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=pq$ where the public exponent $e$ and the private exponent $d$ satisfy an equation of the form $ed-k\left(p^2-1\right)\left(q^2-1\right)=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 variantsContinued fractionsCoppersmith's methodLattice reduction
Contact author(s)
abderrahmane nitaj @ unicaen fr
History
2021-12-17: received
Short URL
https://ia.cr/2021/1632
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2021/1632}},
      url = {https://eprint.iacr.org/2021/1632}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.