De1CTF 2020 - EasyRSA
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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