量子電腦與密碼學
今年 10 月 Google 宣布實現「量子霸權」,全世界都驚呆了!量子電腦已經無所不能了嗎?其實量子霸權的意義在於:人類已經讓量子電腦做到一件古典電腦很難達成的事。不過,量子電腦的進度條的確正快速更新,未來可能帶給人類巨大的福祉,但也會顛覆現今保護我們隱私的加密系統。中研院資訊所鐘楷閔副研究員形容密碼學就像一場好人與壞人的戰爭,站在量子密碼學研究前緣的他,將為研之有物的讀者揭密這場沒有煙硝的資安保衛戰。
中研院資訊所鐘楷閔副研究員,專長為理論計算機科學、量子密碼學、量子複雜度理論......換成白話,就是一位在資訊所用理論 / 數學研究方法研究資訊科學的科學家,專攻量子計算如何影響密碼學,及其潛力與極限。攝影│林洵安

中研院資訊所鐘楷閔副研究員,專長為理論計算機科學、量子密碼學、量子複雜度理論……換成白話,就是一位在資訊所用理論 / 數學研究方法研究資訊科學的科學家,專攻量子計算如何影響密碼學,及其潛力與極限。 攝影│林洵安

 

 欸……什麼是量子電腦?

量子電腦和傳統電腦的不同,在於它利用了各種神奇的量子特性,也就是當我們以微觀的角度觀察這個世界時,那些與巨觀世界不同的特性,像是讓薛丁格的貓介於死和沒死之間的「疊加態」,或是兩個量子即使相距很遠,仍舊會依據對方狀態而決定自己當下狀態的「纏結效應」。( 有關量子效應可參考「研之有物」相關文章 量子電子元件 hen 夯,但如何掌握像情人心難測的量子位元?) 當電腦擁用這些比科幻還科幻的量子特性,將克服古典電腦無法解決的難題。

不過,鐘楷閔立刻猛劃重點強調:

量子電腦不是無所不能,或是每秒鐘能做的事情比較多,它只在某些「特定 (但很重要) 問題」上,有比古典電腦更快的解法,只需要更少的空間和步驟。

舉例來說,未來量子電腦可能用於模擬細菌的固氮作用,將大大提升農業上製造氮肥的效率。因為細菌進行固氮作用時,有些關鍵步驟具有量子效應,模擬這些效應的複雜度將超越了古典電腦的極限。而量子電腦「剛剛好」是以量子效應運作,當然較有希望成功。

不幸的是,量子電腦可攻克的「特定問題」,也包括時刻保護我們交易安全和隱私的加密系統……

 

 堅不可摧的加密系統

登入網購平台,輸入帳號密碼,選好商品放入購物車(又剁了好幾根手指) 之後,再填好地址及電話,按下結帳,輸入信用卡卡號,接下來只要等商品來到家門口,啊,多美好的日常……等等,你算過在剛剛那五分鐘裡,親手傳出多少個人資訊嗎?這個問題細思極恐,事實上不必太擔心,因為密碼學正默默保護著我們。

早在兩千年前凱撒大帝打仗時,就懂得使用「暗號」來保護軍事書信。只有知道暗號的人可以「解讀」信件內容,對於不知道暗號的敵人來說,就算拿到書信也只是一堆亂碼。

但這套方式有個致命傷,那就是「如何一開始讓所有合法的使用者拿到一樣的暗號,又不會讓暗號外洩呢?」當代的密碼學家想出一套稱為「非對稱加密 」的方式,利用成對的公鑰和私鑰來加密暗號,公鑰就像是一個蓋上就鎖住的盒子,私鑰是可以打開這個盒子的鑰匙。如此一來,就能讓素昧平生的合法使用者,先利用比較安全的非對稱加密傳遞暗號,接下來就能靠暗號祕密通訊了。當你登入網購平台買東西,你的電腦和平台之間的通訊,就是透過類似的方式保護你的個資。

舉例來說,當顧客登入網路書店,申請刷卡購買「研之有物」的新書。網路書店會立刻製造一對公鑰和私鑰,把公鑰傳給客戶的電腦。客戶端的電腦再將自己的暗號,以公鑰加密後傳回網路書店。壞人沒有私鑰,就算中途攔截了信息也無法破解。最後,網路書店用私鑰解密,得到客戶的暗號,接下來就可以靠暗號傳送信用卡卡號等個資了。

細心的讀者可能會有疑問:那為什麼不直接把所有訊息透過非對稱加密傳遞,還需要先傳暗號,再用暗號保護訊息呢?原因在於,非對稱加密的效率非常低,而透過暗號加密 (稱為對稱式加密) 的效率很高。因此,目前網路架構中,僅利用非對稱加密傳遞短短的暗號,接下來主要的通訊就使用高效率的對稱式加密。圖說設計│ 林洵安、黃曉君

細心的讀者可能會有疑問:那為什麼不直接把所有訊息透過非對稱加密傳遞,還需要先傳暗號,再用暗號保護訊息呢?原因在於,非對稱加密的效率非常低,而透過暗號加密 (稱為對稱式加密) 的效率很高。因此,目前網路架構中,僅利用非對稱加密傳遞短短的暗號,接下來主要的通訊就使用高效率的對稱式加密。 圖說設計│ 林洵安、黃曉君

 

當然,網路上並不是真的有一個盒子在傳輸!目前的加密系統能如此安全,關鍵是它的核心有一個難以解開的數學難題,需要公鑰加上私鑰才能解開。所以即使壞人拿到加了密的訊息,沒有私鑰還是解不了密碼。

這類數學難題很多,像是超大數字的質因數分解。隨機找兩個很大的質數相乘 ,比如 97 乘上 113,就會得到一個超大數字 10961,很簡單吧?但是,如果一開始給你 10961,你算得出它是哪兩個質數相乘嗎?

這不是國小老師偷懶沒教,而是人類還沒找到有效率的方法 (多項式時間的演算法) 來計算質因數分解這類問題。所以理論上,只要數字夠大,即使是全世界性能最強大的超級電腦,也可能花費上萬年才能破解。

簡言之,加密系統核心的數學難題愈困難,古典電腦就需要花愈長的時間破解,加密系統也就愈安全。

 

 破解古典密碼,量子電腦 hen 會

然而,現今密碼學看似堅不可破的數學難題,在量子電腦的面前變得不堪一擊。因為這些問題的答案都可以轉化成週期性的結構,剛好量子電腦擅長破解。(哭哭)

什麼是週期性結構?再以質因數分解問題舉例:想要找出 N 這個數字是由哪兩個質數( P 與 Q )相乘所得,可以先任意選擇一個數字 A ,用 A 去除 N,得到一個餘數 a1 ,接下來依序用 A2 、 A3 、 A4 ……不斷的除 N ,就會得到餘數 a1 、 a2 、 a3 、 a4 ……最後某一次的操作,餘數會回到 a1 ,形成週期性的結構。一旦能找到週期,就能「比較有效率」的分解 N。

不過,對於古典電腦來說,當數字相當巨大時,尋找餘數的週期仍是十分困難的任務,但對於具有疊加作用的量子電腦,卻是小事一樁。

總之,目前我們所仰賴的加密系統,在量子電腦出現之後將變得不再安全……可是 IBM 、 Google 不斷更新量子電腦發展的進度條,我們已經暴露在資訊外洩的風險之下了嗎?

 

要看更完整的精采文章,請至研之有物官網:

https://research.sinica.edu.tw/chung-kai-min-quantum-computer-cryptography/

(趕快點進來喔!還有更多精采圖文!)