Leaky RSA - ASCIS CTF 2022

Challenge:

from secret import flag

Kbits1 = 120
Kbits2 = 493

p = random_prime(2^512-1, false, 2^511)
q = random_prime(2^512-1, false, 2^511)
N = p*q
e = 0x10001

# Wait this is illegal
Pdigits = p.digits(2)
leaky_p = [0]*19 + Pdigits[19:Kbits1] + [0]*19 + Pdigits[Kbits1+19:Kbits2]

c = pow(flag, e, N)
print(f"(c, e, N) = {(c, e, N)}")
print(f"leaky = {leaky_p}")

# (c, e, N) = (26332525917536404445261335188023824835582728456010807789427648382546117992477286201354477933620634042162778383500347554403856479653121560047163571802966352911016989944196656213695292273900862199180497043773236377160608017101154863030724519304212930989627167943539496731959903689581119612196554873637719776156, 65537, 107953240319236322637058433940161528510672490103418517617520324178241611238072198345853818249768509790971608169523056348162590719063088182552103689228188347112141257514135750575118448199789749158885349374251834100136760987321248910344201579746268207678856824451563937881565576119683013793260110227648499602781)
# leaky = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]

Solve:

from tqdm import tqdm

Kbits1 = 120
Kbits2 = 493

(c, e, N) = (26332525917536404445261335188023824835582728456010807789427648382546117992477286201354477933620634042162778383500347554403856479653121560047163571802966352911016989944196656213695292273900862199180497043773236377160608017101154863030724519304212930989627167943539496731959903689581119612196554873637719776156, 65537, 107953240319236322637058433940161528510672490103418517617520324178241611238072198345853818249768509790971608169523056348162590719063088182552103689228188347112141257514135750575118448199789749158885349374251834100136760987321248910344201579746268207678856824451563937881565576119683013793260110227648499602781)
leaky = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]

leaky_p = leaky

P = PolynomialRing(Zmod(N), 3, 'xyz', order='lex')
x,y,z = P.gens()

f = x +\
 (2**19)*sum([2**i * leaky_p[19+i] for i in range(Kbits1-19)]) +\
 (2**Kbits1)*y +\
 (2**(Kbits1+19))*sum([2**i * leaky_p[19+Kbits1+i] for i in range(Kbits2-(Kbits1+19))]) + \
 (2**(Kbits2))*z

def hermann_may_main(f, bounds, m, t):
    import itertools

    N = int(f.parent().characteristic())
    
    vars = f.parent().gens()
    if f.degree() > 1:
        raise ValueError
    if f.monomial_coefficient(vars[0]) != 1:
        try:
            f = f / f.monomial_coefficient(vars[0])
        except:
            print(f"inverse error: {f.monomial_coefficient(vars[0])}")
            return None
    
    f = f.change_ring(ZZ)
    vars = f.parent().gens() # on ZZ

    polylst = []
    for k in range(m):
        for i in range(m-k + 1):
            for subvars in itertools.combinations_with_replacement(vars[1:], i):
                poly = f**k * prod(subvars) * N**(max(t - k, 0))
                polylst.append(poly)
    
    monos = (f**m).monomials()
    matele = []
    for poly in polylst:
        mateleele = []
        for mono in monos:
            mateleele.append(poly.monomial_coefficient(mono)*mono.subs({vars[i]: bounds[i] for i in range(len(vars))}))
        matele += mateleele
    mat = matrix(ZZ, len(polylst), len(monos), matele)
    red, U = mat.LLL(transformation=True)
    
    redpolys = []
    for i in range(len(vars)):
        redpolys.append(sum([U[i,j]*polylst[j] for j in range(len(polylst))]))
        redpolys[i] = redpolys[i].change_ring(QQ)

    return redpolys


for m in range(5, 5+1):
    try:
        beta = 0.5
        n = len(P.gens())
        tau = 1 - (1-beta)**(1.0/n)
        t = int(m * tau)
        result = hermann_may_main(f, [2**19, 2**19, 2**19], m, t)
    except:
        continue
    x_,y_,z_ = result[0].parent().gens()
    pol1 = result[0].resultant(result[1], x_)
    pol2 = result[0].resultant(result[2], x_)
    
    smallp = PolynomialRing(QQ, 'z__')
    z__ = smallp.gens()[0]
    
    for y__val in tqdm(range(2**19, 0, -1)):
        pol1__ = pol1.subs({x_:0, y_:y__val, z_:z__})
        pol2__ = pol2.subs({x_:0, y_:y__val, z_:z__})
        pol12__ = pol1__.gcd(pol2__)
        rt_z = pol12__.roots()
        if rt_z != []:
            soly = ZZ(y__val)
            solz = ZZ(rt_z[0][0])
            solx = ZZ(result[0].subs({x_:z__, y_:soly, z_:solz}).roots()[0][0])
            print((solx, soly, solz))
            break


#solx,soly,solz = (438971, 391065, 320914)

from Crypto.Util.number import *
p = GCD(int((f.subs({x:solx, y:soly, z:solz})).lift()), N)
q = N // p

d = pow(int(e), -1, int((p-1)*(q-1)))
print(long_to_bytes(int(pow(c, d, N))))
# ASCIS{C0nGratulation_s0_Y0u_D0_kNow_about_H3rm4nN_M4y_730EF6498A3B0441B43400367B788817413F5A65A3900E2976D071232A2FC827}