[Resource Topic] 2017/1076: A generalized attack on RSA type cryptosystems

Welcome to the resource topic for 2017/1076

A generalized attack on RSA type cryptosystems

Authors: Martin Bunder, Abderrahmane Nitaj, Willy Susilo, Joseph Tonien


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\left(p^2-1\right)\left(q^2-1\right)=1. In this paper, we consider the general equation ex-\left(p^2-1\right)\left(q^2-1\right)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.

ePrint: https://eprint.iacr.org/2017/1076

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .