RSA
数学理论基础
互质关系
欧拉函数
欧拉定理
费马小定理（欧拉定理的特例）
加解密准备
- 任意选取两个不同的大素数p和q计算乘积n,n的长度就是密钥长度,3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
- 计算n的欧拉函数φ(n)。
根据公式：φ(n) = (p-1)(q-1) - 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
- 计算e对于φ(n)的模反元素d。 ed mod φ(n) ≡ 1
- 将n和e封装成公钥，n和d封装成私钥。
加密和解密
（1）加密要用公钥 (n,e)
假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
所谓”加密”，就是算出下式的c：
me(上标) ≡ c (mod n)
（2）解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的c以后，就用自己的私钥(n,d) 进行解密。可以证明，下面的等式一定成立：
cd(上标) ≡ m (mod n)
也就是说，c的d次方除以n的余数为m。