第1章 古典密码学

第1章 古典密码学 本章主要对密码学和密码 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 做一简要介绍，并给出一些简单的古典密码体制，以及对这些体制的破译方法。同时，本章对本书中要用到的各种数学知识也做了介绍。 1.1 几个简单的密码体制 密码学的基本目的是使得两个在不安全信道中通信的人，通常称为Alice和Bob，以一种使他们的敌手Oscar不能明白和理解通信内容的方式进行通信。这样的不安全信道在实际中是普遍存在的，例如电话线或计算机网络。Alice发送给Bob的信息，通常称为明文(plaintext)，例如英文单词、数据或符号。Alice使用预先商量好的密钥(key)对明文进行加密，加密过的明文称为密文(ciphertext)，Alice将密文通过信道发送给Bob。对于敌手Oscar来说，他可以窃听到信道中Alice发送的密文，但是却无法知道其所对应的明文;而对于接收者Bob，由于知道密钥，可以对密文进行解密，从而获得明文。 上述观点可用数学方式描述为定义1.1。 定义1.1 一个密码体制是满足以下条件的五元组: (,,,,)PCKED 1( 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示所有可能的明文组成的有限集。 P 2(表示所有可能的密文组成的有限集。 C 3(代表密钥空间，由所有可能的密钥组成的有限集。 K 4(对每一个，都存在一个加密 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 和相应的解密规则。并且对每对e,Ed,DK,KKK ，，满足条件:对每一个明文，均有。 e:PC,d:CP,dexx(()),x,PKKKK 定义1.1中，最关键的是性质4。它主要保证了如果使用对明文进行加密，则可使用相exK 应的对密文进行解密，从而得到明文。 dxK Alice和Bob通过下列流程使用一个特定的密码体制。首先，他们随机选择一个密钥，K,K这一步必须在安全的环境下进行，不能被敌手Oscar知道，例如，两人可在同一地点协商密钥，或者使用安全信道传输密钥。完成密钥协商后，假如Alice想通过不安全信道发送消息串给Bob，不妨设此消息串为 x,xxx12n 为正整数，，。对每一个，使用加密规则对其进行加密，是预先Kx,Pxenin,1,2,,iiK 协商好的密钥。Alice计算，。然后将密文串 yex,()1??iniKi y,yyy12n 通过信道发送给Bob。当Bob接收到密文串时，他使用解密规则对其进行解密，yyyd12nK就可得到明文串。图1.1具体描述了这一加解密过程。 xxx12n 图1.1 通信信道 显然，用来加密的加密函数必须是一个单射函数(例如，一对一映射)，否则将给解密工eK 作带来麻烦，例如，如果 yexex,,()()KK12 且，则Bob就无法判断y究竟该对应于还是。如果，即明文空间等于密文 xx,xxPC,1212空间，则具体的加密函数就是一个置换。这就是说，如果明文空间等于密文空间，则每个加 密函数仅仅是对明文空间的元素的一个重新排列(置换)。 1.1.1 移位密码 本小节介绍移位密码(Shift Cipher)，其基础是数论中的模运算。这里首先给出一些模运算的 基本定义。 定义1.2 假设a和b均为整数，m是一正整数。若m整除，则可将其表示为ba, 。式读作“a与b模m同余”，正整数m称为模数。 abm,(mod)abm,(mod) 假如用m分别除a与b，可得相应的商和余数，余数是在0与之间。即可将a与 bm,1分别表示为，，，。这样，易看出abm,(mod)aqmr,，bqmr,，0??1rm,0??1rm,112212当且仅当。我们将用记号来表示a除以m所得的余数。因此当且仅abm,(mod)rr,ammod12 当。如果用来代替a，我们就说a被模m约化了。 ambmmodmod,ammod 我们给出两个例子，计算，，因为，故。再0?3?6101mod71017143,，，101mod73, 如计算，因为，故。 (101)mod7,,,，,，1017(15)4(101)mod74,, „, m,1之间～并要求取值和a的注:许多计算机编程语言定义a mod m的取值在,m+1, 正负号相同。在此定义下～(,101)mod 7应为,3。但在这里～为了方便起见～我们要求a mod m恒为一非负值。 我们现在定义模上的算术运算:令表示集合，在其上定义两个运算， {0,1,,1}m,Zmm ，加法(+)和乘法()，其运算类似于普通的实数域上的加法和乘法，所不同的只是所得的值 是取模以后的余数。 例如，在上计算，因为，故在上。 ZZ1113，111314381615，,,，，111315，,1616以上定义的上的加法和乘法满足很多我们所熟知的运算法则，在此不加证明地列出 Zm 这些法则: 1(对加法运算封闭:对任意的，有 ZZab,,ab，,mm2(加法运算满足交换律:对任意的，有 Zab,,abba，,，m 3(加法运算满足结合律:对任意的，有 ()()abcabc，，,，，Zabc,,,m 4(0是加法单位元:对任意的，有 a,Zaaa，,，,00m 5(任何元素存在加法逆元:的逆元为，因为amamaa，,,,，,()()0 ama, 6(对乘法运算封闭:对任意的，有 ZZab,,ab,mm ，有 7(乘法运算满足交换律:对任意的Zab,,abba,m 8(乘法运算满足结合律:对任意的，有 ()()abcabc,Zabc,,,m 9(1是乘法单位元:对任意的，有 a,Zaaa，,，,11m 10.乘法和加法之间存在分配律:对任意的，有，()()()abcacbc，,，Zabc,,,m abcabac()()()，,， 性质1、性质3至性质5，说明关于其上定义的加法运算构成一个群;若再加上性 Zm 质2，则构成一个交换群(阿贝尔群)。 性质1至性质10，说明是一个环。本书后面将碰到许多别的群和环，一些常见的环 Zm 有，定义了普通加法和乘法的整数环，实数环，复数环。然而这些环均是无限环，Z 本书中我们关心的环均是一些有限环。 由于在中存在加法逆，可以在中减去一个元素。定义中为。即()modabm,ZZZab,mmm计算整数，然后对它进行模m约化。例如，为了在中计算，我们首先 Zab,1118,31用11减去18，得到，然后计算。 (7)mod3124,,,7 密码体制1.1给出了移位密码。因为英文有26个字母，故其一般定义在上。很容易验证Z26移位密码满足前面所定义的密码体制的条件，即对任意的，都有。 x,Zdexx(()),26KK密码体制1.1 移位密码 令。对，任意，定义 PCK,,,Z0??25Kxy,,Z2626 exxK()()mod26,，K 和 dyyK()()mod26,,K =3～则此密码体制通常叫作凯撒密码(Caesar Cipher)～因为它首先被儒勒?凯注:若取K 撒所使用。 使用移位密码可以用来加密普通的英文句子，但是首先必须建立英文字母和模26剩余之间的一一对应关系:如。将其列表如下: ABZ,,,0,1,,25 A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 下面给出一个实例。 例1.1 假设移位密码的密钥为K,11～明文为 wewillmeetatmidnight 首先将明文中的字母对应于其相应的整数～得到如下数字串: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 然后将每个数都与11相加～再对其和取模26运算～可得 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 最后～再将其转换为相应的字母串～即得密文 HPHTWWXPPELEXTOYTRSE 要对密文进行解密～只需执行相应的逆过程即可～Bob首先将密文转换为数字～再用每个数 减去11后取模26运算～最后将相应的数字再转换为字母可得明文。 注:以上例子中～我们使用小写字母来表示明文～而使用大写字母来表示密文～为了 提高易读性～以下我们仍然遵循这种规则。 一个实用的加密体制，应该满足某些特性才行，显然以下两点必须满足: 1(加密函数和解密函数都应该易于计算。 edKK 2(对任何敌手来说，即使他获得了密文y，也不可能由此确定出密钥或明文x。 K 第二点关于“安全”的要求，在这里有些模糊不清。在已知密文y的情形下，试图得到密钥的过程，我们称其为密码分析(后面还有详细介绍)。注意到，如果Oscar能获得密钥，KK则他解密密文y即可得明文x。因此，通过密文y计算密钥至少和通过密文y计算明文一K 样困难。 移位密码(模26)是不安全的，显然可用密钥穷尽搜索方法来破译。因为密钥空间太小，只有26种可能的情况，可以穷举所有的可能密钥，得到我们所希望的有意义的明文来。我们给出一个例子。 例1.2 设有如下密文串: JBCRCLQRWCRVNBJENBWRWN 依次试验所有可能的解密密钥～可得如下不同字母串: dd,,01 jbcrclqrwcrvnbjenbwrwn iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk fxynyhmnsynrjxfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvdyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwftojof astitchintimesavesnine 至此～已可以得出有意义的明文“a stitch in time saves nine”～相应的密钥。K,9平均来看，使用上述方法计算明文只需试验26/2,13次即可。 上面的例子表明，一个密码体制安全的必要条件是能抵抗穷尽密钥搜索攻击，普通的做法是使密钥空间必须足够大。但是，很大的密钥空间并不是保证密码体制安全的充分条件。