解析RSA加解密算法

By Long Luo

一、RSA 是什么?

RSA\textit{RSA} [1]公钥加密算法是1977年由Ron Rivest、Adi Shamirh和Leonard Adleman在(美国麻省理工学院)开发的。RSA\textit{RSA} 取名来自开发他们三者的名字。

RSA\textit{RSA} 算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。

二、RSA算法原理

RSA\textit{RSA} 算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个才能解密。

下面我们就详细讲解下 RSA\textit{RSA} 算法加解密过程。

2.1 RSA算法组成部分

  • 原文(Message):需要加密的信息,可以是数字、文字、视频、音频等,用 MM 表示。
  • 密文(Ciphertext):加密后得到的信息,用 CC 表示。
  • 公钥(Public Key)和私钥(Private Key):用 PUPUPRPR 表示。
  • 加密算法(Encryption):若 E(x)E(x) 为加密算法,加密过程可以理解为 C=E(M)C = E(M) 根据原文和加密算法得到密文。
  • 解密算法(Decryption):若 D(x)D(x) 为解密算法,解密过程可以理解为 M=D(C)M=D(C) 根据密文和解密算法得到原文。

2.2 RSA算法加密过程

  1. 随机选择两个不相同的素数 p,qp, q
  2. p,qp, q 相乘,记为 n=p×qn = p \times q
  3. 计算 nn 的欧拉函数 φ(n)\varphi(n)欧拉函数[2] 证明,当 p,qp, q 为不相同的素数时,φ(n)=(p1)(q1)\varphi(n) = (p-1)(q-1)
  4. 随机选择一个整数 ee,满足两个条件:φ(n)\varphi(n)ee 互质,且 1<e<φ(n)1 < e < \varphi(n)
  5. 计算 ee 对于 φ(n)\varphi(n) 的模反元素 dd,也就是说找到一个 dd 满足 ed1modφ(n)ed \equiv 1 \mod \varphi(n)。这个式子等价于 ed1=k×φ(n)ed - 1 = k \times \varphi(n),实际上就是对于方程 edk×φ(n)=1ed - k \times \varphi(n) = 1(d,k)(d,k) 的整数解。这个方程可以用扩展欧几里得算法[3]求解。
  6. 最终把 (e,n)(e,n) 封装成公钥,(d,n)(d,n) 封装成私钥。

由于理论太枯燥,我们来举个实际例子运行一遍这个算法。

  1. 随机选择两个不相同的素数 p,qp,q。我们选择 p=103,q=97p=103, q=97
  2. p,qp,q 相乘,n=103×97=9991n=103 \times 97 = 9991
  3. φ(n)=(1031)(971)=9792\varphi(n)=(103-1)(97-1)=9792
  4. 随机选择一个 e=1213e = 1213,满足 φ(n)\varphi(n)ee 互质且 1<e<φ(n)1 < e < \varphi(n)
  5. 计算 ee 对于 φ(n)\varphi(n) 的模反元素 dd,即代入方程 edk×φ(n)=1ed - k \times \varphi(n)=1 求整数解。将 e=1213,φ(n)=9792e=1213,\varphi(n)=9792 代入方程,得到 1213×d9792×k=11213 \times d - 9792 \times k = 1,很容易可以找到 (k,d)(k,d) 的一组解 k=510,d=4117k=510, d=4117
  6. 封装公钥和私钥,最终得到的公钥 (e,n)=(1213,9991)(e,n)=(1213, 9991),私钥 (d,n)=(4117,9991)(d,n)=(4117, 9991)
    至此为止,我们有了原文 MM ,公钥 (e,n)(e,n) 和私钥 (d,n)(d,n)。有了这些信息就可以开始加密和解密了。

2.2.1 加密

RSA\textit{RSA} 算法中,加密过程实际上就是利用公钥 (e,n)(e,n) 计算 C=Me(mod n)C = M^e (mod \ n)。假设原文 M=6M=6,代入上面的值,得到 C=61213(mod 9991)=7863C = 6^{1213} (mod \ 9991) = 7863
于是 C=7863C=7863,Alice就把 78637863 发给了Bob。

2.2.2 解密

Bob收到了密文 C=7863C=7863,就用自己的私钥 (d,n)=(4117,9991)(d,n)=(4117, 9991) 进行解密。RSA\textit{RSA} 证明,原文的 ee 次方对 nn 取模恒等于 ccdd 次方,即 CdMe(mod n)C^d ≡ M^e (mod \ n) 一定成立,所以 M=Cdmod nM = C^d mod \ n。代入 C,d,nC,d,n 的值,得到 M=78634117mod 9991=6M = 7863^{4117} mod \ 9991 = 6

所以Bob就从密文 CC 和私钥 (d,n)=(4117,9991)(d,n)=(4117, 9991) 知道了加密之前的原文 M=6M=6

在整个通信过程Alice只用到了公钥 (e,n)(e,n) 进行加密,Bob只用到了私钥 (d,n)(d,n) 解密,没有任何关于秘钥的传递,只有加密后的密文 CC 有可能在通信中被窃听到。

2.3 为什么RSA可以保证加密通信不被破解?

回顾上面的加密过程,我们用到了六个变量: p,q,n,φ(n),e,dp,q,n,\varphi(n),e,d,其中只有公钥 (e,n)(e,n) 是公开的。想要破解密文,只要知道私钥 (d,n)(d,n),计算 M=Cdmod nM = C^d mod \ n 就可以破解 RSA\textit{RSA} 算法。

那么,有没有可能在已知公钥 (e,n)(e,n) 的情况下,推导出私钥 (d,n)(d,n)

根据 RSA\textit{RSA} 构造的规则(见上述 RSA\textit{RSA} 加密过程1-6步),可以得到以下信息:

  1. 因为公钥中已知 nn,只要计算出 dd,就能得到私钥。

  2. ed1(modφ(n))ed ≡ 1 (mod \varphi(n)),需要知道 eeφ(n)\varphi(n) 的值来求出 dd。因为在公钥中已知 ee,所以只要求出 φ(n)\varphi(n) 的值。

  3. φ(n)=(p1)(q1)\varphi(n)=(p-1)(q-1),要求出 φ(n)\varphi(n) 的值,需要求出 p,qp,q 的值。

  4. n=p×qn=p \times q,想要求出 p,qp,q 的值,必须对 nn 做因数分解。

结论:如果 nn 可以被因数分解,dd 就可以沿着4,3,2,1步骤推出,也就意味着私钥被破解。

但是大整数的质因数分解[4],是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。

三、RSA算法代码实现

RSA\textit{RSA} 项目 源码 如下所示:

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
/********************************************************************************************
* Copyright(c) tcpipstack
* File Name : RSA.c
* Abstract Description : RSA加解密算法的简单演示
* Create Date : 2010/08/17
* Author : tcpipstack
*-------------------------Revision History--------------------------------------------------
* No Version Date Revised By Item Description
* 1 1.0 10/08/17
*
********************************************************************************************/

#include <stdio.h>
#include <math.h>

/* RSA算法中加密方公布的密钥是N和E,解密方使用N和D解密 */
#define P 5 /* P和Q必须为素数,在实际运用中通常为很大的数 */
#define Q 7

#define N (P*Q) /* add the (), or will cause the mistake */
#define Z ((P - 1)*(Q - 1))

#define E 5 /* 加密方选择E,E必须和Z只有一个公约数 */
#define D 5 /* (E * D - 1)必须能够被Z整除 */
/* 由于long int无法表示过大的数字,所以D取5 */

void main(void)
{
int i;
int TrsMsg[4] = {12, 15, 22, 5};
long en[4], de[4];
int SecCode[4], DeMsg[4];

printf("下面是一个RSA加解密算法的简单演示:\n");
printf("\t Copyright(C) Long.Luo.\n\n");
printf("报文\t加密\t 加密后密文\n");

for (i=0; i<4; i++)
{
/* s = m(E) mod N */
en[i] = (int)pow(TrsMsg[i], E);
SecCode[i] = en[i] % N;

printf("%d\t%d\t\t%d\n", TrsMsg[i], en[i], SecCode[i]);
}

printf("\n原始报文\t密文\t加密\t\t解密报文\n");
for (i=0; i<4; i++)
{
/* d = s(D) mod N */
de[i] = pow(SecCode[i], D);
DeMsg[i] = de[i] % N;

printf("%d\t\t%d\t%d\t\t%d\n", TrsMsg[i], SecCode[i], de[i], DeMsg[i]);
}

getchar();
}

输出结果如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
下面是一个RSA加解密算法的简单演示:
Copyright(C) Long.Luo.

报文 加密 加密后密文
12 248832 17
15 759375 15
22 5153632 22
5 3125 10

原始报文 密文 加密 解密报文
12 17 1419857 12
15 15 759375 15
22 22 5153632 22
5 10 100000 5

通过以上,我们就了解了 RSA\textit{RSA} 算法的原理及其实现。

参考资料


  1. Wiki: RSA algorithm ↩︎

  2. Wiki: 欧拉函数 ↩︎

  3. Wiki: 扩展欧几里得算法 ↩︎

  4. 如何深入浅出地讲解RSA密码? ↩︎