that 4 ( N )is known, where 1v = p q with r). < p . Then
+ q) + 1= N +4) + 1
(p
4qN) = ( p l ) ( q  1) = p q (p

˜ ˜
arid this implies
d ( N )+ 1.
p+ y =N ˜
Also,
+ q2 + 4pq = ( p
+ 2PY i = p2 +4N,
(P + 4) =P
2 2
q2 2pq 4)™

˜
which implies
+ q)2
q = J(p
p 4N.
 
From (6.8) and (6.9), we can easily compute
6.5 RSA 287
and we have factored N .
In addition, if 4 ( N ) is known, the private key d is easily recovered by
using the Euclidean Algorithm (see Section A2 in the Appendix), since the
encryption exponent e is public knowledge. Since d is the multiplicative
inverse of e modulo 4 ( N ) ,the process to determine d is precisely the same as
that used in the construction of the key pair.
Clearly, the numbers p , q and d must be “large,” so as to prevent a brute
force attack, but what other properties should they (and e) have? When
constructing the modulus N , the prime numbers p and q need to be chosen
carefully. A s t r o n g prime p is a prime number such that p  1 has a large
+
prime factor r , p 1 has a large prime factor, and T  1 has a large prime
factor. Strong primes p and q should always be used in any implementation
of RSA to thwart the factorization of N through the use of Pollard™s p  1
Algorithm [all.
If the modulus N is misused, then RSA is easily compromised. Suppose
that ( e j , N ) are the RSA public keys of j parties. That is, each user has
the same modulus N , but a different public encryption exponents e j (and,
therefore, different private decryption exponent dy). With the knowledge
of a single private decryption exponent d,, we can efficiently factor N , as
explained below. Then the Euclidean Algorithm can then be used to recover
all of the other decryption keys.
Given a decryption exponent d and the corresponding public key ( e , N ) ,
we can determine the factors of N as follows [19]. First, we compute the
number k = de  1. Because of the way d and e are constructed, we know
that k is a multiple of 4 ( N ) ,say, k = & ( N ) for some l. Since 4 ( N ) is even,
so is k . Then k = 2tr, for some odd T and t 2 1. By a similar argument as
that used above to show that the RSA algorithm works, we have
g k = g e d ( N )= 1 (mod N )
for every g E { 1 , 2 , . . . ,N  l} and, therefore, 91
˜™ is a square root of unity,
modulo N , that is, (g˜/™)* = 1 (mod N ) . The number 1 has four square
roots, modulo N = pq. Two of these square roots are *1 and the other two
(which can be found using the Chinese Remainder Theorenlsee Section A2
where z satisfies the conditions z = 1 (mod p )
in the Appendix), are fz,
and IC = 1 (mod 4 ) . Using either one of these last two square roots, the
factorization of N is revealed by computing gcd(n: 1,N ) . l A straightforward
argument [19] shows that if g E { 1 , 2 , . . . , N  1) is chosen at random, then
with probability at least 1/2 one of the elements in the sequence
g k I 4 , . . . , g˜l™˜ (mod N )
g˜/™,
˜See Section 7.2.2 for an explanation of why this technique yields the desired factoriza
tion.
PUBLIC K E Y S Y S T E M S
288
is a square root of unity that reveals the factorization of N. All elements in
the sequence can be efficiently computed in time on the order of n3,where we
have ri = log2 N , that is, n is the number of bits in the binary representation
of N .
If a small decryption exponent is used, then an attack due to Wiener [159]
can break RSA. Let N = p q , where p and q are primes with q < p < 2q and
suppose that the decryption exponent satisfies d < $N'/4. Wiener showed
that under these conditions, there is an efficient algorithm for computing d ,
assuming that the public key (e, N ) is known.
A conirrion small encryption exponent e can be (and often is) used. That
is, all users can share the same encryption exponent e , but have different N
+
and d. Often, e = 3 or e = 216 1 are used in practice, since these values
make public key operations extremely efficient.' But this efficiency does not
carry over to the corresponding private key operations.
Suppose that Alice wishes to send the same message M to Bob, Carol
and Dave, whose respective public keys are (3, N i ) , for i = 0, I , 2. We as
sume that gcd(Ni,Nj) = 1 for i # j , since otherwise an attacker could
factor Ni and Nj by simply computing gcd(Ni,Nj). Given this scenario,
Alice scnds Co = M" (mod No) to Bob, C = M' (mod N1) to Carol
1
and C = M3 (mod N2) to Dave. If Trudy is eavesdropping and ob
2
tains Co, C arid Cz, then she can use the Chinese Remainder Theorem to
1
compute hf3 (mod NoNlNz). Since M 3 < NoNlN2, Trudy can obtain A 4
by simply computing the ordinary (nonmodular) cube root of M" (sec Prob
lem 16). In practice, this cube root attack (and analogous attacks when a
comnion encryption exponent othcr than e = 3 is used) is easily prevented
by padding the message M . Provided that, as numbers, we have n/f > N1/",
the cube root attack will not succeed.
RSA Conclusion
6.5.2
RSA has proven to be remarkably robust. Having been carefully scrutinized
by many researchers, it has remained secure since its invention more than
thrcc decadcs ago [19]. Timing attacks represent the only publiclyknown
practical attacks on soiind implementations of RSA, and these do not result
from any weakness in the underlying algorithms, and, furthermore, there are
straightforward defenses against such attacks.
Thc ItSA algorithm is the "gold standard" in public key cryptography.
Unlike other more specialized systcms, it provides both encryption and signa
tures. The algorithm is also widely deployed and freely available (the patent,s
'Recc,nt,ly. Bleiclrenbachcr has shown t.hat, if f: = 3 is used, a simple signature forgery a , 
t,ack cxxist,s a.gainst certain incorrect implementations of RSA. For this reason, it is generally
recoriin1c:ircietl to avoid using c = 3 as an encryption exporimt.
6.6 RABIN CIPHER 289
have expired). For example, most secure transactions on the Internet use the
Secure Socket Layer (SSL), which uses RSA.
Undoubtedly it is for these reasons that RSA is the de facto standard in
public key cryptography. Baring some major breakthrough in factoring, or
some unexpected attack by other means, RSA appears certain to remain a
defacto standard for the foreseeable future.
Rabin Cipher
6.6
And one of the elders saith unto me.. .
the Root of David, hath prevailed to open the book,
and to loose the seven seals thereof.
 Revelation 5:5
As we saw in Section 6.5, solving the factoring problem breaks RSA. Although
it is generally believed that the most efficient possible way to break RSA is
by factoring the modulus, no proof of this is known. Rabin [118] proposed
a cryptosystem where the underlying encryption algorithm is provably as
difficult to break as the factorization of large numbers.
In Rabin's clever (and simple) cryptosystern, Alice's public and private
keys are generated in the following way: Let N = p q , where p and q are
distinct primes. Although the scheme works for arbitrary primes, to simplify
the exposition we will assume that p = 3 (mod 4) and q = 3 (mod 4). Alice's
public key is N and her private key consists of p and q.
An agreedupon protocol for converting text into a sequence of positive
integers (each less than N ) is established. Then to encrypt message M ,
compute C = M 2 (mod N ) . Decryption is accomplished by the computation
of square roots of the ciphertext C modulo N , one of which yields the message
M.
How does Alice compute the square roots of ciphertext C modulo N?
We first examine the case where we want to compute the square roots of C
modulo a prime p . The case where C = 0 (mod p ) is trivial, so we assume
that C # 0 (mod p ) . Then we set y = C(P+')/4 (mod p ) , and by Euler's
Theorem, CPpl = 1 (mod p ) , and therefore,
y4 = CP+l = C2Cpp1 C2 (mod p ) .
=
This implies
+ C) = 0 (mod p ) ,
y4  C2 = (y2  C)(y2
and hence y2 = fC (sce Problem 17). From this, we deduce that C is a square
modulo p or that C is a square modulo p , but not both (see Problems 18
PUBLIC K E Y S Y S T E M S
290
and 19). In the case where C is a square modulo p , the square roots of C
are fy; otherwise, the square roots of G modulo p are *y.
For example, suppose we want to find tlie square roots of 3 (mod 11).
+
Sincc ( p 1)/4 = 3, we have
= 33 = 27 = 5 (mod 11).
= 3(pf')/'
y˜
So, either &5 are the square roots of 3 (mod 11) or f 5 are the square roots
of 3 (mod ll), but not both. In this particular example, it is easily verified
that (*5)2 = 3 (mod 11).
Now we consider the computation of square roots, modulo N , where, as
usual: N = pq. In this slightly more complicated situation, we begin with
a concrete example. Suppose that we want to solve x2 = 16 (mod 33).
Any solution of this equation satisfies x2 = 16 + 3(11)k and, in addition,
x2 = 16 = 1 (mod 3) and x2 = 16 = 5 (mod 11). Using the method
described in the previous paragraph, we find that f l are the square roots of
1 (mod 3) and that f 4 are the square roots of 5 (mod 11). These can be
combined in any of four ways:
1 (mod 3)
4 (mod 11) and 2
IC = =
= 1 (mod 3 )
= 4 (mod 11) and z
17:
z = 4 (mod 11) and z = 1 (mod 3 )
IC = 4 (mod 11) and z = 1 (mod 3 )
and s so that 1lr+3s = 1.
Using the Euclidean Algorithm, we find integers T
In this case. we see that
11 = 3 . 3 + 2
3= 2.1+ 1
2=1.2+0.
+
By backsubstituting, we find 11(1) 3(4) = 1. The Chinese Remainder
Theorem provides the unique solution (mod p q ) for the system
(mod p )
IC = a,
(6.10)
z = h (mod q )
namely, z = b p f ˜ q s , where p r + q s = 1. So, in our example, we have p = 11,
a
q = 3. 7 = 1 and s = 4. Therefore, the unique solution to the system
'
n. = 4 (mod 11)
.r 1 (mod 3)
=
+
+ 48 = 37 = 4 (mod 33). In a
is L = (1)(11)(1) (4)(3)(4) = 11
similar fashion, we find that the solutions to the other three systems are given
6.6 RABIN CIPHER 291
by z = 26 (mod 3 3 ) , z = 7 (mod 33) and z = 29 (mod 33), respectively,
and we have that the square roots of 16 (mod 33) are 4, 7, 26, and 29.
In summary, to compute square roots of C (mod N ) , we first conipute
the square roots of C, modulo p and q . Then all systems of the form (6.10),
where a is a square root of C (mod p ) and b is a square root of C (mod q ) are
created. Using the Chinese Remainder Theorem, solutions to these systems
are found. These solutions are the square roots of C (mod N ) .
Once the square roots of C (mod N ) have been computed, Alice needs to
decide which one of the square roots corresponds to the original plaintext M .
If the message is written in some natural language, it is easy for her to choose
the right one. In the case where the message is less structured, the sender
might add a header to the message. Such additional information would allow
Alice to easily determine the correct square root of C.
Chosen Ciphertext Attack
6.6.1
If the attacker Trudy is able to compute square roots modulo N , then she
can factor N and thereby break the Rabin cryptosystem. To see why this is
the case, consider the modulus N = p q , where p > 2 and q > 2 are distinct
primes. Let u and u be square roots of C (mod N ) ,and assume that u # f v .
It is easily verified that either p = gcd(u+w, N ) or q = gcd(u+u, N ) as follows.
c
Since u2 = v2 = (mod N ) ,we have that N divides ( u 2  u 2 ) = (u+u)(u u ).
+
But, N does not divide u v and N does not divide u  u. Therefore, from
+
the Euclidean Algorithm, we compute gcd(u u, ) which is one of the prime
N
factors of N .
This fact allows Trudy to perform the following chosen ciphertext attack
on the Rabin cryptosystem. Suppose that Trudy has access to Alice™s de
cryption machine (as a black box). Trudy chooses M , where 0 < M < N and
computes C = M 2 (mod N ) . She then uses Alice™s decryption machine to
decrypt C, yielding y. The probability that M # f y (mod N ) is l / 2 , and
if this is the case, Trudy finds the prime factors of N and is able to read all
messages sent to Alice; see Problem 23.
By applying some appropriate message preprocessing, this attack can be
thwarted. For example, optimal asymmetric encryption padding (OAEP) [lo]
is a padding scheme that can be used to encode a message before asymmetric
encryption is applied. Through the use of such a scheme, two goals are
achieved. First, an element of randomness is introduced, which converts a
deterministic encryption scheme into a probabilistic one. Secondly, partial
decryption of ciphertexts is made more difficult.
The OAEP scheme works as follows [36]. Here, we assume that binary
strings of length n are used by the bijective trapdoor function f of a cryp
tosystem. Along with this, OAEP utilizes a pseudorandom bit generator G
that maps kbit strings to kbit strings and a hash function h mapping !bit
PUBLIC K E Y SYSTEMS
292
+
strings to kbit strings, where n = k I?.
To encrypt a message M E (0, l}', a random bit string (0, l}kis first
E
T
chosen. Then, we set
z = ( M @ G ( r ) )11 @ h(k1@ G ( T ) ) ) ,
(T
where the "/l'. indicates concatenation and "@" denotes the bitwisc XOR
operator. Finally, C = f ( z ) is computed. The first I? bits of z, that is,
M @ G ( T ) , obtained from the mixing of M and the pseudorandom bits
are
G ( T ) .The last k bits of z arise from the mixing of random seed T and masked
h ( M @ G ( T ) ) .Therefore, a single message M can (and will) yield different
cipliertexts, given different random bit strings T .
To decrypt ciphertext C , we use f  ' , the same pseudorandoni bit gener
ator G, and the same hash function 11 as above. First, we computc f  ' ( C )
which is o f the form a 11 b, where the length of a is J? and the length of b is k .
Next, we compute T = h ( a ) @ b. Then to recover the original message M , we
use the fact that
A1 = M @ G ( T ) G ( T )= k @ G ( T ) G ( h ( a )@ b) = a @ G ( T ) .
1
@ @
In order for attacker Trudy to recover plaintext M from ciphertext C = f ( z ) ,
she must determine all of the bits of n: from C. She needs the first I? bits to
compute h ( a ) and the last k bits to get T . Consequently, partial decryption of
cipliertexts (by exploiting some partial knowledge of z) is made more difficult.
Rabin Cryptosystem Conclusion
6.6.2
Although the Rabiri cryptosystem is effective and it was developed shortly
after RSA, it has never enjoyed anything like the popularity of RSA. Per
haps, this is because only one of the four possible decrypts of a ciphertext
corresponds to the plaintext. However, this issue is easily resolved.3
It is easily verified that the security of the Rabin cryptosystem is equiva
lent to factoring, while this is not known to be the case for RSA. Consequently,
it is conceivable that R S A could be compromised without solving the factor
ing problem. Viewed in this light, it is not unreasonable to argue that the
Rabin cryptosystem rests on a somewhat more secure foundation than RSA.
Of course, to date, thc most significant general attack on RSA is to factor
thc modulus. So, in a practical sense, thc security of RSA and Rabin are
indistinguishable today. Without an overwhelming reason to abandon the
gold st,aridard o f RSA, it is unlikely that the Rabin cryptosysteni will gain a
1110rcsignificant following in the public kcy arena.
"HSA was patented (the patents have now expired) and promoted by RSA Security, Inc.
Jri contrast, thc Rahin cipher had no comparable corporate hacking.
6.7 NTR U CIPHER 293
NTRU Cipher
6.7
“That™s a great deal to make one word mean,”
Alice said in a thoughtful tone.
“When I make a word do a lot of work like that,”
said Humpty Durnpty, ˜(I always pay it extra.”
 Through the Looking Glass
Relative to many other public key cryptosystems, the NTRU cipher, rumored
to stand for “Nthdegree TRUncated polynomial ring” or “Number Theorists
aRe Us,” is young. Invented in 1995 by Hoffstein, Pipher, and Silverman [68],
it is somewhat more complicated than RSA or the Rabin cryptosystem. The
security of NTRU derives from the difficulty of a certain factoring problem
in a polynomial ring. We have more to say about this below, but first we
describe the NTRU system and give an example.
The NTRU cipher depends on three positive integer parameters ( N , , Q)
p
and four sets of polynomials of degree N  1 with integer coefficients. The
sets if polynomials are denoted L f ,L,, L,, and L,. The parameters p and g
are chosen so that gcd(p,q) = 1 and q > p , where q must be much larger
than p .
All of the NTRU polynomials are in the set of truncated polynomials of
degree N  1 having integer coefficients. That is, an NTRU polynomial is of
the form
+ ™ . . + uN2xN2 + U N  l X N1 ,
u(x) = uo + a12 + a2x2
where the ai are integers (taken modulo p or g, depending on the specific
polynomial). Polynomials are added in the usual way. Multiplication is per
fomed modulo xN  1, meaning that polynomials are multiplied in the usual
way, but xN is replaced by 1, x N f l is replaced by x, xN+2is replaced by x2
and so on. We use the symbol LL*” denote this type of polynomial mul
to
tiplication. In mathematical terms, all of the NTRU polynomials are in the
quotient ring
Z[Xl
R=
1)
(XN  ™
The message space L , consists of all polynomials in R modulo p . Assum
ing that p is odd, we define the message space as
I
{M(x) E R
L, 1 ) / 2 , ( p  1)/2]}.
all coefficients of M lie in [  ( p
= 
As a notational convenience, let L ( d 0 ,d l ) be the set of polynomials in R
with do coefficients that are +1 and dl coefficents that are 1, and all re
maining coefficients are 0. For example,
+ x2 + x3  x5 + x9 E L ( 3 , 2 ) ,
1
PUBLIC KE Y SYSTEn;%S
294
since the nonzero coefficients consists of three +Is and two 1s.
Given the NTRU parameters ( N ,p , (I), we must select three additional
parameters, denoted d f , d,: arid d, which should be selected from the recom
mended NTRU parameters (the current set of recommended paranieters can
be found at [108]). These additional parameters are used t o define the sets
of polynomials
and L,, = L ( d , d ) .
L, = L(d,, d,),
L f = L ( d f df
, l),

Now Alice generates her NTRU key pair as follows. She first chooses two
polynomials f ( z ) and g z ! where f ( z ) E L f and f ( x )is invertible modulo p
()
and modulo q , and g(z) E L,. She can find a suitable f ( z )using the algorithm
in Table 6.3 [137].
Table 6.3: Algorithm t o Find Inverse Polynomial
// Input: polynomial u ( J ) , primc p
// Output: b ( r ) = u ( z ) p l in ( 2 / p 2 ) [ z ] / ( z N 1)
// Initialization
k = 0, b(z)= 1, .(z) = 0, f ( z ) = u ( z ) , g(z) = zN  1
// find inverse
repeat
while .fo = 0
f(.) f(r)/r
=
*1
c(z) = c ( z )
k=k+l
end while
if deg(f) = 0 then
b ( z )= f r l b ( z )(mod p )
return r N ' b ( z ) mod (z" 1)

end if
< dcg(g) then
if deg(f)
swap(f. 9)
swap(b, c)
end if
u = fog;' (mod p )
f ( z ) = f(x)  u * g ( . r ) (mod p )
b ( z )= h ( x ) 7˜ * c ( r ) (mod p )
forever
Denote the inverses of f ( z ) modulo p and q and f q ( z )respectively,
ah f,(z)
that
SO
* f ( z ) = 1 (mod *f =
p ) and f(,(.˜) ( 1 ) 1 (mod (I)
f,,(a)
6.7 NTRU CIPHER 295
Then Alice™s public key is the polynomial h ( z )= fq(z) *g(z) (mod q ) . The
ploynomial h ( z ) ,along with the parameters N , p , and 4 , are made public.
Alice™s private key consists of t.he polynomials f(x) and f,(z). To summarize;
we have
Public key: h(z)
Private key: ( f ( z )f,(z))
,
*
where h(z)= fq(z) g(z) (mod q ) and f ( z )* f,(z) = 1 (mod q ) .
Bob sends Alice an encrypted as follows. Bob first selects a polyno
mial M ( z ) E L , that represents the plaintext message. Recall that the
coefficients of the message ploynomial M ( z ) are in the range  ( p  1)/2
and ( p  l ) / 2 and that q is much larger than p . Consequently, the mes
sage M ( z ) can be viewed as a “small” polynomial modulo q , in the sense
that the vector of coefficients has small Euclidean length.
Bob then chooses a random “blinding” polynomial r ( z ) E L, and uses
Alice™s public key to compute the ciphertext message C(z) (also a polynomial)
as
+
C(z) = r(x) * h(z) M ( z ) (mod q ) ,
which he sends to Alice.
To decrypt Bob™s message, Alice computes
The coefficients of a(.) are chosen to be in the interval 4/2 to q / 2 (it is
crucial that the coefficients be taken in this interval before the next step in
the decryption). Then Alice computes b(z)= u ( z ) (mod p ) . Although it is
not obvious, Alice recovers the message M ( z ) by computing
Below we give an intuitive explanation why NTRU decryption works, but
first we give an example.
To illustrate the NTRU algorithm, we use the example found at [108].
Suppose that we select NTRU parameters N = 11, q = 32, p = 3, and the
sets of polynomials L f = L(4 ,3) , L, = L ( 3 , 3 ) , and L, = L( 3,3) . Then to
generate her private key, Alice selects a polynomial f ( z ) E L f , that is, a
polynomial of degree ten with four +1 coefficients and three 1 coefficients,
and all remaining coefficients set to 0. She also chooses a polynomial g(z),
where g(z) E L,. Suppose that the selected polynomial are
+ z + x2 z4 + z6 + 2 9 z10 E L f
f ( z ) = 1  
+ x2 + z3+ z5  2 8 5 1 0 E L,.
g ( z ) = 1 
PUBLIC K E Y SYSTEMS
296
Next, Alice computes f,(z) and fq(.?:), the inverses of f ( x ) modulo p and q.
respectively. Using the algorithm in Table 6.3, she finds
+ 2x + 2 ˜ + z r 4 + 2c5 + 2x7 + 28 + 229
f,(.) =1 3
= 5 + 9x + 6.r2 + 162' + 4x4 + 15x5 + 162' + 22x7
f,(x)
+ 2 0 2 + 18rY+ 302".
Alice's private key consists of the pair of polynomials ( f ( z )f,, ( z ) ) . To gen
erate her public key h ( z ) ,Alice computes
* s(x)
h(x) = P f & )
+ 252 + 22x2 + 2 0 2 + 12x4 + 24x5 + 15x6
8
=
+ 19z7+ 12x8 + 19zy+ 16x1" (mod 32).
Now: suppose that Bob wants to send the message
+ + x9 + X I " L,
M ( x ) = 1 x4  2 E
'

t o Alice. He first chooses a random blinding polynomial r(x) of degree ten
(or less) with thrce $1 coefficients and three 1 coefficients, say,
+ 2 + 2 + x4 .r5 x7 E L,.
r ( x ) = 1 
Bob computes the ciphertext polynomial C(z) as
+
*
C ( x )= ,r(x) h ( x ) M ( x )
+ ll.?:+ 2 6 2 + 24x3 + 14x4 + 16x5+ 3 0˜˜
14
=
+ 7x7 + 252' + 62" + 1 9 ˜ ' "(mod 32),
which he sends to Alice.
When Alice receives the ciphertext polyriornial C(z) from Bob, she uses
her private key f ( x ) t o compute
* C(x)
a(.) =f(x)
+ lox4 + 7z5 + 6x6
72  lox2
=3 llz3
 
+ 727 + 52' 3xY  72'" (mod 32),

where the coefficients of a(.) havc been chosen to lie between 4/2 and y/2
(in this example, from 15 t o + 1 G ) . Alice then reduces the coefficicnts of a(.?:)
modulo p = 3 to obtain
: 2+ x3 + x4 + x5 + x7  x8  d o (mod 3).
z
b ( x ) = 2 
She finds the plaintext message M by computing
+ xg + zl" (mod
+ x3
f p ( x ) b ( 2 ) = 1 3).
x4 x'
 
6.7 NTRU CIPHER 297
+
Why does NTRU work˜? Consider C(z) = r ( z )* h ( z ) M ( z ) (mod q ) ,
where h ( z )is, say, Alice™s public key. Recall that h ( z )= p f q ( z ) * g ( z ) (mod q ) .
For the first step in the decryption, Alice computes
* C(z) = f ( z ) * r ( z )* h ( z )+ f ( z ) * M ( z ) (mod q )
u(z)= f ( z )
=P f ( X ) *) * f q b ) * d z ) + f(.) * M ( 2 ) (mod
(
. 4)
= p r ( z )*g(z) + f ( z ) * M ( z ) (mod q ) .
and M ( z ) all have coefficients that are
The polynomials ˜ ( z )g ( z ) , f(z),
,
small, relative to q . Therefore, the polynomial p r ( z ) * g ( z )+ f ( z ) * M ( z )(not
taken modulo q ) is most likely the same as the polynomial
* g(z) + f(.) * M ( z ) (mod 4).
PT(X™)
If this is the case, the “mod q” in the computation of u ( x )has no effect and
it follows that
b(z)= u ( z ) (mod p ) = f ( z ) * M ( z ) (mod p ) ,
as desired. Then since f p ( z * f ( z ) = 1 (mod p ) , Alice can easily recover the
)
+
plaintext M ( z )from b(z). However, if p r ( z )*g(z) f ( x )* M ( z ) (not taken
modulo q ) does not equal the polynomial p r ( z ) * g ( z )+ f ( z ) * M ( z )(mod q ) ,
then the decryption can fail. Therefore, the NTRU decryption process is
probabilisticalthough it does succeed with a very high probability for ap
propriately chosen parameters.
Before considering attacks, we briefly discuss the underlying hard problem
that is the basis for the security of NTRU. The NTRU public key is the
polynomial h(z), where
* d z ) (mod
h ( z )= f&) 4)
and the corresponding private key consists of the pair of polynomials f ( z )
and f q ( z ) ,where f ( z ) * f,(z) = 1 (mod q ) . Note that this implies
h ( 2 )* f ( z ) = g ( z ) (mod q ) .
If the attacker, Trudy, can determine f ( 5 ) or f q ( z )from h ( z ) , can recover
she
the private key and thereby break NTRU.
We have
+
+ ++
h ( z )= ho hlz h2x2 . . . hN1ZN™,
with f ( z ) and g z defined similarly. Let f be the column vector of coefficients
()
of f ( z ) and g the coefficients of g(z), also given as a column vector. Next,
define the N x N matrix
PUBLIC K E Y SYSTEMS
298
.˜*™˜,we have
Then by t.he definition of
We can now state the problem of recovering f ( r )from h ( r ) as a lattice
reduction problem. Given the public key h ( z ) , we have the block matrix
equ. t 1011
d ™
where V and W are unknown. This block matrix equation simply states
+ qs = g (mod 4 ) . From this latter equation it follows
that f = f and Hf
that H f = g (mod q ) , regardless of s. Since H only depends on the public
key h , ( z ) ,if we can determine V or W, then we can break NTRU. But W is
in the lattice spanned by the columns of AJ (note that, due to the identity
matrices on the diagonal, the columns of M are linearly independent). Fur
thermore, W has a very special form, since it is a “short” vector in the lattice
(recall that both f ( z ) and g(z) are chosen to be small relative to q ) , and the
clenients of W consist of a known number of f l s , 1s and 0s (as determined
hy the parameters d f and d g ) .
This lattice reduction problem is very similar to that used to successfully
attack the knapsack; see Section 6.2. Therefore, we could use lattice reduc
tion techniques, such as the LLL Algorithm in an attempt to break NTRU.
However. the NTRU lattice problem is believed to tic very difficult to solve,
arid no efficient algorithms are known. In fact, the security of the NTRU ci
pher is intentionally based on the difficulty of this particular lattice reduction
problem. It is somewhat ironic that the very technique that leads t o a dev
astating attack on the knapsack can, in a slightly modified setting, become
the basis for constructing a public key system.
It is worth noting that there is one significa.nt difference between the
NTRU lattice problem in (6.11) and the knapsack lattice problem considered
in Section 6.2. The successful knapsack attack breaks a single message, but it
does not enable the attackcr to recover the private key. However, in (6.11) we
are trying to recover the private key from the public key, and, intuitively, this
should be a much harder problem. So it might seem to be unfair to compare
this NTRU lattice problcni to the knapsack lattice problem. It is possible
to give a lattice reduction attack on a single NTRU message, which is more
analogous to the knapsack setting. However, the NTRU lattice reduction
attack is intractable (as far as is known), even in this seemingly simpler
[loll.
CRSC
The primary claim to fame for NTRU is its eficiency˜the encryption,
decrypt,ion. and the key generation process are all very fast by public key
6.7 NTRU CIPHER 299
standards. The inventors of NTRU claim that when comparing a moder
ate NTRU security level to RSA with a 512bit modulus, NTRU is approxi
mately 5.9 times faster for encryption, 14.4 times faster for decryption and 5.0
times faster during key creation [68]. In addition, when comparing the high
est NTRU security level to RSA with a 1024 bit RSA modulus, it is claimed
that NTRU is the same speed for encryption, 3.2 times faster for decryption,
and 5 . 3 times faster for key creation. For this reason alone, NTRU might be
an attractive cryptosystem to use in resource constrained environments such
as embedded systems.
NTRU is somewhat unique since there have been several published at
tacks, but yet the cipher is not considered broken. In the next sections, we
briefly outline a few attacks against NTRU. Some of these attacks have led
to modifications in the suggested parameters for NTRU.
MeetintheMiddle Attack
6.7.1
The NTRU cipher is susceptible to a meetinthemiddle attack. Andrew
Odlyzko first pointed out that if a polynomial s(z) is chosen from a space
with 2n elements, then a bruteforce search can be conducted on a space
of size 2n/2 to recover s(z). His argument was then adapted by Silverman
in [136],where it is shown that if the private key f(x) is chosen from a space
of 2n elements, then the security level of NTRU is 2r1/2.Here, we outline how
this attack works.
Let N , q, d f , f ( z ) , g(z), and h ( z ) be defined as above. To illustrate
the attack, we assume that N and d f are even. The modifications to the
attack for odd values are straightforward. All polynomials are expressed as
ascending sums of powers of x. Let k and !be positive int,egers chosen by
the attacker, Trudy, so that
where the lefthand side of the inequality is much greater than the righthand
side (by, say, a factor of 100).
Let the symbol “I/)™ denote concatenation. Trudy searches for the private
where f ( x )E L ( d f , d f  1) is of the form fo(z) /I f ˜ ( z )and f o ( z )
key f ( z ) , ,
(of length N / 2 ) has d f / 2 coefficients of +1 and d f / 2 coefficients of 1 (and
the rest, zeros) and fi(x) (of length N / 2 ) has d f / 2 ones, d f / 2  1 negative
ones (and the rest, zeros). She wants to find f˜fbx) f l (z) such that
and
has coefficients in {1,0, 1). If this is the case, then g(z) (mod y) is of the
correct form and therefore fo(x) 1) f l ( z ) is a candidate for the private key.
PUBLIC K E Y SYSTEMS
300
First, Trudy lists the polynomials f o ( x ) , which are of length N / 2 . We
identify these polynomials with the lengthN vectors formed by append
ing N / 2 zeros. This requires
steps and is done in the following manner. The f o ( x ) polynomials are stored
in bins based on the first k coordinates of f o ( x )* h(x) (mod 4 ) . To form the
tins, divide the interval [0,y  1 into subintervals of length 2e and call this
1
set of subintervals I, that is, the set I is composed of the subintervals
+ 1) + 11,
e.
Y.
o I < y/2'.
I, 12 j , 2 j
where
(j
=
A bin is a ktuple of intervals chosen from I . If the first k coordinates
of fO(z) * h ( z ) (mod y) are, respectively, (ao, u l , . . . , U k  l ) , then f o ( x ) is
stored in bin (I",.. , I k  l ) , where ai E Ii, for i = 0 , 1 , . . . , k:  1. Note that
.
the storage location of an f o ( x ) depends only on its first k coordinates and
therefore, a bin may contain multiple f 1 (x)polynomials.
In a similar manner, Trudy lists the polynomials f l ( z ) , which are also
of lcngtli N / 2 . In this case, we identify the polynomials with the lengthN
vectors formed by prepending N / 2 zeros. This requires
steps. The f l ( x ) polynomials are stored in bins based the first k coordinates
of each polynomial  f l ( z ) * h(z) (mod q ) . However the bins which are
formed for the f l (x)polynomials are slightly larger than the f o ( z ) bins. More
precisely, let ,I be the set of subintervals
+ 1) 11, where 0 I < q/2'.
j
J:, = [2';j  1,2'(j 
The subintervals J j overlap. so some f l ( x ) polynomials will go into more t,han
m e bin.
Finally, Trudy finds the nonempty, overlapping f o ( x ) and f 1 ( x ) bins. In
this case. for each
it is very likely that (fo(z) 11 fl(:x))*h(.˜:) (mod q ) has coefficients in (1: 0: l}.
Therefore. f o ( x ) I/ f l ( x ) is a candidate for the private key f ( z ) , which follows
from the fact that (.fo(x) I/ f l ( : r ) ) * h(z)(mod q ) is of the correct form.
A few remarks might help to clarify the attack. Although the private
kcy f ( : r ) may not, have the property that half of its ones (that is, d f / 2 of
6.7 NTRU CIPHER 301
its ones) fall in the first N / 2 bits, there is at least one rotation of f ( z )
which has this property and any rotation of f ( z ) can serve as the private key
(see Problem 26). In [136], it is assumed that f ( z ) is chosen with d f ones
and N  d f zeros and some technical conditions on g(z) are satisfied. Under
these conditions, Silverman showed that the time required for the attack is
on the order of
fi
time (f>k
and that the storage necessary for the bins is on the order of 2 ( q / 2 ' ) 2 k . Fur
thermore, Silverman provides experimental results for various values of N , q,
e.
df,k , and
Multiple Transmission Attack
6.7.2
Suppose that Trudy conducts a denialofservice attack on Alice. During this
time, Bob sends Alice an NTRU encrypted message using her public key h ( z ) .
Because of Trudy's attack, his message never reaches Alice. Since Bob is not
aware of Trudy's attack, he assumes that the message was lost and he resends
the same message, again using Alice's public key h ( z ) ,but a different blinding
polynomial ˜ ( z ) .Suppose that this scenario is repeated a few more times,
with Bob sending the same message M ( z ) to Alice n times, using the same
public key h ( z ) but each time using a different r ( z ) , where the i,th choice
of ˜ ( z is denoted r i ( z ) .
)
Under this scenario, Trudy can attack NTRU. The outline of the attack
is as follows. Trudy intercepts the encrypted messages
+
Ci(z) = r i ( z )* h ( z ) M ( z ) (mod q ) , for i = 0 , 1 , . . . ,n.
Assuming that h p l ( z ) (mod 9) exists, she then computes
Ci(z)  Co(z) = p r i ( s ) * h ( z ) p r o ( z )* h ( z ) (mod q )
* h ( z ) (mod q),
= P ( T i ( 2 )  To(.))
for i = 1 , 2 , . . . , n, and Trudy thereby obtains
*
z i ( z ) = ppl(Ci(z) Co(z)) h  l ( z ) (mod y)
(mod
=˜ y),
i ( 2 T ˜ ( x )
)
for i = 1 , 2 , . . . , n. Trudy reduces the coefficients of zi(z)so that they lie
between  q / 2 and q / 2 . Since the coefficients of the r i ( z ) are small (relative
to q ) , she recovers r i ( z )  r g ( z ) , for most (if' not all) i = 1 , 2 , . . . ,n. From
this, many (if not all) of the coefficients of ˜ ( z can be obtained (see Prob
)
lem 28). If Trudy can recover enough of ˜ ( zin this way, then she can recover
)
the remaining coefficients by brute force. Once ˜ ( zis) known, Trudy com
putes Co(z)  ˜ ( z* ) ( z ) (mod y) and thereby recovers the message M ( z ) .
h
PUBLIC K E Y SYSTEMS
302
Chosen Ciphertext Attack
6.7.3
In 2000, Jaulrnes and Joux [73]developed a clever chosenciphertext attack on
NTRU. Their discovery resulted in changes to the recommended parameter
sets by NTRU Cryptosystems, Inc. Since the attack also is effective on OAEP
likc padding, which was originally proposed for use with NTRU, other padding
methods are now used with NTRU. For our overview of the attack, we will
reference the NTRU parameter sets given in [138] and reproduced here in
Table 6.4.
Table 6.4: Previous Recommended NTRU Parameters
Recall that the NTRU decryption process consists of first computing
f(.) * M ( T )
a
(
.) =
+
= f ( ˜ r) r )* h(z) f ( x ) * M ( x ) (mod 4 )
*(
+
= f ( z ) * p r ( ˜*)f,(x) * g(z) f ( x ) * M ( z )(mod q )
* g(x)+ f *) (111od s ) ,
( ˜ M(.)
=pr(r)
followed by f p ( x ) * u ( x ) (mod p ) which usually yields the plaintext mes
sage M ( z ) .For appropriate parameter choices. the coefficients of the polyno
mial p r ( x )*y(x) + f ( z ) * M ( x )lie iii the range q/2 and q/2. Consequently,
the polynomial pr*g(cr) + f(x)* M ( z )(mod q ) is the same as the truc (riori
modular) polynomial, t h a t is; the mod q has no effect. The idea of Jaulmes
and Joux's chosenciphertext attack is to construct ciphertexts, which result
in intermediate polynomials whose modular values differ from the true values.
For cxample, suppose Trudy cliooses a ciphcrtext polynomial which is of
+
tlic form C ( x ) = yh(5) y, where y is an integer and h(z)is Alice's public
key. The NTRU decryption algorithm yields
* C(n:)= f ( x )* y h ( z ) + yf(z) (mod q)
a(.) = f(x)
= yyf(.z.) * h ( z )+ y f ( ˜ ) q)
(mod
+yf(x
= ?/dJ..) ) (mod 411
where f ( x ) and g(z) both have coefficients in (0, 1, I}. It follows that the
+
polynomial ?jy(z) y f ( z ) has coefficicnts in (0, y, y, 2y, 2y}. If Trudy has
chosen y so that>y < q / 2 arid 2y > q / 2 . then the decryption process reduces
6.7 NTRU CIPHER 303
only the coefficients equal to f 2 y modulo q and these coefficients are selected
so as to lie between  q / 2 and q/2. Now suppose that a single coefficient
+
of u ( z )is f 2 y , say, ai = +2y. Then u ( z ) (mod q ) = yg(z) y f ( z )  qzz, and
the final decrypted output is
+Y
f p ( 4 * 4.1 * 4x2
*
= Y f p ( Z ) S(%) (mod
fp(4

Furthermore, if Trudy chose y to be a multiple of p , then the final decrypted
output collapses to
z ( z ) =  f p ( x ) * 9x2  q f p ( z )* zz (mod p ) .
=
Trudy then recovers Alice™s private key f ( x ) by computing
* Y1(z) (mod p).
f ( z ) = 422
+
In general, the polynomial y f ( z ) yyg(z) may have none or several co
efficients equal to f 2 y . In these cases, the above attack would not work.
However, this chosenciphertext attack can be generalized and it can be prac
tical, even for stronger security parameters [138].
The intersection polynomial w(x) of polynomials u(x) and u(x) is defined
to be
+ ++
+
2
= wo W 1 2 2 0 2 2 ... wNIxNl,
W(.)
where
We say that polynomials u ( x ) and v ( x )have a collision when they have the
same nonzero coefficient in a corresponding term.
In the attack discussed above, the intersection polynomial of f ( x )and g ( 2 )
was the polynomial w(x) = xi,that is, f ( x )and g(z) had one collision. Using
the security parameters corresponding to N = 107 in Table 6.4, Jaulmes
and Joux found that the probability of one collision occurring between f ( x )
and g ( 2 ) was 0.13. Therefore, for this particular choice of parameters, the
+
chosen ciphertext attack using C ( x )= yh(z) y is successful approximately
thirteen percent of the time and, in these instances, it easily recovers f ( z ) .
For higher security parameters, the number of expected collisions be
tween f ( x )and g(%) is too high and Alice™s private key f ( x )cannot be re
+
covered in this manner when using the chosen ciphertext C(z) = yh(z) y.
In these cases, chosen ciphertext messages of the form
+ . . . + yh(z)zZf™ + yzjo + . . . + yzjs1,
= yh(z)ziO
.(%)
where y is a multiple of p with
+s + sly > q/2
1)y < q / 2 and (t
(t 
PUBLIC K E Y S Y S T E M S
304
can be used t o attack NTRU. The numbers t and s are chosen so that the
average number of collisions between
t 1 sI
P=O
E=O
is approxiniately one. Jaulmes and ,Joux give the heuristic approxiniation of
t,hc riiimber of collisions as
2d;db
Nt+S1 ™
When this number is near one, appropriate values for t and s have been
deterrnined for the chosenciphertext attack. In [73],the authors present a n
example of complete key recovery, using the highest security set of parameters
described in [138]. They also provide estimated running times for different
sets of parameters using different, values o f t , s , and y.
Although we will not discuss it here, Jaiilmes and Joux also shows that
this attack ca,n be modified so that it is effective against OAEPlike padding
within NTRU. One way to thwart, this chosenciphertext attack is t o use othcr
padding methods as described in [54].
NTRU Conclusion
6.7.4
Like any respectable cryptosysteni, NTRU has been under close scrutiny
sirice its invention. As attacks arid weaknesses have been discovered, the
implementationas well as the recommended security parameters N , p , q ,
L j . L,, and L,rhave evolved over time. In fact, NTRU encryption is now
in its third major revision, due t o viable attacks on earlier v e r ˜ i o n s . ˜
Of course, Kerckhoffs™ Principle dictates that a cryptosystem must be
subject t o extensive investigation. However, the evolution of NTRU is in
stark contrast to, say, RSA, which has undergone no significant revisions
since its invention. Given these track records, it could be argued that RSA
likely rests on a sounder foundat,ion than NTRU. Nevertheless, there are no
known weaknesses in the current version of NTRU encryption [ l o l l .
In any case, it appears t,hat NTRU is a crypt,osystt:m with a future, in
contrast to many other proposed public key systemsalthough a cynic might
argue that this has as much t o do with patents and the heavy corporate
backing NTRU has received than with any inherent technical superiority.
Tirnc will tell whether the current version of NTRU proves more durable
than its predecessors.
˜ N o t e that thesc revisions are rriiich more significant than simply increasing the size of
tlicx parameters.
6.8 ELGAMALSIGNATURE SCHEME 305
ElGamal Signature Scheme
6.8
Drink nothing without seeing it; sign nothing without reading it.
 Spanish Proverb
Public key cryptography can be used to create digital signatures. If properly
implemented, when Bob receives a message digitally signed by Alice, he is
assured that it was composed by Aliceassuming that Alice™s private key is
private.
Several different digital signature schemes have been proposed. For exam
ple, RSA can be used for signing by simply using the private key to “encrypt”
and the public key to verify the signature. ElGamal is another signature
scheme, which we discuss in this section.
In this section, we employ the public key notation defined previously in
Section 5.1. That is, we use the following notation:
Encrypt message M with Alice™s public key: C = { M } ˜ l i ˜ ˜ .
0
c with Alice™s private key: M = [C]Alice.
Decrypt ciphertext
0
Signing and decrypting are the same operations, so the notation for
0
Alice signing message M is S = [M]*lice, where S is the signed message.
Encryption and decryption are inverse operations so that
[{M)AlicelAlice = {[MIAlice)Alice = M .
It is important to remember that only Alice can sign since the signature
requires Alice™s private key. However, anyone can verify Alice™s signature,
since that is a public key operation.
We can define confidentiality as “no unauthorized reading” and integrity
as “no unauthorized writing” [142]. By using Bob™s public key, Alice can send
encrypted messages to Bob and be assured of confidentiality. For integrity,
Alice can use a digital signature, as discussed in Section 5.1. Both integrity
and confidentiality can be achieved by using symmetric key cryptography, but
a digital signature also provides nonrepudiation, which cannot be achieved
with symmetric keys.
How can Alice have confidentiality, integrity and nonrepudiation using a
public key cryptosystem? There are two natural strategies which Alice might
use to accomplish this, that is, she can sign the message M and then encrypt
the result before sending it to Bob or she can encrypt M and then sign the
result before sending it to Bob.
Using scenarios found in [142], we will show that both of these strategies
have potential pitfalls. First, suppose that Alice and Bob are romantically
PUBLIC K E Y SYSTEMS
306
involved. Alice decides to send the message
Af = “I love you”
to Bob. Using sign and encrypt, she sends Bob
Not long after, Alice and Bob have an argument and Bob, in an act of spite,
decrypts the signed message to obtain [I\/!]Alice and reencrypts it as
before sending it on to Charlie. Upon reading the message, Charlie thinks
that Alice is in love with him. causing great embarrassment for both Alice
arid Charlie.
Having learned her lesson, Alice vows to never sign and encrypt again.
Instead, she will encrypt and then sign. Some time later, after Alice and Bob
have resolved their earlier dispute, Alice discovers a solution to a difficult
math problem arid she wants to inform Bob. This time, her message is
= “Factoring is easy arid I have assuredly found an admirable
algorithm, but the margin is too narrow to contain it.”
which she then encrypts and signs
before sending to Bob.
However, Charlie, who is still angry with both Alice and Bob, has set
himself u p as a maninthemiddle arid he is able to intercept all traffic be
tween Alice and Bob. Charlie uses Alice™s public key to compute { M ) B ˜ ˜ ,
which he then signs
[{h4}Bob] Charlie
antl sends to Bob. When Bob receives the message, he verifies Charlie™s
signature and assumes that Charlie has made this astounding discovery. Bob
immediately promotes Charlie. Note that in this scenario Charlie cannot read
t)he message, but, regardless of the message; he can at least cause confusion.
In the first scenario, Charlie can be certain that Alice signed the message.
However, Charlie does not know who encrypted the message (since encryption
is a public key operation) arid he cannot, know whether or not he was the
int,ended recipient of the original message.
In the second scenario, Bob can be certain that Charlie signed the mes
sage. However, this does not imply that Charlie encrypted the message (since
6.8 ELGAMALSIGNATURESCHEME 307
encryption is a public key operation), or even that Charlie knows the content
of the message.
In both of these scenarios, the public key operations were exploited, which
illustrates a fundamental issue in public key cryptography, namely, that any
one can encrypt a message and anyone can verify a signature. The underlying
problem in both scenarios is that the recipient is making assumptions about
digital signatures that are not valid.
Now, let us examine the ElGamal signature scheme [44]. As with Diffie
Hellman, the security of ElGamal rests on the presumed intractability of the
discrete logarithm problem.
Suppose that Alice wants to create a digital signature to protect the in
tegrity of messages that she sends to Bob. To generate her private and public
keys, Alice chooses a large prime p and a base s, where 2 5 s 5 p  2.
She then chooses a private key a , where 2 5 a 5 p  2, and she com
putes a = sa (mod p ) . Alice makes the triple ( p , s, a ) public.
Now suppose that Alice wants to sign a message A 4 E (0, 1, . . . , p  l}. She
first selects a random session key k , with 1 5 k 5 p  2 and gcd(k,p 1) = 1.
Alice then uses k to compute
sk (mod p ) and t ˜ a (mod ( p  1)).
)
kl(A4
= =
T 
The signed message consists of the triple ( M ,T , t ) ,which Alice sends to Bob.
When Bob receives (Ad,, t ) ,he checks to see whether 1 5 T 5 p1. If not,
T
the signature is rejected. If this test is passed, Bob computes v = s M (mod p )
and w = a . rt (mod p ) . If v = w (mod p ) , the signed message is accepted
'
and otherwise it is rejected.
Why does the ElGamal signature scheme work? Is this scheme secure?
To answer the first question, suppose that Alice signs the message ( M , r , t )
as described above. Then we have v = U J (mod p ) , where
= sM (mod p ) and 7u = a ' . rt (mod p ) ,
'u
which follows from
w = a . rt (mod p ) = (s")'(sk)' (mod p )
'
s r a . Skkp'(n/lra)

(mod P )
= s M (mod p )
= v (mod p ) .
If the attacker Trudy is able to compute discrete logarithms efficiently,
then she would be able to recover Alice's private key a from 0 . In order for
Trudy to forge Alice's signature on a message M , she would need to find
elements T and t such that sM = aT.rt. It is not known whether this problem
is equivalent to the computation of discrete logarithms. However, no efficient
algorithm for this problem is known.
PUBLIC K E Y SYSTEMS
308
Mathematical Issues
6.8.1
As in the RSA cryptosystem, some care needs to be taken when using the
ElGamal signature scheme. We now give an overview of some niathematical
issues that arise with ElGamal.
If all of the prime factors of p  1 are small, then t,here is an efficient
algorithm for computing discrete logarithms [83]. Consequently, at least one
of the prime factors of p  1 must be “large.”
Alice should use a “good” random number generator to create k . If Trudy
is able to guess k for a signed message (M, ) ?then she is able to com
T,t
pute T U = M  k t (mod ( p  1)). Since it is very likely that gcd(r,p 1) = 1,
Trudy can then readily obtain Alice™s secret key a (see Problem 3 2 ) .
Alice must use a different session key k for each signed message. To see
why this is the case, suppose Alice uses k to sign messages M and M˜, where
izf # M™. Then Trudy can compute t  t™ = k  ™ ( M  M™) (mod ( p  1)) and,
t,hereby obtain k , since
t™)™ (mod ( p  1)).
Af™)(t
(AT
k =  ˜
Orice Trudy has k , she can obtain Alice™s secret key a (see Problem 3 3 ) .
As with most other signahre schemes, Alice should hash her message
and sign the hashed value. This is not) just a matter of efficiency˜p˜if Alice
signs the message instead of its hash, Trudy can forge Alice™s signature on a
message (see Problem 31). That is, Trudy can construct a message h and f
valid signature ( M ,˜ , t ) To accomplish this, Trudy first chooses b and c,
.
where gcd(c,p  1) = 1. She then sets T = sbaC(mod p ) and computes the
value t = ?.cl (mod ( p  1)). Finally, M = rbc™ (mod ( p  1)) yields a
valid signed message (Aff?T , t ), since
a . rt (mod p )
˜ (s”)˜ . ( ˜ ˜ a “ ) (mod ˜ )˜
˜˜˜p
=
= (s(LI˜) . ,™pc)rc™
(mod P )
™ )(s (mod p )
( )
brc
(pr)
˜
r bc

(mod P )
 ˜
A1
(mod p ) .
=s
ElGamal Signature Conclusion
6.8.2
Since its invention, the ElGamal signature scheme has generated continued
interest within the cryptologic community. Research on the cryptosystem,
as well as realworld usage of ElGamal, continue to this day. In addition,
the ideas underlying ElGamal form the basis of other important signature
schemes such as the Digital Signature Standard (DSS) and the Schnorr sig
nature schcme.
6.9 SUMMARY 309
Summary
6.9
In this chapter, we briefly considered seven public key cryptosystems. The
MerkleeHellman knapsack provides a nice introduction to public key cryptog
raphy. After giving an overview of this cryptosystem, we presented Shamir™s
ingeniuous latticereduction attack on the knapsack. This attack clearly
shows that the MerkleHellman knapsack is insecure and it also highlights
the difficulty of finding secure trap door oneway functions for use in public
key cryptography.
The DiffieHellman key exchange was then examined, along with a man
inthemiddle attack on the system. Our overview of the recently introduced
Arithmetica key exchange illustrates the role of sophisticated mathematics in
the design of public key cryptosystems. We also briefly described the heuristic
(and probabilistic) length attack of Hughes and Tannenbaum on Arithmetica.
The de facto standard in public key cryptography, RSA, was presented.
A few mathematical issues related to RSA were considered. The important
practical issue of implementation attacks on RSA is discussed in some detail
in Chapter 7.
The Rabin cryptosystem and an easily thwarted chosen ciphertext attack
were discussed. The Rabin cipher is at least as secure as RSA, since breaking
Rabin is mathematically equivalent to solving the factoring problem, and this
is not known to be the case for RSA.
We then consider the NTRU cipher and we mentioned several attacks on
it. Lastly, the ElGamal signature scheme was studied and some implementa
tion issues were discussed.
Problems
6.10
1. Suppose that the published DiffieHellman prime and generator are
given by p = 37 and g = 6, respectively. If Alice sends Bob the num
ber c = 36 and Bob sends p = 31 to Alice, find the key on which they
t
agreed. What makes the recovery of this key so easy? From Alice and
Bob™s viewpoint, what would be a better choice of 9?
2. In the DiffieHellman key exchange, g is chosen so that 2 5 g 5 p 2.

Why is g = p 1 not a good choice?

3. In the text we mentioned that digital signatures can be used to prevent
the maninthemiddle attack on DiffieHellman. Suppose that Alice
and Bob already share a symmetric key K before they begin the Diffie
Hellman procedure. Draw a diagram to illustrate a simple method Alice
and Bob can use to prevent a maninthemiddle attack.
PUBLIC K E Y S Y S T E M S
3 to
4. Suppose that Alice and Bob each have a publicprivate key pair, and
Alice and Bob encrypt all communications to and from each other.
Trudy records all encrypted messages between Alice and Bob. Later,
Trudy breaks into Alice and Bob's computers and steals Alice's private
key and Bob's private key. If Trudy cannot decrypt the messages that
she previously recorded: we say that Alice and Bob have perfect forward
secrecy (PFS). Explain how Alice and Bob can use DiffieHellman to
attain perfect forward secrecy. Hint: Use an ephemeral DifieHellman
cxchangc, where Alice forgets her secret, exponent a after she no longer
needs it and Bob forgets his secret, exponent b after he no longer needs
it. You must also prevent a maninthemiddle attack.
5. Suppose that Alice and Bob share a 4digit PIN,. Consider the authen
t,ication protocol below, where RA is ;L random challenge, (or nonce)
selected by Alice, and Rg is a random challenge selected by Bob. The
PIN) , which is sent in message two and is
response is h( "Bob", R A ,
intended to authenticate Bob to Alice, since the creator of the message
must know the PIN, and the nonce RAprevents a replay attack. Sinii
larly, message three is intended to authenticate Alice to Bob. However,
if Trudy observes, say, the first two messages, she can do an offline PIN
cracking attack. That is, Trudy can simply try each possible 4digit PIN
and easily determine Alice and Bob's shared PIN.