A generalized attack on RSA type cryptosystems

Martin Bunder; Abderrahmane Nitaj; Willy Susilo; Joseph Tonien

Paper 2017/1076

A generalized attack on RSA type cryptosystems

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

Abstract

Let $N = p q$ 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 $e d - k (p^{2} - 1) (q^{2} - 1) = 1$ . In this paper, we consider the general equation $e x - (p^{2} - 1) (q^{2} - 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: RSA Cryptanalysis Coppersmith's method Continued fractions Factorization
Contact author(s): abderrahmane nitaj @ unicaen fr
History: 2017-11-10: received
Short URL: https://ia.cr/2017/1076
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1076,
      author = {Martin Bunder and Abderrahmane Nitaj and Willy Susilo and Joseph Tonien},
      title = {A generalized attack on {RSA} type cryptosystems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1076},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1076}
}