公钥加密系统
在一个公钥加密系统中，任何人参与者都拥有独自的公钥和密钥，通常用P表示公钥，用S表示密钥，公钥用于加密，密钥用于解密。并且公钥可以公开，任何人都可以使用这个公钥发送一段密文，而只有私钥的持有者才可以用私钥解密
公钥和私钥对应的函数互为反函数
RSA公钥加密体系基于一个数论事实：把两个大质数相乘很容易，但是分解大数为两个质数的乘积很难
RSA加密
在RSA公钥加密系统中，可以通过以下过程创建一对公钥和私钥
- 任意选取远大于信息 M 的大质数 p 和 q，且 p != q
- 令 n = pq
- 计算 φ = (p-1)(q-1)
- 选取一个与 φ 互质的小奇数 e
- 计算对模 φ 意义下的 e 的乘法逆元 d，即 ed ≡ 1 (mod φ)
- 公开 P=(e, n)，此即为RSA公钥
- 隐藏 S=(d, n)，此即为RSA私钥
对于明文 M，使用以下函数进行加密
对于密文 C，使用以下函数进行解密
反函数关系
根据反函数关系，可得
由于 e 和 d 是关于模 φ 的乘法逆元，所以
由于 p 和 q 远大于 M，所以 M ≢ 0(mod p)，M ≢ 0(mod q)，则
同理，可以得到以下结论
因此
由于 n 远大于 M，所以只需要对前者求余，就能得到 M 的值
