0%

密码学(一):古典密码之维吉尼亚密码介绍

维吉尼亚(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$:加密算法
  $Enc_k(m)=c$ 加密算法$Enc$以密钥$k$、明文$m$为输入,输出密文$c$
$Dec$:加密算法
  $Dec_k(c)=m$ 解密算法$Dec$以密钥$k$、密文$c$为输入,输出明文$m$
算法正确性:对每个明文 $m\in P$ 以及秘钥 $k\in K$ 都有 $Dec_k(Enc_k(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}
$$
其中 $Z_{26}$ 是26个英文字母组成的集合空间。
例如,当偏移量$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)
$$
实际上就是每个明文加上对应的密钥字。
举例如下:若密钥为 $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$,加密过后仍然会有两个相同的字母,若样本多了之后,就可以根据一些单词的特征进行判断推理进行解密,因此普通的移位加密并不是一种好的加密方法。维吉尼亚密码就可以很好的解决这样的问题。

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