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