有限域快速多项式相乘运算核的研究

论文摘要

有限域上的乘积运算是许多加密系统和编码理论的一种基本运算。有限域乘法的运算效率在很大程度上决定了整个系统的性能。运算速度对于很多密码系统来说至关重要,在一些密码系统里,其最主要的运算量来源于计算大量的有限域整系数多项式的乘积。因此提高有限域整系数多项式乘法的速度对于这类密码系统来说很有应用价值。本文采用基于数论变换的算法结构,完成了有限域快速多项式相乘运算核的设计及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。并将本运算核成功地应用于有限域多项式幂运算中。

论文目录

• 摘 要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 有限域发展现状
• 1.3 本论文的选题意义和研究内容
• 第二章 快速Fermat数变换的算法
• 2.1 有限域理论基础
• 2.2 数论变换、快速数论变换和Fermat数变换（FNT）
• 2.3 基4 FFNT（快速Fermat数变换）的推导
• 2.4 基于数论变换的多项式乘法
• 2.5 高次幂多项式乘法
• 2.6 本章小结
• 第三章 有限域快速多项式相乘系统结构设计
• 3.1 有限域快速多项式相乘运算流程
• 3.2 FNT/IFNT用的代码
• 3.3 预计算的多项式除法算法
• 3.4 对称乒乓RAM结构
• 3.5 系统流水线结构
• 3.6 本章小结
• 第四章 有限域快速多项式相乘运算核的设计
• 4.1 有限域快速多项式相乘运算核的系统结构
• 4.2 系统控制模块（Control）
• 4.3 分组模块（AddNet）
• 4.4 可并行处理的64点FNT变换模块（FNT）
• 4.5 模Fermat数乘法模块（MUL）
• 4.6 累加及求重模模块（Modulo）
• 4.7 本章小结
• 第五章 有限域快速多项式相乘运算核的FPGA实现和功能验证
• 5.1 VirtexⅡ系列FPGA结构及特点
• 5.2 开发流程
• 5.3 实现结果分析
• 5.4 功能测试
• 5.5 有限域快速多项式相乘运算核的一个应用
• 5.6 本章小结
• 第六章 小结与展望
• 6.1 论文小结
• 6.2 展望
• 附A：利用Poly32模块构造n=256的多项式相乘
• 攻读硕士学位期间发表的学术论文目录
• 参考文献
• 致谢