低開銷三進制域Eta 雙線性對硬件加速器*

李翔宇

清華大學微電子學研究所北京信息科學與技術(shù)國家研究中心, 北京 100084

1 引言

基于身份標識的加密算法(identity-based encryption, IBE) 是一種可以使用任意字符串的公鑰密碼體制, 它因此不需要公鑰證書的發(fā)放, 簡化了密鑰管理和密鑰分配, 而且在同等安全級別下, 比其他公鑰密碼算法有更小的參數(shù), 因而計算速度更快、存儲空間更小, 符合以無線傳感器網(wǎng)絡(wireless sensor network, WSN) 為代表的物聯(lián)網(wǎng)(internet-of-things, IoT) 應用對低開銷安全機制的需求[1]. 我國國家密碼管理局發(fā)布的商用標識密碼算法SM9 就是一種IBE 算法[2]. 雙線性對是實現(xiàn)IBE 的關(guān)鍵運算, 在IBE 涉及的各種主要運算中, 它最為耗時[3], 它的性能對IBE 計算的時間有著重要影響. 采用軟件方式實現(xiàn)的雙線性對難以滿足當下網(wǎng)絡性能的要求, 因此, 在加密硬件中增加專用的雙線性對硬件加速器可以有效地提高IBE 的計算速度和能量利用率.

現(xiàn)有的雙線性對硬件加速器設(shè)計都是以計算時間為優(yōu)先考慮的指標, 普遍具有較大的硬件開銷或功耗, 并不適用于IoT 節(jié)點的應用場景. 鑒于此, 本文開展低開銷的雙線性對硬件加速器研究, 提出了一種具有更小面積時間積的電路方案.

2 相關(guān)研究

用于IBE 的雙線性對有早期的Weil[4]對和后來提出的Tate 對[5], 以及基于Tate 對的多種改進的雙線性對: 如eta (ηT[6])、ate[7]、reduced ate[8]和optimal ate[9]等. 其中定義在Barreto-Naehrig(BN) 曲線上的Optimal Ate 對計算速度最快, 也是近年研究較多的雙線性對, 但是素數(shù)域Ate 對的存儲開銷較大, 不適合應用在WSN 上. 而eta 對因為是對稱對, 所以支持更多的協(xié)議[10], 而且三進制域GF(3m) 中的乘法及加法電路簡單、同等安全性下操作數(shù)需要的存儲空間要小, eta 對在三進制域上的安全性最高[11], 因此, 三進制eta 對更適合低開銷需求的系統(tǒng), 基于此, 本文選取三進制eta 對的硬件設(shè)計進行研究.

在雙線性對硬件加速器設(shè)計方面, K?mürcü 等人[12]首次實現(xiàn)了Tate 對的ASIC 硬件加速器.Beuchat 等人[13]對三進制域eta 對實現(xiàn)算法進行分析, 提出了無立方根(cube-root-free) 運算算法, 并將Miller 循環(huán)進行循環(huán)展開, 設(shè)計了一個能夠運算模乘、立方、累加運算的復合運算模塊, 實現(xiàn)了一個更簡單的eta 對的FPGA 設(shè)計. 此后, Beuchat 等人[14]利用KOM 乘法器(Karatsub-Ofman Multiplier)設(shè)計了一個流水線結(jié)構(gòu)的高速eta 對硬件. 2010 年, Beuchat 等[15]又通過對Miller 循環(huán)中GF(36m)的稀疏乘法(Sparse Multiplication) 進行優(yōu)化和調(diào)度, 在FPGA 上實現(xiàn)了高效的GF(397)上的eta 對硬件結(jié)構(gòu). 2012 年, Li 等人[16]設(shè)計并實現(xiàn)了800 MHz 的BN 曲線上的optimal Ate 對硬件處理器. 在此基礎(chǔ)上, Jun 等人[17]利用高基Montgomery 模乘器提升了該處理器的性能. 在2015 年, Chung 等人[10]設(shè)計了全流水的eta 對硬件加速芯片, 成為目前運算速度最快的GF(397)上的eta 對ASIC 硬件加速器.

3 Eta 對和Miller 算法

Eta 對是定義在三進制域GF(3m) 超奇異橢圓曲線y2=x3?x+b上的對稱雙線性對, 其中參數(shù)b ∈{1,?1}. 目前普遍采用的三進制eta 對的計算方法是無立方根的逆向eta 對算法, 如算法1 所示:

算法1 三進制域無立方根的逆向eta 對算法[13]Input: P (xP,yP),Q(xQ,yQ) ∈E(GF(3m))[r], 中間變量t ∈GF(3m),R,S ∈GF(36m)Output: ηT (P,Q)M ∈GF(36m)1 xP = xP +b, yP = ?μbyP;2 xQ = x3Q,yQ = y3Q;3 t = xP +xQ;4 R[0] = (yP t ?yQσ ?yP ρ)·(?t2 +yP yQσ ?tρ ?ρ2);5 for i = 0 →(m ?1)/2 ?1 do R[i])3; [1 次GF(36m)立方]7 xQ = x9Q ?b,yQ = ?y9Q; [4 次GF(3m) 立方]8 t = xP +xQ,u = yP yQ,k = t2; [2 次GF(3m) 乘法]9 S = ?k+uσ ?tρ ?ρ2;10 R[i+1] = R[i] ·S; [1 次GF(36m)乘法]11 end 12 返回RM; [GF(36m)冪運算]6 R[i] =(

其中參數(shù)μ滿足:

其中R[i]表示第i輪循環(huán)得到的R,是GF(36m)中的元素. 其中ρ,σ ∈GF(36m),而且滿足ρ3?ρ?b=0和σ2+1 = 0. 由它們構(gòu)造的集合{1,σ,ρ,σρ,ρ2,σρ2}是有限域GF(36m)關(guān)于GF(3m) 的基, 因此可以將R表示為:

其中ri ∈GF(3m),i=0,··· ,5.

上述算法由兩部分組成, 第一部分是Miller 算法和一個M次的最終冪運算(算法1 第12 行). 其中Miller 循環(huán)是加速器設(shè)計的重點.

4 三進制eta 對硬件加速器設(shè)計

4.1 頂層設(shè)計

由于冪運算是對Miller 算法的結(jié)果進行計算, 并且是由一系列串行的運算來完成的, 其本身以及和Miller 算法之間并沒有太大的并行度, 即使增加運算單元, 也不會明顯縮短運算周期數(shù). 如果將Miller 運算和冪運算設(shè)計在一個電路中, 共用一個數(shù)據(jù)通路, 則電路在進行冪運算的時候不能完全利用電路中的運算單元, 效率較低. 因此我們將Miller 算法和最后的冪運算分開設(shè)計. 考慮到在本文設(shè)計中這兩個運算時間相當, 我們將Miller 算法和冪運算流水線執(zhí)行, 這樣電路的吞吐率可以提升接近一倍.

而在控制方面, 由于本文的電路規(guī)模較大, 并且Miller 算法和冪運算是不同的數(shù)據(jù)通路, 因此在控制上采用微碼控制器來實現(xiàn): 通過微碼單元輸出指令來控制數(shù)據(jù)通路.

4.2 主要運算的硬件電路

4.2.1 GF(3m) 模乘器

GF(3m) 模乘是最主要的基本運算, 本設(shè)計采用了字串行的MSE 模乘器(Most-Significant-Element first Multiplier)[18]完成. MSE 模乘器把m位的乘數(shù)分解成多個D位的字, 一次用一個字與被乘數(shù)相乘, 并進行模多項式f(x) 的運算, 整個m×m位的乘法在k=「m/個周期內(nèi)完成. 選用字串行方案是因為相比位串行的乘法器結(jié)構(gòu), 字串行結(jié)構(gòu)更加靈活, 通過選定不同的字長D, 可以實現(xiàn)具有不同面積和速度的模乘器. 為了兼顧電路的面積與速度, 本文選取字長D= 3 進行實現(xiàn). 得到的m×m位MSE電路結(jié)構(gòu)如圖1 所示. 注意: 在電路中每個三進制位使用2 比特信號表示. 其中的乘數(shù)B使用2m比特移位寄存器保存, 每個時鐘周期向左移2D位(對應D個三進制位), 每一輪運算先由部分積運算電路(圖中用乘號表示) 產(chǎn)生D個部分積并移位, 同時模運算單元對上一輪運算的結(jié)果取模并移位, 最后將這些結(jié)果進行累加. 其中部分積的產(chǎn)生由m個GF(3m) 乘法單元完成.

圖1 MSE 模乘器結(jié)構(gòu)Figure 1 MSE multiplier

4.2.2 GF(3m) 立方-加法單元

在Miller 算法和最后的冪運算中都需要較多的立方運算. 如果直接用兩次GF(3m) 模乘來計算的話開銷太大時間也太長. 本文采用文獻[19] 的方法—將立方運算用兩次GF(3m) 的加法完成, 具體原理不再贅述. 首先將擴域的階數(shù)m表示為m= 3μ+r, 其中μ> 0,r=mmod 3∈{0,1,2}, 然后計算式如式(2)所示. 其核心是計算3 個系數(shù)(C0、C1、C2), 它們都是操作數(shù)各位的線性組合(如式(3)), 然后通過兩次加法進行累加. 在本文設(shè)計中根據(jù)算法運算規(guī)律, 我們將立方運算和加法運算合并構(gòu)成立方-加法運算單元, 如圖2 所示. 這個單元可以完成A3+B的運算, 當B=0 時, 即是立方運算單元; 當左右兩個多路選擇器分別選擇1 和0 時, 即執(zhí)行A+B.

圖2 立方-加法單元電路結(jié)構(gòu)Figure 2 Structure of cube-addition unit

4.3 Miller 算法的硬件設(shè)計

Miller 循環(huán)中的R的迭代乘法(算法1 的第10 行) 是GF(36m)的乘法, 由于多項式S只有4 項非0 系數(shù), 因此該步乘法被稱為稀疏乘法. 前人的工作重點普遍是對GF(36m)的稀疏乘法進行優(yōu)化, 努力減少GF(3m) 模乘運算的次數(shù)來降低運算的復雜度. 雖然乘法次數(shù)的降低有利于硬件面積的降低, 但是加法次數(shù)也在急劇地增加, 而控制邏輯也更加復雜. 為了控制電路規(guī)模和功耗, 本文并不一味地追求乘法次數(shù)的降低, 而是通過乘法和加法次數(shù)之間的平衡, 此外, 考慮到Miller 運算的中間結(jié)果具有較大的長度,通常為幾百上千比特, 對于運算中間結(jié)果的存儲和傳輸開銷也進行優(yōu)化——通過調(diào)度盡量減少中間值的存儲和傳輸來提高硬件實現(xiàn)效率, 比如讓各個運算之間共享操作數(shù).

4.3.1 算法調(diào)度與優(yōu)化

首先, 我們把GF(36m)的立方與稀疏乘法(算法1 的第6 行與第10 行) 結(jié)合起來進行優(yōu)化, 尋求更大的并行度和可共享的操作, 整合后的Miller 循環(huán)運算式變?yōu)?

為了直觀表達運算結(jié)果, 先定義中間變量:

并定義A′=?A ?E,B′=?B ?F, 又因為根據(jù)式(1)以及ρ和σ的性質(zhì), 有[14]:

將式(6)代入式(4), 整理可得:

其中:

Miller 循環(huán)的主要內(nèi)容就是計算式(7)中的系數(shù). 在式(7)中我們可以發(fā)現(xiàn)多個重復出現(xiàn)的因子, 在計算時可以充分利用減少運算量和數(shù)據(jù)傳輸.

進行硬件數(shù)據(jù)通路設(shè)計時, 考慮到上述計算方案中乘法運算之間存在一些數(shù)據(jù)依賴關(guān)系, 最多可以有6 個GF(3m) 乘法同時運算, 所以將18 次乘法運算分成三組, 每組用6 個模乘器并行進行計算. 經(jīng)過調(diào)度優(yōu)化, 式(5)和式(7)的計算過程可以分解為3 個“相位”, 完成6 次乘法, 如表1所示.

表1 Miller 循環(huán)的乘法調(diào)度Table 1 Multiplication scheduling of Miller’s loop

表1 的調(diào)度方案, 包括計算參數(shù)k和u的兩次乘法在內(nèi), 一次Miller 循環(huán)需要18 次GF(3m) 乘法、23 次GF(3m) 加法以及10 次GF(3m) 的立方. 相對于Beuchat 等人[15]的方案——14 次GF(3m) 的乘法、58 次GF(3m) 的加法和10 次GF(3m) 的立方, 本文方案雖然增加了4 次乘法, 但把加法次數(shù)減少了一半以上.

從上述的調(diào)度可以看出, 在每一輪模乘運算中, 第2–5 個MSE 模乘器都有一個相同的操作數(shù), 因此在硬件實現(xiàn)的時候, 這4 個模乘器可以共享一個移位寄存器單元, 從而減少了寄存器的使用. 同時, 這4個模乘器每一個相位的另一個操作數(shù)保持不變——除了相位3 中有2 個操作數(shù)需要被替換, 這樣也大大減少了寄存器的刷新次數(shù)和存儲器的讀寫, 可以降低寄存器翻轉(zhuǎn)引起的功耗. 根據(jù)以上方案, 我們就可以對Miller 算法進行硬件實現(xiàn).

4.3.2 Miller 算法單元

所設(shè)計的Miller 算法數(shù)據(jù)通路電路結(jié)構(gòu)如圖3 所示. 由坐標更新單元、模乘器陣列和參數(shù)計算單元三部分組成, 在控制器的控制下迭代運算. 每輪迭代的中間結(jié)果由兩個寄存器堆(RF1 和RF2) 保存, 寄存器堆的輸出反饋給模乘陣列用于迭代. 采用兩個寄存器堆可以提高數(shù)據(jù)讀寫的并行度.

圖3 Miller 算法硬件的數(shù)據(jù)通路結(jié)構(gòu)(μ=1, b=1)Figure 3 Datapath structure of Miller’s algorithm (μ=1 and b=1)

坐標更新單元是eta 對數(shù)據(jù)的輸入與更新模塊, 點P(xP,yP) 和Q(xQ,yQ) 的坐標從data_in 端口依次輸入, 分別存在4 個相應的寄存器中. 根據(jù)eta 對的算法,Q坐標在初始化以及每一輪Miller 循環(huán)中都需要進行立方運算, 所以坐標更新單元中用一個立方運算電路實時計算x3Q和y3Q, 加法器用于計算t=xQ+yQ, 并將操作數(shù)yP, yQ, t輸出給MSE 模乘器, 用于Miller 循環(huán)中的模乘運算.

第二部分是6 個模乘器組成的模乘器陣列, 完成GF(36m)稀疏乘法, 是整個設(shè)計的主要部分. 其中的6 個MSE 模乘器在每個相位所執(zhí)行的運算如表1 所示. 其中u,k和t是多個乘法的輸入數(shù)據(jù), 使用R0, R1 和R2 三個移位寄存器存儲, 因為操作數(shù)相同, MSE2–MSE5共享R2 輸入寄存器, 這減少了3 個2m比特寄存器. 由于存儲器的讀寫帶寬存在限制, 每一相位的并發(fā)模乘運算的輸入和輸出必須分時進行,每一輪的6 次模乘運算不是同時開始而是從左到右依次開始的, 在操作數(shù)載入以及結(jié)果輸出時以類似于流水線的方式運行. 相應地, 在MSE3–MSE5的輸入端路徑上插入了3 級2D比特的延遲寄存器, 把同一個操作數(shù)從左到右依次傳遞給3 個模乘器, 減少了存儲器的訪問. 模乘運算的結(jié)果經(jīng)過多路選擇器分時輸出.

參數(shù)計算單元計算r0–r5與中間項A–F. 首先RF1 和加法器構(gòu)成了一個累加結(jié)構(gòu), 對模乘運算的結(jié)果做累加, 用于計算r0–r5(式(7)). 其次, 在一輪運算完成后, 也就是r0–r5依次計算完成時, 繼續(xù)進行立方累加(由其中的立方-加法單元(圖中用x3+y表示) 完成), 得到中間項A–F并且在把結(jié)果存入RF2中的同時直接旁路給模乘器進行下一輪的Miller 循環(huán)運算.

上述調(diào)度方案允許實時計算和更新操作數(shù), 節(jié)省了等待數(shù)據(jù)和訪問存儲器的時間.

表2 Miller 算法硬件調(diào)度表Table 2 Computation procedure of the i-th iteration in Miller’s algorithm

4.4 GF(36m)冪運算電路

算法1 中最終的GF(36m)冪運算采用了論文[20]中的算法, 其電路結(jié)構(gòu)如圖4 所示. 由于算法是一系列的串行運算, 包括GF(3m) 上的立方、加法和乘法, 因此, 為了減小面積, 硬件結(jié)構(gòu)中只配置了一個GF(3m) 上的模乘器和一個立方-加法單元執(zhí)行運算. 另有一個雙端口RAM 作為數(shù)據(jù)存儲器. 最終冪運算也是通過微指令進行控制. 冪運算步驟較多且是串行計算, 所以將冪運算的指令固化到ROM 中, 通過計數(shù)器產(chǎn)生相應指令的地址.

圖4 最終冪運算單元電路結(jié)構(gòu)Figure 4 Structure of final exponentiation unit

4.5 eta 對硬件加速器整體結(jié)構(gòu)

在上述Miller 算法單元和最終冪運算單元的基礎(chǔ)上實現(xiàn)的eta 對硬件加速器整體結(jié)構(gòu)如圖5 所示.Miller 算法單元和最終冪運算單元各自有分立的控制器, 二者之間存在一個交互信號, 當Miller 算法結(jié)束,就會觸發(fā)冪運算開始工作, 二者以流水線的方式工作.

圖5 eta 對硬件加速器整體結(jié)構(gòu)Figure 5 Top-level structure of proposed eta pairing accelerator

5 性能評估

我們以上述結(jié)構(gòu)實現(xiàn)了m= 97,D= 3 的三進制eta 對加速器, 能夠為IBE 提供相當于66 比特的AES 的安全性. 為了簡化模運算與立方運算, 選取了f(x) =x97+x12?1 做為運算中的不可約三項式.在該參數(shù)下, Miller 運算和最終冪運算分別需要4851 和3272 個周期. 使用Synopsys Design Compiler(DC), 和Synopsys IC Compiler (ICC) 完成了設(shè)計的綜合和版圖, 工藝為SMIC 90 nm 工藝. 所得的設(shè)計版圖如圖6 所示, 面積為650×650 μm2. 表3 列出了基于布局布線后時序分析和功耗仿真得到的設(shè)計參數(shù)對比情況, 所有對比設(shè)計都是GF(397)的eta 對ASIC 設(shè)計. 從表中數(shù)據(jù)可以發(fā)現(xiàn): 相比于Chung等人的全流水ASIC 設(shè)計[10], 本文設(shè)計盡管運算時間較長, 但是面積時間積降低了38.8%. 因此硬件實現(xiàn)效率更高, 且電路的功耗也低于對比設(shè)計, 更適合用于IoT 設(shè)備.

圖6 eta 對硬件加速器版圖Figure 6 Layout of proposed eta pairing accelerator

表3 GF(397) eta 對硬件加速器ASIC 性能對比示例Table 3 Performance comparison of GF(397) eta pairing accelerators

6 結(jié)論

本文設(shè)計了一個低開銷的三進制eta 對硬件加速器. 對Miller 循環(huán)中的運算進行整合后, 提取公共項、優(yōu)化調(diào)度、平衡乘法和加法運算的數(shù)量、充分共享中間結(jié)果, 以減少數(shù)據(jù)傳輸、暫存和存儲器訪問的數(shù)量. 頂層設(shè)計將Miller 算法和最終冪運算以流水線方式運行, 提高了整體的硬件效率, 實現(xiàn)了一個更加高效的雙線性對硬件加速器. 版圖后仿真結(jié)果表明, 該設(shè)計比現(xiàn)有相同功能的ASIC 的面積延時積減小了38.8%. 它更加適合物聯(lián)網(wǎng)等輕量級應用場景. 此外, 雖然由于SM9 算法基于的是素數(shù)域橢圓曲線和擴域上橢圓曲線上的雙線性對, 支持的雙線性對類型限于Weil 對、Tate 對、Ate 對、R-ate 對4 種[2], 本文設(shè)計無法直接用于SM9 算法的實現(xiàn), 但是Miller 算法的核心運算——切線函數(shù)的模冪-乘, 是一致的, 本文的設(shè)計思想——將模冪-乘運算進行整合優(yōu)化對于其它對的Miller 算法的優(yōu)化仍具有借鑒意義, 我們未來將探索SM9 算法的低高面積效率硬件設(shè)計.