RSA 加密周边

主要参考: 饮水思源, 阮一峰, 以及自由意志的公开课.

RSA加密算法使得加密简单, 但解密困难. 就像向存钱罐中存钱容易, 取钱困难. 其中之所以困难在于加密解密双方不对称, 如对称的有DES(被人怀疑有后门). 加密所用公钥是$(n, e)$, 解密所用密钥是$(n, d)$, 其中$ed ≡ 1 (mod\ \psi(n))$. $\psi(n)$是Euler函数, 即不超过$n$的与之互质的数的个数. 公钥是公开的, 密钥只有解密者持有.

将信息$m$加密解密过程如下:

1. $m^e = c  (mod~ n)$ (*加密*)

2. $c^d = m  (mod~ n)$ (*解密*)

而在只有公钥$(n, e)$的基础上想解密则需要获得密钥, 即获得$d$. 然而这将涉及$n$因子分解, 尤其大整数的因子分解.

下面从数学的角度谈论这件事情.

首先随机产生两个不相等的素数$p, q$并取$n = pq$. 由Euler函数的乘积性质可知$\psi(n) = \psi(p)\psi(q)$. 而后随机选取和$\psi(n)$互质的一个整数$e$并得到一个$d$. 从而就得到了公钥$(n, e)$和密钥$(n, d)$. 下面证明加密之后的解密过程恰好解密. 即证$m^{ed} = m (mod~n)$. $m^{ed}=m^{1+k\psi(n)}=m*m^{\psi(n)} (mod~n)$, 而$m^{\psi(n)}=1 (mod~n)$(Euler定理), 故而.

下面证明Euler定理. 一般的证明中会用到所有与$n$互質的同余类构成一个群的性质, 也就是说, 设$\left\{ \overline{a_1}, \overline{a_2}, \cdots, \overline{a_{\varphi(n)}} \right\}$是比$n$小的正整数中所有与$n$互素的数对应的同余类组成的集合(这个集合也称为模$n$的简化剩余系).这些同余类构成一个群, 称为整数模$n$乘法群. 所以当对这些数进行变换$\pi_a: \overline{a_i} \longmapsto \overline{a \cdot a_i} = \overline{a} \cdot \overline{a_i}$的时候（$a, n$互质，从而也属于某个同余类), 变换所得的同余类集合仍然是原来的$\overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}}$. 即是说, 集合$\left\{ \overline{a_1}, \overline{a_2}, \cdots , \overline{a_{\varphi(n)}} \right\}$和$\left\{ \overline{a a_1}, \overline{a a_2}, \cdots , \overline{a a_{\varphi(n)}} \right\}$相同. 因此，$a^{\varphi(n)} a_1 a_2 \cdots a_{\varphi(n)} \equiv (a a_1)(a a_2) \cdots (a a_{\varphi(n)}) \equiv a_1 a_2 \cdots a_{\varphi(n)} \pmod n$. 从而$a^{\varphi(n)} \equiv 1 \pmod n$. 而费马小定理是$n$为素数时的Euler定理.