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