论文部分内容阅读
格是n维实线性空间Rn的离散加法子群，最短向量问题(SVP)和最接近向量问题(CVP)是格中的两种传统困难问题，本文将从线性空间和群两个角度来介绍格的基本概念和性质.求解SVP与CVP的方法称为格基规约算法，本文主要总结分析Lagrange规约、LLL规约及BKZ规约.1994年Shor提出了基于量子计算机模型解决大整数分解和离散对数问题的多项式时间算法，利用此算法RSA、ECC等公钥密码体制都将变得不安全.1996年J.Hoffstein等提出了基于整系数多项式环的NTRU密码体制，由于NTRU的难解性基于格中的SVP困难性，因此相对于之前的公钥密码体制NTRU具有加解密速度快、安全性高等优点.本文主要介绍NTRU密码体制的加解密算法，并从降低解密失败概率的角度分析参数选取，然后给出格攻击NTRU的分析.
为了进一步改进NTRU密码体制，2002年RGaborit首先提出将NTRU中多项式的系数由整数环替换为基于F2的多项式环，虽然该体制很快被攻破但却提供了非常重要的思想.随后又有人相继提出将整数环替换为Gaussian整数环、Eisenstein整数环等欧式环.本文主要研究基于Eisenstein整数环的ETRU密码体制，首先介绍Eisenstein整数的性质，给出一种新的Eisenstein整数除法算法，该算法要优于之前的除法算法;随后为了提升ETRU的加解密速度，构造了环(Z[ω]/)[x]/与环(Z/)[x]/之间的同构映射，利用此同构映射可以将ETRU的加解密速度提升为原来的4倍.最后给出格攻击和选择密文攻击ETRU的分析.