SNPAKA: 基于SNTRUP 的双向认证密钥协商协议FPGA 实现*

杨亚涛， 王在舟， 曾 萍， 肖 嵩

1. 北京电子科技学院 电子与通信工程系， 北京 100070

2. 西安电子科技大学 通信工程学院， 西安 710071

1 引言

随着近年来全球对量子计算技术的研究深入， 人们对替代现有密码系统(例如AES、RSA) 的实用化抗量子密码算法的需求日渐增加. NIST (National Institute of Standards and Technology， 美国国家标准与技术研究院) 于2017 年11 月征集抗量子密码算法后， 共有69 个算法进入了第一轮评估. 2020 年7月， NIST 公布了第三轮的7 个候选算法. 其中密钥封装机制(key encapsulation mechanism， KEM) 有4个， 分别是Classic McEliece、CRYSTALS-KYBER、NTRU 和SABER. 数字签名算法有3 个， 分别是CRYSTALS-DILITHIUM、Falcon 和Rainbow. 另外还有8 种算法进入备选， 其中的KEM 算法分别为BIKE、FrodoKEM、HQC、NTRU Prime 和SIKE. 数字签名算法为GeMSS、Picnic 和SPHINCS+.

在NTRU Prime 项目中， SNTRUP(streamlined NTRU Prime)是一个基于格的小型密钥封装算法，旨在实现IND-CCA2 安全的标准目标. SNTRUP 基于系统化设计， 可最大程度减少全面安全评估的复杂性. 事实证明， SNTRUP 可以低成本消除格上安全性测评的许多复杂问题， 同时满足作为基于小格基密钥封装算法的严格要求. SNTRUP 具有结构简洁、密钥密文尺寸小的优点， 是比较利于实用化的方案. 在国际上， NTRU (number theory research unit) 密码体制已成为IEEE P1363.1 标准[1]， 算法的安全性得到多方认同[2].

2 相关工作

由于格密码计算速度快， 通信开销较小， 且能被用于构造各类密码算法和应用， 因此被认为是最有希望的抗量子密码技术. 其代表算法有NTRU 系列、谷歌的NewHope、同态加密算法BGV、GSW、BFV等. 文献[3]首次提出了NTRU 公钥加密(public key encryption，PKE)方案，该方案被称为经典NTRU.随后研究者基于NTRU 提出了大量的数字签名方案. 文献[4] 中基于NTRU 提出的签名方案是GGH 签名方案[5]相对高效的实例化. 文献[6] 分析指出GGH 签名方案及NTRU 签名方案不够安全， 并指出这类签名方案的私钥是较短的格基， 当签名次数过多时， 签名会暴露出格基形成的基本形态， 从而泄露私钥.此后， 为避免泄露私钥信息， 一些学者构造了基于格的新型签名方案. 其中一个方法是2008 年Gentry 等人[7]提出的GPV 签名方案， 该方案常被称为hash and sign 设计， 需要借助单向陷门函数进行原像采样. 另一个方法是2009 年Lyubashevsky[8，9]提出的基于Fiat-Shamir 变换的方法， 该方法不使用陷门函数， 利用拒绝采样技术来避免签名泄露格基形态. 2014 年， Hoffstein 等人[10]基于NTRU 也提出了hash and sign 类型的签名方案.

近年来NTRU 的使用得到了进一步发展. 文献[11] 给出了五种基于NTRU 体制的全同态加密方案的分析比较， 指出了基于NTRU 加密方案需要优化的部分问题. 文献[12] 提出了一种基于NTRU 的选择明文攻击不可区分性IND-CPA 安全的全同态加密方案. 文献[13] 提出了一种新的全同态掩码防御方案， 解决了NTRU 算法在实现过程中的侧信道攻击安全隐患. 文献[14] 提出了一种T-NTRU 物联网动态安全接入认证算法， 使用动态变化时间序列通过哈希函数来产生动态密钥， 解决了固定哈希函数产生固定密钥的内部攻击安全问题. 文献[15] 结合可逆信息隐藏技术， 提出一种基于NTRU 的密文域可逆信息隐藏算法， 并将该算法应用于图像加密领域. 文献[16] 使用NTRU 格上高效的参数生成算法， 构建了一个基于NTRU 格的群签名方案， 缩短了系统公钥长度. 总之， 上述研究成果都集中在公钥加密体制和数字签名设计上， 未对基于NTRU 的密钥封装机制进行研究， 也没有进行密钥协商协议的设计与硬件实现.

本文的工作以NTRU Prime 项目为基础. 该项目中众多研究小组做出了卓有成效的工作. Biasse等人[17]引入了一种快速量子攻击算法， 破解了分圆多项式下的短生成器问题. Bauch 等人[18]提出了一种更快的基于多元二次函数的子域对数攻击方案. Bernstein 等人[19]给出了NTRU Prime 的原始版本. Hao 等人[20]完成了AVR ATmega1284 微控制器上sntrup653 的实现， 他们使用了8160 665 个周期进行封装， 15 602 748 个周期进行解封装. Marotzke[21]在Xilinx Zynq Ultrascale+ FPGA 上实现了sntrup761 的硬件加解密， 其时钟频率为271 MHz， 分别在4808 μs、524 μs 和958 μs 内完成密钥生成、封装和解封装. 在公钥密码算法的FPGA 实现方面， Huang 等人[22]实现了改进的RSA 加密算法， 在4 ns 时钟下加密速度接近40 kb/s. Kamal 等人[23]完成了NTRUEncrypt 的FPGA 实现， 在4 ns 时钟下加密速度为20.4 kb/s.

本文的主要贡献如下:

(1) 提出了一种SNTRUP 算法下的双向认证密钥协商协议(authentication key agreement protocol based on SNTRUP， SNPAKA). 利用SNTRUP 算法， 在只公布公钥的前提下， 通信双方利用Hash 函数和公钥加密系统进行数据封装和握手通信， 从而在不泄露任何私密信息的情况下完成双向身份认证和密钥交换.

(2) 对SNPAKA 协议进行了运行和测试. 利用Vivado 平台编写相关VHDL 代码， 经过测试和分析，在3 个参数下本程序均能快速实现密钥封装流程， 且能够得到正确的会话密钥. 其运算效率相比文献[22] 中设计的RSA1024 改进算法的FPGA 硬件实现提升了4.53 倍， 相比文献[23] 中设计的NTRU-Encrypt 算法提升了8.83 倍.

3 预备知识

3.1 格的定义

设b1，b2，···，bm为Rn的一组线性无关向量， 取集合L为b1，b2，···，bm的整线性组合， 即

这样的集合L称为格， 其中b1，b2，···，bm称为格L的一组基或简称格基.L的每一组基所含向量的个数相同， 基中所含向量个数称为格L的维数或秩， 记为dim(L)， 它与L所形成的线性子空间的维数相同.

3.2 格中困难问题

关于格有三个著名的NP (non-deterministic polynomial) 问题. 以下L代表一个格，d为格L的维数，‖·‖为2-范数.

3.3 多项式环与NTRU 格

这里f，g及f×g中所有单项式系数均为模q操作， 即将f，g及f×g视作Rq=Zq[X]/XN-1上的元素.R中的元素也可以用向量形式来表示:f(x) 可表示为(f0，f1，···，fN-1).

4 SNTRUP 原理

为了说明SNTRUP 的原理， 表1 给出一些参数定义.

表1 参数定义Table 1 Parameter definition

在说明SNTRUP 的原理前， 先简要分析NTRU 公钥密码体制的原理.

4.1 经典NTRU 公钥密码体制

4.1.1 参数说明

R上多项式元素的加运算与普通多项式加法一致， 用符号“+” 表示; 但乘法运算为卷积运算. 多项式元素模q运算就是把多项式的系数分别进行modq运算. 可以证明的是(R，+，×) 是一个环， 即多项式环.p和q在NTRU 中一般作为模数， 不一定为素数， 但要求(p，q)=1， 且q ≫p.

令R(d1，d2)={F ∈R}， 其中F中有d1个系数为1，d2个系数为-1， 余下系数为0. 则有多项式集合:Rf=R(df，df-1)，Rg=R(dg，dg)，Rφ=R(dφ，dφ)，Rm={m ∈R}， 其中m的系数在-(p-1)/2到(p-1)/2 之间.

4.1.2 密钥生成

随机生成两个多项式f ∈Rf，g′∈Rg(这里使用g′以区分SNTRUP 中的私钥)， 其中f必须在模p和模q下均有乘法逆元， 假设这两个逆元分别为Fp和Fq， 则有:Fq×f ≡1 (modq) 和Fp×f ≡1(modp). 然后计算:h ≡Fq×g′(modq)， 则h为公钥，f为私钥.

4.1.3 加密与解密算法

设明文消息为r ∈Rm， 随机选取多项式φ ∈Rφ， 利用公钥h， 计算:c ≡pφ×h+m(modq)， 则c为消息r对应的密文. 利用密文c和私钥f以及Fp计算:a ≡f×c(modq) 其中，a的系数在区间[-q/2，q/2] 上. 进一步计算:b ≡Fp×a(modp)， 即为解密后的明文. 其解密正确性可以证明如下:

展开并化简多项式a:

其中pφ×g模p显然为零， 从而有:a ≡f×r(modp). 又因b ≡Fp×a(modp)， 由乘法逆元的概念，a中的f也被消去， 从而得到明文消息r(modp).

4.2 SNTRUP 密钥封装算法

SNTRUP 有两个层次. 内层是SNTRUP Core， 这部分为非对称加密算法; 外层是SNTRUP， 这部分为密钥封装算法. 本节将分别介绍， 并分析二者的关系.

4.2.1 SNTRUP 符号说明与相关定义

素数p，q， 正整数w; 其中2p ≥3w，q ≥16w+1. 推荐参数集如下:

xp-x-1 为多项式环(Z/q)[x] 上的不可约多项式.

环Z[x]/(xp-x-1)，(Z/3)[x]/(xp-x-1) 和(Z/q)[x]/(xp-x-1) 分别简记为R，R/3，R/q.如果R中某元素的所有系数均在{-1，0，1}上取值， 则称该元素为小多项式(Small). 如果R中某元素有w个非零元素， 则称该元素的重量为w.R中所有重量为w的小多项式的集合称为短小集(Short).

扩展集(Rounded): 指系数仅在{-(q-1)/2，···，-6，-3，0，3，6，···，(q-1)/2}(其中q ∈1+3Z)或{-(q+1)/2，···，-6，-3，0，3，6，···，(q+1)/2}(其中q ∈2+3Z) 中取值的R的元素的集合.

扩展函数(Round)R/Rounded: 设ai ∈{-(q-1)/2，···，(q-1)/2}，ri是3Z(即3 的倍数集)中最接近ai的元素， 则Round(a0+···+ap-1xp-1)=r0+r1+···+rp-1xp-1. 对于小多项式e ∈R有Round(r)=r+e.

4.2.2 SNTRUP Core 的密钥生成

定义公钥集(PublicKeys):P=R/q; 私钥集(SecretKeys):S=Short×R/3. 算法1 将输出P×S中的元素.

算法1 KeyGen (密钥生成)1 生成一个均匀随机的小多项式g ∈R， 且判断g 在R/3 上能否被xp -x-1 整除， 能则可逆， 进入下一步， 否则不可逆， 重复该步骤直到可逆.2 计算g 在R/3 上的逆元g-1.3 生成一个均匀随机的多项式f ∈Short (f 非零且在R/q 上可逆， 其中w ≥1).4 在R/q 上计算h = g/(3f) (由于假设了q 是大于3 的素数， 所以3 在R/q 上是可逆的， 因而3f 在R/q 上也是可逆的).5 输出(h，(f，g-1))∈P ×S.

4.2.3 SNTRUP Core 的加密与解密算法

定义明文集(Inputs):I=Short; 密文集(Ciphertexts):C=Rounded.

加密算法Encrypt 将I×P映射到C上， 解密算法Decrypt 将C×S映射到I上， 分别见算法2 和算法3.

算法2 Encrypt (加密算法)1 输入r ∈I，h ∈P.2 在R/q 上计算hr ∈R/q.3 输出c = Round(hr).

算法3 Decrypt (解密算法)1 输入c ∈C，(f，v) ∈Short×R/3.2 在R/q 上计算3fc.3 将上一步所得多项式的系数模3， 得到多项式e ∈R/3.4 在R/3 上计算ev.5 将ev 变换为小多项式r′ ∈R.6 如果r′ 的重量为w， 则输出r′， 否则输出(1，··· ，1，0，··· ，0).

4.2.4 经典NTRU 算法SNTRUP Core 的比较

SNTRUP Core 在经典NTRU 算法上做出了一些改动， 如表2 所示. 相比较而言， SNTRUP Core 的参数更为具体， 更有利于使用者选取， 所用多项式环更加多样且复杂， 这增强了对于格攻击的抵抗能力. 加密过程将明文与公钥直接进行卷积， 相比经典算法大幅提高了安全性.

表2 NTRU 与SNTRUP Core 的比较Table 2 Comparison between NTRU and SNTRUP Core

4.2.5 SNTRUP 的参数空间

SNTRUP 除了SNTRUP Core 的参数外， 还增加了以下参数:

(1) 通过确定性编码(Encode) 算法得到的编码公/私钥集， 编码明/密文集:P →Pcode，S →Scode，I →Icode，C →Ccode， 且均为32 字节的字符串. 确定性解码(Decode) 算法为编码算法的逆运算.

(2) 会话密钥集(SessionKeys): Se 为32 字节的字符串.

(3) 认证集(Confirm): Cf 为32 字节的字符串.

(4) 哈希函数(Hashing): 定义Hash(z) 为SHA-512(z) 杂凑函数的前32 字节. 定义Hashb为Hash(z) 中z前再加一字节b ∈{0，1，···，255}， 也记作Hash(b，z).

(5) 确定性哈希认证(HashConfirm) 算法HC:Icode×Pcode→Cf.定义为: HC(r，K) = Hash2(Hash3(r)，Hash4(K))， 其中，rcode∈Icode，Kcode∈Pcode. 该算法能够保障发送方发送的密文确实是使用公钥对明文进行加密所得.

(6) 确定性哈希会话(HashSession) 算法HS:{0，1}×Icode×Ccode×Cf→Se.定义为: HS(b，y，z)=Hashb(Hash3(y)，z) 其中，b ∈{0，1}，y ∈Icode，z ∈Ccode× Cf. 该算法使得会话密钥中同时包含了明文和密文的信息， 从而协商双方都可以生成该密钥.

(7) 设M= (m0，m1，···，mn-1) 和R= (r0，r1，···，rn-1) 是整数序列， 且假设对每个i有0≤ri ≤mi ≤214， 则S= Encode(R，M) 是一个字节序列， 且S的长度只与M有关，Decode(Encode(R，M)，M)=R. 则编码(Encode) 算法见算法4.

算法4 Encode (编码算法)1 如果n = 0 则s 是一个空序列.2 如果n = 1 则S 是r0 的二进制低位在前形式， 且如果m0 ＞28 就截取前2 字节， 如果28 ≥m0 ＞1 就取前1 字节， 否则就取0 字节.3 如果n ≥2 则S 是Encode(R′，M′) 的前缀部分， 其中R′ 和M′ 的长度为「n/2■. 而当i 为偶数时， 对于每对ri mod mi， ri+1 mod mi+1， 可得: r = ri +mirr+1 mod m = mimi+1， 且0 ＜r′ ＜m′ ＜214， 按这种方法就能得到R′ 和M′ 的每一位. 该过程中当m ≥214 时将r mod 28 添加到前缀中， 同时r，m 被替换为■r/28■和■m/28■， 重复0-2 次可将m 减小到正确范围中. 如果n 是奇数则把mn-1，rn-1 也加入R′ 和M′ 中.4 重复进行第3 步直到n ＜2.

以下给出多种集合元素的编码方法.(1) 域元素的编码对于R/q中的元素， 系数处于{-(q-1)/2，···，-1，0，1，···，(q-1)/2}， 给每个系数加(q-1)/2使系数处在{0，1，···，q-1}中. 后使用编码算法， 其中M=(q，···，q).

(2) 扩展集元素的编码扩展集中的元素系数处于{-(q-1)/2，···，-6，-3，0，3，6，···，(q-1)/2}，给每个系数加(q-1)/2后除以3 ， 从而使系数处在{0，1，···，(q-1)/3}中， 然后使用编码算法， 其中M=((q-1)/3+1，···，(q-1)/3+1).

(3) 短小集元素的编码短小集元素系数处于{-1，0，1}中， 给每个系数加1 ， 从而使系数处于{0，1，2}中. 将每四个元素按低位在前合为一个数， 从而得到一个字节， 元素整体长度变为原先的「p/4

4.2.6 SNTRUP 的密钥生成

随机化算法KeyGen′将输出Pcode×Se′中的元素， 其中Se′=Scode×Pcode×Icode， 见算法5.

算法5 KeyGen′ (SNTRUP 密钥生成)1 通过SNTRUP Core 的KeyGen 算法得到(K，k)，K 和k 分别对应公钥和私钥.2 将K 编码为Kcode ∈Pcode.3 将k 编码为kcode ∈Scode.4 生成均匀随机的ρ ∈Icode.5 输出(Kcode，(kcode，Kcode，ρ)).

4.2.7 SNTRUP 的封装与解封装算法

随机化算法Encap 通过输入Pcode中的元素， 输出C′×Se 中的元素， 其中C′=Ccode×Cf， 见算法6.

算法6 Encap (封装算法)1 输入Kcode ∈Pcode， 对Kcode 进行解码得到K ∈P.2 输入明文r ∈I， 对r 进行编码得到rcode ∈Icode.3 计算e = Encrypt(r，K) ∈C， 对e 进行编码得到ecode ∈Ccode.4 E = (ecode，HC(rcode，Kcode)) ∈Ccode ×Cf.5 输出(E，HS(1，rcode，E)).

随机化算法Decap 通过输入C′×Se′中的元素， 输出Se 中的元素， 见算法7.

算法7 Decap (解封装算法)1 输入E = (ecode，γ) ∈Ccode ×Cf 和(kcode，Kcode，ρ) ∈Scode ×Pcode ×Icode.2 对ecode 进行解码得到e ∈C.3 对kcode 进行解码得到k ∈S.4 计算r′ = Decrypt(e，k) ∈I.5 按照Encap 的步骤计算r′code， 最后重新求出一个密文E′.6 如果E′ = E 则输出HS(1，rcode，E)， 否则输出HS(0，ρ，E).code、e′、e′

4.2.8 SNTRUP 两层次的关系

SNTRUP 两个层次之间关系密切， 如图1 所示. 可以看出， 任何信息在封装与解封装模块外均为编码状态， 而SNTRUP Core 加解密模块可以看作其子模块， 该子模块的输入和输出信息都是未经编码的. 编码后由于信息长度被固定为32 字节， 因此E共有64 字节， 前32 字节为编码后的密文e′code， 后32 字节为哈希认证值HC， 而其他的输入输出则均为32 字节， 这极大方便了通信双方对信息的接收与输出.

图1 SNTRUP 两层次关系图Figure 1 Relations between two hierarchies of SNTRUP

4.3 双向认证密钥协商协议SNPAKA 设计

设计的SNPAKA 协议说明如下:

第一阶段: 参数与密钥生成

(1) 密钥Kcode: 32 字节公钥字符串， 通过上文KeyGen′算法生成.kcode: 32 字节私钥字符串， 通过上文KeyGen′算法生成.

(2) 参数ρ: 32 字节反馈信息字符串， 包含了Alice 与Bob 事先约定好的Alice 的认证信息.rcode: 32 字节身份信息字符串， 包含了Alice 与Bob 事先约定好的Bob 的认证信息.

第二阶段: AKA 协议执行

SNPAKA 协议交互流程如图2 所示.

图2 双向认证密钥协商流程Figure 2 Two-directional authentication key agreement process

(1) Alice 作为密钥协商过程发起方， 首先生成密钥(Kcode，(kcode，Kcode，ρ))， 其中Kcode作为公钥由他人使用， (kcode，Kcode，ρ) 包含公/私钥对与反馈信息ρ， 由Alice 谨慎保管. 监听者在该步骤仅能获得公钥Kcode.

(2) Bob 接收公钥Kcode并利用上文Encap 算法求出(E，HS(1，rcode，E)). 其中rcode∈Icode为Bob 的身份信息， HS(1，rcode，E) 为会话密钥. 这里的E= (ecode，HC(rcode，Kcode)) 包含了密文和认证密钥两部分， 后者表明密文e是使用公钥对明文加密后求得. 使用哈希函数保证了无法由E反推得到rcode，Kcode. 之后， 将密文E传送给Alice. 监听者在该步骤仅能获得无法解密的密文E.

(3) Alice 利用上文Decap 算法求出rcode和E′， 并判断E′=E是否成立， 以此来判断Bob 是否是会话密钥的持有者. 如果是， 则通过E和rcode求出HS(1，rcode，E)， 并利用该哈希值将反馈信息ρ进行对称加密得到ρ′并输出. 监听者在该步骤仅能获得无法解密的ρ′.

(4) Bob 接收到Alice 发出的加密后的反馈信息ρ′， 并利用自己的会话密钥HS(1，rcode，E) 对其进行解密. 至此双方都知道了对方的身份以及拥有会话密钥的事实.

此后双方使用该会话密钥进行对称加密通信， 从而实现了双向的认证与密钥协商. 整个过程中监听者未能获得任何敏感信息， 从而保证了协议的安全性. 与一般密钥协商协议相比， 本协议核心为SNTRUP算法， 因而可以更快地进行大量加解密和密钥封装操作， 极大提高了密钥协商的效率.

5 FPGA 实现及性能测试

FPGA(现场可编程逻辑门阵列， field programmable gate array)，是一种可以根据需求对底层电路结构进行设计与更新的芯片， 通过使用FPGA 内部逻辑资源构建计算电路、例化大量计算引擎， 可以提高计算并行度，实现对指定算法的加速计算. SNPAKA 的FPGA 实现基于SNTRUP 密钥封装算法，在Xilinx Vivado 平台下编写代码测试程序， 进行行为级仿真， 对SNTRUP 密钥封装算法进行测试. 以参数857 为例， 通过输入公钥、随机数与密文， 将程序输出的密钥、密文和哈希值与预先计算的结果进行比较. 之后运行参数653 和参数761， 分析并比较其运算性能. 测试环境为: Windows 10 操作系统， Vivado 2020.1.1 工程平台. 依照上述算法， 本程序共设计了10 个模块， 如表3 所示. 在具体实现时， 使用了Karatsuba 快速乘法算法[24]进行大数相乘， 极大降低了算法复杂度.

表3 设计的FPGA 程序模块Table 3 Modules in FPGA implementation

5.1 测试结果与分析

私钥生成部分结果如图3 所示.

图3 私钥生成结果Figure 3 Private key generating result

图3 中， private_key_out_valid 为私钥输出指示信号; private_key_out 为私钥输出; private_key_out_tb 为读取测试文件中的私钥. 可见私钥生成与预先计算的结果一致.

公钥生成部分结果如图4 所示.

图4 公钥生成结果Figure 4 Public key generating result

图4 中， public_key_out_valid 为公钥输出指示信号; public_key_out 为公钥输出; private_key_out_tb 含义同图3. 可见公钥生成与预先计算的结果一致.

密文部分结果如图5 所示.

图5 密文结果Figure 5 Ciphertext result

图5 中， cipher_output_valid 为密文输出指示信号; cipher_output 为封装后的密文输出; output_tb 为读取测试文件中的密文. 可见密文与预先计算的结果一致.

解封装哈希输出如图6 所示.

图6 解封装结果Figure 6 Decapsulation result

5.2 算法性能分析

5.2.1 三种参数下的运算性能

(1) 参数857 下的运算测试

通过实际测试， SNTRUP 密钥封装算法在参数857 下运算速度如表4 所示.

表4 参数857 下的运算速度Table 4 Computing speed under parameter 857

(2) 参数761 下的运算测试

通过实际测试， SNTRUP 密钥封装算法在参数761 下运算速度如表5 所示.

表5 参数761 下的运算速度Table 5 Computing speed under parameter 761

(3) 参数653 下的运算测试

通过实际测试， SNTRUP 密钥封装算法在参数653 下运算速度如表6 所示.

表6 参数653 下的运算速度Table 6 Computing speed under parameter 653

通过图7， 可以看到三种参数下的运算性能， 随着参数逐渐增大， 运算速度呈现平缓下降趋势.

图7 三种参数下运算速度比较(kb/s)Figure 7 Comparison of computing speed among three parameters (kb/s)

5.2.2 资源占用情况分析

经过FPGA 实际仿真测试， 可以得到资源使用情况如表7 所示. 可以看出， 随着参数逐渐增大， 查找表(LUT) 使用数量呈递增趋势. 这是由于输入长度的增加导致了程序对各种RAM 的需求增多. FF 与LUTRAM 使用量仅有小幅波动. BRAM、DSP、IO、BUFG 均不随参数变化而变化. 虽然参数增大提升了SNTRUP 的安全性， 但代价是运算速度随之降低. 因而选择参数时既要考虑安全性也要考虑实际应用场合. 可以看到， 本测试程序所用资源远远小于FPGA 芯片中所含资源; 可见SNTRUP 密钥封装算法十分轻巧， 便于使用.

表7 硬件资源使用情况Table 7 Hardware resource usage

5.3 与其他公钥加密算法的对比

选择同样使用FPGA 实现的改进的RSA1024 公钥加密算法和基于NTRU 的NTRUEncrypt 公钥加密算法作为比较对象， 可得表8. 可以看出， 与改进的RSA1024 公钥加密算法相比， SNTRUP 算法运算速度是其4.53 倍. 而与同样基于NTRU 的NTRUEncrypt 公钥加密算法相比， SNTRUP 算法速度为其8.83 倍.

表8 三种算法运算速度对比Table 8 Comparison of computing speed among three algorithms

6 安全性分析

本节将从SNTRUP 本身和FPGA 实现两方面对安全性进行分析. 目前针对SNTRUP 算法的攻击方式主要为格攻击和中间相遇攻击.

6.1 格攻击

6.2 中间相遇攻击

NTRU 分析中通常取E= 2p. Wunderer 等人[36]归纳了Schanck 的建议， 将传统的中间相遇攻击替换为了量子搜索， 这将增加了L的循环次数， 又节约了大量存储空间. 另一方面，L次循环应该是连续的， 在限定时间T内要求完成(L/T)2次并行量子搜索， 这也大大增加了实际计算开销.到目前为止， 还没有出现能够有效解决格中困难问题的量子算法， SNTRUP 算法能够很好抵抗格攻击和中间相遇攻击， 它也是学者公认安全性较好的基于格问题的公钥加密方案.

6.3 对硬件的分析攻击

分析攻击是指密码分析者从FPGA 芯片本身通过能量分析或直接读取的方式来直接获取密钥信息.本实现方案采用每次开始加密或上电时随机生成密钥存入bram， 使用完成后直接擦除bram 的方式， 保证分析者无法直接读取密钥信息. 另外， 由于密钥生成的随机性， 对同一个明文即使反复加密， 对芯片探测所得能量谱也有巨大差异， 分析者很难通过对硬件进行分析而获取密钥信息.

7 总结

在NIST 开展的抗量子密码算法征集与标准化过程中， 格密码因其优异的性能而备受关注. NTRU和NTRU Prime 作为格密码的典型代表具有重要的研究意义. 本文给出了SNTRUP Core 加密/解密模块与SNTRUP 封装/解封装模块的层次关系， 利用SNTRUP 的密钥封装特性， 设计了双向认证密钥协商协议SNPAKA， 通过四步握手实现了快速认证密钥协商过程， 并进行了FPGA 实际测试. 经过测试和分析， 该方案密钥生成速度为198.22 kb/s， 封装速度为1983.27 kb/s， 解封装速度为919.84 kb/s， 相比经典NTRU 算法NTRUEncrypt 提升了8.83 倍， 相比RSA1024 公钥加密方案提升近了4.53 倍. 最后分析了SNTRUP 的安全性， 给出两种攻击下对SNTRUP 安全性的分析. 下一步我们将继续对SNPAKA 进行完善， 对其硬件快速实现做进一步优化.