1、122.1数据加密概念2.2密码体制2.3密码分类2.4算法分类2.5加密算法2.6数据加密标准DES2.7密码分组操作模式2.8其它分组加密算法2.9破译时间3 明文（plain text)：作为加密输入的原始信息 密文（ciphertext)：明文变换结果 加密算法：变换函数 密钥（key)：:参与变换的参数4 加密通信的模型 密码学的目的：Alice和Bob两个人在不安全的信道上进行通信，而破译者Oscar不能理解他们通信的内容。5 2.1数据加密概念 2.2密码体制 2.3密码分类 2.4算法分类 2.5加密算法 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法
2、 2.9破译时间6 通常一个完整密码体制要包括如下五个要素M,C,K,E,DM是可能明文的有限集称为明文空间C是可能密文的有限集称为密文空间K是一切可能密钥构成的有限集称为密钥空间对于密钥空间的任一密钥，有一个加密算法和相应的解密算法使得ek:MC 和dk:CM（分别为加密解密函数），满足 ,这里 。M x x(x)(edkk7 一个密码体制要是实际可用的必须满足如下特性:每一个加密函数ek和每一个解密函数dk都能有效地计算破译者取得密文后,将不能在有效的时间内破解出密钥k或明文x一个密码系统是安全的必要条件穷举密钥搜索将是不可行的，即密钥空间非常大8 2.1数据加密概念 2.2密码体制 2.
3、3密码分类 2.4算法分类 2.5加密算法 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法 2.9破译时间9按发展进程分：古典密码古典密码:基于字符替换的密码 对称密钥密码对称密钥密码 公开密钥密码公开密钥密码 10按密钥管理的方式分为 秘密密钥算法:对称算法对称算法的加密密钥和解密密钥相同,也叫作秘密密钥算法或单密钥算法,如DES算法。公开密钥算法:如果加密和解密的密钥不同，则称之为公开密钥算法，如RSA和DH算法。11按加密模式分：序列密码：序列密码：每次加密一位或一字节的明文，也可以称为流密码。流密码。分组密码：分组密码：将明文分成固定长度的组，用同一密钥和算法
4、对每一块加密，输出也是固定长度的密文。12 2.1数据加密概念 2.2密码体制 2.3密码分类 2.4算法分类 2.5加密算法 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法 2.9破译时间13 经典密码 代替密码:简单代替，多名或同音代替，多表代替，多字母或多码代替 换位密码:对称加密算法 DES，AES 非对称公钥算法 RSA、背包密码、McEliece密码、Rabin、椭圆曲线、EIGamal D_H14 2.1数据加密概念 2.2密码体制 2.3密码分类 2.4算法分类 2.5加密算法 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法
5、2.9破译时间152.5.1简单代替密码或单字母密码简单代替密码或单字母密码 简单代替密码就是将明文字母表简单代替密码就是将明文字母表M中的每个字母用密文字母表中的每个字母用密文字母表C中的相应字中的相应字母来代替。这一类密码包括移位密码、替母来代替。这一类密码包括移位密码、替换密码、仿射密码、乘数密码、多项式代换密码、仿射密码、乘数密码、多项式代替密码、密钥短语密码等。替密码、密钥短语密码等。16移位密码：是最简单的一类代替密码，将字母表的字母右移k个位置并对字母表长度作模运算形式为 ek(m)=(k+m)(mod q)；解密变换为 dk(c)=(m-k)(mod q)其中，q为字母表M的长
6、度，“m”既代表字母表M中的值，也代表其在M中的位置；“c”既代表字母表C中的值，也代表其在C中的位置。13 mod 26=13;27 mod 26=1 凯撒Caesar 密码是对英文26个字母进行移位代替的密码，其M=C；q=26。这种密码称为凯撒密码是因为凯撒使用过k=3的这种密码，使用凯撒密码将明文M=meet me after the toga party 加密为C=phhw ph diwho wkh wrjd sduwb 17替换密码：对明文字母表的所有字符进行所有可能置换得到密文字母表，移位密码是替换密码算法一个特例。设M=C=Z/(26)，K是由26个符号0，1,.,25的所有可
7、能置换组成。任意 ，定义d(y)=-1(y)=x,-1是的逆置换（有的是乘法逆元）。密钥空间K很大，|K|=26!41026，破译者穷举搜索是不行的，然而，可由统计的方式破译它。移位密码体制是替换密码体制的一个特例，它仅含26个置换做为密钥空间。K 18 乘数密码：是一种替换密码，它将每个字母乘以一个密钥k，即ek(m)=km mod q；其中k和q为互素的，这样字母表中的字母会产生一个复杂的剩余集合。若k和q不互素，则会有一些明文字母被加密成相同的密文字母，而且，不是所有的字母都会出现在密文字母表中。加密函数取形式为ea(x)=ax(mod 26),aZ/(26),要求唯一解的充要条件是gc
8、d(a,26)=1；该算法描述为：设M=C=Z/(26)，K=aZ/(26)|gcd(a,26)=1,对k=aK,定义ek(x)=ax(mod 26)和dk(y)=a-1(y)(mod 26)，x、yZ/(26)。aa-1 mod q=1a=5,a-1=21a=7,a-1=15 19 例子:a=9,ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR明文密文cipher=SUFLKX20 对于乘数密码，当且仅当a与互素时，加密变换才是一一映射的，因此a的选择有11种：a=3,5,7,9,11,15,17,19,21,23,25。可能尝试的密钥
9、只有11个。21 仿射密码：是替换密码的另一个特例，加密的形式为 ek(m)=(k1m+k2)mod q=c mod q；其中k1和q是互素的。22 加密函数取形式为 e(x)=ax+b(mod 26),a、bZ/(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(mod 26)和dk(y)=a-1(y-b)(mod 26)；x,y Z/(26)，q=26时，可能的密钥是26*12=312个。23 例子，设k（7，3），注意到7-1(mod 26
10、)=15,加密函数是ek(x)=7x+3(mod 26),相应的解密函数是dk(y)=15(y-3)=15y 19(mod 26),易见 dk(ek(x)=dk(7x+3)=15(7x+3)-19=x+45-19=x(mod 26)若加密明文：hot，首先转换字母hot成为数字7,14,19,加密：解密：24 简单代替密码由于使用从明文到密文的单一映射，所以明文字母的单字母出现频率分布与密文中相同，可以很容易地通过使用字母频率分析法进行只有密文的攻击25 通过字母的使用频率破译26 与简单代替密码类似，只是映射是一对多的，每个明文字母可以加密成多个密文字母，同音代替密码比简单代替密码难破译得多
11、。例 A 可能为3、7、15 尤其是当对字母的赋值个数与字母出现频率成比例时，这是因为密文符号的相关分布会近似于平的，可以挫败频率分析。然而，若明文字母的其它统计信息在密文中仍很明显时，那么，同音代替密码仍然是可破译的。27 单字母出现频率分布与密文中相同，多表代替密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布，每个映射是简单代替密码中的一对一映射。维吉尼亚Vigenere 密码和博福特Beaufort 密码均是多表代替密码的例子。多表代替密码有多个单字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母，等所有密钥使用完后
12、，密钥又再循环使用。维吉尼亚Vigenere 密码算法如下：设密钥明文加密变换ek(m)=c1c2cn；其中：Ci=（mi+ki）mod 26；密钥k可以通过周期性地延长，反复进行以至无穷。28 不同于前面介绍的，代替密码都是每次加密一个明文字母，多字母代替密码将明文字符划分为长度相同的消息单元，称为明文组；对字符块成组进行代替，这样一来使密码分析更加困难。多字母代替的优点是容易将字母的自然频度隐蔽或均匀化，从而，有利于抗击统计分析。Playfair密码Hill密码都是这一类型的密码。29 在换位密码中，明文的字母保持相同，但顺序被打乱了。由于密文字符与明文字符相同。密文中字母的出现频率与明文
13、中字母的出现频率相同。密码分析者可以很容易地由此进行判别。虽然，许多现代密码也使用换位，但由于它对存储要求很大，有时，还要求消息为某个特定的长度，因而比较少用。30 2.1数据加密概念 2.2密码体制 2.3密码分类 2.4算法分类 2.5加密算法 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法 2.9破译时间312.6.1 DES的产生的产生 1973年年5月月15日日,NBS开始公开征集标准加开始公开征集标准加密算法密算法,并公布了它的设计要求并公布了它的设计要求:(1)算法必须提供高度的安全性算法必须提供高度的安全性(2)算法必须有详细的说明算法必须有详细的说明
14、,并易于理解并易于理解(3)算法的安全性取决于密钥算法的安全性取决于密钥,不依赖于算法不依赖于算法(4)算法适用于所有用户算法适用于所有用户(5)算法适用于不同应用场合算法适用于不同应用场合(6)算法必须高效、经济算法必须高效、经济(7)算法必须能被证实有效算法必须能被证实有效(8)算法必须是可出口的算法必须是可出口的32 1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在19711972年研制 1975年3月17日,NBS公开了全部细节 1976年,NBS指派了两个小组进行评价 1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种
15、政府机构 1977年1月15日,“数据加密标准”FIPS PUB 46 发布33 1979年，美国银行协会批准使用。1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（ANSI.392）。1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1。该标准规定每五年审查一次，计划十年后采用新标准。最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。34 分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序
16、列。35 Shannon称之为理想密码系统中，密文的所有统计特性都与所使用的密钥独立。扩散（Diffusion):明文的统计结构被扩散消失到密文的长程统计特性,使得明文和密文之间的统计关系尽量复杂。混乱(confusion)：使得密文的统计特性与密钥的取值之间的关系尽量复杂。36 软件实现的要求：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等。应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算。最好是用处理器的基本运算，如加法、乘法、移位等。硬件实现的要求：加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方
17、式上，以便采用同样的器件来实现加密和解密，以节省费用和体积。尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现。37 Simplified DES方案，简称S-DES方案。加密算法涉及五个函数：(1)初始置换IP(initial permutation)(2)复合函数fk1，它是由密钥K确定的，具有置换和替代的运算。(3)转换函数SW (4)复合函数fk2 (5)初始置换IP的逆置换IP-1(6)置换函数P8、P1038 算法如下：39 加密算法的数学表示：IP-1*fk2*SW*fk1*IP；也可写为：密文=IP-1（fk2(SW(fk1(IP(明文)其中 K1=P8(移位(P10
18、(密钥K)K2=P8(移位(移位(P10(密钥K)解密算法的数学表示：明文=IP-1（fk1(SW(fk2(IP(密文)40（1）S-DES的密钥生成：设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10),置换P10是这样定义的 P10(k1,k10)=(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6)相当于P10=（3 5 2 7 4 10 1 9 8 6）LS-1为循环左移一次，P8=(6 3 7 4 8 5 10 9)41 算法如下图 按照上述条件,若K选为(1010000010),产生的两个子密钥分别为 K1=(1 0 1 0 0 1 0
19、0)，K2=(0 1 0 0 0 0 1 1)42（2）S-DES的加密运算:初始置换用IP函数:IP=末端算法的置换为IP的逆置换:IP-1=易见IP-1(IP(X)=X。43简化的得DES方案加密细节如右图44（3）函数）函数fk，是加密方案中的最重要部分，它可，是加密方案中的最重要部分，它可表示为：表示为：fk(L,R)=(L F(R,SK),R)；其中其中L、R为为8位输入的左右各位输入的左右各4位位,，F为从为从4位集到位集到4位集的一个映射位集的一个映射,并不要求是并不要求是1-1的。的。SK为子密钥。对映射为子密钥。对映射F来说：首先输入是一来说：首先输入是一个个4位数（位数（n
20、1,n2,n3,n4），第一步运算是扩张），第一步运算是扩张/置换（置换（E/P）运算：）运算：E/P=(4 1 2 3 2 3 4 1)45E/P=(4 1 2 3 2 3 4 1)事实上，它的直观表现形式为：事实上，它的直观表现形式为：46 8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后,与E/P的结果作异或运算得：47 把它们重记为8位：48 上述第一行的4位输入进S盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2位的输出。两个S盒按如下定义：49S盒按下述规则运算：将第1和第4的输入比特做为2 bit数，指示为S盒的一个行；
21、将第2和第3的输入比特做为S盒的一个列。如此确定为S盒矩阵的（i,j）数。例如：（P0,0,P0,3）=(0 0)，并且(P0,1,P0,2)=(1 0)，确定了S0中的第0行2列（0，2）的系数为3，记为（1 1）输出。由S0,S1输出4 bit经置换 P4=(2 4 3 1)；它的输出就是F函数的输出。50 DES是一种对二元数据进行加密的算法,数据分组长度为64位,密文分组长度也是64位,使用的密钥为64位,有效密钥长度为56位,有8位用于奇偶校验,解密时的过程和加密时相似,但密钥的顺序正好相反,DES的整个体制是公开的,系统的安全性完全靠密钥的保密.51DES算法的过程：是在一个初始置
22、换IP(initial permutation)后，明文组被分成右半部分和左半部分，每部分32位以L0和R0表示，然后，是16轮迭代的乘积变换，称为函数f，将数据和密钥结合起来。16轮之后，左右两部分再连接起来，经过一个初始逆置换IP-1 算法结束。525354 初始置换与初始逆置换在密码意义上作用不大，他们的作用在于打乱原来输入x的ASCII码字划分关系，并将原来明文的校验位变成置换输出的一个字节。55 2.1数据加密概念 2.2密码体制 2.3密码分类 2.4算法分类 2.5加密算法 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法 2.9破译时间56 共四种操作模
23、式 电子编码本ECB密码分组链接CBC 密码反馈CFB 输出反馈OFB57 在ECB方式中，对于相同的密钥，相同的明文产生相同的密文 58 特点:简单和有效可以并行实现不能隐藏明文的模式信息 相同明文 相同密文 同样信息多次出现造成泄漏对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放误差传递：密文块损坏,仅对应明文块损坏,适合于传输短信息5960 特点:没有已知的并行实现算法 能隐藏明文的模式信息 需要共同的初始化向量IV 相同明文 不同密文 初始化向量IV可以用来改变第一块 对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏 两明文块损坏 安全性
24、好于ECB 适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如 SSL、IPSec6162CFB特点:分组密码 流密码 没有已知的并行实现算法 隐藏了明文模式 需要共同的移位寄存器初始值IV 对于不同的消息，IV必须唯一 误差传递：一个单元损坏影响两个单元636465OFB特点:OFB:分组密码 流密码 没有已知的并行实现算法 隐藏了明文模式 需要共同的移位寄存器初始值IV 误差传递：一个单元损坏只影响对应单元 对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放 安全性较CFB差66 2.1数据加密概念 2.2密码体制 2.3密码分类 2.4算法分类 2.5加密算法
25、 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法 2.9破译时间67 下面主要考察较为流行的最重要的几个对称密钥的分组密码算法,这些算法都是自DES公布之后,人们了解DES的弱点越来越深入的情况下给出的,给出的方式有两种,一种是对DES进行复合强化它的抗攻击能力；另一种是开辟新的方法，即象DES那样加解密速度快，又具有抗差分攻击和其他方式攻击的能力。这些算法有三重DES、IDEA、RC5、RC6、Blowfish、CAST、RC2。68 这种方式里，使用三或两个不同的密钥对数据块进行三次或两次加密，加密一次要比进行普通加密的三次要快，三重DES的强度大约和112-bi
26、t的密钥强度相当。三重DES有四种模型：1DES-EEE3 使用三个不同密钥顺序进行三次加密变换。2DES-EDE3 使用三个不同密钥依次进行加密-解密-加密变换。3DES-EEE2 其中密钥K1=K3 顺序进行三次加密变换。4DES-EDE2 其中密钥K1=K3 依次进行加密-解密-加密变换。69 到目前为止，还没有人给出攻击三重DES的有效方法，对其密钥空间中密钥进行蛮干搜索，那么由于空间太大这实际上是不可行的。若用差分攻击的方法，相对于单一DES来说复杂性以指数形式增长要超过1052。70 RC5是由RSA公司的首席科学家Ron Rivest于1994年设计，95年正式公开的一个很实用的
27、加密算法。它是一种分组长（2倍字长w位）、密钥长（按字节数计）和迭代轮数都可变的一种分组迭代密码。它以RC5-w/r/b表示。Rivest建议使用的标准RC5为RC5-32/12/16。71该算法具有如下特性：(a)形式简单易于软件或者硬件实现，运算速度快。(b)能适应于不同字长的程序，不同字长派生出相异的算法。(c)加密的轮数可变，这个参数用来调整加密速度和安全性的程度。(d)密钥长度是可变的，加密强度可调节。(e)对记忆度要求不高，使RC5可用于类似Smart Card这类对记忆度有限定的器件。(f)具有高保密性（适当选择好参数）。(g)对数据实行bit循环移位，增强了抗攻击能力。72 R
28、C5自1995年公布以来，尽管至今为止还没有发现实际攻击的有效手段，然而，一些理论攻击的文章先后也分析出RC5的一些弱点。73 IDEA是International Data Encryption Algorithm 的缩写,是1990年由瑞士联邦技术学院来学嘉（X.J.Lai）和Massey提出的建议标准算法,称作PES（Proposed Encryption Standard）.Lai 和Massey 在1992 年进行了改进,强化了抗差分分析的能力，改称为IDEA。它也是对64bit大小的数据块加密的分组加密算法，密钥长度为128位，它基于“相异代数群上的混合运算”设计思想，算法用硬件和
29、软件实现都很容易，它比DES在实现上快得多。74 1997年4月15日美国国家标准和技术研究所NIST 发起了征集AES算法的活动，并成立了专门的AES工作组，目的是为了确定一个非保密的公开披露的全球免费使用的分组密码算法，用于保护下一世纪政府的敏感信息，并希望成为秘密和公开部门的数据加密标准。75 1997年9月12日在联邦登记处公布了征集AES候选算法的通告，AES的基本要求是比三重DES快，而且，至少和三重DES一样安全，分组长度128比特，密钥长度为128/192/256比特。1998年8月20日NIST召开了第一次候选大会并公布了15个候选算法，1999年3月22日举行了第二次AES
30、候选会议，从中选出5个。76 AES将成为新的公开的联邦信息处理标准(FIPSFederal Information Processing Standard)，用于美国政府组织保护敏感信息的一种特殊的加密算法。美国国家标准技术研究所(NIST)预测，AES会被广泛地应用于组织学院及个人，入选AES的五种算法是MARS、RC6、Serpent、Twofish、Rijndael。2000年10月2日美国商务部部长Norman Y.Mineta宣布，经过三年来世界著名密码专家之间的竞争,“Rijndael数据加密算法”最终获胜。77 为此而在全球范围内角逐了数年的激烈竞争宣告结束，这一新加密标准的问
31、世将取代DES数据加密标准成为21世纪保护国家敏感信息的高级算法。为AES开发Rijndael算法的是两位来自比利时的密码专家Proton World International的Joan daemen博士、Katholieke Universiteit Leuven电子工程系(ESAT)的Vincent Rijmen博士后，两位先生在加密领域里一直比较活跃。78 NIST主任Ray Kammer在马里兰召开的新闻发布会上说之所以选中Rijndael，是因为它很快，而且所需的内存不多。这个算法是如此可靠，就连在密码方面最内行的美国国家安全局也决定将用它来保护一些关键数据不被窥视。79 Rijn
32、dael也是5个上了决赛名单中唯一一个不面临潜在的日立公司侵犯专利诉讼的算法，日立在早些时候宣布了对一系列密码采用的数学技术的所有权，但Kammer说法律问题不是决定算法选择的因素，Rijndael算法的原形是Square算法，它的设计策略是宽轨迹策略（Wide Trail Strategy）,这种策略是针对差分分析和线性分析提出来的，是一个分组迭代密码，具有可变的分组长度和密钥长度。80 AES被设计成三个密钥长度128/192/256比特，用于加密长度为128/192/256比特的分组相应的轮数为10/12/14。Rijndael汇聚了安全性能、效率、可实现性和灵活性等优点，尤其是在无论有无反馈模式的计算环境下的软硬件中，Rijndael都显示出其非常好的性能。Rijndael的对内存的需求非常低，也使它很适合用于受限制的环境中。Rijndael的操作简单，并可抵御强大和实时的攻击，此外它还有许多未被特别强调的防御性能。81 2.1数据加密概念 2.2密码体制 2.3密码分类 2.4算法分类 2.5加密算法 2.6数据加密标准DES 2.7密码分组操作模式 2.8其它分组加密算法 2.9破译时间8283思考和练习 1.什么特性使得加密绝对不可攻破？什么特性将使得加密在实际应用中是不可攻破的？2.解释为什么双替换密码比单替换更安全？3.了解三重DES和RC5,6算法。
