黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 情報セキュリティ特論（4） 黒澤　馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 2017/3/4 confidential

演習 CBC-MACについて、以下の M=(m1, m2), Tagを基に、偽造せよ。 m2） （m1, E_K Tag 2017/3/4 confidential

m2 m2） （m1, m1+Tag m1 Ek Ek Ek Ek Tag Tag 2017/3/4 confidential

共通鍵暗号系 E D 鍵 k 暗号化 アルゴリズム 復号 アルゴリズム 暗号文 C 平文m m 敵 解読したい 2017/3/4 confidential

どうやって、鍵Kを共有？ E D 鍵 k 暗号化 アルゴリズム 復号 アルゴリズム 暗号文 C 平文m m 敵 解読したい 2017/3/4 confidential

公開鍵暗号系 暗号化の鍵Pkを公開 E D 復号鍵Skは秘密 暗号化 アルゴリズム 復号 アルゴリズム 暗号文 C 平文m m 2017/3/4 confidential

mod 5 において mod 7 において ・・・ 2017/3/4 confidential

p が素数のとき フェルマーの定理 2017/3/4 confidential

共通鍵暗号系 Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 共通鍵 共通鍵 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential

フェルマーの定理より =1 2017/3/4 confidential

共通鍵暗号系 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

共通鍵暗号系 Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 共通鍵 共通鍵 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential

共通鍵暗号系 Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 共通鍵 共通鍵 X p,e,d X X 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential

公開鍵方式にすると Pohlig-Hellman暗号 共通鍵 素数 p 及び ed = 1 mod (p-1) となる (e,d) 公開鍵 秘密鍵 p,e d 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 2017/3/4 confidential

公開鍵暗号にすると Pohlig-Hellman暗号 共通鍵 敵は、秘密鍵d を計算できる 素数 p 及び ed = 1 mod (p-1) となる (e,d) 敵は、秘密鍵d を計算できる 公開鍵 秘密鍵 p,e, d 暗号化 アルゴリズム 復号 アルゴリズム p,e,平文 m 敵 2017/3/4 confidential

素因数分解 p,qから、N=pqを計算するのは簡単 N(=pq)を素因数分解するのは困難 |N|=1024ビットのとき、１0億年 2017/3/4 confidential

公開鍵暗号系 RSA暗号 (鍵生成アルゴリズム) 512ビットの素数 p,q をランダムに生成 N = pq とおく ed = 1 mod (p-1)(q-1) となる (e,d) を求める 公開鍵 N(=pq),e 秘密鍵 d 暗号化 アルゴリズム 復号 アルゴリズム 平文 m 2017/3/4 confidential

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

フェルマーの定理より =1 2017/3/4 confidential

同様に p,q は互いに素なので 2017/3/4 confidential

同様に p,q は互いに素なので 互いに素でない 2017/3/4 confidential

同様に p,q は互いに素なので 互いに素でない 互いに素 素因数 2017/3/4 confidential

RSA暗号 公開鍵 ： N ( =pq ), e 秘密鍵 ： d ただし ed = 1 mod (p-1)(q-1) 平 文 ： M 暗号文 ： 復 号 ： 2017/3/4 confidential

RSA暗号 公開鍵 ： N ( =pq ), e 秘密鍵 ： d ただし ed = 1 mod (p-1)(q-1) このようなｄをどう求めるか？ 2017/3/4 confidential

（問題） 7x = 1 mod 10 を解け ユークリッド アルゴリズム a , b gcd(a,b) 10= 7= =1 2017/3/4 confidential

（問題） 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

（問題） 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

（問題） 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

ユークリッドアルゴリズム 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

ユークリッドアルゴリズム 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

(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数 ② 10 = 7 × 1 + 3 2017/3/4 confidential

(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数 ② 10 = 7 × 1 + 3 d1は割り切る d1は割り切る 2017/3/4 confidential

(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数 ② 10 = 7 × 1 + 3 d1は両方割り切る d1は割り切る d1は割り切る 2017/3/4 confidential

(10,7)の公約数は (7,3)の公約数の 部分集合であることを証明 (10,7)の 公約数 ・ d1 (7,3)の公約数 ② 10 = 7 × 1 + 3 ③ d1 は (7,3) の公約数 d1は両方割り切る d1は割り切る d1は割り切る 2017/3/4 confidential

左図の様ならば、 同様に①～③より d2は(7,3)の公約数 (10,7)の 公約数 ・ d2 ・ d1 (7,3)の 公約数 2017/3/4 confidential

(10,7)の 公約数 ・ d2 つまり、(10,7)の公約数の集合は (7,3)の公約数の集合の部分集合 ・ d1 でなければならない 2017/3/4 confidential

次に、(7,3)の公約数は (10,7)の公約数の 部分集合であることを証明 (7,3)の 公約数 ・ d (10,7)の 公約数 2017/3/4 confidential

(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

(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

(7,3)の 公約数 ・ d つまり、(7,3)の公約数の集合は (10,7)の公約数の集合の部分 集合である (10,7)の公約数 2017/3/4 confidential

{ (10,7)の公約数 } ⊆ { (7,3)の公約数 } (2) { (10,7)の公約数 } ⊇ { (7,3)の公約数 } よって { (10,7)の公約数 } = { (7,3)の公約数 } ゆえに gcd(10,7) = gcd(7,3) 2017/3/4 confidential

定理 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

ユークリッドアルゴリズム 10 = 7 × 1 ・・・ 3 gcd(10,7) = gcd(7,3) = 1 3 = 1 × 3 ・・・ 0 = gcd(10,7) 2017/3/4 confidential

拡張ユークリッドアルゴリズム 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

（問題） 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

RSA暗号 公開鍵 ： N ( =pq ), e 秘密鍵 ： d ただし ed = 1 mod (p-1)(q-1) このようなｄをどう求めるか？ 2017/3/4 confidential

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

すなわち 0 < a < p なる任意の a に対し mod p における乗法逆元が存在する 例：mod 5 において 1×1 = 1 mod 5 2×3 = 1 〃 3×2 = 1 〃 4×4 = 1 〃 乗法逆元 2017/3/4 confidential

(問) 2x = 3 mod 5 を解け 2017/3/4 confidential

(問) 2x = 3 mod 5 を解け (解) 2017/3/4 confidential

群 ： ＋、－ ができる世界 環 ： ＋、－、× ができる世界 体 ： ＋、－、×、÷ ができる世界 （例） 実数の世界 mod 5 の世界 （例） 実数の世界 　　　　mod 5 の世界 = GF(5) 体 2017/3/4 confidential

有限体（ガロア体） 要素数が有限の体 GF(p) 要素数が p の体 GF(2) 要素数が最小の体 2017/3/4 　　　要素数が有限の体 GF(p) 　　　要素数が p の体 GF(2) 　　　要素数が最小の体 2017/3/4 confidential

定理 　　　GF(q) が存在する 　　　　　　　　　　　　　　　　　　ただし、pは素数 = = 基礎体 拡大体 2017/3/4 confidential

フェルマーの定理 　　　p = 素数のとき 　　　0 < a < p なる任意の a に対し 2017/3/4 confidential

(簡単な証明) 2017/3/4 confidential

(簡単な証明) × 2017/3/4 confidential

(簡単な証明) × 2017/3/4 confidential

p が合成数のとき × 2017/3/4 confidential

(証明) 2017/3/4 confidential

(補題) 2017/3/4 confidential

(証明) まず 0 ≦ bi ≦ p-1 bi = 0 と仮定すると a×i = 0 mod p 両辺 i で割ると ∴a = 0 〃 これは矛盾 よって 1 ≦ bi ≦ p-1 2017/3/4 confidential

(証明 続き) bi = bj と仮定すると a×i = a×j mod p ∴i = j 〃 これは矛盾 次にある i ≠ j に対し 　　これは矛盾 1～p-1 2017/3/4 confidential

(フェルマーの定理の証明) × ap-1=1 mod p 2017/3/4 confidential

RSA暗号の生成 ① 大きな素数 p,q を生成 ② ed = 1 mod (p-1)(q-1) となる (e,d) を求める ③ の計算 2017/3/4 confidential

RSA暗号の生成 ① 大きな素数 p,q を生成 ② ed = 1 mod (p-1)(q-1) となる (e,d) を求める ③ の計算 2017/3/4 confidential

　　　の高速計算法 n ビット 高々 2(n-1)回の乗算 2017/3/4 confidential

素数は無限個存在する (証明) 素数の集合 = { 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

(N,e),C 解読 m （1億年） RSA仮定 N 素因数分解 p,q （10億年） 素因数分解仮定 2017/3/4 confidential

1,・・・,1 鍵生成 アルゴリズム N(=pq),e,d ただし |N| = n ビット n ビット 確率的多項式時間アルゴリズム 乱数テープ 2017/3/4 confidential

（1億年） RSA仮定 (N,e),C 解読 m 乱数テープR Pr(解読) < ε (N,e) この体積 全体積 成功 C R 2017/3/4 confidential

RSA仮定 任意の確率的多項式時間解読アルゴリズム Aに対し Pr（解読） < ε ただし、確率は 鍵生成アルゴリズムの乱数テープ 　 任意の確率的多項式時間解読アルゴリズム 　　 Aに対し 　　　 　　Pr（解読） < ε 　　 ただし、確率は 鍵生成アルゴリズムの乱数テープ 　　　　　 解読アルゴリズム A の乱数テープ 平文 m 　　　についてとる 2017/3/4 confidential

定理 確率εで素因数分解に成功する 確率的多項式時間解読アルゴリズムBが存在 確率εでRSA解読に成功する 2017/3/4 confidential

定理 確率εで素因数分解に成功する 確率的多項式時間解読アルゴリズムBが存在 確率εでRSA解読に成功する 難しい （？） 易しい 2017/3/4 confidential

（証明） A N,e,C N B p,q 2017/3/4 confidential

（証明） A N,e,C N B p,q 乱数テープR 2017/3/4 confidential

（証明） A N,e,C N B p,q より d を求める m 乱数テープR 2017/3/4 confidential

演習 (1) Mod 15の世界において、以下のxを求めよ。 2x=1 4x=1 7x=1 8x=1 11x=1 13x=1 14x=1 2017/3/4 confidential

演習 (2) p=11, q=17, e=3とするRSA暗号 について考える。 gcd((p-1)(q-1),3)の値を求めよ。 公開鍵pk、秘密鍵skを求めよ。 平文m=7に対する暗号文Cを求めよ。 上記のCを復号せよ。 2017/3/4 confidential