Back to Search
Start Over
Cryptoanalysis of RSA variants with special structure of RSA primes
- Publication Year :
- 2024
-
Abstract
- In this paper, we present attacks on three types of RSA modulus when the least significant bits of the prime factors of RSA modulus satisfy some conditions. Let $p,$ and $q$ be primes of the form $p=a^{m_1}+r_p$ and $q=b^{m_2}+r_q$ respectively, where $a,b,m_{1},m_{2} \in \mathbb{Z^+}$ $r_p,$ and $ r_q$ are known. The first attack is when the RSA modulus is $N=pq$ where $m_1$ or $m_2$ is an even number. If $\left(r_{p}r_{q}\right)^\frac{1}{2}$ is sufficiently small, then $N$ can be factored in polynomial time. The second attack is when $N=p^{s}q,$ where $q>p$ and $s$ divides $m_2.$ If $r_pr_q$ is sufficiently small, then $N$ can be factored in polynomial time. The third attack is when $N=p^{s+l}q^{s},$ where $p>q,$ $s,l \in \mathbb{Z^+},$ $l < \frac{s}{2}$ and $s$ divides $m_1l.$ If $a^{m_1}>qa^{\frac{m_1l}{s}},$ and $lr^3_p$ is sufficiently small, then $N$ can be factored in polynomial time.
- Subjects :
- Mathematics - Number Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2403.06184
- Document Type :
- Working Paper