在模运算中,一般没有直接做模除法。模除法a/b mod m都是先计算模逆t=b-1 mod m,再计算模乘at mod m。因此本节就来讨论模逆运算该怎样实现。
求模逆的算法主要是扩展欧几里德算法。该算法的大意如下。
假设计算

。算法通过反复迭代

和

(A、C、d、e为某些待定数)而得出

,这里的迭代主要是做乘法和减法。
算法的步骤大概是这样的。开始的时候先进行初始化——取A=1,d=0,C=0,e=1,得到:

…………(3.2)
然后反复做如下迭代(为了记号的方便,迭代过程中始终让u≥v,否则,交换<1>、<2>两式):
- 取
;
- 新的<1>式 ← 老的<2>式;
- 新的<2>式 ← 老的<1>式-q×老的<2>式;
如此迭代,直到v=0为止。最后得出

,注意最后得出的A可能是负数(比如下面举的例子就是这样),此时只需要加上m即可。
下面给出用扩展欧几里德算法计算的详细描述。算法中出现的符号和上面的介绍一致,新增加的三个变量t1,t2,t3为临时变量。算法可参见[2,§4.5.2算法X]。
───────────────────────────────────────

───────────────────────────────────────
以上是一般情况下的扩展欧几里德算法。如果模数m为奇数(为了以示区别,记此时的奇模数为p),算法可以变的更加简单快捷——利用反复的右移(即除2)来代替除法。
下面来看看这个特殊的算法怎样计算

,这里的p为奇数。(也可参见[9,算法8])。
───────────────────────────────────────

───────────────────────────────────────
下面介绍的求模逆的C程序综合利用了以上两种算法:当模数是奇数而且字长小于450时,利用特殊的扩展欧几里德算法——模数为奇数的扩展欧几里德算法来进行计算,如果模数不满足这个条件,就用一般的扩展欧几里德算法来进行计算。
───────────────────────────────────────
BIGNUM *BN_mod_inverse(BIGNUM *in,const BIGNUM *a, const BIGNUM *n)
功能: 求模逆
输入: a【被模数】,n【模数】
输出: in ← 1/a mod n
返回: in【正常】 or NULL【出错】
出处: bn_gcd.c
───────────────────────────────────────
有一个特殊的模逆函数BN_mod_inverse_no_branch,它利用一些特殊的方法来防止信息泄漏,抵抗能量攻击。其算法思想类似普通的扩展欧几里德算法,但其中间用了点小技巧以防止信息泄漏,详细情况请参见原函数。
───────────────────────────────────────
static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n)
功能: 用抗能量攻击法求模逆
输入: a【被模数】,n【模数】
输出: in ← 1/a mod n
返回: in【正常】 or NULL【出错】
出处: bn_gcd.c
───────────────────────────────────────