SHA-2算法在多核密碼處理器上的實現研究

曲思源 戴紫彬 李 偉，* 戴 強

SHA-2算法在多核密碼處理器上的實現研究

曲思源1戴紫彬2李 偉1，2*戴 強1

1(解放軍信息工程大學 河南 鄭州 450002)

2(復旦大學專用集成電路與系統國家實驗室 上海 201203)

為了找出一種適合多核密碼處理器的SHA-2算法高速實現方式，提高SHA-2算法在多核密碼處理器上的執行速度。首先研究SHA-256、SHA-512算法在密碼處理器上的實現方式，并研究多核密碼處理器的結構特點與數據傳輸方式，分析SHA-2算法在多核上的高速實現原理。然后對SHA-2算法進行任務劃分，提出SHA-2在多核密碼處理器上的調度與映射算法并使用軟件實現調度算法。在ASIC上的仿真驗證結果表明，經優化后的SHA-2算法在多核上并行執行吞吐率有了較大提升，滿足性能上的需求。

SHA-2 多核 密碼處理器 任務調度與映射

0 引 言

SHA算法是由美國國家標準技術研究所和美國國家安全局共同設計的雜湊算法，是使用最為廣泛的安全雜湊算法之一。SHA算法分為SHA-1、SHA-2和SHA-3。 SHA-2算法是目前較多使用的SHA算法。

密碼處理器是針對密碼算法設計的專用指令集處理器，它集成了大量密碼運算單元并設計了專用密碼運算指令。在加密運算中一個編碼環節對應一個運算單元，使它在實現密碼算法時性能大大高于通用處理器，同時可重構的設計使它可以靈活配置，適配多個算法[1]。使用密碼處理器可以實現包含SHA-2在內的多個算法或安全協議，相比于FPGA的實現方式具有更高的靈活性。

為了進一步提升密碼運算性能，設計了多核密碼處理器，該架構采用基于Mesh結構的分簇式設計，將多個同構密碼處理器、控制器以及共享存儲區域集成進一個簇，并可以通過中央調度器實現簇間通信。

在多核運算中，任務分配與調度是提高處理效率的重要環節。本文主要探討如何根據密碼處理器上SHA-2算法的實現特點對其進行任務劃分，并設計劃分后的SHA-2算法在多核架構下的調度與映射算法，以充分發揮多核架構的資源優勢，進一步提升SHA-2在密碼處理器上的處理速度。

1 SHA-2算法高速實現研究

1.1 SHA-2算法介紹及其單核實現

本設計采用的密碼處理器基于VLIW結構。這種結構的密碼處理器在每個時鐘周期內發射固定數目的密碼處理指令集合，它具有較大的數據處理位寬和多處理單元并行結構[2]，使彼此沒有數據相關的指令可以在各自對應的功能部件中并行執行。這種設計[1]有效減少了指令條數，增加了指令執行的并行度，提高了處理性能。

SHA-256的核心由64步迭代運算構成，并使用六種基本的邏輯函數。每步以當前正在處理的消息塊和32位緩存值A、B、C、D、E、F、G、H為輸入，再更新A、B、C、D、E、F、G、H的內容，每步迭代運算還使用一個額外的32位常數值Kt。

SHA-512算法與SHA-256算法結構相同，不同之處是SHA-512算法有80步迭代運算，且緩存對應的處理位寬為64位[3，4]。

以SHA-256為例，算法使用的基本函數[4]如下：

Ch(e,f,g) = (e & f) ^ (～e & g);

Maj(a,b,c) = (A & B) ^ (B & C) ^ (A & C);

Σ1(E) = {E[5:0],E[31:16]} ^ {E[10:0],E[31:11]} ^ {E[24:0],E[31:25]};

Σ2(A) = {A[1:0],A[31:2]} ^ {A[12:0],E[31:13]} ^ {A[21:0],E[31:22]};

R1(W1) = {W1[6:0],W1[31:7]} ^ {W1[17:0],W1[31:18]} ^ {3'b000,W1[31:3]};

R2(W14) = {W14[16:0],W14[31:17]} ^ {W14[18:0],W14[31:19]} ^ {10'b00_0000_0000,W14[31:10]};

其中，Ch、Maj由三值邏輯函數指令實現，Σ1、Σ2、R1、R2由帶移位的三值邏輯函數指令實現，T1的實現使用了模加指令。此外，算法還用到了異或指令、循環移位指令、邏輯移位指令，這些指令屬于密碼處理器專用指令集。

在圖1的算法程序中，配置信息主要配置用于獲得Kt的查找表與處理器需要輸入數據的端口的數據長度。程序的主體由數據塊擴展與循環迭代運算組成。這兩種運算占用了整個算法程序的90%以上。W0～W63需要64個緩存單元存放數據供迭代運算調用，每次運算為不同緩存單元賦值，因此同一程序段順序出現48次(前16次是MOV操作)。在迭代運算中，由于8個哈希值每迭代一輪更新一次，因此只需8個緩存單元，程序設計為循環結構。

圖1 單處理器SHA-256實現流程

1.2 SHA-2高速實現原理

由單處理器實現SHA-256看出，數據擴展運算與迭代運算重復次數較多。在數據較大、數據塊較多的情況下，單核實現算法會消耗大量指令條數，降低算法的運算速度。

由于SHA-2算法中數據擴展環節與輪運算環節并不是所有運算都存在數據相關，沒有依賴的運算可以拆分至密碼處理器的不同核上并行執行以縮短整個算法的執行時間，提高吞吐率。SHA-512算法中數據位寬為64比特，單核運算時需要按高低位先后執行，將高低位分配至不同的核進行計算并通過通信指令在核間進行數據交互同樣可以實現并行化，提高執行效率。

利用SHA-2算法結構的這些特點可以將SHA-2算法按任務或數據拆分，在多核密碼處理器上高速實現SHA-2算法。

1.3 SHA-2多核處理結構

本文設計的多核架構采用如圖2所示的基于Mesh結構的分簇式設計。多核間的數據傳輸模型為共享地址空間和消息傳遞混合式。核A向核B要發送的數據先寫入核間共享存儲區，再由核A向核B發送確認信息，核B接收到確認信息后從核間共享存儲區讀取已保存的數據。這種通信方式的特點是支持核間數據廣播式傳輸，一個核向多個核發送數據不會增加額外的指令條數，同時開辟了核間公共存儲區，不占用核內存儲資源，非常適合SHA-2這種緩存數據生存周期較長的算法。

圖2 多核密碼處理器架構和通信方式

由于通信過程由處理器自身的指令完成，因此通信開銷可以看作處理器額外的任務。在需要向下一個任務提供數據的任務后添加發送數據指令，通信時所需指令條數由寫入數據量決定，發送完成后再添加發送信件指令。在需要接收上一個任務數據的任務前添加查詢郵箱指令，再添加接收數據指令，通信時所需指令條數由讀取數據量決定。

2 多核上SHA-2算法劃分方式

2.1 基于任務的劃分方式

使以SHA-256為例，在數據擴展運算中，Wt生成后保存在寄存器中，循環48次得所有Wt。Wt與Wt-1沒有數據相關性，二者可劃分為并行任務。Wt的生成依賴于Wt-2，因此生成Wt-2必須作為生成Wt的前驅任務。

在循環迭代部分，生成T1、T2二者之間沒有數據相關，可以并行處理；g、f、h生成和b、c、d生成沒有數據相關，可以并行處理；e的生成依賴于T1，生成T1作為生成e的前驅任務；a的生成依賴于T1、T2，生成T1、T2同時作為生成a的前驅任務。

圖3為SHA-256算法的任務拆分示意圖。根據任務劃分，在一次迭代運算中，將相互之間沒有依賴的任務拆分到多個核上并行執行，將存在依賴關系的任務進行適當合并。如圖3，T1與e、a合并，令T1表示合并后以T1為主的新任務。T2、b、c、d、f、g、h順序執行時總指令周期數小于新T1，因此將它們合并，令T2表示合并后以T2為主的新任務。

圖3 SHA-256任務劃分與DAG圖

2.2 任務與數據混合劃分

在SHA-512算法中，輸出雜湊值長度為512比特，初始值為8個64比特的字，在輪運算過程中，數據長度為64比特。在專用密碼處理器中，通用寄存器設定的處理位寬為32比特，因此大位寬運算需要高位低位分別先后執行，SHA-512在密碼處理器上實現時指令存儲器使用率與緩存哈希值更新一次的運算時間均是SHA-256的2倍以上，資源占用大且運算時間較長。可以采用多核分別同時處理大位寬運算的高低位數據的方法提高運算的并行度，從而提高算法執行速度。

SHA-512主要使用三值邏輯函數、異或指令、模加、移位指令。前兩種指令是按位運算，可以直接由兩個核同時使用，分別處理數據的高32位與低32位，運算結果直接放入高位緩存與低位緩存，供下步運算，運算過程中不產生數據交互。模加指令涉及低位向高位進位，由匯編器插入通信指令完成進位的傳遞，并保存在目標核的指定寄存器內與高位數據進行運算。移位指令涉及64位數據整體移位，會產生數據交互，由通信指令來完成高低位數據交互。其中循環移位實現方式如圖4所示，邏輯移位的實現同理。

圖4 高低數據位任務通信流程

根據以上分析，對于SHA-512算法可以在任務劃分的基礎上進行進一步劃分，每一個任務拆分成高數據位部分與低數據位部分，并添加通信類指令構成新的任務TH或TL。最終運算結果更新的8個哈希值同樣分為高32比特與低32比特放入高位緩存與低位緩存中進入下一個數據塊的運算。

基于這種拆分，在DAG圖中生成并行任務對，該任務對由高數據位任務與低數據位任務組成，由兩個相鄰的核同步執行，如圖5所示。

圖5 SHA-512拆分后任務對示意圖

3 任務調度與映射

在完成了算法的任務劃分后，按以下規則在多處理器系統上進行任務映射。

算法程序由密碼處理器指令編寫，任務大小和相關數據大小可以通過剖析指令代碼獲得，因此調度模式為靜態調度[5]。由匯編器完成任務調度、任務映射至處理器與存儲資源重新分配，匯編器插入通信指令完成核間數據傳輸。將分配后的指令代碼注入各處理器的指令存儲器，以完成算法配置。數據拆分工作由上位機完成，算法配置完成后，通過向各處理器的指定端口寫入拆分后的數據使處理器開始工作。需要用合適的算法將DAG圖上的任務映射至多個同構密碼處理器上根據具體需求，主要調度目標有單算法實現和多算法實現[6]。

為使性能達到要求，對于SHA-256/512，定義單核執行一個數據塊所有循環T1任務的時間為單位時間tu：

tu=(tT1+te+ta)×64

對于SHA-256，根據前文分析，需要4個核，調度方案如圖6所示。對于SHA-512，由于任務對的存在，需要兩個處理器簇，因此在運行時存在兩種通信方式，核間郵箱通信與簇間通信，映射時應考慮減小功耗。經分析，每個數據塊在64次循環迭代運算中任務對TP有較多通信，這些T任務對應該放入同一簇內，相較而言，Wt擴展任務與輪運算任務通信較少，Wt的TP可以放入另一個簇內。SHA-512映射后如圖7所示，圖中粗箭頭表示數據通信方向。

圖6 SHA-256映射方案

圖7 SHA-512映射方案

以上為單算法的基本映射方案，在適配多個算法時，為盡可能降低功耗，應考慮最大限度利用處理器資源，減少同時工作的核數。同時為了保證性能，單個核上的任務要滿足單位時間tu的要求。定義一個處理器在tu約束下無法再增加其他任務集合的狀態為飽和狀態，一個處理器上映射了1個T任務集合(T1/T2/TH/TL)或2個W任務集合(Wt/WH/WL)即達到飽和狀態。根據飽和狀態可確定多算法映射時需要的核數，并將未使用或暫時未使用的核的時鐘關閉。

當一個程序由n個SHA-256算法與m個SHA-512算法組成時，首先計算出所有SHA-2算法拆分后的任務總數為：

Tnum=2n+4m

Wnum=(2n+4m)/2=n+2m

需要的總核數Pnum和處理器簇的個數Cnum為：

Pnum=Tnum+Wnum

Cnum=Pnum/4

確定了使用的處理器資源數量后，按順序將任務映射至每個核上，映射算法基于上文分析的兩種基本映射方案，并采用表調度的思想，將SHA-512優先級設為高，將SHA-256優先級設為低，將SHA-512/256的子任務集合中Wt/WH/WL優先級設置為高，T1/T2/TH/TL設置為低，按這種優先級順序映射，以處理器負載飽和為目的。在映射第一個算法時使該算法分布在一個或兩個簇內，映射下一個算法時選擇與前一個簇Cprev相鄰的簇Cnext映射，并首先在Cprev中尋找未達到飽和狀態的核進行任務填充，在Cprev的處理器全部達到飽和狀態后轉向映射Cnext簇。圖8-圖10顯示了多個算法的映射方案，圖中粗箭頭表示核間數據通信方向。

圖8 2個SHA-512映射方案

圖9 1個SHA-512與2個SHA-256映射方案

圖10 4個SHA-256映射方案

映射邏輯如下表所示：

算法：SHA-256/SHA-512混合調度算法邏輯

Input: //Algorithm Set S[] = { SHA1,SHA2,… SHAn}

//DAG graph

1. Divide S[] into Task Set T={TSHA1,TSHA2… TSHAn}

2. //TSHAn= {T1,T2,Wt}

3. //Set a new task sequence by priority order

4. Tnew[] = Sequence (T[],DAG) //Sequence T[] by DAG

5. Map Tnew[0][0～l0)] to Cluster[0] // l0= TSHA0.tasknum

6. for(i=1; i

7. if(m Cores in Cluster[i-1] is not filled){

8. map Tnew[i][0～(m-1)] to Cluster[i-1];

9. map Tnew[i][m～li] to Cluster[i] //li= TSHAi.tasknum

10. }

11. map Tnew[i][0～li] to Cluster[i]

12. }

4 性能分析

SHA-2算法采用密碼專用指令編寫，算法調度程序代碼基于Visual Studio 2008平臺的C++編寫，處理器采用ASIC設計，使用Verilog HDL語言進行RTL級描述，并在65 nm工藝下進行綜合，處理器參數如表1所示。

表1 處理器參數

經調度后的SHA-2算法程序注入各處理器指令存儲器完成配置，向各處理器數據和密鑰等端口注入數據開始運算。在指令填滿流水線后，消耗的時鐘周期數等于指令條數。

在相同架構下，與SHA-2算法一般實現方式相比，在性能、靈活性上均有一定提升，如表2-表4所示。

表2 SHA-2優化前后指令周期數對比

表3 SHA-256優化前后性能對比

表4 SHA-512優化前后性能對比

注：1)吞吐率為平均吞吐率，單位為Mbps；2) 功耗的單位為mW

經過多核優化后的SHA-2算法，在密碼處理器最高頻率下，可以達到較高的吞吐率。由實驗結果得出，經多核優化后的SHA-2算法的吞吐率與文獻[7-9]接近或持平，與FPGA實現方式[8-10]相比，這種實現方式具有更高靈活性，多核資源可以靈活地適配多個算法，或實現含有SHA-2算法的安全協議。

5 結 語

本文設計了多核密碼處理器架構上的SHA-256與SHA-512高速并行實現方法，并給出了多個SHA-2算法同時處理時在多核上的映射方案。經過調度與映射后的算法能充分利用多核資源，在保持較高靈活性的基礎上使性能得到較大提升。同時也為多核密碼處理器編譯器的設計提供了參考。

[1] Zibin Dai，Wei Li，Xiaohui Yang，et al. The Research and Implementation of Reconfigurable Processor Architecture for Block Cipher Processing[C]//Embedded Software and Systems，ICESS ’08 International Conference on IEEE，2008.

[2] 高飛，李紅燕，張永福.密碼協處理器指令級并行編譯研究[J].計算機應用研究，2010，27(5)，1633-1637.

[3] Gueron S，Johnson S，Walker J.SHA-512/256[C]//2011 Eighth International Conference on Information Technology：New Generations，2011.

[4] 鄧朋法.基于FPGA的可重構SHA安全芯片設計[D].大連：大連海事大學，2011.

[5] 周立陽.多核處理器的任務映射與通信路由算法研究[D].上海：復旦大學，2012.

[6] Bin Liu，Bevans M．Baas，Parallel AES Encryption Engines for Many-Core Processor Arrays[J].IEEE Transactions on Computers，2013，62(3)：538-547.

[7] 李淼，徐金甫，戴紫彬,等.可重構散列函數密碼芯片的設計與實現[J].計算機工程， 2010，36(6)：131-132.

[8] Algredo-Badillo I，Morales-Sandoval M，Feregrino-Uribe C，et al. Throughput and Efficiency Analysis of Unrolled Hardware Architectures for the SHA-512 Hash Algorithm[C]//2012 IEEE Computer Society Annual Symposium on VLSI，2012.

[9] Athanasiou G S，Michail H E，Theodoridis G，et al.Optimising the SHA-512 cryptographic hash function on FPGAs[J].Computers & Digital Techniques，2014,8(2)：70-82.

[10] Miao Li，Jinfu Xu，Xiaohui Yang，et al.Design and Implementation of Reconfigurable Security Hash Algorithms based on FPGA[C]//2009 WASE International Conference on Information Engineering，2009.

RESEARCH ON REALISATION OF SHA-2 ON MULTI-CORE CIPHER PROCESSORS

Qu Siyuan1Dai Zibin2Li Wei1,2*Dai Qiang1

1(PLAInformationEngineeringUniversity,Zhengzhou450002,Henan,China)2(StateKeyLaboratoryofASICandSystem,FudanUniversity,Shanghai201203,China)

In order to find a way suitable for SHA-2 algorithm operating on multi-core cipher processors in high speed and to improve the speed of SHA-2 operating on multi-core cipher processors,we first studied the realisation approach of SHA-256 and SHA-512 algorithms operating on a cipher processor,and studied the structural features and data transmission mode of multi-core cipher processors,as well as analysed the principles of high-speed implementation of SHA-2 on multi-core cipher processors. Then we made the tasks partition on SHA-2 algorithm and put forward the scheduling and mapping algorithms of SHA-2 algorithm on multi-core processors,and implemented the scheduling algorithm by software. Results of simulation verification on ASIC showed that the optimised SHA-2 algorithm gained much higher improvement in throughput of operating on multi-core cipher processors and satisfied the need of performance.

SHA-2 Multi-core Cipher-processor Task scheduling and mapping

2014-08-30。國家自然科學基金項目(61404175)。曲思源，碩士生，主研領域：專用集成電路設計。戴紫彬，教授。李偉， 講師。戴強，博士生。

TP309.7

A

10.3969/j.issn.1000-386x.2016.04.012