普莱费尔(Playfair)密码.doc

普莱费尔(Playfair)密码吴师傅 19世纪之前，维热纳尔密码可以说是密码学的巅峰之作。而自从巴贝奇和卡西斯基破坏了密码学的安全性之后，密码编码学就处于一种混乱状态。编码师们一直在寻找新的密码。而20世纪初意大利人马可尼发明了无线电技术，使得安全加密的需要更为紧迫。在无线电开始普及之后，各国政府先后投入精力开始研究加密和破译技术。加上随之而来的第一次世界大战，密码学在影响了战争结果的同时，也在这段时间飞速发展。让我们一起看看这段时间的一些经典成果。普莱费尔(Playfair)密码在维热纳尔密码被破解之后，英国人查尔斯惠斯通爵士开发了这种加密法。经他的朋友普莱费尔的大力提倡后，被英国政府部门和军队采用。它在1854到1855年的克里米亚战争和1899年的布尔战争中被广泛应用，直到1915年的一战时期才被破译。普莱费尔加密法也是一种替换密码，不同的是它不仅比先前提到的维热纳尔加密法更加先进，同时它使用方便而且可以让英语字母的频率统计分析法再无用武之地。在这种方法中，字母是成对而不是单个加密的。而密钥是一个55方阵（除J以外的25个字母随机排列）。加密之前，对明文信息要稍作如下处理：用I代替J；将要加密的信息所有字母排列成字母对形式：XX XX XX XX遇到同样字母组成的字母对，在中间插入Z如果明文中字母个数是奇数，在最后补Z实际操作时，密钥是依赖一个关键词确定产生的。比如选取关键词“rainbow”，把这个词的所含字母按序写到矩阵中之后，用25个字母中余下未出现的字母按字母表顺序补全矩阵的剩余位置，如下图（当然也可以将25个字母随机排列到矩阵中，但是这样并不利于记忆与操作）。当需要加密的信息用上述规则处理后，就可以按照一套既定的规则加密：将密钥扩充成6行6列，第六行与第一行相同，第六列与第一列相同。若两个字母在密钥中位于一行（列），每个字母替换为扩充后的密钥中位于它右侧（下方）的字母。两个字母不同行不同列，则第一个字母替换成与它同行，列数与第二个字母相同的字母，第二个字母替换成与这三个字母形成矩形的字母。破译Playfair与先前所述的密码术相比，普莱费尔密码功能强大。但它并不是无懈可击，至少可以通过关键词发现法破译这种密码。这种方法是由美国军方的大弗兰克穆尔曼在一战时期开发的。他利用关键词的一些特征猜测关键词字母完成破译。穆尔曼知道关键词中每三个辅音字母很可能有两个元音字母，而关键词往往包含一些更为普通的字母。他还发现，如果密文中的某个字母大量和其他字母组合，那该字母很可能就是关键词的字母（因为关键词字母在明文中使用更频繁）。穆尔曼通过分析密文，找出这些字母，它们很可能包含了大部分关键词字母，顺着这些字母继续下去，将密钥补充完整，反复尝试，就可能找出关键词了（除非运气很好，一般情况下工作量还是很大的）。在电影国家宝藏2中，英国女王曾向美国内战中的南方同盟写过两封关于黄金城的密信，以期南方同盟获得巨额财富战胜北方政府。其中第二封信就是用普莱费尔密码加密的。主人公尼古拉斯凯奇的曾曾祖父为了保护了这个秘密，拒绝为南方同盟破译了这个密码被杀。两百年后凯奇依靠曾曾祖父留下的关键词（death）破解了这个普莱费尔密码，找到了黄金城的重要线索，最终解开了这个谜团。希尔密码普莱费尔密码特别之处在于一次加密多个字母。当密码学家了解这种加密法后，他们进一步开始尝试以三连字甚至更多字为单位的加密法。但是他们失败了，其中一个重要原因是维护三维（或以上）表是十分困难的。要成功设计这种加密法，需要引进专业的数学方法。希尔密码诞生在1929年，是以其发明人Lester S. Hill来命名的。他是纽约亨特学院的数学教授，在1929年发表一篇论文提出了这种基于联立方程的加密算法。希尔密码以每次加密m个明文字母块完成加密过程。首先需要对26个字母赋值，通常是a=0,b=1,，z=25（希尔本人采取的是随机赋值）。块中的每个字母的数值一起用于生成一组新的数值。例如，m=3，需要加密的明文块的三个字母的数值（设为p1、p2和p3）通过下面的方程组转换成密文数值C1、C2和 C3。该加密法的密钥就是矩阵举个例子，现在对矩阵赋值如下：利用这个密钥和上面的方程，明文“now”首先转换成数字：13 14 22。将这些数值代入方程解得密文数值：23 20 4。再将这些数字转换成字母后，就得到密文“xue”了。加密密钥是矩阵M，那么解密密钥就是 M -1 。这意味着要使解密可行，矩阵M必须是可逆的，因此密钥值并不能随意选取。从m=3的例子中归纳出用数学方法表达希尔密码的一般形式如下：密钥为可逆矩阵将明文分块使得每块含有n个字母（最后不足位以z不足），用n1的向量表示。例如第 i 块含有字符p1，p2，p3，pn：那么密文就由如下方程确定：希尔密码很好的防止了密文被攻击。而当密钥矩阵越大时，该加密法抗攻击能力就越强。但是用已知明文攻击法可以很容易地破译该密码。其攻击过程类似先前提到的汇编一部明文与密文的对应词典。即用已知明文和密文建立方程组，求解后寻找出密钥。其他的加密技术到这里我们完成了对历史上几种最具代表性的加密系统的介绍，然而这也并非密码史的全部经典。还有不少精妙的加密法就不在此一一详述了。比如二战时期德军使用的Enigma加密法。它属于机械化的加密方法。Enigma加密法利用电机系统实现多码变换，这种系统叫做回转轮系统。回转轮是一个圆盘，它的两面都有电子接点，每个接点代表字母表中的一个字母。回转轮内部有连接各接点的电线，这种连接方式定义了简单单码替换方式。数个这样的回转轮和一个反射器组合起来就构成了强大的Enigma加密机。然而，这个加密法最终还是被英国政府联合波兰破解了。结语密码学从最初的凯撒密码至今，走过了一个漫长的道路。计算机的超强计算能力，让上述经典的加密方法都已失效。但是先哲的思想并未