Wiener's Attack

Introduction

The RSA algorithm is one of the most widely used public-key cryptographic systems. However, certain implementations present critical weaknesses, as we will see in future courses. Wiener's attack, discovered in 1990 exploits a vulnerability when the private exponent $d$ is too small relative to the modulus $N$.

RSA Basics

The RSA cryptosystem uses:

For encryption: a public exponent $e$ and a modulus $N$
For decryption: a private exponent $d$ with the same modulus $N$

The modulus $N$ is the product of two prime numbers: $N = pq$.

The fundamental relationship between these parameters is given by:

\[ed = k\varphi(N) + 1 \tag{1}\]

where $\varphi(N)$ is Euler's totient function:

\[\varphi(N) = (p-1)(q-1) = pq - (p+q) + 1 \simeq N\]

Key Approximation

For large prime numbers p and q, we can write:

\[\varphi(N) = pq - (p+q) + 1 = N - (p+q) + 1 \simeq N\]

This approximation is valid because (p+q) is negligible compared to $N=pq$ when $p$ and $q$ are large.

Mathematical Development:

Starting from equation (1), we can rewrite:

\[ed-k\varphi(N) = 1\]

Dividing by $\varphi(N)$:

\[ \begin{aligned} &\frac{ed}{\varphi(N)} - \frac{k\varphi(N)}{\varphi(N)} = \frac{1}{\varphi(N)} \\[1em] &\frac{ed}{\varphi(N)} - k = \frac{1}{\varphi(N)} \\ \end{aligned} \]

Dividing by $d$:

\[ \frac{e}{\varphi(N)} - \frac{k}{d}=\frac{1}{\varphi(N) \cdot d} \]

Let's use:

\[ \begin{cases} \varphi(N) \simeq N \\ \\ \frac{e}{\varphi(N)} - \frac{k}{d}=\frac{1}{\varphi(N) \cdot d} \\ \\ \frac{1}{Nd} \simeq 0\ \text{(Since N is really large)} \end{cases} \]

We obtain the approximation:

\[\fbox{$\frac{e}{N} \simeq \frac{k}{d}$}\]

Exploitation Using Continued Fractions

Now that we have established that $\frac{k}{d}$ approximates $\frac{e}{N}$, the attack method consists of: 1. Computing the continued fraction expansion of $\frac{e}{N}$ 2. Obtaining the successive convergents of this expansion 3. Testing each convergent $\frac{k}{d}$ as a potential candidate

Continued Fractions Principle

A continued fraction allows us to represent a rational or irrational number in the form:

\[ \cfrac{e}{N} = a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+\cfrac{1}{a_{3}+\dots}}} \]

The convergents $\cfrac{k_{i}}{d_{i}}$ are the best rational approximations of $\cfrac{e}{N}$ with a bounded denominator.

We have two main methods to check if a convergent $\cfrac{k_i}{d_{i}}$ is the correct private exponent.

Method 1: Direct Verification (Slow)

For each convergent $\cfrac{k_i}{d_{i}}$, we can verify if $d_i$ is the correct private exponent by testing if $m^{ed_{i}} \equiv m \pmod{N}$ for a test message m.

Drawback: Requires modular exponentiation ($O(\log N)$ complexity per test).

Method 2: Algebraic Resolution via Quadratic Equation

Instead of testing with encryption, we use algebra: 1. Calculate $\varphi(N) = \frac{ed_i - 1}{k_i}$ (if divisible) 2. Deduce $p + q = N - \varphi(N) + 1$ 3. Solve $x^2 - (p+q)x + N = 0$ to find $p$ and $q$ 4. Verify that $p \cdot q = N$ This method is much faster as it only uses basic arithmetic operations.

Wiener's Criterion

The attack succeeds when:

\[ d < \frac{1}{3}\cdot N^{\frac{1}{4}} \]

If this condition is satisfied, then $\frac{k}{d}$ necessarily appears among the convergents of the continued fraction expansion of $\frac{e}{N}$.

but, why $\frac{1}{3} \cdot N^{\frac{1}{4}}$ ?

See Legendre's formula, more information will come in the course.

Python Implementation

To implement this in python, we will follow the 3 steps of the attack.

Step 1 : Computing the continued fraction expansion of $\frac{e}{N}$

We can compute the continued fraction using euclidean algorithm:

def continued_fractions(n: int, d: int) -> list[int]:
    """
    Compute the continued fraction representation of n/d
    Returns the list of coefficients [a0, a1, a2, ...]
    """
    coefficients = []
    while d != 0:
        q = n // d
        coefficients.append(q)
        # That's look like Euclidean's Algorithm, It'is.
        n, d = d, n - q * d
    return coefficients

Step 2 : Obtaining the successive convergents of this expansion

def convergents(coefficients):
    p0, p1 = 0, 1
    q0, q1 = 1, 0
    convs = []
    for a in coefficients:
        p = a*p1 + p0
        q = a*q1 + q0
        convs.append((p,q))
        p0, p1 = p1, p
        q0, q1 = q1, q
    return convs

Step 3: Testing each convergent $\frac{k}{d}$ as a potential candidate

We will use the seconds method, using algebraic resolution via quadratic equation.

import math


def test_convergent(k: int, d: int, e: int, N: int) -> bool:    
    # Step 1: Check if (ed - 1) is divisible by k
    if (e * d - 1) % k != 0:
        return False

    # Calculate phi(N)
    phi = (e * d - 1) // k

    # Step 2: Calculate p + q
    s = N - phi + 1

    # Step 3: Solve x^2 - sx + N = 0
    discriminant = s * s - 4 * N

    # Check if discriminant is a perfect square
    if discriminant < 0:
        return False

    sqrt_d = math.isqrt(discriminant)
    if sqrt_d * sqrt_d != discriminant:
        return False

    # Step 4: Calculate p and q
    if (s + sqrt_d) % 2 != 0:
        return False

    p = (s + sqrt_d) // 2
    q = (s - sqrt_d) // 2

    return p * q == N and p > 1 and q > 1

Final Step: Wiener's Attack

To complete the wiener attack, you just need to use step together:

# Step 1 : Computing the continued fraction expansion of e/N
coef = continued_fractions(e, N)

# Step 2: Get all convergents
convs = convergents(coef)

# Step 3: Test each convergent
for k, d in convs:
    if k == 0:
        continue
    if test_convergent(k, d, e, N):
        print(d)
        break

Conclusion

Today, we saw how using a private exponent $d$ that is too small severely compromises RSA security. There are standards in place, and this is not just for aesthetics. Nextly, we will learn more about the Boneh-Durfee attack !