现代密码学第十章公约密码

现代密码学第十章：公钥加密1本章主要内容10.1.公钥加密简介10.2.定义

10.2.1选择明文攻击的安全性

10.2.2多重加密10.3.混合加密10.4.RSA加密

10.4.1“教科书式RSA”加密方案及其不安全性

10.4.2对“教科书式RSA”加密方案的攻击

10.4.3填充RSA10.5.ElGamal加密10.6选择密文攻击的安全性10.7*陷门置换

10.7.1定义

10.7.2来自陷门置换的公钥加密210.1公钥加密简介公钥加密的出现标志着密码学领域的一场革命。在此之前，密码学家们完全依靠共享的秘密密钥来实现秘密通信。两个人在一间屋子的两端，能通过大声喊叫与对方交流，虽然没有初始密钥，但屋子里没有人知道他们说什么。在对称密钥加密情况下，两方同意共享一个可同时用于（任何一方）加密和解密的秘密密钥K，公钥加密在这方面是非对称的。具体来说，一方（接收方）产生一对密钥（PK，SK），被分别称为公钥和私钥。发送方用公钥将消息加密，然后发送给对方。接收方就用私鈅将最终收到的密文进行解密。34公钥加密体制的原理邮箱的例子任何人可以向邮箱投举报信用户(审计人员)才能打开邮箱，读信的内容45公钥加密模型公钥加密体制的原理公钥PK本来就是公开的，而且，在上述两种情况都很容易被对方获得。5公钥加密与对称密钥加密的比较

前者假设了所有密钥的完全保密性，然后后者只要求了密钥对（PK，SK）一半的保密性。虽然这看似很小的区别，其实有着很大的不同：在对称密钥加密中，通信的双方必须能够共享密钥，并且不允许第三方获得此密钥；而在公钥环境中，一方可以再不损失安全的情况下通过公共信道将公钥传给第一方。对在一个房间里相互大声喊叫的各方来说，或者更现实点，在一个完全在公共网络（类似电话线或者互联网等）中通信的各方，公钥加密式唯一的选择。另外一个重要的区别在于：对称密钥加密方案加密和解密时使用的密钥是同一个，而公钥加密方案使用不同的密钥。因为这个原因，公钥加密方案有时候被称作非对称的。这个非对称在公钥情况中意味着发送方和接收方不能像私钥情况下互换身份：一个给定的公钥加密方案只允许单向通信（关键点：单方发起的加密迫使放松者和接受者之间存在区别）。另外，公钥加密方案可使多个发送者与单个接受者秘密通信，与之不同的是，依靠双方共享密钥的对称密钥加密只能让两方进行秘密通信。6对称密码和公钥密码比较（1）对称密码运行条件：1、加密和解密使用同一个密钥和一个算法。2、发送方和接收方必须共享密钥和算法。公钥密码运行条件：1、用同一个算法进行加密和解密，而密钥有一对，其中一个用于加密，另一个用于解密。2、发送方和接收方每个拥有一对相互匹配的密钥中的一个(不是同一个)。7对称密码和公钥密码比较（2）对称密码安全条件：1、密钥必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上密文的样本必须不足以确定密钥。公钥密码安全条件：1、两个密钥中的一个必须保密。2、如果不掌握其他信息，要想解密报文是不可能或者至少是不现实的。3、知道所用的算法加上一个密钥加上密文的样本必须不足以确定密钥。8公钥加密的优缺点优点最重要的优势是公钥加密（在某种程度上）解决了密钥分配问题。因为通信双方不需事先共享秘密密钥。公钥加密可以让双方秘密通信，甚至他们之间所有的通信都被监听。在一个接受者与U个发送者通信的情况下，接受者存储一个单独的私钥SK，比共享、存储以及管理U个不同的密钥要方便的多。事实上，当利用公钥加密时候，潜在发送方的数量和标识不需要再密钥产生时被知道。这就有了极大的灵活性，并且对于一个在线商家来说非常重要。缺点比对称密钥加密要慢至少2~3个数量级。9公钥的安全分配到目前为止，我们隐含地假定敌手是被动的。换言之，敌手仅仅偷听接受者和发送者的通信，但不主动干扰通信。如果敌手能够篡改诚实通信方全部的通信，并且该通信方没有共享密钥，则不能实现私密性。本章以及下一章对公钥加密的讨论，都简单地假设发送方有一个接受方公钥的合法拷贝。换言之，假设密钥已经安全分配，这个假设不是因为上面提到的主动攻击不值得关注，而是因为存在着其他阻止这些主动攻击的方案，并且很方便的将安全公钥加密的研究与安全密钥分配的研究分离开来。1010.2定义定义10.1公钥加密方案是如下一个概率多项式时间算法（Gen，Enc，Dec）的元组。（1）生成密钥算法Gen用安全参数作为输入，输出一对密钥（PK，SK）。把

PK称为公钥，把SK称为私钥。为了方便，假设PK和SK的各自长度至少为n，而且可有PK和SK确定。（2）加密算法Enc把公钥PK和来自某个明文空间的一个消息m作为输入。输出密文c，记为

（3）解密算法Dec把私钥SK和密文c作为书输入，输出一个消息m或一个定义为失败的特殊符号。不失一般性，假设Dec是确定的，记为m:=11满足例外的概率是可忽略的，概率的计算来源于由输出的（PK，SK）和Enc使用的任何随机性。

12根据语法的定义，与对称密钥加密的一个重要的区别是：密钥生成算法Gen现在输出两个密钥，而不是一个。公钥PK用来加密，同时私钥SK用来解密。重申之前的讨论，即假设PK广泛地被分发，任何人都可以加密给生成这个密钥的通信方的消息，但是SK必须由接收方保密来保证安全性。注意：这里允许可忽略的解密错误。1310.2.1选择明文攻击的安全性给定一个公钥加密方案II=（Gen，Enc，Dec），敌手A，进行下面的实验：14定义10.3如果对于所有概率多项式时间的敌手A存在可忽略函数negl,满足则公钥加密方案II=（Gen，Enc，Dec）在窃听者存在情况下具有不可区分加密。定义3.8如果对于所有概率多项式时间的敌手A，存在一个可忽略函数negl,使得：则公钥加密方案II=（Gen，Enc，Dec）在窃听者存在情况下具有不可区分加密。

这两者的主要区别是，10.3A给予公钥PK，并且允许A基于这个公钥选择它的消息m0,m1.15考虑下面定义公钥加密方案II=（Gen，Enc，Dec）和敌手A的实验：16如果对于所有概率多项式时间的敌手A存在可忽略函数negl,满足则公钥加密方案II=（Gen，Enc，Dec）在选择明文攻击下具有不可区分加密。总结上面的内容，由于A可以自己使用PK加密消息，所以加密预言机是不必要的。17命题10.5如果一个公钥加密方案II在窃听者存在情况下具有不可区分加密，则II在选择明文攻击戏啊也具有不可区分加密。这和对称密钥加密情形是不同的。在对称密钥加密方案中，窃听者存在情况下具有不可区分加密，在选择明文攻击时是不安全的。完美安全的公钥加密方案的不可能性。完美安全的公钥加密可以从窃听者的视角，类似于定义2.1一样定义（即包括公钥）。同样地，它可以通过扩展定义10.3来定义，即要求所有的敌手A满足18与对称密钥加密的情形相反，无论多长的密钥和多短的消息，完美安全的公钥加密式不可能的。确定性公钥的不安全性。正如对称密钥加密中提到的，任何一确定性的加密方案都不是CPA安全的。在公钥加密情形中有窃听者存在情况下，由于CPA安全和不可区分加密的等价性，可得出结论：定理10.6在窃听者存在情况下，没有一种确定性的公钥加密方案具有不可区分加密。1910.2.2多重加密

在窃听者存在的情况下，任何不不区分加密用来加密多重消息时都是安全的。这意味着，可以通过基于前一个定义来证明安全性，这种方法更加简单，同时，这种证明了安全性的方案也满足后一种定义，这种定义更加精确地建模了敌手的攻击。

20定义10.7如果对于所有的概率多项式时间的敌手A存在一个可忽略函数negl，满足则公钥加密方案II=（Gen，Enc，Dec）在窃听者存在的情况下具有不可区分的多重加密。

对于此定义下的两个声称10.8和10.9见课本P224定理10.10如果在窃听者存在情况下，公钥加密方案II是不可区分加密，则II在窃听者存在情况下是不可区分多重加密。21命题10.11令II和II’如上所述。如果II在窃听者存在的情况下是不可区分的加密，那么II’也是。当II在窃听者存在情况下是不可区分的加密时（而且，可扩展到II是CPA安全时），命题10.11是正确的，但是在选择明文攻击情况下，类似的结论是不正确的。术语说明。已经说明，在公钥加密情况下，任何在有窃听者存在情况下是不可区分的方案也是CPA安全的。这意味着一旦证明了某个方案对于前一个（相对较弱）的定义是安全的，那么将会直接获得关于后一个（更加现实）的定义的安全性。因此在讨论和定理陈述中，将倾向于“CPA安全”，但是在证明中，大多使用这一定义：

窃听者存在情况下的不不区分加密2210.３混合加密命题10.11表明：任何1比特消息的CPA安全的公钥加密方案可用来获得对于任意消息长度的CPA安全的加密方案。使用这种方法加密t比特的消息需要调用原始加密方案t次，意味着计算和密文长度都在原有基础上增加了t的倍数。对于充分长的消息，通过联合使用对称密钥加密和公钥加密，明显可以做得更好。因为对称密钥加密比公钥加密明显更高效，所以这样提高了效率。这种组合叫做“混合加密”，广泛应用在实际中。其基本思想是把加密分成两步。为了加密一个消息m，做如下步骤：23（1）发送方首先选择一个随机的对称密钥K，然后用接收方的公钥加密K，密文为C1。接收方能通过解密C1恢复出K，然后对于窃听者来说K是不可知的（因为公钥加密方案的安全性）。因此，这样就可以在发送方和接收方之间建立一个共享的密钥。（2）然后发送方使用对称密钥加密方案（Gen’，Enc’，Dec’）和刚刚共享的密钥K加密消息m。这个加密的结果叫密文C2，可以被接受者用K解密。24以上两步可以通过让发送方发送密文<C1,C2>来“一次性完成”。这里强调：尽管把对称密钥加密作为一个组成部分来使用，但是以上所构成的公钥加密方案实质上发送和接受双方事先没有共享任何秘密密钥。25

2610.4RSA加密RSA算法简介分组密码，安全性依赖于大数的因子分解。第一个较为完善的公钥算法。能够同时用于加密和数字签名，且易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，被普遍认为是目前最优秀的公钥算法之一。目前仍然无法从理论上证明它的保密性能究竟如何，因为目前人们并没有从理论上证明破译RSA的难度与大整数分解问题的难度等价。27对于方案的安全性，可以认为：计算私钥的困难性和分解由GenRSA输出的模一样困难。原因是：正如7.24节中简单提到的，给定N=pq和满足ed=1modɸ（N）的e，d，在多项式时间内可以计算出N的因子。注意，这个结果没有谈到是否能用其他的方式从密文中恢复出明文，也没有谈到加密方案本身是安全的。2810.4.1“教科书式RSA”加密方案及其不安全性尽管“教科书式RSA”对于在本章中建议的任何安全定义来说都是不安全的，但是如果RSA假设对于GenRSA（见定义7.46）是成立的，则有可能证明这个方案的一个非常弱的安全性。

RSA的实现问题。以RSA加密在实践方面的讨论结束本小节。这里的讨论不仅应用到教科书式RSA方案，也可应用于基于RSA假设的其它方案。e的选择。对于不同的e和采用不同的选择e的方法，RSA问题的困难性都没有表现出任何差异。一个常见的选择是取e=3，然后计算e次幂模N，因这个计算只需要两次乘法。29使用中国剩余定理接收方持有私钥，因此可因此分解N，能利用中国剩余定理来加速计算模N的d次根，这是解密时必须的。特别是由于接收方可以计算部分结果和303110.4.2对“教科书式RSA”加密方案的攻击小e攻击：指e很小时，若使用广播加密（即利用同一个e对同一个消息m加密再分发给多个人）下遭遇的攻击设e=3，攻击方法如下有三个成员的公钥e均为3，但他们彼此的n不同，记为n1，n2，n3c1≡m3(modn1)c2≡m3(modn2)c3≡m3(modn3)

因为n1,n2,n3一般是互素的（否则。。），因此由中国剩余定理可得：

C≡m3(modn1×n2×n3)

又因为m<n1,n2,n3；所以可得m3<n1×n2×n3，则m为C开三次方32共模攻击共模攻击：指通信系统中使用相同的n，且存在两个用户的公钥e1和e2是互素的，则可以由这两个用户对同一条明文的不同加密结果，恢复出原始明文攻击方法：设c1≡me1(modn)c2≡me2(modn)

攻击者知道e1,e2,n,c1,c2

根据中国剩余定理推论：存在s,t使t×e1+s×e2=1(注意是相等)

则c1t×c2s=m(modn)结论：不能用同一个n来生成密钥3310.4.3填充RSA“教科书式RSA”加密方案的不安全性，不仅有前两节中描述的各种各样的攻击，也有它不能满足定义10.13的安全性，意味着需要考虑基于RSA的其它加密方法。一个简单的想法是在加密之前随机填充消息。这种方法的一个通用范例鉴于构造方法10.18.这个构造方法是基于参数L来定义的，该参数决定了可加密消息的长度。34

定理10.19如果RSA问题与GenRSA相关是困难的，则构造方10.18，其中L(n)=O(logn),在选择明文攻击下具有不可区分加密。根据方案的描述，明显表示解密总能成功3510.5ELGamal加密ElGamal加密方案是另一个常见的加密方案，它的安全性是基于判定性Diffie-Hellman问题的困难性。36定理10.22如果DDH问题相对于g来