Sagi Kedmi

Apr 18, 2016

Crypto Classics: Wiener's RSA Attack

When simple math pwns fancy crypto

#crypto #algo

While reading on RSA I stumbled upon Dan Boneh’s Twenty Years of Attacks on the RSA Cryptosystem 1999 paper. In there, I found a trove of applied attacks against RSA; one of which, Wiener’s, employs continued fractions approximation to break RSA efficiently (under certain conditions).

The attack was interesting enough to make me want to learn about it and spread the word.

So, today we’re going to use simple math and Python to distill Wiener’s Attack :).

Professor P
Professor P

Preliminaries

Listed below are some basic math and crypto concepts. Academic fellows might want Wiener’s original paper [1].

Continued Fractions

A simple continued fraction is an expression of the following form x=a0x=a_0:

x=a0+1a1+1a2+1a3+x = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \ldots}}}

Where aia_is are called quotients.

A continued fraction is abbreviated by its continued fraction expansion:

x=[a0,a1,a2,a3,,an]x = [a_0, a_1, a_2, a_3, \ldots, a_n]

Rational numbers (Irrational numbers) have finite (infinite) continued fraction expansions.

Simple examples:

7395=0+11+13+13+17=[0,1,3,3,7]\frac{73}{95} = 0 + \frac{1}{1 + \frac{1}{3 + \frac{1}{3 + \frac{1}{7}}}} = [0, 1, 3, 3, 7] π=[3,7,15,1,292,1,1,1,2,]\pi = [3, 7, 15, 1, 292, 1, 1, 1, 2, \ldots]

The following algorithm calculates the continued fraction expansion of a rational number with nominator nn and denominator dd.

# Continued Fraction Expansion of Rationals

def cf_expansion(n, d):
    e = []

    q = n // d
    r = n % d
    e.append(q)

    while r != 0:
        n, d = d, r
        q = n // d
        r = n % d
        e.append(q)

    return e

Rational Approximations

We know that π\pi is an irrational number. The cool thing is that we can form succinct rational approximations of π\pi using its continued fraction expansion.

c0=31=3.0c_0 = \frac{3}{1} = 3.0 c1=3+17=227=3.142857c_1 = 3 + \frac{1}{7} = \frac{22}{7} = 3.142857 c2=3+17+115=333106=3.141509c_2 = 3 + \frac{1}{7 + \frac{1}{15}} = \frac{333}{106} = 3.141509 c3=3+17+115+11=355113=3.141593c_3 = 3 + \frac{1}{7 + \frac{1}{15 + \frac{1}{1}}} = \frac{355}{113} = 3.141593 \ldots

These rational numbers (cic_i) are called the convergents of a continued fraction. As ii grows cic_i approaches π\pi (3.141592…).

The following algorithm (taken from [1]) calculates the convergents of a continued fraction expansion e=[a0,a1,,an]e = [a_0, a_1,\ldots , a_n]:

def convergents(e):
    n = [] # Nominators
    d = [] # Denominators

    for i in range(len(e)):
        if i == 0:
            ni = e[i]
            di = 1
        elif i == 1:
            ni = e[i]*e[i-1] + 1
            di = e[i]
        else: # i > 1
            ni = e[i]*n[i-1] + n[i-2]
            di = e[i]*d[i-1] + d[i-2]

        n.append(ni)
        d.append(di)
        yield (ni, di)

RSA Review

An RSA public key consists of two integers: an exponent ee and a modulus NN. NN is the product of two randomly chosen prime numbers pp and qq. The private key, dd, is the decryption exponent:

d=e1 mod (p1)(q1)=e1 mod φ(N)d = e^{-1}\ \text{mod}\ (p-1)(q-1) = e^{-1}\ \text{mod}\ \varphi(N)

Where φ(N)\varphi(N) is Euler’s totient function.

That is, there exists an integer kk such that edkφ(N)=1ed-k\varphi(N)=1, therefore:

φ(N)=ed1k\varphi(N) = \frac{ed - 1}{k}

Lets assume that the attacker has an educated guess of what kk and dd are. Using the formula above he can simply compute φ(N)\varphi(N), but what can he do with φ(N)\varphi(N)? and how can he be certain that these are the correct kk and dd?

Factoring N with φ(N)\varphi(N)

Recall that N=pqN=pq and φ(N)=(p1)(q1)\varphi(N) = (p-1)(q-1):

φ(N)=(p1)(q1)=Npq+1=NpNp+1\begin{aligned} \varphi(N) &= (p-1)(q-1) \\ &= N -p -q +1 \\ &= N -p -\frac{N}{p} + 1 \end{aligned}

Therefore:

p2+p(φ(N)N1)N=0p^2 +p(\varphi(N) -N -1) -N = 0

That is, given φ(N)\varphi(N) (NN is public knowledge) we can efficiently compute the quadratic roots p1p_1, p2p_2 and simply check if p1p2=Np_1p_2 = N to ascertain correctness.

Guessing kk and dd

Recall that edkφ(N)=1ed-k\varphi(N)=1, therefore:

eφ(N)kd=1dφ(N)\left| \frac{e}{\varphi(N)} - \frac{k}{d} \right| = \frac{1}{d\varphi(N)}

Hence, kd\frac{k}{d} is a rational approximation of eφ(N)\frac{e}{\varphi(N)} (1dφ(N)\frac{1}{d\varphi(N)} is small). Assuming the attacker has eφ(N)\frac{e}{\varphi(N)}, he may find kd\frac{k}{d} among its convergents. But… the attacker doesn’t have φ(N)\varphi(N), he only has the ee and NN.

Could it be that under certain conditions kd\frac{k}{d} may be derived from eN\frac{e}{N}?

Wiener’s Theorem

Let N=pqN=pq with q<p<2qq<p<2q. Let d<13N14d<\frac{1}{3}N^{\frac{1}{4}}. Given e,N\langle e,N \rangle with ed=1 mod φ(N)ed = 1\ \text{mod}\ \varphi(N), dd can be efficiently recovered by searching the right kd\frac{k}{d} among the convergents of eN\frac{e}{N}.

Sanity Check

So the whole attack is as follows:

  • Generate a vulnerable RSA keypair (one with short private exponent (d<13N14d<\frac{1}{3}N^{\frac{1}{4}})).
  • Find the convergents of the continued fraction expansion of eN\frac{e}{N}.
  • Iterate through the convergents diki\frac{d_i}{k_i}:

    • Compute φi(N)\varphi_i(N) using kik_i and did_i.
    • Ascertain correctness through factoring NN with φi(N)\varphi_i(N). (Alternatively, we can do [2] instead).

Lets see if it actually works.

Vulnerable Key Generation

We simply adapt the normal RSA key generation to fit the constraints on dd, qq and pp.

# Low Private Exponent Generation

import gmpy2, random
from gmpy2 import isqrt, c_div
# Adapted from Hack.lu 2014 CTF

urandom = random.SystemRandom()

def get_prime(size):
    while True:
        r = urandom.getrandbits(size)
        if gmpy2.is_prime(r): # Miller-rabin
            return r

def test_key(N, e, d):
    msg = (N - 123) >> 7
    c = pow(msg, e, N)
    return pow(c, d, N) ==  msg

def create_keypair(size):
    while True:
        p = get_prime(size // 2)
        q = get_prime(size // 2)
        if q < p < 2*q:
            break

    N = p * q
    phi_N = (p - 1) * (q - 1)

    # Recall that: d < (N^(0.25))/3
    max_d = c_div(isqrt(isqrt(N)), 3)
    max_d_bits = max_d.bit_length() - 1

    while True:
        d = urandom.getrandbits(max_d_bits)
        try:
            e = int(gmpy2.invert(d, phi_N))
        except ZeroDivisionError:
            continue
        if (e * d) % phi_N == 1:
            break
    assert test_key(N, e, d)

    return  N, e, d, p, q

The Whole Attack Flow

#!/usr/bin/python3
import cf, sys, hashlib
import vulnerable_key as vk
from sympy import *

def sha1(n):
    h = hashlib.sha1()
    h.update(str(n).encode('utf-8'))
    return h.hexdigest()

if __name__ == '__main__':
    N, e, d, p, q = vk.create_keypair(1024)
    print('[+] Generated an RSA keypair with a short private exponent.')
    print('[+] For brevity, keypair components are crypto. hashed:')
    print('[+] ++ SHA1(e):    ', sha1(e))
    print('[+] -- SHA1(d):    ', sha1(d))
    print('[+] ++ SHA1(N):    ', sha1(N))
    print('[+] -- SHA1(p):    ', sha1(p))
    print('[+] -- SHA1(q):    ', sha1(q))
    print('[+] -- SHA1(phiN): ', sha1((p - 1)*(q - 1)))
    print('[+] ------------------')

    cf_expansion = cf.get_cf_expansion(e, N)
    convergents = cf.get_convergents(cf_expansion)
    print('[+] Found the continued fractions expansion convergents of e/N.')

    print('[+] Iterating over convergents; '
            'Testing correctness through factorization.')
    print('[+] ...')
    for pk, pd in convergents: # pk - possible k, pd - possible d
        if pk == 0:
            continue;

        possible_phi = (e*pd - 1)//pk

        p = Symbol('p', integer=True)
        roots = solve(p**2 + (possible_phi - N - 1)*p + N, p)

        if len(roots) == 2:
            pp, pq = roots # pp - possible p, pq - possible q
            if pp*pq == N:
                print('[+] Factored N! :) derived keypair components:')
                print('[+] ++ SHA1(e):    ', sha1(e))
                print('[+] ++ SHA1(d):    ', sha1(pd))
                print('[+] ++ SHA1(N):    ', sha1(N))
                print('[+] ++ SHA1(p):    ', sha1(pp))
                print('[+] ++ SHA1(q):    ', sha1(pq))
                print('[+] ++ SHA1(phiN): ', sha1(possible_phi))
                sys.exit(0)

    print('[-] Wiener\'s Attack failed; Could not factor N')
    sys.exit(1)

Executing it:

$ ./wiener.py
[+] Generated an RSA keypair with a short private exponent.
[+] For brevity, keypair components are crypto. hashed:
[+] ++ SHA1(e):     cf50c0f6e658fae6bd416f7cb5b99dd2764b44fa
[+] -- SHA1(d):     1772bee24f59ea13976f03510bbc32852f02c300
[+] ++ SHA1(N):     d2d6f603c4adf7cdc0d449ca288dd130a6741c91
[+] -- SHA1(p):     d34f85dbc869626f7cab9c367bcbfec8aad8a6d3
[+] -- SHA1(q):     1e93d20bf5a79200b98441ef8b82d9f76a06df8a
[+] -- SHA1(phiN):  a5835c28d591a66e57eacdeab88a0d1d0cb3d74a
[+] ------------------
[+] Found the continued fractions expansion convergents of e/N.
[+] Iterating over convergents; Testing correctness through factorization.
[+] ...
[+] Factored N! :) derived keypair components:
[+] ++ SHA1(e):     cf50c0f6e658fae6bd416f7cb5b99dd2764b44fa
[+] ++ SHA1(d):     1772bee24f59ea13976f03510bbc32852f02c300
[+] ++ SHA1(N):     d2d6f603c4adf7cdc0d449ca288dd130a6741c91
[+] ++ SHA1(p):     1e93d20bf5a79200b98441ef8b82d9f76a06df8a
[+] ++ SHA1(q):     d34f85dbc869626f7cab9c367bcbfec8aad8a6d3
[+] ++ SHA1(phiN):  a5835c28d591a66e57eacdeab88a0d1d0cb3d74a

All used code snippets are available on github.

That’s it ! :) I hope it brought some value to you.

Comments and thoughts are welcome on this tweet:


  1. M.Wiener. Cryptanalysis of Short RSA Exponents.

  2. We could also validate correctness by encrypting usinge,N\langle e,N \rangle and decrypting using di,N\langle d_i, N \rangle. That is, pick a random message mm and test if m(m)edimod Nm \equiv (m)^{ed_i} \text{mod}\ N.


© 2020 Sagi Kedmi