hellman/0_chall.py

## 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()

## 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)

## 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()


## 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]