NTRU密码

简介： NTRU 加密算法，是 RSA 和椭圆曲线加密ECC 的基于 NTRU 格的替代方案，并且基于格中的最短向量问题。

它依赖于将截断多项式环中的某些多项式因式分解为具有非常小的系数的两个多项式的商的假定困难。

1、NTRU加密算法

首先随机选取素数 $p,g$ ，随机数 $f$ ，要求： $g<f<p，gcd(f,g)=1$

计算：$h=f^{-1}g(modp)$

公钥： $(h,p)$

私钥： $(f,g)$

临时密钥：$r$

加密公式： $c\equiv rh+m(modp)$

解密公式：

令 $a=fc(modp)=rhf+mf(modp)=rg+mf(modp)$

$m\equiv a\ast f^{-1}(modg)=>m\equiv rg{f}^{-1}+m(modg)$

所以 $m\equiv a\ast f^{-1}(modg)$

2、求解私钥

题目给的已知量：公钥 $(q，h)$ 和 密文 e

$h=f^{-1}\ast gmodq$，$e=(r\ast h+m)modq$

需要求解私钥：$(f,g)$

由 $h=f^{-1}\ast gmodq$ 得： $h\ast f=g+k\ast q\Rightarrow h\ast f-k\ast q=g$

选定一组向量 (1 , h) ，(0 , q) ，构造线性无关的向量组 $M=\left[\begin{array}{cc}1& h\\ 0& q\end{array}\right]$ ，作为格 L 的基。

根据线性关系可以构造格 L：$\left[\begin{array}{cc}f& -k\end{array}\right]\left[\begin{array}{cc}1& h\\ 0& q\end{array}\right]=\left[\begin{array}{cc}f& g\end{array}\right]$

向量 （f , g）可以由这组格基向量 M 和整数系数（f , -k）线性组合表示，因此向量 （f , g）也在格 L 上。

所以我们可以利用 LLL 算法计算出这个格的最短向量，也就是私钥 $(f,g)$