针对NTRU算法的新型广播攻击

发布时间：2017-12-31 06:00

本文关键词：针对NTRU算法的新型广播攻击　出处：《密码学报》2016年06期 　论文类型：期刊论文

【摘要】：本文结合多次加密传送攻击和广播攻击的双重特征,提出了一种针对NTRU算法的新型广播攻击,并对该攻击进行了理论分析和实验验证.攻击者首先在不稳定信道(34)中利用多次加密传送攻击的思想,恢复噪声多项式ri的部分系数,从而建立有关明文m的线性方程组.然后在广播模型下获得足够多的线性方程组,从而快速求解出明文m.为充分挖掘噪声多项式的信息,进一步减少攻击所需要的信道数量,本文一方面利用噪声多项式之间发生的"伪碰撞",缩小未知系数的取值范围;另一方面通过直接猜测ri中未知系数,牺牲一定的正确率来获得更多信息.通过这些方法能在有限的信道中,建立更多关于m的方程.理论分析表明新的攻击方法不仅将建立关于明文的方程所需引入的变量个数从原来的N+[N/2]降低到N.而且完成一次攻击所需要的信道数也由原来的N+[N/2]-1+l减少到N/V(N,d/_r,k),这里V(N,d_r,k)=N(1-2(1-(d_r/N))~k+(1-(2d_r/N))~k),并且能够在O(N~3)的时间复杂度下恢复明文.实验结果表明,新广播攻击比原有的多次加密传送攻击、广播攻击更加高效,它对于更高安全等级的NTRU算法攻击仍然有效.
[Abstract]:In this paper, a new broadcast attack against NTRU algorithm is proposed based on the dual characteristics of multiple encryption transmission attack and broadcast attack. The attack is theoretically analyzed and verified by experiments. Firstly, the attacker uses the idea of multiple encryption transmission attack to recover part of the coefficients of noise polynomial ri in unstable channel 34). The linear equations about plaintext m are established, and then enough linear equations are obtained under the broadcast model, so that the clear text m. can be quickly solved to fully mine the information of noise polynomials. To further reduce the number of channels needed for attack, on the one hand, the "pseudo collision" between noise polynomials is used to reduce the range of unknown coefficients; On the other hand, we can get more information by directly guessing the unknown coefficients in ri and sacrificing a certain accuracy. These methods can be used in a limited channel. Theoretical analysis shows that the new attack method not only introduces the number of variables needed to establish the equation of plaintext from the original N. [The number of channels needed to complete an attack was also reduced from the original N. [N / 2] -1 / l is reduced to N / V / N / N / D / T / T / T / T / T / T / T / T / T / T / T / N / V / N / T / T / N / V / N. We can restore the clear text under the time complexity of the OTN / N3. The experimental results show that this method can be used to improve the performance of the system in the future. The experimental results show that the proposed method can be used to restore the clear text in the first half of the year, and the experimental results show that it is possible to restore the clear text under the time complexity of the OTN3. The new broadcast attack is more efficient than the original multiple encryption transmission attack, and it is still effective for the NTRU algorithm attack with higher security level.
【作者单位】：国防科学技术大学理学院;国防科学技术大学计算机学院;
【基金】：国家自然科学基金项目(61572026,11531002)
【分类号】：TN918.4
【正文快照】： 1引言NTRU(Number Theory Research Unit)是由Hoffstein、Pipher、Silverman三位数学家在Crypto 1996上提出的公钥密码算法[1].由于具有信息长度短,密钥产生容易,加解密速度快,内存需求低和抗量子攻击等优点,NTRU已成为最流行的公钥密码体制之一.1997年,Coppersmith和Shamir[2

【相似文献】