[互联网]第4讲 公钥密码体制.ppt

第第4 4讲 公钥密码体制讲 公钥密码体制主讲：谢昕第第4 4讲 公钥密码体制讲 公钥密码体制课程主要内容公钥密码体制概述公钥密码体制概述背包公钥密码背包公钥密码RSARSA公钥密码公钥密码椭圆曲线密码椭圆曲线密码概率加密等概率加密等2 第第4 4讲 公钥密码体制讲 公钥密码体制§1§1 公钥密码体制概述 公钥密码体制概述对称密钥密码体制问题：如何在网络上安全地传送和保管密钥？无法实现抗抵赖的需求等…1976年，美国学者Diffie和Hellman发表了著名论文《密码学的新方向》，提出了建立“公开密钥密码体制”：若用户A有加密密钥PK(公开)，不同于解秘密钥SK(保密)，要求PK的公开不影响SK的安全若B要向A保密送去明文m ，可查A的公开密钥PKA，若用PKA加密得密文c，A收到密文c后，用只有A自己才掌握的解密密钥SKA对x进行解密得到明文m 公开密钥密码体制是现代密码学最重要的发明公开密钥密码体制是现代密码学最重要的发明离散数学第第4 4讲 公钥密码体制讲 公钥密码体制Ø 尽人皆知的密钥叫做公开密钥(public key)；Ø 只有密钥拥有者才知道的密钥：私有密钥(private key) Ø 这两种密钥合在一起称为密钥对；Ø 公开密钥可以解决安全分配密钥问题（不需要与保密密钥通信，所传输的只有公开密钥，它不需要保密），但对保证其真实性和完整性却非常重要。

Ø 如果某一信息用公开密钥加密，则必须用私有密钥解密，这就是实现保密的方法Ø 如果某一信息用私有密钥加密，它必须用公开密钥解密，这就是实现验证的方法 §1§1 公钥密码体制概述 公钥密码体制概述离散数学第第4 4讲 公钥密码体制讲 公钥密码体制算法特点算法特点：使用一个加密算法：使用一个加密算法E E和一个解密算法和一个解密算法DD，，它们它们彼此完全不同，根据已选定的彼此完全不同，根据已选定的E E和和DD，，即使已知即使已知E E的完整描的完整描述，也不可能推导出述，也不可能推导出DD §1§1 公钥密码体制概述 公钥密码体制概述离散数学第第4 4讲 公钥密码体制讲 公钥密码体制§1§1 公钥密码体制概述 公钥密码体制概述数字签名必须保证做到以下数字签名必须保证做到以下3 3点：点：（ （1 1）接收者能够核实发送者对报文的签名；）接收者能够核实发送者对报文的签名；（ （2 2）发送者事后不能抵赖对报文的签名；）发送者事后不能抵赖对报文的签名；（ （3 3）接收者不能伪造对报文的签名接收者不能伪造对报文的签名离散数学第第4 4讲 公钥密码体制讲 公钥密码体制RSA是一种基于公钥密码体制的优秀加密算法，1978年由美国(MIT)的李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提的。

RSA算法是一种分组密码体制算法，它的保密强度是建立建立在具有大素数因子的合数其因子分解是困难的在具有大素数因子的合数其因子分解是困难的（基于大数分解的难度）公钥和私钥是一对大素数的函数，从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准§2§2 RSARSA公钥密码体制公钥密码体制离散数学第第4 4讲 公钥密码体制讲 公钥密码体制整数整数n n的 因子分解的 所需计算的 因子分解的 所需计算十进制位数十进制位数 运算次数 运算次数 时间 时间5050 1.4x10 1.4x1010103.9 3.9小时小时7575 9.0x10 9.0x101212104 104天天100100 2.3x10 2.3x10151574 74年年200200 1.2x10 1.2x1023233.8x10 3.8x109 9年年300300 1.5x10 1.5x1029294.0x10 4.0x101515年年500500 1.3x10 1.3x1039394.2x10 4.2x102525年年 （每微秒一次）§2§2 RSARSA公钥密码体制公钥密码体制离散数学第第4 4讲 公钥密码体制讲 公钥密码体制RSARSA密钥体制的特点：密钥体制的特点：（（1 1））密钥配发十分方便密钥配发十分方便，用户的公开密钥可以像本那，用户的公开密钥可以像本那样公开，使用方便，每个用户只需持有一对密钥即可实现样公开，使用方便，每个用户只需持有一对密钥即可实现与网络中任何一个用户的保密通信。

与网络中任何一个用户的保密通信2 2））RSARSA加密原理加密原理基于单向函数基于单向函数，非法接收者利用公开，非法接收者利用公开密钥不可能在有限时间内推算出秘密密钥密钥不可能在有限时间内推算出秘密密钥RSARSA在在用户确认用户确认和和实现数字签名实现数字签名方面优于现有的其他方面优于现有的其他加密机制加密机制§2§2 RSARSA公钥密码体制公钥密码体制离散数学第第4 4讲 公钥密码体制讲 公钥密码体制单向函数：给定一个函数f，若对任意给定的x，计算y，使得y = f(x)是容易的；但对任意给定的y，计算x，使得 f(x) = y是难解的，即计算f -1(y)是困难的则称f为单向函数例：f(x)=ax（x、aGF(q)）为单向函数§2§2 RSARSA公钥密码体制公钥密码体制陷门单向函数：给定一个函数f，t为f 相关的参数，任意给定的x，计算y = f(x)是容易的；当t未知时，计算逆函数f -1(y)难解，而当t已知时，计算f -1(y)容易则称为f 陷门单向函数离散数学第第4 4讲 公钥密码体制讲 公钥密码体制用于构造双钥密码的单向函数：用于构造双钥密码的单向函数：（（1 1）多项式求根）多项式求根（（2 2））离散对数离散对数（（3 3））大整数分解大整数分解（（4 4））背包问题背包问题（（5 5））DiffieDiffie-Hellman-Hellman问题问题（（6 6）二次剩余问题）二次剩余问题（（7 7）模）模n n的平方根问题的平方根问题§2§2 RSARSA公钥密码体制公钥密码体制离散数学第第4 4讲 公钥密码体制讲 公钥密码体制§2.1§2.1 RSARSA公钥密码算法描述公钥密码算法描述（（1 1）设计密钥）设计密钥A A、在离线方式下，先产生两个足够大的强质数、在离线方式下，先产生两个足够大的强质数p p、、q q；；B B、令、令n=pn=p＊＊q q。

计算欧拉函数计算欧拉函数 ( (n n) )=(p-1)×(q-1)=(p-1)×(q-1)；；C C、选取一个与、选取一个与 ( (n n) )互素的奇数互素的奇数e e，称，称e e为公开指数；为公开指数；DD、根据、根据e×de×d=1 =1 mod(mod( ( (n n) )) )，找出，找出d d；；E E、舍弃、舍弃p p和和q q （但绝不能泄露）（但绝不能泄露） ，公开，公开(n(n，，e)e)，公钥；，公钥；F F、保密、保密(n(n，，d) d) 私钥离散数学第第4 4讲 公钥密码体制讲 公钥密码体制（（2 2）加密）加密对于明文对于明文MM，，用公钥用公钥 (n(n，，e) e) 加密可得到密文加密可得到密文C C C = MC = Me emod (n) mod (n)§2.1§2.1 RSARSA公钥密码算法描述公钥密码算法描述（（3 3））解密解密对于密文对于密文C C，，用私钥用私钥(n(n，，d)d)解密可得到明文解密可得到明文MMM = M = C Cd dmod (n) mod (n) 当定义用私钥(n，d)先进行解密后，然后用公钥(n，e)进行加密，就是数字签名。

离散数学第第4 4讲 公钥密码体制讲 公钥密码体制举例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.1§2.1 RSARSA公钥密码算法描述公钥密码算法描述离散数学第第4 4讲 公钥密码体制讲 公钥密码体制举例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 24362436=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§2.1§2.1 RSARSA公钥密码算法描述公钥密码算法描述13×d=k*2436+1d=(k*2436+1)/13,试凑离散数学第第4 4讲 公钥密码体制讲 公钥密码体制1、加密字串举例：若有明文public key encryptions2、先将明文分块为两个一组(此处为简化计算考虑)：pu bl ic ke ye nc ry pt io ns3、将明文数字化令a,b…,z 分别为00,01,…,25 得1520 0111 0802 1004 24041302 1724 1519 0814 13184、利用加密可得密文0095 1648 1410 1299 13651379 2333 2132 1751 13245、解密后又得到明文§2.1§2.1 RSARSA公钥密码算法描述公钥密码算法描述离散数学第第4 4讲 公钥密码体制讲 公钥密码体制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 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.1§2.1 RSARSA公钥密码算法描述公钥密码算法描述（2）加密离散数学第第4 4讲 公钥密码体制讲 公钥密码体制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)*(341*788)*95 mod 2537=230*2323 mod 2537= 1520 mod 2537 =1520（明文）§2.1§2.1 RSARSA公钥密码算法描述公钥密码算法描述（3）解密离散数学第第4 4讲 公钥密码体制讲 公钥密码体制§2.2§2.2 RSARSA算法的优缺点算法的优缺点优点：。