RSA 算法
RSA 算法由密码学由Ron Rivest、Adi Shamir 和 Leonard Adleman在1977年提出。其数学结构简单易懂，直到今天仍是最广泛使用的公钥密码算法。
RSA 算法利用了大整数分解这一数学难题。消息接收者生成$n = p \times q$，其中$p$和$q$均为大素数。计算$ed \equiv 1 \mod n$，其中 $e$ 为公钥，一般取 $65537$，$d$ 为私钥。消息接收者将$n$ 和 $e$进行公开。
- 消息发送者加密消息时，计算密文$c \equiv m^e \mod (p-1)(q-1)$，
- 消息接收者可通过计算$m \equiv c^d \mod n$ 恢复消息 $m$。
当然，在实际使用时，RSA 算法并非这么简单，还需要考虑填充等结构，以避免一些攻击，如Bleichenbacher's attack 等。
一般来说，RSA 的公钥 $n$ 较大，通常为1024 bit、2048 bit、4096 bit，也就是RSA-1024、RSA-2048 和 RSA-4096。在实现时，RSA 会涉及三类大数运算:1.大数乘法 2.大数取模 3.大数模幂。这三类计算在实现时均有相应的算法来进行优化。其中，大数乘法和取模可以和合并为模乘运算，一般采用大名鼎鼎的Montgomery 模乘算法。
Montgomery模乘
模运算是大数运算中最费时间的一种。模运算实际上是算除法，在运算时，一般需要做试除，导致除法的计算复杂度比乘法要高。因此，我们希望在实现的时候尽量避免乘法。
Montgomery 在论文"Modular Multiplication Without Trial Division"中提出一种计算模乘的方法，将除$n$操作可转化为移位操作，有效的降低了实现复杂度。该算法是目前实现RSA最常用的模乘实现。
Montgomery模乘实际上由模约减和模乘两部分组成，下面我们分别进行介绍。
Montgomery模约减算法
模约减算法$R(\cdot)$定义为：$\forall x \in [0, n^2)$ 计算 $R(x) = xr^{-1} \mod n$，其中$r > n$ 且 $gcd(n, r) = 1$。
计算算法如下：
- 计算 $s = xk \mod r$，其中$k = \frac{r(r^{-1} \mod n)-1}{n}$;
- 计算 $t = x + sn$。注意，$x<n^2<rn$，$sn<rn$，故$t<2nr$。这里$t$还有一个重要特性：$t \equiv 0 \mod r$，也就是$t$是$r$的整数倍。可按下式进行证明：
$$x+sn \equiv x+xkn \equiv x(1+kn) \equiv x(rr{-1})\equiv 0 \mod r;$$ - 计算$u = \frac{t}{r}$，可知$u \equiv tr^{-1} \mod n$；
- 由 $t<2nr$ 可知$u<2n$。如果$u<n$，则直接返回$u$即为$R(x)$结果；否则返回$u-n$。
从上面计算方法可以看出，我们可以将 $\mod n$ 的操作转化为 $\mod r$，除 $r$ 和 减法。特别的，可以取$r = 2^b$，这样在计算机内实现时，模和除 $r$ 均可很快计算得出。这也是Montgomery模乘算法的精髓。
Montgomery模乘
和普通模计算 $a\times b \mod n$ 不同，Montgomery模乘首先计算的是 $abr \mod n$。通过Montgomery 模约减算法，可以简单的通过如下方式计算:
- 计算$c \equiv ar \mod n$ 和 $\equiv br \mod n$；
- 计算$c \times d$，然后通过Montgomery 模约减算法计算$e = R(c \times d)$ 即为$abr \mod n$；
- 输出$er^{-1} \mod n$。
p.s. 对于$x$，$xr \mod n$一般称为$x$的 Montgomery 表示。
Montgomery模乘总结
计算可以将计算 $a\times b \mod n$ 总结如下：
1. 初始化计算
- 选择$r > n$，且 $gcd(r, n) = 1$
- 计算$k = \frac{r(r^{-1} \mod n)-1}{n}$
2. 转化为 Montgomery 表示
- 计算$c \equiv ar \mod n$ 和 $d \equiv br \mod n$
3. 计算 $abr \mod n$
- $x = cd$
- $s = xk \mod r$
- $t = x + sn$
- $u = \frac{t}{r}$
- 若 $u<n$ 输出 $e=u$，否则输出 $e = u-n$
4.从Montgomery 表示转化为一般表示
- $er^{-1} \mod n$
Montgomery 模乘之于RSA 算法
虽然在计算过程中没有$\mod n$相关操作，但在初始化和最后的转化中，还是会进行 $\mod n$ 的操作。这样计算模乘看上去并没有降低计算的复杂程度。然而，在 RSA 算法中，存在一系列的模乘运算，这些模乘运算是连续进行的。如最著名的平方乘算法，就是把模幂运算分解成一系列的模乘和模方操作。另外，我们也不难发现，在Montgomery 模乘输出的结果$e$，其实正是 $ab \mod n$ 的 Montgomery 表示。那么对于计算 $c^d \mod n$ 这样的模幂，我们可以首先完成1.初始化计算 和 2.将 $m$ 转化为 Montgomery 表示，套用平方乘等算法，始终使用Montgomery 表示来计算模乘，最后统一进行4.从Montgomery 表示转化为一般表示。这样可以避免中间过程进行$\mod n$运算从而大大减小计算的复杂程度。Bingo！
参考：
https://www.nayuki.io/page/montgomery-reduction-algorithm
http://www.doc88.com/p-7428222580849.html
