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