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
mbedtls_mpi_mod_raw_cond_assign(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_mod_modulus * N,unsigned char assign)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
mbedtls_mpi_mod_raw_cond_swap(mbedtls_mpi_uint * X,mbedtls_mpi_uint * Y,const mbedtls_mpi_mod_modulus * N,unsigned char swap)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
mbedtls_mpi_mod_raw_read(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N,const unsigned char * input,size_t input_length,mbedtls_mpi_mod_ext_rep ext_rep)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
mbedtls_mpi_mod_raw_write(const mbedtls_mpi_uint * A,const mbedtls_mpi_mod_modulus * N,unsigned char * output,size_t output_length,mbedtls_mpi_mod_ext_rep ext_rep)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
mbedtls_mpi_mod_raw_sub(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * B,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_raw_fix_quasi_reduction(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_raw_mul(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * B,const mbedtls_mpi_mod_modulus * N,mbedtls_mpi_uint * T)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
mbedtls_mpi_mod_raw_inv_prime_working_limbs(size_t AN_limbs)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
mbedtls_mpi_mod_raw_inv_prime(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * N,size_t AN_limbs,const mbedtls_mpi_uint * RR,mbedtls_mpi_uint * T)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
mbedtls_mpi_mod_raw_add(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_uint * B,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_raw_canonical_to_modulus_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_raw_modulus_to_canonical_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_raw_random(mbedtls_mpi_uint * X,mbedtls_mpi_uint min,const mbedtls_mpi_mod_modulus * N,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)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
mbedtls_mpi_mod_raw_to_mont_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_raw_from_mont_rep(mbedtls_mpi_uint * X,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_raw_neg(mbedtls_mpi_uint * X,const mbedtls_mpi_uint * A,const mbedtls_mpi_mod_modulus * N)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 */
277
