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