Hack The Vote 2016 - SMTPresident (Crypto 400) - RSA private key partial exposure attack

1_hastad.py

#-*- coding:utf-8 -*-

"""
Hastad's broadcast attack (CRT + root in integers)
"""

import os, re
from collections import defaultdict
from libnum import *

os.system("cat emails/* >ems")
os.system('for f in pubkeys/*; do echo $f; openssl asn1parse -in "$f"; echo; done >pubs')

E = 17
id2mod = {}
s = open("pubs").read()
for id, mod in re.findall(r"pubkeys/(\w+).*?:(\w{31,})\n", s, re.DOTALL):
    id2mod[id] = int(mod, 16)

by_date = defaultdict(list)
s = open("ems").read()
for to, date, cipher in re.findall(r"From: hillary@hillaryclinton.com\nTo: (\w+)@dnc\.gov\nDate: ([\d\/]+)\nEncryption Type: RSA-2048\nContent: (\w+)\n", s):
    by_date[date].append((to, cipher))

res = ["?"] * 256
for date, ms in by_date.items():
    print date, len(ms), "msgs"
    rems = []
    mods = []
    for to, ct in ms:
        mod = int(id2mod[to])
        rems.append(int(ct, 16))
        mods.append(mod)
    c = solve_crt(rems, mods)
    m = nroot(c, E)
    assert m ** E == c
    m = n2s(m)
    print `m`
    for i, ch in enumerate(m):
        if ch != "#":
            assert res[i] == "?" or res[i] == ch
            res[i] = ch

print `"".join(res)`

'''
Result (original challenge):
"Subject: My Fellow DNC Members\nContent: Keep this safe <MISSING>28957315881597123396979748976302152737640887970674976745386517370413418317681873, that's the key we agreed on."

Updated challenge:
"Subject: My Fellow DNC Members\nContent: Keep this safe <MISSING>2639379129745732820221924615242186617297578211853941290720519611109981302570690707136540905365393, that's the key we agreed on."
'''

2_smtpresident.py

"""
Factor modulus using leaked 97 decimal digits of the private exponent.
"""

from sage.all import *

E = 0x10001
P = 10
L = 97
mod = P**L

if 1:
    # challenge
    E,C,N = (
        65537,
        87665974403152400345077381042571867203077473579612727463205456268600381221618179611248607088507602087157265518990896363173685899474912182298625946170635296927561663847805847731206803355029791082718223576008877104264333178661813748793094344203660848361984558481618464944063264037203726200290655461741881134514,
        109953083145254169793901343426857013906448850647350805103097555822991450991149833383628768990343421456495764531203068401400677799368578354290451972122801174043112323616414199027325725325866843315718644407844904985836004549165811110165566509278440906043886301390114317150851453061813590430159605716700830406237,
    )
    dlow = 2639379129745732820221924615242186617297578211853941290720519611109981302570690707136540905365393
    p = q = None
    start_k = 1
    # hint: the wanted K is 34716
else:
    # local test: generate random case
    p = next_prime(randint(1, 2**512-1))
    q = next_prime(randint(1, 2**512-1))
    N = p * q
    print "p", p
    print "q", q
    print float(log(p, N))
    print float(log(q, N))
    phi = (p-1)*(q-1)
    D = inverse_mod(E, phi)
    C = pow(0x31337, E, N)
    dlow = D % (P**L)
    print "K=", E * D // phi
    start_k = E * D // phi

def solve_quadratic_mod_power(a, b, c, p, e):
    roots = {0}
    for cure in xrange(1, e + 1):
        roots2 = set()
        curmod = p**cure
        for xbit in xrange(p):
            for r in roots:
                v = r + (xbit * p**(cure - 1))
                if (a*v*v + b*v + c) % curmod == 0:
                    roots2.add(v)
        roots = roots2
    return roots

def calc_epsilon(N, X, beta):
    return float(beta**2 - log(2*X)/log(N))

x = PolynomialRing(Zmod(N), names='x').gen()
imod = inverse_mod(mod, N)

for k in xrange(start_k, E):
    a = k
    b = E*dlow - k*N - k - 1
    c = k*N
    for plow in solve_quadratic_mod_power(a, b, c, p=P, e=L):
        print "k", k, "plow", plow
        assert (a * plow**2 + b*plow + c) % mod == 0

        # poly = (x * mod + plow)  but .small_roots want it to be monic,
        # so multiply by inverse of mod (modulo N)
        poly = (x + plow * imod)
        # 0.49 to catch both primes, or 0.5 to catch the highest only
        beta = 0.5
        # math.log(2**512/10**97, 2): 189.77297479592588
        # so 2**200 is enough
        epsilon = calc_epsilon(N=N, X=2**193, beta=beta)

        roots = poly.small_roots(beta=beta, epsilon=epsilon)

        if not roots:
            continue

        print "Roots", roots
        root = int(roots[0])

        kq = root + plow * imod
        q = gcd(N, kq)
        assert 1 < q < N, "Fail"
        p = N // q
        D = inverse_mod(E, (p - 1) * (q - 1))
        msg = pow(C, D, N)
        print msg

        # convert to str
        h = hex(int(msg))[2:].rstrip("L")
        h = "0" * (len(h) % 2) + h
        print `h.decode("hex")`
        quit()