PQC 筆記 2 - 簡單認識後量子時代密碼學演算法

先前提到，當代維繫全世界資訊安全的命脈 - RSA、DSA、ECDSA 等非對稱演算法，會在量子電腦達到百萬量子位元等級後變得不堪一擊。雖然量子位元數目前才剛破千(IBM 於去年剛推出 1121 量子位元處理器)，距離百萬等級還要好幾年，但全面換掉演算法預估得花上好幾年，故有必要提早開始評估規劃。

必須提早開始準備的另一個重要理由是：駭客有可能現在開始蒐集你的加密內容，有計劃地保存等待夠強大的量子電腦問市再破解。(當然，前題是你的資料夠重要且在多年後仍具有價值)

2015 年物理學家 M. Mosca 提出「XYZ 理論」，指出「需要確保資訊安全的時間 X」加上「替換成後量子密碼學(PQC)所需時間 Y」若大於「做出具破解能力量子電腦所需時間 Z」，資訊便會曝露在風險中。舉例來說，若合約需保密五年(X)，預計三年(Y)後可改用 PQC 加密，而量子電腦在七年(Z)後具備破解能力，則未來一年使用非 PQC 加密的合約資料，保密期間的最後一年會有被量子電腦破解的風險。(推薦這篇科普簡報：量子電腦發展對密碼學或資安的影響 by 楊柏因

有鑑於此，美國國家標準暨技術研究院 National Institute of Standards and Technology，簡稱 NIST (前身為 NBS)，依循先前透過公開爭選方式制定 DES、AES 加密標準的慣例，再次扛起拯救世界的責任。面對來勢洶洶的量子電腦威脅，於 2016 年起開始公開徵求 PQC，評比選拔的程序頗繁瑣，可想像成全球頂尖數學家與資安專家探討不同數學演算法優劣的武林大會，我連看戲的資格都沒有，所以直接看結論。

歷經六年三輪競賽，NIST 於 2022/7/5 公佈第一批確認名單：

公鑰加密及金鑰建立演算法(KEM)為 CRYSTALS-KYBER 、數位簽章則有 CRYSTALS-Dilithium、FALCON、SPHINCS+ 三種。

圖片來源

並於 2023/8 公告 KYBER、Dilithium、SPHINCS+ 標準化草案，FALCON 則會在今年公佈。

但評選尚未結束，第四輪決賽仍在進行，預計今年會再公佈第二批確認名單，計劃在 BIKE、Classic McEliece、HQC 與 SIKE 中選出跟 CRYSTALS-KYBER 使用不同數學原理的演算法(KYBER 採用 Lattice-based)，避免雞蛋放在同一個籃子，在 Lattice 系列演算法被發現重大弱點時仍保有其他選項。

PQC 演算法必須避開量子電腦擅長的因數分解與離散對數，目前數學家找到的主要研究方向包含 Lattice (網格/晶格)、Hash (雜湊)、Isogency (超奇異橢圓曲線同源)、Code (編碼)、Multivariate (多變數) 參考。有趣的是有些演算法並不因為量子電腦才被發掘，像是 Classic McEliece 在 RSA 的隔年，1978 年就問市了，比 ECC (1995) 早了 17 年，但因效能、資料長度不夠出色未成主流，如今因量子電腦威脅才重回焦點。

第三輪確認名單與第四輪候選演算法所屬領域如下圖：

圖片來源

更換演算法除了要改寫程式，另一個衝擊是效能跟資料量。RSA 與 ECDSA 之所以成為主流，金鑰小速度快是一大原因。PQC 演算法的金鑰跟簽章普遍都變大，如下圖整理幾種 PQC 電子簽章演算法金鑰及簽章長度，Dilithium II 公鑰 1184 Bytes、簽章 2044，SPHINCS+ 簽章 16,976，Falcon 公鑰 897，簽章 690；而 ECDSA 384，公私鑰及簽章都只需要 48 Bytes，難怪能成為當今主流。

圖片來源

結語：對一般開發者來說，目前還不到開始動手換演算法的時機，資安標準的全面落實需要軟硬體與環境配合，就像 TLS 1.2 一樣，你的瀏覽器想停用不安全的 TLS 1.0/1.1，也得問問網站是否都已支援。現階段對於 PQC 議題，應該就是持續觀注 PQC 與量子電腦發展，預做心理準備，不要聽別人說起 PQC、量子電腦，只能回應一句：「蛤？」 😄