网络与信息安全第一讲ppt课件

网络与信息安全密码学基础(二),潘爱民，北京大学计算机研究所panaimin,内容,公钥算法背包思想RSAEllipticcurveDiffie-Hellman密钥交换消息算法散列算法数字签名加密库Crypto+,公钥密码学的历史,76年Diffie和Hellman发表了“密码学的新方向”，奠定了公钥密码学的基础公钥技术是二十世纪最伟大的思想之一改变了密钥分发的方式可以广泛用于数字签名和身份认证服务78年，RSA算法PKI,公钥算法应用：保密,公钥算法应用：认证,基本思想和要求,涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换,如何设计一个公钥算法,公钥和私钥必须相关，而且从公钥到私钥不可推断必须要找到一个难题，从一个方向走是容易的，从另一个方向走是困难的如何把这个难题跟加解密结合起来计算可行和不可行的界,公钥密码学的研究情况,与计算复杂性理论密切相关计算复杂性理论可以提供指导但是需求不尽相同计算复杂性通常针对一个孤立的问题进行研究而公钥密码学往往需要考虑一些相关的问题比如，密码分析还需要考虑已知明文、选择明文等相关的情形讨论的情形不同计算复杂性考虑最坏的情形而对于公钥密码学则是不够的一个困难问题必然会导致一个保密性很好的密码系统吗？不一定，还需要有好的构造,背包(knapsack)问题,0-1背包问题：给定一个正整数S和一个背包向量A=(a1,an)，其中ai是正整数，求满足方程S=aixi的二进制向量X=(x1,xn)。这是一个NP完全问题，解决这个问题所需要的时间与n呈指数增长背包问题用于公钥密码学做法方法：明文为X，S为密文奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能把易解的背包问题修改成难解的背包问题公开密钥使用难解的背包问题私钥使用易解的背包问题,易解的背包问题超递增背包,满足下列条件的背包aiaj(j=1,i-1)这样的背包也被称为简单背包求解从最大的ai开始，如果S大于这个数，则减去ai,记xi为1，否则记xi为0如此下去，直到最小的ai例如背包序列2,3,6,13,27,52求解70的背包结果为2,3,13,52所以，密文70对应的明文为110101,转换背包,简单背包用作私钥如何产生相应的公钥转换做法：选择一个整数mai(i=1,n)然后选择一个与m互素的整数w，然后ai=wai(modm)(i=1,n)这里的ai是伪随机分布的这样得到的背包是非超递增背包,基于背包问题的公钥密码系统MH公钥算法,加密将明文分为长度为n的块X=(x1,xn)然后用公钥A=(a1,an)，将明文变为密文SS=E(X)=aixi解密先计算S=w-1Smodm再求解简单背包问题S=aixi,背包密码系统的意义,是第一个公钥密码系统有较好的理论价值在实践过程中，大多数的背包方案都已被破解，或者证明存在缺陷,RSA算法,1977年由RonRivest、AdiShamir和LenAdleman发明，1978年公布是一种块加密算法。明文和密文在0n-1之间,n是一个正整数应用最广泛的公钥密码算法只在美国申请专利，且已于2000年9月到期,RSA算法描述,分组大小为k,2kn2k+1加密:C=Memodn解密:M=Cdmodn=Medmodn公钥:KU=e,n,私钥:KR=d,n上述算法需要满足以下条件:能够找到e,d,n,使得Medmodn=M,对所有M0,Pi互不相同,则(n)=Piai(1-1/Pi)若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数,(pq)=(p-1)(q-1),数论基础(续),Euler定理:若a与n为互素的正整数,则a(n)1modn推论:若n=pq,pq都是素数,k是任意整数,则mk(p-1)(q-1)+1mmodn,对任意0mn,RSA密钥生成与使用,产生密钥对选择两个大素数p,q,pq计算n=pq,(n)=(p-1)(q-1)选择整数e,使得gcd(e,(n)=1计算de-1mod(n)公钥:KU=e,n,私钥:KR=d,n使用加密:C=Memodn解密:M=Cdmodn,计算乘幂,计算d=am,m=bkbk-1b0(二进制表示)d1forikdownto0dod(dd)modnifbi=1thend(da)modnreturnd原理：M=(bk2+bk-1)2+bk-2)2+bk-3)2+)2+b0,RSA密钥产生,产生两个素数由于n=pq是公开的，所以，为了防止攻击者利用n获得p和q，必须选择足够大的素数p和q大素数产生算法选择e或者d，然后求出另一个,大素数产生,素数生成过程:随机选择一个奇数n(如通过伪随机数发生器)随机选择a,使an进行素性测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到如果通过了足够次数的测试,认为n是素数,否则转到.素数理论:在N附近，每ln(N)个整数中有一个素数,素性测试,Miller-Rabin算法：用来测试一个整数是否是素数WITNESS(a,n)设bkbk-1b0是(n-1)的二进制表示d1forikdownto0doxdd(dd)modnif(d=1P+O=P一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1=-P2如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P12倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S,椭圆曲线密码示意图,有限域上椭圆曲线,有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modp针对所有的0=xp，可以求出有效的y，得到曲线上的点(x,y)，其中x,yp。记为Ep(a,b)Ep(a,b)中也包括O加法公式:P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则P+Q=(x3,y3)为x3=2-x1-x2(modp)y3=(x1-x3)-y1(modp)其中，如果PQ，则=(y2-y1)/(x2-x1)如果P=Q，则=(3x12+a)/(2y1),椭圆曲线用于加密,找到一个难题：考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密r加密M：先把消息M变换成为Ep(a,b)中一个点Pm然后，选择随机数k，计算密文Cm=kG,Pm+kP)如果k使得kG或者kP为O，则要重新选择k.解密Cm:(Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有扩张,椭圆曲线密码的安全性,难点:从P和kP获得k对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECCRSA*Pollardrho分析方法,消息认证,在网络通信中，有一些针对消息内容的攻击方法伪造消息窜改消息内容改变消息顺序消息重放或者延迟消息认证：对收到的消息进行验证，证明确实是来自声称的发送方，并且没有被修改过。如果在消息中加入时间及顺序信息，则可以完成对时间和顺序的认证,消息认证的三种方式,Messageencryption：用整个消息的密文作为认证标识接收方必须能够识别错误MAC：一个公开函数，加上一个密钥产生一个固定长度的值作为认证标识Hashfunction：一个公开函数将任意长度的消息映射到一个固定长度的散列值，作为认证标识,MessageAuthenticationCode,使用一个双方共享的秘密密钥生成一个固定大小的小数据块，并加入到消息中，称MAC，或密码校验和(cryptographicchecksum)用户A和用户B，共享密钥K，对于消息M，MAC=CK(M)如果接收方计算的MAC与收到的MAC匹配，则接收者可以确信消息M未被改变接收者可以确信消息来自所声称的发送者如果消息中含有序列号，则可以保证正确的消息顺序MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少,MAC应用方式,M,C,|,C,K,K,Compare,M,Ck(M),关于MAC算法,MAC不等于数字签名因为通讯双方共享同一个密钥MAC有固定的长度MAC结构的重要性，例如，密钥足够长+加密算法足够好安全M=(X1,X2,Xt)对M产生校验核M=X1X2XtMAC=EK(M)攻击者选择M=(Y1,Y2,Yt-1,Yt),使得Yt满足:Yt=Y1Y2Yt-1M于是M=MEK(M)=EK(M)CK(M)=CK(M)所以，尽管攻击者不知道K，仍然可以伪造消息M,MAC算法的要求,条件：攻击者知道MAC函数但不知道密钥K要求：已知M和CK(M)，要想构造M使得CK(M)=CK(M)在计算上不可行(计算上无碰撞)CK(M)均匀分布：随机选择M和M,PrCK(M)=CK(M)=2-|MAC|f是M的一个变换(例如对某些位取反),那么,PrCK(M)=CK(f(M)=2-|MAC|,MACbasedonDES,ANSI标准(X9.17)即为CBC模式结构，初始向量为0该方法适用于其他加密算法,算法：M=(X1,X2,Xt)M1=EK(X1)Mj+1=EK(Xj+1Mj),1jtMAC=Mt,HashFunction,MAC需要对全部数据进行加密MAC速度慢Hash是一种直接产生认证码的方法Hash函数:h=H(x),要求:可作用于任何尺寸数据且均产生定长输出H(x)能够快速计算单向性:给定h，找到x使h=H(x)在计算上不可行WeakCollisionResistence(WCR):给定x，找到yx使H(x)=H(y)在计算上不可行StrongCollisionResistence(SCR):找到yx使H(x)=H(y)在计算上不可行,生日攻击理论基础,理论基础若k1.182m/22m/2,则k个在1,2m的随机数中有两个数相等的概率不低于0.5若k0.83n1/2,两个在1,n的k个随机数集合有交集的概率不小于0.5因此，当Hash算法选用N位的Hash值时，两组消息（选择kN/2）中有一对消息产生相同Hash值的概率超过0.5,生日攻击例子,ThisLetterisIamwriting,tointroduce,youtotoyou,Mr.-,Alfred,P.-,Barton,.,Letter2与Letter1中的信含义不同。各自组合出2k封信件，然后在两个组中找到两封hash值相同的信！,Letter1：,Letter2：,.,对策：Hash值足够长，64-128-160-256,hash函数通用模型,由Merkle于1989年提出几乎被所有hash算法采用具体做法:把原始消息M分成一些固定长度的块Yi最后一块padding并使其包含消息M的长度设定初始值CV0压缩函数f,CVi=f(CVi-1,Yi-1)最后一个CVi为hash值,hash函数模型图,b,Y0,n,IV=CV0,f,b,Y1,n,f,b,YL-1,n,CVL-1,f,CV1,n,n,IV=initialvalue初始值CV=chainingvalue链接值Yi=ithinputblock(第i个输入数据块)f=compressionalgorithm(压缩算法）n=lengthofhashcode(散列码的长度)b=lengthofinputblock(输入块的长度),CVL,MD5算法,作者：RonRivest算法输入：任意长度的消息输出：128位消息摘要处理：以512位输入数据块为单位,MD5:示意图,MD5步骤,第一步：padding补长到512的倍数最后64位为消息长度的低64位一定要补长(64+164+512)，内容为1000第二步把结果分割为512位的块：Y0,Y1,YL-1第三步初始化MDbuffer，128位常量(4个字)，进入循环迭代，共L次每次：一个输入128位，另一个输入512位，结果输出128位，用于下一轮输入第四步最后一步的输出即为散列结果128位,MD5的每一步运算示意图,每一轮中16步的每一步运算结构,A,B,C,D,A,B,C,D,+,+,+,CLSs,+,g,Xk,Ti,Functiongg(b,c,d)1F(b,c,d)(bc)(bd)2G(b,c,d)(bd)(cd)3H(b,c,d)bcd4I(b,c,d)c(bd),关于MD5,MD5使用little-endian生日攻击模式+64位可计算128位hash值太短MD5不是足够安全的Dobbertin在1996年找到了两个不同的512-bit块,它们在MD5计算下产生相同的hash至今还没有真正找到两个不同的消息,它们的MD5的hash相等,SecureHashAlgorithm简介,1992年NIST制定了SHA(128位)1993年SHA成为标准1994年修改产生SHA-1(160位)1995年SHA-1成为新的标准SHA-1要求输入消息长度CurrentState()!=DefaultDecryptorWithMAC:KEY_GOOD)cerrCurrentState()!=DefaultDecryptorWithMAC:MAC_GOOD)cerrInvalidMAC.Thefilemayhavebeentemperedwith.n;,例子：摘要,voidDigestFile(constchar*filename)MD5md5;SHAshs;RIPEMD160ripemd;BufferedTransformation*outputs=newHashFilter(md5),newHashFilter(shs),newHashFilter(ripemd);FileSourcefile(filename,true,newFork(3,outputs);coutAttach(newHexEncoder(newFileSink(cout);coutAttach(newHexEncoder(newFileSink(cout);coutAttach(newHexEncoder(newFileSink(cout);coutpub.MaxPlainTextLength()cerrmessagetoolongforthiskeyn;abort();RandomPoolrandPool;randPool.Put(byte*)seed,strlen(seed);char*outstr=newchar2