日本军队的密码破译

1943年春天，日本军队在太平洋上的处境越来越糟.为了鼓舞官兵士气，日本联合舰队司令山本五十六（Yamamoto Isoroku，1884—1943）海军大将决定到巴莱尔、肖特兰和布因视察.4月18日早晨6时，山本五十六按预定计划登上一架轰炸机，在6架战斗机的护卫下启航.令日军万万想不到的是，在此前35min，16架美国闪电式战斗机已经起飞，开始了代号为“复仇”的作战行动，目标直指山本五十六.经过一番激烈的空战，山本五十六乘坐的轰炸机机翼折裂，一头栽进热带丛林.5月21日，日本电台的一个播音员用哭声播报：山本五十六“于本年4月在前线指导全盘作战时与敌交战，在作战飞机上壮烈战死”.山本是日本海军的偶像，是日本人心目中的战神.山本的死沉重地打击了日本侵略军.这次空战胜利的关键在于，美国人及时截获并破译了日军关于山本五十六视察的密电，获悉了山本飞行的时间和地点，从而掌握了精确打击的主动权.美国总统罗斯福因此下令：击毙山本.密码破译在军事上的重要作用于此可见一斑.

密码的历史可以追溯到公元前54年，罗马共和国高卢行省长官儒略·凯撒（Julius Caesar，前100—前44）的一名爱将西塞罗，突然遭到维尔纳人的围攻，情况万分危急.凯撒派了一个高卢骑兵，送一封急信给他，为了不让信万一被敌人截住后获知自己的作战计划，这封信是用密码写的.

凯撒用的是怎样的密码呢？用现代的眼光看，凯撒只是对原始信息进行了一种相当简单的加密变换，就是将原始信息中的每一个字母，用其在字母表中所在位置后面的第三个字母代替.古罗马文字所用的字母就是我们熟知的26个英文字母.即用D代替A，用E代替B，……，用A代替X，用B代替Y，用C代替Z.这些代替规则可以表示为一张表格，如表18.1所示.

表18.1　凯撒密表

表18.1称为凯撒密表，用来代替原来字母的字母称为凯撒暗码.

使用密码进行的通信，原来意思明确的文字符号，经过加密变换后，会成为一串莫名其妙的符号.当收信者收到这样的信息时，一时也无法读懂其中所表达的真正意思.这时收信者就要按照预先约定的密码交换规则，将那些莫名其妙的符号恢复成原来的意思明确的文字，然后才能阅读.这样的密码通信，即使被第三者截获，由于他一般不会知道加密的变换规则，因此无法知道在那串符号后面所隐藏的真正意思，从而起到保密的作用.

在密码学中，我们将要传送的用通用语言明确表达的文字叫做明文，根据事先约定的规则变换成密文的过程叫做加密.收信者按照约定的变换规则将收到的密文恢复为明文的过程叫做解密.假如你已知道收到的信息是按照凯撒表编成的密码，解密工作就变得非常容易，只要将上述加密过程倒过来即可，也就是将密文中的每个字母用标准字母表中相对前移3个位置的字母代替.例如，加密后的信息

JRRG PRUQLQJ

可译为

GOOD MORNING

如果不知道密码加密的变换规则，要揭示密文中暗藏的信息是一件非常困难的事情.根据截获的敌方密文进行分析，找出密码变换规则的过程叫做破译.有一种用于密码破译的统计方法，主要是按照字母表中的字母在文本中出现的频率进行分析.

我们已经知道，根据凯撒暗码的变化规则将明文编成密文时，所有字母都经过移位改写.假设你不知道字母是被前移还是后移，以及被移动几个位置.这时存在很多种可能性，你必须一一进行检验.在找到那个关键的“移位数”，从而译出密电之前，也许你要经过几十次尝试，才能得以破译.

由于在普通书面文字的大量样本中，每个字母出现的频率总是大致相同的.因此，利用字母表中的字母在文本中的相对频率，可以比较简便地确定出每个字母被移动的位数.例如，在作品中出现的全部26个字母中，有13%是E，5%是H，0%是X.当然，这些百分比已经经过四舍五入处理.其中，“0%是X”，不应理解为字母X不可能出现，而要理解为字母X出现的频率大大低于1%，并且非常接近于0%.表18.2列出的是普通文字作品中各个字母出现的相对频率表.

表18.2　字母频率表

现在将26个字母写成水平的一行，并且用画在字母上的横杠表示其相对频率，即一道横杠表示频率为1%，两道横杠表示2%，等等.我们就可得到一幅所有字母的出现频率的分布状态图，它类似于统计中常用的直方图，可称为标准分布图（见图18.1）.

图18.1　标准字母频率分布图

为了破译经过加密处理的电文，先将26个字母从A到Z写成一行，然后采用出现一次画一横杠的方法，标出各个字母在电文中出现的频数.接着，将密码电文中的字母分布图与标准的字母分布图作对照分析，找出为了使密码电文的字母分布与标准分布相似，字母需要移动的位数.

为了便于发现密码电文与标准字母的对应关系，应掌握图18.1所示的标准字母分布图的一些特征：字母E具有最大频率，或者说字母E上的横杠是最突出的.在E左边4个位置中的字母A也具有相当大的频率.N和O是两个相邻的高频率字母.R、S和T构成一个高频率字母区，其中T的频率又是最高的.相邻的5个字母V、W、X、Y和Z构成一个低频率区.

现在来看一个具体的例子.下面是一段经过加密的电文，试用上面介绍的方法译出电文：

先用在字母上画横杠的方法作出密文的字母分布图，如图18.2所示.

图18.2　密文字母分布图

然后将这张字母分布图放在标准分布图的下面进行对照比较.为了能够更方便地看清所有26个字母的频率对应情况，可以将两张标准字母分布图连接在一起使用.通过逐步向右移动密文的分布图，直到两个分布图看上去大致相同为止.经过这样的比较分析，不难发现密文中的字母F与标准字母A相对应.于是密文字母与标准字母有如图18.3所示的对应关系.

图18.3　密文字母与标准字母的对应关系

据此，可将密文译出如下：

以上介绍的是人们早期使用的密码通信，加密方法比较简单，破译也不太困难.经过2000多年的演变，加密方法经历了一个由简单到复杂，由低级到高级的发展过程.第二次世界大战以后，伴随着密码应用的日益广泛，加密技术也越来越先进.

人们将解开密码的钥匙叫做密钥，当然是不公开的.但是，1976年，美国密码学家惠特菲尔德·迪菲（Whitfield Diffie，1944—）和马丁·赫尔曼（Martin Hellman，1945—）在论文《密码学的新方向》中提出了一个新思想：可以设计一种具有两个密钥的密码体制，其中的一个密钥，予以公开，另一个则保密.这就是所谓“公开密钥密码”，简称“公钥密码”.公开的密钥称为公开密钥，保密的密钥称为私人密钥.公开密钥体制的主要特点是，加密过程和解密过程是不对称的，加密非常容易，而解密则极其困难.即使第三者获悉密文和公开密钥也很难破译.就在该论文发表的第二年，美国的罗纳尔·里维斯特（Ronal Rivest），阿迪·沙米尔（Adi Shamir）和伦纳德·阿德勒曼（Leonard Adleman）创造了世界上第一个比较完善的公钥密码体制.后来人们用他们3人名字的首写字母称之为RSA体制.这个体制已成为现代密码学中最有影响的密码系统.这个设计的基本思想是：求两个大素数的乘积在计算上很容易，但是，欲将一个大数进行素因数分解却非常困难.

RSA密码的操作过程是：甲先任意选取两个大素数p和q，并保存好这两个数，p和q就是甲的私人密钥；然后算出p和q的乘积N，并把这个值公开，这个N就是公开密钥.假如乙要给甲发信息，可以先查到甲的公开密钥N，然后将它加入到某个函数中，将加密信息传给甲.甲在接收到乙传来的密信后，可以根据私人密钥p和q将密信解密.如果密信被第三方丙截获，因为不知道私人密钥无法译出密信.他破译密信的关键就是，通过将大数N分解素因数得到p和q.而将一个大数分解素因数是极其困难的.所谓困难，就是计算所花的时间长得不可接受，一般要几百年甚至成千上万年.

为了证明RSA密码的威力，马丁·加德纳（Martin Gardner）在《科学美国人》1977年8月号上，给读者提出了一个挑战.他公布了一篇密文和密文的公开密钥N，N是一个129位数，称为RSA-129.挑战是把这个大数进行素数分解，然后用它们将密文破译.在当时，认为要把129位数进行素数分解，需要20000年以上的时间，也就是说不可能攻破.可是，这个挑战在17年后被贝尔公司的一个拥有600人的团队攻克.

RSA-129的破译成功，意味着RSA密码系统要更好地保密，必须使用更大数量级的数.为了安全，人们建议N至少取240位.在银行转账等更加重要的场合，可让N取300位的大数.这样，即使用现代最快的计算机来进行素数分解也要花几十年，甚至几个世纪，因此是安全的.