带余除法#

从小学数学开始，老师教过我们带余数的除法，例如 $7 ÷ 3 = 2…1$。它的正式定义如下：

对于任意整数 $a$ 和正整数 $n$，存在唯一的整数 $q$（商）和 $r$（余数），使得：$a = n \times q + r, \quad 0 \leq r < n$

这里要求 余数必须是非负的，且必须小于除数。数学上可以有负余数，但在计算机和密码学标准里，我们通常要求 $r \ge 0$。

所以根据这个原理，$-17 \mod 5 = ?$ 因为余数是非负的，所以 $-17 = 5 \times (-4) + 3$，余数是 $3$, 而不是 $-2$。面对负数 $a$ 取余数的情况，我们可以直接加除数 $n$ 的 $q$ 倍，直到为正数，剩余的部分即为余数，即 $r = a + n \times q, \quad a<0$。

因为 $0 \le r<n$，可能会出现余数相同的情况，例如 $6 \div 5 = 1 \dots 1$, $11 \div 5 = 1 \dots 1$。于是我们定义：

如果在除以同一个数 $n$ 时，两个整数 $a$ 和 $b$ 的余数相同，则称 $a$ 与 $b$ 模 $n$ 同余，记作：$a \equiv b \pmod{n}$

例如：

• $17 \equiv 2 \pmod{5}$ ✓ （都余 2）
• $23 \equiv 2 \pmod{7}$ ✓ （都余 2）
• $100 \equiv 2 \pmod{7}$ ✓ （100÷7=14 余 2）

例如 $11 \equiv 6 \pmod 5$，我们可以将其写回带余除法的形式：

• $11 = 5 \times 2 + 1$
• $6 = 5 \times 1 + 1$ 它们只是商不同，除数 $n$ 和余数 $r$ 都相同。那我们看看 $11 - 6$ 的形式：

我们可以发现，余数已经消失了，所以可以得到同余的一个推论：

如果在除以同一个数 $n$ 时，两个整数 $a$ 和 $b$ 的余数相同，则 $n$ 能整除它们的差，记作：$n \mid (a - b)$

对于除数 $n$，我们按照除 $n$ 的余数对被除数 $a$ 进行分类。因为 $0 \leq r < n$，所以按照余数分类可以分成 $n$ 种类型，我们把每一种分类称为一个 剩余类 (Residue Classes)。它的正式定义如下：

对于正整数 $n$，所有除以 $n$ 余数相同的整数构成一个 剩余类。余数为 $r$ 的剩余类记作：$[r]_n$ 或 $\bar{r}$

为什么我们还要折腾这些余数呢？我想一个合理的解释是计算机的存储是有限的。如果不取模，数字不断相乘会变得巨大无比，撑爆内存。通过取模，无论怎么算，结果永远在 $0$ 到 $n-1$ 之间。

此外，密码学需要把原来的信息（明文）弄得面目全非（密文）。模运算是一种很好的“搅拌机”。它很难逆向推导（比如我知道余数是 3，除数是 5，但我不知道原来的数是 3 还是 13 还是 10008）。这种 不可逆性（在某些条件下）是公钥密码学（如 RSA）的基础。

我们前面推导减法规则：$(a - b) \mod n = 0$，那如果是加法和乘法呢？我们尝试进行推理：

同理，可以得到乘法：$(a \times b) \mod n = [(a \mod n) \times (b \mod n)] \mod n$ 。

群、环、域#

我们重新回顾数学中的基础概念：

• 集合 (Set)：一堆数字（或其他元素）的合集。例如：整数集合 $\mathbb{Z}$。
• 运算 (Operation)：一种处理元素的方法。例如：加法 ($+$) 或乘法 ($\times$)。

我们现在要重新定义一个集合中的运算及其遵守的规则。以 整数集合和加法运算 为例，定义如下的规则：

1. 封闭性 (Closure)：整数加整数还是整数，即对于任意的 $a,b \in \mathbb{Z}$，有 $a+b \in \mathbb{Z}$ 。
2. 结合律 (Associativity)：对于任意的 $a,b,c \in \mathbb{Z}$，有 $(a+b)+c = a+(b+c)$ 。
3. 逆元 (Inverse)：对于任意的 $a \in \mathbb{Z}$，存在一个 加法逆元 $-a$，使得 $a + (-a) = 0$ , $0$ 是 加法单位元。

当满足了如上的加法运算规则后，我们就称其为 加法群 (Additive Group)。我们的整数集合 $\mathbb{Z}$ 正好满足这些要求。我们把满足一个运算的应有规则的集合 $R$ 称为 群 (Group)。

当然，回顾小学数学，我们知道加法有三大规则：交换律、结合率和分配率。如果一个整数加法群 $\mathbb{Z}_m$ 满足交换律，即对于任意的 $a,b \in \mathbb{Z}$，有 $a+b = b+a$ ，则称这个群为 阿贝尔群 (Abelian Group) 或交换群。

同理，我们在整数集合上定义乘法及其规则：

1. 封闭性 (Closure)：整数乘整数还是整数，即对于任意的 $a,b \in \mathbb{Z}$，有 $ab \in \mathbb{Z}$ 。
2. 结合律 (Associativity)：对于任意的 $a,b,c \in \mathbb{Z}$，有 $(ab)c = a(bc)$ 。
3. 交换律 (Commutative)，即对于任意的 $a,b \in \mathbb{Z}$，有 $ab = ba$ 。

整数集合在满足乘法的这些要求上，还能满足加法与乘法之间的分配率，即对于任意的 $a,b,c \in \mathbb{Z}$，有 $a(b+c) = ab + ac$。

此时你发现，怎么乘法的规则里面没有逆元这一条。因为整数之间的除法不一定能得到整数，可能会出现分数。

整数集合 $\mathbb{Z}$ 同时满足了加法的 4 条规则和乘法的 2 条规则, 以及加法和乘法的分配率。我们称一个集合 $R$ 同时满足 两个运算 的规则时，它是一个 环 (Rings)。所以，整数集合 $\mathbb{Z}$ 是一个整数环。

在 $\mathbb{Z}_m$ 上，你可以随意加减乘，得到的还是整数。但是你不能随意除（比如 $5 \div 2$ 不是整数）。

注意，此时整数集合在乘法上，并不是群，因为其不满足一定有逆元在整数域中。

当一个集合，在 加法 上是一个群，去掉 $0$ 元素后，它在 乘法 上也是一个群（意味着每个非零元素都有倒数），则称为 域 (Field)。

此时乘法也满足了群的特征，即其逆元也在集合中。例如我们最常见的 实数域 $\mathbb{R}$，或 有理数域 $\mathbb{Q}$。

我们在电脑里做加密，不能用无限的实数，必须用 有限 的整数。但是普通的整数集合 $\mathbb{Z}$ 只是环，不能除。我们需要构造一个 既是有限的，又能做除法 的系统。这就是 有限域 (Finitefield) 或伽罗瓦域(Galoisfield)，通常记作 $GF(p)$ 或 $\mathbb{F}_p$ 。

例如我们之前学到的 模 7 的剩余类 $\mathbb{Z}_7$, 它的集合是 $\{0,1,2,3,4,5,6\}$。在这个集合里，每个非零数字都有逆元 $a^{-1}$，使得 $aa^{-1} = 1$。

例如：$3 \times 5 = 15$，$15 \mod 7 = 1$, 所以 $5$ 是 $3$ 的逆元。同理我们一个个尝试，可以得到 $\mathbb{Z}_7$ 中每一个非零数字的逆元，且在 $\mathbb{Z}_7$ 中。所以它是一个 域。

但是，并非所有的模剩余类都是域，例如 模 12 的剩余类 $\mathbb{Z}_{12}$ 。尝试找 2 的乘法逆元，会发现在 $\mathbb{Z}_{12}$ 中无法找到。

一般而言，模 $m$ 的剩余类的集合 $\mathbb{Z}_m = \{0,1,\dots,m-1\}$ 中，当 $m$ 为质数 (素数) 时，$\mathbb{Z}_m$ 是伽罗瓦域。具体证明比较繁杂，在计算机课程中就不涉及了。

总的来说，我将群、环、域总结为一张表以供参考：

移位密码#

因为英文有 26 个字母，我们将每一个字母都看作 $\mathbb{Z}_{26}$ 中的元素，例如： A -> 0, B -> 1, ..., Z ->25。$\mathbb{Z}_{26}$ 是一个环，里面的元素满足加法和乘法的结果均属于这个环，且加法存在逆元。加法、减法、乘法都要 mod 26 以保证其在 $\mathbb{Z}_{26}$ 中。

移位密码 (Shift Cipher) 运用了环的特性，在 $\mathbb{Z}_{26}$ 的基础上，将每个字母整体平移 $K$ 位后得到密文，具体来说定义为：

Shift Cipher

设明文空间 $P$、密文空间 $C$ 和密钥空间 $K$ 均为 $\mathbb{Z}_{26}$ 。对于 $K \in \{0,25\}$，任意 $x,y \in \mathbb{Z}_{26}$，定义：

• $e_K(x) = (x+K) \mod 26$
• $d_K(y) = (y-K) \mod 26$

当 $K=3$ 时，这个密码就是凯撒密码 (Caesar Cipher)。接下来通过一个例子去演示这个过程：

设移位密码的密钥为 $K=11$，明文为：wewillmeetatmidnight，使用移位密码去加密它。

1. 首先我们将明文按照字母表转为数字序列：22, 4, 22, 8…
2. 然后将每个数都与 11 相加，再对其和取模 26 运算：例如 $22 + 11 = 33 \equiv 7 \pmod{26}$，对应字母 H。
3. 经过全部转换，我们得到密文：HPHTWWXPPELEXTOYTRSE

如果需要解密时，每个密文字母转成数字后减 11 即可。

移位密码的安全性非常有限，因为其密钥空间仅有 26 个可能的取值，攻击者 Oscar 可以穷举所有 $K$ 值，直到出现有意义的英文。

代换密码#

另一个比较有名的古典密码体制是 代换密码（Substitution Cipher）。代换密码不再使用固定的移位，而是用一个完全随机的密码本替换字母表。

Substitution Cipher

在替换密码中，明文空间和密文空间 $P = C = \mathbb{Z}_{26}$。密钥空间 $K$ 是由 26 个元素的所有可能排列（Permutations）构成的集合 $\pi$。对于任意 $x,y \in \mathbb{Z}_{26}$，定义：

• $e_{\pi}(x) = \pi(x)$
• $d_{\pi}(y) = \pi^{-1}(y)$

$\pi^{-1}$ 表示置换 $\pi$ 的逆置换。

例如有如下置换规则 $\pi$：

通过这种随机映射，明文中的每一个字母都被替换成密钥表中对应的另一个字母。解密函数是其相应的逆置换。

代换密码的密钥空间极大（$26!$），暴力破解难以奏效。那代换密码就安全了吗，显然不是。它依然无法掩盖自然语言的统计特性。攻击者可以通过频率分析法，统计密文中各个字母出现的概率并与标准英文频率对比，从而快速推断出替换规则并破解密文。

仿射密码#

从前面我们看到，移位密码是代换密码的一种特殊情形，其只包含了 26 种置换情况。另一个代换密码的特殊情形是 仿射密码（Affine Cipher）。它的置换规则由一个线性方程决定。

Affine Cipher

设 $P = C = \mathbb{Z}_{26}$，若有密钥 $K=\{(a,b) \in \mathbb{Z}_{26} \times \mathbb{Z}_{26}: \gcd(a,26)=1\}$，其中 $x$ 是明文字母对应的数字，则定义：

• 加密函数为：$e(x)=(ax+b) \mod 26$
• 解密函数为：$d(y)=a^{-1}(y - b) \mod 26$

如果密码能被解密，加密函数必须一一对应，否则两个明文字母可能加密成同一个密文字母，解密时就不知道还原成哪一个。即 $ax+b$ 必须是一个单射函数（指向唯一值），它与 $y \in \mathbb{Z}_{26}$ 同余：$ax+b \equiv y \pmod {26}$。分析这个仿射函数的解密，只要 $y \in \mathbb{Z}_{26}$，则 $y-b \in \mathbb{Z}_{26}$。所以是否能解密主要专注于 $a$ 是否有乘法逆元 $a^{-1}$。对于 $a \in \mathbb{Z}_m$，若存在 $a^{-1} \in \mathbb{Z}_m$，使得 $aa^{-1} \equiv a^{-1}a \equiv 1 \pmod{m}$，则 $a^{-1}$ 称为 $a$ 在 $\mathbb{Z}_m$ 上的乘法逆元，记作：$a^{-1} \mod m$.

$a$ 有逆元的 唯一条件 是：$a$ 必须与 $m=26$ 互素，即最大公约数 $\gcd(a,26)=1$。例如 $a=2$，$\gcd(2, 26) = 2$。此时加密字母 a (对应数字为 0) 和 n (对应数字为 13) 时：

• $e(0) = b \pmod {26}$
• $e(13) = 2 \times 13 + b = 26 + b \equiv b \pmod {26}$

两个不同字母映射到了同一个结果，这导致了加密不可逆。所以仿射密码有解的充分必要条件是：$\gcd (a, 26)=1$。那么 $a$ 该如何取值使得其与 $m=26$ 互素呢？下面是严谨一些的数学推导：

欧拉函数 (Euler’s totient function) $\varphi (m)$ 表示 $a \in \mathbb Z_m=\{0,1,\dots,m-1\}$ 里，有多少个数和 $m$ 互素，即 $\gcd(a,m)=1$. 例如在 $\mathbb Z_{10}$ 中，$\varphi (10) = 4$，分别是：$1,3,7,9$。接下来我们分类讨论 $m$ 的不同情况：

1. 如果 $m$ 本身就是一个素数，那么除了它自己外，$\{1,2,\dots,m-1\}$ 全部和它互素。$\varphi(m) = m-1$。例如 $p=7$，因为 7 是素数，除了它自己，前面的 1, 2, 3, 4, 5, 6 全部和它互素， $\varphi(7) = 7 - 1 = 6$.
2. 如果 $m$ 是一个素数的次方，例如 $m = p^e$，你会发现 除了那些包含因子 $p$ 的数外 的数均与 $m$ 互素。例如：$p=3,\ e=3,\ m=3^3=27$。只有那些包含因子 3 的数和 27 不互素，也就是 3 的倍数：3, 6, 9, 12, 15, 18, 21, 24, 27。因为每 $p$ 个数里面就有一个 $p$ 的倍数，所以非互素的数量是：$m \div p = p^{e-1}$. 例子中则是 $27 \div 3 = 9$ 个。那么与 $m$ 互素的数就可以计算为：$\varphi(m) = p^e - p^{e-1}$.
3. 现实情况中，$m$ 往往很复杂。我们学过一个重要的数学定理：任何一个整数都可以拆分成几个素数的乘积，这称为 质因数分解 (Prime Factorization)。这里简单复习一下，我们一般使用短除法来解决。例如 $m=67500$ , 遵循如下的短除法算法对其进行质因数分解：

   1
   def prime_factors(n):
   2
       factors = {}
   3
       i = 2
   4
       while i * i <= n:
   5
           while n % i == 0:
   6
               factors[i] = factors.get(i, 0) + 1
   7
               n = n // i
   8
           i += 1
   9
       if n > 1:
   10
           factors[n] = 1
   11
       return factors
   

   先从 2 开始试，依次尝试每一个素数因子，直到最后的商为 1。最后我们可以得到这样的素数组合：$m = 67500 = 2^2 \times 3^3 \times 5^4$. 所以我们可以将 $m$ 表示为， $$m=\prod_{i=1}^n p_i^{e_i}$$ 接下来我们计算与 $m$ 互素的数的个数，即 $\varphi (m)$。根据上述第二点的结论，与 $m$ 不互素的只有组成 $m$ 的各个素数因子的倍数。因为这些素数是完全独立的，只需要把每个独立的 $\varphi$ 值乘起来就组成了 $m$ 的 $\varphi$ 值。 $$\varphi (m)=\prod_{i=1}^n \left (p_i^{e_i}-p_i^{e_i-1}\right)$$ 我们举一个例子来理解一般情况下的欧拉公式：例如 $m = 100 = 2^2 \times 5^2$，与 $100$ 互素的数有 $\varphi (100) = (2^2-2^1) \times (5^2-5^1) = 40$ 个。

回到仿射密码。对于英文字母表 $m=26$，其质因数分解为 $26 = 2^1 \times 13^1$，与它互素的数，即使得仿射密码有解的 $a$ 的值有 $\varphi(26) = (2^1-2^0) \times (13^1-13^0) = 1 \times 12 = 12$ 个。

拓展到任意的 $m$，对于仿射函数 $ax+b$，$b$ 有 $m$ 种选择（因为其只是平移量，符合 $\mathbb{Z}_m$ 的加法性质），$a$ 有 $\varphi(m)$ 种选择。则 仿射密码的密钥空间 $K = (a,b)$ 的大小为：$m \times \varphi(m)$。

在解密仿射密码时，需要知道 $a$ 的乘法逆元 $a^{-1}$，乘法逆元可以通过 拓展欧几里得算法 (Extended Euclidean Algorithm, EEA) 求得，在后续例子之后补充。在 $m=26$ 下，乘法逆元如下：

下面是一个仿射密码解密的例子：

假设仿射密码的密钥为 $K=(7,3)$，已知 $7^{-1}\equiv 15 \pmod{26}$。加密函数为：$e_K(x) = 7x+3$，解密密文：AXG。

我们先将其转换为数字：$y = \{0,23,6\}$，使用解密函数：$d_K(y) = 7^{-1} (y-3) \mod 26$, 代入密文可以得到：

• $15(0-3)=-45 \equiv 7$，还原为 h；
• $15(23-3)=300\equiv14$，还原为 o；
• $15(6-3)=45\equiv19$，还原为 t。

通过上述步骤，密文 AXG 成功解密为明文 hot。

补充：计算乘法逆元的方法 扩展欧几里得算法 (Extended Euclidean Algorithm, EEA)。在模运算里，求 7 在模 26 下的乘法逆元，就是要找一个数 $x$，使得：$7x \equiv 1 \pmod{26}$，也就是对于整数 $y,\ k,\ y=-k$，存在 $7x = 1 + 26k \implies 7x - 26k = 1 \implies 7x + 26y = 1$。

先使用欧几里得算法 (辗转相除法) 计算 $\gcd(a, b)$：反复用大数除以小数，取余数，直到余数为 0。以 $\gcd (7, 26)$ 为例：

接下来，我们可以通过逆推上述步骤，找到整数 $x$ 和 $y$，使得 $ax + by = \gcd(a, b)$：

现在我们要把 $1$ 写成 $7$ 和 $26$ 的组合。

1. 从第 3 步开始：$5 = 2\times 2 + 1$，移项得到：$1 = 5 - 2\times 2$，接着将第 2 步中得到的余数表达式代入此式：$1 = 5 - 2(7-5)$，展开得到：$1 = 5 - 2\times 7 + 2\times 5$，观察到之前的步骤中存在余数 $5$, 我们整理为带有上一步骤余数的形式：$1 = 3\times 5 - 2\times 7$。
2. 接着继续将第 1 步的余数表达式 $5 = 26 - 3\times 7$ 代入：$1 = 3(26-3\times 7)-2\times 7$，展开得到：$1 = 3\times 26 - 9\times 7 - 2\times 7$，合并保留 $7$ 和 $26$ 的组合：$1 = -11\times 7 + 3\times 26$。
3. 现在对等式两边模 $m=26$：因为 $-11\times 7 + 3\times 26 = 1$, $3\times 26 \equiv 0 \pmod{26}$，所以 $-11\times 7 \equiv 1 \pmod{26}$。这说明 $-11$ 是 $7$ 在 $26$ 下的乘法逆元，写作 $7^{-1}\equiv -11 \pmod{26}$。但是乘法逆元需要 $\in \mathbb{Z}_{26}$, 所以 $7^{-1}\equiv -11\equiv 15\pmod{26}$。

维吉尼亚密码#

在前面介绍的移位密码和代换密码中，一旦密钥被选定，则每个字母对应的数字都被加密变换成对应的唯一数字，这种密码体制我们一般称为单表代换密码。维吉尼亚密码 (Vigenère Cipher) 是一种多表替换密码 (Polyalphabetic cryptosystem)，同一个明文字母在不同位置会被加密成不同的密文字母，从而抵抗简单的词频分析。

维吉尼亚密码 主要使用了一个维度为 $m$ 的密钥向量，这个密钥是一组基于位置的密码表，让每个字母的移位不再和字母本身锁定，而是会随着位置的改变而改变。它的定义如下：

Vigenère Cipher

对于正整数 $m$，定义 $P=C=K=(\mathbb{Z}_{26})^m$。对于任意以 $m$ 维度向量表示的密钥 $K = (k_1,k_2,\dots,k_m)$，定义：

• 加密函数：$e_K(x_1,x_2,\dots,x_m) = (x_1+k_1, x_2+k_2, \dots, x_m+k_m) \pmod {26}$
• 解密函数：$d_K(y_1,y_2,\dots,y_m) = (y_1-k_1, y_2-k_2, \dots, y_m-k_m) \pmod {26}$

实际上维吉尼亚密码算是移位密码的拓展，接下来通过一个简单的例子来展示维吉尼亚密码的过程。

设 $m=6$，密钥字为 CIPHER，其对应于如下的数字串 $K=(2,8,15,7,4,17)$。加密：thiscryptosystemisnotsecure

首先我们将明文串转化为对应的数字。$K$ 是一个维度为 $m=6$ 的向量，它表示这套密码有 6 个不同的移动规则。我们将明文按 $m=6$ 个字符进行分组得到：

• thiscr
• yptosy
• stemis
• notsec
• ure：这一组不满 6 个就保留即可。

对于每一组中，第 $i$ 个字母的偏移量为 $k_i$。例如 thiscr 这一组中，第 $1$ 个字母 t 的偏移量为 $k_1=2$，第 $2$ 个字母 h 的偏移量为 $k_2=8$，依此类推。然后在下一组中重复。于是对于 thiscr 这一组，我们应用密钥 $K$ 可以得到如下的表格：

解密同理，只需要将密钥的移位量减去即可，下面的表格记录了如何将 VPXZGI 解密回 thiscr 的过程：

维吉尼亚密码的密钥空间大小为 $26^m$。维吉尼亚密码比移位密码更难手工破解，但如果用于加解密的密钥 $K$ 重复使用，就会产生周期性结构。只要猜出密钥长度 $k$，维吉尼亚密码就退化为 $k$ 个独立的移位密码。

希尔密码#

在维吉尼亚密码中，我们使用多表替换，同一个字母可能会变成不同的字母。但它的缺点也很明显，它是逐个字母加密的，如果破解者能猜出密钥的长度（比如长度是 6），他们就可以把密文分成 6 组，每组单独使用词频分析法来破解。

为了解决这个问题，希尔密码 (Hill Cipher) 采用了分组加密的思想。它利用线性代数中的矩阵乘法，将 $m$ 个明文字母组成的向量同时进行变换。由于加密过程涉及到多个字母的线性组合，这使得密文不仅取决于当前的明文字母，还取决于与其同组的其他字母，从而更有效地抵御频率分析。

简单来说：希尔密码把几个字母打包成一个向量，然后用矩阵把它们混合起来。

Hill Cipher

设 $m \ge 2$ 是正整数，定义 $P=C=(\mathbb{Z}_{26})^m$，$K = \{m \times m\ \text{invertible matrices over } \mathbb{Z}_{26}\}$，$x=(x_1, x_2,\dots, x_m)$，$(y_1, y_2, \dots, y_m)$ 为密文向量。对于任意的密钥矩阵 $K$ 则定义：

• $e_K(x) = xK \pmod {26}$
• $d_K(y) = yK^{-1} \pmod {26}$

接下来同样通过一个例子去解析这个过程。

设一次性处理 $m=2$ 个字母，密钥 $K = \begin{pmatrix} 11 & 8 \\ 3 & 7 \end{pmatrix}$, $K^{-1} = \begin{pmatrix} 7 & 18 \\ 23 & 11 \end{pmatrix}$，需要加密的明文为 july。使用希尔密码进行加密。

根据 $m$ 的值将明文分为两组，并将其转换为一组向量：

• ju: $(9, 20)$
• ly: $(11, 24)$

接下来我们使用密钥矩阵对明文进行加密，在 ju 这一组中，让明文向量乘密钥矩阵（矩阵乘法，第一行乘第一列，第二行乘第二列）：

然后将其放回 $\mathbb{Z}_{26}$ 中，即 $\pmod{26}$。得到 $(3,4)$，转换回字母得到 DE。

同理可以对第二组 ly 进行加密：

计算 $193 \pmod{26} = 11 \rightarrow \text{L}$, $256 \pmod{26} = 22 \rightarrow \text{W}$。最终，明文 july 被成功加密成了密文 DELW。

既然加密是乘以矩阵 $K$，那解密自然就是乘以 $K$ 的逆矩阵 ($K^{-1}$)。刚才例子中，以及给出了 $K^{-1}$。通过将密文转换的向量与逆矩阵相乘再取模就可以恢复明文了。例如解密 DE：

所以密文向量是：$(3,4)$，相乘：$(3,4) \begin{pmatrix} 7 & 18\\ 23 & 11 \end{pmatrix} = (3\cdot 7+4\cdot 23,\ 3\cdot 18+4\cdot 11) =(113,\ 98)$。再模上 26 可以得到 $(113,98)\equiv (9,20)\pmod{26}$，转回字母可以解出 $\text{DE}\rightarrow \text{ju}$。

我们学习线性代数知道，不是所有的矩阵都有逆。$K$ 可逆是完成解密的必要条件，即 $\det (K) \neq 0$。$\det (K)$ 是密钥矩阵 $K$ 的行列式，$\det(A) = a_{11}C_{11} + a_{12}C_{12} + a_{13}C_{13}$，其中 $C_{ij}$ 是代数余子式（删掉第 $i$ 行第 $j$ 列后剩余矩阵的行列式，它的符号由行列决定，为 $(-1)^{i+j}$）。下面是一个简单的例子：

$A = \begin{pmatrix} 2 & 1 & 3 \\ 0 & 4 & 5 \\ 1 & 0 & 6 \end{pmatrix}$ 如果我们按行展开：

求逆还需要伴随矩阵 $\text{adj}(A)$，它是所有代数余子式组成的矩阵再转置。例如对上述的 $A$ 矩阵，第一步：计算每个位置的代数余子式 $C_{ij}$ 得到：

第三步：转置 → 得到伴随矩阵

有了行列式 $\det (A)$ 和伴随矩阵 $\text{adj}(A)$ 后，我们可以通过如下公式求逆：

在希尔密码中，矩阵的逆通常是在模 $26$ 的情况下求出来的。有一个定理：当行列式与 $26$ 不互素时，矩阵在模 $26$ 下没有逆矩阵。例如刚才的例子中，$\det (A) = 41$, $\gcd(41,26) = 1$, 所以这个例子在 $\pmod {26}$ 下存在逆矩阵。

所以 $\det (A)$ 在 $\pmod {26}$ 下，$41 \equiv 15 \pmod{26}$，而 $\frac{1}{\det(A)} = \det^{-1}(A)$. 根据我们之前提到的扩展欧几里得法，可以计算出 $15^{-1} \equiv 7 \pmod{26}$。所以 $A$ 的逆是：

置换密码#

在我们之前学习的密码中，它们都有一个共同点：核心逻辑是通过特定的映射规则将明文字符替换为另一个字符，从而改变字符的取值。如果你截获了一段密文，你可以笃定里面的字母都不是它原本的意思。

而 置换密码（Permutation Cipher） 反其道而行。它又称换位密码，其核心思想是 保持明文字符集不变，通过 改变字符在序列中的位置 来达到加密目的。与代换密码不同，它不改变字符本身的取值，仅对其进行重新排列。

置换密码首先将密码进行分组（类似希尔密码的分组），每 $m$ 个字母切成一小块。在每一组中，规定一个固定的位置置换顺序。我们有如下置换密码的定义：

Permutation Cipher

设 $m$ 是一个正整数，定义 $P = C = (\mathbb{Z}_{26})^m$。密钥 $K = \pi$ 是由定义在集合集合 $\{1, 2, \dots, m\}$ 上的一组置换组成。

• 加密函数：$e_\pi(x_1, x_2, \dots, x_m) = (x_{\pi(1)}, x_{\pi(2)}, \dots, x_{\pi(m)})$
• 解密函数：$d_\pi(y_1, y_2, \dots, y_m) = (y_{\pi^{-1}(1)}, y_{\pi^{-1}(2)}, \dots, y_{\pi^{-1}(m)})$ 其中 $\pi^{-1}$ 是 $\pi$ 的逆置换。

置换密码实际上是希尔密码的一种特殊情况。如果希尔密码中的密钥矩阵 $K$ 是一个 置换矩阵（即矩阵的每一行和每一列有且只有一个 $1$，其余元素均为 $0$），那么该希尔密码就等价于置换密码。

接下来通过一个例子来演示加密和解密过程。

设 $m=6$，密钥置换 $\pi$ 定义为： $\begin{array}{c|cccccc} x & 1 & 2 & 3 & 4 & 5 & 6\\ \hline \pi(x) & 3 & 5 & 1 & 6 & 4 & 2 \end{array}$ 这意味着：第 1 位换成原先的第 3 位，第 2 位换成原先的第 5 位，以此类推。需要加密的明文为：shesellsseashellsbytheseashore。

将明文按 $m=6$ 分组，得到 shesel，lsseas，hellsb，ythese，ashore。

加密第一组 shesel：明文向量为 $(x_1, x_2, x_3, x_4, x_5, x_6) = (\text{s, h, e, s, e, l})$。接下来根据 $\pi$ 进行位置映射：

解密过程需要用到逆置换 $\pi^{-1}$。根据 $\pi$ 的定义，我们可以推导出 $\pi^{-1}$：

• 因为 $\pi(1)=3$，所以 $\pi^{-1}(3)=1$
• 因为 $\pi(2)=5$，所以 $\pi^{-1}(5)=2$
• 因为 $\pi(3)=1$，所以 $\pi^{-1}(1)=3$
• 因为 $\pi(4)=6$，所以 $\pi^{-1}(6)=4$
• 因为 $\pi(5)=4$，所以 $\pi^{-1}(4)=5$
• 因为 $\pi(6)=2$，所以 $\pi^{-1}(2)=6$

整理得到逆置换：

使用 $\pi^{-1}$ 对密文 EESLSH 进行解密即移动位置，即可还原回 shesel。

替换—置换网络#

替换—置换网络 (Substitution-Permutation Network, SPN) 可以想象为我们之前学习的替换密码和置换密码的组合网络。它的核心思想很简单：一次简单操作不够安全，那就把 替换 和 位置置换 反复做很多轮。

它由两个重要组件组成：

• S盒（S-box, Substitution，代换/混淆）：类似替换密码，通过替换改变数据的值。它的目的是打断明文和密文之间的直接联系，让关系混淆。
• P盒（P-box, Permutation，置换/扩散）： 通过位置置换，改变数据的位置。它的目的是让明文中一个比特的影响迅速扩散到整个密文中。

如果只有 S 盒和 P 盒，如果这些规则是公开的，那么任何人都能照着做加密和解密。所以在 SPN 中，每一轮执行 S 和 P 操作时，都需要加入一个 轮密钥 (Round Key)。与每轮都使用同样的密钥不同，轮密钥使用密钥编排算法生成一组密钥编排方案 $(K^1,K^2,\dots,K^{N_r+1})$。在每一轮中，将与上一轮 P 盒的结果进行 异或 (XOR) 计算 以混合加密数据。解密时，混合模块不需要重新设计。只要拿出同一把轮密钥再做一次 XOR，数据就还原了。

SPN 的定义如下：

Substitution-Permutation Network, SPN

设明文和密文都是长度为 $\ell m$ 的二进制向量 ($\{0,1\}^{\ell}$)，存在 S-box $\pi_S:\{0,1\}^{\ell}\rightarrow \{0,1\}^{\ell}$，和 P-box $\pi_P:\{1,\dots,\ell m\}\rightarrow \{1,\dots,\ell m\}$。密钥 $K \subseteq (\{0,1\}^{\ell})^{N_r+1}$ 由初始密钥 K 用密钥编排算法生成的所有可能的密钥编排方案的集合，对一个密钥编排方案 $(K^1,K^2,\dots,K^{N_r+1})$，使用如下的过程加密明文 $x$。

其中，$\ell$ 表示每个 S-box 处理多少 bit，$m$ 表示每轮有多少个 S-box，$\ell m$ 则表示整个明文分块的大小。

在每轮中，有如下符号：

• $w^{r-1}$: 表示第 $r-1$ 轮结束后的状态。初始化时为 $w^0$，初始值为明文 $x$ 的明文分块形式。
• $K^r$：表示第 $r$ 轮的轮密钥。
• $u^r=w^{r-1}\oplus K^r$：$u^r$ 是第 $r$ 轮 S-box 的输入，它由上一轮的状态和轮密钥异或计算得到。
• $v^r$：表示第 $r$ 轮 S-box 的输出。
• $w^r$：表示第 $r$ 轮经过 P-box 重新排列后输出的状态。$w^r=\pi_P(v^r)$

假设我们要循环 $N$ 次（称为 $N$ 轮，Round）：

1. 初始化：把明文加入算法 ($w_0 \leftarrow x$)。
2. 前 $N-1$ 轮循环：
   1. 密钥混合：把当前状态和这一轮的轮密钥进行 XOR ($u_r \leftarrow w_{r-1} \oplus K_r$)。
   2. 替换：把数据切成小块，分别送进 S-box 进行替换 ($v_r \leftarrow \pi_S(u_r)$)。
   3. 位置置换：把 S-box 的输出，按 P-box 的规则打乱位置 ($w_r \leftarrow \pi_P(v_r)$)。
3. 最后一轮 (第 $N$ 轮) 的特殊处理：
   1. 密钥混合：把倒数第二轮的状态和最后一轮的轮密钥进行 XOR ($u_N \leftarrow w_{N-1} \oplus K_N$)。
   2. 替换：把数据切成小块，分别送进 S-box 进行替换 ($v_N \leftarrow \pi_S(u_N)$)。
   3. 不进行替换，再次进行密钥混合：$y \leftarrow v_N \oplus K_{N+1}$。这是为了让加密和解密的电路是对称的，最后再加一次密钥，是为了防止破解者轻易剥离掉最后一轮的 S-box。这种首尾都加密钥的设计叫白化 (Whitening)。

算法的伪代码如图：

接下来通过一个例子来解析这个过程。

给出如下的 SPN 设置：设 $\ell=m=N_r=4$，S-box 的输入 $z$ 与其输出 $\pi_S(z)$ 都是使用十六进制表示。