Skip to Main content Skip to Navigation
Journal articles

A generalized attack on RSA type cryptosystems

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 (p^2 − 1)(q^2 − 1) = 1. In this paper, we consider the general equation ex − (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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02320917
Contributor : Abderrahmane Nitaj <>
Submitted on : Saturday, October 19, 2019 - 8:27:47 PM
Last modification on : Monday, April 27, 2020 - 4:14:03 PM
Long-term archiving on: : Monday, January 20, 2020 - 1:17:23 PM

File

Generalized_attack_on_RSA_sche...
Files produced by the author(s)

Identifiers

Collections

Citation

Martin Bunder, Abderrahmane Nitaj, Willy Susilo, Joseph Tonien. A generalized attack on RSA type cryptosystems. Theoretical Computer Science, Elsevier, 2017, ⟨10.1016/j.tcs.2017.09.009⟩. ⟨hal-02320917⟩

Share

Metrics

Record views

36

Files downloads

119