Do you think IIT Guwahati certified course can help you in your career?
Introduction
RSA has been one of the most popular public-key cryptosystems in the world for the past 30 years. It is enormously used in a variety of applications. RSA's security is frequently based on the hardness of the integer factorization problem, which is still a well-studied problem.
On going through Dan Boneh's 1999 work, Twenty Years of Attacks on the RSA Cryptosystem, while researching RSA. There, some actual RSA attacks were discovered, one of which, Wiener's attack, effectively breaks RSA using continued fraction approximation (under certain conditions).
In this blog, we will get to know about the Low exponent attack and the decryption exponent and Wiener’s attack, i.e., Wiener's Low Decryption Exponent Attack. We will also discuss the strategy for Wiener’s attack and its algorithm.
RSA Review
An RSA public key comprises two integers: the exponent e and the modulus N. N is the product of randomly chosen prime numbers, p and q. The decryption exponent, d, is the private key:
That is, given an integer 'k' such that ed − kφ(N)=1, so:
φ(N) = (ed − 1) / k
p and q have roughly the same number of bits in a typical RSA cryptosystem, while e < n. C = Me mod n and M = Cd mod n are the encryption and decryption algorithms, respectively.
To accelerate RSA decryption, try using a small secret decryption exponent d. Whenever there is a huge difference in computing power between the two communicating devices, such as communication between a smart card and a bigger computer, using a small d is especially interesting.
Low Exponent Attack
In many real-world scenarios, a constrained device, such as a smart card, handles encryption. In certain situations, increasing M's power could be highly expensive in terms of battery life, time, etc. To streamline the encryption process, one might be tempted to alter the RSA cryptosystem by setting the public exponent to a low value, like r = 3. The only remaining step in the encryption process is to raise a number to power 3, which may be accomplished by performing two multiplications.
When RSA is employed with a low public exponent, low exponent attacks can be mounted. The attack is based on the LLL method, which is based on a technique for finding tiny solutions to low-degree polynomials. This approach for locating roots is intriguing on its own and is also utilized in other RSA system attacks.
Decryption Exponent
Let's assume n = 84773093, and the attacker has discovered that φ(n) = 84754668. The following quadratic equation results from this information:
p2 - 18426p + 84773093 = 0
The quadratic formula can be used to solve this, generating the two different roots, 9538 and 8887. These are the two factors of n. Thus if we know the value of φ(n), we can easily find out the roots of the equation.
If the decryption exponent a is known, a randomized algorithm can factor n in polynomial time. As a result, computing n is essential and no easier than factoring n. This does not, however, rule out the possibility of breaching the RSA Cryptosystem without computing a.
Wiener’s Low Decryption Exponent Attack
Wiener described a polynomial-time algorithm for cracking a typical RSA cryptosystem in 1990, i.e., if p and q are the same size and e < n. Suppose the secret exponent d has no more than one-quarter the number of bits as the modulus n. We also know that there is an integer k for which ed − kφ(N)=1.
As φ(n) ≈ n, we have k/d ≈ e/n. The following form describes the Wiener's attack:
Let N=p*q, with q<p<2q. Let d < (⅓)N1/4. Given ⟨e, N⟩ with ed = 1 mod φ(N), d can be efficiently recovered by searching the right k/d among the convergents of e/N, defined as Wiener’s attack.
So the overall strategy for Wiener’s attack is as follows:
Create a vulnerable RSA key pair (with a short private exponent d < (⅓)N1/4).
Determine the convergents of e/N continued fraction expansion.
Iterate through the di / ki convergents.
Calculate φi(N) using di and ki.
Determine correctness by multiplying N by φi(N).
Or we could also validate correctness by encrypting using ⟨e, N⟩ and decrypting using ⟨di, N⟩. That is, pick a random message mm and test if m ☰ (m)edi mod N.
Wiener’s Attack Algorithm(n, b)
(q1, . . . , qm ; rm) ← EUCLIDEAN ALGORITHM(b, n)
c0 = 1, c1 = q1
d0 = 0, d1 = 1
for j = 2 to j = m:
cj = qj cj−1 + cj−2
dj = qj dj−1 + dj−2
n’ = (dj b − 1)/cj
# n’ = φ(n) if cj/dj is the correct convergent
if n’ == integer:
let p and q be the roots of the equation
x2 − (n − n’+ 1)x + n = 0
if (p and q) >=0 and (p and q) < n:
return (p, q)
return(“FAIL”)
This attack is possible when RSA is used with a low public exponent. The attack is based on the LLL algorithm, which is based on an algorithm for finding small solutions to low-degree polynomials. This root-finding algorithm is interesting but also used in other RSA system attacks.
How secure is RSA?
The computational difficulty of factoring large integers underpins RSA security. The ability to factor more extensive numbers grows as computing power grows and more efficient factoring algorithms are discovered. Key size has a direct relationship with encryption strength.
What role does the decryption exponent play in Wiener’s attack?
If the decryption exponent a is known, a randomized algorithm can factor n in polynomial time.
What is Wiener’s Low Decryption Exponent Attack?
Let N=p*q, with q<p<2q. Let d < (⅓)N1/4. Given ⟨e, N⟩ with ed = 1 mod φ(N), d can be efficiently recovered by searching the right k/d among the convergents of e/N, defined as Wiener’s attack.
Conclusions
In this blog, we have learned about the Low exponent attack and the decryption exponent and Wiener’s attack, i.e., Wiener's Low Decryption Exponent Attack. We also discussed the strategy for Wiener’s attack and its algorithm.
Go through the below mentioned articles for a better understanding of cryptography:
569+ registered 
