SM4密碼算法的階梯式相關(guān)能量分析

叢 旌，韋永壯*，劉爭(zhēng)紅

（1.廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室（桂林電子科技大學(xué)），廣西桂林 541004；2.廣西無線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室（桂林電子科技大學(xué)），廣西桂林 541004）

（*通信作者電子郵箱walker_wyz@guet.edu.cn）

0 引言

2012 年3 月，國家密碼管理局發(fā)布SM4 作為密碼行業(yè)的標(biāo)準(zhǔn)。過去十年，專家學(xué)者們已經(jīng)對(duì)SM4 密碼算法的實(shí)現(xiàn)展開了一系列分析研究，特別是在側(cè)信道分析（Side Channel Analysis,SCA)，如差分能量分析［1］、相關(guān)能量分析（Correlation Power Analysis,CPA)［2-3］等方面取得了若干重要進(jìn)展。

側(cè)信道分析通過分析密碼算法實(shí)現(xiàn)過程中的中間值的信息泄露進(jìn)行破譯。時(shí)間［4］、功耗［5］、電磁波［6-7］等信息均可被用于分析密碼系統(tǒng)。簡(jiǎn)單能量分析是側(cè)通道分析中最經(jīng)典的一種，即：不同的操作可能產(chǎn)生不同的功耗。通過觀察采集到的設(shè)備加密過程中的能量波形，可以直接得到設(shè)備執(zhí)行的具體操作，并進(jìn)一步推測(cè)設(shè)備中的數(shù)據(jù)。1999 年，差分能量分析由Kocher 等［5，8］首先提出，后來由Messerges 等［9］將其形式化。差分能量分析僅利用1 位功率信息對(duì)能量跡進(jìn)行分類［10］，是側(cè)通道分析中使用最廣泛的分析方法。為了改進(jìn)原有的差分能量分析，Bevan 等［11］、Messerges 等［12］引入了多位差分功耗分析（Differential Power Analysis，DPA）。然后，基于漢明距離泄漏模型的相關(guān)能量分析在文獻(xiàn)［13］中提出，該方案通過計(jì)算功率樣本與密碼算法中間值漢明距離之間的相關(guān)系數(shù)確定正確的密鑰。該泄漏模型同樣適用于以S 盒為單位的部分密鑰；故當(dāng)密鑰空間較大時(shí)，可以通過分而治之的方法逐個(gè)恢復(fù)部分密鑰，從而獲得完整密鑰。近幾年，人工智能（Artificial Intelligence，AI）算法也開始應(yīng)用于側(cè)通道分析當(dāng)中［14-15］。

注意到，為了追求效率，密碼算法在硬件實(shí)現(xiàn)時(shí)通常采用并行實(shí)現(xiàn)的方案。此時(shí)，傳統(tǒng)的基于單個(gè)S 盒的泄漏模型不再足夠精確。文獻(xiàn)［16］將傳統(tǒng)相關(guān)能量分析中基于單個(gè)S 盒的泄漏模型改進(jìn)為基于多個(gè)S 盒的泄漏模型，并通過引入遺傳算法以對(duì)抗擴(kuò)大的搜索空間。文獻(xiàn)［17］在此基礎(chǔ)上進(jìn)行了改進(jìn)，設(shè)計(jì)了基于多種群遺傳算法的相關(guān)能量分析，以應(yīng)對(duì)遺傳算法過早收斂的問題。兩者均大幅降低了恢復(fù)密鑰所需的能量跡的條數(shù)，但都存在離線計(jì)算量較大、樣本不足時(shí)得不到任何結(jié)果等問題。如何以盡可能小的計(jì)算量減少噪聲，提高泄漏信息的利用率，成為研究的難點(diǎn)。

本文針對(duì)密碼算法并行實(shí)現(xiàn)下相關(guān)能量分析效率低下的現(xiàn)象分析了原因，并提出了新的方法：階梯式相關(guān)能量分析。其核心思想是優(yōu)化傳統(tǒng)相關(guān)能量分析的流程，提高能量跡的利用率，從而提高分析效率，減少能量跡的條數(shù)需求。階梯式相關(guān)能量分析通過構(gòu)造一種新的階梯式方案并引入confidence 指標(biāo)，可以在分析時(shí)回避正確性較低的分析結(jié)果，以確保每一次分析的結(jié)果有盡可能高的正確率。同時(shí)，隨著階梯式流程的推進(jìn)，原本作為干擾項(xiàng)的部分噪聲也將被逐一消除。整個(gè)分析過程變得越來越準(zhǔn)確，這使得原本容易受噪聲干擾的部分密鑰的恢復(fù)過程變得不再容易出錯(cuò)。將階梯式相關(guān)能量分析應(yīng)用于SM4 密碼算法的分析，本文得到了優(yōu)于傳統(tǒng)相關(guān)能量分析的結(jié)果。其計(jì)算量與傳統(tǒng)相關(guān)能量分析相當(dāng)，但明顯減少了恢復(fù)完整輪密鑰所需求的能量跡條數(shù)。

1 預(yù)備知識(shí)

1.1 SM4密碼算法

SM4 密碼算法與數(shù)據(jù)加密標(biāo)準(zhǔn)（Data Encryption Standard，DES）［18］及高級(jí)加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）［19］類似，均為分組密碼。SM4的分組長度和密鑰長度均為128 比特，加密算法與密鑰擴(kuò)展算法均采用32 輪非線性迭代結(jié)構(gòu)，以32 比特為單位進(jìn)行加密運(yùn)算。SM4 密碼算法的加、解密算法的結(jié)構(gòu)相同、使用的輪密鑰相反，其解密輪密鑰是加密輪密鑰的逆序。

SM4密碼算法的整體結(jié)構(gòu)如圖1所示。

圖1 SM4算法結(jié)構(gòu)Fig.1 Structure of SM4 algorithm

明文輸入為：

密文輸出為：

第i輪運(yùn)算輸入為：

輪密鑰為：

則輪函數(shù)定義為：

其中T為非線性變換和線性變換復(fù)合而成的合成置換。非線性變換由4個(gè)平行的S盒構(gòu)成，S盒的數(shù)據(jù)均采用16進(jìn)制。線性變換公式如下：

其中B為非線性變換得到的字。

最后一輪加密變換時(shí)，輸出為：

其中R為反序變換。

1.2 相關(guān)能量分析

文獻(xiàn)［20］給出了相關(guān)能量分析的具體分析步驟，概括如下：

步驟1 選擇中間值。選擇合適的分析點(diǎn)是進(jìn)行具體相關(guān)能量分析的前提。通過分析具體的密碼算法，找到加解密過程中的一個(gè)中間值。這個(gè)中間值通常由一個(gè)函數(shù)f(p，k)生成，其中p是明文的一部分，k是與p相對(duì)應(yīng)的密鑰的一部分。滿足這種條件的中間值可以泄露k。

步驟2 采集能量跡。搭建實(shí)驗(yàn)平臺(tái)，進(jìn)行d次加密或解密，每次采集長度為l的能量跡，構(gòu)成大小為d×l的矩陣T。同時(shí)記錄每次加密或解密時(shí)計(jì)算中間值f(p，k)所需的p，構(gòu)成長度為d的向量P=(p1，p2，…，pd)。采集到的能量跡需要進(jìn)行預(yù)處理（如對(duì)齊操作等），確保矩陣P中每一列數(shù)據(jù)對(duì)應(yīng)的功耗均由相同的操作產(chǎn)生。

步驟3 計(jì)算假設(shè)中間值。對(duì)k進(jìn)行窮舉，記為向量K=(k1，k2，…，kn)，其中n表示k所能取到的所有值的數(shù)量。根據(jù)所有d次加密或解密對(duì)應(yīng)的p和所有n個(gè)密鑰假設(shè)，計(jì)算v=f(p，k)，構(gòu)成大小為d×n的矩陣V。

步驟4 將中間值映射為功耗。選擇合適的功耗模型，對(duì)V中的每個(gè)假設(shè)中間值計(jì)算對(duì)應(yīng)的假設(shè)功耗值，得到由中間值矩陣V映射而成的功耗矩陣H，其大小依然為d×n。

步驟5 求相關(guān)系數(shù)。對(duì)矩陣H中的每一列hi與矩陣T中的每一列tj求相關(guān)系數(shù)，構(gòu)成大小為n×l的矩陣R。其中的元素ri，j越大，表示hi與tj的匹配性越好。最大元素所對(duì)應(yīng)的列標(biāo)即為所求密鑰。相關(guān)系數(shù)計(jì)算公式如下：

2 階梯式相關(guān)能量分析

2.1 并行實(shí)現(xiàn)下的相關(guān)能量分析

在相關(guān)能量分析中，采集到的能量分為兩部分：信息與噪聲。信息，即分析對(duì)象對(duì)應(yīng)的S 盒在運(yùn)行時(shí)產(chǎn)生的能量；噪聲，包括密碼設(shè)備運(yùn)行時(shí)其他模塊產(chǎn)生的能量與白噪聲。特別的，在密碼算法并行實(shí)現(xiàn)的條件下，其他S 盒的能量信息也會(huì)包含在采集到的能量中。這些能量將被視為該次分析中的噪聲，對(duì)分析結(jié)果產(chǎn)生干擾。

從圖2中可以明確得知，單次分析的密鑰比特?cái)?shù)越多，噪聲越小，但相應(yīng)的搜索空間也會(huì)越大；反之，搜索空間減小，但受噪聲的影響更大。如何權(quán)衡兩者之間的關(guān)系，或者找到新的方法在同一數(shù)量級(jí)的計(jì)算量上提高分析的效率是研究的關(guān)鍵。傳統(tǒng)相關(guān)能量分析采用分而治之的思想，每一次分析恢復(fù)一個(gè)S 盒對(duì)應(yīng)的部分密鑰，多次分析恢復(fù)完整輪密鑰。但實(shí)際上在每一次部分密鑰的恢復(fù)后，一些本可以被利用的信息被忽略掉了。

圖2 采集能量的構(gòu)成Fig.2 Composition of collected power

2.2 階梯式方案

相關(guān)能量分析的傳統(tǒng)方案通過分而治之的思想，利用多次分析分別恢復(fù)每個(gè)S 盒對(duì)應(yīng)的部分密鑰，如圖3 所示：第一次分析第一個(gè)S盒對(duì)應(yīng)的部分密鑰，之后每次分析下一個(gè)S盒對(duì)應(yīng)的部分密鑰，直到分析完所有S 盒對(duì)應(yīng)的部分密鑰，構(gòu)成完整輪密鑰。圖3中m表示完整輪密鑰包含的數(shù)據(jù)字的個(gè)數(shù)。每一次分析的過程是相互獨(dú)立的，即一次分析的結(jié)果不會(huì)對(duì)其他分析造成任何影響。當(dāng)噪聲較大或能量跡條數(shù)過少時(shí)，分析的成功率降低。而任意一次分析的失敗都將導(dǎo)致完整密鑰恢復(fù)的失敗，這是相關(guān)能量分析失敗最常見的原因。

圖3 傳統(tǒng)相關(guān)能量分析方案Fig.3 Classic CPA scheme

然而，成功完成其中任意一次分析后，所獲的部分密鑰對(duì)下一次分析而言并不是沒有任何意義的。將一次分析的結(jié)果納入下一次的分析目標(biāo)，將在維持搜索空間不變的前提下，有效減少噪聲、增加信息。如：第一次分析以第一個(gè)字節(jié)的密鑰為分析目標(biāo)，得到分析結(jié)果：k1=01010101。第二次分析，將第一字節(jié)與第二字節(jié)同時(shí)作為分析目標(biāo)。其中第一字節(jié)固定為k1=01010101 不變，第二字節(jié)k2從00000000 遍歷至11111111。每次分析的密鑰字節(jié)數(shù)越來越長，由圖2 可知噪聲將會(huì)減少。但是因?yàn)槊看畏治鲋惶砑右粋€(gè)字節(jié)的新密鑰，其他密鑰都是已知的、固定不變的，所以搜索空間依然是28=256。具體方案為：第一次分析第一個(gè)S盒對(duì)應(yīng)的8比特密鑰，之后每次分析都將下一個(gè)S 盒對(duì)應(yīng)的8 比特密鑰納入攻擊范圍。在保持前一次分析結(jié)果不變的前提下，遍歷下一個(gè)S 盒對(duì)應(yīng)的8比特密鑰，直到最后一次分析，獲得完整的輪密鑰。

階梯式方案的優(yōu)勢(shì)在于：隨著階梯式流程的推進(jìn)，分析的密鑰字節(jié)數(shù)越來越長，噪聲越來越少。這意味著后分析的部分密鑰將有越來越高的正確率。但相關(guān)能量分析的成功，即完整密鑰的恢復(fù)，取決于每一次對(duì)部分密鑰分析的成功與否，而非單次分析成功率的最大值。前幾次分析的正確性成了階梯式方案的短板。單純的階梯式方案并不能對(duì)前幾次分析的成功率產(chǎn)生有效影響，而后幾次分析成功率的提升對(duì)完整密鑰恢復(fù)的成功率提升非常有限，所以需要進(jìn)一步引入文獻(xiàn)［21］中提及的confidence指標(biāo)（下文中簡(jiǎn)稱c指標(biāo)）：

其中：r1為一次相關(guān)能量分析中獲得的最大的相關(guān)系數(shù)；r2為同一次相關(guān)能量分析中獲得的第二大的相關(guān)系數(shù)。c 指標(biāo)為兩者之差，它可以有效地衡量這一次相關(guān)能量分析結(jié)果的正確性。指標(biāo)數(shù)值越大，結(jié)果為正確的可能性越大，反之則越有可能是受噪聲干擾所得的錯(cuò)誤結(jié)果。

具體分析流程如圖4。描述如下：第一次分析，依次對(duì)4個(gè)S 盒對(duì)應(yīng)的部分密鑰進(jìn)行分析，并計(jì)算每次分析的c 指標(biāo)。保留c 指標(biāo)最高的一次分析所得的密鑰。第二次分析，將已恢復(fù)的密鑰納入分析目標(biāo)，繼續(xù)分析其余3個(gè)S盒對(duì)應(yīng)的部分密鑰，并計(jì)算每次分析的c 指標(biāo)。如：第一次分析已恢復(fù)k3，則依次分析k1|k3，k2|k3，k4|k3，其中k3固定為已恢復(fù)的值，k1，k2，k4依次遍歷256種候選值。保留c指標(biāo)最高的一次分析所得的密鑰。以此類推，直到第四次分析結(jié)束，恢復(fù)出完整輪密鑰。為了便于理解具體流程，表1 給出了階梯式相關(guān)能量分析實(shí)例中每一次分析的具體參數(shù)。

圖4 階梯式相關(guān)能量分析方案Fig.4 Stepwise CPA scheme

表1 階梯式相關(guān)能量分析實(shí)例Tab.1 Example of stepwise CPA

c 指標(biāo)的引入在一定程度上解決了前幾次分析正確率得不到保證的問題?？梢哉f，依據(jù)c 指標(biāo)篩選分析結(jié)果是在資源已定的情況下被動(dòng)地提升成分析的功率，而階梯式方案的推進(jìn)則是主動(dòng)消除噪聲的影響，提升成功率。兩者的結(jié)合有效提高了相關(guān)能量分析的成功率，尤其是在噪聲較大、能量跡條數(shù)較少的情況下。

傳統(tǒng)相關(guān)能量分析的基本思想是“分而治之”，但在分治的過程中，任何一次分析的錯(cuò)誤都將導(dǎo)致最終完整輪密鑰恢復(fù)的失敗。本文提出的階梯式相關(guān)能量分析，其基本思想是“步步為營”。相較于傳統(tǒng)相關(guān)能量分析，只要有一次分析成功，就可以繼續(xù)分析下去。而且隨著階梯式流程的推進(jìn)，一些本可能發(fā)生錯(cuò)誤的分析也將在接下來的分析中因噪聲的減少而被進(jìn)一步修正。

2.3 階梯式相關(guān)能量分析的構(gòu)造

階梯式相關(guān)能量分析包含以下主要步驟：確定分析目標(biāo)、相關(guān)能量分析、篩選分析結(jié)果、狀態(tài)更新。

相關(guān)數(shù)據(jù)定義如下：

1）m表示完整輪密鑰包含的數(shù)據(jù)字的個(gè)數(shù)（以SM4 密碼算法為例，m=4）；

2）數(shù)組key存儲(chǔ)所有已恢復(fù)的部分密鑰；

3）數(shù)組state存儲(chǔ)密鑰恢復(fù)的狀態(tài)（具體是一個(gè)長度為m的布爾數(shù)組，true表示當(dāng)前下標(biāo)對(duì)應(yīng)的S盒對(duì)應(yīng)的部分密鑰已被恢復(fù)，反之則為false）；

4）數(shù)組target存儲(chǔ)本次分析的目標(biāo)（具體是一個(gè)長度為m的布爾數(shù)組，true表示當(dāng)前下標(biāo)對(duì)應(yīng)的S盒對(duì)應(yīng)的部分密鑰被包含在本次分析的目標(biāo)之內(nèi)，反之則為false）；

5）數(shù)組data存儲(chǔ)相關(guān)能量分析的結(jié)果和相應(yīng)的精確系數(shù)；

6）數(shù)組result存儲(chǔ)本次分析保留的恢復(fù)的部分密鑰及其在完整輪密鑰中的位置。

相關(guān)函數(shù)定義及其基本功能如下：

1）函數(shù)target（）根據(jù)密鑰恢復(fù)的狀態(tài)返回本次分析的目標(biāo)。若還沒有任何部分密鑰被恢復(fù)，則分析目標(biāo)為分別為所有部分密鑰；否則分析目標(biāo)為所有未被恢復(fù)的部分密鑰分別與已恢復(fù)的密鑰合并。

2）函數(shù)cpa（）根據(jù)分析目標(biāo)、明文、S 盒函數(shù)及能量跡返回相關(guān)能量分析的結(jié)果和相應(yīng)的c指標(biāo)。

3）函數(shù)select（）根據(jù)相關(guān)能量分析的結(jié)果和相應(yīng)的c 指標(biāo)返回本次分析保留的恢復(fù)的部分密鑰及其在完整密鑰中的位置。

4）函數(shù)update（）根據(jù)本次分析結(jié)果更新數(shù)組key和數(shù)組state，以存儲(chǔ)本輪恢復(fù)的部分密鑰和當(dāng)前密鑰恢復(fù)的情況。

上述函數(shù)均為作者在C語言環(huán)境下編寫而得。下面給出階梯式相關(guān)能量分析的偽代碼：

算法1 階梯式相關(guān)能量分析。

輸入：能量跡W、明文P、S盒函數(shù)S；

輸出：輪密鑰。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 模擬實(shí)驗(yàn)

在模擬實(shí)驗(yàn)中，在C 語言仿真平臺(tái)上對(duì)SM4 算法的S 盒操作進(jìn)行了模擬，并分別添加兩種不同程度的噪聲，其標(biāo)準(zhǔn)差分別為σ=3.0 和σ=5.0。在這兩組數(shù)據(jù)上分別執(zhí)行了傳統(tǒng)相關(guān)能量分析和本文提出的階梯式相關(guān)能量分析。實(shí)驗(yàn)按照不同的給定能量跡條數(shù)分組進(jìn)行，從100 到1 000，間隔為10，每組實(shí)驗(yàn)取1 000 次實(shí)驗(yàn)結(jié)果的平均值。圖5 給出了這兩種方案的成功率。表2總結(jié)了在成功率達(dá)到50%和90%的前提下，兩種方案對(duì)能量跡條數(shù)的需求和相應(yīng)的計(jì)算量。由于計(jì)算量主要取決于相關(guān)系數(shù)的計(jì)算次數(shù)，所以這里忽略了排序操作的計(jì)算量，只記錄恢復(fù)完整輪密鑰所需計(jì)算相關(guān)系數(shù)的次數(shù)。

圖5 不同噪聲下能量跡條數(shù)與成功率的關(guān)系Fig.5 Relationship between the number of power traces and success rate under different noises

表2 階梯式相關(guān)能量分析與傳統(tǒng)相關(guān)能量分析對(duì)比Tab.2 Comparison of stepwise CPA and classic CPA

實(shí)驗(yàn)結(jié)果表明，在能量跡條數(shù)相同的前提下，本文提出的階梯式相關(guān)能量分析的成功率明顯優(yōu)于傳統(tǒng)相關(guān)能量分析。當(dāng)σ=3.0時(shí)，階梯式相關(guān)能量分析只需要420 條能量跡就可以達(dá)到90%的成功率，而傳統(tǒng)相關(guān)能量分析需要560條，減少了25%的能量跡條數(shù)需求。當(dāng)σ=5.0時(shí)，階梯式相關(guān)能量分析只需要630 條能量跡就可以達(dá)到90%的成功率，而傳統(tǒng)相關(guān)能量分析需要760 條，減少了17%的能量跡條數(shù)需求。值得一提的是，階梯式相關(guān)能量分析的計(jì)算量為2 560 次，是傳統(tǒng)相關(guān)能量分析的2.5 倍。相較于計(jì)算量達(dá)到幾萬甚至幾十萬的基于遺傳算法的相關(guān)能量分析（Correlation Power Analysis based on Simple Genetic Algorithm，SGA-CPA）［16］和基于多種群遺傳算法的相關(guān)能量分析（Correlation Power Analysis based on genetic algorithm and Multiple Sieve method，MS-CPA）［17］，階梯式相關(guān)能量分析的計(jì)算量非常小，可以認(rèn)為是與傳統(tǒng)相關(guān)能量分析的計(jì)算量處于同一數(shù)量級(jí)上。

3.2 FPGA上的實(shí)驗(yàn)

在實(shí)際實(shí)驗(yàn)中，使用SAKURA-G 自主搭建實(shí)驗(yàn)平臺(tái)。SAKURA-G是一款專門為硬件安全方面的研究和開發(fā)而設(shè)計(jì)的FPGA 板。它由兩塊Spartan-6 FPGA 集成而來：主FPGA 用于密碼算法的實(shí)現(xiàn)；控制FPGA 用于相應(yīng)控制邏輯的實(shí)現(xiàn)。超低噪聲的設(shè)計(jì)使能量分析變得更加容易。

在具體的相關(guān)能量分析實(shí)驗(yàn)中，把SM4 硬件電路下載到SAKURA-G 開發(fā)板上，然后將其觸發(fā)輸出和信號(hào)輸出分別與示波器相連，并將主控制口通過USB 連接線與電腦相連。對(duì)固定的密鑰和已知的隨機(jī)明文執(zhí)行SM4 密碼算法，并通過使用LeCroy WaveRunner 610Zi 示波器與旁路分析軟件SCAnalyzer 完成5 000 條能量跡的采集。實(shí)際采集到的每一條能量跡為一個(gè)長度為30 000 的數(shù)組，記錄了電壓隨時(shí)間變化的曲線。為了降低噪聲和減少計(jì)算量，需要對(duì)能量跡進(jìn)行重采樣，即數(shù)組中的每10個(gè)點(diǎn)取平均數(shù)，記為一個(gè)點(diǎn)。

首先，對(duì)這5 000 條能量跡進(jìn)行傳統(tǒng)相關(guān)能量分析，計(jì)算單字節(jié)部分密鑰的所有可能值對(duì)應(yīng)的中間值與能量跡的相關(guān)系數(shù)。圖6 給出了實(shí)驗(yàn)結(jié)果：虛線表示正確密鑰，不同灰度的實(shí)線表示其他錯(cuò)誤密鑰。用于計(jì)算相關(guān)系數(shù)的能量跡條數(shù)為10～5 000，間隔為10。當(dāng)能量跡條數(shù)大于3 430 條時(shí)，正確密鑰對(duì)應(yīng)的相關(guān)系數(shù)始終大于錯(cuò)誤密鑰對(duì)應(yīng)的相關(guān)系數(shù)，這意味著本次實(shí)驗(yàn)中使用傳統(tǒng)相關(guān)能量分析恢復(fù)密鑰至少需要3 430條能量跡。

圖6 相關(guān)系數(shù)與能量跡條數(shù)的關(guān)系（傳統(tǒng)相關(guān)能量分析）Fig.6 Relationship between the number of power traces and correlation coefficient（classic CPA）

其次，對(duì)同樣的5 000條能量跡計(jì)算其與完整密鑰對(duì)應(yīng)的中間值的相關(guān)系數(shù)，旨在找出同等實(shí)驗(yàn)環(huán)境下通過相關(guān)能量分析恢復(fù)完整輪密鑰所需能量跡的最小數(shù)量。由于完整輪密鑰長度為32 比特，窮盡所有可能的計(jì)算量較大且沒有必要，所以只選擇部分最具“競(jìng)爭(zhēng)力”的錯(cuò)誤密鑰與正確密鑰進(jìn)行對(duì)比。文獻(xiàn)［17］已給出相關(guān)結(jié)論，即候選密鑰中正確的字節(jié)數(shù)越多，其對(duì)應(yīng)的相關(guān)系數(shù)越大。故本次實(shí)驗(yàn)中只選擇28×4個(gè)只含有3 個(gè)正確字節(jié)的候選密鑰與正確密鑰做對(duì)比。經(jīng)過實(shí)驗(yàn)結(jié)果的分析與對(duì)比發(fā)現(xiàn)，在本實(shí)驗(yàn)中，當(dāng)?shù)? 個(gè)S 盒對(duì)應(yīng)的部分密鑰錯(cuò)誤、其他部分密鑰正確時(shí)，錯(cuò)誤密鑰對(duì)應(yīng)的相關(guān)系數(shù)與正確密鑰對(duì)應(yīng)的相關(guān)系數(shù)最接近。所以為了精簡(jiǎn)圖表數(shù)據(jù)，圖7 將只給出這部分實(shí)驗(yàn)結(jié)果的數(shù)據(jù)：其中虛線表示正確密鑰，不同灰度的實(shí)線表示其他錯(cuò)誤密鑰。用于計(jì)算相關(guān)系數(shù)的能量跡條數(shù)為10～5 000，間隔為10。當(dāng)能量跡條數(shù)大于3 100條時(shí)，正確密鑰對(duì)應(yīng)的相關(guān)系數(shù)始終大于錯(cuò)誤密鑰對(duì)應(yīng)的相關(guān)系數(shù)，這意味著本次實(shí)驗(yàn)中以相關(guān)能量分析為基本思想恢復(fù)完整密鑰最少需要3 100 條能量跡。當(dāng)然這是建立在將相關(guān)能量分析的搜索空間擴(kuò)大到232的前提下的。這是通過巨大計(jì)算量換取分析精度的一種方式。

最后，同樣是這5 000 條能量跡，對(duì)其進(jìn)行階梯式相關(guān)能量分析，記錄每一次分析的結(jié)果對(duì)應(yīng)的相關(guān)系數(shù)，并與正確密鑰對(duì)應(yīng)的相關(guān)系數(shù)進(jìn)行對(duì)比。圖8 給出了實(shí)驗(yàn)結(jié)果：其中虛線表示正確密鑰，4種灰度的實(shí)線由淺至深分別表示4次分析的結(jié)果。用于計(jì)算相關(guān)系數(shù)的能量跡條數(shù)為10～5 000，間隔為10。當(dāng)能量跡條數(shù)達(dá)到2 370條時(shí)，最后一次分析的結(jié)果對(duì)應(yīng)的相關(guān)系數(shù)已基本與正確密鑰對(duì)應(yīng)的相關(guān)系數(shù)重合。當(dāng)能量跡條數(shù)大于3 100條時(shí)，兩者完全重合。這說明階梯式相關(guān)能量分析恢復(fù)正確密鑰的能力已經(jīng)非常接近將搜索空間擴(kuò)展到最大時(shí)的極限。

圖7 相關(guān)系數(shù)與能量跡條數(shù)的關(guān)系（完整輪密鑰）Fig.7 Relationship between the number of power traces and the correlation coefficient（whole round key）

圖8 相關(guān)系數(shù)與能量跡條數(shù)的關(guān)系（階梯式相關(guān)能量分析）Fig.8 Relationship between the number of power traces and correlation coefficient（stepwise CPA）

本次實(shí)驗(yàn)中，使用傳統(tǒng)相關(guān)能量分析恢復(fù)密鑰至少需要3 430 條能量跡，而將搜索空間擴(kuò)大到232時(shí)，對(duì)能量跡條數(shù)需求的極限是3 100 條。階梯式相關(guān)能量分析的結(jié)果在能量跡條數(shù)達(dá)到2 370 條時(shí)基本與正確密鑰吻合，在達(dá)到3 100 條時(shí)完全吻合。不同實(shí)驗(yàn)中的數(shù)據(jù)存在細(xì)微的差別，但數(shù)據(jù)間的關(guān)系和比例大致不變。由此可以看出階梯式相關(guān)能量分析相對(duì)于傳統(tǒng)相關(guān)能量分析有明顯的優(yōu)越性。

4 結(jié)語

本文討論了相關(guān)能量分析在并行實(shí)現(xiàn)下分析效率低下的原因，提出了階梯式方案，并通過引入confidence 指標(biāo)，基于SM4 密碼算法的結(jié)構(gòu)，構(gòu)造了階梯式相關(guān)能量分析。實(shí)驗(yàn)結(jié)果表明階梯式相關(guān)能量分析以較小的計(jì)算量有效降低了傳統(tǒng)相關(guān)能量分析對(duì)能量跡條數(shù)的需求，是一種精確、快捷的分析方案。接下來進(jìn)一步的研究可以考慮對(duì)能量跡進(jìn)行分析和篩選，以減少計(jì)算量、提高分析效率。