第四讲公钥密码体制.pptVIP

第4讲　公钥密码体制;课程主要内容;§1　公钥密码体制概述;　尽人皆知的密钥叫做公开密钥(public key)； 　只有密钥拥有者才知道的密钥：私有密钥(private key) 　这两种密钥合在一起称为密钥对； 　公开密钥可以解决安全分配密钥问题（不需要与必威体育官网网址密钥通信，所传输的只有公开密钥，它不需要必威体育官网网址），但对保证其真实性和完整性却非常重要。 如果某一信息用公开密钥加密，则必须用私有密钥解密，这就是实现必威体育官网网址的方法。 　 如果某一信息用私有密钥加密，它必须用公开密钥解密，这就是实现验证的方法。 ; 算法特点：使用一个加密算法E和一个解密算法D，它们彼此完全不同，根据已选定的E和D，即使已知E的完整描述，也不可能推导出D。 ;§1　公钥密码体制概述; 　RSA是一种基于公钥密码体制的优秀加密算法，1978年由美国(MIT)的李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提的。 　RSA算法是一种分组密码体制算法，它的必威体育官网网址强度是建立在具有大素数因子的合数其因子分解是困难的（基于大数分解的难度）。 　公钥和私钥是一对大素数的函数，从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积。 RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。;　整数n的　　　　　　因子分解的　　　所需计算 十进制位数 　　　　　运算次数 　　　　时间 50 1.4x1010 3.9小时 75 9.0x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年 500 1.3x1039 4.2x1025年 ;RSA密钥体制的特点： （1）密钥配发十分方便，用户的公开密钥可以像电话本那样公开，使用方便，每个用户只需持有一对密钥即可实现与网络中任何一个用户的必威体育官网网址通信。 （2）RSA加密原理基于单向函数，非法接收者利用公开密钥不可能在有限时间内推算出秘密密钥。 RSA在用户确认和实现数字签名方面优于现有的其他加密机制。;单向函数： 给定一个函数f，若对任意给定的x，计算y，使得y = f(x)是容易的；但对任意给定的y，计算x，使得 f(x) = y是难解的，即计算f -1(y)是困难的。则称f为单向函数。 例：f(x)=ax（x、a?GF(q)）为单向函数。;用于构造双钥密码的单向函数： （1）多项式求根 （2）离散对数 （3）大整数分解 （4）背包问题 （5）Diffie-Hellman问题 （6）二次剩余问题 （7）模n的平方根问题;§2.1　RSA公钥密码算法描述;（2）加密 对于明文M，用公钥 (n，e) 加密可得到密文C。　 C = Me mod (n);举例1：选取p=3, q=5，则n=p＊q =15，?(n)=(p-1)(q-1)=8 选取e=11（大于p和q的质数）； 由d×11=1 mod 8，计算出d =3， 　　得到公开密钥：（n，e）=（15，11） 　　　　私有密钥：（n，d）=（15，3） 假定明文M为整数13。则密文　　 C=Me mod n=1311 mod 15 = (132)5*13 mod 15 = (132 mod 15 ) 5 *13 mod 15=4 5 *13 mod 15=7 复原明文M为： M = Cd mod n= 73 mod 15= 343 mod 15 = 13;举例2：设p=43,q=59,n=p?q=43*59=2537, ?(n)=(p-1)(q-1) =42*58 =2436, 取e=13,求e的逆元d 解方程 d×e = 1 mod 2436 2436=13×187+5, 13=2×5+3，5=3+2，3=2+1 所以1=3-2，2=5-3，3=13-2×5，5 =2436-13×187 所以，1=3-2=3-(5-3)=2×3-5=2×(13-2×5)-5 =2×13-5×5=2×13-5×(2436-13×187) =937×13-5×2346 即937×13≡1 mod 2436 取e=13时，d= 937;1、加密字串举例：若有明文public key encryptions 2、先将明文分块为两个一组(此处为简化计算考虑)： 　　　pu bl ic ke ye nc ry pt io ns 3、将明文数字化令a,b…