5.RSA暗号 素因数分解の困難性を利用した暗号.

Presentation on theme: "5.RSA暗号 素因数分解の困難性を利用した暗号."— Presentation transcript:

1 5.RSA暗号 素因数分解の困難性を利用した暗号

2 法演算 合同式 a ≡ b ( mod n ) a と b は n を法として合同 ⇔ a と b は n で割って余りが等しい

3 暗号化の方式 暗号化 復号化 暗号文 y 平文 x 平文 x 復号化鍵(n,d) 暗号化鍵(n,e)

4 暗号化 復号化 ↓ ↓ 暗号文 y = x e mod n yｄ = x mod n 平文 x を得る 例 n=221, 例 n=221,
暗号化鍵 n ,e , 平文 x 　　　　　↓ 暗号文 y = x e mod n 例　n=221, e=23, 　 x=213のとき y = mod 221 = 138 復号化鍵 n , d ,暗号文 y 　　　　　↓ yｄ = x mod n 平文 x を得る 例　n=221, d=167, 　 y=138より 138 =213 mod 221 x = 213 を得る 23 167

5 鍵の生成 アリスがボブにメッセージを送るとする p, q：異なる大きな素数 を生成
→　n = pq、m = (p - 1)(q - 1)　を計算 e：mと互いに素な自然数を生成 →　d：ed ≡ 1 mod m　を満たす整数　を計算 (n, e)：ボブの公開鍵（暗号化鍵） d　　 ：ボブの秘密鍵（復号化鍵） 例 p=13,q=17→n=221,m=192, さらに　e=23→d=167

6 使っている計算 y = xe　mod n 素数の生成 ed≡１ ( mod m ) を満たす d

7 反復二乗法 b ≡ a mod n を高速に計算する方法 例．2 の場合 通常:2×2×2×2×2×2×2×2 ⇒7回の演算
例．2　　の場合 通常:2×2×2×2×2×2×2×2 ⇒7回の演算 反復二乗法: ((2 ) ) 　　⇒3回の演算 　　 2　　の場合　　　　　　 通常：　2×2×2×･･･×2　⇒1023回の演算 反復二乗法：((((2 ) ) )･･･) ⇒10回の演算 x 8 1024

8 ユークリッドのアルゴリズム 入力：整数 a,b⇒出力：整数d, x ,y aとbの最大公約数gcd(a,b)=d
d=ax+byを満たすx, y 　高速に計算 例．a=5,b=3の場合 　1=5･2+3･(-3) 例． a=e=23,b=m=192の場合 　　1=23･ ･(-20)

9 素数の生成 乱数 a を生成 確率的素数判定 （高速） no a ← a + 2 yes a を出力

10 復号化の困難さ ボブは d を使ってy d mod nを計算 → 高速 ボブ以外の人は秘密鍵を知らない → p , qを知る必要がある
　　　　　　　　　→　高速 ボブ以外の人は秘密鍵を知らない 　　　　　　　　 →　p , qを知る必要がある 　　　　　　　　→　困難

11 素因数分解の困難さ 効率的な素因数分解法は発明されていない 512ビットの鍵では解読される可能性が高い
n が10ビット増えると、最低でも計算に2倍の時間が必要 1024ビットになると512ビットのときのおよそ 　　2　 倍(1千兆倍以上)の時間が必要 50

12 素因数分解の困難さ （過去の懸賞問題） nが129ビットで作られた暗号文を復号化する 問題
17年後、1600台のコンピュータを8ヶ月間使った 結果nを素因数分解し、復号化に成功

13 素因数分解の困難さ （新しい懸賞問題） 576ビット長の鍵　　　　　10,000ドル 2048ビット長の鍵　　　　200,000ドル