模算术与RSA

这篇文章的主要介绍RSA密码。

首先介绍RSA的流程。你可能不明所以，也不知那些数字有什么意义，其背后原理是什么。但为了明确文章的主线，有必要在开篇作简要阐述。

0 RSA流程与引入

准备步骤：

接收方找两个贼大的素数$p,q$.
求$m=pq$即其欧拉函数$\varphi(m)=(p-1)(q-1)$
任取$k\in (0,\varphi(m)]\cap\mathbb{Z}$，使得$\gcd(k,\varphi(m))=1$
解同余方程$kd\equiv 1(mod\ \varphi(m))$
公开$m,k$，自己保留$p,q,d$

通信步骤：

他人写好文本，转成数字文件后，按$m$的位数选取合适长度划分。比如gkd三个字母的ASCII码为103107100，比如取五位数字划分，那么第一份就是10310，第二份是7100…
对每个数字n进行如下操作：$n^k(mod\ m)\equiv \bar n$
将每个$n$替换成$\bar n$进行发送，传输给接收者。
接收方可以凭借手中的$p,q$把原来的$n$解出来，也就是计算$\bar n^d (mod\ m)\equiv n $。但是攻击者很难在不知道$p,q$的情况下凭借$\bar n$得到原来的$n$。这就是全过程

看完全程，应该会有如下问题：

要贼大的素数干什么，以及取贼大的素数如何可能？
欧拉函数干什么用的？
gcd是啥，怎么求？
为什么只公开$m,k$？
第六步的操作有什么用？n很大的话，计算岂不是很慢？
第八步的计算操作为何正确？
攻击者很难得到$d$吗？
这个mod是什么东西？

我们会一步步讲解，不过不是按照问题顺序来。比如问题8。

这个mod称为取模运算符，譬如除法是求得商。对于整数之间的运算，如果我们令商也为整数，那么可能多出来的余数就是取模运算符的结果。形式上表达为：

\[a=bq+r\qquad a mod b = r\]

比如$6 mod 5 = 1; 100 mod 15 = 10$。至于带括号的含义，在第二节中有所阐述。

我们先介绍一些基础知识，以及完成对问题3的解答。

1 最大公因数与线性方程

定义：对整数$a,b$，其中$a\neq0$。若$a$整除$b$，则存在整数c使得$b=a$，记作$a\mid b$。称$a$为$b$的因数。

而gcd就一个最大公因数的符号，相应地，我们也可以给出最大公因数$g$的定义：对于两个整数的任何一个公因数$m$，都有$m\mid g$。

接下来就来到第一个部分，如何求两个正整数的最大公因数。（对于负整数只需要考虑相伴，也就是差一个$\pm1$的因子）

1.1 欧几里得算法

给定两正整数$a,b$，假定b是较小的那个(当然，只是为了便于理解)

有:

\[a=q_1\times b+r_1 \\ b=q_2\times r_1+r_2 \\ r_1=q_3\times r_2+r_3 \\ ...\\ r_{n-3}=q_{n-1}\times r_{n-2}+r_{n-1} \\ r_{n-2}=q_n\times r_{n-1}+r_n \\ r_{n-1}=q_{n+1}\times r_n\]

我们对于此类带余除法的要求为余数为非负数，且小于除数。于是可以构成一个下降链$b,r_1,r_2…r_n$。最后必然在0处终止。

证明：

我们断言$r_n$就是$a，b$的最大公因数。首先证明它是公因数：

看最后一个式子，$r_n$是$r_{n-1}$的因数；再从倒数第二个式子，$r_n$是$r_{n-2}$的因数。如此往复得到$r_n$是$a,b$的因数。

对于最大公因数的证明则是反过来，如果一公因数d是a和b的因数，由第一个式子，他必然为$r_1$的因数，一路到最后一个式子。综上证毕。

----证毕----

这个算法对于计算机来说，并不是一个复杂的算法。这也就回答了问题3

1.2 线性方程

从欧几里得算法的证明过程中，我们观察证明的第一部分。可以得到：

\[r_n=r_{n-2}-q_n\times r_{n-1} = (r_{n-4}-q_{n-2}\times r_{n-3})-q_n\times (r_{n-3}-q_{n-1}\times r_{n-2})=...\]

如此往复可以证明：

给定两正整数$a,b$，存在整数$s,t$，使得 $sa+tb = gcd(a,b)$

----证毕----

从上面这个小定理的证明，我们可以得到：

给定两正整数$a,b$，我们对形如$ax+by=m$的线性方程有：

$x,y$是可解的，而且有一个固定的算法。
$gcd(a,b) \mid m$，这一点由欧几里得算法的过程保证。它是方程有解的充分必要条件

进一步，我们希望讨论所有的解，对于一般的情况，我们总可以在左右两侧同时除以某个因子化简成如下形式：

\[\bar a\bar x+\bar b\bar y=1\]

根据之前的解法，得到一组解：$(\bar x_0,\bar y_0)$。我们可以直接构造出另一组解：

\[(\bar x_0+k\bar b,\bar y_0-k\bar a),\quad k\in\mathbb{Z}\]

当然，我们也可以设出两组解，然后相减求得其中关系。

2 同余式

这一节试图回答问题2，5，6

定义： 如果对于整数$a,b,m$，有$m\mid (a-b)$，那么我们说$a$和$b$同余。记作$a\equiv b(mod\ m)$

2.1 性质

很多时候，同余式和等式十分接近。对于相加减和乘法都是一致的。但是对于除法则不一定。

若

\[a\equiv b(mod\ m) \qquad x\equiv y(mod\ m)\]

则有

\[a\pm x\equiv b\pm y(mod\ m)\qquad ax\equiv by(mod\ m)\]

2.2 解同余方程

对于同余方程，比如：

\[x+12\equiv 5(mod\ 8) \\ x\equiv 5-12\equiv -7\equiv 1(mod\ 8)\]

对于复杂一点的：

\[x^2+2x+1\equiv 2(mod\ 7)\]

毫无头绪，我们也可以试探解，从0一直到6。因为接下来在模7同余的意义下都是一致的。

我们的目的是为了求解：

\[ax\equiv c(mod\ m)\]

它有解当且仅当方程$ax-my=c$有解，这就和线性方程中讨论一致。

首先，必须有$gcd(a.m)\mid c$，否则必然无解。

其次，如果有$gcd(a,m)\mid c$，则在同余意义下，有$gcd(a,m)$个解。这一点的证明并不困难，而且与主线关系不大，所以略去。

2.3 费马小定理

费马小定理：对于素数$p$，$a$是与其互素的任意整数，则有：$a^{p-1}\equiv1(\mod p)$

费马小定理描述了有关大数的一个惊人的事实，比如$73^{100}\equiv1(mod\ 101)$。$73^{100}$有惊人的187位，而我们可以直接得到其同余的结果，这十分惊人。

接下来我们给出证明:

我们断言，对于素数$p$，$a$是与其互素的任意整数，在模p的意义下，我们有：{0,1,2,…,p-1}和{0,a,2a,3a,…,(p-1)a}内数字相同且一一对应。

或者说，后一个集合中，在模p的意义下，每个数字两两不同。如果有相同的，则存在$i，j$有：

\[ja\equiv ia(mod\ p)\]

也就是说，有$p\mid a(i-j)$。由于$gcd(a,p)=1$，则只有$p\mid (i-j)$，而$(i-j)\in[1,p-2]$。所以说必然两两不同，而在模p的意义下，两个集合必然等价。我们将两个集合内非零元相乘，约去$(p-1)!$，即可证毕。

----证毕----

2.4 欧拉公式

接下来我们介绍一个更为一般的结果：如果将费马小定理中的素数$p$换成合数$m$，那么它就不成立了。我们希望找个一个与$m$有关的函数，使下式成立：

\[a^?\equiv1(mod\ m)\]

首先，可以肯定的是：如果$gcd(a,m)>1$，显然就不成立。这由欧几里得算法的步骤保证。同时它也引导我们将目光放到那些与$m$互素的数字上去。

在$0$到$m$之间与$m$互素整数的个数是一个重要的量，我们赋予这个量一个名字，欧拉函数：

\[\varphi(m):= \# \{ a:1\le a\le m,\quad \gcd(a,m)=1\}\]

对于比较小的$m$，我们可以通过穷举得到答案，但是对于大数字，比如RSA中的$pq$，我们如何做呢？

首先，对于素数，我们已经有了很明确的答案：$\varphi(p)=p-1$。

接下来我们考虑素数幂。对于$p^k$，我们考虑p的倍数，这是容易的：

\[p，2p，3p，...，(p^{k-1}-1)p，p^k\]

利用容斥原理减去它们，我们得到$\varphi(p^k)=p^k-p^{k-1}$。这也包含了一次幂的特殊情况。

最后，我们针对合数$m=pq$，由此便可归纳地得到所有整数的欧拉函数值。

首先对小数字观察，可以猜想$\varphi(pq)=\varphi(p)\varphi(q)$。

然后我们给出证明，证明的原理是计数法，核心就是构造两个集合，它们之间有一些量的关系，通过映射给出。

对于$\varphi(pq)$，构造：${a:1\le a\le pq, \quad \gcd(a,mn)=1}$

对于$\varphi(p)\varphi(q)$，构造${(x,y):1\le x\le p,\ \gcd(x,p)=1;\quad 1\le y\le q,\ \gcd(y,q)=1}$

给出映射$f$:$a\mapsto(x=a(mod\ p),y=a(mod\ q))$。接下来只需要其为双射。

正向的证明较为容易，此处略去；反方向由中国剩余定理保证。

----证毕----

到这里，我们完成了对问题2的解释。

2.5 中国剩余定理

中国剩余定理：设$m，n$是整数，有$\gcd(m,n)=1$，$b,c$是任意整数，则同余式组： $x\equiv b(mod\ m)\quad x\equiv c(mod\ n)$ 恰有一个解$x\in[0,mn]$

证明：对于式子$x\equiv b(mod\ m)$，有方程$x=my+b$。代入第二个式子得到 $my\equiv c-b(mod n)$

由于$gcd(m,n)=1$，所以在同余意义下只有一解。（见同余式-性质最后一段）

更一般的中国剩余定理可以用归纳给出。

----证毕----

2.6 逐次平方法

这一小节回答对于$n^k(\mod m)\equiv \bar n$的计算，如何可能。

计算机这么强，对吧。这么可能做不了这种事情呢？？？

请看：

\[5^{100\ 000\ 000\ 000\ 000}(mod\ 12830603)\]

很快啊，你机智的小脑壳开始转动。欸，欧拉公式了解一下！

对于12830603这种小数字，轻轻松松嗷，有：

\[\varphi(12830603)=\varphi(3571)\varphi(3593)=12823440\]

然后一手带余除法给那个多0王看看什么叫釜底抽薪：

\[100\ 000\ 000\ 000\ 000=7798219·12823440+6546640\]

现在，计算机只需要计算：

\[5^{6546640}(mod\ 12830603)\]

很不幸的是，$ 5^{6546640}$有400多万位数字。如果不是5而是一个几百位的大数字，那么计算机也只能瑟瑟发抖了。

有没有什么办法可以不计算出幂次结果而直接给出答案呢？

这就是逐次平方法的好处。注意到同余式的性质。我们可以一点一点地乘起来。乘一次，取一次模，这样就保证了临时计算的结果总是小于模数。也就避免了对大数进行运算。但是这样的缺点是不够快。

于是我们想到平方，计算$n^2,n^4,n^8,…(mod\ m)$。为什么这样呢，因为我们可以对指数进行二进制分解，所以这样的分解是有效的。

另外，对于平方的计算是逐步进行的，也就是直接对中间结果进行平方，比如$n^2$计算出中间结果，那么它既是最终结果的一部分（如果有这一项的话），也是下一次计算的根据，据此可以直接平方计算出$(n^2)^2$。

比如：

\[7^{327}=7^{256+64+4+2+1}=298·123·695·49·7(mod\ 853)\]

这样，快速计算就成为了可能。因为计算的主要步骤就只有对各个平方值的计算，对于一个$n$位的幂指数，大概只需要$\log_2n$步。

综上，我们回答了问题5

2.7 逆运算

正向的计算如何快速进行我们已经给出。接下来我们看，怎么才能够解方程：

\[x^k\equiv b(mod\ m)\]

记忆力比较好的同学会想起我们第一次见它时，采用的方法—-那就是试探解。但这对于大整数来说不过是杯水车薪，无济于事。

接下来我们先用一个例子来介绍这种算法：

\[x^{131}\equiv 758(mod\ 1073)\]

第一步计算$\varphi(1073)=28*36=1008$

第二步求解方程：$ku-\varphi(m)v=1$也就是方程$131u-1008v=1$。换句话说，就是求$ku\equiv 1(mod \ \varphi(m))$的正整数解$u$。

用欧几里得算法可能得到负数解，不过我们可以通过调整得到正整数$u$。

本题最终可以得到$u=731$（emmmm，可能不是一个很友好的数字）

接下来就是见证奇迹的时刻了

\[758^{731}\equiv (x^{131})^{731}\equiv x^{1+1008v}\equiv x(mod\ 1073)\]

最后只需要计算$758^{731}(mod\ 1073)$即可，而这对于逐次平方法来说，小菜一碟。

上式的最后一步推导如下：

\[x^k=(b^u)^k=b^{uk}=b^{1+\varphi(m)v}=b·(b^{\varphi(m)})^v\equiv b(mod\ m)\]

这也就证明了，该方程的解为$b^u(mod\ m)$。这也就完成了，对加密解密过程的解释。也就是问题6

这种逆运算的关键一步就是在求取$\varphi(m)$，对于接收方，两个大素数自己是知道的，而对于发送方，不知道也可以加密。那么只有攻击方受伤的世界形成了。

但是嗷，很快嗷，这个攻击者就想到一个高明的手法：中间人攻击。

就是我拿我自己的$m,k$去替换你的$m,k$，然后别人用我的公钥加密，我自己解密了看，看完再用你的公钥加密回去。整个流程走完，信息到达接收方，和原来一致。当然我们也有解决方法，也就是数字签名。

3 素数分解

根据算术基本定理，任何一个大于2的整数都可以唯一地被分解成素数乘积。

这一点似乎很显然，但是如果你对群环域了解一点的话。他并没有那么显然。它只有在唯一因子分解整环中成立。但这个名字长长的环，并不是那么常见。譬如在复数域中，我们有：

\[4 = 2*2 = (3-\sqrt{5})(3+\sqrt{5})\]

这说明4在复数域中的唯一分解并不成立。不过在整数中，你想怎么分就怎么分。

另外，在整数中，大合数的分解也是十分困难的。一般来收，我们只有试除法。它的效率是相当低的。比如对于一个稍微大一点的整数9105293=37·43·59·97。

这种不超过10位数的“小数字”对计算机而言，自然不是什么难事。但是对于数$n=10^{128}+1$，如果它是素数，就需要试除$10^{64}$个可能的因数。

这又引入了两个问题：

A. 如何判断一个数是合数还是素数？

B. 如果它是合数，如何将其分解？

第一个问题远比第二个好回答。我们会在下一节谈到。

4 素性检测

终于来到最后一个问题，大素数判定如何可能？

对于大数字，用传统的方式去判别成为了一件十分困难的事情，比如：

\[m=113\ 736\ 947\ 625\ 310\ 405\ 231\ 177\ 973\ 028\ 344\ 375\ 862\ 964\ 001\]

它实际上是两个相当大的素数的乘积，它们是：

\[40\ 103\ 836\ 670\ 582\ 470\ 495\ 139\ 653*2\ 836\ 061\ 511\ 010\ 998\ 317\]

4.1 巧妙的费马小定理

对他们的计算十分繁复，但是将他们作为指数，就没有那么痛苦。根据前面所讲的逐次平方法，这种计算并没有那么困难。更何况，根据费马小定理，稍稍扩展一下就有(p是素数)：

\[a^p\equiv a(mod\ p)\]

我们只需要用逆否命题巧妙的扭转一下，通过计算得到：

\[2^m\equiv 39\ 241\ 970\ 815\ 393\ 49\ 060\ 120\ 043\ 692\ 630\ 615\ 961\ 790\ 020(mod\ m)\]

根据费马小定理的逆否命题，可以直接判定$m$不是素数。这个结论之强实在是平生罕见，你甚至都不需要进行任何的因数分解，就可以得到这个结论。

但是这离我们的目标还有一些差距。我们需要判定它是素数，而这个只能判断他不是素数。

退一步讲，即使条件：

\[a^p\equiv a(mod\ p)\]

成立，我们也没有理由推断，$p$是素数。

比如说：

\[10^{15}=10(mod\ 15)\]

但是我们知道15并不是素数。但15的确满足上式。(如果你把10换成2就可以得到15不是素数)

这时，你可以自信的说，对于$m$，我们可以选取$1\le a\le m$去一个个验证嘛。这个法子有一个显而易见的缺点，那就是计算量也挺大的。

但问题不出在这儿。而是一类极具迷惑性的数字。这个现象首先由卡米歇尔发现，满足上述条件的最小数字是$561=3·11·17$

4.2 惨绝人寰的卡米歇尔数

对于1到561间的任何整数，你都不能找到一个不符合$a^p\equiv a(mod\ p)$的整数。

类似还有：

\[1105=5·13·17\\ 1729=7·13·19\\ ...\]

也许你会觉得它们都是三个素数的乘积，但是数学嘛，不会总让你舒服。

\[62745=3·5·47·89\]

接下来我们直接给出卡米歇尔数的两个性质并证明：

肯定是个奇数
每个卡米歇尔数都是不同素数的乘积

1：取$a=m-1\equiv-1(mod\ m)$，有$a^m\equiv (-1)^m\equiv -1(mod\ m)$。这就保证了$m$必然为奇数。

2：假设$m$是卡米歇尔数，设$p$是整除$n$的素数。记$p^{e+1}$是整除$n$的最大幂方数。我们要证明$e$为0.

取$a=p^e$，则有$p^{ne}\equiv p^e(mod\ n)$。从而$n\mid (p^{ne}- p^e)$

又有$p^{e+1}\mid n$，则$p^{e+1}\mid (p^{ne}- p^e)$

这说明下面这个数是一个整数：

\[\frac{p^{ne}- p^e}{p^{e+1}}=\frac{p^{(n-1)e}-1}{p}\]

它只能是$e=0$，因为有分解$p^{(n-1)e}-1=(p-1)(p^{(n-1)e-1}+…+p+1)$。

----证毕----

固然，这两个性质具有一些巧妙的应用，但是我们的目的是为了把这个卡米歇尔数给他杀了，免得它干扰我们挑一个可人的大素数。

于是我们给出卡米歇尔数的考塞特判别法：

设$n$是合数，则$n$是卡米歇尔数当且仅当它是奇数，且对于每个整除$n$的素数$p$都有
1. $p^2\nmid n$
2. $(p-1)\mid(n-1)$

这里我们不给出证明。

4.3 素性判断

卡米歇尔数的存在说明了，我们不能仅仅依靠式$a^m\equiv a(mod\ m)$来检验素数。所以我们给出一个对素数描述更加全面一些的性质。(仍然不是充分必要条件)

设$p$是奇素数，记$p-1=2^kq，q$是奇数。
设$a$是不被$p$整除的任何数，则下述两个条件之一成立：
1. $a^q\equiv 1(mod\ p)$
2. 数$a^q,a^{2q},a^{4q}…,a^{2^{k-1}q}$之一模$p$余$-1$.

由费马小定理，我们可以保证数表中的最后一个数字：

\[a^q,a^{2q},a^{4q}...,a^{2^{k-1}q}，a^{2^kq}\]

模$p$必余1，进一步，表中每个数都是前一个数的平方，因此下述两种可能之一必成立：

表中第一个数模$p$必余1
表中某些数模$p$不余1，但它们平方后就是1，也就只能是-1了。

这就完成了对该性质的阐述。

综上，我们得到被称为拉宾-米勒测试的合数试验

合数的拉宾-米勒测试：

合数的拉宾-米勒测试：假设$n$是奇素数，记$n-1=2^kq，q$是奇数。对不被$n$整除的某个$a$，如果下述两个条件都成立，则$n$是合数：
1. $a^q \not\equiv 1(mod\ n)$
2. 对所有$i=0,1,…,k-1，a^{2^iq}\not\equiv -1(mod\ n)$

乍一看，他和我们之前用式子$a^m\equiv a(mod\ m)$来检验素数没什么不同。事实上，目前采用拉宾-米勒测试的底气来源于一下两点：

每个合数都有许多$a$来证明它的合数性(这确保没有类似的”卡米歇尔数”来捣乱)
如果$n$是奇合数，则1到n-1之间至少有75%的数字可以用来证明$n$是个合数。

所以，当我们随机选取100个$a$来进行拉宾-米勒测试，如果它们均不能证明$n$是合数。那么$n$作为合数的可能性只有大概$0.25^{100}\approx 6\times 10^{-61}$。当然，你要是十分谨慎嗷，十分谨慎，不妨使用鸽笼原理取它个25%*n+1个数。

5 重新阐述一切

接收方找两个贼大的素数$p,q$.

首先回答大素数如何可能，以及这么做的意义。

对于大素数的选取，一般就是来个200位的随机数，然后拿拉宾-米勒测试跑一部分数，万一不合格就换下一个。这样得到两个大素数。

从计算机科学的角度看，密码学的本质基于计算机理论的一个问题，也就是$P=NP$问题的猜想。一般认为是不等于的，这样对密码的加密和解密所需要的成本才会有差距。这样的话，密码学才会有其价值。RSA算法基于对大合数的分解，这是一个NP难的问题，虽然可解，但对于大合数，需要消耗庞大的资源。这也是RSA算法成功的关键。

求$m=pq$即其欧拉函数$\varphi(m)=(p-1)(q-1)$

对于已知分解的大合数和未知分解的大合数求起欧拉函数值，难度天差地别。
任取$k\in (0,\varphi(m)]\cap\mathbb{Z}$，使得$\gcd(k,\varphi(m))=1$

这一步是保证下一个同余方程可解
解同余方程$kd\equiv 1(mod\ \varphi(m))$

这一步是解密的核心，由第三步确定了其可解。同时也是解密的核心步骤，对密文的d次幂后相当于原文，这由上式的等于号和欧拉定理保证。
公开$m,k$，自己保留$p,q,d$
他人写好文本，转成数字文件后，按$m$的位数选取合适长度划分。比如gkd三个字母的ASCII码为103107100，比如取五位数字划分，那么第一份就是10310，第二份是7100…
对每个数字n进行如下操作：$n^k(mod\ m)\equiv \bar n$
将每个$n$替换成$\bar n$进行发送，传输给接收者。
接收方可以凭借手中的$p,q$把原来的$n$解出来，也就是计算$\bar n^d (mod\ m)\equiv n $。但是攻击者很难在不知道$p,q$的情况下凭借$\bar n$得到原来的$n$。这就是全过程

为什么我们能解出来了呢？ $\bar n^d\equiv n^{dk}\equiv n^{1+v\varphi(m)}\equiv n(mod\ m)$

上篇丹柯之死

下篇素数