简介
RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。
预备知识
乘法逆元
定义：对于整数a，如果u是a mod n的乘法逆元，那么存在$au ≡ 1 mod n$。
推论：对于整数a，让n作为模数。那么a mod n存在一个乘法逆元当且仅当a ⊥ n。
证明：
注意a mod n存在乘法逆元，当且仅当关于(u,v)的方程$au+nv=1$有解。而且也确实是这样，因为$au ≡ 1 mod n$当且仅当$n | au−1$,这就表示一定存在整数q，使得$au−1=nq$。让q = -v，重新排列得到原方程。
假设，a和n存在最大公约数d，有$a = a’d$, $n=n’d$，那么
$au+nv=a’ud+n’vd=(a’u+n’v)d=1$
这里因为d是整数，所以d=1方程才会成立。且gcd(a,n) = 1 当且仅当 a ⊥ n。
证毕。
积性函数
定义：对一个定义域为$N^+$的函数$ f$，对于任何两个互质的正整数a和b，均满足$f(ab)=f(a)f(b)$，则函数$ f$为积性函数。
性质：
1.对于任何积性函数，均有$f(1)=1$。
2.对于一个正整数N，设$N=∏p_i^{a_i}$，$p_i$为互不相同的质数，那么对于一个积性函数来说，有：$f(N)=f(∏p_i^{a_i})=∏f(p_i^{a_i})$。
欧拉函数
定义：对于正整数n，欧拉函数是指在小于n的正整数中与n互质（两个数没有公约数）的数的数目。
通式：$φ(x)=x∏\limits_{i=1}^n(1-\dfrac{1}{p_i})$
其中p1, p2……pn为x的所有质因数，x是不为0的整数。
若n是质数p的k次幂，$φ(n)=p^k-p^{k-1}=(p-1)p^{k-1}$，因为除了p的倍数外，其他数都跟n互质。
欧拉函数是积性函数——若m,n互质，$φ(mn)=φ(m)φ(n)$。
证明：
$φ(n)=n\mathop∏_{i=1}^x(1-\dfrac{1}{p_i})$
$φ(m)=m\mathop∏_{j=1}^y(1-\dfrac{1}{p_j})$
$φ(n)φ(m)=nm\mathop∏_{i=1}^{x+y}(1-\dfrac{1}{p_i})$
$φ(nm)=nm\mathop∏_{i=1}^z(1-\dfrac{1}{p_i})$
因为n和m互质，所有的质因数$p_i$和$p_j$各不相同，$x+y=z$，所以$φ(nm)=φ(n)φ(m)$。
证毕。
特殊性质：当n为奇质数时，$φ(2n)=φ(n)$, 证明与上述类似。
若n为质数则$ φ(n)=n-1$。
欧拉定理
定义：n作为模数，对于整数a（a与n互质），存在 $a^{φ(n)} ≡ 1 mod n$ 。
证明：
由欧拉函数得到集合X，定义如下：
$X = \{k ∈ [n] | k ⊥ n\}$
这个集合有$φ(n)$个元素，集合有以下元素：
$X = \{x_1,x_2,…,x_{φ(n)}\}$
对于所有i，有$ax_i ⊥ n$，假设$y_i$是X中的元素，存在 $ax_i ≡ y_i mod n$。
注意如果i ≠ j那么 $y_i ≠ y_j$ 。我们可以证明这点，因为a ⊥ n，a mod n有一个乘法逆元叫做b，然后
$y_i ≡ y_j mod n \quad ⇒ \quad ax_i ≡ ax_j mod n \quad ⇒ \quad bax_i ≡bax_j mod n \quad ⇒ \quad x_i ≡x_j mod n$
如果 $x_i=x_j$ 当且仅当 i = j。所以
$X = \{x_1,x_2,…,x_{φ(n)}\} = \{y_1,y_2,…,y_{φ(n)}\}$
这就表示所有$x_i$的乘积等于所有$y_i$的乘积，因此
$x_1 · … · x_{φ(n)}$
$≡y_1 · … · y_{φ(n)} mod n$ 因为$\{x_1,…\}=\{y_1,…\}$
$≡(ax_1) · … · (ax_{φ(n)}) mod n$ 因为$y_i ≡ax_i mod n$
$≡a^{φ(n)} · x_1 · … · x_{φ(n)} mod n$ 重新排列
因为每一个$x_i$都与n互质，消除$x_i$(通过乘法逆元公式)最后获得
$a^{φ(n)} ≡ 1 mod n$
证毕。
RSA加密
公钥密码
公钥密码是一种加解密方法，根据以下原则来运作：
1.加密过程需要使用公钥（public key），公钥对所有人可见。
2.解密过程需要使用私钥（private key），私钥只对信息接受者可见。
3.通过公钥的信息来被破解私钥的信息应该极其困难。
RSA加密过程
RSA加密是一种通过模算术理论提供手段来制作公钥密码的算法，步骤如下：
1.找到 p 和 q 两个不同的正质数，n = pq，那么$φ(n)=(p-1)(q-1)$。
2.选择一个整数e，$1<e<φ(n)$ 并且 $e⊥φ(n)$。(n, e)就称之为公钥。
3.选择一个整数d，$de≡1 mod φ(n)$，(n, d)就称之为私钥。
4.加密信息为M（编码后的整数,$M<n$且$M⊥n$），计算$K ∈ [n]$，$K ≡ M^e mod n$。K作为加密后的信息。
5.因为$M ≡ K^d mod n$，接受者恢复原始信息M。
证明：
$M^{de}=(K+ln)^d$ 因为$K ≡ M^e mod n$，设$M^e=K+ln$
$(K+ln)^d≡K^d mod n$ 因为二项式展开$(K+ln)^d$后，除了首项，其他项被n整除。
$M^{de}=M^{kφ(n)+1}$ 因为$de≡1 mod φ(n)$，设$de=1+kφ(n)$
$M^{kφ(n)+1}=M·M^{kφ(n)}$
$M·M^{kφ(n)}=M(1+fn)^k$ 因为$M^{φ(n)}≡1 mod n$，设$M^{φ(n)}=(1+fn)$
$M(1+fn)^k≡M mod n$ 因为二项式展开$(1+fn)^k$后，除了首项，其他项被n整除。
综上：
$M ≡ K^d mod n$
证毕。
参考书籍
《An infinite descent into pure mathematics》