Skip to content

Instantly share code, notes, and snippets.

@hellman

hellman/0_chall.py

Created Feb 14, 2020
Embed
What would you like to do?
Codegate 2020 Quals - Munch (Crypto 750)
#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util.number import getPrime, bytes_to_long as b2l
from itertools import cycle
from random import randint
class reveal:
def __init__(self, info, bitlen):
self.coeff = cycle(info)
self.prime = getPrime(bitlen)
self.bitlen = bitlen
self.seed = randint(1, self.prime)
print("[*] Revealing...")
print(self.prime, self.seed)
print([chunk.bit_length() for chunk in info])
def __iter__(self):
return self
def __next__(self):
temp = next(self.coeff) * self.seed % self.prime
self.seed = self.seed ** 2 % self.prime
return Chall.munch(temp, self.bitlen * 9 // 10, self.bitlen)
class Chall:
def __init__(self, size, n, cutoff):
self.key = RSA.generate(size)
self.cutoff = cutoff
self.p, self.nchunks = self.key.p, 2 * n + 1
self.info = []
print(self.key.n)
def munchprime(self):
bitlen = self.p.bit_length()
for i in range(0, bitlen, 2 * bitlen // self.nchunks):
bite = self.munch(self.p, i, 2 * bitlen // self.nchunks - 35)
self.info.append(bite)
def expose(self):
leak = reveal(self.info, self.p.bit_length())
print("[*] Leaking...")
for i in range(self.cutoff):
print(next(leak))
def getflag(self):
flag = b2l(open("flag.txt", "rb").read())
c = pow(flag, self.key.e, self.key.n)
return c
@staticmethod
def munch(target, start, length):
return (target >> start) & ((1 << length) - 1)
if __name__ == "__main__":
chall = Chall(1024, 3, 200)
print("[*] Here is your challenge:")
print(chall.getflag())
chall.munchprime()
chall.expose()
from sage.all import *
from info import *
# c1 c2 c3 c4 c5 1
# p
# p
# p
# p
# p
# r1 r2 r3 r4 r5 0 9999
rec = []
for off in range(4):
outs = leak[off::4]
# ri = a * ci % p >> 450
n = len(outs)
m = matrix(ZZ, n + 2, n + 2)
s = seed
for i in range(off):
s = int(pow(s, 2, prime))
for i in range(n):
m[0,i] = s
s = int(pow(s, 2**4, prime))
m[1+i,i] = prime
m[1+n,i] = outs[i] << 460
m[0,n] = 1
m[1+n,n+1] = 10**200
ml = m.LLL()
# test = (m[0] * init[0] - m[1+n]) % prime
test = ml[-1]
out = -test[-2]
rec.append(out)
print(off, out, int(out).bit_length())
print("init =", rec)
# sage 8.9 python2
from sage.all import *
from info import *
from itertools import product
a, b, c, d = init
coef = a + (b << 146) + (c << 292) + (d << 438)
c1 = 2**111
c2 = 2**257
c3 = 2**403
F = PolynomialRing(ZZ, names='x,y,z')
x, y, z = F.gens()
N = n
f = c1 * x + c2 * y + c3 * z + coef
f = f * inverse_mod(c1, n) % n
X = Y = Z = 2**35
t = 1
m = 6
print "exp m =", m
print "exp t =", t
# generate polynomials for lattice
# https://link.springer.com/content/pdf/10.1007%2F978-3-540-89255-7_25.pdf
# Herrman, May, Asiacryp '08
polys = []
for k in xrange(m+1):
fbase = (f**k % N) * N**max(0, t-k)
print("add f**%d N**%d .." % (k, max(0, t-k)))
toadd = []
for ey in range(m+1):
for ez in range(m+1):
if ey + ez <= m - k:
toadd.append(fbase * y**ey * z**ez)
assert fbase in toadd
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)
hs = []
itr = 0
for hrow in m:
itr += 1
if not hrow:
continue
hs.append(topoly(hrow))
print "Polys", len(hs)
def recover(hs):
sols = {(0, 0, 0)}
for i in range(50):
# print("solve", i, ":", len(sols))
sols2 = set()
mod = 2**i
polys = [h.change_ring(Zmod(2*mod)) for h in hs]
# for poly in polys:
# assert poly.subs(x=s1, y=s2, z=s3) == 0
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:
print("fail", i)
return
print("sols?", i, len(sols))
for sx, sy, sz in sols:
if any(poly.subs(x=sx, y=sy, z=sz) for poly in hs):
continue
return sx, sy, sz
while True:
shuffle(hs[:20])
rec = recover(hs[:4])
if not rec:
continue
print("rec", rec)
kp = f.subs(x=rec[0], y=rec[1], z=rec[2])
pp = gcd(kp, N)
if 1 < pp < N:
print("FACTOR", pp)
qq = n // pp
d = inverse_mod(0x10001, n - pp - qq + 1)
flag = pow(encflag, d, n)
from Crypto.Util.number import *
print(long_to_bytes(flag))
# CODEGATE2020{5e7c462214d48ea48045add289f70b0619a0552bdd4201d8c20cedbfd9ce43cd}
quit()
n = 123850820426090063939750639461336535800888872303996740868393788108622197265459429269747101462736954752274429639803614452794471290719054376275608856319222801843407104278834963103014930163521479153822223511859077469170499658852892275556238914610902748238728617276564375256445353397161395711740355127024574224311
# [*] Here is your challenge:
encflag = 56546264931253064991800011273062933350432906376123256400827688151463707024780705798157442404868856565703869323810835490194009709876675990770476983384812994742572992276677277260443081273365933217994869622952757076883760367020628026475789906867095354686131932884540071471310629032433408073596634685260647480557
# [*] Revealing...
prime = 6880599843336662467879109387236213815987292188507187559989074121615354243311606616327703377828006351833629583392546362975490427453804091142854644316412663
seed = 6115683512551493681429013672578437250992709174507633110965073551143324876511315798363722262299405597781297506013981949713431316382568201987118489728973776
chunks_bitlens = [111, 109, 111, 74]
# [*] Leaking...
leak = """
365273572660559
228957749427794
1023871873444793
47252622313084
621483163501141
1613904529954105
670371640095186
746154892348423
273487816490195
151531815782072
1662852876327887
1698199163478340
1075397252623564
1505608634604579
349759022277267
1134428317370092
1914468910812945
1449958424107745
1708263912457545
1608955265676391
962961718578747
492775505618570
1449265435907005
1077616772328631
420940837638395
769389932722088
549881519479757
1676426597279872
1573991110103234
1400714164789778
581968837775620
1376374167375553
1841940053587716
420575338863847
299279483936789
1186210612325224
558893222798419
1215393260436589
1621782119801357
1320723047102254
1910717961955659
422371988218178
1513263394020288
956317417537022
1567996439899881
2193173496691391
566736180966973
81481592808825
868887510227897
897432919933712
1419950508122052
2253104843374582
1314588757176622
1349424195128398
659859552921929
1240565365943525
1693900629547647
1525267164169311
1386373255161464
1536113899311190
56234973351024
1925918815506579
287836215793395
389246591225136
1883177625103946
246236676888424
1944447510201202
608299716617507
2243764093782209
1077408515947411
1138642240666237
1751463533818637
1558555079410531
252098100710701
2239430963100067
2135594922481591
1688483945377282
1549666800062663
1464365625092491
185536557129512
1004362472376337
1948808921789811
2031903620443744
2066731879678723
578914720736828
1363465325184714
1433811139961805
1742483803193365
572175546886313
340979809399667
2171912600026334
1001051821134338
920690743143218
477941886516671
1774215443756664
1982565638845698
166099725703156
2039256848643079
1454907268385438
1603061507691847
2113704084012013
2062092461008443
1614285283894297
759891517833802
1933991890191651
1177925124477624
1686016253481693
2209855994715577
1584350556327567
593731528964815
2083066020813294
2067296679145133
689829581647088
479369674173931
883198559498913
1884907467679494
1014311704919724
754288839180058
1877376912607021
1823444794770617
869728455696930
1864749572741264
1576512935738044
1920494272459775
475282365166640
1547909564519771
1072200754479187
1447950537071799
948325829047773
1454652268959382
413950997951054
179876655529469
316322757161915
1213922549580749
766210166059710
2027301859734191
1133004743606733
2151399978580323
1491074155967000
374252276953386
413251654097948
674423904166975
1923710400363006
939078022522962
551433636957783
920487928633848
2229216155425176
1514460702803065
101282672877916
1231536851493911
817066453849768
1821037449806754
1785440539579619
567403253985889
2026106354461017
148498723126041
2270407174853085
1641168597532922
2289358538467132
139429775743343
676845953850845
2174753880306469
116625659234205
1459734450825718
975035393647684
527839506174836
409604259076605
405810742317469
2230572864819011
2111976384057693
1010755791098506
2249903249031774
1295962383729844
611323710580353
1599339020692593
480416184280072
1617286128325568
928274387980042
506796759542092
1197623032961027
372872018444
1788636647737738
1787946862093433
491126743054673
1289460442319696
1750036145448962
2287699795049243
2068193669828051
2133121457298840
1186681523752311
535668657124933
2157018791958130
63918446189908
1114159378095436
709574049560819
1320201392088036
1691566118724085
1615369417111975
960416212157945
961170133381721
"""
leak = list(map(int, leak.split()))
init = [1554892145023627672041148335479693, 502255800511355120859629514746208, 1853790210514838017041045596385832, 14893066491606236837527]
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.