發展安全的公鑰密碼系統的新方法研究

摘要：從確保密鑰真實性的角度介紹了傳統公鑰基礎設施、基于身份的公鑰密碼系統以及最近提出的兩個新思路，即基于證書的加密和無證書的公鑰密碼系統；分析比較了它們各自的基本思想、優缺點，并對未來的發展方向進行了展望。

關鍵詞：公鑰基礎設施；基于身份的公鑰密碼系統；基于證書的加密；無證書的公鑰密碼系統

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)10-0005-04

在采用密碼技術保護的現代通信系統中，密碼算法通常是公開的，其安全性取決于對密鑰的保護。因此，密鑰管理顯得尤其重要。在公鑰密碼系統中，加密密鑰可以公開傳播，對在公開網絡上進行保密通信、密鑰分配、數字簽名和認證帶來了深遠影響。但是，公鑰的這種公開性也使得它面對主動攻擊時特別脆弱。敵手可以用一個假公鑰P′替換用戶A的真實的公鑰P。所以，除了密鑰對（S，P）和用戶的身份之外，用戶還必須擁有一個保證書，以確保P確實是用戶A的公鑰，而不是一個冒名頂替者 A′的公鑰。當前發展安全的公鑰密碼系統的主要問題是如何建立和管理相應的基礎設施以保證密鑰的真實性。依照保證書的形式，可以對具體的公鑰密碼方案進行分類。最典型的類型有傳統的基于證書的公鑰密碼方案和基于身份的密碼方案。由于這兩種方案的優缺點都較明顯，學者們試圖結合這兩種方案的特點，尋求更有效的方案。例如，基于此Girault提出了自證明公鑰概念及相關應用[1]。最近Gentry和AlRiyami分別提出了兩個新思路，即基于證書的加密（CBE）和無證書的公鑰密碼系統（CLPKC）。

1背景知識

雙線性映射e可以從有限域的橢圓曲線上的Weil對或Tate對導出[2]。

1．3雙線性DiffieHellman問題

設G1是階為大素數q的加法循環群，P是G1的生成元。

計算性DiffieHellman問題(CDHP)：已知(P，aP，bP)，計算abP。

判定性DiffieHellman問題(DDHP)：已知(P，aP，bP，cP)，判斷c≡ab mod q是否成立。

CDH假設：不存在有效多項式時間的算法可以解決CDHP。

Gap DiffieHellman(GDH)群：在群G中，如果存在多項式時間算法解DDHP，但CDHP無法解，即CDH假設成立，就稱G為一個GDH群。

雙線性DiffieHellman問題(BDHP)：已知(P，aP，bP，cP)，計算e(P，P)abc。

雙線性DiffieHellman(BDH)假設：不存在有效的多項式時間算法可以解決BDHP。 

2傳統的公鑰密碼系統

公鑰基礎設施（PKI）是當前部署傳統的公鑰密碼系統（PKC）的主要手段（本文中所提到的PKI都是指用于支持傳統公鑰密碼算法的基礎設施）。在PKI中，一個用戶的身份與其公鑰之間的綁定關系是通過數字證書形式獲得的。證書由可信的證書授權機構（CA）為用戶建立。其中的數據項包括該用戶的公鑰PK和身份I以及一些輔助信息，如公鑰的使用期限、公鑰序列號或識別號、采用的公鑰算法、使用者的住址或網址等。所有的數據經CA用自己的私鑰簽名后就形成證書。CA在給用戶發放證書之前，先驗證該用戶身份的真實性。任何一個信任CA的通信一方，都可以通過驗證對方數字證書上CA的數字簽名來建立起與對方的信任關系，并且獲得對方的公鑰以備使用。

這種傳統的PKI技術存在很多問題。一方面證書管理的過程需要很大的計算量和很強的存儲能力。與證書管理有關的問題，包括證書的撤銷、更新、存儲、分發以及驗證都需要較高的計算成本。其中最顯著的就是證書撤銷問題。由于證書是可撤銷的，CA必須發布大量的最新證書狀態信息以指出某用戶的證書當前是否有效。這些問題對處理器來說，在帶寬受限的環境中顯得特別嚴重。另一方面，靜態的集中化控制和固定的證書內容是傳統PKI固有的缺陷。這個缺點使很多實際應用受限，被認為是許多商業和法律相關問題的根源[3]。

3基于身份的公鑰密碼系統（IDPKC）

3．1IDPKC的概念

為了簡化證書管理問題，Shamir于1984年首次提出了基于身份的公鑰密碼系統（IDPKC）的概念，指出公鑰密碼系統中密鑰真實性問題可以不使用證書而得以解決[4]。

在IDPKC中，每個用戶都有某個身份信息ID。簡單地說就是可以用于識別某個用戶的一個字符串，例如用戶主機的IP地址或用戶的電子郵件地址。一個用戶的公鑰直接由他的身份信息ID導出（一般情況下就是身份信息的哈希值）。相應的私鑰則由一個被稱為私鑰生成器（PKG）的可信第三方利用其主密鑰為該用戶生成。PKG在證實了用戶身份后，才會為他計算出相應的私鑰并發送給他。這實際上就意味著用戶獲得了一種確保其身份和公鑰之間捆綁關系的內在證明。

3．2BF IDPKE方案 

雖然基于身份的思想1984年就已經提出，但Shamir當時只構造出一個具體的簽名方案，并沒有找到設計基于身份的加密（IDPKE）系統的方法。直到2001年，第一個完全實用的安全的IDPKE方案才由Boneh和Frankin提出[2]。該方案（簡稱為BF IDPKE方案）利用橢圓曲線上的雙線性對（Weil對）構造，在隨機預言模型下被證明是自適應性選擇密文安全的。從此以后，IDPKC得到了迅速發展，出現了很多基于身份的簽名方案[5，6]、密鑰協商協議[7]、分層次的方案[8]。BF IDPKE方案的安全性基于BDH假設。具體方案描述如下：

IDPKC具有以下幾個主要性質：用戶公鑰由他的身份直接導出從而不需要公鑰目錄；用戶的私鑰可以在他的公鑰生成并在使用之后再確定。這些與傳統PKI完全不同的性質不僅可以使密鑰分發變得更簡單，而且還可以使該密碼系統具有靈活的密碼學工作流程[3]。所謂密碼學工作流程就是一個用戶為了達到某種目的所需要執行的一系列操作。用戶B可以用他為A所選擇的標志符串加密消息給A。這個標志符應當包含A的身份信息，還可以包含在PKG發送相應的私鑰之前A必須滿足的條件。只有當A滿足該條件后PKG才會將相應的私鑰發送給A。例如，把日期作為條件串接在用戶A的身份信息IDA后，使得該公鑰在這天之后失效（即在這天之后，PKG就不再為用戶A發送與此標志符即公鑰相對應的私鑰了），就可以解決密鑰撤銷問題。在傳統的基于證書的系統中公私鑰和證書生成的時間順序是固定的，即私鑰在公鑰之前生成，公鑰在證書注冊和發放之前生成。因此傳統PKC很難支持這樣的應用。由此可以看到，IDPKC與傳統的PKC相比更有優勢。

3．3．2缺點

在IDPKC中，公鑰由身份信息直接導出，不再需要獨立的證書，從而消除了由管理證書所引發的一系列問題。但是另一方面，PKG利用系統范圍內的主密鑰為用戶生成私鑰不可避免地導致了IDPKC系統所固有的密鑰托管問題。舉例來說，在IDPKS方案中，PKG可以偽造任何實體的簽名，這樣IDPKC就不能像傳統的PKI那樣提供真正的抗否認性。另外，PKG必須通過安全的信道將用戶私鑰發送給用戶，使得私鑰分發比較困難。以上兩個缺陷特別是密鑰托管問題在諸如email等應用中讓人難以接受。由此看來，IDPKC也許只能限制在小的封閉的群體范圍內使用，或是在有限的安全需求情況下應用[9]。針對IDPKC中的密鑰托管問題，也提出了很多解決方法。一種方法是通過引入多個PKG解決該問題[2，6]，但這些處理方法必然需要額外的通信和基礎設施。另外，多個PKG必須獨立地檢驗用戶的身份，對整個系統來說無疑是增加了負擔。另一種方法則是利用用戶自己選擇的某個秘密信息。按照這個思路，形成了基于證書的加密和無證書的公鑰密碼系統。

4基于證書的加密（CBE）

4．1概念及具體實現 

為了簡化傳統PKI中的證書撤銷問題，C.Gentry提出了基于證書的加密的概念[10]，并利用BF IDPKE方案設計了一個具體的CBE方案。該方案是傳統的公鑰加密方案和基于證書的加密方案的組合。與BF IDPKE方案相比，它幾乎沒有增加開支：加密復雜度略微提高但解密復雜度和密文長度完全相同。2004年，Bo Gyeong Kang等人[11]利用與文獻[10]中完全相同的參數及證書撤銷策略，提出了基于證書的簽名的安全性概念，設計了一個基于證書的簽名方案并在隨機預言模式下證明了它的安全性。Gentry的CBE方案描述如下：

在Gentry的模式中，用戶A的私鑰由兩部分組成：由用戶自己選擇并且保密，即方案中的xAQA′；隨時間而定的，由CA替用戶計算且可以在公開信道上傳送給A，即CertA。用戶A的公鑰也由兩個部分組成，且分別與私鑰的兩部分相匹配。其中：PA與A自己選擇的那部分私鑰xAQA′匹配且假設任何想加密消息給A的第三方B都容易得到它； QA可由B利用CA的參數、當前的時間值以及A的公鑰假定值計算得到。私鑰的第二部分CertA實質上是CA給用戶頒發的暗含的證書。這個證書具有傳統PKI證書的所有功能，所不同的是CA利用IBE方案生成此證書，并將此證書用做部分解密密鑰參與解密過程。這個附加功能提供了內在保證：加密消息m給A時，B同時使用公鑰的兩個組成部分對m進行雙加密；A必須同時擁有私鑰的兩個部分，即他自己的個人秘密密鑰和一個CA頒發的最新證書才能夠解密。B之所以能確信只有A能解密是由于它信任CA會正確地更新和分發私鑰的第二個部分。CBE方案的安全性關鍵依賴于CA將正確的公鑰和A的每個時期的暗含的證書捆綁在一起。

CBE同時保留了傳統PKC和IDPKC的優點。與PKI一樣，每個用戶為自己生成公私鑰對，并從CA處申請一個證書。又由于CA不知道用戶A的個人秘密密鑰，不存在密鑰托管問題；而且CA發放的證書不需要保密，不存在秘密密鑰分發問題。頻繁的證書更新使得發送者不需要再去檢查他們得到的證書撤銷狀況，有效地簡化了PKI中的密鑰撤銷問題。

4．2主要缺陷 

CA需要為方案中的每個用戶在每個時間段頒發新的暗含的證書。這實際上給CA增加了很多計算量和通信量，即使是一個用戶總數較少的PKI。基本的CBE方案可以被認為是簡化證書撤銷、為CA減輕不斷增長的工作負荷的有效方法。但它失去了傳統PKI所具有的一個關鍵性質：CA只需要在線執行撤銷功能，其他職責幾乎能夠以離線的方式完成。文獻[11]使用子集覆蓋等方法對基本的CBE方法作了許多增強，這使得必須由CA執行的工作減少了但還沒有完全消除。

5無證書的密碼系統（CLPKC）

5．1概念

S.S.AlRiyami等人[12]提出了一個支持公鑰密碼學應用的新典范——無證書的公鑰密碼系統（CLPKC）。CLPKC也需要一個可信權威，在這里被稱為私鑰生成中心（KGC）。CLPKC的主要特點是它完全不需要證書，并且還消除了IDPKC中固有的密鑰托管問題。上述特點的實現依賴于下面的技術手段。一個用戶的私鑰分兩個步驟產生:a）KGC根據用戶A的身份信息標志符IDA和他的主密鑰s計算出部分私鑰DA并通過秘密的可靠信道發送給用戶。KGC必須確保將部分私鑰安全地發送給用戶A。b）用戶將收到的部分私鑰DA和某個只有用戶自己知道的秘密信息xA組合從而產生實際的私鑰SA。這樣，PKC就不知道用戶的私鑰了。

5．2具體實現

文獻[12]給出了無證書的公鑰加密（CLPKE）及其安全性的定義，提出了一個基于廣義的雙線性DiffieHellman問題（GBDHP）的CLPKE方案。該方案與BF IDPKC方案相似，被證明是INDCCA安全的。文獻[12]同時還設計了無證書的公鑰簽名方案、密鑰交換方案及分層次的CLPKC。此后，文獻[13]又對文獻[12]中的方案進行了修改，提出了一個新的基于雙線性DiffieHellman問題（BDHP）的CLPKE方案。與文獻[12]中的方案相比，所需的雙線性對的計算量更小、公鑰長度更短；由于BDHP比GBDHP更難，使得其安全性更有保障。具體方案描述如下：

5．3性質

1）不需要證書與傳統的基于證書的PKC相比，CLPKC消除了使用證書所引發的許多問題：身份信息標志符只包含相關信息，為用戶提供了更高度的隱私權；與證書相關的冗余不再存在，使得CLPKC的存儲和通信帶寬較低；不需要在使用公鑰前驗證證書，減少了計算量，提高了效率；相對傳統PKI中靜態的集中化控制和固定的證書內容，CLPKC既可以靜態控制又可以動態控制，而標志符內容是動態的，這使得它在實際應用中會顯得更加靈活。

2）靈活的密碼學工作流程與IDPKC一樣，用戶的私鑰可以在他的公鑰生成并且使用后再確定，所以CLPKC也支持密碼學工作流程。實體可以具體指定標志符的內容，從而可以在該系統中發揮更突出的作用。

3）互操作性由于CLPKC方案與基于雙線性對的IDPKC方案有密切聯系，任何支持基于雙線性對的IDPKC方案的基礎設施都可以用于支持CLPKC方案，即這兩種方案可以很方便地共存。

4）信任級別和抗否認性任何公鑰密碼系統都需要可信的權威機構（TA）。Girault將用戶和他們的TA之間的信任關系分為三個級別[1]：級別1指TA知道用戶的私鑰，可以在任何時候冒充任何實體而不被察覺；級別2指雖然TA不知道（或不能容易地計算出）實體的私鑰，但可以通過偽造保證書來冒充實體；級別3是指TA在不知道（或不能容易地計算出）實體私鑰的情況下可以冒充任何實體，但是事后能有證據證明這種欺騙行為。

在傳統的PKI中，因為只有CA能簽發證書，所以對同一個身份存在兩個有效的證書就能作為CA行為不軌的證據。傳統的PKI能達到信任級別3。在IDPKC中，PKG知道每個實體的私鑰，故IDPKC只能達到信任級別1。對CLPKC，情況則復雜一些。當部分私鑰公開時，假的部分私鑰可以作為KGC行為不軌的證據，因為只有KGC才能生成與假公鑰相對應的部分私鑰；當部分私鑰不公開時，使KGC牽連其中的證據只有：某個消息用不同的兩個正在使用的公鑰加密過兩次。但是，發現同一個消息用兩個不同的公鑰加密過并不能簡單地說明是KGC在欺騙。因為也有可能是不誠實的參與者用兩個不同的公鑰加密了同一個消息，所以應該說CLPKC的信任級別介于2、3級[14]。

5．4CLPKC和CBE的關系

CLPKC和CBE在概念上很相像，所使用的私鑰都由兩部分組成。其中一部分由用戶自己選擇；另一部分由可信權威機構利用其主密鑰為用戶計算。但是，Gentry的CBE方案是在傳統PKI的背景下構建的，目的是簡化PKI中的證書撤銷問題。CLPKC則試圖擺脫IDPKC和PKI所強加的思想束縛。它不僅完全背離了傳統PKI的模式，也脫離了IDPKC的模式。事實上，S.S.AlRiyami和K.G.Paterson提出可以修改Gentry的工作使其脫離傳統PKI的背景。而且，只要把公鑰和時間期限添加到身份標志符中，就可以將CLPKC方案作適當修改以能夠具有提供CBE的功能[13]。

6結束語

本文介紹了PKI、IDPKC、CBE和CLPKC的概念，并從確保密鑰真實性的角度分析比較了它們各自的基本思想和優缺點。可以看出，CLPKC是介于傳統PKI與IDPKC的一種公鑰密碼學。CLPKC方案不再是基于身份的方案，因為用戶公鑰不再是直接由其身份導出；它通過在私鑰生成過程中使用用戶自己指定的秘密信息，從而避免了IDPKC中固有的密鑰托管問題；它不需要證書來使用戶對公鑰產生信任，而是通過內在的方式加以實現。可以說，CLPKC的思想不僅兼有傳統PKC和IDPKC的優點，而且還基本上克服了兩者的缺點，因而特別適用于無法接受密鑰托管但是又難以維持整個PKI負擔的情況。無證書公鑰密碼系統的研究思路相當有吸引力。雖然目前已經產生了一些無證書的加密和簽名方案，但還有許多工作有待于進一步開展。比如如何設計更有效更安全的無證書加密方案、簽名方案、密鑰協商方案，如何設計無證書的群簽名、環簽名及電子拍賣等協議都非常值得研究。

參考文獻：

［1］GIRAULT M. Selfcertified public keys[C]//Advances in CryptologyEurocrypt’91，LNCS 547.Berlin:SpringerVerlag，1991：490-497.

[2]BONEH D，FRANKLIN M.Identitybased encryption from the Weil pairing [C]//Advances in CryptologyCrypto’01， LNCS 2139.Berlin: SpringerVerlag， 2001:213-229. 

[3]PATERSON K G，PRICE G. A comparison between traditional public key infrastructures and identitybased cryptography[J].Information Security Technical Report，2003，8(3):57-72.

[4]SHAMIR A. Identitybased cryptosystems and signature schemes[C]//Advances in CryptologyCrypto’84， LNCS 196.Berlin: SpringerVerlag， 1984:47-53.

[5]CHA J C，CHEON J H.An identitybased signature from gap Diffie Hellman groups[C]//Proc of Public Key CryptographyPKC’03， LNCS 2567.Berlin: SpringerVerlag， 2003:18-30. 

[6]HESS F.Efficient identitybased signature schemes based on pairings[C]//Proc of Selected Areas in CryptographySAC’02， LNCS 2595.Berlin: SpringerVerlag，2003:310-324.

[7]SMART N P.An identitybased authenticated key agreement protocol based on the Weil pairing[J].Electronics Letters，2002，38(13): 630-632.

[8]GENTRY C，SILVERBERG A.Hierarchical IDbased cryptography[C]//Advances in CryptologyAsiacrypt’02， LNCS 2501.Berlin: SpringerVerlag， 2002:548-566.

[9]PATERSON K G.Cryptography from pairings:a snapshot of current research[J].Information Security Technical Report，2002，7(3):41-54.

[10]GENTRY C.Certificatebased encryption and the certificate revocation problem[C]//Advances in CryptologyEurocrypt’03， LNCS 2656.Berlin: SpringerVerlag，2003:272-293. 

[11]KANG B G，PARK J H，HAHN S G.A certificatebased signature scheme[C]//Proc of CTRSA’04， LNCS 2964.Berlin: SpringerVerlag，2004:99111.

[12]ALRIYAMI S S，PATERSON K G.Certificateless public key cryptography[C]//Advances in CryptologyAsiacrypt’03， LNCS 2894.Berlin:SpringerVerlag，2003:452-473. 

[13]ALRIYAMI S S，PATERSON K G.CBE from CLPKE:a generic construction and efficient schemes[C]//Proc of Public Key Cryptography PKC’05， LNCS 3386.Berlin: SpringerVerlag，2005:398-415. 

[14]ALRIYAMI S S.Cryptographic schemes based on elliptic curve pairings[D].London:University of London， 2004.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”