講義スライド



情報セキュリティ
第３回
２０１１年４月２２日（金）

1/23

本日学ぶこと

暗号系（暗号システム，Cryptosystem）の基本



安全性を脅かすもの
暗号・復号・解読
歴史的な暗号アルゴリズム
 情報が増えれば解読しやすくなる実例
2
安全性を脅かすもの







盗聴（eavesdropping, wiretapping, intersection）
なりすまし（成り済まし，spoofing, impersonating,
masquerading）
改ざん（改竄，中間者攻撃，interpolation,
man-in-the-middle attack）
偽造（forgery）
DoS攻撃（Denial of Service attack）
DDoS攻撃（Distributed Denial of Service attack）
リプレイ攻撃（再生攻撃，再送攻撃，replay attack）
3
盗聴
送信
受信
敵
機密性を脅かす
4
なりすまし・偽造
送信
受信
敵
完全性を脅かす
なりすましにはユーザ認証，偽造にはメッセージ認証
5
改ざん
送信
受信
敵
完全性を脅かす
6
DoS攻撃
送信
受信
敵
可用性を脅かす
7
DDoS攻撃
敵
敵
送信
受信
敵
敵
敵
可用性を脅かす
8
リプレイ攻撃
送信
受信
敵
完全性を脅かす
9
暗号系と暗号アルゴリズム

暗号系とは


暗号アルゴリズムとは



メッセージを暗号化して送り復号して元の平文が得られるまで
の一連の流れ（システム）
暗号化や復号の具体的な方法（アルゴリズム）
機密性を実現する技術の一つ
用語


暗号化の対象となる情報（文字列，数値列またはバイト列）を
「平文」と書き，「ひらぶん」という．
「暗号化」の対義語は「復号」だが，「復号化」と書かれることも
ある．
10
暗号系
平文
暗号化
平文
暗号
化鍵
復号
鍵
復号
盗聴可能な
通信路
暗号文
暗号文
11
暗号アルゴリズムにおける鍵の役割

暗号アルゴリズムは公開されている


暗号アルゴリズムは簡単に変更できない


自分だけでなく，通信相手すべてがしなければならない
鍵は秘密に管理する


公開・検証されていない暗号アルゴリズムを使うのは「隠すこと
によるセキュリティ」の典型例であり，解読されやすい
たった56～2048bitでも，これが生命線
鍵は交換・破棄可能

PKIでは，鍵の作成・配信・破棄などの手続きが定められている
12
暗号化・復号の数式表現

対称暗号（共通鍵暗号） ［暗号化鍵＝復号鍵］ M: message



C = e(K, M)
M = d(K, C) = d(K, e(K, M))
公開鍵暗号 ［暗号化鍵≠復号鍵］



暗号化
復号
暗号化
復号
K: key
C: ciphertext
Kpub:暗号化鍵 =公開鍵
Kpri:復号鍵=非公開鍵
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をはじめ，多くのシンプルな暗号アルゴリズムで
成立する．
13
暗号解読(cryptanalysis)の分類

目標は？



暗号文に対応する平文を獲得すること
暗号化に使われている鍵を獲得すること
方法は？



暗号文単独攻撃（ciphertext-only attack）
 与えられた暗号文のみから，平文や鍵を獲得する
既知平文攻撃（known-plaintext attack）
 与えられた平文と暗号文のペアから，鍵を獲得する
選択平文攻撃（chosen-plaintext attack）
 解読者が平文と暗号文を選ぶことができ，
その情報から鍵を獲得する
14
平文を構成する文字


「メッセージを，暗号化できる形に変換すること」「復号，解読
された値を，読むことのできる形にすること」も必要
よく用いられる文字の種類



古典暗号：平文を英小文字，暗号文を英大文字で構成し，
数字や記号は用いない
DES，AESなど：ビット列
RSAなど：非負整数値
wagahaihanekodearu
吾輩は猫である
送りたい
情報
字種の
変換
平文
（暗号化）
15
歴史上の暗号（古典暗号）

換字式暗号




「換字」は
「かんじ」ではなく
「かえじ」という
シーザー暗号（各文字をずらす）
 wagahai ⇒ ZDJDKDL
単一換字暗号（各文字を換字表で変換する）
 wagahai ⇒ PQAQHQD
ヴィジュネル暗号（平文と鍵の各文字を足し合わせる）
 wagahai ⇒ YOJEJOL
転置式暗号

2文字単位で入れ替える
 wagahai ⇒ AWAGAHI
16
換字表の例




シーザー暗号（wagahai⇒ZDJDKDL）
平文
文字
a
b
c
…
y
z
暗号文
文字
D
E
F
…
A
B
単一換字暗号（wagahai⇒PQAQHQD）
平文
文字
w
a
g
h
i
…
暗号文
文字
P
Q
A
H
D
…
換字は写像（全単射）
逆写像は復号法 ⇒ 換字表を特定することが「解読」
17
sedコマンドを用いた単一換字暗号の処理


シーザー暗号・単一換字暗号は，プログラムを作らなくても，
sedコマンドで実現できる．
暗号化の例


復号の例


echo wagahai | sed -e y/waghi/PQAHD/
echo PQAQHQD | sed -e y/PQAHD/waghi/
書式




echo 平文 | sed -e y/平文アルファベット/暗号文アルファベット/
cat 平文ファイル| sed -e y/平文アルファベット/暗号文アルファベット/
echo 暗号文 | sed -e y/暗号文アルファベット/平文アルファベット/
cat 暗号文ファイル| sed -e y/暗号文アルファベット/平文アルファベット/
18
鍵空間のサイズ

前提


シーザー暗号



平文として使用する文字（アルファベット）は英小文字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)
19
歴史上の暗号に対する攻撃方法



シーザー暗号には，ブルート・フォース・アタック（総当たり
法）が使える
単一換字暗号ほかに対しては，言語の統計的性質を用いる
頻度分析


英字では「e」が最も多く出現する ⇒ 単一換字暗号の暗号文で，
最も頻度の高い文字を「e」と仮定したら？
「the」「あい」といった，連続する文字の並び（N-gram）の共起
頻度なども求められ（てい）る
20
歴史上の暗号から学ぶこと

暗号文が多いほど，解読・理解のための手がかりを与える



応用例：顔を覚える，未知語を理解する
一つの「情報」だけで物事を判断しない
 同種の情報を集め，比較して判断する
鍵空間が大きいからといって，安全であるとは限らない
21
本日のまとめテスト

資料を見ることなく，以下の文章を読んで下線部を訂正しな
さい．一つだけ，訂正してはいけないものがある．




なりすまし，改ざん，偽造，DDoS攻撃はいずれも，完全性を脅
かす行為である．
公開・検証されていない暗号アルゴリズムを使うのは，安全な
セキュリティの典型例である．
暗号解読の目標には，平文を求める以外に，鍵を求めることも
挙げられる．
単一換字暗号は，現代暗号の一つである．
22
今後の予定




４月２９日（金）：昭和の日のため授業なし
５月６日（金）：出張のため休講
５月１３日（金）：第４回授業
補講は６月ごろ，別の曜日・時限で，A601にて実施する予定
です．改めて連絡します．
23E