暗号通信

暗号の歴史

• 参考書：「暗号解読（上・下）」サイモン・シン 著 青木薫 訳（新潮文庫）
• ウィキペディア 暗号史

スキュタレー暗号

• スキュタレー＝木製の巻き軸
• ひも状の革を巻き付けて、文書を書く
• 革ひもをほどいて（ベルトのようにみせかけて）伝令が運ぶ
• 受け取った革ひもをスキュタレーに巻き付けて読む
• 紀元前５世紀、スパルタ（対ペルシャ）

スキュタレー

転置式暗号

• 文書に書いた文字の順番を変える
• スキュタレー暗号
• レールフェンス暗号
  • 上段、下段に交互に文字を書く

解いてみよう

• しおろてやがぎみさつんいかたら
  • しろやぎさんからおてがみついた
• くさよたろんまべやたずたぎらに
• わみいうびつたみのみきかしはみのをしのかみひなむ

シーザー暗号

• 『ガリア戦記』
• ABCDEF... -> DEFGHI...
• 敵に包囲されて降伏寸前の味方に、伝令を送った
• 槍に手紙を付けて投げ込んだ
• 「すぐに行くからがんばれ！」
  • （こんなものでも暗号にするんですね）

換字式暗号

• 平文の各文字を別の文字で置き換える
• シーザー暗号は 3文字ずらす
• ずらす数を変えれば 25通りの暗号ができる
• どのように置き換えてもよければ 26! 通り
  • 26! = 403,291,461,126,605,635,584,000,000

解いてみよう

• （以下はシーザー暗号 ずらした文字数は 6以下）
• ERBV EH DPELWLRXV
  • BOYS BE AMBITIOUS (3)
• YNRJ NX RTSJD
  (5)

暗号の方式と鍵

• スキュタレー暗号 ... 何文字で一周するスキュタレーを使うか
• シーザー暗号 ... 何文字ずらすか
• シーザー暗号に 限らない 換字式暗号なら、鍵が 400x1兆x1兆 (四百しorじょ:禾扁に予)
• 総当たりでは解けない

換字式暗号の鍵

• 鍵の作り方（例）
• "Yes we can" -> YESWCAN + N の次から
• ABCDEFGHIJKLMNOPQRSTUVWXYZ =>
• YESWCANOPQRTUVXZBDFGHIJKLM

暗号化の例

• There is not a black America and a white America, there's the United States of America
• =>
• GOCDC PF VXG Y ETYSR YUCDPSY YVW Y JOPGC YUCDPSY GOCDCF GOC HVPGCW FGYGCF XA YUCDPSY

換字式暗号を解く

• イスラム帝国アッバース朝（750-1258）
• 暗号通信を多用
• 暗号解読技術も発達
• 400x1兆x1兆 もの総当たりは不可能
• 文字の出現頻度を調べる
  • ETAOIN SHRDLU

英語の文字出現頻度

もっと難しい暗号へ

• ルイ14世の大暗号
• ヴィジュネル暗号
• エニグマ

ルイ14世の大暗号

• ロシニョール父子 (1600年代)
• 字を単位にではなく、音節（対字）を単位にする
• 字に換えるのでなく、数字（３桁）に換える
  • 124-22-125-46-345 => les en-ne-mi-s (敵)
• バズリー (1890年頃) 解読に成功
  • 「鉄仮面」の秘密(?)

ヴィジュネル暗号

• ヴィジュネル方陣
• 

ヴィジュネル暗号の例

• 鍵を KING とすると
• KIN GK ING KINGKIN GK
• but he has nothing on (でも、なんにも着てないよ)
• LCG NO PNY XWGNSVT UX

ヴィジュネル暗号の解読法

• チャールズ・バベッジ
  • 「階差機関」を設計、「解析機関」を構想（今日の計算機の原型）
• 繰り返し現れる文字列に注目
• その文字数から「鍵」の長さを推定
• 鍵の文字毎に暗号文中の文字の頻度分布をみる

教訓

• 暗号文が長い (長い間同じ鍵を使う) と解読しやすい
• 鍵を長く／乱雑な文字列にすると解読できない
  • が、実用的でない
• -> 暗号を作る機械の発明

エニグマ

• 第二次世界大戦 (1939-1945) ドイツ軍で使用
• 

エニグマの機構

• スイッチ -> ローター（換字盤） -> リフレクター -> ローター -> ランプ（文字表示）
• ローターは 1文字毎に回転
• リフレクターはプラグボード（配線を変えられる）
• ローターの種類・初期位置、プラグボードの配線が鍵

エニグマの機構（図）

使い方 (ドイツ軍の)

• 日ごとに鍵を決めておく (日鍵)
• メッセージ毎にローターの初期位置を変える (メッセージ鍵)
• メッセージ鍵を日鍵を使って送る
• 鍵が合っていることを確かめる ... 最初に 3文字x2回の繰り返し

エニグマ暗号の解読

• 換字式 400x兆x兆
• ローター(3個)がわかれば
  • ローターの順 = 3! = 6
  • 各ローターの初期位置の組み合わせ = 26x26x26 =17576

エニグマ暗号の解読

• マリヤン・レイェフスキ (ポーランド)
• アラン・チューリング (イギリス)
• 鍵を見つけるための機械 (計算機) Bombe(a)
• スパイを泳がせニセ情報
• コードブックを奪取 (Uボート を捕獲)

現代の暗号

• 電子計算機が誰でも使える
• 共通鍵暗号と公開鍵暗号
• 文字種を多くする
• 26 文字 -> 鍵の数は最大 400x兆x兆 個
  • 鍵の決め方で制限される
• DES 暗号 = 56bit = 8文字分
• 2⁵⁶ = 72,057,594,037,927,936 種類の文字 -> 鍵の最大数はその階乗
  • 実際には印字できる文字(94)が8文字 = 94⁸ = 6,095,689,385,410,816

暗号の歴史のまとめ

• 暗号には「方式」と「鍵」がある
• 使える鍵の数が多いと、破られにくい
• 同じ鍵を使い続けると、破られやすくなる
  • One Time Pad (乱数で生成) を使う方法もある
• 暗号化、解読の道具の進化
• 数学（統計）-> 機械 -> 計算機 共通鍵暗号と公開鍵暗号
• 共通鍵は、鍵の持ち運びに問題