Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号，量子コンピュータ

Presentation on theme: "Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号，量子コンピュータ"— Presentation transcript:

1 Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号，量子コンピュータ
公開鍵暗号 4.6〜 Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号，量子コンピュータ

2 4.6 Diffie-Hellman鍵共有 離散対数問題 pが素数の時，1≤g, y≤p-1 を満たす整数 g, y から， 　　　　　y = ga mod p となる a を見つける問題。 p が 1024bit 以上かつ p-1 の最大素因数が 160bit 以上の場合，a を見つけることは（現時点では）実質的に不可能。 最良のアルゴリズムである「数体ふるい法」を現在のコンピュータで実行する限界

3 4.6 Diffie-Hellman鍵共有 D-H 問題 pが素数の時，1≤g≤p-1 を満たす整数 g と自然数 a, b に対して， a, b を伏せた状態で ga mod p, gb mod p から 　　　　　gab mod p を計算する問題。

4 4.6 Diffie-Hellman鍵共有 D-H 鍵共有 素数 p と p の生成元(原始根) g (1≤g≤p-1) を公開する。 アリスは自然数 a を秘密にして ga mod p を， ボブは自然数 b を秘密にして gb mod p を公開する。 yA = ga mod p, yB = gb mod p のとき， 　　yAb mod p = yBa mod p = gab mod p という性質を利用すれば，アリスとボブは共有鍵 gab mod p を所有できる。

5 4.6 Diffie-Hellman鍵共有 D-H 鍵共有の例 素数 p=7 と 7 の生成元(原始根) g=3 を公開する。 アリスは自然数 a=11 を秘密にして 311 mod 7 を， ボブは自然数 b=13 を秘密にして 313 mod 7 を公開する。 yA = 311 mod 7 = 5, yB = 313 mod 7 = 3， 　　513 mod 7 = 311 mod 7 = 311x13 mod 7 = 5 なので，アリスとボブは共有鍵 gab mod p = 5 を各自の計算だけで共有できる。

6 4.6 Diffie-Hellman鍵共有 原始根 素数 p, 1≤g≤p-1 のとき，自然数 1≤a≤p-1 に対して 　　y = ga mod p の値 y が全て異なる数（1 から p-1 が１回ずつ現れる数）を生成元(p.20)または原始根という。 31 mod 7 = 3, 32 mod 7 = 2, 33 mod 7 = 6, 34 mod 7 = 4, 35 mod 7 = 5, 36 mod 7 = 1

7 4.7 ElGamal 暗号 Diffie-Hellman鍵共有方式を暗号方式として利用できるように変形したもの。
離散対数問題が解けないことを安全性の根拠としている（と書かれているが正確には異なるらしい→wikipedia） 楕円曲線暗号の基礎をなす暗号方式

8 4.7 ElGamal 暗号 2≤s≤p-1 を満たす s をランダムに選ぶ。
鍵生成 大きい素数 p, その生成元 g (1≤g≤p-1) を選ぶ。 2≤s≤p-1 を満たす s をランダムに選ぶ。 Kp = (p, g, y=gs mod p) が公開鍵， s が秘密鍵。 暗号化 平文 M (1≤M≤p-1) に対して乱数 r (1≤r≤p-1) を選び， 　　c1 = gr mod p, c2 = Myr mod p とすると (c1, c2) が暗号文。

9 4.7 ElGamal 暗号 復号 暗号文と秘密鍵から以下の計算をすることで，平文に復号できる。 　　M = c2 • (c1s)-1 (mod p) 　　　= M • yr / c1s (mod p) 　　　= M • (gs)r / (gr)s (mod p) 　　　= M

10 4.7 ElGamal 暗号 2≤s≤p-1 を満たす s=11 をランダムに選ぶ。
鍵生成例 大きい素数 p=7, その生成元 g=3 (1≤3≤7-1) を選ぶ。 2≤s≤p-1 を満たす s=11 をランダムに選ぶ。 Kp = (p=7, g=3, y=5=311 mod 7) が公開鍵， s=11 が秘密鍵。 暗号化 平文 M=4 (1≤M≤p-1) に対して乱数 r=13 (1≤r≤p-1) を選び， 　　c1 = 313 mod 7 = 3, c2 = 4 • 513 mod 7 = 6 とすると (c1=3, c2=6) が暗号文。

11 4.7 ElGamal 暗号 復号 暗号文と秘密鍵から以下の計算をすることで，平文に復号できる。 　　M = c2 • (c1s)-1 (mod p) 　　　= 6 / 311 (mod 7) 　　　= 6 / 5 (mod 7) 　　　= 4　　( 6 = 5x (mod 7) を満たす x は 4) 　　　

12 4.8 その他の公開鍵暗号 n と P から Q を求めるのはたやすいが， P と Q から n を求めるのは非常に困難 楕円曲線暗号の原理
楕円曲線 E: y2 = x3 + ax + b 楕円曲線上の離散対数問題 曲線 E 上の点 P, Q について， Q = nP となる自然数 n を見つける問題 n と P から Q を求めるのはたやすいが， P と Q から n を求めるのは非常に困難 実際には楕円曲線上の点 P+Q, -P, 単位元O が定義され，そこから Q = nP を導く。

13 4.8 その他の公開鍵暗号 楕円曲線暗号の特徴 RSAやElGamal暗号に比べ，少ない計算量や鍵長で，同程度の暗号強度を持つことが知られている。 D-H問題は乗法群の問題だったので「対数」と言うが，楕円曲線では加法群上の問題だが，考え方は同じなので同じく「対数問題」という。

14 4.8 その他の公開鍵暗号 量子コンピュータ ショアは、1994年に量子コンピュータ上で素因数分解問題を多項式時間で解くことができるアルゴリズムを発見。従来のコンピュータでは準指数時間で解くアルゴリズムしか知られていなかった。 量子コンピュータが実現すると，素因数分解問題や離散対数問題の困難性による暗号技術が使えなくなる。