RSA變型方案小解密指數(shù)攻擊的改進(jìn)分析*

孫哲蕾,彭力強(qiáng),胡 磊,王 強(qiáng)

1.北京空間飛行器總體設(shè)計(jì)部,北京100094

2.中國(guó)科學(xué)院信息工程研究所信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室,北京100093

3.中國(guó)科學(xué)院數(shù)據(jù)與通信保護(hù)研究教育中心,北京100093

4.國(guó)家新聞出版廣電總局 廣播科學(xué)研究院,北京100866

1 引言

利用大整數(shù)因子分解問(wèn)題的困難性,Rivest、Shamir和Adleman[1]在1978年提出了著名的RSA公鑰加密體制.自提出以來(lái),RSA 方案得到了廣泛的應(yīng)用和研究,它有效地解決了信息安全中數(shù)字簽名、密鑰共享等問(wèn)題,是保障實(shí)際網(wǎng)絡(luò)中密鑰管理以及數(shù)字簽名應(yīng)用最為廣泛的的公鑰算法之一.為了方便后面描述,我們首先回顧標(biāo)準(zhǔn)RSA 方案的密鑰生成過(guò)程.

RSA 的密鑰生成算法:隨機(jī)生成兩個(gè)不同的且比特長(zhǎng)度相同的素?cái)?shù)p和q,N=pq為RSA 的模數(shù).隨機(jī)選取滿足gcd(e,?(N))=1 的正整數(shù)e,其中?(N)=(p?1)(q?1),并通過(guò)擴(kuò)展歐幾里得算法計(jì)算得到d,使得ed=1(mod?(N)).RSA 公鑰加密方案的公鑰為(N,e),私鑰為(p,q,d).

除了標(biāo)準(zhǔn)RSA 方案外,結(jié)合效率和安全等因素考慮,研究學(xué)者還設(shè)計(jì)了若干RSA 方案的變型方案,例如基于中國(guó)剩余定理的快速解密標(biāo)準(zhǔn)CRT-RSA 方案[2]、Prime Power RSA 方案[3]等.由于RSA 方案及其變型方案的廣泛應(yīng)用,因此,關(guān)于它們的安全性也一直是密碼學(xué)中的重要研究方向.

RSA方案的小解密指數(shù)攻擊:1990年,Wiener[4]利用連分式方法,提出了在d

1.1 背景知識(shí)

1995年,Kuwakado 等人[13]提出了一種基于奇異三次曲線y2≡x3+bx2(modN)的RSA 型方案,其中N=pq為模數(shù).與標(biāo)準(zhǔn)RSA 方案不同的是,Kuwakado-Koyama-Tsuruoka 方案中的公鑰e和私鑰d滿足ed=1(mod(p2?1)(q2?1)).2002年,Elkamchouchi 等人[14]將RSA 方案擴(kuò)展到高斯整數(shù)環(huán),與Kuwakado-Koyama-Tsuruoka 方案類似,公鑰e和私鑰d也滿足ed=1(mod(p2?1)(q2?1)).類似地,Castagnos[15]在2007年提出了一種基于RSA 模數(shù)的概率方案,該方案中同樣包括了與上述兩方案[13,14]同樣的模方程.因此,如何從模方程ed=1(mod(p2?1)(q2?1))中恢復(fù)出未知變量d,p,q是值得關(guān)注的問(wèn)題.

2016年,Bunder 等人[16]利用連分式方法提出了關(guān)于上述三種方案的小解密指數(shù)d的恢復(fù)攻擊,結(jié)果如下.

定理1令(N,e)為Kuwakado-Koyama-Tsuruoka 方案、高斯整數(shù)RSA 方案,或是Castagnos 方案的公鑰,其中N=pq以及q

則模數(shù)N可以在多項(xiàng)式時(shí)間內(nèi)被分解.

通過(guò)考慮素?cái)?shù)p和q的規(guī)模,Bunder 等學(xué)者[17]進(jìn)一步細(xì)化了定理1 的結(jié)果,并給出了一般情況下,即q

定理2令(N,e)為Kuwakado-Koyama-Tsuruoka 方案、高斯整數(shù)RSA 方案,或是Castagnos 方案的公鑰,其中N=pq以及q

則模數(shù)N可以在多項(xiàng)式時(shí)間內(nèi)被分解.

對(duì)于上述定理,若考慮一般情況下的加密指數(shù)e,即e的規(guī)模與N2一樣.并且假設(shè)d與Nβ有相同的比特長(zhǎng)度,其中0 <β< 2.令p與Nγ的比特長(zhǎng)度一樣,則q?N1?γ,有μ?N2γ?1.忽略與N無(wú)關(guān)的小系數(shù),定理2 的結(jié)果可以描述為

即

1.2 我們的結(jié)果

在本文中,我們首先通過(guò)關(guān)系式ed=1(mod(p2?1)(q2?1)),即ed=1+k(p2?1)(q2?1)構(gòu)造模方程,

其中,k為未知的正整數(shù).之后,我們利用Coppersmith 方法求解上述模方程的一組根(k,?p2,?q2).具體地說(shuō),在應(yīng)用基于格基算法實(shí)現(xiàn)的Coppersmith時(shí),我們選取了若干多項(xiàng)式來(lái)構(gòu)造格基矩陣,并且通過(guò)參數(shù)的設(shè)置,將未知變量的大小考慮在多項(xiàng)式的選取優(yōu)化中.最終,我們將之前的結(jié)果β<1?γ提高到

為了更直觀地比較我們得到的結(jié)果與文獻(xiàn)[17]的結(jié)果,我們?cè)趫D1中描繪了這兩個(gè)式子所代表的區(qū)域,分別表示我們的方法與之前方法可以攻擊的可行參數(shù)區(qū)域.圖中虛線與橫坐標(biāo)所圍成的區(qū)域代表文獻(xiàn)[17]的結(jié)果,實(shí)線與橫坐標(biāo)所圍成的區(qū)域代表我們得到的結(jié)果.通過(guò)對(duì)比可以看出,我們的方法大幅度改進(jìn)了先前的安全性分析結(jié)果.

圖1 Kuwakado-Koyama-Tsuruoka 等RSA 變型方案的小解密指數(shù)安全性分析結(jié)果對(duì)比Figure 1 Analysis of small decryption exponent on several RSA variant schemes

注意到,在2016年,Peng 等學(xué)者[18]利用Coppersmith 方法改進(jìn)了定理1的結(jié)果,即p和q的大小滿足與之前文獻(xiàn)[18]內(nèi)容不同的是,本文考慮一般情況下,即p和q的規(guī)模是任意的.我們?cè)诙囗?xiàng)式的選取中,充分利用p和q的大小關(guān)系,即γ的大小,盡可能多地選取有幫助的多項(xiàng)式,從而達(dá)到最優(yōu)的結(jié)果.

2 預(yù)備知識(shí)

在本節(jié)中,我們簡(jiǎn)要介紹下基于格基約化算法Coppersmith 方法的原理,以及格的一些相關(guān)概念.

2.1 Coppersmith 方法

令h(x1,··· ,xr)=0(modW)為一個(gè)模方程,其中X1,··· ,Xr為該模方程要求解的根的絕對(duì)值的上界.相較于W,如果的值足夠小,那么我們可以利用基于格的Coppersmith 方法在多項(xiàng)式時(shí)間內(nèi)求解出所有的根該方法是由Coppersmith[19,20]在1996年首次提出的,它可以在多項(xiàng)式時(shí)間內(nèi)求解模數(shù)分解未知的單變量模方程小根以及雙變量整方程小根.之后,Howgrave-Graham[21]以及Coron[22]分別重新描述了Coppersmith 的工作[19,20],使得Coppersmith 方法便于理解及應(yīng)用.2006年,Jochemsz和May[23]進(jìn)一步給出了求解任意形式的多變量模方程或是整方程的一般性方法,使得Coppersmith 方法成為了研究公鑰密碼體制安全性的重要工具,尤其是關(guān)于RSA 方案及其變型方案安全性的研究.

本節(jié)簡(jiǎn)要回顧C(jī)oppersmith 方法.首先,我們介紹Coppersmith 方法中所用到的Howgrave-Graham[21]引理.

引理1（Howgrave-Graham[21])給定多變量方程Z[x1,··· ,xk],并且g(x1,··· ,xk)中至多有n個(gè)單項(xiàng)式.若如下兩個(gè)條件同時(shí)成立

由如上引理可以看出,一旦上述條件滿足,我們就可以將一個(gè)模方程的根轉(zhuǎn)化為一個(gè)方程在整數(shù)上的根,并通過(guò)求解方程在整數(shù)上的根來(lái)恢復(fù)模方程的根.詳細(xì)地說(shuō),為了求解k元的模方程h(x1,··· ,xk)=0(modp)的一組根我們需要找到k個(gè)多項(xiàng)式其中也是這些模方程的根,并且這些模方程系數(shù)的范式足夠小,使得Howgrave-Graham 引理的條件成立,從而將求解這些模方程的小根轉(zhuǎn)化為求解方程在整數(shù)上的根.

為了找到具有小范式的多項(xiàng)式,我們利用格以及L3格基約化算法.給定m個(gè)線性無(wú)關(guān)的向量由{w1,··· ,wm} 張成,是{w1,··· ,wm} 的所有整系數(shù)線性組合的集合,即

這里,我們稱w1,··· ,wm為格L的一組格基.另外,如果我們定義由w1,··· ,wm為行的矩陣為W∈Rm×n,格的定義也可以寫成是由矩陣W生成的格,記為

當(dāng)m=n時(shí),L(W)稱為滿秩格,這也是較為常用的格.格的行列式定義為如果格為滿秩格,即W為方陣,我們有det(L(W))=|det(W)|.在本文中我們所構(gòu)造的格均為滿秩格,并且我們所構(gòu)造的格為三角矩陣,因此我們可以簡(jiǎn)單地通過(guò)計(jì)算所有對(duì)角線上項(xiàng)的乘積得到格的行列式.

格已經(jīng)被廣泛應(yīng)用到密碼學(xué)的研究中,如何求解格的非零短向量是其中的關(guān)鍵問(wèn)題之一.L3格基約化算法是由A.K.Lenstra、H.W.Lenstra 以及L.Lovász[24]在1982年提出的,它可以在多項(xiàng)式時(shí)間內(nèi)解決指數(shù)因子的尋找近似最短向量問(wèn)題,

引理2(L3[24])格L是一個(gè)維度為n的格.對(duì)格L應(yīng)用L3格基約化算法,輸出的約化基向量v1,··· ,vn滿足

算法的運(yùn)行時(shí)間為關(guān)于n以及格L的格基向量中向量長(zhǎng)度最大值的多項(xiàng)式時(shí)間.

現(xiàn)在,我們可以根據(jù)上述兩個(gè)引理來(lái)解釋Coppersmith 方法是如何求解模方程h(x1,··· ,xk)=0(modp)的根首先,構(gòu)造n個(gè)多項(xiàng)式h1(x1,··· ,xk),··· ,hn(x1,··· ,xk),并且這些多項(xiàng)式在模pm下的根都為其中m為自己選定的正整數(shù).接下來(lái),構(gòu)造格L,其格基矩陣的行向量為所有多項(xiàng)式h1(x1X1,··· ,xkXk),··· ,hn(x1X1,··· ,xkXk)的系數(shù)向量.由于格L中的所有向量均可以表示為格基向量的整系數(shù)線性組合,因此為格中的任一向量所代表的多項(xiàng)式在模pm下的根.對(duì)格L應(yīng)用L3格基約化算法,可以得到k個(gè)L3約化基向量,對(duì)應(yīng)的多項(xiàng)式為一旦不等式det(L)1/n

注意到,在Coppersmith 方法中,只有L3格基約化算法所輸出的向量對(duì)應(yīng)的多項(xiàng)式相互之間代數(shù)獨(dú)立,我們才能夠通過(guò)計(jì)算結(jié)式或是Gr?bner 基求解方程根.在本文中,如同之前的關(guān)于Coppersmith 方法的工作一樣[7–12],我們假設(shè)這些多項(xiàng)式之間是代數(shù)獨(dú)立的,并且我們通過(guò)實(shí)驗(yàn)結(jié)果驗(yàn)證了我們的分析.

3 我們的分析結(jié)果

在本節(jié)中,我們分析Kuwakado-Koyama-Tsuruoka 等三種RSA 變形方案的小解密指數(shù)的安全性.我們首先考慮的情況.

由ed=1(mod(p2?1)(q2?1)),我們得到如下方程,

其中,k∈N.問(wèn)題轉(zhuǎn)化為求解如下模方程的根(k,?p2,?q2).下面,我們估計(jì)根的大小.因?yàn)镹=pq,且d與Nβ有相同的比特長(zhǎng)度,e與N2的規(guī)模相同,其中0 <β< 2.令p與Nγ的比特長(zhǎng)度一樣,則q?N1?γ.進(jìn)一步,此時(shí)我們有

令X(:=Nβ),Y(:=N2γ)和Z(:=N2(1?γ))分別為根(k,?p2,?q2)的上界.注意到,未知變量之間存在代數(shù)關(guān)系yz=N2.

為了求解f(x,y,z)=0 mode,我們利用Takayasu-Kunihiro[25]的格構(gòu)造方法,盡可能多地選取有幫助多項(xiàng)式,增大可求解根的范圍.所選取多項(xiàng)式如下:

其中,m為正整數(shù).對(duì)于任意的非負(fù)整數(shù)u,i,v,k1以及k2,(x,y,z)=(k,?p2,?q2)為所有選取多項(xiàng)式在模em下的根.

我們定義如下的坐標(biāo)集合:

為了盡可能多地只選取有幫助多項(xiàng)式構(gòu)造格,我們利用拆開的線性化技術(shù)[6],以及 Takayasu-Kunihiro[26]的轉(zhuǎn)化方法,格基矩陣可以轉(zhuǎn)化為三角矩陣,并且對(duì)角線上的元素為

由此可以看出,我們通過(guò)坐標(biāo)集合Ix,Iy以及Iz所選取的多項(xiàng)式均是有幫助多項(xiàng)式.另外,在本節(jié)中我們考慮γ值較小,即的情況,否則集合Iy為空集.因此,我們可以通過(guò)計(jì)算對(duì)角線上元素的乘積得到格的行列式其中,

另一方面,格L的維數(shù)為

根據(jù)引理1與引理2,并且忽略m的小項(xiàng)o(m3),若滿足det(L)1/n

綜上所述,我們可以得到如下結(jié)論,

定理3令(N,e)為Kuwakado-Koyama-Tsuruoka 方案、高斯整數(shù)RSA 方案,或是Castagnos 方案中的公鑰,其中N=pq以及ed≡1(mod(p2?1)(q2?1)).假設(shè)e,d分別與N2和Nβ有相同的比特長(zhǎng)度,其中0<β<2.令p與Nγ的比特長(zhǎng)度一樣,其中則q?N1?γ,若滿足

則模數(shù)N可以在多項(xiàng)式時(shí)間內(nèi)被分解.

3.2 考慮任意e 的情況

在本小節(jié),我們考慮任意情況下的e.首先,回顧Bunder 等學(xué)者[17]的結(jié)果.若公鑰e<(p2?1)(q2?1)滿足

則模數(shù)N可以在多項(xiàng)式時(shí)間內(nèi)被分解.此時(shí),不妨設(shè)e?Nα,d?Nβ.進(jìn)一步,Bunder 等學(xué)者的結(jié)果可以描述為

我們注意到,Bunder 等學(xué)者的結(jié)果并不嚴(yán)謹(jǐn),需要添加限制條件.因?yàn)?ed=1(mod(p2?1)(q2?1)),即α+β>2.這意味著因此,Bunder 等學(xué)者的結(jié)果應(yīng)為

對(duì)于Coppersmith 方法,我們需要修改坐標(biāo)集合為.

通過(guò)類似的計(jì)算,我們可以得到如下結(jié)論,

推論1令(N,e)為Kuwakado-Koyama-Tsuruoka 方案、高斯整數(shù)RSA 方案,或是Castagnos 方案中的公鑰,其中N=pq以及ed≡1(mod(p2?1)(q2?1)).假設(shè)e,d分別與Nα和Nβ有相同的比特長(zhǎng)度,其中0<β<2.令p與Nγ的比特長(zhǎng)度一樣,其中則若滿足

則模數(shù)N可以在多項(xiàng)式時(shí)間內(nèi)被分解.

3.3 實(shí)驗(yàn)結(jié)果

我們利用數(shù)學(xué)軟件Magma 2.11[28]實(shí)現(xiàn)了我們的分析,實(shí)驗(yàn)環(huán)境為Windows 10 操作系統(tǒng),2.50 GHz Intel(R)Core i7-6500 處理器,8 GB 內(nèi)存.表1記錄了p在取不同規(guī)模大小情況下的實(shí)驗(yàn)結(jié)果,其中我們選的模數(shù)N的長(zhǎng)度為1000 比特.

表1 實(shí)驗(yàn)結(jié)果Table 1 Experimental results

4 總結(jié)

在本文中,我們利用Coppersmith 方法改進(jìn)了Bunder 等人的分析結(jié)果,擴(kuò)大了三種變型RSA 方案小解密指數(shù)攻擊的參數(shù)范圍.對(duì)于模方程ed≡1 mod(p2?1)(q2?1)中的未知變量的求解,我們?cè)跇?gòu)造格時(shí),通過(guò)添加額外的參數(shù)使得p和q在不同規(guī)模下,盡可能優(yōu)化格的構(gòu)造,提升了之前結(jié)果.