公鑰密碼體制基本原理介紹及研究方向探索

◆郭東棟 杜文博 周浩

（北京奔馳汽車有限公司 北京 100176）

隨著通信、電子和計(jì)算機(jī)技術(shù)的進(jìn)步，密碼學(xué)得到前所未有的系統(tǒng)發(fā)展，1976 年Whitfield Diffie 和Martin E.Hellman 發(fā)表了奠定密碼學(xué)理論體系的論文《New Directions in Cryptography》，這為解決密碼學(xué)面臨的兩大難題（可靠密鑰的傳輸通道問題和如何提供與手寫簽名等效的認(rèn)證體系）提供了開拓性的理論基礎(chǔ)。此篇論文提出的公鑰密碼算法、公鑰分配算法、單項(xiàng)認(rèn)證算法等，為解決有效認(rèn)證問題提供了全新的思路；同時(shí)，此篇論文介紹的公鑰加密和數(shù)字簽名新構(gòu)想為今天公共密碼交換系統(tǒng)打下了堅(jiān)實(shí)的基礎(chǔ)，被廣泛應(yīng)用于當(dāng)前網(wǎng)絡(luò)通信和計(jì)算機(jī)安全。該論文的引用目前已經(jīng)超過16，000 次。兩位作者Whitfield Diffie 和Martin E.Hellman 因密碼學(xué)研究，獲得2015 年度的圖靈獎(jiǎng)。下面簡要地介紹一下這篇論文的主要內(nèi)容。

1 常規(guī)密碼體系

密碼學(xué)是研究解決保密和認(rèn)證這兩類安全問題的“數(shù)學(xué)”方法的學(xué)科，本質(zhì)上與數(shù)學(xué)學(xué)科存在千絲萬縷的關(guān)系。常規(guī)密碼體系主要包含密鑰、加密、解密等基本概念，現(xiàn)代密碼學(xué)主要基于數(shù)學(xué)理論和計(jì)算機(jī)科學(xué)實(shí)踐。密碼算法是圍繞計(jì)算難度假設(shè)進(jìn)行設(shè)計(jì)的，因此這種算法在實(shí)踐中很難被任何對手破壞。理論上有可能破壞這樣的系統(tǒng)，但是用任何已知的實(shí)際手段來破壞是不可行的。這些方案因此被稱為計(jì)算安全。理論上的進(jìn)步，例如整數(shù)因數(shù)分解算法的改進(jìn)，以及更快的計(jì)算技術(shù)，要求這些解決方案必須不斷調(diào)整。存在信息理論上安全的方案，即使使用無限制的計(jì)算能力也無法證明是可靠的，但是這些方案比最佳的理論上可破解但計(jì)算安全的機(jī)制在實(shí)踐中更難使用。同時(shí)，根據(jù)Shannon 理論，無條件安全的算法是存在的，但因?yàn)槠涿荑€過長而不符合實(shí)際應(yīng)用，這也是在計(jì)算上開發(fā)安全算法的原因。

2 公鑰密碼學(xué)

公鑰密碼的兩個(gè)主要組成部分是公鑰密碼和公鑰分發(fā)算法?！禢ew Directions in Cryptography》一文首次提出的設(shè)計(jì)方案充分體現(xiàn)了公鑰密碼的設(shè)計(jì)思想和實(shí)踐，即密鑰是由公鑰和私鑰組成，不再是機(jī)密內(nèi)容。解決復(fù)雜問題的步驟通常稱為算法，由明文生成密文的步驟是加密的步驟，稱為“加密算法”，解密的步驟稱為“解密算法”，解密算法統(tǒng)稱為密碼算法。密鑰交換的功能是允許雙方協(xié)商同一密鑰，而無須事先共享信息。此密鑰用于數(shù)據(jù)加密。公鑰密碼或非對稱密碼是一種使用密鑰對的密碼系統(tǒng)：可以廣泛傳播的公鑰和私鑰。這種密鑰的產(chǎn)生取決于基于數(shù)學(xué)問題的密碼算法以產(chǎn)生單向函數(shù)。有效的安全性只需要使私鑰保持機(jī)密即可。公鑰可以公開分發(fā)而不會損害安全性。在這樣的系統(tǒng)中，任何人都可以使用接收者的公鑰對消息進(jìn)行加密，但是只能使用接收者的私鑰對加密的消息進(jìn)行解密。

公鑰算法是現(xiàn)代密碼系統(tǒng)，應(yīng)用程序和協(xié)議中的基本安全成分，可確保電子通信和數(shù)據(jù)存儲的機(jī)密性，真實(shí)性和不可否認(rèn)性。它們支持各種Ⅰnternet 標(biāo)準(zhǔn)，例如傳輸層安全性（TLS），S/MⅠME，PGP 和GPG。一些公共密鑰算法提供了密鑰分發(fā)和保密性（例如，Diffie-Hellman 密鑰交換），一些提供了數(shù)字簽名（例如，數(shù)字簽名算法），而另一些提供了兩者（例如RSA）。

Diffie-Hellman 密鑰交換在兩方之間建立了一個(gè)共享的秘密，該秘密可用于秘密通信以通過公共網(wǎng)絡(luò)交換數(shù)據(jù)。一個(gè)類比通過使用顏色而不是非常大的數(shù)字來說明公共密鑰交換的概念：

該過程開始于讓兩方Alice 和Bob 商定一個(gè)不需要保密的任意起始顏色，但每次都應(yīng)有所不同。在此示例中，顏色為黃色。每個(gè)人還選擇自己保留的秘密顏色-在這種情況下，是紅色和藍(lán)綠色。該過程的關(guān)鍵部分是，Alice 和Bob 分別將自己的秘密顏色和彼此共享的顏色混合在一起，分別形成橙色棕褐色和淺藍(lán)色的混合物，然后公開交換兩種混合色。最后，這兩種顏色都將他們從伙伴那里收到的顏色與自己的私有顏色混合在一起。結(jié)果是最終配色（在這種情況下為黃棕色），與伙伴的最終配色相同。

公鑰加密是指在有限信息空間{M}上并基于算法{Ek}和{Dk}定義的可逆算法：

Ek：{M}->{M

Dk：{M}->{M

滿足下列條件：

（1）對任給K∈{K}，Ek 是Dk 的互逆變

（2）對任意的K∈{K}和M∈{M}，用Ek 和Dk 進(jìn)行加密和解密是容易計(jì)算

（3）對幾乎所有的K∈{K}，從Ek 推出Dk 在計(jì)算上是不可行

（4）對任意的K∈{K}，從K 計(jì)算Ek 和Dk 是可行

在此，K 是用于生成Ek 和Dk 的隨機(jī)數(shù)。第三個(gè)條件確保在不損害Dk 的安全性的情況下可以公開Ek，從而確保了公鑰密碼算法的安全性。矩陣求逆僅需n3 時(shí)間，密碼分析時(shí)間與正常解密時(shí)間之比為n。盡管此事例不切實(shí)際，但對于解釋公共密鑰密碼算法很有用。一種更實(shí)用的方法是使用機(jī)器語言的可理解性將加密算法編譯為機(jī)器語言并發(fā)布，而解密算法是機(jī)密的。分析人員很難理解機(jī)器語言的整個(gè)操作過程，因此很難破解。當(dāng)然，此算法必須足夠復(fù)雜，以避免被輸入和輸出對破解。

公鑰分配算法基于計(jì)算對數(shù)然后取模數(shù)的難度。令q 為質(zhì)數(shù)，取有限域GF（q）中的任何q，計(jì)算Y=axmod q，其中a 是GF（q）上的固定基元，然后X=log aYmod q。不難發(fā)現(xiàn)，從X 計(jì)算Y 更容易，這需要大約2×log2q 乘法。但是，由于需要q1/2 運(yùn)算，因此很難從Y 導(dǎo)出X。這樣，對于每個(gè)用戶，從[1，2，...，q-1]中隨機(jī)選擇一個(gè)q，計(jì)算出Yi=aXi mod q，并發(fā)布Yi，并對Xi 保密。然后，當(dāng)用戶i 和j 進(jìn)行通信時(shí)，請使用Kij=aXiXjmod q 作為其公共密鑰。該關(guān)鍵用戶i 是通過j 發(fā)布的Yj 獲得的，即Kij=Yj Ximod q=（aXj）Ximod q=aXiXjmod q。為了讓第三方獲得密鑰，必須對其進(jìn)行計(jì)算，而這在計(jì)算上是不可行的，以便實(shí)現(xiàn)在公共信道上分發(fā)私鑰的效果。

3 單向認(rèn)證

身份驗(yàn)證涉及驗(yàn)證個(gè)人身份文件，使用數(shù)字證書驗(yàn)證網(wǎng)站的真實(shí)性，通過碳日期確定工件的年齡或確保產(chǎn)品或文件不偽造?，F(xiàn)有的認(rèn)證體系只能保證不被第三方冒名頂替，但不能解決發(fā)送者和接收者之間的沖突，為此引入單向函數(shù)的概念，即對定義域中的任意x，f（x）是容易計(jì)算的，但對幾乎所有的值域中的y，求滿足y=f（x）的x在計(jì)算上是不可行的。例如已知多項(xiàng)式p（x）和x，求y=p（x）是容易的，但若已知y 求出x 是困難的。值得注意的是，這里的計(jì)算上不可逆與數(shù)學(xué)中的不可逆是完全不同的（數(shù)學(xué)上的不可逆可能是有多個(gè)原像）。

公鑰密碼算法可用來產(chǎn)生一個(gè)真正的單向認(rèn)證體系。當(dāng)用戶Alice 要發(fā)信息M 給用戶Bob 時(shí)，他用其保密的解密密鑰解密M 并傳給Bpb，Bob 收到時(shí)用Alice 公布的加密密鑰“加密”此消息從而得到信息M。因?yàn)榻饷苊荑€是保密的，只有Alice 發(fā)送的消息才具有這樣的性質(zhì)，從而確認(rèn)此信息來源于Alice，也就建立了一個(gè)單向認(rèn)證體系。

Leslie Lamport 還提出了另一種單向信息認(rèn)證方法，該方法通過在k 維二進(jìn)制空間中將單向函數(shù)f 映射到其自身來實(shí)現(xiàn)。如果發(fā)送方發(fā)送了N 位信息m，則他必須生成2N 個(gè)隨機(jī)的k 維二進(jìn)制矢量x1，X1，x2，X2，...xn，Xn，并將其保密，然后將這些矢量置于y1 之類的f 下，Y1，Y2，Y2，...yn，Yn 發(fā)送給接收者。當(dāng)發(fā)送信息m=（m1，m2，...，mN）時(shí)，當(dāng)m1=0 發(fā)送x1，m1=1 發(fā)送X1，以此類推。接收器用f 映射接收到的信息，如果它是y1，則m1=0，而Y1，則m1=1，然后獲得m。由于函數(shù)f 的單向性，接收者無法從y得出x，因此不能更改收到的任何收據(jù)。當(dāng)然，當(dāng)N 相對較大時(shí)，該方法的開銷非常大。因此，有必要引入單向映射g 來將N 位信息映射到n 位（n 大約為50），但是這里要求g 具有比一般單向函數(shù)更強(qiáng)的特性。

以Web 普遍使用的SSL 認(rèn)證為例，只有客戶端才能驗(yàn)證服務(wù)器以確保其從目標(biāo)服務(wù)器接收數(shù)據(jù)。為了實(shí)現(xiàn)單向SSL，服務(wù)器與客戶端共享其公共證書。

以下是在單向SSL 情況下在客戶端和服務(wù)器之間建立連接和數(shù)據(jù)傳輸所涉及的步驟的描述：

（1）客戶端通過HTTPS 協(xié)議從服務(wù)器請求一些受保護(hù)的數(shù)據(jù)。這將啟動SSL/TLS 握手過程。

（2）服務(wù)器將其公共證書以及服務(wù)器問候消息返回給客戶端。

（3）客戶端驗(yàn)證/驗(yàn)證接收到的證書?？蛻舳送ㄟ^證書頒發(fā)機(jī)構(gòu)（CA）驗(yàn)證CA 簽名證書的證書。

（4）SSL/TLS 客戶端發(fā)送一個(gè)隨機(jī)字節(jié)字符串，以便客戶機(jī)和服務(wù)器都可以計(jì)算用于加密后續(xù)消息數(shù)據(jù)的密鑰。隨機(jī)字節(jié)字符串本身使用服務(wù)器的公鑰加密。

（5）商定此秘密密鑰后，客戶端和服務(wù)器通過使用此密鑰對數(shù)據(jù)進(jìn)行加密/解密，進(jìn)一步交流實(shí)際數(shù)據(jù)傳輸。

4 問題的相關(guān)性和陷門

在1970 年代中期，Diffie，Hellman 和Merkle 提出了非對稱（或公共密鑰）加密技術(shù)后，陷門功能在加密技術(shù)中占據(jù)了重要地位。實(shí)際上，Diffie＆Hellman（1976）創(chuàng)造了這個(gè)詞。已經(jīng)提出了幾個(gè)函數(shù)類，并且很明顯，陷門函數(shù)比最初想象的要難找到。例如，早期的建議是使用基于子集和問題的方案，很快事實(shí)證明不適合。

安全地抵抗已知的明文攻擊的加密算法可以產(chǎn)生單向功能。假設(shè)：{P}->{K}就是這樣的算法，取P=P0，考慮映射f：{K}->{C}定義為f（x）=Sx（P0），則f 是單對函數(shù)而言，因?yàn)閒（x）是要獲得x且已知的明文攻擊是等效的（即已知的P=P0 和SK（P0）找不到K）。埃文斯還提出了另一種方法。他使用的映射為f（x）=Sx（X），這增加了破解的難度，但是這種單向功能違反了已知明文攻擊的安全要求，公鑰密碼算法可用于生成單向身份驗(yàn)證系統(tǒng)。

陷門加密算法是一種函數(shù)，它易于在一個(gè)方向上計(jì)算，但又在沒有特殊信息的情況下卻很難在相反方向上計(jì)算（找到其反函數(shù)）。陷門加密算法函數(shù)廣泛用于加密中，可用于生成公鑰分發(fā)算法。所謂的陷門密碼算法是指僅在已知陷門信息的情況下才能正確還原明文，并且在不掌握陷門信息的情況下破解明文在計(jì)算上是不可行的。

5 計(jì)算復(fù)雜性問題

在計(jì)算機(jī)科學(xué)中，算法的計(jì)算復(fù)雜性或簡單性就是運(yùn)行它所需的資源量，特別關(guān)注時(shí)間和內(nèi)存需求。最壞情況下的復(fù)雜性（大小為n的所有輸入上所需資源的最大值）或平均情況下的復(fù)雜性（大小為n的所有輸入上所需資源的平均值）。時(shí)間復(fù)雜度通常表示為大小為n的輸入上所需的基本運(yùn)算的次數(shù)，其中假定基本運(yùn)算在給定計(jì)算機(jī)上花費(fèi)固定的時(shí)間量，并且在不同的計(jì)算機(jī)上運(yùn)行時(shí)僅改變恒定的因子?？臻g復(fù)雜度通常表示為算法在大小為n 的輸入上所需的內(nèi)存量。

現(xiàn)代密碼算法的安全性基于計(jì)算的不可行性，因此有必要研究計(jì)算的復(fù)雜性。在確定性圖靈機(jī)上用多項(xiàng)式時(shí)間可以解決的問題定義為P 型復(fù)雜度，在不確定性圖靈機(jī)上用多項(xiàng)式時(shí)間可以解決的問題定義為NP 型復(fù)雜度。大多數(shù)加密算法現(xiàn)在都使用NP 完整集中的問題。密碼分析的難度如下：如果可以在P 時(shí)間內(nèi)完成加解密算法，則密碼分析的難度將不會大于NP 時(shí)間。

6 研究方向探索

在論文發(fā)表后，一系列公鑰密碼學(xué)的構(gòu)造破土而出，包括且不僅限于：公鑰加密（RSA、ElGamal、橢圓曲線、Rabin 等）、密鑰交換（Diffie-Hellman、橢圓曲線DH、RSA 等）、數(shù)字簽名（DSA、橢圓曲線DSA、RSA 等），更復(fù)雜的構(gòu)造包括：身份加密、屬性加密、功能加密、全同態(tài)加密等等。以上構(gòu)造充分應(yīng)用在系統(tǒng)的各個(gè)環(huán)節(jié)上，保護(hù)了信息和數(shù)據(jù)的安全，著名的RSA 算法就是第一個(gè)公鑰加密算法。

本文從各個(gè)角度介紹了密碼學(xué)的過去、現(xiàn)在和將來，詳細(xì)分析了公鑰密碼學(xué)的概念和常用算法，讓我們系統(tǒng)了解到關(guān)于密碼學(xué)的理論基礎(chǔ)。如何在現(xiàn)有密碼學(xué)的理論基礎(chǔ)上，發(fā)展密碼理論和創(chuàng)新密碼算法成為亟待研究的課題和方向。由于科技的發(fā)展和計(jì)算機(jī)網(wǎng)絡(luò)的進(jìn)步，不僅給密碼學(xué)的發(fā)展提供了前所未有的契機(jī)和條件，但是也為算法的復(fù)雜度進(jìn)行了更高的考驗(yàn)。計(jì)算機(jī)運(yùn)算能力的加強(qiáng)，使得原來復(fù)雜的算法已經(jīng)可以在有限的時(shí)間內(nèi)解決，這就需要我們進(jìn)行計(jì)算復(fù)雜度研究，創(chuàng)建更加復(fù)雜的算法，用以保證密碼的安全性。同時(shí)如何確保在公開的計(jì)算機(jī)網(wǎng)絡(luò)中安全地傳送和保管密鑰，確保密碼的安全性和隱私性，也是當(dāng)前面臨的嚴(yán)峻問題。

總結(jié)一下，這篇1976 年的論文對密碼學(xué)和信息安全產(chǎn)生了不可估量的影響，這使得一系列的算法、協(xié)議和應(yīng)用破土而出。正是這些數(shù)學(xué)家、密碼學(xué)家的貢獻(xiàn)才使得現(xiàn)在的一切變得可能。這些算法和協(xié)議在幕后默默精巧而準(zhǔn)確的運(yùn)行，保障了信息的保密、完整和可用。同時(shí)，計(jì)算機(jī)網(wǎng)絡(luò)通信技術(shù)的發(fā)展和信息時(shí)代的到來，使得密碼學(xué)仍然面臨著嚴(yán)峻的挑戰(zhàn)和難得的機(jī)遇。因此，在密碼學(xué)領(lǐng)域開展開拓性工作，努力開創(chuàng)密碼學(xué)發(fā)展的新時(shí)代，保護(hù)網(wǎng)絡(luò)信息的隱私和安全。