情報セキュリティ: 2006年05月26日

q
q
情報セキュリティ
第６回：２００５年５月２６日（金）
q
q
本日学ぶこと

RSAのアルゴリズム
q
q
q

前回
RSAの安全性
q
q

剰余演算，べき剰余
ユークリッドの互除法とその拡張
素数判定
素因数分解
対数の計算，離散対数問題
Diffie-Hellman鍵交換
q
q
鍵交換の方法
man-in-the-middle攻撃
2
本日の授業で学ぶ語句







多項式時間，指数時間
素数生成，素数判定，フェルマーテスト，確定的手法，確率
的手法
素因数分解問題，離散対数問題
Diffie-Hellman鍵交換，man-in-the-middle攻撃
指数時間アルゴリズムは効率が悪い．
素因数分解が効率よく行えるなら，RSAは安全でない．
Diffie-Hellman鍵交換で，整数を共有することができる．
安全性は，離散対数問題に依存する．
しかしman-in-the-middle攻撃には弱い．
3
効率の良いアルゴリズム・悪いアルゴリズム

処理時間が，入力の値のビット数 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 に比例するため，
指数時間アルゴリズムと呼ばれる．
4
素数生成



入力：ビット数N
出力：Nビットの素数
アルゴリズム
q
q
q
１？？
…
？？１
Step 1. 最上位が1，間は（N-2回の1ビット乱数生成により）N-2
ビットの乱数，最下位は1となるような，Nビットの整数nをランダ
ムに生成する．
Step 2. nが素数であるかどうかを判定する．素数でないと判定
されたら，Step 1に戻る．
Step 3. nを出力して終了する．
5
素数判定



入力：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」を出力することもある．
6
素数判定法の分類（１）

確率的手法
q
q
q
乱数を使う．
素数でないと判定したら，必ず素数でないが，
素数であると判定しても，実は素数でない可能性がある．
精度と実行時間は，テスト回数次第．
事実
素数でない素数である
○
判素数でない
定
結
果素数である起こり得る
起こらない
○
7
素数判定法の分類（２）

確定的手法
q
q
q
乱数は使わない．
判定結果は正しい．
多項式時間アルゴリズムが提案されているが，計算時間は実
用的ではない．
事実
素数でない素数である
判素数でない
定
結
果素数である
○
起こらない
起こらない
○
8
ＲＳＡと素因数分解の関係


素因数分解が効率よく行えるなら，ＲＳＡは安全でない．
略証：
q
q

NとEを既知とし，（素因数分解により）Nの素因数pが知られて
いるときに，Dを計算できればよい．
q←N/p，L←lcm(p-1,q-1) とし，aE+bL=1を満たす整数の組
(a,b)を拡張ユークリッド法により求め，D←a % L とすればよい．
これらの操作はいずれも効率よく行える．
「RSAが安全でないなら，素因数分解が効率よく行える」は
証明されていない．
9
RSAにおける素因数分解の方法




Nをk=3, 5, 7, ...の順に割って割り切れる（余りが0になる）か
調べる．
乱数を生成して，Nがその数で割り切れるか調べる．
乱数Mを1<M<Nの範囲で生成して，gcd(N,M)を求める．こ
れが1より大きければ，Nの素因数の一つである．
これらで素因数を発見するための実行回数の期待値は，
N（の素因数の小さいほうの値）に比例する．したがって，
指数時間アルゴリズムであり，効率は悪い．
10
整数の対数を求める方法

入力：２以上の整数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' とする．
11
RSAの解読問題（≠離散対数問題）



入力：正整数m，２以上の整数a，正整数y
出力： y = az % mを満たす整数z （ただし1≦z＜m）
前記の「整数の対数を求める方法」は，
いずれも適用できない．
12
離散対数問題



入力：２以上の素数p，生成元g, 正整数y
出力： y = gz % pを満たす整数z （ただし1≦z＜p）
（前ページの）RSAの解読問題が効率よく解ければ，離散対
数問題も効率よく解ける．
q

ただし，mが二つの素数の積であることを利用して，効率よく解
くのであれば，その手法は離散対数問題に適用できない．
離散対数問題が効率よく解けるとしても，（前ページの）RSA
の解読問題には利用できない．
13
生成元の補足

「gがpの生成元である」の必要十分条件
q
q
q
g % p，g2 % p，…，g(p-2) % p がどれも異なる．
g % p，g2 % p，…，g(p-2) % p がいずれも１ではない．
素数かつp-1の約数（p-1の素因数）であるすべてqに対して，
g(p-1)/q % p ≠ 1
14
Diffie-Hellman鍵交換のエッセンス







公開情報：素数P，生成元G
GはPに依存する．
Aliceが秘密に持つ情報：A
Gは必ずしも素数ではない．
Bobが秘密に持つ情報：B
Alice→Bob：GA % P
Bob→Alice：GB % P
Aliceの処理：(GB % P)A % P = GAB % P
Bobの処理：(GA % P)B % P = GAB % P
15
man-in-the-middle攻撃（教科書pp.136-138）
カレーライス
ください
ハヤシライス
お願いします
（悪意ある）
ウエイター
客
カレーライス
どうぞ
料理人
ハヤシライス
できたよ
16
Diffie-Hellman鍵交換に
man-in-the-middle攻撃を適用すると（１）
① アリスがボブ
に送信するが，
マロリーはこ
れを受け取る．
④ マロリーが，
ボブになりす
ましてアリスに
送信する．
② マロリーが，ア
リスになりす
ましてボブに
送信する．
③ ボブがアリス
に送信するが，
マロリーはこ
れを受け取る．
2004年度
情報セキュリティの
試験問題・解答より
17
Diffie-Hellman鍵交換に
man-in-the-middle攻撃を適用すると（２）

AliceとMalloryはGAM % Pを共有し，
BobとMalloryはGBM % Pを共有する．
q

AliceとBobの間では情報を共有していないが，
Aliceは，BobとGAM % Pを共有していると思っている．
Aliceが，GAM % Pを鍵として暗号文を作り，Bobに送ったら，
Malloryはそれを受け取ってGAM % Pで復号し， GBM % Pで
暗号化したものをBobに渡す．
AliceとBobの間で秘密にしたい通信内容が，Mallory
にも知れてしまう！
Alice
α
E(GBM%P,α)
E(GAM%P,α)
α
Bob
Mallory
α
18

Download Report