The new Weakness of RSA and The Algorithm to Solve this Problem

• Kritsanapong Somsuk,

Vol. 14, No. 9, September 30, 2020
10.3837/tiis.2020.09.015, Download Paper (Free):

• RSA
• Weak Parameter
• private key
• Euler’s totient value

Abstract

RSA is one of the best well-known public key cryptosystems. This methodology is widely used at present because there is not any algorithm which can break this system that has all strong parameters within polynomial time. However, it may be easily broken when at least one parameter is weak. In fact, many weak parameters are already found and are solved by some algorithms. Some examples of weak parameters consist of a small private key, a large private key, a small prime factor and a small result of the difference between two prime factors. In this paper, the new weakness of RSA is proposed. Assuming Euler’s totient value, Φ(n), can be rewritten as Φ(n) = ad + b, where d is the private key and ,ab∈, if a divides both of Φ(n) and b and the new exponent for the decryption equation is a small integer, this condition is assigned as the new weakness for breaking RSA. Firstly, the specific algorithm which is created for this weakness directly is proposed. Secondly, two equations are presented to find a, b and d. In fact, one of two equations must be implemented to find a and b at first. After that, the other equation is chosen to find d. The experimental results show that if this weakness has happened and the new exponent is small, original plaintext, m, will be recovered very fast. Furthermore, number of steps to recover d are very small when a is large. However, if a is too large, d may not be recovered because m which must be always written as m = ha is higher than modulus.

Statistics

Cite this article