第 1 章把密碼的安全性描述為相對於攻擊者能力與目標而言的概念，並認定：若在攻擊者已知能力下不可能達成這些目標，該密碼就是安全的。

但在這個脈絡下，「不可能」到底是什麼意思？

密碼學用兩個概念來定義「不可能」：

• 資訊安全性（informational security）：理論上的不可能。
• 計算安全性（computational security）：實務上的不可能。

資訊安全性不量化安全性——它把密碼視為非安全即不安全，中間沒有灰色地帶。因此它在實務上沒有用處，儘管在理論密碼學中扮演重要角色。

計算安全性才是衡量密碼強度時更相關、更實用的尺度。

理論上的安全：資訊安全性#

資訊安全性關心的不是破解一個密碼有多難，而是破解它究竟是否可以想像。

一個密碼是資訊安全的，唯若即使給定無限的計算時間與記憶體，它仍然無法被破解。

即使一次成功的攻擊要花上數兆年，這樣的密碼在資訊安全性的定義下仍屬不安全。

一次性密碼本的例子#

第 1 章介紹的一次性密碼本就是資訊安全的。回想它把明文 P 加密成密文 C = P ⊕ K，其中 K 是每段明文專屬的隨機位元字串。

它之所以資訊安全，是因為：給定一段密文與無限的時間去試遍所有可能的金鑰 K 並算出對應的明文 P，你仍然無法辨識出正確的 K——因為可能的 P 與可能的 K 一樣多。

實務上的安全：計算安全性#

與資訊安全性不同，計算安全性認為：若一個密碼無法在合理的時間內、以合理的資源（記憶體、硬體、預算、能源等）被破解，它就是安全的。

計算安全性是量化密碼或任何密碼學演算法之安全性的方法。

一個例子#

考慮一個密碼 E，你知道一組明文—密文對 (P, C)，但不知道用來計算 C = E(K, P) 的那把 128 位元金鑰 K。

這個密碼不是資訊安全的，因為你可以試遍 2^128 種可能的 128 位元 K，直到找到滿足 E(K, P) = C 的那一把。

但實務上，即使每秒測試 1000 億把金鑰，這也要花上超過 100,000,000,000,000,000,000 年。

因此合理地說，這個密碼是計算安全的，因為破解它在實務上不可能。

(t, ε)-安全#

計算安全性有時以兩個值表示：

• t：攻擊者將執行之運算次數的上限。
• ε（epsilon）：攻擊成功機率的上限。

我們說一個密碼學方案是 (t, ε)-安全的，若一個至多執行 t 次運算（無論這些運算是什麼）的攻擊者，其成功機率不高於 ε（ε 介於 0 與 1 之間）。

若一個密碼是 (t, ε)-安全的，則任何執行少於 t 次運算的攻擊者都不會（以機率 ε）成功。但這不表示恰好執行 t 次運算的攻擊者就會成功，也沒告訴你實際需要多少次運算——那可能遠大於 t。

我們說 t 是所需計算量的下界，因為你至少需要 t 次運算才能危及安全性。

有時我們精確知道破解一個密碼要花多少力氣。這種情況下，若存在一個以機率 ε 且恰好 t 次運算就能破解該密碼的攻擊，我們說 (t, ε)-安全給出了一個緊界（tight bound）。

以 128 位元金鑰為例#

理想上，一個 128 位元金鑰的對稱密碼，對介於 1 與 2^128 之間的任何 t 值，都應該是 (t, t/2^128)-安全的。最佳攻擊應該就是暴力破解（試遍所有金鑰直到找到正確的那把）。

任何更好的攻擊都必須利用密碼的某種不完美之處，所以我們努力設計「暴力破解就是最佳攻擊」的密碼。

給定 (t, t/2^128)-安全的敘述，來看三種可能攻擊的成功機率：

我們可以得出結論：一個 n 位元金鑰的密碼，對任何介於 1 與 2^n 之間的 t，最多是 (t, t/2^n)-安全的。

因為無論密碼多強，針對它的暴力攻擊終究會成功。因此金鑰必須夠長，才能在實務上讓暴力攻擊失效。

上例計算的是密碼被求值的次數，而不是絕對時間或處理器時脈週期數。

計算安全性是技術中立的，這是好事：今天 (t, ε)-安全的密碼，明天仍然是 (t, ε)-安全的。但今天在實務上被認為安全的東西，明天未必還被認為安全。