/**
* 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 \c 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 \c A, \c B, ... are inputs, and are not
* modified by the function.
* - Bignum parameters called \c X, \c Y are outputs or input-output.
* The initial content of output-only parameters is ignored.
* - \c 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 \c 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 \c 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, \c N - 1] and guarantee outputs in the range [0, \c 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).
*/
/*
* Copyright The Mbed TLS Contributors
* SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
*/
#ifndef MBEDTLS_BIGNUM_MOD_RAW_H
#define MBEDTLS_BIGNUM_MOD_RAW_H
#include "common.h"
#if defined(MBEDTLS_BIGNUM_C)
#include "mbedtls/bignum.h"
#endif
#include "bignum_mod.h"
/**
* \brief Perform a safe conditional copy of an MPI which doesn't reveal
* whether the assignment was done or not.
*
* The size to copy is determined by \p N.
*
* \param[out] X The address of the destination MPI.
* This must be initialized. Must have enough limbs to
* store the full value of \p A.
* \param[in] A The address of the source MPI. This must be initialized.
* \param[in] N The address of the modulus related to \p X and \p A.
* \param assign The condition deciding whether to perform the
* assignment or not. Must be either 0 or 1:
* * \c 1: Perform the assignment `X = A`.
* * \c 0: Keep the original value of \p X.
*
* \note This function avoids leaking any information about whether
* the assignment was done or not.
*
* \warning If \p assign is neither 0 nor 1, the result of this function
* is indeterminate, and the resulting value in \p X might be
* neither its original value nor the value in \p A.
*/
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);
/**
* \brief 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 \p N.
*
* \param[in,out] X The address of the first MPI. This must be initialized.
* \param[in,out] Y The address of the second MPI. This must be initialized.
* \param[in] N The address of the modulus related to \p X and \p Y.
* \param swap The condition deciding whether to perform
* the swap or not. Must be either 0 or 1:
* * \c 1: Swap the values of \p X and \p Y.
* * \c 0: Keep the original values of \p X and \p Y.
*
* \note This function avoids leaking any information about whether
* the swap was done or not.
*
* \warning If \p swap is neither 0 nor 1, the result of this function
* is indeterminate, and both \p X and \p Y might end up with
* values different to either of the original ones.
*/
void mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint *X,
mbedtls_mpi_uint *Y,
const mbedtls_mpi_mod_modulus *N,
unsigned char swap);
/** 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).
*
* \param[out] X The address of the MPI. The size is determined by \p N.
* (In particular, it must have at least as many limbs as
* the modulus \p N.)
* \param[in] N The address of the modulus related to \p X.
* \param[in] input The input buffer to import from.
* \param input_length The length in bytes of \p input.
* \param ext_rep The endianness of the number in the input buffer.
*
* \return \c 0 if successful.
* \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't
* large enough to hold the value in \p input.
* \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation
* of \p N is invalid or \p X is not less than \p N.
*/
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);
/** Export A into unsigned binary data.
*
* \param[in] A The address of the MPI. The size is determined by \p N.
* (In particular, it must have at least as many limbs as
* the modulus \p N.)
* \param[in] N The address of the modulus related to \p A.
* \param[out] output The output buffer to export to.
* \param output_length The length in bytes of \p output.
* \param ext_rep The endianness in which the number should be written into the output buffer.
*
* \return \c 0 if successful.
* \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't
* large enough to hold the value of \p A.
* \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation
* of \p N is invalid.
*/
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);
/** \brief Subtract two MPIs, returning the residue modulo the specified
* modulus.
*
* The size of the operation is determined by \p N. \p A and \p B must have
* the same number of limbs as \p N.
*
* \p X may be aliased to \p A or \p B, or even both, but may not overlap
* either otherwise.
*
* \param[out] X The address of the result MPI.
* This must be initialized. Must have enough limbs to
* store the full value of the result.
* \param[in] A The address of the first MPI. This must be initialized.
* \param[in] B The address of the second MPI. This must be initialized.
* \param[in] N The address of the modulus. Used to perform a modulo
* operation on the result of the subtraction.
*/
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);
/** \brief 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 \p N. \p A, \p B and \p X must
* all be associated with the modulus \p N and must all have the same number
* of limbs as \p N.
*
* \p X may be aliased to \p A or \p B, or even both, but may not overlap
* either otherwise. They may not alias \p N (since they must be in canonical
* form, they cannot == \p N).
*
* \param[out] X The address of the result MPI. Must have the same
* number of limbs as \p N.
* On successful completion, \p X contains the result of
* the multiplication `A * B * R^-1` mod N where
* `R = 2^(biL * N->limbs)`.
* \param[in] A The address of the first MPI.
* \param[in] B The address of the second MPI.
* \param[in] N The address of the modulus. Used to perform a modulo
* operation on the result of the multiplication.
* \param[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.
*/
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);
/**
* \brief 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()`.
*
* \param 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()`.
*
* \return The number of limbs of working memory required by
* `mbedtls_mpi_mod_raw_inv_prime()`.
*/
size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs);
/**
* \brief Perform fixed-width modular inversion of a Montgomery-form MPI with
* respect to a modulus \p N that must be prime.
*
* \p X may be aliased to \p A, but not to \p N or \p RR.
*
* \param[out] X The modular inverse of \p A with respect to \p N.
* Will be in Montgomery form.
* \param[in] A The number to calculate the modular inverse of.
* Must be in Montgomery form. Must not be 0.
* \param[in] N The modulus, as a little-endian array of length \p AN_limbs.
* Must be prime.
* \param AN_limbs The number of limbs in \p A, \p N and \p RR.
* \param[in] RR The precomputed residue of 2^{2*biL} modulo N, as a little-
* endian array of length \p AN_limbs.
* \param[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 \p T when it is no
* longer needed, and before freeing it if it was dynamically
* allocated.
*/
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);
/**
* \brief 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 \p N.
*
* \p X may be aliased to \p A or \p B, or even both, but may not overlap
* either otherwise.
*
* \param[out] X The result of the modular addition.
* \param[in] A Little-endian presentation of the left operand. This
* must be smaller than \p N.
* \param[in] B Little-endian presentation of the right operand. This
* must be smaller than \p N.
* \param[in] N The address of the modulus.
*/
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);
/** Convert an MPI from canonical representation (little-endian limb array)
* to the representation associated with the modulus.
*
* \param[in,out] X The limb array to convert.
* It must have as many limbs as \p N.
* It is converted in place.
* If this function returns an error, the content of \p X
* is unspecified.
* \param[in] N The modulus structure.
*
* \return \c 0 if successful.
* Otherwise an \c MBEDTLS_ERR_MPI_xxx error code.
*/
int mbedtls_mpi_mod_raw_canonical_to_modulus_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).
*
* \param[in,out] X The limb array to convert.
* It must have as many limbs as \p N.
* It is converted in place.
* If this function returns an error, the content of \p X
* is unspecified.
* \param[in] N The modulus structure.
*
* \return \c 0 if successful.
* Otherwise an \c MBEDTLS_ERR_MPI_xxx error code.
*/
int mbedtls_mpi_mod_raw_modulus_to_canonical_rep(
mbedtls_mpi_uint *X,
const mbedtls_mpi_mod_modulus *N);
/** Generate a random number uniformly in a range.
*
* This function generates a random number between \p min inclusive and
* \p N exclusive.
*
* The procedure complies with RFC 6979 ยง3.3 (deterministic ECDSA)
* when the RNG is a suitably parametrized instance of HMAC_DRBG
* and \p min is \c 1.
*
* \note There are `N - min` possible outputs. The lower bound
* \p min can be reached, but the upper bound \p N cannot.
*
* \param X The destination MPI, in canonical representation modulo \p N.
* It must not be aliased with \p N or otherwise overlap it.
* \param min The minimum value to return. It must be strictly smaller
* than \b N.
* \param N The modulus.
* This is the upper bound of the output range, exclusive.
* \param f_rng The RNG function to use. This must not be \c NULL.
* \param p_rng The RNG parameter to be passed to \p f_rng.
*
* \return \c 0 if successful.
* \return #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 \p N
* is significantly larger than \p min, which is the case
* for all usual cryptographic applications.
*/
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);
/** Convert an MPI into Montgomery form.
*
* \param X The address of the MPI.
* Must have the same number of limbs as \p N.
* \param N The address of the modulus, which gives the size of
* the base `R` = 2^(biL*N->limbs).
*
* \return \c 0 if successful.
*/
int mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint *X,
const mbedtls_mpi_mod_modulus *N);
/** Convert an MPI back from Montgomery representation.
*
* \param X The address of the MPI.
* Must have the same number of limbs as \p N.
* \param N The address of the modulus, which gives the size of
* the base `R`= 2^(biL*N->limbs).
*
* \return \c 0 if successful.
*/
int mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint *X,
const mbedtls_mpi_mod_modulus *N);
/** \brief Perform fixed width modular negation.
*
* The size of the operation is determined by \p N. \p A must have
* the same number of limbs as \p N.
*
* \p X may be aliased to \p A.
*
* \param[out] X The result of the modular negation.
* This must be initialized.
* \param[in] A Little-endian presentation of the input operand. This
* must be less than or equal to \p N.
* \param[in] N The modulus to use.
*/
void mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint *X,
const mbedtls_mpi_uint *A,
const mbedtls_mpi_mod_modulus *N);
#endif /* MBEDTLS_BIGNUM_MOD_RAW_H */
Codebase Browser
godot