暗号を解いてみよう！【アドベントカレンダー 5日目】

はじめに

こんにちは、18のHFです。アドベントカレンダー5日目です。一昨日から昨日にかけてSECCON 2018 Online CTFに参加していました。さて、CTFという競技ではCryptoという暗号解読をするジャンルがあります。今回は簡単な暗号について、それを解くのに便利なツールと共に紹介しようと思います。

シーザー暗号

非常にシンプルな暗号で、それぞれの文字を辞書順に決まった文字数だけずらすことで、元の文を分からなくします。古代ローマのガイウス・ユリウス・カエサルが使用したことからこの名前が付きました。例えばアルファベットならずらし方が26通りしか存在しないので、容易に解読できます。
例：Advent calendar $\Rightarrow$ Dgyhqw fdohqgdu（3文字ずらす）
多言語シーザー暗号(Universal Caesar cipher)で指定した文字数だけずらすことが出来ます。ちなみに、ずらすだけなので暗号化と復号が同じ方法で出来ます。

換字式暗号

ある文字をある文字へ一対一対応で変換する暗号です。ある程度長い文だと、頻度分析という手法を使うことにより解読することが出来ます。
例：picoCTF 2018 hertz

-------------------------------------------------------------------------------
tfgnbhrz cibi vz xfeb dkhn - zeazrvrervfg_tvlcibz_hbi_zfkphaki_pwkplpwtmb
-------------------------------------------------------------------------------
"mikk, lbvgti, zf nigfh hgu ketth hbi gfm sezr dhwvkx izrhriz fd rci
aefghlhbriz. aer v mhbg xfe, vd xfe ufgr rikk wi rchr rcvz wihgz mhb,
vd xfe zrvkk rbx rf uidigu rci vgdhwviz hgu cfbbfbz liblirbhriu ax rchr
hgrvtcbvzr-v bihkkx aikvipi ci vz hgrvtcbvzr-v mvkk chpi gfrcvgn
wfbi rf uf mvrc xfe hgu xfe hbi gf kfgnib wx dbvigu, gf kfgnib wx
'dhvrcdek zkhpi,' hz xfe thkk xfebzikd! aer cfm uf xfe uf? v zii v
chpi dbvncrigiu xfe-zvr ufmg hgu rikk wi hkk rci gimz."

vr mhz vg sekx, 1805, hgu rci zlihoib mhz rci mikk-ogfmg hggh lhpkfpgh
ztcibib, whvu fd cfgfb hgu dhpfbvri fd rci iwlbizz whbxh diufbfpgh.
mvrc rcizi mfbuz zci nbiiriu lbvgti phzvkv oebhnvg, h whg fd cvnc
bhgo hgu vwlfbrhgti, mcf mhz rci dvbzr rf hbbvpi hr cib bitilrvfg. hggh
lpkfpgh chu chu h tfenc dfb zfwi uhxz. zci mhz, hz zci zhvu, zeddibvgn
dbfw kh nbvlli; nbvlli aivgn rcig h gim mfbu vg zr. liribzaebn, eziu
fgkx ax rci ikvri.

hkk cib vgpvrhrvfgz mvrcfer iytilrvfg, mbvrrig vg dbigtc, hgu uikvpibiu
ax h zthbkir-kvpibviu dffrwhg rchr wfbgvgn, bhg hz dfkkfmz:

"vd xfe chpi gfrcvgn airrib rf uf, tfegr (fb lbvgti), hgu vd rci
lbfzlitr fd zliguvgn hg ipigvgn mvrc h lffb vgphkvu vz gfr rff ribbvaki,
v zchkk ai pibx tchbwiu rf zii xfe rfgvncr airmiig 7 hgu 10 hggirri
ztcibib."

"cihpigz! mchr h pvbekigr hrrhto!" bilkviu rci lbvgti, gfr vg rci
kihzr uvztfgtibriu ax rcvz bitilrvfg. ci chu sezr igribiu, mihbvgn hg
iwabfvuibiu tfebr egvdfbw, ogii abiitciz, hgu zcfiz, hgu chu zrhbz fg
cvz abihzr hgu h zibigi iylbizzvfg fg cvz dkhr dhti. ci zlfoi vg rchr
bidvgiu dbigtc vg mcvtc feb nbhgudhrcibz gfr fgkx zlfoi aer rcfencr, hgu
mvrc rci nigrki, lhrbfgvjvgn vgrfghrvfg ghrebhk rf h whg fd vwlfbrhgti
mcf chu nbfmg fku vg zftvirx hgu hr tfebr. ci migr el rf hggh lpkfpgh,
ovzziu cib chgu, lbizigrvgn rf cib cvz ahku, ztigriu, hgu zcvgvgn cihu,
hgu tfwlkhtigrkx zihriu cvwzikd fg rci zfdh.

"dvbzr fd hkk, uihb dbvigu, rikk wi cfm xfe hbi. zir xfeb dbvigu'z
wvgu hr bizr," zhvu ci mvrcfer hkribvgn cvz rfgi, aigihrc rci
lfkvrigizz hgu hdditriu zxwlhrcx fd mcvtc vguvddibigti hgu ipig vbfgx
tfeku ai uvztibgiu.

Substitution Solver - www.guballa.deに解かせると下のように復号できます。

-------------------------------------------------------------------------------
congrats here is your flag - substitution_ciphers_are_solvable_vmlvpvmcwr
-------------------------------------------------------------------------------
"well, prince, so genoa and lucca are now just family estates of the
buonapartes. but i warn you, if you dont tell me that this means war,
if you still try to defend the infamies and horrors perpetrated by that
antichrist-i really believe he is antichrist-i will have nothing
more to do with you and you are no longer my friend, no longer my
'faithful slave,' as you call yourself! but how do you do? i see i
have frightened you-sit down and tell me all the news."

it was in july, 1805, and the speaker was the well-known anna pavlovna
scherer, maid of honor and favorite of the empress marya fedorovna.
with these words she greeted prince vasili kuragin, a man of high
rank and importance, who was the first to arrive at her reception. anna
pvlovna had had a cough for some days. she was, as she said, suffering
from la grippe; grippe being then a new word in st. petersburg, used
only by the elite.

all her invitations without exception, written in french, and delivered
by a scarlet-liveried footman that morning, ran as follows:

"if you have nothing better to do, count (or prince), and if the
prospect of spending an evening with a poor invalid is not too terrible,
i shall be very charmed to see you tonight between 7 and 10 annette
scherer."

"heavens! what a virulent attack!" replied the prince, not in the
least disconcerted by this reception. he had just entered, wearing an
embroidered court uniform, knee breeches, and shoes, and had stars on
his breast and a serene expression on his flat face. he spoke in that
refined french in which our grandfathers not only spoke but thought, and
with the gentle, patronizing intonation natural to a man of importance
who had grown old in society and at court. he went up to anna pvlovna,
kissed her hand, presenting to her his bald, scented, and shining head,
and complacently seated himself on the sofa.

"first of all, dear friend, tell me how you are. set your friend's
mind at rest," said he without altering his tone, beneath the
politeness and affected sympathy of which indifference and even irony
could be discerned.

ヴィジュネル暗号

換字式暗号の一種で、ヴィジュネル方陣という表を使って暗号化します。上で紹介した暗号よりも複雑な方法で暗号化していて、解読が難しくなっています。しかし、長い文章ならば解読法が存在します。詳しくはwikipediaなどを読んでください。
例：picoCTF 2018 blaise's cipher

Yse lncsz bplr-izcarpnzjo dkxnroueius zf g uzlefwpnfmeznn cousex bls ltcmaqltki my Rjzn Hfetoxea Gqmexyt axtfnj 1467 fyd axpd g rptgq nivmpr jndc zt dwoynh hjewkjy cousex fwpnfmezx. Llhjcto'x dyyypm uswy ybttimpd gqahggpty fqtkw debjcar bzrjx, lnj xhizhsey bprk nydohltki my cwttosr tnj wezypr uk ehk hzrxjdpusoitl llvmlbky tn zmp cousexypxz. Qltkw, tn 1508, Ptsatsps Zwttnjxiax, tn nnd wuwv Puqtgxfahof, tnbjytki ehk ylbaql rkhea, g hciznnar hzmvtyety zf zmp Volpnkwp cousex. Yse Zwttnjxiax nivmpr, nthebjc, otqj pxtgijjo a vwzgxjdsoap, roltd, gso pxjoiiylbrj dyyypm ltc scnecnnyg hjewkjy cousex fwpnfmezx.

Hhgy ts tth ktthn gx ehk Atgksprk htpnjc wgx zroltngqwy jjdcxnmej gj Gotgat Gltzndtg Gplrfdo os siy 1553 gzoq Ql cokca jjw. Sol. Riualn Hfetoxea Hjwlgxz. Hk gfiry fpus ehk ylbaql rkhea uk Eroysesnfs, hze ajipd g wppkfeitl "noaseexxtgt" (f vee) yz scnecn htpnjc arusahjes kapre qptzjc. Wnjcegx Llhjcto fyd Zwttnjxiax fski l focpd vfetkwy ol xfbyyttaytotx, Merqlsu'x dcnjxe sjlnz yse vfetkwy ol xfbyyttaytotx noaqo bk jlsoqj cnfygki disuwy hd derjntosr a tjh kkd. Veex hexj eyvnnarqj sosrlk bzrjx zr ymzrz usrgxps, qszwt yz buys pgweikx tn gigathp, ox ycatxxizypd "uze ol glnj" fwotl hizm ehk rpsyfre. Hjwlgxz's sjehui ehax cewztrki dtxtyg yjnuxney ltc otqj tnj vee. Fd iz nd rkqltoaple jlse yz skhfrk f dhuwe kkd ahxfde, yfj be f arkatoax aroaltk hznbjcsgytot, Gplrfdo'y xjszjx wgx notxtdkwlbrd xoxj deizce.

Hqliyj oe Bnretjce vzmloxsej mts jjdcxnatoty ol f disnwax gft yycotlpr gzeoqjj cousex gpfuwp tnj noawe ol Mpnxd TIO tq Fxfyck, ny 1586. Lgypr, os ehk 19ys ckseuxd, ehk nyvkseius zf Hjwlgxz's inahkw hay rtsgyerogftki eo Bnretjce. Jfgij Plht ny hox moup Ehk Hzdkgcegppry qlmkseej yse sndazycihzeius my yfjitl ehgy siyyzre mld "olyoxjo tnnd isuzrzfyt itytxnmuznzn gso itxeegi yasjo a xjrrkxdibj lnj jwesjytgwj cousex kzr nnx [Volpnkwp] tntfgn mp hgi yozmtnm yz du bttn ne". pohzCZK{g1gt3w3_n1pn3wd_ax3s7_maj_1h7m92d3}

Zmp Volpnkwp cousex llitjo a xjauzfeius qox gpitl pxijatotyarqj szwznm. Sztki luzmzr gso mgysesfeiinln Imlrrjd Layhijlp Duirsus (Wecnd Cgwcorq) narqpd zmp Volpnkwp cousex zybxjlkggwe os siy 1868 uteij "Ehk Fwpnfmez Htpnjc" it f nhoqorks'd mgllzosp. It 1917, Xnikseilnn Asjciify dkxnrogpd zmp Volpnkwp cousex fd "isuzsynmlk tq txfysrfeius". Ehox cevzeaznzn cfd nuy oeyjcvki. Nhgwwey Glbhfre ox vnuby tu mlvk gcoqjy a bfcigse ol yse inahkw ls kfcle fd 1854; hubpvkw, se jnon'z ufbrndh nnd wuwv. Kgxtsqn pnzncerd mrupp tnj nivmpr gso pagwiympd zmp tkhsnovfe os ehk 19ys ckseuxd. Pvks meltce zmts, zmzumm, dosj dkoqwej hcyvylngqjszx noaqo oihlsotyarqj bxjlk zmp cousex ny tnj 16eh ijytawj.

Cxdatulcavmtc yqtdk wflk zdej fd a ifwcaqltoty aoi my zmp Scnds Gwxy hjewkjy 1914 ati 1940.
Ehk Atgksprk htpnjc iy xtmvqp ettfgn yz bk f qikqo cousex nq iz nd uyjo it hznpzycznzn cneh inahkw oiypd. Tnj Notkpdkwltk Xeazjd ol Fxexnna, ltc edfxprj, fski l bxfds inahkw oiyp eo oralkrpnz yse Bnretjce inahkw ouxnyg zmp Asjciify Coatl Cfc. Tnj Notkpdkwlce'x xeyxlgkx hexj qax kcos xpcxje ati ehk Zyius cemzwaxqj cxfnkki ehknc mkxdamjd. Tnwzummzuz yse cfc, tnj Notkpdkwltk qpajjcsnna pxnxaxnwy xjwiki fpus ehxjp kkd ahxfdey, "Rlnimpszjc Brzqf", "Itxprjee Bnntuwj" ati, ls zmp wgw nasj eo g hwoyj, "Nosj Cezwtbaytot".

Ltlhjct Bjcngr erojo tu wppgnc tnj mruppn inahkw (nrkfeitl ehk Aprtfx–Volpnkwp cousex ny 1918), bay, yo sfetkw hhgy se jno, tnj nivmpr cfd sznwl bzwnkwlbrj eo iwjpzfyarddiy. Aprtfx's ctck, nthebjc, ebjytafwle qpd zt ehk tye-znxe vfo, a zmpoxjeiifwle zybxjlkggwe inahkw.

Vigenere Solver - www.guballa.deに解かせるとこのように復号できます。

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 Vigenere cipher. The Trithemius cipher, however, only provided a progressive, rigid, and predictable system for switching between cipher alphabets.

What is now known as the Vigenere cipher was originally described by Giovan Battista Bellaso in his 1553 book La cifra del. Sig. Giovan Battista Bellaso. 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, say by a previous private conversation, Bellaso's system was considerably more secure.

Blaise de Vigenere published his description of a similar but stronger autokey cipher before the court of Henry III of France, in 1586. Later, in the 19th century, the invention of Bellaso's cipher was misattributed to Vigenere. 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 [Vigenere] though he had nothing to do with it". picoCTF{v1gn3r3_c1ph3rs_ar3n7_bad_1c7b92d3}

The Vigenere cipher gained a reputation for being exceptionally strong. Noted author and mathematician Charles Lutwidge Dodgson (Lewis Carroll) called the Vigenere cipher unbreakable in his 1868 piece "The Alphabet Cipher" in a children's magazine. In 1917, Scientific American described the Vigenere cipher as "impossible of translation". This reputation was not deserved. Charles Babbage is known to have broken a variant of the cipher as early as 1854; however, he didn't publish his work. Kasiski entirely broke the cipher and published the technique in the 19th century. Even before this, though, some skilled cryptanalysts could occasionally break the cipher in the 16th century.

Cryptographic slide rule used as a calculation aid by the Swiss Army between 1914 and 1940.
The Vigenere cipher is simple enough to be a field cipher if it is used in conjunction with cipher disks. The Confederate States of America, for example, used a brass cipher disk to implement the Vigenere cipher during the American Civil War. The Confederacy's messages were far from secret and the Union regularly cracked their 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".

Gilbert Vernam tried to repair the broken cipher (creating the Vernam–Vigenere 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.

おわりに

今回紹介したもの以外にも、多くの暗号がCTFでは登場します。ネット上で解読ツールを探したり、アルゴリズムを調べて自分で解読プログラムを書いたりします。ぜひ、暗号解読にチャレンジしてみてください。ここまで読んでいただきありがとうございました。

明日はmikitの記事です。お楽しみに！