Successful cryptanalysis on RSA type modulus N=p2q

Abstract

As internet technology advances and our interactions increasingly take place online, cryptography emerges as a valuable tool to address security concerns. Cryptography serves as a means to guarantee the protection of privacy and confidential information, thereby instilling confidence when sharing and exchanging such data with other parties. One of the benefits of cryptography is providing confidentiality, which protects our information; either data in transit or data at ease. Three new attacks have been proposed on RSA type modulus N=p2q. The equation eX−NY=Z−(p2k+q2m)Y is the basis for the first attack involves random values of k and m such that k being a multiple of 2 and m being a multiple of 3, both being integers with |p2k+q2m|<N1/2 and gcd(X,Y)=1. If Z<|p2k−q2m|3(p2k+q2m|)N1/3Y and XY<N4|p2k+q2m|, then by using continued fractions, factoring N can be accomplished within polynomial time.This paper also suggested the vulnerabilities t RSA cryptosystem moduli Ns=ps2qs for t≥2 and s=1,...,t for the second and third attack. The attacks are effective if there exists a relationship between t RSA public keys (Nt,et) expressed as esx−Nsys=zs−(ps2k+qs2m)ys or esxs−Nsy=zs−(ps2k+qs2m)y, where the variables x, xs, y, ys, and zs are sufficiently small. The importance lies in the presence of an algorithm that operates within probabilistic polynomial time, which is capable of accepting public parameters as input and yield the factors p and q as output. By employing this algorithm, one can verify whether a key falls within the vulnerable class or not. This characteristic can be valuable when designing a cryptosystem during the key generation process, as it helps prevent the inadvertent creation of weak keys.

Keywords

• Continued fraction expansion
• Simultaneous Diophantine approximation
• LLL algorithm
• RSA