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

摘  要：格密码是后量子密码中的一项重要技术，为提高格密码运算效率，提出了一种格密码中多项式乘法的硬件实现方法。该方法利用现场可编程门阵列（Field Program Gate Array，FPGA）内部存储器存放多项式系数，采用乒乓结构提高存储器并行读写速度，并通过预计算和预缩放简化计算过程，降低计算复杂度。同时，采用多级流水线技术，减少存取时间和蝶形运算等待时间，提升整体编译频率，提高运算性能。评估结果表明，该方法最大工作频率达到了 320 MHz，完成一次 1 024 项多项式乘法运算的时间为 41 μs。

内容目录：

1 相关数学基础

1.1 格密码数学基础

1.2 环多项式乘法

2 多项式乘法 FPGA 实现

2.1 多项式乘法算法

2.2多项式乘法 FPGA 实现

3 实现结果评估

4 结  语

随着量子计算技术的发展，量子计算机将能在人们可以接受的时间内破解许多目前计算机无法破解的密码，其中就包括目前大部分公钥密码系统所依赖的大整数质数拆分问题和离散对数问题这两大数学难题。

为应对量子计算机为传统密码系统带来的挑战，后量子密码已成为国内外众多学者的重点研究对象。2016 年，美国国家标准与技术研究院（Nation Institute of Standards and Technology，NIST）开始了一项针对抗量子密码系统的征集计划，旨在寻找、设计、开发和标准化抗量子密码系统，以便于在未来取代现有的密码系统标准。经过 3 轮的征集提交和筛选，2022 年 7 月 NIST 发布了首批入围标准的 4 个 抗 量 子 算 法：Crystals-kyber、CRYSTALS DILITHIUM、FALCON 和 SPHINCS+。这 4 个 算 法中有 3 个基于格的数学难题，另一个使用了散列函数。由此可见，基于格的密码方案是抗量子计算密码学中的研究热点。基于格的密码算法中的运算大多为线性运算，因此较其他密码系统，基于格的密码系统具有计算速度快、密钥和密文较小等优势。本文对格密码中的关键模块——多项式乘法进行研究，给出了一种多项式乘法的运算方法和硬件实现架构，并在现场可编程门阵列（Field Program Gate Array，FPGA）中进行了实现和评估，为格密码硬件实现提供参考。

１相关数学基础

1.1 格密码数学基础

线性独立空间上有集合 格就是这些向量的线性组合，这一过程的表达式为：

式中：系数 a 均在整数域 Z 中。任意一组可以生成格的线性无关向量都称为格的基，格的维度等于格的基中的向量个数。

目前常用的两个基于格的困难问题是短整数问题（Shortest Integer Problem，SIS）和错误学习问题（Learning With Error，LWE），但基于上述两个问题的加密方案需要的密钥量大、效率低、资源消耗高，无法在实际中运用。因此，Lyubashevsky 等人 在 LWE 的基础上提出了环上错误学习（Ring Learning With Errors，RLWE）问题。基于 RLWE 的加密方案在性能上有着显著的优势 ，这是现在许多格密码算法的理论基础。RLWE 在环 上进行操作，其中 f 是 n 项的不可约多项式，通常 其中 n 是 2 的幂，q 为素数。

1.2 环多项式乘法

对于 RLWE 密码算法，其中最为耗时的是环多项式乘法。环多项式乘法有两种实现方式，分别为经典乘法和快速数论变换（Number Theoretic Transform，NTT）乘法。

1.2.1 经典乘法

经典乘法先把多项式 a 中的每一项与多项式 b中的每一项相乘，再把每个多项式相加得到最终结果。如果多项式 a 和 b 的最高次项都为 那么计算复杂度为 需要 个乘法和 个加减法。

1.2.2 NTT 乘法

NTT 是 基 于 快 速 傅 里 叶 变 换（Fast Fourier Transform，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 运算结构

图 2 8 点 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.2 NTT 模块

图 5 为 NTT 模块的实现。

图 5 NTT 实现

数据 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=12 289，并设多项式的项数 N=1 024，测试平台采用 Xilinx公司的 XC7K325T 型号 FPGA。

Kuo 等人 运用了适合于硬件实现的模约减方法，但使用了较多的加法器，编译频率不高。Oder 等人使用的模约减模块包含延时较大的关键路径，且存取效率不高，编译频率也较低。本文的蝶形运算模块及 LN 模运算模块均采用流水线实现，所以实现频率较高，达到了 320 MHz。由于采用流水实现，预算模块和 NTT 运算可以并行执行，且 NTT 内部的蝶形运算模块同样为流水结构，从而大大提高了运算性能。表 1 为本文多项式乘法硬件实现与现有一些硬件实现的比较结果。其中，查找表（Look-Up-Table，LUT）、 寄 存 器（REGister，REG）、块存储器（Block RAM，BRAM）和乘法器（Digital Signal Processing，DSP） 分 别 为 FPGA 内硬件资源。

表 1  多项式乘法硬件评估结果

４结  语

本文提出的多项式乘法硬件实现方法，采用不完全模约减的方式取模，大大减少了取模的时间。同时采用了乒乓切换、流水技术和双 NTT 模块架构，一方面提高了存储器读写带宽，另一方面减少了运算过程中的等待时间，从而提升了运算性能。此外，由于采用了流水设计，编译主频也较高，达到了 320 MHz。因此，本设计无论是在资源占用方面还是在处理性能方面都具有一定的优势，对基于格的后量子密码的硬件实现具有一定的参考意义。

引用格式

引用格式：韩炼冰 , 房利国 , 王松 , 等 . 基于 FPGA 的格密码关键运算模块的设计与实现 [J]. 通信技术 ,2022,55(12):1613-1617.

作者简介 >>>

韩炼冰，男，学士，高级工程师，主要研究方向为信息安全、通信安全技术；

房利国，男，硕士，高级工程师，主要研究方向为信息安全、通信安全技术、计算机应用；

王  松, 男，学士，高级工程师，主要研究方向为信息安全、通信安全技术；

刘鸿博，女，学士，高级工程师，主要研究方向为信息安全、通信安全技术；

杨敏旭，女，学士，工程师，主要研究方向为信息安全、通信安全技术。

选自《通信技术》2022年第12期（为便于排版，已省去原文参考文献）

声明：本文来自信息安全与通信保密杂志社，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。