这篇博客主要从我们小学时了解的最大公约数概念出发，一步步去了解数之间的关系，最后讲述它们是怎么被应用在密码学当中的。因为篇幅所限，再加上下文中提到的很多相关定理都需要用到离散数学的知识，所以本文中并不涉及到它们的证明，如果您对这些定理的证明感兴趣，请自行查阅相关的书籍。
最大公约数 #
我们的故事首先从最大公约数讲起，最大公约数是我们非常熟悉的内容了，如果有两个数a和b，存在一个数m，使得m能同时被a和b整除，并且不存在另外比m大且能同时被a和b整除的数，我们就称m是a和b的最大公约数，可以记为 $$ gcd(a,b) = m $$ 这个概念非常明确，如果真的给定了两个数，要去求它的最大公约数，我们也能很显然地相除一种暴力的解法。那就是让i从1到min(a,b)开始不断去判断是否满足同时被a和b整除，满足条件的最大值就是最大公约数。这种做法的时间复杂度也是很显然的，它是O(min(a/2,b/2))。这种做法在a，b都很大的时候显然不是一个值得提倡的做法，所以人们也想了很多办法去优化它，欧几里得算法就是一个很好的优化方案。
我们不妨假设a > b，则a一定可以表示为下面这种形式
$$
a = p \times b + r
$$
其中p表示a除以b的商，r表示余数。同样的b可以表示为
$$
b = q \times r + r_2
$$
其中q表示b除以r的商，$r_2$表示余数。如此往复，最终我们将会得到余数$r_i$为0的情况，这时它上面的余数就是a和b的最大公约数。我们可以从一个简单的例子来看这个算法，加入a = 64，b = 42，整个过程可以表述为下面的情况。
$$
64 = 1 \times 42 + 22
$$
$$
42 = 1 \times 22 + 20
$$
$$ 22 = 1 \times 20 + 2 $$
$$ 20 = 10 \times 2 + 0 $$
然后我们可以看出2就是它们的最大公约数，可以证明，欧几里得算法的时间复杂度为O(log(min(a,b)))。特别地，我们称gcd(a,b) = 1的情况称为a和b互素。
欧拉数 #
最大公约数作为一个简单的热身，下面我们开始了解一下欧拉数。一个数n的欧拉数ϕ(n)可以表述为整数a(1 < a < n)中满足gcd(a,n) = 1的个数。我们要找一个数的欧拉数同样也就从1开始不断去求和n的最大公约数，如果互素，那我们就让count加1，最后的count就是ϕ(n)。
这时和上面一样的问题就出现了，假如n很大，那我们总不能也去遍历吧，既然求最大公约数有更优的算法，那求欧拉数有没有呢？答案当然是肯定的。我们发现如果gcd(m1,m2) = 1，则ϕ(m1m2) = ϕ(m1) ϕ(m2)。另外设n∈Z+，对任意的正整数n，有分解式, $$ n ={p_1}^{e_1}{p_2}^{e_2}…{p_m}^{e_m} $$ 其中p1, p2,…, pm∈Z+是互不相同的素数，且e1, e2,…, em∈Z+。所以n的欧拉数ϕ(n)可以表示为 $$ ϕ(n) = n(1-1/p_1)(1-1/p_2)…(1-1/p_m) $$ 即如果我们能对一个数n做因子分解，那我们就能用上面的公式去计算它的欧拉数。同样这里我们不给出证明过程，感兴趣的读者可以自己查阅相关资料。
下面是欧拉函数的两个特例，它们本身都是正确的。
- 首先如果n本身是素数的话，那它的欧拉数ϕ(n) = n - 1;
- 如果n = pq(p和q同时都是素数)，则ϕ(n) = (p - 1)(q - 1).
欧拉定理 #
我们通过欧拉数总结出了一个定理，称为欧拉定理，它被表述为如果a和n互素，则用以a为底数，n的欧拉数作为指数的这个数和n取余数的结果为1，它的公式化表述如下： $$ 如果gcd(a,n) = 1,则 a^{ϕ(n)} ≡ 1 mod n. $$ 然后我们从上面欧拉数的两个特例中得到了欧拉定理的两个推论。
推论一(费马(Fermat)小定理)： #
特别地，当n = p，且p本身是素数时，我们称欧拉定理为费马(Fermat)小定理，即p为素数，a是整数且不能被p整除,则: $$ a^{ϕ(p)} = a^{(p-1)} ≡ 1 mod p. $$ 可以看到，上面的公式就应用到了上文中欧拉函数的特例，首先如果n本身是素数的话，那它的欧拉数ϕ(n) = n - 1。
费马小定理的一个很有用的地方在于它可以帮我们计算一个很大的数n除以p的余数，这里我们以$2^{53}$mod(11)为例进行说明。首先如果我们暴力去算$2^{53}$的值，在计算机中是没有办法存放这么大的数的，这本身就是一个问题。但是11本身是一个素数，且和2是互素的，由费马小定理我们知道$2^{10} ≡ 1 mod 11$。所以原式可以被表示为下面的形式 $$ 2^{53}mod(11) = {(2^{10})}^5 \times 2^3 mod(11) = 1^5 \times 2^3 mod(11) = 8 $$ 这样我们就能很轻松地计算出$2^{53}$mod(11)的值了。
推论二： #
欧拉定理还有一个推论，即如果n = pq(p和q同时都是素数)，则ϕ(n) = (p - 1)(q - 1). $$ a^{kϕ(n) + 1} = a^{k(p - 1)(q - 1) + 1} ≡ a mod n. $$ 但是故事到这里还不能结束，因为我们还要看看它式如何被用在密码学当中的。
RSA算法 #
RSA算法是一个非常经典的非对称加密算法，它于1977年由Ron Rivest、Adi Shamir和Len Adleman发明，1978年公布。这里我们先简单介绍一下对称加密和非对称加密。所谓对称加密，就是加密和解密都使用同一个密钥，这个很好理解，Alice将一个需要加密的文件用这个密钥加密之后发给Bob，然后Bob用同样的密钥将它解开。非对称加密是Alice和Bob各有一个公私钥对，这个公私钥对的特点是Alice用公钥加密的文件可以用Alice的私钥解开，同样用Alice的私钥加密的文件可以用Alice的公钥解开。他们都把自己的公钥公开出去，这样当Alice要给Bob发消息的时候，Alice就先用Bob的公钥给文件加密，然后Bob用自己的私钥解开。这就是非对称加密的神奇之处，我们接下来在RSA算法中可以进一步体会它的用法。
在开始RSA之前我们提一下数字签名的概念，因为Alice和Bob的公钥都是公开的，那Alice用自己的私钥对一份文件进行加密，然后将它发布出去的时候，任何人都能用她的公钥对文件进行解密，这样就起不到加密的作用了，这种作用更像是一份签名。比如Alice想说Bob的坏话，她就把它写下来，然后发到网络平台上，大家一般都不会相信这是Alice本人说的话，因为网络世界的信息并没有经过验证。但是假如Alice用自己的私钥这个文档进行加密，然后把加密前的文档和加密后的文档都发到网络中，人们用Alice的公钥对加密文档进行解密，结果对比发现解密后的文档和原文档是一致的，那基本可以认定这就是Alice本人发的。
我们还是继续回到RSA算法，通过前面的描述我们可以发现，如果我们要找一个公私钥对，能够实现公钥加密私钥解密，私钥加密公钥解密的功能还是需要很多技巧的。RSA算法就可以帮助我们生成这样一对公私钥对，公钥为{e,n},私钥为{d,n}，它的流程如下，
（1） 用户选择两个大的随机素数p, q
（2）计算n = p * q
（3）计算n的欧拉数：ø(n) = (p-1)(q-1)
（4）随机算出一个公钥e：1 < e < ø(n)，gcd(e,ø(n))=1
（5）解以下方程得到私钥d ：ed =1 mod ø(n) ，其中 0≤d≤n
（6）加密消息M得到密文C= $M^e$ mod n
（7）解密密文得到明文M = $C^d$ mod n
下面我们来看一个简单的例子，现在Bob想知道Alice每天赚多少钱，两人又怕信息被别人看到，所以Alice要把自己的工资88这个数字加密后传给Bob，首先她就需要知道Bob的公钥，我们假设Bob的一对密钥是这么生成的。
（1）假如Bob找了两个素数p=17 ， q=11
（2）然后我们计算n = pq = 17 * 11 = 187
（3）ø(n) = (p-1)(q-1) = 16 * 10 = 160
（4）随机算出一个公钥e = 7
（5）7 * d =1 mod 160 ，d = 23
现在我们得到了Bob的公钥{7,187}，私钥{23,187}。当然Bob只会把他的公钥公开，私钥是他自己保留的。
（6）现在Alice用Bob的公钥加密88这个信息得到密文C = ${88}^7$ mod 187 = 11.然后她把11发给Bob。
（7）Bob拿到之后对11进行解密，得到明文M = ${11}^{23}$ mod 187 = 88.
这就是一个简单的加解密的过程。现在我们考虑一下这样一个问题，因为Bob的公钥{7,187}是公开的，也就是说我们都知道Bob的n = 187，且e = 7。那我们是不是可以去推出Bob的私钥是多少呢？这个当然也是可以的，因为我们的n很小，如果我们将n因子分解，就很容易求出n的欧拉数ø(n) ，这时我们的安全性基本就得不到保障了。但是如果我们初始设置p和q都很大，那n就是很大的数，计算机就没法轻易做因子分解了，这也是保证RSA安全性的地方。
结语 #
至此，我们就从最大公约数出发，一步步看到了它在密码学中的应用。现在我们再来回忆一下整个旅程，首先我们从最大公约数出发定义了两个数互素的概念，然后我们定义欧拉数ø(n)就是gcd(a,n) = 1的个数，并且如果我们能够对n做因子分解的话就能很快计算出n的欧拉数。但是很明显欧拉数就是一个人为的定义，它具体有什么用呢？于是我们就发现了欧拉定理可以应用欧拉数。特别的，它的特例费马小定理可以帮助我们计算。然后我们根据大数不好做因子分解。也就是说给定一个大数，它的欧拉数并不好计算。结合这个特点和欧拉定理来设计了RSA加密算法，这是一个被广泛应用到我们生活场景中的加密算法。
Last modified on 2022-05-12