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

黃貽望 袁科,2 楊英杰

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

0 引言

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

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

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

1.1 安全性目標

加密方案的安全目標：

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

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

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

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

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

1.2 敵手模型定義

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

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

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

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

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

其安全性證明可以用以下的對局實現：

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

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

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

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

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

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

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

1.3 RO模型介紹

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

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

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

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

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

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

1.4 歸約論斷及其安全性

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

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

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

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

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

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

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

圖1 加密RO模型

假設有個具有一定優勢的敵手 A，則得到它的攻擊 RO模型如圖2所示。

圖2 攻擊RO模型

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

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

選擇密文安全性證明(IND-CCA2)：假設存在優勢為λ(k) 的IND—CCA2敵手，構造算法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*是拋幣的結果。

(4) 令事件Ak表示 A 能構造密文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詢問，但從未提出過關于f-1(a) | |w⊕G(f-1(a))的H詢問。令n(k)表示A提出的詢問總次數，k是安全參數，顯然是有Pr[Lk] ≤n(k) · 2-k，容易看出：A有成功優勢當且僅當事件 Ak或Lk發生，即Pr[Asucc[Lk∧Ak]=1/2，故

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

3 結語

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

[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.