基于余數系統抗MESD攻擊的RSA算法

劉 鶯 迎

(河南牧業經濟學院信息工程學院 河南 駐馬店 450044)

0 引 言

隨著當今社會信息化的程度日益加深，各行各業都加大了對信息技術的依賴度，而且這種趨勢越來越大。盡管信息化能夠為各行業帶來便捷，但是日益嚴重的信息安全問題也為各行業提出了非常大的挑戰[1-2]。SoC智能芯片是實現當今各行業信息安全的十分重要的載體，被廣泛用于軍事、金融、醫療、科研等行業中，加強SoC智能芯片的安全防護對于保護各行業的信息安全具有非常重要的意義。RSA密碼算法[3]作為迄今最成熟最廣泛應用的公鑰密碼體制，由于其加密速度快、安全性高、抗數學攻擊能力強等優點而被廣泛用于SoC智能芯片中。但是能量分析攻擊[4]的提出對采用了RSA密碼算法的SoC智能芯片的安全產生了很大威脅，這種攻擊方法是根據SoC智能芯片在密碼算法執行過程中外泄的能量消耗信息進行攻擊的。為有效加強RSA的抗MESD差分能量分析攻擊能力，本文將余數系統[5]與蒙哥馬利模乘[6]結合起來運用在RSA中，有效實現了RSA的抗MESD差分能量分析攻擊。這是由于余數系統天然獨立以及并行計算的特點能夠把大數運算轉變為小數運算；為了彌補余數系統無法執行除法運算的不足，結合蒙哥馬利模乘算法能夠有效替換取模運算中的除法運算。能耗仿真分析結果表明，本文算法能夠有效抵抗MESD差分能量分析攻擊。

1 相關知識概述

1.1 RSA密碼算法

RSA密碼算法主要是通過以下4個步驟來生成公私鑰密鑰對，其中：(n,e)表示公鑰；d表示私鑰。

步驟1隨機選擇兩個不相同大素數p與q。

步驟2n=pq，φ(n)=(p-1)(q-1)。

步驟3隨機選擇正整數e，1

步驟4用Euclid算法計算d=e-1modφ(n)，其中1

RSA的自左向右二進制掃描算法如算法1所示。

算法1RSA自左向右的二進制掃描算法

輸入：M，(n,e)。

輸出：C=Memodn。

Step1e的二進制編碼為(et-1,et-2,…,e0)2；

Step2設置C=1；

Step3對i從t-1到0，循環計算：

Step3.1C=C2modn；

Step3.2若ei=1，計算C=C·Mmodn；

Step4返回C。

1.2 余數系統

余數系統(Residue Number System, RNS)為無權的并行數值表示系統，各個元素間均沒有進位，主要通過一組基來表示任一整數的余數形式，其中余數系統的基是兩兩互素的整數。如果余數系統有一組基是(d1,d2,…,dk)，可得任意正整數R余數系統形式：

R…=(r1,r2,…,rk)

(1)

(2)

(U*V)…=(u1*v1,u2*v2,…,uk*vk)

(3)

式中：U與V表示正整數；U…=(u1,u2,…,uk)；V…=(v1,v2,…,vk)；運算符*=(+,-,×)。

1.3 蒙哥馬利模乘算法

蒙哥馬利算法是非常高效的無除法模乘算法，該算法首先把任一正整數轉換為模數形式，再通過多次模加運算與模乘運算即可替代模除運算，然后把所得結果的模數形式轉變成正常數制，即是所需求的最終結果。蒙哥馬利模乘算法的具體步驟如算法2所示。

算法2蒙哥馬利模乘算法

輸入：整數a和b，正整數n。

輸出：c=a·b·l-1modn，l=22m，m=log2n。

Step1a的二進制編碼為(at-1,at-2,…,a0)2；

Step2設置c=0；

Step3對i從0到m-1，循環計算：

Step3.1c=c+ai·b；

Step3.2c=c+c0·n；

Step4若c>n，計算c=c-n；

Step5返回n。

2 MESD差分能量分析攻擊算法

MESD差分能量分析攻擊表示多指數單輸入攻擊方法(Multiple-Exponent Single-Data)[7]，該能量分析攻擊方法是在已知明文的前提下，采用多個密鑰對已知明文實施加密，然后對所得到能量消耗曲線進行統計分析，其具體實施步驟如算法3所示。

算法3MESD差分能量分析攻擊算法

輸入：明文M，可控私鑰d′。

輸出：私鑰d。

Step1令M為恒定輸入，d′=0；

Step2采集Md在運行時的真實能量消耗值Ed[j]；

Step3對于i從n-1到0，循環執行：

Step3.3計算D[j]=Ed[j]-E1[j]；

Step4.3更新d′的值；

Step5返回d=d′。

3 算法設計

本文算法的主要思想如下：(1) 分別把兩個大數X和Y與蒙哥馬利模乘因子H相乘，由此可把數的表示形式轉變到蒙哥馬利域下，再自左向右掃描實現二進制模冪運算；(2) 采用余數系統把大數轉變成小數計算，但因為整數的余數系統形式不能執行除法運算，而RSA最主要的即是執行除法運算，故利用蒙哥馬利模乘替代除法運算，得到基于余數系統的蒙哥馬利模乘算法，這樣能夠較好地把余數系統與蒙哥馬利模乘算法結合起來，從而很好地解決不需要執行除法運算的RSA大數模乘問題。由于結合余數系統和蒙哥馬利模乘的RAS算法不需要執行模除運算，只需執行蒙哥馬利模乘運算，執行過程中沒有明顯的能量消耗差異，使得攻擊者無法獲取與密鑰相關的信息，所以可以有效抵抗MESD差分能量分析攻擊。

算法4基于余數系統的蒙哥馬利模乘算法

輸入：[X]A∪B，[Y]A∪B，N。

輸出：[r]A∪B。

//r=XYH-1modN，且有r<2N

Step1對于i從1到l，重復執行：

Step1.1計算wi=(xi×yi)modai；

Step2令zi=BT(zi,0)；

Step3對于j從0到l，重復執行：

Step3.1計算wj=(xj×yj)modbj；

Step3.2計算fj=(wj+zj×Nj)modbj；

//i=j

Step4計算ri=BT(rj,0.5)；

Step5返回(ri,rj)。

算法5基轉換算法

輸入：[g]A，β。

//β為基轉換修正因子，且有β=0或β=0.5

輸出：[g]B。

Step1設置α0=β；

Step2對i從1到l，循環計算：

Step2.3設置xi0=0；

Step3對j從1到l，循環計算：

Step3.1對i從1到l，循環計算：xji=(xj(i-1)+σi|Ai|bj)modbj；

Step3.2xj(l+1)=(xjl+(bj-σl)|A|bj)modbj；

Step4返回xj(l+1)。

由算法4可得大數X的模冪運算Y=XemodN。則可得基于余數系統和蒙哥馬利模乘的RSA二進制掃描算法，如算法6所示。

算法6基于余數系統和蒙哥馬利模乘算法的RSA二進制掃描算法

輸入：[X]A∪B，e=(et-1,et-2,…,e0)2，N。

輸出：[Y]A∪B。

Step1預計算W=H2modN；

//H表示蒙哥馬利模乘因子，其中H=a1×a2×…×al

Step2[F]A∪B=RNSM([X]A∪B,[H]A∪B,N)；

Step3[Y]A∪B=RNSM([1]A∪B,[H]A∪B,N)；

Step4對i從t-1到0，循環計算：

Step4.1[Y]A∪B=RNSM([Y]A∪B,[Y]A∪B,N)；

Step4.2若ei==1，[Y]A∪B=RNSM([Y]A∪B,[F]A∪B,N);

Step5[Y]A∪B=RNSM([Y]A∪B,[1]A∪B,N)；

Step6返回[Y]A∪B。

4 仿真實驗和分析

本節通過MESD能量消耗攻擊仿真來檢驗所給算法6抵抗MESD差分能量分析攻擊的能力。仿真主要是利用文獻[10]提出的實驗平臺來實施所給算法的能量分析攻擊仿真，其中單片機為AT89C52，數字示波器為Tektronix DPO4032，采用LabView編寫虛擬示波器程序來控制數字示波器自動采集能量消耗信息。假設所給算法6采用的真實私鑰為d=(1100)2。仿真步驟主要過程如下：

(1) 配置采樣控制平臺。采樣長度為10 000，采樣次數為10 000，采樣時間為4 ms。

(2) 發送恒定明文信息到單片機，利用真實的私鑰d進行加密，采集真實的能量消耗信息并存儲。

(4) 采用MATLAB 7.0分別求取兩組能量消耗數據，并分別與真實能量消耗信息進行差分計算，生成能量消耗軌跡波形圖。

(5) 通過觀察所生成的能量消耗軌跡。若能量消耗軌跡在猜測密鑰比特位的區域內沒有出現尖峰(能量消耗軌跡中出現尖峰是由于猜測密鑰與真實密鑰操作相反，導致執行的操作指令順序和數目不同，而不同的操作執行時消耗的時間不同，使得所獲得的能量消耗軌跡無法準確對齊，在沒有對齊的時段則會出現尖峰)，則判斷該密鑰比特位取值應為1；若能量消耗軌跡在猜測密鑰比特位的區域內出現尖峰，則判斷該密鑰比特位取值應為0。

(6) 所有密鑰比特位猜測完成后，可獲取通過MESD差分能量分析攻擊得到的密鑰，通過與真實的私鑰比較，判斷猜測的密鑰是否正確。

圖1 猜測第1個比特位為1時采用MESD攻擊的能量消耗軌跡

圖2 猜測第2個比特位為1時采用MESD攻擊的能量消耗軌跡

圖3 猜測第3個比特位為1時采用MESD攻擊的能量消耗軌跡

圖4 猜測第4個比特位為1時采用MESD攻擊的能量消耗軌跡

根據上述4個猜測比特位的能量消耗軌跡可以看出，MESD攻擊最終獲取的密鑰為d′=(0101)，但是實際的密鑰為d=(1100)2。因此，采用MESD差分能量分析攻擊方法攻擊算法6無法得到正確的真實私鑰，即表明本文算法能夠抵抗MESD差分能量分析攻擊。

5 結 語

能量分析攻擊對于RSA密碼算法具有非常大的安全威脅，特別是差分能量分析攻擊中的MESD方法是非常有效的攻擊RSA密碼算法的方法。為了能夠更好地抵抗MESD差分能量分析攻擊，本文提出一種基于余數系統和蒙哥馬利模乘的RSA二進制掃描算法。首先采用整數的余數系統形式把大數運算轉變成小數運算，其主要目的是利用余數系統天然的并行性優點來使RSA密碼算法能夠高度并行化處理；然后用蒙哥馬利模乘替換RAS中的除法運算，其主要目的是彌補采用整數的余數系統形式不能執行除法運算的不足。由實驗仿真分析結果可知，對RSA密碼算法實施MESD差分能量分析攻擊不能得到正確的私鑰信息，因此本文算法可以有效抵抗MESD差分能量分析攻擊。