可信平臺中抗側信道攻擊的RSA算法改進研究

摘 要： 可信計算是信息安全領域研究的熱點，研究可信平臺模塊的安全性具有重要意義。可信平臺模塊傳統RSA加密算法缺少物理保護，具有受到側信道攻擊的風險。根據抵抗側信道攻擊的傳統RSA算法，提出了一種改進方法，將RSA添加偽隨機數操作方案改進為在遇到0 b時通過0，1隨機數判斷是否執行偽隨機操作，減少了模乘運算量。研究表明，在保證安全性的前提下，改進的RSA算法可提高模塊計算效率。

關鍵詞： 可信平臺模塊； RSA； 側信道攻擊； 偽隨機操作

中圖分類號： TN915.08?34 文獻標識碼： A 文章編號： 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 引 言

隨著信息技術的不斷發展，信息安全的形勢也變得越來越嚴峻[1]。信息安全研究滯后于威脅，且相當多的安全隱患是來自于計算機終端，這就要求計算機的硬件系統和操作系統必須不斷提高其安全性。可信計算是信息安全領域的研究熱點，已經取得令人鼓舞的成果。可信是一種信息系統安全新技術，把社會中的管理經驗應用到計算機網絡中，通過建立可信條件保證計算機網絡的安全性[2]。目前，可信計算已經成為國際的熱門研究方向，其核心可信平臺模塊已經安裝到了幾乎所有的計算機中[3]。

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

1 RSA算法基本理論

1.1 傳統RSA算法

RSA是一種安全性極高的非對稱加密算法，其本質是大整數難以分解為大素數因子。

但在工程實際中，加密過程遠沒有理論上那么容易，因為選取的操作數都非常大，計算機無法存儲大量的中間結果，因此必須采用模運算迭代和乘法運算相結合的方法。

1.2 RSA算法的實現

實際計算中RSA算法進行模運算迭代和乘法運算，每次的中間運算結果都需要模上[N，]以保證結果不大于模數[N。]導致了計算量與公鑰[e]和私鑰[d]的大小相關。

以RSA解密為例，其實現方法為：[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改進算法

Binary算法中，[C]為密文，[N]為模數，[d]為密鑰。步驟3和步驟4是循環體，分別執行模數迭代和乘法運算。根據比特是否為1，決定是否進行模數迭代。其運算量與密鑰[d]的長度以及其漢明重量有關。Binary算法將RSA由理論計算轉為工程應用，但其運算量偏大。

1.4 高基改進算法

在高基算法中，[C]為密文，[N]為模數，[d]為密鑰的二進制表達。與Binary算法不同，高基算法在執行過程中每次掃描多個比特，減少了步驟4和步驟5循環的次數，提高了運算效率。但因為每次要掃描多個比特，所以要進行預計算，增加了運算量。因此，高基算法的運算量與密鑰長度和參數[m]相關。文獻[2]給出了密鑰長度與[m]之間的最優解。使得高基算法的效率得到了很大提升。表1給出了高基算法和Binary算法的效率對比。

2 側信道攻擊

側信道攻擊最初是由Paul Kocher于1996年提出的。利用密碼運算過程中內部狀態和物理測量值（如功率消耗、計算時間、電磁輻射等）之間的關系，對測量值進行統計分析，恢復密鑰信息。

2.1 功耗攻擊

目前，噪聲對于簡單功耗分析技術的影響已經越來越小[6]。對于RSA來說，其算法細節是公開的，這正是簡單功耗攻擊出現的外在條件。對于沒有保護設計的RSA算法來說，簡單功耗攻擊存在很大威脅。

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

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

由于公鑰已知，所以對公鑰和私鑰進行加密運算，并將采集數據按照公鑰和私鑰逐位對應，根據差分功耗結果，位相同為0，不同為1，便可恢復出私鑰。

2.2 時間攻擊

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

2.3 故障攻擊

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

3 抗側信道攻擊的改進RSA算法

3.1 添加偽隨機數的傳統RSA算法

該算法考慮到了防御簡單功耗攻擊和差分功耗攻擊，并且通過預計算減少了預算量，提高了運算效率。

3.2 添加偽隨機數的改進RSA算法

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

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

3.3 改進算法安全性分析

3.3.1 抵御簡單功耗攻擊

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

3.3.2 抵御差分功耗攻擊

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

3.3.3 抵御時間攻擊

計時攻擊是根據RSA算法各操作的時間差異進行攻擊。在改進算法中，當操作數為0 b時，引入了偽隨機操作，使得運算時間和執行1 b的時間相同，因此可抵御時間攻擊。

3.3.4 抵御安全錯誤攻擊

在操作數為0 b時，加入了偽隨機操作，攻擊者如果通過安全錯誤注入來攻擊該算法，當操作數執行1 b時，安全錯誤攻擊會影響運算結果；當操作數執行0 b時，因為操作是[M=M×1modN，]具有相關性，依然會影響運算結果。因此安全錯誤攻擊并不能破譯出密鑰，改進算法是安全的，其抗攻擊過程見圖3。

3.4 改進算法的效率分析

4 結 語

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

注：本文通訊作者為鐘衛東。

參考文獻

[1] 沈昌祥.可信計算的研究與發展[M].北京：北京工業大學出版社，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密碼算法的安全及有效實現[J].中山大學學報，2008，47（6）：22?26.

[5] 李子木.一種改進的CRT?RSA防御側信道攻擊算法[J].信息傳輸與接入技術，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] 吳震，陳運，王敏，等.等功耗編碼算法的改進實現及抗功耗分析攻擊研究[J].通信學報，2010，31（8）：26?30.

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