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