格密码入坑到入土一条龙
NTRU(Nth-degree TRunctuated polynomial Unit)，即“N次截断多项式单元”，是格密码中极为知名、应用较广的一种加密原理。
截断多项式？
卷积多项式环
给定 \(N,q \in Z_{+}\)，则模 \(q\) 下的 \(N - 1\) 次卷积多项式环是一个商环(quotient ring)，记作 \(R_{q} = \frac{Z_{q}[x]}{x^{N} - 1}\)。
商环的定义为对环(Ring)上，\(\forall a \neq 0 \in R, \exists a^{-1} \in R\)，即除了加法单位元 \(0\) 外所有元素均存在逆元。
\(R_{q}\)
下的卷积多项式乘法规则如下：假设 \(f \cdot g =
h\)，同样记 \(h =
\sum_{i=0}^{n-1}h_{i}x^{i}\)，存在
$h_{i} {a+b i (N)} f{a}g_{b} (q) $。
不难发现上述规则和普通的多项式乘法并无显著差异，只是对幂数和项数的计算分别放在了 \(Z_{N}\) 和 \(Z_{q}\) 下进行。
写作 \(Z_{q}\) 下 \(n \times n\) 矩阵乘法的形式，形如：
\(\begin{bmatrix} h_0 & h_1 & \cdots & h_{n-2} & h_{n-1} \end{bmatrix} ^ {T} = \begin{bmatrix} f_0 & f_1 & \cdots & f_{n-2} & f_{n-1} \\ f_1 & f_2 & \cdots & f_{n-1} & f_0 \\ \vdots & \vdots && \vdots & \vdots \\ f_{n-1} & f_0 & \cdots & f_{n-3} & f_{n-2} \end{bmatrix} \cdot \begin{bmatrix} g_0 & g_1 & \cdots & g_{n-2} & g_{n-1} \end{bmatrix} ^ {T}\)
若 \(q\) 比较大，考虑到可读性，一般展示时会将 \(f_{i}\) 转化到 \((-\frac{q}{2},\frac{q}{2}]\) 的区间内（当然 \(Z_{q}\) 下其是等价的）。
如，\((N,q) = (3,5)\) 下 \(f = 3x^{2} - x + 1\)，\(g = x + 4\)，计算 \(f \cdot g\)：
先按普通的多项式计算，对 \(N\)
次以上的项进行“截断”，得到 \(12x^{2} - x^{2} -
4x + x + 4\)；
随后将系数映射至 \(Z_{5}\)
下，整理得到结果为 \(x^{2} - 3x + 4 = x^{2} +
2x - 1\)。
而对于 \(R_{q}\) 下的 \(N-1\) 次多项式 \(f\)，当且仅当 \(q\) 为质数且 \(gcd(f,x^{N} - 1) = 1\)（即，\(f\) 是其本原多项式）时， \(f\) 的乘法逆元 \(f^{-1} \in R_{q}\)。
\(f^{-1}\) 的计算同样可以通过拓展欧几里得算法(exgcd)进行，详细原理请自行检索
绝对不是因为小姜讲不明白。
多项式的逆元计算实际上较为繁琐，定义等操作亦然，故建议处理多项式时充分利用数学软件的内置支持，如 “sage magic” 演示：
1 | q = 17 |
参数与密钥生成
NTRU的关键参数为 \((N,p,q,d)\)。其中，
- \(N,q\)
越大则格攻击构造格的维度越高，密码系统越安全，但运算效率会大幅下降；一般选择
\(N \in [250,2500]\)。
- \(p,d\) 均为整数，要求 \(gcd(p,q) = 1\) 且 \(gcd(q,N) = 1\)，\(q > (6d + 1)p\)。
NIST对NTRU的强度-推荐参数组合如下：
| 强度 | N | p | q |
|---|---|---|---|
| 标准 | 251 | 3 | 128 |
| 高 | 347 | 3 | 128 |
| 最高 | 503 | 3 | 256 |
参数 \(d\) 可在满足 \(q > (6d + 1)p\) 下自行决定，一般选择 \(d \approx \frac{N}{3}\) 来达到较好的安全性。
定义函数 \(T(d_{1},d_{2}) (d_{1} + d_{2} < q)\) 表示系数 \(\{1,-1\}\) 计数分别为 \(\{d_{1},d_{2}\}\) 的多项式 \(f\) 的集合。
如，\(f = x^{6} + x^{3} - x^{2} + x - 1 \in T(3,2)\)。
选择两个多项式 \(f = \sum_{i=0}^{N-1} f_{i}x^{i} \in T(d+1,d)\)，\(g = \sum_{i=0}^{N-1} g_{i}x^{i} \in T(d,d)\)。
再计算 \(h \equiv f^{-1}g (\bmod
q)\)，随后将 \(g\)
的记录销毁。
公钥为 \(h\)，私钥为 \(R_{p}\) 和 \(R_{q}\) 下的 \(f^{-1}\)（由于 \(p,q\) 是既定参数，可以认为私钥就是 \(f\)）。
\(g\) 不是公钥或私钥，但知道 \(g\) 就可以完全攻破NTRU，其地位类似于RSA中 \(N\) 的因数分解，故不应保留之。
加密
先将明文编码为一个 \(n\) 次多项式
\(m \in \{-1,0,1\}^{N}\)。
加密时另随机生成一个多项式 \(r \in
\{-1,0,1\}^{N}\)，计算 \(c \equiv ph
\cdot r + m (\bmod q)\)，输出密文 \(c\)。
解密
计算 \(m \equiv f^{-1} \cdot (f \cdot c (\bmod q)) (\bmod p)\)，输出明文 \(m\)。
注意其中涉及到了“换环”，即现在 \(R_{q}\) 下计算 \(f \cdot c\)，将结果转到 \(R_{p}\) 下后再与该环下的 \(f^{-1}\) 相乘。
正确性证明
先在 \(R_{q}\) 下计算， \(f \cdot c = pr \cdot hf + mf \Rightarrow f \cdot c
= prg + mf\)
随后换环到 \(R_{p}\) 上，显然 \(prg \equiv 0 (\bmod p)\)，因此 \(R_{p}\) 下 \((fc
\bmod q) \equiv fm\)
进而 \(fmf^{-1} = m\)
解密正确性得证。
公钥攻击与数学难题
NTRU作为一种公钥密码体制，其依然依赖于数学难题来实现公钥与私钥间的“陷门”特征——即从公钥推导出私钥在理论上是可行的。
已知公钥时推导私钥的方法如下：
假设公钥为 \(f =
\sum_{i=0}^{n}f_{i}x^{i}\)，即 \(\{f_{i}\}\) 是多项式 \(f\) 各项的系数。
有关格、格基规约(LLL)等相关的基础知识可以移步格。
加解密、攻击应用示例
假设Alice和Bob怎么又是你们俩需要利用NTRU进行通信，Alice为接收方，参数
\((N,p,q,d) = (77,3,59,3)\)。
充分利用一番sage对多项式环的支持，代码如下：
1 | # sage |
现在生成了一组公钥：
1
[0, 0, 2, 1, 1, 0, 2, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 0, 2, 1, 2, 0, 1, 0, 2, 1, 0, 0, 2, 1, 2, 0, 0, 0, 2, 2, 0, 1, 1, 2, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 0, 2, 2, 2, 0, 0, 2, 2, 1, 0, 1, 0, 0, 2, 0, 1]
i的数就是 \(h_{i}\)，即 \(h\) 中 \(i\) 次项的系数。
Bob使用该公钥，对接下来通信使用的密钥进行加密，为NTRU类添加一个encrypt方法并运行之：
1
2
3
4
5
6
7def encrypt(self,m:list):
assert len(m) == self.N
assert all(i in (-1,0,1) for i in m)
r = self.T(7,7)
c = self.p * self.h * self.Rp(list(r)) + self.Rp(m)
return list(c)
1 | # Key generated |
Alice接收之，并利用私钥进行解密，获得密钥：
1 | def decrypt(self,c:list): |
结果正确。 但由于参数选择得比较小，若某人获得了他们的公钥 \(h\)，即可实施格攻击来还原私钥，需要的参数仅为 \((N,q)\)。攻击过程：
1 | from itertools import product |
总结
格密码是后量子密码学中极为重要的一环，而其中NTRU亦以其实现开销低等特性称为其中耀眼的新星。
学习NTRU算法的加密、解密原理时更应发挥离散数学的优雅之处——只定义“模板”，无论最终的实现是在
\(Z_{q}\)、\(P_{q}\) 还是 \(R_{q}\) 等等都能一通百通。
而对NTRU的格攻击则开启了基于分块矩阵的多变量、较复杂格构造的新大门。