凡科网站后台,seo引擎优化外包,主流的net快速开发框架,中英版网站系统一#xff0c;RSA简介。
RSA#xff0c;一种非对称加密方式。是目前为止最有影响力的加密算法之一#xff0c;而且是第一个同时应用于加密和数字签名的算法。
其原理为#xff1a;两个大素数相乘容易#xff0c;但是若想将两个大素数相乘的积再分解为两个原始的素数很难…
一RSA简介。
RSA一种非对称加密方式。是目前为止最有影响力的加密算法之一而且是第一个同时应用于加密和数字签名的算法。
其原理为两个大素数相乘容易但是若想将两个大素数相乘的积再分解为两个原始的素数很难。安全性依赖于大数因式分解的困难性。
使用公钥加密私钥解密。
二主要原理。
1公钥私钥的制作过程
1选择两个足够大且互质的素数p和q。
2计算出pq的积n。
3计算出n的欧拉函数n1(p-1)*(q-1).
4选取公钥e选择一个与n1互质的质数不为n1因子且1en1。
5计算私钥dd*e mod n11(就是e对于n1的模逆元素)。
得到公钥KN(e,n)私钥KR(d,n).
2加密解密。
设明文为M密文为C。
加密M^e mod nC。
解密C^d mod nM。
三简单测试。
加密解密
根据第二步中的步骤我们可以进行一项简单测试。
1假设p3,q11。
2n为33。
3n的欧拉函数n120。
4选取公钥e3。
5计算私钥d*3%201,d7。
得到了公钥KN333私钥KR(7,33)。
假设密文M15。
加密15^3mod339C9。
解密9^7mod3315解密成功。
四代码实现。
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/bc……e。
a是被除数d是除数c是商e是余数在他们当中e就是模。
简而言之模就是取余运算保证c为整数。
基于上述表达式模运算表示为
a mod be
模反因数的定义为d*e mod n11(就是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或de表示加密d表示解密if (x e || x E) {char a;cout 是否使用默认密钥(y/n) :;cin a;//输入y或ny表示使用默认密钥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自定义密钥
