信息安全概论第8讲.ppt

信息安全概论 第8讲 3.3公钥密码算法 3.3.1 RSA算法 3.3.1 RSA算法 3.3.2有限域乘群密码与椭圆曲线密码 1. Diffie-Hellman密钥交换算法 1. Diffie-Hellman密钥交换算法 2. ElGamal加密算法 3.椭圆曲线 ECC举例 ECC举例 ECC 3.4 哈希函数 3.4.1安全哈希函数的定义 安全哈希函数 哈希函数的构造框架 哈希函数标准 哈希函数标准 思考 * * 公钥密码算法又称为非对称密钥密码算法，其主要特征是加密密钥可以公开，而不会影响到脱密密钥的机密性。可用于保护数据的机密性、完整性、身份识别等。 1. 系统建立过程 Bob选定两个不同的素数p和q，令n = pq，再选取一个整数e ,使得 。从而可以计算出 Bob的公开密钥———(e, n) Bob的私有密钥———(d, n) 表示n的欧拉函数，即表示不超过n且与n互素的整数个数。易证当n = pq， p和q为不同的素数时， 当把e看成 中的元时对乘法是可逆的，从而可用欧几里的算法求出其逆元 2. 加密过程 RSA算法的明文空间与密文空间均为 3. 脱密过程 用有限域构造有限群： 按照抽象代数的有限域的构造理论，对于给定的任意一个素数p和一个正整数n，存在且仅存在一个pn阶的有限域，记为GF(pn)。则G=GF(pn)×是一个s=pn-1阶的循环群。若g是它的一个生成元，则可记为G=g。 Alice和Bob选择了一个有限域的乘法群G=g。 Bob计算： 结果，双方共享了一个秘密参数值 Alice计算： ； Alice秘密选择一个指数 作为私钥，计算 作为公钥； Bob 秘密选择一个指数 作为私钥，计算 作为公钥； Alice和Bob通过公共信道交换公钥 可作为双方以后进行密码计算所需的秘密值，如作为密钥使用！ 容易看出，一个基本假设是敌手Oscar从给定的A计算a是困难的。也就是说给定底数g和幂A，求指数a是困难的，这就是所谓的离散对数问题是难解的。 对有限域而言，最好的求解离散对数问题的方法叫做指标计算法，它能在亚指数时间内求解离散对数问题。就现在的计算能力来讲，1024比特规模阶的有限域是足够了。 另一方面，人们试图在寻找一个群，使得其上的离散对数问题没有亚指数算法。椭圆曲线中可以提供大量的这样的群。我们稍后再回到这个问题上。 Alice和Bob选择了一个有限域的乘法群G=g。 Alice秘密选择一个指数 ，计算 Bob 秘密选择一个指数 作为私钥，计算 作为公钥； Bob把公钥传给Alice或公开公钥 Alice要向Bob加密传送消息m。 和 把消息 发送给Bob。 Bob可脱密得到: 椭圆曲线是数论研究中的重要工具，有几百年（？）的研究历史。 代数几何描述：椭圆曲线亏格为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 与在有限域上的乘法群一样，在有限域上的椭圆曲线也可实现Diffie-Hellman密钥交换算法和ElGamal加密算法。 例. Alice想使用椭圆曲线版本的ElGamal加密算法给Bob传送一个消息m。这时Bob选择了一个大素数p=8831，并选择了一个有限域GF(8831)上的椭圆曲线E: 以及这条曲线上的一个点G=(4,11)。Bob还选择了自己的私钥b=3，计算并公开一个点B=bG=(413,1808)作为自己的公钥。 假设Alice想要发送的消息可以适当地编码为E上的点 这时她首先随机选择一个指数k=8，然后计算 把这两个数据一同传送给Bob。Bob利用自己的私钥b=3和收到的消息计算 从而完成了脱密