mbedtls/library/bignum_mod.h

9  * - **Modulus parameters**: the modulus is passed as a pointer to a structure
13  *   named \c N and is usually input-only. Functions which take a parameter
15  * - **Bignum parameters**: Bignums are passed as pointers to an array of
18  *   associated with the modulus \c N. Unless otherwise specified:
19  *     - Bignum parameters called \c A, \c B, ... are inputs and are not
22  *     - Bignum parameters called \c X, \c Y, ... are outputs or input-output.
23  *       The initial bignum value of output-only parameters is ignored, but
24  *       they must be set up and associated with the modulus \c N. Some
25  *       functions (typically constant-flow) require that the limbs in an
27  *     - Bignum parameters called \c p are inputs used to set up a modulus or
29  *     - \c T is a temporary storage area. The initial content of such a
31  *     - Some functions use different names, such as \c r for the residue.
32  * - **Bignum sizes**: bignum sizes are always expressed in limbs. Both
38  * - **Bignum representation**: the representation of inputs and outputs is
40  * - **Parameter ordering**: for bignum parameters, outputs come before inputs.
42  * - **Aliasing**: in general, output bignums may be aliased to one or more
46  * - **Overlap**: apart from aliasing of residue pointers (where two residue
49  * - **Error handling**: functions generally check compatibility of input
51  *   form (i.e. that \c A < \c N), this is only checked during setup of a
53  * - **Modular representatives**: all functions expect inputs to be in the
54  *   range [0, \c N - 1] and guarantee outputs in the range [0, \c N - 1].
66  *  SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
91      * - A nist curve (MBEDTLS_ECP_DP_SECPXXXR1_ENABLED) & MBEDTLS_ECP_NIST_OPTIM.
92      * - A Kobliz Curve.
93      * - A Fast Reduction Curve CURVE25519 or CURVE448. */
111     mbedtls_mpi_uint const *rr;  /* The residue for 2^{2*n*biL} mod N */
112     mbedtls_mpi_uint mm;         /* Montgomery const for -N^{-1} mod 2^{ciL} */
136  * The residue will be set up with the buffer \p p and modulus \p N.
139  * The value at the pointed-to memory will be the initial value of \p r and must
140  * hold a value that is less than the modulus. This value will be used as-is
141  * and interpreted according to the value of the `N->int_rep` field.
143  * The modulus \p N will be the modulus associated with \p r. The residue \p r
144  * should only be used in operations where the modulus is \p N.
147  * \param[in] N     The address of the modulus related to \p r.
153  *                  pointed to by `N->p`) and already in the representation
154  *                  indicated by `N->int_rep`.
156  *                  of limbs in the modulus \p N.
160  *              limbs in \p N or if \p p is not less than \p N.
163                                   const mbedtls_mpi_mod_modulus *N,
181  * \param[out] N     The address of the modulus structure to initialize.
183 void mbedtls_mpi_mod_modulus_init(mbedtls_mpi_mod_modulus *N);
187  * \param[out] N    The address of the modulus structure to populate.
188  * \param[in] p     The address of the limb array storing the value of \p N.
189  *                  The memory pointed to by \p p will be used by \p N and must
196 int mbedtls_mpi_mod_modulus_setup(mbedtls_mpi_mod_modulus *N,
200 /** Setup an optimised-reduction compatible modulus structure.
202  * \param[out] N    The address of the modulus structure to populate.
203  * \param[in] p     The address of the limb array storing the value of \p N.
204  *                  The memory pointed to by \p p will be used by \p N and must
212 int mbedtls_mpi_mod_optred_modulus_setup(mbedtls_mpi_mod_modulus *N,
225  * \param[in,out] N     The address of the modulus structure to free.
227 void mbedtls_mpi_mod_modulus_free(mbedtls_mpi_mod_modulus *N);
232  * \note Currently handles the case when `N->int_rep` is
235  * The size of the operation is determined by \p N. \p A, \p B and \p X must
236  * all be associated with the modulus \p N and must all have the same number
237  * of limbs as \p N.
240  * either otherwise. They may not alias \p N (since they must be in canonical
241  * form, they cannot == \p N).
244  *                      number of limbs as \p N.
246  *                      the multiplication `A * B * R^-1` mod N where
247  *                      `R = 2^(biL * N->limbs)`.
250  * \param[in]  N        The address of the modulus. Used to perform a modulo
255  *              have the same number of limbs or \p N is invalid.
256  * \return      #MBEDTLS_ERR_MPI_ALLOC_FAILED on memory-allocation failure.
261                         const mbedtls_mpi_mod_modulus *N);
264  * \brief Perform a fixed-size modular subtraction.
266  * Calculate `A - B modulo N`.
268  * \p A, \p B and \p X must all have the same number of limbs as \p N.
274  *       form (that is, are < \p N) - that will have been done by
278  *                  Must have the same number of limbs as the modulus \p N.
281  * \param[in]  N    The address of the modulus. Used to perform a modulo
291                         const mbedtls_mpi_mod_modulus *N);
294  * \brief Perform modular inversion of an MPI with respect to a modulus \p N.
296  * \p A and \p X must be associated with the modulus \p N and will therefore
297  * have the same number of limbs as \p N.
303  * \param[out] X   The modular inverse of \p A with respect to \p N.
306  * \param[in] N    The modulus to use.
309  * \return         #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p A and \p N do not
320                         const mbedtls_mpi_mod_modulus *N);
322  * \brief Perform a fixed-size modular addition.
324  * Calculate `A + B modulo N`.
326  * \p A, \p B and \p X must all be associated with the modulus \p N and must
327  * all have the same number of limbs as \p N.
333  *       form (that is, are < \p N) - that will have been done by
337  *                  Must have the same number of limbs as the modulus \p N.
340  * \param[in]  N    The address of the modulus. Used to perform a modulo
350                         const mbedtls_mpi_mod_modulus *N);
355  * \p N exclusive.
361  * \note           There are `N - min` possible outputs. The lower bound
362  *                 \p min can be reached, but the upper bound \p N cannot.
366  *                 than \b N.
367  * \param N        The modulus.
375  *                 of attempts. This has a negligible probability if \p N
381                            const mbedtls_mpi_mod_modulus *N,
388  * based on the value of the `N->int_rep` field.
390  * The modulus \p N will be the modulus associated with \p r. The residue \p r
391  * should only be used in operations where the modulus is \p N or a modulus
392  * equivalent to \p N (in the sense that all their fields or memory pointed by
396  *                  number of limbs as the modulus \p N.
397  * \param[in] N     The address of the modulus.
406  *               is invalid or the value in the buffer is not less than \p N.
409                          const mbedtls_mpi_mod_modulus *N,
416  * The modulus \p N must be the modulus associated with \p r (see
420  * based on the value of `N->int_rep` field.
422  * \warning     If the buffer is smaller than `N->bits`, the number of
425  *              (`N->bits`+7)/8.
428  *                  limbs as the modulus \p N. (\p r is an input parameter, but
431  * \param[in] N     The address of the modulus associated with \p r.
447                           const mbedtls_mpi_mod_modulus *N,