1 /** 2 * Modular bignum functions 3 * 4 * This module implements operations on integers modulo some fixed modulus. 5 * 6 * The functions in this module obey the following conventions unless 7 * explicitly indicated otherwise: 8 * 9 * - **Modulus parameters**: the modulus is passed as a pointer to a structure 10 * of type #mbedtls_mpi_mod_modulus. The structure must be set up with an 11 * array of limbs storing the bignum value of the modulus. The modulus must 12 * be odd and is assumed to have no leading zeroes. The modulus is usually 13 * named \c N and is usually input-only. Functions which take a parameter 14 * of type \c const #mbedtls_mpi_mod_modulus* must not modify its value. 15 * - **Bignum parameters**: Bignums are passed as pointers to an array of 16 * limbs or to a #mbedtls_mpi_mod_residue structure. A limb has the type 17 * #mbedtls_mpi_uint. Residues must be initialized before use, and must be 18 * associated with the modulus \c N. Unless otherwise specified: 19 * - Bignum parameters called \c A, \c B, ... are inputs and are not 20 * modified by the function. Functions which take a parameter of 21 * type \c const #mbedtls_mpi_mod_residue* must not modify its value. 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 26 * output residue are initialized. 27 * - Bignum parameters called \c p are inputs used to set up a modulus or 28 * residue. These must be pointers to an array of limbs. 29 * - \c T is a temporary storage area. The initial content of such a 30 * parameter is ignored and the final content is unspecified. 31 * - Some functions use different names, such as \c r for the residue. 32 * - **Bignum sizes**: bignum sizes are always expressed in limbs. Both 33 * #mbedtls_mpi_mod_modulus and #mbedtls_mpi_mod_residue have a \c limbs 34 * member storing its size. All bignum parameters must have the same 35 * number of limbs as the modulus. All bignum sizes must be at least 1 and 36 * must be significantly less than #SIZE_MAX. The behavior if a size is 0 is 37 * undefined. 38 * - **Bignum representation**: the representation of inputs and outputs is 39 * specified by the \c int_rep field of the modulus. 40 * - **Parameter ordering**: for bignum parameters, outputs come before inputs. 41 * The modulus is passed after residues. Temporaries come last. 42 * - **Aliasing**: in general, output bignums may be aliased to one or more 43 * inputs. Modulus values may not be aliased to any other parameter. Outputs 44 * may not be aliased to one another. Temporaries may not be aliased to any 45 * other parameter. 46 * - **Overlap**: apart from aliasing of residue pointers (where two residue 47 * arguments are equal pointers), overlap is not supported and may result 48 * in undefined behavior. 49 * - **Error handling**: functions generally check compatibility of input 50 * sizes. Most functions will not check that input values are in canonical 51 * form (i.e. that \c A < \c N), this is only checked during setup of a 52 * residue structure. 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]. 55 * Residues are set up with an associated modulus, and operations are only 56 * guaranteed to work if the modulus is associated with all residue 57 * parameters. If a residue is passed with a modulus other than the one it 58 * is associated with, then it may be out of range. If an input is out of 59 * range, outputs are fully unspecified, though bignum values out of range 60 * should not cause buffer overflows (beware that this is not extensively 61 * tested). 62 */ 63 64 /* 65 * Copyright The Mbed TLS Contributors 66 * SPDX-License-Identifier: Apache-2.0 67 * 68 * Licensed under the Apache License, Version 2.0 (the "License"); you may 69 * not use this file except in compliance with the License. 70 * You may obtain a copy of the License at 71 * 72 * http://www.apache.org/licenses/LICENSE-2.0 73 * 74 * Unless required by applicable law or agreed to in writing, software 75 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 76 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 77 * See the License for the specific language governing permissions and 78 * limitations under the License. 79 */ 80 81 #ifndef MBEDTLS_BIGNUM_MOD_H 82 #define MBEDTLS_BIGNUM_MOD_H 83 84 #include "common.h" 85 86 #if defined(MBEDTLS_BIGNUM_C) 87 #include "mbedtls/bignum.h" 88 #endif 89 90 /** How residues associated with a modulus are represented. 91 * 92 * This also determines which fields of the modulus structure are valid and 93 * what their contents are (see #mbedtls_mpi_mod_modulus). 94 */ 95 typedef enum { 96 /** Representation not chosen (makes the modulus structure invalid). */ 97 MBEDTLS_MPI_MOD_REP_INVALID = 0, 98 /* Skip 1 as it is slightly easier to accidentally pass to functions. */ 99 /** Montgomery representation. */ 100 MBEDTLS_MPI_MOD_REP_MONTGOMERY = 2, 101 /** TODO: document this. 102 * 103 * Residues are in canonical representation. 104 */ 105 MBEDTLS_MPI_MOD_REP_OPT_RED, 106 } mbedtls_mpi_mod_rep_selector; 107 108 /* Make mbedtls_mpi_mod_rep_selector and mbedtls_mpi_mod_ext_rep disjoint to 109 * make it easier to catch when they are accidentally swapped. */ 110 typedef enum { 111 MBEDTLS_MPI_MOD_EXT_REP_INVALID = 0, 112 MBEDTLS_MPI_MOD_EXT_REP_LE = 8, 113 MBEDTLS_MPI_MOD_EXT_REP_BE 114 } mbedtls_mpi_mod_ext_rep; 115 116 typedef struct { 117 mbedtls_mpi_uint *p; 118 size_t limbs; 119 } mbedtls_mpi_mod_residue; 120 121 typedef struct { 122 mbedtls_mpi_uint const *rr; /* The residue for 2^{2*n*biL} mod N */ 123 mbedtls_mpi_uint mm; /* Montgomery const for -N^{-1} mod 2^{ciL} */ 124 } mbedtls_mpi_mont_struct; 125 126 typedef void *mbedtls_mpi_opt_red_struct; 127 128 typedef struct { 129 const mbedtls_mpi_uint *p; 130 size_t limbs; // number of limbs 131 size_t bits; // bitlen of p 132 mbedtls_mpi_mod_rep_selector int_rep; // selector to signal the active member of the union 133 union rep { 134 /* if int_rep == #MBEDTLS_MPI_MOD_REP_MONTGOMERY */ 135 mbedtls_mpi_mont_struct mont; 136 /* if int_rep == #MBEDTLS_MPI_MOD_REP_OPT_RED */ 137 mbedtls_mpi_opt_red_struct ored; 138 } rep; 139 } mbedtls_mpi_mod_modulus; 140 141 /** Setup a residue structure. 142 * 143 * The residue will be set up with the buffer \p p and modulus \p N. 144 * 145 * The memory pointed to by \p p will be used by the resulting residue structure. 146 * The value at the pointed-to memory will be the initial value of \p r and must 147 * hold a value that is less than the modulus. This value will be used as-is 148 * and interpreted according to the value of the `N->int_rep` field. 149 * 150 * The modulus \p N will be the modulus associated with \p r. The residue \p r 151 * should only be used in operations where the modulus is \p N. 152 * 153 * \param[out] r The address of the residue to setup. 154 * \param[in] N The address of the modulus related to \p r. 155 * \param[in] p The address of the limb array containing the value of \p r. 156 * The memory pointed to by \p p will be used by \p r and must 157 * not be modified in any way until after 158 * mbedtls_mpi_mod_residue_release() is called. The data 159 * pointed to by \p p must be less than the modulus (the value 160 * pointed to by `N->p`) and already in the representation 161 * indicated by `N->int_rep`. 162 * \param p_limbs The number of limbs of \p p. Must be the same as the number 163 * of limbs in the modulus \p N. 164 * 165 * \return \c 0 if successful. 166 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p p_limbs is less than the 167 * limbs in \p N or if \p p is not less than \p N. 168 */ 169 int mbedtls_mpi_mod_residue_setup(mbedtls_mpi_mod_residue *r, 170 const mbedtls_mpi_mod_modulus *N, 171 mbedtls_mpi_uint *p, 172 size_t p_limbs); 173 174 /** Unbind elements of a residue structure. 175 * 176 * This function removes the reference to the limb array that was passed to 177 * mbedtls_mpi_mod_residue_setup() to make it safe to free or use again. 178 * 179 * This function invalidates \p r and it must not be used until after 180 * mbedtls_mpi_mod_residue_setup() is called on it again. 181 * 182 * \param[out] r The address of residue to release. 183 */ 184 void mbedtls_mpi_mod_residue_release(mbedtls_mpi_mod_residue *r); 185 186 /** Initialize a modulus structure. 187 * 188 * \param[out] N The address of the modulus structure to initialize. 189 */ 190 void mbedtls_mpi_mod_modulus_init(mbedtls_mpi_mod_modulus *N); 191 192 /** Setup a modulus structure. 193 * 194 * \param[out] N The address of the modulus structure to populate. 195 * \param[in] p The address of the limb array storing the value of \p N. 196 * The memory pointed to by \p p will be used by \p N and must 197 * not be modified in any way until after 198 * mbedtls_mpi_mod_modulus_free() is called. 199 * \param p_limbs The number of limbs of \p p. 200 * \param int_rep The internal representation to be used for residues 201 * associated with \p N (see #mbedtls_mpi_mod_rep_selector). 202 * 203 * \return \c 0 if successful. 204 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p int_rep is invalid. 205 */ 206 int mbedtls_mpi_mod_modulus_setup(mbedtls_mpi_mod_modulus *N, 207 const mbedtls_mpi_uint *p, 208 size_t p_limbs, 209 mbedtls_mpi_mod_rep_selector int_rep); 210 211 /** Free elements of a modulus structure. 212 * 213 * This function frees any memory allocated by mbedtls_mpi_mod_modulus_setup(). 214 * 215 * \warning This function does not free the limb array passed to 216 * mbedtls_mpi_mod_modulus_setup() only removes the reference to it, 217 * making it safe to free or to use it again. 218 * 219 * \param[in,out] N The address of the modulus structure to free. 220 */ 221 void mbedtls_mpi_mod_modulus_free(mbedtls_mpi_mod_modulus *N); 222 223 /* BEGIN MERGE SLOT 1 */ 224 225 /* END MERGE SLOT 1 */ 226 227 /* BEGIN MERGE SLOT 2 */ 228 229 /** \brief Multiply two residues, returning the residue modulo the specified 230 * modulus. 231 * 232 * \note Currently handles the case when `N->int_rep` is 233 * MBEDTLS_MPI_MOD_REP_MONTGOMERY. 234 * 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. 238 * 239 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 240 * either otherwise. They may not alias \p N (since they must be in canonical 241 * form, they cannot == \p N). 242 * 243 * \param[out] X The address of the result MPI. Must have the same 244 * number of limbs as \p N. 245 * On successful completion, \p X contains the result of 246 * the multiplication `A * B * R^-1` mod N where 247 * `R = 2^(biL * N->limbs)`. 248 * \param[in] A The address of the first MPI. 249 * \param[in] B The address of the second MPI. 250 * \param[in] N The address of the modulus. Used to perform a modulo 251 * operation on the result of the multiplication. 252 * 253 * \return \c 0 if successful. 254 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if all the parameters do not 255 * have the same number of limbs or \p N is invalid. 256 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED on memory-allocation failure. 257 */ 258 int mbedtls_mpi_mod_mul(mbedtls_mpi_mod_residue *X, 259 const mbedtls_mpi_mod_residue *A, 260 const mbedtls_mpi_mod_residue *B, 261 const mbedtls_mpi_mod_modulus *N); 262 263 /* END MERGE SLOT 2 */ 264 265 /* BEGIN MERGE SLOT 3 */ 266 /** 267 * \brief Perform a fixed-size modular subtraction. 268 * 269 * Calculate `A - B modulo N`. 270 * 271 * \p A, \p B and \p X must all have the same number of limbs as \p N. 272 * 273 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 274 * either otherwise. 275 * 276 * \note This function does not check that \p A or \p B are in canonical 277 * form (that is, are < \p N) - that will have been done by 278 * mbedtls_mpi_mod_residue_setup(). 279 * 280 * \param[out] X The address of the result MPI. Must be initialized. 281 * Must have the same number of limbs as the modulus \p N. 282 * \param[in] A The address of the first MPI. 283 * \param[in] B The address of the second MPI. 284 * \param[in] N The address of the modulus. Used to perform a modulo 285 * operation on the result of the subtraction. 286 * 287 * \return \c 0 if successful. 288 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the given MPIs do not 289 * have the correct number of limbs. 290 */ 291 int mbedtls_mpi_mod_sub(mbedtls_mpi_mod_residue *X, 292 const mbedtls_mpi_mod_residue *A, 293 const mbedtls_mpi_mod_residue *B, 294 const mbedtls_mpi_mod_modulus *N); 295 296 /** 297 * \brief Perform modular inversion of an MPI with respect to a modulus \p N. 298 * 299 * \p A and \p X must be associated with the modulus \p N and will therefore 300 * have the same number of limbs as \p N. 301 * 302 * \p X may be aliased to \p A. 303 * 304 * \warning Currently only supports prime moduli, but does not check for them. 305 * 306 * \param[out] X The modular inverse of \p A with respect to \p N. 307 * \param[in] A The number to calculate the modular inverse of. 308 * Must not be 0. 309 * \param[in] N The modulus to use. 310 * 311 * \return \c 0 if successful. 312 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p A and \p N do not 313 * have the same number of limbs. 314 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p A is zero. 315 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if couldn't allocate enough 316 * memory (needed for conversion to and from Mongtomery form 317 * when not in Montgomery form already, and for temporary use 318 * by the inversion calculation itself). 319 */ 320 321 int mbedtls_mpi_mod_inv(mbedtls_mpi_mod_residue *X, 322 const mbedtls_mpi_mod_residue *A, 323 const mbedtls_mpi_mod_modulus *N); 324 /* END MERGE SLOT 3 */ 325 326 /* BEGIN MERGE SLOT 4 */ 327 328 /* END MERGE SLOT 4 */ 329 330 /* BEGIN MERGE SLOT 5 */ 331 /** 332 * \brief Perform a fixed-size modular addition. 333 * 334 * Calculate `A + B modulo N`. 335 * 336 * \p A, \p B and \p X must all be associated with the modulus \p N and must 337 * all have the same number of limbs as \p N. 338 * 339 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 340 * either otherwise. 341 * 342 * \note This function does not check that \p A or \p B are in canonical 343 * form (that is, are < \p N) - that will have been done by 344 * mbedtls_mpi_mod_residue_setup(). 345 * 346 * \param[out] X The address of the result residue. Must be initialized. 347 * Must have the same number of limbs as the modulus \p N. 348 * \param[in] A The address of the first input residue. 349 * \param[in] B The address of the second input residue. 350 * \param[in] N The address of the modulus. Used to perform a modulo 351 * operation on the result of the addition. 352 * 353 * \return \c 0 if successful. 354 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the given MPIs do not 355 * have the correct number of limbs. 356 */ 357 int mbedtls_mpi_mod_add(mbedtls_mpi_mod_residue *X, 358 const mbedtls_mpi_mod_residue *A, 359 const mbedtls_mpi_mod_residue *B, 360 const mbedtls_mpi_mod_modulus *N); 361 /* END MERGE SLOT 5 */ 362 363 /* BEGIN MERGE SLOT 6 */ 364 365 /** Generate a random number uniformly in a range. 366 * 367 * This function generates a random number between \p min inclusive and 368 * \p N exclusive. 369 * 370 * The procedure complies with RFC 6979 §3.3 (deterministic ECDSA) 371 * when the RNG is a suitably parametrized instance of HMAC_DRBG 372 * and \p min is \c 1. 373 * 374 * \note There are `N - min` possible outputs. The lower bound 375 * \p min can be reached, but the upper bound \p N cannot. 376 * 377 * \param X The destination residue. 378 * \param min The minimum value to return. It must be strictly smaller 379 * than \b N. 380 * \param N The modulus. 381 * This is the upper bound of the output range, exclusive. 382 * \param f_rng The RNG function to use. This must not be \c NULL. 383 * \param p_rng The RNG parameter to be passed to \p f_rng. 384 * 385 * \return \c 0 if successful. 386 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was 387 * unable to find a suitable value within a limited number 388 * of attempts. This has a negligible probability if \p N 389 * is significantly larger than \p min, which is the case 390 * for all usual cryptographic applications. 391 */ 392 int mbedtls_mpi_mod_random(mbedtls_mpi_mod_residue *X, 393 mbedtls_mpi_uint min, 394 const mbedtls_mpi_mod_modulus *N, 395 int (*f_rng)(void *, unsigned char *, size_t), 396 void *p_rng); 397 398 /* END MERGE SLOT 6 */ 399 400 /* BEGIN MERGE SLOT 7 */ 401 /** Read a residue from a byte buffer. 402 * 403 * The residue will be automatically converted to the internal representation 404 * based on the value of the `N->int_rep` field. 405 * 406 * The modulus \p N will be the modulus associated with \p r. The residue \p r 407 * should only be used in operations where the modulus is \p N or a modulus 408 * equivalent to \p N (in the sense that all their fields or memory pointed by 409 * their fields hold the same value). 410 * 411 * \param[out] r The address of the residue. It must have exactly the same 412 * number of limbs as the modulus \p N. 413 * \param[in] N The address of the modulus. 414 * \param[in] buf The input buffer to import from. 415 * \param buflen The length in bytes of \p buf. 416 * \param ext_rep The endianness of the number in the input buffer. 417 * 418 * \return \c 0 if successful. 419 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p r isn't 420 * large enough to hold the value in \p buf. 421 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p ext_rep 422 * is invalid or the value in the buffer is not less than \p N. 423 */ 424 int mbedtls_mpi_mod_read(mbedtls_mpi_mod_residue *r, 425 const mbedtls_mpi_mod_modulus *N, 426 const unsigned char *buf, 427 size_t buflen, 428 mbedtls_mpi_mod_ext_rep ext_rep); 429 430 /** Write a residue into a byte buffer. 431 * 432 * The modulus \p N must be the modulus associated with \p r (see 433 * mbedtls_mpi_mod_residue_setup() and mbedtls_mpi_mod_read()). 434 * 435 * The residue will be automatically converted from the internal representation 436 * based on the value of `N->int_rep` field. 437 * 438 * \warning If the buffer is smaller than `N->bits`, the number of 439 * leading zeroes is leaked through timing. If \p r is 440 * secret, the caller must ensure that \p buflen is at least 441 * (`N->bits`+7)/8. 442 * 443 * \param[in] r The address of the residue. It must have the same number of 444 * limbs as the modulus \p N. (\p r is an input parameter, but 445 * its value will be modified during execution and restored 446 * before the function returns.) 447 * \param[in] N The address of the modulus associated with \p r. 448 * \param[out] buf The output buffer to export to. 449 * \param buflen The length in bytes of \p buf. 450 * \param ext_rep The endianness in which the number should be written into 451 * the output buffer. 452 * 453 * \return \c 0 if successful. 454 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p buf isn't 455 * large enough to hold the value of \p r (without leading 456 * zeroes). 457 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p ext_rep is invalid. 458 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if couldn't allocate enough 459 * memory for conversion. Can occur only for moduli with 460 * MBEDTLS_MPI_MOD_REP_MONTGOMERY. 461 */ 462 int mbedtls_mpi_mod_write(const mbedtls_mpi_mod_residue *r, 463 const mbedtls_mpi_mod_modulus *N, 464 unsigned char *buf, 465 size_t buflen, 466 mbedtls_mpi_mod_ext_rep ext_rep); 467 /* END MERGE SLOT 7 */ 468 469 /* BEGIN MERGE SLOT 8 */ 470 471 /* END MERGE SLOT 8 */ 472 473 /* BEGIN MERGE SLOT 9 */ 474 475 /* END MERGE SLOT 9 */ 476 477 /* BEGIN MERGE SLOT 10 */ 478 479 /* END MERGE SLOT 10 */ 480 481 #endif /* MBEDTLS_BIGNUM_MOD_H */ 482