Wiener's attack

Introduction

Wiener's attack uses the continued fraction method to expose the private key d when d is small.

This attack is efficient when :

$$ d < \frac{1}{3}n^{\frac{1}{4}} $$

More information on Wikipedia.

Example

Write-up for the challenge Dachshund Attacks from picoCTF 2021.

Source code :

from Crypto.Util.number import long_to_bytes
from gmpy2 import isqrt


e = 66485515700027508124393462603307250283285433560589922749953846584350319445057850434378385036858864936995624416301155250283854028492295775511806815870240769834283989221116776654053682452967999953321125454046763105962086775969986855276743946578863359050058645755209508360174125889513337651751635233993709763703
n = 106774728126681627939368333568146834748954381924140339429116948705200702583783883904569812973644885904232513676261931492637265097244025465493777677546902927256074232367594502950952251233351032491901485509039965967881313865964941445996219261211676996512756521494649034694180698160424747599765303636899244093939
c = 21075635593431678989011904902132950778533759954604574660679053586128486625762466272222388215969770744892460903083833191261052513118155531928194905031407223419187697073366363016199725047126814786760696773849427861901117730666287515235847725694816508840449318490150711326048955427608080691090808616180851365681


def continued_fraction(n, d):
    if d == 0:
        return []
    q = n // d
    r = n - q * d
    return [q] + continued_fraction(d, r)


def convergents(n, d):
    hh, kk, h, k = 0, 1, 1, 0
    for x in continued_fraction(n, d):
        hh, kk, h, k = h, k, h * x + hh, k * x + kk
        yield h, k


def find_p_q(e, n):
    p, q = 0, 0
    for k, d in convergents(e, n):
        if k != 0:
            phi_n = (e * d - 1) // k
            a, b, c = 1, n - phi_n + 1, n
            delta = pow(b, 2) - 4 * a * c
            if delta >= 0:
                s1 = (-b + isqrt(delta)) // 2 * a
                s2 = (-b - isqrt(delta)) // 2 * a
                if n == s1 * s2:
                    return abs(s1), abs(s2)
    return -1, -1


p, q = find_p_q(e, n)
print("p =", p)
print("q =", q)
phi_n = (p - 1) * (q - 1)
d = pow(e, -1, phi_n)
m = pow(c, d, n)

print("m =", long_to_bytes(m))

Output :

p = 9197819956245901015631601728990631638418208717692563473742796988190206421909944935325440207929307570025064369215701041968300087653761740434804963205001243
q = 11608699521692076588938849927650790786391400299291753998715515591405843662304289817989671652397169970366734483213463001368870446695719828643340099914142473
m = b'picoCTF{proving_wiener_2635457}'