コンピュータの歴史 - VRL - Vision and Robotics

計算機システムⅡ
コンピュータの歴史-2
戦時期における暗号解読
和田俊和
講義計画
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
コンピュータの歴史1
コンピュータの歴史2 (←本日)
コンピュータの歴史3
演習問題
論理回路と記憶,計算:レジスタとALU
主記憶装置とALU,レジスタの制御
命令セットアーキテクチャ
演習問題
パイプライン処理
メモリ階層:キャッシュと仮想記憶
命令レベル並列処理
命令実行順序の変更
入出力と周辺装置:DMA,割り込み処理
演習問題
現代的な計算機アーキテクチャの解説と試験
•
教科書:坂井修一著:電子情報通信学会レクチャーシリーズC−9,コンピュータア
ーキテクチャ,コロナ社
•
最終回の試験によって成績評価を行う.5回以上欠席で不合格とする.
戦時中最も計算を必要としたのは
兵器開発ではなく,暗号解読だった
• ドイツは第一次世界大戦(1914〜1918)勃発後にアメリ
カ駐在のドイツ大使に暗号の電文を送っていた.
– メキシコに資金を提供し,参戦を躊躇していたアメリカ南部を
攻撃し,州を奪還するように要求させ,さらにメキシコ経由で
日本にアメリカ西岸を攻撃させるよう,メキシコ政府とコンタク
トを取れという内容
• この電文をイギリスは傍受・解読し,内容をアメリカ側
に伝え,アメリカは参戦し,ドイツは敗北
• しかし,イギリスは暗号解読ができなかったと嘘の情報
を流したため,第2次大戦開始時までドイツは暗号解読
の重要性を認識できていなかった.
無線の発達と暗号
• 1894年,イタリアの物理学者グリエルモ・マル
コーニが無線通信を発明
• 1901年,イギリスのポルデュからカナダのニ
ューファンドランドまでの(地平線を超えての)
無線通信に成功.
• 暗号の必要性が高まる.
シェルビウスのエニグマ
1918年
• 暗号円盤:換字式暗号のための円盤
• 別のキーワードを用いて円盤を回転させる
ヴィジュネル暗号にも利用可能
• 文字を打つたびに円盤が回転する換字式暗
号のための機械がエニグマ
ヴィジュネル暗号とは
• 換置式暗号ではあるが,キーによって換置テ
ーブルが変化する.
エニグマは当初全く売れなかった
• 1928年シェルビウスは特許を取得.1機2万ポン
ドでビジネスと軍用に販売を開始したが全く売れ
なかった.
• その後,ドイツ軍はこれまで使用してきた暗号が
破られていたことに気づきエニグマを採用した.
エニグマのエンコード
http://www.bletchleypark.org.uk/content/simulator.html
エニグマのデコード
円盤の初期値が同じであれば,
デコードとエンコードは同じ
•
•
•
•
円盤の初期配置が鍵になる.
各円盤の目盛は26,3枚の組み合わせ=263
円盤の枚数は3枚で,交換可能3!=6通り.
さらに6本のケーブルで6つの文字にスクラン
ブルをかけると26C6*6!
• したがって,暗号化のパターンは263×=
2913496185600通り.
• 正規の受信者が解読する場合にも鍵が必要
であった.
各日で鍵は変わった.(日鍵)
• 前日の日鍵を使って翌日の日鍵を暗号化し
て送った.但し,日鍵が正しく伝わらなければ
全ての通信が無駄になるため,毎朝2回暗号
化して無線送信された.
• さらにメッセージを送る前に各メッセージの暗
号化鍵が2回,日鍵で暗号化され付与されて
いた.
• このルールがスパイによって漏らされ,これを
手掛かりに暗号解読を行うことをポーランド
の暗号解読者レイエフスキーが発見した.
ドイツ軍によるエニグマの運用
送信者
前日の日鍵
今日の日鍵
エニグマによる暗号化
2回送信
受信者
前日の日鍵
暗号化された今日の日鍵
暗号化されたメッセージ
の暗号化鍵
今日の日鍵
2回送信
メッセージの
暗号化鍵
メッセージの
暗号化鍵
暗号化されたメッセージ
メッセージ
メッセージ
レイエフスキの作戦
• 暗号の連鎖を辿ることで日鍵を割り出す.
• メッセージ鍵は3つの鍵の繰り返
しから成る6文字.1番目と4番目
は同じ文字を暗号化したもの.メ
ッセージ鍵から作った下記の1,
4番の対応表があれば,スクラン
ブルが解ける.
• ABCDEFGHIJKLMNOPQRSTUVWXYZ
• FQHPLWOGBMVRXUYCZITNJEASDK
暗号の指紋
• ABCD EFG HI J K LMNOPQRSTUVWXY Z
• FQHPLWOGBMVRX UYC Z I TNJ EA S DK
から,連鎖と連結数を求め,これを手掛かりに
日鍵を求めた.(プラグボードの影響が無い)
A→F→W→A
3
B→Q→Z→K→V→E→L→R→I→B 9
C→H→G→O→Y→D→P→C
7
J→M→X→S→T→N→U→J
7
ボンブ
改造エニグマによる日鍵の探索
• 3つの円盤の並び方は3!=6通り
• 6台のエニグマで並列に263=17576通りの日
鍵を探索する機械をレイエフスキが考案し作
成した.(チェックはメッセージキーの繰り返し
を利用する.)
• 約2時間で日鍵は解読できた.
• これにより,わずかな暗号化方法の変更にも
対応できた.
エニグマの大幅な変更
• 円盤(スクランブラ-)の数が5個になり,これ
らのうちから3つ取り出して使うようになった.
3!=6通りから,5C2×3!=60通りになった.
• プラグボードに接続するケーブルの本数が6
本から10本に増えた.
• 60台の改造エニグマによるボンブの作成は
予算上無理であり,解読は不可能になった.
• 1939年ドイツ軍の侵攻を前に,全ての成果を
イギリスに手渡した.
ブレッチレーパークの暗号解読チーム
GCCS: Government Code and Cipher School1919
• 19世紀の富豪の邸宅内にプレハブ住宅を建
て,数学者,エンジニア,言語学者,クロスワ
ードパズルマニアなどを雇い入れた.ポーラ
ンドよりも予算も人的資源も豊富であったた
め,1940年には改良型エニグマの解読も十
分に行えた.
次の難題に備えて
• 日鍵やメッセージキーの反復が無くなったら
どうするか?
• 暗号と平文の対応関係(クリ
ブ)が分かったとすれば,暗
号解読が行えるのではない
か?
• wetter → ETJWPX だとすれ
ば,どうすればスクランブラ
-の設定を見抜けるか?
クリブの内部ループ
• クリブにはループがある.
電気回路による日鍵の発見
ーボンブー
• 機械による鍵の発見
右図のように回路を
組んで,スクランブラを回転させれば,正し
い日鍵の位置でラン
プが点灯する!
これを様々なスクラン
ブラ-の配置で並列に
運転する.
ローレンツマシーンの登場
• ヒトラーと将軍との通
信用に開発されたより
複雑な暗号化マシー
ン
• ランダムに無関係な
文字を挿入する機能
を持つ
• 円盤の数は12枚
• ボンブでは解読不能
コロッサス(巨人)の誕生
• ボンブは定型的な処理しか行えなかった.
• ローレンツマシーンの解読には統計計算,検
索,照合計算,などが必要であり,汎用な計
算が行える機械が必要であった.
• マックス・ニューマンが,「万能チューリングマ
シン」を実現することを提案,しかしGCCSでは
実現を不可能視していたため,開発は中断.
• 1943年に実現したのは郵政省の研究所から
派遣された技術者トミー・フラワーズであった
.
コロッサス
• 1944年コロッサス
MarkⅠは1500個の真
空管を使い,高速に
動作した.
• 同年 MarkⅡが2400
個の真空管で動作性
能はMarkⅠの5倍.
• 右図は関係者らの証
言から複製されたもの
(9割は正しいらしい)
暗号解読は計算機を生んだ!
• Colossus はローレンツマシンを使って暗号化された
メッセージを解読する際に使われた。Colossus はふ
たつのデータ列を比較し、プログラム可能な論理
演算を行う。
• 一方のデータは紙テープから高速に読み込まれ、
もう一方は内部で生成される。そして、様々な設定
でローレンツマシンのエミュレーションを実行する。
ある設定での演算が所定の閾値を越えると電気式
タイプライタにその結果を出力する。
コロッサスの性能
• 紙テープは毎秒12mの速度で処
理可能.
• 処理できる文字数は毎秒5000
文字
• これは紙テープ中央に穿孔され
た穴を通過するたびにクロック
が生成されていたために生じた
限界である.
• 条件分岐命令はなかった.
コロッサスのその後
• チャーチルは 戦後コロッサスを手のひらより小さ
い破片に破壊するよう命令した.製作者Tommy
Flowers は青写真を燃やした.部品を引き抜き,
Newmanが マンチェスター大学の計算機研究所
に持ち込んだColossus Mark I は後に撤去された.
• しかし,2台の Colossus はGCHQ(旧GCCS)が 1952
年から1954年に移転した後も保管されたが,最後
の1台も1960年に分解された.
• コロッサスの存在は戦後も極秘であり,1970年代
後半まで,その存在は知られていなかった.
コロッサスが秘密にされた理由
• 暗号解読の持つ政治的重要性(再び強力な
暗号生成機構が現れれば,解読に対する投
資が爆発的に増加する)
• 実際にイギリスはエニグマやローレンツマシ
ーンの暗号を解読していたことを隠してきた.
• さらに,戦後ドイツ軍から回収したエニグマを
植民地に配り,通信を行わせ,傍受・解読も
おこなってきた.
コロッサスの特性
• ある計算機あるいはプログラミング言語がチ
ューリングマシンと等価な計算が行えるとき,
「チューリング完全」であるという.
• コロッサスは,チューリング完全ではなかった
ため,正確には計算機とはみなされない.
• 但し,Harvard Mark Iの初期版やコンラッド・ツ
ーゼのZ1,Z2などもチューリング完全ではない
.
チューリング・マシン
チューリングマシンは,
• 無限に長いテープ
• テープに格納された文字を読み書きするヘッド
• 機械の内部状態を記憶するメモリとその遷移機構 (制御部)
で構成され,内部状態とヘッドから読み出した文
字の組み合わせで、次の動作を実行する。
•
•
•
•
ヘッドの位置の情報を読みとる
ヘッドの位置に情報を書き込む
機械の内部状態を変える
ヘッドを右か左に一つ移動する
停止状態になるまでこれを反復して実行し続ける.
Turing Machineのイメージ
チューリング・マシンの意義
• 「計算とは何であるか」を明確に定義
した.
• すなわち,チューリング・マシンで計
算可能なことが「計算できることのす
べて」であることを示した.
• ゲーデルの「自然数論を含む帰納的
に記述可能な公理系の不完全性に
関する定理」によって危機にさらされ
た数学を守るために確固とした計算
の基盤を作りたかったらしい.
レポート課題
• チューリング・マシ
ンは仮想的な機械
であるが,磁気テー
プ,制御部はそれ
ぞれ,現代のコンピ
ュータの何に対応
するか,理由を含
めて説明しなさい.