论文部分内容阅读
随着量子技术的不断发展,能够破解RSA和椭圆曲线等公钥密码的量子计算机的问世可能只是时间问题。作为少数能够抵御量子计算机攻击的公钥密码,多变量公钥密码的重要性日益显现。多变量公钥密码的设计和安全性分析是密码学界研究的热点,但针对它的相关硬件设计的数量不是特别多,这也导致了它的商业级和工业级应用远远不如RSA和椭圆曲线等公钥密码的多。本文的目的是研究能够抵御量子计算机攻击的密码硬件,即设计和优化多变量公钥密码硬件,使之能运用于多种关键领域,保护使用者的个人信息安全。多变量公钥密码的基础运算由有限域的运算组成,例如乘法、求逆和求解线性方程组,它们的优化设计能够提升多变量密码硬件的性能。所以,我们设计了三种有助于优化多变量公钥密码硬件的有限域运算。第一种设计是有限域的快速求逆器。通过扩展二叉树,我们设计了新的快速求逆方法。目前几乎所有的有限域运算的设计均基于代数理论,我们的设计打破了这个领域研究的局限性。我们的设计既适合采取非流水线的方法,也适合采取流水线的方法,这显著地加快了求逆的速率,这也打破了目前几乎全部都是非流水线设计的局限性。实验数据和与其它有限域求逆方法的对比结果表明我们的设计显著地缩短了求逆的运算时间以及减小了求逆的时间-面积的乘积。而且,我们的设计可以经过小的修改运用于有限域的乘方运算中。第二种设计是有限域的快速多元乘法器。目前针对多元乘法进行优化的研究几乎为零,我们的设计填补了这块研究的空白。我们设计的乘法器不但是对多元乘法研究的一个创新,而且是一个新型的通用乘法器:它能够适应不同的有限域和使用不同的乘法算法。这很好的利用了不同算法在不同有限域的优势,提升了有限域乘法的性能。实验和与其它乘法器的对比结果表明我们的设计能够在计算多元乘法时更加快。另外,我们利用快速多元乘法器加速了有限域的高斯消元和多变量数字签名。第三种设计是一种有限域的快速求解线性方程组的硬件装置。它创新地把找主元、归一和消元统一起来,用一种几乎并行执行所有运算的方式显著地增加了求解线性方程组的效率。本设计的主要特点如下。首先,我们单时钟周期实现了三元乘法加速乘法运算;其次,我们设计了部分求逆方法替代求逆运算,它加速了归一和消元的运算;再次,在找主元过程中,我们利用索引减少了消耗的时间;最后,我们并行了归一和消元的两个运算,显著地加快了整个求解速度。实验和与相关设计的对比结果表明我们的方法将有限域求解线性方程组的时间缩短了一半。上述三种设计不但可以作为算法的形式存在,而且能够制造成硬件设备,这将大幅增加它们的工业价值和经济价值。我们针对密码硬件设计的两个方向(快速和高效),设计了两种Rainbow签名的硬件。快速Rainbow签名硬件显著地缩短了Rainbow签名所需的时间。我们采用了优化多元乘法、部分求逆算法和快速求解线性方程组的算法,以及综合了其它的优化,在Altera FPGA上实现了快速Rainbow签名算法。实验和对比结果表明我们将Rainbow签名的时间缩短为原来的四分之一。更加令人关注的是它的运行时间比其它的公钥签名更短,例如RSA和椭圆曲线密码。高效Rainbow签名硬件显著地提升了Rainbow签名的性能。我们的设计基于时间和面积两方面的优化,既缩短了Rainbow签名的时间,也减小了它需要的面积。我们基于优化选择有限域的不可约多项式,实现了高效的有限域乘法、求逆和求解线性方程组。实验结果证明了我们的设计显著地减小了Rainbow签名所需的时间-面积的乘积。我们将高效Rainbow签名硬件与相关公钥密码硬件进行了对比,结果表明我们的设计更加高效。Rainbow签名作为目前比较流行的多变量公钥签名之一,在工业界有广泛的应用,所以我们的设计可以为Rainbow签名的工业化提供理论基础,它具有很好的工业和经济价值。最后我们设计了一种小面积的多变量公钥密码处理器。我们的设计主要在三个方向进行优化。首先我们设计了一个模运算逻辑单元,它适用于复合有限域。然后我们设计了一个精简的指令集和解码器。最后我们对寄存器采取了分时复用的方式减小实现的面积。通过其它优化,例如,可逆仿射变换、多变量多次多项式的系数求值和求解线性方程组的精简算法,以及整合上述设计,我们的多变量公钥密码处理器在低资源的Xilinx FPGA上实现,只使用了非常有限的器件资源。我们在小面积多变量公钥密码处理器上实现了三种多变量数字签名方案,即非平衡油醋签名、Rainbow签名和en-TTS签名方案。这三种多变量数字签名方案在我们的处理器上运行的速度适中,它们可以满足绝大部分的应用。当然我们的密码处理器并不局限于使用这三种密码算法,它还可以实现其它多变量公钥密码算法以及其它密码算法。我们将小面积多变量公钥密码处理器与其它公钥密码硬件进行了对比,结果表明我们的设计是目前最小的处理多变量公钥密码算法的密码硬件之一。