Security of RSA

From the contagion of the worldā™s slow stain, he is secure, and can never

mourn, a heart grown cold, a head grown grey in vain.

Percy Bysshe Shelley (1792ā“1822) English poet

6.1 Implementation Attacks

In Exercise 3.44 on page 76, we demonstrated one glaring misuse of the

RSA cipher, namely the use of a common modulus, which leads to a common

modulus protocol failure.6.1 This is not a weakness of RSA, but rather an

exceptionally bad implementation of the cipher. We saw in the aforementioned

exercise that Eve could retrieve the plaintext without either knowledge of a

decryption exponent or having to factor n. What this demonstrates is that

an RSA modulus should never be used by more than one entity. It cannot

be emphasized forcefully enough that true security for the RSA cryptosystem

requires a secure implementation. Without this, any other measures taken,

such as using a 1024-bit private key, as suggested in the discussion on page 74,

will do nothing to overcome the bad implementation. However, there was one

implementation attack, the discovery of which was somewhat troubling.

In 1995, a Stanford undergraduate named Paul Kocher [120] discovered that

he could cryptanalyze RSA and recover the decryption exponent by a careful

timing of the computation times for a sequence of decryptions. This weakness

was a surprising and unexpected discovery since the cryptographic community

felt that the nearly two-decades-old, time-tested cryptosystem was well under-

stood. It turns out, as we shall see, that there are means of thwarting the attack,

but it was disturbing nevertheless. Perhaps the lesson to be learned is never to

be overconļ¬dent, and always be vigilant. Even the discovery of more eļ¬cient

algorithms, such as the number ļ¬eld sieve discussed in Section 5.5, lay waste to

the claims made in the heady heydays of the discovery of RSA in 1977. In Mar-

tin Gardinerā™s Scientiļ¬c American article [93] in that year, it was touted that to

6.1 The common modulus attack, as it is often called, is attributed ļ¬rst to Simmons [212] and

(for a later contribution) to DeLaurentis [67].

111

Ā© 2003 by CRC Press LLC

112 6. Security of RSA

factor the RSA-129 challenge number (at that time) with the fastest computers

and most eļ¬cient algorithms would take several times longer than the life of

the known universe. Yet in 1994, after only eight months of computation, if was

indeed factored (see Footnote 3.7 on page 63). New mathematical discoveries

of eļ¬cient algorithms perhaps pose the greatest challenge. Indeed, Gardiner

stated in his article that āRivest and his associates have no proof that at some

future time no one will discover a fast algorithm for factoring composites as

large as ... [but] they consider the possibility extremely remote.ā

For the following, the reader will need to engage in solving Exercise 6.1 in

order to be familiar with notation and some elementary facts from probability

theory. Moreover, we must review the repeated squaring method on page 50

since we will be referring directly to it. For the convenience of the reader and

to alter notation to ļ¬t the algorithm below, we re-present the repeated squaring

method here.

x The Repeated Squaring Method Revisited

k

Given n ā N and d = j=0 dj 2j , dj ā {0, 1}, the goal is to ļ¬nd xd (mod n).

Set x0 = x, c0 = 1, j = 0, and execute the following steps.

(1) If dj = 1, then set cj ā” xj Ā· x (mod n).

(2) If dj = 0, then set cj ā” xj (mod n).

(3) Compute xj+1 ā” c2 (mod n).

j

(4) Reset j to j + 1. If j = k + 1, then terminate the algorithm with

ck ā” xd (mod n).

Otherwise, go to step (1).

x Timing Attack

We assume that Eve knows the hardware, such as a smart card or computer,

being used. Moreover, suppose that, prior to her attack, Eve has measured the

time values that it takes the hardware to compute xd in the repeated squaring

i

method for some large number r of ciphertexts xi . Eve wants to obtain the

RSA decryption exponent d, and she knows the RSA modulus n. Since Eve

knows that d is odd, she already has d0 = 1. Suppose that she has obtained

d0 , d1 , . . . , d ā’1 for some ā N. Since Eve knows the hardware, she therefore

knows the time ti (for each xi ) that it takes the hardware to compute c , . . . , ck in

the above repeated squaring method. She now wants to determine d . If d = 1,

then the multiplication x Ā· x (mod n) is calculated for each ciphertext xi , and

Eve knows that this takes time qi , say. However, if d = 0, this multiplication

does not take place. Now suppose it takes time si for the computer to complete

the calculation after the multiplication. Then by Exercise 6.1, if d = 1,

var({ti }r ) = var({qi }r ) + var({si }r ) > var({si }r ), (6.1)

i=1 i=1 i=1 i=1

Ā© 2003 by CRC Press LLC

6.1. Implementation Attacks 113

and if d = 0, then this fails to hold. Hence, Eve can determine d , and similarly

dj for each j > . This simple observation allows for Eve to ļ¬nd d without having

to factor n.

To summarize: the attack essentially consists of simulating the computation

to some point, then building a decision criterion (6.1), with only one correct

interpretation possible, depending on the selected value, and ļ¬nally deciding

the bit value by observing whether (6.1) holds or not. This attack is most

eļ¬ective against smart cards and such devices where timing measurements can

be obtained precisely.

So how do we defend against Eveā™s clever intrusion using Kocherā™s idea?

There are two basic methods for defence against Kocherā™s timing attack. The

simplest is to ensure that the modular exponentiation being used always takes

a ļ¬xed amount of time. This may be accomplished by adding a suitable delay

factor in each operation. The second method of defence is attributable to Rivest

(see Footnote 3.2 on page 61). The method is called blinding. Suppose that b is

the ciphertext and e is the RSA encryption exponent. Then prior to deciphering

b, a random r ā (Z/nZ)ā— is chosen and b = b Ā· re (mod n) is computed, followed

by c ā” (b )d (mod n). Then the computer sets c = c Ā· rā’1 (mod n). By

so doing, the computer is exponentiating a random b with d that is totally

unknown to Eve, who cannot mount the attack as a result.

x Other Attacks and Implementation Security Issues

Kocher had another clever idea. It is called power cryptanalysis. By a

very careful measurement of the computerā™s power consumption during decryp-

tion, Eve could recover the secret key. This works since during multi-precision

multiplications the computerā™s power consumption is necessarily higher than it

would normally be. Hence, if Eve measures the length of these high consump-

tion episodes she can easily decide when the computer is performing one or two

multiplications, and this gives away the bits of d.

We conclude this section with a discussion of some randomness requirements

for proper security of RSA not often mentioned in the literature. In [38], it is

shown that implementing the RSA cryptosystem as described on page 62, which

we will call plain RSA (namely, without any preprocessing of plaintext message

units) is insecure. The authors show that for any RSA public key (n, e), given

ciphertext c ā” me (mod n), it is possible to recover the plaintext m in the time it

takes to compute 2m/2+1 modular exponentiations. Moreover, the attack they

present succeeds with 18% probability over choices of m ā {0, 1, . . . , n ā’ 1}.

(They have similar data for the ElGamal cryptosystem, which we will not discuss

here.)

Albeit simple, the attack displayed in [38] is powerful against plain RSA

thereby demonstrating that it is fundamentally insecure in that it does not sat-

isfy basic security requirements. One such requirement is semantic security,

which means that for a given public key (n, e) and ciphertext c, it should be

intractable to recover any information about the plaintext m (see [100] for de-

tails on semantically secure cryptosystems). One example of how plain RSA is

semantically insecure is that the Jacobi symbol (m/n) is easily computed from

Ā© 2003 by CRC Press LLC

114 6. Security of RSA

e

the ciphertext c, since ( n ) = ( m ) = ( m )e .

c

n n

There are methods for adding randomness to the enciphering stage in RSA

(see [19] for instance). In order to obtain a secure RSA cryptosystem from

a plain RSA cryptosystem, there should be an application of a preprocessing

function to the plaintext before enciphering. In [19], there are new standards

for āpaddingā plain RSA so that it is secure against certain chosen ciphertext

attacks (see Section 1.3). The attack against plain RSA given in [38] shows

that even though an m-bit key is used in plain RSA, the eļ¬ective security is

m/2 bits. Hence, it is essential that, before encryption, a preprocessing step be

implemented that uses the so-called Optimal Asymmetric Encryption Padding

(OAEP) (introduced in [19]) such as [183], a recent standard from RSA Labs.

(Also, see [145], [207] for some cautionary notes, as well as [35], [92] for some

new considerations.)

There are also methods required to make hybrid cryptosystems (see Section

3.4) secure. For instance, in [91] it is shown how to ensure a secure hybrid

cryptosystem. This is necessary since hybrid cryptosystem usage is insecure

in general, even if both asymmetric and symmetric encryption are themselves

secure. Also, in [186] there is a presentation of how to protect any one-way

cryptosystem from chosen-ciphertext attacks.

In the next section, we will be looking at attacks on low exponents for RSA.

These attacks break RSA completely in some cases.

Exercises

6.1. Let R be a randomized algorithm (see page 205) that produces t ā R as

output where t is the amount of time it takes for the computer to complete

a calculation for a given input. We record the outputs t1 , t2 , . . . , tr for

given inputs and compute the mean (average, or the expected value)

r

1

m= tj .

r j=1

The variance of the {tj } is deļ¬ned to be:

r

1

var({tj }r ) (tj ā’ m)2 ,

=

j=1

r j=1

var({tj }r ).6.2 Prove that for another

and the standard deviation is j=1

set of outputs s1 , s2 , . . . , sr ,

var({sj }r ) + var({tj }r ) = var({sj }r + {tj }r ).

j=1 j=1 j=1 j=1

Calculate the variance and standard deviation of {sj }r = {4, 4, 4, 4} and

j=1

{tj }r = {5, 10, 50, 100}.

j=1

6.2 In statistics and probability these terms are used to determine āpopulation varianceā

for a sample of a variate having a distribution with a known mean, and the shortened term

āvarianceā is used when there is no confusion with what is called the āsample varianceā.

Ā© 2003 by CRC Press LLC

6.2. Exponent Attacks 115

6.2 Exponent Attacks

Philosophy is written in that great book which ever lies before our eyes ā”

I mean the universe ... This book is written in mathematical language ....

Galileo Galilei (1564ā“1642) Italian astronomer and physicist

In this section, we look at attacks based upon the choice of low encryption

and decryption exponents. We begin with the encryption exponent case.

x Low Public RSA Exponent

In order to make encryption more eļ¬cient, one can use a small public expo-

nent e. By Exercise 6.2, the smallest possible value, and one commonly used, is

e = 3, which requires only one modular multiplication and one modular squar-

ing. However, Exercise 6.3 shows us that sending the same message, that ļ¬ts into

a single block, to three diļ¬erent entities allows recovery of the plaintext. This

can be avoided by use of another recommended exponent e = 216 + 1 = 65537,

because (65537)10 = (10000000000000001)2 , so encryption using the repeated

squaring method (revisited in Section 6.1) needs only 16 modular squarings and

1 modular exponentiation; and here to recover the plaintext by the method

of Exercise 6.4 would require sending the same message to 216 + 1 entities, not

likely to occur. In any case, the method of attack in Exercise 6.4 can be thwarted

by appending a randomly generated bitstring of suitable length to the plaintext

message prior to encryption, a practice called salting the message, since we alter

the ātasteā of the message. The term padding is also commonly used. More-

over, the random bitstring should be independently generated for each separate

encryption. Notice that we are suggesting a preprocessing stage that is analo-

gous to that delineated in Section 6.1 for the implementation attacks discussed

therein.

There are more serious attacks on small public RSA exponents that even

work against salted messages. One of the most serious is the following introduced

by Coppersmith in 1996 (see [61]ā“[62]). We refer the reader to [61] for a proof of

the following since it is beyond the scope of this text. For the interested reader,

the following is based upon the so-called LLL lattice based reduction algorithm

(see [143]).

Theorem 6.2 (Coppersmith)

If n ā N is composite, f (x) = ad xd + adā’1 xdā’1 + Ā· Ā· Ā· + a0 ā Z[x], d ā N, and

there exists an integer x0 such that f (x0 ) ā” 0 (mod n) with |x0 | < n1/d , then x0

can be computed in time that is polynomial in d and ln(n).

Theorem 6.2 provides an eļ¬cient algorithm for ļ¬nding all roots x0 of f

modulo n when x0 < x = n1/d . As x decreases so does the running time

of the algorithm. Notice that n is assumed to be composite since there exist

much better algorithms for ļ¬nding roots modulo a prime than the result in

Theorem 6.2. In view of Coppersmithā™s attack, there is motivation to use large

random public encryption keys. In [140], the authors state that āValues such

Ā© 2003 by CRC Press LLC

116 6. Security of RSA

as 3 and 17 can no longer be recommended, but commonly used values such as

216 + 1 = 65, 537 still seem to be ļ¬ne. If one prefers to stay on the safe side

one may select an odd 32-bit or 64-bit public exponent at random.ā Moreover,

the authors of [41] provide evidence that breaking low exponent RSA cannot be

equivalent to factoring. Even though we still do not have a proof that breaking

RSA is equivalent to factoring the RSA modulus, this should give us pause.

One important application of Theorem 6.2 is a generalization of the notion

given in Exercise 6.4 and ļ¬rst introduced by Hastad [107]. Although the attack

in the exercise can seemingly be thwarted by padding the message, Hastad

showed that certain types of padding are insecure. Now we present a stronger

version of Hastadā™s method proved in [34].

Theorem 6.3 (Strong Hastad Broadcast Attack)

Let n1 , . . . , nr ā N be pairwise relatively prime with n1 ā¤ nj for all j =

1, . . . , r, and let fj (x) ā (Z/nj Z)[x] with the maximum degree of fj (for j =

1, . . . , r) being . If there exists a unique m < n1 such that fj (m) ā” 0 (mod nj )

for all j = 1, . . . , r and r > , then m can be eļ¬ciently calculated.

Example 6.4 Suppose that Alice is communicating with entities B1 , B2 , . . . , Br

and she has RSA encryption exponent e < r. She wishes to send the same

message m to each of them. First she pads m for each recipient Bj as

fj (m) = 2t j + m

where t is the bitlength of m. Then she sends

fj (m) ā” (2t j + m)e (mod nj ) for j = 1, 2, . . . , r.

e

If Eve intercepts more than e of these she can retrieve m via Theorem 6.3.

Example 6.4 is an instance where the messages are linearly related, and this

is a special case of Hastadā™s demonstration that, in fact, any ļ¬xed polynomial

applied as padding is insecure. Therefore, a proper means of defending against

the broadcast attack is to pad with a randomized polynomial, not a ļ¬xed one.

There are also naive random padding algorithms that can be cryptanalyzed

via another attack by Coppersmith. Letā™s discuss how this is done. To under-

stand the basic scenario, we enlist Alice, Bob, and Mallory once again. Alice

pads a message m that she wants to send to Bob, then enciphers it and trans-

mits it. However, malicious Mallory intercepts the message and prevents it from

reaching Bob (a man-in-the-middle attack, see page 27). Yet when Bob does

not respond to her message, she decides to randomly pad m again, encrypts

it and sends it to Bob. Now Mallory intercepts the second message and has

two diļ¬erent encipherments of m using diļ¬erent random pads. The following

theorem describes how Mallory can recover m.

Ā© 2003 by CRC Press LLC

6.2. Exponent Attacks 117

Theorem 6.5 (Coppersmithā™s Short Pad Attack)

Let n be an N -bit RSA modulus with public enciphering key e, and set =

N/e2 . Suppose that m ā (Z/nZ)ā— is a plaintext message unit of bitlength at

most N ā’ , and set m1 = 2 m + r1 and m2 = 2 m + r2 with r1 , r2 ā Z, r1 = r2 ,

0 ā¤ r1 , r2 < 2 . Then with knowledge of n, e, m1 , m2 (but not r1 or r2 ) m can

be eļ¬ciently recovered.

ā·

Proof. See [60].

Remark 6.6 When e = 3, the attack can be mounted if Alice sends messages

with pads of maximum bitlength less than 1/9-th that of the message length,

since in that case, if the message length is M , r1 , r2 < 2M/9 < 2N/9 = 2 . It

can also be seen that the above attack could not be mounted if e = 65337 is

chosen.

Letā™s have a look at an illustration of the attack and how it is manifested.

Example 6.7 Suppose we are given RSA enciphering exponent e = 3, RSA

modulus n, a plaintext message m and a pad r. If we set M = 2 m, we may

consider the simple situation where Alice sends:

M 3 ā” c1 (mod n) and (M + r)3 ā” c2 (mod n),

(since if m1 = M +r1 and m2 = M +r2 , then we may rewrite m2 = m1 +r2 ā’r1 ).

By using resultants6.3 (about which we need not concern ourselves here except

to note that the following can be done), Eve can eliminate M as a variable and

be left with

r9 + 3(c1 ā’ c2 )r6 + 3(c2 + 7c1 c2 + c2 )r3 + (c1 ā’ c2 ) ā” 0 (mod n),

2 1

so as long as the pad r satisļ¬es |r| ā¤ n1/9 , she can recover r by using Theorem

6.2. But how does this allow her to recover m? Essentially the method is due to

Coppersmithā™s generalization of a result by Franklin and Reiter (see [62]). To

see how this is done, we calculate g = gcd(x3 ā’ c1 , (x + r)3 ā’ c2 ) in Z/nZ[x]

using the Euclidean algorithm.6.4 It is clear that x ā’ m divides g. Moreover,

since gcd(3, Ļ(n)) = 1 (given that e = 3 is the RSA public exponent) then x3 ā’c1

cannot factor into 3 linear terms in Z/nZ[x], so x3 ā’ c1 = (x ā’ m)q(x) where

q(x) is an irreducible quadratic. Hence, since it can be shown that g is linear,

g = x ā’ m and we have recovered M from which we get m. (See [90] for e = 3.)

The following attack involves a low public key e and knowledge of some of

the bits of d. Suppose that Eve somehow recovers a fraction of the bits of d.

Then via the following theorem, she can recover all of d, thereby rendering a

total break of the RSA cryptosystem.

6.3 For the reader interested in the details surrounding resultants and the matrix theoretic

connections, see [131, p. 360].

6.4 For the most attentive reader, we note that although Z/nZ[x] is not a Euclidean ring, if

the Euclidean algorithm fails then we get a nontrivial factor of n, so Eve wins out in any case.

Ā© 2003 by CRC Press LLC

118 6. Security of RSA

Theorem 6.8 (Coppersmithā™s Partial Key Exposure Attack)

If n = pq is an RSA modulus of bitlength , then given either the /4 least

signiļ¬cant bits of p or the /4 most signiļ¬cant bits of p, n can be factored

eļ¬ciently.

ā·

Proof. See [61].

Another way of stating Theorem 6.8, is that for a given n = pq and an

estimate x for p such that |x ā’ p| ā¤ n1/4 , then p and q can be computed in

polynomial time (actually it can be shown to be computable in time that is

polynomial in ).6.5 This attack generalizes a key result given in [37], wherein

ā

they show that if e < n, then one can recover d from knowledge of a fraction of

its bits. The result in [37] is often called the partial key exposure attack, but we

retain the label given for Theorem 6.8 above since the result in [37] follows from

Coppersmithā™s result (see Exercise 6.11). This attack is actually a devastating

attack upon a variant of RSA given by Vanstone and Zucchereto in [231] where

high order bits of p and q are prescribed in advance. The lesson here is clear:

Safeguard all of the bits of d. In other words, keep the entirety of d secure.

x Low Secret RSA Exponent

Now we turn our attention to small secret RSA exponents. Again, as with

the reason for choosing small public exponents, we want increased eļ¬ciency in

the decryption process, so we choose small secret exponents. For instance, given

a 1024-bit RSA modulus, the decryption process can have eļ¬ciency increased

ten-fold with the choice of small d. However, Weiner [233] developed an attack

that yields a total break6.6 of the RSA cryptosystem.

Theorem 6.9 (Weinerā™s Attack)

If n = pq where p and q are primes such that q < p < 2q and d < n1/4 /3,

then given a public key e with ed ā” 1 (mod Ļ(n)), d can be eļ¬ciently calculated.

The manner in which Weiner proved this was to use the classical theory

of simple continued fractions (see page 223). The exact connection is given as

follows. If ed = 1 + kĻ(n) for some k ā N, then under the hypothesis of Theorem

6.9, k/d is a convergent in the simple continued fraction expansion of e/n.

Therefore, if the decryption exponent is small enough (as deļ¬ned in Theorem

6.9) a cryptanalyst can compute d via the elementary task of computing a

few convergents in the publicly known value e/n. Hence, we must conclude

that Weinerā™s attack leads to a total break of the RSA cryptosystem if small

decryption exponents are used. Therefore, use of small secret exponents to

gain eļ¬ciency has the result of a total loss of security. Boneh and Durfee [36]

improved Weinerā™s method by showing that the RSA cryptosystem is insecure

6.5 The reader may be interested to know that in 1907, D.N. Lehmer [134] proved the follow-

ing. If n = pq and |p ā’ q| < 2n1/4 , then n can be factored eļ¬ciently.

6.6 By a total break, we mean that a cryptanalyst can recover d, hence retrieve all plaintext

from ciphertext.

Ā© 2003 by CRC Press LLC

6.2. Exponent Attacks 119

for any d < n0.292 . They admit that their attack cannot be stated as a theorem

since they were unable to prove that it always succeeds but, on the other hand,

they could not ļ¬nd a single example where the attack failed.

Exercises

6.2. Show that e = 1, 2 as an RSA encryption exponent yields an insecure RSA

cipher.

6.3. Given RSA public enciphering modulus e = 3, show how a plaintext mes-

sage m can be recovered if it is enciphered and sent to three diļ¬erent

entities having pairwise relatively prime moduli ni with m < ni for each

for i = 1, 2, 3.

(Hint: Use the Chinese Remainder Theorem.)

6.4. Generalize Exercise 6.3 by showing that a plaintext m can be recovered

if e is the RSA enciphering exponent and m is sent to k ā„ e recipients

with pairwise relatively prime RSA moduli ni such that m < ni for i =

1, 2, . . . , k.

In Exercises 6.5ā“6.10, ļ¬nd the RSA decryption exponent d for each given

RSA modulus n and RSA encryption exponent e.

6.5. n = 3359 Ā· 1759 and e = 5.

6.6. n = 1979 Ā· 2281 and e = 7.

6.7. n = 4217 Ā· 4919 and e = 3.

6.8. n = 6373 Ā· 6761 and e = 7.

6.9. n = 7487 Ā· 7559 and e = 3.

6.10. n = 8443 Ā· 8861 and e = 11.

ā° 6.11. Suppose that we have an RSA modulus n and RSA encryption and de-

cryption exponents e and d. Then we know that there exists an integer m

such that

ed ā’ m(n ā’ p ā’ q + 1) = 1.

Assume that Eve knows n/4 of the least signiļ¬cant bits of d and that she

can ļ¬nd solutions to the quadratic congruence

mnp2 ā’ (mn + m + 1)p + mn ā” 0 (mod 2n/4 )

by having to check no more than

e log2 e

possible values for p. Show how Eve can eļ¬ciently factor n.

Ā© 2003 by CRC Press LLC

120 6. Security of RSA

6.3 Strong Moduli

Even if strength fail, boldness at least will deserve praise: in great endeavors

even to have had the will is enough.

Propertius (50ā“16 B.C.) Roman Poet

We have already seen how poor implementation and bad choices can lead to

an insecure RSA cryptosystem. Now we look at proper choices for RSA moduli.

Exercise 3.12 on page 59 shows how primes p and q being close together (in

the sense described therein) results in a means of factoring the modulus n = pq

using Fermatā™s diļ¬erence of squares method. Thus, one clearly bad choice is

such an RSA modulus.

To avoid the above, we can select p and q (not close together ā” see the

discussion following Gordonā™s algorithm below) such that (pā’1)/2 and (q ā’1)/2

are primes. Such p and q are called safe primes. Although it is assumed that

there are inļ¬nitely many safe primes, we have no proof of this suspicion.

x Algorithm for Generating (Probable) Safe Primes

Let b be the input bitlength of the required prime. Execute the following

steps.

(1) Select a (b ā’ 1)-bit odd random n ā N and a smoothness bound B (deter-

mined experimentally).

(2) Trial divide n by primes p ā¤ B. If n is divisible by any such p, go to step

(1). Otherwise, go to step (3).

(3) Use the Miller-Selfridge-Rabin test on page 87 to test n for primality. If

it declares that ā˜n is probably primeā™, then go to step (4). Otherwise, go

to step (1).

(4) Compute 2n + 1 = q and use the Miller-Selfridge-Rabin test on q. If it

declares q to be a probable prime, terminate the algorithm with q as a

ā˜probable safe primeā™. Otherwise go to step (1).

Since long-term security of RSA moduli require products of primes having

512 bits, we would initiate the above algorithm with b = 512. However, there are

primes that have even more constraints to ensure security of the RSA modulus.

They are given as follows.

Deļ¬nition 6.10 (Strong Primes)

A prime p is called a strong prime if each of the following hold.

(1) p ā’ 1 has a large prime factor q.

(2) p + 1 has a large prime factor r.

(3) q ā’ 1 has a large prime factor s.

Ā© 2003 by CRC Press LLC

6.3. Strong Moduli 121

The following algorithm was initiated in [102].

x Gordonā™s Algorithm for Generating (Probable) Strong Primes

(1) Generate two large (probable) primes r = s of roughly equal bitlength

using the Miller-Selfridge-Rabin test on page 87.

(2) Select the ļ¬rst prime in the sequence {2js + 1}jāN , and let

q = 2js + 1

be that prime.

(3) Compute p0 ā” rqā’1 ā’ q rā’1 (mod rq).

(4) Find the ļ¬rst prime in the sequence {p0 + 2iqr}iāN , and let

p = p0 + 2iqr

be that prime, which is a strong prime (see Exercise 6.16).

If one wants p to be a safe prime as well as a strong prime, this can be

done by the methods in [241], but the algorithm therein is not as eļ¬cient as

Gordonā™s algorithm above. We see that an RSA modulus consisting of two strong

primes is not susceptible to the p ā’ 1 or p + 1 factoring methods discussed in

Section 5.2 on page 96. In general, having strong primes in the modulus makes

it more diļ¬cult to factor, but also harder to ļ¬nd such primes. Also, the reader

should be aware that the deļ¬nition of strong prime is not consistent throughout

the literature. There are some more minimal versions than the one we gave in

Deļ¬nition 6.10. Nevertheless, we may be fairly certain that under our deļ¬nition,

if the primes are chosen to be strong and large enough, the RSA cryptosystem is

not susceptible to a direct factorization attack. Even the number ļ¬eld sieve that

we studied in Section 5.5 on page 108 will not threaten the RSA cryptosystem if

we choose the primes large enough. The new device, called Twinkle,6.7 designed

by Shamir to run the number ļ¬eld on general purpose computers (by a factor of

as much as 1000 times faster) will not qualitatively change this since the factor

of 1000 can be retrieved by choosing a larger modulus. That is the essence of

the discussion, since even those who hold the opinion that having strong primes

in the modulus make that modulus no harder to factor than one with āweakerā

primes, agree that choosing random primes ālarge enoughā will thwart direct

factoring techniques.

In [203], Shamir proposed an new variant of RSA which is called unbalanced

RSA. In this version, we may choose the RSA modulus n = pq such that p is

much larger than q and we lose no eļ¬ciency. For instance, p could be a 5000-bit

6.7 This is an acronym for The Weizmann INstitute Key Locating Engine, which is an

electro-optical sieving device that is capable of executing sieve-based factoring algorithms,

such as the GNFS, up to three orders of magnitude faster than on a conventional computer.

(http://www.datastreamconsulting.com/RSAdocs/bulletn12.pdf)

Ā© 2003 by CRC Press LLC

122 6. Security of RSA

prime and q could be a 500-bit prime. Such primes put the RSA modulus far

away from any known factoring attack. To decrypt

c ā” me (mod n),

we compute

m ā” cd (mod q) where d ā” d (mod q ā’ 1).

Then for 0 ā¤ m < q, we must have m = m. Hence, decryption in the unbal-

anced version of RSA involves one exponentiation modulo a 500-bit prime, so

we have the same eļ¬ciency as that obtained with regular RSA having a 500-bit

modulus.

We conclude this section with a discussion of an attack on RSA which will

answer a question in the mind of the most attentive reader: If the reason for

(1)ā“(2) in Deļ¬nition 6.10 is to thwart the p Ā± 1 factoring methods, what is the

reason for (3)? The reader may prepare for the following by solving Exercise

6.18, which is a special case of the following, and we will need that exercise in

its description.

x Cycling Attack on RSA

Let n = pq be an RSA modulus and let e be the encryption exponent, so

that c ā” me (mod n) is the enciphering function. Suppose that t ā N is the

smallest value such that

t

g = gcd(ce ā’ c, n) > 1.

t

If exactly one of p or q divides (ce ā’ c), say, p, then g = p and we have factored

t

n. If both p and q divide (ce ā’ c), then g = n and we are in the situation in

Exercise 6.18, namely, we can retrieve m. Such an attack on RSA is called a

cycling attack.

It is most often the case that the factorization of n will occur with a cycling

attack than that we ļ¬nd m. Therefore, the cycling attack is typically viewed as

an algorithm for factoring n. Since we have already seen that this is infeasible

for a properly chosen RSA modulus, then this does not present a serious threat.

However, it does explain why (3) is part of Deļ¬nition 6.10, namely, to thwart

the cycling attack. Although it is true that a randomly chosen pair of large

primes for an RSA modulus will result in only a negligible chance of the cycling

attack succeeding, we should still choose strong primes since they are at least as

secure as random primes and it takes only an insigniļ¬cant amount of additional

time to compute them, as compared to using random primes. Thus, there is

no good reason or signiļ¬cant savings in not using them. The bottom line in all

this is that, as we have seen throughout the text, we cannot be certain of what

mathematical algorithms will be developed in the future, so choosing strong

primes may help to thwart those attacks, and is one more deposit in our bank

account for security of RSA.

Ā© 2003 by CRC Press LLC

6.3. Strong Moduli 123

Exercises

6.12. Given n ā N, prove that the following are equivalent.

(a) an ā” a (mod n) for all a ā Z.

(b) anā’1 ā” 1 (mod n) for all a ā Z such that gcd(a, n) = 1.

(c) n is squarefree and (p ā’ 1) (n ā’ 1) for all primes p dividing n.

(These equivalent conditions are known as Korseltā™s criterion discovered

in 1899 (but implicit in Gaussā™s [95, Article 92, pp. 60ā“61]). Compare

with Deļ¬nition 4.3 on page 82.)

In what follows, let Ī»(n) be the Carmichael function deļ¬ned in Exercise 5.2

on page 95.

6.13. Prove that if n is squarefree, then

aĪ»(n)+1 ā” a (mod n),

for all a ā Z. Give a counterexample to the latter when n is not squarefree.

ā° 6.14. Given n ā N, a ā Z, prove that the following are equivalent.

(a) There exist s, t ā N such that atĪ»(n)+s ā” as (mod n).

(b) gcd(as+1 , n) as .

6.15. Let n = pq be an RSA modulus, (e, d) a public/private key pair, and

deļ¬ne a function f by

f (x) ā” xe (mod n), where ed ā” 1 (mod Ī»(n)).

Prove that f is a one-way function with d as trapdoor.

6.16. Prove that the prime p output by Gordonā™s algorithm is indeed a strong

prime.

6.17. Suppose that we obtain two strong primes p and q using Gordonā™s algo-

rithm on page 121. Also, we set

n = (p ā’ 1)(q ā’ 1)/4,

n = pq,

and choose a random integer e such that

(p ā’ 1) (e ā’ 1), (q ā’ 1) (e ā’ 1).

gcd(e, n ) = 1,

Show how to set up an RSA cryptosystem with public enciphering key e

and RSA modulus n.

6.18. Given an RSA modulus n and public enciphering exponent e, we encrypt

via the function f (m) ā” me ā” c (mod n). Show that there exists an ā N

such that ce ā” c (mod n), and prove that knowledge of can be used to

retrieve m.

Ā© 2003 by CRC Press LLC

124 6. Security of RSA

6.4 Generation of Random Primes

Truth, as light, manifests itself and darkness, thus truth is the standard of

itself and of error.

Baruch Spinoza (1632ā“1677) Dutch philosopher

Given the discussion at the end of Section 6.3, it is clearly important for

the security of RSA that we be able to generate large random primes eļ¬ciently.

This section is devoted to a discussion of methods for accomplishing this task.

For the ļ¬rst of our generation algorithms, we will use one of the probabilistic

primality testing algorithms discussed in Chapter 4.

x Large (Probable) Prime Generation

We let b be the input bitlength of the desired prime and let B be the input

smoothness bound (empirically determined). Execute the following steps.

(1) Randomly generate an odd b-bit integer n.

(2) Use trial division to test for divisibility of n by all odd primes no bigger

than B. If n is so divisible, go to step (1). Otherwise go to step (3).

(3) Use the Miller-Selfridge-Rabin (MSR) probabilistic primality test on page

87 to test n for primality. If it is declared to be a probable prime, then

output n as such. Otherwise, go to step (1).

There is a variant of the above test that injects a step after the MSR test

by invoking an elliptic curve primality proving algorithm (see Footnote 5.7 on

page 103 and [165, Theorem 6.30, p. 240]) namely, a deterministic primality

test in which case the output is called a provable prime. However, we have not

studied these elliptic curve primality proving algorithms herein, so we are going

to now describe a prime generating algorithm that produces provable primes

based upon the contents of Exercise 4.1 on page 83 ā” Pocklingtonā™s theorem

from 1914 (see [184]).

We ļ¬rst restate Pocklingtonā™s theorem here in a diļ¬erent format and nota-

tion.

Theorem 6.11 (Pocklingtonā™s Theorem)

Suppose that

n ā’ 1 = 2AB where A, B ā N with B > 2A.

If there exists a prime divisor p of B and an integer m > 1 such that both

mnā’1 ā” 1 (mod n),

and

gcd(m(nā’1)/p ā’ 1, n) = 1,

then n is a provable prime.

Ā© 2003 by CRC Press LLC

6.4. Generation of Random Primes 125

x Maurerā™s Large (Provable) Prime Generation (Brief Version)

The goal is to output a random large provable prime of a given required

bitlength.

(1) Randomly generate an odd integer B (for instance see Exercise 6.23).

(2) Select a random integer A < B.

(3) Test n = 2AB + 1 using Pocklingtonā™s Theorem 6.11. If n is prime, then

go to step (4). Otherwise go to step (2).

(4) If n is of the required bitlength, then output n as a provable prime.

Otherwise, set n = B and go to step (2).

The full version of the above may be found in [149], [151]. The running time

of Maurerā™s test is only slightly larger than that for the probable prime test

described before it. Of course, the larger the value of the required bitlength,

the faster the former will run over the latter, but the latter has provable security

attached to it that the former does not have.

The decision to use either of the above algorithms reduces to the deter-

mination of the size of the prime to be generated, how often the algorithm

is implemented, the computing facilities available, and the degree of security

sought. Today, with increasingly fast processors available, especially special-

purpose hardware for RSA (see [40]), the small amount of extra time needed

to output a provable vs. a probable prime is insigniļ¬cant in terms of taking

advantage of the power a provable prime ensures.

We now give an illustration (deliberately contrived) of Maurerā™s algorithm.

Example 6.12 Suppose that we want to generate a 35-bit random (provable)

prime. We randomly generate B = 168 and A = 3, so n = 2AB + 1 = 1009. By

choosing m = 2 and p = 3 we get 21008 ā” 1 (mod n) and gcd(21008/3 ā’ 1, n) = 1,

so n = 1009 is a provable prime. However, this is only a 10-bit prime since

1009 = (1111110001)2 . Thus we set n = B and go back to step (2). We

randomly select A = 146, so n = 2AB + 1 = 2 Ā· 146 Ā· 1009 + 1 = 294629 and

apply Theorem 6.11 with m = 3 and p = 2. Then

3nā’1 ā” 1 (mod n) and gcd(3(nā’1)/p ā’ 1, n) = 1,

so n = 294629 is a provable prime. However, n = (1000111111011100101)2 is

a 19-bit prime, so we set B = 294629 and go to step (2). We randomly select

A = 50415 and set n = 2AB + 1 = 2 Ā· 50415 Ā· 294629 + 1 = 29707442071. For

m = 2, and p = 294629 we get,

2nā’1 ā” 1 (mod n) and gcd(2(nā’1)/p ā’ 1, n) = 1,

so n = 29707442071 is a provable prime. Moreover,

n = (11011101010101100111001011110010111)2 ,

a 35-bit prime, so we are done. See Exercises 6.19ā“6.22.

Ā© 2003 by CRC Press LLC

126 6. Security of RSA

Maurerā™s algorithm makes repeated use of Pocklingtonā™s Theorem by res-

electing values of A and testing for successively larger prime values until the

desired bitlength is achieved and we have a provable prime of the required size.

There is yet another method similar to the above that uses Pocklingtonā™s

Theorem to generate large primes given by Ribenboim in [194], which the reader

may also ļ¬nd in [245]. Ribenboim gives evidence (in the absence of a proof)

that for producing primes of a given size the algorithm will run in polynomial

time. In any case, in public-key cryptography, we require eļ¬cient algorithms

for generating large, random primes as an indispensable tool.

Exercises

In Exercises 6.19ā“6.22, take the given values of A, B, m, p, and execute

Maurerā™s algorithm until the provable prime of given bitlength b is achieved.

6.19. A = 3, B = 51, m = 2, p = 17, and b = 9.

6.20. A = 7, B = 75, m = 2, p = 5, and b = 14.

6.21. A = 11, B = 105, m = 2, p = 5, and b = 12.

6.22. A = 11, B = 211, m = 2, p = 211, and b = 13.

6.23. Let n = pq be an RSA modulus. Randomly select a ā N such that

gcd(a, Ļ(n)) = 1 and choose a seed s0 ā N where 1 ā¤ s0 ā¤ n ā’ 1. Recur-

sively deļ¬ne

sj ā” sa (mod n), 1 ā¤ j < ,

jā’1

where is the least integer such that s +1 = sj for some natural number

j ā¤ . Then

f (s0 ) = (s1 , s2 , . . . , s )

is called the RSA pseudo-random number generator. The value is called

the period length of f and a is called the exponent.

(a) Prove that must exist.

(b) Find f when a = 3, s0 = 2, b = 0 and n = 561.

(c) ļ¬nd in (b).

(Bit generators such as the one above are generally called pseudorandom

bit-generators (PRBG). The RSA-PRBG is deemed to be cryptographically

secure since it too is based upon the intractability of the integer factoring

problem. A predecessor to it is the linear congruential generator, those of

the form sj ā” asjā’1 + b (mod n) (see [165]), discovered by D.H. Lehmer

in 1949 (see Footnote 4.3).)

Ā© 2003 by CRC Press LLC