從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也不會選擇它去作為標準。

 相關報導  PQC在量子運算時代脫穎而出