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