密碼指令集擴展研究

摘要：詳細分析了常見密碼算法的基本操作以及密碼指令集擴展的研究現狀，針對當前密碼系統需要支持多種密碼算法的特點指出未來密碼指令集擴展的發展方向：指令設計需朝通用性上發展且通用密碼處理器是處理器密碼指令集擴展的最終目的。

關鍵詞：密碼指令集擴展； 基本操作； 通用性； 通用密碼處理器

中圖分類號：TP309.7

文獻標志碼：A

文章編號：1001－3695(2008)06－1833－03

信息安全是當今計算機和網絡系統中至關重要的一環，而密碼算法是確保信息安全的重要依據。隨著信息技術的迅猛發展，計算機和網絡系統對密碼處理有了更高的要求，通常會采用多種密碼算法來滿足不同級別的安全需求，這就要求密碼處理系統在滿足密碼性能要求的同時能夠支持多種密碼算法的處理。

密碼算法通常有硬件實現和軟件實現兩種實現方式。硬件實現具有速度快、安全性高的優點；但是由于固化了算法實現，靈活性差；而軟件實現則恰恰相反，靈活性好但性能較低。

一種密碼算法軟/硬件實現的折中方法是指令集擴展，即面向特定的應用對處理器指令進行擴展，采用硬件實現影響密碼算法性能的基本操作部件，并在指令集中添加相應的指令。該方法既保留了軟件實現的靈活性，又進一步地提升了系統性能。密碼指令集擴展在最近幾年引起了廣泛關注，此項研究涉及了密碼學、計算機系統結構等方面的知識，是一個嶄新的跨學科研究領域。

本文通過分析當前常見密碼算法的基本操作，研究密碼指令集擴展的研究現狀以及分析現有信息系統對密碼處理系統的需求，對未來密碼指令集擴展的發展趨勢以及研究方向進行了預測。

1密碼算法的基本操作

任何一個密碼算法都是由一系列的基本運算按照一定的規則組合而成的。這些運算稱為密碼算法的基本操作。密碼算法主要包括對稱密碼和公鑰密碼兩種，本文從兩類密碼算法中選取常用的可以代表當前密碼算法發展方向的算法，對這些密碼算法中的基本操作分析如下。

1．1對稱密碼基本操作

比較常見的對稱密碼算法包括DES[1]、AES[2]、NSSU[1]、IDEA[1]、RC6[3]、MARS[4]、SERPENT[5]、Two－fish[6]、MD5[7]、SHA[7]等。DES和AES是NIST指定的標準對稱密碼算法；NSSU是前蘇聯政府公布的供保密通信使用的國家標準；RC6、MARS、SERPENT、Two－fish是與AES最后一輪競選時的對手算法；IDEA是一種比較常用的加密算法；MD5和SHA屬于安全散列算法。

將對稱加密算法中的操作分為以下幾類：邏輯操作(包括與、或、取反、異或操作等)；邏輯移位操作；循環移位操作；模乘操作（底數是 216+1或232）；模加/減操作（底數216或232）；有限域乘法（基于GF（ 28））；有限域加法（基于GF（ 28））；置換操作（包括對等位置換、基于對等字節置換以及擴展位置換）；S盒（8入8出，4入4出，6入4出）。表1總結了上述對稱密碼算法中所涉及的操作類型。

1．2公鑰密碼基本操作

在公鑰密碼體制中，密鑰對的選擇要保證從公鑰求出私鑰等價于求解一個困難的運算問題。構成常用公鑰密碼基礎的困難問題有如下的數論問題：

a)整數的因子分解問題；

b)離散對數問題；

c)橢圓曲線離散對數問題。

RSA[1]算法是基于大數分解的公鑰加密算法，其加/解密都是通過模冪運算來實現的。而模冪的基本操作是模乘操作，大整數的模乘操作可以看做是素數域GF(P)上的運算。

基于離散對數問題的ElGamal公鑰密碼的基本運算也是模冪運算，同樣可以轉換為素數域 GF(P)上的模乘運算。

基于橢圓曲線離散對數問題的密碼處理也可以分解成模乘運算：定義于素數有限域GF(P)上的橢圓曲線群上的點可以轉換成大整數的模乘運算；而定義于GF( 2m)上的橢圓曲線群上的點運算可以轉換成二進制多項式的模乘運算。

總之，公鑰密碼算法中的操作是有限域上的乘法和加法操作，本文所指的有限域一般為素數域GF（P）或二進制域GF( 2m)。公鑰密碼算法中操作數通常位數較多，如RSA密碼算法中通常為1 024 bit，甚至于2 048 bit，而ECC的密鑰長度相對較短，但也在200 bit以上。如果要在通用處理器上實現公鑰算法，就需要采用相應的多精度算法，將操作數拆分成適合于處理器字長的運算。因此，在通用處理器中，公鑰密碼的操作最終可以化成底數為2w的整數模乘、二進制多項式模乘、整數模加/減、二進制多項式模加等基本操作。其中，w為處理器字。

2密碼指令擴展研究現狀

密碼指令集擴展通過分析所采用的密碼算法，抽取影響密碼算法處理速度的操作，進行指令擴展來加速密碼運算。所擴展指令對應的操作可以是密碼算法的基本操作，也可以是多個基本操作的組合。

文獻[8]中提出了二進制多項式乘法指令MULGF2，雖然此指令是面向ECC算法提出的，但是其可以用于任何包含GF( 2m)上運算的密碼算法；文獻[9]將算法的探索和指令集擴展結合起來，認為指令集的擴展對未來新的密碼算法的設計有很好的借鑒意義；文獻[10]在采用二進制多項式乘法指令MULGF2的基礎上，提出了二進制域GF( 2m)的大數乘法、平方和減法的有效算術算法，最后還指出了指令集擴展改進的方向即將MULGF2和異或指令xor結合起來；文獻[11]設計了針對一種8 bit的AVR處理器的多項式乘法指令。

文獻[12]采用ECC中擴展的二進制多項式乘法指令mulgf 2、二進制多項式乘加指令maddgf 2和移位指令sha來加速AES算法的軟件實現；文獻[13]通過引入S盒指令sbox和二進制多項式乘法指令gf2mul來加速AES；文獻[14]提出了一種AESENC指令，此指令針對狀態矩陣的每一行進行執行字節替代、行移位和列混合三種操作；文獻[15]提出了sbox4s/isbox4s/sbox4r和mixcol4s/imixcol4s用于加速AES中的字節替換和列混合操作；文獻[16]提出Smix指令；文獻[17]提出用于執行任意的n位到n位對等置換的GRP指令。此指令加速了DES算法以及有對等置換操作的密碼算法的軟件實現效率；文獻[18]針對特定的嵌入式處理器CK520提出了用于增強加密、解密運算性能的PERM置換指令。

顯然，已有的密碼指令集擴展多是針對有限域GF( 2m)上的運算、S盒運算和置換運算，這是因為這些操作在通用的處理器上沒有得到很好的支持。文獻[8，10~13]中提出的二進制多項式乘法以及文獻[17，18]中的位置換指令具有很好的通用性，可以適用于任何包含相應操作的密碼算法。而像文獻[13]中的S盒指令、文獻[14]中的AESENC指令以及文獻[15，16]中的列混合指令則具有很大的專用性，只能適用于AES算法，當密碼算法改變時，性能不高。

3密碼指令擴展的發展方向

通過分析密碼指令集擴展研究現狀，可以發現目前的密碼指令擴展大多數是用于提高單個密碼算法性能的，主要分為兩類：a)面向密碼算法中的基本操作如二進制多項式乘法，位置換等。雖然這些指令的設計是針對特定的密碼算法，但由于此類指令面向的是密碼算法中的基本操作，因而具有很好的通用性，可以適用于包含此類操作的密碼算法；b)面向特定密碼算法中的特定運算，這類指令通常是面向基本操作的組合操作進行設計的，由于不同算法中基本操作的組合方式不同，此類指令專用性很強，面向此類算法速度很高，性能很好，但是一般不適用于其他密碼算法。顯然，兩類密碼算法指令設計各有優缺點，是提高通用性還是專用性，需要進行慎重考慮。

目前，密碼算法的種類十分繁多，而不同的網絡協議在不同的環境下會同時支持多種密碼算法，并且協議的更新、密碼算法的發展以及應用環境的變化等都使得系統支持的密碼算法在不斷地變化。例如Internet中廣泛應用的SSL安全協議為例，協議可以通過協商，采用IDEA、RC2－40，DES－40、DES、3DES、Fortezza、RC4－40和RC4－128密碼算法中的任一種給加上消息驗證碼的壓縮消息進行加密，計算消息驗證碼的哈希算法可以使用MD5或者SHA－1。僅僅采用一種密碼算法的系統已經不復存在。如此變幻莫測的系統環境使得采用專用性很強的密碼指令不切合實際，而且密碼指令集擴展的初衷就是要保留一定的靈活性的基礎上來加速密碼軟件實現性能，專用性強的指令違背了這個原則。指令的通用性越強，處理器面對密碼算法的變更適應性就越強，通用性是密碼計算指令發展的必然之路。

密碼指令的通用性僅僅能使處理器支持具有此類操作的密碼算法，如果想要支持更多種類的密碼算法，則需要擴展更多種類不被處理器有效支持的操作。每擴展一條指令，都需要增加相應的硬件資源。那么，處理器的規模會不會隨著擴展指令個數的增加而無限膨脹？通過研究常用密碼算法中的基本操作，可以看出密碼算法的基本操作大多局限于異或、循環移位、置換、S盒代替、整數模乘、整數模加、多項式乘法等少數幾種操作類型。因此隨著密碼算法個數n的增加，其重用操作和重用次數也會越來越多，按照多個密碼算法提取的擴展指令個數增長速度會越來越慢，其規模不會因為算法個數n的增加而無限膨脹。由此也可以看出，處理器所要支持操作的集合并不是各個密碼基本操作簡單的并集，而是這個并集減去所有重用的操作所得到的集合。

隨著處理器支持密碼種類的增多，未來處理器進行密碼指令集擴展的最終結果是通用密碼處理器。通用密碼處理器的設計，需要對多種密碼算法進行分析，抽取影響密碼算法處理速度的基本操作，然后針對這些基本操作研究處理器中需要進行擴展的指令。通用密碼處理器中的指令都具有很好的通用性，能夠適用于具有此類操作的密碼算法。

4結束語

綜上所述，針對密碼指令集擴展的研究已經取得了不少成果，但是所擴展的指令存在專用性強的問題，這些指令僅僅在處理特定的密碼算法時可以獲得性能的提升，并不能滿足不同密碼用戶多層次的安全性能需求和密碼算法不斷更新換代的需要，從而在安全方面留下隱患。未來密碼指令的設計要朝通用性上發展，而且針對多個密碼算法進行指令集擴展的通用密碼處理器是未來發展的必然趨勢。

參考文獻：

[1]盧開澄. 計算機密碼學[M]. 北京: 清華大學出版社，1998.

[2]單玉峰. 一種新的加密標準AES[J]. 信息技術，2002(11):32－33.

[3]李莉，張煥國. 高級加密標準AES候選之一——RC6[J]. 通信保密，2000(1):57－61.

[4]崔競松，張煥國. 高級加密標準AES候選之一——MARS算法[J].通信保密，2000(2):59－64.[5]李斕，張煥國. 高級加密標準AES候選之一——Serpent算法[J]. 通信保密，2000(2)68－72.[6]范春湘，張煥國. 高級加密標準AES候選之一——Twofish算法[J]. 通信保密，2000（2）:53－59.

[7]蔡皖東. 網絡信息安全[M].西安：西北工業大學出版社，2004.

[8]BARTOLINI S， BRANOVIC I， GIORGI R， et al. A performance evaluation of ARM ISA extension for elliptic curve cryptography over binary finite fields[C] //Proc of 16th Symposium on Computer Architecture and High Performance Computing.Washington DC: IEEE CS Press， 2004.

[9]GROBSHDL J， IENNE P， POZZI L， et al. Combining algorithm exploration with instruction set design:a case study in elliptic curve cryptography[C] //Proc of the 9th Conference on Design， Automation and Test in Europe. WashingtonDC: IEEE CS Press， 2006.

[10]GROBSCHDL J， KAMENDJE G A. Instruction set extension for fast elliptic curve cryptography over binary finite fields GF(2m)[C] //Proc of the 14th Conference on Application－specific Systems， Architectures and Processors. WashingtonDC: IEEE CS Press，IEEE Computer Society Press， 2003.

[11]KUMAR S， PAAR C. Reconfigurable instruction set extension for enabling ECC on an 8－bit processor[C] //Proc of the 14th International Conference Field Programmable Logic and Application. Berlin: Springer－Verlag， 2004.

[12]TILLICH S， GROBSCHDL J.Accelerating AES using instruction set extensions for elliptic curve cryptography[J]. Computational Science and Its Applications， 2005， 3481: 665－675.

[13]TILLICH S， GROBSCHDL J， SZEKELY A. An instruction set extension for fast and memory－efficient AES implementation[J]. Communications and Multimedia Security， 2005，3677: 1－21.

[14]NADEHARA K， IKEKAWA M， KURODA I. Extended instructions for the AES cryptography and their efficient implementation[C] //Proc of the 18th IEEE Workshop on Signal Processing Systems， Piscataway. Washington DC:IEEE Computer Society Press， 2004.

[15]TILLICH S， GROBSCHDL J.Instruction set extensions for efficient AES implementation on 32－bit processors[J].Cryptographic Hardware and Embedded Systems， 2006， 4249: 270－284.

[16]BERTONI G， BREVEGLIERI L， FARINA R.Speeding up AES by extending a 32－bit processor instruction set[C] //Proc of the 17th IEEE International Conference on Application－Specific Systems， Architectures and Processors. Washington DC: IEEE Computer Society Press， 2006.

[17]SHI Zhi－jie. Bit permutation instruction architecture implementation and cryptographic properties[D]. New York: Princeton University， 2004.

[18]潘國振，王界兵，嚴曉浪. 高性能嵌入式CPU特殊指令單元的設計與實現[J]. 浙江大學學報:工學版，2005，39(2):211－215.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文