Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/0_writeup.py

Last active Jul 27, 2020
Embed
What would you like to do?
De1CTF 2020 - EasyRSA
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}
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))
N: 24402191928494981635640497435944050736451453218629774561432653700273120014058697415669445779441226800209154604159648942665855233706977525093135734838825433023506185915211877990448599462290859092875150657461517275171867229282791419867655722945527203477335565212992510088077874648530075739380783193891617730212062455173395228143660241234491822044677453330325054451661281530021397747260054593565182679642519767415355255125571875708238139022404975788807868905750857687120708529622235978672838872361435045431974203089535736573597127746452000608771150171882058819685487644883286497700966396731658307013308396226751130001733
e1: 4046316324291866910571514561657995962295158364702933460389468827072872865293920814266515228710438970257021065064390281148950759462687498079736672906875128944198140931482449741147988959788282715310307170986783402655196296704611285447752149956531303574680859541910243014672391229934386132475024308686852032924357952489090295552491467702140263159982675018932692576847952002081478475199969962357685826609238653859264698996411770860260854720047710943051229985596674736079206428312934943752164281391573970043088475625727793169708939179742630253381871307298938827042259481077482527690653141867639100647971209354276568204913
e2: 1089598671818931285487024526159841107695197822929259299424340503971498264804485187657064861422396497630013501691517290648230470308986030853450089582165362228856724965735826515693970375662407779866271304787454416740708203748591727184057428330386039766700161610534430469912754092586892162446358263283169799095729696407424696871657157280716343681857661748656695962441400433284766608408307217925949587261052855826382885300521822004968209647136722394587701720895365101311180886403748262958990917684186947245463537312582719347101291391169800490817330947249069884756058179616748856032431769837992142653355261794817345492723
cipher: 5089249888618459947548074759524589606478578815336059949176718157024022678024841758856813241335191315643869492784030633661717346809979076682611760035885176766380484743187692409876479000444892361744552075578050587677106211969169204446554196613453202059517114911102484740265052582801216204900709316109336061861758409342194372241877343837978525533125320239702501424169171652846761028157198499078668564324989313965631396082388643288419557330802071756151476264735731881236024649655623821974147680672733406877428067299706347289297950375309050765330625591315867546015398294367460744885903257153104507066970239487158506328863
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.