摘要：公钥密码体制是今天应用最广泛的密码体制，RSA是公钥密码体制中最具代表性的算法之一，不仅有良好的安全性，同时也易于实现，这使得其被广泛运用于各种加密场景中。可是RSA算法在实现过程需要进行大量的模幂运算，高安全性要求下的RSA要使用大位数的密钥，增加了RSA算法的计算量，影响了RSA算法的运行效率。因此，RSA算法的快速实现具有重要意义。本文研究RSA算法基本原理，分析前人改进RSA算法的可行方案，总结出能够增加RSA算法实现速度的三种基本方法：多素数RSA算法，中国剩余定理和蒙哥马利模乘法，并分析其在提升RSA算法运行效率的可行性。归纳目前常见的针对RSA攻击方式，对RSA算法进行安全性分析，证明改进的RSA算法在提升算法效率的同时依然保证高安全性。

关键词： RSA；安全性；中国剩余定理；多素数；蒙哥马利模乘法

目录

摘要

Abstract

1 绪论-1

1.1研究背景-1

1.2 国内外研究现状-2

1.3 论文主要工作-3

1.4论文组织结构-3

2 密码学基础及相关数学基础-5

2.1 密码学基础-5

2.1.1 密码学基本概念-5

2.1.2 密码体制-5

2.2相关数学基础-6

2.2.1 模运算-6

2.2.2 费马定理-7

2.2.3 欧拉定理-7

2.2.4 中国剩余定理-7

2.2.5 单向陷门函数-7

3  RSA密码算法的分析-9

3.1 RSA密码体制-9

3.1.1 RSA算法基本内容-9

3.1.2 RSA算法分析-10

3.2 RSA算法的安全性分析-11

3.2.1 因子分解模数n-11

3.2.2 攻击公共模数n-12

3.2.3 小指数攻击-12

3.2.4 选择密文攻击-13

3.2.5 时间攻击-14

3.3 防御攻击RSA的策略-14

4 改进的RSA快速实现算法分析-16

4.1 多素数RSA算法-16

4.1.1 多素数RSA算法运行过程-16

4.1.2 多素数RSA的正确性-17

4.2 CRT-RSA-18

4.2.1 CRT-RSA算法运行过程-18

4.2.2 CRT-RSA算法分析-18

4.3 Montegomery模乘法优化RSA-19

4.4优化算法比较分析-20

5 结束语-22

参考文献-23

致谢-24