RSA加密算法(C实现)

RSA加密算法的编程实现 学号：0806580114 姓名：管睿

RSA算法是世界上第一个既能用于数据加密也能用于数字签名的非对称性加密算法。它易于理解和操作，所以流行甚广。算法的名字以发明者的名字命名，他们是：Ron Rivest，Adi Shamir 和Leonard Adleman。虽然RSA的安全性一直未能得到理论上的证实，但它经历了各种攻击，至今未被完全攻破。 在RSA算法中，先要获得两个不同的质数P和Q做为算法因子，再找出一个正整数E，使得E与 ( P - 1 ) * ( Q - 1 ) 的值互质，这个E就是私钥。找到一个整数D，使得( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立1[1]，D就是公钥1。设N为P和Q的乘积，N则为公钥2。加密时先将文转换为一个或一组小于N的整数I，并计算ID mod N的值M，M就密文。解密时将密文ME mod N，也就是M的E次方再除以N所得的余数就是明文。 因为私钥E与( P - 1 ) * ( Q - 1 )互质，而公钥D使( E * D ) mod ( ( P - 1 ) * ( Q - 1 ) ) = 1成立。破解者可以得到D和N，如果想要得到E，必须得出( P - 1 ) * ( Q - 1 )，因而必须先对N进行因数分解。如果N很大那么因数分解就会非常困难，所以要提高加密强度P和Q的数值大小起着决定性的因素。一般来讲当P和Q都大于2128时，按照目前的机算机处理速度破解基本已经不大可能了。 RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )式验证。具体操作时考虑到安全性和 m信息量较大等因素，一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。 由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。 */ #include #include #include using namespace std;//RSA算法所需参数 typedef struct RSA_PARAM_Tag { unsigned __int64 p, q; //两个素数，不参与加密解密运算 unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算 unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1 unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1 unsigned __int64 s; //块长，满足2^s<=n的最大的s，即log2(n)

} RSA_PARAM;//小素数表 const static long g_PrimeTable[]= {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 }; const static long g_PrimeCount=sizeof(g_PrimeTable) / sizeof(long);const unsigned __int64 multiplier=12747293821; const unsigned __int64 adder=1343545677842234541;//随机数类 class RandNumber{ private: unsigned __int64 randSeed; public: RandNumber(unsigned __int64 s=0); unsigned __int64 Random(unsigned __int64 n); }; RandNumber::RandNumber(unsigned __int64 s) { if(!s) { randSeed= (unsigned __int64)time(NULL); } else { randSeed=s; } } unsigned __int64 RandNumber::Random(unsigned __int64 n) { randSeed=multiplier * randSeed + adder; return randSeed % n; }static RandNumber g_Rnd;/* 模乘运算，返回值 x=a*b mod n */ inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n) { return a * b % n; } /* 模幂运算，返回值 x=base^pow mod n */ unsigned __int64 PowMod(unsigned __int64 &base, unsigned __int64 &pow, unsigned __int64 &n) { unsigned __int64 a=base, b=pow, c=1; while(b) { while(!(b & 1)) { b>>=1; //a=a * a % n; //函数看起来可以处理64位的整数，但由于这里a*a在a>=2^32时已经造成了溢出，因此实际处理范围没有64位 a=MulMod(a, a, n); } b--; //c=a * c % n; //这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。 c=MulMod(a, c, n); } return c; }/* Rabin-Miller素数测试，通过测试返回1，否则返回0。 n是待测素数。注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4 */ long RabinMillerKnl(unsigned __int64 &n) { unsigned __int64 b, m, j, v, i; m=n - 1; j=0; //0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数 while(!(m & 1)) { ++j; m>>=1; } //1、随机取一个b，2<=bb=2 + g_Rnd.Random(n - 3); //2、计算v=b^m mod n v=PowMod(b, m, n); //3、如果v==1，通过测试 if(v == 1) { return 1; } //4、令i=1 i=1; //5、如果v=n-1，通过测试 while(v != n - 1) { //6、如果i==l，非素数，结束 if(i == j) { return 0; } //7、v=v^2 mod n，i=i+1 v=PowMod(v, 2, n); ++i; //8、循环到5 } return 1; }/* Rabin-Miller素数测试，循环调用核心loop次 全部通过返回1，否则返回0 */ long RabinMiller(unsigned __int64 &n, long loop) { //先用小素数筛选一次，提高效率 for(long i=0; i < g_PrimeCount; i++) { if(n % g_PrimeTable[i] == 0) { return 0; } } //循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)^loop for(long i=0; i < loop; i++) { if(!RabinMillerKnl(n)) { return 0; } } return 1; }/* 随机生成一个bits位(二进制位)的素数，最多32位 */ unsigned __int64 RandomPrime(char bits) { unsigned __int64 base; do { base= (unsigned long)1 << (bits - 1); //保证最高位是1 base+=g_Rnd.Random(base); //再加上一个随机数 base|=1; //保证最低位是1，即保证是奇数 } while(!RabinMiller(base, 30)); //进行拉宾－米勒测试30次 return base; //全部通过认为是素数 }/*欧几里得法求最大公约数*/ unsigned __int64 EuclidGcd(unsigned __int64 &p, unsigned __int64 &q) { unsigned __int64 a=p > q ? p : q; unsigned __int64 b=p < q ? p : q;