李子臣　孫亞飛　楊亞濤　梁　斕　湯永利

1(西安電子科技大學(xué)通信工程學(xué)院　陜西 西安 710071) 2(北京印刷學(xué)院　北京 102600) 3(北京電子科技學(xué)院　北京 100070) 4(河南理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院　河南 焦作 454000)

0　引　言

RSA密碼算法是由Ron Rivest、Adi Shamir和Leonard Adleman[1]于1978年提出的著名公鑰密碼體制。目前關(guān)于RSA密碼算法的研究已經(jīng)相當(dāng)成熟，且廣泛應(yīng)用在多個(gè)行業(yè)內(nèi)。同時(shí)，也正是由于其應(yīng)用的廣泛性，有大量的研究人員對(duì)其算法進(jìn)行漏洞分析。傳統(tǒng)的數(shù)學(xué)分析方法包括：RSA小指數(shù)攻擊[2]、非共模攻擊及共模攻擊[3]、循環(huán)攻擊[4]等。有別于傳統(tǒng)攻擊方法的是文獻(xiàn)[5]提出的計(jì)時(shí)攻擊，也從此開辟了關(guān)于RSA的側(cè)信道攻擊。

近年來，國內(nèi)外針對(duì)RSA密碼算法的側(cè)信道攻擊與防御研究主要有：文獻(xiàn)[6]針對(duì)部分密鑰泄露，給出攻擊方法，并提出相應(yīng)的防御策略。文獻(xiàn)[7]指出常規(guī)的模冪運(yùn)算并不能達(dá)到其聲稱的抵抗計(jì)時(shí)攻擊效果。文獻(xiàn)[8]針對(duì)采用盲化策略的RSA密碼算法進(jìn)行能量攻擊，通過采用多條能量跡成功對(duì)RSA實(shí)現(xiàn)攻擊。

本文通過分析基于大整數(shù)分解困難問題及基于橢圓曲線離散對(duì)數(shù)問題的核心運(yùn)算，詳細(xì)介紹側(cè)信道攻擊中的計(jì)時(shí)攻擊與能量攻擊技術(shù)，結(jié)合運(yùn)算本身的性質(zhì)及側(cè)信道攻擊的關(guān)鍵點(diǎn)，提出一種隨機(jī)功耗的思想來提高密碼算法的安全性及效率。

與RSA類似的橢圓曲線公鑰密碼體制[9]，其核心運(yùn)算均為如下：y=mxmodn。為便于計(jì)算，針對(duì)此冪指數(shù)運(yùn)算，我們一般采用從左向右、從右向左及隨機(jī)指數(shù)三種方法進(jìn)行運(yùn)算。考慮到運(yùn)算效率，我們采用蒙哥馬利模乘器來加速其運(yùn)算。下面敘述從左向右、從右向左算法及隨機(jī)算法的蒙哥馬利實(shí)現(xiàn)算法。首先，計(jì)算x=ak(modn)，將k表示成二進(jìn)制形式k=(1kt-1…k1k0)2。

算法1從左向右算法

ak=(…((a2·akt-1)2·akt-2)2·…·ak1)2·ak0。

Input:t,k0,k1,…,kt-1,a,n

Setx=a

Fori=t-1,t-2,…,1,0repeat

Setx=x2(modn)

Ifki=1thensetx=xa(modn)

Output:x

算法2從右向左。

ak=a2t·((a2t-1)kt-1·…·((a22)k2·((a2)k1·(ak0·1)))…)。

Input:t,k0,k1,…,kt-1,a,n

Setx=1,y=a

Fori=0,1,…,t-1repeat

Ifki=1thensetx=xy(modn)

Sety=y2(modn)

Setx=xy(modn)

Output:x

算法3隨機(jī)指數(shù)。

Input:t,k0,k1,…,kt-1,a,n

Setx=1,y=a,z=random(1,n-2)

Fori=z,…,n-2repeat

Ifki=1thensetx=xy(modn)

Sety=y2(modn)

Setx=xy(modn)

Fori=z-1,…,0repeat

x=x2modn

Ifki=1thensetx=xy(modn)

Output:x

1　側(cè)信道攻擊及防御技術(shù)

通過上述模冪運(yùn)算，可知，當(dāng)對(duì)應(yīng)bit位為1的時(shí)候，與bit位為0相比較，多了一個(gè)乘法同余運(yùn)算。因此，其運(yùn)算時(shí)間和能量消耗明顯增多，利用此信息，能夠方便、快速、有效地實(shí)施計(jì)時(shí)攻擊及能量攻擊。

1.1　計(jì)時(shí)攻擊

計(jì)時(shí)攻擊[5]通過獲得一系列經(jīng)密碼芯片處理后的信息及處理時(shí)間，根據(jù)應(yīng)答時(shí)序差來進(jìn)行密鑰的推斷。計(jì)時(shí)攻擊模型如圖1所示。

圖1　計(jì)時(shí)攻擊模型

其中，m：消息，k：密鑰，S：輸出，A：算法。A(m,k)=m*k,*指算法，T：算法計(jì)算需要的時(shí)間，T(m,k)=t[A(m,k)]。

假定計(jì)算中密鑰恒定，且監(jiān)聽者已經(jīng)破解一組消息及計(jì)算時(shí)間T，現(xiàn)為了攻擊密鑰的第i個(gè)比特ki，當(dāng)監(jiān)聽者捕獲時(shí)間T(m,ki)，則可建立函數(shù)判斷比特位的值。

假定隨機(jī)變量v0,v1的分布是不同的，通過觀察實(shí)際的T(m,0)與T(m,1)的分布，則有可能推測(cè)出ki，進(jìn)而推測(cè)出完整的密鑰值。

1.2　能量攻擊

能量攻擊[10]主要有：簡單能量攻擊SPA(Simple Power Analysis)和差分能量攻擊DPA(Differential Power Analysis)。

簡單能量攻擊：通過分析硬件電路加密時(shí)釋放出的能量特征獲取與密鑰相關(guān)的信息，根據(jù)能量曲線的特征及分析者的經(jīng)驗(yàn)就可直觀分析出指令執(zhí)行的順序。程序運(yùn)行時(shí)，能量曲線有明顯的不同，通常情況下軌跡較寬且能量消耗較多對(duì)應(yīng)密鑰位“1”，否則，對(duì)應(yīng)密鑰位“0”。逐位逐比特對(duì)密鑰位進(jìn)行猜測(cè)，即可完成對(duì)算法的破譯。

差分能量攻擊：根據(jù)能量曲線的差分信號(hào)分析出所需的關(guān)鍵信息，并采集多組能量曲線及每條曲線對(duì)應(yīng)的明密文，需要大量的信息及一定的SPA分析經(jīng)驗(yàn)和長時(shí)間分析運(yùn)算。DPA需要采集多組能量曲線，將其作為先驗(yàn)函數(shù)，而將猜測(cè)的密鑰組根據(jù)一定規(guī)則進(jìn)行分類作為后驗(yàn)函數(shù)，通過找出兩組函數(shù)所具有信息量的相關(guān)性，若相關(guān)性強(qiáng)，則密鑰猜測(cè)正確，反之，重新采集數(shù)據(jù)并作比對(duì)。

1.3　防御措施

針對(duì)側(cè)信道攻擊技術(shù)的特點(diǎn)，主要是防御思想是通過增加冗余信息、延長算法執(zhí)行時(shí)間、加入固定(隨機(jī))噪聲及擾亂能量曲線等。常用的側(cè)信道攻擊防御措施主要有：掩碼技術(shù)[11]、功耗平衡技術(shù)[12]及功耗擾亂技術(shù)。其中掩碼技術(shù)分為布爾掩碼、多項(xiàng)式掩碼及內(nèi)積掩碼，都是通過變換掩蓋明文信息或中間結(jié)果，即使破譯成功，得到的也不是原始明文信息。功耗技術(shù)主要是通過增加時(shí)間或者能量的消耗，加大噪聲功率，減少信噪比，提高信息提取難度，從而達(dá)到防御目的。

2　隨機(jī)功耗算法實(shí)現(xiàn)

信息的泄露主要是由于時(shí)序差及能量的消耗所引起，理論上講，設(shè)計(jì)一種算法，增加執(zhí)行代碼，使得對(duì)于“0”和“1”執(zhí)行相同的動(dòng)作，這樣就能使得每一次計(jì)算消耗的能量就無法區(qū)分，且計(jì)算過程的時(shí)間相同。因此，通過此方法能很好地防御SPA和DPA。

根據(jù)上述基本思想，本文提出隨機(jī)功耗算法，并給出編碼實(shí)現(xiàn)如下,以從左向右算法為例：

對(duì)于計(jì)算x=ak(modn)，將k表示成二進(jìn)制形式k=(1kt-1…k1k0)2。

算法4從左向右隨機(jī)功耗算法

ak=(…((a2·akt-1)2·akt-2)2·…·ak1)2·ak0。

Input:t,k0,k1,…,kt-1,a,n

Setx=a

Fori=t-1,t-2,…,1,0repeat

Setx=x2(modn)

Ifki=1thensetx=xa(modn)

Ifr=random(0,1)=1thensetx=rx(modn)

Output:x

其中r=random(0,1)表示r為隨機(jī)從{0,1}中選取。對(duì)于從右向左及隨機(jī)算法，有類似的改進(jìn)。

3　方案分析

3.1　抗計(jì)時(shí)攻擊

在每輪的迭代運(yùn)算中，當(dāng)比特位不為1而隨機(jī)數(shù)r為1的時(shí)候，算法包含偽操作，耗時(shí)增加。由于隨機(jī)數(shù)的存在，造成時(shí)序差的混亂，即對(duì)于比特位為0的運(yùn)算，耗時(shí)是不固定的，同時(shí)也混淆了0和1的時(shí)間消耗，這樣攻擊者就無法通過對(duì)比迭代運(yùn)算的時(shí)序差獲取相應(yīng)的密鑰信息。

假設(shè)密鑰比特位出現(xiàn)“0”和“1”的概率是完全隨機(jī)的，對(duì)于全“0”字段，其對(duì)應(yīng)的操作是重復(fù)進(jìn)行的，由于隨機(jī)數(shù)的參與，或造成其消耗的時(shí)間類似于有比特位為1的運(yùn)算參與。攻擊者無法通過計(jì)時(shí)獲取密鑰的具體內(nèi)容。

綜合以上分析，本文提出的隨機(jī)功耗算法能夠有效地達(dá)到抗計(jì)時(shí)攻擊的目的。

3.2　抗能量攻擊

對(duì)于抗簡單能量攻擊：在隨機(jī)功耗算法中，當(dāng)滿足隨機(jī)數(shù)為1時(shí)，存在偽操作運(yùn)算。偽操作運(yùn)算在多精度算法相同的情況下，消耗的平均能量是相同，由于隨機(jī)數(shù)的存在，攻擊者無法根據(jù)全“0”時(shí)的曲線有效分析出原比特值。

雖說偽操作運(yùn)算在一定程度上會(huì)存在泄露信息的風(fēng)險(xiǎn)，但可以使用簡單的時(shí)序控制屏蔽信息泄露，加之隨機(jī)數(shù)的混淆作用，可以有效地防御SPA攻擊。

對(duì)于抗差分能量攻擊：差分能量攻擊能夠通過差分計(jì)算將噪聲和偽操作剔除，然后通過簡單能力分析即可破譯密碼。

隨機(jī)功耗算法則不同，由于當(dāng)偽隨機(jī)操作被過濾之后，攻擊者可以區(qū)分全“1”字段，然而這樣的字段概率是很小的。通過模冪運(yùn)算的操作步驟可知，密鑰比特位猜測(cè)的關(guān)鍵是本輪迭代中是否有乘同余操作，若有，則對(duì)應(yīng)指數(shù)為“1”，否則為“0”。平方剩余的計(jì)算則與指數(shù)位取值無關(guān)。

對(duì)于n比特長的密鑰，若要成功破譯密碼算法，則其關(guān)鍵是確定非全“0”指數(shù)段的取值。而這樣的情況有2n-1種，而對(duì)于比特位為“1”的字節(jié)，其每次計(jì)算消耗的能量也是隨機(jī)的，因此無法有效地區(qū)分取值。若要從相同的操作中分析出對(duì)應(yīng)比特位的具體值，則攻擊者需要采用高階攻擊的方法。導(dǎo)致所需采集和處理的數(shù)據(jù)呈指數(shù)增長，而根據(jù)文獻(xiàn)[13]的結(jié)果，三階以上的DPA實(shí)施起來都是相當(dāng)困難。

綜上所述，該隨機(jī)功耗算法能夠有效地混淆能量曲線，加大分析破譯難度。從而達(dá)到防御側(cè)信道攻擊的效果。

4　效率分析

本節(jié)從算法消耗的時(shí)間及運(yùn)行過程消耗的能量進(jìn)行分析。算法設(shè)計(jì)本身就是采用運(yùn)算效率較高的蒙哥馬利形式的算法，因此，運(yùn)算效率相比較傳統(tǒng)的算法[14]，有明顯的提高。

在運(yùn)行效率上，假設(shè)密鑰長度為n比特長，其中0、1各占50%，執(zhí)行一次模平方操作消耗的時(shí)間為T，一次模乘操作消耗時(shí)間為T。對(duì)于未加保護(hù)的原始方案，當(dāng)比特位為1時(shí)，需要執(zhí)行模平方與模乘計(jì)算，需要的執(zhí)行時(shí)間為n/2×(T+T)=nT；當(dāng)比特位為0時(shí)，僅有一次模乘運(yùn)算，需要的執(zhí)行時(shí)間為nT/2，共計(jì)需要執(zhí)行的時(shí)間為3nT/2。對(duì)于等功耗編碼的實(shí)現(xiàn)方式，當(dāng)比特位為1時(shí)，每次均需要執(zhí)行一次模平方計(jì)算和模乘計(jì)算，則需要執(zhí)行的時(shí)間為：n/2×(T+T)=nT；對(duì)于比特位為0時(shí)，每次計(jì)算時(shí)同樣需要執(zhí)行一次模平方計(jì)算和模乘計(jì)算，則需要執(zhí)行的時(shí)間為：n/2×(T+T)=nT，共計(jì)需要執(zhí)行的時(shí)間為2nT。針對(duì)本文提出的方法，當(dāng)比特位為1時(shí)，計(jì)算時(shí)間為n/2×(T+T)=nT，當(dāng)比特位為0時(shí)，有一半的需要執(zhí)行模平方操作，需要執(zhí)行時(shí)間為nT/2，另一半需要的時(shí)間為nT/4，因此，需要的總運(yùn)算時(shí)間為：nT+nT/2+nT/4=7nT/4。

在能量消耗方面，假設(shè)執(zhí)行一次模平方操作消耗能量為P/2，一次模乘操作消耗能量為P/2。對(duì)于未加保護(hù)的原始方案，當(dāng)比特位為1時(shí)，需要消耗的能量為nP，當(dāng)比特位為0時(shí)，均需要進(jìn)行模乘操作，需消耗能量為nP/2，共需消耗能量為3nP/2。等功耗編碼方式，對(duì)于所有的0比特位時(shí)，均執(zhí)行模平方操作，使得0比特位與1比特位消耗的能量相同，共需消耗能量為2nP，提高了方案的安全性，但是增大了能量的消耗。本文所提出的方案對(duì)比特位為0時(shí)進(jìn)行處理，當(dāng)比特位為0時(shí)，以一定的概率進(jìn)行模平方操作，假設(shè)n長比特中0、1各占50%，比特位為0的字節(jié)中，有50%的做模平方操作。當(dāng)比特位為0時(shí)，均需要進(jìn)行模乘操作，需消耗能量為nP/2，存在一半的比特位執(zhí)行模平方操作，即能量消耗為1/2×nP/2=nP/4，則共需消耗的能量為7nP/4。

通過分析比較，本文提出的方案，比原始方案增加了15%左右的時(shí)間和能耗開銷，但是提高了方案的安全性；對(duì)比等功耗編碼實(shí)現(xiàn)方式節(jié)省了15%左右的時(shí)間和能耗開銷，但同樣的能保證方案的安全性。針對(duì)目前RSA密碼算法的安全密鑰長度至少為2 048比特，文獻(xiàn)[12]中的算法至少增加1 000次模乘，而本文所設(shè)計(jì)的算法，與文獻(xiàn)[12]相比較節(jié)約了至少500次模乘，在效率上有大幅度的提高。

由此可以看出，改進(jìn)后的隨機(jī)功耗算法能夠有效地節(jié)省運(yùn)算時(shí)間，提高執(zhí)行效率。同時(shí)，也正是由于隨機(jī)數(shù)的引入，對(duì)能量的消耗起到一個(gè)很好的混淆效果，使得能量攻擊難度加大。表1給出本文算法與蒙哥馬利算法及靜態(tài)掩蓋法的效率對(duì)比。

表1　算法效率對(duì)比分析

其中，P為消耗的單位能量。

5　結(jié)　語

本文通過設(shè)計(jì)一種隨機(jī)功耗算法，既能提高模冪運(yùn)算的安全性，同時(shí)還能保證其效率相對(duì)較高。該算法能夠有效地抵抗計(jì)時(shí)攻擊及能量攻擊，在運(yùn)行效率上，能夠提高15%左右；在功耗上能夠節(jié)省15%左右。該方法便于應(yīng)用在橢圓曲線公鑰密碼體制，對(duì)所有涉及模冪運(yùn)算的算法都有一定的借鑒意義。

[1] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the Acm, 1978, 26(2):96-99.

[2] 韓立東,王小云,許光午. RSA密碼系統(tǒng)小CRT解密指數(shù)的攻擊分析[J]. 中國科學(xué):信息科學(xué),2011,41(2):173-180.

[3] Zou H. An Prime Generating Scheme to Avoid Effectively Common Modulus Attack on RSA[J]. Computer Engineering & Applications, 2004, 40(27):88-91.

[4] 姜正濤,懷進(jìn)鵬,王育民. RSA推廣循環(huán)攻擊實(shí)效性與弱模問題的研究與分析[J]. 通信學(xué)報(bào),2009,30(6):70-74.

[5] Kocher P C. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[C]//International Cryptology Conference on Advances in Cryptology. Springer-Verlag, 1996:104-113.

[6] Cimato S, Mella S, Susella R. Partial Key Exposure Attacks on RSA with Exponent Blinding[C]//International Conference on E-Business and Telecommunications. Springer International Publishing, 2015:364-385.

[7] Schindler W. Exclusive Exponent Blinding May Not Suffice to Prevent Timing Attacks on RSA[M]//Cryptographic Hardware and Embedded Systems-CHES 2015. Springer Berlin Heidelberg, 2015: 229-247.

[8] Schindler W, Wiemers A. Power attacks in the presence of exponent blinding[J]. Journal of Cryptographic Engineering, 2014, 4(4):213-236.

[9] Menezes A J. Elliptic Curve Public Key Cryptography[J]. International Course on the State of the Art & Evolution of Computer Security & Industrial Cryptography Location Leuven Be Date, 1993(3):76-79.

[10] Kocher P, Jaffe J, Jun B. Differential Power Analysis[C]//International Cryptology Conference on Advances in Cryptology. Springer-Verlag, 1999:388-397.

[11] 任燕婷,烏力吉,李翔宇,等. 抗攻擊低功耗RSA處理器設(shè)計(jì)與實(shí)現(xiàn)[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,56(1):1-6.

[12] 陳運(yùn),吳震,陳俊,等. 防范邊信道攻擊的等功耗編碼實(shí)現(xiàn)算法[J]. 電子科技大學(xué)學(xué)報(bào),2008,37(2):168-171.

[13] Gebotys C H. A table masking countermeasure for low-energy secure embedded systems[J]. IEEE Transactions on Very Large Scale Integration Systems, 2006, 14(7):740-753.

[14] 陳運(yùn),龔耀寰. 大數(shù)冪剩余的二進(jìn)制冗余數(shù)Montgomery算法[J]. 電子科技大學(xué)學(xué)報(bào),2000,29(6):587-590.