第四章公钥密码体制81046new

《第四章公钥密码体制81046new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章公钥秘密体制1传统密码体制的缺陷：（1）密钥必须通过某一信道协商对这个信道的安全性的要求比正常的传送消息的信道的安全性要高（2）密钥管理量的困难传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500（3）数字签名的问题传统加密算法无法实现抗抵赖的需求。24.1公钥密码体制的基本原理1976年，美国学者Diffie和Hellman发表了著名论文《密码学的新方向》，提出了建立“公开密钥密码体

2、制”：若用户A有加密密钥ka（公开），不同于解秘密钥ka’（保密），要求ka的公开不影响ka’的安全。若B要向A保密送去明文m,可查A的公开密钥ka，若用ka加密得密文c，A收到c后，用只有A自己才掌握的解密密钥ka’对x进行解密得到m。公开密钥算法3公钥密码体制4公钥密码学解决的基本问题密钥交换对称密码进行密钥交换的要求：已经共享一个密钥利用密钥分配中心数字签名与传统的签名比较5公钥密码学是密码学一次伟大的革命使用两个密钥：公钥、私钥六个组成部分：明文、密文；公钥、私钥；加密、解密算法仅根据密码算法和加密密钥来确定解密密钥在计算上不可行加解密的非对称性是对对

3、称密码的重要补充6公开密钥算法公开密钥密码体制基于陷门单向函数单向函数f(x)P50(1)给定x，计算y=f(x)是容易的；(2)给定y,计算x使y=f(x)是非常困难的，具有陷门信息的单向函数(3)存在δ，已知δ时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。单向陷门函数的例子暗码锁、xbmodn单纯的单向函数不能用作加密函数公钥密码学的理论基础7公钥方案的安全性•和对称方案一样，公钥密码体制不是无条件安全的，我们只研究公钥体制的计算安全性•安全性基于一些陷门单向函数–求逆只是计算上不可行–要求使用非常大的数–因此比对称方案计算速度慢84

4、.2RSA算法1977年，美国麻省理工学院(MIT)的研究小组成员：李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提出了一种基于公钥密码体制的优秀加密算法——RSA算法。RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数，其因子分解是困难的。(困难的衡量标准:是否是NP问题)。RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。1999年美国参议院已通过了立法，规定电子数字签名与手写签名的文件、邮件在美国具有同等的法律效力。公开密钥算法9定义1素数：只

5、能被1和它本身整除的自然数；否则为合数。每个合数都可以唯一地分解出素数因子6=2·3999999=3·3·3·7·11·13·3727641=131·121从2开始试验每一个小于等于√27641的素数。整数n的十进制位数因子分解的运算次数所需计算时间（每微秒一次）501.4x10103.9小时759.0x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0x1015年5001.3x10394.2x1025年数论知识简介10定义2互素：若a,b都为整数，且gcd(a,b)=1，则整数a和b互素。11数论知

6、识简介定义3模运算同余：如果a和b都是整数，而m是一个固定的正整数，则当m能够整除a-b时，称a,b对模m同余，记为ab(modm),如果a除m的余数为r,则r称为a模m的剩余，记作amodm.如amodm=bmodm，表示(a-b)modm=0；定义:zm={0,1,2,3,……m-1},为模m剩余集,其中m为整数.12数论知识简介模运算：9＋9＝6mod129×9＝9mod129－10＝11mod12模运算的性质：[(amodm)+(bmodm)]modm=(a+b)modm；--；**；例：152mod12=(3*3)mod12=913数论知识简介a,

7、x,n都为整数定义4若a•xmodm=1，则称a与x在乘法运算下关于模m互为逆元。如2和3关于模5互为逆元。若a和m互素，则a在模m下有逆元。故zm*中每个元素关于模m都有逆元。用Euclid算法求乘法逆元。zm*定义为zm中与m互素的数的集合.Euler函数：φ(n)=与n互素的、小于n的正整数的个数，即zm*中元素的个数。例：φ(3)=φ(4)=φ(6)=2，φ(5)=4，φ(7)=6，φ(12)=6若n是素数，则φ(n)=n-1若n=p*q，p、q是不同素数，则φ(n)=(p-1)*(q-1)例：φ(21)=φ(3*7)=2*6=1214RSA算法由MI

8、T的Rivest,Shamir&Adl