NTRU加密算法

2022-10-28

随着信息技术的迅猛发展和一些高技术武器设备、通信指挥系统等的需要，未来军事部门将大量地使用公钥密码技术。由于RSA 和ECC 加密算法不能抗量子计算攻击，而NTRU加密算法能抗量子计算攻击，且速度快和安全性高，特别别适合用于诸如智能卡，保密蜂窝电话系统，保密传真、无线保密数据网，以及认证系统等业务。

NTRU加密算法简介

NTRU加密算法是1996年由美国布朗大学三位数学教授发明的公开密钥体制。经过几年的迅速发展与完善，NTRU加密算法在密码学领域中受到了高度的重视并在实际应用中取得了很好的效果。

一、参数说明

NTRU加密体制中，选取了三个整数参数（n,p,q）和四个多项式集合Rf,Rg,R_Φ ,Rm，这些集合中的多项式次数小于N-1，系数均为整数。p,q不一定是素数，但必须满足gcd(p,q)=1，而且q远远大于p。

二、NTRU 加密算法密钥的生成

随机生成2 个多项式f∈Rf,g∈Rg，其中f必须满足在模p和模q的情形下均有乘法逆元。如果参数选择合适，大多数的f都有逆元，而且可以通过改进欧几里得算法很容易找到这些逆元。用Fp,Fq分别表示这两个逆元，即

Fq_f ≡1(modq)

Fp_f ≡1(modp)

然后，计算

h≡Fq_g_(modq)

多项式h即为公钥，私钥为f，实际上Fp,Fq也必须保密。

三、NTRU加密算法加密过程

假设要加密的消息m∈Rm，随机选取多项式φ∈Rφ，然后利用公钥h进行如下运算：

e≡Pφ_h_+m(modq)

多项式e为消息m对应的密文。

四、NTRU加密算法解密过程

收到密文e后，可利用私钥f进行解密。Fp必须预先计算。解密首先计算

a≡f_e(modq)

其中选取多项式a的系数在区间[-q/2,q/2]内。然后通过如下计算恢复明文：

Fp_a(modp)。

五、NTRU加密算法解密过程工作原理

多项式a满足：

a≡f_e≡f_PΦ_h+f_m(modq)

a≡f_e≡f_PΦ_Fq_g+f_m(modq)

a≡f_e≡PΦ_g+f_m(modq)

对于最后一个多项式PΦ_g+f_m，如果参数选择合适，这个多项式的系数都可以限制在区间[-q/2,q/2]内，因此，这个多项式在所有系数模q的情形下不会改变。这意味着将f_e(modq)的所有系数都选取在区间][-q/2,q/2]内，的确可以得到正确的

a=PΦ_gf_m∈Z[X]/(Xn-1)

将多项式a进行模p约化，可得到f_m(modp)，然后用Fp去乘上述多项式即可得到相应的明文消息m(modp)。

NTRU加密算法的安全性

NTRU加密算法的安全性介于RSA和ECC加密算法之间。

NTRU加密算法的优点

NTRU加密算法设计的非常巧妙，整个加密算法只包括小整数的加、乘和模运算，在相同安全级别的前提下，NTRU加密算法的速度要比其它公钥密码体制的算法快得多，NTRU加密、解密一个长度为N的信息块需要0（N2）次操作，RSA加密算法需要0（N3）次操作，所以NTRU加密算法比RSA加密算法快至少100倍。用NTRU加密算法产生密钥的速度也很快，它的密钥产生速度比RSA加密算法快300倍。

NTRU加密算法的缺点

NTRA公钥加密系统并没有提供完善的解密机制，也就是说存在着用公钥加密产生合法密文不能被私钥解密的现象。攻击者可能利用这一点来进行攻击，攻击者会利用DC判断程序来判断合法的密文是否被正确解密，通过系统提供的相关信息来恢复用户的私钥，不过可通过对系统参数的仔细选择，使解密失败的概率可小于5×10的-5次方。

国外有很多研究机构正在对NTRU加密算法安全性进行研究，但到目前为止还没有任何理由说明NTRU加密算法是不安全的，有理由相信NTRU加密算法完全有可能在公开密钥体制中占有主导地位。

小知识之公开密钥密码体制

公开密钥密码体制的产生主要是因为两个方面的原因，一是由于常规密钥密码体制的密钥分配问题，另一种是由于对数字签名的需求。