质数
大于1的自然数中，只能被1和它本身的数整除，如 2、3、5、7
互质关系：
如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系
- 1与任何数都互质
- 任意两个质数都互质
- 质数与小于它的每一个数，都构成互质关系。如5与1、2、3、4都构成互质关系
欧拉函数：
任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？计算这个值的方法就叫做欧拉函数，以符号$\phi(n)$表示
- $\phi(1)=1$
- 如果n为质数，则 $\phi(n)=n-1$
- 如果n是两个互质的整数之积 $n=p_1\times p_2$ 则 $\phi(n)=\phi(p_1)\times \phi(p_2)$
欧拉定理：
如果两个正整数a和n互质，则下面的公式成立：
$$
a^{\phi(n)} \equiv 1 \pmod n
$$
模反元素：
如果两个正整数a和n互质，那么一定可以找到b，使得下面的公式成立：
$$
ab\equiv1\pmod n
$$
证明模反元素必然存在，把欧拉定理拆开，$a\times a^{\phi(n)-1} \equiv 1 \pmod n$,
$a^{\phi(n)-1} + kn$ 全都是模反元素
随机选择两个不相等的质数p和q (越大越好)
计算p和q的乘积 $n=p\times q$
计算n的欧拉函数 $\phi(n)=(p-1)(q-1)$
随机选择一个整数e, $1<e<\phi(n) 且 e与\phi(n)互质$
计算e对于$\phi(n)$的模反元素d（知道e和$\phi(n)$就可以计算出模反元素，使用扩展欧几里德算法）
公布(n,e)为公钥、(n,d)为私钥
加密：公钥(n,e)
加密信息为m, m必须是整数，且m必须小于n
加密就是算出下面式子中的c:
$$
m^e\equiv c \pmod n
$$
即密文 $c=m^e\bmod n$
解密： 私钥(n,d)
下面的等式一定成立:
$$
c^d \equiv m \pmod n
$$
即明文 $m = c^d\bmod n$
$$
为什么\ \ c^d \equiv m \pmod n \ \ \ (1) \\
\because m^e\equiv c \pmod n\\
\therefore c = m^e-kn\\
c带入(1)得 \ (m^e - kn)^d \equiv m \pmod n\\
等同与\ m^{ed}\equiv m \pmod n \ \ (2)\\
(比如(a+b)^2 = a^2 + 2ab + b2，只有a得最高项不带b) \\
\because ed \equiv 1 \pmod{\phi(n)}\\
\therefore ed = h\phi(n) +1 \\
将ed带入(2)得 \ m^{h\phi(n)+1} \equiv m \pmod n \ \ \ (3)\\
$$
证明(1)就是证明（3）：
如果 m 和 n 互质
$$
由欧拉定理得\ m^{\phi(n)}\equiv 1 \pmod n \ \\
\because m\equiv m \pmod n \\
同余式相乘性质：若a≡b(mod\ n)，c≡d(mod\ n)，则ac≡bd(mod\ n)。\\
(m^{\phi(n)})^h\times m \equiv m \times1^h \pmod n \\
m^{h\phi(n)+1} \equiv m \pmod n\\
证明完成
$$
如果 m 和 n 不互质
$$
\because n = pq\ (质因子)\\\therefore 必然有\ m = kp\ 或\ m=kq\ (公因子只能是p或q)\\以\ m=kp\ 为例，k与q必然互质,因为m和n只可能有一个公因子\\kp与q也互质（m，n不互质，n失去与m唯一的公因子后肯定互质）\\根据欧拉定理\ (kp)^{q-1} \equiv 1 \pmod q \ (自己多次乘上自己，再两边同时乘kp)\\进一步得到\ [(kp)^{q-1}]^{h(p-1)} \times kp \equiv kp \pmod q\\\because ed = h\phi(n) +1 \\化简\ (kp)^{ed} \equiv kp \pmod q\\改写成\ (kp)^{ed} = kp + tq\\这时t必然能被p整除,即\ t=t'p\ (因为(kp)^{ed}一定是p的整倍数)\\(kp)^{ed} = kp+t'pq\\\because m=kp, n=pq\\\therefore m^{ed}=m+t'n\\\therefore m^{ed} \equiv m \pmod n\\证明完成
$$
https://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html