Include error handling to modular inverse

[GiacomoPope]

Description of problem

Currently, the function inverse(u,v) has no error handling for when the base and modulus are not coprime. This leads to unexpected results for bad input. This can be particularly bad for cryptographic verification which relies on the computation of the modular inverse of user input.

For example, using the current code, we can use inverse(u,v) to attempt to find the modular inverse even when the base u = 0 or when the base and modulus are not coprime gcd(u,v) != 1:

>>> p = 163
>>> for x in range(1,p):
...     x_inv = inverse(x,p)
...     assert (x*x_inv) % p == 1
x = 0; x_inv = inverse(x,p); assert (x*x_inv) % p == 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
x = 2*p; x_inv = inverse(x,p); assert (x*x_inv) % p == 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError
>>> x = p; x_inv = inverse(x,2*p); assert (x*x_inv) % (2*p) == 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError

Proposed fix

This pull request introduces an additional check after performing the extended Euclidian algorithm to ensure that the output value indeed is the modular inverse. This follows the Wikipedia pseudocode for modular inverse using xgcd.

Effectively, this check is the same as ensuring that the base u and the modulus v are coprime gcd(u,v) = 1 and raises a ValueError when this is not the case. In terms of performance, one additional integer comparison is included into the function.

def inverse(u, v):
    """The inverse of :data:`u` *mod* :data:`v`."""
    u3, v3 = u, v
    u1, v1 = 1, 0
    while v3 > 0:
        q = u3 // v3
        u1, v1 = v1, u1 - v1*q
        u3, v3 = v3, u3 - v3*q
    if u3 > 1:
        raise ValueError("base is not invertible for the given modulus")
    while u1 < 0:
        u1 = u1 + v
    return u1

With the proposed change, running the same examples as above, we see bad inputs are caught and raised as a ValueError before returning an incorrect "inverse" element.

>>> p = 163
>>> for x in range(1,p):
...     x_inv = inverse(x,p)
...     assert (x*x_inv) % p == 1
>>> x = 0; x_inv = inverse(x,p); assert (x*x_inv) % p == 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 10, in inverse
ValueError: base is not invertible for the given modulus
>>> x = 2*p; x_inv = inverse(x,p); assert (x*x_inv) % p == 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 10, in inverse
ValueError: base is not invertible for the given modulus
>>> x = p; x_inv = inverse(x,2*p); assert (x*x_inv) % (2*p) == 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 10, in inverse
ValueError: base is not invertible for the given modulus

Alignment with proposed performance enhancement

In the pull request Improve speed of GCD, size, inverse, it is proposed that for newer versions of python (from 3.8) that inverse uses the faster, native inverse.

if sys.version_info[:2] >= (3,8):
    def inverse(u,v):
        return pow(u,-1,v)
else:
    ...

This pull request will align the error handling of pycryptodomes inverse with python's pow(u,-1,v):

>>> p = 163
>>> pow(0,-1,p)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: base is not invertible for the given modulus
>>> pow(2*p,-1,p)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: base is not invertible for the given modulus

Allowing inverse(u,v) to be consistent across python versions.