πŸ–ŠοΈ
Crypto
  • Crypto
  • Fundamentals
    • Divisibility, Factors and Euclid's Algorithms
    • Modular Arithmetic
    • Rings, Fields and Euler's Totient Function
  • Further Maths
    • Continued Fractions
  • RSA
    • Overview
    • Public Exponent Attacks
      • e=1
      • Small e
      • Multi-party RSA with Small e
      • Wiener's Attack
    • Choice of Primes
      • N is prime
      • Mersenne Primes
      • P=Q
      • Fermat Factorisation
    • Factorisation Methods
      • Pollard's p-1
  • Diffie-Hellman Key Exchange
    • Overview
    • Solving the DLP
      • Baby Step, Giant Step
Powered by GitBook
On this page
  • Overview
  • Introduction
  • Determining the Private Information
  • Solving for p, q

Was this helpful?

  1. RSA
  2. Public Exponent Attacks

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}dk​ to attempt to guess the decryption exponent ddd when eee is large, as ddd 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Ο•(N)=(pβˆ’1)(qβˆ’1)=pqβˆ’(p+q)+1β‰ˆN

​We can also say that since ed≑1mod  ϕ(N)ed \equiv 1 \mod \phi(N)ed≑1modΟ•(N)​, we can rearrange this to say that ed=kΟ•(N)+1ed = k\phi(N) + 1ed=kΟ•(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)}d=kΟ•(N)+1edβˆ’kΟ•(N)=1Ο•(N)eβ€‹βˆ’dk​=dΟ•(N)1​

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

eNβ‰ˆkd\frac{e}{N} \approx \frac{k}{d}Neβ€‹β‰ˆdk​

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

Determining the Private Information

We can represent eN\frac{e}{N}Ne​ as a continued fraction. If we go through the convergents of this fraction, we may come across kd\frac{k}{d}dk​ since eNβ‰ˆkd\frac{e}{N} \approx \frac{k}{d}Neβ€‹β‰ˆdk​ (kd\frac{k}{d}dk​ 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}d<31​N41​.

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)ed≑1modΟ•(N) and Ο•(N)\phi(N)Ο•(N) is even, ddd must be odd, so we can discard convergences with even denominators.

  • Since Ο•(N)\phi(N)Ο•(N) must be a whole number, we can compute edβˆ’1k\frac{ed - 1}{k}kedβˆ’1​ 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)Ο•(N) and attempt to calculate ddd 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=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Ο•(N)=(pβˆ’1)(qβˆ’1)Ο•(N)=Nβˆ’(p+q)+1p+q=Nβˆ’Ο•(N)+1

If we now consider a quadratic equation (xβˆ’p)(xβˆ’q)=0(x-p)(x-q) = 0(xβˆ’p)(xβˆ’q)=0, with the roots ppp and qqq being the prime factors of NNN, 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(xβˆ’p)(xβˆ’q)=0x2βˆ’(p+q)x+pq=0x2βˆ’(Nβˆ’Ο•(N)+1)x+N=0

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

PreviousMulti-party RSA with Small eNextChoice of Primes

Last updated 3 years ago

Was this helpful?