Skip to main content
placeholder image

Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits

Conference Paper


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(p2- 1 ) (q2- 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.

Publication Date

  • 2021

Citation

  • Cherkaoui-Semmouni, M., Nitaj, A., Susilo, W., & Tonien, J. (2021). Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 13118 LNCS (pp. 42-53). doi:10.1007/978-3-030-91356-4_3

Scopus Eid

  • 2-s2.0-85121867699

Start Page

  • 42

End Page

  • 53

Volume

  • 13118 LNCS

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(p2- 1 ) (q2- 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.

Publication Date

  • 2021

Citation

  • Cherkaoui-Semmouni, M., Nitaj, A., Susilo, W., & Tonien, J. (2021). Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 13118 LNCS (pp. 42-53). doi:10.1007/978-3-030-91356-4_3

Scopus Eid

  • 2-s2.0-85121867699

Start Page

  • 42

End Page

  • 53

Volume

  • 13118 LNCS