针对离散私钥比特泄漏的RSA格攻击方法

摘要：

RSA算法是目前应用最广泛的公钥密码体制之一，而格攻击是针对RSA体制的一类重要攻击方法。为此，将RSA算法的部分私钥泄漏问题转化为多变元陑性同余方程的求解问题，基于同余方程构造出特定的格，利用LLL格基约化算法进行约化，从而以一定的概率求得同余方程的小根。以上述多变元陑性同余方程的小根求解技术为基础，提出一种针对离散私钥比特泄漏的RSA格攻击方法。在该方法下，如果RSA算法的公钥参数e=Nβ≤N1/2，并且私钥d的未知部分Nα≤N1/2-β，则能以高概率恢复出RSA算法的私钥d。通过NTL包对长度为1024 bit的大整数进行实验，结果验证了该攻击方法的有效性。

关键词：RSA算法、格攻击、离散私钥比特泄漏、陑性同余方程、小根、格基约化算法

分类号：TN918

资助基金：陠目国家自然科学基金资助陠目61003291；数学工程与先进计算国家重点实验室开放基金资助陠目2013A03。

在线出版日期：2014-04-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：163-166