基于 FPGA 的格密码关键运算模块的设计与实现

随着量子计算技术的发展，量子计算机将能在人们可以接受的时间内破解许多目前计算机无法破解的密码，其中就包括目前大部分公钥密码系统所依赖的大整数质数拆分问题和离散对数问题这两大数学难题。为应对量子计算机为传统密码系统带来的挑战，后量子密码已成为国内外众多学者的重点研究对象。2016年，美国国家标准与技术研究院（NationInstituteofStandardsandTechnology，NIST）开始了一项针对抗量子密码系统的征集计划，旨在寻找、设计、开发和标准化抗量子密码系统，以便于在未来取代现有的密码系统标准。经过3轮的征集提交和筛选，2022年7月NIST发布了首批入围标准的4个抗量子算法：Crystals-kyber、CRYSTALSDILITHIUM、FALCON和SPHINCS+。这4个算法中有3个基于格的数学难题，另一个使用了散列函数。由此可见，基于格的密码方案是抗量子计算密码学中的研究热点。基于格的密码算法中的运算大多为线性运算，因此较其他密码系统，基于格的密码系统具有计算速度快、密钥和密文较小等优势。本文对格密码中的关键模块——多项式乘法进行研究，给出了一种多项式乘法的运算方法和硬件实现架构，并在现场可编程门阵列（FieldProgramGateArray，FPGA）中进行了实现和评估，为格密码硬件实现提供参考。１相关数学基础1.1格密码数学基础线性独立空间上有集合格就是这些向量的线性组合，这一过程的表达式为：式中：系数a均在整数域Z中。任意一组可以生成格的线性无关向量都称为格的基，格的维度等于格的基中的向量个数。目前常用的两个基于格的困难问题是短整数问题（ShortestIntegerProblem，SIS）和错误学习问题（LearningWithError，LWE），但基于上述两个问题的加密方案需要的密钥量大、效率低、资源消耗高，无法在实际中运用。因此，在LWE的基础上提出了环上错误学习（RingLearningWithErrors，RLWE）问题。基于RLWE的加密方案在性能上有着显著的优势，这是现在许多格密码算法的理论基础。RLWE在环上进行操作，其中f是n项的不可约多项式，通常其中n是2的幂，q为素数。1.2环多项式乘法对于RLWE密码算法，其中最为耗时的是环多项式乘法。环多项式乘法有两种实现方式，分别为经典乘法和快速数论变换（NumberTheoreticTransform，NTT）乘法。1.2.1经典乘法经典乘法先把多项式a中的每一项与多项式b中的每一项相乘，再把每个多项式相加得到最终结果。如果多项式a和b的最高次项都为那么计算复杂度为需要个乘法和个加减法。1.2.2NTT乘法NTT是基于快速傅里叶变换（FastFourierTransform，FFT）实现的，其将FFT中的旋转因子由复数变成了整数。设正整数序列其所有元素均小于模数M，有如下NTT变换：式（2）为NTT正变换，式（3）为逆NTT变换。其中，a为模M的N阶本原单位根，满足：在模M下的逆元，满足以下性质：NTT运算是一个递推的过程，图1给出了N=8点的NTT运算结构。如图1中的椭圆标识所示，NTT变换后的结果顺序与原输入顺序呈二进制的倒序关系，因此为避免在计算完成后进行顺序变换，通常采用逆序的方式进行运算，运算结构如图2所示。图3为一次蝶形运算。N通常可以表示为2的幂的形式，则N点NTT运算需要执行次蝶形运算，所以8点NTT需要执行12次蝶形运算。图18

点NTT运算结构图28点

NTT逆序运算结构图3蝶形运算２多项式乘法FPGA实现2.1多项式乘法算法NTT中的每一次蝶形运算都需要做一次乘法和乘法结果取模运算，因此快速完成乘法和取模运算是提高NTT运算效率的关键。本文采用了Longa等人提出的适用于模数的高效取模算法，即LN取模算法，再结合FPGA内部的高效乘法器来实现NTT快速运算。LN取模算法有K-RED和K-RED2x两种形式，如算法1和算法2所示。算法1适用于对加法结果取模，算法2适用于对乘法结果取模。NTT变换和逆NTT变换算法如下：算法3中M为模数，为单位根，N为多项式的项数，如果N不满足2的整数次幂需要补0。步骤6-9为一次蝶形运算。步骤11正变换查逆变换查算法4中的步骤7每运算一次相当于在该项上乘以了k，步骤8每运算一次相当于在该项上乘以如果对步骤8中每个都乘以经过步骤8运算后也相当于该项上乘以k。NTT每一项的运算次数为算法4中步骤2总的循环次数，即次（N为多项式的项数）。所以每项都增加了倍，增加部分可以通过预计算的方式消除。算法5中的步骤1是为了消除NNT运算时每项增加的倍而做的预处理。步骤6中的则是为了消除INNT运算后扩大的倍，并完成INNT运算后的除法运算。2.2多项式乘法FPGA实现多项式乘法的FPGA实现如图4所示。图4多项式乘法FPGA实现2.2.1数据预运算模块数据预运算模块用于对多项式数据进行预处理，同时完成对多项式的倒位序。ROM地址表内存放预计算好的位序映射表。根据ROM读出的地址读取原始序列，预运算后写入NTT模块内的存储器中。2.2.2NTT模块图5为NTT模块的实现。图5NTT实现数据RAM1和数据RAM2为多项式系数存储区，由于FPGA内部实现的RAM通常只有2路通道，不能满足蝶形运算同时对RAM的2次读和写操作。为了解决这个问题，本文设计了RAM1和RAM2两个数据存储区。当RAM1作为数据读取区时，蝶形运算的结果写入RAM2区，当RAM2作为数据读取区时，蝶形运算的结果写入RAM1区，由内部控制模块乒乓切换两个数据区的读写模式。预计算查找表用于存放蝶形运算所需的预计算数据，该数据可以预先计算好后固化在存储区内部，不占用NTT的计算时间。预计算的数据包括蝶形运算及控制模块通过状态机控制NTT的3层循环，以及每次蝶形数据和预计算数据的读取，调用K-RED和完成运算。因蝶形运算下一次的输入数据不会用到上一次的结果，所以蝶形运算可实现流水操作，从而提升运算性能。2.2.3乘法模块乘法模块用于完成算法5的步骤4和步骤6。其中乘法模块1用于完成两个多项式转换到NTT域后各项的相乘，并根据ROM地址表内存放的地址读取多项式的值相乘，将结果存放在NNT的RAM内，用于逆NNT运算。乘法模块2用于完成逆NTT运算结果除N运算和消除运算产生的缩放。由于k通常都不大，内部的和可以转换为由移位和加法实现，不需要乘法运算。３实现结果评估为了便于结果评估，本文选用模数M=12289，并设多项式的项数N=1024，测试平台采用Xilinx公司的XC7K325T型号FPGA。Kuo等人运用了适合于硬件实现的模约减方法，但使用了较多的加法器，编译频率不高。Oder等人使用的模约减模块包含延时较大的关键路径，且存取效率不高，编译频率也较低。本文的蝶形运算模块及LN模运算模块均采用流水线实现，所以实现频率较高，达到了320MHz。由于采用流水实现，预算模块和NTT运算可以并行执行，且NTT内部的蝶形运算模块同样为流水结构，从而大大提高了运算性能。表1为本文多项式乘法硬件实现与现有一些硬件实现的比较结果。其中，查找表（Look-Up-Table，LUT）、寄存器（REGister，REG）、块存储器（BlockRAM，BRAM）和乘法器（DigitalSignalProcessing，DSP）分别为FPGA内硬件资源。表1 多项式乘法硬件评估结果４结 语本文提出的多项式乘法硬件实现方法，采用不