# Dachshund Attacks

What if d is too small? Connect with nc mercury.picoctf.net 37455.

We are told $d$ is too small, so this is a classic Wiener's Attack. I discuss the technique here, so I won't go over it again. Connecting to the server gives us $e$, $N$ and $c$. I will use SageMath for the continued fractions.

from Crypto.Util.number import long_to_bytes

e = 112754541700690073210034568883976704637179938391109984739882317717493134117274992183187134977340726366735137168283197063242918320349494617964667665047419548553575295453656621241958205285249437600208333153358419149045651177119281187188167703425363227405679672963841306943107073166807574585389125832534066751809
N = 144390361348920501869993938709991886178924525779849244222262670433367312227444944591566139662690206095975554337178767396284003325304590032011497856478923049097805457881081418119675617493053963010551906982495811656212858357088185653656378487033852680537367010991060358788282243207315359582442103359642135446811
c = 121200875764971898969856362104661551030573743599078234011937926996191831804013529938239036069865696197047682885988162602437942341629152031466396781294970679065309433084336383355723998945746263068555929945549034859795066917254742307603845777657499038889879448604171444521283481396818702315095487896851743793699

def get_convergences(N, e):
frac = continued_fraction(e / N)
convergences = list()

for i in range(frac.length()):
convergences.append((frac.numerator(i), frac.denominator(i)))

return convergences

def factorises(N, e, numerator, denominator):
if numerator == 0:
return None

if denominator % 2 == 0:  # d must be odd
return None

phi = (e * denominator - 1) / numerator

if int(phi) % 2 != 0:  # phi must be an even whole number
return None

x = var('x')
assume(x, 'integer')
solutions = solve([x ** 2 - ((N - phi) + 1) * x + N], x)

if len(solutions) == 2:
return solutions

return None

for numerator, denominator in get_convergences(N, e):
factors = factorises(N, e, numerator, denominator)

if factors:
p, q = factors

if p * q == N:
phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, N)
print(long_to_bytes(m))
break

# picoCTF{proving_wiener_3878674}


Last updated