格子を用いたRSA暗号に対する攻撃における行列の次数低減
スポンサーリンク
概要
- 論文の詳細を見る
BonehとDurfeeによって提案されたRSA暗号への攻撃は,ある制限のもとに1組の公開鍵から秘密鍵を鍵の長さの多項式時間で求めるものであり,この攻撃の中心的な役割を果たすのはLLLアルゴリズムである.彼らの攻撃が成功するための条件は大雑把にいって,そのパラメータがe≈N,p+q<3√<N>,d<N^<1-√<2>/2>≈N^<0.2928>をみたしていることであるが,dがN^<0.2928>に近いようなRSA暗号を解こうとした場合に行列の次数が大きくなるという問題点があった.本論文においては,彼らの格子を用いた攻撃の概要を紹介し,その格子(行列)の改良を提案する.その改良により,実用的な範囲においては,彼らのものに比べて8%から15%程度次数の小さな行列で同一のパフォーマンスを出すことに成功した.
- 社団法人電子情報通信学会の論文
- 2007-04-19
著者
関連論文
- Shortest vector問題を用いたRSA暗号への攻撃における格子の構成方法
- 格子を用いたRSA暗号に対する攻撃における行列の次数低減
- Shortest vector 問題を用いたRSA暗号への攻撃における格子の構成方法