一种格密码加解密中的环多项式乘法器电路

摘要

本发明公开了一种格密码加解密中的环多项式乘法器电路，具有高并行度，在FPGA硬件实现时达到了减少时间周期以及高吞吐率的效果，并简化了控制单元。同时，结合具体参数可将其中一个多项式乘法的系数采用有符号数表示，可在FPGA中单个DSP模块同一时钟完成两次乘法，优化模约减，大大加快了格密码加解密效率，减少了资源的消耗。

说明书

技术领域

本发明属于格密码硬件实现领域，特别涉及了一种环多项式乘法器电路。

背景技术

量子计算机的产生，会对现有的密码体制造成很大的威胁，格密码是一类最有希望的能够抗量子攻击的后量子密码，而环多项式乘法是基于RLWE(Ring Learning WithErrors)和MLWE(Module Learning With Errors)问题的格密码加密和解密操作中计算最为复杂，消耗资源与时间的最多操作，是影响格密码硬件实现性能的关键部分。在整数域上，给定两个多项式a(x),b(x)，形如：

将这样两个多项式直接相乘后得到多项式

这种按常规方法去得到两个多项式相乘后的结果的方法又叫做Schoolbook多项式乘法(Schoolbook Polynomial Multiplication,SPM)。在基于RLWE和MLWE问题格密码中的数多为素数q为模的整数环域Z

其中a(x),b(x)系数相乘后a

在软件上实现SPM可以采用循环判断的简单算法去实现，但是在硬件架构上实现环多项式乘法并不那么容易，乘法和加法都是模乘和模加，通常要消耗大量时间周期和资源。为了减少环多项式乘法硬件实现的资源，有研究者提出了只采用一个或两个乘法器，牺牲时间周期的环多项式乘法单元，这使得格密码加密和解密执行时间多用在多项式乘法中，在需要进行多个多项式乘法时消耗了大量时间，因此对SPM环多项式乘法单元减少执行时间周期是十分有意义的。

发明内容

为了解决上述背景技术提到的技术问题，本发明提出了一种格密码加解密中的环多项式乘法器电路。

为了实现上述技术目的，本发明的技术方案为：

一种格密码加解密中的环多项式乘法器电路，包括256个6比特移位寄存器、128个有符号双模乘单元、256个13比特寄存器和控制单元；所述控制单元输出控制信号Crl_S和地址信号addr_ab，所述控制信号Crl_S表示有符号双模乘单元中的符号标志位；将多项式b(x)的256个系数按照b

进一步地，所述有符号双模乘单元包括两个模约减单元、两个异或运算器和一个乘法运算器；所述有符号双模乘单元的输入为多项式b(x)相邻两个系数b

在第一个时钟周期，将b

在第二个时钟周期，将数据x的高18位数据输入一个模约减单元，将数据x的低18位数据输入另一个模约减单元，所述模约减单元包括依次连接的移位单元、第一减法器、加法器和第二减法器，两组18位数据通过所述模约减单元实现如下操作：

对18位数据的高5位数据通过所述移位单元进行左移9位操作后得到14位数据，再通过所述第一减法器减去前述高5位数据得到14位数据，再通过所述加法器加上18位数据的低13位数据得到14位数据，判断该14位数据是否大于模值7681，若是则通过所述第二减法器减去模值7681，最终模约减单元输出小于模值7681的13位数据；

在第三个时钟周期，将b

采用上述技术方案带来的有益效果：

本发明在硬件实现时达到了减少时间周期以及高吞吐率的效果，同时简化控制单元。同时，结合具体参数可将其中一个多项式乘法的系数采用有符号数表示，在FPGA中可在单个DSP模块同一时钟完成两次乘法，同时优化模约减，大大加快了格密码加解密效率，也减少了资源的消耗，若采用其他格密码参数时候，该结构经过增加乘法单元数量和修改模约减单元，通用于其他格密码参数。

附图说明

图1是环多项式乘法运算法则示意图；

图2是环多项式乘法的时序策略示意图；

图3是本发明中有符号双模乘单元结构图；

图4是本发明中环多项式乘法器电路图。

具体实施方式

以下将结合附图，对本发明的技术方案进行详细说明。

对于SPM算法，大多数设计都是集中于轻量级，即对单个或少量模乘单元按下面环多项式计算公式：

不断复用单个乘法器单元依次计算最终多项式系数，此方法除了耗时过多的缺点，在硬件电路实现时还会存在数据处理速度慢即低吞吐率，以及复杂的控制单元。SPM的电路结构想要获得更高的吞吐率，需要多个模乘单元并行计算。为了更清晰的理解整数环多项式Schoolbook算法的计算过程，图1对整个算法的计算进行详细的展开。根据图1的运算规律，可以更加明了地布局环多项式乘法的时序策略，以一个矩阵-向量乘法的运算来直观的表示，如图2所示。将多项式b(x)的系数以一个n×n的循环矩阵(前一列循环移位并添加负号得到后一列)表示，而多项式a(x)的系数就直接表示为n×1的向量。矩阵的第一列代表多项式b(x)的最原始的系数，在第一个时钟周期分别同时与多项式a(x)的第一个系数a

结合具体格密码参数，本发明采用模数为q＝7681，n＝256的参数，同时考虑到在RLWE和MLWE中的格密码两个多项式系数，一个是在q上的均匀分布的公钥项，数据位宽为13位，另一个是在q上高斯分布或二项分布的数据，采样出来的数据在不同参数下位宽不同，本发明采用分布范围在[0,32)和[7649,7681)，为了充分利用FPGA中的DSP资源，将错误项数据用有符号数表示，位宽为6位，数据位宽5位，符号位占据1位，正数符号位为0，负数符号位为1。在这样的重新安排错误项数据之后，在Xilinx FPGA中，DSP48E1支持最大位宽为25×18比特的乘法，那么通过在其中一个输入的乘法数中采用数据位拼接的方法，在5比特的两个数据中间填充13位0，即为{b,13′b0,c}。这样，与13比特的a相乘生成36比特的结果，得到的高18位为a×b的结果，低18位为a×c的结果，这样仅用一块DSP48E1就可以在同一时钟得到两个乘法结果，再考虑符号位。在数字电路中通过将错误项数据最高位的符号位与环多项式乘法的符号位控制位相异或可得到最终的符号位，再利用负数模约减时a*(-b)modq＝q-(a*bmodq)性质，得到最终的结果。

实现高并行度的计算，需要消耗大量的模乘单元，硬件资源消耗也会大幅增加。因此，模乘单元的资源消耗将决定整个多项式乘法结构的资源。由于采用的是有符号的采样，13×13比特的模乘被转换13×5比特的模乘，然后基于DSP48E1的高利用率的方法，使得硬件资源消耗减少。对于模约减部分，由于所执行的模约减只有18比特和模数q值的特殊性，一个18比特的无符号数x，可以被拆开为：

x[17:0]＝x[17:13]×2

此时将拆分后的数据模约减q值，可以得到：xmod7681＝x[17:13]×511+x[12:0]＝x[17:13]＜＜9-x[17:13]+x[12:0]对数据这样整理之后，整个模约减电路结构只需要一个移位模块、一个14比特的减法器、一个13比特的加法器和一次模减，较其他模约减技术减少了消耗的资源。整个有符号双模乘的电路结构如图3所示，采用流水线设计，输入为13比特的a

在本发明中，如图3所示的有符号双模乘结构是整体结构的核心部分，在第一个时钟周期，利用一个DSP IP核输入的乘法数中采用数据位拼接的方法，取6比特的有符号数b

如图4所示，为本发明的环多项式乘法的整体结构。在数据载入阶段，多项式b(x)的系数b

实施例仅为说明本发明的技术思想，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在技术方案基础上所做的任何改动，均落入本发明保护范围之内。