題:
通過Quantum Computers不能破解哪些類型的加密？
Tobias Kienzler
2014-01-03 20:15:59 UTC
view on stackexchange narkive permalink

最近有一篇文章 NSA試圖構建可以破解大多數加密類型的量子計算機。現在，我對NSA嘗試進行任何 1 sup>感到驚訝，但是讓我感到困惑的是“最”一詞-因此，什麼加密算法是已知的，並且經過充分測試卻不是嚴重易受量子計算的影響嗎？

1）是的，如果他們有一個秘密的算命部門，我什至不會感到驚訝...
量子計算機仍然遙不可及。這個概念依賴於使用位，當不被觀察時，它們都是1和0，因此能夠使用給定空間中可以表示的所有值進行計算-只需一次計算。聽起來如此浪漫，我至今尚未聽到用這種方式進行計算的方法，同時又不對其進行觀測。
不要僅僅因為NSA這麼大的組織就試圖建立某種他們希望很快就能成功部署的東西而已。因為軍備競賽是種族，所以組織通常會研究一些東西，因為他們不想在競爭對手部署它們時才剛剛開始。如果國家安全局對了解量子計算的人們建立起一種大腦信任，那麼他們也許能夠在競爭對手之前部署一個，並且不太可能措手不及。
我關心的不是NSA，他可能還會使用一些不太愉快的方法來獲取秘密，而是QC的含義
為什麼量子計算機也不能啟用相應更強的加密？
-1
最好在現實世界中使用OTP，而對於虛擬世界，則使用對稱算法+ 256位密鑰。看看這個http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance
@November稍微修改一下[這個不錯的Gedankenexperiment]（http://physics.stackexchange.com/a/3162/97），假設您的一個朋友在天冷之前就出門了。你們倆都不知道他們帶了多少手套（如果有的話），但是他們倆都知道剩下的手套在哪裡。並且，由於嚴寒，您的朋友一旦發現一些遺失的手套，便會回家帶回剩下的手套。假設您的朋友想在外面見面的朋友也一樣。現在，觀察他們的一些手套是否在家中-瞧，您可以確定他們是在戶外見面還是回家
@November您的知識已經過時。已經對qbits進行了計算。只是不是很多。但是這個概念沒有什麼“浪漫的”，它已經在實踐中得到了證明。
感謝您糾正我。這非常令人興奮，您是否有一個鏈接可以對此進行更深入的說明？
@November這才剛出來：http://arxiv.org/pdf/1512.02206v1.pdf這有點技術性，需要相當多的知識才能使用，但是我想這裡的大多數人是:-)
五 答案:
Thomas Pornin
2014-01-03 21:01:05 UTC
view on stackexchange narkive permalink

像往常一樣，談論技術主題的新聞界往往對細節一無所知...

假設可以構建真正的 Quantum計算機，則：

RSA和依賴整數分解的難度的其他算法（例如Rabin）是敬酒的。 Shor算法非常有效地分解大整數。
  • DSA，Diffie-Hellman ElGamal和其他依賴於離散對數硬度的算法破碎。 Shor算法的變體也適用。請注意，每個組都是如此，因此這些算法的橢圓曲線變體效果也不會更好。

  • 對稱加密弱了；也就是說，量子計算機可以在時間 2 n / 2 sup> 中搜索大小為 2 n sup> 的空間。這意味著128位AES密鑰將降級為64位密鑰的強度-但是，請注意，這些是 2 64 sup> 量子-計算 i>操作；您不能應用通過FPGA和GPU進行的研究得出的數據，並且盲目地假設，如果可以完全 構建量子計算機，那麼可以廉價地構建和運行量子計算機。

  • 類似地，哈希函數對各種攻擊的抵抗力也會類似地降低。粗略地講，輸出為 n 位的哈希函數將抵抗強度為 2 n / 2 sup> 的原像，並且碰撞到 2 n / 3 sup> （傳統計算機上的數字為 2 n sup> 和 2 n / 2 sup > ）。如今，SHA-256在抵禦衝突方面仍具有與170位哈希函數一樣強大的功能，即優於“完美的SHA-1”。

    • 因此，如果證明要製造量子計算機，對稱加密不會受到嚴重破壞。即使可以很便宜地構建它，實際的對稱加密和散列函數算法仍然會提供相當大的阻力。但是，對於非對稱加密，這將意味著麻煩。儘管如此，我們仍然知道幾種不對稱的算法，這些算法不知道有效的基於QC的攻擊，特別是基於晶格縮減（例如NTRU）和古老的 McEliece加密的算法。由於各種原因，這些算法在當今並不十分流行（NTRU的早期版本很弱；有專利； McEliece的公鑰很大，等等），但是有些仍然

    在可以構建高效量子計算機的假設下進行密碼學的研究稱為後量子密碼學。

    我個人不要相信僅僅8000萬美元的預算就能使NSA步履維艱。 IBM在該主題上進行了數十年的研究，並花了很多錢，而且他們最好的原型並不令人驚訝。 NSA在量子計算的概念上花了一些錢是很合理的。畢竟，那是他們的工作，如果納稅人的錢沒有 進入這種研究，那將是一個醜聞。但是搜索和查找之間是有區別的。

    +1，希望我能給您最後兩句話+10。在所有關於他們虐待的醜聞中，有時很容易忘記，當所有人都說過並且能夠監視他人時，是他們的*工作*，而我們反對的是他們缺乏約束力...
    +1-當然，您可能會認為，只要花費8000萬美元，美國國家安全局就可以[僱用傻瓜來擊敗大多數目標中的私鑰]（http://xkcd.com/538/）...然後他們又可以迫使IBM和其他公司“自願”提供迄今為止最秘密的研究進展
    -1
    @Rell3oT:的思想是，量子位是多個狀態的疊加，因此，在某種程度上，通過一個操作，可以同時完成多個計算。不確定性原理是在量子水平上，我們認為是“物質”的行為實際上像概率分佈一樣的事實，是另一種無關緊要的表達。
    好的，謝謝@ThomasPornin。您所描述的是我認為不確定性原理。顯然我需要刷牙...
    這是否表示如果可以破壞RSA，那麼由於在會話開始時使用RSA協商對稱密鑰，所有帶有證書的TLS會話都會被破壞嗎？我們還能有PFS嗎？
    @Rell3oT不確定性可以歸結為利用狀態疊加是不夠的，但是必須以某種方式做到這一點，以便以後可以測量整個結果而不更改其已測量部分-例如如果在x坐標中編碼了一位，而在該方向的動量中編碼了另一位，您可能仍然會感到困惑，因為測量動量（足夠精確）將_retroactively_更改您剛測量的x坐標（最大可能的精度），反之亦然。順便說一句，請查看http://physics.stackexchange.com;）
    服務器使用@Matrix RSA（或DSA）標識自己，密鑰協商使用[Diffie-Hellman]（https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange）。但這就像DSA一樣依賴於離散對數，因此我認為它同樣容易受到Quantum Computing的攻擊。但是，如果沒有一種方法可以對PFS使用/修改質量控制較弱的方法，我會感到驚訝
    如果加密也是在量子計算機上完成的，那該怎麼辦？
    @Jojo01:我認為已經定義了一些設計用於量子計算機上運行的加密算法（目前我不記得詳細信息）。他們應該使用量子計算機抵禦攻擊者，但他們也要求使用量子計算機，並且由於目前缺乏量子計算機的可用性，我們無法對其進行測試。假設它們是一個有趣的智力構造，它可能在將來的世界中有用，因為在每個世界中，每台計算機和智能手機都是量子計算機。
    @ThomasPornin是的，我認為量子計算將提高帳戶安全性，因為大公司很可能會使用您通常的黑客所沒有的量子計算機。當然，當量子計算成為消費者的槓桿時，這種優勢就會消失，情況會回到零。
    那蛇呢？我讀過它也不會受到影響。
    @skan: Serpent是一種對稱加密算法。我對AES的說法同樣適用於Serpent。實際上，這意味著用128位密鑰進行的蛇形加密可以在量子計算機上用大約2 ^ 64次操作來破壞（2 ^ 64在傳統計算機上已經是非常可觀的數量）。
    經過與IBM的多次接觸後，我懷疑他們數十年前就開發了量子計算機，但沒人能在他們的網站上找到它的鏈接。
    “請注意，這些是$ 2 ^ 64 $量子計算操作”：這些操作也必須是順序的，這意味著您的量子計算機必須非常快（$ 2 ^ 64 $納秒> 500年）。使用$ K $並行量子計算機，您的速度會有所提高，但仍然需要時間$ \ frac {2 ^ 64} {\ sqrt {K}} $。參見https://quantumcomputing.stackexchange.com/a/4538/5047
    mricon
    2014-01-03 21:05:28 UTC
    view on stackexchange narkive permalink

    量子計算將對非對稱加密產生最顯著的影響，但是對稱算法被認為具有足夠大的密鑰大小（256位）是安全的。所以，是的，我們必須在量子計算真正起飛之時（足夠大的TODO）來重新發明x509 / SSL，但是會有很大一部分密碼學保持相對安全。

    http://en.wikipedia.org/wiki/後期量子密碼學 http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/ 9783540887010-c1.pdf

    0skar
    2016-03-08 00:26:36 UTC
    view on stackexchange narkive permalink

    當密碼學家談論量子計算機和後量子密碼學時，實際上他們談論的是 Shor算法在分解數上的作用，因此用於創建密碼系統的基於分解數的難題就被打破了。 Shor的算法（量子計算機）使RSA，DSA，ELGamal，Diffie-Hellman密鑰交換，ECC容易受到量子計算的攻擊！

    在公鑰加密中，三種方案是量子安全的：

  • 像NTRUEncrypt這樣的基於格的密碼；基於網格
  • 像McEliece那樣的基於代碼的密碼；基於信息論
  • 多元加密（例如隱藏字段方程）
    • ol>

    ，在對稱加密（例如AES）中，如果選擇長密鑰，則可以抵禦量子計算機和NSA ！

    供將來閱讀： Quanta雜誌鏈接和量子後加密書

    sean
    2015-03-14 21:08:01 UTC
    view on stackexchange narkive permalink

    1-time pad保持最強的，不可破解的（如果使用正確）加密。當然，您確實需要面對面交換鍵盤，但我認為95％的需要這種安全級別的人在設置安全通信之前會遇到。

    只需指定要使用的256位密鑰特定的郵件可以完美地工作，並且可以被安全服務使用。

    這不能解釋量子計算機無法破解的加密類型，因此也無法真正回答問題。
    @Xander這個答案說一次性墊方法是堅不可摧的，這是正確的說法。
    我不明白為什麼這個答案提到256位密鑰。使用256位密鑰加密1024位純文本不使用OTP。
    Bardeen
    2014-01-04 09:38:37 UTC
    view on stackexchange narkive permalink

    要增強對NSA的保護，請使用AES鏈塊密碼模式進行加密，然後再次對密文（第一次加密的結果）進行加密，並重複多次。 NSA可能會嘗試通過蠻力搜索來遍歷搜索空間，並通過確定所測試的每個鍵的結果的熵來找出它們已經破解了代碼。當他們看到有意義的文本作為結果時，他們知道何時停止。通過多次加密，可以使他們更難確定何時破解了代碼，因為如果他們嘗試使用正確的密鑰，則結果將是混亂的，幾乎與錯誤密鑰的結果沒有區別。隨著重新加密次數的增加，破解加密內容的難度變得更加困難。國家安全局將全神貫注地試圖弄清楚他們何時破解了代碼。

    像TrueCrypt這樣的軟件可以為您進行多次加密。但是要提防只在“電子密碼書”（ECB）模式下運行的幼稚加密。您將需要以更複雜的模式之一（例如“ Chain Block Cipher”或“ Cipher Feedback”）運行的加密。是的，量子計算機將使NSA更加容易地通過可能的密鑰進行嘗試。但是，通過多次加密（當然，每次加密重複都使用不同的密鑰），會使您的搜索空間變得困難，因為密鑰長度是這個因素的兩倍。希望這可以幫助您將自己的東西存放在NSA的控制範圍之外。

    應用多層加密的含義可能非常複雜，在最壞的情況下，請降低各個層的安全性-例如，對整個消息_twice_進行“ XOR”運算-您最終將得到原始消息！即使您使用兩個不同的鍵，它仍然等效於對_one_完全不同的鍵進行“ XOR”運算。使用AES當然會更複雜，但是您確實可以通過增加密鑰大小來幫自己一個忙……
    @TobiasKienzler僅適用於某些類型的密碼。對於流密碼，只要隨機數不同，一切都很好。對於（大多數）分組密碼，密鑰是否不同甚至都沒有關係，儘管當然，如果密鑰相同，則不會獲得額外的安全性。對於AES之類的東西，進行多重加密是完全安全的，通常只是愚蠢而不必要的。
    @forest做一些愚蠢且不必要的_is_不安全的操作，因為您浪費了計算資源，而這些事情並不能真正增加安全性，而當適當使用該資源時
    @TobiasKienzler是的。複雜性的增加可能導致錯誤。我只是說，從純粹的密碼學意義上講，在大多數情況下這並不安全。


    ⓘ
    該問答將自動從英語翻譯而來。原始內容可在stackexchange上找到，我們感謝它分發的cc by-sa 3.0許可。
    Loading...