【作者】 刘波；

【导师】 聂旭云；

【作者基本信息】 电子科技大学 ， 软件工程（专业学位）， 2016， 硕士

【摘要】 多变量公钥密码体制(MPKC)被认为可能有效抵抗量子计算机攻击,倍受各国学者们的关注,已日渐成为了现代密码学研究的热点。由于多变量公钥密码体制的加解密过程是在较小有限域上的运算,因此相对于传统的公钥密码体制如RSA、DSA等,多变量公钥密码的加/解密效率更高。但存储多变量多项式方程组需要消耗较大的空间,使得多变量公钥密码体制拥有着较大的密钥量,这严重阻碍着其在实践中的应用。有效降低多变量公钥密码体制的密钥量,仍是研究者们十分关注的一个方向。目前已有的多变量公钥密码体制的公钥多项式的次数大多是二次的,它们几乎都面临着各种攻击的威胁,如解方程,线性化方程攻击,差分攻击,秩攻击等。经分析,如果将公钥多项式的次数增加到三次,将能有效的避免上述威胁,并大大地提高安全性。虽说这种改进将增大密钥量,但是这种牺牲空间换取高安全性是可行的。本文利用提升多变量公钥体制的公钥次数的思想,提出了三次UOV签名体制和三次多变量公钥密码体制,并成功破解了乔等人提出四次的新多变公钥密码体制。由于UOV签名体制的中心映射中不存在油变量的交叉项,使得攻击者很容易实现油醋分离伪造私钥,从而破解UOV体制。本文利用特殊的映射将中心映射的次数提升到三次,隐藏原UOV体制中心映射中的特殊结构。经过分析发现,新体制能够有效地抵抗现有的安全分析方法,并且由于新体制中的醋变量相对较少,使得与原始体制相比,新体制的公钥量降低了62%。三次多变量公钥密码体制的核心思想将小域上的明文向量映射到大域上的三次单项式。虽然公钥量有所增大,但是却能很好地抵抗现有的攻击,如线性化方程,秩攻击,差分攻击,解方程攻击等。本文在Magma平台上实现了该体制,并进行了全面的安全分析和效率分析。在乔等人提出的新多变量公钥密码扩展方案中,因为加入了非线性的温顺变换,使得经该方案改进后的体制能够有效的避免线性化方程攻击和差分攻击。本文分析了这种改进方案的一个实例,发现其存在二次化方程,利用该方程能够有效地恢复加密后的消息。论文中通过实验验证了该攻击方法。更多还原

【Abstract】 Multivariate public key cryptosystem(MPKC) is designed to resist the quantum computer, which has attracted much interests in recent years. The operations of MPKCs are defined in some small finite fields, so there are more efficient and faster than traditional public key cryptosystems, such as RSA and DSA. However, the key sizes of MPKCs are very large, which definitely hinders their applications in practice.Hence, how to reduce the public key sizes is also a hot topic in MPKCs.Currently, almost all the existing MPKCs are quadratic. Most of them are faced with the threat of variety of attacks, such as solving the equations attack, differential cryptanalysis, linearization equations attack and rank attack etc. According to our analysis, if we increase the degree of public key polynomials to three or higher, this could make the scheme be able to avoid the threats above. It may increase the key sizes,but this kind of sacrifice in exchange for high security is feasible. In our thesis, we proposed two high degree schemes, Cubic Unbalanced Oil and Vinegar Signature(CUOV) system and Cubic Multivariate Public Key Cryptosystem(CMPKC). And we broke a New Extended Multivariate Public Key Cryptography(NEMPKC) in whose degree is quartic.There are no cross terms of oil variables in the central map of UOV signature system, so an attacker can easily separate oil and vinegar and break the scheme. We use a special transformation to reconstruct the central map with cubic degree. It is secure against the existing attacks, and its key sizes are reduced by 62% compared with the original UOV.The key idea of CMPKC is to replace the polynomial in small field with a cubic monomial in big field. The public key of new scheme becomes bigger than before, but it’s very effective to against the existing attacks. Then we implement the scheme on the Magma, and analysis its security and efficiency.The nonlinear tame transformation in the NEMPKC can hide the weakness of the original scheme. And the authors indicated that the improved scheme is able to resist the known attacks. But we find that there are many quadratization equations in the central map, which can be used to recover the encrypted message effectively. We did many experiments on Magma to verify it.更多还原