维吉尼亚（Vigenère Cipher）密码原理介绍

一、介绍

  维吉尼亚密码（又译维热纳尔密码）是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。
  维吉尼亚密码曾多次被发明。该方法最早记录在吉奥万·巴蒂斯塔·贝拉索（ Giovan Battista Bellaso）于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的密码》（意大利语：La cifra del. Sig. Giovan Battista Bellaso）中。然而，后来在19世纪时被误传为是法国外交官布莱斯·德·维吉尼亚（Blaise De Vigenère）所创造，因此现在被称为“维吉尼亚密码”。
  维吉尼亚密码以其简单易用而著称，同时初学者通常难以破解，因而又被称为“不可破译的密码”（法语：le chiffre indéchiffrable）。这也让很多人使用维吉尼亚密码来加密的目的就是为了将其破解。
来源：百度百科

二、古典密码

1. 移位密码

我们首先引入符号表示：

$P$：明文空间，所有可能的明文组成的有限集
$C$：密文空间，所有可能的密文组成的有限集
$K$：密钥空间，所有可能的密钥 $k$ 组成的有限集
$Enc$：加密算法
  $En{c}_k(m)=c$ 加密算法$Enc$以密钥$k$、明文$m$为输入，输出密文$c$
$Dec$：加密算法
  $De{c}_k(c)=m$ 解密算法$Dec$以密钥$k$、密文$c$为输入，输出明文$m$
算法正确性：对每个明文 $m\in P$ 以及秘钥 $k\in K$ 都有 $De{c}_k(En{c}_k(m))=m$

其中最典型的移位密码就是凯撒密码，凯撒密码是通过移位替换的方法，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
令 P = C = K = Z 26 = { 0 , 1 , 2 , 3 , . . . , 25 } 随 机 选 择 K ∈ Z 26 作 为 密 钥 E n c k ( m ) = m + k ( m o d 26 ) D e c k ( c ) = c − k ( m o d 26 ) 令P=C=K=Z_{26}=\{ 0,1,2,3,...,25 \} \\ 随机选择 K \in Z_{26} 作为密钥 \\ Enc_k(m)=m+k \pmod {26} \\ Dec_k(c)=c-k\pmod{26} 令P=C=K=Z26​={0,1,2,3,...,25}随机选择K∈Z26​作为密钥Enck​(m)=m+k(mod26)Deck​(c)=c−k(mod26)
其中 $Z_{26}$ 是26个英文字母组成的集合空间。
例如，当偏移量$k$是3的时候，所有的字母A将被替换成D，B变成E … Z变成C，以此类推。

2.维吉尼亚密码

维吉尼亚密码便是移位密码的推广
$$\begin{gathered} P=C=K=Z_{26}^n \\ 随机选择密钥k=(k_1,k_2,..,k_n)\in Z_{26}^n \\ En{c}_k(m_1,m_2,...,m_n)=(m_1+k_1,m_2+k_2,...,m_n+k_n) \\ De{c}_k(c_1,c_2,...,c_n)=(c_1-k_1,c_2-k_2,...,c_n-k_n) \end{gathered}$$
实际上就是每个明文加上对应的密钥字。
举例如下：若密钥为 $CIPHER$，即 $k=(2,8,15,7,4,17)$

明文是以下字符串：

$THISCRYPTOSYSTEMISNOTSECURE$

我们根据字母表将字符串翻译成数字：

$(19,7,8,18,2,17,24,15,19,14,18,24,18,19,4,12,8,18,13,14,19,18,4,2,20,17,4)$

然后将其按照密钥个数进行分组，分别与集合 $K$ 相加，得到密钥：

$(21,15,23,25,6,8,0,23,8,21,22,15,20,1,19,19,12,9,15,22,8,25,8,19,22,25,19)$

因此密文为：

$VPXZGIAXIVWPUBTTMJPWIZITWZT$

3. 二维表形式

我们观察到，若密钥为1的话，A将会变成B，若密钥为2的话，A将会变成C，实际上就是字母表整体往左边移动了一个字母和两个字母的距离，我们把移动的26种情况整理下来，变成了一张二维表。
其中棕色的行表示明文，橙色的列表示密钥。
若密钥为3，实际上对应的字母为C，那么就到C的那一行，可以观察到，A对应的是C，以此类推。因此若想找明文A对应密钥为C的密文，只要找他们的交点即可。以上述例子为例，$THIS$ 的密钥为$(2,8,5,17)$，对应的字母为 $CIPH$，找到 $T$ 和 $C$的交点 $V$，$H$ 和 $I$ 的交点 $P$，$I$ 和 $P$ 的焦点 $X$，$S$ 和 $H$ 的交点 $Z$.因此其密文为 $VPXZ.$

普通的移位密码是通过相同的移位来加密，若明文中有两个相同的字母，例如 $HAPPY$ 的$P$，加密过后仍然会有两个相同的字母，若样本多了之后，就可以根据一些单词的特征进行判断推理进行解密，因此普通的移位加密并不是一种好的加密方法。维吉尼亚密码就可以很好的解决这样的问题。

下一章将介绍维吉尼亚密码的解密。