攻撃法

攻撃法
RSA暗号
ElGamal暗号
いつでも安全か？
RSA暗号、ElGamal暗号、
共に攻撃法は存在する。
対
策
法
鍵のサイズを十分に大きくして
ランダムに鍵を選ぶ。
フェルマの素因数分解法の概要

普通の素因数分解は
2,3,5,7, 
の順に素因数を探す

フェルマの素因数分解法は
n の付近から素因数を探す
n  pq
どのような時が危険か？
p ≒ q の時が危険である
な
ぜ
な
ら
p≒ n
だからである
例
n  10057
の時
n  100.2846 なので
t  101
よって
、 t2
t  101
、
t  pq 2
s  pq 2
 n  144  12
s  12
2
なので
p  113 、 q  89 となる。
フェルマ法の対策法

p と q を10進数で十桁は離す
PH法の概要

y  g mod pとなる s は
s
mod p  1

で求まる
中国剰余定理を使い
s mod p  1 を求める
どのような時が危険か？
p  1が小さい素因数しか
もたないときは危険
なぜなら
p  1  i 1 pi
k
s mod pi
ci
は
ci
とすると
O pi  の検索で見つかる
例
p  29 とする。このとき
p  1  28  2 7
2 1
g  2 , y  18 として
s  log 2 18 を決定したい。
例
s mod 2
2
を計算し
s  3mod 4
1
s mod 7
を得る。
を計算し
s  4 mod 7
を得る。
例
連立合同式
s  3 mod 4

s  4 mod 7 
を中国剰余定理で解いて
s  11 mod 28
を得る。
ＰＨ法の対策法

p  1が160ビット以上の素数を含む
安全な鍵
RSA暗号は
n が 1024 ビット以上
ElGamal暗号は
p が 1024 ビット以上
となる大きさの鍵を
ランダムに選ぶ

Download Report