一種針對RSA抗側信道攻擊的改進窗口算法

趙躍華，趙 加，韓 牟

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

1 概述

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

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

2 RSA 的實現算法及抗側信道攻擊分析

2.1 RSA 的實現算法

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

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

輸出 M

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

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

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

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

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

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

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

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

輸出 M

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

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

輸出 M

Step1 預計算

Step1.1 R0←1

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

Step2 M←1

Step3 對于j 從s 遞減到0，執行：

Step3.1 M←M2kmod N

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

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

Step4 返回(M)。

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

3 實現RSA 模冪運算的改進窗口算法

3.1 算法介紹

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

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

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

輸出 M

Step1 預計算

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

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

Step2 M←1

Step3 對于j 從s 遞減到0，執行：

Step4 返回M。

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

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

3.2 改進窗口算法的蒙哥馬利實現形式

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

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

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

輸入 正整數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 預計算余數表

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

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

Step4 對于j 從s 遞減到0，執行：

Step5 蒙哥馬利運算后處理

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

Step6 返回M。

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

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

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

4.1 抗計時攻擊分析

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

4.2 抗簡單能量攻擊分析

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

4.3 抗差分能量攻擊分析

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

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

由于2 個不同數相乘可以表示為x×y=((x+y)2-(x-y)2)/4，因此一次快速乘法剩余的運算時間為平方剩余運算時間的2 倍。設密鑰d 中“0”和“1”出現是等概率的，一次平方剩余運算時間為單位時間T，隨機偽操作發生的概率為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 步后續處理，但由于經典模乘法在進行迭代運算時，除了需要使用與蒙哥馬利乘法相同的單精度運算外，還需要額外s 次的單精度除法，這開銷隨著s 增加而遠大于蒙哥馬利的預計算。因此，在s較大的情況下，算法5 可以大為減少模乘總計算時間，提高防御效率。

6 結束語

本文針對RSA 原有的抗側信道攻擊措施效率低的問題，在原有改進的等功耗編碼防御方法基礎上，提出一種改進窗口算法。將乘法與求平方之間的平衡轉換到更為有利的求平方過程中，只需將預計算余數表中的奇次冪進行預先計算和存儲。分析結果表明，該算法在保證安全性的前提下，可較大地提高運行效率。另外，如何設計一種有效防御復合側信道攻擊的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 密碼算法的安全及有效實現[J]. 中山大學學報: 自然科學版,2008,47(6): 22-26.

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

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

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

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

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

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

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

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