学位论文 > 优秀研究生学位论文题录展示
OEF上的快速算法研究及其在ECC上的应用实现
作 者: 唐涛
导 师: 周亮
学 校: 电子科技大学
专 业: 密码学
关键词: 椭圆曲线 内联汇编 最优扩域 多项式乘法 有限域 标量乘
分类号: TN918.1
类 型: 硕士论文
年 份: 2005年
下 载: 85次
引 用: 1次
阅 读: 论文下载
内容摘要
椭圆曲线加密体制(ECC)是一种基于椭圆曲线上的离散对数问题而设计的非对称公钥密码体制。本文主要分析研究了最优扩域(OEF)上的快速算法及其在ECC 上的应用实现。椭圆曲线的计算算法可分为高层计算和低层计算两类算法。其中高层计算算法主要处理椭圆曲线上点的操作,而低层算法侧重于处理有限域中的多项式计算算法,本文通过将这两者有机结合来提高椭圆曲线密码系统中的计算速度。本文对理想扩域的结构特点和椭圆曲线上的标量乘(kP)快速算法进行了分析研究,并对这些快速算法加以测试改进。在最优扩域上的快速算法的研究过程中,通过分析子域求模的快速算法、域元素求逆(MAIA 算法、EEA 算法)和多项式相乘(硬乘算法、Karatsuba 算法)等经典算法后,结合我们选择的有限域(Ⅱ型最优扩域GF ((232 -46305)5))的特点,本文提出了一种基于Karatsuba 法的改进型域元素多项式乘算法,并通过理论分析证明该改进算法的计算复杂度低于Karatsuba 算法。经测试(CPU/PⅣ1.4GHz,MS Visual C++6.0),验证改进算法的性能与Karatsuba 算法相当,比硬乘算法提高了大约4%。在椭圆曲线上的标量乘快速算法的研究过程中,通过分析计算标量乘(二进制算法、Montgomery 算法、NAF 算法、2P + Q算法和FBW 算法等)的算法,本文提出了一种改进型3P 算法和一种基于固定基的MFBW 算法。改进型3P 算法通过优化正整数k 的表示形式来降低标量乘的计算复杂度,MFBW 算法利用一些预计算来提高标量乘的计算速度,并且将这两种改进算法结合来计算标量乘。经测试,改进算法的性能比常规的二进制算法和Montgomery 算法提高了大约15% ,比NAF 算法提高了大约7%。本文利用VC++内联式汇编和C 语言对算法进行软件实现,并给出了测试结果。与Daniel V.Bailey 仿真的结果相比,我们的测试数据与他的测试数据处于同一数量级或优于他的测试数据。
|
全文目录
第一章 引言 11-13 1.1 研究背景和意义 11-12 1.2 本文章节安排 12-13 第二章 ECC 的数学基础 13-25 2.1 群、域、环 13-14 2.1.1 群、域、环的概念 13 2.1.2 有限域 13-14 2.1.3 素数域GF( p ) 及其数学结构 14 2.1.4 特征为p 的有限域GF ( pm ) 14 2.2 椭圆曲线 14-18 2.2.1 椭圆曲线相关概念 14-15 2.2.2 定义在代数封闭域上的椭圆曲线 15-16 2.2.3 椭圆曲线群 16 2.2.4 椭圆曲线方程的判别式 16 2.2.5 实数域上的椭圆曲线群 16-17 2.2.6 有限域GF (p) 上的椭圆曲线群 17 2.2.7 有限域GF (pm) 上的椭圆曲线群 17-18 2.3 ECC 的原理 18-19 2.3.1 椭圆曲线群上离散对数问题与公钥加密体制 18 2.3.2 椭圆曲线域参数 18 2.3.3 ECC 的原理 18-19 2.4 椭圆曲线数字签名(ECDSA) 19-21 2.4.1 ECDSA 概述 19-20 2.4.2 ECDSA 域参数 20 2.4.3 椭圆曲线数字签名算法 20-21 2.5 椭圆曲线加密的性能分析 21-24 2.5.1 加密算法效率的评价标准 22 2.5.2 计算量与处理速度 22-23 2.5.3 存储空间占用小 23 2.5.4 带宽要求低 23-24 2.6 小结 24-25 第三章 软件实现环境 25-31 3.1 IA-32 与保护模式汇编程序 25-27 3.1.1 CPU 内部的寄存器 25 3.1.2 保护模式的内存管理 25-26 3.1.3 数据寻址方式 26-27 3.2 VC++内联式汇编 27-30 3.2.1 asm 关键字和_asm 块 27-28 3.2.2 _asm 块中访问C/C++变量 28 3.2.3 _asm 块对寄存器的影响和代码优化 28-29 3.2.4 从_asm 块中调用C/C++函数 29-30 3.2.5 标号 30 3.2.6 调试工具 30 3.3 小结 30-31 第四章 最优扩域 31-43 4.1 最优扩域的定义 31-32 4.2 最优扩域中的数学运算 32-42 4.2.1 快速子域求模 32-35 4.2.2 加法和减法 35 4.2.3 乘法(多项式相乘) 35-39 4.2.4 子域求模逆 39-40 4.2.5 域元素求逆 40-41 4.2.6 域元素模P (x) 归约 41-42 4.3 小结 42-43 第五章 椭圆曲线上的快速算法 43-54 5.1 椭圆曲线上的点加运算和倍点运算 43-45 5.1.1 实数域上的点加运算 43 5.1.2 素数域GF (p) 上的点加运算 43-44 5.1.3 有限域GF (pm) 上的点加运算 44-45 5.2 仿射坐标和投影坐标下的点加公式 45-46 5.2 ECC 上的标量乘法 46-53 5.2.1 二进制法 46 5.2.2 Montgomery 法 46-47 5.2.3 非临近生成NAF 法 47-49 5.2.4 固定基窗口FBW 法 49-50 5.2.5 2P+Q 算法 50-51 5.2.5 改进型3P 算法 51-52 5.2.6 改进型MFBW 法 52-53 5.3 小结 53-54 第六章 算法的实现和性能测试 54-72 6.1 子域求模加 54-55 6.2 子域求模减 55-56 6.3 子域求模乘 56 6.4 子域求模逆 56-57 6.5 扩域求模加 57-58 6.6 扩域求模减 58-59 6.7 扩域求模乘(硬乘法) 59 6.8 扩域求模乘(Karatsuba 法) 59-60 6.9 扩域求模乘(改进算法) 60-61 6.10 域元素求逆(EEA) 61-62 6.11 域元素求逆(MAIA) 62-63 6.12 椭圆曲线上的点加 63 6.13 椭圆曲线上的倍加 63-64 6.14 随机生成160 位二进制形式正整数 64 6.15 随机生成160 位NAF 形式正整数 64 6.16 二进制加减法kP 计算 64-66 6.17 Montgomery 法kP 计算 66-67 6.18 非临近NAF 法kP 计算 67-68 6.19 改进型算法kP 计算 68-70 6.20 综合分析 70-71 6.21 小结 71-72 第七章 总结和展望 72-74 参考文献 74-76 致谢 76-77 个人简历 77
|
相似论文
- 一种高性能可扩展公钥密码协处理器的研究与设计,TN918.1
- 多进制LDPC码构造方法的研究,TN911.22
- 星载一体化小卫星高可靠通信编码技术研究,TN927.2
- SSL协议应用于网络会议系统中的改进与研究,TP393.08
- 无线传感器网络中的分布式数据存储安全性研究,TP212.9
- 线性码自同构群的研究,O157.4
- 基于椭圆曲线动态口令身份认证方案的研究与实现,TP393.08
- 基于ECC的双因素身份认证的设计与实现,TP393.08
- 基于密码技术的安全电子邮件系统设计,TP393.098
- 基于ECC的高效可分电子现金协议研究,TP393.09
- 反逆向工程技术研究,TP311.52
- ECC协处理器专用指令与可重构单元设计技术研究,TN918.2
- 本原正规多项式系数分布的研究,TN918.1
- 椭圆曲线6Y~2=X~3-X+6上的整数点,O186.11
- 基于IP组播的密钥管理技术研究,TP393.08
- 基于指纹认证的移动支付系统设计与实现,TN929.5
- 椭圆曲线标量乘算法的设计与分析,TN918.1
- 基于GPU的椭圆曲线相关算法并行化效率分析,TN918.1
- 基于ECC的快速数字签名技术及实现,TN918.1
- 对称密码有限域运算模块可重构设计技术研究,TN918.1
- 椭圆曲线密码点乘算法的并行调度研究,TN918.1
中图分类: > 工业技术 > 无线电电子学、电信技术 > 通信 > 通信保密与通信安全 > 理论
© 2012 www.xueweilunwen.com
|