信息安全概论第8讲PPT课件

1、1,信息安全概论,第8讲,2,3.3公钥密码算法,公钥密码算法又称为非对称密钥密码算法，其主要特征是加密密钥可以公开，而不会影响到脱密密钥的机密性。可用于保护数据的机密性、完整性、身份识别等,3,3.3.1 RSA算法,1. 系统建立过程,Bob选定两个不同的素数p和q，令n = pq，再选取一个整数e ,使得,从而可以计算出,Bob的公开密钥(e, n) Bob的私有密钥(d, n,表示n的欧拉函数，即表示不超过n且与n互素的整数个数。易证当n = pq， p和q为不同的素数时,当把e看成,中的元时对乘法是可逆的，从而可用欧几里的算法求出其逆元,4,3.3.1 RSA算法,2. 加密过程,R

2、SA算法的明文空间与密文空间均为,3. 脱密过程,5,3.3.2有限域乘群密码与椭圆曲线密码,用有限域构造有限群： 按照抽象代数的有限域的构造理论，对于给定的任意一个素数p和一个正整数n，存在且仅存在一个pn阶的有限域，记为GF(pn)。则G=GF(pn)是一个s=pn-1阶的循环群。若g是它的一个生成元，则可记为G,6,1. Diffie-Hellman密钥交换算法,Alice和Bob选择了一个有限域的乘法群G,Bob计算,结果，双方共享了一个秘密参数值,Alice计算：,Alice秘密选择一个指数,作为私钥，计算,作为公钥,Bob 秘密选择一个指数,作为私钥，计算,作为公钥,Alice和B

3、ob通过公共信道交换公钥,可作为双方以后进行密码计算所需的秘密值，如作为密钥使用,7,1. Diffie-Hellman密钥交换算法,容易看出，一个基本假设是敌手Oscar从给定的A计算a是困难的。也就是说给定底数g和幂A，求指数a是困难的，这就是所谓的离散对数问题是难解的。 对有限域而言，最好的求解离散对数问题的方法叫做指标计算法，它能在亚指数时间内求解离散对数问题。就现在的计算能力来讲，1024比特规模阶的有限域是足够了。 另一方面，人们试图在寻找一个群，使得其上的离散对数问题没有亚指数算法。椭圆曲线中可以提供大量的这样的群。我们稍后再回到这个问题上,8,2. ElGamal加密算法,Al

4、ice和Bob选择了一个有限域的乘法群G,Alice秘密选择一个指数,计算,Bob 秘密选择一个指数,作为私钥，计算,作为公钥,Bob把公钥传给Alice或公开公钥,Alice要向Bob加密传送消息m,和,把消息,发送给Bob,Bob可脱密得到,9,3.椭圆曲线,椭圆曲线是数论研究中的重要工具，有几百年（？）的研究历史。 代数几何描述：椭圆曲线亏格为1的光滑的代数曲线（而椭圆、抛物线、双曲线是亏格为0的光滑代数曲线）。 椭圆曲线可以化简为平面曲线，并由下列的Weierstrass方程表示,10,R2上椭圆曲线点的图像,11,椭圆曲线上的点有一种自然的加法运算，曲线上的点连同y轴方向上无穷远点O

5、构成一个加法群。图像上点的加法规则表述为： O是单位元. 曲线与任意一条直线如果有交点，则恰有三个交点，三点的和为O. 由此可以同有限域乘法群类似地构造密码体制,椭圆曲线群结构,12,EC的基本运算,计算两个点的和。已知P(x1,y1), Q(x2,y2) ，求R=P+Q的坐标R(x3,y3)。 令,13,若Q=-P,则 R=O 若Q -P,则,14,1985年Miller, Koblitz注意到有限域上的椭圆曲线加法群具有这样的属性。并发表了该想法，称为ECC。 经过多年的研究人们发现，ECC有较高的安全开销比RSA小（一般认为其密钥长度开销是RSA算法的1/4以下，而运算时间开销则会更小）

6、。从而受到业界的青睐。 RSA不能公用密码参数，ECC则可以,4. 椭圆曲线密码ECC,15,ECC举例,与在有限域上的乘法群一样，在有限域上的椭圆曲线也可实现Diffie-Hellman密钥交换算法和ElGamal加密算法,例. Alice想使用椭圆曲线版本的ElGamal加密算法给Bob传送一个消息m。这时Bob选择了一个大素数p=8831，并选择了一个有限域GF(8831)上的椭圆曲线E,以及这条曲线上的一个点G=(4,11)。Bob还选择了自己的私钥b=3，计算并公开一个点B=bG=(413,1808)作为自己的公钥,16,ECC举例,假设Alice想要发送的消息可以适当地编码为E上的

7、点,这时她首先随机选择一个指数k=8，然后计算,把这两个数据一同传送给Bob。Bob利用自己的私钥b=3和收到的消息计算,从而完成了脱密运算,17,ECC,有两类椭圆曲线上的离散对数问题没有预期的那样难解。一类称为超奇异（supersingular）的曲线，其离散对数求解稍比其基域（有限域）上的困难一点。另一类称为反常（anomalous）的曲线，其上的离散对数问题可以通过形式指数-形式对数映射为十分简单的问题。用椭圆曲线构造密码系统时，绝对要避免反常曲线的情形。密码研究原来对超奇异曲线也不感兴趣，但是近年来人们又发现超奇异曲线有一些非常好的性质。主要是通过weil配对，给出的E到基域乘法群上

8、的双线性映射，为人们提供了一种可以构造基于身份的密码系统的方法。而且这种密码经常是在较基本的假设下可以证明其安全性，从而成为近年来学术界追逐的对象之一,18,3.4 哈希函数,哈希函数是一类重要的函数，可用于计算数字签名和消息鉴别码。从而用于防抵赖、身份识别和消息鉴别等,19,3.4.1安全哈希函数的定义,哈希函数是为了实现数字签名或计算消息的鉴别码而设计的。哈希函数以任意长度的消息作为输入，输出一个固定长度的二进制值，称为哈希值、杂凑值或消息摘要。从数学上看，哈希函数H是一个映射,这里,20,安全哈希函数,哈希函数是代表一个消息在计算意义下的特征数据。所谓计算特征数据表示在计算上无法找到两个

9、不同的消息 和 ，使得他们有相同的函数值。这条性质称为哈希函数的强无碰撞性。 满足强无碰撞性的Hash函数叫做安全Hash函数。显然安全Hash函数满足,1）弱无碰撞性：给定消息,计算上无法找到一个不同的,使得他们有相同的函数值,2）单向性：对于任一给定的一个函数值，求源像，计算上是不可行的。 实践证明安全哈希函数的构造是一件十分困难的事，已经成为密码学研究的一个热点,21,哈希函数的构造框架,1. 选择一个适当的正整数b，称为分组长度，构造一个映射h,2. 选定一个初始向量,3.对任意给定的消息x，把它按照固定的规则扩展成长度为b的整倍数的二进制值： xx1x2xs,4. 令y0=IV，执行

10、下列迭代运算,则H(x)=ys即为输入x的杂凑值,22,哈希函数标准,1. MD5和SHA-1,MD4由Rivest在1990年提出，其增强版于1991年提出。而SHA则是NSA与NIST1993年在MD4基础上改进的，并由美国国家标准技术局NIST公布作为安全Hash标准( FIPS 180)。1995年, 由于SHA存在一个未公开的安全性问题，NSA提出了SHA的一个改进算法SHA-1作为安全Hash标准（SHS, FIPS 180-1.）。2002年，在安全Hash标准FIPS PUB 180-2中公开了SHA的三种固定输出长度分别为256比特、384比特及512比特的变形算法SHA-2

11、56、SHA-384及SHA-512.。原SHA和SHA-1的固定输出长度为160比特。但目前应用较广泛的还是SHA-1。MD4的另一个改进版MD5，已经被证明不满足强无碰撞性，从而在一些需要强无碰撞性的场合使用MD5是不安全的,23,哈希函数标准,2. MD5和SHA-1的安全性,1998年，两位法国研究人员Florent Chabaud 与 Antoine Joux 发现了攻击SHA（也称SHA-0）的一种差分碰撞算法。2004年美洲密码年会Crypto2004上，Antoine Joux利用BULL SA公司开发计算机系统TERA NOVA发现了SHA算法的碰撞的实例。 同一会议上，王小云指出可通过大约240次的计算，找出SHA-0的碰撞例子，她因为攻击MD5、HAVAL-128、 MD4和RIPE