CTF歡樂賽-密碼學-哈希哈希題解

1、下載源文件后拿到一個數組和一個salt=131,因為給的是一個數組,我們可以猜測這個是hash字符串的前綴和

hash1[34]={1,137,17961,2352894,308229132,40378016292,5289520134276,692927137590175,90773455024312932,11891322608184994096,8236759480631890849,9104335687623707495,12076354361294378429,14029175064251686857,11594270119725368294,6216371639840014010,2687945575821564212,1632733032143431075,10973842399984403068,17174060722321327476,17745921705238153833,425990098794648510,464470720970299981,5505432225980642670,1788602728791676750,12946028587195034875,17276034214980371573,12657705169863378919,16399154691952544583,8466952095475352928,2366080084698136616,14808585916103070846,3016627269999361153,7796546822015727126};salt=131

題目提示是hash題,這個數組的首個是為1,salt給出的又是hash常見的131素數。

我們日常最常見的字符串hash求前綴和的操作是

p即可視為我們的salt,mod數一般是極大的素數或者使用unsigned long long 的自動溢出法

根據上述的hash[i]的求法,我們可以根據前綴和逆推求出每一位的原字符串

即當我們要求0<=l<=r<=n 的l-r上的hash值時有如下公式

當l==r的時候即可求出單個字符的hash值即原值

通過腳本可得出原數組,數組值在0-25之間,即代表a-z,得出原字符串為

godsaythereislightandthereislight

將此字符串輸入壓縮文件密碼中,解開壓縮文件,發現一個網址與一個圖

https://www.cnblogs.com/post/ReadAuth?blogId=463042&PostId=12524932&url=%2FNever-Land%2Fprotected%2Fp%2F12524932.html

其實這個是古埃及文,對應古埃及字母表可翻譯出原文

magichash

得到后進入網頁中

L.OeOeKhItNhTtHiYwGsLeAiSdSe,gaanmditeenlilhtthdenfaa,ceeltghnoiusveiieDw,eesbtoNtotwoinsdtehre'tbimmeemtehraetvfialcueoshhtofuiltdufBo.remmaintontehdelro,gWyhhotsseifhrte,ssherlekpnaiirrwiffoneotwitphsoeuDr,eeneeswtelsath,sTehgoauednoishttbfeogsuwioldentihwehwgourolrdh,tuunobhlteosSs;seommiermportehhefro.lFiorrpwAhyelreevioslsehhetskocfaabisrlwlhaoCseeeuhntenaireehdswdonmab,Dsissadlagisn'srtehhettoimlylhatgteroafutohhyTh?uystbiarnedtrsyo?pOprowthsooits,heevsoolf-ofnldewsislilhbfeOt,h}erteokmcbafhl_adga{b

觀察文章的開頭0 2 4 6 8 10等字符,是LOOK IN THY GLASS , and tell the face thou viewest.

這句話其實是莎士比亞的十四行詩中某一首的開頭。

再倒序觀察1 3 5 7 9等奇數字符,是Die single, and thine image dies with thee. 的倒序。

(標題——頭尾相接!!!)

觀察出亂序的規律之后我們即可寫腳本還原這首詩

LOOK in thy glass, and tell the face thou viewestNow is the time that face should form another,Whose fresh repair if now thou renewest,Thou dost beguile the world, unbless some mother.For where is she so fair whose uneared wombDisdains the tillage of thy husbandry?Or who is he so fond will be the tombflag{bad_hacker},Of his self-love, to stop posterity?Thou art thy mother's glass, and she in theeCalls back the lovely April of her prime;So thou through windows of thine age shalt see,Despite of wrinkles, this thy golden time.But if thou live rememb'red not to be,Die single, and thine image dies with thee.

即可拿到flag

考點:前綴和,hash字符串