沒有人知道什么時(shí)候，但威脅加密的量子機(jī)器即將到來。以下是研究人員如何使用量子力學(xué)破解非對(duì)稱密碼學(xué)中的大整數(shù)。
量子計(jì)算繼續(xù)存在于實(shí)際應(yīng)用和理論推測(cè)之間的模糊空間，但它正在接近現(xiàn)實(shí)世界的使用。量子計(jì)算機(jī)更有趣的用例之一是現(xiàn)代互聯(lián)網(wǎng)密碼學(xué)。
量子計(jì)算和量子比特
量子計(jì)算之所以得名，是因?yàn)樗蕾囉趤喸?span id="xvhqsm6" class="wpcom_tag_link">粒子的特性，而亞原子粒子的規(guī)律對(duì)我們這些植根于宏觀世界的人來說似乎很奇怪。特別是，量子計(jì)算機(jī)使用qubits（量子位）而不是我們從傳統(tǒng)計(jì)算機(jī)系統(tǒng)中知道的二進(jìn)制數(shù)字（位）。
量子比特本質(zhì)上是概率性的，而比特是確定性的。一點(diǎn)最終歸結(jié)為一個(gè)物理開關(guān)——盡管它非常小，只有幾納米。位是二進(jìn)制的：開或關(guān)，真或假，0 或 1。
量子比特并非如此。
量子比特的物理基礎(chǔ)可以是多種現(xiàn)象，例如電子的自旋或光子的極化。這是一個(gè)引人入勝的話題：連接想象和現(xiàn)實(shí)的線性方程領(lǐng)域。量子力學(xué)被認(rèn)為是對(duì)潛在現(xiàn)實(shí)的解釋，而不是描述，并且是高度計(jì)算復(fù)雜性的根源。
量子比特的狀態(tài)被描述為兩種可能狀態(tài)的線性疊加。一旦觀察到，狀態(tài)就會(huì)被解析為真或假。但是，相同的輸入不一定會(huì)解析為相同的輸出，并且未觀察到的狀態(tài)只能用概率術(shù)語來描述。
從經(jīng)典物理學(xué)的角度來看，更令人驚訝的是，量子計(jì)算機(jī)中的量子比特可以同時(shí)存在多個(gè)狀態(tài)。當(dāng)計(jì)算機(jī)對(duì)一個(gè)量子比特的狀態(tài)進(jìn)行采樣時(shí)，它會(huì)分解為一個(gè)非此即彼（稱為波函數(shù)崩潰）。
密碼學(xué)中的量子計(jì)算
從科學(xué)和哲學(xué)的角度來看，所有這些都是相當(dāng)有趣的。例如，量子計(jì)算機(jī)的功能驗(yàn)證了觀察對(duì)粒子的影響，并表明確實(shí)，上帝確實(shí)在與宇宙擲骰子。但在這里，我們關(guān)注的是量子計(jì)算在我們?nèi)粘Ｉ钪胁粩嘣黾拥哪芰Φ膶?shí)際方面。未來幾年，最深遠(yuǎn)的影響可能是密碼學(xué)。
從量子計(jì)算到密碼學(xué)最著名的途徑是發(fā)生在 1994 年的理論突破：Shor 算法。從理論上講，該算法展示了量子圖靈機(jī)有效解決使用傳統(tǒng)計(jì)算機(jī)難以解決的一類問題的能力：大整數(shù)的因式分解。
如果您熟悉Diffie-Hellman和 RSA 等非對(duì)稱密碼系統(tǒng)算法，您就會(huì)知道它們依賴于求解大數(shù)因子的難度。但是如果量子計(jì)算解決了這個(gè)問題呢？
用量子力學(xué)破解大整數(shù)
Shor 的算法和一些其他算法利用量子力學(xué)來破解非對(duì)稱密碼學(xué)核心的單向函數(shù)。絕熱量子計(jì)算也被用于攻擊分解。
Shor 和其他算法依賴于量子計(jì)算機(jī)憑借量子位居住在多種狀態(tài)的能力。然后，他們以允許采樣中高度概率的方式對(duì)這些量子比特（這會(huì)破壞它們的狀態(tài)）進(jìn)行采樣。本質(zhì)上，我們將“給定數(shù)字的因素是什么”這個(gè)問題交給了神秘的看不見的世界，在那里粒子屬性可以以多種狀態(tài)存在。然后，我們查詢這些屬性以獲得最可能的答案。（是的，這確實(shí)有效。）
Shor 算法所分解的最大數(shù)是 21。絕熱量子計(jì)算已成功分解了 143。
這些算法復(fù)雜且令人印象深刻，但到目前為止，它們的數(shù)量微不足道。RSA 的當(dāng)前標(biāo)準(zhǔn)是 2048 位，也就是 617 位！然而，在攻擊數(shù)字 143 時(shí)，研究人員在不知不覺中揭示了一種允許更大數(shù)字的方法，至少在理論上是這樣。一個(gè)例子是56,153，與破壞現(xiàn)實(shí)世界密碼系統(tǒng)所需的數(shù)量相比，這仍然是一個(gè)相對(duì)較小的數(shù)字。它還取決于不能用于所有數(shù)字的還原技巧。
對(duì)網(wǎng)絡(luò)安全基礎(chǔ)設(shè)施的威脅
我們現(xiàn)在所知道的是，對(duì)非對(duì)稱算法的量子攻擊的基本方面正在被解決。該技術(shù)將以多快的速度發(fā)展到可以接近更大數(shù)量的程度？
有趣的是，我們每天使用的對(duì)稱算法（如 AES）并不十分容易受到量子算法的攻擊。Grover 的算法是適用的算法。如果使用 256 位密鑰，即使在理論上，也無法比經(jīng)典算法進(jìn)一步減少攻擊這些算法所需的時(shí)間。
然而，大多數(shù)對(duì)稱安全通信通過非對(duì)稱交換建立其密鑰。因此，當(dāng)今的大多數(shù)網(wǎng)絡(luò)流量都容易受到高級(jí)量子計(jì)算攻擊。如果攻擊者可以發(fā)現(xiàn)在交互開始時(shí)建立的密鑰，那么再多的對(duì)稱加密都將無用。
因此，對(duì)網(wǎng)絡(luò)安全基礎(chǔ)設(shè)施的威脅是真實(shí)存在的。讓我們想一想游戲中的動(dòng)態(tài)。首先要考慮的是純粹的經(jīng)濟(jì)和訪問。目前，只有現(xiàn)金充裕的組織才有能力修補(bǔ)這些東西。IBM、谷歌和中國(guó)的研究科學(xué)家正在爭(zhēng)奪生產(chǎn)可行系統(tǒng)的領(lǐng)導(dǎo)地位，以及許多大學(xué)的努力。在幕后，像美國(guó)國(guó)家安全局這樣的政府機(jī)構(gòu)肯定不會(huì)閑著。事實(shí)上， NSA對(duì)公共密碼學(xué)和量子計(jì)算問題有自己的看法。
不斷發(fā)展的量子計(jì)算安全性
小規(guī)模參與者不太可能獲得足以攻擊現(xiàn)代非對(duì)稱密鑰的量子計(jì)算能力，直到大型機(jī)構(gòu)完成它很久之后。這意味著我們處于一個(gè)很長(zhǎng)一段時(shí)間內(nèi)，安全基礎(chǔ)設(shè)施可以響應(yīng)量子計(jì)算的動(dòng)態(tài)而發(fā)展。
沒有人知道真正具有加密威脅的量子機(jī)器何時(shí)會(huì)出現(xiàn)，但它似乎很可能會(huì)發(fā)生。處理這個(gè)問題的兩個(gè)標(biāo)準(zhǔn)是系統(tǒng)中量子比特的數(shù)量和這些量子比特的壽命。
量子比特受到所謂的退相干的影響。熵總是把電子和光子的微妙集合帶走。問題是量子比特的數(shù)量和壽命都很難量化。對(duì) RSA 2048 密鑰進(jìn)行實(shí)際的可重復(fù)攻擊需要多少量子比特？有人說幾十，有人說幾百萬。需要多少連貫性？有人說幾百納秒，有人說幾分鐘。
而所有這些都可以被前面提到的預(yù)處理算法的棘手使用等技術(shù)所顛覆。誰知道現(xiàn)在聰明的本科生正在想出一種新的方法。在量子機(jī)器上分解 143 的人直到兩年后才意識(shí)到他們也破解了 56,153 。
后量子密碼學(xué)
條條大路通后量子世界，很多人已經(jīng)在為之努力。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院目前正在舉辦開發(fā)抗量子算法的競(jìng)賽。其中一些努力正在取得成果。
歸根結(jié)底，基于越來越真實(shí)的結(jié)果，我們可以說對(duì)密碼學(xué)的量子威脅是真實(shí)存在的。但就目前而言，它不僅僅是被反補(bǔ)貼力量所抵消。我們最終可能不得不告別一些我們心愛的舊算法，但新的算法將取代它們。
在接下來的十年里，這將是一場(chǎng)有趣的舞蹈。
