【文章标题】:现学现卖Vigenere加密法
【文章作者】: schlieffen
【作者邮箱】: mirrorbyice@163.com
【作者声明】: 只是感兴趣，没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------

    版主jackozoo在先前已经发表了一篇关于Vigenere加密法的帖子(http://bbs.pediy.com/showthread.php?t=89667)，但是并没有涉及具体的破解工作。我现在正在学习密码学，于是现学现卖，讲讲Vigenere加密法一些详细内容。水品不咋滴，望大虾们赐教。

    Vigenere加密法也是需要关键字的，但并非是单码加密法的一一替换关系，而是通过关键字与明文关联，从而确定密文。例如，我的明文为“maxwell house”（我喜欢的咖啡品牌），关键字是“love”，那么关键字--明文的对应关联如下：
    密钥：lovelovelove
    明文：maxwellhouse

    密文将通过下面的Vigenere表得到，由密钥字母确定表的行，明文字母确定表的列，我们在行与列的交叉处得到密文，上例的密文将是：“xosapzglzini”。这有点像我们在几何中通过x、y的坐标来确定点在坐标图中的位置。
  
      
  
   
    Vigenere加密法的强大使其持续了几百年不可被破解，先前用于分析单码加密的方法对他没有多大效果。尤其是密文中出现的字母频率都差不多了，便无法通过语言的自身特性来与其匹配。当然，强中更有强中手，Vigenere加密法出现300年后，在1863年一个叫Frederick Kasiski的人出版了一本有关密码分析的小册子，其中便描述了确定Vigenere加密法关键字长度的过程，有了关键字的长度，便很容易确定关键字和明文了。（我读到的破解Vigenere加密法的历史与jackozoo讲到的不太一样，年份是差不多，方法也一样，就是名字不一样。具体谁是对的，有兴趣的读者可以上网查一查，也有可能两个人都对了，嘿嘿！）

    Frederick Kasiski通过对Vigenere加密法长时间的观察，得到一个简单的结论：密钥的重复部分与明文的重复部分连接，在密文中也产生一个重复部分。在通信中，我们肯定会使用很多重复的单词，例如the、what、dear等，如果与他们对应的关键字也是相同的，则会产生相同的密文。举一个简单的例子：
密钥:r u n r u n r u n r u n r u n r u n r u n r u n r u n r u n
明文:t o b e o r n o t t o b e t h a t i s t h e q u e s t i o n
密文:k i o v i e e i g k i o v n u r n v j n u v k h v m g z i  a
     |--------9--------|       |-----6-----|
我们注意到，密文中重复字符串之间的距离反映了密钥重复的次数，既反映了密钥的长度。上例中，两次“kiov”之间的距离为9，“nu”之间的距离为6，我们可以猜测这些距离因该是密钥长度的倍数，密钥长度可能为3。于是Kasiski建议的破解过程如下：
(1)找到密文中重复的字符部分
(2)计算重复字符之间的字符数
(3)找出从步骤(2)中得到的数的因子（就是最大公约数）
(4)最大公约数很可能就是关键字的长度

    当然，也会有巧合的时候。偶然性的重复字符串会影响对关键字长度的确定，这需要靠我们更多的观察、思考来排除。

    找到了关键字长度，我们就可以下手破解了。关键字的长度意味着什么？我们可以看出，在明文中，将与关键字中相同字符关联的明文字符集合到一起，他们其实是单码加密的。我文笔不好，说的比较晦涩。还是上面的例子，将与密钥run中的r字符关联的明文（黄色字符表示）的放在一起，然后参考Vigenere表中的r列，可以发现它们都是简单的移位加密。
于是，在我们知道关键字长度后，破解Vigenere加密法就变成了破解n（关键字长度为n）个不同的单码加密的问题了。

   我们根据关键字长度，将密文字符串按一定规律分解排布，将1，n+1，2n+1，3n+1，。。。。。。字符放入第一个集合，将2，n+2，2n+2，3n+2.。。。。。放入第二个集合，同样操作至结束。每个集合就是一个单码加密的密文，然后我们通过对单码加密的分析法来一一破解。其实对每一个集合，我们还可以用低频率分析法来分析，将集合I中的每个字符移位一次得到另一个集合II，再移位一次又能得到新的集合III。。。。。重复这些动作，一共移位25次，我们共得到26个集合，其中有一个集合便是我们需要的明文。但是这个集合是从原始的明文中选取的集合，其中的不可能构成可能的单词，我们便通过标准英语的另外一一些特征来确定它是不是我们需要的明文集合，例如字母j、k、q、x、z这些字符出现的频率和不足2%。


    讲到这里，我们基本上了解了破解Vigenere加密法的步骤，其中的要害便是找到关键字的长度。


    美国密码学家William Friedman（一开始我将Friedman读成冯诺依曼,顿时又添一份崇拜感，汗。当然，这两位都是密码学上的大师）通过他对数学的造诣，提出了一致性索引的概念（Index of Coincidence，IC）来分析多码加密法。我们知道，英语中每个字符出现的概率都是不一样的，绘成频率分析图，图中就有高峰与低谷，单码加密法是没有办法改变字母出现的概率的，但是对于多玛加密法，我们得到的字母频率图就变得很光滑了。完全平滑的分布就是每个字母出现的概率就是1/26的情况。IC是基于凹凸度量的，凹凸度量是指从文本中选取的字母的实际概率与从完全平滑的分布中选取该字母的概率之差。

    设Pa是从密文中选取a字母的概率，那么上述的概率偏差即为（Pa-1/26）^2。加平方是为了保证得到的值为正值。设MR为完全偏差，因此a到z所有字母的偏差和为MR=，通过拆分和取舍，可以将这个式子简化成。

    对于某个密文，如果估算出Pa^2，那么MR就能确定。由于Pa为从密文中选取字母a的概率，那么Pa^2就是从全部密文中选取字母a的概率和从剩余密文中（即去掉第一个a字母的密文）中选取的字母a的概率的倍数。如果密文中有n个a字母，Fa是密文中a字母的个数，那么Pa=Fa/n，Pa^2=（Fa/n）[（Fa-1）/(n-1)]。（这一段完全抄书，我对Pa^2的计算不太理解，概率平方后加起来是不是一了？，我说不太清楚，概率论考试也挂了，哎）

    MR依赖于密文的唯一之处就是Pa^2的和，于是IC可以定义为：IC=。

    通过分析和资料，我们得知单码加密法的IC大概为0. 066。完全平滑的文字，其值为0.38，如果IC的值在0.38到0.066之间，就说明该密文很可能就是多码加密法。事实上，通过下表，我们能得知IC值暗示的多码加密法的密钥长度：


    到此为止，我所能讲的就这些了，现学现卖。前半部分是通过我的理解写出来的，后面关于IC的部分基本抄书。我所用的参考书是《经典密码学与现代密码学》，Richard Spillman著，原书更加精彩。到了发贴的时候才知道不会编辑，于是版面很乱。

--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                                              2009年09月06日