5..公钥密码学

2020/1/251信息安全导论第五讲公钥密码学华中科技大学图象所信息安全研究室2020/1/252公钥密码体制RSA公钥密码体制EIGamal密码体制椭圆曲线密码学2020/1/253对称密钥（私钥）密码体制中的分组密码和流密码，它们的一个共同点是加密密钥与相应的解密密钥相同（或者由加密密钥容易推导得到与之相对应的解密密钥）。对称密码系统中，消息的发送方和接收方必须在密文传输之前通过安全信道进行密钥传输。实际的传输信道安全性并不理想，密钥在传输过程中被暴露的风险很大，增加了系统的脆弱性。2020/1/254对称密码体制的缺陷密钥分配问题:通信双方要进行加密通信，需要通过秘密的安全信道协商加密密钥，而这种安全信道可能很难实现；密钥管理问题:在有多个用户的网络中，任何两个用户之间都需要有共享的加密密钥，当网络中的用户n很大时，需要管理的密钥数目是非常大。没有签名功能:当主体A收到主体B的电子文挡(电子数据)时，无法向第三方证明此电子文档确实来源于B。2020/1/255公钥密码体制概述2020/1/256公钥密码体制概述公钥密码体制是密码学研究的一个具有里程碑意义的重要事件。公钥密码技术又称为双钥密码或非对称密码技术。1976年由Diffie和Hellman在其密码学新方向一文中首次提出公钥密码思想，对密码学的发展起到了极其重要的促进作用。见划时代的文献：W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-6542020/1/2571978年，RSA算法作为第一个比较完善的公钥密码算法面世。算法的取名采用其创始者Rivest,Shamir和Adleman名字的首字母，以纪念三位学者对密码学的杰出贡献。公钥密码技术研究的基本工具不再象对称密码技术那样是代换和置换，而是数学函数。2020/1/258基本思想和要求公钥密码的基本思想是将传统密码的密钥一分为二，分为加密密钥和解密密钥，而且由计算复杂性确保由加密密钥在计算上推导出相对应的解密密钥不具有可实现性。这样，即使是将加密密钥公开也不会暴露解密密钥，不会损害密码的安全。于是，可将加密密钥公开（即公钥），而只对解密密钥保密（即私钥）。2020/1/259涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换2020/1/2510至此，密码体制解脱了必须对密钥进行安全传输的束缚，使密码学的应用前景豁然明朗。它的主要特点是将加密和解密能力分开，因而可以实现多个用户加密的信息只能由一个用户解读，或由一个用户加密的信息而多个用户可以解读。前者可以用于公共网络中实现通信保密，而后者可以用于实现对用户的认证。2020/1/2511公钥密码的最大优点同时也是最重要的创新之处在于针对密钥管理方法的改进。加密密钥是公开的，任何人都可以采用这些公开的加密密钥对自己准备传输的消息进行加密。同时，只有正确的接收方才能用自己所保管的解密密钥对密文进行解密。解密密钥需要妥善保存。与对称密钥密码体制相比，公钥体制的密钥在处理和发送上更为方便而且安全。2020/1/2512在当今具有用户量大、消息发送方与接收方存在明显的信息不对称特点的应用环境中，公钥密码系统表现出了令人乐观的前景。2020/1/2513公钥密码体制的安全性计算上的安全性安全性的理论基础：复杂性理论问题是需要回答的一般性提问，通常含有若干个未定参数或自由变量。问题的描述包括给定所有的未定参数的一般性描述陈述“答案”或“解”必须满足的性质算法是求解某个问题的一系列具体步骤，通常可理解为求解某个问题的通用计算机程序。一个算法的复杂性由该算法所需求的最大时间（T）和存储空间（S）度量。由于算法用于同一问题的不同规模实例所需求的时间和空间往往不同，所以总是将他们表示成问题实例的规模n的函数，n表示描述该实例所需的输入数据长度。2020/1/2514算法复杂性算法复杂性用“大O”的符号来表示，它表示算法复杂性的数量级。f(n)=O(g(n))意味着存在常数c和n0，使得对一切n≥n0,有f(n)≤c|g(n)|。通常按时间（或空间）复杂性对算法进行分类。一个输入的大小为n的算法被称为是：线性的：如果运行时间是O(n)多项式的：如果运行时间是O(nt),其中t是一个常数指数的：如果运行时间是O(th(n)),其中t是一个常数,h(n)是一个多项式一般地，一个可以在多项式时间内解决的问题被认为是可解的，而任何比多项式时间更长的时间，尤其是指数时间，被认为是不可解的。2020/1/2515问题复杂性理论利用算法复杂性理论作为工具，将大量典型的问题按求解代价进行分类。图灵机是一种具有无限读写能力的有限状态机，并且可以做无限的并行操作。图灵机分为确定型和非确定型两种。确定型是指图灵机的每一步操作的结果是唯一确定的。所谓非确定型图灵机的每一步操作结果及下一步操作都有多种选择，不是唯一确定的。一个问题的复杂性由在图灵机上解此问题的最难实例所需要的最小时间与空间决定。即解此问题的最有效的算法所需的时间与空间来度量。2020/1/2516在确定型图灵机上可用多项式时间求解的问题，称为易处理问题。易处理问题的全体称为确定性多项式时间可解类，记为P。在非确定型图灵机上可用多项式时间求解的问题，称为非确定性多项式时间可解问题，简称NP问题。NP问题的全体称为非确定性多项式时间可解类，记为NP。求解分为猜测和验证阶段。NP完全问题，即多项式复杂程度的非确定性问题。简单的写法是NP=P？，问题就在这个问号上，到底是NP等于P，还是NP不等于P，还没有人证明:P=NP？，是世界七大数学难题之一。2020/1/2517公钥密码算法公钥密码算法是公钥密码体制的核心。这些算法基于不同的计算问题，但在理论上都保证了由加密密钥得到解密密钥是不可行的。当然，公钥密码体制的这种安全性理论基础只是基于复杂性理论的一种计算安全性，非绝对的安全性。实际上，在密码学中，绝对的安全一般是不存在的。2020/1/2518由于利用目前现有的技术无法在多项式时间里对NP完全问题进行求解，公钥密码思想的首创者Diffie和Hellmen在其研究中指出：计算复杂性可以被用作设计加密算法的基础，而NP完全问题则是一个理想的解决途径。Diffie和Hellman曾推测，密码学可以汲取NP复杂性问题，通过检验找出NP完全问题中可用于密码的问题。2020/1/2519信息可通过编码被加密在一个NP完全问题之中，使得要破译这种密码以普通的方法就要解这个NP完全问题。但若使用解密密码，就可能有捷径求解。为构造这样的密码，秘密的‘陷门’信息必须被嵌在一个涉及单向函数求逆的计算困难问题中。单向函数是公钥密码体制的一个重要概念。2020/1/2520单向陷门函数是满足下列条件的函数f：计算y=f(x)是容易的；给定y,计算x使y=f(x)是困难的；所谓计算x=f-1(Y)困难是指计算上相当复杂，已无实际意义。存在δ，已知δ时,对给定的任何y，若相应的x存在，则计算x使y=f(x)是容易的。2020/1/2521注：1.仅满足(1)、(2)两条的称为单向函数；第(3)条称为陷门性，δ称为陷门信息。2.当用陷门函数f作为加密函数时，可将f公开，这相当于公开加密密钥。此时加密密钥便称为公开钥，记为Pk。f函数的设计者将δ保密，用作解密密钥，此时δ称为秘密钥匙，记为Sk。由于加密函数是公开的，任何人都可以将信息x加密成y=f(x)，然后送给函数的设计者（当然可以通过不安全信道传送）；由于设计者拥有Sk，他自然可以解出x=f-1(y)。3.单向陷门函数的第(2)条性质表明窃听者由截获的密文y=f(x)推测x是不可行的。2020/1/2522基于公开密钥的加密过程2020/1/2523基于公开密钥的鉴别过程2020/1/2524用公钥密码实现保密用户B拥有自己的密钥对(eB,dB)公钥eB公开,私钥dB保密A－B:Y=EeB(X)（公钥加密）B:DdB(Y)=DdB(EeB(X))=X（私钥解密）2020/1/2525用公钥密码实现鉴别条件:两个密钥中任何一个都可以用作加密而另一个用作解密鉴别:A－ALL:Y=EdA(X)（A用私钥签名）ALL:EeA(Y)=DeA(EdA(X))=X（用A的公钥鉴别）鉴别+保密:A－B:Z=EeB(EdA(X))B:DeA(DdB(Z))=X2020/1/2526公钥密钥的应用范围加密/解密数字签名(身份鉴别)密钥交换2020/1/2527下图是公钥密码技术示意图：公钥密码的加密变换E(eB,m)与解密交换D(dB,c)应满足：D(dB,c)是E(eB,m)的逆变换，即对任何的明文m有：D(dB,c)=D(dB,E(eB,m))=m；在已知加密密钥eB时，E(eB,m)的计算不难；在已知解密密钥dB时，D(dB,c)的计算也不难；若不知道dB，那么即使知道eB，具体的加密与解密算法过程及密文c，确定明文的计算是不可行的。设计公开密钥密码体制就变成了寻找陷门单向函数。可提供单向函数的数学难题是：整数分解问题（简称IFP）；离散对数问题（简称DLP）；椭圆曲线离散对数问题（简称ECDLP,也时被归为离散对数问题类）。2020/1/2528构造公钥密码系统的关键是如何在求解某个单向函数的逆函数的NP完全问题中设置合理的“后门”。并非所有的困难问题都可以用于设计公钥密码系统。通过检验，人们已经找到若干可用于密码的这类问题，如大整数分解问题和背包问题、离散对数问题等。某些被用于设计公钥密码系统的这类问题在计算上的难易程度也不完全代表该密码系统的强弱程度。2020/1/2529原因是一方面，对于这类问题的计算复杂性进行度量通常依据的是其在最坏或者平均情况下的特性，而密码系统则要求对于该问题的求解在几乎所有的情况下都无法进行；另一方面，计算复杂性问题通常考虑的是某种孤立的情形，而密码学中所考虑的问题基本上都具有大量的统计相关性。2020/1/2530目前，许多函数被认为是单向函数，然而，还没有通过严格的证明得到某个函数的确为单向函数这一结论。2020/1/2531•基于大整数分解问题的公钥密码体制•基于有限域中的离散对数问题公钥密码算法•基于代数编码系统的公钥密码算法•基于有限自动机的公开密码技术•基于椭圆曲线的公开密钥密码技术除椭圆曲线公钥密码算法是在椭圆曲线上进行运算之外，其余各公钥密码算法均在有限域上进行。人们已经研究出的公钥密码算法：2020/1/2532注：1.从另一个角度考虑，由于令人满意的加密与解密过程都必须尽可能的迅速，所以更难的问题并不适合用于设计加密算法。2.因此，这种计算安全性也给密码分析者提供了破解公钥加密算法的可能性，使密码分析人员能够通过在多项式时间内猜测并检验某个密钥的方法完成破译工作。2020/1/2533RSA公钥密码体制2020/1/25342020/1/2535RSA公钥算法RSA公钥算法是第一个比较完善、应用最广泛的公钥密码算法。1977由麻省理工学院的Rivest、以色列魏茨曼科学中心的Shamir和南加洲大学的Adleman发明，1978年发表了著名的论文“AMethodforObtainingDigitalSignatureandPublic-KeyCryptosystems（获得数字签名和公开密钥密码系统的一种方法）”。是一种分组加密算法。明文和密文在0~n-1之间,n是一个正整数只在美国申请专利，且已于2000年9月到期2020/1/2536该算法的数学基础是初等数论中的Euler(欧拉)定理，并建立在大整数因子分解的困难性之上，目前