|
2 RSA文件加密软件的设计与实现 2.1 需求分析与总体设计 http://www.paper51.com
2.1.1 功能分析 内容来自论文无忧网 www.paper51.com 经过1.3.2节的论述，我们可以将对软件的要求总结如下： 内容来自论文无忧网 www.paper51.com ① 可以按要求的位数生成非对称密钥。 copyright paper51.com ② 可以用指定密钥以RSA算法加密任意一个文件，加密生成的数据为纯文本。 http://www.paper51.com
③ 可以装载加密过的文件，并用指定的密钥解密还原出原文件。 http://www.paper51.com
④ 提示信息完整、操作舒适、图形界面雅观 内容来自论文无忧网 www.paper51.com
按上述描述，给出UseCase和Statechart如图2-1。 内容来自论文无忧网 www.paper51.com
copyright paper51.com 图2-1 本项目的 Use Case和Statechart copyright paper51.com 根据以上分析，一般来说，需要进行编码的程序有 内容来自www.paper51.com ①RSA密钥生成 ②RSA加密解密 ③任意文件的读取④各环节必要的数据编码转换 ⑤图形操作界面。 内容来自论文无忧网 www.paper51.com 2.1.2 工程方案选择 内容来自www.paper51.com 综合考虑复用性、可维护性和执行效率，较妥当的方法是分层设计。核心的RSA算法由C++类库实现，针对用户所在的操作系统封装成本地化组件。其他各功能如文件操作、数据编码转换和图形界面等，由托管代码借助虚拟机平台标准库的功能快速开发实现(本文针对选用.Net上的C#论述，选用java由JNI或其他方式调用本地组件，设计模式上是完全类似的)。这种开发方式，核心功能集中在最底层，在不断的封装中针对具体环境对组件功能不断扩充，任意一个层面的封装都可以被直接应用到其他项目，比如在Web使用以前为某窗体程序写的组件、给嵌入式设备交叉编译算法库等。但是每一层都需要依赖底层的所有组件。图2-2形象的说明了分层设计给复用带来的好处。 copyright paper51.com 内容来自论文无忧网 www.paper51.com 图2-2 综合考虑复用性、可维护性和执行效率的分层设计 内容来自www.paper51.com 选用这种设计方案，上层使用C#，底层算法使用C++，可以由一个Visual Studio解决方案管理，给调试带来极大的方便。整个工程分四层，实现RSA加密算法的C++核心类库、封装C++核心类库的DLL组件、引用DLL的.Net类、实现文件操作功能的.Net窗体应用程序。2.2节详细介绍各部分的设计与开发。 paper51.com 考虑到工作量，本软件加解密数据没有严格遵从RSA标准PKCS #1，而是在满足设计要求的前提下，以一种尽可能简单的方式实现加密和解密。 paper51.com 2.2各部分的设计与开发 内容来自论文无忧网 www.paper51.com 2.2.1实现RSA加密算法的C++核心类库 http://www.paper51.com 1. 大数存储和四则运算 内容来自论文无忧网 www.paper51.com 根据RSA算法的要求，为了实现大数的各种复杂运算，需要首先实现大数存储和基本四则运算的功能。当今开源的大数运算C++类有很多，多用于数学分析、天文计算等，本文选用了一个流行的大数类型，并针对RSA算法和本项目的具体需要对其进行了扩充和改进。下面简单介绍大数存储和四则运算的实现原理。 paper51.com 最先完成的功能是大数的存储，存储功能由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对大数的管理。 copyright paper51.com 内容来自论文无忧网 www.paper51.com 图2-3 flex_unit对大数的管理 copyright paper51.com 在flex_unit的存储功能基础上，将其派生，得到vlong_value，在vlong_value中实现四则运算函数，并实现强制转换运算符unsigned，以方便大数类型和普通整数的互相赋值。当大数被强制转换为unsigned时，将取其最低四字节的值。四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。虽然实现了四则运算函数，但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我们另写一个类vlong，关联(Associate，即使用vlong_value类型的对象或其指针作为成员)vlong_value，在vlong重载运算符。这样，当我们操作vlong大数对象的时候，就可以像使用一个简单类型一样使用各种运算符号了。之所以将vlong_value的指针作为成员而不是直接构造的对象，也是为了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。 内容来自论文无忧网 www.paper51.com 2. 大数幂模与乘模运算•Montgomery幂模算法 内容来自www.paper51.com 在实现了vlong类型后，大数的存储和四则运算的功能都完成了。考虑到RSA算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个vlong的友元，完成幂模运算功能。幂模运算是RSA 算法中比重最大的计算，最直接地决定了RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质，先将幂模运算化简为乘模运算。 内容来自论文无忧网 www.paper51.com 通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求D=，E=15，可分解为如下6个乘模运算。 copyright paper51.com copyright paper51.com http://www.paper51.com 内容来自论文无忧网 www.paper51.com 内容来自www.paper51.com copyright paper51.com copyright paper51.com 归纳分析以上方法，对于任意指数E，可采用如图2-4的算法流程计算 。 内容来自www.paper51.com
http://www.paper51.com
图2-4 幂模运算分解为乘模运算的一种流程 paper51.com 按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。 paper51.com ① 求的值 内容来自论文无忧网 www.paper51.com 开始 D= 1 P= 2 mod 17 = 2 E= 15 paper51.com E奇数 D= DP mod n = 2 P= PP mod n = 4 E= (E-1)/2 =7 http://www.paper51.com E奇数 D= DP mod n = 8 P= PP mod n = 16 E=(E-1)/2 =3 内容来自www.paper51.com E奇数 D= DP mod n = 9 P= PP mod n = 1 E= (E-1)/2 =1 内容来自论文无忧网 www.paper51.com E奇数 D= DP mod n = 9 P= PP mod n = 1 E= (E-1)/2 =0 copyright paper51.com
最终D = 9 即为所求。 内容来自论文无忧网 www.paper51.com
② 求的值 内容来自www.paper51.com 开始 D = 1 P= 2 mod 13 = 2 E= 8 copyright paper51.com E偶数 D= 1 P= PP mod n = 4 E = E/2 =4 内容来自论文无忧网 www.paper51.com
E偶数 D= 1 P= PP mod n = 3 E = E/2 =2 paper51.com
E偶数 D= 1 P= PP mod n = 9 E = E/2 =1 paper51.com E奇数 D= DP mod n = 9 P= 不需要计算 E =(E-1)/2 =0 http://www.paper51.com 最终D = 9 即为所求。 paper51.com 观察上述算法，发现E根据奇偶除以二或减一除以二实际就是二进制的移位操作，所以要知道需要如何乘模变量，并不需要反复对E 进行除以二或减一除以二的操作，只需要验证E 的二进制各位是0 还是1 就可以了。同样是计算，下面给出从右到左扫描二进制位进行的幂模算法描述，设中间变量D,P,E的二进制各位下标从左到右为u,u-1,u-2,…,0。 内容来自www.paper51.com Powmod(C,E,n) 内容来自www.paper51.com { 内容来自论文无忧网 www.paper51.com D=1; copyright paper51.com P=C mod n; 内容来自论文无忧网 www.paper51.com
for i=0 to u do 内容来自论文无忧网 www.paper51.com
{ copyright paper51.com if(Ei=1)D=D*P(modn); 内容来自论文无忧网 www.paper51.com P=P*P(mod n); paper51.com
} paper51.com return D; http://www.paper51.com } paper51.com 有些文献将上述算法称为平方乘积二进制快速算法，例如参考文献中的《基于RSA算法的一种新的加密核设计》，其实这种算法本质上和图2-4的流程完全一致，只是把根据指数奇偶分开的减一和除以二合并成对指数二进制各位的判断而已。在本软件的代码中采用直接扫描vlong二进制各位的办法。 内容来自www.paper51.com
剩下的问题就是乘模运算了。提高乘模运算的速度是提高模幂运算速度的关键。一般情况下，n是数百位乃至千位以上的二进制整数，用普通的除法求模而进行乘模运算是不能满足速度的要求的。为此，Montgomery在1983年提出了一种模加右移的乘模算法（主要著作发表于1985年），从而避免了通常求模算法中费时的除法步骤。本软件仅仅是应用Montgomery(蒙哥马利)算法，算法的具体推导证明需要颇多数论知识，不在本文的讨论范围内，如需了解可参见蒙哥马利的相关著作。下面简单描述RSA中常用的Montgomery(蒙哥马利)算法供参考理解源程序。 内容来自www.paper51.com |