基于后量子密碼改進(jìn)算法的FPGA設(shè)計(jì)優(yōu)化

摘要：為了提高硬件整體的運(yùn)算效率，研究提出了一種可以降低Crystals-Kyber算法復(fù)雜度的改進(jìn)算法，硬件實(shí)現(xiàn)方式采用基于頻率抽取的數(shù)論變換（NTT）算法。通過(guò)合并NTT計(jì)算層減少需要的的內(nèi)存量，設(shè)計(jì)了一種迭代型NTT和流水型NTT相結(jié)合的硬件結(jié)構(gòu)。與之前其他的設(shè)計(jì)相比較，基于Crystals-Kyber算法的可編程門(mén)陣列（FPGA）優(yōu)化實(shí)現(xiàn)了高效的NTT多項(xiàng)式乘法。實(shí)驗(yàn)結(jié)果表明，所提方案優(yōu)化算法使用了較快的計(jì)算速度和較少的計(jì)算周期，以及較小的面積時(shí)間乘積（Area Time，AT），改進(jìn)的Crystals-Kyber算法與其他算法相比，至少縮短了39.13%的NTT計(jì)算周期，并縮短了47.50%計(jì)算時(shí)間，優(yōu)化了基于格密碼的執(zhí)行時(shí)間和硬件資源開(kāi)銷(xiāo)。

關(guān)鍵詞：后量子密碼；NTT算法；FPGA

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1001-5922（2025）02-0155-03

FPGA design optimization based on post-quantum cryptography improvement algorithm

TIAN Hongliang，WANG Xinyu，ZHANG Haiwu

（Northeast Electric Power University，Changchun 132000，China）

Abstract：In order to improve the overall computing efficiency of the hardware，an improved algorithm was pro?posed to reduce the complexity of the Crystals-Kyber algorithm，and the hardware implementation adopted the Num?ber Theory Transformation（NTT）algorithm based on frequency decimation.By merging the NTT computing layer to reduce the amount of memory required，a hardware structure combining iterative NTT and streamlined NTT was designed.Compared to other previous designs，the programmable gate array（FPGA）based on the Crystals-Kyber algorithm was optimized to achieve efficient NTT polynomial multiplication.Experimental results showed that the proposed scheme optimization algorithm used faster calculation speed，less calculation period，and smaller Area Time（AT），and the improved Crystals-Kyber algorithm shortened the NTT calculation period by at least 39.13%and shortened the calculation time by 47.50%compared with other algorithms，and optimized the execution time and hardware resource overhead of lattice based ciphers.

Key words：post quantum cryptography；NTT algorithm；FPGA

隨著量子計(jì)算機(jī)的發(fā)展，傳統(tǒng)公鑰密碼體制面臨著嚴(yán)重的安全問(wèn)題。基于格（LBC）的密碼算法具有加密效率高和抗量子攻擊等優(yōu)勢(shì)，成為研究熱點(diǎn)。如采用4個(gè)蝶形單元并行，合理安排存儲(chǔ)單元中的存儲(chǔ)順序得到高速的多項(xiàng)式乘法模塊[1]。在Xilinx Vir?tex UltraScale+XCVU7P高性能FPGA上實(shí)現(xiàn)Kyber的NTT運(yùn)算，頻率達(dá)到了預(yù)期值[2]。NTT單元采用基于時(shí)域和基于頻率的結(jié)合型蝶形單元，有關(guān)多項(xiàng)式的加減法操作復(fù)用該蝶形單元完成[3]。這些學(xué)者在關(guān)于格密碼實(shí)際應(yīng)用方面的研究仍存在運(yùn)算效率低，浪費(fèi)硬件資源等問(wèn)題[4]，因此，如何利用可編程門(mén)陣列對(duì)格密碼方案實(shí)現(xiàn)整體運(yùn)算效率的提高，這一問(wèn)題亟待解決。

1 Crysyals-Kyber算法理論基礎(chǔ)

1.1公鑰加密協(xié)議

Kyber是一個(gè)由CPA-安全公鑰加密（PKE）方案構(gòu)建的，是Fujisaki-Okamoto一個(gè)變體應(yīng)用在CCA-安全的KEM中作為密鑰生成、封裝和解封步驟的主要算法[5]。CCA-安全的KEM在基于MLWE硬件的CPA-安全密碼系統(tǒng)上構(gòu)建了Kyber機(jī)制，該機(jī)制分為Kyber512、Kyber768和Kyber1024 3個(gè)版本，根據(jù)所采用的參數(shù)集產(chǎn)生不同的后量子安全水平[6]。

然而，量子計(jì)算機(jī)正逐漸對(duì)目前使用的主要加密系統(tǒng)公鑰加密技術(shù)構(gòu)成威脅。量子計(jì)算機(jī)可以輕易的解決這些計(jì)算問(wèn)題，所以Crystals-Kyber算法采用基于頻率抽取的（DIF）數(shù)論變換（NTT）的蝶形運(yùn)算單元[7]。

1.2基于頻率抽取的乘法運(yùn)算

NTT是在離散傅立葉變換（DFT）數(shù)論上實(shí)現(xiàn)的，是定義在環(huán)上的線性正交變換，只在整數(shù)環(huán)上進(jìn)行運(yùn)算[8-9]。環(huán)多項(xiàng)式Rq定義式：

Rq= Zq（X）/f（X）"""""""""""""""" （1）

式中：Zq（X）表示多項(xiàng)式環(huán)，每一項(xiàng)的系數(shù)都在Zq上，也就是[0，q）之間的整數(shù)；f（X）則表示這些多項(xiàng)式在mod f（X）的意義下建立了相等的關(guān)系[10]。

f（X）= Xd+ udd- 1Xd- 1+ …+ u0（2）

式中：f（X）是次數(shù)為d的多項(xiàng)式。

那么Rq中的元素則可具體寫(xiě)為如下形式的多項(xiàng)式：

s= ad- 1Xd- 1+ ad- 2 Xd- 2+ ...+ a0，0lt;ailt; q（3）

式中：s? Rq。

Kyber中分圓環(huán)和降價(jià)環(huán)的同構(gòu)表示為：

Zq（X）/（Xd+ 1）= Zq（X）/（Xd- ζd 2）-

（Zq（X）/（Xd 2- ζd 4）Zq（X）/（Xd 2+ ζd 4）（4）

式中：用ζ表示某一個(gè)d次本原單位根。

數(shù)論變換（NTT）是一種用來(lái)快速計(jì)算多項(xiàng)式環(huán)上多項(xiàng)式乘法的計(jì)算，Kyber算法中就使用了NTT[11-12]。對(duì)于乘積的每個(gè)系數(shù)，都需要做最多次乘法，總共有n個(gè)系數(shù)，所以乘法操作的復(fù)雜度O（n2），使用NTT優(yōu)化過(guò)后的乘法操作，時(shí)間復(fù)雜度可以降低為O（nlogn）。NTT的正逆變換定義如下：

xm= k（n）0（1）xkΨ（2m+ 1）k= ?k（n）0（1）xkΨkωmkmodq（5）

xk= m（n）0（1）xmΨ-（2m+ 1）k= Ψ-k′ m（n）0（1）xmω-mkmodq

（6）

式中：φ是旋轉(zhuǎn)因子；ω是旋轉(zhuǎn)因子的模平方根。

2 Crystals-Kyber算法優(yōu)化設(shè)計(jì)

2.1合并NTT計(jì)算層

在FPU寄存器中，從ST（0）～ST（7）總共8個(gè)寄存器，每個(gè)寄存器的寬度大小是80個(gè)二進(jìn)制位，可以放進(jìn)去雙精度浮點(diǎn)數(shù)，因?yàn)殡p精度浮點(diǎn)數(shù)是64位，其他的16位用來(lái)做別的用處。在改進(jìn)中，使用了合并NTT計(jì)算層的通用優(yōu)化策略。該策略背后的思想是一次加載多個(gè)系數(shù)，這樣一次就可以計(jì)算出超過(guò)一層的NTT。Kyber的最新實(shí)現(xiàn)還部署了這種策略，合并層7～5和層4～2，同時(shí)分別計(jì)算圖層1[13-14]。通過(guò)使用浮點(diǎn)寄存器，合并第7～4層和第3～1層來(lái)實(shí)現(xiàn)NTT。對(duì)于在2個(gè)寄存器之間傳送數(shù)據(jù)，每個(gè)層都需要128個(gè)負(fù)載和128個(gè)存儲(chǔ)空間，還需要額外的128個(gè)vmovaps傳送單精度數(shù)。程序復(fù)制整個(gè)寄存器只復(fù)制低位，既不會(huì)影響程序功能，也不會(huì)影響執(zhí)行速度。

2.2改進(jìn)NTT硬件結(jié)構(gòu)

蝶形運(yùn)算單元是NTT計(jì)算的核心，是先計(jì)算模乘，再計(jì)算模加減。通過(guò)對(duì)現(xiàn)有的NTT結(jié)構(gòu)方案進(jìn)行全面系統(tǒng)的研究，并考慮計(jì)算時(shí)間和面積這種問(wèn)題，利用迭代型和流水型結(jié)合技術(shù)來(lái)處理多項(xiàng)式乘法中的計(jì)算時(shí)間問(wèn)題[15]。

在第二輪和第三輪kyber算法中，模q= 3 329，該素?cái)?shù)有256次原根，參考NIST的官方文件，在環(huán)多項(xiàng)式域上可以分解為128個(gè)平方項(xiàng)多項(xiàng)式乘積，即n= 128個(gè)點(diǎn)的NTT，需要執(zhí)行7輪蝶形運(yùn)算。在設(shè)計(jì)硬件結(jié)構(gòu)R2MDC中，只需要兩級(jí)，因?yàn)槊恳患?jí)實(shí)現(xiàn)需要一塊DSP塊，需要2塊DSP塊實(shí)現(xiàn)NTT結(jié)構(gòu)，以上結(jié)構(gòu)均使用流水線結(jié)構(gòu)以提高運(yùn)行頻率，縮短計(jì)算周期，提高計(jì)算效率。

3實(shí)驗(yàn)結(jié)果分析和對(duì)比

表1展示的是所提出的流水線和迭代NTT結(jié)構(gòu)

在硬件綜合實(shí)現(xiàn)后，資源與時(shí)間和目前最先進(jìn)的結(jié)構(gòu)對(duì)比。提出的結(jié)構(gòu)和對(duì)比的結(jié)果均使用參數(shù)n= 256，q= 3 329。表1以LUT、FF、DSP、BRAM為評(píng)估面積資源消耗，頻率和周期表示硬件設(shè)計(jì)的計(jì)算速度和時(shí)間，展示了提出設(shè)計(jì)的實(shí)現(xiàn)結(jié)果。

在表1中，本文方案具有最短的計(jì)算時(shí)間。在AT值方面，本文方案優(yōu)于大部分方案，但差于文獻(xiàn)[1]和文獻(xiàn)[3]方案。文獻(xiàn)[2]方案以運(yùn)算邏輯復(fù)用實(shí)現(xiàn)各步操作，占用資源最少，但導(dǎo)致并行程度低，NTT計(jì)算周期長(zhǎng)，AT值最高。文獻(xiàn)[3]方案雖然具有較好的AT值，但AT值稍高。文獻(xiàn)[4]文案采用的是16個(gè)蝶形運(yùn)算單元，縮短了計(jì)算周期，運(yùn)算文獻(xiàn)[5]方案在FPGA內(nèi)放置了2個(gè)蝶形運(yùn)算單元，導(dǎo)致NTT計(jì)算周期長(zhǎng)，AT值較高。提出的改進(jìn)Kyber算法，使得至少縮短了39.13%的NTT計(jì)算周期，并縮短了47.50%計(jì)算時(shí)間，在保證較高的工作頻率下，充分利用了芯片邏輯資源，具有較優(yōu)的AT值。

4結(jié)語(yǔ)

針對(duì)在實(shí)際應(yīng)用中格密碼運(yùn)行效率低，運(yùn)算效率慢的問(wèn)題，提出了一種改進(jìn)的CK算法，通過(guò)對(duì)硬件結(jié)構(gòu)的優(yōu)化設(shè)計(jì)，合并NTT計(jì)算層減少需要的內(nèi)存數(shù)量，然后設(shè)計(jì)一種迭代型和流水型相結(jié)合的NTT硬件結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的Crystals-Kyber算法與其他算法相比，至少縮短了39.13%的NTT計(jì)算周期，并縮短了47.50%計(jì)算時(shí)間，優(yōu)化了基于格密碼的執(zhí)行時(shí)間和硬件資源開(kāi)銷(xiāo)。

【參考文獻(xiàn)】

[1]肖超恩，倉(cāng)曉彤，張磊.輕量級(jí)序列密碼算法lizard的FP-GA設(shè)計(jì)與優(yōu)化[J].北京電子科技學(xué)院學(xué)報(bào)，2023，31（1）：9-18.

[2]伍松，毛宇河.高階矩陣并行求逆的FPGA設(shè)計(jì)與實(shí)現(xiàn)[J].機(jī)械設(shè)計(jì)與制造，2023（3）：187-192.

[3]吳文君.紅外與CCD圖像的融合及FPGA設(shè)計(jì)分析[J].今日自動(dòng)化，2023（8）：76-78.

[4]賴(lài)培鋒，吳建華，韓勇.驅(qū)控一體化多軸伺服系統(tǒng)的FP-GA設(shè)計(jì)與實(shí)現(xiàn)[J].機(jī)械設(shè)計(jì)與制造，2023（3）：286-290.

[5]李俊榜，李金林，潘晟，等.基于復(fù)合域的SM4算法FPGA設(shè)計(jì)與實(shí)現(xiàn)[J].桂林電子科技大學(xué)學(xué)報(bào)，2023，43（1）：49-55.

[6]莫海城.基于等值網(wǎng)絡(luò)模型的電子設(shè)備故障智能分析診斷技術(shù)[J].粘接，2023，50（9）：192-196.

[7]楊碎明，尹艷艷.大數(shù)據(jù)時(shí)代下計(jì)算機(jī)電子信息處理技術(shù)研究[J].粘接，2021，45（2）：84-88.

[8]陳韜，李慧琴，李偉，等.面向格基后量子密碼算法的可重構(gòu)多項(xiàng)式乘法架構(gòu)[J].電子與信息學(xué)報(bào)，2023，45（9）：3380-3392.

[9]范建南，高獻(xiàn)偉，章索.基于格的后量子密碼算法采樣模塊的研究及FPGA實(shí)現(xiàn)[J].北京電子科技學(xué)院學(xué)報(bào)，2022，30（3）：55-63.

[10]董慧康，裴東芳.考慮無(wú)線網(wǎng)絡(luò)安全的量子密碼更新算法仿真[J].計(jì)算機(jī)仿真，2023，40（2）：399-402.

[11]肖昊，趙延睿，胡越，等.抗量子密碼中快速數(shù)論變換的硬件設(shè)計(jì)與實(shí)現(xiàn)[J].信息網(wǎng)絡(luò)安全，2023（4）：72-79.

[12]張瀚豐，周子健，楊智超，等.一種新的多項(xiàng)式環(huán)上的數(shù)論變換算法[J].密碼學(xué)報(bào)，2023，10（3）：539-553.

[13]李斌，陳曉杰，馮峰，等.后量子密碼CRYSTALS-Kyber的FPGA多路并行優(yōu)化實(shí)現(xiàn)[J].通信學(xué)報(bào)，2022，43（2）：196-207.

[14]張青.Kyber加密算法及其改進(jìn)算法的研究和實(shí)現(xiàn)[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2022（11）：26-29.

[15]張輝，凌元，孫健.基于Cordic算法的對(duì)數(shù)運(yùn)算FPGA設(shè)計(jì)與實(shí)現(xiàn)[J].信息記錄材料，2023，24（6）：116-118.

（責(zé)任編輯：平海，蘇幔）