Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
RSA Review
3.
Low Exponent Attack
4.
Decryption Exponent
5.
Wiener’s Low Decryption Exponent Attack
6.
Frequently Asked Questions
6.1.
What exactly is a low exponent attack in RSA?
6.2.
How secure is RSA?
6.3.
What role does the decryption exponent play in Wiener’s attack?
6.4.
What is Wiener’s Low Decryption Exponent Attack?
7.
Conclusions
Last Updated: Mar 27, 2024
Medium

Wiener’s Low Decryption Exponent Attack on RSA

Author Rashi
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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).

Wiener’s Low Decryption Exponent Attack on RSA

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

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:

d=e−1 mod (p−1)(q−1) = e−1 mod φ(N)

φ(N) denotes Euler's totient function.

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 < nC = 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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Low Exponent Attack

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’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:
 

  • It uses the concept of Euclidean Algorithm. 
     
  • 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”)

You can also read about GCD Euclidean Algorithm here.

Frequently Asked Questions

What exactly is a low exponent attack in RSA?

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:

RSA Algorithm

What is Cryptography and Why Do We Use it?

Cryptography Hash Functions

You can refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning!

Live masterclass