背景
我们开发的打印系统需要一套授权工具，里面用到了rsa加密算法，之前的笔记一直没整理，最近闲着刚好整理下，方便以后查询。
rsa原理
RSA加密采用了大质数难以分解的原理来进行加密和解密。
两个随机的大质数（越大越难以破解）p，q，n=p * q，计算的n就是密钥的长度。rsa有1024，2048等长度的密钥
rsa加密有一对密钥，公钥和私钥，公钥是公开的，用来加密，私钥用来解密。私钥签名，公钥解签。
加密解密过程
1. `pow(x, e) % n = y; ` x是明文，y为加密后的密文，x的e次方模n得到y，这就是加密的过程，知道e和n就可以加密了，公钥是用来加密的所以，公钥 = （e,n）的组合
2. `pow(y, d) % n = x;` y是密文，x为明文，y的d次方模n得到x，私钥来解密，所以私钥 = (d,n)的组合
生成公钥与私钥
> 生成密钥对的过程就是求 n， n的欧拉函数φ(n)，e, d
- 求n
准备两个互质数p，q。这两个数不能太小，太小则会容易破解，将p乘以q就是N。如果互质数p和q足够大，那么根据目前的计算机技术和其他工具，至今也没能从N分解出p和q。换句话说，只要密钥长度N足够大（一般1024足矣，也可以是2048，3072，4096...），基本上不可能从公钥信息推出私钥信息。
n = p * q - n的欧拉函数φ(n)
φ(n) = (p-1)(q-1) - 求e
随机选择一个整数e，满足条件：1< e < φ(n)，且e与φ(n) 互质；实际应用中，常常选择65537 - 求d
e对于φ(n)的模反元素d，意思就是找到一个整数d，可以使得ed被φ(n)除的余数为1
即e * d = 1 (mod φ(n))等价于ed - 1 = kφ(n)实际上就是对ex + φ(n)y = 1的公式求解，用扩展欧几里德算法求解
d 必须满足 1 < d < φ(n)
举个例子
p = 13 q = 19 n = 13×19 = 247
l = (p-1) * (q-1) = 216
取e = 17 ，满足 1< e < l，且e与l 互质
求d, 17x + 216y = 1
根据扩展欧几里德算法（这个算法没看过网上炒的例子）算出一组数 (x,y)=(89,-7)，d大于1，即 d=89
假设有一个数m = 101 加密：101的17次方模247=255 解密：255的89次方模247=101。代码如下：
package main
import (
"fmt"
"math/big"
)
func main() {
n := big.NewInt(247)
e := big.NewInt(17)
d := big.NewInt(89)
m := big.NewInt(101)
//加密，Exp的第三个参数如果给上n，可以直接计算出加密后的值，不需要在调用Mod方法
var l big.Int
l.Exp(m, e, nil)
var x big.Int
x.Mod(&l, n)
fmt.Println(x.Int64())
//解密
var t big.Int
t.Exp(big.NewInt(x.Int64()), d, nil)
var y big.Int
y.Mod(&t, n)
fmt.Println(y.Int64(), y.Int64() == m.Int64())
}
rsa安全吗？
n和e是公开的，也就是已知公钥，想要破解只要知道私钥就行了，那根据上面的公式，只需要知道d就可以计算出私钥，e * d = 1 (mod φ(n))，要想得到d 就得计算出φ(n)的值，根据公式φ(n)=(p-1) * (q-1) 那其实就是求p和q，n=p*q，要求p和q就是对n做因数分解，那就是说如果n可以被因数分解，那就能破解密文。而大整数要做分解是一件很困难的事，这也证明了为什么要选择2个大整数作为p和q，越大越难以破解。
