NTRU加密算法的一类弱密钥研究.pdf

《NTRU加密算法的一类弱密钥研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第9期计算机应用研究Vo1．31No．92014年9月ApplicationResearchofComputersSep．2014NTRU加密算法的一类弱密钥研究牟宁波(中国社会科学院金融研究所博士后流动站，北京100732)摘要：分析了NTRU公钥加密算法的一类弱密钥。根据NTRU所涉及的cs格与循环码的生成矩阵结构相似的特点，指出5-NTRU的公钥与(一1)的最大公因式的次数大于零时，CS格的生成矩阵不可逆，此时可用类似于循环码译码的方法和格基归约算法破解NTRU。最后给出了能使NTRU避免生成此类弱密钥的方法。关键词：NTRU；循环码译码；弱密钥；格基

2、归约中图分类号：TN918．1；TP309文献标志码：A文章编号：1001—3695(2014)09—2784·04doi：10．3969／j．issn．1001—3695．2014．09．053ResearchonweakkeyofNTRUencryptionschemeMUNing—bo(PostdoctoralResearchStation，InstituteofFinance＆Banking，ChineseAcademyofSocialSciences，Beijing100732，China)Abstract：Thispaperanalyzedaclasso

3、fweakkeysofNTRU．AccordingtothesimilaritybetweenthestructuresoftheCSlat—riceinNTRUandthegenerationmatrixofcycliccode，whenthedegreeofthegreatestcommondivisorofNTRUpublickeyand(一1)wasgreatthanzero，generationmatrixofCSlatticewasnotreversibleandNTRUcouldbebrokenbythedeco—dingtechniqueofcycl

4、iccodeandlatticereductionalgorithm．FinallyitproposedamethodtoprotectNTRUagainstthisflaw．Keywords：NTRU；cyclecodedecoding；weakkey；latticereductionHofstein等人⋯在1998年提出的NTRU加密算法是当今加密：e=prh+m(roodq)快速公钥的代表算法之一。NTRU能够快速地生成密钥且加／解密：d=el(roodq)，m=‘(modP)解密所需的运算量较小，这使得它在一些数字设备和安全标有一点需要说明：计算d=ef=p

5、rg+mf(modq)后，当d=准’中广泛应用。与此同时，也出现了一些对NTRU的有效(prg+)的每个系数都在(一q／2，q／2]中时，d=d，此时分析与攻击。本文通过循环码构造和译码的方法研究了‘=prd；。+m=m(modP)。当d的系数不在(一q／2，q／2]对NTRU的攻击，根据NTRU加密结构的特点，提出了一种新中时，便发生解密失败。解密失败的存在给NTRU带来了一系的攻击NTRU的方法。当NTRU的公钥h是模(一1)生成的列非常有效的攻击’，适当的参数选取可以避免解密失败的多项式环上的零因子时，可以用对密文乘以零因子和格基归约发生，具体可参考文献[8]

6、。的方法来破解NTRU。1．3NTRU基于的困难问题格是空间中一类具有周期性结构离散点的集合。具体来1NTRU公钥加密算法说，n维线性空间中m个线性无关的向量(b．，b，⋯，b)所生符号约定：P、q为两个互素的正整数，且P<

7、，完成后各系数取值在(一i／2，i／2]中)；L(，Y)为R[](closestvectorproblem，CVP)。所谓最短向量问题是指对于给上个系数为1、Y个系数为一l、其余系数为0的多项式集合；定的一组基，找出其所生成的格中欧几里德长度最小的非零向。。为多项式在环R[]上的逆元，即～xf=1(modi)。除量；所谓最近向量问题是指对于给定的格及任一向量，在格中特别说明外，下文所有运算都是在多项式环R[]上进行的。找出距该向量最近的向量。这两个计算问题都是NP困难的。1．1密钥生成DonCoppersmith等人指出，破解NTRU的困难来自于Cs取l厂L(，