Coverage Report

Created: 2024-11-21 06:47

/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
0
{
51
0
    return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1;
52
0
}
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
0
{
61
0
    mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result;
62
63
0
    if (X->n != Y->n) {
64
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
65
0
    }
66
67
    /*
68
     * Set N_is_negative to MBEDTLS_CT_FALSE if N >= 0, MBEDTLS_CT_TRUE if N < 0.
69
     * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
70
     */
71
0
    X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1);
72
0
    Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1);
73
74
    /*
75
     * If the signs are different, then the positive operand is the bigger.
76
     * That is if X is negative (X_is_negative == 1), then X < Y is true and it
77
     * is false if X is positive (X_is_negative == 0).
78
     */
79
0
    different_sign = mbedtls_ct_bool_ne(X_is_negative, Y_is_negative); // true if different sign
80
0
    result = mbedtls_ct_bool_and(different_sign, X_is_negative);
81
82
    /*
83
     * Assuming signs are the same, compare X and Y. We switch the comparison
84
     * order if they are negative so that we get the right result, regardles of
85
     * sign.
86
     */
87
88
    /* This array is used to conditionally swap the pointers in const time */
89
0
    void * const p[2] = { X->p, Y->p };
90
0
    size_t i = mbedtls_ct_size_if_else_0(X_is_negative, 1);
91
0
    mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n);
92
93
    /*
94
     * Store in result iff the signs are the same (i.e., iff different_sign == false). If
95
     * the signs differ, result has already been set, so we don't change it.
96
     */
97
0
    result = mbedtls_ct_bool_or(result,
98
0
                                mbedtls_ct_bool_and(mbedtls_ct_bool_not(different_sign), lt));
99
100
0
    *ret = mbedtls_ct_uint_if_else_0(result, 1);
101
102
0
    return 0;
103
0
}
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
0
{
122
0
    int ret = 0;
123
124
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
125
126
0
    {
127
0
        mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign);
128
129
0
        X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s);
130
131
0
        mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign);
132
133
0
        mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign);
134
0
        for (size_t i = Y->n; i < X->n; i++) {
135
0
            X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]);
136
0
        }
137
0
    }
138
139
0
cleanup:
140
0
    return ret;
141
0
}
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
0
{
153
0
    int ret = 0;
154
0
    int s;
155
156
0
    if (X == Y) {
157
0
        return 0;
158
0
    }
159
160
0
    mbedtls_ct_condition_t do_swap = mbedtls_ct_bool(swap);
161
162
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
163
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n));
164
165
0
    s = X->s;
166
0
    X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s);
167
0
    Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s);
168
169
0
    mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap);
170
171
0
cleanup:
172
0
    return ret;
173
0
}
174
175
/* Implementation that should never be optimized out by the compiler */
176
119M
#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
80.7M
{
183
80.7M
    X->s = 1;
184
80.7M
    X->n = 0;
185
80.7M
    X->p = NULL;
186
80.7M
}
187
188
/*
189
 * Unallocate one MPI
190
 */
191
void mbedtls_mpi_free(mbedtls_mpi *X)
192
79.5M
{
193
79.5M
    if (X == NULL) {
194
0
        return;
195
0
    }
196
197
79.5M
    if (X->p != NULL) {
198
79.5M
        mbedtls_mpi_zeroize_and_free(X->p, X->n);
199
79.5M
    }
200
201
79.5M
    X->s = 1;
202
79.5M
    X->n = 0;
203
79.5M
    X->p = NULL;
204
79.5M
}
205
206
/*
207
 * Enlarge to the specified number of limbs
208
 */
209
int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
210
443M
{
211
443M
    mbedtls_mpi_uint *p;
212
213
443M
    if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
214
0
        return MBEDTLS_ERR_MPI_ALLOC_FAILED;
215
0
    }
216
217
443M
    if (X->n < nblimbs) {
218
119M
        if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL)) == NULL) {
219
0
            return MBEDTLS_ERR_MPI_ALLOC_FAILED;
220
0
        }
221
222
119M
        if (X->p != NULL) {
223
39.5M
            memcpy(p, X->p, X->n * ciL);
224
39.5M
            mbedtls_mpi_zeroize_and_free(X->p, X->n);
225
39.5M
        }
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
119M
        X->n = (unsigned short) nblimbs;
230
119M
        X->p = p;
231
119M
    }
232
233
443M
    return 0;
234
443M
}
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
745
{
242
745
    mbedtls_mpi_uint *p;
243
745
    size_t i;
244
245
745
    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
745
    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
5.28k
    for (i = X->n - 1; i > 0; i--) {
256
5.25k
        if (X->p[i] != 0) {
257
716
            break;
258
716
        }
259
5.25k
    }
260
745
    i++;
261
262
745
    if (i < nblimbs) {
263
37
        i = nblimbs;
264
37
    }
265
266
745
    if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL) {
267
0
        return MBEDTLS_ERR_MPI_ALLOC_FAILED;
268
0
    }
269
270
745
    if (X->p != NULL) {
271
745
        memcpy(p, X->p, i * ciL);
272
745
        mbedtls_mpi_zeroize_and_free(X->p, X->n);
273
745
    }
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
745
    X->n = (unsigned short) i;
278
745
    X->p = p;
279
280
745
    return 0;
281
745
}
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
0
{
286
0
    if (limbs == 0) {
287
0
        mbedtls_mpi_free(X);
288
0
        return 0;
289
0
    } else if (X->n == limbs) {
290
0
        memset(X->p, 0, limbs * ciL);
291
0
        X->s = 1;
292
0
        return 0;
293
0
    } else {
294
0
        mbedtls_mpi_free(X);
295
0
        return mbedtls_mpi_grow(X, limbs);
296
0
    }
297
0
}
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
233M
{
309
233M
    int ret = 0;
310
233M
    size_t i;
311
312
233M
    if (X == Y) {
313
68.3M
        return 0;
314
68.3M
    }
315
316
164M
    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
1.52G
    for (i = Y->n - 1; i > 0; i--) {
325
1.41G
        if (Y->p[i] != 0) {
326
56.6M
            break;
327
56.6M
        }
328
1.41G
    }
329
164M
    i++;
330
331
164M
    X->s = Y->s;
332
333
164M
    if (X->n < i) {
334
40.4M
        MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i));
335
124M
    } else {
336
124M
        memset(X->p + i, 0, (X->n - i) * ciL);
337
124M
    }
338
339
164M
    memcpy(X->p, Y->p, i * ciL);
340
341
164M
cleanup:
342
343
164M
    return ret;
344
164M
}
345
346
/*
347
 * Swap the contents of X and Y
348
 */
349
void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y)
350
2.16k
{
351
2.16k
    mbedtls_mpi T;
352
353
2.16k
    memcpy(&T,  X, sizeof(mbedtls_mpi));
354
2.16k
    memcpy(X,  Y, sizeof(mbedtls_mpi));
355
2.16k
    memcpy(Y, &T, sizeof(mbedtls_mpi));
356
2.16k
}
357
358
static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
359
246M
{
360
246M
    if (z >= 0) {
361
246M
        return z;
362
246M
    }
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
2.27k
    return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
368
246M
}
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
246M
#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
96.0M
{
379
96.0M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
380
381
96.0M
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1));
382
96.0M
    memset(X->p, 0, X->n * ciL);
383
384
96.0M
    X->p[0] = mpi_sint_abs(z);
385
96.0M
    X->s    = TO_SIGN(z);
386
387
96.0M
cleanup:
388
389
96.0M
    return ret;
390
96.0M
}
391
392
/*
393
 * Get a specific bit
394
 */
395
int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
396
529
{
397
529
    if (X->n * biL <= pos) {
398
0
        return 0;
399
0
    }
400
401
529
    return (X->p[pos / biL] >> (pos % biL)) & 0x01;
402
529
}
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
0
{
409
0
    int ret = 0;
410
0
    size_t off = pos / biL;
411
0
    size_t idx = pos % biL;
412
413
0
    if (val != 0 && val != 1) {
414
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
415
0
    }
416
417
0
    if (X->n * biL <= pos) {
418
0
        if (val == 0) {
419
0
            return 0;
420
0
        }
421
422
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1));
423
0
    }
424
425
0
    X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx);
426
0
    X->p[off] |= (mbedtls_mpi_uint) val << idx;
427
428
0
cleanup:
429
430
0
    return ret;
431
0
}
432
433
/*
434
 * Return the number of less significant zero-bits
435
 */
436
size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
437
459k
{
438
459k
    size_t i;
439
440
459k
#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
459k
    #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
459k
#endif
449
450
459k
#if defined(mbedtls_mpi_uint_ctz)
451
459k
    for (i = 0; i < X->n; i++) {
452
459k
        if (X->p[i] != 0) {
453
459k
            return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
454
459k
        }
455
459k
    }
456
#else
457
    size_t count = 0;
458
    for (i = 0; i < X->n; i++) {
459
        for (size_t j = 0; j < biL; j++, count++) {
460
            if (((X->p[i] >> j) & 1) != 0) {
461
                return count;
462
            }
463
        }
464
    }
465
#endif
466
467
0
    return 0;
468
459k
}
469
470
/*
471
 * Return the number of bits
472
 */
473
size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
474
148M
{
475
148M
    return mbedtls_mpi_core_bitlen(X->p, X->n);
476
148M
}
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
20.7M
{
491
20.7M
    *d = 255;
492
493
20.7M
    if (c >= 0x30 && c <= 0x39) {
494
20.7M
        *d = c - 0x30;
495
20.7M
    }
496
20.7M
    if (c >= 0x41 && c <= 0x46) {
497
0
        *d = c - 0x37;
498
0
    }
499
20.7M
    if (c >= 0x61 && c <= 0x66) {
500
0
        *d = c - 0x57;
501
0
    }
502
503
20.7M
    if (*d >= (mbedtls_mpi_uint) radix) {
504
0
        return MBEDTLS_ERR_MPI_INVALID_CHARACTER;
505
0
    }
506
507
20.7M
    return 0;
508
20.7M
}
509
510
/*
511
 * Import from an ASCII string
512
 */
513
int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
514
207k
{
515
207k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
516
207k
    size_t i, j, slen, n;
517
207k
    int sign = 1;
518
207k
    mbedtls_mpi_uint d;
519
207k
    mbedtls_mpi T;
520
521
207k
    if (radix < 2 || radix > 16) {
522
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
523
0
    }
524
525
207k
    mbedtls_mpi_init(&T);
526
527
207k
    if (s[0] == 0) {
528
0
        mbedtls_mpi_free(X);
529
0
        return 0;
530
0
    }
531
532
207k
    if (s[0] == '-') {
533
21.0k
        ++s;
534
21.0k
        sign = -1;
535
21.0k
    }
536
537
207k
    slen = strlen(s);
538
539
207k
    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
207k
    } else {
554
207k
        MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
555
556
20.9M
        for (i = 0; i < slen; i++) {
557
20.7M
            MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i]));
558
20.7M
            MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix));
559
20.7M
            MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d));
560
20.7M
        }
561
207k
    }
562
563
207k
    if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) {
564
19.9k
        X->s = -1;
565
19.9k
    }
566
567
207k
cleanup:
568
569
207k
    mbedtls_mpi_free(&T);
570
571
207k
    return ret;
572
207k
}
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
274k
{
580
274k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
581
274k
    mbedtls_mpi_uint r;
582
274k
    size_t length = 0;
583
274k
    char *p_end = *p + buflen;
584
585
19.9M
    do {
586
19.9M
        if (length >= buflen) {
587
0
            return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
588
0
        }
589
590
19.9M
        MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix));
591
19.9M
        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
19.9M
        if (r < 0xA) {
596
19.9M
            *(--p_end) = (char) ('0' + r);
597
19.9M
        } else {
598
0
            *(--p_end) = (char) ('A' + (r - 0xA));
599
0
        }
600
601
19.9M
        length++;
602
19.9M
    } while (mbedtls_mpi_cmp_int(X, 0) != 0);
603
604
274k
    memmove(*p, p_end, length);
605
274k
    *p += length;
606
607
274k
cleanup:
608
609
274k
    return ret;
610
274k
}
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
548k
{
618
548k
    int ret = 0;
619
548k
    size_t n;
620
548k
    char *p;
621
548k
    mbedtls_mpi T;
622
623
548k
    if (radix < 2 || radix > 16) {
624
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
625
0
    }
626
627
548k
    n = mbedtls_mpi_bitlen(X);   /* Number of bits necessary to present `n`. */
628
548k
    if (radix >=  4) {
629
548k
        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
548k
    }
634
548k
    if (radix >= 16) {
635
0
        n >>= 1;                 /* Number of hexadecimal digits necessary to
636
                                  * present `n`. */
637
638
0
    }
639
548k
    n += 1; /* Terminating null byte */
640
548k
    n += 1; /* Compensate for the divisions above, which round down `n`
641
             * in case it's not even. */
642
548k
    n += 1; /* Potential '-'-sign. */
643
548k
    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
548k
    if (buflen < n) {
647
274k
        *olen = n;
648
274k
        return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
649
274k
    }
650
651
274k
    p = buf;
652
274k
    mbedtls_mpi_init(&T);
653
654
274k
    if (X->s == -1) {
655
28.1k
        *p++ = '-';
656
28.1k
        buflen--;
657
28.1k
    }
658
659
274k
    if (radix == 16) {
660
0
        int c;
661
0
        size_t i, j, k;
662
663
0
        for (i = X->n, k = 0; i > 0; i--) {
664
0
            for (j = ciL; j > 0; j--) {
665
0
                c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF;
666
667
0
                if (c == 0 && k == 0 && (i + j) != 2) {
668
0
                    continue;
669
0
                }
670
671
0
                *(p++) = "0123456789ABCDEF" [c / 16];
672
0
                *(p++) = "0123456789ABCDEF" [c % 16];
673
0
                k = 1;
674
0
            }
675
0
        }
676
274k
    } else {
677
274k
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X));
678
679
274k
        if (T.s == -1) {
680
28.1k
            T.s = 1;
681
28.1k
        }
682
683
274k
        MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen));
684
274k
    }
685
686
274k
    *p++ = '\0';
687
274k
    *olen = (size_t) (p - buf);
688
689
274k
cleanup:
690
691
274k
    mbedtls_mpi_free(&T);
692
693
274k
    return ret;
694
274k
}
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
0
{
822
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
823
0
    const size_t limbs = CHARS_TO_LIMBS(buflen);
824
825
    /* Ensure that target MPI has exactly the necessary number of limbs */
826
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
827
828
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
829
830
0
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
0
    return ret;
838
0
}
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
0
{
846
0
    return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen);
847
0
}
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
0
{
855
0
    return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
856
0
}
857
858
/*
859
 * Left-shift: X <<= count
860
 */
861
int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
862
128M
{
863
128M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
864
128M
    size_t i;
865
866
128M
    i = mbedtls_mpi_bitlen(X) + count;
867
868
128M
    if (X->n * biL < i) {
869
37.8M
        MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i)));
870
37.8M
    }
871
872
128M
    ret = 0;
873
874
128M
    mbedtls_mpi_core_shift_l(X->p, X->n, count);
875
128M
cleanup:
876
877
128M
    return ret;
878
128M
}
879
880
/*
881
 * Right-shift: X >>= count
882
 */
883
int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
884
20.3M
{
885
20.3M
    if (X->n != 0) {
886
20.3M
        mbedtls_mpi_core_shift_r(X->p, X->n, count);
887
20.3M
    }
888
20.3M
    return 0;
889
20.3M
}
890
891
/*
892
 * Compare unsigned values
893
 */
894
int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
895
90.1M
{
896
90.1M
    size_t i, j;
897
898
759M
    for (i = X->n; i > 0; i--) {
899
758M
        if (X->p[i - 1] != 0) {
900
89.1M
            break;
901
89.1M
        }
902
758M
    }
903
904
1.40G
    for (j = Y->n; j > 0; j--) {
905
1.40G
        if (Y->p[j - 1] != 0) {
906
89.1M
            break;
907
89.1M
        }
908
1.40G
    }
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
90.1M
    if (i > j) {
914
15.6M
        return 1;
915
15.6M
    }
916
74.5M
    if (j > i) {
917
22.3k
        return -1;
918
22.3k
    }
919
920
147M
    for (; i > 0; i--) {
921
135M
        if (X->p[i - 1] > Y->p[i - 1]) {
922
61.8M
            return 1;
923
61.8M
        }
924
73.7M
        if (X->p[i - 1] < Y->p[i - 1]) {
925
262k
            return -1;
926
262k
        }
927
73.7M
    }
928
929
12.3M
    return 0;
930
74.5M
}
931
932
/*
933
 * Compare signed values
934
 */
935
int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
936
199M
{
937
199M
    size_t i, j;
938
939
2.78G
    for (i = X->n; i > 0; i--) {
940
2.76G
        if (X->p[i - 1] != 0) {
941
186M
            break;
942
186M
        }
943
2.76G
    }
944
945
312M
    for (j = Y->n; j > 0; j--) {
946
202M
        if (Y->p[j - 1] != 0) {
947
89.1M
            break;
948
89.1M
        }
949
202M
    }
950
951
199M
    if (i == 0 && j == 0) {
952
13.6M
        return 0;
953
13.6M
    }
954
955
186M
    if (i > j) {
956
96.9M
        return X->s;
957
96.9M
    }
958
89.0M
    if (j > i) {
959
214k
        return -Y->s;
960
214k
    }
961
962
88.8M
    if (X->s > 0 && Y->s < 0) {
963
615
        return 1;
964
615
    }
965
88.8M
    if (Y->s > 0 && X->s < 0) {
966
249
        return -1;
967
249
    }
968
969
172M
    for (; i > 0; i--) {
970
161M
        if (X->p[i - 1] > Y->p[i - 1]) {
971
888k
            return X->s;
972
888k
        }
973
160M
        if (X->p[i - 1] < Y->p[i - 1]) {
974
76.6M
            return -X->s;
975
76.6M
        }
976
160M
    }
977
978
11.3M
    return 0;
979
88.8M
}
980
981
/*
982
 * Compare signed values
983
 */
984
int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
985
109M
{
986
109M
    mbedtls_mpi Y;
987
109M
    mbedtls_mpi_uint p[1];
988
989
109M
    *p  = mpi_sint_abs(z);
990
109M
    Y.s = TO_SIGN(z);
991
109M
    Y.n = 1;
992
109M
    Y.p = p;
993
994
109M
    return mbedtls_mpi_cmp_mpi(X, &Y);
995
109M
}
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
20.7M
{
1002
20.7M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1003
20.7M
    size_t j;
1004
20.7M
    mbedtls_mpi_uint *p;
1005
20.7M
    mbedtls_mpi_uint c;
1006
1007
20.7M
    if (X == B) {
1008
0
        const mbedtls_mpi *T = A; A = X; B = T;
1009
0
    }
1010
1011
20.7M
    if (X != A) {
1012
20.7M
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1013
20.7M
    }
1014
1015
    /*
1016
     * X must always be positive as a result of unsigned additions.
1017
     */
1018
20.7M
    X->s = 1;
1019
1020
35.1M
    for (j = B->n; j > 0; j--) {
1021
20.7M
        if (B->p[j - 1] != 0) {
1022
6.34M
            break;
1023
6.34M
        }
1024
20.7M
    }
1025
1026
    /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
1027
     * and B is 0 (of any size). */
1028
20.7M
    if (j == 0) {
1029
14.4M
        return 0;
1030
14.4M
    }
1031
1032
6.34M
    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
6.34M
    p = X->p;
1037
1038
6.34M
    c = mbedtls_mpi_core_add(p, p, B->p, j);
1039
1040
6.34M
    p += j;
1041
1042
    /* Now propagate any carry */
1043
1044
6.34M
    while (c != 0) {
1045
1.27k
        if (j >= X->n) {
1046
35
            MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
1047
35
            p = X->p + j;
1048
35
        }
1049
1050
1.27k
        *p += c; c = (*p < c); j++; p++;
1051
1.27k
    }
1052
1053
6.34M
cleanup:
1054
1055
6.34M
    return ret;
1056
6.34M
}
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
70.4M
{
1063
70.4M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1064
70.4M
    size_t n;
1065
70.4M
    mbedtls_mpi_uint carry;
1066
1067
1.38G
    for (n = B->n; n > 0; n--) {
1068
1.38G
        if (B->p[n - 1] != 0) {
1069
69.3M
            break;
1070
69.3M
        }
1071
1.38G
    }
1072
70.4M
    if (n > A->n) {
1073
        /* B >= (2^ciL)^n > A */
1074
0
        ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1075
0
        goto cleanup;
1076
0
    }
1077
1078
70.4M
    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
70.4M
    if (A->n > n && A != X) {
1084
4.70k
        memcpy(X->p + n, A->p + n, (A->n - n) * ciL);
1085
4.70k
    }
1086
70.4M
    if (X->n > A->n) {
1087
4.28k
        memset(X->p + A->n, 0, (X->n - A->n) * ciL);
1088
4.28k
    }
1089
1090
70.4M
    carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
1091
70.4M
    if (carry != 0) {
1092
        /* Propagate the carry through the rest of X. */
1093
131k
        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
131k
        if (carry != 0) {
1097
0
            ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1098
0
            goto cleanup;
1099
0
        }
1100
131k
    }
1101
1102
    /* X should always be positive as a result of unsigned subtractions. */
1103
70.4M
    X->s = 1;
1104
1105
70.4M
cleanup:
1106
70.4M
    return ret;
1107
70.4M
}
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
90.9M
{
1116
90.9M
    int ret, s;
1117
1118
90.9M
    s = A->s;
1119
90.9M
    if (A->s * B->s * flip_B < 0) {
1120
70.1M
        int cmp = mbedtls_mpi_cmp_abs(A, B);
1121
70.1M
        if (cmp >= 0) {
1122
70.1M
            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
70.1M
            X->s = cmp == 0 ? 1 : s;
1127
70.1M
        } else {
1128
5.33k
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A));
1129
            /* Since |A| < |B|, the sign is the opposite of A. */
1130
5.33k
            X->s = -s;
1131
5.33k
        }
1132
70.1M
    } else {
1133
20.7M
        MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B));
1134
20.7M
        X->s = s;
1135
20.7M
    }
1136
1137
90.9M
cleanup:
1138
1139
90.9M
    return ret;
1140
90.9M
}
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
20.7M
{
1147
20.7M
    return add_sub_mpi(X, A, B, 1);
1148
20.7M
}
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
70.1M
{
1155
70.1M
    return add_sub_mpi(X, A, B, -1);
1156
70.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
20.7M
{
1163
20.7M
    mbedtls_mpi B;
1164
20.7M
    mbedtls_mpi_uint p[1];
1165
1166
20.7M
    p[0] = mpi_sint_abs(b);
1167
20.7M
    B.s = TO_SIGN(b);
1168
20.7M
    B.n = 1;
1169
20.7M
    B.p = p;
1170
1171
20.7M
    return mbedtls_mpi_add_mpi(X, A, &B);
1172
20.7M
}
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
167
{
1179
167
    mbedtls_mpi B;
1180
167
    mbedtls_mpi_uint p[1];
1181
1182
167
    p[0] = mpi_sint_abs(b);
1183
167
    B.s = TO_SIGN(b);
1184
167
    B.n = 1;
1185
167
    B.p = p;
1186
1187
167
    return mbedtls_mpi_sub_mpi(X, A, &B);
1188
167
}
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
54.0k
{
1195
54.0k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1196
54.0k
    size_t i, j;
1197
54.0k
    mbedtls_mpi TA, TB;
1198
54.0k
    int result_is_zero = 0;
1199
1200
54.0k
    mbedtls_mpi_init(&TA);
1201
54.0k
    mbedtls_mpi_init(&TB);
1202
1203
54.0k
    if (X == A) {
1204
48.2k
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
1205
48.2k
    }
1206
54.0k
    if (X == B) {
1207
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
1208
0
    }
1209
1210
54.6k
    for (i = A->n; i > 0; i--) {
1211
54.0k
        if (A->p[i - 1] != 0) {
1212
53.3k
            break;
1213
53.3k
        }
1214
54.0k
    }
1215
54.0k
    if (i == 0) {
1216
639
        result_is_zero = 1;
1217
639
    }
1218
1219
54.2k
    for (j = B->n; j > 0; j--) {
1220
54.0k
        if (B->p[j - 1] != 0) {
1221
53.7k
            break;
1222
53.7k
        }
1223
54.0k
    }
1224
54.0k
    if (j == 0) {
1225
293
        result_is_zero = 1;
1226
293
    }
1227
1228
54.0k
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
1229
54.0k
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
1230
1231
54.0k
    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
54.0k
    if (result_is_zero) {
1238
687
        X->s = 1;
1239
53.3k
    } else {
1240
53.3k
        X->s = A->s * B->s;
1241
53.3k
    }
1242
1243
54.0k
cleanup:
1244
1245
54.0k
    mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA);
1246
1247
54.0k
    return ret;
1248
54.0k
}
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
159M
{
1255
159M
    size_t n = A->n;
1256
3.32G
    while (n > 0 && A->p[n - 1] == 0) {
1257
3.16G
        --n;
1258
3.16G
    }
1259
1260
    /* The general method below doesn't work if b==0. */
1261
159M
    if (b == 0 || n == 0) {
1262
6.49M
        return mbedtls_mpi_lset(X, 0);
1263
6.49M
    }
1264
1265
    /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
1266
152M
    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
152M
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1));
1279
152M
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1280
152M
    mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
1281
1282
152M
cleanup:
1283
152M
    return ret;
1284
152M
}
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
69.3M
{
1295
69.3M
#if defined(MBEDTLS_HAVE_UDBL)
1296
69.3M
    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
69.3M
    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
69.3M
#if defined(MBEDTLS_HAVE_UDBL)
1317
69.3M
    dividend  = (mbedtls_t_udbl) u1 << biL;
1318
69.3M
    dividend |= (mbedtls_t_udbl) u0;
1319
69.3M
    quotient = dividend / d;
1320
69.3M
    if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) {
1321
0
        quotient = ((mbedtls_t_udbl) 1 << biL) - 1;
1322
0
    }
1323
1324
69.3M
    if (r != NULL) {
1325
0
        *r = (mbedtls_mpi_uint) (dividend - (quotient * d));
1326
0
    }
1327
1328
69.3M
    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
69.3M
}
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
19.9M
{
1396
19.9M
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1397
19.9M
    size_t i, n, t, k;
1398
19.9M
    mbedtls_mpi X, Y, Z, T1, T2;
1399
19.9M
    mbedtls_mpi_uint TP2[3];
1400
1401
19.9M
    if (mbedtls_mpi_cmp_int(B, 0) == 0) {
1402
116
        return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1403
116
    }
1404
1405
19.9M
    mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z);
1406
19.9M
    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
19.9M
    T2.s = 1;
1415
19.9M
    T2.n = sizeof(TP2) / sizeof(*TP2);
1416
19.9M
    T2.p = TP2;
1417
1418
19.9M
    if (mbedtls_mpi_cmp_abs(A, B) < 0) {
1419
279k
        if (Q != NULL) {
1420
275k
            MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0));
1421
275k
        }
1422
279k
        if (R != NULL) {
1423
4.88k
            MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A));
1424
4.88k
        }
1425
279k
        return 0;
1426
279k
    }
1427
1428
19.6M
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A));
1429
19.6M
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B));
1430
19.6M
    X.s = Y.s = 1;
1431
1432
19.6M
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2));
1433
19.6M
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z,  0));
1434
19.6M
    MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2));
1435
1436
19.6M
    k = mbedtls_mpi_bitlen(&Y) % biL;
1437
19.6M
    if (k < biL - 1) {
1438
19.6M
        k = biL - 1 - k;
1439
19.6M
        MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k));
1440
19.6M
        MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k));
1441
19.6M
    } else {
1442
164
        k = 0;
1443
164
    }
1444
1445
19.6M
    n = X.n - 1;
1446
19.6M
    t = Y.n - 1;
1447
19.6M
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t)));
1448
1449
20.5M
    while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) {
1450
831k
        Z.p[n - t]++;
1451
831k
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y));
1452
831k
    }
1453
19.6M
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t)));
1454
1455
89.0M
    for (i = n; i > t; i--) {
1456
69.3M
        if (X.p[i] >= Y.p[t]) {
1457
22
            Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u;
1458
69.3M
        } else {
1459
69.3M
            Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1],
1460
69.3M
                                                 Y.p[t], NULL);
1461
69.3M
        }
1462
1463
69.3M
        T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1464
69.3M
        T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
1465
69.3M
        T2.p[2] = X.p[i];
1466
1467
69.3M
        Z.p[i - t - 1]++;
1468
69.3M
        do {
1469
69.3M
            Z.p[i - t - 1]--;
1470
1471
69.3M
            MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0));
1472
69.3M
            T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
1473
69.3M
            T1.p[1] = Y.p[t];
1474
69.3M
            MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1]));
1475
69.3M
        } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0);
1476
1477
69.3M
        MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1]));
1478
69.3M
        MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1,  biL * (i - t - 1)));
1479
69.3M
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1));
1480
1481
69.3M
        if (mbedtls_mpi_cmp_int(&X, 0) < 0) {
1482
63
            MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &Y));
1483
63
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1484
63
            MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1));
1485
63
            Z.p[i - t - 1]--;
1486
63
        }
1487
69.3M
    }
1488
1489
19.6M
    if (Q != NULL) {
1490
19.6M
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z));
1491
19.6M
        Q->s = A->s * B->s;
1492
19.6M
    }
1493
1494
19.6M
    if (R != NULL) {
1495
5.30k
        MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k));
1496
5.30k
        X.s = A->s;
1497
5.30k
        MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X));
1498
1499
5.30k
        if (mbedtls_mpi_cmp_int(R, 0) == 0) {
1500
327
            R->s = 1;
1501
327
        }
1502
5.30k
    }
1503
1504
19.6M
cleanup:
1505
1506
19.6M
    mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
1507
19.6M
    mbedtls_mpi_free(&T1);
1508
19.6M
    mbedtls_platform_zeroize(TP2, sizeof(TP2));
1509
1510
19.6M
    return ret;
1511
19.6M
}
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
19.9M
{
1520
19.9M
    mbedtls_mpi B;
1521
19.9M
    mbedtls_mpi_uint p[1];
1522
1523
19.9M
    p[0] = mpi_sint_abs(b);
1524
19.9M
    B.s = TO_SIGN(b);
1525
19.9M
    B.n = 1;
1526
19.9M
    B.p = p;
1527
1528
19.9M
    return mbedtls_mpi_div_mpi(Q, R, A, &B);
1529
19.9M
}
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
8.48k
{
1536
8.48k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1537
1538
8.48k
    if (mbedtls_mpi_cmp_int(B, 0) < 0) {
1539
333
        return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1540
333
    }
1541
1542
8.14k
    MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B));
1543
1544
9.50k
    while (mbedtls_mpi_cmp_int(R, 0) < 0) {
1545
1.42k
        MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B));
1546
1.42k
    }
1547
1548
8.08k
    while (mbedtls_mpi_cmp_mpi(R, B) >= 0) {
1549
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B));
1550
0
    }
1551
1552
8.14k
cleanup:
1553
1554
8.14k
    return ret;
1555
8.08k
}
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
19.9M
{
1562
19.9M
    size_t i;
1563
19.9M
    mbedtls_mpi_uint x, y, z;
1564
1565
19.9M
    if (b == 0) {
1566
0
        return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1567
0
    }
1568
1569
19.9M
    if (b < 0) {
1570
0
        return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1571
0
    }
1572
1573
    /*
1574
     * handle trivial cases
1575
     */
1576
19.9M
    if (b == 1 || A->n == 0) {
1577
0
        *r = 0;
1578
0
        return 0;
1579
0
    }
1580
1581
19.9M
    if (b == 2) {
1582
0
        *r = A->p[0] & 1;
1583
0
        return 0;
1584
0
    }
1585
1586
    /*
1587
     * general case
1588
     */
1589
150M
    for (i = A->n, y = 0; i > 0; i--) {
1590
130M
        x  = A->p[i - 1];
1591
130M
        y  = (y << biH) | (x >> biH);
1592
130M
        z  = y / b;
1593
130M
        y -= z * b;
1594
1595
130M
        x <<= biH;
1596
130M
        y  = (y << biH) | (x >> biH);
1597
130M
        z  = y / b;
1598
130M
        y -= z * b;
1599
130M
    }
1600
1601
    /*
1602
     * If A is negative, then the current y represents a negative value.
1603
     * Flipping it to the positive side.
1604
     */
1605
19.9M
    if (A->s < 0 && y != 0) {
1606
0
        y = b - y;
1607
0
    }
1608
1609
19.9M
    *r = y;
1610
1611
19.9M
    return 0;
1612
19.9M
}
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
1.59k
{
1622
1.59k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1623
1624
1.59k
    if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
1625
736
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1626
736
    }
1627
1628
862
    if (mbedtls_mpi_cmp_int(E, 0) < 0) {
1629
117
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1630
117
    }
1631
1632
745
    if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS ||
1633
745
        mbedtls_mpi_bitlen(N) > MBEDTLS_MPI_MAX_BITS) {
1634
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1635
0
    }
1636
1637
    /*
1638
     * Ensure that the exponent that we are passing to the core is not NULL.
1639
     */
1640
745
    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
745
    size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n);
1649
745
    mbedtls_mpi_uint *T = (mbedtls_mpi_uint *) mbedtls_calloc(T_limbs, sizeof(mbedtls_mpi_uint));
1650
745
    if (T == NULL) {
1651
0
        return MBEDTLS_ERR_MPI_ALLOC_FAILED;
1652
0
    }
1653
1654
745
    mbedtls_mpi RR;
1655
745
    mbedtls_mpi_init(&RR);
1656
1657
    /*
1658
     * If 1st call, pre-compute R^2 mod N
1659
     */
1660
745
    if (prec_RR == NULL || prec_RR->p == NULL) {
1661
745
        MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N));
1662
1663
745
        if (prec_RR != NULL) {
1664
352
            *prec_RR = RR;
1665
352
        }
1666
745
    } 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
745
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1676
1677
    /*
1678
     * Compensate for negative A (and correct at the end).
1679
     */
1680
745
    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
745
    if (mbedtls_mpi_cmp_mpi(X, N) >= 0) {
1693
171
        MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
1694
171
    }
1695
745
    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
745
    {
1701
745
        mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p);
1702
745
        mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T);
1703
745
        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
745
        } else {
1706
745
            mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T);
1707
745
        }
1708
745
        mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T);
1709
745
    }
1710
1711
    /*
1712
     * Correct for negative A.
1713
     */
1714
745
    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
745
cleanup:
1722
1723
745
    mbedtls_mpi_zeroize_and_free(T, T_limbs);
1724
1725
745
    if (prec_RR == NULL || prec_RR->p == NULL) {
1726
393
        mbedtls_mpi_free(&RR);
1727
393
    }
1728
1729
745
    return ret;
1730
745
}
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
1.59k
{
1736
1.59k
    return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR);
1737
1.59k
}
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
1.41k
{
1751
1.41k
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1752
1.41k
    size_t lz, lzt;
1753
1.41k
    mbedtls_mpi TA, TB;
1754
1755
1.41k
    mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB);
1756
1757
1.41k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A));
1758
1.41k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B));
1759
1760
1.41k
    lz = mbedtls_mpi_lsb(&TA);
1761
1.41k
    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
1.41k
    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
1.41k
    if (lzt < lz) {
1773
409
        lz = lzt;
1774
409
    }
1775
1776
1.41k
    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
229k
    while (mbedtls_mpi_cmp_int(&TA, 0) != 0) {
1812
        /* Divisions by 2 preserve the invariant (I). */
1813
228k
        MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, mbedtls_mpi_lsb(&TA)));
1814
228k
        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
228k
        if (mbedtls_mpi_cmp_mpi(&TA, &TB) >= 0) {
1824
105k
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TA, &TA, &TB));
1825
105k
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, 1));
1826
122k
        } else {
1827
122k
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TB, &TB, &TA));
1828
122k
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, 1));
1829
122k
        }
1830
        /* Note that one of TA or TB is still odd. */
1831
228k
    }
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
1.41k
    MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&TB, lz));
1843
1.41k
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB));
1844
1845
1.41k
cleanup:
1846
1847
1.41k
    mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB);
1848
1849
1.41k
    return ret;
1850
1.41k
}
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
0
{
1883
0
    if (min < 0) {
1884
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1885
0
    }
1886
0
    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
0
    int ret = mbedtls_mpi_resize_clear(X, N->n);
1894
0
    if (ret != 0) {
1895
0
        return ret;
1896
0
    }
1897
1898
0
    return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng);
1899
0
}
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
0
{
1906
0
    int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1907
0
    mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
1908
1909
0
    if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
1910
0
        return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1911
0
    }
1912
1913
0
    mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TU); mbedtls_mpi_init(&U1); mbedtls_mpi_init(&U2);
1914
0
    mbedtls_mpi_init(&G); mbedtls_mpi_init(&TB); mbedtls_mpi_init(&TV);
1915
0
    mbedtls_mpi_init(&V1); mbedtls_mpi_init(&V2);
1916
1917
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N));
1918
1919
0
    if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
1920
0
        ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
1921
0
        goto cleanup;
1922
0
    }
1923
1924
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&TA, A, N));
1925
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA));
1926
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, N));
1927
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TV, N));
1928
1929
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U1, 1));
1930
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U2, 0));
1931
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V1, 0));
1932
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V2, 1));
1933
1934
0
    do {
1935
0
        while ((TU.p[0] & 1) == 0) {
1936
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TU, 1));
1937
1938
0
            if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) {
1939
0
                MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB));
1940
0
                MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA));
1941
0
            }
1942
1943
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U1, 1));
1944
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U2, 1));
1945
0
        }
1946
1947
0
        while ((TV.p[0] & 1) == 0) {
1948
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TV, 1));
1949
1950
0
            if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) {
1951
0
                MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB));
1952
0
                MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA));
1953
0
            }
1954
1955
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V1, 1));
1956
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V2, 1));
1957
0
        }
1958
1959
0
        if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) {
1960
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV));
1961
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1));
1962
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2));
1963
0
        } else {
1964
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU));
1965
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1));
1966
0
            MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2));
1967
0
        }
1968
0
    } while (mbedtls_mpi_cmp_int(&TU, 0) != 0);
1969
1970
0
    while (mbedtls_mpi_cmp_int(&V1, 0) < 0) {
1971
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, N));
1972
0
    }
1973
1974
0
    while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) {
1975
0
        MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, N));
1976
0
    }
1977
1978
0
    MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1));
1979
1980
0
cleanup:
1981
1982
0
    mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TU); mbedtls_mpi_free(&U1); mbedtls_mpi_free(&U2);
1983
0
    mbedtls_mpi_free(&G); mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TV);
1984
0
    mbedtls_mpi_free(&V1); mbedtls_mpi_free(&V2);
1985
1986
0
    return ret;
1987
0
}
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 */