现代密码学第5章公钥密码.ppt

第5章 公钥密码 主要内容 5. 1 公钥密码的理论基础 5. 2 RSA公钥密码 5. 2. 1 中国剩余定理 5. 2. 2 Euler 函数 5. 2. 3 Euler定理和Fermat小定理 5. 2. 4 RSA 公钥密码体制 5. 2. 5 RSA 的安全性讨论 5. 2. 6 模n求逆的算法 5. 2. 7 模n的大数幂乘的快速算法 5. 2. 8 因子分解 5.3 大素数的生成 5. 3. 1 素数的分布 5. 3. 2 模奇素数的平方剩余 5. 3. 3 Legendre 符号 5. 3. 4 Jacobi 符号 5. 3. 5 Solovay-Strassen 素性测试法 5. 3. 6 Miller-Rabin 素性测试法 5. 4 EIGamal 公钥密码 5. 4. 1 EIGamal 公钥密码体制 5. 4. 2 EIGamal 公钥密码体制的安全性 5. 4. 3 有限域上离散对数的计算方法 5. 5 椭圆曲线上的Menezes-Vanstone 公钥密码 5. 5. 1 椭圆曲线的定义 5. 5. 2 实数域上椭圆曲线的图像 5. 5. 2 实数域上椭圆曲线的图像 5. 5. 3 实数域上椭圆曲线点的加法运算 5. 5. 4 实数域上椭圆曲线点加法运算的性质 5. 5. 5 有限域上的椭圆曲线 5. 5. 6 有限域上的椭圆曲线的性质 5. 5. 7 椭圆曲线上的离散对数问题 5. 5. 8 Menezes-Vanstone 公钥密码体制 定理5.20 (Hasse 定理) 设E 是有限域 上的椭圆曲线, 则 定理5.21 (Hasse 定理) 设E 是有限域 上的椭圆曲线, 则 其中t 的绝对值 定理5.22 (椭圆曲线的群结构) 设E 是有限域 上的椭圆曲线, p 3 为素数, 则存在正整数 和 ，使得E 与 同构, 和 满足 并且 定义5.11 设E 是有限域 上的椭圆曲线, 的阶是满足 的最小正整数n, 记为ord(P), 其中O 是无穷远点。 定义5.12 设p 3 是一个素数, E 是有限域 上的椭圆曲线. 设G 是E的一个循环子群, P 是G 的一个生成元, Q ∈ G. 已知P 和Q, 求满足nP = Q的唯一整数 称为椭圆曲线上的离散对数问题。 随机选取整数d， 1 ≤d ≤ ord(α) ? 1。计算β = dα， β是公开的加密密钥，d是保密的解密密钥 Menezes-Vanstone公钥密码体制描述如下 设p 3 是一个大素数，E 是有限域Zp 上的椭圆曲线。 α ∈ E是椭圆曲线 上的一个点，并且α的阶足够大，使得在由α生成的循环子群中离散对数 问题是难解的。p 和E 以及α都公开 明文空间为 密文空间为 加密变换：对任意明文 ，秘密随机选取一 个整数k，1 ≤ k ≤ ord(α) ? 1，密文为 其中 解密变换：对任意密文 明文为 其中 点击此处返回 RIP是一种基于距离矢量算法的协议，它通过UDP报文进行路由信息的交换，使用的端口号为520。RIP使用跳数来衡量到达目的地址的距离，跳数也称为度量值。在RIP中，路由器到与它直接相连网络的跳数为0，通过一个路由器可达的网络的跳数为1，其余依此类推。为限制收敛时间，RIP规定度量值取0～15之间的整数，大于或等于16的跳数被定义为无穷大，即目的网络或主机不可达。由于这个限制，使得RIP不适合应用于大型网络。为提高性能，防止产生路由环路，RIP支持水平分割（split horizon）和毒性逆转（poison reverse）功能。 * 公钥密码的理论基础 RSA 公钥密码 大素数的生成 EIGamal 公钥密码 椭圆曲线上的Menezes-Vanstone 公钥密码 在公钥密码中, 加密密钥和解密密钥是不一样的。 加密密钥简称公钥(publickey), 解密密钥简称私钥(private key)。加密密钥可以公开, 解密密钥当然必须保密。 定义5.1 设f 是一个函数. 如果对任意给定的x, 计算y 使得y = f(x) 是容易的, 但对任意给定的y, 计算x 使得f(x) = y 是难解的, 即求f 的逆函数是难解的, 则称f 是一个单向函数(