Deterministic Polynomial-time Equivalence of Computing the CRT-RSA Secret Keys and Factoring

Let N = pq be the product of two large primes. Consider Chinese remainder theorem-Rivest, Shamir, Adleman (CRT-RSA) with the public encryption exponent e and private decryption exponents dp, dq. It is well known that given any one of dp or dq (or both) one can factorise N in probabilistic poly(log N) time with success probability almost equal to 1. Though this serves all the practical purposes, from theoretical point of view, this is not a deterministic polynomial time algorithm. In this paper, we present a lattice-based deterministic poly(log N) time algorithm that uses both dp, dq   (in addition to the public information e, N) to factorise N for certain ranges of dp, dq. We like to stress that proving the equivalence for all the values of dp, dq may be a nontrivial task.

Keywords:    CRT-RSAcryptanalysisfactorisationLLL algorithmRSA

RSA17 is one of the most popular cryptosystems in the history of cryptology. Let us briefly describe the idea of RSA as follows:

• primes p, q, with q<p< 2q,
• N = pq, φ(N) = (p − 1)(q − 1),
• e, d are such that ed =1+ k φ(N), k ≥ 1,
• N, e are publicly available and plaintext M is encrypted as CMe mod N,
• The secret key d is required to decrypt the ciphertext as
MCd mod N.

The study of RSA is one of the most attractive areas in cryptology research as evident from many excellent works1,10,15. Rivest17, et al. itself presents a probabilistic polynomial time algorithm that on input N, e, d provides the factorisation of N; this is based on the technique provided by Miller16,18. It has been proved7,14 that given N, e, d, one can factor N in deterministic poly(log N) time provided edN2 .

Speeding up RSA encryption and decryption is of serious interest and for large N as both e, d cannot be small at the same time. For fast encryption, it is possible to use smaller e, e.g., the value as small as 216 + 1 is widely believed to be a good candidate. For fast decryption, the value of d needs to be small. However, Wiener19 showed that for $d<\frac{1}{3}{N}^{\frac{1}{4}}$ , N can be factorised easily. Later, Boneh-Durfee2 increased this bound up to d<N0.292. Thus, use of smaller d is in general not recommended. In this direction, an alternative approach has been proposed by Wiener19 exploiting the Chinese Remainder Theorem (CRT) for faster decryption. The idea is as follows:

• the public exponent e and the private CRT exponents dp and dq are used satisfying edp ≡ 1 mod (p − 1) and edq ≡ 1 mod (q − 1),
• the encryption is same as standard RSA,
• to decrypt a ciphertext C one needs to compute ${M}_{\text{1}}\equiv {C}^{{d}_{p}}$ mod p and ${M}_{\text{2}}\equiv {C}^{{d}_{q}}$ mod q,
• using CRT, one can get the plain text $M\in {ℤ}_{N}$ such that MM1 mod p and MM2 mod q.

This variant of RSA is popularly known as CRT-RSA. One may refer to Jochemsz & May12 and the references therein for state-of-the-art analysis on CRT-RSA.

Let us now outline the organization of this paper. Some preliminaries required in this area are discussed in section 1.1 and 1.2. A lattice-based technique was used to show that one can factorise N in deterministic polynomial time from the knowledge of N, e, dp , dq for certain ranges of dp , dq. Section 3 concludes the paper.

1.1   Probabilistic Polynomial Time Algorithm

Given N, e and any one of dp , dq (or both), there exists a well known solution to factorise N in probabilistic poly(log N) time with probability almost 1. An important work in this direction shows that with the availability of decryption oracle under a fault model, one can factorise N in poly(log N) time [3,Section 2,2] and the idea has been improved by Lenstra13.

Without loss of generality, consider that dp is available. One can pick any random integer W in [2, N − 1]. If gcd(W, N) ≠ 1, then we already have one of the factors. Else, we consider gcd (${W}^{e{d}_{p}-1}-1$ , N). First note that p divides. This is because, edp ≡ 1 mod (p − 1), i.e., edp − 1= k(p − 1) for some positive integer k and hence ${W}^{e{d}_{p}-1}-1$ =Wk(p−1)−1 is divisible by ${W}^{e{d}_{p}-1}-1$ p. Thus if q does not divide ${W}^{e{d}_{p}-1}-1$  then

gcd(${W}^{e{d}_{p}-1}-1$ , N) = p (this happens with probability almost equal to 1). If q too divides ${W}^{e{d}_{p}-1}-1$ , then gcd(${W}^{e{d}_{p}-1}-1$ , N) = N and the factorisation is not possible (this happens with a very low probability).

Thus, when both dp, dq are available, one can calculate both gcd(${W}^{e{d}_{p}-1}-1$ , N) and gcd(${W}^{e{d}_{q}-1}-1$ , N). If both of them are N (which happens with a very low probability) then the factorisation is not possible by this method.

Given e, dp, dq and N, let us deﬁne,
T e,dp ,dq ,N = {W $\in$ [2, N − 1]| gcd(W, N)=1,
gcd(${W}^{e{d}_{p}-1}-1$ , N) = N and gcd(${W}^{e{d}_{p}-1}-1$ , N) = N}
T e,dp,N = {W$\in$ [2, N − 1]| gcd(W, N)=1,
gcd(${W}^{e{d}_{p}-1}-1$ , N) = N} and
T e,dq,N = {W $\in$ [2, N − 1]|
gcd(W, N)=1, gcd(${W}^{e{d}_{p}-1}-1$ , N) = N}.

Table 1.Cardinality of Te,dp,dq,N : some toy examples

It is easy to note that Te,dp,dq,N = Te,dp,NTe,dq,N . Let us now provide some examples in Table 1. It is clear that while |Te,dp,dq,N | is quite large for one prime-pair, it is very small for the other.

Proposition 1

Consider CRT-RSA with N = pq, encryption exponent e and decryption exponents dp and dq. Let g1 = gcd(p−1, q −1),
gp=gcd(edp−1, q−1), gq = gcd(edq −1, p−1) and ge = gcd(edp − 1, edq − 1). Then |Te,dp,N| = gp(p − 1) − 1, |Te,dq,N| = gq(q − 1) − 1 and |Te,dp ,dq ,N| = gp gq − 1. Further, ${g}_{1}^{2}$ − 1 ≤|Te,dp,dq,N|≤ ${g}_{e}^{2}$ − 1.

Proof

We have gp = gcd(edp − 1, q − 1). Then there exists a subgroup Sq of order gp in ${ℤ}_{q}^{*}$  such that for any $w\in {S}_{q}$ , we have q|wgp − 1. Now consider any ${w}_{1}\in {ℤ}_{p}^{*}$ and w2 from Sq. By CRT, there exists a unique $W\in {ℤ}_{N}^{*}$ such that Ww1 mod p and
Ww2 mod q, and vice versa. Thus the number of such W’s is gp(p − 1). It is evident that for all these W’s, we have
gcd(W, N) = 1 and N|W edp−1 − 1. We can also observe that any $W\in {T}_{e,{d}_{p},N}$ can be obtained in this way. Discarding the case
W = 1, we get | Te,dp,N | = gp(p − 1) – 1.
Similarly, we have gq = gcd(edq − 1, p − 1). Then there exists a subgroup Sp of order gq in ${ℤ}_{p}^{*}$  such that for any $w\in {S}_{p}$ , we have p|wgq − 1. In the same manner, we get
|Te,dq,N | = gq(q − 1) – 1.
Now consider any ${w}_{1}\in {S}_{p}$ and ${w}_{2}\in {S}_{q}$ . By CRT, there exists a unique $W\in {ℤ}_{N}^{*}$ such that Ww1 mod p and Ww2 mod q, and vice versa. Thus the number of such W’s is gpgq. It is evident that for all these W’s, we have gcd(W, N) = 1,
N|W edp−1 − 1 and N|W edq−1 − 1. One may observe that any
W ÎTe,dp,dq,N  can be obtained in this manner. Discarding the case W = 1, we get |Te,dp,dq,N | = gpgq − 1.
Consider edp − 1= k(p − 1) and edq − 1= l(q − 1). Then we get |Te,dp,dq,N |≥ ${g}_{1}^{2}$  − 1, as g1 divides both gp and gq. Since ge = gcd(edp − 1, edq − 1) = gcd(k(p − 1), l(q − 1)), each of gp, gq divides ge. Thus the bounds on |Te,dp,dq,N | follow.
Given e, N, dp, dq, one can get ge easily, and thus the upper bound of |Te,dp,dq,N | is immediately known. If ge is bounded by poly(log N), then it is enough to try ${g}_{e}^{2}$ many distinct W’s to factorise N in poly(log N) time. However, from proposition 1, it is clear that |Te,dp,dq,N | may not be bounded by poly(log N) as gp,gq may not be bounded by poly(log N) in all the cases. Thus we have the following question, where an affirmative answer will transform the probabilistic algorithm to a deterministic one. Is it possible to identify a W $\in$ [2,N − 1] \ Te,dp,dq,N  in poly(log N) time?
To our knowledge, an affirmative answer to the above question is not known. Thus, from theoretical point of view, getting a deterministic polynomial time algorithm for factorising N with the knowledge of N, e, dp,dq is important. We solve it using lattice-based technique.

1.2 Preliminaries on Lattices

Let us present some basics on lattice reduction techniques. Consider the linearly independent vectors u1,..., , $\in {ℤ}^{n}$ where ω ≤ n. A lattice, spanned by {u1,...,}, is the set of all linear combinations of u1,...,, i.e., ω is the dimension of the lattice. A lattice is called full rank when ω = n. Let L be a lattice spanned by the linearly independent vectors u1,...,, where u1,..., $\in {ℤ}^{n}$ . By ${u}_{1}^{*}$ ,......,${u}_{w}^{*}$ , we denote the vectors obtained by applying the Gram-Schmidt process to the vectors u1,...,uω.
The determinant of L is deﬁned as $\mathrm{det}\left(L\right)={\prod }_{i=1}^{w}\parallel {u}_{i}^{*}\parallel$ , where ||.|| denotes the Euclidean norm on vectors. Given a polynomial $g\left(x,y\right)=\sum {a}_{i,j}{x}^{i}{y}^{j}$ , we deﬁne the Euclidean norm as $\parallel g\left(x,y\right)\parallel =\sqrt{{\sum }_{i,j}{a}_{i,j}^{2}}$    and infinity norm as $\parallel g\left(x,y\right)\parallel \infty ={\mathrm{max}}_{i,j}|{a}_{i,j}|$ .
It is known that given a basis u1,...,uω of a lattice L, the LLL algorithm13 can ﬁnd a new basis b1,...,bω of L with the following properties.

$‖{b}_{i}^{*}‖{}^{2}\le 2{‖{b}_{i+1}^{*}‖}^{2}$, for 1 ≤ i < ω.
– For all i, if ${b}_{i}={b}_{i}^{*}+{\sum }_{j=1}^{i-1}{\mu }_{i,j}{b}_{j}^{*}$ then $|{\mu }_{i,j}|\le \frac{1}{2}$ for all j.
–  $‖{b}_{i}‖\le {2}^{\frac{w\left(w-1\right)+\left(i-1\right)\left(i-2\right)}{4\left(w-i+1\right)}}\mathrm{det}{\left(L\right)}^{\frac{1}{w-i+1}}$   for i =1,...,ω.

Deterministic polynomial time algorithms has been presented by Coppersmith4 to ﬁnd small integer roots of (i) polynomials in a single variable mod N, and of (ii) polynomials in two variables over the integers. The idea of Coppersmith4 extends to more than two variables also, but in that event, the method becomes heuristic.
A simpler algorithm by Coron5, than Coppersmith4 has been presented in this direction, but it was asymptotically less efficient. Later, a simpler idea by Coron6 than Coppersmith4 has been presented with the same asymptotic bound as in Coppersmith4. Both the works of Coron5,6 depends on the result of Howgrave-Graham8.
The results of May14, in finding the deterministic polynomial time algorithm to factorise N from the knowledge of e, d, uses the techniques presented by Coppersmith4 & Coron5. Further, the work of Coron and May7 exploits the technique presented in Howgrave-Graham9.

2.     DETERMINISTIC POLYNOMIAL TIME ALGORITHM

In this section we consider that both dp, dq are known apart from the public information N, e. We start with the following lemma. In the following results, we consider $p\approx {N}^{{\gamma }_{1}}$  as the bit size of p can be correctly estimated in log N many attempts.

Lemma 1
Let ,${d}_{p}\le {N}^{{\delta }_{1}}$ ,${d}_{q}\le {N}^{{\delta }_{2}}$ . Suppose p > q and $p\approx {N}^{{\gamma }_{1}}$ .  If both dp, dq. are known then one can factor N in deterministic poly(log N) time if 2α + δ1 + δ2 ≤ 2 − γ1.

Proof
We have edp − 1= k(p − 1), edq − 1= l(q − 1) for some positive integers k, l.
So,$kl=\frac{\left(e{d}_{p}-1\right)\left(e{d}_{q}-1\right)}{\left(p-1\right)\left(q-1\right)}$
Let $A=\frac{\left(e{d}_{p}-1\right)\left(e{d}_{q}-1\right)}{N}$. Now $|kl-A|=\left(e{d}_{p}-1\right)\left(e{d}_{q}-1\right)\frac{N-\left(p-1\right)\left(q-1\right)}{N\left(p-1\right)\left(q-1\right)}\approx \frac{e{d}_{p}e{d}_{p}\left(p+q\right)}{{N}^{2}}\le {N}^{2\alpha +{\delta }_{1}+{\delta }_{2}+{\gamma }_{1}-2}$ (neglecting the small constant).

So, as long as, 2α + δ1 + δ2 ≤ 2 − γ1, we have $kl=⌈A⌉$ . After ﬁnding kl, one gets (p − 1)(q − 1) and hence p + q can be obtained immediately, which factorises N. In the next result, we use the idea of Coppersmith4.

Theorem 1
Let ,${d}_{p}\le {N}^{{\delta }_{1}}$ ,${d}_{q}\le {N}^{{\delta }_{2}}$   . Suppose p is estimated as ${N}^{{\gamma }_{1}}$ . Further consider that an approximation p0 of p is known such that $|p-{p}_{0}|<{N}^{\beta }$ .
Let ${k}_{0}=⌊\frac{e{d}_{p}}{{p}_{0}}⌋,{q}_{0}=⌊\frac{N}{{p}_{0}}⌋,{l}_{0}=⌊\frac{e{d}_{p}}{{q}_{0}}⌋$ and

g = gcd(N –1,edq–1 + l0–l0N, edp–1 + k0k0 N) = Nη
If both dp , dq are known then one can factor N in deterministic poly(log N) time if
α2 + αδ1 +2αβ +δ1β −2αγ1${\gamma }_{1}^{2}$ +αδ21δ2
+βδ2 −2γ1δ2 −2βη +2γη –η2 −α−δ1 +β +2η −1 < 0
provided 1+3γ1 − 2β − δ1 − α − η ≥ 0.

Proof
We have edp = 1+ k(p − 1) and edq = 1+ l(q − 1). So $k=\frac{e{d}_{p}-1}{p-1}$ . We also have${k}_{0}=\frac{e{d}_{p}}{{p}_{0}}$
then,
$|k-{k}_{0}|=|\frac{e{d}_{p}-1}{p-1}-\frac{e{d}_{p}}{{p}_{0}}|\approx |\frac{e{d}_{p}}{p}-\frac{e{d}_{p}}{{p}_{0}}|=\frac{e{d}_{p}|p-{p}_{0}|}{p{p}_{0}}\le {N}^{\alpha +{\delta }_{1}+\beta -2{\gamma }_{1}}$ Considering ${q}_{0}=\frac{N}{{p}_{0}}$ , it can be shown that,|qq0| <N1+β-2γ1, neglecting the small constant. Assume, $q={N}^{{\gamma }_{\text{2}}}$ , where γ2 =1–γ1 . So if we take ${l}_{0}=\frac{e{d}_{p}}{{p}_{0}}$ .
then  $|k-{k}_{0}|=|\frac{e{d}_{p}-1}{p-1}-\frac{e{d}_{p}}{{p}_{0}}|\approx |\frac{e{d}_{p}}{p}-\frac{e{d}_{p}}{{p}_{0}}|=\frac{e{d}_{p}|p-{p}_{0}|}{p{p}_{0}}\le {N}^{\alpha +{\delta }_{1}+\beta -2{\gamma }_{1}}$

Considering ${q}_{0}=\frac{N}{{p}_{0}}$,it can be shown that $|q-{q}_{0}|<{N}^{1+\beta -2{\gamma }_{1}}$, neglecting the small constant. Assume, $q={N}^{{\gamma }_{\text{2}}}$ , where  γ2 =1- γ1 . So if we take ${l}_{0}=\frac{e{d}_{p}}{{p}_{0}}$ then$\begin{array}{l}|l-{l}_{0}|=|\frac{e{d}_{q}-1}{q-1}-\frac{e{d}_{q}}{{q}_{0}}|\approx |\frac{e{d}_{q}}{q}-\frac{e{d}_{q}}{{q}_{0}}|\\ =\frac{e{d}_{q}|q-{q}_{0}|}{q{q}_{0}}\le {N}^{\alpha +{\delta }_{2}+1+\beta -2{\gamma }_{1}-2{\gamma }_{2}}={N}^{\alpha +{\delta }_{2}+\beta -1}\end{array}$

Let k1 = k k0 and l1 = ll0. We have edp + k1= kp. So edp + k0 + k1 − 1= (k0 + k1)p. Similarly, edq+l0+l1−1=(l0 + l1)q. Now multiplying these equations, we get
(edp − 1+ k0)(edq − 1+ l0)+ k1(edq − 1+ l0)
+ l1(edp − 1+ k0)+ k1l1 =(k0 + k1)p(l0 + l1)q

Now if we substitute k1, l1 by x, y respectively, then
(edp − 1+ k0)( edp − 1+ l0)+ x(edq − 1+ l0)
+ y(edp − 1+ k0)+ xy =( k0 + x)p(l0 + y)q

Hence we have to ﬁnd the solution k1, l1 of
(edp − 1+ k0)( edq − 1+ l0)+ x(edq− 1+ l0)
+ y(edp − 1+ k0)+ xy =( k0 + x)p(l0 + y)q
i.e., we have to ﬁnd the roots of ${f}^{\prime }$ (x, y) = 0, where
${f}^{\prime }$ (x, y) = (1 − N)xy + x(edq − 1+ l0 − l0N)
+ y(edp−1+k0k0N)+( edp− 1+ k0)( edq− 1+ l0) − k0 l0 N.
We have
g = gcd(1 − N, edq − 1+ l0l0 N, edp − 1+ k0k0N)= Nη .
Let $f\left(x,y\right)=\frac{{f}^{\prime }\left(x,y\right)}{g}$ , X = ${N}^{\alpha +{\delta }_{1}+\beta -2{\gamma }_{1}}$ and Y = ${N}^{\alpha +{\delta }_{2}+\beta -1}$ . Clearly X, Y are the upper bounds of (k1,l1), the root of f
Thus,

Then from Coppersmith4 we need $XY<{W}^{\frac{2}{3}}$ , which implies 2α + δ1 + δ2 +2η< 3 + 4(γ1 − β)                                        (1)

If one of the variables x, y is significantly smaller than the other, we give some extra shifts on x or y. Without loss of generality, let us assume that k1 is significantly smaller than l1. Following the ‘extended strategy’ of Jochemsz and May11,we know that these polynomials can be found by lattice reduction if for ${s}_{j}=\sum {}_{{x}^{{i}_{\text{\hspace{0.17em}}1}}{y}^{{i}_{\text{\hspace{0.17em}}2}}\in M/{S}^{{i}_{j}}}$
where$s=|S|$ , j=1, 2. One can check that

${s}_{1}=\frac{3}{2}{m}^{2}+\frac{7}{2}m+\frac{{t}^{2}}{2}+\frac{5}{2}t+2mt+2$

,${s}_{2}=\frac{3}{2}{m}^{2}+\frac{7}{2}m+t+mt+2$
,
and s =(m + 1)2 + mt + ts = (m + 1)2 + mt + t

Let t = τm. Neglecting the lower order terms we get that  is satisﬁed when
i.e., when

In this case the value of τ for which the left hand side of the above inequality is minimum is $\tau =\frac{1+3{\gamma }_{1}-2\beta -{\delta }_{1}-\alpha -\eta }{\alpha +{\delta }_{1}+\beta -2{\gamma }_{1}}$ . As $\tau \ge 0$ , we need $1+3{\gamma }_{1}-2\beta -{\delta }_{1}-\alpha -\eta \ge 0$ . Putting this optimal value of τ we get the required condition as ${\alpha }^{2}+\alpha {\delta }_{1}+2\alpha \beta +{\delta }_{1}\beta -2\alpha {\gamma }_{1}-\gamma \frac{2}{1}+\alpha {\delta }_{2}+{\delta }_{1}{\delta }_{2}+\beta {\delta }_{2}-2{\gamma }_{1}{\delta }_{2}-2\beta \eta -{\eta }^{2}-\alpha -{\delta }_{1}+\beta +2\eta -1<0.$

The strategy presented by Jochemsz and May11 works in polynomial time in log N. As we follow the same strategy, N can be factored from the knowledge of N, e, dp, dq in deterministic polynomial time in log N.
As the condition given in Theorem 1 is quite involved, we present a few numerical values in Table 2.

Table 2. Numerical values of α, δ1, δ2, β, γ1, η following Theorem 1 for which N can be factored in poly(log N) time.

Corollary 1
Let ,${d}_{p}<{N}^{{\delta }_{1}}$ ,${d}_{q}<{N}^{{\delta }_{2}}$   .
Let g = gcd(N − 1, edp − 1, edq − 1) = Nη .
If N, e, dp, dq are known then N can be factored in deterministic polynomial time in log N when
2α + δ1 + δ2 +2η< 3.

Proof
Since in this case we do not consider any approximation of p, q, we take β = γ. Putting this value of β in Inequality 1, we get the desired result.
For practical purposes, p, q are same bit size and if we consider that no information about the bits of p is known, then we have . In this case, we require as well as .
As discussed in Section 1.1, if |Te,dp,dq,N | is small, then one can easily prove the deterministic polynomial time equivalence. However, this idea cannot be applied when |Te,dp,dq,N | is large. In such an event, our lattice based technique provides a solution for certain ranges of dp, dq. In all our experiments we start with large g1, e.g., of the order of 100 bits. In such cases, |Te,dp,dq,N | is large as $g\frac{2}{1}-1$   ≤|Te,dp,dq,N | following Proposition 1. One may note that the g1 in Proposition 1 divides the g in Theorem 1.
Let us now present some experimental results in Table 3. Our experiments are based on the strategy of Coron5 as it is easier to implement. We have written the programs in SAGE 3.1.1 over Linux Ubuntu 8.04 on a computer with Dual CORE Intel(R) Pentium(R) D 1.83 GHz CPU, 2 GB RAM and 2 MB Cache. We take large primes p, q such that N is of 1000 bits. We like to point out that the experimental results cannot reach the theoretical bounds due to the small lattice dimensions.

Table 3. Experimental results corresponding to Theorem 1.

Towards theoretical interest, we have presented a deterministic poly(log N) time algorithm that can factorise N given e, dp and dq for certain ranges of dp , dq. This algorithm is based on lattice reduction techniques.

The authors like to thank Dr A Venkateswarlu for pointing out Proposition 1 and Mr Sourav Sen Gupta for presenting detailed comments on this version.

1. Boneh, D. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS, 1999, 46(2), 203-13.

2. Boneh, D. & Durfee, G. Cryptanalysis of RSA with private key d less than N0.292. IEEE Trans. Infor­m. Theory, 2000, 46(4),1339-349,

3. Boneh, D.; DeMillo, R.A. & Lipton, R.J. On the importance of eliminating errors in cryptographic compu­tations. Journal of Cryptology, 2001, 14(2), 101-19.

4. Coppersmith, D. Small solutions to polynomial equations and low exponent vulnerabilities. Journal of Cryp­tology, 1997, 10(4), 223-60.

5. Coron, J.S. Finding small roots of bivariate integer equations revisited. Eurocrypt 2004, Lecture Notes in Computer Science, LNCS 3027, 2004, pp. 492-505.

6. Coron, J. S. Finding small roots of bivariate integer equations: A direct approach. Crypto 2007, Lecture Notes in Computer Science,Lecture Notes in Computer Science, LNCS 4622, 2007, pp. 379-94.

7. Coron, J. S. & May, A. Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. Journal of Cryptology, 2007, 20(1), 39-50.

8. Howgrave-Graham, N. Finding small roots of univariate modular equations revisited. In Proceedings of Cryp­tography and Coding,Lecture Notes in Computer Science, LNCS1355, 1997, pp.131-42.

9. Howgrave-Graham, N. Approximate integer common divisors. In Proceedings of CaLC’01, Lecture Notes in Computer Science, LNCS 2146, 2001, pp. 51-66.

10. Jochemsz, E. Cryptanalysis of RSA variants using small roots of polynomials. Technische Universiteit Eindhoven, 2007. PhD Thesis.

11. Jochemsz, E. & May, A. A Strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. Asiacrypt 2006, Lecture Notes in Computer Science, LNCS 4284, 2006, pp. 267-82.

12. Jochemsz, E. & May, A. A polynomial time attack on RSA with private CRT-exponents smaller than N0.073. Crypto 2007, Lecture Notes in Computer Science, LNCS 4622, 2007, pp. 395-411.

13. Lenstra, K.; Lenstra, H.W. & Lov´asz, L. Factoring polynomials with rational coeﬃcients. Mathematische Annalen, 1982, 261, 513-34.

14. May, A. Computing the RSA secret key is deterministic polynomial time equivalent to factoring. Crypto 2004, Lecture Notes in Computer Science, LNCS 3152, 2004, pp. 213-19.

15. May, A. Using LLL-reduction for solving RSA and factorisation problems: A survey. LLL+25 Confer­ence in honour of the 25th birthday of the LLL algorithm, 2007. http://www.informatik.tu­darmstadt.de/KP/alex.html [Accessed on 23 December, 2008].

16. Miller, G.L. Riemann’s hypothesis and test of primality. In the 7th Annual ACM Symposium on the Theory of Computing, 1975, pp. 234–239.

17. Rivest, R.L.; Shamir, A. & Adleman, L. A method for obtaining digital signatures and public key cryp­tosystems. Communications of ACM, 1978, 21(2), 158-64.

18. Stinson, D.R. Cryptography -Theory and practice. Ed 2nd, Chapman & Hall/CRC, 2002.

19. Wiener, M. Cryptanalysis of short RSA secret exponents. IEEE Trans. Inform. Theo., 1990, 36(3), 553-58.