公钥密码体制中强素数生成算法与大数乘法的研究

摘要

随着互联网的广泛应用，信息安全问题已成为当今待解决的首要问题之一。密码技术是使信息安全到达最重要的手段。密码体制可分为传统密码体制和公钥密码体制。公钥密码体制可很好地支持互联网用户间的保密通信。公钥密码体制最重要的两个问题是系统的安全性和运行效率。在对公钥密码体制的各种攻击中有的利用密钥对的某些特点发起攻击；有的则利用计算机不断加快的运算能力达到分解大数的目的。对此必须使用强素数并采用尽量大数位的密钥对。大数位的密钥对影响了公钥密码系统的运行效率。因此研究强素数的快速生成以及公钥密码系统的运行效率具有显著的价值。 本论文主要做了如下工作： (1) 介绍了密码学的概念及发展情况，详细介绍了公钥密码体制所用到的数论基础知识，为后面的工作打下了基础。 (2) 对公钥密码体制中的强素数生成算法进行了研究。首先介绍了公钥密码体制使用强素数的重要性，其次详细分析了几个典型的强素数生成算法，并对这些算法的优缺点进行了比较，在此基础上提出了一个强素数快速生成算法，并对它的优点进行了详细的分析和证明。 (3) 对公钥密码体制中的大数乘法进行了研究。首先阐述了公钥密码体制中改进大数乘法的意义，其次深入研究了十进制普通大数乘法和十进制分治大数乘法，提出了一个 进制的分治大数乘法，最后对提出的算法的优点从理论和实验两个方面来验证。 (4) 给出了一个基于 进制分治大数乘法的RSA算法实现。首先介绍了RSA算法，讨论了算法实现中大数进制、存储、数据结构以及精确计时等问题的一般解决方法，并分别用十进制普通大数乘法和 进制分治乘法实现了RSA算法，最后从效率方面进行了比较分析。