Search

The RSA (Rivest–Shamir–Adleman) asymmetric-key cryptosystem is widely used for encryptions and digital signatures. Let (n , e) be the RSA public key and d be the corresponding private key (or private exponent). One of the attacks on RSA is to find the private key d using continued fractions when d is small. In this paper, we present a new technique to improve a small private exponent attack on RSA using continued fractions and multicore systems. The idea of the proposed technique is to find an interval that contains ϕ (n) , and then propose a method to generate different points in the interval that can be used by continued fraction and multicore systems to recover the private key, where ϕ is Euler's totient function. The practical results of three small private exponent attacks on RSA show that we extended the previous bound of the private key that is discovered by continued fractions. When n is 1024 bits, we used 20 cores to extend the bound of d by 0.016 for de Weger, Maitra-Sarkar, and Nassr et al. attacks in average times 7.67 h, 2.7 h, and 44 min, respectively. [ABSTRACT FROM AUTHOR]

Let (n = p q , e = n β) be an RSA public key with private exponent d = n δ , where p and q are large primes of the same bit size. At Eurocrypt 96, Coppersmith presented a polynomial-time algorithm for finding small roots of univariate modular equations based on lattice reduction and then succussed to factorize the RSA modulus. Since then, a series of attacks on the key equation e d − k ϕ (n) = 1 of RSA have been presented. In this paper, we show that many of such attacks can be unified in a single attack using a new notion called Coppersmith's interval. We determine a Coppersmith's interval for a given RSA public key (n , e). The interval is valid for any variant of RSA, such as Multi-Prime RSA, that uses the key equation. Then we show that RSA is insecure if δ < β + 1 3 α − 1 3 1 2 α β + 4 α 2 provided that we have approximation p 0 ≥ n of p with p − p 0 ≤ 1 2 n α , α ≤ 1 2. The attack is an extension of Coppersmith's result. [ABSTRACT FROM AUTHOR]

The Murru-Saettone cryptosystem is an RSA-like cryptosystem constructed from a particular group with a non-standard product in a cubic field related to the general cubic form of the Pell equation. In this cryptosystem, the public key is (n , e , r) , where n is a product of two large primes p , and q of the same bit size, e is a positive integer such that gcd ⁡ (e , ψ (n)) = 1 , ψ (n) = (p 2 + p + 1) (q 2 + q + 1) , and r is a non-cube integer in Z p , Z q and Z n. The private exponent d is the multiplicative inverse of e modulo ψ (n). In this paper, we use continued fractions to make three attacks on RSA work on the Murru-Saettone cryptosystem. The first attack, due to de Weger, works when d ≤ n 3 / 4 p − q. The second attack, due to Maitra-Sarkar (ISC 2008), works when d ≤ n 3 / 4 2 q − p. The third attack, due to Nassr et al. (AICCSA 2008), works when d < n (1 − α) / 2 assuming that we know an approximation p 0 of p , such that | p − p 0 | ≤ n α , α ≤ 1 / 2. [ABSTRACT FROM AUTHOR]