RSA加密

RSA

RSA是非对称秘钥加密。用公钥加密,私钥解密。反之亦可。

(1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
 (2)甲方获取乙方的公钥,然后用它对信息加密。
 (3)乙方得到加密后的信息,用私钥解密。

解决了对称加密中秘钥传输的问题,同时也可以用于数字签名。
基于大素数难分解,算法可靠,密钥越长,就越难破解。
目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解。
可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。

基础数论知识

欧拉函数

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

特别的如果n为质数,则 φ(n)=n-1
如果p,q互质,且n=p*q 则 φ(n)=φ(p)×φ(q)

欧拉定理

如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
这里写图片描述

欧拉定理有一个特殊情况:
假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成:
这里写图片描述

乘法逆元

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。
这里写图片描述
这是b称为a的模反元素
欧拉定理可以用来证明模反元素必然存在。
这里写图片描述
可以看到,a的 φ(n)-1 次方,就是a的模反元素。
对于乘法逆元的求解,需要使用扩展的欧几里得算法
这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int extgcd(int a, int b, int& x, int& y)
{
int d = a;
if(b != 0){
d = extgcd(b, a % b, y, x);
y -= (a / b) * x;
}else {
x = 1;
y = 0;
}
return d;
}
int mod_inverse(int a, int m) //a模m的乘法逆元
{
int x, y;
extgcd(a, m, x, y);
return (m + x % m) % m;
}

RSA加密与解密

生成密钥

1 随机选择两个不相等的质数p和q。

选择p=61,q=53

2 计算p和q的乘积n。

n = p*q = 3233

n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

3 计算n的欧拉函数φ(n)。

φ(n) = (p-1)(q-1)
φ(3233)等于60×52,即3120

4 随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。

随机选e = 17。(实际应用中,常常选择65537。)

5.计算e对于φ(n)的模反元素d。

ed ≡ 1 (mod φ(n))

用”扩展欧几里得算法”求解,此处省略具体过程。解得 d=2753。

6.将n和e封装成公钥,n和d封装成私钥。

n=3233,e=17,d=2753
所以公钥就是 (3233,17),私钥就是(3233, 2753)。

加密

所谓”加密”,就是算出下式的c:

m^e ≡ c (mod n)

其中m为明文,c为密文,(n,e)公钥

公钥(n,e) 只能加密小于n的整数m,如果要加密大于n的整数有两种方法:分段进行加密;先采用对称加密的方式加密,再使用公钥加密对称加密的密钥。

解密

所谓”解密”,就是通过下式算出明文

c^d ≡ m (mod n)

其中c为密文,m为明文,(n,d)私钥

可以看到,如果不知道d,就没有办法从c求出m。而要知道d就必须分解n。

代码实现

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
//快速幂
int fast_pow_mod(int a,int b,int n){
int result=1;
for (int i = 0; i <b ; ++i) {
result *= a;
result %= n;
}
return result;
}

//加密
vector<int> RSA_encrypt(string message, int e, int n){
int length = message.length();
vector<int> result;
for (int i = 0; i < length; ++i) {
result.push_back(fast_pow_mod(message[i],e,n));
}
return result;
}

//解密
vector<int> RSA_decrypt(vector<int> c,int d,int n){
vector<int>::iterator it;
vector<int> result;
for (it=c.begin();it!=c.end();it++){
result.push_back(fast_pow_mod(*it,d,n));
}
return result;
}

//测试
void RSA(){
cout<<"请输入明文:"<<endl;
string message;
getline(cin,message);
vector<int> c= RSA_encrypt(message,E,N);
vector<int>::iterator it;
cout<<"加密后密文:"<<endl;
for (it = c.begin();it!=c.end(); ++it) {
cout<<*it<<" ";
}
cout<<endl<<"解密后的明文:"<<endl;
vector<int> m = RSA_decrypt(c,mod_inverse(E,(P-1)*(Q-1)),N);
for (it = m.begin(); it !=m.end() ; ++it) {
printf("%c",*it);
}
}

这里写图片描述