hellman · February 14, 2020 18:13
diff --git a/0_chall.py b/0_chall.py
 #!/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()
diff --git a/1_solve_HNP.py b/1_solve_HNP.py
 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)
diff --git a/2_solve_bitleaks.py b/2_solve_bitleaks.py
 # 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()

diff --git a/info.py b/info.py
 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]
	#!/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=xX, y=yY, 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]