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

素性检测算法研究及其在现代密码学中的应用

作　者: 魏成行
导　师: 周大水
学　校: 山东大学
专　业: 系统分析与集成
关键词: 素性检测 Miller-Rabin 公钥密码学
分类号: TN918.1
类　型: 硕士论文
年　份: 2009年
下　载: 285次
引　用: 1次
阅　读: 论文下载
 

内容摘要


素数问题是一个使很多数学家着迷的问题。素数就是一个除了1和它自身以外不能被其它数整除的数。素数的一个基本问题是如何有效地确定一个数是否是一个素数,即素性测试问题。素性测试问题不仅在数学上是一个有挑战性的问题,而且在实际应用中也是非常重要的。在现代密码系统中,大素数的判别和寻找对一些加密系统的建立起着关键作用。很多公钥密码算法都用到素数,特别是160位(二进制)以上的大素数。RSA的公共模数就是两个512位以上的大素数的乘积;基于有限域PF上离散对数的公钥密码体制,其中素数p要求在512位以上;基于椭圆曲线离散对数的公钥密码体制(ECC)中,一般要求基点的阶是一个160位以上的大整数,且是一个素数。由此可见对大数进行的素性判断的重要性。判定一个整数是否是素数,最为简单的想法是直接利用素数的定义,用比要判断的整数小的素数去一一试除,如果能整除被检测的数的话,那就能确定无疑为合数了,但是对于大素数来说,由于计算量太大,根本无法实现以用于具体应用。所以科学家们根据素数判断的理论发明了许多新的算法,提高了判断一个大数是否是一个大素数的效率。Eratosthenes筛法是对于所有素数都有效的最古老的算法,然而它的时间复杂性是输入规模的幂指数,因此在实际中使用它是不合适的。17世纪的Fermat小定理是一些有效素性测试算法的起点,但其逆定理是不满足的。许多科学家在费马小定理的基础上进行研究发明了很多新的素数检测方法,但是这些算法大部分都是概率性的,比如说Miller-Rabin算法和Solovay-Strassen概率素数测试法。直2002年,印度的三位科学家发明了确定性的素数检测算法AKS算法。但是研究表明AKS算法的时间复杂度和空间复杂度并不能满足时间中的需要。随着椭圆曲线算法的研究的开展,许多科学家又发明了利用椭圆曲线算法进行素性检测的方法,并且成为今年来素性检测领域里的一个重要方向。本文也对2中基本的椭圆曲线素性检测算法做了简单的分析。本文从素性检测算法的基本理论入手,对素性将测算法做一个全面的介绍,对大部分的素性检测算法进行了分析,其中着重对实践中常用的Miller-Rabin算法进行了分析,并且对Miller-Rabin算法做了一定的优化,使Miller-Rabin算法的效率提高了一倍,生成1024位素数的效率提升至,在1.5G的计算机上每1.5秒生成一个,并且给出了Miller-Rabin算法的算法流程图和部分关键代码的实现。

全文目录


中文摘要  8-10
ABSTRACT  10-12
符号说明  12-13
第一章 引言  13-15
第二章 素性判定的概述  15-18
第三章 素性判定的理论依据  18-25
  3.1 定义  18-20
  3.2 素性判定方法理论依据  20-24
  3.3 本章总结  24-25
第四章 几种素性检测算法研究  25-45
  4.1 概率算法的基础  25-26
    4.1.1 PP类  25
    4.1.2 Monte Carlo算法  25-26
    4.1.3 Las Vegas算法  26
  4.2 几种素性检测所需要的算法的复杂度  26-31
    4.2.1 欧几里德算法  26-29
    4.2.2 模指数算法  29-30
    4.2.3 随机素数的生成算法  30
    4.2.4 计算Jacobi符号的算法  30-31
  4.3 素性检测算法及其分析  31-44
    4.3.1 Fermat小定理作为合性检测  31-32
    4.3.2 Euler判则作为合性检测  32
    4.3.3 Lucas检测算法  32-33
    4.3.4 Pocklington检测算法  33-34
    4.3.5 Demytko定理  34-35
    4.3.6 Monte-Carlo算法进行素性检测  35-36
    4.3.7 Las Vegas算法进行素性检测  36
    4.3.8 Solovay-Strassen概率素数测试法  36-37
    4.3.9 AKS素性检测算法  37-39
    4.3.10 几种椭圆曲线素性检测算法  39-44
  4.4 本章总结  44-45
第五章 Miller_Rabin素性检测算法  45-54
  5.1 算法描述  45-46
  5.2 算法分析  46-47
  5.3 Miller-Rabin算法的流程图及关键部分的代码  47-53
    5.3.1 Miller-Rabin算法的工作流程  47-49
    5.3.2 Miller-Rabin算法中的测试函数  49-53
  5.4 Miller-Rabin算法的一些优化  53
  5.5 有关Miller-Rabin算法的最近一些进展  53-54
第六章 素性检测算法在密码学中的重要应用  54-59
  6.1 RSA公钥密码算法  54-57
    6.1.1 RSA加密解密运算  54-55
    6.1.2 RSA签名体制  55-56
    6.1.3 Rabin签名体制  56-57
  6.3 ElGamal密码体制  57
    6.3.2 ElGamal签名体制  57
  6.4 本章总结  57-59
第七章 结束语及展望  59-60
参考文献  60-63
致谢  63-64
学位论文评阅及答辩情况表  64

相似论文

  1. Miller-Rabin素数检测优化算法研究及其并行实现,TN918.1
  2. 无证书签名和无证书环签密方案研究,TN918.1
  3. 多变量公钥密码理论在数字签名与Hash函数构造中的应用,TN918.1
  4. 门限密码方案安全性和应用研究,TN918.4
  5. 密码算法与协议简化设计,TN918.1
  6. 基于双线性配对的加密方案及密钥协商协议,TN918
  7. 基于身份的公钥密码学研究,TN918.1
  8. 基于多变量公钥密码体制的加密和签名方案的研究,TN918.1
  9. 结构化对等网络的安全性与匿名性研究,TP393.02
  10. 基于CPK的认证及密钥管理技术研究,TN918.1
  11. 基于辫群的密码方案的设计与分析,TN918.4
  12. 安全认证系统中基于PKI技术的安全中间件的开发与设计,TP393.08
  13. 移动自组网若干安全问题的研究,TN929.5
  14. 数字签名算法的研究与设计,TN918.1
  15. RSA与背包公钥密码算法的安全性分析,TN918.1
  16. 移动自组网中混合认证协议的研究,TN929.5
  17. 基于自认证的签密体制的研究,TN918.1
  18. 数字签名技术在网上报税系统中的应用,TP393.09
  19. 基于椭圆曲线的密码体制及若干算法与协议,TN918.1
  20. 基于（t，n）门限秘密共享的图像隐藏系统的研究与实现,TP309

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