基于Toom-Cook多项式乘法SNTRUP算法的FPGA快速实现

FPGA Fast Implementation Based on Toom-Cook polynomial Multiplication SNTRUP Algorithm

摘要: 本文设计了基于Toom-Cook多项式乘法Streamlined NTRU Prime算法的FPGA快速实现方法，Toom-Cook多项式乘法能对Streamlined NTRU Prime算法中封装以及解封装运算的多项式系数相乘进行优化，能明显减少乘法运算次数，增加Streamlined NTRU Prime算法的运算效率。在ModelSim仿真软件Intel Cyclone IV GX系列EP4CGX150DF31I7AD芯片上进行仿真实验。实验结果表明，本方案可以在封装以及解封装速度上可以提升26%。

Abstract: This paper designs a fast FPGA implementation method based on Toom-Book polynomial multiplication Streamlined NTRU Prime algorithm. Toom-Book polynomial multiplication can optimize the multiplication of polynomial coefficients of encryption and decryption operations in Streamlined NTRU Prime algorithm, significantly reduce the number of multiplication operations, and increase the efficiency of Streamlined NTRU Prime algorithm. The simulation experiment is carried out on the ModelSim simulation software Intel Cyclone IV GX series EP4CGX150DF31I7AD chip. The experimental results show that the encryption and decryption speed of this scheme can be improved by 26%.

1. 引言

近年来，随着密码技术的快速发展，传统的密码算法已经不能抵抗量子计算机 [1] 的攻击，许多曾被认为无法破解的密码学困难问题，在量子计算技术面前变得不再可靠。20世纪90年代中期，Shor [2] 提出大数分解的量子算法，能够在多项式时间内解决大整数分解问题以及可以对离散对数问题进行求解，比传统计算机计算速度有指数级的提升。2001年，O’brien J L提出光量子计算 [3] ，仅使用单光子源，线性光学原件就可以进行可扩展的量子计算，又基于错误编码方法大大减少资源开销，使全光学架构量子计算机大规模实现成为可能。2018年，Preskill J提出了一种新的量子计算技术 [4] ，具有50~100个量子位的量子计算机能够代替现在的传统计算机，并且其量子门中的噪声可以使量子电路变得很小。基于此美国国家标准与技术研究院(NIST)于2016年开始后量子密码算法的征集工作 [5] ，2022年7月，NIST公布了第三轮15个后量子密码方案，目前的后量子加密算法主要分为基于格的算法 [6] 、基于编码的算法 [7] 、基于哈希的算法 [8] 、基于多变量的算法 [9] 、基于超奇异椭圆曲线的算法 [10] 和基于零知识证明的算法 [11] ，其中基于格的NTRU Prime算法 [12] 成为备选公钥加密和密钥生成算法，它具有较高的可移植性及安全性，且更易于在硬件上实现 [13] 。文献 [14] 对如何在FPGA上快速实现认证密钥协商协议的问题进行深入研究，设计了一种双向认证密钥协商协议，并且对SNTRUP算法的密钥生成速度和封装解封装速度都有较大提升。文献 [15] 针对格密码算法计算开销大的问题，设计了一种多项式乘法器，实现快速模乘运算。

NTRU Prime算法由于代数结构上的差异以及加密方式的不同，分为NTRU LPRime算法(NTRU LPR)以及Streamlined NTRU Prime算法(SNTRUP)。本文重点介绍了Streamlined NTRU Prime算法的密钥产生过程以及封装和解封装过程，在算法封装过程中会大量使用多项式乘法运算，而乘法运算是影响封装速度的主要因素，并且会占用大部分的时间和资源，影响运算效率。因此本文对封装过程中的多项式乘法部分进行重点优化，在多项式相乘时，大整数相乘运算时间直接影响两个多项式相乘的时间，因此使用Toom-Cook算法 [16] [17] 对多项式系数进行拆分、评估、逐点相乘、插值、重组五个步骤，以减少多项式系数相乘的次数以及时间复杂度，增加FPGA硬件实现效率。最后在仿真软件ModelSim上对Cyclone IV GX系列EP4CGX150DF31I7AD芯片进行仿真实验，测试该算法的资源占用情况以及实现效率。

2. Streamlined NTRU Prime算法

Streamlined NTRU Prime算法是基于格理论的后量子加密算法，该算法主要包括四个部分：参数选择、密钥生成算法、封装算法和解封装算法。下面是对这四个部分的重点介绍。

1) SNTRUP参数选择

Streamlined NTRU Prime定义了如下多项式环，令 $\mathbb{Z}$ 表示整数，环 $\mathbb{Z}\left[x\right]/\left(x^n-x-1\right)$ 、环 $\left(\mathbb{Z}/3\right)\left[x\right]/\left(x^n-x-1\right)$ 和环 $\left(\mathbb{Z}/q\right)\left[x\right]/\left(x^n-x-1\right)$ 分别记为 $\mathcal{R}$ 、 $\mathcal{R}/3$ 和 $\mathcal{R}/q$ 。Streamlined NTRU Prime的参数(p, q, w)满足以下条件：p，q均为素数，w是正整数， $2p\ge 3w$ ， $q\ge 16w+1$ ，并且 $x^p-x-1$ 在 $\mathcal{R}/q$ 中是不可约的。如果 $\mathcal{R}$ 的所有系数都在{−1, 0, 1}范围内，则称 $\mathcal{R}$ 的多项式为Small多项式。如果一个Small的2t个系数不为零，我们就称它为t-Small。Weight w表示的多项式恰好有w个非零系数。Round表示将多项式的所有系数近似到最接近3的倍数。Hash_a(x)表示以a作为x的前缀取SHA-512哈希值的前256位。Encode和Decode表示使用编码或解码算法将 $\mathcal{R}/3$ 和 $\mathcal{R}/q$ 中的多项式转换为字节字符串。

Streamlined NTRU Prime算法的参数集设置有六种，分别为：sntrup653、sntrup761、sntrup857、sntrup953、sntrup1013、sntrup1277，本文将针对其中的sntrup761参数集做具体研究，其具体参数为p = 761，q = 4591，w = 286。

2) SNTRUP密钥生成算法

Streamlined NTRU Prime算法的密钥生成过程需要产生公钥和私钥，具体算法如下：首先在Small中随机生成一个多项式 $g\left(x\right)$ ，并且确保多项式 $g\left(x\right)$ 在 $\mathcal{R}/3$ 中可逆。再随机生成一个属于t-Small的多项式 $f\left(x\right)$ ，并且满足多项式 $f(x)\in \mathcal{R}$ 。接下来随机生成一个属于t-Small的多项式 $\rho \left(x\right)$ ，并且多项式 $\rho \left(x\right)$ 长度为(p + 3)/4。然后把多项式 $g\left(x\right)$ 的倒数 $1/g\left(x\right)$ 用 $v\left(x\right)$ 表示， $g\left(x\right)/3f\left(x\right)$ 的结果用 $K\left(x\right)$ 表示， $K\left(x\right)$ 经过Encode编码生成 $\bar{K}\left(x\right)$ ，多项式 $f\left(x\right)$ ， $v\left(x\right)$ 共同编码生成 $\bar{k}\left(x\right)$ ，最后把 $\bar{K}\left(x\right)$ 作为公钥进行输出， $\left(\bar{k}\left(x\right),\bar{K}\left(x\right),\rho \left(x\right),has{h}_4\left(\bar{K}\left(x\right)\right)\right)$ 作为私钥进行输出。

3) SNTRUP封装算法

Streamlined NTRU Prime算法的加密过程需要输入在密钥生成过程中产生的公钥，输出结果为加密后的密文以及会话密钥，具体算法如下：首先随机生成一个属于t-Small的多项式 $r\left(x\right)$ ，接着对 $\bar{K}\left(x\right)$ 进行Decode解码生成 $K\left(x\right)$ ，再将多项式 $K\left(x\right)$ 和 $r\left(x\right)$ 相乘的结果Round后赋值给 $c\left(x\right)$ ，并将 $c\left(x\right)$ 进行Encode编码生成 $\bar{c}\left(x\right)$ ，接下来将 $r\left(x\right)$ 进行Encode编码生成 $\bar{r}\left(x\right)$ 。接着把 $\bar{c}\left(x\right)$ 、 $has{h}_2\left(has{h}_3\left(\bar{r}\left(x\right)\right)\right)$ 和 $has{h}_4\left(\bar{K}\left(x\right)\right)$ 组合赋值给C，C就是最终的密文，把 $has{h}_1\left(has{h}_3\left(\bar{r}\left(x\right)\right)\right)$ 和密文C共同组合生成会话密钥。最后把密文以及会话密钥共同输出。

4) SNTRUP解封装算法

Streamlined NTRU Prime算法的解密过程需要把密文C以及在密钥生成过程中产生的私钥 $\left(\bar{k}\left(x\right),\bar{K}\left(x\right),\rho \left(x\right),has{h}_4\left(\bar{K}\left(x\right)\right)\right)$ 共同作为算法的输入，解密过程具体算法如下：首先把 $\bar{c}\left(x\right)$ 进行Decode解密生成 $c\left(x\right)$ ，再对 $\bar{k}\left(x\right)$ 解密生成 $f\left(x\right)$ ， $v\left(x\right)$ ，接着把 $3f\left(x\right)c\left(x\right)$ 的结果做模3运算，结果赋值给 $e\left(x\right)$ ，再把 $e\left(x\right)$ 和 $v\left(x\right)$ 乘积的结果用 $r^{\prime }\left(x\right)$ 表示。接下来判断如果 $r^{\prime }\left(x\right)$ 中没有w个非零系数，就把 $\left(1,1,\cdots ,0,0,\cdots ,0\right)$ 赋值给 $r^{\prime }\left(x\right)$ ，其中前w个元素为1，其余为0。接着用 $\bar{K}\left(x\right)$ 和 $r^{\prime }\left(x\right)$ 重新做封装计算新的密文C’，然后把 $r^{\prime }\left(x\right)$ 进行Encode加密生成 $\overline{r^{\prime }}\left(x\right)$ ，判断C’是否等于C，如果等于就输出 $has{h}_1\left(has{h}_3\left(\overline{r^{\prime }}\left(x\right)\right),C\right)$ ，如果不等于就输出 $has{h}_0\left(has{h}_3\left(\rho \left(x\right)\right),C\right)$ 。

3. SNTRUP算法FPGA优化算法

3.1. 算法实现

在Streamlined NTRU Prime算法的封装和解封装以及生成公私钥的过程中会大量使用多项式乘法，而多项式乘法是影响算法效率的主要因素，两个多项式直接相乘虽然可以实现但是效率较低资源占用率较大，因此采用Toom-Cook算法对多项式乘法进行优化，需要把多项式均匀分成k个部分，进行2k − 1次乘法来增加Streamlined NTRU Prime算法的运算效率。

Toom-Cook算法是采用分治的思想，把给定的大整数分成k份，用Toom-Cook-k算法进行递归运算。本次设计综合考虑了Streamlined NTRU Prime算法的特性以及硬件资源占用比，采用Toom-Cook-3快速乘法对Streamlined NTRU Prime算法进行优化设计，图1是SNTRUP优化算法的流程图，在K(x)多项式和r(x)多项式相乘时使用Toom-Cook-3多项式乘法对Streamlined NTRU Prime算法进行优化，两个多项式的系数经过拆分、评估、逐点相乘、插值和重组五个步骤最终计算出结果c(x)，其中SNTRUP算法的多项式相乘是影响该算法效率的主要步骤，逐点相乘是Toom-Cook-3多项式乘法的关键步骤，其流程图如图2所示。

Figure 1. SNTRUP algorithm flow chart

图1. SNTRUP算法流程图

Figure 2. Point-by-point multiplication algorithm flowchart

图2. 逐点相乘算法流程图

接下来具体介绍Streamlined NTRU Prime多项式乘法优化算法的五个步骤，首先该算法把n位数多项式系数a和b分成三段，每一段都有 $\lceil \frac{n-1}{3}\rceil$ 位数，把a和b可以表示为，如式(1)所示：

$\{\begin{array}{l}a=a_2\times {10}^{2\times \lceil \frac{n-1}{3}\rceil }+a_1\times {10}^{\lceil \frac{n-1}{3}\rceil }+a_0\\ b=b_2\times {10}^{2\times \lceil \frac{n-1}{3}\rceil }+b_1\times {10}^{\lceil \frac{n-1}{3}\rceil }+b_0\end{array}$ (1)

例如：当整数为12345678时，就可以把此数写作 $12\times {10}^6+345\times {10}^3+678$ 。

由于a和b中x的最高次项均是2次项，所以乘积c中最高次项是4次项，乘积c的多项式表达式如式(2)所示。

$c=a\times b=c_4\times {10}^{4\times \lceil \frac{n-1}{3}\rceil }+c_3\times {10}^{3\times \lceil \frac{n-1}{3}\rceil }+c_2\times {10}^{2\times \lceil \frac{n-1}{3}\rceil }+c_1\times {10}^{\lceil \frac{n-1}{3}\rceil }+c_0$ (2)

由于10的幂次是 $\lceil \frac{n-1}{3}\rceil$ 的整数倍，因此只需要计算c₀，c₁，c₂，c₃，c₄这5个系数，再根据各个系数与 ${10}^{\lceil \frac{n-1}{3}\rceil }$ 所相乘的值再进行左移操作，最后通过简单的加法操作得到乘积c。由于c是一个关于 ${10}^{\lceil \frac{n-1}{3}\rceil }$

的四次多项式，而c₀，c₁，c₂，c₃，c₄是这个多项式的五个未知数，因此就把问题转换为求解五个未知数的问题。因为求解四次多项式至少需要五个已知点才能求解，所以需要选取五组点构造五个方程，在点的选取上，可以选取任意的点来求解方程，但是在实际的操作中，会尽量选取容易计算的点，以简化计算，所以一般选取x的值为0，1，−1，2， $\infty$ 。将上述x的取值带入式(1)中得到a和b的结果，结果如下：

$\{\begin{array}{l}a\left(0\right)=a_0\\ a\left(1\right)=a_2+a_1+a_0\\ a\left(-1\right)=a_2-a_1+a_0\\ a\left(2\right)=4a_2+2a_1+a_0\\ a\left(\infty \right)=a_2\end{array}$ (3)

$\{\begin{array}{l}b\left(0\right)=b_0\\ b\left(1\right)=b_2+b_1+b_0\\ b\left(-1\right)=b_2-b_1+b_0\\ b\left(2\right)=4b_2+2b_1+b_0\\ b\left(\infty \right)=b_2\end{array}$ (4)

将上述x的取值带入式(2)中得到c的结果，结果如下：

$\{\begin{array}{l}c\left(0\right)=c_0\\ c\left(1\right)=c_4+c_3+c_2+c_1+c_0\\ c\left(-1\right)=c_4-c_3+c_2-c_1+c_0\\ c\left(2\right)=16c_4+8c_3+4c_2+2c_1+c_0\\ c\left(\infty \right)=c_4\end{array}$ (5)

以上式子中， $a\left(\infty \right)$ 、 $b\left(\infty \right)$ 均是在趋近于 $\infty$ 时， $a\left(\infty \right)$ 或 $b\left(\infty \right)$ 与 ${\infty }^2$ 的比值， $c\left(\infty \right)$ 是在x趋近于 $\infty$ 时与 ${\infty }^4$ 的比值。因此，该算法就转换为求解式(5)的线性方程组。可以把方程组(5)表示为矩阵形式，如式(6)所示：

$\left[\begin{array}{c}c\left(0\right)\\ c\left(1\right)\\ c\left(-1\right)\\ c\left(2\right)\\ c\left(\infty \right)\end{array}\right]=\left(\begin{array}{ccccc}0& 0& 0& 0& 1\\ 1& 1& 1& 1& 1\\ 1& -1& 1& -1& 1\\ 16& 8& 4& 2& 1\\ 1& 0& 0& 0& 0\end{array}\right)\times \left[\begin{array}{c}{c}_4\\ c_3\\ c_2\\ c_1\\ c_0\end{array}\right]$ (6)

将上述矩阵等式记作C = M × N，若要求解N矩阵，就要根据矩阵求逆法则，对矩阵M求逆，可得式(7)：

$\left[\begin{array}{c}{c}_4\\ c_3\\ c_2\\ c_1\\ c_0\end{array}\right]=\left(\begin{array}{ccccc}0& 0& 0& 0& 1\\ \frac{1}{2}& -\frac{1}{2}& -\frac{1}{6}& \frac{1}{6}& \frac{1}{2}\\ -1& \frac{1}{2}& \frac{1}{2}& 0& -1\\ -\frac{1}{2}& 1& -\frac{1}{3}& -\frac{1}{6}& -\frac{1}{2}\\ 1& 0& 0& 0& 0\end{array}\right)\times \left[\begin{array}{c}c\left(0\right)\\ c\left(1\right)\\ c\left(-1\right)\\ c\left(2\right)\\ c\left(\infty \right)\end{array}\right]$ (7)

根据式(2)，可以快速求得 $c\left(0\right)$ 、 $c\left(1\right)$ 、 $c\left(-1\right)$ 、 $c\left(2\right)$ 和 $c\left(\infty \right)$ 的值，再根据上述式(7)矩阵，求得c₄、c₃、c₂、c₁和c₀的值。再利用插值法对c₄左移 $4\times \lceil \frac{n-1}{3}\rceil$ 位，c₃左移 $3\times \lceil \frac{n-1}{3}\rceil$ 位，c₂左移 $2\times \lceil \frac{n-1}{3}\rceil$ 位，c₁左移 $\lceil \frac{n-1}{3}\rceil$ 位，c₀进行累加，最后得出运算结果c。

Toom-Cook-3算法把两个大整数分成三部分进行相乘，把优化前的9次乘法化简成5次乘法，它的时间复杂度是O(n^1.465)，对比不使用Toom-Cook-3算法两个大整数直接相乘的时间复杂度是O(n²)，因此Toom-Cook-3算法能提高多项式乘法的运算速度。

3.2. SNTRUP算法框架

经过上述多项式乘法算法的优化，表1展示了SNTRUP算法的框架。

Table 1. Algorithmic framework

表1. 算法框架

4. SNTRUP的FPGA实验结果

4.1. 实验环境

本次实验的FPGA硬件环境平台是Intel Cyclone IV GX系列EP4CGX150DF31I7AD芯片，其查找表(LUT, Look Up Table)资源是1497600，触发器(FF, flip flop)资源是299520，数字信号处理器(DSP, Digital Signal Processing)资源是1200，块RAM (BRAM, Block RAM)存储器资源是500，输入输出端口(I/O, Input/Output Part)资源是508。使用硬件描述语言Verilog-HDL在Quartus II 13.0软件上实现了Streamlined NTRU Prime算法的整体硬件设计，在此环境中，使用ModelSim SE-64 10.5仿真软件仿真实现了后量子密码算法Streamlined NTRU Prime的密钥产生以及加解密部分，并针对Streamlined NTRU Prime算法的多项式乘法部分进行了具体优化。

4.2. 实验结果

文中方案使用多项式优化算法是Toom-Cook-3算法，对Streamlined NTRU Prime算法加解密部分的多项式乘法进行了优化，表2展示了Toom-Cook-3算法以及Streamlined NTRU Prime算法总体的资源占用情况。

Table 2. Resource usage of the Toom-Cook-3 algorithm and the Streamlined NTRU Prime algorithm

表2. Toom-Cook-3算法以及Streamlined NTRU Prime算法的资源占用情况

主要的性能指标为LUT查找表，FF触发器，I/O输入输出端口，DSP数字信号处理器，BRAM块RAM。Toom-Cook-3算法使用LUT资源占Streamlined NTRU Prime算法总消耗的2.26%，FF资源消耗占2.93%，DSP资源消耗占4%，I/O资源消耗占2.54%。Streamlined NTRU Prime算法消耗的LUT资源占总体资源量的6.06%，FF资源消耗占1.46%，DSP资源消耗占2.08%，BRAM资源消耗占3.4%，I/O资源消耗占38.78%。由此可见，在此环境下实现Streamlined NTRU Prime算法消耗I/O资源占比较高，其余资源消耗均处在较低水平，而Toom-Cook-3算法模块各资源消耗占比均处在较低水平。本次设计只占用较少的资源就可以在FPGA上实现SNTRUP算法的密钥生成、封装以及解封装过程，并且Toom-Cook-3算法可以对SNTRUP算法进行加速操作，可以更加快速的实现SNTRUP算法。

5. 结束语

本文对后量子密码Streamlined NTRU Prime算法的密钥生成过程以及加解密过程进行了详细的介绍，针对在加解密阶段的多项式乘法部分进行了具体优化。本文通过使用Toom-Cook-3算法把多项式的大整数系数分成三部分，利用拆分、评估、逐点相乘、插值、重组五个具体步骤，把九次乘法优化成五次乘法，大大减少了乘法次数，相比于多项式系数直接相乘，本方案速度更快且资源占用更少。

为了验证Toom-Cook-3算法的优化效率，在Intel Cyclone IV E系列EP4CE40F29C8芯片平台上进行仿真实验，结果表明，采用Toom-Cook-3算法，比多项式直接相乘提升了效率，可以解决大整数乘法速度较慢的问题，因此本文提出的多项式优化算法具有一定的研究价值。

基金项目

国家自然科学基金(61370188)；北京市教委科研计划(KM202010015009)；北京市教委科研计划资助(No. KM202110015004)；北京印刷学院博士启动金项目(27170120003/020)；北京印刷学院科研创新团队项目(Eb202101)；北京印刷学院校内学科建设项目(21090121021)；北京印刷学院重点教改项目(22150121033/009)；北京印刷学院科研基础研究一般项目(Ec202201)；北京印刷学院博士启动金项目(27170122006)；北京印刷学院基础研究一般项目(Ec202201)；北京市高等教育学会2022年立项面上课题(MS2022093)；北京市教育委员会科学研究计划项目资助(KM202310015002)；北京印刷学院网络空间安全培育学科建设项目(21090123010)。

NOTES

^*通讯作者。