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

RSA快速实现算法的研究与改进

作　者: 梁小英
导　师: 黄铮
学　校: 北京邮电大学
专　业: 密码学
关键词: 公钥密码 模乘 模幂 滑动窗口编码 限长游程编码
分类号: TN918.1
类　型: 硕士论文
年　份: 2010年
下　载: 237次
引　用: 0次
阅　读: 论文下载
 

内容摘要


公钥密码体制使得密码学由传统的政府和军事应用领域走向商用和民用领域,使得现代密码学的商业价值和社会价值得到了广泛的认同。目前,RSA是使用最为广泛的一种公钥密码体制。但由于RSA算法是基于大素数分解难题的,特别是为防止各种攻击,其模长在不断增加,其主要运算是大整数的模幂和模乘,算法的运行速度较慢成为RSA的一个显著缺陷。因此,对大整数模幂和模乘算法以及取模算法的加速实现进行研究具有重要的理论意义和实用价值。本课题重点研究RSA算法的加速实现技术。当前针对RSA的研究主要包括密钥生成的优化、素性检测的优化、大整数模乘和模幂运算的优化等,本文重点研究大数模乘和模幂运算的优化问题。本课题受目前流行的蒙哥马利算法思想的启发,提炼出了模简化定理并予以证明,简化模逆运算,优化了蒙哥马利算法。本课题在研究了基于滑动窗口编码的算法之后,设计出新颖的限长游程编码,并将其应用于设计大整数的模乘和模幂运算实现算法。在完成算法设计之后,本文对算法的时间和空间复杂度进行了详细的分析。对比已有的相关算法效率,在理论上证明了算法的优越性。另外,还编程模拟实现了算法,通过实验证明了算法的效率确实有较大提高。本文还研究了行程编码,并试图将行程编码直接应用于设计大数模乘和模幂算法,经过分析得出行程编码并不适合应用于设计大数模乘和模幂算法的结论,从而进一步证明了本文设计的限长游程编码是应用于设计大整数的模乘和模幂算法的较优编码技术。本课题的完成,为公钥密码体制的进一步推广作出了较大的贡献,使得主要运算为大整数模幂运算的公钥密码算法的运算速度大大提高,具有广阔的商业价值。

全文目录


摘要  4-5
Abstract  5-9
第一章 绪论  9-15
  1.1 引言  9
  1.2 国内外研究现状  9-11
  1.3 大整数模幂乘的应用背景  11-13
    1.3.1 RSA公钥密码体制  11-12
    1.3.2 ELGamal公钥密码体制  12
    1.3.3 DSA公钥密码体制  12-13
  1.4 本论文的工作  13-15
第二章 经典算法  15-21
  2.1 二进算法及其实现  15-16
    2.1.1 S-X二进算法  15-16
    2.1.2 自右至左扫描二进算法  16
  2.2 M-进算法  16-17
  2.3 因子算法  17
  2.4 幂树算法  17-18
  2.5 加法链算法  18-19
  2.6 基于CRT的模幂算法  19-20
  2.7 本章小结  20-21
第三章 Montgomery算法及改进  21-27
  3.1 Montgomery算法及其实现  21-26
    3.1.1 Montgomery模乘算法  21-22
    3.1.2 Montgomery的SOS实现  22-23
    3.1.3 Montgomery模平方算法  23-24
    3.1.4 Montgomery模幂算法  24-25
    3.1.5 简化模逆运算  25-26
  3.2 本章小结  26-27
第四章 基于滑动窗口编码的算法  27-39
  4.1 滑动窗口编码  27
  4.2 基于滑动窗口的模乘算法  27-30
  4.3 算法复杂度分析  30-32
    4.3.1 时间复杂度分析  30-31
    4.3.2 空间复杂度分析  31-32
  4.4 基于滑动窗口的模幂算法  32-34
  4.5 算法复杂性分析  34-35
    4.5.1 时间复杂度分析  34
    4.5.2 空间复杂度分析  34-35
  4.6 实验及结果  35-37
  4.7 本章小结  37-39
第五章 基于限长游程编码的算法  39-50
  5.1 限长游程编码  39-40
  5.2 基于限长游程编码的快速模乘算法  40-42
  5.3 算法复杂性分析  42-44
    5.3.1 时间复杂度分析  42-43
    5.3.2 空间复杂度分析  43-44
  5.4 基于限长游程编码的快速模幂算法  44-46
  5.5 算法复杂性分析  46-47
    5.5.1 时间复杂度分析  46
    5.5.2 空间复杂度分析  46-47
  5.6 实验及结果  47-49
  5.7 本章小结  49-50
第六章 系统模型与其它方案  50-56
  6.1 基于限长游程编码的Montgomery算法  50-51
  6.2 非对称的实现系统模型  51-52
  6.3 行程编码及其在大整数模乘模幂运算的应用  52-54
    6.3.1 行程编码  52-53
    6.3.2 基于行程编码的大整数模乘算法  53-54
  6.4 本章小结  54-56
第七章 结论与展望  56-58
  7.1 结论  56
  7.2 展望  56-58
参考文献  58-60
致谢  60-61
攻读学位期间发表的学术论文目录  61

相似论文

  1. Skitter与Ark探测架构下AS级拓扑分析及动态核数建模,TP393.02
  2. 一种高性能可扩展公钥密码协处理器的研究与设计,TN918.1
  3. 基于身份的加密和签名研究,TN918.1
  4. 基于身份标识的NVD远程密钥系统的设计与实现,TN918.2
  5. 基于标识的认证体制研究与实施,TN918.1
  6. 基于灰理论的代数加密算法的研究与实现,TP393.08
  7. 基于PKI的电子签章技术的研究与实现,TP311.52
  8. 公钥密码中大素数快速生成方法研究与实现,TN918.1
  9. 小面积RSA硬件加密引擎的VLSI设计,TN918.2
  10. RSA算法研究与实现,TN918.1
  11. 多变量公钥密码系统的研究与应用,TN918.1
  12. 盲签名电子现金方案的研究与应用,TN918.2
  13. 车辆自组织网络可保护隐私的认证技术研究,TN929.5
  14. 基于椭圆曲线的数字签名研究,TN918.1
  15. 无证书签名和无证书环签密方案研究,TN918.1
  16. 基于流水线的Montgomery模乘算法硬件实现,TN918.1
  17. RSA加密子系统的设计与实现,TP393.08
  18. 基于RSA的密钥交换算法的研究,TP393.08
  19. 环Z_n上圆锥曲线盲签名的公钥密码协议及在电子选举中的应用,TN918.1
  20. RSA加密算法的研究与实现,TN918.1

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