RSA加密原理

一般加密算法都是基于可逆函数来做的，这样经过原函数加密后，再使用一次逆函数就得到原文了。RSA加密也是利用了这个道理，区别在于这2个函数使用了2个不一样的参数，也就是我们熟知的公私钥。

RSA算法具体参见维基百科，如果简单描述下大致就是

1. 随机选取2个大素数, $p, q, p \not = q$

2. 计算 $n = p q$

3. 选取一个与 $\phi(n)$ 互质的奇数 $e$ 其中 $\phi(n) = (p-1)(q-1)$ 这个函数叫欧拉函数，衡量的是一个群的空间，这个群的运算当然就是模运算

4. 对模 $\phi(n)$ 计算 $e$ 的乘法逆元 $d$ 因为所有整数和模运算构成一个群，所以这个群里每个元素，都存在一个乘法逆元，即 $ed = 1 \mod \phi(n)$

5. 公钥为(e, n)，私钥为 (d, n) 公钥加密函数为 $P(M)= M^e \mod n$ 私钥解密函数为 $S(C) = C^d \mod n$

要验证RSA的正确性的话直接代入公式验算 $S(P(M)) = (M^e \mod n) ^d \mod n \\ = M^{ed} \mod n \newline ed = 1 + k(p-1)(q-1) \\ M^{ed} \equiv M \mod p \\ M^{ed} \equiv M \mod q \\ M^{ed} \equiv M \mod n$

验算的核心思想就是要得到 $M^{ed}$ 和 M 模 n 同余，上面的推导已经证明了这一点，用到了一个中国剩余定理。

如果一个攻击者想要解密一条消息，那么他需要获取到私钥（d, n)，获取n比较简单，多试几次根据概率统计规则大致能猜出来，但是要获取d就很难，因为要对n做因数分解，这个问题在理论上已经被证明是很难的。