當 RSA 加密碰上量子電腦:2048 位元金鑰還能安全多久?

作者 | 發布日期 2019 年 06 月 16 日 21:44 | 分類 尖端科技 , 資訊安全 , 電腦 follow us in feedly

量子電腦在運算上遠比傳統電腦強大,也因此在量子電腦問世後,人們對許多事情的看法都出現了轉變,像是過往被認為幾乎是不可能破解的 RSA 2048 加密,理論上當量子電腦成長至一定階段,破解便會成為可行選項,於是剩下的問題便在於——什麼時候會發生?

在過去的研究中,考量到量子位元系統中的噪音(nosie)問題,科學家普遍認為量子電腦要發展至能夠破解現今常見的 2048 位元加密,還得需要數十年以上的時間,但在最近 Google 聖塔芭芭拉員工 Craig Gidney 和瑞典皇家理工學院(KTH)Martin Ekera 的努力下,這個時間點有可能將大幅提前。

RSA 加密演算法

RSA 加密演算法在公開金鑰加密和電子商業中被廣泛使用,這種建立在暗門函數(trapdoor function)基礎上的加密方式,主要是透過對極大整數進行質因數分解的困難,讓電腦得花費太長時間運算,以致於破解變成一種「不可行」的選項進而達到加密效果。

但究竟數字得多長才有足夠安全性?為了確認 RSA 金鑰長度的長度安全性,美國研究相關技術的 RSA Security 曾在 1991 年公布 8 個巨大合成數(composite number)並提供獎金開放大眾進行分解挑戰,這 8 個合成數量級分別為 RSA-640、RSA-704、RSA-768、RSA-896、RSA-1024、RSA-1536、RSA-2048,截至目前為止,成功被分解的只有到 RSA-768 階段(2009 年),後續 4 個合成數並未有人挑戰成功。

*後方數字為合成數寫成二進制時的位元數,以 RSA-768 為例,這代表該合成數有 768 個位元,以常用的十進制來看則有 232 個數字。

以目前來說,RSA 金鑰通常會在 1,024~4,096 位元間,由於科學家認為傳統電腦不太可能破解超過 2,048 位元的 RSA 加密,2,048 位元金鑰可以說是憑證認證機構最常見的加密形式。

然而量子電腦的存在一直都帶來些許疑慮。1994 年時,美國數學家 Peter Shor 便曾提出一種量子演算法,證明量子電腦能夠在遠勝傳統電腦的速度下進行對數運算,物理學家也曾在 2012 年時成功使用 4 量子位元的量子電腦分解 143,並在 2014 年時以同樣的設備分解 56,153。

在這種進步速度下,人們很容易就會認為量子電腦很快就會贏過最好的傳統電腦,但事情實際上並非如此。

量子運算在實踐階段遠比理論要困難許多,原因之一就是量子位元系統中的噪音問題,目前最佳的解決方法是使用大量額外資源進行錯誤更正,然而目前技術無法提供足夠的量子位元進行更正,因此噪音的干擾可說是無可避免。

考慮到糾錯會大幅增加運算所需的資源,2015 年時研究人員估計,量子電腦需要 10 億個量子位元才有機會破解能 2,048 位元金鑰,做為參考,現在最先進的量子電腦約有 70 個量子位元。安全專家因此推斷,在量子電腦對 RSA 加密造成威脅之前,人們還有好幾十年的時間可以安心。

當然,就像傳統電腦的發展歷程一樣,量子電腦的進展可能會十分快速,但 70 與 10 億仍有相當明顯的差距,即使再樂觀也明白這得花上一些時間。

但如果,是 70 與 2,000 萬呢?

改良的秀爾演算法

這便是 Gidney 和 Ekera 所做的事。在 Shor 提出的「秀爾演算法」(Shor’s algorithm)中,模指數運算(modular exponentiation)可以說是需要耗費最多資源的操作,而 Gidney 和 Ekera 成功找到許多改善方法大大減少了運行演算法所需的資源。

▲ RSA 演算是現在最廣泛使用的非對稱加密法。(Source:shutterstock)

透過使用改良後的演算法,兩人估計量子電腦破解 2,048 位元金鑰所需的量子位元數將從 10 億降低至 2,000 萬,Gidney 和 Ekera 推算,這樣的設備只需要大約 8 小時就能破解 2,048 位元金鑰。

相較起 70,2,000 萬仍是相當大的數字,要能建造出 2,000 萬量子位元的量子電腦,以目前看來仍是遙遠的夢想。但《麻省理工科技評論》(MIT Technology Review)認為,相關專家應該問自己的問題是在他們想要保護資訊的 25 年內,這樣的設備是否有機會成為可能。

如果答案是「是」,那麼他們便需要一種新的加密形式。

實際上,安全專家已經開發了「後量子密碼」(post-quantum codes),即使使用量子電腦也無法破解,因此可以說,現在確實有保護數據免受未來量子電腦攻擊的方式,但這些代碼並未作為標準使用,多數政府和企業仍以傳統加密法保護機密資訊。

對普通人來說,RSA 金鑰被破解的風險並不大,多數人只會在網路傳送信用卡等個人資訊時接觸到 2,048 位元加密,即使這些交易紀錄在 25 年內外流,人們也不會損失太多東西,但對政府或軍事機構來說,它們現在傳送的資訊或許在 25 年內仍相當重要。如果這些消息還是以 2,048 位元金鑰加密或類似方式發送,那麼這些組織確實應該開始擔心。

(首圖來源:shutterstock)

延伸閱讀: