面向雙線性對的 -FIOS模乘算法及其實(shí)現(xiàn)架構(gòu)研究

姜占鵬，孫銘瑋，黃海，徐江，劉志偉，白瑞，方舟，曲家興

（1.哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080；2.哈爾濱理工大學(xué)電氣與電子工程學(xué)院，黑龍江 哈爾濱 150080；3.黑龍江省網(wǎng)絡(luò)空間研究中心，黑龍江 哈爾濱 150090）

0 引言

1984 年，為解決非對稱密碼體制的頻繁認(rèn)證問題，Shamir 提出了基于標(biāo)識(shí)的密碼體系[1]（IBC,identity-based cryptosystem）。IBC 簡化了傳統(tǒng)的公鑰基礎(chǔ)設(shè)施（PKI,public key infrastructure），使用戶不需要進(jìn)行證書的申請和驗(yàn)證，適用于群體用戶的通信。2016 年，國家密碼管理局發(fā)布SM9 標(biāo)識(shí)密碼算法，同年該密碼算法正式成為我國密碼算法的一項(xiàng)標(biāo)準(zhǔn)[2]。雙線性對被廣泛地應(yīng)用于構(gòu)建IBC，IBC 與傳統(tǒng)公鑰密碼RSA 和ECC的數(shù)學(xué)原理相比，雙線性對具有更復(fù)雜的數(shù)學(xué)結(jié)構(gòu)及運(yùn)算過程。因此，IBC的應(yīng)用問題受到雙線性對計(jì)算速度的限制。密碼學(xué)家提出多種類型雙線性對以提高性能，如ate[3]、R-ate[4]以及Optimal ate[5]等，其中Optimal ate是目前效率極高的雙線性對之一。Koblitz 和Menezes[6]提出了雙線性對友好域的概念，并構(gòu)造了塔式擴(kuò)域。不僅如此，密碼學(xué)者引入雙線性對友好曲線[7]概念，定義了參數(shù)化曲線，其中在Barreto-Naehrig（BN）曲線上的Optimal ate 對是實(shí)現(xiàn)雙線性對的最快方式之一[8]。

3) 基于所設(shè)計(jì)的模乘架構(gòu)實(shí)現(xiàn)了雙線性對運(yùn)算單元，并完成Optimal ate 對運(yùn)算。

1 二次擴(kuò)域運(yùn)算

1.1 塔式擴(kuò)域

雙線性對的定義為G1×G2→GT，即2 個(gè)加法循環(huán)群G1和G2映射到另一乘法循環(huán)群GT。同理，雙線性對在橢圓曲線中的應(yīng)用是兩組橢圓曲線點(diǎn)群以線性關(guān)系映射到另一乘法群上，一般在有限素?cái)?shù)域Fp內(nèi)定義的橢圓曲線E 上構(gòu)造雙線性對。雙線性對的計(jì)算過程復(fù)雜，采用不同種類的雙線性對可降低運(yùn)算中的Miller 循環(huán)次數(shù)，從而提高雙線性對的計(jì)算效率。高階擴(kuò)域映射到低階擴(kuò)域能減少M(fèi)iller 循環(huán)的運(yùn)算量，塔式擴(kuò)域?qū)崿F(xiàn)了高階擴(kuò)域與低階擴(kuò)域的轉(zhuǎn)換。采用適用于雙線性對計(jì)算的參數(shù)曲線，可進(jìn)一步提升雙線性對計(jì)算效率。其中，安全長度為128 位的BN 曲線上的Optimal ate 是目前計(jì)算雙線性對的最優(yōu)方式，SM9 標(biāo)識(shí)密碼算法也選擇以BN 曲線為基礎(chǔ)構(gòu)造雙線性對。

1.2 二次擴(kuò)域模乘

蒙哥馬利模乘算法通過移位操作代替除法來實(shí)現(xiàn)Fp乘法運(yùn)算如ABmodP，而乘法需要計(jì)算(AB+CD)modP形式的模乘。文獻(xiàn)[14]中先計(jì)算兩次Fp模乘，再對結(jié)果進(jìn)行模加減得到的模乘結(jié)果。該設(shè)計(jì)中對改進(jìn)的高基蒙哥馬利模乘算法[12]重新排序，減少了計(jì)算周期數(shù)。文獻(xiàn)[14]提出的并行的高基蒙哥馬利模乘運(yùn)算如算法1 所示。

算法1并行的高基蒙哥馬利模乘運(yùn)算

文獻(xiàn)[9]對商流水蒙哥馬利模乘進(jìn)行改進(jìn)，得到用于計(jì)算(AB+CD)modP形式模乘的C-MM（combined high-radix montgomery multiplication）算法。C-MM 算法的迭代過程如式(2)所示。

C-MM 算法利用商流水模乘的商值與約減過程中A,B無直接關(guān)系，在約減過程中增加乘積運(yùn)算項(xiàng)，從而實(shí)現(xiàn)(AB+CD)modP形式的運(yùn)算，最終可以直接運(yùn)算出下模乘的結(jié)果。

原始蒙哥馬利模乘算法的模約減輸入條件為0 ≤T=AB≤P2≤RP，其中A,B≤P，經(jīng)過模約減0≤T+mP≤RP+RP=2RP乘法需要計(jì)算(AB+CD)modP形式的模乘，在模運(yùn)算的基本運(yùn)算規(guī)律中(T1modP+T2modP)modP=(T1+T2)modP，通過該方式進(jìn)行模乘計(jì)算只需一次模運(yùn)算即可。本文將該運(yùn)算規(guī)律應(yīng)用在同F(xiàn)IOS模乘等價(jià)的高基蒙哥馬利模乘算法，通過對兩組模乘的模約減部分結(jié)合，提出一種二次擴(kuò)域細(xì)集成操作數(shù)掃描（-FIOS,quadratic extension field finely integrated operand scanning）模乘算法。合并過程如圖1 所示。

圖1 模乘算法的合并過程

合并過程中，模約減由兩次減為一次，減少了計(jì)算冗余量。模約減的輸入T1＜RP和T2＜RP合并后輸入范圍變?yōu)門=T1+T2＜ 2RP，經(jīng)過模約減后，因此最終減法的運(yùn)算條件由判斷P≤Z是否成立改為判斷2P≤Z或P≤Z＜2P是否成立，根據(jù)結(jié)果決定Z=Z-2P、Z=Z-P或Z=Z。通過該合并過程提高了下乘法運(yùn)算的并行度。-FIOS 模乘算法如算法2 所示。

算法2-FIOS 模乘算法

表1 模乘的乘加計(jì)算量比較

表1 模乘的乘加計(jì)算量比較

表1 中，n表示算法的循環(huán)周期數(shù)，若乘數(shù)的位寬為256 位而乘法單元的運(yùn)算位寬為64 位，則循環(huán)周期數(shù)為256÷64=4。據(jù)表1 中數(shù)據(jù)可知，-FIOS 算法計(jì)算模乘的乘法運(yùn)算量和加法運(yùn)算量均小于其他算法，有效降低了模乘所需的資源開銷。

圖2 -FIOS2和 -FIOS3架構(gòu)

通過對算法2步驟間的數(shù)據(jù)依賴關(guān)系進(jìn)行分析，外循環(huán)的步驟5)和內(nèi)循環(huán)的步驟8)可同時(shí)運(yùn)行，并依次對其他步驟進(jìn)行排序。通過對算法循環(huán)的排序提出適用于2 種架構(gòu)的并行調(diào)度，圖3 是適用于-FIOS2架構(gòu)的二路并行調(diào)度運(yùn)行流程，以乘法位寬64 位為例，用于下256 位乘法運(yùn)算。

圖3 適用于 -FIOS2架構(gòu)的二路并行調(diào)度運(yùn)行流程

圖4 適用于 -FIOS3架構(gòu)的三路并行調(diào)度運(yùn)行流程

4 仿真分析

本節(jié)采用Verilog 建模并使用ModelSim SE10.5進(jìn)行仿真和驗(yàn)證。模型包括乘法位寬為64、32 位的架構(gòu)，乘法位寬為64、32、16、8 位的-FIOS3架構(gòu)。文獻(xiàn)[14]中模乘單元數(shù)據(jù)是本文通過實(shí)驗(yàn)得到的結(jié)果，實(shí)驗(yàn)環(huán)境與本文設(shè)計(jì)一致，采用TSMC 55 nm 工藝庫進(jìn)行綜合。相關(guān)設(shè)計(jì)均實(shí)現(xiàn)了下的256 位模乘，性能對比如表2 所示。

由于本文實(shí)現(xiàn)了多種乘法位寬的模乘架構(gòu)以及與其他文獻(xiàn)使用的工藝庫不同，表2 中的AT 是等效門數(shù)與單次模乘時(shí)間的乘積。AT 可綜合時(shí)鐘頻率、周期和等效門數(shù)三者對實(shí)現(xiàn)結(jié)果進(jìn)行對比，AT 值越低表示性能越高。本文設(shè)計(jì)的AT 值均較低，尤其是乘法位寬為64 位的設(shè)計(jì)均低于其他設(shè)計(jì)。其中乘法位寬越短，周期增長幅度越大，AT 值較高，性能略低。因此，使用乘法位寬為64 位的計(jì)算下的256 位模乘更適合，其中-FIOS2架構(gòu)在硬件資源消耗上更少。-FIOS3架構(gòu)在硬件資源上消耗較前者多一些，周期數(shù)較小，計(jì)算所需時(shí)間更短，AT 值更低，達(dá)到綜合性能上的最優(yōu)。通過分析表2，當(dāng)使用-FIOS 實(shí)現(xiàn)模乘時(shí)，-FIOS2架構(gòu)適用于面積受限的情況，-FIOS3架構(gòu)適用于速度更快的情況。

表2 相關(guān)設(shè)計(jì)實(shí)現(xiàn)模乘性能對比

表2 相關(guān)設(shè)計(jì)實(shí)現(xiàn)模乘性能對比

仿真結(jié)果表明，本文設(shè)計(jì)的2 種模乘架構(gòu)具有高性能。以乘法位寬為64 位的2 種架構(gòu)為代表，通過單次模乘計(jì)算所需時(shí)間和硬件資源消耗對比，本文設(shè)計(jì)均低于其他文獻(xiàn)。其中，文獻(xiàn)[10]中C-MM模乘不適用于短乘法位寬，處理器中的乘法運(yùn)算為53×320 bit，計(jì)算需18 個(gè)周期。模乘計(jì)算結(jié)果位寬為320 位，需要額外的硬件資源進(jìn)行模約減運(yùn)算。本文的2 種架構(gòu)可用于多種乘法位寬，當(dāng)乘法運(yùn)算為64×64 bit 時(shí)，計(jì)算周期數(shù)僅需31 個(gè)和24 個(gè)。同時(shí)模乘結(jié)果不需要額外的模約減，硬件資源消耗更低。文獻(xiàn)[11]的改進(jìn)算法支持參數(shù)在一定范圍可變，但計(jì)算需70 個(gè)周期，致使計(jì)算所需時(shí)間較長。本文設(shè)計(jì)的參數(shù)可為1、-1、0 和-2，在參數(shù)范圍內(nèi)的模乘計(jì)算速度遠(yuǎn)快于文獻(xiàn)[11]，并且該參數(shù)范圍適用于大部分IBC 方案，如滿足SM9的參數(shù)設(shè)定。文獻(xiàn)[14]采用2 個(gè)Fp模乘單元并行計(jì)算，通過對2 個(gè)Fp模乘的結(jié)果進(jìn)行模加減得到的模乘結(jié)果，該設(shè)計(jì)需要4 個(gè)64 位乘法器以及一個(gè)額外的模加減單元實(shí)現(xiàn)，計(jì)算下的256 位模乘，共需31 個(gè)周期。本文架構(gòu)在實(shí)現(xiàn)模乘時(shí)，-FIOS2只需2 個(gè)64 位乘法器以及31 個(gè)周期即可完成，需3 個(gè)64 位乘法器以及24 個(gè)周期，2 種架構(gòu)較文獻(xiàn)[14]不僅減少了硬件資源消耗，同時(shí)計(jì)算周期更具有優(yōu)勢。綜上所述，本文設(shè)計(jì)的模乘架構(gòu)不僅面積小，計(jì)算所需時(shí)間也低于其他設(shè)計(jì)，在的乘法計(jì)算上有較高提升。通過圖5 所設(shè)計(jì)的雙線性對運(yùn)算單元完成Optimal ate 對的計(jì)算，與其他相關(guān)設(shè)計(jì)的對比數(shù)據(jù)如表3 所示。

圖5 雙線性對運(yùn)算單元

表3 相關(guān)設(shè)計(jì)實(shí)現(xiàn)安全長度128 位的Optimal ate 性能對比

仿真參數(shù)采用SM9 標(biāo)準(zhǔn)，仿真結(jié)果表明，使用本文設(shè)計(jì)的模乘架構(gòu)實(shí)現(xiàn)的雙線性對運(yùn)算單元能快速計(jì)算出Optimal ate 對的結(jié)果。該結(jié)果得益于模乘在Optimal ate的運(yùn)算量占比較高，本文設(shè)計(jì)采用4 個(gè)-FIOS3架構(gòu)并行執(zhí)行來完成模乘，可在一定程度上減少運(yùn)算所需時(shí)鐘周期數(shù)。相較于其他設(shè)計(jì)，如文獻(xiàn)[10]雖然提高了模乘的運(yùn)算速度，但未對雙線性對運(yùn)算做完整的并行排序，使運(yùn)算周期數(shù)過多導(dǎo)致計(jì)算時(shí)間并不理想。文獻(xiàn)[14]對雙線性對運(yùn)算過程進(jìn)行了詳細(xì)的并行排序，但設(shè)計(jì)的運(yùn)算單元沒有完全發(fā)揮出基本運(yùn)算域運(yùn)算的并行度。文獻(xiàn)[15]同樣使用并行單元運(yùn)算，但對雙線性對運(yùn)算過程的并行性利用不充分導(dǎo)致計(jì)算周期過多。文獻(xiàn)[16]對參數(shù)固定的多項(xiàng)式模乘設(shè)計(jì)了專用的處理器，但不能用于其他參數(shù)，不具備通用性。文獻(xiàn)[17]提出的可編程的SoC 平臺(tái)可用于多種雙線性對計(jì)算，但在Optimal ate 對運(yùn)算上較慢。文獻(xiàn)[18]采用輕量級方式實(shí)現(xiàn)，消耗硬件資源較低，但運(yùn)算周期過多導(dǎo)致計(jì)算時(shí)間較長。綜上所述，本文設(shè)計(jì)的-FIOS3架構(gòu)所實(shí)現(xiàn)的雙線性對運(yùn)算單元可在較短周期內(nèi)計(jì)算出相應(yīng)結(jié)果，且時(shí)鐘頻率較高，在計(jì)算時(shí)間上具有較大優(yōu)勢。

5 結(jié)束語