信息安全概论第8讲

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

2、的，从而可用欧几里的算法求出其逆元3.3.1 rsa算法2. 加密过程nzennmmzze:rsa算法的明文空间与密文空间均为3. 脱密过程dnncczzd:3.3.2有限域乘群密码与椭圆曲线密码用有限域构造有限群：按照抽象代数的有限域的构造理论，对于给定的任意一个素数p和一个正整数n，存在且仅存在一个pn阶的有限域，记为gf(pn)。则g=gf(pn)是一个s=pn-1阶的循环群。若g是它的一个生成元，则可记为g=。1. diffie-hellman密钥交换算法 szbbgbabgaabbgbabagalice和bob选择了一个有限域的乘法群g=。bob计算：结果，双方共享了一个秘密参数值a

3、lice计算： ；szaaga alice秘密选择一个指数作为私钥，计算作为公钥； bob 秘密选择一个指数作为私钥，计算作为公钥； alice和bob通过公共信道交换公钥可作为双方以后进行密码计算所需的秘密值，如作为密钥使用！1. diffie-hellman密钥交换算法 容易看出，一个基本假设是敌手oscar从给定的a计算a是困难的。也就是说给定底数g和幂a，求指数a是困难的，这就是所谓的离散对数问题是难解的。对有限域而言，最好的求解离散对数问题的方法叫做指标计算法，它能在亚指数时间内求解离散对数问题。就现在的计算能力来讲，1024比特规模阶的有限域是足够了。另一方面，人们试图在寻找一个群

4、，使得其上的离散对数问题没有亚指数算法。椭圆曲线中可以提供大量的这样的群。我们稍后再回到这个问题上。2. elgamal加密算法szbbgbalice和bob选择了一个有限域的乘法群g=。alice秘密选择一个指数，计算bob 秘密选择一个指数作为私钥，计算作为公钥； bob把公钥传给alice或公开公钥alice要向bob加密传送消息m。szk kgc 1bkmgc 2,21ccc 和把消息发送给bob。 bob可脱密得到:12)(mbkgc3.椭圆曲线 椭圆曲线是数论研究中的重要工具，有几百年（？）的研究历史。代数几何描述：椭圆曲线亏格为1的光滑的代数曲线（而椭圆、抛物线、双曲线是亏格为0

5、的光滑代数曲线）。椭圆曲线可以化简为平面曲线，并由下列的weierstrass方程表示：64223312axaxaxyaxyayr2上椭圆曲线点的图像l椭圆曲线上的点有一种自然的加法运算，曲线上的点连同y轴方向上无穷远点o构成一个加法群。图像上点的加法规则表述为：lo是单位元.l曲线与任意一条直线如果有交点，则恰有三个交点，三点的和为o.l由此可以同有限域乘法群类似地构造密码体制椭圆曲线群结构ec的基本运算l计算两个点的和。已知计算两个点的和。已知p(x1,y1), q(x2,y2) ，求求r=p+q的坐标的坐标r(x3,y3)。 令令),(p31111axayx213111114122121

6、1212,223,xxaxayyaaxaxxxxxyy若若若q=-p,则 r=o若q -p,则3131313212123)(ayxaxxyxxaaxl1985年年miller, koblitz注意到有限域上的椭圆曲线加法注意到有限域上的椭圆曲线加法群具有这样的属性。并发表了该想法，称为群具有这样的属性。并发表了该想法，称为ecc。l经过多年的研究人们发现，经过多年的研究人们发现，ecc有较高的安全有较高的安全开销比开销比rsa小（一般认为其密钥长度开销是小（一般认为其密钥长度开销是rsa算法的算法的1/4以以下，而运算时间开销则会更小）。从而受到业界的青睐。下，而运算时间开销则会更小）。从而受

7、到业界的青睐。lrsa不能公用密码参数，不能公用密码参数，ecc则可以。则可以。4. 椭圆曲线密码ecc ecc举例 与在有限域上的乘法群一样，在有限域上的椭圆曲线也可实现diffie-hellman密钥交换算法和elgamal加密算法。例. alice想使用椭圆曲线版本的elgamal加密算法给bob传送一个消息m。这时bob选择了一个大素数p=8831，并选择了一个有限域gf(8831)上的椭圆曲线e:45332xxy以及这条曲线上的一个点g=(4,11)。bob还选择了自己的私钥b=3，计算并公开一个点b=bg=(413,1808)作为自己的公钥。ecc举例 )1743, 5(mp)63

8、21,5415(kg)3576,6626( kbpm)146,673()6321,5415(3)(kgb)1743, 5()146,673()3576,6626()146,673()3576,6626(假设alice想要发送的消息可以适当地编码为e上的点这时她首先随机选择一个指数k=8，然后计算把这两个数据一同传送给bob。bob利用自己的私钥b=3和收到的消息计算从而完成了脱密运算。ecc有两类椭圆曲线上的离散对数问题没有预期的那样难解。一类称为超奇异（supersingular）的曲线，其离散对数求解稍比其基域（有限域）上的困难一点。另一类称为反常（anomalous）的曲线，其上的离散对

9、数问题可以通过形式指数-形式对数映射为十分简单的问题。用椭圆曲线构造密码系统时，绝对要避免反常曲线的情形。密码研究原来对超奇异曲线也不感兴趣，但是近年来人们又发现超奇异曲线有一些非常好的性质。主要是通过weil配对，给出的e到基域乘法群上的双线性映射，为人们提供了一种可以构造基于身份的密码系统的方法。而且这种密码经常是在较基本的假设下可以证明其安全性，从而成为近年来学术界追逐的对象之一。 3.4 哈希函数哈希函数是一类重要的函数，可用于计算数字签名和消息鉴别码。从而用于防抵赖、身份识别和消息鉴别等。 3.4.1安全哈希函数的定义 哈希函数是为了实现数字签名或计算消息的鉴别码而设计的。哈希函数以

10、任意长度的消息作为输入，输出一个固定长度的二进制值，称为哈希值、杂凑值或消息摘要。从数学上看，哈希函数h是一个映射： )(:2*2xhxzzhnnmmzz2*2这里 安全哈希函数哈希函数是代表一个消息在计算意义下的特征数据。所谓计算特征数据表示在计算上无法找到两个不同的消息 和 ，使得他们有相同的函数值。这条性质称为哈希函数的强无碰撞性。 满足强无碰撞性的hash函数叫做安全hash函数。显然安全hash函数满足：1x2x1x12xx（1）弱无碰撞性：给定消息，计算上无法找到一个不同的，使得他们有相同的函数值。（2）单向性：对于任一给定的一个函数值，求源像，计算上是不可行的。实践证明安全哈希函

11、数的构造是一件十分困难的事，已经成为密码学研究的一个热点。哈希函数的构造框架1. 选择一个适当的正整数b，称为分组长度，构造一个映射h：),(),(:222yxhyxzzzhnnb2. 选定一个初始向量n2ziv。3.对任意给定的消息x，把它按照固定的规则扩展成长度为b的整倍数的二进制值： xx1x2xs1, 1 , 0),(11siyxhyiii4. 令y0=iv，执行下列迭代运算：则h(x)=ys即为输入x的杂凑值。哈希函数标准1. md5和sha-1。md4由rivest在1990年提出，其增强版于1991年提出。而sha则是nsa与nist1993年在md4基础上改进的，并由美国国家标

12、准技术局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-256、sha-384及sha-512.。原sha和sha-1的固定输出长度为160比特。但目前应用较广泛的还是sha-1。md4的另一个改进版md5，已经被证明不满足强无碰撞性，从而在一些需要强无碰撞性的场合使用md5是不安全的。哈希函数标准2. md5和sha-1的安全性。1998年，两位法国研究人员florent chabaud 与 antoine joux 发现了攻击sha（也称sha-0）的一种差分碰撞算法。2004年美洲密码年会crypto2004上，antoine joux利用bull sa公司开发计算机系统tera nova发现了sha算法的碰撞的实例。同一会议上，王小云指出可通过大约240次的计算，找出sha-0的碰撞例子，她