[Re挑战题]-KMPC-wp
程序逻辑输入字符串,pad操作使长度为4的倍数,计算填充后消息总字节数除以 4,得到块数。4 字节为一块解析为整数 m,计算 p = next_prime(m),并记 Δ = p − m。v32为常量表CONST_TABLE,构造: k_i = (CONST_TABLE[i % TABLE_SIZE] ^ 0xCC) + i + (rand() % 65)将 k_i 和 p 传入KMPC,得到 v30,即该轮最终的结果。KMPC函数轮数等于 k_i,每轮进行操作:从当前值 p 开始,枚举最小正整数 x,使得 x*p+1 是质数,即为返回结果。算法伪代码: from Crypto.Util.number import *
m = bytes_to_long(b'abcd')
p = next_prime(m)
delta = p - m
print(delta)
rounds = 200
v6 = p
v7 = 0
for i in range(rounds):
v5 = 1
v7 = p * v5
v7 += 1
while not isPrime(v7):
v5 += 1
v7 = p * v5
v7 += 1
p = v7
#print(i,v5,p)
print(p)rounds=k_i的最大值为0xFF+1+64,需要根据时间戳来作为seed后计算,比较麻烦,直接爆破,逆向求解: from Crypto.Util.number import *
delta = [6, 12, 7, 6, 23, 13, 108, 5, 18, 22, 43, 18, 20, 10, 4, 19, 12, 9, 4, 4]
c = [2307430515417642170598703087707505930160785550991606260613724253818605083806744252899251602973539062287007377692542963977238696516376273662953854291493729206113488396572818506445012660359351395494710275014351500219059927470309416629, 164827326021882054700160467389127811277945378634424737531132062375406865129953011964492581532036559362210021302782216193017641986328723499982561761459054839934900876049154773065494465360196784446103024012913833641587964838499459039374934513404806021535640585967410998315240953613367223987588083784964604791646811587786831302235856936255956774362951764586701, 189523033948179602347069979420616507162910041953017694840378936580822426406915039936461268896589896025153070809659802654365279928923465029968381406754998580999027817405751382911272335798265158308500690435408461687401236643841233490327322559766000767734847429227041981020054619385212901354042937166520374538023366418987502398759215175822504434709328902701487761120418569719, 3016666616268407975955881148741564692550493743410146824395625330443588462553102742505616858011821886838900993143209176385734864468642887556202156270064434124469988489411474368356371205947697570994562286197723409370816117198056824097835504908016344310642654057301624113754693995758313360406528698908115108163749201121503335683833989794186235536461561093283508565177070442554986527695509012471972296128105768596353663, 62094221504255102909925696281974021581079168694993253616816096436948414541954309991262384169229906134243693411334803447081071761962844498064101691553431195593438104909324340846877977318061502880312403533525312392830096149392212406124603237632016570348716311538830010142319994102910050097112033516410164995864401191216877320707761794818431232891529347149, 17329427151193910190412843204510519921828563007649717405618565904796098909935705981953467839567100463639694454771770352815103024790730770156702913774000785476541223079549018080156804272783461171038455524897316166383257694831, 26368080590822728403067196614405912033389139473467947045444287981023471388459490984555886528234992925035124575186448376434083585871790378522915107709979398301526759467633970417281655473967156796854734862262703306300063466016037218222466032375221, 75514616957705773251888663111269109160411388957928808569182982376193872411968259097534896795143366041769952244653944481450885628248481790615488540113399072012331401354817486967100310720220616243094493360390279189491189751745359742507685618232338191014581794940153694337792289269367443090416375310197864452835469462643, 4199860765255189356680080736964144169231277103743231392126180076212486374718343368371396372023773724784395039646308576407752298185622350840317038894849214205247012657694183158638199675103608265367582588058577462014972798420783597474441490170301912974514607226370106412647562709787497160220542055318377776486726794490397782201836327, 56198964069224133292471994380539397275926935171824208542529333959437771082739745179269689131470272806175039558769710431264461380159474985129815580200302971049856029185281374863221794650978939262136127222463701053638102799377920152615927835925335750647891, 2272780357637140423555582755857157121364626155610705746107981401774050539254313808316898739715829477649650049385045295431821599635024221251184163250398724395515751592341793110290478092415536614435165131446362915689345598755946138986627133140092809, 1558304834719083121794992161901600418073191575379839691404283125672007602895764566728636197706453872873436874900294921792395859025595220382557262105300634250718249387996025764525732488049927845711199650077546677008228525660932947511116210321083469414891871603980140741, 325942645912201270431128589764279616629070065251426659399651392306624220205333773929347557326368163713961886948317492126325472512768264009813697437303626546072187917826800915566965611267756771687994448244363270832194843938753983780592652697768761, 81853502055467201910413565956189615690642432700977453812122030386148921348565900747037693816973778910988911889359934941802424202519795939278230048443489479676862117804881501150755013259387355961626557922723938524023077037283389207065704425172428899421, 6517900380520735950894992782044645914466509503733409311405616596403379832270251308318673975382963544220005631099802583007226128895843649175657040944362379263352906999149557, 203851889486030766848434888630577907187691727345280520254770376092218085994290448164474560867375850952979197704158056922792931823794431343278010070453077251299675325476312702722397113394858546011864275124356892573543702802124505044266123293230556335397857622923695277068730471851, 122736421387568180150802824114475587707130000407976760065468743156389673961739867538760990585169893820564068230140960498577182120705135941570720885912335787986428242477073828278977559978153882092616215573270821068991465856465224257, 7455034749129014849292133339754282007839949942650254319806736018475681898640959533838724097888024813258455331897857590167064410891749027000243583241910453796408391773522754967646564790152306901815639503034834843358746180951282583557277747975753935413, 18160624137300173535462416698543468451100920491224633109467778557753251063866887002156941184516814687612078030170806754237918713148694092537849323920587715022710252357920315409169733642209445973649738530746514043090659443172185129060411404709004102572143864747609472449008355185959362267065332600827275677891000444914746143256554103033624749, 35740328731175669467983579995860448146451330800554232601621039339903803160225437294684278918556124265649788476041514832930049229211888458387766848552492047534114486756729588320492701944923633372730564561871461758463767877164154521544388122687622472333692256430795250427747615873973465419120660122709983942641247246293838021936551]
flag = b''
for i in range(len(c)):
print(i)
v = c[i]
# 爆破rounds
for j in range(200):
# 爆破每轮的k,回溯
for k in range(1, 10000):
if (v - 1) % k == 0 and isPrime((v - 1) // k):
v = (v - 1) // k
break
if (v - delta[i]).bit_length() == 31:
flag += long_to_bytes(v - delta[i])
print(flag)
break
# b'flag{You_Have_Totally_Understood_the_Principle_Of_K-Mul_Prime_Chains_Enryption!}'