1 /** 2 * Low-level modular bignum functions 3 * 4 * This interface should only be used by the higher-level modular bignum 5 * module (bignum_mod.c) and the ECP module (ecp.c, ecp_curves.c). All other 6 * modules should use the high-level modular bignum interface (bignum_mod.h) 7 * or the legacy bignum interface (bignum.h). 8 * 9 * This is a low-level interface to operations on integers modulo which 10 * has no protection against passing invalid arguments such as arrays of 11 * the wrong size. The functions in bignum_mod.h provide a higher-level 12 * interface that includes protections against accidental misuse, at the 13 * expense of code size and sometimes more cumbersome memory management. 14 * 15 * The functions in this module obey the following conventions unless 16 * explicitly indicated otherwise: 17 * - **Modulus parameters**: the modulus is passed as a pointer to a structure 18 * of type #mbedtls_mpi_mod_modulus. The structure must be set up with an 19 * array of limbs storing the bignum value of the modulus. The modulus must 20 * be odd and is assumed to have no leading zeroes. The modulus is usually 21 * named \c N and is usually input-only. 22 * - **Bignum parameters**: Bignums are passed as pointers to an array of 23 * limbs. A limb has the type #mbedtls_mpi_uint. Unless otherwise specified: 24 * - Bignum parameters called \c A, \c B, ... are inputs, and are not 25 * modified by the function. 26 * - Bignum parameters called \c X, \c Y are outputs or input-output. 27 * The initial content of output-only parameters is ignored. 28 * - \c T is a temporary storage area. The initial content of such a 29 * parameter is ignored and the final content is unspecified. 30 * - **Bignum sizes**: bignum sizes are usually expressed by the \c limbs 31 * member of the modulus argument. All bignum parameters must have the same 32 * number of limbs as the modulus. All bignum sizes must be at least 1 and 33 * must be significantly less than #SIZE_MAX. The behavior if a size is 0 is 34 * undefined. 35 * - **Bignum representation**: the representation of inputs and outputs is 36 * specified by the \c int_rep field of the modulus for arithmetic 37 * functions. Utility functions may allow for different representation. 38 * - **Parameter ordering**: for bignum parameters, outputs come before inputs. 39 * The modulus is passed after other bignum input parameters. Temporaries 40 * come last. 41 * - **Aliasing**: in general, output bignums may be aliased to one or more 42 * inputs. Modulus values may not be aliased to any other parameter. Outputs 43 * may not be aliased to one another. Temporaries may not be aliased to any 44 * other parameter. 45 * - **Overlap**: apart from aliasing of limb array pointers (where two 46 * arguments are equal pointers), overlap is not supported and may result 47 * in undefined behavior. 48 * - **Error handling**: This is a low-level module. Functions generally do not 49 * try to protect against invalid arguments such as nonsensical sizes or 50 * null pointers. Note that passing bignums with a different size than the 51 * modulus may lead to buffer overflows. Some functions which allocate 52 * memory or handle reading/writing of bignums will return an error if 53 * memory allocation fails or if buffer sizes are invalid. 54 * - **Modular representatives**: all functions expect inputs to be in the 55 * range [0, \c N - 1] and guarantee outputs in the range [0, \c N - 1]. If 56 * an input is out of range, outputs are fully unspecified, though bignum 57 * values out of range should not cause buffer overflows (beware that this is 58 * not extensively tested). 59 */ 60 61 /* 62 * Copyright The Mbed TLS Contributors 63 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later 64 */ 65 66 #ifndef MBEDTLS_BIGNUM_MOD_RAW_H 67 #define MBEDTLS_BIGNUM_MOD_RAW_H 68 69 #include "common.h" 70 71 #if defined(MBEDTLS_BIGNUM_C) 72 #include "mbedtls/bignum.h" 73 #endif 74 75 #include "bignum_mod.h" 76 77 /** 78 * \brief Perform a safe conditional copy of an MPI which doesn't reveal 79 * whether the assignment was done or not. 80 * 81 * The size to copy is determined by \p N. 82 * 83 * \param[out] X The address of the destination MPI. 84 * This must be initialized. Must have enough limbs to 85 * store the full value of \p A. 86 * \param[in] A The address of the source MPI. This must be initialized. 87 * \param[in] N The address of the modulus related to \p X and \p A. 88 * \param assign The condition deciding whether to perform the 89 * assignment or not. Must be either 0 or 1: 90 * * \c 1: Perform the assignment `X = A`. 91 * * \c 0: Keep the original value of \p X. 92 * 93 * \note This function avoids leaking any information about whether 94 * the assignment was done or not. 95 * 96 * \warning If \p assign is neither 0 nor 1, the result of this function 97 * is indeterminate, and the resulting value in \p X might be 98 * neither its original value nor the value in \p A. 99 */ 100 void mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint *X, 101 const mbedtls_mpi_uint *A, 102 const mbedtls_mpi_mod_modulus *N, 103 unsigned char assign); 104 105 /** 106 * \brief Perform a safe conditional swap of two MPIs which doesn't reveal 107 * whether the swap was done or not. 108 * 109 * The size to swap is determined by \p N. 110 * 111 * \param[in,out] X The address of the first MPI. This must be initialized. 112 * \param[in,out] Y The address of the second MPI. This must be initialized. 113 * \param[in] N The address of the modulus related to \p X and \p Y. 114 * \param swap The condition deciding whether to perform 115 * the swap or not. Must be either 0 or 1: 116 * * \c 1: Swap the values of \p X and \p Y. 117 * * \c 0: Keep the original values of \p X and \p Y. 118 * 119 * \note This function avoids leaking any information about whether 120 * the swap was done or not. 121 * 122 * \warning If \p swap is neither 0 nor 1, the result of this function 123 * is indeterminate, and both \p X and \p Y might end up with 124 * values different to either of the original ones. 125 */ 126 void mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint *X, 127 mbedtls_mpi_uint *Y, 128 const mbedtls_mpi_mod_modulus *N, 129 unsigned char swap); 130 131 /** Import X from unsigned binary data. 132 * 133 * The MPI needs to have enough limbs to store the full value (including any 134 * most significant zero bytes in the input). 135 * 136 * \param[out] X The address of the MPI. The size is determined by \p N. 137 * (In particular, it must have at least as many limbs as 138 * the modulus \p N.) 139 * \param[in] N The address of the modulus related to \p X. 140 * \param[in] input The input buffer to import from. 141 * \param input_length The length in bytes of \p input. 142 * \param ext_rep The endianness of the number in the input buffer. 143 * 144 * \return \c 0 if successful. 145 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't 146 * large enough to hold the value in \p input. 147 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation 148 * of \p N is invalid or \p X is not less than \p N. 149 */ 150 int mbedtls_mpi_mod_raw_read(mbedtls_mpi_uint *X, 151 const mbedtls_mpi_mod_modulus *N, 152 const unsigned char *input, 153 size_t input_length, 154 mbedtls_mpi_mod_ext_rep ext_rep); 155 156 /** Export A into unsigned binary data. 157 * 158 * \param[in] A The address of the MPI. The size is determined by \p N. 159 * (In particular, it must have at least as many limbs as 160 * the modulus \p N.) 161 * \param[in] N The address of the modulus related to \p A. 162 * \param[out] output The output buffer to export to. 163 * \param output_length The length in bytes of \p output. 164 * \param ext_rep The endianness in which the number should be written into the output buffer. 165 * 166 * \return \c 0 if successful. 167 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't 168 * large enough to hold the value of \p A. 169 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the external representation 170 * of \p N is invalid. 171 */ 172 int mbedtls_mpi_mod_raw_write(const mbedtls_mpi_uint *A, 173 const mbedtls_mpi_mod_modulus *N, 174 unsigned char *output, 175 size_t output_length, 176 mbedtls_mpi_mod_ext_rep ext_rep); 177 178 /** \brief Subtract two MPIs, returning the residue modulo the specified 179 * modulus. 180 * 181 * The size of the operation is determined by \p N. \p A and \p B must have 182 * the same number of limbs as \p N. 183 * 184 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 185 * either otherwise. 186 * 187 * \param[out] X The address of the result MPI. 188 * This must be initialized. Must have enough limbs to 189 * store the full value of the result. 190 * \param[in] A The address of the first MPI. This must be initialized. 191 * \param[in] B The address of the second MPI. This must be initialized. 192 * \param[in] N The address of the modulus. Used to perform a modulo 193 * operation on the result of the subtraction. 194 */ 195 void mbedtls_mpi_mod_raw_sub(mbedtls_mpi_uint *X, 196 const mbedtls_mpi_uint *A, 197 const mbedtls_mpi_uint *B, 198 const mbedtls_mpi_mod_modulus *N); 199 200 /** \brief Multiply two MPIs, returning the residue modulo the specified 201 * modulus. 202 * 203 * \note Currently handles the case when `N->int_rep` is 204 * MBEDTLS_MPI_MOD_REP_MONTGOMERY. 205 * 206 * The size of the operation is determined by \p N. \p A, \p B and \p X must 207 * all be associated with the modulus \p N and must all have the same number 208 * of limbs as \p N. 209 * 210 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 211 * either otherwise. They may not alias \p N (since they must be in canonical 212 * form, they cannot == \p N). 213 * 214 * \param[out] X The address of the result MPI. Must have the same 215 * number of limbs as \p N. 216 * On successful completion, \p X contains the result of 217 * the multiplication `A * B * R^-1` mod N where 218 * `R = 2^(biL * N->limbs)`. 219 * \param[in] A The address of the first MPI. 220 * \param[in] B The address of the second MPI. 221 * \param[in] N The address of the modulus. Used to perform a modulo 222 * operation on the result of the multiplication. 223 * \param[in,out] T Temporary storage of size at least 2 * N->limbs + 1 224 * limbs. Its initial content is unused and 225 * its final content is indeterminate. 226 * It must not alias or otherwise overlap any of the 227 * other parameters. 228 */ 229 void mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint *X, 230 const mbedtls_mpi_uint *A, 231 const mbedtls_mpi_uint *B, 232 const mbedtls_mpi_mod_modulus *N, 233 mbedtls_mpi_uint *T); 234 235 /** 236 * \brief Returns the number of limbs of working memory required for 237 * a call to `mbedtls_mpi_mod_raw_inv_prime()`. 238 * 239 * \note This will always be at least 240 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`, 241 * i.e. sufficient for a call to `mbedtls_mpi_core_montmul()`. 242 * 243 * \param AN_limbs The number of limbs in the input `A` and the modulus `N` 244 * (they must be the same size) that will be given to 245 * `mbedtls_mpi_mod_raw_inv_prime()`. 246 * 247 * \return The number of limbs of working memory required by 248 * `mbedtls_mpi_mod_raw_inv_prime()`. 249 */ 250 size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs); 251 252 /** 253 * \brief Perform fixed-width modular inversion of a Montgomery-form MPI with 254 * respect to a modulus \p N that must be prime. 255 * 256 * \p X may be aliased to \p A, but not to \p N or \p RR. 257 * 258 * \param[out] X The modular inverse of \p A with respect to \p N. 259 * Will be in Montgomery form. 260 * \param[in] A The number to calculate the modular inverse of. 261 * Must be in Montgomery form. Must not be 0. 262 * \param[in] N The modulus, as a little-endian array of length \p AN_limbs. 263 * Must be prime. 264 * \param AN_limbs The number of limbs in \p A, \p N and \p RR. 265 * \param[in] RR The precomputed residue of 2^{2*biL} modulo N, as a little- 266 * endian array of length \p AN_limbs. 267 * \param[in,out] T Temporary storage of at least the number of limbs returned 268 * by `mbedtls_mpi_mod_raw_inv_prime_working_limbs()`. 269 * Its initial content is unused and its final content is 270 * indeterminate. 271 * It must not alias or otherwise overlap any of the other 272 * parameters. 273 * It is up to the caller to zeroize \p T when it is no 274 * longer needed, and before freeing it if it was dynamically 275 * allocated. 276 */ 277 void mbedtls_mpi_mod_raw_inv_prime(mbedtls_mpi_uint *X, 278 const mbedtls_mpi_uint *A, 279 const mbedtls_mpi_uint *N, 280 size_t AN_limbs, 281 const mbedtls_mpi_uint *RR, 282 mbedtls_mpi_uint *T); 283 284 /** 285 * \brief Perform a known-size modular addition. 286 * 287 * Calculate `A + B modulo N`. 288 * 289 * The number of limbs in each operand, and the result, is given by the 290 * modulus \p N. 291 * 292 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 293 * either otherwise. 294 * 295 * \param[out] X The result of the modular addition. 296 * \param[in] A Little-endian presentation of the left operand. This 297 * must be smaller than \p N. 298 * \param[in] B Little-endian presentation of the right operand. This 299 * must be smaller than \p N. 300 * \param[in] N The address of the modulus. 301 */ 302 void mbedtls_mpi_mod_raw_add(mbedtls_mpi_uint *X, 303 const mbedtls_mpi_uint *A, 304 const mbedtls_mpi_uint *B, 305 const mbedtls_mpi_mod_modulus *N); 306 307 /** Convert an MPI from canonical representation (little-endian limb array) 308 * to the representation associated with the modulus. 309 * 310 * \param[in,out] X The limb array to convert. 311 * It must have as many limbs as \p N. 312 * It is converted in place. 313 * If this function returns an error, the content of \p X 314 * is unspecified. 315 * \param[in] N The modulus structure. 316 * 317 * \return \c 0 if successful. 318 * Otherwise an \c MBEDTLS_ERR_MPI_xxx error code. 319 */ 320 int mbedtls_mpi_mod_raw_canonical_to_modulus_rep( 321 mbedtls_mpi_uint *X, 322 const mbedtls_mpi_mod_modulus *N); 323 324 /** Convert an MPI from the representation associated with the modulus 325 * to canonical representation (little-endian limb array). 326 * 327 * \param[in,out] X The limb array to convert. 328 * It must have as many limbs as \p N. 329 * It is converted in place. 330 * If this function returns an error, the content of \p X 331 * is unspecified. 332 * \param[in] N The modulus structure. 333 * 334 * \return \c 0 if successful. 335 * Otherwise an \c MBEDTLS_ERR_MPI_xxx error code. 336 */ 337 int mbedtls_mpi_mod_raw_modulus_to_canonical_rep( 338 mbedtls_mpi_uint *X, 339 const mbedtls_mpi_mod_modulus *N); 340 341 /** Generate a random number uniformly in a range. 342 * 343 * This function generates a random number between \p min inclusive and 344 * \p N exclusive. 345 * 346 * The procedure complies with RFC 6979 §3.3 (deterministic ECDSA) 347 * when the RNG is a suitably parametrized instance of HMAC_DRBG 348 * and \p min is \c 1. 349 * 350 * \note There are `N - min` possible outputs. The lower bound 351 * \p min can be reached, but the upper bound \p N cannot. 352 * 353 * \param X The destination MPI, in canonical representation modulo \p N. 354 * It must not be aliased with \p N or otherwise overlap it. 355 * \param min The minimum value to return. It must be strictly smaller 356 * than \b N. 357 * \param N The modulus. 358 * This is the upper bound of the output range, exclusive. 359 * \param f_rng The RNG function to use. This must not be \c NULL. 360 * \param p_rng The RNG parameter to be passed to \p f_rng. 361 * 362 * \return \c 0 if successful. 363 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was 364 * unable to find a suitable value within a limited number 365 * of attempts. This has a negligible probability if \p N 366 * is significantly larger than \p min, which is the case 367 * for all usual cryptographic applications. 368 */ 369 int mbedtls_mpi_mod_raw_random(mbedtls_mpi_uint *X, 370 mbedtls_mpi_uint min, 371 const mbedtls_mpi_mod_modulus *N, 372 int (*f_rng)(void *, unsigned char *, size_t), 373 void *p_rng); 374 375 /** Convert an MPI into Montgomery form. 376 * 377 * \param X The address of the MPI. 378 * Must have the same number of limbs as \p N. 379 * \param N The address of the modulus, which gives the size of 380 * the base `R` = 2^(biL*N->limbs). 381 * 382 * \return \c 0 if successful. 383 */ 384 int mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint *X, 385 const mbedtls_mpi_mod_modulus *N); 386 387 /** Convert an MPI back from Montgomery representation. 388 * 389 * \param X The address of the MPI. 390 * Must have the same number of limbs as \p N. 391 * \param N The address of the modulus, which gives the size of 392 * the base `R`= 2^(biL*N->limbs). 393 * 394 * \return \c 0 if successful. 395 */ 396 int mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint *X, 397 const mbedtls_mpi_mod_modulus *N); 398 399 /** \brief Perform fixed width modular negation. 400 * 401 * The size of the operation is determined by \p N. \p A must have 402 * the same number of limbs as \p N. 403 * 404 * \p X may be aliased to \p A. 405 * 406 * \param[out] X The result of the modular negation. 407 * This must be initialized. 408 * \param[in] A Little-endian presentation of the input operand. This 409 * must be less than or equal to \p N. 410 * \param[in] N The modulus to use. 411 */ 412 void mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint *X, 413 const mbedtls_mpi_uint *A, 414 const mbedtls_mpi_mod_modulus *N); 415 416 #endif /* MBEDTLS_BIGNUM_MOD_RAW_H */ 417
