RSA.zip

 #include <iostream> #include<math.h> using namespace std; typedef long long LL; //编写一个模长为32比特的RSA加解密算法即寻找两个16比特的素 //数，e = 5为公钥，计算相应的私钥，对消息abc(ASCII码表示)用基 //本的RSA算法加密，并进行解密验证 //****************************素数检验算法begin********************************* LL mulmod(LL a, LL b, LL p) { LL d = 1; a = a % p; while (b > 0) { if (b & 1) d = (d * a) % p; a = (a * a) % p; b >>= 1; } return d; } bool witness(LL a, LL n) { LL d = n - 1; if (n == 2) return true; if (!(n & 1)) return false; while (!(d & 1)) d = d / 2; LL t = mulmod(a, d, n); while ((d != n - 1) && (t != 1) && (t != n - 1)) { t = mulmod(t, 2, n); d = d << 1; } return (t == n - 1) || (d & 1); } bool isprime(LL n)//米勒拉宾算法——素性测试 { int a[3] = { 2,7,61 }; for (int i = 0; i < 3; i++) if (!witness(a[i], n)) return false; return true; } //*******************************素数检验算法end******************************* //快速指数算法 // a^k=b(mod m) LL FastExp(LL a, LL k, LL n) { LL b = 1; while (k >= 1) { if (k % 2) b = (a * b) % n; a = (a * a) % n; k /= 2; } return b; } int main() { LL p, q; LL i = 62213; while (1) { if (isprime(i)) { p = i; cout << "p=" << i << endl; break; } i++; }//产生p,p>60000 i = 51234; while (1) { if (isprime(i)) { q = i; cout << "q=" << i << endl; break; } i++; }//产生q,q>50000.所以p,q都16位,n有32位 LL n = p * q; cout << "n=" << n << endl; LL fn = (p - 1) * (q - 1); cout << "φ(n)=" << fn << endl; LL e = 5; cout << "e=" << e << endl; LL d = fn / e; while (1) { if ((d * e) % fn == 1) { cout << "e*dmodφ(n)=1; 私钥d=" << d << endl; break; } d++; }//寻找结果为2550094765，过程时间较长约为10s,若在此不再测试请执行下面的代码 /*d = 2550094765; cout << "e*dmodφ(n)=1; 私钥d=" << d << endl;*/ //以{e,n}为公开钥,{d,p,q}为秘密钥 //abc ASCII转化结果为979899 LL m = 979899; cout << "message=" << m << endl; LL c = FastExp(m,e,n); cout << "加密结果c=" << c << endl; //LL k = (((m * m) % n) * ((m * m) % n) * m在这里×m以后就会越界，只能用快速幂) % n; m = FastExp(c, d, n); cout << "解密结果m=" << m << endl; return 0; }