RSA加密算法_源代码__C语言实现.doc

RSA算法 1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。 RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 密钥对的产生。选择两个大素数，p 和q 。计算：n = p * q 然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 )互质。最后，利用Euclid 算法计算解密密钥d, 满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,., mi ，块长s，其中 2s = n, s 尽可能的大。对应的密文是：ci = mie ( mod n ) ( a ) 解密时作如下计算：mi = cid ( mod n ) ( b ) 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; /块长，满足2s=1; /a=a * a % n; /函数看起来可以处理64位的整数，但由于这里a*a在a=232时已经造成了溢出，因此实际处理范围没有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*2j，其中m是正奇数，j是非负整数 while(!(m & 1) +j; m=1; /1、随机取一个b，2=bn-1 b=2 + g_Rnd.Random(n - 3); /2、计算v=bm 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=v2 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_PrimeTablei = 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 q ? p : q; unsigned _int64 b=p q ? p : q; unsigned _int64 b=p q ? p : q; unsigned _int64 t, r=1; if(p = q) return p; /两数相等，最大公约数就是本身 else while(!(a & 1) & (!(b & 1) r=1; b=1; if(!(a & 1) t=a; /如果a为偶数，交换a，b a=b; b=t; do while(!(b & 1) b=1; /b为偶数，a为奇数时，gcd(b,a)=gcd(b/2,a) if(b 1; /b、a都是奇数，gcd(b,a)=gcd(b-a)/2,a) while(b); return r * a; /*已知a、b，求x，满足a*x =1 (mod b)相当于求解a*x-b*y=1的最小整数解*/unsigned _int64 Euclid(unsigned _int64 &a, unsigned _int64 &b) unsigned _int64 m, e, i, j, x, y; long xx, yy; m=b; e=a; x=0; y=1; xx=1; yy=1; while(e) i=m / e; j=m % e; m=e; e=j; j=y; y*=i; if(xx = yy) if(x y) y=x - y; else y-=x; yy=0; else y+=x; xx=1 - xx; yy=1 - yy; x=j; if(xx = 0) x=b - x; return x;/*随机产生一个RSA加密参数*/RSA_PARAM RsaGetParam(void) RSA_PARAM Rsa= 0 ; unsigned _int64 t; Rsa.p=RandomPrime(16); /随机生成两个素数 Rsa.q=RandomPrime(16); Rsa.n=Rsa.p * Rsa.q; Rsa.f=(Rsa.p - 1) * (Rsa.q - 1); do Rsa.e=g_Rnd.Random(65536); /小于216，65536=216 Rsa.e|=1; /保证最低位是1，即保证是奇数，因f一定是偶数，要互素，只能是奇数 while(SteinGcd(Rsa.e, Rsa.f) != 1); Rsa.d=Euclid(Rsa.e, Rsa.f); Rsa.s=0; t=Rsa.n 1; while(t) Rsa.s+; /s=log2(n) t=1; return Rsa;/*拉宾米勒测试*/void TestRM(void) unsigned long k=0; cout - Rabin-Miller prime check.n endl; for(unsigned _int64 i=4197900001; i 4198000000; i+=2) if(RabinMiller(i, 30) k+; cout i endl; cout Total: k endl;/*RSA加密解密*/void TestRSA(void) RSA_PARAM r; char pSrc=abcdefghijklmnopqrstuvwxyz; const unsigned long n=sizeof(pSrc); unsigned char *q, pDecn; unsigned _int64 pEncn; r=RsaGetParam(); cout p= r.p endl; cout q= r.q endl; cout f=(p-1)*(q-1)= r.f endl; cout n=p*q= r.n endl; cout e= r.e endl; cout d= r.d endl; cout s= r.s endl; cout Source: pSrc endl; q= (unsigned char *)pSrc; cout Encode:; for(unsigned long i=0; i n; i+) pEnci=PowMod(qi, r.e, r.n); co