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

劉向輝，韓文報(bào)，王 政，權(quán)建校

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

劉向輝1,2，韓文報(bào)1,2，王 政1,2，權(quán)建校3

(1. 解放軍信息工程大學(xué)四院，鄭州 450002；2. 數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，鄭州 450002； 3. 江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083)

RSA算法是目前應(yīng)用最廣泛的公鑰密碼體制之一，而格攻擊是針對(duì)RSA體制的一類(lèi)重要攻擊方法。為此，將RSA算法的部分私鑰泄漏問(wèn)題轉(zhuǎn)化為多變?cè)€性同余方程的求解問(wèn)題，基于同余方程構(gòu)造出特定的格，利用LLL格基約化算法進(jìn)行約化，從而以一定的概率求得同余方程的小根。以上述多變?cè)€性同余方程的小根求解技術(shù)為基礎(chǔ)，提出一種針對(duì)離散私鑰比特泄漏的RSA格攻擊方法。在該方法下，如果RSA算法的公鑰參數(shù)=N≤1/2，并且私鑰的未知部分N≤1/2–β，則能以高概率恢復(fù)出RSA算法的私鑰。通過(guò)NTL包對(duì)長(zhǎng)度為1 024 bit的大整數(shù)進(jìn)行實(shí)驗(yàn)，結(jié)果驗(yàn)證了該攻擊方法的有效性。

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

1 概述

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

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

早期的RSA私鑰泄漏攻擊都建立在文獻(xiàn)[2-3]求解多變?cè)７匠袒蛘咔蠼舛嘧冊(cè)囗?xiàng)式方程小根的基礎(chǔ)上，主要集中在私鑰的高位連續(xù)比特或者低位連續(xù)比特泄漏的情形。在實(shí)際環(huán)境中，攻擊者獲得的部分私鑰信息通常是不連續(xù)的，特別是旁道攻擊[7]的存在使得RSA體制離散比特私鑰泄露攻擊也顯得更有意義。文獻(xiàn)[8]通過(guò)構(gòu)造多變?cè)€性模方程并利用格基約化算法進(jìn)行求解，提出針對(duì)泄漏私鑰部分離散比特的攻擊方法，在泄漏私鑰的70%比特信息的條件下該方法能夠有效分解RSA的模數(shù)。文獻(xiàn)[9]利用變換多項(xiàng)式的格構(gòu)造方法給出針對(duì)私鑰指數(shù)的離散比特泄漏攻擊，但該方法要求格的維數(shù)較高。

本文通過(guò)構(gòu)造多變?cè)€性模方程，并利用典型的格構(gòu)造方法，針對(duì)RSA算法私鑰部分離散比特泄漏的情況進(jìn)行分析。在公鑰指數(shù)較小的條件下，如果泄漏私鑰的部分離散比特，則可以有效恢復(fù)出RSA算法的私鑰參數(shù)。

2 準(zhǔn)備知識(shí)

本節(jié)給出RSA格攻擊所用到的基礎(chǔ)知識(shí)，包括格的基本概念、Minkowski定理等格的基本理論以及LLL算法等格基約化算法，具體細(xì)節(jié)可參考文獻(xiàn)[10]。

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

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

本節(jié)根據(jù)RSA算法的已知信息建立多變?cè)€性同余方程，并利用格基約化算法對(duì)方程進(jìn)行求解，從而給出離散私鑰比特泄漏的RSA格攻擊方法。

方程的解為：

對(duì)于一般的多變?cè)€性同余方程，解的個(gè)數(shù)以及解的結(jié)構(gòu)是一個(gè)較困難的問(wèn)題，但是在某些限定條件下，能夠得到上述同余方程的唯一解。定理2給出了一種求解情況，能夠在一些限定條件下完成對(duì)RSA算法私鑰的恢復(fù)。

易求格的范數(shù)為：

注釋1 在證明過(guò)程中，省略小常數(shù)3，這是因?yàn)槌?shù)3相對(duì)于非常微小。如果是一個(gè)1 024 bit的大整數(shù)，小常數(shù)影響的指數(shù)為0.00 155，而且它并不隨著攻擊算法參數(shù)的改變而改變。于是為了計(jì)算方便，通常忽略這些小常數(shù)，并且它基本不影響攻擊算法的結(jié)果。

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

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

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

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

(2)根據(jù)定理2的證明對(duì)方程進(jìn)行變換并構(gòu)造格；

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

本文算法能夠有效恢復(fù)出離散私鑰比特泄漏情形的私鑰，本節(jié)對(duì)攻擊方法進(jìn)行實(shí)現(xiàn)，給出了部分實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)采用Intel Core2 Duo CPU E7500 2.93 GHz、2 GB內(nèi)存、Windows XP操作系統(tǒng)、C++編程語(yǔ)言、Visual Studio 2005編程環(huán)境。實(shí)驗(yàn)基本數(shù)據(jù)類(lèi)型以及部分函數(shù)使用NTL包5.5.2版本[12]。

隨機(jī)產(chǎn)生1 024 bit的大整數(shù)如下：

=89884656743115795386465259539451236680898848947115328636715040578866337902750481566354238661203768010560056939935696678829394884407208445324503014745709298151367448461125728029121649765323616136679383490070243049322387623086994912866587628961575922009245120828003518545377059539890024051847723277345174851613

選擇公鑰參數(shù)=65 537，并計(jì)算其私鑰參數(shù)：

=74675981359372092515712657756748721101081534514435134559284992133269975222072389952619979349454853909073866369617449879745836591028025167936105408347565173424220906961557338958448600530303116223128214181994791463002504381615405570121172373758673816534516868922306693487189599921278285735907955687259234560833

為描述方便，以下運(yùn)算選擇16進(jìn)制表示。私鑰參數(shù)的16進(jìn)制表示為：

=6a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a86a5795a8dda37444610e8ebd0bd2f42d0bd2f42d0bd2f42d0 bd2f42d0bd2f42d0bd2f42d0bd2f42d0bd2f42d0bd2f42d0bd2 f42d0bd2f42d0bd2f42d0bd2f42d0bd2f44e5fc14d425cb6eb41

顯然是一個(gè)1 024 bit的大整數(shù)。根據(jù)定理2，如果私鑰的未知比特?cái)?shù)小于490 bit，那么可以恢復(fù)私鑰。下文分2種情況進(jìn)行實(shí)驗(yàn)驗(yàn)證。

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

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

其中，*表示未知部分。那么可以建立一個(gè)雙變?cè)姆匠?，然后?gòu)造3變?cè)母駥?duì)其進(jìn)行求解，運(yùn)行LLL算法恢復(fù)出私鑰的未知比特。

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

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

其中，*表示未知部分。那么可以建立一個(gè)6變?cè)姆匠蹋缓髽?gòu)造7變?cè)母駥?duì)其進(jìn)行求解，運(yùn)行LLL算法恢復(fù)出私鑰的未知比特。

通過(guò)上述2個(gè)實(shí)驗(yàn)，本文算法能夠有效恢復(fù)出RSA算法的私鑰，并且由于算法使用的格非常小，整個(gè)攻擊過(guò)程在普通PC機(jī)上即可完成。

5 結(jié)束語(yǔ)

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

[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] 陳財(cái)森, 王 韜, 鄭媛媛, 等. RSA公鑰密碼算法的計(jì)時(shí)攻擊與防御[J]. 計(jì)算機(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] 劉向輝, 韓文報(bào), 孫 杰. 基于離散比特的RSA私鑰泄漏攻擊[J]. 信息工程大學(xué)學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61003291)；數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金資助項(xiàng)目(2013A03)。

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

2013-03-07

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

10.3969/j.issn.1000-3428.2014.03.033