1.RSA非对称加密
(1)选择两个素数p和q ,计算n=p*q和欧拉函数φ(n)=(p-1)(q-1)，选择整数e，使gcd(φ(n), e)=1（即φ(n)和e是互素），1<e<φ(n)；
(2)计算e的逆元d=e-1mod φ(n)（即ed = 1 mod φ(n)）；
(3)得到公钥Kpub＝{e, n}，私钥Kpri＝{d, n}（公开公钥Kpub ，保密私钥Kpri ）；
(4)加密(使用公钥Kpub)：对于明文m<n，密文c=me mod n ;
(5)解密(使用私钥Kpri)：对于密文c，明文m=cd mod n
2.RSA加解密示例
3.RSA正确性证明
4.代码实现（c++）
#include <iostream>using namespace std;// 最大公因数int maxCommonDivisor(int a, int b){int temp = a;if (a < b){a = b;b = temp;}while(a % b){temp = b;b = a % b;a = temp;}return b;}// 最小公倍数int leastCommonMultiple(int a, int b){int macDivisor = maxCommonDivisor(a, b);return a / macDivisor * b;}// 计算 input ^ rate mod yint multiMod(int input, int rate, int y){int start = 1;int arr[100];arr[0] = 1;arr[1] = input;int step = 1;int result = 1;while(rate){if (step == 1){arr[step] = input;}else{arr[step] = arr[step - 1] * arr[step - 1];arr[step] %= y;}if(rate&1){result *= arr[step];result %= y;}step ++;rate = rate >> 1;}return result;}int main(){int input;int p, q;int N, L, E, D;while(cin >> p >> q >> input >> E){N = p * q;//最小公倍数L = leastCommonMultiple(p - 1, q - 1);//E * D mod L = 1int X = 1;while((X * L + 1) % E){X ++;}D = (X * L + 1) / E;cout<<"N = " << N << " L = " << L << " E = " << E << " D = " << D << " X = " << X <<endl;// 加密过程int code = multiMod(input, E, N);// 解密过程int deCode = multiMod(code, D, N);cout<< "code = " << code << " deCode = " << deCode << endl;}}
