基于RO模型的公鑰加密方案安全性分析與證明

黃貽望 袁科,2 楊英杰

1銅仁學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 貴州 554300 2南開大學(xué)信息技術(shù)科學(xué)學(xué)院 天津 300071

0 引言

密碼方案或協(xié)議的安全性證明在設(shè)計(jì)階段又是很難做到的，基于此目前普遍做法是，提出一種方案或協(xié)議后，根據(jù)某種困難性假設(shè)，做出具體的安全性分析，然后給出其安全性論斷：如果在一段時(shí)間內(nèi)找不到該方案協(xié)議的漏洞，則接受其安全性論斷；否則，加以修正以繼續(xù)使用，直至超出應(yīng)用所能承受的代價(jià)?？勺C明安全性理論方法是首先確定所設(shè)計(jì)的方案或協(xié)議安全性目標(biāo)和攻擊敵手模型，通過敵手在多項(xiàng)式時(shí)間內(nèi)成功破解的概率優(yōu)勢是可以忽略的，從而給出其安全性證明，通過可證明安全性方法得到證明的方案或協(xié)議可以防止一些未知的攻擊。

1 隨機(jī)預(yù)言模型可證明安全及歸約論斷

一個(gè)典型的RO模型首先確定安全目標(biāo)和敵手模型，因此，實(shí)現(xiàn)可證明安全性的首要工作是在為密碼體制確定合適的安全性目標(biāo)，由于密碼體制因應(yīng)用要求不同而有所側(cè)重，大致分為加密安全性和簽名安全性：

1.1 安全性目標(biāo)

加密方案的安全目標(biāo)：

(1) 單向性：由密文不能恢復(fù)相應(yīng)的明文。

(2) 不可區(qū)分性：對敵手給定的兩個(gè)明文，加密者隨機(jī)選擇其中一個(gè)進(jìn)行加密，敵手無法從密文中知道是對哪個(gè)明文的加密。

(3) 語義安全性：敵手在知道密文的情況下，能計(jì)算出明文的信息量并不他在不知道密文的時(shí)候多，除了明文長度。

(4) 不可延展性：敵手無法構(gòu)造與已給密文有關(guān)系的新密文。

(5) 明文可意識(shí)性：敵手不能以一個(gè)不可忽略的概率，在不知道明文的情況下，構(gòu)造一個(gè)密文。

1.2 敵手模型定義

加密方案的敵手攻擊類型有：

(1) 選擇明文攻擊(CPA)：敵手可加密所選的任何明文，獲得相應(yīng)的密文。

(2) 非適應(yīng)性選擇密文攻擊(CCA1)：敵手在得到挑戰(zhàn)密文C*之前可以選擇密文詢問解密機(jī)，以獲得相應(yīng)的明文，但在得到C*后就不再詢問解密機(jī)。

(3) 適應(yīng)性選擇密文攻擊(CCA2)：敵手在得到挑戰(zhàn)密文C*前后都可以詢問解密機(jī)，以獲得相應(yīng)的明文，但在得到C*后，不能詢問C*的明文。

對于加密方案，目前接受的安全性是適應(yīng)性選擇密文攻擊下的不可區(qū)分性(IND—CCA2)，所以具有語義安全的加密方案是指該方案具有IND—CCA2安全性。

其安全性證明可以用以下的對局實(shí)現(xiàn)：

(1) 密鑰生成器生成系統(tǒng)的公鑰和私鑰，公鑰向敵手公開而私鑰對其保密。

(2) 敵手A選擇密文解密機(jī)進(jìn)行一系列的詢問，對每一個(gè)詢問解密機(jī)用私鑰解密并將解密結(jié)果給敵手。敵手可以任意的方式構(gòu)造這些密文，不一定用加密算法來構(gòu)造。

(3) 敵手A也可以對加密機(jī)進(jìn)行一系列的詢問。敵手選擇兩長度相同的消息M0和M1交給加密機(jī)，該加密機(jī)隨機(jī)選b∈R{ 0,1}，然后對Mb進(jìn)行加密得到密文Cb*交給敵手A。

(4) 敵手A仍然可象第(2)步一樣向解密機(jī)提出新的詢問，但他不能詢問目標(biāo)密文Cb*。

(5) 敵手A輸出b'∈ { 0 ,1}，表示它對b的猜想，如果b=b'，則敵手贏得對局。

在對局中，敵手A的優(yōu)勢(Advantage)定義為概率

稱一個(gè)公鑰加密體制是IND—CCA2安全的，是指對于任意的多項(xiàng)式時(shí)間敵手A，它的優(yōu)勢是可以忽略的。

1.3 RO模型介紹

完整的RO模型：假定各方共同擁有一個(gè)公開的Random Oracle就可以構(gòu)建一個(gè)安全協(xié)議P，首先在RO模型中證明PR，然后用函數(shù)h取代Oracle。需指出的是，這種模型的可證明安全性并非嚴(yán)格意義上的。

假設(shè)我們提出一個(gè)協(xié)議問題∏(這個(gè)問題和h函數(shù)“獨(dú)立”)，要設(shè)計(jì)一個(gè)安全協(xié)議P解決該問題，可按如下步驟執(zhí)行：

(1) 建立∏在RO模型中的形式定義，RO模型中各方(包括敵手)共享隨機(jī)OracleR；

(2) 在RO模型中設(shè)計(jì)一個(gè)解決問題∏的有效協(xié)議P；

(3) 證明P滿足∏的定義；

(4) 在實(shí)際應(yīng)用中用函數(shù)h取代R。

1.4 歸約論斷及其安全性

在RO模型中的歸約論斷一般表現(xiàn)為：首先形式化定義方案的安全性；假設(shè)PPT敵手能夠以不可忽略的概率破壞協(xié)議的安全性(如偽造簽名)；然后模仿者S(就是設(shè)計(jì)者或分析者)為敵手提供一個(gè)與實(shí)際環(huán)境不可區(qū)分的模擬環(huán)境(RO模型)，回答敵手的所有Oracle詢問(模擬敵手能得到的所有攻擊條件)；最后利用敵手的攻擊結(jié)果(如一個(gè)存在性的偽造簽名)設(shè)法解決基礎(chǔ)難題，如果把RO模型換成現(xiàn)實(shí)模型就得到標(biāo)準(zhǔn)安全性證明。

歸約論斷的思想：(1)指明問題P1的難解性意味著另一個(gè)問題P2的難解性；(2)求解P2的算法可以用來求解P1。

具體安全性處理的一個(gè)重要目標(biāo)就是：在把一個(gè)基本原子命題轉(zhuǎn)化成相應(yīng)協(xié)議時(shí)，盡可能多地表現(xiàn)原子的強(qiáng)度，這表現(xiàn)為要求“緊”的歸約方法，因?yàn)橐粋€(gè)“松”歸約意味著要求采用更長的安全參數(shù)，從而降了效率。

2 公鑰加密方案的可證明安全性分析與證明

可證明安全理論能夠保證密碼方案或協(xié)議在某種強(qiáng)度下的安全性，能夠預(yù)防未知的攻擊，因此，成為現(xiàn)代密碼學(xué)一個(gè)熱點(diǎn)研究方向，許多密碼學(xué)者做出一些相關(guān)的可證明安全方案或協(xié)議，這里僅就RO模型下的滿足選擇密文安全性的加密方案(BR)作簡要說明。

2.1 RO模型下的IND-CCA2安全性證明思想

由前面可得到如圖1所示的公鑰加密的RO模型。

圖1 加密RO模型

假設(shè)有個(gè)具有一定優(yōu)勢的敵手 A，則得到它的攻擊 RO模型如圖2所示。

圖2 攻擊RO模型

2.2 BR方案的IND-CCA2安全性證明

2.2.2 BR方案的IND—CCA2安全性證明

選擇密文安全性證明(IND-CCA2)：假設(shè)存在優(yōu)勢為λ(k) 的IND—CCA2敵手，構(gòu)造算法M，任意給定y，M的目標(biāo)是求解f-1(y),步驟如下：

(1) 在find-stage，M仿真oracle G，H和DG，H；M回答解密詢問a| |w||b方法；如果A做過G詢問r和H詢問ru且滿足于a=f(r)andw=G(r) ⊕u，則返回u，否則返回“無效”。

(2) 當(dāng)A選擇 (m0,m1) 后，M選擇密文a←y||w||b，其中w和b隨機(jī)選擇。

(3) 在guess-stage，M以同樣的方式仿真oracleG,H和DG,H；若有G詢問r滿足f(r) =y；此明M就會(huì)成功。若為了使 A感覺不到欺騙，M可以計(jì)算G(r) =w⊕mb*,H(mb*) =b,b*是拋幣的結(jié)果。

(4) 令事件Ak表示 A 能構(gòu)造密文a| |w||b僅當(dāng)A提過r的G詢問或ru的H詢問，其中r滿足a=f-1(r)。令事件Lk表示a| |w| |b(滿足b=H(f-1(a) | |w⊕G(f-1(a))))的DG,H詢問，但從未提出過關(guān)于f-1(a) | |w⊕G(f-1(a))的H詢問。令n(k)表示A提出的詢問總次數(shù)，k是安全參數(shù)，顯然是有Pr[Lk] ≤n(k) · 2-k，容易看出：A有成功優(yōu)勢當(dāng)且僅當(dāng)事件 Ak或Lk發(fā)生，即Pr[Asucc[Lk∧Ak]=1/2，故

注意到事件 Lk則M將會(huì)失敗，故Pr[Mi n vertf]≥λ(k) -n(k)·2-k，因此方案具有選擇密文的安全性。

3 結(jié)語

可證明安全性理論是基于一定的基礎(chǔ)假設(shè)的選取，因此安全強(qiáng)度依賴于某一假設(shè)為基礎(chǔ)，因此，假設(shè)越弱的安全性證明越可靠。同時(shí)，兩種可證明安全性模型相比較，隨機(jī)預(yù)言(RO)模型盡管是在一定的條件下的安全性，但是具有重要實(shí)際應(yīng)用價(jià)值；而標(biāo)準(zhǔn)模型的可證明安全性由于實(shí)現(xiàn)的代價(jià)大，因此，適應(yīng)于理論分析。

[1]Bellare M. Practice-Oriented provable-security.In: Damgard I,ed.Modern Cryptology in Theory and Practice.LNCS 1561,Berlin,Heidelberg:Springer-Verlag.1999.

[2]Goldreich O.Foundations of Cryptography.Cambridge:Cambridge University Press.2001.

[3]Goldwasser S, Micali S. Probabilistic encryption. Journal of Computer and System Science.1984.

[4]Goldwasser S,Micali S,Rivest R.A digital signature scheme secure against adaptive chosen-message attacks.SIAM Journal of Computing.1988.

[5]Bellare M,Rogaway P.Random oracles are practical:A paradigm for designing efficient protocols.In: Proc.of the 1st ACM Conf. on Computer and Communications Security.New York:ACM Press.1993.

[6]張文政.公鑰密碼密碼體制可證明安全性的幾點(diǎn)注記[J].信息安全與通信保密.2005.

[7]馮登國.可證明安全性理論與方法研究[J].軟件學(xué)報(bào): Vol.16,No.10.