pwn-thy-bytes-lotr.sage

import time
import random
from hashlib import sha256

f = open('gov_officials_PK.txt')
ns = [ int(n) for n in f.read().strip().split('\n') ]

k = 1024
b = 2*k + 128
e = 0x10001

MASK = 2^256 - 1

def rsa(x, e, N):
  q, r = x // N, x % N
  assert (q+1)*N <= 2 ** b
  return q * N + int(pow(r, e, N))

x_min = 2**(b-1) + 2**(2*k)
x_max = 2**b - 2**(2*k)
q_mins = [ x_min // n + 1 for n in ns ]
q_maxs = [ x_max // n for n in ns ]

# generate
def gen():
  ms = []
  dms = []
  h = 0
  for i in range(len(ns)):
    n, q_min, q_max = ns[i], q_mins[i], q_maxs[i]
    # base (m1) and delta (m2)
    m1 = random.randint(q_min, q_max) * n
    m2 = random.randint(q_min, q_max) * n

    ms.append(m1)
    dms.append(m1 ^^ m2)
  return ms, dms

# format to matrices A and b
def fmt(ms, dms, target):
  y = target
  for m in ms: y ^^= m
  y &= MASK

  a = [ [ (dms[i] >> j) & 1 for i in range(len(ms)) ] for j in range(256) ]
  b = [ ((y >> j) & 1) for j in range(256) ]
  return Matrix(Zmod(2), a), vector(Zmod(2), b)

tg = int(sha256('FAKE NEWS').hexdigest(), 16)

i = 0
while True:
  t = time.time()

  ms, dms = gen()
  a, b = fmt(ms, dms, tg)
  try:
    x = a.solve_right(b)
    for j in range(len(x)):
      if x[j] == 0:
        print ms[j]
      else:
        print ms[j] ^^ dms[j]
    break
  except:
    pass

  i += 1
  print 'round %d - time %.4lfs' % (i, time.time() - t)

print x