量子計算和密碼學

量子計算是一種新的計算方式，可以讓人類使用當今的計算技術執行根本不可能的技術。它允許非常快速的搜索，這會破環我們今天使用的一些加密算法。

本文由格密鏈社區的劉天成翻譯。

量子計算可以很容易地計算大數，這會破壞任何密鑰長度的RSA密碼系統。這就是密碼學家努力設計和分析“量子抗性”公鑰算法的原因。目前，量子計算還處于起步階段，密碼學家無法確定哪些是安全的，哪些不是安全的。但即使假設外星人已經充分發揮了這項技術的作用，量子計算也并不意味著密碼學的世界末日。對稱加密很容易產生量子抗性，我們正致力于量子抗性公鑰算法。如果根據我們的數學知識和計算能力，公鑰加密最終只是一個暫時的異常，我們仍然可以生存。如果一些不可思議的外星技術可以打破所有的密碼學，我們仍然可以基于信息理論保密 - 盡管能力有很大的損失。

 

密碼學的核心依賴于數學上的技巧，即有些事情比撤消更容易做。就像粉碎一塊鋼板比將所有碎片粘合在一起更容易一樣，將兩個素數相乘以獲得一個大的數字比把這個大數字再分解成兩個素數要容易得多。這種不對稱 - 單向函數和陷阱門單向函數 - 是所有密碼學的基礎。

 

為了加密消息，我們將它與密鑰組合以形成密文。沒有密鑰，逆轉過程就更加困難了。不僅有點困難，而且是非常的難。現代加密算法如此之快，以至于它們可以保護您的整個硬盤驅動而不會出現任何明顯的減速，但是在宇宙爆炸之前，加密是無法打破的。

 

使用對稱加密，來用于加密消息，文件和驅動器，這種不平衡性是指數級的，并且隨著密鑰的增大而被放大。添加一位密鑰會使加密的復雜程度增加不到百分之一（略過不證明），但打破成本卻增加了一倍。因此，256位密鑰看起來只有128位密鑰的兩倍，但是（根據我們目前的數學知識），破解256位的秘鑰比破解128位的秘鑰要困難340, 282, 366, 920, 938, 463, 463, 374, 607, 431, 768, 211, 456倍。

 

公鑰加密（主要用于密鑰交換）和數字簽名更加復雜。因為它們依賴于諸如因子分解之類的困難的數學問題，所以有更多潛在的技巧來反推它們。因此，您將看到RSA的密鑰長度為2,048位，基于橢圓曲線的算法的密鑰長度為384位。但是，在這里，用這些密鑰長度反轉算法的成本超出了人類目前的承受能力。

 

這種單向性基于我們的數學知識。當你聽說密碼學家“打破”一個算法時，發生的事情就是他們找到了一個新的技巧，使反推變得更容易。密碼學家一直在發現新的技巧，這就是為什么我們傾向于使用長度超過嚴格要求的密鑰長度。這對于對稱和公鑰算法都是如此; 我們正在努力證明它們的未來。

 

量子計算機有望顛覆這一切。由于它們的工作方式，它們擅長扭轉這些單向函數所需的各種計算。對于對稱密碼學，這不是太糟糕。Grover的算法表明量子計算機可以加速這些攻擊，從而有效地將密鑰長度減半。這意味著256位密鑰與量子計算機一樣強，就像128位密鑰與傳統計算機相比; 兩者在可預見的未來都是安全的。

 

對于公鑰加密而言，結果更加可怕。Shor的算法可以很容易地破解所有常用的基于因式分解和離散對數問題的公鑰算法。密鑰長度加倍會增加破解難度的難度。可這還不足夠持久這樣。

 

這兩個段落有很多值得注意的地方，其中最大的一點是能夠做這樣的事情的量子計算機目前還不存在，沒有人知道什么時候會出現 - 或者即使 - 我們能夠建立一個。當我們嘗試實現Grover或Shor的算法時，除了密鑰大小之外，我們也不知道會出現什么樣的實際困難。（量子計算機上的糾錯很容易成為一個不可逾越的問題。）另一方面，一旦人們開始使用實際的量子計算機，我們不知道會發現什么其他技術。我敢打賭，我們將克服工程挑戰，并將有許多進步和新技術，但他們將花時間去發現和發明。就像我們花了幾十年的時間才能把超級計算機裝進口袋一樣，要花上幾十年的時間才能解決建造大型量子計算機所需的所有工程問題。

 

從短期來看，密碼學家在設計和分析量子抗性算法方面付出了相當大的精力，而這些算法可能在幾十年來都保持安全。這是必然是一個緩慢的過程，因為良好的密碼分析轉換標準需要時間。幸運的是，我們還有時間。實用的量子計算似乎總是在“未來十年”中，這意味著沒有人可以知道。

 

然而，在那之后，這些算法總是有可能落入具有更好量子技術的外星人。我不太擔心對稱加密，其中Grover的算法基本上是量子改進的上限，而不是基于數論的公鑰算法，這種算法感覺更脆弱。量子計算機有可能在某一天摧毀所有這些計算機，即使是那些今天就具有量子抗性的計算機。

 

如果發生這種情況，我們將面臨一個沒有強大的公鑰密碼學的世界。這將是對安全性的巨大打擊，并且會打破我們目前所做的很多事情，但我們可以適應。在20世紀80年代，Kerberos是一個全對稱的身份驗證和加密系統。最近，GSM蜂窩標準只進行了對稱加密進行了大規模的身份認證和密鑰分發。是的，這些系統具有集中的信任和失敗點，但是可以設計使用秘密拆分和秘密共享的其他系統來最小化該風險。（想象一下，一對通信者分別從五個不同的密鑰服務器中獲取一個會話密鑰。）通信的普及也使今天的事情變得更容易。我們可以使用帶外協議，例如，您的手機可以幫助您為計算機創建密鑰。我們可以使用面對面注冊來增加安全性，可能是在商店購買您的智能手機或初始化您的互聯網服務。硬件的進步也可能有助于在這個世界中保護密鑰。我不是想在這里設計任何東西，只是指出有很多設計可能性。我們知道密碼學是關于信任的，而且我們有比早期的互聯網更多的技術來管理信任。像前向保密這樣的一些重要屬性會變得遲鈍而且復雜得多，但只要對稱加密仍然有效，我們仍然會有安全性。

 

這是一個奇怪的未來。也許基于數論加密的整個概念，這是我們現代公鑰系統的基礎，是基于我們不完整的計算模型的暫時的迂回。現在我們的模型已經擴展到包括量子計算，我們可能最終回到20世紀70年代末和80年代初的水平：對稱加密，基于密碼的加密，Merkle哈希簽名。這既有趣又具有諷刺意味。

 

是的，我知道量子密鑰分配是公鑰加密的潛在替代品。但是，拜托 - 是否有人希望系統需要專門的通信硬件和電纜才能用于除小眾應用之外的任何其他應用？未來是移動，永遠是嵌入式計算設備。這些軟件的任何安全性都必須僅限于軟件。

 

還有一個未來的方案需要考慮，一個不需要量子計算機的方案。雖然有幾種數學理論支持我們在密碼學中使用的單向性，但證明這些理論的有效性實際上是計算機科學中一個重大的開放性問題。正如聰明的密碼學家有可能找到一種新技巧，可以更容易地破解特定算法，我們可以想象有足夠數學理論的外星人可以打破所有加密算法。今天對我們來說的話，這也太荒謬了。公鑰密碼學是所有數論，并且可能容易受到數學傾向的外星人的影響。對稱密碼學是如此多的非線性混亂，因此容易變得更加復雜，并且容易增加密鑰長度，這種未來是不可想象的。考慮具有512位塊和密鑰大小以及128循環的AES變體。除非數學與我們目前的理解有根本不同，否則在計算機由物質以外的東西構成并占據除空間之外的東西之前，這將是安全的。

 

但是，如果這種難以想象的事情發生了，那我們將只有完全基于信息理論的加密：一次性密碼本及其變體。這將是對安全的巨大打擊。一次性密碼本可能在理論上是安全的，但實際上它們不能用于除專門的小眾應用之外的任何東西。今天，只有破解者才會試圖建立基于一次性密碼本的通用系統 - 密碼學家嘲笑他們，因為他們用密鑰管理和物理安全問題（更加困難）取代了算法設計問題（簡單）。在我們陌生的科幻未來中，我們可能一無所有。

 

對于這些神一般的外星人，密碼學將是我們唯一可以肯定的技術。我們的核武器可能會拒絕引爆，我們的戰斗機可能會從空中墜落，但我們仍然能夠使用一次性密碼本安全地進行通信。這里面有一種樂觀主義。