2018网鼎杯 第四场 shanghai writeup

2018网鼎杯 myhloli 374次浏览 未收录 2个评论

因政治任务,公司要求强制参加本届网鼎杯ctf比赛,也是第一次参与,成绩不是很理想。

下面正文

0x01 题目原文

shanghai.txt

bju lcogx fisep vjf pyztj sdgh 13 gifc qsxw. pkiowxc
glv jqtio ekpy-hfgcouibkh qijgzkfoqur bj r twnovtvlnfvxqe sdxnie arw nqhhcregiu fg nujv hegxzwbc qgjkvgm rvwwdy 1467 ith hwvh i ouoir gvtyiz fynk zs fazxkj rzbcirr tmxjum irtuesibu. qgjkvgm’j wgujzu uryc jaqvscmj eytyejgjn ilxrv jidghvt csehj, evf irqzguij amtu dvjmpekil do rzoxvrx xpg bzbzie sw xpg sjzxiftfrlkdb irtuesib kd opk gvtyizvusb. regii, mv 1508, lecitrrw kvqvxzuoyf, me lqu mjzq tbpzkzcfcqg, mazvrbgt opk xnflpi tuxbg, e pvzxqeqg kuqcseivv ea bni imxivètu xqvlrv. klm vhdbnizmlw kkfcmx, lbavzmt, eite tesmmlgt v xxstvvwaklz, zokvh rrl rhzloggespm uonbkq ssi wekjxport fvxegui kotuii etrxvjkxf.[gzxivyjv tirhvh]

ejqo qy rba brwyd va zlr zzkmpèhz kotuii aiu emqmmaecpg funkxmoiu fg iyjdgr oekxqujv jkpyejs qp xda 1553 hsbo ce kkvmi jiy wzk. okeqit fnxkmavq wmrpnwf.[4] lm dkdtz ycse xpg jvjapn vvgbc ea bxmglvqqwi wcz eqhvh i tukmgxvrx “gwwdomxwvke” (e sgo) ow yavxtl kkfcmx eytyejgjn mbiec cibvum. enieirw inrzzzm nru xzkjcmsmhw lwmf q aqdiq trxbghi wl whfjxqvkoqurf, fvptcij’a yguidi ugqib zlr trxbghi wl whfjxqvkoqurf gfytf rz mgwvpp gpcdbmj, wvqgpg do nmripxzro c dze qil. ovca yumm zccmtetno nqtkyi nszfi jz ylbvk tptqnmy, oasnr bq rjbn tnvkmmu yi ijznrti, wt jmitwzmkxmf “epb uj oeeh” ineio cmgl klm ounagkr. fvptcij’a siglfh bjkn zkuhmiil ujmwtk fityzkjt nuv brcc bju fme. ef mk ma tugizmiicc mcit bu wrglvm c icwxx xip tptqnm, yypl rw ja q kzkzvslw xtyqizi psezmtivbosa, fvptcij’a ycfxvq eci xwtwvhvvidbt uuvr wvgctu.[xqzegmfr vguymj]

fyezwm fu qqmiaèvv tcdbdaniq lzw lgixzotgmfr wh q nqsmyei fcv iozurtii ecvefme gvtyiz duawxi glv gwwho wl lrric qky jn lvnrti, qp 1586.[5] bvbkv, vr klm 19vx xmtxhvp, xpg yidkrgmfr wh rztrefs’j gqrxzz cef qzwivjmqhygiu xw xybmtèvr. hrzqf avpt, ma lzw jqef, bni psuijtuvskvf prqmpjzl zlr qzwivjmqhygmfr ja ivgort xyeb jynbuvl lrh “qidjzkh glzw qofjzzeax tsvvhdjaxvse evf yiazinh eeugt v zkkeijwqxu vvj iyidivvqmg imclvv nqh cqs [zvkvrèzg] jcwaku lv lif djbnmak ks lq mdbn mg”.[6]

xyi dkwzvèxi pmglmt wvqtiq e iixwjvbosa jfv jgyio kbpigxqqdvtrc fxisvi. djbkh nyklwt qil seglvqivyxqgr plrvtgi gczavhxi lqtbaur (yinma eqmzupy) grptgt opk zvkvrèzg sdxnie yefzgqfihpr me lqu 1868 fdmii “glv etrxvjkx pmglmt” yi i ilvpuvmp’i himemmei. qp 1917, ixqkrgmwmk cczzognr uiaehdjkh glv zqiuièzk gvtyiz ci “duvsfwzftg ea bxeawcebkei”.[7][8] bneg vvtcvqoqur jej rwv tzakviiu. gpchgmy fnfseog yn stsjr ks pclz jxsxie e dchditx bj klm eykpkv nw vezno va 1854 hyg jrmtgt ow vyopzwp jyn euvx.[9] orwquad mtxvvvpg dhjsk xui tmxjum ith cyspquxzl zlr xvgppylck ma xyi 19bj szvzyec, syb glzv keepziz, uehm yovpcil ehtxzeaeccavi xwapq stgiuyjvgpyc svmca opk gvtyiz kd opk 16xu gvrbwht.[6]

kxccxfkzcfcqi wymui zwbz cyiq ej e kcbxcregmfr ikt wg zlr wnmau qmue frxnimp 1914 qil 1940.
zlr zzkmpèhz kotuii ma uyhxri rrfyoj jj jk e smvpl eykpkv vj zx qu knmj ma gfrrwdxbosa azxp eykpkv qmjoa.[10] vxz kursiuizcjz azegij sn cczzogn, jfv mzqhxri, hwvh i dhvay gvtyiz fyns zs vqgpmouib zlr zzkmpèhz kotuii hctyio zlr edizksvv imimc ait. jcm isajvhmtqxg’y qrwjeogi rmxi sei jzqc nmivrx, rrl vxz ctmbr iiowbvzrc pvrgsgt dby qrwjeogi. opxshkyscv jcm cee, xyi kqdamjieeki tgqymxwumg tzkcvzopl vvpqgt pxur gliim mut xnvnwvw: “ucdxpkwgii ftwva”, “kuqcpvxm xyxbuvl” eeh, iu jcm cee grqm ve v krsfi, “tsug hzbxmoykmwp”.[11]

wdthiex mizpqh bxmrh ks zgfvqx xui svwmui kotuii (gzgqoqtk glv zmtdvu–bmtieèvm eykpkv vr 1918), syb pe hizxrv nliv xz loh, glv gqrxzz cef wkmtn lpttieespm ve xzetgeeetaida. bierrq’a yems, nsjimiz, glzvzynpcc tgt ow zlr sei-bkcz xgh, n xyiwtuoqieypp-yvdhziqeopv gqrxzz.[12]

jifgimxvyjv

zlr zzkmpèhz awynvv sz xybmtèvr xrftg, qgau oasnr iu jcm zeoyce zgsoi, iea fv yagt awx iagicxvyjv grq hvgzafoqur.
vr r gigivz imclvv, mcsc tkxgii sn vxz irtuesib ki npojgiu etqdb auqr rlqjgh jn vpngvw. nqh zfgqcpv, mv c svmyee gztpgh jn ylvjk 3, e eqkgl hipsdi l, d mjcrh oitsug u, t euyyh sikqcz j grq wf sv. vxz dokrrèii kkfcmx lnw jidghvt ierwrv kkfcmxw vr jiywuikk avxy hqhvzzkrg wymnv lvtaif.

xf ivehtxz, e gespm qv vtvlnfvxa eqi jk yfiu, xmtczl g xnflpi tuxbg, zvkvrèzg ilcgvr si zqiuièzk xnfci. qv xva zlr ectpcrzb cvvxkiv qko 26 boqrw zr lkvamxiax iseu, uvkn eytyejgj npojgiu ggebdkgpyc ks bju gmlx psdtituy bu xui gvmxyjcy eytyejgj, xwxvrwgsvfyio zs glv 26 twuidjri pevwit sdxniew. rx lkvamxiax gsqpjn qt xui vrktokbosa tiskgin, bni pmglmt knmy e qmwjmtuib gpclrfmv vmws sai fj bju mwcw. glv etrxvjkx hwvh iv uvkn tbmex lgfzvjw br r vmruvbort ovceqhy.[koxnxzsv puzlkh]

ssi ifccktk, whtgsag jciz xui gpikdomdx gs si mpsmgvxrh zw

ivjvkqeghrav.
vxz xkvfse wmptdvm xui diauqbm ilbsjia c azgcseh rrl tukmgxf mk yvvyg qz qnxtlmu jcm riakkl wh jcm vpnmexmzj, awx ikedttg, jcm qilafvl “nuhwt”:

prqfrtgcjvri
retl zqm nbgvgw nmbj q fme prxkiz. vxz zkwg sw xpg hje nsyhj xpg bzbziew r xw b (yi anmsxvh wttzz). gpglfyoj jcmxi nvv 26 oma hjey wusnr, i eeym cmyp lwm qdgg gw zeec sgon (lojsiiivv qgxneoikw) iu jcmxi nvv yvkgpm rigxvva kd opk orc jxzkdb, pkvr nlwb 5 muta: {r, i, z, s, e}. jtcw, ‘{‘ vvj ‘zvkvrmtudabiecveaaxpp’ grq ‘}’ jfv awsxmywvzv pmvjzzy ss xyi uginimi, fytgmuiddk prxkizu ea bni xip wbtyio cmyp si bcazv grq irgp ounagkr pvxbgh zvimclvvmf rt cymak zxa eemzkwcsehqpw fme vba. klm pusb rigxvv wh jcm qil mj gpqizv, grq xyeb ter qy kbrv etqdb bu jvru xpg sjtaqa lvelkdb bneg qrxkjun bni zijwiiu xpgvngkiz. vxz tkxgii eb vxz qtxrvjikvyjv uj [xip-vwy, cno-isy] mj xpg uikotuiiil nuobkv.

ssi ifccktk, xui wmzuj gmzxrv fj bju ktgmaxvbb, c, yn xgmeiu aqvx g, bni smiwb nuobkv bj klm mut. bnieiwszg, hje r eah tstwci i uj glv zqiuièzk wdyrvm chz cyiq, rrqmno g. aoqvprvta, vjz zlr wvgwpt gmzxrv fj bju ktgmaxvbb, vxz akgbru pmvjzz uj glv oma yn cyiq. xyi tgjomx eg vfa m cdy kuphqe x qu n. opk vrwk sn vxz xrevrkifv yn mtgvtyizgt dv g wvqzpit vvanmbr:

gpikdomdx: nxkekmqolgaa
ovc: tgcjvrizsepm
eykpkvgiox: tzvjxbisvelz
fuxzetgmfr qu fzzlseqvh ja wjqtk gs klm ter qt xui kejnu xwxvrwgsvfyio zs glv oma, vdvjmak klm renqzmbr fj bju xqvlrvkifv bzbzie me xpcj mwc eah klmp knqtk glv gwnkhv’y pnfvp iu jcm vpnmexmzj. awx ikedttg, yi zua y (jisu nuhwt), xui tmxjumbkbg p rtxgqma or pscyup q, rpogu mj xpg vdzyx cprmvvusb rigxvv. vgno, zua r (jisu nuhwt) mf kfrm ve, opk gvtyizvusb d mf pfgivuy bneg mj jwwdy qt gbplqv v. jccy x vw klm uuxwth cprmvvusb rigxvv.

0x02 解题思路

题目shanghai,首先想到上海,然后看了内容之后,感觉还是互相伤shang害hai吧。

通览整篇文章,能够一眼看出来的是空格正常,单词长度正常。数字没有被加密,符号没有被加密。

初步感觉可能是凯撒加密。

从比较短的单词入手,1位的可能是i或者a,2位的可能是in或者is或者of,3位的可能是the或者and。

kxccxfkzcfcqi wymui zwbz cyiq ej e kcbxcregmfr ikt wg zlr wnmau qmue frxnimp 1914 qil 1940.

此句入手,因为1914和1940没有加密,经查询得知大概是一战和二战的年份,猜测句末为between 1914 and 1940.

因frxnimp和between中,后者出现了3个e,前者对应位置分别是r,i,m,所以判断加密方式不是简单的凯撒加密,无法通过词频方式简易破解。

去百度百科看了下凯撒密码,其中提到了凯撒密码的进阶 维吉尼亚密码

手滑点进去之后,发现正是我想要的。

ps:虽然赛后才知道维吉尼亚密码是ctf常考的内容,但是不得不说运气也是实力的一种体现形式。

维吉尼亚密码的百科介绍里,看到了关键的几个年份:1467 1508 1553 1586 1868 1917 1918

和题目密文中的未加密年份刚刚好可以对上,所以我有理由相信这篇密文的原文就是百科维吉尼亚密码的英文版本。

通常,解密维吉尼亚密码首先要确定密钥的长度。

计算密钥长度的原理基于 卡西斯基试验

orwquad mtxvvvpg dhjsk xui tmxjum ith cyspquxzl zlr xvgppylck ma xyi 19bj szvzyec, syb glzv keepziz, uehm yovpcil ehtxzeaeccavi xwapq stgiuyjvgpyc svmca opk gvtyiz kd opk 16xu gvrbwht.[6]

切入点为上面这句,句末可以看到重复的两个opk

opk gvtyiz kd opk

第一个opk末尾的距离到第二个opk末尾的距离为11,且11为素数,根据卡西斯基试验可知,密钥为11的约数,而11的约数仅有1和11,即密钥长度为11位。

因后部opk 16xu gvrbwht. 其中16和xu连接,英文中这种写法很大概率是16th,词组为the 16th century.

同理上半句xyi 19bj szvzyec,也可以认为是the 19th century。

即根据此两段推得密钥

sec: opk 16xu gvrbwht.

key: vig     en  ereicqv

orig:the  16th century

sec:  xyi   19bj  szvzyec

key: ere       ic  qvigene

orig:the  19th  century

因为维吉尼亚加密的密钥实际上是凯撒密钥的循环,可得出密钥为vigenereicq或icqvigenere

这个密钥长度正好与我们先前推算出来的长度11相符

其中vigenere即为维吉尼亚的英文拼写

把原文拷入在线解密网站(http://www.zjslove.com/3.decode/weijiniya/index.html),输入密钥icqvigenere

可解出原文:

the quick brown fox jumps over 13 lazy dogs. history
the first well-documented description of a polyalphabetic cipher was formulated by leon battista alberti around 1467 and used a metal cipher disc to switch between cipher alphabets. alberti’s system only switched alphabets after several words, and switches were indicated by writing the letter of the corresponding alphabet in the ciphertext. later, in 1508, johannes trithemius, in his work poligraphia, invented the tabula recta, a critical component of the vigenère cipher. the trithemius cipher, however, only provided a progressive, rigid and predictable system for switching between cipher alphabets.[citation needed]

what is now known as the vigenère cipher was originally described by giovan battista bellaso in his 1553 book la cifra del sig. giovan battista bellaso.[4] he built upon the tabula recta of trithemius but added a repeating “countersign” (a key) to switch cipher alphabets every letter. whereas alberti and trithemius used a fixed pattern of substitutions, bellaso’s scheme meant the pattern of substitutions could be easily changed, simply by selecting a new key. keys were typically single words or short phrases, known to both parties in advance, or transmitted “out of band” along with the message. bellaso’s method thus required strong security for only the key. as it is relatively easy to secure a short key phrase, such as by a previous private conversation, bellaso’s system was considerably more secure.[citation needed]

blaise de vigenère published his description of a similar but stronger autokey cipher before the court of henry iii of france, in 1586.[5] later, in the 19th century, the invention of bellaso’s cipher was misattributed to vigenère. david kahn, in his book, the codebreakers lamented the misattribution by saying that history had “ignored this important contribution and instead named a regressive and elementary cipher for him [vigenère] though he had nothing to do with it”.[6]

the vigenère cipher gained a reputation for being exceptionally strong. noted author and mathematician charles lutwidge dodgson (lewis carroll) called the vigenère cipher unbreakable in his 1868 piece “the alphabet cipher” in a children’s magazine. in 1917, scientific american described the vigenère cipher as “impossible of translation”.[7][8] that reputation was not deserved. charles babbage is known to have broken a variant of the cipher as early as 1854 but failed to publish his work.[9] kasiski entirely broke the cipher and published the technique in the 19th century, but even earlier, some skilled cryptanalysts could occasionally break the cipher in the 16th century.[6]

cryptographic slide rule used as a calculation aid by the swiss army between 1914 and 1940.
the vigenère cipher is simple enough to be a field cipher if it is used in conjunction with cipher disks.[10] the confederate states of america, for example, used a brass cipher disk to implement the vigenère cipher during the american civil war. the confederacy’s messages were far from secret, and the union regularly cracked its messages. throughout the war, the confederate leadership primarily relied upon three key phrases: “manchester bluff”, “complete victory” and, as the war came to a close, “come retribution”.[11]

gilbert vernam tried to repair the broken cipher (creating the vernam–vigenère cipher in 1918), but no matter what he did, the cipher was still vulnerable to cryptanalysis. vernam’s work, however, eventually led to the one-time pad, a theoretically-unbreakable cipher.[12]

description

the vigenère square or vigenère table, also known as the tabula recta, can be used for encryption and decryption.
in a caesar cipher, each letter of the alphabet is shifted along some number of places. for example, in a caesar cipher of shift 3, a would become d, b would become e, y would become b and so on. the vigenère cipher has several caesar ciphers in sequence with different shift values.

to encrypt, a table of alphabets can be used, termed a tabula recta, vigenère square or vigenère table. it has the alphabet written out 26 times in different rows, each alphabet shifted cyclically to the left compared to the previous alphabet, corresponding to the 26 possible caesar ciphers. at different points in the encryption process, the cipher uses a different alphabet from one of the rows. the alphabet used at each point depends on a repeating keyword.[citation needed]

for example, suppose that the plaintext to be encrypted is

attackatdawn.
the person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword “lemon”:

lemonlemonle
each row starts with a key letter. the rest of the row holds the letters a to z (in shifted order). although there are 26 key rows shown, a code will use only as many keys (different alphabets) as there are unique letters in the key string, here just 5 keys: {l, e, m, o, n}. flag, ‘{‘ and ‘vigenereisveryeasyhuh’ and ‘}’ for successive letters of the message, successive letters of the key string will be taken and each message letter enciphered by using its corresponding key row. the next letter of the key is chosen, and that row is gone along to find the column heading that matches the message character. the letter at the intersection of [key-row, msg-col] is the enciphered letter.

for example, the first letter of the plaintext, a, is paired with l, the first letter of the key. therefore, row l and column a of the vigenère square are used, namely l. similarly, for the second letter of the plaintext, the second letter of the key is used. the letter at row e and column t is x. the rest of the plaintext is enciphered in a similar fashion:

plaintext: attackatdawn
key: lemonlemonle
ciphertext: lxfopvefrnhr
decryption is performed by going to the row in the table corresponding to the key, finding the position of the ciphertext letter in that row and then using the column’s label as the plaintext. for example, in row l (from lemon), the ciphertext l appears in column a, which is the first plaintext letter. next, row e (from lemon) is gone to, the ciphertext x is located that is found in column t. thus t is the second plaintext letter.

其中flag为

flag {vigenereisveryeasyhuh}

0x03 补充

解密维吉尼亚加密通常根据大于等于3个字母的相同密文,推算出密钥的长度

然后根据密钥长度切片,用相似的片段和短单词通常是a,is,in,of,and,the这些高频短词推算出部分密钥,再结合上下文推算出完整密钥。

因此篇原文较长,且内容包含未加密数字,为解密分析带来了一定的便利,越长的文章越容易解密。

本例中使用了在线加解密网站节约解密时间。具体解密代码算法可以参考百度。

ps:直接打开英文wiki的维吉尼亚密码词条

https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher

即为原文

做题的时候没有在英文wiki上搜到,写这篇文章的时候去搜又搜到了。囧

pss:受年份误导,搜索1868 1917关键词时,搜索到一位黑人音乐家

Scott Joplin(1868-1917)

https://en.wikipedia.org/wiki/Scott_Joplin

为此我还研究了半天的19世纪美洲音乐。。

  萝莉社,版权所有丨如未注明,均为原创丨本网站采用BY-NC-SA协议进行授权,转载请注明转自:https://myhloli.com/2018%e7%bd%91%e9%bc%8e%e6%9d%af-%e7%ac%ac%e5%9b%9b%e5%9c%ba-shanghai-writeup.html
喜欢 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(2)个小伙伴在吐槽
  1. 更新了居然 :shock:
    Sulfen2018-09-01 10:24 回复
加载中……