# Wiener's Attack

Using Continued Fractions to attack large e values

Last updated

Using Continued Fractions to attack large e values

Last updated

Overview

Wiener's Attack utilises the convergents of the continued fraction expansion of $\frac{k}{d}$ to attempt to guess the decryption exponent $d$ when $e$ is large, as $d$ is necessarily small as a result.

Introduction

We can say that

$\phi(N) = (p-1)(q-1) \\
= pq - (p + q) + 1 \\
\approx N$

We can also say that since $ed \equiv 1 \mod \phi(N)$, we can rearrange this to say that $ed = k\phi(N) + 1$.

$d = k\phi(N) + 1 \\
ed - k\phi(N) = 1 \\
\frac{e}{\phi(N)} - \frac{k}{d} = \frac{1}{d\phi(N)}$

Now since $d\phi(N)$ is likely to be huge, we can say $\frac{1}{d\phi(N)}$ is almost zero, and also use the approximation from before to say that

$\frac{e}{N} \approx \frac{k}{d}$

Determining the Private Information

Once we list the convergents, we iterate through and there are a few checks we can make to determine whether or not it's the correct convergent:

Solving for p, q

Note that $\frac{e}{N}$ is composed of **entirely public information**, meaning we have access to an approximation to $\frac{k}{d}$, which is **entirely private information**.

We can represent $\frac{e}{N}$ as a continued fraction. If we go through the convergents of this fraction, we may come across $\frac{k}{d}$ since $\frac{e}{N} \approx \frac{k}{d}$ ($\frac{k}{d}$ is a good approximation). This is more likely to work whendis smaller due to **Legendre’s Theorem in Diophantine Approximations **(TODO prove this), specifically when $d<\frac{1}{3}N^\frac{1}{4}$.

As $ed \equiv 1 \mod \phi(N)$ and $\phi(N)$ is even, $d$ must be odd, so we can discard convergences with even denominators.

Since $\phi(N)$ must be a whole number, we can compute $\frac{ed - 1}{k}$ and see if it returns an integer or not - if not, we can discard the convergent.

Once we find a convergent we don't discard, we can assume it's $\phi(N)$ and attempt to calculate $d$ with that, seeing if the resultant private key yields a valid result or not. This can take a **lot** of decryption attempts to work successfully however - we can speed up the "checking" process using a quadratic equation.

If we say $N=pq$, it follows that:

$\phi(N) = (p-1)(q-1) \\
\phi(N) = N - (p + q) + 1 \\
p + q = N - \phi(N) + 1$

If we now consider a quadratic equation $(x-p)(x-q) = 0$, with the roots $p$ and $q$ being the prime factors of $N$, we can expand this and substitute:

$(x-p)(x-q) = 0 \\
x^2 - (p+q)x + pq = 0 \\
x^2 - (N - \phi(N) + 1)x + N = 0$

If our value of $\phi(N)$ is correct, we can substitute this into the equation and solve it for two integer values $p$ and $q$. If the values are not integer, the result can be discarded.