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 #if defined(MBEDTLS_BIGNUM_C)
74 #include "mbedtls/bignum.h"
75 #endif
76
77 #include "constant_time_internal.h"
78
79 #define ciL (sizeof(mbedtls_mpi_uint)) /** chars in limb */
80 #define biL (ciL << 3) /** bits in limb */
81 #define biH (ciL << 2) /** half limb size */
82
83 /*
84 * Convert between bits/chars and number of limbs
85 * Divide first in order to avoid potential overflows
86 */
87 #define BITS_TO_LIMBS(i) ((i) / biL + ((i) % biL != 0))
88 #define CHARS_TO_LIMBS(i) ((i) / ciL + ((i) % ciL != 0))
89 /* Get a specific byte, without range checks. */
90 #define GET_BYTE(X, i) \
91 (((X)[(i) / ciL] >> (((i) % ciL) * 8)) & 0xff)
92
93 /** Count leading zero bits in a given integer.
94 *
95 * \warning The result is undefined if \p a == 0
96 *
97 * \param a Integer to count leading zero bits.
98 *
99 * \return The number of leading zero bits in \p a, if \p a != 0.
100 * If \p a == 0, the result is undefined.
101 */
102 size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a);
103
104 /** Return the minimum number of bits required to represent the value held
105 * in the MPI.
106 *
107 * \note This function returns 0 if all the limbs of \p A are 0.
108 *
109 * \param[in] A The address of the MPI.
110 * \param A_limbs The number of limbs of \p A.
111 *
112 * \return The number of bits in \p A.
113 */
114 size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs);
115
116 /** Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
117 * into the storage form used by mbedtls_mpi.
118 *
119 * \param[in,out] A The address of the MPI.
120 * \param A_limbs The number of limbs of \p A.
121 */
122 void mbedtls_mpi_core_bigendian_to_host(mbedtls_mpi_uint *A,
123 size_t A_limbs);
124
125 /** \brief Compare a machine integer with an MPI.
126 *
127 * This function operates in constant time with respect
128 * to the values of \p min and \p A.
129 *
130 * \param min A machine integer.
131 * \param[in] A An MPI.
132 * \param A_limbs The number of limbs of \p A.
133 * This must be at least 1.
134 *
135 * \return MBEDTLS_CT_TRUE if \p min is less than or equal to \p A, otherwise MBEDTLS_CT_FALSE.
136 */
137 mbedtls_ct_condition_t mbedtls_mpi_core_uint_le_mpi(mbedtls_mpi_uint min,
138 const mbedtls_mpi_uint *A,
139 size_t A_limbs);
140
141 /**
142 * \brief Check if one unsigned MPI is less than another in constant
143 * time.
144 *
145 * \param A The left-hand MPI. This must point to an array of limbs
146 * with the same allocated length as \p B.
147 * \param B The right-hand MPI. This must point to an array of limbs
148 * with the same allocated length as \p A.
149 * \param limbs The number of limbs in \p A and \p B.
150 * This must not be 0.
151 *
152 * \return MBEDTLS_CT_TRUE if \p A is less than \p B.
153 * MBEDTLS_CT_FALSE if \p A is greater than or equal to \p B.
154 */
155 mbedtls_ct_condition_t mbedtls_mpi_core_lt_ct(const mbedtls_mpi_uint *A,
156 const mbedtls_mpi_uint *B,
157 size_t limbs);
158
159 /**
160 * \brief Perform a safe conditional copy of an MPI which doesn't reveal
161 * whether assignment was done or not.
162 *
163 * \param[out] X The address of the destination MPI.
164 * This must be initialized. Must have enough limbs to
165 * store the full value of \p A.
166 * \param[in] A The address of the source MPI. This must be initialized.
167 * \param limbs The number of limbs of \p A.
168 * \param assign The condition deciding whether to perform the
169 * assignment or not. Callers will need to use
170 * the constant time interface (e.g. `mbedtls_ct_bool()`)
171 * to construct this argument.
172 *
173 * \note This function avoids leaking any information about whether
174 * the assignment was done or not.
175 */
176 void mbedtls_mpi_core_cond_assign(mbedtls_mpi_uint *X,
177 const mbedtls_mpi_uint *A,
178 size_t limbs,
179 mbedtls_ct_condition_t assign);
180
181 /**
182 * \brief Perform a safe conditional swap of two MPIs which doesn't reveal
183 * whether the swap was done or not.
184 *
185 * \param[in,out] X The address of the first MPI.
186 * This must be initialized.
187 * \param[in,out] Y The address of the second MPI.
188 * This must be initialized.
189 * \param limbs The number of limbs of \p X and \p Y.
190 * \param swap The condition deciding whether to perform
191 * the swap or not.
192 *
193 * \note This function avoids leaking any information about whether
194 * the swap was done or not.
195 */
196 void mbedtls_mpi_core_cond_swap(mbedtls_mpi_uint *X,
197 mbedtls_mpi_uint *Y,
198 size_t limbs,
199 mbedtls_ct_condition_t swap);
200
201 /** Import X from unsigned binary data, little-endian.
202 *
203 * The MPI needs to have enough limbs to store the full value (including any
204 * most significant zero bytes in the input).
205 *
206 * \param[out] X The address of the MPI.
207 * \param X_limbs The number of limbs of \p X.
208 * \param[in] input The input buffer to import from.
209 * \param input_length The length bytes of \p input.
210 *
211 * \return \c 0 if successful.
212 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't
213 * large enough to hold the value in \p input.
214 */
215 int mbedtls_mpi_core_read_le(mbedtls_mpi_uint *X,
216 size_t X_limbs,
217 const unsigned char *input,
218 size_t input_length);
219
220 /** Import X from unsigned binary data, big-endian.
221 *
222 * The MPI needs to have enough limbs to store the full value (including any
223 * most significant zero bytes in the input).
224 *
225 * \param[out] X The address of the MPI.
226 * May only be #NULL if \p X_limbs is 0 and \p input_length
227 * is 0.
228 * \param X_limbs The number of limbs of \p X.
229 * \param[in] input The input buffer to import from.
230 * May only be #NULL if \p input_length is 0.
231 * \param input_length The length in bytes of \p input.
232 *
233 * \return \c 0 if successful.
234 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p X isn't
235 * large enough to hold the value in \p input.
236 */
237 int mbedtls_mpi_core_read_be(mbedtls_mpi_uint *X,
238 size_t X_limbs,
239 const unsigned char *input,
240 size_t input_length);
241
242 /** Export A into unsigned binary data, little-endian.
243 *
244 * \note If \p output is shorter than \p A the export is still successful if the
245 * value held in \p A fits in the buffer (that is, if enough of the most
246 * significant bytes of \p A are 0).
247 *
248 * \param[in] A The address of the MPI.
249 * \param A_limbs The number of limbs of \p A.
250 * \param[out] output The output buffer to export to.
251 * \param output_length The length in bytes of \p output.
252 *
253 * \return \c 0 if successful.
254 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't
255 * large enough to hold the value of \p A.
256 */
257 int mbedtls_mpi_core_write_le(const mbedtls_mpi_uint *A,
258 size_t A_limbs,
259 unsigned char *output,
260 size_t output_length);
261
262 /** Export A into unsigned binary data, big-endian.
263 *
264 * \note If \p output is shorter than \p A the export is still successful if the
265 * value held in \p A fits in the buffer (that is, if enough of the most
266 * significant bytes of \p A are 0).
267 *
268 * \param[in] A The address of the MPI.
269 * \param A_limbs The number of limbs of \p A.
270 * \param[out] output The output buffer to export to.
271 * \param output_length The length in bytes of \p output.
272 *
273 * \return \c 0 if successful.
274 * \return #MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL if \p output isn't
275 * large enough to hold the value of \p A.
276 */
277 int mbedtls_mpi_core_write_be(const mbedtls_mpi_uint *A,
278 size_t A_limbs,
279 unsigned char *output,
280 size_t output_length);
281
282 /** \brief Shift an MPI in-place right by a number of bits.
283 *
284 * Shifting by more bits than there are bit positions
285 * in \p X is valid and results in setting \p X to 0.
286 *
287 * This function's execution time depends on the value
288 * of \p count (and of course \p limbs).
289 *
290 * \param[in,out] X The number to shift.
291 * \param limbs The number of limbs of \p X. This must be at least 1.
292 * \param count The number of bits to shift by.
293 */
294 void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs,
295 size_t count);
296
297 /**
298 * \brief Shift an MPI in-place left by a number of bits.
299 *
300 * Shifting by more bits than there are bit positions
301 * in \p X will produce an unspecified result.
302 *
303 * This function's execution time depends on the value
304 * of \p count (and of course \p limbs).
305 * \param[in,out] X The number to shift.
306 * \param limbs The number of limbs of \p X. This must be at least 1.
307 * \param count The number of bits to shift by.
308 */
309 void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs,
310 size_t count);
311
312 /**
313 * \brief Add two fixed-size large unsigned integers, returning the carry.
314 *
315 * Calculates `A + B` where `A` and `B` have the same size.
316 *
317 * This function operates modulo `2^(biL*limbs)` and returns the carry
318 * (1 if there was a wraparound, and 0 otherwise).
319 *
320 * \p X may be aliased to \p A or \p B.
321 *
322 * \param[out] X The result of the addition.
323 * \param[in] A Little-endian presentation of the left operand.
324 * \param[in] B Little-endian presentation of the right operand.
325 * \param limbs Number of limbs of \p X, \p A and \p B.
326 *
327 * \return 1 if `A + B >= 2^(biL*limbs)`, 0 otherwise.
328 */
329 mbedtls_mpi_uint mbedtls_mpi_core_add(mbedtls_mpi_uint *X,
330 const mbedtls_mpi_uint *A,
331 const mbedtls_mpi_uint *B,
332 size_t limbs);
333
334 /**
335 * \brief Conditional addition of two fixed-size large unsigned integers,
336 * returning the carry.
337 *
338 * Functionally equivalent to
339 *
340 * ```
341 * if( cond )
342 * X += A;
343 * return carry;
344 * ```
345 *
346 * This function operates modulo `2^(biL*limbs)`.
347 *
348 * \param[in,out] X The pointer to the (little-endian) array
349 * representing the bignum to accumulate onto.
350 * \param[in] A The pointer to the (little-endian) array
351 * representing the bignum to conditionally add
352 * to \p X. This may be aliased to \p X but may not
353 * overlap otherwise.
354 * \param limbs Number of limbs of \p X and \p A.
355 * \param cond Condition bit dictating whether addition should
356 * happen or not. This must be \c 0 or \c 1.
357 *
358 * \warning If \p cond is neither 0 nor 1, the result of this function
359 * is unspecified, and the resulting value in \p X might be
360 * neither its original value nor \p X + \p A.
361 *
362 * \return 1 if `X + cond * A >= 2^(biL*limbs)`, 0 otherwise.
363 */
364 mbedtls_mpi_uint mbedtls_mpi_core_add_if(mbedtls_mpi_uint *X,
365 const mbedtls_mpi_uint *A,
366 size_t limbs,
367 unsigned cond);
368
369 /**
370 * \brief Subtract two fixed-size large unsigned integers, returning the borrow.
371 *
372 * Calculate `A - B` where \p A and \p B have the same size.
373 * This function operates modulo `2^(biL*limbs)` and returns the carry
374 * (1 if there was a wraparound, i.e. if `A < B`, and 0 otherwise).
375 *
376 * \p X may be aliased to \p A or \p B, or even both, but may not overlap
377 * either otherwise.
378 *
379 * \param[out] X The result of the subtraction.
380 * \param[in] A Little-endian presentation of left operand.
381 * \param[in] B Little-endian presentation of right operand.
382 * \param limbs Number of limbs of \p X, \p A and \p B.
383 *
384 * \return 1 if `A < B`.
385 * 0 if `A >= B`.
386 */
387 mbedtls_mpi_uint mbedtls_mpi_core_sub(mbedtls_mpi_uint *X,
388 const mbedtls_mpi_uint *A,
389 const mbedtls_mpi_uint *B,
390 size_t limbs);
391
392 /**
393 * \brief Perform a fixed-size multiply accumulate operation: X += b * A
394 *
395 * \p X may be aliased to \p A (when \p X_limbs == \p A_limbs), but may not
396 * otherwise overlap.
397 *
398 * This function operates modulo `2^(biL*X_limbs)`.
399 *
400 * \param[in,out] X The pointer to the (little-endian) array
401 * representing the bignum to accumulate onto.
402 * \param X_limbs The number of limbs of \p X. This must be
403 * at least \p A_limbs.
404 * \param[in] A The pointer to the (little-endian) array
405 * representing the bignum to multiply with.
406 * This may be aliased to \p X but may not overlap
407 * otherwise.
408 * \param A_limbs The number of limbs of \p A.
409 * \param b X scalar to multiply with.
410 *
411 * \return The carry at the end of the operation.
412 */
413 mbedtls_mpi_uint mbedtls_mpi_core_mla(mbedtls_mpi_uint *X, size_t X_limbs,
414 const mbedtls_mpi_uint *A, size_t A_limbs,
415 mbedtls_mpi_uint b);
416
417 /**
418 * \brief Perform a known-size multiplication
419 *
420 * \p X may not be aliased to any of the inputs for this function.
421 * \p A may be aliased to \p B.
422 *
423 * \param[out] X The pointer to the (little-endian) array to receive
424 * the product of \p A_limbs and \p B_limbs.
425 * This must be of length \p A_limbs + \p B_limbs.
426 * \param[in] A The pointer to the (little-endian) array
427 * representing the first factor.
428 * \param A_limbs The number of limbs in \p A.
429 * \param[in] B The pointer to the (little-endian) array
430 * representing the second factor.
431 * \param B_limbs The number of limbs in \p B.
432 */
433 void mbedtls_mpi_core_mul(mbedtls_mpi_uint *X,
434 const mbedtls_mpi_uint *A, size_t A_limbs,
435 const mbedtls_mpi_uint *B, size_t B_limbs);
436
437 /**
438 * \brief Calculate initialisation value for fast Montgomery modular
439 * multiplication
440 *
441 * \param[in] N Little-endian presentation of the modulus. This must have
442 * at least one limb.
443 *
444 * \return The initialisation value for fast Montgomery modular multiplication
445 */
446 mbedtls_mpi_uint mbedtls_mpi_core_montmul_init(const mbedtls_mpi_uint *N);
447
448 /**
449 * \brief Montgomery multiplication: X = A * B * R^-1 mod N (HAC 14.36)
450 *
451 * \p A and \p B must be in canonical form. That is, < \p N.
452 *
453 * \p X may be aliased to \p A or \p N, or even \p B (if \p AN_limbs ==
454 * \p B_limbs) but may not overlap any parameters otherwise.
455 *
456 * \p A and \p B may alias each other, if \p AN_limbs == \p B_limbs. They may
457 * not alias \p N (since they must be in canonical form, they cannot == \p N).
458 *
459 * \param[out] X The destination MPI, as a little-endian array of
460 * length \p AN_limbs.
461 * On successful completion, X contains the result of
462 * the multiplication `A * B * R^-1` mod N where
463 * `R = 2^(biL*AN_limbs)`.
464 * \param[in] A Little-endian presentation of first operand.
465 * Must have the same number of limbs as \p N.
466 * \param[in] B Little-endian presentation of second operand.
467 * \param[in] B_limbs The number of limbs in \p B.
468 * Must be <= \p AN_limbs.
469 * \param[in] N Little-endian presentation of the modulus.
470 * This must be odd, and have exactly the same number
471 * of limbs as \p A.
472 * It may alias \p X, but must not alias or otherwise
473 * overlap any of the other parameters.
474 * \param[in] AN_limbs The number of limbs in \p X, \p A and \p N.
475 * \param mm The Montgomery constant for \p N: -N^-1 mod 2^biL.
476 * This can be calculated by `mbedtls_mpi_core_montmul_init()`.
477 * \param[in,out] T Temporary storage of size at least 2*AN_limbs+1 limbs.
478 * Its initial content is unused and
479 * its final content is indeterminate.
480 * It must not alias or otherwise overlap any of the
481 * other parameters.
482 */
483 void mbedtls_mpi_core_montmul(mbedtls_mpi_uint *X,
484 const mbedtls_mpi_uint *A,
485 const mbedtls_mpi_uint *B, size_t B_limbs,
486 const mbedtls_mpi_uint *N, size_t AN_limbs,
487 mbedtls_mpi_uint mm, mbedtls_mpi_uint *T);
488
489 /**
490 * \brief Calculate the square of the Montgomery constant. (Needed
491 * for conversion and operations in Montgomery form.)
492 *
493 * \param[out] X A pointer to the result of the calculation of
494 * the square of the Montgomery constant:
495 * 2^{2*n*biL} mod N.
496 * \param[in] N Little-endian presentation of the modulus, which must be odd.
497 *
498 * \return 0 if successful.
499 * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if there is not enough space
500 * to store the value of Montgomery constant squared.
501 * \return #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p N modulus is zero.
502 * \return #MBEDTLS_ERR_MPI_NEGATIVE_VALUE if \p N modulus is negative.
503 */
504 int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X,
505 const mbedtls_mpi *N);
506
507 #if defined(MBEDTLS_TEST_HOOKS)
508 /**
509 * Copy an MPI from a table without leaking the index.
510 *
511 * \param dest The destination buffer. This must point to a writable
512 * buffer of at least \p limbs limbs.
513 * \param table The address of the table. This must point to a readable
514 * array of \p count elements of \p limbs limbs each.
515 * \param limbs The number of limbs in each table entry.
516 * \param count The number of entries in \p table.
517 * \param index The (secret) table index to look up. This must be in the
518 * range `0 .. count-1`.
519 */
520 void mbedtls_mpi_core_ct_uint_table_lookup(mbedtls_mpi_uint *dest,
521 const mbedtls_mpi_uint *table,
522 size_t limbs,
523 size_t count,
524 size_t index);
525 #endif /* MBEDTLS_TEST_HOOKS */
526
527 /**
528 * \brief Fill an integer with a number of random bytes.
529 *
530 * \param X The destination MPI.
531 * \param X_limbs The number of limbs of \p X.
532 * \param bytes The number of random bytes to generate.
533 * \param f_rng The RNG function to use. This must not be \c NULL.
534 * \param p_rng The RNG parameter to be passed to \p f_rng. This may be
535 * \c NULL if \p f_rng doesn't need a context argument.
536 *
537 * \return \c 0 if successful.
538 * \return #MBEDTLS_ERR_MPI_BAD_INPUT_DATA if \p X does not have
539 * enough room for \p bytes bytes.
540 * \return A negative error code on RNG failure.
541 *
542 * \note The bytes obtained from the RNG are interpreted
543 * as a big-endian representation of an MPI; this can
544 * be relevant in applications like deterministic ECDSA.
545 */
546 int mbedtls_mpi_core_fill_random(mbedtls_mpi_uint *X, size_t X_limbs,
547 size_t bytes,
548 int (*f_rng)(void *, unsigned char *, size_t),
549 void *p_rng);
550
551 /** Generate a random number uniformly in a range.
552 *
553 * This function generates a random number between \p min inclusive and
554 * \p N exclusive.
555 *
556 * The procedure complies with RFC 6979 §3.3 (deterministic ECDSA)
557 * when the RNG is a suitably parametrized instance of HMAC_DRBG
558 * and \p min is \c 1.
559 *
560 * \note There are `N - min` possible outputs. The lower bound
561 * \p min can be reached, but the upper bound \p N cannot.
562 *
563 * \param X The destination MPI, with \p limbs limbs.
564 * It must not be aliased with \p N or otherwise overlap it.
565 * \param min The minimum value to return.
566 * \param N The upper bound of the range, exclusive, with \p limbs limbs.
567 * In other words, this is one plus the maximum value to return.
568 * \p N must be strictly larger than \p min.
569 * \param limbs The number of limbs of \p N and \p X.
570 * This must not be 0.
571 * \param f_rng The RNG function to use. This must not be \c NULL.
572 * \param p_rng The RNG parameter to be passed to \p f_rng.
573 *
574 * \return \c 0 if successful.
575 * \return #MBEDTLS_ERR_MPI_NOT_ACCEPTABLE if the implementation was
576 * unable to find a suitable value within a limited number
577 * of attempts. This has a negligible probability if \p N
578 * is significantly larger than \p min, which is the case
579 * for all usual cryptographic applications.
580 */
581 int mbedtls_mpi_core_random(mbedtls_mpi_uint *X,
582 mbedtls_mpi_uint min,
583 const mbedtls_mpi_uint *N,
584 size_t limbs,
585 int (*f_rng)(void *, unsigned char *, size_t),
586 void *p_rng);
587
588 /**
589 * \brief Returns the number of limbs of working memory required for
590 * a call to `mbedtls_mpi_core_exp_mod()`.
591 *
592 * \note This will always be at least
593 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`,
594 * i.e. sufficient for a call to `mbedtls_mpi_core_montmul()`.
595 *
596 * \param AN_limbs The number of limbs in the input `A` and the modulus `N`
597 * (they must be the same size) that will be given to
598 * `mbedtls_mpi_core_exp_mod()`.
599 * \param E_limbs The number of limbs in the exponent `E` that will be given
600 * to `mbedtls_mpi_core_exp_mod()`.
601 *
602 * \return The number of limbs of working memory required by
603 * `mbedtls_mpi_core_exp_mod()`.
604 */
605 size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs);
606
607 /**
608 * \brief Perform a modular exponentiation with secret exponent:
609 * X = A^E mod N, where \p A is already in Montgomery form.
610 *
611 * \p X may be aliased to \p A, but not to \p RR or \p E, even if \p E_limbs ==
612 * \p AN_limbs.
613 *
614 * \param[out] X The destination MPI, as a little endian array of length
615 * \p AN_limbs.
616 * \param[in] A The base MPI, as a little endian array of length \p AN_limbs.
617 * Must be in Montgomery form.
618 * \param[in] N The modulus, as a little endian array of length \p AN_limbs.
619 * \param AN_limbs The number of limbs in \p X, \p A, \p N, \p RR.
620 * \param[in] E The exponent, as a little endian array of length \p E_limbs.
621 * \param E_limbs The number of limbs in \p E.
622 * \param[in] RR The precomputed residue of 2^{2*biL} modulo N, as a little
623 * endian array of length \p AN_limbs.
624 * \param[in,out] T Temporary storage of at least the number of limbs returned
625 * by `mbedtls_mpi_core_exp_mod_working_limbs()`.
626 * Its initial content is unused and its final content is
627 * indeterminate.
628 * It must not alias or otherwise overlap any of the other
629 * parameters.
630 * It is up to the caller to zeroize \p T when it is no
631 * longer needed, and before freeing it if it was dynamically
632 * allocated.
633 */
634 void mbedtls_mpi_core_exp_mod(mbedtls_mpi_uint *X,
635 const mbedtls_mpi_uint *A,
636 const mbedtls_mpi_uint *N, size_t AN_limbs,
637 const mbedtls_mpi_uint *E, size_t E_limbs,
638 const mbedtls_mpi_uint *RR,
639 mbedtls_mpi_uint *T);
640
641 /**
642 * \brief Subtract unsigned integer from known-size large unsigned integers.
643 * Return the borrow.
644 *
645 * \param[out] X The result of the subtraction.
646 * \param[in] A The left operand.
647 * \param b The unsigned scalar to subtract.
648 * \param limbs Number of limbs of \p X and \p A.
649 *
650 * \return 1 if `A < b`.
651 * 0 if `A >= b`.
652 */
653 mbedtls_mpi_uint mbedtls_mpi_core_sub_int(mbedtls_mpi_uint *X,
654 const mbedtls_mpi_uint *A,
655 mbedtls_mpi_uint b,
656 size_t limbs);
657
658 /**
659 * \brief Determine if a given MPI has the value \c 0 in constant time with
660 * respect to the value (but not with respect to the number of limbs).
661 *
662 * \param[in] A The MPI to test.
663 * \param limbs Number of limbs in \p A.
664 *
665 * \return 0 if `A == 0`
666 * non-0 (may be any value) if `A != 0`.
667 */
668 mbedtls_mpi_uint mbedtls_mpi_core_check_zero_ct(const mbedtls_mpi_uint *A,
669 size_t limbs);
670
671 /**
672 * \brief Returns the number of limbs of working memory required for
673 * a call to `mbedtls_mpi_core_montmul()`.
674 *
675 * \param AN_limbs The number of limbs in the input `A` and the modulus `N`
676 * (they must be the same size) that will be given to
677 * `mbedtls_mpi_core_montmul()` or one of the other functions
678 * that specifies this as the amount of working memory needed.
679 *
680 * \return The number of limbs of working memory required by
681 * `mbedtls_mpi_core_montmul()` (or other similar function).
682 */
mbedtls_mpi_core_montmul_working_limbs(size_t AN_limbs)683 static inline size_t mbedtls_mpi_core_montmul_working_limbs(size_t AN_limbs)
684 {
685 return 2 * AN_limbs + 1;
686 }
687
688 /** Convert an MPI into Montgomery form.
689 *
690 * \p X may be aliased to \p A, but may not otherwise overlap it.
691 *
692 * \p X may not alias \p N (it is in canonical form, so must be strictly less
693 * than \p N). Nor may it alias or overlap \p rr (this is unlikely to be
694 * required in practice.)
695 *
696 * This function is a thin wrapper around `mbedtls_mpi_core_montmul()` that is
697 * an alternative to calling `mbedtls_mpi_mod_raw_to_mont_rep()` when we
698 * don't want to allocate memory.
699 *
700 * \param[out] X The result of the conversion.
701 * Must have the same number of limbs as \p A.
702 * \param[in] A The MPI to convert into Montgomery form.
703 * Must have the same number of limbs as the modulus.
704 * \param[in] N The address of the modulus, which gives the size of
705 * the base `R` = 2^(biL*N->limbs).
706 * \param[in] AN_limbs The number of limbs in \p X, \p A, \p N and \p rr.
707 * \param mm The Montgomery constant for \p N: -N^-1 mod 2^biL.
708 * This can be determined by calling
709 * `mbedtls_mpi_core_montmul_init()`.
710 * \param[in] rr The residue for `2^{2*n*biL} mod N`.
711 * \param[in,out] T Temporary storage of size at least
712 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`
713 * limbs.
714 * Its initial content is unused and
715 * its final content is indeterminate.
716 * It must not alias or otherwise overlap any of the
717 * other parameters.
718 */
719 void mbedtls_mpi_core_to_mont_rep(mbedtls_mpi_uint *X,
720 const mbedtls_mpi_uint *A,
721 const mbedtls_mpi_uint *N,
722 size_t AN_limbs,
723 mbedtls_mpi_uint mm,
724 const mbedtls_mpi_uint *rr,
725 mbedtls_mpi_uint *T);
726
727 /** Convert an MPI from Montgomery form.
728 *
729 * \p X may be aliased to \p A, but may not otherwise overlap it.
730 *
731 * \p X may not alias \p N (it is in canonical form, so must be strictly less
732 * than \p N).
733 *
734 * This function is a thin wrapper around `mbedtls_mpi_core_montmul()` that is
735 * an alternative to calling `mbedtls_mpi_mod_raw_from_mont_rep()` when we
736 * don't want to allocate memory.
737 *
738 * \param[out] X The result of the conversion.
739 * Must have the same number of limbs as \p A.
740 * \param[in] A The MPI to convert from Montgomery form.
741 * Must have the same number of limbs as the modulus.
742 * \param[in] N The address of the modulus, which gives the size of
743 * the base `R` = 2^(biL*N->limbs).
744 * \param[in] AN_limbs The number of limbs in \p X, \p A and \p N.
745 * \param mm The Montgomery constant for \p N: -N^-1 mod 2^biL.
746 * This can be determined by calling
747 * `mbedtls_mpi_core_montmul_init()`.
748 * \param[in,out] T Temporary storage of size at least
749 * `mbedtls_mpi_core_montmul_working_limbs(AN_limbs)`
750 * limbs.
751 * Its initial content is unused and
752 * its final content is indeterminate.
753 * It must not alias or otherwise overlap any of the
754 * other parameters.
755 */
756 void mbedtls_mpi_core_from_mont_rep(mbedtls_mpi_uint *X,
757 const mbedtls_mpi_uint *A,
758 const mbedtls_mpi_uint *N,
759 size_t AN_limbs,
760 mbedtls_mpi_uint mm,
761 mbedtls_mpi_uint *T);
762
763 #endif /* MBEDTLS_BIGNUM_CORE_H */
764
