《信息安全引论》课件Chapter2

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息的保密问题是信息安全科学中最早提出的问题，也是最重要的问题。本章主要研究保密问题的解决方案：对称加密算法,第,2,章 对称加密算法,本章内容,第,1,节 历史与分类,第,2,节 数据加密标准,-DES,第,3,节 先进加密标准,-AES,第,4,节 密码运算模式,第,5,节 对称密码算法的应用,第,6,节 对称加密算法的优缺点,小结,本章主要讲述了保证信息机密性的主要方法,-,对称加密方法，其中讲述了两种分组密码算法,DES,、,AES,；讲述了当消息的长度不是规定的输入长度时如何进行加密,-,加密模式；讲述了对称加密算法的应用以及对称加密算法的优缺点。,练习题,1. Alice,、,Bob,、,Carol,三个人在一起吃饭。吃完饭后，,Alice,要结账时，服务员告诉她：已经有人结账了。这结账的人，可能是他们当中的一个，也可能是,NSA,。他们都尊重彼此匿名付账的权利，但都想知道到底是他们其中的一个人结的账，还是,NSA,结的账。他们想出了一个方法：,假设他们围成一圈，每个人都和他右边的人抛一枚硬币，只有他们两个能看到结果。然后每个人都大声说他看到的两次抛币结果是否相同，如果有一个人结账，她就说假话，如果没有结帐，就说真话。如果说看到结果不同的人数为奇数，表明它们之间有一个人结账，但除结账者以外，别人不知道是谁付的账，如果为偶数，表明,NSA,为他们结账了。试用数学方法证明这对任意人数的吃饭者都成立。,The End,第,1,节,密码系统的历史与分类,In Preamble,，我们介绍过信息安全的历史,(,主要是密码学的历史,),。现代密码学产生以前的历史都是对称密码学的历史。现代密码学诞生以后密码学的历史则较为复杂。,对于密码系统基本上有三种分类方法：,(1),根据将明文变换成密文的方法分为：,替换密码,：将明文的每个单位替换成密文的一个单位；,换位密码,：将明文内容的顺序进行重新排列。,LAUNCHATTACKONOCTOMBERTWE LVEOF 1 1,LATEAAOLUCMENKBECOOBOHNRAOT1TCW1,密码系统的分类,(2),根据使用的密钥数量可以将密码系统分为,对称密码学,系统和,公开密钥密码系统,：如果系统中消息的发送者与接受者使用相同的密钥，则称为对称密码系统，如果使用不同的密钥就称为公开密钥密码系统。,密码系统的分类,根据对明文进行处理的方式可以分为两种：分组密码和序列密码。,分组密码,就是将比较长的明文信息，分成较小的信息组进行加密。,DES,和,AES,都是分组密码。,DES,和,AES,代表分组密码的最高水平，所以主要讲述,DES,和,AES,。,序列密码,，对于较长的信息不是进行分组加密，而是应用一定的机制，对于到来得信息像水流一样进行加密，所以又称流密码。,BACK,第,2,节 数据加密标准,DES,DES (Data Encryption Standard ),算法是,1977,年由美国国家标准局颁布的标准，用于商业和非机密的政府应用领域的加密。是在,IBM,的,Lucifer,算法基础上设计的，后被国家标准局采用。是分组密码算法，一次加密,64,比特的明文分组，输出是,64,比特的密文分组。目前我国的银行系统、商业系统、政府部门大部分采用的都是,DES,加密。这是我国信息安全领域的一块心病，是信息安全面临的一个挑战。,分组密码算法示例,分组密码算法是将一组明文转换成一组密文的算法。这里有一个密钥长度的选择问题，密钥长度太短，显然不安全。类似地分组的长度也不能太小。太小时，一旦有明文密文对就很容易解密。分组长度太长，可能影响加密算法的效率，而密码学界公认,64,比特是比较合理的长度，因为当分组长度大于,64,比特时，不容易获得足够的用于分析的明文密文对，即使获得也没有足够的空间存储这样的明文密文对，或者没有足够的时间进行搜索。,分组密码算法示例,对称密钥算法一般用一个长度合理的密钥生成一个一一对应的映射，这种映射对于不知道密钥的人来说，这种映射关系看起来是随机的。要求输入的每个比特必须对输出的每个比特都有影响。,要加密,64,比特的分组，最直接的方法是将,2,64,种分组的每个分组变换到特定的,2,64,种密文分组，要求这种变换必须是一一对应的，否则无法解密。,分组密码算法示例,虽然攻击者没有空间存储这种变换，难以通过,Brute,Force,进行攻击。使用者也有空间存储问题。因而必须想另外的方法。对于每一个分组可以设想两种变换：替换和置换。,替换：,k,比特的分组有,2,k,种可能输入，对于每种输入都构造一个一一对应的变换替换。这种替换对于,2,64,可能替换，有存储问题，但当,k,比较小时则是可行的。,分组密码算法示例,置换,：对于,k,比特的输入，指定输出时每个比特必须出现在那个位置。比如输入的第一比特在输出中变为,31,比特等。一种构造对称加密算法的方法就是把能够处理的小块，每小块设计一个一一对应映射。然后将替换后的所有小块放到一起作置换，通过置换可以将各个比特移动到不同的位置，随后不断重复这一过程，就可以把输入的每个比特混合到一起。,分组密码的,1,轮示例,分组密码算法示例,上述过程如果只进行一轮的话，输入的每个比特只能影响输出的,8,个比特。为了保证安全性，必须保证进行一定的轮数。但也不是轮数越多越安全。与洗牌一样，如果洗牌已经保证扑克牌有足够的随机性时，更多的洗牌次数只是浪费时间。设计算法的一部分工作就是要确定最佳轮数。少不能保证安全，多了就会影响算法的效率。,DES,Algorithm,DES,算法很容易用硬件实现，用软件实现相对困难。现在计算机技术的发展已经使得用软件实现起来也易如反掌。,DES,中有四种基本运算：,替换,、,置换,、异或与,Mangler,函数运算。,替换,是对单个元素的运算，将一个元素换成另一个元素。,置换,是对一个集合的运算。集合,3, 1, 4, 5, 2,就是集合,1, 2, 3, 4, 5,的一个置换。,DES,算法概述,DES,算法的分组长度是,64,比特，密钥长度也是,64,比特，计算机技术的发展使得,64,比特的密钥已经有点短了，按照摩尔定律，计算机的性价比每,18,个月翻一番。我们假设每两年翻一番，那么密钥的长度每两年需要增加,1,比特，假设,64,比特的密钥在,1995,年是安全的，那么,128,比特的密钥在,2123,年之前都是安全的。,DES,的基本结构,数据的初始置换,数据分组的初始置换,(,对安全性没有影响,),数据的末置换,DES,的基本结构,生成子密钥的初始置换,首先对密钥的,56,个有效比特作置换，得到,56,比特的输出，这个输出被分成两部分，每个部分,28,比特，记为,C,0,、,D,0,其置换如下：,密钥的初始置换,(,对安全性没有影响,),DES,的基本结构,子密钥,K,i,的生成方法,前面已经介绍了如何生成,C,0,、,D,0,。其他子密钥都是以,C,0,、,D,0,为基础循环生成的，每一轮由,C,i-1,生成,C,i,D,i-1,生成,D,i,，对,C,i,和,D,i,分别进行一次置换，然后将经过置换后的,C,i,和,D,i,进行合并，就得到第,i,轮的子密钥,K,i,。,生成,K,的第,i,轮,如何循环左移,生成子密钥的循环左移的左位移数目，在不同轮中是不同的：第,1,、,2,、,9,、,16,轮只进行,1,比特的循环左移，而其他各轮则循环左移两个比特，从左边移出的比特又从最右边移入。这里的置换可能对安全性有影响。,获得,K,i,左半部分的置换,获得,K,i,右半部分的置换,48,比特的子密钥,从上述置换可以看出，置换的结果由,56,比特的密钥变成了,48,比特的子密钥，严格来说并不是置换，而是对某个子集的置换，在上述置换中密钥的左半部分，第,9,、,18,、,22,、,25,比特被丢弃。右半部分,35,、,38,、,43,、,54,比特被丢弃。丢弃之后再作置换。生成了,48,比特的子密钥。,DES,的基本结构,1 Round of DES Algorithm,DES,的一轮运算包括左右两半部分对换、异或运算、,mangler,函数运算、两部分合并等过程，其中最巧妙的是,mangler,函数的构造，这是影响安全性的主要因素。,1 Round of DES,Mangler,Function,Mangler,函数的输入为右边的,32,比特的数据、,48,比特的子密钥，输出为,32,比特的数据。所进行的运算包括数据扩展、异或运算和,S,盒替换。,Expand right 32 bits into 48 bits,块转换,第,1,个,S,盒的,4,比特输出,(1-4,比特,),根据,S-Box,的第,1,与第,6,比特选定一行，根据第,2,到第,6,比特的数据选定一列，这样给定,S-box,的输入，就能查表确定唯一的的输出,其他,S,盒的输出,其他,S,盒的输入与输出的关系与第一个,S,盒的输入输出关系大同小异，方法是一样的，也是用查表的方法进行替换，不同的是表的内容有所变化。这样我们就对,DES,算法的全部细节有了比较彻底的了解，现在我们再回头看一下在,DES,中还有没有不清楚的地方。,DES,的基本结构,DES,的现状,In 1997,RSA Security,sponsored a series of contests, offering a $10,000 prize to the first team that broke a message encrypted with DES for the contest. That contest was won by the,DESCHALL Project, led by,Rocke,Verser,Matt Curtin, and Justin,Dolske, using idle cycles of thousands of computers across the Internet. Their motivation was to show that DES was breakable in practice as well as in theory.,Now all the DES used in practice is in triple-DES form.,BACK,第,3,节,AES Algorith,(1/9),因为,DES,算法的密钥太短，,3DES,速度太慢，,IDEA,算法有专利保护，且速度也不快。所以,NIST,希望建立一个新的加密算法标准，新的算法应该高效、灵活且不难应用。,NIST,与,1997,年,1,月,2,日宣布征集新的用于保护敏感的非机密信息的加密标准。算法可以来自任何地方，但必须达到规定的一系列指标，包括提供完整的设计原理文档。,AES(2/9),在征集公告发布后，世界各地的密码学家与密码研究机构提交了许多密码算法，,NIST,经过初步的挑选从提交的算法中选出,15,种算法，供全世界的密码学研究人员进行攻击、分析、评价。采用淘汰赛的方法，经过第,2,轮的淘汰，选出,5,个算法，作为,AES Candidate,，供世界各地的密码研究人员进一步研究、分析、攻击、评价。前后历时近,5,年时间，,2001,年,11,月,26,日,NIS T,最后选择了两个比利时的博士提交的,Rijin-dael,算法做为,AES,。,AES(3/9),Rijindael,算法设计的分组长度与密钥长度可以为,128,、,160,、,192,、,224,或,256Bits,。但,AES,强制分组大小为,128Bits,，密钥长度可以为,128,、,192,或,256bits,。分组大小用,N,b,表示，密钥长度用,N,k,表示。它们都必须是,32bits,的倍数。轮数用,N,r,表示。,N,r,需要由,N,b,、,N,k,计算得到。基本结构如下：,密钥扩展和轮运算的元操作,AES,有四种原操作分别是：,(1),异或运算,(2),字节对字节的替换，称为,S,盒运算。,(3),通过循环移动行或列，对字节进行重新排列。,(4),MixColumn,操作。将一个,4,字节的列替换为另一个,4,字节的列。,AES,算法,(4/9),AES,算法以,32,比特为一个基本单元，如果分组包含,4,个,32,比特，就说,N,b,=4,，,AES,的分组大小可以为,128,、,192,或,256,。特别是密钥长度和分组长度可以不同。,AES,强制分组大小为,128,比特，密钥长度可以为,128,、,192,或,256,比特，分别记作,AES-128,、,AES-192,、,AES-256,，相应的分组长度为,4,、,6,或,8,。密钥长度,N,k,的定义与分组长度相同。,AES,算法,循环的轮数用公式,N,r,=6+max (,N,b,N,k,).,大的分组需要大的计算轮数,。,AES,算法用一个矩阵保存运算状态，该矩阵有,4,行，,N,b,列，矩阵的每个元素代表一个字节。将输入的,4,N,b,字节逐个填到状态矩阵中，该状态经过,N,r,轮运算，到达最终状态，逐列读出该矩阵的数据就得到输出结果。,AES,算法,在第一轮之前，两轮之间与,N,r,轮之后，都把经过扩展的密钥的下一个,4,N,b,字节的密钥拿来与状态表进行异或运算。第一轮到,N,r,-1,轮执行相同的操作，第,N,r,轮则跳过其中的部分操作。,AES,算法,上面的基本概述已经描述了,AES,的整个过程，如果搞清了密钥如何扩展、如何进行,S,盒替换、如何做,MixColumn,，那么整个算法就清楚了，现在我们就逐项搞清这些操作。,S-Box Substitute,S-Box,替换是,AES,算法非常更重要的一个步骤。这里的替换使用一个字节代替输入的一个字节，一个字节为,8,比特，表示为两个,4,比特，每,4,个比特用一个,16,进制的数来表示，这样,10110010,就表示为,b2,，那么,b2,用哪一个字节来替换呢？通过下面的表来确定。查表可知为,16,进制的,3,和,7,，换回来就是,00110111,AES,的,S,盒替换,Mix,Column,Mix Column,是将一列用新的一列来替换，给定一个输入列，如何确定一个输出列呢？首先根据一列中每个字节确定一个新的,4,字节列，共确定,4,个,4,字节列，对这四个列进行规定的运算，就可以计算出输出列。,使用查表法进行,Mix Column,操作,Mix Column,的另一种表示,密钥扩展运算,密钥的扩展算法为：首先将初始密钥排列成,N,k,个,4,字节的列，然后周期性地生成后续的,N,k,个列。为生成第,i,个,N,k,列，只需要知道第,i-1,个密钥。那么各密钥的各列如何生成呢？请看下面的图。,AES,生成第,0,个集合的密钥扩展,图中每个,k,表示一个字节，对于密钥长度为,128,的情况，共有四列。,AES,密钥扩展循环执行,N,k,6,时的特殊处理,如果,N,k,6,，前,4,列的生成方法相同，只是生成第,5,列时，必须对第,4,列做一个额外的操作，就是对每个字节都经过,S,盒替换，然后再用于上述其它步骤相同的方法生成后面的各列。,AES,密钥扩展循环执行,N,k,6,时第,4,列的生成方法,元操作的逆运算,异或的逆运算就是它本身；行或列的循环移动的逆运算就是沿相反的方向移动行和列；,S,盒的替换用的是上述,S,盒的逆盒，见下面的表；,MixColumn,的逆运算称为,InvMix,Column,， 与,MixColum,运算相同，只不过是用的是另一个表。,AES,的盒的逆,InvMixColumn,表,BACK,第,5,节,密码运算模式,DES,加密的分组长度为,64,比特，,AES,加密的分组长度为,128,比特。那么当加密的信息长度不是,64,比特或,128,比特时，怎么加密呢？一个很自然的想法当然是重复应用加密。,但重复加密使用用不当可能使安全性降低。,为保证重复加密仍然安全，重复加密必须遵循一定的模式，这就是密码运算模式研究的内容。,运算模式,DES81,中规定了,5,种密码运算模式，分别是：,1.,电子密码本模式,(Electronic Code Book-,ECB,),2.,密码分组连接模式,(Cipher Block Chaining-,CBC,),3. K,比特输出反馈模式,(Output Feed back-,OFB,),4. K,比特密文反馈模式,(Cipher Feedback-,CFB,),5.,计数器模式,(Counter-,CTR,),BACK,电子密码本,ECB,模式,ECB,模式解密,ECB,模式的问题,姓名,(16,字节,),职位,(16,字节,),工资,(8,字节,),John CEO 78964,Smith Vice President 64000,Adam CFO 62000,Bush CIO 60000,ECB,模式的问题,电子密码本模式是最直接、最简单的加密模式，但也是最不安全的加密模式。,ECB,模式有两个严重的问题，能够看到密文的人就能够从重复的分组中分析出一些有用的信息；还可能修改分组或重新排列分组，以便从中获利，或者破坏消息的正确性。,BACK,CBC,模式,密码分组链接模式克服了,ECB,模式的一些缺点，使用,CBC,模式，即使明文中有重复的分组，在密文中也不会出现相同的密文分组。下面给出一个帮助理解,CBC,模式的例子，首先生成,64,比特的随机数，然后将明文分组与随机数进行异或，异或后进行加密，传送密文分组的同时传送随机数。,密码分组链接模式,随机电子码本加密,上述方式的缺点,一个缺点是要传送的信息是实际需要传送信息的两倍。攻击者可能重新排列密文或者删除一部分密文，从而导致无法解密处正确的明文。,CBC,模式用类似的方法解决了,EBC,模式的缺点，只是对第一个分组生成一个随机数，然后用前一个分组的密文，作为后一个分组的随机数。,密码分组链接模式,密码分组链接解密,CBC,模式的缺点,CBC,模式克服了传递密文分组和同样数量的随机数的问题。缺点是攻击者仍然可以对密文分组进行修改，从而影响该分组之后的所有分组的解密。也可以重新排列密文，使整个信息无法解密。,BACK,输出反馈模式,输出反馈模式是序列密码所用的加密模式，这种模式通过将输出的数据串与消息进行异或运算以实现加密。假设有一个随机序列生成器，首先生成,64,比特的随机序列,b,0,，然后用密钥加密,b,0,得到,b,1,等等以此类推，得到一次一密序列,b,0,b,1,b,2,b,3,要加密消息时，只要将消息与足够多的,b,0,b,1,b,2,b,3,进行异或即可。,K,比特输出反馈模式,K,比特输出反馈模式，一次生成,64,比特，但只反馈其中的,k(0k= 64),比特作为生成下一个随机序列的数据与用于加密的数据，其他多余的比特被抛弃。,k,比特,OFB,模式的一种,OFB,的优点,1.,在知道要加密的消息之前就可以预先生成一次一密序列。需要加密的时候只要进行简单的异或即可。,2.,如果密文的一个比特被篡改了，明文也只有相应的比特被篡改。,3.,消息可以是任意长度的数据块，只要收到一组明文，相应的密文就可以立即发送。,BACK,密文反馈模式,CFB,CFB,与,OFB,模式类似，每次生成,k,比特的数据，并与,k,比特的明文异或。与,OFB,不同，移位进入寄存器的,k,比特，是上一次密文分组的,k,比特。这里的,k,可以不是,64,，甚至是,8,都可以。这种模式比较难于篡改，具体情况请看参考书。,密文反馈模式,BACK,计数器模式,计数器模式和,OFB,模式类似，都是生成一次一密序列并与数据进行异或运算实现加密，不同的是,CTR,不是对上一个一次一密序列分组进行加密，以获得的下一个分组，而是逐步增加,IV,，并用它进行加密，进而获得一次一密序列。其优点与,OFB,模式类似,计数器模式,BACK,第,5,节 应用,:,保密通信,(1) Alice & Bob negotiate a cryptosystem E,；,(2) Alice & Bob negotiate a key K,；,(3) Alice computes E,K,(M),，,obtains cipher-text,；,(4) Alice sends cipher-text to Bob,；,(5) Bob,用同样的密钥和算法解密密文，得到原始明文，然后阅读明文。,应用,:,保证消息的完整性,采用,CBC,、,CFB,、,OFB,和,CTR,模式进行加密可以保证窃听者无法解密消息，但我们这里提出的是另一个问题：如果消息是以明文的方式传输的，有没有办法保证消息在传输过程中不被修改。加密的方法可以解决这个问题，就是用,CBC,方式对消息进行加密，但是发送明文时附带发送密文最后一个分组，我们称之为,CBC,留数。,CBC,留数,应用,:,同时保证机密性和完整性,如果要保证消息的保密性可以用,CBC,模式加密，如果要保证消息的完整性可以在发送消息的同时，发送,CBC,留数。如果要同时保证机密性和完整性，很自然的想法是发送加密消息的同时发送,CBC,留数。,但这样是不行的,。那么如果先计算,CBC,留数，并将,CBC,留数合并到明文后面，然后再用,CBC,模式加密合并后的数据，是否可行呢？,也不行,。,带,CBC,留数的,CBC,加密,同时保证机密性和完整性,BACK,第,6,节 对称加密算法的优缺点,(1),对称加密算法用于加密数据时加密速度快，是公钥加密算法速度的,1001000,倍。且对已知明文攻击强度较强。,(2),由于每一对通信实体之间都要共享一个密钥，所以,n,个实体之间通信需要,n(n-1)/2,个密钥，需要的密钥太多。,(3),密钥分配问题难以解决。,BACK,