Vigenere暗号をKasiski Testで解読する

はじめに

前回の古典暗号の勉強の続きです.
Vigenere暗号を解読するための,頻度分析のうちの1つであるKasiski Testを手作業+Pythonで実際に行ってみます.
szarny.hatenablog.com

Vigenere暗号の復習

これは前回と同じですが一応再掲.

ヴィジュネル暗号(Vigenere Cipher)は,二次元のヴィジュネル方陣を用いて暗号文を生成するアルゴリズムです.

下記のヴィジュネル方陣における垂直方向を平文の1文字,水平方向を鍵の1文字と照らし合わせて,2つのラインが重なる部分の文字を暗号文として用います.

平文の長さより鍵の長さの方が短い時は,鍵を循環させる形で利用します.

例えば,平文i,鍵Dの時,暗号文はLになります.
f:id:Szarny:20180104174327p:plain

# ヴィジュネル方陣生成アルゴリズム
def TableGen():
    table = []
    
    text = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    for i in range(26):
        table.append(text)
        text = text[1:] + text[0]
        
    return table

# 鍵生成アルゴリズム
def KeyGen():
    key = input("Key : ")
    return key

# 暗号化アルゴリズム
def Enc(plain, key, table):
    cipher = ""
    text_l = "abcdefghijklmnopqrstuvwxyz"
    text_u = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    for i,p in enumerate(plain):
        cipher += table[text_u.index(key[i % len(key)])][text_l.index(p)]
        
    return cipher

# 復号アルゴリズム
def Dec(cipher, key, table):
    plain = ""
    text_l = "abcdefghijklmnopqrstuvwxyz"
    text_u = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    for i,c in enumerate(cipher):
        plain += text_l[table[text_u.index(key[i % len(key)])].index(c)]
    
    return plain
        
def main():
    print("[Usage] Enc: [a-z]->[A-Z]\tDec: [A-Z]->[a-z]")
    while True:
        mode = input("[E]nc [D]ec e[X]it : ")
        
        if mode == "X":
            return
        
        msg = input("Message : ")

        if mode == "E":
            print(Enc(msg, KeyGen(), TableGen()))
        elif mode == "D":
            print(Dec(msg, KeyGen(), TableGen()))
        
        print()
    
main()
[Usage] Enc: [a-z]->[A-Z]	Dec: [A-Z]->[a-z]
[E]nc [D]ec e[X]it : E
Message : helloworld
Key : SZARNY
ZDLCBUGQLU

[E]nc [D]ec e[X]it : D
Message : ZDLCBUGQLU
Key : SZARNY
helloworld

Kasiski Test

ヴィジュネル暗号は、単純な頻度分析では解読できないが、同一文字列の出現周期から鍵周期を特定することによって、頻度分析を適用できる(単純なシフト暗号に帰着できる)ことが指摘された。多表式換字では、同一の文字列("the" のような文字の並び)に対応する暗号文は、鍵の長さ分だけのバリエーションがあり、かつ鍵周期に従って選択されるため、暗号文中に同一の並びが出現する間隔は(偶然に一致する場合を除くと)鍵周期の公倍数になる。鍵周期の公倍数となる値を複数個集めて最大公約数を求めると鍵周期を得ることができる。

頻度分析 (暗号) - Wikipedia

つまり,こうです.

  1. 暗号文において複数回出現する部分文字列を見つける
  2. その部分文字列の間隔を調べる
  3. 間隔の約数を基に鍵の長さを推測する

以上の方法によって鍵の長さを割り出すことができれば,あとはブルートフォースで解くことができます.
必要な試行回数を見ても,6~7文字程度であれば短時間で解くことができます.
(鍵長が長そうなときは,別の方法を考慮する必要がありそう)

計算式 文字長 必要な試行回数
26^ 1 1 26
26^ 2 2 676
26^ 3 3 17576
26^ 4 4 456976
26^ 5 5 11881376
26^ 6 6 308915776
26^ 7 7 8031810176
26^ 8 8 208827064576
26^ 9 9 5429503678976
26^10 10 141167095653376

実例を通してみていきます.
以下はヴィジュネル暗号によって暗号化された暗号文です.(見やすさのために改行してあります)
現時点での情報はこれだけで,鍵の情報(長さ,内容)は一切ありません

AICRFYATOALKNHHUOQFUJEUQRUQITGOOGDBAFPTBFKNHUOTNOXFOZQUFXESIEUCNZYHFTEIGATMEEY
IUJANQCLKNHNAVIHZGSSGPMKEEVHFVOSVOJUEBPDJIEUVHFTETQOOGRUJAOAOVV
HJPKJNLSWNZQUBTADGAOFPSQVFKTUJEICRFYATOUDJANWSFFAUVHFKDFCOGTUOPIOIASCCFY
IUJTIGTPTTPKSFDUUHOSVHFHUOQFUJEUJIOIHFCGSGEEUOUJEGQXXJOICDDQNTGNUGDUQADVA
TLUEIENCRLGDUJEEKSUCNDGAOFSUCRUGDUJESWNOGRTQFGVHFJASGWBUSPQNGCRPWTPHSJI
HUCNEVONCKFVHFVOSVOJUEGGEMXESADFGPMAHPYRJFIDWLPWSJVWBUFPTHJOTPVRZCRBEEX
KTICHBTEIGLBADPYNCGSJFEUJEDQUSUEUQTBMEBPAQWNUKLUJEUQRUQITGSIQUMFCBVCIWPUJEUQRUQI
TGMFCNXJIMGKFRTHQIOISMQWMABVVSUGAEKLZCNECFUGRBVINGPBUSFFTIGPMCCFYHFTEUJEICRFYATU
LFGPJPGCWTUJEICRFULFRTPPVFTYQGADGFVNLZCNEYHFPAUNATVHFFIEYALGUQVHFV
OSVOJUEXCSOGASVHFIOBNTIGHBTEOQWSCNIKSTYIGVETVBVVHFEOVNDOQTPXESVAL
GTIGTPTTPKSFKNUKMFVHFTADGITPOUCLXCYTVOUJETYIGV

暗号文をよく見ると,VHFという文字列が頻繁に表れていることが見て取れます.

これらの間隔をチェックすると15, 66, 39, 96, 33, 267, 9, 15, 30, 33となっています.
これらの数の公約数は明らかに3であるといえます,

よって,鍵の長さが3である可能性が非常に高いといえます.

早速,鍵の長さを3にしてブルートフォースアタックを行ってみます.
行うことは単純で,

  • 任意の3文字([A-Z][A-Z][A-Z])の鍵をDec関数に与え
  • the you of という頻出英単語が平文(かもしれないもの)に含まれていれば出力

だけです.

上記のプログラムに以下の関数を追記し,実行します.

def Attack(cipher):
    alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    
    for letter_1 in alphabet_upper:
        for letter_2 in alphabet_upper:
            for letter_3 in alphabet_upper:
                tmp_key = letter_1 + letter_2 + letter_3
                tmp_plain = Dec(cipher, tmp_key, TableGen())
                
                if ("the" in tmp_plain) and ("you" in tmp_plain) and ("of" in tmp_plain):
                    print("Key might be {}".format(tmp_key))
                    print("Plaintext might be {}".format(tmp_plain[:100] + "..."))
                    print()

cipher = "AICRFYATOALKNHHUOQFUJEUQRUQITGOOGDBAFPTBFKNHUOTNOXFOZQUFXESIEUCNZYHFTEIGATMEEYIUJANQCLKNHNAVIHZGSSGPMKEEVHFVOSVOJUEBPDJIEUVHFTETQOOGRUJAOAOVVHJPKJNLSWNZQUBTADGAOFPSQVFKTUJEICRFYATOUDJANWSFFAUVHFKDFCOGTUOPIOIASCCFYIUJTIGTPTTPKSFDUUHOSVHFHUOQFUJEUJIOIHFCGSGEEUOUJEGQXXJOICDDQNTGNUGDUQADVATLUEIENCRLGDUJEEKSUCNDGAOFSUCRUGDUJESWNOGRTQFGVHFJASGWBUSPQNGCRPWTPHSJIHUCNEVONCKFVHFVOSVOJUEGGEMXESADFGPMAHPYRJFIDWLPWSJVWBUFPTHJOTPVRZCRBEEXKTICHBTEIGLBADPYNCGSJFEUJEDQUSUEUQTBMEBPAQWNUKLUJEUQRUQITGSIQUMFCBVCIWPUJEUQRUQITGMFCNXJIMGKFRTHQIOISMQWMABVVSUGAEKLZCNECFUGRBVINGPBUSFFTIGPMCCFYHFTEUJEICRFYATULFGPJPGCWTUJEICRFULFRTPPVFTYQGADGFVNLZCNEYHFPAUNATVHFFIEYALGUQVHFVOSVOJUEXCSOGASVHFIOBNTIGHBTEOQWSCNIKSTYIGVETVBVVHFEOVNDOQTPXESVALGTIGTPTTPKSFKNUKMFVHFTADGITPOUCLXCYTVOUJETYIGV"
Attack(cipher)

結果は以下のようになりました.

Key might be ABC
Plaintext might be aharewasmakingfunofthetortoiseonedayforbeingsoslowdoyouevergetanywhereheaskedwithamockinglaughyesrep...

Key might be AFC
Plaintext might be adarawaomagincfujofpheporpoioeojedwyfkrbaincsoolosdououavengepanuwharedeaokezwiphaiocginclaqghuesnep...

Key might be AIF
Plaintext might be aaxrxtaljadfnzcuglfmeemlrmlilbogbdtvfhobxfnzpoliopaorluxsekdemxnrthxoeabalhewtimeaflcdfnziandhrbskbp...

Key might be AUI
Plaintext might be aourlqazgarcnnzuuifabeairaiizyouydhsfvlblcnnmozfodxofiulpeyaeaunfqhlleoyazeekqiabaticrcnnfabahfysyyp...

Key might be IOR
Plaintext might be suljrhsfxsxtftqmazxgswgzjgzafpgapvnjxbctrtftdgfwgjoglzmrgwerwglflhzrcwupsfvwqhagsszzuxtftwshrzlpkeph...

Key might be NKO
Plaintext might be nyoevknjanbwaxthecskvrkcekcvjsbesqrmsffovwaxgbjzbnrbpchvjriurkoapkuvfrysnjyrukvkvndcpbwaxznluupsfisc...

Key might be PJP
Plaintext might be lzncwjlkzlcvyysffbqluplbclbtkrzfroslqgemwvyyfzkyzoqzqbfwipjtplnyqjswepzrlkxpvjtlulebncvyyylmtsqrdjra...

Key might be QSZ
Plaintext might be kqdbnzkbpktlxpiewrpckocrbcrsbhywhnjbpxulnlxpvyboyfgyhrenyoajocdxhzrnuoqhkbnomzsckkvrmtlxpokdjrhhcahz...

明らかに,鍵がABCの時に,英語らしき文章が見えます.
鍵をABCに設定し,解読を行った結果を以下に示します.

[E]nc [D]ec e[X]it : D
Message : AICRFYATOALKNHHUOQFUJEUQRUQITGOOGDBAFPTBFKNHUOTNOXFOZQUFXESIEUCNZYHFTEIGATMEEYIUJANQCLKNHNAVIHZGSSGPMKEEVHFVOSVOJUEBPDJIEUVHFTETQOOGRUJAOAOVVHJPKJNLSWNZQUBTADGAOFPSQVFKTUJEICRFYATOUDJANWSFFAUVHFKDFCOGTUOPIOIASCCFYIUJTIGTPTTPKSFDUUHOSVHFHUOQFUJEUJIOIHFCGSGEEUOUJEGQXXJOICDDQNTGNUGDUQADVATLUEIENCRLGDUJEEKSUCNDGAOFSUCRUGDUJESWNOGRTQFGVHFJASGWBUSPQNGCRPWTPHSJIHUCNEVONCKFVHFVOSVOJUEGGEMXESADFGPMAHPYRJFIDWLPWSJVWBUFPTHJOTPVRZCRBEEXKTICHBTEIGLBADPYNCGSJFEUJEDQUSUEUQTBMEBPAQWNUKLUJEUQRUQITGSIQUMFCBVCIWPUJEUQRUQITGMFCNXJIMGKFRTHQIOISMQWMABVVSUGAEKLZCNECFUGRBVINGPBUSFFTIGPMCCFYHFTEUJEICRFYATULFGPJPGCWTUJEICRFULFRTPPVFTYQGADGFVNLZCNEYHFPAUNATVHFFIEYALGUQVHFVOSVOJUEXCSOGASVHFIOBNTIGHBTEOQWSCNIKSTYIGVETVBVVHFEOVNDOQTPXESVALGTIGTPTTPKSFKNUKMFVHFTADGITPOUCLXCYTVOUJETYIGV
Key : ABC
aharewasmakingfunofthetortoiseonedayforbeingsoslowdoyouevergetanywhereheaskedwithamockinglaughyesrepliedthetortoiseandigettheresoonerthanyouthinkillrunyouaraceandproveittheharewasmuchamusedattheideaofrunningaracewiththetortoisebutforthefunofthethingheagreedsothefoxwhohadconsentedtoactasjudgemarkedthedistanceandstartedtherunnersofftheharewassoonfaroutofsightandtomakethetortoisefeelverydeeplyhowridiculousitwasforhimtotryaracewithaharehelaydownbesidethecoursetotakeanapuntilthetortoiseshouldcatchupthetortoisemeanwhilekeptgoingslowlybutsteadilyandafteratimepassedtheplacewheretheharewassleepingbuttheharesleptonverypeacefullyandwhenatlasthedidwakeupthetortoisewasnearthegoaltheharenowranhisswiftestbuthecouldnotovertakethetortoiseintimetheraceisnotalwaystotheswift

適当に空白を入れます.

a hare was making fun of the tortoise one day for being so slowdo you ever get anywhere he asked
with a mocking laughyes replied the tortoise and i get there sooner than you think ill run you a race
and prove itthe hare was much amused at the idea of running a race with the tortoise but for the fun
of the thing he agreed so the fox who had consented to act as judge marked the distance and started
the runners offthe hare was soon far out of sight and to make the tortoise feel very deeply how ridiculous
it was for him to try a race with a hare he lay down beside the course to take a nap until the tortoise should
catch upthe tortoise meanwhile kept going slowly but steadily and after a time passed the place where the
hare was sleeping but the hare slept on very peacefully and when at last he did wake up the tortoise was
near the goal the hare now ran his swiftest but he could not overtake the tortoise in timethe race is not always to the swift

平文を導けました!
ちなみに,ウサギとカメです.

おわりに

Kasiski TestによるVigenere暗号の鍵のサイズ推測と解読を行いました.
実際に手を動かしながらやると分かりやすいですね~

参考文献

暗号技術の全て IPUSIRON