cryptography

Article
New Cryptanalytic Attack on RSA Modulus N = pq
Using Small Prime Difference Method
Muhammad Rezal Kamel Ariffin 1,2,† , Saidu Isah Abubakar 1, *,† , Faridah Yunos 1,2,† and
Muhammad Asyraf Asbullah 1,3,†
1 Al-Kindi Cryptography Research Laboratory, Institute for Mathematical Research, Universiti Putra Malaysia,
43400 Selangor, Malaysia; rezal@upm.edu.my (M.R.K.A.); faridahy@upm.edu.my (F.Y.);
ma_asyraf@upm.edu.my (M.A.A.)
2 Department of Mathematics, Faculty of Science, Universiti Putra Malaysia, 43400 Selangor, Malaysia
3 Centre of Foundation Studies for Agriculture Science, Universiti Putra Malaysia, 43400 Selangor, Malaysia
* Correspondence: siabubakar82@gmail.com
† These authors contributed equally to this work.




Received: 1 November 2018; Accepted: 15 December 2018; Published: 20 December 2018


Abstract: This paper presents new short decryption exponent attacks on RSA, which successfully
leads to the factorization of RSA modulus N = pq in polynomial time. The paper has two parts. In
the first part, we report the usage of the small prime difference method
√
of the form |b2 p − a2 q| < N γ
q 2 3
where the ratio of p is close to ba2 , which yields a bound d < √3 N 4 −γ from the convergents of
2
e
the continued fraction expansion of 2
a +b 2 √ . The second part of the paper reports four
N −d ab N e+1
cryptanalytic attacks on t instances of RSA moduli Ns = ps qs for s = 1, 2, . . . , t where we use
2 + b2 √
N − d a ab N e + 1 as an approximation of φ( N ) satisfying generalized key equations of the shape
es d − k s φ( Ns ) = 1, es ds − kφ( Ns ) = 1, es d − k s φ( Ns ) = zs , and es ds − kφ( Ns ) = zs for unknown
positive integers d, k s , ds , k s , and zs , where we establish that t RSA moduli can be simultaneously
factored in polynomial time using combinations of simultaneous Diophantine approximations and
lattice basis reduction methods. In all the reported attacks, we have found an improved short secret
exponent bound, which is considered to be better than some bounds as reported in the literature.

Keywords: RSA modulus; primes difference; cryptanalysis; short decryption exponent; attacks;
continued fraction

1. Introduction
The RSA cryptosystem is the most widely used public key cryptosystem, invented by three
mathematicians, Rivest, Shamir, and Adleman [1] and since then has been extensively used for many
applications in the government as well as commercial domain, which include e-banking, secure
telephone, smart cards, and communications in different types of networks [2].
RSA key generation involves a random selection of two distinct large prime numbers such that
their product is represented as N = pq and called an RSA modulus. The Euler totient function
φ( N ) is computed as φ( N ) = ( p − 1)(q − 1). Additionally, choose an integer e < φ( N ) such that
gcd(e, φ( N )) = 1 and compute short decryption exponent d such that the relation ed ≡ 1 (mod φ( N ))
is satisfied. Then, (e, N ) are the public pair and (d, p, q) are private key tuple.
The encryption function is computed by choosing a message M ∈ Z N and computing the
ciphertext C = Me (mod N ), while the plaintext can be recovered by computing the decryption
exponent from equation M = C d (mod N ). The primes p and q in most cases are considered to have
same bit-length.

Cryptography 2019, 3, 2; doi:10.3390/cryptography3010002 www.mdpi.com/journal/cryptography

Cryptography 2019, 3, 2 2 of 25

In simpler terms, an RSA cryptosystem involves three processes of key generation, encryption,
and decryption algorithms as presented in Algorithms 1–3 below:

Algorithm 1 RSA key generation

1: Initialization: Input the size n and (e, N ).
2: Choose two random and distinct n − bit strong primes ( p, q).
3: for each pair of the form ( p, q) do
4: N := pq
5: φ( N ) := ( p − 1)(q − 1)
6: end for
7: Choose a random integer e such that 1 < e < φ( N ) and gcd(e, φ( N )) = 1.
8: if d is an integer then
9: ed ≡ 1 (mod φ( N )).
10: end if
11: return the public key pair ( N, e) and the private key pair ( N, d).

Algorithm 2 RSA encryption

1: Initialization: Input the public key pair (e, N ) and the plaintext M.
2: Represents the plaintext message M as integer such that M < N and gcd( M, N ) = 1.
3: for each triplet of the form (e, N, M ) do
4: C := Me (mod N )
5: end for
6: return the ciphertext C.

Algorithm 3 RSA decryption

1: Initialization: Input the private key pair (d, N ) and the ciphertext C.
2: for each triplet of the form (d, N, C ) do
3: M := C d (mod N )
4: end for
5: return the message M.

The security of an RSA cryptosystem depends on the difficulty of solving the integer factorization
problem, the failure of an adversary to compute the secret key d from RSA key equation ed = 1 + kφ( N ),
where only the public key e is given as outlined in Algorithm 1 and the difficulty of solving the eth -root
problem of C = Me (mod N ) as outlined in Algorithm 2. The problem of computing d from (e, N ) is
equivalent to the problem of factoring RSA modulus N into its nontrivial prime factors of p and q, as
proven by Reference [3]. It is therefore recommended for RSA users to generate primes p and q in such
a way that the problem of factoring N = pq is computationally infeasible for an adversary. Choosing p
and q as strong primes has been recommended as a way of maximizing the difficulty of factoring RSA
modulus N.
In an RSA cryptosystem, there are public key pairs (e, N ) and private key tuples (d, p, q, φ( N )).
Once the private key d is known, it can lead to the total break of RSA. It is often tempting to use a small
decryption exponent so as to speed up computation in RSA decryption and signature verification.
However, this poses a great security challenge to the system. A very small decryption exponent can be
broken by a trivial brute force exhaustive search to find the correct decryption exponent. For instance,
all private exponents d < 260 can be recovered easily, but it is computationally infeasible to recover all
private exponents d < 280 by brute force attack [4].
Cryptography 2019, 3, 2 3 of 25

The first attack on small decryption exponent was reported by Wiener in 1990. He showed that
RSA is insecure if the small decryption exponent is d < 31 N 0.25 using the continued fractions method
to recover d from the convergents of the continued fractions expansion of Ne , [5]. Since then, many
attacks on short decryption exponents emerged, which improved the bound. Boneh and Durfee (1999)
proposed an attack on the small decryption exponent using the Coppersmith lattice-based technique,
in which they heuristically showed that RSA in insecure if d < N 0.292 , as reported by Reference [6].
In another development, B. De Weger (2002) also used the primes difference method to carry out
3
an attack on RSA modulus N = pq, where he proved that if d < | pN−4q| , then the RSA cryptosystem is
considered to be insecure where primes p and q have the same bit-length, which is an improvement
on Wiener’s bound as reported by Reference [7]. In addition, Maitra and Sarkar (2008) improved the
work of Reference [7] using the prime difference method of |2q − p| < N γ and showed that RSA is not
1− γ
secure if d < N 2 , as reported by Reference [8].
Furthermore, Chen’s et al. (2009) have generalized the work of Reference [7], where they proposed
an attack using the generalization method, in which they proved that RSA modulus N = pq can be
3 p
broken if | ap − bq| = N γ and d < N 4 −γ , where the ratio of two primes q is very near to the ratio ba ,
where p < q < 2p, a, and b are small positive integers less than log N, then the RSA modulus can
e√
be factored from the convergents of the continued fraction expansion of a+b . Substituting
√ N− N +1
ab
a = b = 1 gave the approximation of φ( N ) as reported by [7]. Also, taking a = 2 and b = 1 gave
approximation of φ( N ) as reported by Reference [8]. In their experiment result, they used the value of
γ = 0.5 to justify their theorem, as reported by Reference
√ [9] .
√
6 2 14
Nitaj (2013) improved Wiener’s bound to d < 6 N , as reported by Reference [10]. Asbullah
1 41
(2015) also improved Wiener’s bound to d < 2N ,
as reported [11].
This paper reports the use of the small prime difference method to factor the RSA modulus N and
its relation to further extend the bound of weak decryption exponents. Given public key pair (e, N ), we
exploited RSA key equation ed = 1 + kφ( N ) and broke the instances of RSA by factoring the modulus
N into its nontrivial prime factors p and q. We also reported four cryptanalytic attacks on factoring t
RSA moduli using a system of equations where, in one instance, the moduli (es , Ns ) shared a common
decryption exponent d and, in another scenario, every pair (es , Ns ) had its own unique decryption
q 2
exponent ds . The method uses |b2 p − a2 q| < N γ such that if the ratio of p is close to the ratio of ba2 ,
√ 3
where a and b are small positive integers and 0.25 < γ ≤ 0.5, then private key d < √3 N 4 −γ can be
2
e
efficiently recovered from the convergents of the continued fraction expansion of 2 + b2 √ . Our
N −d a ab N e+1
bound is considered to be an improved bound of that of References [5,9,11]. This paper also presents
an experimental result which shows that taking γ = 15
32 , we can recover primes p and q if the private
√
key d < √3 N 0.28125 . This is an improvement of the result of Reference [9], as they did not give an
2
experiment result of γ < 0.5.
The second part of the paper presents t instances of factoring RSA moduli Ns = ps qs for t =
1, 2, . . . , t by transforming generalized key equations of the form es d − k s φ( Ns ) = 1, es ds − kφ( Ns ) =
1, es d − k s φ( Ns ) = zs , and es ds − kφ( Ns ) = zs for unknown parameters d, k s , ds , k s , and zs into
simultaneous Diophantine problem and applying the lattice basis reduction and LLL methods to find
the values of d, k s , ds , and k. We formulated a quadratic equation which enabled us to find t prime
factors ps and qs and finally factorize t moduli N1 , N2 , . . . , Nt in polynomial time. We have found
decryption exponents bounds that are greater than those of References [12,13].
The rest of the paper is organized as follows. In Section 2, we present a review of some preliminary
results on continued fractions and state some theorems that are related to our work. Section 3 presents
our proposed findings and discussion on the results. We give experimental results to illustrate our
theorems, which show how an incorrect choice of d can lead to the factorization of RSA modulus
N = pq in polynomial time. Finally, in Section 4, we conclude the paper.
Cryptography 2019, 3, 2 4 of 25

2. Preliminaries and Methods

In this section, we state some basics on continued fraction, the lattice basis reduction technique,
simultaneous Diophantine approximations, and theorems related to our work.

Definition 1 (Continued fractions). For any positive x ∈ R, define x0 = x and for i = 1, 2, . . . , n, do

1
x i = b a i c , x i +1 = x − a until xn ∈ Z. Then, x can be expanded as continued fraction in following form,
i i

1
x = a0 + 1
.
a1 +
a2 + a 1+...
3

This expression is often used in the form x = [ a0 , a1 , a2 , . . . , an , . . .]. Any rational number ba can be
expressed as a finite continued fraction x = [ a0 , a1 , a2 , . . . , an ]. The convergents ba of x are the fractions denoted
by ba = [ a0 , a1 , a2 , . . . , ai ] for i ≥ 0. We note that if x = ba is a rational number, then the continued fraction
expansion of x is finite with total number of convergents being polynomial in log(b).

Definition 2. Let b1 , b2 , · · · , bm ∈ V where V is a vector space subset of Rn . The set of vectors

b1 , b2 , · · · , bm ∈ V are said to be linearly dependent if there exist x1 , . . . , xm ∈ R, which are not all zero
and such that:
m
∑ ( x i bi = 0 ) .
i

Otherwise, they are said to be linearly independent.

Definition 3. (Lenstra et al. 1982) Let n be a positive integer. A subset L of an n-dimensional real vector
space Rn is called a lattice and if there exists a basis b1 , . . . , bn on Rn such that we have the following relation
L = ∑in=1 Zbi = ∑in=1 ri bi f or ri ∈ Z, 1 ≤ i ≤ n. In this situation, we say that b1 , . . . , bn are the basis for L
or that they span L.

Definition 4. (Nitaj, 2013) (LLL Reduction) Let B = hb1 · · · bn i be a basis for a lattice L and suppose
B∗ = hb1∗ · · · bn∗ i be the associated Gram–Schmidt orthogonal basis. Let:

hbi , b∗j i
µi,j = f or 1 ≤ j < i.
hb∗j , b∗j i

The basis B is said to be LLL reduced if it satisfies the following two conditions:

1. µi,j ≤ 12 , f or 1 ≤ j < i ≤ n
3 ∗ 2 ∗ ∗ 2
2. 4 || bi −1 || ≤ || bi + µi,i −1 bi −1 || f or 1 ≤ i ≤ n. Equivalently, it can be written as:

3
||bi∗ ||2 ≥ ( − µ2i,i−1 )||bi∗−1 ||2 .
4

Theorem 1. (Legendre’s Theorem). Let α be a positive real number. If the rational numbers ( a, b) ∈ Z such
that gcd( a, b) = 1 and:
a 1
α− < 2,
b 2b
a
then b is one of the convergents of the continued fraction expansion α.

Proof. See Reference [14].

Cryptography 2019, 3, 2 5 of 25

p p p
Theorem 2. (Wang et al., 2016). If q 1 , q22 , . . . , q k , . . . are convergents of the simple continued fraction
1 k
[ a1 , a2 , . . . , ak , . . .], then the numerators and denominators of these convergents satisfy the following
recursive relations:
p1 = a1 , p2 = a2 a1 + 1, pk = ak pk−1 + pk−2 ,

q1 = 1, q2 = a2, qk = ak qk−1 + qk−2 ,

for k ≥ 3.

Theorem 3. (Wiener, 1990). Let N = pq be an RSA modulus with q < p < 2q. Let e < φ( N ) be a public
1
exponent and d be the corresponding private key. If d < 13 N 4 , then one can factor N in polynomial time.

Theorem 4. (B. de Weger, 2002). Let N = pq be an RSA modulus with q < p < 2p such that | p − q| < N β
for β = [ 14 , 12 ], and N > 8d. Let e and d be public and private keys respectively such that e < φ( N ), with
φ( N ) > 34 N and d < N δ . If δ < 34 − β, then the convergents can be found from the continued fraction of
e
√ , which led to the factorization of N.
N −2 N +1

Theorem 5. (Maitra-Sarkar, 2008). Let N = pq be an RSA modulus satistying q < p < 2q. Suppose that
|ρq − p| ≤ N16 with γ < 12 , 1 ≤ ρ ≤ 2 and d = N δ . Then N can be factored in polynomial time if δ < 1−2 γ
γ

e√
from the convergents of the continued fraction expansion of √3
.
N− N +1
2

Theorem 6. (Chen et al., 2009). Let p and q be RSA primes satisfying p < q < 2p. Let | ap − bq| = N γ .
q 3
If q is close to ba such that (b( a2 + 1) p − a(b2 + 1)q)( ap − bq) > 0, then the secret key d < N 4 −γ can be
e√
discovered from the convergents of a+b .
N− √ N +1
ab

Theorem 7. (Blomer-May, 2004). Let ( N, e) be an RSA public pair with modulus N = pq and the prime
1
difference p − q ≥ cN 2 . Suppose that the public exponent e ∈ Zφ( N ) satisfies ex + y = kφ( N ) with
1 −3
0 < x < 13 N 4 and |y| ≤ N 4 ex for c ≤ 1. Then, N can be factored in polynomial time.

Theorem 8. (Lenstra et al., 1982). Let L be a lattice basis of dimension n having a basis v1 · · · vn . The LLL
algorithm produces a reduced basis b1 · · · bn satisfying the following condition:
n ( n −1) 1
||b1 || ≤ ||b2 || ≤ · · · ≤ ||b j || ≤ 2 4(n+1− j) det(L) n+1− j ,

for all 1 ≤ j ≤ n.

Proof. See Reference [15].

We will use the following Theorem 9 in our proofs of Theorems 14–17.

Theorem 9. (Simultaneous Diophantine Approximations) (Nitaj et al., 2014). Given any rational numbers of
the form α1 , . . . , αn and 0 < ε < 1, there is a polynomial time algorithm to compute integers p1 , . . . , pn and a
positive integer q such that:
n ( n −3)
max |qαi − pi | < ε and q ≤ 3n 2 4 ε−n .
i

Theorem 10. (Nitaj et al. 2014). Let Ni = pi qi for 1 ≤ i ≤ k be k RSA moduli. Let N = min{ Ni } and ei ,
i = 1, . . . , k be k public exponents. Define δ = 2(kk+1) . If there exist an integer x < N δ and k integers yi < N δ
p −q
and |zi | < 3( pi +qi ) yi N 1/4 such that ei x − yi φ( Ni ) = zi for i = 1, . . . , k, then one can factor k RSA moduli
i i
N1 , . . . , Nk in polynomial time.
Cryptography 2019, 3, 2 6 of 25

Theorem 11. (Nitaj et al., 2014). Let Ni = pi qi , for 1 ≤ i ≤ k be k RSA moduli Ni where p and p are
(2α−1)k
balanced primes. Let ei , i = 1, . . . , k, be k public exponents with min{ei } = N α . Define δ = 2(k+1) . If there
p −q
exist an integer y < N δ and k integers xi < N δ and |zi | < 3( pi +qi ) yN 1/4 such that ei xi − yφ( Ni ) = zi for
i i
i = 1, . . . , k, then one can factor the k RSA moduli N1 , . . . , Nk in polynomial time.

Theorem 12. (Asbullah, 2015). Let N = pq with q < p < 2q. Let e < φ( N ) and d satisfy ed ≡ 1 mod φ( N ).
1
If d < 12 N 4 , then dk is a convergent of the continued fraction Ne .

3. The Proposed Findings and Discussion

In this section, we present our findings. The first part reported a short secret exponent attack
on RSA√modulus N = pq, where p and q are prime numbers of the same bit-length. We show that
3
if d < √3 N 4 −γ , then one can find dk from the convergents of the continued fraction expansion of
2
e
a 2 + b2 √ which leads to the factorization of RSA modulus N in polynomial time. In the second
N −d ab N e+1
part of the paper, we presented four cryptanalytic attacks using a generalized key equation of the
shape es d − k s φ( Ns ) = 1, es ds − kφ( Ns ) = 1, es d − k s φ( Ns ) = zs , and es ds − kφ( Ns ) = zs for unknown
integers d, k s , ds , k s , and zs . We showed that t RSA moduli Ns = ps qs can be simultaneously factored
in polynomial time where s = 1, 2, . . . , t.

3.1. A Short Decryption Exponent Attack Using |b2 p − a2 q| < N γ

In this section, we present two lemmas and a theorem with numerical examples.

Lemma 1. Let p and q be prime numbers, where q < p < 2q and N = pq. If a and b are small positive integers
2 q 2 + b2 √
such that ba2 is close to p for a > b and b2 p − a2 q 6= 0, then φ( N ) > N − a ab N + 1.

Proof of Lemma 1. Let (b2 p − a2 q)( a2 p − b2 q) < 0, then we get,

a2 b2 p2 − a4 pq − b4 pq + a2 b2 q2 < 0
a2 b2 ( p2 + q2 ) < ( a4 + b4 ) pq.

Adding 2a2 b2 pq to both sides we have,

a2 b2 ( p + q)2 < a4 + 2a2 b2 + b4 ) pq

a2 + b2 √
p+q < N.
ab
2 + b2 √
Then φ( N ) > N + 1 − a ab N.

Lemma 2. Let p and q be prime numbers where q < p < 2q and N = pq. If,

( a2 (b4 + 1) p − b2 ( a4 + 1)q)(b2 p − a2 q) > 0,

then,
a2 + b2 √ ( b2 p − a2 q )2
N − ( p + q) < 2 2 √ .
ab + b + 2) N
( a ab

Proof of Lemma 2. We first compute,

a2 + b2 √ a2 + b2 √
  
N − ( p + q) N + ( p + q ) − ( b2 p − a2 q )2
ab ab
Cryptography 2019, 3, 2 7 of 25

( a2 + b2 )2 ( a2 + b2 ) √ ( a2 + b2 ) √
= 2 2
N+ N ( p + q) − N ( p + q ) − ( p + q )2 − ( b2 p − a2 q )2
a b ab ab
−( a2 b6 + a2 b2 ) p2 + ( a4 + 2a4 b4 + b4 ) pq − ( a6 b2 − a2 b2 )q2
=
a2 b2
−( a (b + 1) p − b ( a + 1)q)(b2 p − a2 q)
2 4 2 4
= .
a2 b2

Since ( a2 (b4 + 1) p − b2 ( a4 + 1)q)(b2 p − a2 q) > 0, we get,

a2 + b2 √ a2 + b2 √
  
N − ( p + q) N + ( p + q ) − ( b2 p − a2 q )2 <0
ab ab
a2 + b2 √ ( b2 p − a2 q )2
N − ( p + q) < 2 2 √
ab a +b
N + ( p + q)
ab
a2 + b2 √ ( b2 p − a2 q )2
N − ( p + q) < 2 2 √ .
ab + b + 2) N
( a ab

Theorem 13. Let p and q be prime numbers, where q < p < 2q and N = pq. Given the pair (e, N ) for
q 2
e < φ( N ) as a public key pair and (d,p,q) as a private key tuple, let |b2 p − a2 q| < N γ . If p is close to ba2
√ 3
such that the relation ( a2 (b4 + 1) p − b2 ( a4 + 1)q)(b2 p − a2 q) > 0 holds and d < √3 N 4 −γ , then dk can be
2
e
calculated efficiently from the convergent of the continued fraction expansion of a + b2
2 √ for k < d and
N −d ab N e+1
( a, b) are positive integers less than log N.

Proof of Theorem 13. Since ( a2 (b4 + 1) p − b2 ( a4 + 1)q)(b2 p − a2 q) > 0 and b2 p − a2 q < N γ ,

then from Lemma 2 we have,

a2 + b2 √ ( b2 p − a2 q )2
N − ( p + q) < 2 2 √ √
ab a +b
N+2 N
ab
a + b2 √
 2
N 2γ

N + φ( N ) − N − 1 < 2 2 √ .
ab + b + 2) N
( a ab

Using RSA key equation ed − kφ( N ) = 1, for some k ∈ Z, this gives us,

e k 1
− = .
φ( N ) d dφ( N )

a2 + b2
√
Taking N − ab N + 1 as approximation of φ( N ), this becomes,

e k e k
− = a2 + b2
√ −
φ( N ) d N− N+1 d
ab
e e e k
= a2 + b2
√ − + −
N− N+1 φ( N ) φ( N ) d
ab
e e e k
≤ a2 + b2
√ − + −
N− ab N + 1 φ( N ) φ( N ) d
2 2 √
e|(φ( N ) − N − a ab+b N − 1)| 1
= a + b2
2 √ + .
φ( N )( N − ab N + 1) dφ ( N)
Cryptography 2019, 3, 2 8 of 25

Finally,

e k N 2γ 1
− < a2 + b2
√ 2 + b2 √ √ + . (1)
φ( N ) d (N − N + 1)( a ab N + 2 N) dφ( N )
ab

2 + b2 √
Now, assuming that N − a ab N + 1 > (a4ab
+ b )2
N, φ( N ) > 45 N and N > 10d, where a and b are
small positive integers, plugging the conditions into above inequality (Equation (1)), we get,

e k N 2γ 1
− < (4ab) √ √ + 4
φ( N ) d a2 + b2 2
( a + b )2
N( ab N + 2 N) 5 (10d )
3
N 2γ− 2 1
< + 2.
4 8d
√ 3
Suppose that d < √3 N 4 − γ , then,
2

3
N 2γ− 2 1 1
+ 2 < 2.
4 8d 2d
Hence, we have,
e k 1
a2 + b2
√ − < 2.
N− N+1 d 2d
ab
k
This shows that Theorem 13 produces d as the convergent of the continued fraction expansion of
e
a2 + b2
√ . This terminates the proof.
N− ab N +1

3
This is an improvement on the work of Reference
√
[9], whose d < N 4 −γ . Also taking the value
of γ = 15
we have our decryption exponent d < √3 N 0.28125 ,
32 , 2
which is also an improvement on the
1 1
results of References [5,11] whose decryption exponents were d < 13 N 4 and d < 12 N 4 , respectively.
From Table 1 one can observe that our bound is an improvement of the abovementioned bounds.

Table 1. Comparison of the bounds on d for RSA modulus N = pq.

Authors Bound for d Assumed Interval for γ

1
1
[5] 3N Not applicable
4
3
[7] d < 18 N 4 −γ 0.25 ≤ γ < 0.5
1− γ
[8] d<N 2 0.25 ≤ γ < 0.5
3
[9] d <√N 4 −γ 0.25 ≤ γ < 0.5
√
1
[10] d < 66 2 N 4 Not applicable
1
[11] d <√ 12 N 4 Not applicable
3
Our result d < √3 N 4 − γ 0.25 ≤ γ < 0.5
2

15
Example 1. In this example, we illustrate how to factor the RSA modulus N = pq for the case γ = 32 =
0.46875. Let,
N = 26165530044163,

e = 20107848788311,
15 e√
and a = 3, b = 2,γ = 32 . Taking the continued fraction expansion of , we get,
N −d 13
6 N e+1

[0, 1, 3, 3, 7, 1, 1, 1, 4, 161, 2, 3, 1, 1, 1, 5, 1, 2, 2, 8, 4, 5, 1, 5, 26, 3]

Cryptography 2019, 3, 2 9 of 25

and their corresponding convergents are as follows,

3 10 73 83 156 239 1112 179,271 359,654 1,258,233 1,617,887 2,876,120

[0, 1, , , , , , , , , , , , , · · · ],
4 13 95 108 203 311 1447 233,278 468,003 1,637,287 2,105,290 3,742,577
k 1112
d = 1447 and computing,

1 + kφ( N )
= 20107848788311
d
φ( N ) = 26165519061768
N − φ( N ) + 1 = 10982396.

Finally, solving the quadratic equation x2 − ( N − φ( N ) + 1) x + N = 0 leads to the factorization

of N. This reveals the factors of N as p = 7488127
√
and q = 3494269. Taking the value of γ = 0.46875,
this shows that our bound increases to d < √3 N 0.28125 , that is, 1447 < 7274.146806. This shows that
2
our private key is greater than the bounds of References [5,11], i.e., 753.8954627 < 1147 < 7274.146806
(bound of Reference [5] ) and 1130.843194 < 1147 < 7274.146806 (bound of Reference [11]). This is an
improvement on bounds stated in Table 1.

a2 + b2
√
3.2. System of Equations Using N − ab N + 1 as Approximation of φ( N )
In this section, we present four cryptanalytic attacks on t RSA moduli Ns = ps qs using a system of
equations of the form es d − k s φ( Ns ) = 1, es ds − kφ( Ns ) = 1, es d − k s φ( Ns ) = zs , and es ds − kφ( Ns ) = zs
for s = 1, . . . , t, in which we successfully factor t RSA moduli in polynomial time for unknown positive
integers d, k s , zs , ds , and k for s = 1, . . . , t.

3.2.1. The Attack on t RSA Moduli Ns = ps qs Satisfying es d − k s φ( Ns ) = 1

Taking t ≥ 2, let Ns = ps qs , s = 1, . . . , t. The attack works for t instances ( Ns , es ) when there
exist an integer d and t integers k s satisfying equation es d − k s φ( Ns ) = 1. We show that prime
factors ps and qs of t RSA moduli Ns for s = 1, . . . , t can be found efficiently for N = max{ Ns } and
d < N γ , k s < N γ , for all γ = 2(3t3t+1) . In this case, the RSA instances shared common decryption
exponent d.

Theorem 14. Let Ns = ps qs be t RSA moduli for s = 1 . . . t and let (es , Ns ) be a public key pair and
(d, Ns ) be a private key pair such that es < φ( Ns ) and the relation es d ≡ 1 (mod φ( N )) is satisfied. Let
also N = max{ Ns }; if there exist positive integers d < N γ , k s < N γ , for all γ = 2(3t3t+1) such that
equation es d − k s φ( Ns ) = 1 holds, then prime factors of t RSA moduli Ns can be successfully recovered in
polynomial time.

Proof of Theorem 14. For t ≥ 2, and let Ns = ps qs , 1 ≤ s ≤ t be t moduli. Let N = max{ Ns } and
suppose that k s < N γ . Then equation es d − k s φ( Ns ) = 1 can be rewritten as,

es d − k s ( Ns − ( ps + qs ) + 1) =1
a2 + b2 √ a2 + b2 √
 
es d − k s Ns − Ns + Ns − ( Ns − φ( Ns ) + 1) + 1 =1
ab ab
2 + b2 √
 
es 1 − k s Ns − φ( Ns ) + 1 − a ab Ns
√ d − ks = 2 + b2 √ .
a2 + b2
Ns − ab Ns + 1 Ns − a ab Ns + 1

Let N = max{ Ns } and suppose that k s < N γ are positive integers and from Theorem 13, it was
shown that,
Cryptography 2019, 3, 2 10 of 25

a2 + b2 √ N 2γ
Ns + φ( Ns ) − Ns − 1 < 2 2 √
ab + b + 2) N
( a ab
a2 + b2 √ 4ab
Ns − Ns + 1 > N
ab ( a + b )2

2 + b2 √
   2 2√ 
1 − k s Ns − φ( Ns ) + 1 − a ab Ns 1 + k s a ab +b Ns − Ns + φ( Ns ) − 1
2 + b2 √ ≤ 2 + b2 √
Ns − a ab Ns + 1 Ns − a ab Ns + 1
 
N 2γ
1 + Nγ 2 + b2 √
( a ab +2) N
< 4ab
( a + b )2
N
1
1 + N 3γ− 2 −1
<
4
3
< bN 3γ− 2

We therefore have,
es 3
√ d − k s < bN 3γ− 2 .
a2 + b2
Ns − ab Ns +1
3
Hence, to show the existence of integer d and t integers k s we let ε = bN 3γ− 2 , with γ = 3t
2(3t+1)
.
Then, we have,
3 t
  3t
N γ εt = N γ bN 3γ− 2 = bt N γ+3γt− 2 = bt .
t ( t −3) t ( t −3)
Following Theorem 9, we have bt < 2 4 · 3t for t ≥ 2, then, we get N γ εt < 2 4 × 3t . It follows
t ( t −3)
that if d < N γ , then d < 2 4 × 3t × ε−t for s = 1, . . . , t. Finally,

es
√ d − k s < ε.
a2 + b2
Ns − ab Ns +1

This clearly satisfies the conditions of Theorem 9, and we proceed to reveal the private key d and
t integers k s for s = 1, . . . , t. Next, from equation es d − k s φ( Ns ) = 1 we compute,

es d − 1
φ( Ns ) =
ks
ps + qs = Ns − φ( Ns ) + 1.

Finally, by finding the roots of the quadratic equation x2 − ( Ns − φ( Ns ) + 1) x + Ns = 0, the prime

factors ps and qs can be revealed, which lead to the factorization of t RSA moduli Ns for s = 1, . . . , t in
polynomial time.

Let,
e1 e2 e3
X1 = √ , X2 = √ , X3 = √ .
a2 + b2 a2 + b2 a2 + b2
N1 − ab N1 +1 N2 − ab N2 +1 N3 − ab N3 +1

Define,
(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε − t −1 ] . (2)

Consider the lattice L spanned by the matrix,

Cryptography 2019, 3, 2 11 of 25

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T × X3 ]
 
0
 T 0 0 

M=



0 0 T 0 
 
0 0 0 T

Taking suitable small positive integers a and b, the matrix M can be used in computing the
reduced basis after we apply the LLL algorithm.

Example 2. In what follows, we give an illustration of how Theorem 14 works on three RSA moduli and their
corresponding public exponents,

Let N1 = 359072092653124553811906103878007890140989
N2 = 324883680116881280214836807152055627596063
N3 = 382594344895631082046807051393818596023693
e1 = 45375420344792168881455554779343580096391
e2 = 243789589028178310684702159604367474648551
e3 = 310614049489189851372469759955479934011591.

Observe that,

N = max{ N1 , N2 , N3 }
= 382594344895631082046807051393818596023693.

3t
By using a = 3, b = 2 and since t = 3, we will have from Algorithm 4 γ = 2(3t+1)
= 0.45 and
3
ε= bN 3γ− 2 = 0.000001157761794.

Algorithm 4 Theorem 14
1: Initialization: The public key tuple ( Ns , es , γ) satisfying Theorem 14.
2: Choose a, b and t to be suitable small positive integers and N = max{ Ns } for s = 1, . . . , t.
3: for any ( a, b, t, N, γ) do
3
4: ε := bN 3γ− 2
(t+1)(t−4)
5: T = [ 3t +1 × 2 4 × ε−t−1 ] for t ≥ 2.
6: end for
7: Consider the lattice L spanned by the matrix M as stated above.
8: Applying the LLL algorithm to L, we obtain the reduced basis matrix K.
9: for any ( M, K ) do
10: J :== M−1
11: Q = JK.
12: end for
13: Produce d, k s from Q
14: for each triplet (d, k s , es ) do
15: φ( Ns ) := es dk−s
1

16: Ws := Ns − φ( Ns ) + 1.
17: end for
18: Solve the quadratic equation x2 − Ws x + Ns = 0
19: return the prime factors ( ps , qs ).
Cryptography 2019, 3, 2 12 of 25

Applying Theorem 9 and using Algorithm 4 for n = t = 3, we compute,

(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε−t−1 ] = 22541258940000000000000000. (3)

Consider the lattice L spanned by the matrix,

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T × X3 ]
 
0
 T 0 0 

M= 


0 0 T 0 
 
0 0 0 T

Therefore, by applying the LLL algorithm to L, we obtain the reduced basis with the
following matrix,

−2034699965866566690 −2344404377412628796
 
2578263109750711 2580976588820297660
 2580976588820297660 −7038163058258067570 1213053071081376612 −4486161207788962020
K= 
 4247153090969385088 −4534704902749259520 12312546858704031232 7327527172122145280 
−8914983043342173506 −11071823379597700260 −645732543479046584 −645732543479046584

Next, from Algorithm 4 we compute Q = K · J,

 
2578263109750711 325811375370309 1934703841407202 2093195458460643
 9287723537945650383 1173676173123327666 6969418419258590716 7540355619851993530 
Q=
 7540355619851993530

536706585430991758 3187022832955722161 3448104860897526334 
−8914983043342173506 −1126573496618480874 −6689717536897095223 −7237741543135901521

From the first row of matrix Q, we obtain d, k1 , k2 , and k3 as follows,

d = 2578263109750711, k1 = 325811375370309, k2 = 1934703841407202, k3 = 2093195458460643

e s d −1
Using Algorithm 4, we now compute φ( Ns ) = ks for s = 1, 2, 3.

φ( N1 ) = 359072092653124553810707267684522589776000

φ( N2 ) = 324883680116881280213619313059216656916880

φ( N3 ) = 382594344895631082045445951038518440638400.

Next, from Algorithm 4 we proceed to compute Ws for s = 1, 2, 3.

W1 = 1198836193485300364990

W2 = 1217494092838970679184

W3 = 1361100355300155385294.

Finally, solving the quadratic equation x2 − Ws x + Ns = 0 for s = 1, 2, 3 yields ( p1 , q1 ), ( p2 , q2 ),

and ( p3 , q3 ), which lead to the factorization of three RSA moduli N1 , N2 , N3 .That is,

p1 = 614582596386772289501, q1 = 584253597098528075489

p2 = 822497570179231384793, q2 = 394996522659739294391

p3 = 964370894659814712593, q3 = 396729460640340672701.
Cryptography 2019, 3, 2 13 of 25

From our result, one can observe that we get d ≈ N 0.3706 , which is larger than Blömer–May’s
bound x < 31 N 0.25 , as reported in Reference [12]. Our d ≈ N 0.3706 is also larger than Nitaj et al.’s bound
d ≈ N 0.344 , as reported in Reference [13] .

3.2.2. The Attack on t RSA Moduli Ns = ps qs Satisfying es ds − kφ( Ns ) = 1

In this section, we consider a second case in which t RSA moduli satisfy t equations of the form
es ds − kφ( Ns ) = 1 for unknown positive integers ds and k for s = 1, . . . , t. In this case, every pair of the
RSA instances has its own unique decryption exponent ds .

Theorem 15. Let Ns = ps qs be t RSA moduli for s = 1, . . . , t and let (es , Ns ) be a public key pair and
(ds , Ns ) be a private key pair with es < φ( Ns ) and the given relation es ds ≡ 1 (mod φ( N )) is satisfied. Let e
= min{es } = N α be t public exponents; if there exist t integers ds < N γ , k < N γ , f or all γ = (21(+ 2α)t
3t+1)
such
that equation es ds − kφ( Ns ) = 1 holds, then t prime factors of RSA moduli Ns can be successfully recovered in
polynomial time.

Proof of Theorem 15. For t ≥ 3 and Ns = ps qs , be t RSA moduli. Let e = min{es } = N α be t public
exponents for s = 1, . . . , t and suppose that ds < N γ . Then, the equation es ds − kφ( Ns ) = 1 can be
rewritten as,

es ds − k( Ns − ( ps + qs ) + 1) = 1
a2 + b2 √ a2 + b2 √
 
es ds − k Ns − Ns + Ns − ( Ns − φ( Ns ) + 1) + 1 = 1
ab ab
2 + b2 √ √
   
a2 + b2
Ns − a ab Ns + 1 1 − k Ns − φ( Ns ) + 1 − ab Ns
k − ds = .
es es

Let N = max{ Ns } and ds < N γ , k < N γ be positive integers and from Theorem 13, it was
shown that,
a2 + b2 √ N 2γ
Ns + φ( Ns ) − Ns − 1 < 2 2 √ .
ab ( a + b + 2) N ab

Additionally, suppose that e = min{es } = Nα, then we have,


a2 + b2
√  
a2 + b2
√ 
1 − k Ns − φ( Ns ) + 1 − ab Ns 1+k ab Ns − Ns + φ( Ns ) − 1
≤
es es
 
N 2γ
1 + Nγ 2 + b2 √
( a ab +2) N
<
Nα
√ 1
< 8N 3γ− 2 −α .

Hence, we get, 
a2 + b2
√ 
Ns − ab Ns + 1 √ 1
k − ds < 8N 3γ− 2 −α .
es
√ 1
We now proceed to show the existence of integer k and t integers ds . Let ε = 8N 3γ− 2 −α and
(1+2α)t
γ = 2(3t+1) . Then, we get,

√ 1
t t t t
N γ εt = N γ 8N 3γ− 2 −α = 8 2 N γ+3γt− 2 −αt = 8 2 .
Cryptography 2019, 3, 2 14 of 25

t t ( t −3) t ( t −3)
Following Theorem 9, we have 8 2 < 2 4 · 3t for t ≥ 3, then we get N γ εt < 2 4 · 3t . It follows
t ( t −3)
that if k < N γ and following Theorem 9, we have k < 2 4 × 3t × ε−t for s = 1, . . . , t. Finally,

a2 + b2
√ 
Ns − ab Ns + 1
k − ds < ε.
es

This clearly satisfies the conditions of Theorem 9, and we proceed to reveal t integers of the
private key ds and integer k for s = 1, . . . , t. Next, from equation es ds − kφ( Ns ) = 1 we compute,

es ds − 1
φ( Ns ) =
k
ps + qs = Ns − φ( Ns ) + 1.

Finally, by finding the roots of the quadratic equation x2 − ( Ns − φ( Ns ) + 1) x + Ns = 0, the prime

factors ps and qs can be found, which lead to the factorization of t RSA moduli Ns for s = 1, . . . , t.

Let,

a2 + b2
√ a2 + b2
√ a2 + b2
√
N1 − ab N1 + 1 N2 − ab N2 + 1 N3 − ab N3 + 1
X1 = , X2 = , X3 = .
e1 e2 e3

Define,
(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε − t −1 ] . (4)

Consider the lattice L spanned by the matrix,

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T ( X3 )]
 
0
 T 0 0 

M= 


0 0 T 0 
 
0 0 0 T

Taking suitable small positive integers a and b, the matrix M can be used in computing the
reduced basis after we apply the LLL algorithm

Example 3. In what follows, we give a numerical example to illustrate how our attack of Theorem 15 works on
three RSA Moduli. We consider the following three RSA moduli and their corresponding public exponents,

N1 = 163889671902988443382883271210955564227203

N2 = 1148623006222285920602264446698309119625517

N3 = 958230896880440803103514702761136188985911

e1 = 102148699518319970718711207616780801429013

e2 = 555369481273226483312414829199486063579195

e3 = 2947238068713166701798078609368273575653161.
Cryptography 2019, 3, 2 15 of 25

Observe that ,

N = max{ N1 , N2 , N3 }
= 1148623006222285920602264446698309119625517
es = min{e1 , e2 , e3 }
= 102148699518319970718711207616780801429013,

with es = min{e1 , e2 , e3 } = N α with α = 0.9750133088. By using a = 3, b = 2 and since t = 3, we will

(1+2α)t √ 1
have from Algorithm 5 γ = 2(3t+1) = 0.44250 and ε = 8N 3γ− 2 −α = 0.000001768531652.
Applying Theorem 9 and using Algorithm 5, we compute,
(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε−t−1 ] = 4140031786000000000000000.

Algorithm 5 Theorem 15
1: Initialization: The public key tuple ( Ns , es , α, γ) satisfying Theorem 15.
2: Choose a, b and t to be suitable small positive integers and N = max{ Ns } for s = 1, . . . , t.
3: for any √( a, b, t, N, α, γ) do
1
4: ε = 8N 3γ− 2 −α
5: e =: min{es } := N α
(t+1)(t−4)
6: T = [ 3t +1 × 2 4 × ε−t−1 ] for t ≥ 2.
7: end for
8: Consider the lattice L spanned by the matrix M as stated above.
9: Applying the LLL algorithm to L, we obtain the reduced basis matrix K.
10: for any ( M, K ) do
11: J :== M−1
12: Q = JK.
13: end for
14: Produce ds , k from Q
15: for each triplet (ds , k, es ) do
16: φ( Ns ) := es dks −1
17: Ws := Ns − φ( Ns ) + 1.
18: end for
19: Solve the quadratic equation x2 − Ws x + Ns = 0
20: return the prime factors ( ps , qs ).

Consider the lattice L spanned by the matrix,

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T ( X3 )]
 
0
 T 0 0 

M= 


0 0 T 0 
 
0 0 0 T

Therefore, by applying the LLL algorithm to L, we obtain the reduced basis with the
following matrix,
 
1944662874609887749 739703099714239590 345516048415097753 75220223065832636
 −312939819716059 3078110579756278310 −414033376574202823 −67328478162817476 
K= 
 641396426019740525 −1430247980684822250 −660964237954996575 −2681843509732748900
−893602997419446810 1688910391195682900 3790386709273250430 −350853801896118840
Cryptography 2019, 3, 2 16 of 25

Next, from Algorithm 5, we compute Q = K · J,

 
1944662874609887749 3120060871891740871 4021979227238758337 632265194403229474
 −312939819716059 −502087688051741 −647226555670387 −101745633411641 
Q=
 641396426019740525

1029070857639965612 1326545148548731842 208536215341829039 
−893602997419446810 −1433716755565101613 −1848162342143902764 −290535742857772536

From the second row of matrix Q, we obtain k, d1 , d2 , and d3 as follows,

k = 312939819716059, d1 = 502087688051741, d2 = 647226555670387, d3 = 101745633411641.

e s d s −1
Using Algorithm 5, we compute φ( Ns ) = k for s = 1, 2, 3. That is,

φ( N1 ) = 163889671902988443381763445058591755881248

φ( N2 ) = 1148623006222285920600119881462113872455296

φ( N3 ) = 958230896880440803101547264462074637000800.

Next, from Algorithm 5 we proceed to compute Ws for s = 1, 2, 3.

W1 = 1119826152363808345956

W2 = 2144565236195247170222

W3 = 1967438299061551985112.

Finally, solving the quadratic equation x2 − Ws x + Ns = 0 for s = 1, 2, 3 yields ( p1 , q1 ), ( p2 , q2 ),

and ( p3 , q3 ) which lead to the factorization of three RSA moduli N1 , N2 , N3 . That is,

p1 = 946711448692045925137, q1 = 173114703671762420819

p2 = 1106444100091356676813, q2 = 1038121136103890493409

p3 = 1081045755724110472721, q3 = 886392543337441512391.

From our result, one can observe that we get min{d1 , d2 , d3 } ≈ N 0.333 , which is larger than
Blömer–May’s bound x < 13 N 0.25 , as reported in Reference [12].

3.2.3. The Attack on t RSA Moduli Ns = ps qs Satisfying es d − k s φ( Ns ) = zs

In this section, we consider another case in which t RSA moduli satisfies t equations of the form
es ds − kφ( Ns ) = zs for unknown positive integers ds , k, and zs for s = 1, . . . , t.
For t ≥ 2, let Ns = ps qs , for = 1, . . . , t. The attack works for t instances ( Ns , es ) if there exist an
integer d and t integers k s such that es d − k s φ( Ns ) = zs holds. We show that prime factors ps and qs
of t RSA moduli Ns for s = 1, . . . , t can be found efficiently for N = max{ Ns } and d, k s , and zs < N γ
for all γ = 2(4t3t+1) for unknown positive integers d, k s , and zs . In this case, the RSA instances shared a
common decryption exponent d.

Theorem 16. Let Ns = ps qs be RSA moduli for s = 1, · · · , t and let the pair (es , Ns ) be public keys and
(d, Ns ) bea private key with es < φ( Ns ) and the given relation es d ≡ zs (mod φ( Ns )) is satisfied. Let N
= max{ Ns } for s = 1, . . . , t. If there exist integers d < N γ , k s < N γ , f or all γ = 2(4t3t+1) such that
equation es d − k s φ( Ns ) = zs holds, then the prime factors of t RSA moduli Ns can be successfully recovered in
polynomial time.
Cryptography 2019, 3, 2 17 of 25

Proof of Theorem 16. For t ≥ 2, and let Ns = ps qs , 1 ≤ s ≤ t be t RSA moduli. Let N = max{ Ns } and
suppose that k s < N γ . Then equation es d − k s φ( Ns ) = zs can be rewritten as,

es d − k s ( Ns − ( ps + qs ) + 1) = zs
a2 + b2 √ a2 + b2 √
 
es d − k s Ns − Ns + Ns − ( Ns − φ( Ns ) + 1) + 1 = zs
ab ab

2 + b2 √
 
es zs − k s Ns − φ( Ns ) + 1 − a ab Ns
√ d − ks = 2 + b2 √ . (5)
a2 + b2
Ns − ab Ns +1 Ns − a ab Ns + 1

Taking N = max{ Ns } and suppose that k s < N γ , zs < N γ are positive integers and from
Theorem 13, it was shown that,

a2 + b2 √ N 2γ
Ns + φ( Ns ) − Ns − 1 < 2 2 √
ab + b + 2) N
( a ab
a2 + b2 √ 4ab
Ns − Ns + 1 > N.
ab ( a + b )2

Plugging into Equation (5) yields,

2 + b2 √
   2 2√ 
zs − k s Ns − φ( Ns ) + 1 − a ab Ns ) zs + k s a ab +b Ns − Ns + φ( Ns ) − 1 )
2 + b2 √ ≤ 2 + b2 √
Ns − a ab Ns + 1 Ns − a ab Ns + 1
 
N 2γ
Nγ + Nγ a 2 + b2 √
( ab +2) N
< 4ab
( a + b )2
N
3
< bN 4γ− 2 .

Hence, we have,
es 3
√ d − k s < bN 4γ− 2 .
a2 + b2
Ns − ab Ns +1
3
Hence, to show the existence of integer d and t integers k s , we let ε = bN 4γ− 2 , with γ = 3t
2(4t+1)
.
Then,we have:
3 t
  3t
N γ εt = N γ bN 4γ− 2 = bt N γ+4γt− 2 = bt .
t ( t −3) t ( t −3)
Following Theorem 9, we have bt < 2 4 × 3t for t ≥ 2, then we get N γ εt < 2 4 × 3t . It follows
t ( t −3)
that if d < N γ , then d < 2 4 × 3t × ε−t for s = 1, . . . , t. Finally,

es
√ d − k s < ε.
a2 + b2
Ns − ab Ns +1

This also satisfies the conditions of Theorem 9, and we next proceed to reveal the private key d
and t integers k s for s = 1, . . . , t. Next, from equation es d − k s φ( Ns ) = zs we compute,

es d − zs
φ( Ns ) =
ks
ps + qs = Ns − φ( Ns ) + 1.
Cryptography 2019, 3, 2 18 of 25

Finally, by finding the roots of the quadratic equation x2 − ( Ns − φ( Ns ) + 1) x + Ns = 0, prime

factors ps and qs can be revealed, which lead to the factorization of t RSA moduli Ns for s = 1, . . . , t in
polynomial time.

Let,
e1 e2 e3
X1 = √ , X2 = √ , X3 = √ .
a2 + b2 a2 + b2 a2 + b2
N1 − ab N1 +1 N2 − ab N2 +1 N3 − ab N3 +1

Define,
(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε − t −1 ] . (6)

Consider the lattice L spanned by the matrix,

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T ( X3 )]
 
0
 T 0 0 

M= 


0 0 T 0 
 
0 0 0 T

Taking suitable small positive integers a and b, the matrix M can be used in computing the
reduced basis after we apply the LLL algorithm.

Example 4. In what follows, we give a numerical example to illustrate how our attack of Theorem 16 works on
t RSA Moduli. We consider the following three RSA moduli and their corresponding public exponents,

Let N1 = 330296126221226061978488805127502203372577
N2 = 187396362359066080307391868109309718740567
N3 = 216436372402461777072305279786697609409967
e1 = 302169635060396919768302245253373846319703
e2 = 91199418785305795947645004809998556532621
e3 = 162134135066593548250015517503190950433936.

Observe that,

N = max{ N1 , N2 , N3 }
= 330296126221226061978488805127502203372577.

3t
By using a = 3, b = 2 and since t = 3, we will have from Algorithm 6 γ = 2(4t+1)
= 0.346 and
ε = bN 3γ− 23 = 0.00003240252930. Applying Theorem 9 and Algorithm 6 for n = t = 3 we compute,
(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε−t−1 ] = 36740018900000000000.
Cryptography 2019, 3, 2 19 of 25

Algorithm 6 Theorem 16
1: Initialization: The public key tuple ( Ns , es , zs , γ) satisfying Theorem 16.
2: Choose a, b and t to be suitable small positive integers and N = max{ Ns } for s = 1, . . . , t.
3: for any ( a, b, t, N, γ) do
3
4: ε = bN 3γ− 2
(t+1)(t−4)
5: T = [ 3t +1 × 2 4 × ε−t−1 ] for t ≥ 2.
6: end for
7: Consider the lattice L spanned by the matrix M as stated above.
8: Applying the LLL algorithm to L, we obtain the reduced basis matrix K.
9: for any ( M, K ) do
10: J :== M−1
11: Q = JK.
12: end for
13: Produce d, k s from Q
14: for each triplet (d, k s , es , zs ) do
15: φ( Ns ) := es dk−s zs
16: Ws := Ns − φ( Ns ) + 1.
17: end for
18: Solve the quadratic equation x2 − Ws x + Ns = 0
19: return the prime factors ( ps , qs ).

Consider the lattice L spanned by the matrix

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T ( X3 )]
 
0
 T 0 0 

M= 


0 0 T 0 
 
0 0 0 T

Therefore, by applying the LLL algorithm to L, we obtain the reduced basis with the
following matrix,
 
221202829045687 93563315351041 100537693381434 43249006678519
 219137979005996 215228853099828 −366048772777528 36384754276652 
K=
 
−15192444691558 −450517287777994

9761598838844 503486112156954 
337933481607001 −490633444109457 −161755868358618 −208327724754663

Next, from Algorithm 6, we compute Q = K · J,

 
221202829045687 202366218737588 107651873220345 165704724042021
 219137979005996 200477201781543 106646981123572 164157929150241 
Q=
 
−15192444691558 −13898726335799 −7393644723707 −11380776032563


337933481607001 309156628568763 164460700958544 253148544961339

From the first row of matrix Q, one can observe that we obtain d, k1 , k2 , and k3 as follows,

d = 221202829045687, k1 = 202366218737588, k2 = 107651873220345, k3 = 165704724042021.

es d − zs
Using Algorithm 6, we compute φ( Ns ) = ks for s = 1, 2, 3 where z1 , z2 , z3 are,

z1 = 78214488852833, z2 = 81546995635627, z3 = 268274979696656

Cryptography 2019, 3, 2 20 of 25

φ( N1 ) = 330296126221226061977286874278835760293956

φ( N2 ) = 187396362359066080306393381432741963476000

φ( N3 ) = 216436372402461777071093307335033501180256.

Next, from Algorithm 6, we compute Ws for s = 1, 2, 3.

W1 = 1201930848666443078622

W2 = 998486676567755264568

W3 = 1211972451664108229712.

Finally, solving the quadratic equation x2 − Ws x + Ns = 0 for s = 1, 2, 3 yields ( p1 , q1 ), ( p2 , q2 ),

and ( p3 , q3 ) which lead to the factorization of three RSA moduli N1 , N2 , N3 . That is,

p1 = 776645004884812569823, q1 = 425285843781630508799

p2 = 747935011770876784817, q2 = 250551664796878479751

p3 = 994294007747013311743, q3 = 217678443917094917969.

From our result, one can observe that we get d ≈ N 0.3455 , which is larger than Blömer–May’s
bound x < 31 N 0.25 , as reported in Reference [12]. Our d ≈ N 0.3455 is also larger than Nitaj et al.’s bound
x ≈ N 0.344 , as reported in Reference [13].

3.2.4. The Attack on t RSA Moduli Ns = ps qs Satisfying es ds − kφ( Ns ) = zs

In this section, we present another case in which t RSA moduli satisfies t equations of the
form es ds − kφ( Ns ) = zs for unknown positive integers ds , k, and zs for s = 1, . . . , t, which can be
simultaneously factored in polynomial time. In this case, every pair of the RSA instances has its own
unique decryption exponent ds .

Theorem 17. Let Ns = ps qs be t RSA moduli for s = 1, · · · , t and let (es , Ns ) be a public key pair and (ds , Ns )
be a private key pair with condition es < φ( Ns ) and the given relation es ds ≡ zs (mod φ( Ns )) is satisfied. Let e
= min{es } = N α be t public exponents. If there exist positive integers ds < N γ , k < N γ , f or all γ = (21(+ 2α)t
4t+1)
such that the equation es ds − kφ( Ns ) = zs holds, then t prime factors of RSA moduli Ns can be found
successfully in polynomial time.

Proof of Theorem 17. For t ≥ 3 and suppose Ns = ps qs to be t RSA moduli for s = 1, . . . , t . Suppose
that e = min{es } = N α are t public exponents and suppose that ds < N γ . Then, equation es ds −
kφ( Ns ) = zs can be rewritten as,

es ds − k( Ns − ( ps + qs ) + 1) = zs
a2 + b2 √ a2 + b2 √
 
es ds − k Ns − Ns + Ns − ( Ns − φ( Ns ) + 1) + 1 = zs
ab ab
2 + b2 √ √
   
a2 + b2
Ns − a ab Ns + 1 zs − k Ns − φ( Ns ) + 1 − ab Ns
k − ds = .
es es
Cryptography 2019, 3, 2 21 of 25

Let N = max{ Ns } for s = 1, · · · , t, and ds < N γ , k < N γ , zs < N γ be positive integers and
√
a2 + b2 2γ
ab Ns + φ( Ns ) − Ns − 1 < a2 +bN 2 √ , e = min{ es } = N , then we have,
α
( ab +2) N

a2 + b2
√  
a2 + b2
√ 
zs − k Ns − φ( Ns ) + 1 − ab Ns zs + k ab Ns − Ns + φ( Ns ) − 1
≤
es es
 
N 2γ
Nγ + Nγ 2 + b2 √
( a ab +2) N
<
r Nα
a 3γ− 1 −α
< N 2 .
b

Hence, we get, 
a2 + b2
√ 
Ns − ab Ns + 1 r
a 3γ− 1 −α
k − ds < N 2 .
es b
q
a 3γ− 12 −α
We now proceed to show the existence of integer k and t integers ds . Let ε = bN and
(1+2α)t
γ= 2(4t+1)
. Then, we get,

r t at at
a 3γ− 1 −α 2 t 2
Nγ εj = Nγ N 2 = N γ+3γt− 2 −αt = .
b b b

a

t t ( t −3) t ( t −3)
Following Theorem 9, we have b
2 <2 4 × 3t for t ≥ 2, then we get N γ εt < 2 4 × 3t . It
t ( t −3)
follows that if k < N γ , then k < 2 4 × 3t × ε−t for s = 1, . . . , t. Finally,
2 + b2 √
 
Ns − a ab Ns + 1
k − ds < ε.
es

This satisfies the conditions of Theorem 9 and we proceed to find the values of ds and k for
s = 1, . . . , t. Next, from the equation es ds − kφ( Ns ) = zs we compute,

es ds − zs
φ( Ns ) =
k
ps + qs = Ns − φ( Ns ) + 1

Finally, by finding the roots of the quadratic equation x2 − ( Ns − φ( Ns ) + 1) x + Ns = 0, the prime

factors ps and qs can be found, which lead to the factorization of t RSA moduli Ns for s = 1, . . . , t.

Let,

a2 + b2
√ a2 + b2
√ a2 + b2
√
N1 − ab N1 + 1 N2 − ab N2 + 1 N3 − ab N3 + 1
X1 = , X2 = X3 =
e1 e2 e3

Define,
(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε − t −1 ] . (7)

Consider the lattice L spanned by the matrix,

Cryptography 2019, 3, 2 22 of 25

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T ( X3 )]
 
0
 T 0 0 

M=



0 0 T 0 
 
0 0 0 T

Taking suitable small positive integers a and b, the matrix M can be used in computing the
reduced basis after we apply the LLL algorithm.

Algorithm 7 Theorem 17
1: Initialization: The public key tuple ( Ns , es , zs , α, γ) satisfying Theorem 17.
2: Choose a, b and t to be suitable small positive integers and N = max{ Ns } for s = 1, . . . , t.
3: for any q( a, b, t, N, γ) do
1
4: ε = ba N 3γ− 2 −α
5: e =: min{es } := N α
(t+1)(t−4)
6: T = [ 3t +1 × 2 4 × ε−t−1 ] for t ≥ 2.
7: end for
8: Consider the lattice L spanned by the matrix M as stated above.
9: Applying the LLL algorithm to L, we obtain the reduced basis matrix K.
10: for any ( M, K ) do
11: J :== M−1
12: Q = JK.
13: end for
14: Produce ds , k from Q
15: for each triplet (ds , k, es , zs ) do
16: φ( Ns ) := es dsk−zs
17: Ws := Ns − φ( Ns ) + 1.
18: end for
19: Solve the quadratic equation x2 − Ws x + Ns = 0
20: return the prime factors ( ps , qs ).

Example 5. In what follows, we give a numerical example to illustrate how our attack of Theorem 17 works on
t RSA Moduli. We consider the following three RSA moduli and their corresponding public exponents,

N1 = 336942490676287248746778854034851937369893

N2 = 668105444816109132056919917066428038906749

N3 = 639755280744251044114047220423078131849607

e1 = 216385769902449684764280685469492987883161

e2 = 2771656074511409731272546199640816528153287

e3 = 1987635316084364424107099117207438936875885.

Observe that,

N = max{ N1 , N2 , N3 }
= 668105444816109132056919917066428038906749
es = min{e1 , e2 e3 }
= 216385769902449684764280685469492987883161,
Cryptography 2019, 3, 2 23 of 25

with es = min{e1 , e2 , e3 } = N α for α = 0.9882936490. By using

q a = 3, b = 2 and since t = 3, we will
(1+2α) j 1
have from Algorithm 7 γ = 2(4t+1) = 0.3434523805 and ε = ba N 3γ− 2 −α = 0.00001994181860.
Applying Theorem 9 and using Algorithm 7, we compute,
(t+1)(t−4)
T = [ 3t +1 × 2 4 × ε−t−1 ] = 256091979900000000000.

Consider the lattice L spanned by the matrix,

 
1 −[ T ( X1 )] −[ T ( X2 )] −[ T ( X3 )]
 
0
 T 0 0 

M= 


0 0 T 0 
 
0 0 0 T

Therefore, by applying the LLL algorithm to L, we obtain the reduced basis with the
following matrix,
 
475374059459089 −261893631007311 −36395361888534 −199732740251281
−1289880599128957 −2285004592985757 −1543204053684258 795956829369853 
 
K=
−1037212131324544

 196749388649856 −1127770407188736 −2527706537969024

1215125997180921 973858878471321 −2293826172011526 1849797988697991

Next, from Algorithm 7 we compute Q = K · J,

 
475374059459089 740222980786823 114588530795597 153007476978677
 
−1289880599128957 −2008522011135318 −310924670404006 −415170689585032
Q=
 

−1037212131324544 −1615082355210807 −250019141530540 −333844912543661
 
1215125997180921 1892118784706700 292905134341853 391109610085597

From the first row of matrix J, one can observe that we obtain k, d1 , d2 , and d3 as follows,

k = 475374059459089, d1 = 740222980786823, d2 = 114588530795597, d3 = 153007476978677.

es ds − zs
Using Algorithm 7, we compute φ( Ns ) = k for s = 1, 2, 3, where z1 , z2 , z3 are,

z1 = 254677352608291, z2 = 170274159918143, z3 = 138475454795345

φ( N1 ) = 336942490676287248745614825672641206658508

φ( N2 ) = 668105444816109132055284112629804447897564

φ( N3 ) = 639755280744251044112444603349851200819200.

Next, from Algorithm 7 we compute Ws for s = 1, 2, 3.

W1 = 1164028362210730711386

W2 = 1635804436623591009186

W3 = 1602617073226931030408.
Cryptography 2019, 3, 2 24 of 25

Finally, solving the quadratic equation x2 − ( Ns − Ws x + Ns = 0 for s = 1, 2, 3 yields ( p1 , q1 ),

( p2 , q2 ), and ( p3 , q3 ), which lead to the factorization of three RSA moduli N1 , N2 , N3 . That is,

p1 = 624417203774295157627, q1 = 539611158436435553759

p2 = 847203991351099142923, q2 = 788600445272491866263

p3 = 849683014443852067207, q3 = 752934058783078963201.

From our result, one can observe that we get min{d1 , d2 , d3 } ≈ N 0.336 , which is larger than
Blömer–May’s bound x < 13 N 0.25 , as reported in Reference [12].

4. Conclusions
In this paper, it has been shown that our proposed cryptanalytic attacks on RSA modulus N = pq
2 + b2 √
using the prime difference method can be used efficiently. The use of N − a ab N + 1 as a good
approximation
√
of φ( N ) is necessary as we have discovered a short decryption exponent bound
3
d < √3 N 4 −γ as a right candidate from the convergents of the continued fraction expansion of
2
e
a 2 + b2 √ that led to the successful factorization of the RSA modulus in polynomial time. This
N − ab N +1
paper also reported instances of factoring t RSA moduli by transforming generalized key equations
es d − k s φ( Ns ) = 1, es ds − kφ( Ns ) = 1, es d − k s φ( Ns ) = zs , and es ds − kφ( Ns ) = zs , where s = 1, . . . , t
into a simultaneous Diophantine approximations problem and later applied the LLL and lattice basis
reduction methods, which produced a reduced basis that yielded the values of d, k s , ds k, and zs . Finally,
we computed φ( Ns ) and solved a system of quadratic equation x2 − ( Ns − φ( Ns ) + 1) x + Ns = 0 for
s = 1, 2, 3, which produce the roots ( p1 , q1 ), ( p2 , q2 ), and ( p3 , q3 ) as prime factors of t RSA moduli
N1 , N2 , N3 . In all the four attacks presented on t instances of RSA moduli Ns = ps qs , we have improved
the short secret exponent bound.

Author Contributions: All the authors made substantial contributions in the development of this paper.
M.R.K.A. and S.I.A. oversaw the paper from its introduction to its conclusion. M.A.A. provided insight into the
conceptualization of the paper and also into running the Maple for numerical examples, as contained in the paper.
F.Y. provided thorough revision, including punctuations of the paper and made useful suggestions in improving
the quality of the paper.
Funding: This research work is funded by the Fundamental Research Grant Scheme [02-01-15-1745FR] provided
by the Ministry of Higher Education, Malaysia.
Conflicts of Interest: The authors declare no conflict of interest.

References
1. Rivest, R.L.; Shamir, A.; Adleman, L. A method for obtaining digital signatures and public-key cryptosystems.
Commun. ACM 1978, 21, 120–126.
2. Dubey, M.K.; Ratan, R.; Verma, N.; Saxena, P.K. Cryptanalytic Attacks and Countermeasures on RSA. In
Proceedings of the Third International Conference on Soft Computing for Problem Solving; Springer: New Delhi,
India, 2014; pp. 805–819.
3. Bach, E.; Miller, G.; Shallit, J. Sums of divisors, perfect numbers and factoring. SIAM J. Comput. 1986, 15,
1143–1154.
4. Hinek, M.J. Cryptanalysis of RSA and Its Variants; Chapman and Hall/CRC: Boca Raton, FL, USA, 2009.
5. Wiener, M. Cryptanalysis of Short RSA Secret Exponents. IEEE Trans. Inform. Theory 1990, 36, 553–558.
6. Boneh, D.; Glenn, D. Cryptanalysis of RSA with private key d less than N 0.292 . IEEE Trans. Inf. Theory 2000,
46, 1339–1349.
7. De Weger, B. Cryptanalysis of RSA with small prime difference. Appl. Algebra Eng. Commun. Comput. 2002,
13, 17–28.
8. Maitra, S.; Sarkar, S. Revisiting Wiener’s attack–new weak keys in RSA. In International Conference on
Information Security; Springer: Berlin/Heidelberg, Germany, 2008; pp. 228–243.
Cryptography 2019, 3, 2 25 of 25

9. Chen, C.Y.; Hsueh, C.C.; Lin, Y.F. A Generalization of de Weger’s Method. In Proceedings of the 2009 Fifth
International Conference on Information Assurance and Security, Xi’an, China, 18–20 August 2009; Volume 1,
pp. 344–347.
10. Nitaj, A. Diophantine and lattice cryptanalysis of the RSA cryptosystem. In Artificial Intelligence, Evolutionary
Computing and Metaheuristics; Springer: Berlin/Heidelberg, Germany, 2013; pp. 139–168.
11. Asbullah, M.A. Cryptanalysis on the Modulus N = p2 q and the Design of Rabin Cryptosystem without
Decryption Failure. Ph.D. Thesis, Universiti Putra Malaysia, Selangor, Malaysia, 2015.
12. Blömer, J.; May, A. A generalized Wiener attack on RSA. In International Workshop on Public Key Cryptography;
Springer: Berlin/Heidelberg, Germany, 2004; pp. 1–13.
13. Nitaj, A.; Ariffin, M.R.; Nassr, D.I.; Bahig, H.M. New attacks on the RSA cryptosystem. In International
Conference on Cryptology in Africa; Springer, Cham, Switzerland, 2014; pp. 178–198.
14. Wang, X.; Xu, G.; Wang, M.; Meng, X. Mathematical Foundations of Public Key Cryptography; CRC Press:
Boca Raton, FL, USA, 2016.
15. Lenstra, A.K.; Lenstra, H.W.; Lovász, L. Factoring polynomials with rational coefficients. Mathematische
Annalen 1982, 261, 515–534.

c 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access
article distributed under the terms and conditions of the Creative Commons Attribution
(CC BY) license (http://creativecommons.org/licenses/by/4.0/).