By Long Luo
一、RSA 是什么?
\(\textit{RSA}\) 公钥加密算法是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算法加密过程
- 随机选择两个不相同的素数 \(p, q\);
- 将 \(p, q\) 相乘,记为 \(n = p \times q\);
- 计算 \(n\) 的欧拉函数 \(\varphi(n)\) ,欧拉函数 证明,当 \(p, q\) 为不相同的素数时,\(\varphi(n) = (p-1)(q-1)\)。
- 随机选择一个整数 \(e\),满足两个条件:\(\varphi(n)\) 与 \(e\) 互质,且 \(1 < e < \varphi(n)\)。
- 计算 \(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)\) 的整数解。这个方程可以用扩展欧几里得算法求解。
- 最终把 \((e,n)\) 封装成公钥,\((d,n)\) 封装成私钥。
由于理论太枯燥,我们来举个实际例子运行一遍这个算法。
- 随机选择两个不相同的素数 \(p,q\)。我们选择 \(p=103, q=97\)。
- 将 \(p,q\) 相乘,\(n=103 \times 97 = 9991\)
- \(\varphi(n)=(103-1)(97-1)=9792\)
- 随机选择一个 \(e = 1213\),满足 \(\varphi(n)\) 与 \(e\) 互质且 \(1 < e < \varphi(n)\)。
- 计算 \(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\)。
- 封装公钥和私钥,最终得到的公钥 \((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步),可以得到以下信息:
因为公钥中已知 \(n\),只要计算出 \(d\),就能得到私钥。
\(ed ≡ 1 (mod \varphi(n))\),需要知道 \(e\) 和 \(\varphi(n)\) 的值来求出 \(d\)。因为在公钥中已知 \(e\),所以只要求出 \(\varphi(n)\) 的值。
\(\varphi(n)=(p-1)(q-1)\),要求出 \(\varphi(n)\) 的值,需要求出 \(p,q\) 的值。
\(n=p \times q\),想要求出 \(p,q\) 的值,必须对 \(n\) 做因数分解。
结论:如果 \(n\) 可以被因数分解,\(d\) 就可以沿着4,3,2,1步骤推出,也就意味着私钥被破解。
但是大整数的质因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。