New attacks on RSA with Moduli N = pr q
Abderrahmane Nitaj1? and Tajjeeddine Rachidi2
1

Laboratoire de Mathématiques Nicolas Oresme
Université de Caen Basse Normandie, France
abderrahmane.nitaj@unicaen.fr
2
School of Science and Engineering
Al Akhawayn University in Ifrane, Morocco
T.Rachidi@aui.ma

Abstract. We present three attacks on the Prime Power RSA with modulus N = pr q. In the first attack, we consider a public exponent e satisfying an equation ex − φ(N )y = z where φ(N ) = pr−1 (p − 1)(q − 1).
We show that one can factor N if the parameters |x| and |z| satisfyr(r−1)|xz| < N (r+1)2 thereby extending the recent results of Sakar [16]. In
the second attack, we consider two public exponents e1 and e2 and theircorresponding private exponents d1 and d2 . We show that one can factor N when d1 and d2 share a suitable amount of their most significant
r(r−1)

bits, that is |d1 − d2 | < N (r+1)2 . The third attack enables us to factor two Prime Power RSA moduli N1 = pr1 q1 and N2 = pr2 q2 when p1
and p2 share a suitable amount of their most significant bits, namely,|p1 − p2 | < 2rqp11 q2 .

Keywords: RSA, Cryptanalysis, Factorization, Coppersmith’s method, PrimePower RSA

1Introduction

The RSA public-key cryptosystem, invented in 1978 by Rivest, Shamir and Adleman [15], is one of the most popular systems in use today. In the RSA cryptosystem, the public key is (N, e) where the modulus N = pq is a product of two
primes of the same bitsize, and the public exponent is a positive integer satisfying ed ≡ 1 (mod φ(N )). In RSA, encryption and decryption require executing
heavy exponential multiplications modulo the large integer N . To reduce thedecryption time, one may be tempted to use a small private exponent d. However, in 1990 Wiener [18] showed that RSA is insecure if d < 31 N 0.25 , and Bonehand Durfee [2] improved the bound to d < N 0.292 . In 2004, Blömer and May [1]combined both Wiener’s method and Boneh and Durfee’s method to show that
RSA is insecure if the public exponent e satisfies an equation ex + y = kφ(N )13with x < 13 N 4 and |y| ≤ N − 4 ex.
?

Partially supported by the French SIMPATIC (SIM and PAiring Theory for Information and Communications security).

2

Abderrahmane Nitaj and Tajjeeddine Rachidi

Concurrent to these efforts, many RSA variants have been proposed in orderto ensure computational efficiency while maintaining the acceptable levels of
security. One such important variant is the Prime Power RSA. In Prime Power
RSA the modulus N is in the form N = pr q for r ≥ 2. In [17], Takagi showed
how to use the Prime Power RSA to speed up the decryption process when the
public and private exponents satisfy an equation ed ≡ 1 (mod (p − 1)(q − 1)).
As in the standard RSA cryptosystem, the security of the Prime Power RSA
depends on the difficulty of factoring integers of the form N = pr q.
Therefore, a Prime Power RSA modulus must be appropriately chosen, since
it has to resist factoring algorithms such as the Number Field Sieve [10] and the
Elliptic Curve Method [9]. Table 1, shows the suggested secure Power RSA forms
as a function of the size of the modulus back in 2002 (see [4]). Note that, due
to the ever increasing development of computing hardware, the form N = p2 q is
no longer recommended for 1024 bit modulus.

Modulus size (bits)

1024

1536

2048

3072

2

2

2

2

4096
2

8192
3

2

Form of the modulus N pq, p q pq, p q pq, p q pq, p q pq, p q, p q pq, p q, p3 q, p4 q
Table 1. Optimal number of prime factors of a Prime Power RSA modulus [4].

In 1999, Boneh, Durfee, and Howgrave-Graham [3] presented a method forfactoring N = pr q when r is large. Furthermore, Takagi [17] proved that oner1
can factor N if d < N 2(r+1) , and May [13] improved the bound to d < N (r+1)2(r−1)2or d < N (r+1)2 . Very recently, Lu, Zhang and Lin [12] improved the bound tor(r−1)

d < N (r+1)2 , and Sarkar [16] improved the bound for N = p2 q to d < N 0.395
and gave explicit bounds for r = 3, 4, 5.
In this paper, we focus on the Prime Power RSA with a modulus N = pr q,
and present three new attacks: In the first attack we consider a public exponent
e satisfying an equation ex − φ(N )y = z where x and y are positive integers.
Using a recent result of Lu, Zhang and Lin [12], we show that one can factor N inr(r−1)

polynomial time if |xz| < N (r+1)2 . In the standard situation z = 1, the conditionr(r−1)

becomes d = x < N (r+1)2 which improves the bound of May [13] for r ≥ 3 andretrieves the bound of Lu, Zhang and Lin [12]. Note that unlike Sarkar [16] whosolves ex − φ(N )y = 1, we solve a more general equation ex − φ(N )y = z. This
leads to less constraints on the solution space, which in turn leads to an increasein the number of solutions to the equation. Intuitively speaking, our method has
higher likelihood of finding solutions; that is, factoring RSA. In section 3, weshall present an example supporting this claim.
In the second attack, we consider an instance of the Prime Power RSA withmodulus N = pr q. We show that one can factor N if two private keys d1 and d2
share an amount of their most significant bits, that is if |d1 − d2 | is small enough.

New attacks on RSA with Moduli N = pr q3

r(r−1)

More precisely, we show that if |d1 − d2 | < N (r+1)2 , then N can be factored inpolynomial time. The method we present is based on a recent result of [12] with
Coppersmith’s method for solving an univariate linear equation.
In the third attack, we consider two instances of the Prime Power RSA withtwo moduli N1 = pr1 q1 and N2 = pr2 q2 such that the prime factors p1 and p2
share an amount of their most significant bits, that is |p1 − p2 | is small. Moreprecisely, we show that one can factor the RSA moduli N1 and N2 in polynomial
time if |p1 − p2 | < 2rqp11 q2 . The method we use for this attack is based on thecontinued fraction algorithm.
The rest of this paper is organized as follows: In Section 2, we briefly review
the preliminaries necessary for the attacks, namely Coppersmith’s technique
for solving linear equations and the continued fractions theorem. In Section 3,
we present the first attack on the Prime Power RSA, which is valid with noconditions on the prime factors. In Section 4, we present the second attack inthe situation where two decryption exponents share an amount of their mostsignificant bits. In Section 5, we present the third attack on the Prime Power
RSA when the prime factors share an amount of their most significant bits. We
then conclude the paper in Section 6.

2

Preliminaries

In this section, we present some basics on Coppersmith’s method for solving
linear modular polynomial equations and an overview of the continued fraction
algorithm. Both techniques are used in the crafting of our attacks.
First, observe that if N = pr q with q < p, then pr+1 > pr q = N , and1p > N r+1 . Hence throughout this paper, we will use the inequality p > N β
1where β = r+1.
2.1

Linear Modular Polynomial Equations

In 1995, Coppersmith [5] developed powerful lattice-based techniques for solving
both modular polynomial diophantine equations with one variable and two variables. These techniques have been generalized to more variables, and have served
for cryptanalysis of many instances of RSA. More on this can be found in [14,8].
In [7], Herrmann and May presented a method for finding the small roots of amodular polynomial equation f (x1 , . . . , xn ) ≡ 0 (mod p) where f (x1 , . . . , xn ) ∈Z[x1 , . . . , xn ] and p is an unknown divisor of a known integer N . Their method
is based on the seminal work of Coppersmith [5]. Very recently, Lu, Zhang and
Lin [12] presented a generalization for finding the small roots of a modular
polynomial equation f (x1 , . . . , xn ) ≡ 0 (mod pv ), where pv is a divisor of somecomposite integer N . For the bivariate case, they proved the following result,which we shall use in the crafting of our attacks.
Theorem 1 (Lu, Zhang and Lin). Let N be a composite integer with adivisor pu such that p ≥ N β for some 0 < β ≤ 1. Let f (x, y) ∈ Z[x, y] be4Abderrahmane Nitaj and Tajjeeddine Rachidi

a homogenous linear polynomial. Then one can find all the solutions (x, y) of
the equation f (x, y) = 0 mod pv with gcd(x, y) = 1, |x| < N γ1 , |y| < N γ2 , inpolynomial time if
γ1 + γ2 < uvβ 2 .
2.2

The Continued Fractions Algorithm

We present here the well known result of Legendre on convergents of a continued
fraction expansion of a real number. The details can be found in [6]. Let ξ
be a positive real number. Define ξ0 = ξ and for i = 0, 1, . . . , n, ai = bξi c,
ξi+1 = 1/(ξi − ai ) unless ξi is an integer. This expands ξ as a continued fractionin the following form:1ξ = a0 +a1 +, a0 ∈ N, and ai ∈ N∗ for i ≥ 1,

1
..

.+

1
an +

1
..

.

which is often rewritten as ξ = [a0 , a1 , . . . , an , . . .]. For i ≥ 0, the rational numbers [a0 , a1 , . . . , ai ] are the convergents of ξ. If ξ = ab is a rational number, then
ξ = [a0 , a1 , . . . , an ] for some positive integer n, and the continued fraction expansion of ξ is finite with the total number of convergents being polynomial inlog(b). The following result enables one to determine if a rational number ab is aconvergent of the continued fraction expansion of a real number ξ (see Theorem
184 of [6]).
Theorem 2 (Legendre). Let ξ be a positive real number. Suppose gcd(a, b) = 1
and
a
1
ξ−
< 2.
b
2b
Then ab is one of the convergents of the continued fraction expansion of ξ.
Note that the continued fractions expansion process is polynomial in time.

3

The First Attack on Prime Power RSA with Modulus
N = pr q

In this section, we present an attack on the Prime Power RSA when the publickey (N, e) satisfies an equation ex − φ(N )y = z with small parameters x and |z|.
Theorem 3. Let N = pr q be a Prime Power RSA modulus and e a public
exponent satisfying the equation ex − φ(N )y = z with y 6≡ 0 (mod pq), 1 < e <φ(N ) and gcd(e, φ(N )) = 1. Then one can factor N in polynomial time ifr(r−1)|xz| < N (r+1)2 .

New attacks on RSA with Moduli N = pr q

5

Proof. Suppose that e < N satisfies an equation ex − φ(N )y = z with |x| < N δand |z| < N γ . Then, since φ(N ) = pr−1 (p − 1)(q − 1), we get ex − z ≡ 0
1(mod pr−1 ). Applying Theorem 1 with u = r, v = r − 1 and β = r+1, we cansolve the equation in polynomial time ifδ + γ < uvβ 2 =r(r − 1),
(r + 1)2r(r−1)ethat is |xz| < N (r+1)2 . Since φ(N) < 1, then, using x and z in the equationex − φ(N )y = z, we get for sufficiently large N comparatively to r,y=r(r−1)
ex − ze|x||z|<+< |x| + |z| ≤ 1 + |xz| < 1 + N (r+1)2 < N.
φ(N )φ(N ) φ(N )Hence, when y 6≡ 0 (mod pq), we getgcd(ex − z, N ) = gcd(pr−1 (p − 1)(q − 1)y, pr q) = g,1

with g = pr−1 , g = pr or g = pr−1 q. If g = pr−1 , then p = g r−1 , if g = pr , then1
p = g r and if g = pr−1 q, then p = Ng . This leads to the factorization of N . tu
Example 1. For r = 2 and N = pr q, let us take for N and e the 55 digit numbers
N = 8138044578297117319482018441148072252199996769522371021,
e = 1199995230601021126201343651611107957480251354355883029.
In order to solve the diophantine equation ex−φ(N )y = z, we transformed it
into the equation ex − z ≡ 0 (mod pr−1 ) using Theorem 3. To be able to apply
Coppersmith’s technique via Theorem 1, we chose the parameters m = 7, t = 6
r(r−1)

so that the dimension of constructed the lattice is 36, and X = N (r+1)2=

1592999974064. We built the lattice using the polynomial f (x1 , x2 ) = x1 + ex2 ,then applied the LLL algorithm [11], and used Gröbner basis method to findthe smallest solution x1 = −11537 and x2 = 7053 to f (x1 , x2 ) ≡ 0 (mod pr−1 )in 174 seconds using an off-the-shelf computer. From this solution, we deduced
p = gcd(x1 + ex2 , N ) = 2294269585934949239, and finally recovered q = pN2 =1546077175000723901. We then computed φ(N ) and d ≡ e−1 (mod φ(N )) as
follows:
φ(N ) = 8138044578297117310671227668089561946257896925261579800,
d = 2015994747748388772982436393811213317361971865510756269.
Observe that d ≈ N 0.98 which is out of range of Sarkar’s bound [16] which can
only retrieve private keys d < N 0.395 for r = 2.

64

Abderrahmane Nitaj and Tajjeeddine Rachidi

The Second Attack on Prime Power RSA using Two
Decryption Exponents

In this section, we present an attack on the Prime Power RSA when two private
exponents d1 and d2 share an amount of their most significant bits, that is|d1 − d2 | is small.
Theorem 4. Let N = pr q be an RSA modulus and d1 and d2 be two private
exponents such that e1 e2 (d1 − d2 ) − (e2 − e1 ) 6≡ 0 (mod N ). Then, one can factor
N in polynomial time, ifr(r−1)|d1 − d2 | < N (r+1)2 .
Proof. Suppose that e1 d1 − k1 φ(N ) = 1 and e2 d2 − k2 φ(N ) = 1 with e1 > e2 .
Hence e1 d1 ≡ 1 (mod φ(N )) and e2 d2 ≡ 1 (mod φ(N )). Multiplying the firstequation by e2 and the second by e1 and subtracting, we get
e1 e2 (d1 − d2 ) ≡ e2 − e1(mod φ(N )).

Since φ(N ) = pr−1 (p − 1)(q − 1), we get e1 e2 (d1 − d2 ) ≡ e2 − e1 (mod pr−1 ).
Now, consider the modular linear equatione1 e2 x − (e2 − e1 ) ≡ 0(mod pr−1 ),d1 − d2 is a root of such equation. Suppose further that |d1 − d2 | < N δ , then1
applying Theorem 1 with u = r, v = r − 1 and β = r+1
will lead to the solution
x = d1 − d2 obtained in polynomial time if
δ < uvβ 2 =r(r − 1).
(r + 1)2r(r−1)

That is if |d1 − d2 | < N (r+1)2 . Computing
gcd(e1 e2 x − (e2 − e1 ), N ) = gcd pr−1 (p − 1)(q − 1)y, pr q = g,
and assuming that e1 e2 (d1 −d2 )−(e2 −e1 ) 6≡ 0 (mod N ) will lead to determining
1
1
p, hence factoring N as follows: p = g r−1 when g = pr−1 , or p = g r when g = pr ,
N
r−1
t
u
or p = g if g = p q.
Example 2. Let us present an example corresponding to Theorem 4. Consider
N = p2 q with
N = 6093253851486120878859471958399737725885946526553626219,
e1 = 2749600381847487389715964767235618802529675855606377411,
e2 = 3575081244952414009316396501512372226545892558898276551.
The polynomial equation is f (x) = e1 e2 x − (e2 − e1 ) ≡ 0 (mod pr−1 ), which canbe transformed into g(x) = x − a ≡ 0 (mod pr−1 ) where a ≡ (e2 − e1)(e1 e2 )−1New attacks on RSA with Moduli N = pr q

7

(mod N ). Using m = 8 and t = 6, we built a lattice with dimension ω = 9. Applying the LLL algorithm [11] and solving the first reduced polynomials, we get
the solution x0 = 1826732340. Hence gcd(f (x0 ), N ) = p = 1789386140116417697
and finally q = pN2 = 1903010275819064491. The whole process took less than
4 seconds using an off-the-shelf computer. Then, using φ(N ) = p(p − 1)(q −1), we retrieved the private exponents d1 ≡ e−1(mod φ(N )) and d2 ≡ e−1
1
2
0.99(mod φ(N )). Note that again d1 ≈ d2 ≈ N
which Sarkar’s method with thebound d < N 0.395 could not possibly retrieve.

5

The Third Attack on Prime Power RSA with Two
RSA Moduli

In this section, we consider two Prime Power RSA moduli N1 = pr1 q1 and N2 =pr2 q2 , where p1 and p2 share an amount of their most significant bits.
Theorem 5. Let N1 = pr1 q1 and N2 = pr2 q2 be two RSA moduli with p1 > p2 . If
p1,
2rq1 q2|p1 − p2 | <then, one can factor N in polynomial time.
Proof. Suppose that N1 = pr1 q1 and N2 = pr2 q2 with p1 > p2 . Then q2 N1 −q1 N2 =q1 q2 (pr1 − pr2 ). HenceN2
q1 q2 |pr1 − pr2 |
q2
=
.
−
N1
q1
q12 pr1
In order to apply Theorem 2, we need that|pr1 − pr2 | <q1 q2 |pr1 −pr2 |< 2q12 , or equivalently
q12 pr1
1

pr1.
2q1 q2(1)

Observe that|pr1 − pr2 | = |p1 − p2 |r−1
X

p1r−1−i pi2 < r|p1 − p2 |pr−1
.
1

i=0
pr

Then (1) is fulfilled if r|p1 − p2 |pr−1< 2q11q2 , that is if1|p1 − p2 | <p1.
2rq1 q2

Under this condition, we get qq21 among the convergents of the continued fraction  r1  r1N2
N1
N2
expansion of N
.
Using
q
and
q
,
we
get
p
=
and
p
=
.
t
u
1
2
1
2
q1
q2
1

8

Abderrahmane Nitaj and Tajjeeddine Rachidi

Example 3. We present here an example corresponding to Theorem 5. Consider
N1 = p21 q1 and N2 = p22 q2 with
N1 = 170987233913769420505896917437304719816691353833034482461,
N2 = 120532911819726882881630714003135237766675602824250965921.
We applied the continued fraction algorithm to compute the first 40 convergents
q2
2
of N
N1 . Every convergent is a candidate for the ratio q1 of the prime factors. Oneof the convergents is 36443689
51698789 leading to q2 = 36443689 and q1 = 51698789. This
gives the prime factors p1 and p2
sN1= 1818618724382942951460443,
p1 =
q1
s
N2
p2 =
= 1818618724382943035672683.
q2

6

Conclusion

In this paper, we have considered the Prime Power RSA with modulus N = pr q
and public exponent e. We presented three new attacks to factor the modulus
in polynomial time. The first attack can be applied if small parameters x, y andz satisfying the equation ex − φ(N )y = z can be found . The second attack can
be applied when two private exponents d1 and d2 share an amount of their mostsignificant bits. The third attack can be applied when two Prime Power RSA
moduli N1 = pr1 q1 and N2 = pr2 q2 are such that p1 and p2 share an amount of
their most significant bits.

References
1. Blömer, J., May, A.: A generalized Wiener attack on RSA. In Public Key Cryptography - PKC 2004, volume 2947 of Lecture Notes in Computer Science, pp. 1–13.
Springer-Verlag (2004)
2. Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N 0.292 ,Advances in Cryptology-Eurocrypt’99, Lecture Notes in Computer Science Vol.
1592, Springer-Verlag, pp. 1–11 (1999)
3. Boneh, D., Durfee, G., Howgrave-Graham, N.: Factoring N = pr q for Large r.
In M. Weiner, ed., Proceedings of Crypto’99, vol. 1666 of LNCS, pp. 326–337.
Springer-Verlag, Aug. (1999)
4. Compaq Computer Corperation. Cryptography using Compaq multiprime technology in a parallel processing environment, 2002. Availabe online at
ftp://ftp.compaq.com/pub/solutions/CompaqMultiPrimeWP.pdf
5. Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA
vulnerabilities. Journal of Cryptology, 10(4), pp. 233–260 (1997)
6. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford
University Press, London (1975)

New attacks on RSA with Moduli N = pr q

9

7. Herrmann, M., May, A.: Solving linear equations modulo divisors: On factoring
given any bits. In Advances in Cryptology-ASIACRYPT 2008. Springer, 2008, pp.
406–424 (2008)
8. Hinek, M.J.: Cryptanalysis of RSA and its variants. Chapman & Hall/CRC Cryptography and Network Security. CRC Press, Boca Raton, FL, (2010)
9. Lenstra, H.: Factoring integers with elliptic curves, Annals of Mathematics, Vol.
126, pp. 649–673 (1987)
10. Lenstra, A.K., Lenstra, H.W. Jr. (eds.): The Development of the Number Field
Sieve, Lecture Notes in Mathematics, vol. 1554, Berlin, Springer-Verlag, (1993)
11. Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rationalcoefficients, Mathematische Annalen, Vol. 261, pp. 513–534, (1982)
12. Y. Lu and R. Zhang and D. Lin, New Results on Solving Linear Equations Modulo Unknown Divisors and its Applications, Cryptology ePrint Archive, Report
2014/343, 2014 https://eprint.iacr.org/2014/343.
13. May, A.: Secret Exponent Attacks on RSA-type Schemes with Moduli N = pr q.
Public Key Cryptography–PKC 2004, LNCS 2947, pp. 218–230, (2004)
14. May A.: Using LLL-reduction for solving RSA and factorization problems: a survey.
In: LLL+25 Conference in Honour of the 25th Birthday of the LLL Algorithm.
Springer, Berlin, Heidelberg (2007)
15. Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining digital signatures andpublic-key cryptosystems, Communications of the ACM, Vol. 21 (2), pp. 120–126(1978)
16. Sarkar, S.: Small secret exponent attack on RSA variant with modulus N = pr q,
Designs, Codes and Cryptography, Volume 73, Issue 2 , pp 383–392 (2015)
17. Takagi, T.: Fast RSA-type cryptosystem modulo pk q. In Advances in Cryptology–
Crypto’98, pp. 318–326. Springer, (1998)
18. Wiener, M.: Cryptanalysis of short RSA secret exponents, IEEE Transactions on
Information Theory, Vol. 36, pp. 553–558 (1990)