選定安全等級之後，重要的是確保你的密碼學方案真的守得住這個等級。換句話說，你要的是信心，而不只是希望與不確定。

要建立對一個密碼演算法之安全性的信心，你可以依靠：

• 數學證明——稱為可證明安全性（provable security）。
• 破解嘗試皆告失敗的證據——這裡稱為啟發式安全性（heuristic security），有時也叫 probable security。

這兩種取徑是互補的，沒有哪一個比另一個更好。

可證明安全性#

可證明安全性的重點，是證明破解你的密碼方案，至少與解決另一個已知困難的問題一樣難。這樣的安全性證明保證：只要該困難問題仍然困難，密碼就仍然安全。

這類證明稱為歸約（reduction），來自複雜度理論。我們說「破解某密碼可歸約到問題 X」，若任何解決問題 X 的方法也能導出破解該密碼的方法。

安全性證明依所用的「假定困難問題」型態分成兩種。

相對於數學問題的證明#

許多安全性證明（例如公鑰密碼學的證明）顯示：破解一個密碼方案至少與解決某個困難的數學問題一樣難。這裡談的是那種已知解存在、一旦知道就容易驗證，但計算上很難找到的問題。

其實沒有真正的證明能說明那些看似困難的數學問題確實困難。事實上，為某一類問題證明這件事，是複雜度理論領域最大的挑戰之一——在本書寫作時，克雷數學研究所（Clay Mathematics Institute）為解出它的人提供 100 萬美元的懸賞。詳見第 9 章。

因式分解問題是密碼學中最知名的數學問題：給定一個你知道是兩個質數乘積的數 n = pq，找出這兩個質數。例如 n = 15，答案是 3 與 5。這對小數字很容易，但隨著數字變大會呈指數級變難——當 n 長達 3000 位元（約 900 個十進位數字）以上，因式分解被認為實際上不可行。

RSA 是最著名的、依賴因式分解問題的密碼方案：它把視為大數的明文 P 加密成 C = P^e mod n，其中 e 與 n = pq 是公鑰；解密則計算 P = C^d mod n，其中 d 是對應於 e 與 n 的私鑰。

如果我們能分解 n，就能破解 RSA（從公鑰還原私鑰）；反之，若能取得私鑰，就能分解 n。換言之，還原 RSA 私鑰與分解 n 是等難的問題——這正是可證明安全性所要的歸約。

然而，並沒有保證還原一段 RSA 明文與分解 n 一樣難，因為知道一段明文並不會洩漏私鑰。

相對於另一個密碼學問題的證明#

與其把一個密碼方案拿去和數學問題比較，你也可以拿它和另一個密碼方案比較，證明「只有破解得了第一個，才破解得了第二個」。對稱密碼的安全性證明通常走這條路。

例如若你手上只有一個置換演算法，你可以透過對這個置換施以各種型態的輸入並組合起來，建構出對稱密碼、隨機位元產生器，以及雜湊函式等其他密碼學物件（見第 6 章）。證明接著顯示：若該置換是安全的，則新建出來的方案也是安全的。換句話說，我們確知新演算法不會比原本那個更弱。這類證明通常的做法，是「給定一個對大元件的攻擊，就構造出一個對小元件的攻擊」——也就是展示一個歸約。

證明一個密碼演算法不比另一個更弱，主要好處是縮小攻擊面：你不必同時分析核心演算法與其組合方式，只要看新密碼的核心演算法就好。

具體來說，若你寫了一個使用新開發之置換與新組合方式的密碼，你可以證明該組合相對於核心演算法並未削弱安全性。因此要破解這個組合，就必須先破解那個新置換。

但要小心#

密碼學研究者高度倚賴安全性證明，無論是相對於數學問題還是相對於其他密碼方案。但安全性證明的存在，並不保證一個密碼方案是完美的，也不是忽視實作面務實考量的藉口。

密碼學家 Lars Knudsen 說過：「若它是可證明安全的，它大概就不安全。」（“If it’s provably secure, it’s probably not."）

意思是：安全性證明不該被當成安全的絕對保證。

更糟的是，「可證明安全」的方案仍可能導致安全失效，原因有好幾種：

• 「安全性證明」這個說法本身就有問題。 在數學中，證明是絕對真理的展示；但在密碼學中，證明只是相對真理的展示。例如「證明你的密碼與計算離散對數（給定 g 與 g^x mod n 求 x）一樣難破解」，保證的只是：若你的密碼失守，一大票其他密碼也會一起失守，最壞情況發生時沒有人會怪你。

• 證明通常只針對單一的安全概念。 例如你可能證明了「還原某密碼的私鑰與因式分解問題一樣難」。但如果攻擊者能在沒有金鑰的情況下從密文還原明文，他就繞過了這個證明——還原金鑰與否也就無關緊要了。

• 證明未必正確。 破解一個演算法可能比原先想的更容易。

  遺憾的是，很少研究者會仔細檢查那些動輒數十頁的安全性證明，這讓品質控管更加困難。

  話說回來，證明被指出有誤，不必然代表證明的目標完全錯誤；若結論是正確的，修正錯誤後證明仍可能被挽救。

• 困難的數學問題有時比預期容易解。 例如某些弱參數會讓破解 RSA 變得容易。又或者該數學問題在特定情況下困難、平均而言卻不困難——當參照問題較新且未被充分理解時常會如此。1978 年 Merkle 與 Hellman 的背包（knapsack）加密方案就是這樣，後來被格基約化（lattice reduction）技術完全攻破。

• 證明沒問題，實作卻可能很弱。 攻擊者可能利用功率消耗或執行時間這類旁道資訊，來了解演算法的內部運作並加以破解，從而繞過證明。或者實作者誤用了該密碼方案：如果演算法太複雜、有太多可調的旋鈕，使用者或開發者搞錯設定的機率就更高，而這可能讓演算法變得完全不安全。

啟發式安全性#

可證明安全性是建立信心的好工具，但它不適用於所有種類的演算法。事實上，多數對稱密碼都沒有安全性證明。

我們每天靠 AES 在手機、筆電與桌機上安全通訊，但 AES 並非可證明安全——沒有任何證明說它與某個知名問題一樣難破解。

AES 無法被關聯到某個數學問題或另一個演算法，因為它自己就是那個困難問題。

在可證明安全性不適用的情況下，信任一個密碼的唯一理由，就是許多有能力的人試圖破解它而失敗了。這就是所謂的啟發式安全性。

那我們何時能確定一個密碼是安全的#

我們永遠無法確定。但當數百位經驗豐富的密碼分析者，每人各花了數百小時試圖破解它並發表他們的發現之後，我們可以相當有信心它不會被攻破。

這些嘗試通常是針對簡化版本的密碼——往往是運算較少、或輪數（rounds，密碼為了混合位元而反覆迭代的短運算序列）較少的版本。

安全邊際#

分析一個新密碼時，密碼分析者先試著破解一輪，接著兩輪、三輪，能破幾輪就破幾輪。

當一個密碼經過數年研究後安全邊際仍然很高，我們就對它（大概）是安全的產生信心。