Wiener's attack is based on the following theorem:
Some observations on RSA
In order to better understand Wiener's Attack, it may be useful to take note of certain properties of RSA:
The Attack
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:
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)
Let n=pq, with q<p<2q. Let d<314n. Given n and e with ed≡1modϕ(n), the attacker can efficiently recover d.
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.
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)