趙躍華，趙 加，韓 牟

(江蘇大學計算機科學與通信工程學院，江蘇 鎮(zhèn)江 212013)

1 概述

隨著密碼算法的完善，傳統(tǒng)的線性和差分分析已經(jīng)很難實現(xiàn)密碼破譯。而專用集成電路(Application Specific Integrated Circuit,ASIC)、現(xiàn)場可編程門陣列(Field Programmable Gate Array,FPGA)、數(shù)字信號處理(Digital Signal Processing,DSP)以及智能卡等密碼算法芯片的大量普及應(yīng)用，研究者越來越注意到利用實現(xiàn)和操作環(huán)境泄露的時間、能量、電磁等信息進行攻擊的可能性。利用這些泄漏的信息對密碼算法進行分析的方法稱為側(cè)信道攻擊(Side Channel Attack,SCA)，其主要的攻擊類型有時間攻擊[1]和能量分析[2]攻擊等。

RSA 算法作為公鑰密碼體系的核心算法之一，廣泛應(yīng)用于各種嵌入式密碼系統(tǒng)，但其在實現(xiàn)過程中卻易遭受側(cè)信道攻擊[3-4]。針對該問題，國內(nèi)外研究人員提出了許多RSA的側(cè)信道攻擊及抗側(cè)信道攻擊方法[5-6]。文獻[7]提出功耗軌跡分析方法和添加隨機偽操作方法防御SCA，但該方法會泄露密鑰中的部分比特位為0 的信息，且額外計算量較大；文獻[8]提出等功耗編碼方法能使算法效率提高，但全零段極易受到SCA，且增加了預計算過程；文獻[9]改進了文獻[8]全零段的抗攻擊弱點，但預計算量仍未降低。本文對這些防御方法進行簡單介紹，并針對時間和能量分析攻擊，在改進的等功耗編碼算法[9]的基礎(chǔ)上，提出一種針對RSA抗側(cè)信道攻擊的改進窗口算法。

2 RSA 的實現(xiàn)算法及抗側(cè)信道攻擊分析

2.1 RSA 的實現(xiàn)算法

算法1 從左到右掃描的模冪(LR)M=Cdmod N

輸入 正整數(shù)N，密文C，整數(shù)d=(dndn-1…d0)2

輸出 M

2.2 RSA 模冪算法的側(cè)信道攻擊及其防御措施

由上述模冪運算過程可以看出，當d 的二進制bit 位為0 時，僅有平方操作；而d 的bit 位為1 時，運算過程包括平方和乘法操作，2 個不同bit 位運行時間存在明顯差異。因此，可以利用密碼算法執(zhí)行時間差異進行時間攻擊[1]。

能量分析攻擊可以分為簡單能量分析(Simple Power Analysis,SPA)攻擊和差分能量分析(Differential Power Analysis,DPA)攻擊。SPA 攻擊在攻擊者對算法本身特性有一定了解的前提下，通過觀察功耗軌跡[7]，結(jié)合時間攻擊，加之一定的經(jīng)驗來猜測密鑰。差分能量分析攻擊可以通過區(qū)分函數(shù)濾除偽操作和固定噪聲，根據(jù)能量差分曲線是否會出現(xiàn)明顯的尖峰來判斷猜測的密鑰是否正確，從而破譯密鑰[2]。LR 模冪算法16 位RSA 不同bit 位的功率軌跡如圖1 所示。

圖1 LR 模冪算法16 位RSA 不同bit 位的功率軌跡

對時間攻擊應(yīng)用最廣泛的防御方法是盲化技術(shù)[10-11]，可以防止攻擊者一位一位地進行分析。RSA 數(shù)據(jù)安全公司聲稱由于使用了盲化技術(shù)，運算性能降低了2%～10%。

對于能量分析攻擊的防御，文獻[7]提出添加隨機偽操作方法，算法如下：

算法2 添加隨機偽操作的從左到右掃描的模冪(LR)

輸入 正整數(shù)N、W，密文C，整數(shù)d=(dndn-1…d0)2

輸出 M

雖然算法2在運算效率上比直接添加偽操作的LR模冪運算算法有所提高[7]，但它的執(zhí)行效率仍較低。因此，文獻[9]在此算法及文獻[8]的基礎(chǔ)上提出了改進的等功耗編碼算法[9]。

算法3 改進的等功耗編碼算法

輸出 M

Step1 預計算

Step1.1 R0←1

Step1.2 對于i 從1 增加到2k-1，執(zhí)行：Ri←Ri-1×C mod N(有Ri=Cimod N)

Step2 M←1

Step3 對于j 從s 遞減到0，執(zhí)行：

Step3.1 M←M2kmod N

Step3.2 若dj≠0，M←M×Rdjmod N

否則，U←M×Rand(R)mod N

Step4 返回(M)。

其中，Rand(R)為余數(shù)表中的隨機抽取的一個數(shù)。雖然算法3 解決了文獻[8]中全零段抗攻擊弱點，但預計算量仍未減少。

3 實現(xiàn)RSA 模冪運算的改進窗口算法

3.1 算法介紹

由于算法3 每次預計算是在前一個余數(shù)的基礎(chǔ)上處理C 的一次方，產(chǎn)生連續(xù)余數(shù)表，因此所用的乘法為2k-3 個。研究后發(fā)現(xiàn)，可以對預計算過程進行優(yōu)化，每次預計算處理C 的二次方，產(chǎn)生C 奇次冪的余數(shù)表，將乘法與求平方之間的平衡轉(zhuǎn)換到更為有利的求平方過程中，只需要將預計算余數(shù)表中的奇次冪進行預先計算和存儲。因此，本文算法的乘法僅需2k-1-1 個，預計算的乘法運算量減少了一半，使得RSA 實現(xiàn)過程在有效地抵御時間攻擊和能量分析攻擊的同時，能夠提高運算速度。

算法4 從左到右的改進窗口模冪運算

輸入 正整數(shù)N、k，密文C，整數(shù)d=(dsds-1…d0)b，dj=2hjuj，0≤j≤s，其中，uj是奇數(shù)；若dj=0，則hj=0,uj=0

輸出 M

Step1 預計算

Step1.1 R0←1,R1←C,R2←C2mod N

Step1.2 對于i 從1 到2k-1-1，執(zhí)行：R2i+1←R2i-1×R2mod N

Step2 M←1

Step3 對于j 從s 遞減到0，執(zhí)行：

Step4 返回M。

其中，Rand(R)同算法3，為余數(shù)表中隨機抽取的數(shù)；h 為1～(k-1)之間的隨機數(shù)。

在算法3 中，當dj=0 時，計算結(jié)果存儲到中間變量U中，不影響結(jié)果的輸出；dj≠0 時，每輪迭代輸出結(jié)果M =M2k×Rdj=M2k×Cdj。同理，在算法4 中，dj=0 時，計算結(jié)果也存儲到中間變量U 中，不影響輸出；dj≠0 時，得到M =M2k×(Ruj)2hj=M2k×(Cuj)2hj=M2k×C2hjuj=M2k×Cdj。2 個算法的輸出結(jié)果一致，因此，算法4 是正確的。

3.2 改進窗口算法的蒙哥馬利實現(xiàn)形式

由于除法運算比加減乘運算要費時得多，從降低或避免除法使用角度考慮，將算法4 與只需用乘法和數(shù)的位移就可實現(xiàn)模冪運算的蒙哥馬利算法結(jié)合，從而得到算法5，進一步加快模冪算法的運行速度。

定義蒙哥馬利約減為：MontRed(A,N,r)=Ar-1mod N；蒙哥馬利模乘為：MontPro(A,B,N,r)=ABr-1mod N；其中，r=bn，bn-1≤N＜bn。

算法5 使用蒙哥馬利實現(xiàn)的從左到右改進窗口模冪運算

輸入 正整數(shù)N、k，密文C，d=(dsds-1…d0)b

輸出 M

Step1 M←1

Step2 蒙哥馬利運算預處理：

C←MontPro(C,r2mod N,N,r)=Cr mod N

M←MonrPro(M,r2mod N,N,r)=Mr mod N

Step3 預計算余數(shù)表

R1=C R2=MontRed(C2,N,r)

對于i 從1 到(2k-1-1)，執(zhí)行R2i+1←MontPro(R2i-1,R2,N,r)

Step4 對于j 從s 遞減到0，執(zhí)行：

Step5 蒙哥馬利運算后處理

M=MontPro(M,1,N,r)

Step6 返回M。

在算法5 中，由于存在預處理，經(jīng)過蒙哥馬利計算后得到的余數(shù)表為R1=Cr，R2=C2r，R2i+1=C2i+1r。當dj=0 時，計算結(jié)果存儲到中間變量U 中，不影響結(jié)果的輸出；當dj≠0時，每輪迭代輸出結(jié)果：

完成循環(huán)后，需進行蒙哥馬利運算后處理，得M = M×1×r-1=(M2k×Cdj×r)×1×r-1=M2k×Cdj，算法5 的結(jié)果與算法4 一致，因此，算法5 是正確的。

4 改進窗口算法的抗計時和能量攻擊分析

4.1 抗計時攻擊分析

由算法5 可以看出，密鑰被分為長度為k 的密鑰段(最左邊密鑰段的長度在1～k 之間)。算法是對密鑰段而不是密鑰比特位進行迭代循環(huán)控制，因此，Kocher 的計時攻擊是無效的。同時，在k 未知的情況下，計時無法直接確定循環(huán)的起點與次數(shù)，會增加攻擊的難度。即使通過窮舉搜索獲取了k，但其密鑰段對應(yīng)2k種可能的密鑰，而且k 長的dj=0 密鑰段與dj≠0 密鑰段對應(yīng)的蒙哥馬利操作數(shù)也一樣，輸出的中間結(jié)果都會存儲到變量存儲器中，避免了偽操作與真實算法操作之間的時間差異，使攻擊者無法從操作時間上區(qū)分兩者，彌補了文獻[8]存在dj=0 密鑰段攻擊的缺陷，消除了分支結(jié)構(gòu)導致的信息泄漏。因此，當k＞1 時，算法5達到了抗時間攻擊的目的。

4.2 抗簡單能量攻擊分析

由算法5 的步驟4 可以看出，無論密鑰段dj=0 或dj≠0都會在余數(shù)表中隨機選取一個余數(shù)執(zhí)行相同次數(shù)的蒙哥馬利操作，其功耗情況在操作性上無法區(qū)分。加之電子噪聲對輪迭代之間的干擾，攻擊者無法直接通過功耗軌跡差異得出密鑰段與軌跡圖之間的關(guān)系，從而可以有效地抗SPA攻擊，符合文獻[12]靜態(tài)掩蓋算法抗SPA 攻擊有效的結(jié)論。

4.3 抗差分能量攻擊分析

DPA 攻擊主要利用密碼設(shè)備能量消耗的數(shù)據(jù)依賴性，通過差分將系統(tǒng)噪聲、偽操作等剔除，獲取密碼算法中間值與功耗之間的相關(guān)性，進而得出密鑰指數(shù)與相應(yīng)的功耗軌跡的相關(guān)性。在算法5 中，當密鑰段為dj=0 時，隨機選取余數(shù)表中一個余數(shù)進行蒙哥馬利運算，并將操作結(jié)果U存儲到中間變量存儲器中，其操作與真實操作一樣，因此，不存在真正的偽操作，DPA 攻擊不能鑒別出U，消除了上文提到的常規(guī)偽操作不儲存結(jié)果對功耗曲線的影響。dj=0密鑰段和dj≠0 密鑰段都需要執(zhí)行蒙哥馬利運算和讀取余數(shù)表操作，中間值都會進行存儲，兩者功耗無差別，顯著地降低能量消耗的數(shù)據(jù)依賴性。算法5 消除了密鑰指數(shù)段與功耗軌跡之間的相關(guān)性，使能量消耗獨立于密碼算法的中間值，因此，可以有效實現(xiàn)抗DPA 攻擊。

5 改進窗口算法的防御效率分析

由于2 個不同數(shù)相乘可以表示為x×y=((x+y)2-(x-y)2)/4，因此一次快速乘法剩余的運算時間為平方剩余運算時間的2 倍。設(shè)密鑰d 中“0”和“1”出現(xiàn)是等概率的，一次平方剩余運算時間為單位時間T，隨機偽操作發(fā)生的概率為p。對于未添加偽操作的算法1 而言，平均需要n 次平方操作和n/2 次乘法操作，運算總時間T1為2nT；對添加隨機偽操作的算法2，需要n 次平方操作和(1+p)×n/2 次乘法操作，運算總時間T2為(2+p)nT；對于改進的等功耗算法3，需要1 次平方和2k-3 次乘法預計算，sk 次平方和s 次乘法計算，運算總時間T3為{1+2(2k-3)+sk+2s}T；對于本文算法即算法4，需要1 次平方和2k-1-1 次乘法預計算，sk+hs次平方和s 次乘法計算，運算總時間T4為{1+2(2k-1-1)+sk+hs+2s}T，其中，0≤hs＜k。

表1 各種防御算法總計算時間的比較

由表1 可以看出，在保證安全的前提下，算法4 較算法2 防御效率提高了36.8%，較算法3 提高了4%。

分析算法5 的模乘總計算時間。雖然算法5 采用蒙哥馬利運算需要增加2 步預處理和1 步后續(xù)處理，但由于經(jīng)典模乘法在進行迭代運算時，除了需要使用與蒙哥馬利乘法相同的單精度運算外，還需要額外s 次的單精度除法，這開銷隨著s 增加而遠大于蒙哥馬利的預計算。因此，在s較大的情況下，算法5 可以大為減少模乘總計算時間，提高防御效率。

6 結(jié)束語

本文針對RSA 原有的抗側(cè)信道攻擊措施效率低的問題，在原有改進的等功耗編碼防御方法基礎(chǔ)上，提出一種改進窗口算法。將乘法與求平方之間的平衡轉(zhuǎn)換到更為有利的求平方過程中，只需將預計算余數(shù)表中的奇次冪進行預先計算和存儲。分析結(jié)果表明，該算法在保證安全性的前提下，可較大地提高運行效率。另外，如何設(shè)計一種有效防御復合側(cè)信道攻擊的RSA 算法是今后的研究方向。

[1]Kocher P C. Timing Attacks on Implementations of Diffie-Hellman,RSA,DSS,and Other Systems[C]//Proc. of CRYPTO'96. Santa Barbara,USA: Springer-Verlag,1996.

[2]Kocher P C,Jaffe J,Benjamin J. Differential Power Analysis[C]//Proc. of CRYPTO'99. Santa Barbara,USA:Springer-Verlag,1999.

[3]Perin G,Torres L,Benoit P. Amplitude Demodulation-based EM Analysis of Different RSA Implementations[C]//Proc. of Design,Automation and Test in Europe Conference and Exhibition. [S. l.]: IEEE Press,2012.

[4]王 敏,吳 震. 針對隨機偽操作的簡單功耗分析攻擊[J].通信學報,2012,33(5): 138-142.

[5]張寶華,殷新春. RSA 密碼算法的安全及有效實現(xiàn)[J]. 中山大學學報: 自然科學版,2008,47(6): 22-26.

[6]饒金濤,陳 運,吳 震,等. 一種抗簡單功耗分析攻擊的模冪算法[J]. 成都信息工程學院學報,2011,26(2): 123-126.

[7]韓 軍,曾曉洋,湯庭鰲. RSA 密碼算法的功耗軌跡分析及其防御措施[J]. 計算機學報,2006,29(4): 590-596.

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

[9]吳 震,陳 運,王 敏,等. 等功耗編碼算法的改進實現(xiàn)及抗功耗分析攻擊研究[J]. 通信學報,2010,31(8): 26-30.

[10] 陳財森,王 韜,田軍艦,等. 一種針對RSA 算法軟件應(yīng)用的差分計時攻擊[J]. 小型微型計算機系統(tǒng),2011,32(4):672-675.

[11] 田軍艦,田 穎,寇應(yīng)展,等. 一種針對OpenSSL 中RSA的計時攻擊改進算法[J]. 軍械工程學院學報,2011,23(2):62-64,68.

[12] 吳 震,陳 運,陳 俊,等. 真實硬件環(huán)境下冪剩余功耗軌跡指數(shù)信息提取[J]. 通信學報,2010,31(2): 17-21.

[13] Denis T S. BigNum Math: 加密多精度算法的理論與實現(xiàn)[M]. 尹浩瓊,譯. 北京: 中國水利水電出版社,2008.