情報セキュリティ: 2007年4月27日

q
q
情報セキュリティ
第３回：２００７年４月２７日（金）
q
q
本日学ぶこと

暗号系（暗号システム，Cryptosystem）の基本
q
q
q
安全性を脅かすもの
暗号・復号・解読
歴史的な暗号アルゴリズム
 情報が増えれば解読しやすくなる実例
2
安全性を脅かすもの






盗聴（eavesdropping, wiretapping, intersection）
なりすまし（成り済まし，spoofing, impersonating,
masquerading）
改ざん（改竄，interpolation，man-in-the-middle attack）
偽造（forgery）
DOS攻撃（Denial of Service attack）
リプレイ攻撃（再生攻撃，再送攻撃，replay attack）
3
盗聴
送信
受信
敵
機密性を脅かす
4
なりすまし・偽造
送信
受信
敵
完全性を脅かす
なりすましにはユーザ認証，偽造にはメッセージ認証
5
改ざん
送信
受信
敵
完全性を脅かす
6
DOS攻撃
送信
受信
敵
可用性を脅かす
複数の敵が一斉に攻撃すれば，DDOS攻撃
7
リプレイ攻撃
送信
受信
敵
完全性を脅かす
8
暗号系と暗号アルゴリズム

暗号系とは
q

暗号アルゴリズムとは
q

メッセージを暗号化して送り復号して元の平文が得られるまで
の一連の流れ（システム）
暗号化や復号の具体的な方法（アルゴリズム）
用語
q
q
暗号化の対象となるメッセージを「平文」と書き，「ひらぶん」とい
う．
「暗号化」の対義語は「復号」だが，「復号化」と書かれることも
ある．
9
暗号系
平文
暗号化
平文
暗号
化鍵
復号
鍵
復号
盗聴可能な
通信路
暗号文
暗号文
10
暗号アルゴリズムにおける鍵の役割

暗号アルゴリズムは公開されている
q

暗号アルゴリズムは簡単に変更できない
q

自分だけでなく，通信相手すべてがしなければならない
鍵は秘密に管理する
q

公開・検証されていない暗号アルゴリズムを使うのは「隠すこと
によるセキュリティ」の典型例であり，解読されやすい
たった56～2048bitでも，これが生命線
鍵は交換・破棄可能
q
PKIでは，鍵の作成・配信・破棄などの手続きが定められている
11
暗号化と復号の数式表現

対称暗号（共通鍵暗号）［暗号化鍵＝復号鍵］ M: message
q
q

C = e(K, M)
M = d(K, C) = d(K, e(K, M))
公開鍵暗号［暗号化鍵≠復号鍵］
q
q

暗号化
復号
暗号化
復号
K: key
C: ciphertext
Kpub:暗号化鍵 =公開
鍵
Kpri:復号鍵=非公開鍵
C = e(Kpub, M)
M = d(Kpri, C) = d(Kpri, e(Kpub, M))
復号したのち暗号化したら？
q
M = e(K, d(K, M)) や M = e(Kpub, d(Kpri, M)) は
 一般には成立しない．
 しかしRSAをはじめ，多くのシンプルな暗号アルゴリズムで
成立する．
12
暗号解読の分類

目標は？
q
q

暗号文に対応する平文を獲得すること
暗号化に使われている鍵を獲得すること
方法は？
q
q
q
暗号文のみ（ciphertext-only attack）
 与えられた暗号文のみから，平文や鍵を獲得する
既知平文攻撃（known-plaintext attack）
 与えられた平文と暗号文のペアから，鍵を獲得する
選択平文攻撃（chosen-plaintext attack）
 解読者が平文と暗号文を選ぶことができ，
その情報から鍵を獲得する
13
エンコードとは

メッセージを，暗号化できる形に変換すること
q

復号，解読された情報を読める形にするのは「デコード」
よく用いられるエンコードの種類
q
q
q
古典暗号：平文を英小文字，暗号文を英大文字で構成し，
数字や記号は用いない
DES，AESなど：ビット列
RSAなど：非負整数値
送りたい
情報
エンコード
平文
（暗号化）
14
歴史上の暗号（古典暗号）

換字式暗号
q
q
q

「換字」は
「かんじ」ではなく
「かえじ」という
シーザー暗号（各文字をずらす）
 wagahai ⇒ ZDJDKDL
単一換字暗号（各文字を換字表で変換する）
 wagahai ⇒ PQAQHQD
ヴィジュネル暗号（平文と鍵の各文字を足し合わせる）
 wagahai ⇒ YOJEJOL
転置式暗号
q
2文字単位で入れ替える
 wagahai ⇒ AWAGAHI
15
sedコマンドを用いた単一換字暗号の処理


シーザー暗号・単一換字暗号は，プログラムを作らなくても，
sedコマンドで実現できる．
暗号化の例
q

復号の例
q

echo wagahai | sed -e y/waghi/PQAHD/
echo PQAQHQD | sed -e y/PQAHD/waghi/
書式
q
q
echo 平文 | sed -e y/平文アルファベット/暗号文アルファベット/
echo 暗号文 | sed -e y/暗号文アルファベット/平文アルファベット/
16
鍵空間のサイズ

前提
q

シーザー暗号
q
q

平文として使用する文字（アルファベット）は英小文字26種類
鍵は，1文字ずらす（a⇒B，b⇒C，…z⇒A），2文字ずらす，…，
26文字ずらす（a⇒A），のいずれか
鍵空間のサイズは26
 アルファベットがn文字であれば，n
単一換字暗号
q
q
aをA～Zのどれかに割り当て，bをその残りのどれかに割り当て
…として換字表ができる．
鍵空間のサイズは26×25×…×1 = 26! = 4.03×1026
 アルファベットがn文字であれば，n! (>2n)
17
歴史上の暗号に対する攻撃方法


言語の統計的性質を用いる
頻度分析
q
q
英字では「e」が最も多く出現する ⇒ 単一換字暗号の暗号文で，
最も頻度の高い文字を「e」と仮定したら？
「the」「あい」といった，連続する文字の並び（N-gram）の共起
頻度なども求められ（てい）る
18
歴史上の暗号から学ぶこと

暗号文が多いほど，解読・理解のための手がかりを与える
q
q

応用例：顔を覚える，未知語を理解する
一つの「情報」だけで物事を判断しない
 同種の情報を集め，比較して判断する
鍵空間が大きいからといって，安全であるとは限らない
19
第１回レポート課題

以下の暗号文を解読しなさい．
PQFBGXEBTGAHQTYTJXTUTHTPXHEAFAPTHPSAAHXYS
QAEXUTPBHHXHJBEAZXOQYTFQHUBYYXTGTOTYARQOX
OQYYBTYXJXPXHBDXHXFTOXEBHZQUQHUTPXOQETFBO
XEBHZXUTYAGXTOXSAAFSQPAHXFAGXHEBTGAJXHYXT
ZXXYYBJXTPXYASXPARQGXUTOBYBTOXEAPQHQGTOTY
AJXHYXTHQGQHDAGXESXHGXTXYXFTHTXFAYQOTBEQH
QGQHDAPXFXOXTHTYTHQZQYQPAUSQAGQASXETFBTZX
PTOXEAZXEQHQYAAETHGXGTOTYAGQAETPTHQOAEBHJ
BHETHJBXYYBOQYTFQHXHZQARQYAPXYYBTOXEAJBEA
PXFXGAYAAHQUSAETHPTJBAPBSQAYQETYBOQGTOTYA
GQAETPTJXPXFXGAYAAHQUSAETHPTJBGXGXTFXHXTE
QHQABGAZQAGXXHZQAJXPXFXYXYQBNQCSZXOTYAPXY
YBOQEQHQHXTSQAZXYQPBHXTPQATAGAAHTHTUSAAHQ
GTOTYADQAZSQRQPQPQFQOTYBTOXEAQRXPXFTJBEAP
XHX
20
第１回レポート課題

レポートに記載するもの
q
q
q
q
q
科目名，「第１回レポート」，学籍番号，氏名，提出年月日
解読の結果（もとの平文）
頻度表（暗号文中のどの文字が何回出現しているか）
変換表
 「A→p, B→f…」の形式，または，復号のsedコマンド
 変換表はアルファベット順ではなく，対応を見つけた順で書く
こと
原文（分かれば）
21
第１回レポート課題

提出方法
q
q
q

次回授業（５月１１日）の授業開始時に提出すること．
A4用紙に打ち出すこと．（１枚で収まるはず．）
 手書きは減点する．
コピーが疑われる答案があれば，メールで問い合わせるかも．
暗号文に関する補足
q
q
q
暗号文は，ある日本語の会話文（一人の発言）をローマ字に変
換してから，単一換字暗号により暗号化したもの
訓令式ローマ字を採用している．平文には，１箇所だけ英単語
が含まれている．
暗号文のテキストファイルは
 http://www.wakayama-u.ac.jp/~takehiko/secu2007/
20070427-cipher.txt
22

Download Report