現(xiàn)代密碼學(xué)第十章公約密碼

現(xiàn)代密碼學(xué)第十章：公鑰加密1本章主要內(nèi)容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公鑰加密簡介公鑰加密的出現(xiàn)標(biāo)志著密碼學(xué)領(lǐng)域的一場革命。在此之前，密碼學(xué)家們完全依靠共享的秘密密鑰來實(shí)現(xiàn)秘密通信。兩個(gè)人在一間屋子的兩端，能通過大聲喊叫與對方交流，雖然沒有初始密鑰，但屋子里沒有人知道他們說什么。在對稱密鑰加密情況下，兩方同意共享一個(gè)可同時(shí)用于（任何一方）加密和解密的秘密密鑰K，公鑰加密在這方面是非對稱的。具體來說，一方（接收方）產(chǎn)生一對密鑰（PK，SK），被分別稱為公鑰和私鑰。發(fā)送方用公鑰將消息加密，然后發(fā)送給對方。接收方就用私鈅將最終收到的密文進(jìn)行解密。34公鑰加密體制的原理郵箱的例子任何人可以向郵箱投舉報(bào)信用戶(審計(jì)人員)才能打開郵箱，讀信的內(nèi)容45公鑰加密模型公鑰加密體制的原理公鑰PK本來就是公開的，而且，在上述兩種情況都很容易被對方獲得。5公鑰加密與對稱密鑰加密的比較

前者假設(shè)了所有密鑰的完全保密性，然后后者只要求了密鑰對（PK，SK）一半的保密性。雖然這看似很小的區(qū)別，其實(shí)有著很大的不同：在對稱密鑰加密中，通信的雙方必須能夠共享密鑰，并且不允許第三方獲得此密鑰；而在公鑰環(huán)境中，一方可以再不損失安全的情況下通過公共信道將公鑰傳給第一方。對在一個(gè)房間里相互大聲喊叫的各方來說，或者更現(xiàn)實(shí)點(diǎn)，在一個(gè)完全在公共網(wǎng)絡(luò)（類似電話線或者互聯(lián)網(wǎng)等）中通信的各方，公鑰加密式唯一的選擇。另外一個(gè)重要的區(qū)別在于：對稱密鑰加密方案加密和解密時(shí)使用的密鑰是同一個(gè)，而公鑰加密方案使用不同的密鑰。因?yàn)檫@個(gè)原因，公鑰加密方案有時(shí)候被稱作非對稱的。這個(gè)非對稱在公鑰情況中意味著發(fā)送方和接收方不能像私鑰情況下互換身份：一個(gè)給定的公鑰加密方案只允許單向通信（關(guān)鍵點(diǎn)：單方發(fā)起的加密迫使放松者和接受者之間存在區(qū)別）。另外，公鑰加密方案可使多個(gè)發(fā)送者與單個(gè)接受者秘密通信，與之不同的是，依靠雙方共享密鑰的對稱密鑰加密只能讓兩方進(jìn)行秘密通信。6對稱密碼和公鑰密碼比較（1）對稱密碼運(yùn)行條件：1、加密和解密使用同一個(gè)密鑰和一個(gè)算法。2、發(fā)送方和接收方必須共享密鑰和算法。公鑰密碼運(yùn)行條件：1、用同一個(gè)算法進(jìn)行加密和解密，而密鑰有一對，其中一個(gè)用于加密，另一個(gè)用于解密。2、發(fā)送方和接收方每個(gè)擁有一對相互匹配的密鑰中的一個(gè)(不是同一個(gè))。7對稱密碼和公鑰密碼比較（2）對稱密碼安全條件：1、密鑰必須保密。2、如果不掌握其他信息，要想解密報(bào)文是不可能或者至少是不現(xiàn)實(shí)的。3、知道所用的算法加上密文的樣本必須不足以確定密鑰。公鑰密碼安全條件：1、兩個(gè)密鑰中的一個(gè)必須保密。2、如果不掌握其他信息，要想解密報(bào)文是不可能或者至少是不現(xiàn)實(shí)的。3、知道所用的算法加上一個(gè)密鑰加上密文的樣本必須不足以確定密鑰。8公鑰加密的優(yōu)缺點(diǎn)優(yōu)點(diǎn)最重要的優(yōu)勢是公鑰加密（在某種程度上）解決了密鑰分配問題。因?yàn)橥ㄐ烹p方不需事先共享秘密密鑰。公鑰加密可以讓雙方秘密通信，甚至他們之間所有的通信都被監(jiān)聽。在一個(gè)接受者與U個(gè)發(fā)送者通信的情況下，接受者存儲(chǔ)一個(gè)單獨(dú)的私鑰SK，比共享、存儲(chǔ)以及管理U個(gè)不同的密鑰要方便的多。事實(shí)上，當(dāng)利用公鑰加密時(shí)候，潛在發(fā)送方的數(shù)量和標(biāo)識不需要再密鑰產(chǎn)生時(shí)被知道。這就有了極大的靈活性，并且對于一個(gè)在線商家來說非常重要。缺點(diǎn)比對稱密鑰加密要慢至少2~3個(gè)數(shù)量級。9公鑰的安全分配到目前為止，我們隱含地假定敵手是被動(dòng)的。換言之，敵手僅僅偷聽接受者和發(fā)送者的通信，但不主動(dòng)干擾通信。如果敵手能夠篡改誠實(shí)通信方全部的通信，并且該通信方?jīng)]有共享密鑰，則不能實(shí)現(xiàn)私密性。本章以及下一章對公鑰加密的討論，都簡單地假設(shè)發(fā)送方有一個(gè)接受方公鑰的合法拷貝。換言之，假設(shè)密鑰已經(jīng)安全分配，這個(gè)假設(shè)不是因?yàn)樯厦嫣岬降闹鲃?dòng)攻擊不值得關(guān)注，而是因?yàn)榇嬖谥渌柚惯@些主動(dòng)攻擊的方案，并且很方便的將安全公鑰加密的研究與安全密鑰分配的研究分離開來。1010.2定義定義10.1公鑰加密方案是如下一個(gè)概率多項(xiàng)式時(shí)間算法（Gen，Enc，Dec）的元組。（1）生成密鑰算法Gen用安全參數(shù)作為輸入，輸出一對密鑰（PK，SK）。把

PK稱為公鑰，把SK稱為私鑰。為了方便，假設(shè)PK和SK的各自長度至少為n，而且可有PK和SK確定。（2）加密算法Enc把公鑰PK和來自某個(gè)明文空間的一個(gè)消息m作為輸入。輸出密文c，記為

（3）解密算法Dec把私鑰SK和密文c作為書輸入，輸出一個(gè)消息m或一個(gè)定義為失敗的特殊符號。不失一般性，假設(shè)Dec是確定的，記為m:=11滿足例外的概率是可忽略的，概率的計(jì)算來源于由輸出的（PK，SK）和Enc使用的任何隨機(jī)性。

12根據(jù)語法的定義，與對稱密鑰加密的一個(gè)重要的區(qū)別是：密鑰生成算法Gen現(xiàn)在輸出兩個(gè)密鑰，而不是一個(gè)。公鑰PK用來加密，同時(shí)私鑰SK用來解密。重申之前的討論，即假設(shè)PK廣泛地被分發(fā)，任何人都可以加密給生成這個(gè)密鑰的通信方的消息，但是SK必須由接收方保密來保證安全性。注意：這里允許可忽略的解密錯(cuò)誤。1310.2.1選擇明文攻擊的安全性給定一個(gè)公鑰加密方案II=（Gen，Enc，Dec），敵手A，進(jìn)行下面的實(shí)驗(yàn)：14定義10.3如果對于所有概率多項(xiàng)式時(shí)間的敵手A存在可忽略函數(shù)negl,滿足則公鑰加密方案II=（Gen，Enc，Dec）在竊聽者存在情況下具有不可區(qū)分加密。定義3.8如果對于所有概率多項(xiàng)式時(shí)間的敵手A，存在一個(gè)可忽略函數(shù)negl,使得：則公鑰加密方案II=（Gen，Enc，Dec）在竊聽者存在情況下具有不可區(qū)分加密。

這兩者的主要區(qū)別是，10.3A給予公鑰PK，并且允許A基于這個(gè)公鑰選擇它的消息m0,m1.15考慮下面定義公鑰加密方案II=（Gen，Enc，Dec）和敵手A的實(shí)驗(yàn)：16如果對于所有概率多項(xiàng)式時(shí)間的敵手A存在可忽略函數(shù)negl,滿足則公鑰加密方案II=（Gen，Enc，Dec）在選擇明文攻擊下具有不可區(qū)分加密?？偨Y(jié)上面的內(nèi)容，由于A可以自己使用PK加密消息，所以加密預(yù)言機(jī)是不必要的。17命題10.5如果一個(gè)公鑰加密方案II在竊聽者存在情況下具有不可區(qū)分加密，則II在選擇明文攻擊戲啊也具有不可區(qū)分加密。這和對稱密鑰加密情形是不同的。在對稱密鑰加密方案中，竊聽者存在情況下具有不可區(qū)分加密，在選擇明文攻擊時(shí)是不安全的。完美安全的公鑰加密方案的不可能性。完美安全的公鑰加密可以從竊聽者的視角，類似于定義2.1一樣定義（即包括公鑰）。同樣地，它可以通過擴(kuò)展定義10.3來定義，即要求所有的敵手A滿足18與對稱密鑰加密的情形相反，無論多長的密鑰和多短的消息，完美安全的公鑰加密式不可能的。確定性公鑰的不安全性。正如對稱密鑰加密中提到的，任何一確定性的加密方案都不是CPA安全的。在公鑰加密情形中有竊聽者存在情況下，由于CPA安全和不可區(qū)分加密的等價(jià)性，可得出結(jié)論：定理10.6在竊聽者存在情況下，沒有一種確定性的公鑰加密方案具有不可區(qū)分加密。1910.2.2多重加密

在竊聽者存在的情況下，任何不不區(qū)分加密用來加密多重消息時(shí)都是安全的。這意味著，可以通過基于前一個(gè)定義來證明安全性，這種方法更加簡單，同時(shí)，這種證明了安全性的方案也滿足后一種定義，這種定義更加精確地建模了敵手的攻擊。

20定義10.7如果對于所有的概率多項(xiàng)式時(shí)間的敵手A存在一個(gè)可忽略函數(shù)negl，滿足則公鑰加密方案II=（Gen，Enc，Dec）在竊聽者存在的情況下具有不可區(qū)分的多重加密。

對于此定義下的兩個(gè)聲稱10.8和10.9見課本P224定理10.10如果在竊聽者存在情況下，公鑰加密方案II是不可區(qū)分加密，則II在竊聽者存在情況下是不可區(qū)分多重加密。21命題10.11令I(lǐng)I和II’如上所述。如果II在竊聽者存在的情況下是不可區(qū)分的加密，那么II’也是。當(dāng)II在竊聽者存在情況下是不可區(qū)分的加密時(shí)（而且，可擴(kuò)展到II是CPA安全時(shí)），命題10.11是正確的，但是在選擇明文攻擊情況下，類似的結(jié)論是不正確的。術(shù)語說明。已經(jīng)說明，在公鑰加密情況下，任何在有竊聽者存在情況下是不可區(qū)分的方案也是CPA安全的。這意味著一旦證明了某個(gè)方案對于前一個(gè)（相對較弱）的定義是安全的，那么將會(huì)直接獲得關(guān)于后一個(gè)（更加現(xiàn)實(shí)）的定義的安全性。因此在討論和定理陳述中，將傾向于“CPA安全”，但是在證明中，大多使用這一定義：

竊聽者存在情況下的不不區(qū)分加密2210.３混合加密命題10.11表明：任何1比特消息的CPA安全的公鑰加密方案可用來獲得對于任意消息長度的CPA安全的加密方案。使用這種方法加密t比特的消息需要調(diào)用原始加密方案t次，意味著計(jì)算和密文長度都在原有基礎(chǔ)上增加了t的倍數(shù)。對于充分長的消息，通過聯(lián)合使用對稱密鑰加密和公鑰加密，明顯可以做得更好。因?yàn)閷ΨQ密鑰加密比公鑰加密明顯更高效，所以這樣提高了效率。這種組合叫做“混合加密”，廣泛應(yīng)用在實(shí)際中。其基本思想是把加密分成兩步。為了加密一個(gè)消息m，做如下步驟：23（1）發(fā)送方首先選擇一個(gè)隨機(jī)的對稱密鑰K，然后用接收方的公鑰加密K，密文為C1。接收方能通過解密C1恢復(fù)出K，然后對于竊聽者來說K是不可知的（因?yàn)楣€加密方案的安全性）。因此，這樣就可以在發(fā)送方和接收方之間建立一個(gè)共享的密鑰。（2）然后發(fā)送方使用對稱密鑰加密方案（Gen’，Enc’，Dec’）和剛剛共享的密鑰K加密消息m。這個(gè)加密的結(jié)果叫密文C2，可以被接受者用K解密。24以上兩步可以通過讓發(fā)送方發(fā)送密文<C1,C2>來“一次性完成”。這里強(qiáng)調(diào)：盡管把對稱密鑰加密作為一個(gè)組成部分來使用，但是以上所構(gòu)成的公鑰加密方案實(shí)質(zhì)上發(fā)送和接受雙方事先沒有共享任何秘密密鑰。25

2610.4RSA加密RSA算法簡介分組密碼，安全性依賴于大數(shù)的因子分解。第一個(gè)較為完善的公鑰算法。能夠同時(shí)用于加密和數(shù)字簽名，且易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，被普遍認(rèn)為是目前最優(yōu)秀的公鑰算法之一。目前仍然無法從理論上證明它的保密性能究竟如何，因?yàn)槟壳叭藗儾]有從理論上證明破譯RSA的難度與大整數(shù)分解問題的難度等價(jià)。27對于方案的安全性，可以認(rèn)為：計(jì)算私鑰的困難性和分解由GenRSA輸出的模一樣困難。原因是：正如7.24節(jié)中簡單提到的，給定N=pq和滿足ed=1mod?（N）的e，d，在多項(xiàng)式時(shí)間內(nèi)可以計(jì)算出N的因子。注意，這個(gè)結(jié)果沒有談到是否能用其他的方式從密文中恢復(fù)出明文，也沒有談到加密方案本身是安全的。2810.4.1“教科書式RSA”加密方案及其不安全性盡管“教科書式RSA”對于在本章中建議的任何安全定義來說都是不安全的，但是如果RSA假設(shè)對于GenRSA（見定義7.46）是成立的，則有可能證明這個(gè)方案的一個(gè)非常弱的安全性。

RSA的實(shí)現(xiàn)問題。以RSA加密在實(shí)踐方面的討論結(jié)束本小節(jié)。這里的討論不僅應(yīng)用到教科書式RSA方案，也可應(yīng)用于基于RSA假設(shè)的其它方案。e的選擇。對于不同的e和采用不同的選擇e的方法，RSA問題的困難性都沒有表現(xiàn)出任何差異。一個(gè)常見的選擇是取e=3，然后計(jì)算e次冪模N，因這個(gè)計(jì)算只需要兩次乘法。29使用中國剩余定理接收方持有私鑰，因此可因此分解N，能利用中國剩余定理來加速計(jì)算模N的d次根，這是解密時(shí)必須的。特別是由于接收方可以計(jì)算部分結(jié)果和303110.4.2對“教科書式RSA”加密方案的攻擊小e攻擊：指e很小時(shí)，若使用廣播加密（即利用同一個(gè)e對同一個(gè)消息m加密再分發(fā)給多個(gè)人）下遭遇的攻擊設(shè)e=3，攻擊方法如下有三個(gè)成員的公鑰e均為3，但他們彼此的n不同，記為n1，n2，n3c1≡m3(modn1)c2≡m3(modn2)c3≡m3(modn3)

因?yàn)閚1,n2,n3一般是互素的（否則。。），因此由中國剩余定理可得：

C≡m3(modn1×n2×n3)

又因?yàn)閙<n1,n2,n3；所以可得m3<n1×n2×n3，則m為C開三次方32共模攻擊共模攻擊：指通信系統(tǒng)中使用相同的n，且存在兩個(gè)用戶的公鑰e1和e2是互素的，則可以由這兩個(gè)用戶對同一條明文的不同加密結(jié)果，恢復(fù)出原始明文攻擊方法：設(shè)c1≡me1(modn)c2≡me2(modn)

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

根據(jù)中國剩余定理推論：存在s,t使t×e1+s×e2=1(注意是相等)

則c1t×c2s=m(modn)結(jié)論：不能用同一個(gè)n來生成密鑰3310.4.3填充RSA“教科書式RSA”加密方案的不安全性，不僅有前兩節(jié)中描述的各種各樣的攻擊，也有它不能滿足定義10.13的安全性，意味著需要考慮基于RSA的其它加密方法。一個(gè)簡單的想法是在加密之前隨機(jī)填充消息。這種方法的一個(gè)通用范例鑒于構(gòu)造方法10.18.這個(gè)構(gòu)造方法是基于參數(shù)L來定義的，該參數(shù)決定了可加密消息的長度。34

定理10.19如果RSA問題與GenRSA相關(guān)是困難的，則構(gòu)造方10.18，其中L(n)=O(logn),在選擇明文攻擊下具有不可區(qū)分加密。根據(jù)方案的描述，明顯表示解密總能成功3510.5ELGamal加密ElGamal加密方案是另一個(gè)常見的加密方案，它的安全性是基于判定性Diffie-Hellman問題的困難性。36定理10.22如果DDH問題相對于g來