Coverage Report

Created: 2024-11-21 07:03

/src/mbedtls/library/bignum_core.h
Line
Count
Source (jump to first uncovered line)
1
/**
2
 *  Core bignum functions
3
 *
4
 *  This interface should only be used by the legacy bignum module (bignum.h)
5
 *  and the modular bignum modules (bignum_mod.c, bignum_mod_raw.c). All other
6
 *  modules should use the high-level modular bignum interface (bignum_mod.h)
7
 *  or the legacy bignum interface (bignum.h).
8
 *
9
 * This module is about processing non-negative integers with a fixed upper
10
 * bound that's of the form 2^n-1 where n is a multiple of #biL.
11
 * These can be thought of integers written in base 2^#biL with a fixed
12
 * number of digits. Digits in this base are called *limbs*.
13
 * Many operations treat these numbers as the principal representation of
14
 * a number modulo 2^n or a smaller bound.
15
 *
16
 * The functions in this module obey the following conventions unless
17
 * explicitly indicated otherwise:
18
 *
19
 * - **Overflow**: some functions indicate overflow from the range
20
 *   [0, 2^n-1] by returning carry parameters, while others operate
21
 *   modulo and so cannot overflow. This should be clear from the function
22
 *   documentation.
23
 * - **Bignum parameters**: Bignums are passed as pointers to an array of
24
 *   limbs. A limb has the type #mbedtls_mpi_uint. Unless otherwise specified:
25
 *     - Bignum parameters called \p A, \p B, ... are inputs, and are
26
 *       not modified by the function.
27
 *     - For operations modulo some number, the modulus is called \p N
28
 *       and is input-only.
29
 *     - Bignum parameters called \p X, \p Y are outputs or input-output.
30
 *       The initial content of output-only parameters is ignored.
31
 *     - Some functions use different names that reflect traditional
32
 *       naming of operands of certain operations (e.g.
33
 *       divisor/dividend/quotient/remainder).
34
 *     - \p T is a temporary storage area. The initial content of such
35
 *       parameter is ignored and the final content is unspecified.
36
 * - **Bignum sizes**: bignum sizes are always expressed in limbs.
37
 *   Most functions work on bignums of a given size and take a single
38
 *   \p limbs parameter that applies to all parameters that are limb arrays.
39
 *   All bignum sizes must be at least 1 and must be significantly less than
40
 *   #SIZE_MAX. The behavior if a size is 0 is undefined. The behavior if the
41
 *   total size of all parameters overflows #SIZE_MAX is undefined.
42
 * - **Parameter ordering**: for bignum parameters, outputs come before inputs.
43
 *   Temporaries come last.
44
 * - **Aliasing**: in general, output bignums may be aliased to one or more
45
 *   inputs. As an exception, parameters that are documented as a modulus value
46
 *   may not be aliased to an output. Outputs may not be aliased to one another.
47
 *   Temporaries may not be aliased to any other parameter.
48
 * - **Overlap**: apart from aliasing of limb array pointers (where two
49
 *   arguments are equal pointers), overlap is not supported and may result
50
 *   in undefined behavior.
51
 * - **Error handling**: This is a low-level module. Functions generally do not
52
 *   try to protect against invalid arguments such as nonsensical sizes or
53
 *   null pointers. Note that some functions that operate on bignums of
54
 *   different sizes have constraints about their size, and violating those
55
 *   constraints may lead to buffer overflows.
56
 * - **Modular representatives**: functions that operate modulo \p N expect
57
 *   all modular inputs to be in the range [0, \p N - 1] and guarantee outputs
58
 *   in the range [0, \p N - 1]. If an input is out of range, outputs are
59
 *   fully unspecified, though bignum values out of range should not cause
60
 *   buffer overflows (beware that this is not extensively tested).
61
 */
62
63
/*
64
 *  Copyright The Mbed TLS Contributors
65
 *  SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
66
 */
67
68
#ifndef MBEDTLS_BIGNUM_CORE_H
69
#define MBEDTLS_BIGNUM_CORE_H
70
71
#include "common.h"
72
73
#include "mbedtls/bignum.h"
74
75
#include "constant_time_internal.h"
76
77
1.06G
#define ciL    (sizeof(mbedtls_mpi_uint))     /** chars in limb  */
78
967M
#define biL    (ciL << 3)                     /** bits  in limb  */
79
3.62M
#define biH    (ciL << 2)                     /** half limb size */
80
81
/*
82
 * Convert between bits/chars and number of limbs
83
 * Divide first in order to avoid potential overflows
84
 */
85
0
#define BITS_TO_LIMBS(i)  ((i) / biL + ((i) % biL != 0))
86
3.38k
#define CHARS_TO_LIMBS(i) ((i) / ciL + ((i) % ciL != 0))
87
/* Get a specific byte, without range checks. */
88
#define GET_BYTE(X, i)                                \
89
902k
    (((X)[(i) / ciL] >> (((i) % ciL) * 8)) & 0xff)
90
91
/* Constants to identify whether a value is public or secret. If a parameter is marked as secret by
92
 * this constant, the function must be constant time with respect to the parameter.
93
 *
94
 * This is only needed for functions with the _optionally_safe postfix. All other functions have
95
 * fixed behavior that can't be changed at runtime and are constant time with respect to their
96
 * parameters as prescribed by their documentation or by conventions in their module's documentation.
97
 *
98
 * Parameters should be named X_public where X is the name of the
99
 * corresponding input parameter.
100
 *
101
 * Implementation should always check using
102
 *  if (X_public == MBEDTLS_MPI_IS_PUBLIC) {
103
 *      // unsafe path
104
 *  } else {
105
 *      // safe path
106
 *  }
107
 * not the other way round, in order to prevent misuse. (That is, if a value
108
 * other than the two below is passed, default to the safe path.)
109
 *
110
 * The value of MBEDTLS_MPI_IS_PUBLIC is chosen in a way that is unlikely to happen by accident, but
111
 * which can be used as an immediate value in a Thumb2 comparison (for code size). */
112
415k
#define MBEDTLS_MPI_IS_PUBLIC  0x2a2a2a2a
113
6.02k
#define MBEDTLS_MPI_IS_SECRET  0
114
#if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C)
115
// Default value for testing that is neither MBEDTLS_MPI_IS_PUBLIC nor MBEDTLS_MPI_IS_SECRET
116
#define MBEDTLS_MPI_IS_TEST  1
117
#endif
118
119
/** Count leading zero bits in a given integer.
120
 *
121
 * \warning     The result is undefined if \p a == 0
122
 *
123
 * \param a     Integer to count leading zero bits.
124
 *
125
 * \return      The number of leading zero bits in \p a, if \p a != 0.
126
 *              If \p a == 0, the result is undefined.
127
 */
128
size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a);
129
130
/** Return the minimum number of bits required to represent the value held
131
 * in the MPI.
132
 *
133
 * \note This function returns 0 if all the limbs of \p A are 0.
134
 *
135
 * \param[in] A     The address of the MPI.
136
 * \param A_limbs   The number of limbs of \p A.
137
 *
138
 * \return      The number of bits in \p A.
139
 */
140
size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs);
141
142
/** Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
143
 * into the storage form used by mbedtls_mpi.
144
 *
145
 * \param[in,out] A     The address of the MPI.
146
 * \param A_limbs       The number of limbs of \p A.
147
 */
148
void mbedtls_mpi_core_bigendian_to_host(mbedtls_mpi_uint *A,
149
                                        size_t A_limbs);
150
151
/** \brief         Compare a machine integer with an MPI.
152
 *
153
 *                 This function operates in constant time with respect
154
 *                 to the values of \p min and \p A.
155
 *
156
 * \param min      A machine integer.
157
 * \param[in] A    An MPI.
158
 * \param A_limbs  The number of limbs of \p A.
159
 *                 This must be at least 1.
160
 *
161
 * \return         MBEDTLS_CT_TRUE if \p min is less than or equal to \p A, otherwise MBEDTLS_CT_FALSE.
162
 */
163
mbedtls_ct_condition_t mbedtls_mpi_core_uint_le_mpi(mbedtls_mpi_uint min,
164
                                                    const mbedtls_mpi_uint *A,
165
                                                    size_t A_limbs);
166
167
/**
168
 * \brief          Check if one unsigned MPI is less than another in constant
169
 *                 time.
170
 *
171
 * \param A        The left-hand MPI. This must point to an array of limbs
172
 *                 with the same allocated length as \p B.
173
 * \param B        The right-hand MPI. This must point to an array of limbs
174
 *                 with the same allocated length as \p A.
175
 * \param limbs    The number of limbs in \p A and \p B.
176
 *                 This must not be 0.
177
 *
178
 * \return         MBEDTLS_CT_TRUE  if \p A is less than \p B.
179
 *                 MBEDTLS_CT_FALSE if \p A is greater than or equal to \p B.
180
 */
181
mbedtls_ct_condition_t mbedtls_mpi_core_lt_ct(const mbedtls_mpi_uint *A,
182
                                              const mbedtls_mpi_uint *B,
183
                                              size_t limbs);
184
185
/**
186
 * \brief   Perform a safe conditional copy of an MPI which doesn't reveal
187
 *          whether assignment was done or not.
188
 *
189
 * \param[out] X        The address of the destination MPI.
190
 *                      This must be initialized. Must have enough limbs to
191
 *                      store the full value of \p A.
192
 * \param[in]  A        The address of the source MPI. This must be initialized.
193
 * \param      limbs    The number of limbs of \p A.
194
 * \param      assign   The condition deciding whether to perform the
195
 *                      assignment or not. Callers will need to use
196
 *                      the constant time interface (e.g. `mbedtls_ct_bool()`)
197
 *                      to construct this argument.
198
 *
199
 * \note           This function avoids leaking any information about whether
200
 *                 the assignment was done or not.
201
 */
202
void mbedtls_mpi_core_cond_assign(mbedtls_mpi_uint *X,
203
                                  const mbedtls_mpi_uint *A,
204
                                  size_t limbs,
205
                                  mbedtls_ct_condition_t assign);
206
207
/**
208
 * \brief   Perform a safe conditional swap of two MPIs which doesn't reveal
209
 *          whether the swap was done or not.
210
 *
211
 * \param[in,out] X         The address of the first MPI.
212
 *                          This must be initialized.
213
 * \param[in,out] Y         The address of the second MPI.
214
 *                          This must be initialized.
215
 * \param         limbs     The number of limbs of \p X and \p Y.
216
 * \param         swap      The condition deciding whether to perform
217
 *                          the swap or not.
218
 *
219
 * \note           This function avoids leaking any information about whether
220
 *                 the swap was done or not.
221
 */
222
void mbedtls_mpi_core_cond_swap(mbedtls_mpi_uint *X,
223
                                mbedtls_mpi_uint *Y,
224
                                size_t limbs,
225
                                mbedtls_ct_condition_t swap);
226
227
/** Import X from unsigned binary data, little-endian.
228
 *
229
 * The MPI needs to have enough limbs to store the full value (including any
230
 * most significant zero bytes in the input).
231
 *
232
 * \param[out] X         The address of the MPI.
233
 * \param X_limbs        The number of limbs of \p X.
234
 * \param[in] input      The input buffer to import from.
235
 * \param input_length   The length bytes of \p input.
236
 *
237
 * \return       \c 0 if successful.
238
 * \return       #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't
239
 *               large enough to hold the value in \p input.
240
 */
241
int mbedtls_mpi_core_read_le(mbedtls_mpi_uint *X,
242
                             size_t X_limbs,
243
                             const unsigned char *input,
244
                             size_t input_length);
245
246
/** Import X from unsigned binary data, big-endian.
247
 *
248
 * The MPI needs to have enough limbs to store the full value (including any
249
 * most significant zero bytes in the input).
250
 *
251
 * \param[out] X        The address of the MPI.
252
 *                      May only be #NULL if \p X_limbs is 0 and \p input_length
253
 *                      is 0.
254
 * \param X_limbs       The number of limbs of \p X.
255
 * \param[in] input     The input buffer to import from.
256
 *                      May only be #NULL if \p input_length is 0.
257
 * \param input_length  The length in bytes of \p input.
258
 *
259
 * \return       \c 0 if successful.
260
 * \return       #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't
261
 *               large enough to hold the value in \p input.
262
 */
263
int mbedtls_mpi_core_read_be(mbedtls_mpi_uint *X,
264
                             size_t X_limbs,
265
                             const unsigned char *input,
266
                             size_t input_length);
267
268
/** Export A into unsigned binary data, little-endian.
269
 *
270
 * \note If \p output is shorter than \p A the export is still successful if the
271
 *       value held in \p A fits in the buffer (that is, if enough of the most
272
 *       significant bytes of \p A are 0).
273
 *
274
 * \param[in] A         The address of the MPI.
275
 * \param A_limbs       The number of limbs of \p A.
276
 * \param[out] output   The output buffer to export to.
277
 * \param output_length The length in bytes of \p output.
278
 *
279
 * \return       \c 0 if successful.
280
 * \return       #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't
281
 *               large enough to hold the value of \p A.
282
 */
283
int mbedtls_mpi_core_write_le(const mbedtls_mpi_uint *A,
284
                              size_t A_limbs,
285
                              unsigned char *output,
286
                              size_t output_length);
287
288
/** Export A into unsigned binary data, big-endian.
289
 *
290
 * \note If \p output is shorter than \p A the export is still successful if the
291
 *       value held in \p A fits in the buffer (that is, if enough of the most
292
 *       significant bytes of \p A are 0).
293
 *
294
 * \param[in] A         The address of the MPI.
295
 * \param A_limbs       The number of limbs of \p A.
296
 * \param[out] output   The output buffer to export to.
297
 * \param output_length The length in bytes of \p output.
298
 *
299
 * \return       \c 0 if successful.
300
 * \return       #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't
301
 *               large enough to hold the value of \p A.
302
 */
303
int mbedtls_mpi_core_write_be(const mbedtls_mpi_uint *A,
304
                              size_t A_limbs,
305
                              unsigned char *output,
306
                              size_t output_length);
307
308
/** \brief              Shift an MPI in-place right by a number of bits.
309
 *
310
 *                      Shifting by more bits than there are bit positions
311
 *                      in \p X is valid and results in setting \p X to 0.
312
 *
313
 *                      This function's execution time depends on the value
314
 *                      of \p count (and of course \p limbs).
315
 *
316
 * \param[in,out] X     The number to shift.
317
 * \param limbs         The number of limbs of \p X. This must be at least 1.
318
 * \param count         The number of bits to shift by.
319
 */
320
void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs,
321
                              size_t count);
322
323
/**
324
 * \brief               Shift an MPI in-place left by a number of bits.
325
 *
326
 *                      Shifting by more bits than there are bit positions
327
 *                      in \p X will produce an unspecified result.
328
 *
329
 *                      This function's execution time depends on the value
330
 *                      of \p count (and of course \p limbs).
331
 * \param[in,out] X     The number to shift.
332
 * \param limbs         The number of limbs of \p X. This must be at least 1.
333
 * \param count         The number of bits to shift by.
334
 */
335
void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs,
336
                              size_t count);
337
338
/**
339
 * \brief Add two fixed-size large unsigned integers, returning the carry.
340
 *
341
 * Calculates `A + B` where `A` and `B` have the same size.
342
 *
343
 * This function operates modulo `2^(biL*limbs)` and returns the carry
344
 * (1 if there was a wraparound, and 0 otherwise).
345
 *
346
 * \p X may be aliased to \p A or \p B.
347
 *
348
 * \param[out] X    The result of the addition.
349
 * \param[in] A     Little-endian presentation of the left operand.
350
 * \param[in] B     Little-endian presentation of the right operand.
351
 * \param limbs     Number of limbs of \p X, \p A and \p B.
352
 *
353
 * \return          1 if `A + B >= 2^(biL*limbs)`, 0 otherwise.
354
 */
355
mbedtls_mpi_uint mbedtls_mpi_core_add(mbedtls_mpi_uint *X,
356
                                      const mbedtls_mpi_uint *A,
357
                                      const mbedtls_mpi_uint *B,
358
                                      size_t limbs);
359
360
/**
361
 * \brief Conditional addition of two fixed-size large unsigned integers,
362
 *        returning the carry.
363
 *
364
 * Functionally equivalent to
365
 *
366
 * ```
367
 * if( cond )
368
 *    X += A;
369
 * return carry;
370
 * ```
371
 *
372
 * This function operates modulo `2^(biL*limbs)`.
373
 *
374
 * \param[in,out] X  The pointer to the (little-endian) array
375
 *                   representing the bignum to accumulate onto.
376
 * \param[in] A      The pointer to the (little-endian) array
377
 *                   representing the bignum to conditionally add
378
 *                   to \p X. This may be aliased to \p X but may not
379
 *                   overlap otherwise.
380
 * \param limbs      Number of limbs of \p X and \p A.
381
 * \param cond       Condition bit dictating whether addition should
382
 *                   happen or not. This must be \c 0 or \c 1.
383
 *
384
 * \warning          If \p cond is neither 0 nor 1, the result of this function
385
 *                   is unspecified, and the resulting value in \p X might be
386
 *                   neither its original value nor \p X + \p A.
387
 *
388
 * \return           1 if `X + cond * A >= 2^(biL*limbs)`, 0 otherwise.
389
 */
390
mbedtls_mpi_uint mbedtls_mpi_core_add_if(mbedtls_mpi_uint *X,
391
                                         const mbedtls_mpi_uint *A,
392
                                         size_t limbs,
393
                                         unsigned cond);
394
395
/**
396
 * \brief Subtract two fixed-size large unsigned integers, returning the borrow.
397
 *
398
 * Calculate `A - B` where \p A and \p B have the same size.
399
 * This function operates modulo `2^(biL*limbs)` and returns the carry
400
 * (1 if there was a wraparound, i.e. if `A < B`, and 0 otherwise).
401
 *
402
 * \p X may be aliased to \p A or \p B, or even both, but may not overlap
403
 * either otherwise.
404
 *
405
 * \param[out] X    The result of the subtraction.
406
 * \param[in] A     Little-endian presentation of left operand.
407
 * \param[in] B     Little-endian presentation of right operand.
408
 * \param limbs     Number of limbs of \p X, \p A and \p B.
409
 *
410
 * \return          1 if `A < B`.
411
 *                  0 if `A >= B`.
412
 */
413
mbedtls_mpi_uint mbedtls_mpi_core_sub(mbedtls_mpi_uint *X,
414
                                      const mbedtls_mpi_uint *A,
415
                                      const mbedtls_mpi_uint *B,
416
                                      size_t limbs);
417
418
/**
419
 * \brief Perform a fixed-size multiply accumulate operation: X += b * A
420
 *
421
 * \p X may be aliased to \p A (when \p X_limbs == \p A_limbs), but may not
422
 * otherwise overlap.
423
 *
424
 * This function operates modulo `2^(biL*X_limbs)`.
425
 *
426
 * \param[in,out] X  The pointer to the (little-endian) array
427
 *                   representing the bignum to accumulate onto.
428
 * \param X_limbs    The number of limbs of \p X. This must be
429
 *                   at least \p A_limbs.
430
 * \param[in] A      The pointer to the (little-endian) array
431
 *                   representing the bignum to multiply with.
432
 *                   This may be aliased to \p X but may not overlap
433
 *                   otherwise.
434
 * \param A_limbs    The number of limbs of \p A.
435
 * \param b          X scalar to multiply with.
436
 *
437
 * \return           The carry at the end of the operation.
438
 */
439
mbedtls_mpi_uint mbedtls_mpi_core_mla(mbedtls_mpi_uint *X, size_t X_limbs,
440
                                      const mbedtls_mpi_uint *A, size_t A_limbs,
441
                                      mbedtls_mpi_uint b);
442
443
/**
444
 * \brief Perform a known-size multiplication
445
 *
446
 * \p X may not be aliased to any of the inputs for this function.
447
 * \p A may be aliased to \p B.
448
 *
449
 * \param[out] X     The pointer to the (little-endian) array to receive
450
 *                   the product of \p A_limbs and \p B_limbs.
451
 *                   This must be of length \p A_limbs + \p B_limbs.
452
 * \param[in] A      The pointer to the (little-endian) array
453
 *                   representing the first factor.
454
 * \param A_limbs    The number of limbs in \p A.
455
 * \param[in] B      The pointer to the (little-endian) array
456
 *                   representing the second factor.
457
 * \param B_limbs    The number of limbs in \p B.
458
 */
459
void mbedtls_mpi_core_mul(mbedtls_mpi_uint *X,
460
                          const mbedtls_mpi_uint *A, size_t A_limbs,
461
                          const mbedtls_mpi_uint *B, size_t B_limbs);
462
463
/**
464
 * \brief Calculate initialisation value for fast Montgomery modular
465
 *        multiplication
466
 *
467
 * \param[in] N  Little-endian presentation of the modulus. This must have
468
 *               at least one limb.
469
 *
470
 * \return       The initialisation value for fast Montgomery modular multiplication
471
 */
472
mbedtls_mpi_uint mbedtls_mpi_core_montmul_init(const mbedtls_mpi_uint *N);
473
474
/**
475
 * \brief Montgomery multiplication: X = A * B * R^-1 mod N (HAC 14.36)
476
 *
477
 * \p A and \p B must be in canonical form. That is, < \p N.
478
 *
479
 * \p X may be aliased to \p A or \p N, or even \p B (if \p AN_limbs ==
480
 * \p B_limbs) but may not overlap any parameters otherwise.
481
 *
482
 * \p A and \p B may alias each other, if \p AN_limbs == \p B_limbs. They may
483
 * not alias \p N (since they must be in canonical form, they cannot == \p N).
484
 *
485
 * \param[out]    X         The destination MPI, as a little-endian array of
486
 *                          length \p AN_limbs.
487
 *                          On successful completion, X contains the result of
488
 *                          the multiplication `A * B * R^-1` mod N where
489
 *                          `R = 2^(biL*AN_limbs)`.
490
 * \param[in]     A         Little-endian presentation of first operand.
491
 *                          Must have the same number of limbs as \p N.
492
 * \param[in]     B         Little-endian presentation of second operand.
493
 * \param[in]     B_limbs   The number of limbs in \p B.
494
 *                          Must be <= \p AN_limbs.
495
 * \param[in]     N         Little-endian presentation of the modulus.
496
 *                          This must be odd, and have exactly the same number
497
 *                          of limbs as \p A.
498
 *                          It may alias \p X, but must not alias or otherwise
499
 *                          overlap any of the other parameters.
500
 * \param[in]     AN_limbs  The number of limbs in \p X, \p A and \p N.
501
 * \param         mm        The Montgomery constant for \p N: -N^-1 mod 2^biL.
502
 *                          This can be calculated by `mbedtls_mpi_core_montmul_init()`.
503
 * \param[in,out] T         Temporary storage of size at least 2*AN_limbs+1 limbs.
504
 *                          Its initial content is unused and
505
 *                          its final content is indeterminate.
506
 *                          It must not alias or otherwise overlap any of the
507
 *                          other parameters.
508
 */
509
void mbedtls_mpi_core_montmul(mbedtls_mpi_uint *X,
510
                              const mbedtls_mpi_uint *A,
511
                              const mbedtls_mpi_uint *B, size_t B_limbs,
512
                              const mbedtls_mpi_uint *N, size_t AN_limbs,
513
                              mbedtls_mpi_uint mm, mbedtls_mpi_uint *T);
514
515
/**
516
 * \brief Calculate the square of the Montgomery constant. (Needed
517
 *        for conversion and operations in Montgomery form.)
518
 *
519
 * \param[out] X  A pointer to the result of the calculation of
520
 *                the square of the Montgomery constant:
521
 *                2^{2*n*biL} mod N.
522
 * \param[in]  N  Little-endian presentation of the modulus, which must be odd.
523
 *
524
 * \return        0 if successful.
525
 * \return        #MBEDTLS_ERR_MPI_ALLOC_FAILED if there is not enough space
526
 *                to store the value of Montgomery constant squared.
527
 * \return        #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p N modulus is zero.
528
 * \return        #MBEDTLS_ERR_MPI_NEGATIVE_VALUE if \p N modulus is negative.
529
 */
530
int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X,
531
                                        const mbedtls_mpi *N);
532
533
#if defined(MBEDTLS_TEST_HOOKS)
534
/**
535
 * Copy an MPI from a table without leaking the index.
536
 *
537
 * \param dest              The destination buffer. This must point to a writable
538
 *                          buffer of at least \p limbs limbs.
539
 * \param table             The address of the table. This must point to a readable
540
 *                          array of \p count elements of \p limbs limbs each.
541
 * \param limbs             The number of limbs in each table entry.
542
 * \param count             The number of entries in \p table.
543
 * \param index             The (secret) table index to look up. This must be in the
544
 *                          range `0 .. count-1`.
545
 */
546
void mbedtls_mpi_core_ct_uint_table_lookup(mbedtls_mpi_uint *dest,
547
                                           const mbedtls_mpi_uint *table,
548
                                           size_t limbs,
549
                                           size_t count,
550
                                           size_t index);
551
#endif /* MBEDTLS_TEST_HOOKS */
552
553
/**
554
 * \brief          Fill an integer with a number of random bytes.
555
 *
556
 * \param X        The destination MPI.
557
 * \param X_limbs  The number of limbs of \p X.
558
 * \param bytes    The number of random bytes to generate.
559
 * \param f_rng    The RNG function to use. This must not be \c NULL.
560
 * \param p_rng    The RNG parameter to be passed to \p f_rng. This may be
561
 *                 \c NULL if \p f_rng doesn't need a context argument.
562
 *
563
 * \return         \c 0 if successful.
564
 * \return         #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p X does not have
565
 *                 enough room for \p bytes bytes.
566
 * \return         A negative error code on RNG failure.
567
 *
568
 * \note           The bytes obtained from the RNG are interpreted
569
 *                 as a big-endian representation of an MPI; this can
570
 *                 be relevant in applications like deterministic ECDSA.
571
 */
572
int mbedtls_mpi_core_fill_random(mbedtls_mpi_uint *X, size_t X_limbs,
573
                                 size_t bytes,
574
                                 int (*f_rng)(void *, unsigned char *, size_t),
575
                                 void *p_rng);
576
577
/** Generate a random number uniformly in a range.
578
 *
579
 * This function generates a random number between \p min inclusive and
580
 * \p N exclusive.
581
 *
582
 * The procedure complies with RFC 6979 ยง3.3 (deterministic ECDSA)
583
 * when the RNG is a suitably parametrized instance of HMAC_DRBG
584
 * and \p min is \c 1.
585
 *
586
 * \note           There are `N - min` possible outputs. The lower bound
587
 *                 \p min can be reached, but the upper bound \p N cannot.
588
 *
589
 * \param X        The destination MPI, with \p limbs limbs.
590
 *                 It must not be aliased with \p N or otherwise overlap it.
591
 * \param min      The minimum value to return.
592
 * \param N        The upper bound of the range, exclusive, with \p limbs limbs.
593
 *                 In other words, this is one plus the maximum value to return.
594
 *                 \p N must be strictly larger than \p min.
595
 * \param limbs    The number of limbs of \p N and \p X.
596
 *                 This must not be 0.
597
 * \param f_rng    The RNG function to use. This must not be \c NULL.
598
 * \param p_rng    The RNG parameter to be passed to \p f_rng.
599
 *
600
 * \return         \c 0 if successful.
601
 * \return         #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was
602
 *                 unable to find a suitable value within a limited number
603
 *                 of attempts. This has a negligible probability if \p N
604
 *                 is significantly larger than \p min, which is the case
605
 *                 for all usual cryptographic applications.
606
 */
607
int mbedtls_mpi_core_random(mbedtls_mpi_uint *X,
608
                            mbedtls_mpi_uint min,
609
                            const mbedtls_mpi_uint *N,
610
                            size_t limbs,
611
                            int (*f_rng)(void *, unsigned char *, size_t),
612
                            void *p_rng);
613
614
/**
615
 * \brief          Returns the number of limbs of working memory required for
616
 *                 a call to `mbedtls_mpi_core_exp_mod()`.
617
 *
618
 * \note           This will always be at least
619
 *                 `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`,
620
 *                 i.e. sufficient for a call to `mbedtls_mpi_core_montmul()`.
621
 *
622
 * \param AN_limbs The number of limbs in the input `A` and the modulus `N`
623
 *                 (they must be the same size) that will be given to
624
 *                 `mbedtls_mpi_core_exp_mod()`.
625
 * \param E_limbs  The number of limbs in the exponent `E` that will be given
626
 *                 to `mbedtls_mpi_core_exp_mod()`.
627
 *
628
 * \return         The number of limbs of working memory required by
629
 *                 `mbedtls_mpi_core_exp_mod()`.
630
 */
631
size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs);
632
633
/**
634
 * \brief            Perform a modular exponentiation with public or secret exponent:
635
 *                   X = A^E mod N, where \p A is already in Montgomery form.
636
 *
637
 * \warning          This function is not constant time with respect to \p E (the exponent).
638
 *
639
 * \p X may be aliased to \p A, but not to \p RR or \p E, even if \p E_limbs ==
640
 * \p AN_limbs.
641
 *
642
 * \param[out] X     The destination MPI, as a little endian array of length
643
 *                   \p AN_limbs.
644
 * \param[in] A      The base MPI, as a little endian array of length \p AN_limbs.
645
 *                   Must be in Montgomery form.
646
 * \param[in] N      The modulus, as a little endian array of length \p AN_limbs.
647
 * \param AN_limbs   The number of limbs in \p X, \p A, \p N, \p RR.
648
 * \param[in] E      The exponent, as a little endian array of length \p E_limbs.
649
 * \param E_limbs    The number of limbs in \p E.
650
 * \param[in] RR     The precomputed residue of 2^{2*biL} modulo N, as a little
651
 *                   endian array of length \p AN_limbs.
652
 * \param[in,out] T  Temporary storage of at least the number of limbs returned
653
 *                   by `mbedtls_mpi_core_exp_mod_working_limbs()`.
654
 *                   Its initial content is unused and its final content is
655
 *                   indeterminate.
656
 *                   It must not alias or otherwise overlap any of the other
657
 *                   parameters.
658
 *                   It is up to the caller to zeroize \p T when it is no
659
 *                   longer needed, and before freeing it if it was dynamically
660
 *                   allocated.
661
 */
662
void mbedtls_mpi_core_exp_mod_unsafe(mbedtls_mpi_uint *X,
663
                                     const mbedtls_mpi_uint *A,
664
                                     const mbedtls_mpi_uint *N, size_t AN_limbs,
665
                                     const mbedtls_mpi_uint *E, size_t E_limbs,
666
                                     const mbedtls_mpi_uint *RR,
667
                                     mbedtls_mpi_uint *T);
668
669
/**
670
 * \brief            Perform a modular exponentiation with secret exponent:
671
 *                   X = A^E mod N, where \p A is already in Montgomery form.
672
 *
673
 * \p X may be aliased to \p A, but not to \p RR or \p E, even if \p E_limbs ==
674
 * \p AN_limbs.
675
 *
676
 * \param[out] X     The destination MPI, as a little endian array of length
677
 *                   \p AN_limbs.
678
 * \param[in] A      The base MPI, as a little endian array of length \p AN_limbs.
679
 *                   Must be in Montgomery form.
680
 * \param[in] N      The modulus, as a little endian array of length \p AN_limbs.
681
 * \param AN_limbs   The number of limbs in \p X, \p A, \p N, \p RR.
682
 * \param[in] E      The exponent, as a little endian array of length \p E_limbs.
683
 * \param E_limbs    The number of limbs in \p E.
684
 * \param[in] RR     The precomputed residue of 2^{2*biL} modulo N, as a little
685
 *                   endian array of length \p AN_limbs.
686
 * \param[in,out] T  Temporary storage of at least the number of limbs returned
687
 *                   by `mbedtls_mpi_core_exp_mod_working_limbs()`.
688
 *                   Its initial content is unused and its final content is
689
 *                   indeterminate.
690
 *                   It must not alias or otherwise overlap any of the other
691
 *                   parameters.
692
 *                   It is up to the caller to zeroize \p T when it is no
693
 *                   longer needed, and before freeing it if it was dynamically
694
 *                   allocated.
695
 */
696
void mbedtls_mpi_core_exp_mod(mbedtls_mpi_uint *X,
697
                              const mbedtls_mpi_uint *A,
698
                              const mbedtls_mpi_uint *N, size_t AN_limbs,
699
                              const mbedtls_mpi_uint *E, size_t E_limbs,
700
                              const mbedtls_mpi_uint *RR,
701
                              mbedtls_mpi_uint *T);
702
703
/**
704
 * \brief Subtract unsigned integer from known-size large unsigned integers.
705
 *        Return the borrow.
706
 *
707
 * \param[out] X    The result of the subtraction.
708
 * \param[in] A     The left operand.
709
 * \param b         The unsigned scalar to subtract.
710
 * \param limbs     Number of limbs of \p X and \p A.
711
 *
712
 * \return          1 if `A < b`.
713
 *                  0 if `A >= b`.
714
 */
715
mbedtls_mpi_uint mbedtls_mpi_core_sub_int(mbedtls_mpi_uint *X,
716
                                          const mbedtls_mpi_uint *A,
717
                                          mbedtls_mpi_uint b,
718
                                          size_t limbs);
719
720
/**
721
 * \brief Determine if a given MPI has the value \c 0 in constant time with
722
 *        respect to the value (but not with respect to the number of limbs).
723
 *
724
 * \param[in] A   The MPI to test.
725
 * \param limbs   Number of limbs in \p A.
726
 *
727
 * \return        MBEDTLS_CT_FALSE if `A == 0`
728
 *                MBEDTLS_CT_TRUE  if `A != 0`.
729
 */
730
mbedtls_ct_condition_t mbedtls_mpi_core_check_zero_ct(const mbedtls_mpi_uint *A,
731
                                                      size_t limbs);
732
733
/**
734
 * \brief          Returns the number of limbs of working memory required for
735
 *                 a call to `mbedtls_mpi_core_montmul()`.
736
 *
737
 * \param AN_limbs The number of limbs in the input `A` and the modulus `N`
738
 *                 (they must be the same size) that will be given to
739
 *                 `mbedtls_mpi_core_montmul()` or one of the other functions
740
 *                 that specifies this as the amount of working memory needed.
741
 *
742
 * \return         The number of limbs of working memory required by
743
 *                 `mbedtls_mpi_core_montmul()` (or other similar function).
744
 */
745
static inline size_t mbedtls_mpi_core_montmul_working_limbs(size_t AN_limbs)
746
0
{
747
0
    return 2 * AN_limbs + 1;
748
0
}
Unexecuted instantiation: rsa.c:mbedtls_mpi_core_montmul_working_limbs
Unexecuted instantiation: bignum.c:mbedtls_mpi_core_montmul_working_limbs
Unexecuted instantiation: bignum_core.c:mbedtls_mpi_core_montmul_working_limbs
Unexecuted instantiation: ecp_curves.c:mbedtls_mpi_core_montmul_working_limbs
749
750
/** Convert an MPI into Montgomery form.
751
 *
752
 * \p X may be aliased to \p A, but may not otherwise overlap it.
753
 *
754
 * \p X may not alias \p N (it is in canonical form, so must be strictly less
755
 * than \p N). Nor may it alias or overlap \p rr (this is unlikely to be
756
 * required in practice.)
757
 *
758
 * This function is a thin wrapper around `mbedtls_mpi_core_montmul()` that is
759
 * an alternative to calling `mbedtls_mpi_mod_raw_to_mont_rep()` when we
760
 * don't want to allocate memory.
761
 *
762
 * \param[out]    X         The result of the conversion.
763
 *                          Must have the same number of limbs as \p A.
764
 * \param[in]     A         The MPI to convert into Montgomery form.
765
 *                          Must have the same number of limbs as the modulus.
766
 * \param[in]     N         The address of the modulus, which gives the size of
767
 *                          the base `R` = 2^(biL*N->limbs).
768
 * \param[in]     AN_limbs  The number of limbs in \p X, \p A, \p N and \p rr.
769
 * \param         mm        The Montgomery constant for \p N: -N^-1 mod 2^biL.
770
 *                          This can be determined by calling
771
 *                          `mbedtls_mpi_core_montmul_init()`.
772
 * \param[in]     rr        The residue for `2^{2*n*biL} mod N`.
773
 * \param[in,out] T         Temporary storage of size at least
774
 *                          `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`
775
 *                          limbs.
776
 *                          Its initial content is unused and
777
 *                          its final content is indeterminate.
778
 *                          It must not alias or otherwise overlap any of the
779
 *                          other parameters.
780
 */
781
void mbedtls_mpi_core_to_mont_rep(mbedtls_mpi_uint *X,
782
                                  const mbedtls_mpi_uint *A,
783
                                  const mbedtls_mpi_uint *N,
784
                                  size_t AN_limbs,
785
                                  mbedtls_mpi_uint mm,
786
                                  const mbedtls_mpi_uint *rr,
787
                                  mbedtls_mpi_uint *T);
788
789
/** Convert an MPI from Montgomery form.
790
 *
791
 * \p X may be aliased to \p A, but may not otherwise overlap it.
792
 *
793
 * \p X may not alias \p N (it is in canonical form, so must be strictly less
794
 * than \p N).
795
 *
796
 * This function is a thin wrapper around `mbedtls_mpi_core_montmul()` that is
797
 * an alternative to calling `mbedtls_mpi_mod_raw_from_mont_rep()` when we
798
 * don't want to allocate memory.
799
 *
800
 * \param[out]    X         The result of the conversion.
801
 *                          Must have the same number of limbs as \p A.
802
 * \param[in]     A         The MPI to convert from Montgomery form.
803
 *                          Must have the same number of limbs as the modulus.
804
 * \param[in]     N         The address of the modulus, which gives the size of
805
 *                          the base `R` = 2^(biL*N->limbs).
806
 * \param[in]     AN_limbs  The number of limbs in \p X, \p A and \p N.
807
 * \param         mm        The Montgomery constant for \p N: -N^-1 mod 2^biL.
808
 *                          This can be determined by calling
809
 *                          `mbedtls_mpi_core_montmul_init()`.
810
 * \param[in,out] T         Temporary storage of size at least
811
 *                          `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`
812
 *                          limbs.
813
 *                          Its initial content is unused and
814
 *                          its final content is indeterminate.
815
 *                          It must not alias or otherwise overlap any of the
816
 *                          other parameters.
817
 */
818
void mbedtls_mpi_core_from_mont_rep(mbedtls_mpi_uint *X,
819
                                    const mbedtls_mpi_uint *A,
820
                                    const mbedtls_mpi_uint *N,
821
                                    size_t AN_limbs,
822
                                    mbedtls_mpi_uint mm,
823
                                    mbedtls_mpi_uint *T);
824
825
#endif /* MBEDTLS_BIGNUM_CORE_H */