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