Cryptanalysis of Public-Key Cryptosystems

Abstract

The thesis aimed to study the cryptanalysis of both RSA and NTRU public-key cryptosystems. The results obtained in the thesis are as follows: - We study factoring n when n = pq is a product of two primes p and q satisfying that p lk1 (mod 2 1) and q lk2 (mod 2 2) for some positive integers 1; 2; k1; k2 log n and l: We show that n can be factored in time polynomial in log n if l < 2 with j p􀀀lk1 2 1 jj q􀀀lk2 2 2 j < lk or 2 0 n1=4, where = minf 1; 2g; 0 = maxf 1; 2g and k = minfk1; k2g: - Let (n = pq; e = n ) be an RSA public-key with private exponent d = n ; where p and q are large primes of the same bit size. Let the key equation be ed 􀀀 k (n) = 1: We give the notion Coppersmith interval. For every integer m in a Coppersmith interval, the solution (k;m􀀀 (n)) of the modular polynomial equation fm(x; y) = xy + mx+1 0 (mod e) can be found by using Coppersmith's method. Then we determine a Coppersmith interval for a given RSA publickey (n; e): The obtained Coppersmith interval is also valid for any variant of RSA that uses the key equation ed􀀀k (n) = 1: We show that: 1. the attack of [10] and its improvements by [19] and by [43] as well as the attack presented by [74] can be obtained from the proposed Coppersmith interval. 2. RSA is insecure if < + 1 3 􀀀 1 3 p 12 + 4 2 provided that we have approximation p0 p n of p with jp 􀀀 p0j xi 1 2n ; 1 2 : The attack can be considered as an extension of Coppersmith's result on a factorization. 3. de Weger's attack on RSA can be extended to Multi-Prime RSA. - Let (n = pq; e = n ) be an RSA public-key with private exponent d = n ; q < p < 2q; and jp 􀀀 qj = n : We show that if p; q share m bits of their least signi cant bits and LSB( (n)) < 22m; then we can factor n in polynomial time. Also, if we have an approximation z0 for LSB( (n)) such that jLSB( (n))􀀀z0j = n with 􀀀1=4 or < + 1 3 􀀀 1 3 p 12 + 4 2; then we can factor n in polynomial time. - Let (n = pq; e1; e2 n ) be an RSA public-key with two public exponents e1 and e2 and the corresponding decryption exponents d1 and d2: Suppose that jp 􀀀 qj = 2mu with 2m = n , and jd1 􀀀 d2j < n . We show that one can factor n if d1; d2 < n under the condition < 5 2 􀀀 2 􀀀 􀀀 1 4 p 6(1 􀀀 4 )(5 + 4 􀀀 4 􀀀 4 ): - we study the cryptanalysis of NTRU, when the coe cients of the private polynomial g contains one or more zero patterns at di erent positions and show that the lattice attack of May [44] on NTRU is a special case of our result. Keywords: RSA, Multi-prime RSA, NTRU, public-key, cryptanalysis, lattice, Coppersmith interval, (n); factoring. xii