DES算法分析PPT课件

-,1,第二章数据加密技术,2.1数据加密概述2.2古典密码技术2.3对称加密流密码2.4对称加密分组密码2.5非对称加密2.6数字签名2.7报文鉴别2.8密钥的管理,主要内容,-,2,第二章数据加密技术,掌握数据加密的基本概念掌握传统的密码技术掌握对称密钥密码和公开密钥密码体制掌握密钥管理掌握数字签名的方法,本章学习重点,2.1数据加密概述,2.1.1密码学的发展密码学（Cryptography，来源于古希腊的Crypto和Graphein，意思是密写）是一门古老而深奥的学科，它以认识密码变换为本质，以加密与解密基本规律为研究对象。早在几千年前，人类就已经有了保密通信的思想和方法，但这些保密方法都是非常朴素、原始和低级的，而且大多数是无规律的。1949年，信息论的创始人香农（C.E.Shannon）发表了一篇著名的文章，论证了一般经典加密方法都是可以破解的。到了20世纪60年代，随着电子技术、信息技术的发展及结构代数、可计算性理论和复杂度理论的研究，密码学又进入了一个新的时期。,概述,加密算法是加密技术的核心以及重点研究对象，算法的优良与否直接影响系统的安全性能，其主要是指对机密信息进行加密或解密的方法。按密钥方式分为：对称加密算法：又叫传统密钥算法或私有密钥算法。非对称加密算法：又叫公开密钥算法。,对称加密算法,对称加密算法：加解密密钥相同或可互相推出。安全性依赖于密钥。有：DES、3DES、IDEA、AES、RC等。分为分组密钥和流密钥。分组密钥：将明文分成固定块用同一密钥和算法加密，并输出固定长度密文。流密钥：对明文逐位进行加密。,发送方,接收方,两个密钥相同,对称加密,非对称加密（Cont.）,非对称加密算法需要两个密钥:公钥私钥一个用于加密，另一个则用作解密不能根据一个密钥来推算得出另一个密钥公钥对外公开，私钥只有其持有人才知道RSA，DSA，Diffie-Hellman,发送方,接收方,非对称加密,多个用户加密的信息只能由一个用户解读,发送方,接收方,一个用户加密的信息，多个用户解读,非对称加密（Cont.）,对称加密技术,对称密码体制概述分组密码原理DES算法,对称密钥密码的概念,1对称密钥密码体制的基本思想对称密钥密码体制也叫传统密钥密码体制，其基本思想就是“加密密钥和解密密钥相同或相近”，由其中一个可推导出另一个。对称密钥密码体制模型如图2-3所示。,图2-3对称密钥密码体制模型,发送端,对称密码体制概述,在对称密码体制中，加密密钥和解密密钥相同，或彼此之间容易相互确定。对称密码分类分组密码（blockcipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。,流密码,对称加密流密码,流密码（即序列密码）是一种类似于“一次一密”密码体制加密过程：是将密钥流（密钥的二进制位）与等长的明文的二进制位进行模2运行解密过程：是将密钥流与密文进行逐位模2运行，所以流密码是一种对称加密方式,2.3.1流密码的工作原理,在现代计算机网络中，由于报文、数据和图像等消息都可以通过某一编码技术转化为二进制数字序列，因而可假定流密码中的明文空间M是由所有可能的二进制数字序列组成的集合。设K为密钥空间，由于流密码应使用尽可能长的密钥，而太长的密钥在存储、分配等方面都有一定的困难，于是研究人员采用一个短的密钥kK来控制某种算法A产生出长的密钥序列，供加密和解密使用。而短密钥k的存储和分配在实现方式上都比较容易。根据密码学的约定，算法A是公开的，而密钥k是保密的。,流密码,A5/1,A5/1,A5/1,图2-5A5/1密钥流生成器的工作过程,A5/1,分组密码原理,分组密码一般原理：分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。,分组密码原理,1.Feistel网络结构1)将明文P分为左右相等长度的两半L0、R02)将R0L1L0F(R0,k1)R13)在第i轮时Ri-1LiLi-1F(Ri-1,ki)Ri4)至止最后一轮nLn=Rn-1Rn=Ln-1F(Rn-1,kn),+,图2-7Feistel的加密和解密过程,Feistel的解密过程,2.4.2数据加密标准（DES）,数据加密标准（DataEncryptionStandard，DES）是由IBM公司在1971年设计的一个加密算法。1977年由美国国家标准局（现美国国家标准技术委员会）作为第46号联邦信息处理标准而采用的一种数据加密标准。之后，DES成为金融界及其他非军事行业应用最为广泛的对称加密标准。DES是分组密码的典型代表，也是第一个被公布出来的标准算法。DES的算法完全公开，在密码学史上开创了先河。DES是迄今为止世界上应用最为广泛的一种分组密码算法。,DES简介,分组加密算法：明文和密文为64位分组长度。对称算法：加密和解密除密钥编排不同外，使用同一算法。密钥长度：56位。看起来是64位，但每个第8位为奇偶校验位，可忽略。采用混乱和扩散的组合，每个组合先替代后置换，共16轮。只使用了标准的算术和逻辑运算，易于实现。,DES基本结构,56比特密钥,生成16个轮密钥,16个48比特轮密钥,DES对64位的明文分组进行操作。step1:通过一个初始置换，将明文分组分成左半部分和右半部分，各32位长。step2:进行16轮完全相同的运算，这些运算被称为函数f，在运算过程中数据与密钥结合。Step3:经过16轮后，左、右半部分合在一起，经过一个末置换（初始置换的逆置换），这样该算法就完成了。,数据加密标准DES,1,2,3,P0=IP(P)=L0R0,Li=Ri-1Ri=Li-1f(Ri-1,Ki),DES算法描述,初始置换IP,IP-1,L1=R0,R1=L0(RO,K1),L2=R1,R2=L1(R1,K2),L15=R14,R15=L14(R14,K15),R16=L15(R15,K16),L16=R15,64位明文,64位密文,DES算法大致可以分为3个部分：初始置换迭代过程逆置换迭代过程：密钥置换扩展置换S-盒代替P-盒置换,DES算法描述,初始置换IP,IP-1,L1=R0,R1=L0(RO,K1),L2=R1,R2=L1(R1,K2),L15=R14,R15=L14(R14,K15),R16=L15(R15,K16),L16=R15,64位明文,64位密文,DES算法的总体过程输入64位明文数据，并进行初始置换IP；在初始置换IP后，明文组再被分为左右两部分，每部分32位，以L0，R0表示。在密钥的控制下，经过16轮运算()；16轮后，左、右两部分交换，并连接在一起；经过末置换（初始置换的逆置换）；输出64位密文。,DES算法描述,初始置换与末置换初始置换IP(initialpermutation)在第一轮运算之前进行。未置换IP-1(初始置换的逆置换)在第十六轮运算之后进行。,IP-1,作用：将通过IP初始变换后已处于乱序状态的64位数据，变换到原来的正常位置,IP和IP-1,例1：明文中的第20位经过初始变换后处于第14位，通过逆初始变换第14位换回到第20位例2：明文m中的第60为数据在初始变换后处于第9位，通过逆初始变换第9位换回到第60位,DES算法描述,迭代过程经过初始置换后，进行16轮完全相同的运算。这些运算被称为，在运算过程中数据与密钥结合。,函数的输出经过一个异或运算，和左半部分结合，其结果成为新的右半部分，原来的右半部分成为新的左半部分。,DES算法描述,函数函数由四步运算构成：密钥置换(Ki的生成i=0,1,16)扩展置换S-盒代替P-盒置换1)密钥置换DES算法由64位密钥产生16轮的48位子密钥。在每一轮运算过程中，使用不同的子密钥。,F函数,DES算法描述,64位密钥,置换选择1,置换选择2,置换选择2,压缩置换。将56位输入置换为48位。,不考虑每字节的第8位，将64位密钥减至56位。然后进行一次密钥置换。,各轮循环移动的次数由轮数决定。,每一轮子密钥K生成过程可以表示为：,数据加密标准(DES),数据加密标准,5749413325179158504234261810259514335271911360524436,6355473931331576254463830221466153453729211352820124,不考虑各字节第8位,密钥（64位）,C0(28位),D0(28位),密钥置换选择1,C0(28位)=k57k49k44k36,D0(28位)=k63k55k12k4,数据加密标准(DES),数据加密标准,Ci(28位),Di(28位),1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932,Ki(48位),密钥置换2,去掉第9，18，22，25，35，38，43，54位，56位变成48位,DES算法描述,经过置换选择1，将输出的56位密钥分成两部分，每部分28位。然后，根据轮数，将两部分分别循环左移1位或2位。如下表所示。,DES子密钥的生成,DES算法描述,假设Li和Ri是第i次迭代结果的左半部分和右半部分，Ki是第i轮的48位密钥，则每一轮迭代过程可以表示为：,函数,扩展置换E,S盒代替,P-盒置换,Ri(32bit),Li(32bit),Ri=Li-1(Ri-1,Ki-1),Li=Ri-1,DES算法描述,2)扩展置换E通过扩展置换E，数据的右半部分Ri从32位扩展到48位。扩展置换改变了位的次序，重复了某些位。扩展置换有两方面的目的：产生与密钥同长度的数据以进行异或运算；提供更长的结果，使得在替代运算时能够进行压缩。,F函数,DES算法描述,32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|01,扩展置换E,数据的扩展置换规则：中间为32位，两边为扩展位，扩展后为48位。,扩展变换,DES算法描述,3)S盒代替压缩后的密钥与扩展分组异或以后，将48位的结果送入，进行代替运算。,F函数,DES算法描述,48-位输入,32-位输出,S-盒1,代替运算由8个不同的代替盒（S盒）完成。每个S盒有6位输入，4位输出。48位的输入被分为8个6位的分组，每一分组对应一个S-盒代替操作。经过S盒代替，形成8个4位分组。,DES算法描述,例如，假设S-盒6的输入(即异或函数的第31位到36位)为110011。第1位和最后一位组合形成了11，它对应着S-盒6的第3行。中间的4位组合形成了1001，它对应着S-盒6的第9列。S-盒6的第3行第9列处的数是14，得到输出值为1110。,S-盒6,012，1，10，15，9，2，6，8，0，13，3，4，14，7，5，11，110，15，4，2，7，12，9，5，6，1，13，14，0，11，3，8，29，14，15，5，2，8，12，3，7，0，4，10，1，13，11，6，34，3，2，12，9，5，15，10，11，14，1，7，6，0，8，13,0123456789101112131415,S-盒的构造,DES算法描述,4)P盒置换S-盒代替运算后的32位输出依照P盒进行置换。P盒置换将每一输入位映射到输出位。任一位不能被映射两次，也不能被略去。经过P-盒置换的结果与最初64位分组的左半部分异或，然后左右两部分交换，开始下一轮迭代。,例如，第21位移到了第4位，第4位移到了第31位。,DES解密,在经过所有的代替、置换、异或和循环移动之后，获得了这样一个非常有用的性质：加密和解密可使用相同的算法。DES使得用相同的函数来加密或解密每个分组成为可能，二者的唯一不同之处是密钥的次序相反。这就是说，如果各轮的加密密钥分别是K1，K2，K3，K16那么解密密钥就是K16，K15，K14，K1。为各轮产生密钥的算法也是循环的。密钥向右移动，每次移动个数为0，1，2，2，2，2，2，2，1，2，2，2，2，2，2，1。,DES解密：,DES解密,DES解密：,简单地说：-DES的解密和加密使用相同的算法。-解密过程中使用的子密钥顺序与加密过程中使用的密钥顺序相反。即：如果各轮的加密密钥是K1,K2,K3,K16，那么解密密钥就是K16,K15,K14,K1。,DES算法描述,DES算法特点1)分组加密算法：以64位为分组。64位一组的明文从算法一端输入，64位密文从另一端输出。2)对称算法：加密和解密用同一密钥。3)有效密钥长度为56位。密钥通常表示为64位数，但每个第8位用作奇偶校验，可以忽略。,DES算法描述,DES算法特点4)代替和置换DES算法是两种加密技术的组合：混乱和扩散。先代替后置换。5)易于实现DES算法只是使用了标准的算术和逻辑运算，其作用的数最多也只有64位，因此用70年代末期的硬件技术很容易实现。算法的重复特性使得它可以非常理想地用在一个专用芯片中。,DES的实现,DES的实现：,举例：已知明文m=computer，密钥k=program，用ASCII码表示为：m=0110001101101111011011010111000001110101011101000110010101110010k=01110000011100100110111101100111011100100110000101101101因为k只有56位，必须插入第8，16，24，32，40，48，56，64位奇偶校验位，合成64位。而这8位对加密过程没有影响。,DES的实现,DES的实现：,m经过IP置换后得到L0=11111111101110000111011001010111R0=00000000111111110000011010000011密钥k通过PC-1得到C0=1110110010011001000110111011D0=1011010001011000100011100110再各自左移一位，通过PC-2得到48位k1=001111011000111111001101001101110011111100000110R0（32位）经E作用膨胀为48位，100000000001011111111110100000001101010000000110,DES的实现,DES的实现：,再和k1作异或运算得到（分成8组）101111011001100000110011101101111110101101001110通过S盒后输出位32比特，01110110001101000010011010100001S盒的输出又经过P置换得到01000100001000001001111010011111这时：,所以，第一趟的结果是：0000000011111111000001101000001110111011100110001110100011001000,DES的实现,DES的实现：