q q 情報セキュリティ 第３回：２００７年４月２７日（金） q q

本日学ぶこと 暗号系（暗号システム，Cryptosystem）の基本 安全性を脅かすもの 暗号・復号・解読 歴史的な暗号アルゴリズム 情報が増えれば解読しやすくなる実例

安全性を脅かすもの 盗聴（eavesdropping, wiretapping, intersection） なりすまし（成り済まし，spoofing, impersonating, masquerading） 改ざん（改竄，interpolation，man-in-the-middle attack） 偽造（forgery） DOS攻撃（Denial of Service attack） リプレイ攻撃（再生攻撃，再送攻撃，replay attack）

盗聴 送信 受信 敵 機密性を脅かす 波多浩昭「原理から学ぶネットワークセキュリティ 第2回 情報秘匿のための共有鍵暗号」 波多浩昭「原理から学ぶネットワークセキュリティ　第2回　情報秘匿のための共有鍵暗号」 日経Linux 2007年5月号，p.146の図1を一部改変 機密性を脅かす

なりすまし・偽造 送信 受信 敵 完全性を脅かす なりすましにはユーザ認証，偽造にはメッセージ認証

改ざん 送信 受信 敵 完全性を脅かす

DOS攻撃 送信 受信 敵 可用性を脅かす 複数の敵が一斉に攻撃すれば，DDOS攻撃 DDOS = Distributed Denial of Service 可用性を脅かす 複数の敵が一斉に攻撃すれば，DDOS攻撃

リプレイ攻撃 送信 受信 敵 完全性を脅かす

暗号系と暗号アルゴリズム 暗号系とは 暗号アルゴリズムとは 用語 メッセージを暗号化して送り復号して元の平文が得られるまでの一連の流れ（システム） 暗号アルゴリズムとは 暗号化や復号の具体的な方法（アルゴリズム） 用語 暗号化の対象となるメッセージを「平文」と書き，「ひらぶん」という． 「暗号化」の対義語は「復号」だが，「復号化」と書かれることもある．

暗号系 平文 平文 暗号化 暗号 化鍵 復号 鍵 復号 盗聴可能な 通信路 暗号文 暗号文

暗号アルゴリズムにおける鍵の役割 暗号アルゴリズムは公開されている 暗号アルゴリズムは簡単に変更できない 鍵は秘密に管理する 公開・検証されていない暗号アルゴリズムを使うのは「隠すことによるセキュリティ」の典型例であり，解読されやすい 暗号アルゴリズムは簡単に変更できない 自分だけでなく，通信相手すべてがしなければならない 鍵は秘密に管理する たった56～2048bitでも，これが生命線 鍵は交換・破棄可能 PKIでは，鍵の作成・配信・破棄などの手続きが定められている

暗号化と復号の数式表現 対称暗号（共通鍵暗号） ［暗号化鍵＝復号鍵］ 公開鍵暗号 ［暗号化鍵≠復号鍵］ 復号したのち暗号化したら？ 暗号化 C = e(K, M) 復号 M = d(K, C) = d(K, e(K, M)) 公開鍵暗号 ［暗号化鍵≠復号鍵］ 暗号化 C = e(Kpub, M) 復号 M = d(Kpri, C) = d(Kpri, e(Kpub, M)) 復号したのち暗号化したら？ M = e(K, d(K, M)) や M = e(Kpub, d(Kpri, M)) は 一般には成立しない． しかしRSAをはじめ，多くのシンプルな暗号アルゴリズムで成立する． M: message K: key C: ciphertext Kpub:暗号化鍵 =公開鍵 Kpri:復号鍵=非公開鍵

暗号解読の分類 目標は？ 方法は？ 暗号文に対応する平文を獲得すること 暗号化に使われている鍵を獲得すること 暗号文のみ（ciphertext-only attack） 与えられた暗号文のみから，平文や鍵を獲得する 既知平文攻撃（known-plaintext attack） 与えられた平文と暗号文のペアから，鍵を獲得する 選択平文攻撃（chosen-plaintext attack） 解読者が平文と暗号文を選ぶことができ， その情報から鍵を獲得する 池野信一，小山謙二『現代暗号理論』，電子情報通信学会，pp.3-4

送りたい 情報 平文 エンコードとは メッセージを，暗号化できる形に変換すること よく用いられるエンコードの種類 エンコード 復号，解読された情報を読める形にするのは「デコード」 よく用いられるエンコードの種類 古典暗号：平文を英小文字，暗号文を英大文字で構成し， 数字や記号は用いない DES，AESなど：ビット列 RSAなど：非負整数値 送りたい 情報 平文 エンコード （暗号化）

歴史上の暗号（古典暗号） 換字式暗号 転置式暗号 シーザー暗号（各文字をずらす） wagahai ⇒ ZDJDKDL 単一換字暗号（各文字を換字表で変換する） wagahai ⇒ PQAQHQD ヴィジュネル暗号（平文と鍵の各文字を足し合わせる） wagahai ⇒ YOJEJOL 転置式暗号 2文字単位で入れ替える wagahai ⇒ AWAGAHI 「換字」は 「かんじ」ではなく 「かえじ」という http://ja.wikipedia.org/wiki/%E6%8F%9B%E5%AD%97%E5%BC%8F%E6%9A%97%E5%8F%B7 http://ja.wikipedia.org/wiki/%E3%83%B4%E3%82%A3%E3%82%B8%E3%83%A5%E3%83%8D%E3%83%AB%E6%9A%97%E5%8F%B7 http://ja.wikipedia.org/wiki/%E8%BB%A2%E7%BD%AE%E5%BC%8F%E6%9A%97%E5%8F%B7 ヴィジュネル暗号例の鍵は「code」

sedコマンドを用いた単一換字暗号の処理 暗号化の例 echo wagahai | sed -e y/waghi/PQAHD/ 復号の例 echo PQAQHQD | sed -e y/PQAHD/waghi/ 書式 echo 平文 | sed -e y/平文アルファベット/暗号文アルファベット/ echo 暗号文 | sed -e y/暗号文アルファベット/平文アルファベット/ http://www.linux.or.jp/JM/html/GNU_sed/man1/sed.1.html http://www.wakayama-u.ac.jp/~takehiko/secu2006/20060428/sed.html

鍵空間のサイズ 前提 シーザー暗号 単一換字暗号 平文として使用する文字（アルファベット）は英小文字26種類 鍵は，1文字ずらす（a⇒B，b⇒C，…z⇒A），2文字ずらす，…，26文字ずらす（a⇒A），のいずれか 鍵空間のサイズは26 アルファベットがn文字であれば，n 単一換字暗号 aをA～Zのどれかに割り当て，bをその残りのどれかに割り当て…として換字表ができる． 鍵空間のサイズは26×25×…×1 = 26! = 4.03×1026 アルファベットがn文字であれば，n! (>2n)

歴史上の暗号に対する攻撃方法 言語の統計的性質を用いる 頻度分析 英字では「e」が最も多く出現する ⇒ 単一換字暗号の暗号文で，最も頻度の高い文字を「e」と仮定したら？ 「the」「あい」といった，連続する文字の並び（N-gram）の共起頻度なども求められ（てい）る http://www7.plala.or.jp/dvorakjp/hinshutu.htm 「生起頻度」は件数， 「生起確率」は割合（全生起確率を足せば１）

歴史上の暗号から学ぶこと 暗号文が多いほど，解読・理解のための手がかりを与える 鍵空間が大きいからといって，安全であるとは限らない 応用例：顔を覚える，未知語を理解する 一つの「情報」だけで物事を判断しない 同種の情報を集め，比較して判断する 鍵空間が大きいからといって，安全であるとは限らない

第１回レポート課題 以下の暗号文を解読しなさい． PQFBGXEBTGAHQTYTJXTUTHTPXHEAFAPTHPSAAHXYS QAEXUTPBHHXHJBEAZXOQYTFQHUBYYXTGTOTYARQOX OQYYBTYXJXPXHBDXHXFTOXEBHZQUQHUTPXOQETFBO XEBHZXUTYAGXTOXSAAFSQPAHXFAGXHEBTGAJXHYXT ZXXYYBJXTPXYASXPARQGXUTOBYBTOXEAPQHQGTOTY AJXHYXTHQGQHDAGXESXHGXTXYXFTHTXFAYQOTBEQH QGQHDAPXFXOXTHTYTHQZQYQPAUSQAGQASXETFBTZX PTOXEAZXEQHQYAAETHGXGTOTYAGQAETPTHQOAEBHJ BHETHJBXYYBOQYTFQHXHZQARQYAPXYYBTOXEAJBEA PXFXGAYAAHQUSAETHPTJBAPBSQAYQETYBOQGTOTYA GQAETPTJXPXFXGAYAAHQUSAETHPTJBGXGXTFXHXTE QHQABGAZQAGXXHZQAJXPXFXYXYQBNQCSZXOTYAPXY YBOQEQHQHXTSQAZXYQPBHXTPQATAGAAHTHTUSAAHQ GTOTYADQAZSQRQPQPQFQOTYBTOXEAQRXPXFTJBEAP XHX

第１回レポート課題 レポートに記載するもの 科目名，「第１回レポート」，学籍番号，氏名，提出年月日 解読の結果（もとの平文） 頻度表（暗号文中のどの文字が何回出現しているか） 変換表 「A→p, B→f…」の形式，または，復号のsedコマンド 変換表はアルファベット順ではなく，対応を見つけた順で書くこと 原文（分かれば）

第１回レポート課題 提出方法 暗号文に関する補足 次回授業（５月１１日）の授業開始時に提出すること． A4用紙に打ち出すこと．（１枚で収まるはず．） 手書きは減点する． コピーが疑われる答案があれば，メールで問い合わせるかも． 暗号文に関する補足 暗号文は，ある日本語の会話文（一人の発言）をローマ字に変換してから，単一換字暗号により暗号化したもの 訓令式ローマ字を採用している．平文には，１箇所だけ英単語が含まれている． 暗号文のテキストファイルは http://www.wakayama-u.ac.jp/~takehiko/secu2007/ 20070427-cipher.txt