當 RSA 加密碰上量子電腦：2048 位元金鑰還能安全多久？
量子電腦在運算上遠比傳統電腦強大，也因此在量子電腦問世後，人們對許多事情的看法都出現了轉變，像是過往被認為幾乎是不可能破解的 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）