Cryptanalysis Of RSA-type Scheme Moduli (?)q

The dangers of using RSA with small private exponents has been known for almost twenty years. In 1990, Wiener [22] showed that every RSA public key (N, e)with e∈Z_φ(N)^* that satisfies ed-1 =0 modφ(N) for some d<(?) yields the factorization of N = pq.In 1996, Coppersmith [4] introduced a method for finding small roots of modular polynomial equations using the LLL-algorithm. Since then, the method has found many different applications in the area of public key cryptography.In 1999, Boneh and Durfee [2] proposed an attack on RSA with samll secret exponent which is based on Coppersmith's lattice-based technique for finding small roots of bivariate modular polynomial equation[4]. The attack works if d0.292. Similar attack was proposed by Bl(?)mer and May if d0.29.In 2004 Johannes Blomer and Alexander May [1] proposed a generalized Wiener attack , and extended the result, they showed p and q could be found in polynomial time for every (N, e) satisfying ex + y = 0 modφ(N) withIn recent years modulus of the form N = p^rq have found many application in cryptograpgy. For example, Fujioke et al. [5] use a modulus N = p²q in an elextronic cash scheme. Okamoto and Uchiyama [17] use N = p^rq for an elegant public key system. And Takagai [20] observed that RSA decryption can be performed significantly faster by using a modulus of the form N = p^rq. In all these applications, the factors p and q are approximately the same size. The security of the system relies on the difficulty of factoring N.It is a very natural question to study what will happen when we consider the generalized Wiener attack like [1] to this type RSA whose modulus is N-p^rq rather than N = pq. In this paper, we give an attack on RSA-type scheme with public key (N. e), where N=p^rq for some fixed r > 1. Our method finds p and q in polynomial time for every (N, e) satisfying ex + y = 0 modφ(N) withThe method works as follows: As in Wiener's attack, we use the continued frac-tion algorithm to recover the unknown values x and k. Afterwards, we show that a factorization method due to [3] can be applied.Afterwards, we show that not only 0 < x≤(?) is dangerous but alsoφ(N)-(?)≤x≤φ(N) can not be used in cryptographic design.Besides the bound of dangerous x, we also should discuss the number of weak keys on these x. We define the size of a class of public key tuples by the number of elements(N, e) in the class for every fixed N. Let C be a class of public key tuples (N,e), thenC is called weak if1. The size of C is plynomial in N, i.e.size_c(N) =Ω(N^γ) for someγ> 02. There exists a probabilistic algorithm A that on every input (N, e)∈C outputs the factorization of N in time polynomial time.We show that the number of weak keys is at least (?) and that the number increases with decreasing prime difference p-q. Let |p-q|θ. We show that N can be factored in polynomial time if 0<θ≤(?). And if (?)<θ<(?) we give a probabilistic algorithm with expected polynomial running time .