数论与群论密码学-06-密码学

狭义密码系统

古代的密码系统通常可概括为以下格式:

1
-明文->[加密器]-密文->[解密器]-明文->

形式化地来说,狭义的密码系统由 \((\mathcal{P}, \mathcal{C}, f)\) 组成。其中 \(\mathcal{P}\) 表示明文的集合,即可阅读的消息序列之集合,密文 \(\mathcal{C}\) 为经由函数 \(f\) 编码,不可读的消息序列之集合,记作 \(\mathcal{C}\); 函数 \(f: \mathcal{P} \to \mathcal{C}\) 被称作加密变化,其逆函数 \(f: \mathcal{C} \to \mathcal{P}\) 被称作解密变化,有

\[ \mathcal{P} \stackrel{f}{\to} \mathcal{C} \stackrel{f^{-1}}{\to} \mathcal{P} \]

由于发信方需要在通信之前先将 \(f^{-1}\) 告知收信方,因此需要事先便有一条安全的通信渠道,例如双方私下会面并约定分开后的通讯经由某一特定的方式加密。我们将要在之后看到的某个密码系统便是统帅凯撒与其军事将领在出征前约定好所使用的函数的。

如此的方案有两处不妥。首先它并不适用于通信双方并无法事先建立安全的通信渠道的情况,例如互联网上互不相识的双方并不能事先通过安全的渠道约定好所用的密码系统。另外一点是类似的:这样的密码系统的保密性完全依赖于函数 \(f^{-1}\) 的秘密性,因此这样的系统必定是一次性的,即函数 \(f\) 在一次使用后即不应该再次使用。

因此我们对密码系统做出如下推广:

广义密码系统

广义密码系统由 \((\mathcal{P}, \mathcal{C}, \mathcal{K}, \mathcal{E}, \mathcal{D})\) 组成,其中 \(\mathcal{P}, \mathcal{C}\) 如前述代表明文及密文集合; \(\mathcal{K}\) 为密钥空间,其于以下两集合中分别索引(指定)一个函数;而 \(\mathcal{E}=\{E_k\}_{k\in\mathcal{K}}, \mathcal{D}=\{D_k\}_{k\in\mathcal{K}}\) 分别为形同如下的函数之集合:

\[ E_k: \mathcal{P} \to \mathcal{C} \qquad D_k: \mathcal{C} \to \mathcal{P} \]

我们称 \(E_k\) 为加密函数, \(D_k\) 为解密函数,并要求其符合

\[ \forall k\in\mathcal{K}, \exists k'\in\mathcal{K}, \forall p\in\mathcal{P}: D_{k'}(E_k(p)) = p \]

即:对于每一个由 \(k\in\mathcal{K}\) 参数化的加密函数 \(E_k\) 都存在至少一个由某一 \(k'\in\mathcal{K}\) 参数化的解密函数 \(D_{k'}\),使得任何由 \(E_k\) 加密的密文皆可由 \(D_{k'}\) 解密。

这样一来,由于加密及解密函数集分别为两组由 \(\mathcal{K}\) 参数化的函数族,我们便可以安全地固定下一个密码系统,而仅通过变更使用的密钥来解决先前对古典密码系统提出的问题中的第二点。

而关于第一个问题,我们将随后提出一种在不安全的信道中以不为第三方所知的交换密钥的方式。

以下给出几个著名的密码系统,作为对先前所述的数论之应用。

几个密码系统的例子

凯撒密码

\[ \begin{aligned} \mathcal{P} &= \mathbb{Z}/26\mathbb{Z} \iff \text{A-Z}\\ \mathcal{C} &= \mathcal{P} \\ f(x) &= (x + 3) \bmod 26 \\ f^{-1}(x) &= (x - 3) \bmod 26 \end{aligned} \]

即明文密文皆为英文字母表组成的字符串,其由整数 0 至 25 分别编码 A-Z。加密将每一字母向后滑动三位,超出 Z 的部分绕回至 A。而解密则向前滑动三位。

另外我们注意到,若将此系统拓展至任意位的滑动,则有

\[ \begin{aligned} \mathcal{K} &= \mathbb{Z}/26\mathbb{Z} \\ E_k(x) &= (x + k) \bmod 26, k\in\mathcal{K} \\ D_k(x) &= (x - k) \bmod 26, k\in\mathcal{K} \\ \end{aligned} \]

且对应 \(E_k\) 的解密函数为 \(D_k\)

由于英文(乃至各语言)中各字符的出现频率在统计学上有可循规律,因此可以据此推断出可能的密钥 \(k\)。甚至,由于该系统中共有 26 种可能的密钥,而两段阅读起来同样对人类有意义的明文不大可能被加密到同样的密文,我们完全可以尝试遍所有可能的密钥。

维热纳尔密码系统 (维吉尼亚密码系统,维吉利亚密码系统,弗吉尼亚密码系统)

\[ \begin{aligned} \mathcal{P} = \mathcal{C} &= (\mathbb{Z}/26\mathbb{Z})^n\\ D_k(\vec{x}) &= \vec{x} + \vec{k} \end{aligned} \]

其中 \(k\in\mathcal{K}=\mathcal{P}\)

概念上我们可以这么理解:相对于凯撒密码中逐字母加密的方法,该系统将明文分成大小为 \(n\) 的若干块,并且对每一块使用同样的函数加密:即对于每一块中第 \(i\) 个字母,总是使用同样的凯撒密码加密,而对于不同位的字母,使用的密钥是不同的。

通过该系统,我们可以引出分块加密的概念:定义 \(n\)-块 密码系统为 \(\mathcal{P} = \mathcal{C} = \Sigma^n = \underbrace{\Sigma\times\cdots\times\Sigma}_{\text{$n$ 个}}\) 的系统,其中 \(\Sigma\) 为一个相当于之前的\(\mathcal{P}, \mathcal{C}\) 的有限的符号集,被称为密码系统的字母表,而 \(\mathcal{P}, \mathcal{C}\) 被称为词或者块集合。

该系统解决了凯撒密码中的两个问题,然而其依旧是不足够安全的:若加密块的长度 \(n\) 远小于明文的长度,我们依旧可以尝试不同的 \(n\),并将密文分成大小为 \(n\) 的若干块,随后提取每一块的第 \(i\) 个字母,并进行类似凯撒密码小节中所述的统计学分析。这一点在同一份密钥被反复使用的情况下同样适用。

希尔密码系统

\[ \begin{aligned} \Sigma &= \mathbb{Z}/m\mathbb{Z}, n \ge 1 \\ \mathcal{P} = \mathcal{C} &= \Sigma^n \qquad \text{(列向量)}\\ \mathcal{K} &= GL_n(\Sigma) \qquad \text{($n \times n$ 可逆矩阵,其元素来源于 $\Sigma$)}\\ E_A(\vec{x}) &= A\vec{x}\\ D_A(\vec{x}) &= A^{-1}\vec{x}\\ \end{aligned} \]

其中 \(A\in\mathcal{K}\)\(A\) 可逆,其逆 \(A^{-1}\in\mathcal{K}\).

因此有

\[ D_A(E_A(\vec{x})) = D_A(A\vec{x}) = A^{-1}A\vec{x} = \underbrace{A^{-1}A}_{I}\vec{x} = \vec{x} \]

其中所有运算都在 \(\mathbb{Z}/m\mathbb{Z}\) 中进行。

我们可以做如下拓展:

仿射密码系统

\[ \begin{aligned} \Sigma &= \mathbb{Z}/m\mathbb{Z}, n \ge 1 \\ \mathcal{P} = \mathcal{C} &= \Sigma^n\\ \mathcal{K} &= GL_n(\Sigma)\times\mathcal{P}\\ E_{A, \vec{b}}(\vec{x}) &= A\vec{x}+\vec{b}\\ D_{A, \vec{b}}(\vec{x}) &= A^{-1}\vec{x}-A^{-1}\vec{b}\\ \end{aligned} \]

注意有

\[ D_{A, \vec{b}}(E_{A, \vec{b}}(\vec{x})) = D_{A, \vec{b}}(A\vec{x}+\vec{b}) = A^{-1}(A\vec{x}+\vec{b})-A^{-1}\vec{b} = A^{-1}A\vec(x)+A^{-1}\vec{b}-A^{-1}\vec{b} = \vec{x} \]

因此,我们需要知道当何时矩阵 \(A\in M_n(\mathbb{Z}/m\mathbb{Z})\) 可逆。

\(R\) 为交换环, \(A\in M_n(R)\) 为一 \(n \times n\) 矩阵,则以下三个命题等价:

  1. \(A\) 可逆,即 \(\exists B \in M_n(R), AB = BA = I\).
  2. \(det(A) \in R^\times\),即 \(det(A)\)\(R\) 中有逆。
  3. 关于 \(A\) 的线性映射 \(L_A: R^n \to R^n, L(\vec{x}) = A\vec{x}\) 定义了一个双射(即可逆)。

\(i \implies ii\)\(AB = BA = I\),那么 \(det(A)det(B) = det(AB) = I\),于是 \(det(A) \in R^\times\).

\(ii \implies i\) 可使用 \(A\) 的余子式证得。

\(i \iff iii\) 因为有 \(L_{AB} = L_A \circ L_B, L_I = I_{R^n}\),因此 \(L_{A^{-1}}\)\(L_A\) 的逆。


应该注意到的是,这几个系统远非可被称作是安全的。首先由于该密钥空间很小,攻击者完全可以尝试所有可能的密钥。另外,其所使用的加密函数通常都使得密文有统计规律可寻。我们将在随后的文章中对通过这样的统计规律进行攻击做出简要的介绍。

另外需要注意到的是,前述的密码系统都是对称的。即加密解密所使用的函数皆使用相同的密钥,或者两密钥之间存在简单的变换。实际上,我们可以将如此系统中的密钥理解为某种共享的秘密,于是我们又回到了面临通信双方需要事先准备好一条私密的通信渠道的问题。

我们今后将给出一共两种本质上相同的方案:其一为不对称的公钥加密系统,该种系统使得通信双方不需事先约定好本次通信所共用的密钥;其二为通信双方通过某种方法在不安全的信道创建不可为第三方所知的密钥,而随后将此密钥用在类似于前述的对称加密系统中。