RSA加密

质数

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。

互质

互质是公约数只有1的两个整数，也可记为 $\gcd(a,b)=1$ ，叫做互质整数。

欧拉

在数论中，对正整数 $n$ ，欧拉函数 $\varphi(n)$ 是小于等于 $n$ 的正整数中与 $n$ 互质的数的数目。此函数以其首名研究者欧拉命名，它又称为 $\varphi$ 函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

来自 https://zh.wikipedia.org/wiki/欧拉函数

例如 $11$ 的欧拉函数：

比 $11$ 小且与 $11$ 互质的正整数有： $1,2,3,4,5,6,7,8,9,10$ 。

$\varphi(11)=10=11-1$

由上例子同时可知，质数的欧拉函数是它本身减 $1$ ：

$\varphi(N)=N-1$

同时欧拉函数是积性函数，即是说若 $m,n$ 互质，则

$\varphi(mn)=\varphi(m)\varphi(n)$

欧几里得算法

也叫辗转相除法，用来找出两个数的最大公约数 $\gcd(a,b)$ 。
商记作 $q_i$ ，余数记作 $r_i$ ，欧几里得算法可写为

$r_{i-1}=q_i r_i+r_{i+1}$

eg1: 寻找160, 11 的最大公约数

$r_{i-1}=q_i r_i+r_{i+1}$	商 $q_i$	余数 $r_i$
		160
		11
$160=14\times 11+6$	14	6
$11=1\times 6+5$	1	5
$6=1\times 5+1$	1	1
$5=5\times 1+0$	5	0

可得最大公约数为 $1$ ，同时因为 $\gcd(160,11)=1$ ，所以 $160,11$ 互质。

eg2: 寻找 160, 122 的最大公约数

$r_{i-1}=q_i r_i+r_{i+1}$	商 $q_i$	余数 $r_i$
		160
		122
$160=1\times 122+38$	1	38
$122=3\times 38+8$	3	8
$38=4\times 8+6$	4	6
$8=1\times 6+2$	1	2
$6=3\times 2+0$	3	0

所以最大公约数为 $2$ 。

模反元素

模逆元也称为模倒数，或者模逆元。<- 模反元素
如果两个正整数 $a$ 和 $n$ 互质，那么一定可以找到整数 $b$ ，使得 $ab-1$ 被 $n$ 整除，或者说

$ab\equiv 1\pmod n$

这时， $b$ 就叫做 $a$ 的“模反元素”。

如 $3$ 关于 $20$ 的模反元素是 $7$ ，因为

$3\times 7\equiv 1\pmod{20}$

https://zh.wikipedia.org/wiki/模反元素

拓展欧几里得算法

计算欧几里得算法时，同时多计算

$s_{i-1}=q_i s_i+s_{i+1},\quad t_{i-1}=q_i t_i+t_{i+1}$

初始分别为 $s_0=1,s_1=0$ 和 $t_0=0,t_1=1$ 。
可以寻找出满足

$ax+by=\gcd(x,y)$

的 $a,b$ ，同时还可用来求模乘逆元。

eg1: 寻找160, 11 的最大公约数

$r_{i-1}=q_i r_i+r_{i+1}$	商 $q_i$	余数 $r_i$	$s_{i-1}=q_i s_i+s_{i+1}$	$s_i$	$t_{i-1}=q_i t_i+t_{i+1}$	$t_i$
		160		1		0
		11		0		1
$160=14\times 11+6$	14	6	$1=14\times 0+1$	1	$0=14\times 1-14$	-14
$11=1\times 6+5$	1	5	$0=1\times 1-1$	-1	$1=1\times(-14)+15$	15
$6=1\times 5+1$	1	1	$1=1\times(-1)+2$	2	$-14=1\times 15-29$	-29
$5=5\times 1+0$	5	0	$-1=5\times 2-11$	11	$15=5\times(-29)+130$	130

可得

$\gcd(160,11)=1=2\times 160+(-29)\times 11=320-319$

所以：

$2$ 是 $160$ 关于 $11$ 的模乘逆元。
$131=-29+160$ 是 $11$ 关于 $160$ 的模乘逆元，因为 $-29$ 为负数，需要加上模变成正数。

欧拉定理

在数论中，欧拉定理（也称费马-欧拉定理或欧拉 $\varphi$ 函数定理）是一个关于同余的性质。欧拉定理表明，若 $n,a$ 为正整数，且 $n,a$ 互素（即 $\gcd(a,n)=1$ ），则

$a^{\varphi(n)}\equiv 1\pmod n$

即 $a^{\varphi(n)}$ 与 $1$ 在模 $n$ 下同余。欧拉定理得名于瑞士数学家莱昂哈德·欧拉。

$\gcd$ : greatest common divisor（最大公约数）

RSA

随意选择两个大的质数 $p$ 和 $q$ ，且 $p\ne q$ ，计算 $N=pq$ 。
求 $N$ 的欧拉函数， $r=\varphi(N)=\varphi(p)\varphi(q)=(p-1)(q-1)$ 。
选择一个小于 $r$ 的整数 $e$ ，使 $\gcd(e,r)=1$ 。并求得 $e$ 关于 $r$ 的模反元素，命名为 $d$ ，即 $ed\equiv 1\pmod r$ 。
$(N,e)$ 是公钥， $(N,d)$ 是私钥。
加密原文 $m$ ，得到密文 $x\equiv m^e\pmod N$ 。
解密公式为 $m\equiv x^d\pmod N$ 。
只能加密比 $N$ 小的数字，比 $N$ 大的数字无法加密。

eg：

选择两个质数3,11。

$N=3\times 11=33$

$r=\varphi(N)=\varphi(3)\varphi(11)=(3-1)(11-1)=20$

选择一个小于 $r$ 且与 $r$ 互质的整数 $e=3$ ，求得 $3$ 关于 $20$ 的模反元素 $d=7$ 。
得到公钥 $(33,3)$ ，私钥 $(33,7)$ 。

加密数字 $24$ ：

$24^3\equiv 30\pmod{33}$

获得加密后的密文 $30$ 。
对密文 $30$ 解密：

$30^7\equiv 24\pmod{33}$

获得解密后的明文 $24$ 。