第2章数据加密算法NEW 信息安全

1第2章数据加密算法2内容2.1数据加密概念2.2密码体制2.3密码分类2.4算法分类2.5加密算法2.6数据加密标准DES2.7密码分组操作模式2.8其它分组加密算法2.9破译时间32.1数据加密概念•明文（plaintext)：作为加密输入的原始信息•密文（ciphertext)：明文变换结果•加密算法：变换函数•密钥（key)：:参与变换的参数4•加密通信的模型Alice加密机Oscar解密机Bob密钥源安全信道XYXKK•密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。5•2.1数据加密概念•2.2密码体制•2.3密码分类•2.4算法分类•2.5加密算法•2.6数据加密标准DES•2.7密码分组操作模式•2.8其它分组加密算法•2.9破译时间62.2密码体制通常一个完整密码体制要包括如下五个要素M,C,K,E,D–M是可能明文的有限集称为明文空间–C是可能密文的有限集称为密文空间–K是一切可能密钥构成的有限集称为密钥空间–对于密钥空间的任一密钥，有一个加密算法和相应的解密算法使得ek:MC和dk:CM（分别为加密解密函数），满足,这里。Mxx(x))(edkk7一个密码体制要是实际可用的必须满足如下特性:–每一个加密函数ek和每一个解密函数dk都能有效地计算–破译者取得密文后,将不能在有效的时间内破解出密钥k或明文x–一个密码系统是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间非常大8•2.1数据加密概念•2.2密码体制•2.3密码分类•2.4算法分类•2.5加密算法•2.6数据加密标准DES•2.7密码分组操作模式•2.8其它分组加密算法•2.9破译时间92.3密码分类按发展进程分：①古典密码:基于字符替换的密码②对称密钥密码③公开密钥密码10按密钥管理的方式分为①秘密密钥算法:对称算法的加密密钥和解密密钥相同,也叫作秘密密钥算法或单密钥算法,如DES算法。②公开密钥算法:如果加密和解密的密钥不同，则称之为公开密钥算法，如RSA和DH算法。11按加密模式分：•序列密码：每次加密一位或一字节的明文，也可以称为流密码。•分组密码：将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。12•2.1数据加密概念•2.2密码体制•2.3密码分类•2.4算法分类•2.5加密算法•2.6数据加密标准DES•2.7密码分组操作模式•2.8其它分组加密算法•2.9破译时间132.4算法分类•经典密码代替密码:简单代替，多名或同音代替，多表代替，多字母或多码代替换位密码:•对称加密算法DES，AES•非对称公钥算法RSA、背包密码、McEliece密码、Rabin、椭圆曲线、EIGamalD_H14•2.1数据加密概念•2.2密码体制•2.3密码分类•2.4算法分类•2.5加密算法•2.6数据加密标准DES•2.7密码分组操作模式•2.8其它分组加密算法•2.9破译时间152.5加密算法2.5.1简单代替密码或单字母密码简单代替密码就是将明文字母表M中的每个字母用密文字母表C中的相应字母来代替。这一类密码包括移位密码、替换密码、仿射密码、乘数密码、多项式代替密码、密钥短语密码等。16移位密码：是最简单的一类代替密码，•将字母表的字母右移k个位置并对字母表长度作模运算形式为ek(m)=(k+m)(modq)；解密变换为dk(c)=(m-k)(modq)•其中，q为字母表M的长度，“m”既代表字母表M中的值，也代表其在M中的位置；“c”既代表字母表C中的值，也代表其在C中的位置。{13mod26=13;27mod26=1}•凯撒Caesar密码是对英文26个字母进行移位代替的密码，其M=C；q=26。这种密码称为凯撒密码是因为凯撒使用过k=3的这种密码，使用凯撒密码将明文M=meetmeafterthetogaparty加密为C=phhwphdiwhowkhwrjdsduwb17替换密码：对明文字母表的所有字符进行所有可能置换得到密文字母表，移位密码是替换密码算法一个特例。–设M=C=Z/(26)，K是由26个符号0，1,..,25的所有可能置换组成。任意，定义dπ(y)=-1(y)=x,π-1是π的逆置换（有的是乘法逆元）。–密钥空间K很大，|K|=26!≈4×1026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。Kπ18•乘数密码：是一种替换密码，它将每个字母乘以一个密钥k，即ek(m)=kmmodq；•其中k和q为互素的，这样字母表中的字母会产生一个复杂的剩余集合。若k和q不互素，则会有一些明文字母被加密成相同的密文字母，而且，不是所有的字母都会出现在密文字母表中。•加密函数取形式为ea(x)=ax(mod26),a∈Z/(26),要求唯一解的充要条件是gcd(a,26)=1；•该算法描述为：设M=C=Z/(26)，K={a∈Z/(26)|gcd(a,26)=1},对k=a∈K,定义ek(x)=ax(mod26)和dk(y)=a-1(y)(mod26)，x、y∈Z/(26)。aa-1modq=1a=5,a-1=21a=7,a-1=1519•例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR明文密文cipher=SUFLKX20•对于乘数密码，当且仅当a与２６互素时，加密变换才是一一映射的，因此a的选择有11种：a=3,5,7,9,11,15,17,19,21,23,25。•可能尝试的密钥只有11个。21•仿射密码：是替换密码的另一个特例，加密的形式为ek(m)=(k1m+k2)modq=cmodq；其中k1和q是互素的。22•加密函数取形式为e(x)=ax+b(mod26),a、b∈Z/(26)•要求唯一解的充要条件是gcd(a,26)=1•该算法描述为：设M=C=Z/(26)；K={(a,b)∈Z/(26)×Z/(26)|gcd(a,26)=1},k=(a,b)∈K,•定义：ek(x)=ax+b(mod26)和dk(y)=a-1(y-b)(mod26)；x,y∈Z/(26)，q=26时，可能的密钥是26*12=312个。23•例子，设k＝（7，3），注意到7-1(mod26)=15,加密函数是ek(x)=7x+3(mod26),相应的解密函数是dk(y)=15(y-3)=15y–19(mod26),易见dk(ek(x))=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod26)若加密明文：hot，首先转换字母hot成为数字7,14,19,加密：解密：242.5.2单表替换密码的破译•简单代替密码由于使用从明文到密文的单一映射，所以明文字母的单字母出现频率分布与密文中相同，可以很容易地通过使用字母频率分析法进行只有密文的攻击252.5.2单表替换密码的破译•通过字母的使用频率破译262.5.3多名或同音代替密码•与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母，同音代替密码比简单代替密码难破译得多。例A可能为3、7、15•尤其是当对字母的赋值个数与字母出现频率成比例时，这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。然而，若明文字母的其它统计信息在密文中仍很明显时，那么，同音代替密码仍然是可破译的。272.5.4多表代替密码•单字母出现频率分布与密文中相同，多表代替密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布，每个映射是简单代替密码中的一对一映射。•维吉尼亚Vigenere密码和博福特Beaufort密码均是多表代替密码的例子。•多表代替密码有多个单字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母，等所有密钥使用完后，密钥又再循环使用。维吉尼亚Vigenere密码算法如下：设密钥明文加密变换ek(m)=c1c2…cn；其中：Ci=（mi+ki）mod26；密钥k可以通过周期性地延长，反复进行以至无穷。282.5.5多字母或多码代替密码•不同于前面介绍的，代替密码都是每次加密一个明文字母，多字母代替密码将明文字符划分为长度相同的消息单元，称为明文组；•对字符块成组进行代替，这样一来使密码分析更加困难。多字母代替的优点是容易将字母的自然频度隐蔽或均匀化，从而，有利于抗击统计分析。Playfair密码Hill密码都是这一类型的密码。292.5.6换位密码•在换位密码中，明文的字母保持相同，但顺序被打乱了。•由于密文字符与明文字符相同。密文中字母的出现频率与明文中字母的出现频率相同。密码分析者可以很容易地由此进行判别。•虽然，许多现代密码也使用换位，但由于它对存储要求很大，有时，还要求消息为某个特定的长度，因而比较少用。30•2.1数据加密概念•2.2密码体制•2.3密码分类•2.4算法分类•2.5加密算法•2.6数据加密标准DES•2.7密码分组操作模式•2.8其它分组加密算法•2.9破译时间312.6数据加密标准DES(DataEncryptionStandard)•2.6.1DES的产生1973年5月15日,NBS开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的32•1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在1971~1972年研制•1975年3月17日,NBS公开了全部细节•1976年,NBS指派了两个小组进行评价•1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构•1977年1月15日,“数据加密标准”FIPSPUB46发布332.6.2DES的应用•1979年，美国银行协会批准使用。•1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（ANSI.392）。•1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1。•该标准规定每五年审查一次，计划十年后采用新标准。•最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。342.6.3分组密码的一般设计原理•分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。352.6.4两个基本设计方法Shannon称之为理想密码系统中，密文的所有统计特性都与所使用的密钥独立。•扩散（Diffusion):明文的统计结构被扩散消失到密文的长程统计特性,使得明文和密文之间的统计关系尽量复杂。•混乱(confusion)：使得密文的统计特性与密钥的取值之间的关系尽量复杂。362.6.5实现的设计原则•软件实现的要求：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用处理器的基本运算，如加法、乘法、移位等。•硬件实现的要求：加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方式上，以便采用同样的器件来实现加密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。372.6.6简化的DES•SimplifiedDES方案，简称S-DES方案。加密算法涉及五个函数：(1)初始置换IP(initialpermutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和替代的运算。(3)转换函数SW(4)复合函数fk2(5)初始置换IP的