Wiener's Attack

Using Continued Fractions to attack large e values

Overview

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

Introduction

We can say that

Ο•(N)=(pβˆ’1)(qβˆ’1)=pqβˆ’(p+q)+1β‰ˆN\phi(N) = (p-1)(q-1) \\ = pq - (p + q) + 1 \\ \approx N

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

d=kΟ•(N)+1edβˆ’kΟ•(N)=1eΟ•(N)βˆ’kd=1dΟ•(N)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Ο•(N)d\phi(N) is likely to be huge, we can say 1dΟ•(N)\frac{1}{d\phi(N)} is almost zero, and also use the approximation from before to say that

eNβ‰ˆkd\frac{e}{N} \approx \frac{k}{d}

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

Determining the Private Information

We can represent eN\frac{e}{N} as a continued fraction. If we go through the convergents of this fraction, we may come across kd\frac{k}{d} since eNβ‰ˆkd\frac{e}{N} \approx \frac{k}{d} (kd\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<13N14d<\frac{1}{3}N^\frac{1}{4}.

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:

  • As ed≑1mod  ϕ(N)ed \equiv 1 \mod \phi(N) and Ο•(N)\phi(N) is even, dd must be odd, so we can discard convergences with even denominators.

  • Since Ο•(N)\phi(N) must be a whole number, we can compute edβˆ’1k\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 Ο•(N)\phi(N) and attempt to calculate dd 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.

Solving for p, q

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

Ο•(N)=(pβˆ’1)(qβˆ’1)Ο•(N)=Nβˆ’(p+q)+1p+q=Nβˆ’Ο•(N)+1\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(x-p)(x-q) = 0, with the roots pp and qq being the prime factors of NN, we can expand this and substitute:

(xβˆ’p)(xβˆ’q)=0x2βˆ’(p+q)x+pq=0x2βˆ’(Nβˆ’Ο•(N)+1)x+N=0(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 Ο•(N)\phi(N) is correct, we can substitute this into the equation and solve it for two integer values pp and qq. If the values are not integer, the result can be discarded.

Last updated