密碼學基礎與應用
以量子電腦的Grover演算法搜尋n位元對稱式加密的金鑰時，所需的計算次數一般認為約為 2^(n/2) 次。以這個單純的參考值來看，AES-128對量子電腦的安全性最接近下列何者？
- A約相當於64位元
- B約相當於127位元
- C約相當於128位元
查看答案與解析
正確答案：A. 約相當於64位元
Grover演算法把暴力破解的次數從 2ⁿ 減少到約 2^(n/2)，也就是平方根。AES-128為 2^(128/2) = 2⁶⁴ 次，安全性約相當於64位元。與以多項式時間破解公開金鑰加密的Shor演算法不同，這可以靠加長金鑰來應對，AES-256仍保有約128位元的安全性。不過，Grover演算法平行化的效果小，又必須毫無錯誤地持續進行很長的計算，因此這只是單純的參考值；在NIST對後量子密碼學的評估中，與AES-128的金鑰搜尋同等困難，也是最低安全性等級的基準。
- A. 正確。2^(128/2) = 2⁶⁴，約相當於64位元。
- B. 約127位元對應於傳統電腦暴力破解時，平均試到一半的 2¹²⁷ 次就會找到。
- C. 這是假設完全不受量子電腦影響的值。Grover演算法會使安全性的位元數大約減半。