PQC 筆記 1 - 靠近一點看量子電腦對當代密碼學的威脅

PQC 筆記 1 - 靠近一點看量子電腦對當代密碼學的威脅-黑暗執行緒

PQC (Post-Quantum Cryptography)，後量子密碼學，意指在量子電腦成熟後，現行的部分密碼學演算法將變得不堪一擊，需要更成換足以抵抗量子電腦破解的密碼學演算法。這些抗量子電腦攻擊的加解密及簽章演算法的相關研究便被稱為後量子密碼學，簡稱 PQC。(註：有個推動雲端安全的組織 CSA (Cloud Security Alliance)，比照當年 Y2K 問題的概念，啟動了所謂 Y2Q 倒數，寫這篇文章的當下大約剩下 6 年又 70 天。延伸閱讀：Y2Q 倒數與 Q-Day，當代資訊安全防線即將崩潰)

我打算靠近一點來看所謂「量子電腦對當代密碼學造成的威脅」，從這句話開始追根究底：

量子電腦**「成熟」後，現行的「部分」密碼學演算法將變得「不堪一擊」**

由這句話可衍生三個問題：

1. 量子電腦只會讓「部分」密碼學演算法變得不堪一擊，所以不是全部？是哪些會受影響？
2. 量子電腦要多「成熟」，才會讓當代密碼學演算法不堪一擊？
3. 量子電腦會讓部分密碼學演算法變成「不堪一擊」，是有多不堪？

這篇文章將試著回答以上問題。

首先，講到量子電腦比古典電腦強大(是的，現在大家在用的電腦已經被定義成古典電腦惹)，你腦中浮現可能會是 13 代 Intel Core i9 對比八代 Core i3 快，或是 GTX 4090 顯卡的算力把 GTX 1050 壓在地上磨擦，是種效能上的全面性輾壓。但事實並非如此，量子電腦靠著量子疊加態與量子糾纏等特性，得以實現一些特殊演算法，在特定領域比古典電腦快 N 倍。但量子電腦並不能完全取代古典電腦，它只在某些特殊領域佔優勢，其他運算跟古典電腦差不多甚至更糟，故量子電腦普及後程式主要邏輯仍會靠古典電腦執行，遇到量子電腦擅長任務時，再將其交由量子電腦計算取回結果。若量子電腦成熟到可做成普通晶片，未來主機板上或許會同時有傳統 CPU 跟量子電腦 QPU (甚至 CPU + GPU + QPU 整合成一顆 參考)，二者協力合作。就像古早時代 8086 CPU 與 8087 FPU 浮點運算器聯手一樣，或是現在 CPU + GPU 協力運算，靠專屬硬體加速特定運算，突破效能瓶頸。

量子電腦擅長哪些領域呢？可粗分成三類：Search (搜尋)、Hidden Subgroup (隱藏子群)、量子模擬 (Quantum Simulation)。參考

Search Problem

搜尋問題在於嘗試所有可能的答案並找出正確答案，Grover 是針對搜尋問題最具代表性的量子演算法。古典電腦搜尋 N 個可能答案耗費時間與 N 成正比，Grover 演算法耗費時間僅為 N 的平方根。當 N = 100 萬，Grover 演算法比古典電腦快 1000 倍，N = 100 億，則快 10 萬倍，N 愈大，差異愈明顯。

要破解 SHA256、AES256 這類雜湊或加密演算法，多半得暴力嘗試所有組合。改用量子電腦可讓嘗數次數開平方，縮短破解時間，但 SHA、AES 的破解難度是每增加一個位元增加一倍，Grover 的平方根效果相當於減少一個位元長度，故只要長度夠長，還是能有效抵抗量子電腦攻擊，受到的威脅性不大。

Hidden Subgroup Problem

Hidden Subgroup Problem (HSP) 與因式分解、離散對數、圖同構和最短向量問題有關，最有名的量子演算法是 Shor 演算法，古典電腦要計算數萬年的超大質數因式分解，量子電腦能在很短時間內解開。目前我們主要採用的公私鑰演算法，RSA 背後是因式分解，DSA、ECDSA 是離散對數，均位於重災區，預估會被量子電腦輕易破解。(延伸閱讀：數位簽章知識補充包 - ECC 橢圓曲線密碼學、Ed25519、Curve 25519)

Quantum Simulation

因量子電腦本身靠量子特性運作，特別適合用來模擬量子力學行為，但這塊跟密碼學比較沒關係。

至此，第一個問題有了答案，「部分」密碼學演算法指的是 RSA、DSA、ECDSA 這類公開金鑰演算法，將因量子電腦潰不成軍，而 SHA、AES 估計仍相當安全。

接下來的問題是，那需要多大台的量子電腦？要花多久時間破解？

用量子電腦實作 Shor 演算法究竟需多少量子位元(Qubit)？這個問題有點複雜。參考 Quantum Attack Resource Estimate: Using Shor’s Algorithm To Break Rsa Vs Dh/Dsa Vs Ecc 這篇研究，實做 Shor 演算法需要的量子位元數，可依以下原理推算。

首先是，不同演算法要達到相同的位元安全性(Bit-Security)所需的金鑰長度不同，以下是 RSA、ECC 不同 Bit Security 對應的金鑰長度：
註：Bit-Security 是加密算法安全性的量化單位，用「攻擊者破解密碼所需工作量」以量化安全性

上表就是之前談 ECC 橢圓密碼學說 ECDSA 可以用較短的金鑰長度達到與 RSA 相同的安全等級，ECDSA 256 bit 相當於 RSA 3072 bit 的由來。

將這三種位元安全性對應攻擊該等級演算法所需的最少量子位元數量如下：

以上的量子位元數量是演算法層次的理想值，要實作出可執行運算邏輯，需設計並組合線路，有時為提高效率還需用空間換取時間，靠增加記憶體數量減少運算次數，故需要的實體量子位元將遠大於邏輯值。再加上目前量子位元存在一定的錯誤率，需要量子錯誤更正碼 (Quantum Error Correction Code) 教會用多個實體量子位元組成一個邏輯量子位元(依 Google 去年的資料，使用 49 個實體量子位元組成一個邏輯位元，錯誤率約 2.914%)以偵測並修正錯誤 參考。綜合以上，完成 Shor 演算法需要的實體量子位元會遠大於上述數字。

依據不同錯誤率，估算要在 24 小時內以 5MHz Surface Clock (可想成量子電腦運算頻率) 破解不同演算法不同金鑰長度所需的百萬個實體量子位元數(下表中的 MegaQuibitDays 單位)如下面兩張表。

1. 若實體量子位元錯誤率 10-3，想 24 小時破 RSA 3072 要 4 M Qubits，ECDSA-256 要 7.4 M Qubits

   Cipher	Minimum logical qubits required	Overall cost (megaqubitdays)
   RSA-2048	6190	1.17
   RSA-3072	9288	4.03
   RSA-7680	23239	86.5
   ECDSA-256	2619	7.43
   ECDSA-384	3901	10.0
   ECDSA-512	5273	15.6

2. 若實體量子位元錯誤率低於 10-5，則 24 小時破 RSA 3072 要 340 K Qubits，ECDSA-256 要 890 K Qubits

   Cipher	Minimum logical qubits required	Overall cost (megaqubitdays)
   RSA-2048	6190	0.34
   RSA-3072	9288	1.14
   RSA-7680	23239	18.9
   ECDSA-256	2619	0.89
   ECDSA-384	3901	1.00
   ECDSA-512	5273	1.56

在 Migrating to Post-Quantum Cryptography: a Framework Using Security Dependency Analysis 這篇論文我找到另一組參考數據：

DL with NIST P-256 (橢圓曲線離散對數)，若有 68 M Qubits，可在 24 小時內破解；RSA 3072 難一點，需要 640 M Qubits，也能在 24 小時內破解；至於 AES-128，那就難了，即使有 2 的 30 次方(1,073,741,824)，1 G Qubits，也要花上一年；所以只要升級成 AES-256 (難度再上升 2128 倍)當可高枕無憂。

綜合以上，想在一天內破解 RSA、ECDSA，需要的實體量子位元差不多要百萬起跳，依據 IBM 的十年計劃，要在 2033 年打造出 100,000 個量子位元(不到 100K)的量子電腦，已經有點接近目標了。

最後，回答一開始的疑問：

1. 量子電腦只會讓「部分」密碼學演算法變得不堪一擊，指的主要是 RSA、ECDSA。雜湊及對稱式加密只要長度夠長，如 SHA256、AES256 還是很安全的。
2. 量子電腦要到百萬量子位元 (Mega Qubits) 等級，才能輕鬆破解當代密碼學演算法。
3. 目前估算用量子電腦攻擊密碼多以 24 小時內破解為標準，只能擋一天跟現在的幾百年起跳相比，確實算不堪一擊。

</div