RSA算法原理（一）：数学知识
# 40.RSA算法原理（一）：数学知识
在学习RSA算法原理之前，读者应该有一些基本的数学知识，这里介绍下模运算、质因数和欧拉函数。以下情况如无特别说明，假设讨论的数字都是正整数
# 余数和取模
取模运算是求两个数相除的余数。例如，7÷3 = 2 .... 1，也就是商等于2，余数为1。我们也可以称之为7对3取模，可以写作：7 mod 3 = 1。一般公式：a mod b=c，指的是 a ÷ b 的余数为 c。
由于模运算的英文是Modular Arithmetic，我们常用 mod 表示取模运算符，也叫求余运算符。在编程语言中，经常使用百分号%作为取模运算符。
有时候我们还会见到一个公式：a ≡ b (mod c)，这个公式的意思是说，a 和 b 分别对 c 取模，余数是相同的，也读作 a 与 b 同余，mod为c ，“≡”是数论中表示同余的符号。例如：7 ≡ 1（mod 3），指的是 7 和 1 分别对3取余，余数是相同的。
由于取模其实就是取余数，因此有这样的规律：
设 x mod y = n，则存在一个整数k，使得ky + n = x。
这应该不难理解，x mod y 其实就是 x ÷ y，那么结果就是k（商），余数为 n，也就是 x ÷ y = k.... n
其实我们生活中就有用到取模的例子。
- 假设现在是上午10点，同事约你说7小时后吃饭，也就是17点，那么其实也就是下午5点（17 mod 12 = 5）。在一些钟表里，只有1 ~ 12 的数字，可以认为超过12的会自动做取模运算
- 若12月1号是周一，很容易就知道12月8号、15号、22号、29号也是周一。
同时，我们可以推导出以下规律：
- 自反性：a≡a（mod m）。
- 对称性：若a≡b（mod m）, 则 b ≡ a（mod m）。
- 传递性： 若a≡b（mod m)，b≡c（mod m）, 则a≡c（mod m）。
此外，模运算的加减乘除，和基本的四则运算类似：
- 加法：(a + b) mod p = (a mod p + b mod p) mod p
- 减法：(a - b) mod p = (a mod p - b mod p ) mod p
- 乘法：(a * b) mod p = (a mod p * b mod p) mod p
- 幂运算：(a^b^) mod p = ((a mod p)^b^) mod p （这个幂运算的规律后续会经常用到）
另外还有一个公式要了解：（其实就是幂运算的一种情况）
a^xy^ mod p = （（a^x^ mod p）^y^ ）mod p 证明如下：
a^xy^ mod p =（a^x^ * a^x^ .... * a^x^）mod p （注：y个a^x^相乘等于 a^xy ^）。
= （a^x^ mod p * a^x^ mod p.... * a^x ^mod p ）mod p（根据乘法规律可得）
= ( (a^x^ mod p )^y^ ) mod p （ y个 a^x ^mod p 相乘，也就是(a^x^ mod p )^y^）
还有一个公式知道即可：若 a ≡ b（mod m），则 （a - b）mod m = 0。这个很好推导：
- 假设a mod m 的余数是 y，则 a mod m = y； 另外，b mod m 也等于 y
- 假设 a = km + y （k是正整数），b = zm + y （z 也是整数）
- 那么 a - b = （km + y ）- （zm + y） = （k - z）m，这个数 mod m，余数当然是0了。
# 取模运算的用处
在公钥加密算法中，由于公钥是对所有人公开的信息，我们需要保证数据被“公钥”加密之后，不能够被轻易地反推出来。
那什么样的算法单向计算容易，而逆向反推却非常难呢？答案是模运算（Modular Arithmetic），像计算机中的伪随机数，散列（hash）算法都是它的典型应用。
试想下面这个例子：3^3^ mod 7 的值是多少？要计算3的3次方对7取余数，很容易；算出来等于27 mod 7 = 6；
但如果是这个式子：3^x^ mod 7 = 6。已知余数是6的情况下，我们又应当如何去寻找这里的x值呢？
由于求余运算并不可逆，我们只能一个数一个数地带进去试：
3^0^ mod 7 = 1
3^1^ mod 7 = 3
3^2^ mod 7 = 2
3^3^ mod 7 = 6
3^4^ mod 7 = 4
3^5^ mod 7 = 5
但如果这里出现的是很大很大的数，例如 3^x^ mod 935654654654651616516498465178135 = 5，再逐个去尝试就不太现实了。
这也是为什么模运算被称作是单向函数，因为对于大数来说，对模运算求逆是根本不现实的。因此也常用在加密算法里，用来生成密文。
# 质数、素数、因子
加密算法中经常会用到几种特别的数字：
质数：只能被自身和 1 整除的数，就是质数，也叫素数。例如2,3,5,7,11,13,17,19......
合数：比1大但不是质数的数字，或者说能被1和自身之外的数整除的数字，例如4 = 2 × 2， 15 = 3 × 5
1和0既非质数也非合数。
因子：也叫因数，约数。设a × b =c，（a和b都是整数）则a和b就是c的因子，例如：2× 3 = 6，则2和3是6的因子；1 × 6 = 6，则1和6也是6的因子。因此6有两组因子
公因子：能同时整除几个整数的整数。例如4可以整除8，也可以整除12，那么8和12有一个公因子4；同理，24和12也有一个公因子4。公因子可能有多个。例如8和12的公因子有1,2,4
质因数：如果一个质数是某个数n的因子，我们就称这个质数为n的质因数
分解质因数：把一个合数用质因数相乘的形式表现出来，就是分解质因数。例如：
30=2×3×5，则2,3,5就是30的质因数。
12=2×2×3，则2和3都是12的质因数
分解质因数只针对合数，每个合数都可以写成几个质数相乘的形式。
# 大整数分解质因数
分解质因数，是非常非常困难的。分解没有公式，只能暴力破解（也就是一个个穷举），数字小的时候容易，当数字特别大时，只能靠计算机的计算速度了。
举例来说，你可以对30做质因数分解，也可以对3233进行质因数分解（61×53），但是如果让你对下面这个整数进行质因数分解呢？：
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
这里直接说答案吧，上面的整数是如下两个质数的乘积：
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
×
36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
比它更大的整数分解，还没有被成功过（至少没有被报到过），因此目前被破解的最长RSA密钥就是768位。事实上，这大概是人类已经分解的最大整数（232个十进制位，768个二进制位）。
质因数分解被认为是指数级增长类型的问题（随着数字的增大，难度指数级增长）。所以，在加密算法里，就是依靠这个特点来保证破解密钥是非常困难的，实际应用中，RSA密钥一般是1024个二进制位，重要场合则为2048位，基本不可能被分解成功，因此也破解不了。
假如有人找到一种快速因数分解的算法，那么可能目前的加密体系得颠覆了，但找到这样的算法的可能性是非常小的，也不是本文的重点。
# 互质
互质：如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
由互质关系能得出以下结论：
- 1和任意一个自然数是都是互质关系，比如1和99。
- 任意两个质数构成互质关系，比如7和61。
- 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
- p是大于1的整数，则p和p-1构成互质关系，比如57和56。
- p是大于1的奇数，则p和p-2构成互质关系，比如17和15。
# 欧拉函数
思考一个问题：任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）
有一个计算这个数量的函数，称为欧拉函数。以φ(n)表示（φ是希腊字母，读音/fai/）。例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。
φ(n) 的计算方法并不复杂，我们分以下情况讨论，最后再得出通用的公式：
如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
如果n是质数的某一个次方，即 n = p^k^（p是质数，k是大于或等于1的整数），则φ(p^k^) = p^k ^- p^k-1^。比如 φ(8) = φ (2^3^) =2^3^ - 2^2^ = 8 - 4 = 4。怎么推导的呢？
首先，p是质数，而n是p的某一个次方；那么1×p、2×p、3×p....p^(k-1)^×p，这几个数都和n有一个共同的公因子p， 把它们减去，剩下的就是与n互质的数。可以看出，上面的第二种情况是 k=1 时的特例。
这个公式也可以写成：φ(p^k^) = p^k ^- p^k-1 ^= p^k^（1-1/p）
如果n可以分解成两个互质的整数之积，n = p1 × p2，则φ(n) = φ(p1p2) = φ(p1)φ(p2)。即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。原理涉及到中国剩余定理，这里不展开了，毕竟本文是计算机系列，不是数学系列 （主要是因为笔者也看不懂了🙁）
我们来总结下通用的公式是怎么得出的：
- 任意一个大于1的正整数，都可以写成一系列质数的积（合数可以质因数分解，质数的话则是1×本身）：n = p~1~^k1 ^p~2~^k2^p~3~^k3^......p~r~^kr^
- 根据第4种情况，可以得出：φ (n) =φ (p~1~^k1^) × φ (p~2~^k^) × ...... × φ (p~r~^kr^)
- 根据第3种情况，可以得到φ (n) = p~1~^k1 ^p~2~^k2^p~3~^k3^......p~r~^kr^（1-1/p~1~）（1-1/p~2~）...（1-1/pr）
- 也就是等于φ (n) = n （1-1/p~1~）×（1-1/p~2~）× ... ×（1-1/pr）。这就是通用公式
我们来测试下这个公式：
- φ(8) = φ(2^3^) = 8 × （1 - 1/2） = 4
- φ(1323) = φ ( 3^3^ × 7^2^) = 1323 ×（1-1/3 ）× (1 - 1/7） =756
- 其他的就不一一计算了
以上规律理解即可，不用死记硬背，知道有这个公式即可。
需要注意的是，即使有了这个公式，也并不是说求欧拉函数是一件很容易的事情，因为本身质因数分解是非常困难的。之前我们假设n = p~1~^k1 ^p~2~^k2^p~3~^k3^......p~r~^kr^，如果不知道p~1~^k1^，p~2~^k2^....p~r~^kr^分别是多少，还是很难计算出来欧拉函数的值的。
# 欧拉定理
欧拉函数的用处，在于欧拉定理：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
a^ φ (n) ^= 1 （mod n）
也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。
欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。
欧拉定理可以大大简化某些运算。比如，7和10互质，根据欧拉定理，7^ φ (10) ^= 1 （mod 10），已知φ(10)=φ( 2 × 5) = φ( 2 ) × φ(5) = 1 × 4，所以马上得到7的4倍数次方的个位数肯定是1。因此，7的任意次方的个位数，能很快就算出来（不用算出整个数是多少）。
欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。
这里说一个欧拉定理的特例，假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成 a^ p-1 ^= 1 （mod p），这就是著名的费马小定理。
# 模反元素
最后一个知识点：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1，公式：ab ≡ 1 （mod n）。这时，b就叫做a的"模反元素"。
比如，3和11互质，那么3的模反元素就是4，因为 ( 3 × 4 ) -1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。
欧拉定理可以用来证明模反元素必然存在：a^ φ (n) ^= a × a^ φ (n) -1^ ≡ 1（mod n） ，我们设 a^ φ (n) -1^=b，也就是 ab ≡ 1（mod n）
可以看到，b，也就是a的 φ(n)-1 次方，就是a的模反元素。
# 课后习题
- 举一个生活中取模的例子
- 理解什么是质数、合数和质因数，并尝试质因数分解28
- 理解什么是欧拉函数，并计算28的欧拉函数值
- 理解什么是欧拉定理，并计验证 7^ φ (20) ^= 1 （mod 20）
- 理解什么是模反元素
在往下看答案之前，请先自己计算一遍
# 课后答案
- 数字28 = 2 × 14 = 2 × 2 × 7，28这个数字很小，可以人肉眼看出质因数
- φ(28) = φ(2) × φ(2) × φ(7) = 1 × 1 × 6 = 6。首先是质因数分解，然后计算乘积即可
- φ(20) = φ(2) × φ(2) × φ(5) = 1 × 1 × 4 = 4，而7^4^ = 2401，2401 mod 20 =1. （目前数字都比较小，可以通过电脑自带的计算器运算）
