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