|
独立思考是突破颜值文化的唯一出路 古哥古点 2015年11月30日 密码传奇（十二） 《分解和步进》 密码传奇（十二）分解和步进 来自古哥古点 00:00 20:40 弗兰克·罗列特（Frank Rowlett）是弗里德曼最早招揽的小组成员之一，1930年4月就加入了通信情报服务中心（SIS）的密码团队。他后来也成为承担破解紫色密码重任的核心成员。要想知道弗里德曼的这个团队有多么厉害，1933年发生的一个故事可以从侧面加以证明。那一年，美国的一位商人花了10万美元获得了一款德国密码机的专利授权。这种机器最早研制于1924年，它的发明者使用了当时密码圈最时髦的一句话来宣传自己的产品，这是一款不可能被破解的机器。美国商人为了证实发明者所言不虚，他向SIS的负责人弗里德曼提出挑战。他送来一段200个字信息的密文，想看看弗里德曼小组是否能够破译出对应的明文。弗里德曼觉得这是让自己的团队进行实战演练的一次好机会，便愉快的接受了挑战。这封密码信息送达时，首先盖上了时间戳“2月24日上午11点12分”（FEB24 AM 11:12），弗里德曼在戳记的旁边写下了一句注释：“开始工作！WFF”（Commenced work. WFF）。WFF就是破解密码机的代号。没过多久，午餐时间到了，弗里德曼继续注释道“午餐期间超时，50分钟，WFF”（Timeout during lunch period, 50 minutes. WFF）。再过了一小会，当时间来到下午2点43分，弗里德曼已经完成了最后一次注释“WFF已解决！”（SolvedWFF）。整个破解任务从开始到结束仅耗时短短的3小时31分钟。 弗里德曼团队 尽管这个小组如此能干，但是当紫色密码的迷雾从东方日本飘来时，前所未见的困难仍然接二连三的凸显出来。 在介绍弗里德曼团队具体破解紫密的方法之前，先要来说明一下紫密机器的基本构造。和恩格玛机类似，97式打字机由三个部分组成：打字键盘、插线板和步进转轮。其中插线板和步进转轮是加密的核心部件。插线板起到了直接的按键置换作用，接近于恩格玛机的连接线。当打字人员按下字母A时，在插线板的置换连接下，这个按键可能就被移动到了字母T，或者其他可能的字母处。如果只有插线板工作的话，这个时候产生的密码只相当于很原始的移位密码，根本构不成有力的安全保障。置换作用的真正意义在于，当移位操作结合到了后面的组合数量庞大的转轮操作时，转轮加密部分可能存在的实际上已经极其微弱的周期性痕迹会在很大程度上进一步被抹平，而且经过置换作用放大后的转轮组合数目已经到了天文数字，这将极大的降低统计特征被发现或者被识别到的概率。所以，置换作用虽然简单，但是没有它的增强，转轮部分的安全性也会下降很多。打个比方来说，置换作用就像一层毛玻璃，把一个目标直接放到毛玻璃下，其实不难找到它的位置，然而当你把寻找标的物的亮度降低到很低时，再覆盖上一层毛玻璃，困难程度就加大了许多。 紫密机器的键盘插线板有一个独特的特性，就是为了方便元音字母和辅音字母的区分，其插线板设计成了两个独立区，第一个区管理6个键，第二个区管理20个键。每次加密时，这两个区域是完全分开互不联系的。例如在某次配置中，第一个区被分配了六个字母C、G、L、M、O、R，那么加密时，这六个字母的置换只会发生在彼此之间。同样的，第二个区内的字母置换也不会超出另外20个字母相互替换的范围。绝不会出现第二区的字母T被置换为第一区的字母G的情况。请注意，就是这个设计，无意中成为了整个密码系统的短板，最终帮助分析人员取得了突破。 紫色密码机 紫密机器的步进式转轮部分是整个密码系统复杂性的主要来源。这里说是转轮，其实只是为了方便的类比恩格玛机的机械轮盘，因为二者在功能上是类似的。日本的97式打字机内部并没有使用机械轮盘，而是采用了步进机构组件，类似于当时的电报交换机。这种步进机组是在电力驱动下，每次前进一定的步长，多级组件配合在一处，其加密效果就接近于旋转的机械轮盘，但是它们毕竟不同，步进机组的组合不规则性更高于一次一步的轮盘结构。具体来说，6字母组区域对应的是一组6级每级25个位点的步进机组，20字母组区域对应的是一个三级步进机构，其中只有一个字母会随着步进机构而移动，所以在这个区域每经过15625个字母后才会出现重复的循环。所谓位点就是步进机构每次前行一步后的位置，25个位点意味着该机构只能取25个状态，移动25步后，机构就会返回初始位置。这类似于旋转轮盘的齿轮。 有了这些结构方面的认识，再加上此前已经介绍过的恩格玛机的工作原理。我们大概已经能够理解紫密机器是如何加密的。但问题是，没有收听我们节目的弗里德曼团队当时并不知道这些信息。当时，他们唯一能够看到的就是一些前所未见的，以五个字母为一组发送的难以理解的密电文，而他们唯一可以很快确定下来的结论就是这套密码不好破。 紫色密码机的步进机构 自从弗里德曼团队接受了破解紫密的任务以来，进展甚少，罗列特他们用了几个月的时间也仅仅是带有猜测性质的确定了一个方向，那就是紫色密码可能是红色密码的升级。幸运的是而且也很关键的是，这个猜测是正确的。这个看起来似乎也没什么了不起的判断为什么重要？因为它为密码分析人员预测密码结构和有针对性的设计具体的统计分析项目提供了重要的依据。破解红色密码时的一些线索和技巧起码可以发挥出参照作用，而不需要完全的从头做起。此外，还要多多感谢日方各个重要使馆和外交机构中的密码使用人员，要不是他们或许出于保密知识的不足，又或许出于保密意识的缺乏，经常会把同一份报文用高级别的紫密和低级别的红密分别加密发送的话，整个SIS团队也将因为没有分析资料而面临巧妇难为无米之炊的困境。由于红密已经完全被SIS所掌握，这就等于把紫密密文所对应的明文直接交给了美方。密文和明文的对照组，对于任何的破译行为而言，都是不可或缺的重要资料。就是在这些底牌的帮助下，密码团队逐渐取得了进展。 首先被弗里德曼团队察觉到的就是，紫色密码的密文似乎有着分组出现的规律，所有的字母全都可以被分解到两个独立的组，一个组内有6个字母，另一个组内有20个字母。在每份密文内，两个组的字符不会发生混合。这当然是前面所述的紫色密码机的插线板结构使然，而这恰好是突破的第一步。在每份密文中鉴定出这两个字母组的字母成员并不困难。因为两个组的字符不会混合，每个组只在组内进行字符的替换，所以6字母组的密文字符的频率其实等同于它对应的明文字符在自然文本中的统计频率。故此，可以采用尝试的方法，通过在26个子母中不断枚举可能的6字母组合，比较其自然文本下的统计频率与密文6字母组的统计频率，当二者极为接近时就可以确定出该篇密文的6字母组，自然这也就同时的确定出了较大的20字母组。有人可能会有疑惑，26个字母的6字母组合其实非常多，穷举比较的话时间上可能不允许。是这样的，但这是一个经验积累的问题。最开始分析的时候，穷举的效率一定是极低的，然而随着经验和知识的累积以及其他一些语法线索的配合，分析人员对于字母组合的特征会越来越熟悉，到了后来确定6字母组已经不再是困难的事情。由于紫密机器的密钥每天更换一次，每一天中的电报密文的6字母组通常是相同的。这就为上述的统计分析提供了足够的样本，不至于因样本过小而出现偏差。 工作人员正在破译紫色密码机 分解字母组，这一步看起来很简单，实质上却非常关键。紫密机器设计上的这个疏忽之处，让原本结合在一起的26个字符变成了6字符和20字符的两个组，这就等于把一个规模为26的集合，拆成了两个相对较小的集合，其中的一个集合的规模甚至仅仅是6这样一个很低的水平。熟悉计算机算法的人都能体会到，这种可分解性对于降低问题复杂度的巨大价值。这就让紫色密码隐藏自己指纹的防线出现了一个突破口。机械式密码并不是真正安全的完全随机系统，它本质上还是逃不出字母替换表的循环周期，只不过这个周期太长太长，在实际上就接近了随机的程度，或者说这是一种伪随机机制。为了能够机械化的实现这一机制，这种超长周期也不是直接的构造出来的，而是通过若干组件的组合产生的。恩格玛机的每个轮盘，紫密机的每个步进机组都是这样的组件。所以，这意味着，机械式密码必然都是可分解的。攻破这样的密码，从本质上来说，就是要找到超长周期的分解方式。而现在，紫密机器的短板让第一个可分解性如此迅速的浮现出来，这对于弗里德曼小组来说当然是一个巨大的进展。 短小的6字母组最容易处理，可以成为密码规则性的某种索引。弗里德曼小组首先编制了一个有头没尾的无穷字母替换表。替换表的行索引是已经确定出来的6字母组的明文字符，列索引则是所谓的键位（KeyPosition），也就是6字母组对应的步进机组的每个步长的位置。当然，编写替换表时，弗里德曼等人并不知道紫密机器的构造也不清楚步进机组的存在，他们定义的键位就是根据上述的所有的机械式密码都必然遵守的可分解性，假定出来的最低一级的那个循环组件的状态集合。但是这个集合的循环状态的数量一开始并不清楚，所以初始键位是开放式的，可以一直向下排列。分析人员根据每天截获密文的统计，把当天6个字符在不同键位上对应的密文变换字符全部填入表格中，形成了一个长长的阵列。通过观察和研究这个阵列，技术人员很快发现，这里面隐藏着很深的周期性。比如当天鉴定出来的明文六字母组是A、B、D、H、O、R，自然地在加密后的密文中它们就会对应于许多种不同的密文六字母组，这种不同是键位不一样引起的。把这些不同的密文六字母组全部填入替换表中，分析人员经过耐心细致的工作发现当把这个阵列的行反复尝试着进行不同顺序的重组时，就有可能碰巧形成这样一种表格。它的每一个字符在第1，第26，第51，第76...的位置时，会出现重复；类似的，在第2，第27，第52，第77...位置时也会出现重复。替换表格不再是开放的，而是6*25的封闭表格。很明显，这意味着替换表在最底层具有长度为25的循环周期，而这正是分析人员迫切想要的结果，它反映了该系统底层循环的周长。 有了循环替换表，下面就要寻找字母替换的路径指纹了。同一天内的电文的六字母组是固定，而且战时电报的数量巨大，只要确定了这一天起始的键位，分析人员就可以在替换表的对应行进行具体的字符个数统计。计算这个数据，是要鉴定出每个位置具体对应于六字母中的哪一个。方法还是频率比较，把6个字母的自然频率分别和实际的密文频率进行比对，便可大致断定字符的对应关系。例如某天的6字母组是A、B、D、H、O、R，经过当天的密文统计，在替换表上，第一行当中拥有最高统计数量的字符是D，第二行是最高的是H，第三行是B，第四行还是H等等。由于在实际字母表里，A、B、D、H、O、R这一组子母里O的自然频率最高，所以可以推断出O在第一键位的变化为D，第二键位是H，第三行是B，第四行是H，等等。 之后扫描整个替换表，可以发现只有第四列符合DHBH...这一排布规律，所以O就对应第四列。类似的，还可以找到其他的明文字母在加密后于各个键位行的变换序列，并根据这一序列确定出替换表中符合的列号。例如字母A还原出来的变换序列是HOOB，其与第一列符合，A就对应第一列。 每个字母都可以找到自己的对应列，这些列和列之间的跳跃就反应出机械组件的次级循环的切换关系。不过，破译人员虽然知道这一点，但是紫色密码呈现出来的这种列之间的跳跃方式却让弗里德曼小组百思不得其解，经过长时间的探测他们明白，这种跳跃方式不可能是旋转的密码轮引起的。那紫密机到底采用的是什么结构呢？后来有一天，利奥·罗森（LeoRosen）有一次在无意中看到了电报机上使用的“单向选接器”的交换机部件，他突然意识到紫密替换表的跳跃规律完全可用此类的步进机组来实现。到后来，密码小组果然用这个方法在所谓的紫色模拟机上再现了跳跃规律，使用的就是步进电机组，而他们没有想到的是，完全凭借数学规律进行的模仿却和真实的紫密机构造一般无二。 再接下来就是要确定系统的循环组件的层级到底是几层以及每层循环的切换规律。这牵涉到增广替换表与循环路径的挖掘。每一天的报文中，虽然6个字母是固定的，但不同日的密文却代表着不同的6字母组，这样把多日的电报叠加在一起，就可以形成26个字母各自存在于6字母区时对应的字母替换表。这是一个21×25的表格，叫做增广替换表。其中，由于6字母的等同关系，所以其列数是21而不是26。分析人员同样发现，在这个表格中，字母沿着行向下跳跃的切换路径是重复出现的，这条路径就反映出不同层级的循环结构之间的切换关系。这是一个重要的模式，此外还有一个关键的模式就是多表并列。把多张不同密钥下得到的增广替换表放在一起，首先利用前面所讲的第一模式确定出那些同构替换表。所谓同构替换表就是那些密钥只是在步进器的初始位置上不同，而插线板出于相同设定下的替换表。观察在这些同构替换表中可能存在的列的重复现象，分析人员发现在把这些表格适当编组排序后，每一列的跳跃也会出现固定的周期，从这里便可以分析出6字母区对应的是6级循环。至此，尽管从未见过紫密机器的庐山真面目，弗里德曼团队已经彻底搞清楚了这部机器工作的全部细节。1940年，SIS制造出八台紫密模拟机，分别送到了英国、菲律宾、夏威夷等地，这些机器在后面的战争中将起到决定性的作用。 不过日本人似乎心有不甘。当年日本外务省引进紫色密码时，曾经咨询过数学家高木贞治。这位并没有深入了解过密码学的学者只是凭借组合数目的估算就断定紫色密码的变化数目极其丰富，这是难以被攻克的。或许正是因为这样的信心，在很长一段时间以来，日本都有人坚称弗里德曼的小组一定是见过紫色密码机或者类似的恩格玛机才能仿造成功。这样的自大很快就会在后面的战争中继续带给日军严厉的惩罚。
|
|
|
