论文部分内容阅读
有限域上的乘积运算是许多加密系统和编码理论的一种基本运算。有限域乘法的运算效率在很大程度上决定了整个系统的性能。运算速度对于很多密码系统来说至关重要,在一些密码系统里,其最主要的运算量来源于计算大量的有限域整系数多项式的乘积。因此提高有限域整系数多项式乘法的速度对于这类密码系统来说很有应用价值。本文采用基于数论变换的算法结构,完成了有限域快速多项式相乘运算核的设计及FPGA实现和测试验证,包括从算法设计、系统结构设计、各个子模块的设计和实现、系统联调仿真到FPGA的下载实现和测试整个流程。研究设计了一种具有自主知识产权的高速、高精度的有限域多项式相乘运算核。提出了一种可行的、易于硬件实现的结构,具有无误差、速度快、设计复杂度低的优点。在Xilinx公司的100万门的VirtexⅡ器件上实现,进行一次两个256点的有限域多项式相乘仅需65. 4μs。和采用3台PC并行处理的软件实现方法相比,速度有2倍的提高;和采用1台PC处理相比,速度有7倍的提高。可直接应用于数字签名运算中。本文有特色的主要工作如下:1、 利用Fermat数变换(FNT)的循环卷积性质进行整系数多项式相乘,提高了运算的精度和速度。本文还利用迭代和多项式拆分相乘的技巧,将高次幂多项式相乘转化为低次幂多项式相乘再进行迭加,克服了FNT运算点数的限制。并采用乒乓RAM的结构提高运算能力,得到流水线结构。2、 采用类似基4 FFT的快速算法实现64点FNT。所设计的FNT模块可并行处理两组数据。并具有可扩展的性能,可根据具体的要求实现多组数据并行处理。3、 采用新码码制进行FNT运算。其中涉及的乘法运算和模运算均被方便地转化为移位运算和加减法运算,有利于硬件实现。4、 采用带进位的模加器和保留进位加法(MCSA)的结构提高FNT和模乘的处理速度并节省硬件资源。5、 运算核采用VirtexⅡ系列xc2v1000-4fg256实现,最高工作频率可达到100MHz,完成一次运算所需的时间为65. 4μs。并将本运算核成功地应用于有限域多项式幂运算中。