面向格基后量子密码算法的可重构多项式乘法架构

陈 韬 李慧琴 李 伟 南龙梅 杜怡然

(战略支援部队信息工程大学 郑州 450000)

1 引言

量子破译算法对RSA, EIGamal, ECC公钥密码产生了严重的威胁。Shor[1]在1994年发表了名为《Polynomial Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer》(《量子计算机上的质因数分解和离散对数的多项式时间算法》)的论文，认为在量子计算机上实现大整数因式分解仅需多项式时间，而在经典计算机上用现今最快的算法需要指数倍的时间。在此背景下，后量子公钥密码算法设计在网络信息安全领域已成为新兴的研究方向。

美国国家标准技术研究所(National Institute of Standards and Technology, NIST)从2012年开始启动后量子密码方向的研究。2018年，NIST进行了第1轮入围算法的讨论，截止到2020年10月27日，NIST公布了第3轮入围候选者[2,3]，其中包括基于格的算法、基于编码的算法、多变量的算法和Hash函数的签名算法。加密算法包括Classic McEliece, CRYSTALS-Kyber, NTRU与Saber，签名算法包括CRYSTALS-Dilithium, Falcon与Rainbow，其中CRYSTALS-Kyber, NTRU, Saber, CRYSTALS-Dilithium与Falcon都属于基于格的密码。2022年，第3轮标准化结果公布，属于格基密码的CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon确定入选。与其他几种后量子公钥密码算法相比，基于格的密码算法有以下优点：可证明安全性、公私钥尺寸更小、计算速度更快以及在格理论密码系统出现之前，没有合适的问题可以用于构造同态加密系统。综上所述，格基密码方案被认为是最有前途的用于公钥加密和数字签名的后量子密码算法。随着格基后量子公钥密码的不断发展与研究，国内也开始为量子计算机对传统密码算法带来的冲击做准备。2018年11月，由欧洲电信标准化协会主办的第六届量子安全国际会议在京开幕。中国科学院信息工程研究所副所长荆继武在会上表示，中国或将于2022年左右开展后量子密码算法标准化的工作，于2025年左右实现商业化应用落地。此表明未来常用格基公钥密码多样，其中参数结构迥异需要可重构架构去实现。因此，设计一种可满足不同算法中的多项式乘法架构具有重要意义。

针对不同参数，2019年，麻省理工学院的Banerjee等人[4]提出了一种采用Barrett取模算法可重构不同模数的多项式乘法实现方法。最终在不加流水线前提下，最大频率可达100 MHz。2020年，来自慕尼黑工业大学的Fritzmann等人[5]将格基后量子密码扩展到RISC-V架构上实现了3种不同的算法，其中就模数不同的架构和内存上的访问方案进行了探究。此前大多数研究将NTT的旋转因子进行了预计算，并将其存储在单独的内存中，但对于高次多项式会占用过大面积，考虑到动态计算延迟会增加，所以此设计结合预计算和动态微扰度计算的优势，提出了一种混合使用方法。对于次数较大的多项式，例如在NewHope-512和NewHope-1 024中，使用动态计算的方式，否则使用预先计算的表，例如在Kyber算法中应用。针对不同项数和模数，2021年华中科技大学的刘冬生团队[6]针对数论变换参数的多样性，提出一种基于随机存取存储器(Random Access Memory, RAM)的可重构多通道数论变换单元。在数论变换单元设计中，按时间抽取的基础上改进多通道架构，并提出一种优化地址分配方法。

针对不同格基后量子公钥密码算法，项数相同，且模数都在16 bit以内的Kyber与Saber算法经常作为可重构多项式乘法的研究对象。2020年，文献[7]中的设计采用单路迭代的方式，迭代使用模乘单元实现Kyber, Saber与Newhope算法中的多项式乘法，此方法花费时间较长但占用较小面积。2022年，华中科技大学团队基于此两种算法采用Schoolbook和Toeplitz方法来实现[8]，针对每种算法进行了资源效率和性能权衡策略下可变参数和指令编程的灵活实现。此外，以同一团队提出的Kyber与Dilithium算法为研究对象也是常见选择[9]，针对不同模数进行模乘单元的可扩展重构设计。清华大学刘雷波团队[10]提出的设计作为支持算法最多的硬件实现，可支持Kyber, Saber, NTRU, Dilithium, McEliece与Rainbow等6种格基后量子公钥算法，采用阵列的形式最大限度地复用运算单元。因此，通过分析不同格基后量子公钥密码中多项式乘法运算特征，得到不同重构参数需求，提出统一运算网络是目前关键方向之一。

针对上述分析，本文提出一种面向多种难题格基后量子公钥密码算法的可重构多项式乘法架构。通过分析不同参数多项式乘法的PtNTT实现算法，就其核心操作特征设计得到一个满足实现不同基次的4×4串并行可转换运算单元架构，并设计了其内部的可重构模乘单元。面向不同格基后量子密码公钥算法中的多项式乘法进行系数地址的分配需求分析，具体体现在系数地址生成逻辑、同个RAM中Bank划分逻辑以及实际地址与虚拟地址对应逻辑。实际来看，是在前述运算单元最佳性能范围内实现数据分配机制的优化，基于上述机制得到一种满足基k-NTT的多Bank数据存储结构。

2 多项式乘法运算特征分析

2.1 多项式乘法重构参数分析

面对未来对多种格基后量子密码算法的需求，只是设计满足一种参数或形式的多项式乘法具有局限性。本节希望采用同种形式算法，为多种参数形式的多项式乘法构造出一种可重构架构。在NIST第3轮候选标准算法范围内，除了Falon算法需采用FFT来实现多项式乘法，其余算法都可采用NTT或变换后的算法实现。

依据不同算法中乘法的具体参数，将其总结为3种不同形式的差异——项数n、模数q以及模多项式f(x)。较多文献针对的多项式乘法参数多为符合Kyber, Saber和Dilithium的2的幂次项数，关于NTRU中的素数项数涉及较少，通过文献[11]的阐述，可通过扩展项数使得其实现可使用NTT算法。模数中，有满足q=1modn素数参数的Kyber与Saber算法，也有符合Dilithium与NTRU算法的2的幂次模数，前者可采用PtNTT算法架构的实现方式达到高效的目标，同时由于模数位数差别较大，需要构造适应不同参数的模乘运算硬件结构，后者可通过扩大模数的NTT操作后直接取低位。此外，需要注意不同模多项式对于采用算法中参数的影响。

其中，ωn=1 modq，ωn/2=-1 modq。如图1(b)所示。通过对比上述两种不同的模多项式，可观察到不同算法除了对应单位根不同，其运算结构具有相似性。

图1 不同模多项式依据中国剩余定理映射示意图

在NTRU算法中，当模多项式为(xn–1)/(x–1)=xn–1+xn–2+···+1时，可先使用NTT方法进行扩项数后的模xn–1的运算，再进行模xp–1的运算。由于xp–1+xp–2+···+1是xp–1的因式，所以可以先进行约简高次多项式，再约简因式低次多项式的方式。最后通过判断比较系数得到模xp–1+xp–2+···+1的多项式。

上述重构参数分析后可总结为不同格基后量子公钥密码算法的多项式乘法架构特征：都可采用NTT算法的思想来实现，可采用相似的蝶形运算架构；其具体操作包括不同长度的模乘与模加减，位宽在32 bit以内；整体实现方式为多轮相同操作迭代完成，适合深度流水和高度并行操作处理。

2.2 可重构多项式乘法运算网络分析

基于上述关于格基后量子公钥密码算法中多项式乘法运算特征的分析，本小节将通过整理具体算法中的运算流程，总结出可重构核心运算单元架构。可重构实现不同参数的多项式乘法时，将其分类为可直接用PtNTT算法实现、通过扩大模数间接采用PtNTT算法以及通过同时扩展模数和项数采用混合基PtNTT算法来实现。

第1种分类具体包括Kyber和Dilithium算法，项数256都为4的幂次，且模数和项数都满足q≡1modn，不同的仅有模数大小，需通过可重构模乘单元的设计来解决不同模数位数大小的现状。第2种分类只包括Saber算法，其模数为2的幂次，不能直接使用NTT算法来实现，可通过将模数扩展为NTT友好的数据量，且要求为最小友好数据。既保证了可采用NTT这一本身计算复杂度低的算法，又可尽量减少多余位数增加的面积消耗和时间损耗成本。最后一种分类则是以NTRU为主体的不同参数算法，其项数为素数，模数为2的幂次。此类项数已不满足n为2的幂次这一条件，为了解决此问题，只能通过扩展项数使其可通过NTT算法来实现。在扩域过程中，由于此类算法模多项式有(xp-1)/(x-1)与xp-1，先采用NTT算法实现模xn-1， 再根据传统模多项式的算法进行模xp-1操作。这就要求在扩域时，项数扩展必须大于原来的两倍，且尽可能小。在选择扩展后的项数时，需使用混合基NTT的算法，为实际减小项数带来的面积和时间成本大幅度降低提供可行性。最终适于可重构架构的多项式乘法参数如表1所示。

表1 适于可重构架构的多项式乘法参数

其中出现次数最多的项数为256，且为4的幂次，其余项数509, 677, 821与701可分别扩展为256×4, 512×3, 9×64×3与512×3。256, 512,9×64代表采用NTT算法的项数，其中包括2, 3与4的幂次，说明可重构架构需同时满足基2, 基3与基4的基本运算操作；“×4”“×3”则说明需要分成3组和4组进行PtNTT算法的分组点乘计算。以NTRUhps4096821算法为例，其实际运算流程为如算法1所示。

根据上述流程需要确定可重构核心运算单元所支持的基k-NTT算法，最频繁出现的为基4操作，且实质上是基2操作的两层复合操作，所以需要尽可能通过并行或串行基2来实现基4；基3则是为支持尽可能减少较大项数出现的操作，其完整实现也是必不可少的。算法2—算法4详细描述了不同基k-NTT算法的核心运算流程。

其中，i=0,1,2,...,n/3-1。

如表1所示，算法5中的T0, T1与算法6中的T2,T3进行的是相同的运算，算法5中的T2, T3与算法6中的T0, T1进行的是相同的运算，具有可重构的基础。此外，已知需要一种架构同时实现基4、基3与基2的蝶形运算，且基4的基本操作需要4个乘法，可同时满足4次基2的操作，基3的基本操作则是需要3个乘法，选择基4或基2与基3重构需要明确。若选择基2与基3蝶形运算进行重构，实现1次核心操作，基2运算会浪费1个乘法单元，基4运算会浪费2个乘法单元；若选择基4与基3蝶形运算进行重构，仅基3运算浪费1个乘法单元。所以采用基4核心基本运算单元，在此基础上，进行其他运算功能的增加。

则a(x)=a0(z)+x·a1(z)+x2·a2(z)， 同 理b(x)=b0(z)+x·b1(z)+x2·b2(z)。最终乘积结果多项式用c(x)表示。

算法1 NTRUhps4096821采用混合基PtNTT的多项式乘法

算法5 基4-NTT算法的核心运算操作拆解，其中µ=ωn/4

上述公式推导了3路采用PtNTT算法进行点乘运算的具体流程，4路点乘运算与之同理，下述表格中的算法具体列出了化简后的流程。由于点乘操作是在多项式乘法中NTT与INTT之间进行的，故仅将点乘流程在下述表格中体现出来，如算法7、算法8所示。

算法7 4路PtNTT中的点乘算法

通过上述分析，不同格基后量子密码算法中多项式乘法核心操作的实现都有共通之处，通过提炼相似操作，以最小的面积冗余实现不同参数的多项式乘法。

3 可重构多项式乘法运算架构设计

3.1 串并行可转换型运算单元架构

依据第2节关于核心运算可重构过程的建立，需构建一个同时满足基4、基3与基2操作的核心蝶形运算架构。根据算法5中针对基4-NTT核心运算操作拆解，具体结构如图2所示。

图2 基4-NTT/INTT核心蝶形运算架构图

若本设计以上述蝶形运算架构为基础进行可重构单元的搭建，带来的面积冗余过大。以红框内的3个模乘单元为基准，前后需要各添加1个模乘单元，模加减单元数量并不会降低。观察到其拆解运算具有高度重合性，将具有相同操作的连线用相同颜色标注出来，整体可重构运算单元与单个基4-NTT/INTT内包含的模乘单元数量相同，将操作分为4个部分，即PE0, PE1, PE2与PE3。同理，基3蝶形运算也可在4个PE内实现。

故实现基4数论变换算法结构至少为2×2、包含4种不同分操作的基本运算单元 (PE0, PE1,PE2与PE3)，其中的具体分操作是对基4与基3的可重构转化。本设计面向算法的参数要求为0～32 bit，若仅将其中最大位宽固定到32 bit，对于小位宽的多项式乘法，将带来3/4面积上的冗余，不满足可重构中关于“有效利用硬件资源从而达到节约逻辑资源”的要求[12]。此扩展性设计被舍弃，故将最大位宽缩小到16 bit，满足最小参数为3 329(12位)的要求。因此，2×2运算单元可实现1次16 bit的基4/3的核心操作。当实现16～32 bit参数的多项式乘法时，一个2×2运算单元仅能实现1次32 bit基4/3的核心操作中涉及乘法的1个步骤。考虑到对于最大工作频率的限制，需要全流水实现。若通过复用此基本运算单元架构，浪费时间周期数较多，带来的性能损耗较大，故设计为4×2×2(4×4)的整体运算单元架构，可完整实现1次32 bit的基4/3的核心操作。整体电路结构如图3所示。

图3 串并行可转换型运算单元结构图

上述结构图对重构设计进行了描述，其中4个可重构核心运算单元(单元1—单元4)构成了整体运算架构，仅在并行计算点乘中的Ri,j时，其支持的运算略有不同。此外，在实现32 bit模乘时，各单元内的PEi共同实现图4的功能，每个PEi完成其中的1个乘法和附加运算，实际上PEi内的单个乘法实现的是32 bit乘法(图4单元中的选择信号sel为0时)。

图4 适于Kyber算法的4-Bank存储系数情况

图3将单元一的运算框图进行了具体描绘，其复杂的连接和选择关系代表可同时实现16 bit基4/3/2的NTT和INTT算法操作，红蓝箭头代表虚线框内基于数据选择器的互连关系。①代表单元内部PEi之间的互连，实现16 bit基4/3/2的NTT和INTT算法操作；②代表单元之间同种PE以及不同单元之间首末PEi的互连，实现32 bit基4/3/2的NTT和INTT算法操作。

3.2 可重构模乘单元设计

根据第2节针对模数的总结分析，模数支持位宽为0～16 bit与17～32 bit。直接设置大比特位宽是一种解决思路，然而相较于小比特位宽具有较大的面积冗余，且为了支持未来可能出现的其他位宽模数，本设计将通过串行16 bit的模乘来实现3 bit的模乘，同时通过运算单元的并置来实现4个16 bit的模乘。既解决了实现小比特位宽运算带来的面积冗余，也避免了小比特位宽串行实现导致的时间成本的增加。

选择具体模乘算法实现时，Montgomery算法与Barrett算法均具有较好的可重构功能，支持任意比特的模乘。32 bit Montgomery模乘算法具体需要3个32 bit乘法，但需要进行预处理与后处理，时间成本会成倍增加；32 bit Barrett模乘算法则具体需要4个32 bit乘法，32 bit乘法可通过4个16 bit乘法组合实现，16 bit Barrett模乘算法也可通过此4个16 bit乘法实现，如算法9所示。从而可获得既可实现16 bit模乘又可实现32 bit乘法的可重构模乘单元结构。

4 多项式乘法存储数据分配机制

4.1 满足基k-NTT的数据分配机制

(1) Kyber与Saber算法

整体采取基4-2PtNTT方法来实现，即整体4×4单元其中每1×4单元实现n=64的基4 NTT操作。以装载64个多项式系数的空间为1个RAM单元，需要同时读写4个数据。可得到具体的分组情况如图4所示。

图4所示的4-Bank存储系数的划分情况完全符合图5所示Kyber算法中多项式乘法NTT/INTT要求的地址互斥关系。其次就地址生成规律与划分规律进行讨论分析。理论上需要3种计数器进行地址的生成，应将其进行精简优化。根据算法要求，分配方案需要同一周期在一个RAM(N/4，也为下面论述中的n项)中读出4个数据，其余3项数据可在基数据的基础上进行改变。例如在第1子轮16项数据的基础上加上0x010000, 0x100000与0x110000。最外部需要1个计数器Cnt0，总共运行log4n轮，内部循环Cnt1计数n/4次。内部循环每满4log2n-1-Cnt0加上 4log2n-Cnt0，变化量实质上与Cnt0有关，所以无需新添计数器的数目。

图5 Kyber算法中多项式乘法NTT/INTT地址互斥连通图

故第1 子轮基数据为0 x 0 0 X X X X，其中XXXX代表Cnt1值，循环加1；第2子轮基数据为0xXX00XX；第3子轮基数据为0xXXXX00。其余3项数据在基数据基础上，将其中00替换为01, 10和11。所以最终地址在Cnt0和Cnt1的控制下进行转换。

整体划分规律则是按照二进制“1”的奇偶个数进行划分，偶数个“1”划分为第0、第2个Bank，奇数个“1”划分为第1、第3个Bank。然后按照a[0]^a[4], a[3]进行划分，在第0、第2个Bank中，当a[3]为1且a[0]^a[4]为0或a[3]为0且a[0]^a[4]为1时，划分为第2个Bank，反之分为第0个Bank。在第1、第3个Bank中，当a[3]为1且a[0]^a[4]为0或a[3]为0且a[0]^a[4]为1时，划分为第1个Bank，反之分为第3个Bank。高log2n–2位代表其在Bank内的实际地址。Saber算法参数类型与之相同。

(2) Dilithium算法

与Kyber相似，Dilithium算法内多项式乘法项数同为256，但其模数以及适应NTT形式不同。此算法可完全按照传统NTT算法来实现，本文为减少控制结构的复杂性，故同样采用基4-2PtNTT算法来实现，由于模数长度为Kyber算法的两倍，需要4×4个运算单元，每1×4个运算单元实现基4中1个阶段的32 bit模乘运算，最终共同实现1次32 bit基4操作。一个装载64个多项式系数的RAM单元，也需要同时读写4个数据。地址生成规律、Bank划分规律与Kyber算法相同，只是将a[3]转换为a[3]^a[7]。

算法9 16 bit模乘、32 bit乘法

(3) NTRUhps2048509算法

经过第2节针对NTRU算法进行NTT友好型参数转换后，其项数为1 024，整体采用基4-2Pt-NTT方法。以装载256个多项式系数的空间为一个RAM单元，需要同时读写4个数据。与前两种分配方式相比，每个Bank内的存储量增加，不同类算法可重构实现表明可共用存储面积。且为了控制结构复杂度降低，分配方式需要同时满足两者的要求。所以前文所满足的多种分配方式既需要满足此算法的要求，也需要降低控制结构复杂度。

实际上，在对Kyber与Dilithium中小项数的划分情况进行分析时，其具体分组情况具有多样性，并不如图4所示仅有1种划分情况。为保证此算法中对应的大项数划分可成功实现，减少由于地址生成逻辑复杂性的提高带来整体单位面积性能的降低，将划分情况更加偏向大项数划分，在满足此类情况的划分前提下同时满足Kyber, Dilithium中小项数的划分情况，即Bank划分规律上述算法是相一致的。

地址生成规律实质上也与第(1)节陈述类似，本质在于项数不同带来的计数范围的不同。Cnt0,Cnt1分别与log4n, n/4有关。其地址生成规律变为了第1 子轮基数据为0 x 0 0 X X X X X X，其中XXXXXX代表Cnt1值，循环加1；第2子轮基数据为0xXX00XXXX；第3子轮基数据为0xXXXX00XX；第4子轮基数据为0xXXXXXX00。其余3项数据在基数据基础上，将其中00替换为01, 10和11。

(4) NTRUhps2048677与NTRUhrss701算法

第2节针对NTRU算法进行NTT友好型参数转换后，其项数都为1 536(512×3)，整体采用基2数论变换与3路预处理相结合的方法。以装载512个多项式系数的空间为一个RAM单元。作为分组数据较大的算法，且针对32 bit基2蝶形操作的4路并行实现方案，需要同时读写4个数据。

其地址生成规律与基二蝶形操作相关，与上述基4操作具有相通之处。Cnt0, Cnt1分别与log2n,n/2有关。其地址生成规律变为第1子轮基数据为0 x 0 X X X X X X X X，其中X X X X X X X X 代表Cnt1值，循环加1；第2子轮基数据为0xX0XXXXXXX；依此类推，最后1子轮基数据为0xXXXXXXXX0。其余一项数据在基数据基础上，将其中0替换为1。

(5) NTRUhps4096821算法

作为NTT友好型参数转换后项数最大的多项式乘法，其项数为1 728(9×64×3)，整体采用混合基数论变换与3路预处理相结合的方法。需要先进行基3数论变换运算，再进行基4数论变换运算，然后进行点乘，最后进行逆数论变换运算。

由于是混合基次数论变换，其地址生成逻辑与上述论述出入较大，同样保证以简单的布尔逻辑与循环计数来实现。基3数论变换以64为数量单位的地址块为整体进行地址转换，则简化为n=9的蝶形操作，扩展到64×9可直接通过移位实现；基4数论变换则以9为数量单位的地址块为整体进行地址转换，与上述基4数论变换地址生成规律吻合，即与第(1)节论述完全相同。

在对Bank划分规律进行分析前，需要注意的是，在混合基次过程中基数变换的这一阶段，由于存在读出的数据经过运算不再写回到原来的地址上这一问题。若以增加存储面积作为代价，多出1倍的存储区，分别用来存储3-Bank与4-Bank的数据。本身作为最大项数的多项式乘法，其存储面积占用较大，使得其他算法的实际有效占用率较低。此问题主要出现在基3与基4混合基操作时，同一系数在不同分配操作中占据不同的Bank与实际内存地址。所以解决思路为不额外占用存储面积的前提下完成虚拟地址与实际地址的相统一。

为使地址相统一，将RAM划分为3与4的最小公倍数——12个Bank。同时以两种划分规律为抓手，分为0.BankA、1.BankB、···、2.BankC与2.BankD。但实际上，若是均匀分配(按照63×11+70)，最终并不能正确匹配实际运算过程中的地址，会出现读写数据有可能会存在于同一Bank中从而产生读写数据冲突。需通过整块地址的调整最终得到可同时满足基3与基4的多Bank数据存储方案。

以适应基3的存储量9的存储单元为整体，称为存储块。存储块内的系数地址是连续变化的，则存储块的块号是以适应基4的存储量64进行计数，可划分为4个Bank；当以适应基4的存储量64的存储单元为整体，称为存储条。存储条内的系数地址是连续变化的，则存储块的块号是以适应基3的存储量9进行计数，可划分为3个Bank。最后综合来看可分为12个Bank。为方便实际地址到内存地址的转换，以存储块的形式进行保存。最终具体12Bank地址划分如图6所示。

图6 12-Bank地址划分标识图

设计在应用于多种算法中的多项式乘法时，此RAM存储方式中1 Bank中存储数据量最大为54，第(1)(2)(3)节中每个Bank最大存储量为64，与之相近，无需修正。但只占用4个Bank，在控制逻辑中，可将其余无用Bank不添加进可选择范围内。第(4)节中每个Bank最大存储量为128，为最大限度增大存储面积的有效占用率，可将此类算法存储模式分为8个Bank，将每个Bank存储量降为64，前提需将此Bank划分满足其地址的读写互斥关系。

4.2 满足基k-NTT的存储单元设计

数据分配机制确定后，需要根据具体算法的实际需求设计出具有精简式控制结构的存储单元，控制完成多项式系数的调度，计数使能信号的产生和转换以及其他关键控制信号的产生。

在此基础上精简存储单元的复杂度，并行度为16，RAM分组组数为12，每一轮运算地址的转换需要计数器进行辅助设计。以最简单的基4蝶形操作为例，l og4(n/4)轮运算之间需要1个计数器Cnt0进行轮数k的更新；每一轮运算内部需要1个计数器Cnt1进行4k次系数的调度；具体进行系数调度时，计数器Cnt2进制/与第1个轮数计数值Cnt0有关，每当加到(n/16)4k重新以全新的数字进行计数。若按照此设计方法至少需要3个计数器，最终4个读地址由3个计数器的值加减组合得到。针对这一问题，需要通过布尔函数，移位等简单逻辑运算将地址转换进行优化，从而减少计数器的数目。

将计数器Cnt1(Cnt_Addr)进数值设置为基本的n/4，实际系数是在此基础上通过移位或其他简单运算产生；计数器Cnt0(Cnt_RAM)将Cnt1的进位信号作为计数使能信号；Cnt2则是计数器Cnt0值和Cnt1值共同决定，不需要再设置冗余的计数器。最终读写地址则是由计数器Cnt1值硬连线形成，根据Cnt_RAM值的不同，在读数时，决定在不同的位置插入“00”, “01”, “10”或“11”。A ddr={2′bZ0,Cnt_Addr[log2n/4-1,0]}，填充的数据取决于不同的Bank选择，填充位置则是由实现NTT的轮数Cnt0有关。根据地址汉明重量的奇偶性以及其中3位的不同将其分为4组。对于不同Bank地址的选择生成逻辑具体为

对于单个Bank的地址生成逻辑Addr_Bank_wt=Addr_wt>>2， Addr_Bank_rd=Addr_rd>>2。对于图7中的sel_x信号对应上述地址选择生成公式括号内的判断条件。

图7 多端口RAM单元硬件设计框图

若是较为复杂的混合基运算，由于在不同的基k蝶形操作中，存储块内的数据量是不同的。整体以块号为地址生成逻辑的基础，之前基地址的简化生成方式实际上利用了二进制表示的优势，所以基3操作中基地址的形成以及其余地址的衍生不能伴随简单的硬连线完成。只能通过算法中简单的乘加实现，×3通过移位和加来实现，×9则是迭代实现两次×3。其次针对混合基多Bank的划分规律进行分析，实际上是基于数据量为9存储块的块号进行划分，则是先根据基3的Bank划分规律——当(a[0]+a[1])mod3=0，划分到第0个Bank；当(a[0]+a[1])mod3=1，划分到第1个Bank；当(a[0]+a[1])mod3=2，划分到第2个Bank。再根据上述基4蝶形操作中Bank划分规律得到12Bank的具体划分形式。最后将问题聚焦到系数对应虚拟地址至Bank内实际地址的转换，混合基中多Bank中不再是上述可以直接通过简单移位来实现地址转换。且为了更容易兼容未来不同种情况的混合基地址转换情况，设置4个查找表，将虚拟地址与实际地址进行对应，即4个6×576 bit大小的ROM存储其对应关系。最终基于PtNTT算法中其中一个分组对应的存储单元及对应控制结构如图7所示。

存储单元进行Bank分配不冲突的优化，实现了在不同的运算阶段，读出和输入地址不冲突且Bank数量最小，从而保证了地址分配最优的多端口RAM设计。

5 结果与比较

本文通过Vivado 2 019.1软件进行仿真综合，芯片型号为Artix-7中的xc7a35tfgg484-3，最高工作频率可达到152 MHz，共占用13 794个LUT硬件资源。

通过查阅并列举近几年相关文献，发现与NTRU算法中的多项式乘法可重构架构相对较少，Kyber算法则是作为较易重构的架构，由于与Saber算法中项数相同易于重构，与Dilithium则是同一团队研发，可采用相同的NTT算法架构。本文则是将上述4种格基后量子密码算法中的多项式乘法进行重构。

从可重构功能和具体实现方式来说，文献[7]中的设计支持NewHope, Kyber和Saber中16 bit以内的多项式乘法，且为低并行度实现，占用面积小但花费周期数较多。文献[8]虽然同时支持Kyber, Saber中的多项式乘法，然而分别采用Schoolbook和Toeplitz方法来实现，实际上使用两种不同的乘法器，并不是可复用的，起码会占用36个Toeplitz乘法器与支持Kyber算法中NTT实现方法的模乘单元。

文献[9]、文献[10]都是支持Kyber与Dilithium中多项式乘法的重构。文献[9]中两种参数的花费时钟周期数相同，说明其关键路径限制在32 bit相乘，再加上32路蝶形运算单元，优点是时钟周期数较少，但单位面积性能不高。文献[10]支持算法众多，主要分为两类—采用NTT方法实现的Kyber与Dilithium算法，采用分层Karatsuba方法的Saber,NTRU算法，在25 nm工艺下工作频率高达500 MHz。虽然其占用面积较大，然而实现功能较多，可支持基于不同难题算法对应的多项式乘法。文献[13]中则是将Dilithium与Saber算法中的多项式乘法同时采用NTT架构来实现的，通过改变扩大Saber算法中的模数共用蝶形单元架构，与本文设计思想相近。要说明的是，文献[10]与文献[13]是基于ASIC条件下完成，故未在表2中体现。

表2 基于FPGA不同多项式乘法架构性能对比

文献[14]提出了一种高效的混合基数MDF NTT架构，适用于高性能大规模数据密码处理器。灵活的设计使NTT架构适应各种参数集并且基数值的合理选择有助于实现高性能。其支持Kyber以及与之参数要求相同的NewHope算法(现已落选)，灵活性范围有限。文献[6]则提出一种基于随机存取存储器(Random Access Memory, RAM)的可重构多通道数论变换单元支持实现项数256～2048，模数在32 bit范围内。灵活性强的关键在于设计了基于RAM的可重构模乘单元，针对特定参数(满足q≡1mod2n条件)优化的模乘器在资源消耗方面具有明显的优势，但不适用于多参数可重构设计。

通过上述分析，本文设计了实现Kyber, Saber,Dilithium和NTRU等4类算法中多项式乘法的可重构架构。在面向未来可能出现的格基后量子公钥算法的形势下，本文提出的架构具有高灵活性的优势。经对比可得，采用PtNTT算法的多项式乘法单元架构其时延性能较多优于其他文献中的数据。这是由于选用算法本身带来的时间复杂度低，4×4并行结构和统一化运算单元保证在性能上的提升。

整体来看，本文所提基于PtNTT算法可重构多项式乘法架构，支持4种格基后量子公钥密码，为未来针对可重构目标的多项式乘法提供架构设计建议。

6 结束语

本文通过论述针对多项式重构参数的分析，为后续可重构网络的建立提供理论基础。具体来看，通过分析不同参数多项式乘法的PtNTT实现算法，就其核心操作特征设计得到一个满足实现不同基次的4×4串并行可转换运算单元架构，并设计了其内部的可重构模乘单元。面向不同格基后量子密码公钥算法中的多项式乘法进行系数地址的分配需求分析，具体体现在系数地址生成逻辑、同个RAM中Bank划分逻辑以及实际地址与虚拟地址对应逻辑，基于上述机制得到一种满足基k-NTT的多Bank数据存储结构。为可重构多项式乘法提供架构设计建议。