emmm先转载一篇文章吧
RSA算法原理(一)
非常推荐的一篇文章,我原本就想写个讲RSA算法的文章,然后发现这篇文章基本就可以满足我的要求了,所以就直接转过来了。
这里主要讲c++代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <bits/stdc++.h>
#include <math.h>
#include<ctime>
using namespace std;
#define randomInt(a,b) (rand()%(b-a+1)+a)

typedef long long int ll;
#define int ll

struct rsakeys{
int p, q, n, fn, d, e;
};

rsakeys* rsakey;

ll mod_mul(ll a, ll b, ll mod){
ll res = 0;
while (b){
if (b & 1)
res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res;
}

ll mod_pow(ll a, ll n, ll mod){
ll res = 1;
while (n){
if (n & 1)
res = mod_mul(res, a, mod);
a = mod_mul(a, a, mod);
n >>= 1;
}
return res;
}

// Miller-Rabin随机算法检测n是否为素数
bool Miller_Rabin(ll n){
if (n == 2)
return true;
if (n < 2 || !(n & 1))
return false;
ll m = n - 1, k = 0;
while (!(m & 1))
{
k++;
m >>= 1;
}
for (int i = 1; i <= 20; i++) // 20为Miller-Rabin测试的迭代次数
{
ll a = rand() % (n - 1) + 1;
ll x = mod_pow(a, m, n);
ll y;
for (int j = 1; j <= k; j++)
{
y = mod_mul(x, x, n);
if (y == 1 && x != 1 && x != n - 1)
return false;
x = y;
}
if (y != 1)
return false;
}
return true;
}

int gcd(int a,int b){
int r;
while(b){
r=a%b;
a=b;
b=r;
}
return a;
}

int creat_prime(){
int tmp = 4;
while(!Miller_Rabin(tmp))tmp=rand();
return tmp;
}

int create_keys(rsakeys* key){
srand((unsigned)time(NULL));

key->p = creat_prime();
cout<<"Your p is: "<<key->p<<endl;
key->q = creat_prime();
cout<<"Your q is: "<<key->q<<endl;

key->n=key->p*key->q;
cout<<"Your n is: "<<key->n<<endl;
key->fn = (key->p-1) * (key->q-1);
cout<<"Your fn is: "<<key->fn<<endl;

while(1){
key->e = rand()%key->fn;
if(gcd(key->e,key->fn)==1)break;
}
cout<<"Your e is: "<<key->e<<endl;

int k = 1;
while((k*key->fn+1)%key->e){
k++;
}
key->d = (k*key->fn+1)/(key->e);
cout<<"Your d is: "<<key->d<<endl;
}

int create_keys_by_pq(int p, int q, rsakeys* key){
cout<<p<<" "<<q<<endl;
key->n = p * q;
cout<<"Your n is: "<<key->n<<endl;
key->fn = (p-1) * (q-1);
cout<<"Your fn is: "<<key->fn<<endl;

while(1){
key->e = rand()%key->fn;
if(gcd(key->e,key->fn)==1)break;
}
cout<<"Your e is: "<<key->e<<endl;

int k = 1;
while((k*key->fn+1)%key->e){
k++;
}
key->d = (k*key->fn+1)/(key->e);
cout<<"Your d is: "<<key->d<<endl;
}

int write_to_file(rsakeys* key){
ofstream d, e, n;

d.open("d");
d<<key->d;
e.open("e");
e<<key->e;
n.open("n");
n<<key->n;

d.close();e.close();n.close();
return 0;
}

int read_file(rsakeys* key){
ifstream d, e, n;

d.open("d");
d>>key->d;
e.open("e");
e>>key->e;
n.open("n");
n>>key->n;

d.close();e.close();n.close();
return 0;
}

signed main(){
rsakey = (rsakeys*)malloc(sizeof(rsakeys));
cout<<"============================================================"<<endl;
cout<<"1. Creat keys and write to file."<<endl;
cout<<"2. Creat keys by given p and q and write to file."<<endl;
cout<<"3. Read keys from file."<<endl;
cout<<"4. Encrypt a number."<<endl;
cout<<"5. Decrypt a number."<<endl;
cout<<"============================================================"<<endl;

int d, e, n;
while(1){
char command[64];
ll msg;
ll key;
ll inn;
scanf("%s",command);
if(!strcmp(command,"1")){
create_keys(rsakey);
write_to_file(rsakey);
}
if(!strcmp(command,"2")){
int p,q;
cin>>p>>q;
create_keys_by_pq(p,q,rsakey);
write_to_file(rsakey);
}
if(!strcmp(command,"3")){
read_file(rsakey);
}
if(!strcmp(command,"4")){
scanf("%d",&msg);
cout<<mod_pow(msg,rsakey->e,rsakey->n)<<endl;
}
if(!strcmp(command,"5")){
scanf("%d",&msg);
cout<<mod_pow(msg,rsakey->d,rsakey->n)<<endl;
}
}
return 0;
}

就酱啦,再扔篇参考文章溜了。。。
[[2]RSA密码的实现-你也能看的懂的python实现方法][2]
[2]: https://blog.csdn.net/kinnisoy/article/details/91049381 “RSA密码的实现-你也能看的懂的python实现方法”