前言
最近学校开了一门mathematics for cryptography的课，主要讲了一些密码学中常用到的数学原理。CSDN上关于RSA的文章中，只看到了关于RSA算法的一些讲解，对于其涉及的数学原理并没有多少介绍，因此想写点东西与大家分享，同时也是为了自己复习和巩固。第一次写文章，可能会有一些问题和不足，希望大家能够指正。此外，这篇文章主要参考了我们老师Zülfükar Saygı（TOBB ETÜ - University of Economics & Technology）的PPT课件，《信息安全原理及应用》第三版（熊平，朱天清）以及《信息安全数学基础——算法、应用与实践》第二版（任伟）。
1.RSA简介
RSA是1977年由麻省理工学院的Ron Rivest,Adi Shamir和Leonard Adlenman提出的非对称公开密钥密码算法。其可靠性基于大数的因子分解问题。目前为止，仍未找到快速分解因子的算法，所以还没有任何可靠的攻击RSA算法的方式。只要密钥的长度足够长，用RSA加密的信息实际上是不可能破解的。因此，RSA算法已经成为目前应用最广泛的公钥密码。
RSA算法的加密过程如下：
1) 选择两个足够大素数p、q
2) 计算n=p·q Ф=(p-1)(q-1)
3) 选择一个数e，满足1<e<Ф，且gcd（e，Ф）=1
4) 计算d，使得e·d≡1 mod Ф
其中{n,e}为公钥，{n,d}为私钥。明文m加密算法为c=$m^e$ mod n，接收方解密方式为m= $c^d$ mod n。
RSA的算法并不复杂，其工作原理也有很多文章做了解释和证明。为了确保算法的可靠性，需选取足够长的密钥。本文将讲解在足够长的密钥（1024-2048位，约为$10^{300}$）的情况下，使用RSA算法运算时涉及到的数学基础，主要有Miller-Rabin检测法、费马小定理、欧拉函数与欧拉定理，中国余数定理以及模重复平方算法。
2.数论基础
RSA用到的数学原理涉及到很多数论中的概念。在此做简要说明。
2.1 整除（Divisibility）
定理：整数a和b，如果存在整数c，使得b=a·c，则b能被a整除，记做a|b。
2.2 素数（Prime）
定义：如果整数p≥2且只能被1和它本身整除，则其为素数，否则为合数（composite）。
2.3 最大公约数(Greatest Commom Divisor,gcd)
定义：a和b的最大公约数是能够同时整除a和b的最大正整数，记做gcd（a,b）
2.4 同余（Congruence theorem）
定义：设整数a,b,n(n≠0)，如果a-b是n的整数倍，即a=b+kn，k为整数，则a≡b mod n
2.5 乘法逆元（Multiplicative Inverse Elements）
定义：如果gcd（a,b）=1，那么：
1) 存在$a^{-1}$，使得a·a-1≡1 mod b，即(a·$a^{-1}$)mod b=1;
2) 存在$b^{-1}$，使得b·b-1≡1 mod a，即(b·$b^{-1}$)mod a=1。
把$a^{-1}$ 称为a模b的乘法逆元，$b^{-1}$称为b模a的乘法逆元。一般而言，如果a与n是互素的，即gcd（a，n）=1,那么a模n的乘法逆元a-1≡x mod n有唯一解；否则，a-1≡x mod n无解。
3.数学定理
3.1 Miller-Rabin检测法和费马小定理（Fermat’s Little Theorem，FLT）
在RSA算法中，n是由两个素数的乘积来确定的。由于n是公开的，为了避免攻击者用穷举法求出p和q（n=p·q），p和q应足够大。RSA目前建议的密钥长度为1024或2048位。对于一个1024位的密钥而言，p和q的大小在$10^{100}$~$10^{200}$之间。目前还没有有效的方法产生任意大小的素数，只能从期望大小的数中进行测试，直到检测到素数为止。目前常用的方法为Miller-Rabin素性检测法。Miller-Rabin检测法可以确定一个整数是合数，但不能确定其一定是素数。不过尽管如此，该算法所产生的数几乎可以肯定是素数。
3.1.1费马小定理（Fermat’s Little Theorem）
Miller-Rabin素性检测法主要是依据费马小定理和费马测试，所以先介绍费马小定理
定理：如果p是素数且gcd（a,p）=1，1≤a≤p-1，则$a^{p-1}$≡1 mod p
因此，给定需要判定素性的数n，若能找到一个整数a，使得$a^{n-1}$≠1 mod n，则n是合数。
Fermat素性测试：
输入：奇数n≥3
输出：prime/composite
Fermat（n）：{
随机选择a，2≤a≤n-2
r=$a^{n-1}$ mod n;
if r≠1 return composite；
return prime；
}
在费马测试中，如果输出是合数，则n一定是合数。若输出为素数，则有可能为素数。这是因为存在着这样的一些合数n，对于满足gcd（a,n）=1的a，均有$a^{n-1}$=1 mod n。这些数被称为Carmichael数，例如561,1105,1729,2465,2821,6601,8911……但这种数比较稀少，对费马测试的准确性准确性影响很小。研究表明，如果算法输出为prime，即通过了素性测试，则n为素数的可能性大于1-1/2，若测试了t次均为prime，则n为素数的可能性大于1-1/$2^t$。
费马小定理除了可以用在Miller-Rabin检测法中，还被用于计算乘法逆元。当 p取素数时，计算过程如下：
1) p是素数且gcd（a,p）=1
2) FLT→$a^{p-1}$≡1 mod p→a·$a^{a-2}$≡1 mod p
3) $a^{p-1}$≡$a^{p-2}$ mod p
3.1.2 Miller-Rabin检测法
在Fermat测试中，需要计算$a^{n-1}$mod n。若结果为1则输出素数，不为1则输出合数。为了简化计算过程，可以采用如下方法。对于n（n>2），若n为偶数，则n必定为合数；n为奇数，则n-1为偶数，设n-1=2t,于是$a^{n-1}$=$（a^t）^2$，如果$a^t$=±1 mod n，则直接输出素数，没有必要继续计算（因为平方后会得到$a^{n-1}$=1 mod n）。进而，如果n-1=$2^k$t(k≥0)，则
$a^{n-1}$=$(((a^t)^2)^2)^2……)^2$共k次平方
同前面的分析，如果$a^t$=±1 mod n，则必有$a^{n-1}$=1 mod n，直接输出素数；否则，在k-1次平方的过程中，有一个为-1，则$a^{n-1}$=1 mod n，输出为素数。
根据上面的分析，算法如下。
Miller-Rabin素性测试
输入：奇数n≥3
输出：prime/composite
Miller-Rabin（n）{
把n-1写成n-1=$2^k$t，随机选择整数a，1≤a≤n-1
b=$a^t$ mod n;
if b≡1 mod n return prime;
for(i=0,i<k,i++){
if b≡-1 mod n return prime;
else b=$b^2$ mod n;
}
return composite;
}
3.2 欧拉函数与欧拉定理
在AES算法中，利用Miller-Rabin检测法求得两个足够大的素数p、q，并且计算出计算n=p·q和Ф=(p-1)(q-1)。其中Ф的值为n的欧拉函数（Euler Phi）。
3.2.1欧拉函数（Euler Phi Function）
定义：小于n且与n互素的正整数的个数，记做Ф(n)，把Ф(n)称为欧拉函数。
性质：
如果n=p是素数，Ф(n)=n-1
如果n=$p^e$是素数的幂，Ф(n)=$p^e$-$p^{e-1}$
如果gcd(m,n)=1，Ф(n·m)= Ф(n) ·Ф(m)
在AES算法中，因为p和q都是素数，所以Ф(n)= (p-1)(q-1)
3.2.2欧拉定理(Euler’s Theorem)
定理：对于任意互素的整数a和n，有aФ(n) ≡1 mod n
事实上费马小定理仅是欧拉定理的一种特殊情况（n为素数），所以欧拉定理对于任意的模n都可以求解乘法逆元（用于3.4中计算私钥d）。计算过程如下：
Euler’s Theorem→$a^{Ф(n)}$≡1 mod n→a·aФ(n) ≡1 mod n
$a^{-1}$≡$a^{Ф(n)-1}$ mod n
例如，求$13^{-1}$ mod 49。
Ф(49)= Ф($7^2$)=($7^2$)-($7^1$)=42
Euler’s Theorem→$13^{42}$ ≡1 mod 49
$13^{-1}$≡$13^{42}$ mod 49
3.3 模重复平方算法（Repeated square-and-multiply algorithm）
RSA加密和解密时都需要计算模幂，欧拉定理求解逆元时也需要计算模幂。普通的求模幂的方法在幂指数特别大时耗时非常大。因此需要用模平法算法加快计算模幂的速度。在此算法中，将指数e用二进制形式表示，即e =$\sum{i=0}^k=e_i2^i$，ei等于0或1，则：
$a^e=\prod ^k{i=0}a^{e_i2_i}=(a^{2^0})^{e_0}(a^{2^1})^{e_1}\cdot \cdot \cdot (a^{2^k})^{e_k}$
例如，计算$5^{110}$ mod 131.
110=64+32+8+4+2=$(1101110)_2$
$5^2$≡ 25 mod 131 ,$5^4$≡ 101 mod 131
$5^8$≡ 114mod 131 ,$5^{16}$≡ 27 mod 131
$5^{32}$≡ 74 mod 131 ,$5^{64}$ ≡ 105 mod 131
所以$5^{110}$≡ $5^{64+32+8+4+2}$ ≡ $5^{64}$ ·$5^{32}$ ·$5^8$ ·$5^4$ ·$5^2$ ≡ 105·74·114·101·25 ≡ 60 mod 131
3.4 欧几里得算法（Euclidean Algorithm,EA）
在求得p、q、n、Ф之后，选取一整数e，使得满足1<e<Ф，且gcd（e，Ф）=1。因为任意两个随机数互素的概率约为0.6，所以这一步并不复杂。随机选择整数e，求gcd（e，Ф）并逐一判断即可。e和Ф很小时，很容易e和Ф的最大公约数gcd（e，Ф），如果e和Ф的值很大，可以采用欧几里得算法（Euclidean Algorithm,EA）。
EA算法基于以下定理，对于任意非负整数a和任意正整数b，有
gcd（a,b）=gcd(b,a mod b)
循环使用该定理，可以得到gcd(a,b) = gcd(b,r1) = ··· = gcd(rk,0) = rk。
其算法描述如下：
A←a,B←b；
若B=0，则返回A=gcd（a，b）；
R=A mod B；
A←B；
B←R；
转到2）；
例如，
gcd(91,52) = gcd(52,91−52 = 39)
= gcd(39,52−39 = 13)
= gcd(13,39−3·13 = 0) = 13.
gcd(11111,12345) = gcd(1111,12345-1111= 1234)
= gcd(1234,11111−9·1234 = 5)
= gcd(5,1234−5·246 = 4)
= gcd(4,5-4 = 1)
= gcd(1,0)
=1.
3.5扩展的欧几里得算法(Extended Euclidean Algorithm,EEA)
在求得e之后，可以计算d，使得e·d≡1 mod Ф。d为e模Ф的乘法逆元，即为e-1。因为e与Ф互素，所以e-1一定存在。使用EA算法求得gcd（e，Ф）=1，再将推导过程一步一步反推回去，可求得两个整数x，y，满足x·e+y·Ф=1→ x·e=-y·Ф+1，即x·e ≡1 mod Ф，e-1=x。即为EEA算法。
在上面的例子中，gcd（91,25）= 13，所以91、25没有逆元
gcd(11111,12345)=1，
则1=5-4=5 -（1234-5·246）=247·5-1234
=247·（11111-9·1234）-1234=247·11111-2224·1234
=247·111 1-2224·（12345-11111）=2471·11111-2224·12345
所以，11111模12345的逆元为2471，12345模11111的逆元为-2224。
至此，我们可以结合欧拉定理和Repeated square-and-multiply algorithm，或者利用EEA算法来计算任意模n的逆元。
3.6中国剩余定理（Chinese remainder theorem，CRT）
3.6.1中国剩余定理
中国剩余定理，又称孙子定理，最早见于南北朝的经典数学著作《孙子算经》中的“物不知数”问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”
这其实是求解一个一次同余式方程组，即：
x≡2 mod 3
x≡3 mod 5
x≡2 mod 7
《孙子算经》中给出了解法，但只是一个孤立的例子，南宋数学家秦九韶给出了一般性的求解方法。中国古代将这一成果统称为“孙子定理”，在外文文献中常被称为 “中国剩余定理”。它可能是最著名的由中国人给出的算法。下面给出其定理。
定理：设$m1$,$m_2$,…，$m_k$是k个两两互素的正整数，m=$\prod {i=1}^{k}mi$，$M_i$=m/$m_i$，则对于任意的整数$a_1$,$a_2$,…,$a_k$，则同余式组
x≡$a_1$ mod $m_1$
x≡$a_2$ mod $m_2$
…
x≡$a_k$ mod $m_k$
有唯一解，即x≡$\sum {i=1}^kM_iM^{-1}a_i$ mod n，其中$M_iM^{-1}$≡1 mod n。
例如韩信点兵问题，可化为同余式组
x≡1 mod 5
x≡5 mod 6
x≡4 mod 7
x≡10 mod 11
应用CRT，m=5·6·7·11=2310
$M_1$=462 $M_1^{-1}$≡3 mod 5
$M_2$=385 $M_2^{-1}$≡1 mod 6
$M_3$=330 $M_3^{-1}$≡1 mod 7
$M_4$=210 $M_4^{-1}$≡1 mod 11
x≡462·3·1+385·1·5+330·1·4+210·1·10≡6731≡2111 mod 2310
3.6.2 CRT在RSA中的应用
解密者在计算m=$c^d$ mod n的过程中，可以分别计算m=$c^d$ mod p和m=$c^d$ mod q，然后利用CRT计算出m。但CRT算法只能对解密过程加速，不能对加密过程加速，因为加密者只知道公钥（e，n），并不知道n的分解p、q。所以，，为了维护加密者的用户体验，很多情况下RSA的加密密钥e较解密密钥d小。
小结
在RSA算法的求解过程如下，
用Miller-Rabin检测法去选取两个足够大（$10^{100}$~$10^{200}$）的素数p、q。
利用p、q计算出n=p·q和n的欧拉数Ф(n)=(p-1)·(q-1)。
随机选取整数e， 利用EA算法计算最大公约数gcd（e，Ф），使得gcd（e，Ф）=1。
使用EEA或者Euler’s Theorem求解d。
解密过程中，可以用到CRT算法来加速解密过程。