浅谈古典密码

根据密码学的考纲和PPT，简单的归纳一下古典密码学的做法。一般来说都会作为大题考察，因为考察近现代密码用手算不是很现实……

代替密码是指先建立一个替换表，加密时将需要加密的明文依次通过查表，替换为相应的字符。明文字符被逐个替换后，生成无任何意义的字符串，即密文。代替密码的密钥就是其替换表。

根据密码算法加解密时使用替换表多少的不同，代替密码又可分为单表代替密码和多表代替密码。

单表代替密码：密码算法加解密时使用一个固定的替换表
多表代替密码：密码算法加解密时使用多个替换表

我们简单的把古典密码分为单标代替和多表代替来讨论。单表代替的重点是仿射密码，多表代替的重点是希尔密码。虽然古典密码相对比较简单，但还是推荐读者多动笔计算一下。

那么就开始吧。

单表代替

单表代替密码密钥量很小，不能抵抗穷尽搜索攻击。且没有将明文字母出现的概率掩藏起来，很容易受到统计分析的攻击。

单表代替密码主要介绍三种：

移位密码
使用密钥的单表代替密码
仿射密码

移位密码

移位密码非常简单，就是把明文对应的字符移动对应的位数即可得到密文，再移回来就可以得到明文。

加密变换： $E=\{E:Z_{26}\rightarrow Z_{26},E_k(p)=p+k(\bmod26)|p\in P,k\in K \}$

解密变换： $D=\{D:Z_{26}\rightarrow Z_{26},D_k=c-k(\bmod 26)|c\in C,k\in K \}$

当移位密码的密钥 $k=3$ 时，就是著名的凯撒密码。

此时： $ceasar\ cipher\rightarrow FDHVDU\ FLSKHU$

使用密钥的单表代替加密

选用一个英文短语或者单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字母串，然后将字母表中的其他字母依次写于此字母串之后，就可构造出一个字母代替表。

例题

给定密钥为： $spectacular$

明文： $ABCDEFGHIJKLMNOPQRSTUVWXYZ$

密文： $spectaulrbdfghijkmnoqvwxyz$

如果明文为 $China$ ，则对应密文为 $elrhs$

仿射密码

仿射密码是加强版的移位密码。移位密码的密钥空间只有26，但是仿射密码的密钥空间有312.虽然比移位密码更强大，但数据量仍然不大，在现代计算机面前通过爆破破解明文轻而易举。同时，没有隐藏

仿射密码是一种线性变换。仿射密码的明文空间和密文空间与移位密码相同，但密钥空间为 $K=\{(k_1,k_2)|k_1,k_2\in Z_{26},gcd(k_1,26)=1 \}$ 。即需要两个密钥 $k_1$ ， $k_2$ ； $k_1$ 必须和26互素。否则会出现多个明文字母对应同一密文字母的情况。

对任意的 $p\in P,c\in C,k=(k_1,k_2)\in K$ ，

定义加密变换为： $c=E_k(p)=k_1p+k_2(\bmod26)$

相应的解密变换为： $p=D_k(c)=k^{-1}(c-k_2)(\bmod 26)$

其中 $k_1k_1^{-1}=1(\bmod26)$ ，即 $k_1^{-1}$ 为 $k_1$ 的逆元。

例题

设明文消息为China，密钥 $k = (k_1, k_2) = (7, 3)$ ，用仿射密码对其进行加密，然后再进行解密。

利用扩展欧几里得算法求出 $k_1^{-1}=7_{-1}=15(\bmod26)$ ，加密函数 $E_k(p)=7\times p+3(\bmod26)$ ，对应的解密函数为 $D_k(c)=15\times (c-3)(\bmod26)=15c-19(\bmod26)$ 。

明文消息 $China$ 对应的数字序列为 $(2,7,8,13,0)$ ，用仿射密码对明文进行加密：

$c=E_{k}(p)=7 \times\left[\begin{array}{c} 2 \\ 7 \\ 8 \\ 13 \\ 0 \end{array}\right]+\left[\begin{array}{l} 3 \\ 3 \\ 3 \\ 3 \\ 3 \end{array}\right]=\left[\begin{array}{c} 17 \\ 52 \\ 59 \\ 94 \\ 3 \end{array}\right] \bmod 26=\left[\begin{array}{c} 17 \\ 0 \\ 7 \\ 16 \\ 3 \end{array}\right]=\left[\begin{array}{c} R \\ A \\ H \\ Q \\ D \end{array}\right]$

对应密文消息为 $RAHQD$

解密：

$D_{k}(c)=15 \times\left[\begin{array}{c} 17 \\ 0 \\ 7 \\ 16 \\ 3 \end{array}\right]-\left[\begin{array}{c} 19 \\ 19 \\ 19 \\ 19 \\ 19 \end{array}\right]=\left[\begin{array}{c} 236 \\ -19 \\ 86 \\ 221 \\ 26 \end{array}\right] \bmod 26=\left[\begin{array}{c} 2 \\ 7 \\ 8 \\ 13 \\ 0 \end{array}\right]=\left[\begin{array}{c} C \\ H \\ I \\ N \\ A \end{array}\right]$

多表代替密码

多表代替密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率的分布，其中每个映射都是单表代替密码中的一对一映射。一般来说，我们的做法都是将明文字母划分为长度相同的消息单元，称为明文分组，对明文字母成组地进行代替。

多表代替密码的特点是使用两个或者两个以上的表。

我们主要介绍以下三个多表代替密码：

普莱菲尔密码（Playfair Cipher）
维吉尼亚密码（Vigenere Cipher）
希尔密码（Hill Cipher）

Playfair密码

Playfair密码加密流程如下：

将明文中的双字母作为一个单元对待，并将这些单元转换为密文字母组合
基于一个5×5字母矩阵，使用一个关键词（密钥）来构造
构造方法：从左至右，从上至下依次填入关键词的字母（去除重复的字母），然后再以字母表顺序依次填入其他的字母。加密时字母I和J被算作一个字母

例如，密钥 $k= playfair\ is\ a\ digram\ cipher$ ，去除重复字母后， $k= playfirsdgmche$ ，可得字母矩阵如下
对每一对明文字母P1, P2的加密方法如下：
- 若P1、P2在同一行，密文C1、C2分别是紧靠P1、P2右端的字母。其中第一列被看作是最后一列的右方；（解密时反向）
- 若P1、P2在同一列，密文C1、C2分别是紧靠P1、P2下方的字母。其中第一行看作是最后一行的下方；（解密时反向）
- 若P1、P2不在同一行，也不在同一列，则C1、C2是由P1、P2确定的矩形其它两角的字母，且C1和P1在同一行，C2和P2在同一行；（解密时处理方法相同）
- 若P1＝P2，则两个字母间插入一个预先约定的字母，如q，并用前述方法处理；如balloon，则以ba lq lo on 来加密。
- 若明文字母数为奇数，则在明文尾填充约定字母。

例题

密钥不变，延续上文的字母矩阵。明文为 $p = playfair\ cipher$ ，用playfair密码进行加密。

明文分组： $pl\ ay\ fa\ ir\ ci\ ph\ er$

密文分组： $LA\ YF\ PY\ RS\ MR\ AM\ CD$

特点

虽然仅有26个字母，但有26×26＝676种双字母组合．因此识别各种双字母组合要困难得多
各个字母组的频率要比单字母呈现出大得多的范围，使得频率分析困难得多
仍然使许多明文语言的结构保存完好，使得密码分析者能够利用

Vigenere密码

Vigenere密码是最著名的多表代替密码的例子，它使用一个词组作为密钥，密钥中每一个字母用来确定一个代替表，每一个密钥字母用来加密一个明文字母，等所有密钥字母使用完后，密钥又再循环使用

设密钥 $𝑘 = (𝑘_1, 𝑘_2, ⋯ , 𝑘_𝑑)$ ，明文： $𝑝 = (𝑝_1, 𝑝_2, ⋯ , 𝑝_𝑛)$ ，密文： $𝑐 = (𝑐_1, 𝑐_2, ⋯ , 𝑐_𝑛)$ 。

加密变换： $𝐸_𝑘(p)= (𝑐_1, 𝑐_2, ⋯ , 𝑐_𝑛)$ ，其中 $𝑐_𝑖 = (𝑝_𝑖 + 𝑘_𝑖)(\bmod 26)，i =1, 2, …, n$

解密变换： $𝐷_𝑘(c)= (𝑝_1, 𝑝_2, ⋯ , 𝑝_𝑛)$ ，其中 $𝑝_𝑖 = (𝑐_𝑖 − 𝑘_𝑖)(\bmod 26)，i =1, 2, …, n$

即对每一个字母都用不同的表去进行移位代替。

例题

$p = appliedcryptosystem$ ， $k = cipher$ ，用Vigenere密码对其进行加密。

由 $k=cipher$ 得n=6。密钥对应的数字序列为 $(2,8,15,17,4,17)$ 。将明文按照每6个字母进行分组，并将这些明文字母转换为相应的数字，再用模26加上对应的密钥数字，加密过程如图所示：

Hill密码

注意，由于Hill密码涉及到矩阵的乘法，所以运算顺序的不同会影响最终的结果。网络上的资料多为密钥右乘，而本文章遵循的是学校PPT教材，采取的方式是密钥左乘（即 $k\times p/c$ ），务必留意。

基本思想：将n个明文字母通过线性变换，将它们转换为n个密文字母。解密只需做一次逆变换即可。

算法的密钥为 $k=\{Z_{26}上的n\times n可逆矩阵 \}$ ，明文p与密文c均为n维向量，记为：

$p=\left(\begin{array}{c} p_{1} \\ p_{2} \\ \vdots \\ p_{n} \end{array}\right), \quad c=\left(\begin{array}{c} c_{1} \\ c_{2} \\ \vdots \\ c_{n} \end{array}\right), k=\left(k_{i j}\right)_{n \times n}=\left[\begin{array}{cccc} k_{11} & k_{12} & \cdots & k_{1 n} \\ \vdots & \ddots & & \vdots \\ \vdots & & \ddots & \vdots \\ k_{n 1} & k_{n 2} & \cdots & k_{n n} \end{array}\right]$

加密变换： $E_k(p)=k·p=c(\bmod26)$

解密变换： $D_k(c)=k^{-1}·c=p(\bmod26)$

其中 $k^{-1}$ 被称为 $k$ 在模26上的逆矩阵。逆矩阵涉及到线性代数，因此我们需要特别定义一下密钥矩阵 $k$ ，来保证其逆矩阵存在。

假设 $A=(a_{ij})$ 为一个定义在 $Z_{26}$ 的 $n\times n$ 矩阵，如果 $A$ 在模26上可逆，则有： $A^{-1}=A^*/det(A)(\bmod26)$ 。

其中 $det(A)$ 为 $A$ 的行列式， $A^*$ 为 $A$ 的伴随矩阵， $A^*_{j,i}=(-1)^{i+j}M_{i,j}$ ， $M_{i,j}$ 为矩阵 $A$ 去掉第 $i$ 行、第 $j$ 列后剩余元素所组成的矩阵行列式。注意，伴随矩阵需要进行转置处理。

对于一个 $n×n$ 矩阵 $A$ ，其伴随矩阵 $\text{adj}(A)$ 是由 A 的代数余子式构成的矩阵的转置。

在n=2时，有下列推论：

假设 $A=\left(\begin{array}{c} a_{1,1},a_{1,2} \\ a_{2,1},a_{2,2} \\ \end{array}\right)$ 是一个 $Z_{26}$ 上的 $2\times 2$ 矩阵，它的行列式 $det(A)=a_{1,1}a_{2,2}-a_{1,2}a_{2,1}$ ，那么有：

$A^{-1}=(det(A))^{-1}\left(\begin{array}{c} a_{2,2},-a_{1,2} \\ -a_{2,1},a_{1,1} \\ \end{array}\right)$

例题

设明文消息为 $good$ ，试用n＝2，密钥 $k=\left(\begin{array}{c} 11,8 \\ 3,7 \\ \end{array}\right)$ 的Hill密码对其进行加密，然后再进行解密（明密文分组列向量表示）

因为 $k=\left(\begin{array}{c} 11,8 \\ 3,7 \\ \end{array}\right)$ ，故 $\text{det}\left(\begin{array}{c} 11,8 \\ 3,7 \\ \end{array}\right)=11\times 7-3\times 8(\bmod26)=53(\bmod)=1$

$k^{-1}=\left(\begin{array}{c} 11,8 \\ 3,7 \\ \end{array}\right)=1^{-1}\times \left(\begin{array}{c} 7,-8 \\ -3,11 \\ \end{array}\right)=\left(\begin{array}{c} 11,18 \\ 23,7 \\ \end{array}\right)\bmod26$

将明文划分为两组： $(g,o),(o,d)$ ，即 $(6,14),(14,3)$ ，加密过程如下：

$\begin{array}{l} \binom{c_{1}}{c_{2}}=k\binom{p_{1}}{p_{2}}=\left(\begin{array}{ll} 11 & 8 \\ 3 & 7 \end{array}\right)\binom{6}{14}=\binom{178}{116}=\binom{22}{12}(\bmod 26) \Rightarrow\binom{w}{m} \\ \binom{c_{3}}{c_{4}}=k\binom{p_{3}}{p_{4}}=\left(\begin{array}{cc} 11 & 8 \\ 3 & 7 \end{array}\right)\binom{14}{3}=\binom{178}{63}=\binom{22}{11}(\bmod 26) \Rightarrow\binom{w}{l} \end{array}$

因此，good的加密结果是wmwl。显然，明文不同位置的字母“o”加密成的密文字母不同。

解密变换：由前面计算有 $k^{-1}=\left(\begin{array}{c} 7,18 \\ 23,11 \\ \end{array}\right)$ ，可由密文解密计算出明文，过程如下：

$\begin{array}{l} \binom{p_{1}}{p_{2}}=k^{-1}\binom{c_{1}}{c_{2}}=\left(\begin{array}{cc} 7 & 18 \\ 23 & 11 \end{array}\right)\binom{22}{12}=\binom{370}{638}=\binom{6}{14}(\bmod 26) \Rightarrow\binom{g}{o} \\ \binom{p_{3}}{p_{4}}=k^{-1}\binom{c_{3}}{c_{4}}=\left(\begin{array}{cc} 7 & 18 \\ 23 & 11 \end{array}\right)\binom{22}{11}=\binom{352}{627}=\binom{14}{3} \bmod 26 \Rightarrow\binom{o}{d} \end{array}$