1、第1章 传统密码第第1 1章章 传统密码传统密码1.1基本概念基本概念1.2 传统密码举例传统密码举例1.3 密码分析举例密码分析举例习题习题1实践练习实践练习1第1章 传统密码 为了经济或军事的需要，古代就出现了各种各样的加密方法。经过人类多年的研究和改进，已经取得了大量的成果。现代密码学是在借鉴与发展传统密码学的基础上诞生的。在学习现代密码学之前，了解传统密码学的基本概念和成功经验是十分必要的。本章将介绍最典型的几种传统密码算法及其破译方法。第1章 传统密码1.1基本概念基本概念1.1.1密码与密码学密码与密码学 密码是为解决信息安全而进行的编码。安全指通信系统抗御外来攻击的能力。外来攻击
2、主要有两大类：一类是以截获或窃听通信内容为目标的被动攻击，攻击者截获他人信息、窃取密码、打探隐私、偷盗机密、危害民众；另一类是以纂改或伪造信息为手段的主动攻击，攻击者冒充合法发信人，发布信息，安置黑客，散布病毒，甚至破坏通信系统。针对被动攻击，密码可以使所传输信息具有保密功能，窃听者即使截获了一些信息，也会因不懂密文而不知所云。针对主动进攻，密码应具备“认证”功能，对发信人身份、消息来源以第1章 传统密码及消息完整性等加以认证，使非法发信人不得进入系统，使虚假消息能被识别，使篡改行为得以被发现。保密和认证是密码的两大基本功能。为了军事、政治、司法等方面的需求，有时也需要破译对方的密码或者赚取对
3、方的认证，由此便出现了与“密码编码学”原理相同但目的相反的另一分支，叫做“密码分析学”。这种保密与破译的斗争如同矛与盾的关系一样，魔高一尺，道高一丈，相依相存，相克相长，促进了二者共同的发展。近年来曾多次听到某种保密系统悬赏破译，某个防火墙产品欢迎投诉，其目的就是通过不断发现问题与解决问题，增强自己的抗攻击性能。为了设计出更加安全可靠的密码系统，设计第1章 传统密码者不仅要研究出更新更强的密码技术，还要研究对手有哪些可能的攻击手段。设计以分解大数复杂性为基础的RSA密码体制时，必定要讨论分解大数的技巧；设计以离散对数复杂性为基础的密码体制时，难免要讨论离散对数的计算方法，因此，聪明的密码设计者
4、同时也应该是高明的密码分析者，二者统一于同一个目标。“密码学”则是“密码编码学”与“密码分析学”的总称。1.1.2传统密码学与现代密码学传统密码学与现代密码学 密码技术的历史源远流长。很久以前，人们为了保存或传递经济、军事、外交上的重要信息，就已经开始使用密码或类似的保密技术，发明了多种多样的加密和解密方法，其手段由手工加密发展到机械加密，直到近代的电子加密。密第1章 传统密码码技术的发展历史上，记载着不少精辟的成就，书写了丰富的经验，密码技术的成果也曾在二战中发挥了巨大作用。然而直到20世纪40年代以前，密码技术却一直是纯经验性的学问。1949年，Shannon发表了“保密系统的通信理论1”
5、，用信息论的观点对密源、密钥、密文等概念进行了数学描述，对保密系统进行了定量化的分析，才使保密学建立在科学的理论基础之上。我们把20世纪70年代以前的密码研究与应用称为传统密码学。那时，互联网、智能卡以及很多现代交互方式都还没有出现，传统密码学以研究秘密通信为目的，它关注的是怎样使所传输的信息不被第三者所窃取，发信人身份的认证问题并未引起足够的重视。第1章 传统密码 随着计算机互联网的出现与普及，一方面通信网络极大地方便了人们对信息的交换和共享，另一方面也同时给攻击者提供了更多的机会。如何更好地解决信息安全问题，已成为刻不容缓的任务。社会需求的推动与科研成果的积累，终于迎来了20世纪70年代以
6、公开密钥体制为标志的密码学大发展阶段。古老的密码学重新焕发出蓬勃的生机，成为新的热门学科。密码学作为信息安全的卫士，已走出密码学家神秘的殿堂，成为广大民众和商界关注的学科。一般认为现代密码学诞生于20世纪70年代，标志性的大事有两件2：一是1977年美国国家标准局正式公布实施了美国数据加密标准(DES)，并批准用于非机要部门和商业用途，第1章 传统密码传统密码学的神秘面纱被揭开；二是1976年11月，美国斯坦福大学电气工程系研究生W.Diffie和副教授Helman在IEEE上发表了题为“密码学新方向”的学术论文，公钥密码研究的序幕就此拉开。从此密码学以一种全新的理念和姿态迅速崛起，理论研究成
7、果频出的同时，实际应用也大踏步地走进了人们的生活。传统密码学只重视保密功能，而现代密码学除了重视保密功能之外，还对认证功能提出了多方面的要求，如发信人身份认证、信息完整性认证、不可抵赖性认证等，对于抵御主动攻击发挥了巨大的作用。数字签名是一种常见的认证手段。现代密码学还提出了公开算法的思想，开创了公开密钥体制的新思路，从而在安全观念与设计理念上明显地区别于传统密码学，第1章 传统密码独树一帜，成为当代信息安全的重要技术支柱。由于现代密码学的需要，过去某些纯数学理论的领域，如经典数论、椭圆曲线等，一下子找到了用武之地，变得火爆起来。1.1.3对称密钥与非对称密钥对称密钥与非对称密钥 就系统使用的
8、密钥来分类，有两大类密钥体制。一类是对称密钥体制，加密与解密的密钥相同，掌握加密密钥的人，必然也能解密，这种密码体制也叫做单密钥体制。另一类是非对称密钥体制，加密密钥与解密密钥是不相同的，因而可以将其中一把密钥公开，只需秘密保管另一把，这种密码体制也叫做公开密钥体制或双钥体制。传统密码系统全都属于对称密钥体制,而现代密码系统中两类密钥体制都存在。比如DES属于对称密钥体制，RSA则属于非对称密钥体制。第1章 传统密码1.1.4分组密码与序列密码分组密码与序列密码就系统加密与解密方式来分类，有分组密码与序列密码两类。分组密码是把欲加密的文本分成一些较短的段落，每次使用相同的密钥与算法处理一段，然
9、后将处理后的各个小段连接起来。解密过程也是按原来的分段一段段解译，然后再连接起来。序列密码方式则不进行分段，直接把整个文章顺序送入加密器，密钥也应当源源不断地输入加密器，加密器通常只是完成某种很简单的算法，比如模二加法。这种看似简单的一字一密加密方式已被Shannon从理论上证明是无法破译的，当然它要求的密钥是无限长的随机序列。第1章 传统密码1.1.5密码学基本术语密码学基本术语3保密通信过程的流程图如图1.1所示。保密通信的一些基本术语对于传统密码学与现代密码学都同样有用。如：明文(plaintext)：发送方(sender)未经过加密处理的信息，其内容是容易理解的。密文(cipherte
10、xt)：发送方经过加密处理后的信息，文字被改变，其内容是难以理解的。密钥(key)：发送方加密处理时所用的秘密信息。在传统密码学中，解密也使用同样的密钥。加密(encryption,encipher)：发送方把明文加工成密文的变换，即 c=Ek(m)(1-1)第1章 传统密码 解密(decryption,decipher)：接收方(receiver)把密文解译成明文的变换，即 m=Dk(c)(1-2)为了顺利进行上述保密通信过程，通信之前还必须完成以下准备工作：(1)协议(protocol)：约定通信双方的通信步骤和各个技术细节。(2)密钥交换(key exchange)：通信双方必须设法取得
11、所约定的密钥(指对称密钥)。用公共信道传输密钥是不安全的，除非利用某种专门用于传送密钥的秘密信道来传输，然而其代价可能是昂贵的，或是很不方便的。可见，密钥交换问题是传统密码体制的一大难题。第1章 传统密码图1.1保密通信的流程示意 第1章 传统密码1.2传统密码举例传统密码举例21.2.1逆序密码逆序密码设：明文为 m=Thousands of years ago,cryptography had been used to keep secrets of military operations or treasure.加密算法Ek为将原文忽略空格并不计字母大小写，每5字符一组，各组取逆序，连接
12、后得到密文：c=suohtosdnaraeyfcogasotpyrhpargbdahysuneekotdeespeeste rclimfoyratiareposnoitertroerusa 这里，k=5是密钥。第1章 传统密码1.2.2棋盘密码棋盘密码将26个字母写入55 方阵中，i和 j 占同一格，使每个字符都由一对行、列脚标表示之，如表1.1所示。例如,明文为 m=There are all kinds of encryption schemes in classic cryptography.则将原文忽略空格，用表1.1的行、列脚标编码，可写出如表1.2所示的密文。第1章 传统密码表表1
13、.1棋盘密码的字母排列棋盘密码的字母排列 第1章 传统密码表表1.2棋盘密码对明文的加密结果棋盘密码对明文的加密结果 44 23 15 42 15 11 42 15 11 31 31 25 14 33 14 43 34 21 15 33 13 42 54 35 44 24 34 33 43 13 23 15 32 15 43 24 33 13 31 11 43 43 24 13 13 42 54 35 44 34 44 34 22 42 11 35 23 54 第1章 传统密码1.2.3凯撒密码凯撒密码将26个英文字母按字母表序号025编号(有时也可以按126编号)，如表1.3所示。加密编码的
14、方法是把明文的每个字母用向后循环移动k位后的字符代替：c=Ek(m)=m+k mod 26 (1-3)移位距离k(0k26)是密钥。例如明文是：m=Julius Caesar(朱丽叶斯凯撒)则不计空格与大小写，明文各字符的序号为9 20 11 8 20 18 2 0 4 18 0 17 假设平移k=11，则变为20 31 22 19 31 29 13 11 15 29 11 28第1章 传统密码表表1.3 英文字母按字母表序号英文字母按字母表序号025编号编号 第1章 传统密码循环位移意味着：31=5 mod 26，29=3 mod 26，28=2 mod 26于是，得到平移后的序号：20 5
15、 22 19 5 3 13 11 15 3 11 2再按字母表写出，则密文为c=UFWTFDNLPDLC 更一般的方法是不仅平移而且作“仿射变换”：c=k1m+k2 mod 26 (1-4)式中，k1和k2是两个密钥，k1要求与26互素。例如，m=information对应的字母序号是：8 13 5 14 17 12 0 19 8 14 13第1章 传统密码 若选k1=7，k2=10，则变换后的数字是：14 23 19 4 25 16 10 13 14 4 23对应的密文是c=OXTEZQKNOEX 第1章 传统密码1.2.4单表置换密码单表置换密码 实际上，除了移位，还可以置换，甚至任意调换
16、，26个字母的各种排列共26!种，每指定一种调换方式，都可以写出一张与原字母表对应的置换对照表，称为单表置换。在置换表中引入密钥的方法有许多种。例如可按下述方式编制置换对照表：设密钥为University of Science and Technology，略去重复字符，得到UNIVERSTYOFCADHLG，排在置换对照表的最前面，后面顺序接上字母表中尚未出现过的字符，就构成了下面的列置换表：第1章 传统密码1.2.5多表置换多表置换维吉利亚维吉利亚(Vigenere)密码密码单表置换虽然改变了明文的模样，但密文中同一个字符总来自明文的同一字母，这样就很容易从概率分析上破译(找到概率最大的字
17、母，就可能是e变来的)。为此引入多表变换，原文中的同一字母出现在不同位置时，会变换成密文的不同字符。设密钥k是长度为n的字符串(k1k2kn)，这里kj是密码的第j个字符在字母表的序号。明文m也被分成许多长为n的小段，第i段Mi=m1m2mn；那么该段明文对应的密文Ci=c1c2cn。则有 cj=(mj+kj)mod 26 j=1，2，n (1-5)例如：密钥k=shift，其字母序号为18，7，8，5，19；密钥长度n=5。将明文m=encodealgorithm忽略空格，按n=5分段后，其字母序号是：第1章 传统密码 4,13,2,14,3；4,0,11,6,14；17,8,19,7,12
18、；则第1段5个字符分别移位18，7，8，5，19后序号变为22,20,10,19,22，即WUKTW；第2段5个字符再分别移位18，7，8，5，19后序号变为22,7,19,11,7，即WHTLH；第3段5个字符又分别移位18，7，8，5，19后序号变为9,15,1,12,5，即JPBMF。最终的密文是 c=WUKTWWHTLHJPBMF。为了容易地查到不同密钥字符的变换结果，可以列出一张“维吉利亚”方阵表，第一行26个字母按序排列。第二行是第一行左移一位的结果，B开头，字母顺序不变，直到Z，最后是A作结尾。第三行是循环左移二位 直到第26行以Z开头，后接ABXY。当密钥字符为a时，就查第一行
19、；当密钥第1章 传统密码字符为b时，就查第二行当密钥字符为z时，就查最后一行。表中的列用来查询每个明文字母应当对应什么密文字母。这种方式称为多表置换。后来，比欧福特(Beaufort)将“维吉利亚”方阵表的各行按逆序排列得到了“比欧福特方阵”，使破译更加困难。第1章 传统密码1.2.6维尔南维尔南(Vernam)加密算法加密算法 当明文、密文、密钥均为二元代码(0，1)时，维吉利亚密码就成了维尔南密码。维尔南密钥在计算机代码中得到广泛应用，其计算公式是：ci=(mi+ki)mod 2 i=1，2，3，(1-6)式中，mi、ki、ci都是0或1。密钥一般是取一个周期很长的伪随机二元码序列。加密后
20、，密钥的随机性掩盖了明文的可读性，使密文变的不可理解。为了得到较长的密钥，可以找两个不太长的密钥，各自循环着使其中一个对另一个加密，当两密钥长度互素时，可得到长度为二者之积的密钥。第1章 传统密码1.2.7普莱费厄普莱费厄(Playfair)加密算法加密算法 普莱费厄加密算法把引入密钥词组的单表密码与棋盘密码结合。例如密钥是five stars，按单表方式排序后写成55方阵：若明文为M=Play fair cipher was actually invented by wheat stone则先将明文两两分组：第1章 传统密码pl,ay,fa,Ir,ci,ph,wa,sa,ct,ua,lq,l
21、y,in,ve,nt,ed,by,wh,ea,ts,to,ne 分组时注意：(1)若分组出现两字母相同时，则在两字母之间插入一个q。(2)若总字符个数为单数，则在最后那个不配对的字母后添一个q。加密方法如下：(1)若分组m1m2在方阵同行时，密文c1c2分别是m1和m2右面的字母，其中第一列可视为第五列的右面。(2)若分组m1m2处在方阵同一列时，密文c1和c2分别是m1和m2下面的字母，第一行可视为第五行的下面。第1章 传统密码 (3)若m1m2不同行也不同列时，c1和c2是m1m2为对角的矩阵块的另两个角，并且c1与m1同行，c2与m2同行。按此加密方法，上例中分组被加密为 QK,BW,I
22、T,VA,AS,OK,IG,IC,TA,WT,QZ,KZ,AW,ES,MA,FK,KE,XG,IB,CF,RM,PI1.2.8希尔希尔(Hill)加密算法加密算法将明文中长为L的字符分组m通过线性变换k，变为密文中长为L的字符分组c。字符分组以列矢量表示：c=km mod26 (1-7)有时，字符分组以行矢量表示，此时应采用的变换式为 c=mk mod26 (1-8)第1章 传统密码例如,m=Hill，四个字母序号为7，8，11，11 4116109485105965968k若则 c=km=26 mod 23819241111874116109485105965968即 c=YTIX 第1章
23、传统密码解密可由反变换：m=k-1c mod 26 (1-9)来计算，k-1是k的逆矩阵,且作模26处理。掌握密钥的用户不难求出k-1。本例中：25222252562021181121520231k第1章 传统密码1.3密码分析举例密码分析举例以破译密码为目的的学问叫密码分析学。越来越多的事实告诉我们，密码分析是密码学不可分割的组成部分。每研制出一种新密码的同时，就应当讨论它的抗攻击性能；每当某种密码被破译的同时，也就启示密码学家发现原先密码系统的漏洞和改进方法。根据掌握数据的多少，密码分析可以分为以下几种：(1)唯密文攻击：仅掌握若干被同一密钥和同一加密算法得到的密文，想导出明文。(2)已知
24、明文攻击：不仅掌握若干密文，还知道相应的明文，想从中找到密钥,从而对任何其他同类加密的密文都能破解。第1章 传统密码 (3)选择明文攻击：不仅掌握密文，还有多个可供选择的明文。显然攻击力度更强了，或破译更容易了。下面举几个破译传统密码的例子。1.3.1对单表置换密码的分析对单表置换密码的分析 单表密码系统的漏洞在于明文中相同的字符一定对应密文中同样的字符，明文中出现概率最高的字符，必然对应于密文中出现最多的字符，因此利用自然语言文字的概率统计性质容易找到明、密文字符的对应关系。下面以两个实例来展示分析过程。对大量英语文章的统计发现，各个字母出现的概率是不相同的。对单个字母的统计结果列于表1.4
25、中(概率值为x%)。第1章 传统密码表表1.4英文文章中各个字母出现的概率英文文章中各个字母出现的概率 第1章 传统密码 【例1】已知仿射密码的密文为4FMXVEDRAPHFERBNDKRXRSREFMORUDSDKDVSHVUFEDKAPRKDLYEVLRHHRH共57字。对应的明文是什么？解解：先统计各字符(特别是高频字符)出现的频度：R(8)，D(7)，E、H、K(各5),F、S、V(各4)(1)根据出现频率大小，不妨设Re，Dt，R序号为17，D序号为3，e为4，t为19。将之代入加密的仿射方程：y=ek(x)=ax+b mod26 (1-10)第1章 传统密码326 mod19172
26、6 mod 4baba得解得196ba由于gcd(a,26)=2，表明此密码不正确(正确的a应当与26互素)。(2)重新假设Re，Et，E的序号为4，从而得1026 mod191726 mod 4baba解得53ba由于gcd(a,26)=1，因此有可能是正确的结果。第1章 传统密码 (4)由加密算法：y=3x+5 mod 26得到解密算法26mod19926mod35yyx 式中：3-1=9 mod 26(3的模逆元是9)。(5)用这个结果解译密文，看能否得到有意义的明文。结果是：algorithms are quite general definitions of arithmetic p
27、rocesses 得到了有意义的明文，表明破译正确。第1章 传统密码 【例2】已知单表加密的280字密文为2 GJXXN GGOTZ NUCOT WMOHY JTKTA MTXOB YNFGO GINUG JFNZVQHYNG NEAJF HYOTW GOTHY NAFZN FTUIN ZBNEG NLNFU TXNXU FNEJC INHYA ZGAEU TUCQG OGOTH JOHOA TCJXK HYNUV OCOHO UHCNU GHHAF NUZHY NCUTW JUWNA EHYNA FOWOT UCHNPHOGLN FQZNG FOUVC NVJHT AHNGG NTHOU C
28、GJXY OGHYN ABNTOTWGNT HNTXN AEBUF KNFYO HHGIU TJUCE AFHYN GACJH OATAE IOCOH UFQXO BYNFG如何解密以恢复明文？第1章 传统密码 解解：(1)先统计密文中各字母出现的次数：(由大到小排列)N(36),H(26),O(25),G(23),T(22),U(20),F(17),A(16),Y(14),C(13),J(12),X(9),E(7),Z(7),W(6),B(5),I(5),Q(5),V(4),K(3),L(2),M(2),P(1)英文文章中的高概率字母e、t、a、o、n、i、r、s、h和中概率字母d、l、u、
29、c、m之间的概率值有一明显的间断。由此我们大体可确定密文中出现频度较高的9个字符N、H、O、G、T、U、F、A、Y的对应范围，并且大体能肯定N就是e。(2)再来统计密文中各字符的前缀与后缀的出现频度。下表列出了密文中出现频度较高的9个字符的前后连缀关系。表格中的每组数分别表示该行、该列两字符的两种不同排序方式所出现的次数。比如N行G列交叉处的(5,4)表示NG出现5次，GN出现4次。第1章 传统密码第1章 传统密码 由这些数据推测，O、U、A可能是元音i、a、o，这是因为它们互连的可能很小；OA出现两次，OU出现一次，其他UO、UA、AO、AU均无出现，所以Oi,AO；又由OU出现一次，NU出
30、现5次，UN不出现，可猜到Ua(因ea常见ae极少，ia也是存在的)。根据n是高频辅音,且n的前面是元音的概率高达80%，现在T频度为22，前面是O.U.A的占17次，由此可判定Tn。YN出现9次,NY不出现，已经判知Ne,于是可判Yh。根据th常见而ht罕见，及HY出现10次，YH一次也没有，知Ht。高概率集中只剩下r和s尚看不出与密文前9位中剩余的F和G有何对应关系。第1章 传统密码 (3)接下来就把280个字母中已找到的159个先写出来，空出尚未找到对应关系的字母，待猜测填空(注意：大写表示密文字符，小写表示已经找到的明文字符)。由Mith猜出Mw,于是由nKnownnknown知Kk；
31、由intJition知Ju。将已判定的字母填入置换对照表中就有：之后的HJ_M已呈现出字母表的顺序，于是可猜到中间空的是Lv；而前面的rs应当是FG,后面的xy则是PQ；最前面既然Ua，可猜到Vb。第1章 传统密码 再次将猜到的字母代入密文，就得到：由suXXess 可猜出Xc，于是由XiBhers知Bp，得ciphers；还可由Eour猜Ef得four；thinW猜Wg，得thing。再次回到单表对照关系上，就知密钥词组是：NEW YORK CITY。去掉重复的Y，后面按顺序接字母表中尚未出现的字符，就是：NEW YORK CIT ABDFGHJLMPQS。最后将UVXZ循环移位到前面去，得
32、到与字母表对应的置换密钥是UVXZNEWYORKCITABDFGHJLMPQS。第1章 传统密码 (4)按此对照表，可将密文全文译出为 Success in dealing with unknown ciphers is measured by these four things in the order named,perseverance,careful methods of analysis,intuition,luck.The ability at least to read the language of the original text is very desirable but
33、 not essential.Such is the opening sentence of Parker Hitts Manual for the Solution of Military Ciphers.意思是：破译一未知密码是否成功，可由以下四个因素来衡量，按顺序为：毅力、审慎的分析方法、直观和运气。阅读原文文字的起码能力是需要的，然而不是必不可少的。这是Parker Hitt的“军事密码破译指南”一书的开场白。第1章 传统密码1.3.2对维吉利亚密码的分析对维吉利亚密码的分析2，5 维吉利亚密码属多表密码，明文相同的字符变换到密文中未必是相同的字符，只有当这两个相同字符距离等于密钥长度
34、时，它们对应的密文字符才会相同。因此分析密文中两个相同字符出现的位置,就是寻找密钥长度的关键。1.密钥长度的初步判断密钥长度的初步判断 首先统计密文中不同距离处出现相同字符的次数。例如密文是如下的280个字符：UFQUIUDWFHGLZARIHWLLWYYFSYYQATJPFKMUXSSWWCSVFAEVWWGQCMVVSWFKUTBLLGZFVITYOEIPASJWGGSJEPNSUETPTMPOPHZSFDCXEPLZQWKDWFXWTHASPWIUOVSSSFKWWLCCEZWEUEHGVGLR 第1章 传统密码LGWOFKWLUWSHEVWSWTTUARCWHWBVTGNITJRWWK
35、COYFGMILRQESKWGYHAQENDIULKDHZIQASFMPRGWRVPBUIQQDSVMPFZMVEGEEPFODJQCHZIUZZMXKZBGJOTZAXCCMUMRSSJW从头到尾考察密文中所有的符号。统计距离为1的两个相同符号出现的次数，就是数出相邻两字符相同的次数，结果是20次；统计距离为2的两个相同符号出现的次数，也就是中间只隔一个符号的两相同符号的次数，结果共出现52次。再统计距离为3的两个相同符号出现的次数，得到是32次。下表列出了两个相同字符出现在距离20以内的各种情况的次数：第1章 传统密码 可以看到，距离为2和5时，两相同符号出现的次数最多，由此可以推测，密钥
36、长度可能为2或5。但是长度为2 的密钥极少有人取，于是初步判定密钥长度为5。2.密钥长度的确认密钥长度的确认 根据初步判断，可以把密文依次按列排序，每列5个字符，构成m=5行的阵列。也就是说，把原来的序列像发扑克牌似地依次分配到5行中：UUGIWYJUWAGVUGTFGPTOFPKWPVKCUGGWHTCVTKGQGNKQPVQMVPQUKOCRFDLHYYPXCEQSTZYAGNPPDLDTWSWRELWLETWTJCMEYDDARPQPEFCZZTCS第1章 传统密码QWZWYQFSSVCWBFOSSSTHCZWHISWZHROUVUHGROISHIHSGBDFGOHZBZMSUFALFA
37、KSVWMFLVEIJUMZXQFAUSLWGLFWWAWNWTLKAUZFWUSZEDZMGAUJIHRLSTMWFWVKLIIWEEPSEWXSOFCEVLKSSRBIWPRWELIMRIVMEJIXJXMW 如果密钥长度确实是5，则若设密钥为k=k1k2k3k4k5，那么阵列的第1行应当是明文中序号为1,6,11,16的相应字符用第1位密钥k1移位加密的结果，第2行是明文中序号为2,7,12,17的相应字符用第2位密钥k2移位加密的结果 由于同一行的各个元素都是由明文字符通过相同距离的移位产生的，第1章 传统密码而这种单表加密方式的字符替换不改变原来的概率分布，因此每行仍然应当呈现出与明
38、文英语相同的统计规律。然而，如果密钥长度本不是5，却按照上述方式排成了5行的阵列，则它的同一行各个元素是由不同的移位规律的多表加密方式产生，就不具备明文英语字符的统计规律，而呈现完全随机的统计特征。完全随机排列的字符序列中，任一位置出现指定字符(比如A)的概率是 在两位置都出现该指定字符的概率是 ，261 2261所以两位置出现相同字符(不论什么字符)的概率是 0385.0261261262 而如果是英语明文序列，不同字母出现的概率是不相同的，比如A是0.0856，两指定位置同时出现 A的概 第1章 传统密码率(假设为无记忆信源)是(0.0856)2，B是 0.0139，两指定位置同时出现B的
39、概率(假设为无记忆信源)是(0.0139)2 于是两指定位置出现任意相同字母的概率是 设明文(密文)的长度为n，维吉利亚密钥长度为m。再设已统计出密文中字母A的数目为nA个，B的数目为nB个，Z的数目为nZ个，那么字母A构成的重复双A对(不论间隔多远)的数目是 ，同理B构成的重复双B对的数目是 0687.02ZAp)1(21AAnn)1(21BBnn Z构成的重复双Z对的数目是 。所有相同字母)1(21ZZnn对的数目为 。而长为n的密文中，任取两ZAnnS)1(21第1章 传统密码字符组成的对子的数目为 ，可见两位置上字母相同的概率为)1(21nnZAnnnn)1()1(1-11)IC称为重
40、合指数，表示指定序列中任意两位置上有相同字符的频度。对上述阵列每行分别计算重合指数：第一行为 0.0623，第二行为 0.0506，第三行为 0.0649，第四行为0.0617，第五行为0.0617；它们都很接近英文明文序列的统计结果 0.0687，而明显不同于完全随机序列的理论值0.0385。这就表明了各行都是单表置换所得，也就是说，m=5的判断是正确的。第1章 传统密码 3.密文的破译密文的破译 我们不妨把一、二两行合起来作为一个整体来计算重合指数：AAnnnnnnnn)1)()1)(IC(2)(1)(2)(1)(2)(1)(2)(1)式中，上角标(1)、(2)分别代表第一行和第二行，n(
41、1)+n(2)则是两行总字符数。因为(2)(1)(2)(1)2(2)2(1)(2)(1)(2)(1)2)1)(nnnnnnnnnnZA第1章 传统密码(2)(1)(2)(1)2(2)2(1)2nnnnnn式中，除 项外，其他都是常量，所以相关系数 最大，则IC最大。)2()1(nnZAnn)2()1(设第一行的密钥为k1,第二行为k2，一般k1k2。我们首先计算密文一、二两行的相关系数X12=的值，之后ZAnn)2()1(将第一行各字符按字母表顺序右移一位后再计算第一行与第二行的相关系数X12，再将第一行各字符按字母表顺序右移二位再计算第一行与第二行的相关系数X12如此作下去，这些X12中最大
42、的一个必定是右移12位，使12+k1=k2的那个，因为它使得一、二两行都变成了相同密钥k2产生的密文。第1章 传统密码 换言之，我们由X12的最大，找到了一、二两行密钥序号之差12=k2-k1。同理，由计算一、三两行的X13的最大值可找到一、三两行密钥序号之差13。同样还可找到14和15。本例的结果是12=9，13=12，14=16，15=2。进行到这一步，其实已经有了解译密文的方法：把第二行各字符按字母顺序左移9位，把第三行各字符左移12位，第四行左移16位，第五行左移2位，于是所有密钥都变得与密钥一样了。之后把这样移位处理后的5段密文重新按原来的顺序连接起来，得到：第1章 传统密码 此文中
43、所有的字符都来自同样的循环移位，只需找到这个位移值k1,问题就得到解决。对此单表密码问题，已有成熟的破译方法：统计各个字符出现的频度，不难得到，文中G(序号为6)出现最多，为36次，可以大体判定它就是e(序号为4)，因此位移值k1=6-4=2。将所有字符均按字母表顺序，移回2个字符，就得到与例1内容完全相同的译文。既然k1=2，那么就有k2=11，k3=14，k4=18和k5=4，表明密钥是“close”。第1章 传统密码 4.破译方法的简化破译方法的简化实际上，由初步判断得到密钥长度m，把密文按列排序写成m行的阵列后，分别统计出每一行(j=1,2,5)各字符出现频度分布矢量：nn,nn,nn
44、ZBAj P就可以直接与常规英文字符频率(见表1.4)矢量Q=0.0856，0.0139，0.0279，0.0378，0.1304,，0.0008进行比较判定了,即将常规英文字符频率矢量进行各种距离(i=0,1,25)的循环移位，得到26个位移矢量Qi，分别计算它们与第一行频度分布矢量的点乘积：第1章 传统密码X1Q=P1Q0,P1Q1,P1Q25式中,显然，只有当位移值等于密钥k1时，点乘积最大，由此就能得到k1。同样的，由第二行频度分布矢量与各个位移矢量点乘积的最大值可以得到k2。同理得到k3，k4，k5。知道了密钥后，对密文实施反向移位的Vigenere加密变换，就可求得明文。1.3.3
45、对对Hill密码的分析密码的分析 Hill密码是x=(x1x2xm)y=(y1y2ym)的线性变换，很难用唯密文攻击。在已知部分密文与对应明文的情况下可以用线性代数方法求出变换矩阵，即密钥。ZAiiiqpQP第1章 传统密码 【例3】已知明文=Friday=(5,17,8,3,0,24)，密文=UNJVOU=(20,13,9,21,14,20)，Hill变换矩阵为22方阵，求此变换矩阵。解解：将frUN和idJV代入变换公式c=km，有：26 mod 317852113920k26 mod 381971512921139203178521139201 k第1章 传统密码以上是否正确呢？这可由a
46、yOU来验证：26 mod 201426 mod 72 456240 38197可见结果正确。第1章 传统密码习题习题1 1.凯撒密码密钥为k=11，明文为wewillmeetatmidnight，请将其加密。2.维吉尼亚密码的密钥字为“CIPHER”，试将明文“thiscryptosystemisnotsecure”加密。3.设密钥为 ，明文为july，用希尔加密算法加密，求密文。4.假设明文是Breathtaking，使用Hill密码被加密为RUPOTENTOIFV，试分析出加密密钥矩阵(矩阵维数m未知)。5.在Alice和Bobe的保密通信中，传送的密文是Rjjy rj ts ymj x
47、fggfym bj bnqq inxhzxx ymj uqfs，如果他们采用的是恺撒密码算法，试解密其通信内容。7 3 8 11k第1章 传统密码实践练习实践练习 1 实验题目实验题目：Vigenere密文的生成与破译。实验平台实验平台：Mathematica 4.0。实验内容实验内容：编写程序将任意明文加密成Vigenere密文，然后学生之间互相交换密文后进行破译训练。实验步骤实验步骤：(1)编写Vigenere加密程序。(2)对收到的密文统计不同距离处出现相同字符的次数，初步确定密钥长度m。(3)将密文写成m列的阵列。(4)写出常规英语字符频率矢量及其各个循环移位矢量Qi。第1章 传统密码 (5)分别计算密文阵列各行字符出现频度分布矢量Pj与各个常规英语字符频率移位矢量Qi的点乘积Xji，并由各行Xji的最大值确定密钥的相应值ki。(6)用Vigenere加密程序验证破译结果。(用密钥的负值加密就是解密)
