從 4 大關鍵問題搞懂 PQC 與密碼學競賽

從 4 大關鍵問題搞懂 PQC 與密碼學競賽

近年來,量子運算帶來的威脅持續成議題,後量子密碼學(Post-Quantum Cryptography,PQC)的發展也備受關注,而隨著 NIST 舉行的「後量子密碼學標準化」競賽,在 2020 年後進入最後階段,因此,不只是密碼學界,現在已經是各界都在關注 PQC 的最新發展。

基本上,這是一項對於公鑰密碼系統的考驗,NIST 的目的很簡單,就是要選出可以不受量子電腦威脅的新密碼系統,成為美國的國家新標準,但由於制定完成後,全世界都會採用,因此,其效果就是成為世界的新標準。

NIST 是何方神聖?他們是美國國家標準暨技術研究院,在諸多產業都有多年標準制定經驗,而資訊技術與網路安全也是他們的重點,包括網路安全與隱私保護、密碼學及密碼驗證等 9 大領域。

由於量子電腦威脅的議題,近年來 PQC 逐漸受到關注,加上 NIST 舉辦相關競賽要選出新標準,但國內大多人對此議題可能還不熟悉,因此,這次我們找到這方面的專家──臺大數學系兼任助理教授陳君明,幫助我們更進一步瞭解。

而為了讓大家對 PQC 與 NIST 密碼學競賽能更有概念,因此,我們整理出四大面向的問題,讓大家能夠一步步瞭解。

 

問題 1 最近時常聽到量子運算突破的新聞,以及現有加密系統將會被破解的消息,這與後量子密碼學(PQC)有何關連?

隨著量子運算的出現,讓傳統加密系統出現危機,尤其是將對當今的非對稱式密碼系統帶來極大影響,這是指那些密碼系統?其差異為何?

簡單來說,密碼系統分成兩大類,一類是對稱式密碼,AES 就是一例,另一類是公開金鑰密碼,也就是非對稱式密碼。陳君明指出,所謂的量子破密,主要影響的是非對稱式密碼系統,例如,公鑰密碼系統,也就是現今普遍的公鑰基礎架構,包括 RSA 或 ECC 這類非對稱加密演算法。

基本上,加密演算法都是建立在特定數學難題的基礎之上。以 RSA 而言,過往之所以安全,是建立在極大整數質因數分解的數學難題,對傳統電腦而言,需要花費太長時間運算,而量子電腦則可於多項式時間破解這樣的難題。

至於對稱式密碼系統,雖然也會受到量子電腦攻擊的影響,但影響程度算是有限。舉例來說,原本 AES 256 的強度變成 AES 128 的強度,因此,只要密鑰長度加倍就可因應。

那麼,為何過去 DES 演進到 AES 時,沒有出現類似後量子密碼學這樣的新名詞定義?陳君明表示,DES 與 AES 都是對稱式密碼相當明確,而在公鑰密碼方面,雖然 RSA、ECC 與 PQC 都是這個範疇,但由於前兩者都會被量子電腦破解,因此,專注在不會被量子電腦破解的公鑰密碼系統,就需要有一個新的名稱。

同時,他也指出,全球在因應量子電腦破密的威脅上,其實有兩大路線,除了基於密碼學的 PQC,還有基於量子技術的量子密鑰分發(Quantum Key Distribution,QKD)等。

不過,自 2020 年 10 月後,PQC 可能將會更受重視。陳君明表示,主要原因在於,美國國家安全局公開表示,他們不看好 QKD 與量子加密(Quantum Cryptography,QC),而且也說明 QKD 的 5 個技術限制,包括需要專用設備,以及需要增加基礎設施成本與內部威脅風險等,他們甚至直言,日後將只會關注在PQC的發展。因此,就現在的態勢來看,除了持續關注量子電腦的最新進展,追蹤後量子密碼的標準制定也是重點。

 

問題 2 現在大家在關注的後量子密碼學,它是現在才新出現的嗎?還是其實已經發展了很多年?

在 2020 年 7 月,由美國 NIST 所舉辦的「後量子密碼學標準化競賽」(Post-Quantum Cryptography Standardization),公布第三輪決選名單,此事也讓我們注意到,原來因應量子運算威脅的 PQC,發展已久。

例如,這項競賽從 2016 年就開始對外公開徵選,甚至他們是在 2012 年開始準備 PQC 計畫,而更早 NIST 在 2009 年就有這方面的調查。

對於後量子密碼學的發展與演進,陳君明表示,其實,全球最早注意到量子運算的威脅,已經是20多年前。

從 1994 年開始,當時 AT&T 貝爾實驗室的數學家 Peter Shor 有了一項重大發現,他提出大整數質數分解的第一個量子算法,稱之為 Shor’s 演算法,因此開啟了量子破密的里程碑。

而後續提出的 Grover 演算法,也發現會使對稱式密碼系統的安全等級減半。

陳君明指出,當時整個密碼學界就開始關注這件事,但還不是那麼急迫要去因應,主要原因,當時大家公認量子電腦還不會那麼快邁向成熟。

不過,約自 2000 年開始,其實全球密碼學界都已在關注,並且一直陸續都有針對這方面的相關研究。

另外,我們也好奇,難道 20 年前就有後量子密碼學一詞嗎?他解釋,關於 PQC 一詞,其實是由 Daniel J. Bernstein 提出。而在更早之前,像是美國 NIST 與 NSA 是以「Quantum Resistant」稱呼這類密碼學。

因此,我們看到早年 NIST 對於 PQC 的一項調查研究,當時是稱之為 Quantum Resistant Public Key Cryptography,不過,現在大家幾乎都是以 PQC 來統一其稱呼。

 

問題 3 關於 NIST 舉辦密碼學標準化競賽,吸引來自全世界的團隊參賽一較高下,這樣的密碼學競賽多嗎?

除了這次的 Post-Quantum Cryptography 的競賽以外,我們其實看到 NIST 共列出 4 個競賽,包括:Block Cipher(AES)、Hash Function(SHA-3),以及Lightweight Crypto,這些競賽有何不同?

陳君明表示,其實,NIST 並非第一次舉辦這類密碼學的競賽。在 20 年前,NIST 就舉辦過 AES 進階加密標準的競賽。他們是在 1997 年 1 月開始公開徵選,然後在 2000 年制定出新標準,當時,這項競賽是為了選出取代早期的 DES 標準,成為新的對稱式加解密的標準。

特別的是,這也是他們第一次,舉辦全世界都可以參與的競賽。因為,在 1976 年制定的 DES 標準,僅是由 IBM 的一個團隊,先設計了對稱式加解密,然後再經由美國國家安全局 NSA 參與修改,才確立為國家標準,因此當時並沒有對外公開徵求候選者。

而在 NIST 這麼做之後,也打開了標準競賽舉辦的風氣,因為,其他國家也開始舉辦這類的全國性標準競賽,像是南韓、日本與中國等。

不僅如此,約在 10 年前,NIST 又舉辦了 SHA-3 第三代安全雜湊演算法的競賽。簡單而言,這是因為 SHA-1 被發現嚴重的問題,而 SHA-2 又與 SHA1 設計原理類似,因此 NIST 要選出一個設計原理非常不一樣的成為新標準。後續,SHA-3 與 SHA-2 併行成為美國政府的雜湊函數的國家標準。

至於現階段,陳君明說,NIST 其實是有兩項競賽正在進行,除了 PQC 的競賽之外,另外還有一項名為 Lightweight Crypto 的競賽。

他解釋,這是一個輕量級的密碼學競賽,主要因為現在有越來越多 IoT 裝置,但是,在這些裝置上執行 AES 並不易,因此,需要有一個執行運算資源需求較少,又能維持基本安全性,短時間破不了的密碼系統。這項競賽在 2019 年才發起,目前有 57 個投稿。

 

問題 4 這次 PQC 競賽時間漫長,若是這段期間如果有新演算法提出,難道就不能成為標準嗎?

從上述 PQC 的發展與 NIST 的這些競賽來看,我們還是很好奇,例如,以這次 PQC 標準化競賽的評選時程,似乎比之前 AES 競賽時間要更長,而這麼多年的時間下來,難道就不會有新的技術被提出,而無法入選成為新的標準嗎?

陳君明解釋,其實我們並沒有辦法嚴格證明某一個密碼系統的安全,因此,能夠做的事情,就是將演算法公開,讓大家來攻擊後,如果大家都破解不了,就代表越安全。

「在密碼學的領域,並不是技術越新越好,而是要越經得起考驗越好。」他說,以這次 NIST PQC 標準化競賽為例,名為 McEliece 的密碼學系統是第三輪入選之一,它已經被提出40年之久,就是因為大家都破解不了,而且被大家普遍使用的時間越久,這代表著越經得考驗,因此大家相信它的程度就會越高。

另外,他也以這次其他競賽投稿為例,像是 NTRU 已被提出超過 25 年之久,而 Rainbow 也已經提出有 15 年。

反之,新提出的密碼學系統,通常沒有經過長時間的考驗,因此大家對它的信心也會較低,而 NIST 也不會選擇它去作為標準。

 

新聞稿原文出自: 從 4 大關鍵問題搞懂 PQC 與密碼學競賽

 


Please publish modules in offcanvas position.