维吉尼亚密码解码（维吉尼亚密码crimaster）
维吉尼亚密码解码（维吉尼亚密码crimaster）
维吉尼亚密码引入了“密钥”的概念，即根据密钥来决定用哪一行的密表来进行替换，以此来对抗字频统计。假如以上面第一行代表明文字母，左面第一列代表密钥字母，对如下明文加密:
TO BE OR NOT TO BE THAT IS THE QUESTION
当选定RELATIONS作为密钥时，加密过程是：明文一个字母为T，第一个密钥字母为R，因此可以找到在R行中代替T的为K，依此类推，得出对应关系如下：
密钥:RE LA TI ONS RE LA TION SR ELA TIONSREL
明文:TO BE OR NOT TO BE THAT IS THE QUESTION
密文:KS ME HZ BBL KS ME MPOG AJ XSE JCSFLZSY
与凯撒密码类似,进行一下运算两次即可
1.Kerckhoff's principle:
加密方法不必要求是保密的，它肯定会很容易就落入敌人的手中。安全性仅仅依靠key的安全性。
支持上述principle的三个基本理论：
（1）无论对于哪一方来说，保持一个短的key的安全性比保持加密算法的安全性要简单得多。
（2）当信息被暴露时，改变一个key比替换一个加密模式要简单。
（3）用户们一起使用相同的加密算法好过用户自己使用它们自己的加密算法。
2.通过利用英文的统计模型，可以攻击单字母替换密码：（暴力攻击需要26次）
（1）如果e映射为D，则每个在明文中出现的e都会在密文中显示为D。
（2）每个英文字母出现的频率分布是已知的。
3.移位密码的改进版攻击方法：
（1）将26个字母与数字0~25一一对应，设pi为第i个字母出现的频率（确定的），0= pi =1。由Figure 1.3 给出以下式子：
（2）得到一些密文后，设qi为第i个字母在密文中出现的频率（第i个字母出现的次数除以密文长度）。
（3）设key为k，则pi=
，因为第i个字母被映射到第(i+k)个字母。
（4）设 j ∈{0，...，25} ，对于 j 可能取到的这26个值，分别计算下列式子：
（5）当找到Ik = 0.065，则可得到key的值k。
4.破解多字母移位密码（维吉尼亚密码）： （当key长度为t时，暴力攻击需要 26t 次）
吉尼亚密码分解后实则就是多个凯撒密码，只要知道密钥的长度，我们就可以将其分解。
如密文为：ABCDEFGHIJKLMN
如果我们知道密钥长度为3，就可将其分解为三组：
组1：A D G J M （密文中第 0， 3，6，9，12 个字母）
组2：B E H K N （密文中第 1，4，7，10，13 个字母）
组3：C F I L （密文中第 2，5，8，11 个字母）
分解后每组就是一个凯撒密码，即组内的位移量是一致的，对每一组即可用频度分析法来解密。
所以破解维吉尼亚密码的关键就是确定密钥的长度。
当不知道key的长度时。
（1）设key的长度为t，以下字符有相同的位移量
（2）设qi为第i个字母在上面字符串中出现的频率（第i个字母出现的次数除以字符串长度）。
（3）设位移量为j，则
（4）设
（左边这个变量包含了我们要求的key的长度t ，我们从1开始试t的值）
由（1）我们可知
有相同的位移量。接着我们计算下列式子，找出符合式子的t值：
（5）当T不是key的长度t时，则我们期望每个qi的频率都是1/26
※ 维吉尼亚密码、单字母替换密码比对移位密码的攻击需要更长的密文。
5.如今，schemes（方案）被以一种更系统的方式发展和分析，并最终用来给出严格proof（证据）证明给出的construction（结构）是安全的。为了清晰表达这些proofs，我们首先要正式定义“安全”的含义，结果是，大多数密码证明依赖于目前未经证实的假设，这些假设关于某些数学问题的算法难度。
6.比起古典密码学，现代密码学更强调3个规则（principles）：定义、假设和证明（definitions, assumptions, and proofs）。
（1）Formal definitions：给出两个准确的描述：在这个范围内威胁有哪些、什么样的安全保障是被需要的。这样，definitions能够帮助引导加密方案（cryptographic schemes）的设计。在合适的definition下，我们可以研究一个被推荐的方案去看它是否完成需求保障；某些情况下，我们还可以通过展示满足definition证明一个给出的结构的安全。
一个满足更弱定义的方案可能会比满足更强定义的方案更有效。
（2）一个安全定义有两个元素：一个安全保障（从攻击者的观点来看，什么对该方案（scheme）构成成功的攻击，即scheme旨在预防攻击者的行动）；一个威胁的模型（描述敌手的能力）。
（3）威胁模型假定攻击者拥有的能力，但对敌手使用的策略没有限制，不用假定敌手是怎么使用它的能力的。
（4）威胁模型，按顺序，攻击者的能力增加：唯密文攻击、已知明文攻击、选择明文攻击、选择密文攻击。
（5）Precise Assumptions：安全证明（proofs）经常依赖于假设（assumptions）。
（6）如果被视为建筑块的基本假设，作为方案安全证明的部分是明确的，接着我们只需检查要求的假设是否被新弱点影响。
（7）Proofs and Security: 严格的证明：在某些特定的假设（assumption）下，一个构造（construction）满足给出的定义（definition）。
在说维吉尼亚加密法的破解方法之前，有必要来回顾一下它的加密原理。
维吉尼亚加密法是由26套密码组成的表，我们默认要用多套密码给原文加密的时候，具体操作中密文的每个字母由哪套密码来加密，是由钥匙规定的。钥匙最初都是一个正常的单词，原文很长，钥匙最初很短，为了让原文和钥匙一一对应，就反复使用钥匙。比如钥匙是boy，只有3个字母，我们可以boyboyboy这样一直循环下去，和原文中每个字母一一对应。
我们先来看一个例子，在这个例子里，原文是“the sun and the man in the moon”，钥匙是KING，用维吉尼亚加密法加密之后，密码文是一串看起来没什么规律的字母。我们把钥匙、原文和密文的内容依次记录下来。
原文的内容中，有3个定冠词the，变成密文后，the变成了两种样子，第一种是DPR，第二和第三种是BUK。第一个我们不管，关键点就在于——
第二个和第三个竟然加密成了相同的密文。
为什么会出现这种情况，这是巧合吗？
不是的。我们可以看钥匙单词KING，它由4个字母组成。我们再看密文中，后两个代表the的BUK，间隔了8个字母，间隔距离正好是钥匙长度的2倍。也就是说，正好在KING这个钥匙循环到整数倍的时候，如果也正好赶上出现了同样的原文，那巧合就出现了——原文就会被加密成相同的密文。
根据这个规律，我们就能确定钥匙的长度。
比如有这样一段密文：
DYDUXRMH TV NQD QN DYDUXRMH ARTJGW NQD
其中，两个 DYDUXRMH 的出现相隔了15个字母。因此，可以假定钥匙的长度是15的约数，即长度为15、5或3。而两个 NQD 则相距20个字母，意味着钥匙长度应为20、10、5、4或2。取两者的交集，则可以基本确定钥匙长度为5。
这一步，就是破解维吉尼亚加密法的关键一步。
接下来，我们已经知道钥匙的长度是5了，那就意味着在原文中第1、第6、第11、第16……，这些字母单独挑出来放在一组叫作A组。A组可是由维吉尼亚密码表中，同一行移位的字母加密得到的结果。我们再把第2、第7、第12、第17……，这些字母挑出来放在一起称作B组，它们又是用另一行移位字母加密得到的。
我们把这些按组别归纳起来：
A组：第1、第6、第11、第16……
B组：第2、第7、第12、第17……
C组：第3、第8、第13、第18……
D组：第4、第9、第14、第19……
F组：第5、第10、第15、第20……
这就相当于，将原来的密文分解成了五组新的密文，每一组都是由维尼尼亚加密法中的单独一行加密而成，也即单套密码加密。
单套密码加密怎么破解？我们之前介绍过的——频率分析法。
所以，我们来总结一下维吉尼亚加密法的步骤：
第一步，是从密文中找出拼写完全相同的字母串；
第二步，计算出钥匙的长度；
第三步，将密文分析成若干组（与钥匙长度对应）；
第四步，分别对每组密文用频率分析法破解。
在20世纪之前，人们一直以为这套方法是普鲁士少校卡西斯基在1863年发明的，所以一直以来这套破解法叫作“卡西斯基试验法”。但是后来更多的资料公布，发现剑桥大学的英国科学家巴贝奇在9年前就已经写下了解法，这位巴贝奇也是后世认为的计算机创造者之一。
发明者受委屈，这既是密码学领域的特点，又是密码学研究者躲不过的委屈。
不论是剑桥大学的巴贝奇，还是普鲁士军官卡西斯基，虽然他们破解了维吉尼亚密码法，但他们在世的时候，始终都不知道自己其实已经在密码学上引起了一场革命。
往期文章：
密码那些事儿｜（九）维吉尼亚登场
密码那些事儿｜（八）玛丽女王被密码改变的人生
密码那些事儿｜（七）以频率之矛，攻移位之盾
密码那些事儿｜（六）中外古时候的移位加密
密码那些事儿｜（五）换个位置，面目全非
密码那些事儿｜（四）隐藏的消息
密码那些事儿｜（三）“风语者”——从未被破解的密码
密码那些事儿｜（二）密码学发展的七个阶段
密码那些事儿｜（一）无所不在的密码
本人是官方授权会员推广专员，点击 会员专属通道 成为会员，您将会获得钻奖励及诸多权益！
《钻奖励调整公告》
采用替代密码算法中的维吉尼亚密码方法，密文C＝“HEADVIGENERE”,密钥K＝KEY，求明文P
将密文HEADVIGENERE用密钥替换后为KEYKEYKEYKEY
替换前:HEADVIGENERE
替换后:KEYKEYKEYKEY
解密求明文:
按替换后的内容找到第一行的K所在位置向下寻找,找到H的位置,当前行最左侧第一列对应的就为明文X
加密求密文:
按明文找到第一列对应的H,在从第一行中找到对应的密钥K,两个位置相交的值就为密文.
答案:
HEA DVI GEN ERE
KEY KEY KEY KEY
XAC TRK WAP UNG
