Wiener's attack is an attack on RSA that uses continued fractions to find the private exponent d when it's small (less than 31β4nβ, 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β‘eβ1modΟ(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:
If our Ο(n) is correct, the polynomial x2β(nβΟ(n)+1)x+n will have roots p and q, which we can verify by checking if pq=n.
Set the numerator to be k and denominator to be d
Check if d is odd, if not, move on to the next convergent
Check if edβ‘1modk, if not, move on to the next convergent
Set Ο(n)=kedβ1β and find the roots of the polynomial x2β(nβΟ(n)+1)x+n
If the roots of the polynomial are integers, then we've found d. (If not, move on to the next convergent)
If all convergents have been tried, and none of them work, then the given RSA parameters are not vulnerable to Wiener's attack.
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())
#!/usr/bin/env python3
import owiener
from Crypto.Util.number import long_to_bytes
#--------Data--------#
N = <N>
e = <e>
c = <c>
#--------Wiener's attack--------#
d = owiener.attack(e, N)
if d:
m = pow(c, d, N)
flag = long_to_bytes(m).decode()
print(flag)
else:
print("Wiener's Attack failed.")
