格子を用いたRSA暗号に対する攻撃における行列の次数低減

摘要

BonehとDurfeeによって提案されたRSA暗号への攻撃は，ある制限のもとに1組の公開鍵から秘密鍵を鍵の長さの多項式時間で求めるものであり，この攻撃の中心的な役割を果たすのはLLLアルゴリズムである．彼らの攻撃が成功するための条件は大雑把にいって，そのパラメータがe≈N, p+q＜3N{sup}(1/2), d＜N{sup}(1-(2{sup}(1/2))/2≈N{sup}0.2928をみたしていることであるが，dがN{sup}0.2928に近いようなRSA暗号を解こうとした場合に行列の次数が大きくなるという問題点があった．本論文においては，彼らの格子を用いた攻撃の概要を紹介し，その格子（行列）の改良を提案する．その改良により，実用的な範囲においては，彼らのものに比べて8％から15％程度次数の小さな行列で同一のパフォーマンスを出すことに成功した．