格密码入坑到入土一条龙
NTRU(Nth-degree TRunctuated polynomial Unit)，即“N次截断多项式单元”，是格密码中极为知名、应用较广的一种加密原理。
截断多项式？
定义一个多项式 \(f \in R_{q}\) 。
参数与密钥生成
NTRU的关键参数为 \((N,p,q,d)\)。其中，
- \(N - 1\)
为多项式的最高幂数。越大则格攻击构造格的维度越高，密码系统越安全，但代价是运算效率会大幅下降；一般选择
\(N \in [250,2500]\)。
- \(p,q,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}\) 下计算， \(\begin{align*} f \cdot c &= pr \codt hf + mf
\\ f \cdot c &= prg + mf \end{align*}\)
随后换环到 \(R_{p}\) 上，显然 \(prg \equiv 0 (\bmod p)\)，因此 \((fc \bmod q) \equiv fm (\bmod p)\)
进而 \(R_{p}\) 下 \(fmf^{-1} = m\)
解密正确性得证。
公钥攻击与数学难题
NTRU作为一种公钥密码体制，其依然依赖于数学难题来实现公钥与私钥间的“陷门”特征——即从公钥推导出私钥在理论上是可行的。
已知公钥时推导私钥的方法如下：
假设公钥为 \(f =
\sum_{i=0}^{n}f_{i}x^{i}\)，即 \(\{f_{i}\}\) 是多项式 \(f\) 各项的系数。
有关格、格基规约(LLL)等相关的基础知识可以移步格。
加解密、攻击应用示例
总结
格密码是后量子密码学中极为重要的一环，而其中NTRU亦以其实现开销低等特性称为其中耀眼的新星。
学习NTRU算法的加密、解密原理时更应发挥离散数学的优雅之处——只定义“模板”，无论最终的实现是在
\(Z_{q}\)、\(P_{q}\) 还是 \(R_{q}\) 等等都能一通百通。
而对NTRU的格攻击则开启了基于分块矩阵的多变量、较复杂格构造的新大门。