论文部分内容阅读
多变量公钥密码是一类非常重要的后量子密码技术,目前它被认为具有抵御量子计算机攻击的潜能。它的结构非常特殊,其公钥是由一组有限域上非线性多变量多项式构成。最重要的是,多变量公钥方案的计算速度一般比基于数论的传统公钥方案快,因此,它的应用范围非常广,不但可以应用于各类安全通信系统中,如电子商务、教育系统、军事系统以及其他安全系统等,而且非常适合应用于资源有限的设备或环境里,比如USB令牌、低功耗智能卡、射频识别标签、车载系统、移动手机、掌上设备以及其他嵌入式设备等。可以说,多变量公钥密码是一类研究价值非常高的密码安全技术。然而,目前在多变量公钥密码发展道路上存在着一些亟待解决的问题。比如,安全的多变量方案少(尤其混合型多变量方案稀缺)、基础陷门种类少、公钥过长以及安全性难于形式化证明等。针对这些,本文首先着重研究双极型和混合型两大类多变量结构系统,分别设计出一种命名为TOT的双极型多变量密码系统和一种命名为RGB的混合型多变量签名系统,最后利用基于身份的机制来解决多变量密码中公钥过长问题,并提出一种具有可证明安全的基于身份的签名方案叫IBUOV。文中分别描述这三种自设计的新型多变量公钥密码系统,详细地分析它们的安全性,从各个方面综合评估它们的性能表现,并将它们与其他公钥密码系统进行充分的比较(包括以实验的形式),其具体内容如下:在第四章里,文中首先介绍一种自定义的安全陷门函数,然后利用这个安全陷门函数提出一种新型的双极型多变量公钥密码系统称为TOT,它能够用于加密、签名、认证等场合。通过详细分析发现,在适当的参数选择下TOT能够抵御目前已知的代数攻击,包括穷举攻击、仿射多元攻击、线性化方程攻击、Kipnis-Shamir攻击、提取攻击、差分攻击、Grobner基攻击以及XL攻击。文中据此给出TOT的攻击复杂度,并分析其各个构成部件的计算复杂度,以及提供一些安全参数(至少达到280)。为了更充分地说明TOT系统的性能,文中还将它与其他公钥方案(包括多变量与非多变量方案)进行详细比较。结果表明,与HFE、HFEv、Quartz相比,TOT更容易获得较高安全水平,而且适当地提高TOT的安全级并不影响其解密(或签名)速度。在80比特安全级上,实验显示TOT的Magma程序在一台2.50 GHz的普通PC上的解密(或签名)时间为0.202s;TOT的C/C++程序的签名时间为8.60ms。显然,它的解密速度比相同安全级的HFE和PMI+快;它的签名速度也比相同安全级的HFEv、Quartz和RSA-1024快。另外,从结构上看,TOT私钥映射的计算速度与C*和Sflashn2相当(虽然C*方案已经被打破,但是它的解密速度很快是一个不争的事实)。在第五章里,文中首先自定义一类结构特殊的多变量多项式称为“三色多项式”和其所对应的映射“三色映射”。之所以命名为三色多项式,是因为该类多变量多项式有三类变量,且它的二次项部分所相应的对称矩阵形式类似于色度学中的三色模型,即红绿蓝三原色模型。基于这种三色映射,本文设计出一种新型的混合型多变量公钥签名系统叫RGB(意为Red-Green-Blue)。RGB的中心映射的每个多变量多项式包含大量的二次交叉项,而且这些交叉项涉及到全部变量,从而使得中心映射的变量值能够充分地“混合”系统的消息值。这一点很重要,因为二次交叉项的数量往往在一定程度上决定系统的安全度。一般来说,二次交叉项越多,系统越安全;交叉项涉及的变量越多,系统也就越安全。通过详细分析发现,在适当参数选择下RGB系统能够抵御目前已知的代数攻击,包括穷举攻击、分离攻击、最小秩攻击、直接攻击。而其他类型的攻击方法如Thomae-Wolf攻击、高秩攻击、线性化方程攻击、差分攻击等则不适合用于攻击RGB系统。此外,在80比特安全级上,实验表明RGB的Magma程序在一台2.50 GHz的普通PC上的签名时间为0.046 s;而RGB的C程序在一台800 MHz的机器上的签名时间为3.10 ms。比较发现,RGB的签名速度比相同安全级的Sflash"2、 Quartz、UOV、Rainbow以及RSA-1024还快,而略慢于相同安全级的ECDSA-163和NTRUSign-251。总之,从安全与效率来看,RGB是一个不错的选择方案。在第六章里,文中利用基于身份机制来解决多变量公钥过长问题,并根据“基于证书基于身份的签名系统”的构造思想,提出一种基于身份的非平衡油醋签名系统叫IBUOV(意为Identity-Based Unbalanced Oil-Vinegar)。它是UOV签名系统的变种,其安全性紧紧依赖于UOV,文中对此给出它的可证明安全分析。虽然这个证明法并不具备通用安全模型的特性,但不失为初步性研究多变量可证明安全,具有一定的参考价值,因为一般来说多变量密码系统是很难使用形式化语言来证明其安全性的。与UOV相比,IBUOV的公钥(即ID)长度明显很小,因为80比特安全级的UOV的公钥长度为99.94 KB,而IBUOV的公钥仅为0.02 KB。可见,基于身份的机制在一定程度上能够解决多变量公钥过长问题。