100次哈希长度拓展攻击
MD5哈希碰撞之哈希长度拓展攻击 - 阅读清单 - 腾讯云开发者社区-腾讯云 (tencent.com)
exp：
import math
from typing import Any, Dict, List
from pwn import *
from Crypto.Util.number import *
rotate_amounts = [7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21]
constants = [int(abs(math.sin(i + 1)) * 2 ** 32) & 0xFFFFFFFF for i in range(64)]
functions = 16 * [lambda b, c, d: (b & c) | (~b & d)] + \\
16 * [lambda b, c, d: (d & b) | (~d & c)] + \\
16 * [lambda b, c, d: b ^ c ^ d] + \\
16 * [lambda b, c, d: c ^ (b | ~d)]
index_functions = 16 * [lambda i: i] + \\
16 * [lambda i: (5 * i + 1) % 16] + \\
16 * [lambda i: (3 * i + 5) % 16] + \\
16 * [lambda i: (7 * i) % 16]
def get_init_values(A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> List[int]:
return [A, B, C, D]
def left_rotate(x, amount):
x &= 0xFFFFFFFF
return ((x << amount) | (x >> (32 - amount))) & 0xFFFFFFFF
def padding_message(msg: bytes) -> bytes:
"""
在MD5算法中，首先需要对输入信息进行填充，使其位长对512求余的结果等于448，并且填充必须进行，即使其位长对512求余的结果等于448。
因此，信息的位长（Bits Length）将被扩展至N*512+448，N为一个非负整数，N可以是零。
填充的方法如下：
1) 在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。
2) 在这个结果后面附加一个以64位二进制表示的填充前信息长度（单位为Bit），如果二进制表示的填充前信息长度超过64位，则取低64位。
经过这两步的处理，信息的位长=N*512+448+64=(N+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
"""
orig_len_in_bits = (8 * len(msg)) & 0xffffffffffffffff
msg += bytes([0x80])
while len(msg) % 64 != 56:
msg += bytes([0x00])
msg += orig_len_in_bits.to_bytes(8, byteorder = 'little')
return msg
def md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> int:
message = padding_message(message)
hash_pieces = get_init_values(A, B, C, D)[:]
for chunk_ofst in range(0, len(message), 64):
a, b, c, d = hash_pieces
chunk = message[chunk_ofst:chunk_ofst + 64]
for i in range(64):
f = functions[i](b, c, d)
g = index_functions[i](i)
to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
a, b, c, d = d, new_b, b, c
for i, val in enumerate([a, b, c, d]):
hash_pieces[i] += val
hash_pieces[i] &= 0xFFFFFFFF
return sum(x << (32 * i) for i, x in enumerate(hash_pieces))
def md5_to_hex(digest: int) -> str:
raw = digest.to_bytes(16, byteorder = 'little')
return '{:032x}'.format(int.from_bytes(raw, byteorder = 'big'))
def get_md5(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe, D: int = 0x10325476) -> str:
return md5_to_hex(md5(message, A, B, C, D))
def md5_attack(message: bytes, A: int = 0x67452301, B: int = 0xefcdab89, C: int = 0x98badcfe,
D: int = 0x10325476) -> int:
hash_pieces = get_init_values(A, B, C, D)[:]
for chunk_ofst in range(0, len(message), 64):
a, b, c, d = hash_pieces
chunk = message[chunk_ofst:chunk_ofst + 64]
for i in range(64):
f = functions[i](b, c, d)
g = index_functions[i](i)
to_rotate = a + f + constants[i] + int.from_bytes(chunk[4 * g:4 * g + 4], byteorder = 'little')
new_b = (b + left_rotate(to_rotate, rotate_amounts[i])) & 0xFFFFFFFF
a, b, c, d = d, new_b, b, c
for i, val in enumerate([a, b, c, d]):
hash_pieces[i] += val
hash_pieces[i] &= 0xFFFFFFFF
return sum(x << (32 * i) for i, x in enumerate(hash_pieces))
def get_init_values_from_hash_str(real_hash: str) -> List[int]:
"""
Args:
real_hash: 真实的hash结算结果
Returns: 哈希初始化值[A, B, C, D]
"""
str_list: List[str] = [real_hash[i * 8:(i + 1) * 8] for i in range(4)]
# 先按照小端字节序将十六进制字符串转换成整数，然后按照大端字节序重新读取这个数字
return [int.from_bytes(int('0x' + s, 16).to_bytes(4, byteorder = 'little'), byteorder = 'big') for s in str_list]
def get_md5_attack_materials(origin_msg: bytes, key_len: int, real_hash: str, append_data: bytes) -> Dict[str, Any]:
"""
Args:
origin_msg: 原始的消息字节流
key_len: 原始密钥（盐）的长度
real_hash: 计算出的真实的hash值
append_data: 需要添加的攻击数据
Returns: 发起攻击需要的物料信息
{
'attack_fake_msg': bytes([...]),
'attack_hash_value': str(a1b2c3d4...)
}
"""
init_values = get_init_values_from_hash_str(real_hash)
# print(['{:08x}'.format(x) for x in init_values])
# 只知道key的长度，不知道key的具体内容时，任意填充key的内容
fake_key: bytes = bytes([0xff for _ in range(key_len)])
# 计算出加了append_data后的真实填充数据
finally_padded_attack_data = padding_message(padding_message(fake_key + origin_msg) + append_data)
# 攻击者提前计算添加了攻击数据的哈希
attack_hash_value = md5_to_hex(md5_attack(finally_padded_attack_data[len(padding_message(fake_key + origin_msg)):],
A = init_values[0],
B = init_values[1],
C = init_values[2],
D = init_values[3]))
fake_padding_data = padding_message(fake_key + origin_msg)[len(fake_key + origin_msg):]
attack_fake_msg = origin_msg + fake_padding_data + append_data
return {'attack_fake_msg': attack_fake_msg, 'attack_hash_value': attack_hash_value}
sh = remote("manqiu.top",20584)
for Rounds in range(100):
print(Rounds)
sh.recvuntil(b"Round")
sh.recvuntil(b"msg:")
# 服务端根据正常的数据预先计算出来的哈希值
msg = long_to_bytes(int(sh.recvline().strip().decode(),16))
attack_data: bytes = b"zima"
sh.recvuntil(b"sign:")
h = sh.recvline().strip().decode()
md5_value = h
# 预备发起攻击，先计算构造碰撞相关的参数
attack_materials = get_md5_attack_materials(msg, 32, md5_value, attack_data)
newmsg = attack_materials['attack_fake_msg']
h = attack_materials['attack_hash_value']
sh.sendline(newmsg.hex().encode())
sh.sendline(h.encode())
sh.recvline()
sh.recvline()
print(sh.recvline())
#VNCTF{append_key_instead_of_message#6603db4e}
传一个超递增序列过去，为了简单取2^n，相当于我们手上有私钥，那么就可以恢复rr，那么做一个简单的模2减法（xor）即可获得flag。
交互传数据：
from pwn import *
def get_ii():
r = [2]
for x in range(256 - 1):
r.append(2 * r[-1])
print(r)
print()
return str(r)[1:-1]
def dec(S,r):
ans = []
for t in r[::-1]:
if S >= t:
ans.append(1)
S -= t
print(f'find {t}, S <- {S}')
else:
ans.append(0)
return ans[::-1]
io = remote('manqiu.top',20456)
print(io.recvuntil(b"Undoubtedly, this is a backdoor left for you: "))
ii = get_ii()
io.sendline(ii.encode())
io.interactive()
flag：
from Crypto.Util.number import *
r = [2]
for x in range(256 - 1):
r.append(2*r[-1])
print(r)
print(str(r)[1:-1])
def dec(S,r):
ans = []
for t in r[::-1]:
if S >= t:
ans.append(1)
S -= t
print(f'find {t}, S <- {S}')
else:
ans.append(0)
return ans[::-1]
s = [179451767990794616947262847232020748116433644630345646618220193879775616294500, 139134938966897335093122811549647229634971798268672235965814865710116021280452, 48107960420342850794914857723820353291941390656225913211555657721969670670984, 215778418789168623531802177826160601971839492711531383067369879291387780396078, 217511912142186136236877125143825321663279868851009641815088462314252724086998, 196385589819148033367736348654351940175701368035251720407587867511524085010906, 55902944467485333181165499322678454297992168401686278919017913899827881743414, 229733407233976167587576839095647421580096334366514532709851954446345296300910, 78889094874062889491911150720899291650633925513885395712750983090007613563310, 42089117087600817284935897268337069912865156985855303460778943135418268598158, 185300017723943488284409488292379208190738692934304225516766014532941597610362, 199367483981277516911666919111842259364985821264070935849377546898819569252782, 192894073672636815084451720483598133211978392118119465545650439474695264018124, 187470577957299459352805959401926664248851933603247658465657024111095289421156, 148953505636439996989217442340416960379069324595270359663012943544314569055510, 12621940333638732922918621931364588374230478673758179913060578617723982292084, 184898201047430265632837279469753422107359401987076083472104660977812425945934, 158139606503780164866418505778293020906613470905772396789968299162957553228694, 151558924566173312789172029209768227208561201754370679671687982428113352725142, 210056317378895900893995310934690525551435340271752898333890558314233556210304, 64970181892852858716359319812561689117250768617127551215614840552494956164984, 5487393390031439362427684168681256461550352852983419530644724176827835002006, 181473064307042757553079780705605832532475062424320196211045146701154576932042, 79842688500330258137131637191013285665226547299472584354136812980510700457350, 183164402048219893059793541766733341111429034244283301129706822600213203693988, 81291529549495656034607544596429961078068902516744698100098208845981219829390, 79298734323001685963163453531156426889484405974227302149464054329071153267214, 54276486743337376942698283134951424660570490029990314800707188315710202570438, 199624501962412893251162563292964237826928266231612916961138558105478642230716, 197027388193460169599391860200447180124689913681302370168607263712977328985974, 166198969346904628588090068991999678144665215687348812001800184535221844669584, 155603310051523924251834883863818145995666344044397520635322149227135400229162, 148872883548933756378489274197073983499719704261435615859986802495559010921006, 81750708149366870083009301272096885752897060661769218412989916737971915943976, 148678447667514938666217851109630684698494205266898323731021124876770785034450, 139091215705003885194651231164242939498323144911221815383977207111732590387794, 163048636015080103825098329819199941136682327741881112121639355982997152149776, 187106364152459245290064872482090544751002499525219947771026193325298171667344, 108976935503990364643794301632733346404623951921025042380886776919502332897472, 97957106863977801328795616898849379345417227158621516493092872609953154457006, 17753070743753606144300177896289193529616925569234502937982179327348579720220, 109141681218687755215391791999206602547374922884309822586452204011101983161640, 163673304221321167016506018368905578668595903262726360175142519822773166080294, 8983035357818474869572010606077694266241689631876083783135948049779786496832, 218590693600310061909741008149791751446183302180595255688271681626181231971786, 183132613813658121350904290515488388001103466975092999754040652867442486972592, 95586241377015502042695127228722330504767228863212992944406594321453188604510, 92765769598904848611768814669404279335194000407769545279099921380575938837374, 210909461340816816668931296404051780984288597651166091919877839156369357778724, 166222209522549277431127312559025559479345612852276374106590241573668934420876, 34022163829232114325153526417514511278907433280000600791287230381380359487150, 43216560238426228819284264146455998755081480811146626018001217144877328162830, 176817176636745294758850195733637712425664811745561449137602550877163399249968, 8954166457793279825389539602327278289337614243342849447786412999886336575524, 136722037185367506826140157262553112145743456552907792246237105164237991219764, 222034192586437845775591035067266452666371392051272210058519402276356351705990, 76908783820395858053232182645089909004948764645403652253150992348853018522562, 172587272125591859621940561581993897258375210637746506605804698205693381100364, 93234293704400573080180249687128229898761910709580350892036330187249891873598, 188799689880897732161660809551747828062199471266989039892439444269291961506548, 83332605068254138740673196209572741012260010733105545915384275202826621020968, 60610676862979083678107065605982320447902651882262953487700149151584511257580, 118741342330661748241378043358268310066863139609047530347921924627998808703562, 4403467090650870486483490854776066686987774881134028294749120767328207638062, 161860357451558475990080211293360384106216025250410519074271827672562189900648, 205190364867922907508273108385609657241642525828132090425442309347909257662442, 224737619892965364120795944328537948525763940197813301151587531670106216593964, 96933648004261730379520397215023410499025894907418637979605850044657801746374, 121724865174142242216578991564259342709491841099115482404139090878725924852566, 223317062063182448632142357656570243928534866576734401019398091860198561983172, 160333394977314803412318373721492426463988862389499100747650407594771166106940, 174319713050693692526267698733569938334242186233053085169656409568655285803952, 209657773682714512238712246616684247243095985691955532542212378233977870316748, 101215909402117582376958739067780322296963063231146921525786135476637090148718, 171275304621847294706061062264153629853546426276561901166690170825729995642814, 168671195531074416495701658498679681393499073353603668734944009154242216785816, 28834942816192041532616990710213956666201258092150421136796644470675006240824, 206737893208787737245980705440907835701359542947680420070609844441932120739898, 112124774136317944185492724137064314926308038700709515495761607768972970679358, 177950974816690344087188383665706688480284902889493553285756798116500998764190, 8330302691988817970098018311712256013829128815912115297559768883303072464592, 152467783891250677240829459341143479057072942271216425330871020038214625505828, 136331936353241610784214422645492531869623354035678358765316461009389636002540, 100759256475729499225918226559065103200906833800035852546737101254653740272790, 211341013630578383011051927286357563089773859141038663588089714309480862013056, 56914660884400145315913516543148657128285826485398149804728848731501569067154, 51896303455125315935769682499718656855645745938290661870615932155210204390310, 115066862941708620141470146313987582498640264671841847684601654747853537506394, 59113948508963856499799028607900145260892432559324684977603360999904361656460, 1990881513851906106322847266774160134085182595414969903469047509142072142384, 54887131817696814517233323585199589555188139187573099371417033550619611581234, 161357810001089140701996146134468679584723824558923361824193123751018791991140, 94621530242733574096174055659281382811604277464454073617443671162724382665128, 118944279468629093229869415090103526403275903420042469902420699235478902352602, 171159782311883815479238802314485916587871896496707427326184614514835675542800, 124499073142233268521571467144432918098640767238224720054121875947430855753814, 145043678310702237923849745286825835702830448409051564943632967725639355612778, 133811548742935594721658861480209621486603049181985706137472670623823251634618, 52496179714329684640970357988752569551968071437624294752005895706119159993336, 213183865432382531641155486364982015226667824006044288916075135252231491256932, 194984454234076241286871120431005090055510108332640203809239464854464613641694, 84107555988610101501900051736004949864792563086394585702588254663252102453740, 52018804800813859505257733317018916907401831159335717688684381244471514960864, 117472986077536676766540066835934140854349083920546545673804052487957063702614, 27388578124620740531854639339287630196450200655785290281651896705869439703532, 99773146063384217086908342823217890356453500343657421312515844133406645570264, 137444706237542745007964580290851824527405624492607219033910929540713638283160, 103965027914619372581143175756364192363851747544451127170224643831498110043136, 154860154224959429234398216032961104582058159979819617452778868685590732656616, 86031973725075126449707847121699189713660258633581353722733236211323758355714, 229569187579452586385084489786060477606277898660725775633049912933938732522072, 49766964383464165622314385505381795447919281141948537834814601127943037347740, 134568571237893088253606079428807966989459698631351737332902934137955404141312, 35340789381336863667546488845725974724572962982309790438630377557606088928954, 24429345084416934721085305853479872153153356192578880865555503217219991721758, 150097384553277280288737147437517804124059303752283065504576922949058747497376, 212507216572101833532632572916431153224823130460296206760645348597900304228516, 218302323186894088254230684322418659880200726545387471110017579072642032634108, 195102095385131255644235370514792465566724676207226839793789112736653121153386, 25173585893553954017764831091845513989197026894991294026612174311403537093256, 170277293707340262776363143908027030482687714083607445012629936146226967310566, 37033828375263353262429302518698731463111720801565601629914866263739313661430, 116842318720576470064497223091186484127724012867012667212886709239688802155298, 180961542702917845306416548235001038291203957380814151629343825925805821074586, 99366793555417235005981145564069870208335307668343266552074435406530233825566, 81622536331747355854325200606127089881245747268106984412931343696609889555774, 174314460949345999707023432854319031085318078787271551510869720087971536877726, 207835525766991513809650850063458480766240727679288597391400984208502336417378, 130786181387296145666689692524754046008205160781946635688883181653192151636668, 119829098315494600425757653070327771340525501812409511666980177904211932000872, 87310235449960718371407218933700596781608372776765319827304906260354083577886, 172090064388753665499745495342746572320117394589981848612582247640075395872202, 25368876791304322181931962837962199446448371365343154971112561641875695754654, 61278378258863294765669453795502975674601338170656954087639429559114291674210, 139448999052509326718803318195651841543199173951519507311068010517092149475478, 209977476028009520078370847547697471412639406922766600068381888615177208854848, 119097689959887551318035986062915380379788263525294491633657301865249989664616, 187573234732045545151773134531779330271044694472130120662600684264102501920002, 109435041171910904178321249407990824522282353355844612144553057086316125330796, 81871429224234036164001906979482185002540462857796514243973888624953165754368, 83896617767540189095622315114107915194726607542771999500655166355099438373200, 230133138550212858009694914729528578290658534243926060203878940816340947323812, 51638159207506851680907175131225830683390728915457374700450098784989329593726, 52079291857868770810533016725392567540878267190954335710982566244034998245238, 31120976054232618932601685028211330713744540033677586063424708958009621205682, 174688760570134054798704900064232319326692063255964507138701218881982505348492, 206782905589773145114526770426468178294642667184406541527358423425829161295342, 164004834534480203615549702930181023025667501218770871790479223051421106245950, 227686096426389875373266482944132497780157288948269635545229656110148545904866, 162633888407394181246446426104387320836153011970397982056280711390463746774310, 62412344886166250066838928149442061837141165818183155474224922698674159426876, 196332736579154840266682740495537608650752334676807728641838358274624276071484, 190235531625288268048762600170942815604532035456189572132390882132765051429186, 7324560614038963688853229513004502484898911659340360974218340709888461840018, 112792706618831529163938446622843993538531460030326649691115268707596807767552, 41523880801377875828094778641241878222197353203506251190995874416392055383506, 186998740132585869023585521836200251406035497423571459251025270381662035835650, 51087351330066196310068612416599473055604814182632261828945209521766400256092, 39882188205284529945936151101489260148922134298480652221333181212170019399322, 112013235100872880681298555897348462880115988355407192758399556843067120991858, 166157526302065485293676442977074414646904614953903068839117451632797288342598, 220873138670706477137982525017295852463424785608304735699798952756816154511642, 96201890909795882959637595537551513724436983315710478392978183995582384781252, 14151163675165526143025952163384095501006423033274633984930900434786163027978, 42858867401089480403492917826659572581728648700409974546352599368517621525406, 102488741490084188345373357292145614485097397689439112619838345592595805121418, 97321531489764656292363638690844052265884285206895042958360198034279539093928, 115409172100772301459377403625936511984901931809529927454031664181706061029686, 94371687613380738970851572012073766836995896307806079669650158810251022608854, 204193661998252173788143172991062388484845835038777284379379717801883872753714, 134261711033343221164752700117479290621219821662581788603246096556891044284020, 1758615104209533426043168814012216890706596422234035413651454114928241516142, 136291817824196235887723280305531554177318036787015770715920972049679378122688, 129500702679725826780387414802925964068826670058824722872498829407851390394604, 118837180359126995245540507392403348105472741893216046393275856795113865319532, 219768284215449712648939135609186883072494158475237898267768604679963277614702, 64189381202462862387955612908514196570275476740166864892665346730382084373814, 226501179896857829324355615439940490332580463698334044805215411978052426457570, 17575217931416628540874686072100926934856263078043289247714688189795680020, 95005900213436642541036165309726672503076070215655945155902148606015563714744, 8210374772139148727605208176147867817275422566372418056070688487499626246714, 99430289089400113902262839646227834996403020252290220444913308128536296693032, 136512343005613849207293711302840644848553901031082481339075849277691403575066, 78949564501249677446580244018734227738282348159386764104568598133372671578002, 132744857858108767600866848523589954682295959845216481680661562060566281681860, 112364019900883106152110397238792908591881657592168747469834225217783357662510, 227832488758370271900373405480727619209055338511588290120211434081657045152502, 14127662014725264547074008362507461766282787078001741397080986395131885651230, 152773503104256610618104932830375950818032236289819535279367868514569805760312, 29538334769275005195533406765017662469586823203549315572893298429558431671540, 9024615501294560299189477158152682539131263178918854468891157906502008253770, 105172454563065832395294317560583345525810505911888598783452338552162855806908, 135439489041474764542873016098373433344984594068864895756007681124763876397730, 106586091773035032378973797984527857463878855145673356060941160067938814199730, 106631767091864384870584075205033941156612930856838275283365567851270675438534, 107360691994528883197573776023927130974084232236676203687550855433932080635914, 185907729528753668786092519933200419731250597889993621461175842796082438778970, 228036571324559286732161499611501500990087289209203281258725997400661693959754, 95427217040199748220983414328190940966970345950862977961834433413704188977818, 25833623559001713525362383583891274787162086523779005617650326627296646898600, 195292434250269933978904562683549318223605020900531187149822008576788092957944, 99796799203461869828237894964274708795650422996484349850862680141803626551138, 99373689857601007615804921234142326376082348906177131211762139842948271863004, 19890340359247695451145532315550196955077931588869966529498144411389637563574, 124165891896179194472250292000172284010670743524036899102991035305195143879872, 33704327357304293314015992340719883572950460610460294462628657808151776804124, 180090950907500000911702191454568746986698268845830686848311717538852289954440, 142527615596053439968255837973634657059196376987579490266330949885050289099780, 134204251397547958256809693208233249171786891429831900530698434522517688369608, 29083563323197704755692997240471949551440116635406875882919559728352076923616, 46236605576138861541574198633513377632561906310983205448658920192938429973162, 181521965902711909923714114995199155278430235580170964048085811428642794028646, 34161457314234584626337836601313176084585884740536207396585098479484200753210, 183440795370017692985025829984008619693741253725363590872476394578612202054454, 219944840366784899573951287763962708072440572073547954855219536567821286912168, 30042967118930695286099841393193645935351101306228749482252779328060278170028, 216219488812546939177697792745668315195328111069468183798658140825268223777944, 109241285295292905117710572834188065354064780854415743680990104068395798560046, 100989357069559197467142359597521558889966359566809852068194665826733438563518, 139590705952805077465191730593621623799342647618624262518016664734021238245062, 92200058718912980064387638508972685988154993789794053643646982824503384280284, 98034319683133402750866863624297793495742834915358230014289910324419399633756, 44137549960774744667643566929834293380020844773917398690876442693745348435776, 18317760141145405355128736382314988497454087697937157737307292527688131744286, 85246896791991313048389535888044535561589871382206378194010979125524952119034, 134238664126894391209252037655707797082095100388058003569269560114104926316942, 141103175255484387177991652440546327675852821048298247098906677302615741153026, 206411828353926822233322505101569581290808710124979343274663334328204699465610, 139079210812270792616551837085339489409875060589180795038521046875556594160678, 159095448834076211585013333623237957745618481303241785881930596185888048128, 6713693295047053819130412285055262971359192730121563182199674982649124060362, 135547980296971914692532711969361209076720242961766186801415592338258073059014, 213610249479553204959338285648431162933461290039949597778177179861664850135198, 60482763154058430670599860891353647558593620173623418646215786072775206519962, 39894864290235587220530943163903022768167846002321871650411861543100646076158, 216969947980493768182962505585240129196518167563099273705951931375568787518596, 11828224649014773247941925821931099421723032316887062307356915464472608617010, 181966656134173614691824741232558066505041532448636525132539876266892602618712, 145171015242895636899268955733103156147249736487044315117117146275409143478336, 29346722574487379716303940345145151057357008630041362985766138820658202756138, 22577441305887582037213371498070923076265118052958339441151925277982759305818, 146300783502670809521691993497757449088190034196155722738519046252104984206412, 177242574658313827937508862298598198535427216819967902665186423453034167963100, 52596202892409259691095680918100898770810241148641034922117050898127069239358, 114171963706169496631899750520405951604545446241121389598414989441312574542612, 142214192764513870334864543375241372777680660413314377951643784458584315417096, 181462546551546705527768984464665089965720050251832121264382151562999477457486, 65523010769205154095472691398839928416632898878537957956293250128004099544138, 111703256109220744292374450804923423021428480256262405765479932170784220829012, 66120503671483001546465351710178833510140005872566179106518734070737968718194, 196881918880550085270780682129152570188063378959761911953203000379409500642054, 97868782312312034615276655042385958287283282335656306905282948585421006457900, 28106809025881239917718329184965056028080398682624824880167167294082666549654, 3730087978568419749657200649876066839896130120027155500156049041647053581644, 126468941171242920569892660107708715477179426944699621750411449577990626585290, 8457804124932822422112786137452775344591352456572873070862479706393068968868]
ans = dec(s[0],r)
print(ans)
cc = '0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 1 0 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0'.split(' ')
cc = [int(i) for i in cc]
flag = []
for i in range(256):
flag.append(cc[i]^ans[i])
m = ''
for i in flag:
m += str(i)
m = int(m,2)
print(long_to_bytes(m))
令$x=ai-j$，已知关系为$y=g^{g^xmodq}modp$，显然q是mod p的乘法阶。我们把x拆开以后，有$g^{g^{ai}} = g^{g^{x+j}}=g^{y^{j}} mod p$，进一步有$g^{ai}=y^{j}modq$
这里是已知指数范围在48比特，那么a取24比特，对i和j的遍历，在$2^{24}$以内即可。这也是个小细节，当指数范围随机（在模数以内）的时候，bsgs的时间复杂度为$\sqrt{p}$，当知道指数大致为e量级的时候，时间复杂度降低为$\sqrt{e}$.
题目远程要求30min，试了一下第一阶段计算幂需要17分钟左右(累乘优化一点)，时间卡的很死，那么考虑先计算完第一阶段再去nc远程拿y求解第二阶段。
from tqdm import tqdm
from gmpy2 import powmod
from pwn import *
q = 11769445852166501942131444325164359907623906505859865854871085543754710159882777389890225783970170353153967463136054852998337865848469266919651006863215539
p = 23538891704333003884262888650328719815247813011719731709742171087509420319765554779780451567940340706307934926272109705996675731696938533839302013726431079
g = 2
dic1 = {}
a = 2 ** 24
for i in tqdm(range(2**24)):
index = powmod(g,a*i,q)
dic1.update({powmod(g,index,p):i})
io = remote('manqiu.top',20142)
y = int(io.recvline())
print(y)
print(io.recvuntil(b'> '))
# print(io.sendline(b'1'))
# print(io.recvline())
x = 0
for j in tqdm(range(2**24)):
index = powmod(g,j,q)
tmp = powmod(y,index,p)
if tmp in dic1.keys():
x = (a*dic1[tmp] - j) % q
break
io.sendline(str(x).encode())
print(io.recvline())