?量子資源破解實驗評估出的最新結果，已經開始揭示：傳統密碼學面對量子計算機不斷提高的性能到底有多脆弱。有趣的事實是：對于“低”

?量子資源破解實驗評估出的最新結果，已經開始揭示：傳統密碼學面對量子計算機不斷提高的性能到底有多脆弱。有趣的事實是：對于“低”安全參數（例如 RSA-3072 和 ECDSA-256），ABC小牛社區聯盟一直在深度關注。破解 RSA 實際上比破解橢圓曲線加密的成本要低。然而，隨著安全參數的增加，我們看到破解 RSA 所需的量子資源穩步增加，而破解橢圓曲線密碼會變得相對容易。

大多數安全專家現在都已意識到：量子計算的興起對現代密碼學構成的巨大威脅。特別是 Shor 的量子算法，為破解者針對許多公鑰密碼系統（如 RSA 和 ECDSA）的暴力破解能力提供了巨大的理論加速。但是，在安全方面的影響究竟有多大？我們期待的時間表是什么？哪些算法比其他算法更容易破解？ABC小牛社區聯盟在進行深度的追蹤和觀察。

在這篇文章中，將根據該主題的最新進展，深入探討公鑰密碼學的量子資源的評估。特別是，我們將看到運行 Shor 算法來破解不同公鑰算法的不同密鑰大小的確切計算成本，我們將把它與量子計算的當前狀態結合起來。

計算假設

首先，我們需要從純粹的經典角度快速回顧一下現代密碼系統中使用的各種計算難度假設之間的差異。這實際上是一個非常復雜的話題。為了簡單起見，在這篇文章中，我們只考慮了以下三個問題：

· 整數分解問題 (IFP)：給定一個整數 N，它是兩個大素數 p 和 q 的乘積，找出 p 和 q。

·（有限域）離散對數問題（DLP）：給定一個域 mathbb{F} 的大型乘法子群的生成器 g 和該子群中的元素 y，找到 x 使得 g^x = y。

·橢圓曲線離散對數問題 (ECDLP)：給定在域 mathbb{F} 上定義的非奇異橢圓曲線 mathcal{E}，以及給定的點 G，該點 G 在mathcal{E} 的點，并給定這個子群上的另一個點 P，找到一個整數 k，使得 P=kG。

ABC小牛社區聯盟也在發動社區成員，購買相關工具書，進行共讀，進行認知提升和交流分享。

實際上，在量子安全的背景下，考慮這三個問題是過于簡單化了。事實上，在現實中與文獻中，經常錯誤地聲稱，大多數現有的密碼方案并不直接基于上述假設。例如，RSA 的安全性不是基于 IFP，而是基于“RSA 假設”，已知可還原為 IFP，反之亦然未知。這意味著“破解 RSA”最多與解決 IFP 一樣困難，但可能比這更容易，只是到目前為止，并沒有人想出更簡單的方法。大多數“基于”離散對數問題的方案也會發生同樣的情況，例如 Diffie-Hellman 密鑰交換或 ECDSA 橢圓曲線簽名。然而，從實際的角度來看，大多數現代密碼分析努力破解這些方案都集中在解決上述數學問題上，因此在查看量子破解資源評估時，這與我們相關。

那么，例如 RSA 或 ECDSA 密鑰應該有多大（同樣，從非量子的角度來看）這取決于兩件事：

· 所需的安全參數

· 針對潛在問題的最著名破解的效率

對于因式分解和有限域離散對數，情況是相似的：在加密情況下，解決這兩個問題的最著名算法（分別為數域篩法和指數微積分法）具有相似的漸近次指數復雜度，可以粗略地近似為 mathcal {O}left( 2^{9sqrt[3]{n}}right) 對于 n 位模數。這意味著針對 RSA 和 DH 等加密方案的 n 位安全性需要大量增加密鑰大?。?048 位用于 112 位安全性，3072 位用于 128 位安全性，7680 位用于 192 位安全性，等等。

相反，對于 ECDLP 問題，最著名的通用求解算法（Pollard's Rho）對于 n 位曲線域具有大約 mathcal{O}left(2^frac{n}{2}right) 的指數復雜度。到目前為止，缺乏已知的次指數破解的算法基本上是使橢圓曲線密碼術具有吸引力的原因，因為對于相同位的安全級別，生成的密鑰可以具有更小的簽名尺寸，相應地增加了帶寬和效率。下表總結了這一點。

表 1：等效安全位的密鑰大小

然而，正如我們將看到的，這也是橢圓曲線密碼學更容易受到量子計算破解的原因。

肖氏算法

現在我們看一下量子場景，即我們考慮一種情況，即已經構建了大型可擴展量子計算機，并且能夠運行復雜的量子算法。眾所周知，Shor 的量子算法可以在多項式時間內解決整數分解問題。讓我們更深入地了解這一主張。

首先，Shor 的算法實際上由兩部分組成：純量子部分（Quantum Fast Fourier Transform，簡稱 QFFT）和純經典的前后處理階段。從復雜性的角度來看，對于 n 位輸入整數，QFFT 的多項式時間復雜度大致為 mathcal{O}left(n^3right)。鑒于經典部分具有類似的復雜性，我們將只考慮量子復雜性。

為了分解 n 位整數，運行 Shor 算法的量子計算機顯然需要至少 n 個（邏輯）量子位的量子存儲器來表示整數，但它還需要額外的工作量子寄存器來增加總量子位計數?？紤]到量子比特數可以被看作是破解的限制資源，因此已經提出了能夠運行 QFFT 以最小化所需量子比特數的電路版本。這些電路的當前技術水平需要大量的量子位，大約是輸入整數位大小的兩倍。

與經典案例一樣，IFP 和 DLP 的情況在量子場景中也相似：Shor 算法可以推廣到離散對數，QFFT 可用于使用大約 2n 個邏輯量子位和具有大致相同的多項式時間復雜度 mathcal{O}left(n^3right)。

橢圓曲線的情況略有不同。同樣，QFFT 可用于在大致三次時間內有效地求解 ECDLP，如上，但由于算法的經典部分需要如何將曲線點表示嵌入到更大的組中，這次所需的量子比特數大約為 10 乘以曲線字段的位大??！

現在，您可能會想說，以上內容暗示橢圓曲線加密聽起來比 RSA 或 DSA 更能抵御量子破解，因為發起破解需要更多的量子位。但如果你仔細觀察，你就會明白為什么恰恰相反！

事實上，請記住橢圓曲線密鑰很小，因為最好的經典破解效率更低。這種差異在量子場景中消失了，因為量子破解具有相似的時間復雜度。而且由于 RSA 和離散對數密碼系統已經需要使用大密鑰來抵抗經典破解，因此它們所需的量子比特數實際上更大！下表總結了這一點：

表 2：被破解的最小邏輯量子比特數

如您所見，隨著安全參數的增加，破解 RSA 所需的量子比特數的增長速度遠遠快于對相同經典安全級別的橢圓曲線進行等效破解。我們幾乎可以說，經典破解使 RSA 和相關的“更具彈性”來面對量子破解。

這不應被解釋為 RSA 對量子破解是安全的：我們在這里考慮的方案都不是。然而，到目前為止，基于 ECC 的密碼學似乎比 RSA 更容易受到量子破解，并且鑒于可用于量子計算的量子比特數量的穩步增加，橢圓曲線密碼學似乎比其他方案更早下架。

量子破解的資源估算

事情變得比這更復雜。最終，我們對這個問題感興趣：“我們需要多少量子資源才能對某個方案實現破解？”回答這個問題需要我們深入挖掘。

我們需要記住，量子計算是由幾個“層”組成的：

· 算法層：更高效的算法等于更高效的破解能力。到目前為止，正如我們上面解釋的，我們只看 QFFT 算法；

· 電路層：相同的算法可以在電路層面以不同的方式實現，使用不同的量子門，使用寬度「使用的量子比特數）和深度（運行時間）等之間的權衡。」將量子算法轉化為量子電路稱為量子編譯器。量子編譯的進步可以導致更有效的破解。

· 邏輯層：電路運行的糾錯（“完美、理想、邏輯”）量子位和門。一個邏輯量子位是通過在一個糾錯結構中將許多低級、嘈雜的物理量子位“組合”在一起來實現的。最常用的方法是所謂的“表面代碼”，它是物理量子位的方形網格，定期進行糾錯。其中一個間隔稱為“表面周期”，目前需要 1 μs 到 1 ms（在不久的將來目標為 200 ns 是“合理的”）。所用量子糾錯碼的緊湊性和糾錯周期速度的改進可以帶來更好的破解性能。

· 物理層：表現出量子效應并被視為“骯臟、嘈雜”的量子比特的基本物理單元。改進這些物理量子位的操作并降低它們的基本噪音，將導致更好的整體性能。

顯然，對這些層中的任何一層進行任何改進都會提高量子破解的效率，并減少發起破解所需的量子資源量。因此，評估必要的資源數量很棘手，因為這使目標不斷變化（主要是變得越來越簡單，成本越來越低）。無論如何，可以說一些關于它的東西，最近的一些作品為這個話題提供了新的思路。

首先，必須考慮發起破解所需的量子位數量可能不是限制因素。本文前一部分提供的評估值，是考慮到所需的最小邏輯量子位數量的下限，但這并不是普遍接受的硬資源衡量標準。事實上，還有更好的：如果我們考慮從物理量子位底層到算法層的完整實現堆棧，我們會看到某些常見的基本量子門比其他的更昂貴。泡利門通?！案菀讓崿F”，因為它們易于實施且快速，而 T 門（Toffoli）則極其困難。事實上，它們非常困難，作為第一個近似值，人們可以簡單地忽略所有其他量子門，而只計算 T 門的數量，作為運行量子算法復雜性的衡量標準?！癟 計數”復雜度恰恰反映了這一點：量子算法的 T 計數復雜度越高，構建能夠運行它的量子計算機就越困難。

鑒于上述情況，量子編譯器通常允許在一種模式下運行，該模式不會優化邏輯量子位的數量，而是優化 T 門的數量。這通常會產生副作用：所需的物理量子位數量大幅增加（因為從物理到邏輯的轉換需要 T 門），并且總體運行時間也會增加。如果某個 T 門只在某個量子位上使用一次，那也是一種浪費，而一旦實現它們，盡可能多地重復使用它們可能會更好。出于這個原因，另一個非常有用的指標是所謂的“T 深度”復雜度，它考慮到一個電路可以在“層”中描述的事實，其中許多 T 門可以在不同的量子位上并行使用。

構建優化 T 計數或 T 深度的電路最終可能會使用比嚴格最小值更多的邏輯層，但它會導致總體上更有效的破解，因為它最大限度地減少了現實世界的資源（實現的時間和成本），最近在量子密碼分析方面的工作采用了這種方法，并且最近發表了新的成果。下表顯示了兩種不同情況下，用來量子破解的資源評估的最新技術水平：當前（現實）基礎物理量子位中的基本噪聲誤差為 10^{-3} 的情況（通過當前最先進的超導技術實現） qubits），或者更樂觀的錯誤率 10^{-5} 的情況，大多數專家似乎都同意在短期內可以實現。

請注意，與上表相比，邏輯量子位的最小數量有所增加，因為如前所述，量子優化的最新結果旨在最小化 T 計數和 T 深度，而不是電路寬度。此外，發起破解所需的時間在很大程度上取決于底層算法單次運行的失敗率，這本身取決于糾錯機制中實現的純度水平，而后者本身取決于在表面代碼。事實證明，在下面的每個場景中，使用的物理量子位數量與運行破解所需的時間之間的比率都非常穩定。出于這個原因，引入了一種新的量子資源衡量標準：兆量子比特天。這是給定 200 ns (5 MHz) 的表面周期（“量子時鐘”）和 {10}^{-3}或每次測量 {10}^{-5} 個錯誤。

表 3：在每個表面周期 200ns 的物理量子位實現中，10^-3 噪音率的量子破解資源評估。

表 4：在每個表面周期 200ns 的物理量子位實現中，10^-5 噪聲率的量子破解資源評估。

請注意以下有趣的事實。對于“低”安全參數（例如 RSA-3072 和 ECDSA-256），破解 RSA 實際上比破解橢圓曲線加密的成本要低。這是最近 Shor 因式分解算法優化結果的結果。

然而，隨著安全參數的增加，我們看到破解 RSA 所需的量子資源穩步增加，而破解橢圓曲線密碼會變得相對容易。

結論

量子資源破解實驗評估出的最新結果，已經開始揭示傳統密碼學對量子計算機不斷提高的性能到底有多脆弱。 ABC小牛社區聯盟一直作為一個吹哨人，讓區塊鏈行業的朋友重視此事。“橢圓曲線密碼學比 RSA 和離散對數更容易受到量子計算機破解”的傳統觀點仍然成立，但截止點已移至大約 160 位的經典安全性，而對于 128 位的安全性差異不是那么重要。這是一個移動目標，主要是最近對 Shor 破解 IFP 和 DLP 的算法進行了優化，因此破解 ECDLP 的實際成本可能會更低。進一步的結果肯定會改變目前的評估。很明顯，只要有足夠多的物理量子位，所有這些密碼系統都可以在幾個小時內破解。

對稱密鑰加密的情況完全不同，但量子資源評估的最新進展仍然有助于更好地確定量子計算機可能對 AES 和 SHA-3 等基元的實際位安全性產生的影響。

原文來自于：