bignum_mod_raw.h File Reference

#include "common.h"
#include "bignum_mod.h"

Include dependency graph for bignum_mod_raw.h:

Go to the source code of this file.

Functions
void	mbedtls_mpi_mod_raw_cond_assign (mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_mod_modulus *N, unsigned char assign)
	Perform a safe conditional copy of an MPI which doesn't reveal whether the assignment was done or not.
void	mbedtls_mpi_mod_raw_cond_swap (mbedtls_mpi_uint *X, mbedtls_mpi_uint *Y, const mbedtls_mpi_mod_modulus *N, unsigned char swap)
	Perform a safe conditional swap of two MPIs which doesn't reveal whether the swap was done or not.
int	mbedtls_mpi_mod_raw_read (mbedtls_mpi_uint *X, const mbedtls_mpi_mod_modulus *N, const unsigned char *input, size_t input_length, mbedtls_mpi_mod_ext_rep ext_rep)
int	mbedtls_mpi_mod_raw_write (const mbedtls_mpi_uint *A, const mbedtls_mpi_mod_modulus *N, unsigned char *output, size_t output_length, mbedtls_mpi_mod_ext_rep ext_rep)
void	mbedtls_mpi_mod_raw_sub (mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *B, const mbedtls_mpi_mod_modulus *N)
	Subtract two MPIs, returning the residue modulo the specified modulus.
void	mbedtls_mpi_mod_raw_mul (mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *B, const mbedtls_mpi_mod_modulus *N, mbedtls_mpi_uint *T)
	Multiply two MPIs, returning the residue modulo the specified modulus.
size_t	mbedtls_mpi_mod_raw_inv_prime_working_limbs (size_t AN_limbs)
	Returns the number of limbs of working memory required for a call to mbedtls_mpi_mod_raw_inv_prime().
void	mbedtls_mpi_mod_raw_inv_prime (mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *N, size_t AN_limbs, const mbedtls_mpi_uint *RR, mbedtls_mpi_uint *T)
	Perform fixed-width modular inversion of a Montgomery-form MPI with respect to a modulus N that must be prime.
void	mbedtls_mpi_mod_raw_add (mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_uint *B, const mbedtls_mpi_mod_modulus *N)
	Perform a known-size modular addition.
int	mbedtls_mpi_mod_raw_canonical_to_modulus_rep (mbedtls_mpi_uint *X, const mbedtls_mpi_mod_modulus *N)
int	mbedtls_mpi_mod_raw_modulus_to_canonical_rep (mbedtls_mpi_uint *X, const mbedtls_mpi_mod_modulus *N)
int	mbedtls_mpi_mod_raw_random (mbedtls_mpi_uint *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_raw_to_mont_rep (mbedtls_mpi_uint *X, const mbedtls_mpi_mod_modulus *N)
int	mbedtls_mpi_mod_raw_from_mont_rep (mbedtls_mpi_uint *X, const mbedtls_mpi_mod_modulus *N)
void	mbedtls_mpi_mod_raw_neg (mbedtls_mpi_uint *X, const mbedtls_mpi_uint *A, const mbedtls_mpi_mod_modulus *N)
	Perform fixed width modular negation.

Function Documentation

mbedtls_mpi_mod_raw_add()

void mbedtls_mpi_mod_raw_add	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_uint *	A,
		const mbedtls_mpi_uint *	B,
		const mbedtls_mpi_mod_modulus *	N
	)

Perform a known-size modular addition.

Calculate A + B modulo N.

The number of limbs in each operand, and the result, is given by the modulus N.

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

Parameters

[out]	X	The result of the modular addition.
[in]	A	Little-endian presentation of the left operand. This must be smaller than N.
[in]	B	Little-endian presentation of the right operand. This must be smaller than N.
[in]	N	The address of the modulus.

mbedtls_mpi_mod_raw_canonical_to_modulus_rep()

int mbedtls_mpi_mod_raw_canonical_to_modulus_rep	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_mod_modulus *	N
	)

Convert an MPI from canonical representation (little-endian limb array) to the representation associated with the modulus.

Parameters

[in,out]	X	The limb array to convert. It must have as many limbs as N. It is converted in place. If this function returns an error, the content of X is unspecified.
[in]	N	The modulus structure.

Returns

0 if successful. Otherwise an MBEDTLS_ERR_MPI_xxx error code.

mbedtls_mpi_mod_raw_cond_assign()

void mbedtls_mpi_mod_raw_cond_assign	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_uint *	A,
		const mbedtls_mpi_mod_modulus *	N,
		unsigned char	assign
	)

Perform a safe conditional copy of an MPI which doesn't reveal whether the assignment was done or not.

Low-level modular bignum functions

This interface should only be used by the higher-level modular bignum module (bignum_mod.c) and the ECP module (ecp.c, ecp_curves.c). All other modules should use the high-level modular bignum interface (bignum_mod.h) or the legacy bignum interface (bignum.h).

This is a low-level interface to operations on integers modulo which has no protection against passing invalid arguments such as arrays of the wrong size. The functions in bignum_mod.h provide a higher-level interface that includes protections against accidental misuse, at the expense of code size and sometimes more cumbersome memory management.

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.
• Bignum parameters: Bignums are passed as pointers to an array of limbs. A limb has the type mbedtls_mpi_uint. Unless otherwise specified:
  • Bignum parameters called A, B, ... are inputs, and are not modified by the function.
  • Bignum parameters called X, Y are outputs or input-output. The initial content of output-only parameters is ignored.
  • T is a temporary storage area. The initial content of such a parameter is ignored and the final content is unspecified.
• Bignum sizes: bignum sizes are usually expressed by the limbs member of the modulus argument. 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 for arithmetic functions. Utility functions may allow for different representation.
• Parameter ordering: for bignum parameters, outputs come before inputs. The modulus is passed after other bignum input parameters. 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 limb array pointers (where two arguments are equal pointers), overlap is not supported and may result in undefined behavior.
• Error handling: This is a low-level module. Functions generally do not try to protect against invalid arguments such as nonsensical sizes or null pointers. Note that passing bignums with a different size than the modulus may lead to buffer overflows. Some functions which allocate memory or handle reading/writing of bignums will return an error if memory allocation fails or if buffer sizes are invalid.
• Modular representatives: all functions expect inputs to be in the range [0, N - 1] and guarantee outputs in the range [0, N - 1]. 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).

The size to copy is determined by N.

Parameters

[out]	X	The address of the destination MPI. This must be initialized. Must have enough limbs to store the full value of A.
[in]	A	The address of the source MPI. This must be initialized.
[in]	N	The address of the modulus related to X and A.
	assign	The condition deciding whether to perform the assignment or not. Must be either 0 or 1: 1: Perform the assignment X = A. 0: Keep the original value of X.

Note

This function avoids leaking any information about whether the assignment was done or not.

Warning

If assign is neither 0 nor 1, the result of this function is indeterminate, and the resulting value in X might be neither its original value nor the value in A.

mbedtls_mpi_mod_raw_cond_swap()

void mbedtls_mpi_mod_raw_cond_swap	(	mbedtls_mpi_uint *	X,
		mbedtls_mpi_uint *	Y,
		const mbedtls_mpi_mod_modulus *	N,
		unsigned char	swap
	)

Perform a safe conditional swap of two MPIs which doesn't reveal whether the swap was done or not.

The size to swap is determined by N.

Parameters

[in,out]	X	The address of the first MPI. This must be initialized.
[in,out]	Y	The address of the second MPI. This must be initialized.
[in]	N	The address of the modulus related to X and Y.
	swap	The condition deciding whether to perform the swap or not. Must be either 0 or 1: 1: Swap the values of X and Y. 0: Keep the original values of X and Y.

Note

This function avoids leaking any information about whether the swap was done or not.

Warning

If swap is neither 0 nor 1, the result of this function is indeterminate, and both X and Y might end up with values different to either of the original ones.

mbedtls_mpi_mod_raw_from_mont_rep()

int mbedtls_mpi_mod_raw_from_mont_rep	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_mod_modulus *	N
	)

Convert an MPI back from Montgomery representation.

Parameters

X	The address of the MPI. Must have the same number of limbs as N.
N	The address of the modulus, which gives the size of the base R= 2^(biL*N->limbs).

Returns

0 if successful.

mbedtls_mpi_mod_raw_inv_prime()

void mbedtls_mpi_mod_raw_inv_prime	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_uint *	A,
		const mbedtls_mpi_uint *	N,
		size_t	AN_limbs,
		const mbedtls_mpi_uint *	RR,
		mbedtls_mpi_uint *	T
	)

Perform fixed-width modular inversion of a Montgomery-form MPI with respect to a modulus N that must be prime.

X may be aliased to A, but not to N or RR.

Parameters

[out]	X	The modular inverse of A with respect to N. Will be in Montgomery form.
[in]	A	The number to calculate the modular inverse of. Must be in Montgomery form. Must not be 0.
[in]	N	The modulus, as a little-endian array of length AN_limbs. Must be prime.
	AN_limbs	The number of limbs in A, N and RR.
[in]	RR	The precomputed residue of 2^{2*biL} modulo N, as a little- endian array of length AN_limbs.
[in,out]	T	Temporary storage of at least the number of limbs returned by mbedtls_mpi_mod_raw_inv_prime_working_limbs(). Its initial content is unused and its final content is indeterminate. It must not alias or otherwise overlap any of the other parameters. It is up to the caller to zeroize T when it is no longer needed, and before freeing it if it was dynamically allocated.

mbedtls_mpi_mod_raw_inv_prime_working_limbs()

size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs

(

size_t

AN_limbs

)

Returns the number of limbs of working memory required for a call to mbedtls_mpi_mod_raw_inv_prime().

Note

This will always be at least mbedtls_mpi_core_montmul_working_limbs(AN_limbs), i.e. sufficient for a call to mbedtls_mpi_core_montmul().

Parameters

AN_limbs

The number of limbs in the input A and the modulus N (they must be the same size) that will be given to mbedtls_mpi_mod_raw_inv_prime().

Returns

The number of limbs of working memory required by mbedtls_mpi_mod_raw_inv_prime().

mbedtls_mpi_mod_raw_modulus_to_canonical_rep()

int mbedtls_mpi_mod_raw_modulus_to_canonical_rep	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_mod_modulus *	N
	)

Convert an MPI from the representation associated with the modulus to canonical representation (little-endian limb array).

Parameters

[in,out]	X	The limb array to convert. It must have as many limbs as N. It is converted in place. If this function returns an error, the content of X is unspecified.
[in]	N	The modulus structure.

Returns

0 if successful. Otherwise an MBEDTLS_ERR_MPI_xxx error code.

mbedtls_mpi_mod_raw_mul()

void mbedtls_mpi_mod_raw_mul	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_uint *	A,
		const mbedtls_mpi_uint *	B,
		const mbedtls_mpi_mod_modulus *	N,
		mbedtls_mpi_uint *	T
	)

Multiply two MPIs, 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.
[in,out]	T	Temporary storage of size at least 2 * N->limbs + 1 limbs. Its initial content is unused and its final content is indeterminate. It must not alias or otherwise overlap any of the other parameters.

mbedtls_mpi_mod_raw_neg()

void mbedtls_mpi_mod_raw_neg	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_uint *	A,
		const mbedtls_mpi_mod_modulus *	N
	)

Perform fixed width modular negation.

The size of the operation is determined by N. A must have the same number of limbs as N.

X may be aliased to A.

Parameters

[out]	X	The result of the modular negation. This must be initialized.
[in]	A	Little-endian presentation of the input operand. This must be less than or equal to N.
[in]	N	The modulus to use.

mbedtls_mpi_mod_raw_random()

int mbedtls_mpi_mod_raw_random	(	mbedtls_mpi_uint *	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 MPI, in canonical representation modulo N. It must not be aliased with N or otherwise overlap it.
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_raw_read()

int mbedtls_mpi_mod_raw_read	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_mod_modulus *	N,
		const unsigned char *	input,
		size_t	input_length,
		mbedtls_mpi_mod_ext_rep	ext_rep
	)

Import X from unsigned binary data.

The MPI needs to have enough limbs to store the full value (including any most significant zero bytes in the input).

Parameters

[out]	X	The address of the MPI. The size is determined by N. (In particular, it must have at least as many limbs as the modulus N.)
[in]	N	The address of the modulus related to X.
[in]	input	The input buffer to import from.
	input_length	The length in bytes of input.
	ext_rep	The endianness of the number in the input buffer.

Returns

0 if successful.

MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if X isn't large enough to hold the value in input.

MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation of N is invalid or X is not less than N.

mbedtls_mpi_mod_raw_sub()

void mbedtls_mpi_mod_raw_sub	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_uint *	A,
		const mbedtls_mpi_uint *	B,
		const mbedtls_mpi_mod_modulus *	N
	)

Subtract two MPIs, returning the residue modulo the specified modulus.

The size of the operation is determined by N. A and B must 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.

Parameters

[out]	X	The address of the result MPI. This must be initialized. Must have enough limbs to store the full value of the result.
[in]	A	The address of the first MPI. This must be initialized.
[in]	B	The address of the second MPI. This must be initialized.
[in]	N	The address of the modulus. Used to perform a modulo operation on the result of the subtraction.

mbedtls_mpi_mod_raw_to_mont_rep()

int mbedtls_mpi_mod_raw_to_mont_rep	(	mbedtls_mpi_uint *	X,
		const mbedtls_mpi_mod_modulus *	N
	)

Convert an MPI into Montgomery form.

Parameters

X	The address of the MPI. Must have the same number of limbs as N.
N	The address of the modulus, which gives the size of the base R = 2^(biL*N->limbs).

Returns

0 if successful.

mbedtls_mpi_mod_raw_write()

int mbedtls_mpi_mod_raw_write	(	const mbedtls_mpi_uint *	A,
		const mbedtls_mpi_mod_modulus *	N,
		unsigned char *	output,
		size_t	output_length,
		mbedtls_mpi_mod_ext_rep	ext_rep
	)

Export A into unsigned binary data.

Parameters

[in]	A	The address of the MPI. The size is determined by N. (In particular, it must have at least as many limbs as the modulus N.)
[in]	N	The address of the modulus related to A.
[out]	output	The output buffer to export to.
	output_length	The length in bytes of output.
	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 output isn't large enough to hold the value of A.

MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation of N is invalid.