RSA加密算法

一、前言

RSA加密算法由Ron Rivest、Adi Shamir和Leonard Adleman于1977年提出，算法名字取自三位的姓氏首字母；其安全性部分依赖于大整数分解的困难。之所以说“部分依赖于”，是因为至今还没证明RSA的安全性完全依赖于大整数分解。

何为大整数分解？公开两个大素数的乘积$n=p\ast q$，分解其两个素因子$p$、$q$，即$n=p\ast q$。

二、算法详解

公钥与私钥生成

公钥与私钥生成的流程如下：

1. 随机选取两个大素数$p$、$q$，计算$n=p\ast q$；
2. 随机选取加密密钥$e$，使得$e$ 与 $(p-1)\ast (q-1)$互素；
3. 用扩展欧几里得扩展算法计算密钥$e$模$(p-1)\ast (q-1)$的逆元$d$，亦即$d=e^{-1}\mathrm{mod}((p-1)\ast (q-1))$

注意：$d$与$n$也是互素。$e$和$n$是公钥，$d$是私钥。

加密与解密

对消息$m$加密，密文$c=m^e\mathrm{mod}n$。用私钥解密密文，恢复明文$m=c^d\mathrm{mod}n$。

解密公式证明需要用到欧拉定理。首先引入欧拉函数$\varphi (n)$，表示与$n$互素的小于$n$的正整数数目（$n>1$），也称之为模$n$的余数化简集中元素的数目。如果$n$是素数，那么$\varphi (n)=n-1$；如果$n=p\ast q$ 且$p$与$q$互素，那么$\varphi (n)=(p-1)\ast (q-1)$。
欧拉定理：如果$gcd(a,n)=1$，那么$a^{\varphi (n)}\mathrm{mod}n=1$。

解密公式的证明如下：

$$\begin{array}{rl}{c}^d\mathrm{mod}n& =(m^e{)}^d\mathrm{mod}n\\ & =m^{e\ast d}\mathrm{mod}n\\ & =m^{k(p-1)(q-1)+1}\mathrm{mod}n\\ & =m\ast m^{k(p-1)(q-1)}\mathrm{mod}n\\ & =m\ast m^{k\ast \varphi (n)}\mathrm{mod}n\\ & =m\mathrm{mod}n\end{array}$$

三、参考资料

[1] R. Rivest, A . Shamir, and L. Adleman. “A method for obtaining digital signatures and public-key cryptosystems”. Communications of the ACM , vol. 21, no. 2, pp. 120–126, 1978.