密碼學也要超前部署!美國後量子密碼標準競賽,台灣學者晉級決賽

作者 | 發布日期 2020 年 11 月 16 日 8:00 | 分類 科技教育 , 軟體、系統 Telegram share ! follow us in feedly


為了迎接後量子密碼學時代來臨,美國國家標準與技術局(National Institute of Standards and Technology,NIST)自 2016 年起舉辦「後量子密碼學標準化競賽」,吸引全世界團隊參賽一較高下,在這場競賽取得最終優勝者,將成為新一代標準化密碼系統。最近中研院資訊科學研究所楊柏因(見首圖)研究員團隊,以名為「Rainbow」的密碼學系統通過第一、二輪考驗,今年成為進入決選的 7 組決勝者之一,距離成為世界標準只剩一步之遙。

不論網路購物還是網路銀行交易,我們的網路一舉一動,都依賴嚴密的加密系統,保護我們隱私不讓駭客盜取,守護我們的資訊安全。然而隨著量子電腦發展,現行加密系統卻面臨破解的威脅(有關目前的加密系統,請見《量子電腦到底有多霸氣?即將引爆終極密碼戰?!》一文)。

因目前加密系統的根基,都是一道複雜的數學難題,而主流公鑰加解密系統,包括 RSA 加密演算法橢圓曲線密碼系統,背後的數學難題複雜得讓古典電腦一籌莫展,卻正好是量子電腦最擅長解決的問題型態。

這些數學難題的答案,皆可轉化成週期性結構。理論上,只要找到答案的週期,量子電腦就可「較輕鬆」的破解問題。

怎麼做?量子電腦的每個量子位元的數值是以機率呈現,意即每位元會有一個最高機率的數值,代表這個位元最可能的數。研究者可針對以上答案具週期性構造的數學函數,構造出相應的量子組態,使量子位元最高機率數值之間的差距,恰恰就是原本函數週期的整數倍,如函數的週期是 4,量出來的差距可能是 4、8、12。研究員只要測量這些差距,就能反推出函數的週期,破解古典密碼學加密系統仰賴的數學難題。

全球密碼武林大會

幸好加密系統不只一兩種,就好像武俠小說總會有武當派、峨嵋派等,各種派別都有自己的獨門招式,加密系統也根據數學難題結構分成好幾派,除了當紅的 RSA 加密演算法、橢圓曲線密碼系統,還有晶格、偵錯修正碼、多變量二次函數、雜湊函數及超奇異橢圓曲線同源等。

為了因應量子電腦即將引爆的終極密碼戰,美國國家標準與技術局(NIST)自 2016 年起舉辦「後量子密碼學標準化競賽」,就如武林比武大會,要找出能抵禦量子電腦的武林盟主,為後量子密碼學時代的新標準。不過最後標準至少要有兩個,分別用在數位簽章和加解密,所以參賽者也很自然分成兩組。

▲ NIST 負責推動美國的度量衡學、標準、技術,例如後量子密碼標準化。因美國官方標準通常也會通行世界,此次密碼學競賽結果預測將決定未來全球密碼學標準。(Source:NIST

武林大會英雄帖一出,自然吸引全世界密碼學高手前來較勁,而中研院資訊所研究員楊柏因也是其一──他組了團隊,以 Rainbow 演算法參賽。在多變量二次函數這派別,楊柏因也算長老,這派的獨門絕技就是多變量二次函數這個數學難題,也是楊柏因長期投入的主題。他和團隊殺進這場武林盛會,Rainbow 這個難題的核心,是要解一個多變量方程組,包括 100 個變數、64 個二次方程組。

多變量二次函數問題的答案,沒有週期性結構,不是量子電腦擅長的難題,因此在後量子密碼學時代也擁有很好的安全性。

演算法大亂鬥

武林大會第一場比武是大亂鬥──69 組參賽者提出的演算法,必須接受彼此攻擊,如果被破解,代表安全性不夠,這階段就會被淘汰。楊柏因形容:「過程很像練蠱,最強的才能從甕裡爬出來。」2017 年 12 月 21 日公布 69 組演算法後,雖然緊接聖誕節,但才短短幾天,就有不少演算法被破解。「大概阿宅都不過節」,楊柏因笑稱。一番廝殺後,Rainbow 順利通過考驗,成為進入第二階段的 26 組參賽者之一。

第二場比武要看演算法的性能。一個派別的武功如果到了深山或森林等特殊環境就難以施展,就無法成為武林盟主。同理,NIST 要求晉級團隊將自家演算法在一般電腦、計算能力較弱的微處理機、硬體晶片,都要能順利運作,且效果不能太差。楊柏因解釋:「在這階段要做的是,保證 Rainbow 安全性的情況下,找出讓它跑最快的參數。」

事實上,通常密碼系統的複雜度可大可小,所以跑得較快的演算法,相當於可修改成跑得跟其他演算法一樣快、但更安全的演算法。

在現在的密碼學,速度基本等同安全性,效能愈高,相當於實用安全性愈好。

第二階段比武仍舊沒有難倒 Rainbow,一路過關斬將,Rainbow 成了 7 組有資格站上決選擂台的候選者之一。此外,中研院資訊科技創新研究中心,周彤助理研究員所屬團隊提出的 Classic McEliece 也和 Rainbow 一樣是 Finalist。7 組 Finalist 中,中研院就占了 2 組,整體表現可是相當不錯呢。

風雨過後見 Rainbow

Rainbow 晉級並非一帆風順。Rainbow 演算法的關鍵部分,被來自中國的美籍學者丁津泰教授申請專利,當楊柏因要組隊以 Rainbow 參賽時,曾詢問丁教授是否同意「如 Rainbow 獲選,將免費釋出專利」。丁教授第一時間沒有答應,後來楊柏因總算說服他,如果Rainbow 獲選,將放棄專利營利。

密碼學沒什麼非你不可,換句話說,一旦 Rainbow 包含一個沒有釋出的專利,這演算法幾乎不可能選上。

另一個插曲發生在第二階段快要結束時,有人提出一個以前就有、針對 Rainbow 的攻擊新研究,對方表示這個攻擊比楊柏因的團隊認為的更有效,楊柏因說:「我們重算一遍,對方說的沒錯,但即使照重算結果,對我們演算法造成的影響也還好,只要小小調整參數即可。」後來楊柏因重新提交修改系統給 NIST,有驚無險的過關了。

強敵:晶格演算法

晉級最後階段的除了7組候選團隊,還有8組備選團隊。總共 15 種演算法,就有 7 種是「晶格派」。數位簽章的 3 組決選者,除了 Rainbow,另兩組都是晶格派。晶格通常指物質內原子的規則排列,但此處指的是一個空間向量構成的離散加法群。而「晶格派」背後的數學難題,則與空間向量有關──若在一空間有 N 條向量,要如何從這些向量彼此加加減減中,得到最短向量?只要向量夠多,這個難題一樣複雜到讓古典電腦一籌莫展,且還不像 RSA 演算法可轉換成答案有週期性結構的問題。

楊柏因承認,以目前後量子密碼學的發展狀況來說,晶格派是顯學,原因在於以晶格演算法產生出的公私鑰、密文、數位簽章等,長度約是現行 RSA、橢圓曲線密碼系統的十倍左右。相較之下,Rainbow 產生的公鑰長度是現行數百倍之長,這也是 Rainbow 所屬派別最主要的弱點。

儘管有弱點,但 Rainbow 卻很適合運用在根憑證的數位簽章與驗章,或是用在 CPU 的內碼微程式更新這類應用。這類過程不需時常傳送公鑰,所以公鑰長一點也無所謂。Rainbow 數位簽章與驗章的速度,在候選系統中是最快的。

公鑰長度很長是 Rainbow 的主要缺點,不過簽章和驗章都最快。

Rainbow 的用途:數位簽章

數位簽章(digital signature)對資訊安全的重要性,並不亞於公鑰加解密。舉例來說,當在研之有物網頁買書時,除了不想讓個資與研之有物傳遞時被駭客盜取,我們還得確定正在使用的網站真是研之有物,而不是駭客建造的假網站。

為了讓購物的消費者安心,研之有物必須向第三方的憑證公司申請憑證,也就是請憑證公司證明「這個網站真的是我們,安啦!」研之有物必須提供自己的資料、自己的公鑰給憑證公司,憑證公司確認後,就會在研之有物的公鑰簽數位簽章,就好像蓋印章。這數位簽章只有憑證公司簽得出來,其他人偽造數位簽章成功的機率極小,只有 2 的 128 次方分之一。

消費者使用的瀏覽器,內建憑證公司的公鑰,這個公鑰可辨認數位簽章(驗章),一旦辨認成功,代表「研之有物網站是憑證公司驗證過的,係金ㄟ!所以使用者可以安心購物囉」。

憑證裡的數位簽章可認證網站的真實性,保障使用者的資訊安全。

▲ 傳給讀者的訊息是憑證、公鑰 A、簽章、其他輔助資訊,但讀者確認公鑰 A 屬於研之有物後,會用這個公鑰 A 回傳加密的「暫時性金鑰」給研之有物,接下來雙方就用這暫時性金鑰互傳資訊。

「NIST 說過,公鑰加解密與數位簽章會分開選擇,而(兩個組分別)決選出來的優勝者可能不只一個團隊。」楊柏因說。即使 NIST 選擇晶格為本的數位簽章系統 Falcon 或是 Dilithium,也有可能讓 Rainbow 一起獲選。數位簽章的優異速度,可能成為 Rainbow 最終獲選的優勢。楊柏因也開始「超前部署」,正打算和資訊工程專家合作,準備嘗試將 Rainbow 放入實際網路應用,測試看看應用會不會產生問題。「Rainbow 一旦成為新標準,我們馬上就會需要這些東西。如果我希望 Rainbow 選上,應該準備實作支援。」楊柏因說。

Rainbow 最後會否成為世界標準?「謀事在人,成事在天」,楊柏因對此很輕鬆,他說:「Rainbow 的簽章和驗章運作表現數據確實最佳,但決定權還是在 NIST 手上。」身為盡責的研究者,「我會繼續工作,包括繼續研究 Rainbow 的安全性、測試 Rainbow 的實際應用狀況,其他的就看 NIST 吧!」

事實上,楊柏因也加入另一個團隊 NTRU Prime,這隊屬於晶格派,且不是 7 組最終候選者,而是 8 組備選者之一,相當於進入敗部,正在苦苦掙扎力爭上游。他同樣表示,盡力之後,就看老天爺(NIST)賞不賞光了。

(作者:郭雅欣;本文由 研之有物 授權轉載)