コンピュータの歴史－２ 戦時期における暗号解読 和田俊和

最近の CPU (ARM の一種 ) Nvidia 社製 Tegra 3 の省電力技術 「 4-PLUS-1 」 メインである 4 つのコア に加え、低性能・低消費電力のコンパ ニオンコアを状況に応じて活用する技 術。 – 端末のパフォーマンスが必要なときは 4 つのコアから必要な数のコアを使い、不 要なときは低消費電力のコンパニオンコ アだけで動作して全体の消費電力を削減 する。ビデオ再生時では最大 61% 、 Web 閲覧では最大 30% の消費電力の削減が可 能。

これは一般人の常識レベルの知識

低性能・低消費電力のコンパニオンコ ア

戦時中最も計算を必要としたの は 兵器開発ではなく，暗号解読だ った ドイツは第一次世界大戦 (1914 〜 1918) 勃発後にアメ リカ駐在のドイツ大使に暗号の電文を送っていた ． – メキシコに資金を提供し，参戦を躊躇していたアメリカ 南部を攻撃し，州を奪還するように要求させ，さらにメ キシコ経由で日本にアメリカ西岸を攻撃させるよう，メ キシコ政府とコンタクトを取れという内容 この電文をイギリスは傍受・解読し，内容をアメ リカ側に伝え，アメリカは参戦し，ドイツは敗北 しかし，イギリスは暗号解読ができなかったと嘘 の情報を流したため，第 2 次大戦開始時までドイツ は暗号解読の重要性を認識できていなかった．

無線の発達と暗号 1894 年，イタリアの物理学者グリエルモ ・マルコーニが無線通信を発明 1901 年，イギリスのポルデュからカナダ のニューファンドランドまでの（地平線 を超えての）無線通信に成功． 暗号の必要性が高まる．

シェルビウスのエニグマ 1918 年 暗号円盤：換字式暗号のための円盤 別のキーワードを用いて円盤を回転させ るヴィジュネル暗号にも利用可能 文字を打つたびに円盤が回転する換字式 暗号のための機械がエニグマ

ヴィジュネル暗号とは 換置式暗号ではあるが，キーによって換 置テーブルが変化する．

エニグマは当初全く売れなかっ た 1928 年シェルビウスは特許を取得． 1 機 2 万ポ ンドでビジネスと軍用に販売を開始したが全 く売れなかった． その後，ドイツ軍はこれまで使用してきた暗 号が破られていたことに気づきエニグマを採 用した．

エニグマのエンコード

エニグマのデコード

円盤の初期値が同じであれば， デコードとエンコードは同じ 円盤の初期配置が鍵になる． 各円盤の目盛は 26 ， 3 枚の組み合わせ＝ 26 3 円盤の枚数は 3 枚で，交換可能 3! ＝ 6 通り． さらに 6 本のケーブルで６つの文字にスク ランブルをかけると 26 C 6 *6! したがって，暗号化のパターンは 26 3 ×= 通り． 正規の受信者が解読する場合にも鍵が必 要であった．

各日で鍵は変わった．（日鍵） 前日の日鍵を使って翌日の日鍵を暗号化 して送った．但し，日鍵が正しく伝わら なければ全ての通信が無駄になるため， 毎朝 2 回暗号化して無線送信された． さらにメッセージを送る前に各メッセー ジの暗号化鍵が 2 回，日鍵で暗号化され付 与されていた． このルールがスパイによって漏らされ， これを手掛かりに暗号解読を行うことを ポーランドの暗号解読者レイエフスキー が発見した．

ドイツ軍によるエニグマの運用 送信者 エニグマによる暗号化 受信者 前日の日鍵 今日の日鍵 暗号化された今日の日 鍵 前日の日鍵 メッセージの 暗号化鍵 暗号化されたメッセー ジの暗号化鍵 メッセージの 暗号化鍵 メッセージ 暗号化されたメッセー ジ メッセージ 2 回送信

レイエフスキの作戦 暗号の連鎖を辿ることで日鍵を割り出す ． メッセージ鍵は 3 つの鍵の繰り 返しから成る 6 文字． 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

ボンブ 改造エニグマによる日鍵の探索 ３つの円盤の並び方は３！＝６通り ６台のエニグマで並列に 26 3 ＝ 通りの 日鍵を探索する機械をレイエフスキが考 案し作成した．（チェックはメッセージ キーの繰り返しを利用する．） 約 2 時間で日鍵は解読できた． これにより，わずかな暗号化方法の変更 にも対応できた．

エニグマの大幅な変更 円盤（スクランブラ－）の数が 5 個になり ，これらのうちから 3 つ取り出して使うよ うになった． 3! ＝ 6 通りから， 5 C 2 ×3! ＝ 60 通りになった． プラグボードに接続するケーブルの本数 が 6 本から 10 本に増えた． 60 台の改造エニグマによるボンブの作成 は予算上無理であり，解読は不可能にな った． 1939 年ドイツ軍の侵攻を前に，全ての成 果をイギリスに手渡した．

ブレッチレーパークの暗号解読チー ム GCCS: Government Code and Cipher School 世紀の富豪の邸宅内にプレハブ住宅を 建て，数学者，エンジニア，言語学者， クロスワードパズルマニアなどを雇い入 れた．ポーランドよりも予算も人的資源 も豊富であったため， 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 のイメージ

チューリング・マシンの意義 「計算とは何であるか」を明確に 定義した． すなわち，チューリング・マシン で計算可能なことが「計算できる ことのすべて」であることを示し た． ゲーデルの「自然数論を含む帰納 的に記述可能な公理系の不完全性 に関する定理」によって危機にさ らされた数学を守るために確固と した計算の基盤を作りたかった らし い ．

レポート課題 チューリング・マ シンは仮想的な機 械であるが，磁気 テープ，制御部は それぞれ，現代の コンピュータの何 に対応するか，理 由を含めて説明し なさい．