学位论文 > 优秀研究生学位论文题录展示

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

作　者: 韩芳
导　师: 赖宗声
学　校: 华东师范大学
专　业: 微电子学与固体电子学
关键词: 有限域 快速算法 多项式相乘 FNT 模乘
分类号: TN918
类　型: 硕士论文
年　份: 2005年
下　载: 138次
引　用: 0次
阅　读: 论文下载
 

内容摘要


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

全文目录


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

相似论文

  1. 一种高性能可扩展公钥密码协处理器的研究与设计,TN918.1
  2. 多进制LDPC码构造方法的研究,TN911.22
  3. 星载一体化小卫星高可靠通信编码技术研究,TN927.2
  4. 基于差分方程的激光谐振腔模式快速算法及其应用研究,TN248
  5. 线性码自同构群的研究,O157.4
  6. 电磁超声表面波换能器换能效率的研究,TB552
  7. 本原正规多项式系数分布的研究,TN918.1
  8. Hermitian Toeplitz矩阵向量积的计算,O241.6
  9. 基于GPU的椭圆曲线相关算法并行化效率分析,TN918.1
  10. 对称密码有限域运算模块可重构设计技术研究,TN918.1
  11. 基于FPGA的数字锁相检测系统,TN911.8
  12. 在Galois有限域GF（2~n）中的图像置乱加密的研究,TP309.7
  13. 有限域上一类线性方程的性质,O241.6
  14. 基于分圆方法的差集偶及跳频序列的构造研究,O157.2
  15. 有限域上的k-型高斯正规基及Reed-Solomon码,O157.4
  16. 主QF环上模的结构定理及在编码理论中的应用,O157.4
  17. 有限域上的旋转对称函数与k-型高斯正规基,O153.4
  18. 一种快速算法在弹塑性结构可靠度计算中的应用,TB114.3
  19. ECC标量乘法VLSI实现以及功耗分析攻击技术研究,TN918.1
  20. 基于ZEVIO 1020系统的JPEG解码研究,TP391.41
  21. 椭圆曲线密码体制的研究与分析,TN918.1

中图分类: > 工业技术 > 无线电电子学、电信技术 > 通信 > 通信保密与通信安全
© 2012 www.xueweilunwen.com