只要是从事网络安全或安全软件开发的人，就都可能已经了解过公钥加密以及在 20 世纪 70 年代末和 80 年代前后创建的方法。现在我们可能需要学习更多的理论，因为我们所学的方法可能会受到量子计算机的威胁。

如果想开始学习这些新方法，那就有必要往下读了。

(mod p) 运算

在传统的公钥加密中，我们使用一个模数来创建有限域。虽然这听起来很复杂，但实际上这是一个非常简单的概念。对于有限域，我们引入一个模数，它通常是一个素数。对于素数，我们从整数除法中确定余数，然后取余数作为结果。例如，如果素数为 17，我们将得到 0 到 16 范围内的输出值：

5 (mod 17) = 6 19 (mod 17) = 2 100 (mod 17) = 15

(mod p) 运算的伟大之处在于，我们仍然可以进行加减乘除，并最终得到相同的结果，例如：

15 (mod 17) +100 (mod 17) = (15+100) (mod 17) = 13 15 (mod 17) * 100 (mod 17) = (15*100) (mod 17) = 4

在离散对数中，我们经常使用 Diffie Hellman 方法，我们选择一个共享素数 (p) 和一个共享生成器值 (g)，并计算：

A = g^x (mod p) B = g^y (mod p)

交换 A 和 B，共享密钥为：

K = A^y (mod p)

之所以有效，是因为：

K = A^y (mod p) = (g^x)^y (mod p) = g^{xy} (mod p)

在 RSA 方法中，我们使用模数 (N)。对于加密，我们有：

C = M^e (mod N)

要破译：

M = C^d (mod N)

在这种情况下，N 是两个素数的乘积，RSA 的优势在于分解模数 (N) 的难度。椭圆曲线方法也使用一个素数 (p) 的模数，其中我们有：

y² =x³ + ax + b (mod p)

这将我们在椭圆曲线上使用的点的值限制在 0 和 (p-1) 之间。

多项式

但是，量子计算机将破解 RSA、椭圆曲线和离散对数，那么后量子密码学中的模数相当于什么？我们可以使用格加密，这涉及到我们使用多项式值来表示我们的位串。

如果我们有一个值 19，它可以表示为 10011 和一个多项式值：

x⁴+x+1

67 可以用 1000011 表示，并且是一个多项式：

x ⁶+ x +1

如果我们把这两个多项式相加，我们得到：

( x⁴ + x +1)+( x ⁶+ x +1)= x ⁶+ x ⁴+1+1

因为我们使用的是 Base 2，所以 1+1 等于 0，因此我们得到：

( x⁴ + x +1)+( x ⁶+ x +1)= x ⁶+ x ⁴

同样的道理也适用于添加相同的幂，例如:

x⁴ + x⁴ = 0 x⁴ + x⁴ + x⁴ = x⁴

以此类推。

在格密码中，我们用多项式进行加，减，乘，除。一个运算可能有一个 x³+x+1 的多项式，和一个 x²+1 的秘密多项式，然后将它们相乘得到一个结果。为了恢复原来的值，我们可以除以秘密多项式。

但是，我们如何将多项式的最大幂限制在有限域内呢？就像我们用传统的公钥方法那样，我们用一个模数，然后除以模数，保留余数。

有限域的模数

有限域或 Galois 域 (GF) 具有有限数量的元素，并且阶数等于素数 (GF(p)) 或素数的幂 (GF(2^ p ))。例如，GF(2^n) 有 2^n 个元素，它的元素被称为二元多项式 ( 其中多项式因子的系数要么为零，要么为一个值 )。为了将多项式减少到给定的大小，我们使用一个模数多项式，它除以输出值。对于 GF(128)，我们可以使用 x ⁷+ x +1 的模数。

让我们举个例子：

a = x³ + x ²+1

b = x ⁶+ x ⁴+ x ³+1

当我们相加时，得到：

a + b = x ³+ x ²+1+ x ⁶+ x ⁴+ x ³+1= x ⁶+ x ⁴+ x ²

现在，我们把它们相乘：

a × b =( x ³+ x ²+1)×( x ⁶+ x ⁴+ x ³+1)= x⁹ + x ⁷ + x ⁶+ x ³+ x ⁸+ x ⁶+ x ⁵+ x ²+ x ⁶+ x ⁴+ x ³+1= x ⁹+ x ⁸+ x ⁷ + x ⁵+ x ⁴+ x²+1

我们现在用这个值除以模数。在此例中，对于 GF(128)，模数是 x⁷ + x +1：

对于 GF(128)， a×b 的结果如下：

a × b = x ⁶+ x ⁵+ x ⁴+ x ³+ x ²

在 Sage 中：

示例运行：

如果我们现在使用 GF(256) ：

示例运行：

我们可以看到，在 Sage 中 GF(256) 的默认模数为：

x ⁸+ x ⁴+ x ³+ x ²+1

我们可以在 Sage 中使用列出默认模值：

给出了：

不可约多项式

就像公钥加密中的素数一样，我们需要一个不能被任何数整除的多项式。为此，我们使用一个不可约多项式。不可约多项式的例子有：

我们的不可约多项式是 x、x²、x²+x+1 和 x³+x²+1。它们等价于我们在传统公钥加密方法中使用的素数，并类似于 (mod p) 运算。一种常用的方法是 x⁸+x⁴+x³+x+1，用于 AES 加密。在 Sage 中，我们可以定义自己的模数，例如：

k.<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)

如果我们有 y = x ⁵+ x ³+ x ²+1 的输入值 101101，我们乘以 h = x ⁴+ x +1，我们得到：

r = yh = (x⁵+x³+x²+1) × (x⁴+x+1)

然后我们可以创建以下 Sage 代码：

\# Rijndael finite field

k.<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)

y = (x^5+x^3+x^2+1)

h= (x^4+x+1)

r=y*h

print(f"(x^5+x^3+x^2+1) * (x^4+x+1)= {r} ({r.integer_representation()})")

当运行时，我们会得到的结果：

$ sage 1.sage

(x^5+x^3+x^2+1) * (x^4+x+1)= x^7 + x^4 + 1 (145)

现在可以除以我们的不可约多项式，得到原来的值：

\# Rijndael finite field

k.<x>= GF(2^8, modulus=x^8+x^4+x^3+x+1)

y = (x^5+x^3+x^2+1)

h= (x^4+x+1)

r=y*h

r2=r/h

print(f"{r}/ (x^4+x+1)= {r2} ({r2.integer_representation()})")

得到的结果：

$ sage 1.sage

x^7 + x^4 + 1/ (x^4+x+1)= x^5 + x^3 + x^2 + 1 (45)

我们可以看到乘法，除法，加减法，这些运算都是可逆的。

结论

公钥加密的旧篇章即将结束，新篇章即将开启。在 20 世纪 70 年代末完成的工作对我们很有帮助，但现在我们面临着量子计算机会打破这些方法的威胁。事实上，我们开发的方法从来都不是真正可证明的难题——它们只是在传统计算机中难以破解。所以，让我们来看看多项式，模和格的奇妙世界。