可信平臺(tái)中抗側(cè)信道攻擊的RSA算法改進(jìn)研究

摘 要： 可信計(jì)算是信息安全領(lǐng)域研究的熱點(diǎn)，研究可信平臺(tái)模塊的安全性具有重要意義?？尚牌脚_(tái)模塊傳統(tǒng)RSA加密算法缺少物理保護(hù)，具有受到側(cè)信道攻擊的風(fēng)險(xiǎn)。根據(jù)抵抗側(cè)信道攻擊的傳統(tǒng)RSA算法，提出了一種改進(jìn)方法，將RSA添加偽隨機(jī)數(shù)操作方案改進(jìn)為在遇到0 b時(shí)通過0，1隨機(jī)數(shù)判斷是否執(zhí)行偽隨機(jī)操作，減少了模乘運(yùn)算量。研究表明，在保證安全性的前提下，改進(jìn)的RSA算法可提高模塊計(jì)算效率。

關(guān)鍵詞： 可信平臺(tái)模塊； RSA； 側(cè)信道攻擊； 偽隨機(jī)操作

中圖分類號(hào)： TN915.08?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）19?0067?04

Abstract： The trusted computing is a research hotspot in the field of information security， and the study of the trusted platform module （TPM） security has the great significance. The traditional RSA encryption algorithm of TPM lacks of physical protection， and has the risk of side?channel attacks. According to the traditional RSA algorithm to resist the side?channel attacks， an improved method is put forward. The scheme of adding pseudo?random number operation into RSA is improved to determine whether executing pseudo?random operation with 0 and 1 random numbers while encountering a 0 b， so as to reduce the modular multiply operation. The research shows that the improved RSA algorithm can improve the module calculation efficiency while guaranteeing the security.

Keywords： trusted platform model； RSA； side?channel attack； pseudo?random operation

0 引 言

隨著信息技術(shù)的不斷發(fā)展，信息安全的形勢(shì)也變得越來越嚴(yán)峻[1]。信息安全研究滯后于威脅，且相當(dāng)多的安全隱患是來自于計(jì)算機(jī)終端，這就要求計(jì)算機(jī)的硬件系統(tǒng)和操作系統(tǒng)必須不斷提高其安全性?？尚庞?jì)算是信息安全領(lǐng)域的研究熱點(diǎn)，已經(jīng)取得令人鼓舞的成果?？尚攀且环N信息系統(tǒng)安全新技術(shù)，把社會(huì)中的管理經(jīng)驗(yàn)應(yīng)用到計(jì)算機(jī)網(wǎng)絡(luò)中，通過建立可信條件保證計(jì)算機(jī)網(wǎng)絡(luò)的安全性[2]。目前，可信計(jì)算已經(jīng)成為國(guó)際的熱門研究方向，其核心可信平臺(tái)模塊已經(jīng)安裝到了幾乎所有的計(jì)算機(jī)中[3]。

可信平臺(tái)模塊是可信計(jì)算平臺(tái)的信任根，為用戶提供確保平臺(tái)安全可靠的證明?？尚牌脚_(tái)模塊設(shè)計(jì)比較成功，但同時(shí)也存在一些問題。文獻(xiàn)[1]中指出可信計(jì)算的核心部分——可信平臺(tái)模塊總體上設(shè)計(jì)是成功的，但其中缺少芯片本身物理方面的安全設(shè)計(jì)?？尚牌脚_(tái)模塊采用RSA加密方式，一旦RSA密鑰被破譯，那么可信平臺(tái)模塊將失去安全，因此改進(jìn)RSA加密方式即可抵抗現(xiàn)有攻擊。相比分組密碼，RSA加密方式的安全性較高，但運(yùn)算時(shí)間卻是分組密碼的幾倍，因此提高RSA運(yùn)算速度也亟待解決。針對(duì)可信平臺(tái)模塊中的這兩個(gè)問題，結(jié)合已有抗側(cè)信道攻擊的RSA算法，提出了一種改進(jìn)的RSA算法，希望為今后可信平臺(tái)模塊的設(shè)計(jì)提供幫助。

1 RSA算法基本理論

1.1 傳統(tǒng)RSA算法

RSA是一種安全性極高的非對(duì)稱加密算法，其本質(zhì)是大整數(shù)難以分解為大素?cái)?shù)因子。

但在工程實(shí)際中，加密過程遠(yuǎn)沒有理論上那么容易，因?yàn)檫x取的操作數(shù)都非常大，計(jì)算機(jī)無法存儲(chǔ)大量的中間結(jié)果，因此必須采用模運(yùn)算迭代和乘法運(yùn)算相結(jié)合的方法。

1.2 RSA算法的實(shí)現(xiàn)

實(shí)際計(jì)算中RSA算法進(jìn)行模運(yùn)算迭代和乘法運(yùn)算，每次的中間運(yùn)算結(jié)果都需要模上[N，]以保證結(jié)果不大于模數(shù)[N。]導(dǎo)致了計(jì)算量與公鑰[e]和私鑰[d]的大小相關(guān)。

以RSA解密為例，其實(shí)現(xiàn)方法為：[CdmodN=（M×M×M…M）modN=[（M×M）modN×Md-2]modN=[（（M×M）modN×M）modN×Md-3]modN=[（（（M×M）modN×M）modN）…M]modN]

1.3 Binary改進(jìn)算法

Binary算法中，[C]為密文，[N]為模數(shù)，[d]為密鑰。步驟3和步驟4是循環(huán)體，分別執(zhí)行模數(shù)迭代和乘法運(yùn)算。根據(jù)比特是否為1，決定是否進(jìn)行模數(shù)迭代。其運(yùn)算量與密鑰[d]的長(zhǎng)度以及其漢明重量有關(guān)。Binary算法將RSA由理論計(jì)算轉(zhuǎn)為工程應(yīng)用，但其運(yùn)算量偏大。

1.4 高基改進(jìn)算法

在高基算法中，[C]為密文，[N]為模數(shù)，[d]為密鑰的二進(jìn)制表達(dá)。與Binary算法不同，高基算法在執(zhí)行過程中每次掃描多個(gè)比特，減少了步驟4和步驟5循環(huán)的次數(shù)，提高了運(yùn)算效率。但因?yàn)槊看我獟呙瓒鄠€(gè)比特，所以要進(jìn)行預(yù)計(jì)算，增加了運(yùn)算量。因此，高基算法的運(yùn)算量與密鑰長(zhǎng)度和參數(shù)[m]相關(guān)。文獻(xiàn)[2]給出了密鑰長(zhǎng)度與[m]之間的最優(yōu)解。使得高基算法的效率得到了很大提升。表1給出了高基算法和Binary算法的效率對(duì)比。

2 側(cè)信道攻擊

側(cè)信道攻擊最初是由Paul Kocher于1996年提出的。利用密碼運(yùn)算過程中內(nèi)部狀態(tài)和物理測(cè)量值（如功率消耗、計(jì)算時(shí)間、電磁輻射等）之間的關(guān)系，對(duì)測(cè)量值進(jìn)行統(tǒng)計(jì)分析，恢復(fù)密鑰信息。

2.1 功耗攻擊

目前，噪聲對(duì)于簡(jiǎn)單功耗分析技術(shù)的影響已經(jīng)越來越小[6]。對(duì)于RSA來說，其算法細(xì)節(jié)是公開的，這正是簡(jiǎn)單功耗攻擊出現(xiàn)的外在條件。對(duì)于沒有保護(hù)設(shè)計(jì)的RSA算法來說，簡(jiǎn)單功耗攻擊存在很大威脅。

在RSA的Binary改進(jìn)算法中，當(dāng)密鑰位是0時(shí)，算法僅進(jìn)行模方運(yùn)算；當(dāng)密鑰位是1時(shí)，算法進(jìn)行模方和模乘運(yùn)算。導(dǎo)致在SPA攻擊中，可以清晰地看到密鑰不同時(shí)的功耗軌跡。攻擊者只需根據(jù)功耗軌跡，就能逐位還原密鑰。圖1給出了密鑰不同時(shí)的功耗軌跡。

差分功耗攻擊利用統(tǒng)計(jì)分析提取相關(guān)密鑰信息，不需要知道詳細(xì)的算法執(zhí)行細(xì)節(jié)，一般從密碼的第1步或最后1步入手，對(duì)加密或解密進(jìn)行多次操作并測(cè)量采集功耗值，選擇合適的分割函數(shù)，用遍歷方法試遍所有密鑰。根據(jù)計(jì)算分割函數(shù)1和0的平均功耗差值確定密鑰。隨著數(shù)據(jù)增加，如果差值趨于0則密鑰不正確，如果差值趨于實(shí)際值，則密鑰正確。

由于公鑰已知，所以對(duì)公鑰和私鑰進(jìn)行加密運(yùn)算，并將采集數(shù)據(jù)按照公鑰和私鑰逐位對(duì)應(yīng)，根據(jù)差分功耗結(jié)果，位相同為0，不同為1，便可恢復(fù)出私鑰。

2.2 時(shí)間攻擊

時(shí)間攻擊由Kocher提出，利用算法運(yùn)行時(shí)間的差異恢復(fù)密鑰信息攻擊[7]。其原理是：不同加密算法運(yùn)算執(zhí)行時(shí)間不同，如分支操作、有限域操作、冪指數(shù)運(yùn)算等，具體操作時(shí)間由所涉及的操作數(shù)決定。在RSA算法執(zhí)行過程中，模數(shù)為0 b和1 b的操作時(shí)間明顯不同，由此可以分析出密鑰。

2.3 故障攻擊

故障攻擊由Boneh提出，通過注入安全錯(cuò)誤，判斷是正確操作還是偽操作。偽操作與算法執(zhí)行沒有相關(guān)性，如果影響了結(jié)果，就是進(jìn)行了正確操作，反之為偽操作。Yen提出一種攻擊RSA算法的故障攻擊算法[8]。攻擊者在RSA密碼芯片運(yùn)行過程中，主動(dòng)使用故障干擾密碼芯片運(yùn)算過程，根據(jù)故障是否影響密碼運(yùn)算結(jié)果，迅速推測(cè)密鑰信息。

3 抗側(cè)信道攻擊的改進(jìn)RSA算法

3.1 添加偽隨機(jī)數(shù)的傳統(tǒng)RSA算法

該算法考慮到了防御簡(jiǎn)單功耗攻擊和差分功耗攻擊，并且通過預(yù)計(jì)算減少了預(yù)算量，提高了運(yùn)算效率。

3.2 添加偽隨機(jī)數(shù)的改進(jìn)RSA算法

添加偽隨機(jī)數(shù)的等功耗算法針對(duì)側(cè)信道攻擊進(jìn)行防御，通過預(yù)計(jì)算減少了運(yùn)算量，但其計(jì)算效率仍可進(jìn)一步提高。添加偽隨機(jī)數(shù)的等功耗算法為了掩蓋0 b，1 b在執(zhí)行時(shí)的功耗差，執(zhí)行0 b時(shí)要額外運(yùn)算[V=M×Random（R）modN，]這就使得運(yùn)算量增加。此外，偽隨機(jī)操作和執(zhí)行算法間沒有相關(guān)性，添加偽隨機(jī)數(shù)的等功耗算法不能抵抗安全錯(cuò)誤注入攻擊。研究表明，加入隨機(jī)數(shù)判斷決定是否執(zhí)行偽隨機(jī)數(shù)操作可以減少計(jì)算量，將偽隨機(jī)操作[V=M×Random（R）modN]改為[M=M×1modN，]可以消除偽隨機(jī)操作的不相關(guān)性。

因?yàn)殡S機(jī)抽取0和1的概率相等，而操作數(shù)一般為1 024 b，改進(jìn)算法理論上可以減少50%的隨機(jī)數(shù)運(yùn)算，而攻擊者在知道50%的0 b情況下，無法恢復(fù)出全部密鑰。改進(jìn)算法保證了模塊在側(cè)信道攻擊下的安全性。

3.3 改進(jìn)算法安全性分析

3.3.1 抵御簡(jiǎn)單功耗攻擊

采用等功耗執(zhí)行算法，無論操作數(shù)為1 b還是0 b，其功耗均相同。在執(zhí)行0 b運(yùn)算時(shí)，理論上有50%的0 b會(huì)體現(xiàn)在功耗曲線上，但由于實(shí)際中RSA的操作數(shù)一般為1 024 b，所以即使知道50%的0 b位，依然很難通過窮盡方法破譯密鑰，加上電子噪聲干擾，改進(jìn)算法能夠抵抗簡(jiǎn)單功耗的攻擊。

3.3.2 抵御差分功耗攻擊

差分功耗攻擊利用統(tǒng)計(jì)分析提取相關(guān)密鑰信息，直接將噪聲、偽操作通過差分消除掉。而后使用分割函數(shù)，遍歷所有的公鑰和私鑰的密鑰位，將1 b和0 b分為兩個(gè)集合，通過對(duì)比公鑰和私鑰的差分功耗確定私鑰的密鑰。改進(jìn)算法采用了等功耗方法，雖然有50%的0 b功耗會(huì)被暴露，但要想破譯密鑰，仍需要極其復(fù)雜的計(jì)算。

3.3.3 抵御時(shí)間攻擊

計(jì)時(shí)攻擊是根據(jù)RSA算法各操作的時(shí)間差異進(jìn)行攻擊。在改進(jìn)算法中，當(dāng)操作數(shù)為0 b時(shí)，引入了偽隨機(jī)操作，使得運(yùn)算時(shí)間和執(zhí)行1 b的時(shí)間相同，因此可抵御時(shí)間攻擊。

3.3.4 抵御安全錯(cuò)誤攻擊

在操作數(shù)為0 b時(shí)，加入了偽隨機(jī)操作，攻擊者如果通過安全錯(cuò)誤注入來攻擊該算法，當(dāng)操作數(shù)執(zhí)行1 b時(shí)，安全錯(cuò)誤攻擊會(huì)影響運(yùn)算結(jié)果；當(dāng)操作數(shù)執(zhí)行0 b時(shí)，因?yàn)椴僮魇荹M=M×1modN，]具有相關(guān)性，依然會(huì)影響運(yùn)算結(jié)果。因此安全錯(cuò)誤攻擊并不能破譯出密鑰，改進(jìn)算法是安全的，其抗攻擊過程見圖3。

3.4 改進(jìn)算法的效率分析

4 結(jié) 語

針對(duì)可信平臺(tái)模塊中RSA加密算法的安全性進(jìn)行分析，發(fā)現(xiàn)其不能抵抗側(cè)信道的攻擊。在已有的RSA抗側(cè)信道攻擊算法的基礎(chǔ)上，提出一種改進(jìn)方法，將添加偽隨機(jī)操作的運(yùn)算通過一個(gè)0，1隨機(jī)判斷來決定是否執(zhí)行，減少了運(yùn)算量，并且將偽隨機(jī)運(yùn)算改進(jìn)為[M=M×1modN，]使偽隨機(jī)操作和算法存在相關(guān)性，抵抗安全錯(cuò)誤攻擊。研究表明，在保證安全性的前提下，改進(jìn)的RSA算法可提高整體運(yùn)算效率。在今后的研究中，將探索如何進(jìn)一步提高改進(jìn)RSA算法的效率，使其在保證安全性的前提下更加實(shí)用。

注：本文通訊作者為鐘衛(wèi)東。

參考文獻(xiàn)

[1] 沈昌祥.可信計(jì)算的研究與發(fā)展[M].北京：北京工業(yè)大學(xué)出版社，2010.

[2] KO? C K. Analysis of sliding window techniques for exponen?tiation [J]. Computer and mathematics with applications， 1995， 30（10）： 17?24.

[3] KIM H S， KIM T H， YOON J C， et al. Practical second?order correlation power analysis on the message blinding method and its novel countermeasure for RSA [J]. ETRI journal， 2010， 32（1）： 102?111.

[4] 張寶華，殷新春.RSA密碼算法的安全及有效實(shí)現(xiàn)[J].中山大學(xué)學(xué)報(bào)，2008，47（6）：22?26.

[5] 李子木.一種改進(jìn)的CRT?RSA防御側(cè)信道攻擊算法[J].信息傳輸與接入技術(shù)，2013，39（6）：60?64.

[6] KOCHER P， JAFFE J， JUN B. Differential power analysis [C]// Proceedings of 1999 Annual International Conference on Advances in Cryptology. Santa Barbara： Springer?Verlag， 1999： 388?397.

[7] KOCHER P C. Timing attacks on implementations of Diffie?Hellman， RSA， DSS， and other systems [C]// Proceedings of 16th Annual International Cryptology Conference. Santa Barbara： Springer?Verlag， 1996： 104?113.

[8] YEN S M， JOYE M. Checking before output may not be enough against fault?based cryptanalysis [J]. IEEE transactions on computers， 2000， 49（9）： 967?970.

[9] 吳震，陳運(yùn)，王敏，等.等功耗編碼算法的改進(jìn)實(shí)現(xiàn)及抗功耗分析攻擊研究[J].通信學(xué)報(bào)，2010，31（8）：26?30.

[10] 趙躍華，趙加，韓牟.一種針對(duì)RSA抗側(cè)信道攻擊的改進(jìn)窗口算法[J].計(jì)算機(jī)工程，2013，39（6）：150?154.