算法基础-RSA公钥体系

公钥加密系统

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

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

$$\left\{ \begin{array}{ll} M=P(S(M)) \\\\ M=S(P(M)) \end{array} \right.$$

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

RSA加密

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

1. 任意选取远大于信息$M$的大质数$p$和$q$,且$p \neq 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$,使用以下函数进行加密

$$P(M)=M^e\ mod\ n$$

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

$$S(C)=C^d\ mod\ n$$

反函数关系

根据反函数关系,可得

$$P(S(M))=S(P(M))=M^{ed}\ mod\ n$$

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

$$ed=1+k(p-1)(q-1)$$

由于$p,q >> M$,所以$M \not\equiv 0(mod\ p),M \not\equiv 0(mod\ q)$,则

$$\begin{array}{ll} M^{ed} &\equiv M(M^{p-1})^{k(q-1)} \\\\ &\equiv M((M\ mod\ p)^{p-1})^{k(q-1)} \\\\ &\equiv M(1)^{k(q-1)} \\\\ &\equiv M \end{array}$$

同理,可以得到以下结论

$$\left\{ \begin{array}{ll} M^{ed} \equiv M\ mod\ p \\\\ M^{ed} \equiv M\ mod\ q \end{array} \right.$$

因此$M^{ed}\equiv M\ mod\ n$,由于$n >> M$,所以只需要对前者求余,就能得到$M$的值