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)」,對細節有興趣的讀者可以參見其維基百科條目。

參考資料:Eleni Diamanti et al., Best of both worlds, Nature Physics 13, 3–4 (2017)

 

--
作者:陳奕廷,台大物理系學士,史丹佛大學應用物理系博士班就讀中。對各領域的科學都非常好奇,歡迎互相交流。

 

加入好友

9,697 人瀏覽過