信息安全数学基础幻灯片.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,中南大学信息科学与工程学院计算机系,段桂华,2010,年,9,月,信息安全数学基础,信息科学与工程学院,网络信息的安全威胁,网上犯罪形势不容乐观；,有害信息污染严重；,网络病毒的蔓延和破坏；,网上黑客无孔不入；,机要信息流失与信息间谍潜入；,网络安全产品的自控权；,信息战的阴影不可忽视。,引 言,网络通信的困境,引 言,信息完整,用户认证,网站认证,密钥管理,不可抵赖,数据安全,我们要保护什么呢？,引 言,网络安全体系的五类服务,访问控制技术,身份鉴别技术,加密技术,信息鉴别技术,访问控制服务,对象认证服务,保密性服务,完整性服务,防抵赖服务,引 言,网络安全体系的五类服务,访问控制服务,：,根据实体身份决定其访问权限,；,身份鉴别服务,：,消息来源确认、防假冒、证明你,是否就是你所声明的你；,保密性服务,：,利用加密技术将消息加密，非授权,人无法识别信息,；,数据完整性服务,：,防止消息被篡改，证明消息与,过程的正确性,；,防抵赖服务,：,阻止你或其他主体对所作所为的进,行否认的服务，可确认、无法抵赖,。,引 言,引 言,解决方法：,加密,如何实现保密性？,密码分析,公共网络,Alice,Bob,加密,密钥,解密,密钥,Eve,引 言,解决方法：,数字摘要,如何实现完整性？,无法篡改,z,消息篡改,公共网络,Alice,Bob,m,z,m,z,z=h,k,(m),y=h,k,(,m,),Eve,如果,y,z,m,被篡改,引 言,解决方法：,数字签名,如何实现不可否认性？,否认,公共网络,Alice,Bob,Trent,谁是正确的？,举报,引 言,解决方法：,密码技术,公共网络,Alice,Bob,假冒,Eve,身份鉴别：,就是确认实体是它所声明的，身份鉴别服务提供关于某个实体身份的保证，以对抗假冒攻击。,如何鉴别通信对象的身份？,本课程的相关知识点,简单的密码学基础：,密码技术是信息安全的核心技术；,需要掌握一些密码学基础知识。,相关的数学知识：,密码技术的实现依赖于数学知识；,掌握密码技术涉及的相应数学基础知识点。,参考教材：,(1),密码学导引,机械工业出版社,Paul Garrett,著,吴世忠等译；,(2),信息安全数学基础,武汉大学出版社,李继国等,主编。,引 言,什么是密码技术？,窃听,公共网络,Alice,Bob,Eve,篡改,伪造,加密,密钥,解密,密钥,密文,密码学是一门古老而深奥的学科,包括密码编码学和密码分析学,;,通信双方按照某种约定将消息的原形隐藏,。,密码系统,:,明文,密文,加解密算法,密钥,。,引 言,密码学的起源与发展,三个阶段：,1949,年之前：密码学是一门艺术；,1949,1975,年：密码学成为科学；,1976,年以后：密码学的新方向公钥密码学。,1949,年之前,(,手工阶段的初级形式,),隐写术：隐形墨水、字符格式的变化、图像；,举例：,芦花丛中一扁舟，俊杰俄从此地游；,义士若能知此理，反躬难逃可无忧。,258 71539 258 314697 314697 15358 24862 17893,引 言,19491975,年,(,机械阶段,),：现代密码出现,1949,年香农,Shannon,提出“保密系统信息理论”；,提出：数据的安全基于密钥而不是密码算法。,1976,年以后,(,计算机阶段,),：公钥密码诞生,1976,年,Diffie&Hellman,的“,New Directions in Cryptography”,提出了不对称密钥密码；,1977,年,Rivest,Shamir&Adleman,提出了,RSA,公钥算法；,90,年代出现椭圆曲线,ECC,等其他公钥算法。,引 言,对称密钥密码算法进一步发展,1977,年,DES,正式成为标准；,80,年代出现“过渡性”的“,post DES”,算法，如,IDEA,、,RCx,、,CAST,等；,90,年代对称密钥密码进一步成熟，,Rijndael,、,RC6,、,MARS,、,Twofish,、,Serpent,等出现；,2001,年,Rijndael,成为,DES,的替代者,AES,。,2004,年,6,月美国,NIST,提出最新信息加密技术,-,量子密码。,2004,年山东大学王小云教授成功破解处理电子签名的,MD5,。,引 言,密码算法的分类,按照保密的内容分,受限制的算法：保密性基于保持算法的秘密。,基于密钥的算法：保密性基于密钥的保密。,Kerchoffs,原则,1883,年,Kerchoffs,第一次明确提出了编码的原则：,保密性完全依赖于密钥，算法应该公开。,这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为,古典密码,和,现代密码,的分界线。,引 言,基于密钥的算法，按照密钥的特点分类：,对称密码算法：,又称秘密密钥算法或单密钥算法，加密密钥和解密密钥相同，或可以容易地从一个推出另一个。,特点：,加密速度快；密钥管理复杂，主要用于加密信息。,非对称密钥算法：,又称公开密钥算法，加密密钥和解密密钥不相同，而且很难从一个推出另一个。,特点：,密钥管理简单，但加密速度慢，用于加密会话密钥和用于数字签名。,实际网络应用中，常采用非对称密码来交换对称密码算法的密钥。,引 言,经典的,古典密码,算法主要有：,代替密码：,将明文字符用另外的字符代替，典型的有恺撒密码、仿射密码、维吉尼亚密码等；,换位密码：,明文的字母保持相同，但顺序打乱。,经典的,现代密码,算法有很多种，最通用的有：,DES,：,数据加密标准，对称密码算法，用于加密；,AES:,高级加密标准，对称密码算法，用于加密；,引 言,RSA,：,最流行的公钥密码算法，加密和数字签名；,ECC,：,椭圆曲线密码，采用,ElGamal,算法，公钥密码算法，安全性高，密钥量小，灵活性好；,DSA,：,数字签名算法，是数字签名的一部分，公钥密码算法，数字签名。,MD5(SHA-1),：,数字摘要算法，数字签名，保证消息的完整性。,引 言,理论安全：,攻击者无论截获多少密文，都无法得到足够的信息来唯一地决定明文。,Shannon,用理论证明：欲达理论安全，加密密钥长度必须大于等于明文长度，密钥只用一次，用完即丢，即一次一密密码本，不实用。,实际安全：,如果攻击者拥有无限资源，任何密码系统都是可以被破译的；但是，在有限的资源范围内，攻击者都不能通过系统地分析方法来破解系统，则称这个系统是计算上安全的或破译这个系统是计算上不可行。,引 言,密码系统的安全,四种基本攻击类型：,唯密文攻击：,攻击者只有一些密文；,已知明文攻击：,攻击者知道一些明文密文对；,选择明文攻击：,攻击者可以选择明文密文对；,针对密钥的攻击：,主要是针对公钥密码系统。,穷举攻击：,攻击者采用尝试方法穷举可能的密钥。,当密钥空间较小时很有效。,字典攻击,是,利用一些常用的单词进行组合。,基本要求：,任何一种加密系统都必须能够对抗唯,密文攻击。,目前的标准是：,一个密码系统应当能够对抗选择,明文攻击。,引 言,密码系统的攻击,第一章 简单密码,经典的简单密码：,移位密码、一次一密乱码本、仿射密码。,1.1,移位密码,1.Caesar,密码：,最简单的移位密码。,原理：,将消息中的每个字母前移,3,位或者后,移,3,位。,举例：,all of gaul is devided into three parts,DOO RI JDXO LU GLYLGHG LQWR WKUHH SDUWU,2.,移位密码：,改进,Caesar,密码：,发送方和接收方协商一个密钥,k,，,1k25,，代表移动位数。,3.,攻击：,穷举攻击：,25,种可能的密钥,(,密钥空间,),；,4.,特点：,对称密码：,加密密钥和解密密钥相同；,单表代替密码：,所有的明文字母用同一种方法,加密，即子密钥相同。,1.2,约简,/,整除算法,1.n,模,m,的约简：,n,除以,m,的余数,r,，,0r,|m|,记作：,r=n%m,或者,r=n mod m,，,m,称为模数。,计算：,设,a=|n|%|m|,，则,当,n0,时，,n%m=|m|-a,；,当,m0,时，,n%m=n%|m|,。,第一章 简单密码,举例：,-10%7,：,10%(-7),：,-10%(-7),：,4,，,因为,-10=7(-2)+,4,3,，,因为,10=-7(-1)+,3,4,，,因为,-10=-72+,4,注意：,任何整数模,m,的约简都是非负数。,2.,乘法逆,n,模,m,的乘法逆,t,满足：,nt%m=1,记作：,t=n,-1,%m,举例：,2,-1,%5,的值为：,3,-1,%100,的值为：,3,，,因为,3,2%5=1,67,，,因为,67,3%100=1,第一章 简单密码,4.,乘法逆元的计算,(1),穷举法：寻找满足条件的数。,技巧：若,tn%m=-1,，,则,n,-1,%m=m-t,。,33,3%100=-1,，,所以,3,-1,%100,的值为,67,。,第一章 简单密码,3.,命题,设,m,0,1,为整数，,x,与,m,互素，则,x,有模,m,的,乘法逆元。特别地，满足表达式,ax+bm=1,的任意,整数,a,就是一个,x,模,m,的乘法逆元。,假如,y,是,x,模,m,的乘法逆元，对于,y,，若,m|y-y,，,那么,y,也是,x,模,m,的乘法逆元；反之亦然。,(2),欧几里德算法,：,举例：,23,-1,%100,方法：,100-,4,23=8,23-,2,8=7,8-,1,7=,1,7-,7,1=0,所以：,1,=,3,100-,13,23,1,=-,13,23%100 23,-1,%100=,-13,=,87,1,=,3,100%23 100,-1,%23=8,-1,%23=,3,算法：,1,=8-,1,7,=8-,1,(23-,2,8),=,3,8-,1,23,=,3,(100-,4,23)-,1,23,=,3,100-,13,23,1 -1 -1 3 3-13,0 1,1,-7,0 1,1,-1,0 1,1,-2,0 1,1,-4,100,23,1,0,=,所以：,3,100-,13,23=,1,第一章 简单密码,1.3,欧几里得算法,用以寻找两个整数,m,和,n,的最大公因子,d,。,使用该算法将,x,和,y,的最大公因子表示为：,ax+by=gcd(x,y),的形式。,1.,举例描述,两个整数,513,和,614,614-1513=101,513-5101=8,101-128=5,8-15=3,5-13=2,3-12=1,2.,寻找整数,a,b,1=3-1,2=3-1,(5-1,3),=-1,5+2,3=-1,5+2,(8-1,5),=2,8-3,5=2,8-3,(101-12,8),=-3,101+38,8,=-3,101+38,(513-5,101),=38,513-193,101,=38,513-193,(614-1,513),=-193,614+231,513,最大公因子为,1,193614+231513=1,第一章 简单密码,2.,乘法逆元的计算,两个整数,x,和,y,x-yq,1,=r,1,x,1,-y,1,q,2,=r,2,x,2,-y,2,q,3,=r,3,x,n-1,-y,n-1,q,n,=0,x,n,y,n,结论：,当,x,和,y,互素时，,gcd(x,y),为,1,，即可得到,x,-1,%y,为,a,，,y,-1,%x,为,b,。,第一章 简单密码,3.,举例,所以：,21,-1,%25,的结果为,6,。,例,2,：求,1234,-1,%4321,例,1,：求,21,-1,%25,解：,25-121=4,21-54=1,4-14=0,第一章 简单密码,3.,命题：,(1),给定一非零整数,m,和任意整数,n,，存在唯一的,整数,q,和,r,，使得,0r,|m|,且,n=qm+r,(2),设,n,和,N,为两个整数，对某个整数,k,有,N=kn,，,则对任意整数,x,有：,(x%N)%n=x%n,1.3,一次一密乱码本,OTP,1.,思想：,密钥与消息一样长，且只能使用一次。,2.,工作原理：,消息长度为,n,，,x=(x,1,x,2,x,n,),；,随机密钥：,k=(k,1,k,2,k,n,),；,加密：,E,k,(x)=(x,1,+k,1,)%26,(x,n,+k,n,)%26),解密：,D,k,(y)=(y,1,-k,1,)%26,(y,n,-k,n,)%26),第一章 简单密码,3.,举例：,消息：,n,e v e r m o,r,e,密钥：,e,x c e l s i,o,r,密文：,R,B X I C E W,F,V,R(17)=(n(13)+e(4)%26,F(5)=(r(17)+o(14)%26,4.,特点：,密钥的产生与分发管理复杂；,对称密码；,多表代替密码：明文中不同位置的字母采用的加,密密钥不同。,第一章 简单密码,1.4,仿射密码,1.,思想：,对移位密码进行改进，扩大密钥空间。,2.,原理：,加密：,E,a,b,(x)=(a,x+b)%26 0a,b,25,解密：,D,a,b,(y)=,3.,特点：,(1),当,a=1,时为移位密码；,(2),加密密钥为,(a,b),；解密密钥为,(a,-1,-a,-1,b),；,(3),单表代替密码；,(4),对称密码：由加密密钥可以推导出解密密钥；,第一章 简单密码,(5),密钥空间：由于,a,-1,必须存在，所以可能的密钥数,为,1226-1=311,个。,第一章 简单密码,4.,攻击方法：,穷举攻击：,尝试,311,个可能的密钥。,选择明文攻击：,E,a,b,(0)=(a,0+b)%26,E,a,b,(1)=(a1+b)%26,已知明文攻击：,E,a,b,(x)=(a,x+b)%26,E,a,b,(y)=(ay+b)%26,唯密文攻击：,字母频率攻击。,a=(x-y),-1,(,E,a,b,(x)-E,a,b,(y)%26,b=(E,a,b,(x)-ax)%26,b=,E,a,b,(0),a=(E,a,b,(1)-b)%26,第一章 简单密码,举例：,已知明文：,m,eet me,a,t mi,d,nig,h,t,假设密文：,H,NNS HN,D,S HX,E,QXF,O,S,(1),选择明文攻击,攻击者选择：,a(0),D(3),d(3)E(4),第一章 简单密码,E,a,b,(0)=(a,0+b)%26,E,a,b,(3)=(a3+b)%26,3=,b%26,4=(3a+b)%26,b=3,a=3,-1,%26=9,加密密钥,a,-1,%26=3,-a,-1,b=-33%26=17,解密密钥,(2),已知明文攻击,攻击者获得：,m(12),H(7),h(7)O(14),E,a,b,(12)=(a,12+b)%26,E,a,b,(7)=(a7+b)%26,7=(12a+,b)%26,14=(7a+b)%26,a=(-75,-1,)%26=9,b=(14-79)%26=3,加密密钥,第一章 简单密码,第一章 简单密码,1.5 Vigenere,密码,1.,特点：,具有相对较大的密钥空间；,对称密码；多表代替密码；,有周期性的弱点：若两个字符出现的间隔是密钥长度的倍数，则它们将以同样的方法加密。,2.,加密和解密的原理：,(1),密钥是一个字符序列：,k=(k,0,k,1,k,m-1,),；,明文,x=(x,0,x,1,x,N,),被分成长度为,m,的段。,(2),加密函数：,E,k,(x,0,x,1,x,N,)=(y,0,y,1,y,N,),y,i,=(x,i,+k,i%m,)%26,解密函数：,D,k,(y,0,y,1,y,N,)=(x,0,x,1,x,N,),x,i,=(y,i,-k,i%m,)%26,第一章 简单密码,3.,多轮加密,(3),举例：,明文,m=meet me in the alley after midnight,密钥,k=,goph er,go phe rgoph ergop hergophe,密文,c=,SSTA QV OB IOI RRZTF EWZSG TMUTWVOX,2,12,17,20,若一个明文使用密钥长度为,m,的维吉尼亚密码加密，得到的密文再用长度为,n,的密钥加密，其结果与用长度为,lcm(m,n),的维吉尼亚密码加密的结果一样。,若,m,n,互素，则,lcm(m,n)=mxn,，密钥长度很大。,第一章 简单密码,1.6,最小公倍数,lcm,和最大公约数,gcd,1.,定义,对于两个整数,d,n,，若,d,整除,n,，或者说,d,是,n,的一个因子，记作：,d|n,设,m,n,是两个非,0,的整数，则最大公约数,d,为最,大的正整数，使得,d|m,和,d|n,，记作,d=gcd(m,n),；,最小公倍数,N,为最小的正整数，使得,m|N,和,n|N,，,记作,N=lcm(m,n),。,2.,定理,m,n,的最大公约数,gcd(m,n),具有这样的特性：对于,m,n,的每一个公因子,e,满足,e|gcd(m,n),；,m,n,的最小公倍数,lcm(m,n),具有这样的特性：对于,m,n,的每一个公倍数,N,满足,lcm(m,n)|N,；,第一章 简单密码,3.,素数,素数,p,是那些不存在因子,d,的整数,1d,p,1/2,；,定理：,每一个正整数都可以分解为素数的乘积，,而且这种分解是唯一的。,12=2,2,x3,35=5x7,(1),对于每一个素数,p,，整除,gcd(m,n),的,p,的方幂，是既整除,m,又整除,n,的,p,的方幂的最小值。,(2),两个方幂中较大的一个便组成了最小公倍数。,举例：,3960=2,3,x3,2,x5x11,400=2,4,x5,2,则：,gcd(3960,400)=2,3,x5=40,lcm(3960,400)=2,4,x3,2,x5,2,x11=39600,第一章 简单密码,1.7,生日攻击,1.,命题,在实验,x,中，不同结果,x,1,x,2,x,n,的概率分别为,p(x,1,)=p,1,p(x,n,)=p,n,。集合,A,为样本空间,x,1,x,n,的一个子集，且有,p(A)=p,。设,0kN,，则,N,次实验中,A,恰好出现,k,次的概率为：,举例,：,投币。假设一枚公平的硬币朝上或朝下的,几率是相等的，且每次投币是独立的。,分析：,记录一个,n,次投掷的过程：,2,n,任何单个序列出现的概率是,1/2,n,n,次投掷恰好有,k,次正面朝上的概率是：,10,次投掷中：,恰好,5,次正面朝上的概率为：,252/1024,1/4,6-4,或者,4-6,组合的概率是：,420/10242/5,2.,生日攻击,设,=1,2,N,为所有原子事件的样本空间，,p(i)=1/N,。,n,次实验后至少,2,次结果相同的概率至少为：,1-e,-n(n-1)/2N,。因此，对于,出现两次相同结果的概率至少为,1/2,。,第一章 简单密码,证明：,先计算出没有两种完全相同结果出现的概,率,p,，则出现两次相同结果的概率,p=1-p,。,1,次试验时，,p,1,=1,；,2,次试验时，,两次结果相同的概率为,1/N,，则,p,2,=1-1/N,；,3,次试验时，,前两次结果肯定是不相同的，第,3,次与,前两次结果相同的概率为,2/N,，不同则,为,1-2/N,，根据条件概率有：,p,3,=(1-1/N)(1-2/N),类推：,p,n,=(1-1/N)(1-2/N)(1-(n-1)/N),取对数：,lnp,n,=ln(1-1/N)+ln(1-2/N)+ln(1-(n-1)/N),根据泰勒级数展开式：,ln(1-x)=-(x+x,2,/2+x,3,/3+)-x,第一章 简单密码,所以,lnp,n,=ln(1-1/,N,)+ln(1-2/,N,)+ln(1-(n-1)/,N,),-(1/,N+,2/,N+,+,(n-1)/,N,),=-(1+2+n-1)/,N,=-n(n-1)/2,N,-n,2,/2,N,p,=,p,n,e,-n(n-1)/2,N,p=1-p,1-e,-n(n-1)/2,N,n,次实验后至少,2,次结果相同的概率,p,1-e,-n(n-1)/2,N,另外：,要使得,p,1/2,，则,p1/2,ln,p,ln,1/2,-n,2,/2,N,ln,1/2,-n,2,/2,N,ln,2,第一章 简单密码,作业：,(1),为移位密码加密的消息解密：,YRQ QEFP BUXJMIB FP IBPP BXPV,(2),求,-1000,模,88,的约简。,(3),求,29,模,100,的乘法逆。,(4),已知明文攻击：,E,a,b,(3)=5,且,E,a,b,(6)=7,，求解密密钥。,(5),求,gcd(1112,1544),，并将其表示成如下形式：,1112x+1544y,(6),求,1001,模,1234,的乘法逆。,第一章 简单密码,古典密码的两大机制：,代替密码：,字母表范围内替换；,换位密码：,在消息内变换字母的位置。,2.1,代替密码,1.,描述,密钥是字母表的任意组合，有一个明密对应表；,密钥空间巨大：,26!,；,单表代替密码的两个特例：移位密码和仿射密码。,2.,举例,首先选加密表；为了便于记忆，协商一个密钥：,DO YOU LIKE THIS BOOK,去掉重复字母，再进行补充，形成加密表：,abcdefghijklmnopqrstuvwxyz,DOYULIKETHSB,ACFGJMNPQRVWXZ,第二章 代替与换位,第二章 代替与换位,2.2,换位密码,1.,机制：,单个字符不变而位置改变。,如将文本翻转：明文,computersystems,密文,SMETSYSRETUPMOC,2.,特点：,(1),密文长度与明文长度相同；,(2),唯密文攻击可能得到多种不同的破译结果；,如,keep,peek,；,live,evil,vile,3.,分组换位密码,针对固定大小的分组进行操作。,举例：明文,can you understand,(1),列换位法,设密钥,k=4,，将明文进行分组排列,c,a,n,y,o,u,u,n,d,e,r,s,t,a,n,d,按列,读出,密文：,CODTAUEANURNYNSD,C,A,N,Y,O,U,U,N,D,E,R,S,T,A,N,D,按行,读出,明文：,canyouunderstand,明文：,canyouunderstand,按,4,个字符一行分组排列,按,4,个字符一列分组排列,1 2 3 4,1 2 3 4,第二章 代替与换位,按列,读出,t y p e,c,a,n,y,o,u,u,n,d,e,r,s,t,a,n,d,密文：,YNSDNURNCODTAUEA,C,A,N,Y,O,U,U,N,D,E,R,S,T,A,N,D,按行,读出,明文：,canyouunderstand,明文：,canyouunderstand,按,4,个字符一行分组排列,按,type(3,4,2,1),填入,1 2 3 4,3 4,2 1,YNSD NURN CODT AUEA,(2),密钥为字符串,type,1,2,3,4,按密钥长度分组,第二章 代替与换位,(3),矩阵换位法：置换矩阵作为密钥,明文：,canyouunderstand,c a n y o u u n d e r s t a n d,n c y a u o n u r d s e n t d a,密文：,NCYAUONURDSENTDA,按置换矩阵的阶,4,分组,c a n y o u u n d e r s t a n d,N C Y A U O N U R D S E N T D A,明文：,canyouunderstand,解密置换矩阵：,说明：,第二章 代替与换位,第二章 代替与换位,2.3,频率攻击,1.,原理：,利用自然语言的频率攻击,字母出现的频率有规律：,e:11.67 t:9.53 o:7.81 a:7.73,the:4.65 to:3.02 of:2.61 and:1.85,2.,应用：,对古典密码进行唯密文攻击。,3.,举例：,对仿射密码的攻击,密文：,JFFGJFDMGFSJHYQHTAGHQGAFDCCFP,统计字母出现的次数：,F,6 G,4 H,3 J,3,猜测：,e(4),F(5)t(19),G(6),则有：,E,a,b,(e)=F E,a,b,(t)=G,第二章 代替与换位,E,a,b,(4)=(a,4+b)%26,E,a,b,(19)=(a19+b)%26,5=(4a+,b)%26,6=(19a+b)%26,a=15,-1,%26=7,b=3,加密密钥,a,-1,%26=15,-a,-1,b=-153%26=7,解密密钥,E,a,b,(x)=(7x+3)%26,解密函数为：,E,15,7,(x)=(15x+7)%26,解密后的明文为：,meet me after midnight in the alley,第二章 代替与换位,4.,举例：,对代替密码的攻击,KOS BMKKBS ISS YFSJ NFK BMES KOS,IDY IFP KF JSS MK.,t,h,e,t,h,e,e,ee,e,e,ee,t,t,t,tt,o,o,o,o,n,i,i,i,l,l,l,k,b,b,s,s,d,d,b,a,y,分析：由,ESROL,得到,er,s,o,l,或,re,s,o,l,loser,或,sorel,那么：由,VIERD,得到,drive,或,irevd,所以比较合理的明文是：,loser,drive,5.,举例：,对换位密码的攻击,ESROL VIERD,第二章 代替与换位,作业：,(1),解密由仿射密码加密的密文：,VCLLCP BKLC LJKX XCHCP,(2),解密用简单换位密码加密的密文：,EAGGAR DAIREP,3.1,群,1.,二元运算,定义：,设,s,为集合，函数,f:s,s,s,称为,s,上的二,元运算或代数运算。满足：,可计算性：,s,中任何元素都可以进行这种运算；,单值性：运算结果唯一；,封闭性：,s,中任何两个元素运算结果都属于,s,。,2.,群的定义,定义：,设,是代数系统，,为,G,上的二元运算，如果,运算是可结合的，则称,半群。,若,为半群，并且二元运算,存在单位元,e,G,，则称,为幺半群；,若,为半群，并且二元运算,存在单位元,e,G,，,G,中的任何元素,x,都有逆元,x,-1,G,，称,为群，简记为,G,。,第三章 置 换,举例：,(1),是群，其中,Z,为整数集合，,+,是普通,的加法，单位元是,0,，整数,x,的逆元是,-x,。,(2),是群，,Z,6,=0,1,2,3,4,5,，,为模,6,加法。显然,满足结合律，单位元是,0,；由于,15=0,，,24=0,，,33=0,，所以,1,和,5,互为逆元，,2,和,4,互为逆元，,3,和,0,的逆元仍然是,3,和,0,。,3.,群中元素的阶,定义：,设,是群，,a,G,，,nZ,，则,a,的,n,次幂为,e n=0,a,n,=a,n-1,a n0,(a-1),m,n0,n=-m,举例：,在群,中，,3,0,=0,，,3,5,=15,，,3,-5,=-15,在群,中，,2,0,=0,，,2,3,=0,，,2,-3,=0,第三章 置 换,阶的定义：,(1),设,是群，,a,G,，使得等式,a,k,=e,成立的,最小正整数,k,称为,a,的阶，记做,|a|=k,，,a,称为,k,阶元，若不存在这样的整数,k,，则,a,称为无限阶元。,例如：,在,中，,2,和,4,是,3,阶元，,3,是,2,阶元，,1,和,5,是,6,阶元，,0,是,1,阶元。,在,中，,0,是,1,阶元，其他都是无限阶元。,(2),设,为群，,a,G,，且,|a|=r,。设,k,是整数，则,a,k,=e,当且仅当,r|k,。,(3),设,为群，则群中任何元素,a,与其逆元,a,-1,具有相同的阶。,第三章 置 换,4.,循环群和置换群,定义,1,：,设,为群，如果存在一个元素,a,G,，,使得,G=a,k,|k,Z,，则称,G,为循环群，记做,G=,，,称,a,为生成元。若,|a|=n,，则,G,称为,n,阶循环群。,例如：,是循环群，其中,Z,6,=0,1,2,3,4,5,，,为模,6,加法，生成元为,1,或,5,。,是循环群，生成元为,1,或,-1,。,是循环群，,Z,n,=0,1,n-1,，,生成,元为,1,。,第三章 置 换,定义,3,：,设,s=1,2,n,，,s,上的,n!,个置换构成集合,s,n,，则称,s,n,与置换的复合运算,构成的群,为,s,上,的,n,元对称群，,的任意子群称为,s,上的,n,元置换群。,第三章 置 换,定义,2,：,设,s=1,2,n,，,s,上的任何双射映射函数,:ss,称为,s,上的,n,元置换，记为：,3.2,置换概念,1.,置换,一个集合,X,的置换,f,定义为,X,到自身的一个双射,函数,f,。对应有,n,个元素的集合,X,，共有,n!,个置换。,问题：,对于集合,X,，给定某个状态，经过多少次,置换返回初始状态？,Sn=1,2,3,n-1,n,表示,n,个元素的置换群,置换,g,为满足,g(k)=i,k,的一个置换：,平凡置换,e,：,没有移动任何元素的置换。,即对于所有的,i,，有,e(i)=i,。,置换与集合内容无关,第三章 置 换,2.,置换的合成或乘积,设,g,和,h,是两个置换，先应用,h,，再应用,g,，,记为：,gh,或,gh,注意：,gh,hg,置换的合成满足结合律：,(gh)k=g(hk),3.,逆置换,对于任意置换,g,，存在一个逆置换,g,-1,，满足：,gg,-1,=g,-1,g=e,4.,图表记法,用来计算两个置换的乘积。如：,第三章 置 换,5.,循环,最简单的置换是不同长度的循环。,一个,k,循环满足：,f(i,1,)=i,2,f(i,2,)=i,3,f(i,k-1,)=i,k,f(i,k,)=i,1,，对于任意,j,(i,1,i,2,i,k,),，有,f(j)=j,。,举例：,则：,可见：,gh hg,，具有不可交换性。,记作：,(i,1,i,2,i,k,),(,1 2,),(,1 3,),第三章 置 换,6.,结论,(1),如果,g,是一个,k,循环，那么,g,k,=e,。,注意：,一个,k,循环有,k,种表示法。,比较：,(,1 2 3,),与,(,1 3 2,),(,1 2 3,)=(,2 3 1,)=(,3,1 2,),(,1 3 2,),如：,则：,即：,对某个集合应用,g,操作,k,次，不会对集合产生,任何影响。,第三章 置 换,(2),置换的阶,是置换被多次应用后却不产生任何实际影响所需要的重复次数。,若置换,g,是一个,k,循环，则有,g,k,=e,，,g,的阶为,k,。,(3),不相交的循环,若,g=,(i,1,i,k,),和,h=,(j,1,j,l,),分别为,k,循环和,l,循环，且,i,1,i,2,i,k,和,j,1,j,2,j,l,是不相交的列表，则有：,gh=hg,这样的循环,g,和,h,称为不相交的循环。,第三章 置 换,一个置换,g,的阶,k=,不相交循环分解中各循环长度的最小公倍数。,如：,思考：,如果一副,50,张的牌洗得好，重复洗,8,次后所,有的牌将返回初始位置。,阶为,4,(4),置换的不相交循环分解,任何置换都可以表示为不相交循环的乘积，并且本质上只有这一种表示方法。,=(,1,4 5 7,)(,2 3,)(,6,),第三章 置 换,3.3,切牌,最简单的切牌：选择一个随机点把一副牌一分为二，然后交换两部分。,n,张牌：,0,1,n-1 i+1,n-1,0,1,i,切牌过程为：,f,i,(x)=(x+n-i-1)%n,如：,n=6,i=1,0,1,2,3,4,5 2,3,4,5,0,1,置换过程为：,f1(x)=(x+4)%6,第三章 置 换,若,n,张牌的位置编号为：,1,2,n-1,n,i+1,n-1,n,1,i,则切牌过程为：,f,i,(x)=(x+n-i-1)%n+1,第三章 置 换,如：,n=6,i=2,1,2,3,4,5,6 3,4,5,6,1,2,置换过程为：,f1(x)=(x+3)%6+1,2n,张牌：,1,2,n,n+1,2n-1,2n,两半交错：,n+1,1,n+2,2,2n-1,n-1,2n,n,1,n+1,2,n+2,n-1,2n-1,n,2n,命题：对一副有,2n,张牌,1,2,2n-1,2n,的完美快速,洗牌过程为：,f(x)=(2x)%(2n+1),推论：若,e,为,2,模,2n+1,的阶，即,e,是满足,2,e,=1 mod,2n+1,的最小正整数。那么对一副有,2n,张牌经,过,e,次洗牌后，所有的牌都第一次返回到它们,的起始位置。,不好的洗牌,完美洗牌,第三章 置 换,3.4,洗牌,然后按列读取这些数：,0,n,2n,mn-n,1,n+1,2n+1,mn-n+1,mn-1,对于数,x,，行：,x/n,列：,x%n,3.5,分组交错,给定正整数,m,和,n,，针对,mn,个元素，一个,m,n,分组交换的置换定义为：,按行将,mm,个数据写成,m,n,的矩阵的形式,第三章 置 换,然后按列读取这些数：,0,4,8,1,5,9,2,6,10,3,7,11,对应的置换过程为：,例：,12,个数据,0,1,2,3,4,5,6,7,8,9,10,11,，,进行,3,4,分组交错。,对应的循环分解为：,数据,置换位置,阶为,5,按,4,行,3,列写出,第三章 置 换,命题：忽略两个不动点,0,和,mn-1,，,m,n,分组交错,对集合,1,2,3,mn-2,的作用是：,x (mx)%(mn-1),举例：,3,6,分组交错,3x%17,3,x,%17,分析：快速洗牌，去掉两个不动点,完美的快速洗牌：,x (2x)%(2n+1),第三章 置 换,作业：,(1),计算乘积,第三章 置 换,用不相交循环的乘积表示上述的结果，并确定阶。,(2)S,5,中任意元素的最大阶是多少？,S,14,呢？,(3),确定对一副,20,张牌的完美快速洗牌的循环分解。,(4),找出,3,5,的分组交错置换的循环分解。,第四章 现代对称密码,香农提出的,现代密码,设计准则：,Kerchhoff,原则：,系统的安全性不依赖于对密文或,加密算法的保密，而依赖于密钥。,惟一需要保密的是密钥；,决定了古典密码学与现代密码学。,一个好的密码将融合混淆和扩散,混淆：,混淆明文的不同部分；,扩散：,对攻击者隐藏一些语言的局部特征；,现代密码将结合换位和代替：,代替密码,在混淆上是有效的；,换位密码,扩散性较好。,4.1,数据加密标准,DES,(,Data Encryption Standard,),1976,年被采纳作为联邦标准，并授权在非密级,的政府通信中使用，应用广泛。,DES,是一个分组加密算法，对称密码，,64,位分,组，密钥长度为,64,位,(,实际长度为,56,位,),。,第四章 现代对称密码,现代密码算法的特点：,只要保证密钥安全，就能保证加密信息的安全。,对称密码算法：,很好地融合了混淆和扩散；,DES,、,AES,、,IEDA,、,RC6,等,非对称密码算法：,基于数学难题；,RSA,、,ECC,、,ElGamal,等,DES,的整个算法是公开的，系统的安全性靠,密钥保证。算法包括三个步骤：初始置换,IP,、,16,轮,迭代的乘积变换、逆初始变换,IP,-1,。,1.,初始置换,IP,初始置换,IP,可将,64,位明文,M=m,1,m,2,m,64,的位置进,行置换，得到乱序的,64,位明文组,M,0,=m,58,m,50,m,7,。,2.,逆初始置换,IP,-1,逆初始置换,IP,-1,将,16,轮迭代后的,64,比特数据的各,字节按列写出，将前四列