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