不可區(qū)分性在公約密碼學(xué)中的應(yīng)用介紹

1、不可區(qū)分性在公鑰密碼學(xué)中的應(yīng)用摘要：本文主要總結(jié)了不可區(qū)分性在公鑰密碼體制中的運(yùn)用，這些運(yùn)用主要包括如何刻畫密碼體制的安全性（語義安全性）、如何通過規(guī)約的方式利用不可區(qū)分實(shí)驗(yàn)證明密碼體制的安全性、以及一些常見的密碼體制中不可區(qū)分性的作用。全文主要分為三個(gè)部分，第一部分主要介紹了一些基礎(chǔ)知識(shí)，包括密碼體制的組成以及完善保密密碼體制的含義，如何利用不可區(qū)分性來等價(jià)描述完善保密密碼體制。第二部分主要介紹了不可區(qū)分實(shí)驗(yàn)（游戲）在公鑰密碼學(xué)中的應(yīng)用。這一部分先對(duì)攻擊者的層次進(jìn)行了劃分，之后介紹了如何用不可區(qū)分實(shí)驗(yàn)來給最基本的密碼體制的語義安全性下定義。這一部分最后利用CCA2的語義安全性作為例子說明如何

2、利用不可區(qū)分實(shí)驗(yàn)定義擁有特定防御功能的公鑰密碼體制的語義安全性。第三部分介紹了規(guī)約證明的相關(guān)內(nèi)容，規(guī)約證明現(xiàn)如今已成為現(xiàn)代公鑰密碼學(xué)可證明安全理論常用的證明方法，而兩個(gè)問題規(guī)約的過程中與不可區(qū)分性密不可分。第四部分主要舉了一個(gè)例子來說明不可區(qū)分性在證明密碼體制安全性中的應(yīng)用。本文對(duì)公鑰密碼學(xué)中的不可區(qū)分性理論做了比較簡(jiǎn)單的總結(jié)和歸納，不可區(qū)分性在公鑰密碼學(xué)可證明安全理論中有著十分重要的地位，本文對(duì)剛剛接觸不可區(qū)分性的學(xué)者有著一定的幫助。 第一部分：基礎(chǔ)知識(shí)及不可區(qū)分性的定義 這一部分內(nèi)容主要介紹一下有關(guān)于不可區(qū)分性的基礎(chǔ)知識(shí)，包括密碼體制的組成、完善保密密碼體制、完美不可區(qū)分性的含義以及敵手不

3、可區(qū)分性的含義。首先先給出密碼體制的定義：定義1.1 密碼體制一個(gè)密碼體制由三個(gè)部分構(gòu)成：密鑰產(chǎn)生算法Gen、加密算法Enc、解密算法Dec。他們的功能如下：（1）密鑰產(chǎn)生算法Gen是一個(gè)概率算法，能夠根據(jù)方案定義的某種分布選擇并輸出一個(gè)密鑰. （2）加密算法Enc，輸入為密鑰和明文，輸出為密文。把使用密鑰加密明文記為Enc(). （3）解密算法Dec，輸入為密鑰和密文，輸出為明文。把使用密鑰解密密文記為Dec(). 對(duì)任意的密碼體制的基本要求是：對(duì)任意通過Gen輸出的密鑰，每個(gè)明文消息都滿足Dec(Enc() 密鑰生成函數(shù)Gen輸出的所有可能的密鑰稱為密鑰空間，用表示。所有明文消息的集合稱為

4、明文空間，記作。集合和一起定義了所有可能的密文的集合，稱為密文空間。上述密碼體制可記為明文空間為的密碼體制(Gen,Enc,Dec). 如何刻畫一個(gè)密碼體制的安全性，完善保密密碼體制是所有密碼體制中最理想的情況：定義1.2 完善保密密碼體制 明文空間為的密碼體制(Gen,Enc,Dec)是完善保密密碼體制，如果對(duì)于上任意的概率分布，任何明文，任何密文且，都有下面給出完美不可區(qū)分性對(duì)于完善保密密碼體制的等價(jià)刻畫。記為加密時(shí)的密文概率分布。定義1.3 完美不可區(qū)分性 的概率分布獨(dú)立于明文。也就是說，對(duì)于任意的，和的分布是相同的。由此，可以得到一下結(jié)論：定理1.1 明文空間為的密碼體制(Gen,En

5、c,Dec)是完善保密密碼體制當(dāng)且僅當(dāng)對(duì)于任意上的概率分布，以及，都有證明：必要性顯然。下證充分性：記由條件可知，對(duì)于任意的，都有，于是由于的任意性，故對(duì)任意的，即該密碼體制是完善的。 以上使用完美不可區(qū)分性給出了完善保密密碼體制的等價(jià)條件。而在現(xiàn)代公鑰密碼學(xué)領(lǐng)域更多研究的則是稱之為“敵手不可區(qū)分性”與密碼體制安全性的內(nèi)在聯(lián)系。在第二部分將給出敵手不可區(qū)分性的相關(guān)內(nèi)容，這塊內(nèi)容將涉及不可區(qū)分實(shí)驗(yàn)（游戲），根據(jù)敵手能力的不同，游戲的進(jìn)行方式也有所不同。第二部分：不可區(qū)分實(shí)驗(yàn)（游戲） 在給出敵手不可區(qū)分性的定義之前，有必要對(duì)敵手的能力進(jìn)行簡(jiǎn)單的分析和歸類。下面首先介紹公鑰密碼體制中，敵手的攻擊手段

6、以及相應(yīng)與這種攻擊手段，敵手所具備的破譯密碼體制的能力：（1）唯密文攻擊(COA)：敵手只能通過考察一些密文來試圖推導(dǎo)出解密密鑰（即私鑰）或這些密文對(duì)應(yīng)的明文（2）已知明文攻擊(KPA)：敵手已知一定數(shù)量的明文和相對(duì)應(yīng)的密文，試圖推導(dǎo)出私鑰或者其他密文對(duì)應(yīng)的明文。（3）非適應(yīng)性選擇明文攻擊(CPA1)：敵手可以選擇一些明文，通過訪問加密諭言機(jī)，得到這些明文相對(duì)應(yīng)的密文（4）適應(yīng)性選擇明文攻擊(CPA2)：敵手可以選擇一些明文，通過訪問加密諭言機(jī)，得到這些明文相應(yīng)的密文，且明文的選可依賴于前面得到的密文。值得注意的是，CPA1和CPA2的主要區(qū)別是在訪問加密預(yù)言機(jī)的時(shí)候，CPA1 只能一次性提交

7、所選擇的所有明文，而CPA2 可以多次分階段提交所選擇的明文。所以從敵手能力的角度來說，CPA2的敵手能力更強(qiáng)。CPA1和CPA2統(tǒng)稱為CPA。 但是CPA的敵手畢竟是屬于被動(dòng)的，下面兩種攻擊方式屬于主動(dòng)攻擊：（5）非適應(yīng)性選擇密文攻擊(CCA1)：敵手可以選擇密文，接著得到相應(yīng)的明文。即敵手擁有解密諭言機(jī)的訪問權(quán)。（6）適應(yīng)性選擇密文攻擊(CCA2) ：敵手可以選擇密文，得到相應(yīng)的明文。且在見到挑戰(zhàn)密文之后還能繼續(xù)訪問解密諭言機(jī)。 在這里CCA2 與CCA1 的區(qū)別在于敵手是否擁有在見到挑戰(zhàn)密文后還能訪問解密諭言機(jī)的能力。CCA2 中敵手有這個(gè)能力，但CCA1 沒有。CCA1 也稱為“午餐攻

8、擊”，意味著過了“午餐”時(shí)間，就不能再訪問解密諭言機(jī)了。 敵手的攻擊能力基本上可以分為以上六種，但是隨著科技的進(jìn)步，敵手的能力在不斷增強(qiáng)，需要我們對(duì)最新的攻擊方式做出新的安全性分析和證明。下面將介紹近代公鑰密碼體制中對(duì)安全性（語義安全性）普遍刻畫不可區(qū)分實(shí)驗(yàn)（游戲）。首先需給出最基本的所謂竊聽不可區(qū)分實(shí)驗(yàn)：設(shè)任意對(duì)稱密鑰密碼體制(Gen,Enc,Dec) ，任何敵手，對(duì)任意安全參數(shù)，定義竊聽不可區(qū)分實(shí)驗(yàn)：（1）敵手輸出兩個(gè)長(zhǎng)度相等的消息。（2）運(yùn)行Gen函數(shù)生成密鑰，選擇一個(gè)隨機(jī)比特，將加密得到密文，并將密文給敵手。（稱為挑戰(zhàn)密文）（3）敵手輸出，如果，則敵手攻擊成功。（注意：這里的敵手默認(rèn)為

9、PPT的敵手）定義2.1 敵手優(yōu)勢(shì)函數(shù) 參數(shù)為的函數(shù)稱為敵手優(yōu)勢(shì)函數(shù)。這個(gè)函數(shù)形象地刻畫了敵手猜對(duì)那一比特的優(yōu)勢(shì)。利用敵手優(yōu)勢(shì)函數(shù)，我們可以非常自然地給出密碼體制語義安全性的定義。不過在這之前，首先應(yīng)該給出所謂函數(shù)“可忽略”的定義：定義2.2 對(duì)于函數(shù)是可忽略的，如果，存在正整數(shù)使得時(shí)都有，定義2.3 密碼體制(Gen,Enc,Dec)是語義安全的，如果對(duì)于任何PPT的敵手，敵手優(yōu)勢(shì)函數(shù)可忽略。 這個(gè)定義給出了一般密碼體制的安全性刻畫，下面針對(duì)于公鑰密碼體制，我們給出它的安全性定義，為了方便起見，我們將給出一個(gè)包含了不可區(qū)分實(shí)驗(yàn)以及敵手優(yōu)勢(shì)函數(shù)的全新定義：定義2.4 一個(gè)公鑰密碼體制是語義安全

10、的，如果對(duì)于所有的PPT敵手，函數(shù)是可忽略的。 在這個(gè)定義中，和對(duì)應(yīng)著實(shí)驗(yàn)中的第一步（公鑰密碼體制中密鑰是公開的，所以出現(xiàn)在第一步），和是實(shí)驗(yàn)中的第二步，則是實(shí)驗(yàn)中的第三步，最后考察的事件則是。以后如果不作說明，均已這個(gè)定義來闡述密碼體制的語義安全性。 這里可以舉一個(gè)例子來說明如何定義能夠防御特定攻擊能力的敵手的密碼體制的安全性： 由上述對(duì)低收的分類我們知道適應(yīng)性選擇密文攻擊即CCA2的敵手擁有比較強(qiáng)大的攻擊能力，針對(duì)這樣的敵手，我們應(yīng)該如何定義相應(yīng)的安全性呢？ 首先我們可以寫出CCA2的不可區(qū)分實(shí)驗(yàn)：（1）運(yùn)行Gen函數(shù)生成密鑰，敵手獲得公開鑰。（2）敵手訪問解密諭言機(jī)。（即敵手輸入密文，諭

11、言機(jī)返回該密文對(duì)應(yīng)的明文）（3）敵手輸出兩個(gè)長(zhǎng)度相等的消息。（4）選擇一個(gè)隨機(jī)比特，將加密得到挑戰(zhàn)密文，并將挑戰(zhàn)密文給敵手。（5）敵手繼續(xù)訪問解密諭言機(jī)。（敵手輸入的密文不能是挑戰(zhàn)密文）（6）敵手輸出，如果，則敵手攻擊成功。從上面的過程中我們可以發(fā)現(xiàn)在CCA2的不可區(qū)分實(shí)驗(yàn)中，敵手可以隨時(shí)訪問解密諭言機(jī)，敵手試圖通過這些訪問的結(jié)果來增加自己猜對(duì)的可能。正是因?yàn)槿绱耍覀円髷呈譄o法從這些訪問的信息中得到挑戰(zhàn)密文的任何信息或者得到可忽略的信息。因此，CCA2安全性定義如下：定義2.4.1 一個(gè)公鑰密碼體制是CCA2語義安全的，如果對(duì)于所有的PPT敵手，都有，有時(shí)，函數(shù)是可忽略的。類似的我們可以定

12、義很多密碼體制的語義安全性，在這里不多作贅述。第三部分：規(guī)約證明 這一部分主要介紹如何證明一個(gè)密碼體制安全性的一種方法規(guī)約證明。 定義3.1 所謂規(guī)約，其實(shí)是復(fù)雜性理論中的概念，一個(gè)問題規(guī)約到問題是指，已經(jīng)解決問題的算法，我們能夠構(gòu)造另一個(gè)算法，可以以作為子程序，用來解決問題。如果我們將規(guī)約的方法運(yùn)用到密碼學(xué)領(lǐng)域中的話，則可以達(dá)到證明密碼體制安全性的目的。 我們可以把敵手對(duì)密碼體制的攻擊規(guī)約到一個(gè)易經(jīng)得到深入研究的密碼本原。即如果敵手能夠?qū)υ撁艽a體制發(fā)動(dòng)有效的攻擊，就可以利用敵手構(gòu)造一個(gè)算法來攻破密碼本原，從而得出矛盾。 下面我們具體到對(duì)密碼體制的安全性證明上來討論規(guī)約。假設(shè)我們要證明一個(gè)密碼

13、體制的安全性，我們可以將體制規(guī)約到體制上，即如果敵手能夠攻擊體制，則敵手能夠攻擊體制，其中體制是已經(jīng)證明安全的，或是一個(gè)困難問題，或是一個(gè)密碼本原。我們可以通過下圖來描述兩個(gè)方案之間的規(guī)約： 圖中挑戰(zhàn)者表示建立密碼體制的一方，表示敵手。當(dāng)敵手能夠成功地攻擊體制的時(shí)候，敵手模擬的挑戰(zhàn)者，參考體制的挑戰(zhàn)者對(duì)自己的訓(xùn)練去訓(xùn)練敵手，使攻破體制，從中敵手掌握了如何利用敵手攻破體制的方法以及挑戰(zhàn)者對(duì)自己的訓(xùn)練來攻破體制。 規(guī)約證明的方法已經(jīng)成為現(xiàn)代公鑰密碼學(xué)可證明安全性的基礎(chǔ)，任何密碼體制被提出必須對(duì)其進(jìn)行安全性進(jìn)行證明。而規(guī)約證明的方法則是目前一個(gè)非常實(shí)用的證明密碼體制安全性的方法。下面一個(gè)部分我們將看

14、到如何使用規(guī)約證明的方法給出一些特殊的密碼體制的安全性證明第四部分：一個(gè)例子這一部分將通過一個(gè)例子說明不可區(qū)分性在公鑰密碼學(xué)中的應(yīng)用。例1. ElGamal加密算法在選擇明文(CPA)攻擊下的安全性分析ElGamal加密算法：密鑰產(chǎn)生：設(shè)是階為大素?cái)?shù)的群，為其生成元，即。隨機(jī)選擇，計(jì)算。以為秘密鑰，為公開鑰。加密（Enc）：設(shè)消息，隨機(jī)選擇與互素的整數(shù)，計(jì)算密文為解密（Dec）： 在分析其安全性之前，我們首先驗(yàn)證一下加密算法的正確性，即是否滿足式子Dec(Enc() 顯然，滿足式。 下面對(duì)其安全性進(jìn)行分析：ElGamal加密算法的安全性是基于Diffie-Hellman判定性問題：設(shè)是階為大素

15、數(shù)的群，為其生成元。沒有多項(xiàng)式時(shí)間的算法可以區(qū)分以下兩個(gè)分布： 隨機(jī)4元組的分布； Diffie-Hellman 4元組的分布，其中，。 這里對(duì)次問題進(jìn)行變形，我們做代換：，那么上述兩個(gè)分布變形為： 隨機(jī)3元組的分布； Diffie-Hellman 3元組的分布。， 那么ElGamal加密算法與Diffie-Hellman判定性問題不可區(qū)分。原因在于當(dāng)挑戰(zhàn)者與敵手進(jìn)行CPA不可區(qū)分游戲時(shí)，敵手輸出兩個(gè)長(zhǎng)度相同的消息，挑戰(zhàn)者加密，得到密文。 如果，則為Diffie-Hellman 3元組。 如果，則也為Diffie-Hellman 3元組。兩者不可區(qū)分。 不可區(qū)分性在公鑰密碼學(xué)中扮演著十分重要的角色，是可證明安全理論的基石，也是證明密碼體制或者加密算法在某種意義下安全的必要手段。本文對(duì)于不可區(qū)分性內(nèi)容的歸納尚未系統(tǒng)化，有些結(jié)論也只是適用于較平凡的情況。比如第四部分的例子中，ElGamal加密算法在CPA意義下已經(jīng)能夠證明是安全的，但是這是基于敵手完全被動(dòng)的情況，如果敵手能夠選擇性的發(fā)動(dòng)主動(dòng)攻擊，這個(gè)加密算法也是不安全的。例如敵手可以在得到的密文上進(jìn)行更改，構(gòu)造出新的密文，其中，解密詢問以后得到，通過計(jì)算得到的明文。或者可以構(gòu)造，其中，此時(shí)解密