公鑰/私鑰（Public Key/Private Key）

公鑰密碼學（也稱為非對稱密碼學）是使用一對相關密鑰的加密系統領域。每對密鑰由一個公鑰和一個對應的私鑰組成。密鑰對是通過基於數學問題的加密算法生成的，這些數學問題被稱為單向函數。公鑰密碼學的安全性依賴於保持私鑰的機密性；公鑰可以公開分發而不危及安全性。公鑰密碼學有多種類型，每種類型具有不同的安全目標，包括數字簽名、Diffie-Hellman密鑰交換、公鑰封裝和公鑰加密。

公鑰算法是現代密碼系統中的基礎安全原語，包括提供電子通信和數據存儲保密性與真實性保證的應用和協議。它們是眾多互聯網標準的基礎，如傳輸層安全協議（TLS）、SSH、S/MIME和PGP。與對稱密碼學相比，公鑰密碼學在許多用途上可能過於緩慢，因此這些協議通常將對稱密碼學與公鑰密碼學結合使用，形成混合密碼系統。

概述

在1970年代中期之前，所有的密碼系統都使用對稱密鑰算法，其中發送方和接收方都使用相同的密鑰與基礎算法進行加密，且必須保持密鑰的機密性。每個這樣的系統中的密鑰都必須在使用系統之前以某種安全的方式在通信方之間交換——例如通過安全通道。這一要求從來不是簡單的，且隨着參與者數量的增加，或者在沒有安全通道的情況下，或者在（作為合理的加密實踐）頻繁更換密鑰時，這一問題很快變得不可管理。特別是，如果消息需要對其他用戶保持安全，則需要為每對用戶提供單獨的密鑰。

與此相比，在公鑰密碼系統中，公鑰可以廣泛且公開地傳播，只有相應的私鑰需要保持機密。

公鑰密碼學中最著名的兩種類型是數字簽名和公鑰加密：

1. 數字簽名系統：發送方可以使用私鑰和消息一起生成簽名。任何擁有相應公鑰的人都可以驗證簽名是否與消息匹配，但無法知道私鑰的偽造者無法找到任何可以通過公鑰驗證的消息/簽名對。例如，軟件發布者可以創建一個簽名密鑰對，並將公鑰包含在安裝在計算機上的軟件中。後來，發布者可以使用私鑰簽名軟件更新，任何收到更新的計算機都可以通過使用公鑰驗證簽名來確認更新的真實性。只要軟件發布者保持私鑰的機密性，即使偽造者分發惡意更新到計算機，它們也無法說服計算機認為惡意更新是真實的。
2. 公鑰加密系統：任何擁有公鑰的人都可以加密消息，得到密文，但只有知道相應私鑰的人才能解密密文以獲得原始消息。例如，一名記者可以在網站上發布加密密鑰對的公鑰，以便來源能夠以密文的形式向新聞機構發送機密消息。只有知道相應私鑰的記者才能解密密文以獲取來源的消息——一個監聽者在郵件傳輸過程中無法解密密文。然而，公鑰加密本身並不隱藏元數據，例如來源使用了哪個計算機發送消息，何時發送的消息，以及消息有多長。公鑰加密本身也不會告訴接收者是誰發送了消息——它只隱藏了消息的內容。

一個重要的問題是如何確保/證明特定的公鑰是可信的，即它是正確的並且屬於聲稱的個人或實體，且沒有被篡改或被某個（可能是惡意的）第三方替換。可以採取幾種方法，包括：

1. 公鑰基礎設施（PKI），其中一個或多個第三方——稱為證書頒發機構（CA）——對密鑰對的所有權進行認證。TLS就依賴於此。這意味着PKI系統（包括軟件、硬件和管理）必須得到所有參與方的信任。
2. 信任網絡（Web of Trust）通過使用個體對用戶與其公鑰之間鏈接的推薦來實現去中心化認證。PGP使用這種方法，此外還查找域名系統（DNS）。用於數字簽名電子郵件的DKIM系統也使用這種方法。

應用

公鑰加密系統的最明顯應用是加密通信以提供機密性——發送方使用接收方的公鑰加密消息，而該消息只能通過接收方配對的私鑰解密。

公鑰密碼學的另一個應用是數字簽名。數字簽名方案可用於發送方身份驗證。

不可否認系統使用數字簽名來確保一方無法成功否認其對文檔或通信的創作。

在此基礎上構建的其他應用包括：數字現金、密碼認證密鑰協議、時間戳服務和不可否認協議。

混合密碼系統

由於非對稱密鑰算法通常比對稱密鑰算法計算量大得多，因此常用公私鑰非對稱密鑰交換算法來加密和交換對稱密鑰，之後使用對稱密鑰密碼學來傳輸數據，採用現已共享的對稱密鑰進行對稱密鑰加密算法。PGP、SSH 和 SSL/TLS 系列協議都採用了這種程序，因此它們被稱為混合密碼系統。最初基於非對稱密碼學的密鑰交換，用於從服務器到客戶端共享服務器生成的對稱密鑰，具有不需要手動預共享對稱密鑰（例如通過印刷的紙張或由快遞員運送的磁盤）這一優點，同時在共享連接的其餘部分，提供比非對稱密鑰加密更高的數據吞吐量。

弱點

公鑰加密系統有許多潛在的安全弱點。除了選擇不合適的非對稱密鑰算法（目前只有少數幾種被廣泛認為是滿意的）或密鑰長度過短外，主要的安全風險是密鑰對中的私鑰被泄露。一旦私鑰泄露，消息安全、身份驗證等都將喪失。

此外，隨着量子計算的發展，許多非對稱密鑰算法被認為容易受到攻擊，因此正在開發新的抗量子攻擊的加密方案。

算法

所有公鑰方案理論上都可能遭受「暴力破解密鑰攻擊」。然而，只有當破解所需的計算量（由Claude Shannon稱為「工作量」）超出所有潛在攻擊者的計算能力時，這種攻擊才變得不可行。在許多情況下，工作量可以通過選擇更長的密鑰來增加。但其他算法可能固有地具有更低的工作量，使得抗暴力攻擊的能力（例如，使用更長的密鑰）變得無關緊要。一些特定的算法已經被開發出來，專門用於攻擊某些公鑰加密算法；例如，RSA和ElGamal加密算法都有已知的攻擊方法，其速度比暴力破解方法要快。但這些攻擊方法尚未得到實質性的改進，因此並不實用。

一些曾經被認為很有前景的非對稱密鑰算法已被發現存在重大漏洞。例如，「背包打包」算法在新的攻擊方法出現後被證明不安全。像所有加密功能一樣，公鑰的實現可能容易受到側信道攻擊，這些攻擊通過利用信息泄露來簡化秘密密鑰的搜索。這些攻擊往往與所使用的算法無關。目前正在進行研究，以發現並防範新的攻擊。

公鑰篡改

使用非對稱密鑰的另一個潛在安全漏洞是「中間人攻擊」，即第三方（「中間人」）攔截公鑰的通信並修改它們，提供不同的公鑰。然後，攻擊者必須攔截、解密並重新加密加密的消息和響應，使用正確的公鑰來避免引起懷疑。

通信被認為是不安全的，尤其是當數據傳輸的方式使得數據容易被攔截（也稱為「嗅探」）時。這些術語指的是讀取發送者的私密數據。通信特別不安全的情況是攔截無法被發送者預防或監控時。

儘管實施「中間人攻擊」可能困難，因為現代安全協議的複雜性，然而，當發送方使用不安全的媒體（如公共網絡、互聯網或無線通信）時，攻擊者可以通過妥協通信基礎設施而不是數據本身來簡化攻擊。舉例來說，一個惡意的互聯網服務提供商（ISP）員工可能會發現實施中間人攻擊相對簡單。捕獲公鑰只需要在ISP的通信硬件中搜索公鑰；如果非對稱密鑰方案得當實現，這不會構成重大風險。

在一些高級的中間人攻擊中，一方會看到原始數據，而另一方會收到惡意變體。非對稱的中間人攻擊可以使用戶無法意識到其連接已經被破壞，即使其中一個用戶的數據已經被泄露，因為對方看到的數據仍然正常。這可能導致用戶之間的混亂爭論，比如「肯定是你那邊的問題！」但實際上沒有一方有錯。因此，只有當通信基礎設施由一方或雙方完全控制時，中間人攻擊才是完全可防止的；例如通過發送方自己建築內的有線路線。總之，當攻擊者控制了發送方使用的通信硬件時，公鑰更容易被篡改。

公鑰基礎設施（PKI）

一種防止這類攻擊的方法是使用公鑰基礎設施（PKI）；這是一個包含角色、政策和程序的體系，旨在創建、管理、分發、使用、存儲和撤銷數字證書，並管理公鑰加密。然而，PKI也有潛在的弱點。

例如，頒發證書的證書頒發機構（CA）必須得到所有參與方的信任，確認它已經正確驗證了密鑰持有者的身份，確保在頒發證書時公鑰是正確的，並且免於計算機黑客攻擊。此外，所有參與方都必須事先安排好，檢查他們的所有證書，才能開始受保護的通信。例如，Web瀏覽器通常會接受一個由PKI提供者頒發的自簽名身份證書列表——這些證書用於驗證證書頒發機構的合法性，然後，第二步檢查潛在通訊者的證書。如果攻擊者能夠顛覆證書頒發機構，使其為一個虛假的公鑰頒發證書，那麼他們就可以發起一個「中間人攻擊」，就像完全不使用證書方案一樣容易。如果攻擊者滲透了證書頒發機構的服務器並獲取了其證書和密鑰（公鑰和私鑰）存儲，那麼他們將能夠偽造、偽裝、解密並偽造交易，只要他們能夠將自己置於通信流中。

儘管存在理論上的潛在問題，公鑰基礎設施仍然被廣泛使用。例如，TLS及其前身SSL常用於提供Web瀏覽器交易的安全（例如，大多數網站使用TLS進行HTTPS通信）。

除了特定密鑰對的抗攻擊能力外，在部署公鑰系統時還必須考慮證書層次的安全性。一些證書頒發機構——通常是一個運行在服務器計算機上的專用程序——為特定私鑰分配的身份提供擔保，生成數字證書。公鑰數字證書通常有效期為幾年，因此相關的私鑰在這段時間內必須保持安全。當用於創建更高層次PKI服務器證書的私鑰被泄露或意外披露時，就可能發生「中間人攻擊」，使得任何下級證書完全不安全。

未加密的元數據

大多數現有的公鑰加密軟件不會隱藏消息頭中的元數據，這可能包括發送者和接收者的身份、發送日期、主題字段以及他們使用的軟件等信息。相反，只有消息的正文被隱藏，只有目標接收者的私鑰才能解密該消息。這意味着，第三方可以構建一個非常詳細的通信網絡模型，了解討論的主題，即使消息內容本身被隱藏。

然而，最近有展示加密消息頭的技術，能夠隱藏發送者和接收者的身份，並大大減少第三方可用的元數據。這個概念基於一個公開的倉庫，其中包含分別加密的元數據塊和加密的消息。只有目標接收者才能解密元數據塊，並在解密後下載並解密他們的消息。目前，這種消息系統還處於實驗階段，尚未部署。擴展這一方法將只向第三方顯示接收者所用的郵箱服務器和發送和接收的時間戳。該服務器可以由成千上萬的用戶共享，從而使得社交網絡建模變得更加困難。

發展歷程

在密碼學的早期歷史中，兩個通信方依賴於一種通過安全但非加密的方法交換密鑰，比如面對面會面或通過可信的信使。這把密鑰，雙方必須絕對保密，然後用它來交換加密信息。這種分發密鑰的方法會帶來許多實際的困難。

預見

在他1874年的著作《科學原理》中，威廉·斯坦利·傑文斯寫道：

讀者能說出哪兩個數字相乘會得到8616460799嗎？我認為除了我自己，沒有人能知道。

在這裡，他描述了單向函數與密碼學的關係，並進一步討論了用於創建陷門函數的因式分解問題。1996年7月，數學家所羅門·W·戈洛姆說：「傑文斯預見了RSA公鑰密碼學算法的一個關鍵特徵，儘管他當然沒有發明公鑰密碼學的概念。」

保密發現

1970年，英國政府通信總部（GCHQ）的密碼學家詹姆斯·H·埃利斯提出了「非保密加密」（現在稱為公鑰密碼學）的可能性，但他看不出如何實現它。

1973年，他的同事克利福德·科克斯實現了後來成為RSA加密算法的方案，提供了一種「非保密加密」的實用方法。1974年，另一位GCHQ的數學家和密碼學家馬爾科姆·J·威廉姆森開發了現在被稱為Diffie–Hellman密鑰交換的方案。該方案也被傳遞給了美國國家安全局（NSA）。這兩個機構都有軍事重點，在任何情況下可用的計算能力也很有限；因此，公鑰密碼學的潛力仍未被這兩個機構實現：

我認為它對軍事用途非常重要...如果你可以快速且電子地共享密鑰，你就能比對手獲得重大優勢。直到從伯納斯-李為CERN設計開放互聯網架構，經過其對ARPANET的適配和採納，公鑰密碼學才真正實現了它的全部潛力。

——拉爾夫·本傑明

這些發現直到27年後才被公開承認，直到1997年英國政府解密了這些研究。

公共發現

1976年，惠特菲爾德·迪菲和馬丁·赫爾曼發表了一種非對稱密鑰加密系統，受拉爾夫·默克爾關於公鑰分發工作的啟發，他們披露了一種公鑰協議的方法。這種使用有限域中指數運算的密鑰交換方法被稱為Diffie–Hellman密鑰交換。這是首個公開發布的實用方法，用於在已認證（但非保密）的通信通道上建立共享的秘密密鑰，而不需要預先共享秘密。默克爾的「公鑰協議技術」被稱為默克爾謎題，發明於1974年，並於1978年發布。因此，非對稱加密在密碼學中算是一個相對較新的領域，儘管密碼學本身已經有超過2000年的歷史。

1977年，科克斯方案的一個推廣被MIT的羅恩·里維斯特、阿迪·沙米爾和倫納德·阿德爾曼三位學者獨立發明。後來的作者在1978年通過馬丁·加德納的《科學美國人》專欄發布了他們的工作，這一算法被稱為RSA，以他們的名字首字母命名。RSA使用模大質數的指數運算來加密和解密，既能進行公鑰加密，也能生成公鑰數字簽名。其安全性與大整數因式分解的極高難度相關，這一問題沒有已知的高效通用技術。該算法的描述在1977年8月的《科學美國人》數學遊戲專欄中發布。

自1970年代以來，已經開發了大量種類的加密、數字簽名、密鑰協議等技術，包括拉賓密碼系統、ElGamal加密、DSA和橢圓曲線加密（ECC）等。