Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits

Meryem Cherkaoui-Semmouni; Abderrahmane Nitaj; Willy Susilo; Joseph Tonien

Paper 2021/1632

Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits

Meryem Cherkaoui-Semmouni, Abderrahmane Nitaj, Willy Susilo, and Joseph Tonien

Abstract

We consider four variants of the RSA cryptosystem with an RSA modulus $N = p q$ where the public exponent $e$ and the private exponent $d$ satisfy an equation of the form $e d - k (p^{2} - 1) (q^{2} - 1) = 1$ . We show that, if the prime numbers $p$ and $q$ share most significant bits, that is, if the prime difference $| p - q |$ is sufficiently small, then one can solve the equation for larger values of $d$ , and factor the RSA modulus, which makes the systems insecure.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Information Security Conference ISC 2021
DOI: 10.1007/978-3-030-91356-4_3
Keywords: RSA variants Continued fractions Coppersmith's method Lattice reduction
Contact author(s): abderrahmane nitaj @ unicaen fr
History: 2021-12-17: received
Short URL: https://ia.cr/2021/1632
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1632,
      author = {Meryem Cherkaoui-Semmouni and Abderrahmane Nitaj and Willy Susilo and Joseph Tonien},
      title = {Cryptanalysis of {RSA} Variants with Primes Sharing Most Significant Bits},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1632},
      year = {2021},
      doi = {10.1007/978-3-030-91356-4_3},
      url = {https://eprint.iacr.org/2021/1632}
}