5.RSA暗号 素因数分解の困難性を利用した暗号
法演算 合同式 a ≡ b ( mod n ) a と b は n を法として合同 ⇔ a と b は n で割って余りが等しい
暗号化の方式 暗号化 復号化 暗号文 y 平文 x 平文 x 復号化鍵(n,d) 暗号化鍵(n,e)
暗号化 復号化 ↓ ↓ 暗号文 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 = 213 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
鍵の生成 アリスがボブにメッセージを送るとする 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
使っている計算 y = xe mod n 素数の生成 ed≡１ ( mod m ) を満たす d
反復二乗法 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 2 2 2 1024 2 2 2 2
ユークリッドのアルゴリズム 入力：整数 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･167+192･(-20)
素数の生成 乱数 a を生成 確率的素数判定 （高速） no a ← a + 2 yes a を出力
復号化の困難さ ボブは d を使ってy d mod nを計算 → 高速 ボブ以外の人は秘密鍵を知らない → p , qを知る必要がある → 高速 ボブ以外の人は秘密鍵を知らない → p , qを知る必要がある → 困難
素因数分解の困難さ 効率的な素因数分解法は発明されていない 512ビットの鍵では解読される可能性が高い n が10ビット増えると、最低でも計算に2倍の時間が必要 1024ビットになると512ビットのときのおよそ 2 倍(1千兆倍以上)の時間が必要 50
素因数分解の困難さ （過去の懸賞問題） nが129ビットで作られた暗号文を復号化する 問題 17年後、1600台のコンピュータを8ヶ月間使った 結果nを素因数分解し、復号化に成功
素因数分解の困難さ （新しい懸賞問題） 576ビット長の鍵 10,000ドル 2048ビット長の鍵 200,000ドル