Line data Source code
1 : /*
2 : * Multi-precision integer library
3 : *
4 : * Copyright The Mbed TLS Contributors
5 : * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 : */
7 :
8 : /*
9 : * The following sources were referenced in the design of this Multi-precision
10 : * Integer library:
11 : *
12 : * [1] Handbook of Applied Cryptography - 1997
13 : * Menezes, van Oorschot and Vanstone
14 : *
15 : * [2] Multi-Precision Math
16 : * Tom St Denis
17 : * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
18 : *
19 : * [3] GNU Multi-Precision Arithmetic Library
20 : * https://gmplib.org/manual/index.html
21 : *
22 : */
23 :
24 : #include "common.h"
25 :
26 : #if defined(MBEDTLS_BIGNUM_C)
27 :
28 : #include "mbedtls/bignum.h"
29 : #include "bignum_core.h"
30 : #include "bignum_internal.h"
31 : #include "bn_mul.h"
32 : #include "mbedtls/platform_util.h"
33 : #include "mbedtls/error.h"
34 : #include "constant_time_internal.h"
35 :
36 : #include <limits.h>
37 : #include <string.h>
38 :
39 : #include "mbedtls/platform.h"
40 :
41 :
42 :
43 : /*
44 : * Conditionally select an MPI sign in constant time.
45 : * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid
46 : * values.)
47 : */
48 4838708 : static inline signed short mbedtls_ct_mpi_sign_if(mbedtls_ct_condition_t cond,
49 : signed short sign1, signed short sign2)
50 : {
51 4838708 : return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1;
52 : }
53 :
54 : /*
55 : * Compare signed values in constant time
56 : */
57 0 : int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X,
58 : const mbedtls_mpi *Y,
59 : unsigned *ret)
60 : {
61 : mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result;
62 :
63 0 : if (X->n != Y->n) {
64 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
65 : }
66 :
67 : /*
68 : * Set N_is_negative to MBEDTLS_CT_FALSE if N >= 0, MBEDTLS_CT_TRUE if N < 0.
69 : * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
70 : */
71 0 : X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1);
72 0 : Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1);
73 :
74 : /*
75 : * If the signs are different, then the positive operand is the bigger.
76 : * That is if X is negative (X_is_negative == 1), then X < Y is true and it
77 : * is false if X is positive (X_is_negative == 0).
78 : */
79 0 : different_sign = mbedtls_ct_bool_ne(X_is_negative, Y_is_negative); // true if different sign
80 0 : result = mbedtls_ct_bool_and(different_sign, X_is_negative);
81 :
82 : /*
83 : * Assuming signs are the same, compare X and Y. We switch the comparison
84 : * order if they are negative so that we get the right result, regardles of
85 : * sign.
86 : */
87 :
88 : /* This array is used to conditionally swap the pointers in const time */
89 0 : void * const p[2] = { X->p, Y->p };
90 0 : size_t i = mbedtls_ct_size_if_else_0(X_is_negative, 1);
91 0 : mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n);
92 :
93 : /*
94 : * Store in result iff the signs are the same (i.e., iff different_sign == false). If
95 : * the signs differ, result has already been set, so we don't change it.
96 : */
97 0 : result = mbedtls_ct_bool_or(result,
98 : mbedtls_ct_bool_and(mbedtls_ct_bool_not(different_sign), lt));
99 :
100 0 : *ret = mbedtls_ct_uint_if_else_0(result, 1);
101 :
102 0 : return 0;
103 : }
104 :
105 : /*
106 : * Conditionally assign X = Y, without leaking information
107 : * about whether the assignment was made or not.
108 : * (Leaking information about the respective sizes of X and Y is ok however.)
109 : */
110 : #if defined(_MSC_VER) && defined(MBEDTLS_PLATFORM_IS_WINDOWS_ON_ARM64) && \
111 : (_MSC_FULL_VER < 193131103)
112 : /*
113 : * MSVC miscompiles this function if it's inlined prior to Visual Studio 2022 version 17.1. See:
114 : * https://developercommunity.visualstudio.com/t/c-compiler-miscompiles-part-of-mbedtls-library-on/1646989
115 : */
116 : __declspec(noinline)
117 : #endif
118 4838708 : int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X,
119 : const mbedtls_mpi *Y,
120 : unsigned char assign)
121 : {
122 4838708 : int ret = 0;
123 :
124 4838708 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
125 :
126 : {
127 4838708 : mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign);
128 :
129 4838708 : X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s);
130 :
131 4838708 : mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign);
132 :
133 4838708 : mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign);
134 4855368 : for (size_t i = Y->n; i < X->n; i++) {
135 16660 : X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]);
136 : }
137 : }
138 :
139 4838708 : cleanup:
140 4838708 : return ret;
141 : }
142 :
143 : /*
144 : * Conditionally swap X and Y, without leaking information
145 : * about whether the swap was made or not.
146 : * Here it is not ok to simply swap the pointers, which would lead to
147 : * different memory access patterns when X and Y are used afterwards.
148 : */
149 0 : int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X,
150 : mbedtls_mpi *Y,
151 : unsigned char swap)
152 : {
153 0 : int ret = 0;
154 : int s;
155 :
156 0 : if (X == Y) {
157 0 : return 0;
158 : }
159 :
160 0 : mbedtls_ct_condition_t do_swap = mbedtls_ct_bool(swap);
161 :
162 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
163 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n));
164 :
165 0 : s = X->s;
166 0 : X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s);
167 0 : Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s);
168 :
169 0 : mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap);
170 :
171 0 : cleanup:
172 0 : return ret;
173 : }
174 :
175 : /* Implementation that should never be optimized out by the compiler */
176 : #define mbedtls_mpi_zeroize_and_free(v, n) mbedtls_zeroize_and_free(v, ciL * (n))
177 :
178 : /*
179 : * Initialize one MPI
180 : */
181 13417917 : void mbedtls_mpi_init(mbedtls_mpi *X)
182 : {
183 13417917 : X->s = 1;
184 13417917 : X->n = 0;
185 13417917 : X->p = NULL;
186 13417917 : }
187 :
188 : /*
189 : * Unallocate one MPI
190 : */
191 13342304 : void mbedtls_mpi_free(mbedtls_mpi *X)
192 : {
193 13342304 : if (X == NULL) {
194 0 : return;
195 : }
196 :
197 13342304 : if (X->p != NULL) {
198 2337787 : mbedtls_mpi_zeroize_and_free(X->p, X->n);
199 : }
200 :
201 13342304 : X->s = 1;
202 13342304 : X->n = 0;
203 13342304 : X->p = NULL;
204 : }
205 :
206 : /*
207 : * Enlarge to the specified number of limbs
208 : */
209 51292373 : int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
210 : {
211 : mbedtls_mpi_uint *p;
212 :
213 51292373 : if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
214 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
215 : }
216 :
217 51292373 : if (X->n < nblimbs) {
218 2595379 : if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL)) == NULL) {
219 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
220 : }
221 :
222 2595379 : if (X->p != NULL) {
223 256819 : memcpy(p, X->p, X->n * ciL);
224 256819 : mbedtls_mpi_zeroize_and_free(X->p, X->n);
225 : }
226 :
227 : /* nblimbs fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
228 : * fits, and we've checked that nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
229 2595379 : X->n = (unsigned short) nblimbs;
230 2595379 : X->p = p;
231 : }
232 :
233 51292373 : return 0;
234 : }
235 :
236 : /*
237 : * Resize down as much as possible,
238 : * while keeping at least the specified number of limbs
239 : */
240 31373 : int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
241 : {
242 : mbedtls_mpi_uint *p;
243 : size_t i;
244 :
245 31373 : if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
246 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
247 : }
248 :
249 : /* Actually resize up if there are currently fewer than nblimbs limbs. */
250 31373 : if (X->n <= nblimbs) {
251 0 : return mbedtls_mpi_grow(X, nblimbs);
252 : }
253 : /* After this point, then X->n > nblimbs and in particular X->n > 0. */
254 :
255 208500 : for (i = X->n - 1; i > 0; i--) {
256 208500 : if (X->p[i] != 0) {
257 31373 : break;
258 : }
259 : }
260 31373 : i++;
261 :
262 31373 : if (i < nblimbs) {
263 279 : i = nblimbs;
264 : }
265 :
266 31373 : if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL) {
267 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
268 : }
269 :
270 31373 : if (X->p != NULL) {
271 31373 : memcpy(p, X->p, i * ciL);
272 31373 : mbedtls_mpi_zeroize_and_free(X->p, X->n);
273 : }
274 :
275 : /* i fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
276 : * fits, and we've checked that i <= nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
277 31373 : X->n = (unsigned short) i;
278 31373 : X->p = p;
279 :
280 31373 : return 0;
281 : }
282 :
283 : /* Resize X to have exactly n limbs and set it to 0. */
284 32875 : static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
285 : {
286 32875 : if (limbs == 0) {
287 0 : mbedtls_mpi_free(X);
288 0 : return 0;
289 32875 : } else if (X->n == limbs) {
290 110 : memset(X->p, 0, limbs * ciL);
291 110 : X->s = 1;
292 110 : return 0;
293 : } else {
294 32765 : mbedtls_mpi_free(X);
295 32765 : return mbedtls_mpi_grow(X, limbs);
296 : }
297 : }
298 :
299 : /*
300 : * Copy the contents of Y into X.
301 : *
302 : * This function is not constant-time. Leading zeros in Y may be removed.
303 : *
304 : * Ensure that X does not shrink. This is not guaranteed by the public API,
305 : * but some code in the bignum module might still rely on this property.
306 : */
307 4708727 : int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
308 : {
309 4708727 : int ret = 0;
310 : size_t i;
311 :
312 4708727 : if (X == Y) {
313 74012 : return 0;
314 : }
315 :
316 4634715 : if (Y->n == 0) {
317 2231 : if (X->n != 0) {
318 0 : X->s = 1;
319 0 : memset(X->p, 0, X->n * ciL);
320 : }
321 2231 : return 0;
322 : }
323 :
324 27078096 : for (i = Y->n - 1; i > 0; i--) {
325 27051581 : if (Y->p[i] != 0) {
326 4605969 : break;
327 : }
328 : }
329 4632484 : i++;
330 :
331 4632484 : X->s = Y->s;
332 :
333 4632484 : if (X->n < i) {
334 1942415 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i));
335 : } else {
336 2690069 : memset(X->p + i, 0, (X->n - i) * ciL);
337 : }
338 :
339 4632484 : memcpy(X->p, Y->p, i * ciL);
340 :
341 4632484 : cleanup:
342 :
343 4632484 : return ret;
344 : }
345 :
346 : /*
347 : * Swap the contents of X and Y
348 : */
349 0 : void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y)
350 : {
351 : mbedtls_mpi T;
352 :
353 0 : memcpy(&T, X, sizeof(mbedtls_mpi));
354 0 : memcpy(X, Y, sizeof(mbedtls_mpi));
355 0 : memcpy(Y, &T, sizeof(mbedtls_mpi));
356 0 : }
357 :
358 18428175 : static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
359 : {
360 18428175 : if (z >= 0) {
361 18425233 : return z;
362 : }
363 : /* Take care to handle the most negative value (-2^(biL-1)) correctly.
364 : * A naive -z would have undefined behavior.
365 : * Write this in a way that makes popular compilers happy (GCC, Clang,
366 : * MSVC). */
367 2942 : return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
368 : }
369 :
370 : /* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
371 : * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
372 : #define TO_SIGN(x) ((mbedtls_mpi_sint) (((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1)
373 :
374 : /*
375 : * Set value from integer
376 : */
377 6667076 : int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
378 : {
379 6667076 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
380 :
381 6667076 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1));
382 6667076 : memset(X->p, 0, X->n * ciL);
383 :
384 6667076 : X->p[0] = mpi_sint_abs(z);
385 6667076 : X->s = TO_SIGN(z);
386 :
387 6667076 : cleanup:
388 :
389 6667076 : return ret;
390 : }
391 :
392 : /*
393 : * Get a specific bit
394 : */
395 881106 : int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
396 : {
397 881106 : if (X->n * biL <= pos) {
398 7144 : return 0;
399 : }
400 :
401 873962 : return (X->p[pos / biL] >> (pos % biL)) & 0x01;
402 : }
403 :
404 : /*
405 : * Set a bit to a specific value of 0 or 1
406 : */
407 0 : int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
408 : {
409 0 : int ret = 0;
410 0 : size_t off = pos / biL;
411 0 : size_t idx = pos % biL;
412 :
413 0 : if (val != 0 && val != 1) {
414 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
415 : }
416 :
417 0 : if (X->n * biL <= pos) {
418 0 : if (val == 0) {
419 0 : return 0;
420 : }
421 :
422 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1));
423 : }
424 :
425 0 : X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx);
426 0 : X->p[off] |= (mbedtls_mpi_uint) val << idx;
427 :
428 0 : cleanup:
429 :
430 0 : return ret;
431 : }
432 :
433 : /*
434 : * Return the number of less significant zero-bits
435 : */
436 3578754 : size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
437 : {
438 : size_t i;
439 :
440 : #if defined(__has_builtin)
441 : #if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz)
442 : #define mbedtls_mpi_uint_ctz __builtin_ctz
443 : #elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl)
444 : #define mbedtls_mpi_uint_ctz __builtin_ctzl
445 : #elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll)
446 : #define mbedtls_mpi_uint_ctz __builtin_ctzll
447 : #endif
448 : #endif
449 :
450 : #if defined(mbedtls_mpi_uint_ctz)
451 3578754 : for (i = 0; i < X->n; i++) {
452 3578754 : if (X->p[i] != 0) {
453 3578754 : return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
454 : }
455 : }
456 : #else
457 : size_t count = 0;
458 : for (i = 0; i < X->n; i++) {
459 : for (size_t j = 0; j < biL; j++, count++) {
460 : if (((X->p[i] >> j) & 1) != 0) {
461 : return count;
462 : }
463 : }
464 : }
465 : #endif
466 :
467 0 : return 0;
468 : }
469 :
470 : /*
471 : * Return the number of bits
472 : */
473 8594847 : size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
474 : {
475 8594847 : return mbedtls_mpi_core_bitlen(X->p, X->n);
476 : }
477 :
478 : /*
479 : * Return the total size in bytes
480 : */
481 16890 : size_t mbedtls_mpi_size(const mbedtls_mpi *X)
482 : {
483 16890 : return (mbedtls_mpi_bitlen(X) + 7) >> 3;
484 : }
485 :
486 : /*
487 : * Convert an ASCII character to digit value
488 : */
489 0 : static int mpi_get_digit(mbedtls_mpi_uint *d, int radix, char c)
490 : {
491 0 : *d = 255;
492 :
493 0 : if (c >= 0x30 && c <= 0x39) {
494 0 : *d = c - 0x30;
495 : }
496 0 : if (c >= 0x41 && c <= 0x46) {
497 0 : *d = c - 0x37;
498 : }
499 0 : if (c >= 0x61 && c <= 0x66) {
500 0 : *d = c - 0x57;
501 : }
502 :
503 0 : if (*d >= (mbedtls_mpi_uint) radix) {
504 0 : return MBEDTLS_ERR_MPI_INVALID_CHARACTER;
505 : }
506 :
507 0 : return 0;
508 : }
509 :
510 : /*
511 : * Import from an ASCII string
512 : */
513 0 : int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
514 : {
515 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
516 : size_t i, j, slen, n;
517 0 : int sign = 1;
518 : mbedtls_mpi_uint d;
519 : mbedtls_mpi T;
520 :
521 0 : if (radix < 2 || radix > 16) {
522 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
523 : }
524 :
525 0 : mbedtls_mpi_init(&T);
526 :
527 0 : if (s[0] == 0) {
528 0 : mbedtls_mpi_free(X);
529 0 : return 0;
530 : }
531 :
532 0 : if (s[0] == '-') {
533 0 : ++s;
534 0 : sign = -1;
535 : }
536 :
537 0 : slen = strlen(s);
538 :
539 0 : if (radix == 16) {
540 0 : if (slen > SIZE_MAX >> 2) {
541 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
542 : }
543 :
544 0 : n = BITS_TO_LIMBS(slen << 2);
545 :
546 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n));
547 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
548 :
549 0 : for (i = slen, j = 0; i > 0; i--, j++) {
550 0 : MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1]));
551 0 : X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2);
552 : }
553 : } else {
554 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
555 :
556 0 : for (i = 0; i < slen; i++) {
557 0 : MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i]));
558 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix));
559 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d));
560 : }
561 : }
562 :
563 0 : if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) {
564 0 : X->s = -1;
565 : }
566 :
567 0 : cleanup:
568 :
569 0 : mbedtls_mpi_free(&T);
570 :
571 0 : return ret;
572 : }
573 :
574 : /*
575 : * Helper to write the digits high-order first.
576 : */
577 0 : static int mpi_write_hlp(mbedtls_mpi *X, int radix,
578 : char **p, const size_t buflen)
579 : {
580 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
581 : mbedtls_mpi_uint r;
582 0 : size_t length = 0;
583 0 : char *p_end = *p + buflen;
584 :
585 : do {
586 0 : if (length >= buflen) {
587 0 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
588 : }
589 :
590 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix));
591 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix));
592 : /*
593 : * Write the residue in the current position, as an ASCII character.
594 : */
595 0 : if (r < 0xA) {
596 0 : *(--p_end) = (char) ('0' + r);
597 : } else {
598 0 : *(--p_end) = (char) ('A' + (r - 0xA));
599 : }
600 :
601 0 : length++;
602 0 : } while (mbedtls_mpi_cmp_int(X, 0) != 0);
603 :
604 0 : memmove(*p, p_end, length);
605 0 : *p += length;
606 :
607 0 : cleanup:
608 :
609 0 : return ret;
610 : }
611 :
612 : /*
613 : * Export into an ASCII string
614 : */
615 0 : int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix,
616 : char *buf, size_t buflen, size_t *olen)
617 : {
618 0 : int ret = 0;
619 : size_t n;
620 : char *p;
621 : mbedtls_mpi T;
622 :
623 0 : if (radix < 2 || radix > 16) {
624 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
625 : }
626 :
627 0 : n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */
628 0 : if (radix >= 4) {
629 0 : n >>= 1; /* Number of 4-adic digits necessary to present
630 : * `n`. If radix > 4, this might be a strict
631 : * overapproximation of the number of
632 : * radix-adic digits needed to present `n`. */
633 : }
634 0 : if (radix >= 16) {
635 0 : n >>= 1; /* Number of hexadecimal digits necessary to
636 : * present `n`. */
637 :
638 : }
639 0 : n += 1; /* Terminating null byte */
640 0 : n += 1; /* Compensate for the divisions above, which round down `n`
641 : * in case it's not even. */
642 0 : n += 1; /* Potential '-'-sign. */
643 0 : n += (n & 1); /* Make n even to have enough space for hexadecimal writing,
644 : * which always uses an even number of hex-digits. */
645 :
646 0 : if (buflen < n) {
647 0 : *olen = n;
648 0 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
649 : }
650 :
651 0 : p = buf;
652 0 : mbedtls_mpi_init(&T);
653 :
654 0 : if (X->s == -1) {
655 0 : *p++ = '-';
656 0 : buflen--;
657 : }
658 :
659 0 : if (radix == 16) {
660 : int c;
661 : size_t i, j, k;
662 :
663 0 : for (i = X->n, k = 0; i > 0; i--) {
664 0 : for (j = ciL; j > 0; j--) {
665 0 : c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF;
666 :
667 0 : if (c == 0 && k == 0 && (i + j) != 2) {
668 0 : continue;
669 : }
670 :
671 0 : *(p++) = "0123456789ABCDEF" [c / 16];
672 0 : *(p++) = "0123456789ABCDEF" [c % 16];
673 0 : k = 1;
674 : }
675 : }
676 : } else {
677 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X));
678 :
679 0 : if (T.s == -1) {
680 0 : T.s = 1;
681 : }
682 :
683 0 : MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen));
684 : }
685 :
686 0 : *p++ = '\0';
687 0 : *olen = (size_t) (p - buf);
688 :
689 0 : cleanup:
690 :
691 0 : mbedtls_mpi_free(&T);
692 :
693 0 : return ret;
694 : }
695 :
696 : #if defined(MBEDTLS_FS_IO)
697 : /*
698 : * Read X from an opened file
699 : */
700 : int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin)
701 : {
702 : mbedtls_mpi_uint d;
703 : size_t slen;
704 : char *p;
705 : /*
706 : * Buffer should have space for (short) label and decimal formatted MPI,
707 : * newline characters and '\0'
708 : */
709 : char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
710 :
711 : if (radix < 2 || radix > 16) {
712 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
713 : }
714 :
715 : memset(s, 0, sizeof(s));
716 : if (fgets(s, sizeof(s) - 1, fin) == NULL) {
717 : return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
718 : }
719 :
720 : slen = strlen(s);
721 : if (slen == sizeof(s) - 2) {
722 : return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
723 : }
724 :
725 : if (slen > 0 && s[slen - 1] == '\n') {
726 : slen--; s[slen] = '\0';
727 : }
728 : if (slen > 0 && s[slen - 1] == '\r') {
729 : slen--; s[slen] = '\0';
730 : }
731 :
732 : p = s + slen;
733 : while (p-- > s) {
734 : if (mpi_get_digit(&d, radix, *p) != 0) {
735 : break;
736 : }
737 : }
738 :
739 : return mbedtls_mpi_read_string(X, radix, p + 1);
740 : }
741 :
742 : /*
743 : * Write X into an opened file (or stdout if fout == NULL)
744 : */
745 : int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout)
746 : {
747 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
748 : size_t n, slen, plen;
749 : /*
750 : * Buffer should have space for (short) label and decimal formatted MPI,
751 : * newline characters and '\0'
752 : */
753 : char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
754 :
755 : if (radix < 2 || radix > 16) {
756 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
757 : }
758 :
759 : memset(s, 0, sizeof(s));
760 :
761 : MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n));
762 :
763 : if (p == NULL) {
764 : p = "";
765 : }
766 :
767 : plen = strlen(p);
768 : slen = strlen(s);
769 : s[slen++] = '\r';
770 : s[slen++] = '\n';
771 :
772 : if (fout != NULL) {
773 : if (fwrite(p, 1, plen, fout) != plen ||
774 : fwrite(s, 1, slen, fout) != slen) {
775 : return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
776 : }
777 : } else {
778 : mbedtls_printf("%s%s", p, s);
779 : }
780 :
781 : cleanup:
782 :
783 : return ret;
784 : }
785 : #endif /* MBEDTLS_FS_IO */
786 :
787 : /*
788 : * Import X from unsigned binary data, little endian
789 : *
790 : * This function is guaranteed to return an MPI with exactly the necessary
791 : * number of limbs (in particular, it does not skip 0s in the input).
792 : */
793 0 : int mbedtls_mpi_read_binary_le(mbedtls_mpi *X,
794 : const unsigned char *buf, size_t buflen)
795 : {
796 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
797 0 : const size_t limbs = CHARS_TO_LIMBS(buflen);
798 :
799 : /* Ensure that target MPI has exactly the necessary number of limbs */
800 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
801 :
802 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen));
803 :
804 0 : cleanup:
805 :
806 : /*
807 : * This function is also used to import keys. However, wiping the buffers
808 : * upon failure is not necessary because failure only can happen before any
809 : * input is copied.
810 : */
811 0 : return ret;
812 : }
813 :
814 : /*
815 : * Import X from unsigned binary data, big endian
816 : *
817 : * This function is guaranteed to return an MPI with exactly the necessary
818 : * number of limbs (in particular, it does not skip 0s in the input).
819 : */
820 31479 : int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
821 : {
822 31479 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
823 31479 : const size_t limbs = CHARS_TO_LIMBS(buflen);
824 :
825 : /* Ensure that target MPI has exactly the necessary number of limbs */
826 31479 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
827 :
828 31479 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
829 :
830 31479 : cleanup:
831 :
832 : /*
833 : * This function is also used to import keys. However, wiping the buffers
834 : * upon failure is not necessary because failure only can happen before any
835 : * input is copied.
836 : */
837 31479 : return ret;
838 : }
839 :
840 : /*
841 : * Export X into unsigned binary data, little endian
842 : */
843 0 : int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X,
844 : unsigned char *buf, size_t buflen)
845 : {
846 0 : return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen);
847 : }
848 :
849 : /*
850 : * Export X into unsigned binary data, big endian
851 : */
852 1117 : int mbedtls_mpi_write_binary(const mbedtls_mpi *X,
853 : unsigned char *buf, size_t buflen)
854 : {
855 1117 : return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
856 : }
857 :
858 : /*
859 : * Left-shift: X <<= count
860 : */
861 2222245 : int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
862 : {
863 2222245 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
864 : size_t i;
865 :
866 2222245 : i = mbedtls_mpi_bitlen(X) + count;
867 :
868 2222245 : if (X->n * biL < i) {
869 11771 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i)));
870 : }
871 :
872 2222245 : ret = 0;
873 :
874 2222245 : mbedtls_mpi_core_shift_l(X->p, X->n, count);
875 2222245 : cleanup:
876 :
877 2222245 : return ret;
878 : }
879 :
880 : /*
881 : * Right-shift: X >>= count
882 : */
883 15953901 : int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
884 : {
885 15953901 : if (X->n != 0) {
886 15953901 : mbedtls_mpi_core_shift_r(X->p, X->n, count);
887 : }
888 15953901 : return 0;
889 : }
890 :
891 : /*
892 : * Compare unsigned values
893 : */
894 15863705 : int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
895 : {
896 : size_t i, j;
897 :
898 72836288 : for (i = X->n; i > 0; i--) {
899 72821314 : if (X->p[i - 1] != 0) {
900 15848731 : break;
901 : }
902 : }
903 :
904 40122830 : for (j = Y->n; j > 0; j--) {
905 40118696 : if (Y->p[j - 1] != 0) {
906 15859571 : break;
907 : }
908 : }
909 :
910 : /* If i == j == 0, i.e. abs(X) == abs(Y),
911 : * we end up returning 0 at the end of the function. */
912 :
913 15863705 : if (i > j) {
914 1611511 : return 1;
915 : }
916 14252194 : if (j > i) {
917 28287 : return -1;
918 : }
919 :
920 14323555 : for (; i > 0; i--) {
921 14301430 : if (X->p[i - 1] > Y->p[i - 1]) {
922 4794319 : return 1;
923 : }
924 9507111 : if (X->p[i - 1] < Y->p[i - 1]) {
925 9407463 : return -1;
926 : }
927 : }
928 :
929 22125 : return 0;
930 : }
931 :
932 : /*
933 : * Compare signed values
934 : */
935 27864749 : int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
936 : {
937 : size_t i, j;
938 :
939 140090547 : for (i = X->n; i > 0; i--) {
940 140063390 : if (X->p[i - 1] != 0) {
941 27837592 : break;
942 : }
943 : }
944 :
945 46434057 : for (j = Y->n; j > 0; j--) {
946 34939936 : if (Y->p[j - 1] != 0) {
947 16370628 : break;
948 : }
949 : }
950 :
951 27864749 : if (i == 0 && j == 0) {
952 27150 : return 0;
953 : }
954 :
955 27837599 : if (i > j) {
956 14467934 : return X->s;
957 : }
958 13369665 : if (j > i) {
959 72611 : return -Y->s;
960 : }
961 :
962 13297054 : if (X->s > 0 && Y->s < 0) {
963 0 : return 1;
964 : }
965 13297054 : if (Y->s > 0 && X->s < 0) {
966 0 : return -1;
967 : }
968 :
969 13692739 : for (; i > 0; i--) {
970 13424936 : if (X->p[i - 1] > Y->p[i - 1]) {
971 1775968 : return X->s;
972 : }
973 11648968 : if (X->p[i - 1] < Y->p[i - 1]) {
974 11253283 : return -X->s;
975 : }
976 : }
977 :
978 267803 : return 0;
979 : }
980 :
981 : /*
982 : * Compare signed values
983 : */
984 11746027 : int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
985 : {
986 : mbedtls_mpi Y;
987 : mbedtls_mpi_uint p[1];
988 :
989 11746027 : *p = mpi_sint_abs(z);
990 11746027 : Y.s = TO_SIGN(z);
991 11746027 : Y.n = 1;
992 11746027 : Y.p = p;
993 :
994 11746027 : return mbedtls_mpi_cmp_mpi(X, &Y);
995 : }
996 :
997 : /*
998 : * Unsigned addition: X = |A| + |B| (HAC 14.7)
999 : */
1000 3969205 : int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1001 : {
1002 3969205 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1003 : size_t j;
1004 : mbedtls_mpi_uint *p;
1005 : mbedtls_mpi_uint c;
1006 :
1007 3969205 : if (X == B) {
1008 0 : const mbedtls_mpi *T = A; A = X; B = T;
1009 : }
1010 :
1011 3969205 : if (X != A) {
1012 488686 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1013 : }
1014 :
1015 : /*
1016 : * X must always be positive as a result of unsigned additions.
1017 : */
1018 3969205 : X->s = 1;
1019 :
1020 7246767 : for (j = B->n; j > 0; j--) {
1021 7245855 : if (B->p[j - 1] != 0) {
1022 3968293 : break;
1023 : }
1024 : }
1025 :
1026 : /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
1027 : * and B is 0 (of any size). */
1028 3969205 : if (j == 0) {
1029 912 : return 0;
1030 : }
1031 :
1032 3968293 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j));
1033 :
1034 : /* j is the number of non-zero limbs of B. Add those to X. */
1035 :
1036 3968293 : p = X->p;
1037 :
1038 3968293 : c = mbedtls_mpi_core_add(p, p, B->p, j);
1039 :
1040 3968293 : p += j;
1041 :
1042 : /* Now propagate any carry */
1043 :
1044 5691531 : while (c != 0) {
1045 1723238 : if (j >= X->n) {
1046 18260 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
1047 18260 : p = X->p + j;
1048 : }
1049 :
1050 1723238 : *p += c; c = (*p < c); j++; p++;
1051 : }
1052 :
1053 3968293 : cleanup:
1054 :
1055 3968293 : return ret;
1056 : }
1057 :
1058 : /*
1059 : * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1060 : */
1061 20555435 : int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1062 : {
1063 20555435 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1064 : size_t n;
1065 : mbedtls_mpi_uint carry;
1066 :
1067 75820318 : for (n = B->n; n > 0; n--) {
1068 75801210 : if (B->p[n - 1] != 0) {
1069 20536327 : break;
1070 : }
1071 : }
1072 20555435 : if (n > A->n) {
1073 : /* B >= (2^ciL)^n > A */
1074 0 : ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1075 0 : goto cleanup;
1076 : }
1077 :
1078 20555435 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n));
1079 :
1080 : /* Set the high limbs of X to match A. Don't touch the lower limbs
1081 : * because X might be aliased to B, and we must not overwrite the
1082 : * significant digits of B. */
1083 20555435 : if (A->n > n && A != X) {
1084 2915188 : memcpy(X->p + n, A->p + n, (A->n - n) * ciL);
1085 : }
1086 20555435 : if (X->n > A->n) {
1087 6468765 : memset(X->p + A->n, 0, (X->n - A->n) * ciL);
1088 : }
1089 :
1090 20555435 : carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
1091 20555435 : if (carry != 0) {
1092 : /* Propagate the carry through the rest of X. */
1093 4508045 : carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n);
1094 :
1095 : /* If we have further carry/borrow, the result is negative. */
1096 4508045 : if (carry != 0) {
1097 0 : ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1098 0 : goto cleanup;
1099 : }
1100 : }
1101 :
1102 : /* X should always be positive as a result of unsigned subtractions. */
1103 20555435 : X->s = 1;
1104 :
1105 20555435 : cleanup:
1106 20555435 : return ret;
1107 : }
1108 :
1109 : /* Common function for signed addition and subtraction.
1110 : * Calculate A + B * flip_B where flip_B is 1 or -1.
1111 : */
1112 19817776 : static int add_sub_mpi(mbedtls_mpi *X,
1113 : const mbedtls_mpi *A, const mbedtls_mpi *B,
1114 : int flip_B)
1115 : {
1116 : int ret, s;
1117 :
1118 19817776 : s = A->s;
1119 19817776 : if (A->s * B->s * flip_B < 0) {
1120 15848607 : int cmp = mbedtls_mpi_cmp_abs(A, B);
1121 15848607 : if (cmp >= 0) {
1122 6424031 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B));
1123 : /* If |A| = |B|, the result is 0 and we must set the sign bit
1124 : * to +1 regardless of which of A or B was negative. Otherwise,
1125 : * since |A| > |B|, the sign is the sign of A. */
1126 6424031 : X->s = cmp == 0 ? 1 : s;
1127 : } else {
1128 9424576 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A));
1129 : /* Since |A| < |B|, the sign is the opposite of A. */
1130 9424576 : X->s = -s;
1131 : }
1132 : } else {
1133 3969169 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B));
1134 3969169 : X->s = s;
1135 : }
1136 :
1137 19817776 : cleanup:
1138 :
1139 19817776 : return ret;
1140 : }
1141 :
1142 : /*
1143 : * Signed addition: X = A + B
1144 : */
1145 9011773 : int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1146 : {
1147 9011773 : return add_sub_mpi(X, A, B, 1);
1148 : }
1149 :
1150 : /*
1151 : * Signed subtraction: X = A - B
1152 : */
1153 10806003 : int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1154 : {
1155 10806003 : return add_sub_mpi(X, A, B, -1);
1156 : }
1157 :
1158 : /*
1159 : * Signed addition: X = A + b
1160 : */
1161 2 : int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1162 : {
1163 : mbedtls_mpi B;
1164 : mbedtls_mpi_uint p[1];
1165 :
1166 2 : p[0] = mpi_sint_abs(b);
1167 2 : B.s = TO_SIGN(b);
1168 2 : B.n = 1;
1169 2 : B.p = p;
1170 :
1171 2 : return mbedtls_mpi_add_mpi(X, A, &B);
1172 : }
1173 :
1174 : /*
1175 : * Signed subtraction: X = A - b
1176 : */
1177 15070 : int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1178 : {
1179 : mbedtls_mpi B;
1180 : mbedtls_mpi_uint p[1];
1181 :
1182 15070 : p[0] = mpi_sint_abs(b);
1183 15070 : B.s = TO_SIGN(b);
1184 15070 : B.n = 1;
1185 15070 : B.p = p;
1186 :
1187 15070 : return mbedtls_mpi_sub_mpi(X, A, &B);
1188 : }
1189 :
1190 : /*
1191 : * Baseline multiplication: X = A * B (HAC 14.12)
1192 : */
1193 6325187 : int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
1194 : {
1195 6325187 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1196 : size_t i, j;
1197 : mbedtls_mpi TA, TB;
1198 6325187 : int result_is_zero = 0;
1199 :
1200 6325187 : mbedtls_mpi_init(&TA);
1201 6325187 : mbedtls_mpi_init(&TB);
1202 :
1203 6325187 : if (X == A) {
1204 1801462 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
1205 : }
1206 6325187 : if (X == B) {
1207 21043 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
1208 : }
1209 :
1210 21512238 : for (i = A->n; i > 0; i--) {
1211 21512238 : if (A->p[i - 1] != 0) {
1212 6325187 : break;
1213 : }
1214 : }
1215 6325187 : if (i == 0) {
1216 0 : result_is_zero = 1;
1217 : }
1218 :
1219 28435704 : for (j = B->n; j > 0; j--) {
1220 28435704 : if (B->p[j - 1] != 0) {
1221 6325187 : break;
1222 : }
1223 : }
1224 6325187 : if (j == 0) {
1225 0 : result_is_zero = 1;
1226 : }
1227 :
1228 6325187 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
1229 6325187 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
1230 :
1231 6325187 : mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j);
1232 :
1233 : /* If the result is 0, we don't shortcut the operation, which reduces
1234 : * but does not eliminate side channels leaking the zero-ness. We do
1235 : * need to take care to set the sign bit properly since the library does
1236 : * not fully support an MPI object with a value of 0 and s == -1. */
1237 6325187 : if (result_is_zero) {
1238 0 : X->s = 1;
1239 : } else {
1240 6325187 : X->s = A->s * B->s;
1241 : }
1242 :
1243 6325187 : cleanup:
1244 :
1245 6325187 : mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA);
1246 :
1247 6325187 : return ret;
1248 : }
1249 :
1250 : /*
1251 : * Baseline multiplication: X = A * b
1252 : */
1253 602563 : int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
1254 : {
1255 602563 : size_t n = A->n;
1256 9624847 : while (n > 0 && A->p[n - 1] == 0) {
1257 9022284 : --n;
1258 : }
1259 :
1260 : /* The general method below doesn't work if b==0. */
1261 602563 : if (b == 0 || n == 0) {
1262 4 : return mbedtls_mpi_lset(X, 0);
1263 : }
1264 :
1265 : /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
1266 602559 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1267 : /* In general, A * b requires 1 limb more than b. If
1268 : * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1269 : * number of limbs as A and the call to grow() is not required since
1270 : * copy() will take care of the growth if needed. However, experimentally,
1271 : * making the call to grow() unconditional causes slightly fewer
1272 : * calls to calloc() in ECP code, presumably because it reuses the
1273 : * same mpi for a while and this way the mpi is more likely to directly
1274 : * grow to its final size.
1275 : *
1276 : * Note that calculating A*b as 0 + A*b doesn't work as-is because
1277 : * A,X can be the same. */
1278 602559 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1));
1279 602559 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1280 602559 : mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
1281 :
1282 602559 : cleanup:
1283 602559 : return ret;
1284 : }
1285 :
1286 : /*
1287 : * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1288 : * mbedtls_mpi_uint divisor, d
1289 : */
1290 41762 : static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1,
1291 : mbedtls_mpi_uint u0,
1292 : mbedtls_mpi_uint d,
1293 : mbedtls_mpi_uint *r)
1294 : {
1295 : #if defined(MBEDTLS_HAVE_UDBL)
1296 : mbedtls_t_udbl dividend, quotient;
1297 : #else
1298 : const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1299 : const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1;
1300 : mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1301 : mbedtls_mpi_uint u0_msw, u0_lsw;
1302 : size_t s;
1303 : #endif
1304 :
1305 : /*
1306 : * Check for overflow
1307 : */
1308 41762 : if (0 == d || u1 >= d) {
1309 0 : if (r != NULL) {
1310 0 : *r = ~(mbedtls_mpi_uint) 0u;
1311 : }
1312 :
1313 0 : return ~(mbedtls_mpi_uint) 0u;
1314 : }
1315 :
1316 : #if defined(MBEDTLS_HAVE_UDBL)
1317 41762 : dividend = (mbedtls_t_udbl) u1 << biL;
1318 41762 : dividend |= (mbedtls_t_udbl) u0;
1319 41762 : quotient = dividend / d;
1320 41762 : if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) {
1321 0 : quotient = ((mbedtls_t_udbl) 1 << biL) - 1;
1322 : }
1323 :
1324 41762 : if (r != NULL) {
1325 0 : *r = (mbedtls_mpi_uint) (dividend - (quotient * d));
1326 : }
1327 :
1328 41762 : return (mbedtls_mpi_uint) quotient;
1329 : #else
1330 :
1331 : /*
1332 : * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1333 : * Vol. 2 - Seminumerical Algorithms, Knuth
1334 : */
1335 :
1336 : /*
1337 : * Normalize the divisor, d, and dividend, u0, u1
1338 : */
1339 : s = mbedtls_mpi_core_clz(d);
1340 : d = d << s;
1341 :
1342 : u1 = u1 << s;
1343 : u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1));
1344 : u0 = u0 << s;
1345 :
1346 : d1 = d >> biH;
1347 : d0 = d & uint_halfword_mask;
1348 :
1349 : u0_msw = u0 >> biH;
1350 : u0_lsw = u0 & uint_halfword_mask;
1351 :
1352 : /*
1353 : * Find the first quotient and remainder
1354 : */
1355 : q1 = u1 / d1;
1356 : r0 = u1 - d1 * q1;
1357 :
1358 : while (q1 >= radix || (q1 * d0 > radix * r0 + u0_msw)) {
1359 : q1 -= 1;
1360 : r0 += d1;
1361 :
1362 : if (r0 >= radix) {
1363 : break;
1364 : }
1365 : }
1366 :
1367 : rAX = (u1 * radix) + (u0_msw - q1 * d);
1368 : q0 = rAX / d1;
1369 : r0 = rAX - q0 * d1;
1370 :
1371 : while (q0 >= radix || (q0 * d0 > radix * r0 + u0_lsw)) {
1372 : q0 -= 1;
1373 : r0 += d1;
1374 :
1375 : if (r0 >= radix) {
1376 : break;
1377 : }
1378 : }
1379 :
1380 : if (r != NULL) {
1381 : *r = (rAX * radix + u0_lsw - q0 * d) >> s;
1382 : }
1383 :
1384 : quotient = q1 * radix + q0;
1385 :
1386 : return quotient;
1387 : #endif
1388 : }
1389 :
1390 : /*
1391 : * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1392 : */
1393 15098 : int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1394 : const mbedtls_mpi *B)
1395 : {
1396 15098 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1397 : size_t i, n, t, k;
1398 : mbedtls_mpi X, Y, Z, T1, T2;
1399 : mbedtls_mpi_uint TP2[3];
1400 :
1401 15098 : if (mbedtls_mpi_cmp_int(B, 0) == 0) {
1402 0 : return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1403 : }
1404 :
1405 15098 : mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z);
1406 15098 : mbedtls_mpi_init(&T1);
1407 : /*
1408 : * Avoid dynamic memory allocations for constant-size T2.
1409 : *
1410 : * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1411 : * so nobody increase the size of the MPI and we're safe to use an on-stack
1412 : * buffer.
1413 : */
1414 15098 : T2.s = 1;
1415 15098 : T2.n = sizeof(TP2) / sizeof(*TP2);
1416 15098 : T2.p = TP2;
1417 :
1418 15098 : if (mbedtls_mpi_cmp_abs(A, B) < 0) {
1419 11174 : if (Q != NULL) {
1420 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0));
1421 : }
1422 11174 : if (R != NULL) {
1423 11174 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A));
1424 : }
1425 11174 : return 0;
1426 : }
1427 :
1428 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A));
1429 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B));
1430 3924 : X.s = Y.s = 1;
1431 :
1432 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2));
1433 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z, 0));
1434 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2));
1435 :
1436 3924 : k = mbedtls_mpi_bitlen(&Y) % biL;
1437 3924 : if (k < biL - 1) {
1438 3924 : k = biL - 1 - k;
1439 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k));
1440 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k));
1441 : } else {
1442 0 : k = 0;
1443 : }
1444 :
1445 3924 : n = X.n - 1;
1446 3924 : t = Y.n - 1;
1447 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t)));
1448 :
1449 4378 : while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) {
1450 454 : Z.p[n - t]++;
1451 454 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y));
1452 : }
1453 3924 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t)));
1454 :
1455 45686 : for (i = n; i > t; i--) {
1456 41762 : if (X.p[i] >= Y.p[t]) {
1457 0 : Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u;
1458 : } else {
1459 41762 : Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1],
1460 41762 : Y.p[t], NULL);
1461 : }
1462 :
1463 41762 : T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1464 41762 : T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1465 41762 : T2.p[2] = X.p[i];
1466 :
1467 41762 : Z.p[i - t - 1]++;
1468 : do {
1469 72153 : Z.p[i - t - 1]--;
1470 :
1471 72153 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0));
1472 72153 : T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1473 72153 : T1.p[1] = Y.p[t];
1474 72153 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1]));
1475 72153 : } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0);
1476 :
1477 41762 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1]));
1478 41762 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1479 41762 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1));
1480 :
1481 41762 : if (mbedtls_mpi_cmp_int(&X, 0) < 0) {
1482 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &Y));
1483 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1484 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1));
1485 0 : Z.p[i - t - 1]--;
1486 : }
1487 : }
1488 :
1489 3924 : if (Q != NULL) {
1490 2 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z));
1491 2 : Q->s = A->s * B->s;
1492 : }
1493 :
1494 3924 : if (R != NULL) {
1495 3922 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k));
1496 3922 : X.s = A->s;
1497 3922 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X));
1498 :
1499 3922 : if (mbedtls_mpi_cmp_int(R, 0) == 0) {
1500 0 : R->s = 1;
1501 : }
1502 : }
1503 :
1504 3924 : cleanup:
1505 :
1506 3924 : mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
1507 3924 : mbedtls_mpi_free(&T1);
1508 3924 : mbedtls_platform_zeroize(TP2, sizeof(TP2));
1509 :
1510 3924 : return ret;
1511 : }
1512 :
1513 : /*
1514 : * Division by int: A = Q * b + R
1515 : */
1516 0 : int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R,
1517 : const mbedtls_mpi *A,
1518 : mbedtls_mpi_sint b)
1519 : {
1520 : mbedtls_mpi B;
1521 : mbedtls_mpi_uint p[1];
1522 :
1523 0 : p[0] = mpi_sint_abs(b);
1524 0 : B.s = TO_SIGN(b);
1525 0 : B.n = 1;
1526 0 : B.p = p;
1527 :
1528 0 : return mbedtls_mpi_div_mpi(Q, R, A, &B);
1529 : }
1530 :
1531 : /*
1532 : * Modulo: R = A mod B
1533 : */
1534 15096 : int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
1535 : {
1536 15096 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1537 :
1538 15096 : if (mbedtls_mpi_cmp_int(B, 0) < 0) {
1539 0 : return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1540 : }
1541 :
1542 15096 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B));
1543 :
1544 15118 : while (mbedtls_mpi_cmp_int(R, 0) < 0) {
1545 22 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B));
1546 : }
1547 :
1548 15096 : while (mbedtls_mpi_cmp_mpi(R, B) >= 0) {
1549 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B));
1550 : }
1551 :
1552 15096 : cleanup:
1553 :
1554 15096 : return ret;
1555 : }
1556 :
1557 : /*
1558 : * Modulo: r = A mod b
1559 : */
1560 0 : int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b)
1561 : {
1562 : size_t i;
1563 : mbedtls_mpi_uint x, y, z;
1564 :
1565 0 : if (b == 0) {
1566 0 : return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1567 : }
1568 :
1569 0 : if (b < 0) {
1570 0 : return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1571 : }
1572 :
1573 : /*
1574 : * handle trivial cases
1575 : */
1576 0 : if (b == 1 || A->n == 0) {
1577 0 : *r = 0;
1578 0 : return 0;
1579 : }
1580 :
1581 0 : if (b == 2) {
1582 0 : *r = A->p[0] & 1;
1583 0 : return 0;
1584 : }
1585 :
1586 : /*
1587 : * general case
1588 : */
1589 0 : for (i = A->n, y = 0; i > 0; i--) {
1590 0 : x = A->p[i - 1];
1591 0 : y = (y << biH) | (x >> biH);
1592 0 : z = y / b;
1593 0 : y -= z * b;
1594 :
1595 0 : x <<= biH;
1596 0 : y = (y << biH) | (x >> biH);
1597 0 : z = y / b;
1598 0 : y -= z * b;
1599 : }
1600 :
1601 : /*
1602 : * If A is negative, then the current y represents a negative value.
1603 : * Flipping it to the positive side.
1604 : */
1605 0 : if (A->s < 0 && y != 0) {
1606 0 : y = b - y;
1607 : }
1608 :
1609 0 : *r = y;
1610 :
1611 0 : return 0;
1612 : }
1613 :
1614 : /*
1615 : * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value,
1616 : * this function is not constant time with respect to the exponent (parameter E).
1617 : */
1618 504 : static int mbedtls_mpi_exp_mod_optionally_safe(mbedtls_mpi *X, const mbedtls_mpi *A,
1619 : const mbedtls_mpi *E, int E_public,
1620 : const mbedtls_mpi *N, mbedtls_mpi *prec_RR)
1621 : {
1622 504 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1623 :
1624 504 : if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
1625 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1626 : }
1627 :
1628 504 : if (mbedtls_mpi_cmp_int(E, 0) < 0) {
1629 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1630 : }
1631 :
1632 1008 : if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS ||
1633 504 : mbedtls_mpi_bitlen(N) > MBEDTLS_MPI_MAX_BITS) {
1634 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1635 : }
1636 :
1637 : /*
1638 : * Ensure that the exponent that we are passing to the core is not NULL.
1639 : */
1640 504 : if (E->n == 0) {
1641 0 : ret = mbedtls_mpi_lset(X, 1);
1642 0 : return ret;
1643 : }
1644 :
1645 : /*
1646 : * Allocate working memory for mbedtls_mpi_core_exp_mod()
1647 : */
1648 504 : size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n);
1649 504 : mbedtls_mpi_uint *T = (mbedtls_mpi_uint *) mbedtls_calloc(T_limbs, sizeof(mbedtls_mpi_uint));
1650 504 : if (T == NULL) {
1651 0 : return MBEDTLS_ERR_MPI_ALLOC_FAILED;
1652 : }
1653 :
1654 : mbedtls_mpi RR;
1655 504 : mbedtls_mpi_init(&RR);
1656 :
1657 : /*
1658 : * If 1st call, pre-compute R^2 mod N
1659 : */
1660 504 : if (prec_RR == NULL || prec_RR->p == NULL) {
1661 415 : MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N));
1662 :
1663 415 : if (prec_RR != NULL) {
1664 415 : *prec_RR = RR;
1665 : }
1666 : } else {
1667 89 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n));
1668 89 : RR = *prec_RR;
1669 : }
1670 :
1671 : /*
1672 : * To preserve constness we need to make a copy of A. Using X for this to
1673 : * save memory.
1674 : */
1675 504 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1676 :
1677 : /*
1678 : * Compensate for negative A (and correct at the end).
1679 : */
1680 504 : X->s = 1;
1681 :
1682 : /*
1683 : * Make sure that X is in a form that is safe for consumption by
1684 : * the core functions.
1685 : *
1686 : * - The core functions will not touch the limbs of X above N->n. The
1687 : * result will be correct if those limbs are 0, which the mod call
1688 : * ensures.
1689 : * - Also, X must have at least as many limbs as N for the calls to the
1690 : * core functions.
1691 : */
1692 504 : if (mbedtls_mpi_cmp_mpi(X, N) >= 0) {
1693 76 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
1694 : }
1695 504 : MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n));
1696 :
1697 : /*
1698 : * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod().
1699 : */
1700 : {
1701 504 : mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p);
1702 504 : mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T);
1703 504 : if (E_public == MBEDTLS_MPI_IS_PUBLIC) {
1704 346 : mbedtls_mpi_core_exp_mod_unsafe(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1705 : } else {
1706 158 : mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1707 : }
1708 504 : mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T);
1709 : }
1710 :
1711 : /*
1712 : * Correct for negative A.
1713 : */
1714 504 : if (A->s == -1 && (E->p[0] & 1) != 0) {
1715 0 : mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n);
1716 0 : X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1);
1717 :
1718 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X));
1719 : }
1720 :
1721 504 : cleanup:
1722 :
1723 504 : mbedtls_mpi_zeroize_and_free(T, T_limbs);
1724 :
1725 504 : if (prec_RR == NULL || prec_RR->p == NULL) {
1726 0 : mbedtls_mpi_free(&RR);
1727 : }
1728 :
1729 504 : return ret;
1730 : }
1731 :
1732 158 : int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A,
1733 : const mbedtls_mpi *E, const mbedtls_mpi *N,
1734 : mbedtls_mpi *prec_RR)
1735 : {
1736 158 : return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR);
1737 : }
1738 :
1739 346 : int mbedtls_mpi_exp_mod_unsafe(mbedtls_mpi *X, const mbedtls_mpi *A,
1740 : const mbedtls_mpi *E, const mbedtls_mpi *N,
1741 : mbedtls_mpi *prec_RR)
1742 : {
1743 346 : return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_PUBLIC, N, prec_RR);
1744 : }
1745 :
1746 : /*
1747 : * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1748 : */
1749 9557 : int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
1750 : {
1751 9557 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1752 : size_t lz, lzt;
1753 : mbedtls_mpi TA, TB;
1754 :
1755 9557 : mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB);
1756 :
1757 9557 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A));
1758 9557 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B));
1759 :
1760 9557 : lz = mbedtls_mpi_lsb(&TA);
1761 9557 : lzt = mbedtls_mpi_lsb(&TB);
1762 :
1763 : /* The loop below gives the correct result when A==0 but not when B==0.
1764 : * So have a special case for B==0. Leverage the fact that we just
1765 : * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
1766 : * slightly more efficient than cmp_int(). */
1767 9557 : if (lzt == 0 && mbedtls_mpi_get_bit(&TB, 0) == 0) {
1768 0 : ret = mbedtls_mpi_copy(G, A);
1769 0 : goto cleanup;
1770 : }
1771 :
1772 9557 : if (lzt < lz) {
1773 5423 : lz = lzt;
1774 : }
1775 :
1776 9557 : TA.s = TB.s = 1;
1777 :
1778 : /* We mostly follow the procedure described in HAC 14.54, but with some
1779 : * minor differences:
1780 : * - Sequences of multiplications or divisions by 2 are grouped into a
1781 : * single shift operation.
1782 : * - The procedure in HAC assumes that 0 < TB <= TA.
1783 : * - The condition TB <= TA is not actually necessary for correctness.
1784 : * TA and TB have symmetric roles except for the loop termination
1785 : * condition, and the shifts at the beginning of the loop body
1786 : * remove any significance from the ordering of TA vs TB before
1787 : * the shifts.
1788 : * - If TA = 0, the loop goes through 0 iterations and the result is
1789 : * correctly TB.
1790 : * - The case TB = 0 was short-circuited above.
1791 : *
1792 : * For the correctness proof below, decompose the original values of
1793 : * A and B as
1794 : * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
1795 : * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
1796 : * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
1797 : * and gcd(A',B') is odd or 0.
1798 : *
1799 : * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
1800 : * The code maintains the following invariant:
1801 : * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
1802 : */
1803 :
1804 : /* Proof that the loop terminates:
1805 : * At each iteration, either the right-shift by 1 is made on a nonzero
1806 : * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
1807 : * by at least 1, or the right-shift by 1 is made on zero and then
1808 : * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
1809 : * since in that case TB is calculated from TB-TA with the condition TB>TA).
1810 : */
1811 1789376 : while (mbedtls_mpi_cmp_int(&TA, 0) != 0) {
1812 : /* Divisions by 2 preserve the invariant (I). */
1813 1779819 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, mbedtls_mpi_lsb(&TA)));
1814 1779819 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, mbedtls_mpi_lsb(&TB)));
1815 :
1816 : /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
1817 : * TA-TB is even so the division by 2 has an integer result.
1818 : * Invariant (I) is preserved since any odd divisor of both TA and TB
1819 : * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
1820 : * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
1821 : * divides TA.
1822 : */
1823 1779819 : if (mbedtls_mpi_cmp_mpi(&TA, &TB) >= 0) {
1824 907049 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TA, &TA, &TB));
1825 907049 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, 1));
1826 : } else {
1827 872770 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TB, &TB, &TA));
1828 872770 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, 1));
1829 : }
1830 : /* Note that one of TA or TB is still odd. */
1831 : }
1832 :
1833 : /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
1834 : * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
1835 : * - If there was at least one loop iteration, then one of TA or TB is odd,
1836 : * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
1837 : * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
1838 : * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
1839 : * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
1840 : */
1841 :
1842 9557 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&TB, lz));
1843 9557 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB));
1844 :
1845 9557 : cleanup:
1846 :
1847 9557 : mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB);
1848 :
1849 9557 : return ret;
1850 : }
1851 :
1852 : /*
1853 : * Fill X with size bytes of random.
1854 : * The bytes returned from the RNG are used in a specific order which
1855 : * is suitable for deterministic ECDSA (see the specification of
1856 : * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()).
1857 : */
1858 152 : int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size,
1859 : int (*f_rng)(void *, unsigned char *, size_t),
1860 : void *p_rng)
1861 : {
1862 152 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1863 152 : const size_t limbs = CHARS_TO_LIMBS(size);
1864 :
1865 : /* Ensure that target MPI has exactly the necessary number of limbs */
1866 152 : MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
1867 152 : if (size == 0) {
1868 0 : return 0;
1869 : }
1870 :
1871 152 : ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng);
1872 :
1873 152 : cleanup:
1874 152 : return ret;
1875 : }
1876 :
1877 1244 : int mbedtls_mpi_random(mbedtls_mpi *X,
1878 : mbedtls_mpi_sint min,
1879 : const mbedtls_mpi *N,
1880 : int (*f_rng)(void *, unsigned char *, size_t),
1881 : void *p_rng)
1882 : {
1883 1244 : if (min < 0) {
1884 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1885 : }
1886 1244 : if (mbedtls_mpi_cmp_int(N, min) <= 0) {
1887 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1888 : }
1889 :
1890 : /* Ensure that target MPI has exactly the same number of limbs
1891 : * as the upper bound, even if the upper bound has leading zeros.
1892 : * This is necessary for mbedtls_mpi_core_random. */
1893 1244 : int ret = mbedtls_mpi_resize_clear(X, N->n);
1894 1244 : if (ret != 0) {
1895 0 : return ret;
1896 : }
1897 :
1898 1244 : return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng);
1899 : }
1900 :
1901 : /*
1902 : * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1903 : */
1904 9553 : int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
1905 : {
1906 9553 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1907 : mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1908 :
1909 9553 : if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
1910 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1911 : }
1912 :
1913 9553 : mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TU); mbedtls_mpi_init(&U1); mbedtls_mpi_init(&U2);
1914 9553 : mbedtls_mpi_init(&G); mbedtls_mpi_init(&TB); mbedtls_mpi_init(&TV);
1915 9553 : mbedtls_mpi_init(&V1); mbedtls_mpi_init(&V2);
1916 :
1917 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N));
1918 :
1919 9553 : if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
1920 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
1921 0 : goto cleanup;
1922 : }
1923 :
1924 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&TA, A, N));
1925 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA));
1926 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, N));
1927 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TV, N));
1928 :
1929 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U1, 1));
1930 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U2, 0));
1931 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V1, 0));
1932 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V2, 1));
1933 :
1934 : do {
1935 3558880 : while ((TU.p[0] & 1) == 0) {
1936 1782542 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TU, 1));
1937 :
1938 1782542 : if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) {
1939 750779 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB));
1940 750779 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA));
1941 : }
1942 :
1943 1782542 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U1, 1));
1944 1782542 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U2, 1));
1945 : }
1946 :
1947 3529316 : while ((TV.p[0] & 1) == 0) {
1948 1752978 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TV, 1));
1949 :
1950 1752978 : if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) {
1951 799176 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB));
1952 799176 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA));
1953 : }
1954 :
1955 1752978 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V1, 1));
1956 1752978 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V2, 1));
1957 : }
1958 :
1959 1776338 : if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) {
1960 906347 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV));
1961 906347 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1));
1962 906347 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2));
1963 : } else {
1964 869991 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU));
1965 869991 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1));
1966 869991 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2));
1967 : }
1968 1776338 : } while (mbedtls_mpi_cmp_int(&TU, 0) != 0);
1969 :
1970 10537 : while (mbedtls_mpi_cmp_int(&V1, 0) < 0) {
1971 984 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, N));
1972 : }
1973 :
1974 9557 : while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) {
1975 4 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, N));
1976 : }
1977 :
1978 9553 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1));
1979 :
1980 9553 : cleanup:
1981 :
1982 9553 : mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TU); mbedtls_mpi_free(&U1); mbedtls_mpi_free(&U2);
1983 9553 : mbedtls_mpi_free(&G); mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TV);
1984 9553 : mbedtls_mpi_free(&V1); mbedtls_mpi_free(&V2);
1985 :
1986 9553 : return ret;
1987 : }
1988 :
1989 : #if defined(MBEDTLS_GENPRIME)
1990 :
1991 : /* Gaps between primes, starting at 3. https://oeis.org/A001223 */
1992 : static const unsigned char small_prime_gaps[] = {
1993 : 2, 2, 4, 2, 4, 2, 4, 6,
1994 : 2, 6, 4, 2, 4, 6, 6, 2,
1995 : 6, 4, 2, 6, 4, 6, 8, 4,
1996 : 2, 4, 2, 4, 14, 4, 6, 2,
1997 : 10, 2, 6, 6, 4, 6, 6, 2,
1998 : 10, 2, 4, 2, 12, 12, 4, 2,
1999 : 4, 6, 2, 10, 6, 6, 6, 2,
2000 : 6, 4, 2, 10, 14, 4, 2, 4,
2001 : 14, 6, 10, 2, 4, 6, 8, 6,
2002 : 6, 4, 6, 8, 4, 8, 10, 2,
2003 : 10, 2, 6, 4, 6, 8, 4, 2,
2004 : 4, 12, 8, 4, 8, 4, 6, 12,
2005 : 2, 18, 6, 10, 6, 6, 2, 6,
2006 : 10, 6, 6, 2, 6, 6, 4, 2,
2007 : 12, 10, 2, 4, 6, 6, 2, 12,
2008 : 4, 6, 8, 10, 8, 10, 8, 6,
2009 : 6, 4, 8, 6, 4, 8, 4, 14,
2010 : 10, 12, 2, 10, 2, 4, 2, 10,
2011 : 14, 4, 2, 4, 14, 4, 2, 4,
2012 : 20, 4, 8, 10, 8, 4, 6, 6,
2013 : 14, 4, 6, 6, 8, 6, /*reaches 997*/
2014 : 0 /* the last entry is effectively unused */
2015 : };
2016 :
2017 : /*
2018 : * Small divisors test (X must be positive)
2019 : *
2020 : * Return values:
2021 : * 0: no small factor (possible prime, more tests needed)
2022 : * 1: certain prime
2023 : * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2024 : * other negative: error
2025 : */
2026 0 : static int mpi_check_small_factors(const mbedtls_mpi *X)
2027 : {
2028 0 : int ret = 0;
2029 : size_t i;
2030 : mbedtls_mpi_uint r;
2031 0 : unsigned p = 3; /* The first odd prime */
2032 :
2033 0 : if ((X->p[0] & 1) == 0) {
2034 0 : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2035 : }
2036 :
2037 0 : for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) {
2038 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p));
2039 0 : if (r == 0) {
2040 0 : if (mbedtls_mpi_cmp_int(X, p) == 0) {
2041 0 : return 1;
2042 : } else {
2043 0 : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2044 : }
2045 : }
2046 : }
2047 :
2048 0 : cleanup:
2049 0 : return ret;
2050 : }
2051 :
2052 : /*
2053 : * Miller-Rabin pseudo-primality test (HAC 4.24)
2054 : */
2055 0 : static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds,
2056 : int (*f_rng)(void *, unsigned char *, size_t),
2057 : void *p_rng)
2058 : {
2059 : int ret, count;
2060 : size_t i, j, k, s;
2061 : mbedtls_mpi W, R, T, A, RR;
2062 :
2063 0 : mbedtls_mpi_init(&W); mbedtls_mpi_init(&R);
2064 0 : mbedtls_mpi_init(&T); mbedtls_mpi_init(&A);
2065 0 : mbedtls_mpi_init(&RR);
2066 :
2067 : /*
2068 : * W = |X| - 1
2069 : * R = W >> lsb( W )
2070 : */
2071 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1));
2072 0 : s = mbedtls_mpi_lsb(&W);
2073 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W));
2074 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s));
2075 :
2076 0 : for (i = 0; i < rounds; i++) {
2077 : /*
2078 : * pick a random A, 1 < A < |X| - 1
2079 : */
2080 0 : count = 0;
2081 : do {
2082 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng));
2083 :
2084 0 : j = mbedtls_mpi_bitlen(&A);
2085 0 : k = mbedtls_mpi_bitlen(&W);
2086 0 : if (j > k) {
2087 0 : A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1;
2088 : }
2089 :
2090 0 : if (count++ > 30) {
2091 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2092 0 : goto cleanup;
2093 : }
2094 :
2095 0 : } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 ||
2096 0 : mbedtls_mpi_cmp_int(&A, 1) <= 0);
2097 :
2098 : /*
2099 : * A = A^R mod |X|
2100 : */
2101 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR));
2102 :
2103 0 : if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 ||
2104 0 : mbedtls_mpi_cmp_int(&A, 1) == 0) {
2105 0 : continue;
2106 : }
2107 :
2108 0 : j = 1;
2109 0 : while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) {
2110 : /*
2111 : * A = A * A mod |X|
2112 : */
2113 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A));
2114 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X));
2115 :
2116 0 : if (mbedtls_mpi_cmp_int(&A, 1) == 0) {
2117 0 : break;
2118 : }
2119 :
2120 0 : j++;
2121 : }
2122 :
2123 : /*
2124 : * not prime if A != |X| - 1 or A == 1
2125 : */
2126 0 : if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 ||
2127 0 : mbedtls_mpi_cmp_int(&A, 1) == 0) {
2128 0 : ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2129 0 : break;
2130 : }
2131 : }
2132 :
2133 0 : cleanup:
2134 0 : mbedtls_mpi_free(&W); mbedtls_mpi_free(&R);
2135 0 : mbedtls_mpi_free(&T); mbedtls_mpi_free(&A);
2136 0 : mbedtls_mpi_free(&RR);
2137 :
2138 0 : return ret;
2139 : }
2140 :
2141 : /*
2142 : * Pseudo-primality test: small factors, then Miller-Rabin
2143 : */
2144 0 : int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds,
2145 : int (*f_rng)(void *, unsigned char *, size_t),
2146 : void *p_rng)
2147 : {
2148 0 : int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2149 : mbedtls_mpi XX;
2150 :
2151 0 : XX.s = 1;
2152 0 : XX.n = X->n;
2153 0 : XX.p = X->p;
2154 :
2155 0 : if (mbedtls_mpi_cmp_int(&XX, 0) == 0 ||
2156 0 : mbedtls_mpi_cmp_int(&XX, 1) == 0) {
2157 0 : return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2158 : }
2159 :
2160 0 : if (mbedtls_mpi_cmp_int(&XX, 2) == 0) {
2161 0 : return 0;
2162 : }
2163 :
2164 0 : if ((ret = mpi_check_small_factors(&XX)) != 0) {
2165 0 : if (ret == 1) {
2166 0 : return 0;
2167 : }
2168 :
2169 0 : return ret;
2170 : }
2171 :
2172 0 : return mpi_miller_rabin(&XX, rounds, f_rng, p_rng);
2173 : }
2174 :
2175 : /*
2176 : * Prime number generation
2177 : *
2178 : * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2179 : * be either 1024 bits or 1536 bits long, and flags must contain
2180 : * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
2181 : */
2182 0 : int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags,
2183 : int (*f_rng)(void *, unsigned char *, size_t),
2184 : void *p_rng)
2185 : {
2186 : #ifdef MBEDTLS_HAVE_INT64
2187 : // ceil(2^63.5)
2188 : #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2189 : #else
2190 : // ceil(2^31.5)
2191 : #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2192 : #endif
2193 0 : int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2194 : size_t k, n;
2195 : int rounds;
2196 : mbedtls_mpi_uint r;
2197 : mbedtls_mpi Y;
2198 :
2199 0 : if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) {
2200 0 : return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2201 : }
2202 :
2203 0 : mbedtls_mpi_init(&Y);
2204 :
2205 0 : n = BITS_TO_LIMBS(nbits);
2206 :
2207 0 : if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR) == 0) {
2208 : /*
2209 : * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2210 : */
2211 0 : rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 :
2212 0 : (nbits >= 650) ? 4 : (nbits >= 350) ? 8 :
2213 0 : (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27);
2214 : } else {
2215 : /*
2216 : * 2^-100 error probability, number of rounds computed based on HAC,
2217 : * fact 4.48
2218 : */
2219 0 : rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 :
2220 0 : (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 :
2221 0 : (nbits >= 750) ? 8 : (nbits >= 500) ? 13 :
2222 0 : (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51);
2223 : }
2224 :
2225 : while (1) {
2226 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng));
2227 : /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2228 0 : if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) {
2229 0 : continue;
2230 : }
2231 :
2232 0 : k = n * biL;
2233 0 : if (k > nbits) {
2234 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits));
2235 : }
2236 0 : X->p[0] |= 1;
2237 :
2238 0 : if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) {
2239 0 : ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng);
2240 :
2241 0 : if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2242 0 : goto cleanup;
2243 : }
2244 : } else {
2245 : /*
2246 : * A necessary condition for Y and X = 2Y + 1 to be prime
2247 : * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2248 : * Make sure it is satisfied, while keeping X = 3 mod 4
2249 : */
2250 :
2251 0 : X->p[0] |= 2;
2252 :
2253 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3));
2254 0 : if (r == 0) {
2255 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8));
2256 0 : } else if (r == 1) {
2257 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4));
2258 : }
2259 :
2260 : /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2261 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X));
2262 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, 1));
2263 :
2264 : while (1) {
2265 : /*
2266 : * First, check small factors for X and Y
2267 : * before doing Miller-Rabin on any of them
2268 : */
2269 0 : if ((ret = mpi_check_small_factors(X)) == 0 &&
2270 0 : (ret = mpi_check_small_factors(&Y)) == 0 &&
2271 0 : (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng))
2272 0 : == 0 &&
2273 0 : (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng))
2274 : == 0) {
2275 0 : goto cleanup;
2276 : }
2277 :
2278 0 : if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
2279 0 : goto cleanup;
2280 : }
2281 :
2282 : /*
2283 : * Next candidates. We want to preserve Y = (X-1) / 2 and
2284 : * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2285 : * so up Y by 6 and X by 12.
2286 : */
2287 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12));
2288 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6));
2289 : }
2290 : }
2291 : }
2292 :
2293 0 : cleanup:
2294 :
2295 0 : mbedtls_mpi_free(&Y);
2296 :
2297 0 : return ret;
2298 : }
2299 :
2300 : #endif /* MBEDTLS_GENPRIME */
2301 :
2302 : #if defined(MBEDTLS_SELF_TEST)
2303 :
2304 : #define GCD_PAIR_COUNT 3
2305 :
2306 : static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2307 : {
2308 : { 693, 609, 21 },
2309 : { 1764, 868, 28 },
2310 : { 768454923, 542167814, 1 }
2311 : };
2312 :
2313 : /*
2314 : * Checkup routine
2315 : */
2316 0 : int mbedtls_mpi_self_test(int verbose)
2317 : {
2318 : int ret, i;
2319 : mbedtls_mpi A, E, N, X, Y, U, V;
2320 :
2321 0 : mbedtls_mpi_init(&A); mbedtls_mpi_init(&E); mbedtls_mpi_init(&N); mbedtls_mpi_init(&X);
2322 0 : mbedtls_mpi_init(&Y); mbedtls_mpi_init(&U); mbedtls_mpi_init(&V);
2323 :
2324 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16,
2325 : "EFE021C2645FD1DC586E69184AF4A31E" \
2326 : "D5F53E93B5F123FA41680867BA110131" \
2327 : "944FE7952E2517337780CB0DB80E61AA" \
2328 : "E7C8DDC6C5C6AADEB34EB38A2F40D5E6"));
2329 :
2330 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16,
2331 : "B2E7EFD37075B9F03FF989C7C5051C20" \
2332 : "34D2A323810251127E7BF8625A4F49A5" \
2333 : "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2334 : "5B5C25763222FEFCCFC38B832366C29E"));
2335 :
2336 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16,
2337 : "0066A198186C18C10B2F5ED9B522752A" \
2338 : "9830B69916E535C8F047518A889A43A5" \
2339 : "94B6BED27A168D31D4A52F88925AA8F5"));
2340 :
2341 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N));
2342 :
2343 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2344 : "602AB7ECA597A3D6B56FF9829A5E8B85" \
2345 : "9E857EA95A03512E2BAE7391688D264A" \
2346 : "A5663B0341DB9CCFD2C4C5F421FEC814" \
2347 : "8001B72E848A38CAE1C65F78E56ABDEF" \
2348 : "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2349 : "ECF677152EF804370C1A305CAF3B5BF1" \
2350 : "30879B56C61DE584A0F53A2447A51E"));
2351 :
2352 0 : if (verbose != 0) {
2353 0 : mbedtls_printf(" MPI test #1 (mul_mpi): ");
2354 : }
2355 :
2356 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2357 0 : if (verbose != 0) {
2358 0 : mbedtls_printf("failed\n");
2359 : }
2360 :
2361 0 : ret = 1;
2362 0 : goto cleanup;
2363 : }
2364 :
2365 0 : if (verbose != 0) {
2366 0 : mbedtls_printf("passed\n");
2367 : }
2368 :
2369 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N));
2370 :
2371 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2372 : "256567336059E52CAE22925474705F39A94"));
2373 :
2374 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16,
2375 : "6613F26162223DF488E9CD48CC132C7A" \
2376 : "0AC93C701B001B092E4E5B9F73BCD27B" \
2377 : "9EE50D0657C77F374E903CDFA4C642"));
2378 :
2379 0 : if (verbose != 0) {
2380 0 : mbedtls_printf(" MPI test #2 (div_mpi): ");
2381 : }
2382 :
2383 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 ||
2384 0 : mbedtls_mpi_cmp_mpi(&Y, &V) != 0) {
2385 0 : if (verbose != 0) {
2386 0 : mbedtls_printf("failed\n");
2387 : }
2388 :
2389 0 : ret = 1;
2390 0 : goto cleanup;
2391 : }
2392 :
2393 0 : if (verbose != 0) {
2394 0 : mbedtls_printf("passed\n");
2395 : }
2396 :
2397 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL));
2398 :
2399 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2400 : "36E139AEA55215609D2816998ED020BB" \
2401 : "BD96C37890F65171D948E9BC7CBAA4D9" \
2402 : "325D24D6A3C12710F10A09FA08AB87"));
2403 :
2404 0 : if (verbose != 0) {
2405 0 : mbedtls_printf(" MPI test #3 (exp_mod): ");
2406 : }
2407 :
2408 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2409 0 : if (verbose != 0) {
2410 0 : mbedtls_printf("failed\n");
2411 : }
2412 :
2413 0 : ret = 1;
2414 0 : goto cleanup;
2415 : }
2416 :
2417 0 : if (verbose != 0) {
2418 0 : mbedtls_printf("passed\n");
2419 : }
2420 :
2421 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N));
2422 :
2423 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2424 : "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2425 : "C3DBA76456363A10869622EAC2DD84EC" \
2426 : "C5B8A74DAC4D09E03B5E0BE779F2DF61"));
2427 :
2428 0 : if (verbose != 0) {
2429 0 : mbedtls_printf(" MPI test #4 (inv_mod): ");
2430 : }
2431 :
2432 0 : if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2433 0 : if (verbose != 0) {
2434 0 : mbedtls_printf("failed\n");
2435 : }
2436 :
2437 0 : ret = 1;
2438 0 : goto cleanup;
2439 : }
2440 :
2441 0 : if (verbose != 0) {
2442 0 : mbedtls_printf("passed\n");
2443 : }
2444 :
2445 0 : if (verbose != 0) {
2446 0 : mbedtls_printf(" MPI test #5 (simple gcd): ");
2447 : }
2448 :
2449 0 : for (i = 0; i < GCD_PAIR_COUNT; i++) {
2450 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0]));
2451 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1]));
2452 :
2453 0 : MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y));
2454 :
2455 0 : if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) {
2456 0 : if (verbose != 0) {
2457 0 : mbedtls_printf("failed at %d\n", i);
2458 : }
2459 :
2460 0 : ret = 1;
2461 0 : goto cleanup;
2462 : }
2463 : }
2464 :
2465 0 : if (verbose != 0) {
2466 0 : mbedtls_printf("passed\n");
2467 : }
2468 :
2469 0 : cleanup:
2470 :
2471 0 : if (ret != 0 && verbose != 0) {
2472 0 : mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
2473 : }
2474 :
2475 0 : mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X);
2476 0 : mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V);
2477 :
2478 0 : if (verbose != 0) {
2479 0 : mbedtls_printf("\n");
2480 : }
2481 :
2482 0 : return ret;
2483 : }
2484 :
2485 : #endif /* MBEDTLS_SELF_TEST */
2486 :
2487 : #endif /* MBEDTLS_BIGNUM_C */
|
