SHA-2算法在多核密碼處理器上的實現(xiàn)研究

曲思源 戴紫彬 李 偉，* 戴 強(qiáng)

SHA-2算法在多核密碼處理器上的實現(xiàn)研究

曲思源1戴紫彬2李 偉1，2*戴 強(qiáng)1

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

2(復(fù)旦大學(xué)專用集成電路與系統(tǒng)國家實驗室 上海 201203)

為了找出一種適合多核密碼處理器的SHA-2算法高速實現(xiàn)方式，提高SHA-2算法在多核密碼處理器上的執(zhí)行速度。首先研究SHA-256、SHA-512算法在密碼處理器上的實現(xiàn)方式，并研究多核密碼處理器的結(jié)構(gòu)特點(diǎn)與數(shù)據(jù)傳輸方式，分析SHA-2算法在多核上的高速實現(xiàn)原理。然后對SHA-2算法進(jìn)行任務(wù)劃分，提出SHA-2在多核密碼處理器上的調(diào)度與映射算法并使用軟件實現(xiàn)調(diào)度算法。在ASIC上的仿真驗證結(jié)果表明，經(jīng)優(yōu)化后的SHA-2算法在多核上并行執(zhí)行吞吐率有了較大提升，滿足性能上的需求。

SHA-2 多核 密碼處理器 任務(wù)調(diào)度與映射

0 引 言

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

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

為了進(jìn)一步提升密碼運(yùn)算性能，設(shè)計了多核密碼處理器，該架構(gòu)采用基于Mesh結(jié)構(gòu)的分簇式設(shè)計，將多個同構(gòu)密碼處理器、控制器以及共享存儲區(qū)域集成進(jìn)一個簇，并可以通過中央調(diào)度器實現(xiàn)簇間通信。

在多核運(yùn)算中，任務(wù)分配與調(diào)度是提高處理效率的重要環(huán)節(jié)。本文主要探討如何根據(jù)密碼處理器上SHA-2算法的實現(xiàn)特點(diǎn)對其進(jìn)行任務(wù)劃分，并設(shè)計劃分后的SHA-2算法在多核架構(gòu)下的調(diào)度與映射算法，以充分發(fā)揮多核架構(gòu)的資源優(yōu)勢，進(jìn)一步提升SHA-2在密碼處理器上的處理速度。

1 SHA-2算法高速實現(xiàn)研究

1.1 SHA-2算法介紹及其單核實現(xiàn)

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

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

SHA-512算法與SHA-256算法結(jié)構(gòu)相同，不同之處是SHA-512算法有80步迭代運(yùn)算，且緩存對應(yīng)的處理位寬為64位[3，4]。

以SHA-256為例，算法使用的基本函數(shù)[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由三值邏輯函數(shù)指令實現(xiàn)，Σ1、Σ2、R1、R2由帶移位的三值邏輯函數(shù)指令實現(xiàn)，T1的實現(xiàn)使用了模加指令。此外，算法還用到了異或指令、循環(huán)移位指令、邏輯移位指令，這些指令屬于密碼處理器專用指令集。

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

圖1 單處理器SHA-256實現(xiàn)流程

1.2 SHA-2高速實現(xiàn)原理

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

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

利用SHA-2算法結(jié)構(gòu)的這些特點(diǎn)可以將SHA-2算法按任務(wù)或數(shù)據(jù)拆分，在多核密碼處理器上高速實現(xiàn)SHA-2算法。

1.3 SHA-2多核處理結(jié)構(gòu)

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

圖2 多核密碼處理器架構(gòu)和通信方式

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

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

2.1 基于任務(wù)的劃分方式

使以SHA-256為例，在數(shù)據(jù)擴(kuò)展運(yùn)算中，Wt生成后保存在寄存器中，循環(huán)48次得所有Wt。Wt與Wt-1沒有數(shù)據(jù)相關(guān)性，二者可劃分為并行任務(wù)。Wt的生成依賴于Wt-2，因此生成Wt-2必須作為生成Wt的前驅(qū)任務(wù)。

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

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

圖3 SHA-256任務(wù)劃分與DAG圖

2.2 任務(wù)與數(shù)據(jù)混合劃分

在SHA-512算法中，輸出雜湊值長度為512比特，初始值為8個64比特的字，在輪運(yùn)算過程中，數(shù)據(jù)長度為64比特。在專用密碼處理器中，通用寄存器設(shè)定的處理位寬為32比特，因此大位寬運(yùn)算需要高位低位分別先后執(zhí)行，SHA-512在密碼處理器上實現(xiàn)時指令存儲器使用率與緩存哈希值更新一次的運(yùn)算時間均是SHA-256的2倍以上，資源占用大且運(yùn)算時間較長?？梢圆捎枚嗪朔謩e同時處理大位寬運(yùn)算的高低位數(shù)據(jù)的方法提高運(yùn)算的并行度，從而提高算法執(zhí)行速度。

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

圖4 高低數(shù)據(jù)位任務(wù)通信流程

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

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

圖5 SHA-512拆分后任務(wù)對示意圖

3 任務(wù)調(diào)度與映射

在完成了算法的任務(wù)劃分后，按以下規(guī)則在多處理器系統(tǒng)上進(jìn)行任務(wù)映射。

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

為使性能達(dá)到要求，對于SHA-256/512，定義單核執(zhí)行一個數(shù)據(jù)塊所有循環(huán)T1任務(wù)的時間為單位時間tu：

tu=(tT1+te+ta)×64

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

圖6 SHA-256映射方案

圖7 SHA-512映射方案

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

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

Tnum=2n+4m

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

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

Pnum=Tnum+Wnum

Cnum=Pnum/4

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

圖8 2個SHA-512映射方案

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

圖10 4個SHA-256映射方案

映射邏輯如下表所示：

算法：SHA-256/SHA-512混合調(diào)度算法邏輯

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算法采用密碼專用指令編寫，算法調(diào)度程序代碼基于Visual Studio 2008平臺的C++編寫，處理器采用ASIC設(shè)計，使用Verilog HDL語言進(jìn)行RTL級描述，并在65 nm工藝下進(jìn)行綜合，處理器參數(shù)如表1所示。

表1 處理器參數(shù)

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

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

表2 SHA-2優(yōu)化前后指令周期數(shù)對比

表3 SHA-256優(yōu)化前后性能對比

表4 SHA-512優(yōu)化前后性能對比

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

經(jīng)過多核優(yōu)化后的SHA-2算法，在密碼處理器最高頻率下，可以達(dá)到較高的吞吐率。由實驗結(jié)果得出，經(jīng)多核優(yōu)化后的SHA-2算法的吞吐率與文獻(xiàn)[7-9]接近或持平，與FPGA實現(xiàn)方式[8-10]相比，這種實現(xiàn)方式具有更高靈活性，多核資源可以靈活地適配多個算法，或?qū)崿F(xiàn)含有SHA-2算法的安全協(xié)議。

5 結(jié) 語

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

[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] 高飛，李紅燕，張永福.密碼協(xié)處理器指令級并行編譯研究[J].計算機(jī)應(yīng)用研究，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的可重構(gòu)SHA安全芯片設(shè)計[D].大連：大連海事大學(xué)，2011.

[5] 周立陽.多核處理器的任務(wù)映射與通信路由算法研究[D].上海：復(fù)旦大學(xué)，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] 李淼，徐金甫，戴紫彬,等.可重構(gòu)散列函數(shù)密碼芯片的設(shè)計與實現(xiàn)[J].計算機(jī)工程， 2010，36(6)：131-132.

[8] Algredo-Badillo I，Morales-Sandoval M，F(xiàn)eregrino-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。國家自然科學(xué)基金項目(61404175)。曲思源，碩士生，主研領(lǐng)域：專用集成電路設(shè)計。戴紫彬，教授。李偉， 講師。戴強(qiáng)，博士生。

TP309.7

A

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