摘 要

本文主要综述了基于大整数分解的数论基础及散列函数，并简述了经典的整数分解算法和现代理论计算机科学研究中提出的几种解决整数分解的新算法，然后又提出了一种新的因子分解方法；最后对RSA算法以及RSA扩展算法进行了介绍、对比、分析和总结。

论文主要分析了大整数分解的经典算法、新算法和一种新的因子分解方法，并分析了RSA算法及RSA扩展算法的加密解密原理、安全性、可靠性。

分析结果表明：这种新的因子分解方法是对试除法的一次改进，有关大整数分解的高效算法有待于进一步开发；通过扩展素因子的个数的RSA扩展算法能够达到RSA算法的安全性。

本文的特色:基于RSA算法的安全性依赖于大整数分解的困难性，本文主要介绍了有关大整数分解的各种算法的演进，并提出一种新的因子分解方法，最后提出了通过扩展因子的个数以达到更高的安全性的RSA扩展算法。

关键词：公钥密码体制；RSA算法；RSA扩展算法；大整数分解；

Abstract

This review focuses on the basic theory of numbers and hash function of integer factorization,and outlines several classic modern integer factorization algorithms and a new algorithm to solve the integer factorization which was put forward in theoretical computer science ,Then proposes a new method of factorization;At last,making the presentation, comparison, analysis and summary toward the RSA algorithm and RSA expansion algorithm.

Paper analyzes the classical integer factorization algorithm, the new algorithm and a new factorization method;then analyzes the encryption and decryption principle , security, and reliability of the principles of the RSA algorithm and RSA expansion algorithm.

The results show that: this new approach is to try factoring division again improved, efficient algorithms related to the integer factorization need to be further developed; The RSA expansion algorithm can achieve security of the RSA algorithm through expansion of the number of prime factors.

Features of Text: Since the security of the RSA algorithm relies on the difficulty of factoring large integers, this paper describes the evolution of the relevant integer factorization algorithms, and proposes a new factorization method. Finally, by spreading the number of the factor to achieve greater security of RSA expansion algorithm.

Key Words:public-key cryptography; RSA algorithm; RSA expansion algorithm; Integer factorization;

目 录

摘要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2研究目的及意义 2

1.3研究内容 2

第2章 数学基础 3

2.1数论基础 3

2.1.1大整数分解问题 3

2.1.2相关定理 3

2.2散列函数 4

2.2.1单向函数 4

2.2.2单向散列函数 5

第3章 经典的整数分解算法 7

3.1因子分解算法 7

3.1.1欧拉函数法 7

3.1.2 蒙特卡罗算法 8

3.1.3 p-1算法 8

3.1.4  平方同余法 9

3.2一种新的因子分解法 10

第4章 RSA算法以及RSA扩展算法 13

4.1 RSA算法 13

4.1.1 获取密钥 13

4.1.2 明文加密 13

4.1.3 密文解密 14

4.1.4 安全性 14

4.2研究现状 15

4.3 RSA扩展算法 15

4.4比较与分析 16

第5章 总结与展望 17

参考文献 19

附录 21

致谢 23

第1章 绪论

数学和密码学自古就有着密切的关系，而且大整数分解问题是数学领域的一个大的难题，同时也是密码学中的一个重要的组成部分。大整数分解问题困难程度伴随着密码学的广泛应用和不断发展在不断减弱，现如今所有的基于大整数分解困难性的签名和算法都是建立在我们公认的“安全”的基础之上。可是我们得出的一个非常重要的结论是：公钥密码体制（包括RSA）永远不能提供无条件的安全性。Davis，Holdredge，Simmons在1983年成功的利用二次筛选法破解了（合数）的因子，而且Brent在1988年用椭圆曲线分解[1]的最大的整数是费尔马玛数，同时Lenstra和Manasse在1989年已经可以利用二次筛选法通过把计算分配给数百台离得很远的工作站来分解106位的十进制数，Leyland,Lenstra,Graff以及Atkins于1994年再次利用二次筛选法分解了被称为Rsa-129的129位十进制数。大整数分解之所以能够进展的如此之快，除了得益于计算机性能的改进之外，其中最关键的因素是算法的改进，因为采用陈旧的分解法是永远不可能分解了这样大的整数的。大整数分解的速度随着计算机分解方法的发展和硬件水平的提高也得到了极大的提高。因此，大整数分解的困难性在日益减弱，而且对大整数分解的算法研究不仅具有重要的现实价值，同时更具有非常广阔的实际应用价值。

1.1 研究背景