信息安全概论第8讲.ppt

信息安全概论,第8讲,3.3公钥密码算法,公钥密码算法又称为非对称密钥密码算法，其主要特征是加密密钥可以公开，而不会影响到脱密密钥的机密性。可用于保护数据的机密性、完整性、身份识别等。,3.3.1RSA算法,1.系统建立过程,Bob选定两个不同的素数p和q，令n=pq，再选取一个整数e,使得,。从而可以计算出,Bob的公开密钥(e,n)Bob的私有密钥(d,n),表示n的欧拉函数，即表示不超过n且与n互素的整数个数。易证当n=pq，p和q为不同的素数时，,当把e看成,中的元时对乘法是可逆的，从而可用欧几里的算法求出其逆元,3.3.1RSA算法,2.加密过程,RSA算法的明文空间与密文空间均为,3.脱密过程,3.3.2有限域乘群密码与椭圆曲线密码,用有限域构造有限群：按照抽象代数的有限域的构造理论，对于给定的任意一个素数p和一个正整数n，存在且仅存在一个pn阶的有限域，记为GF(pn)。则G=GF(pn)是一个s=pn-1阶的循环群。若g是它的一个生成元，则可记为G=。,1.Diffie-Hellman密钥交换算法,Alice和Bob选择了一个有限域的乘法群G=。,Bob计算：,结果，双方共享了一个秘密参数值,Alice计算：；,Alice秘密选择一个指数,作为私钥，计算,作为公钥；,Bob秘密选择一个指数,作为私钥，计算,作为公钥；,Alice和Bob通过公共信道交换公钥,可作为双方以后进行密码计算所需的秘密值，如作为密钥使用！,1.Diffie-Hellman密钥交换算法,容易看出，一个基本假设是敌手Oscar从给定的A计算a是困难的。也就是说给定底数g和幂A，求指数a是困难的，这就是所谓的离散对数问题是难解的。对有限域而言，最好的求解离散对数问题的方法叫做指标计算法，它能在亚指数时间内求解离散对数问题。就现在的计算能力来讲，1024比特规模阶的有限域是足够了。另一方面，人们试图在寻找一个群，使得其上的离散对数问题没有亚指数算法。椭圆曲线中可以提供大量的这样的群。我们稍后再回到这个问题上。,2.ElGamal加密算法,Alice和Bob选择了一个有限域的乘法群G=。,Alice秘密选择一个指数,，计算,Bob秘密选择一个指数,作为私钥，计算,作为公钥；,Bob把公钥传给Alice或公开公钥,Alice要向Bob加密传送消息m。,和,把消息,发送给Bob。,Bob可脱密得到:,3.椭圆曲线,椭圆曲线是数论研究中的重要工具，有几百年（？）的研究历史。代数几何描述：椭圆曲线亏格为1的光滑的代数曲线（而椭圆、抛物线、双曲线是亏格为0的光滑代数曲线）。椭圆曲线可以化简为平面曲线，并由下列的Weierstrass方程表示：,R2上椭圆曲线点的图像,椭圆曲线上的点有一种自然的加法运算，曲线上的点连同y轴方向上无穷远点O构成一个加法群。图像上点的加法规则表述为：O是单位元.曲线与任意一条直线如果有交点，则恰有三个交点，三点的和为O.由此可以同有限域乘法群类似地构造密码体制,椭圆曲线群结构,EC的基本运算,计算两个点的和。已知P(x1,y1),Q(x2,y2)，求R=P+Q的坐标R(x3,y3)。令,若Q=-P,则R=O若Q-P,则,1985年Miller,Koblitz注意到有限域上的椭圆曲线加法群具有这样的属性。并发表了该想法，称为ECC。经过多年的研究人们发现，ECC有较高的安全开销比RSA小（一般认为其密钥长度开销是RSA算法的1/4以下，而运算时间开销则会更小）。从而受到业界的青睐。RSA不能公用密码参数，ECC则可以。,4.椭圆曲线密码ECC,ECC举例,与在有限域上的乘法群一样，在有限域上的椭圆曲线也可实现Diffie-Hellman密钥交换算法和ElGamal加密算法。,例.Alice想使用椭圆曲线版本的ElGamal加密算法给Bob传送一个消息m。这时Bob选择了一个大素数p=8831，并选择了一个有限域GF(8831)上的椭圆曲线E:,以及这条曲线上的一个点G=(4,11)。Bob还选择了自己的私钥b=3，计算并公开一个点B=bG=(413,1808)作为自己的公钥。,ECC举例,假设Alice想要发送的消息可以适当地编码为E上的点,这时她首先随机选择一个指数k=8，然后计算,把这两个数据一同传送给Bob。Bob利用自己的私钥b=3和收到的消息计算,从而完成了脱密运算。,ECC,有两类椭圆曲线上的离散对数问题没有预期的那样难解。一类称为超奇异（supersingular）的曲线，其离散对数求解稍比其基域（有限域）上的困难一点。另一类称为反常（anomalous）的曲线，其上的离散对数问题可以通过形式指数-形式对数映射为十分简单的问题。用椭圆曲线构造密码系统时，绝对要避免反常曲线的情形。密码研究原来对超奇异曲线也不感兴趣，但是近年来人们又发现超奇异曲线有一些非常好的性质。主要是通过weil配对，给出的E到基域乘法群上的双线性映射，为人们提供了一种可以构造基于身份的密码系统的方法。而且这种密码经常是在较基本的假设下可以证明其安全性，从而成为近年来学术界追逐的对象之一。,3.4哈希函数,哈希函数是一类重要的函数，可用于计算数字签名和消息鉴别码。从而用于防抵赖、身份识别和消息鉴别等。,3.4.1安全哈希函数的定义,哈希函数是为了实现数字签名或计算消息的鉴别码而设计的。哈希函数以任意长度的消息作为输入，输出一个固定长度的二进制值，称为哈希值、杂凑值或消息摘要。从数学上看，哈希函数H是一个映射：,这里,安全哈希函数,哈希函数是代表一个消息在计算意义下的特征数据。所谓计算特征数据表示在计算上无法找到两个不同的消息和，使得他们有相同的函数值。这条性质称为哈希函数的强无碰撞性。满足强无碰撞性的Hash函数叫做安全Hash函数。显然安全Hash函数满足：,（1）弱无碰撞性：给定消息,，计算上无法找到一个不同的,，使得他们有相同的函数值。,（2）单向性：对于任一给定的一个函数值，求源像，计算上是不可行的。实践证明安全哈希函数的构造是一件十分困难的事，已经成为密码学研究的一个热点。,哈希函数的构造框架,1.选择一个适当的正整数b，称为分组长度，构造一个映射h：,2.选定一个初始向量,。,3.对任意给定的消息x，把它按照固定的规则扩展成长度为b的整倍数的二进制值：xx1x2xs,4.令y0=IV，执行下列迭代运算：,则H(x)=ys即为输入x的杂凑值。,哈希函数标准,1.MD5和SHA-1,。,MD4由Rivest在1990年提出，其增强版于1991年提出。而SHA则是NSA与NIST1993年在MD4基础上改进的，并由美国国家标准技术局NIST公布作为安全Hash标准(FIPS180)。1995年,由于SHA存在一个未公开的安全性问题，NSA提出了SHA的一个改进算法SHA-1作为安全Hash标准（SHS,FIPS180-1.）。2002年，在安全Hash标准FIPSPUB180-2中公开了SHA的三种固定输出长度分别为256比特、384比特及512比特的变形算法SHA-256、SHA-384及SHA-512.。原SHA和SHA-1的固定输出长度为160比特。但目前应用较广泛的还是SHA-1。MD4的另一个改进版MD5，已经被证明不满足强无碰撞性，从而在一些需要强无碰撞性的场合使用MD5是不安全的。,哈希函数标准,2.MD5和SHA-1的安全性,。,1998年，两位法国研究人员FlorentChabaud与AntoineJoux发现了攻击SHA（也称SHA-0）的一种差分碰撞算法。2004年美洲密码年会Crypto2004上，AntoineJoux利用BULLSA公司开发计算机系统TERANOVA发现了SHA算法的碰撞的实例。同一会议上，王小云指出可通过大约240次的计算，找出SHA-0的碰撞例子，她因为攻击MD5、HAVAL-128、MD4和RIP