雙線性密碼引擎的實(shí)現(xiàn)*

王 松，張 潔

（1.中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041；2.石家莊信息工程職業(yè)學(xué)院，河北 石家莊 050035）

0 引 言

為了簡(jiǎn)化公鑰基礎(chǔ)設(shè)施對(duì)用戶公鑰證書的管理，Shamir在1984年提出了基于身份密碼體制的概念，核心思想是利用用戶的身份信息作為用戶的公鑰[1]。在該體制下，用戶利用對(duì)方的身份信息（如設(shè)備ID號(hào)、身份證號(hào)碼、手機(jī)號(hào)碼、郵件地址等）作為公鑰來使用，用戶無需事先申請(qǐng)證書，也不用查詢和驗(yàn)證證書，相比傳統(tǒng)的公鑰基礎(chǔ)設(shè)施具有突出的優(yōu)勢(shì)。

在2000年左右，密碼學(xué)家們提出了使用橢圓曲線上的雙線性對(duì)來設(shè)計(jì)基于身份加密方案的思路，并且給出了該密碼方案的安全性證明，引起了密碼學(xué)術(shù)界的極大反響[2]。此后，采用橢圓曲線上的雙線性對(duì)來設(shè)計(jì)標(biāo)識(shí)密碼算法，成為密碼學(xué)術(shù)界的研究熱點(diǎn)。從2006年起，國(guó)家密碼管理局組織了密碼學(xué)領(lǐng)域的相關(guān)專家開始進(jìn)行標(biāo)識(shí)密碼算法的研究，并在2016年3月頒布了我國(guó)的商用標(biāo)識(shí)密碼算法——SM9。標(biāo)識(shí)密碼算法發(fā)展的時(shí)間還不長(zhǎng)，主要以軟件實(shí)現(xiàn)為主。標(biāo)識(shí)密碼算法本身較為復(fù)雜，在現(xiàn)在大多數(shù)嵌入式處理器中的運(yùn)行性能遠(yuǎn)遠(yuǎn)不能滿足實(shí)際應(yīng)用需求。在許多嵌入式設(shè)備中，可利用FPGA做一些輔助運(yùn)算。如果能在FPGA中利用較少的資源實(shí)現(xiàn)復(fù)雜的雙線性運(yùn)算，將大大提高設(shè)備的標(biāo)識(shí)算法運(yùn)算性能。本文參考當(dāng)前市場(chǎng)上的密碼芯片設(shè)計(jì)原理[3]，設(shè)計(jì)了一款適合用于雙線性標(biāo)識(shí)密碼算法的密碼引擎，并完成了SM9算法的雙線性運(yùn)算在該引擎上的實(shí)現(xiàn)。最終的測(cè)試驗(yàn)證表明，相比嵌入式處理器，該密碼引擎能有效實(shí)現(xiàn)雙線性密碼運(yùn)算的加速。

1 SM9密碼算法

1.1 SM9密碼算法運(yùn)算層次

在SM9標(biāo)識(shí)密碼算法的第5部分參數(shù)定義中規(guī)定，SM9標(biāo)識(shí)密碼發(fā)的曲線參數(shù)是基于BN曲線上R-ate對(duì)的，其橢圓曲線方程式為y2=x3+b。群G1和群G2分別在常曲線和參數(shù)為的扭曲線上。所有的運(yùn)算都在素域上進(jìn)行，數(shù)學(xué)運(yùn)算層次可以分為基礎(chǔ)運(yùn)算層、曲線運(yùn)算層、塔式擴(kuò)張層、群運(yùn)算層、雙線性運(yùn)算層和應(yīng)用層。各個(gè)層次之間的關(guān)系如圖1所示。

圖1 標(biāo)識(shí)密碼算法運(yùn)算層次

基礎(chǔ)運(yùn)算層在素域上進(jìn)行，包括模加法運(yùn)算、模減法運(yùn)算、模逆運(yùn)算、模乘運(yùn)算、數(shù)據(jù)比較、數(shù)據(jù)比特移位等基礎(chǔ)操作。曲線運(yùn)算層包括常曲線和扭曲線的點(diǎn)加、倍點(diǎn)等運(yùn)算。群運(yùn)算層主要是指常曲線和扭曲線上的標(biāo)量乘法。很多標(biāo)識(shí)密碼算法（如SM9等）的雙線性運(yùn)算在擴(kuò)域中進(jìn)行，塔式擴(kuò)張層的作用是將擴(kuò)域中的元素用基域中的元素進(jìn)行表示和計(jì)算。雙線性運(yùn)算層通過調(diào)用底層的數(shù)學(xué)運(yùn)算實(shí)現(xiàn)雙線性對(duì)的運(yùn)算。本文實(shí)現(xiàn)的雙線性層運(yùn)算是基于BN曲線上R-ate對(duì)。應(yīng)用層一般是指密鑰協(xié)商、簽名驗(yàn)簽和加解密等上層應(yīng)用。

本文設(shè)計(jì)的雙線性密碼引擎設(shè)計(jì)定位是實(shí)現(xiàn)應(yīng)用層以下的所有運(yùn)算層。應(yīng)用層以下的群運(yùn)算層、雙線性運(yùn)算層等占用了標(biāo)識(shí)密碼算法的絕大部分運(yùn)算時(shí)間。對(duì)該部分運(yùn)算的加速能較好地提高標(biāo)識(shí)密碼的運(yùn)算性能。

標(biāo)識(shí)密碼算法的應(yīng)用層運(yùn)算在整個(gè)算法中的運(yùn)算開銷不多。但是，不同的算法在這個(gè)層次的設(shè)計(jì)都有自己的特點(diǎn)，組織較為靈活。如果在密碼引擎中實(shí)現(xiàn)應(yīng)用層的運(yùn)算，需要較多的硬件資源來實(shí)現(xiàn)這些處理模塊，但對(duì)整個(gè)算法的性能并不能帶來比較明顯的提升。這種情況和ECC算法比較類似。國(guó)內(nèi)絕大多數(shù)橢圓曲線密碼芯片也僅實(shí)現(xiàn)了群運(yùn)算層及以下的運(yùn)算處理。

標(biāo)識(shí)密碼算法的應(yīng)用層可在調(diào)用密碼引擎的處理器中實(shí)現(xiàn)，達(dá)到標(biāo)識(shí)密碼算法性能加速的目的，如圖2所示。

圖2 標(biāo)識(shí)密碼算法實(shí)現(xiàn)方式

1.2 基礎(chǔ)運(yùn)算層

基礎(chǔ)運(yùn)算層是實(shí)現(xiàn)標(biāo)識(shí)密碼算法的基礎(chǔ)。密碼算法在運(yùn)行過程中需要反復(fù)調(diào)用基礎(chǔ)運(yùn)算層的運(yùn)算?；A(chǔ)運(yùn)算層的運(yùn)算性能對(duì)整個(gè)算法的性能影響較大，設(shè)計(jì)時(shí)需要盡量?jī)?yōu)化其性能。基礎(chǔ)運(yùn)算層的運(yùn)算主要有素?cái)?shù)域和二進(jìn)制域兩種。因?yàn)镾M9算法規(guī)定的曲線參數(shù)定義在素域上，所以本文設(shè)計(jì)的雙線性密碼引擎的基礎(chǔ)運(yùn)算是基于素域的。

素域中的基礎(chǔ)運(yùn)算層運(yùn)算是基于素?cái)?shù)進(jìn)行的?；A(chǔ)運(yùn)算的結(jié)果需要對(duì)該素?cái)?shù)求模。例如，數(shù)據(jù)d1、d2基于P的模乘法運(yùn)算，是將兩個(gè)數(shù)先做乘法，再將乘法結(jié)果對(duì)素?cái)?shù)P進(jìn)行求模。

在基礎(chǔ)運(yùn)算層中，模加法運(yùn)算、模減法運(yùn)算、模乘運(yùn)算、數(shù)據(jù)比較、數(shù)據(jù)比特移位等基礎(chǔ)操作采用硬件邏輯實(shí)現(xiàn)。其中，模乘運(yùn)算較為復(fù)雜，如果直接實(shí)現(xiàn)該運(yùn)算需要較多的硬件資源開銷，且運(yùn)算速度很慢。通常情況下，非對(duì)稱密碼算法中的模乘運(yùn)算都轉(zhuǎn)換到了蒙哥馬利域中進(jìn)行[4]，故雙線性密碼引擎中的模乘模塊完成的是蒙哥馬利模乘。模逆運(yùn)算在整個(gè)標(biāo)識(shí)密碼算法中調(diào)用次數(shù)比其他基礎(chǔ)運(yùn)算模塊要少得多，且其計(jì)算較為復(fù)雜，模逆運(yùn)算的實(shí)現(xiàn)需要消耗大量的硬件資源，但對(duì)整個(gè)算法的性能提升影響不大。綜上所述，模逆運(yùn)算采用編程的方式調(diào)用其他基礎(chǔ)運(yùn)算模塊實(shí)現(xiàn)。

1.3 曲線運(yùn)算層

因?yàn)镾M9算法的曲線有常曲線和扭曲線兩種。曲線運(yùn)算層的運(yùn)算包括兩種曲線的點(diǎn)加、倍點(diǎn)、無窮遠(yuǎn)點(diǎn)判斷及處理等運(yùn)算。扭曲線與常曲線的點(diǎn)加和倍點(diǎn)運(yùn)算基于相同的運(yùn)算步驟，區(qū)別在于二者所屬的群不同。一般來講，扭曲線的運(yùn)算性能是常曲線的1/4左右。該層運(yùn)算通過在密碼引擎中編程的方式調(diào)用基礎(chǔ)運(yùn)算層的基礎(chǔ)運(yùn)算單元來實(shí)現(xiàn)。

1.4 塔式擴(kuò)張層

塔式擴(kuò)張運(yùn)算是雙線性運(yùn)算的基礎(chǔ)，SM9算法規(guī)定的曲線參數(shù)中嵌入次數(shù)等于12。Fq12可以按照1→2→4→12的方式進(jìn)行擴(kuò)張。下面以1→2為例，說明擴(kuò)域中的運(yùn)算規(guī)則。

Fq2[u]=Fq[u]/(u-a)，a=-2。定義兩個(gè)Fq2中的元素A=(a0,a1)，B=(b0,b1)。Fq2上的模加法和模減法是對(duì)應(yīng)維度上的數(shù)據(jù)進(jìn)行模加運(yùn)算和模減運(yùn)算，即X+Y=(a0+b0,a1+b1)，X-Y=(a0-b0,a1-b1)。模乘法需要將多項(xiàng)式乘法的結(jié)果進(jìn)行求模，X*Y在Fq2中的模乘結(jié)果為：X*Y=(a0*b1+a1*b0,a1*b1-2a0*b0)。

1.5 群運(yùn)算層

群運(yùn)算層實(shí)現(xiàn)常曲線和扭曲線的標(biāo)量乘法運(yùn)算，已經(jīng)有比較成熟的方法。本設(shè)計(jì)中，為了節(jié)約硬件資源的開銷，密碼引擎模塊僅支持二進(jìn)制方法的標(biāo)量乘法運(yùn)算。群運(yùn)算層的實(shí)現(xiàn)通過在密碼引擎中編程的調(diào)用曲線層運(yùn)算來實(shí)現(xiàn)。

1.6 雙線性運(yùn)算層

SM9算法雙線性運(yùn)算層的實(shí)現(xiàn)參考SM9標(biāo)識(shí)密碼算法第一部分中BN曲線上R-ate對(duì)計(jì)算給出的計(jì)算步驟來實(shí)現(xiàn)。在雙線性對(duì)計(jì)算過程中，會(huì)使用Miller算法[5]。Miller算法是一種計(jì)算雙線性對(duì)的有效算法，在SM9標(biāo)識(shí)密碼算法第一部分的附錄B中有完整的表述。

2 雙線性密碼引擎設(shè)計(jì)

雙線性密碼引擎的的內(nèi)部功能邏輯，如圖3所示。

圖3 雙線性密碼引擎內(nèi)部功能邏輯

雙線性密碼引擎由密碼引擎核、接口數(shù)據(jù)存儲(chǔ)器、程序存儲(chǔ)器、臨時(shí)數(shù)據(jù)存儲(chǔ)器、總線控制器以及基礎(chǔ)運(yùn)算層的硬件運(yùn)算單元組成。

2.1 存儲(chǔ)器

在雙線性密碼引擎內(nèi)部包括三個(gè)存儲(chǔ)器單元，分別是接口數(shù)據(jù)存儲(chǔ)器、臨時(shí)數(shù)據(jù)存儲(chǔ)器和程序存儲(chǔ)器。接口數(shù)據(jù)存儲(chǔ)器主要用于配合接口總線完成與外部控制芯片的信息交換。臨時(shí)數(shù)據(jù)存儲(chǔ)器用于存放程序運(yùn)行過程中的所有臨時(shí)數(shù)據(jù)，以及一些程序的運(yùn)行狀態(tài)和堆棧信息等。程序存儲(chǔ)器用于存儲(chǔ)密碼引擎運(yùn)行的程序。為了保證程序存儲(chǔ)器不會(huì)因?yàn)橐馔馐录黄茐?，程序存?chǔ)器的外部設(shè)置了一個(gè)保護(hù)電路，用戶需要更新程序存儲(chǔ)器中的數(shù)據(jù)時(shí)，必須先配置對(duì)應(yīng)的寄存器，才能完成程序存儲(chǔ)器的寫操作。

2.2 密碼引擎核

密碼引擎核是雙線性密碼引擎的核心單元。密碼引擎核負(fù)責(zé)整個(gè)密碼引擎的調(diào)度和控制。當(dāng)外部控制芯片通過接口存儲(chǔ)器和接口總線發(fā)起運(yùn)算指令時(shí)，密碼引擎立即將接收到的數(shù)據(jù)讀入臨時(shí)數(shù)據(jù)存儲(chǔ)區(qū)，并根據(jù)程序存儲(chǔ)器的程序?qū)?shù)據(jù)進(jìn)行處理。為了更好地實(shí)現(xiàn)算法加速，雙線性密碼引擎在工作室采用取指、譯碼、執(zhí)行的流水線操作。密碼引擎核訪問臨時(shí)數(shù)據(jù)存儲(chǔ)器和調(diào)用基礎(chǔ)運(yùn)算層的運(yùn)算單元都是通過總線控制器進(jìn)行的。當(dāng)程序執(zhí)行完成，密碼引擎核將得到的運(yùn)算結(jié)果從臨時(shí)存儲(chǔ)器讀出，并寫入接口數(shù)據(jù)存儲(chǔ)器，然后將運(yùn)算完成信息通過接口總線通知外部控制芯片。

2.3 基礎(chǔ)運(yùn)算模塊

雙線性密碼引擎中，基礎(chǔ)運(yùn)算層的硬件模塊負(fù)責(zé)完成一些底層的數(shù)學(xué)運(yùn)算，如蒙哥馬利模乘、模加減法和比特移位操作等?；A(chǔ)運(yùn)算層的硬件模塊通過總線控制器來完成臨時(shí)數(shù)據(jù)存儲(chǔ)器中的數(shù)據(jù)讀寫操作。

2.4 總線控制器

總線控制器是整個(gè)密碼引擎的關(guān)鍵部分。該模塊根據(jù)密碼引擎核的指令進(jìn)行整個(gè)密碼引擎芯片的數(shù)據(jù)總線切換，完成數(shù)據(jù)流的控制。如果需要進(jìn)行蒙哥馬利模乘運(yùn)算時(shí)，總線控制器必須及時(shí)將模乘模塊和臨時(shí)數(shù)據(jù)存儲(chǔ)器模塊的數(shù)據(jù)訪問通道連接，同時(shí)斷開其他模塊與臨時(shí)數(shù)據(jù)存儲(chǔ)器的連接。在需要輸出運(yùn)算結(jié)果時(shí)，總線控制器又將根據(jù)密碼引擎核送出的指令，將臨時(shí)數(shù)據(jù)存儲(chǔ)器中對(duì)應(yīng)地址的數(shù)據(jù)寫入接口數(shù)據(jù)存儲(chǔ)器的對(duì)應(yīng)地址中。

3 雙線性密碼實(shí)現(xiàn)

3.1 指令定義

雙線性密碼引擎中的指令分為運(yùn)算指令和控制指令，如表1所示。

表1 雙線性密碼引擎中指令舉例

雙線性密碼引擎中的控制指令主要負(fù)責(zé)程序運(yùn)行的跳轉(zhuǎn)、程序的返回等操作。運(yùn)算指令主要負(fù)責(zé)完成對(duì)指定數(shù)據(jù)的運(yùn)算處理，并將運(yùn)算結(jié)果輸出到指定的位置。

3.2 雙線性密碼實(shí)現(xiàn)及測(cè)試

使用雙線性密碼引擎定義的指令可以完成雙線性密碼的實(shí)現(xiàn)。例如，F(xiàn)q2中op1和op2需要進(jìn)行模乘法并輸出到rop，可以用如下代碼實(shí)現(xiàn)：

SM9算法的其他底層運(yùn)算，如Fq12上的運(yùn)算、扭曲線和常曲線的運(yùn)算等，均通過類似的方式實(shí)現(xiàn)。完成實(shí)現(xiàn)后的程序主要函數(shù)如表2所示。

在完成雙線性密碼引擎正確性驗(yàn)證后，本文對(duì)比測(cè)試了雙線性密碼引擎和ARM Cotex M7上實(shí)現(xiàn)雙線性密碼的性能，測(cè)試結(jié)果如表3所示。

表2 密碼引擎中程序主要函數(shù)

表3 對(duì)比測(cè)試結(jié)果

3.3 資源開銷情況

雙線性密碼引擎的調(diào)試通過Modelsim SE 6.5軟件進(jìn)行。完成設(shè)計(jì)后的密碼引擎代碼在Xilinx公司型號(hào)為xc5vlx50的FPGA上進(jìn)行了編譯。編譯器為Xilinx ISE Design Suite 13.2。它的硬件資源開銷情況如表4所示。

表4 雙線性密碼引擎資源開銷情況

4 結(jié) 語

本文設(shè)計(jì)的雙線性密碼引擎能較好地實(shí)現(xiàn)雙線性密碼運(yùn)算的加速。對(duì)SM9標(biāo)準(zhǔn)中規(guī)定參數(shù)的常曲線及扭曲線上的標(biāo)量乘法和雙線性運(yùn)算性能測(cè)試表明，雙線性密碼引擎能極大地提高雙線性密碼的運(yùn)算速度，整體性能提升約9倍。