rsa 算法原理 C C. 大数的运算 1. 大数的运算原理 RSA 算法依赖于大数的运算，目前主流RSA 算法都建立在512 位到1024 位的大数运算之上，所以我们首先需要掌握大数（比如1024 位）的运算原理。 大多数的编译器只能支持到32 位（或 64 位）的整数运算，即我们在运算中所使用的整数必须小于等于32 位，即 0x FFFFFFFF，这远远达不到RSA 的需要，于是需要专门建立大数运算库，来解决这一问题。 最简单的办法是将大数当作字符串进行处理，也就是将大数用 10 进制字符数组进行表示，然后模拟人们手工进行“竖式计算”的过程编写其加减乘除函数。但是这样做效率很低。当然其优点是算法符合人们的日常习惯，易于理解。 另一种思路是将大数当作一个二进制流进行处理，使用各种移位和逻辑操作来进行加减乘除运算，但是这样做代码设计非常复杂，可读性很低，难以理解也难以调试。 这里我们采用了一种介于两者之间的思路：将大数看作一个 N 进制数组，对于目前的32 位系统而言，N 可以取 2 的32 次方，即 0x 100000000，假如将一个 1024 位的大数转化成 0x 10000000 进制，它就变成了 32 位，而每一位的取值范围是 0－0x FFFFFFFF。我们正好可以用一个无符号长整数来表示这一数值。所以1024 位的大数就是一个有 32个元素的u nsigned long 数组。而且 0x 100000000 进制的数组排列与 2 进制流对于计算机来说，实际上是一回事，但是我们完全可以针对 u nsigned long 数组进行“竖式计算”，而循环规模被降低到了 32 次之内，并且算法很容易理解。 但考虑到乘法和除法，都要进行扩展才能进行快速的计算（如果把除法变减法而不扩展，速度将慢的无法忍受）。所以我们将 N 取 2 的16 次方的，即 0x FFFF。每一位用u nsigned short 来表示，当进行乘除运算时，将 short 扩展成 long，这是编译器所支持的，所以运算起来，比较快。 2. 大数的各种运算 这些运算都是常见的，同时也是常用的。要实现RSA 算法，就必须先实现大数的这些运算。 1) 大数的比较。两个无符号或有符号的大数进行大小比较。大数和一般整数进行比较。大于，等于，小于，返回值各异，以区别比较结果。 2) 大数的赋值。将一个大数的值，符号等，逐位赋给另一个大数。将一般整数的值，符号等赋给一个大数。 3) 大数的加法。两个大数从低位到高位逐位相加，要考虑到进位的问题。或大数与一般整数的相加。 4) 大...
VIP
