RSA是一种非对称加密算法，是以三位发明者（Ron Rivest、Adi Shamir、Leonard Adleman）的last name的首字母组成的。（来自：维基百科，RSA加密算法）
目前RSA被广泛使用，尤其在web server的密钥、SSH等领域。因其应用广泛，所以值得学习一下。我主要用一个简单的例子来解释RSA的运行原理，以及怎么（理论上）破解它。
但是讲解之前还是要强调，大家都在用并不代表就是安全的。抛去各种因素不考虑，单是计算机计算能力的快速提升就让RSA加密算法越来越不安全了。看完大家就有大概的了解了。
概念解释（来自：维基百科，RSA加密算法）
公钥与私钥的产生
- 随意选择两个大的素数$p$和$q$，$p$不等于$q$，计算$N=pq$。
- $r =(p-1)(q-1)$
- 选择一个小于$r$的整数$e$，使$e$与$r$互质。
- 求得$e$关于$r$的模逆元，命名为$d$（既$(e \times d)\ \ mod\ \ 1 = r$）
- 将$p$和$q$的记录销毁。
- $(N,e)$是公钥，$(N,d)$是私钥。Alice将她的公钥$(N,e)$传给Bob，而将她的私钥$(N,d)$藏起来。
加密消息
$密文 = 明文^e\ mod\ \ N\ $
解密消息
$明文 = 密文^d\ mod\ \ N$
签名
签名过程其实就是用私钥加密，公钥解密的过程，因为公钥智能解密对应私钥加密的消息，而私钥（理论上）不会被泄露，所以能够确定就是拥有私钥的人签的名。
例子
假设Alice想要通过一个不可靠的媒体接收Bob的一条私密消息，假设这个私密消息是99（如果像发送其他格式的消息，也需要转化为整数才行，这是不难的），那么详细过程如下：
- 生成共私钥：
- 选择两个素数11和17，那么$N = 11 \times 17 = 187$
- $r = (11 -1) \times (17 -1) = 160$
- 找到一个与$r$互质的整数$e = 3$
- 由$( 3 \times d)\ mod\ \ 1 = 160$的$d$可为107。
- 将$N = 187$和$e = 3$作为公钥发给Bob，自己保留$N=187$和$d = 107$
- 加密消息
- Bob想要发送私密消息99
- $密文 = 99^e\ mod\ \ N = 99^3\ mod\ \ 187 = 143$
- 将密文143发送给Alice
- 解密消息
- Alice拿到密文143
- $明文 = 143^d\ mod\ \ N = 143^{107}\ mod\ \ 187 = 99$
- 这样Alice拿到了私密消息99
破解RSA
从上面加解密的过程可以意识到开始时选择的两个素数的重要性。
拥有公钥（$N$和$e$）再算出开始时使用的两个素数，很容易就可以算出私钥：
$$
私钥d = ((11 - 1) \times (17 - 1) \times n + 1) \div e\
= (160 \times n + 1) \div 3\
= (160 \times 2 + 1) \div 3\
= 107
$$
其中$n$为正整数。
所以将N分解为两个素数就等同于破解了密码，好在大素数分解目前还没有多项式时间算法，只能用暴力法试。但是只要算力和时间足够，这并没有想象中的困难，而且密钥生成的过程中有很多因素会削弱密钥的安全性。想具体了解，大家可以看 trailofbits 的博客 Seriously, stop using RSA