数学与密码的结合——RSA的数学背景

未完结

参数要求

1. p和q是质数
2. m<n
3. e<$\phi(n)$ （暂时没找到数学知识）
4. e与$\phi(n)$互质

数学支撑

答1：公钥中的n是公开的，RSA基于的数学困难问题是分解大整数，如果p和q是合数，那么有算法可以快速分解，并计算$\phi(n)$从而计算出私钥d

答2：在RSA解密中

$$m \equiv c^d \equiv m^{e\cdot d} \equiv m^{\phi(n)+1}\pmod n$$

通过拓展欧拉函数( 或者说是费马小定理 )得到m的过程中

$$m^{\phi(n)+1} \equiv m\cdot m^{\phi(n)} \equiv m \cdot 1 \pmod n = m$$

如果$m\geq n$，那么最后一步计算就会得到模去n的m，被抹去部分信息，无法正常解密。

答4：

由裴蜀定理得

$$a\cdot x+b\cdot y=\gcd(a,b)$$

特别地，若$\gcd(a,b) =1$，则存在x，y，使得$a\cdot x+b\cdot y=1$

也就是说

只有当a和b互为素数时，$a\cdot x\equiv1 \pmod b$

应用到RSA中

带入a=e，b=$\phi(n)$

有

$$e\cdot x +\phi(n)\cdot y = \gcd(e, \phi(n))$$

两边同时模上$\phi(n)$，得

$$e\cdot x \equiv \gcd(e, \phi (n)) \mod {\phi (n)}$$

当e与$\phi(n)$互素时，才会有一个整数解 d

$$d \equiv e^{-1} \mod {\phi (n)}$$

由这可知，我们可以用拓展欧几里得算法来求一个数的逆元

解密原理

$$m \equiv c^d \pmod n$$

具体见上答2，其中运用的数学原理是拓展欧拉函数。