算法基础-RSA公钥体系

公钥加密系统

在一个公钥加密系统中，任何人参与者都拥有独自的公钥和密钥，通常用P表示公钥，用S表示密钥，公钥用于加密，密钥用于解密。并且公钥可以公开，任何人都可以使用这个公钥发送一段密文，而只有私钥的持有者才可以用私钥解密

公钥和私钥对应的函数互为反函数

RSA公钥加密体系基于一个数论事实：把两个大质数相乘很容易，但是分解大数为两个质数的乘积很难

RSA加密

在RSA公钥加密系统中，可以通过以下过程创建一对公钥和私钥

1. 任意选取远大于信息 M 的大质数 p 和 q，且 p != q
2. 令 n = pq
3. 计算 φ = (p-1)(q-1)
4. 选取一个与 φ 互质的小奇数 e
5. 计算对模 φ 意义下的 e 的乘法逆元 d，即 ed ≡ 1 (mod φ)
6. 公开 P=(e, n)，此即为RSA公钥
7. 隐藏 S=(d, n)，此即为RSA私钥

对于明文 M，使用以下函数进行加密

对于密文 C，使用以下函数进行解密

反函数关系

根据反函数关系，可得

由于 e 和 d 是关于模 φ 的乘法逆元，所以

由于 p 和 q 远大于 M，所以 M ≢ 0(mod p)，M ≢ 0(mod q)，则

同理，可以得到以下结论

因此

由于 n 远大于 M，所以只需要对前者求余，就能得到 M 的值