. 11
( 16)


14. The continuous approxiniation phase of the MD4 attack relies on the
fact that for the functions F and G in (5.4) and (5.5), nearby inputs
produce nearby outputs. Suppose that the 32-bit words A , B and C are
rcplaced with 8-bit bytes a , b and c. Furthermore, suppose that a™ differs
from u in exactly one randomly selected bit position, b differs from b

in exactly one randomly selected bit position, and c™ differs from c in
exactly one randomly selected bit position. Write computer programs
to answer the following.

a. Find the probability that F ( u , b. c ) and F(a™, b™, c™) differ in ex-
actly k bit positions, for k = 0 , 1 , 2 , . . . .8.
b. Find the probability that G ( a , b . c ) and G(a™,b™,c™) differ in ex-
actly k bit positions, for k = 0 , 1 , 2 , . . . ,8.
c. Find the probability that H ( a , b , c ) and H(a™,b™,c™) differ in ex-
actly k bit positions, for k = 0 , 1 , 2 , . . . , 8 , where H is defined
in (5.6).

15. Implement tho continuous approximation equation solving phase of the
MD4 attack. Use your program to provide empirical estimates of the

a. How many iterations, on avcrage, are required before the chcck
condition in (5.35) holds?
b. In the continuous approximation, on average, how many iterations
are required before the solution converges? That is, given a so-
lution to (5.35)?how many iterations are needed before (5.36) is
c. The continuous approximation can sometinies fail to converge. Us-
ing a cutoff of 100,000 iterations, what is the probability that the
continuous approximation fails to converge?
d. How marly nonadmissiblc solutions are computed, on average, be-
fore one admissible solution is found?

16. mJrite a program to implement the differential phase of the MD4 attack.
Use your program to empirically estimate the probabilities that appear
in Table 5.5.

17. Dobbertiri [42] claims that the probability of siiccess of the differential
phase of the MD4 attack is 1/222. Assuming this is the case, show
that the work factor for Dobbertin™s attack is roughly equivalent to the
cornputation of 220 h4D4 hashes.
5.6 PROBLEMS 261

18. Approximately how many MD4 collisions can be found using Dob-
bertin™s attack˜?

19. Let M = ( X OX i , . . . , X i s ) ,where
Xo = 0˜1089fc26,
= 0˜9074449b,
X2 X3
= Ox8bf37fa2, = Oxld630daf,
X s = 0x4e4f430a1
X, = Ox63247e24,
= 0x43415254, X7 = Ox410aOa54,
= 0x68742074, Xg = 0x72702065,
= 0x20656369, Xi1 = 0 ˜ 2 4 2 0 6 6 6 f ,
Xi2 = 0 ˜ 2 ˜ 3 6 3 7 3 1 , i 3 = 0x20353934,
Xi5 = 0 ˜ 7 7 6 f 6 ˜ 4 2 .
Xi4 = 0˜20666˜41,

a. Compute the MD4 hash of M .
b. Let MI be the same as M , with the exception that Xi2 is replaced
by X i 2 = X12 1, that is, X i 2 = 0x2˜363732.Compute the MD4
hash of MI.
c. Interpret 111 arid M™ as ASCII text, where the byte order of each X i
is little endian. Then, for example, X6 consists of the bytes


which represents the ASCII text “TRAC”.

20. Let
F ( A , B , C )= (AAB ) V (™A A C )
$ ( A ,B , C ) = (A A B ) C).
™ A

Suppose that A, B and C are 32-bit words selected at random. Then
what is the probability that F ( A , B ,C) = F(A, B , C)?
21. In Section 5.4.2 we described Wang™s “precise differential,” which we
denoted by V X . Given 32-bit words X™ and X , let U = XI A 1 X
and L = 1X™ A X . Then it is easy to see that X™ @ X = U 6 L .

a. Show that for U and L defined in this way,

X™ - X = U L (mod 232). (5.56)

b. Given U = ( u o , u ˜. , . u g l ) , L = ( t o , e l , . . . , t : 3 1 ) and X™ and X as
defined above, define a string S = ( S O ,s1,. . ,s31) with a “+” in
precisely those positions j where u = 0, a LL-” in precisely those
positions where ej = 0, and a “.” in all other positions. Show
that S = V X .

c. Verify that (5.56) holds for every line in Tables A-2, A-3, A-4,
and A-5, that is, show that

L (mod 2 ” ) ,
AOntput = -

where U arid L are determined from the VOutput. T h a t is, U
has a 1 in each position where there is a “+” in VOutput and 0
elsewhere, and L has a 0 in each position where there is a “-”
in VOutput and 0 elsewhere.

22. This problem deals with some properties of cyclic rotations with respect
to the signed differential.

a. Vmify that

b. Suppose that we have X˜ - X = U - L , where U = X™ A - X ,
and L = 1 X ˜ A X . Then, in addition t o the differences being
equal, we have X™ @ X = U @ L , each 1 in U corresponds t o a 1
in X™ and a 0 in X , each 1 in L corresponds to a 1 in X and a 0
in X™. and U and L are “disjoint”, in the sense that U A L = 0.
Givcn such X ™ , X , U and L , verify that

( X ™ << n) ( X << n)
< < (U << n ) - ( L << n).
< <

Either prove this in general, or verify that it holds for all choices
of 1-byte values and for all n = 0 , 1 , 2 , . . . ,7.
X™ X . Give a n
c. Let X™, X , U and L be as in part h. Let 2 = -

example for which

( Z < < n ) # (U << n)
< < ( L << n )

0 . 1 , 2 , . . . ,7.
23. Lct T and y be randomly selected bytes. For each k =
what is the probability p k that

>> k
> . >> k ) - ( y >> k ) ,
(> >
y) =
(J -

where the subt,raction is taken modulo 256?

24. This problem analyzes sonic issues related to the MD5 single-step mod-
ificat ions techiiique.
5.6 PROBLEMS 263

a. Let X and Y be 32-bit words and n E {0,1,2,. . . , 3 1 } and compute

+ (Y << n) (mod
2=X 232).

Denote the bits of 2 as (zo,21,. . ,231). Let in, i l , . . . , ik be a set
of k distinct elements of the set {0,1,2,. . . ,31}. Let E, be the
byte that is all 0, except for a 1 in bit i . Then Ei = 231-i. Let

A = (2 ziOEi,,- zilE,il - . .. - z i k E i k )(mod 2 3 2 ) (5.57)

+ Y (mod
Y = ( ( A 2)>> n )
> 2”).

Show that 2 = X + (p << n ) (mod 2 3 2 ) has zero bits in po-
sitions i n , i ˜ . . . ,ik. Either prove this in general, or show that it
holds for all 1-byte values, with n and k modified accordingly.
b. Suppose that we want to force some bits of 2 to be 1 instead of 0.
How can be accomplish this by modifying (5.57)˜?

25. Consider the MD5 attack, as described in this chapter. Suppose we are
trying to find a collision for the first message block Mo. When we test
the probabilistic conditions, and the test fails, why does it suffice to
only modify the last two words of Mn instead of computing an entirely
new Mn?
26. This problem asks you to demonstrate that a meaningless MD5 collision
can be used in a meaningful attack.

a. Verify that the following two 1024-bit messages (given in hexadeci-
mal) differ, specify the bit positions where the messages differ, and
verify that the two messages have the same MD5 hash value.
e6 ee c4 69 3d 9a 06 98
dl 31 dd 02 c5 af f9 5c
4 7e ab
6 40 04 58 3e 89
2f ca b5 12 b8 fb 7f
83 e4 88 83
55 ad 34 09 f4 b3 02 25 71 41 5a
51 25 e8 f7 cd c9 9f d9 Id bd f2 37 3c 5b
08 80
e4 d8 97 f4
96 Ob Id dl dc 41 7b 9c 5a 65 55 d5
35 9a c7 fO eb fd Oc 30 29 fl 66 dl bl 8f
79 79
75 27 7f 30 d5 5c eb 22 e8 ad ba cc 15 5c
74 cb
ed dd 5f c5 d3 6d bl 9b Oa d8 35 cc a7 e3
dl 31 dd 02 c5 e6 ee c4 3d 9a 06 98 af f9 5c
07 46 04
2f ca b5 12 7e ab 40 58 3e b8 fb 7f 89
34 e4
55 ad 06 f4 b3 02 83 88 83 25 fl 41 5a
51 25 e8 f7 cd 9f d9 Id bd 72 80 3c 5b
08 c9
96 Ob Id dl dc 41 7b e4 d8 f4 5a 65 55 d5
9c 97
47 fO
73 09
35 9a eb fd Oc 30 29 fl 66 dl bl 8f
75 27 7f 79 30 d5 5c eb 22 ad ba 4c 15 5c
ed cb dd 5f c5 d3 6d bl 9b Oa 58 35 cc a7 e3

b. Use the collision in part a to construct two files that display very
different text when viewed or printed, yet have identical MD5
hashes. Hint: Mimic the attack outlined in Section 5.4.7.

27. In Section 5.4.5 we determined conditions on T 5 and T that must he
met for Wang's MD5 attack to succeed. Perform a similar analysis to
determine conditions on T7.

28. In Section 5.4.5 we analyzed steps four and five of the MD5 hash to
determine conditions on the QJ that must be met for Wang's MD5
attack to succeed. Perform a similar analysis for step six.
Chapter 6

Public Key Systems

It is generally regarded as self-evident, that, in order to prevent an interceptor
from understanding a message which is intelligible to the authorised recipient,
it is necessary to have some initial information known to the sender
and to the recipient but kept secret from the interceptor.. ..
This report demonstrates that this secret information
is not theoretically necessary.. ..
- James Ellis [45]

All of the cryptosystems discussed in previous chapters are examples of sym-
metric key ciphers. In this type of system, both parties use a common key
to encrypt and decrypt messages. In public key cryptography, each user has
a key pair consisting of a public key and a private key. Not surprisingly, Al-
ice™s public key is public, while Alice™s private key is known only to Alice.
Anyone can use Alice™s public key (since it is public) to send encrypted mes-
sages to her, but only she can decrypt such messages since only she has the
corresponding private key. Whereas symmetric key cryptography has been
used since antiquity, public key cryptography came into being in the 1970s.
Perhaps the most remarkable thing about public key crypto is that it exists
at all.
A public key cryptosystem is based on a “trap door one-way function.”
The security of a public key cipher rests on this function, which is easy to
compute in one directlion but difficult to compute in the other direction.
Furthermore, the trap door feature ensures that an attacker cannot obtain
information about the secret decryption key from knowledge of the public
encryption key. Examples of trap door one-way functions used in public key
cryptography include factoring (RSA), discrete logarithms (Diffie-Hellman),


and finding the nearest codeword in a linear binary code (McEliece). Finding
a trap door one-way function suitable for use in a public key cryptosystem is
riot an easy task. Consequently, the number of sensible public key cryptosys-
tenis is far smaller than the number of strong symmetric cipher systems.
Digital s i g n a t u r e s can also be implemented using public key cryptography.
Alice can digihlly sign a message by “encrypting” it with her private key.
Then, anyone can “decrypt” the message using Alice™s public key, thereby
verifying that only Alice could have signed the message. In fact, the ability
to create digital signatures is a very useful feature of public key cryptography,
for which there is no analog in the realm of symmetric ciphers.
Alice™s digital signature is similar to her handwritten signature in the
sense that only she can create it, but, in principle, anyone can verify whether
or not the signature is Alice™s. However, digital signatures offer some signif-
icant advantages over handwritten signatures. For example, when correctly
implemented, a digital signature cannot be forged, in stark contrast to a
handwritten signature. Also, a digital signature is tied directly to the signed
document. Whereas a handwritten signature can be photocopied onto differ-
ent documents, a digital signature cannot be duplicated in such a manner.
As discussed in Section 5.1, digital signatures provide integrity. That is,
if Alice signs a message M , the recipient can automatically verify that the
received message is the message that was actually sent. Another important
property of digital signatures is that they provide n o n - r e p u d i a t i o n . When
Alice digitally signs a message, it guarantees that she actually signed the
message and she cannot later claim that she did not do so. That is, Alice
cannot repudiate the signature. While it is possible to provide integrity using
symmetric key cryptography, it is not possible to achieve non-repudiation
using symmetric keys. This follows from the fact that Alice™s private key is
known only to Alice. On the other hand, if Alice wants to communicate with
Bob using a symmetric key, the key must he known to both Alice and Bob.
Since Bob has the symmetric key, he can do anything with the key that Alice
can do. Consequently, if Alice “signs” with the symmetric key, she can later
repudiate the signature, claiming that Bob forged her signature. Although
Bob knows that he did not “sign” for Alice, he cannot prove it.
In this chapter, we examine several public key systems, including the
Merkle-Hellman knapsack cipher, the Diffie-Hellnian and Arithmetica key
exchange protocols, the RSA, Rabin and NTRU public key cryptosystems,
rind the ElGamal signature scheme. All of these systems have played (and in
some instances, continue to play) an important role in the fascinating field of
public key cryptography.
Our primary goal in this chapter is to int,roduce the variety of public key
syskrns and to emphasize some of the relatively subtle mathematical issues
that arise in public key Cryptography. In keeping with the theme of the book,
we present these math issues as “attacks,” although many of the attacks

discussed in this chapter would never be a serious threat in practice. However,
the attacks on the Merkle-Hellman knapsack discussed in the next section,
and some of the attacks on NTRU mentioned in Section 6.7 are exceptions,
since these raise serious cryptanalytic issues. However, the coverage of these
attacks is less detailed than those presented in previous chapters. Chapter 7
is more in tune with the previous chapters of the book, since it contains a
more in-depth treatment of a few cryptanalytic attacks on public key systems.

Merkle-Hellman Knapsack

Every private in the French army carries a. Field Marshal wand in his knapsack.
- Napoleon Bonaparte

The Merkle-Hellman knapsack cryptosystem [loo] was one of the first pro-
posed public key cryptosystems. This cipher utilizes a few elementary, but
nonetheless clever mathematical ideas. Because of its historical significance
and since it is easy to understand, we examine it first. The cipher is based
on a mathematical problem which is known to be NP-complete [55].
The subset sun1 or knapsack problem can be stated as follows: Given a
set of r weights
= (wo, W l , . . . , WT-1)

and a sum X, find zo, 2 1 , . . . , ˜ each z E (0, l}, so that
˜ - where

+ . . . +X r - l W T - l ,

provided that this is possible. Note that the z simply select a subset of the
For example, suppose that the weights are W = (4,3,9,1,12,17,19,23)
and the given sum is X = 35. Then, a solution to the subset problem exists
and is given by z = (01011010), since

+ 1 . 3 + 0 . 9 + 1 . 1 + 1 . 1 2 + 0 . 1 7 + 1 . 1 9 + 0 . 2 3 = 35.

For this set of weights, if X = 6, the problem does not have a solution.
While the general knapsack problem is NP-complete, a special type of
knapsack known as a superincreasing knapsack can be solved efficiently. A
superincreasing knapsack is a set W that, when ordered from least to greatest,
has the property that each weight is greater than the sum of all the previous
weights. For example,

W = (2; 3,6; 13,29,55,112,220) (6.1)
is a superincreasing knapsack.

It is straightforward to solve a superincreasing knapsack problem. For
example, suppose that we arc given the set of weights in (6.1) and the
sum X = 76. Since X is less than 112, we must have 2 7 = 2 6 = 0. Then,
+++ +
since X > 55 and we have 2 3 6 13 29 < 55, it must be the case
that 2 5 = 1. That is, if we do not select the weight 55, then we cannot
possibly reach the desired sum, since the sum of all remaining weights is less
than 55, due to the superincreasing property.
Now, let X I = X - 5 5 = 21. Since 13 < XI < 29, we must have that 2 4 =
= 1. Continuing in this manner, we find z = (10110100) which is
0 and
++ +
casily verified to be correct since 76 = 2 6 13 55. This process yields
an efficient (linear time) algorithm to solve any superincreasing knapsack
Merkle and Hellman™s [lo01 idea was to disguise a superincreasing knap-
sack S through the use of a mathematical transformation to make it look
like an arbitrary knapsack T . The disguised knapsack T is made public by
Alice and T acts as Alice™s public key. When Alice receives a ciphertext, she
applies the inverse of the transformation to convert the problem back to the
superincreasing case. Alice decrypts by solving the resulting superincreas-
ing knapsack problem. Without knowledge of the transformation, it would
appear that a cryptanalyst must solve a general knapsack, which is a hard
prohlein. However, there is a shortcut attack, which we describe below. But
first we discuss the the knapsack cryptosystem in more detail.
To creatc her public and private keys, Alice first chooses a superincreasing
knapsack S = (so, s1,. . s,˜). To convert S into T , she also chooses a
coriversion factor m and a modulus n, where gcd(m,n) = 1 and n is greater
than the sum of all elements of 5™. The transformed knapsack is computed as

T = (sonz (mod n ) ,s1m (mod n ) .. . . , s , - l m (mod n ) )

arid T is made public. Alice™s private key consists of S and m-l (mod n ) .
Suppose Bob wants to send a message of T bits to Alice. Bob first converts
his plaintext into a binary block B . He then uses the 1 bits of B to select thc
elerrient,˜ T , which are then summed to give the ciphertext block C. Alice
recovers the plaintext B , by using the private key to compute Cm-™ (mod n ) ,
arid solves using her superincreasing knapsack. To encrypt longer messages,
inult,iple blocks are encrypted.
To make things more concrete, consider the following example. Suppose
that Alice chooses the superincreasing knapsack

S = (2.3.7,14, 30,57.120,251),

41 and moduli˜sn = 491. To transform S into a general
aloiig with ni =

knapsack T , Alice performs the following computations

2m = 2 . 4 1 = 82 (mod 491)
3m = 3 . 4 1 = 123 (mod 491)
7m = 7 . 4 1 = 287 (mod 491)
14m = 14.41 = 83 (mod 491)
30m = 30.41 = 248 (mod 491)
57m = 57.41 = 373 (mod 491)
120m = 120.41 = 10 (mod 491)
251m = 251 . 4 1 = 471 (mod 491).

Then Alice's public key is

T = (82,123,287,83,248,373,10,471).

Alice's private key consists of

S (2,3,7,14,30,57,120,251)

m-' (mod n ) = 41-l (mod 491) = 12.
Now; suppose that Bob wants t o encrypt the message M = 150 for Alice.
He first converts 150 t o binary, that is 10010110. He then uses the 1 bits
t o select the elements of T that are summed t o give the ciphertext. In this
example, Bob computes the ciphertext

+ 83 + 373 + 10 = 548
C = 82

and sends C t o Alice. To decrypt this ciphertext, Alice uses her private key
to compute

Cm-l (mod n ) = 548.12 (mod 491) = 193.

She then solves the superincreasing knapsack S for 193 and she recovers the
message in binary 10010110 or, in decimal, 111 = 150.
That this decryption process works can be verified by using elementary
properties of modular arithmetic. In the particular example considered above,
we have
+ 83m-' + 37m-I + 10m-1
548m-' = 82m-'
= 2mm-' + 14mm-' + 57mm-' + 120mm-'
= 2 + 14 + 57 + 120
193 (mod 491).

In general: due to the linearity of the process used to convert from the sii-
perincrcasing knapsack S into the public key knapsack T , knowledge of rri,-l
makes it easy to convert the ciphertext to the superincreasing case. With-
out Alice™s private key, (S,m-™ (mod n,)),t,he attacker Trudy needs to find
a subset, of T which sums to the ciphertext™ value C . This appears to be a
general knapsack problem, which is intractable.
By converting the superincreasing knapsack into the general knapsack
through the use of modular arithmetic, it trapdoor is introduced into the
knapsack. Without rn, it is not clcar how to find the conversion factor nb- .
The one-way feature results from the fact that it is easy to encrypt with
the general knapsack, but it is (hopefully) difficult to decrypt without the
private key. But with the private key, the problem can bc converted into a
superincreasing knapsack, which is easy to solve and thus enables the intended
recipient t,o easily decrypt.
However, this cryptosystem was shown to be insecure by Shamir [132] in
1983. It turns out that the ”general knapsack” (the public-key) which arisos
in the Merkle-Hellman cryptosysteni is not general enough. Instead, it is a .
highly structured case of the knapsack and Shamir™s lattice reduction attack
is able to take advantage of this fact. Shamir™s ingenious method of attack is
dicussed in the next section.

Lattice-Reduct ion Attack
Lattice reduction is it powerfiil technique which can be used to solve many
different t,ypes of combinatoria.1 problems. We first describe the lattice re-
duction method, as discussed in [142], and then illustrate how it can be used
to attack thc hlerkle˜-Hellman knapsack cryptosysteni. Some elementary lin-
ear dgebra is used in this section; scc the Appendix for an overview of the
necessary linear algebra.
Consider: for example, the vectors

Since cg arid c1 are linearly independent, any point in the plane can be
uniquely represented by N O C O Q I C I , where 00 and are real numbers.
If we restrict the coefficients to integers, that is, we require tha,t a and a1
are integers, then we obtain a lattice consisting of discrete points in thc plane.
Figure 6.1 illustrates the lattice spanned by co and c1. In general, a lattice C
is thc set of all linear combinations of a set of column vectors ci with integer
Given an m x n matrix A and an r n x 1 matrix B , suppose we want to
find a solut,ion U t o t,he matrix equation AU = B , with the restriction that U
consist,s cntirely of 0s and 1s. I f U is a solution to AU = B >then the block
N 271


Figure 6.1: A lattice in the plane.

matrix equation

holds true, since M V = W is equivalent to U = U and AU - B = 0. Con-
sequently, finding a solution V to the block matrix equation M V = W is
equivalent to finding a solution U to the original matrix equation AU = B .
Note that the columns of M are linearly independent, since the n x n identity
matrix appears in the upper left and the final column begins with n zeros.
Let CO, c1, c2,. . . , c , be the n 1 columns of the matrix M in (6.2) and
let v g , v1, v 2 , . . . , vn be the elements of V. Then

w = uoco + V l C l + . . . + ?Jncn. (6.3)
W ,where
We have M V =


and we want to determine U . Instead of solving linear equations to obtain
V ,we will find U by determining W . Note that because of (6.3), W is in the
lattice C.spanned by thc columns of M .
The Euclidean length of a vector Y = [yo, y ˜. , . ,ylL+nL- is

However, the length of a vector W in (6.4) is

which is much “shorter” than a typical vector in C. Furthermore, W has a
very special form, since its first nl entries consist of 0s and 1s with its last m
cntries I-xing all 0. Is it possible to take advantage of this special structure
t o find W ?
In 1982, Lenstra, Lenstra and Lov&sz [91] discovered the so-called LLL
Algorithm, which provides an efficient method t o find short vectors in a lat-
tice. In Table 6.1, we give a n outline of their algorithm in pseudo-code,
where G S ( M ) refers t o the Grarn--Schmidt process, which returns an or-
thonormal basis for the subspace spanned by the columns of M . The Gram-
Schmidt process appears in Table 6.2. Note that a small number of lines of
pseudo-code suffices t o specify the entire LLL Algorithm.
With clever insight, Shaniir [I321 realized that lattice reduction could
be used t o attack the Merkle-Hellman knapsack cryptosystern. Suppose that
Bob™s public knapsack is given by T = (to,t l , . . . , t r - l ) , and Alice sends Bob a
ciphertext block C, encrypted with Bob™s public knapsack. Since the attacker,
Trudy, knows the public knapsack T and C, she can break the system if she
is able t o solve the matrix equation TU = C , where U is a n T x 1 column
matrix consisting of 0s and 1s.
Trudy can rewrite the matrix equation T U = C in block matrix form as

arid apply the LLL Algorithm t o the matrix A f . The resulting short vectors
which are obtained can be checked t o see if they have the special form required
of W ,which is a column vector where the first T entries are all 0 or 1 and last
entry is 0. The LLL Algorithm will not always produce the desired vector
and therefore, the attack is not always successful. However, in practirp, the
lattice reduction attack is highly effectivc against the original Merkle-Hellman
To illustrate the lattice reduction attack, suppose Alice constructs her
knapsack key pair from the superincreasing knapsack

S = (SO, ˜ (2,3.7,14,30,57,120,251),
1 . .. , ˜ 7 =

Table 6.1: LLL Algorithm

// find short vectors in the lattice spanned
// by the columns of M = (bo, b l , . . . ,b,)
( X , Y ) GS(M)
f o r j = 1 to n
f o r i = j - 1 to 0
> 1/2
i f Iyijl then
+ 1/2]bi
bJ = bj Lyij

end i f
next i
next j
( X , Y ) GS(M)
for j = 0 to n - 1
+ yj,j+lzj(I2 < $ ( l ˜ jt h e n
if (Izj+l ((˜
SW"P(bj, b+l)
goto abc
end i f
next j
r e t u r n (M )
abc: continue

with m = 41 and modulus n = 491. Then, m-l = 12 (mod 491). The corre-
sponding general knapsack T is obtained by computing ti = 41si (mod 491),
for i = 0 , 1 , 2 , . . . , 7 , which was found above t o be

T = (to,tl,.. . , t 7 ) = (82,123,287,83,248,373,10,471).

Alice's knapsack key pair is defined by

Public key: T

Private key: S and rr-™ (mod n ) .
Suppose Bob wants t o encrypt the message M = 10010110 for Alice.
Then, as discussed above, Bob computes

and sends ciphertext C = 548 to Alice.

Table 6.2: Gram-Schmidt, Process

//Gram--Schmidt M = (bo, b l , . . . , b,)
20 = bo
for j = I t o n
2; = b .
for i =0 t o j - 1
yl/ij = ( x i . bj)/\lx:l/il12
n:j = Ic. ,] - yzjzi
next i
next j
return(X,Y )
end GS

Now, suppose that Trudy wants to recover the plaintext that corresponds
to ciphertext C = 548. Since Trudy knows the public key T and cipher-
text C = 548, she needs to firid a set of u l , for i = 0 , 1 , . . . , 7 , with the
rcstrictiori that each u,E (0, l}, and

This can be written as the matrix equation

T .U 548.

where T is Alicc's public knapsack and U = ( 2 1 0 , u 1 , . . . , u 7 ) , arid the a, are
unknown. but earh must be cither 0 or 1. This is of the form AU = B (as
discussed above), so Trudy rewrites the matrix equation as AJV = W and
applies the LLL Algorithm to 1 . . this case, Trudy firids
2 1In

0 0 00 0
-1 0 0 0
0 1 0 0 0 0 0 0
00 1 0 0 0 0 0 0
00 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
00 0 00 0 0 1
10 471 -548
- 8 2 123 287 83 248 373

The LLL Algorithm outputs a matrix h ™ consisting of short vectors in the

0 1 0 1 0 0
--1-1 1
0-1 1 0 0 0 0
0 0 0
1-1 0-1 1 2
0 -1
1 -1 -1 0 -1 0
M™= 0 0 10-2-1 0 1 0
0 0 0 11-1
1 1 1
0 1 0
0 0 0-1 0-1
0 0 0 0 0 11-1
-1-1 1-1
1 0 2 0

The entries in the fourth column of M™ have the correct form to be a solution
to this knapsack problem. Therefore, Trudy obtains the putative solution

u = (1,0,0,1,0,1,1,0)
Using the public key and ciphertext C = 548, she can easily verify that U is
indeed the original plaintext sent by Bob.

Knapsack Conclusion
Much research has been done on the knapsack problem since the Merkle-
Hellman cryptosystem was broken. Several different knapsack variants have
been created and some of these appear to yield secure cryptosystems. How-
ever, people have been reluctant to use these systems, since “knapsack” con-
tinues to be equated with “broken,” even to this day. For more information
on knapsack cryptosystems, see [37, 89, 1091.

Diffie-Hellman Key Exchange

[If] you look right under the center of a streetlight,
you don™t find anything that wasn™t known before.
I f you look out into the darkness, you don™t discover anything,
cause you can™t see anything.
So you™re always working at the edge o f the streetlight,
trying to find your keys.
- Whitfield Diffie

In symmetric key cryptography, both parties use a common key to encrypt
and decrypt messages. However, when using such a system, there is a critical
issue that needs to be dealt with, that is, how can Alice and Bob agree upon
a key? Can this be accomplished in a secure manner over a public channel?

These and related questions were on the minds of Diffie, Hellman and Merkle
during the 1970s. At the time, there was no solution in sight for this vexing
kxy distribution problem.
In 1976, Diffie arid Hellman published their seminal paper [38] which made
the case that public key cryptography should be possible and proposed the
Diffie˜-Hellman key exchange protocol as a solution to the key distribution
problem; see also [l20]. Ironically, the first to discover DiffieeHellman was
actually Malcolm Williamson of GCHQ (roughly, the British equivalent of
NSA) [93]. However, this does nothing to diminish the accomplishment of
Diffie and Hellman, since Williamson's work was classified.
The Diffie-Hellman key exchange, as illustrated in Figure 6.2; opemtes in
the following way. Let p be a large prime and g an integer, where 2 5 g 5 p-2.
Both the prime p and generator g are publicly known. Alice chooses a random
niiniher a , where 1 5 a 5 p - 2 and calculates a = ga (mod p ) . She
then serids Q to Bob. The number a is private, that is, a is known only
to Alice. Bob also chooses a random number b, where 1 5 b 5 p - 2 and
calculates fi = 9' (mod p ) and sends /3 to Alice. The number b is private,
known only to Bob. Alice t,lien calculates

(mod p ) = gab (mod p )
0" (mod p) =

arid Bob computes

a' (mod p ) = (g")b (mod p ) = g a b (mod p ) .

Alice and Bob now share gab (mod p ) , which can be used as a symmetric key.

Figure 6.2: Difie Hellman key exchange.

Trudy sees ga (mod p ) and g6 (mod p ) and she breaks the key exchange
protocol if she can find gab (mod p ) . To do 50, it appears that she must find a
from ga (mod p ) or b from gb (mod p ) . Therefore, the strength of the Diffie-
Hcllinan key exchange protocol is believed to depend on the computational

complexity of solving the discrete logarithm problem. That is, there is no
efficient solution to the problem of finding y given ICY (mod p ) , the base z
and the modulus p .
Suppose, for example, we want to solve the equation 2" = 9 (mod 11).
Since the numbers are so small, this is easy to solve by exhaustively searching
through all of the possible exponents. We see that

2'= 1 (mod 11)
2l 2 (mod 11)

22 = 4 (mod 11)
23 = 8 (mod 11)
24 = 16 = 5 (mod 11)
25 = 5 . 2 10 (mod 11)

1 0 . 2 = 9 (mod 11)

and, therefore, II: = 6 is the desired solution. However, for large p , an ex-
haustive search is not feasible. Although there are some efficient methods
for solving certain classes of discrete logarithm problems, there is no known
efficient algorithm for solving g z = t (mod p ) for z in general, where g, t
and p are given. Some of the current discrete log algorithms are analyzed in
Section 7.3.

Man-in-the-Middle At tack
The Diffie-Hellrnan key exchange is subject to a man-in-the-middle attack
if there is no procedure to authenticate the participants during the key ex-
change. Suppose that Trudy wants to read messages that are being sent
between Alice and Bob, where Alice and Bob use the Diffie-Hellman key ex-
change. First, Trudy chooses an exponent t. She then intercepts ga (mod p )
and gb (mod p ) and sends g t (mod p ) to Alice and Bob. At this point, Alice
believes gt (mod p ) came from Bob, and Bob believes gt (mod p ) came from
Alice. Now Trudy computes K A = ( g a ) t (mod p ) and K B = (gb)t (mod p ) .
Alice, not realizing that Trudy is in the middle, follows the Diffie-Hellman
protocol and computes K A . Similarly, Bob computes K g . Then when Alice
sends a message to Bob (encrypted with K A ) , Trudy can intercept it, decrypt
it and re-encrypt it (or encrypt a different message) with K B before sending
it on to Bob. In this manner, Trudy can read (and alter, if she so desires) all
messages between Alice and Bob, and neither Alice nor Bob will suspect that
there is any problem. Figure 6.3 illustrates this man-in-the-middle attack.
The man-in-the-middle attack on the Diffic-Hellman key exchange can be
prevented provided the parties are properly authenticated. For example, an
authentication protocol that uses digital signatures would assure Alice and

Figure 6.3: Man-in-the-middle attack on Diffie-Hellniari

Bob that the received messages originated from the correct person. Since
Trudy cannot forge Alice™s or Bob™s signatures, her man-in-the-middle attack
would be thwarted. In addition, such a protocol will prevent a replay attack.
There are several ways to prevent the man-in-the-middle attack on Diffie-
Hellrnan. For example, the Station-to-Statzon protocol, devised by Diffie,
van Oorschot and Wiener [39], could be used for authentication purposes.
Problem 3 gives a simple example illustrating a technique that prevents the
man-in-t he-middle attack.

Diffie-Hellman Conclusion

Diffic-Hellman provides an elegant solution to one of the most challenging
problems in all of cryptography-the so-called key estaOlishmen,t problem (or
key distribution problem), thiLt is, how to securely agree on a shared sym-
metric key. Prior to the development of public key cryptography, the most,
common method of key establishment was via a human courier. Obviously,
this was not a desirable situation.
Care must be taken when using Diffic-Hellman, since the man-in-thc-
middle attack is a serious threat. But the man-in-the-middle attack can be
prcvmted in many important applications. Consequently, the Diffie-Hellman
key exchange is one of the most useful-and widely used-public key cryp-
Diffie-Hellrnan is used, for example, in the IPSec protocol to provide
perfect forward secrecy (PFS); see Problem 4. To achieve PFS, an ephemeral
Dzfic-Hellman key exchange is used. In some situations, Diffie-Hellman can
be used to make a weak PIN-based or password-based authentication protocol
relatively secure; see [ll]and Problem 5 for more details.

Arithmetica Key Exchange

To divide a cube into two other cubes,
a fourth power o r in general any power whatever into two powers
of the same denomination above the second is impossiblc,
and I have assuredly found an admirable proof of this,
but the margin is too narrow to contain if;.
- in the margin of Pierre de Fermat's

copy of Diophantus' Arithmetica

Arithmetica is a relatively new key exchange mechanism which was invented
in 1999 by Anshel, Anshel and Goldfeld [5]. Although it serves the same
purpose as the Diffie-Hellman key exchange, Arithnietica uses an entirely
different approach than Diffie-Bellman. The Arithmetica key exchange relies
on some of the most sophisticated mathematics that we discuss in this book.
However, the reader should not feel intimidated since the basic ideas underly-
ing the system are relatively easy to understand. We assume that the reader
is familiar with the basic notion of a group. Section A-2 in the Appendix
provides enough group theory background to understand all of the material
in this section.
The material in this section is a little more abstract than most of the
other sections in this book, so we begin with some examples. Along the way,
relevant definitions and concepts will be introduced. For our first example,
consider the set G consisting of all finite words using the alphabet

Typical elements of G include

The letter 1˜can be thought of as the e m p t y word in G. Here, it is important
t o note that the order in which letters appear in a word matters so that, for
example, ub and b are two different words in G. When working with elements
of G, we use exponent notation and its properties. Consequently, the elements
in (6.6) can be rewritten as

aba-lb-™, a, b-™,
b3a,b4, nbP1a2b,
aba2bK2, l˜,

respectively. A binary operation V' , which is the concatenation operator,
can be defined on G. For example,

The set, G of all finite words using the alphabet in (6.5), along with the
concatenation operator "*", is a group (see Section A-2 in the Appendix). In
fact, this group is known as the free group o n two genw-ators and it is denoted
G = (u,b).
The elenicrits u and b are the generators of G, since all nori-empty words in G
are formed using a and b (along with u-' and b - l ) . The term "free" refers t o
the fact that there are no relations between a , b, a-', and b-'. For example,
ab cannot be written as, say, bn.
We can impose relations on G = ( a ,h). For example, consider the set G as
in (6.7) with the concatenation operator "*" (as in our first example), along
with the relations

Then the identity element 1˜ can be expressed in an infinite number of ways,

1 ˜ = a 2 , 1˜ = b2, 1˜ = ababF™a-lb-l, and 1˜ = a3bbabnP1b,

arid concatenation between words in G can be rewritten, as dictated by thc
relations. For example,
* ab = a b l c b = ah 2 l = a.
abn-' =a ˜

Our set G. along with concatenation operator '.*" and these relations, is also
a group. Let us denote this group as

This notation gives a finite presentation of the group 5'3, which is a well-
known symmetric group. It is important to note that a group G rnay have
many different finite presentations. For example, Problem 6 asks the reader
to show that
s:j= ( x , y I Z''I , y2, (n:y) 2 ).
Sometimes, thc relations in a finite presentation can be used t o rewrite
cvery possible word into a canonical form. For example, using the finite prc-
smtatiori S;( = (z,y I 2': y 2 , ( z ˜ ) ˜ ) ,see that the clernent zyzy = Is:, can
be rcwrittcm as z-'(xy;my) = :cP1 . lLy:,, which simplifics to yzy = zP1(:c3),
whicli, in turn, simplifies to yxg = x2 and, finally, y x = :c2y. Using the fact
that yx = x2y, along with the fact that z 3 = y2 = 1sZJ, can write cvery
word in 5™3 in the form zi:yj, where i E (0, 1 , 2 } arid j E (0, l}. Consequently,
tlic group ˜ : cim he viewed as t,Iie set, of elements { l s , , ˜ , 2 2 , y , z y . x ' y } ,

together with the binary operation of concatenation, and subject t o the rela-
tions z3= y2 = zyzy = lss.
We are now ready t o give a description of Arithmetica. Suppose that Alice
and Bob want to establish a symmetric key. A finitely presented, infinite non-
abelian group G is made public. Alice and Bob create their public keys to be
subgroups of G, say,

s1,. . , s - )
. ,l Sg = ( t o , t l , . . . t m - l ) ,
S A= (so, and
respectively, and these are made public knowledge. The subgroups S A and
Sg can be thought of as being the sets of all formal words in the alphabets
si and t j respectively, with the binary operation of concatenation, subject t o
the relations of G . Alice and Bob select their private keys

si(n-liE S A and
a = s ˜ .˜ . b = t r ( 0 ) . . . tjmpl
40) an-1

Then Alice computes the set of elements {a-ltoa, . . . , a-lt,-la) and
sends the result t o Bob. Bob computes the set {b-lslb, . . . , b-'s,-lb} and
sends it t o Alice. Before transmission, each of these sets are rewritten (using
the specified relations) so as to obscure the private keys a and b. With the
information received from Bob, Alice is able t o compute b-lab since
b-lab ...
= b-lSi0
b Zn-1
u(0) So(,-1)
= b-1s2(o)bb-1s2(l)b.. . b- 1s 2 ˜ ( ˜ - ˜ )
. . . (b-l˜o(n-l)b)znpl.

Similarly, Bob can compute a-'ba. Using their respective private keys, Alice
and Bob each compute a-lb-lab, which can serve as a shared symmetric key.
Although this seems very complicated, in fact it really is not, as a sim-
plified example will illustrate. Suppose Alice and Bob decide t o establish a
common key, using the Arithmetica key exchange. They first select a group,
G = (z, Y I z4,Y2,P Y z )
and make it public. Alice chooses her public key to be

= {IG, 5'9
Y) z2Y}
S A = (SO, =

and Bob chooses his public key t o be
SB = ( t o ) = (z) = { l G , z , Z , x 3 } ,
which are also made public. Now, Alice generates her private key
a = (z2 ) 2 . ( y ) - l = .4y-1 I G .y-1 = y-1

and Bob generates his private key

b = (x)" = x:3.

Next, Alice computes a-ltoa = y-lzy and rewrites it as yzy. She then sends
{ y z y } to Bob. In a. similar manner, Bob coniputes (and rewrites)

x 3= x . ˜
=q ˜ = 'xP2y = x 2y.
b P 1 s l b = x-'yx3 y

He then sends { x P 2 ,z 2 y } to Alice.
To establish a common key, Alice computes

b-lab (x?)*(x*y)-I = ( 2 ) 2 ( y p x - * )
= x 4 y -1 x -2 - 1c; y-1.c-2 = yx2 = x 2y

Finally, she computes a-l(b-'ab) yx2y = x2. Similarly,
= =
Bob computes

a,-1 ba (yxy)" = yxy yxg . yxy
= '

yxy2 x?J2 xy = 2/X 1 G x . 1 G . xy
' '

= yJ' y = 2:.

Bob then computes the value a-™b-™a = ( a - 'ba)-' = x-™, which he uses to
obtain the shared secret (a-'b-'a)b = xP1. 2 = x2. Alice and Bob can then
compute a shared symmetric key based on this shared secret.
In our example, a small finite non-abelian group was used to illustrate the
ideas underlying Arithmetica. In a real-world implementation of Arithinetica,
G, SA, and Sg are chosen to be infinite non-abelian groups, each having a
large number of generators.
Before outlining an attack on Arithmetica, we mention some important
observations concerning the algorithm. First, thc security of Arithmetica
is based on t,he computational complexity of the conjugacy problem. For a
finitely represented group G, there is no known efficient algorithm to solve
t,he following problcm: Given two words z and y in G, does there exist a word
g t G so that y = y-lxg? If the attacker Trudy is able to efficiently solve the
cori.jugacy problem, she would be able to recover the private keys a and b by
solving the associated systems of conjiigacy equations (from S A and SB).
Also in the Arithmetica key exchange, it is very likely that the established
key will be written in different ways for Alice and Bob. Therefore, it is nec-
essary to extract an identical element from the common key a-lb-lah. One
way to do t,his is if every element in G can be put into a unique canonical

form. If this is the case, then Alice and Bob simply convert their shared
key into canonical form. In [15], Birman, KO, and Lee showed that for the
braid groups, there is a polynomial-time algorithm for converting the group
elements into a canonical form. Furthermore, the conjugacy problem is seem-
ingly intractable for this class of groups. Consequently, a braid group is often
used in the implementation of Arithmetica.

Hughes-Tannenbaum Length Attack
It is somewhat ironic that the necessity of being able to convert the group
elements into a canonical form in Arithmetica also opens the door to an attack
on the system. Introduced by Hughes and Tannenbaum [69],the basic idea of
the attack on Arithmetica (and other similar systems) is that group elements
with long lengths--which is well-defined since every element has a canonical
form-have a higher probability of not combining with other factors. This
allows an attacker to recover information about the shared secret. Here, we
give a very brief description of the length attack on Arithmetica.
For any element w E G, define the length of 20 to be

. , . giN--l
ko ki
w = siogz,

is in canonical form. Then for any two words x,y E G, we see that the lengths
satisfy l ( x y ) 5 l ( x )+ !(y). If some of the parts of x and y cancel, then it
may be that the length of xy is much shorter than the sum of the lengths of
x and y.
As above, let
0, E S A = (5'0, s1,. . . , sn-1)

be Alice's private key. For purposes of this discussion, we assume that the
factors s have lengths which are large, relative to the length of a . From Bob's
public key,
SB = ( t o , t l , . . . , t m - l ) ,
Alice computes u, = u-lt,u, for r = 0 , 1 , . . . , m - 1, and transmits these to
Bob. The attacker Trudy performs the length attack by repeatedly computing

If she finds that
< l(ur),
Trudy infers that s is a factor of a on the left--not with certainty, but with
some positive probability. Once a factor is recovered, the attack is similarly

applied again to recover another factor of a arid this process is repeated
to recover all of a , with some positive probability. The length attack is
effective when the . t ( s L )
are large. Experimental evidence [5] suggests that if
the generators so,s1,. . , s T L - l arc each of length less than ten (for the Artin
generators of the braid group G) then the length attack is thwarted. This
attack is very new and is the subject of ongoing research.

Arithmetica Conclusion
In comparison to many of the cryptosystems discussed in this book, Arith-
rnetica uses some very sophisticated matheniatics. However, it is not particu-
larly unusual in the world of public key cryptography, where advanced math-
ematics plays a significant role in the design and analysis of cryptosystems.
For example, ongoing research in elliptic curve cryptography, group-based
cryptosystems and lattice-based encryption schemes illustrate this point. The
interested reader is directed to [17, 84, 1021, respectively, for more information
or1 these mathematically sophisticated types of cryptosystems. Undoubtedly,
advanced mathematics will play a central role in the design and analysis of
future public key cryptosystems.


Using RSA in the manner I used for this example
woiild rcwult in a system that would be no harder to break
than those fanious qiiotation puzzles in the Sunday paper.
- Ben Goren [60]

In 1973, Clifford Cocks, a cryptologist in the British government agency
GCHQ, wrote a n internal document describing a practical public kcy cryp-
tosystcm [93]. This was a significant, accomplishment as Cocks had found
an appropriatc mathematical one-way function for such a cryptosystern. Its
sccurity was based on the idea that factoring an integer into its prime divi-
sors is a computationally difficult task. In 1978, Rivest, Shamir, and Adel-
man [123] published thcir ground-breaking paper, stunning the cryptographic
comnuinit,y at large. Essentially, tlieir paper rediscovered Cocks™ cryptosys-
t,cni: which had been classified five years earlier by the British government.
Of course, this docs nothing to diminish Rivest , Shamir, and Adelman™s tlis-
covcry, sirice it was accomplished independently of Cock™s work.
In the RSA cryptosystcm, Alice™s public--private key pair is generated as
follows: First, generate two large distinct primes, p arid q , and let N = pq.
Then. choose e so that gcd(e,d(N)) = 1 and let d = e-™ (mod q5(N)),
6.5 RSA 285

where 4 ( N ) denotes the Euler phi function (this function is defined in Sec-
tion A-2 of the Appendix). Alice's public key is ( e , N ) and her private key
is d. Below, we make use of the fact that 4 ( N ) = ( p - l ) ( q - 1).
To send a message, an agreed-upon protocol for converting text into a
sequence of positive integers (each less than N ) must first be established.
The public key ( e , N ) is made public and used to send messages to Alice.
Only Alice knows her private decryption key d. Encryption of a message M
is accomplished by C = M e (mod N ) and decryption of the ciphertext C is
M = Cd (mod N ) .
Why does this work? To verify that RSA works, we must show that for
any integer M , where 1 5 M < N , we have ( M e ) d(mod N ) = M . First,
if gcd(M, N ) = 1, then

( M e ) d M e d = M 1 + k 4 ( N= M ( M 4 ( N ) ) k
(mod N ) .

By Euler's Theorem, which appears in Section A-2 of the Appendix, we
= 1 (mod N ) so that

M ( M 4 ( N ) )= M . lk (mod N ) = M (mod N ) ,

as desired. On the other hand, if gcd(M, N ) = p , then

( M y = M1+""()
- Ml+(P-l)(q--l)k

= M(M4-l)"P-l)

M(l)k(ppl) M (mod q ) ,

again: by Euler's Theorem. Also note that in this case, M = 0 (mod p ) ,
which implies ( M e ) d 0 (mod p ) . It follows that ( M e ) d M (mod N ) ; see
Problem 14.
In the next section, we consider some mathematical and implernentation
issues related to RSA. Then in Chapter 7 we discuss implementation-related
attacks on RSA.

Mathematical Issues
There is large body of literature focusing on the cryptanalysis of RSA. An
excellent source of information is Boneh's survey [19]. In this section, we
mention a few mathematical issues related to the security of RSA. Our in-
tent is to illustrate some of the issues that can lead to attacks on flawed
implementations of RSA.
First, we mention a generic attack that applies to public key systems (and
hash functions in some situations) but not to symmetric ciphers. We state the

attack in the context of RSA, but it applies to other public key cryptosystems
as well.
Suppose that Alice encrypts the secret message
M “Attack at dawn”

using Bob™s public key ( e , N ) ,that is, she computes C = M e (niod N ) , and
she sends C to Bob. Suppose Trudy intercepts C. Since Bob™s public key is
public, Trudy can try to guess messages M™ and for each guess compute the
putative ciphertext C™ = (M™)˜ (mod N ) . If Trudy ever finds a message M™
for which C™ = C, then Trudy knows that M™ = M and she has broken the
RSA encryption.
This method of attacking public key encryption is known as a forward
search. It does not apply to symmetric ciphers, since Alice and Bob™s shared
symmetric key would not be available to Trudy, so she could not try to en-
crypt likely messages. Obviously, for both synirnetric key and public key
cryptography, the size of the key space must he large enough to prevent a
brute-force exhaustive search. However, the forward search attack shows that
for public key encryption, the size of the plaintext space must be sufficiently
large that an attacker cannot simply try to encrypt all likely messages. In
practice, it is easy to prevent the forward search attack by padding messages
with a sufficient number of raridorn bits, thereby increasing the size of the
plaint,ext space.
RSA is also susceptible to a chosen ciphertext attack in the following
sense. Suppose that Alice will decrypt an innocent-looking ciphertext of
Trudy˜s choosing and return the result to Trudy. Then Trudy can recover the
plaintext for any ciphertext that was encrypted with Alice™s public key; see
Problem 1 3 .
An interesting mathematical fact regarding RSA is that the factors p arid q


. 11
( 16)