twctf-twinprimes.py

#!/usr/bin/python

import math

def isqrt(n):
  x = n
  y = (x + 1) // 2
  while y < x:
    x = y
    y = (x + n // x) // 2
  return x

with open("key1", "r") as f:
  n1 = int(f.readline())
  e1 = int(f.readline())

with open("key2", "r") as f:
  n2 = int(f.readline())
  e2 = int(f.readline())

diffq = ((n2 - n1) - 4) / 2
print " [!] solving for p..."

import sympy
import sys

a = -1
b = diffq
c = 0 - n1

x = sympy.Symbol('x')
p = int(max(sympy.solve(a*x**2 + b*x + c, x)))

print " [*] quadratic equation solved"
q = n1 / p
# print q
if p * q == n1:
  print " [*] solved: p*q == n1"
else:
  print " [-] not solved: p*q != n, remainder = %d" % (n1 % p)
  sys.exit(0)

if (p+2) * (q+2) == n2:
  print " [*] confirmed: (p+2) * (q+2) == n2"
else:
  print " [-] not confirmed, twin prime does not match n2"
  sys.exit(0)

print " [+] stage2: undoing shitfest RSA"
from Crypto.Util.number import *
import Crypto.PublicKey.RSA as RSA
import os

e = long(65537)
d1 = inverse(e, (p-1)*(q-1))
d2 = inverse(e, (p+1)*(q+1))
key1 = RSA.construct((n1, e, d1))
key2 = RSA.construct((n2, e, d2))

with open("encrypted","r") as f:
  c = int(f.readline())

c = key2.decrypt(c)
c = key1.decrypt(c)
print long_to_bytes(c)