RSA
RSA 是一种广泛使用的非对称加密算法。非对称加密包含三个部分: 公钥和私钥的生成，使用公钥加密数据，使用私钥解密数据。
- 乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
- 甲方获取乙方的公钥，然后用它对信息加密。
- 乙方得到加密后的信息，用私钥解密。
公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。
下面用两个不相等的质数 p 和 q 来说明生成过程:
密钥的生成
Step 1: 随机选择两个不相等的质数p和q。
爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）
Step 2: 计算p和q的乘积n \(n = 61×53 = 3233\) Step 3: 计算n的欧拉函数φ(n)。
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
\(φ(n) = (p-1)(q-1) = 60 \times 52 = 3120\) Step 4: 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质
爱丽丝就在1到3120之间，随机选择了17。
从条件可以看出，如果 φ(n) 可以分解为两个整数相乘，且其中一个是 e， 那么这样的 e 就不满足要求 (不互质)。
例如，请问 e = 15 是否可以使用? \(because \ gcd(15, 3120) \ is \ not \ 1 \\ gcd(15, 3120) = 15\) 显然，e=15是不能使用的
Step 5: 计算e对于φ(n)的模反元素d。
所谓“模反元素”就是指有一个整数d，可以使得ed被 φ(n) 除的余数为1 \(d = e^{-1} \ mod \ φ(n) = 17^{-1} \ mod \ 3120 =2753\) Step 6: 将n和e封装成公钥，n和d封装成私钥。
在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。
下面就可以使用公钥和私钥进行加密通信了
加密:
加密要用公钥 (n,e)
假设鲍勃要向爱丽丝发送加密信息m，他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意，m必须是整数（字符串可以取ascii值或 unicode 值），且m必须小于n。
所谓”加密”，就是算出下式的c： \(m^e ≡ c \ (mod \ n)\) 爱丽丝的公钥是 (3233, 17)，鲍勃的m假设是65，那么可以算出下面的等式： \(e = 17, \ m = 65 \\ encryption \ = \ (m^e) \% n = (65^{17} \ \% \ 3233) \ = 2790\)
解密
解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的2790以后，就用自己的私钥(3233, 2753) 进行解密。可以证明，下面的等式一定成立： \(c^d ≡ m \ (mod \ n) \\ decryption \ = \ (c^d)\%n = (2790^{2753}) \%3233 = 65\)
