RSA加密解密

什么是RSA

RSA是一种公钥密码算法，它的名字是由它的三位开发者，即Ron Rivest、Adi Shamir 和 Leonard Adleman的姓氏的首字母>组成的( Rivest-Shamir-Adleman )。

RSA可以被用于公钥密码和数字签名。

RSA加密

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

密文=明文^E mod N (RSA加密)

RSA的密文是对代表明文的数字的E次方求mod N的结果。换句话说，就是将 明文和自己做E次乘法,然后将其结果除以N求余数，这个余数就是密文。

加密公式中出现的两个数E和 N，到底都是什么数呢? RSA的加密是求明文的 E次方mod N，因此只要知道E和N这两个数，任何人都可以完成加密的运算。所以说，E 和 N是RSA加密的密钥，也就是说，E 和 N的组合就是公钥。

RSA解密

RSA的解密和加密一样简单，可以用下面的公式来表达:

明文=密文 ^D mod N ( RSA解密)

表示密文的数字的D次方求 mod N就可以得到明文。

这里所使用的数字N和加密时使用的数字N是相同的。数 D 和数 N 组合起来就是RSA的解密密钥，因此D和N的组合就是私钥。

在RSA中，加密和解密的形式是相同的。加密是求“明文的E次方的 mod N”，而解密则是求“密文的D次方的 mod N”。

生成密钥对

在RSA中，加密是求“明文的E次方的 mod N”，而解密则是求“密文的D次方的 mod N”。

由于E和N是公钥，D和N是私钥，因此求E、D和N这三个数就是生成密钥对。RSA密钥对的生成步骤如下：

1. 求N
2. 求L( L是仅在生成密钥对的过程中使用的数)
3. 求E
4. 求D

求N

首先准备两个很大的质数。这两个很大的质数为p和q。p和q太小的话，密码会变得容易破译，但太大的话计算时间又会变得很长。

判断一个数是不是质数并不是看它能不能分解质因数，而是通过数学上的判断方法来完成。

准备好两个很大的质数之后，我们将这两个数相乘，其结果就是数N。也就是说，数 N 可以用下列公式来表达：

N = p x q (p、q为质数)

求L

L 这个数在RSA的加密和解密过程中都不出现，它只出现在生成密钥对的过程中。

L 是 p-1 和 q-1 的最小公倍数( least common multiple, lcm )。

如果用lcm(X, Y) 来表示 “X和Y的最小公倍数”，则L可以写成下列形式。

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

求E

E是一个比1大、比L小的数。此外，E和L的最大公约数( greatest common divisor, gcd)必须为1。

如果用gcd(X, Y)来表示X和Y的最大公约数，则E和L之间存在下列关系。

1 < E < L
gcd(E,L)= 1

求D

数D是由数E计算得到的。D、E和L之间必须具备下列关系。

1 < D < L
E x D mod L = 1

举个密钥对生成的例子

• 求N

首先我们准备两个质数p、q,这里我们选择17和19,它们都是质数。

N = p x q
  = 17 x 19
  = 323

• 求L

L是p-1和q- 1的最小公倍数。

L = lcm(p-1,q-1)
  = lcm(16, 18)
  = 144

• 求E

E和L的最大公约数必须是1。

gcd(E,L)=1

满足条件的E有很多，例如下面这些数都可以。

5,7,11,13,17,19,23,25,29,31,...

这些数好像都是质数，但其实并不是这样的，比如25就不是质数。这些数称为和 L “互质的数”，也就是相对于L是质数的意思。我们选择5来作为E。

E=5, N=323 就是公钥。

• 求D

D必须满足下列条件:

E x D mod L=l

D = 29可以满足上面的条件，因为:

E x D mod L = 5 x 29 mod 144
            = 145 mod 144
            =1

我们已经成功生成了密钥对，即:

公钥: E=5 N=323 私钥: D=29 N=323

公钥(E,N)=(5,323)是可以任意公开的，但是私钥(D,N)= >(29,323)必须妥善保管。

• 加密

要加密的明文必须是小于N的数，也就是小于323的数，我们假>设要加密的明文是123，加密时使用的是公钥 E=5、N=323。

明文^E mod N = 123⁵ mod 323 = 255

因此密文就是 255。

• 解密

我们对密文225进行解密。解密时使用的是私钥D=29、N=323。

密文 ²⁹ mod N = 225²⁹ mod 323 = 123

辗转相除法

辗转相除法：辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

例如，求（319，377）：

∵ 319÷377=0（余319）

∴（319，377）=（377，319）；

∵ 377÷319=1（余58） ∴（377，319）=（319，58）；

∵ 319÷58=5（余29）

∴ （319，58）=（58，29）；

∵ 58÷29=2（余0）

∴ （58，29）= 29；

∴ （319，377）=29。