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 
mbedtls_mpi_mod_residue_setup(mbedtls_mpi_mod_residue * r,const mbedtls_mpi_mod_modulus * N,mbedtls_mpi_uint * p,size_t p_limbs)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 
mbedtls_mpi_mod_residue_release(mbedtls_mpi_mod_residue * r)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 
mbedtls_mpi_mod_modulus_init(mbedtls_mpi_mod_modulus * N)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 
mbedtls_mpi_mod_modulus_free(mbedtls_mpi_mod_modulus * N)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 
set_mont_const_square(const mbedtls_mpi_uint ** X,const mbedtls_mpi_uint * A,size_t limbs)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 
mbedtls_mpi_mod_modulus_setup(mbedtls_mpi_mod_modulus * N,const mbedtls_mpi_uint * p,size_t p_limbs,mbedtls_mpi_mod_rep_selector int_rep)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 
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)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 */
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)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 
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)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 
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)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 
mbedtls_mpi_mod_inv(mbedtls_mpi_mod_residue * X,const mbedtls_mpi_mod_residue * A,const mbedtls_mpi_mod_modulus * N)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 */
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)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 
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)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 */
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)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 
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)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