#include "common.h"

Include dependency graph for bignum_mod.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	mbedtls_mpi_mod_residue

struct	mbedtls_mpi_mont_struct

struct	mbedtls_mpi_opt_red_struct

struct	mbedtls_mpi_mod_modulus

union	mbedtls_mpi_mod_modulus::rep

Typedefs
typedef int(*	mbedtls_mpi_modp_fn) (mbedtls_mpi_uint *X, size_t X_limbs)

Enumerations
enum	mbedtls_mpi_mod_rep_selector { MBEDTLS_MPI_MOD_REP_INVALID = 0 , MBEDTLS_MPI_MOD_REP_MONTGOMERY = 2 , MBEDTLS_MPI_MOD_REP_OPT_RED }

enum	mbedtls_mpi_mod_ext_rep { MBEDTLS_MPI_MOD_EXT_REP_INVALID = 0 , MBEDTLS_MPI_MOD_EXT_REP_LE = 8 , MBEDTLS_MPI_MOD_EXT_REP_BE }

Functions
int	mbedtls_mpi_mod_residue_setup (mbedtls_mpi_mod_residue r, const mbedtls_mpi_mod_modulus N, mbedtls_mpi_uint *p, size_t p_limbs)

void	mbedtls_mpi_mod_residue_release (mbedtls_mpi_mod_residue *r)

void	mbedtls_mpi_mod_modulus_init (mbedtls_mpi_mod_modulus *N)

int	mbedtls_mpi_mod_modulus_setup (mbedtls_mpi_mod_modulus N, const mbedtls_mpi_uint p, size_t p_limbs)

int	mbedtls_mpi_mod_optred_modulus_setup (mbedtls_mpi_mod_modulus N, const mbedtls_mpi_uint p, size_t p_limbs, mbedtls_mpi_modp_fn modp)

void	mbedtls_mpi_mod_modulus_free (mbedtls_mpi_mod_modulus *N)

int	mbedtls_mpi_mod_mul (mbedtls_mpi_mod_residue X, const mbedtls_mpi_mod_residue A, const mbedtls_mpi_mod_residue B, const mbedtls_mpi_mod_modulus N)
	Multiply two residues, returning the residue modulo the specified modulus.

int	mbedtls_mpi_mod_sub (mbedtls_mpi_mod_residue X, const mbedtls_mpi_mod_residue A, const mbedtls_mpi_mod_residue B, const mbedtls_mpi_mod_modulus N)
	Perform a fixed-size modular subtraction.

int	mbedtls_mpi_mod_inv (mbedtls_mpi_mod_residue X, const mbedtls_mpi_mod_residue A, const mbedtls_mpi_mod_modulus *N)
	Perform modular inversion of an MPI with respect to a modulus `N`.

int	mbedtls_mpi_mod_add (mbedtls_mpi_mod_residue X, const mbedtls_mpi_mod_residue A, const mbedtls_mpi_mod_residue B, const mbedtls_mpi_mod_modulus N)
	Perform a fixed-size modular addition.

int	mbedtls_mpi_mod_random (mbedtls_mpi_mod_residue X, mbedtls_mpi_uint min, const mbedtls_mpi_mod_modulus N, int(f_rng)(void , unsigned char , size_t), void p_rng)

int	mbedtls_mpi_mod_read (mbedtls_mpi_mod_residue r, const mbedtls_mpi_mod_modulus N, const unsigned char *buf, size_t buflen, mbedtls_mpi_mod_ext_rep ext_rep)

int	mbedtls_mpi_mod_write (const mbedtls_mpi_mod_residue r, const mbedtls_mpi_mod_modulus N, unsigned char *buf, size_t buflen, mbedtls_mpi_mod_ext_rep ext_rep)

Typedef Documentation

◆ mbedtls_mpi_modp_fn

typedef int(* mbedtls_mpi_modp_fn) (mbedtls_mpi_uint *X, size_t X_limbs)

Enumeration Type Documentation

◆ mbedtls_mpi_mod_ext_rep

enum mbedtls_mpi_mod_ext_rep

Enumerator
MBEDTLS_MPI_MOD_EXT_REP_INVALID
MBEDTLS_MPI_MOD_EXT_REP_LE
MBEDTLS_MPI_MOD_EXT_REP_BE

◆ mbedtls_mpi_mod_rep_selector

enum mbedtls_mpi_mod_rep_selector

Modular bignum functions

This module implements operations on integers modulo some fixed modulus.

The functions in this module obey the following conventions unless explicitly indicated otherwise:

Modulus parameters: the modulus is passed as a pointer to a structure of type mbedtls_mpi_mod_modulus. The structure must be set up with an array of limbs storing the bignum value of the modulus. The modulus must be odd and is assumed to have no leading zeroes. The modulus is usually named N and is usually input-only. Functions which take a parameter of type const mbedtls_mpi_mod_modulus* must not modify its value.
Bignum parameters: Bignums are passed as pointers to an array of limbs or to a mbedtls_mpi_mod_residue structure. A limb has the type mbedtls_mpi_uint. Residues must be initialized before use, and must be associated with the modulus N. Unless otherwise specified:
- Bignum parameters called A, B, ... are inputs and are not modified by the function. Functions which take a parameter of type const mbedtls_mpi_mod_residue* must not modify its value.
- Bignum parameters called X, Y, ... are outputs or input-output. The initial bignum value of output-only parameters is ignored, but they must be set up and associated with the modulus N. Some functions (typically constant-flow) require that the limbs in an output residue are initialized.
- Bignum parameters called p are inputs used to set up a modulus or residue. These must be pointers to an array of limbs.
- T is a temporary storage area. The initial content of such a parameter is ignored and the final content is unspecified.
- Some functions use different names, such as r for the residue.
Bignum sizes: bignum sizes are always expressed in limbs. Both mbedtls_mpi_mod_modulus and mbedtls_mpi_mod_residue have a limbs member storing its size. All bignum parameters must have the same number of limbs as the modulus. All bignum sizes must be at least 1 and must be significantly less than SIZE_MAX. The behavior if a size is 0 is undefined.
Bignum representation: the representation of inputs and outputs is specified by the int_rep field of the modulus.
Parameter ordering: for bignum parameters, outputs come before inputs. The modulus is passed after residues. Temporaries come last.
Aliasing: in general, output bignums may be aliased to one or more inputs. Modulus values may not be aliased to any other parameter. Outputs may not be aliased to one another. Temporaries may not be aliased to any other parameter.
Overlap: apart from aliasing of residue pointers (where two residue arguments are equal pointers), overlap is not supported and may result in undefined behavior.
Error handling: functions generally check compatibility of input sizes. Most functions will not check that input values are in canonical form (i.e. that A < N), this is only checked during setup of a residue structure.
Modular representatives: all functions expect inputs to be in the range [0, N - 1] and guarantee outputs in the range [0, N - 1]. Residues are set up with an associated modulus, and operations are only guaranteed to work if the modulus is associated with all residue parameters. If a residue is passed with a modulus other than the one it is associated with, then it may be out of range. If an input is out of range, outputs are fully unspecified, though bignum values out of range should not cause buffer overflows (beware that this is not extensively tested). How residues associated with a modulus are represented.

This also determines which fields of the modulus structure are valid and what their contents are (see mbedtls_mpi_mod_modulus).

Enumerator
MBEDTLS_MPI_MOD_REP_INVALID	Representation not chosen (makes the modulus structure invalid).
MBEDTLS_MPI_MOD_REP_MONTGOMERY	Montgomery representation.
MBEDTLS_MPI_MOD_REP_OPT_RED

Function Documentation

◆ mbedtls_mpi_mod_add()

int mbedtls_mpi_mod_add	(	mbedtls_mpi_mod_residue *	X,
		const mbedtls_mpi_mod_residue *	A,
		const mbedtls_mpi_mod_residue *	B,
		const mbedtls_mpi_mod_modulus *	N
	)

Perform a fixed-size modular addition.

Calculate A + B modulo N.

A, B and X must all be associated with the modulus N and must all have the same number of limbs as N.

X may be aliased to A or B, or even both, but may not overlap either otherwise.

Note: This function does not check that A or B are in canonical form (that is, are < N) - that will have been done by mbedtls_mpi_mod_residue_setup().

Parameters

[out]	X	The address of the result residue. Must be initialized. Must have the same number of limbs as the modulus `N`.
[in]	A	The address of the first input residue.
[in]	B	The address of the second input residue.
[in]	N	The address of the modulus. Used to perform a modulo operation on the result of the addition.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the given MPIs do not have the correct number of limbs.

◆ mbedtls_mpi_mod_inv()

int mbedtls_mpi_mod_inv	(	mbedtls_mpi_mod_residue *	X,
		const mbedtls_mpi_mod_residue *	A,
		const mbedtls_mpi_mod_modulus *	N
	)

Perform modular inversion of an MPI with respect to a modulus N.

A and X must be associated with the modulus N and will therefore have the same number of limbs as N.

X may be aliased to A.

Warning: Currently only supports prime moduli, but does not check for them.

Parameters

[out]	X	The modular inverse of `A` with respect to `N`.
[in]	A	The number to calculate the modular inverse of. Must not be 0.
[in]	N	The modulus to use.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if A and N do not have the same number of limbs.; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if A is zero.; MBEDTLS_ERR_MPI_ALLOC_FAILED if couldn't allocate enough memory (needed for conversion to and from Mongtomery form when not in Montgomery form already, and for temporary use by the inversion calculation itself).

◆ mbedtls_mpi_mod_modulus_free()

void mbedtls_mpi_mod_modulus_free ( mbedtls_mpi_mod_modulus * N )

Free elements of a modulus structure.

This function frees any memory allocated by mbedtls_mpi_mod_modulus_setup().

Warning: This function does not free the limb array passed to mbedtls_mpi_mod_modulus_setup() only removes the reference to it, making it safe to free or to use it again.

Parameters

[in,out] N The address of the modulus structure to free.

◆ mbedtls_mpi_mod_modulus_init()

void mbedtls_mpi_mod_modulus_init ( mbedtls_mpi_mod_modulus * N )

Initialize a modulus structure.

Parameters

[out] N The address of the modulus structure to initialize.

◆ mbedtls_mpi_mod_modulus_setup()

int mbedtls_mpi_mod_modulus_setup	(	mbedtls_mpi_mod_modulus *	N,
		const mbedtls_mpi_uint *	p,
		size_t	p_limbs
	)

Setup a modulus structure.

Parameters

[out]	N	The address of the modulus structure to populate.
[in]	p	The address of the limb array storing the value of `N`. The memory pointed to by `p` will be used by `N` and must not be modified in any way until after mbedtls_mpi_mod_modulus_free() is called.
	p_limbs	The number of limbs of `p`.

Returns: 0 if successful.

◆ mbedtls_mpi_mod_mul()

int mbedtls_mpi_mod_mul	(	mbedtls_mpi_mod_residue *	X,
		const mbedtls_mpi_mod_residue *	A,
		const mbedtls_mpi_mod_residue *	B,
		const mbedtls_mpi_mod_modulus *	N
	)

Multiply two residues, returning the residue modulo the specified modulus.

Note: Currently handles the case when N->int_rep is MBEDTLS_MPI_MOD_REP_MONTGOMERY.

The size of the operation is determined by N. A, B and X must all be associated with the modulus N and must all have the same number of limbs as N.

X may be aliased to A or B, or even both, but may not overlap either otherwise. They may not alias N (since they must be in canonical form, they cannot == N).

Parameters

[out]	X	The address of the result MPI. Must have the same number of limbs as `N`. On successful completion, `X` contains the result of the multiplication `A * B * R^-1` mod N where `R = 2^(biL * N->limbs)`.
[in]	A	The address of the first MPI.
[in]	B	The address of the second MPI.
[in]	N	The address of the modulus. Used to perform a modulo operation on the result of the multiplication.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if all the parameters do not have the same number of limbs or N is invalid.; MBEDTLS_ERR_MPI_ALLOC_FAILED on memory-allocation failure.

◆ mbedtls_mpi_mod_optred_modulus_setup()

int mbedtls_mpi_mod_optred_modulus_setup	(	mbedtls_mpi_mod_modulus *	N,
		const mbedtls_mpi_uint *	p,
		size_t	p_limbs,
		mbedtls_mpi_modp_fn	modp
	)

Setup an optimised-reduction compatible modulus structure.

Parameters

[out]	N	The address of the modulus structure to populate.
[in]	p	The address of the limb array storing the value of `N`. The memory pointed to by `p` will be used by `N` and must not be modified in any way until after mbedtls_mpi_mod_modulus_free() is called.
	p_limbs	The number of limbs of `p`.
	modp	A pointer to the optimised reduction function to use. `p`.

Returns: 0 if successful.

◆ mbedtls_mpi_mod_random()

int mbedtls_mpi_mod_random	(	mbedtls_mpi_mod_residue *	X,
		mbedtls_mpi_uint	min,
		const mbedtls_mpi_mod_modulus *	N,
		int()(void , unsigned char *, size_t)	f_rng,
		void *	p_rng
	)

Generate a random number uniformly in a range.

This function generates a random number between min inclusive and N exclusive.

The procedure complies with RFC 6979 §3.3 (deterministic ECDSA) when the RNG is a suitably parametrized instance of HMAC_DRBG and min is 1.

Note: There are N - min possible outputs. The lower bound min can be reached, but the upper bound N cannot.

Parameters

X	The destination residue.
min	The minimum value to return. It must be strictly smaller than N.
N	The modulus. This is the upper bound of the output range, exclusive.
f_rng	The RNG function to use. This must not be `NULL`.
p_rng	The RNG parameter to be passed to `f_rng`.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was unable to find a suitable value within a limited number of attempts. This has a negligible probability if N is significantly larger than min, which is the case for all usual cryptographic applications.

◆ mbedtls_mpi_mod_read()

int mbedtls_mpi_mod_read	(	mbedtls_mpi_mod_residue *	r,
		const mbedtls_mpi_mod_modulus *	N,
		const unsigned char *	buf,
		size_t	buflen,
		mbedtls_mpi_mod_ext_rep	ext_rep
	)

Read a residue from a byte buffer.

The residue will be automatically converted to the internal representation based on the value of the N->int_rep field.

The modulus N will be the modulus associated with r. The residue r should only be used in operations where the modulus is N or a modulus equivalent to N (in the sense that all their fields or memory pointed by their fields hold the same value).

Parameters

[out]	r	The address of the residue. It must have exactly the same number of limbs as the modulus `N`.
[in]	N	The address of the modulus.
[in]	buf	The input buffer to import from.
	buflen	The length in bytes of `buf`.
	ext_rep	The endianness of the number in the input buffer.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if r isn't large enough to hold the value in buf.; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if ext_rep is invalid or the value in the buffer is not less than N.

◆ mbedtls_mpi_mod_residue_release()

void mbedtls_mpi_mod_residue_release ( mbedtls_mpi_mod_residue * r )

Unbind elements of a residue structure.

This function removes the reference to the limb array that was passed to mbedtls_mpi_mod_residue_setup() to make it safe to free or use again.

This function invalidates r and it must not be used until after mbedtls_mpi_mod_residue_setup() is called on it again.

Parameters

[out] r The address of residue to release.

◆ mbedtls_mpi_mod_residue_setup()

int mbedtls_mpi_mod_residue_setup	(	mbedtls_mpi_mod_residue *	r,
		const mbedtls_mpi_mod_modulus *	N,
		mbedtls_mpi_uint *	p,
		size_t	p_limbs
	)

Setup a residue structure.

The residue will be set up with the buffer p and modulus N.

The memory pointed to by p will be used by the resulting residue structure. The value at the pointed-to memory will be the initial value of r and must hold a value that is less than the modulus. This value will be used as-is and interpreted according to the value of the N->int_rep field.

The modulus N will be the modulus associated with r. The residue r should only be used in operations where the modulus is N.

Parameters

[out]	r	The address of the residue to setup.
[in]	N	The address of the modulus related to `r`.
[in]	p	The address of the limb array containing the value of `r`. The memory pointed to by `p` will be used by `r` and must not be modified in any way until after mbedtls_mpi_mod_residue_release() is called. The data pointed to by `p` must be less than the modulus (the value pointed to by `N->p`) and already in the representation indicated by `N->int_rep`.
	p_limbs	The number of limbs of `p`. Must be the same as the number of limbs in the modulus `N`.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if p_limbs is less than the limbs in N or if p is not less than N.

◆ mbedtls_mpi_mod_sub()

int mbedtls_mpi_mod_sub	(	mbedtls_mpi_mod_residue *	X,
		const mbedtls_mpi_mod_residue *	A,
		const mbedtls_mpi_mod_residue *	B,
		const mbedtls_mpi_mod_modulus *	N
	)

Perform a fixed-size modular subtraction.

Calculate A - B modulo N.

A, B and X must all have the same number of limbs as N.

X may be aliased to A or B, or even both, but may not overlap either otherwise.

Note: This function does not check that A or B are in canonical form (that is, are < N) - that will have been done by mbedtls_mpi_mod_residue_setup().

Parameters

[out]	X	The address of the result MPI. Must be initialized. Must have the same number of limbs as the modulus `N`.
[in]	A	The address of the first MPI.
[in]	B	The address of the second MPI.
[in]	N	The address of the modulus. Used to perform a modulo operation on the result of the subtraction.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the given MPIs do not have the correct number of limbs.

◆ mbedtls_mpi_mod_write()

int mbedtls_mpi_mod_write	(	const mbedtls_mpi_mod_residue *	r,
		const mbedtls_mpi_mod_modulus *	N,
		unsigned char *	buf,
		size_t	buflen,
		mbedtls_mpi_mod_ext_rep	ext_rep
	)

Write a residue into a byte buffer.

The modulus N must be the modulus associated with r (see mbedtls_mpi_mod_residue_setup() and mbedtls_mpi_mod_read()).

The residue will be automatically converted from the internal representation based on the value of N->int_rep field.

Warning: If the buffer is smaller than N->bits, the number of leading zeroes is leaked through timing. If r is secret, the caller must ensure that buflen is at least (N->bits+7)/8.

Parameters

[in]	r	The address of the residue. It must have the same number of limbs as the modulus `N`. (`r` is an input parameter, but its value will be modified during execution and restored before the function returns.)
[in]	N	The address of the modulus associated with `r`.
[out]	buf	The output buffer to export to.
	buflen	The length in bytes of `buf`.
	ext_rep	The endianness in which the number should be written into the output buffer.

Returns: 0 if successful.; MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if buf isn't large enough to hold the value of r (without leading zeroes).; MBEDTLS_ERR_MPI_BAD_INPUT_DATA if ext_rep is invalid.; MBEDTLS_ERR_MPI_ALLOC_FAILED if couldn't allocate enough memory for conversion. Can occur only for moduli with MBEDTLS_MPI_MOD_REP_MONTGOMERY.

Classes

Typedefs

Enumerations

Functions

Typedef Documentation

◆ mbedtls_mpi_modp_fn

Enumeration Type Documentation

◆ mbedtls_mpi_mod_ext_rep

◆ mbedtls_mpi_mod_rep_selector

Function Documentation

◆ mbedtls_mpi_mod_add()

◆ mbedtls_mpi_mod_inv()

◆ mbedtls_mpi_mod_modulus_free()

◆ mbedtls_mpi_mod_modulus_init()

◆ mbedtls_mpi_mod_modulus_setup()

◆ mbedtls_mpi_mod_mul()

◆ mbedtls_mpi_mod_optred_modulus_setup()

◆ mbedtls_mpi_mod_random()

◆ mbedtls_mpi_mod_read()

◆ mbedtls_mpi_mod_residue_release()

◆ mbedtls_mpi_mod_residue_setup()

◆ mbedtls_mpi_mod_sub()

◆ mbedtls_mpi_mod_write()