RSA算法加密和解密的实现(Visual C++)

摘 要
自20世纪90年代以来，计算机网络技术使得计算机应用得到进一步普及和发展，但是如何保证信息的安全却是一个十分重要的问题。RSA算法在公钥密码体制中占有重要的地位。在论文中首先介绍了加密算法的数学基础，理论上说明了RSA算法的原理，以及RSA算法中参数的选择。用VC++编程实现了RSA算法加密和解密运算，在算法的实现过程中，调用了已有的大整数类函数所提供的接口函数。

关键词：密码学；RSA；加密；解密
 
Implementation of RSA Cryptosystem
Abstract
Computer network technology, whose application has gone deep into almost every field of human life and social activity, has been further popularized and developed since 1900s, but it is a very important question to guarantee information security. RSA is a crucial and significant public key cryptosystem. In the paper first the encryption algorithm is introduced based on the mathematical and theoretical introduction of the RSA algorithm theory, RSA algorithm and the parameter choices. VC + + Programming the RSA algorithm, the algorithm implementation process, has been called many interface functions of a given integer class.

Key Words: Cryptology; RSA; Encryption; Decryption
 
RSA加密解密算法
RSA加密解密算法如下：
  ⑴取两个随机大素数p和q（保密）；
  ⑵计算公开的模数n=pq（公开）；
  ⑶计算秘密的欧拉函数φ(n)=（p-1）（q-1）（保密），两个素数p和q不再需要，应该丢弃，不要让任何人知道；
  ⑷随机选取整数e，满足gcd（e,φ(n)）=1（公开e，加密密钥）；
  ⑸计算d，满足de≡1（modφ(n)）（保密d，解密密钥，陷门信息）；
  ⑹将明文m首先分成小于n的数据块，加密，从而产生密文，公式为ci=mie（modn）
要解密信息，取每个加密块ci并计算 mi=cid（modn）
因为ed=1-rφ(n)，因此cid≡(mie)d≡m i(miφ( n))-r≡ mi(mod n) = mi
其中，r 为整数。这里利用了欧拉定理： miφ( n)≡1(mod n)。以上公式从密文恢复出了明文。
公钥 n：两个素数p和q的乘积（p和q必须保密）。e：与( p- 1)(q-1 )互素
私钥 d :e-1 (mod( p - 1)(q -1))
加密  c = me(mod n)
解密  m = cd(mod n)

RSA参数的选择
技术上，RSA 算法的安全性等价于求解 RSA 单向函数的逆的困难性。但是，在实际应用中，很多时候是因为算法实现的细节的漏洞导致攻击，所以在使用RSA 算法构造密码系统时，为了保证系统的安全性，必须仔细选择各个参数。RSA的主要参数有三个：模数n，加密密钥e，解密密钥d。
下面我们讨论参数的选择以及相关的问题。

需求分析
根据需要，我们设定对软件的要求如下：
1、对于软件运行所需要的加密和解密密钥，使用其他的工具来产生，并存入在本机的文本文件中。由于RSA的实现是一个很复杂的过程，不论是系统参数选择(即加密解密时使用的密钥的产生)，还是加密解密运算，都是很复杂的过程。故在本次设计中，我们只考虑RSA的加密解密的实现。
2、由于大整数在运算上复杂性，要自己实现上千位的大整数的运算，不论是工作量，还是复杂度和难度，都比较困难，所以在进行加密解密运算时，调用了已有的大整数类提供的接口函数。
3、RSA是非对称密码体制，加密和解密的运算速度，相对于对称密码体制而言比较慢，所以主要用于加密短消息如密钥，帐号，密码等。所以在实现过程中，我们只考虑了一个分组，长度为小于等于100字节。

平台选择
本设计选用的平台是：VC++，Windows XP操作系统。选择这种平台的原因主要基于以下考虑：
Visual C++自诞生以来，一直是Windows环境下最主要的应用开发系统之一。Visual C++不仅是C++语言的集成开发环境，而且与Win32紧密相连，所以，利用Visual C++开发系统可以完成各种各样的应用程序的开发，从底层软件直到上层直接面向用户的软件。而且，Visual C++强大的调试功能也为大型复杂软件的开发提供了有效的排错手段。
更为重要的是，由于RSA在加密和解密时，需要比较大的计算。因为VC++是一种先编译后执行的语言，执行效率较解释执行的语言高，更加符合需要。

设计流程
1、首先要用其他的工具来产生执行RSA所需的系统密钥，即加密密钥对(e,n)和解密密钥对(d,n)，把它们分别存放到一个文本文件中。
2、实现把所需的密钥导入到大整数类所提供的实例中，并根据大整数类所提供的接口函数的要求，对密钥进行处理。
3、调用大整数类所提供的接口函数，实现对所给文本文件加密和对密文解密，并显示出来。这里会用到GB码的相关知识。
4、考虑未按顺序操作出现的情况，在实现过程中，程序给出了容错处理和友好提示。

目  录
1引言 1
1.1密码学应用的相关背景 1
1.2使用RSA加密的意义 2
2 RSA相关理论知识 3
2.1 RSA的数学基础知识 3
2.1.1 关于数的基本理论 3
2.1.2 欧拉定理 费马小定理 4
2.1.3 中国剩余定理 4
2.1.4单向陷门函数 5
2.2 RSA加密解密算法 5
2.3 RSA参数的选择 6
2.3.1 模数n的确定 6
2.3.2 模数e的选取原则 7
2.3.3 素数的产生 7
3需求分析与平台选择 8
3.1需求分析 8
3.2平台选择 8
4 RSA密码体制的实现 9
4.1设计流程 9
4.2 截图及运行说明 9
4.3代码实现 10
4.4 各个功能模块介绍 10
4.4.1加密和解密函数的实现 10
4.4.2 导入加密密钥模块 11
(毕业设计)
4.4.3选择文件模块 12
4.4.4加密模块 12
4.4.5导入解密密钥模块 13
4.4.6生成明文 14
5测试 16
结    论 17
参考文献 17
致    谢 18
声    明 19
 
参考文献
[1] Douglas R.Stinson，冯登国.密码学原理与实践（第二版）[M].北京：电子工业出版社，2002。
[2] 邓安文.密码学--加密演算法[M].北京：电子工业出版社，2003。
[3] 李欣.RSA公钥密码算法的能量分析攻击与防御研究[D].：电子科技大学[硕士论文]，2006。
[4] 刘强,佟冬,程旭.一款RSA模乘幂运算器的设计与实现[J].电子学报，2005，（5）:923-927。
[5] 陈艳波.RSA密码算法的改进与实现[D].长沙：湖南大学，2006。
[6] 杨波.现代密码学[M].北京：清华大学出版社，2004。
[7] 陈恭亮.信息安全数学基础[M].北京：清华大学出版社，2005。
[8] 王锦.RSA加密算法的研究[D].沈阳：沈阳工业大学[硕士论文]，2006。
 

VC﹢﹢(36)