RSA變型方案小解密指數攻擊的改進分析*

孫哲蕾,彭力強,胡 磊,王 強

1.北京空間飛行器總體設計部,北京100094

2.中國科學院信息工程研究所信息安全國家重點實驗室,北京100093

3.中國科學院數據與通信保護研究教育中心,北京100093

4.國家新聞出版廣電總局 廣播科學研究院,北京100866

1 引言

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

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

除了標準RSA 方案外,結合效率和安全等因素考慮,研究學者還設計了若干RSA 方案的變型方案,例如基于中國剩余定理的快速解密標準CRT-RSA 方案[2]、Prime Power RSA 方案[3]等.由于RSA 方案及其變型方案的廣泛應用,因此,關于它們的安全性也一直是密碼學中的重要研究方向.

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

1.1 背景知識

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

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

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

則模數N可以在多項式時間內被分解.

通過考慮素數p和q的規模,Bunder 等學者[17]進一步細化了定理1 的結果,并給出了一般情況下,即q

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

則模數N可以在多項式時間內被分解.

對于上述定理,若考慮一般情況下的加密指數e,即e的規模與N2一樣.并且假設d與Nβ有相同的比特長度,其中0 <β< 2.令p與Nγ的比特長度一樣,則q?N1?γ,有μ?N2γ?1.忽略與N無關的小系數,定理2 的結果可以描述為

即

1.2 我們的結果

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

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

為了更直觀地比較我們得到的結果與文獻[17]的結果,我們在圖1中描繪了這兩個式子所代表的區域,分別表示我們的方法與之前方法可以攻擊的可行參數區域.圖中虛線與橫坐標所圍成的區域代表文獻[17]的結果,實線與橫坐標所圍成的區域代表我們得到的結果.通過對比可以看出,我們的方法大幅度改進了先前的安全性分析結果.

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

注意到,在2016年,Peng 等學者[18]利用Coppersmith 方法改進了定理1的結果,即p和q的大小滿足與之前文獻[18]內容不同的是,本文考慮一般情況下,即p和q的規模是任意的.我們在多項式的選取中,充分利用p和q的大小關系,即γ的大小,盡可能多地選取有幫助的多項式,從而達到最優的結果.

2 預備知識

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

2.1 Coppersmith 方法

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

本節簡要回顧Coppersmith 方法.首先,我們介紹Coppersmith 方法中所用到的Howgrave-Graham[21]引理.

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

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

為了找到具有小范式的多項式,我們利用格以及L3格基約化算法.給定m個線性無關的向量由{w1,··· ,wm} 張成,是{w1,··· ,wm} 的所有整系數線性組合的集合,即

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

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

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

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

算法的運行時間為關于n以及格L的格基向量中向量長度最大值的多項式時間.

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

注意到,在Coppersmith 方法中,只有L3格基約化算法所輸出的向量對應的多項式相互之間代數獨立,我們才能夠通過計算結式或是Gr?bner 基求解方程根.在本文中,如同之前的關于Coppersmith 方法的工作一樣[7–12],我們假設這些多項式之間是代數獨立的,并且我們通過實驗結果驗證了我們的分析.

3 我們的分析結果

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

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

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

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

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

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

我們定義如下的坐標集合:

為了盡可能多地只選取有幫助多項式構造格,我們利用拆開的線性化技術[6],以及 Takayasu-Kunihiro[26]的轉化方法,格基矩陣可以轉化為三角矩陣,并且對角線上的元素為

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

另一方面,格L的維數為

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

綜上所述,我們可以得到如下結論,

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

則模數N可以在多項式時間內被分解.

3.2 考慮任意e 的情況

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

則模數N可以在多項式時間內被分解.此時,不妨設e?Nα,d?Nβ.進一步,Bunder 等學者的結果可以描述為

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

對于Coppersmith 方法,我們需要修改坐標集合為.

通過類似的計算,我們可以得到如下結論,

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

則模數N可以在多項式時間內被分解.

3.3 實驗結果

我們利用數學軟件Magma 2.11[28]實現了我們的分析,實驗環境為Windows 10 操作系統,2.50 GHz Intel(R)Core i7-6500 處理器,8 GB 內存.表1記錄了p在取不同規模大小情況下的實驗結果,其中我們選的模數N的長度為1000 比特.

表1 實驗結果Table 1 Experimental results

4 總結

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