暗号理論の勉強メモ(古典暗号編)

はじめに

暗号理論の講義を控えている + CTFのCrypt問で点を稼げるようになりたいので,暗号理論の勉強をぼちぼちやっていこうと思います.

基本的にはアルゴリズムを確認した後に,Pythonで実装するという方式で進んでいきます.

参考文献はこちら
www.shoeisha.co.jp
www.hyuki.com

最初は古典暗号から...

シーザー暗号

アルゴリズム

シーザー暗号(Caesar Cipher)は,アルファベットを3文字シフトさせることで暗号文を生成するアルゴリズムです.
f:id:Szarny:20180104170913p:plain

攻撃方法

3文字ずらすだけで解読できてしまうので,攻撃方法はありません.

Pythonによる実装

シフト処理は,文字をord()を用いて整数にした後,chr()を用いて再度文字に戻すことによって実現します.

# 鍵生成アルゴリズム
def KeyGen():
    n = 3
    return 3

# 暗号化アルゴリズム
def Enc(plain, key):
    cipher = ""
    
    for p in plain:
        offset = (-32) - key
        p_sign = ord(p)
        c_sign = p_sign + offset
        
        if c_sign < 65:
            c_sign += 26
        
        c = chr(c_sign)
        cipher += c
    
    return cipher

# 復号アルゴリズム
def Dec(cipher, key):
    plain = ""
    
    for c in cipher:
        offset = 32 + key
        c_sign = ord(c)
        p_sign = c_sign + offset
        
        if p_sign > 122:
            p_sign -= 26
        
        p = chr(p_sign)
        plain += p
    
    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()))
        elif mode == "D":
            print(Dec(msg, KeyGen()))
        
        print()
    
main()
[Usage] Enc: [a-z]->[A-Z]	Dec: [A-Z]->[a-z]
[E]nc [D]ec e[X]it : E
Message : helloworld
EBIILTLOIA

[E]nc [D]ec e[X]it : D
Message : EBIILTLOIA
helloworld

ROTn

アルゴリズム

ROTnは,シーザー暗号における鍵であるシフト量を任意の値に設定したうえでシフトさせるアルゴリズムです.

攻撃方法

鍵であるnは,1から25のどれかしかないので,ブルートフォースアタックが有効です.
以下の実行結果においては,[Key 13]において平文が確認できます.

Pythonによる実装

シーザー暗号からの変更点は,シフト量(key)をユーザからの入力によって決定するようにしたことのみです.
攻撃用の関数も用意しています.

# ROTn
# n文字ずらすアルゴリズム

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

# 暗号化アルゴリズム
def Enc(plain, key):
    cipher = ""
    
    for p in plain:
        offset = (-32) - key
        p_sign = ord(p)
        c_sign = p_sign + offset
        
        if c_sign < 65:
            c_sign += 26
        
        c = chr(c_sign)
        cipher += c
    
    return cipher

# 復号アルゴリズム
def Dec(cipher, key):
    plain = ""
    
    for c in cipher:
        offset = 32 + key
        c_sign = ord(c)
        p_sign = c_sign + offset
        
        if p_sign > 122:
            p_sign -= 26
        
        p = chr(p_sign)
        plain += p
    
    return plain
    
# 攻撃用アルゴリズム
def Attack(msg):
    for key in range(25):
        print("[key {}] {}".format(key, Dec(msg, key)))
    return
    
def main():
    print("[Usage] Enc: [a-z]->[A-Z]\tDec: [A-Z]->[a-z]")
    while True:
        mode = input("[E]nc [D]ec [A]ttack e[X]it : ")
        
        if mode == "X":
            return
        
        msg = input("Message : ")

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

[E]nc [D]ec [A]ttack e[X]it : D
Message : URYYBJBEYQ
Key : 13
helloworld

[E]nc [D]ec [A]ttack e[X]it : A
Message : URYYBJBEYQ
[key 0] uryybjbeyq
[key 1] vszzckcfzr
[key 2] wtaadldgas
[key 3] xubbemehbt
[key 4] yvccfnficu
[key 5] zwddgogjdv
[key 6] axeehphkew
[key 7] byffiqilfx
[key 8] czggjrjmgy
[key 9] dahhksknhz
[key 10] ebiiltloia
[key 11] fcjjmumpjb
[key 12] gdkknvnqkc
[key 13] helloworld
[key 14] ifmmpxpsme
[key 15] jgnnqyqtnf
[key 16] khoorzruog
[key 17] lippsasvph
[key 18] mjqqtbtwqi
[key 19] nkrrucuxrj
[key 20] olssvdvysk
[key 21] pmttwewztl
[key 22] qnuuxfxaum
[key 23] rovvygybvn
[key 24] spwwzhzcwo

単一換字式暗号

アルゴリズム

単一換字式暗号(SubstitutionCipher)は,文字を特定の別の文字と対応付けることで暗号文を生成するアルゴリズムです.
換字を行うために,前もって鍵となる対応表を作成しておく必要があります.
f:id:Szarny:20180104173022p:plain

攻撃方法

単一換字式暗号に対しては,頻度分析が有効です.
出現しやすい文字(e, a, t, ...)や出現しやすい単語(the, a, I, you, of, ...)を元に平文を特定していく方法です.

Pythonによる実装

# 鍵生成アルゴリズム
def KeyGen():
    key = {
        "src": "abcdefghijklmnopqrstuvwxyz",
        "dst": "KWJHUBVGTXLZIDQYSMFRNCPAEO"
    }
    return key

# 暗号化アルゴリズム
def Enc(plain, key):
    cipher = ""
    
    for p in plain:
        if p in key["src"]:
            loc = key["src"].index(p)
            cipher += key["dst"][loc]
        else:
            cipher += p
        
    return cipher

# 復号アルゴリズム
def Dec(cipher, key):
    plain = ""
    
    for c in cipher:
        if c in key["dst"]:
            loc = key["dst"].index(c)
            plain += key["src"][loc]
        else:
            plain += 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()))
        elif mode == "D":
            print(Dec(msg, KeyGen()))
        
        print()
    
main()
[Usage] Enc: [a-z]->[A-Z]\tDec: [A-Z]->[a-z]
[E]nc [D]ec e[X]it : E
Message : hello world!
GUZZQ PQMZH!

[E]nc [D]ec e[X]it : D
Message : GUZZQ PQMZH!
hello world!

転置式暗号

アルゴリズム

転置式暗号は,文字の位置をブロックごとに入れ替えるアルゴリズムです.
いわゆる,アナグラムのような処理を行います.
復号は,暗号化時に用いた転置の逆を行うことで実現できます.
f:id:Szarny:20180104173910p:plain

攻撃方法

転置式暗号に対しては,ブルートフォースアタックが有効です.
但し,アタックにおける試行回数は「ブロック長の階乗」であるため,ブロック長が長ければ長いほど解読は困難になります.

Pythonによる実装

# 鍵生成アルゴリズム
def KeyGen():
    key = [3, 1, 4, 2]
    return key

# 暗号化アルゴリズム
def Enc(plain, key):
    cipher = ""
    
    front = 0
    rear = 4
    
    while front < len(plain):
        p_block = plain[front:rear]
        
        # ブロック内の文字が4文字に満たない場合は無視する
        if len(p_block) != 4:
            cipher += p_block
        else:
            for loc in key:
                cipher += p_block[loc-1]
                
        front += 4
        rear += 4
        
    return cipher

# 復号アルゴリズム
def Dec(cipher, key):
    plain = ""
    
    front = 0
    rear = 4
    
    while front < len(cipher):
        c_block = cipher[front:rear]
        
        # ブロック内の文字が4文字に満たない場合は無視する
        if len(c_block) != 4:
            plain += c_block
        else:
            for loc in key[::-1]:
                plain += c_block[loc-1]
                
        front += 4
        rear += 4
                
    return plain
        
def main():
    print("Enc,Dec: [whatever]->[whatever]")
    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()))
        elif mode == "D":
            print(Dec(msg, KeyGen()))
        
        print()
    
main()
Enc,Dec: [whatever]->[whatever]
[E]nc [D]ec e[X]it : E
Message : こんにちは!Hello World!
にこちんHはe!ol lrWlod!

[E]nc [D]ec e[X]it : D
Message : にこちんHはe!ol lrWlod!
こんにちは!Hello World!

ヴィジュネル暗号

アルゴリズム

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

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

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

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

攻撃方法

ヴィジュネル暗号に対しては,カシスキーテストという解読方法が存在します.
カシスキーテストは,鍵の循環的な利用によって発生する暗号文のパターンを元に,平文を割り出す方法です.(複雑なので,別記事で取り上げたい...)

※追記 書きました!
szarny.hatenablog.com

Pythonによる実装

暗号化と復号の際の文字の変換が若干複雑になっちゃってます.

暗号化の際は,ヴィジュネル方陣[鍵の文字の位置][平文の文字の位置]で文字を算出しています.
また,復号の際は,英小文字[ヴィジュネル方陣[鍵の文字の位置]における暗号文の文字の位置]で文字を算出しています.

鍵の添字に剰余を利用しているのは,添字を循環させるためです.(0, 1, 2, ... , len(鍵)-1, 0, 1, 2, ..., len(鍵)-1, 0, 1, ...)

# ヴィジュネル方陣生成アルゴリズム
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

おわりに

代表的な古典暗号について,そのアルゴリズムPythonによる実装を紹介しました.
次回から,現代暗号である共通鍵暗号公開鍵暗号をやっていきます('ω')/