困難的計算問題是現代密碼學的基石。 它們描述起來簡單，實際上卻不可能解決——即使是最好的演算法，也無法在太陽燒盡之前找出解答。

1970 年代對困難問題的嚴謹研究，催生了一門稱為計算複雜度理論的新學科，它戲劇性地影響了密碼學以及經濟學、物理學、生物學等許多領域。

本章脈絡#

  1. 計算困難性——如何衡量執行時間，以及多項式時間 vs. 超多項式時間。
  2. 複雜度類別——P、NP、NP-complete，以及百萬美元的 P vs. NP 問題。
  3. 因式分解問題——RSA 的基礎。
  4. 離散對數問題——Diffie–Hellman 的基礎，以及群的概念。

常見錯誤#

四十多年過去，我們仍不知道如何有效率地分解大數或求解離散對數。

業餘者可能會爭辯說終有一天會有人攻破因式分解——我們確實沒有證明說它永遠不會被攻破，但我們同樣沒有 P ≠ NP 的證明。同理，你可以推測 P 也許等於 NP；然而據專家所言，這個意外不太可能發生。

所以不必擔心。今日部署的所有公鑰密碼學，也確實依賴因式分解（RSA）或 DLP（Diffie–Hellman、ElGamal、橢圓曲線密碼學）。

然而，數學或許不會辜負我們，真實世界的疏漏與人為錯誤卻會趁虛而入。

當因式分解變容易#

分解大數並不總是困難的。以下面這個 1024 位元的數 N 為例——對 RSA 中 N = pq 形式的 1024 位元數，我們預期最好的演算法需要約 2^70 次運算。但用 SageMath 這個基於 Python 的數學軟體，在一台 2015 年的 MacBook 上，factor() 函式不到五秒就找出了因式分解：

2^800 × 641 × 6700417 × 167773885276849215533569
      × 37414057161322375957408148834323969

作者作弊了。這個數不是 N = pq 的形式——它不只有兩個大質因數，而是有五個，包含非常小的因數，這讓它容易分解。

你會先用一份預先算好的質數清單試出 2^800 × 641 × 6700417 的部分，剩下一個 192 位元的數——那比一個有兩個大因數的 1024 位元數容易分解得多。

但因式分解變容易，不只發生在 N 有小質因數的時候。當 N 或其因數 p、q 具有特定形式時也會：

  • N = pq 而 p 與 q 都接近某個 2^b
  • N = pq 而 p 或 q 的某些位元已知
  • N 是 N = p^r q^s 的形式且 r 大於 log p

小的困難問題並不困難#

計算上困難的問題在夠小的時候就變得容易，即使是指數時間的演算法，隨著問題規模縮小也會變得實用。

一個對稱密碼可能是安全的——意思是沒有比 2^n 時間之暴力破解更快的攻擊——但若金鑰長度 n = 32，你幾分鐘內就能破解它。

這聽起來理所當然，你可能覺得沒人會天真到使用小金鑰，但現實中這種事發生的理由多得是。

真實故事一：128 位元的 RSA

假設你是個對密碼學一無所知的開發者，手上有個能用 RSA 加密的 API，被告知要以 128 位元安全性加密。你會挑什麼 RSA 金鑰長度？

作者見過真實的 128 位元 RSA 案例——也就是基於一個 128 位元 N = pq 的 RSA。

然而，雖然對長達數千位元的 N 而言因式分解困難到不切實際，分解一個 128 位元的數卻很容易：

sage: p = random_prime(2**64)
sage: q = random_prime(2**64)
sage: factor(p*q)
6822485253121677229 * 17596998848870549923

這在典型筆電上瞬間完成。但若改用 p = random_prime(2**1024) 挑 1024 位元質數，factor(p*q) 這道指令永遠不會完成——至少不會在作者有生之年。

平心而論，現有工具並沒有幫忙防止「天真地使用不安全的短參數」。

例如 OpenSSL 工具包讓你能產生短至 31 位元的 RSA 金鑰而不發出任何警告：

$ openssl genrsa 31
Generating RSA private key, 31 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)
-----BEGIN RSA PRIVATE KEY-----
MCsCAQACBHHqFuUCAwEAAQIEP6zEJQIDANATAgMAjCcCAwCSBwICTGsCAhpp
-----END RSA PRIVATE KEY-----

顯然這種短金鑰完全不安全。

審查密碼學時，你不只該檢查所用演算法的類型，還要檢查它們的參數與秘密值的長度。

真實故事二：512 位元的 Diffie–Hellman

2015 年，研究人員發現許多 HTTPS 伺服器與電子郵件伺服器仍支援一個較舊、不安全版本的 Diffie–Hellman 金鑰協商協定：底層的 TLS 實作支援在一個由僅 512 位元之質數 p 定義的群 Zp* 中執行 Diffie–Hellman——在那裡，離散對數問題已經不再是實際上不可能計算的了。

不只伺服器支援弱演算法，攻擊者還能藉由在客戶端的工作階段中注入惡意流量，強迫一個良性的客戶端使用該演算法。

對攻擊者更有利的是：攻擊中最耗時的部分只需執行一次，就能回收用來攻擊多個客戶端。對某個特定的群 Zp* 花約一週計算之後，破解不同使用者的個別工作階段只需要 70 秒。

在密碼學中，你永遠應該讀那些小字。

細節見研究論文〈Imperfect Forward Secrecy: How Diffie–Hellman Fails in Practice〉：https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf ↗。

延伸閱讀#

作者鼓勵你更深入探究運算的基礎面向：可計算性（哪些函式能被計算？）與複雜度（代價多大？），以及它們與密碼學的關係。

高度推薦 Scott Aaronson 的《Quantum Computing Since Democritus》（Cambridge University Press, 2013）。它大部分談量子計算，但前幾章對複雜度理論與密碼學的引介極為出色。

在密碼學研究文獻中你還會找到其他困難計算問題。以下例子展示了密碼學家所利用之問題的多樣性：

  • Diffie–Hellman 問題（給定 g^x 與 g^y，求 g^xy）是離散對數問題的變體，廣泛用於金鑰協商協定。
  • 格問題（lattice problems），例如最短向量問題（SVP）與帶錯誤學習問題（LWE），是唯一被成功用於密碼學的 NP-hard 問題範例。
  • 編碼問題依賴「在資訊不足的情況下解碼糾錯碼」的困難性，自 1970 年代末就被研究。
  • 多變數問題是關於求解非線性方程組，潛在上是 NP-hard 的，但它們未能提供可靠的密碼系統——因為困難的版本太大太慢，而實用的版本被發現不安全。
Backward 基於置換的 AEAD 計算困難性 Forward