A Factorization Attack Algorithm on RSA Cryptosystem Using Fast Searching Algorithm
Yuh- Sien, Che Wun Chiou, Weicheng Sun · Journal of Applied Mathematics and Computation · 2022
The RSA cryptosystem is the first public key cryptosystem and has widely applied in privacy and ensure authenticity of digital data and included in many standards such as FIPS PUB 186-4.The security of RSA cryptosystem is heavily relied on the practical difficulty of factoring the product of p and q (N=p×q).Many studies are reported for attacking RSA cryptosystem, but no direct solving algorithms for finding p and q of the RSA cryptosystem by mathematical derivative are proposed.This paper uses strictly mathematical steps to derive out important parameters such as K=p+q, B = p-q, and N K B 4 2 -= for breaking the RSA cryptosystem.Two fast searching methods are proposed to find out the correct K value, and then two primary values p = 2 B K + and q = 2 B Kcan be computed directly.Proposed algorithms need division operations with complexity ( ) N O in average to solve the q solution and suggest some important up-down search limits to attack RSA-2048 for helping cryptanalysis on such unbroken cryptosystem.The proposed algorithms can find out the precision K value with computation complexity ( ) N O, and thus unbroken RSA cryptosystems with huge numbers such as the RSA-2048 cryptosystem will be solved immediately because exhaustive search is no more needed.