Paper 2021/1632 Original: eprint.iacr.org/2021/1632 ↗
Cryptanalysis of RSA Variants with Primes Sharing Most Significant Bits
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
- Preprint.
- History
- 2021-12-17: last updated
- 2021-12-17: published
- Short URL
- https://ia.cr/2021/1632
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2021/1632}
}