Coverage Report

Created: 2024-11-21 07:03

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