周朕，何德彪，羅敏，李莉

緊湊的Aigis-sig數(shù)字簽名方案軟硬件協(xié)同實現(xiàn)方法

周朕1,2，何德彪1,2，羅敏1,2，李莉1,2

（1.空天信息安全與可信計算教育部重點實驗室，湖北 武漢 430072； 2.武漢大學(xué)國家網(wǎng)絡(luò)安全學(xué)院，湖北 武漢 430072）

基于理想格構(gòu)造的Aigis-sig數(shù)字簽名方案具有實現(xiàn)效率高、簽名長度短、抗量子攻擊等優(yōu)勢。針對Aigis-sig方案，構(gòu)造了一種改進的模乘計算元件，設(shè)計了一種基于快速數(shù)論變換（NTT）算法實現(xiàn)環(huán)上多項式運算的緊湊硬件架構(gòu)；同時以此架構(gòu)為基礎(chǔ)，提出了Aigis-sig數(shù)字簽名方案的FPGA軟硬件協(xié)同實現(xiàn)方法。實驗表明，在Xilinx Zynq-7000 SoC平臺上，CPU頻率和硬件頻率分別設(shè)置為666.66MHz和150MHz時，該實現(xiàn)方案相較于純軟件實現(xiàn)，簽名階段和驗簽階段分別取得約26%和17%的性能提升。

后量子密碼；數(shù)字簽名；Aigis-sig；現(xiàn)場可編程邏輯門陣列；快速數(shù)論變換

1 引言

隨著量子計算技術(shù)的不斷發(fā)展與成熟，量子研究學(xué)者對可實用量子計算機的研制不斷取得突破性的進展[1]。量子計算機在帶給人們強大算力的同時，也對基于大整數(shù)分解、離散對數(shù)問題的傳統(tǒng)公鑰密碼體系構(gòu)成了一定的威脅。Shor等[2]提出了可以在多項式時間內(nèi)破解大整數(shù)分解問題和離散對數(shù)問題的量子算法，一旦足夠成熟的量子計算機研制成功并投入使用，傳統(tǒng)的密碼體系將不再能提供安全性保障。因此，學(xué)者對新興的后量子密碼產(chǎn)生了濃厚興趣，并積極研究如何構(gòu)造高效安全可實用的后量子密碼方案。

作為公認可以抵抗量子計算機攻擊的一類密碼算法——后量子密碼的研發(fā)是密碼學(xué)者應(yīng)對量子計算威脅的防范措施之一[3]。主流的后量子密碼算法主要包括：格密碼、編碼密碼、哈希密碼、多變量密碼。2012年，美國國家標(biāo)準(zhǔn)技術(shù)研究所（NIST，National Institute of Standards and Technology）正式啟動了后量子密碼的研究工作，并于2016年開展全球范圍內(nèi)的后量子密碼算法標(biāo)準(zhǔn)的征集和篩選[4-6]。截至2020年7月，NIST已經(jīng)完成了3輪的篩選工作，并確定了7個最終方案和8個候選方案，預(yù)計近幾年將最終確認新一代公鑰密碼算法標(biāo)準(zhǔn)?；诟竦拿艽a方案是研究熱度較高的后量子密碼體系之一，這主要是由于格密碼具有實現(xiàn)效率高、密鑰長度較短、允許最壞情況困難假設(shè)等優(yōu)點，除此之外，基于格的密碼方案在同態(tài)加密技術(shù)領(lǐng)域極具研究價值，可以真正意義上支持全同態(tài)的加密算法均為格密碼方案。在NIST后量子密碼標(biāo)準(zhǔn)化進程第3輪的7個最終方案中，有5個方案都屬于格密碼體系。 2019年，中國密碼學(xué)會舉辦了全國密碼算法設(shè)計競賽[7-8]，公鑰密碼組的參賽方案中包含大量的后量子密碼方案，其中基于格的參賽密碼方案占據(jù)了一定的比例，如Aigis-sig/enc、LAC.PKE/KEX、AKCN、Fatseal等[7]。

在基于格的密碼體系中，錯誤學(xué)習(xí)問題（LWE，learning with error）[9]和小整數(shù)解問題（SIS，short integer solution）[10]是密碼學(xué)者構(gòu)造方案時經(jīng)常涉及和使用的數(shù)學(xué)困難問題。除此之外，兩類困難問題在環(huán)上（RLWE/RSIS，ring-LWE/ ring-SIS）和模格上（MLWE/MSIS，module-LWE/ module-SIS）的版本也受到密碼學(xué)者們的廣泛關(guān)注，其主要原因是理想格具備一些標(biāo)準(zhǔn)格所不具備的額外代數(shù)結(jié)構(gòu)和代數(shù)特性，更準(zhǔn)確地說，以特定多項式環(huán)上的多項式乘法代替大維數(shù)的矩陣或向量乘法，可以使環(huán)或模格上所構(gòu)造的密碼方案能夠通過一定的算法技巧實現(xiàn)極大程度的性能改進[11]。在2019年全國密碼算法設(shè)計競賽的眾多方案中，如Aigis-sig/enc，LAC.PKE/KEX，AKCN等獲得優(yōu)秀名次的參賽方案都是在環(huán)或模格結(jié)構(gòu)基礎(chǔ)之上所提出的格密碼方案[8]。然而，關(guān)于這些優(yōu)秀方案在不同平臺上的高性能實現(xiàn)方面的研究工作非常少。

本文的主要研究目標(biāo)在于針對Aigis-sig方案[12]提出FPGA平臺上緊湊高效的軟硬件協(xié)同實現(xiàn)方法，該實現(xiàn)方案中的核心工作是構(gòu)造出一種針對Aigis-sig方案參數(shù)選擇的多項式運算硬件實現(xiàn)架構(gòu)。實驗表明，CPU頻率和硬件頻率分別設(shè)置為666.66 MHz和150 MHz時，本文的實現(xiàn)方法相較于同F(xiàn)PGA平臺下的純軟件實現(xiàn)在簽名和驗簽方面分別有26%和17%的提升。

2 研究現(xiàn)狀

基于格的密碼體系是近幾年發(fā)展較為迅速、理論較為成熟的后量子密碼體系之一，同時，針對格密碼方案的安全快速實現(xiàn)也是后量子密碼研究人員的關(guān)注點之一[13]。對于理想格上密碼方案的高性能實現(xiàn)，研究者的關(guān)注點主要集中于多項式乘法的快速實現(xiàn)、特定噪聲分布的安全實現(xiàn)、高速哈希函數(shù)實現(xiàn)等方面。其中針對多項式乘法，在特定環(huán)上可以采用快速數(shù)論變換（NTT，number theoretic transform）方法從算法層面上大幅提升性能。

在軟件實現(xiàn)方面，2015年，De C等[14]提出了一種ARM Cortex-M4F微處理器平臺上基于RLWE公鑰加密方案的快速軟件實現(xiàn)方法；2016年，Yuan等[15]提出了一種格密碼方案的可移植JavaScript實現(xiàn)，該實現(xiàn)方法可以應(yīng)用于網(wǎng)頁瀏覽器、安卓系統(tǒng)；同年，Stebila等[16]設(shè)計了一個名為“開源量子安全”的軟件平臺，該平臺不僅內(nèi)置了許多格密碼方案的C語言實現(xiàn)，同時還具備將軟件實現(xiàn)整合到實際產(chǎn)品中的功能。

在開源庫方面，NFLlib是針對理想格上多項式運算快速實現(xiàn)的函數(shù)庫之一[17]，該庫基于C++語言開發(fā)，并且還在不斷地完善；除此之外，微軟公司研發(fā)了針對格上BFV和CKKS全同態(tài)加密方案的函數(shù)庫SEAL[18]，同樣基于C++語言。

在硬件實現(xiàn)方面，G?ttert等[19]于2012年提出了Virtex-7平臺上RLWE加密方案的硬件實現(xiàn)，該硬件架構(gòu)實現(xiàn)了相當(dāng)大的數(shù)據(jù)吞吐量，其運算可以達到數(shù)百倍于相應(yīng)軟件實現(xiàn)的運算速度，同時占用了較大的面積資源；2014年，P?ppelmann等[20]在Spartan-6和Virtex-5系列平臺上設(shè)計了一種輕量級格密碼硬件實現(xiàn)引擎，該架構(gòu)的面積資源消耗非常低，因此在資源較少的嵌入式平臺上有很強的應(yīng)用價值；針對NTT算法，Roy等[21]在2014年設(shè)計了一個非常緊湊的硬件協(xié)處理器，該工作對后續(xù)許多針對NTT的硬件實現(xiàn)均具有啟發(fā)性的指導(dǎo)作用。2019年，Basu等[22]針對NIST第二輪候選方案中的大量后量子方案進行了基于高層次綜合（HLS）方法的硬件實現(xiàn)測試，并提供了性能對比結(jié)果；同年，Dang等[23]針對提交到NIST的FrodoKEM、Round5、Saber 3個密鑰封裝方案提出了軟硬件協(xié)同實現(xiàn)方法，與純軟件實現(xiàn)相比，性能大幅提升；Banerjee等[24]設(shè)計了針對許多格密碼方案的可配置協(xié)處理器Sapphier，該協(xié)處理器可以高效完成多項式乘法運算與噪聲采樣任務(wù)；2020年，Xin等[25]提供了特定域上的向量化處理器，可以支持并行NTT算法和向量式的噪聲采樣，其性能在Sapphier的基礎(chǔ)上提高了一個數(shù)量級。

3 背景知識

本節(jié)將對Aigis-sig中涉及的相關(guān)數(shù)學(xué)定義、重要算法以及簽名方案流程等進行簡單介紹。

3.1 符號定義

文中主要使用的數(shù)字符號及其定義如下。

3.2 多項式環(huán)上的加法與乘法

3.3 快速數(shù)論變換

算法1 正向NTT算法

2) for=2 to,=2

4) for=0 to/2?1,=+1

5) for=0 to?1,=+

8) end for

10) end for

11) end for

算法2 反向NTT算法

1) for=to 2,=/2

3) for=0 to/2?1,=+1

4) for=0 to?1,=+

7) end for

9) end for

10) end for

3.4 Aigis-sig數(shù)字簽名方案

本文中所實現(xiàn)的方案Aigis-sig為Schnorr簽名在格密碼上的延伸。本文主要研究Aigis-sig方案在推薦參數(shù)組PARAMS-Ⅱ下的實現(xiàn)，下面給出Aigis-sig方案簡略的流程，更詳細的方案介紹可參考官方設(shè)計文檔[12]。參數(shù)組PARAMS-Ⅱ的部分參數(shù)如表1所示。

表1 參數(shù)組PARAMS-Ⅱ的部分參數(shù)

密鑰生成算法如下所示。

算法3 密鑰生成算法

輸出 公鑰pk，私鑰sk

算法4 簽名算法

輸入 私鑰sk，消息

驗簽算法如下所示。

算法5 驗簽算法

輸出 簽名驗證結(jié)果{合法，不合法}

7) 輸出簽名合法

4 算法設(shè)計

本節(jié)將對本文所使用的關(guān)鍵算法以及相應(yīng)的設(shè)計優(yōu)化進行介紹。

4.1 模乘

在Aigis-sig方案中，多項式乘法在整體計算開銷中占據(jù)了相當(dāng)大的比重，而Z上的模乘運算是多項式乘法中的重要運算單元，因此，根據(jù)硬件的實現(xiàn)特性，對模乘運算進行算法層面上的優(yōu)化對提高整個簽名方案的實現(xiàn)性能極具幫助。模乘運算可以分為標(biāo)準(zhǔn)數(shù)乘和模約減兩個階段，在本文中，標(biāo)準(zhǔn)數(shù)乘所對應(yīng)的比特長度為22，利用模數(shù)(=3 870 721)本身的比特分布特點和數(shù)學(xué)性質(zhì)，設(shè)計了一種針對該模數(shù)的改進模乘算法。

對于FPGA上的硬件實現(xiàn)而言，數(shù)乘是通過調(diào)用平臺內(nèi)置DSP資源中的乘法器來完成的，而乘法器的比特長度是固定的，對于超過乘法器長度的乘法任務(wù)可以通過多個乘法器拼接的方式來實現(xiàn)，但這意味著額外的乘法器用量以及過長的硬件路徑。然而通過采用Karastuba乘法算法，不僅可以從算法層面減少數(shù)乘所需要的乘法器數(shù)量，而且通過流水線設(shè)計，可以將硬件路徑拆分，從而增大硬件模塊所能承受的最大頻率。本文通過采取兩段式的Karastuba算法來實現(xiàn)硬件上的標(biāo)準(zhǔn)數(shù)乘，具體算法如下。

算法6 標(biāo)準(zhǔn)數(shù)乘算法

通過除法確定商的方式來完成模約減，運算復(fù)雜度是除數(shù)長度的立方級，因此在實現(xiàn)模約減階段時，通常采用Barret、Montgomery等快速約減算法。這兩種算法會涉及與固定常數(shù)相乘的運算操作，對于形式特殊的常數(shù)，甚至可以不通過乘法運算而僅通過加法和移位等簡單操作獲得正確結(jié)果。本文通過分析模數(shù)自身的特性，采用Montgomery算法來實現(xiàn)模約減階段，如算法7所示。

算法7 Montgomery約減算法

4.2 多項式乘法

算法8 本文設(shè)計的正向NTT算法

3) for r=2 to,=2

6) for=0 to?1,=+2

13) end for

15) end for

16) end for

算法9 本文設(shè)計的反向NTT算法

1) for=to 2,=/2

3) for=0 to/2?1,=+1

4) for=0 to?1,=+2

11) end for

13) end for

14) end for

5 硬件架構(gòu)設(shè)計

本節(jié)主要介紹本文設(shè)計的基于NTT算法的多項式乘法硬件架構(gòu)，其主要包括各個硬件組件的設(shè)計、功能、組件之間的連接方式以及該硬件架構(gòu)的調(diào)用方法。

5.1 硬件模塊

（1）地址生成模塊

該模塊主要負責(zé)生成硬件架構(gòu)工作時，RAM的讀地址、寫地址序列以及相對應(yīng)的使能信號序列。

（2）旋轉(zhuǎn)因子生成模塊

該模塊主要負責(zé)生成架構(gòu)在進行NTT算法時所需要的旋轉(zhuǎn)因子序列。

（3）運算模塊

該模塊主要負責(zé)完成架構(gòu)工作時待處理數(shù)據(jù)所需進行的模加、模減、模乘運算以及數(shù)據(jù)對的調(diào)整。

（4）驅(qū)動信號分流模塊

該模塊主要負責(zé)將總線的驅(qū)動信號通過連續(xù)寄存的方式分流成其余各模塊需要的驅(qū)動信號，以校正各模塊驅(qū)動信號的時鐘差。

5.2 地址序列生成

圖1 地址生成方式圖解

Figure 1 Diagram of address generation

5.3 算數(shù)模塊

在本文的硬件架構(gòu)中，算數(shù)模塊主要負責(zé)完成NTT算法中的蝶形運算以及多項式的逐點乘法和逐點加法，對于NTT算法，該模塊還同時承擔(dān)了數(shù)據(jù)對重排的作用。架構(gòu)中的模乘元件是其中比較重要的元件，如3.1節(jié)所述，本架構(gòu)中的模乘是通過標(biāo)準(zhǔn)數(shù)乘與特殊模數(shù)下的Montgomery約減所實現(xiàn)的，但為了進一步提升硬件架構(gòu)的性能，額外地使用了一些微妙的流水線設(shè)計技巧，流水線級數(shù)為6。本架構(gòu)中流水線模乘算法如下所示。

算法10 流水線模乘算法

//第一級

//第二級

//第三級

//第四級

//第五級

//第六級

圖2 NTT數(shù)據(jù)流向?qū)嵗?/p>

Figure 2 An instance of data flow instance

5.4 旋轉(zhuǎn)因子生成元件

圖3 旋轉(zhuǎn)因子生成部分過程（正向階段5）

Figure 3 Partial process of twiddle factor generation (forward stage 5)

表2 正向與反向NTT各階段所需的旋轉(zhuǎn)因子

5.5 整體架構(gòu)

在本文中，各個硬件模塊組合成完整的硬件架構(gòu)之后通過總線協(xié)議與平臺上內(nèi)置的CPU軟核相連接，與之共同完成Aigis-sig方案的軟硬件協(xié)同實現(xiàn)。本文的整體硬件架構(gòu)如圖4所示。

CPU與硬件部分通過總線通信，傳遞內(nèi)容主要有兩種：一是通過總線將待處理多項式系數(shù)數(shù)據(jù)寫入硬件的RAM中以及將RAM中經(jīng)過處理的系數(shù)數(shù)據(jù)讀出；二是通過總線向硬件發(fā)送相應(yīng)的驅(qū)動信號以及監(jiān)聽硬件部分拋出的完成信號。架構(gòu)中的地址生成模塊、旋轉(zhuǎn)因子生成模塊以及算數(shù)模塊均包含有限狀態(tài)機（FSM），但均僅包含“空閑”和“工作”兩種狀態(tài)，當(dāng)接收到相應(yīng)的開始驅(qū)動信號時，模塊從“空閑”進入“工作”狀態(tài)，完成相應(yīng)任務(wù)，完成之后將自動切換回“空閑”狀態(tài)，并由地址生成模塊負責(zé)產(chǎn)生完成信號。由于3個FSM之間開始工作的時鐘周期存在一定偏差，因此需要驅(qū)動信號分流模塊將總開始信號按照校正值分流出3個開始信號來保證各模塊間的正常運行。

圖4 整體硬件架構(gòu)

Figure 4 Overall hardware architecture

5.6 架構(gòu)功能與調(diào)用方式

本文的硬件架構(gòu)中的RAM可以同時存儲4個多項式，分別記為0號、1號、2號、3號位，架構(gòu)可以完成的所有操作指令主要有以下6種。

（1）寫多項式：向硬件模塊的0號、1號、 2號、3號寫入多項式。

（2）讀多項式：從硬件模塊的0號、1號、 2號、3號讀出多項式。

（3）正向NTT：0號、1號多項式進行正向NTT操作。

（4）反向NTT：2號、3號多項式進行反向NTT操作。

（5）逐點相乘：0號多項式與1號多項式逐點相乘之后存入2號多項式位。

（6）逐點相加：2號多項式與3號多項式逐點相加之后存入3號多項式位。

算法11 多項式向量內(nèi)積算法

1) 3號多項式位清零

2) for=0 to 3,=+1:

5) 對0號多項式進行正向NTT

6) 對1號多項式進行正向NTT

7) 執(zhí)行逐點相乘

8) 執(zhí)行逐點相加

9) end for

10) 對3號多項式進行反向NTT

11) 將3號多項式讀出賦值給

12) 將多項式寫入0號位

13) 將多項式寫入1號位

14) 執(zhí)行逐點相乘

15) 將2號多項式讀出賦值給

然而，在具體實現(xiàn)Aigis-sig方案中的多項式運算時，并不需要嚴(yán)格按照最完整的過程執(zhí)行所有步驟。例如，矩陣的行向量作為多項式向量內(nèi)積運算輸入之一，依照方案，該矩陣為隨機矩陣，因而可以直接視為NTT表達形式，不需要額外的正向NTT變換；又如矩陣與向量進行乘法運算時，需要計算次內(nèi)積，但向量是公共的，因此不需要對其重復(fù)執(zhí)行正向NTT變換。

6 軟硬協(xié)同實現(xiàn)

6.1 軟件實現(xiàn)

在本文所描述的實現(xiàn)方法中，軟件部分所使用的C語言程序代碼是Aigis-sig方案設(shè)計團隊在全國密碼算法設(shè)計競賽中所提交的參考實現(xiàn)代碼的基礎(chǔ)上修改而來的[12]，代碼的修改主要是將一些本文的實驗平臺所不支持的數(shù)據(jù)結(jié)構(gòu)、函數(shù)指令以及外源依賴庫等全部替換為平臺支持且邏輯完全相同的功能實現(xiàn)。修改之后的C程序代碼即本文在實驗階段用于性能對比的純軟件實現(xiàn)代碼。

6.2 協(xié)同實現(xiàn)

本文所提出的軟硬件協(xié)同實現(xiàn)方法本質(zhì)上是將純軟件實現(xiàn)中涉及多項式運算的部分由軟件CPU實現(xiàn)轉(zhuǎn)化為硬件架構(gòu)實現(xiàn)。平臺內(nèi)置的CPU為主設(shè)備，硬件架構(gòu)為從設(shè)備，軟件部分由CPU獨自實現(xiàn)，硬件部分則是CPU通過相應(yīng)的總線協(xié)議，將待處理數(shù)據(jù)以及處理指令傳送給硬件架構(gòu)，從而調(diào)用其完成相應(yīng)的邏輯功能，再將處理完的數(shù)據(jù)返還給CPU。圖5為純軟件實現(xiàn)與軟硬件協(xié)同實現(xiàn)的簡單說明。

圖5 純軟件實現(xiàn)與軟硬件協(xié)同實現(xiàn)

Figure 5 Software-only implementation and software/hardware cooperative implementation

7 實驗

7.1 平臺及測試方法

為了更客觀地評估本文所提出的實現(xiàn)方案的性能，采用與同一平臺上的純軟件實現(xiàn)進行對比的方式展示相關(guān)數(shù)據(jù)。本文所使用的FPGA平臺為Xilinx Zynq 7000 Soc XC7Z020-2CLG400I，內(nèi)置PS端Cortex-A9 ARM 處理器與PL端Artix-7架構(gòu)可編程邏輯資源，軟件與硬件（PS端與PL端）之間采用AXI總線協(xié)議傳遞相關(guān)數(shù)據(jù)。本文的對比實驗包括NTT算法和簽名、驗簽兩個層面，針對NTT算法的性能評估，本文提供一些已存在且性能較優(yōu)的硬件設(shè)計的相關(guān)數(shù)據(jù)，并從硬件面積和時鐘周期消耗數(shù)兩個方面進行比較。

7.2 多項式運算性能

對Aigis-sig方案的實現(xiàn)而言，環(huán)上多項式乘法的實現(xiàn)效率很大程度上影響整個方案的性能。本文利用NTT算法實現(xiàn)多項式相乘是硬件架構(gòu)主要實現(xiàn)的功能之一。表3給出了本架構(gòu)的硬件部分在本文實驗平臺的邏輯資源消耗、時鐘周期、最大頻率等數(shù)據(jù)，其中資源消耗指標(biāo)包括查找表（LUT）、數(shù)字信號處理器（DSP）、塊存儲器（Bram），同時給出一些具有對比價值的設(shè)計成果用于參照。

表3的數(shù)據(jù)表明，與Roy等在文獻[21]中的設(shè)計相比，本文的架構(gòu)消耗了更多的DSP和LUT資源，最大頻率則大約是文獻[21]的50%～60%，這主要是模數(shù)7 681和12 289的比特長度較短，模乘本身復(fù)雜度就低，然而本文的架構(gòu)可以在更少的時鐘周期內(nèi)完成256次多項式的NTT算法。Feng等在文獻[26]中給出的硬件設(shè)計其所需的時鐘周期僅為工作的20%，然而本文的架構(gòu)所消耗的LUT資源僅相當(dāng)于文獻[26]的10%左右，對于資源受限的應(yīng)用設(shè)備，本文的硬件架構(gòu)設(shè)備更具優(yōu)勢。模數(shù)僅在Aigis-sig方案中出現(xiàn)，因此目前還沒有模數(shù)相同，更具有公平參照價值的現(xiàn)有研究成果用作對比。

在密碼算法方案的軟硬件協(xié)同實現(xiàn)方法中，硬件模塊執(zhí)行相關(guān)運算的時間消耗即便是在低時鐘頻率驅(qū)動的前提下一般也是非常低的，遠小于將軟核內(nèi)的待處理數(shù)據(jù)通信傳輸?shù)接布K，或?qū)⒂布K中的結(jié)果數(shù)據(jù)返還給CPU軟核所消耗的時間，表4給出了本文的實驗測試結(jié)果，可以看出NTT算法硬件執(zhí)行時間僅占總消耗時間的6.2%左右。正是出于這個原因，本文的實驗架構(gòu)中才選擇加入了逐點乘和逐點累加的功能，這種方法使在計算多項式向量內(nèi)積操作時可以節(jié)約通信次數(shù)，從而提高實現(xiàn)的時間性能。

表3 NTT性能對比（多項式長度n=256）

注：“—”表示無法獲得。

表4 總線通信性能

7.3 數(shù)字簽名性能

本文所實現(xiàn)的Aigis-sig方案的參數(shù)組為PARAMS Ⅱ，該組參數(shù)為推薦參數(shù)。表5、表6分別給出了在本文的FPGA平臺上，不同的實現(xiàn)方法中簽名階段和驗簽階段在本架構(gòu)上實現(xiàn)的時間消耗。除此之外，為了說明本文的硬件架構(gòu)對方案性能提升的程度，本文也給出了在FPGA平臺上純ARM核實現(xiàn)的時間消耗結(jié)果。實驗測試中，軟硬件協(xié)同實現(xiàn)和純軟件實現(xiàn)的CPU軟核頻率設(shè)置均為666.66 MHz，該設(shè)置為本文所使用的開發(fā)板推薦的默認設(shè)置，同時也是保證程序?qū)崿F(xiàn)正常運行的最大頻率。在表3中已說明本文的硬件模塊正常運行的最大時鐘頻率為168MHz，因此將硬件架構(gòu)的時鐘頻率設(shè)置為150MHz，即不超過最大頻率前提下，便于平臺晶振準(zhǔn)確生成的最大頻率。

表5 簽名階段性能

表6 驗證階段性能

由表5和表6可知，CPU頻率和硬件頻率分別設(shè)置為666.66 MHz和150 MHz時，本文設(shè)計的硬件架構(gòu)設(shè)計的引入最終使Aigis-sig方案的性能在簽名階段和驗簽階段，相較于同樣平臺下的純ARM核軟件實現(xiàn)，分別取得約26.93%和17.08%的提升。在本文之前尚未有Aigis-sig方案在嵌入式平臺上實現(xiàn)的相關(guān)工作發(fā)表和展開，因此沒有對比數(shù)據(jù)，然而單從FF、LUT、DSP、Bram消耗量上來看，本文實現(xiàn)的資源消耗是很少的。

8 結(jié)束語

基于理想格構(gòu)造的密碼方案的快速實現(xiàn)在量子計算機不斷發(fā)展的時代背景下具有強大的研究價值和應(yīng)用前景。本文基于Aigis-sig方案設(shè)計了一種多項式運算的緊湊硬件架構(gòu)，并以此為基礎(chǔ)，提出了FPGA平臺下Aigis-sig方案的軟硬件協(xié)同快速實現(xiàn)方法。實驗結(jié)果表明，在Xilinx Zynq-7000 SoC平臺上，CPU頻率和硬件頻率分別設(shè)置為666.66 MHz和150 MHz時，本實現(xiàn)方法使Aigis-sig的簽名階段和驗簽階段分別取得約26.93%和17.08%的性能提升。

[1] KELLY, J, BARENDS R, FOWLER A G, et al. State preservation by repetitive error detection in a superconducting quantum circuit[J]. Nature, 2015, 519(7541): 66-69.

[2] SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303 -332.

[3] 楊妍玲. 后量子密碼在信息安全中的應(yīng)用與分析[J].信息與電腦(理論版), 2020, 32(8): 177-181.

YANG Y L. Application and analysis of post-quantum cryptography in information security[J]. Information and Computers (Theoretical), 2020, 32(8): 177-181.

[4] CHEN L, JORDAN S, LIU Y K, et al. Report on post-quantum cryptography[M]. Maryland: National Institute of Standards and Technology, 2016.

[5] ALAGIC G, ALPERIN-SHERIFF J, APON D, et al. Status report on the first round of the NIST post-quantum cryptography standardization process[M]. Maryland: National Institute of Standards and Technology, 2019.

[6] ROMA C A, TAI C A, HASAN M A. Energy consumption of round 2 submissions for NIST PQC standards[R]. Maryland: National Institute of Standards and Technology, 2019.

[7] 中國密碼學(xué)會. 全國密碼算法設(shè)計競賽進入第2輪公鑰算法[EB].

Chinese Association for Cryptologic Research. Public key scheme selected to the second-round competition of national cryptographic algorithm competition[EB].

[8] 中國密碼學(xué)會. 關(guān)于全國密碼算法設(shè)計競賽算法評選結(jié)果的公示[EB].

Chinese Association for Cryptologic Research. Announcement of the selection results of the national cryptographic algorithm competition[EB].

[9] REGEV O. On lattices, learning with errors, random linear codes, and Cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 1-40.

[10] AJTAI M. Generating hard instances of lattice problems[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing. 1996: 99-108.

[11] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings[J]. Journal of the ACM (JACM) 2013, 60(6): 1-35.

[12] 中國密碼學(xué)會. 數(shù)字簽名方案Aigis-sig算法提交文檔[EB]. Chinese Association for Cryptologic Research. Submitted document of the digital signature scheme Aigis-sig [EB].

[13] NEJATOLLAHI H, DUTT N, RAY S, et al. Software and hardware implementation of lattice-cased cryptography schemes[J]. University of California Irvine, CECSTR 17 4 (2017).

[14] DE C R, ROY S S, VERCAUTEREN F, et al. Efficient software implementation of Ring-LWE encryption[C]//Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE′15). 2015.

[15] YUAN Y J, CHENG C M, KIYOMOTO S, et al. Portable implementation of lattice-based cryptography using JavaScript[J]. International Journal of on Computing and Networking. 2016, 6(3): 309-327.

[16] STEBILA D, MOSCA M. Post-quantum key exchange for the internet and the open quantum safe project[R]. Cryptology ePrint Archive, 2016.

[17] AGUILAR-MELCHOR C, BARRIER J, GUELTON S, et al. NFLlib: NTT-based fast lattice library[C]//RSA Conference. 2016: 341-356.

[18] CHEN H, HAN K, HUANG Z, et al. Simple encrypted arithmetic library - seal (v2.3)[R]. 2017.

[19] G?TTERT N, FELLER T, SCHNEIDER M, et al. On the design of hardware building blocks for modern lattice-based encryption schemes[C]//Proceedings of the International Conference on Cryptographic Hardware and Embedded Systems (CHES′12). 2012.

[20] P?PPELMANN T, GüNEYSU T. Area optimization of lightweight Lattice-based encryption on reconfigurable hardware[C]// Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS′14). 2014.

[21] ROY S S, VERCAUTEREN F, MENTENS N, et al. Compact ring-LWE cryptoprocessor[C]//Proceedings of the International Conference on Cryptographic Hardware and Embedded Systems (CHES′14). 2014.

[22] BASU K, SONI D, NABEEL M, et al. NIST post-quantum cryptography-a hardware evaluation study[C]//IACR Cryptology ePrint Archive. 2019: 47.

[23] DANG V B, FARAHMAND F, ANDRZEJCZAK M, et al. Implementing and benchmarking three lattice-based post-quantum cryptography algorithms using software/hardware codesign[C]//2019 International Conference on Field-Programmable Technology (ICFPT). 2019: 206-214.

[24] BANERJEE U, UKYAB T S, CHANDRAKASAN A P. Sapphire: a configurable crypto-processor for post-quantum Lattice-based protocols (Extended Version)[C]//IACR Crypto. ePrint Arch. 2019: 1140.

[25] XIN G Z, HAN J, YIN T Y, et al. VPQC: a domain-specific vector processor for post-quantum cryptography based on RISC-V architecture[J]. IEEE Transactions on Circuits and Systems I-regular Papers 2020, 67(8): 2672-2684.

[26] FENG X, LI S G, XU S F. RLWE-oriented high-speed polynomial multiplier utilizing multi-lane stockham NTT algorithm[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2019, 99: 1.

[27] DU C H, BAI G Q. Towards efficient polynomial multiplication for Lattice-based cryptography[C]//2016 IEEE International Symposium on Circuits and Systems (ISCAS). 2016: 1178-1181.

Compact software/hardware co-design and implementation method of Aigis-sig digital signature scheme

ZHOU Zhen1,2, HE Debiao1,2, LUO Min1,2, LI Li1,2

1. Key Laboratory of Aerospace Information Security and Trusted Computing, Ministry of Education, Wuhan 430072, China 2. China School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China

Digital signature scheme Aigis-sig, constructed on ideal lattice, takes the advantages of high efficiency, short signature length and resistant to quantum attack, etc. An optimized modular multiplication arithmetic component was constructed and a compact hardware architecture for polynomial operation over a ring based on number theory transformation (NTT) algorithm for Aigis-sig was designed. Besides, based on this architecture, software/hardware co-design and implementation for Aigis-sig scheme on FPGA platform in cryptography was proposed. Experimental results show that the speed of signature phase and verification phase are increased by about 26% and 17% respectively, compared with the pure software implementation on Xilinx Zynq-7000 SoC platform when CPU clock frequency and hardware clock frequency are set as 666.66MHz and 150MHz respectively.

post-quantum cryptography, digital signature, Aigis-sig, FPGA, number theory transformation

TN918

A

10.11959/j.issn.2096?109x.2021026

2020?11?14；

2021?01?09

何德彪，hedebiao@163.com

國家自然科學(xué)基金（61972294, 61932016）

TheNational Natural Science Foundation of China (61972294, 61932016)

周朕, 何德彪, 羅敏, 等. 緊湊的Aigis-sig數(shù)字簽名方案軟硬件協(xié)同實現(xiàn)方法[J]. 網(wǎng)絡(luò)與信息安全學(xué)報, 2021, 7(2): 64-76.

ZHOU Z, HE D B, LUO M, et al. Compact software/hardware co-design and implementation method of Aigis-sig digital signature scheme[J]. Chinese Journal of Network and Information Security, 2021, 7(2): 64-76.

周朕（1996? ），男，安徽亳州人，武漢大學(xué)碩士生，主要研究方向為后量子密碼、密碼算法設(shè)計實現(xiàn)。

何德彪（1980? ），男，山東陽谷人，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向為密碼學(xué)、區(qū)塊鏈安全等。

羅敏（1974? ），男，湖北武漢人，武漢大學(xué)副教授，主要研究方向為密碼學(xué)、區(qū)塊鏈安全等。

李莉（1976? ），女，湖北武漢人，武漢大學(xué)副教授，主要研究方向為密碼學(xué)、區(qū)塊鏈安全等。