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 #define ciL (sizeof(mbedtls_mpi_uint)) /** chars in limb */
78 #define biL (ciL << 3) /** bits in limb */
79 #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 #define BITS_TO_LIMBS(i) ((i) / biL + ((i) % biL != 0))
86 #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 (((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 #define MBEDTLS_MPI_IS_PUBLIC 0x2a2a2a2a
113 #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 */
mbedtls_mpi_core_montmul_working_limbs(size_t AN_limbs)745 static inline size_t mbedtls_mpi_core_montmul_working_limbs(size_t AN_limbs)
746 {
747 return 2 * AN_limbs + 1;
748 }
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 */
826