Title of presentation: 32 pt Arial

情報セキュリティ特論（1）
黒澤馨（茨城大学）
[email protected]
2015/9/30
confidential
1
教科書・参考書
現代暗号への招待：
黒澤馨 (著),
サイエンス社
現代暗号の基礎数理
黒澤馨、尾形わかは（著）
電子情報通信学会編（コロナ社）
2015/9/30
confidential
2
講義内容
• 暗号の歴史
• 確率
• メッセージ認証コード
2015/9/30
confidential
3
暗号の歴史
• シーザー暗号から公開鍵暗号まで
2015/9/30
confidential
4
暗号
•従来：
軍事・外交
•現在：
ビジネス、個人のプライバシ
2015/9/30
confidential
5
シーザー暗号（１）
•（平文）
ＨＡＬ
↓ ↓ ↓
•（暗号文）ＩＢＭ
2015/9/30
confidential
6
シーザー暗号（2）
•アルゴリズム
何文字かずらすという手順
•鍵
ずらす文字数
2015/9/30
confidential
7
外交と暗号
•ワシントン軍縮交渉（１９２１年）
軍艦保有数の英米と日本の比率
•日本の主張１０：７
•譲歩の用意１０：６
（暗号解読で知られていた）
2015/9/30
confidential
8
紫暗号（旧海軍）
•解読するのは至難のわざ
•米の天才フリードマンらが成功
ミッドウェイ海戦に圧勝
山本五十六大将の戦死
2015/9/30
confidential
9
エニグマ暗号（ドイツ)
•解読するのは至難のわざ
•英の天才チューリングらが成功
Ｕボートの被害減少
2015/9/30
confidential
10
天才チューリング
•チューリング賞
•チューリング機械
計算可能とは何か
2015/9/30
confidential
11
世界初のコンピュータ
•コロッサス（英、１９４３年）
エニグマ暗号の解読
•戦後、処分
設計図も焼却処分
厳重な緘口令
2015/9/30
confidential
12
栄誉はエニアックへ
•１９４５年
米ペンシルバニア大学の
エッカートとモークリー
•１８，０００本の真空管
•毎秒５，０００回の計算
2015/9/30
confidential
13
アメリカでは
•ウィーナー
砲弾を命中させるために
計算機の製作を言上
•ノイマン
プログラム内蔵を提唱
•シャノン
情報理論
2015/9/30
confidential
14
発熱しない真空管を作れ
•１９４７年トランジスタ
ブラッテン
バーディン
ショックレー
•１９５４年パラメトロン
後藤英一
2015/9/30
confidential
15
戦後の暗号
•計算機を利用した解読
•計算機を利用した製作
•計算機を所有していたのは
政府機関と軍関係のみ
2015/9/30
confidential
16
１９６０年代
•計算機の性能向上
•一般企業も所有し、
•暗号を送金や商取引に
2015/9/30
•標準化の要望
confidential
17
ＤＥＳ暗号
•１９７６年
米国標準暗号に制定
2015/9/30
•アルゴリズムは公開
鍵のみ秘密
平文＝６４ビット
暗号文＝６４ビット
鍵長＝５６ビット
confidential
18
ＤｅｅｐＣｒａｃｋ
•１９９９年
ＤＥＳ暗号を２２時間で破る
•製作費用
わずか２５万ドル
2015/9/30
confidential
19
ＡＥＳ暗号
•次期暗号をコンテストで募る
•Ｒｉｊｎｄａｅｌに決定（２００１年）
平文１２８ビット
暗号文１２８ビット
鍵長１２８、１９４、２５６ビット
2015/9/30
confidential
20
共通鍵暗号の弱点
•送信者と受信者が鍵を共有
•どうやって鍵を配送するか？
スーツケースに入れて運ぶ
手間と費用が大変
2015/9/30
confidential
21
公開鍵暗号の登場
•暗号化鍵ｐｋを公開！！
•復号鍵ｓｋのみを秘密
•ただし、
ｐｋからｓｋを求めることは困難
2015/9/30
confidential
22
ＤＨとＲＳＡ
•１９７６年
Diffie and Hellman が概念
•１９７７年
ＲＳＡ暗号
2015/9/30
confidential
23
英のＧＣＨＱ
•実は、１９７５年以前に
公開鍵暗号
•秘密厳守
•特許もとらず
2015/9/30
confidential
24
代表的な公開鍵暗号
• RSA暗号
N=pqの素因数分解の困難さを利用
• ElGamal暗号
有限巡回群上の離散対数問題を利用
2015/9/30
confidential
25
現代暗号理論
•デジタル署名
•電子選挙
•電子現金
•放送型暗号系
•零知識証明などなど
計算機科学の一大分野に成長
2015/9/30
confidential
26
講義内容
• 暗号の歴史
• 確率
教科書、２章p.8～
• メッセージ認証コード
2015/9/30
confidential
27
確率とは
• さいころを考える
Pr(1) Pr(2) ・・・・・・・・・ Pr(6)
|
1
6
標本空間
U ={1,2,・・・,6}
確率分布
確率関数
1
Pr(1)=Pr(2)=・・・=
6
さいころ
1
2015/9/30
2
3
4
5
6
confidential
28
確率とは
• さいころを考える
Pr(1) Pr(2) ・・・・・・・・・ Pr(6)
|
1
6
標本空間
U ={1,2,・・・,6}
確率分布
確率関数
1
Pr(1)=Pr(2)=・・・=
6
さいころ
1
2015/9/30
2
3
4
5
6
confidential
(1) i = 1,・・・,6に対し
Pr(i)≧0
(2) Pr(1)+・・・+Pr(6) = 1
29
• 定義１
以下の性質が成り立つとき、
（標本空間 U、確率関数Pr）の組を
確率分布と呼ぶ
（１）各 u∈ U に対し、 Pr(u)≧0
（２） Σu Pr(u) = 1
2015/9/30
confidential
30
• |U| = 集合Uの要素数
• たとえば、
U = { 1, 2, ・・・ , 6 } のとき、|U| = 6
• 定義２
各 u∈ U に対し、
1
Pr(u) = U
が成り立つ確率分布を一様分布という
2015/9/30
confidential
31
|
1
6
1 1 1
Pr(A) = + =
6 6 3
1
2015/9/30
2
3
4
5
6
confidential
32
|
1
6
1 1 1
Pr(A) = + =
6 6 3
1
2
3
4
5
6
事象A
2015/9/30
confidential
33
|
1
6
1 1 1
Pr(A) = + =
6 6 3
1
2
3
4
5
6
事象A
• 定義３
標本空間Uの部分集合Aを事象と呼び、
Pr(A) =  Pr(μ)
と定義する。
μ
A
2015/9/30
confidential
34
1 2
Pr(A) = 1 - =
3 3
|
1
6
1 1 1
Pr(A) = + =
6 6 3
1
2
事象A
3
4
5
6
余事象A
• 定義３
標本空間Uの部分集合Aを事象と呼び、
Pr(A) = Pr(μ)
μ
A
と定義する。
事象Aの補集合Aは余事象と呼ばれ、
Pr(A) = 1 – Pr(A)
2015/9/30
confidential
35
A
B
A∩B
A∪B
２つの部分集合、A,B U⊆ に対し
|A∪B| = |A| + |B| － |A∩B|
2015/9/30
confidential
36
A
B
A∩B
A∪B
２つの部分集合、A,B ⊆ U に対し
|A∪B| = |A| + |B| － |A∩B|
確率においても、同様に
Pr(A∪B) = Pr(A) + Pr(B) － Pr(A∩B)
≦ Pr(A) + Pr(B)
2015/9/30
confidential
37
• （例）コインを2枚投げる
2枚目
H
T
H
HH
HT
T
TH
TT
1枚目
H=表
T=裏
標本空間 U
Pr(HH)=Pr(HT)=Pr(TH)=Pr(TT)=1/4
2015/9/30
confidential
38
• （例）コインを2枚投げる
2枚目
H
T
H
HH
HT
T
TH
TT
1枚目
H=表
T=裏
標本空間 U
少なくとも一回は表が出る
事象A
A = { HH,HT,TH },
Pr(A) = ¼ + ¼ + ¼ = ¾
2015/9/30
confidential
39
• （例）コインを2枚投げる
2枚目
H
T
H
HH
HT
T
TH
TT
1枚目
H=表
T=裏
標本空間 U
少なくとも一回は表が出る
事象A
A = { HH,HT,TH }
余事象A
A = { TT },
2015/9/30
confidential
40
条件付確率
Pr(μ)
• Pr（μ| B） =
if μ∈B ①
Pr(B)
• Pr（μ| B） = 0
if μ 
B
②
事象A ⊆ U の条件付確率
Pr(A|B) = Pr(μ|B)
μ
A
Pr(A∩B)
=
③
Pr(B)
⇒ Pr(A∩B) = Pr(A|B) ・ Pr(B)
2015/9/30
confidential
41
B1
B2
・・・・・・・・
Bn
U=
A
• 標本空間 U がn個の事象
B1,B2,・・・,Bnに分割されていると仮定する。
すると、任意の事象Aに対し
n
n

Pr（A） = 
Pr（A∩B
）
=
Pr(A|Bi)・Pr(Bi)
i
i 1
i 1
2015/9/30
confidential
42
B1
B2
・・・・・・・・
U=
Bn
A
Pr(B1 | A) = Pr(A∩B1) / Pr(A)
分子 = Pr(A | B1) ・Pr(B1)
分母 = ΣPr(A | Bi)・Pr(Bi)
= Pr(A | B1) ・Pr(B1) / ΣPr(A | Bi)・Pr(Bi)
2015/9/30
confidential
43
B1
B2
・・・・・・・・
U=
Bn
A
ベイズの定理
Pr(B1 | A) = Pr(A | B1) ・Pr(B1) / ΣPr(A | Bi)・Pr(Bi)
2015/9/30
confidential
44
講義内容
• 暗号の歴史
• 確率
• メッセージ認証コード
教科書, p.12～
2015/9/30
confidential
45
なりすまし攻撃
好き
アリス
ボブ
敵
2015/9/30
confidential
46
改ざん攻撃
アリス
きらい
好き
ボブ
敵
2015/9/30
confidential
47
メッセージ認証
平文
アリス
鍵 K
認証子
（好き,Tag）
敵
2015/9/30
ボブ
鍵 K
・なりすまし攻撃
・改ざん攻撃
confidential
48
方式
•
•
•
•
p=大きな素数
鍵 K=(a,b) ← {0, 1, …, p-1}
平文 m ∈ {0, 1, …, p-1}
Tag=a・m+b mod p
2015/9/30
confidential
49
送信者のアルゴリズム
• 平文 m ∈ {0, 1, …, p-1}
• 鍵 K=(a,b) ← {0, 1, …, p-1}
• アリスは、
Tag =a・m+b mod p
を計算し、(m,Tag)をボブに送る。
2015/9/30
confidential
50
受信者のアルゴリズム
• 平文 m ∈ {0, 1, …, p-1}
• 鍵 K=(a,b) ← {0, 1, …, p-1}
• (m,Tag)を受け取ったボブは、
Tag=a・m+b mod p
• が成り立てばaccept
2015/9/30
confidential
51
メッセージ認証
平文
アリス
鍵 K
認証子
（m,Tag）
ボブ
鍵 K = （a,b）
=
（a,b）
敵
• p＝素数
• 鍵 a,b ← {0,1,2,・・・,p-1} からランダムに選
• 平文 m ∈ {0,1,2,・・・,p-1}
2015/9/30
confidential
52
メッセージ認証
平文
アリス
鍵 K
認証子
（m,Tag）
ボブ
鍵 K = （a,b）
=
（a,b）
敵
Tag = a m + b mod p
pは素数
• 鍵 a,b ← {0,1,2,・・・,p-1} からランダムに選ぶ
平文 m ∈ {0,1,2,・・・,p-1}
2015/9/30
confidential
53
定理
• 本方式においては、
Pr(なりすまし成功) = 1/p
Pr(改ざん成功)
= 1/p
2015/9/30
confidential
54
なりすまし攻撃
m, Tag
アリス
ボブ
K=(a,b)
敵
ボブ accepts if
Tag=a×m+b mod p
2015/9/30
confidential
55
なりすまし確率
(m, Tag)=固定
アリス
ボブ
敵
K=(a,b):ランダム
Pr(ボブ accepts)
= Pr(Tag=a×m+b mod p
となる鍵(a,b)を持っている)
2015/9/30
confidential
56
なりすまし攻撃
b
a
0
1
2
・
・
・
p-1
0
1
2
・・・
p-1
（0,0）（0,1）（0,2）・・・（0,p-1）
（1,0）
・
・
（2,0）
・
A
・
・
・
・
・
・
（p-1,0）・・・・・・・・・
（p-1,p-1）
標本空間 U
Tag = a m + b mod p
となる(a,b)の集合A
2015/9/30
confidential
57
b
a
0
1
2
・
・
・
p-1
0
1
2
・・・
p-1
（0,0）（0,1）（0,2）・・・（0,p-1）
（1,0）
・
・
（2,0）
・
A
・
・
・
・
・
・
（p-1,0）・・・・・・・・・
（p-1,p-1）
標本空間 U
A = ボブがだまされるという事象
= （Tag = a m + b mod p ）が成り立つ事象
固定
2015/9/30
confidential
58
b
a
0
1
2
・
・
・
p-1
0
1
2
・・・
p-1
（0,0）（0,1）（0,2）・・・（0,p-1）
（1,0）
・
・
Tag=am+b
（2,0）
・
・
・
mod
p
・
・
・
・
（p-1,0）・・・・・・・・・
（p-1,p-1）
標本空間 U
この面積
Pr(A) =
全面積
2015/9/30
confidential
59
b
a
0
1
2
・
・
・
p-1
0
1
2
・・・
p-1
（0,0）（0,1）（0,2）・・・（0,p-1）
（1,0）
・
・
Tag=am+b
（2,0）
・
・
・
mod
p
・
・
・
・
（p-1,0）・・・・・・・・・
（p-1,p-1）
標本空間 U
この面積
Pr(A) =
全面積
この式が成り立つ（a,b）の個数
=
（a,b）の総数
2015/9/30
confidential
60
b
a
0
1
2
・
・
・
p-1
0
1
2
・・・
p-1
（0,0）（0,1）（0,2）・・・（0,p-1）
（1,0）
・
・
Tag=am+b
（2,0）
・
・
・
mod
p
・
・
・
・
（p-1,0）・・・・・・・・・
（p-1,p-1）
標本空間 U
この式が成り立つ（a,b）の個数
Pr(A) =
（a,b）の総数 = p2
2015/9/30
confidential
61
b
a
0
1
2
・
・
・
p-1
0
1
2
・・・
p-1
（0,0）（0,1）（0,2）・・・（0,p-1）
（1,0）
・
・
Tag=am+b
（2,0）
・
・
・
mod
p
・
・
・
・
（p-1,0）・・・・・・・・・
（p-1,p-1）
分子：
aを決めると、
bが決まる。
この式が成り立つ（a,b）の個数
Pr(A) =
（a,b）の総数 = p2
a = 0 → b = tag
a = 1 → b = tag - m
・
・
・
p個
a = p-1 → b = tag - （p-1）m
2015/9/30
confidential
62
b
a
0
1
2
・
・
・
p-1
0
1
2
・・・
p-1
（0,0）（0,1）（0,2）・・・（0,p-1）
（1,0）
・
・
Tag=am+b
（2,0）
・
・
・
mod
p
・
・
・
・
（p-1,0）・・・・・・・・・
（p-1,p-1）
標本空間 U
この式が成り立つ（a,b）の個数
Pr(A) =
（a,b）の総数
p
a = 0 → b = tag
= p2
a = 1 → b = tag - m
1
= p
2015/9/30
・
・
・
p個
a = p-1 → b = tag - （p-1）m
confidential
63
•
•
∀x
,P(x)
全てのx
各x
任意のx
For any x
∀x ,∀y,P(x,y)
全ての(x,y)
各(x,y)
任意の(x,y)
•
に対し、P(x)が成り立つ
∀m, ∀Tag,
2015/9/30
に対し、P(x,y)が成り立つ
Pr(なりすまし攻撃でボブが騙される) =
confidential
1
p
64
改ざん攻撃
アリス
鍵 K
（m,Tag）
（m’,Tag’）
=
m’ ≠ m
ボブ
鍵 K = （a,b）
（a,b）
敵
2015/9/30
confidential
65
改ざん攻撃
アリス
鍵 K
（m,Tag）
（m’,Tag’）
=
事象A
m’ ≠ m
ボブ
鍵 K = （a,b）
（a,b）
敵
2015/9/30
confidential
if accept = 事象B
66
改ざん攻撃
任意に固定
アリス
鍵 K
（m,Tag）
（m’,Tag’）
=
事象A
ボブ
鍵 K = （a,b）
（a,b）
敵
2015/9/30
confidential
if accept = 事象B
67
• 事象A = {（a,b）| Tag = a・m + b mod p }
• 事象B = {（a,b）| Tag’ = a・m’ + b mod p }
• ∀m, ∀Tag, ∀m’(≠m), ∀Tag’
Pr(ボブが騙される)
Pr(A∩B)
= Pr(B|A) = Pr(A)
=
2015/9/30
事象A,Bが成り立つ(a,b)の数
事象Aが成り立つ(a,b)の数
confidential
＝ 1
p
68
方式
• 平文 m ∈ {0, 1, …, p-1}
• 鍵 (a,b) ← {0, 1, …, p-1}
• アリスは、
Tag=a・m+b mod p
を計算し、(m,Tag)をボブに送る。
• ボブは、
Tag=a・m+b mod p
• が成り立てばaccept
2015/9/30
confidential
69
定理
• 本方式においては、
Pr(なりすまし成功)=1/p
Pr(改ざん成功)=1/p
2015/9/30
confidential
70
長いメッセージの場合
• 平文 m1, m2 ∈ {0, 1, …, p-1}
• 鍵 (a, b, c) ← {0, 1, …, p-1}
• Tag=a・m1+b・m2+c mod p
2015/9/30
confidential
71
演習(1)
• この方式においても、
Pr(なりすまし成功)=1/p
Pr(改ざん成功)=1/p
が成り立つことを証明せよ。
2015/9/30
confidential
72
演習(2)
以下の方式の
Ｐｒ(なりすまし成功)、Pr(改ざん成功)
を求めよ。
• 平文 m1, m2 ∈ {0, 1, …, p-1}
• 鍵 (a, c) ← {0, 1, …, p-1}
• Tag=a・m1+a2・m2+c mod p
2015/9/30
confidential
73

Download Report