主题：【原创】密码传奇（一）：7、Painvin对这两份电文的分析只能就此止步了 -- 1001n
家园 【原创】密码传奇（一）：7、Painvin对这两份电文的分析只能就此止步了 呵呵，前几天的篇外历史附注估计把大家的脑袋都给活活看大了。唉，想完全理解一段历史，真是难啊……为了避免把密码故事写成第一次世界大战西线战争史（我倒￥#%），现在开始，继续讲述本章密码故事最压轴的部分。
同时，以前每篇的长度实在是太……长了，非有极强定力，真是无法一口气读完。从现在开始，二话不说，该截就截，力争让兄弟们看完一篇以后，不会再次发出“看的辛苦死了”这样的评价……呵呵，说归说，估计我这水准，还是得把大伙累个半死――咋办ni？尽量搞生动一点吧。。。
在这里，再次对等待故事结尾的众多兄弟致以诚挚的谢意，和由衷的抱歉，让大家久等了！
--------------------------------------------------------------------------
历经数万字的铺垫，我们的主人公极为牛叉的破解故事终于该闪亮登场了……
现在的时间是1918年6月1日，正是西线德军连续五次战役中的第三次战役，埃纳河战役进行到第六天的时候。
在这一天，鲁登道夫又指挥15个德军师发动了进攻。这一回，德军的前线锋芒已经越过法军阵地，直扑马恩河――现在他们离巴黎的距离，最近的地方只有不到50公里了。
还在这一天，德军升级了他们的战地密码；如前所述，ADFGX被ADFGVX所取代。德军这么做原因并非是得知自己的密码已经被破，而不过是一个希望更加保险的手段而已。
而很快我们就能看到，德军对ADFGVX实在是太自信了，以至于犯下了根本无可原谅的错误。而最后，这个错误完全毁了他们自己。
协约国这边也忙的一塌糊涂。不管军事行动了，咱们单说这破译密码的部分吧。
29岁的陆军中尉Georges Painvin从当天17时，也就是德军发起进攻后十个小时后，开始对截收到的德军密电进行密码分析。回想4月1日他的分析过程，我们可以知道：他现在急需如4月1日那两份报头和报尾相同的电报。没有这个，他的分析就无法进行――连天书般的密文都无法分段，还谈什么破解？
（注：这里看不明白的兄弟，恐怕得回头复习一下前文，也就是密码传奇（一）：5、重压之下的超一流天才破解链接出处对Painvin破解ADFGX的描述了，呵呵。不愿意看那些让人痛苦的分析过程而又要理解本篇的内容，难度确实比较大。为了照顾那些跟我一样实在不想再痛苦一次的兄弟，这里也做个提示吧：
1、找出长度相同、内容非常近似的报文；
2、对比两份电文的报头，方法是将电文报头完整列出，第一行是第一份电文，第二行是第二份；要求完全对齐；
3、找出上下两行中完全相同的字母组，并以此为指标，一段段将密文分段；
4、密文段的数量就是移位表的密钥数字长度，也就是移位表的宽度；
5、长的密文段和短的密文段，分别对应移位表的长列和短列；
6、因为移位表是从左至右书写的，所以，长密文段必然在表的左边，短密文段必然在右边；
7、每个密文段都有编号，那么对于两份密电来讲，同一编号对应的密文段，则会出现三种情况：
a：同长；
b：同短；
c：有长有短。
8、以这个标准，将密文段的编号归入三个集合；
9、以上是对报头的分析结果。对报尾进行步骤2-8的完全相同的操作，又得到三个集合；
10、将分析报头得到的三个集合和分析报尾得到的三个集合取交集，得到最多九个集合（上文中，有4个是空集，只有5个非空的集合用的上）；
11、根据以上9个集合的本来涵义，归纳出密文段编号的次序；
12、借助这个次序，将密文段一个个按顺序纵向列出；虽然很多还不能确定先后次序的密文段，但是所有密文段的大致次序都被确定了；
13、至此，移位加密被初步破解完毕；
14、使用频率分析的方法，在所有密文中寻找特定的字母组合，以确定被替换掉的原始明文字母；
15、构造原始方表，试验性填入已猜解出的字母；
16、对方表的横坐标、纵坐标分开进行分析，根据字母频率变化，确定某个编号所指代的密文段究竟是奇数列还是偶数列；
17、根据步骤12得出的结果，联系步骤16得出的结果，最终可以完全确定每个列（密文段）的具体位置。也就是，换位表被完全破解；
18、根据以上结果，对方表进行猜测性攻击；
19、完全破解方表，得出明文。
简单这么概括了一遍，感觉跟前几天写这个的时候完全一样，――还是那么累！！本注总算注解完了，唉，一个注都那么长。。。）
接着说6月1日这天Painvin对ADFGVX的破解吧。
莫非冥冥之中自有定数？就象1001n生生造出的一句俗语所说的那样，幸福的破解都是相似的，倒霉的德军各有各的倒霉――对截获的密电进行仔细端详以后，Painvin的注意力很快就集中到其中三份电文上。这三份电文有个共同特点：
都是GCI电台发出的；
电文的时间组都是00：05。
其中有两份电文，连长度都一样，是106个字母。这两份电文一份是发给DAX电台的，另一份则发给DAK电台。
老办法，Painvin把密文并列着抄下来，然后上下对比查找相同的密文段。根据对应密文呈现出有规律的相同部分，他很快就给这两份电文分好了段：一共是21组密文段。
这也就意味着：德军在ADFGVX加密的第二步，也就是移位变换加密时，使用的密钥，其长度应该是21。换言之，德军所用的移位表，应该是21行宽。
用106/21，结果是商5余1。
这个结果就又告诉Painvin：
21个密文段中，应该有（余数）个密文段比其它的密文段长；余数是1，所以，有1个密文段比其它的密文段长；
这个长密文段的长度应该是（商+1）=（5+1）=6。
而其余的20个密文段，长度应该是商本身，也就是5。
用刚才分好的段进行验证，完全无误：密文被分成了20个短密文段，和1个长密文段；短密文段的长度是5，长密文段的长度是6。作为一个休闲活动，我们不妨再把它加一下：
（短密文段个数*长度）+（长密文段*长度）=（20*5）+（1*6）=100+6=106，正好跟电文长度完全相同。看，科学或者数学，是多么地有意思啊~~
――简直是废话，要是不相同，那肯定是哪步算错了……
这个简单的算式告诉我们什么呢？
德军的移位表，长度21，高度为6；画下来也就是这个样子的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ←-密钥长度为21
X X X X X X X X X X X X X X X X X X X X X ←-┐
X X X X X X X X X X X X X X X X X X X X X │
X X X X X X X X X X X X X X X X X X X X X 短列（短密文段）长度为5
X X X X X X X X X X X X X X X X X X X X X │
X X X X X X X X X X X X X X X X X X X X X ←-┙
X
↑
┕---- 长列（长密文段）长度为6
其中，数字1代表的这一列，长度为6；其余一律为5。
到现在为止，Painvin干的不错。但是，在这两份报文上，这个不错也就到此为止了――它们实在是太像了，以至于，连差别都少的可怜；这个差别少到一定程度，Painvin就没法搞了――想想也是，如果他得到两份完全一样的密电，那不跟得到一份密电一样么？
而仅仅拿着一份密电，怎么可能去破译？！
说到这里，我对holmers兄在英雄版发的帖子开书---香烟解码法链接出处里的部分内容实在无法苟同。
帖子里说：
军校严禁学生谈恋爱，他们有辄儿，把加密的情书公开的贴在学校报栏上，真正的“我的心事只有你能懂！”内容有点长，我还是不继续引用了吧。大致给归纳一下，意思基本是这样的：
某军事院校的学生把情书写成密文，张贴出来；老教授也就是密码权威，看着看着就郁闷的要命，因为加密实在太简单了，根本不符合他的严谨风格；他已经看出，明文都是情书来了。
――这一段，我实在是难以理解：除非，这六份情书是用同一密码进行加密的，这样才有可能进行密码分析。而情书恐怕是内容各异，比较和分析都得用不少时间，怎么可能老教授在学校报栏站着看了一会就看懂了，就怒了呢？也且不说这个，或许老教授的确是真正的大牛，能够瞬间破解密码，并看懂原文吧。
――而文后接着就说：
老头儿是一封接着一封的批判。前五封一无是处，每封五分钟，骂完了事。倒是最后一封颇对老头子的脾气，结结实实的批了半个钟头。最后说还是这封多少有些气象！――如此说来，他们用的完全不是同一密码加密的；不说前五份，最后一份起码就是使用了单独的加密方式；而这，也就是密码学概念中的“一文一密”。
而“一文一密”，怎么可能被破译？毫无道理啊！
我举个例子吧：我把“密码故事其实很精彩”用拼音连续写下来，某种意义上也算是进行了密码编码：
密码故事很精彩
mimagushihenjingcai
ok,有人说，看到mimagushihenjingcai，我读都能读出来，这样不也是一文一密么？不一样能破解么？明文就是“密码故事其实很精彩”啊！
可如果我说，我这不是用拼音加密的呢？为了稍微说明白这个道理，我把密文重新整理一下：
原来的密文 mimagushihenjingcai
分段后的密文 mim agu sh ihe nj ingc ai
内容完全相同，之所以分开，只是为了下面讲述方便：）
根据现在刚刚拟定的1001n新密本，mim可以指代“我”，agu可以指代“不”，sh指代“相信”，ihe指代“这”，nj指代“个”，ingc指代“故”，ai指代“事”――可以不？从密码规则上讲，当然完全可以。于是，密文和对应的明文实际上就应该是
mim agu sh ihe nj ingc ai
我 不 相信 这 个 故 事
――跟“密码故事其实很精彩”还一样么？
如果我再次改变1001n密本，重新指定这些字母组的含义，那么明文又该是什么呢？对于只看到密文的人，他知道我在说什么么？
这件事告诉我们一个道理，硬要从一份密文进行解密，实际是可以做到的；只是这样做确实毫无意义――因为同样一份密文，可以脱出无限多种可能的明文！
而得到“无限多种的”明文，和得不到明文，难道不是一回事么？换言之，你还是不知道明文到底在说什么啊……如果各位还记得我以前用新华字典映射红楼梦的例子的话，大概就更明白一些了：
在没有任何其它信息可以利用的前提下，单一的密文，理论上讲是无解的！
――写下以上这些文字，非对holmers老兄有所不敬；只是，这样的故事，听听而已，千万不要太当真――说到底，密码不是巫术，不是拍脑瓜的东西；密码编码也好，密码分析也好，是建立在严格的科学基础上的――即便是看似随意性最大的猜测性明文攻击，那也是根据频率分析等等的结果进行的，绝对不是靠很感性的“我认为它大概就应该这样吧”来进行的。
而这，实际上又是个“该怎么样认识科学”的问题。一直以来，科学版上关于“科学是什么”，“怎么样认识科学”都有了足够深刻的讨论。我一直关注这些声音，因为的的确确，如何认识科学，是我们人类的一个非常基础的问题。有篇文摘提到了“货机崇拜式科学”，文中观点之一针见血，我以为的确扎到了痛处――对于暂时无法认识的现象，人类容易出现盲目的信仰；而这些信仰，是不是能真正经受实践的检验呢？
――科学的本质是“证伪”的。不爱吱声此说，我举双手赞同！
又扯远了――我这是咋咧？唉。。。血气太盛，非福啊非福……
-------------------------------------------------------------------------------
喘口气儿，接着说Painvin的破解吧。
上面提到，他对GCI电台发给DAX和DAK电台的密电进行了分析，初步得知了当天的移位表的轮廓。但是由于这两份密电实在太相似了，相似到了缺乏足够进行下一步分析的细节，他对这两份电文的分析只能就此止步了。
不过，刚才不是提到，GCI电台在00：05分不是发了三份电文么？实际上，这第三份电文跟刚才的两份也很相似，它是GCI电台发给DTD电台的。如果说有什么大的区别，那就是这份电文的长度不再是106，而是108了；或者说，这份电文里有108个字母。
除此之外，内容也是高度相似。
――如果把你换在Painvin当时的位置上，你会觉得这106和108有什么问题么？
反正我是没感觉出什么问题来……而实践再次证明，这Painvin绝对不是浪得虚名，他马上就联想到了一个问题。
什么问题呢？
元宝推荐：不爱吱声,
本帖一共被 2 帖 引用 (帖内工具实现)家园 严格意义上的一文一密，其实应该是一字一密， 也就是说密码长度和明文长度一样。有人要说了，密码长度和明文一样，那密码怎么传送呢？如果有办法安全的传送密码，我不如直接用那个方法传送明文了。这里面关键在一个时效性：我可以派专人护送写在纸上的密码，但有紧急消息要传回来时，就可以用电话或者无线电来发送密文而不怕被窃听。
事实上，当年苏联派往美国的间谍就用过这个方法：他们随身携带一个小本子，每页上面都是很长一串数。有电报要发送时，就先把文字翻成电报明码，再按照顺序，把密码本上的每一个数字加到明文上去形成密文。假如明文是12，32，45，66。。。密码本上是92，83，27，74。。。密文就是（只取后两位）04，15，72，40。。。
但是有一个关键的关键，就是密码本的每一页用过之后就要撕去，今后永不再用。密码本撕完了，要换一本完全不同的全新的。
这样的密码，理论上是不可能破译的
当然，这样的密码代价也极高，因为密码本不可重用，运送密码本需要极高的成本。后来苏联间谍大意了一下，违反了纪律，以为密码本重用个几次也没问题吧，结果就被美国人给破了。
后来冷战期间，美苏首脑之间的热线，也还是用的这种加密办法。
说清了这个概念之后，我不得不指出，楼主的这句话似乎是不对的：
最后一份起码就是使用了单独的加密方式；而这，也就是密码学概念中的“一文一密”。
而“一文一密”，怎么可能被破译？毫无道理啊！
只有一份秘文，不等于就不能破解。不然我要问了，我把一份密文丛中裁开，变成两份如何？
一份密文，也可能被分成了很多段，每段用相同的方法加密，这样就不符合一字一密的要求了，就有被攻破的可能了。军事学院的学生发情书，由于实际应用的困难，想来不会用到这种最高级的密码，那么所述的故事，至少在理论上，是可能发生的。
感兴趣的同学请参看http://en.wikipedia.org/wiki/One_time_pad
家园 呵呵，老兄所提的故事恐怕不能证伪“单一密文理论上无解”的结论吧：） 感谢老兄的用心思考。下面我从4个方面试着予以回答，与老兄共同探讨：）
1、
不然我要问了，我把一份密文丛中裁开，变成两份如何？呵呵，那就用ADFGX做例子，给个回答：
先生造一段密文：
AAGGGDDDFFXXXXXAAA ←毫无意义的生造密文，嘿嘿
AAGG GDDD FFXX XXXA AA ←被四四分段之后，可以看出：此时使用的移位表宽4，长列2个，长度为5；短列2个，长度为4
AAGGG DDDFF XXXXX AAA ←被五五分段之后，可以看出：此时使用的移位表宽5，长列3个，长度为4；短列1个，长度为1
那么，德军用的到底是宽度为4，高度为5的移位表呢；还是宽度为5，高度为4的移位表呢？注意，这不是简单的移位表变形，连长列和短列的数量都变了。如果看起来还不明显，我们就再三三断开一次，得到
AAG GGD DDF FXX XXX AAA ←被三三分段之后，可以看出：此时使用的移位表宽3，长列3个，长度为6，无短列
连移位表都变了，老兄还觉得能分析出正确的明文来么？
2、
但是有一个关键的关键，就是密码本的每一页用过之后就要撕去，今后永不再用。密码本撕完了，要换一本完全不同的全新的。这样的密码，理论上是不可能破译的。
其实老兄所说，在密码学概念中属于密本加密的范畴。由于密本本身几乎可以说是任意构造出来的，比如前文中举过的英国SA密，里面关于某个名词，比如ship，定义出那么多数字组合。这些数字组合有具体意义么？没有，只是任意定的。
在这样的密本加密下，老兄就是把密文剁成一千段一万段，大概也破不出来――就象让一个不懂汉语的老外来看人民日报，即便他知道起码的破解常识，比如E在英文中频率出现最高等等，即便他把这报纸上的文章切成无数截，他依然看不懂――汉语对他来说，就是密本；而这个密本，是不在乎分段分析的。
3、
一份密文，也可能被分成了很多段，每段用相同的方法加密，这样就不符合一字一密的要求了，就有被攻破的可能了。我琢磨了一下，老兄似乎是把“明文”给手误成“密文”了，因为对密文的再次加密，初步密文我们也不妨看做是明文，这和我们讨论的问题不矛盾。如此看来，老兄的意思大概是这样：
123456789 ←明文
123 456 789 ←待加密明文
用加密规则X对123，456，789分别加密，得到
ABC DEF GHI，也即 ABCDEFGHI
的确，有可能被破解。但是！请老兄注意我说的原话：
在没有任何其它信息可以利用的前提下，单一的密文，理论上讲是无解的！问题跟着就来了：当老兄拿到这份密文的时候，又没有任何提示，――那么老兄是从何得知它是被分段重复加密，进而去破解的呢？
那样一段密文的加密规则X，本身就可以是密本加密，方表加密，多表替代加密，甚至恺撒加密，ENIGMA加密……等等中的任何一种或几种的组合。光看密文，如何确定破解方法？
而一眼能看出是分段加密，那不真成神仙了
扯远了说一句，即便猜出是单一的规则X加密，密钥又何在？如果这个也能猜出来，Painvin也好，Marian Rejewski同志同志也好，何必还对ADFGX/ADFGVX、ENIGMA那么头疼呢？他们知道了这个加密方式，但在没有密钥的前提下依然无法知道密文啊――而这样的密文，又该如何被破解？光知道加密方式，帮助很大么？
还是拉回来，说单一密文的问题。
当有哪怕只是一点点信息提示的时候，单一的密文也未必保险。
这话和我前文说到的原理，应该是相辅相成并不矛盾的关系。
4、
严格意义上的一文一密，其实应该是一字一密这是老兄回帖的题目，呵呵，也引用一下。其实所谓一字一密，从多表替代的改良之后就已经是这样了，登峰造极的莫过于ENIGMA――在二战前，嘿嘿。。现在说句话实在是不敢不严格啊……
老兄在这里似乎是把两个概念混淆了。一文一密，是指一种加密方式对一份明文加密后即不再使用，保证该密文是唯一通过该加密方式加密的。
而一字一密，是指在一份明文中，针对每个字母都用不同的加密方式予以加密。广义上说，ENIGMA也好，多表替代也好，实际上就是使用了这个办法――当然，最理想的一字一密方式应该是下面例子中这个类型的：
ABCDEFG ← 明文
加密时，
A B C D E F G ←明文
↑ ↑ ↑ ↑ ↑ ↑ ↑
多表 恺撒 多义码 ADFGX
ENIGMA 多名码 密本
这个办法肯定相当保险，但是这里又涉及到前文强调过的“密码代价”的问题了。到底值得不值得？――也是个问题了。
5、总结
老兄提到的内容，实际上并没有证明我提出观点的错误，呵呵，我就只好继续坚持了。这里把上文说过的再重复一下吧：
在没有任何其它信息可以利用的前提下，单一的密文，理论上讲是无解的！
当有哪怕只是一点点信息提示的时候，单一的密文也未必保险。
6、插一句，关于军校情书的故事，呵呵，我看还是别讨论了。如有兄弟说的，大二的学生，刚刚从军事基础课脱出身来，能有什么密码功力？大概是通过他们认为是“密码”的方式进行的“加密”吧，呵呵。如果真是这样，德高望重的老教授就太亏了――实际上是被这个故事给损毁了形象啊，呵呵。。不提了，不提了。。
再次感谢老兄的探讨！
元宝推荐：ArKrXe,
家园 献花 家园 来晚了。。。把着门口看吧 花
我吐血，您这话茬留的比老萨还损啊
家园 一文一密也不是不可能被破译的。 前提是密文足够长，和加密方法足够简单。
家园 好文顶上来 很少顶这个系列的文章，只是偷偷摸摸的背后献花。
在没有任何其它信息可以利用的前提下，单一的密文，理论上讲是无解的！
- 复 好文顶上来
家园 呵呵，其实老兄对我的帮助我才是没法还呢。。也公开拍一次MP吧：） 还记得那时候一高兴，随手回了个“也说说密码”的帖子，老兄当头就给加了个精。。。怎么说呢，老兄加精无数，怕是已经忘记了那一次吧？
可就是那一次，真是给了我极大的动力，之后借着涨起来的信心，又写了个“再说说密码”，好像是这名字吧，光的一声，又是个精。。
从此就上了科学版的贼船，呵呵，下定决心写了ENIGMA，之后又查了N多资料，……总之一句话，过上了苦不堪言又乐在其中的写作生活，也才渐渐有了现在的密码传奇。。。
我也注意到过，每次老兄都是高速加精，往往发了没多久帖子就已经亮起来了――说实在的，老兄在我见过的斑竹里面，确实是很佩服的一个――我发帖子的时间，可是早在北京时间上午，晚至北京时间凌晨，什么点儿都有啊……以至于我还跟人感叹过，莫非不爱老兄是不睡觉的么？？完全想不通啊
对新人的鼓励有多么重要，我就是个例子。听闻你要渐渐引退，总觉得很遗憾――论坛风气好不好，主要就看斑竹的作为，这点我感触太深刻了。。
不知道科学版其他兄弟怎么想，至少我觉得，这个科学版从老兄所说“默默无闻”到现在的“人声鼎沸，成为西西河的特色版面之一”，固然有那么多原创高手的努力，更重要的是有个良好的氛围。而这个氛围，绝对跟斑竹的努力和引导分不开。我想各位兄弟多少都有体会，就不多说了。
说起来，我对老兄的文章也是默默地看的多，说的少，花就更少。。现在补上一朵，聊以致意！