針對離散私鑰比特泄漏的RSA格攻擊方法

劉向輝，韓文報，王 政，權建校

針對離散私鑰比特泄漏的RSA格攻擊方法

劉向輝1,2，韓文報1,2，王 政1,2，權建校3

(1. 解放軍信息工程大學四院，鄭州 450002；2. 數學工程與先進計算國家重點實驗室，鄭州 450002； 3. 江南計算技術研究所，江蘇 無錫 214083)

RSA算法是目前應用最廣泛的公鑰密碼體制之一，而格攻擊是針對RSA體制的一類重要攻擊方法。為此，將RSA算法的部分私鑰泄漏問題轉化為多變元線性同余方程的求解問題，基于同余方程構造出特定的格，利用LLL格基約化算法進行約化，從而以一定的概率求得同余方程的小根。以上述多變元線性同余方程的小根求解技術為基礎，提出一種針對離散私鑰比特泄漏的RSA格攻擊方法。在該方法下，如果RSA算法的公鑰參數=N≤1/2，并且私鑰的未知部分N≤1/2–β，則能以高概率恢復出RSA算法的私鑰。通過NTL包對長度為1 024 bit的大整數進行實驗，結果驗證了該攻擊方法的有效性。

RSA算法；格攻擊；離散私鑰比特泄漏；線性同余方程；小根；格基約化算法

1 概述

自1976年公鑰密碼的思想提出以來，各種公鑰密碼體制不斷涌現，但公認安全的且應用廣泛的卻并不多，其中較著名的是RSA公鑰密碼體制、ElGamal公鑰密碼體制和橢圓曲線公鑰密碼體制。而RSA公鑰密碼體制由于具有簡單易用、明密文長度相同等優點，在各種秘密通信中得到廣泛應用，一直是公鑰密碼學研究的熱點[1]。一般來講，公鑰密碼體制往往利用數學中已經得到證明的難題或公認的難題來設計方案，RSA算法就是建立在大數分解問題上的。目前，針對大數分解問題最好的通用攻擊算法是一般數域篩法，它是一個亞指數時間算法，在當前的計算能力下無法對實際使用的RSA模數進行分解。也就是說，在不借助其他條件下直接通過大數分解對RSA體制進行攻擊是困難的。

然而，在實際使用過程中可能會泄漏RSA體制的部分信息，例如泄漏私鑰或者的若干比特信息。同時，由于旁道攻擊等手段的發展，攻擊者往往能夠獲得部分密鑰信息。如何利用這些已知信息對RSA體制進行攻擊成為密碼學的一個重要研究課題。文獻[2-3]提出利用LLL算法求解整系數同余方程及多項式方程小根的方法，此后該方法被廣泛應用于RSA算法的私鑰泄漏攻擊中，例如，在泄漏私鑰的低/4比特，同時加密指數較小的條件下RSA的私鑰恢復[4]；在加密指數較大情況下的RSA部分私鑰泄漏攻擊等[5]；私鑰指數的連續比特泄漏攻擊等[6]。

早期的RSA私鑰泄漏攻擊都建立在文獻[2-3]求解多變元模方程或者求解多變元多項式方程小根的基礎上，主要集中在私鑰的高位連續比特或者低位連續比特泄漏的情形。在實際環境中，攻擊者獲得的部分私鑰信息通常是不連續的，特別是旁道攻擊[7]的存在使得RSA體制離散比特私鑰泄露攻擊也顯得更有意義。文獻[8]通過構造多變元線性模方程并利用格基約化算法進行求解，提出針對泄漏私鑰部分離散比特的攻擊方法，在泄漏私鑰的70%比特信息的條件下該方法能夠有效分解RSA的模數。文獻[9]利用變換多項式的格構造方法給出針對私鑰指數的離散比特泄漏攻擊，但該方法要求格的維數較高。

本文通過構造多變元線性模方程，并利用典型的格構造方法，針對RSA算法私鑰部分離散比特泄漏的情況進行分析。在公鑰指數較小的條件下，如果泄漏私鑰的部分離散比特，則可以有效恢復出RSA算法的私鑰參數。

2 準備知識

本節給出RSA格攻擊所用到的基礎知識，包括格的基本概念、Minkowski定理等格的基本理論以及LLL算法等格基約化算法，具體細節可參考文獻[10]。

顯然，一個格有多組基，在解決格上相關問題時，希望能找到一組特定的基有利于問題的解決，尋找這組基的過程就稱為格基約化，這組基就稱為約化基。擁有長度較短向量的基往往具有一些良好的性質，如何尋找具有短向量的基一直受到人們的關注。定理1給出了格中最短向量長度的上界。

3 一種離散私鑰比特泄漏的RSA格攻擊方法

本節根據RSA算法的已知信息建立多變元線性同余方程，并利用格基約化算法對方程進行求解，從而給出離散私鑰比特泄漏的RSA格攻擊方法。

方程的解為：

對于一般的多變元線性同余方程，解的個數以及解的結構是一個較困難的問題，但是在某些限定條件下，能夠得到上述同余方程的唯一解。定理2給出了一種求解情況，能夠在一些限定條件下完成對RSA算法私鑰的恢復。

易求格的范數為：

注釋1 在證明過程中，省略小常數3，這是因為常數3相對于非常微小。如果是一個1 024 bit的大整數，小常數影響的指數為0.00 155，而且它并不隨著攻擊算法參數的改變而改變。于是為了計算方便，通常忽略這些小常數，并且它基本不影響攻擊算法的結果。

注釋2格基約化算法通常采用LLL算法，它是一個多項式時間算法，這樣能夠在多項式時間內完成攻擊，而且LLL算法往往能夠得到需要的短向量。

注釋3定理2描述的攻擊方法是一個概率算法。也就是說，如果滿足已知條件，該方法并不能保證一定可以恢復出私鑰。但實際結果表明，該方法往往能夠得到方程的解并恢復出私鑰。

根據上述描述及定理2的證明，給出如下針對離散私鑰比特泄漏的RSA格攻擊算法。

算法離散私鑰比特泄漏的RSA格攻擊算法

(2)根據定理2的證明對方程進行變換并構造格；

(3)利用LLL算法求取格中的短向量；

(4)對短向量進行代入計算出原始方程的解；

(5)輸出私鑰未知比特塊的值。

4 實驗結果與分析

本文算法能夠有效恢復出離散私鑰比特泄漏情形的私鑰，本節對攻擊方法進行實現，給出了部分實驗結果。

實驗采用Intel Core2 Duo CPU E7500 2.93 GHz、2 GB內存、Windows XP操作系統、C++編程語言、Visual Studio 2005編程環境。實驗基本數據類型以及部分函數使用NTL包5.5.2版本[12]。

隨機產生1 024 bit的大整數如下：

=89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208445324503014745709298151367448461125728029121649765323616136679383490070243049322387623086994912866587628961575922009245120828003518545377059539890024051847723277345174851613

選擇公鑰參數=65 537，并計算其私鑰參數：

=74675981359372092515712657756748721101081534514435134559284992133269975222072389952619979349454853909073866369617449879745836591028025167936105408347565173424220906961557338958448600530303116223128214181994791463002504381615405570121172373758673816534516868922306693487189599921278285735907955687259234560833

為描述方便，以下運算選擇16進制表示。私鑰參數的16進制表示為：

=6a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a8dda37444610e8ebd0bd2f42d0bd2f42d0bd2f42d0 bd2f42d0bd2f42d0bd2f42d0bd2f42d0bd2f42d0bd2f42d0bd2 f42d0bd2f42d0bd2f42d0bd2f42d0bd2f44e5fc14d425cb6eb41

顯然是一個1 024 bit的大整數。根據定理2，如果私鑰的未知比特數小于490 bit，那么可以恢復私鑰。下文分2種情況進行實驗驗證。

情況1私鑰單未知比特塊未知。假設的第101比特~第580比特未知，也即：

=6a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a************************************************************************************************************************d0bd2f44e5fc14d425cb6eb41

其中，*表示未知部分。那么可以建立一個雙變元的方程，然后構造3變元的格對其進行求解，運行LLL算法恢復出私鑰的未知比特。

情況2私鑰多比特塊未知。選取5個比特塊未知，假設的第101比特~第180比特，第257比特~第356比特，第457比特~第556比特，第657比特~第756比特，第857比特~第956比特共480個比特信息未知，也即此時：

=6a5795a86a5795a86*************************5795a86a5795a86a5795a86a5*************************95a86a5795a86a5795a8dda37*************************2d0bd2f42d0bd2f42d0bd2f42*************************0bd2f42d0bd2f42d0bd********************d0bd2f44e5fc14d425cb6eb41

其中，*表示未知部分。那么可以建立一個6變元的方程，然后構造7變元的格對其進行求解，運行LLL算法恢復出私鑰的未知比特。

通過上述2個實驗，本文算法能夠有效恢復出RSA算法的私鑰，并且由于算法使用的格非常小，整個攻擊過程在普通PC機上即可完成。

5 結束語

隨著旁道攻擊等物理攻擊手段的不斷發展，RSA算法的私鑰泄漏攻擊越來越受到人們的重視。但是，由于離散比特的私鑰泄漏攻擊列方程及解方程的困難性，目前研究大多集中于泄漏私鑰的連續比特。本文對離散私鑰比特泄漏情形的RSA安全性進行了初步分析，利用多變元線性同余方程的典型求解算法，給出一種針對離散私鑰比特泄漏的RSA格攻擊方法。利用該方法攻擊者可以有效恢復RSA算法的私鑰參數。另一方面，本文分析結果還可以指導RSA算法在使用時選取安全的參數。然而，本文結果要求已知RSA算法有較多的私鑰比特，同時利用基本的格構造方法，雖然構造格的維數比較低，格基約化運算部分用時較少，但是該方法是概率性的，可能會有不成功的情形存在。因此，如何對本文方法進行改進是下一步研究的重點。

[1] Rivest R, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public Key Cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.

[2] Coppersmith D. Finding a Small Root of a Univariate Modular Equation[C]//Proceedings of EUROCRYPT’96. Berlin, Germany: Springer-Verlag, 1996: 155-165.

[3] Coppersmith D. Finding a Small Root of a Bivariate Integer Equation Factoring with High Bits Known[C]//Proceedings of EUROCRYPT’96. Berlin, Germany: Springer-Verlag, 1996: 178-189.

[4] Blomer J, May A. New Partial Key Exposure Attacks on RSA[C]//Proceedings of CRYPTO’03. Berlin, Germany: Springer-Verlag, 2003: 27-43.

[5] Ernst M, Jochemsz E, May A. Partial Key Exposure Attacks on RSA up to Full Size Exponents[C]//Proceedings of EUROCRYPT’05. Berlin, Germany: Springer-Verlag, 2005: 371-386.

[6] Santanu S. Some Results on Cryptanalysis of RSA and Fac- torization[D]. Kolkata, Indian: Indian Statistical Institute, 2011.

[7] 陳財森, 王 韜, 鄭媛媛, 等. RSA公鑰密碼算法的計時攻擊與防御[J]. 計算機工程, 2009, 35(2): 123-125.

[8] Herrman M. Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits[C]//Proceedings of ASIACRYPT’08. Berlin, Germany: Springer-Verlag, 2008: 406-424.

[9] 劉向輝, 韓文報, 孫 杰. 基于離散比特的RSA私鑰泄漏攻擊[J]. 信息工程大學學報, 2012, 13(4): 385-388.

[10] Nguyen P Q, Valle B. The LLL Algorithm: Survey and Applications[M]. Berlin, Germany: Springer Publishing Company, 2009.

[11] Lenstra A K, Lenstra H W, Lovasz L. Factoring Polynomials with Rational Coefficients[J]. Mathematiche Annalen, 1982, 261(4): 515-534.

[12] Shoup V. Number Theory Library(NTL) for C++[EB/OL]. (2010-05-16). http://www.shoup.net/ntl/.

編輯 陸燕菲

RSA Lattice Attack Method for Discrete Private Key Bit Leakage

LIU Xiang-hui1,2, HAN Wen-bao1,2, WANG Zheng1,2, QUAN Jian-xiao3

(1. The Fourth Institute, PLA Information Engineering University, Zhengzhou 450002, China; 2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450002, China; 3. Jiangnan Institute of Computing Technology, Wuxi 214083, China)

RSA algorithm is one of the most widely used public key cryptosystems at present and lattice attacks play an important role for the analysis of RSA system. The problem of partial discrete private key bit leakage is transformed into the solution of multivariate linear congruence equations and a special lattice is constructed. And then by the lattice reduction algorithms such as LLL algorithm, the small roots of multivariate linear congruence equations can be obtained with a high probability. Based on the above technology, this paper proposes a lattice attack method on RSA for discrete private key bit leakage. With this method, if the public parameter satisfies=N≤1/2and the unknown part of private keysatisfiesN≤1/2–β, it can recover the private keywith a high probability. The experiment on 1 024 bit number is given with NTL package and the results verify the availability of the attack method.

RSA algorithm; lattice attack; discrete private key bit leakage; linearcongruence equation; small root; lattice base reduction algorithm

1000-3428(2014)03-0163-04

A

TN918

國家自然科學基金資助項目(61003291)；數學工程與先進計算國家重點實驗室開放基金資助項目(2013A03)。

劉向輝(1984－)，男，博士研究生，主研方向：密碼學，信息安全；韓文報，教授、博士、博士生導師；王 政，副教授、博士；權建校，助理研究員、碩士。

2013-03-07

2013-04-07 E-mail：lxhkz2002@163.com

10.3969/j.issn.1000-3428.2014.03.033