公鑰密碼體制研究綜述

溫雅敏

摘要：公鑰密碼體制對于保證網(wǎng)絡(luò)信息安全起到了非常重要的作用，本文結(jié)合筆者學(xué)習(xí)密碼學(xué)基礎(chǔ)的一些體會，對公鑰密碼體制的基本概念，發(fā)展現(xiàn)狀、及未來的發(fā)展展望做個簡單地概述。

關(guān)鍵詞：公鑰密碼體制；RSA；離散對數(shù)；橢圓曲線

1引言

密碼已有幾千年的歷史。在很長一段時間里，密碼都是作為一種隱蔽通信技術(shù)。直到20世紀50年代，1949

年，信息論創(chuàng)始人Shannon發(fā)表的經(jīng)典論文“保密通信的信息理論”，將密碼學(xué)的研究引入了科學(xué)的軌道。密碼才發(fā)展成為一門完整的、成熟的學(xué)科。整體而言，安全與秘密通訊的學(xué)科包括密碼編碼學(xué)（cryptography）與密碼分析學(xué)（cryptoanalysis），統(tǒng)稱為密碼學(xué)（Cryptology）。1976年，著名學(xué)者Diffie和 Hellman“密碼學(xué)新方向”的發(fā)表，奠定了公鑰密碼學(xué)的基礎(chǔ)；Diffie和Hellman描述了幾個可能用來實現(xiàn)公鑰密碼的數(shù)學(xué)變換，稱之為單向陷門函數(shù)，簡單地理解即是從x計算y=f(x)是容易的，而從y計算出x是困難的，單向陷門函數(shù)的概念使得公鑰密碼系統(tǒng)成為可能。[1]

隨著計算機網(wǎng)絡(luò)迅猛發(fā)展及電子商務(wù)應(yīng)用的需求，網(wǎng)絡(luò)信息安全保密性要求日益提高，公鑰密碼體制在數(shù)字簽名和公開信道密鑰建立上的兩個重要應(yīng)用，保證網(wǎng)上數(shù)據(jù)傳輸?shù)耐暾?、有效性和不可否認性，對促進網(wǎng)絡(luò)安全電子商務(wù)的發(fā)展也就起到了不可替代的巨大作用。本文結(jié)合筆者在密碼學(xué)基礎(chǔ)學(xué)習(xí)的基礎(chǔ)上，對公鑰密碼體制的基本概念，發(fā)展現(xiàn)狀、及未來發(fā)展的展望做個簡單地概述。

2基礎(chǔ)知識

保密是密碼學(xué)的核心，而加密是獲得信息保密的實用工具?，F(xiàn)代加密技術(shù)主要分為兩種體制，一種是稱為對稱密碼體制（又稱為單鑰密碼體制），另一種也是我們重點介紹的稱為非對稱密碼體制（又稱為雙鑰/公鑰密碼體制），我們在此分別對這兩個概念做個簡單的總結(jié)。

2.1對稱密碼體制

對稱密碼體制是一種傳統(tǒng)密碼體制,也稱為單鑰/私鑰密碼體制。在對稱加密系統(tǒng)中,加密和解密采用相同的密鑰，密文發(fā)送者必須和密文接收者分享密文的該加密密鑰。因為加解密密鑰相同,需要通信的雙方必須選擇和保存他們共同的密鑰,各方必須信任對方不會將密鑰泄密出去,這樣就可以實現(xiàn)數(shù)據(jù)的機密性和完整性。然而，這需要通信雙方在基于對稱密碼體制進行保密通信以前，必須首先生成它們之間共享的正確密鑰，這需要在網(wǎng)絡(luò)應(yīng)用中不依賴于物理地傳輸，即要建立安全的密鑰信道保證密鑰的保密性和可靠性。這也是對稱密碼體制的一個不足之處。

2.2非對稱密碼體制

非對稱密碼體制也稱為公鑰加密技術(shù),該技術(shù)就是針對私鑰密碼體制的缺陷被提出來的。在公鑰加密系統(tǒng)中,加密和解密是相對獨立的,加密和解密會使用兩把不同的密鑰,加密密鑰(公開密鑰)向公眾公開,誰都可以使用,解密密鑰(秘密密鑰)只有解密人自己知道,非法使用者根據(jù)公開的加密密鑰無法推算出解密密鑰,顧其可稱為公鑰密碼體制。

2.3對稱與非對稱密碼體制比較

采用分組密碼、序列密碼等對稱密碼體制時,加解密雙方所用的密鑰都是秘密的,而且需要定期更換,新的密鑰總是要通過某種秘密渠道分配使用方,在傳遞的過程中,稍有不慎,就容易泄露。公鑰密碼加密密鑰通常是公開的,而解密密鑰是秘密的,由用戶自己保存,不需要往返交換和傳遞,大大減少了密鑰泄露的危險性。同時,在網(wǎng)絡(luò)通信中使用對稱密碼體制時,網(wǎng)絡(luò)內(nèi)任何兩個用戶都需要使用互不相同的密鑰,只有這樣,才能保證不被第三方竊聽,因而N個用戶就要使用N(N-1)/2個密鑰。

對稱密鑰技術(shù)由于其自身的局限性,無法提供數(shù)字簽名的功能。這是因為數(shù)字簽名是網(wǎng)絡(luò)應(yīng)用中表征人或機構(gòu)的真實性、唯一性和私有性的重要手段,而對稱密鑰技術(shù)中的密鑰至少需要在交互雙方之間共享,不滿足惟一性、私有性,無法用于實現(xiàn)數(shù)字簽名。相比之下,公鑰密碼技術(shù)由于存在一對公鑰和私鑰,私鑰可以表征惟一性和私有性,而且經(jīng)私鑰加密的數(shù)據(jù)只能用與之對應(yīng)的公鑰來驗證,其他人無法仿冒,因此廣泛用于實現(xiàn)網(wǎng)絡(luò)中的數(shù)字簽名服務(wù)。另外，公鑰密碼體制的一個重要優(yōu)點就是易于建立兩個相距遙遠的終端用戶間的密鑰信道，而不需要他們彼此見面或者使用在線認證服務(wù)，這正好克服了傳統(tǒng)對稱技術(shù)的缺點。

3公鑰密碼體制的研究現(xiàn)狀

近代公鑰密碼系統(tǒng)的研究中，其安全性都是基于難解的困難問題的。如：（1）大整數(shù)因子分解問題；（2）計算有限域的離散對數(shù)問題；（3）平方剩余問題;(4)橢圓曲線的離散對數(shù)問題等?；谶@些問題,各種公鑰密碼體制相繼研究出來，主要集中在以下的幾個方面：（1）RSA公鑰體制的研究；（2）橢圓曲線密碼體制ECC的研究；（3）各種公鑰密碼體制的研究（量子密碼，NTRU，基于辮群的密碼體制等；（4）數(shù)字簽名研究。在此，我們對幾個主要的密碼體制做個介紹。

3.1 RSA密碼體制

RSA密碼系統(tǒng)是較早提出的一種公開鑰密碼系統(tǒng)。RSA是建立在“大整數(shù)的素因子分解是困難問題”基礎(chǔ)上的,RSA算法的安全性基于RSA問題(開e次方根的問題),而RSA問題的困難性又依賴于整數(shù)分解的困難性。所以,RSA需要選擇合適的安全參數(shù)，才能保證RSA有足夠的中長期安全，所使用的RSA密鑰至少需要｜N｜=1024bit,且它的兩個素因子p和q的長度要相等。

具體的教科書式的RSA算法可簡單描述如下：公鑰（N,e）,私鑰d(滿足ed=1 mod （p-1）(q-1))；加密：c=me(mod N)；解密： m=cd(mod N)。兩個素數(shù)p和q不再需要,可以舍棄,但絕不能泄漏。加密消息m時,首先將它分成若干比N小的數(shù)據(jù)分組，對每個分組分別實施上述加解密過程，加密后的密文c,將由相同長度的分組ci組成。

當然，當可證明安全的概念引入后，這種教科書式的加密體制在實際應(yīng)用中證明是不安全的。目前，作為RSA加密標準的是RSA-OAEP方案。

3.2基于橢圓曲線離散對數(shù)的密碼體制[2]

橢圓曲線在代數(shù)學(xué)和幾何學(xué)上已有一百五十多年的研究歷史,有著復(fù)雜的數(shù)學(xué)背景,涉及到數(shù)論、群論和射影幾何等學(xué)科。1985年,N.Koblitz和V.Miller分別提出了橢圓曲線密碼體制(Elliptic Curve Cryptosystem,ECC),其安全性依賴于橢圓曲線群上離散對數(shù)問題(ECDLP)的難解性,即已知橢圓曲線上的點p和kp計算k的困難程度。不過在當時一直沒有像RSA等密碼系統(tǒng)一樣受到重視。但從現(xiàn)在來看,ECC是目前已知的公鑰密碼體制中,對每一比特所提供加密強度最高的一種體制,它具有安全性高、計算量小、存儲空間占用小、帶寬要求低等特點,這些優(yōu)點使得橢圓曲線公鑰密碼體制將應(yīng)用到越來越多的領(lǐng)域。如存儲空間小,這對于加密算法在IC卡上的應(yīng)用具有特別重要的意義,帶寬要求低使ECC在無線網(wǎng)絡(luò)領(lǐng)域具有廣泛的應(yīng)用前景。

目前,求解橢圓曲線離散對數(shù)問題(ECDLP)的算法主要有小步—大步法、Pollardρ方法、Pohlig-Hellman算法和MOV歸約攻擊等。在這些算法中,Pollardρ方法是目前求解一般ECDLP的最有效算法,它的時間復(fù)雜度為O(sqrt(πn/2))數(shù)級的。Wiene和Zuccherato將該算法時間復(fù)雜度改進為O(sqrt(πn)/2),Pollardρ算法可以并行實現(xiàn),使用r個處理器的運行時間大概是O(sqrt(πn)/2r)。但在使用ECC時,橢圓曲線的選擇上一定要避免超奇異曲線和奇異曲線,這兩種曲線是不宜用于密碼體制的橢圓曲線,它們的ECDLP相對容易,易遭到特定算法的攻擊。另外,ECDLP是否存在亞指數(shù)時間算法是有待證明的問題,因為它關(guān)系ECC未來的安全性。

4公鑰密碼學(xué)體制的應(yīng)用

公鑰密碼體制主要服務(wù)于以下幾個方面：（1）數(shù)據(jù)加密；（2）數(shù)字簽名、身份認證與識別；（3）密鑰分配。由于公鑰密碼體制用于數(shù)據(jù)加密的密鑰生成成本較高，其主要用于數(shù)字簽名和密鑰分配。當然,數(shù)字簽名和密鑰分配都有自己的研究體系,形成了各自的理論框架。目前數(shù)字簽名的研究內(nèi)容非常豐富,包括普通簽名和特殊簽名。特殊簽名有盲簽名、代理簽名、群簽名、不可否認簽名、公平盲簽名、門限簽名、具有消息恢復(fù)功能的簽名等,它與具體應(yīng)用環(huán)境密切相關(guān)。顯然,數(shù)字簽名的應(yīng)用涉及到法律問題,美國聯(lián)邦政府基于有限域上的離散對數(shù)問題制定了自己的數(shù)字簽名標準(DSS),部分州已制定了數(shù)字簽名法。數(shù)字簽名涉及的內(nèi)容非常豐富，也是近年來公鑰密碼學(xué)領(lǐng)域的主要研究熱點。

密鑰管理中還有一種很重要的技術(shù)就是秘密共享技術(shù),是由安全多方計算技術(shù)的引入而發(fā)展而來的一種分割秘密的技術(shù),目的是阻止秘密過于集中,自從1979年Shamir提出這種思想以來,秘密共享理論和技術(shù)達到了空前的發(fā)展和應(yīng)用,特別是其應(yīng)用至今人們?nèi)允株P(guān)注。我國學(xué)者在這些方面也做了一些跟蹤研究,發(fā)表了很多論文,按照X. 509標準實現(xiàn)了一些CA。但沒有聽說過哪個部門有制定數(shù)字簽名法的意向。目前人們關(guān)注的是數(shù)字簽名和密鑰分配的具體應(yīng)用以及潛信道的深入研究。

5結(jié)束語

公鑰密碼體制是非常重要的一種技術(shù)，它實現(xiàn)了數(shù)字簽名的概念，提供了對稱密鑰協(xié)定的切實可行的機制，使安全通信成為可能。密鑰對的思想也實現(xiàn)了其他的服務(wù)和協(xié)議，包括：機密性、數(shù)據(jù)完整性、安全偽隨機數(shù)發(fā)生器和零知識證明等[3]。

目前，公鑰密碼的重點研究方向，理論方面[4]：（1）用于設(shè)計公鑰密碼的新的數(shù)學(xué)模型和陷門單向函數(shù)的研究；（2）公鑰密碼的安全性評估問題,特別是橢圓曲線公鑰密碼的安全評估問題。應(yīng)用方面：（1）針對實際應(yīng)用環(huán)境的快速實現(xiàn)的公鑰密碼設(shè)計；（2）公鑰密碼在當今熱點技術(shù)如網(wǎng)絡(luò)安全、電子商務(wù)、PKI、信息及身份認證等中的應(yīng)用,這方面還將是持續(xù)研究熱點。

參考文獻：

[1]Wenbo Mao著,王繼林等譯.現(xiàn)代密碼學(xué)理論與實踐.北京：電子工業(yè)出版社，2004(7).

[2]卓澤朋等.公鑰密碼體制的現(xiàn)狀與發(fā)展[J].電腦知識與技術(shù)，2006(12).

[3]畢仁平.公鑰密碼體制綜述及展望[J].廣西輕工業(yè)，2007(4)：55-57.

[4]馮登國.國內(nèi)外密碼學(xué)研究現(xiàn)狀及發(fā)展趨勢[J].通信學(xué)報,2002,23(5):18-26.