q q 情報セキュリティ 第６回：２００７年５月２５日（金） q q 本日学ぶこと RSAのアルゴリズム q q q q 前回 RSAの安全性 q 剰余演算，べき剰余 ユークリッドの互除法とその拡張 素数判定 素因数分解 対数の計算，離散対数問題 RSA鍵生成で，乱数を用いて生成する値と，式を計算して求 める値がある． 指数時間アルゴリズムは効率が悪い． 素因数分解が効率よく行えるなら，RSAは安全でない． 2 素数生成 入力：ビット数b 出力：bビットの素数 アルゴリズム q q q １ ？ ？ … ？ ？ １ Step 1. 最上位が1，間は（b-2回の1ビット乱数生成により）b-2 ビットの乱数，最下位は1となるような，bビットの整数nをランダ ムに生成する． Step 2. nが素数であるかどうかを判定する．素数でないと判定 されたら，Step 1に戻る． Step 3. nを出力して終了する． 3 素数判定 入力：2以上の整数n，テスト回数T ap-1 % p = 1 ） 出力：nが素数なら「yes」，素数でないなら「no」 アルゴリズム（フェルマーテスト） q q q q q q q フェルマーの小定理： p が素数 ⇒ （gcd(p,a)=1 ⇒ Step 1. i←1とする． Step 2. 2以上n未満の正整数aをランダムに生成する． Step 3. gcd(a,n)>1ならば，Step 7に進む． Step 4. an-1%n≠1ならば，Step 7に進む． Step 5. i←i+1とする．i≦Tならば，Step 2に戻る． Step 6. 「yes」と出力して終了する． Step 7. 「no」と出力して終了する． うまくいく? q 素数であれば必ず「yes」と出力するが，素数でないのに誤って 「yes」を出力することもある． 4 素数判定法の分類（１） 確率的手法 q q q 乱数を使う． 素数でないと判定したら，必ず素数でないが， 素数であると判定しても，実は素数でない可能性がある． 精度と実行時間は，テスト回数次第． 事実 素数でない 素数である ○ 判 素数でない 定 結 果 素数である 起こり得る 起こらない ○ 5 素数判定法の分類（２） 確定的手法 q q q 乱数は使わない． 判定結果は正しい． 計算に時間がかかる． 事実 素数でない 素数である 判 素数でない 定 結 果 素数である ○ 起こらない 起こらない ○ 6 鍵ペア生成の流れ 素数p,qを生成 N=p*q, L=lcm(p-1,q-1) Eを1<E<Lの範囲で生成 E*D % L = 1 となるDを1<D<Lの範囲で求める (E,N)が暗号化鍵（公開鍵），(D,N)が復号鍵（プライベート鍵） 乱 E E*D % L = 1 D L = lcm(p-1, q-1) 暗号化鍵 乱 p N 復号鍵 乱 q N = p*q N 図の出典：『暗号技術入門―秘密の国のアリス』 p.130を一部改変 7 鍵ペア生成の流れ：余談 RSAの初期仕様やWikipediaでは，L=(p-1)(q-1) と記載され ている．この式を用いて鍵ペア(E,N), (D,N)を求めても，暗号 化・復号は問題なくできる． lcm(p-1,q-1)≦(p-1)(q-1)/2＜(p-1)(q-1) に注意すると， L=lcm(p-1,q-1)を用いてDを求めるほうが，その値が小さくな り，より速く復号できるので望ましい． 参考文献 q 池野信一，小山謙二：『現代暗号理論』，電子情報通信学会， pp.106-108 （1986）． 8 RSAは安全か？ 安全性を破るアプローチ q q N = p*q に着目する…素因数分解問題 C = ME % N に着目する…離散対数問題の変種 9 ＲＳＡと素因数分解の関係 素因数分解が効率よく行えるなら，ＲＳＡは安全でない． 略証： q q NとEを既知とし，（素因数分解により）Nの素因数pが知られて いるときに，Dを計算できればよい． q←N/p，L←lcm(p-1,q-1) とし，a*E+b*L=1を満たす整数の組 (a,b)を拡張ユークリッドの互除法により求め，D←a % L とすれ ばよい．これらの操作はいずれも効率よく行える． 「RSAが安全でないなら，素因数分解が効率よく行える」は 証明されていない． 10 効率の良いアルゴリズム・悪いアルゴリズム 処理時間が，入力の値のビット数 L と適当な定数 C,k を 用いて C・Lk で抑えられるならば，効率が良い． q 多項式時間アルゴリズムと呼ばれる． 処理時間が，入力の値に比例するならば，効率が悪い． q q q 例１： a % m, a2 % m, …, ab % m の順にべき剰余を求める． 例２： a*b % n = 1 を満たす整数 b を，b←1, 2, … と順に 代入して求める． 入力の値のビット数を L とすると，処理時間は2L に比例する ため，指数時間アルゴリズムと呼ばれる． 11 RSAにおける素因数分解の方法 Nをk=3, 5, 7, ...の順に割って割り切れる（余りが0になる）か 調べる． 乱数を生成して，Nがその数で割り切れるか調べる． 乱数Mを1<M<Nの範囲で生成して，gcd(N,M)を求める．こ れが1より大きければ，Nの素因数の一つである． これらで素因数を発見するための実行回数の期待値は， N（の素因数の小さいほうの値）に比例する．したがって， 指数時間アルゴリズムであり，効率は悪い． 12 整数の対数を求める方法 入力：２以上の整数a，正整数y 出力： y = az を満たす整数 z 方法１ q q log2 az = z log2 a を用いる． 整数値xのビット数を |x| で表すとき，|y| ≒ z×|a| である． よって z ≒ |y| / |a|． 方法２ q q ２分探索を応用する． q q+1 a, a2, a4, a8,... を求めていき，a2 ≦y＜a2 を満たす整数qが q 見つかれば，2q≦z＜2q+1とわかる．y'=y / a2 に対して，y'=az' を満たすz'を（再帰的に）求め，z=2q+z' とする． 13 RSAの解読問題（≠離散対数問題） 入力：正整数m，２以上の整数a，正整数y 出力： y = az % mを満たす整数z （ただし1≦z＜m） 前記の「整数の対数を求める方法」は， いずれも適用できない． 14 離散対数問題 入力：素数p，生成元g, 正整数y 出力： y = gz % pを満たす整数z （ただし1≦z＜p） （前ページの）RSAの解読問題が効率よく解ければ，離散対 数問題も効率よく解ける． q 「Diffie-Hellman 鍵交換」の安全性の 根拠となっている ただし，mが二つの素数の積であることを利用して，効率よく解 くのであれば，その手法は離散対数問題に適用できない． 離散対数問題が効率よく解けるとしても，（前ページの）RSA の解読問題には利用できない． 「gがpの生成元である」の必要十分条件 2 p-2 % p がどれも異なる． g % p，g % p，…，g 2 p-2 % p がいずれも１ではない． g % p，g % p，…，g 素数かつp-1の約数（p-1の素因数）であるすべてqに対して，g(p-1)/q % p ≠ 1 15 数論アルゴリズムの計算例（１） 310 % 7 は？ q q q 初期値： a = 3, b = 10, m = 7, r = 1, s = a = 3, t = b = 10 反復： t が奇数のとき r ← r * s % m t の偶奇に関係なく，s ← s * s % m, t ← t / 2 t=0 になった時点の r が解（以下の表では，4） r s t 1 3 10 ↓ 2 5 2 4 2 ↓ 2 1 4 0 16 数論アルゴリズムの計算例（２） 1440x + 50y = gcd(1440, 50) を満たす整数x, yは？ q q q q q 初期化：a = 1440, b = 50, s = 1440, t = 50, u = 0, v = 1 反復： q←s/t, r←s-q*t, w←u-q*v, s←t, t←r, u←v, v←w r=0になった時点で， x←(t-b*v)/a, y←v s t u 1440 50 0 50 40 40 10 v q r w 1 28 40 -28 1 -28 1 10 29 -28 29 4 0 y = 29, x = -1 gcd(a,b) = t = 10．実際，1440*(-1)+50*29=10 である． 17 検算の方法 Linuxが使えるなら，bcコマンドが便利 q q echo '3 ^ 10 % 7' | bc echo '1440 * -1 + 50 * 29' | bc 計算機が使えない場合，目で危なそうな箇所をチェック q q べき剰余 r の更新と s の更新を間違えていないか？ t の最後は…→1→0になっているか？ 拡張ユークリッドの互除法 u,v,w は整数，それ以外は非負整数になっているか？ x と y の一方が正，もう一方が負になっているか？ 18 例題 117 % 13は？ 194x + 37y = 1 を満たす整数(x,y)は？ 104x % 231 = 1 を満たす整数xは？ q 104x + 231y = 1と変形して求める 19
© Copyright 2024 ExpyDoc
