國產通用處理器密碼算法指令實現研究*

陳子鈺，何 軍，郭翔宇

(上海高性能集成電路設計中心,上海 201204)

1 引言

密碼安全是信息安全的基石，密碼算法作為保證密碼安全的關鍵技術已被廣泛應用于信息加密傳輸、可信計算等領域，深刻地影響著信息安全和國家安全。因此密碼算法及其執行效率是學術界研究的重點之一。采用純軟件的方式優化密碼算法執行程序[1]、采用定制專用硬件電路[2]或專用處理器[3,4]實現密碼算法、采用指令集架構ISA(Instruction Set Architecture)擴展[5 - 7]來支持密碼算法，是當前最具代表性的3類提升密碼算法執行效率的方式。純軟件優化的方式雖然靈活、成本低，但是優化空間有限且易受側信道攻擊；專用電路和專用處理器實現的方式雖然執行速度快，但成本高、靈活性和可擴展性不佳、不易與其它系統融合。相對而言，面向特定的密碼算法采用指令集架構擴展的方式[8]兼顧了硬件和軟件的不同特性，同時具有軟件優化和硬件加速的優勢。該方法既能用硬件加速執行密碼算法中的關鍵操作，又方便軟件靈活使用，可以很好地平衡密碼算法執行效率與硬件開銷、設計靈活性和可擴展性之間的矛盾，達到以較少的硬件資源大幅提升密碼算法執行效率和降低代碼占用空間的效果，還能靈活地與其他運算模塊融合，實現很強的可擴展性。

高級加密標準AES(Advanced Encryption Standard)[9]和安全散列算法SHA(Secure Hash Algorithm)[10]是2種當前應用廣泛且影響深遠的密碼算法，處理器對這2種密碼算法的支持情況極大地影響著其在密碼安全應用領域的競爭力。Intel X86、IBM Power和ARMv8等主流通用處理器架構中都針對AES和SHA密碼算法進行了指令集擴展。基于對AES和SHA密碼算法的研究，參考國內外主流通用處理器的密碼指令集實現，本文采用指令集架構擴展優化的方式對AES算法和SHA進行指令擴展優化，面向國產通用處理器設計了AES和SHA密碼算法擴展指令集，實現了全流水執行的AES和SHA密碼算法指令部件，并進行了實現評估分析和優化，以期提高國產通用處理器執行密碼算法的效率，并進一步增強國產處理器芯片在密碼安全應用領域的性能和競爭力。

2 AES和SHA密碼算法

當前，國際主流的密碼算法主要有RSA(Rivest,Shamir,Adleman)算法、橢圓曲線ECC(Elliptic Curve enCryption)算法、高級加密標準AES和安全散列算法SHA等。其中AES算法和SHA是由美國國家標準與技術研究所NIST(National Institute of Standards and Technology)制定和發布的通用密碼算法，因被廣泛使用而在國際上有深遠的影響。

2.1 AES算法

AES算法因具有安全性強、加密效率高、硬件開銷小和靈活易用等優勢已被廣泛應用于信息加密和密碼芯片等領域。AES算法是一種分組密碼算法，其輸入、輸出分組和加密、解密過程中的中間分組均為128 bit，使用Nr個輪，每輪均需要一個擴展密鑰Key參與(Nr取10,12或14，對應的輸入密鑰長度為128,192或256 bit)。受限于輸入密鑰的長度，AES算法在運算過程中需要進行密鑰擴展(Key expansion)，以生成各輪的輪密鑰。AES算法的加密流程主要運用了查找SBox并進行字節置換、行變換、列混合和密鑰加等4個轉換操作。其中，SBox字節置換是指按設定的轉換表對每個字節用SBox作一個置換進而生成狀態矩陣；行變換的基本操作是循環移位(右移);列混合的基本操作是邏輯異或和定義在有限域上的多項式乘法，多項式乘法運算采用矩陣乘實現；密鑰加的基本操作是邏輯異或。除最后一輪僅用3個(無列混合)轉換外，每一輪都使用4個可逆的轉換。解密是加密的逆過程，在此不再詳述。由于AES算法加解密過程運算復雜度高，因此處理器對AES算法的支持性能成為AES算法高效運行的主要限制因素。

2.2 安全散列算法SHA

SHA是一組哈希密碼算法，主要用于數字簽名、散列消息認證碼和生成隨機數等應用。安全散列標準SHS(Secure Hash Standard)FIPS 180-4規定了SHA-1、SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224和SHA-512/256等算法。所有的算法都是根據消息字迭代算法對應的哈希函數來產生消息摘要字，所有操作均以字為單位。SHA中的主要參數如表1所示，對于SHA-1、SHA-224和SHA-256算法，字長為32位，消息塊大小為16個字(512位)，其它算法字長為64位，消息塊大小為16個字(1 024位)。

Table 1 Main parameters of SHA表1 SHA的主要參數

3 主流通用處理器對密碼算法應用的支持

采用在ISA中擴展密碼算法指令的方式能大幅提升密碼算法的執行效率，同時還具有硬件開銷小、代碼占用空間小、靈活性好和可擴展性強等優勢。因此，國際主流的通用處理器架構都是通過定義專門的密碼算法指令，以擴展指令集的方式來實現處理器對主要密碼算法的支持，進而提升處理器在密碼安全應用方面的性能。當前，為增強對AES和SHA密碼算法應用的支持，Intel X86架構、IBM Power架構和ARMv8架構都在原有指令集的基礎上新增了針對AES和SHA密碼算法的擴展指令集，如表2所示。其中，Intel X86架構新增了包括6條AES密碼指令的高級密碼標準指令集AES-NI[11]和7條SHA擴展指令[12]，分別用以加速AES加/解密標準算法和SHA(特別是SHA-1和SHA-256)；IBM Power指令集[13]也為AES加/解密標準算法新增了5條指令，同時針對SHA-256和SHA-512新增了2條SHA密碼算法指令；ARMv8指令集也面向AES和SHA密碼算法應用分別擴展了4條和10條密碼算法指令[14]。

Table 2 AES/SHA extended instructions of mainstream general purpose processors表2 主流通用處理器的密碼擴展指令集

對于AES算法，主流通用處理器的指令集架構的擴展指令都是對輪加/解密中的幾個過程進行合并從而實現為一條指令。所不同的是，Intel X86區分了加密輪和尾加密輪，但依然保留了列混合指令。同時，Intel X86有一條專用的密鑰生成指令，這條指令對應AES-256密鑰生成規則。IBM Power8也區分了加密輪和尾加密輪，單獨設有用于字節替換的SBox查找指令(可用于密鑰生成Sub Word函數)。ARMv8中將列混合單獨作為一條指令，同時不區分是否是最后一輪。上述處理器架構中的指令均為128位向量指令。對于SHA：主流通用處理器的指令集架構主要支持SHA-1、SHA-256和SHA-512，均為128位向量指令。其中,IBM Power8沒有指令支持SHA-1，但有指令支持SHA-512，Intel X86和ARMv8不支持SHA-512。SHA密碼算法擴展指令主要針對Hash計算提供指令加速，沒有對消息填充和分塊提供支持。其中，IBM Power8沒有對整輪Hash計算過程提供指令支持，而針對Hash計算中的關鍵函數sigma提供指令支持；Intel X86和ARMv8對整輪Hash計算提供指令支持，包括消息調度和工作變量更新。

當前，國內主要的處理器研制廠商和機構普遍都采用或兼容Intel X86、IBM Power或ARMv8等主流通用處理器架構及其指令集，因此暫未見到專門面向國產處理器而自主設計的AES和SHA密碼算法擴展指令集被公布。然而，我國一直非常重視信息安全和密碼研究，為了加速密碼算法的執行以增強國產處理器在支持主要密碼算法應用方面的性能，國內的主要處理器研制廠商和機構都在積極地發展密碼算法擴展指令集，以提升國產處理器芯片在密碼安全領域的競爭力。目前，中科龍芯、天津飛騰和兆芯等處理器研制機構都已經在兼容原有指令集架構的同時發展了支持部分國密算法的擴展指令集[15]。

4 國產通用處理器密碼算法指令集及其實現

密碼算法擴展指令集設計必須采用原有指令系統的指令格式和編碼規則，以保證新增指令與原有指令集兼容。同時，新指令的數量不宜過多且執行部件不能太復雜，以避免帶來過多的硬件開銷導致系統運行速度降低。

4.1 國產通用處理器密碼算法擴展指令集

為實現國產通用處理器對AES算法和SHA的支持，根據高級加密標準 (AES) FIPS 197和安全散列標準FIPS 180-4，參考國內外主流處理器的密碼指令集設計，針對國產通用處理器架構的指令格式和 256位SIMD(Single Instruction Multiple Data)的特點，結合硬件實現，本文設計了面向國產通用處理器的AES、SHA密碼算法擴展指令集，如表3所示，指令長度為32位，指令格式有簡單運算指令格式、復合運算指令格式(立即數)和復合運算指令格式(寄存器)3種。AES密碼算法擴展指令集支持FIPS 197標準定義的AES算法，包括5條指令，分別用以支持AES所規定的加密輪、加密尾輪、解密輪、解密尾輪和SBox字節替換操作。SHA密碼算法擴展指令集支持FIPS 180-4標準定義的SHA，包括8條指令，主要對Hash值計算中的消息調度字準備和工作變量字迭代更新2個重要過程進行加速，支持SHA-1、SHA-256和SHA-512。

Table 3 AES/SHA extended instructions of domestic general purpose processors表3 國產通用處理器的密碼算法擴展指令集

4.2 密碼算法指令部件的設計實現

密碼算法擴展指令集在支持密碼算法的同時不應降低原指令集架構的性能，也不宜增加太復雜的硬件。在密碼算法指令集執行部件實現的過程中需要將可以并行的部分盡量并行，以使所有的指令都能全流水實現，以減少時間延遲，可以共享的部分盡量共享，以減少硬件開銷。同時，為了能滿足國產通用處理器的工作頻率要求，需要將算法劃分為盡可能一致的運算分量，且每一個時鐘周期的邏輯不能過多。

Figure 1 Structure of cryptographic algorithm instruction unit圖1 密碼算法指令部件結構

根據AES和SHA密碼算法指令集，密碼算法指令部件的結構如圖1所示，按密碼算法的特征，分別設置AES和SHA 2個子部件，均支持全流水運算。其中，AES密碼算法指令子部件的功能是實現5條AES指令，主要基本操作為查表、移位和邏輯異或。并且級聯的邏輯數不是很多，各條指令均能在1個時鐘周期之內完成。SHA密碼算法指令子部件的功能是執行8條SHA指令，由于要實現迭代運算，因此需要根據迭代次數和運算邏輯量進行時鐘周期劃分，按照頻率要求，分別將各條指令的運算劃分成基本一致的1～8段運算分量。為減少硬件開銷，在滿足算法邏輯功能的前提下需要對密碼算法的運算過程進行優化。

4.2.1 AES密碼算法指令實現

AES密碼算法指令子部件的主要功能是對AES查找SBox并替換字節、AES加/解密輪及其尾輪提供加速，完成 AES輪加密(VAESENC)、AES尾輪加密(VAESENCL)、AES輪解密(VAESDEC)、AES尾輪解密(VAESDECL)和AES字節替換(VAESSBOX)5條指令。子部件主要執行查找加密轉換表SBox并替換字節生成狀態矩陣、行移位變換、列混合變換、加密密鑰加、查找解密轉換表InvSBox并替換字節、行移位逆變換、列混合逆變換和解密密鑰加等操作過程，其底層的邏輯操作是查表、移位和異或。

AES密碼算法指令子部件的結構如圖2所示，分別為加密和解密過程定義的基本操作，設置加密查表轉換(SUBBYTES)、行移位變換(SHIFTROWS)、列混合變換(MIXCOLUMNS)、解密查表轉換(INVSUBBYTES)、行移位逆變換(INVSHIFTROWS)和列混合逆變換(INVMIXCOLUMNS)6個子模塊。根據指令控制信息和輸入數據，選擇對應的數據通路即可實現AES密碼算法指令。AES密碼算法指令子部件的輸入和輸出數據的位寬均為256位，可以使用128,192 和 256 位密鑰的迭代式對稱密鑰塊密碼，并且可以對 128 位(16 個字節)的數據塊進行加密和解密，每條指令的執行延遲為1個時鐘周期。

Figure 2 Instruction subassembly structure of AES 圖2 AES密碼算法指令子部件結構

為加速算法執行，將SubBytes和InvSubBytes所定義的表格信息直接用專用電路實現，可以有效地減少因執行AES算法的查表和訪存而造成的延遲。此外，行移位變換在電路實現上只需改變信號連線的組合，因此除導線上的信號延遲外移位操作不需要其他時間開銷。因為尾輪加密和輪加密相比僅僅少了一個列混合變換，因此VAESENC指令和VAESENCL指令可以共享一組硬件來實現，同理VAESDEC指令和VAESDECL指令也可以共享一組硬件，這樣有效地減少了硬件開銷。

4.2.2 SHA密碼算法指令實現

Figure 3 Instructions subassembly structure of SHA 圖3 SHA密碼算法指令子部件結構

與AES密碼算法指令子部件同理，通過改變電路連線直接實現移位操作可有效加速算法中的移位運算。為進一步加速算法執行，實現中將常數選擇子模塊定義的常數直接用專用電路實現,以減少SHA算法中常數選擇判斷帶來的延遲。此外，需要將能壓縮的工作字盡早壓縮，以縮短壓縮數據所需的時間延遲；將能并行的操作盡可能地并行，以減少工作字迭代帶來的時間延遲。在SHA1MSW和SHA512MSL0指令中，因為各消息調度字的生成是獨立的，因此這2條指令可各自同時將8個消息調度字并行生成；SHA256MSW和SHA512MSL1指令中由于工作字之間存在數據真相關，單條指令每時鐘周期最多只能并行生成2個工作字；SHA1R、SHA256R、SHA512R0和SHA512R1這4條指令中由于每個工作變量字均依賴于前一個工作變量字，因此同一條指令的工作字生成過程無法直接并行，但可采用流水執行來實現，并且在每個工作變量字的生成過程中要盡早壓縮能壓縮的數據。為減少硬件開銷，以減小面積和功耗，實現中采用改進運算步驟的方式對SHA1R的字更新算法進行了優化，將4個條件選擇支路中模2w加運算提到選擇支路之外，即先選擇常數和函數，然后再進行模2w加和壓縮，優化后的算法相比原算法在不改變時序延遲和正確性的前提下可減少24個CSA3B2和24個CSA4B2壓縮器。此外,SHA512R0和SHA512R1指令的迭代流程相同，只是選取不同結果數據，因此可共享一套硬件來節省硬件開銷。

5 密碼算法指令實現評估

對照高級加密標準FIPS 197和安全散列標準FIPS 180-4可知，本文提出的密碼算法擴展指令集對AES和SHA提供了比較完備的支持。對比主流通用處理器架構中的密碼算法擴展指令集，對AES算法，該AES擴展指令集的功能設置與Intel X86、IBM Power和ARMv8等主流通用處理器指令集中的AES擴展指令集大致相同，但因該AES擴展指令集中的所有指令支持256位的SIMD運算，并且在實現上都僅需1個時鐘周期即可完成，因此具有更短的執行延遲。對SHA，由于不同的SHA擴展指令集提供的加速過程及其運算量都不一致，難以直接通過對比指令的延遲時鐘周期數來評估不同擴展指令集間的性能差異，但在功能上本文提出的SHA擴展指令集能同時支持SHA-1、SHA-256和SHA-512，并且既能加速工作字迭代，又能加速消息調度字生成，因此該SHA擴展指令集比當前主流的SHA擴展指令集的功能更加完善。

為驗證密碼算法指令部件的功能和執行結果的正確性，本文采用已經驗證正確性的密碼算法程序為參考模型，通過源操作數取隨機值和典型特征值的方法進行大量模擬實驗。此外，還針對設計實現代碼進行了代碼覆蓋率和功能覆蓋率分析，代碼覆蓋率和功能覆蓋率均可達100%。實驗表明，密碼算法指令部件的功能和執行結果正確，達到了設計預期。

為評估密碼算法指令部件的時序、功耗和面積等性能指標，采用Design Compiler綜合工具，基于某工藝條件，時鐘頻率2.0 GHz，對密碼算法指令部件的Verilog設計代碼進行了邏輯綜合，結果如表4所示。其中，對SHA1R算法的優化可使SHA密碼算法指令子部件面積減小3.32%，功耗減小0.94%。

Table 4 Logic synthesis results of AES and SHA表4 密碼算法指令執行部件綜合結果

為分析AES和SHA密碼算法擴展指令相比原指令集對密碼算法執行效率的改善，需分析密碼算法指令部件相對軟件采用原有通用指令實現密碼算法的加速比。由于軟件程序在實際執行時情況非常復雜，且采用相同指令集的不同處理器的硬件配置也各有差異，為使指令集性能優化分析結果不依賴于具體的硬件配置、軟件執行環境和測試平臺，同時使分析過程有效和簡化，對軟件采用的原有通用指令執行密碼算法做以下假設：(1)密碼算法中查表所需的數據已全部存儲到處理器的數據緩存中；(2)所有訪存全部命中；(3)所有指令全部流水執行；(4)不存在數據真相關的指令全部能并行執行。

以AES輪加密指令VAESENC為例，采用AES密碼算法指令部件實現只需1個時鐘周期即可完成，但如果通過軟件采用原有通用指令來實現則需要查SBox表替換字節、行移位、列混合、加密鑰加4個過程，依次需要調用裝入立即數指令(LDI，1個時鐘周期)、裝入長字整數指令(FLDD，4個時鐘周期)、長字邏輯右移指令(SRLL，1個時鐘周期)和邏輯異或指令(XOR，1個時鐘周期)，即便不考慮處理器并行指令數的限制，軟件最少也有7個時鐘周期的執行延遲，因此AES輪加密指令VAESENC具有7.00倍的最小加速比。

基于上述假設，分別分析軟件采用原有通用指令實現AES和SHA擴展指令的最小執行延遲。結果如表5所示，AES指令部件的最大執行延遲DImax均為1個時鐘周期，軟件實現AES指令對應算法的最小延遲DSmin為5～19個時鐘周期。用軟件的最小執行延遲DSmin與AES指令部件的最大延遲DImax的比值表征密碼算法指令的最小加速比，則AES指令的最小加速比為5.00～19.00倍，幾何平均數為8.90倍。SHA指令部件的最大執行延遲DImax為2～9個時鐘周期，軟件實現SHA指令對應算法的最小延遲DSmin為5～74個時鐘周期。不同SHA指令的最小加速比為2.50～8.22倍，幾何平均數為4.75倍。因AES和SHA密碼算法指令部件均支持全流水執行，因此SHA密碼算法指令的實際平均執行延遲會小于最大執行延遲DImax，即在全流水執行的情況下每個時鐘周期都能完成一條密碼算法指令，此時SHA密碼算法指令的最小加速比達5.00～74.00倍，幾何平均數為19.30倍。考慮到軟件在使用原有通用指令實現密碼算法時還存在構建查表、訪存不命中、處理器指令執行部件和并行指令數有限、不能全部流水執行等情況，實際的軟件程序延遲會大于最小延遲DSmin，AES和SHA密碼算法指令的實際加速比會大于最小加速比。因此,表明該密碼算法指令部件能顯著地加速處理器對密碼算法的執行效率。

Table 5 Speed up of AES/SHA instructions表5 密碼算法指令部件的性能加速比

6 結束語

本文基于國際主流密碼算法AES和SHA,綜述了主流通用處理器架構的密碼算法指令發展現狀;面向國產通用處理器設計了一個密碼算法擴展指令集，包括5條AES密碼算法指令和8條SHA密碼算法指令，相比于當前主流的密碼算法擴展指令集，該擴展指令集能對AES密碼算法和SHA密碼算法提供更完備的加速支持，并且AES指令具有更短的執行延遲。還實現了能全流水執行的AES和SHA密碼算法指令部件，通過流水執行、專用硬件電路實現查表、及時壓縮中間運算結果以及改進運算步驟等方法對算法實現進行了優化，既提高了算法執行效率，又減少了密碼算法指令部件的硬件開銷和功耗。最后對本文設計進行了正確性驗證、邏輯綜合和性能評估分析。結果顯示，該密碼算法指令部件的功能和正確性達到了設計預期，工作頻率可達2.0 GHz，總面積為17 644 μm2,總功耗為59.62 mW。相比基于原有通用指令集采用軟件實現密碼算法，新增AES和SHA密碼算法指令后，密碼算法指令部件對AES密碼算法的最小加速比為8.90倍，對SHA密碼算法的最小加速比為4.75倍，全流水情況下可達19.30倍。表明新增密碼算法指令集及其執行部件能顯著加速處理器對密碼算法執行的性能，有望應用于國產通用處理器并進一步提升國產通用處理器芯片在密碼安全應用領域的競爭力。此外，該密碼算法指令部件還可以封裝成專門用于支持密碼算法的IP，應用于密碼安全領域的專用芯片中。