模运算
非对称加密解密所用到的一个非常重要的特性就是模运算不可逆
比如算 $ 3^3 \text{ } mod \text{ } 7 $ 的值， 很容易算出余数为 27 - 21 = 6
但是知道 $ 3^{\color{green}{x}} \text{ } mod \text{ } 7 = 6 $， 然后求 $x$ 的值呢，那么就只能挨个去试了，但是如果式子中的数字稍微大那么一点，比如
$$
520^{\color{green}{x}} \text{ } mod \text{ } 1011 = 721
$$
再挨个去试就很不现实了。
试想有3个数字， ${\color{green}{e}},{\color{red}{d}}, {\color{blue}{n}}$ 满足下面的条件
$$
m^{\color{green}{e}} \text{ } mod \text{ } {\color{blue}{n}} = c \\
c^{\color{red}{d}} \text{ } mod \text{ } {\color{blue}{n}} = m
$$
m 可以表示是要加密的信息，c 表示加密后的密文， 那么就可以通过这个规则对信息进行加解密了，其中
- $({\color{green}{e}}, {\color{blue}{n}})$ 用来当做 公钥
- $({\color{red}{d}}, {\color{blue}{n}})$ 用来当做 私钥
上面公式经过一些变化可以得到
$$
{m^{\color{green}{e}{\color{red}{d}}} \text{ } mod \text{ } {\color{blue}{n}} = m}
$$
如何选取这个 ${\color{green}{e}}$ 和 ${\color{red}{d}}$ 便成了非对称加密中的最关键的问题， 这就提到了欧拉定理
欧拉函数
讲欧拉定理前，先说下什么是欧拉函数
对于正整数N, 欧兰函数 $\phi(n)$ 的值等于从 1 到 N 中与 N 互质的数的个数
互质: 如果两个整数它们的最大公约数为 1， 则这两个数互质。
比如
| 正整数 N |
与 N 互质的数 |
欧拉函数值 |
| 2 |
{1} |
$\phi(2)$ = 1 |
| 3 |
{1, 2} |
$\phi(3)$ = 2 |
| 4 |
{1, 3} |
$\phi(4)$ = 2 |
| 5 |
{1, 2, 3, 4} |
$\phi(5)$ = 4 |
| 6 |
{1, 5} |
$\phi(6)$ = 2 |
| 7 |
{1, 2, 3, 4, 5, 6} |
$\phi(7)$ = 6 |
对于质数来说, 小于它的数都与它互质，所以对于质数 $n$, 有 $\phi(n) = n - 1$
欧拉定理
对于互质的正整数 $m$、$n$，则 $m$ 的 $\phi{(n)}$ 次方与$1$同余，模为 $n$, 即
$$
m^{\phi(n)} \equiv 1 \text{ } (mod\text{ }{n})
$$
我们对公式进行一些简单的变换，等式两端同时取 $k$ 次幂, 即
$$
(m^{\phi(n)})^k = 1^k \text{ } (mod \text{ }n)
$$
等同于
$$
m^{k\phi(n)} = 1 \text{ } (mod \text{ }n)
$$
两端同时乘以 $m$
$$
m^{k\phi(n)} * m = 1 * m \text{ } (mod \text{ }n)
$$
再简化
$$
m^{k\phi(n)+1} = m \text{ } (mod \text{ }n)
$$
最后将模运算写在等式的左边
$$
m^{k\phi(n)+1}\text{ } mod \text{ }n = m
$$
然后和之前的加解密公式对应起来
$$
{m^{\color{green}{e}{\color{red}{d}}} \text{ } mod \text{ } {\color{blue}{n}} = m}
$$
我们可以将 ${\color{red}{d}}$ 与 ${\color{green}{e}}$ 的关系表实证下面这种形式
$$
{\color{green}{e}}{\color{red}{d}} = k\phi({\color{blue}{n}})+1
$$
即
$$
{\color{red}{d}} = \frac{k\phi({\color{blue}{n}})+1}{\color{green}{e}}
$$
我们可以通过选取这里的 $k$，$\color{blue}{n}$，$\color{green}{e}$ 来计算用于解密的密钥 $\color{red}{d}$
前面讲欧拉函数的时候我们讲到，对于互质的数，有 $\phi(n) = n - 1$ , 除此之外欧拉函数还有一个重要的特性,对于互质的 $p$ 和 $q$
$$
\phi(p * q) = \phi(p) * \phi(q)
$$
我们选取 $p=3, q=11$ 因此
$$
{\color{red}{d}} = \frac{k * 20+1}{\color{green}{e}}
$$
我们找一个与 $20$ 互斥的较小的数 $3$ 当做 $\color{green}{e}$, 然后尝试找满足等式的 ${\color{red}{d}}$，当 $k=1$的时候，存在 ${\color{red}{d}} = 7$ 满足条件，然后就可以把公钥 ${\color{green}{e}} = 3, {\color{blue}{n}} = 20$ 公布当做公钥，自己保留 ${\color{red}{d}} = 7$ 当做私钥。
至此就生成了不容易被破解非对称的密钥。