使用C++实现RSA加密解密

一，RSA简介。

RSA，一种非对称加密方式。是目前为止最有影响力的加密算法之一，而且是第一个同时应用于加密和数字签名的算法。

其原理为：两个大素数相乘容易，但是若想将两个大素数相乘的积再分解为两个原始的素数很难。安全性依赖于大数因式分解的困难性。

使用公钥加密，私钥解密。

二，主要原理。

1，公钥私钥的制作过程：

1，选择两个足够大，且互质的素数，p和q。

2，计算出p，q的积，n。

3，计算出n的欧拉函数n1=(p-1)*(q-1).

4，选取公钥e：选择一个与n1互质的质数，不为n1因子且1<e<n1。

5，计算私钥d：d*e mod n1=1(就是e对于n1的模逆元素)。

得到公钥KN(e,n)，私钥KR(d,n).

2，加密解密。

设明文为：M；密文为C。

加密：M^e mod n=C。

解密：C^d mod n=M。

三，简单测试。

加密解密

根据第二步中的步骤，我们可以进行一项简单测试。

1，假设p=3,q=11。

2，n为33。

3，n的欧拉函数n1=20。

4，选取公钥：e=3。

5，计算私钥：d*3%20=1,d=7。

得到了公钥KN：（3，33）私钥：KR(7,33)。

假设密文M=15。

加密：15^3mod33=9；C=9。

解密：9^7mod33=15；解密成功。

四，代码实现。

1，难点。

1，素数。

首先要解决的就是判断所输入的数子是否为素数，使用C++实现代码为：

bool isPrime(int num) {// 首先，检查数字0和1不是素数，因为它们只有1个因数if (num <= 1)return false;// 素数大于1，所以我们从2开始遍历到sqrt(num)，如果找到能整除num的因子，则num不是素数for (int i = 2; i <= sqrt(num); ++i) {// 如果num可以被i整除，说明num不是素数if (num % i == 0) // 模运算符%，结果为0表示可以整除return false;}// 如果我们没有找到任何因子，那么num就是素数return true;
}

首先，质数不能为负数。

其次在for循环内使用了sqre函数，sqre函数是计算所输入的值的平方根，要判断一个数是不是质数，只需要判断 2到所获取的数字之间开根号有没有可以整除的数就可以了。

此处使用了一个简单的数学规则，假设数n，我们并不知道它是否为质数，虽然也可以使用穷举法，但过于耗费时间；但如果他不是素数，必然存在除了1和它本身之外的数，假设有两个因数，都比根号n大，这两个因数相乘必然比根号n的二次方大，就比n大。所以，如果在2和根号n之间的整数能整除n，就说明n不是质数，反之则为质数。

2，模反因数运算。

在计算模反因数之前，要先了解模运算。

a/b=c……e。

a是被除数，d是除数，c是商，e是余数；在他们当中，e就是模。

简而言之，模就是取余运算，保证c为整数。

基于上述表达式，模运算表示为：

a mod b=e

模反因数的定义为：d*e mod n1=1(就是e对于n1的模逆元素)

就是d*e的积除以n1的值，余数是1。

使用C++实现：

// 函数用于判断一个数是否与n互质
bool isCoprime(int num, int n) {// 如果num和n的最大公约数为1，则它们互质return gcd(num, n) == 1;
}// 函数用于计算两个数的最大公约数
int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);
}// 找到一个最小的与n互质的质数eint e = 2;while (!isPrime(e) || !isCoprime(e, n·1)) {e++;}cout << "找到的最小的与 " << n << " 互质的质数是 " << e << "。" << endl;

2，完整代码。

#include <iostream>
#include <cmath>
using namespace std;// 定义一个函数 isPrime，接收一个整数作为参数
bool isPrime(int num) {// 首先，检查数字0和1不是素数，因为它们只有1个因数if (num <= 1)return false;// 素数大于1，所以我们从2开始遍历到sqrt(num)，如果找到能整除num的因子，则num不是素数for (int i = 2; i <= sqrt(num); ++i) {// 如果num可以被i整除，说明num不是素数if (num % i == 0) // 模运算符%，结果为0表示可以整除return false;}// 如果我们没有找到任何因子，那么num就是素数return true;
}
// 找到比 n1 小的最大质数
int findMaxPrimeLessThan(int n1) {for (int i = n1 - 1; i > 1; --i) {if (isPrime(i)) return i;}return -1; // 如果没有找到，返回 -1
}
bool isCoprime(int a, int b) {// 如果num和n的最大公约数为1，则它们互质int gcd(int a, int b);{if (b == 0) {return a;}return gcd(b, a % b);
}
}// 函数用于计算两个数的最大公约数
int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);
}
// 扩展欧几里得算法
void extendedEuclidean(int a, int b, int& x, int& y) {if (b == 0) {x = 1;y = 0;return;}int x1, y1;extendedEuclidean(b, a % b, x1, y1);x = y1;y = x1 - (a / b) * y1;
}// 计算模逆
int modInverse(int a, int m) {int x, y;extendedEuclidean(a, m, x, y);return (x % m + m) % m;
}
// 快速幂算法
long long fastPowerMod(long long base, long long exp, long long mod) {long long result = 1;while (exp > 0) {if (exp % 2 == 1) {result = (result * base) % mod;}base = (base * base) % mod;exp /= 2;}return result;
}int main() {char x;cout << "加密/解密(e/d) ：";cin >> x;//输入e或d，e表示加密，d表示解密if (x == 'e' || x == 'E') {char a;cout << "是否使用默认密钥？(y/n) :";cin >> a;//输入y或n，y表示使用默认密钥，n表示使用自定义密钥if (a == 'n'||a == 'N') {cout << "请输入两个用于加密的质数: \n";int num1, num2;cout << "请输入第一个质数: ";cin >> num1;cout << "请输入第二个质数: ";cin >> num2;//输入两个数if (isPrime(num1) && isPrime(num2)) {int p = num1;int q = num2;int n1 = (p - 1) * (q - 1);int e = findMaxPrimeLessThan(n1);//寻找ewhile (!isPrime(e) || !isCoprime(e, n1)) {e++;}int d = modInverse(e, n1);int n = p * q;int C;cout <<"n = "<< n << endl;cout <<"请输入要加密的数字(必须小于n): ";cin >> C;long long M = fastPowerMod(C, e, n);cout << "公钥是 (" << e << ", " << n << ")，私钥是 (" << d << ", " << n << ")。" << endl;cout << "加密后的数字是 ：" << M << endl;} else {cout << "输入的两个数中至少有一个不是素数,请重新输入。" << endl;}} else {cout << "默认密钥已使用." << endl;int p = 3;int q = 5;int n = p * q;int n1 = (p - 1) * (q - 1);int e = 7;int d = 11;int C;cout <<"n = "<< n << endl;cout <<"请输入要加密的数字(必须小于n): ";cout <<"请输入要加密的数字: ";cin >> C;int M = fmod(pow(C, e), n);cout << "加密前的数字是:" << C << endl;cout << "加密后的数字是:" << M << endl;cout << "公钥是 (" << e << ", " << n << ")，私钥是 (" << d << ", " << n << ")。" << endl;}
}else if (x == 'd'||x == 'D') {char a;cout << "是否使用默认密钥？(y/n):";cin >> a;if (a == 'n'||a == 'N'){int d, n, C;cout << "请输入私钥 (d, n)，中间使用空格分隔: ";cin >> d >> n;cout << "请输入要解密的数字: ";cin >> C; long long M = fastPowerMod(C, d, n);cout << "解密后的数字是 " << M << endl;}else if (a == 'y'||a == 'Y'){int d = 11;int n = 15;int C;cout <<"请输入要解密的数字: ";cin >> C;int M = fmod(pow(C, d), n);cout << "解密后的数字是 " << M << endl;}else {cout << "输入错误，请重新输入" << endl;}
}
else {cout << "输入错误，请重新输入" << endl;
}return 0;
}

这段代码，或者说这个插件，可以进行RSA计算。不仅可以加密，也可以根据密钥进行解密；而且内置了简单的默认加密方式用于学习，而且还可以对加密参数进行手动修改，更改内容也有相应的检测机制。

运行结果为：

1，使用默认密钥：

2，自定义密钥：