谷歌最新研究：量子計算機能在8小時內破解2048位RSA加密

一項新的研究表明，量子技術將比預期更快地趕上當今的加密標準。所有需要長期（25 年左右）安全存儲數據的人都應該警覺。

許多人擔心量子計算機將能夠破解某些用於發送安全信息的加密代碼。所謂的加密代碼使用“陷門（trapdoor）”函數加密數據，這種函數在一個方向上十分容易執行，但在相反方向上則不然。這就使得加密數據變得容易，但如果沒有特殊密鑰的幫助，解碼數據就非常困難。

這些加密系統一直都不是牢不可破的。相反，它們的安全性是通過經典計算機完成解碼所需的大量時間體現的。現代的加密方法是專門設計的，解碼它們需要很長時間，因此說它們幾乎不可破解。

但是量子計算機改變了這種想法。量子計算機比傳統的計算機功能強大得多，應該能夠輕鬆破解這些代碼。

這就提出了一個重要的問題——量子計算機何時才能強大到可以做到這一點? 在此之後，受此加密形式保護的所有信息都將變得不安全。

因此，計算機科學家們試圖計算出構建這樣一台量子計算機可能需要的資源，以及構建這種機器需要多長時間。此前的答案總是幾十年。

然而現在，谷歌的 Craig Gidney 和瑞典斯德哥爾摩 KTH 皇家理工學院的 Martin Ekera 的研究工作顯示，這個答案需要被修正。研究人員已經找到了一種更有效的方式，讓量子計算機執行代碼破解計算，從而將量子計算機所需的資源減少了幾個數量級。

（來源：麻省理工科技評論）

因此，這些量子計算機比任何人想象的都更接近現實。這一結果將讓政府、軍方和安全機構、銀行以及所有需要保護數據長達 25 年甚至更長時間的人感到不安。

早在 1994 年，美國數學家 Peter Shor 就發現了一種量子算法，其性能優於經典算法。Shor 的算法因子大，是破解基於陷門函數密碼的關鍵因素。

陷門函數是基於乘法過程的，它在一個方向上很容易執行，但在相反的方向上很難執行。例如，將兩個數字相乘很簡單：593 乘以 829 等於 491,597。但是很難算出 491,597 是由哪兩個質數相乘才能得到。

隨著數字的增大，計算變得越來越困難。事實上，計算機科學家認為經典計算機幾乎不可能分解出大於 2048 位的數字，而 2048 位是 RSA 加密最常用的基礎形式。

Shor 證明，一個功能足夠強大的量子計算機可以輕鬆做到這一點，這一結果在整個安全行業一石激起千層浪。

從那以後，量子計算機的功能一直在增強。2012 年，物理學家們用一台四量子位量子計算機來分解 143。然後在 2014 年，他們使用了類似的設備來分解出了 56153。

按照這樣的發展速度，很容易想象，量子計算機應該很快就能超越最好的經典計算機。

但現實或許不是這樣。事實證明，量子因式分解在實際應用中比我們想象的要困難得多。原因是，大型量子計算機存在一個重要難題——噪聲。目前處理噪聲的最佳方法是使用糾錯碼，但是糾錯碼需要大量額外量子位元。

這將顯著增加量子計算機分解 2048 位數字所需的資源。2015 年，研究人員估計，一台量子計算機需要 10 億個量子位元才能可靠地完成這項工作。當今最先進的量子計算機只有 70 個量子位元，這是巨大的差距。

在此基礎上，安全專家很可能已經能夠證明，用量子計算機破解 2048 位 RSA 加密的信息，還需要幾十年的時間。

現在，Gidney 和 Ekera 已經展示了量子計算機如何用 2000 萬個量子位來進行計算。事實上，他們證明，這樣一個裝置只需要8 個小時就可以完成計算。他們表示：“(這一結果)，已經使得分解 2048 位 RSA 整數最多需要多少量子位，下降了近兩個數量級。”

他們的方法側重的是用一種稱為冪模運算的更有效的方法來執行數學運算。冪模運算是將數字提高到某個冪然後除以另一個數，找到余數的過程。

這個過程是 Shor 算法中計算量最大的操作。但是 Gidney 和 Ekera 找到了多種方法來優化它，顯著地減少了運行算法所需的資源。

這是一項有趣的工作，對於所有為未來存儲信息的人來說都具有重要的意義。一台 2000 萬個量子位的量子計算機在今天看來無疑還很遙遠。但專家們需要知道的是，在他們確保信息安全的 25 年內，這種設備是否有可能實現。如果能實現，那麽人們就需要一種新的加密方式了。

事實上，安全專家已經開發出了量子計算機也無法破解的後量子代碼。因此，現在可能已經有方法可以保護數據免受量子計算機未來的攻擊。但是這些代碼現在還沒有作為標準使用。

對於普通人來說，被破解的風險很小。大多數人使用 2048 位加密或類似的方法來完成用互聯網發送信用卡詳細信息的任務。如果這些交易記錄發生在今天，即使在 25 年內被破解，那麽損失也會微乎其微。

但對政府來說，風險會更大。他們今天發出的信息，例如大使館和軍方之間的信息，在 20 年後可能會很重要，因此值得保密。如果這些信息仍然通過 2048 位 RSA 加密或類似的方式發送，那麽這些組織就應該開始擔心了。

-End-

編輯：李亞山

參考：https://www.technologyreview.com/s/613596/how-a-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/

請隨簡歷附上3篇往期作品（實習生除外）