IJPAM: Volume 110, No. 4 (2016)

Title

NEW PRACTICAL ATTACK
ON RSA MODULUS OF TYPE $N=p^{2}q$

Authors

Normahirah Nek Abd Rahman$^1$, Muhammad Rezal Kamel Ariffin$^2$
$^{1,2}$Al-Kindi Cryptography Research Laboratory
Institute for Mathematical Research
Universiti Putra Malaysia
43400 UPM Serdang, Selangor, MALAYSIA
$^2$Department of Mathematics
Faculty of Science
Universiti Putra Malaysia
43400 UPM Serdang, Selangor, MALAYSIA

Abstract

This paper proposes three new attacks on RSA with the modulus $N=p^{2}q$. The first attack is based on the equation $eX-NY=(p^{2}u+q^{2}v)Z$ such that $u$ is an integer multiple of $2$ and $v$ is an integer multiple of $3$ with $\vert{p^{2}u-q^{2}v}\vert< N^{1/2}$ and gcd$(X,Y)=1$. If $X\vert Z\vert<\frac{N}{2\vert p^{2}u+q^{2}v\vert}$, then $N$ can be factored in polynomial time using continued fractions expansion. For the second and third attack, this paper proposes new vulnerabilities in $k$ RSA cryptosystem moduli $N_{i}=p_{i}^{2}q_{i}$ for $k \ge 2$ and $i=1,...,k$. The attacks work when $k$ RSA public keys $(N_{i},e_{i})$ are related through $e_{i}x-N_{i}y_{i}=(p_{i}^{2}u+q_{i}^{2}v)z_{i}$ or $e_{i}x_{i}-N_{i}y=(p_{i}^{2}u+q_{i}^{2}v)z_{i}$ where the parameters $x$, $x_{i}$, $y$, $y_{i}$ and $z_{i}$ are suitably small.

History

Received: June 23, 2016
Revised: August 15, 2016
Published: November 9, 2016

AMS Classification, Key Words

AMS Subject Classification: 11A51, 11A55, 11K60, 03G10
Key Words and Phrases: RSA, factorization, continued fraction, LLL algorithm, simultaneous diophantine approximations

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
M.A. Asbullah, Cryptanalysis on the Modulus $N=p^{2}q$ and Design of Rabin-Like Cryptosystem without Decryption Failure, PhD Thesis, Universiti Putra Malaysia, 2015.

2
M.A. Asbullah, M.R.K. Ariffin, New attack on RSA with modulus $N=p^{2}q$ using continued fractions, Journal of Physics, 622 (2015), 191-199.

3
J. Blömer, A. May, A generalized Wiener attack on RSA, Practice and Theory in Public Key Cryptography PKC 2004 LNCS Springer-Verlag, 2947 (2004), 1-13, doi: https://doi.org/10.1007/978-3-540-24632-9-1.

4
D. Boneh and G. Durfee, Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$,Advance in Cryptology-Eurocrypt'99, Lecture Notes in Computer Science, 1592 (1999), 1-11.

5
B. de Weger, Cryptanalysis of RSA with small prime difference, Applicable Algebra in Engineering Communication and Computing, 13 No. 1 (2002), pages 17, doi: https://doi.org/10.1007/s002000100088.

6
G. Hardy and E. Wright, An Introduction to the Theory of Numbers, Oxford University Press, London, 1965.

7
J. Hinek, On the Security of Some Variants of RSA, PhD Thesis, Waterloo, Ontario, Canada, 2007.

8
N. Howgrave-Graham, J. Seifert, Extending Wiener attack in the presence of many decrypting exponents, In: Secure Networking-CQRE (Secure)'99 Lecture Notes in Computer Science, 1740, Springer-Verlag (1999), 153-166.

9
A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring Polynomials with Rational Coefficients, Mathematische Annalen, 261(1982), 513-534, doi: https://doi.org/10.1007/BF01457454.

10
A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, PhD Thesis, University of Paderborn, 2003.

11
A. May, Secret exponent attacks on RSA-type scheme with moduli $N=p^{r}q$, In: PKC 2004 LNCS, 2947, Springer-Verlag (2004), 218-230.

12
A. Nitaj, Cryptanalysis of RSA using the ratio of the primes, Progress in Cryptology - AFRICACRYPT, Springer (2009), 98-115, doi: https://doi.org/10.1007/978-3-642-02384-2_7.

13
A. Nitaj, A new vulnerable class of exponents in RSA, JP Journal of Algebra, Number Theory and Applications, 21 No. 2 (2011a), 203-220.

14
A. Nitaj, New weak RSA keys, JP Journal of Algebra, Number Theory and Applications, 23 No. 2 (2011b), 131-148.

15
A. Nitaj, M. Ariffin, D.I. Nassr, H.M. Bahig, New attacks on the RSA cryptosystem, Lecture Notes in Computer Science, 8469, Springer Verlag (2014), 178-198, doi: https://doi.org/10.1007/978-3-319-06734-6_12.

16
T. Okamoto, S. Uchiyama, A new public-key cryptosystem as secure as factoring, In: Advances In Cryptology-EUROCRYPT'98, Springer (1998), 308-318, doi: https://doi.org/10.1007/BFb0054135.

17
R. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communication of the ACM, 21, No. 2 (1978), 17-28, doi: https://doi.org/10.1145/359340.359342.

18
S. Sarkar, Small secret exponent attack on RSA variant with modulus $N=p^{r}q$, Designs, Codes and Cryptography, 73, No. 2, Springer (2014), 383-392, doi: https://doi.org/10.1007/s10623-014-9928-6.

19
S. Sarkar, S. Maitra, Cryptanalysis of RSA with two decryption exponents, Information Processing Letters, 110 (2010), 178-181, doi: https://doi.org/10.1016/j.ipl.2009.11.016.

20
T. Takagi, Fast RSA-type cryptosystem modulo $p^{k}q$, Advances in Cryptology-CRYPTO'98, Springer (1998), 318-326, doi: https://doi.org/10.1007/BFb0055738.

21
M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Transaction on Information Theory IT-36, 36 (1990), 553-558, doi: https://doi.org/10.1109/18.54902.

How to Cite?

DOI: 10.12732/ijpam.v110i4.3 How to cite this paper?

Source:
International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2016
Volume: 110
Issue: 4
Pages: 587 - 607


$N=p^{2}q$%22&as_occt=any&as_epq=&as_oq=&as_eq=&as_publication=&as_ylo=&as_yhi=&as_sdtAAP=1&as_sdtp=1" title="Click to search Google Scholar for this entry" rel="nofollow">Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).