黃貽望 袁科,2 楊英杰

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

0 引言

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

1 隨機預言模型可證明安全及歸約論斷

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

1.1 安全性目標

加密方案的安全目標：

(1) 單向性：由密文不能恢復相應的明文。

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

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

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

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

1.2 敵手模型定義

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 RO模型介紹

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

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

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

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

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

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

1.4 歸約論斷及其安全性

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

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

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

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

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

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

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

圖1 加密RO模型

假設(shè)有個具有一定優(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的目標是求解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) 當A選擇 (m0,m1) 后，M選擇密文a←y||w||b，其中w和b隨機選擇。

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

(4) 令事件Ak表示 A 能構(gòu)造密文a| |w||b僅當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)勢當且僅當事件 Ak或Lk發(fā)生，即Pr[Asucc[Lk∧Ak]=1/2，故

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

3 結(jié)語

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

[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]張文政.公鑰密碼密碼體制可證明安全性的幾點注記[J].信息安全與通信保密.2005.

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