单表代替的缺点

第二讲古典密码何俊杰2015年3月2学习本章目的：1.学习基本的密码编制原理;2.了解早期编制密码的基本方法;3.为进一步学习现代密码的编制打下基础。3基本编码技术的分类(1)代替密码利用预先设计的代替规则,对明文逐字符或逐字符组进行代替的密码.分为单表代替和多表代替两种(2)移位密码对各字符或字符组进行位置移动的密码.(3)加减密码将明文逐字符或逐字符组与乱数相加或相减的密码.4一、移位密码：移位密码是对明文字符在不改变其原形的基础上，按密钥指示的规则，对明文字符进行位置移动的密码。换句话说，移位密码就是对明文字符的位置进行重新排列的一种密码。移位密码有时也称为易位密码、置换密码、换位密码等。5例1明文：明晨五时发起总攻移位规则：该移位规则的含义是：第1个密文字符是第5个明文字符、第2个密文字符是第4个明文字符，…。由该移位规则加密得到的密文为：发时起攻总五晨明收方可利用上述加密规则求出相应的脱密规则，它是加密变换的逆变换，即：根据该脱密规则，第1个明文字符就是第8个密文字符、第2个明文字符就是第7个密文字符，…。收方利用上述脱密规则对密文进行脱密，就可得到相应的明文“明晨五时发起总攻”。密文字符位置12345678明文字符位置54687321明文字符位置12345678密文字符位置876213546例2明文：wewillmeet移位规则：首先按五个字母为一组将明文分为wewil和lmeet两组，然后逐组执行移位变换，得到密文eliwwmtele.在脱密时，收方按照相同的移位规则：明文字符位置12345密文字符位置41532对密文进行脱密，得到相应的明文。密文字符位置12345明文字符位置23413明文字符位置12345密文字符位置415327移位密码的优点优点：明文字符的位置发生变化。移位密码打乱了明文字符之间的跟随关系，使得明文自身具有的结构规律得到了破坏。移位密码的缺点也十分明显：明文字符的形态不变。这个缺点也直接导致了移位密码的信息泄漏规律：一个密文字符的出现次数也是该字符在明文中的出现次数。利用明文的上述信息泄漏规律，在已知明文攻击的条件下很容易求出移位密码的移位规则，从而攻破移位密码。在唯密文攻击的条件下，也可利用上述信息泄漏规律实现对移位密码的破译。8对于移位密码，在很多情况下，明文甚至可由密文直接猜测出来。例如，如果密文是全1的数字，那么毫无疑问，如果它是由移位密码加密的，明文也一定是全1数字。再如：例1中，我们也很容易从密文中推测出对应的明文。9移位密码是密码发展的早期产物，许多拼音文字国家，早期的密码大多采用这种密码。目前，尽管移位密码不再单独作为加密算法使用，但移位密码有其独特的优点，因而仍然是许多密码算法中的基本密码变换。因此，掌握移位密码的优缺点，对于学习和掌握现代密码的编制方法具有重要的意义。10二、代替密码：利用预先设计的固定代替规则,对明文逐字符或逐字符组进行代替的密码.其中一个字符组称为一个代替单位（也称为一个分组），代替规则又称为代替函数、代替表或S盒。.这里代替规则又称为代替函数、代替表或S盒。它的固定性是指这个代替规则与被加密的明文字符的序号无关。即相同的明文字符组产生相同的密文字符组.11在拼音文字国家，其早期大多采用代替密码，而现代机器密码也大量采用代替密码法。广义地讲，由于所有的加密算法都是密文对明文的代替，因而都是代替密码。代替密码可分为单表代替、多表代替。其中在多表代替密码中，有一类在理论上是可以证明能够做到不可破译的。121、单表代替在单表代替中，始终使用一个代替表，即代替表是固定的，与被加密的明文字符组的序号无关。设是所有可能的明文字符组，是对应的密文字符组，:E是一个双射。再设1}{iimm是明文字符组序列，则1}{iic就是利用代替表E对明文m加密得到的密文字符组序列。其中对1i，都有)(iimEc.其中双射E称为一个代替表。13例3汉字和符号与区位码（内码）的对应关系，就可理解为一个单表代替的代替表。下图是国标GB2312-80区位编码表的部分代替关系。14其具体的编码方式是：对于每个汉字或符号，它的区位码就是将它所在行最左侧的四位数字的最低两位加上它所在列最上面的两位数字。例如，汉字“豆”和“读”的区位码分别是2225和2233。由于上述对应关系是公开的，且编码规律很强，因而它实际上是明码而不是密码。15例4以十进值数为代替单位的S盒则明文晨五点总攻先变换为区位码19314669216755601505再被加密成密文46241996849700954050:{0,1,2,,9}{0,1,2,,9}S[10]{5,4,8,2,1,0,9,7,3,6}S记作代替表为:明文数字0123456789密文数字548210973616在脱密时，收方利用预先得到的脱密用表密文数字0123456789明文数字5438109726对收到的密文46241996849700954050逐数字代替，得到明文的区位码19314669216755601505然后再利用汉字与区位码的对应关系，将它转换为明文：晨五点总攻单表代替的缺点:明文字符相同,则密文字符也相同代替密码的代替规则就是其密钥。在例4中，由于10个数字的全排列共有10！，因而由十个数字形成的单表代替的总数是10!。17•下面介绍一个历史上著名的凯撒密表。该代替密码由凯撒大帝在战争中首次使用。例.5加法密码:选定固定的正整数q和k，并将明文空间和密文空间都选定为{0,1,,1}qZq。加密变换：()()modkcEmmkq脱密变换：()()modkmDcckq在加密时，利用固定的q和k对应的加密用代替表对明文逐字符代替，得到密文；在脱密时，利用固定的q和k对应的脱密用代替表对密文逐字符代替，得到明文。1890,10mod)3()(3mmmEc加密变换为：例如：取q=10和k=3,则脱密变换为：90,10mod)3()(3cccDm此时,明文:晨五点总攻变换为区位码19314669216755601505后就被加密成密文42647992549088934838缺点:密文差=明文差10mod)(10mod)]3()3[(]10mod)3(10mod)3[(21212121mmmmmmcc19例6:Caesar密码(凯撒密码)这是一种对英文字母的典型逐字母加密的的加法密码。在上例中如果取q=26，并将明文空间和密文空间作为26个英文字母的序号（从0至25）英文字母被编码为该字母的序号英文ABCD…XYZ数字0123…232425，则相应的代替密码就是凯撒密表3()()mod26,025cEmmkm加密变换为：脱密变换为：3()()mod26,025mDcckc20例如《数字城堡》中有一组密码：HLFKZCVDLDS只需把每个字母都按字母表中的顺序依次后移一个字母即可——A变成B，B就成了C，依此类推。因此明文为：IMGLADWEMET21凯撒密码的弱点：只有26种可能:AmapstoA,B,..Z可以简单的实验每个密钥（穷密钥搜索）例如：phhwphdiwhuwkhwrjdsduwb分别取k=1,2,…,25可得22qiixqiejxivxlixsketevxcrjjyrjfkyjwymjytlfufwydskkzskglzkxznkzumgvgxzetllatlhmalyaolavnhwhyafummbuminbmzbpmbwoixizbgvnncvnjocnacqncxpjyjachwoodwokpdobdrodyqkzkbdixppexplqepcespezrlalcejyqqfyqmrfqdftqfasmbmdfkzrrgzrnsgregurgbtncneglasshasothsfhvshcuodofhmbttibtpuitgiwtidvpepgincuujcuqvjuhjxujewqfqhjodvvkdvrwkvikyvkfxrgrikpewwlewsxlwjlzwlgyshsjlqfxxmfxtymxkmaxmhztitkmrgyyngyuznylnbyniaujulnshzzohzvaozmoczojbvkvmotiaapiawbpanpdapkcwlwnpujbbqjbxcqboqebqldxmxoqvkccrkcydrcprfcrmeynyprwlddsldzesdqsgdsnfzozqsxmeetmeafterthetogaparty-nffunfbgufsuifuphbqbsuzoggvogchvgtvjgvqicrctva23例5:标准字头密码(又称密钥字密码)这是一种对英文字母的典型逐字母加密的密码,它利用一个密钥字来构造代替表。如:若选择cipher作为密钥字,则对应代替表为:明文ABCDEFGHIJKLMNOP…密文CIPHERABDFGJKLMN…24单表代替密码的安全性分析优点:明文字符的形态一般将面目全非缺点:(A)明文的位置不变;(B)明文字符相同,则密文字符也相同;从而导致:(I)若明文字符e被加密成密文字符a,则明文中e的出现次数就是密文中字符a的出现次数;(II)明文的跟随关系反映在密文之中.因此,明文字符的统计规律就完全暴露在密文字符的统计规律之中.形态变但位置不变25英文字母使用频率2627英语字母中常见的组合28单表代替的上述信息泄漏，直接导致了对单表代替密码的破译方法。在唯密文攻击条件下，由于敌手可以掌握明文字符或明文字符组的统计规律，因而可利用不同的明文字符或明文字符组的出现频次的不同，利用密文字符或密文字符组的出现频次推断出代替关系，并利用明文的文意、文字规律、格式规律等确认该代替关系。29对于加法密码，还有可被敌手利用的更多的信息泄漏规律。例如，假设1m和2m是两个明文字符，1c和2c是两个密文字符，则有121212()mod[()mod][()mod]()modccqmkqmkqmmq即明文差等于密文差，这就是加减密码的等差规律。根据这个信息泄漏，一旦我们能够猜测出一个密文字符所代替的明文字符，也就可以得到由用一个密钥k加密的其它密文字符所代替的明文字符。单表代替的上述信息泄漏都是由于一个明文字符组总是被一个固定的密文字符组代替所造成的。如果一个明文字符组能够被多个密文字符组代替，那么密文字符组的统计规律就可能变得更加均匀，从而更加安全。这就是多表代替的设计思想。302、多表代替密码单表代替还有一个明显的缺点，就是密钥与加密算法不分。知道了代替表，也就破译了单表代替密码。在多表代替密码中，代替表的使用由密钥来指示。对于设计得好的多表代替密码，在密钥保密并且使用正确的条件下，代替表的公开与否对多表代替密码的安全没有影响。31根据密钥的指示，来选择加密时使用的代替表的方法，称为多表代替密码。利用数学语言描述，多表代替密码可以描述如下：设是所有可能的明文字符组构成的集合，是对应的密文字符组全体构成的集合，:kE是一簇双射。再设1}{iikk是预先选定的密钥序列，1}{iimm是明文字符组序列，则1}{iic就是利用多表代替密码E对明文m加密得到的密文字符组序列。其中对1i，都有)(ikimEci.其中每个k对应的双射kE都称为一个单表。3210mod)()(kmmEck例7:加密变换为：但k不再是固定常数而是密钥序列：43215378432231091107加密算法：明文：晨五点总攻明文序列：19314669216755601505密钥序列：43215378432231091107密文序列：52529937648986692602若密钥序列是随机的,该密码就是绝对安全的.随机就是指序列的信号相互独立且等概分布.33可以证明，如果密钥序列是随机的，即它们相互独立且服从等概分布，则在未知密钥序列的条件下，即使知道加密变换是10mod)(kmc，该