面向雙線性對的 -FIOS模乘算法及其實現架構研究

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

（1.哈爾濱理工大學計算機科學與技術學院，黑龍江 哈爾濱 150080；2.哈爾濱理工大學電氣與電子工程學院，黑龍江 哈爾濱 150080；3.黑龍江省網絡空間研究中心，黑龍江 哈爾濱 150090）

0 引言

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

3) 基于所設計的模乘架構實現了雙線性對運算單元，并完成Optimal ate 對運算。

1 二次擴域運算

1.1 塔式擴域

雙線性對的定義為G1×G2→GT，即2 個加法循環群G1和G2映射到另一乘法循環群GT。同理，雙線性對在橢圓曲線中的應用是兩組橢圓曲線點群以線性關系映射到另一乘法群上，一般在有限素數域Fp內定義的橢圓曲線E 上構造雙線性對。雙線性對的計算過程復雜，采用不同種類的雙線性對可降低運算中的Miller 循環次數，從而提高雙線性對的計算效率。高階擴域映射到低階擴域能減少Miller 循環的運算量，塔式擴域實現了高階擴域與低階擴域的轉換。采用適用于雙線性對計算的參數曲線，可進一步提升雙線性對計算效率。其中，安全長度為128 位的BN 曲線上的Optimal ate 是目前計算雙線性對的最優方式，SM9 標識密碼算法也選擇以BN 曲線為基礎構造雙線性對。

1.2 二次擴域模乘

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

算法1并行的高基蒙哥馬利模乘運算

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

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

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

圖1 模乘算法的合并過程

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

算法2-FIOS 模乘算法

表1 模乘的乘加計算量比較

表1 模乘的乘加計算量比較

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

圖2 -FIOS2和 -FIOS3架構

通過對算法2步驟間的數據依賴關系進行分析，外循環的步驟5)和內循環的步驟8)可同時運行，并依次對其他步驟進行排序。通過對算法循環的排序提出適用于2 種架構的并行調度，圖3 是適用于-FIOS2架構的二路并行調度運行流程，以乘法位寬64 位為例，用于下256 位乘法運算。

圖3 適用于 -FIOS2架構的二路并行調度運行流程

圖4 適用于 -FIOS3架構的三路并行調度運行流程

4 仿真分析

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

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

表2 相關設計實現模乘性能對比

表2 相關設計實現模乘性能對比

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

圖5 雙線性對運算單元

表3 相關設計實現安全長度128 位的Optimal ate 性能對比

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

5 結束語