rsa文件加密软件的设计与实现毕业设计论文(编辑修改稿)

rsa文件加密软件的设计与实现毕业设计论文(编辑修改稿)内容摘要：

，而是在满足设计要求的前提下，以一种尽可能简单的方式实现加密和解密。 各部分的设计与开发 实现 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 的实例中被存入比当前存储的数更小的数青岛 大学本科生毕业论文（设计） 9 时，存储空间并不会自动紧缩，这是为了在运算的时候提高执行效率。 结合指针 a，有两个重要的无符号整数来控制存储， unsigned z 和 unsigned n， z 是被分配空间的单元数，随数字变大不断增大，不会自己紧缩，而 n 是当前存储的大数所占的单元数，组成一个大数的各 unsigned 单元的存入和读出由 set、 get方法完成，变量 n是只读的。 类型 unsigned在 32 位机是 32 位的，所以对于 flex_unit 这个大数类来说，每个大数最大可以达到 个字节长，这已经超过了 32 位机通常的最大内存容量，所以是足够进行 RSA 所需要的各种运算的。 图 23 形象的说明了大数存储类 flex_unit 对大数的管理。 图 23 flex_unit 对大数的管理 在 flex_unit 的存储功能基础上，将其派生，得到 vlong_value，在 vlong_value 中实现四则运算函数，并实现强制转换运算符 unsigned，以方便大数类型和普通整数的互相赋值。 当大数被强制转换为 unsigned 时，将取其最低四字节的值。 四则运算实现的原理十分简单，都是按最基本的算术原理实现的，四则运算过程的本质就是按一定数制对数字的计算，比如相加，就是低位单元对齐，逐单元相加并进位，减法同理。 而乘除法和取余也都是按照竖式运算的原理实现，并进行了必要的优化。 虽然实现了四则运算函数，但是若是程序里的运算都要调用函数，显得烦琐而且看起来不美观，所以我们另写一个类 vlong，关联 (Associate，即使用 vlong_value 类型的对象或其指针 作为成员 )vlong_value，在 vlong 重载运算符。 这样，当我们操作 vlong 大数对象的时候，就可以像使用一个简单类型一样使用各种运算符号了。 之所以将 vlong_value 的指针作为成员而不是直接构造的对象，也是为了提高执行效率，因为大型对象的拷贝要消耗不少机器时间。 2. 大数幂模与乘模运算 •Montgomery 幂模算法 在实现了 vlong 类型后，大数的存储和四则运算的功能都完成了。 考虑到 RSA 算法需要进行幂模运算，需要准备实现这些运算的方法。 所以写一个 vlong 的友元，完成幂模运算功能。 幂模运算是 RSA 算法中比重最大的计算，最直接地决定了 RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出 了很多的解决方案。 经查阅相关数学著作，发现通常都是依据乘模的性质 nnbnanba m o d))m o d()m o d((m o d)(  ，先将幂模运算化简为乘模运算。 *a unsigned 类型的指针 大数占 n 个单元 开辟了 z 个单元大的内存 内存空间 青岛 大学本科生毕业论文（设计） 10 通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求 D= nCE mod ， E=15， 可分解为如下 6 个乘模运算。 nCnCCC m o dm o d 21  nCnCCC m o dm o d 312  nCnCCC m o dm o d 6223  nCnCCC m o dm o d 734  nCnCCC m o dm o d 14445  nCnCCC modmod 1556  归纳分析以上方法，对于任意指数 E，可采用如图 24 的算法流程计算。 青岛 大学本科生毕业论文（设计） 11 图 24 幂模运算分解为乘模运算的一种流程 按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。 ① 求 17mod215 的值 开始 D = 1 P = 2 mod 17 = 2 E = 15 E 奇数 D = DP mod n = 2 P = PP mod n = 4 E = (E1)/2 =7 E 奇数 D = DP mod n = 8 P = PP mod n = 16 E = (E1)/2 =3 开始 D=1。 P=C mod n E0? E 为奇数 ? nPDD m od)(  E=E1 nPPP m od)(  E 为偶数 ? E=E/2 Yes No Result=D 结束 Yes Yes No No 青岛 大学本科生毕业论文（设计） 12 E 奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E1)/2 =1 E 奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E1)/2 =0 最终 D = 9 即为所求。 ② 求 13mod28 的值 开始 D = 1 P = 2 mod 17 = 2 E = 8 E 偶数 D = 1 P = PP mod n = 4 E = E/2 =4 E 偶数 D = 1 P = PP mod n = 3 E = E/2 =2 E 偶数 D = 1 P = PP mod n = 9 E = E/2 =1 E 奇数 D = DP mod n = 9 P = 不需要计算 E = (E1)/2 =0 最终 D = 9 即为所求。 观察上述算法，发现 E 根据奇偶除以二或减一除以二实际就是二进制的移位操作，所以要知道需要如何乘模变量，并不需要反复对 E 进行除以二或减一除以二的操作，只需要验证 E 的二进制各位是 0 还是 1 就可以了。 同样是计算 nCD E mod ，下面给出从右到左扫描二进制位进行的幂模算法描述，设中间变量 D,P,E 的二进制各位下标从左到右为 u,u1,u2,…,0。 Powmod(C,E,n) { D=1。 P=C mod n。 for i=0 to u do { if(Ei=1)D=D*P(mod n)。 P=P*P(mod n)。 } return D。 } 有些文献将上述算法称为平方乘积二进制快速算法，例如参考文献中的《基于 RSA算法的一种新的加密核设计》，其实这种算法本质上和图 24 的流程完全一致，只是把根据指数奇偶分开的减一和除以二合并成对指数二进制各 位的判断而已。 在本软件的代码中采用直接扫描 vlong 二进制各位的办法。 剩下的问题就是乘模运算了。 提高乘模运算的速度是提高模幂运算速度的关键。 一般情况下， n 是数百位乃至千位以上的二进制整数，用普通的除法求模而进行乘模运算是不能满足速度的要求的。 为此， Montgomery 在 1983 年提出了一种模加右移的乘模算法 （主要著作发表于 1985 年） ，从而避免了通常求模算法中费时的除法步骤。 本软件仅仅是应用 Montgomery(蒙哥马利 )算法，算法的具体推导证明需要颇多数论知识，不在本青岛 大学本科生毕业论文（设计） 13 文的讨论范围内，如需了解可参见蒙哥马 利的相关著作。 下面简单描述 RSA 中常用的Montgomery(蒙哥马利 )算法供参考理解源程序。 选择与模数 n 互素的基数 R=2k， n 满足 2k－ 1≤ n2k， n 应 为奇数。 并且选择 R1及n’，满足 0 R1n, 0 n’n,使得 RR1nn’＝ 1。 对于 0≤ mRn 的任意整数 ,Montgomery给出求模乘法 mR1 mod n 的快速算法 M(m): M(m) { Rnmt RRnRm /)( 0。 m o d39。 )m o d(     if (t≥ n) return (tn)。 else return t。 } 因为 Rmmnnn m o d39。  ，故 t 为整数；同时 nmtR mod ，得 nmRt mod1。 由于 RnRnnm  0 ， M(m) 中 t 结果范围是 0≤ t2n，返回时如果 t 不小于 n，应返回 tn。 本软件程序中， RSA 核心运算使用的乘模算法就是 M(A*B)。 虽然 M(A*B)并不是乘模所需要的真正结果，但只要在幂模算法中进行相应的修改，就可以调用这个乘模算法进行计算了。 本软件起初未使用 Montgomery 乘模算法时 ，加密速度比使用Montgomery 乘模算法慢，但速度相差不到一个数量级。 将上述乘模算法结合前面叙述的幂模算法，构成标准 Montgomery 幂模算法，即本软件所使用的流程，叙述如下。 M(m) { k = ( m * n’ ) mod R。 x = (m + k*n ) / R。 if (x=n) x = n。 return x。 } exp(C,E,n) { D=Rn。 P=C*R mod n。 i=0。 while(true) { if(E 的当前二进制位 Ei==1)D=M(D*P)。 //从低位到高位检测二进制位 青岛 大学本科生毕业论文（设计） 14 i+=1。 if(i==E 的二进制位数 )break。 P=M(P*P)。 } return D*R1 (mod n)。 } 在具体的实现中，对应 monty 类的 mul 和 exp 方法。 全局函数 modexp 初始化 monty对象并调用其 exp 方法，使用的时候直接调用 modexp 即可。 3. 寻找素数 •Eratosthenes 筛 选与 Fermat 素数测试 首先要说明的是，事实上，当今的计算机还不足以聪明到立刻计算生成一个很大的随机素数。 一般来说，要得到 100%准确的大素数，都是通过查已经计算好的素数表的方式。 但是素数表的方式给 RSA 的安全性带来隐患，因为攻击者如果得到了密钥生成时所使用的素数表，攻破 RSA 加密的难度将会大大降低。 本程序起初使用素数表的方式，后来考虑到安全性问题，生成密钥的方式改为随机计算生成。 这样，短时间内如果要得到一个 100%准确的大素数是很困难的，只能以尽可能高的概率得到一个大素数。 经过 和 小节，所有的大数运算功能都准备完毕，在此基础上，本工程将寻找素数的功能置于类 Prime_factory_san 之中。 外部只要调用本类实例的成员 vlong find_prime( vlong amp。 start )就可以以大数 start 为起点，得到一个数，这个数是素数的概率很大。 下面介绍寻找素数的原理。 首先在需要寻找素数的整数范围内对整数进行筛选，把所有确知为合数的整数排除出去。 程序中构造了一个数组 b[]，大小为一轮素数搜索的范围，记搜索范围大小为 SS。 b[0]到 b[SS]分别对应大数 start 到 start+SS。 b[]中所有元素先初始化为 1，如果对应的大数确定为合数，就将 b[]中对应的元素置为 0。 最后，只需对那些 b[]中为 1 的元素对应的大数进行比较确切的素数测试即可，只要被测试的数是素数概率达到一定门限，就判这个数为素数。 这样做既保证了这段程序可以在短时间内执行完，又保证了可以以比较高的准确度得到素数。 函数 find_prime 先把 b[]的所有元素赋值为 1，然后按参数 start 给标记数组 b[]的各元素赋 0 值。 下面描述标记数组 b[]的赋 0 值算法。 首先，在类 Prime_factory_san 被构造的时候，构造 函数中从 2 开始搜寻一些小素数，记录在数组 pl[]中，共记录 NP 个。 这些小素数用来当作因子，他们的倍数将被从大素数搜索范围内剔除 (即把数组 b[]的对应元素标记为 0)，剔除的程序。