C++RSA算法文件加密解决方案RSA论文 第6页
{
b[r] = 0;
r += p;
}
}
这里利用start对各小素数因子p求模的办法，得到当前p在素数搜索范围内的最小倍数在b[]中的对应位置，将其剔除后，不断后移p个位置，将这个小素数因子p在搜索范围内的所有倍数全部剔除，如图2-5所示。在完成对所有小素数因子的类似操作后，他们的倍数在搜索范围内的位置标记b[r]被全部标记为0。实际上这就是Eratosthenes筛选法。
图2-5 在素数搜索范围内剔除小素数因子p的倍数
接下来，对可能为素数的数(即标记数组b[]中值为1的元素对应的数)进行素数测试。数论学家利用费马小定理研究出了多种素数测试方法，本程序使用一种最简单的方式，直接应用费马小定理。取一个与p互素的整数A，对于大素数p来说应该满足Ap-1mod p=1，但是我们把p代入一个大整数，满足这个关系的数不一定是素数。这时我们改变A，进行多次测试，如果多次测试都通过，这个数是素数的概率就比较大。按这种原理，我们编写素数测试函数如下。
int is_probable_prime_san( const vlong &p )
{
const rep = 4; //测试次数
const unsigned any[rep] = { 2,3,5,7 }; //测试用的底数
for ( unsigned i=0; i<rep; i+=1 )
if ( modexp( any[i], p-vlong(1), p ) != vlong(1) ) return 0;
//modexp是幂模函数，按上一小节叙述的算法编码。
//这里modexp计算any[i]p-1mod p。
return 1;
}
测试通过，程序就判定这个数为找到的素数，将找到的素数返回给上层程序使用。在这里其实有一个不可忽视的问题，就是得到一个测试通过的合数。对于这种情况，RSA算法加密解密是否还可以实现，是一个需要从数学角度论证的问题。因为得到素数的概率很高，经过一整天的生成密钥和加密操作，没有发现失败的密钥， 所以本文暂没有对这个问题进行讨论。
综上所述，总结素数寻找的流程，如图2-6所示。
图2-6 函数find_prime寻找素数的流程框图
得到了大素数，即RSA算法中的p、q，我们就可以计算出密钥，进行加密等操作了。
4. 二元一次不定方程
在RSA 算法中，往往要在已知A、M的情况下，求B的最小值，使得 (AB) mod M = 1。即相当于求解B、N都是未知数的二元一次不定方程 AB-MN=1的最小整数解。
而针对不定方程ax-by=1 的最小整数解，古今中外都进行过详尽的研究，西方有著名的欧几里德算法，即一种辗转相除法，中国有秦九韶的“大衍求一术”。欧几里德算法是一种递归算法，较容易理解。下面举例说明用欧几里德算法求解二元一次不定方程的最小整数解。
给定不定方程11x-49y=1，求最小的x
（1） 11 x - 49 y = 1 49 mod 11 = 5
（2） 11 x - 5 y = 1 11 mod 5 = 1
（3） x - 5 y = 1 5 mod 1 = 0
逆向代入：
令y=0 代入（3）得x=1
令x=1 代入（2）得y=2
令y=2 代入（1）得x=9
x=9;y=2即为所求。
程序中，全局函数vlong modinv( const vlong &a, const vlong &m )用来完成这种算法。对应前面的叙述，参数a对应A，参数m对应M，函数返回值即为B的最小值。
5. 按常规RSA算法实现加密与解密
最后，类RSA_san基于前面的准备工作，实现RSA密钥生成和加解密的功能(算法在此不再赘述，RSA算法协议见
http://www.di-mgt.com.au/rsa_alg.html)。为了方便阅读，整个类的源程序中，所使用的变量字母均和RSA算法协议中一致。在类RSA_san的构造函数里，执行准备一对随机密钥的操作。之后可以直接使用类的其他成员进行RSA加解密操作，也可以载入以前保存的密钥或再次随机生成密钥。类中各成员频繁的用到字符串和vlong类型的转换，因为大数是用字符串置入的，而把大数读出，也是保存在字符指针指向的一段内存空间里，所以也是字符串。所以，需要实现一系列的编码转换函数，比如将unsigned指针指向的一段空间里保存的一个大数，表示成十辣进制形式的字符串文本。编码转换通常是用C风格的指针操作和sprintf函数来完成。
需要加密和解密的数据也是通过字符串参数置入的。由于字符串的结尾字符“\0”实际上也可能是需要加密的数据，所以置入的串长度并不能以“\0”来决定，程序里引入一个unsigned类型的参数来决定置入的串长度，这样就解决了加密连0数据时候被截断的问题。
因为是对文件加密的软件，需要加密的数据通常并不止几字节，这时由上层程序将数据按用户的设置分块，分别加密或解密。本软件默认的分块大小是1字节，即逐个字节作为参数，调用C++核心模块中的方法。
加密解密流程均为标准RSA算法，具体过程和使用方法参见源程序和接口文档。
6. 核心类库综述
综上几小节所述，实现RSA加密算法的C++核心类库由辣个类组成，类名和对应的功能描述总结如表2-1所示。各个类之间的关系如图2-7所示。
表2-1 RSA加密算法的C++类库中的类
class flex_unit 大数运算和存储最基本的类，主要实现超大整数的存储和索引管理。
class vlong_value 是flex_unit的派生类，在灵活大数存储的基础上实现四则运算函数。
class vlong 以vlong_value为基础(将一个vlong_value指针作成员)，重载运算符。
class monty 为RSA准备大数求幂模运算的函数，vlong的友元。
class Prime_factory_san 素数工厂，寻找大素数的类。
class RSA_san 在前5个类的基础上，实现RSA核心算法的类。
图2-7 C++核心功能类图
另外需要说明的是，程序中有几个不属于任何类的全局函数，比如应用辗转相除法求最大公约数的函数gcd、解同余方程的函数modinv等。按常规设计模式来说，不应当出现类之外的函数，但是因为这些函数使用频繁，考虑到机器效率，直接置于全局，不再另行包装。
2.2.2 封装C++核心类库的DLL组件
在Visual Studio当前的解决方案中以VC++创建一个win32dll工程，将测试好的实现RSA加密算法的C++核心类库中的所有文件加入到此工程下，新建一对cpp和h文件，把可能用到的功能全部规划为新文件中的全局函数，并以C接口导出，即__declspec(dllexport)。由于核心类库的对外功能都使由RSA_san类提供的，所以在新cpp文件中全局的声明一个RSA_san类的对象指针(RSA_san *WRSA)，全局函数int start_RSA_san()初始化*WRSA对象，在初始化成功后，其他全局函数通过调用*WRSA对象的公开方法实现各种功能，如加密、读取密钥等。在关闭上层引用程序以前，应执行int finish_RSA_san()来释放WRSA，该函数执行delete WRSA的操作。其他接口函数的使用见DLL接口文档。
另外，DLL组件可以自己在全局函数中实现一些其他功能，作为对核心类库功能的补充。C接口的DLL组件可以被诸如VB、Delphi等开发环境方便的引用。
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>
C++RSA算法文件加密解决方案RSA论文 第6页下载如图片无法显示或论文不完整，请联系qq752018766
