对称/非对称加密
在1976年前，所有方法都是对称加密算法。
Alice想出一种可逆加密方法，把加密方法告诉Bob，Bob加密了消息把密码发给Alice，Alice根据加密方法解密。
要是别人截获了消息和加密方法，或者根据密码推测出加密方法，那么就能获得密码信息。
1976年，Diffie–Hellman_key提供了一种非堆成加密的思想。
Alice有两个密钥，公钥和私钥，把公钥告诉Bob，Bob加密了把消息把密码发给Alice，Alice用私钥解密。
非对称加密方法的好处是私钥是保存在电脑的，也就是无论别人窃取什么东西，没有私钥也无法解密。
RSA算法就是一种现在普遍使用的非对称加密算法。
RSA算法
构造过程
凭空变出两个质数$p,q$。
设$N=p\times q$
根据欧拉函数$r=\varphi(N)=(p-1)\times (q-1)$
凭空变出一个小于$r$的整数$e$使得$e$和$r$互质。
求$d$使得$ed \equiv 1 \pmod{r} $
销毁$p,q$，没有人知道$p,q$是多少。
得出$(N,e)$是公钥，$(N,d)$是私钥。
使用方法
Alice得到公钥和私钥，Alice把公钥告诉Bob，自己把私钥藏起来不告诉任何人。
Bob给Alice发消息。
加密
假设Bob的消息是$n$，密码是$c$，手上有公钥$(N,e)$
Bob将加密后的$c$发给Alice
解密
Alice得到密码c，根据私钥$(N,d)$
解密得到$n$
原理
因为$e\cdot d\equiv 1 \pmod{r}$，即$e\cdot d\equiv h\cdot r+1\pmod {N}$，其中$h$是自然数。
式子又可以写成
根据欧拉定理$a^\varphi(n)\equiv 1\pmod{n}$
安全性
假设窃取者得到了$(N,e)$以及加密后的密码$c$，没有获得Alice的私钥$d$。鉴于多次剩余并不可求，目前唯一已知的（已公布的）方法就是将$N$分解质因数。
将$N$分解质因数得到$N=pq$，然后可以得到$r=\varphi(N)=(p-1)\times (q-1)$，根据$ed\equiv 1\pmod{r}$得到$d$。
所以目前认为只要$N$够大，黑客就没办法了。目前推荐的$N$的长度至少为2048位，不然可以很快分解。
已经证明量子计算机可以在多项式时间内进行因数分解。
如果量子计算机成型，RSA算法将被淘汰。
实现细节
密钥生成
首先生成$N$，方法是用一个非常好的，而且没有被发表的方法（不会被窃取）随机生成一个看起来像质数的大数，然后用概率算法（类似Miller-Rabin）检验是否是质数。如果能通过测试，则进行精确的测试确保是一个质数。
$p$和$q$不能太靠近，而且$p-1$和$q-1$的因子不能太小。
$d$必须大。1990年有人证明$q<p<2q,d<\frac{1}{3}N^{\frac{1}{4}}$，那么很好算出$d$。
以上证明我都不知道怎么证的，但是了解一下就好。
e=2永远不能用。
算法速度
由于要求很多以及计算过程比较复杂，RSA比较慢。实际运用（如TLS）是结合了非对称加密（如RSA）和一些对称加密（AES）
密钥分配
假设Eve在Alice和Bob中间传话，把Alice告诉他的公钥独吞，告诉Bob自己的公钥，然后传递信息的时候先解密Bob的信息然后加密发给Alice，那么Alice和Bob甚至不知道有人窃取了信息。
现在人们通过一个可信的第三者来解决这一问题。即证书中心，一个可信的数字认证机构将用户的个人身份和公钥连接在一起，确定这个公钥就是Alice的而不是Eve窃取以后更改的。这个问题的前提是人们信赖第三方机构。
攻击方法
因数分解
2009年 RSA-768(768bit)被成功分解
时间攻击
Even要是知道Alicze对特定密码的加密时间以及了解Alice的硬件设备，可能可以根据加密时取模的时间计算，因为1比0花的时间要多，可以推算出$d$。