• 标 题:PE Explorer 1.95 ?了!
  • 作 者:oinion
  • 时 间:2004-07-09 22:32:10

PE Explorer 相信大家都知道这个软件吧!
这是官方的介绍: 

Here's what's new in PE Explorer 1.95

 General:
  • Added the Remove Debug Information Tool.
  • Added the Remove Relocations Tool.

 Disassembler:
  • Now supports the SSE3 instruction set.
  • Upgraded the algorithm for detecting Unicode strings.
  • Improved the data analysis algorithm to produce a higher quality disassembly listing.

 Resource editor:
  • Bugfix: TypeLibs in the multi-language resources would occassionally display incorrectly.

点击下载http://bbs.pediy.com/upload/image/?眵靡.JPG_83478.jpg http://bbs.pediy.com/upload/image/未命名.JPG_83478.jpg

  • 标 题:Montgomery乘法介绍
  • 作 者:publickey
  • 时 间:2011-02-18 18:42:29

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功能即可满足一般终端的使用需求。