《密码技术与物联网安全：mbedtls开发实战》 —3.3.4　模逆运算

3.3.4　模逆运算

和普通加法运算一样，模运算中对于每个整数也存在加法逆元，或称为负数。在模运算中整数a的加法逆元b是使得(a+b)mod n=0成立的值。同样，每个整数也存在乘法逆元，或称为倒数。在模运算中整数a的乘法逆元b满足(a·b)≡1 mod n。

表3-3为模8的加法计算结果，表3-4为模8的乘法计算结果。由于加法运算和乘法运算的交换性，从表3-3或表3-4可以看出，模加法和模乘法的计算结果均关于主对角线对称。关于模8的加法逆元可以通过浏览表3-3中值为0的项获得，例如3的加法逆元为5；而乘法逆元可以通过浏览表3-4中值为1的项获得，例如3的乘法逆元为3。

表3-3　关于模8的加法运算

表3-4　关于模8的乘法运算

关于模8的乘法逆元结果可以看出，整数1、3和5存在关于模8的乘法逆元，而整数2、4和6不存在关于模8的乘法逆元，如表3-5所示。实际上，只有当a和m互为质数，也就是说gcd(a,m)=1时，才存在一个整数b且满足a·b≡1 mod m。此处3和8互为质数，5和8互为质数，而4和8并不存在互为质数的关系。

表3-5　关于模8的加法逆元和乘法逆元结果汇总

模乘法逆元可使用扩展欧几里得算法计算得到，具体算法可参考《深入浅出密码学—常用加密技术原理与应用》6.3.1节欧几里得算法和6.3.2节扩展的欧几里得算法。代码清单3-1是扩展欧几里得算法计算模乘法逆元的python脚本，可通过命令行输入参数计算得到模乘法逆元。该文件名称为eea.py，位于本书代码仓库scripts目录下。

代码清单3-1　计算模乘法逆元脚本 eea.py

import sys

n = int(sys.argv[1])

p = int(sys.argv[2])

def extended_euclid_algorithm(n, p):

    s, old_s = 0, 1

    t, old_t = 1, 0

    r, old_r = p, n

    while r != 0:

        quotient = old_r // r

        old_r, r = r, old_r - quotient * r

        old_s, s = s, old_s - quotient * s

        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t

def inverse_of(n, p):

    gcd, x, y = extended_euclid_algorithm(n, p)

    assert (n * x + p * y) % p == gcd

    if gcd != 1:

        raise ValueError(

            '{} has no multiplicative inverse '

            'modulo {}'.format(n, p))

    else:

        return x % p

print(n, "^ -1 mod", p, "=", inverse_of(n, p))

计算7 mod 23的乘法逆元的代码如下：

$ cd scripts

$ python3 eea.py 7 23

# 输出

7 ^ -1 mod 23 = 10