文档介绍：典型抗量子公钥加密算法分析
摘要：量子计算机便是一种理论上计算量可以无限大的一台并行计算机。如果我们采用这种量子计算机来穷举法***密码，由于其可以在同一时间进行多种状态的运算，现有的大多数密码技术所产生的密文都将被完全破译。在量子计算出了NTRU公钥加密算法。NTRU公钥加密算法不仅能够抵御可能出现的量子计算机的暴力破译，而且在密码算法所基于的数学问题上比现在市面上大多数采用的RSA及ECC椭圆曲线算法更难以破解。从现阶段的研究来看，NTRU公钥加密算法所基于的数学困难问题是难以被量子计算机所***的。不仅如此，在加解密的速度方面，NTRU因为流程相对简单，步骤简洁，其运算速度比现有的大多数加密算法更胜一筹，公钥系统也相对容易实现。总的来说，我们有理由相信后量子公钥加密算法（NTRU）完全有可能在未来的公钥密码体系中占有主导地位。（N，p，q），以及四个N-1次整数系多项式的集合。该算法的加密以及解密过程均是在多项式截断环R=Z[X]/（XN-1）上运算。对于整数p和q，他们不需要是素数，但必须满足gcd（p，q）=1，且q必须远远大于p。我们设：L（d1，d2）意味着对于多项式F属于R，多项式中共有d1个系数为1，d2个系数为1，则剩余的系数均为0，可以得到以下多项式的集合：Lf=（df，df-1）（1）Lg=（dg，dg-1）（2）Lr=（dr，dr-1）（3）Lm定义为：m属于多项式R且m的系数位于区间-（p-1）/2到（p-1）/2之间（4），绝大部分的运算都是发生在多项式截断环R=Z[X]/（XN-1）上。通过了解该加密算法的加解密流程，我们可以得知加密时需要用多项式h和多项式r想乘，而在解密时需要用私钥f与密文多项式e相乘得多项式a，且还原明文时会用到私钥f模p的逆Fp与多项式a相乘得到解密后得明文m我们不妨设私钥f多项中系数-1和系数+1的个数相等均为d，这样在使用扩展欧几里得算法时就可以很简单的得出私钥f模p的逆Fp=1。通过设置私钥f的多项式中正负一系数的个数就可以提高NTRU加密算法的运算速率。我们随机生成两个次数不高于N-1次的多项式f和g分别属于Lf和Lg，Fp，Fq分别为多项式f模算法参数p和q的逆。我们需要用扩展欧几里得算法来对Fp和Fq是否存在进行验证。对于扩展欧几里得算法：设存在整数a，b，则一定存在整数x，y满足：ax+by=gcd（a，b）（5）当b=0时存在x与y为最后一组解，而每一组的解均可以根据最后一组求得。所以第一组的解x与y必定存在，这时可用递归算法，求得b=0时返回x=1，y=0。再根据x1=y2，y1=x2-k*y2可得当层的解，由此不断返回可得原解。将整数a，b扩展为多项式则可以得到设存在多项式a（x），b（x），则一定存在u（x），v（x）满足u（x）a（x）+v（x）b（x）=gcd（a（x），b（x））（6）在这种前提下，我们不妨设私钥多项式f为a（x）且b（x）=（xN-1）=（x-1）（xN-1+xN-2+……+x+1）代入即可算出第一层的多项式为私钥f模p和q的逆元。在此的基础上我们可以合理推测，若存在gcd（f，xN-1）=1mod2；那么也就存在多项式u（x）与多项