RSA可视化算法程序的实现与研究

RSA可视化算法程序的实现与研究[java毕业论文下载]

RSA算法的实现

 

摘  要

本文设计的是一套完整实用的RSA文件加密解决方案,并具体编码实现。本文采用费马小定理测试素数,使用Montgomery加快大数模乘运算,用C++实现RSA加密算法类库,并在32位windows平台封装成组件。在.Net平台引用此组件,实现可以对任意文件进行RSA加密操作的窗体应用程序。经过加密的文件以及密钥文件都是文本文件。本文首先给出关键类类图、整个应用程序的结构描述文档,然后对关键模块流程图、详细的接口文档进行阐述,并给出关键的实现代码,最后对应用程序进行测试,对测试结果进行分析研究,进而对应用程序进行改进,对关键算法进行尽可能的优化,最终得到一个在windows运行的可以用指定密钥对任意文件进行RSA加密并可解密的完整应用程序,和一些相关的可移植组件。

 

关键词: RSA;文件加密;Montgomery;费马定理

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Implement of RSA Algorithm

Abstract

In this paper, a solution of encrypting file with RSA algorithm and the codes of this system are introduced. Fermat theory is used to test prime number. Montgomery is used to cut short the time of modular multiplication of large number. The class library of RSA is implemented in C++, and packaged to component on the platform of 32 bits windows. On the platform of .Net, the application is implemented with reference of this component and can encrypt any file with RSA. Both encrypted files and key files are text files. In this paper, core class figures and the framework are first introduced. Then the flow of core modules and detail interfaces are stated and the kernel codes are showed also. Finally, it analyzes the result of test, then optimizes core algorithm. In the conclusion, an entire application which can encrypt any files with RSA algorithm using given key and some transplanted components are implemented.

 

Key words: RSA ; File Encryption ; Montgomery ; Fermat

 

目  录

论文总页数:35页

1  引言 1

1.1课题背景 1

1.2 RSA算法介绍与应用现状 1

1.3 RSA应用于文件加密的分析 2

1.3.1 文件加密使用RSA的可行性 2

1.3.2 文件加密使用RSA的意义 3

2  RSA文件加密软件的设计与实现 4

2.1 需求分析与总体设计 4

2.1.1 功能分析 4

2.1.2 工程方案选择 4

2.2 各部分的设计与开发 5

2.2.1 实现RSA加密算法的C++核心类库 5

2.2.2 封装C++核心类库的DLL组件 25

2.2.3 引用DLL.Net类与实现文件操作功能的窗体应用程序 26

3  软件整体测试与分析改进 27

3.1 编写测试各项性能需要的精确计时类 27

3.2 测试数据与分析改进 27

3.2.1 密钥生成测试 27

3.2.2 数据输入输出测试 28

3.2.3 加密解密测试 29

结    论 31

参考文献 32

     33

     34

     35

 

 

1  引言

1.1课题背景

RSA公钥加密算法是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也十分流行。算法的名字以发明者的姓氏首字母命名:Ron Rivest, Adi Shamir 和Leonard Adleman。虽然自1978年提出以来,RSA的安全性一直未能得到理论上的证明,但它经历了各种攻击,至今(2006年)未被完全攻破。随着越来越多的商业应用和标准化工作,RSA已经成为最具代表性的公钥加密技术。VISA、MasterCard、IBM、Microsoft等公司协力制定的安全电子交易标准(Secure Electronic Transactions,SET)就采用了标准RSA算法,这使得RSA在我们的生活中几乎无处不在。网上交易加密连接、网上银行身份验证、各种信用卡使用的数字证书、智能移动电话和存储卡的验证功能芯片等,大多数使用RSA技术。

当今公钥加密更广泛应用于互联网身份认证,本课题将公钥加密算法RSA应用于小型文件加密。将任意文件加密成文本的解决方案,使其使用更加灵活。整个工程的分层设计,给引用移植和后续开发带来便利。

1.2 RSA算法介绍与应用现状

RSA算法可以简单叙述如下:

<密钥生成>

取素数p,q,令n=p×q.

取与(p-1)×(q-1)互素的整数e,

由方程d×e=1 (mod (p-1)×(q-1))解出d,

二元组(e,n)作为公开密钥,

二元组(d,n)作为私有密钥.

<加密解密>

b=ae mod n,c=bd mod n.

附录中给出了证明a=c (mod n).

RSA公开密钥加密算法自20世纪70年代提出以来,已经得到了广泛认可和应用。发展至今,电子安全领域的各方面已经形成了较为完备的国际规范。RSA作为最重要的公开密钥算法,在各领域的应用数不胜数。RSA在硬件方面,以技术成熟的IC应用于各种消费类电子产品。

RSA在软件方面的应用,主要集中在Internet上。加密连接、数字签名和数字证书的核心算法广泛使用RSA。日常应用中,有比较著名的工具包Open SSL(SSL,Security Socket Layer,是一个安全传输协议,在Internet上进行数据保护和身份确认。Open SSL是一个开放源代码的实现了SSL及相关加密技术的软件包,由加拿大的Eric Yang等发起编写的。相关详细介绍见http://www.openssl.org/about/ )。Open SSL应用RSA实现签名和密钥交换,已经在各种操作系统得到非常广泛的应用。另外,家喻户晓的IE浏览器,自然也实现了SSL协议,集成了使用RSA技术的加密功能,结合MD5和SHA1,主要用于数字证书和数字签名,对于习惯于使用网上购物和网上银行的用户来说,几乎天天都在使用RSA技术。

1.3 RSA应用于文件加密的分析

1.3.1 文件加密使用RSA的可行性

通过1.2节的论述,不难看出RSA当今的应用多在于数字签名和证书等方面。之所以只应用于这些短小数据的加密解密,是因为RSA算法加密极慢,速度是DES对称密钥加密速度的千分之一左右。正是因为这样,把RSA应用于普通文件加密的想法一直被忽略。通常文件被想象成大数据块,但是实际上在日常应用中,有些极其重要的文本资料是并不太大的,比如因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。

虽然RSA加密运算的速度十分慢,但是在PC性能越来越好的今天,对于几千字节的数据进行一次几百位密钥的RSA加密,所消耗的时间应该是可以接受的。下面结合大数运算程序的调试,从理论上简单的分析消耗时间。在一台普通配置的PC机上对一个整数进行幂模运算,因为公开密钥的e通常取的较小,所以指数取一个小整数,比如C353,模一个70字节长的整数(140位十六进制,大数单元以线性组方式实现,对应到RSA算法中,这相当于约560bit的n),调试一个函数测试,按初等数论中的知识对程序进行算法优化,最终在一台配置为AMD Athron2800+,外频333MHZ,物理内存512MB的PC上测试需要约45毫秒时间。如果按这种速度,逐字节对1KB的数据进行同样的运算,所消耗的时间理论上为45毫秒的1024倍即约45秒。这个时间并不是非常长。

其实从一个简单的角度来说,既然RSA用于数字签名可行,那就完全可以用于同样大小的普通文件。对于较大的文件,如果分成与数字签名同样大小的段(这里假设数字签名较短,不分段一次计算加密完成),分开的各段逐一进行加密运算,那所需要的时间也只是按文件大小线性的增长。通常数字签名为几十字节,加密运算并不需要很长的等待,这就说明对于几百字节或一两K字节大小的文件来说,如果进行RSA加密,并不会是非常漫长的工作。当然,如果文件更大,加密就显得十分漫长了。比如按前面叙述的45毫秒大数运算程序推理,加密1M字节大小的文件需要约1天的时间。所以,要在普通PC用几百位以上的长密钥RSA加密文件,文件不能过大,一般可以接受的上限是几KB。如果要在较短时间内加密大文件,需要缩短密钥长度以减小运算量,这将带来安全性隐患。

本文的第3章将根据实际调试好的软件,测试给出具体的时间消耗数据。例如,在一台配置为AMD Athron2800+,外频333MHZ,物理内存512MB的PC上测试实现的软件,以560bit的n逐字节加密一个1KB大小的文件需要55秒。通常记录如银行帐号密码等重要数据的文本文件大小不足百字节,加密只需要数秒钟。所以对于小型文件,进行较长密钥的RSA加密是完全可行的。

 

1.3.2 文件加密使用RSA的意义

如1.3.1节所述,小型文件加密可以使用RSA。比如,因担心遗忘而用普通文本记录的银行帐号和密码、不应被陌生人知道的重要电话号码、几千字节大的重要小图片等。可行的方法未必是必要的,本小节讨论何种文件适合用非对称密钥加密,即RSA加密文件的意义所在。

对于前面叙述的带有重要信息的小型文本和二进制数据的维护,①如果不加密,将无法放心的保存在计算机上,尤其是连网的或机房里的公共计算机。②如果借助功能强大的大型多用户数据保护程序维护几个小型文件,显得十分烦琐,好比杀鸡用牛刀。③如果采用对称密钥加密,即加密解密的密钥相同,只适合部分情况。在某些情况下,使用对称密钥加密文件,交流使用不够方便。比如,张三由于某种原因,需要将自己的某个文件在公共计算机上留给李四,而不希望别人看到内容。如果采用对称密钥加密,张三和李四提前约好一个密码就可以。但是如果张三想要在同一台公共计算机上再留一个秘密文件给王五,而不希望别人看到,就要和王五另外约定一个密码。如果需要在这台公共计算机上留十个文件给不同的人,自己就要记和十个人约定好的密码,这样以来交流起来不够方便,因为对于张三,要自己维护太多的密钥。非对称密钥(公开密钥方式)恰好解决这样的问题。只要大家都在这台计算机或这台计算机可以访问到的地方,留下自己的公开密钥,一切就变的容易解决了。张三要留给李四的文件,就用李四的公开密钥加密,要留给王五的文件,就用王五的公开密钥加密。李四和王五只要把留给自己的文件用自己的私有密钥解密,就可以得到留给自己的文件了。显然,非对称密钥体制更适合多用户交流,而将这种加密方式直接应用于文件加密,使我们在公开场合的交流更加灵活方便。

综上所述,使用前面叙述的方式加密文件有两点重要意义:①应用非对称密钥加密任意文件,使非对称密钥的应用不仅仅局限于互联网络。②非对称加密后的数据变换成文本,使得我们可以通过几乎任何方式安全传递任意文件,比如在只有http的环境使用xml方式。

2  RSA文件加密软件的设计与实现

2.1 需求分析与总体设计

2.1.1 功能分析

经过1.3.2节的论述,我们可以将对软件的要求总结如下:

① 可以按要求的位数生成非对称密钥。

② 可以用指定密钥以RSA算法加密任意一个文件,加密生成的数据为纯文本。

③ 可以装载加密过的文件,并用指定的密钥解密还原出原文件。

④ 提示信息完整、操作舒适、图形界面雅观

按上述描述,给出Use Case和Statechart如图2-1。

 

图2-1 本项目的 Use Case和Statechart

根据以上分析,一般来说,需要进行编码的程序有

①RSA密钥生成 ②RSA加密解密 ③任意文件的读取 ④各环节必要的数据编码转换 ⑤图形操作界面。

 

2.1.2 工程方案选择

综合考虑复用性、可维护性和执行效率,较妥当的方法是分层设计。核心的RSA算法由C++类库实现,针对用户所在的操作系统封装成本地化组件。其他各功能如文件操作、数据编码转换和图形界面等,由托管代码借助虚拟机平台标准库的功能快速开发实现(本文针对选用.Net上的C#论述,选用java由JNI或其他方式调用本地组件,设计模式上是完全类似的)。这种开发方式,核心功能集中在最底层,在不断的封装中针对具体环境对组件功能不断扩充,任意一个层面的封装都可以被直接应用到其他项目,比如在Web使用以前为某窗体程序写的组件、给嵌入式设备交叉编译算法库等。但是每一层都需要依赖底层的所有组件。图2-2形象的说明了分层设计给复用带来的好处。

图2-2 综合考虑复用性、可维护性和执行效率的分层设计

选用这种设计方案,上层使用C#,底层算法使用C++,可以由一个Visual Studio解决方案管理,给调试带来极大的方便。整个工程分四层,实现RSA加密算法的C++核心类库、封装C++核心类库的DLL组件、引用DLL的.Net类、实现文件操作功能的.Net窗体应用程序。2.2节详细介绍各部分的设计与开发。

考虑到工作量,本软件加解密数据没有严格遵从RSA标准PKCS #1,而是在满足设计要求的前提下,以一种尽可能简单的方式实现加密和解密。

2.2 各部分的设计与开发

2.2.1 实现RSA加密算法的C++核心类库

1. 大数存储和四则运算

根据RSA算法的要求,为了实现大数的各种复杂运算,需要首先实现大数存储和基本四则运算的功能。当今开源的大数运算C++类有很多,多用于数学分析、天文计算等,本文选用了一个流行的大数类型,并针对RSA算法和本项目的具体需要对其进行了扩充和改进。下面简单介绍大数存储和四则运算的实现原理。

最先完成的功能是大数的存储,存储功能由flex_unit类提供。和普通的类型一样,每一个大数对应一个flex_unit的实例。类flex_unit中,用一个无符号整数指针unsigned * a指向一块内存空间的首地址,这块内存空间用来存储一个大数,所以可以说,大数是被存储在一个以unsigned为单元的线性组中。在方法void reserve( unsigned x )中通过C++的new来给a开辟空间,当flex_unit的实例中被存入比当前存储的数更大的数时,就会调用reserve来增加存储空间,但是当flex_unit的实例中被存入比当前存储的数更小的数时,存储空间并不会自动紧缩,这是为了在运算的时候提高执行效率。结合指针a,有两个重要的无符号整数来控制存储,unsigned z和unsigned n,z是被分配空间的单元数,随数字变大不断增大,不会自己紧缩,而n是当前存储的大数所占的单元数,组成一个大数的各unsigned单元的存入和读出由set、get方法完成,变量n是只读的。类型unsigned在32位机是32位的,所以对于flex_unit这个大数类来说,每个大数最大可以达到 2**32个字节长,这已经超过了32位机通常的最大内存容量,所以是足够进行RSA所需要的各种运算的。图2-3形象的说明了大数存储类flex_unit对大数的管理。

 

图2-3 flex_unit对大数的管理

在flex_unit的存储功能基础上,将其派生,得到vlong_value,在vlong_value中实现四则运算函数,并实现强制转换运算符unsigned,以方便大数类型和普通整数的互相赋值。当大数被强制转换为unsigned时,将取其最低四字节的值。四则运算实现的原理十分简单,都是按最基本的算术原理实现的,四则运算过程的本质就是按一定数制对数字的计算,比如相加,就是低位单元对齐,逐单元相加并进位,减法同理。而乘除法和取余也都是按照竖式运算的原理实现,并进行了必要的优化。虽然实现了四则运算函数,但是若是程序里的运算都要调用函数,显得烦琐而且看起来不美观,所以我们另写一个类vlong,关联(Associate,即使用vlong_value类型的对象或其指针作为成员)vlong_value,在vlong重载运算符。这样,当我们操作vlong大数对象的时候,就可以像使用一个简单类型一样使用各种运算符号了。之所以将vlong_value的指针作为成员而不是直接构造的对象,也是为了提高执行效率,因为大型对象的拷贝要消耗不少机器时间。

RSA可视化算法程序的实现与研究[点击下载]

如需要全部源码,联系QQ:2812491287如需要全部源码,联系QQ:2812491287

评论