OpenSSL密码库算法笔记——第1.2.1章经典乘法

所谓的经典乘法就是在小学的时候学到的那一套做乘法的方法。如果假设被乘数a和乘数b为&＃xff1a;

&＃xff0c;                         …………(1.1)

则经典乘法是这样做的&＃xff1a;

   。                   …………(1.2)

即分别做a×bi&＃xff0c;再累加到r上。

算法如下&＃xff1a;&＃xff08;参见[1]算法14.12&＃xff09;

───────────────────────────────────────

算法&＃xff1a;    经典乘法

step1&＃xff1a;   对i从0到&＃xff08;m&＃xff0b;n&＃xff0d;1&＃xff09;&＃xff0c;令ri←0。

step2&＃xff1a;   对j从0到n&＃xff0d;1&＃xff0c;执行如下运算&＃xff1a;

2.1) c←0。

2.2) 对于i从0到m&＃xff0d;1&＃xff0c;

2.2.1) 计算

       …………(1.3)

这里的h32表示h为32比特&＃xff0c;h16表示h为16比特&＃xff0c;其余同理。

说明&＃xff08;2&＃xff09;、&＃xff08;3&＃xff09;可归纳为下表&＃xff1a;

表1.2 bn_mul、bn_mul_add与mul64的比较

关于上述函数与宏定义的关系请参见§1.2.3。

当乘数退化成一个字的时候&＃xff0c;可以使用大整数与字的乘法。

───────────────────────────────────────

BN_ULONG bn_mul_word(BIGNUM *a, BN_ULONG w)

功能&＃xff1a;    大数与字的乘法

输入&＃xff1a;    a【大数】&＃xff0c;w【字】

输出&＃xff1a;    a←a×w

返回&＃xff1a;    1【正常】 or 0【出错】

出处&＃xff1a;    bn_word.c

───────────────────────────────────────

注意&＃xff1a;这个函数的名称bn_mul_word和前面提到的bn_mul_words&＃xff08;见本小节对经典乘法函数bn_mul_normal的说明(1)&＃xff09;很相似&＃xff0c;功能也有些相似&＃xff0c;都可以看作是做大整数&＃xff08;前者对应BIGNUM *而后者对应BN_ULONG *&＃xff09;与字的乘法。bn_mul_word(a,w)是做大整数与字的乘法a←a×w&＃xff0c;而bn_mul_words 主要是被乘法运算调用&＃xff0c;作为一个内部子函数来调用&＃xff0c;基本上没有作为独立的函数在用。请注意区别。