密码学---公钥密码---NTRU公钥密码系统

NTRU公钥密码系统概念

NTRU是一种基于环的公钥密码系统，系统的特点是密钥短且容易产生、算法的运算速度快、所需的存储空间小

NTRU公钥密码系统流程

系统建立在整系数多项式环上，现对多项式环做如下介绍：
设R表示最高次数不超过N-1的所有整系数多项式集合，设a=a₀+a₁x+a₂x²+…+a_N-1x^N-1，b=b₀+b₁x+b₂x²+…+b_N-1x^N-1是R上的两个元素，且定义R上的加法定义为：a+b=(a₀+b₀)+(a₁+b₁)x+(a₂+b₂)x²+…+(a_N-1+b_N-1)x^N-1。乘法定义为：a×b=c₀+c₁x+c₂x²+…+c_N-1x^N-1，其中c_k的定义如下所示：

参数

NTRU公钥密码的参数包括3个整数(N,p,q)，其中p和q不要求是素数，但满足gcd(p,q)=1其q大于p
还包括4个次数为N-1的整系数多项式集合L_f，L_g，L_Φ，L_m。

密钥产生

密钥的产生由接受方B完成。过程如下：
1.随机选取两个多项式f，g∈L_g，且多项式f在模q和模p下均可逆，逆元用F_q和F_p表示。即F_q×f ≡ 1 (mod q)和F_p×f ≡ 1 （mod p）
2.计算h=F_q×g (mod q)
3.确定公钥为h，私钥为f，且接收者还需要保存F_p

加密流程

有明文数据m∈L_m，对m进行加密操作：
1.随机选取多项式Φ∈L_Φ
2.用公钥h对明文消息进行加密，得到密文c的结果如下所示：
e≡pΦ*h+m (mod p)

解密流程

对密文数据e，用私钥f对其进行如下解密操作：
1.计算a≡f*e (mod q)，a的系数选在(-q/2,q/2)范围内
2.将a作为一个整系数多项式，计算F_p*a(mod p)即可恢复明文m