03-公钥密码体系

南京邮电大学第3讲公钥密码体制王志伟计算机学院信息安全系[e-mail]2020/1/29南京邮电大学2本讲内容公钥密码体制的设计原理1Diffie-Hellman密钥交换2RSA（椭圆曲线密码体制）3公钥密码体制的应用42020/1/29南京邮电大学31公钥密码体制公钥密码体制的引入公钥密码体制数学基础在对称密码体制中，消息的发送方和接收方必须在密文传输之前通过安全信道进行密钥传输。而实际的传输信道安全性并不理想，所以密钥在传输过程中被暴露的风险很大。公钥密码的最大优点在于针对密钥管理方法的改进。在公钥密码系统中，加密密钥是公开的，任何人都可以采用这些公开的加密密钥对消息进行加密。同时只有正确的接收方才能够用自己所保管的解密密钥对密文进行解密。这些解密密钥需要妥善保存。提供单向函数的数学难题（NP完全问题-Non-deterministicPolynomialCOMPLETE问题）。对于一个函数f(x),如果对于其定义域上的任意x，f(x)都容易计算，同时，对于其值域中几乎所有的取值y，计算其逆函数f-1(y)都是不可行的。大整数分解问题离散对数问题椭圆曲线离散对数问题2020/1/29南京邮电大学41公钥密码体制明文私钥d公钥e明文密文加密器Ek解密器Dk2020/1/29南京邮电大学51公钥密码体制公钥密码体制的应用领域--消息的机密性--密钥分配利用通信双方已有的公钥、私钥对计算出一个公有的密钥，用于通信加密。Diffie-Hellman--认证——消息的来源和消息的完整性参见课本P96页图7.1参见课本P96页图7.2双重加解密同时实现认证和机密性，具体参见课本P97页图7.32020/1/29南京邮电大学61.1公钥算法Diffie-Hellman密钥分配协议第一个公开发表的公钥密码算法只用于密钥分配并不能完成信息加解密RSA是目前为止最为成功的非对称密码算法第一个比较完善的公钥系统Rivest,ShamirandAdleman2020/1/29南京邮电大学7本讲内容公钥密码体制的设计原理1Diffie-Hellman密钥交换2RSA（椭圆曲线密码体制）3公钥密码体制的应用42020/1/29南京邮电大学82Diffie-HellmanDiffie-Hellman是一个简单的公钥算法，用于实现密钥交换。这个协议是的通信的双方利用基于离散对数问题的公钥算法建立秘密钥。这个协议是安全的，仅当通信双方的真实性能够得到保证。2020/1/29南京邮电大学92Diffie-Hellman公开:g和n秘密:Alice的指数a,Bob的指数bAlice,aBob,bgamodngbmodnAlice计算(gb)a=gba=gabmodnBob计算(ga)b=gabmodn他们可以使用K=gabmodn做为对称密钥2020/1/29南京邮电大学102.1举例选定n=97,g=5Alice选择自己的私有密钥a=36,则她的公钥是X＝536mod97＝50Bob选择自己的私有密钥b=58,则他的公钥是Y＝558mod97=44用户Alice和Bob互换公钥后，都可以计算出Alice方：k=Yamod97=4436mod97=75Bob方：k=Xbmod97=5058mod97=752020/1/29南京邮电大学11本讲内容公钥密码体制的设计原理1Diffie-Hellman密钥交换2RSA（椭圆曲线密码体制）3公钥密码体制的应用42020/1/29南京邮电大学123RSA密码体制安全性是建立在“大数分解和素性检测”这个数论难题的基础上。既将两个大素数相乘在计算上容易实现，而将该乘积分解的计算量相当大虽然安全性没有能得到理论证明，但20多年的实践证明其是安全的2020/1/29南京邮电大学133.1RSA算法的密钥选取两个大素数p与q，然后算出n=pq，φ(n)=(p-1)(q-1)，再选取一个正整数e，使之满足(e，φ(n))=1，1eφ(n)，其中()表示求最大公约数；再求出正整数d，使之满足1dφ(n)，且使d×e≡1modφ(n)。然后用{n，e}作为公钥，{n，d}作为私钥2020/1/29南京邮电大学143.2RSA算法的加解密加密C=Memodn解密M=Cdmodn2020/1/29南京邮电大学153.3举例选取两个“大”素数p＝11，q＝3n＝p×q＝33φ(n)=(p-1)(q-1)＝20选择e＝3，因为3与20互质再求出正整数d，使之满足1dφ(n)，且使d×3≡1mod20所以d＝7公钥（n，e）＝（33，3）私钥（n，d）＝（33，7）2020/1/29南京邮电大学163.3举例公钥（n，e）＝（33，3）私钥（n，d）＝（33，7）假设明文是M＝8密文是C=Memodn=83=512=17mod33明文是M=Cdmodn=177=410,338,673=12,434,50533+8=8mod332020/1/29南京邮电大学173.4文本加密令26个字母对应0-25设明文为M＝publicE(p)=153=9mod33E(u)=203=14mod33E(b)=13=1mod33E(l)=113=11mod33E(i)=83=17mod33E(c)=23=8mod33则c＝E（M）＝091401111728＝joblri2020/1/29南京邮电大学183.5文本解密收到密文后用d=7进行解密D(j)=097=15mod33,即明文pD(o)=147=20mod33,即明文uD(b)=017=1mod33,即明文bD(l)=117=11mod33,即明文lD(r)=177=8mod33,即明文iD(i)=087=2mod33,即明文c2020/1/29南京邮电大学19RSA算法中的计算问题求一个整数的整数次幂如果按其含义直接计算，则中间结果运算量非常大如何提高加、解密运算中指数运算的有效性？利用模运算的性质重复对每个部分结果做平方参见课本P99-100页不作要求2020/1/29南京邮电大学20RSA讨论RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何，而且密码学界多数人士倾向于因子分解不是NPC问题。2020/1/29南京邮电大学21RSA算法分析R.L.Rivest等人证明：攻破RSA加密算法的计算复杂度等同于分解大数n的计算复杂度。1994年,一个小组利用因特网上1600台计算机,经过8个月的计算,攻破了公钥长度为129位十进制数(约428比特)的RSA(这种攻击意义不大).现在通常认为,采用1024比特密钥长度(约300位十进制数)是比较安全的.2020/1/29南京邮电大学22RSA缺点A)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。B)分组长度太大，为保证安全性，n至少也要600bits以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(SecureElectronicTransaction)协议中要求CA采用2048比特长的密钥，其他实体使用1024比特的密钥。椭圆曲线算法DES密钥长度(bit)RSA密钥长度(bit)563846451211217921282304DES和RSA性能比较(同等强度）3.6椭圆曲线算法2020/1/29南京邮电大学241985年，N.Koblitz和V.Miller分别独立提出了椭圆曲线密码体制(ECC)，其依据就是定义在椭圆曲线点群上的离散对数问题得难解性。椭圆曲线算法可以用来开发许多椭圆曲线密码方案，包括密钥交换、加密和数字签名。ECC密钥长度mRSA密钥长度MIPS-年1601024101232051201036600210001078120012000010168ECC和RSA性能比较与同等安全性的RSA相比，由于ECC使用的密钥更短，计算速度更快。2020/1/29南京邮电大学26本讲内容公钥密码体制的设计原理1Diffie-Hellman密钥交换2RSA（椭圆曲线密码体制）3公钥密码体制的应用42020/1/29南京邮电大学27公钥与以前的密码学不同之处传统的密码基于混淆和发散，使用替换和置换技术公钥基于数学函数的求解复杂度非对称的两个密钥应用范围更广，消息的保密性、密钥的分配和认证领域2020/1/29南京邮电大学28公钥vs私钥公钥体制大大简化了复杂的密钥分配管理问题公钥要比私钥慢得多慢约1000倍公钥用于认证（数字签名、身份识别等）和密钥管理私钥用于信息加密2020/1/29南京邮电大学29对于公钥的误解一公钥密码比传统密码更安全？不是！任何加密方法安全性依赖于密钥的长度和破译密文所需要的计算量。2020/1/29南京邮电大学30对于公钥的误解二公钥是一种通用的方法，传统密码已经过时？不是！公钥的计算量大，目前不能取代传统密码“公钥密码学仅限于用在密钥管理和签名此类应用上，这几乎是被广泛接受的事实”2020/1/29南京邮电大学31对于公钥的误解三传统密码中与密钥分配中心KDC的握手是一件麻烦的事情公钥的密钥管理非常简单？不！也需要某种形式的协议，该协议一般包含一个中心代理，处理并不比传统密码中的那些工程更简单2020/1/29南京邮电大学32公钥算法应用：加密2020/1/29南京邮电大学33用公钥密码实现保密用户拥有自己的密钥对(KU,KR)公钥KU公开,私钥KR保密A:Y=EKUb(X)B:DKRb(Y)=DKRb(EKUb(X))=X2020/1/29南京邮电大学34公钥算法应用：认证2020/1/29南京邮电大学35用公钥密码实现鉴别条件:两个密钥中任何一个都可以用作加密而另一个用作解密鉴别:A－ALL:Y=EKRa(X)ALL:DKUa(Y)=DKUa(EKRa(X))=X鉴别+保密:A－B:Z=EKUb(EKRa(X))B:DKUa(DKRb(Z))=X南京邮电大学[e-mail]