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

◆郭東棟 杜文博 周浩

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

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

1 常規密碼體系

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

2 公鑰密碼學

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

公鑰算法是現代密碼系統，應用程序和協議中的基本安全成分，可確保電子通信和數據存儲的機密性，真實性和不可否認性。它們支持各種Ⅰnternet 標準，例如傳輸層安全性（TLS），S/MⅠME，PGP 和GPG。一些公共密鑰算法提供了密鑰分發和保密性（例如，Diffie-Hellman 密鑰交換），一些提供了數字簽名（例如，數字簽名算法），而另一些提供了兩者（例如RSA）。

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

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

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

Ek：{M}->{M

Dk：{M}->{M

滿足下列條件：

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

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

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

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

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

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

3 單向認證

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

公鑰密碼算法可用來產生一個真正的單向認證體系。當用戶Alice 要發信息M 給用戶Bob 時，他用其保密的解密密鑰解密M 并傳給Bpb，Bob 收到時用Alice 公布的加密密鑰“加密”此消息從而得到信息M。因為解密密鑰是保密的，只有Alice 發送的消息才具有這樣的性質，從而確認此信息來源于Alice，也就建立了一個單向認證體系。

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

以Web 普遍使用的SSL 認證為例，只有客戶端才能驗證服務器以確保其從目標服務器接收數據。為了實現單向SSL，服務器與客戶端共享其公共證書。

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

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

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

（3）客戶端驗證/驗證接收到的證書。客戶端通過證書頒發機構（CA）驗證CA 簽名證書的證書。

（4）SSL/TLS 客戶端發送一個隨機字節字符串，以便客戶機和服務器都可以計算用于加密后續消息數據的密鑰。隨機字節字符串本身使用服務器的公鑰加密。

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

4 問題的相關性和陷門

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

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

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

5 計算復雜性問題

在計算機科學中，算法的計算復雜性或簡單性就是運行它所需的資源量，特別關注時間和內存需求。最壞情況下的復雜性（大小為n的所有輸入上所需資源的最大值）或平均情況下的復雜性（大小為n的所有輸入上所需資源的平均值）。時間復雜度通常表示為大小為n的輸入上所需的基本運算的次數，其中假定基本運算在給定計算機上花費固定的時間量，并且在不同的計算機上運行時僅改變恒定的因子。空間復雜度通常表示為算法在大小為n 的輸入上所需的內存量。

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

6 研究方向探索

在論文發表后，一系列公鑰密碼學的構造破土而出，包括且不僅限于：公鑰加密（RSA、ElGamal、橢圓曲線、Rabin 等）、密鑰交換（Diffie-Hellman、橢圓曲線DH、RSA 等）、數字簽名（DSA、橢圓曲線DSA、RSA 等），更復雜的構造包括：身份加密、屬性加密、功能加密、全同態加密等等。以上構造充分應用在系統的各個環節上，保護了信息和數據的安全，著名的RSA 算法就是第一個公鑰加密算法。

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

總結一下，這篇1976 年的論文對密碼學和信息安全產生了不可估量的影響，這使得一系列的算法、協議和應用破土而出。正是這些數學家、密碼學家的貢獻才使得現在的一切變得可能。這些算法和協議在幕后默默精巧而準確的運行，保障了信息的保密、完整和可用。同時，計算機網絡通信技術的發展和信息時代的到來，使得密碼學仍然面臨著嚴峻的挑戰和難得的機遇。因此，在密碼學領域開展開拓性工作，努力開創密碼學發展的新時代，保護網絡信息的隱私和安全。