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

2021-02-14 DeepTech深科技

 

一項新的研究表明，量子技術將比預期更快地趕上當今的加密標準。所有需要長期（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/

  DeepTech 招聘 : 科技編輯/記者，實習生  

坐標：北京·國貿

聯繫方式：hr@mittrchina.com

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

相關焦點

  • WannaCryp 勒索病毒使用的 RSA-2048 加密能否攻破?
    2048 加密 AES 的密鑰，每個文件使用一個隨機密鑰。從歷史看來，如果計算能力每1年能夠翻1倍；差不多每10年，傳統計算機的計算能力擴大一千倍（2^10 = 1024），能推進約256 bit(80 digits )。 可以估計，用目前的gnfs 算法，加上足夠的人力財力支撐，最樂觀的估計,分解RSA 2048，也就是40-50年內的事情。
  • A股主題周觀察:量子通信或將更早出現突破性進展
    近期，谷歌的一項研究展示了量子計算機如何在8 個小時就可以分解 2048 位 RSA加密的信息，表明量子技術將比預期更快地破解現有的加密標準，5G時代即將來臨，數據爆發速度將比以往更加猛烈，而摩爾定律將可能於10年內失效，經典計算機的計算能力趨於瓶頸，唯有量子計算的算力增長可以應對指數級別的數據爆發
  • 九章量子計算機能讓中國計算機彎道超車嗎?
    還有問九章能不能挖比特幣的。事實果真如此嗎？我們來看一下。1200億年是算的什麼東西?這次九章開發團隊宣傳使用的計算是高斯玻色取樣，100億樣本的時候，這個東西用世界第一超算富嶽算要1200億年而九章只要10個小時，這個數據把量子計算機推上神壇。
  • 量子計算機越來越近 傳統網絡加密「快不行了」
    當谷歌表示，它已經超越了傳統超級計算機的性能，實現了「量子霸權」時，專家們的反應既興奮又擔憂，他們擔心下一代計算可能會影響到從醫學到金融投資組合優化的一切。伯明罕大學計算機科學學院高級講師克裡斯託夫·佩蒂(Christophe Petit)表示，「如果是300位或400位數字，分解會很困難，即使是使用最大的計算機。沒有有效解決這個問題的方法，而加密技術正是依靠這種難度。」由於量子計算機提供了額外的能量，像因式分解這樣的問題很容易擴展。
  • ECC+RSA雙證書解決方案
    ECC算法的數學理論非常深奧和複雜，在工程應用中比較難於實現，但它的單位安全強度相對較高，它的破譯或求解難度基本上是指數級的，黑客很難用通常使用的暴力破解的方法來破解。RSA算法的特點之一是數學原理相對簡單，在工程應用中比較易於實現，但它的單位安全強度相對較低。
  • 九章量子計算機可以破解網絡密碼嗎?美國會怎樣應對我國量子崛起
    如果有一個量子位，就是2的一次方，一次就可以算出兩個結果；如果是三個量子位， 2的3次方，就是8個計算結果；8個量子位，一次就可以出2的八次方也就是256個結果，以此類推。可不要小瞧指數增長，一張普通白紙，對摺51次，也就是厚度變為2的51次方倍，它的厚度比地球到太陽的距離還要大，人走路大概需要3千多年才能走完這段距離。
  • 量子計算機200秒完成的運算,最強超算需1萬年,谷歌實現量子霸權
    邊策 慄子 發自 凹非寺量子位 出品 | 公眾號 QbitAI量子計算機用3分20秒完成的一項計算，全球最強大的超算Summit要花1萬年。這個成果，來自谷歌最新的量子計算研究，發表在NASA官網上。論文宣布，「量子霸權」實現了。
  • 量子計算機威脅到網絡加密只是一個時間問題
    1994 年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。
  • 微軟:五年內造出擁有100個拓撲量子比特的量子計算機
    因為量子計算一旦落地，將從根本上重新定義計算這件事，我們所學的每一個算法都可能要重寫，我們在這個領域所取得的所有學位都可能需要回爐，所有成果都需要翻新。舉個例子，今天的區塊鏈和加密數字貨幣普遍依賴 256 位的哈希函數和非對稱加密方案。在經典的馮諾依曼計算機體系中，即便我們調動全球的算力，破解一個密碼、或者尋找一次哈希碰撞也需要數萬年的時間。
  • MIT數學家Peter Shor:量子計算機威脅到網絡加密只是時間問題
    破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。 如今，量子計算機已經成為現實，但它們分解超過兩位數數字的能力依然處於初級水平。但是，量子計算機威脅到網絡加密只是一個時間問題。 《自然》（Nature）採訪了Shor，詢問他如何看待自己研究的影響力，以及網絡安全的未來將走向何方。
  • 量子計算機威脅到網絡加密只是一個時間問題|對話應用數學家Peter...
    1994 年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。
  • 谷歌開源量子計算軟體原始碼,便利科學家利用量子計算機
    繼開源tensorflow、caffe等深度學習開發框架後，當地時間10月24日，谷歌在自己的官方博客上宣布，開源量子計算軟體OpenFermion，從而讓科學家更方便的使用量子計算機。谷歌稱，這次開放的是OpenFermion的原始碼，可供用戶免費使用，化學家和材料學家可以利用谷歌軟體改編算法和方程，使之能在量子計算機上運行。
  • 對話Peter Shor: 量子計算機威脅到網絡加密只是一個時間問題
    1994年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。如今，量子計算機已經成為現實，但它們分解超過兩位數數字的能力依然處於初級水平。
  • 對話Peter Shor:量子計算機威脅到網絡加密只是一個時間問題
    1994年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。
  • 我國量子計算機實現量子霸權,計算速度比谷歌快了100億倍
    去年9月，谷歌也宣稱它實現了量子霸權。當時，谷歌的53個量子比特的計算機「懸鈴木」在幾分鐘之內完成了一個數學算法，而當時超級計算機完成這個算法需要上萬年的時間。等效來看，我們的「九章」量子計算機比「懸鈴木」的計算速度快了100億倍。不過，這兩種系統的工作方式是不同的。
  • 關於RSA加密破解利用D-Wave量子計算機做大數分解的論文模擬驗證
    作者：李利鵬 匯真科技董事長 吳明華 匯真科技研究員近期，上海大學研究小組王超團隊在 《中國科學：物理力學與天文學（Physics
  • 隨著替代技術的發展,量子計算機的競爭加劇
    大型公司長期以來一直不願採用的用於構建量子計算機的技術正在蓬勃發展。在過去的十年中，隨著量子計算已從學術活動轉變為大型企業，聚光燈主要集中在一種方法上-IBM和英特爾等技術巨頭所採用的微小超導環路。去年，谷歌宣稱它已經通過量子機器實現了「量子優勢」，該量子機器首次執行了超出最佳經典計算機實際能力的特殊計算。
  • 九章量子計算機實現量子霸權?
    雖然數學家們考量了很多角度，這個問題屬於幾乎不可能有經典計算機短時間內就能算出來的算法啊，幾乎不敢把話說死，但是你敢說打包票。就像一個經典的比喻。一陣大風吹過一對零件，能吹出一架波音飛機嗎？你說絕對不可能，但又好像不是完全不可能，你找不到一個絕對的邊界。
  • 量子計算機離我們的生活還有...
    簡單來說就是一個執行機構，能根據輸入和自己當前的狀態決定下一個狀態及輸出。人類目前的計算設備都屬於圖靈機。因此，量子計算機能解決的問題，傳統計算機都能解決；反之亦然。實際上，現在還不知道哪些問題屬於量子計算機能解決而傳統計算機無法解決的。
  • 中國量子計算機的崛起
    （圖片來源：BGR）舉個例子，量子計算機可以輕而易舉的就破解信息安全機制。現在你查看的郵件和銀行數據都是由安全機密系統所保護著的，藉由你給所有使用者不同組的公開密匙來加密只有你能解密的信息。但如果應用基於量子計算邏輯的 shor's algorithm（見下文），整個分解的過程就會被縮減位log₂N量級的運算次數，這就意味著目前最安全的加密方式，幾分鐘就可以破解，而經典計算機可能需要永遠。但通過量子計算機，迅速破解信用卡、國家機密和其它機密資料都不在話下。 量子計算機可以取代經典計算機嗎？