|
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} |