Download presentation
Presentation is loading. Please wait.
1
黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp
情報セキュリティ特論（4） 黒澤 馨 （茨城大学） 2017/3/4 confidential
2
演習 CBC-MACについて、以下の M=(m1, m2), Tagを基に、偽造せよ。 m2） （m1, E_K Tag 2017/3/4
confidential
3
m2 m2） （m1, m1+Tag m1 Ek Ek Ek Ek Tag Tag 2017/3/4 confidential
4
共通鍵暗号系 E D 鍵 k 暗号化 アルゴリズム 復号 アルゴリズム 暗号文 C 平文m m 敵 解読したい 2017/3/4
confidential
5
どうやって、鍵Kを共有？ E D 鍵 k 暗号化 アルゴリズム 復号 アルゴリズム 暗号文 C 平文m m 敵 解読したい 2017/3/4
confidential
6
公開鍵暗号系 暗号化の鍵Pkを公開 E D 復号鍵Skは秘密 暗号化 アルゴリズム 復号 アルゴリズム 暗号文 C 平文m m
2017/3/4 confidential
7
mod 5 において mod 7 において ・・・ 2017/3/4 confidential
8
p が素数のとき フェルマーの定理 2017/3/4 confidential
9
共通鍵暗号系 Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 共通鍵 共通鍵
暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential
10
フェルマーの定理より =1 2017/3/4 confidential
11
共通鍵暗号系 Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d)
11= 3= 7= 10= 例：m=3,e=3,d=7,p=11の場合 p,e p,d 11= =3 11= =7 3= 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential
12
共通鍵暗号系 Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 共通鍵 共通鍵
暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential
13
共通鍵暗号系 Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 共通鍵 共通鍵
X p,e,d X X 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential
14
公開鍵方式にすると Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 公開鍵
秘密鍵 p,e d 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential
15
公開鍵暗号にすると Pohlig-Hellman暗号 共通鍵 敵は、秘密鍵d を計算できる
素数 p 及び ed = 1 mod (p-1) となる (e,d) 敵は、秘密鍵d を計算できる 公開鍵 秘密鍵 p,e, d 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 敵 2017/3/4 confidential
16
素因数分解 p,qから、N=pqを計算するのは簡単 N(=pq)を素因数分解するのは困難 |N|=1024ビットのとき、１0億年
2017/3/4 confidential
17
公開鍵暗号系 RSA暗号 (鍵生成アルゴリズム) 512ビットの素数 p,q をランダムに生成 N = pq とおく
ed = 1 mod (p-1)(q-1) となる (e,d) を求める 公開鍵 N(=pq),e 秘密鍵 d 暗号化 アルゴリズム 復号 アルゴリズム 平文 m 2017/3/4 confidential
18
RSA暗号 p,qを求めることはできない ed = 1 mod (p-1)(q-1) 敵は、(p-1)(q-1)を計算できない
公開鍵 N(=pq),e 秘密鍵 d 暗号化 アルゴリズム 復号 アルゴリズム 平文 m 敵 p,qを求めることはできない ed = 1 mod (p-1)(q-1) 敵は、(p-1)(q-1)を計算できない よって、敵はdがわからない 2017/3/4 confidential
19
フェルマーの定理より =1 2017/3/4 confidential
20
同様に p,q は互いに素なので 2017/3/4 confidential
21
同様に p,q は互いに素なので 互いに素でない 2017/3/4 confidential
22
同様に p,q は互いに素なので 互いに素でない 互いに素 素因数 2017/3/4 confidential
23
RSA暗号 公開鍵 ： N ( =pq ), e 秘密鍵 ： d ただし ed = 1 mod (p-1)(q-1) 平 文 ： M
暗号文 ： 復 号 ： 2017/3/4 confidential
24
RSA暗号 公開鍵 ： N ( =pq ), e 秘密鍵 ： d ただし ed = 1 mod (p-1)(q-1)
このようなｄをどう求めるか？ 2017/3/4 confidential
25
（問題） 7x = 1 mod 10 を解け ユークリッド アルゴリズム a , b gcd(a,b) 10= 7= =1 2017/3/4
confidential
26
（問題） 7x = 1 mod 10 を解け 拡張 a , b ユークリッド アルゴリズム ax + by = gcd(a,b)
10= 7= 拡張 ユークリッド アルゴリズム a , b 10 7 1 ax + by = gcd(a,b) となる(x,y) =2 =3 - 2017/3/4 confidential
27
（問題） 7x = 1 mod 10 を解け 拡張 a , b ユークリッド アルゴリズム ax + by = gcd(a,b)
10= 7= 拡張 ユークリッド アルゴリズム a , b 10 7 1 ax + by = gcd(a,b) となる(x,y) =2 =3 - 両辺の mod 10 をとる 7y = 1 mod 10 =3 2017/3/4 confidential
28
（問題） 7x = 1 mod 10 を解け 拡張 a , b ユークリッド アルゴリズム ax + by = gcd(a,b)
10= 7= 拡張 ユークリッド アルゴリズム a , b 10 7 1 ax + by = gcd(a,b) となる(x,y) =2 =3 - 両辺の mod 10 をとる 7y = 1 mod 10 =3 3= ∴ 7x = 1 mod 10 2017/3/4 confidential
29
ユークリッドアルゴリズム 10 = 7 × 1 ・・・ 3 7 = 3 × 2 ・・・ 1 3 = 1 × 3 ・・・ 0 2017/3/4
10 = 7 × 1 ・・・ 3 7 = 3 × 2 ・・・ 1 3 = 1 × 3 ・・・ 0 2017/3/4 confidential
30
ユークリッドアルゴリズム 10 = 7 × 1 ・・・ 3 gcd(10,7) = gcd(7,3) を証明する。
7 = 3 × 2 ・・・ 1 3 = 1 × 3 ・・・ 0 = gcd(10,7) 2017/3/4 confidential
31
(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数
② 10 = 7 × 1 + 3 2017/3/4 confidential
32
(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数
② 10 = 7 × 1 + 3 d1は割り切る d1は割り切る 2017/3/4 confidential
33
(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数
② 10 = 7 × 1 + 3 d1は両方割り切る d1は割り切る d1は割り切る 2017/3/4 confidential
34
(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数
② 10 = 7 × 1 + 3 ③ d1 は (7,3) の公約数 d1は両方割り切る d1は割り切る d1は割り切る 2017/3/4 confidential
35
左図の様ならば、 同様に①～③より d2は(7,3)の公約数 (10,7)の 公約数 ・ d2 ・ d1 (7,3)の 公約数
2017/3/4 confidential
36
(10,7)の 公約数 ・ d2 つまり、(10,7)の公約数の集合は (7,3)の公約数の集合の部分集合 ・ d1 でなければならない
2017/3/4 confidential
37
次に、(7,3)の公約数は (10,7)の公約数の 部分集合であることを証明 (7,3)の 公約数 ・ d (10,7)の 公約数
2017/3/4 confidential
38
(7,3)の 公約数 ① d が (7,3) の公約数と仮定すると ② 10 = 7 × 1 + 3 ・ d dは割り切る dは割り切る
10 = 7 × 1 + 3 ・ d dは割り切る dは割り切る (10,7)の 公約数 2017/3/4 confidential
39
(7,3)の 公約数 ① d が (7,3) の公約数と仮定すると ② 10 = 7 × 1 + 3 よって
10 = 7 × 1 + 3 よって ③ d は (10,7) の公約数 ・ d dは割り切る dは割り切る (10,7)の 公約数 dは両方割り切る 2017/3/4 confidential
40
(7,3)の 公約数 ・ d つまり、(7,3)の公約数の集合は (10,7)の公約数の集合の部分 集合である (10,7)の公約数
2017/3/4 confidential
41
{ (10,7)の公約数 } ⊆ { (7,3)の公約数 } (2) { (10,7)の公約数 } ⊇ { (7,3)の公約数 } よって
{ (10,7)の公約数 } = { (7,3)の公約数 } ゆえに gcd(10,7) = gcd(7,3) 2017/3/4 confidential
42
定理 a = q・b + c のとき gcd(a,b) = gcd(b,c) (証明)
(1) { (a,b)の公約数 } ⊆ { (b,c)の公約数 } (2) { (a,b)の公約数 } ⊇ { (b,c)の公約数 } よって { (a,b)の公約数 } = { (b,c)の公約数 } ゆえに gcd(a,b) = gcd(b,c) 2017/3/4 confidential
43
ユークリッドアルゴリズム 10 = 7 × 1 ・・・ 3 gcd(10,7) = gcd(7,3)
= 1 3 = 1 × 3 ・・・ 0 = gcd(10,7) 2017/3/4 confidential
44
拡張ユークリッドアルゴリズム 10 = 7 × 1 ・・・ 3 7 = 3 × 2 ・・・ 1 3 = 1 × 3 ・・・ 0
10 = 7 × 1 ・・・ 3 7 = 3 × 2 ・・・ 1 3 = 1 × 3 ・・・ 0 10 = 10×1 + 7×0 7 = 10×0 + 7×1 3 = 10×1 + 7×(-1) 1 = 10×(-2) + 7×3 gcd(10,7) x y = gcd(10,7) 2017/3/4 confidential
45
（問題） 7x = 1 mod 10 を解け 拡張 a , b ユークリッド アルゴリズム ax + by = gcd(a,b)
10= 7= 拡張 ユークリッド アルゴリズム a , b 10 7 1 ax + by = gcd(a,b) となる(x,y) =2 =3 - 両辺の mod 10 をとる 7y = 1 mod 10 =3 3= ∴ 7x = 1 mod 10 2017/3/4 confidential
46
RSA暗号 公開鍵 ： N ( =pq ), e 秘密鍵 ： d ただし ed = 1 mod (p-1)(q-1)
このようなｄをどう求めるか？ 2017/3/4 confidential
47
p = 素数のとき 0 < a < p なる任意の a に対し gcd(p,a) = 1 よって px + ay = 1
よって px + ay = 1 となる(x,y)が存在 a y = 1 mod p 例： p = 5 のとき gcd(5,1) = 1 gcd(5,2) = 1 gcd(5,3) = 1 gcd(5,4) = 1 = 乗法逆元： 2017/3/4 confidential
48
すなわち 0 < a < p なる任意の a に対し
mod p における乗法逆元が存在する 例：mod 5 において 1×1 = 1 mod 5 2×3 = 〃 3×2 = 〃 4×4 = 〃 乗法逆元 2017/3/4 confidential
49
(問) 2x = 3 mod 5 を解け 2017/3/4 confidential
50
(問) 2x = 3 mod 5 を解け (解) 2017/3/4 confidential
51
群 ： ＋、－ ができる世界 環 ： ＋、－、× ができる世界 体 ： ＋、－、×、÷ ができる世界 （例） 実数の世界 mod 5 の世界
（例） 実数の世界 mod 5 の世界 = GF(5) 体 2017/3/4 confidential
52
有限体（ガロア体） 要素数が有限の体 GF(p) 要素数が p の体 GF(2) 要素数が最小の体 2017/3/4
要素数が有限の体 GF(p) 要素数が p の体 GF(2) 要素数が最小の体 2017/3/4 confidential
53
定理 GF(q) が存在する ただし、pは素数 = = 基礎体 拡大体 2017/3/4 confidential
54
フェルマーの定理 p = 素数のとき 0 < a < p なる任意の a に対し 2017/3/4 confidential
55
(簡単な証明) 2017/3/4 confidential
56
(簡単な証明) × 2017/3/4 confidential
57
(簡単な証明) × 2017/3/4 confidential
58
p が合成数のとき × 2017/3/4 confidential
59
(証明) 2017/3/4 confidential
60
(補題) 2017/3/4 confidential
61
(証明) まず 0 ≦ bi ≦ p-1 bi = 0 と仮定すると a×i = 0 mod p 両辺 i で割ると ∴a = 0 〃
これは矛盾 よって 1 ≦ bi ≦ p-1 2017/3/4 confidential
62
(証明 続き) bi = bj と仮定すると a×i = a×j mod p ∴i = j 〃 これは矛盾 次にある i ≠ j に対し
これは矛盾 1～p-1 2017/3/4 confidential
63
(フェルマーの定理の証明) × ap-1=1 mod p 2017/3/4 confidential
64
RSA暗号の生成 ① 大きな素数 p,q を生成 ② ed = 1 mod (p-1)(q-1) となる (e,d) を求める ③ の計算
2017/3/4 confidential
65
RSA暗号の生成 ① 大きな素数 p,q を生成 ② ed = 1 mod (p-1)(q-1) となる (e,d) を求める ③ の計算
2017/3/4 confidential
66
の高速計算法 n ビット 高々 2(n-1)回の乗算 2017/3/4 confidential
67
素数は無限個存在する (証明) 素数の集合 = { 2,5,7,11 } (と仮定する) p = 2×5×7×11+1 とおく。すると
素数の集合 = { 2,5,7,11 } (と仮定する) p = 2×5×7×11+1 とおく。すると p は 2 で割り切れない p は 11 で割り切れない よって、 p はどの素数でも割り切れない ゆえに p は素数である。 これは矛盾 ・・・ 2017/3/4 confidential
68
(N,e),C 解読 m （1億年） RSA仮定 N 素因数分解 p,q （10億年） 素因数分解仮定 2017/3/4
confidential
69
1,・・・,1 鍵生成 アルゴリズム N(=pq),e,d ただし |N| = n ビット n ビット 確率的多項式時間アルゴリズム
乱数テープ 2017/3/4 confidential
70
（1億年） RSA仮定 (N,e),C 解読 m 乱数テープR Pr(解読) < ε (N,e) この体積 全体積 成功 C R
2017/3/4 confidential
71
RSA仮定 任意の確率的多項式時間解読アルゴリズム Aに対し Pr（解読） < ε ただし、確率は 鍵生成アルゴリズムの乱数テープ
任意の確率的多項式時間解読アルゴリズム Aに対し Pr（解読） < ε ただし、確率は 鍵生成アルゴリズムの乱数テープ 解読アルゴリズム A の乱数テープ 平文 m についてとる 2017/3/4 confidential
72
定理 確率εで素因数分解に成功する 確率的多項式時間解読アルゴリズムBが存在 確率εでRSA解読に成功する
2017/3/4 confidential
73
定理 確率εで素因数分解に成功する 確率的多項式時間解読アルゴリズムBが存在 確率εでRSA解読に成功する
難しい （？） 易しい 2017/3/4 confidential
74
（証明） A N,e,C N B p,q 2017/3/4 confidential
75
（証明） A N,e,C N B p,q 乱数テープR 2017/3/4 confidential
76
（証明） A N,e,C N B p,q より d を求める m 乱数テープR 2017/3/4 confidential
77
演習 (1) Mod 15の世界において、以下のxを求めよ。 2x=1 4x=1 7x=1 8x=1 11x=1 13x=1 14x=1
2017/3/4 confidential
78
演習 (2) p=11, q=17, e=3とするRSA暗号 について考える。 gcd((p-1)(q-1),3)の値を求めよ。
公開鍵pk、秘密鍵skを求めよ。 平文m=7に対する暗号文Cを求めよ。 上記のCを復号せよ。 2017/3/4 confidential
Similar presentations
