Montgomery乘法是公钥算法实现中的一个核心算法,其主要作用是为模乘运算加速。
在公钥算法实现中,通常需要计算a mod M、a*b mod M、a^b mod M等,一般看见mod M,最直接想到的当然是除法,可是除法运算慢且实现难,于是,就有人发明了一种不需要计算除法的计算模的方法,这就是所谓的Montgomery乘法。
Montgomery乘法的数学表达是A*B*R^(-1) mod M,其中,A、B是与M同位长的大数,R = 2^bitlen(bitlen指M位长),R^(-1)是指R相对于M的模逆,即R^(-1)是满足如下条件的数:R*R^(-1) mod M = 1;这个条件成立的充要条件是R与M互素,这一点只需要M为奇数即可,所以Montgomery乘法通常适用于对奇数求模。
数学最烦人也是最忌讳的是只见形式不懂实质;以下为你慢慢揭示Montgomery乘法的内在涵义。
从一个除法例子说起吧。
例如要计算11111111除以1011(二进制表示),写出其除法过程如下:
1011| 11111111| 1
| 1011 |
——————————————
1001111| 0
0000 |
——————————————
1001111| 1
1011 |
——————————————
100011| 0
0000 |
——————————————
100011| 1
1011 |
——————————————
1101 | 1
1011 |
——————————————
10
计算过程本质上是将被除数从高位归0直至余数小于除数的过程,归0过程的规则是要使用被除数减除数。例如在第一步中,是将1111减去1011,即把被除数最高位归成0,然后将余做100作高位与被除数低位1111拼成新的被除数,如此迭代。
现在来做一种新的运算。这种新运算与之前除法有两点相反:一是从低位归0,二是归0规则使用加法,其运算过程如下:
11111111| 1011
1011|
————————————
100001010|
1011 |
————————————
100100000|
从低位归0需要“除数”是奇数,否则,当“被除数”是奇数时,“被除数”的最低位总是无法归成0。
低位归0方法总可以迭代到“被除数”的非0高位与“除数”相差不大,上例中,当低位归到5个0时,“被除数”的高位变为1001,舍弃低位的5个0,把高位的1001当做“余数”;通常,传统的Montgomery乘法归0的个数是与模数位长相等的,所以这里我们归掉4个0,然后将10010减去1011,得到的111作为“余数”。
比较上述2种运算的运算量,可以发现:从高位归0需要额外使用“比较”操作,因为需要确保每次归0时被除数大于除数。
以下来揭示第二种“除法”的涵义。
上述第二种“除法”实际是在被除数上加了若干除数,使得被除数的低位变为0,而高位与除数接近(所以也可以让其比除数小),将高位当做余数。用S记被除数,M记除数,q记累加M的次数,R记2^bitlen,其中bitlen指归0的个数,则余数的表达式为:(S+qM)/R。
当“除数”是奇数时,“被除数”的低位总能被归成0,所以,适当选取q,总可以使得(S+qM)/R为一个小于除数的数。
S与S+qM是什么关系呢?显然,S和S+qM对M是同余的。所以表达式(S+qM)/R的涵义可以理解为:在与S同余的数中,选取一个低位有bitlen个0,且高位小于M的数,去掉该数低位的bitlen个0,所得的数即为(S+qM)/R。
如果了解一些模和群的知识,表达式(S+qM)/R写成S*R^(-1)就更简单,形式上的意思就变为:剩余类S与剩余类R^(-1)的乘积。
对于Montgomery乘法A*B*R^(-1) mod M,将S看做A*B,涵义自然就比较清晰了。
使用Montgomery乘法代替A*B mod M必须要做到功能能替代A*B mod M,且要有其速度上的优势,否则Montgomery乘法就没有存在的必要了。
先来看速度上的优势。
通过前面的说明可以知道:从低位归0比从高位归0每次迭代可以省去大数的比较操作,这是Montgomery乘法速度上的优势之一。
更为重要的是,Montgomery乘法可以做大量的并行运算,而A*B mod M则必须先将A*B计算出来再计算除法。所以当使用硬件实现Montgomery乘法会有很高的效率。
如何使用A*B*R^(-1) mod M代替A*B mod M呢?
通常,将x映射成x*R mod M,后者可以称之为x的Montgomery表示,可以发现,输入两个Montgomery表示下的乘数,使用Montgomery乘法运算,可以得到原乘数使用普通模乘得到的数的Montgomery表示。所以,要计算模乘运算,可以先将乘数化成Montgomery表示,然后使用Montgomery乘法,最后将结果脱掉Montgomery表示,即得普通模乘的结果;这个过程虽然复杂些,但是对于计算大量模乘的运算(例如模幂)而言,只是多了初始的入和出Montgomery表示的过程,但中间每次计算Montgomery乘法,却比计算普通模乘省下大量时间。
要将x写成Montgomery表示,可以计算x与R^2的Montgomery乘法,要脱掉Montgomery乘法,可以计算x与1的Montgomery乘法。由于R^2是常数,可以提前计算。
Montgomery乘法目前常常被使用于RSA和ECC中,智能卡芯片通常使用硬件实现Montgomery乘法,软件实现RSA和ECC功能即可满足一般终端的使用需求。