RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）在1977年一起提出的，RSA 就是他们三人姓氏开头字母拼在一起组成的。
——Wikipedia
RSA算法加密的安全性基于大整数因数分解的复杂度，算法设计思路简单，只用到部分简单初等数论的知识，具有充分的美感，容易让人理解和接受。
本文将阐述RSA算法在进行加密解密和签名时的数学原理，以及RSA算法的安全性。
前置数学知识
这个部分会简单提到部分RSA算法中会用到的数学知识，我并不会重复整个初等数论体系，需要你有一些预备的基本初等数论知识，主要是包括同余理论、最大公约数和最小公倍数部分内容。
注意，为了讨论方便，在本文中我们总是假定p为质数。
首先是一个关于同余的小结论
性质 1 若a,b,m,n为整数，且a\equiv b\pmod m,a\equiv b \pmod n，则有a \equiv b\pmod{\operatorname{lcm} (m,n)}.
特别地，当\gcd (m,n)=1时，a\equiv b\pmod{mn}.
证明
由同余的定义，我们有m \mid a-b, n \mid a-b，因此\operatorname{lcm} (m,n) \mid a-b，也就是a \equiv b\pmod{\operatorname{lcm} (m,n)}.
Q.E.D
定义 1 设n是正整数，则Euler Totient函数（简称Euler函数）\varphi(n)为小于等于n的正整数中与n互质的数的数目。
例如，与8互质并且小于等于8的数有1,3,5,7，因此\varphi (8)=4.
Euler函数具有如下的积性，
性质 2 \forall m,n \in \mathbb{N}, \gcd (m,n)=1, \varphi (mn)=\varphi(m)\varphi(n).
证明 略
Q.E.D
并且对于质数的幂次，我们可以得到Euler函数的便捷计算式，结合其积性我们可以通过正整数的素因数分解式快速计算Euler函数。
性质 3 设n为非负整数，则
\varphi (p^n)=p^n-p^{n-1}.证明
在小于等于p^{n}的所有正整数中，与其不互质的只有形如p \cdot t,t\in {1, 2,\cdots ,p^{n-1}}的数，总共p^{n-1}个，因此互质的数的数目为p^n-p^{n-1}.
Q.E.D
性质 4 设非负整数n有标准分解式n=p_{1}^{t_1}p_{2}^{t_2}\cdots p_{s}^{t_s}，则
\varphi (n)= n\prod \limits _{i=1} ^{s} (1-\frac{1}{p_{i}}).证明
通过算术基本定理将n分解后利用Euler函数的积性和性质 3即可。
Q.E.D
与Euler函数相关的最重要的定理为下面的Euler-Fermat定理
定理 1（Euler-Fermat定理） 设a,n\in \mathbb{N}_{+},\gcd (a, n)=1，则
a^{\varphi(n)} \equiv 1 \pmod n.证明
我们记(\mathbb{Z}/n\mathbb{Z})^* = \{ m:1\leq m \leq n,\gcd(m,n)=1 \}，显然有\varphi (n)=\#(\mathbb{Z}/n\mathbb{Z})^*.
并且容易证明实际上(\mathbb{Z}/n\mathbb{Z})^*是一个整数乘法诱导的乘法群。
因此由Lagrange定理，子群阶数总是整除大群阶数，也就是(\mathbb{Z}/n\mathbb{Z})^*中任何元素阶数总是整除\varphi (n)，所以\bar {a}^{\varphi (n)}=\bar{1}，也就是a^{\varphi (n)} \equiv 1 \pmod n.
Q.E.D
RSA算法
以下部分摘自Wikipedia，并作了一些补充说明。
公钥与私钥的产生
假设Alice要通过不可靠信道接受Bob的一条私密信息，她用如下方式来产生一个公钥和私钥：
- 随机选择两个不相同的大质数
p与q，记N=pq; - 由前面Euler函数的性质，我们有
r = \varphi (N)=\varphi (p)\varphi (q) = (p - 1)(q - 1); - 选择正整数
e小于r并且与r互质。设d为e模r的乘法逆元（即ed \equiv 1 \pmod r，由于e与r互质，由Bezout定理知这样的逆元存在，关于求乘法逆元的算法可以参照模意义下乘法逆元的算法实现）。 - 为了安全需要销毁
p和q.
此时我们就得到了公钥(N,e)与私钥(N,d)。Alice需要将公钥发送给Bob，将私钥保管好。
加密与解密
Bob给Alice发送消息时，需要先将消息转换为小于N的非负整数n，这种转换方式很多，例如可以将消息编码后分段，使得每一小段对应数字都很小。
然后我们可以通过Bob的公钥计算出密文
c \equiv n^e \pmod N当Alice收到密文后，通过自己的私钥即可计算出原文
n \equiv c^d \pmod N以下是解密正确性的证明
实际上由上述过程可知，为了解密只需要证明
n^{ed} \equiv n \pmod N我们有ed\equiv 1\pmod r，也就是ed = 1+h\varphi (N)，我们分别考虑n与N互质与不互质的情况。
当n与N互质时，由Euler定理容易得到
n^{ed} = n^{1+h\varphi (N)} = n(n^{\varphi (N)})^h \\
\implies n^{ed} \equiv n(1)^h \equiv n \pmod N当n与N不互质时，只可能为n含有因数p或q，不妨设n=ph。由ed\equiv 1 \pmod N，我们可以令ed = 1+h\varphi (N)=1+h(p-1)(q-1)=1+k(q-1)，于是有
n^{ed} = (ph)^{ed} \equiv 0 \equiv ph \equiv n\pmod p\\
n^{ed} = n^{ed-1}n = n^{k(q-1)}n\\=(n^{q-1})^k n\equiv 1^{k}n\equiv n \pmod q由于p和q总是互质的，因此前述同余的性质1知n^{ed}\equiv n\pmod N.
数字签名
Alice想要给Bob发送RSA签名的消息时，首先需要将自己的消息计算一个摘要。我们可以注意，根据前面加密解密的数学证明，RSA算法中的公钥和私钥事实上是可以互相替代的（注意在一些列如椭圆曲线加密（ECC）的算法中，这通常是不可以的），此时Alice可以将散列值通过自己私钥加密后发送给Bob，而这个加密的摘要只有经过她的公钥才能解密。
当Bob收到加密的摘要和消息后，他可以将摘要解密，能正常解密说明确实是Alice进行的签名。然后将实际收到的消息用相同算法计算摘要并与解密后的摘要进行对比，如果符合则说明消息没有被篡改。
安全性
我们这里讨论的安全性，实际指的是在已知RSA公钥的情况下计算私钥的复杂度，然而实际上安全性在实际应用中还受到诸多因素影响（例如基于硬件的旁路攻击、时间攻击，基于溢出的差错攻击，或者黑客直接把你电脑黑了记录下了所有东西）。
假设现在偷听着Eve监听到Alice的公钥(N,e)，现在要计算出Alice的私钥(N,d)。要破解出d，可以将N分解为pq，然后通过解同余方程ed\equiv 1 \pmod{(p-1)(q-1)}即可解出d。虽然求乘法逆元的复杂度是可以接受的，但是分解N却没有一个多项式时间的算法（这里问题规模指的是二进制位长度，所以多项式是指关于\log N的多项式），当然目前也没有人证明这样的算法不存在。
不过上述是针对电子计算机的，1994年Peter Shor证明量子计算机可以在多项式时间内进行质因数分解，不过目前碍于技术原因（似乎是受到一种称为量子“退相干”现象影响），实现还需要很长的时间。
目前最新的分解记录是2019年12月通过大量电子计算机集群实现的对有效长度795 bits的大整数分解，所以我们有理由相信1024bits RSA不再安全，目前推荐使用的长度为2048bits以上。
妙啊