**A generalized attack on RSA type cryptosystems**

*Martin Bunder and Abderrahmane Nitaj and Willy Susilo and Joseph Tonien*

**Abstract: **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\"{o}mer-May on RSA.

**Category / Keywords: **public-key cryptography / RSA, Cryptanalysis, Coppersmith's method, Continued fractions, Factorization

**Date: **received 6 Nov 2017

**Contact author: **abderrahmane nitaj at unicaen fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20171110:153109 (All versions of this report)

**Short URL: **ia.cr/2017/1076

[ Cryptology ePrint archive ]