標籤：

【後量子密碼】是什麼？為什麼RSA"不行了"？有什麼用？研究和應用現狀如何？

10-12
【後量子密碼】是什麼？為什麼RSA"不行了"？有什麼用？研究和應用現狀如何？

29 人贊了文章

後量子密碼，作為未來 5-10 年逐漸代替 RSA、Diffie-Hellman、橢圓曲線等現行公鑰密碼演算法的密碼技術，正被越來越多的人所了解。目前，美國國家標準技術研究所 (NIST) 正在制定的新一代密碼技術標準，正是後量子密碼標準。我在博士期間的方向是後量子密碼，更準確的說，是基於格 (RLWE) 問題的後量子密鑰交換。目前我在知乎上只看到很少的關於後量子密碼的文章。所以，我希望通過後量子密碼專欄，對這個未來極為重要的密碼技術，進行介紹和科普。

專欄前言

很多人聽到「後量子密碼」，第一反應是：這個密碼是不是和量子計算機有關的？能幹什麼？能在普通電腦和手機上用嗎？

希望你在讀完這篇文章後，能對：

  1. 後量子密碼是什麼
  2. 有什麼用
  3. 為什麼 RSA 在未來 5-10 年要被逐漸替換掉
  4. 後量子密碼的研究和應用現狀是什麼

這些問題有一些了解。專欄會盡量少涉及枯燥晦澀的數學問題。

專欄系列文章：

  • 第一篇：【後量子密碼】是什麼？為什麼 RSA"不行了"？有什麼用？研究和應用現狀如何？
  • 第二篇：【後量子密碼】主要構造技術、對比和應用
  • 第三篇：【後量子密碼】基於格 (RLWE) 問題的密鑰交換協議和原理

後量子密碼是什麼？

一句話概括：後量子密碼，是[能夠抵抗量子計算機對現有密碼演算法攻擊的]新一代密碼演算法。

所謂「後」，是因為量子計算機的出現，現有的絕大多數公鑰密碼演算法（RSA、Diffie-Hellman、橢圓曲線等）能被足夠大和穩定的量子計算機攻破，所以可以抵抗這種攻擊的密碼演算法可以在量子計算和其之後時代存活下來，所以被稱為「後」量子密碼。也有人稱之為「抗量子密碼」，說的都是一個意思。英文中的表述是："Post-quantum Cryptography (PQC)"，或者 "Quantum-resistant cryptography"。

下文中，用 PQC 代指後量子密碼。

為什麼需要後量子密碼？

這都要從密碼學和量子計算機說起。(這裡不會過多注重細節，只對結論進行簡單表述，例如：這裡不會涉及量子計算機的原理、建造等)

詳細的完整解釋較為複雜，那這裡直接介紹核心的結論：

  1. 量子計算機很強大，但利用其強大算力的前提是：存在能高效解決問題的量子演算法，否則量子計算機沒什麼用，反而因為其高昂的成本帶來劣勢。數據：5 量子比特的量子計算機造價在千萬美元左右
  2. 量子計算機現有的一些強大演算法/應用包括：密碼演算法安全性、數學計算、機器學習等
  3. 對於密碼演算法安全性，主要是針對公鑰密碼演算法：
    1. 公鑰密碼演算法安全性依賴的數學問題可以被高效的量子演算法所解決。由於底層依賴的數學問題被解決，所以這些公鑰密碼演算法不再安全。這些數學問題包括：離散對數 (及橢圓曲線版本)、大整數分解等。這直接影響目前使用的 RSA、Diffie-Hellman、橢圓曲線等演算法。著名的量子演算法是 1994 年的 Shors algorithm
    2. 關於對稱密碼演算法和哈希函數（例如 AES、SHA1、SHA2 等），雖然有量子演算法可以理論上攻破，但這個演算法的影響有限，且有很多限制條件。著名的量子演算法是 1996 年的 Grovers algorithm
  4. 對於公鑰密碼演算法，量子計算機對安全性的影響：
    1. 完全攻破目前廣泛使用的公鑰密碼演算法
    2. 增大參數的長度沒有用。有人說：把 RSA 的長度從 1024 加到 2048 比特甚至更長，不就安全了嗎？答案是：對於現有的經典計算機和演算法，這樣是可以的。但對於量子計算機和演算法，這是徒勞的（除非 RSA 的長度增大到 1GB 或更長。但這樣的話，演算法還能用嗎？對於其他演算法呢？）
    3. 需要全新的公鑰密碼演算法
  5. 對於對稱密碼演算法，量子計算機對安全性的影響：
    1. 降低現有演算法的安全性：安全性從 k-bit 降低為 k/2-bit
    2. 增大參數的長度有用
    3. 把密鑰長度或哈希的長度加倍即可，例如：AES-128 升級至 AES-256，SHA-256 升級至 SHA-512 等。但這並不是必須的，原因後面會進行介紹
  6. 攻破 RSA-2048 的預計時間和開銷：2030 年，量子計算機，10 億美元，核電站 (PQCrypto 2014, Matteo Mariantoni 的預估)

下圖為 IBM 製造的 5 和 16 量子比特 (qubit) 晶元：

關於量子計算機，再介紹幾個結論：

  1. 量子比特數量重要，但更重要的是質量。目前建造的量子計算機（例如 Google 的 72 qubit 晶元）中，qubit，也就是量子物理比特的質量很差。由於量子相干等物理機制，必須引入糾錯機制，但需要成百上千個量子物理比特進行糾錯，來實現一個量子邏輯比特的功能
  2. 攻破現有的公鑰密碼演算法需要幾千甚至幾萬個邏輯比特。結合上面一點可以看到，建造量子計算機仍處在很初級的階段
  3. D-Wave 建造的 D-Wave 2000Q 「量子計算機」 實際上是量子退火演算法的，並不是真正意義上的普遍適用的量子計算機
  4. 對於量子演算法（例如 Grover），需要指數級別的內存，因此 Grover 演算法的威脅不如 Shor 的演算法那麼緊迫

用 NIST 後量子密碼團隊負責人 Dustin Moody 在 AsiaCrypt 2017 會議上的 Talk 概括一下：

可以看到：

  1. 公鑰密碼演算法：紅色叉，需要後量子密碼演算法代替
  2. 對稱密碼演算法：藍色框，不那麼緊迫需要新演算法代替。可以通過調整參數解決

對後量子密碼演算法的需求是什麼？有多急迫？

我們需要什麼？

顯然，是後量子密碼演算法。更準確的說，是後量子密碼技術標準。密碼實踐中的一個重要結論是：不要自己造輪子（除非你是大佬）。我們現在使用 RSA、Diffie-Hellman、橢圓曲線等演算法正是在被定為國際標準後，才逐漸進入應用領域的。

後量子密碼演算法應該：

  1. 安全：不僅要在現在的計算條件下安全，也要在量子計算機下安全
  2. 運行速度快：現有的結果顯示，相同安全強度下，後量子密碼的計算速度可以超越現有公鑰密碼的計算速度
  3. 通信開銷合理：實踐中幾乎不會使用一個公鑰/密文大小達到幾 M 甚至更大的演算法。目前的 RSA-2048 公鑰大小約為 256 bytes，橢圓曲線大約為 64 bytes。最好的後量子密碼演算法的公鑰大小在 1KB 左右
  4. 可被用作現有演算法和協議的直接代替，例如：公鑰加密、密鑰交換、數字簽名等
  5. 更廣應用場景：例如：同態加密 (Homomorphic Encryption)、屬性加密 (Attribute-based Encryption)、函數加密 (Functional Encryption)、不可區分混淆 (Indistinguishability Obfuscation) 等高級密碼學應用

下圖是 NIST 總結的後量子密碼技術和應用棧：

什麼時候需要？

這是不容易取得一致結論的地方，主要原因在於：

  1. 對大型且穩定的量子計算機被建造出來的時間預估：未來 10 年左右
  2. 新一代密碼演算法需要多久被確定，以及在真實世界中被應用

直觀的結論是：我們要在現有密碼演算法被攻破前做好準備，儘管什麼時間被攻破無人能給出準確的時間。做好準備是指，後量子演算法從研究到真正被實際應用和部署，而非局限在學術界的研究領域。

值得注意的是，2015 年 8 月，美國國家安全局 (NSA) 呼籲遷移至可以抵抗量子計算機攻擊的演算法。有意思的是，作為破解加密通訊和密碼演算法的最大組織，NSA 站出來號召採用後量子密碼演算法。不知道他們是不是已經在現有的密碼破解領域取得了極大的突破？

"IAD will initiate a transition to quantum resistant algorithms in the not too distant future. Based on experience in deploying Suite B, we have determined to start planning and communicating early about the upcoming transition to quantum resistant algorithms." -- NSA

後量子密碼的研究現狀如何？

概況

密碼學界很早就在研究可以抵抗量子計算機攻擊的密碼演算法，最早可以追溯到 1978/9 年的 McEliece 加密、 Merkle 哈希簽名等。但在那時，量子計算機對密碼演算法的威脅並沒有很明確，也沒有「後量子」的概念。所以直到最近十幾年，後量子密碼的重要性逐漸顯現出來。"Post-quantum" 的概念

對後量子密碼技術的研究和標準制定有以下重要參與方：

  1. 美國國家標準技術研究所 (NIST)。NIST 早在 2012 年啟動了後量子密碼的研究工作，並於 2016 年 2 月啟動了全球範圍內的後量子密碼標準徵集，並於 2017.11.30 截止草案提交。2018 年 4 月在 Florida 舉辦了第一屆 PQC 標準化會議。NIST 預計在未來 5 年左右，確定新一代公鑰密碼演算法標準
  2. 歐盟：PQCRYPTO 項目
  3. 歐洲電信標準化協會 (ETSI)：ETSI 也在尋求制定新一代後量子密碼標準。ETSI 已舉辦了 6 屆 workshop。2018 年的 workshop 將於 11 月在北京舉行
  4. 互聯網工程任務組 (IETF)
  5. 美國電氣和電子工程師協會 (IEEE)

NIST 後量子密碼標準徵集

NIST PQC 標準徵集工作與 2016 年正式啟動。NIST 主要聚焦於以下 3 類後量子密碼演算法的徵集：加密、密鑰交換、數字簽名。截至 2017.11.30 提交截止，NIST 共收到 82 個演算法草案。在進行初步篩選後，NIST 公布了 69 個「完整且適合」的草案。

在 69 個候選草案中，主要包括以下 4 種數學方法構造的後量子密碼演算法：

  1. 格 (Lattice-based)
  2. 編碼 (Code-based)
  3. 多變數 (Multivariate-based)
  4. 哈希 (Hash-based)

從 NIST 公布至今（2018.9），已經過去了近 1 年的時間。密碼學界對這些演算法進行了詳細的密碼分析，目前已有近 1/3 的演算法被發現存在各種各樣的缺陷，近 1/5 的演算法已被徹底攻破。

我參加的提案

我很榮幸的向 NIST 的 PQC 標準徵集活動提交了一個草案，並參加了第一屆 PQC 標準化會議。我參加的草案 Ding Key Exchange 是一個基於格問題 (Ring Learning with Errors, RLWE) 的密鑰交換演算法。草案可以在這裡找到。

提案的 slide 可以在這裡下載：csrc.nist.gov/CSRC/medi

下圖是我參與的草案的演算法：

這是一個可以直接代替 Diffie-Hellman 密鑰交換的後量子密碼演算法，基於極為困難的格問題 RLWE 設計。該演算法的細節將在後續文章中介紹和分析。敬請期待

應用現狀

學術界和企業界早已開始合作，在產品中進行後量子密碼技術的應用。下面舉幾個典型的例子：

  1. 最為著名的是 2016 年 Google 在 Chrome Canary 分支版本 (Chrome 54 beta) 中加入了基於 RLWE 問題的後量子密鑰交換演算法 NewHope。Google 在部分 Google 伺服器上搭建了使用 NewHope + X25519 兩種密鑰交換演算法構造的一個 TLS 密碼套件 (Ciphersuite) CECPQ1 進行測試。測試進行了 2-3 個月後結束，並被移除出 Chrome
  2. 微軟研究院將其主推的後量子密碼演算法 Picnic 使用到 PKI 和 HSM 集群中
  3. 微軟研究院推出的後量子 VPN
  4. Open Quantum Safe (OQS) 將一些後量子密碼演算法與 TLS 結合，並開源了後量子 OpenSSL 庫的測試實現

結語

後量子密碼演算法，作為未來 10 年最為重要和前沿的密碼技術，將對現有的公鑰密碼體制產生極為重要而深遠的影響。作為 RSA、Diffie-Hellman、橢圓曲線等現行公鑰密碼演算法的代替品，提早理解演算法及其應用場景對於未來的信息安全和密碼學具有重要的意義。專欄的後續文章中，我會對後量子密碼的底層技術、演算法的原理和構造方法、安全性、實際效率、應用場景等更多方面進行介紹。歡迎持續關注！

擴展閱讀

  1. 量子計算機會不會取代今天的計算機演算法技術？
  2. 怎麼去理解量子計算機的 「量子」？與傳統計算機有什麼區別？
  3. Timeline of quantum computing

註：本文部分圖片截取自 NIST 後量子密碼團隊負責人 Dustin Moody 在 AsiaCrypt 2017 會議上的 Talk slide。


推薦閱讀：

TAG:密碼學 | 量子計算機 | 信息安全 |