分组密码技术讲义

,1,1.1,1.1.1,1.1.1,1.1.1.1,-,57,-,第二章 分组密码技术,第二章 分组密码技术,1,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,密码学的历史,密码学从形成到发展经历了,5,个重要阶段,手工阶段,机械阶段,电气阶段,计算机阶段,网络化阶段。,第二章 分组密码技术,2,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,保密系统模型,熵的概念,联合熵,条件熵,理论保密性,“一次一密”的密码系统就是这样的无条件安全的密码系统。,实际保密性,一个密码系统是计算上安全的是指，利用最好的算法（已知或者是未知的）来破解这个密码系统需要的计算量是,O(,N,),的，,N,是一个很大的数。的计算量超过了攻击者所能控制的所有计算资源在合理的时间内能够完成的计算量。所以计算上安全也称为实际的保密性。,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,第二章 分组密码技术,3,什么是分组密码,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,第二章 分组密码技术,4,分组加密的评价标准,评价分组加密算法及其工作模式的一般标准是：,预估的安全水平（如破译需要的密文数量等）,密钥的有效位长,分组大小,加密映射的复杂性,数据的扩张（,Data Expansion,）,错误的扩散（,Diffusion,）,/,传播（,Propagation,）,分组加密的一般结构,Feistel,网络结构,SP,网络结构,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,第二章 分组密码技术,5,DES,概述,分组加密算法：明文和密文为64位分组长度；,对称算法：加密和解密除密钥编排不同外，使用同一算法；,密钥长度：56位，但每个第8位为奇偶校验位，可忽略；,密钥可为任意的56位数，但存在弱密钥，容易避开；,采用混乱和扩散的组合，每个组合先替代后置换，共16轮；,只使用了标准的算术和逻辑运算，易于实现；,DES,加密算法描述,DES,加密算法的一般描述,初始置换,IP,和初始逆置换,IP,1,DES,的一轮叠代,L,i-,1,（32,比特）,R,i-,1,（32,比特）,L,i,（32,比特）,48比特寄存器,选择扩展运算,E,48比特寄存器,子密钥,K,i,（48,比特）,32比特寄存器,选择压缩运算,S,置换运算,P,R,i,（32,比特）,L,i,=,R,i-,1,L,i,= R,i-1,;,R,i,= L,i-1,F(R,i-1,K,i,),扩展置换-盒32位扩展到48位,扩展,压缩替代,S-,盒48位压缩到32位,压缩替代,S-,盒,S-,盒1,S-,盒4,S-,盒3,S-,盒2,S-,盒5,S-,盒6,S-,盒7,S-,盒8,S-,盒的构造,S-,盒的构造要求,S-,盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度；,提供了密码算法所必须的混乱作用；,如何全面准确地度量,S-,盒的密码强度和设计有效的,S-,盒是分组密码设计和分析中的难题；,非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门；,S-,盒的构造准则,S,盒的每一行,应该包括所有16种比特组合,；,没有一个,S,盒是它输入变量的线性函数；,改变,S,盒的一个输入位至少要引起两位的输出改变；,S盒的两个输入刚好在两个中间比特不同，则输出必须至少两个比特不同,；,S盒的两个输入在前两位不同，最后两位相同，两个输出必须不同；,P-,盒的构造准则,每个,S,盒输出的四个比特被分布开，一边其中的两个影响下次循环的中间比特，另外两个影响两端比特；,每个,S,盒输出的四个比特影响下个循环6个不同的,S,盒；,P,置换的目的是增强算法的扩散特性，提供,雪崩效应（,明文或密钥的一个比特的变动都引起密文许多比特的变化）,DES,中的子密钥的生成,DES,的强度分析,循环次数：,循环次数越多，密码分析难度越大，循环次数的选择准则是密码分析工作量大于简单的穷举式密钥搜索工作量；,函数,F：,依赖于,S,盒的使用，非线性程度越大，密码分析难度越大，还应具有良好雪崩性质；,密钥调度算法：,选择子密钥时要使得推测各个子密钥和由此推出主密钥的难度尽可能大；,IDEA ( International Data Encryption Algorithm),瑞士联邦理工学院,Xuejia,Lai,和,James Massey,提出；,IDEA,是对称、分组密码算法，输入明文为,64,位，密钥为,128,位，生成的密文为,64,位，它的设计目标：,（1）密码强度：扰乱通过三种操作实现（逐位异或，整数模相加或乘积）；,（2）使用方便性：设计考虑到硬件和软件的实现；,IDEA,是一种相对较新的算法，虽有坚实理论基础，但仍应谨慎使用,(,尽管该算法已被证明可对抗差分分析和线性分析,),；,IDEA,是一种专利算法,(,在欧洲和美国,),，专利由,Ascom,-Tech AG,拥有，,PGP,中已实现了,IDEA,；,IDEA,框图,IDEA,轮函数,AES,AES,是,DES,的替代品，希望能有20-30年的使用寿命。在,评选过程中，最后的,5,个候选算法：,Mars, RC6,Rijndael, Serpent,和,Twofish,。,2000年10月，,Rijndael,算法被选中,；,Rijndael,算法的原型是,Square,算法，其设计策略是宽轨迹策略,(Wide Trail Strategy),，以针对差分分析和线性分析；,Rijndael,是迭代分组密码，其分,组长度和密钥长度都是可变的，为了满足,AES,的要求，分组长度为,128bit,，密码长度为,128/192/256bit,，相应的轮数,r,为,10/12/14；,2001年11月，美国,NIST,发布标准,FIPS PUB 197；,AES,框图,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,第二章 分组密码技术,6,对分组密码的攻击,穷举分析,差分分析,线性分析,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,第二章 分组密码技术,7,分组密码的工作模式,电子密码本,ECB (Electronic Codebook Mode),明文每次处理64,bit，,每个明文分组用同一密钥加密；,密码分组链接,CBC (Cipher Block Chaining),输入是当前明文和前边明文的异或，每个分组使用相同密码,；,密码反馈,CFB (Cipher Feedback Mode),分组密码,流密码,；,输出反馈,OFB (Output Feedback Mode),分组密码,流密码,；,电子密码本,ECB,ECB,的特点,简单有效，可以并行实现；,不能隐藏明文的模式信息，相同明文,生成,相同密文，,同样信息多次出现造成泄漏；,对明文的主动攻击是可能的信息块可被替换、重排、删除、重放；,误差传递：密文块损坏,仅,对应明文块损坏；,适合于传输短信息；,密码分组链接,CBC,CBC,的特点,没有已知的并行实现算法；,能隐藏明文的模式信息，相同明文,生成,不同密文，初始化向量,IV,可以用来改变第一块；,对明文的主动攻击是不容易的，信息块不容易被替换、重排、删除、重放；,误差传递：密文块损坏,两,明文,块,损坏；,安全性好于,ECB，,适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如,SSL、IPSec,；,密码反馈,CFB,加密,C,i,=P,i,(,E,K,(S,i,),的高j位),;,S,i+1,=(S,i,j)|C,i,密码反馈,CFB,解密,P,i,=C,i,(,E,K,(S,i,),的高j位),;,S,i+1,=(S,i,j)|C,i,CFB,的特点,分组密码,流密码,;,没有已知的并行实现算法;,隐藏了明文模式;,需要共同的移位寄存器初始值,IV;,对于不同的消息，,IV,必须唯一;,误差传递：一个单元损坏影响多个单元;,输出反馈,OFB,加密,C,i,=P,i,(,E,K,(S,i,),的高j位),；,S,i+1,=(S,i,j)|,(,E,K,(S,i,),的高j位),输出反馈,OFB,解密,P,i,=C,i,(,E,K,(S,i,),的高j位),;,S,i+1,=(S,i,j)|,(,E,K,(S,i,),的高j位),OFB,的特点,分组密码,流密码；,没有已知的并行实现算法；,隐藏了明文模式；,需要共同的移位寄存器初始值,IV,对于不同的消息，,IV,必须唯一；,误差传递：一个单元损坏只影响对应单元；,对明文的主动攻击可能，信息块可被替换、重排、删除、重放；,安全性较,CFB,差；,密码学的历史,香农安全理论,分组密码的基本概念,分组密码设计原理,典型的分组密码算法,对分组密码的攻击,分组密码的工作模式,多重加密,第二章 分组密码技术,8,DES,的密钥长度分析,关于,DES,算法的另一个最有争议的问题就是担心实际56比特的密钥长度不足以抵御穷举式攻击，因为密钥量只有 个,强力攻击：平均2,55,次尝试,差分密码分析法：平均2,47,次尝试,线性密码分析法：平均2,43,次尝试,早在1977年，,Diffie,和,Hellman,已建议制造一个每秒能测试100万个密钥的,VLSI,芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元；,DES,的密钥长度分析,1990年，以色列密码学家,Eli,Biham,和,Adi,Shamir,提出了差分密码分析法，可对,DES,进行选择明文攻击；,在,CRYPTO93,上，,Session,和,Wiener,给出了基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到,DES,密钥；,美国克罗拉多洲的程序员,Verser,从1997年2月18日起，用了96天时间，在,Internet,上数万名志愿者的协同工作下，成功地找到了,DES,的密钥，赢得了悬赏的1万美元；,DES,的密钥长度分析,1998年7月电子前沿基金会（,EFF）,使用一台25万美元的电脑在56小时内破译了56比特密钥的,DES；,1999,年1月,RSA,数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个,DES,的密钥；,两重,DES,E,K2,E,K1,P=E,K3,P ?,中途攻击,C=E,K2,E,K1,P,X=E,K1,P=D,K2,C,三重,DES,两个密钥的三重,DES,用于密钥管理标准,ANS X9.17,和,ISO 8732 2,中；,三个密钥的三重,DES,用于,PGP,和,S/MIME；,进阶阅读和习题,