RSA公钥加密算法
1. 什么是RSA?
-
计算机中常用的加密技术分为两类:对称加密、非对称加密。
-
RSA属于非对称加密。加密、解密过程使用不同的秘钥,分为公钥、私钥。公钥可以公开,私钥不可以。
-
对称加密:加密和解密使用相同的的秘钥
Key
,这个Key
需要在网络上传输,不安全,因此需要非对称加密。
2. RSA算法
2.1 生成公钥和私钥
(1)随意选择两个大的素数P
和Q
,P
不等于Q
;
(2)令 N = P × Q 、 T = ( P − 1 ) × ( Q − 1 ) N = P \times Q、T = (P – 1) \times (Q – 1) N=P×Q、T=(P−1)×(Q−1);
(3)选择一个整数E
作为秘钥,需要满足:gcd(E, T)=1 && E<T
;
(4)根据 ( D × E ) m o d T = 1 (D \times E) \ mod \ T = 1 (D×E) mod T=1,计算出D
,作为另一个秘钥;
(5)使用PK=(N、E)
作为公钥、SK=(N, D)
作为私钥(当然可以反过来)。
2.2 使用公钥加密信息
-
使用
PK=(N、E)
公钥加密信息。 -
若明文为
M
,则密文C
可以按照如下计算得到(要求M<N
):
C = M E m o d N C = M ^ E \ mod \ N C=ME mod N
2.3 使用私钥解密信息
-
使用
SK=(N, D)
私钥解密信息。 -
如密文为
C
,则明文M
可以按照如下计算得到:
M = C D m o d N M = C ^ D \ mod \ N M=CD mod N
3. 一个例子
生成公钥和私钥
-
取
P=11、Q=13
; -
N = P × Q = 11 × 13 = 143 、 T = ( P − 1 ) × ( Q − 1 ) = 10 × 12 = 120 N = P\times Q=11\times 13=143、T = (P-1)\times (Q-1)=10\times 12=120 N=P×Q=11×13=143、T=(P−1)×(Q−1)=10×12=120;
-
取
E=7
; -
因为 ( D × 7 ) m o d 120 = 1 (D \times 7) \ mod \ 120 = 1 (D×7) mod 120=1,得到
D=103
。 -
因此公钥
(N, E) = (143, 7)
,秘钥(N, D)=(143, 103)
使用公钥加密信息
- 对数据
M = 2
进行加密,得到加密后的数据C
:
C = M E m o d N = 2 7 m o d 143 = 128 C = M ^ E \ mod \ N \\ = 2^7 \ mod \ 143 = 128 C=ME mod N=27 mod 143=128
使用私钥解密
- 对数据
C=128
进行解密,解密后的数据为M
:
M = C D m o d N = 12 8 103 m o d 143 = 2 M = C ^ D \ mod \ N \\ = 128^{103} \ mod \ 143 = 2 M=CD mod N=128103 mod 143=2
4. RSA的应用:数字签名
-
数字签名是实现安全交易的核心技术之一,实现基础是RSA加密技术。
-
数字签名类似于我们生活中的手写签名,必须保证签名的人事后不能抵赖,同时不能让别人伪造我们的签名。因此数字签名需要保证:
-
(1)发送者事后不能抵赖对报文的签名;
-
(2)接受者不能伪造对报文的签名。
-
-
如果
A
向B
发送报文M
,A
手中有私钥,公钥是公开的,A
给M
使用私钥进行加密再发给B
即可。 -
这样即可保证上述两点:
-
(1)因为只有
A
可以对M
使用私钥进行加密,A
不能抵赖; -
(2)
B
用公钥可以得到原始信息M
,如果伪造成M'
,则A
可以证明其伪造了信息。
-
5. RSA的安全性
-
RSA算法的安全性依赖于大数分解。因此为了保证安全性,需要使得
P、Q
非常大。 -
因为数据很大,又牵涉到幂次运算,因此计算量很大。
6. 代码实现
/* 测试用例 11 13 */
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int p, q; // 两个质数
int N, T;
int E, D; // 公钥: (N, E), 私钥: (N, D)
PII PK, SK; // 公钥、私钥
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void gen_keys() {
// 生成公钥、私钥
N = p * q, T = (p - 1) * (q - 1);
for (E = 2; ; E++)
if (gcd(E, T) == 1)
break;
for (D = 2; ; D++)
if (D * E % T == 1)
break;
PK = {
N, E}, SK = {
N, D};
}
int qmi(int a, int b, int p) {
int res = 1 % p;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int encryption(int m) {
// 加密
int n = PK.x, e = PK.y;
return qmi(m, e, n);
}
int decrypt(int c) {
// 解密
int n = SK.x, d = SK.y;
return qmi(c, d, n);
}
int main() {
cin >> p >> q;
// 第一步:生成公钥、私钥
gen_keys();
printf("公钥: (%d, %d)\n", PK.x, PK.y);
printf("私钥: (%d, %d)\n", SK.x, SK.y);
// 第二步:加密
int m = 2;
int c = encryption(m);
printf("%d 加密后的数据: %d\n", m, c);
// 第三步:解密
printf("%d 解密后的数据: %d\n", c, decrypt(c));
return 0;
}
- 参考书:程序员的数学思维修炼。
今天的文章rsa公钥加密算法的提出者_rsa生成公钥和私钥的步骤「建议收藏」分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/75461.html