Document

エニグマ暗号の解読
ドイツ軍の暗号はどのように
解読されたか?
その手法は現代暗号にも使えるか?
星野 力
エニグマ暗号とは?
• 対称性のある換字暗号
• 例 a←→k e ←→w
平文(ひらぶん) plaintext
暗号文
ciphertext
平文
a
暗号文
k
… k
w … a
e
平文の1文字毎に交換関係が変化し、単純な頻度分析
(ポオ「黄金虫」やコナンドイル「踊る人形」)では解読できない。
共通鍵暗号(送り手と受け手が同じ暗号表を持つ)なので、暗号
表を予め別の手段で配らないといけない。
対称性があるので、暗号と復号は同じ機械でできる。
エニグマ暗号機
ブレチレイパークにて撮影
幅は30cm程度
ローター
ランプ
キーボード
スッテカー・ボード
Wikipediaの記述
暗号機の内部結線
電池
↓
キーボード
↓
ステッカーボード(10本の結線)
↓
3つの文字変換ローター
↓
反射板
↓
再びローターとステッカー結線
↓
ランプ
↓
電池へ戻る
ローター
• 両面の接点間をランダム
な結線でつないでいる。
• 結線はローター毎に異な
る。固定。
• ローターには26文字が表
示されたリングがあり、円
周方向に回転させ固定で
きる。
• ローターが1回転する間
に、爪が隣のローターに
力を伝え1文字だけ回転
させる。歯車計算器の桁
上げ機構に類似。
ドイツ軍同士の通信(送り手)
配布された暗号表による日毎の初期設定;日鍵
ロータ 1 2 3 4 5
暗号表
(X月Y日)
ロータ を 位置 へ挿入
245
BCD
ロータ
2 4 5
挿入位置 A B C D
リング設定
リング設定
端子 と 端子 を接続
C
K
A
M
…………… 合計10ペア
R
W
スッテカーボード端子
A B C D ………
K L M ……R S T
UVWXYZ
エニグマ暗号機
日鍵設定の可能な総数
• ローター5枚から3枚を選び順に挿入。5P3=60
• ローターの初期回転位置。26x26x26=17576
• ステッカー結線:26端子を10本のケーブルで。
14
C
・
C
・
C
・・・
C
/
10!
≒
1.5x10
26 2 24 2 22 2
8 2
• エニグマ暗号変換の総組み合わせ数
≒1.58x1020
ドイツ軍同士の通信(送り手) 続き
日鍵を使ってメッセージ鍵(その通信だけに有効な鍵)を
送る
• インディケーター設定;ローターを任意に選んだ初期位置にセットする。
たとえば文字 JCMが見える位置に。
• インディケーター;任意に選んだ三つの文字(BGZとしよう)を2回(BGZ
BGZ)タイプする。BGZBGZは暗号化されて、TNUFDQ(ランプが点
灯)に。それを記録する。後、タイプは1回になった。
平文 → 暗号文
• ローターをBGZに合わせ、本番のテキストをタイプする。ランプを読みと
り暗号文を記録する。
無線送信
• コールサイン、時刻、文字数、暗号機の型を送る。
• インディケーター設定 JCMを送る。次に暗号化され
たインディケーターTNUFDQを送る。
• 暗号化された本文を送る。
受け手(ドイツ軍)
• 暗号表の日鍵に合わせて、暗号機を設定し、電文の到着
を待つ。
• 受信したインディケーター設定 JCMにローターを合わせ
る。
• 受信したインディケーターTNUFDQをタイプするとBGZ
BGZという復号されたインディケーターが現れるので、
ローターをBGZに合わせる。
• 受信した暗号化本文をタイプすると、最終的な平文がえら
れる。
受け手(イギリス軍)
• 電文を傍受しても日鍵が不明なので、解読できない。
日鍵は暗号表を入手すれば解る。
• 暗号表はスパイ活動または戦場の作戦で入手でき
たが、作戦は容易ではないし、入手しても1ヶ月しか
有効ではない。
• 暗号機が改造されるとお手上げ。4枚ローターの暗
号機がUボートに配置されたとき、暗号は10ヶ月間
解読できなくなった。多くの人命が海の底に沈んだ。
ポーランド数学者レイェフスキーらによる解読
• 暗号機の構造・通信方法を(実は日鍵も)フランス情報部から得ていた。
• 1938年以前;日鍵の組み合わせ数が少なかった。
(ローター3枚の挿入 6通り) ×
(インディケーターの組み合わせ26の3乗) =
105456通り
• インディケーター設定を2回タイプしていた。
平文
B G Z
B
G
Z
暗号文
T N U F
R
Q
ポーランドの発見(1)
サイモン・シン「暗号解読」より
• 暗号文{E . . X . . .} とか {X . . O . . .} とか {O . . M . . .}
• 1番目と4番目の文字の間の関係
1番目
4番目
•
•
•
•
•
Eから始まる長さ5のループ;E→X→O→M→H→E
Aから始めると15の長さのループ;(省略)
Vから始めると長さ1のループ(不動点);V→V
I から始めると長さ5のループ;I→S→K→U→Q→I
この4つのループで26文字すべてを尽くしている。
ポーランドの発見(2)
• ループ構造(ループの数とその長さ)は、ローター変
換に固有で、ステッカー結線の影響を受けない。ス
テッカー結線は2文字を入れ替えるだけ。
• 日鍵のすべての組み合わせ( 105456通り)を、レ
プリカの暗号機で試し、日鍵 vs ループ構造の表
を作る。
• ある日の暗号文を集めて、最初の六文字からルー
プ構造を抽出し、この表を逆引きすれば、日鍵が発
見できる。
もちろん事はそれほど簡単ではない
• 6文字のうちにループが含まれていないかも。
• ステッカー結線で文字が入れ替わっていて、平文が読みとれ
ない。暗号機により実際に試すという試行錯誤がいる。
• しかし、本質的な山はこれで越えられた。
• 後に、ループを自動的に発見するリレー式の電気回路
(Bomba)を作って対抗したが、……
• 時間切れ。ドイツのポーランド侵攻が目前に。このノウハウは
フランスとイギリスの諜報部へ渡された。
ブレッチレイ・パーク
ロンドンの北西、約60kmにあるお屋敷
(大戦中は政府の暗号学校、現在はテーマパーク)
建て増しが多くてよくわからないが、
これが入り口。
Hut8 チューリングらが
暗号解読していた小屋
チューリングらによるアプローチ
•
機械化と数理的考察をさらに進め、エニグマ暗号解読の専用マシン;
Turing Bombeを設計・製作し、リアルタイムに解読した。
•
チャーチルの回顧録にも出てこないほど極秘にされた活動(暗号名
ULTRA)。
独創性は;
• スクランブラーという3枚のローターの機能をシミュレートする回転ドラムを、
多数並列に並べ、暗号機の逐次的な状態を空間方向に展開。
•
電流経路を26本の並行ケーブルとし、26文字を同時並列にスキャン。
•
最も独創的な発明はフィードバック結線、とくに対角結線。
• 数学的な考察(チューリングによる)。
スクランブラー
ローターの往復の回路を一方向に展開し
たもの。ただし桁上げ機構がない。
チューリング・ボンベ
• スクランブラーを並列に(文字列の方向)へ並べ、26芯
ケーブルで自由に接続できるようにしたもの。
2007年、ブレッチレイ・パークにて再現されたチューリン
グ・ボンベが動いています。
http://www.jharper.demon.co.uk/bombe2.htm
イギリスの暗号解読の概略
•
諜報活動によって、暗号機の構造、日鍵とメッセージ鍵の存在、通信方
法を承知していた。
•
目的;日鍵を1日以内に推定しなければならない。
•
まず、クリブ(平文の中に含まれると推定された文字・句)から、文字の間
の関係「メニュー」を取り出し、それに基づいてスクランブラー間を配線す
る。
•
自動運転;日鍵を順次スクランブラーに設定し、リレー回路で電圧の分
布を調べ、日鍵とステッカー結線が発見されれば、自動運転をストップ
する。
•
レプリカ暗号機で、矛盾なく解読されていることを確認。
•
矛盾があるとき、次の日鍵を自動的に設定し、自動運転を続ける。
ボンベで解読さ
れた状態
暗号文
平文
注;この図ではスッカー結線が見えなくなっている
•
暗号文「UILKNX」
平文「GEHEIM」はクリブ
•
•
•
•
•
•
電圧のかかっている端子;
暗号側の最左のスクランブラーのU端子だけに、
2番目のスクランブラーの I 端子だけに、
3、4、5、6番目のスクランブラーのL、K、N、X端子だけに、
平文側も同様。
これら以外の端子には電圧はかかっていない。
•
•
これが正しく解読された状態。
しかし、これを一気に発見することはほとんど不可能。
ステッカー結線を明示すると
暗号文が
Z M K H V K
平文の推定(クリブ)が G E H E I M
そこからM→E→H→K→Mという長さが4のメニューが
取り出される。メニューを構成する回路全体に電圧は拡がる。
M/A 仮説
• 第2スクランブラで、文字Mの相手(ローター端子)は未知。
• それを仮にAとする(MとAを結ぶステッカー結線を仮定)。
• 第6スクランブラーのMの相手も当然Aである(結線は1日中
変わらない)。Aだけに電圧が現れるはず。
• もし現れていないときは、Mの相手はAでなくBかも。それもダ
メなら全部の文字を試行することになるが、それには長い時
間を要する。
• その試行をやらずに、瞬時に相手を発見する方法がフィード
バック結線: M→E→H→K→M~Mという閉回路を作り、
電圧の分布を調べる。
正解の条件
• スクランブラーが正しく設定されている場合;
• (C1) ある端子に電圧をかけると、その端子に限って電圧が
現われる。
• (C2) ある端子に電圧をかけると、その端子を除いて電圧が
拡がる。
• (C1)か(C2)であることをリレーで判別し、自動的に停止す
る。
• クリブが不足してメニューが間違っている場合、「偽の停止」も
ありうる。
• それを避けるには良質のクリブが必要で、007のような活動を
実際イアン・フレミングがやっていたという。
正解でない場合
• メニューが適切ではないか、スクランブラーの設定が
間違っている場合;
• 電圧は全部の端子へ拡がる。
• これは、述語論理の命題「間違った仮定から導出さ
れる定理は全部真になる」の一例であると解釈され
ている。
フィードバック結線
(大きな発想の転換 )
恒等的に等しくなるべき変数は低抵抗のケー
ブルで結合してしまう。
コンピュータ(チューリング・マシン)
では、恒等的に等しい変数は(専用
ハードウェアを作らないかぎり)、原理
的に実装出来ない。
チューリング・ボンベはチューリング・
マシンではない。
対角結線
• 数学者ウエルチマンによって提案された。
• ステッカー結線は対称であるから、対称の位置にあ
る端子ペアを積極的に低抵抗のケーブルで結線し
てしまえばいい。
• フィードバック結線と同じ哲学に基づいている。
• 対角結線によって、クリブの不足は大幅に補なわれ、
暗号解読の成功率は大きく改善した。
ステッカー結線の推定
• ボンベが自動的に停止した。文字Mが自動的に見つかった。
• ステッカー結線のないレプリカの暗号機に、日鍵やメッセージ
鍵を設定し、第2スクランブラのVから辿れば、文字E、H、Kの
ステッカー結線相手α、γ、δが順に判明する。
• そのとき、ステッカー結線相手に矛盾(重複)が生じると、その
停止状態は「偽の停止」である。
• ボンベは次の鍵を設定して、探索を再開する。
• 以上の手順:電圧の分布を自動的に判定し、ステッカー結線
の無矛盾状態を発見するリレー回路を追加したボンベの改良
機“JUMBO”があった。
解読手順のまとめ
(1)最初のスクランブラーを日鍵とメッセージ鍵探索の初期値に設定し、順次スクラン
ブラーを一文字ずつ回転させる。
(2)電文からクリブを想定し、メニューを作成し、スクランブラー間を結線する。フィー
ドバック結線と対角結線を追加する。
(3)試行端子(普通はAとする)を選び、そこに電圧をかける。
(4)ボンベは全部の端子の電圧を自動的にチェックし、全部に現れていたら、それは
間違った鍵なので、(7)へ進む。
(5)メニューに現れている文字端子に順次電圧をかけ、その電圧だけがそのままで、
他の端子には電圧が現れていないか(この状態をストレートと呼んだ)を調べ
る。これは正解条件(C1)の場合である。他の端子に電圧が現れていれば
(7)へ。
(6)いくつかのストレートの状態がみつかれば、それらに関して、ステッカー結線の無
矛盾(異なった端子と二重に結線されていないこと)を確かめ、すべてのスト
レートが矛盾していれば(7)へ。無矛盾なものが残れば、ボンベは停止し
(8)へ。
(7)スクランブラーは自動的に回転し、次の鍵の設定に変わる。(3)へ戻る。
(8)ローターの桁上げ位置すなわちリング設定と、ループ中には現れていないステッ
カー結線を推定する仕事が残っている。レプリカの暗号機において、実際に
求まった日鍵とメッセージ鍵を設定し、暗号文を打ち込んでみて、意味のあ
るドイツ語(平文)が現れるまで試行錯誤をくり返し、矛盾しない桁上げ位置
とすべてのステッカー結線を推定する。
(9)レプリカ機に日鍵とメッセージ鍵を設定し、暗号文を打ち込んで平文をえる。
北大西洋の戦い
• Uボート; 連合軍の輸送船団を発見すると、
暗号電文で基地へ報告する。1昼夜以内にU
ボートが集合し、攻撃態勢が整う。
• 輸送船団;Uボートに発見されたということが
(傍受した暗号の解読で)わかれば、回避行動
をとる。
• 戦後も機密保持は厳重で、解禁されたのは
1970年代。チューリングの名誉回復は実に
2009年。
COLOSSUS
• フィッシュ暗号(ドイツ軍上層部で使われ
た)解読のための専用マシン(相関計算)
↑ローレンツ
暗号機
復元COLOSSUS
→
もしイギリスが暗号解読に成功して
いなかったら…?
• 終戦時 200台のボンベ;10台のCOLOSSUSが
あった。
• ボンベがなかったら、アメリカからの物資・武器・
人員輸送ははかどらず、ソ連軍の進撃も遅れる。
• COLOSSUSがなかったら、ノルマンディ上陸作
戦は成功せず、連合軍の進撃も遅れる。
• ドイツ軍のイギリス空爆と上陸、アメリカによるド
イツへの原爆投下の可能性。
• ヨーロッパの戦後は、今とは大きく違った姿に
なっただろう。
恒等回路の一般化
• 自由な変数が張る空間
を想定し、ルールや法則で
その空間を制約したものが解空間
である。
• 例;物理の最小作用経路。制約プログラミングなど。
• そのとき、制約を満たさない矛盾した解の張る部分空間を崩
壊させる(矛盾を掻き出す)強力な手法があれば望ましい。
恒等回路はそういう手法かも?
数学的な多変数空間
矛盾した解空間
法則で制約された解空間
現代暗号も恒等回路で解けるか?
• 中身は何であれ、それをブラックボックスにして、自
己言及(恒等)回路
のループ中に入れてしま
えばいい。
平文
任意の暗号
暗号文
鍵
しかし……残念だが
ここが逐次的になる。
越中コンピュータで
チューリングを越えたい!
デジタル回路では0と1の出力がぶつかると、
過電流が流れる。それを検出する?
Brainstormingをやれば、まったく新しい計算のパラダイムが
開けるかも。やる気さえあれば………。
参考
•
Frank Carter “The Turing Bombe” The Bletchley Park Trust
Report no. 16 (Jan. 2000)
•
サイモン・シン「暗号解読」新潮社 2001
•
ルドルフ・キッペンハーン「暗号攻防史」文春文庫 2001
•
F.L.Bauer “Decrypted Secrets” Springer 1997
•
F.H.Hinsley & Alan Stripp “Code Breakers” Oxford Univ. Press
1993
•
星野 力「甦るチューリング」NTT出版 2002
•
星野 力「チューリングを受け継ぐ」頸草書房 2009