Crypto.Number.ModArithmetic

Raised when two numbers are supposed to be coprimes but are not.

Raised when the assumption about the modulus is invalid.

Compute the modular exponentiation of base^exponent using algorithms design to avoid side channels and timing measurement

Modulo need to be odd otherwise the normal fast modular exponentiation is used.

With an odd modulo the work is done in C, four bits of exponent at a time: four squarings and one multiplication by a small power of the base, taken from a table of sixteen which is read by touching every entry and keeping one of them with a mask. So each group of four bits costs the same five multiplications and the same sixteen reads whatever those bits are, and nothing branches on the exponent or indexes memory with it.

What the exponent still shows is its length: it is rounded up to a whole 64-bit word and every bit of that is walked over, so its value is hidden but its size is not. The mpz_powm_sec of GMP, which GHC stopped offering in integer-gmp 1.1 and which this replaces, hides exactly as much.

The base is taken to be public -- in this library it is a ciphertext, a public value from a peer, or a generator -- and is reduced modulo the modulus in the ordinary way first.

Hiding the exponent has a price: against the windowed exponentiation of GMP, which is what this function used to end up calling, a 2048-bit modulus costs somewhat over twice as much.

Compute the modular exponentiation of base^exponent using the fastest algorithm without any consideration for hiding parameters.

Use this function when all the parameters are public, otherwise expSafe should be preferred.

inverse computes the modular inverse as in g^(-1) mod m.

inverseSafe computes the modular inverse without letting the number being inverted steer how long the work takes, which is what inverse does: the extended Euclidean algorithm takes a number of steps that follows the bits it is given, and a nonce inverted that way has been taken apart before by watching the steps go by.

The answer comes from a fixed number of division steps where the assembly for them is built, and from inverseFermat where it is not. Either way it is checked here by multiplying out: neither one says when the number has no inverse -- the first returns something that is not one and the second returns something that is not one either -- so the check is what makes this agree with inverse on every input, and inverse is asked when it fails. That fallback is reached only by parameters that are already broken.

The division steps cost about a twentieth of the exponentiation: on an Apple M4, inverting modulo the P-256 group order is 0.80 microseconds against 6.02, and modulo the P-521 one 2.05 against 63.2.

Compute the modular inverse of two coprime numbers. This is equivalent to inverse except that the result is known to exists.

If the numbers are not defined as coprime, this function will raise a CoprimesAssertionError.

Modular inverse using Fermat's little theorem. This works only when the modulus is prime but avoids side channels like in expSafe.

Computes the Jacobi symbol (a/n). 0 ≤ a < n; n ≥ 3 and odd.

The Legendre and Jacobi symbols are indistinguishable exactly when the lower argument is an odd prime, in which case they have the same value.

See algorithm 2.149 in "Handbook of Applied Cryptography" by Alfred J. Menezes et al.

Modular square root of g modulo a prime p.

If the modulus is found not to be prime, the function will raise a ModulusAssertionError.

This implementation is variable time and should be used with public parameters only.