q q 情報セキュリティ 第７回：２００５年５月２７日（金） q q 本日学ぶこと RSAのアルゴリズム q q q 前回 RSAの安全性 q q 剰余演算，べき剰余 ユークリッドの互助法とその拡張 素数判定 素因数分解 離散対数問題 暗号アルゴリズムのその他の話題 q q ハイブリッド暗号 ブロック暗号モード 2 素数生成 入力：ビット数N 出力：Nビットの素数 アルゴリズム q q q １ ？ ？ … ？ ？ １ Step 1. 最上位が1，間は（N-2回の1ビット乱数生成により）N-2 ビットの乱数，最下位は1となるような，Nビットの整数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」を出力することもある（例：n=561）． 4 素数判定法の分類（１） 確率的手法 q q q 乱数を使う． 素数でないと判定したら，必ず素数でないが， 素数であると判定しても，実は素数でない可能性がある． 精度と実行時間は，テスト回数次第． 事実 素数でない 素数である ○ 判 素数でない 定 結 果 素数である 起こり得る 起こらない ○ 5 素数判定法の分類（２） 確定的手法 q q q 乱数は使わない． 判定結果は正しい． 多項式時間アルゴリズムが提案されているが，計算時間は実 用的ではない． 事実 素数でない 素数である 判 素数でない 定 結 果 素数である ○ 起こらない 起こらない ○ 6 RSAにおける素因数分解の方法 Nをk=3, 5, 7, ...の順に割って割り切れる（余りが0になるか） を調べる． 乱数を生成して，Nがその数で割り切れるか調べる． 乱数Mを1<M<Nの範囲で生成して，gcd(N,M)を求める．こ れが1より大きければ，Nの素因数の一つである． これらで素因数を発見するための実行回数の期待値は， N（の素因数の小さいほうの値）に比例する．したがって， 指数時間アルゴリズムであり，効率は悪い． 素因数分解をする多項式時間アルゴリズムはまだ見つかっ ていない． q 存在していたら，RSAは安全でなくなってしまう． 7 整数の対数を求める方法 入力：２以上の整数a，正整数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' とする． 8 離散対数問題 入力：２以上の整数a，正整数m, y = az % m 出力：z （ただし1≦z＜m） 前記の「整数の対数を求める方法」は， いずれも適用できない． 9
© Copyright 2024 ExpyDoc
