《第4讲 公钥密码体制》由会员分享，可在线阅读，更多相关《第4讲 公钥密码体制（96页珍藏版）》请在金锄头文库上搜索。
1、第4讲公钥密码体制,主讲：谢昕,2,课程主要内容,公钥密码体制概述,背包公钥密码,RSA公钥密码,椭圆曲线密码,概率加密等,1公钥密码体制概述,对称密钥密码体制问题：如何在网络上安全地传送和保管密钥？无法实现抗抵赖的需求等 1976年，美国学者Diffie和Hellman发表了著名论文密码学的新方向，提出了建立“公开密钥密码体制”：若用户A有加密密钥PK(公开)，不同于解秘密钥SK(保密)，要求PK的公开不影响SK的安全。若B要向A保密送去明文m ，可查A的公开密钥PKA，若用PKA加密得密文c，A收到密文c后，用只有A自己才掌握的解密密钥SKA对x进行解密得到明文m。,公开密钥密码体制是现代
2、密码学最重要的发明,离散数学,尽人皆知的密钥叫做公开密钥(public key)； 只有密钥拥有者才知道的密钥：私有密钥(private key) 这两种密钥合在一起称为密钥对； 公开密钥可以解决安全分配密钥问题（不需要与保密密钥通信，所传输的只有公开密钥，它不需要保密），但对保证其真实性和完整性却非常重要。 如果某一信息用公开密钥加密，则必须用私有密钥解密，这就是实现保密的方法。 如果某一信息用私有密钥加密，它必须用公开密钥解密，这就是实现验证的方法。,1公钥密码体制概述,离散数学,算法特点：使用一个加密算法E和一个解密算法D，它们彼此完全不同，根据已选定的E和D，即使已知E的完整描述，也不
3、可能推导出D。,1公钥密码体制概述,离散数学,1公钥密码体制概述,数字签名必须保证做到以下3点： （1）接收者能够核实发送者对报文的签名； （2）发送者事后不能抵赖对报文的签名； （3）接收者不能伪造对报文的签名。,离散数学,RSA是一种基于公钥密码体制的优秀加密算法，1978年由美国(MIT)的李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提的。 RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数其因子分解是困难的（基于大数分解的难度）。 公钥和私钥是一对大素数的函数，从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积。 RSA得到
4、了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。,2 RSA公钥密码体制,离散数学,整数n的因子分解的所需计算 十进制位数 运算次数 时间 50 1.4x1010 3.9小时 75 9.0 x1012 104天 100 2.3x1015 74年 200 1.2x1023 3.8x109年 300 1.5x1029 4.0 x1015年 500 1.3x1039 4.2x1025年,（每微秒一次）,2 RSA公钥密码体制,离散数学,RSA密钥体制的特点： （1）密钥配发十分方便，用户的公开密钥可以像电话本那样公开，使用方便，每个用户只需持有一对
5、密钥即可实现与网络中任何一个用户的保密通信。 （2）RSA加密原理基于单向函数，非法接收者利用公开密钥不可能在有限时间内推算出秘密密钥。 RSA在用户确认和实现数字签名方面优于现有的其他加密机制。,2 RSA公钥密码体制,离散数学,单向函数： 给定一个函数f，若对任意给定的x，计算y，使得y = f(x)是容易的；但对任意给定的y，计算x，使得 f(x) = y是难解的，即计算f -1(y)是困难的。则称f为单向函数。 例：f(x)=ax（x、aGF(q)）为单向函数。,2 RSA公钥密码体制,陷门单向函数： 给定一个函数f，t为f 相关的参数，任意给定的x，计算y = f(x)是容易的；当t
6、未知时，计算逆函数f -1(y)难解，而当t已知时，计算f -1(y)容易。则称为f 陷门单向函数。,离散数学,用于构造双钥密码的单向函数： （1）多项式求根 （2）离散对数 （3）大整数分解 （4）背包问题 （5）Diffie-Hellman问题 （6）二次剩余问题 （7）模n的平方根问题,2 RSA公钥密码体制,离散数学,2.1RSA公钥密码算法描述,（1）设计密钥 A、在离线方式下，先产生两个足够大的强质数p、q； B、令n=pq。计算欧拉函数(n)=(p-1)(q-1)； C、选取一个与(n)互素的奇数e，称e为公开指数； D、根据ed=1 mod(n)，找出d； E、舍弃p和q （但
7、绝不能泄露） ，公开(n，e)，公钥； F、保密(n，d) 私钥。,离散数学,（2）加密 对于明文M，用公钥 (n，e) 加密可得到密文C。 C = Me mod (n),2.1RSA公钥密码算法描述,（3）解密 对于密文C，用私钥(n，d)解密可得到明文M。 M = Cd mod (n),当定义用私钥(n，d)先进行解密后，然后用公钥(n，e)进行加密，就是数字签名。,离散数学,举例1：选取p=3, q=5，则n=pq =15，(n)=(p-1)(q-1)=8 选取e=11（大于p和q的质数）； 由d11=1 mod 8，计算出d =3， 得到公开密钥：（n，e）=（15，11） 私有密钥：
8、（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.1RSA公钥密码算法描述,离散数学,举例2：设p=43,q=59,n=pq=43*59=2537, (n)=(p-1)(q-1) =42*58 =2436, 取e=13,求e的逆元d 解方程 de = 1 mod 2436 2436=13187+5, 13=25+3
9、，5=3+2，3=2+1 所以1=3-2，2=5-3，3=13-25，5 =2436-13187 所以，1=3-2=3-(5-3)=23-5=2(13-25)-5 =213-55=213-5(2436-13187) =93713-52346 即937131 mod 2436 取e=13时，d= 937,2.1RSA公钥密码算法描述,13d=k*2436+1 d=(k*2436+1)/13,试凑,离散数学,1、加密字串举例：若有明文public key encryptions 2、先将明文分块为两个一组(此处为简化计算考虑)： pu bl ic ke ye nc ry pt io ns 3、将明
10、文数字化令a,b,z 分别为00,01,25 得 1520 0111 0802 1004 2404 1302 1724 1519 0814 1318 4、利用加密可得密文 0095 1648 1410 1299 1365 1379 2333 2132 1751 1324 5、解密后又得到明文,2.1RSA公钥密码算法描述,离散数学,C=Me mod n=152013 mod 2537 = (15202)6*1520 mod 2537 15202 1730 mod 2537 C= (1730)6*1520 mod 2537 = (17302)3*1520 mod 2537 17302 1777
11、mod 2537 C= (1777)3*1520 mod 2537 = (1777)2*1777*1520 mod 2537 17772 1701 mod 2537 C=1701*(1777*1520) mod 2537 =1701*1672 mod 2537 =95（密文）,2.1RSA公钥密码算法描述,（2）加密,离散数学,M = Cd mod n= 95937 mod 2537 = (952)468*95 mod 2537 = (1414)468*95 mod 2537 = (14142)234*95 mod 2537 = (240)234*95 mod 2537 = (625*25)*
12、(341*788)*95 mod 2537 =230*2323 mod 2537 = 1520 mod 2537 =1520（明文）,2.1RSA公钥密码算法描述,（3）解密,离散数学,2.2RSA算法的优缺点,优点： 是第一个能同时用于加密和数字签名的算法，也易于理解和操作，也是被研究得最广泛的公钥算法，二十年来经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。 特别符合计算机网络环境。 对于网上的大量用户，可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信，只需从公钥簿上查出对方的加密密钥，用它
13、对所传送的信息加密发出即可。对方收到信息后，用仅为自己所知的解密密钥将信息解密，了解报文的内容。,离散数学,缺点： （1）产生密钥很麻烦，难以做到一次一密。 （2）RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。目前人们已能分解140多位十进制位的大素数，这就要求使用更长的密钥，速度更慢。而且目前人们正在积极寻找攻击RSA的方法。 （3）速度太慢, RSA的分组长度太大。为了速度问题，目前人们广泛使用单、公钥密码结合使用的方法，优缺点互补：单钥密码加密速度快， 用它来加密较长的文件，然后用RSA来给文件密钥加密，极好的解决了单钥密码的密钥分发问题。,
14、2.2RSA算法的优缺点,离散数学,2.3RSA密码体制的实现,实现的步骤如下：(Bob为实现者) (1)Bob寻找出两个大素数p和q； (2)Bob计算出n=p*q和(n)=(p-1)(q-1)； (3)Bob选择一个随机数e(0e(n) 满足gcd(e, (n)= 1； (4)Bob使用辗转相除法计算d=e-1(mod (n)； (5)Bob在目录中公开n和e作为他的公钥。,密码分析者攻击RSA体制的关键点在于如何分解n。 若分解成功使n=p*q，则可以算出(n)=(p-1)(q-1) 。然后由公开的e 解出秘密的d。,离散数学,RSA密码系统设计要求： （1）p、q必须选择强素数 （2）
15、p、q之差必须很大 （3）p1、q1的最大公约数应尽量小 （4）p、q选择应足够大 （5）e不可以太小 （6）e应选择使模(n)的阶最大,2.3RSA密码体制的实现,离散数学,美国斯坦福大学的Merkle和Hellman于1978年提出的。 背包问题描述：已知一长度为b的背包及长度分别为a1,a2,an的n个物品。假定这些物品的直径与背包相同，若从这些物品中选出若干个正好装满这个背包，究竟是哪些物品。 数学描述：已知b，求解a1x1+ a2x2 + + anxn = b，其中a1,a2,an和b都是正整数。 背包问题目前尚无有效求解算法。 背包公钥密码：选取正整数a1,a2,an作为公钥，明文
16、位串 为m= m1m2mn，利用公钥加密问题c= a1m1+ a2m2 + + anmn 。从密文c求明文m等价于背包问题。,3背包公钥密码体制,离散数学,MH公钥背包密码：其背包系列a1,a2,an是由超递增系列b1,b2,bn（ ）经过MH变换ak=wbk得到的。 虽然a1,a2,an不具有超递增性，但可经变换后成为超递增系列求解。若超递增背包问题确实有解，则容易用所谓的贪心算法求出其解。 例：超递增序列1，2，4，2n，若背包方程 x1+ 2x2 + 4x3 + 8x4 + 16x5+ 32x6 = 47 则x6 =1，x5 =0，x4 =1，x3 =1，x2 =1，x1 =1 所以密文为：111101,3背包公钥密码体制,离散数学,MH公钥背包密码过程： （1）密钥生成 用户构造长度为n的超递增背包分量b1,b2,bn，选择两个正整数M、W，其中 ，WM且保证gcd(W,M)=1。 则由W W-11 mod M，求出W-1（0 W-1M)， 计算ai = W
