1 of 3

Low Private Component Attacks

Wiener's Attack

Wiener's attack is an attack on RSA that uses continued fractions to find the private exponent $d$ when it's small (less than $\frac{1}{3}\sqrt[4]{n}$ , where $n$ is the modulus). We know that when we pick the public exponent $e$ to be a small number and calcute its inverse $d \equiv e^{-1} \mod \phi(n)$

Wiener's theorem

Wiener's attack is based on the following theorem:

Let , with . Let . Given and with , the attacker can efficiently recover .

Some observations on RSA

In order to better understand Wiener's Attack, it may be useful to take note of certain properties of RSA:

We may start by noting that the congruence can be written as the equality for some value , we may additionally note that , since both and are much shorter than , we can say that .

Dividing the former equation by gives us , and using the latter approximation, we can write this as . Notice how the left-hand side of this equation is composed entirely of public information, this will become important later.

It is possible to quickly factor by knowing and . Consider the quadratic polynomial , this polynomial will have the roots and . Expanding it gives us , and substituting for the variables we know we can write this as . Applying the quadratic formula gives us and : , where , , and .

Wiener's attack works by expanding to a continued fraction and iterating through the terms to check various approximations of . In order to make this checking process more efficient, we can make a few observations (this part is optional):

Since is even, and and are both by definition coprime to , we know that is odd.
Given the above equations and the values of , , , and , we can solve for with the equation , thus we know that has to be divisible by .

The Attack

Suppose we have the public key , this attack will determine

Convert the fraction into a continued fraction
Iterate over each convergent in the continued fraction:
Check if the convergent is by doing the following:

Here's a sage implementation to play around with:

//TODO: Proof of Wiener's theorem

Automation

The Python module owiener simplifies the scripting process of Wiener's attack:

Here is a Wiener's attack template:

Boneh-Durfee Attack

What is Boneh-Durfee Attack

Boneh-Durfee attack is an extension of Wiener's attack. That is, it also attacks on low private component $d$ with a further relaxed condition. If $d$ satisfies:

d < N^{0.292}

Then we can use Boneh-Durfee attack to retrive $d$

this, using a graphical directed point of view, can be seen as:

\{E, n\} \xrightarrow[d < N^{0.292}]{P} \{d\}

Consider for first, see that

As stated above, the RSA's totient function can be espressed as:

continuing with the equation, we see that

and if we decide to consider and , we will have:

At this point, finding is equivalent to find the 2 small solutions and to the congruence

now let and this will preserve the scomposed subtraction

consider (with any ), we deduct that must be really closed to because is in the same order of the length of (so ), we will get

Sage Implementation

Boneh-Durfee Attack

What is Boneh-Durfee Attack

Boneh-Durfee attack is an extension of Wiener's attack. That is, it also attacks on low private component $d$ with a further relaxed condition. If $d$ satisfies:

d < N^{0.292}

Then we can use Boneh-Durfee attack to retrive $d$

this, using a graphical directed point of view, can be seen as:

\{E, n\} \xrightarrow[d < N^{0.292}]{P} \{d\}

Consider for first, see that

As stated above, the RSA's totient function can be espressed as:

continuing with the equation, we see that

and if we decide to consider and , we will have:

At this point, finding is equivalent to find the 2 small solutions and to the congruence

now let and this will preserve the scomposed subtraction

consider (with any ), we deduct that must be really closed to because is in the same order of the length of (so ), we will get

Sage Implementation

Wiener's Attack

Wiener's theorem

Wiener's attack is based on the following theorem:

Let , with . Let . Given and with , the attacker can efficiently recover .

Some observations on RSA

In order to better understand Wiener's Attack, it may be useful to take note of certain properties of RSA:

We may start by noting that the congruence can be written as the equality for some value , we may additionally note that , since both and are much shorter than , we can say that .

Since is even, and and are both by definition coprime to , we know that is odd.
Given the above equations and the values of , , , and , we can solve for with the equation , thus we know that has to be divisible by .

The Attack

Suppose we have the public key , this attack will determine

Convert the fraction into a continued fraction
Iterate over each convergent in the continued fraction:
Check if the convergent is by doing the following:

Here's a sage implementation to play around with:

//TODO: Proof of Wiener's theorem

Automation

The Python module owiener simplifies the scripting process of Wiener's attack:

Here is a Wiener's attack template:

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None
# Test to see if our attack works
if __name__ == '__main__':
    n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
    e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
    c = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
    d = wiener(e,n)
    assert not d is None, "Wiener's attack failed :("
    print(long_to_bytes(int(pow(c,d,n))).decode())

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None
# Test to see if our attack works
if __name__ == '__main__':
    n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
    e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
    c = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
    d = wiener(e,n)
    assert not d is None, "Wiener's attack failed :("
    print(long_to_bytes(int(pow(c,d,n))).decode())

Low Private Component Attacks

Wiener's Attack

hashtagWiener's theorem

hashtagSome observations on RSA

hashtagThe Attack

hashtagAutomation

Boneh-Durfee Attack

hashtagWhat is Boneh-Durfee Attack

hashtagSage Implementation

Low Private Component Attacks

Boneh-Durfee Attack

hashtagWhat is Boneh-Durfee Attack

hashtagSage Implementation

Wiener's Attack

hashtagWiener's theorem

hashtagSome observations on RSA

hashtagThe Attack

hashtagAutomation

Wiener's theorem

Some observations on RSA

The Attack

Automation

What is Boneh-Durfee Attack

Sage Implementation

What is Boneh-Durfee Attack

Sage Implementation

Wiener's theorem

Some observations on RSA

The Attack

Automation