量子威脅:量子計算和密碼學

海擁科技 發佈 2022-05-23T13:52:36.060106+00:00

沒有人知道什麼時候,但威脅加密的量子機器即將到來。以下是研究人員如何使用量子力學破解非對稱密碼學中的大整數。量子計算繼續存在於實際應用和理論推測之間的模糊空間,但它正在接近現實世界的使用。量子計算機更有趣的用例之一是現代網際網路密碼學。

沒有人知道什麼時候,但威脅加密的量子機器即將到來。以下是研究人員如何使用量子力學破解非對稱密碼學中的大整數。

量子計算繼續存在於實際應用和理論推測之間的模糊空間,但它正在接近現實世界的使用。量子計算機更有趣的用例之一是現代網際網路密碼學。

量子計算和量子比特

量子計算之所以得名,是因為它依賴於亞原子粒子的特性,而亞原子粒子的規律對我們這些植根於宏觀世界的人來說似乎很奇怪。特別是,量子計算機使用qubits(量子位)而不是我們從傳統計算機系統中知道的二進位數字(位)。

量子比特本質上是概率性的,而比特是確定性的。一點最終歸結為一個物理開關——儘管它非常小只有幾納米。位是二進位的:開或關,真或假,0 或 1。

量子比特並非如此。

量子比特的物理基礎可以是多種現象,例如電子的自旋或光子的極化。這是一個引人入勝的話題:連接想像和現實的線性方程領域。量子力學被認為是對潛在現實的解釋,而不是描述,並且是高度計算複雜性的根源。

量子比特的狀態被描述為兩種可能狀態的線性疊加。一旦觀察到,狀態就會被解析為真或假。但是,相同的輸入不一定會解析為相同的輸出,並且未觀察到的狀態只能用概率術語來描述。

從經典物理學的角度來看,更令人驚訝的是,量子計算機中的量子比特可以同時存在多個狀態。當計算機對一個量子比特的狀態進行採樣時,它會分解為一個非此即彼(稱為波函數崩潰)。

密碼學中的量子計算

從科學和哲學的角度來看,所有這些都是相當有趣的。例如,量子計算機的功能驗證了觀察對粒子的影響,並表明確實,上帝確實在與宇宙擲骰子。但在這裡,我們關注的是量子計算在我們日常生活中不斷增加的能力的實際方面。未來幾年,最深遠的影響可能是密碼學。

從量子計算到密碼學最著名的途徑是發生在 1994 年的理論突破:Shor 算法。從理論上講,該算法展示了量子圖靈機有效解決使用傳統計算機難以解決的一類問題的能力:大整數的因式分解。

如果您熟悉Diffie-Hellman和 RSA 等非對稱密碼系統算法,您就會知道它們依賴於求解大數因子的難度。但是如果量子計算解決了這個問題呢?

用量子力學破解大整數

Shor 的算法和一些其他算法利用量子力學來破解非對稱密碼學核心的單向函數。絕熱量子計算也被用於攻擊分解。

Shor 和其他算法依賴於量子計算機憑藉量子位居住在多種狀態的能力。然後,他們以允許採樣中高度概率的方式對這些量子比特(這會破壞它們的狀態)進行採樣。本質上,我們將「給定數字的因素是什麼」這個問題交給了神秘的看不見的世界,在那裡粒子屬性可以以多種狀態存在。然後,我們查詢這些屬性以獲得最可能的答案。(是的,這確實有效。)

Shor 算法所分解的最大數是 21。絕熱量子計算已成功分解了 143。

這些算法複雜且令人印象深刻,但到目前為止,它們的數量微不足道。RSA 的當前標準是 2048 位,也就是 617 位!然而,在攻擊數字 143 時,研究人員在不知不覺中揭示了一種允許更大數字的方法,至少在理論上是這樣。一個例子是56,153,與破壞現實世界密碼系統所需的數量相比,這仍然是一個相對較小的數字。它還取決於不能用於所有數字的還原技巧。

對網絡安全基礎設施的威脅

我們現在所知道的是,對非對稱算法的量子攻擊的基本方面正在被解決。該技術將以多快的速度發展到可以接近更大數量的程度?

有趣的是,我們每天使用的對稱算法(如 AES)並不十分容易受到量子算法的攻擊。Grover 的算法是適用的算法。如果使用 256 位密鑰,即使在理論上,也無法比經典算法進一步減少攻擊這些算法所需的時間。

然而,大多數對稱安全通信通過非對稱交換建立其密鑰。因此,當今的大多數網絡流量都容易受到高級量子計算攻擊。如果攻擊者可以發現在交互開始時建立的密鑰,那麼再多的對稱加密都將無用。

因此,對網絡安全基礎設施的威脅是真實存在的。讓我們想一想遊戲中的動態。首先要考慮的是純粹的經濟和訪問。目前,只有現金充裕的組織才有能力修補這些東西。IBM、谷歌和中國的研究科學家正在爭奪生產可行系統的領導地位,以及許多大學的努力。在幕後,像美國國家安全局這樣的政府機構肯定不會閒著。事實上, NSA對公共密碼學和量子計算問題有自己的看法。

不斷發展的量子計算安全性

小規模參與者不太可能獲得足以攻擊現代非對稱密鑰的量子計算能力,直到大型機構完成它很久之後。這意味著我們處於一個很長一段時間內,安全基礎設施可以響應量子計算的動態而發展。

沒有人知道真正具有加密威脅的量子機器何時會出現,但它似乎很可能會發生。處理這個問題的兩個標準是系統中量子比特的數量和這些量子比特的壽命。

量子比特受到所謂的退相干的影響。熵總是把電子和光子的微妙集合帶走。問題是量子比特的數量和壽命都很難量化。對 RSA 2048 密鑰進行實際的可重複攻擊需要多少量子比特?有人說幾十,有人說幾百萬。需要多少連貫性?有人說幾百納秒,有人說幾分鐘。

而所有這些都可以被前面提到的預處理算法的棘手使用等技術所顛覆。誰知道現在聰明的本科生正在想出一種新的方法。在量子機器上分解 143 的人直到兩年後才意識到他們也破解了 56,153 。

後量子密碼學

條條大路通後量子世界,很多人已經在為之努力。美國國家標準與技術研究院目前正在舉辦開發抗量子算法的競賽。其中一些努力正在取得成果。

歸根結底,基于越來越真實的結果,我們可以說對密碼學的量子威脅是真實存在的。但就目前而言,它不僅僅是被反補貼力量所抵消。我們最終可能不得不告別一些我們心愛的舊算法,但新的算法將取代它們。

在接下來的十年裡,這將是一場有趣的舞蹈。

關鍵字: