rsa加密算法_源代碼_c__實(shí)現(xiàn)

1、unsigned _int64p, q;unsigned _int64f;unsigned _int64n, e;unsigned _int64d;unsigned _int64s; RSA_PARAM;/ 小素?cái)?shù)表RSA 算法#include <iostream>#include <stdlib>#include <time>using namespace std;/RSA 算法所需參數(shù) typedef struct RSA_PARAM_Tag/兩個(gè)素?cái)?shù)，不參與加密解密運(yùn)算/f=(p-1)*(q-1) ，不參與加密解密運(yùn)算/ 公匙， n=p*q ，gcd(

2、e,f)=1/私匙， e*d=1 (mod f) ， gcd(n,d)=1/塊長(zhǎng)，滿足2As<=n的最大的s,即Iog2(n)const static longg_PrimeTabIe=3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 ;unsignedconst static Iongg_PrimeCount=sizeof(g_PrimeTabIe) / sizeof(Iong);const_int64 muItipIier=12747293821;const un sig ned _in t64a

3、dder=1343545677842234541; 隨機(jī)數(shù)類cIassRandNumber/* */private:unsigned _int64randSeed;/* */public:RandNumber(unsigned _int64 s=0); unsigned _int64Random(unsigned _int64 n);/* */RandNumber:RandNumber(unsigned _int64 s)if(!s)randSeed= (unsigned _int64)time(NULL);else randSeed=s;/* */unsigned _int64 RandNu

4、mber:Random(unsigned _int64 n)randSeed=multiplier * randSeed + adder; return randSeed % n;static RandNumber g_Rnd;/* 模乘運(yùn)算，返回值 x=a*b mod n*/inline unsigned _int64 MulMod(unsigned _int64 a, unsigned _int64 b, unsigned _int64 n)return a * b % n;/*模幕運(yùn)算，返回值x=baseyow mod n*/unsigned _int64 PowMod(unsigned

5、 _int64 &base, unsigned _int64 &pow, unsigned _int64 &n)unsigned _int64a=base, b=pow, c=1;while(b)while(!(b & 1)b>>=1;/a=a * a % n;/函數(shù)看起來可以處理 64 位的整數(shù)，但由于這里a*a在a>=2A32時(shí)已經(jīng)造成了溢出，因此實(shí)際處理范圍沒有64位a=MulMod(a, a, n);/這里也會(huì)溢出，若把 64位整數(shù)拆為b-;/c=a * c % n;兩個(gè) 32 位整數(shù)不知是否可以解決這個(gè)問題。c=MulMod(a, c

6、, n); return c;/*Rabin-Miller 素?cái)?shù)測(cè)試，通過測(cè)試返回1，否則返回 0。n 是待測(cè)素?cái)?shù)。 注意：通過測(cè)試并不一定就是素?cái)?shù)，非素?cái)?shù)通過測(cè)試的概率是 1/4 */long RabinMillerKnl(unsigned _int64 &n)unsigned _int64b, m, j, v, i;j 是非負(fù)整數(shù)m=n - 1;j=0;0、先計(jì)算出 m、j，使得n-仁m*2j，其中m是正奇數(shù),while(!(m & 1)+j;m>>=1;/1 、隨機(jī)取一個(gè) b， 2<=b<n-1b=2 + g_Rnd.Random(n - 3);2

7、、計(jì)算 v=bAm mod nv=PowMod(b, m, n);/3、如果 v=1 ，通過測(cè)試if(v = 1)return 1; /4 、令 i=1i=1;/5、如果 v=n-1 ，通過測(cè)試while(v != n - 1)/6、如果 i=l ，非素?cái)?shù)，結(jié)束if(i = j)return 0;/7、 v=vA2 mod n ， i=i+1v=PowMod(v, 2, n);+i; /8 、循環(huán)到 5 return 1;/*Rabin-Miller 素?cái)?shù)測(cè)試，循環(huán)調(diào)用核心 loop 次 全部通過返回 1 ，否則返回 0*/long RabinMiller(unsigned _int64 &a

8、mp;n, long loop)/先用小素?cái)?shù)篩選一次，提高效率 for(long i=0; i < g_PrimeCount; i+) if(n % g_PrimeTablei = 0)return 0;(1/4Floop / 循環(huán)調(diào)用 Rabin-Miller 測(cè)試 loop 次，使得非素?cái)?shù)通過測(cè)試的概率降為 for(long i=0; i < loop; i+)if(!RabinMillerKnl(n)return 0; return 1;/*隨機(jī)生成一個(gè) bits 位(二進(jìn)制位 )的素?cái)?shù)，最多 32 位*/unsigned _int64 RandomPrime(char bi

9、ts)unsigned _int64base;dobase= (unsigned long)1 << (bits - 1);/保證最高位是 1base+=g_Rnd.Random(base);/ 再加上一個(gè)隨機(jī)數(shù)base|=1; / 保證最低位是 1，即保證是奇數(shù) while(!RabinMiller(base, 30);/ 進(jìn)行拉賓米勒測(cè)試 30 次return base; /全部通過認(rèn)為是素?cái)?shù)/*歐幾里得法求最大公約數(shù)*/unsigned _int64 EuclidGcd(unsigned _int64 &p, unsigned _int64 &q)unsign

10、ed _int64 unsigned _int64 unsigned _int64 if(p = q)a=p > q ? p : q; b=p < q ? p : q; t;return p; /兩數(shù)相等，最大公約數(shù)就是本身elsewhile(b)/ 輾轉(zhuǎn)相除法， gcd(a,b)=gcd(b,a-qb)a=a % b; t=a; a=b;b=t;return a;/*Stein 法求最大公約數(shù)*/ unsigned _int64 SteinGcd(unsigned _int64 &p, unsigned _int64 &q) a=p > q ? p : q;

11、 b=p < q ? p : q; t, r=1;unsigned _int64unsigned _int64unsigned _int64 if(p = q)return p;/兩數(shù)相等，最大公約數(shù)就是本身 elsewhile(!(a & 1) && (!(b & 1) r<<=1;a>>=1;b>>=1;if(!(a & 1)/a、b 均為偶數(shù)時(shí)， gcd(a,b)=2*gcd(a/2,b/2)t=a;a=b;b=t;do/如果 a 為偶數(shù)，交換 a，while(!(b & 1)b>>=1

12、;/b 為偶數(shù), a 為奇數(shù)時(shí), if(b < a)gcd(b,a)=gcd(b/2,a)t=a; a=b;b=t;如果b小于a,交換a, while(b); return r * a;b=(b - a) >> 1; /b 、 a 都是奇數(shù), gcd(b,a)=gcd(b-a)/2,a)/* 已知 a、 相當(dāng)于求解 a*x-b*y=1 的最小整數(shù)解b,求x，滿足a*x =1 (mod b)*/unsigned _int64 Euclid(unsigned _int64 &a, unsigned _int64 &b) unsigned _int64m, e, i

13、, 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;elsey-=x;yy=0;elsey+=x;xx=1 - xx;yy=1 - yy; x=j; if(xx = 0)x=b - x; return x;/* 隨機(jī)產(chǎn)生一個(gè) RSA 加密參數(shù)*/RSA_PARAM RsaGetParam(void)RSA_PARAM Rsa= 0 ; unsigned _int64t;Rsa.p=RandomPrime(16

14、);/ 隨機(jī)生成兩個(gè)素?cái)?shù)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);小于 2A16, 65536=2X6Rsa.e|=1;/保證最低位是1,即保證是奇數(shù)，因f 一定是偶數(shù),要互素，只能是奇數(shù) 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>&g

15、t;=1; return Rsa;/* 拉賓米勒測(cè)試*/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 <<

16、endl;/*RSA 加密解密*/void TestRSA(void)RSA_PARAMr;charpSrc="abcdefghijklmnopqrstuvwxyz"const unsigned long n=sizeof(pSrc);unsigned char*q, pDecn;unsigned _int64pEncn;r=RsaGetParam();cout << "p=" << r.p << endl;cout << "q=" << r.q << endl;

17、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); cout << hex << pEnci << "