RSA算法的工作流程
1. 生成公钥私钥
生成两个素数p和q，计算n=p*q，计算φ(n)=n-p-q+1，然后生成e与d，使 e * d = 1 mod φ(n)。
然后以(n, e)作为公钥，(n,d)作为私钥，其他的p,q,φ(n)可以舍弃。
2. 加密
明文为c
密文r = ce mod n
解密
密文为r
明文c = rd mod n
3. 证明
将加密的结果代入解密公式中，可以得到 rd mod n = (ce mod n)d mod n = ced mod n = ck*φ(n)+1 mod n = (cφ(n))k * c mod n
现在需要分情况讨论
a. c与n互质，那么根据欧拉公式可以知道：cφ(n) =1 mod n，所以 (cφ(n))k * c mod n = c，得证
b. c不与n互质，那么c=mq或者mp。假定c = mp
此时我们需要证明 ced = c mod n，由于n=p*q，由费马小定理可以知道，此命题的充分条件是ced = c mod p && ced = c mod q
对于ced = c mod p，由于c = mp，容易知道c mod p = 0, ced mod p = 0，所以ced = c mod p得证
对于ced = c mod q，有ced mod q = ck*φ(n)+1 mod q = (cφ(n))k * c mod q = (c(q-1)*(p-1))k * c mod q = (c(q-1))(p-1)*k * c mod q = c，所以ced = c mod q得证。
于是我们证明了 ced = c mod n
但是有一点需要注意的是，此时密文r与公钥n有公约数p或者q，攻击者可以非常轻易的求解出私钥，这直接破坏了RSA的安全性。
好在取到这种明文的可能性极小，概率上可以忽略。
最原始的RSA（textbook RSA）：已知公钥(n,e)，我们想传递一个密钥k，那么计算ke mod n得到密文c。
但是这种RSA是不安全的，其破解方式如下：
比方说k长度为64bit，那么这个k大约有20%的可能是由两个不超过34bit大小的k1*k2组成的
那么ke mod n = (k1 * k2) e mod n = (k1e * k2e) mod n，也就是说 c / k1e = k2e in Zn
如果先构建一个表格：{c/1e,c/2e,c/3e...c/234*e}，然后假设k2的取值为0到234，检查k2e是否在上一步中构建的表格里，如果发现存在，那么立即可以知道k1与k2的值，也就知道密文k的值了
总的时间复杂度不超过240 << 264
正确使用RSA的姿势之一：PKCS1 v1.5 (public key cryptograhy standard)
比方说如果我们想要加密一个128bit的AES密钥msg，我们需要将其扩充为一个长度为2048bit的明文，其核心操作如下：
头16bit为0x0002（PKCS1 mode 2），再填充1896bit的随机值（不含0x00），再跟8bit的0x00，然后才是128bit的密钥。也就是将128bit的密钥msg扩充成了2048bit的明文p
现在我们可以将得到的明文p进行一般的RSA加密操作了，得到密文e。
接收者收到密文e后，用私钥解密，得到明文p，然后根据p的头16bit得到其模式为mode 2。然后直接取末尾的128bit，就得到了需要的密钥msg了。
对PKCS1 v1.5的攻击
SSL服务器在收到PKCS1 v1.5产生密文之后，根据解密后的明文的头16bit是否为0x0002返回结果 yes:countinue；no:error。
现在攻击者想要解密由公钥(n,e)产生的密文c
那么攻击者可以从Zn中选择r，然后计算c' = re * c = (r * KPCS1(m))e
将c'提交给服务器后可以知道，r * KPCS1(m)的头16bit是否为0x0002
如果巧妙构造r并多次提交，可以逐渐的猜测出KPCS1(m)的全文，虽然成功概率很小，但是依然是不可忽视的
攻击细节描述：原始论文，stackexchange上的问答
HTTPS社区的对抗---RFC5246
核心思想，如果接收到的密文解密之后，不是以0x0002开头的，那就假定用户发送的密钥是一段随机字符串（也就是不立即告诉用户这个密文是不合法的），让错误信息在后续的通信中抛出。
正确使用RSA的姿势之二：PKCS1 v2.0 OAEP (Optimal asymmetric encryption padding)
为什么RSA难以破解？
因为如果想从公钥推知私钥，那么需要对大整数n进行因式分解，这个是极难做到的。
目前人类能完成的最好成绩是RSA-768，它是由两个384bit长的素数相乘得到的768bit长的整数，这是在2009年底被破解的
就目前来看，2048bit的密钥长度是绝对安全的。
为了提高解密速度，在私钥中使用比较小的d（比方说n是2048bit，d是128bit）
实际上如果d的长度小于n的长度的1/4，算法是不安全的。
d的长度不能小于n/2，最好与n长度相等。但是这涉及到一个开放问题。
RSA中，推荐使用的e值为65537=216+1，这样加密就只需要计算17次乘法
RSA中，p和q不宜相距太近，现在一般认为，如果合数N的位数为n，那么|p-q|要同时满足
N的NAF(Non-Adjacent Form，非相邻形式)权重不能小于N/4