基于多项式基底的字串行乘法器设计与实现

发布时间：2020-06-23 14:26

【摘要】：随着网络科技的发展,1024位的RSA算法被破解,椭圆曲线加密算法逐渐取代RSA算法成为主流的加密技术。椭圆曲线加密算法常实现于素数域和二元扩域,而二元扩域中的运算无需考虑进位链且适合硬件实现,因此得到广泛研究与应用。在二元扩域下椭圆曲线加解密算法中最为耗时的操作为多倍点运算,而多倍点运算需要频繁调用加法和乘法。其中加法运算可以使用异或操作来解决,因此设计一个高效率低面积复杂度的乘法器是至关重要的。决定乘法器运算效率的因素主要有两个,一个为表示域元素的基底,另一个为乘法器的结构。在二元扩域下,域元素的表示方式中最为常用的两个基底为多项式基底和高斯正规基。本文选择表示直观、易于分割的多项式基底来表示域元素。现有的乘法器架构中主要分为三类,位串行,位并行和字串行结构。为了能够达到时间和空间复杂度上的平衡,因此本文选择字串行结构作为乘法器结构。本文从多项式基底和不可约三项式出发重新定义了一种新型的多项式基底并结合多项式基底定义了双基底乘法。从而使得双基底乘法可转换成矩阵向量乘积形式并且该矩阵满足Toeplitz矩阵的性质。根据Toeplitz矩阵的形式以及k-way TMVP(Toeplitz Matrix Vector Product)方法,本文设计出了一种低空间复杂度的字串行乘法器。虽然本文设计的乘法器在计算时间上相比其他已存在乘法器略大,但是在面积、空间复杂度上有着显著的优势。尤其在分段数K取值为4、6时能够达到时间复杂度与空间复杂度上的平衡,更加利于现代的嵌入式移动设备的实现。使用Verilog HDL编写了改进的移位相加法和该乘法器架构相应的two-way TMVP方法并通过Model Sim进行的功能仿真验证,验证了乘法方法的正确性。同时使用Xilinx ISE评估了两种方法的硬件资源利用率以及最大频率等指标,并在Spartan-6系列的FPGA开发板上使用串口与上位机通信实现了256位的多倍点运算。
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP332.22

【参考文献】