一種基于維數縮減的單變元Coppersmith 算法*

趙春智，曹金政，程慶豐

信息工程大學網絡空間安全學院，鄭州450001

1 引言

1977 年，麻省理工學院的三名學者Rivest、Shamir 和Adleman[1]提出了著名的RSA 方案.RSA是世界上第一個完整的公鑰加密(public key encryption，PKE) 方案，它不僅可以用于加密，還可以用于數字簽名，并且簡單易實現.如今RSA 公鑰加密方案被廣泛應用于信息行業.1982 年，Lenstra 等人[2]提出了求解最短向量問題(shortest vector problem，SVP) 的LLL 算法.該算法是高斯算法在高維上的拓展，實際上是一個附加條件的整系數Gram-Schmidt 正交化過程，并且可以在多項式時間內得到一個較短的格向量.利用格的相關理論攻擊RSA 的思路起源于Coppersmith[3]在1996 年發表的一篇論文，該論文針對RSA 部分明文泄露的情況將恢復全部明文等價于求解一個單變元模方程，然后構造相應的格并通過LLL 算法求解格中較短向量來將該模方程轉化為整數環上的方程，最后利用整數環上求解多項式方程的一般方法進行高效求解.這篇論文的發表引發了國際密碼學界研究利用格基約化技術攻擊公鑰密碼系統的浪潮.隨后，Coppersmith[4]于1997 年對利用LLL 算法求解模多項式方程小根的方法進行了總結和完善.1999 年，Coupé[5]等人通過對針對低指數RSA 的Coppersmith 算法進行大量實驗，發現實驗中未知量上界接近于理論上界，進一步驗證了Coppersmith 算法的實用性.同時他們證實了當模數的大小超過未知量大小的e倍時，明文能夠通過Coppersmith 算法被有效恢復.2000 年，Boneh 和Durfee[6]在Coppersmith 算法的基礎上改善了Wiener 的低解密指數攻擊的效果，他們將解密指數d的上界提高到N0.292，即當d ＜N0.292時，攻擊者可以在多項……