Wiener's attack is an attack on RSA that uses continued fractions to find the private exponent d when it's small (less than 314n, 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 n=pq, with q<p<2q. Let d<314n. Given n and e with ed≡1modϕ(n), the attacker can efficiently recover d.
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 ed≡1modϕ(n) can be written as the equality ed=kϕ(n)+1 for some value k, we may additionally note that ϕ(n)=(p−1)(q−1)=pq−p−q+1, since both p and q are much shorter than pq=n, we can say that ϕ(n)≈n.
Dividing the former equation by dϕ(n) gives us ϕ(n)e=dk+1, and using the latter approximation, we can write this as ne≈dk. 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 n by knowing n and ϕ(n). Consider the quadratic polynomial (x−q)(x−p), this polynomial will have the roots p and q. Expanding it gives us x2−(p+q)x+pq, and substituting for the variables we know we can write this as x2−(n−ϕ(n)+1)x+n. Applying the quadratic formula gives us p and q: p∧q=2a−b±b2−4ac, where a=1, b=n−ϕ(n)+1, and c=n.
Wiener's attack works by expanding ne to a continued fraction and iterating through the terms to check various approximations of dk. In order to make this checking process more efficient, we can make a few observations (this part is optional):
Since ϕ(n) is even, and e and d are both by definition coprime to ϕ(n), we know that d is odd.
Given the above equations and the values of e, n, d, and k, we can solve for ϕ(n) with the equation ϕ(n)=ked−1, thus we know that ed−1 has to be divisible by k.
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.
The Attack
Suppose we have the public key (n,e), this attack will determine d
Convert the fraction ne into a continued fraction [a0;a1,a2,…,ak−2,ak−1,ak]
Iterate over each convergent in the continued fraction: 1a0,a0+a11,a0+a1+a211,…,a0+a1+ak−2+ak−11⋱1,
Check if the convergent is dk by doing the following:
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.
Here's a sage implementation to play around with:
from Crypto.Util.number import long_to_bytesdefwiener(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 requirementsif k ==0or d%2==0or 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 rootsiflen(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 dreturnNone# Test to see if our attack worksif__name__=='__main__': n =6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079 e =4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743 c =5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634 d =wiener(e,n)assertnot d isNone,"Wiener's attack failed :("print(long_to_bytes(int(pow(c,d,n))).decode())
//TODO: Proof of Wiener's theorem
Automation
The Python module owiener simplifies the scripting process of Wiener's attack: