密码学（一）：古典密码之维吉尼亚密码原理介绍

维吉尼亚（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$P：明文空间，所有可能的明文组成的有限集
$C$C：密文空间，所有可能的密文组成的有限集
$K$K：**空间，所有可能的** $k$k 组成的有限集
$Enc$Enc：加密算法
  $Enc_k(m)=c$Enck​(m)=c 加密算法$Enc$Enc以**$k$k、明文$m$m为输入，输出密文$c$c
$Dec$Dec：加密算法
  $Dec_k(c)=m$Deck​(c)=m 解密算法$Dec$Dec以**$k$k、密文$c$c为输入，输出明文$m$m
算法正确性：对每个明文 $m\in P$m∈P 以及秘钥 $k\in K$k∈K 都有 $Dec_k(Enc_k(m))=m$Deck​(Enck​(m))=m

其中最典型的移位密码就是凯撒密码，凯撒密码是通过移位替换的方法，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
$令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}$Z26​ 是26个英文字母组成的集合空间。
例如，当偏移量$k$k是3的时候，所有的字母A将被替换成D，B变成E … Z变成C，以此类推。

2.维吉尼亚密码

维吉尼亚密码便是移位密码的推广
$P=C=K=Z_{26}^n\\ 随机选择**k=(k_1,k_2,..,k_n) \in Z_{26}^n \\ Enc_k(m_1,m_2,...,m_n)=(m_1+k_1,m_2+k_2,...,m_n+k_n) \\ Dec_k(c_1,c_2,...,c_n)=(c_1-k_1,c_2-k_2,...,c_n-k_n)$P=C=K=Z26n​随机选择密钥k=(k1​,k2​,..,kn​)∈Z26n​Enck​(m1​,m2​,...,mn​)=(m1​+k1​,m2​+k2​,...,mn​+kn​)Deck​(c1​,c2​,...,cn​)=(c1​−k1​,c2​−k2​,...,cn​−kn​)
实际上就是每个明文加上对应的**字。
举例如下：若**为 $CIPHER$CIPHER，即 $k=(2,8,15,7,4,17)$k=(2,8,15,7,4,17)

明文是以下字符串：

$THISCRYPTOSYSTEMISNOTSECURE$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)$(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$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)$(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$VPXZGIAXIVWPUBTTMJPWIZITWZT

3. 二维表形式

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

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

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