钥匙：密码学最关键的概念？Key: the most critical concept in cryptography
上次讲到了第三代维吉尼亚密码的加密思路，从这个加密法开始，密码学领域最关键的概念——“钥匙”就出现了。
它是加密和解密的核心，之后凡是涉及到加密解密，就再也离不开钥匙了。
回顾一下什么是钥匙——
我们默认要用多套密码给原文加密的时候，具体操作中每个字母由哪套密码来加密，是由钥匙规定的。
为了处理方便，钥匙最初都是一个正常的单词，比如dream、flower、king等。钥匙中每个字母的顺位，表示原文中对应的字母在加密时采用第几套加密法。
原文很长，钥匙最初很短。但没关系，为了让原文和钥匙一一对应，就反复使用钥匙。比如钥匙是bed，只有3个字母，我们可以bedbedbed这样一直循环下去，和原文中每个字母一一对应。
如果钥匙是bed的话，这个钥匙由3个字母组成，长度是3。那么原文中任何一个字母，都有可能被加密成三种其他字母。因为bed中的b代表后移2位，bed中的e代表后移5位，bed中的d代表后移4位，原文中任何字母都有可能被后移2、4、5位。
那么当钥匙是bed的时候，原文中经常出现的定冠词the，会被加密成3种样式。但如果钥匙是university这样由10个字母组成的长钥匙，原文加密后变成什么样，种类就是10种。这个看起来并不多，但当我们不知道钥匙文具体是什么的时候，种类就会变得无穷多。
而可能性多，其实并不是维吉尼亚密码法的优势，因为即便是单套加密，也有无数多可能性。
那维吉尼亚加密法的优势是什么呢？
维吉尼亚加密法真正的优势是，密文中拼写完全一样的字符，对应的原文可能性也是巨量的，比如说，如果密文是10个字母，钥匙也是10个字母，那么原文就有10^10，也就是100亿种可能性。
同样的原文对应上亿种密文，相同的密文也一样对应上亿种原文。这才是维吉尼亚加密法难以破解的关键。
曾经人们为了抹去字母的频率特征，选用同音替代法。但这样最多只能做到一种原文对应N种密文，而且N一般不会超过10，但反方向上密文一定只对应一种原文。
所以同音替代法的强度，远不及维吉尼亚密码法。
既然维吉尼亚密码法这么强大，是不是无法破解呢？当然不是。
按步骤讲讲破解方法，这种漏洞的出现是什么因素决定的。
在这个例子里，原文是“the sun and the man in the moon”，钥匙是KING，密码文是一串看起来没什么规律的字母。这3样，我们现在都知道。
原文的内容中，有3个定冠词the，变成密文后，the变成了两种样子，第一种是DPR，第二和第三种是BUK。第一个我们不管，关键点就在于——
第二个和第三个竟然加密成了相同的密文。
还记得刚说过维吉尼亚加密法的优势，忍不住要问：
你刚才不是说同一个原文会被加密成非常非常多的形式吗？怎么这短短一句话，原文里的the就被两次加密成同样的密文了？只是因为太巧合了吗？
不是的。我们可以看钥匙单词KING，它由4个字母组成。我们再看密文中，后两个代表the的BUK，间隔了8个字母，间隔距离正好是钥匙长度的2倍。也就是说，正好在KING这个钥匙循环到整数倍的时候，如果也正好赶上出现了同样的原文，那巧合就出现了——原文就会被加密成相等的密文。
这一点，就是破解维吉尼亚密码最关键的部分。
当然，刚刚为了让你好理解，我把钥匙是什么，原文和密文是什么全写出来了。实际破解的时候，你手中只有密文，既不知道钥匙是什么单词，也不知道这个单词的长度，难度会大大增加。但还是有方法——
从密文中把完全一样的单词挑出来，从中总结规律，分析出钥匙的长度。
你一定会质疑：
刚刚不是说维吉尼亚加密法中，相同的密文对应的原文不但不是唯一的，而且数量还极为庞大吗？钥匙是4个字符的情况下，如果密文长度也是4个字符，那密文对应的原文会有256种可能。现在怎么好像原文经常会被加工成相同的密文了？
哎，这背后的原因就是，虽然密文可以变成原文的可能性非常非常多，比如说，有256种之多，但其中大部分拼写出来，根本不是有意义的单词，而是一串没意义的字母，当然就谈不上能拼成完整的句子。
所以，密文对应的原文虽然理论上数量巨大，但拼写规则一卡，数据量就急剧减少。
而且密文里的字符串长度越长，对应真实存在的单词数量就越少。
比如说，让你随口举例由3个字母组成的单词，你光凭脑子想就能找出10多个。但现在我要你随口举出几个由15个字母组成的单词，估计你一个都想不出来，就算查字典，数量也不是特别多。
破解维吉尼亚加密法的方法就是——
第一步，是从密文中找出拼写完全相同的字母串，尤其是那些长度大于4的重复出现的密文。比如一篇几百个字母的密文中，长度超过4，并且重复出现的字母串一共有4种，我们就把它们叫作甲乙丙丁。
第二步呢，我们就数一数，它们第一次出现到第二次出现，中间隔了多少个字母。比如说，如果甲字符串重复间隔了20个字母，那它代表了什么意义呢？
它就代表这段密文对应的钥匙，在这20个字母中，正好反复使用了若干次。那具体是反复使用了1次、2次，还是4次呢？其实都有可能。我们把所有可能性都列出来。
比如说间隔20个字母后同样的密文再次出现，就有这样几种可能：
如果钥匙长度是2的话，说明钥匙正好反复使用了10次，
如果钥匙长度是4的话，说明钥匙正好使用了5次，
如果钥匙长度是5的话，钥匙正好使用了4次。
如果钥匙长度是10的话，钥匙正好使用了2次。
如果钥匙长度是20的话，钥匙正好使用了1次。
你发现没有，其实就是把间隔数的所有因数都找出来就对了。这时候乙、丙、丁的情况，也按同样的步骤操作。我们还会得到很多种钥匙长度的可能性。
到底哪个可能性才是对的呢？我们只要看看，哪个因数在所有甲乙丙丁密文的因数列表里都存在，那个因数对应的钥匙长度就是最终的答案。
到此为止，大功告成。
可能有些人觉得，这没什么可高兴的，知道钥匙具体的内容才管用啊，知道它的长度有什么用呢？
其实不然。
比如说，我们已经知道钥匙的长度是5了，那就意味着在原文中第1、第6、第11、第16……，这些字母单独挑出来放在一组叫作A组。A组可是由维吉尼亚密码表中，同一行移位的字母加密得到的结果。我们再把第2、第7、第12、第17……，这些字母挑出来放在一起称作B组，它们又是用另一行移位字母加密得到的。
那么使用单一一套移位法加密过的文字，我们能不能破解呢？当然了。具体怎么操作，估计你已经想到了——就是我们之前讲的频率分析法。这时候凡是那些出现频率最高的，我们都可以猜它是原文中的字母e，然后再依次分析下去。
所以，猜中钥匙长度就等于，把维吉尼亚密码法化简为N套最基础的移位法了。
完整讲了怎么破解第三代密码——维吉尼亚密码法。核心就是猜钥匙长度，而钥匙也是之后所有加密法和破解法关注的重中之重。
当年抓住钥匙长度破解维吉尼亚密码法的过程，别看我们说出来只用5分钟，但历史上，破解法与加密法足足相隔了230多年的时间。
上节我们讲过，到底是谁发明了维吉尼亚加密法，有很多争议。其实它的解法到底是谁发明的，也有争议。
在20世纪之前，人们一直以为是卡西斯基在1863年破解的，所以一直以来这套破解法叫作“卡西斯基试验法”。但是后来更多的资料公布，发现剑桥大学的巴贝奇在更早的9年前就已经写下了解法。只不过受限于当时英国和俄国在打克里米亚战争，英国情报部门禁止他公开发表成果。
损失了一个发明者的荣誉，但是换来的是英国在之后9年里，轻松获得俄方机密文件的技术优势。
发明者受委屈，这既是密码学领域的特点，又是密码学研究者躲不过的委屈。
不论是剑桥大学的巴贝奇，还是普鲁士军官卡西斯基，虽然他们破解了维吉尼亚密码法，但他们在世的时候，始终都不知道自己其实已经在密码学上引起了一场革命。
最后做个总结：
破解维吉尼亚密码法的关键，就是猜出钥匙的长度；知道了钥匙的长度，维吉尼亚密码就变成了最基础的移位法，用频率分析法就能破解。
1
网友评论