速度驚人！量子演算法如何在短時間內破譯密鑰？

出品：科普中國

製作：陳星

監製：中國科學院計算機網路信息中心

日常生活中的加密，例如銀行轉賬、身份識別、在線瀏覽，郵箱登錄等，加密方式都採用的是RSA密鑰。RSA密鑰採用的是一種非對稱加密演算法。在公開密鑰加密和電子商業中RSA被廣泛使用。在這裡我們不詳細討論RSA密鑰的加密過程，只舉一個例子加以說明。

假設存在愛麗絲和鮑伯兩個人，鮑伯想給愛麗絲一條信息，但是又不想被第三方竊聽。那麼他們兩人通過RSA密鑰的加密解密過程大體上相當於以下的步驟：愛麗絲給鮑伯一個開著的保險箱，這個開著的保險箱相當於是RSA密鑰中的公鑰，保險箱的密碼只有愛麗絲知道，這相當於是RSA密鑰中的私鑰。然後鮑伯把需要加密的信息放入這個保險箱，然後關上保險箱，這就相當於用公鑰對信息進行了加密。然後鮑伯可以放心的把保險箱交給愛麗絲而不用擔心信息泄露，因為除了愛麗絲之外，其他人不知道保險箱的密碼。

就像沒有絕對安全的保險箱一樣，現有的RSA密鑰也不是絕對安全的，它的安全性是由計算複雜度來保證的。例如，按照現在最快的電腦——神威·太湖之光超級計算機，破解一個1024比特的RSA密鑰(目前比較常見的長度)也需要5457560年，大概就是500萬年的樣子，因此一般認為RSA密鑰是安全的。但是這只是對於經典計算機來說是正確的，對於量子計算機就不一定了。

傳統的破解RSA密鑰的方式是暴力破解，也就是通過計算機去逐個去窮盡所有的可能。這就需要去嘗試所有可能的質數組合，因此需要很長的時間。

舒爾（Shor）演算法的出現從根本上改變了這種情況。舒爾演算法是一種量子演算法，是1994年由美國數學家彼得.舒爾發明的。這種量子演算法利用了量子比特的疊加性，可以在短時間內破譯RSA密鑰。例如，對於1024比特的RSA密鑰，大概只需要1.4×107秒，大概就是160天左右。也就是說，大概只用半年左右的時間就能破譯目前世界上最常用的密鑰系統，這就是舒爾演算法的強大之處。

舒爾演算法的量子線路非常簡單，如下圖所示：

圖中的U代表一些具體的量子門，QFT-1表示的是量子逆傅里葉變換。通過以上的量子線路使得輸入的量子比特產生疊加和糾纏，然後利用量子比特的疊加性和糾纏性，舒爾演算法可以在很短的時間破譯RSA密鑰。假定要分解的大數為N,舒爾演算法的具體步驟如下：

(1)隨機選取整數a(a

(2)若 T 為 奇 數, 則 返 回 1, 重 新 選 取 a; 若T 為偶數,則取y=a^(T/2)。

(3)求 得 y 後, 用 歐 幾 里 德 輾 轉 相 除 法 求 得y-1,y+1與 N 的最大公約n_1,n_2，則可以找到質因子 p,q 使得 N=pq。

舒爾演算法關鍵的地方就在於它能有效的計算f(x)=a^x mod N的周期T，這就大大的縮短了求N的質因子所需的時間。

舒爾演算法的出現使得人們意識到了量子計算機的強大性，也使得各國政府和學術界開始重視對量子信息，量子計算的研究。

不過，現在我們並不需要擔心量子計算機和舒爾演算法給傳統RSA密鑰帶來的威脅，因為破譯現有的RSA密鑰需要量子計算機上有上千個量子比特同時運行才能實現，在現有的技術條件下，我們只能勉強實現對10個左右的量子比特的操作，更不用說上千個量子比特了。但是，這並不代表量子計算機距離我們很遠，想想我們從第一台運算速度只有幾千的電子計算機到現在運算速度達到億億次的超級計算機，只用了半個多世紀的時間，對於量子計算機，也許時間會更短。

「科普中國」是中國科協攜同社會各方利用信息化手段開展科學傳播的科學權威品牌。

本文由科普中國融合創作出品，轉載請註明出處。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！