.....
word 格式 .整理版
一、 设计原理（算法工作原理）
RSA 原理：
RSA 密钥的选取和加解密过程都非常简洁，在算法上主要要实现四个问题：
1、如何处理大数运算
2、如何求解同余方程 XY % M = 1
3、如何快速进行模幂运算
4、如何获取大素数
( 一) 大数存储
RSA 依赖大数运算， 目前主流 RSA 算法都建立在 1024 位的大数运算之上。
而大多数的编译器只能支持到 64 位的整数运算，即我们在运算中所使用的整数
必须小于等于 64 位，即：0xffffffffffffffff ，也就是 18446744073709551615，
这远远达不到 RSA 的需要，于是需要专门建立大数运算库来解决这一问题。
一个有效的改进方法是将大数表示为一个 n 进制数组，对于目前的 32 位
系统而言 n 可以取值为 2 的 32 次方，即 0x100000000，假如将一个二进制为
1024 位的大数转化成 0x10000000进制，就变成了 32 位，而每一位的取值范围
不再是二进制的 0—1 或十进制的 0—9，而是 0-0xffffffff ，我们正好可以用一
个 32 位的 DWORD （如：无符号长整数， unsigned long ） 类型来表示该值。所
以 1024 位的大数就变成一个含有 32 个元素的 DWORD数组，而针对 DWORD数组
进行各种运算所需的循环规模至多 32 次而已。而且 0x100000000 进制与二进制，
对于计算机来说，几乎是一回事，转换非常容易。
例如：大数 18446744073709551615，等于 0xffffffff ffffffff ，就相当
于十进制的 99：有两位，每位都是 0xffffffff 。而 18446744073709551616等于
0x00000001；00000000 00000000，就相当于十进制的 100：有三位，第一位是 1 ，
其它两位都是 0 ，如此等等。在实际应用中，“数字数组”的排列顺序采用低
位在前高位在后的方式，这样，大数 A 就可以方便地用数学表达式来表示其值：
A=Sum[i=0 to n](A*r**i) ，r=0x100000000，0<=A<r其中 Sum 表示求和， A表
示用以记录 A 的数组的第 i 个元素， ** 表示乘方。任何整数运算最终都能分解
成数字与数字之间的运算，在 0x100000000 进制下其“数字”最大达到
0xffffffff ，其数字与数字之间的运算，结果也必然超出了目前 32 位系统的字
长。在 VC++中，存在一个 __int64 类型可以处理 64 位的整数，所以不用担心这
一问题。
( 二) 加减乘除
设有大数 A、B 和 C，其中 A>=B：
A=Sum[i=0 to p](A*r**i)
B=Sum[i=0 to q](B*r**i)
C=Sum[i=0 to n](C*r**i)
r=0x100000000，0<=A,B,C<r，p>=q
则当 C=A+B、C=A-B、C=A*B时，我们都可以通过计算出 C来获得 C：C=A+B，显
然 C不总是等于 A+B，因为 A+B可能 >0xffffffff ，而 C必须 <=0xffffffff ，这
时就需要进位，当然在计算 C[i-1] 时也可能产生了进位，所以计算 C时还要加
上上次的进位值。如果用一个 64位变量 result 来记录和，另一个 32位变量 carry
来记录进位，则有：
carry=0
VIP享7折，此内容立减4.47元 
评论0