By Long Luo
一、RSA 是什么?
RSA 公钥加密算法是1977年由Ron Rivest、Adi Shamirh和Leonard Adleman在(美国麻省理工学院)开发的。RSA 取名来自开发他们三者的名字。
RSA 算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥。
二、RSA算法原理
RSA 算法是一种非对称密码算法,所谓非对称,就是指该算法需要一对密钥,使用其中一个加密,则需要用另一个才能解密。
下面我们就详细讲解下 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算法加密过程
- 随机选择两个不相同的素数 p,q;
- 将 p,q 相乘,记为 n=p×q;
- 计算 n 的欧拉函数 φ(n) ,欧拉函数 证明,当 p,q 为不相同的素数时,φ(n)=(p−1)(q−1)。
- 随机选择一个整数 e,满足两个条件:φ(n) 与 e 互质,且 1<e<φ(n)。
- 计算 e 对于 φ(n) 的模反元素 d,也就是说找到一个 d 满足 ed≡1modφ(n)。这个式子等价于 ed−1=k×φ(n),实际上就是对于方程 ed−k×φ(n)=1 求 (d,k) 的整数解。这个方程可以用扩展欧几里得算法求解。
- 最终把 (e,n) 封装成公钥,(d,n) 封装成私钥。
由于理论太枯燥,我们来举个实际例子运行一遍这个算法。
- 随机选择两个不相同的素数 p,q。我们选择 p=103,q=97。
- 将 p,q 相乘,n=103×97=9991
- φ(n)=(103−1)(97−1)=9792
- 随机选择一个 e=1213,满足 φ(n) 与 e 互质且 1<e<φ(n)。
- 计算 e 对于 φ(n) 的模反元素 d,即代入方程 ed−k×φ(n)=1 求整数解。将 e=1213,φ(n)=9792 代入方程,得到 1213×d−9792×k=1,很容易可以找到 (k,d) 的一组解 k=510,d=4117。
- 封装公钥和私钥,最终得到的公钥 (e,n)=(1213,9991),私钥 (d,n)=(4117,9991)。
至此为止,我们有了原文 M ,公钥 (e,n) 和私钥 (d,n)。有了这些信息就可以开始加密和解密了。
2.2.1 加密
在 RSA 算法中,加密过程实际上就是利用公钥 (e,n) 计算 C=Me(mod n)。假设原文 M=6,代入上面的值,得到 C=61213(mod 9991)=7863。
于是 C=7863,Alice就把 7863 发给了Bob。
2.2.2 解密
Bob收到了密文 C=7863,就用自己的私钥 (d,n)=(4117,9991) 进行解密。RSA 证明,原文的 e 次方对 n 取模恒等于 c 的 d 次方,即 Cd≡Me(mod n) 一定成立,所以 M=Cdmod n。代入 C,d,n 的值,得到 M=78634117mod 9991=6。
所以Bob就从密文 C 和私钥 (d,n)=(4117,9991) 知道了加密之前的原文 M=6。
在整个通信过程Alice只用到了公钥 (e,n) 进行加密,Bob只用到了私钥 (d,n) 解密,没有任何关于秘钥的传递,只有加密后的密文 C 有可能在通信中被窃听到。
2.3 为什么RSA可以保证加密通信不被破解?
回顾上面的加密过程,我们用到了六个变量: p,q,n,φ(n),e,d,其中只有公钥 (e,n) 是公开的。想要破解密文,只要知道私钥 (d,n),计算 M=Cdmod n 就可以破解 RSA 算法。
那么,有没有可能在已知公钥 (e,n) 的情况下,推导出私钥 (d,n)?
根据 RSA 构造的规则(见上述 RSA 加密过程1-6步),可以得到以下信息:
-
因为公钥中已知 n,只要计算出 d,就能得到私钥。
-
ed≡1(modφ(n)),需要知道 e 和 φ(n) 的值来求出 d。因为在公钥中已知 e,所以只要求出 φ(n) 的值。
-
φ(n)=(p−1)(q−1),要求出 φ(n) 的值,需要求出 p,q 的值。
-
n=p×q,想要求出 p,q 的值,必须对 n 做因数分解。
结论:如果 n 可以被因数分解,d 就可以沿着4,3,2,1步骤推出,也就意味着私钥被破解。
但是大整数的质因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。
三、RSA算法代码实现
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
|
#include <stdio.h> #include <math.h>
#define P 5 #define Q 7
#define N (P*Q) #define Z ((P - 1)*(Q - 1))
#define E 5 #define 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++) { 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++) { 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 算法的原理及其实现。
参考资料