現代密碼算法研究

摘要：密碼技術是信息安全的核心技術。密碼技術主要包括對稱密碼算法和非對稱密碼算法及協議。對稱加密算法加密密鑰和解密密鑰相互推導容易，加/解密速度非常快，適用于大批量數據加密的場合。非對稱密鑰密碼體制從私有密鑰推導公開密鑰是計算不可行的，雖然公鑰加密算法在運行速度方面無法和對稱加密算法媲美，但很好地解決了對稱密碼學面臨的密鑰的分發與管理問題，同時對于數字簽名問題也給出了完美的解答。

關鍵詞：分組密碼；流密碼；Hash函數；非對稱密碼；密碼協議

Abstract: Technologies of cryptography are the core of information security. It mainly includes symmetric encryption algorithms and asymmetric cryptographic algorithms and protocols. For the symmetric encryption algorithm， it is easy to deduce decryption keys from the encryption keys and vice versa. Because this algorithm encrypts and decrypts data very quickly， it is applicable in situations where large numbers of data have to be protected. However， for the asymmetric algorithm， extracting the secret key from the public key is computationally infeasible. Although the performance speed of asymmetric encryption algorithm is much slower than that of the symmetric algorithm， the asymmetric algorithm has key management advantages over the symmetric one， and it generates signature of digital messages.

Key words: block cipher; stream cipher; Hash function; asymmetric cryptography; cryptographic protocol

信息安全本身包括的范圍很大，從安全性需求的角度來說涉及到信息的保密性、完整性、可用性、認證性和不可否認性。其中，密碼技術是保障信息安全的核心技術。

密碼學是一門充滿挑戰的交叉學科，有著悠久而迷人的歷史。4 000多年前就有埃及人運用簡單的加密手段傳遞秘密信息的記錄。在兩次世界大戰中，密碼學更是扮演了舉足輕重的角色。但是，早期密碼技術的研究和應用多屬于軍隊、外交和政府行為。20世紀60年代計算機與通信系統的迅猛發展，促使人們開始考慮如何通過計算機和通信網絡安全地完成各項事務，從而使得密碼技術開始廣泛應用于民間，也進一步促進了密碼技術的迅猛發展。

傳統密碼技術更多被看成是一門藝術，密碼學專家常常是憑自己的直覺來進行密碼算法的設計和分析。直到1949年Shannon[1]發表《保密系統的通信理論》一文，文章從信息論的角度討論了加密系統的安全性和設計準則，從此將密碼學從藝術帶入了系統科學的殿堂。20世紀70年代，IBM公司設計出數據加密標準(DES)分組密碼算法，并在1977年被美國聯邦政府采納為聯邦信息處理標準。幾乎同時，Diffie和Hellman[2]提出了公鑰密碼學的思想。他們在《密碼學的新方向》一文中解決了原有對稱密碼系統存在的密鑰分配問題，并提出了數字簽名的新思路。1978年，Rivest、Shamir和Aldleman[3]設計出了第一個在實踐中可用的公開密鑰加密和簽名方案——RSA，從而拉開了現代密碼學的序幕。

1 對稱加密算法

密碼算法主要分為對稱密碼算法和非對稱密碼算法兩大類。對稱加密算法指加密密鑰和解密密鑰相同，或知道密鑰之一很容易推導得到另一個密鑰。通常情況下，對稱密鑰加密算法的加/解密速度非常快，因此，這類算法適用于大批量數據加密的場合。這類算法又分為分組密碼和流密碼兩大類。

1.1 分組密碼

分組密碼算法如圖1所示。相對流密碼算法來說，分組密碼算法不需要存儲生成的密鑰序列，所以適用于存儲空間有限的加密場合。此外，目前使用的分組密碼算法的分析和設計過程都相對公開，通常伴隨著大型的征集和公開評估活動。這樣一來不僅僅增加了算法的透明度，防止攻擊者隱藏陷門并使得用戶充分相信算法的安全強度；另一方面極大促進了分組密碼技術的飛速發展。

1973年5月13日的美國聯邦政府提出征求在傳輸和存儲數據中保護計算機數據的密碼算法的建議，這一舉措最終導致了DES算法的研制。在公開征得的眾多算法中，IBM公司提出的算法Lucifer中選。1975年3月17日，美國國家標準局(NBS)首次公布了此算法，請公眾評議。1977年1月NBS正式向社會公布，采納IBM公司設計的方案作為非機密數據的數據加密標準。DES正式成為美國聯邦政府信息處理標準，即FIPS-46標準，同年7月15日開始生效。此后，每隔5年美國國家保密局(NSA)對DES作新的評估，并重新批準它是否繼續作為聯邦加密標準。

1997年，美國標準技術研究所(NIST)對DES進行再次評測并宣布：DES算法的安全強度已經不足以保障聯邦政府信息數據的安全性，所以NIST建議撤銷相關標準，此后DES算法只作為三重數據加密標準(TDES)的一個組成部分使用。同時，NIST開始征集新的數據加密標準高級數據加密標準(AES)[4]，他們要求新算法的分組長度為128，支持可變密鑰長度128、192、256比特。1998年，NIST在第一輪AES征集會議上公布了征集到的15個算法，并且邀請全世界的密碼研究機構對算法進行安全性等方面的評測。1999年，NIST從中選取了5個優良的算法作為AES的候選算法，它們分別是MARS、RC6、Rijndael、Serpent和Twofish，并通過最終的綜合評價確定Rijndael算法為新的數據加密標準，2001年12月正式公布FIPS-197標準。

歐洲于2000年1月啟動了NESSIE工程[5]，該工程的目的是評價出包含分組密碼、流密碼等在內的一系列安全、高效和靈活的密碼算法。至2000年9月，共收集到了17個分組密碼算法，同時他們將TDES和AES納入了評估范圍，并作為分組密碼算法的評測基準。經過3年2個階段的篩選，最終確定下列算法為推薦的分組密碼算法：MISTY164、Camllia128、SHACAL-2和AES128。

日本政府在2000年成立了密碼研究與評估委員會(CRYPTREC)[6]并參考歐洲NESSIE工程的作法對密碼算法的安全性和效率等問題進行評估，以備政府使用。評估涵蓋了對稱密碼算法、非對稱密碼算法、散列函數和隨機數生成器4部分。2002年初步擬定了推薦算法的草案，2003年3月確定了推薦算法名單，其中分組密碼算法包括：

分組長度為64比特的算法：CIPHERUNICORN-E、MISTY1[Ma00]和3-keyTDES。

分組長度為128比特的算法：Camellia、CIPHERUNICORN-A、SC2000、Hierocrypt-3和Rijndael128。

目前，分組密碼的設計與分析依然是密碼學研究的熱點。設計方面主要是尋求更好的設計技術在安全性和效率方面突破AES算法。分析方面主要是可證明安全性理論研究、應用安全性研究及新的攻擊方法挖掘。此外，利用分組密碼技術設計新的流密碼算法、新的Hash函數算法也是研究的熱點。

1.2 流密碼

流密碼(也叫序列密碼)的理論基礎是一次一密算法，它的主要原理是：生成與明文信息流同樣長度的隨機密鑰序列，使用該序列按比特加密信息流，得到密文序列，解密變換是加密變換的逆過程。根據Shannon的研究，這樣的算法可以達到完全保密的要求。但是，在現實生活中，生成完全隨機的密鑰序列是不可行的，因此只能生成一些類似隨機的密鑰序列，稱之為偽隨機序列。

流密碼內部存在記憶元件(存儲器)來存儲生成的密鑰序列。根據加密器中記憶元件的存儲狀態是否依賴于輸入的明文序列，又分為同步流密碼算法(如圖2所示)和自同步流密碼算法(如圖3所示)。

流密碼算法最初主要用于政府、軍方等國家要害部門，因此，流密碼不像分組密碼那樣有公開的國際標準，大多數設計、分析成果都是保密的。但是隨著流密碼的應用需求越來越廣泛，從NESSIE工程開始，流密碼算法的設計與分析也列上了公開征集評測的日程。

2000年1月歐洲啟動的NESSIE工程中，有6個流密碼算法(Leviathan、UIi-128、BMGL、SOBER-t32、SNOW、SOBER-tl)進入了第二階段評估，但是因為他們都不符合NESSIE的征集準則而最終全部落選。

2003年3月，日本政府的密碼研究與評估委員會(CRYPTREC)推薦了3個流密碼算法：MUGI、MULTI-S01和RC4-128。

ECRYPT[7]是歐洲第6框架研究計劃(FP6)下IST基金支持的一個為期4年的項目，該項目啟動于2004年2月，分為AZTEC、PROVILAB、VAMPIRE、STVL和WAVILA 5個部分。其中STVL正在進行流密碼算法的公開征集評估活動：2004年10月14—15日在比利時舉行了一個名為SASC的特別會議，會議的討論引發了流密碼算法的征集活動，并于2004年11月發布了征集公告，這也是對NESSIE沒有征集到流密碼算法的一個補充。征集活動到2005年4月29日結束，根據4個征集原則，一共征集到了34個流密碼算法。2007年4月開始進入第三輪評估，針對軟件設計的候選算法有CryptMT(Version3)、Dragon、Rabbit、HC(HC-128和HC-256)、LEX(LEX-128、LEX-192和LEX-256)、NLS(NLSv2加密)、Salsa20和SOSEMANUK。針對硬件設計的候選算法包括DECIM(DECIMv2和DECIM-128)、F-FCSR(F-FCSR-Hv2和F-FCSR-16)、Edon80、Grain(Grainv1和Grain-128)、MICKEY(MICKEY2.0和MICKEY-1282.0)、Moustique、Trivium和Pomaranch (Version 3) 。

對流密碼研究內容集中在如下兩方面：

(1)衡量密鑰流序列好壞的標準。通常，密鑰序列的檢驗標準采用Golomb的3點隨機性公設，除此之外，還需做進一步局部隨機性檢驗，包括頻率檢驗、序列檢驗、撲克檢驗、自相關檢驗和游程檢驗，以及反映序列不可預測性的復雜度測試等。但是，究竟什么樣的序列可以作為安全可靠的密鑰序列，還是一個未知的問題。

(2)構造線性復雜度高、周期大的密鑰流序列。當前最常用的密鑰序列產生器主要有：基于線性反饋移位寄存器的前饋序列產生器、非線性組合序列產生器、鐘控序列產生器、基于分組密碼技術的密鑰生成器等。

2 Hash函數

Hash函數(也稱雜湊函數、散列函數)就是把任意長的輸入消息串變化成固定長度的輸出“0”、“1”串的函數，輸出“0”、“1”串被稱為該消息的Hash值(或雜湊值)。一個比較安全的Hash函數應該至少滿足以下幾個條件：

輸出串長度至少為128比特，以抵抗生日攻擊。

對每一個給定的輸入，計算Hash值很容易(Hash算法的運行效率通常都很高)。

對給定的Hash函數，已知Hash值，得到相應的輸入消息串(求逆)是計算上不可行的。

對給定的Hash函數和一個隨機選擇的消息，找到另一個與該消息不同的消息使得它們Hash值相同(第二原像攻擊)是計算上不可行的。

對給定的Hash函數，找到兩個不同的輸入消息串使得它們的Hash值相同(即碰撞攻擊)實際計算上是不可行的。

Hash函數主要用于消息認證算法構造、口令保護、比特承諾協議、隨機數生成和數字簽名算法中。Hash函數算法有很多，最著名的主要有MD系列和SHA系列，一直以來，對于這些算法的安全性分析結果沒有很大突破，這給了人們足夠的信心相信它們是足夠安全的，并被廣泛應用于網絡通信協議當中。直到2004年，中國密碼學家王小云教授和她的團隊將MD4的碰撞攻擊復雜度時間降到手工可計算[8]；并將尋找MD5算法實際碰撞的復雜度和SHA-1算法碰撞的理論復雜度分別降為239和263 [9-10]。她們的出色工作，顛覆了這座堅固的大廈，也迫使眾多密碼學家重新評價目前Hash算法的安全強度，同時思考新的Hash函數算法設計方法。

NESSIE工程推薦使用的Hash算法有SHA-256/384/512和Whirlpool，日本密碼研究與評估委員會推薦使用的算法有SHA-1/256/384/512、 RIPEMD-160。

ECRYPT也在Hash算法研究方面舉辦了一系列活動。此外，NIST研究所將于2008年啟動新的Hash標準的征集活動。

3 非對稱密碼算法

非對稱密鑰密碼體制，即公開密鑰密碼體制指用戶有兩個密鑰，一個公開密鑰，一個私有密鑰，并且從私有密鑰推導公開密鑰是計算不可行的。公鑰加密算法在運行速度方面無法和對稱加密算法媲美，但是這一思想很好地解決了對稱密碼學面臨的密鑰的分發與管理問題，同時對于數字簽名問題也給出了完美的解答，并正在繼續產生許多新的，優秀的思想和方案。

3.1 基于CA的公鑰密碼

公鑰密碼算法設計的關鍵是存在多項式時間內不可解的困難問題。最早的也是目前使用最廣泛的公鑰加密和簽名方案是RSA算法，該算法的安全性基于大整數分解問題。

Diffie和Hellman提出的DH密鑰交換方案以及后來的數字簽名標準(DSS)和ElGamal加密算法多基于同離散對數問題相關的困難問題。此外，在基于離散對數問題的密碼算法中有一類特殊的算法——橢圓曲線和超橢圓曲線密碼學(ECC)。這類算法的優點是參數長度較短(見表1)可以達到較高的安全性，因此，非常適合在智能卡等存儲空間有限的密碼設備上使用。

在NESSIE工程中共推薦了3個數字簽名算法：ECDSA、RSA-PSS、SFLASH。2003年3月，日本政府的密碼研究與評估委員會推薦了兩個公鑰加密算法(RSAES-PKCS1-v1 5、RAS-OAEP)和4個數字簽名算法(ECDSA、RSASSA-PKCS1-v1 5、 DSA、RSA-PSS)。

歷經20多年的分析研究，密碼學家依然沒有徹底攻破基于整數分解和基于離散對數的經典算法，從而增強了人們對于這些算法的信心，但是這并不意味著公鑰加密和簽名算法的研究可以停滯不前了。首先，雖然在原始計算模型的假設下，目前為止最有效的分解因子解法和離散對數解法都是亞指數時間。但是離散對數問題和分解因子問題始終沒有被證明是多項式時間內不可解(NP)問題。其次，即使證明他們是NP問題，也不能確保相應的密碼算法是安全的，例如基于背包問題設計的密碼算法幾乎全軍覆沒。最后，在量子計算機問世后，這兩類問題將存在多項式時間解法[11]。所以，密碼學家一直在探尋新的、可以用于設計公鑰密碼算法的困難問題。目前研究比較廣泛的算法主要有如下幾種：基于編碼問題的公鑰密碼算法(McEliece，1978)、基于格問題的密碼算法(NTRU，1996)、多變量密碼系統(Multivariate PKC，1999)以及基于無限群理論的密碼算法(辮子群， 2000)等。

3.2 基于身份的公鑰密碼

基于身份的密碼學是由Shamir[12]于1984年提出。其主要思想是，系統中可以直接使用用戶的標識，如姓名、IP地址、電子郵件地址等作為用戶的公鑰。用戶的私鑰通過一個被稱作私鑰生成器(PKG)的可信任第三方計算分發給用戶。Shamir在提出這一思想的同時設計了一個基于身份的數字簽名方案。然而，直到2001年，Boneh等人[13]利用橢圓曲線的雙線性對才得到一個真正有效的基于身份的加密體制(IBE)。目前，基于身份的方案(包括基于身份的加密算法、簽名算法以及各種協議)不斷涌現出來。現階段，基于對的運算效率問題是亟需解決的問題，也是現在研究的熱門問題。

3.3 密碼協議

所謂協議，就是兩個或者兩個以上的參與者為完成某項特定的任務而采取的一系列步驟。密碼協議的參與者可能是可以信任的人，也可能是攻擊者。在網絡通信中最常用的基本的密碼協議按照其完成的功能可以分成以下3類：

(1)密鑰交換協議

參與協議的兩個或者多個實體之間建立共享的秘密，例如在一次通信中所使用的會話密鑰。協議可以采用對稱密碼體制，也可以采用非對稱密碼體制，例如Diffie-Hellman密鑰交換協議。日本政府的密碼研究與評估委員會推薦了3個密鑰交換協議(DH、ECDH、PSEC-KEM)。

(2)認證協議

認證協議中包括實體認證(身份認證)協議、消息認證協議、數據源認證和數據目的認證協議等，用來防止假冒、篡改、否認等攻擊。NESSIE工程中推薦了一個由法國的Ecole Normal Superieure大學和電信公司提交的鑒別方案GPS。

(3)解決特殊問題的安全協議

解決特殊問題的安全協議有電子選舉協議、電子錢幣協議、安全多方計算協議等。

ECRYPT的PROVI實驗室在密碼協議研究方面又劃分了3個研究小組：模型和定義小組，主要負責認證、密鑰協商、零知識和身份認證的研究；安全計算小組，主要負責高效的多方計算協議、實用協議的可證明安全性和安全協議的無條件安全性研究；合理密碼協議小組，主要負責密碼協議模型的定義和合理參與者的多方計算問題研究。ECRYPT于2007年3月和7月分別舉辦了相關的主題研討會。

密碼協議是許多分布式系統安全的基礎，因此，對協議的安全性進行分析和研究是一個重要的課題。造成協議存在安全缺陷的原因主要有兩個：一是協議設計者誤解或者采用了不恰當的技術；二是協議設計者對環境的安全需求研究不足。目前，對密碼協議進行分析的方法主要有兩大類：一類是攻擊檢驗方法；一類是形式化的分析方法。所謂攻擊檢驗方法就是搜集使用目前的對協議的有效攻擊方法，逐一對安全協議進行攻擊，檢驗安全協議是否具有抵抗這些攻擊的能力。這種分析方法是否奏效關鍵在于攻擊方法的選擇。形式化的分析方法是采用各種語言或者模型，為協議建立模型，并按照規定的假設和分析、驗證方法證明協議的安全性。目前，形式化的分析方法是研究的熱點，但是就其實用性來說，還沒有什么突破性的進展。

4 參考文獻

[1] SHANNON C E. Communication theory of secrecy systems [J]. Bell System Technical Journal， 1949， 28(4): 656-715.

[2] DIFFIE W， HELLMAN M. New irection in Cryptography [J]. IEEE Transactions on Information Theory， 1976，22(6):644-654.

[3] The RSA challenge numbers [EB/OL]. http://www.rsa.com/rsalabs/node.asp.

[4] AES Candidate algorithms [EB/OL]. http://csrcnistgov/encryption/aes/aes-homehtm#candidates.

[5] Linear cryptan alysis of reduced-round SAFER++ [EB/OL]. http://www.cryptonessie. org.

[6] 王秋麗. 世界三次大規模密碼算法評選活動介紹 [J]. 信息安全與通信保密， 2004(2):76-78.

[7] Network of excellence in cryptology [EB/OL]. http://www.ecrypt.eu.org.

[8] WANG Xiaoyun， FENG Dengguo， LAI Xuejia， et al. Collisions for Hash functions MD4， MD5， HAVAL-128 and RIPEMD [C]//Proceedings of Crypto'04， Aug 15-19，2004， Santa Barbara， CA，USA. Berlin，Germany: Springer-Verlag，2004.

[9] WANG Xiaoyun， YIN Yiqun， YU Hongbo. Finding collisions in the full SHA-1 [C]// Proceedings of Crypto'05， Aug 14-18，2005， Santa Barbara， CA，USA. Berlin， Germany: Springer-Verlag.2005.

[10] WANG Xiaoyun， YU Hongbo. How to break MD5 and other Hash functions [C]//Proceedings ofcrypto’05， Aug 14-18，2005， Santa Barbara， CA，USA. Berlin， Germany: Springer-Verlag.2005.

[11] SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer [J]. SIAM Journal on Computing， 1997，26(5):1484-1509.

[12] SHAMIR A. Identity-based cryptosystems and signature schemes [C]//Proceedings of CRYPTO '84， Aug 19-22，1984，Santa Barbara， CA，USA. Berlin， Germany: Springer-Verlag， 1984:47-53.

[13] BONEH D， FRANKLIN M. Identity-based encryption from the weil pairing [C]//Proceedings of CRYPTO’01， Aug， 19-23， 2001， Santa Barbara， CA，USA. Berlin， Germany: Springer-Verlag， 2001:213-229.

收稿日期：2007-07-17

鄭世慧，山東大學博士畢業，北京郵電大學信息工程學院博士后，主要研究領域為密碼算法的分析與設計。