劉 鶯 迎

(河南牧業(yè)經(jīng)濟(jì)學(xué)院信息工程學(xué)院 河南 駐馬店 450044)

0 引 言

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

1 相關(guān)知識概述

1.1 RSA密碼算法

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

步驟1隨機(jī)選擇兩個不相同大素數(shù)p與q。

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

步驟3隨機(jī)選擇正整數(shù)e，1

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

RSA的自左向右二進(jìn)制掃描算法如算法1所示。

算法1RSA自左向右的二進(jìn)制掃描算法

輸入：M，(n,e)。

輸出：C=Memodn。

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

Step2設(shè)置C=1；

Step3對i從t-1到0，循環(huán)計算：

Step3.1C=C2modn；

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

Step4返回C。

1.2 余數(shù)系統(tǒng)

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

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

(1)

(2)

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

(3)

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

1.3 蒙哥馬利模乘算法

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

算法2蒙哥馬利模乘算法

輸入：整數(shù)a和b，正整數(shù)n。

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

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

Step2設(shè)置c=0；

Step3對i從0到m-1，循環(huán)計算：

Step3.1c=c+ai·b；

Step3.2c=c+c0·n；

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

Step5返回n。

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

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

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

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

輸出：私鑰d。

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

Step2采集Md在運(yùn)行時的真實(shí)能量消耗值Ed[j]；

Step3對于i從n-1到0，循環(huán)執(zhí)行：

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

Step4.3更新d′的值；

Step5返回d=d′。

3 算法設(shè)計

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

算法4基于余數(shù)系統(tǒng)的蒙哥馬利模乘算法

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

輸出：[r]A∪B。

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

Step1對于i從1到l，重復(fù)執(zhí)行：

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

Step2令zi=BT(zi,0)；

Step3對于j從0到l，重復(fù)執(zhí)行：

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基轉(zhuǎn)換算法

輸入：[g]A，β。

//β為基轉(zhuǎn)換修正因子，且有β=0或β=0.5

輸出：[g]B。

Step1設(shè)置α0=β；

Step2對i從1到l，循環(huán)計算：

Step2.3設(shè)置xi0=0；

Step3對j從1到l，循環(huán)計算：

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

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

Step4返回xj(l+1)。

由算法4可得大數(shù)X的模冪運(yùn)算Y=XemodN。則可得基于余數(shù)系統(tǒng)和蒙哥馬利模乘的RSA二進(jìn)制掃描算法，如算法6所示。

算法6基于余數(shù)系統(tǒng)和蒙哥馬利模乘算法的RSA二進(jìn)制掃描算法

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

輸出：[Y]A∪B。

Step1預(yù)計算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，循環(huán)計算：

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 仿真實(shí)驗(yàn)和分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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