RNNで暗号であるEnigmaを解く

Enigma暗号とは

　1918年に発明されたEnigmaは第二次世界大戦時に発明された暗号化機であり、電線の配線のパターンと、ロータといわれる入力するたびに回転する円盤のパターンで、様々な文字の置き換えを行います。

　ドイツ軍で用いたられたアルファベットの数だけ暗号化のもととなる配線が記された三つのロータを組み合わせて、膨大な動的に変換するパターンを構築して文字列を置換して、単純な交換則が成立しない複雑な暗号を構築して連合軍を苦しめました。

図1. JavaScriptによるEnigma Simulator

　連合国側のイギリスの特殊チームのULTRAによって解析されたようです。数学的な暗号の原理を追っているのですが、まだ完全にキャッチアップしきっておりませんが、群論とコンピュータのパワーとヒントとなるキーが人間の発想に依存するという特性を利用して解いたそうです。総当たりに近い方法を用いており、とにかくコンピュータリソースが必要でした。

　2006年、分散コンピューティングを利用して総当たりにて、最後の未解決であったEnigma暗号を解いたとのことです[1]。

どのようにEnigmaを連合国軍は解いたのか

二つの方法を組み合わせたような表現を確認しました。

Bombeとよばれるコンピュータで総当たり攻撃した
人間が利用しがちなカギや文章（日付などが末尾に入るとか）から推定されるパターンを限定する

図2. 現代に再現さたBombe(Wikipediaより)

今風の機械学習で解くにはどうすればいいのか

2.のように、何らかの暗号化前の文章と暗号化後の暗号文が手に入ったとします。このとき、この対が十分な量があるとき、ディープラーニングのアルゴリズムの一つであるRNNで解くことが可能です[2]

ロータが機械的に回転し、絡み合うような仕組みは、ディープラーニングのような機械学習は苦手だろう思い込みがあったので、この[2]の資料を見たときは驚きました。

ロータが二つのEnigmaを仮定

　複雑な三つのロータではなく、簡単にした二つのロータのみで構成されるEnigmaを仮定します

　Enigmaのロータは一文字進むごとに回転し、初期値が不明になっており、キーはランダムになっているとします.

　初期値が不明なため、26(+3)²パターンの成立しうるロータの状態をディープラーニングのネットワークを施行し、もっとも自然な文字列である初期状態とロータの配線を全探索しないと、原理として解くことはできません。

　暗号化として以下のような二つのロータを仮定したスクリプトを作成ました

　コーパスとしてBBCの公開ニュースコーパスを利用しています。

total = ''
for name in glob.glob('courpus/bbc/*/*'):
  try:
    text = open(name).read()
  except Exception as ex:
    continue
  buff = []
  for char in list(text.lower()):
    if char in char_index_0:
      buff.append(char)
  total += ''.join(buff)

# random slice
pairs = []
for index in random.sample( list(range(0, len(total) - 150)),100000):
  _char_index_0 = copy.copy(char_index_0)
  _char_index_1 = copy.copy(char_index_1)
  real = total[index:index+150]

  enigma = []
  for diff, char in enumerate(real):
    # roater No.1 update _char_index
    _char_index_0 = { char:(ind+1)%len(_char_index_0) for char, ind in _char_index_0.items() }
    # get index
    ind = _char_index_0[char]
    next_char = chars[ind]

    # roater No.2
    _char_index_1 = { char:(ind+1)%len(_char_index_1) for char, ind in _char_index_1.items() }
    # get index
    ind = _char_index_1[next_char]
    next_char = chars[ind]

    enigma.append(next_char)
  cript = ''.join(enigma)

  crop = random.choice(list(range(len(char_index_0))))
  real, cript = real[crop:crop+100], cript[crop:crop+100]
  pairs.append( (real, cript) )

open('pairs.json', 'w').write( json.dumps(pairs, indent=2) )

DeepLearningのネットワークを設計

Kerasで実装しました。
GRUを用いネットワークはこのようになっています。
初期状態が不明なEnigmaで暗号化された暗号文を最大100文字入力し、対応する100文字を入力します

timesteps   = 100
inputs      = Input(shape=(timesteps, 29))
x           = Bi(GRU(512, dropout=0.10, recurrent_dropout=0.25, return_sequences=True))(inputs)
x           = TD(Dense(3000, activation='relu'))(x)
x           = Dropout(0.2)(x)
x           = TD(Dense(3000, activation='relu'))(x)
x           = Dropout(0.2)(x)
x           = TD(Dense(29, activation='softmax'))(x)

decript     = Model(inputs, x)
decript.compile(optimizer=Adam(), loss='categorical_crossentropy')

前処理

Enigmaの配線をランダムで初期化

$ python3 14-make-enigma.py

コーパスから暗号文と正解のペアを作成

$ python3 15-prepare.py

RNNで入力する密ベクトルに変換

$ python3 16-make-vector.py

学習

全体の99%を学習します

$ python3 17-train.py --train

評価

学習で使わなかった1%のデータを評価します

$ python3 17-train.py --predict

出力

[オリジナルの文] 　　 all targets, he said. the exceptional quality of the paintings in our permanent collection is also h
[入力された暗号文] 　 ccxej,,,xum yh.bfpp,ggm.ihsorjges.iy .cyvmyl wvogaxdqyzqmomtdkzbqqeobszs uyyaoagyy.nsuomynekaescf sc
[モデルで評価した文]  all targets, he said. the exceptional quality of the paintings in our permanent collection is also h

このように、Enigmaのネットワークが未知であっても、確定してわかるテキストが十分にあれば、RNNでエニグマ暗号は解けることがわかりました。
今回は仮想的なロータを二つソフトウェア的に再現しましたが、ロータが三つでも十分にRNNのネットワークが大きく、データが十分にあれば、この延長線上で解けると思います。