【写在前面】这篇文章是我师傅最近心血来潮写的，主要介绍如何在无密钥的情况下使用数学方法破解维吉尼亚密码，一共分为三个部分，会预设读者——也就是你——已经了解了维吉尼亚密码的基本操作方法，并具备一定的数学知识。当然，如果你完全不了解这些，他在最后也附上了破解的操作性方法和部分C++代码以供使用。不过，如果你能听得懂前面的内容，建议还是听一听，这样如果破解的时候出了问题，自己就能排查。
第一部分：如何把维吉尼亚密码写成谁也看不懂的样子
为了让计算机也能处理维吉尼亚密码的密文，我们要先定义这种加密方式。为了更通俗易懂地说明，我们先从凯撒密码开始。
代换密码的本质是用另一个符号代替明文中的符号，即明文所使用的符号集 和密文所使用的符号集 是一一对应的双射关系。用数学语言表示就是：对于映射 ，如果集合中的任意两个不同元素 ，都有 ，且对于集合中的任一元素 ，都有集合中的元素 使得 ，那么这个映射 就是双射。
破解密码的过程实质上就是寻找这两个集合之间的对应关系，即求解逆映射 的过程。在凯撒密码中，代换方式是使用26个字母相互替换，因此可以表示为英文字母集的自映射，即 。凯撒密码的加密方式是：对于集合中的某一个字母，都使用其后一个字母来替换（如果是字母z，那么使用字母a来替换）。因此，我们可以先将字母用数字代替，然后使用一个定义在模26剩余类加群上的函数来表示凯撒密码。具体定义过程如下：
首先，令a=0，b=1，c=2，以此类推到z=25，，这样一来，凯撒密码的加密方式就基本等同于“+1”，只有当“25+1=26”后，才需要将26换成0。因此，我们可以用“取余”的方式来统一定义：“（25+1）mod 26=0”。
所以其次，定义一个剩余类群 ，其代数运算为模26剩余类加法，即对于任意两个元素 ，都有 。
这样一来，我们就能定义凯撒密码的加密方式了：存在映射 ，使得任意的明文 都存在密文 满足 ，其中映射的具体形式为 。所以，反过来讲，其解密方式为逆映射 。
当然，继凯撒密码之后，我们还可以衍生出类似的加密方式，比如每次不再用b替代a，而是用c替代a，即向后移动两位来加密，那么这时候的映射就变为 。我们可以定义一个“密钥”的概念来统合这些升级版本：设密钥为自然数 ，那么可以将凯撒密码升级为 。
类似地，代换密码都可以用 的形式来定义，例如有名的仿射密码，其密钥为定义在 上的二元数组 ，加密方式为 ，解密方式为 。当然，这不在我们今天的讨论范围之内。
注意，上面的 、 都是代表单个字母，如果你要加密解密一整段文字，那么需要不断重复这个过程。当然，我们也可以直接用向量的方式来表示对一整段文字的凯撒加密：即定义n维列向量 ，令密钥为n维列向量 ，其中，加密方式就能写成 。
准备工作完成，我们可以定义维吉尼亚密码了。
维吉尼亚密码也是凯撒密码的升级版，即使用一个密钥令明文中的不同字母使用不同的凯撒移位来加密。例如，密钥是LOVE——对应的数学表示就是(11,14,21,4)，明文是Do you like apples——对应的数学表示就是（3,14,24,14,20,11,8,10,4,0,15,15,11,4,18）。对于第一个字母D，使用密钥中的L来加密，即（3+11）mod 26=14，代换为O；对于第二个字母o，使用密钥中的O来加密，即（14+14）mod 26=2，代换为c；以此类推，直到第五个字母，再回头使用密钥中的L来加密，代换为f，以此循环往复，直至写出密文Oc tsf zdop oktwsn。
根据上述例子，我们将密钥拓展到和明文长度对应后（例如，将密钥扩写成LOVELOVELOVELOV，长度和明文Do you like apples一致），就能定义维吉尼亚密码：对于映射，存在密钥 ，使得对于任意的明文 ，都存在密文 ，使得。
完成了数学上的定义后，下一个问题是，如何破解呢？
第二部分：惟密文攻击法，又名坑爹上司连个密钥都没法给我搞到让我怎么开展工作
相信密码圈的朋友乃至是一般的网推圈朋友都听说过“字频统计法”。对于一段有意义文本，每个字母出现的频率是不一样的。例如，在英文中，e的使用频率最高，z、q、x等就很少使用，以及某些字母在词尾常见/罕见，某两个或三个字母的组合非常常见（如on、the等），等等等等。1970年Dewey,G统计了约438023个字母得到了一份英文字母频率表（下称“26字母频率表”）：| 字母 | 频率 | 字母 | 频率 | 字母 | 频率 | | A | 0.0788 | J | 0.0010 | S | 0.0634 | | B | 0.0156 | K | 0.0060 | T | 0.0978 | | C | 0.0268 | L | 0.0394 | U | 0.0280 | | D | 0.0389 | M | 0.0244 | V | 0.0102 | | E | 0.1268 | N | 0.0706 | W | 0.0214 | | F | 0.0256 | O | 0.0776 | X | 0.0016 | | G | 0.0187 | P | 0.0186 | Y | 0.0202 | | H | 0.0573 | Q | 0.0009 | Z | 0.0006 | | I | 0.0707 | R | 0.0594 | | |
这些规律有助于我们去猜测单表加密的文本。例如，如果你看到一段文本中，经常出现“wkh”这个组合，那么你就可以猜测这是移位3的凯撒加密，wkh=the；又或者，你统计了整段文本，发现a出现的频率远高于其他字母，那么你可以大胆猜测a=e。假设，验证，根据词义和构词规则不断发展，逐渐地解开一段密文。这就是字频统计法。
然而，字频统计法的前提是，密文本身没有破坏符号的分布规律。但对于维吉尼亚这种不同字母使用不同凯撒的加密方式，你就没法单纯从密文文本的统计数据来进行推测了。因此，我们需要更高端的方法。
首先需要确定的是密钥长度：如果能知道密钥长度  ，那么就可以将整个文本拆分为 组（例如第1个、第  个、第  个等等为一组），每一组就等于是一种凯撒加密。因此，首先介绍的是“克思斯基测试”。
因为密钥是周期性循环的，而文本中又常常会有the、and、for这类常见的词组，因此，我们期望一段长文本中，总会有那么几次恰好是同样的密钥字母加密了同样的词组，得到了一样的字母组合。反过来讲，若密文中出现两个相同的字母组，它们所对应的明文字母组未必相同，但相同的可能性很大。因此，克思斯基测试就是，将密文中相同的字母组找出来，并对其相同字母数综合研究，找出它们的相同字母数的最大公因子，就有可能提取出有关密钥字的长度 的信息。
我们结合一个栗子来讲解。下面是一段维吉尼亚加密的文本：
CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE
可以发现，CHR这个字母组出现了足足五次，因此我们可以猜测这恰好是同样的词组被同样的密钥给加密了。因此，数出它们中间间隔的字母个数，求取最大公因数，很可能就是密钥的长度。例如，这段文本中的五个CHR中的每个C之间间隔165、70、40、10个字母，最大公因数为5，因此猜测密钥长度  。
但是，克思斯基测试也有缺陷，至少它不能排除有其他词组被其他密钥加密成同样的CHR的可能性。而且，如果找不到足够多的重复字母组，那么克思斯基测试也等于无用。所以我们需要新的工具。
我们假设一门语言由  个字母构成，每个字母发生的概率为  ，其中  ，那么用概率论的语言来讲，就是将你写下一个字母视为一个事件，该事件的随机变量  一共有 种取值  、  、……、  ，其分布律为  。如果是完全随机的文本，那么所有 的值应该是一样的，都是  ；但前面提到，有意义的英文文本中每个字母出现的概率并不一致。
接下来，我们定义一个名叫“重合指数”（Coincidence Index）的概念。
我们知道字母e在英文文本中出现的概率是12.68%，那么如果在一段长文本中，随机选取两个字母，发现都是e的概率是多少呢？没错，是  。类似地，对于任一概率为 的字母  ，随机选取两个字母后都是 的概率为  。因此，对于一段文本，随机选择其中两个字母，它们相同的概率为  。我们将这个数据记为重合指数  。对于一段完全随机的英文字母文本，  ，而一段有意义的英文文本的  。
重合指数 可以用来描述这段文本的分布律，你可以将其类比为一种“特征值”。如果密文的重合指数非常接近0.065，那么说明它使用了单表替换；如果两段密文的重合指数相似，那么说明它们使用了同一种代换加密方式。
当然，在处理实际密文的时候，我们不可能知道在这种加密方式下每种字母出现的真实概率 ，所以往往会用其估计值  来替代，其中  为密文长度，  为某个字母  出现的频次。这个估计值是怎么得到的呢？这就要用到组合数学的知识了！从 个字母中选择两个，共有  种方法，而两个字母都是 的选法有  种，所以，满足“两个字母相同”的选法共有  种。因此，选到两个字母相同的概率即为“能让两个字母相同的选法”比上“随便选两个字母的选法”，得到  。
好，我们把话题扯回来。那么，面对一段维吉尼亚密文，我们就可以尝试将其进行分组，然后计算不同组的重合指数，如果各组的重合指数平均看下来很接近0.065，那就说明这种分组方法是正确的。例如，我们将上面那段密文5份5份地切开，然后将每份的第一个字母组成一组，每份的第二个字母组成一组，以此类推组成5组，计算其重合指数：0.06298、0.0681004、0.0686124、0.0608144、0.0724484，平均约为0.06659，比其他分组方法得到的数据更接近0.065，说明密钥长度更有可能是5。
解决了密钥长度 的问题后，我们将密文分为 组，每组内都使用一种单一的凯撒加密：
第一组：CVABWEBQBUAWWQRWWXANTBDPXXRDWBFAXCWMNJJFAIACNRNCATBWKDMCDCQQXWK
第二组：HOEITESEWOOEGMFTIFUDSTNSNVTNDPASNHESBGSEGEMRDRSHEAIEORTHNHOANOE
第三组：RARANOBQRASAJNVRAPTCXUGRJRUQTHLVGRLJHNGYNQRRGINRYQPVEEBRVRHIRIE
第四组：EHAXXPQEVKXHMKGZKSEMMIMEEVLWYXJBLZEIWMLPRJVELMRQEEEKWMHTRCPIMI
第五组：EMTXBHMRXXXBMGXXLKMGXAGLLPHTGTHFLBKKRGXHBTLMXGWHVBEAAXHKZLWWGF
考虑到每组对应的明文的可能性只有26种，所以我们需要暴力的范围一下子从  （ 为密文全长）降低到了  。可喜可贺，可喜可贺……个屁嘞！
此时字频统计依旧不能用——因为每组内的密文都是间隔  个字母取到的，根本没法猜测词组、词尾字母频数等，而文本量的骤然减少也让对单个字母的字频统计变得不够准确（说不定这组密文对应的明文中，a出现的次数反而比e多呢？），导致原本在大文本的情况下使用的“边猜边凑”的方法已经不能用了。如果是暴力破解，那等于是每组都要把26种位移可能性都试一遍，试个 组，这依旧不是人类能完成的工程。
那么有什么思路可以使用吗？既然单个字频不靠谱，那我们可不可以整体性地将密文字母的分布律和“26字母频率表”的分布律相比较？虽然可能在单个字母的概率上会有些许出入，但只要整体的那张“图景”足够相似不就好了？
你或许会问，对于每一组密文，我们都有26种位移可能，即便有时间将它们和26字母频率表一一比较，我们又该凭什么断言某一种位移可能比另一种要更“像”26字母频率表呢？
还记得前面提到的重合指数法吗？只不过，前面是在同一段文本中随机选取两个字母，这次是在两段文本中各随机选取一个字母，这样计算出来的“拟重合指数”就是  ，其中  就是密文的某一种位移后得到的字母的频率，  就是字母的一般概率，也就是上面的26字母频率表。这个“拟重合指数”越大，说明两段文本的字母的分布律越相像。而且据我的经验来看，一般最大的那个指数也接近0.065。
因此，破译的“拟重合指数法”就分为五个步骤：
第一步，统计每组密文中每个字母的频数  、  、……、  。
第二步，计算每组密文的长度 ，计算26个字母在该组中的频率分布  、  、……、  。
第三步，找到一般文本的字母概率分布（即上面的频率表）  、  、……、  。
第四步，对于频率分布 进行移位，得到26种排序。如果我草稿没打错，当位移量为  的时候，原本的排序  、  、……、  就会变为  、  、……、 、 、 、……、  ，可将这种排序设为26维向量  ，将第三步中的一般频率的排序设为向量  。
第五步，计算26个相关值  ，其中最大的值所对应的 即为该组密文的位移量。
只要按照这五步骤，将每组的位移量都找到，就可以拼凑出密钥，获得明文。
还是拿前面的例子，对于第一组字母，首先获得  ，自然也就能得到其他25种排序。接着计算相关值，得到下表： | k | 0 | 1 | 2 | 3 | 4 | 5 | | CI | 0.0347667 | 0.0310079 | 0.0356968 | 0.0382286 | 0.0358683 | 0.0389302 | | k | 6 | 7 | 8 | 9 | 10 | 11 | | CI | 0.0273635 | 0.0281905 | 0.0490778 | 0.0616127 | 0.0390984 | 0.0316079 | | k | 12 | 13 | 14 | 15 | 16 | 17 | | CI | 0.0397143 | 0.0381111 | 0.0380333 | 0.0448175 | 0.0354571 | 0.0300444 | | k | 18 | 19 | 20 | 21 | 22 | 23 | | CI | 0.0421222 | 0.0422667 | 0.035781 | 0.0332317 | 0.0486841 | 0.043381 | | k | 24 | 25 | | | | | | CI | 0.0415127 | 0.0356937 | | | | |
可以发现，除了  时相关值约为0.06，其他时候相关值都在0.03或0.04左右徘徊。因此可以确定，第一组的位移量为9，即密钥的首位是J。
以此类推，我们可以得到密钥的五位分别是9、0、13、4、19，即JANET。而明文为：
THE ALMOND TREE WAS IN TENTATIVE BLOSSOM. THE DAYS WERE LONGER OFTEN ENDING WITH MAGNIFICENT EVENINGS OF CORRUGATED PINK SKIES. THE HUNTING SEASON WAS OVER, WITH HOUNDS AND GUNS PUT AWAY FOR SIX MONTHS. THE VINEYARDS WERE BUSY AGAIN AS THE WELL-ORGANIZED FARMERS TREATED THEIR VINES AND THE MORE LACKADAISICAL NEIGHBORS HURRIED TO DO THE PRUNING THEY SHOULD HAVE DONE IN NOVEMBER.
第三部分：保姆式操作说明与部分C++代码
要在没有密钥的情况下破解维吉尼亚密码的步骤：
第一步：使用克思斯基测试或重合指数法，确定密钥长度；
第二步：根据密钥长度对密文进行分组；
第三步：对每组密文使用拟重合指数法，确定位移量；
第四步：写出明文。
以下是我写的C++代码，可自行取用。当然，如果你听懂了前面两部分，那你自己也能写。另外，如果密文长度太短，则也不适合用这个方法，因为统计得到的字母频率和正常的概率偏差过大，导致相关系数不够准确，此时建议大家直接暴力。
#include<iostream>#include<cstring> usingnamespace std; intmain() { //这是我看到的另一种字母概率表，你可以用它替换下一行使用：const float q[26] = {8.17,1.49,2.78,4.25,12.70,2.23,2.02,6.09,6.97,0.15,0.77,4.03,2.41,6.75,7.51,1.93,0.10,5.99,6.33,9.06,2.76,0.98,2.36,0.15,1.97,0.07}; const float q[26] ={7.88,1.56,2.68,3.89,12.68,2.56,1.87,5.73,7.07,0.10,0.60,3.94,2.44,7.06,7.76,1.86,0.09,5.94,6.34,9.78,2.80,1.02,2.14,0.16,2.02,0.06};//英文字母的概率 char t[500];//用于存储密文 int s; int ss; cout << "密文是大写字母请输入1，是小写请输入0："; cin >> ss; if (ss==1) { s = 65; } else { s = 97; }//区分大小写 cout << "请输入密文："; cin >> t;//输入密文 const int long_of_text = strlen(t);//确定密文长度 int m_min; int m_max; int m;//实际的密钥长度，之后有用 cout << "请输入密钥长度范围（最小值）："; cin >> m_min; cout << "请输入密钥长度范围（最大值）："; cin >> m_max; for (int fenzu=m_min; fenzu<=m_max;fenzu++) { int number_of_zu = long_of_text /fenzu; int shen_yu = long_of_text % fenzu; if (shen_yu != 0) { number_of_zu++; } else { shen_yu = fenzu; }//完成分组 int mi_wen[number_of_zu][fenzu]; int fenchai = 0; for (int row=0; row<number_of_zu;row++) { for (int col=0; col<fenzu;col++) { if (fenchai<long_of_text)//fenchai的编号是从0开始，所以不能用小于等于 { mi_wen[row][col] =t[fenchai] - s;//因为大写字母A的数字是65 } fenchai++; } }//将密文转化为数字，存进二维数组中 float CI_guji = 0.0; for (int col=0; col<fenzu; col++) { int chang_du_L = number_of_zu; if (col>=shen_yu) { chang_du_L--; }//得到该组实际的密文长度 int f[26] = {0};//用于计算字频 for (int row=0; row<chang_du_L;row++) { f[mi_wen[row][col]]++; }//计算每个字母的频数 for (int i=0; i<26; i++) { CI_guji = CI_guji +1.0*f[i]*(f[i]-1)/chang_du_L/(chang_du_L-1); } }//针对每一组，进行重合指数分析 CI_guji = CI_guji / fenzu; cout << "m=" <<fenzu << "：" << CI_guji << endl; } cout << "请输入最接近0.065的m："; cin >> m;//输入密钥长度 cout << "密钥为："; //不要问我为什么不把下面这段和上面一模一样的内容做成函数，因为我不知道怎么返回数组。咱只是一个数学系的半吊子，其实根本不懂写代码 int number_of_zu = long_of_text / m; int shen_yu = long_of_text % m; if (shen_yu != 0) { number_of_zu++; } else { shen_yu = m; } int mi_wen[number_of_zu][m];//存储密文的二维数组 int ming_wen[number_of_zu][m];//将用于存储明文的二维数组 int fenchai = 0; for (int row=0; row<number_of_zu; row++) { for (int col=0; col<m; col++) { if (fenchai<long_of_text) { mi_wen[row][col] = t[fenchai] - s; } fenchai++; } } for (int col=0; col<m; col++) { int chang_du_L = number_of_zu; if (col>=shen_yu) { chang_du_L--; } int f[26] = {0};//字母频数 float p[26] = {0.0};//字母频率 for (int row=0; row<chang_du_L;row++) { f[mi_wen[row][col]]++; } for (int i=0; i<26; i++) { p[i] = 1.0 * f[i] / chang_du_L; }//计算每个字母的频率 double corr = 0.0;//相关值卷积 double corr_max = 0.0;//最大相关值 int max_number = 0;//最大对应的位移数 float pp[26] = {0.0};//用于移动26个字母频率的不同序列 for (int k=0; k<26; k++) { for (int i=0; i<26; i++) { pp[i] = p[(k+i)%26]; } for (int j=0; j<26; j++) { corr = corr + pp[j] *(q[j]/100); } if (corr > corr_max) { corr_max = corr; max_number = k; } corr = 0; } for (int i=0; i<chang_du_L; i++) { ming_wen[i][col] = (mi_wen[i][col]+ 26 - max_number) % 26; } char key = max_number + s; cout << key; } for (int row=0; row<number_of_zu; row++) { for (int col=0; col<m; col++) { t[row*m+col] = ming_wen[row][col] +s; } } cout << endl << "明文为："<< t; //实际输出的明文末尾可能会带有几个乱码，但不影响前面的内容 return 0; }
下面是本文的例子的输出结果：
密文是大写字母请输入1，是小写请输入0：1
请输入密文：CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBWRVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAKLXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELXVRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHRZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJTAMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBIPEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHPWQAIIWXNRMGWOIIFKEE
请输入密钥长度范围（最小值）：1
请输入密钥长度范围（最大值）：9
m=1：0.0450152
m=2：0.0432958
m=3：0.0466458
m=4：0.0416841
m=5：0.0665911
m=6：0.0438283
m=7：0.0424544
m=8：0.0420378
m=9：0.0455366
请输入最接近0.065的m：5
密钥为：JANET
明文为：THEALMONDTREEWASINTENTATIVEBLOSSOMTHEDAYSWERELONGEROFTENENDINGWITHMAGNIFICENTEVENINGSOFCORRUGATEDPINKSKIESTHEHUNTINGSEASONWASOVERWITHHOUNDSANDGUNSPUTAWAYFORSIXMONTHSTHEVINEYARDSWEREBUSYAGAINASTHEWELLORGANIZEDFARMERSTREATEDTHEIRVINESANDTHEMORELACKADAISICALNEIGHBORSHURRIEDTODOTHEPRUNINGTHEYSHOULDHAVEDONEINNOVEMBER礱
Process returned 0 (0x0) execution time : 19.595 s
Press any key to continue. | 
