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