带余除法#

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

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

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

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

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

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

例如：

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

例如 $11\equiv 6(\mathrm{mod}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\le r<n$，所以按照余数分类可以分成 $n$ 种类型，我们把每一种分类称为一个 剩余类 (Residue Classes)。它的正式定义如下：

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

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

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

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

同理，可以得到乘法：$(a\times b)\mathrm{mod}n=[(a\mathrm{mod}n)\times (b\mathrm{mod}n)]\mathrm{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÷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}$，使得 $a{a}^{-1}=1$。

例如：$3\times 5=15$，$15\mathrm{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)\mathrm{mod}26$
• $d_K(y)=(y-K)\mathrm{mod}26$

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

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

1. 首先我们将明文按照字母表转为数字序列：22, 4, 22, 8…
2. 然后将每个数都与 11 相加，再对其和取模 26 运算：例如 $22+11=33\equiv 7(\mathrm{mod}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)\mathrm{mod}26$
• 解密函数为：$d(y)=a^{-1}(y-b)\mathrm{mod}26$

如果密码能被解密，加密函数必须一一对应，否则两个明文字母可能加密成同一个密文字母，解密时就不知道还原成哪一个。即 $ax+b$ 必须是一个单射函数（指向唯一值），它与 $y\in {\mathbb{Z}}_{26}$ 同余：$ax+b\equiv y(\mathrm{mod}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$，使得 $a{a}^{-1}\equiv a^{-1}a\equiv 1(\mathrm{mod}m)$，则 $a^{-1}$ 称为 $a$ 在 ${\mathbb{Z}}_m$ 上的乘法逆元，记作：$a^{-1}\mathrm{mod}m$.

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

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

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

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

1. 如果 $m$ 本身就是一个素数，那么除了它自己外，$\{1,2,\dots ,m-1\}$ 全部和它互素。$\phi (m)=m-1$。例如 $p=7$，因为 7 是素数，除了它自己，前面的 1, 2, 3, 4, 5, 6 全部和它互素， $\phi (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÷p=p^{e-1}$. 例子中则是 $27÷3=9$ 个。那么与 $m$ 互素的数就可以计算为：$\phi (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$ 互素的数的个数，即 $\phi (m)$。根据上述第二点的结论，与 $m$ 不互素的只有组成 $m$ 的各个素数因子的倍数。因为这些素数是完全独立的，只需要把每个独立的 $\phi$ 值乘起来就组成了 $m$ 的 $\phi$ 值。
   $$\phi (m)=\prod _{i=1}^n\left(p_i^{e_i}-p_i^{e_i-1}\right)$$
   我们举一个例子来理解一般情况下的欧拉公式：例如 $m=100=2^2\times 5^2$，与 $100$ 互素的数有 $\phi (100)=(2^2-2^1)\times (5^2-5^1)=40$ 个。

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

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

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

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

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

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

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

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

补充：计算乘法逆元的方法 扩展欧几里得算法 (Extended Euclidean Algorithm, EEA)。在模运算里，求 7 在模 26 下的乘法逆元，就是要找一个数 $x$，使得：$7x\equiv 1(\mathrm{mod}26)$，也就是对于整数 $y,k,y=-k$，存在 $7x=1+26k⟹7x-26k=1⟹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(\mathrm{mod}26)$，所以 $-11\times 7\equiv 1(\mathrm{mod}26)$。这说明 $-11$ 是 $7$ 在 $26$ 下的乘法逆元，写作 $7^{-1}\equiv -11(\mathrm{mod}26)$。但是乘法逆元需要 $\in {\mathbb{Z}}_{26}$, 所以 $7^{-1}\equiv -11\equiv 15(\mathrm{mod}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)(\mathrm{mod}26)$
• 解密函数：$d_K(y_1,y_2,\dots ,y_m)=(y_1-k_1,y_2-k_2,\dots ,y_m-k_m)(\mathrm{mod}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(\mathrm{mod}26)$
• $d_K(y)=y{K}^{-1}(\mathrm{mod}26)$

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

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

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

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

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

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

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

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

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

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

我们学习线性代数知道，不是所有的矩阵都有逆。$K$ 可逆是完成解密的必要条件，即 $\det (K)\ne 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=\left(\begin{array}{ccc}2& 1& 3\\ 0& 4& 5\\ 1& 0& 6\end{array}\right)$ 如果我们按行展开：

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

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

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

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

所以 $\det (A)$ 在 $(\mathrm{mod}26)$ 下，$41\equiv 15(\mathrm{mod}26)$，而 $\frac{1}{\det (A)}={\det }^{-1}(A)$. 根据我们之前提到的扩展欧几里得法，可以计算出 $15^{-1}\equiv 7(\mathrm{mod}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}{ccccccc}x& 1& 2& 3& 4& 5& 6\\ \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 }\to \{0,1{\}}^{\ell }$，和 P-box ${\pi }_P:\{1,\dots ,\ell m\}\to \{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)$ 都是使用十六进制表示。

S-box (十六进制对照): 类似一个字典。

P-box: 表示输出 $w$ 的第 $i$ 位，取输入 $v$ 的第 ${\pi }_P(i)$ 位。

密钥 $K=00111010100101001101011000111111$，通过一些编排算法后得到如下的轮密钥：

• $K^1=0011101010010100$
• $K^2=1010100101001101$
• $K^3=1001010011010110$
• $K^4=0100110101100011$
• $K^5=1101011000111111$

明文是 $x=0010011010110111$。接下来我们开始这个流程：

1. 初始化：$w^0=x=0010011010110111$
2. 第 $1$ 轮：
   1. 密钥混合：已知 $K^1=0011101010010100$，将其与 $w^0$ 逐位异或可以得到 $u^1=w^0\oplus K^1=0001110000100011=1C23$。
   2. 替换：把 $u^1$ 分成 $m$ 组，每组刚好四个 bit，将其转换会十六进制，对每组查表替换：$1\to 4,C\to 5,2\to D,3\to 1$，$v^1=45D1=0100010111010001$
   3. 位置置换：应用 P-box 规则，例如 $w^1$ 的第 $1$ 位是 $u^1$ 的第 $1$ 位，第 $2$ 位是 $u^1$ 的第 $5$ 位… $w^1=0010111000000111$
3. 接下来是第 2 ~ 3 轮，过程类似。
4. 在第 4 轮中，
   1. 密钥混合： $w^3=1110010001101110$, $K^4=0100110101100011$, $u^4=w^3\oplus K^4=1010100100001101$
   2. S-box 替换：$v^4=0110101011101001$
   3. 白化：再次进行一轮密钥混合，$y=v^4\oplus K^5$, $K^5=1101011000111111$，所以 $y=1011110011010110$，将其转换为十六进制是 $\boxed{BCD6}$

过程对照表如下：

DES#

在刚才学习的 SPN 网络中，有一个隐藏的问题：为了能让密文解密还原回明文，我们在 SPN 里使用的 S-box 必须是可逆的。然而在数学上，设计一个高安全度且可逆的 S-box 很困难。为了解决这个问题，密码学家提出了 Feistel 结构，并设计了 DES (Data Encryption Standard)。在这种结构中，每一轮的轮函数 (S-box) 并不要求是可逆的，因为其解密过程是通过 结构自身的对称性 来实现的。这使得 S 盒的设计更加灵活，可以使用更复杂的非线性映射来增强安全性，而无需担心解密时的可逆性限制。

Feistel 结构的基本原理是将输入的明文平分成左右两部分。具体而言：

1. 每一轮把当前状态分成两半：$u_i=L_i{R}_i$，$L_i$ 表示左半边，$R_i$ 表示右半边。对于第 $i$ 轮而言，它的输入是 $L_{i-1},R_{i-1}$。
2. 在第 $i$ 轮中：
   1. 将右半边的 $R_{i-1}$ 复制一份，直接等于下一轮的左半边：$L_i=R_{i-1}$
   2. 将右半边的 $R_{i-1}$ 和当前这一轮的轮密钥 $K_i$ 一起加入一个搅拌函数 $f$ 中得到一个加密数据：$f(R_{i-1},K_i)$。
   3. 最后将这个加密数据与原本的左半边 $L_{i-1}$ 进行 异或 ($\oplus$) 运算，得到的结果成为了下一轮的右半边：$R_i=L_{i-1}\oplus f(R_{i-1},K_i)$

下图展示了 Feistel 结构的基础架构：

这个结构同时也是 DES 加密过程中的一轮。DES 是一个 16 轮的 Feistel 网络，处理 64 比特 的数据块，用一个 56 比特 的密钥（另有 8 比特奇偶校验，实际存储 64 比特）。

DES 的大致流程是：

1. 先对明文 $x$ 做一个固定的 初始置换 IP (Initial Permutation)，记为 $\text{IP}(x)=L^0{R}^0$
2. 经过如上的 16 轮 Feistel 结构加密，得到 $L_{16}{R}_{16}$，将其 交换顺序 得到：$R_{16}{L}_{16}$。
3. 将交换顺序后的密文做一个固定的 逆置换 $I{P}^{-1}$，得到最后加密的密文 $y$，即 $y={\text{IP}}^{-1}(R_{16}{L}_{16})$。

其中初始置换及其逆置换没有密码学意义，仅是为了适应当时的硬件设计。

那 DES 的设计为什么能解决要求轮函数可逆的问题呢？它运用了异或运算的数学性质：一个数据被同一个值异或两次，就会回到原值 $A\oplus B\oplus B=A$。

假设你拿到了第 $i$ 轮结束后的密文结果 $(L_i,R_i)$：

• $L_i$ 就是上一轮的 $R_{i-1}$，所以可以得到 $R_{i-1}=L_i$
• 当你知道当前这一轮的密钥 $K_i$ 时，你同时也知道上一轮的右半边 $R_{i-1}$，你可以代入加密函数重构它的值 $f(R_{i-1},K_i)$。
• 接下来就可以通过异或的性质得到上一轮的左半边 $L_{i-1}$：$R_i=L_{i-1}\oplus f(R_{i-1},K_i)⟹L_{i-1}=R_i\oplus f(R_{i-1},K_i)$

在 DES 中，我们 根本不需要去逆向破解 $f$ 函数。只需要重新运行它一次，利用异或运算的还原能力，就能把数据完美还原。DES 的加密和解密算法是完全相同的，解密时只需将相同的输入跑一遍，并把子密钥的调度顺序反过来即可。

你可能会好奇它的加密函数 $f$ 内的样子，和 SPN 类似吗？下图展示了其加密函数的架构。

DES $f$ 函数的输入是：$f(R_{i-1},K_i):\{0,1{\}}^{32}\times \{0,1{\}}^{48}\to \{0,1{\}}^{32}$，它包含 32 位的右半边和 48 位的轮密钥，最后产生一个 32 位的结果。

1. 在其中，$f$ 函数使用扩展函数 $E$ 重新排列 32 位的右半边输入，并将其中的 16 位复制一遍，扩展成 48 位拉伸后的数据 $E(A)$；
2. 将其与轮密钥逐位异或：$E(A)\oplus K_i$，并将运算结果分成 8 个小组（$B_1$ 到 $B_8$），每组包含 6 个比特。
3. 将这 8 个组分别送入 8 个不同的 S 盒（$S_1$ 到 $S_8$），经过查表替换，每个 S 盒得到 4 个比特：$S_i:\{0,1{\}}^6\to \{0,1{\}}^4$.
4. 将其输出拼在一起得到 32 位的 $C$，然后送进置换函数 $P$ 中进行置换。置换后输出的 $P(C)$，就是 $f$ 函数的最终产物。

AES#

DES 为了避开设计可逆 S 盒的难题，使用了 Feistel 结构，代价是 每轮只能加密一半的数据。密码学家利用高级的数学工具（有限域/伽罗瓦域）制造出了 SPN 中的完美可逆 S 盒。AES (Advanced Encryption Standard) 抛弃了 Feistel 结构，全面回归了 SPN 结构。这使得 AES 每轮能把所有数据都加密一遍，效率提高。

AES 中，标准的数据块是 128 bits。它不再把这 128 bits 看作一条序列，而是把它切成 16 个 Byte（1 byte = 8 bits），然后转换成一个 4 x 4 的矩阵。这个矩阵在 AES 中被称为 状态矩阵 (State)，其表达式如下（Byte 按 列顺序 摆出）。

AES 会根据不同的密钥长度定义不同的轮数，一般来说 AES-128 是 10 轮，AES-192 是 12 轮，AES-256 是 14 轮。

在 $N-1$ 轮中，都包含如下四步：

1. 字节代换 (SubBytes)：将状态矩阵通过一个 16 x 16 的固定 S 盒，每个 byte 通过 S-box 替换。如图是一个 S 表的例子。
2. 行移位 (ShiftRows)：它会将每一行循环左移不同距离，相当于行置换。第 $i=0,1,2,3$ 行整体向左移动 $i$ 格。例如第 0 行移动 0 格（不变），第 1 行经过上一步后的输出为：$s_{1,0},s_{1,1},s_{1,2},s_{1,3}$，经过 ShiftRows 向左移动 1 格后变为：$s_{1,1},s_{1,2},s_{1,3},s_{1,0}$。
3. 列混淆 (MixColumns)：将每一列内部混合。它每次处理矩阵的一列。它把这 4 个字节当作多项式的系数，去乘以一个固定的矩阵。经过极度复杂的运算后，输出全新的 4 个字节。
4. 轮密钥加 (AddRoundKey)：最后，把这一轮的 128 位轮密钥也拆分为字节，排成一个 4x4 的矩阵，跟我们刚才搅拌好的状态矩阵进行简单的 异或 ($\oplus$) 运算。

而 第 $N$ 轮时则没有 MixColumns 这个操作。

AES 的轮密钥是通过 密钥拓展 (Key Expansion) 生成的，这一过程将初始密钥按 字 (Word) (1 Word = 4 Bytes) 扩展为一个更大的密钥序列，确保每一轮迭代都使用唯一的子密钥。例如 AES-128 需要将 128 位的初始密钥扩展为 11 组轮密钥，128 位的密钥对应 16 个 Byte，即 4 Words。Key Expansion 会生成 $11\times 4=44$ 个 Word，每轮 AddRoundKey 使用其中 4 个 Word。

Hash 函数和 MAC#

之前学习的加密算法都在尝试各种方法将一段信息加密为其他人看不懂的内容，在现实世界中，只有机密性是不够的。其他人就算看不懂密文，但他如果把密文拦截下来，随便篡改几个字节都会导致你解密失败。或者是黑客假冒你的身份发了一条指令，这时解密者不知道是否是你发的。

这时候我们就需要解决两个新问题：

1. 完整性 (Integrity)：数据在传输过程中，有没有被改动过。
2. 认证 (Authentication)：这数据是否是你本人发出来的。

一个很简单的方法就是：添加指纹 (fingerprint)。

哈希函数 (Hash Function) 是一种给信息添加指纹的方法。它的输入可以是任意长度的消息（一个文件、一句话、一部电影），输出则是固定长度的无规律字符串，也就是数字指纹，也被称为 消息摘要 (message digest)。比如常见的 MD5 或 SHA-256 就是 Hash 算法。这个指纹是公开可计算的，任何人拿到消息，都能通过同样的 Hash 函数算出一样的指纹。Hash 函数具有如下的特性：

• 不可逆：无法通过 Hash 值推导出原信息是什么。
• 雪崩效应 (Avalanche Effect)：信息发生任何的改动都会导致 Hash 值的变化。
• 抗碰稳固：很难找到两份内容不同但 Hash 值却一样的文件。

一个非常常见的 Hash 函数的应用就是 软件完整性验证：官网发布软件时，同时公布它的 Hash 值。个人下载软件后自己算一遍 Hash 值，对比官网的值，就知道文件有没有被篡改或损坏。

Hash 算法是没有密钥的，每个人都可以算。而在此基础上，消息认证码 (MAC) 则是加上了一个密钥。MAC 的计算不仅依赖于文件内容，还依赖于一个 只有通信双方才知道的秘密密钥 ($K$)。黑客就算篡改了文件，想重新算一个合法的 MAC，但他 没有密钥，所以算不出来。

Hash 函数解决了数据有没有变的问题，而 MAC 更进一步，不仅解决了数据有没有变，还提供了密钥认证，以确定计算者的身份，保证数据是你发的。

Merkle-Damgård 结构#

我们知道，哈希函数具有输入为任意长度的信息，输出为固定长度的信息摘要的特点。这样的特性是怎么设计的呢？在密码学里，数学家们非常擅长使用 压缩函数 (Compression Function，通常记为 $f$)，它只可以接受固定长度的输入，并输出固定长度的信息。密码学家设计了一种 Merkle-Damgård (MD) 结构，将压缩函数 $f$ 扩展成一个 可以处理任意长消息 的 Hash 函数。

MD 结构的核心思想是：用一个只能处理固定长度输入的压缩函数 $f$，反复处理长消息 $x\in X$ 的每一块；每一轮的输出变成下一轮的状态，最后一个状态就是 hash 值。这样的过程类似于递归求解。

首先我们设定一个碰撞稳固的压缩函数：$\text{compress}:\{0,1{\}}^{m+t}\to \{0,1{\}}^m$，它的输入是 $m+t$ bits，输出是 $m$ bits。这个 $m$ 也是多轮递归处理时的状态长度（因为上一轮的输出一定是 $m$），同时最后生成的 Hash 值也是长度为 $m$ 的消息摘要。$t$ 表示除了状态以外还能吃进去的额外空间相关参数。我们用 $n=|x|$ 记录整体输入信息的长度。

我们需要构造这样的 Hash 函数：$h:X\to \{0,1{\}}^m$，其中 $X$ 是足够长的有限比特字符串的集合。现在问题是：真实的输入 $x\in X$ 可能很长，而压缩函数只能处理固定长度 $m+t$ bits。所以 MD 结构设计了这样的链式结构：

1
初始状态 → 吃第 1 块 → 新状态
2
新状态   → 吃第 2 块 → 新状态
3
新状态   → 吃第 3 块 → 新状态
4
...
5
最终状态 = hash 消息摘要

在第 $i$ 轮可以写作：$g_i=\text{compress}(g_{i-1}\Vert y_i)$，$g_i$ 表示第 $i$ 轮后的状态；$y_i$ 表示第 $i$ 个信息块，$\Vert$ 表示拼接。我们可以把每一轮的状态 $g_i$ 理解为前 $i$ 个消息块共同留下来的 累计指纹，因为我们不是分块单独压缩，而是基于前面的分块再加上当前分块的链式压缩。所以每一轮压缩函数都必须带上上一次的状态 $g_{i-1}$，这也类似于递归中的值的传递。每一轮的压缩本质上是把前面的内容压缩成一个固定长度状态。

那我们已经知道，第 $i-1$ 轮压缩后的状态 $g_{i-1}$ 是 $m$ 位的。而下一轮的压缩函数只能输入 $m+t$ 位，直觉上第 $i$ 轮可以吃 t 位的信息块，但实际上还需要在上一轮状态和这一轮的信息块之间 加入 1 bit 的固定标记 $1$。这是为了防止 内部碰撞，即如果攻击者能找到某个状态与消息块的组合碰撞，他就可以在两个长度不同的消息间制造相同的哈希值。

所以 信息块的长度 应该设置为：$t-1$. 那么根据这个长度，我们可以将初始的输入 $x$ 分为长度为 $t-1$ 的若干块，所需要的块数是：$k=\lceil \frac{n}{t-1}\rceil$。此时得到：$x=x_1\Vert x_2\Vert \cdots \Vert x_k$

因此，可能会存在最后一个块 $x_k$ 的长度小于 $t-1$ bits. 例如每块长度是 $t-1=4$ bits，消息长度是 $n=14$ bits，那么：$k=\lceil 14/4\rceil =4$，最后一块 $|x_k|=2<t-1$. 遇到这种情况的时候，我们一般会给它后面补 $d$ 个 $0$, $d=(t-1)\times k-n$。