王騰飛，張海峰，許 森

1.上海交通大學(xué) 電子信息與電氣工程學(xué)院，上海 200240

2.北京智芯微電子科技有限公司，北京 100192

3.觀源（上海）科技有限公司，上海 200241

隨著信息技術(shù)的發(fā)展和對信息安全需求的增長，公鑰密碼的使用變得更加廣泛。在公鑰密碼體制中，與RSA算法相比，橢圓曲線密碼（ECC）[1]算法能夠使用較短的密鑰而達(dá)到較高的安全性，因而得到了越來越多的關(guān)注。2012年，中國國家密碼管理局公布了基于ECC的公鑰商用密碼標(biāo)準(zhǔn)，簡稱SM2[2]，并且在2017年被國際上確立為ISO標(biāo)準(zhǔn)，正在得到越來越廣泛的應(yīng)用。但由于其中涉及到的數(shù)學(xué)運(yùn)算較為復(fù)雜，在具體應(yīng)用中還存在計(jì)算效率不高的問題，因此，對SM2軟硬件快速實(shí)現(xiàn)技術(shù)的研究成為一項(xiàng)重要課題。

SM2標(biāo)準(zhǔn)屬于橢圓曲線密碼體系，它與基于ECC的其他國際標(biāo)準(zhǔn)，如ECDSA之間在數(shù)學(xué)基礎(chǔ)、算法結(jié)構(gòu)和實(shí)現(xiàn)方式等方面具有相同點(diǎn)，橢圓曲線標(biāo)量乘算法是實(shí)現(xiàn)這一類標(biāo)準(zhǔn)的關(guān)鍵部分。針對ECC的實(shí)現(xiàn)通常有兩種途徑：一是軟件實(shí)現(xiàn)，即在通用處理器（general purpose processor，GPP）上通過軟件編程方式實(shí)現(xiàn)相應(yīng)算法；二是硬件實(shí)現(xiàn)，硬件平臺(tái)主要包括專用集成電路（application specific integrated circuit，ASIC）和現(xiàn)場可編程門陣列（field programmable gate array，F(xiàn)PGA）兩種。前者的優(yōu)點(diǎn)在于靈活性高，可以很方便地進(jìn)行各種參數(shù)的配置，缺點(diǎn)是GPP缺少對大數(shù)運(yùn)算的支持，計(jì)算效率低；后者的優(yōu)點(diǎn)在于計(jì)算速度快，缺點(diǎn)是靈活性差，尤其是基于ASIC的實(shí)現(xiàn)，指定參數(shù)后就不能隨意修改，而FPGA因?yàn)榫哂锌删幊烫匦裕陟`活性上比ASIC要強(qiáng)一些。

由于FPGA在計(jì)算效率和靈活性上的優(yōu)勢，目前國內(nèi)外有許多對ECC（包括SM2）實(shí)現(xiàn)的研究選擇FPGA作為實(shí)驗(yàn)平臺(tái)。Loi等人[3]提出的橢圓曲線密碼處理器能夠支持美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST）推薦的五種素域橢圓曲線，利用Xilinx Virtex-5 FPGA上的DSP48E達(dá)到了較高的性能。Zhang等人[4]針對SM2推薦的橢圓曲線在Altera StratixII FPGA上實(shí)現(xiàn)了高性能的標(biāo)量乘。但是上述文獻(xiàn)所采用的實(shí)現(xiàn)方法都是利用狀態(tài)機(jī)來控制算法流程，這樣會(huì)導(dǎo)致控制邏輯占用大量硬件資源，同時(shí)也不利于應(yīng)用流水線技術(shù)進(jìn)行加速。除此之外，還有一類實(shí)現(xiàn)方法是設(shè)計(jì)專用指令集處理器（application specific instruction-set processor，ASIP）[5]，即可以針對ECC算法的計(jì)算特點(diǎn)設(shè)計(jì)專用的指令，使處理器能夠以執(zhí)行指令的形式高效靈活地實(shí)現(xiàn)算法。張軍[6]提出面向二元域和素?cái)?shù)域上ECC運(yùn)算的專用指令集，設(shè)計(jì)了一種可以實(shí)現(xiàn)多種ECC算法的專用指令向量協(xié)處理器。夏輝等人[7]提出了一套通用的專用指令處理器的設(shè)計(jì)驗(yàn)證方案，并將該方案應(yīng)用于ECC，從而大幅提升其在硬件資源受限的嵌入式環(huán)境中的執(zhí)行效率。但目前還沒有專門針對SM2標(biāo)準(zhǔn)的專用指令協(xié)處理器的研究。

本文借鑒利用ASIP高效實(shí)現(xiàn)ECC算法的設(shè)計(jì)思想，在詳細(xì)了解SM2算法特點(diǎn)的基礎(chǔ)上，提出一種適用于實(shí)現(xiàn)SM2算法的專用指令協(xié)處理器。所提出的SM2專用指令協(xié)處理器能夠結(jié)合軟硬件實(shí)現(xiàn)各自具有的優(yōu)勢，以FPGA為平臺(tái)，高效利用其計(jì)算資源，同時(shí)考慮抵御側(cè)信道攻擊的安全性，實(shí)現(xiàn)了從底層硬件單元到上層指令序列的整體優(yōu)化，具有面積小、速度快、靈活性高的特點(diǎn)。

1 背景概述

SM2底層的基本運(yùn)算是定義在有限域上的，具體分為素域和二元擴(kuò)域兩種，本文主要討論基于素域的實(shí)現(xiàn)。

1.1 素域運(yùn)算

階為素?cái)?shù)的有限域稱為素域，素域上的運(yùn)算可以通過在整數(shù)的基本運(yùn)算后再加一步對素?cái)?shù)階P的約減運(yùn)算完成，以使結(jié)果同樣落在素域下面。簡單來說，素域運(yùn)算包括模加、模減、模乘和模逆運(yùn)算，而模逆可以由一系列的加法和移位運(yùn)算實(shí)現(xiàn)。

SM2算法在實(shí)現(xiàn)的過程中，會(huì)不斷調(diào)用底層的素域運(yùn)算，其中模加減運(yùn)算比較簡單，不會(huì)占用太多時(shí)間，而模乘運(yùn)算調(diào)用次數(shù)多，計(jì)算時(shí)間長，是提高整體性能的關(guān)鍵運(yùn)算。為了提高計(jì)算效率，本文采用Montgomery模乘方法[8]來實(shí)現(xiàn)素域上的模乘運(yùn)算。Montgomery模乘方法避免了使用耗時(shí)的除法運(yùn)算來進(jìn)行約減，取而代之的是簡單的移位運(yùn)算，其計(jì)算形式如公式（1）所示：

其中，R=2k,k為P的位數(shù)，其核心思想是將對P的取模運(yùn)算轉(zhuǎn)化為對R的取模和除法運(yùn)算，這樣在執(zhí)行的過程中就只需要簡單的截取和移位操作，非常適合硬件實(shí)現(xiàn)。在SM2的計(jì)算過程中，可以首先將原始數(shù)據(jù)與R2做Montgomery模乘運(yùn)算，使其轉(zhuǎn)換為“Montgomery形式”，然后在這種形式下就可以用Montgomery模乘代替普通模乘，模加減仍為普通模加減，得到的中間結(jié)果保持“Montgomery形式”不變，直到最后一步通過將結(jié)果與1做Montgomery模乘運(yùn)算，使其轉(zhuǎn)換至普通形式。這樣只需增加開始和結(jié)束時(shí)的兩步轉(zhuǎn)換過程，而節(jié)省了中間大量模乘運(yùn)算的耗時(shí)，能夠起到良好的加速效果。

相比于模乘運(yùn)算，素域上的模逆運(yùn)算更為復(fù)雜，對素域上的元素X求模逆，即找到素域上的元素Z，使得Z與X的乘積模P的結(jié)果為1，如公式（2）所示：

二進(jìn)制擴(kuò)展歐幾里德算法[9]可以將模逆運(yùn)算轉(zhuǎn)換為一系列的加減和移位運(yùn)算，因此在設(shè)計(jì)模逆的硬件計(jì)算單元時(shí)，可以通過控制邏輯調(diào)用模加減和移位單元執(zhí)行運(yùn)算，從而節(jié)省硬件資源。另外，將橢圓曲線上的點(diǎn)由仿射坐標(biāo)轉(zhuǎn)換為Jacobian坐標(biāo)可以減少模逆運(yùn)算的調(diào)用次數(shù)，從而提高計(jì)算速度。

1.2 橢圓曲線密碼算法

橢圓曲線密碼算法的安全性是基于橢圓曲線上離散對數(shù)問題[10]，該類型算法是目前公認(rèn)的單比特安全度最高的公鑰密碼算法。ECC具備密鑰長度短、計(jì)算資源需求少等優(yōu)勢，尤其適用于資源受限設(shè)備上的應(yīng)用，如智能卡等。

橢圓曲線E是一個(gè)具有兩變量的三次方程，該方程一般定義在某個(gè)數(shù)域K上，在本文中K為素域，方程的定義如公式（3）所示：

其中a,b,c,d,e∈K，且其判別式Δ≠0，判別式的定義為：

則，橢圓曲線E上所有點(diǎn)的集合為：

這里O為無窮遠(yuǎn)點(diǎn)。

SM2標(biāo)準(zhǔn)給出的定義在素域上的橢圓曲線方程具有如下形式：

設(shè)橢圓曲線E上不同的兩點(diǎn)P=(x1,y1)和Q=(x2,y2)，兩點(diǎn)相加稱為點(diǎn)加運(yùn)算，點(diǎn)P和Q的點(diǎn)加運(yùn)算結(jié)果為P+Q=(x3,y3)，其計(jì)算公式為：

相同的兩點(diǎn)相加稱為倍點(diǎn)運(yùn)算，點(diǎn)P的倍點(diǎn)運(yùn)算結(jié)果為2P=(x4,y4)，其計(jì)算公式為：

同一個(gè)點(diǎn)的多次重復(fù)相加稱為該點(diǎn)的多倍點(diǎn)運(yùn)算，如P的d倍點(diǎn)：

橢圓密碼算法的安全性來源于橢圓曲線上離散對數(shù)的計(jì)算復(fù)雜性，即Q=[d]P。其中，P和Q為橢圓曲線上的點(diǎn)，而d為標(biāo)量，由P和d計(jì)算得到Q是易于實(shí)現(xiàn)的，而由P和Q得到d，在計(jì)算上不可行。與RSA算法的模冪運(yùn)算類似，[d]P是橢圓曲線密碼算法的核心，也稱之為標(biāo)量乘運(yùn)算。為了抵御簡單功耗分析（SPA）攻擊，本文采用Montgomery Powering Ladder（MPL）算法[11]，如算法1所示。

算法1MPL標(biāo)量乘算法

輸入：整數(shù)d和點(diǎn)P,d的比特長度l

1.3 SM2算法

SM2算法呈現(xiàn)層次性特點(diǎn)，自上而下可以分為四層，如圖1所示。在協(xié)議層包括數(shù)字簽名算法、密鑰交換協(xié)議和公鑰加密算法三部分，向下調(diào)用橢圓曲線點(diǎn)乘運(yùn)算和素域GF(n)上的模運(yùn)算。點(diǎn)乘運(yùn)算層實(shí)現(xiàn)公式（9）所示的橢圓曲線標(biāo)量乘運(yùn)算，由算法1可知該運(yùn)算的實(shí)現(xiàn)過程包括一系列的點(diǎn)加和倍點(diǎn)運(yùn)算，在群運(yùn)算層完成。而點(diǎn)加和倍點(diǎn)的計(jì)算過程如公式（7）和（8）所示，通常為了減少計(jì)算量，會(huì)將其轉(zhuǎn)換至Jacobian坐標(biāo)下進(jìn)行，但都需要調(diào)用素域GF(p)上的模運(yùn)算。有限域?qū)訉?shí)現(xiàn)大數(shù)的模加、模減、模乘和模逆運(yùn)算，本文只考慮有限域?yàn)樗赜虻那闆r，包括協(xié)議層直接調(diào)用的素域GF(n)和群運(yùn)算層調(diào)用的素域GF(p)，運(yùn)算規(guī)則如1.1節(jié)所述。除此之外，協(xié)議層還需調(diào)用一些輔助函數(shù)，如密碼雜湊函數(shù)、密鑰派生函數(shù)和隨機(jī)數(shù)發(fā)生器，這類函數(shù)可以通過軟硬件方式單獨(dú)完成，與本文所設(shè)計(jì)的協(xié)處理器結(jié)合即可實(shí)現(xiàn)完整的協(xié)議。

圖1 SM2算法的層次結(jié)構(gòu)Fig.1 Layer of SM2 algorithm

與其他基于ECC的國際密碼體制相比，SM2采用了獨(dú)特的素?cái)?shù)域，256位橢圓曲線，GM/T 0003規(guī)定了SM2算法的曲線參數(shù)[2]。依據(jù)標(biāo)準(zhǔn)所選取的參數(shù)，圖1中的有限域?qū)铀杼幚淼牟僮鲾?shù)據(jù)均為256位無符號(hào)整數(shù)，因此在本文所設(shè)計(jì)的SM2協(xié)處理器中，使用256位無符號(hào)整數(shù)計(jì)算單元執(zhí)行有限域?qū)拥幕具\(yùn)算，專用指令與存儲(chǔ)單元也同樣與此相適應(yīng)。

2 協(xié)處理器設(shè)計(jì)

2.1 整體架構(gòu)

針對SM2算法的特點(diǎn)，借鑒通用處理器執(zhí)行計(jì)算任務(wù)的方式，本文提出的硬件協(xié)處理器整體架構(gòu)如圖2所示。

圖2 SM2硬件協(xié)處理器整體架構(gòu)Fig.2 Architecture of SM2 hardware co-processor

整體架構(gòu)包含五個(gè)部分：接口邏輯、取指單元、譯碼單元、執(zhí)行單元、程序存儲(chǔ)單元和數(shù)據(jù)存儲(chǔ)單元，其中的指令是根據(jù)SM2算法的特點(diǎn)而專門設(shè)計(jì)的，具有控制256位整數(shù)的模加減、模乘、模逆和移位運(yùn)算、數(shù)據(jù)讀寫、指令跳轉(zhuǎn)等功能。接口邏輯從外部接收數(shù)據(jù)和控制信號(hào)，根據(jù)控制信號(hào)決定協(xié)處理器的工作狀態(tài)：存取數(shù)據(jù)、執(zhí)行算法或者空閑；執(zhí)行算法時(shí)取指單元會(huì)根據(jù)程序計(jì)數(shù)器所記錄的當(dāng)前指令地址從程序存儲(chǔ)單元中取出指令，并更新程序計(jì)數(shù)器；取出的指令傳到譯碼單元，譯碼單元按照一定規(guī)則對指令進(jìn)行譯碼，確定當(dāng)前指令所要完成的功能；執(zhí)行單元負(fù)責(zé)實(shí)現(xiàn)具體的計(jì)算任務(wù)，包括256位整數(shù)的模加減、模乘、模逆和移位運(yùn)算；程序存儲(chǔ)單元負(fù)責(zé)存儲(chǔ)實(shí)現(xiàn)SM2算法的指令序列，加密、解密、簽名、驗(yàn)簽分別對應(yīng)不同的地址范圍；數(shù)據(jù)存儲(chǔ)單元負(fù)責(zé)存儲(chǔ)曲線參數(shù)以及中間數(shù)據(jù)，能夠根據(jù)需要快速地進(jìn)行讀寫。

作為一個(gè)能夠獨(dú)立執(zhí)行SM2算法的硬件模塊，所設(shè)計(jì)的協(xié)處理器具有類似主處理器的簡單工作過程，所有專用指令和中間數(shù)據(jù)的處理都在模塊內(nèi)部進(jìn)行，并具有四級(jí)流水線結(jié)構(gòu)。在執(zhí)行SM2算法之前，協(xié)處理器需要首先通過對外接口從主處理器獲取的輸入數(shù)據(jù)，如待簽名消息的哈希值、公私鑰對等，將輸入數(shù)據(jù)存入數(shù)據(jù)存儲(chǔ)單元的特定位置，然后才能執(zhí)行相應(yīng)算法，算法執(zhí)行結(jié)束后同樣會(huì)將結(jié)果保存至數(shù)據(jù)存儲(chǔ)單元的特定位置，主處理器可以通過接口進(jìn)行讀取，這一過程均在接口邏輯的控制下完成。

2.2 專用指令集

根據(jù)SM2算法的實(shí)際計(jì)算需求，本文設(shè)計(jì)了協(xié)處理器可執(zhí)行的專用指令集，包含17條專用指令，每條指令具有30位固定長度，指令格式為：6位操作碼opr+8位源操作數(shù)1地址rs+8位源操作數(shù)2地址rt+8位目的操作數(shù)地址rd，操作碼決定了指令的功能，均為SM2算法在實(shí)現(xiàn)過程中涉及到的基本操作，包括素域GF(p)和GF(n)上的模加、模減、模乘和模逆運(yùn)算，移位運(yùn)算，指令跳轉(zhuǎn)等，具體如表1所示。

表1 專用指令操作碼功能Table 1 Functions of specific instructions’opcode

在表1中，[rs]、[rt]表示按照地址rs、rt從數(shù)據(jù)存儲(chǔ)單元中取出的數(shù)據(jù)，[rd]表示按照地址rd待寫入數(shù)據(jù)存儲(chǔ)單元的數(shù)據(jù)，pc為程序計(jì)數(shù)器，用于存放當(dāng)前欲執(zhí)行指令在指令存儲(chǔ)單元中的地址。指令1為空指令，不執(zhí)行任何操作，用于算法執(zhí)行結(jié)束；指令2~9控制素域上的運(yùn)算，調(diào)用同一個(gè)計(jì)算模塊執(zhí)行256位模加、模減、模乘和模逆操作，然后依據(jù)具體指令選擇模數(shù)是p還是n，需要注意的是，由于執(zhí)行單元采用Montgomery模乘的實(shí)現(xiàn)方法，所以指令中的模乘同樣是指Montgomery模乘；指令10可以讀取[rs]，用于算法執(zhí)行結(jié)束后對外輸出結(jié)果；指令11可以將當(dāng)前指令地址加2后存入[rd]，用于保存調(diào)用標(biāo)量乘函數(shù)之后的返回地址；指令12是將[rs]左移一位后存入[rd]，用于標(biāo)量乘算法每次循環(huán)后對標(biāo)量的處理；指令13~17為跳轉(zhuǎn)指令，可以改變指令序列的執(zhí)行順序，用于算法中的循環(huán)控制，條件轉(zhuǎn)移和函數(shù)調(diào)用，包括直接跳轉(zhuǎn)、根據(jù)[rs]是否為0進(jìn)行跳轉(zhuǎn)、根據(jù)[rs]最高位是否為1進(jìn)行跳轉(zhuǎn)以及根據(jù)[rs]和[rt]的大小關(guān)系進(jìn)行跳轉(zhuǎn)。以上指令可以覆蓋SM2中除輔助函數(shù)之外的所有基本操作，通過編寫指令序列的方式即可實(shí)現(xiàn)相應(yīng)的算法流程。

在定義了指令的格式和功能的基礎(chǔ)上，SM2加密、解密、簽名、驗(yàn)簽算法中除輔助函數(shù)之外的計(jì)算過程可以通過手工編寫指令序列完成。指令序列存儲(chǔ)在程序存儲(chǔ)單元中，程序存儲(chǔ)單元在FPGA上以寄存器數(shù)組的形式實(shí)現(xiàn)，地址位寬是7位，數(shù)據(jù)位寬是30位，通過給寄存器賦初值的方式將指令序列寫入。為了節(jié)省寄存器資源，程序存儲(chǔ)單元可以根據(jù)算法類型被動(dòng)態(tài)賦值，比如同一段地址對應(yīng)的寄存器就可以依據(jù)輸入的算法選擇信號(hào)而被賦予加密或簽名的指令序列。由于協(xié)議層會(huì)多次調(diào)用標(biāo)量乘算法，所以依據(jù)算法1編寫的標(biāo)量乘算法指令序列會(huì)被寫入特定的地址范圍0x01~0x43，協(xié)議層在調(diào)用這段指令序列時(shí)只需將輸入的標(biāo)量值d和點(diǎn)P寫入特定位置，并保存返回地址，然后指令跳轉(zhuǎn)至0x01位置即可。協(xié)議層加密、解密、簽名、驗(yàn)簽算法的起始地址均為0x44，因?yàn)樗惴ㄩL度不同，所以有不同的結(jié)束地址，通過將pc的值初始化為起始地址并在wen信號(hào)的控制下使算法開始執(zhí)行，當(dāng)pc指向所選擇算法的結(jié)束地址時(shí)終止執(zhí)行。指令序列可以根據(jù)具體需求重新編寫，可以實(shí)現(xiàn)更快速或更安全的優(yōu)化算法。

程序存儲(chǔ)單元中的指令序列通過取值單元逐條取出。取指單元包含一個(gè)程序計(jì)數(shù)器pc和一個(gè)指令寄存器inst，可以按照順序或者轉(zhuǎn)移的方式從程序存儲(chǔ)單元中取出待執(zhí)行的指令。程序計(jì)數(shù)器pc存放當(dāng)前指令在程序存儲(chǔ)單元中的地址，其初始值是SM2算法指令的起始地址0x44。當(dāng)接收到接口邏輯發(fā)送的執(zhí)行算法的命令時(shí)，取指單元將pc的值發(fā)送至程序存儲(chǔ)單元的地址端口，經(jīng)過一個(gè)時(shí)鐘周期后取出指令，并將其存放在inst中發(fā)送至譯碼單元。之后需要對pc的值進(jìn)行更新，以便去取下一條指令，對pc的更新要考慮當(dāng)前指令是否為轉(zhuǎn)移指令，如果是轉(zhuǎn)移指令，則將pc賦值為指令中要轉(zhuǎn)移的目的地址（條件轉(zhuǎn)移指令還需要判斷是否滿足轉(zhuǎn)移條件），否則令pc=pc+1。當(dāng)pc增加至算法指令的結(jié)束地址時(shí)，停止取指操作并不再更新pc，同時(shí)給出執(zhí)行結(jié)束的信號(hào)。

譯碼單元從取指單元獲得inst指令并對其執(zhí)行譯碼操作，工作時(shí)首先將30位指令分解成6位操作碼opr+8位源操作數(shù)1地址rs+8位源操作數(shù)2地址rt+8位目的操作數(shù)地址rd的形式，然后對操作碼opr進(jìn)行判斷，如果是表1所述的17種情況之一，則按照對應(yīng)關(guān)系將操作碼轉(zhuǎn)換為具體的行為，完成對相關(guān)寄存器的賦值過程，向執(zhí)行單元發(fā)送使能信號(hào)和運(yùn)算類型的選擇信號(hào)，向數(shù)據(jù)存儲(chǔ)單元發(fā)送地址信息。由于不同類型的指令需要耗費(fèi)不同的時(shí)鐘周期數(shù)，所以譯碼單元同時(shí)還會(huì)根據(jù)操作碼類型設(shè)定延時(shí)周期。

2.3 執(zhí)行單元

執(zhí)行單元是整個(gè)協(xié)處理器的核心運(yùn)算模塊，完成SM2算法中的底層計(jì)算任務(wù)，即素域上的大數(shù)模運(yùn)算和移位運(yùn)算，其硬件架構(gòu)如圖3所示。

在圖3中，執(zhí)行單元以256位無符號(hào)整數(shù)a、b為輸入，執(zhí)行以p和n為模數(shù)的模加減、模乘和模逆的運(yùn)算，以及對a的移位運(yùn)算。模逆單元實(shí)現(xiàn)的是二進(jìn)制擴(kuò)展Euclidean算法，其中需要用到模加減和移位操作，為了節(jié)省硬件資源，直接將執(zhí)行上層指令的模加減和移位單元加入模逆單元中，通過控制命令來選擇執(zhí)行的運(yùn)算類型，如果是模逆運(yùn)算，則在模逆控制器的控制下完成計(jì)算任務(wù)，大約耗時(shí)1 300個(gè)時(shí)鐘周期；如果是模加減或移位運(yùn)算，則直接將數(shù)據(jù)輸入模加/減或移位單元，只需1個(gè)時(shí)鐘周期即可完成計(jì)算。

圖3 執(zhí)行單元硬件架構(gòu)Fig.3 Hardware architecture of execute unit

相比于普通模乘，Montgomery模乘因避免了取模過程當(dāng)中的除法操作而更加高效，因此執(zhí)行單元采用了實(shí)現(xiàn)Montgomery模乘算法的模乘單元。在可并行的高階Montgomery模乘算法[12]（算法2）實(shí)現(xiàn)方案的基礎(chǔ)上，本文增加了對模數(shù)p和n的選擇，以及針對“Montgomery友好”[13]的模數(shù)p作了優(yōu)化，進(jìn)一步提高了計(jì)算速度。另外，硬件實(shí)現(xiàn)過程中的最后一步約減操作具有固定時(shí)長的特點(diǎn)，避免了算法最后一步的條件約減可能存在側(cè)信道信息泄露的風(fēng)險(xiǎn)。

模乘單元包含模乘控制器、乘加模塊、寄存器堆和減法器四個(gè)主要部分，其硬件架構(gòu)如圖4所示。其中模乘控制器通過狀態(tài)轉(zhuǎn)換的方式控制算法的執(zhí)行順序，在接收到外部傳來的start信號(hào)之后，其狀態(tài)由空閑轉(zhuǎn)為開始運(yùn)行，之后每個(gè)時(shí)鐘周期狀態(tài)轉(zhuǎn)換一次，同時(shí)向乘加模塊和寄存器堆發(fā)送當(dāng)前狀態(tài)下的執(zhí)行命令；乘加模塊包含兩個(gè)并行執(zhí)行(c,z)=a+xy+b的乘加器，不同狀態(tài)下會(huì)有不同的數(shù)據(jù)給到輸入端口a、x、y、b，當(dāng)狀態(tài)對應(yīng)于算法2中的第5步和第6步，第8步和第9步，以及第12步與下次循環(huán)中的第3步時(shí)，兩個(gè)乘加器同時(shí)工作，經(jīng)過一個(gè)時(shí)鐘周期得到計(jì)算結(jié)果；寄存器堆存放計(jì)算過程中產(chǎn)生的中間結(jié)果，并根據(jù)當(dāng)前狀態(tài)將相應(yīng)的值傳入乘加模塊，當(dāng)算法2中的外層循環(huán)部分執(zhí)行結(jié)束后，將所得結(jié)果傳給減法器；減法器執(zhí)行最后一步減法運(yùn)算，根據(jù)減法是否產(chǎn)生借位決定最終的輸出結(jié)果。模乘單元可以根據(jù)輸入的sel信號(hào)選擇模數(shù)為p還是n，對應(yīng)的w會(huì)通過預(yù)計(jì)算得到，寫入乘加模塊中。因?yàn)閜是“Montgomery友好”模數(shù)，通過p計(jì)算得到的w值為1，所以當(dāng)模數(shù)為p時(shí)可以省略算法2中的第4步運(yùn)算，得到更快的計(jì)算速度。

圖4 模乘單元硬件架構(gòu)Fig.4 Hardware architecture of modular multiplication unit

算法2可并行的高階Montgomery模乘算法

輸入：A,B,P,w,wherew=-P-1modr,r=2n

輸出：Z=A×B×R-1modP,whereR=rm

模乘單元計(jì)算一次Montgomery模乘所耗費(fèi)的周期數(shù)與算法2中m的取值有關(guān)，m取值越大周期數(shù)越少，但同時(shí)會(huì)導(dǎo)致乘加模塊的計(jì)算延時(shí)增加，降低時(shí)鐘頻率，所以需要平衡時(shí)鐘頻率和周期數(shù)之間的關(guān)系。通過實(shí)驗(yàn)發(fā)現(xiàn)，對256位Montgomery模乘，當(dāng)m=4時(shí)可以在計(jì)算速度上達(dá)到最優(yōu)，此時(shí)n=64，即乘加模塊的輸入輸出數(shù)據(jù)為64位。如果算法2中的每一步運(yùn)算耗時(shí)一個(gè)時(shí)鐘周期，那么對模數(shù)n的Montgomery模乘需耗時(shí)26個(gè)時(shí)鐘周期，而對模數(shù)p的Montgomery模乘需耗時(shí)22個(gè)時(shí)鐘周期。為了盡可能降低關(guān)鍵路徑上乘加模塊的計(jì)算延時(shí)，以提高整體時(shí)鐘頻率，本文對其中包含的乘加器作了優(yōu)化設(shè)計(jì)，如圖5所示。

乘加器包含16個(gè)16×16的乘法計(jì)算單元和8個(gè)不同位數(shù)的加法計(jì)算單元，計(jì)算(c,z)=a+xy+b的過程分為四級(jí)：第一級(jí)是將輸入的64位乘數(shù)x、y以16位為單位從高到低分解成{x3,x2,x1,x0}和{y3,y2,y1,y0}，然后按照圖5所示的傳輸路徑同時(shí)給到16個(gè)乘法計(jì)算單元實(shí)現(xiàn)兩兩互乘，得到16個(gè)32位部分積，與此同時(shí)，右上方的64位加法計(jì)算單元完成了a+b的計(jì)算；第二級(jí)是將16個(gè)部分積在移位、合并之后進(jìn)行兩兩相加，移位操作按照部分積乘數(shù)的位置，如x0y1需左移16位，移位之后相差32位的數(shù)據(jù)可以直接合并，如左移16位的x0y1和左移48位的x0y3，再使用四個(gè)加法計(jì)算單元將合并之后的數(shù)據(jù)相加，包括a+b的和；第三級(jí)是將第二級(jí)得到的四個(gè)結(jié)果再進(jìn)行兩兩相加；第四級(jí)執(zhí)行最后一步加法運(yùn)算，輸出128位計(jì)算結(jié)果{c,z}。整個(gè)計(jì)算過程在一個(gè)時(shí)鐘周期內(nèi)完成，最長延時(shí)路徑包括1個(gè)乘法計(jì)算單元和3個(gè)加法計(jì)算單元，在FPGA上此路徑延時(shí)小于10 ns，有效地提高了乘法器的最高工作頻率。

圖5 乘加器硬件架構(gòu)Fig.5 Hardware architecture of multiply-add unit

2.4 流水線結(jié)構(gòu)

類似于通用處理器的指令處理方式，SM2專用指令協(xié)處理器同樣采用了流水線技術(shù)，將指令的處理過程分為取指、譯碼、執(zhí)行、寫回四級(jí)流水，譯碼階段同時(shí)包含了取操作數(shù)，流水線結(jié)構(gòu)如圖6所示。

圖6 指令流水線結(jié)構(gòu)Fig.6 Pipeline architecture of instructions

為了使SM2協(xié)處理器的各功能單元能夠按照圖6所示的流水方式運(yùn)行，需要合理安排時(shí)序。在指令流水中，取指、譯碼和寫回都只需要一個(gè)時(shí)鐘周期，而執(zhí)行階段所需耗費(fèi)的時(shí)鐘周期數(shù)取決于指令類型，所以在譯碼階段需要給出指令的延時(shí)周期數(shù)。另外還需設(shè)置一個(gè)延時(shí)計(jì)數(shù)器來記錄運(yùn)行周期，在每條指令的執(zhí)行階段開始時(shí)刻將其置零，然后每個(gè)時(shí)鐘周期加1。由計(jì)數(shù)器的值與當(dāng)前指令的延時(shí)周期數(shù)的關(guān)系可以確定后續(xù)指令的譯碼、取指時(shí)刻以及當(dāng)前指令的寫回和下條指令的執(zhí)行時(shí)刻。需要注意的是，由于相鄰指令之間往往具有數(shù)據(jù)相關(guān)性，而下條指令的執(zhí)行與當(dāng)前指令的寫回是發(fā)生在同一時(shí)刻的，這就要求數(shù)據(jù)存儲(chǔ)單元能夠及時(shí)為下條指令提供更新后的操作數(shù)，實(shí)現(xiàn)方法是當(dāng)讀寫地址相同且寫使能的情況下，數(shù)據(jù)存儲(chǔ)單元直接提供即將寫入的數(shù)據(jù)作為輸出，并在下個(gè)周期將數(shù)據(jù)寫入。由此，SM2協(xié)處理器實(shí)現(xiàn)了具有流水線結(jié)構(gòu)的指令處理過程。

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

本文采用硬件描述語言Verilog實(shí)現(xiàn)了所設(shè)計(jì)的SM2專用指令協(xié)處理器，在Xilinx ZYNQ-7 ZC706評(píng)估板上運(yùn)行，驗(yàn)證了功能的正確性。在性能方面，協(xié)處理器的最高時(shí)鐘頻率為110 MHz，可以在2 480 210個(gè)時(shí)鐘周期內(nèi)完成一次SM2中的標(biāo)量乘運(yùn)算，時(shí)間約為2.25 ms，在此基礎(chǔ)上執(zhí)行不包含輔助函數(shù)的加密、解密、簽名、驗(yàn)簽算法所需耗費(fèi)的時(shí)間分別為4.53 ms、2.27 ms、2.28 ms、4.51 ms。在資源使用方面，協(xié)處理器共占用7 146個(gè)Slice，其中LUT的使用量為14 658個(gè)，Register的使用量為17 420個(gè)，另外執(zhí)行單元還占用了32個(gè)DSP資源。安全性方面，協(xié)處理器執(zhí)行常時(shí)的MPL算法（算法1）實(shí)現(xiàn)標(biāo)量乘運(yùn)算，內(nèi)部的執(zhí)行單元能夠在固定時(shí)鐘周期數(shù)內(nèi)完成底層運(yùn)算，因而可以抵御簡單功耗攻擊。作為對比，如果使用最簡單的二進(jìn)制展開算法實(shí)現(xiàn)標(biāo)量乘，則所需耗費(fèi)的時(shí)間會(huì)減少為1.79 ms，資源使用量基本相同，但其功耗曲線會(huì)泄露標(biāo)量值信息，不具備抵御側(cè)信道攻擊的安全性。與同樣基于FPGA實(shí)現(xiàn)256位素域上橢圓曲線標(biāo)量乘的硬件協(xié)處理器對比情況如表2所示。

從表2中與相關(guān)工作的對比可以發(fā)現(xiàn)，本文實(shí)現(xiàn)的SM2硬件協(xié)處理器在速度和面積上均達(dá)到了不錯(cuò)的效果。相比于較早的工作，如文獻(xiàn)[14]和文獻(xiàn)[15]，本文的設(shè)計(jì)在速度和面積上均有優(yōu)勢，盡管使用了更先進(jìn)的FPGA平臺(tái)，但這種優(yōu)勢依然可以從設(shè)計(jì)方法中體現(xiàn)出來，其采用的乘完之后再約減的方法使模乘單元的數(shù)據(jù)通路中包含512位的數(shù)據(jù)，這樣的數(shù)據(jù)位寬限制了其頻率的提高，另外有限狀態(tài)機(jī)（FSM）的使用也增加了控制邏輯所占用的資源。文獻(xiàn)[3]提出的設(shè)計(jì)可以占用較少的資源，達(dá)到較高的頻率，但在計(jì)算耗時(shí)上較本文稍差，說明本文提出的設(shè)計(jì)可以在較低功耗的條件下實(shí)現(xiàn)比其更快的計(jì)算速度。文獻(xiàn)[4]實(shí)現(xiàn)了高性能低功耗的標(biāo)量乘計(jì)算，其加速方法主要來自于針對SM2素?cái)?shù)域GF(p)的快速約減，但沒有考慮SM2協(xié)議層上除標(biāo)量乘之外的其他運(yùn)算，而本文的協(xié)處理器同時(shí)考慮了GF(p)和GF(n)上的模運(yùn)算，更適用于協(xié)議層的實(shí)現(xiàn)。需要說明的是，本文提出的協(xié)處理器所占用的資源中，有很大一部分是用于標(biāo)量乘之外的其他運(yùn)算，如簽名算法的指令和數(shù)據(jù)的存儲(chǔ)需要使用額外的Slice，如果與其他文獻(xiàn)一樣只考慮標(biāo)量乘運(yùn)算所需的資源，則Slice的使用量將會(huì)減少20%左右。

表2 相關(guān)工作對比Table 2 Comparison between related works

4 總結(jié)

本文提出一種具有SM2專用指令的硬件協(xié)處理器，可以通過類似通用處理器的工作方式執(zhí)行專用指令序列，從而實(shí)現(xiàn)了SM2簽名、驗(yàn)簽、加密、解密中除輔助函數(shù)之外的所有運(yùn)算。其中，適用于SM2算法的專用指令集、高效的執(zhí)行單元和四級(jí)流水線結(jié)構(gòu)是所提出的SM2硬件協(xié)處理器的主要特點(diǎn)。與通過有限狀態(tài)機(jī)控制算法流程的實(shí)現(xiàn)方法相比，設(shè)計(jì)專用指令可以結(jié)合軟硬件實(shí)現(xiàn)各自的優(yōu)勢，更加靈活高效地利用資源，達(dá)到軟硬件協(xié)同優(yōu)化的效果。執(zhí)行單元的設(shè)計(jì)采用可并行的高階Montgomery模乘算法，減少執(zhí)行模乘運(yùn)算所需的時(shí)鐘周期，同時(shí)對關(guān)鍵路徑上的核心計(jì)算單元進(jìn)行了優(yōu)化，提高了工作頻率。流水線結(jié)構(gòu)將指令的實(shí)現(xiàn)過程分為取指、譯碼、執(zhí)行和寫回四個(gè)階段，通過四級(jí)流水使協(xié)處理器的工作更加高效。

實(shí)驗(yàn)結(jié)果表明，本文所提出的協(xié)處理器可以以較快的速度實(shí)現(xiàn)安全的橢圓曲線標(biāo)量乘算法，同時(shí)占用較少的硬件資源。與之前的工作相比，本文同時(shí)考慮了標(biāo)量乘算法和SM2協(xié)議層的其他運(yùn)算，更加適用于完整協(xié)議的實(shí)現(xiàn)。另外，通過修改指令序列，本文提出的協(xié)處理器可以實(shí)現(xiàn)更加安全或快速的標(biāo)量乘算法，也能夠很容易地修改為支持基于ECC的其他公鑰密碼協(xié)議，具有軟件實(shí)現(xiàn)的靈活性優(yōu)勢。