Vulnerabilities of \(ex^2\) - \(y^2\)\(\phi\) (N)= z Using Modulus of the Form N= \(p^r\)\(q^s\)
Sadiq Shehu, Buhari Auwalu Ibrahim, Aminu A. Ibrahim, Ahmad Rufai
Journal of Advances in Mathematics and Computer Science · pp. 53–65 · Published 17 Jun 2023
10.9734/jamcs/2023/v38i81790Abstract
The technical details of RSA works on the idea that it is easy to generate the modulus by multiplying two sufficiently large prime numbers together, but factorizing that number back into the original prime numbers is extremely difficult. Suppose that \(N=p^r q^s\) are RSA modulus, where \(p\) and \(q\) are product of two large unknown of unbalance primes for \(2 \leq s<r\). The paper proves that using an approximation of \(\phi(N) \approx\) \(N-N^{\frac{r+8-1}{2 r}}\left(\lambda^{\frac{1-8}{2 r}}+\lambda^{\frac{-8}{2 r}}\right)+N^{\frac{r+8-2}{2 T}} \lambda^{\frac{1-8}{2 r}}\), private keys \(\frac{x^2}{y^2}\) can be found from the convergents of the continued fractions expansion of \[ \left|\frac{e}{N-N^{\frac{r+8-1}{2 r}}\left(\lambda^{\frac{1-8}{2 r}}+\lambda^{\frac{-8}{2 r}}\right)+N^{\frac{r+8-2}{2 r}} \lambda^{\frac{1-8}{2 r}}}-\frac{y^2}{x^2}\right|<\frac{1}{2 x^4} \] which leads to the factorization of the moduli \(N=p^r q^s\) into unbalance prime factors p and q in polynomial time. The second part of this reseach report further, how to generalized two system of equations of the form \(e_ux^2\) - \(y^2_u\phi(N_u)\) = \(z_u\) and \(e_ux^2_u\) - \(y^2\phi(N_u)\) = \(z_u\) using simultaneous Diophantine approximation method and LLL algorithm to and the values of the unknown integers \(x,y_u\),\(\phi(N_u)\) and \(x_u\),y,\(\phi(N_u)\) respectively, which yeild to successful factorization of k moduli \(N_u=p^r_uq^s_u\) for u = 1,2, ... k in polynomial time.
References (17)
- 1 New directions in cryptography [DOI]
- 2 A method for obtaining digital signatures and public-key cryptosystems [DOI]
- 3 Factoring polynomials with rational coefficients [DOI]
- 4 Cryptanalysis of short RSA secret exponents [DOI]
- 5 Fast RSA-type cryptosystem modulo p k q [DOI]
- 6 Cryptanalysis of RSA with Small Prime Difference [DOI]
- 7 Artificial Intelligence, Evolutionary Computing and Metaheuristics [DOI]
- 8 Revisiting Wiener’s Attack – New Weak Keys in RSA [DOI]
- 9 A Generalized Takagi-Cryptosystem with a Modulus of the Form prqs [DOI]
- 10 Revisiting Prime Power RSA [DOI]
- 11 Diophantine and Lattice Cryptanalysis of the RSA Cryptosystem [DOI]
- 12 Factoring $$N=p^rq^s$$ for Large r and s [DOI]
- 13 New Attacks on RSA with ModulusN=p2qUsing Continued Fractions [DOI]
- 14 Improved Factorization of $$N=p^rq^s$$ [DOI]
- 15 IEEE Transactions on Information Theory [DOI]
- 16 New RSA Vulnerabilities Using Lattice Reduction Methods
- 17 Applicable Algebra in Engineering, Communication and Computing [DOI]
Cited by 0
No indexed citations yet.
Related research
- Generalized Hadamard Matrices and 2-Factorization of Complete Graphs — shares topic coverage
- Strategic Way of Factoring Modulus \(N = p^r q\) — shares topic coverage
- Breaking Modulus of the form \(N = p^rq^s\) with Improved Polynomial Attacks — shares topic coverage
- The Continued Fractions Ladder of Specific Pairs of Irrationals — shares topic coverage
- Half-Inverse Problem for Stieltjes String — shares topic coverage
Article metrics
Real usage data collected on this platform.
37
Page views
0
PDF downloads
4
Outbound clicks
0
Citations
Views over time
Views by country
Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".
Traffic sources
Referring site, by host.
Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.