RSA加密算法原理

RSA 是目前使用最广泛的非对称加密密码算法，也称为公钥密码算法。它的名字是由它的三位开发者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的 first name 的首字母组成的。

P.S.

对称密码是指在加密和解密时使用同一密钥的方式。

非对称加密则是指在加密和解密时使用不同密钥的方式。

1.RSA 加密

在 RSA 中，明文、密钥和密文都是数字，RSA的加密过程可以用下列公式来表达

密文=明文EmodN

对代表明文的数字 E 次方后再对其用 N 求余，就得到了用RSA加密后的密文。

2.RSA 解密

RSA 解密和加密过程一样简单

明文=密文DmodN

将加密后的密文求 D 次方后再用 N 求余，就得到了原来的明文。

简单来说就是 E和N的组合就是公钥，D和N的组合就是私钥

Name Description

公钥 数E 和 数N

私钥 数D 和 数N

加密 密文=明文EmodN

(明文的 E 次方除以 N 的余数)

解密 明文=密文DmodN

(密文的 D 次方除以 N 的余数)

那么，我们该如何计算 E、D、N 三个数字呢？

3. 生成密钥对

生成顺序：N、E、D

3.1

N=p∗q

 ( p、q 为两个很大很大的质数)

中间过程

L=lcm(q−1,p−1)

 (L 是 p - 1, q - 1的最小公倍数)

3.2

1<E<L

gcd(E,L)=1

 (E 和 L 互质)

3.3

1<D<L

E∗DmodL=1

总的来说就是

Name Description

(1)求 N 用伪随机数生成质数 p、q, N = p * q

(2)求 L L = lcm(p-1, q-1)，L是q-1,p-1的最小公倍数

(3)求 E 1 < E < L, gcd(E, L)=1, E、L互质

(4)求 D 1 < D < L, E * d mod L = 1