信息安全概论第8讲.ppt

信息安全概论 第8讲 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看成中的元时对乘法是可逆的，从而可用欧几里的算法求出其逆元 3.3.1 RSA算法 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上椭圆曲线点的图像 l椭圆曲线上的点有一种自然的加法运算，曲线 上的点连同y轴方向上无穷远点O构成一个加法 群。图像上点的加法规则表述为： lO是单位元. l曲线与任意一条直线如果有交点，则恰有三个交点 ，三点的和为O. l由此可以同有限域乘法群类似地构造密码体制 椭圆曲线群结构 EC的基本运算 l计算两个点的和。已知P(x1,y1), Q(x2,y2) ，求R=P+Q的坐标R(x3,y3)。 令 若Q=-P,则 R=O 若Q -P,则 l1985年Miller, Koblitz注意到有限域上的椭圆曲线加法 群具有这样的属性。并发表了该想法，称为ECC。 l经过多年的研究人们发现，ECC有较高的安全开销比 RSA小（一般认为其密钥长度开销是RSA算法的1/4以 下，而运算时间开销则会更小）。从而受到业界的青睐 。 lRSA不能公用密码参数，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标准( 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的碰撞例子，她 因为攻击MD5、HAVAL-128、 MD4和RIPE