1 /** 2 * Modular bignum functions 3 * 4 * This module implements operations on integers modulo some fixed modulus. 5 */ 6 7 /* 8 * Copyright The Mbed TLS Contributors 9 * SPDX-License-Identifier: Apache-2.0 10 * 11 * Licensed under the Apache License, Version 2.0 (the "License"); you may 12 * not use this file except in compliance with the License. 13 * You may obtain a copy of the License at 14 * 15 * http://www.apache.org/licenses/LICENSE-2.0 16 * 17 * Unless required by applicable law or agreed to in writing, software 18 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT 19 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 20 * See the License for the specific language governing permissions and 21 * limitations under the License. 22 */ 23 24 #ifndef MBEDTLS_BIGNUM_MOD_H 25 #define MBEDTLS_BIGNUM_MOD_H 26 27 #include "common.h" 28 29 #if defined(MBEDTLS_BIGNUM_C) 30 #include "mbedtls/bignum.h" 31 #endif 32 33 /* Skip 1 as it is slightly easier to accidentally pass to functions. */ 34 typedef enum 35 { 36 MBEDTLS_MPI_MOD_REP_INVALID = 0, 37 MBEDTLS_MPI_MOD_REP_MONTGOMERY = 2, 38 MBEDTLS_MPI_MOD_REP_OPT_RED 39 } mbedtls_mpi_mod_rep_selector; 40 41 /* Make mbedtls_mpi_mod_rep_selector and mbedtls_mpi_mod_ext_rep disjoint to 42 * make it easier to catch when they are accidentally swapped. */ 43 typedef enum 44 { 45 MBEDTLS_MPI_MOD_EXT_REP_INVALID = 0, 46 MBEDTLS_MPI_MOD_EXT_REP_LE = 8, 47 MBEDTLS_MPI_MOD_EXT_REP_BE 48 } mbedtls_mpi_mod_ext_rep; 49 50 typedef struct 51 { 52 mbedtls_mpi_uint *p; 53 size_t limbs; 54 } mbedtls_mpi_mod_residue; 55 56 typedef struct { 57 mbedtls_mpi_uint const *rr; /* The residue for 2^{2*n*biL} mod N */ 58 mbedtls_mpi_uint mm; /* Montgomery const for -N^{-1} mod 2^{ciL} */ 59 } mbedtls_mpi_mont_struct; 60 61 typedef void *mbedtls_mpi_opt_red_struct; 62 63 typedef struct { 64 const mbedtls_mpi_uint *p; 65 size_t limbs; // number of limbs 66 size_t bits; // bitlen of p 67 mbedtls_mpi_mod_rep_selector int_rep; // selector to signal the active member of the union 68 union rep 69 { 70 mbedtls_mpi_mont_struct mont; 71 mbedtls_mpi_opt_red_struct ored; 72 } rep; 73 } mbedtls_mpi_mod_modulus; 74 75 /** Setup a residue structure. 76 * 77 * The residue will be set up with the buffer \p p and modulus \p m. 78 * 79 * The memory pointed to by \p p will be used by the resulting residue structure. 80 * The value at the pointed-to memory will be the initial value of \p r and must 81 * hold a value that is less than the modulus. This value will be used as-is 82 * and interpreted according to the value of the `m->int_rep` field. 83 * 84 * The modulus \p m will be the modulus associated with \p r. The residue \p r 85 * should only be used in operations where the modulus is \p m. 86 * 87 * \param[out] r The address of the residue to setup. 88 * \param[in] m The address of the modulus related to \p r. 89 * \param[in] p The address of the limb array containing the value of \p r. 90 * The memory pointed to by \p p will be used by \p r and must 91 * not be modified in any way until after 92 * mbedtls_mpi_mod_residue_release() is called. The data 93 * pointed to by \p p must be less than the modulus (the value 94 * pointed to by `m->p`) and already in the representation 95 * indicated by `m->int_rep`. 96 * \param p_limbs The number of limbs of \p p. Must be the same as the number 97 * of limbs in the modulus \p m. 98 * 99 * \return \c 0 if successful. 100 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p p_limbs is less than the 101 * limbs in \p m or if \p p is not less than \p m. 102 */ 103 int mbedtls_mpi_mod_residue_setup( mbedtls_mpi_mod_residue *r, 104 const mbedtls_mpi_mod_modulus *m, 105 mbedtls_mpi_uint *p, 106 size_t p_limbs ); 107 108 /** Unbind elements of a residue structure. 109 * 110 * This function removes the reference to the limb array that was passed to 111 * mbedtls_mpi_mod_residue_setup() to make it safe to free or use again. 112 * 113 * This function invalidates \p r and it must not be used until after 114 * mbedtls_mpi_mod_residue_setup() is called on it again. 115 * 116 * \param[out] r The address of residue to release. 117 */ 118 void mbedtls_mpi_mod_residue_release( mbedtls_mpi_mod_residue *r ); 119 120 /** Initialize a modulus structure. 121 * 122 * \param[out] m The address of the modulus structure to initialize. 123 */ 124 void mbedtls_mpi_mod_modulus_init( mbedtls_mpi_mod_modulus *m ); 125 126 /** Setup a modulus structure. 127 * 128 * \param[out] m The address of the modulus structure to populate. 129 * \param[in] p The address of the limb array storing the value of \p m. 130 * The memory pointed to by \p p will be used by \p m and must 131 * not be modified in any way until after 132 * mbedtls_mpi_mod_modulus_free() is called. 133 * \param p_limbs The number of limbs of \p p. 134 * \param int_rep The internal representation to be used for residues 135 * associated with \p m (see #mbedtls_mpi_mod_rep_selector). 136 * 137 * \return \c 0 if successful. 138 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p int_rep is invalid. 139 */ 140 int mbedtls_mpi_mod_modulus_setup( mbedtls_mpi_mod_modulus *m, 141 const mbedtls_mpi_uint *p, 142 size_t p_limbs, 143 mbedtls_mpi_mod_rep_selector int_rep ); 144 145 /** Free elements of a modulus structure. 146 * 147 * This function frees any memory allocated by mbedtls_mpi_mod_modulus_setup(). 148 * 149 * \warning This function does not free the limb array passed to 150 * mbedtls_mpi_mod_modulus_setup() only removes the reference to it, 151 * making it safe to free or to use it again. 152 * 153 * \param[in,out] m The address of the modulus structure to free. 154 */ 155 void mbedtls_mpi_mod_modulus_free( mbedtls_mpi_mod_modulus *m ); 156 157 /* BEGIN MERGE SLOT 1 */ 158 159 /* END MERGE SLOT 1 */ 160 161 /* BEGIN MERGE SLOT 2 */ 162 163 /* END MERGE SLOT 2 */ 164 165 /* BEGIN MERGE SLOT 3 */ 166 /** 167 * \brief Perform a fixed-size modular subtraction. 168 * 169 * Calculate `A - B modulo N`. 170 * 171 * \p A, \p B and \p X must all have the same number of limbs as \p N. 172 * 173 * \p X may be aliased to \p A or \p B, or even both, but may not overlap 174 * either otherwise. 175 * 176 * \note This function does not check that \p A or \p B are in canonical 177 * form (that is, are < \p N) - that will have been done by 178 * mbedtls_mpi_mod_residue_setup(). 179 * 180 * \param[out] X The address of the result MPI. Must be initialized. 181 * Must have the same number of limbs as the modulus \p N. 182 * \param[in] A The address of the first MPI. 183 * \param[in] B The address of the second MPI. 184 * \param[in] N The address of the modulus. Used to perform a modulo 185 * operation on the result of the subtraction. 186 * 187 * \return \c 0 if successful. 188 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if the given MPIs do not 189 * have the correct number of limbs. 190 */ 191 int mbedtls_mpi_mod_sub( mbedtls_mpi_mod_residue *X, 192 const mbedtls_mpi_mod_residue *A, 193 const mbedtls_mpi_mod_residue *B, 194 const mbedtls_mpi_mod_modulus *N ); 195 /* END MERGE SLOT 3 */ 196 197 /* BEGIN MERGE SLOT 4 */ 198 199 /* END MERGE SLOT 4 */ 200 201 /* BEGIN MERGE SLOT 5 */ 202 203 /* END MERGE SLOT 5 */ 204 205 /* BEGIN MERGE SLOT 6 */ 206 207 /* END MERGE SLOT 6 */ 208 209 /* BEGIN MERGE SLOT 7 */ 210 /** Read a residue from a byte buffer. 211 * 212 * The residue will be automatically converted to the internal representation 213 * based on the value of the `m->int_rep` field. 214 * 215 * The modulus \p m will be the modulus associated with \p r. The residue \p r 216 * should only be used in operations where the modulus is \p m or a modulus 217 * equivalent to \p m (in the sense that all their fields or memory pointed by 218 * their fields hold the same value). 219 * 220 * \param[out] r The address of the residue. It must have exactly the same 221 * number of limbs as the modulus \p m. 222 * \param[in] m The address of the modulus. 223 * \param[in] buf The input buffer to import from. 224 * \param buflen The length in bytes of \p buf. 225 * \param ext_rep The endianness of the number in the input buffer. 226 * 227 * \return \c 0 if successful. 228 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p r isn't 229 * large enough to hold the value in \p buf. 230 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p ext_rep 231 * is invalid or the value in the buffer is not less than \p m. 232 */ 233 int mbedtls_mpi_mod_read( mbedtls_mpi_mod_residue *r, 234 const mbedtls_mpi_mod_modulus *m, 235 const unsigned char *buf, 236 size_t buflen, 237 mbedtls_mpi_mod_ext_rep ext_rep ); 238 239 /** Write a residue into a byte buffer. 240 * 241 * The modulus \p m must be the modulus associated with \p r (see 242 * mbedtls_mpi_mod_residue_setup() and mbedtls_mpi_mod_read()). 243 * 244 * The residue will be automatically converted from the internal representation 245 * based on the value of `m->int_rep` field. 246 * 247 * \warning If the buffer is smaller than `m->bits`, the number of 248 * leading zeroes is leaked through timing. If \p r is 249 * secret, the caller must ensure that \p buflen is at least 250 * (`m->bits`+7)/8. 251 * 252 * \param[in] r The address of the residue. It must have the same number of 253 * limbs as the modulus \p m. (\p r is an input parameter, but 254 * its value will be modified during execution and restored 255 * before the function returns.) 256 * \param[in] m The address of the modulus associated with \r. 257 * \param[out] buf The output buffer to export to. 258 * \param buflen The length in bytes of \p buf. 259 * \param ext_rep The endianness in which the number should be written into 260 * the output buffer. 261 * 262 * \return \c 0 if successful. 263 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p buf isn't 264 * large enough to hold the value of \p r (without leading 265 * zeroes). 266 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p ext_rep is invalid. 267 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if couldn't allocate enough 268 * memory for conversion. Can occur only for moduli with 269 * MBEDTLS_MPI_MOD_REP_MONTGOMERY. 270 */ 271 int mbedtls_mpi_mod_write( const mbedtls_mpi_mod_residue *r, 272 const mbedtls_mpi_mod_modulus *m, 273 unsigned char *buf, 274 size_t buflen, 275 mbedtls_mpi_mod_ext_rep ext_rep ); 276 /* END MERGE SLOT 7 */ 277 278 /* BEGIN MERGE SLOT 8 */ 279 280 /* END MERGE SLOT 8 */ 281 282 /* BEGIN MERGE SLOT 9 */ 283 284 /* END MERGE SLOT 9 */ 285 286 /* BEGIN MERGE SLOT 10 */ 287 288 /* END MERGE SLOT 10 */ 289 290 #endif /* MBEDTLS_BIGNUM_MOD_H */ 291
