第4讲 公钥密码体制

第4讲公钥密码体制主讲：谢昕第4讲公钥密码体制2课程主要内容公钥密码体制概述背包公钥密码RSA公钥密码椭圆曲线密码概率加密等第4讲公钥密码体制3§1公钥密码体制概述对称密钥密码体制问题：如何在网络上安全地传送和保管密钥？无法实现抗抵赖的需求等…1976年，美国学者Diffie和Hellman发表了著名论文《密码学的新方向》，提出了建立“公开密钥密码体制”：若用户A有加密密钥PK(公开)，不同于解秘密钥SK(保密)，要求PK的公开不影响SK的安全。若B要向A保密送去明文m，可查A的公开密钥PKA，若用PKA加密得密文c，A收到密文c后，用只有A自己才掌握的解密密钥SKA对x进行解密得到明文m。公开密钥密码体制是现代密码学最重要的发明第4讲公钥密码体制4尽人皆知的密钥叫做公开密钥(publickey)；只有密钥拥有者才知道的密钥：私有密钥(privatekey)这两种密钥合在一起称为密钥对；公开密钥可以解决安全分配密钥问题（不需要与保密密钥通信，所传输的只有公开密钥，它不需要保密），但对保证其真实性和完整性却非常重要。如果某一信息用公开密钥加密，则必须用私有密钥解密，这就是实现保密的方法。如果某一信息用私有密钥加密，它必须用公开密钥解密，这就是实现验证的方法。§1公钥密码体制概述第4讲公钥密码体制5算法特点：使用一个加密算法E和一个解密算法D，它们彼此完全不同，根据已选定的E和D，即使已知E的完整描述，也不可能推导出D。§1公钥密码体制概述第4讲公钥密码体制6§1公钥密码体制概述数字签名必须保证做到以下3点：（1）接收者能够核实发送者对报文的签名；（2）发送者事后不能抵赖对报文的签名；（3）接收者不能伪造对报文的签名。第4讲公钥密码体制7RSA是一种基于公钥密码体制的优秀加密算法，1978年由美国(MIT)的李维斯特(Rivest)、沙米尔(Shamir)、艾德曼(Adleman)提的。RSA算法是一种分组密码体制算法，它的保密强度是建立在具有大素数因子的合数其因子分解是困难的（基于大数分解的难度）。公钥和私钥是一对大素数的函数，从一个公钥和密文中恢复出明文的难度等价于分解两个大素数之积。RSA得到了世界上的最广泛的应用，ISO在1992年颁布的国际标准X.509中,将RSA算法正式纳入国际标准。§2RSA公钥密码体制第4讲公钥密码体制8整数n的因子分解的所需计算十进制位数运算次数时间501.4x10103.9小时759.0x1012104天1002.3x101574年2001.2x10233.8x109年3001.5x10294.0x1015年5001.3x10394.2x1025年（每微秒一次）§2RSA公钥密码体制第4讲公钥密码体制9RSA密钥体制的特点：（1）密钥配发十分方便，用户的公开密钥可以像电话本那样公开，使用方便，每个用户只需持有一对密钥即可实现与网络中任何一个用户的保密通信。（2）RSA加密原理基于单向函数，非法接收者利用公开密钥不可能在有限时间内推算出秘密密钥。RSA在用户确认和实现数字签名方面优于现有的其他加密机制。§2RSA公钥密码体制第4讲公钥密码体制10单向函数：给定一个函数f，若对任意给定的x，计算y，使得y=f(x)是容易的；但对任意给定的y，计算x，使得f(x)=y是难解的，即计算f-1(y)是困难的。则称f为单向函数。例：f(x)=ax（x、aGF(q)）为单向函数。§2RSA公钥密码体制陷门单向函数：给定一个函数f，t为f相关的参数，任意给定的x，计算y=f(x)是容易的；当t未知时，计算逆函数f-1(y)难解，而当t已知时，计算f-1(y)容易。则称为f陷门单向函数。第4讲公钥密码体制11用于构造双钥密码的单向函数：（1）多项式求根（2）离散对数（3）大整数分解（4）背包问题（5）Diffie-Hellman问题（6）二次剩余问题（7）模n的平方根问题§2RSA公钥密码体制第4讲公钥密码体制12§2.1RSA公钥密码算法描述（1）设计密钥A、在离线方式下，先产生两个足够大的强质数p、q；B、令n=p＊q。计算欧拉函数(n)=(p-1)×(q-1)；C、选取一个与(n)互素的奇数e，称e为公开指数；D、根据e×d=1mod((n))，找出d；E、舍弃p和q（但绝不能泄露），公开(n，e)，公钥；F、保密(n，d)私钥。第4讲公钥密码体制13（2）加密对于明文M，用公钥(n，e)加密可得到密文C。C=Memod(n)§2.1RSA公钥密码算法描述（3）解密对于密文C，用私钥(n，d)解密可得到明文M。M=Cdmod(n)当定义用私钥(n，d)先进行解密后，然后用公钥(n，e)进行加密，就是数字签名。第4讲公钥密码体制14举例1：选取p=3,q=5，则n=p＊q=15，(n)=(p-1)(q-1)=8选取e=11（大于p和q的质数）；由d×11=1mod8，计算出d=3，得到公开密钥：（n，e）=（15，11）私有密钥：（n，d）=（15，3）假定明文M为整数13。则密文C=Memodn=1311mod15=(132)5*13mod15=(132mod15)5*13mod15=45*13mod15=7复原明文M为：M=Cdmodn=73mod15=343mod15=13§2.1RSA公钥密码算法描述第4讲公钥密码体制15举例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=1mod24362436=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≡1mod2436取e=13时，d=937§2.1RSA公钥密码算法描述13×d=k*2436+1d=(k*2436+1)/13,试凑第4讲公钥密码体制161、加密字串举例：若有明文publickeyencryptions2、先将明文分块为两个一组(此处为简化计算考虑)：publickeyencryptions3、将明文数字化令a,b…,z分别为00,01,…,25得15200111080210042404130217241519081413184、利用加密可得密文00951648141012991365137923332132175113245、解密后又得到明文§2.1RSA公钥密码算法描述第4讲公钥密码体制17C=Memodn=152013mod2537=(15202)6*1520mod2537∵15202＝1730mod2537∴C=(1730)6*1520mod2537=(17302)3*1520mod2537∵17302＝1777mod2537∴C=(1777)3*1520mod2537=(1777)2*1777*1520mod2537∵17772＝1701mod2537∴C=1701*(1777*1520)mod2537=1701*1672mod2537=95（密文）§2.1RSA公钥密码算法描述（2）加密第4讲公钥密码体制18M=Cdmodn=95937mod2537=(952)468*95mod2537=(1414)468*95mod2537=(14142)234*95mod2537=(240)234*95mod2537………=(625*25)*(341*788)*95mod2537=230*2323mod2537=1520mod2537=1520（明文）§2.1RSA公钥密码算法描述（3）解密第4讲公钥密码体制19§2.2RSA算法的优缺点优点：是第一个能同时用于加密和数字签名的算法，也易于理解和操作，也是被研究得最广泛的公钥算法，二十年来经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。特别符合计算机网络环境。对于网上的大量用户，可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信，只需从公钥簿上查出对方的加密密钥，用它对所传送的信息加密发出即可。对方收到信息后，用仅为自己所知的解密密钥将信息解密，了解报文的内容。第4讲公钥密码体制20缺点：（1）产生密钥很麻烦，难以做到一次一密。（2）RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。目前人们已能分解140多位十进制位的大素数，这就要求使用更长的密钥，速度更慢。而且目前人们正在积极寻找攻击RSA的方法。（3）速度太慢,RSA的分组长度太大。为了速度问题，目前人们广泛使用单、公钥密码结合使用的方法，优缺点互补：单钥密码加密速度快，用它来加密较长的文件，然后用RSA来给文件密钥加密，极好的解决了单钥密码的密钥分发问题。§2.2RSA算法的优缺点第4讲公钥密码体制21§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。第4讲公钥密码体制22RSA密码系统设计要求：（1）p、q必须选择强素数（2）p、q之差必须很大（3）p－1、q－1的最大公约数应尽量小（4）p、q选择应足够大（5）e不可以太小（6）e应选择使模(n)的阶最大§2.3RSA密码体制的实现第4讲公钥密码体制23美国斯坦福大学的Merkle和Hellman于1978年提出的。背包问题描述：已知一长度为b的背包及长度分别为a1,a2,…an的n个物品。假定这些物品的直径与背包相同，若从这些物品中选出若干个正好装满这个背包，究竟是哪些物品。数学描述：已知b，求解a1x1+a2x2+…+anxn=b，其中a1,a2,…an和b都是正整数。背包问题目前尚无有效求解算法。背包公钥密码：选取正整数a1,a2,…an作为公钥，明文位串为m=m1m2…mn，利用公钥加密问题c=a1m1+a2m2+…+anmn。从密文c求明文m等价于背包问题。§3背包公钥密码体制第4讲公钥密码体制24MH公钥背包密码：其背包系列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11ijjibb§3背包公钥密码体制第4讲公钥密码体制25MH公钥背包密码过程：（1）密钥生成用户构造长度为n的超递增背包分量b1,b2,…,bn，选择两个正整数M、W，其中，WM且保证gcd(W,M)=1。则由WW-1＝1modM，求出W-1（0W-1M)，计算ai=WbimodM，0in选择背包系统的公钥为Pk=(a1,a2,…,an)，私钥为Sk=(b1,b2,…,bn,M,W-1)§3背包公钥密码体制niibM1第4讲公钥密码体制26（2）加密过程用户A给用户B发送秘密消息时，使用B的公钥PK，对明文m=（m1,m2,…,mn）进行加密变换：（3）解密过程用户收到密文C后，使用自己的私钥SK，计算niiiPKammEC1)(niii