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

本日学ぶこと RSAのアルゴリズム RSAの安全性 RSA鍵生成で，乱数を用いて生成する値と，式を計算して求める値がある． 剰余演算，べき剰余 ユークリッドの互除法とその拡張 素数判定 RSAの安全性 素因数分解 対数の計算，離散対数問題 RSA鍵生成で，乱数を用いて生成する値と，式を計算して求める値がある． 指数時間アルゴリズムは効率が悪い． 素因数分解が効率よく行えるなら，RSAは安全でない． 前回

素数生成 入力：ビット数b 出力：bビットの素数 アルゴリズム Step 1. 最上位が1，間は（b-2回の1ビット乱数生成により）b-2ビットの乱数，最下位は1となるような，bビットの整数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はカーマイケル数

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

○ ○ 素数判定法の分類（２） 確定的手法 乱数は使わない． 判定結果は正しい． 計算に時間がかかる． 事実 素数でない 素数である 起こらない 素数である 起こらない ○

図の出典：『暗号技術入門―秘密の国のアリス』 p.130を一部改変 鍵ペア生成の流れ 素数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 q N N = p*q N 図の出典：『暗号技術入門―秘密の国のアリス』 p.130を一部改変

鍵ペア生成の流れ：余談 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を求めるほうが，その値が小さくなり，より速く復号できるので望ましい． 参考文献 池野信一，小山謙二：『現代暗号理論』，電子情報通信学会，pp.106-108 （1986）． http://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7

RSAは安全か？ 安全性を破るアプローチ N = p*q に着目する…素因数分解問題 C = ME % N に着目する…離散対数問題の変種

ＲＳＡと素因数分解の関係 素因数分解が効率よく行えるなら，ＲＳＡは安全でない． 略証： 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が安全でないなら，素因数分解が効率よく行える」は証明されていない．

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

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） 「Diffie-Hellman 鍵交換」の安全性の 根拠となっている 入力：素数p，生成元g, 正整数y 出力： y = gz % pを満たす整数z （ただし1≦z＜p） （前ページの）RSAの解読問題が効率よく解ければ，離散対数問題も効率よく解ける． ただし，mが二つの素数の積であることを利用して，効率よく解くのであれば，その手法は離散対数問題に適用できない． 離散対数問題が効率よく解けるとしても，（前ページの）RSAの解読問題には利用できない． 「gがpの生成元である」の必要十分条件 g % p，g2 % p，…，gp-2 % p がどれも異なる． g % p，g2 % p，…，gp-2 % p がいずれも１ではない． 素数かつp-1の約数（p-1の素因数）であるすべてqに対して，g(p-1)/q % p ≠ 1

数論アルゴリズムの計算例（１） 310 % 7 は？ 初期値： 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 4

数論アルゴリズムの計算例（２） 1440x + 50y = gcd(1440, 50) を満たす整数x, yは？ 初期化：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 y = 29, x = -1 gcd(a,b) = t = 10．実際，1440*(-1)+50*29=10 である． s t u v q r w 1440 50 1 28 40 -28 10 29 4

検算の方法 Linuxが使えるなら，bcコマンドが便利 計算機が使えない場合，目で危なそうな箇所をチェック echo '3 ^ 10 % 7' | bc echo '1440 * -1 + 50 * 29' | bc 計算機が使えない場合，目で危なそうな箇所をチェック べき剰余 r の更新と s の更新を間違えていないか？ t の最後は…→1→0になっているか？ 拡張ユークリッドの互除法 u,v,w は整数，それ以外は非負整数になっているか？ x と y の一方が正，もう一方が負になっているか？

例題 117 % 13は？ 194x + 37y = 1 を満たす整数(x,y)は？ 104x % 231 = 1 を満たす整数xは？