易海博

（深圳職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)工程學(xué)院，廣東 深圳518055）

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

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

抗量子密碼又被叫做后量子密碼（Post-Quantum Cryptography）[9]，重要學(xué)術(shù)會議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]，已逐漸成為這個(gè)領(lǐng)域的熱點(diǎn)．

1 多變量公鑰密碼方案

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

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

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

圖1 中心映射陷門構(gòu)造

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

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

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

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

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

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

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

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

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

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

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

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

3 多變量密碼方案側(cè)信道分析研究進(jìn)展

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

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

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

目前，AES、RSA、ECC 等密碼的側(cè)信道研究已經(jīng)逐漸形成體系[66-69]，新的攻擊和防護(hù)模型被不斷提出，較大地促進(jìn)了這個(gè)領(lǐng)域的基礎(chǔ)研究．

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

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

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

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

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

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

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

4 總結(jié)和展望

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