RSA加密法遇上量子電腦

量子電腦是基於量子力學的計算工具，圖中為量子力學中波函數常用的符號。

■通訊和情報一直是商業和國防最重要的一環，而加密是其中的核心。二十世紀末以來，
RSA加密法憑藉著古典電腦難以企及的複雜度變得日趨流行，安全性高。但對於特定的計算工作，量子電腦的計算力遠遠超越古典電腦，這是否會對你我日常都在使用的RSA加密造成威脅呢?回答問題前，先讓我們看看RSA和量子電腦背後分別有些什麼。

●在RSA之前：對稱性加密

關於對稱性加密，最廣為人知的是二次大戰中德軍的密碼系統「Enigma」。每位軍士官擁有一份密碼錶(金鑰)，當收到加密訊息時(圖一)，必須用相同的密碼錶才能翻譯密文。敵軍竊聽者缺少了密碼錶，就算攔截到訊號也無法解開密文。這種密碼系統非常成功，當時德軍靠著它，透過閃電戰順利擊敗周圍國家。

圖一、對稱性加密示意圖。對稱性加密中的「對稱」指的是加密和解密使用相同的金鑰(密碼錶)。他的優點是加密過程簡單明了，且在金鑰不外流的情況下安全性很高。但缺點是一旦金鑰外流，整個密碼系統就瓦解了。無論是過去戰爭或是現代生活，保證金鑰絕不外流是一件不切實際的事，因此對稱性加密的安全性並不是真的很可靠。

●非對稱性加密

德軍將密碼錶印在水溶性材料上，每個月更新一次。若遭到俘虜，密碼錶可以立即被銷毀。即使密碼錶真的被拿走，也只能用一個月而已。但這仍非完美，如果團體中有間諜定期外流密碼錶，密碼系統就瓦解了。可能的對策是每兩個人之間都有一份獨特的密碼錶，若團體中有n個人，一個間諜外流的密碼錶不會影響到其他(n-1)人。但如此一來，團體總共需要約n平方組密碼錶[注1]，非常不方便。再者，要和一位新成員秘密通訊，如何安全傳遞密碼錶也是一個大問題。針對這些難題，非對稱性加密因應而生。

非對稱性加密的精隨在於加密和解密需要不同的鑰匙，分別為公開金鑰和私有金鑰。任何擁有公開金鑰的人都可以加密任何訊息，但唯有私有金鑰才能解開密文。圖二中，男孩為了安全地向女孩發送訊息，事先向女孩索取一份用來加密的公開金鑰。女孩收到加密訊息後用私有金鑰解密。若有竊聽者攔截訊號，他也只能得到已加密的訊息和加密用的公開金鑰，無法解密。值得一提地，若男孩誤刪自己的訊息原文，他本人也無法透過公鑰還原訊息，地位變得和竊聽者一樣。這樣的密碼架構下，雖然需要花時間事先索取公鑰，但免去了傳送密碼錶的風險，安全度大幅提升。

圖二、非對稱加密示意圖。「非對稱」指的是加密和解密使用不同的金鑰，因此我們可以任意的發送只能用來加密的公開金鑰。圖中男孩像女孩發送訊息前，必須先索取一份公鑰，傳送訊息步驟稍長，但安全性提高很多。竊聽者再怎麼攔截訊號，都無法得到解密用的私鑰，因為它從來不存在於通訊之中。唯一能竊取私鑰的方法就是侵入持有者的電腦或家中(但如果他真的成功入侵，他直接竊取訊息就好，也不需要竊取金鑰了)。

●密碼背後的數學和安全性

當今最廣為使用的非對稱加密法是RSA演算法，其名稱由發明者Ron Rivest、 Adi Shamir 和 Leonard
Adleman的姓氏組成。概念如圖三，RSA演算法基於兩個質數p和q，它們製造符合條件的公開金鑰(n,e)和私有金鑰(n,d)。
加密和解密是對訊息取次方並取餘數(mod) [注2]，例如要使用公鑰(n=143,e=7)加密體重「72」公斤，讀者動筆 (或計算機) 算算會得到密文
。解密時，用私鑰對密文做類似的運算可以得到 。

對於沒有私鑰卻想要破解訊息的竊聽者，他唯一的資訊只有公鑰(n,e)。其中一種破解方式是對n做質因子分解找出p和q，從而推導出私鑰d。但是對於標準的2048位元RSA加密，就算用目前世界上最強的超級電腦(太湖之光，中國制)，花費地球年齡的時間(46億年)都無法破解。RSA演算法安全性高，又只需分享公開金鑰，因此從社交軟體到軍事通訊都有他的蹤影，我們的生活可說是一舉一動離不開RSA。

圖三、在RSA演算法背後，公鑰和私鑰其實是兩組數字，它們符合圖中的數學條件。想要加密一個訊息(Message)
m，只要對m做次方和餘數的運算就好，而解密一則密文 (Ciphertext)
c也只需要做類似的運算，非常方便。安全性方面，其實在公開金鑰中已經含有足以破解密文的資訊，但是要找到這些正確的資訊需要計算非常久的時間，一般的古典電腦根本無法有效做到。對於深入數學有興趣的讀者，可以參考維基百科中RSA加密演算法條目。

●量子電腦和周期性

量子電腦針對特定的問題，計算能力遠大於古典電腦。由於量子力學用「波動性」的概念來描述物質，波動的「周期」是量子力學中根本的性質之一。各種物理量之間存在共軛性，而這些共軛的物理量有像是波動和周期的相互關係。例如：動量可以想成是空間上的周期、能量像是時間上的周期，或更抽象地，粒子數像是相位中的周期。因為這些特性，量子電腦特別擅長尋找周期。

在上述RSA演算法中，一個核心的元素是「取餘數(mod)」。這個函數具有周期性，是他的優點也是他的弱點。因為有周期性，他可以有效率地被用於加密和解密。但是若有一台機器能夠快速找出函數的周期性，RSA演算法則能輕鬆地被破解[注3]。量子電腦恰好就是這樣的機器，破解RSA演算法是量子電腦發展的目標之一，也是學界、業界和政府投入大量資金進行研發的重要原因之一。

若要破解一組2048位元的RSA加密，理論上大約需要4000個量子位元(qubit)。目前Google和IBM的量子電腦約有20個量子位元。儘管數量仍遠遠不足，但是相較於2016年的9位元和5位元，兩家公司都將數目提升兩倍了。未來能否用量子電腦對現有密碼系統革命，讓我們繼續看下去吧。

注釋：

[注1] 團體中有n人，任兩個人配一個獨特的密碼錶，總共需要n(n-1)/2個，複雜度為n平方。

[注2] mod是取餘數的意思，他的格式為「被除數 = 餘數 mod 除數」。例如17除以5等於3餘2，可以寫作「17=2 mod 5」。

[注3] 最廣為人知的破解RSA的演算法是「秀爾演算法(Shor』s Algorithm)」，對細節有興趣的讀者可以參見其維基百科條目。

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