Montgomery模乘算法

2019-04-13 11:54发布

站内文章 / 模拟电子
9378 0 1413
本文节选自《密码学引论》第二版。        Montgomery算法把部分积对任意的n取模运算转化为对数基R的取模，由于R比n小得多，对数基R的取模运算要比对n的取模运算简单得多。对于特别选择的R可使得对R的取模运算变为移位运算,从而可以提高模乘运算的速度。因为利用Montgomery算法可以实现快速模幂运算，所以Montgomery算法在RSA密码的软硬件实现中得到广泛应用。       Montgomery算法:       设n为模数，选择一个与n互素的正整数R作为基数。再选择正整数R^-1和n' ，满足0     Function Mon(A,B,R,n):
  1. T=AB
  2. s=Tn' modR
  3. t=(T+sn)/R
  4. if t>=n then retum(t-n) else returm t
      根据算法Mon(A,B,R,n)可知，t=(T+sn)/R,tR=T+sn。所以有
      T +sn=0 mod R
      这说明(T+sn)是R的倍数，因此t为整数。根据tR=T+sn,于是又有
      tR=T mod n;   t=TR^-1 mod n;  t=ABR^-1 mod n ;
      这就证明了Montgomery算法完成了ABR^-1 mod n的计算。即
      Mon(A,B,R,n) =AB R^-1 mod n      为了利用函数Mon(A,B,R,n)，必须首先选择产生R和n’，但是这种选择产生的计算是一次性的，可以预处理，因此消耗的时间不多。
     值得注意的是，在函数Mon(A,B,R,n)中的第①步,计算T=AB,由于A和B都是大数,这乘法运算仍是很麻烦的。这说明Montgomery 算法并不能省略大数的乘法运算。但是这里仅仅是计算大数的乘法，而不需要取模运算。这与普通的大数模乘运算相比，仍然节省了很多。
      另外,在函数Mon(A,B,R,n)中没有进行mod n的计算，只进行了mod R的计算。一般R比n小得多，而且通常都选R=2^w ,w是非负整数,从而使mod R的计算变成移位操作,计算更加简捷。       下面给出利用函数Mon(A,B,R,n)计算y=ab mod n的完整过程。       1.首先进行预处理:           A=aR,B=bR        2.然后计算:            Y= Mon(A,B,R,n) =ABR^-1 mod n
             =(aR)(bR)R^-1 mod n=abR mod n        3.最后进行调整运算:            y =YR^-1 mod n
              = (abR)R^-1 mod n=ab mod n       注意，由于Mongomery算法采用了mod R运算,因此在计算ab mod n时先要进行预处理，最后还要进行调整运算。

热门文章