【信息技术】【2002.06】基于代数和点阵方法的RSA密码分析

本文为美国斯坦福大学（作者：Glenn Durfee）的博士论文，共123页。

我们研究了公钥密码系统的安全性。特别地，我们研究了RSA公钥密码体制和多个变种。我们利用整数点阵理论中的工具得到了我们的结果。首先介绍整数点阵的理论，描述了在接下来的工作中使用的主要结果。然后我们回顾了公钥密码体制的概念，特别是RSA公钥密码体制。接下来，我们介绍了一种与RSA和其他公钥密码系统密切相关的一类整数分解算法，证明了一类新的整数可以进行有效地分解。我们接着介绍了对RSA公钥密码系统的新攻击，该系统使用了用户**的部分知识，表明泄漏**的四分之一位就足以危害RSA。接下来，我们描述当使用短秘密指数时对RSA公钥密码系统的新攻击。最后，我们描述了RSA的三个Sun-Yang-Laih**生成方案，并介绍了用于破坏其中两个方案的攻击。

We study the security of public keycryptosystems. In particular we study the RSA public key cryptosystem andseveral variants. We obtain our results using tools from the theory of integerlattices. We begin with an introduction to the theory of integer lattices anddescribe the main results to be used throughout the rest of the work. We thenreview the concept of a public key cryptosystem and in particular the RSApublic key cryptosystem. Next we introduce a novel algorithm for thefactorization of class of integers closely related to those used by RSA andother public key cryptosystems in the literature, showing that a new class ofintegers can be efficiently factored. We go on to introduce new attacks on theRSA public key cryptosystem which use partial knowledge of a user’s secret key,showing that leaking one quarter of the bits of the secret key is sufficient tocompromise RSA. Next we describe new attacks on the RSA public key cryptosystemwhen a short secret exponent is used. Lastly, we describe the threeSun-Yang-Laih key generation schemes for RSA, and introduce attacks to breaktwo of these schemes.

1. 引言
2. 点阵理论
3. 公钥密码
4. 点阵分解法
5. 部分**暴露攻击
6. 短秘密指数RSA的攻击
7. 对RSA变体的攻击
   附录A 模二次方程的解
   附录B 近似平方根
   附录C 短秘密指数的行列式
   附录D 定理6.3.1的证明
   附录E Sun-Yang-Laih方案的行列式

更多精彩文章请关注公众号：