密码学复习.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.,密码学概述,主动攻击与被动攻击,：对一个保密系统采取截获密文进行分析的这类攻击方法称为,被动攻击,(passive attack),。非法入侵者主动干扰系统，采用,删除、更改、增添、重放,等方法向系统加入假消息，则这种攻击为,主动攻击,(active attack),。,从,攻击效果,看，敌手可能达到以下结果：,（,1,）,完全攻破,。敌手找到了相应的,密钥,，从而可以恢复任意的密文。,（,2,）,部分攻破,。敌手没有找到相应的密钥，但对于给定的密文，敌手能够获得明文的特定信息。,（,3,）,密文识别,。如对于两个给定的不同明文及其中一个明文的密文，敌手能够识别出该密文对应于哪个明文，或者能够识别出给定明文的密文和随机字符串。,第二章 经典密码学,线性同余密码,将,移位密码,和,乘数密码,进行组合就可以得到更多的选择方式，也叫,仿射密码,(affine cipher),。,若选取,k,1,，,k,2,两个参数，其中,(,k,1,26),1,，即,k,1,和,26,互素，,令,C,k,1,m,k,2,mod 26,k,1,1,时便是,Kaiser,变换。,例如,k,1,7,，,k,2,10,，则明文,please send moneys,的对应数据为,16 12 5 1 19 5 19 5 14 4 13 15 14 5 25 19,通过变换,c,7,m,10 mod 26,可得,18 16 19 17 13 19 13 19 4 12 23 11 4 19 3 13,对应的密文为,R P S Q M S M S D L W K D S C M,习题,1,、对于线性替代密码，设已知明码字母,J(9),对应于密文字母,P(15),，即,9k mod 26=15,试计算密钥,k,以破译此密码。,答：,k=9,-1,*15 mod 26 9,-1,mod 26=3 k=3*15 mod 26=19,第四章 序列密码,序列密码的加密和解密就是用一个,随机序列,与,明文,序列叠加产生密文用,同一个随机序列,与,密文,序列叠加来恢复明文。,若设明文为,m,，密钥为,k,，加密后的密文为,c,，则加密变换为：,c,m,k,，解密变换：,m,c,k,，其中,m,，,k,，,c,是,0,、,1,随机序列，,表示模,2,加法运算。,4.1,序列密码的基本概念,图,4.1,序列密码的加密和解密,4.2,密钥流与密钥生成器,一般地，序列密码中对密钥流有如下要求：,（,1,）,极大的周期,。因为,随机序列,是非周期的，而按,任何算法,产生的序列都是,周期,的，因此应要求密钥流具有尽可能大的周期。,（,2,）良好的统计特性。随机序列有,均匀,的,游程分布,。游程指序列中相同符号的连续段，其前后均为异种符号。,如,0 111 0000 10,中,3,个段分别为,长为,3,的,1,游程,、,长为,4,的,0,游程,、长为,1,的,1,游程。,一般要求其在一周期内满足：,同样长度,的,0,游程,和,1,游程,的个数相等，或近似相等。,（,3,）,不能用级数较小的线性移位寄存器近似代替，即要有很高的线性复杂度。,（,4,）用统计方法由密钥序列,k,0,k,1,k,2,k,i,提取,密钥生成器结构,或,种子密钥,的足够信息在,计算上是不可能,的。,目前密钥流生成器大都是基于,移位寄存器的,，这种基于移位寄存器的密钥流序列称为,移位寄存器序列,。,4.3,线性反馈移位寄存器序列,移位寄存器是序列密码产生密钥序列的一个主要组成部分。,GF(2),上一个,n,级反馈移位寄存器由,n,个二元存储器与一个反馈函数,f(a,1,a,2,.a,n,),组成，如图,4.3,所示。,图,4.3 GF(2),上的,n,级反馈移位寄存器,每一个存储器称为移位寄存器的一级。,在任一时刻，这些级的内容构成该反馈移位寄存器的状态。,表,4.1,三级反馈移位寄存器的输出状态表,图,4.4,一个,3,级反馈移位寄存器,这个反馈移位寄存器的状态对应于一个,GF(2),上的,n,维向量，共有,2,n,种可能的状态。,每一时刻的状态可用,n,长序列,a,1,a,2,a,3,a,n,或,n,维行向量,(a,1,a,2a,3,a,n,),表示，其中,a,i,是第,i,级存储器的内容。,每一级存储器,a,i,都将其内容向下一级,a,i,1,传递，并根据存储器当前状态计算,f(a,1,a,2,a,3,a,n,),作为,a,n,下一时间的内容。,函,f(a1,a2,a3,an),称为反馈函数，其中,f(a1,a2,a3,an),是,n,元布尔函数,，即,n,个变元,a1,a2,a3,an,可以独立地取,0,和,1,这两个可能的值,.,最后的函数值也为,0,或,1,。,表,4.1,三级反馈移位寄存器的输出状态表,图,4.4,一个,3,级反馈移位寄存器,三级反馈移位寄存器，其初始状态为,(a1,a2,a3),(1,0,1),，,输出可由表,4.1,求出，其输出序列为,10111011101,，周期为,4,。,如果移位寄存器的反馈函数,f(a,1,a,2,a,n,),是,a,1,a,2,a,n,的线性函数，则称之为,线性反馈移位寄存器,（,LFSR,）。,此时反馈函数,f,可写为,f(a,1,a,2,a,n,),c,n,a,1,c,n1,a,2,c,1,a,n,，,其中常数,c,i,0,或,1,，,是模,2,加法。,线性反馈移位寄存器（,LFSR,）,f(a1,a2,a5),a1,a4,图,4.6,一个,5,级线性反馈移位寄存器,n,级线性反馈移位寄存器最多有,2,n,个,不同的状态。,若其初始状态非,0则其后继状态不会为,0,。,因此,n,级线性反馈移位寄存器的状态周期,2,n,-1,。,其,输出序列的周期,与,状态周期,相等，也,2,n,-1,。,只要选择合适的,反馈函数,便可使序列的周期达到最大值,2,n,-1,，周期达到最大值的序列称为,m,序列,。,反馈函数,:b1+b3,设,n,级线性移位寄存器的输出序列,a,i,满足递推关系,a,k+n,c,1,a,k,n,1,c,2,a,k,n,2,.,c,n,a,k,，,对任何,k1,成立。将这种递推关系用一个一元高次多项式,表示，称这个多项式为线性移位寄存器的,连接多项式,。,4.4,线性移位寄存器的一元多项式表示,反馈函数,:b1+b3,反馈函数,:b1+b2+b3+b4,试题,设,g(x)=x4+x2+1,，,g(x),为,GF,（,2,）上的多项式，以其为连接多项式组成线性移位寄存器。画出逻辑框图。设法遍历其所有状态，并写出其状态变迁及相应的输出序列。,解答,通常采用的方法是，由,线性移位寄存器,(LFSR),和一个,非线性组合函数,即,布尔函数,组合，构成一个,密钥流生成器,，如图,4.2,所示的密钥流生成器。,4.2,密码流生成器,（,a,）由,一个,线性移位寄存器和,一个滤波器,构成。,（,b,）由,多个线性移位寄存器,和,一个组合器,构成。,通常将这类生成器分解成两部分，其中线性移位寄存器部分称为,驱动部分,，另一部分称为,非线性组合部分,。,各自用途,驱动部分：控制生成器的,状态序列,，并为非线性组合部分提供统计性能良好的序列。,如周期很大；分布较随机,非线性部分：将驱动部分所提供的序列,组合,成密码特性好的序列。,可隐蔽驱动序列与密钥,k,之间过分明显的依赖关系,第五章 分组密码,5.2.1 DES,加密算法概述,DES,的加密过程可简单描述为三个阶段：,5.2.5 DES,的安全性,对,DES,安全性的主要争论：,1,、对,DES,的,S,盒、迭代次数、密钥长度等设计准则的争议,2,、,DES,存在着一些弱密钥和半弱密钥,3,、,DES,的,56,位密钥无法抵抗穷举工具,三重,DES,加密,加密：,C,=,E,k1,D,k2,E,k1,P,解密：,P,=,D,k1,E,k2,D,k1,C,三重,DES,加密,两个密钥的三重,DES,称为,加密,-,解密,-,加密方案,，简记为,EDE,(encrypt-decrypt-encrypt),。,此方案已在,ANSI X9.17,和,ISO 8732,标准中采用，并在保密增强邮递,(,PEM,),系统中得到利用。,破译它的穷举密钥搜索量为,2,112,510,35,量级，而用差分分析破译也要超过,10,52,量级。此方案仍有足够的安全性。,三个密钥的三重,DES,已在因特网的许多应用（如,PGP,和,S/MIME,）中被采用,习题,2026/5/25 周一,现代密码学理论与实践05,44,复习,The AES Cipher,2026/5/25 周一,现代密码学理论与实践05,45,/28,第,5,章 高级加密标准之要点,AES,是一种分组密码，用以取代,DES,的商业应用。其分组长度为,128,位，密钥长度为,128,位、,192,位或,256,位,AES,没有使用,Feistel,结构。每轮由四个独立的运算组成：字节代换、置换、有限域上的算术运算，以及与密钥的异或运算,2026/5/25 周一,现代密码学理论与实践05,46,/28,AES,密码,由比利时密码学家,Vincent Rijmen,和,Joan Daemen,设计,分组长度，密钥长度可以是,128/192/256,位之一,2026/5/25 周一,现代密码学理论与实践05,47,/28,2026/5/25 周一,现代密码学理论与实践05,48,/28,2026/5/25 周一,现代密码学理论与实践05,49,/28,GF(2,8,),上的域元素,加法,2026/5/25 周一,现代密码学理论与实践05,50,/28,乘法,在多项式表示中，有限域,GF(2,8,),上的乘法,(,记为,),定义为多项式的乘积模一个次数为,8,的不可约多项式：,m,(,x,)=,x,8+,x,4+,x,3+,x,+1,用十六进制表示该多项式为,011b,。例如，,57 83=c1,，,因为,(x6+x4+x2+x+1)(x7+x+1),=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1,=x13+x11+x9+x8+x6+x5+x4+x3+1,而,x13+x11+x9+x8+x6+x5+x4+x3+1 modulo(x8+x4+x3+x+1)=x7+x6+1,2026/5/25 周一,现代密码学理论与实践05,51,/28,扩展欧几里德算法求逆,元素,01,是乘法单位元。对任意次数小于,8,的非零二元多项式,b(x),，其乘法逆元记为,b,-1,(x),，可通过下述方法找到：使用扩展欧几里德算法计算多项式,a(x),和,cx),使得,b(x)a(x)+m(x)c(x)=1,m,(,x,)=,x,8+,x,4+,x,3+,x,+1,因此,a(x)b(x)mod m(x)=1,意味着,b,-1,(x)=a(x)mod m(x).,由此可见，由所有,256,个可能的字节值组成的集合构成有限域,GF(2,8,),，其每个元素,(,除了,0),都可用扩展欧几里德算法求逆,。,2026/5/25 周一,现代密码学理论与实践05,52,/28,2026/5/25 周一,现代密码学理论与实践05,53,/28,逆字节代换,2026/5/25 周一,现代密码学理论与实践05,54,/28,逆,S,盒,2026/5/25 周一,现代密码学理论与实践05,55,/28,系数在,GF(2,8,),中的多项式,考虑含有,4,个项、且系数为有限域元素的多项式，即,注意本节中的多项式与有限域元素定义中使用的多项式操作起来是不同的，该节中的系数本身就是有限域元素，即字节,(bytes),而不是比特,(bits),2026/5/25 周一,现代密码学理论与实践05,56,/28,c,(,x,)=,a,(,x,),b,(,x,),2026/5/25 周一,现代密码学理论与实践05,57,/28,2026/5/25 周一,现代密码学理论与实践05,58,/28,2026/5/25 周一,现代密码学理论与实践05,59,/28,2026/5/25 周一,现代密码学理论与实践05,60,/28,2026/5/25 周一,现代密码学理论与实践05,61,/28,安全性,暴力攻擊,單就金鑰長度來看，,AES,裡面最少,128,位元的金鑰絕對比,DES,的,56,位元金鑰要安全得 多。,差異攻擊與線性攻擊,AES,系統目前仍然沒有任何已知的差異攻擊或者線性攻擊存在。,2026/5/25 周一,现代密码学理论与实践05,62,/28,国际数据加密算法,IDEA,密码强度,分组长度：,64,位,密钥长度：,128,位,国际数据加密算法,IDEA,IDEA,的基本操作是将两个,16,位的值映射成一个,16,位的值,逐位异或，,整数模,2,16,(65536),加,整数模,2,16,+1(65537),乘,IDEA,的三种基本操作,5.4 IDEA,思想,该算法所依据的设计思想是“混合使用来自不同代数群中的运算”。,该算法所需要的“混乱”可通过连续使用三个“不相容”的群运算于两个,16,比特子块来获得，,并且该算法所选择使用的,密码结构,可提供必要的“扩散”。,5.5 SMS4,密码算法,SMS4,是用于,WAPI,（,WLAN Authentication and Privacy Infrastructure,）的分组密码算法，,是国内官方公布的第一个,商用密码算法,。,SMS4,算法是一个分组算法。,SMS4,算法的分组长度为,128,比特，密钥长度为,128,比特。加密算法与密钥扩展算法都采用,32,轮,非线性迭代结构。,5.6,分组密码的工作模式,分组密码的工作模式就是以该分组密码算法为基础构造的各种密码系统。,模式适用于所有的分组密码，包括,DES,、,AES,和,IDEA,等。,5.6,分组密码的工作模式,5.6.1,电子密码本模式（,ECB,）,5.6.2,密码分组链接模式（,CBC,）,5.6.3,密码反馈模式（,CFB,）,5.6.4,输出反馈模式（,OFB,）,5.6.5,记数模式（,CTR,）,分组链接模式,Cipher Block Chaining(CBC),加密输入是当前明文分组和前一密文分组的异或，形成一条链，使用相同的密钥，这样每个明文分组的加密函数输入与明文分组之间不再有固定的关系,5.6.2,CBC,模式的优点,如果明文分组中的一位出错，将影响该分组的密文及其以后的所有密文分组。,在一定程度上等防止数据篡改,.,但是如果密文序列中丢失,1,位，那么所有后续分组要移动,1,位，并且解密将全部错误。,CBC,模式的缺点,加密的消息的长度只能是分组长度的倍数，不是任意长度的消息。,以,des,为例，必须等到每,8,个字节都接受到之后才能开始加密，否则就不能得到正确的结果。,这在要求实时性比较高的时候就显得不合适了。,CFB,模式的优点和局限,当数据以位或字节形式到达时使用都是适当的,在加密解密两端都需要用分组加密器,明文发生错误时，错误会传播,如果其中有一个字节的密文在传输的时候发生错误（即使是其中的一位），那么它出现在移位寄存器期间解密的,8,个字节的数据都会得不到正确的解密结果，当然，这,8,个字节过去之后，依然可以得到正确的解密结果。,该模式也是比较浪费的，因为在每轮加解密中都丢弃了大部分结果,j,通常为一字节（,8,位）,.,输出反馈模式（,OFB,）,5.6.4,输出反馈模式（,OFB,）,优点是：错误传播小，当前明文分组的错误不会影响后继的密文分组；且密文中的,1,比特错误只导致明文中的,1,个错误；消息长度是任意的。,OFB,模式的缺点是：密文篡改难于检测,适合传输语音图像,计数器模式,Counter(CRT),CTR,的优点,预处理：算法和加密盒的输出不依靠明文和密文的输入,高效,:,可以做并行加密,允许同时处理多块明文,/,密文,第,i,块密文的解密不依赖于第,i-1,块密文，提供很高的随机访问能力,加密算法将仅仅是一系列异或运算，这将极大地提高吞吐量。,仅要求实现加密算法，但不要求实现解密算法。对于,AES,等加,/,解密本质上不同的算法来说，这种简化是巨大的,第六章,Hash,函数,第,1,类生日问题,假设已经知道,A,的生日为某一天，问至少有多少个人在一起时，至少有,1/2,的概率使有一个人和,A,的生日相同？,在此，我们假定一年有,365,天，且所有人的生日均匀分布于,365,天中。,如果已知一个,Hash,函数,H,有,n,个可能的输出，其中,H(x),是一个特定的输出。,随机取,k,个输入，则至少有一个输入,y,使得,H(y),H(x),的概率为,0.5,时，,k,有多大？,第,1,类生日攻击,假设一年有,365,天，每个人的生日均匀分布于,365,天,那么至少有多少个人在一起是，能保证至少有,1/2,的概率存在,2,个人有相同的生日。,第,2,类生日问题,若一文件,m,的,Hash,值,H(m),为,n,比特，试问至少有多少的文件在一起，有两个文件的,Hash,值以至少,1/2,的概率相同。,第,2,类生日攻击MD5,的安全性,MD5,算法,抗密码分析的能力较弱,，对,MD5,的生日攻击所需代价是,需要试验,2,64,个消息,。,2004,年,8,月,17,日,，在美国加州圣巴巴拉召开的美密会（,Crypto2004,）上，中国的,王小云,、冯登国、来学嘉、于红波,4,位学者宣布，,只需,1,小时就可找出,MD5,的碰撞,。（,利用差分分析）,图,6.6 SHA-1,消息处理框图,SHA-1,与,MD5,的比较,安全性：,SHA-1,的报文摘要比,MD5,的,长,32,比特,抗密码分析攻击的强度，,SHA-1,似乎高于,MD5,效率：,MD5,效率比,SHA-1,高。,MD5,已被破解；,SHA-1,目前还可以应用,总的说来，,SHA-1,的安全性是以牺牲效率为代价的，类似于分组密码的加密,第七章 消息认证码,MAC,实质上是一个,双方共享的密钥,k,和消息,m,作为输入的函数,记为,MAC=C,K,(M),MAC-”,带密钥的,hash,函数”,MAC:,消息认证码是什么,一种是基于分组密码的,一种是基于带密钥的,Hash,函数的。,7.1,消息认证码的构造,基于分组密码的,MAC,CBC-MAC,（,1,）接收者确信消息未被更改过。,（,2,）接收者确信消息来自所谓的发送者。,消息认证码实现认证,公钥密码体制的基本概念,公钥密码所依赖的数学难题,背包问题,二次剩余问题,模,n,的平方根问题,多变量方程系统,格规约,:NTRU,大整数分解问题,（,The Integer Factorization Problem,RSA,体制,）,离散对数问题：,有限域的,乘法群上的离散对数问题,（,The Discrete Logarithm Problem,ELGamal,体制,）,定义在有限域的,椭圆曲线上的离散对数问题,（,The Elliptic Curve Discrete Logarithm Problem,，类比的,ELGamal,体制）,RSA,算法,概况：,MIT,三位年青数学家,R.L.Rivest,，,A.Shamir,和,L.Adleman,在,1978,年发现了一种,用数论构造双钥体制,的方法，称作,MIT,体制，后来被广泛称之为,RSA,体制,。,它既可用于加密、又可用于数字签名。,RSA,算法的,安全性基于,数论中,大整数分解的困难性,。,2,、,RSA,算法,算法描述,密钥产生,KG(),：,独立地选取两大素数,p,和,q,(,各,100,200,位十进制数字,),计算,n,=,p,q,，其欧拉函数值,(,n,)=(,p,1)(,q,1),随机选一整数,e,，,1,e,(,n,),，,gcd(,(,n,),e,)=1,在模,(,n,),下，计算,e,的有逆元,d=e,-1,mod,(,n,),以,n,，,e,为公钥。私钥为,d,。,(,p,q不再需要，可以销毁。,),算法描述,加密,E(),和解密,D(),：,加密,将明文分组，各组对应的十进制数小于,n,c=m,e,mod,n,解密,m=c,d,mod,n,3,、,RSA,的安全性,RSA,的安全性是基于分解大整数的困难性假定（尚未证明分解大整数是,NP,问题）,如果分解,n=p,q,，则立即获得,(,n,)=(,p,1)(,q,1),，从而能够确定,e,的模,(,n,),乘法逆,d,RSA-129,历时,8,个月被于,1996,年,4,月被成功分解，,RSA-130,于,1996,年,4,月被成功分解,n,的长度应该介于,1024bit,到,2048bit,之间,1,、大素数的产生,试除法,费马法,Rabin-Miller,算法,未通过检测的整数一定是合数,但，并非所有通过检测的整数都是素数,实用最广泛，是一种概率算法,2,、求乘法逆元：扩展的欧几里得算法,RSA,的实现,3,、快速指数计算,利用反复平方乘算法,每次乘法运算后就取模,3,、椭圆曲线密码体制的优点,安全性高（椭圆曲线群上的离散对数更难计算）,攻击有限域上的离散对数可用指数积分法，运算复杂度为亚指数复杂。对,ECC,上离散对数攻击并不有效。,攻击,ECC,上离散对数问题的方法只有大步小步法，复杂度为指数。因此,ECC,上的密码体制比基于有限域上离散对数问题的公钥体制更安全,数字签名,ElGamal,数字签名,公钥数学基础,Euler,定理,-,费马定理,Euler,定理,:,对任意互素的,a,和,n,有,a,(n),mod n=1,费马定理,:a,p-1,mod p=1,密码学考试感想,一简答,1,密码体制,2,什么是强无碰撞的散列函数，解释强无碰撞与弱无碰撞的含义,二,RSA,密码，给定,N,11*7,，从,e1=3,和,e2=17,，选择一个合适的公钥，并计算出私钥,三 实数域上的椭圆曲线，即由,y2=x3-36x,定义的曲线，推导曲线上点的加法公式，并已知,P=(-3,9),Q=(-2,8),，计算,P+Q,和,2P,。（课后作业的改造）,四 简述,AES,的特征，它与,DES,的本质区别是什么？,五 证明由如下方式中构造的,Hash,函数是强无碰撞的：,q=(p-1)/2,，,p,和,q,都是素数，,是本原根，,=a(a,是保密指数,),，,h(x1,x2)=x1x2,（课件中有详细证明）。,六 古典密码：用,Vigenere Cipher,解密一串密文，密钥由六个字母组成：,H C P I R E,。,做完考题，感触很深：,1,第五题要证明,Hash,函数强无碰撞，没有做完全，让我最郁闷的是，昨天晚上，我把这个证明在纸上写了一遍，感觉没有什么问题了。可是，今天一考试，又傻了，不会做了。看来我没有理解证明的原理，对证明过程没有宏观的把握，还没有完全明白为什么要这样证明，昨天晚上我能写下来，仅仅是强记的而已。,2,第六题没有做对，同样让我一样郁闷，我没有看清题目，我以为密钥就是,HCPIRE,，而不知道应该对这六个字母进行组合；我太笨了，做题的时候还纳闷呢，这明明是,cipher,单词的字母嘛，怎么要把它的顺序打乱来做密钥呢。原来题目考的就是要对这六个字母重新排列，恢复出,cipher,，看来我是傻呼呼地到家了。,3,时间没有合理安排好，前面时间用得多，到后面就没有时间做了。之所以第五题与第六题没有做好，很大原因也是时间到后面不够了，如果第六题放在前面的话，我在很大概率上能做出来，可惜到了后来没有时间仔细看题目了；还有第五题也是，如果给我足够的时间，我应该能把卡住的问题解决。唉，以后考试得合理安排时间，不能在前面慢慢磨蹭啊。,4,考了多少分并不重要，重要的是通过考试能够发现自己学习的方式和习惯的不足之处，接下来还有信息安全数学基础，形式化方法，信息系统安全的考试，我得借鉴此次教训，把基础打扎实一些，不能再忽悠自己了，不要浮躁，要做到知其然知其所以然。,