rsa-solver.py

from Crypto.PublicKey import RSA
from Crypto.Util import number

import encrypt

def load_data():
  global PUB_KEYS
  global CIPHERTEXTS
  PUB_KEYS = []
  CIPHERTEXTS = [None]  # dummy
  for i in range(10):
    with open('key-' + str(i) + '.pem', 'r') as f:
      PUB_KEYS.append(RSA.importKey(f.read()))
  for i in range(1, 6):
    with open('ciphertext-' + str(i) + '.bin', 'r') as f:
      CIPHERTEXTS.append(f.read())

TRIED = []

def try_priv_key(key):
  for i in range(1, 6):
    res = encrypt.decrypt(key, CIPHERTEXTS[i])
    if res is not None:
      print res
      return res

def gen_key(e, p, q):
  n = p*q
  phi_n = (p-1)*(q-1)
  d = number.inverse(e, phi_n)
  return RSA.construct((n, e, d, p, q))

def solve_gcd():
  for i in range(10):
    for j in range(10):
      if i == j:
	continue
      p = number.GCD(PUB_KEYS[i].n, PUB_KEYS[j].n)
      if p > 1:
	try_priv_key(gen_key(PUB_KEYS[i].e, p, PUB_KEYS[i].n / p))
	try_priv_key(gen_key(PUB_KEYS[j].e, p, PUB_KEYS[j].n / p))
	TRIED.append(i)
	TRIED.append(j)
	return

def solve_small():
  for i in range(10):
    if i in TRIED:
      continue
    n = PUB_KEYS[i].n
    def g(x):
      return (x*x + 1) % n
    starter = 2
    l = 1
    p = 1
    x = starter
    y = starter
    accum = 1
    for ix in range(200000):
      if l == p:
	y = x
	p *= 2
	l = 0
      x = g(x)
      l += 1
      accum = (accum * (x-y)) % n
      if ix % 100 != 0:
	continue
      d = number.GCD(accum, n)
      accum = 1
      if d == 1:
        continue
      elif d == n:
	starter += 1
        x = starter
        y = starter
	accum = 1
	l = 1
	p = 1
	print "had to restart pollard's rho"
        continue
      else:
        try_priv_key(gen_key(PUB_KEYS[i].e, d, n / d))
	TRIED.append(i)
        return

def solve_smooth():
  from sympy import sieve
  B = 2**16
  for i in range(10):
    if i in TRIED:
      continue
    n = PUB_KEYS[i].n
    a = 7L
    for x in sieve.primerange(1, B):
      tmp = 1
      while tmp < B:
        a = pow(a, x, n)
        tmp *= x
    g = number.GCD(a-1, n)
    if g == 1:
      continue # failed :(
    elif g == n:
      print "had to restart pollard's rho" # unlucky
    else:
      try_priv_key(gen_key(PUB_KEYS[i].e, g, n / g))
      TRIED.append(i)
      return

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

def solve_fermat():
  LIMIT = 20
  for i in range(10):
    n = PUB_KEYS[i].n
    a = isqrt(n) + 1
    for _ in range(LIMIT):
      b = isqrt(a*a - n)
      if b*b == a*a - n:
	try_priv_key(gen_key(PUB_KEYS[i].e, a-b, a+b))
	TRIED.append(i)
	return

def solve_quadr(b, c):
  # x^2 + bx + c == 0
  if b%2 != 0:
    return None, None
  # x^2 + bx + b^2/4 = b^2 / 4 - c
  discr = b**2 // 4 - c
  if discr < 0:
    return None, None
  root = isqrt(discr)
  if root*root != discr:
    return None, None
  return (b//2) + root, (b//2) - root

def solve_wiener():
  LIMIT = 4000

  for i in range(10):
    E = PUB_KEYS[i].e
    if E == 65537:
      continue
    N = PUB_KEYS[i].n
    e, n = E, N
    p0, p1 = 1, 0
    q0, q1 = 0, 1
    for _ in range(LIMIT):
      a, n, e = n // e, e, n % e
      p0, p1 = p1, p1 * a + p0
      q0, q1 = q1, q1 * a + q0

      if (E*q1 - 1) % p1 == 0:
	PHI_N = (E*q1 - 1) // p1
	P, Q = solve_quadr(N-PHI_N+1, N)
	if P is None:
	  continue
	try_priv_key(gen_key(E, P, Q))
	TRIED.append(i)
	return



if __name__=="__main__":
  load_data()
  solve_gcd()
  solve_fermat()
  solve_wiener()
  solve_smooth()
  solve_small()