ńňđ. 11 
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 32bit words A , B and C are
rcplaced with 8bit 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
following.
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
satisfied?
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
,
Xi
Xo = 0˜1089fc26,
= 0˜9074449b,
X2 X3
= Ox8bf37fa2, = Oxld630daf,
X s = 0x4e4f430a1
X, = Ox63247e24,
= 0x43415254, X7 = Ox410aOa54,
X,
= 0x68742074, Xg = 0x72702065,
Xs
= 0x20656369, Xi1 = 0 ˜ 2 4 2 0 6 6 6 f ,
Xi0
Xi2 = 0 ˜ 2 ˜ 3 6 3 7 3 1 , i 3 = 0x20353934,
X
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
(0x54,0x52,0x41,0x43)
which represents the ASCII text â€śTRACâ€ť.
20. Let
F ( A , B , C )= (AAB ) V (â€™A A C )
and
$ ( A ,B , C ) = (A A B ) C).
(A
â€™ A
Suppose that A, B and C are 32bit 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 32bit 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
j
positions where ej = 0, and a â€ś.â€ť in all other positions. Show
that S = V X .
HASH FUNCTIONS
262
c. Verify that (5.56) holds for every line in Tables A2, A3, A4,
and A5, that is, show that
L (mod 2 â€ť ) ,
U
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 1byte 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 singlestep mod
ificat ions techiiique.
5.6 PROBLEMS 263
a. Let X and Y be 32bit 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 = 231i. Let
A = (2 ziOEi,, zilE,il  . ..  z i k E i k )(mod 2 3 2 ) (5.57)

and
+ 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 1byte 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 1024bit 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
87
2f ca b5 12 b8 fb 7f
83 e4 88 83
06
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
73
35 9a c7 fO eb fd Oc 30 29 fl 66 dl bl 8f
09
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
and
dl 31 dd 02 c5 e6 ee c4 3d 9a 06 98 af f9 5c
69
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
09
37
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
79
75 27 7f 79 30 d5 5c eb 22 ad ba 4c 15 5c
e8
74
ed cb dd 5f c5 d3 6d bl 9b Oa 58 35 cc a7 e3
HASH FUNCTIONS
264
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
6
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 selfevident, 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]
Introduction
6.1
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 oneway 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 oneway functions used in public key
cryptography include factoring (RSA), discrete logarithms (DiffieHellman),
265
PUBLIC KE Y SYSTEILIS
266
and finding the nearest codeword in a linear binary code (McEliece). Finding
a trap door oneway 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 nonrepudiation
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
MerkleHellman knapsack cipher, the DiffieHellnian 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
6.2 MERKLEHELLMAN KNAPSACK 267
discussed in this chapter would never be a serious threat in practice. However,
the attacks on the MerkleHellman 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 indepth treatment of a few cryptanalytic attacks on public key systems.
MerkleHellman Knapsack
6.2
Every private in the French army carries a. Field Marshal wand in his knapsack.
 Napoleon Bonaparte
The MerkleHellman 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 NPcomplete [55].
The subset sun1 or knapsack problem can be stated as follows: Given a
set of r weights
w
= (wo, W l , . . . , WT1)
and a sum X, find zo, 2 1 , . . . , ˜ each z E (0, l}, so that
i
˜  where
1,
+ . . . +X r  l W T  l ,
x=zowo+z˜w˜
provided that this is possible. Note that the z simply select a subset of the
i
weights.
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.
0.4
For this set of weights, if X = 6, the problem does not have a solution.
While the general knapsack problem is NPcomplete, 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.
PUBLIC K E Y SYSTEMS
268
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
problem.
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 ml (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
of
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 =
6.2 MERKLEHELLMAN KNAPSACK 269
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)
=
and
m' (mod n ) = 41l (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
Cml (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' + 37mI + 10m1
548m' = 82m'
= 2mm' + 14mm' + 57mm' + 120mm'
= 2 + 14 + 57 + 120
193 (mod 491).
=
PUBLIC K E Y SYSTEMS
270
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 oneway 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 publickey) which arisos
in the MerkleHellman 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.
LatticeReduct ion Attack
6.2.1
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
0
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
coefficients.
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
6.2 MERKLEHELLMA KNAPSACK
N 271
Y
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 =
W=
PUBLIC K E Y S Y S T E M S
272
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 .
,IT
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 Ixing 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 socalled 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 pseudocode,
where G S ( M ) refers t o the GrarnSchmidt 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
pseudocode suffices t o specify the entire LLL Algorithm.
With clever insight, Shaniir [I321 realized that lattice reduction could
be used t o attack the MerkleHellman 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 MerkleHellman
knapsack.
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 =
)
6.2 MERKLEHELLMANKNAPSACK 2 73
Table 6.1: LLL Algorithm
// find short vectors in the lattice spanned
// by the columns of M = (bo, b l , . . . ,b,)
repeat
( 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
forever
with m = 41 and modulus n = 491. Then, ml = 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
and
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.
PUBLIC K E Y SYSTEMS
274
Table 6.2: GramSchmidt, Process
//GramSchmidt M = (bo, b l , . . . , b,)
GS(Rf)
20 = bo
for j = I t o n
2; = b .
3
.I
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
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 0 1 0 0
0
0 0 0 0 0 0 1 0
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
1.
6.3 DIFFIEHELLMAN KEY EXCHANGE 275
0 1 0 1 0 0
11 1
01 1 0 0 0 0
11
0 0 0
11 01 1 2
0 1
1 1 1 0 1 0
1
Mâ€™= 0 0 1021 0 1 0
0 0 0 111
1 1 1
0 1 0
0 0 01 01
0
0 0 0 0 0 111
0
11 11
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
6.2.2
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.
DiffieHellman Key Exchange
6.3
[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?
PUBLIC K E Y S Y S T E M S
276
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 DiffieHellman 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 p2.
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
6.3 DIFFIEHELLMAN K E Y EXCHANGE 277
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.
ManintheMiddle At tack
6.3.1
The DiffieHellrnan key exchange is subject to a maninthemiddle 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 DiffieHellman 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 DiffieHellman
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 reencrypt 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 maninthemiddle attack.
The maninthemiddle attack on the DifficHellman key exchange can be
prevented provided the parties are properly authenticated. For example, an
authentication protocol that uses digital signatures would assure Alice and
PUBLlC K E Y SYSTEMS
278
Figure 6.3: Maninthemiddle attack on DiffieHellniari
Bob that the received messages originated from the correct person. Since
Trudy cannot forge Aliceâ€™s or Bobâ€™s signatures, her maninthemiddle attack
would be thwarted. In addition, such a protocol will prevent a replay attack.
There are several ways to prevent the maninthemiddle attack on Diffie
Hellrnan. For example, the StationtoStatzon 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
manint hemiddle attack.
DiffieHellman Conclusion
6.3.2
DifficHellman provides an elegant solution to one of the most challenging
problems in all of cryptographythe socalled 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 DifficHellman, since the maninthc
middle attack is a serious threat. But the maninthemiddle attack can be
prcvmted in many important applications. Consequently, the DiffieHellman
key exchange is one of the most usefuland widely usedpublic key cryp
tosysterns.
DiffieHellrnan is used, for example, in the IPSec protocol to provide
perfect forward secrecy (PFS); see Problem 4. To achieve PFS, an ephemeral
DzficHellman key exchange is used. In some situations, DiffieHellman can
be used to make a weak PINbased or passwordbased authentication protocol
relatively secure; see [ll]and Problem 5 for more details.
6.4 ARITHMETICAK E Y EXCHANGE 279
Arithmetica Key Exchange
6.4
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 DiffieHellman key exchange, Arithnietica uses an entirely
different approach than DiffieBellman. 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 A2 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
a
of G, we use exponent notation and its properties. Consequently, the elements
in (6.6) can be rewritten as
abalbâ€™, a, bâ€™,
b3a,b4, nbP1a2b,
aba2bK2, l˜,
respectively. A binary operation V' , which is the concatenation operator,
can be defined on G. For example,
PUBLIC K E Y SYSTEMS
280
The set, G of all finite words using the alphabet in (6.5), along with the
concatenation operator "*", is a group (see Section A2 in the Appendix). In
fact, this group is known as the free group o n two genwators and it is denoted
by
(6.7)
G = (u,b).
The elenicrits u and b are the generators of G, since all noriempty 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,
including
1 ˜ = a 2 , 1˜ = b2, 1˜ = ababFâ€™albl, 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
we
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
we
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 } ,
j
6.4 ARITHMETICAK E Y EXCHANGE 281
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(nliE S A and
a = s ˜ .˜ . b = t r ( 0 ) . . . tjmpl
"
.
SB,
7(m1)
40) an1
respectively.
Then Alice computes the set of elements {altoa, . . . , alt,la) and
sends the result t o Bob. Bob computes the set {blslb, . . . , 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 blab since
blab ...
= blSi0
b Zn1
u(0) So(,1)
= b1s2(o)bb1s2(l)b.. . b 1s 2 ˜ ( ˜  ˜ )

,
1
b
. . . (bl˜o(nl)b)znpl.
(bls,(o)b)z"
=
Similarly, Bob can compute a'ba. Using their respective private keys, Alice
and Bob each compute alblab, 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,
say,
G = (z, Y I z4,Y2,P Y z )
and make it public. Alice chooses her public key to be
= {IG, 5'9
(z2,
Y) z2Y}
S A = (SO, =
S1)
and Bob chooses his public key t o be
2
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 = .4y1 I G .y1 = y1
=
PUBLIC K E Y SYSTEMS
282
and Bob generates his private key
b = (x)" = x:3.
Next, Alice computes altoa = ylzy and rewrites it as yzy. She then sends
{ y z y } to Bob. In a. similar manner, Bob coniputes (and rewrites)
and
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
blab (x?)*(x*y)I = ( 2 ) 2 ( y p x  * )
=
= x 4 y 1 x 2  1c; y1.c2 = yx2 = x 2y
'
Finally, she computes al(b'ab) yx2y = x2. Similarly,
(yâ€™)â€™(x2y)
= =
Bob computes
a,1 ba (yxy)" = yxy yxg . yxy
= '
yxy2 x?J2 xy = 2/X 1 G x . 1 G . xy
' '
3
= 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 nonabelian group was used to illustrate the
ideas underlying Arithmetica. In a realworld implementation of Arithinetica,
G, SA, and Sg are chosen to be infinite nonabelian 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 = ylxg? 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 alblah. One
way to do t,his is if every element in G can be put into a unique canonical
6.4 ARITHMETICA KEY EXCHANGE 283
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 polynomialtime 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.
HughesTannenbaum Length Attack
6.4.1
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 lengthswhich is welldefined since every element has a canonical
formhave 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
where
. , . giNl
ko ki
w = siogz,
kN1
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,. . . , sn1)
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
i
public key,
SB = ( t o , t l , . . . , t m  l ) ,
Alice computes u, = ult,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),
q;(,sl
slu)r)
Trudy infers that s is a factor of a on the leftnot with certainty, but with
"
some positive probability. Once a factor is recovered, the attack is similarly
PUBLIC K E Y SYSTEMS
284
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
6.4.2
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, groupbased
cryptosystems and latticebased 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.
RSA
6.5
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 oneway 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 groundbreaking 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 publicprivate 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 A2 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 agreedupon 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 A2 of the Appendix, we
= 1 (mod N ) so that
have
M ( M 4 ( N ) )= M . lk (mod N ) = M (mod N ) ,
k
as desired. On the other hand, if gcd(M, N ) = p , then
( M y = M1+""()
 Ml+(Pl)(ql)k

= M(M4l)"Pl)
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 implementationrelated
attacks on RSA.
Mathematical Issues
6.5.1
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
PUBLIC KEY SYSTEMS
286
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
bruteforce 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 innocentlooking 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 