使用维吉尼亚密码进行文件加解密

16世纪法国外交家维吉尼亚（Vigenere，1523—1596）发明的维吉尼亚（Vigenere）密码是密码学发展历史上的重要里程碑，维吉尼亚（Vigenere）密码属于替代密码。

【任务描述】

雅鹿公司电商专员小王需要通过搜索引擎了解维吉尼亚密码的加解密机制，并使用维吉尼亚加解密如下文件内容。请帮助小王完成这一任务。

密钥：stick（长度为5）

明文：Almost all people work hard for success，but not all people can success.Many people ask how tomake success.I think the answer is persistence.The way to success is full of failure and difficulty.People should never give up when meet them.

【任务分析】

维吉尼亚密码是最古老、最著名的多表替代密码之一，与位移密码相似，但维吉尼亚密码的密钥是动态周期变化的。该密码体制有一个参数n。在加解密时，同样把英文字母映射为0～25的数字再进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合，因此可表示加密变换定义如下：

设密钥k＝（k1，k2，…，kn），明文M＝（m1，m2，…，mn），加密变换为Ek（M）＝（c1，c2，…，cn），其中ci＝（mi＋ki）mod26（i＝1，2，…，n）。对密文c＝（c1，c2，…，cn）的解密变换为Dk（C）＝（m1，m2，…，mn），其中mi＝（ci-ki）mod26（i＝1，2，…，n）。

【知识准备】

1.替代密码

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

2.替代密码的分类

1）单表替代密码

单表替代密码的密码算法在加解密时使用一个固定的替代表。单表替代密码又可分为一般单表替代密码、移位密码、仿射密码和密钥短语密码。

2）单表替代密码的加解密原理

一般单表替代密码的原理是以26个英文字母集合上的一个置换π为密钥，对明文消息中的每个字母依次进行变换。其可描述为：明文空间M和密文空间C都是26个英文字母的集合，密钥空间k＝{π：Z26→Z26｜π是置换}，是所有可能置换的集合。

对任意π∈k，定义：

加密变换：eπ（M）＝π（M）＝C

解密变换：dπ（C）＝π-1（C）＝M，π-1是π的逆置换。

3）多表替代密码

多表替代密码的密码算法在加解密时使用多个替代表。多表替代密码有维吉尼亚密码、希尔（Hill）密码和Playfair密码等。

3.替代和移位的区别

1）明文字母顺序的区别

替代保持明文字母顺序，而移位则打乱明文字母顺序。

2）密钥量的区别

移位的密钥量为n！，取决于字母串的个数n，如果n较小，就很容易通过遍历找到密钥。单表替代的密钥量是q！，多表替代有多种情况。

3）字母量的区别

移位不会出现字母串以外的字母，而替代可能出现字母串以外的字母。

【任务实施】

1.使用手工计算进行维吉尼亚密码的加解密

1）根据维吉尼亚密码表进行加密

加密的口诀：密钥指示列，明（密）文指示行，即密码表的最上面一行是明（密）文所在的位置，密码表的最左侧一列是密钥所在的位置。

例如，明文为“MEETME ON THURSDAY”，密钥为“VIGILANCE”，加密方法如下：

（1）先在最上面一行定位明文的第一个字母M，然后沿着M所在的列，往下划一条竖线；

（2）在密码表的最左侧列中定位密钥的第一个字母V，然后沿着V所在的行，往右划一条横线；

（3）两条线的交叉点就是密文H；

（4）依此类推，就可以得到密文为“HMKB XEBP XPMY LLYR”。

2）根据维吉尼亚密码表进行解密(www.xing528.com)

解密的口诀：密钥指示列，找到密文向左看。同理逆向推理可得。

例如，密文为“HMKB XEBP XPMY LLYR”，密钥为VIGILANCE，解密方法如下：

（1）在密码表的最左侧列中定位密钥的第一个字母V，然后沿着V所在的行，往右方查找；

（2）找到字母H后，再向上到密码表的最上面一行，定位出明文的第一个字母M；

（3）依此类推，就可以得到明文“MEETME ON THURSDAY”。

具体破解示例如图3-8所示。

图3-8　具体破解示例

2.使用CAP4软件进行维吉尼亚密码的加解密

已知明文：Almost all people work hard for success，but not all people can success.Many people ask how tomake success.I think the answer is persistence.Theway to success is full of failure and difficulty.People should never give up when meet them.

1）猜测密钥的长度

使用CAP4软件，把密文复制进“Ciphertext”文本框中，单击“Polyalphabetic Tools”→“Kasiski”→“Run”按钮，得到该密文的关键字组长为5，如图3-9所示。

图3-9　猜测密钥的长度

根据运行的结果，使用普通的维吉尼亚解密法进行解密。

2）猜测密钥

单击“Polyalphabetic Tools”→“Low Freq”按钮，在“Enter Possible Key Word Length”文本框中输入“5”，得出最有可能的密钥为“stiak”，如图3-10所示。

图3-10　猜测密钥

3）根据密钥破解出明文

由于知道该密文是使用维吉尼亚密码加密而成的，所以运行“Cipher”→“Vigenere”命令进行解密。在“KeyWord”文本框中输入“stiak”，单击“Decipher”按钮得到明文，如图3-11所示。

图3-11　破解出明文

3.破解多表替代密码

（1）多表替代密码的特点。单表替代密码明文中单字母出现的频率分布与密文中相同，多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布，每个映射是简单替代密码中的一对一映射。多表替代密码将明文字母划分为长度相同的消息单元，称为明文分组，对明文成组地进行替代，同一个字母有不同的密文，这改变了单表替代密码中密文的唯一性，使密码分析更加困难。

多表替代密码的特点是使用了两个或两个以上的替代表，著名的维吉尼亚密码和希尔（Hill）密码均是多表替代密码。

（2）多表替代密码的破解难度。多表替代密码的破解比单表替代密码难得多，因为在单表替代下，字母的频率、重复字母模式、字母结合方式等统计特性，除改变了字母名称之外，都未发生变化，依靠这些不变的统计特性，就能破译单表替代密码，而在多表替代下，原来明文中的这些特性通过多个替代表的平均作用被隐蔽起来，因此简单的频率分析方法就失效了。

（3）使用CAP4软件对多表替代密码进行破解。

已知密文：“uhhogwivggiefqwvmwneutkkvfchozjnjyxbtlurfvhtxvaorcsefgpduogxfsdthd opvesevzsuh hurfshtxcywniteqjmogvzeuirtxpdhzismltixhhzlfrwniurdtwniwzieddzevngkvxeqzeoyiuvnoizenphxmogznmmel txsaqymfnwojuhhxidelbmogvzeuirtgblfapbthyeoifbxiawjsfsqzqbtfnxiertigoxthjnwnigrdsiuhhtxieukgfiyorhsw gxjoqieorhpidtwnigrdsiprirehtkkyteu”采用维吉尼亚密码加密，密钥长度是5，请分析得出明文。

单击CAP4软件左侧分析工具“Polyalphabetic Tools”中的“Low Freq”按钮，输入密钥可能长度，单击“Run”按钮，出现频率分析报告和可能的密钥。

再使用可能的密钥对密文进行解密，看是否能够正确解密出明文，直到找到正确的密钥为止。密文越长，用频率分析的效果越好。采用低频率分析工具对多表替代密码进行密钥分析如图3-12所示。

图3-12　采用低频率分析工具对多表替代密码进行密钥分析

（4）CAP4软件提供了很多实用的密码分析工具，一般来说，破解密码不可能一次成功，往往需要尝试很多方法，学习者应当在掌握密码算法的基础上进行分析。

【讨论】

使用简单频率分析方法破解单表替代密码的缺点是什么？

【动手做一做】

选择一门编程语言，编写维吉尼亚密码算法的实现程序。要求：用户从键盘输入密钥k和任意的明文信息，输出相应的密文。