RSA加密算法概述流程+伪代码_rsa伪代码

rsa加密算法

简介：

RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。
RSA算法是现今使用最广泛的公钥密码算法，也是号称地球上最安全的加密算法。在了解RSA算法之前，先熟悉下几个术语
根据密钥的使用方法，可以将密码分为对称密码和公钥密码
对称密码：加密和解密使用同一种密钥的方式
公钥密码：加密和解密使用不同的密码的方式，因此公钥密码通常也称为非对称密码。

一、加密算法概述

二、算法原理图解

流程图

RSA中涉及到的数论知识

质数：

又称素数，一个大于1的正整数，除了1和它自身外，不能被其他整数整除。
互质关系：
如果两个正整数，除了1以外没有其他公因子，就称这两个数是互质关系。

推论：

任意两个质数构成互质关系。
大数是质数的两个数一定是互质关系。

同余：

给定一个正整数m，若存在两个整数a和b满足a-b能被m整除，即(a-b) mod m = 0, 那么就称整数a与b对模m同余，记作 ：a≡b(mod m) , 同3时又成立：a mod m = b

欧拉函数：

• 定义： 对于给定正整数n，计算在小于等于n的正整数中，有多少个数与n构成互质关系。如：φ(8) = 4 .

推论：

• 若n可以拆成两个互质的正整数之积，如 n = p × q ，则有：φ(n) = φ(pq) = φ§φ(q)

• 对质数m ， 有：φ(m) = m-1 .

• 若n可以拆解成两个质数p和q的积，则：φ(n) = (p-1)(q-1) .

• 欧拉定理：如果两个正整数a和n互质，则n的欧拉函数φ(n)有：
  $$\phi (n)=\phi (pq)=\phi \S \phi (q)$$
  对质数m ， 有：φ(m) = m-1 .

若n可以拆解成两个质数p和q的积，则：φ(n) = (p-1)(q-1) .

欧拉定理：如果两个正整数a和n互质，则n的欧拉函数φ(n)有：
$$a\phi (n)\equiv 1(modn)$$

意味着 a的φ(n)次方被n除的余数为1.

模反元素

如果两个正整数a和n互质，则一定有整数b，使得：ab-1能被n整除，或者说ab被n整除的余数是1，记作：ab≡1(mod n)

原理：

加密过程：

1. 选取两个不同的大质数p和q，计算它们的乘积n=pq，并求出欧拉函数φ(n)=(p-1)(q-1)。

2. 选择一个小于φ(n)且与φ(n)互质的整数e作为公钥，即公钥为(n,e)。

3. 求出与e模φ(n)同余的整数d，即d*e=1 mod φ(n)，d为私钥，私钥为(n,d)。

4. 将明文M转换成整数m，使得m<n。

5. 对明文进行加密，计算密文C=m^e mod n。

6. 发送密文C。
   

解密过程：

伪代码：

// 生成公钥和私钥
int p = 61;
int q = 53;
int n = p * q;
int phi = (p - 1) * (q - 1);
int e;
do {
e = random(2, phi - 1); // 生成一个与phi互质的整数e
} while (gcd(e, phi) != 1); // 判断e与phi是否互质
int d = modInverse(e, phi);

// 加密过程
int m = 123;
int c = modPow(m, e, n); // 计算密文

// 解密过程
int m2 = modPow(c, d, n); // 计算明文

// 辅助函数
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}

int modInverse(int a, int m) {
int m0 = m;
int y = 0, x = 1;
if (m == 1) {
return 0;
}
while (a > 1) {
int q = a / m;
int t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) {
x += m0;
}
return x;
}

int modPow(int a, int b, int m) {
int res = 1;
while (b > 0) {
if ((b & 1) == 1) {
res = (res * a) % m;
}
a = (a * a) % m;
b >>= 1;
}
return res;
}
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