Skip to content

Instantly share code, notes, and snippets.

@badmonkey7

badmonkey7/exp.py

Created September 19, 2020 15:35
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save badmonkey7/12d18efddee731669d461f9bd31fcdd2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save badmonkey7/12d18efddee731669d461f9bd31fcdd2 to your computer and use it in GitHub Desktop.
Download ZIP
2020第五空间题解
Raw
exp.py
from Crypto.Util.number import *
from sage.all import *
def lcg(seed,a,b,m):
x = seed%m
while True:
x = (a*x+b)%m
yield x
def decrypt(key,leak_data):
a,b,m = key
mlen = len(leak_data)-1
A = Matrix(ZZ,mlen,mlen)
A[0,0] = m
for i in range(1,mlen):
A[i,0] = a^i
A[i,i] = -1
AL = A.LLL()
leak_data = [leak_data[i]<<128 for i in range(32)]
delta_Y = vector([leak_data[i+1]-leak_data[i] for i in range(mlen)])
W1 = AL*delta_Y
W2 = vector([round(RR(w)/m)*m-w for w in W1])
delta_Z = AL.solve_right(W2)
delta_X = delta_Y+delta_Z
x0 = (inverse_mod(a-1,m)*(delta_X[0]-b))%m
lcg_iter = lcg(x0,a,b,m)
cur_out = next(lcg_iter)
pre_out = ((cur_out-b)*inverse_mod(a,m))%m
# print(pre_out>>128)
seed = ((pre_out-b)*inverse_mod(a,m))%m
orgin_seed = ((seed-b)*inverse_mod(a,m))%m
print(orgin_seed)
return orgin_seed
a = 14795840725848724233989125515381332891983447763911838803860161229073761165459
b = 46856731968181268756048136355293380676858169739364057598770342358628231105837
m = 75395323186914723695383746297731220829260297827914721397090336698050785547901
key = (a,b,m)
leak_data = [136252050295979513578524586196889171948, 74159806199029176365391514660175453445, 149009261329273670617645548606230622069, 10804653241785352036362691068732736466, 8301866905629821931833736018745870696, 157855582728403457694964231929562653354, 178027817844712429743828235794152230122, 80034824078666750068565497570794144445, 170373875544515217159377257439355857413, 212173471024808766218767490865913392646, 95467817412140832591838699989464945653, 173475962624021238667335879772637670470, 81228038826202736980181080253070973426, 38517665965602217903989903052781616297, 46317216313784340947138237859397553178, 73480604487960250667527460166934447951, 181632542873120638719727356775589934086, 20942574859167575225267568077383208513, 38652426910419634089323803603851872337, 45320099645552147689201245689226315649, 159381067221751927173322401473016180375, 193506543095896556423712674109718555846, 104424148854666757299886973298137655262, 128843388729958406286436691041300045263, 185545719480113124900452350138120090653, 52962693230539519899467724304596006290, 174467298993457220087453407135470977097, 108748490990737778209782462542797272925, 94970284329938606345438744396772890917, 158383211690414095044606007624481697156, 35675324836784472216060017492844885509, 149209120676432244783142365900170210500]
seed = decrypt(key,leak_data)
# seed = 172249955599053439033078493520693122929584790340636422377323636607140227
output = bin(seed)[2:]
from tqdm import tqdm
from hashlib import sha256
N = 128
X = Matrix(GF(2),N,N)
for i in tqdm(range(2**18,2**19)):
try:
tmp = output+bin(i)[2:].zfill(19)
O = [int(i) for i in tmp]
B = vector(GF(2),O[N:2*N])
for i in range(N):
X[i] = O[i:i+N]
mask = B*X.inverse()
MASK1 = ''.join([str(i) for i in mask])[::-1]
MASK2 = ''.join([str(i) for i in mask])
flag1 = int(MASK1,2)
flag2 = int(MASK2,2)
FLAG1 = "flag{"+hex(flag1).strip("0xL")+"}"
FLAG2 = "flag{"+hex(flag2).strip("0xL")+"}"
target_hex = 'cf8b3aa0b672218fa4c7b64eb82186b9d2d022f8faea2a1259e7c9fc5725c196'
if sha256(FLAG1.encode()).hexdigest() == target_hex:
print(FLAG1)
break
elif sha256(FLAG2.encode()).hexdigest() == target_hex:
print(FLAG2)
break
except:
continue
Raw
exp2.py
#!/usr/bin/python3
# @Time : 2020-09-11 15:54：07
# @Author : badmonkey
# @FileName: exp2.py
# @Software: PyCharm
import random
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
def inverse_right(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift
return tmp
# right shift with mask inverse
def inverse_right_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp >> shift & mask
return tmp
# left shift inverse
def inverse_left(res, shift, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift
return tmp
# left shift with mask inverse
def inverse_left_mask(res, shift, mask, bits=32):
tmp = res
for i in range(bits // shift):
tmp = res ^ tmp << shift & mask
return tmp
def extract_number(y,diff):
y = y^diff
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
return y&0xffffffff
def recover(y,diff):
y = inverse_right(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right(y,11)
y = y^diff
return y&0xffffffff
f = open("output","r").read()
data = f.split(',')
leak = []
enc = data[-1]
for i in data[:-1]:
leak.append(int(i))
blist = [i for i in range(256)]*3
def xor(clist):
res = 0
for i in clist:
res = res^i
return res
alist = []
for i in range(624):
alist.append(xor(blist[:i+1]))
alist = [0]+alist
def recover(y,diff):
y = inverse_right(y,18)
y = inverse_left_mask(y,15,4022730752)
y = inverse_left_mask(y,7,2636928640)
y = inverse_right(y,11)
y = y^diff
return y&0xffffffff
def extract_number(y,diff):
y = y^diff
y = y ^ y >> 11
y = y ^ y << 7 & 2636928640
y = y ^ y << 15 & 4022730752
y = y ^ y >> 18
return y&0xffffffff
state = []
for i in range(624):
tmp = recover(leak[i],alist[i])
state.append(tmp)
random.setstate((3, tuple(state + [0]), None))
key=long_to_bytes(random.getrandbits(128))
h=AES.new(key,AES.MODE_ECB)
flag = h.decrypt(bytes.fromhex(enc))
print(flag)
Raw
output.txt
243520274080122403985128153194603408953
49474323594145200559385628802580838848879021128066969607301625236641503110976
62744393699985943665652216514713475779922550735992655920946286372323674877256
69067320217543431654621424264005179125346990489881376695756002882685312972819
12944250562032716098610669372090630708
76920656073249907004018876597336693415
126422861343841715404764794697406636441
54094786367980120338368900490538312244
135775263166274965222180293863886023332
90280854500072140389540191109518275050
80270171363461427214470171427872971407
84828653120192605942548655633339296608
2902620807048991810964024307476479809
129063759501264466267843569659376536212
11837526761041015537736466393914752965
175758827504791239579565933215438218072
7889255918593387096609751962125874690
115126644876589048030929043718594270241
19267639070582093171876052852951444430
192521667882780339775995735219989425412
33883611444662338644285340925373965711
44981787723023467136623855987271611020
193358180557371895676826077053512922196
117580322751590991904932067416456205029
69730434872918356179237110196505375998
44054459993910733017949454198319752394
102685321083422665837974659533279018568
78721698549283360426844009039463589087
110039550518040813871519063899638564567
92881002991990053932643391897838352996
1309982542876420469355124257143105611
191699130333666580230735307629047037727
136553403264281766427651920148946305845
7102876254885461585348397328498345301
146729773946322797619660059295827935430
65539296642765028968798396744276990223
Raw
output2.txt
914721912,1158106598,1664171378,2079964496,2195710906,2445522187,2870099184,1762259840,3620537208,421810061,1109601937,181663827,954292323,3095444496,2732285080,343820339,30170263,2790007897,2907379311,3675964307,3098422059,2694593297,182973512,3378590757,951088280,3471438169,3355323265,4057631849,3372527366,1104560409,61544386,1919486919,2513914407,1752038956,385553422,1589170465,680188118,3580521406,3194388996,2632057200,1043805296,238783243,1815529356,1975044066,2463757915,1614604037,1139392375,770865415,3486680590,1357194806,1368619767,3637268364,2898124965,3182584275,186722929,3634328202,1183917102,4207489845,1322688575,1118430779,527227356,498412424,2189136855,2504752361,2430354335,2928862585,3100477994,2694810518,1644183631,648721518,1532400555,2090022146,3176789982,1371576046,930108070,3139089660,1466791774,2169351867,736227206,2823851960,4022511036,1040113426,3316910399,3351542676,2974946665,1030952986,3739116725,455323701,4089743345,1095035897,3392643068,39686477,2311245914,1071276688,1128822487,4195264614,706901286,1759262991,1685141393,3827645566,1417644490,1089727143,3248259870,2657061474,2177646160,4120446757,3235986006,1113205654,2542272174,3239924666,320598636,3304041662,2836653980,1081546827,3258322947,451837524,1009745703,3207424566,3419664127,3910965704,3573392783,3004773839,4223952628,574084565,3683658642,1296906623,2496054430,3911190460,1577569491,3984433900,3701306806,3532358772,1322037945,1620460066,3939563351,3409010796,1481180516,3872071318,339008934,37295031,2005772,2592152173,3743255681,964024844,4246992040,3364566492,2278408092,742935255,4258869885,2187039570,1607791709,174497982,803618006,736892326,2917233013,3152054611,2948614270,4279236943,2483414528,3577351993,1857443840,952540943,1586196093,3783957937,2094041459,1593739399,650324057,640430786,4208672197,1120589578,2828222071,279910230,2689366438,2074029708,4194602345,1436551891,4258885634,3350775787,2248377502,1433061115,1180552014,2411282437,1291013605,3092142427,2046164235,725377312,4041607894,3089045385,3825157011,1721213615,1081891241,2816251213,29000979,2050359932,3350269274,2865033094,3889996604,3986486956,1500618467,2218707561,2878951708,1985706741,3355802135,1491911277,4203695238,3556078943,2722287141,1427720333,768534152,338205459,933237037,3203640884,3650735302,3191490666,391584098,429643447,1758664220,1515727649,989621188,3673818997,2008858806,1425385565,3946781399,2278025276,2236680129,3325769218,1416292357,3173491889,693462539,3854948457,4240814275,3216601420,2729641241,2942831445,2132345971,3400983943,2998694741,444175975,536324900,1009737995,3456637476,1620878844,4098728523,2130143711,887648331,934594250,3482195318,1505222592,1953971736,4162873962,4045604491,3119339116,2242043059,1899866403,448401229,3571162873,3752328190,2704382439,870161641,2176896208,1523327738,2167622677,2488486171,3323670980,3037995693,2973493534,353176507,608651074,3891412930,3489406427,4273102772,400545256,1874482790,2851496977,3661746417,3341436754,1071619324,413423240,2640877930,152120220,127737677,2415828073,3866639372,1771581015,3126559561,2561124905,1248986227,3865843150,579326654,1904104042,3970042563,2985102338,2176090189,1280925219,1516629100,2516827045,2061659126,151754969,2448009791,1637816214,4060330218,1561616885,1011430513,2070140561,2067694175,2727264124,2942919344,3159647795,2170663140,2785251928,323834143,1228033361,1118571921,1908925334,259896739,276900613,2266323790,4279350877,3864154261,2180003667,3618348312,1342482092,2319035988,3493502874,2965444753,2058973179,4174164717,4260942208,1839663830,2788335938,841118548,1161013387,2068316012,1354655292,1179165440,480460109,2733154703,1899723902,2149849825,2923263710,4085178718,737484551,2802102314,3295060691,377480291,847376934,531594847,3568801896,1045552742,4076552362,484623249,3537997602,1510082983,4074668441,3682673018,2050517295,4019993248,563153318,3303866487,1431994107,1625999412,2903380681,3502852636,1999898464,3627948916,1256217781,3745759349,2262729348,3959088276,4001121448,979106929,3343639098,2448146507,2583722383,1101095243,4098087523,3294433171,2319320805,795222193,3703528344,2694703262,1596497654,1264130125,651659678,1781827037,1963954658,1004757671,1731164336,1540497461,2433107302,2241044226,1568642395,486485559,1054919634,4058280056,371120007,4104158518,3073471778,608093195,1236080778,499389422,353234417,1005383765,1486465426,1292340608,1429570830,3090666254,4100954623,445682978,1986341764,3738246361,1466618382,3421458483,3668531466,1129871388,1166881813,4043706622,3430513585,2916161791,1361252906,3609796675,1032590012,2525322460,1595925018,270955717,44756410,2149411918,986530801,3899134814,2076849965,757519906,145249599,2538690012,284800421,3914606667,3251200821,3731220915,451690971,25863680,3970664557,803891889,2301511904,3223815653,1319327535,1027404315,4263563900,1869143836,241868057,1055304242,1262073263,1156226528,560927469,2504073497,2562773969,2667876973,4125473750,3042728923,3021076456,3649902655,1235072967,3632328489,3699916797,652351818,2808330207,3730173598,2332685546,3201129654,1231839102,2294603137,896914448,2013262385,3904508133,3078349860,835484041,1308518138,3565656840,2409151369,666313623,3017626735,3813756385,1241011834,3270357878,1420682211,108698946,3142247211,2153046253,2668657523,3905189182,163883577,3046346709,1771400914,2785793535,3643363412,1890892913,1044922884,3826337129,386105148,1593778269,1884545790,79938815,1482971635,3436404700,2042270007,1079401022,981423837,723994219,743046209,766009973,731039598,2645312460,3703536649,2244669281,1713394577,3751316854,312074976,325599786,4238385520,2391219985,930847560,1397849016,3769591512,4292535637,4196610218,2107839811,377966591,3158202322,3370339314,377269467,283642883,3010861710,3249195448,426565814,2284021810,242720454,4112963245,1032868389,1147751073,143876520,46704323,2546757778,2789033434,3106990891,311050982,3191654227,2792542466,1351098528,2543031401,2730178247,39926384,4042096915,57806258,2498990647,3016858156,3483849558,2509387161,2113757769,1260502261,511664829,3056611050,3848046456,3202282247,3305542913,2038290373,2302393111,3811593429,4086817523,609012360,3086766702,951540682,721444063,305036799,680464969,4290612310,65062287,632749567,2700092238,3806472679,1043677707,3501175183,3831567522,1863540776,3889489864,1878813156,23060395,2054644258,3829700683,3754795039,4229190776,2235445614,363011358,1855410433,1001657319,1607118991,3756257655,2421650166,3270229943,2571081479,1897176402,848934708,3778139938,4131741677,4173231756,2721995894,2690067853,3273772598,3902721999,1283760330,2014975172,747668598,3549896684,61801694,4229339173,2784202355,237404181,3065805875,1683460753,4194742867,2430809647,2431532596,360077288,1438369909,889589789,439190437,2982845060,9d0f5c9f746ce587c6d4231057e2c83a7c4be66b96687a9bc25e7a20c2405299af682f4f702cb2b5744f7fe2b47c0ab0
Raw
task1.py
import random
from secret import flag
from Crypto.Util.number import getPrime
from hashlib import sha256
N = 128
assert flag.startswith(b"flag{")
assert flag.endswith(b"}")
assert sha256(flag).hexdigest() == '7de3b16ab9b3f02e3e59e38b447d182765381f61683bd22a8760806bf07aa6fd'
def lfsr(R, mask):
feedback = R & mask
feed_bit = bin(feedback)[2:].count("1") & 1
output_bit = R & 1
state = (R >> 1) | (feed_bit << (N - 1))
return state, output_bit
def gen_lcg(bit_length):
m = getPrime(bit_length)
a = random.randint(1, m)
b = random.randint(1, m)
return (a, b, m)
def next(state, a, b, m):
return (a * state + b) % m
def leak(seed, a, b, m):
state = seed
for i in range(32):
state = next(state, a, b, m)
print(str(state>>128))
def main():
outputs = ''
state = getPrime(N)
print(state)
mask = int(flag[5:-1], 16)
assert mask.bit_length() == N
for _ in range(237):
state, output_bit = lfsr(state, mask)
outputs += str(output_bit)
seed = int(outputs, 2)
a, b, m = gen_lcg(2*N)
print(a)
print(b)
print(m)
seed = next(seed, a, b, m)
leak(seed, a, b, m)
main()
Raw
task2.py
flag=open("flag","r").read()
import os
import random
import hashlib
from Crypto.Util.number import bytes_to_long,long_to_bytes
from Crypto.Cipher import AES
def init(r):
sl=[]
for _ in range(624):
x=os.urandom(4)
sl.append(bytes_to_long(x))
st = (3, tuple(sl + [0]), None)
r.setstate(st)
def gsu(r):
return r.getstate()[1][-1] % 624
def ss(r,sl,u):
s = (3, tuple(sl + [u]), None)
r.setstate(s)
def gsl(r):
return r.getstate()[1][:-1]
def renc(r,rkey):
sl=gsl(r)
su=gsu(r)
nsl=[]
for i in sl:
nsl.append(i^rkey)
ss(r,nsl,su)
if __name__ == "__main__":
init(random)
for _ in range(624):
print(random.getrandbits(32),end=",")
renc(random,_%256)
key=long_to_bytes(random.getrandbits(128))
h=AES.new(key,AES.MODE_ECB)
print(h.encrypt(flag.encode().zfill(48)).hex())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment