多变量公钥密码系统实现研究进展*

易海博

（深圳职业技术学院 计算机工程学院，广东 深圳518055）

随着物联网的兴起和快速发展，密码系统的应用日益广泛．芯片采用的RSA（Rivest-Shamir-Adleman）[1]、ECC（Elliptic curve cryptography）[2]等公钥密码的安全性基于大整数分解或椭圆曲线离散对数问题，被美国科学家Peter Shor 证明可以使用量子计算机在多项式时间内求解[3]．尽管能够破解公钥密码的量子计算机尚未面世，但已有不少研究取得了巨大进步．谷歌在提出“量子霸权”1年多时间后，终于迎来了自己在量子计算领域里新的突破[4-5]．2018年3月5日，谷歌量子人工智能实验室（Quantum AI Lab）研究科学家Julian Kelly 在谷歌的官方博客上公布了一款拥有72 量子比特的量子处理器，名为Bristlecone（中文译为“狐尾松”），随后谷歌在洛杉矶举行的美国物理学会年会上展示了这款新的处理器．2017年11月，IBM 成功开发出了1 台50 量子比特的原型机，可为今后IBM Q 系统奠定基础[6-7]．英特尔也向谷歌发起了挑战，在2018年1月的CES2018 国际消费电子产品展上，向合作伙伴交付首个49 量子比特量子计算测试芯片．加拿大D-Wave 公司推出的专用量子计算机2000Q 已达到了2000 量子比特[8]．

我们的二代身份证使用ECC 密码，如果量子计算机的处理能力再度提升，就有可能破解该密码，不法分子就能够大肆伪造身份证．面对量子计算机的巨大威胁，美国政府率先行动，美国国家安全局NSA 和美国国家标准与技术研究院NIST 相继公布了从现有的公钥密码体制过渡到抗量子密码体制的公告．

抗量子密码又被叫做后量子密码（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]．这些研究为多变量公钥密码的发展奠定了基础．

多变量公钥密码的发展主要分为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）被认为安全性和效率更高．油醋结构由多个油变量和醋变量组成，油变量数量和醋变量数量一样多则称为平衡油醋，不一样则称为非平衡油醋．UOV 是非平衡油醋的单层结构，而Rainbow则是非平衡油醋的多层结构．

3）第三类中心映射建立在基域上的三角形体制TTM 方案，这一类方案主要应用于多变量签名的构造，其中比较知名的是基于TTM 的TTS 签名以及增强TTS 签名enTTS，这类签名基于三角形构造，签名速度很快，但安全性比Rainbow 较低．

4）第四类介于第一类和第二类之间，其中心映射是建立在中间的域上的方案，如丢番图方程结构MFE 方案和可逆循环体制ℓ-IC 方案．

5）第五类是基于多变量二次拟群提出的方案，该方案采用了一种新的基于拟群和拟群变换理论的多变量二次陷门函数．相对于其它方案，它的加密速度相近，但它不会使密文扩张．

除了以上这5 类方案，国内外多位知名学者通过寻找新的陷门函数、改进和组合已有方案在不断提出新的多变量方案，使多变量公钥加密和签名的安全性和效率更高．美国University of Cincinnati 学者Jintai Ding 在2009年的著作《Multivariate Public Key Cryptosystems》[35]中系统地总结了多变量公钥密码体制的发展概况．

在探索多变量公钥密码的新方案的重要方法有加方法、减方法、醋变量方法和内部扰动方法等，其中减方法和醋变量方法主要用于设计多变量数字签名方案，内部扰动方法则是由美国学者Jintai Ding 提出的一种系统化的增强多变量公钥密码的安全性的方法．通过变形后的最著名的多变量公钥密码算法是SFlash 签名算法（从MI减加密算法发展而来）[36]，曾被NESSIE 确定为2004年低功耗智能卡的安全标准，但Dubois在2007年结合差分攻击和线性化方程将SFLASH 方案攻破[37]．

2 多变量密码方案实现研究进展

随着量子技术的研究不断推进，能够破解现有主流公钥密码系统的量子计算机面世的可能性越来越大，设计具有抗量子计算特性的密码系统成为非常迫切的事情．研究多变量密码实现已逐渐成为热点，主要集中在提升速度、缩小面积、优化性能等3 个方面．

加快速度的方案主要通过引入优化结构、优化有限域运算等方案来缩短时间．其中，针对Rainbow 签名速度的提升主要有：Balasubramanian 等人在FCCM 2008 会议上提出的快速实现Rainbow 签名的方案[40]，通过FPGA和ASIC 的特性将Rainbow 签名的时间大幅提升；Tang 等人在PQCrypto 2011 会议上提出的快速实现Rainbow 签名的方案[39]，通过设计优化有限域运算，例如三元乘法、并行高斯约当消元，将Rainbow 签名的时间缩短了四分之三；Petzoldt等人在PQCrypto 2013 会议上提出的快速验证UOV 和Rainbow 签名的方案[38]，将Rainbow 和UOV 的签名验证时间大幅缩短．针对UOV 的优化主要通过缩小公钥提升签名验证速度，缩小私钥提升签名生成速度，代表性论文有：Petzoldt等人在PKC 2012 会议上提出的缩小公钥提升UOV 签名验证速度的方案[41]和Tan 等人在Inscrypt 2015 会议上提出的缩小私钥提升UOV签名速度的方案[42]．另外，enTTS 签名和SimpleMatrix 加密也是优化实现的热点，代表性论文有：Yang 等人在CHES 2004 会议上提出的快速实现enTTS 的方案[43]和Peng 等人在ISPEC 2016 会议上提出的快速实现SimpleMatrix 加密方案[44]．

缩小面积的方案主要通过微处理器、缩小公钥、精简运算、优化有限域运算等方式实现，其中Yi 等人在2016年提出的在FPGA 上实现最小多变量密码处理器（Rainbow、UOV、enTTS）的方案[45]采用了精简指令集来实现；Czypek 等人在CHES 2012 会议上提出的在受限设备上实现Rainbow、UOV、enTTS 签名的方案[46]采用了精简运算；Tan 等人在2016年上提出的一种节省内存的Raibow 签名方案[47]和Petzoldt 等人在INDOCRYPT 2010 会议上提出的一种缩小公钥的Raibow 签名方案[48]；从公钥消耗内存的角度对面积进行了缩小；另外，Chen 等人在2016年提出的一种应用于无线传感器网络的UOV 签名方案[49]和Tang 等人在2015年提出的一种应用于云计算环境的PMI+加密方案[50]也是缩小面积的方案的代表．

追求时间面积平衡的方案主要有Wang 等人在2016年提出的基于神经网络实现多变量密码的方案[51]、Shih 等人在2013年提出的高效实现TTS的ASIC 方案[52]、Bogdanov 等人在CHES 2008 会议上提出的高效实现UOV、enTTS、Rainbow 的方案[53]、Yi 等人在2018年提出的高效实现Rainbow的方案[54]、Chen 等人在CHES 2009 会议上提出的高效实现HFE、Rainbow、TTS 的方案[55]．这些方案在提升方案速度的同时，同时优化面积，达到性能均衡，主要采取了systolic、神经网络等特殊结构实现．

上述多变量密码方案的实现研究表明多变量签名方案，如Rainbow、UOV、enTTS 在性能方面已经接近或者超过RSA、ECC 等公钥签名，但除了SimpleMatrix，其他加密方案在性能方面并不尽如人意．另外，公钥数量较大也制约了多变量密码方案的广泛应用． Rainbow、UOV、enTTS、SimpleMatrix 等多变量密码方案已经逐渐成为抗量子公钥密码芯片的重要选择之一[56]．

3 多变量密码方案侧信道分析研究进展

对于密码系统，它的安全性遵循“木桶效应”，在防范代数攻击的同时，还需防范侧信道攻击，这种攻击方法基于密码系统物理实现过程中泄露的信息，属于物理攻击的一种，并不破坏硬件的物理结构，也不需要利用算法数学方面的弱点．信道攻击的原理是侧信道信息（例如能量消耗、电磁泄露、时间信息、声音等）可以为破解密码系统密钥提供额外的帮助．相应的，常用的侧信道攻击方法包括时间攻击[57]、能量攻击[58]、电磁攻击[59]、故障攻击[60]等．

在侧信道攻击的方法中，故障攻击的原理是尝试改变密码系统运行的环境，例如电压、时钟、温度、光亮等，从而在密码运算过程中造成故障，观测相关变化，以达到破解密钥的目的．一种常用的故障攻击方法是对某一个寄存器使用激光束，导致寄存器的部分比特产生翻转，即从0 变成1 或从1 变成0．故障攻击已经成功在攻击RSA签名中实施[61]．

另一种常用的侧信道攻击方法是能量攻击，基于观测密码系统的能量变化而实现攻击．常用的能量攻击方法包括简单能量攻击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 攻击需要基于能量模型实现，例如汉明重量模型和汉明距离模型[65]．汉明重量模型基于密码系统中数据的汉明重量的变化进行差分能量攻击，而汉明距离模型则基于数据的汉明距离．一般来说，汉明距离模型更适合CMOS 密码系统攻击．

目前，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 等易遭受差分功耗分析和故障分析，中心映射和仿射变换中的密钥容易通过侧信道方法进行恢复．多变量密码的侧信道安全分析和防护研究仍然处于起步阶段，研究具备抗量子计算和抗侧信道攻击的密码系统，有重要现实意义和理论价值．

4 总结和展望

近年来，多变量密码的算法设计和分析是抗量子计算密码领域研究的热点之一．本文从多变量密码的系统实现和侧信道分析和防护等方面的研究展开了介绍．多变量密码方案的实现研究表明多变量签名方案，如Rainbow、UOV、enTTS 在性能方面已经接近或者超过RSA、ECC 等公钥签名，但除了SimpleMatrix，其他加密方案在性能方面并不尽如人意．另外，公钥数量较大也制约了多变量密码方案的广泛应用． Rainbow、UOV、enTTS、SimpleMatrix 等多变量密码方案已经逐渐成为抗量子公钥密码芯片的重要选择之一．其中，Rainbow和SimpleMatrix 被认为是多变量签名方案和公钥加密方案的代表性方案，有望成为国家抗量子密码方案的候选．AES、RSA、ECC 等密码的侧信道研究已经逐渐形成体系，新的攻击和防护模型被不断提出，较大地促进了这个领域的基础研究．相比之下，多变量密码的侧信道安全分析研究则较少．已有的多变量密码的侧信道安全分析表明多变量签名方案，如Rainbow、UOV、enTTS 等易遭受差分功耗分析和故障分析，中心映射和仿射变换中的密钥容易通过侧信道方法进行恢复．多变量密码的侧信道安全分析和防护研究仍然处于起步阶段，研究具备抗量子计算和抗侧信道攻击的密码系统，可以推动多变量密码技术的跨域式发展，对我国自主掌握抗量子密码系统安全技术，确保量子计算机时代的信息安全具有重要战略意义．