# 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}}$$

## 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}'