解析RSA加解密算法

By Long Luo

一、RSA 是什么？

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

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

二、RSA算法原理

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

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

2.1 RSA算法组成部分

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

2.2 RSA算法加密过程

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

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

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

2.2.1 加密

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

2.2.2 解密

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

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

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

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

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

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

根据 $\textit{RSA}$ 构造的规则（见上述 $\textit{RSA}$ 加密过程1-6步），可以得到以下信息：

1. 因为公钥中已知 $n$，只要计算出 $d$，就能得到私钥。

2. $ed ≡ 1 (mod \varphi(n))$，需要知道 $e$ 和 $\varphi(n)$ 的值来求出 $d$。因为在公钥中已知 $e$，所以只要求出 $\varphi(n)$ 的值。

3. $\varphi(n)=(p-1)(q-1)$，要求出 $\varphi(n)$ 的值，需要求出 $p,q$ 的值。

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

结论：如果 $n$ 可以被因数分解，$d$ 就可以沿着4，3，2，1步骤推出，也就意味着私钥被破解。

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

三、RSA算法代码实现

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

/********************************************************************************************
*	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();
}

输出结果如下所示：

下面是一个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

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

参考资料

---

1. Wiki: RSA algorithm ↩︎

2. Wiki: 欧拉函数 ↩︎

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

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