摘 要

基于Ring-LWE公钥加密技术具有抗量子攻击、效率高、密钥长度小等优点而成为后量子加密时代的热点。Ring-LWE加密方案由密钥生成、加密和解密三部分组成，这三个部分的实现都离不开多项式乘法，多项式乘法的计算需要花费的大量时间与资源。本文面向Ring-LWE中的多项式乘法运算，通过研究负包裹卷积的快速数论变换（FNTT），设计一个硬件电路模块，使其能高速完成Ring-LWE里面的多项式运算。本设计先进行FNTT运算的C语言仿真，并在Xilinx Spartan-6系列的FPGA上实现。

通过使用ISE自带的Isim仿真工具进行仿真与调试，该快速数论变换单元能在300us内完成13-bit、长度为256的多项式的FNTT运算与逆运算，能够满足Ring-LWE加密算法中快速多项式乘法的要求。

关键词：Ring-LWE、FPGA、FNTT、负包裹卷积

目 录

第1章 绪论 1

1.1 课题背景与研究意义 1

1.2 国内外研究现状 1

1.2.1 基于格的加密方案研究 1

1.2.2 Ring-LWE加密方案的研究 2

1.3 课题核心问题及目标 3

第2章 FNTT算法理论基础及方案设计 4

2.1 Ring-LWE加密方案 4

2.2 多项式乘法与离散傅里叶变换 5

2.2.1 多项式的表示 5

2.2.2 多项式的运算 5

2.2.3 多项式乘法与离散傅里叶变换 6

2.3 快速傅里叶变换与蝶形运算 7

2.4 NTT原理 9

2.4.1 同余式与欧拉函数 9

2.4.2 整数的次数与原根 9

2.4.3 快速数论变换 10

2.5 Ring-LWE中多项式乘法与负包裹卷积FNTT算法 11

第3章 Ring-LWE中FNTT算法的仿真 14

3.1 FNTT总体程序设计与运算参数选择 14

3.2 负包裹卷积FNTT算法子函数设计 15

3.2.1 指数模乘函数实现 15

3.2.2 码位置换函数实现 16

3.2.3 初始化与单位根计算函数实现 17

3.2.4 FNTT与IFNTT函数实现 18

3.3 C语言验证与结果分析 19

第4章 FNTT运算单元的FPGA硬件电路设计 23

4.1 总体结构设计 23

4.2 FNTT功能划分 24

4.3 状态机模块设计 26

4.4 地址生成模块设计 28

4.5 数据处理模块设计 29

第5章 FNTT运算单元仿真验证与结果分析 31

5.1 数据读写与码位置换仿真验证 31

5.2 地址生成模块仿真验证 32

5.3 数据运算通路及FNTT仿真验证 33

5.4 运算单元资源与时间消耗 34

第6章 总结与展望 36

参考文献 38

致 谢 40

绪论

1.1 课题背景与研究意义

传统加密算法对明文进行加密，简单的说就是利用某种难以求逆的函数对数据进行处理得到密文的过程，而解密则是通过所给的函数特征信息，对密文进行处理得到明文的过程。加密算法的安全性，与社会中的各行各业息息相关，每当一种新加密算法的提出与广泛使用的加密算法被破解，都会引起世界上各国各业的关注，甚至引起大的变化。从古希腊时的古典密码的使用到二战时德国科学家Arthur Scherbius发明了英格玛编码机，再到近年层出不穷的信息泄露事件。信息安全的需求已经越来越普世化，人民对于信息安全问题越来越敏感，有关信息安全的事件会牵动着世界上各行各业的关注。

当今广泛使用的是传统加密算法，例如RSA与ECC是建立在因子分解与椭圆曲线离散对数问题的基础上。Shor在1994年与2003年提出的算法，将RSA与ECC指数级的破解运算变成多项式级别，使得理论上量子计算机能够破解RSA与ECC加密^[1]。即便没有量子计算机，密码分析技术的提升也极大影响了传统加密算法的安全性^[2]。因此随着近几年量子计算机日趋成熟与密码分析技术的不断发展，现广泛使用的加密算法的安全性已经不能满足国家与社会，乃至个人的信息安全需求。目前社会需要一种普通计算机能够应用的后量子(抗量子)密码，来抵抗量子计算机的暴力攻击破解^[3]。而且在可预见的未来，随着大规模物联网不断发展与实现，低成本、低功耗、高安全性的加密算法与其硬件实现将是未来智能社会的重要基石之一。

目前后量子公钥密码可分为基于编码的公钥密码体制、基于多变量的密码体制、基于Hash算法构造的密码体制和基于格的密码体制四个类型^[4]。在这四个类型中，基于格的密码系统因为有良好的安全性证明并且没有已知的量子破解算法而成为替代传统密码系统的热门方案。

1.2 国内外研究现状

1.2.1 基于格的加密方案研究

1611年，开普勒提出了猜想，即如果在一个容器里堆叠放置相同半径的小球，那么小球所能达到的最大密度为。而在1840年左右，高斯证明了开普勒的猜想，并引进了格的概念。又通过了至今许多数学家的研究，格理论发展至今，而其中最重要的两个问题便是SCP（最短向量问题）与CVP（最近向量问题）^[5]。

1996年Ajtai提出了基于格的单向陷门函数的思想与基于worst-case下格问题设计加密方案的可能性。1997年出现的Ajtai-Dwork方案是第一个基于格的公钥加密方案，但存在着效率低的问题，不适合实际使用。1998年，Hoffstein提出了NTRU加密方案，即一种基于特定环的公钥加密方案，其安全性依赖于SVP问题。2005年，LWE(Learning With Errors)问题被Regev首次提出，但是一次只能够加密1bit^[6]。2008年，NTRU被选入IEEE 标准^[7]。2009年，Regev和Micciancio在原有的基础上提出了LWE的改进方案，即多比特的LWE公钥加密方案。2010年Lyubashevsky 等人在欧洲密码学会上提出了Ring-LWE（learning with errors over ring）。2011年，Perikert等人提出了基于身份的LWE加密方案。Brakerski 和 Vaikuntanathan第一个提出了基于LWE与Ring-LWE 的全同态加密方案，利用维度模数规约技术降低了密文的维度从而降低了计算的复杂性。

这几种公钥加密方案都是基于格难题，即格难题的破解难度决定了这两种问题的安全性与可靠程度。而且因为格是一种线性结构，因此基于格的加密方案主要涉及线性运算，相较于其他数学难题更易于在硬件中实现，具有广阔的发展前景。在加密方案的设计中，有一个重要的问题，即加密方案的安全性与参数紧密相关。如果参数过少或者过小，那么加密算法的安全性就得不到足够的保证；如果参数过多或者过大、那么会导致加密方案的效率过低、密钥过长。

在加密强度相同的情况下，NTRU与RSA相比，加密、解密过程十分简单、因此加密、解密速度更快、随着参数的增大，对于加密效率没有显著影响。因此在参数较大的情况下，NTRU较RSA的速度优势更为明显。但是NTRU也有缺点，那就是不支持理论安全性证明，正确率不高等。因此相比而言，支持理论安全性证明的LWE加密方案更有优势。

1.2.2 Ring-LWE加密方案的研究

目前LWE加密方案有以下几个研究方向：

1. 高效加密研究：虽然LWE加密方案具有安全性证明，且效率在诸多基于格的加密方案中最高。但是LWE加密方案同样具有基于格的加密方案所普遍具有的缺点，即安全参数大、密文拓展率高而导致的实用性较差。因此在保证安全性的情况下使得加密方案的效率提高是一个重要的方向，Ring-LWE就是其中的一个代表^[8]。
2. 同态加密方案研究：同态加密使得对多个密文计算后解密与解密后计算时等价的。因此使用同态加密方案能够减少通信代价并且转移计算任务，在计算、通信、安全三个方面都有很大的优势。因此同态LWE和Ring-LWE加密方案的研究有着重要的实际意义^[9]。
3. 抗密码分析的研究：现代密码分析技术的发展，包括旁道攻击、量子攻击在内的一系列技术使得加密方案不仅需要有安全性证明，在实现时也要采取相应手段进行抗密码分析。旁道攻击不攻击加密本身，而是通过加密系统的信息泄露例如功耗、电磁辐射、运算时间等进行攻击。因此如何从硬件实现上减小密码分析的可能性还需要许多研究。

虽然LWE加密方案支持理论安全性证明，但也有着许多问题，其中最重要的就是密钥长度太大，而且随着安全参数的增大，消耗的资源会呈指数增加，不利于实际的应用。Ring-LWE是LWE方案在环域上的变体，相比LWE有着密钥长度更短、加密过程更为简洁、误码率更低、硬件实现更为简单等优点，因此成为了后量子加密方案中的一大热点^[10][9]。

国内外对Ring-LWE的研究主要围绕在硬件的安全高效实现以及同态加密的实现上。2012年，Thomas Poppelmann和Tim Guneysu所发表的论文中提出了一种Ring-LWE可重构微处理器架构^[11]。2014年，这两位学者又提出了一种轻量级的Ring-LWE硬件加密单元，在Xilinx Spartan-6 FPGA平台上使用了32个slices，1块BRAM和1个DSP模块，能够以较快速度实现Ring-LWE的加密与解密过程，而且占用的资源适度。2015年，Donald Donglong Chen等人发表的论文中提出了一种基于Ring-LWE和SHE的高速多项式乘法结构，在占用了较多资源的情况下，实现了高性能的多项式乘法。2019年，一种低资源消耗以及抗旁道攻击的Ring-LWE加密方案的硬件实现被提出。

近年来，许多优秀的Ring-LWE加密方案的硬件实现在FPGA平台上出现。这些设计方案中，有一部分是追求高吞吐量，即高性能方向；而其他的设计方案则是追求低面积以及低功耗^[2]。Ring-LWE加密技术的软件实现非常灵活，适用于生物特征数据安全等多用途物联网应用。然而，目前还没有实用的Ring-LWE加密方案能够适用于许多资源受限的硬件设备。

他们的研究证明了在硬件上实现低成本Ring-LWE公钥加密方案是可行的。在2019年初，麻省理工大学的Utsav Banerje等人实现了40nm的Ring-LWE加密处理器，在低压供电的情况下实现了低功耗，可重构，占用资源小与较快的处理速度等性能指标。体现了近年来Ring-LWE加密技术实现的大步发展，不断进行优化，向着低成本、低功耗、高性能的指标进行研究。Ring-LWE加密方案的硬件实现逐渐满足实际的使用需求，能够被用于各种嵌入式物联网设备及高速通信设备中，符合未来的大规模物联网及各行业的低成本、高安全性的通信需求。

1.3 课题核心问题及目标

Ring-LWE公钥加密方案具有易于硬件实现以及抗量子攻击的特点，因此设计出运算速度快、占用面积小、资源低、能够实际运用的硬件加密电路是一直以来的重点。

在Ring-LWE公钥加密方案的硬件实现中，主要有两个方向，一是设计出快速高效的运算单元实现加密过程中的多次多项式乘法；二是设计出高效的高斯采样器。本课题的核心问题便是设计出快速高效的运算单元实现多项式乘法。

多项式乘法实际上便是卷积运算，而对于计算卷积，常见的就是快速傅里叶变换(FFT)。在多项式阶数较高时，通过FFT计算卷积比直接计算能够很大程度的减少计算时间、计算量以及资源消耗。但是FFT中存在着浮点数与复数的运算，会增加资源的消耗，且存在着精度的问题。因此本设计通过使用FNTT（fast number theory transformation）,即快速数论变换，在整数的范围内实现多项式乘法，进一步减少资源的消耗，不存在精度的问题，适用于硬件电路的实现以及面积小、性能高的要求。

本课题的目标在于设计出一个应用于Ring-LWE加密方案中的NTT运算单元，能够实现多项式的乘法运算、满足加密解密过程中的各种要求。而且本运算单元应具有硬件资源消耗少、计算速度快的特点。

FNTT算法理论基础及方案设计

2.1 Ring-LWE加密方案

2010年，Ring-LWE加密方案首先由Lyubashevsky在论文中提出。之后Lindne和 Peikert在此基础上提出了有效的Ring-LWE加密参数集。Lyubashevsky 与 Peikert等人证明了Ring-LWE加密方案的困难性可以约束到GaspSVP和SIVP问题上。因此如果理想格上的SVP问题不能在多项式量子时间内求解，那么任何的量子时间算法都不能破解Ring-LWE加密方案。Ring-LWE加密方案的抗量子攻击的能力也就得到了保证。

Ring-LWE加密方案是在多项式环上的进行的，其中n为2的指数次方，q对2n求模的余数为1。在此条件下，需要知道参数长度N与模q。N决定了数据的长度，而q决定了数据的位数。表2-1列举了几个适用于Ring-LWE加密方案的硬件参数^[12]。

表2-1 Ring-LWE加密方案硬件参数表

在Ring-LWE加密方案中，包括每次运算结果在内的所有数据约束在模q中。开始加密之前，首先将输入的二进制信息m编码为模q内的数据，编码规则为:将1编码成(q-1)/2、而0保持不变。解密完成后，恢复原始信息的规则m为：如果(q−1)/4≤m≤3(q−1)/4则返回1;否则,就返回0。通过如此的编码与解码规则，我们完成了二进制编码与模q内编码的对应。

Ring-LWE加密方案主要可分为三个部分,即密钥生成部分、加密部分与解密部分。

密钥生成部分：生成服从离散高斯分布，数组长度为N，且约束在模q内。令。则公钥为p，私钥为。为噪声生成密钥,在后面的过程中不会再被用到。而 为常数,数组长度为N、数据大小约束在模q中，且在整个加密、解密过程中保持不变。

加密部分：输入的信息为 ，二进制为数字信号，通过加密规则转换成模q内编码，即 。生成错误向量服从离散高斯分布 。密文的计算方法为 。

解密部分：解密的结果。再通过解码规则实现模q内编码到二进制编码的转换，即。

可以知道，在密钥生成、加密及解密三部分中，所涉及的乘法都是多项式乘法，而许多参数都是通过离散高斯抽样生成。因此离散高斯采样的速度与多项式乘法的速度决定了整个Ring-LWE加密与解密的速度。

2.2 多项式乘法与离散傅里叶变换

2.2.1 多项式的表示

由若干个单项式相加组成的代数式，形式同（1）的叫做多项式（减法可视作加上该数的相反数）。

（2-1）

其中的每个单项式叫做多项式的项，单项式的最高项次数，即多项式的次数。不含字母的项叫做常数项。称为多项式的系数。

多项式有点值表示法与系数表示法两种：

1. 点值表示法：

对于n次多项式，只需要确定n 1个点，那么多项式就是确定并且唯一的。因此记这n 1个点组成的集合为。该集合便为多项式的点值表示。

1. 系数表示法：

对于n次多项式，记向量为多项式的系数表示。

由系数表示获得点值表示的运算称为求值，而由点值表示求出系数表示的运算称为插值。

2.2.2 多项式的运算

首先，需要知道多项式的四则运算时建立在同类项的基础上的：如果两个单项式，它们所含的字母与其指数相同，那么两个单项式就称为同类项。给定两个多项式作为示例：

（2-2）

（2-3）

多项式的加法与减法便是进行合并同类项操作，所得项的系数是合并前各同类项的系数之和，字母与其指数不变。

（2-4）

（2-5）

多项式的乘法则是将一个多项式中的每个单项式与另一个多项式中的每个单项式进行相乘之后再合并同类项。设两个多项式进行线性卷积（乘法）得到多项式。

（2-6）

可以知道多项式的乘法如果用点值表示法进行表示的话，那么

（2-7）

因此知道多项式的点值表示的话，很容易就能实现多项式乘法。然而实际上的多项式都是通过系数表示，选取n个相异的点算出点值表示后再进行多项式的乘法操作。如果n个点的选取够特殊的时候，可以将的时间复杂度变为。

多项式的除法一般以竖式进行运算，有以下步骤：

1. 将两个多项式都按字母做降幂排列，并将所缺的项使用零进行补齐。
2. 用被除多项式的第一项除以除多项式的第一项从而得到商式的第一项。再用商式的第一项乘以除多项式，将积写入下放，进行合并同类项操作。
3. 再把差式当做新的被除多项式进行运算，指导余式为零或者余式的次数低于除多项式的次数为止。

2.2.3 多项式乘法与离散傅里叶变换

由式（2-6）可知，进行多项式乘法的时间复杂度为。随着多项式长度的增加，直接进行多项式乘法的计算量会变得十分巨大，计算效率会不断降低。因而需要使用信号处理的技术，即离散傅里叶变换来进行多项式乘法运算。

傅里叶变换能够将难以运算的时域信号转变成易于分析与运算的频域信号。但是在数字电路与计算机中，连续时间、连续频率的傅里叶变换是没办法进行的，因此需要将信号进行离散化，使用离散傅里叶变换(DFT)进行处理。DFT为：

（2-8）

（2-9）

反变换(IDFT)为：

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：