======================= **基础知识** =======================
对称性算法： 信息传递的双方的加解密信息，需要保护的是加解密信息；因为此时加解密的方式是一样的；
非对称性算法(公开密钥加密算法）: 信息传递的双方的加解密信息，需要保护的是解密信息，可以公开的是加密信息；此时加解密的方式是不一样的；
举一个最简单的非对称加密方式：
传递一个 <1000 的数字，每次加密方式是 * 91， 然后传递出去； 解密方式是 接收信息 * 11 % 1000；
1 #include<iostream>
2 using namespace std;
3
4 int main() {
5
6 int in_val = 0, pass_val = 0, dec_val = 0;
7 while(cin >> in_val) {
8 cout << "input val is " << in_val
9 << ",then becaom val: " << (pass_val = in_val * 91) <<
10 ", final decode val is: " << (dec_val = pass_val * 11 % 1000) << endl;
11 }
12 return 0;
13 }
最简单的一种RSA
非对称加密算法过程：(下面的部分涉及到欧拉定理，具体实现逻辑是通过找到两个互为逆元的值，然后分别保存这一对值作为加密解密的钥匙）；
1. 任意选择两个大素数 p， q， n = p * q;
2. φ(n) = φ(p) * φ(q) = (p - 1) * (q - 1)
3. 随机选取一个小于φ(n),且与 φ(n) 互质的 e;
4. 通过e 取得其逆元 d 值，使得 e * d ≡ 1 (mode φ(n));
证明：已知 phi_n, e, 求e 的逆元 d;
phi_n = k * e + r ; (k = phi_n / e, r = phi_n % e)
k * e + r ≡ 0 (mod phi_n)
k * e * d * r-1 + r * d * r-1 ≡ 0 (mod phi_n)
k * r-1 + d ≡ 0 (mod phi_n)
d = - k * r-1 (mod phi_n) //将一个较大值问题转换成一个较小值问题；
此时可以得到 加密钥匙（公钥）: (e, n); 加密过程 Me % n = C
解密钥匙（私钥）: (d, n); 解密过程 Cd % n = M
证明过程：
（Me )d% n = (Me * d )% n = M(k*φ(n) + 1) % n = M(k*φ(n) ) * M % n = M % n = M
======================= **代码演示** =======================
1 //#include "RSA.h"
2 #include <iostream>
3 using namespace std;
4
5 #ifndef DEBUG
6 #define MSG 0
7 #else
8 #define MSG 1
9 #endif
10
11 #define MAX_N 20000
12 int prime[MAX_N] = {0};
13
14 void init_prime() {
15 for(int i = 2; i < MAX_N; i++) {
16 if(!prime[i]) prime[++prime[0]] = i;
17 for(int j = 1; j <= prime[0]; j++) {
18 if(i * prime[j] >= MAX_N) break;
19 prime[i * prime[j]] = 1;
20 if(!(i % prime[j])) break;
21 }
22 }
23 return;
24 }
25
26 long long gcd(long long a, long long b){
27 if(!b) return a;
28 return gcd(b, a % b);
29 }
30
31 long long get_inv(long long e, long long phi, long long &x, long long &y){
32 if(phi == 0) {
33 x = 1, y = 0;
34 return e;
35 }
36 long long r = get_inv(phi ,e % phi, y, x);
37 y -= ( e / phi) * x;
38 return r;
39 }
40
41 long long quick_mod(long long a, long long b, long long c) {
42 long long ans = 1, temp = a;
43 while(b) {
44 if (b & 1) ans = ans * temp % c;
45 temp = temp *temp % c;
46 b >>= 1;
47 }
48 return ans;
49 }
50 int main()
51 {
52 init_prime();
53 srand(time(0));
54
55 //1.选取两个大质数；
56 long long p = 0 , q = 0;
57 do{
58 p = random() % 100 + prime[0] - 99;
59 q = random() % 100 + prime[0] - 99;
60 }while(p == q);
61
62 //2. 获得phi_n;
63 long long n = prime[p] * prime[q], phi_n = (prime[p] - 1) * (prime[q] - 1),
64 e = 0;
65
66 //3.随机选取一个与phi_n 互质,且小于phi_n 的值
67 while(e == 0 || gcd(e, phi_n) != 1) {
68 e = random() % phi_n;
69 }
70
71 //4.根据e 获得逆元d;
72 long long d = 0, y = 0;
73 get_inv(e, phi_n, d, y);
74 d = (((d % phi_n) + phi_n) % phi_n);
75 if(MSG) cout << e << " * " << d << " % " << phi_n << "= " << e * d % phi_n << endl;
76 cout << "( " << e << ", " << n << ")" << endl;
77 cout << "( " << d << ", " << n << ")" << endl;
78
79 //5. 使用密钥
80 long long M = 0, C = 0;
81
82 while(cin >> M) {
83 C = quick_mod(M, e , n);
84 printf("intput M value is %lld, the new RSA encryption %lld, %lld\n",
85 M, C, quick_mod(C, d, n));
86 }
87
88 return 0;
89 }
RSA
======================= **应用场景** =======================
各类的加密传输信息，无密码登录等场景；
标签：prime,phi,return,int,RSA,long,算法,金融,mod From： https://www.cnblogs.com/ChunboBlog/p/16753499.html