抽象代数补充

卷积多项式环

定理：设$F$是域，非零多项式$m\in F[x]$，那么每个非零同余类$a\in F[x]/(m)$存在唯一的代表元$r$满足$\deg r<\deg m,a\equiv r(\bmod m)$。

对于商环$F[x]/(x^2+1)$，根据上面的定理可知商环的每个元素可以被唯一表示成$\overline{\alpha+\beta x},\alpha,\beta\in F$，有加法运算：

乘法运算类似，但是需要注意结果是在环上，需要取余：

给定正整数为$N$，可以构造卷积多项式环为$R=\frac{Z[x]}{x^N-1}$。模$q$的卷积多项式环为$R_q=\frac{(Z/qZ)[x]}{x^N-1}$，这里的模是指对于多项式的每个系数模$q$。

根据上面的定理可以得知卷积多项式环的元素都为以下形式：

根据除法取余可知，即模运算时只需将$x$次数模$m$：

通常为了简便把多项式$a(x)=a_0+a_1x+a_2x^2+…+a_{N-1}x^{N-1}\in R$表示成向量：

进行加法符合向量计算法则，对应系数相加。

进行乘法时，如果$a(x)\cdot b(x)=c(x)$且有$a(x),b(x)\in R_q$，先进行普通的多项式相乘写出结果（注意模幂），然后需要对$c_k$系数模$q$。

中心提升

设$a(x)\in R_q$，把$a(x)$对$R$的中心提升为$a’(x)$，记为$CL(a)$，满足$a’(x)\bmod q=a(x)$，$a’(x)$的系数满足$-\frac q2＜a_i’≤\frac q2$。

比起模多项式将$R$上多项式转换到$R_p,R_q$上，中心提升（Center-lift）将$R_p,R_q$中的多项式转换回了$R$中，且使得多项式系数绝对值最小。

转换规则也很简单：

例如如果$q=2$，$a(x)$的中心提升是系数为$0,1$的多项式。

当$N=5,q=7$时：

多项式$a(x)=5+3x-6x^2+2x^3+4x^4$的中心提升系数为${-3,-2,…,2,3}$，可得$CL(a)=-2+3x+x^2+2x^3-3x^4$。

多项式$b(x)=3+5x^2-6x^3+3x^4$的中心提升系数为${-3,-2,…,2,3}$，可得$CL(b)=3-2x^2+x^3+3x^4$。

注意到提升映射不满足环同态，即$CL(a)\cdot CL(b)≠CL(a\cdot b)$。

NTRU密码系统

参数引入

首先令$N＞1$，选定模数$p,q$，设卷积多项式环：

通过对系数模运算，可以将$R$中的多项式给转到$R_p$或者$R_q$的元素，反之可以利用中心提升将$R_p$或者$R_q$的元素给转到$R$中。

这里需要确定$N$是素数且$\gcd(N,q)=\gcd(p,q)=1$，再设$d_1,d_2$是正整数，定义一个集合：

这个集合里的多项式称为三值多项式。

密钥生成

Alice选择公开参数$(N,p,q,d)$，其中$N$和$p$为素数，满足$\gcd(N,q)=\gcd(p,q)=1$，$q＞(6d+1)p$。

Alice的私钥生成需要两个随机的多项式：

计算逆元$F_q(x)=f(x)^{-1}\in R_q$，$F_p(x)=f(x)^{-1}\in R_p$（逆元可能会不存在，不存在需要重新选择）。

计算公钥$h(x)=F_q(x)\cdot g(x)\in R_q$，对应的私钥为$(f(x),F_p(x))$。

加解密过程

Bob的明文为是$R$上的多项式$m(x)$，系数大小都在$-\frac p2$和$\frac p2$之间（$m(x)$是$R_p$多项式的一个中心提升），接受公钥之后选择一个随机多项式$r(x)\in \mathcal{T}(d,d)$，计算密文$e(x)=ph(x)\cdot r(x)+m(x)(\bmod q)$，密文$e(x)$在环$R_q$中。

Alice收到Bob密文后，计算$a(x)\equiv f(x)\cdot e(x)(\bmod q)$，将$a(x)$中心提升到$R$中之后得$b(x)$：

得到$m(x)$。

原理证明

证明NTRU加解密原理，需要证明在满足$q＞(6d+1)p$时Alice计算出的$b(x),m(x)$相等。

对于多项式$pg(x)\cdot r(x)+f(x)\cdot m(x)$，考虑其可能的最大值：

由于$g(x),r(x)$都在$\mathcal{T}(d,d)$上，所以卷积$g(x)\cdot r(x)$的最大可能系数为$2d$。

同理$f(x)\in \mathcal T(d+1,d)$，$m(x)$系数在$-\frac p2$和$\frac p2$之间，所以最大可能系数是$(2d+1)\frac p2$。

相加，最大可能系数就是$(3d+\frac 12)p$。

满足$q＞(6d+1)p$即为$\frac q2＞(3d+\frac 12)p$。Alice计算出的每一个系数在数量上都要严格小于$\frac q2$，所以经过计算并中心提升后就可以恢复出准确值，$a(x)$就是$R$中的多项式。

Alice然后计算$b(x)$就能得到$m(x)$：

安全性证明

在NTRU里的公钥$h(x)$的系数是模$q$下的随机整数，但是相关的$f(x)$和$g(x)$都是三值多项式，系数很小：

所以想要破解NTRU需要进行密钥恢复：给定$h(x)$如何找到$f(x)$和$g(x)$满足上式。

需要注意到私钥的解不唯一，如果$(f(x),g(x))$是一个解，对于$0≤k＜N$，$(x^kf(x),x^kg(x))$也是一个解，同余式的等价关系并没有变。

这里的$x^kf(x)$称作$f(x)$的循环。

恢复密钥的难点在于无法被穷举或者碰撞。如果使用穷举进行攻击，需要验证$f(x)\cdot h(x)(\bmod q)$是否是三值多项式。

根据$f(x)\in\mathcal{T}(d+1,d)$，需要先令$d+1$个系数为$1$，然后让剩下$N-(d+1)$个系数中的$d$个为$-1$，但是由于所有的$f(x)$的循环都满足，所以有$N$中选择。

举个例子，提供的公开参数为$(N,p,q,d)=(251,3,257,83)$，看起来数并不是很大，然而爆破出密钥需要的次数约为：

造格破解

格攻击就是格规约攻击，常用的用途是用来解小未知数方程。

这里的思想通过构造格得到私钥，也就是通过用公钥$h(x)$解出私钥$f(x)$和$g(x)$，和同余密码系统类似，但是这里我们构造的对象是多项式而不是之前的整数。

对于公共参数$(N,p,q,d)$和公钥$h(x)=h_0+h_1x+…+h_{N-1}x^{N-1}$，构造格：

这个格和同余密码系统的格形式上其实差不多，下面的推导也和同余密码系统的神似：

注意到格$L$的维度为$2N$，每个行向量有$2N$个坐标，可以看做用两个多项式向量链接在一起的向量，也就是说现在将私钥$f(x),g(x)$连在一起所得到的结果是否是格$L$的向量。

还是回到这个公式：

转为等式，但是这里补给$q$的参数不是整数而是多项式，这里设为$u(x)$把上式换个形式：

发现：

发现$(f,g)$是格中的向量，设公共参数$d≈\frac N3,q≈2N$，计算范数，比较一下高斯期望：

当$N$为大数，向量长度远小于高斯期望，格的最短向量就极有可能是向量$(f,g)$或者它的循环，即为得到了私钥。

一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bits = 512
while True:
  q = random_prime(2^bits, lbound=2^(bits - 1))
  R = GF(q)
  f = R(random_prime(2^(bits//2 - 1)))
  g = R(random_prime(2^(bits//2 - 1), lbound=2^(bits//4 - 1)))
  if gcd(f, q*g) == 1:
    h = f^(-1) * g
    break

print('q = %d' % q)
print('h = %d' % h)
# q = 11771107769919685639025680019132176714690799312096361547135769537209645333910623545026199750211710876592602157283472114417112848369348753900020624817689903
# h = 10244740934987488963223294332625298216569051945560244475215923413678863448556753932134017729009652572232483956393290621358806004252483727672873796530687963

# Aim: find f and g

这是一个一维的NTRU密钥的生成，在这个例子中，有方程：

已知$q,h$求解$f,g$，知道$f,g<\sqrt{\frac q2}$，$\gcd(f,qg)=1$。