Go to Qiita Advent Calendar 2024 Top
LoginSignup
45
23

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@KentaKudo(けんた くどう)

Enigmaの実装

Last updated at Posted at 2017-07-20

先日以下のような tweetを目にしました。

エニグマは第二次世界大戦中ナチス軍が発明し使用された最強の、”unbreakable”な暗号機です。

エニグマの動作

エニグマは以下の部品から構成されます。

  • 5つのロータ(海軍は8つ)
  • リフレクター
  • 10のプラグを設置するプラグボート
  • AからZそれぞれの入力スイッチ
  • AからZそれぞれの出力ランプ

毎朝コードブックを確認し、その日の

  • 使用するロータ3つとその順番
  • ロータの初期位置を示すアルファベット三文字
  • 10のプラグの配置

をもとにエニグマをセットアップします。

800px-EnigmaMachineLabeled.jpg
(https://en.wikipedia.org/wiki/Enigma_machine　より)

送信者は文字をタイプした時に点灯するランプの文字を一文字づつ書き写し、暗号文として送信します。
受信者は送信者と同じセットアップをした後、受け取った暗号文を一文字づつ入力し、ランプに示された文字から元の文、平文を得ることができます。

エニグマの原理

入力された文字はプラグボードを通してロータに送られます。プラグボードは繋がれた2文字の信号を入れ替えます(A ⇄ Eのように)。プラグボードにより、組み合わせの総数を爆発させることができます。

プラグボードを出た信号は3つ並んだロータに順に入力されます。
ロータは文字を違う文字に変換する役割を持っています(プラグボードとの違いはA→EのときにE→Aとなるかどうか。ロータはなってもいい、プラグボードはならなくてはいけない)。同じ文字に対応しても構いませんが、文字が重複してはいけません(A→Aはいいけど、A→E,B→Eはだめ)。
この文字と文字の対応は換字表と呼ばれ、26!通り存在します。各ロータはこの26!通りある中の一つを表しています。

ロータをでた信号はリフレクタに入力されます。
リフレクタもプラグボードと同じようにA⇄Eとなる装置ですが、全ての文字が違う文字に変換される必要があります(A⇄Aになってはいけない)。
リフレクタがあることで暗号化と復号を同じ手順で行うことが可能になります(あとで確かめてみます)。一方で、A⇄Aになってはいけないという制約が暗号解読の突破口となってしまいました。

信号はリフレクタでUターンをし、3つのロータ、プラグボードを通ってランプに繋がり、点灯します。
と同時にロータが回転します。一番右のロータは一文字分回転、真ん中のロータは右のロータが一回転(26文字分)したとき一文字分回転、一番左のロータは真ん中のロータが一回転(26*26文字分)したとき一文字分回転します。
こうして入力ごとに回転が起こることで、同じ文字を入力しても毎回出力が違う動作になり(一文字ごとに違う換字表を使っていることになる)、頻度解析のような方法で解読されるのを防ぐことができます。

Enigma_wiring_kleur.svg.png
(https://ja.wikipedia.org/wiki/エニグマ_(暗号機) より)

エニグマで作る暗号の組み合わせの総数は、

  • ロータの組み合わせ: 5つから順番を考慮し3つ選ぶので543 = 60通り
  • ロータの初期位置の組み合わせ: 262626 = 17576通り
  • プラグの組み合わせ: 26! / 6! / 2**10 / 10! = 150738274937250通り1

この全てを掛け合わせた、158,962,555,217,826,360,000通り(159 million million million)です。

実装

エニグマについてわかったところで実際に書いてみました。
https://github.com/KentaKudo/Enigma

言語はSwiftです。

public struct Enigma {
    
    private var rotorBox: RotorBox
    private let plugboard: Cipher
    
    public typealias Key = (Token, Token, Token)
    public init(rotor0: @escaping Cipher, rotor1: @escaping Cipher, rotor2: @escaping Cipher, plugboard: @escaping Cipher, key: Key) {
        self.rotorBox = RotorBox(
            rotor0: RotorBox.Rotor(rotor0, position: key.0),
            rotor1: RotorBox.Rotor(rotor1, position: key.1),
            rotor2: RotorBox.Rotor(rotor2, position: key.2)
        )
        self.plugboard = plugboard
    }
    
    public mutating func cipher(_ target: Token) -> Token {
        return plugboard(rotorBox.cipher(plugboard(target)))
    }
    
    public mutating func cipher(_ target: String) -> String {
        var output = ""
        for char in target.characters {
            output += String(cipher(Token(rawValue: char)!).rawValue)
        }
        return output
    }
}

イニシャライザでその日のロータ3つ、プラグの組み合わせ、ロータの初期位置Keyを受け取ります。
文字は以下のように定義しました。

public enum Token: Character {
    case A = "A", B = "B", C = "C", D = "D", E = "E", F = "F"
    case G = "G", H = "H", I = "I", J = "J", K = "K", L = "L"
    case M = "M", N = "N", O = "O", P = "P", Q = "Q", R = "R"
    case S = "S", T = "T", U = "U", V = "V", W = "W", X = "X"
    case Y = "Y", Z = "Z"
}

ロータ、プラグボード、リフレクタを表すCipherは文字を受け取って文字を返す関数として定義しています。

public typealias Cipher = (Token) -> (Token)

暗号化の処理は 入力→プラグボード→ロータ→プラグボード の順に関数を呼び、最後のプラグボードからの出力を返します。
次にRotorです。

public struct RotorBox {
    
    public struct Rotor {
        
        let forward: Cipher
        let backward: Cipher
        var position: Token
        
        init(_ forward: @escaping Cipher, position: Token) {
            self.forward = forward
            self.backward = { token in
                let tokens: [Token] = [.A, .B, .C, .D, .E, .F, .G, .H, .I, .J, .K, .L, .M, .N, .O, .P, .Q, .R, .S, .T, .U, .V, .W, .X, .Y, .Z]
                return tokens.filter{ forward($0) == token }.first!
            }
            self.position = position
        }
        
        mutating func rotate() {
            position = position.next()
        }
    }

    ...

}

換字のパターンと初期位置を渡して初期化します。往路と復路、forward・backwardの処理は逆になります(A⇄E)。これはリフレクタとは異なるので注意してください。イメージとしては、リフレクタは表のAと表のEがつながっているイメージ、ロータは表のAと裏のEがつながっているイメージです。
次に暗号化の処理です。

public struct RotorBox {
    
    ...
    
    public mutating func cipher(_ target: Token) -> Token {
        defer {
            rotate()
        }
        
        let input = connect(pure, rotor0)(target)
        let r0 = rotor0.forward(input)
        let _r0 = connect(rotor0, rotor1)(r0)
        let r1 = rotor1.forward(_r0)
        let _r1 = connect(rotor1, rotor2)(r1)
        let r2 = rotor2.forward(_r1)
        let _r2 = connect(rotor2, reflector)(r2)
        let ref = reflector.forward(_r2)
        let _ref = connect(reflector, rotor2)(ref)
        let r2ret = rotor2.backward(_ref)
        let _r2ret = connect(rotor2, rotor1)(r2ret)
        let r1ret = rotor1.backward(_r2ret)
        let _r1ret = connect(rotor1, rotor0)(r1ret)
        let r0ret = rotor0.backward(_r1ret)
        let output = connect(rotor0, pure)(r0ret)
        
        return output
    }
    
    private mutating func rotate() {
        mod1 = (mod1 + 1) % 26
        mod2 = (mod2 + 1) % (26 * 26)
        rotor0.rotate()
        if mod1 == 0 {
            rotor1.rotate()
        }
        if mod2 == 0 {
            rotor2.rotate()
        }
    }
    
    private func connect(_ input: Rotor, _ output: Rotor) -> (Token) -> Token {
        let gap = input.position - output.position
        return { token in
            return token - gap
        }
    }
}

ロータ0から順につなぎ、リフレクタでUターンして戻ってきます。
ポイントは

  • connectによりロータ間の相対的なずれを修正している
  • 関数を抜ける際に回転する

点です。

ロータを出た信号がAだった時、その信号はそのまま隣のロータに入りますが、そこがAであるとは限らないので、connectメソッドにより相対的な位置を考慮して修正します。(演算子の定義等は省略しています。)
また、mod1,2でロータ1,2の回転の状態を保存します。

…というわけで実際に動かしてみましょう。
以下のようにロータとプラグボードを定義します。

let I_K: Cipher = { token in
    switch token {
    case .A: return .P
    case .B: return .E
    case .C: return .Z
    case .D: return .U
    case .E: return .O
    case .F: return .H
    case .G: return .X
    case .H: return .S
    case .I: return .C
    case .J: return .V
    case .K: return .F
    case .L: return .M
    case .M: return .T
    case .N: return .B
    case .O: return .G
    case .P: return .L
    case .Q: return .R
    case .R: return .I
    case .S: return .N
    case .T: return .Q
    case .U: return .J
    case .V: return .W
    case .W: return .A
    case .X: return .Y
    case .Y: return .D
    case .Z: return .K
    }
}
let II_K: Cipher = { token in
    switch token {
    case .A: return .Z
    case .B: return .O
    case .C: return .U
    case .D: return .E
    case .E: return .S
    case .F: return .Y
    case .G: return .D
    case .H: return .K
    case .I: return .F
    case .J: return .W
    case .K: return .P
    case .L: return .I
    case .M: return .C
    case .N: return .Q
    case .O: return .X
    case .P: return .H
    case .Q: return .M
    case .R: return .V
    case .S: return .B
    case .T: return .L
    case .U: return .G
    case .V: return .N
    case .W: return .J
    case .X: return .R
    case .Y: return .A
    case .Z: return .T
    }
}
let III_K: Cipher = { token in
    switch token {
    case .A: return .E
    case .B: return .H
    case .C: return .R
    case .D: return .V
    case .E: return .X
    case .F: return .G
    case .G: return .A
    case .H: return .O
    case .I: return .B
    case .J: return .Q
    case .K: return .U
    case .L: return .S
    case .M: return .I
    case .N: return .M
    case .O: return .Z
    case .P: return .F
    case .Q: return .L
    case .R: return .Y
    case .S: return .N
    case .T: return .W
    case .U: return .K
    case .V: return .T
    case .W: return .P
    case .X: return .D
    case .Y: return .J
    case .Z: return .C
    }
}
let UKW_K: Cipher = { token in
    switch token {
    case .A: return .I
    case .B: return .M
    case .C: return .E
    case .D: return .T
    case .E: return .C
    case .F: return .G
    case .G: return .F
    case .H: return .R
    case .I: return .A
    case .J: return .Y
    case .K: return .S
    case .L: return .Q
    case .M: return .B
    case .N: return .Z
    case .O: return .X
    case .P: return .W
    case .Q: return .L
    case .R: return .H
    case .S: return .K
    case .T: return .D
    case .U: return .V
    case .V: return .U
    case .W: return .P
    case .X: return .O
    case .Y: return .J
    case .Z: return .N
    }
}
let ETW_K: Cipher = { token in
    switch token {
    case .A: return .Q
    case .B: return .W
    case .C: return .E
    case .D: return .R
    case .E: return .T
    case .F: return .Z
    case .G: return .U
    case .H: return .I
    case .I: return .O
    case .J: return .A
    case .K: return .S
    case .L: return .D
    case .M: return .F
    case .N: return .G
    case .O: return .H
    case .P: return .J
    case .Q: return .K
    case .R: return .P
    case .S: return .Y
    case .T: return .X
    case .U: return .C
    case .V: return .V
    case .W: return .B
    case .X: return .N
    case .Y: return .M
    case .Z: return .L
    }
}
let swissK = [I_K, II_K, III_K, UKW_K, ETW_K]
let plugboard: Cipher = { token in
    switch token {
    case .A: return .D
    case .B: return .P
    case .C: return .L
    case .D: return .A
    case .E: return .X
    case .H: return .M
    case .J: return .S
    case .K: return .O
    case .L: return .C
    case .M: return .H
    case .N: return .Z
    case .O: return .K
    case .P: return .B
    case .Q: return .Y
    case .S: return .J
    case .U: return .W
    case .W: return .U
    case .X: return .E
    case .Y: return .Q
    case .Z: return .N
    default:
        return token
    }
}

ロータは出力文字が重複しない限り適当で構いませんが(ここではwikipediaよりSwissKというモデルを参考にしました)、プラグボードは2つの文字が対応するように気をつけてください。
以下のようにエニグマをセットアップし、暗号・復号してみます。

var enigma = Enigma(rotor0: swissK[0], rotor1: swissK[1], rotor2: swissK[2], plugboard: plugboard, key: (.A, .A, .A))
let message = "HELLOWORLD"
let message2 = "AAAAAAAAAA"
let ciphered = enigma.cipher(message)
let ciphered2 = enigma.cipher(message2)

var _enigma = Enigma(rotor0: swissK[0], rotor1: swissK[1], rotor2: swissK[2], plugboard: plugboard, key: (.A, .A, .A))
let deciphered = _enigma.cipher(ciphered)
let deciphered2 = _enigma.cipher(ciphered2)

1-V904x73Tm-d1xhGwBI2N0w.png

無事平文を得ることができました。リフレクタのおかげで暗号と復号が同じ手順でできます。また、同じ文字を続けて入力しても違う文字が返ってくることがわかります。

ためしにロータの回転を止めてみると…

1-ycbn42ba5ugiblRQQVm_fA.png

1-RcJtypdfCW3MzNQLvSaXYg.png

このように、同じ入力は同じ出力となります。

以下のサイトで遊ぶことができるので試してみてください。
https://swift.sandbox.bluemix.net/#/repl/596fbd6ea2b1686cef557b9d

さいごに

さてこの最強の暗号機エニグマはアランチューリングが発明したBombeにより解読されるわけですが、その詳細及びそれにまつわるドラマはこちらの本にお任せしたいと思います。
暗号解読〈上〉 (新潮文庫)

また、 The Imitation Game という、チューリングや第二次世界大戦中のブレッチリーパークを題材にした映画もおすすめです。
イミテーション・ゲーム/エニグマと天才数学者の秘密

そして暗号の技術的側面に触れたい方は「暗号技術入門」がおすすめです。
暗号技術入門 第3版

参考

  1. プラグの組み合わせ: 26文字から順番を考慮せず2文字選ぶのでC(26,2)、次に24文字から2文字選ぶのでC(24,2)、以下同様。よってC(26,2) ×C(24,2)×C(22,2)×…×C(2,2) = 26! / 6! / 2**10、プラグはすべて同じで区別がつかないので区別がついた場合の組み合わせ10!で割る。 ↩

45
23
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
45
23

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?