RSAに対する新しい攻撃について
Y.-D. Zhao and W.-F. Qi “Small Private-Exponent Attack on RSA with Primes Sharing Bits.” (ISC 2007)
ISC 2007 - Programに発表資料があるので見てた.
N=pqとして,
- pまたはqの半分のビットが既知の場合
- d<N^{0.292}の場合
のいずれかで, LLLを用いてdを知ることが出来るというのは良く知られている話.
B. de Wegerが2002年に, pとqの差が小さい場合にはdの制限が緩くても良いということを話したらしい *1. この場合, pとqの上の方のビットを共有していると言える.
では, 「逆は?」という発想の下, pとqの下の方のビットが同じという仮定から色々話をしている.
nをセキュリティパラメータとして, p, qをn/2ビットの素数とする. 下の(1/2-α)nビット分が同じだとする. また, eをγnビットの正の奇数とし, dをβnビット以下の正の数とする.
ここから頑張って解析を行うと, (α,γ)=(1/2,1)のときでβ≦0.284 (全く制限をつけない場合). (α,γ)=(1/4,1)のとき, β≦0.375 (pとqが下半分を共有). (α,γ)=(0.3,0.6)のときβ≦0.507.
解析の結果を見るに, αとγそれぞれが小さくなるとβの上限が上がるようだ.
さて, eが3の時はγ=2/nなのだが, この場合のβはどうなるのだろう? (α,γ)=(1/2 1/1000)でn=2048の時に上限の式を計算するとβ≦0.832になった. ただ他のところで齟齬を来たすので無理かな?
