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
mbedtls_mpi_mod_residue_setup(mbedtls_mpi_mod_residue * r,const mbedtls_mpi_mod_modulus * N,mbedtls_mpi_uint * p,size_t p_limbs)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
mbedtls_mpi_mod_residue_release(mbedtls_mpi_mod_residue * r)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
mbedtls_mpi_mod_modulus_init(mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_modulus_free(mbedtls_mpi_mod_modulus * N)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
set_mont_const_square(const mbedtls_mpi_uint ** X,const mbedtls_mpi_uint * A,size_t limbs)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
standard_modulus_setup(mbedtls_mpi_mod_modulus * N,const mbedtls_mpi_uint * p,size_t p_limbs,mbedtls_mpi_mod_rep_selector int_rep)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
mbedtls_mpi_mod_modulus_setup(mbedtls_mpi_mod_modulus * N,const mbedtls_mpi_uint * p,size_t p_limbs)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
mbedtls_mpi_mod_optred_modulus_setup(mbedtls_mpi_mod_modulus * N,const mbedtls_mpi_uint * p,size_t p_limbs,mbedtls_mpi_modp_fn modp)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
mbedtls_mpi_mod_mul(mbedtls_mpi_mod_residue * X,const mbedtls_mpi_mod_residue * A,const mbedtls_mpi_mod_residue * B,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_sub(mbedtls_mpi_mod_residue * X,const mbedtls_mpi_mod_residue * A,const mbedtls_mpi_mod_residue * B,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_inv_mont(mbedtls_mpi_mod_residue * X,const mbedtls_mpi_mod_residue * A,const mbedtls_mpi_mod_modulus * N,mbedtls_mpi_uint * working_memory)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
mbedtls_mpi_mod_inv_non_mont(mbedtls_mpi_mod_residue * X,const mbedtls_mpi_mod_residue * A,const mbedtls_mpi_mod_modulus * N,mbedtls_mpi_uint * working_memory)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
mbedtls_mpi_mod_inv(mbedtls_mpi_mod_residue * X,const mbedtls_mpi_mod_residue * A,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_add(mbedtls_mpi_mod_residue * X,const mbedtls_mpi_mod_residue * A,const mbedtls_mpi_mod_residue * B,const mbedtls_mpi_mod_modulus * N)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
mbedtls_mpi_mod_random(mbedtls_mpi_mod_residue * X,mbedtls_mpi_uint min,const mbedtls_mpi_mod_modulus * N,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)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
mbedtls_mpi_mod_read(mbedtls_mpi_mod_residue * r,const mbedtls_mpi_mod_modulus * N,const unsigned char * buf,size_t buflen,mbedtls_mpi_mod_ext_rep ext_rep)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
mbedtls_mpi_mod_write(const mbedtls_mpi_mod_residue * r,const mbedtls_mpi_mod_modulus * N,unsigned char * buf,size_t buflen,mbedtls_mpi_mod_ext_rep ext_rep)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 */
395
