Cryptanalysis of Short RSA Secret Exponents

Michael J. Wiener
BNR
P.O. Box 3511 Station C
Ottawa, Ontario, Canada, K1Y 4H7

1989 August 3

Abstract. A cryptanalytic attack on the use of short RSA secret exponents is described.
This attack makes use of an algorithm based on continued fractions which finds the
numerator and denominator of a fraction in polynomial time when a close enough
estimate of the fraction is known. The public exponent e and the modulus pq can be used
to create an estimate of a fraction which involves the secret exponent d. The algorithm
based on continued fractions uses this estimate to discover sufficiently short secret
exponents. For a typical case where e < pq, GCD( p-1, q-1) is small, and p and q have
approximately the same number of bits, this attack will discover secret exponents with up
to approximately one-quarter as many bits as the modulus. Ways to combat this attack,
ways to improve it, and two open problems are described. This attack poses no threat to
the normal case of RSA where the secret exponent is approximately the same size as the
modulus. This is because this attack uses information provided by the public exponent
and, in the normal case, the public exponent can be chosen almost independently of the
modulus.

Key Words. RSA, cryptanalysis, continued fraction, short exponent.

1. Introduction

From the set of all key pairs for the RSA public-key cryptosystem [5], some key pairs have
properties which can be exploited by various cryptanalytic attacks. Some attacks exploit
weaknesses in the modulus, and others exploit weaknesses in the public exponent or the
secret exponent. The weaknesses discussed here are those which allow an attack on RSA
to be completed in a length of time which is polynomial in the length of the modulus.

Attacks on the RSA modulus are aimed at discovering the two prime factors (p and q) of
the modulus. One such attack can be used to factor the modulus when the prime factors of
either p-1 or q-1 are all small [3]. The modulus can also be factored when the prime factors
of either p+1 or q+1 are all small [6]. There is a simple algorithm for factoring the
modulus when the difference between the primes is only polynomially times larger than the
square root of either prime. This algorithm is based upon the following identity:
 2 2
( p+2 q ) - pq = ( p-q2 ) .

The modulus can be factored by finding (p+q)/2 and (p-q)/2. ((p+q)/2)2 can be found in a
linear search through the perfect squares starting from the modulus. The correct square is
found when the difference between the square and the modulus is itself a perfect square.

There are various attacks on RSA which require, among other conditions, either the public
or secret exponent to be short. In some cases it may be desirable to use a shorter public or
secret exponent because this reduces the encryption or decryption execution time. This is
because, for a fixed modulus size, the RSA encryption or decryption time is roughly
proportional to the number of bits in the exponent. One situation where the use of short
exponents is particularly advantageous is when there is a large difference in computing
power between two communicating devices. An example of this is when RSA is used in
communications between a smart card and a larger computer. In this case, it would be
desirable for the smart card to have a short secret exponent, and for the larger computer to
have a short public exponent in order to reduce the processing required in the smart card.
However, one must be wary of short exponent attacks on RSA.

Short public exponents can be exploited when the same message is broadcast to many
parties [1]. To illustrate this attack, suppose that a message m is broadcast to three parties
whose public exponents are e1 = e2 = e3 = 3 and whose moduli are n1, n2, and n3. The
encrypted messages are

m3 mod n1, m3 mod n2, and m3 mod n3.

Using the Chinese Remainder Theorem, one can find m3 mod n1n2n3. But, m3 < n1n2n3
because m < n1, n2, n3. Therefore, m3 is not affected by being reduced modulo n1n2n3,
and the message can be recovered by taking the cube root of m3.

In this paper, an attack on short secret exponents is described. This attack is based upon
continued fractions.

2. Continued Fractions Background

Continued fractions can be used to find the numerator and denominator of a fraction when a
close enough estimate of the fraction is known. This will be related to RSA in Section 4
where the public exponent and modulus will be used to construct an estimate of a fraction
involving the secret exponent.

The algorithm for using continued fractions to find the numerator and denominator of a
fraction given an estimate will be referred to here as the continued fraction algorithm. This
algorithm will be described in Section 3. A background in continued fractions for a
discussion of the continued fraction algorithm is presented in this section. Further
discussion of continued fractions can be found in [2].

2
A continued fraction is an expression of the form

a1
a2
q1 +
a3
q2 +
= a1/(q1 + a2/(q2 + a3/( ... /(qm-1 + am/qm) ... ))). (1)
...

am
qm-1 +
qm

We are interested in continued fractions which have all the a i's in (1) equal to 1. For
convenience, let us define

〈 q 0, q 1, ..., qm 〉 = q0 + 1/(q1 + 1/(q2 + 1/( ... /(qm-1 + 1/qm) ... ))). (2)

4
For example, 〈 0, 2, 1, 3 〉 = 0 + 1/(2 + 1/(1 + 1/3)) = .
11

〈 0, 2, 1, 3 〉 is called the continued fraction expansion of 4/11. The continued fraction

expansion of a positive rational number f is formed by subtracting away the integer part of f
and repeatedly inverting the remainder and subtracting away the integer part until the
remainder is zero. Let qi be the integer quotient and ri be the remainder at step i, and let m
be the number of inversion steps.

q0 =  f  , r0 = f - q 0, and

 
1 1
qi = , ri = -q for i = 1, 2, ..., m (3)
ri-1 ri-1 i

Because rm = 0, we have f = 〈 q0, q1, ..., qm 〉.

There are two observations which can be made at this point which will be useful later on.
The first is that q m ≥ 2. This is true because q m = 1 implies that r m-1 = 1 which is
impossible. The second is that for any x > 0,

〈 q 0 , q 1 , ..., q m 〉 < 〈 q 0, q 1, ..., q m-1, q m +x 〉 if m is even,

〈 q 0 , q 1 , ..., q m 〉 > 〈 q 0, q 1, ..., q m-1, q m +x 〉 if m is odd. (4)

This can be seen by looking at the number of levels of fraction nesting in (2).

3
We will now consider how one would go about reconstructing f from its continued fraction
expansion. Using equation (2), f can be reconstructed by starting from qm and adding and
inverting at each step back to q0. However, it is useful to be able to reconstruct f starting
from q 0. Let n i and d i, i = 0, 1, ..., m be a sequence of numerators and denominators
defined as follows:

ni
= 〈 q 0, q 1, ..., q i 〉, GCD(ni, di) = 1 for i = 0, 1, ..., m. (5)
di

It can be shown that

n0 = q 0 , d0 = 1,
n1 = q0q1 + 1, d1 = q 1 ,
ni = q in i-1 + n i-2, di = qidi-1 + di-2 for i = 2, 3, ..., m. (6)

nm
In this way, the fraction f = can be reconstructed.
dm

There is a relationship between the numerators and denominators which will be useful later
on. It can be shown that

nidi-1 - ni-1di = - (-1)i for i = 1, 2, ..., m. (7)

Sufficient background in continued fractions has been presented for a discussion of the
continued fraction algorithm.

3. Continued Fraction Algorithm

Let f' be an underestimate of f:

f' = f(1 - δ ) for some δ ≥ 0. (8)

Let qi, ri and qi', ri' be the ith quotients and remainders of f and f' respectively. If δ is
small enough, then the numerator and denominator of f can be found using the following
algorithm:

Repeat the following until f is found:

- Generate the next quotient (qi') of the continued fraction expansion of f'.
- Use (6) to construct the fraction equal to
〈 q 0 ', q 1 ', ..., q i-1 ', q i '+1 〉 if i is even,
〈 q 0 ', q 1 ', ..., q i-1 ', q i ' 〉 if i is odd.
- Check whether the constructed fraction is equal to f.

4
The reason for adding one to even quotient values is that the guess of f should be larger
then f', because f ≥ f', and it can be seen from (4) that 〈 q 0 ', q 1 ', ..., q i-1 ', q i' 〉 is less
than f' = 〈 q 0', q 1', ..., q i-1', q i'+ri' 〉. Note that a test must exist to determine whether a
guess of f is correct.

The continued fraction algorithm will succeed if

〈 q 0 , q 1 , ..., q m-1, q m -1 〉 < f' ≤ 〈 q 0 , q 1 , ..., q m 〉 if m is even,

〈 q 0 , q 1 , ..., q m-1, q m +1 〉 < f' ≤ 〈 q 0 , q 1 , ..., q m 〉 if m is odd. (9)

We will now consider the implications of (9) on the size of δ. Solving (8) for δ yields

f'
δ = 1 - . (10)
f

Separate analyses will be done for the following cases: m = 0, m = 1, m even and m ≥ 2,
and m odd and m ≥ 3.

Case 1: m = 0

Using (9) to substitute for f' in (10) yields

δ < 1 - 〈 q0 - 1 〉 / 〈 q0 〉 . (11)

Using (2), this reduces to δ < 1/q0 which can be rewritten as (recall that n0 = q0 and
d0 = 1)
1
δ < . (12)
n 0d 0

Case 2: m = 1

Using (9) to substitute for f' in (10) yields

δ < 1 - 〈 q0, q1+1 〉 / 〈 q0, q1 〉 . (13)

Using (2), this reduces to

1
δ < . (14)
(q0q1 + 1)(q1 + 1)

5
It was shown earlier that qm ≥ 2. This implies that for this case, (3/2)q1 ≥ q1+1.
Combining this with (14) and the expression for n1 and d1 in (6) yields the fact that

1
δ < (15)
3
n d
2 1 1

is sufficient to guarantee the success of the continued fraction algorithm.

Case 3: m even and m ≥ 2

Using (9) to substitute for f' in (10) yields

δ < 1 - 〈 q 0, q 1, ..., q m-1, q m -1 〉 / 〈 q 0, q 1, ..., q m 〉 . (16)

Using (6), we have

(qm - 1)nm-1 + nm-2
〈 q 0 , q 1 , ..., q m-1, q m -1 〉 = and
(qm - 1)dm-1 + dm-2

qmnm-1 + nm-2
〈 q 0 , q 1 , ..., q m 〉 = . (17)
qmdm-1 + dm-2

Substituting these expressions into (16) yields

nm-1dm-2 - nm-2dm-1
δ < . (18)
(qmnm-1 + nm-2)(qmdm-1 + dm-2 - dm-1)

Using (7) and the expressions for nm and dm in (6) yields

1
δ < . (19)
nm(dm - dm-1)

Therefore,
1
δ < (20)
nmdm

is sufficient to guarantee the success of the continued fraction algorithm.

6
 Case 4: m odd and m ≥ 3

Performing a similar analysis to the one done in case 3 yields

1
δ < . (21)
nm(dm + dm-1)

Because dm = qmdm-1 + dm-2 and qm ≥ 2, we have dm + dm-1 ≤ (3/2)dm. Therefore,

1
δ < (22)
3
n d
2 m m

is sufficient to guarantee the success of the continued fraction algorithm.

Taking into account the results of all four cases,

1
δ < (23)
3
n d
2 m m

is sufficient to guarantee the success of the continued fraction algorithm. Recall that nm and
dm are the numerator and denominator of f.

Let us now consider the execution time of this algorithm. Let x = max(n m , d m ). The
number of quotients in the continued fraction expansion of f can be shown to be O(log x).
For each quotient, a guess of f is generated and tested. The calculations required to
generate each guess of f is polynomial in log x. Therefore, assuming that the test of
whether the guess of f is correct is polynomial in log x, the continued fraction algorithm
execution time is polynomial in log x.

4. Continued Fraction Algorithm Applied to RSA

The following relationship between the public exponent e and the secret exponent d is given
in reference [5]:

ed ≡ 1 (mod LCM(p-1, q-1)) (24)

This relationship is necessary for exponentiation with the public exponent and secret
exponent to be inverses of each other. From (24), there must exist an integer K such that

7
 ed = K ⋅ LCM(p-1, q-1) + 1. (25)

If we let G = GCD(p-1, q-1) and use the fact that LCM(p-1, q-1) = (p-1)(q-1)/G, we get

K
ed = ( p-1)(q-1) + 1. (26)
G

It is possible for K and G to have common factors. Let us define k = K/GCD(K, G) and g
= G/GCD(K, G). Then k/g = K/G, and GCD(k, g) = 1. We now have

k
ed = ( p-1)(q-1) + 1. (27)
g

Dividing through by dpq in (27) gives

g
p+q-1-
e k k
= (1 - δ ), where δ = . (28)
pq dg pq

Note that e/pq consists entirely of public information and is a close underestimate of k/dg.
Before invoking the continued fraction algorithm, we must remember that this algorithm
always finds fractions in lowest terms. From (25), we see that GCD(K, d) = 1. Because k
divides K, we have GCD(k, d) = 1. Also, GCD(k, g) = 1 by definition. Therefore,
GCD(k, dg) = 1, and the continued fraction algorithm can be used to find k and dg as long
as δ is small enough.

Using the expression for δ in (28) and the restriction on δ in (23), it can be shown that

pq
kdg < (29)
3
(p + q)
2

is sufficient to allow k and dg to be found. Note that (-1 - g/k) in the expression for δ was
dropped because it is small compared to (p+q). This does not affect the validity of (29)
because (-1 - g/k) serves to reduce the size of δ.

We will now consider how one could test whether a guess of k and dg is correct. In order
to simplify this test, we will assume that ed > pq. This is not a particularly restrictive
assumption because when either e or d is fixed, the expected value of the other is
approximately pq/G (recall that G = GCD(p-1, q-1)). Unless G is chosen to be large, it is
very likely that ed > pq. From equation (27), a consequence of ed > pq is that k > g. By
rewriting equation (27) as

edg = k(p-1)(q-1) + g (30)

8
we see that dividing edg by k yields a quotient of (p-1)(q-1) and a remainder of g as long as
k > g. This provides a guess of (p-1)(q-1) and of g. If the guess of (p-1)(q-1) is zero,
then k and dg are wrong. This case must be filtered out at this point or else the remainder
of this test will succeed in factoring pq into 1 and pq. The guess of (p-1)(q-1) can be used
to create a guess of (p+q)/2 using the following identity:

pq - (p-1)(q-1) + 1 p+q
= . (31)
2 2

If the guess of (p+q)/2 is not an integer, then the guess of k and dg is wrong. The guess of
(p+q)/2 can be used to create a guess of ((p-q)/2)2 using the following identity:

p+ q 2 p-q 2
( )2
- pq = ( )2
. (32)

If the guess of ((p-q)/2)2 is a perfect square, then the original guess of k and dg is correct.
The secret exponent d can be found by dividing dg by g. Recall that g was the remainder
when edg was divided by k. We can also recover p and q easily from (p+q)/2 and (p-q)/2.

If nothing special is done to combat this continued fraction attack on RSA, then one can
expect g to be small, and k < dg. Under these conditions, we can see from (29) that secret
exponents with up to approximately one-quarter as many bits as the modulus can be found
in polynomial time. This attack cannot be extended to the normal case where the secret
exponent is approximately the same size as the modulus. This is because this attack relies
on the public exponent providing information to help factor the modulus and, in the normal
case, the public exponent can be chosen almost independently of the modulus.

5. An Example

In this section, the continued fraction algorithm will be applied to a small RSA key pair.
For this example,

pq = 8927 and e = 2621.

A continued fraction expansion will be performed on e/pq = 2621/8927:

9
Calculated Quantity How it is Derived i=0 i=1 i=2

q i' see (3) 0 3 2

2621 1064 493

r i' see (3)
8927 2621 1064

n i' 0 1 2
d i' see (6)
1 3 7
= 〈 q 0 ', q 1 ', ..., q i ' 〉

1 1 3
guess of k/dg 〈 q 0 ', q 1 ', ..., q i-1 ', q i'+1 〉 (i even) 1 3 10
〈 q 0 ', q 1', ..., q i' 〉 (i odd)

guess of edg e ⋅ dg 2621 7863 26210

guess of (p-1)(q-1) edg/k 2621 7863 8736

guess of g edg mod k 0 0 2

guess of (p+q)/2 see (31) 3153.5 532.5 96

(quit) (quit)

guess of ((p-q)/2)2 see (32) 289 = 172

d dg/g 5

The continued fraction attack on RSA for this example yields

d = 5, p = 113, q = 79, k = 3, and g = 2.

One can verify that equation (27) is satisfied for these values in order to see that d = 5 is the
secret exponent corresponding to e = 2621. One can also verify that the sufficient
condition for the success of this algorithm (equation (29)) is satisfied.

This example illustrates the details of the continued fraction attack on RSA, but it is useful
to consider a more realistic case. Suppose that a 1024-bit modulus is used for RSA. Then

10
p and q are approximately 2512. Suppose that g = 2, and that e ≈ pq so that k ≈ dg (see
equation (28)). Then using equation (29), we see that the continued fraction attack will
find secret exponents up to a size of approximately 2255.

6. Combatting the Continued Fraction Attack on RSA

There are two ways of reducing the maximum size of secret exponent which can be found
using the continued fraction attack on RSA. From equation (29), we can see that these are
to make k larger and to make g larger.

In order to make k larger, one must make the public exponent e larger (see equation (27)).
This can be done by adding a multiple of LCM(p-1, q-1) to e. Suppose that e > (pq) 1.5.
This implies that k/dg > (pq)0.5 (see equation (28)). Substituting k = dg(pq)0.5 into (29)
leads to d < 1. Therefore, if e > (pq)1.5, the continued fraction algorithm is not guaranteed
to work for any size of secret exponent. Increasing the size of e has the disadvantage that it
increases the execution time of public key encryption. But, this may be acceptable in some
systems.

In order to make g larger, p and q must be chosen such that GCD( p-1, q-1) is large.
However, we will see later that there are ways to find g or factors of g under certain
conditions.

7. Improvements to the Attack on RSA

In this section, four possible improvements to the attack on short secret exponents will be
discussed. The first improvement is to allow the continued fraction algorithm to continue
searching for d slightly beyond the limit of equation (29). The algorithm is only guaranteed
to work up to this limit, but it may work slightly beyond the limit. This may add a bit or so
to the size of secret exponent that can be found.

The second improvement is based upon the observation that the denominator of e/pq
(which is the underestimate of k/dg) is simply an overestimate of (p-1)(q-1). A closer
overestimate of (p-1)(q-1) is

( pq - 1) 2  .

Using this estimate, equation (29) becomes

2
kdg <
2
3 ( pq - 1
p - q
) .

This increases the size of secret exponent that can be found. The amount of improvement
increases as p - q decreases.

11
The third improvement to the continued fraction attack on RSA is to perform the algorithm
on many guesses of k/dg. One might start at some initial guess and then try successively
larger guesses. In this way, one would be performing a linear search for k/dg. For secret
exponents up to the limit of equation (29), the algorithm takes polynomial time. As the
secret exponent increases in size beyond this limit, the number of times that the algorithm
must be performed increases exponentially.

The fourth improvement is to attempt to find g or factors of g. Suppose that t is known to

be a factor of g. Then one could use

k
t ( pqe ) as an underestimate of
g
.
d( )
t

In this case, equation (29) becomes

kd ( gt ) <
3
pq
(p+ q)
.
2

This increases the size of d that can be found by a factor of t. We now need a way to find
factors of g. Because g divides GCD(p-1, q-1), g divides both p-1 and q-1. This means
that g also divides pq-1 because

pq-1 = (p-1)(q-1) + (p-1) + (q-1).

One may be able to find factors of g by factoring pq - 1. If g is chosen to be large and all
of the prime factors of g are large, then it may be difficult to find factors of g by factoring
pq-1. However, if g is so large that (p-1)/g and (q-1)/g are small, then one could find g by
searching through possible values of (p-1)/g and (q-1)/g.

8. Open Problems

The main motivation for using short secret exponents is to reduce the secret key
exponentiation time. A useful technique for reducing the secret key exponentiation time is
to take advantage of the knowledge of p and q (rather than just the product pq) [4]. Using
this technique, two half-sized exponentiations are performed. The first exponentiation
gives the result modulo p using exponent dp = d mod (p-1), and the second gives the result
modulo q using exponent dq = d mod (q - 1). These two results can be combined easily
using the Chinese Remainder Theorem to obtain the final result modulo pq. One could
reduce the secret key exponentiation time further by choosing d so that dp and dq are short.
An interesting open problem is whether there is an attack on RSA when dp and dq are short,
but not equal.

12
There is another open problem related to the size of the public exponent. Recall that the
attack described in this paper is defeated if the public exponent is chosen to be at least 50%
longer than the modulus pq. For some systems, this may be a small price to pay in order to
have fast secret key exponentiations. An interesting question is whether there is an attack
on RSA when the secret exponent is short, and the public exponent is larger than the
modulus.

9. Conclusion

The continued fraction algorithm can be used to find sufficiently short RSA secret
exponents in polynomial time. For a typical case where e < pq, GCD(p-1, q-1) is small,
and p and q have approximately the same number of bits, this algorithm will find secret
exponents with up to approximately one-quarter as many bits as the modulus.

There are ways to combat the continued fraction attack on RSA. If e > (pq)1.5, then the
continued fraction algorithm is not guaranteed to work for any size of secret exponent.
Also, one might choose GCD(p-1, q-1) to be large because the size of secret exponent
which can be found is inversely proportional to GCD(p-1, q-1). However, choosing
GCD(p-1, q-1) to be large may cause other problems.

A number of improvements to the continued fraction attack on RSA were discussed.

However, they only add a few more bits to the maximum size of secret exponent which can
be found in polynomial time. As the secret exponent increases in size beyond this
maximum, the time required to find the secret exponent increases exponentially.

This attack cannot be extended to the normal case where the secret exponent is
approximately the same size as the modulus.

References

[1] Hastad, J., "On Using RSA with Low Exponent in a Public Key Network", Lecture
Notes in Computer Science : Advances in Cryptology - CRYPTO '85 Proceedings,
Springer-Verlag, pp. 403-408.
[2] Knuth, D.E., Art of Computer Programming Volume 2 / Seminumerical
Algorithms, Addison Wesley, 1969.
[3] Pollard, J.M., "Theorems on factorization and primality testing", Proc. Cambridge
Philos. Soc., vol. 76, 1974, pp. 521-528.
[4] Quisquater, J.J. and C. Couvreur, "Fast Decipherment Algorithm for RSA Public-
Key Cryptosystem", Electronics Letters, vol. 18, no. 21, October 1982, pp. 905-
907.
[5] Rivest, R.L., A. Shamir, and L. Adleman, "A Method for Obtaining Digital
Signatures and Public-Key Cryptosystems", Communications of the ACM, vol. 21,
no. 2, February 1978, pp. 158-164.

13
[6] Williams, H.C., "A p+1 Method of Factoring", Mathematics of Computation,
vol. 39, no. 159, July 1982, pp. 225-234.

14