CryptoBook
  • CryptoBook
  • Book Plan
  • Style Guide
    • Sample Page
  • Contributors
  • Fundamentals
    • Mathematical Notation
    • Division and Greatest common divisor
      • Euclidean Algorithm
    • Modular Arithmetic
      • Theorems of Wilson, Euler, and Fermat
        • Fermat's Little Theorem in Detail
        • Euler's Theorem in Detail
      • Quadratic Residues
    • Continued Fractions
  • Number Theory
  • Ideals
  • Polynomials With Shared Roots
  • Integer Factorization
    • Pollard rho
    • Sieves
  • Abstract algebra
    • Groups
      • Another take on groups
      • Discrete Log Problem
    • Rings
    • Fields
    • Polynomials
  • Elliptic Curves
    • Untitled
  • Lattices
    • Introduction
    • LLL reduction
      • Gram-Schmidt Orthogonalization
      • Lagrange's algorithm
      • LLL reduction
    • Lattice reduction
      • Minkowski reduced
      • HKZ reduced
      • LLL reduced
    • Applications
      • Coppersmith algorithm
      • Extensions of Coppersmith algorithm
    • Hard lattice problems
    • Lattices of interest
    • Cryptographic lattice problems
      • Short integer solutions (SIS)
      • Learning with errors (LWE)
      • Ring-LWE
      • NTRU
    • Interactive fun
    • Resources and notations
  • Asymmetric Cryptography
  • RSA
    • Proof of correctness
    • RSA application
    • Low Private Component Attacks
      • Wiener's Attack
      • Boneh-Durfee Attack
    • Common Modulus Attack
    • Recovering the Modulus
  • Diffie-Hellman
    • MITM
  • Elliptic Curve Cryptography
  • Symmetric Cryptography
    • Encryption
    • The One Time Pad
    • AES
      • Rijndael Finite Field
      • Round Transformations
  • Hashes
    • Introduction / overview
    • The Birthday paradox / attack
  • Isogeny Based Cryptography
    • Introduction to Isogeny Cryptography
    • Isogenies
    • Isogeny and Ramanujan Graphs
  • Appendices
    • Sets and Functions
    • Probability Theory
Powered by GitBook
On this page
  • Wiener's theorem
  • Some observations on RSA
  • The Attack
  • Automation

Was this helpful?

Export as PDF
  1. RSA
  2. Low Private Component Attacks

Wiener's Attack

PreviousLow Private Component AttacksNextBoneh-Durfee Attack

Last updated 3 years ago

Was this helpful?

Wiener's attack is an attack on RSA that uses continued fractions to find the private exponent ddd when it's small (less than 13n4\frac{1}{3}\sqrt[4]{n}31​4n​, where nnn is the modulus). We know that when we pick the public exponent eee to be a small number and calcute its inverse d≡e−1mod  ϕ(n)d \equiv e^{-1} \mod \phi(n)d≡e−1modϕ(n)

Wiener's theorem

Wiener's attack is based on the following theorem:

Let n=pqn = pqn=pq, with q<p<2qq < p < 2qq<p<2q. Let d<13n4d < \frac{1}{3}\sqrt[4]{n}d<31​4n​. Given nnn and eee with ed≡1mod  ϕ(n)ed \equiv 1 \mod \phi(n)ed≡1modϕ(n), the attacker can efficiently recover ddd.

Some observations on RSA

In order to better understand Wiener's Attack, it may be useful to take note of certain properties of RSA:

We may start by noting that the congruence ed≡1mod  ϕ(n)ed \equiv 1 \mod \phi(n)ed≡1modϕ(n) can be written as the equality ed=kϕ(n)+1ed = k\phi(n)+1ed=kϕ(n)+1 for some value kkk, we may additionally note that ϕ(n)=(p−1)(q−1)=pq−p−q+1\phi(n) = (p-1)(q-1) = pq - p - q + 1ϕ(n)=(p−1)(q−1)=pq−p−q+1, since both ppp and qqq are much shorter than pq=npq = npq=n, we can say that ϕ(n)≈n\phi(n) \approx nϕ(n)≈n.

Dividing the former equation by dϕ(n)d\phi(n)dϕ(n) gives us eϕ(n)=k+1d\frac{e}{\phi(n)} = \frac{k+1}{d}ϕ(n)e​=dk+1​, and using the latter approximation, we can write this as en≈kd\frac{e}{n} \approx \frac{k}{d}ne​≈dk​. Notice how the left-hand side of this equation is composed entirely of public information, this will become important later.

It is possible to quickly factor nnn by knowing nnn and ϕ(n)\phi(n)ϕ(n). Consider the quadratic polynomial (x−q)(x−p)(x-q)(x-p)(x−q)(x−p), this polynomial will have the roots ppp and qqq. Expanding it gives us x2−(p+q)x+pqx^2 - (p + q)x + pqx2−(p+q)x+pq, and substituting for the variables we know we can write this as x2−(n−ϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + nx2−(n−ϕ(n)+1)x+n. Applying the quadratic formula gives us ppp and qqq: p∧q=−b±b2−4ac2ap \wedge q = \frac{-b \pm \sqrt{b^2-4ac}}{2a}p∧q=2a−b±b2−4ac​​, where a=1a = 1a=1, b=n−ϕ(n)+1b = n - \phi(n) + 1b=n−ϕ(n)+1, and c=nc = nc=n.

Wiener's attack works by expanding en\frac{e}{n}ne​ to a continued fraction and iterating through the terms to check various approximations of kd\frac{k}{d}dk​. In order to make this checking process more efficient, we can make a few observations (this part is optional):

  • Since ϕ(n)\phi(n)ϕ(n) is even, and eee and ddd are both by definition coprime to ϕ(n)\phi(n)ϕ(n), we know that ddd is odd.

  • Given the above equations and the values of eee, nnn, ddd, and kkk, we can solve for ϕ(n)\phi(n)ϕ(n) with the equation ϕ(n)=ed−1k\phi(n) = \frac{ed-1}{k}ϕ(n)=ked−1​, thus we know that ed−1ed-1ed−1 has to be divisible by kkk.

  • If our ϕ(n)\phi(n)ϕ(n) is correct, the polynomial x2−(n−ϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + nx2−(n−ϕ(n)+1)x+n will have roots ppp and qqq, which we can verify by checking if pq=npq = npq=n.

The Attack

Suppose we have the public key (n,e)(n, e)(n,e), this attack will determine ddd

  1. If all convergents have been tried, and none of them work, then the given RSA parameters are not vulnerable to Wiener's attack.

Here's a sage implementation to play around with:

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None
# Test to see if our attack works
if __name__ == '__main__':
    n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
    e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
    c = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
    d = wiener(e,n)
    assert not d is None, "Wiener's attack failed :("
    print(long_to_bytes(int(pow(c,d,n))).decode())

//TODO: Proof of Wiener's theorem

Automation

The Python module owiener simplifies the scripting process of Wiener's attack:

Here is a Wiener's attack template:

#!/usr/bin/env python3
import owiener
from Crypto.Util.number import long_to_bytes

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Wiener's attack--------#

d = owiener.attack(e, N)

if d:
    m = pow(c, d, N)
    flag = long_to_bytes(m).decode()
    print(flag)
else:
    print("Wiener's Attack failed.")

Convert the fraction en\frac{e}{n}ne​ into a continued fraction [a0;a1,a2,…,ak−2,ak−1,ak][a_0;a_1,a_2, \ldots , a_{k-2},a_{k-1}, a_k][a0​;a1​,a2​,…,ak−2​,ak−1​,ak​]

Iterate over each convergent in the continued fraction: a01,a0+1a1,a0+1a1+1a2, …,a0+1a1+⋱ak−2+1ak−1,\frac{a_{0}}{1},a_{0} + \frac{1}{a_{1}},a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}}, \ \ldots, a_{0} + \frac{1}{a_{1} + \frac{\ddots} {a_{k-2} + \frac{1}{a_{k-1}}}},1a0​​,a0​+a1​1​,a0​+a1​+a2​1​1​, …,a0​+a1​+ak−2​+ak−1​1​⋱​1​,

Check if the convergent is kd\frac{k}{d}dk​ by doing the following:

Set the numerator to be kkk and denominator to be ddd

Check if ddd is odd, if not, move on to the next convergent

Check if ed≡1mod  ked \equiv 1 \mod ked≡1modk, if not, move on to the next convergent

Set ϕ(n)=ed−1k\phi(n) = \frac{ed-1}{k}ϕ(n)=ked−1​ and find the roots of the polynomial x2−(n−ϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + nx2−(n−ϕ(n)+1)x+n

If the roots of the polynomial are integers, then we've found ddd. (If not, move on to the next convergent)

LogoGitHub - orisano/owiener: A Python3 implementation of the Wiener attack on RSAGitHub
owiener