第5章[第3部分]公钥密码及Rabin密码及椭圆曲线密码.ppt

第5章[第3部分]公钥密码及Rabin密码及椭圆曲线密码.ppt

  1. 1、本文档共29页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第5章[第3部分]公钥密码及Rabin密码及椭圆曲线密码

椭圆曲线密码体制概述 椭圆曲线举例 加法运算 加法运算 密码学中用的椭圆曲线 椭圆曲线上点的产生 加法定义 加法定义 加法举例-不同点相加 以E23(1,1)为例,设P=(3,10),Q=(9,7),计算P+Q 加法举例-同点相加 求2P, P=(3,10) DH体制 DH体制 DH体制举例 ECC举例 网络工程学院? 第5章 公钥密码体制(3)   对RSA密码体制,n被分解成功,该体制便被破译,即破译RSA的难度不超过大整数的分解,但不能证明破译RSA和分解大整数是等价的。   Rabin密码体制已被证明对该体制的破译与分解大整数是等价的,它有两个特点: 1、它不是以一一对应的单向陷门函数为基础,对同一密文,可能有两个以上对应的明文 2、破译该体制与分解大整数是等价的 概述 密码体制(1) 1、密钥产生 随机选择两个大素数p, q,满足p≡ q≡ 3 mod 4,即这两个素数形式为4k+3;计算n=p*q。 以n作为公钥,p, q作为密钥 2、加密 c ≡ m2modn m是明文分组,c是对应的密文分组 密码体制(2) 3、解密   解密即为求解x2 ≡ c ≡ m2modn,由中国剩余定理知该方程等价于解方程组       x2 ≡cmodp x2 ≡cmodq 由于p≡ q≡ 3 mod 4,下面将看到,方程组的解可容易求出,其中每个方程都有两个解,即 x≡m mod p, x≡-mmod p x≡m mod q, x≡-m mod q 经过组合可得到4个同余方程组: x≡-m mod q x≡-m mod q x≡m mod q x≡m mod q x≡-mmod p x≡m mod p x≡-mmod p x≡m mod p 由中国剩余定理可解出每一方程组的解,共有4个,即每一密文对应的明文不惟一。为了有效确定明文,可在m中加入某些双方商定的信息,如日期、发送者的ID等。 解密 p≡q≡3 mod 4,下面将看到,方程组的解可容易求出: 一个结论:对x2 ≡cmodp,c是modp的平方剩余的充要条件是c(p-1)/2≡1modp 简单推导:x2 ≡cmodp =>x(p-1) ≡c(p-1)/2modp 因为c是modp的平方剩余,故c不能被p 整除,所以x也不能被p 整除 由Fermat定理可知x(p-1) ≡1modp, 故c(p-1)/2≡1modp 解方程组 p≡q≡3 mod 4,可得:p+1=4k,即(p+1)/4是一个整数。 则(c(p+1)/4)2≡ (c(p+1)/2≡ c(p-1)/2*c≡cmodp 故(c(p+1)/4和p-(c(p+1)/4是方程x2 ≡cmodp的两个根。同理,故(c(q+1)/4和q-(c(q+1)/4是方程x2 ≡cmodq的两个根 解方程组 例:p=11, q=23, 则n=253 公钥为253,私钥为(11,23) 取m’=6=110,重复后两位,则加密的明文为m=11010,m为十进制的26。 1.加密:c=m2modn=262mod 253=676mod 253=170,加密的密文即为170。 2.解密:设x2=170 mod 253 密码体制例 由中国剩余定理,其等价于 x2=170 mod 11=5 mod 11 x2=170 mod 23=9 mod 23 ?由公式知: x= c(p+1)/4=53mod 11 =±4 x= c(p+1)/4=56mod 23=±3 ?其等价于 x≡4 mod 11 x≡-4mod 11 x≡4mod11 x≡-4mod 11 x≡3 mod 23 x≡3 mod 23 x≡-3 mod 23 x≡-3 mod 23 ?其解依次为26, 95,158, 227 密码体制例 例:实体A选择素数p=277,q=331,计算n=pq=91687,A的公钥是n=91687,A的私钥是(p=277, q=331)。 假设在加密之前需要复制原信息的后6位,为加密10位信息,B复制的后6位得到16位信息m=1001111001111001,用十进制数字表示为m=40569。B计算得c=m2 mod n=405692mod 91687=62111并发送给A。 为解密c,A计算c mod n的四个平方根: m1=69654 m2=22033 m3=40569 m4=51118 二进制表示为: m1=10001000000010110 m2=101011000010001 m3=1001111001111001   m4=1100011110101110 密码体制例 为保证RSA算法的安全性

文档评论(0)

xcs88858 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:8130065136000003

1亿VIP精品文档

相关文档