2022DASCTF_NOV-lllcccggg-wp

题目描述

如题目名字一样，有好多个lcg，当时看晕了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from Crypto.Util.number import *
key=b'*************'
key=bytes_to_long(key)
key=bin(key)[2:]

n=getPrime(256)
a=[getPrime(256)]
for i in range(1,len(key)):
    a.append(a[i-1]*2)
b=getPrime(256)
m=[]
for i in range(len(key)):
    m.append((a[i]*b)%n)
s=0
for i in range(len(key)):
    s+=m[i]*int(key[i])


seed=s
a = getPrime(300)
b = getPrime(300)
n = getPrime(300)
output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)

print("output = ",output)
print('m=',m)



state=int(key,2)
a=getPrime(256)
b=getPrime(256)
c=getPrime(256)
for _ in range(10**10000):
    state = (a * state + b) % c
flag=b'****************************************'
state_md5=hashlib.md5(str(state).encode()).hexdigest()
xorflag=xor(flag,state_md5).hex()
print('a=',a)
print('b=',b)
print('c=',c)
print('xorflag=',xorflag)

题目分析

1.key是一个背包问题，已知公钥m，和的话目前不知道。

2.以1中的和为seed，通过LCG产生了一组序列output。

至此，已经可以根据output来求出LCG中的a、b、n，从而求出seed，从而通过背包可求得key。

3.以key为seed，称作state，再进行LCG，state = (a * state + b) % c，并且a，b，c已知。

但是想要直接正向求解出最后的state，十分困难，for循环了10^10000次，这里涉及到了矩阵快速幂的使用。

通过构造矩阵 \[ \mathbf{A} = \begin{bmatrix} state & 1 \end{bmatrix} \] \[ \mathbf{C} = \begin{bmatrix} a & 0\\ b & 1\\ \end{bmatrix} \] 通过计算\(A*C^{10*10000}\)即可得到矩阵B，B = [ state, 1]

4.求出state后进行异或解密即可。

EXP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
from functools import reduce
from math import gcd
import hashlib
from Crypto.Util.number import *
import gmpy2

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return modulus

output = [75581294523880849612962675076574164955427439308298754836702542570856707873339581806556114, 85105032146983524265511965363979041936757881362506442483720291395014453678757599185295866, 1135521205967352800446368309480529634045225881261100886117662161359310082444102071893527191, 668602662320826002160475166323016971968419541611162501120982012317608523771962990634779874, 649673553234341629614052928960182629959348742983379959653724041939165898600067312959677865, 785853955591839090537858092210736716046894245185520583713505441606094906159642640920286905, 937799570303158165818350743257433287791556030352377438071495081189542968310256239806349207, 734514754865608924980327625447363286114899547828404532253101460271494241963897226149955073, 1106313725444442262780946046218124519471559148520571880678416934586056489046936771811070897, 8768152099561586039808874499029856564696410477579827751292882367683300035228537162519939]
m= [72110328606337761986452574632319920368225905906258123752738204764660440229296, 54011682421724526639264309053337133761455956763651742732220904522794415369243, 17814390052498055944887777895371560547916058478438980691186304039062365649137, 35628780104996111889775555790743121095832116956877961382372608078124731298274, 71257560209992223779551111581486242191664233913755922764745216156249462596548, 52306145629033450225461382951669777408332612778647340756234927305972460103747, 14403316467115903117281925692036847841669370508430176739214349605418455118145, 28806632934231806234563851384073695683338741016860353478428699210836910236290, 57613265868463612469127702768147391366677482033720706956857398421673820472580, 25017556945976227604614565324992075758359109018576909140459291836821175855811, 50035113891952455209229130649984151516718218037153818280918583673642351711622, 9861252992953913084817421088665596058440581025443131788581662340758238333895, 19722505985907826169634842177331192116881162050886263577163324681516476667790, 39445011971815652339269684354662384233762324101772527154326649363032953335580, 78890023943631304678539368709324768467524648203545054308653298726065906671160, 67571073096311612023437897207346829960053441358225603844051092445605348252971, 44933171401672226713234954203390952945111027667586702914846679884684231416593, 89866342803344453426469908406781905890222055335173405829693359769368462833186, 89523710815737909519298976602261104805448255621482306886131214532210460577023, 88838446840524821704957112993219502635900656194100108999006924057894456064697, 87467918890098646076273385775136298296805457339335713224758343109262447040045, 84726862989246294818905931338969889618615059629806921676261181211998428990741, 79244751187541592304171022466637072262234264210749338579266857417470392892133, 68280527584132187274701204721971437549472673372634172385278209828414320694917, 46352080377313377215761569232640168123949491696403839997300914650302176300485, 2495185963675757097882298253977629272903128343943175221346324294077887511621, 4990371927351514195764596507955258545806256687886350442692648588155775023242, 9980743854703028391529193015910517091612513375772700885385297176311550046484, 19961487709406056783058386031821034183225026751545401770770594352623100092968, 39922975418812113566116772063642068366450053503090803541541188705246200185936, 79845950837624227132233544127284136732900107006181607083082377410492400371872, 69482926884297456930826248043265566490804358963498709392909249814458335654395, 48756878977643916528011655875228426006612862878132914012562994622390206219441, 7304783164336835722382471539154145038229870707401323251870484238253947349533, 14609566328673671444764943078308290076459741414802646503740968476507894699066, 29219132657347342889529886156616580152919482829605293007481936953015789398132, 58438265314694685779059772313233160305838965659210586014963873906031578796264, 26667555838438374224478704415163613636682076269556667256672242805536692503179, 53335111676876748448957408830327227273364152539113334513344485611073385006358, 16461248562802499564273977449351747571732450029362164253433466215620304923367, 32922497125604999128547954898703495143464900058724328506866932431240609846734, 65844994251209998257095909797406990286929800117448657013733864862481219693468, 41481013711468999180550979383511273598863745186032809254212224718435974297587, 82962027422937998361101958767022547197727490372065618508424449436871948595174, 75715080054924999388563077322742387420459125695266732243593393867217432100999, 61221185318899001443485314434182067865922396341668959713931282727908399112649, 32233395846847005553329788657061428756848937634473414654607060449290333135949, 64466791693694011106659577314122857513697875268946829309214120898580666271898, 38724608596437024879678314416943008052399895489029153845172736790634867454447, 77449217192874049759356628833886016104799790978058307690345473581269734908894, 64689459594797102185072417456469325234603726907252110607435442156013004728439, 39169944398643207036503994701635943494211598765639716441615379305499544367529, 78339888797286414073007989403271886988423197531279432883230758610999088735058, 66470802803621830812375138595241067001850540013694360993206012215471712380767, 42732630816292664291109436979179427028705224978524217213156519424416959672185, 85465261632585328582218873958358854057410449957048434426313038848833919344370, 80721548474219659830796907705415001139825044865232364079370572691141373599391, 71234122157488322327952975199527295304654234681600223385485640375756282109433, 52259269524025647322265110187751883634312614314335941997715775744986099129517, 14309564257100297310889380164201060293629373579807379222176046483445733169685, 28619128514200594621778760328402120587258747159614758444352092966891466339370, 57238257028401189243557520656804241174517494319229516888704185933782932678740, 24267539265851381153474201102305775374039133589594529004152866861039400268131, 48535078531702762306948402204611550748078267179189058008305733722078800536262, 6861182272454527280255964197920394521160679309513611243355962437631135983175, 13722364544909054560511928395840789042321358619027222486711924875262271966350, 27444729089818109121023856791681578084642717238054444973423849750524543932700, 54889458179636218242047713583363156169285434476108889946847699501049087865400, 19569941568321439150454586955423605363575013903353275120439893995571710641451, 39139883136642878300909173910847210727150027806706550240879787991143421282902, 78279766273285756601818347821694421454300055613413100481759575982286842565804, 66350557755620515869995855432086135933604256177961696190263646958047220042259, 42492140720290034406350870652869564892212657307058887607271788909567974995169, 84984281440580068812701741305739129784425314614117775214543577819135949990338, 79759588090209140291762642400175552593854774179371045655831650631745434891327, 69310201389467283249884444589048398212713693309877586538407796256964404693305, 48411427987983569166128048966794089450431531570890668303560087507402344297261, 6613881185016140998615257722285471925867208092916831833864670008278223505173, 13227762370032281997230515444570943851734416185833663667729340016556447010346, 26455524740064563994461030889141887703468832371667327335458680033112894020692, 52911049480129127988922061778283775406937664743334654670917360066225788041384, 15613124169307258644203283345264843838879474437804804568579215125925110993419, 31226248338614517288406566690529687677758948875609609137158430251850221986838, 62452496677229034576813133381059375355517897751219218274316860503700443973676, 34696018563507071819985426550816043736039940453573931775378216000874422858003, 69392037127014143639970853101632087472079880907147863550756432001748845716006, 48575099463077289946300865991961467969163906765431222328257358996971226342663, 6941224135203582558960891772620228963331958481997939883259212987415987595977, 13882448270407165117921783545240457926663916963995879766518425974831975191954, 27764896540814330235843567090480915853327833927991759533036851949663950383908, 55529793081628660471687134180961831706655667855983519066073703899327900767816, 20850611372306323609733428150620956438315480663102533358891902792129336446283, 41701222744612647219466856301241912876630961326205066717783805584258672892566, 83402445489225294438933712602483825753261922652410133435567611168517345785132, 76595916187499591544226584993664944531527990255955762097879717330508226480915, 62982857584048185754812329776027182088060125463047019422503929654489987872481, 35756740377145374175983819340751657201124395877229534071752354302453510655613, 71513480754290748351967638681503314402248791754459068143504708604907021311226, 52817986717630499370294437151703921829501728460053631513753912203287577533103, 15426998644310001406948034092105136684007601871242758254252319400048689976857, 30853997288620002813896068184210273368015203742485516508504638800097379953714, 61707994577240005627792136368420546736030407484971033017009277600194759907428, 33207014363529013921943432525538386497064959921077561260763050193863054725507, 66414028727058027843886865051076772994129919842155122521526100387726109451014, 42619082663165058354132889890850839013263984635445740269796695768925753812679, 85238165326330116708265779781701678026527969270891480539593391537851507625358, 80267355861709236082890719352100649078060083492918456305931278069176550161367, 70325736932467474832140598492898591181124311936972407838607051131826635233385, 50442499073983952330640356774494475387252768825080310903958597257126805377421, 10676023357016907327639873337686243799509682601296117034661689507727145665493, 21352046714033814655279746675372487599019365202592234069323379015454291330986, 42704093428067629310559493350744975198038730405184468138646758030908582661972, 85408186856135258621118986701489950396077460810368936277293516061817165323944, 80607398921319519908597133191677193817159066571873367781331527117107865558539, 71005823051688042483553426172051680659322278094882230789407549227689266027729, 51802671312425087633466012132800654343648701140899956805559593448852066966109, 13396367833899177933291184054298601712301547232935408837863681891177668842869, 26792735667798355866582368108597203424603094465870817675727363782355337685738, 53585471335596711733164736217194406849206188931741635351454727564710675371476, 16961967880242426132688632223086106723416522814618765929653950122894885653603, 33923935760484852265377264446172213446833045629237531859307900245789771307206, 67847871520969704530754528892344426893666091258475063718615800491579542614412, 45486768250988411727868217573386146812336327468085622663976095976632620139475, 764561711025826122095594935469586649676799887306740554696686946738775189601, 1529123422051652244191189870939173299353599774613481109393373893477550379202, 3058246844103304488382379741878346598707199549226962218786747786955100758404, 6116493688206608976764759483756693197414399098453924437573495573910201516808, 12232987376413217953529518967513386394828798196907848875146991147820403033616, 24465974752826435907059037935026772789657596393815697750293982295640806067232, 48931949505652871814118075870053545579315192787631395500587964591281612134464, 7654924220354746294595311528804384183634530526398286227920424176036759179579, 15309848440709492589190623057608768367269061052796572455840848352073518359158, 30619696881418985178381246115217536734538122105593144911681696704147036718316, 61239393762837970356762492230435073469076244211186289823363393408294073436632, 32269812734724943379884144249567439963156633373508074873471281810061681783915, 64539625469449886759768288499134879926313266747016149746942563620123363567830, 38870276147948776185895736786967052877630678445167794720629622233720262046311, 77740552295897552371791473573934105755261356890335589441259244467440524092622, 65272129800844107409942106936565504535526858731806674109262983928354583095895, 40335284810737217486243373661828302096057862414748843445270462850182701102441, 80670569621474434972486747323656604192115724829497686890540925700365402204882, 71132164451997872611332654436010501409235594610130869007826346394204339320415, 52055354113044747889024468660718295843475334171397233242397187781882213551481, 13901733435138498444408097110133884711954813293929961711538870557237962013613, 27803466870276996888816194220267769423909626587859923423077741114475924027226, 55606933740553993777632388440535538847819253175719846846155482228951848054452, 21004892690156990221623936669768370720642651302575188919055459451377231019555, 42009785380313980443247873339536741441285302605150377838110918902754462039110, 84019570760627960886495746679073482882570605210300755676221837805508924078220, 77830166730304924439350653146844258790145355371737006579188170604491383067091, 65451358669658851545060466082385810605294855694609508385120836202456301044833]
a2= 102146678855348749881681741830301892566150942749854546938156269348575567682569
b2= 57926598868103510549704115342815226386495366694945712679089221082045615713293
c= 79112540456632613121737537841885533313599936328220061653608162113976717833173
xor = 0x2079677330734e7d07116d73543d03316c6501555c02403b7201080612101049
n = crack_unknown_modulus(output)
a=(output[2]-output[1])*inverse((output[1]-output[0]),n)%n
b=(output[1]-a*output[0])%n
seed = (inverse(a,n)*(output[0]-b))%n


# sage
# sum = seed
# nbits=len(m)
# A=Matrix(ZZ,nbits+1,nbits+1)
# for i in range(nbits):
#     A[i,i]=2
#     A[i,-1]=m[i]
# for i in range(nbits+1):
#     A[-1,i]=1
# A[-1,-1]=sum
# A[:,-1]=2**100
# r=A.LLL()
# for i in r:
#     if len(set(i[:-1])) == 2:
#         print(i)

key=[-1, 1, 1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, 1, 1, -1, -1, -1, 1, 1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, -1, 1, -1, 1, -1, -1, -1, -1, -1, 1, -1, -1, 1, 1, 1, -1, -1, 1, -1, -1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, 1, -1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, -1, -1, -1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, -1, -1, 0]
key0=[]
for i in range(len(key)):
    if key[i]==-1:
        key0.append(1)
    if key[i]==1:
        key0.append(0)
state = int(''.join([str(i) for i in key0]), 2)

# 矩阵快速幂
# a = 102146678855348749881681741830301892566150942749854546938156269348575567682569
# b = 57926598868103510549704115342815226386495366694945712679089221082045615713293
# c = 79112540456632613121737537841885533313599936328220061653608162113976717833173
# state = 1459518099080641908882248947391577149455413355
# A=[state,1]
# A = Matrix(Zmod(c),A)
# C = Matrix(Zmod(c),[[a, 0], [b, 1]])
# state=A*C^(10**10000)
# print(state)


state=5413978693489756582509930284917854732906886271552898511650182850401353715151
state_md5=hashlib.md5(str(state).encode()).hexdigest()
state_md5=bytes_to_long(state_md5.encode())
flag=long_to_bytes(state_md5^xor)
print(flag)
# b'DASCTF{D0u_Ge_1S_R4al1y_G00d!!!}'
CTF
#wp
2022DASCTF_NOV-lllcccggg-wp
https://sch01ar.github.io/2022/11/30/2022DASCTF_NOV-lllcccgggwp/
作者
Roo1e
发布于
2022年11月30日
许可协议