暗号機エニグマをシミュレートしてみたかった

## 読み飛ばしてください

どうも限界派遣SESです。
社畜化が進んで最近記事書くことが辛くなくなって来ました。

映画イミテーションゲームを見てから既に何年か経過していますが、最近エニグマの構造を動画で解説しているものをYouTubeで見ました。

それで、順を追ってみると思ったより簡単な構造をしているのでプログラムとして起こしてみたくなりました。

## エニグマとは？

第二次世界大戦中、ドイツ軍が使用していた暗号機械のこと。エニグマ暗号は、当時の暗号解読技術では解読が困難であったことで知られています。
これは、エニグマの回路が複雑で、毎日暗号の鍵が変更されたことによるものです。

しかし、回路自体は複雑な経路を辿りますが、基本的な原理は思ったよりも単純です。エニグマの回路は、入力された文字を別の文字に置き換えるという基本的な暗号化を行っています。


## もっとも単純な暗号化

まず、最も簡単な暗号化を考えてみましょう。
アルファベット26文字をそれぞれ別のアルファベットに置き換えるという暗号化です。

例えば、１文字ずつずらすという暗号化を考えます。

```
A -> B
B -> C
C -> D
...
Z -> A
```

となるような暗号化です。これをシーザー暗号と呼びます。

この暗号化を行うプログラムを作成してみましょう。

```py
input_text = "HELLO"

# 暗号化
def encrypt(text):
    encrypted = ""
    for c in text:
        # 1文字ずらす
        code = ord(c) + 1
        # Zを超えた場合はAに戻す
        if code > ord("Z"):
            code -= 26
        # 文字に変換
        encrypted += chr(code)
    return encrypted
```

このプログラムを実行すると、`HELLO` という文字列が `IFMMP` という文字列に変換されます。

しかし、これだと暗号化のためのルールが単純すぎて、すぐに解読されてしまいます。

## より複雑な暗号化

では、どうすればより安全な暗号化を行うことができるでしょうか？
それは、暗号化の際により面倒な手続きを踏むことです。

例えば、固定の数分の文字をずらすのではなく、ランダムな数分の文字をずらすという方法です。

```
A -> C
B -> X
C -> Q
...
Z -> E
```

のようにそれぞれがランダムな文字に変換されるような暗号化です。

しかし、「頻出する文字を特定する」といったような手法により思ったより簡単に解読することができます。
そこで、より複雑な暗号化を行うために、エニグマのような暗号化を行うことが考えられます。

## エニグマの暗号化

エニグマ暗号は、入力された文字を別の文字に置き換えるという点ではこれまでの暗号化と同じですが、その置き換えが入力の度に変わるという点が異なります。
例えば最初に `A` が入力された場合、`B` に変換されるかもしれませんが、次に `A` が入力された場合には `C` に変換されるかもしれません。
これは、エニグマの回路では1文字入力される度にローターの回転によって回路が変化するためです。

また、前面にはプラグボードと呼ばれるものがあり、これによって入力された文字を固定で別の文字に変換することができます。

その組み合わせ数は膨大で、さらにこれらの組み合わせは毎日の変更されていたため暗号解読は現実的に人力では不可能な状態でした。

## Pythonでエニグマ暗号を実装する

しかしながら、最初に述べたようにエニグマの基本的な原理は回路の複雑さに反して単純です。
まず、エニグマの回路ではローターと呼ばれるものがあり、これはアルファベットの入れ替えを行うものです。

### ローターの実装

先ほどの例で示した以下のような変換表をローター実装しています。
ローターはアルファベット26文字で構成されており、それぞれの文字が別の文字に変換されるようになっています。
そのため、組み合わせは26!通りとなります。

```py
# アルファベットの範囲
ALPHABET_RANGE = 26

# ディスクを0番から26! -1 までIDが振られているとする
disk_id = 114514

def generate_disk_pattern(disk_id: int) -> list[int]:
    """ディスクのパターンを生成する
    """
    result = list(range(ALPHABET_RANGE))
    for i in reversed(range(1, ALPHABET_RANGE)):
        # 最初に Z(26番目の位置にある文字) の位置を決める
        # Z は Aから自身のZまでの26パターン入れ替えられる
        # 次は 25番目の位置にある文字の入れ替えパターンを決める
        # これはZとYが入れ替わっているパターンもあるため、Yの位置とは限らない
        # 最終的にZ から始めたスワップは 26! 通りとなる

        swap_point = disk_id % (i + 1)  # スワップ先を決める
        (result[i], result[swap_point]) = (result[swap_point], result[i])
        disk_id //= (i + 1)
    return result

# ディスクのパターンを生成
disk_pattern = generate_disk_pattern(disk_id)
```

これを実行すると
`[1, 2, 3, 24, 5, 6, 22, 23, 9, 25, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 0, 7, 8, 4, 10]`
のようなリストが生成されます。

これは、`index = 0`を`A`として考えたときに`0 -> 1`のように変換されることを示しています。
また、ローターを逆向きに変換する際は、`1 -> 0`のように変換されることを示しています。

そして、このローターをエニグマでは3つ使用しています。

### プラグボードの実装

次に、プラグボードを実装します。
プラグボードはアルファベットの入れ替えを行うものです。

これも変換表を作成して、それを元に文字列を変換する関数を作成します。

```py
def generate_plugboard(*plug_pairs: tuple[str, str]) -> list[int]:
    """プラグボードのパターンを生成する
    """

    result = list(range(ALPHABET_RANGE))
    for (a, b) in plug_pairs:
        a_index = to_index(a)
        b_index = to_index(b)
        result[a_index], result[b_index] = result[b_index], result[a_index]
    return result

# プラグボードのパターンを生成
plugboard_pattern = generate_plugboard(("A", "B"), ("C", "D"), ("E", "F"))
```

このようにプラグボードを生成することで、入力された文字を別の文字に変換することができます。

### エニグマの暗号化

このローターとプラグボードを組み合わせて、エニグマの暗号化を行う関数を作成します。
意外とアッサリしてますよね。

今までのロジックを組み合わせて、エニグマの暗号化を行う関数を作成します。

```py
import math

# A から始まるアルファベットのリストを生成
START_CHAR = ord("A")

# アルファベットの範囲(A-Z)
ALPHABET_RANGE = 26

# アルファベットのリスト
ALPHABET_LIST: list[str] = [chr(START_CHAR + i) for i in range(ALPHABET_RANGE)]

# ディスクのIDとなりうる最大値
# 26! - 1
MAX_PATTERN_ID = math.factorial(ALPHABET_RANGE) - 1


def to_char(index: int) -> str:
    """アルファベットのインデックスから文字に変換する"""
    return ALPHABET_LIST[index]


def to_index(char: str) -> int:
    """アルファベットの文字からインデックスに変換する"""
    return ALPHABET_LIST.index(char)


def print_char(char: int):
    print(f"{to_char(char)} -> ", end="")


def generate_disk_pattern(disk_id: int) -> list[int]:
    """ディスクのパターンを生成する
    """
    result = list(range(ALPHABET_RANGE))
    for i in reversed(range(1, ALPHABET_RANGE)):
        # 最初に Z(26番目の位置にある文字) の位置を決める
        # Z は Aから自身のZまでの26パターン入れ替えられる
        # 次は 25番目の位置にある文字の入れ替えパターンを決める
        # これはZとYが入れ替わっているパターンもあるため、Yの位置とは限らない
        # 最終的にZ から始めたスワップは 26! 通りとなる

        swap_point = disk_id % (i + 1)  # スワップ先を決める
        (result[i], result[swap_point]) = (result[swap_point], result[i])
        disk_id //= (i + 1)
    return result


def generate_plugboard(*plug_pairs: tuple[str, str]) -> list[int]:
    """プラグボードのパターンを生成する
    """

    result = list(range(ALPHABET_RANGE))
    for (a, b) in plug_pairs:
        a_index = to_index(a)
        b_index = to_index(b)
        result[a_index], result[b_index] = result[b_index], result[a_index]
    return result


def input_plug_pairs() -> list[tuple[str, str]]:
    """プラグのペアを入力する"""

    input_pairs = input("プラグのペアを入力してください。例: AB CD: ").split()

    # それぞれ入力が2文字かどうかを確認
    if not all(len(pair) == 2 for pair in input_pairs):
        raise ValueError("入力値が不正です")

    # 重複した場所にプラグを挿していない確認
    if len(set("".join(input_pairs))) != len(input_pairs) * 2:
        raise ValueError("プラグが重複しています")

    # 入力値をタプルに変換
    plug_pairs = [(a, b) for a, b in input_pairs]

    return plug_pairs


def input_disk_ids() -> list[int]:
    """ディスクのIDを入力する"""
    input_ids = list(
        map(
            int,
            input(
                f"ディスクのIDをいくつか入力してください。 0以上{MAX_PATTERN_ID}以下: "
            ).split()
        )
    )
    # 入力の全てが0以上かつMAX_PATTERN_ID以下かどうかを確認
    for id in input_ids:
        if id < 0 or id > MAX_PATTERN_ID:
            raise ValueError("入力値が不正です")
    return input_ids


def encrypt_disk(disk_pattern: list[list[int]], char: int) -> int:
    """ディスクによる暗号化を行う"""
    print_char(char)
    # まず、ディスクの0番目からn番目まで文字を入れ替える
    for disk in disk_pattern:
        char = disk[char]
        print_char(char)

    # ディスクを通ったあとは固定の配線のため、((ALPHABET_RANGE// 2) + char) % ALPHABET_RANGE で入れ替える
    char = ((ALPHABET_RANGE // 2) + char) % ALPHABET_RANGE
    print_char(char)

    # ここで逆方向にディスクを通す
    for disk in reversed(disk_pattern):
        char = disk.index(char)  # 逆順ということは、逆順のインデックスを取得する事になる
        print_char(char)

    return char


def rotate_disk_pattern(disk_pattern: list[list[int]], index: int) -> list[list[int]]:
    """ディスクのパターンを回転させる"""
    # ALPHABET_RANGE範囲でN進数として考える
    # ここでは26進数として考える
    # まず、diskの数 ^ ALPHABET_RANGE で全てのパターンを生成できる
    # それ以上の場合は繰り上がりが発生する

    # ディープコピーでディスクのパターンをコピー
    result = [disk.copy() for disk in disk_pattern]

    # 全ての回転パターン数
    steps = ALPHABET_RANGE ** len(disk_pattern)

    # indexがstepsを超えた場合は繰り上がりが発生する
    index = index % steps

    disk_index = 0
    while index > 0:
        # n番目のディスクの回転数を求める
        rotate_steps = index % ALPHABET_RANGE

        # ディスクのパターンを取得
        src = disk_pattern[disk_index]

        # ディスクを回転させる
        result[disk_index] = src[rotate_steps:] + src[:rotate_steps]

        # 次のディスクに繰り上げる
        index //= ALPHABET_RANGE
        disk_index += 1

    return result


def main():
    # ここではCHARのAを0として扱う(配列のインデックスとして扱うため)

    # プラグボードのパターンを生成
    plugboard = generate_plugboard(*input_plug_pairs())

    # ディスクのIDを入力
    input_ids = input_disk_ids()

    # ディスクのパターンを生成
    disk_patterns = [generate_disk_pattern(disk_id) for disk_id in input_ids]

    # 暗号化する文字列を入力
    input_text = input("暗号化する文字列を入力してください: ")

    # 入力された文字列をインデックスに変換
    char_index_list = [to_index(char) for char in input_text]

    # 暗号化を行う
    # 暗号化は一文字ずつ行う
    encrypted_text = ""

    for i, char_index in enumerate(char_index_list):

        print_char(char_index)

        # プラグボードを通す
        char_index = plugboard[char_index]

        print_char(char_index)

        # ディスクを通す
        rotated_disk_pattern = rotate_disk_pattern(disk_patterns, i)
        char_index = encrypt_disk(
            rotated_disk_pattern,
            char_index)

        # プラグボードを逆方向に通す
        char_index = plugboard.index(char_index)

        print(to_char(char_index))

        # 暗号化した文字を文字列に変換
        encrypted_text += to_char(char_index)

    print(f"暗号化前の文字列: {input_text}")
    print(f"暗号化された文字列: {encrypted_text}")


if __name__ == "__main__":
    main()
```

これを実行すると標準入力で設定と暗号化する文字列を入力求められます。

まず、プラグボードのペアを入力します。
次に、ディスクのIDを入力します。
このIDというのはとりえる組み合わせ数が26!通りあるため、その中から選択することになります。

最後に暗号化する文字列を入力すると、暗号化された文字列が表示されます。

```
プラグのペアを入力してください。例: AB CD: AB CD EF
ディスクのIDをいくつか入力してください。 0以上403291461126605635583999999以下: 114514 1919
暗号化する文字列を入力してください: HELLOWORLD
H -> H -> H -> X -> C -> P -> O -> N -> N
E -> F -> F -> W -> A -> N -> M -> K -> K
L -> L -> L -> O -> P -> C -> X -> F -> E
L -> L -> L -> P -> Q -> D -> C -> Y -> Y
O -> O -> O -> T -> U -> H -> G -> B -> A
W -> W -> W -> C -> D -> Q -> P -> J -> J
O -> O -> O -> V -> W -> J -> I -> R -> R
R -> R -> R -> E -> F -> S -> R -> J -> J
L -> L -> L -> U -> Z -> M -> L -> C -> D
D -> C -> C -> M -> N -> A -> W -> X -> X
暗号化前の文字列: HELLOWORLD
暗号化された文字列: NKEYAJRJDX
```

これを逆にすることで復号化を行うことができます。

```
プラグのペアを入力してください。例: AB CD: AB CD EF
ディスクのIDをいくつか入力してください。 0以上403291461126605635583999999以下: 114514 1919
暗号化する文字列を入力してください: NKEYAJRJDX
N -> N -> N -> O -> P -> C -> X -> H -> H
K -> K -> K -> M -> N -> A -> W -> F -> E
E -> F -> F -> X -> C -> P -> O -> L -> L
Y -> Y -> Y -> C -> D -> Q -> P -> L -> L
A -> B -> B -> G -> H -> U -> T -> O -> O
J -> J -> J -> P -> Q -> D -> C -> W -> W
R -> R -> R -> I -> J -> W -> V -> O -> O
J -> J -> J -> R -> S -> F -> E -> R -> R
D -> C -> C -> L -> M -> Z -> U -> L -> L
X -> X -> X -> W -> A -> N -> M -> C -> D
暗号化前の文字列: NKEYAJRJDX
暗号化された文字列: HELLOWORLD
```

ね、面白いでしょ？


## まとめ

エニグマ暗号は、当時の暗号解読技術では解読が困難であったことで知られています。
これはまだコンピューターがなかった時代であり、人間が手作業で解読を行っていたためです。

そしてアラン・チューリングが開発したコンピューターを使って解読に成功し、その後の私たちの暮らしに大きな影響を与えました。

やっぱ、チューリングはすごいよね。