1 /* 2 * Low-level 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/error.h" 27 #include "mbedtls/platform_util.h" 28 29 #include "mbedtls/platform.h" 30 31 #include "bignum_core.h" 32 #include "bignum_mod_raw.h" 33 #include "bignum_mod.h" 34 #include "constant_time_internal.h" 35 36 #include "bignum_mod_raw_invasive.h" 37 38 void mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint *X, 39 const mbedtls_mpi_uint *A, 40 const mbedtls_mpi_mod_modulus *N, 41 unsigned char assign) 42 { 43 mbedtls_mpi_core_cond_assign(X, A, N->limbs, assign); 44 } 45 46 void mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint *X, 47 mbedtls_mpi_uint *Y, 48 const mbedtls_mpi_mod_modulus *N, 49 unsigned char swap) 50 { 51 mbedtls_mpi_core_cond_swap(X, Y, N->limbs, swap); 52 } 53 54 int mbedtls_mpi_mod_raw_read(mbedtls_mpi_uint *X, 55 const mbedtls_mpi_mod_modulus *N, 56 const unsigned char *input, 57 size_t input_length, 58 mbedtls_mpi_mod_ext_rep ext_rep) 59 { 60 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; 61 62 switch (ext_rep) { 63 case MBEDTLS_MPI_MOD_EXT_REP_LE: 64 ret = mbedtls_mpi_core_read_le(X, N->limbs, 65 input, input_length); 66 break; 67 case MBEDTLS_MPI_MOD_EXT_REP_BE: 68 ret = mbedtls_mpi_core_read_be(X, N->limbs, 69 input, input_length); 70 break; 71 default: 72 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 73 } 74 75 if (ret != 0) { 76 goto cleanup; 77 } 78 79 if (!mbedtls_mpi_core_lt_ct(X, N->p, N->limbs)) { 80 ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 81 goto cleanup; 82 } 83 84 cleanup: 85 86 return ret; 87 } 88 89 int mbedtls_mpi_mod_raw_write(const mbedtls_mpi_uint *A, 90 const mbedtls_mpi_mod_modulus *N, 91 unsigned char *output, 92 size_t output_length, 93 mbedtls_mpi_mod_ext_rep ext_rep) 94 { 95 switch (ext_rep) { 96 case MBEDTLS_MPI_MOD_EXT_REP_LE: 97 return mbedtls_mpi_core_write_le(A, N->limbs, 98 output, output_length); 99 case MBEDTLS_MPI_MOD_EXT_REP_BE: 100 return mbedtls_mpi_core_write_be(A, N->limbs, 101 output, output_length); 102 default: 103 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 104 } 105 } 106 107 /* BEGIN MERGE SLOT 1 */ 108 109 /* END MERGE SLOT 1 */ 110 111 /* BEGIN MERGE SLOT 2 */ 112 113 void mbedtls_mpi_mod_raw_sub(mbedtls_mpi_uint *X, 114 const mbedtls_mpi_uint *A, 115 const mbedtls_mpi_uint *B, 116 const mbedtls_mpi_mod_modulus *N) 117 { 118 mbedtls_mpi_uint c = mbedtls_mpi_core_sub(X, A, B, N->limbs); 119 120 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c); 121 } 122 123 #if defined(MBEDTLS_TEST_HOOKS) 124 125 MBEDTLS_STATIC_TESTABLE 126 void mbedtls_mpi_mod_raw_fix_quasi_reduction(mbedtls_mpi_uint *X, 127 const mbedtls_mpi_mod_modulus *N) 128 { 129 mbedtls_mpi_uint c = mbedtls_mpi_core_sub(X, X, N->p, N->limbs); 130 131 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) c); 132 } 133 134 #endif /* MBEDTLS_TEST_HOOKS */ 135 136 void mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint *X, 137 const mbedtls_mpi_uint *A, 138 const mbedtls_mpi_uint *B, 139 const mbedtls_mpi_mod_modulus *N, 140 mbedtls_mpi_uint *T) 141 { 142 mbedtls_mpi_core_montmul(X, A, B, N->limbs, N->p, N->limbs, 143 N->rep.mont.mm, T); 144 } 145 146 /* END MERGE SLOT 2 */ 147 148 /* BEGIN MERGE SLOT 3 */ 149 150 size_t mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs) 151 { 152 /* mbedtls_mpi_mod_raw_inv_prime() needs a temporary for the exponent, 153 * which will be the same size as the modulus and input (AN_limbs), 154 * and additional space to pass to mbedtls_mpi_core_exp_mod(). */ 155 return AN_limbs + 156 mbedtls_mpi_core_exp_mod_working_limbs(AN_limbs, AN_limbs); 157 } 158 159 void mbedtls_mpi_mod_raw_inv_prime(mbedtls_mpi_uint *X, 160 const mbedtls_mpi_uint *A, 161 const mbedtls_mpi_uint *N, 162 size_t AN_limbs, 163 const mbedtls_mpi_uint *RR, 164 mbedtls_mpi_uint *T) 165 { 166 /* Inversion by power: g^|G| = 1 => g^(-1) = g^(|G|-1), and 167 * |G| = N - 1, so we want 168 * g^(|G|-1) = g^(N - 2) 169 */ 170 171 /* Use the first AN_limbs of T to hold N - 2 */ 172 mbedtls_mpi_uint *Nminus2 = T; 173 (void) mbedtls_mpi_core_sub_int(Nminus2, N, 2, AN_limbs); 174 175 /* Rest of T is given to exp_mod for its working space */ 176 mbedtls_mpi_core_exp_mod(X, 177 A, N, AN_limbs, Nminus2, AN_limbs, 178 RR, T + AN_limbs); 179 } 180 181 /* END MERGE SLOT 3 */ 182 183 /* BEGIN MERGE SLOT 4 */ 184 185 /* END MERGE SLOT 4 */ 186 187 /* BEGIN MERGE SLOT 5 */ 188 void mbedtls_mpi_mod_raw_add(mbedtls_mpi_uint *X, 189 const mbedtls_mpi_uint *A, 190 const mbedtls_mpi_uint *B, 191 const mbedtls_mpi_mod_modulus *N) 192 { 193 mbedtls_mpi_uint carry, borrow; 194 carry = mbedtls_mpi_core_add(X, A, B, N->limbs); 195 borrow = mbedtls_mpi_core_sub(X, X, N->p, N->limbs); 196 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) (carry ^ borrow)); 197 } 198 /* END MERGE SLOT 5 */ 199 200 /* BEGIN MERGE SLOT 6 */ 201 202 int mbedtls_mpi_mod_raw_canonical_to_modulus_rep( 203 mbedtls_mpi_uint *X, 204 const mbedtls_mpi_mod_modulus *N) 205 { 206 switch (N->int_rep) { 207 case MBEDTLS_MPI_MOD_REP_MONTGOMERY: 208 return mbedtls_mpi_mod_raw_to_mont_rep(X, N); 209 case MBEDTLS_MPI_MOD_REP_OPT_RED: 210 return 0; 211 default: 212 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 213 } 214 } 215 216 int mbedtls_mpi_mod_raw_modulus_to_canonical_rep( 217 mbedtls_mpi_uint *X, 218 const mbedtls_mpi_mod_modulus *N) 219 { 220 switch (N->int_rep) { 221 case MBEDTLS_MPI_MOD_REP_MONTGOMERY: 222 return mbedtls_mpi_mod_raw_from_mont_rep(X, N); 223 case MBEDTLS_MPI_MOD_REP_OPT_RED: 224 return 0; 225 default: 226 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; 227 } 228 } 229 230 int mbedtls_mpi_mod_raw_random(mbedtls_mpi_uint *X, 231 mbedtls_mpi_uint min, 232 const mbedtls_mpi_mod_modulus *N, 233 int (*f_rng)(void *, unsigned char *, size_t), 234 void *p_rng) 235 { 236 int ret = mbedtls_mpi_core_random(X, min, N->p, N->limbs, f_rng, p_rng); 237 if (ret != 0) { 238 return ret; 239 } 240 return mbedtls_mpi_mod_raw_canonical_to_modulus_rep(X, N); 241 } 242 243 /* END MERGE SLOT 6 */ 244 245 /* BEGIN MERGE SLOT 7 */ 246 int mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint *X, 247 const mbedtls_mpi_mod_modulus *N) 248 { 249 mbedtls_mpi_uint *T; 250 const size_t t_limbs = mbedtls_mpi_core_montmul_working_limbs(N->limbs); 251 252 if ((T = (mbedtls_mpi_uint *) mbedtls_calloc(t_limbs, ciL)) == NULL) { 253 return MBEDTLS_ERR_MPI_ALLOC_FAILED; 254 } 255 256 mbedtls_mpi_core_to_mont_rep(X, X, N->p, N->limbs, 257 N->rep.mont.mm, N->rep.mont.rr, T); 258 259 mbedtls_platform_zeroize(T, t_limbs * ciL); 260 mbedtls_free(T); 261 return 0; 262 } 263 264 int mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint *X, 265 const mbedtls_mpi_mod_modulus *N) 266 { 267 const size_t t_limbs = mbedtls_mpi_core_montmul_working_limbs(N->limbs); 268 mbedtls_mpi_uint *T; 269 270 if ((T = (mbedtls_mpi_uint *) mbedtls_calloc(t_limbs, ciL)) == NULL) { 271 return MBEDTLS_ERR_MPI_ALLOC_FAILED; 272 } 273 274 mbedtls_mpi_core_from_mont_rep(X, X, N->p, N->limbs, N->rep.mont.mm, T); 275 276 mbedtls_platform_zeroize(T, t_limbs * ciL); 277 mbedtls_free(T); 278 return 0; 279 } 280 281 void mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint *X, 282 const mbedtls_mpi_uint *A, 283 const mbedtls_mpi_mod_modulus *N) 284 { 285 mbedtls_mpi_core_sub(X, N->p, A, N->limbs); 286 287 /* If A=0 initially, then X=N now. Detect this by 288 * subtracting N and catching the carry. */ 289 mbedtls_mpi_uint borrow = mbedtls_mpi_core_sub(X, X, N->p, N->limbs); 290 (void) mbedtls_mpi_core_add_if(X, N->p, N->limbs, (unsigned) borrow); 291 } 292 /* END MERGE SLOT 7 */ 293 294 /* BEGIN MERGE SLOT 8 */ 295 296 /* END MERGE SLOT 8 */ 297 298 /* BEGIN MERGE SLOT 9 */ 299 300 /* END MERGE SLOT 9 */ 301 302 /* BEGIN MERGE SLOT 10 */ 303 304 /* END MERGE SLOT 10 */ 305 306 #endif /* MBEDTLS_BIGNUM_C */ 307