公钥密码中大素数快速生成方法研究与实现

论文摘要

在现代网络应用中,信息安全是一个核心问题。特别是在信息传输和交换、网络远程认证和电子签名等应用方面,对信息的保密性、安全性、完整性和真实性要求极为严格。目前保证这些信息安全特性的主要手段,是利用基于数论理论的公钥加密机制和技术实现。而公钥加密机制算法绝大部分都是基于素数运算实现,如RSA算法,ElGamal算法等。在实际应用,为了保证加密的安全性和可靠性,算法运算都是建立在大素数的基础之上的,比如,RSA算法要求至少100位（10进制数）以上的素数。而随着计算机技术的发展,计算机计算能力越来越强,这些算法就会要求更长位数的素数来保证其加密可靠性。因此,如何快速的寻找到大素数,对加密效率和加密应用至关重要。本文在研究过程中,参考了大量国内外文献,对素数理论和素数计算等方面的研究现状进行了概括。文章主要对大素数的产生和素性判定等方面的内容进行了详细分析研究,重点对概率性测试算法进行了深入分析和对比。在研究已有大素数计算方法的基础上,结合自己研究工作环境,通过对Lehmann与Rabin-Miller实验对比分析,以及基于它们的改进方案实验结果对比分析,选择通过改进Rabin-Miller测试,以软件方式来实现大素数快速产生。算法基于对Rabin-Miller测试改进,利用C语言开发实现。本文用10000进制对大数进行表示,并在此表示基础上实现了大数的加、减、乘及大数快速求模运算。影响大素数的生成效率的主要环节是Rabin-Miller测试过程。算法先利用改进的小素数筛值法对大数进行预测试,以减少大素数生成中运算Rabin-Miller测试的次数,从而提高对合数的排除效率。对Rabin-Miller测试的改进,具体体现在:首先采用模块化的设计方法对其实现难度进行了分解;其次,对测试中证据随机数的产生进行了优化;最后,利用自己设计的试商相减法实现的大数求模运算以及自行改进的加法链生成算法实现了高次剩余运算。算法实验结果显示,改进算法能够有效提高大素数产生效率,分析结果也表明用改进算法产生的素数具有很高的可信度,算法具有较强的实际应用意义。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题研究背景与意义
• 1.2 大素数判定的研究概述
• 1.3 研究内容及工作安排
• 第二章 素数基本理论
• 2.1 素数的应用
• 2.2 素数分布
• 2.3 素数定理
• 2.3.1 欧拉定理
• 2.3.2 费马小定理
• 2.4 素数的充分必要条件
• 2.5 本章小结
• 第三章 素数测试方法分析与研究
• 3.1 素数搜索方法
• 3.2 素数测试的分类
• 3.3 确定性测试算法
• 3.3.1 试除法
• 3.3.2 AKS 算法
• 3.3.3 n-1 测试
• 3.3.4 n+1 测试
• 3.4 概率测试算法
• 3.4.1 Solovag-Strasson 概率判定法
• 3.4.2 Lehmann 测试法
• 3.4.3 Rabin-Miller 测试法
• 3.4.4 概率测试算法的比较
• 3.5 本章小结
• 第四章 大数表示与基本运算的设计与实现
• 4.1 整体分析
• 4.2 大数运算的准备
• 4.2.1 大数存储表示的数据结构
• 4.2.2 大数的生成
• 4.2.3 大数的比较
• 4.2.4 大数的输出
• 4.3 大数基本运算
• 4.3.1 大数加法
• 4.3.2 大数减法
• 4.3.3 大数乘法
• 4.3.4 大数求余
• 4.4 本章小结
• 第五章 大素数快速生成算法设计与实现
• 5.1 整体分析
• 5.2 随机数的产生
• 5.3 预测试
• s×M 的实现'>5.4 P-1=2^s×M 的实现
• 5.5 大数的2 进制转换
• 5.6 高阶大数的快速求余
• 5.7 基于改进Lehmann 测试的快速生成算法实现
• 5.7.1 Lehmann 测试与Solovag-Strasson 测试比较
• 5.7.2 Lehmann 测试算法分析
• 5.7.3 基于 Lehmann 测试改进的快速生成算法
• 5.8 基于改进Rabin-Miller 测试的快速生成算法实现
• 5.8.1 Rabin-Miller 算法分析
• 5.8.2 基于Rabin-Miller 测试改进的快速生成算法
• 5.8.3 实验方案设计及结果分析
• 5.9 安全大素数生成实验
• 5.10 本章小结
• 第六章 总结与展望
• 6.1 系统总结
• 6.2 主要工作
• 6.3 工作中的不足
• 6.4 工作中遇到的问题
• 6.5 工作中的研究发现
• 致谢
• 参考文献
• 攻硕期间取得的研究成果