关于破解维吉尼亚密码的问题

mathe

最近CSDN有人问到如何破解维吉尼亚密码，
关于维吉尼亚密码，大家可以参考
http://baike.baidu.com/view/270838.htm
一种非常简单的古典加密方法，所以应该是非常容易破解的。

下面我们用下面密文作为例子来分析破解的数学原理:
BZWIEZSEHPVCIEBSYHAWWYLIIGWHMILZLMHTCSXWWCWXWWJLEIWOLMBSWPXWWXSVTZPWE   
XVESXWWXPMHLPRXDLSMWSJPEQXZLHATOPVIQAYHMCYDLIPNPWSUUZVRDMEMRIZPJMTDOA   
LTFDYHSWYPCBQDLIPXCSWTSYHWIGZHYEJTKLIOSMPTQZYVHZPEZTKREXWWCIHGGFRHBAY   
IECVMSATVOSACLZMXWADFVDLSIVHKLMHIGSMQSGJSYXFEIRSLZVIXYYSZTJFWAXDWCSJS   
NXYPDWCVJDPYWPFOXLTQSEXTVSMQPDWXLTEZVIQWNEYHWZJLXKOVIPELRHLZLXLTZLHWP   
AO
我们需要试验不同密码长度的情况，不同长度可能得出不同结果，但是自然只有正确密码长度才能够得到有意义的结果。
由于实际密码长度为5，我们这里就以密码长度为5来举例。
我们每隔5个字母采样，分别得到5个不同的统计序列
BZV...
ZSC...
WEI...
IHE...
EPB...
分别统计这5个序列中26个字母的频率，比如第一个序列
总共70个字母，出现次数分别为：
4 1 0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2 7
而理想状态下A-Z的出现次数分别应该为
5.52 1.09 1.88 2.72 8.88 1.79 1.31 4.01 4.95 0.07 0.42 2.76 1.71 4.94 5.43 1.30 0.06 4.16 4.44 6.85 1.96 0.71 1.50 0.11 1.41 0.04


我们需要分别将"4 1 0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2 7"循环移位若干位然后同理想状态比较，
移位多少次后两个序列最接近，结果就是哪个，所以分别拿
4 1 0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2 7
1 0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2 7 4
0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2 7 4 1
...
7 4 1 0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2
同理想状态比较。
这里我们需要一个函数来评判两个序列的匹配程度。
统计上比较好的方法是使用$chi^2$检验方法来检测一个随机序列是否服从某个分布.
不过在使用$chi^2$检验方法需要注意的时，每一组的理论值不能太小，太小了就需要对某些数据进行合并。
比如上面各组理论值小于3的我们全部进行合并，可以得到理论分布
{A}: 5.52, {B,C,D}:5.69,{E}:8.88,{F,G,H}:7.11,{I}:4.95,{J,K,L}:3.25,{M,N}:6.65,{O}:5.43,{P,Q,R}:5.52,{S}:4.44,{T}:6.85,{U,V,W,X,Y,Z}:5.73
然后对于上面每个可能情况，分别同样分组，比如对于第三个
0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2 7 4 1
对应分组为:
0,5+2+3=10,5,0+0+3=3,3,6+1+1=8,2+0=2,3,0+4+1=5,1,5,10+1+2+7+4+1=25
然后每个值同对应理论值相减，求平方并且除以理论值再累加，得
${(5.52-0)^2}/5.52+{(5.69-10)^2}/5.69+{(8.88-5)^2}/8.88+{(7.11-3)^2}/7.11+{(4.95-3)^2}/4.95+{(3.25-8)^2}/3.25+{(6.65-2)^2}/6.65+{(5.43-3)^2}/5.43+{(5.52-5)^2}/5.52+{(4.44-1)^2}/4.44+{(6.85-5)^2}/6.85+{(5.73-25)^2}/5.73$
=92.92
上面数据总共被分成12组，数学理论说上面的计算结果应该符合(12-1)=11阶的$chi^2$分布
查$chi^2$分布表知道即使取99%的置信度，上面的和也不应该超过24.72,所以我们基本可以否决这个方案。
同样，对于所有26种可能我们一一计算，计算出来和值最小的一组就最可能是真正结果，而对于其他方案，通常应该会被$chi^2$检验所淘汰。
不过C语言标准没有提供$chi^2$分布函数，所以如果要写一个通用程序(比如自己修改置信度以后）比较麻烦。

下面我们改用极大似然估计方法来看看。
我们首先列出字母A-Z出现的频率
0.0788,0.0156,0.0268,0.0389,0.1268,0.0256,0.0187,
0.0573,0.0707,0.0010,0.0060,0.0394,0.0244,0.0706,0.0776,0.0186,0.0009,0.0594,0.0634,0.0978,0.0280,0.0102,0.0214,0.0016,0.0202,0.0006
也就是
$p_A=0.0788,p_B=0.0156,p_C=0.0268,...$
对于每种发生的实际情况，我们分别计算其概率，比如还是对第三种可能情况:
0 5 2 3 5 0 0 3 3 6 1 1 2 0 3 0 4 1 1 5 10 1 2 7 4 1
那么其概率密度就是
$p_A^0 xx p_B^5 xx p_C^2 xx ... xx p_Z^1$
极大似然估计就是采用所有方案中让上面概率密度达到最大的一种方案。
由于连乘非常不方便，我们可以对上面表达式求对数，也就是计算
$0xx log(p_A)+5xx log(p_B)+2xx log(p_C)+...+1xx log(p_Z)$
对所有的26组分别计算这些表达式，然后取表达式取值最大的一组就可以了。
或者为方便起见，注意到每个对数取值都是负数，我们对上面表达式都取相反数，然后取最后表达式最大的一组就可以了。
对于这个表达式，如果对于正确序列，我们可以注意到，其实际结果将近似于
$n*(-p_A xx log(p_A)-p_B xx log(p_B)-p_C xx log(p_C) -...-p_Z xx log(p_Z))$
也就是实际上就是序列的熵值，所以说，我们得出的结论是熵值最小的序列是正确的序列。
实际上，这个结论对于本题也可以通过数学里面的排列不等式加以证明:
也就是对于正确的序列，表达式里面使用的每项正好式$p_i xx (-log(p_i))$,而对于其他错误的序列，对应的每项是$p_i xx (-log(p_j))$,其中i和j不同。
由于-log(x)是单调减函数，所以所有的和式当中,正确的序列对应的正好是两个逆序序列乘积之和，有排序不等式知道，这个和比其他任何排列方式的和都小。
所以这里通过排列不等式，我们也能够得出，从理论上，熵值最小的那个序列最有可能是正确的序列。
不过仅仅通过这个方法，我们还无法知道这个方法得出的结果有多好，下面我们可以在计算一下这个方案的结果到底有多好。
对于正确的表达式，我们可以认为我们定义了一个函数，对于抽样明文（每隔5隔字母抽样了)中每个字母X,我们取f(X)=-log(p_X).
然后对于整个抽样明文,我们对所有字母取函数f然后累加，这个和式就是我们上面计算的表达式（极大似然估计然后取对数的结果).
对这个表达式分别计算期望值和方差，
其期望值公式为
$E=n(-p_A xx log(p_A) - p_B xx log(p_B) - ... - p_Z xx log(p_Z))$
其平方数期望值为
$S=n(p_A xx log^2(p_A)+p_B xx log^2(p_B) +... + p_z xx log^2(p_Z))$
所以标准差为:
$d=sqrt(S-E^2/n)$
对于n充分大的时候，我们可以认为上面表达式将服从正态分布(根据大数定律)
所以，如果计算结果大于E+3d,我们可以认为对应序列是正确序列的可能性小于0.1%.
在实际计算过程中，我采用了这个方法，采用3倍标准差，通常只要密文长度足够，3倍方差的方案都可以将错误的密码拒绝掉，而最终只会显示一组可能的解码方式。
通过这种方法，用程序分别计算密码长度为1,2,3,4,5,...
可以得到密码长度为5的时候能够解密出来，如下:
Potential result: Key Length 5, Password SLEEP
        JOSEPHHADADREAMANDWHENHETOLDITTOHISBROTHERSTHEYHATEDHIMALLTHEMOREHESAIDTOTHEMLISTENTOTHISDREAMIHADWEWEREBINDINGSHEAVESOFCORNOUTINTHEFIELDWHENSUDDENLYMYSHEAFROSEANDSTOODUPRIGHTWHILEYOURSHEAVESGATHEREDROUNDMINEANDBOWEDDOWNTOITHISBROTHERSSAIDTOHIMDOYOUINTENDTOREIGNOVERUSWILLYOUACTUALLYRULEUSANDTHEYHATEDHIMALLTHEMOREBECAUSEOFHISDREAMANDWHATHEHADSAID

附件中是源代码，不过CSDN中遇到问题的朋友估计都是作业题，所以我觉得他们应该在学会理论方法以后自己加以实现而不是在没有懂得原理的情况下直接使用别人的代码。
所以我对下载源代码做了很大的限制：需要阅读权限20（我不知道这个代表什么）以及20枚金币
decodev.zip (1.71 KB, 下载次数: 13, 售价: 10 枚金币)

2008-2-25 09:20 上传

点击文件名下载附件
源代码
阅读权限: 20

gxqcn

原帖由 mathe 于 2008-2-25 09:13 发表
... 附件中是源代码，不过CSDN中遇到问题的朋友估计都是作业题，所以我觉得他们应该在学会理论方法以后自己加以实现而不是在没有懂得原理的情况下直接使用别人的代码。
所以我对下载源代码做了很大的限制：需要阅读权限20（我不知道这个代表什么）以及20枚金币 ...

本论坛用户组与阅读权限对照表：

游客　　　　1
禁止发言　　2
待转正会员　5
新手上路　　10
注册会员　　20
中级会员　　30
高级会员　　50
金牌会员　　80
论坛元老　　100
天使保护组　120
版主　　　　150
超级版主　　200
管理员　　　255

阅读权限主要与图片相关：比如设定阅读权限大于1，则游客将无法直接浏览上传的图片。
当然其它类型附件也有关，达不到权限标准的将没有下载权限。

gxqcn

如果想迅速提升等级，可以

• 多发有质量的帖子，一则可以通过发帖本身累积积分，二则可以得到其它会员的评分奖励；
  
• 邀请朋友注册。见：http://bbs.emath.ac.cn/invite.php，成功后，受邀人+1金币；邀请人+5金币，并自动成为被邀请人的“好友”；
  
• 会员推广。如果大家认同这里，可以推荐给自己的朋友圈，见：http://bbs.emath.ac.cn/my.php?item=promotion，里面直接写明了奖励规则。
  
• 通过社区银行贷款（需要审批），但要记得及时还贷哦

troy

我是注册会员吗？

mathe

应该是呀，你的阅读权限我查看了一下，正好是20，应该没有问题呀

gxqcn

原帖由 troy 于 2008-2-25 11:38 发表
我是注册会员吗？

点我的权限即可查阅。

数学研发论坛的用户组与积分对应关系（未包含系统用户组和特殊用户组）如下图：
　　

用户组与积分对应关系

dobear

晕，每页只有５楼？

gxqcn

原帖由 dobear 于 2008-2-25 12:49 发表
晕，每页只有５楼？

因为本论坛是定位于数学和算法的专业论坛，一个帖子要表达清楚需要一定的篇幅，
况且还涉及到数学公式等的解析，每页楼层少点可以加快页面显示。凡事均有利弊吧。。。

admin:2008-03-19 修改每页楼层数为 10

lmax

如果大家真的是搞学术的话，就不要搞这么多的限制啦。。。

看个代码都这么麻烦。。。。

gxqcn

各个论坛有各个论坛的管理方式，请尊重所在论坛的各项规定。
相对其它论坛，本论坛对游客及会员的权限已算相当宽松的了。

注意到楼上刚才另外连续注册了5个马甲，并滥用“评分”项给自己加分，这无论在哪儿都是让人鄙视的（已对马甲“禁止发言”）。
念及初犯，不作警告处理；同时仅将你的几个恶意回帖删除而已，请好自为之。