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

Wiener's theorem

Wiener's attack is based on the following theorem:
Let
n=pqn = pq
, with
q<p<2qq < p < 2q
. Let
d<13n4d < \frac{1}{3}\sqrt[4]{n}
. Given
nn
and
ee
with
ed1modϕ(n)ed \equiv 1 \mod \phi(n)
, the attacker can efficiently recover
dd
.

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
ed1modϕ(n)ed \equiv 1 \mod \phi(n)
can be written as the equality
ed=kϕ(n)+1ed = k\phi(n)+1
for some value
kk
, we may additionally note that
ϕ(n)=(p1)(q1)=pqpq+1\phi(n) = (p-1)(q-1) = pq - p - q + 1
, since both
pp
and
qq
are much shorter than
pq=npq = n
, we can say that
ϕ(n)n\phi(n) \approx n
.
Dividing the former equation by
dϕ(n)d\phi(n)
gives us
eϕ(n)=k+1d\frac{e}{\phi(n)} = \frac{k+1}{d}
, and using the latter approximation, we can write this as
enkd\frac{e}{n} \approx \frac{k}{d}
. 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
nn
by knowing
nn
and
ϕ(n)\phi(n)
. Consider the quadratic polynomial
(xq)(xp)(x-q)(x-p)
, this polynomial will have the roots
pp
and
qq
. Expanding it gives us
x2(p+q)x+pqx^2 - (p + q)x + pq
, and substituting for the variables we know we can write this as
x2(nϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + n
. Applying the quadratic formula gives us
pp
and
qq
:
pq=b±b24ac2ap \wedge q = \frac{-b \pm \sqrt{b^2-4ac}}{2a}
, where
a=1a = 1
,
b=nϕ(n)+1b = n - \phi(n) + 1
, and
c=nc = n
.
Wiener's attack works by expanding
en\frac{e}{n}
to a continued fraction and iterating through the terms to check various approximations of
kd\frac{k}{d}
. In order to make this checking process more efficient, we can make a few observations (this part is optional):
    Since
    ϕ(n)\phi(n)
    is even, and
    ee
    and
    dd
    are both by definition coprime to
    ϕ(n)\phi(n)
    , we know that
    dd
    is odd.
    Given the above equations and the values of
    ee
    ,
    nn
    ,
    dd
    , and
    kk
    , we can solve for
    ϕ(n)\phi(n)
    with the equation
    ϕ(n)=ed1k\phi(n) = \frac{ed-1}{k}
    , thus we know that
    ed1ed-1
    has to be divisible by
    kk
    .
    If our
    ϕ(n)\phi(n)
    is correct, the polynomial
    x2(nϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + n
    will have roots
    pp
    and
    qq
    , which we can verify by checking if
    pq=npq = n
    .

The Attack

Suppose we have the public key
(n,e)(n, e)
, this attack will determine
dd
    1.
    Convert the fraction
    en\frac{e}{n}
    into a continued fraction
    [a0;a1,a2,,ak2,ak1,ak][a_0;a_1,a_2, \ldots , a_{k-2},a_{k-1}, a_k]
    2.
    Iterate over each convergent in the continued fraction:
    a01,a0+1a1,a0+1a1+1a2, ,a0+1a1+ak2+1ak1,\frac{a_{0}}{1},a_{0} + \frac{1}{a_{1}},a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}}, \ \ldots, a_{0} + \frac{1}{a_{1} + \frac{\ddots} {a_{k-2} + \frac{1}{a_{k-1}}}},
    3.
    Check if the convergent is
    kd\frac{k}{d}
    by doing the following:
      Set the numerator to be
      kk
      and denominator to be
      dd
      Check if
      dd
      is odd, if not, move on to the next convergent
      Check if
      ed1modked \equiv 1 \mod k
      , if not, move on to the next convergent
      Set
      ϕ(n)=ed1k\phi(n) = \frac{ed-1}{k}
      and find the roots of the polynomial
      x2(nϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + n
      If the roots of the polynomial are integers, then we've found
      dd
      . (If not, move on to the next convergent)
    4.
    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:
1
from Crypto.Util.number import long_to_bytes
2
3
def wiener(e, n):
4
# Convert e/n into a continued fraction
5
cf = continued_fraction(e/n)
6
convergents = cf.convergents()
7
for kd in convergents:
8
k = kd.numerator()
9
d = kd.denominator()
10
# Check if k and d meet the requirements
11
if k == 0 or d%2 == 0 or e*d % k != 1:
12
continue
13
phi = (e*d - 1)/k
14
# Create the polynomial
15
x = PolynomialRing(RationalField(), 'x').gen()
16
f = x^2 - (n-phi+1)*x + n
17
roots = f.roots()
18
# Check if polynomial as two roots
19
if len(roots) != 2:
20
continue
21
# Check if roots of the polynomial are p and q
22
p,q = int(roots[0][0]), int(roots[1][0])
23
if p*q == n:
24
return d
25
return None
26
# Test to see if our attack works
27
if __name__ == '__main__':
28
n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
29
e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
30
c = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
31
d = wiener(e,n)
32
assert not d is None, "Wiener's attack failed :("
33
print(long_to_bytes(int(pow(c,d,n))).decode())
Copied!
//TODO: Proof of Wiener's theorem

Automation

The Python module owiener simplifies the scripting process of Wiener's attack:
GitHub - orisano/owiener: A Python3 implementation of the Wiener attack on RSA
GitHub
owiener
Here is a Wiener's attack template:
1
#!/usr/bin/env python3
2
import owiener
3
from Crypto.Util.number import long_to_bytes
4
5
#--------Data--------#
6
7
N = <N>
8
e = <e>
9
c = <c>
10
11
#--------Wiener's attack--------#
12
13
d = owiener.attack(e, N)
14
15
if d:
16
m = pow(c, d, N)
17
flag = long_to_bytes(m).decode()
18
print(flag)
19
else:
20
print("Wiener's Attack failed.")
Copied!
Last modified 4mo ago