PlaidCTF 2015: curious writeup

solve_captured.py

#!/usr/bin/env python

# https://github.com/pablocelayes/rsa-wiener-attack
import RSAwienerHacker

def int2ascii(n):
	# Cut off 0x and L
	h = hex(n)[2:-1]
	# Convert each hex byte to ascii char
	return "".join([chr(int(h[i:i+2], 16)) for i in range(0, len(h), 2)])

with open("captured_a4ff19205b4a6b0a221111296439b9c7") as f:
	txt = f.read().split("\n")[1:-1]
# Magic the input into a list of lists
data = [[int(y.strip()[2:-1], 16) for y in x[1:-1].split(":")] for x in txt]

for (N, e, c) in data:
	d = RSAwienerHacker.hack_RSA(e, N)
	if d != "NOPE":
		m = pow(c, d, N)
		print(int2ascii(m))
		exit(0)

writeup.md

The description mentioned e. Looking through the given data, some of the e are greater than their respective N. Going through the toolbox of standard RSA attacks, we find Wiener's attack, which lets us recover d < 1/3*N**(1/4)

I found an implementation, and threw the numbers at it.

flag_S0Y0UKN0WW13N3R$4TT4CK!