NTRU的原理及安全性现状分析.doc

NTRU的原理及安全性现状分析

【摘要】NTRU一种比较新的公开密钥体制，由于NTRU产生的密钥方法比较容易，加密、解密的速度比RSA等著名算法快得多，NTRU成为当前公钥体制研究的一个热点。本文介绍了NTRU的原理，总结了对该算法密码分析的结果，给相关的理论研究及工程应用提供一些参考。
【关键词】NTRU；加密；解密
1 引言
1.1 NTRU的研究背景和意义
NTRU(Number Theory Research Unit)算法是1996年由美国布朗大学三位数学教授发明的公开秘密体制 。这是一个基于多项式环（其中N是一个安全参数）的密码体制。它的安全性依赖于格中最短向量问题（SVP）。相对于离散对数或大数分解等公开秘密体制来说，它有许多优势。在安全性方面，NTRU算法具有抵抗量子计算攻击的能力，而RSA和ECC算法是无法抵抗量子计算的。当前，对于用什么公钥密码来替代正在大量使用的RSA和ECC，主要有以下互相竞争的技术解决方案：NTRU公钥密码体制、McEliece 公钥密码体制、MQ 公钥密码体制。
McEliece 公钥密码体制的安全性基于纠错码问题，安全性强，但计算效率低。MQ 公钥密码体制，即多变元二次多项式公钥密码体制（Multivariate Quadratic Polynomials in Public KeyCryptosystem），基于有限域上的多变元二次多项式方程组的难解性，在安全性方面的缺点比较明显。相比之下，NTRU公钥加密体制算法简洁、计算速度快、占用存贮空间小。
1.2 国内外研究现状
随着信息技术的迅猛发展和一些高技术武器设备、通信指挥系统等的需要，未来军事部门将大量地使用公钥密码技术。由于RSA 和ECC 不能抗量子计算攻击，而NTRU 能抗量子计算攻击，且速度快和安全性高，特别别适合用于诸如智能卡，保密蜂窝电话系统，保密传真、无线保密数据网，以及认证系统等业务，这也扩大了公钥密钥体制的应用范围。有理由相信NTRU 算法完全有可能在公钥密钥体制中占有主导地位。
自从该密码体制被提出来后，就引起国外一流的密码学家的关注，这包括Don Coppersmith Johan Hastad, Andres Odlyzko,and Adi Shamir 等。到目前为止，有很多讨论NTRU 算法安全性。但还没有哪一种分析方法能破译该密码体制。从现阶段研究来看，NTRU 所基于的困难问题是安全的。接下来的研究主要集中在体制的参数设置和适当的使用填充方案。
在2000 年，Jaulmes 和Joux 论证了仔细的选择填充方案可以防止选择密文攻击，Howgrave-Graham 等的研究结果显示了仔细的选择参数集可以使得解密失败概率降为几乎为0，一旦正确的参数的选择和适当填充方案的使用，任何对NTRU 的攻击都可以转发为对困难格问题的求解。
为了充分利用在学术界和商界的专家的经验和知识，提供一个完善的、有效的、能共同操作的，正确使用NTRU 公钥密码系统的方法，在2002 年10 月出版了一个标准EESS1v1：NTRU 加密和签名的实施，2003 年5 月对第一版进行完善和修改出台二版:EESS1v2。

1.3 本文安排
本文将在第2节中介绍NTRU的数学背景—格的知识，然后就是LLL算法、BKZ算法和NTRU算法的数学基础；在第3节中，介绍NTRU公钥加密体制，第4节介绍一些对NTRU算法的攻击方法，进而对算法的安全性进行分析；最后在第5节进行了小结。
2 数学背景
2.1 格问题（lattice problem）
2.1.1格的定义
这里的格是指点格。它是的一个离散子群。特别地，对于的任意加法子群都构成一个格，这样的格称为整格（integer lattice）。格的具体定义如下：
定义1设为中一组线性无关向量，取集合为的整线性组合，即
这样的集合称为格，其中称为格的一组基或简称格基。的每一组基所含向量的个数相同，基中所含向量个数称之为格的维数或秩，记为，它与所张成的线性子空间的维数相同。
当时，格中有无数组基。任意两组基之间都可以通过一个幺模矩阵（行列式为的整数矩阵）进行相互转化。因此格中所有的基都有相同的Gram行列式，其中表示两个向量的内积。格的体积定义为格基的Gram行列式的平方根。当，也就是为满维格时，它的体积等于以任何一组基为行向量的矩阵的行列式的绝对值。
中向量的欧氏范数和中心化欧氏范数定义为：
若，则的欧氏范数为，

而的中心化欧氏范数定义为，
其中

本节以下部分如无特别说明均指中心化欧氏范数。
由于格是离散的，所以格中必有最短非零向量，这个向量的欧式范数称为格的第一最小，记为或。更一般的，对于所有的，Minkowski的次最小定义为

其中最小值取自中个线性无关向量构成的向量组的集合。，，…， 称为的逐次最小。总存在一组线性无关向量达到所有的逐次最小，即对所有的，。但是当时，这样的一组向量不一定是一组格基；当时，甚至可能不存在这样一组格基。
利用高斯启发式算法(Gaussian heuristic)，随机维格的最短向量长度约为
。
2.1.2格中的困难问题
关于格有三个著名的NP问题。以下代表一个格，为格的维数，为一范数。
①最短向量问题(SVP)：给定格的一组基，寻找格中一非零向量，使得。近似最短向量问题(APPR-SVP)：给定格的一组基，寻找一非零向量，使得，其中是与维数有关的某个近似因子。
②最近向量问题(CVP)，也称为最近格点问题：给定格的一组基和向量，不一定在中，寻找一向量，使得都有。类似地，近似最近向量问题定义为：给定格的一组基和向量，不一定在中，寻找一向量，使得都有。
③最小基问题(SBP)：这个问题目前研究的人并不多，本文也未曾涉及，这里就不作介绍了。
2.1.3格约化(lattice reduction)
在格中总有线性无关向量组可以达到所有的逐次最小值，但一般来说，这样一组线性无关向量并不构成格的一组基；格中也没有一组基比其它基“明显好”。格约化的目的是利用已有的一组基找另一组“更好”的基，这组基满足：
 该基中的向量比原有的基中的向量更短，或者该基中有向量的范数。
‚该基中的向量两两正交或者相对正交（即该基中任意两个向量的内积与它们的长度之积的比率特别小，接近于零）。
一组约化的基可以帮助解决SVP和CVP。目前最有名的格基约化算法为A. K. Lenstra、H. W. Lenstra Jr和L. Lovász提出的LLL算法。
2.1.4多项式环及NTRU格
NTRU加密体制及NTRUSign数字签名体制都是基于商环上运算的算法。环中的乘法运算定义为卷积 “”(convolution multiplication)：设，
，，
定义
，
其中的的系数为
，。
称是模的是指及中的所有单项式系数均为模q的，即将及视作的元素。
中的元素也可以用向量形式来表示，即可表示为。因此类似可定义中元素的欧式范数和中心化欧氏范数。
中的元素还可以用循环矩阵来表示：即可表示为

类似地有。很显然地，映射为一同构映射，即，其中为普通的矩阵乘法。
对应于环中的任一元素，有的一自然格，即由的行向量生成的格。对于每个，，集合

是一个维数为2N的格。这种形式的格称为NTRU格。显然，它有一组基为。作为格，其体积为，因此中最短向量长度约为。
中元素的欧氏范数定义为分量形式的欧式范数，即
。
定义两个符号：对于任意,令「」表示最接近的整数，记「」。若多项式是有理系数的，用「」和分别表示对其系数进行「」、运算所得的多项式。
2.2 LLL算法
2.2.1LLL规约基的定义及有关定理
定义2令是格L上一组基，是由格朗姆——施密特正交化过程定义的。记，，且 。
我们称向量组为LLL规约（关于）的，如果他们满足一下两个条件：

‚
引理1是格L上的一组基，是格中的最短向量，则。
证明：设是非零向量，是使得最大的坐标。则

因为是整数，所以

即
定理1如果是一组关于的LLL—规约基，则至多比格中的最短非零向量长倍，。
证明：若则，

同理

由定义可知

对进行递推，可得

由引理可证得

证毕
2.2.2 LLL算法
LLL算法是一个将一个基转化为LLL约减基的迭代算法。因为LLL约减基的定义使用了施密特正交向量组，所以这个算法将施密特正交法作为一个子程序。第一种情况可以通过适当的整数线性组合来满足。第二种情况不满足，则比短，这时交换和，并由原路返回。具体算法如下：
输入：
输出：LLL规约基
1:计算施密特正交基和系数，
2:计算
3:
4:while do
5: for downto 1do
6: Let=「」and set
7: update ，
8： end for
9： if then
10:
11: else
12; Samp with
13; update and, ,and
14:
15: end if
16:end while
2.3 BKZ算法
LLL算法的一般化是由Schnorr提出来的，他的想法是约减维数为的基，，而不是维数为2的基。约减这些子格的基是受Korkin-Zolotarev的启发。
定义3是格L的一组基，是KZ规约基，如果
（1）
(2),其中是指中最小非零向量的长度。
定义4是格L的一组基, 是分组长度为k的分组KZ规约基，或k-BKZ规约基，如果
(1)
(2) 是KZ-规约的，
在这个定义下，格的一组维的基是LLL规约基当且仅当是2-BKZ规约基，是KZ规约基当且仅当是n-BKZ规约基。下面我们简单描述一个关于在k-BKZ规约基中最长向量的长度的定理。
定理2如果是k-BKZ规约基，至多是格中最短向量的倍，当。
计算k-BKZ规约基的算法与LLL算法相似，算法如下：
输入：格L的一组基，一个整数
输出：格L的一组k-BKZ规约基
1：约减的大小
2：if 存在使得不是KZ规约的then
3： KZ规约
4： goto 1
5：return
2.4 NTRU算法的数学基础
NTRU 是一种基于多项式环的加密系统，其加、解密过程基于环上多项式代数运算和对数及的模约化运算，解密的有效性依赖于某些元素的概率。它是由正整数以及4个次整系数多项式集合来建构的。一般为一大质数，为多项式截断环(Truncated rolynomial rings)，其元素可表示为向量的形式：
。
定义5 上多项式元素加运算为普通多项式之间的加运算，用符号+表示；上多项式元素乘法运算为普通多项式的乘法运算，但乘完的结果要模上多项式(XN-1)，即2个多项式的卷积运算，常称为卷积，用表示。多项式元素模q运算就是把多项式的系数作处理，用表示。可以证明是一个环。
和在NTRU 中一般作为模数，不一定为质数，但是为了安全，要求和必须互质，且远大于。和为正整数，分别决定了多项式集合的系数分布。令={：的个系数为1，个系数为-l，余下的系数为0}，则多项式集合：
，为明文空间。由于4个集合的元素系数一般都比较小，常称为小多项式。
3 NTRU公钥加密算法简介
3.1 参数说明
NTRU加密体制中，选取了三个整数参数（）和四个多项式集合，这些集合中的多项式次数小于，系数均为整数。不一定是素数，但必须满足，而且远远大于。
3.2 密钥的生成
随机生成2 个多项式，其中必须满足在模和模的情形下均有乘法逆元。如果参数选择合适，大多数的都有逆元，而且可以通过改进欧几里得算法很容易找到这些逆元。用分别表示这两个逆元，
即

然后，计算

多项式即为公钥，私钥为，实际上也必须保密。
3.3 加密算法
假设要加密的消息，随机选取多项式，然后利用公钥进行如下运算：

多项式为消息对应的密文。
3.4 解密算法
收到密文后，可利用私钥进行解密。必须预先计算。解密首先计算

其中选取多项式的系数在区间内。然后通过如下计算恢复明文：
。
3.5 解密算法的工作原理
多项式满足：

对于最后一个多项式，如果参数选择合适，这个多项式的系数都可以限制在区间内，因此，这个多项式在所有系数模的情形下不会改变。这意味着将的所有系数都选取在区间内，的确可以得到正确的
。
将多项式进行模约化，可得到，然后用去乘上述多项式即可得到相应的明文消息。
4 NTRU 加密体制的安全性分析
4.1 格攻击
NTRU的格攻击是由Coppersmith和Shamir提出的，该攻击的本质是将NTRU的私钥和一个2N维的格相关联，利用LLL算法求出格中的最短向量来逼近私钥。May和Silverman利用相同的思想对标准的NTRU格做了改进，增强了攻击强度。下面我们将介绍五种类型的格，并讨论它们的区别。
4.1.1标准的NTRU格
1997年，Coppersmith 和Shamir提出了能够实施格攻击的一组基；对一个给定的常数，有一个由四个阶子阵构成的阶矩阵：

是公钥的第个系数，是一个使搜寻私钥尽可能有效的数。我们称由这个矩阵生成的格为。这样可以表示为

而，故格肯定包含向量。
下面讨论怎样选取使恢复出的概率更大。如果随机维格的决定因子为
，则其最短向量的期望长度在和 之间,在这里，，
所以可以认为最短向量略大于, 那么攻击者只要选择使最大化，那么
格找到最短向量的概率就大。可以证明当最大时。格攻击同样适用于对明文进行攻击。
4.1.2Zero-Run 格
May发现在多项式和有许多零系数，这是密码体制的一个潜在弱点。May的攻击是假定多项式有一个长为的零串，这有利于用规约算法找到小向量。他把的列到列乘以大数，得到新格

如果足够大，这将减少小向量的搜索范围。因为选择大于的，使得新格在LLL规约后，几乎所有格向量的第位到位为零。
4.1.3 Zero-Forced 格
Silverman论证了没有必要选择长度为的零串，当猜想私钥中有个零时。他将May的想法一般化，称之为 Zero-Forced 格。在这个攻击中，假设随机选取的个系数为零，并且通过减少格的维数来使这些系数为零。维数越小的格越有优势，因为它提高了规约算法的速度。
是在中随机选取的个系数组成的集合。我们构造一个使任意，的 Zero-Forced 格。注意格对所有向量都成立的个等式

（1）
假设，，我们就得到了个关于的关系式，且可以求解。假设已经求解出了对于的个等式。现在我们得到一组新的方程
（2）
我们将之放到新的格上，得到

基于这个矩阵的格为,维数为。目标向量或的循环在上当且仅当系数，。
为了能分析用这种格攻破NTRU体制所需的时间，对猜测出正确的零串做一个好的估计非常重要。对于任意，的概率为

对于任意，的循环等于零的概率近似为

这里概率之所以是近似值的原因是在g的不同循环中，r串零不成功的概率不是相互独立的。
4.1.4Dimension-Reduced 格
提高基规约算法速度的一个想法就是通过简单地从基中删去一些列来降低格的维数。我们可以在和上实施。从基的左半部分随机选列，右半部分随机选列，，其中在上，;在上，。这个基矩阵的维数是，但仅仅是线性无关的。我们仍然可能通过约减这个新基来逼近私钥，特别是私钥与其他短向量之间有间隔时。如果都小于1，一些系数肯定能被猜出来。
4.1.5不失真的 Zero-Forced 格
当构造zero-forced 格时，因为丢弃了关于的个关系式，没有考虑到系数的有关信息，所以有部分信息丢失。我们可以使用扩展的集合构造一个不失真的Zero-Forced 格.

这个集合的构造方法与Zero-Forced 格的基的构造方法一样，等同于（2）中的。不同之处在适用于方程（1）体系的矢量运算同样适用于整个扩展的集合。用这种构造方法，我们没有丢弃任何关于系数的关系式，并接受了一个子矩阵的，矩阵中的向量是向量的线性组合，其中。同时为了确保这些关系式仍然是模的，我们加入了行。这个格的维数为，正确猜出中零串的概率仍然为
。
4.1.6实验结果
格攻击的本质在于构造一个格使这个格与NTRU的私钥相关联，然后再利用格规约算法求出格中的最短向量来逼近私钥。所以攻破所需的时间必定与构造的格和所选择的规约算法有关。下面是用BKZ算法进行试验的结果。
图1是用和不同，分别使用四种格对中等强度的NTRU密码体制进行攻击的结果。

图1：用对中等强度N=167的NTRU密码体制的攻击技术比较。实线表示的时间，虚线表示用 使维数降低的格 的时间，折线表示的时间，点折线表示用使维数降低的格的时间。
同时对于标准强度的NTRU密码体制，我们也做了相似的实验，其中分组长度为。实验结果如图2所示：

图2：用对标准强度N=263的NTRU密码体制的攻击技术比较。实线表示的时间，虚线表示用 使维数降低的格 的时间，折线表示的时间，点折线表示用使维数降低的格的时间。
从图1和图2可以看出，对几乎所有选择的对，攻击NTRU密码体制最有效的方法是使用有损耗的格。并且还可以看出降维的有损耗的zero-forced的格攻击效果不是很好，但降维的不失真的zero-forced的格攻击效果好于没有降维的攻击。从图2还可以看出当使用不失真的zero-forced格时，攻击时间比较陡，当时，它几乎成为最有效的攻击方法。
4.2不完备解密攻击
不完备解密攻击与格攻击的原理完全不同，这种攻击没有利用格攻击中的最短向量问题，而是利用NTRU存在的解密失败问题（可详见参考文献[4]）
从NTRU公钥加密模式的解密过程可以看出，解密成功的前提条件是多项式的系数在区间内，否则就会导致解密失败。因为正确的解密依赖于私钥，所以不能正确解密时，解密的过程中就有可能泄露有关私钥的信息。攻击者可能利用NTRU这种不完善的解密特性，对NTRU实施成功的攻击。攻击方法主要用可解密文攻击DCA来攻击NTRU。首先我们介绍两个定义：
定义6 可解密文预言机DC(Decipherable Ciphertext oracle)是指接收满足Epk(x)=y的x和y作为输入，而输出Dsk(y)是否等于x．也就是说，一个DC可以确定用公钥pk加密消息产生的有效密文是否能用私钥sk进行解密．
定义7 可解密文攻击DCA是指运用公钥信息和DC对密码体制进行的攻击．
我们可以把NTRU的公钥密码体制表示为 ，攻击主要有三步：
随机选择一个对子使得，且是不可解密文。如果找到了，实验结果见表1
N
p
q

试验次数
机密失败次数
107
3
64
R(15,14)
R（12,12）
R（5,5）
105
5
167
3
128
R(61,60)
R(20,20)
R(18,18)
105
6
263
3
128
R(50,49)
R(24,24)
R(16,16)
2*105
3
503
3
256
R(216,215)
R(72,72)
R(55,55 )
2*105
14
表1：NTRU的推荐参数
‚由于的系数在区间内，所以运用第一步找到的对子，找到使的系数全部落在区间上，并且任何非零系数设置为零后使得是可解密文的。由于系数的变化会引起的变化，且只能在中取值，所以可以通过下面的办法找到。将的非零系数设置为0，查询可解密文预言机，如果不能正确解密，则将其设置为0；如果解密正确，则选取的另一个非0系数，继续判断，重复这个过程直到得到的满足要求。
ƒ运用恢复密钥。由于是不可解密文，所以的系数至少一个在集合中取值，假设中只有一个系数满足这一个条件，设为第个系数，其它系数在区间，并有。设，分别指第阶的系数对应为-1,0,1.可按如下方式计算：

(1)当i=1时，由(i0 , )是不可解密文，可得；
(2)当i =-1时，由 (i0, )是不可解密文，可得 ；
(3)当i= 0时，如果 (i- , )是可解密文，那么 ；如果 (i+ )是可解密文，那么；否则．
由前面的说明和均是有效密钥，我们假设，确定密钥。在的讨论中假设，对于基本原理相同，区别仅为此时考虑的是产生-1的项的系数。
对于攻击者固定通过大量的来查找的攻击方式与第一种方法的类似，详细可参见文献[4]
4.3 选择密文攻击
在2000年的美密会上，Jaulmes和Joux首先提出了对NTRU的选择密文攻击，这种攻击使用了特殊模型下的无效密文，但还没有使用解密预言机。在2003年的美密会上，Howgrave-Graham等人发现充分利用NTRU的解密失败特点，将使得选择密文攻击更加有力。这类攻击仅仅使用了一种不牢固的解密预言机，它只有在给定的密文解密失败时才会报告。介于这两类攻击之间，Nicolas Gama 和 Phong Q. Nguyen提出了一种新的有效的选择密文攻击。这种攻击不仅询问给定的密文是否解密失败，而且询问NTRU解密算法关于这个密文的所有输出。下面我们分别介绍这三种攻击。
4.3.1Jaulmes和Joux对NTRU的选择密文攻击
选择一个形如的密文，c是一个整数，h是公钥，对其解密：

因为f和g的系数为1,0，-1，所以的系数只能是。为了使的系数在区间内，选取c使得且。如果假设a只有一个系数是，记为，则。
下一步解密输出 ，
若c为p的倍数，上式变为
，，所以可以恢复，求其逆得，因为f
的系数是-1,0,1，所以，再计算，就得到了与等价的密钥。
一般情况下，可能没有或有好几个系数为，此时上述攻击不成立，需要进行适当的改进。用是否能够得到取决于和的碰撞。当碰撞太多时，用可能不能得到，此时，可以测试或更一般的，因此要考虑需要考虑测试的可能碰撞数与密文数的一个折中，具体的数值见表1。
表2：NTRU各个参数中碰撞数为0,1,2,3的概率

碰撞数的平均值
14.5
9.03
61.7
碰撞数为1的概率

碰撞数为2的概率

碰撞数为3的概率

碰撞数为4的概率

0.011

碰撞数为5的概率

0.028

4.3.2Howgrave-Graham对NTRU的选择密文攻击
首先我们回顾一下多项式的逆转的有关概念。我们用表示多项式的逆转，如,则它的反转为：这是一个环同构。是和的乘积，且。换句话说，的连续项可以通过点乘它自己的连续逆转得到。这一点很重要，因为从中我们可以知道，而其他项的大小是。 因此我们知道有一项的大小为，而其他项的大小大约是。相比于任意两个与f的范数相同的多项式的乘积，多项式的宽度是最大的。因此我们假设无论宽度何时最大，与密切相关，与密切相关。
我们导出一个独立于填充方案的强大的选择密文攻击。事实上，假设一个攻击者能够搜集许多三元组，使得无法正确解密。如果解密失败的可能性十分高，攻击者可以通过一个疲软的选择密文攻击来获得这些三元组，可以通过仅仅选择随机的消息，对它们进行加密直到发生解密失败。有趣的是，这样的攻击仅使用了有效的密文。
对于这样的一个三元组，我们知道的宽度很大，并且不知道为何存在一个整数使得与相近，与相近。不幸的是，我们不知道的值，否则我们可以通过使用逆转来消除未知的：如果与相近，与相近，则一定分别相近于。一旦由均值法导出，使用Gentry 和 Szydlo的算法，可能在多项式时间内恢复。严格的说，为了使用此算法，需要确定由和导出的的理想跨度。
为了检验这种攻击的有效性，我们需要找出大量的解密失败，这取决于依赖的参数，且相当耗时。事实上，用一个相对疲软的攻击进行试验，发现攻击是有效的。这个攻击基于下面的预言机：当一个有效的密文e在预言机上询问时，预言机显示的宽度是否大于B。因此预言机只是检测了间隔失败。通过使用比q小得多的B的值和下面的算法，我们能够在合理的时间内检验我们的攻击。算法如下：
1、 设置
2、 生成大量的有效密文。对于每一个密文e：
访问
‚如果显示a的宽度比B大，设置，
3、 用使用的有效密文的数量除以和。
在达到足够长的记录后，和应该收敛于和。对于二元的和,通过研究这个来看准确地恢复需要多少宽度大于B的消息。结果显示在表2。实验发现的最近似值为
。
表3：用对B的不同变量值恢复所需的消息
B
消息
范数（猜想的）
36
500000
15.5
36
1400000
7.38

B
消息
18
10000

二元的

当与猜想的的距离约为时，可以最终四舍五入恢复。由上可得出从一个真正的解密预言机恢复和，需要的解密失败不多于一百万或者更少。所以这种攻击使得仍然适用于填充的NTRU。
4.3.3Nicolas Gama 和 Phong Q. Nguyen对NTRU的选择密文攻击
提出的这种攻击同样利用了解密失败，攻击模型介于Jaulmes 和 Joux的限制性选择密文攻击和Howgrave-Graham等的实在论的模型之间。预言机仅在搜索解密失败的时候访问，如下面的算法1所示。从算法中，可以清晰的看出解密预言机仅用于产生合法的密文。此外，这些密文甚至不是由攻击者精选的，而是随机生成的。因为这些原因，攻击没有Jaulmes 和 Joux 的攻击强大。但攻击者有机会获得输出，这比Howgrave-Graham等的攻击获得更多的信息。
算法1：找到一个随机的解密失败
输入：NTRU参数集，公钥和解密预言机
输出：解密失败，如，
1：重复
2：生成一个随机消息，并且对其加密得到一个有效密文
3：记住或恢复加密使用的随机多项式
4：将密文提交给解密预言机
5：直到存在一个解密失败
6：返回三元组
这种攻击提出两个假设和两个启发：
假设1：如果(商环)是一个二元或三元的多项式是一致随机选择的，则中心为0的多项式的系数是相互独立的。
假设2：如果和是从有限的中心为0的多项式中随机选择的，且相互独立，如果它们的系数也相互独立，则的系数也相互独立。
启发1：如果解密失败，有一个系数在区间外的可能性相当高。
启发2;如果解密失败，超出范围的的系数非常接近于。更加准确的说，对于标准的NTRU参数，我们期望。
这种攻击也是建立在上文献[11]上，值得注意的是每一个解密失败生成了一个和的逆转的近似值。这里，更值得注意的是解密预言机的全部输出使得我们可以找出这些逆转。换句话说，预言机在每一个解密失败上的输出揭示了两个与和有许多相同系数的多项式。不幸的是，这个近似值没有显示正确系数的正确位置。因此在这个攻击中，为了计算出一个更加准确的近似值，需要求出从解密失败中推断出的众多的近似值的平均值，直到能通过四舍五入恢复。
具体算法如下：
输入：公钥
输出：私钥
1：
2：估计
3： loop
4：使用算法1找到一个解密失败
5：找到整数k使得
6：
7：或如果
8：
9：使
10：如果，则返回
11：使
12：如果，则返回
13：end loop
表3是用这个攻击进行实验的结果：
表4：实验结果
NTRU类型[12]
N

利用的解密失败的次数
恢复的的位数
NTRU-1998
167
3
128
32
50
100
N—3
N（all）
NTRU-2001
251
X+2
127
40
80
140
N—1
N（all）
NTRU-2005二元组
（使用较小的）
251
2
127
64
80
130
N—2
N（all）
NTRU-2005乘积形式
（使用较小的）
251
2
113
9
100
150
250
N—3
N—1
N（all）

图3：算法中估计的密钥的系数
从表3可以看出，恢复私钥所需的解密失败次数只有几百次。注意每密文中有一个解密失败，这意味着访问解密预言机的总次数大约为，运用没有优化的加密和解密算法只需要不到两天的时间。如图3所示，算法的主要目的是建立私钥的一个近似值。我们使用的解密失败越多，近似值就越准确。因为密钥值是整数系数，所以近似值最终达到一个精确水平，这只需要一个简单的四舍五入程序就足够完全恢复密钥值。
这两张图表示的是对于攻击NTRU-2005所估计的密钥（算法2步骤9的向量）系数的分布情况。不同层次的灰度代表相应的密钥系数的值。只有当这些不同的颜色被垂线很好的隔开时，攻击才起作用。第一张图片是在收集150次解密失败后得到的，第二张图片是在收集250次解密失败后得到。在第一张图片中，只有一个黑条错放在的区域中，所以在150次解密失败后，除了一个错误，我们已经恢复了的所有位。在第二张图片中，所有颜色被很好的隔开，所以私钥已经全部恢复。
5 总结
本文介绍了NTRU公钥密码体制和实现方法，并对其安全性进行了研究。NTRU算法被公认为是公开密钥体制中最快的算法，通过对NTRU的安全性分析和比较来看，它对系统要求极低，不需要较高的计算机能力以及较复杂的硬件设备，它高速、低需求、易实现、快速而安全的特性使得它适合于安全性要求高、体积、成本、内存及计算能力等受限的电子设备，必将在诸如智能卡、移动通信系统、保密数据网、电子商务、电子现金和微型支会系统及认证系统等业务方面发挥重要作用它完全有可能在公钥密码体制中占有重要地位，去代替现在非常流行的RSA密码体制。

23

参考文献
[1] 管海明.抗量子计算公钥密码需求分析与技术路线[J]. 专题研究 2009，4：12-13.
[2] 赵小龙，王衍波，郑学瑜，于杰山，端木庆峰.NTRU公钥密码体制安全性分析及攻击[J]. 军事通信技术，2004，25(2)：9-10.
[3] 杨 铭，曹云飞.NTRU 的应用前景分析与展望[J]. 信息安全与通信保密 2007，8：37-38.
[4]缪祥华，余位驰，张文芳，孙宇 .一种攻击NTRU公钥密码体制的方法[J]. 昆明理工大学学报，2006，31(2)：70-72.
[5] 卓泽朋，魏仕民.NTRU公钥密码体制及安全性分析[J]. 淮阴工学院学报, 2006，15(5)：65-66.
[6] 胡新祥. NTRU公钥密码体制的安全性分析和应用研究[D]. 西安：西安电子科技大学, 2005.
[7] 赵永斌. NTRU公钥密码体制的研究与应用[D]. 西安：西安电子科技大学, 2005.
[8] E. Jaulmes and A. Joux. A chosen ciphertext attack on NTRU[C]. Crypto’00, LNCS 1880, Springer-Verlag, 2000,P.23-26.
[9] N. A. Howgrave-Graham, P. Q. Nguyen, D. Pointcheval, J. Proos., J. H. Silverman,A. Singer, and W. Whyte. The impact of decryption failures on the security ofNTRU encryption[C]. Crypto ’03, LNCS 2729,Springer-Verlag, 2003, P.226–246.
[10] Nicolas Gama and Phong Q. Nguyen.New Chosen-Ciphertext Attacks on NTRU[C].PKC 2007,LNCS 4450, Springer-Verlag,2007,P.89-106.
[11]Daniel Roseneberg. NTRUEncrypt and Lattice Attacks[EB/OL]. http://www.nada.kth.se/utbildning/grukth/exjobb/rapportlistor/2004/rapporter04/rosenberg_daniel_04163.pdf

Principle and Security Analysis of NTRU
ZHOU Yang-hong 105012007093 Advisor:KE Pin-hui
Major in Pure and Applied Mathematics,College of Mathematics and Computer Science

【Abstract】NTRU is a relatively new public key system. Because the NTRU key generation method is easier, the speed of encryption,decryption is much faster than the RSA algorithm and other well-known algorithm, NTRU public key cryptosystem becomes a research hotspot.This paper introduces the principle of NTRU ,sums up the results of the analysis of the algorithm code, so as to provide some reference to the relevant theoretical research