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