蒙哥马利大整数模幂算法

  前几天写了一篇博客《25行代码实现完整的RSA算法》，是关于用Python代码实现一个完整的RSA算法的代码，整个代码中最核心、最浪费时间的代码部分就是关于求解大整数模幂算法这里。整个算法也叫“蒙哥马利幂模”算法。
  首先简单介绍一下蒙哥马利相关的几个算法，具体详细介绍可以参考《蒙哥马利算法详解》。蒙哥马利算法并不是一个独立的算法，而是三个相互独立又相互联系的算法集合，其中包括：

• 蒙哥马利乘模，是用来计算 x⋅y(modN) x ⋅ y ( m o d N ) <script type="math/tex" id="MathJax-Element-65">x⋅y (mod N)</script>
• 蒙哥马利约减，是用来计算 t⋅ρ−1(modN) t ⋅ ρ − 1 ( m o d N ) <script type="math/tex" id="MathJax-Element-66">t⋅ρ^{-1} (mod N)</script>
• 蒙哥马利幂模，是用来计算 xy(modN) x y ( m o d N ) <script type="math/tex" id="MathJax-Element-67">x^{y} (mod N)</script>

  在这三个算法中，蒙哥马利幂模是RSA加密算法的核心部分。本篇文章为了简单起见就不介绍前两个“蒙哥马利乘模”和“蒙哥马利约减”算法了。主要介绍第三个“蒙哥马利幂模”的计算方法过程，以及通过一个小例子进行说明这个算法的具体计算过程，至于证明方法我就不在这里介绍，大家只要能看到这个例子以后，能把代码写出来就能写完整的RSA算法了。如果想看已经实现的代码请参考这里，或者这里。在这两篇博文里都有完整的代码实现方法。下面介绍“蒙哥马利幂模”的详细计算过程：
  RSA公钥密码的加密算法与解密算法都要计算“模幂乘运算” ab(modN) a b ( m o d N ) <script type="math/tex" id="MathJax-Element-68">a^b(modN)</script>。
设b的二进制数字表示为 br−1...b1b0 b r − 1 . . . b 1 b 0 <script type="math/tex" id="MathJax-Element-69">b_{r-1}...b_1b_0</script>，即：
       b=b0+b1×2+...+br−1×2r−1 b = b 0 + b 1 × 2 + . . . + b r − 1 × 2 r − 1 <script type="math/tex" id="MathJax-Element-70">b=b_0+b_1×2+...+b_{r-1}×2^{r-1}</script>。
于是：
       ab≡ab0×(a2)b1×...×(a2r−1)br−1(modN) a b ≡ a b 0 × ( a 2 ) b 1 × . . . × ( a 2 r − 1 ) b r − 1 ( m o d N ) <script type="math/tex" id="MathJax-Element-71">a^b≡a^{b_0}×(a^2)^{b_1}×...×(a^{2^{r-1}})^{b_{r-1}}(mod N)</script>
令 A0=a A 0 = a <script type="math/tex" id="MathJax-Element-72">A_0=a</script>， Ai≡(Ai−1)2(modN) A i ≡ ( A i − 1 ) 2 ( m o d N ) <script type="math/tex" id="MathJax-Element-73">A_i≡(A_{i-1})^2(mod N)</script>，i = 1， 2… r - 1，则有：
     ab≡A0b0×A1b1×...×Ar−1br−1(modN) a b ≡ A 0 b 0 × A 1 b 1 × . . . × A r − 1 b r − 1 ( m o d N ) <script type="math/tex" id="MathJax-Element-74">a^b ≡ {A_0}^{b_0} × {A_1}^{b_1} × ... × {A_{r-1}}^{b_{r-1}} (mod N)</script>
其中，在这里

<script type="math/tex; mode=display" id="MathJax-Element-75">{A_i} ^ {b_i}=\begin{cases} A_i, & 若b_i=1\\ 1, & 若b_i=0 \end{cases} i=0,1...r-1</script>
下面通过一个例子来说明以上的公式：
  例1：取p=43,q=59，n = 43 × 59 = 2537 , φ(n) = (43 - 1) × (59 - 1) = 2436 , 选取e = 13。字母表（a，b，….，z）依次用00,01，…，25表示，各占2位，设明文段m=2106，也就是m = vg，那么密文 c=210613mod2537 c = 2106 13 m o d 2537 <script type="math/tex" id="MathJax-Element-76">c = 2106^{13} mod 2537</script>。计算如下：13的二进制表示为1101，即 13=1×23+1×22+0×21+1×20=23+22+1 13 = 1 × 2 3 + 1 × 2 2 + 0 × 2 1 + 1 × 2 0 = 2 3 + 2 2 + 1 <script type="math/tex" id="MathJax-Element-77">13=1×2^3 + 1×2^2 + 0×2^1 + 1×2^0 = 2^3 + 2^2 + 1</script>。
   A0=2106≡−431(mod2537) A 0 = 2106 ≡ − 431 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-78">A_0 = 2106 ≡ -431 (mod 2537)</script>，
   A1=(−431)2≡560(mod2537) A 1 = ( − 431 ) 2 ≡ 560 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-79">A_1 = (-431)^2 ≡ 560 (mod 2537)</script>，
   A2=(560)2≡−988(mod2537) A 2 = ( 560 ) 2 ≡ − 988 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-80">A_2 = (560)^2 ≡ -988 (mod 2537)</script>，
   A3=(−988)2≡−601(mod2537) A 3 = ( − 988 ) 2 ≡ − 601 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-81">A_3 = (-988)^2 ≡ -601 (mod 2537)</script>，
   210613=(−431)×(−988)×(−601)≡2321(mod2537) 2106 13 = ( − 431 ) × ( − 988 ) × ( − 601 ) ≡ 2321 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-82">2106^{13} = (-431) × (-988) × (-601) ≡ 2321 (mod 2537)</script>
得到密文c=2321。
  又设收到密文是0981，要把它恢复成明文，计算 13−1≡937(mod2436) 13 − 1 ≡ 937 ( m o d 2436 ) <script type="math/tex" id="MathJax-Element-83">{13}^{-1} ≡ 937(mod2436)</script>，得d = 937，明文 m′=981937(mod2537) m ′ = 981 937 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-84">m^{'} = 981 ^ {937} (mod 2537)</script>。计算如下：937的二进制表示为1110101001，即 937=1+23+25+27+28+29 937 = 1 + 2 3 + 2 5 + 2 7 + 2 8 + 2 9 <script type="math/tex" id="MathJax-Element-85">937 = 1 + 2^3 + 2^5 + 2^7 + 2^8 + 2^9</script>。
   A0=981 A 0 = 981 <script type="math/tex" id="MathJax-Element-86">A_0 = 981</script>，
   A1=9812≡838(mod2537) A 1 = 981 2 ≡ 838 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-87">A_1 = 981^2 ≡ 838 (mod 2537)</script>，
   A2=8382≡−505(mod2537) A 2 = 838 2 ≡ − 505 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-88">A_2 = 838^2 ≡ -505 (mod 2537)</script>，
   A3=(−505)2≡−1325(mod2537) A 3 = ( − 505 ) 2 ≡ − 1325 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-89">A_3 = (-505)^2 ≡ -1325 (mod 2537)</script>，
   A4=13252≡21(mod2537) A 4 = 1325 2 ≡ 21 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-90">A_4 = 1325^2 ≡ 21 (mod 2537)</script>，
   A5=212≡441(mod2537) A 5 = 21 2 ≡ 441 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-91">A_5 = 21^2 ≡ 441 (mod 2537)</script>，
   A6=4412≡−868(mod2537) A 6 = 441 2 ≡ − 868 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-92">A_6 = 441^2 ≡ -868 (mod 2537)</script>，
   A7=(−868)2≡−65(mod2537) A 7 = ( − 868 ) 2 ≡ − 65 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-93">A_7 = (-868)^2 ≡ -65 (mod 2537)</script>，
   A8=(−65)2≡−849(mod2537) A 8 = ( − 65 ) 2 ≡ − 849 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-94">A_8 = (-65)^2 ≡ -849 (mod 2537)</script>，
   A9=(−849)2≡293(mod2537) A 9 = ( − 849 ) 2 ≡ 293 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-95">A_9 = (-849)^2≡ 293 (mod 2537)</script>，
   981937≡981×1325×441×981×981×293≡704(mod2537) 981 937 ≡ 981 × 1325 × 441 × 981 × 981 × 293 ≡ 704 ( m o d 2537 ) <script type="math/tex" id="MathJax-Element-96">981^{937} ≡ 981 × 1325 × 441 × 981 × 981 × 293 ≡ 704(mod 2537)</script>,
得明文： m′=0704 m ′ = 0704 <script type="math/tex" id="MathJax-Element-97">m' = 0704</script>，即he。
  如果想看到一个正式的加密解密代码请点击我的第一篇博客《 25行代码实现完整的RSA算法》，在这里你才能真正领略“蒙哥马利算法”在互联网支付与通信时代所发挥的重大的作用。今天我们敢在手机上、电脑上以及服务器上面很放心地对自己的银行卡进行操作，全都依赖rsa算法的威力。