基于SIDH有限域的高效模乘算法的设计与实现

摘要

随着量子计算机技术的不断发展，现有的公钥密码体制所面临的挑战也越来越大，这推动了后量子密码体制的研究工作，对于未来的信息安全具有重大意义。基于超奇异椭圆曲线的同源映射问题而提出的超奇异同源椭圆曲线公钥交换协议（SIDH）虽然提出的时间不长，但是显示出极具潜力的安全性和应用前景。因为有限域上的模乘运算是SIDH公钥交换协议主要的计算瓶颈之一，所以设计并实现高效的模乘算法对于SIDH公钥交换协议的研究和应用具有重要意义。 首先，本文深入研究了几种面向SIDH公钥交换协议的模乘算法，包括蒙哥马利模乘算法、巴雷特约减算法和高效有限域的模乘算法（EFFM），并且对这几种算法进行了分析与比较，详细描述了其中性能最好的EFFM算法的原理、流程和实现。 其次，本文提出了改进的EFFM算法（IEFFM）。所提出的算法通过减少输入操作数，有效地降低了EFFM算法的计算复杂度，显著地提升了EFFM算法的速度性能。随后对所提出的IEFFM算法进行了软硬件的设计和实现，并且对实现结果做了分析与比较。其中软件实现基于GMP算术库使用C语言编写，硬件实现基于Kintex-7FPGA芯片使用Verilog HDL语言编写。实现结果的分析与比较表明，所提出的算法显著地提升了EFFM算法的速度性能，与EFFM算法相比，IEFFM算法的软件实现在速度上提升了24％，硬件实现在速度上提升了约6倍。 此外，本文还提出了一种新的基于SIDH有限域的模乘算法（NFFM）。所提出的算法受EFFM高效除法运算算法的启发，通过利用数学方式将部分除法运算转换为移位操作，有效地降低了模乘运算的计算复杂度，显著地简化了模乘算法的流程控制。本文详细阐述了NFFM算法的原理与流程，将算法进行了软件实现，并对实现的结果做了分析与比较。实验结果表明，NFFM算法的软件实现在速度性能上优于EFFM算法而劣于IEFFM算法，但是NFFM算法的适用范围更加广泛。

目录

第一个书签之前