服务粉丝

我们一直在努力
当前位置：首页 > 财经 >

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

日期： 来源：信息安全与通信保密杂志社收集编辑：Cismag





摘  要：格密码是后量子密码中的一项重要技术，为提高格密码运算效率，提出了一种格密码中多项式乘法的硬件实现方法。该方法利用现场可编程门阵列（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 次蝶形运算。
图 1　8 点 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期（为便于排版，已省去原文参考文献）


商务合作 | 开白转载 | 媒体交流 | 理事服务 

请联系：15710013727（微信同号）

《信息安全与通信保密》杂志投稿

联系电话：13391516229（微信同号）

邮箱：xxaqtgxt@163.com   

《通信技术》杂志投稿

联系电话：15198220331（微信同号）

邮箱：txjstgyx@163.com

文章推荐

相关阅读

  • 高手善用的“数学思维”｜长江读书392期

  • 不同领域的人，理解世界的视角也多有不同。而认知方式的碰撞，便可能激发新的思考。本周长江读书带来文津图书奖得主吴军博士的《富足》一书，在书中，他用数学深入浅出地总结了几点

  • Python 100天 16：print函数打印九九乘法表

  • 前面我们学习了Python的一个常用函数print的用法。Python 100天 15：print("hello world")茴香豆的写法学习了后我们怎么利用这个函数来体验一下实际的用途，这样才能直观的感受

  • Python输出乘法口诀表（小试牛刀）

  • 工欲善其事，必先利其器，所以我们需要安装一个属于自己的代码编辑器，我这里之后所用的全部都是Sublime Text编辑器，你可以看我之前发的内容选择与安装适合你的编辑器。
    一、在Sub

  • 马立平：小学数学教材中的严重问题

  • 撰文 | 马立平一个多月前，人教社小学数学教材的插画引起了热议。在此笔者拟指出小学数学教材中一个比插画更为严重的问题，即2001年以来，因为“取消被乘数

  • 最小二乘法（ordinary least squares）趋势面拟合

  • 最小二乘法理论最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的

  • 最小二乘法公式推导过程

  • 假设现在有n对坐标系中的点现在要做k阶多项式拟合，多项式函数如下将已知的观测点数据代入上述公式得到如下n组等式：......
    最小二乘法（又称最小平方法）是一种数学优化技术。它通

聚合标签

中国 自己的 美国 都是 疫情 的人 亿元 的是 三星 手机 华为 这款 车型 万元 企业 日本 小米 俄罗斯 民警 项目

热门文章

  • “复活”半年后　京东拍拍二手杀入公益事业

  • 京东拍拍二手“复活”半年后，杀入公益事业，试图让企业捐的赠品、家庭闲置品变成实实在在的“爱心”。 把“闲置品”变爱心 6月12日，“益心一益·守护梦想每一步”2018年四

最新文章

  • 6起典型窃密泄密案例

  • 保密事关国家安全和利益。中国特色社会主义进入新时代，安全保密形势日益严峻，反窃密防泄密斗争尖锐复杂。以案为鉴，常敲保密警钟，时刻绷紧保密弦，才能增强保密意识、规范保密管理

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

  • 摘  要：格密码是后量子密码中的一项重要技术，为提高格密码运算效率，提出了一种格密码中多项式乘法的硬件实现方法。该方法利用现场可编程门阵列（Field Program Gate Array，FPGA）

  • 工业互联网数据安全治理实践

  • 摘要：自2017年首次提出数据安全治理以来，国内外对数据安全治理已投入大量研究，同时随着国内工业互联网的兴起，伴随工业互联网积累的海量数据带来了前所未有的数据安全挑战，基于数

  • MQTT 协议安全加固研究

  • 摘　要：通过研究针对消息队列遥测传输（Message Queuing Telemetry Transport，MQTT）协议的安全加固方法，给出了一个 MQTT 协议的安全加固框架。首先，对 MQTT 协议面临的风险进行了

  • 高安全等级密码模块安全技术设计

  • 摘　要：随着金融、大数据等行业的普及和发展，对密码设备的依赖与日俱增，并且业内在数据安全领域提出了多方面更高的要求，例如密码模块的物理安全、抗非入侵式攻击、抗环境失效等