基于FPGA的Streamlined NTRU Prime抗量子加密技术研究

王 鹏，武俊鹏*，高 迪

(1.哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001；2.国科大杭州高等研究院，浙江 杭州 310024)

0 引言

量子计算是一种将物理学与计算机科学相结合的技术[1]，该技术可以显著提高计算机算力，完成经典计算机难以实现的任务[2]。量子比特是实现高性能计算的关键,量子比特同时具备0和1两种状态,并且可以通过与空间上相互独立的其他量子比特共享状态来实现并行计算[3]。因此,随着芯片中量子比特位数的增加,其计算性能呈指数增长[4]。近年来,国内外的许多团队对量子计算技术开展了较为深入的研究并取得了一定的研究成果。早在2017年11月,IBM就对外宣称完成了50量子比特量子计算机的研制工作,并着手研制更高性能的量子计算机[5]。在2021年,中国科学技术大学设计出了一个具有62量子比特的芯片,并在此芯片上演示高保真单粒子和双粒子量子行走算法[6]。62量子比特芯片的制备成功,标志着将量子计算技术应用于解决实际问题成为可能。

然而,随着Shor算法[7-8]和Grover算法[9]的提出，传统的公钥密码算法已不再安全[10]，因此需要提出新的加密算法来应对量子计算机的攻击。NIST于2017年截止后量子加密算法草案的征集,共有69个方案满足NIST所提出的最低要求,对这69个方案进一步筛选得到26个方案作为第二轮的候选方案[11]。在这26个方案中,基于NTRU的Streamlined NTRU Prime方案较易于用硬件实现。

国外研究人员已经针对Streamlined NTRU Prime加密方案进行了一些初步研究。2019年Cheng等人[12]将Streamlined NTRU Prime方案在IoT设备上进行轻量级实现,其根据所要应用的IoT设备特点寻找出一个相对最优的多项式乘法算法,并使用汇编语言编写系数取模运算以提高效率,但这种实现方式的可移植性相对较差,当更换硬件平台时需要进行较大的改动。2020年，Yeniaras等人[13]提出3种多项式乘法算法并将算法应用于提高Streamlined NTRU Prime方案解封装的速度。2021年， Alkim等人[14]针对Streamlined NTRU Prime算法所需要进行的多项式乘法开展研究,提出2种不同的基于数论变换(NTT)的多项式乘法计算方法：一种方法是利用Good’s trick技术实现多项式高速相乘,并且可以支持多种参数集,具有较高的通用性；另一种方法是基于混合积数论变换来实现多项式乘法,其特点是在进行计算时只需要占用很小的内存空间。Alkim等人还对2种方法在Cortex-M4平台进行了性能评估。

本文将从密钥产生和封装2个方面来介绍第二轮Streamlined NTRU Prime方案的原理以及硬件实现方式,最终在Xilinx Kintex UltraScale FPGA KCU105平台测试此方案资源占用情况。

1 Streamlined NTRU Prime算法

NTRU Prime是一种基于NTRU的格基后量子密码算法族[15]，NTRU Prime中包含2种KEM方案：Streamlined NTRU Prime(SNTRUP)和NTRU LPRime(NTRULPR)。Streamlined NTRU Prime方案的公钥为h=g/(3f)，其中g和f为不公开的多项式，这种方案类似于传统的NTRU加密算法。NTRU LPRime方案是基于环上容错学习(RLWE)构造的[16]，其公钥为h=e+Af，其中e和f不需要公开，而A需要被公开。

Streamlined NTRU Prime的第二轮方案包括3个级别的参数集，参数集中包含的3个元素分别为：p，q和w，其中p和q为大素数，w为正整数，并且规定2p≥3w，q≥16w+1以及xp-x-1在多项式环(/q)[x]上是不可约的。

美国国家标准与技术研究院(NIST)将后量子加密算法的安全性分为5个级别[17]：

第1级：安全性与128位分组密码(如AES128)相同或更优；

第2级：安全性与256位哈希函数(如SHA256/SHA3-256)相同或更优；

第3级：安全性与192位分组密码(如AES192)相同或更优；

第4级：安全性与384位哈希函数(如SHA384/SHA3-384)相同或更优；

第5级：安全性与256位分组密码(如AES256)相同或更优。

参数集与NIST安全性级别的对应关系如表1所示。

表1 Streamlined NTRU Prime参数集设置

1.1 符号说明

1.2 密钥产生

Streamlined NTRU Prime算法在此阶段需要输出所产生公钥和私钥。其算法如下：

密钥产生算法输出:(公钥,私钥)= (h-(x),(k-(x),h-(x),ρ(x)))① g(x)＄←Small② 如果1/g(x)∉R/3,跳转到步骤①③ v(x)←1/g(x)∈R/3④ f(x)＄←Short⑤ h(x)←g(x)/(3f(x))∈R/q⑥ ρ(x)＄←Short⑦ h-(x)←Encode(h(x))⑧ k-(x)←Encode(f(x),v(x))⑨ 返回 (h-(x),(k-(x),h-(x),ρ(x)))

1.3 封装

Streamlined NTRU Prime的封装操作需要以公钥作为输入，并生成密文和会话密钥作为输出。其算法如下：

封装算法输入:编码后的公钥=h-(x)输出:(密文,会话密钥)= (C,HashSession(1,r-(x),C))① h(x)←Decode(h-(x))② r(x)＄←Short③ r-(x)←Encode(r(x))④ h(x)r(x)←h(x)·r(x)∈R/q⑤ c(x)←Round(h(x)r(x))∈Rounded⑥ c-(x)←Encode(c(x))⑦ C←(c-(x),HashConfirm(r-(x),h-(x)))⑧ 返回(C,HashSession(1,r-(x),C))

2 核心实现

2.1 多项式乘法实现

在Streamlined NTRU Prime算法执行过程中需要进行多次多项式乘法运算。暴力求解多项式乘法的时间复杂度为O(n2)，该方法虽然容易实现但效率较低。本设计采用单次Karatsuba算法实现多项式乘法[18]，Karatsuba算法是通过降低运算过程中乘法的次数来提高计算效率。

假设存在2个多项式A(x)和B(x)，由于Streamlined NTRU Prime算法所规定的参数集中p均为奇数，无法均匀地划分为2个部分，故在2个多项式最高位分别附加apxp和bpxp，其中ap和bp恒定为0，即：

(1)

设A0，A1，B0，B1分别为：

(2)

则A(x)和B(x)可以表示为：

(3)

(4)

2.2 编码与解码实现

为了减少空间的占用，Streamlined NTRU Prime算法需要对公钥、私钥以及密文进行编码操作。其中Encode的功能是将环上元素编码成串，而Decode的功能是将串还原成环上元素[15]。

假设存在2个整数序列M=(m0,m1,…,mn-1)和R=(r0,r1,…,rn-1)，其中0≤ri

编码算法输入:2个整数序列R,M输出:编码后的串S① 如果n的大小为0,则S是一个空序列② 如果n的大小为1:③ 用r和m分别表示R[0]和M[0]的值④ 当m的值大于1时循环执行以下步骤:⑤ 在S中存入r模28后的值⑥ 将r除以28且做下取整的结果赋值给r⑦ 将m除以28且做上取整的结果赋值给m⑧ 输出S⑨ 创建2个空序列R2和M2⑩ 令变量i在[0,n-1]以步长为2进行循环: 令m的值为M[i]与M[i+1]的乘积 令r的值为R[i]+M[i]∗R[i+1] 当m的值大于214时循环执行以下步骤: 在S中存入r模28后的值 将r除以28且做下取整的结果赋值给r 将m除以28且做上取整的结果赋值给m 在R2中存入r 在M2中存入m 如果n为奇数: 在R2中存入R的最后一个元素 在M2中存入M的最后一个元素 将R2和M2作为输入递归执行以上过程,并将结果存入S作为输出

解码算法输入:编码后的串S和整数序列M输出:整数序列R① 如果n的大小为0,则输出一个空序列② 如果n的大小为1:③ 令变量i遍历S的范围,计算S[i]∗256∗i并求和记为Z④ 输出Z对M中第一个元素取模的值⑤ 设置一个初值为0的变量k⑥ 设置2个空序列bottom和M2⑦ 令变量i在[0～n-1]以步长为2进行循环:⑧ 令m的值为M[i]和M[i+1]的乘积⑨ 令r的初始值为0,t的初始值为1⑩ 当m的值大于214时循环执行以下步骤: 令r的值为r+S[k]∗t 令t的值为t∗256 令k做自增运算 将m除以28且做上取整的结果赋值给m 将r和t的组合存入bottom中 将m存入M2中 如果n为奇数,则在M2中存入M的最后一个元素 将S[k:]和M2作为输入执行以上过程所得结果赋值给R2 设置一个空序列R 令变量i在[0,n-1]以步长为2进行循环: 将bottom[i∥2]赋值给r和t 令r的值为r+t∗R2[i∥2] 将r对M[i]取模的值存入序列R中 将(r∥M[i])对M[i+1]取模的结果存入R中 如果n为奇数则将R2中的最后一个元素存入R中 输出R

2.2.1 公钥的编码方法

假设所有公钥可以表示为多项式r0+r1x+…+rp-1xp-1，式中的每一个系数ri∈{-(q-2)/2,…,-1,0,1,…,(q-1)/2}，将所有系数加(q-1)/2可以获得范围为{0,1,…,q-1}的p个元素，最后对M=(q,…,q)应用Encode操作，即可得到编码后的公钥。

2.2.2 私钥的编码方法

私钥是由f(x)和1/g(x)两个部分构成，f(x)与1/g(x)采用相同的方式进行编码。假设二者均可用多项式r=r0+r1x+…+rp-1xp-1表示，将多项式按照自变量x指数递增的形式排列并对所有系数加1，则系数ri的范围均为{0,1,2}，故一个系数可由2位二进制数进行表示。按序将4个系数压缩至1 Byte即可完成编码操作。

2.2.3 密文的编码方法

对于Rounded中的多项式r0+r1x+…+rp-1xp-1，每个系数ri∈{-(q-1)/2,…,-3,0,3,…,(q-1)/2}。对所有系数加(q-1)/2并做除3运算，则系数ri的取值范围为{0,1,…,(q-1)/3}。最后，对M=((q-1)/3+1,…,(q-1)/3+1)应用Encode操作，即可获得编码后的密文。

解码是编码的逆操作，以私钥解码为例，按序将每个字节拆分成4个部分就可以还原出所有的系数，由所获得的系数即可还原出编码前的多项式，从而完成解码操作。

3 实验结果

本设计所使用的FPGA为Xilinx Kintex UltraScale FPGA KCU105，如图1所示。在此硬件基础上实现NIST第二轮Streamlined NTRU Prime算法的密钥产生和封装2个部分，在没有采用特殊时钟约束的前提下，本设计的最大时钟频率为192.901 MHz，各种资源占用情况如表2所示。

图1 FPGA环境Fig.1 FPGA environment

表2 资源占用报告

由表2可以看出，本设计只需要很少的资源就可以完成密钥产生和封装操作，且时钟频率处于相对较高的数值，因此本设计可以用在资源受限的FPGA平台，具有较好的兼容性和可移植性。

在完成布局布线后对本设计进行功耗估计，片上总功耗为0.655 W，其中动态功耗为0.175 W，占总功耗的27%，静态功耗为0.479 W，占总功耗的73%。动态功耗包括Clocks，Signals，Logic，BRAM，DSP和IO，其具体功耗如表3所示。本设计总体功耗较低，可以用于功耗限制严格的设备。

表3 动态功耗

4 结束语

本文对NIST第二轮Streamlined NTRU Prime算法做了详细的介绍，并且提出了一种硬件实现方案。本方案对密钥产生和封装2个过程进行了完整的实现，在密钥产生阶段能够正确地产生公钥和私钥并将其编码成串，在封装阶段可以对公钥解码并生成密文。本设计采用次Karatsuba算法实现多项式乘法，相较于传统的暴力求解方案速度更快且对资源要求不高。因此，本方案同样适用于硬件资源不足的设备，具有较好的可移植性。目前的加密方式大多以CPU作为硬件平台，采用软件实现加密算法，而采用此方式实现加密算法通常存在加/解密效率低、系统资源占用率高以及可移植性差等问题。FPGA具有流水线并行和数据并行的特点，即在单位时间内，相较于CPU可以完成更多次运算，因此在FPGA平台可以更快地完成加/解密操作。