密码学体制和古典密码学

密码学体制

一个密码学体制是满足下列条件的五元组:

  1. P 表示所有明文的集合。
  2. C 表示所有密文的集合。
  3. K 表示密钥空间,是由所有密钥组成的集合。
  4. 对于任意一个 $k \in K$,都存在一个对应的加密函数 $e_K(x) \in \epsilon$ 和对应的解密规则 $d_K \in D$ ,对于任意的明文 $ x \in P $,均有 $ d_K(e_k(x)) = x $。

其中最关键的是性质 4,其保证任意明文被加密后都可以被解密到原文。需要指出的,要使得被加密后的明文可以被正常解密,一个必须满足的条件就是 $ e_K(x) $ 必须是一个单射函数。

位移密码

位移密码是很简单的一种密码体制,简单的说就是将明文按照一定的顺序向前或向后移动一定位置后得到明文。一个很经典的例子就是凯撒密码,凯撒密码就是将字母按照字母表顺序向后移动三位。例如对于明文 hello 我们可以对每个字母按照字母表顺序向后移动三位,得到密文 KHOOR。(为了方便表示,我们用小写字母表示原文,用大写字母表示密文,下同。)

简单给一个 Python 用凯撒密码加密 hello 的源代码:

for i in 'hello':
    print(chr(ord(i) + 3).upper(), end='')

但是凯撒密码并不是位移密码,而是位移密码的一种特殊形式。下面给出位移密码的密码学体制:

位移密码体制:$P = C = K = Z_{26}$,对于任意的明文 $x \in P$,有如下加密函数:

$$ y = e_K(x) = (x + k) mod 26 $$

我们很容易得到相应的解密函数:

$$ x = d_K(y) = (y – k) mod 26 $$

所以我们可以知道,位移密码的密码空间大小是 26,所以这种密码体制很不安全,在得到明文之后可以通过暴力破解的方法,用所有可能的密钥解密密文,最终可以得到有意义的明文。平均来说只需要尝试 13 次就可以得到明文。

代换密码

代换密码首先要有一个加密函数 $\pi(x)$,对于这个加密函数,给出相应的解密函数 $\pi^{-1}(x)$,表示其逆置换。这里随便给出一个例子:

a b c d e f g h i j k l m
X N Y A H P O G Z Q W B T
n o p q r s t u v w x y z
S F L R C V M U E K J D I

这里的逆置换就是把表格上下两行颠倒。

对于给定的明文,我们只需要按照表格 $\pi(x)$ 中的方式进行代换就可以得到明文。比如明文 hello 按照上表中进行替换就是 GHBBF,要对密文进行解密,只需要按照相反的方式进行就可以了。

下面给出代换密码的密码体制:

代换密码体制:$ P = C = Z_{26} $,而密钥空间 $K$ 是由 26 个字母构成的所有可能的置换,而加密函数和解密函数就是其中一种置换及其逆置换。

要知道这种密码体制的密钥空间的大小,只需要知道所有可能的置换的个数,我们把 26 个字母按顺序排列作为表格的第一行(明文),那么所有可能的置换就是 26 个字母的全排列,一共有 $ 26! $ 种,这个数值超过了 $4.0 \times 10^{26}$,这使得暴力破解成了几乎不可能的事情。后面我们会用到别的密码分析方法很容易的攻破这种密码体制。

仿射密码

仿射密码的加密函数是一个仿射函数,定义如下:

$$ e_K(x) = (ax + b) mod 26$$

其中 $a,b \in Z_{26} $。

为了保证这个函数是一个单射函数,需要满足的条件是 $gcd(a, 26) = 1$,即 $a$ 和 $26$ 互质。下面给出证明:

假设上述条件满足,且存在 $x_1, x_2$ 使得:

$$ ax_1 \equiv ax_2 (mod 26) $$

则有

$$ a(x_1 – x_2) \equiv 0 (mod26) $$

由整除的基本属性,上式在 $ gcd(a, 26) = 1 $ 的条件下有:

$$ x_1 – x_2 \equiv 0 (mod26) $$

也成立。故有 $ x_1 = x_2 (mod26) $。

证毕。

为了对密文进行解密,首先我们要了解一个概念叫做乘法逆元,简单的说就是 $ a $ 及其乘法逆元 $a^{-1}$ 满足 $ a \cdot a^{-1} = 1 (mod 26)$,具体的还得自己去了解。我们得到 $a$ 的乘法逆元 $a^{-1} $ 之后就可以得到其解密函数:

$$ d_K(y) = a^{-1}(y – b)mod26 $$

至此我们可以给出仿射密码的密码体制:

仿射密码体制:$P = C = Z_{26}$,$K = (a,b) \in (Z_{26})^2 $,其中 $a$ 满足 $gcd(a,26) = 1 $。定义加密函数:

$$ e_K(x) = (ax + b) mod 26$$

解密函数:

$$ d_K(y) = a^{-1}(y – b)mod26 $$

简单举出一个例子,在 $a = 7,b = 3$ 的条件下,$a$ 的乘法逆元 $a^{-1} = 15$(因为$ 15 \times 7 = 105 = 1(mod26)$, 所以加密函数和解密函数就确定下来了,加密 hello 的结果为…懒得算了,留给读者(¯﹃¯)

维吉尼亚密码

前面我们提到的密码体制都是单表密码,维吉尼亚密码是一种多表密码体制,首先我们选定表的长度 $m$,然后给出一系列的 $i \in [1, m] $,密钥 $ k = k_1k_2k_3…k_i $,对于任意的明文,我们要先按这个长度进行分组,然后分别对每组明文按照密钥和加密函数 $e_K(x) = x + k_i $ 进行加密。

举个例子,比如我选定 $m = 2, k_1 = 1, k_2 = 2$,然后对 hello 进行加密,首先对明文按照长度 $m = 2$ 进行分组,得到 he\ll\o,然后对每组分别按照上述方式进行加密,可以得到密文 JH\NO\Q,即加密后的密文为 JHNOQ

为了对密文进行解密,我们把上面的过程反过来进行,首先对密文进行分组,然后分别用解密函数 $d_K(y) = y – k_i$,就可以得到明文了。

维吉尼亚密码可以说是一种多表密码体制下的位移密码了。

希尔密码

希尔密码是对原文进行仿射变换的一种密码体制,我们要先选定一个整数 $m$,然后构造一个 $m \times m$ 的矩阵,例如我选定 $ m = 2 $,构造的矩阵为:

$$K = \begin{pmatrix}11 & 8 \\3 & 7\\ \end{pmatrix}$$

则我们对明文进行线性变换 $y = xK$,即:

$$(y_1, y_2) = (x_1, x_2)\begin{pmatrix}11 & 8 \\3 & 7\\\end{pmatrix}$$

展开之后也即:

$$ y_1 = (11x_1+3x_2)mod26$$

$$y_2 = (8x_1+7x_2)mod26$$

要对明文进行加密也需要先进行分组,对于上面举出的例子,加入我们要加密的明文为 july,则密文为 DELW

要对密文进行解密,首先要了解逆矩阵的概念,读者自行了解。我们把矩阵 $K$ 的逆矩阵表示为 $K^{-1}$,则可以得到解密函数为:

$$ x = yK^{-1}$$

很明显为了构成一个密码体制,必须要使得 $K$ 具有逆矩阵,需要满足的条件为矩阵 $K$ 所对应的行列式的值非零。

到此,给出希尔密码的密码体制:

希尔密码的密码体制: $P = C = (Z_{26})^m$,其中 $m\ge 2$,K 定义为在 $Z_{26}$ 上的 $m \times m$ 矩阵。其加密函数和解密函数分别如下:

$$e_K(x) = xK$$

以及

$$ d_K(y) = yK^{-1} $$

置换密码

置换密码是一种变换原文字母顺序的密码体制,只重新打乱原文。我们先取一个整数 $m$,然后构造一个对原文进行变换的置换 $\pi(x)$。例如我选定的 $ m = 6 $,选定的置换 $\pi(x)$ 表示为:

x 1 2 3 4 5 6
$\pi(x)$ 3 5 1 6 4 2

在这种置换下有:

$$ e_K(x_1, x_2, …, x_m) = (x_{\pi(1)}, x_{\pi(2)}, …,x_{\pi(m)}) $$

对于上面的置换来说就是:

$$ e_K(x_1, x_2, x_3, x_4, x_5, x_6) = (x_3, x_5, x_1, x_6, x_4, x_2) $$

这样就调换了原文的顺序,老规矩,还是要先对明文分组,然后每组用加密函数进行加密,还比较简单,具体的例子我就不举了。

要对密文进行解密,就找出 $\pi(x)$ 的逆置换 $\pi^{-1}(x) $,然后用相反的方式进行就OK。

置换密码的密码体制:$P = C = (Z_{26})^m$,而 $K$ 是所有定义在集合 {1, 2, …, m} 上的置换组成。加密函数及解密函数如下:

$$ e_K(x_1, x_2, …, x_m) = (x_{\pi(1)}, x_{\pi(2)}, …,x_{\pi(m)}) ​$$

以及

$$d_K(y_1, y_2, …, y_m) = (y_{\pi^{-1}(1)}, y_{\pi^{-1}(2)}, …,y_{\pi^{-1}(m)}) $$

特别指出的是,置换密码实际上是希尔密码的一种特殊形式,需要构造的矩阵如下:

$$ k_{i, j} = \begin{cases} 1 &\mbox{i = $\pi (x)$} \\ 0 & \mbox{其他} \end{cases}$$

此条目发表在密码学分类目录。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注