RSA数学原理

生成公私钥过程

随机选择两个大的质数p、q
由质数p和q相乘得到n， $n = p * q$
由欧拉函数求出φ(n)， $r = \varphi(n) = \varphi(p) * \varphi(q) = (p-1)* (q-1)$
随机选择与r互质的数e，通常选择65537
最后求出e关于模数r的模反元素d， $e*d\ _{mod} \ r \equiv 1 \Rightarrow e * d = k * r + 1(k=...-2,-1,0,1,2...)$

此时得到的{n，e}为公钥，{n，d}为私钥。

数学知识

互质关系

定义

如果两个正整数，除了1以外，没有其他公因子，那么这两个数就是互质关系。

欧拉函数

定义

任意给定正整数n，在小于等于n的正整数之中，有多少个与n构成互质关系（比如，在1到8之中，有多少个数与8构成互质关系）？计算这个值的方法就叫做欧拉函数，以φ(n)表示。
公式
- 如果n = 1，φ(1) = 1；
- 如果n为质数，φ(n) = n - 1；
- 如果n是a的k次幂， $\varphi \left ( n \right ) = \varphi \left ( {a^k} \right ) = a^k - a^{k-1} = (a-1)\cdot {a^{k-1}}$
- 如果m，n互质，则φ(mn) = φ(m) * φ(n)

欧拉定理

定义

若两个正整数n和m互质，则：
$m^{\varphi \left ( n \right )} \ _{mod} \ {n} \equiv 1$
即 m 的 φ(n)次方整除n的余数是1，其中φ(n)表示在小于n的正整数中与n互质的个数。

费马小定理

定义

若m是不能被质数p整除的数，则：
$m^{p-1} \ _{mod} \ {p} \equiv 1$
其实就是欧拉定理的特殊情况，由于 p 是质数，所以 φ(p) = p-1。

模反元素

定义

如果两个正整数e和r互质，那么一定可以找到整数d，使得e * d - 1被r整除，那么d就是e对于模数r的模反元素。
$e * d \ _{mod} \ r \equiv 1$

推导

由于 $1^k \equiv 1$ ，所以 $m^{\varphi(n) } \ _{mod} \ n \equiv 1 \Rightarrow m^{\varphi(n) * k } \ _{mod} \ n \equiv 1$
由于 $1 * m \equiv m$ ，所以 $m^{\varphi(n) * k } \ _{mod} \ n \equiv 1 \Rightarrow m^{\varphi(n) * k + 1 } \ _{mod} \ n \equiv m$
由模反元素的定义知道 $e * d \ _{mod} \ r\equiv 1 \ \Rightarrow e * d \equiv r * k + 1$

比较公式
$m^{\varphi(n) * k + 1 } \ _{mod} \ n \equiv m \tag{1}$
与
$e * d \equiv r * k + 1 \tag{2}$
当式1中的 $\varphi(n)$ 与式2中的 $\ r \$ 相等时，式1就变形成：
$m^{e * d} \ _{mod} \ n \equiv m \tag{3}$
将上面的式3进行拆分得到加解密的流程：
$\begin{align*} m^{e} \ _{mod} \ n \equiv c \tag{encrypt} \\ c^d \ _{mod} \ n \equiv m \tag{decrypt} \end{align*}$
其中m为要加密的数据，{n，e}为公钥，{n，d}为私钥，c为加密后的数据。