5.2公钥密码体制.pptVIP

公钥密码体制 公钥密码体制的基本原理 对称密码体制的缺点： 密钥分配和管理 传统密钥管理两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时密钥空间急剧增大如: n=100 时C(100,2)=4,995 n=5000时C(5000,2)=12,497,500 确证问题 数字签名 公开钥密码的基本思想 用户选择一对密钥Ke和Kd，分别为公开钥和秘密钥，并构造加密算法Ee和解密算法Ed 已知： C = E(M,Ke) M = D(C,Kd)=D(E(M,Ke),Kd) 用户公开Ke和Ee 若用户A想向用户B传送一条消息M 公开密钥加密方法1 方法1缺点 任何人都能够冒充用户A给B发消息，B无法察觉 无法保证信息的真实性 公开密钥加密方法2 A用自己必威体育官网网址的密钥KdA解密M,得到密文C，将C发给B，B收到C以后，查A的公开加密钥KeA,用KeA加密C后得到明文M 方法2缺点 无法保证信息的秘密性 公开密钥加密方法3 公开密钥密码应当满足的条件 加密算法和解密算法互逆，即对所有明文都有 D(E(M,Ke),Kd)=M 计算上不能由Ke求出Kd 算法E和D都是高效的 E(D(M,Kd),Ke)=M 单项陷门函数 单向陷门函数是满足下列条件的函数f (1)给定x，计算y=f(x)是容易的 (2)给定y, 计算x使y=f(x)是困难的 (所谓计算x=f-1(Y)困难是指计算上相当复杂已无 实际意义) (3)存在k 已知k时,对给定的任何y,若相应的x存在,则计算x使y=f(x)是容易的 几个典型的公开钥密码系统 RSA系统 背包系统 椭圆曲线密码体制 RSA 算法 RSA公钥算法是由Rivest,Shamir Adleman在1978年提出来的。 该算法的数学基础是初等数论中的Euler (欧拉)定理,并建立在大整数因子的困难性之上。 素数(Prime Numbers) 一个大于1的整数，如果它的正因数只有1和它本身，就叫做质数（素数），否则就叫做合数。 eg. 2,3,5,7 素数， 4,6,8,9,10 不是 素数在数论中具有重要的地位 小于200 的素数有: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 素因子分解 数n的因子分解是把它写成其它数的乘积 n=a × b × c 相对于把因子相乘得到一个数，进行一个数的因子分解是困难的。 素因子分解是把一个数写成素数的乘积形式 eg. 91=7×13 ; 3600=24×32×52 RSA的安全性基于大整数分解因子的困难性 N为两个大素数p和q的乘积，分解n被认为是非常困难的 生成RSA密钥 选择两个素数p,q,对外界必威体育官网网址 计算n=pq 计算? (n)=(p-1)(q-1) 选择e,使它成为是? (n)的一个互质数 确定d,使得de=1mod ? (n),并且d ? (n) 基本算法 C=Me mod n M=Cd mod n 公钥：{e,n} 私钥：{d,n} 在等式中,mod表示计算余数，例如12 mod 10=2 例子： 选择p=7,q=17 N=pq=119, ? (n)=(p-1)(q-1)=6*16=96 选择随机整数e=5，与96互素 找出d,使得d*e=1mod96,选择d=77 算法 C=Me mod n M=Cd mod n 选择明文19，C=195mod119=66 密文66，M=6677mod119=19 RSA算法的安全性 对RSA算法的攻击实际上等效于对n的乘积分解。 由于M=Cd mod n, n公开,则需要求出d 有由于de=1mod ? (n), e已知 需要求出? (n) 由于? (n)=(p-1)(q-1)，所以必须求出p,q n=pq,所以必须对n进行分解 * * 加密算法E 解密算法D 加密密钥Ke 解密密钥Kd 明文m 明文m 公开，其他用户可以像查找电话号码一样查到 用户A 用户B M 用户A 用户B C Ke Kd 对称密钥加密方法 用户A 用户B C KeB KdB A查到B的公开加密钥KeB,用它加密M后得到C,将C发给B，B收到C以后，用自己必威体育官网网址的解密钥KdB解密C,得到明文M 查找 找到KeB 用户A 用户B C KeB KdB 查找 找到KeB 用户C 此消息对用户A可能不利 用户A 用户B C KdA KeA 查找 找到KeA 用户A 用户B C KdA KeA 查找 找到KeA 用