De1CTF 2020 - EasyRSA

0_writeup.py

from sage.all import *

cipher = 5089249888618459947548074759524589606478578815336059949176718157024022678024841758856813241335191315643869492784030633661717346809979076682611760035885176766380484743187692409876479000444892361744552075578050587677106211969169204446554196613453202059517114911102484740265052582801216204900709316109336061861758409342194372241877343837978525533125320239702501424169171652846761028157198499078668564324989313965631396082388643288419557330802071756151476264735731881236024649655623821974147680672733406877428067299706347289297950375309050765330625591315867546015398294367460744885903257153104507066970239487158506328863
e1 = 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491467702140263159982675018932692576847952002081478475199969962357685826609238653859264698996411770860260854720047710943051229985596674736079206428312934943752164281391573970043088475625727793169708939179742630253381871307298938827042259481077482527690653141867639100647971209354276568204913
e2 = 1089598671818931285487024526159841107695197822929259299424340503971498264804485187657064861422396497630013501691517290648230470308986030853450089582165362228856724965735826515693970375662407779866271304787454416740708203748591727184057428330386039766700161610534430469912754092586892162446358263283169799095729696407424696871657157280716343681857661748656695962441400433284766608408307217925949587261052855826382885300521822004968209647136722394587701720895365101311180886403748262958990917684186947245463537312582719347101291391169800490817330947249069884756058179616748856032431769837992142653355261794817345492723
n = 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
    
g = 4 # guessed gcd(p-1, q-1)

# =================================

F = PolynomialRing(ZZ, names='x,y,z')
x, y, z = F.gens()

# e1 * d1 - 1 == k1 * (n+1-p-q) / gcd(p-1, q-1)
# e2 * d2 - 1 == k2 * (n+1-p-q) / gcd(p-1, q-1)
# ->
# ( (p+q)*k1 * e2 - k1 * (n+1)*e2 - e2 * gcd(p-1, q-1)) % (e1*e2) = 0
# ( (p+q)*k2 * e1 - k2 * (n+1)*e1 - e1 * gcd(p-1, q-1)) % (e1*e2) = 0

# x = k1 < d1
# y = k2 < d2
# z = p+q 
N = e1*e2

# bounds
X = 2**(48+2048//3+1)
Y = 2**(48+2048//3+1)
Z = 2**1025
# total: ~2/3+1/2 = 7/6 logN
# modulus: ~2logN

pol1 = z*x*e2 - x*(n+1)*e2 - e2*g
pol2 = z*y*e1 - y*(n+1)*e1 - e1*g

# weird params
NPOLYS = 5
M = 1
m = 3

# Trivariate polynomial roots modulo
# Modified variant of
# https://link.springer.com/content/pdf/10.1007%2F978-3-540-89255-7_25.pdf
# Herrman, May, Asiacryp '08

# generate polynomial shifts
polys = []
for f in (pol1, pol2): # use both polys (redundant but ok)
    for k in range(m+1):
        fbase = f**k * N**max(0, M-k)
        
        toadd = []
        for ey in range(m+1):
            for ez in range(m+1):
                for ex in range(m+1):
                    if ex + ey + ez <= m - k:
                        toadd.append(fbase * y**ey * x**ex * z**ez)
        for p in toadd:
            p = p.subs(x=x*X, y=y*Y, z=z*Z)
            polys.append( p )

polys = sorted(set(polys))

# monomials <-> indices
monos = set()
for p in polys:
    for c, mono in p:
        monos.add(mono)

mono_order = sorted(monos)

# make matrix with lattice rows
m = matrix(ZZ, len(polys), len(mono_order))
for yi, p in enumerate(polys):
    for c, mono in p:
        xi = mono_order.index(mono)
        m[yi,xi] = c

print("LLL...", m.nrows(), "x", m.ncols())
m = m.LLL()
print("Done\n")

def topoly(hrow):
    return sum(c*mono / mono.subs(x=X,y=Y,z=Z)
               for c, mono in zip(hrow, mono_order)).change_ring(QQ)

# forming polys from coefficients
hs = []
for hrow in m:
    if not hrow:
        continue
    h = topoly(hrow)
    # estimate possible overflow of modulus
    v = int(h.subs(x=X,y=Y,z=Z))
    hs.append((h, abs(int(v // N**M))))
    if len(hs) == NPOLYS: 
        break

def recover(hs):
    # bit-by-bit solution of polynomial system
    sols = {(0, 0, 0)}
    hsmod = [h.change_ring(Zmod(2**1025)) for h in hs]
    for i in range(1025):
        if 2 <= i < 10 or i % 50 == 1 or i > 1020:
            print("solve", i, ":", len(sols), "polys", len(hs))
        if len(sols) > 200: return
        sols2 = set()
        mod = 2**i
        polys = [h.change_ring(Zmod(2*mod)) for h in hsmod]
        for bits in product(range(2), repeat=3):
            bx, by, bz = bits
            for sol in sols:
                sx, sy, sz = sol
                if bx: sx += mod
                if by: sy += mod
                if bz: sz += mod
                if any(poly.subs(x=sx, y=sy, z=sz) for poly in polys):
                    continue
                sols2.add((sx, sy, sz))
        sols = sols2
        if not sols:
            return
    
    for sx, sy, sz in sols:
        if any(poly.subs(x=sx, y=sy, z=sz) for poly in hs):
            continue
        yield sx, sy, sz

# guess overflows of modulus
from itertools import product
vs = [v for h, v in hs]

totry = list(product(*[list(range(-v, v+1)) for h, v in hs]))
totry.sort(key=lambda v:
    # some heuristic about smallest overflows
    sum([abs(a**2/(1+mx)**0.1) for a, mx in zip(v, vs)]))

for tosub in totry:
    print("trying to sub", tosub, "/", vs)
    polys = [h - c * N**M for (h, v), c in zip(hs, tosub)]
    for k1, k2, s in recover(polys):
        print("Testing solution")
        d1 = inverse_mod(e1, n-s+1)
        d2 = inverse_mod(e2, n-s+1)
        if pow(2, e1*d1, n) == 2:
            m1 = int(pow(cipher, d1, n))
            m2 = int(pow(cipher, d2, n))
            print(m1.to_bytes(256, "big").strip(b"\x00"))
            print(m2.to_bytes(256, "big").strip(b"\x00"))
            quit()

# De1CTF{4ef5e5b2-c169-47e2-b90e-9421c56f2f5e}

1_task.py

from Crypto.Util.number import *
import gmpy2
import random
from FLAG import flag

def genE(lcm,limit):
    while True:
        r = random.randint(limit,limit*0x1000000000001)
        d = gmpy2.next_prime(r)
        e = gmpy2.invert(d,lcm)
        if isPrime(e):
            break
    return e

p = getStrongPrime(1024)
q = getStrongPrime(1024)
n = p*q
lcm = gmpy2.lcm(p-1,q-1)
limit = gmpy2.iroot(n,3)[0]

e1 = genE(lcm,limit)
e2 = genE(lcm,limit)

phi = (p-1)*(q-1)
d1 = gmpy2.invert(e1,phi)
d2 = gmpy2.invert(e2,phi)

e = [e1,e2]
plain = bytes_to_long(flag)
cipher = pow(plain,e[random.getrandbits(1)],n)

print('N:' + str(n))
print('e1:' + str(e1))
print('e2:' + str(e2))
print('cipher:' + str(cipher))

2_data.txt

N: 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
e1: 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491467702140263159982675018932692576847952002081478475199969962357685826609238653859264698996411770860260854720047710943051229985596674736079206428312934943752164281391573970043088475625727793169708939179742630253381871307298938827042259481077482527690653141867639100647971209354276568204913
e2: 1089598671818931285487024526159841107695197822929259299424340503971498264804485187657064861422396497630013501691517290648230470308986030853450089582165362228856724965735826515693970375662407779866271304787454416740708203748591727184057428330386039766700161610534430469912754092586892162446358263283169799095729696407424696871657157280716343681857661748656695962441400433284766608408307217925949587261052855826382885300521822004968209647136722394587701720895365101311180886403748262958990917684186947245463537312582719347101291391169800490817330947249069884756058179616748856032431769837992142653355261794817345492723
cipher: 5089249888618459947548074759524589606478578815336059949176718157024022678024841758856813241335191315643869492784030633661717346809979076682611760035885176766380484743187692409876479000444892361744552075578050587677106211969169204446554196613453202059517114911102484740265052582801216204900709316109336061861758409342194372241877343837978525533125320239702501424169171652846761028157198499078668564324989313965631396082388643288419557330802071756151476264735731881236024649655623821974147680672733406877428067299706347289297950375309050765330625591315867546015398294367460744885903257153104507066970239487158506328863