bignum_mod.c (11490B)
1 /** 2 * Modular bignum functions 3 * 4 * Copyright The Mbed TLS Contributors 5 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later 6 */ 7 8 #include "common.h" 9 10 #if defined(MBEDTLS_BIGNUM_C) && defined(MBEDTLS_ECP_WITH_MPI_UINT) 11 12 #include <string.h> 13 14 #include "mbedtls/platform_util.h" 15 #include "mbedtls/error.h" 16 #include "mbedtls/bignum.h" 17 18 #include "mbedtls/platform.h" 19 20 #include "bignum_core.h" 21 #include "bignum_mod.h" 22 #include "bignum_mod_raw.h" 23 #include "constant_time_internal.h" 24 25 int mbedtls_mpi_mod_residue_setup(mbedtls_mpi_mod_residue *r, 26 const mbedtls_mpi_mod_modulus *N, 27 mbedtls_mpi_uint *p, 28 size_t p_limbs) 29 { 30 if (p_limbs != N->limbs || !mbedtls_mpi_core_lt_ct(p, N->p, N->limbs)) { 31 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 32 } 33 34 r->limbs = N->limbs; 35 r->p = p; 36 37 return 0; 38 } 39 40 void mbedtls_mpi_mod_residue_release(mbedtls_mpi_mod_residue *r) 41 { 42 if (r == NULL) { 43 return; 44 } 45 46 r->limbs = 0; 47 r->p = NULL; 48 } 49 50 void mbedtls_mpi_mod_modulus_init(mbedtls_mpi_mod_modulus *N) 51 { 52 if (N == NULL) { 53 return; 54 } 55 56 N->p = NULL; 57 N->limbs = 0; 58 N->bits = 0; 59 N->int_rep = MBEDTLS_MPI_MOD_REP_INVALID; 60 } 61 62 void mbedtls_mpi_mod_modulus_free(mbedtls_mpi_mod_modulus *N) 63 { 64 if (N == NULL) { 65 return; 66 } 67 68 switch (N->int_rep) { 69 case MBEDTLS_MPI_MOD_REP_MONTGOMERY: 70 if (N->rep.mont.rr != NULL) { 71 mbedtls_zeroize_and_free((mbedtls_mpi_uint *) N->rep.mont.rr, 72 N->limbs * sizeof(mbedtls_mpi_uint)); 73 N->rep.mont.rr = NULL; 74 } 75 N->rep.mont.mm = 0; 76 break; 77 case MBEDTLS_MPI_MOD_REP_OPT_RED: 78 N->rep.ored.modp = NULL; 79 break; 80 case MBEDTLS_MPI_MOD_REP_INVALID: 81 break; 82 } 83 84 N->p = NULL; 85 N->limbs = 0; 86 N->bits = 0; 87 N->int_rep = MBEDTLS_MPI_MOD_REP_INVALID; 88 } 89 90 static int set_mont_const_square(const mbedtls_mpi_uint **X, 91 const mbedtls_mpi_uint *A, 92 size_t limbs) 93 { 94 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 95 mbedtls_mpi N; 96 mbedtls_mpi RR; 97 *X = NULL; 98 99 mbedtls_mpi_init(&N); 100 mbedtls_mpi_init(&RR); 101 102 if (A == NULL || limbs == 0 || limbs >= (MBEDTLS_MPI_MAX_LIMBS / 2) - 2) { 103 goto cleanup; 104 } 105 106 if (mbedtls_mpi_grow(&N, limbs)) { 107 goto cleanup; 108 } 109 110 memcpy(N.p, A, sizeof(mbedtls_mpi_uint) * limbs); 111 112 ret = mbedtls_mpi_core_get_mont_r2_unsafe(&RR, &N); 113 114 if (ret == 0) { 115 *X = RR.p; 116 RR.p = NULL; 117 } 118 119 cleanup: 120 mbedtls_mpi_free(&N); 121 mbedtls_mpi_free(&RR); 122 ret = (ret != 0) ? MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED : 0; 123 return ret; 124 } 125 126 static inline void standard_modulus_setup(mbedtls_mpi_mod_modulus *N, 127 const mbedtls_mpi_uint *p, 128 size_t p_limbs, 129 mbedtls_mpi_mod_rep_selector int_rep) 130 { 131 N->p = p; 132 N->limbs = p_limbs; 133 N->bits = mbedtls_mpi_core_bitlen(p, p_limbs); 134 N->int_rep = int_rep; 135 } 136 137 int mbedtls_mpi_mod_modulus_setup(mbedtls_mpi_mod_modulus *N, 138 const mbedtls_mpi_uint *p, 139 size_t p_limbs) 140 { 141 int ret = 0; 142 standard_modulus_setup(N, p, p_limbs, MBEDTLS_MPI_MOD_REP_MONTGOMERY); 143 N->rep.mont.mm = mbedtls_mpi_core_montmul_init(N->p); 144 ret = set_mont_const_square(&N->rep.mont.rr, N->p, N->limbs); 145 146 if (ret != 0) { 147 mbedtls_mpi_mod_modulus_free(N); 148 } 149 150 return ret; 151 } 152 153 int mbedtls_mpi_mod_optred_modulus_setup(mbedtls_mpi_mod_modulus *N, 154 const mbedtls_mpi_uint *p, 155 size_t p_limbs, 156 mbedtls_mpi_modp_fn modp) 157 { 158 standard_modulus_setup(N, p, p_limbs, MBEDTLS_MPI_MOD_REP_OPT_RED); 159 N->rep.ored.modp = modp; 160 return 0; 161 } 162 163 int mbedtls_mpi_mod_mul(mbedtls_mpi_mod_residue *X, 164 const mbedtls_mpi_mod_residue *A, 165 const mbedtls_mpi_mod_residue *B, 166 const mbedtls_mpi_mod_modulus *N) 167 { 168 if (N->limbs == 0) { 169 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 170 } 171 172 if (X->limbs != N->limbs || A->limbs != N->limbs || B->limbs != N->limbs) { 173 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 174 } 175 176 mbedtls_mpi_uint *T = mbedtls_calloc(N->limbs * 2 + 1, ciL); 177 if (T == NULL) { 178 return MBEDTLS_ERR_MPI_ALLOC_FAILED; 179 } 180 181 mbedtls_mpi_mod_raw_mul(X->p, A->p, B->p, N, T); 182 183 mbedtls_free(T); 184 185 return 0; 186 } 187 188 int mbedtls_mpi_mod_sub(mbedtls_mpi_mod_residue *X, 189 const mbedtls_mpi_mod_residue *A, 190 const mbedtls_mpi_mod_residue *B, 191 const mbedtls_mpi_mod_modulus *N) 192 { 193 if (X->limbs != N->limbs || A->limbs != N->limbs || B->limbs != N->limbs) { 194 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 195 } 196 197 mbedtls_mpi_mod_raw_sub(X->p, A->p, B->p, N); 198 199 return 0; 200 } 201 202 static int mbedtls_mpi_mod_inv_mont(mbedtls_mpi_mod_residue *X, 203 const mbedtls_mpi_mod_residue *A, 204 const mbedtls_mpi_mod_modulus *N, 205 mbedtls_mpi_uint *working_memory) 206 { 207 /* Input already in Montgomery form, so there's little to do */ 208 mbedtls_mpi_mod_raw_inv_prime(X->p, A->p, 209 N->p, N->limbs, 210 N->rep.mont.rr, 211 working_memory); 212 return 0; 213 } 214 215 static int mbedtls_mpi_mod_inv_non_mont(mbedtls_mpi_mod_residue *X, 216 const mbedtls_mpi_mod_residue *A, 217 const mbedtls_mpi_mod_modulus *N, 218 mbedtls_mpi_uint *working_memory) 219 { 220 /* Need to convert input into Montgomery form */ 221 222 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 223 224 mbedtls_mpi_mod_modulus Nmont; 225 mbedtls_mpi_mod_modulus_init(&Nmont); 226 227 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_modulus_setup(&Nmont, N->p, N->limbs)); 228 229 /* We'll use X->p to hold the Montgomery form of the input A->p */ 230 mbedtls_mpi_core_to_mont_rep(X->p, A->p, Nmont.p, Nmont.limbs, 231 Nmont.rep.mont.mm, Nmont.rep.mont.rr, 232 working_memory); 233 234 mbedtls_mpi_mod_raw_inv_prime(X->p, X->p, 235 Nmont.p, Nmont.limbs, 236 Nmont.rep.mont.rr, 237 working_memory); 238 239 /* And convert back from Montgomery form */ 240 241 mbedtls_mpi_core_from_mont_rep(X->p, X->p, Nmont.p, Nmont.limbs, 242 Nmont.rep.mont.mm, working_memory); 243 244 cleanup: 245 mbedtls_mpi_mod_modulus_free(&Nmont); 246 return ret; 247 } 248 249 int mbedtls_mpi_mod_inv(mbedtls_mpi_mod_residue *X, 250 const mbedtls_mpi_mod_residue *A, 251 const mbedtls_mpi_mod_modulus *N) 252 { 253 if (X->limbs != N->limbs || A->limbs != N->limbs) { 254 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 255 } 256 257 /* Zero has the same value regardless of Montgomery form or not */ 258 if (mbedtls_mpi_core_check_zero_ct(A->p, A->limbs) == 0) { 259 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 260 } 261 262 size_t working_limbs = 263 mbedtls_mpi_mod_raw_inv_prime_working_limbs(N->limbs); 264 265 mbedtls_mpi_uint *working_memory = mbedtls_calloc(working_limbs, 266 sizeof(mbedtls_mpi_uint)); 267 if (working_memory == NULL) { 268 return MBEDTLS_ERR_MPI_ALLOC_FAILED; 269 } 270 271 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 272 273 switch (N->int_rep) { 274 case MBEDTLS_MPI_MOD_REP_MONTGOMERY: 275 ret = mbedtls_mpi_mod_inv_mont(X, A, N, working_memory); 276 break; 277 case MBEDTLS_MPI_MOD_REP_OPT_RED: 278 ret = mbedtls_mpi_mod_inv_non_mont(X, A, N, working_memory); 279 break; 280 default: 281 ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 282 break; 283 } 284 285 mbedtls_zeroize_and_free(working_memory, 286 working_limbs * sizeof(mbedtls_mpi_uint)); 287 288 return ret; 289 } 290 291 int mbedtls_mpi_mod_add(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 if (X->limbs != N->limbs || A->limbs != N->limbs || B->limbs != N->limbs) { 297 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 298 } 299 300 mbedtls_mpi_mod_raw_add(X->p, A->p, B->p, N); 301 302 return 0; 303 } 304 305 int mbedtls_mpi_mod_random(mbedtls_mpi_mod_residue *X, 306 mbedtls_mpi_uint min, 307 const mbedtls_mpi_mod_modulus *N, 308 int (*f_rng)(void *, unsigned char *, size_t), 309 void *p_rng) 310 { 311 if (X->limbs != N->limbs) { 312 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 313 } 314 return mbedtls_mpi_mod_raw_random(X->p, min, N, f_rng, p_rng); 315 } 316 317 int mbedtls_mpi_mod_read(mbedtls_mpi_mod_residue *r, 318 const mbedtls_mpi_mod_modulus *N, 319 const unsigned char *buf, 320 size_t buflen, 321 mbedtls_mpi_mod_ext_rep ext_rep) 322 { 323 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 324 325 /* Do our best to check if r and m have been set up */ 326 if (r->limbs == 0 || N->limbs == 0) { 327 goto cleanup; 328 } 329 if (r->limbs != N->limbs) { 330 goto cleanup; 331 } 332 333 ret = mbedtls_mpi_mod_raw_read(r->p, N, buf, buflen, ext_rep); 334 if (ret != 0) { 335 goto cleanup; 336 } 337 338 r->limbs = N->limbs; 339 340 ret = mbedtls_mpi_mod_raw_canonical_to_modulus_rep(r->p, N); 341 342 cleanup: 343 return ret; 344 } 345 346 int mbedtls_mpi_mod_write(const mbedtls_mpi_mod_residue *r, 347 const mbedtls_mpi_mod_modulus *N, 348 unsigned char *buf, 349 size_t buflen, 350 mbedtls_mpi_mod_ext_rep ext_rep) 351 { 352 /* Do our best to check if r and m have been set up */ 353 if (r->limbs == 0 || N->limbs == 0) { 354 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 355 } 356 if (r->limbs != N->limbs) { 357 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 358 } 359 360 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 361 mbedtls_mpi_uint *working_memory = r->p; 362 size_t working_memory_len = sizeof(mbedtls_mpi_uint) * r->limbs; 363 364 if (N->int_rep == MBEDTLS_MPI_MOD_REP_MONTGOMERY) { 365 366 working_memory = mbedtls_calloc(r->limbs, sizeof(mbedtls_mpi_uint)); 367 368 if (working_memory == NULL) { 369 ret = MBEDTLS_ERR_MPI_ALLOC_FAILED; 370 goto cleanup; 371 } 372 373 memcpy(working_memory, r->p, working_memory_len); 374 375 ret = mbedtls_mpi_mod_raw_from_mont_rep(working_memory, N); 376 if (ret != 0) { 377 goto cleanup; 378 } 379 } 380 381 ret = mbedtls_mpi_mod_raw_write(working_memory, N, buf, buflen, ext_rep); 382 383 cleanup: 384 385 if (N->int_rep == MBEDTLS_MPI_MOD_REP_MONTGOMERY && 386 working_memory != NULL) { 387 388 mbedtls_zeroize_and_free(working_memory, working_memory_len); 389 } 390 391 return ret; 392 } 393 394 #endif /* MBEDTLS_BIGNUM_C && MBEDTLS_ECP_WITH_MPI_UINT */