Chapter 6

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