量子計算將能分解任意極大整數,RSA加密或成擺設

2020-11-24 雷鋒網

就算是一臺超級計算機有可能在數年的時間內計算出任意質因數，這也是得不償失的。為了科學地解決這個問題，麻省理工學院（MIT）的科學家找到了明確的方法。今天，《科學》雜誌最新發表的一篇論文顯示，量子計算機有史以來第一次以可擴展的方式，實現了Shor算法。

據外媒Engadget報導，MIT和 Innsbruck大學的計算機科學家組裝了一臺5量子比特的量子計算機，它將能夠用Shor算法完成對數字15的質因數分解。他們研發了一臺量子計算機原型，然後使用一系列離子，藉助雷射脈衝來在4個量子比特上執行Shor算法，令其分解數字，第5個量子比特則用於儲存和輸出結果。目前的結果是，這臺計算機不僅能夠比現有量子系統更高效地計算出方案，而且區間縮放相對容易。

據維基百科解釋，Shor算法（秀爾算法）是一個在1994年發現，以數學家彼得·秀爾命名，針對整數分解的量子算法（在量子計算機上面運作的算法）。比較不正式的表述是，它解決題目如下：給定一個整數N，找出他的質因數。

在一個量子計算機上面，要分解整數N，秀爾算法的運作需要多項式時間（時間是log N的某個多項式這麼長）。更精確的說，這個算法花費O((log N)3)的時間，展示出質因數分解問題可以使用量子計算機以多項式時間解出，因此在複雜度類BQP裡面。這比起傳統已知最快的因數分解算法，普通數域篩選法，其花費次指數時間——大約O(e1.9 (log N)1/3 (log log N)2/3)，還要快了一個指數的差異。

秀爾算法的重要性不言而喻，實現它我們就有望破解已被廣泛使用的公開密鑰加密方法——RSA加密算法。RSA加密算法是一種非對稱加密算法，在公開密鑰加密和電子商業中RSA被廣泛使用，其高度可靠的秘密在在於：對極大整數做因數分解的極大難度。也就是說，對一極大整數做因數分解愈困難，RSA算法愈可靠。但是，假如有人找到一種快速因數分解的算法的話，那麼用RSA加密的信息的可靠性就肯定會極度下降。此前，世界上還沒有任何攻擊RSA算法的可靠方式。

然而，秀爾算法展示了因數分解這問題在量子計算機上可以很有效率地解決，所以一個足夠大的量子計算機可以破解RSA。這對於建立量子計算機和研究新的量子計算機算法，是一個非常大的動力。

圖片來源：http://gizmodo.com/

雷鋒網原創文章，未經授權禁止轉載。詳情見轉載須知。

相關焦點

  • 科普問答 | 現有的量子計算機能否破解rsa等商用軍用加密技術?
    群友問：現有的量子計算機能否破解rsa等商用軍用加密技術?實用型的通用量子計算機能做出嗎?如果不能，是因為計算原理導致的嗎?(Shor算法——以數學家彼得·秀爾命名，是一個在1994年發現的，針對整數分解這題目的的量子算法(在量子計算機上面運作的算法)。它解決如下題目:給定一個整數N，找出他的質因數。）——引用來源：百度 在計算複雜度理論中，通常把需要多項式時間的算法視為快速計算。多項式時間是指一個大小為N的問題的求解時間不大於N的多項式倍數（N，k為常數）。
  • 量子計算核心突破!Shor算法實現或使密碼成擺設
    過去我們認為RSA不可破解，但隨著量子計算的發展，RSA的安全性正受到挑戰。今天刊發在《科學》雜誌的最新論文，量子計算機有史以來第一次以可擴展的方式，用Shor算法完成對數字15的質因數分解。IBM 物理科學高級主管Mark Ritter表示，將Shor算法實現出來這件事，能夠與經典計算中的『Hello，World』 相提並論。
  • 未來的量子計算機將在8小時內破解2048位RSA加密
    毫無疑問，許多人擔心量子計算機將能夠破解全球最流行的加密技術中的70％以上，使它們變得無用和過時，並將他們保護的敏感數據暴露給任何想要讀取的人。但是，主要的加密技術是使用所謂的「活板門」數學函數對數據進行加密的技術，這些函數可以在一個方向上輕鬆地工作，而在另一個方向上卻不行。
  • 素數判別和整數分解存在多項式算法
    在這個密碼體制中，對電文的加密過程是公開的，但是，你僅知道加密過程而未被告知解密過程則不可能對電文進行解密。他們的體制就是依靠這樣一個事實：我們能夠很容易地將兩個百位大素數乘起來；反過來，要分解一個200位的整數則幾乎不可能，超過400位，計算機已經不能承受。
  • 量子計算機能做什麼？
    量子計算領域這幾年發展得如火如荼，量子計算機的比特位數也在不斷增加。2019年12月，谷歌宣布實現「量子霸權」——量子計算機在某一「特定問題」上的計算速度超過傳統計算機，這標誌著量子計算機的發展進入了一個新階段。但「特定問題」只是一些毫無價值的問題，量子計算機作為一個工具，它將來究竟能為我們做些什麼有用的事情呢？
  • 量子計算機分解的最大質因數有新紀錄了!
    我們知道破解加密涉及到相當複雜的技術，破解與反破解總是在不斷升級之中。現在由於量子技術的發展，量子計算機有一天可能會通過破解加密而威脅到網際網路的安全。最近量子計算初創公司Zapata與IBM合作開發了一種分解大數字的新方法，成功將其應用到迄今為止量子計算機所能分解的最大質因數上，該進展可能讓量子技術距離加密破解又近了一步。
  • 量子計算機能做什麼用途？
    量子計算機能做什麼？量子計算領域這幾年發展得如火如荼，量子計算機的比特位數也在不斷增加。2019年12月，谷歌宣布實現「量子霸權」——量子計算機在某一「特定問題」上的計算速度超過傳統計算機，這標誌著量子計算機的發展進入了一個新階段。
  • 「九章」問世-量子計算將如何影響區塊鏈技術?
    量子計算能否破解區塊鏈密碼？量子計算如此厲害，區塊鏈技術是否還能夠保障用戶密碼安全？這也成了行業內外備受關注的話題。「在我們的有生之年，量子計算只能用於解決特定問題，是不能取代通用計算機的。鄒均認為，目前存在公認的兩個算法會對區塊鏈產生影響：一個是破局公鑰系統的Shor算法，該算法能對基於大整數質數因子分解難題（RSA)算法，或者基於橢圓曲線的對數分解難題（ECC)算法有指數級加速，也就是說，Shor算法能將經典算法的指數級複雜性降低到多項式時間複雜度，從而破解公鑰系統。另一個是Grover算法，該算法能將經典搜索算法降低一個開平方根的層度。
  • 量子計算機威脅到網絡加密只是一個時間問題
    1994 年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。
  • 數學家Peter Shor：量子計算機威脅網絡加密，只是時間
    而在25年前，美國應用數學家Peter Shor提出Shor算法，證明了如何讓量子計算變得可行，量子計算會如何威脅到數據。量子計算機以量子比特為單位處理信息——量子比特對應經典比特，但能同時表示0和1。已知量子態對噪聲非常敏感，這會造成信息丟失。Shor提出的誤差修正技術能檢測到噪聲導致的錯誤，帶來了一種讓量子信息更抗噪的方法。
  • 終於還是要講到這一篇——RSA算法原理
    1.質數：只能分解成1和它自身乘積的，大於1的自然數。2.互質：最大公因數是1的多個自然數之間就是互質關係。注意，互質的整數不一定都是質數。3.模運算：mod，即計算餘數的運算，如x mod yn，表示x除以y的餘數是n。上述數學概念都是中學學過的，下面的定理就進入數論部分了。
  • 遇事不決，量子力學；量子計算，地覆天翻
    一位來自赫赫有名的貝爾實驗室的天才，彼得·秀爾（Peter Shor）提出了量子質因子算法，並證明了量子計算機可以完成對數計算，且速度遠勝傳統計算機。關於這個質因子算法我想說一說。我們知道現在使用的銀行卡都是帶有加密算法的，當今主流的非對稱（公鑰）加密算法，如RSA加密算法，大多數都是基于于大整數的因式分解或者有限域上的離散指數的計算這兩個數學難題。
  • Peter Shor：量子計算機威脅到網絡加密只是時間問題
    1994年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。
  • 量子科技的兩塊試驗田:量子計算與量子通信丨前途有「量」
    >接下來，商業化將成為「量子」進一步的努力方向。 將量子力學和資訊理論合併的想法出現在20世紀70年代，但很少引起關注，直到1982年，物理學家理察·費曼（Richard Feynman）發表了一次演講，他在演講中推理出基於經典邏輯的計算不可能遷移到處理描述量子現象的計算。然而，基於量子現象配置的計算來模擬其他量子現象，就不會遇到同樣的瓶頸。
  • 量子科技的兩塊試驗田：量子計算與量子通信丨前途有「量」
    ，接下來，商業化將成為「量子」進一步的努力方向。現階段的量子計算機能夠在某些計算問題的解決上，如整數分解（這是RSA加密的基礎），大大快於經典計算機。1994年，Peter Shor又開發了一種整數分解的量子算法。 儘管自20世紀90年代末以來，實驗進展不斷，但大多數研究人員認為，「容錯量子計算」仍然是一個相當遙遠的夢想。
  • 後量子加密究竟是什麼?
    黑客也可能採用某些針對特定任務進行優化的量子算法。其中一種算法由AT&T公司貝爾實驗室的Lov Grover於1996年提出，其能夠幫助量子計算機更快地搜索可能的排列。另一種由Peter Shor於1994年提出，當時身在貝爾實驗室的他如今已經成為麻省理工學院教授。這種算法能夠幫助量子計算機以極快的速度找到任意整數的質因數。
  • 量子計算機刷屏,量子計算到底是什麼!
    現在你查看的郵件和銀行數據都是由安全機密系統所保護著的，藉由你給所有使用者不同組的公開密匙來加密只有你能解密的信息。比如現在應用最廣的RSA 加密方式 （由Ronald Rivest, Adi Shamir, and Leonard Adleman）是基於一個簡單的共識：即基於經典計算機的邏輯運算法則下，分解整數的質因數過程是一個複雜的計算過程。
  • 什麼是量子密碼學?RSA加密算法又是什麼?量子計算機厲害嗎?
    」是一門通過量子計算機強大的計算能力進行加密/解密的新興學科。　　作為一種非對稱加密算法，目前世界上還沒有任何可靠的攻擊RSA算法的方式。但該神話將被量子計算機終結。但是，谷歌的科學家於2019年發表的一個研究結果顯示，使用量子計算機僅用8小時就破解了2048位長的RSA加密信息，這個運算量對於超級計算機而言則需要80年！
  • 量子計算和加密貨幣
    量子計算是計算領域的下一個巨大飛躍。但這也可能會造成加密技術的巨大破壞。我們來一起探索一下這項新技術。本文探討什麼是量子計算機以及它們對加密行業造成什麼樣的威脅。科學家和研究人員開始利用量子物理學的力量來構建功能強大的計算機，並具有破解世界級別的加密算法的能力。除了區塊鏈以外，量子計算還可能威脅全球金融系統，機密情報機構以及手機上所有數據的安全。
  • 量子計算機威脅到網絡加密只是一個時間問題|對話應用數學家Peter...
    25年前，Peter Shor證明了如何讓量子計算變得可行，同時也表明了量子計算會如何威脅到數據；以下是《自然》對他的採訪。1994 年，他第一次發現了[2]使用理論量子計算機的方法，震驚了物理學界和計算機科學界——這種方法可能有用但也令人擔憂。他寫了一種算法，可以讓量子計算機以閃電般的速度將整數分解質因數。今天的大部分網絡流量的安全性都是由基於大質數的加密技術來保證的。破解這些密碼很難，因為經典計算機分解大整數質因數的速度很慢。