複数の復号指数を持つRSA暗号の安全性解析

概要

論文の詳細を見る
RSA 暗号の復号指数 d が小さいときには,RSA 法 N が効率的に素因数分解されることは広く知られている.Boneh と Durfee は,Coppersmith の格子を用いた攻撃を使い,d<N1-1/√2 のとき多項式時間で素因数分解が成功することを示した.これまで,ある RSA 法 N に対し k 個の暗号化指数 / 復号指数のペアが与えられたときには,どれだけ大きな復号指数に対して素因数分解を効率的に行うことができるかという研究がされてきた.Howgrave-Graham と Seifert はデイオファントス近似問題を解くことで,その攻撃アルゴリズムを構成し,k→∞ のときには復号指数がフルサイズでも素因数分解が成功することを示した.Aono は Coppersmith の手法を用いたアルゴリズムを構成し,これは k≧2 が小さなときには既存の最高のアルゴリズムであるが,k→∞ のときに復号指数が d<N3/4 でなければ素因数分解を行うことができない.本稿で,我々は Aono と同様 Coppersmit の手法を用いることで,暗号化指数 / 復号指数のペアが複数ある場合の改良アルゴリズムを提案する.我々のアルゴリズムは,復号指数が d<N1-√2/(3k+1) を満たすときに素因数分解を行うことができる.
2014-06-26