**Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits**

*Meryem Cherkaoui-Semmouni and Abderrahmane Nitaj and 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.

**Category / Keywords: **public-key cryptography / RSA variants, Continued fractions, Coppersmith's method, Lattice reduction

**Original Publication**** (in the same form): **Information Security Conference ISC 2021
**DOI: **10.1007/978-3-030-91356-4_3

**Date: **received 14 Dec 2021

**Contact author: **abderrahmane nitaj at unicaen fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20211217:142215 (All versions of this report)

**Short URL: **ia.cr/2021/1632

[ Cryptology ePrint archive ]