q q 情報セキュリティ 第６回：２００５年５月２６日（金） q q

本日学ぶこと RSAのアルゴリズム RSAの安全性 Diffie-Hellman鍵交換 剰余演算，べき剰余 ユークリッドの互除法とその拡張 素数判定 RSAの安全性 素因数分解 対数の計算，離散対数問題 Diffie-Hellman鍵交換 鍵交換の方法 man-in-the-middle攻撃 前回

本日の授業で学ぶ語句 多項式時間，指数時間 素数生成，素数判定，フェルマーテスト，確定的手法，確率的手法 素因数分解問題，離散対数問題 Diffie-Hellman鍵交換，man-in-the-middle攻撃 指数時間アルゴリズムは効率が悪い． 素因数分解が効率よく行えるなら，RSAは安全でない． Diffie-Hellman鍵交換で，整数を共有することができる． 安全性は，離散対数問題に依存する． しかしman-in-the-middle攻撃には弱い．

効率の良いアルゴリズム・悪いアルゴリズム 処理時間が，入力の値のビット数 L と適当な定数 C,k を 用いて C・Lk で抑えられるならば，効率が良い． 多項式時間アルゴリズムと呼ばれる． 処理時間が，入力の値に比例するならば，効率が悪い． 例１： a % m, a2 % m, …, ab % m の順にべき剰余を求める． 例２： a*b % n = 1 を満たす整数 b を，b←1, 2, … と順に 代入して求める． 入力の値のビット数を L とすると，2L に比例するため， 指数時間アルゴリズムと呼ばれる．

素数生成 入力：ビット数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はカーマイケル数

○ ○ 素数判定法の分類（１） 確率的手法 乱数を使う． 素数でないと判定したら，必ず素数でないが， 素数であると判定しても，実は素数でない可能性がある． 精度と実行時間は，テスト回数次第． 事実 素数でない 素数である 判定結果 素数でない ○ 起こらない 素数である 起こり得る ○

○ ○ 素数判定法の分類（２） 確定的手法 乱数は使わない． 判定結果は正しい． 多項式時間アルゴリズムが提案されているが，計算時間は実用的ではない． 事実 素数でない 素数である 判定結果 素数でない ○ 起こらない 素数である 起こらない ○

ＲＳＡと素因数分解の関係 素因数分解が効率よく行えるなら，ＲＳＡは安全でない． 略証： NとEを既知とし，（素因数分解により）Nの素因数pが知られているときに，Dを計算できればよい． q←N/p，L←lcm(p-1,q-1) とし，aE+bL=1を満たす整数の組(a,b)を拡張ユークリッド法により求め，D←a % L とすればよい．これらの操作はいずれも効率よく行える． 「RSAが安全でないなら，素因数分解が効率よく行える」は証明されていない．

RSAにおける素因数分解の方法 Nをk=3, 5, 7, ...の順に割って割り切れる（余りが0になる）か調べる． 乱数Mを1<M<Nの範囲で生成して，gcd(N,M)を求める．これが1より大きければ，Nの素因数の一つである． これらで素因数を発見するための実行回数の期待値は， N（の素因数の小さいほうの値）に比例する．したがって， 指数時間アルゴリズムであり，効率は悪い．

整数の対数を求める方法 入力：２以上の整数a，正整数y 出力： 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' とする．

RSAの解読問題（≠離散対数問題） 入力：正整数m，２以上の整数a，正整数y 出力： y = az % mを満たす整数z （ただし1≦z＜m） 前記の「整数の対数を求める方法」は， いずれも適用できない．

離散対数問題 入力：２以上の素数p，生成元g, 正整数y 出力： y = gz % pを満たす整数z （ただし1≦z＜p） （前ページの）RSAの解読問題が効率よく解ければ，離散対数問題も効率よく解ける． ただし，mが二つの素数の積であることを利用して，効率よく解くのであれば，その手法は離散対数問題に適用できない． 離散対数問題が効率よく解けるとしても，（前ページの）RSAの解読問題には利用できない．

生成元の補足 「gがpの生成元である」の必要十分条件 g % p，g2 % p，…，g(p-2) % p がどれも異なる． 素数かつp-1の約数（p-1の素因数）であるすべてqに対して，g(p-1)/q % p ≠ 1

Diffie-Hellman鍵交換のエッセンス 公開情報：素数P，生成元G Aliceが秘密に持つ情報：A Bobが秘密に持つ情報：B Alice→Bob：GA % P Bob→Alice：GB % P Aliceの処理：(GB % P)A % P = GAB % P Bobの処理：(GA % P)B % P = GAB % P GはPに依存する． Gは必ずしも素数ではない．

man-in-the-middle攻撃（教科書pp.136-138） カレーライス ください ハヤシライス お願いします （悪意ある） ウエイター 客 料理人 カレーライス どうぞ ハヤシライス できたよ

Diffie-Hellman鍵交換に man-in-the-middle攻撃を適用すると（１） アリスがボブに送信するが，マロリーはこれを受け取る． マロリーが，ボブになりすましてアリスに送信する． マロリーが，アリスになりすましてボブに送信する． ボブがアリスに送信するが，マロリーはこれを受け取る． 2004年度 情報セキュリティの 試験問題・解答より

Diffie-Hellman鍵交換に man-in-the-middle攻撃を適用すると（２） AliceとMalloryはGAM % Pを共有し， BobとMalloryはGBM % Pを共有する． AliceとBobの間では情報を共有していないが， Aliceは，BobとGAM % Pを共有していると思っている． Aliceが，GAM % Pを鍵として暗号文を作り，Bobに送ったら，Malloryはそれを受け取ってGAM % Pで復号し， GBM % Pで暗号化したものをBobに渡す． 　　　　AliceとBobの間で秘密にしたい通信内容が，Malloryにも知れてしまう！ α E(GBM%P,α) α E(GAM%P,α) Mallory Alice Bob α