基于運(yùn)算部件的可重構(gòu)密碼算法處理架構(gòu)

楊壯林，郭宇波，趙夢(mèng)戀

（浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所，杭州310027）

基于運(yùn)算部件的可重構(gòu)密碼算法處理架構(gòu)

楊壯林，郭宇波，趙夢(mèng)戀

（浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所，杭州310027）

針對(duì)加解密運(yùn)算中微處理器性能低、功耗高，以及專(zhuān)用電路靈活度受限的問(wèn)題，提出基于運(yùn)算部件粗粒度可重構(gòu)的密碼加速單元及其架構(gòu)。給出密碼運(yùn)算的原子運(yùn)算并實(shí)例化為運(yùn)算部件，以原子運(yùn)算部件為重構(gòu)粒子，路由表負(fù)責(zé)配置運(yùn)算部件互連網(wǎng)絡(luò)以組合運(yùn)算，參數(shù)表負(fù)責(zé)配置密碼算法參數(shù)。通過(guò)生成路由表與參數(shù)表配置信息，對(duì)密碼加速單元進(jìn)行粗粒度重構(gòu)。該架構(gòu)在TSMC 0.13μm時(shí)可工作在350 MHz的時(shí)鐘頻率下。實(shí)驗(yàn)結(jié)果表明，提出的架構(gòu)兼具微處理器與專(zhuān)用電路的優(yōu)點(diǎn)，支持多種密碼算法，所需的信息量和資源消耗少，并具有較好的性能面積比。

密碼算法；粗粒度；可重構(gòu)；運(yùn)算部件陣列；路由器陣列；路由表

1 概述

信息技術(shù)的飛速發(fā)展對(duì)信息正確性和私密性的要求越來(lái)越高。為提高加密強(qiáng)度，一般采用兩方面措施：（1）加長(zhǎng)密鑰長(zhǎng)度；（2）增加算法復(fù)雜度。無(wú)論采用哪種措施，都會(huì)導(dǎo)致運(yùn)算量急劇增加，并對(duì)密碼加解密平臺(tái)的運(yùn)算能力提出極高要求。一種運(yùn)算運(yùn)行是通用微處理器，采用軟件方式加解密，具有高度靈活性，但性能與能效表現(xiàn)不佳。另一種傳統(tǒng)的加解密平臺(tái)是專(zhuān)用集成電路（Application Specific Integrated Circuit，ASIC），能充分匹配應(yīng)用特征并做優(yōu)化處理，具有出色的性能與功耗表現(xiàn)，但缺乏靈活性。采用通用微處理器或ASIC平臺(tái)進(jìn)行加解密運(yùn)算在現(xiàn)實(shí)應(yīng)用中存在比較明顯的劣勢(shì)。

可重構(gòu)方法兼具微處理器和ASIC密碼處理靈活與高效的特點(diǎn)。文獻(xiàn)［1］設(shè)計(jì)了4個(gè)功能可重構(gòu)的處理單元組成流水線結(jié)構(gòu)，運(yùn)算并行度高但其只能支持RSA（Rivest-Sham ir-Adleman）與橢圓曲線（Elliptic Curve Cryptographic，ECC）2種密碼算法。文獻(xiàn)［2］提出了3級(jí)重構(gòu)的密碼算法處理結(jié)構(gòu)，靈活度高，但大量配置信息需要從存儲(chǔ)器動(dòng)態(tài)加載，性能較差。文獻(xiàn)［3］提出基于FPGA的細(xì)粒度可重構(gòu)密碼芯片，可支持?jǐn)?shù)據(jù)加密標(biāo)準(zhǔn)（Data Encryption Standard，DES）算法，高級(jí)加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）算法，RSA算法等多種典型密碼算法，通用性高，但面積與功耗都很大。縱觀上述設(shè)計(jì)方法，通常只能支持個(gè)別密碼算法，或配置信息太多，功耗與性能表現(xiàn)不佳，在通用性、性能與功耗上存在缺陷。

本文提出一種通用的粗粒度可重構(gòu)密碼算法處理架構(gòu)，核心思想是提取出密碼算法的原子運(yùn)算并實(shí)例化為運(yùn)算部件，由路由表配置運(yùn)算部件的互聯(lián)網(wǎng)絡(luò)，實(shí)現(xiàn)基于運(yùn)算部件的粗粒度可重構(gòu)。

2 密碼算法分析

2.1 主流密碼算法運(yùn)算分析

密碼算法的基本原理是以固定的算法循環(huán)迭代對(duì)數(shù)據(jù)依次進(jìn)行加解密運(yùn)算。對(duì)主流密碼算法的研究發(fā)現(xiàn)，加解密運(yùn)算可抽象為某些原子運(yùn)算的組合，原子運(yùn)算包括邏輯操作（主要為異或）、移位、加法、乘法、數(shù)據(jù)緩存等。表1歸納了一些主流密碼算法的原子運(yùn)算操作。不僅表1所示的密碼算法，很多其他密碼算法如數(shù)字簽名算法（Digital Signature A lgorithm，DSA）、數(shù)論研究單元算法（Number Theory Research Unit，NTRU）等都可以分解為表1所歸納的原子運(yùn)算。不同密碼算法的數(shù)據(jù)操作寬度雖然各不相同，但都可采用32位的數(shù)據(jù)位寬循環(huán)迭代實(shí)現(xiàn)大位寬運(yùn)算［4-7］。

表1 主流密碼算法的原子運(yùn)算bit

2.2 RSA密碼算法的原子運(yùn)算分解

以RSA密碼算法為例，其加解密都是基于模冪運(yùn)算。常用的模冪算法如二進(jìn)制算法、滑動(dòng)窗口法等都是依次掃描密鑰每個(gè)比特位，根據(jù)掃描結(jié)果進(jìn)行相應(yīng)模乘運(yùn)算。蒙哥馬利模乘算法的一種實(shí)現(xiàn)方式［8］如下所示，將運(yùn)算分解為數(shù)據(jù)位寬為k的原子運(yùn)算。輸入的被乘數(shù)和乘數(shù)為A=as-1as-2…a0和B=bs-1bs-2…b0，結(jié)果為C。

提取出蒙哥馬利算法每一個(gè)步驟所對(duì)應(yīng)的原子運(yùn)算，有加法、乘法、移位和數(shù)據(jù)緩存，RSA密碼算法的加解密運(yùn)算即由這些原子運(yùn)算組合而成。不僅RSA，其他大量密碼算法的運(yùn)算也可分解為表1所示的原子運(yùn)算的組合。

3 可重構(gòu)密碼算法處理架構(gòu)設(shè)計(jì)

3.1 整體架構(gòu)

前文歸納了大量密碼算法共有的原子運(yùn)算，本文在實(shí)例化這些原子運(yùn)算為運(yùn)算部件的基礎(chǔ)上提出基于運(yùn)算部件粗粒度可重構(gòu)的密碼算法處理架構(gòu)，輔以路由表與參數(shù)表重構(gòu)運(yùn)算功能，支持各種密碼算法。架構(gòu)主要包含接口模塊、控制模塊、運(yùn)算部件陣列、路由器陣列、存儲(chǔ)器以及可自定義的路由表和參數(shù)表，如圖1所示。

圖1 可重構(gòu)的密碼算法處理架構(gòu)

接口負(fù)責(zé)與外部控制信息和數(shù)據(jù)的通信。存儲(chǔ)器由4個(gè)部分組成，存儲(chǔ)器0與1用于緩存運(yùn)算部件計(jì)算所需的源數(shù)據(jù)，存儲(chǔ)器2用于緩存運(yùn)算結(jié)果，存儲(chǔ)器3用于緩存與外部通信的密碼算法參數(shù)。參數(shù)表定義了屬性參數(shù)，如密鑰、二元域控制位、加解密數(shù)據(jù)的長(zhǎng)度、運(yùn)算部件處理的數(shù)據(jù)位寬等。控制模塊與參數(shù)表配合，負(fù)責(zé)整個(gè)架構(gòu)的全局控制管理，如讀取存放存儲(chǔ)器數(shù)據(jù)、路由表項(xiàng)、參數(shù)、啟動(dòng)停止運(yùn)算等。

運(yùn)算部件陣列、路由器陣列以及路由表是架構(gòu)的核心模塊，這3個(gè)模塊配合完成架構(gòu)的重構(gòu)。運(yùn)算部件陣列包括加法器、乘法器、左移位器、右移位器、邏輯操作共5個(gè)原子運(yùn)算單元以及數(shù)據(jù)緩存器。原子運(yùn)算單元獨(dú)立完成相應(yīng)的運(yùn)算操作。數(shù)據(jù)緩存器內(nèi)部有5個(gè)獨(dú)立的寄存器組，與5個(gè)運(yùn)算單元一一對(duì)應(yīng)，可通過(guò)配置寄存控制位與保持控制位對(duì)運(yùn)算單元的結(jié)果進(jìn)行寄存、保持或直接輸出，如圖2所示。寄存控制位用于決定運(yùn)算結(jié)果是否寄存一級(jí)再輸出。保持控制位用于決定是否保持原先的運(yùn)算結(jié)果。數(shù)據(jù)緩存器配合寄存控制位可以靈活調(diào)整數(shù)據(jù)通路的邏輯路徑延時(shí)，使電路能夠滿足多種頻率需求，從而達(dá)到較高的工作頻率。

圖2 數(shù)據(jù)緩存器結(jié)構(gòu)

運(yùn)算結(jié)果經(jīng)由數(shù)據(jù)緩存器處理后輸入到路由器陣列。路由器陣列是運(yùn)算部件以及存儲(chǔ)器之間的互連網(wǎng)絡(luò)。路由表由多個(gè)表項(xiàng)組成，是運(yùn)算部件之間互聯(lián)關(guān)系的映射，每個(gè)表項(xiàng)由路由器0～10的路由信息、寄存控制位與保持控制位組成，如圖3所示。路由0～10每一項(xiàng)為3位，分別對(duì)應(yīng)原子運(yùn)算單元及存儲(chǔ)器輸入端數(shù)據(jù)的路由信息，其對(duì)應(yīng)連接關(guān)系可參考圖1。寄存控制位與保持控制位均有5位，分別對(duì)應(yīng)5個(gè)原子運(yùn)算部件。通過(guò)配置數(shù)據(jù)源的路由編碼，定義數(shù)據(jù)通路，為運(yùn)算部件和存儲(chǔ)器3選擇合適的數(shù)據(jù)來(lái)源。

圖3 路由表項(xiàng)信息

每一個(gè)路由表項(xiàng)定義了一種數(shù)據(jù)通路，是一種運(yùn)算組合的映射。不同密碼算法或同一密碼算法的不同運(yùn)算階段往往具有不同的運(yùn)算內(nèi)容，運(yùn)算過(guò)程中通過(guò)不斷讀取并切換路由表項(xiàng)重構(gòu)運(yùn)算部件的互連關(guān)系，動(dòng)態(tài)重構(gòu)數(shù)據(jù)通路，完成動(dòng)態(tài)變化的運(yùn)算內(nèi)容。

本設(shè)計(jì)采用以運(yùn)算部件為重構(gòu)粒子的粗粒度重構(gòu)方式，只需對(duì)路由表以及參數(shù)表進(jìn)行配置，即可完成對(duì)不同密碼算法的支持，重構(gòu)邏輯簡(jiǎn)單，重構(gòu)信息較少，有利于用戶(hù)實(shí)現(xiàn)。

3.2 RSA在架構(gòu)中的映射實(shí)現(xiàn)

以典型密碼算法RSA為例，闡述其在該架構(gòu)的映射。首先初始化參數(shù)表，即初始化密鑰，將二元域的控制位置零，設(shè)置好數(shù)據(jù)長(zhǎng)度，運(yùn)算位寬設(shè)為32位等。根據(jù)算法生成對(duì)應(yīng)的路由表信息是一個(gè)關(guān)鍵步驟。加解密運(yùn)算由多個(gè)原子運(yùn)算組合完成，需將運(yùn)算組合映射到路由表項(xiàng)。以t［j］+a［j］×b［j］為例，其先進(jìn)行乘法再進(jìn)行加法運(yùn)算。乘法器輸入數(shù)據(jù)a［j］與b［j］來(lái)自存儲(chǔ)器0與1，結(jié)合圖3的數(shù)據(jù)源編碼，則路由器2與3的配置項(xiàng)為101與110。加法器輸入數(shù)據(jù)來(lái)源分別為乘法器與存儲(chǔ)器2，則路由器0與1的配置項(xiàng)為001和111。最終的運(yùn)算結(jié)果來(lái)自于加法器并被存放到存儲(chǔ)器2中，則路由器10配置項(xiàng)為000。在本次運(yùn)算過(guò)程中沒(méi)有用到的運(yùn)算部件，輸入源的路由配置項(xiàng)選擇自身。如本次運(yùn)算中沒(méi)有用到的左移器，其輸入端的路由配置項(xiàng)為010。路由表項(xiàng)的寄存控制位為10111，保持控制位為00111，即加法結(jié)果寄存一級(jí)再輸出，乘法結(jié)果不寄存直接輸出給加法器，沒(méi)有用到的運(yùn)算部件對(duì)應(yīng)的保持控制位和寄存控制位為1，以保持原先結(jié)果。t［j］+a［j］×b［j］到路由表項(xiàng)的映射結(jié)果如表2所示。

表2 t［j］+a［j］×b［j］到路由表項(xiàng)的映射

按照該方式可完成蒙哥馬利算法所有運(yùn)算步驟到路由表的映射，即完成RSA密碼算法到路由表的映射。對(duì)于其他密碼算法，類(lèi)似的只需要匹配好目標(biāo)算法，提取出原子運(yùn)算及組合，并生成對(duì)應(yīng)的參數(shù)表與路由表信息，即可粗粒度重構(gòu)處理架構(gòu)的功能，從而支持各種密碼算法運(yùn)算。

4 實(shí)驗(yàn)結(jié)果與分析

本文提出的處理架構(gòu)采用的乘法器需2個(gè)時(shí)鐘周期完成運(yùn)算，并配置路由表使數(shù)據(jù)都先寄存一次再輸出。采用Synopsys公司的Design Com p lier工具，TSMC 130 nm RVT工藝庫(kù)對(duì)電路進(jìn)行綜合，延時(shí)為2.8 ns，路由器輸入端到乘法器中間結(jié)果的邏輯路徑為關(guān)鍵路徑，電路最高工作頻率為350 MHz。

以典型密碼算法RSA，ECC與RC6為例，設(shè)計(jì)實(shí)驗(yàn)對(duì)提出的處理架構(gòu)進(jìn)行功能驗(yàn)證，并與處理器和專(zhuān)用電路平臺(tái)作對(duì)比，對(duì)結(jié)果進(jìn)行分析評(píng)估。分別采用CK810處理器與本文提出的處理架構(gòu)，對(duì)相同的密鑰與明文數(shù)據(jù)進(jìn)行密碼運(yùn)算，對(duì)比實(shí)驗(yàn)結(jié)果如表3所示。

表3 本文架構(gòu)與CK 810的RSA性能對(duì)比

盡管CK810是高頻率、指令雙發(fā)射并亂序執(zhí)行的高性能處理器［9］，但其軟件加解密方式在性能與功耗上表現(xiàn)都較差。本文的架構(gòu)針對(duì)RSA進(jìn)行粗粒度重構(gòu)，能更好地匹配算法特點(diǎn)，性能更高且功耗更低。

表4對(duì)比了本文架構(gòu)與其他專(zhuān)用電路進(jìn)行RSA密碼運(yùn)算的性能。文獻(xiàn)［10］采用大位寬乘法器與加法器以提高運(yùn)算效率，但工作頻率低，資源消耗大，性能僅為本文架構(gòu)的45.5%。文獻(xiàn)［11］采用總共34個(gè)加法器在高時(shí)鐘頻率條件下流水完成運(yùn)算，性能比本文架構(gòu)高7%，但資源消耗遠(yuǎn)大于本文架構(gòu)。此外，文獻(xiàn)［10-11］均只能支持RSA密碼算法，靈活性較差。

表4 RSA算法性能對(duì)比

表5對(duì)比了本文與其他電路的ECC密碼運(yùn)算性能。文獻(xiàn)［12］設(shè)計(jì)了4個(gè)運(yùn)算單元并行計(jì)算，性能比本文架構(gòu)略?xún)?yōu)，但運(yùn)算資源是本文架構(gòu)的近4倍。文獻(xiàn)［13］設(shè)計(jì)了基于FPGA細(xì)粒度重構(gòu)的ECC密碼加速系統(tǒng)，不僅資源消耗大，而且性能較低。

表6對(duì)比了本文架構(gòu)與文獻(xiàn)［4］的RC6密碼運(yùn)算性能。文獻(xiàn)［4］的性能比本文架構(gòu)高21%，但運(yùn)算資源是本文架構(gòu)的4倍，運(yùn)算部件采用部分串聯(lián)連接，路徑延時(shí)較大且不能很好匹配算法特點(diǎn)，運(yùn)算資源得不到充分利用。

表6 RC6算法性能對(duì)比

受限于篇幅，本文設(shè)計(jì)所支持的其他密碼算法對(duì)比實(shí)驗(yàn)結(jié)果不再列出。已有的對(duì)比實(shí)驗(yàn)結(jié)果表明，相比軟件方式加解密，本文提出的密碼處理架構(gòu)性能更高，功耗更低。相比專(zhuān)用電路或其他可重構(gòu)電路，本文的設(shè)計(jì)重構(gòu)邏輯簡(jiǎn)單，重構(gòu)所需信息量少，資源消耗少，性能良好，具有更好的性能面積比。

5 結(jié)束語(yǔ)

本文提出一個(gè)密碼算法處理架構(gòu)，設(shè)計(jì)運(yùn)算部件陣列、路由器陣列以及路由表與參數(shù)表等關(guān)鍵模塊，可對(duì)處理架構(gòu)進(jìn)行粗粒度重構(gòu)，從而靈活支持各種密碼算法，重構(gòu)信息少、重構(gòu)便捷。實(shí)驗(yàn)結(jié)果表明，與微處理器、專(zhuān)用電路或其他可重構(gòu)電路相比，該架構(gòu)在保證靈活性的基礎(chǔ)上，功耗較低，性能優(yōu)良，具有良好的性能面積比，在多樣的密碼加解密應(yīng)用中有充分的競(jìng)爭(zhēng)力。為進(jìn)一步優(yōu)化設(shè)計(jì)方案，后續(xù)工作將增加原子運(yùn)算單元，提高通用性與并行性；研究原子運(yùn)算單元以及運(yùn)算部件陣列之間的路由網(wǎng)絡(luò)，更好地匹配密碼算法的特點(diǎn)，提高加解密運(yùn)算性能。

［1］ 黎 明，吳 丹，戴 葵，等.高性能可擴(kuò)展公鑰密碼協(xié)處理器研究與設(shè)計(jì)［J］.電子學(xué)報(bào)，2011，39（3）：665-670.

［2］ 王玉良.面向密碼算法的粗粒度可重構(gòu)結(jié)構(gòu)研究與設(shè)計(jì)［D］.鄭州：解放軍信息工程大學(xué)，2010.

［3］ 李可長(zhǎng).基于FPGA可重構(gòu)快速密碼芯片設(shè)計(jì)［J］.計(jì)算機(jī)測(cè)量與控制，2011，19（7）：1665-1667.

［4］ 楊曉輝.面向分組密碼處理的可重構(gòu)設(shè)計(jì)技術(shù)研究［D］.鄭州：解放軍信息工程大學(xué)，2007.

［5］ Elbirt A J.Reconfigurable Computing for Symmetric-key Algorithms［D］.Worcester，USA：Worcester Polytechnic Institute，2002.

［6］ Ravikumar K，Udhayakumar A.A Detailed Study of Elliptic Curve Cryptography Algorithm and Its Performance［J］. International Journal of Engineering Science&Research Technology，2013，2（10）：2960-2964.

［7］ Bluhm M，Gueron S.Fast Software Implementation of Binary Elliptic Curve Cryptography［EB/OL］.（2014-10-15）.http：//eprint.iacr.org/2013/741.pdf.

［8］ Ko??K，Acar T，Kaliski B S.Analyzing and Comparing Montgomery Multiplication Algorithms［J］.IEEE Micro，1996，16（3）：26-33.

［9］ C-Sky Microsystems.Co.，Ltd..C-Sky CK810 User's Manual［EB/OL］.（2014-10-20）.http：//www.c-sky.com.

［10］ Moon S.Design of a Scalable RSA Cryptoprocessor Em bedded with an Efficient MAC Unit［C］// Proceedings of the 2nd International Conference on Future Generation Communication and Networking. Washington D.C.，USA：IEEE Press，2008：74-77.

［11］ Chen Yunlu，Tseng Chih-Yeh，Chang Hsie-Chia.Design and Implementation of Reconfigurable RSA Cryptosystem［C］//Proceedings of International Symposium on VLSI Design，Automation and Test.Washington D.C.，USA：IEEE Press，2007：1-4.

［12］ Zhao Xuem i，Wang Zhiying，Yue Hong，et al.TTA-EC：A W hole Algorithm Processor for ECC Based on Transport Triggered Architecture［J］.Chinese Journal of Computings，2007，30（2）：225-233.

［13］ Liu Sining，F(xiàn)rancis B，Brian K，et al.Elliptic Curves Cryptosystem Implementation Based on a Look-up Table Sharing Scheme［C］//Proceedings of International Symposium on Circuits and System s.Washington D.C.，USA：IEEE Press，2006：2921-2924.

編輯顧逸斐

Reconfigurable Cryptographic Algorithm Processing Architecture Based on Operating Element

YANG Zhuanglin，GUO Yubo，ZHAO Menglian
（Institute of VLSI Design，Zhejiang University，Hangzhou 310027，China）

Facing with the poor performance and high power consumption of microprocessor and inflexibility of ASIC in encryption and decryption computation，coarse-grain reconfigurable cryptographic algorithm processing architecture based on operating elements is proposed.This paper extracts atomic operations and instantiates them as processing elements.Operating elements are taken as reconfigurable gains，coupled with routing table and parameter table.Routing table is in charge of configuring interconnection network of operating elements while parameter table is responsible for configuring cryptographic algorithm parameters.By generating routing table and parameter table information according to different cryptographic algorithms，cryptographic accelerator is coarse-grain reconfigured to support various cryptographic algorithms.The circuit reaches clock frequency of 350 MHz using TSMC 0.13μm cell library.Experimental results show that the architecture has both the advantages of microprocessor and ASIC and it flexibly supports various cryptographic algorithms.The required amount of information and resource consumption is less，and has better performance area ratio.【Key words】cryptographic algorithm；coarse-grain；reconfigurable；operating element array；router array；routing table

10.3969/j.issn.1000-3428.2015.11.016

楊壯林，郭宇波，趙夢(mèng)戀.基于運(yùn)算部件的可重構(gòu)密碼算法處理架構(gòu)［J］.計(jì)算機(jī)工程，2015，41（11）：89-93.

英文引用格式：Yang Zhuanglin，Guo Yubo，Zhao Menglian.Reconfigurable Cryptographic Algorithm Processing Architecture Based on Operating Element［J］.Computing Engineering，2015，41（11）：89-93.

1000-3428（2015）11-0089-05

A

TP301.6

楊壯林（1988-），男，碩士研究生，主研方向：計(jì)算機(jī)體系結(jié)構(gòu)；郭宇波，工程師、碩士；趙夢(mèng)戀，副教授。

2014-11-21

2014-12-19 E-m ail：edians@163.com