Paper 2017/1076
A generalized attack on RSA type cryptosystems
Martin Bunder, Abderrahmane Nitaj, 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ömer-May on RSA.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- RSACryptanalysisCoppersmith's methodContinued fractionsFactorization
- 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},
note = {\url{https://eprint.iacr.org/2017/1076}},
url = {https://eprint.iacr.org/2017/1076}
}
