RSA Basics

– RSA = Rivest, Shamir and Adleman, 3 proposers, MIT, 1978.

– RSA is a public key system, i.e. a public key is used for encrypting. But a private key
must be known for deciphering. So anyone, essentially, can encrypt. But only cognoscenti can
decrypt.
– Plaintext is encrypted in blocks.
– Each block is upper-bounded by a numeric value n. This means that block size is
log2(n). (Why? n = 7 gives binary value 111. log2 7 < 3 since log2 8 = 3.)
≤ – In practice, block size is 2k bits with 2k < n 2k+1.
– Plaintext block: M ≤
– Ciphertext block: C
– C = Me mod n
– M = Cd mod n = (M e)d mod n = M ed mod n
– Both sender and receiver know the value of n.
– Sender knows the value of e.
– Receiver knows the value of d.
– So:
Public key = e, n
Private key = { d, n }
– Note on right {hand}term of expression for M above:
(ax)y = axy
Cf. (32)2 = 92 = 81
or 34 = 3.3.3.3 = 81
– Aim: choose e, d (and n) in such a way that nothing (e.g. ciphertext C characteristics;
or public key values e and n) will “give the game away”.
– Numbers which are prime or relatively prime are a very good basis for such values.
– A “one-way function”: a function which is easy to calculate but difficult to compute
inverse function. E.g. power function. 3 7 is not too hard to determine; but the 7th root of
a number is not easy to determine. Second example: multiplying prime numbers together.
Both examples are used in RSA.
– Also known as a “trapdoor function”: determining inverse is difficult.
– Knowledge of e, n is more or less useless for inferring value of d. As we will see, both
have prime factors, p { } Knowledge of p and q would be an excellent start to cryptanalysis
and q.
of such a public key system (we think!). (Have a quick look at the next section to see how e
and d are constructed from prime numbers p and q.)
We could factorize n to get p and q, we suppose.
We know e because it is public.
So d could be derived fairly easily.
Factorize n? Say n is about 200 decimal digits. Then it would take about 30 million years
to do the factorizing!

Example pp. 278-279 of Singh (1999): Scientific American (Martin Gardner) published a
challenge in 1997 to factor a number N with 129 digits. Solution found by team of 600 people
in 1994. In solution p and q were 64- and 65-digit primes.

RSA: the algorithm

– Select two primes, p and q. E.g. p = 3,q = 17.
– Form product, n = pq = 51.
– And: (p − 1)(q − 1) = 32. ;1;1;128;128;1;0x;1;1;128;128;1;0x – Choose number e between
3 and (p − 1)(q − 1), relatively prime to the latter. E.g. e = 7.
– Next choose d such that ed mod ((p − 1)(q − 1)) = 1.

1
 I.e. ed = k(p 1)(q 1) + 1, k integer.
Here: 7d mod — 32 = 1 −
giving d = 23.
Show this: 7 . 23 = 161. 161/32 = 5 + remainder 1. Consequently we see that 161 mod
32 = 1.
– Next define the public key: (e, n) = (7, 51).
– Say, message is M = 2.
– Ciphertext, C = Me mod n = 27 mod 51 = 128 mod 51 = 26.
– Decipherment requires knowledge of (d, n). I.e. (23, 51).
– Then: M = Cd mod n = 2623 mod 51.
But how do we solve this?!
– One thing we can do is factorize as follows:
2623 mod 51 = (261.262.264.2616) mod 51
We know that ab mod n = (a mod n . b mod n) mod n.
So this implies:
(261.262.264.2616) mod 51 = 26 mod 51 . 676 mod 51 . 264 mod 51 . 2616 mod 51) mod 51
(We’ve left some parts unresolved for the moment. Now we’ll use: 676 = 51 . 13 +
remainder 13)
= (26.13.((13.13) mod 51).(2616 mod 51)) mod 51
(Now we’ll use: 13 . 13 = 169. 169 mod 51 = 16.)
= (26.13.16.((16.16.16.16) mod 51)) mod 51
= (26.13.16.((16.16) mod 51).((16.16) mod 51)) mod 51
(Now use: 16 . 16 = 256. 256 mod 51 = 1.)
= (26.13.16.1.1) mod 51
(Just multiply this out. 26 . 13 . 16 = 5408. We find that this equals 51 . 106 with
remainder 2.)
= 2.
This is of course our input message, M = 2.
We certainly need a better way to solve such an equation. We will write a little program
which will do this for us.

Algorithm for finding private key, d

– We want to solve the following for d: ed mod φ = 1
– By definition, φ = (p 1)(q 1)
– Take e = 7,φ = 32. We—are using
− the figures used in earlier example.
– Define r(0) = φ = 32, and r(1) = e = 7
– Solving means that we seek: e.d = k.φ + 1 for constant k, i.e., k.φ + e.d = 1 or using
our new notation, Const. . r(0) + d.r(1) = 1. −
– First phase of the algorithm is to determine a sequence of remainder terms based on
modulo r(.) terms (see the following) until we get r(k) = 1 for some integer k:
r(0) = a(1)r(1) + r(2)
r(1) = a(2)r(2) + r(3)
r(2) = a(3)r(3) + r(4)
etc.
– This iterative scheme allows us, by back-substitution, to determine r(k) = u.r(0)+v.r(1)
which is the solution we are looking for.
– The form of this solution is right: r(k) = 1 following the recurrence above, φ = r(0)
by definition.
– r(1) = e again by definition
– This leads to the coefficient v being what we are looking for.
– Let’s proceed:
32 = a(1).7 + r(2) = 32 = 4.7 + 4
⇒ = 7 = a(2).4 + r(3) = 7 = 1.4 + 3
r(1) = a(2).r(2) + r(3)
r(2) = a(3).r(3) + r(4) = ⇒4 = a(3).3 + r(4) = 4 = 1.3 + 1
So r(k) = 1 and k = 4. ⇒

2
 Example of back-substitution.
Take [1] r(2) = a(3).r(3) + r(4) = r(4) = r(2) a(3).r(3).
Now r(1) = a(2).r(2) + r(3) = r(3) ⇒ = r(1) a(2).r(2)
−
Back to [1]: ⇒ −
r(4) = r(2) a(3).r(1) + a(2).a(3).r(2) = r(4) = r(2) 1.7 + 1.1.r(2)
—
Now r(0) = a(1).r(1) + r(2) = r(2) = r(0)⇒ a(1).r(1) =− r(2) = 32 4.7 = r(2) = 4
⇒
So, r(4) = r(0) a(1).r(1) a(3).r(1) −
+ a(2).a(3)[r(0) ⇒
a(1).r(1)] = −
—
r(4) = r(0)[1 + a(2).a(3)] −
+ r(1)[ −
a(1) a(3) a(1).a(2).a(3)] =
r(4) = r(0)[1 + 1.1] + r(1)[ 4 1— 1.1.4] − = −
r(4) = r(0).2 + r(1).( 9) — − −
So now we finally have − our value, 9. Are we right? We have r(0) = 32, r(1) =
7, and r(4) = 1. So we are right. −
But a positive number is needed (unless we want to deal with very small fractions). We
are working in an arithmetic modulo φ, i.e. modulo 32. We know that 9 23 mod 32 which
—
is what we are looking for. This was the value used in the example previously..

Example 2 of RSA encryption

– M = “MAKE CONTACT IMMEDIATELY”
– Say, A = 01, B = 02, C = 03, D = 04, etc.
– M = 13 01 11 05 03 15 14 20 01 ...
– Use blocks of 4 digits:
M1 = 1301
M2 = 1105
etc.
– Take p = 47,q = 59.
– So n = pq = 2773 and (p 1)(q 1) = 2668.
– Value of e must be chosen —between − 3 and 2668.
– Let’s take it as e = 17.
– Now, for d, ed mod (p 1)(q 1) = 17d mod 2668 = 1.
(Explanation: 17d = k.2668 — + 1 for
− some integer k. Find d = 157.)
– Encipherment of M1 = (1301)17 mod 2773 = x.
– Decipherment of x = (x)157 mod 2773.
Latter has to equal our message block,
1301.

RSA Example 3
– 2 primes, p, q. p = 7,q = 17.
– n = pq: 7 x 17 = 119 = n.
– φ(n) = (p 1)(q 1) = 6 16 = 96.
– e relatively —
prime − × than φ(n), greater than 3. Take e = 5.
to φ(n), less
– d s.t. ed = 1 mod 96 and d < 96. Find d = 77 (because 77 5 = 385 = 4 96 + 14).
– Public key = (e, n) = (5, 119). × ×
Private key = (d, n) = (77, 119).
– Plaintext input message: M = 19.
– Ciphertext, C = Me(mod n) = 195(mod 119) = 2476099 mod 119 = 66.
– Decryption: M = Cd(mod n) = 6677(mod 119) = 19.
– Best to have a little program to solve these equations! We’ll look now at an algorithm.

3
 Review
DES, IDEAL etc. use symmetric keys
I.e. same key for E and for D
With public key systems, you create KE and
KD KE is public, available to anyone
KD is private, available to you only
Key length is short, e.g. 56
compared to key lengths in public systems

Euler’s totient function, φ(n)

We have already seen how we use n = pq in the RSA algorithm, and furthermore φ =
(p 1)(q 1). This function φ is interesting in its own right. It will lead us also to Euler’s
—
theorem, − be used below.
to
Euler’s totient function, φ(n): the number of positive integers less than n, and relatively
prime to n. Let’s see:
n 1 2 3 4 5 6 7 8 9 10 11
φ(n) 1 1 2 2 4 2 6 4 6 4 10
(See Stallings, chapter 7.) For a prime number, p, φ(p) = p 1.
Now suppose we have two prime numbers, p and q, then − for n = pq, φ(n) = φ(pq) =
φ(p)φ(q) = (p − 1)(q − 1).
Euler’s theorem: from every a and n that are relatively prime, aφ(n) ≡ 1 mod n.
Example 1: a = 3, n = 10. Then: φ(10) = 4. We have: 34 = 81. We can easily see that
Euler’s theorem is true: 81 ≡ 1 mod 10.
Example 2: a = 2, n = 11. Then: φ(11) = 10. We have: 210 = 1024. We see that:
1024 ≡ 1 mod 11.
Remark: If n is prime, then φ(n) = n 1, and so we have Fermat’s theorem (also known
as Fermat’s Little Theorem). −

Solving expressions like 2623 mod 51

Or M = 6677 mod 119
We will consider two different ideas, and then proceed to get them implemented as an
easily-programmable algorithm.
1. [(a mod n) × (b mod n)] mod n = (ab) mod n
Check this:
17 × 13 mod 5 = 221 mod 5. Have: 221/5 = 44+ rem. 1 which gives an answer of 1.
Alternative: 17 mod 5 = 2; 13 mod 5 = 3; 2 × 3 mod 5 = 1.
2. Taking this idea further:
x16 = x × x × .. . × x, resulting in 16 − 1 = 15 multiplications.
Alternative: x16 : x × x = x2 −→ x4 −→ x8 −→ x16, resulting in 4 multiplications.
We will now proceed to operationalize these two ideas.
Suppose we are trying to determine am with a and m positive integers.
Express m as a binary number: m = bkbk−1 . .. b0 where each b is a binary digit.
Example: 17 = 1 0 0 0 1 implying b4 = 1, b3 = 0, b2 = 0, b1 = 0, b0 = 1.
Σ
k
Rewriting: m = bi 2i with bi ∈ {0, 1}.
i

4
 Σ
k
b 2i k
i
Therefore: am i=
a =
(Read: product over i = 0, 2, . . . k of a to the power of bi 2i .)
For the example of a17:
4 3 2 1 0 4 3 2 1 0
a1×2 +0×2 +0×2 +0×2 +1×2 = a1×2 ×a0×2 ×a0×2 ×a0×2 ×a1×2 .
So, now, finally:
i i
am mod n = [Πk abi 2 ] mod n = (Πk [abi 2 mod n]) mod n.
i i
Here we are generalizing: (ab) mod n = [(a mod n)(b mod n)] mod n.

Algorithm:

c → 0; d → 1;
for i → k downto 0{
c → 2 × c;
d → (d × d) mod n;
if bi = 1 then {
c → c + 1;
d → (d × a) mod n;
}
}
return d

Note that variable c is not output from the above.

Example: n = 561,a = 7,m = 560.
am mod n ⇐⇒ 7560 mod 561.
m = 560 =⇒ bkbk−1 . .. b0 = 1 0 0 0 1 1 0 0 0 0. We find k = 9.
i 9 8 7 6 5 4 3 2 1 0

bi 1 0 0 0 1 1 0 0 0 0

c 2.0 + 1 2.1 2.2 2.4 2.8 + 1 2.17 + 1 2.35 2.70 2.140 2.280
= 1 = 2 =4 = 8 = 17 = 35 = 70 = 140 = 280 = 560

d 7 49 157 526 160 241 298 166 67 1

Answer: 1.
How did we get:
d = 7? Case of bi = 1 so d ← (d × a) mod n = 1 × 7 mod 561 = 7.
d = 49? Case of bi = 1 so d ← (d × d) mod n = (7 × 7) mod 561 = 49.
d = 157? Case of bi = 1 so d (d d) mod n = (49 49) mod 561 = 2401 mod 561.
Have 2401/561 = 4 + rem ← × ×
157.
Another example (start only): 6677 mod 119 (which, as we have said, = 19).
77 = 1 0 0 1 1 0 1 so that k = 6.
i 6 5 4 3 2 1 0
bi 1 0 0 1 1 0 1
c 1 2 4 9 19 38 77
d 66 19

Generating large prime numbers

– Sieve of Eratosthenes.
– Pick a number, initially 2.
– Let 2 = first prime number.
– Divisible by a prime number found so far? No. Keep 2.
– Add 1 to number.

5
 – Divisible by 2? No. Keep 3.
– Add 1.
– Divisible by 2, 3? Yes for 2. Reject.
– Etc. Not too practical for large primes.
– Note: there are “weak” and “strong” prime numbers for RSA.

– Alternative: we choose a number and then test for primality.

– Following algorithm like in previous section: we are working on the number (n 1)
represented by bits bkbk 1 .. . b1b0. The algorithm is to calculate an−1 mod n. −
−
– We know from Fermat’s theorem that a n−1
1 mod n if n is prime.
– So if we solve an−1 mod n and find the result to ≡ be not equal to 1, then n is not prime.
– The algorithm we looked at above will do this test for us.
– So we choose an odd number n, and a randomly integer a < n, and carry out this test.
– Algorithm returns either “not prime” or “possibly prime”.
– Let the probability of the above procedure saying that n is “possibly prime” and in
fact is not prime be less than 0.5.
– So, repeatedly invoke the algorithm, using different values of a.
– If we get a “possibly prime” outcome s times in succession, then the probability that n
is prime is at least 1 2−s.
−
– We take lots of values of a, and each test strengthens our case. There remains a small
chance of a non-prime slipping through.
– This completes the overview of this probabilistic algorithm for testing whether or not
we have a prime number.
– It is an example of a stochastic algorithm for primality testing.
– We take values for a and increase the evidence (and our confidence) in favour of the
number being prime.
– We will never know for certain with this procedure if the number is prime.
– But we also know that the probability is arbitrarily low that it is non-prime.

El Gamal encryption
– Based on discrete logarithm problem (which we will not discuss).
– Unlike RSA, El Gamal encryption has public parameters which are shared between a
number of users. They are called domain parameters.
• p, a large prime, around 1024 bits,
• p − 1 is divisible by another prime, q, of around 160 bits,
• g such that g(p−1)/q mod p ⊕=
1. Then, one creates
• private key, x, an integer,
• public key, h = gx mod p.
– Note: in RSA two large primes are needed. In El Gamal, a random number is needed,
plus a modular exponentiation.
– To encrypt a message, m (also in mod p)
• generate a random ephemeral key, k,
• set c1 = gk
• set c2 = mhk
• which gives ciphertext c = (c1, c2).

6
 – Each message has a different ephemeral key, so encrypting the same message twice
will produce different ciphertexts.
– To decrypt a ciphertext c = (c1, c2):
c2/cx = mhk/gxk = mgxk/gxk = m all with modulus p.
1
– Example: p = 809,q = 101,g = 3
– Aside: recall that Fermat’s Little Theorem states that if p is prime, and a is a positive
integer not divisible by p, then it holds: ap−1 1 mod p, and hence 3808 1 mod p.
– For public and private keys, choose: x =≡68, and h = gx mod p = 368 ≡mod 809 = 65.
(Exercise: check this.)
– Encrypt a message, m = 100.
– Generate a random ephemeral key, k = 89.
– c1 = gk mod p = 389 mod 809 = 345. (Exercise: check this.)
– c2 = mhk mod p = 100(6589 mod 809) mod p = 100 709 mod p = 517. (Exercise:
check this.) ×
– Ciphertext, c = (345, 517).
– Decryption: c2/cx = 517/34568 = 517/709. (Exercise: check this.)
1

– Here we look a bit stuck. Let’s see... what is 709−1 mod 809? We see that we need the
multiplicative inverse of 709 modulo 809.
– What is 2−1 mod 5? Answer is 3, since 2 3 = 6 1 mod 5.
– Here is how we solve this. We first determine × gcd(709,
≡ 809) using the Euclid algorithm.
Do this. We solve for gcd(809, 709):
809 = 1 709 + 100 gcd(709, 100)
709 = 7 ×100 + 9 gcd(100, 9)
100 = 11 × 9 + 1
So gcd(809,×709) = 1 (hence these numbers are relatively prime).
Now we seek the linear combination d = ua + vb for d = gcd(a, b).
We back-substitute from the Euclid algorithm in order to do this:
1 = 100 11 9
= 809 1 — 709 × 11(709 7 100)
= 809 —1 ×709 −11 709−+ 77(809 1 709)
= 809 12 709 + 77 × 809 77 709
— × − −
—
= 78 809 89 709× × − ×
×
(Excercise: − this.)
check ×
From this, we read off the multiplicative inverse of 709 with modulus 809, i.e. 709−1 mod
809 = 89.
We −need a positive integer, so knowing that 1 809 = 720 89 we find the solution as
720. — × −
Good, now back to solving 517/709 mod 809.

We have 517/709 mod 809 = 517×709−1 mod 809 = [(517 mod 809)(709−1 mod 809)] mod
809 = 517 × 720 mod 809 = 100. QED.
– Another version of El Gamal uses elliptical functions. (We won’t deal with these.)
– Rabin encryption: based on the difficulty of extracting square root modulo n = pq.

Authentication
1. Message confidentiality
– Disclosure
– Traffic analysis
2. Message authentication
– Masquerade
– Content modification
– Sequence modification
– Timing modification

7
 3. Digital signature
– Repudiation

Encryption ensures against

Authentication functions
eavesdroppers Authentication ensures
– MAC for integrity, i.e. demonstrably no tampering with message.
– Message encryption: against imposters
public, private. Integrity ensures
– Message authentication code (MAC): cryptographic checksum, appended to message.
againstismodified
– Hash function: a message mapped messages
onto a fixed length code.
MAC: need not be encrypted itself. It can be used to compare, using shared secret key,
the message as transmitted at the sender end, and as received at the recipient end.
MAC = fk(M ) where M is message, k is secret key, f is check function. Transmitted
then is: M MAC.
ǁ
MAC is therefore separate from the issue of
encryption. Why MAC and not just encryption?
– E.g. message in the clear, one recipient (among many recipients) is responsible for
authentication.
– Heavy load, encryption, one recipient responsible for authentication.
– Authentication of software, which itself doesn’t have to be encrypted.

Example of MAC, based on DES, referred to as Data Authentication Algorithm.

– CBC (cipher block chaining) mode of DES, with initialization of zero.
– 64-bit blocks: D1, D2, . . . , DN . Last: padding with zeros if necessary.
– E = DES encryption algorithm, secret key, K.
– DAC, data authentication code:
O1 = EK (D1)
O2 = EK (D2⊕ O1)
O3 = EK (D3 O2)
... ⊕
ON = EK (DN ⊕ ON−1)
– Finally, DAC returns ON or leftmost M bits of this block, with 16 M 64.
– I.e. take final block as the MAC, after an optional post-processing stage≤ and
≤ truncation.

Alternative based on hash functions: hash code can be appended to message and then all
encrypted.
Simple hash function:
ci = bi1 ⊕ bi2 . . . ⊕ bim
ci is ith bit of block.
b is block, ⊕ is XOR.
Fixed length public function key
D.S. – – Y
MAC Y Y Y
Hash Y Y –
Informally, we could say that D.S. is to check human violation, MAC is to check
“technical” and human violation, and Hash is to check “technical” violation.

8
 Hash functions
– Basic properties include:
– 1. Ease of computation.
– 2. Compression. h(x) is of fixed length.
– 3. Pre-image resistance. Given y, it is difficult to find x s.t. h(x) = y.
– 4. Weak collision resistence. Difficult to find x and xJ, x xJ s.t. h(x) = h(xJ).
– 5. Strong collision resistence. Infeasible to find...
– Points 1 to 4 lead to one-way hash function. Point 5 leads to a collision-resistent hash
function.
– Output of hash function: hash value, message digest, checksum.
– Examples: SHA-1 (Secure Hash Algorithm 1), MD4, MD5. SHA-1 processes 512-bit
blocks and generates 160-bit hash values.
– 80 rounds of processing on five 32-bit inputs. Combinations of AND, OR, NOT and
XOR operations used.
– See Stallings.
– Rivest’s MD5, Message Digest Algorithm.
– Arbitrary length message is mapped into 128-bit hash (“fingerprint of message digest”).
– Seek:
(1) “Impossible” to find 2 messages which produce same result.
(2) “Impossible” to generate a message that will produce a predefined hash result.
– Estimated that the number of operations required to generate two messages that
produce the same MD is 264.
– Complexity of finding a message with a predefined MD is 2128.

Message integrity with hash functions, and birthday

attacks
– Hash function: take variable input and map into set of output values of fixed length.
– Hash function is publicized.
– Integrity of the message can be checked by use of its hash value.
– Hash function should be a one-way function.
– Hash function must be collision-free. I.e. for two messages M and M’, we cannot have
h(M) = h(M’). A “birthday attack” on message integrity makes use of the birthday paradox.
– Birthday attack: it is probable enough that an alternative message produced the same
hash code.
– Say we have 23 people at a party. Then the probability that two or more will have the
same birthday is greater than 50%. How come? For 365 days in the year, we would expect
that two people having the same birthday would be a fairly improbable event.
– We have stated the problem as “two or more people” having the same birthday. So let
us put the problem into reverse gear for the moment, and ask what is the probability of two
or more people do not share the same birthday.
– We proceed as follows. Let r = 23. Let n = 365.
– We take one of the people (on the list of r-values), and cross this person’s birthday off
the n-list. What is the probability that we do not find an already-selected birthday?
– For first person, we have no already-selected birthday, so this probability must be 1.
– For second person, probability is (n – 1)/n.
– For third person, probability is (n – 2)/n.
– Etc. Putting this all together (remember: a joint event means that the individual
probabilities are multiplied):
n!
P(no birthdays the same) = n . n−1 . n−2........n−r+1 =
n n n n (n−r)!nr
– For n = 365 and r = 23, this probability is 0.493.
– Therefore the probability that two or more people share the same birthday is 1.0
0.493 = 0.507. −

9
 – Translate this to the area of hash functions: for a given length of hash code, n, and a
given number of attempts at cracking it, r, we find a particular probability, p.
– For the probability of cracking the hash code to be less than 10 −6 after 255 attempts,
then we must have n > 2128. I.e., hash code length, n, must be at least 128 bits.
– We can use DES as a hash function.
– Message, M, is enciphered with DES and a secret key.
– Result is added to M, modulo 2.
– Key for subsequent blocks could be defined from the hash function. If the hash function
is based on a specified number of bits, then these can be read off (e.g., from the left of the
final outcome).

Key distribution – and Diffie-Hellman

– Key distribution, communiction: why important?
– Problem of getting the top secret symmetric key between sender and receiver.
– Points to need for public keys, i.e. not top secret.
– Key distribution problem tackled by Diffie, Hellman and Merkle.
– Little story of Alice sending message to Bob, with malevolent Eve trying to intercept.
– Principle:
A −→ B: EA(M)
Message
B −→ A: Eintegrity – was message okay?
B EA(M)
A decrypts using her own key leaving: EB(M)
A Entity
B:authentication
EB (M) – was “Alice” really Alice?
Now−B knows his key and can decrypt.
Message authentication – both together
– Alternatively:
EA(M)
EB EA(M)
DA EB EA(M)
DB DA EB EA(M)
But the problem is: is this algorithmically possible? What class of functions allow us to
do other than the normal “last in, first out” calculation?
One-way functions are needed. (Reminiscent of mixing a number of paint colours. Easy
to mix, practically impossible to separate afterwards.) Modular arithmetic is rich in one-way
functions. One-way function can provide a solution to the “last in, first out” dilemma.
Use function like: yx(modp) where y and p are in the public domain – or at least not
really critical.
Example where y = 7, and p = 11.

A B
Step 1 Secret key chosen, e.g. 3 Secret key chosen, e.g. 6
Step 2 Encrypt: 73(mod11) Encrypt: 76(mod11)
= 343 mod 11 = 2 = 117649 mod 11 = 4
Step 3 A sends 2 to B B sends 4 to A
Step 4 Works out: 43(mod11) Works out: 26(mod11)
= 64 mod 11 = 9 = 64 mod 11 = 9

10
 Hence they have ended up with one and the same key.
One could say that a secret key has been established by public
discussion. Diffie-Hellman-Merkle key exchange protocol.
Alice Bob
a ga −→ ga
gb ←− gb b
– Ephemeral “secrets”, a, b.
– Alice can compute K = (gb)a since she knows a and was sent gb by Bob.
– Bob can also compute K = (ga)b since he knows b and was sent ga by Alice.
– Attacker Eve can see ga, gb and needs to recover K = gab. Not easy!
– Another example: p = 2147483659, g = 2.
Alice Bob
a = 12345 b = 654323
A = ga = 428647416 given to Bob A
B Given to Alice by Bob B = gb = 450904856

Secret key: Ab = 428647416654323 mod p

= Ba = 45090485612345 mod p
= same key.
– Usually p is around 21024. Elliptic curves allow for use of p = 2160.
– Diffie-Helman key agreement protocol: as seen.
– Diffie-Helman key transport protocol: one party uses a long-term key of the form ga
instead of ephemeral “secret”.
– Problem of authenticating sender. When someone says he is Bob, how do you know it
is not really Eve?
Alice Eve Bob
a ga
gm − m
←
gam gam
n −→ gn
g b b
←
gbn gbn
– So Alice agrees a key with Eve, thinking it is Bob.
– Bob agrees a key with Eve, thinking it is Alice.
– Eve examines communications as they pass through her. No detection of this.
– Solution: digital signature.

Digital signature
– To authenticate the sender.
– Let the sender encrypt a message using his/her private key.
(Not a good idea in principle, since anyone can decrypt this using the sender’s known –
axiomatically – public key.)
– Then decrypt using the sender’s public key.
We know therefore that it could only have come from them.
– This is a public key system in reverse!
– Used e.g. for authentication of software.

11
 Left → right Encryption: Decryption:
You use: my public key I use: my private key

Left ← right Signature verification: Signing:

I use: your public key You use: your private key

– We could use RSA for both data and the digital signature:
– Before A sends message, a digital signature is added which is encrypted with A’s
private key, SA. (S = secret.)
– Then encrypted with public key of B, PB .
– Sent.
– B then decrypts using SB .
– Authenticates using A’s public key, PA.
– Overall: PA SB PB SA (M)
– Hash function may precede use of RSA to make for compact set of data.

Public key infrastructure, PKI

– Set of protocols, services and standards supporting applications of public key cryptog-
raphy. Relatively recent use of term.
– Services include: key registration – issuing a new certificate for a public key; cer-
tificate revocation – cancelling a previously issued certificate; key selection – obtaining a
party’s public key; trust evaluation – determining whether a certificate is valid, and what
operations it authorizes.
– There is no single pervasive PKI today. Often various “root” or “top level” certificate
authorities in a global PKI.
– PKI standardization efforts are underway by various governments and standards bodies.

- Distribution of public keys

— Public announcement (cf. popular use of PGP)
— Publicly available directory (trusted organisation)
— Public key authority
— Public key certificates
- Distribution of private keys
— With or without confidentiality and authentication
See Stallings, section 6.3
See RSA “Frequently Asked Questions About Today’s Cryptography”, especially “Public
Key Issues”,
http://www.rsa.com/rsalabs/faq/4-1-3.html

– Key pair: anyone who wishes to sign messages or to receive encrypted messages must
have a key pair.
– Companies may use one or more pairs for encryption – maybe keys stored under key
escrow to safeguard the key in event of loss, maybe a single key non-escrowed for authentica-
tion.

– Key escrow.

– Trusted third parties.

... keep copies of private keys, to aid in key

recovery.

12
 – User can generate own key pair, or company officer. Kerberos is a secret-key authenti-
cation system, which uses a central server to generate keys.
– After key pair generation, a user must register the public key with a central
administra- tion called a Certifying Authority, CA. The CA returns a certificate attesting to
– Kerberos
the validity of the user’s public key.

– Authentication system for use in open distributed computing

– In RSA, private key (modulus, exponent) is unique. But the exponent could be shared
environment.
by a group of users. Some values could be used as “public exponents” so that public key
operations – encryption and signature verification – are relatively fast compared to private
– From MIT
key operations Project Athena.
– decryption and signing.

Security issues in relation to PKI agencies

1. Every key should have an expiration date to guard against long-term cryptanalytic
attack.
2. Appropriate key size can be defined in relation to expiration date.
3. Signature verification should include check for expiration date.
4. An expired key may need to be retained for a period in order to decrypt still outstanding
encrypted messages.
5. If a key is lost, the CA revokes the relevant certificate. A certificate revocation list,
CRL, is kept up to date.
6. If a private key is compromised, the relevant CAs must be notified for revocation of
the relevant certificates. Then a new key pair must be generated, and a new certificate
obtained.
7. A private key should be stored encrypted under a password. Preferably on disk which
is not network-accessible.
8. Similarly private keys at CAs have to allow for illegal acts by their employees, etc.
Several people must use their data keys to access e.g. a system called SafeKeyper
from BBN.
9. Passing public key: in the clear, but one should verify the key (e.g., by computing a
hash of the key and verifying by some independent communication).

Certificates
– Certificates: digital documents attesting to the binding of a public key to an individual
or other entity. In some cases, there may be a chain of certificates, each one certifying the
previous one.
– In simplest form, certificates contain a public key and a name. Also: expiration date,
name of CA, digital signature of the certificate issuer. Most widely used format for certificates
is X.509.

13
 – Certificates typically used to generate confidence in the legitimacy of the public key.
They are a type of digital signature which protect keys from forgery, false representation, or
alteration. Verification can be performed with greater or lesser rigour.
– Could associate one or more certificates with every signed message. Alternative is a
hierarchical certificate chain, with one certificate testifying to the authenticity of the
previous certificate. A top level certifying authority is trusted without a certificate from any
other certifying authority.
– Examples of CAs: Baltimore Technologies, RSA Security, VeriSign. Or a CA protocol
is found in Apple’s Mac System 7.5.
– Preventing attacks on CAs: extensive cryptanalytic attack is preempted by regular key
change; if an old key is broken, then time-stamping becomes important; impersonation is
avoided by personal indentification, notarization, etc.; bribery or other CA employee
illegality is limited by more than one employee being required to issue a certificate.

X.509 (ITU) certification authority

– Part of set of standards for directory services.
– Such services include also: user names, network addresses, etc.
– Repository of public key certificates. Each certificate: public key of user, lodged by and
signed with the private key of a trusted certificate authority.
– Alternative authentication protocols are supported also.
– X.509 CA is used in SSL, SET and elsewhere. (On SSL and SET, see below.)
– In X.500, Distinguished Names can be defined. E.g., country or state names, company
or trading name. (ITU X.400 standards relate to email. X.500 standards relate to directory
services – naming and name resolution conventions, yellow page services, etc.)
– See Stallings, section 11.2.

Standards authorities
– (Not just related to public keys, of course.)
– ANSI
– ITU (CCITT)
– ISO
– IEEE
– IETF
– Industry consortia
– Government bodies, agencies

Zero-knowledge techniques
– In authentication, to prove your identity, you say something about yourself. E.g. pass-
word. But now your identity is known. What if the partner in the exchange exploited this
knowledge to pretend that he/she was you?
– Zero knowledge techniques authenticate you without giving secret information away.
– Use techniques similar to RSA. But, for digital signatures, much more efficient techniques
than RSA are used.
– Identification sequence is established which, for the correct person, must lead to a right
conclusion for that person.
– See pp. 181-190 of van der Lubbe for a good description.

14
 Fair cryptosystem
– How to cater for criminal use of cryptography?
– Force surrender of keys is threat to person’s privacy.
– Fair cryptosystem: authorized body can decrypt.
– How?
– Deposits parts of key with trusted body.
– Clipper, capstone.
Two encryption systems, resp. for telephone and computer communication, adhering to
American Escrowed Encryption Standard, adopted in 1994.
System of key escrow: a pre-installed chip holds half your private key, and the other
half is lodged with a government agency.
Considered to have failed.

Internet and web security issues

– Have a look at the Internet protocols page at
http://www.rad.com/networks/1997/nettut/protocols.html
– Note: (i) OSI 7-layer model – Application, Presentation, Session, Transport, Network,
Link and Physical; Internet protocol suite – in layers 5, 6 and 6, Telnet, ftp, SMTP, SNMP,
HTTP, and others; in layer 4, tcp, UDP; in layer 3, IP.
– Internet security consists of three distinct services: (i) access security, (ii) transaction
security, and (iii) authentication.
– Access security includes passwords and the use of proxy servers.
– What is a proxy server? It is a specialized http server. Used in conjunction with
corporate firewall. Firewall implies no direct http access to outside world. Proxy is an
indirect connection, in that everything is chanelled through it. A proxy can cache
documents efficiently from the outside world.
– Transaction security includes SSL, Secure Socket Layer.
– Authentication includes password, digital signature, or biometric technique
(fingerprint, iris).
– SSL runs on top of a transport protocol, but under application protocols such as http
and ftp. Operates between browser and a server.
– SSL protects the link, not the documents or files transferred. It authenticates the
server, and optionally the browser.
– Typically uses port 443. HTTP usually uses port 80. If SSL is in use, often the URL
begins with https:// rather than http://
– SSL makes use of RSA as its public-key cipher, X.509 certificates for authentication,
and DES or some other private key system for its symmetric cipher.
– TLS (Transport Layer Security) is a protocol like, and based on, SSL. WTLS (Wireless
TLS) is used in WAP (Wireless Application Protocol), and is therefore best for low-
bandwidth bearer networks.
– SSH (Secure Shell) permits secure remote access across a network from one computer
to another. Effectively a secure telnet, rlogin or rsh.
– SET, Secure Electronic Transfer.
– Designed for credit card use over Internet. Developed jointly by Visa and Mastercard.
Specification is open.
– Secure communication, X.509 certificates, privacy.
– Partners: cardholder, merchant, issuer. Also: certificate authority, payment gateway
and acquirer (latter: financial institution processing authorization and payment).
– Uses DES for bulk data encryption, and RSA for signatures and public-key encryption
of data encryption keys and bankcard numbers.

15
 – S/MIME (Secure / Multipurpose Internet Mail Extensions) adds digital signatures and
encryption to MIME messages. MIME is an email standard: (structured) header and (unstruc-
tured) body of message are specified. MIME allows for support of multimedia files (image,
audio, video, etc.)
– PGP is due to Phil Zimmermann. Used, e.g., in email. Multiple platform. Address:
www.pgp.com, www.pgpi.com
– Lots of difficulties due to (i) RSA holding licences, (ii) US Govt’s objections to export
of anything strongly encrypted, and even more so the technologies behind strong
encryption.
– So put onto a newsgroup in 1991.
– Symmetric encryption is fast, IDEA even more than DES.
– Symmetric key is a problem, in practice.
– RSA looks after key distribution well, but is computationally more costly.
– PGP combines these: RSA is used for the key, and IDEA for the message.

16