A generalized attack on RSA type cryptosystems

Citation data:

Theoretical Computer Science, ISSN: 0304-3975, Vol: 704, Page: 74-81

Publication Year:
Usage 16
Abstract Views 16
Captures 22
Readers 22
Citations 1
Citation Indexes 1
Repository URL:
Bunder, Martin W; Nitaji, Abderrahmane; Susilo, Willy; Tonien, Joseph
Elsevier BV
Mathematics; Computer Science; attack; generalized; rsa; cryptosystems; type; Engineering; Science and Technology Studies
article description
Let N=pq be an RSA modulus with unknown factorization. Some variants of the RSA cryptosystem, such as LUC, RSA with Gaussian primes and RSA type schemes based on singular elliptic curves use a public key e and a private key d satisfying an equation of the form ed−k(p2−1)(q2−1)=1. In this paper, we consider the general equation ex−(p2−1)(q2−1)y=z and present a new attack that finds the prime factors p and q in the case that x, y and z satisfy a specific condition. The attack combines the continued fraction algorithm and Coppersmith's technique and can be seen as a generalization of the attacks of Wiener and Blömer–May on RSA.