多變量公鑰密碼系統(tǒng)實現(xiàn)研究進展*

易海博

（深圳職業(yè)技術學院 計算機工程學院，廣東 深圳518055）

隨著物聯(lián)網(wǎng)的興起和快速發(fā)展，密碼系統(tǒng)的應用日益廣泛．芯片采用的RSA（Rivest-Shamir-Adleman）[1]、ECC（Elliptic curve cryptography）[2]等公鑰密碼的安全性基于大整數(shù)分解或橢圓曲線離散對數(shù)問題，被美國科學家Peter Shor 證明可以使用量子計算機在多項式時間內求解[3]．盡管能夠破解公鑰密碼的量子計算機尚未面世，但已有不少研究取得了巨大進步．谷歌在提出“量子霸權”1年多時間后，終于迎來了自己在量子計算領域里新的突破[4-5]．2018年3月5日，谷歌量子人工智能實驗室（Quantum AI Lab）研究科學家Julian Kelly 在谷歌的官方博客上公布了一款擁有72 量子比特的量子處理器，名為Bristlecone（中文譯為“狐尾松”），隨后谷歌在洛杉磯舉行的美國物理學會年會上展示了這款新的處理器．2017年11月，IBM 成功開發(fā)出了1 臺50 量子比特的原型機，可為今后IBM Q 系統(tǒng)奠定基礎[6-7]．英特爾也向谷歌發(fā)起了挑戰(zhàn)，在2018年1月的CES2018 國際消費電子產品展上，向合作伙伴交付首個49 量子比特量子計算測試芯片．加拿大D-Wave 公司推出的專用量子計算機2000Q 已達到了2000 量子比特[8]．

我們的二代身份證使用ECC 密碼，如果量子計算機的處理能力再度提升，就有可能破解該密碼，不法分子就能夠大肆偽造身份證．面對量子計算機的巨大威脅，美國政府率先行動，美國國家安全局NSA 和美國國家標準與技術研究院NIST 相繼公布了從現(xiàn)有的公鑰密碼體制過渡到抗量子密碼體制的公告．

抗量子密碼又被叫做后量子密碼（Post-Quantum Cryptography）[9]，重要學術會議PQCrypto（International Workshop on Post-Quantum Cryptography）已舉辦了9 屆．后量子密碼主要包括四大類，基于格的密碼（Lattice-Based Cryptography）[10]、基于編碼的密碼（Code-Based Cryptography）[11]、多變量密碼（Multivariate Cryptography）[12]以及基于哈希的密碼（Hash-Based Cryptography）[13]等．在后量子密碼中，多變量密碼的安全性基于求解有限域的多元二次方程組，被證明是NP-Hard 問題[12]．PQCrypto 收錄近40%的論文來源于這方面的研究[14]，已逐漸成為這個領域的熱點．

1 多變量公鑰密碼方案

多變量密碼的研究始于20 世紀80年代，H.Ong、Claus-Peter Schnorr、Adi Shamir 等學者于1984年和1985年提出了基于二次方程和多項式方程組的簽名方案[15-16]；Harriet J.Fell,Whitfield Diffie 等學者于1985年提出了多項式替換構造公鑰密碼的方案[17]；John M.Pollard,Claus-Peter Schnorr 于1987年提出了對x2+ky2=m(modn)進行求解的方法[18]．這些研究為多變量公鑰密碼的發(fā)展奠定了基礎．

多變量公鑰密碼的發(fā)展主要分為5 類（如圖1所示）：

1）第一類中心映射建立在擴域上方案，典型方案有單變量多項式結構MI(Matsumoto-Imai)方案和HFE 方案等；MI 加密方案是Tsutomu Matsumoto 和Hideki Imai 于1988年共同提出了第一個多變量公鑰密碼方案，以他們姓氏的首字母命名[19]．但在1996年，法國學者Jacques Patarin用一種線性化方程的攻擊方法破解了MI 加密算法，證明了它不安全[20]．隨后，Jacques Patarin通過改進MI 加密算法，提出了HFE 密碼算法[21]．在1998年，Jacques Patarin 在MI 的基礎上，提出了兩類新的多變量方案[22]．關于MI 和HFE 的變種，如PMI+、IPHFE+加密也逐漸被提出，以及簡單矩陣乘法的SimpleMatrix 加密[23-30]的提出，豐富了多變量公鑰加密的研究．在簽名方面，HFE簽名系列（如HFEv-、Gui）[31-34]開始成為研究的熱點之一．

圖1 中心映射陷門構造

2）第二類中心映射建立在基域上的非平衡油醋UOV 方案，這一類方案主要應用于多變量簽名的構造，包括UOV 在內的油醋OV 簽名系列（如UOV、Rainbow）被認為安全性和效率更高．油醋結構由多個油變量和醋變量組成，油變量數(shù)量和醋變量數(shù)量一樣多則稱為平衡油醋，不一樣則稱為非平衡油醋．UOV 是非平衡油醋的單層結構，而Rainbow則是非平衡油醋的多層結構．

3）第三類中心映射建立在基域上的三角形體制TTM 方案，這一類方案主要應用于多變量簽名的構造，其中比較知名的是基于TTM 的TTS 簽名以及增強TTS 簽名enTTS，這類簽名基于三角形構造，簽名速度很快，但安全性比Rainbow 較低．

4）第四類介于第一類和第二類之間，其中心映射是建立在中間的域上的方案，如丟番圖方程結構MFE 方案和可逆循環(huán)體制?-IC 方案．

5）第五類是基于多變量二次擬群提出的方案，該方案采用了一種新的基于擬群和擬群變換理論的多變量二次陷門函數(shù)．相對于其它方案，它的加密速度相近，但它不會使密文擴張．

除了以上這5 類方案，國內外多位知名學者通過尋找新的陷門函數(shù)、改進和組合已有方案在不斷提出新的多變量方案，使多變量公鑰加密和簽名的安全性和效率更高．美國University of Cincinnati 學者Jintai Ding 在2009年的著作《Multivariate Public Key Cryptosystems》[35]中系統(tǒng)地總結了多變量公鑰密碼體制的發(fā)展概況．

在探索多變量公鑰密碼的新方案的重要方法有加方法、減方法、醋變量方法和內部擾動方法等，其中減方法和醋變量方法主要用于設計多變量數(shù)字簽名方案，內部擾動方法則是由美國學者Jintai Ding 提出的一種系統(tǒng)化的增強多變量公鑰密碼的安全性的方法．通過變形后的最著名的多變量公鑰密碼算法是SFlash 簽名算法（從MI減加密算法發(fā)展而來）[36]，曾被NESSIE 確定為2004年低功耗智能卡的安全標準，但Dubois在2007年結合差分攻擊和線性化方程將SFLASH 方案攻破[37]．

2 多變量密碼方案實現(xiàn)研究進展

隨著量子技術的研究不斷推進，能夠破解現(xiàn)有主流公鑰密碼系統(tǒng)的量子計算機面世的可能性越來越大，設計具有抗量子計算特性的密碼系統(tǒng)成為非常迫切的事情．研究多變量密碼實現(xiàn)已逐漸成為熱點，主要集中在提升速度、縮小面積、優(yōu)化性能等3 個方面．

加快速度的方案主要通過引入優(yōu)化結構、優(yōu)化有限域運算等方案來縮短時間．其中，針對Rainbow 簽名速度的提升主要有：Balasubramanian 等人在FCCM 2008 會議上提出的快速實現(xiàn)Rainbow 簽名的方案[40]，通過FPGA和ASIC 的特性將Rainbow 簽名的時間大幅提升；Tang 等人在PQCrypto 2011 會議上提出的快速實現(xiàn)Rainbow 簽名的方案[39]，通過設計優(yōu)化有限域運算，例如三元乘法、并行高斯約當消元，將Rainbow 簽名的時間縮短了四分之三；Petzoldt等人在PQCrypto 2013 會議上提出的快速驗證UOV 和Rainbow 簽名的方案[38]，將Rainbow 和UOV 的簽名驗證時間大幅縮短．針對UOV 的優(yōu)化主要通過縮小公鑰提升簽名驗證速度，縮小私鑰提升簽名生成速度，代表性論文有：Petzoldt等人在PKC 2012 會議上提出的縮小公鑰提升UOV 簽名驗證速度的方案[41]和Tan 等人在Inscrypt 2015 會議上提出的縮小私鑰提升UOV簽名速度的方案[42]．另外，enTTS 簽名和SimpleMatrix 加密也是優(yōu)化實現(xiàn)的熱點，代表性論文有：Yang 等人在CHES 2004 會議上提出的快速實現(xiàn)enTTS 的方案[43]和Peng 等人在ISPEC 2016 會議上提出的快速實現(xiàn)SimpleMatrix 加密方案[44]．

縮小面積的方案主要通過微處理器、縮小公鑰、精簡運算、優(yōu)化有限域運算等方式實現(xiàn)，其中Yi 等人在2016年提出的在FPGA 上實現(xiàn)最小多變量密碼處理器（Rainbow、UOV、enTTS）的方案[45]采用了精簡指令集來實現(xiàn)；Czypek 等人在CHES 2012 會議上提出的在受限設備上實現(xiàn)Rainbow、UOV、enTTS 簽名的方案[46]采用了精簡運算；Tan 等人在2016年上提出的一種節(jié)省內存的Raibow 簽名方案[47]和Petzoldt 等人在INDOCRYPT 2010 會議上提出的一種縮小公鑰的Raibow 簽名方案[48]；從公鑰消耗內存的角度對面積進行了縮小；另外，Chen 等人在2016年提出的一種應用于無線傳感器網(wǎng)絡的UOV 簽名方案[49]和Tang 等人在2015年提出的一種應用于云計算環(huán)境的PMI+加密方案[50]也是縮小面積的方案的代表．

追求時間面積平衡的方案主要有Wang 等人在2016年提出的基于神經網(wǎng)絡實現(xiàn)多變量密碼的方案[51]、Shih 等人在2013年提出的高效實現(xiàn)TTS的ASIC 方案[52]、Bogdanov 等人在CHES 2008 會議上提出的高效實現(xiàn)UOV、enTTS、Rainbow 的方案[53]、Yi 等人在2018年提出的高效實現(xiàn)Rainbow的方案[54]、Chen 等人在CHES 2009 會議上提出的高效實現(xiàn)HFE、Rainbow、TTS 的方案[55]．這些方案在提升方案速度的同時，同時優(yōu)化面積，達到性能均衡，主要采取了systolic、神經網(wǎng)絡等特殊結構實現(xiàn)．

上述多變量密碼方案的實現(xiàn)研究表明多變量簽名方案，如Rainbow、UOV、enTTS 在性能方面已經接近或者超過RSA、ECC 等公鑰簽名，但除了SimpleMatrix，其他加密方案在性能方面并不盡如人意．另外，公鑰數(shù)量較大也制約了多變量密碼方案的廣泛應用． Rainbow、UOV、enTTS、SimpleMatrix 等多變量密碼方案已經逐漸成為抗量子公鑰密碼芯片的重要選擇之一[56]．

3 多變量密碼方案側信道分析研究進展

對于密碼系統(tǒng)，它的安全性遵循“木桶效應”，在防范代數(shù)攻擊的同時，還需防范側信道攻擊，這種攻擊方法基于密碼系統(tǒng)物理實現(xiàn)過程中泄露的信息，屬于物理攻擊的一種，并不破壞硬件的物理結構，也不需要利用算法數(shù)學方面的弱點．信道攻擊的原理是側信道信息（例如能量消耗、電磁泄露、時間信息、聲音等）可以為破解密碼系統(tǒng)密鑰提供額外的幫助．相應的，常用的側信道攻擊方法包括時間攻擊[57]、能量攻擊[58]、電磁攻擊[59]、故障攻擊[60]等．

在側信道攻擊的方法中，故障攻擊的原理是嘗試改變密碼系統(tǒng)運行的環(huán)境，例如電壓、時鐘、溫度、光亮等，從而在密碼運算過程中造成故障，觀測相關變化，以達到破解密鑰的目的．一種常用的故障攻擊方法是對某一個寄存器使用激光束，導致寄存器的部分比特產生翻轉，即從0 變成1 或從1 變成0．故障攻擊已經成功在攻擊RSA簽名中實施[61]．

另一種常用的側信道攻擊方法是能量攻擊，基于觀測密碼系統(tǒng)的能量變化而實現(xiàn)攻擊．常用的能量攻擊方法包括簡單能量攻擊SPA（Simple Power Analysis ）[62]和差分能量攻擊DPA（Differential Power Analysis）[63]．DPA 由Kocher等人在1999年提出，原始DPA（mono-bit DPA）針對寄存器單個比特進行觀測．mono-bit DPA 被Messerges 等人擴展為multi-bit DPA，可以對某個中間運算結果的一組比特進行觀測．后來，Messerges 等人對DPA 進行再次擴展，即可以同時觀測多個運算結果的功耗，這種方法被叫做高階DPA 攻擊[64]．DPA 攻擊需要基于能量模型實現(xiàn)，例如漢明重量模型和漢明距離模型[65]．漢明重量模型基于密碼系統(tǒng)中數(shù)據(jù)的漢明重量的變化進行差分能量攻擊，而漢明距離模型則基于數(shù)據(jù)的漢明距離．一般來說，漢明距離模型更適合CMOS 密碼系統(tǒng)攻擊．

目前，AES、RSA、ECC 等密碼的側信道研究已經逐漸形成體系[66-69]，新的攻擊和防護模型被不斷提出，較大地促進了這個領域的基礎研究．

相比之下，多變量密碼的側信道安全分析研究則較少，主要針對SFLASH、enTTS、UOV 和Rainbow 等密碼，主要的代表作有：

1）Okeya 等人提出了一種基于差分功耗分析SHA-1 模塊攻擊多變量簽名SFLASH 的方法[70]，但并不適用未采用SHA 模塊的Rainbow、UOV等多變量密碼；

2）Hashimoto 等人提出了一種故障分析多變量密碼的方法[71]，可以恢復部分的密鑰；

3）Yi 等人提出了一種基于故障分析結合差分功耗分析恢復三角構造中心映射和仿射變換密鑰的模型，基于ASIC 功耗評估恢復了enTTS 的所有密鑰[72]；

4）Yi 等人提出了一種基于側信道攻擊UOV 和Rainbow 的方法[73-74]．

針對側信道攻擊，多變量密碼的側信道安全防護研究主要有Nakkar 等人提出了一種防護故障攻擊的Rainbow 簽名方案[75]．

已有的多變量密碼的側信道安全分析表明多變量簽名方案，如Rainbow、UOV、enTTS 等易遭受差分功耗分析和故障分析，中心映射和仿射變換中的密鑰容易通過側信道方法進行恢復．多變量密碼的側信道安全分析和防護研究仍然處于起步階段，研究具備抗量子計算和抗側信道攻擊的密碼系統(tǒng)，有重要現(xiàn)實意義和理論價值．

4 總結和展望

近年來，多變量密碼的算法設計和分析是抗量子計算密碼領域研究的熱點之一．本文從多變量密碼的系統(tǒng)實現(xiàn)和側信道分析和防護等方面的研究展開了介紹．多變量密碼方案的實現(xiàn)研究表明多變量簽名方案，如Rainbow、UOV、enTTS 在性能方面已經接近或者超過RSA、ECC 等公鑰簽名，但除了SimpleMatrix，其他加密方案在性能方面并不盡如人意．另外，公鑰數(shù)量較大也制約了多變量密碼方案的廣泛應用． Rainbow、UOV、enTTS、SimpleMatrix 等多變量密碼方案已經逐漸成為抗量子公鑰密碼芯片的重要選擇之一．其中，Rainbow和SimpleMatrix 被認為是多變量簽名方案和公鑰加密方案的代表性方案，有望成為國家抗量子密碼方案的候選．AES、RSA、ECC 等密碼的側信道研究已經逐漸形成體系，新的攻擊和防護模型被不斷提出，較大地促進了這個領域的基礎研究．相比之下，多變量密碼的側信道安全分析研究則較少．已有的多變量密碼的側信道安全分析表明多變量簽名方案，如Rainbow、UOV、enTTS 等易遭受差分功耗分析和故障分析，中心映射和仿射變換中的密鑰容易通過側信道方法進行恢復．多變量密碼的側信道安全分析和防護研究仍然處于起步階段，研究具備抗量子計算和抗側信道攻擊的密碼系統(tǒng)，可以推動多變量密碼技術的跨域式發(fā)展，對我國自主掌握抗量子密碼系統(tǒng)安全技術，確保量子計算機時代的信息安全具有重要戰(zhàn)略意義．