DES算法分析

第二章数据加密技术2.1数据加密概述2.2古典密码技术2.3对称加密—流密码2.4对称加密—分组密码2.5非对称加密2.6数字签名2.7报文鉴别2.8密钥的管理主要内容第二章数据加密技术掌握数据加密的基本概念掌握传统的密码技术掌握对称密钥密码和公开密钥密码体制掌握密钥管理掌握数字签名的方法本章学习重点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所示。明文P密文C加密（E）发送端解密（D）接收端明文PAB密钥图2-3对称密钥密码体制模型发送端对称密码体制概述在对称密码体制中，加密密钥和解密密钥相同，或彼此之间容易相互确定。对称密码分类分组密码（blockcipher):将明文分成固定长度的组，用同一密钥和算法对每一块加密，输出也是固定长度的密文。流密码（streamcipher):又称序列密码.序列密码每次加密一位或一字节的明文，也可以称为流密码。流密码对称加密—流密码流密码（即序列密码）是一种类似于“一次一密”密码体制加密过程：是将密钥流（密钥的二进制位）与等长的明文的二进制位进行模2运行解密过程：是将密钥流与密文进行逐位模2运行，所以流密码是一种对称加密方式2.3.1流密码的工作原理在现代计算机网络中，由于报文、数据和图像等消息都可以通过某一编码技术转化为二进制数字序列，因而可假定流密码中的明文空间M是由所有可能的二进制数字序列组成的集合。设K为密钥空间，由于流密码应使用尽可能长的密钥，而太长的密钥在存储、分配等方面都有一定的困难，于是研究人员采用一个短的密钥k∈K来控制某种算法A产生出长的密钥序列，供加密和解密使用。而短密钥k的存储和分配在实现方式上都比较容易。根据密码学的约定，算法A是公开的，而密钥k是保密的。流密码A5/1A5/1A5/1图2-5A5/1密钥流生成器的工作过程A5/1分组密码原理分组密码一般原理：分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列。加密算法k=(k0,k1,…kn-1)(m0,m1,…mn-1)(c0,c1,…cn-1)(m0,m1,…mn-1)解密算法k=(k0,k1,…kn-1)分组密码原理1.Feistel网络结构1)将明文P分为左右相等长度的两半L0、R02)将R0→L1L0⊕F(R0,k1)→R13)在第i轮时Ri-1＋→LiLi-1⊕F(Ri-1,ki)→Ri4)至止最后一轮nLn=Rn-1Rn=Ln-1⊕F(Rn-1,kn)PL0R0L1R1k1F＋F＋LiRiki……FLnRnkn……+图2-7Feistel的加密和解密过程Feistel的解密过程2.4.2数据加密标准（DES）数据加密标准（DataEncryptionStandard，DES）是由IBM公司在1971年设计的一个加密算法。1977年由美国国家标准局（现美国国家标准技术委员会）作为第46号联邦信息处理标准而采用的一种数据加密标准。之后，DES成为金融界及其他非军事行业应用最为广泛的对称加密标准。DES是分组密码的典型代表，也是第一个被公布出来的标准算法。DES的算法完全公开，在密码学史上开创了先河。DES是迄今为止世界上应用最为广泛的一种分组密码算法。DES简介分组加密算法：明文和密文为64位分组长度。对称算法：加密和解密除密钥编排不同外，使用同一算法。密钥长度：56位。看起来是64位，但每个第8位为奇偶校验位，可忽略。采用混乱和扩散的组合，每个组合先替代后置换，共16轮。只使用了标准的算术和逻辑运算，易于实现。DES基本结构输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据交换左右32比特56比特密钥生成16个轮密钥16个48比特轮密钥DES对64位的明文分组进行操作。step1:通过一个初始置换，将明文分组分成左半部分和右半部分，各32位长。step2:进行16轮完全相同的运算，这些运算被称为函数f，在运算过程中数据与密钥结合。Step3:经过16轮后，左、右半部分合在一起，经过一个末置换（初始置换的逆置换），这样该算法就完成了。数据加密标准DES初始置换…64位明文初始置换第1轮…第16轮左右交换逆初始置换…64位密文置换选择2置换选择n置换选择1左循环移位左循环移位……56位密钥123123置换选择1…56位密钥P0=IP(P)=L0R0Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)DES算法描述初始置换IP+k1+k2+k16IP-1L0R0L1=R0R1=L0(RO,K1)L2=R1R2=L1(R1,K2)L15=R14R15=L14(R14,K15)R16=L15(R15,K16)L16=R1564位明文64位密文DES算法大致可以分为3个部分：初始置换迭代过程逆置换迭代过程：密钥置换扩展置换S-盒代替P-盒置换DES算法描述初始置换IP+k1+k2+k16IP-1L0R0L1=R0R1=L0(RO,K1)L2=R1R2=L1(R1,K2)L15=R14R15=L14(R14,K15)R16=L15(R15,K16)L16=R1564位明文64位密文DES算法的总体过程输入64位明文数据，并进行初始置换IP；在初始置换IP后，明文组再被分为左右两部分，每部分32位，以L0，R0表示。在密钥的控制下，经过16轮运算()；16轮后，左、右两部分交换，并连接在一起；经过末置换（初始置换的逆置换）；输出64位密文。DES算法描述初始置换与末置换初始置换IP(initialpermutation)在第一轮运算之前进行。未置换IP-1(初始置换的逆置换)在第十六轮运算之后进行。初始置换IP初始逆置换IP-15850423426181024084816562464326052443628201243974715552363316254463830221463864614542262306456484032241683754513532161295749413325179136444125220602859514335271911335343115119592761534537292113534242105018582663554739312315733141949175725IP-1作用：将通过IP初始变换后已处于乱序状态的64位数据，变换到原来的正常位置IP和IP-1例1：明文中的第20位经过初始变换后处于第14位，通过逆初始变换第14位换回到第20位例2：明文m中的第60为数据在初始变换后处于第9位，通过逆初始变换第9位换回到第60位DES算法描述迭代过程经过初始置换后，进行16轮完全相同的运算。这些运算被称为，在运算过程中数据与密钥结合。+k1L0R0L1=R0R1=L0(RO,K1)函数的输出经过一个异或运算，和左半部分结合，其结果成为新的右半部分，原来的右半部分成为新的左半部分。DES算法描述函数函数由四步运算构成：1)密钥置换(Ki的生成i=0,1,…,16)1)扩展置换2)S-盒代替3)P-盒置换1)密钥置换DES算法由64位密钥产生16轮的48位子密钥。在每一轮运算过程中，使用不同的子密钥。Li-1(32bit)Ri-1(32bit)扩展置换ES盒代替P-盒置换Ri(32bit)Li(32bit)Ki48bitRi=Li-1(Ri-1,Ki-1)Li=Ri-132位48位48位32位32位32位F函数DES算法描述64位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)置换选择2循环左移循环左移Ci(28位)Di(28位)置换选择256位k148位ki48位56位压缩置换。将56位输入置换为48位。不考虑每字节的第8位，将64位密钥减至56位。然后进行一次密钥置换。各轮循环移动的次数由轮数决定。每一轮子密钥K生成过程可以表示为：数据加密标准(DES)数据加密标准57494133251791585042342618102595143352719113605244366355473931331576254463830221466153453729211352820124不考虑各字节第8位密钥（64位）C0(28位)D0(28位)密钥置换选择1C0(28位)=k57k49…k44k36D0(28位)=k63k55…k12k4数据加密标准(DES)数据加密标准Ci(28位)Di(28位)1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932Ki(48位)密钥置换2去掉第9，18，22，25，35，38，43，54位，56位变成48位DES算法描述C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)64位密钥置换选择1经过置换选择1，将输出的56位密钥分成两部分，每部分28位。然后，根据轮数，将两部分分别循环左移1位或2位。如下表所示。每轮移动的位数表轮12345678910111213141516位数1122222212222221DES子密钥的生成DES算法描述假设Li和Ri是第i次迭代结果的左半部分和右半部分，Ki是第i轮的48位密钥，则每一轮迭代过程可以表示为：函数Li-1(32bit)Ri-1(32bit)扩展置换ES盒代替P-盒置换Ri(32bit)Li(32bit)Ri=Li-1(Ri-1,Ki-1)Li=Ri-132位48位48位32位32位32位DES算法描述2)扩展置换E通过扩展置换E，数据的右半