公鑰密碼體制總結(jié)及展望

1、公鑰密碼體制總結(jié)及展望摘要：計算機網(wǎng)絡(luò)的發(fā)展突飛猛進，與此同時產(chǎn)生了 公鑰密碼體制，本文重點介紹了當前公鑰密碼體制的幾種常 見的算法以及公鑰密碼體制的未來發(fā)展趨勢。關(guān)鍵詞公鑰密碼體制RSA DSA ECDSA SHA-1數(shù)字簽名 身份認證1引言公開密鑰密碼體制的概念是1976年由美國密碼學專家 狄匪(Diffie)和赫爾曼(Hellman)1提出的，有兩個重要的 原則：第一，要求在加密算法和公鑰都公開的前提下，其加 密的密文必須是安全的；第二，要求所有加密的人和掌握私 人秘密密鑰的解密人，他們的計算或處理都應比較簡單，但 對其他不掌握秘密密鑰的人，破譯應是極困難的。隨著計算 機網(wǎng)絡(luò)的發(fā)展，信息

2、保密性要求的日益提高，公鑰密碼算法 體現(xiàn)出了對稱密鑰加密算法不可替代的優(yōu)越性。近年來，公 鑰密碼加密體制和PKI、數(shù)字簽名、電子商務等技術(shù)相結(jié)合， 保證網(wǎng)上數(shù)據(jù)傳輸?shù)臋C密性、完整性、有效性、不可否認性， 在網(wǎng)絡(luò)安全及信息安全方面發(fā)揮了巨大的作用。本文詳細介 紹了公鑰密碼體制常用的算法及其所支持的服務。2公鑰密碼算法公鑰密碼算法中的密鑰依性質(zhì)劃分，可分為公鑰和私鑰 兩種。用戶或系統(tǒng)產(chǎn)生一對密鑰，將其中的一個公開，稱為 公鑰；另一個自己保留，稱為私鑰。任何獲悉用戶公鑰的人 都可用用戶的公鑰對信息進行加密與用戶實現(xiàn)安全信息交 互。由于公鑰與私鑰之間存在的依存關(guān)系，只有用戶本身才 能解密該信息，任何未

3、受授權(quán)用戶甚至信息的發(fā)送者都無法 將此信息解密。在近代公鑰密碼系統(tǒng)的研究中，其安全性都 是基于難解的可計算問題的。如：（1）大數(shù)分解問題；（2）計算有限域的離散對數(shù)問題；（3） 平方剩余問題；（4）橢圓曲線的對數(shù)問題等。基于這些問題，于是就有了各種公鑰密碼體制。關(guān)于公 鑰密碼有眾多的研究，主要集中在以下的幾個方面：（1）RSA公鑰體制的研究；（2）橢圓曲線密碼體制的研 究；（3）各種公鑰密碼體制的研究；（4）數(shù)字簽名研究。公鑰加密體制具有以下優(yōu)點：（1）密鑰分配簡單；（2）密鑰的保存量少；（3）可以滿足 互不相識的人之間進行私人談話時的保密性要求；（4）可以 完成數(shù)字簽名和數(shù)字鑒別。RSA算法

4、RSA 算法2是 Ron Rivest, Adi Shamir 和 Len Adleman 在1978年提出的，是一種公認十分安全的公鑰密碼算法。 RSA算法是目前網(wǎng)絡(luò)上進行保密通信和數(shù)字簽名的最有效安 全算法。RSA算法的安全性基于數(shù)論中大素數(shù)分解的困難性。所以，RSA需采用足夠大的整數(shù)。因子分解越困難，密碼就 越難以破譯，加密強度就越高。其公開密鑰和私人密鑰是一 對大素數(shù)的函數(shù)。從一個公開密鑰和密文中恢復出明文的難 度等價于分解兩個大素數(shù)之積。因式分解理論的研究現(xiàn)狀表 明：所使用的RSA密鑰至少需要1024比特，才能保證有足 夠的中長期安全。為了產(chǎn)生兩個密鑰，選取兩個大素數(shù)p和q。為了獲得

5、 最大程度的安全性，兩數(shù)的長度一樣。計算乘積：N=pq，然 后隨機選取加密密鑰。，使。和互素。最后用歐幾里得擴展 算法計算解密密鑰d，以滿足：ed=1mod則d=e-1mod注意： d和n也互素。e和n是公開密鑰，d是私人密鑰。兩個素數(shù) p和q不再需要，可以舍棄，但絕不能泄漏。加密消息m時，首先將它分成比n份小的數(shù)據(jù)分組。加 密后的密文c，將由相同長度的分組ci組成。加密公式可表 示為：ci=mie X(mod n)解密消息時，取每一個加密后的 分組 ci 并計算：mi= cdi X (mod n)。由于：cdi= (mei ) d= medi = mi k (p - 1) (q- 1) +

6、1= m iXm i k (p - 1) (q- 1)= m i X1= m i (mod n)這 個公式能恢復出全部明文。公開密鑰n：兩個素數(shù)p和q的 乘積；e：與互素。私人密鑰d：與n互素。加密c=me X (mod n)；解密 m=cdX (mod n)。ECDSA 算法橢圓曲線數(shù)字簽名算法(ECDSA) 5設(shè)計的數(shù)學原理是 基于橢圓曲線離散對數(shù)問題的難解性。EC點上離散對數(shù)的研 究現(xiàn)狀表明:所使用的ECDSA密鑰至少需要192比特,才能保 證有足夠的中長期安全。橢圓曲線是指由韋爾斯特拉斯 (Weierstrass)方程：y2+a1xy+a3y=x3+a2x2+a4x+a6所確定的平面曲

7、線。定義F為一個域，其中aiF,i = 1,2,6。F可為有理解域、實數(shù)域、復數(shù)域，也可為有 限域GF(q)。在橢圓曲線密碼體制中，F(xiàn) 一般為有限域。由 有限域橢圓曲線上的所有點外加無窮遠點組成的集合，連同 按照“弦切法”所定義的加法運算構(gòu)成一個有限Abel群。 在此有限Abel群上，定義標量乘法(Scalar Multiplication) 為：mP = P+P+P(m 個 P 相加)；若 mP = Q,定義：m=logpQ 為橢圓曲線點群上的離散對數(shù)問題，此問題無多項式時間內(nèi) 的求解算法。ECDSA的設(shè)計正是基于這一問題的難解性。在此，我們討論定義在有限域GF(2m)上的橢圓曲線數(shù)字 簽名

8、算法。今定義橢圓曲線方程為：y2+xy = x3+ax2+b a,b GF(2m)；則橢圓曲線的域參數(shù)為D(m,f(x),a,b,P,n)其中,f(x)為GF(2m)的多項式基表示的不可約多項式。P 表示橢圓曲線上的一個基點，n為素數(shù)且為點G的階。ECDSA算法密鑰對的生成過程為：在區(qū)間1, n-1上選 擇一個隨機數(shù)d,計算Q = dP,則Q為公鑰，d為私鑰。ECDSA算法的簽名生成過程可簡述如下：若簽名的消息 為e,則在區(qū)間1, n-1上選擇一個隨機數(shù)k,計算kG=(xl, y1) ； r = xl mod n； s = k-1(e+dr) mod 口。如果 r 或 s 為 零，則重新計算，

9、否則生成的簽名信息為(r,s)。ECDSA算法的簽名驗證過程可簡述如下：若公鑰為Q, 簽名的消息為e計算：w = s-1 mod n ； u1 = ew mod n ； u2 = rw mod n ； X = u1P + u2Q=(xl, y1)。如果 X 為無窮 遠點，則拒絕簽名，否則計算：v = xl mod n；如果v = r, 則接受簽名，否則拒絕簽名。SHA-1 算法SHA-1雜湊算法4起初是針對DSA算法而設(shè)計的，其設(shè) 計原理與Ron Rivest提出的MD2, MD4,尤其是MD5雜湊函 數(shù)的設(shè)計原理類似。當輸入長度264bit的消息時，輸出 160bit的摘要，其算法分為5步：

10、(1)填充消息使其長度為512的倍數(shù)減去64,填充的方 法是添一個“1”在消息后，然后添加“0”直至達到要求的 長度，要求至少1位，至多512位填充位；(2)完成第1步后，在新得到的消息后附加上64bit填 充前的消息長度值；(3)初始化緩存，SHA-1用5字的緩存，每個字均是 32bit；(4)進入消息處理主循環(huán)，一次循環(huán)處理512bit,主循環(huán)有4輪，每輪20次操作;(5)循環(huán)結(jié)束后，得到的輸出值即為所求。3公鑰密碼的服務數(shù)據(jù)加密一般說來，公鑰密碼中的計算是很慢的，以至于在很多 情況下是不可行的?？梢杂靡粋€兩步過程來代替。(1)用隨機生成的對稱密鑰來加密數(shù)據(jù)。(2)用授權(quán)接收者的公鑰來加密

11、這個對稱密鑰。當授權(quán)接收者收到加過密的數(shù)據(jù)后，也采取一個類似的 兩步過程：(1)授權(quán)接收者用自己的私鑰來解出對稱密鑰。(2)接著用對稱密鑰進行解密獲得原始數(shù)據(jù)。數(shù)字簽名數(shù)字簽名在公鑰密碼體制下是很容易獲得的一種服務， 但在對稱密碼體制下很難獲得。數(shù)字簽名從根本上說是依靠 密鑰對的概念。發(fā)送方必須擁有一個只有自己知道的私鑰， 這樣當他簽名一些數(shù)據(jù)時，這些數(shù)據(jù)唯一而又明確地和他聯(lián) 系在一起，同時，應該有一個或更多實體都知道的公鑰，以 便大家驗證，并確認簽名是發(fā)送方的。因此，可以把數(shù)字簽 名操作看作是在數(shù)據(jù)上的私鑰操作。整個簽名操作就是一個 兩步過程：(1)簽名者通過雜湊函數(shù)把數(shù)據(jù)變成固定大小。(2

12、)簽名者把雜湊后的結(jié)果用于私鑰操作。驗證操作也是一個類似的兩步過程：(1)驗證者通過雜湊函數(shù)把數(shù)據(jù)變成固定大小。(2)驗證者檢查雜湊后的結(jié)果，傳輸來的簽名，如果傳 輸來的簽名用公鑰解密后的結(jié)果和驗證者計算的雜湊結(jié)果 相匹配，簽名就被驗證，否則，驗證失敗。從而，數(shù)字簽名不僅提供了數(shù)據(jù)起源認證服務，還有數(shù) 據(jù)完整性及不可否認性的服務。密鑰的建立公鑰密碼體制也可以用來實現(xiàn)兩個實體間的密鑰建立 的功能，也就是說，一個協(xié)議用到公鑰和私鑰，協(xié)議的結(jié)果 是兩個實體共享一個對稱密鑰，而這個密鑰不為其他的實體 所知。密鑰的建立可以通過以下兩種途徑：(1)密鑰傳遞：一個實體產(chǎn)生一個對稱密鑰送給其他的 實體，公鑰密

13、碼體制可以用來保證傳送的機密性。如發(fā)送方 用接收方的公鑰來加密對稱密鑰，使得只有接收方才能得 到。(2)密鑰協(xié)定：兩個實體共同來完成對稱密鑰的產(chǎn)生， 公鑰密碼體制把這個過程變得相對簡單。如Diffie-Hellman 6體制是第一個利用公鑰密碼的特點來選取雙方共同約定 的對稱密碼體制中密鑰的方案。其具體方法如下：假設(shè)Alice和Bob兩個用戶打算選取 一個高階有限域Zp中某一個數(shù)作為會話密鑰。設(shè)P是一個 質(zhì)數(shù)，g是P的一個本原元：0 a P,當k= 1,2，,P-1時 gKmod P的值，可以使1,2，,P-1中的每一狀態(tài)都出現(xiàn)一 次。選定g和P,由網(wǎng)絡(luò)中的所有用戶和主機共享。Alice和 B

14、ob可以通過如下的交換過程建立相同的密鑰：Alice隨機選取整數(shù)a (1aP-1)予以保密，并計 算 Qa=gamod PZp；Bob隨機選取整數(shù)b (1bp-1)予以保密，并計算 Qb=gbmod PZp；Alice 將 Qa 傳送給 Bob,而 Bob 將 Qb 傳送 Alice；Alice 收到 Qb 后，計算 K=Qbamod PZp； Bob 收 到 Qa 后，計算 K=Qabmod PZp；則KEZp就可作為Alice和Bob所使用對稱密碼體制 中的密鑰。3.4身份標識和認證在對稱密碼環(huán)境下，通信雙方的身份認證是十分困難 的，這就成了推動公鑰密碼體制發(fā)展的巨大動力之一。通信 或交易

15、時，應該保證信息的接收方和發(fā)送方能夠被唯一地標 識出來，讓通信雙方都能夠知道信息從哪里來或者到哪里 去。我們也將這種安全保障簡稱為真實性。按照被驗證對象 可以將真實性問題分成三種，一種是設(shè)備真實性，其二是人 的真實性，其三是信息的真實性。通過主機地址，主機名稱， 擁有者的口令等都在一定的程度上保證了對設(shè)備的驗證，但 都不能很好地滿足安全的要求。非對稱算法或數(shù)字簽名是人 員、設(shè)備或信息驗證的一種好方法。原理上說，沒有人能夠 假冒數(shù)字簽名?；诠€體制的身份認證主要利用數(shù)字簽名 和hash函數(shù)實現(xiàn)。設(shè)A對信息M的hash值H(M)的簽名 為SigSA(H(M),其中SA為A的私鑰.A將M及SigS

16、A (H(M)發(fā)送給用戶B。B通過A的公鑰PA進行解密：PA的完整性得到保障。(2)公鑰以一種可信的方式和它的聲稱者綁定在一起。公私證書機制很好的解決了通信雙方相互確定身份的 問題。4結(jié)束語公鑰密碼體制是非常重要的一種技術(shù)，它實現(xiàn)了數(shù)字簽 名的概念，提供了對稱密鑰協(xié)定的切實可行的機制，使安全 通信成為可能。密鑰對的思想也實現(xiàn)了其他的服務和協(xié)議， 包括：機密性、數(shù)據(jù)完整性、安全偽隨機數(shù)發(fā)生器和零知識 證明等。目前，公鑰密碼的重點研究方向，理論方面7:(1)用于設(shè)計公鑰密碼的新的數(shù)學模型和陷門單向函數(shù) 的研究；(2)公鑰密碼的安全性評估問題，特別是橢圓曲線公鑰 密碼的安全性評估問題。應用方面:(1

17、)針對實際應用環(huán)境的快速實現(xiàn)的公鑰密碼設(shè)計；(2)公鑰密碼在當今熱點技術(shù)如網(wǎng)絡(luò)安全、電子商務、 PKI、信息及身份認證等中的應用，這方面還將是持續(xù)研究 熱點。參考文獻Diffie, W.and M.Hellman. New directions in Cryptography. IEEE Transactions on Information Theory 22(1976):644-654.Rivest R , Shamir A , Adleman L. A method for obtaining digitalsignatures andpublic-keycryptosystemsJ.Communicationsof theACM,1976 ,21 (2) :120-126.3譚凱軍，諸鴻文，顧尚杰.基于數(shù)字簽名方案 DSS/DSA的幾種應用方案J.計算機研究與發(fā) 展.1999,36(5):632-638.4吳世忠，祝世雄等.應用密碼學-協(xié)議、算法與C源 程序M.機械工業(yè)出版社,XX.M J B Robshaw, Yiqun Lisa Yin. Elliptic Curve Cryptosystems. An RSA laborat