RSA 不對稱加密和 Diffie-Hellman 密鑰交換是互聯(lián)網(wǎng)的安全之盾，但在 Shor 揭示了量子計算強大的分解能力之后，安全主宰的未來地位似乎岌岌可危，密碼學(xué)家開始爭相研究量子計算無法破解的加密算法。Quanta 的這篇文章講述了現(xiàn)代版的貓捉老鼠游戲簡史。
8月11日，NSA 網(wǎng)站發(fā)布了一份措辭含糊的聲明，稱將更換政府和軍事數(shù)據(jù)的加密方式以抵御尚未明確的量子計算機攻擊。
“現(xiàn)在很清楚了，當(dāng)前的互聯(lián)網(wǎng)安全手段及其背后的加密方式無法抵御量子計算機所帶來的新的計算能力的攻擊，” NSA 發(fā)言人在郵件中確認(rèn)了網(wǎng)站的這一變動：“NSA 保護關(guān)鍵的國家安全系統(tǒng)的使命要求我們要預(yù)料到這樣的進展。”
大家的普遍預(yù)測是，一度被視為遙不可及、僅具備理論可能性的量子計算機將在 5 到 30年 內(nèi)實現(xiàn)。這種設(shè)備可利用量子物理的概率論破解包括 NSA 秘密、銀行記錄、郵箱密碼在內(nèi)的全球大部分的 “安全” 數(shù)據(jù)。意識到這一威脅的密碼學(xué)家正在爭相開發(fā)既高效又可 “抵御量子攻擊” 的加密方法。
基于晶格數(shù)學(xué)—即多維的重復(fù)點陣的那些被認(rèn)為是其中最有希望的一種。信息隱藏在具有數(shù)百維度的晶格背后，要想破解，必須知道秘密的路由。
不過去年10月，英國的電子監(jiān)管機構(gòu)政府通訊總部（GCHQ）在網(wǎng)上發(fā)表了一篇神秘的論文，質(zhì)疑了某些晶格類加密法的安全性。論文暗示，在長達(dá) 10年 的不斷追求加密效率的道路上，已經(jīng)有一些漏洞暴露出來。由于加密者簡化了作為基礎(chǔ)的晶格，導(dǎo)致加密模式更容易受到攻擊。
根據(jù) GCHQ 的聲明，去年兩個團隊的破譯專家花了 1年 的時間去確定哪些晶格加密方法是可以被量子計算機破解的，哪些是安全的。
荷蘭萊頓大學(xué)的 Ronald Cramer 把這稱為是加解密者之間現(xiàn)代版的貓捉老鼠游戲。解密者沒有動靜的時候，為了提高效率，加密者會適當(dāng)放寬一些安全基礎(chǔ)。但是一旦寬松稍微過度，解密者就有機可乘，現(xiàn)在就是這種情況。
公開的秘密
每次訪問以 “HTTPS” 開頭的網(wǎng)站時，你收發(fā)的都是加密過的數(shù)據(jù)。安全互聯(lián)網(wǎng)交易正是由 1970年 代的革命性發(fā)明—公鑰加密促成的。在此之前，密碼術(shù)結(jié)伴上就是政府和間諜之間的游戲；交換信息的雙方（如間諜和接頭人）必須事先約定好密鑰（key）才能進行通信（比如簡單的 “凱撒密碼” 就是把字母按照雙方約定進行統(tǒng)一移位）。而公鑰加密（不對稱加密）讓每個人都可以向別人發(fā)送只有接接收者才能破解的加密信息，這個過程中雙方無需事先協(xié)定任何東西，且不懼監(jiān)聽。
公鑰加密的特點是加密容易解密難。比方說，計算機計算兩個素數(shù)的乘積是很容易的，如 34,141 x 81,749 = 2,790,992,609，但是反過來要把 2,790,992,609 這樣的大數(shù)分解成原來的那兩個素數(shù)卻要花很長的時間。密碼學(xué)家因此就利用這兩個素數(shù)做出了公鑰加密法，生成一對密鑰，其中一個作為 “公鑰” 發(fā)布給別人，后者利用這個 “公鑰” 對信息進行加密；另一把則是前者自己持有的 “私鑰”—公鑰加密的信息只有私鑰才能解密。
1970年 代末誕生的兩種有效的加密方法至今仍用得最為廣泛：一個是基于素因子問題的 RSA（用發(fā)明者 Ron Rivest、Adi Shamir 與 Leonard Adleman 的名字命名），以及基于離散對數(shù)問題的 Diffie-Hellman 密鑰交換。盡管這兩種算法在合理時間范圍內(nèi)不可能有解尚未經(jīng)過實際證明，但至今無人想出有效的計算辦法。
“隨著時間的流逝，大家開始樹立起對某些問題的難度的信心，因為那么多人絞盡腦汁想要破解都失敗了，” 布朗大學(xué)的數(shù)學(xué)家和密碼學(xué)家 Jill Pipher 這樣評價。
現(xiàn)有的這些算法下，要想計算出典型長度的公鑰素因子往往需要數(shù)年的時間。因此，RSA 和 Diffie-Hellman 密鑰交換成為了互聯(lián)網(wǎng)之盾，給人以安全主宰的味道。
不過結(jié)果證明，這種安全性也有保鮮期。
Shor 算法
1994年，有關(guān)計算機難以破解部分?jǐn)?shù)學(xué)問題的假設(shè)被打破，AT&T 一位名叫 Peter Shor 的研究人員發(fā)現(xiàn)了量子計算機的理論解密能力。
在一般計算機里，信息通常是用位（要么是 0 或 1 兩種狀態(tài)）來存儲的，而計算機的計算能力與位數(shù)成正比。然而量子計算機里面信息的存儲單位是量子比特（qubit），它的特點是 0 態(tài)和 1 態(tài)可以同時并存（比方說量子比特可以是亞原子粒子的形式，它可以同時進行順時針或逆時針旋轉(zhuǎn)）。由于帶有許多量子比特的系統(tǒng)可以任何可能的獨立狀態(tài)的所有可能組合形式存在，因此量子計算機的計算能力會隨著量子比特的數(shù)量而指數(shù)增長。
加密黑箱的新設(shè)計
這似乎讓量子計算機成為比傳統(tǒng)計算機更加強大的問題解決者。然而，要想真正挖掘量子計算的潛能，需要找到一個算法來捕捉到它的并發(fā)狀態(tài)，這樣與正確答案相對應(yīng)的系統(tǒng)狀態(tài)才會最終出現(xiàn)。這件事實現(xiàn)起來沒那么簡單，自 1980年 代量子計算機構(gòu)思出現(xiàn)以來的 10 多年時間里，尚未出現(xiàn)過有希望的算法，這個領(lǐng)域也慢慢失去了活力?！皩嶋H上沒人關(guān)注，” MIT 的量子計算理論家 Seth Lloyd 說。
不過 1994年 一切都有了改觀—Shor（現(xiàn)在 MIT）發(fā)明了足以有效計算素因子和離散對數(shù)的量子計算機算法，在理論上 RSA 加密和 Diffie-Hellman 密鑰交換同時變得弱不禁風(fēng)。Lloyd 說，在量子計算有了一個殺手應(yīng)用（可稱之為 quapp）之后，對量子計算的興趣開始爆發(fā)。
在 Shor 算法揭示了量子計算的超級計算能力之后，全球的研究者開始爭相開發(fā)量子計算機。與此同時，密碼學(xué)家也在爭分奪秒設(shè)計量子計算無法破解的加密方法?！昂荛L一段時間我們都沒有頭緒，” Georgia Institute of Technology 的密碼學(xué)家 Chris Peikert 說：“不過晶格似乎是一個很好的基礎(chǔ)。”
未完待續(xù)......
本文編譯自：quantamagazine.org
“看完這篇還不夠？如果你也在創(chuàng)業(yè)，并且希望自己的項目被報道，請戳這里告訴我們！”
聯(lián)系客服
