OpenSSL密码库算法笔记——第4.1.4章模指数函数介绍

和第三章介绍的模乘法一样&＃xff0c;根据使用的模运算的不同&＃xff0c;模指数在具体实现时也分成利用经典模运算实现的模指数运算、利用Barrett模运算实现的模指数运算、利用Montgomery模运算实现的模指数运算。

首先看看利用经典模运算实现的模指数运算。

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

int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m)

功能&＃xff1a;    大数的模指数运算&＃xff08;利用经典模运算实现&＃xff09;

输入&＃xff1a;    a【基数】&＃xff0c;p【指数】&＃xff0c;m【模数】

输出&＃xff1a;    r ←    

返回&＃xff1a;    1【正常】 or 0【出错】 or &＃xff0d;1【p为CONSTTIME属性】      

出处&＃xff1a;    bn_exp.c

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

再来看看利用Barrett约化实现的模指数运算。

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

int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,const BIGNUM *m)

功能&＃xff1a;    大数的模指数运算&＃xff08;利用Barrett约化实现&＃xff09;

输入&＃xff1a;    a【基数】&＃xff0c;p【指数】&＃xff0c;m【模数】

输出&＃xff1a;    r ←    

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

出处&＃xff1a;    bn_exp.c

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

接着来看看利用Montgomery约化实现的模指数运算。注意此时需要模数为奇数&＃xff0c;否则不满足Montgomery约化的基本条件gcd(m,R)&＃61;1。

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

int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,const BIGNUM *m, BN_MONT_CTX *in_mont)

功能&＃xff1a;    大数的模指数运算&＃xff08;利用Montgomery约化实现&＃xff09;

输入&＃xff1a;    a【基数】&＃xff0c;p【指数】&＃xff0c;m【模数】&＃xff0c;in_mont【Montgomery模数】

输出&＃xff1a;    r ←    

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

出处&＃xff1a;    bn_exp.c

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

当基数a退化成一个字的时候&＃xff0c;利用Montgomery约化实现的模指数运算变成&＃xff1a;

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

int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,const BIGNUM *m, BN_MONT_CTX *in_mont)

功能&＃xff1a;    字的模指数运算&＃xff08;利用Montgomery约化实现&＃xff09;

输入&＃xff1a;    a【字】&＃xff0c;p【指数】&＃xff0c;m【模数】&＃xff0c;in_mont【Montgomery模数】

输出&＃xff1a;    r&＃xff1d; 

返回&＃xff1a;    1【正常】 or 0【出错】 or &＃xff0d;1【p为CONSTTIME属性】

出处&＃xff1a;    bn_exp.c

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

在做模指数运算时使用Barrett约化和Montgomery约化比使用经典模运算好&＃xff0c;进一步&＃xff0c;使用Montgomery约化的模指数运算应该是最优的[7]&＃xff0c;但是必需满足条件gcd(m,R)&＃61;1。

下面将要介绍的这个模指数运算综合运用了上面提到的BN_mod_exp_recp&＃xff08;利用Barrett约化实现&＃xff09;和BN_mod_exp_mont&＃xff08;利用Montgomery约化实现&＃xff09;。因为使用Montgomery约化的模指数运算是最优的&＃xff0c;所以当模数m为奇数时&＃xff0c;调用Montgomery约化实现的模指数运算BN_mod_exp_mont。当m为偶数的时候&＃xff0c;不满足Montgomery约化的基本条件gcd(m,R)&＃61;1&＃xff0c;无法使用Montgomery约化&＃xff0c;所以改为调用利用Barrett约化实现的模指BN_mod_exp_recp。

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

int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m)

功能&＃xff1a;    大数的模指数运算

输入&＃xff1a;    a【基数】&＃xff0c;p【指数】&＃xff0c;m【模数】

输出&＃xff1a;    r ←     

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

出处&＃xff1a;    bn_exp.c

备注&＃xff1a;    当m为偶数时&＃xff0c;利用Barrett约化&＃xff0c;当m为奇数时&＃xff0c;利用Montgomery约化实现。

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