RSA利用大整数实现加密解密与签名认证

145 阅读 0 评论 96 点赞

我是靠谱客的博主帅气夕阳，这篇文章主要介绍RSA利用大整数实现加密解密与签名认证，现在分享给大家，希望可以做个参考。

（一）利用RSA进行加密

1.原理

该算法的数学基础是初等数学论中的Euler定理，其安全性建立在大整数因式分解的困难性之上，利用了单向陷门函数（如图）的原理。

2.算法描述

明文空间P＝密文空间C=Zn
密钥的生成

选择互异素数p,q，

计算 $n = p * q, \emptyset (n) = (p - 1) (q - 1)$

选择整数e使 $g c d (\emptyset (n), e) = 1, 1 < e < \emptyset (n)$

计算d,使 $d=e^{-1}mod emptyset(n)$
公钥Pk={e,n}
私钥Sk={d,n}
加密 (用e,n)
明文：M<n 密文： $C=M^e(mod n)$
解密 (用d,n)
密文：C 明文： $M=C^d（mod n)$

3.安全性要求

①p与q必为足够大的素数，使分析者没有办法在有效时间内将n分解出来。建议选择 p和q大约是100位的十进制素数。模数n的长度要求至少是 512比特。

②为了抵抗现有的整数分解算法，对RSA模n的素因子 p和q还有如下要求：

(1)|p-q|很大，通常 p和q的长度相同；

(2)p-1 和q-1分别含有大素因子p1和q1

(3)gcd(p1-1,q1-1)应该很小。

③为了提高加密速度，通常取e为特定的小整数，如EDI国际标准中规定$ e＝2^{16}+1$，ISO/IEC9796中甚至允许取e＝3。这时加密速度一般比解密速度快10倍以上。

4.算法总结

(1)选择两个大素数p和q，通常要求每个均大于10100。

计算n＝pq和z＝(p－1)(q－1)。

选择一与z互质的数、令其为d 。

找到一个e满足e×d＝1 (mod z)。

(2)选好这些参数后，将明文划分成块，使得每个明文报文P 长度m满足0<m<n加密P时，计算 $C＝P^e(mod n)$ ，解密C时计算 $P＝C^d(mod n)$ 。由于模运算的对称性，可以证明，在确定的范围内，加密和解密函数是互逆的。

(3)为实现加密，需要公开(e, n)，为实现解密需要(d, n)。

5.算法图

其中在解密中，欧拉定理的推理，参照：《应用密码学》/胡向东，魏琴芳，胡蓉编著. —4版. —北京：电子工业出版社，2019.6 ：68

（二）利用RSA进行数字签名

签名是用自己的私钥对要签名的内容进行签名，需要进行验证的一方利用签名方的公钥进行验证

（三）加密与签名的c++源代码

注意

1.代码是写在一个头文件当中的，对RSA的加密测试，签名测试，需要在mian（）里面调用

2.包含素性检测的头文件"Miller-Rabin.h"，参考：素性检测（Miller-Rabin）_remandancy.h的博客-CSDN博客_素性检测

3.包欧几里得算法的头文件"Euclid.h"，参考：欧几里得函数与扩展欧几里得函数_remandancy.h的博客-CSDN博客_欧几里得函数

4.需要安装大整数集vcpkg，请参考：windows通过vcpkg安装gmp库_Fretory的博客-CSDN博客_vcpkg安装gmp，注意在安装的根目录，名录名称不要有空格

5.一份别人使用GMP写RSA的参考：基于GMP大数库用 “ 快速幂取模算法 ” + “ 扩展欧几里得算法 ”实现RSA加密算法（C++实现）_Em0s_Er1t的博客-CSDN博客

复制代码

#pragma once
#include<gmp.h>
#include<gmpxx.h>
#include<iostream>
#include<vector>
#include"Miller-Rabin.h"
#include"Euclid.h"
using namespace std;
class RSA
{
public:
RSA();
~RSA();
//void Init(int len);//初始化密钥，公钥,输入为密钥的长度（素数的长度）
void Init(mp_bitcnt_t len);
void SetMeesge();//设置明文
void SetCipher();//设置密文
void Encryption();//加密
void Decryption();//解密
void Signature();//签名
void Authenticate();//认证
private:
mpz_class p, q,d;//两个大素数,私钥d
mpz_class n, e;//公钥
mpz_class eurl;//欧拉数(p-1)(q-1)
mpz_class *message, *cipher,*temp;
int textsize = 0;
int cipsize = 0;
};
RSA::RSA()
{
}
RSA::~RSA()
{
}
//inline void RSA::Init(int len)//初始化密钥，公钥,输入为密钥的生成0-len长度的密钥
//{
//	//产生随机数的范围
//	mpz_class temp1=1, temp2=1,subtemp=0;
//	for (int i =1; i < len; i++)
//	{
//
temp1 = temp1 * 10;
//	}
//	temp2 = temp1 * 10;
//	subtemp = temp2 - temp1;
//	//产生随机数
//	mpz_class ran;
//	gmp_randclass rr(gmp_randinit_default);//设置随机数生成算法为默认
//	rr.seed(time(NULL));//设置随机化种子为当前时间;
//	while (1)
//	{
//
ran = rr.get_z_bits(512);//生成125bit的随机数
//
mpz_class random = ran.get_ui(); //生成随机数
//
p = random % subtemp + temp1;//生成temp1-temp2之间的随机给p
//
if (Miller_Rabin(p))
//
{
//
break;
//
}
//	}
//	cout << "p=" << p << endl;
//	while (1)
//	{
//
ran = rr.get_z_bits(512);//生成512bit的随机数
//
mpz_class random = ran.get_ui(); //生成随机数
//
q = random % subtemp + temp1;//生成temp1-temp2之间的随机数给q
//
if (Miller_Rabin(q)&&(q!=p))
//
{
//
break;
//
}
//	}
//	cout << "q=" << q << endl;
//	n = p * q;
//	cout << "n=" << n << endl;
//	eurl = (p - 1)*(q - 1);
//	cout << "eurl=" << eurl << endl;
//	while (1)
//	{
//
ran = rr.get_z_bits(512);//生成512bit的随机数
//
mpz_class random = ran.get_ui(); //生成随机数
//
e = random % (eurl - 1)+1;//生成1-euil之间的数
//
if (GCD(e, eurl) == 1)//判断是否互素
//
{
//
break;
//
}
//	}
//	cout << "e=" << e << endl;
//	d = ExtendedEuclid(e, eurl);
//	d = d + eurl;
//	cout << "d=" << d << endl;
//}
inline void RSA::Init(mp_bitcnt_t len)//初始化密钥，公钥,输入为密钥的生成0-len长度(bit)的密钥
{
//产生随机数的范围
//产生随机数
mpz_class ran;
gmp_randclass rr(gmp_randinit_default);//设置随机数生成算法为默认
rr.seed(time(NULL));//设置随机化种子为当前时间;
while (1)
{
ran = rr.get_z_bits(len);//生成lenbit的随机数
p = ran.get_ui(); //生成随机数
if (Miller_Rabin(p))
{
break;
}
}
cout << "p=" << p << endl;
while (1)
{
ran = rr.get_z_bits(len);//生成512bit的随机数
q = ran.get_ui(); //生成随机数
if (Miller_Rabin(q)&&(q!=p))
{
break;
}
}
cout << "q=" << q << endl;
n = p * q;
cout << "n=" << n << endl;
eurl = (p - 1)*(q - 1);
cout << "eurl=" << eurl << endl;
e = 5;
//while (1)
//{
//	ran = rr.get_z_bits(len);//生成512bit的随机数
//	mpz_class random = ran.get_ui(); //生成随机数
//	e = random % (eurl - 1)+1;//生成1-euil之间的数
//	if (GCD(e, eurl) == 1)//判断是否互素
//	{
//
break;
//	}
//}
cout << "e=" << e << endl;
d = ExtendedEuclid(e, eurl);
d = d + eurl;
cout << "d=" << d << endl;
}
inline void RSA::SetMeesge()
{
cout << "请输入明文：";
string text;
cin >>text;
textsize = text.size();
message = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
message[i] = (int)text[i];
}
}
inline void RSA::SetCipher()
{
cout << "对密文进行解密：";
cipher = temp;
}
inline void RSA::Encryption()
{
/*cout << "请输入明文：";
string text;
cin >> text;
textsize = text.size();
message = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
message[i] = (int)text[i];
}*/
cout << "加密结果：";
temp = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(message[i], e, n);
cout << temp[i]<<",";
}
}
inline void RSA::Decryption()
{
cout << "解密结果：";
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(temp[i], d, n);
cout << (char)(temp[i].get_ui());
}
}
void RSA::Signature()
{
cout << "输出需要签名的内容：";
string text;
cin >> text;
textsize = text.size();
message = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
message[i] = (int)text[i];
}
//签名：
temp = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(message[i], d, n);
cout << temp[i] << ",";
}
}
void RSA::Authenticate()
{
cout << endl<<"认证结果：";
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(temp[i], e, n);
cout << (char)(temp[i].get_ui());
}
}
void RSATest()//加密解密
{
RSA rsa;
int len;
cout << "素数长度(bit)：";
cin >> len;
rsa.Init(len);
rsa.SetMeesge();
rsa.Encryption();
cout << endl;
rsa.SetCipher();
rsa.Decryption();
}
void RSASinAndAuth()//签名与认证
{
RSA rsa;
int len;
cout << "素数长度(bit)：";
cin >> len;
rsa.Init(len);
rsa.Signature();
rsa.Authenticate();
}

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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#pragma once
#include<gmp.h>
#include<gmpxx.h>
#include<iostream>
#include<vector>
#include"Miller-Rabin.h"
#include"Euclid.h"
using namespace std;
class RSA
{
public:
RSA();
~RSA();
//void Init(int len);//初始化密钥，公钥,输入为密钥的长度（素数的长度）
void Init(mp_bitcnt_t len);
void SetMeesge();//设置明文
void SetCipher();//设置密文
void Encryption();//加密
void Decryption();//解密
void Signature();//签名
void Authenticate();//认证
private:
mpz_class p, q,d;//两个大素数,私钥d
mpz_class n, e;//公钥
mpz_class eurl;//欧拉数(p-1)(q-1)
mpz_class *message, *cipher,*temp;
int textsize = 0;
int cipsize = 0;
};
RSA::RSA()
{
}
RSA::~RSA()
{
}
//inline void RSA::Init(int len)//初始化密钥，公钥,输入为密钥的生成0-len长度的密钥
//{
//	//产生随机数的范围
//	mpz_class temp1=1, temp2=1,subtemp=0;
//	for (int i =1; i < len; i++)
//	{
//
temp1 = temp1 * 10;
//	}
//	temp2 = temp1 * 10;
//	subtemp = temp2 - temp1;
//	//产生随机数
//	mpz_class ran;
//	gmp_randclass rr(gmp_randinit_default);//设置随机数生成算法为默认
//	rr.seed(time(NULL));//设置随机化种子为当前时间;
//	while (1)
//	{
//
ran = rr.get_z_bits(512);//生成125bit的随机数
//
mpz_class random = ran.get_ui(); //生成随机数
//
p = random % subtemp + temp1;//生成temp1-temp2之间的随机给p
//
if (Miller_Rabin(p))
//
{
//
break;
//
}
//	}
//	cout << "p=" << p << endl;
//	while (1)
//	{
//
ran = rr.get_z_bits(512);//生成512bit的随机数
//
mpz_class random = ran.get_ui(); //生成随机数
//
q = random % subtemp + temp1;//生成temp1-temp2之间的随机数给q
//
if (Miller_Rabin(q)&&(q!=p))
//
{
//
break;
//
}
//	}
//	cout << "q=" << q << endl;
//	n = p * q;
//	cout << "n=" << n << endl;
//	eurl = (p - 1)*(q - 1);
//	cout << "eurl=" << eurl << endl;
//	while (1)
//	{
//
ran = rr.get_z_bits(512);//生成512bit的随机数
//
mpz_class random = ran.get_ui(); //生成随机数
//
e = random % (eurl - 1)+1;//生成1-euil之间的数
//
if (GCD(e, eurl) == 1)//判断是否互素
//
{
//
break;
//
}
//	}
//	cout << "e=" << e << endl;
//	d = ExtendedEuclid(e, eurl);
//	d = d + eurl;
//	cout << "d=" << d << endl;
//}
inline void RSA::Init(mp_bitcnt_t len)//初始化密钥，公钥,输入为密钥的生成0-len长度(bit)的密钥
{
//产生随机数的范围
//产生随机数
mpz_class ran;
gmp_randclass rr(gmp_randinit_default);//设置随机数生成算法为默认
rr.seed(time(NULL));//设置随机化种子为当前时间;
while (1)
{
ran = rr.get_z_bits(len);//生成lenbit的随机数
p = ran.get_ui(); //生成随机数
if (Miller_Rabin(p))
{
break;
}
}
cout << "p=" << p << endl;
while (1)
{
ran = rr.get_z_bits(len);//生成512bit的随机数
q = ran.get_ui(); //生成随机数
if (Miller_Rabin(q)&&(q!=p))
{
break;
}
}
cout << "q=" << q << endl;
n = p * q;
cout << "n=" << n << endl;
eurl = (p - 1)*(q - 1);
cout << "eurl=" << eurl << endl;
e = 5;
//while (1)
//{
//	ran = rr.get_z_bits(len);//生成512bit的随机数
//	mpz_class random = ran.get_ui(); //生成随机数
//	e = random % (eurl - 1)+1;//生成1-euil之间的数
//	if (GCD(e, eurl) == 1)//判断是否互素
//	{
//
break;
//	}
//}
cout << "e=" << e << endl;
d = ExtendedEuclid(e, eurl);
d = d + eurl;
cout << "d=" << d << endl;
}
inline void RSA::SetMeesge()
{
cout << "请输入明文：";
string text;
cin >>text;
textsize = text.size();
message = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
message[i] = (int)text[i];
}
}
inline void RSA::SetCipher()
{
cout << "对密文进行解密：";
cipher = temp;
}
inline void RSA::Encryption()
{
/*cout << "请输入明文：";
string text;
cin >> text;
textsize = text.size();
message = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
message[i] = (int)text[i];
}*/
cout << "加密结果：";
temp = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(message[i], e, n);
cout << temp[i]<<",";
}
}
inline void RSA::Decryption()
{
cout << "解密结果：";
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(temp[i], d, n);
cout << (char)(temp[i].get_ui());
}
}
void RSA::Signature()
{
cout << "输出需要签名的内容：";
string text;
cin >> text;
textsize = text.size();
message = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
message[i] = (int)text[i];
}
//签名：
temp = new mpz_class[textsize];
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(message[i], d, n);
cout << temp[i] << ",";
}
}
void RSA::Authenticate()
{
cout << endl<<"认证结果：";
for (int i = 0; i < textsize; i++)
{
temp[i] = Quick_Power_Mod(temp[i], e, n);
cout << (char)(temp[i].get_ui());
}
}
void RSATest()//加密解密
{
RSA rsa;
int len;
cout << "素数长度(bit)：";
cin >> len;
rsa.Init(len);
rsa.SetMeesge();
rsa.Encryption();
cout << endl;
rsa.SetCipher();
rsa.Decryption();
}
void RSASinAndAuth()//签名与认证
{
RSA rsa;
int len;
cout << "素数长度(bit)：";
cin >> len;
rsa.Init(len);
rsa.Signature();
rsa.Authenticate();
}