/src/mbedtls/library/bignum_core.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Core bignum functions |
3 | | * |
4 | | * Copyright The Mbed TLS Contributors |
5 | | * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later |
6 | | */ |
7 | | |
8 | | #include "common.h" |
9 | | |
10 | | #if defined(MBEDTLS_BIGNUM_C) |
11 | | |
12 | | #include <string.h> |
13 | | |
14 | | #include "mbedtls/error.h" |
15 | | #include "mbedtls/platform_util.h" |
16 | | #include "constant_time_internal.h" |
17 | | |
18 | | #include "mbedtls/platform.h" |
19 | | |
20 | | #include "bignum_core.h" |
21 | | #include "bn_mul.h" |
22 | | #include "constant_time_internal.h" |
23 | | |
24 | | size_t mbedtls_mpi_core_clz(mbedtls_mpi_uint a) |
25 | 7.56M | { |
26 | 7.56M | #if defined(__has_builtin) |
27 | | #if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_clz) |
28 | | #define core_clz __builtin_clz |
29 | | #elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_clzl) |
30 | 7.56M | #define core_clz __builtin_clzl |
31 | | #elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_clzll) |
32 | | #define core_clz __builtin_clzll |
33 | | #endif |
34 | 7.56M | #endif |
35 | 7.56M | #if defined(core_clz) |
36 | 7.56M | return (size_t) core_clz(a); |
37 | | #else |
38 | | size_t j; |
39 | | mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1); |
40 | | |
41 | | for (j = 0; j < biL; j++) { |
42 | | if (a & mask) { |
43 | | break; |
44 | | } |
45 | | |
46 | | mask >>= 1; |
47 | | } |
48 | | |
49 | | return j; |
50 | | #endif |
51 | 7.56M | } |
52 | | |
53 | | size_t mbedtls_mpi_core_bitlen(const mbedtls_mpi_uint *A, size_t A_limbs) |
54 | 7.56M | { |
55 | 7.56M | int i; |
56 | 7.56M | size_t j; |
57 | | |
58 | 34.9M | for (i = ((int) A_limbs) - 1; i >= 0; i--) { |
59 | 34.9M | if (A[i] != 0) { |
60 | 7.56M | j = biL - mbedtls_mpi_core_clz(A[i]); |
61 | 7.56M | return (i * biL) + j; |
62 | 7.56M | } |
63 | 34.9M | } |
64 | | |
65 | 2.10k | return 0; |
66 | 7.56M | } |
67 | | |
68 | | static mbedtls_mpi_uint mpi_bigendian_to_host(mbedtls_mpi_uint a) |
69 | 12.0k | { |
70 | 12.0k | if (MBEDTLS_IS_BIG_ENDIAN) { |
71 | | /* Nothing to do on bigendian systems. */ |
72 | 0 | return a; |
73 | 12.0k | } else { |
74 | | #if defined(MBEDTLS_HAVE_INT32) |
75 | | return (mbedtls_mpi_uint) MBEDTLS_BSWAP32(a); |
76 | | #elif defined(MBEDTLS_HAVE_INT64) |
77 | 12.0k | return (mbedtls_mpi_uint) MBEDTLS_BSWAP64(a); |
78 | 12.0k | #endif |
79 | 12.0k | } |
80 | 12.0k | } |
81 | | |
82 | | void mbedtls_mpi_core_bigendian_to_host(mbedtls_mpi_uint *A, |
83 | | size_t A_limbs) |
84 | 2.50k | { |
85 | 2.50k | mbedtls_mpi_uint *cur_limb_left; |
86 | 2.50k | mbedtls_mpi_uint *cur_limb_right; |
87 | 2.50k | if (A_limbs == 0) { |
88 | 0 | return; |
89 | 0 | } |
90 | | |
91 | | /* |
92 | | * Traverse limbs and |
93 | | * - adapt byte-order in each limb |
94 | | * - swap the limbs themselves. |
95 | | * For that, simultaneously traverse the limbs from left to right |
96 | | * and from right to left, as long as the left index is not bigger |
97 | | * than the right index (it's not a problem if limbs is odd and the |
98 | | * indices coincide in the last iteration). |
99 | | */ |
100 | 2.50k | for (cur_limb_left = A, cur_limb_right = A + (A_limbs - 1); |
101 | 8.50k | cur_limb_left <= cur_limb_right; |
102 | 6.00k | cur_limb_left++, cur_limb_right--) { |
103 | 6.00k | mbedtls_mpi_uint tmp; |
104 | | /* Note that if cur_limb_left == cur_limb_right, |
105 | | * this code effectively swaps the bytes only once. */ |
106 | 6.00k | tmp = mpi_bigendian_to_host(*cur_limb_left); |
107 | 6.00k | *cur_limb_left = mpi_bigendian_to_host(*cur_limb_right); |
108 | 6.00k | *cur_limb_right = tmp; |
109 | 6.00k | } |
110 | 2.50k | } |
111 | | |
112 | | /* Whether min <= A, in constant time. |
113 | | * A_limbs must be at least 1. */ |
114 | | mbedtls_ct_condition_t mbedtls_mpi_core_uint_le_mpi(mbedtls_mpi_uint min, |
115 | | const mbedtls_mpi_uint *A, |
116 | | size_t A_limbs) |
117 | 2.02k | { |
118 | | /* min <= least significant limb? */ |
119 | 2.02k | mbedtls_ct_condition_t min_le_lsl = mbedtls_ct_uint_ge(A[0], min); |
120 | | |
121 | | /* limbs other than the least significant one are all zero? */ |
122 | 2.02k | mbedtls_ct_condition_t msll_mask = MBEDTLS_CT_FALSE; |
123 | 10.1k | for (size_t i = 1; i < A_limbs; i++) { |
124 | 8.07k | msll_mask = mbedtls_ct_bool_or(msll_mask, mbedtls_ct_bool(A[i])); |
125 | 8.07k | } |
126 | | |
127 | | /* min <= A iff the lowest limb of A is >= min or the other limbs |
128 | | * are not all zero. */ |
129 | 2.02k | return mbedtls_ct_bool_or(msll_mask, min_le_lsl); |
130 | 2.02k | } |
131 | | |
132 | | mbedtls_ct_condition_t mbedtls_mpi_core_lt_ct(const mbedtls_mpi_uint *A, |
133 | | const mbedtls_mpi_uint *B, |
134 | | size_t limbs) |
135 | 2.04k | { |
136 | 2.04k | mbedtls_ct_condition_t ret = MBEDTLS_CT_FALSE, cond = MBEDTLS_CT_FALSE, done = MBEDTLS_CT_FALSE; |
137 | | |
138 | 12.1k | for (size_t i = limbs; i > 0; i--) { |
139 | | /* |
140 | | * If B[i - 1] < A[i - 1] then A < B is false and the result must |
141 | | * remain 0. |
142 | | * |
143 | | * Again even if we can make a decision, we just mark the result and |
144 | | * the fact that we are done and continue looping. |
145 | | */ |
146 | 10.1k | cond = mbedtls_ct_uint_lt(B[i - 1], A[i - 1]); |
147 | 10.1k | done = mbedtls_ct_bool_or(done, cond); |
148 | | |
149 | | /* |
150 | | * If A[i - 1] < B[i - 1] then A < B is true. |
151 | | * |
152 | | * Again even if we can make a decision, we just mark the result and |
153 | | * the fact that we are done and continue looping. |
154 | | */ |
155 | 10.1k | cond = mbedtls_ct_uint_lt(A[i - 1], B[i - 1]); |
156 | 10.1k | ret = mbedtls_ct_bool_or(ret, mbedtls_ct_bool_and(cond, mbedtls_ct_bool_not(done))); |
157 | 10.1k | done = mbedtls_ct_bool_or(done, cond); |
158 | 10.1k | } |
159 | | |
160 | | /* |
161 | | * If all the limbs were equal, then the numbers are equal, A < B is false |
162 | | * and leaving the result 0 is correct. |
163 | | */ |
164 | | |
165 | 2.04k | return ret; |
166 | 2.04k | } |
167 | | |
168 | | void mbedtls_mpi_core_cond_assign(mbedtls_mpi_uint *X, |
169 | | const mbedtls_mpi_uint *A, |
170 | | size_t limbs, |
171 | | mbedtls_ct_condition_t assign) |
172 | 6.59M | { |
173 | 6.59M | if (X == A) { |
174 | 0 | return; |
175 | 0 | } |
176 | | |
177 | | /* This function is very performance-sensitive for RSA. For this reason |
178 | | * we have the loop below, instead of calling mbedtls_ct_memcpy_if |
179 | | * (this is more optimal since here we don't have to handle the case where |
180 | | * we copy awkwardly sized data). |
181 | | */ |
182 | 156M | for (size_t i = 0; i < limbs; i++) { |
183 | 150M | X[i] = mbedtls_ct_mpi_uint_if(assign, A[i], X[i]); |
184 | 150M | } |
185 | 6.59M | } |
186 | | |
187 | | void mbedtls_mpi_core_cond_swap(mbedtls_mpi_uint *X, |
188 | | mbedtls_mpi_uint *Y, |
189 | | size_t limbs, |
190 | | mbedtls_ct_condition_t swap) |
191 | 25 | { |
192 | 25 | if (X == Y) { |
193 | 0 | return; |
194 | 0 | } |
195 | | |
196 | 577 | for (size_t i = 0; i < limbs; i++) { |
197 | 552 | mbedtls_mpi_uint tmp = X[i]; |
198 | 552 | X[i] = mbedtls_ct_mpi_uint_if(swap, Y[i], X[i]); |
199 | 552 | Y[i] = mbedtls_ct_mpi_uint_if(swap, tmp, Y[i]); |
200 | 552 | } |
201 | 25 | } |
202 | | |
203 | | int mbedtls_mpi_core_read_le(mbedtls_mpi_uint *X, |
204 | | size_t X_limbs, |
205 | | const unsigned char *input, |
206 | | size_t input_length) |
207 | 0 | { |
208 | 0 | const size_t limbs = CHARS_TO_LIMBS(input_length); |
209 | |
|
210 | 0 | if (X_limbs < limbs) { |
211 | 0 | return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; |
212 | 0 | } |
213 | | |
214 | 0 | if (X != NULL) { |
215 | 0 | memset(X, 0, X_limbs * ciL); |
216 | |
|
217 | 0 | for (size_t i = 0; i < input_length; i++) { |
218 | 0 | size_t offset = ((i % ciL) << 3); |
219 | 0 | X[i / ciL] |= ((mbedtls_mpi_uint) input[i]) << offset; |
220 | 0 | } |
221 | 0 | } |
222 | |
|
223 | 0 | return 0; |
224 | 0 | } |
225 | | |
226 | | int mbedtls_mpi_core_read_be(mbedtls_mpi_uint *X, |
227 | | size_t X_limbs, |
228 | | const unsigned char *input, |
229 | | size_t input_length) |
230 | 476 | { |
231 | 476 | const size_t limbs = CHARS_TO_LIMBS(input_length); |
232 | | |
233 | 476 | if (X_limbs < limbs) { |
234 | 0 | return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; |
235 | 0 | } |
236 | | |
237 | | /* If X_limbs is 0, input_length must also be 0 (from previous test). |
238 | | * Nothing to do. */ |
239 | 476 | if (X_limbs == 0) { |
240 | 0 | return 0; |
241 | 0 | } |
242 | | |
243 | 476 | memset(X, 0, X_limbs * ciL); |
244 | | |
245 | | /* memcpy() with (NULL, 0) is undefined behaviour */ |
246 | 476 | if (input_length != 0) { |
247 | 476 | size_t overhead = (X_limbs * ciL) - input_length; |
248 | 476 | unsigned char *Xp = (unsigned char *) X; |
249 | 476 | memcpy(Xp + overhead, input, input_length); |
250 | 476 | } |
251 | | |
252 | 476 | mbedtls_mpi_core_bigendian_to_host(X, X_limbs); |
253 | | |
254 | 476 | return 0; |
255 | 476 | } |
256 | | |
257 | | int mbedtls_mpi_core_write_le(const mbedtls_mpi_uint *A, |
258 | | size_t A_limbs, |
259 | | unsigned char *output, |
260 | | size_t output_length) |
261 | 246 | { |
262 | 246 | size_t stored_bytes = A_limbs * ciL; |
263 | 246 | size_t bytes_to_copy; |
264 | | |
265 | 246 | if (stored_bytes < output_length) { |
266 | 0 | bytes_to_copy = stored_bytes; |
267 | 246 | } else { |
268 | 246 | bytes_to_copy = output_length; |
269 | | |
270 | | /* The output buffer is smaller than the allocated size of A. |
271 | | * However A may fit if its leading bytes are zero. */ |
272 | 1.65k | for (size_t i = bytes_to_copy; i < stored_bytes; i++) { |
273 | 1.50k | if (GET_BYTE(A, i) != 0) { |
274 | 98 | return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; |
275 | 98 | } |
276 | 1.50k | } |
277 | 246 | } |
278 | | |
279 | 920 | for (size_t i = 0; i < bytes_to_copy; i++) { |
280 | 772 | output[i] = GET_BYTE(A, i); |
281 | 772 | } |
282 | | |
283 | 148 | if (stored_bytes < output_length) { |
284 | | /* Write trailing 0 bytes */ |
285 | 0 | memset(output + stored_bytes, 0, output_length - stored_bytes); |
286 | 0 | } |
287 | | |
288 | 148 | return 0; |
289 | 246 | } |
290 | | |
291 | | int mbedtls_mpi_core_write_be(const mbedtls_mpi_uint *X, |
292 | | size_t X_limbs, |
293 | | unsigned char *output, |
294 | | size_t output_length) |
295 | 3.50k | { |
296 | 3.50k | size_t stored_bytes; |
297 | 3.50k | size_t bytes_to_copy; |
298 | 3.50k | unsigned char *p; |
299 | | |
300 | 3.50k | stored_bytes = X_limbs * ciL; |
301 | | |
302 | 3.50k | if (stored_bytes < output_length) { |
303 | | /* There is enough space in the output buffer. Write initial |
304 | | * null bytes and record the position at which to start |
305 | | * writing the significant bytes. In this case, the execution |
306 | | * trace of this function does not depend on the value of the |
307 | | * number. */ |
308 | 3.25k | bytes_to_copy = stored_bytes; |
309 | 3.25k | p = output + output_length - stored_bytes; |
310 | 3.25k | memset(output, 0, output_length - stored_bytes); |
311 | 3.25k | } else { |
312 | | /* The output buffer is smaller than the allocated size of X. |
313 | | * However X may fit if its leading bytes are zero. */ |
314 | 245 | bytes_to_copy = output_length; |
315 | 245 | p = output; |
316 | 551 | for (size_t i = bytes_to_copy; i < stored_bytes; i++) { |
317 | 539 | if (GET_BYTE(X, i) != 0) { |
318 | 233 | return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; |
319 | 233 | } |
320 | 539 | } |
321 | 245 | } |
322 | | |
323 | 902k | for (size_t i = 0; i < bytes_to_copy; i++) { |
324 | 899k | p[bytes_to_copy - i - 1] = GET_BYTE(X, i); |
325 | 899k | } |
326 | | |
327 | 3.26k | return 0; |
328 | 3.50k | } |
329 | | |
330 | | void mbedtls_mpi_core_shift_r(mbedtls_mpi_uint *X, size_t limbs, |
331 | | size_t count) |
332 | 19.7M | { |
333 | 19.7M | size_t i, v0, v1; |
334 | 19.7M | mbedtls_mpi_uint r0 = 0, r1; |
335 | | |
336 | 19.7M | v0 = count / biL; |
337 | 19.7M | v1 = count & (biL - 1); |
338 | | |
339 | 19.7M | if (v0 > limbs || (v0 == limbs && v1 > 0)) { |
340 | 9 | memset(X, 0, limbs * ciL); |
341 | 9 | return; |
342 | 9 | } |
343 | | |
344 | | /* |
345 | | * shift by count / limb_size |
346 | | */ |
347 | 19.7M | if (v0 > 0) { |
348 | 2.72M | for (i = 0; i < limbs - v0; i++) { |
349 | 2.31M | X[i] = X[i + v0]; |
350 | 2.31M | } |
351 | | |
352 | 2.72M | for (; i < limbs; i++) { |
353 | 2.31M | X[i] = 0; |
354 | 2.31M | } |
355 | 415k | } |
356 | | |
357 | | /* |
358 | | * shift by count % limb_size |
359 | | */ |
360 | 19.7M | if (v1 > 0) { |
361 | 851M | for (i = limbs; i > 0; i--) { |
362 | 836M | r1 = X[i - 1] << (biL - v1); |
363 | 836M | X[i - 1] >>= v1; |
364 | 836M | X[i - 1] |= r0; |
365 | 836M | r0 = r1; |
366 | 836M | } |
367 | 15.2M | } |
368 | 19.7M | } |
369 | | |
370 | | void mbedtls_mpi_core_shift_l(mbedtls_mpi_uint *X, size_t limbs, |
371 | | size_t count) |
372 | 4.52M | { |
373 | 4.52M | size_t i, v0, v1; |
374 | 4.52M | mbedtls_mpi_uint r0 = 0, r1; |
375 | | |
376 | 4.52M | v0 = count / (biL); |
377 | 4.52M | v1 = count & (biL - 1); |
378 | | |
379 | | /* |
380 | | * shift by count / limb_size |
381 | | */ |
382 | 4.52M | if (v0 > 0) { |
383 | 29.8M | for (i = limbs; i > v0; i--) { |
384 | 27.5M | X[i - 1] = X[i - v0 - 1]; |
385 | 27.5M | } |
386 | | |
387 | 12.7M | for (; i > 0; i--) { |
388 | 10.4M | X[i - 1] = 0; |
389 | 10.4M | } |
390 | 2.31M | } |
391 | | |
392 | | /* |
393 | | * shift by count % limb_size |
394 | | */ |
395 | 4.52M | if (v1 > 0) { |
396 | 19.3M | for (i = v0; i < limbs; i++) { |
397 | 17.6M | r1 = X[i] >> (biL - v1); |
398 | 17.6M | X[i] <<= v1; |
399 | 17.6M | X[i] |= r0; |
400 | 17.6M | r0 = r1; |
401 | 17.6M | } |
402 | 1.78M | } |
403 | 4.52M | } |
404 | | |
405 | | mbedtls_mpi_uint mbedtls_mpi_core_add(mbedtls_mpi_uint *X, |
406 | | const mbedtls_mpi_uint *A, |
407 | | const mbedtls_mpi_uint *B, |
408 | | size_t limbs) |
409 | 11.4M | { |
410 | 11.4M | mbedtls_mpi_uint c = 0; |
411 | | |
412 | 207M | for (size_t i = 0; i < limbs; i++) { |
413 | 196M | mbedtls_mpi_uint t = c + A[i]; |
414 | 196M | c = (t < A[i]); |
415 | 196M | t += B[i]; |
416 | 196M | c += (t < B[i]); |
417 | 196M | X[i] = t; |
418 | 196M | } |
419 | | |
420 | 11.4M | return c; |
421 | 11.4M | } |
422 | | |
423 | | mbedtls_mpi_uint mbedtls_mpi_core_add_if(mbedtls_mpi_uint *X, |
424 | | const mbedtls_mpi_uint *A, |
425 | | size_t limbs, |
426 | | unsigned cond) |
427 | 0 | { |
428 | 0 | mbedtls_mpi_uint c = 0; |
429 | |
|
430 | 0 | mbedtls_ct_condition_t do_add = mbedtls_ct_bool(cond); |
431 | |
|
432 | 0 | for (size_t i = 0; i < limbs; i++) { |
433 | 0 | mbedtls_mpi_uint add = mbedtls_ct_mpi_uint_if_else_0(do_add, A[i]); |
434 | 0 | mbedtls_mpi_uint t = c + X[i]; |
435 | 0 | c = (t < X[i]); |
436 | 0 | t += add; |
437 | 0 | c += (t < add); |
438 | 0 | X[i] = t; |
439 | 0 | } |
440 | |
|
441 | 0 | return c; |
442 | 0 | } |
443 | | |
444 | | mbedtls_mpi_uint mbedtls_mpi_core_sub(mbedtls_mpi_uint *X, |
445 | | const mbedtls_mpi_uint *A, |
446 | | const mbedtls_mpi_uint *B, |
447 | | size_t limbs) |
448 | 17.1M | { |
449 | 17.1M | mbedtls_mpi_uint c = 0; |
450 | | |
451 | 435M | for (size_t i = 0; i < limbs; i++) { |
452 | 418M | mbedtls_mpi_uint z = (A[i] < c); |
453 | 418M | mbedtls_mpi_uint t = A[i] - c; |
454 | 418M | c = (t < B[i]) + z; |
455 | 418M | X[i] = t - B[i]; |
456 | 418M | } |
457 | | |
458 | 17.1M | return c; |
459 | 17.1M | } |
460 | | |
461 | | mbedtls_mpi_uint mbedtls_mpi_core_mla(mbedtls_mpi_uint *d, size_t d_len, |
462 | | const mbedtls_mpi_uint *s, size_t s_len, |
463 | | mbedtls_mpi_uint b) |
464 | 167M | { |
465 | 167M | mbedtls_mpi_uint c = 0; /* carry */ |
466 | | /* |
467 | | * It is a documented precondition of this function that d_len >= s_len. |
468 | | * If that's not the case, we swap these round: this turns what would be |
469 | | * a buffer overflow into an incorrect result. |
470 | | */ |
471 | 167M | if (d_len < s_len) { |
472 | 0 | s_len = d_len; |
473 | 0 | } |
474 | 167M | size_t excess_len = d_len - s_len; |
475 | 167M | size_t steps_x8 = s_len / 8; |
476 | 167M | size_t steps_x1 = s_len & 7; |
477 | | |
478 | 1.54G | while (steps_x8--) { |
479 | 1.38G | MULADDC_X8_INIT |
480 | 1.38G | MULADDC_X8_CORE |
481 | 1.38G | MULADDC_X8_STOP |
482 | 1.38G | } |
483 | | |
484 | 519M | while (steps_x1--) { |
485 | 352M | MULADDC_X1_INIT |
486 | 352M | MULADDC_X1_CORE |
487 | 352M | MULADDC_X1_STOP |
488 | 352M | } |
489 | | |
490 | 538M | while (excess_len--) { |
491 | 371M | *d += c; |
492 | 371M | c = (*d < c); |
493 | 371M | d++; |
494 | 371M | } |
495 | | |
496 | 167M | return c; |
497 | 167M | } |
498 | | |
499 | | void mbedtls_mpi_core_mul(mbedtls_mpi_uint *X, |
500 | | const mbedtls_mpi_uint *A, size_t A_limbs, |
501 | | const mbedtls_mpi_uint *B, size_t B_limbs) |
502 | 3.21M | { |
503 | 3.21M | memset(X, 0, (A_limbs + B_limbs) * ciL); |
504 | | |
505 | 18.5M | for (size_t i = 0; i < B_limbs; i++) { |
506 | 15.3M | (void) mbedtls_mpi_core_mla(X + i, A_limbs + 1, A, A_limbs, B[i]); |
507 | 15.3M | } |
508 | 3.21M | } |
509 | | |
510 | | /* |
511 | | * Fast Montgomery initialization (thanks to Tom St Denis). |
512 | | */ |
513 | | mbedtls_mpi_uint mbedtls_mpi_core_montmul_init(const mbedtls_mpi_uint *N) |
514 | 3.38k | { |
515 | 3.38k | mbedtls_mpi_uint x = N[0]; |
516 | | |
517 | 3.38k | x += ((N[0] + 2) & 4) << 1; |
518 | | |
519 | 16.9k | for (unsigned int i = biL; i >= 8; i /= 2) { |
520 | 13.5k | x *= (2 - (N[0] * x)); |
521 | 13.5k | } |
522 | | |
523 | 3.38k | return ~x + 1; |
524 | 3.38k | } |
525 | | |
526 | | void mbedtls_mpi_core_montmul(mbedtls_mpi_uint *X, |
527 | | const mbedtls_mpi_uint *A, |
528 | | const mbedtls_mpi_uint *B, |
529 | | size_t B_limbs, |
530 | | const mbedtls_mpi_uint *N, |
531 | | size_t AN_limbs, |
532 | | mbedtls_mpi_uint mm, |
533 | | mbedtls_mpi_uint *T) |
534 | 1.59M | { |
535 | 1.59M | memset(T, 0, (2 * AN_limbs + 1) * ciL); |
536 | | |
537 | 67.7M | for (size_t i = 0; i < AN_limbs; i++) { |
538 | | /* T = (T + u0*B + u1*N) / 2^biL */ |
539 | 66.1M | mbedtls_mpi_uint u0 = A[i]; |
540 | 66.1M | mbedtls_mpi_uint u1 = (T[0] + u0 * B[0]) * mm; |
541 | | |
542 | 66.1M | (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, B, B_limbs, u0); |
543 | 66.1M | (void) mbedtls_mpi_core_mla(T, AN_limbs + 2, N, AN_limbs, u1); |
544 | | |
545 | 66.1M | T++; |
546 | 66.1M | } |
547 | | |
548 | | /* |
549 | | * The result we want is (T >= N) ? T - N : T. |
550 | | * |
551 | | * For better constant-time properties in this function, we always do the |
552 | | * subtraction, with the result in X. |
553 | | * |
554 | | * We also look to see if there was any carry in the final additions in the |
555 | | * loop above. |
556 | | */ |
557 | | |
558 | 1.59M | mbedtls_mpi_uint carry = T[AN_limbs]; |
559 | 1.59M | mbedtls_mpi_uint borrow = mbedtls_mpi_core_sub(X, T, N, AN_limbs); |
560 | | |
561 | | /* |
562 | | * Using R as the Montgomery radix (auxiliary modulus) i.e. 2^(biL*AN_limbs): |
563 | | * |
564 | | * T can be in one of 3 ranges: |
565 | | * |
566 | | * 1) T < N : (carry, borrow) = (0, 1): we want T |
567 | | * 2) N <= T < R : (carry, borrow) = (0, 0): we want X |
568 | | * 3) T >= R : (carry, borrow) = (1, 1): we want X |
569 | | * |
570 | | * and (carry, borrow) = (1, 0) can't happen. |
571 | | * |
572 | | * So the correct return value is already in X if (carry ^ borrow) = 0, |
573 | | * but is in (the lower AN_limbs limbs of) T if (carry ^ borrow) = 1. |
574 | | */ |
575 | 1.59M | mbedtls_ct_memcpy_if(mbedtls_ct_bool(carry ^ borrow), |
576 | 1.59M | (unsigned char *) X, |
577 | 1.59M | (unsigned char *) T, |
578 | 1.59M | NULL, |
579 | 1.59M | AN_limbs * sizeof(mbedtls_mpi_uint)); |
580 | 1.59M | } |
581 | | |
582 | | int mbedtls_mpi_core_get_mont_r2_unsafe(mbedtls_mpi *X, |
583 | | const mbedtls_mpi *N) |
584 | 1.69k | { |
585 | 1.69k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
586 | | |
587 | 1.69k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1)); |
588 | 1.69k | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, N->n * 2 * biL)); |
589 | 1.69k | MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N)); |
590 | 1.69k | MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(X, N->n)); |
591 | | |
592 | 1.69k | cleanup: |
593 | 1.69k | return ret; |
594 | 1.69k | } |
595 | | |
596 | | MBEDTLS_STATIC_TESTABLE |
597 | | void mbedtls_mpi_core_ct_uint_table_lookup(mbedtls_mpi_uint *dest, |
598 | | const mbedtls_mpi_uint *table, |
599 | | size_t limbs, |
600 | | size_t count, |
601 | | size_t index) |
602 | 412k | { |
603 | 3.52M | for (size_t i = 0; i < count; i++, table += limbs) { |
604 | 3.10M | mbedtls_ct_condition_t assign = mbedtls_ct_uint_eq(i, index); |
605 | 3.10M | mbedtls_mpi_core_cond_assign(dest, table, limbs, assign); |
606 | 3.10M | } |
607 | 412k | } |
608 | | |
609 | | /* Fill X with n_bytes random bytes. |
610 | | * X must already have room for those bytes. |
611 | | * The ordering of the bytes returned from the RNG is suitable for |
612 | | * deterministic ECDSA (see RFC 6979 §3.3 and the specification of |
613 | | * mbedtls_mpi_core_random()). |
614 | | */ |
615 | | int mbedtls_mpi_core_fill_random( |
616 | | mbedtls_mpi_uint *X, size_t X_limbs, |
617 | | size_t n_bytes, |
618 | | int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) |
619 | 2.43k | { |
620 | 2.43k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
621 | 2.43k | const size_t limbs = CHARS_TO_LIMBS(n_bytes); |
622 | 2.43k | const size_t overhead = (limbs * ciL) - n_bytes; |
623 | | |
624 | 2.43k | if (X_limbs < limbs) { |
625 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
626 | 0 | } |
627 | | |
628 | 2.43k | memset(X, 0, overhead); |
629 | 2.43k | memset((unsigned char *) X + limbs * ciL, 0, (X_limbs - limbs) * ciL); |
630 | 2.43k | MBEDTLS_MPI_CHK(f_rng(p_rng, (unsigned char *) X + overhead, n_bytes)); |
631 | 2.02k | mbedtls_mpi_core_bigendian_to_host(X, limbs); |
632 | | |
633 | 2.43k | cleanup: |
634 | 2.43k | return ret; |
635 | 2.02k | } |
636 | | |
637 | | int mbedtls_mpi_core_random(mbedtls_mpi_uint *X, |
638 | | mbedtls_mpi_uint min, |
639 | | const mbedtls_mpi_uint *N, |
640 | | size_t limbs, |
641 | | int (*f_rng)(void *, unsigned char *, size_t), |
642 | | void *p_rng) |
643 | 2.26k | { |
644 | 2.26k | mbedtls_ct_condition_t ge_lower = MBEDTLS_CT_TRUE, lt_upper = MBEDTLS_CT_FALSE; |
645 | 2.26k | size_t n_bits = mbedtls_mpi_core_bitlen(N, limbs); |
646 | 2.26k | size_t n_bytes = (n_bits + 7) / 8; |
647 | 2.26k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
648 | | |
649 | | /* |
650 | | * When min == 0, each try has at worst a probability 1/2 of failing |
651 | | * (the msb has a probability 1/2 of being 0, and then the result will |
652 | | * be < N), so after 30 tries failure probability is a most 2**(-30). |
653 | | * |
654 | | * When N is just below a power of 2, as is the case when generating |
655 | | * a random scalar on most elliptic curves, 1 try is enough with |
656 | | * overwhelming probability. When N is just above a power of 2, |
657 | | * as when generating a random scalar on secp224k1, each try has |
658 | | * a probability of failing that is almost 1/2. |
659 | | * |
660 | | * The probabilities are almost the same if min is nonzero but negligible |
661 | | * compared to N. This is always the case when N is crypto-sized, but |
662 | | * it's convenient to support small N for testing purposes. When N |
663 | | * is small, use a higher repeat count, otherwise the probability of |
664 | | * failure is macroscopic. |
665 | | */ |
666 | 2.26k | int count = (n_bytes > 4 ? 30 : 250); |
667 | | |
668 | | /* |
669 | | * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA) |
670 | | * when f_rng is a suitably parametrized instance of HMAC_DRBG: |
671 | | * - use the same byte ordering; |
672 | | * - keep the leftmost n_bits bits of the generated octet string; |
673 | | * - try until result is in the desired range. |
674 | | * This also avoids any bias, which is especially important for ECDSA. |
675 | | */ |
676 | 2.43k | do { |
677 | 2.43k | MBEDTLS_MPI_CHK(mbedtls_mpi_core_fill_random(X, limbs, |
678 | 2.43k | n_bytes, |
679 | 2.43k | f_rng, p_rng)); |
680 | 2.02k | mbedtls_mpi_core_shift_r(X, limbs, 8 * n_bytes - n_bits); |
681 | | |
682 | 2.02k | if (--count == 0) { |
683 | 0 | ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
684 | 0 | goto cleanup; |
685 | 0 | } |
686 | | |
687 | 2.02k | ge_lower = mbedtls_mpi_core_uint_le_mpi(min, X, limbs); |
688 | 2.02k | lt_upper = mbedtls_mpi_core_lt_ct(X, N, limbs); |
689 | 2.02k | } while (mbedtls_ct_bool_and(ge_lower, lt_upper) == MBEDTLS_CT_FALSE); |
690 | | |
691 | 2.26k | cleanup: |
692 | 2.26k | return ret; |
693 | 2.26k | } |
694 | | |
695 | | static size_t exp_mod_get_window_size(size_t Ebits) |
696 | 3.38k | { |
697 | | #if MBEDTLS_MPI_WINDOW_SIZE >= 6 |
698 | | return (Ebits > 671) ? 6 : (Ebits > 239) ? 5 : (Ebits > 79) ? 4 : 1; |
699 | | #elif MBEDTLS_MPI_WINDOW_SIZE == 5 |
700 | | return (Ebits > 239) ? 5 : (Ebits > 79) ? 4 : 1; |
701 | | #elif MBEDTLS_MPI_WINDOW_SIZE > 1 |
702 | 3.38k | return (Ebits > 79) ? MBEDTLS_MPI_WINDOW_SIZE : 1; |
703 | | #else |
704 | | (void) Ebits; |
705 | | return 1; |
706 | | #endif |
707 | 3.38k | } |
708 | | |
709 | | size_t mbedtls_mpi_core_exp_mod_working_limbs(size_t AN_limbs, size_t E_limbs) |
710 | 1.69k | { |
711 | 1.69k | const size_t wsize = exp_mod_get_window_size(E_limbs * biL); |
712 | 1.69k | const size_t welem = ((size_t) 1) << wsize; |
713 | | |
714 | | /* How big does each part of the working memory pool need to be? */ |
715 | 1.69k | const size_t table_limbs = welem * AN_limbs; |
716 | 1.69k | const size_t select_limbs = AN_limbs; |
717 | 1.69k | const size_t temp_limbs = 2 * AN_limbs + 1; |
718 | | |
719 | 1.69k | return table_limbs + select_limbs + temp_limbs; |
720 | 1.69k | } |
721 | | |
722 | | static void exp_mod_precompute_window(const mbedtls_mpi_uint *A, |
723 | | const mbedtls_mpi_uint *N, |
724 | | size_t AN_limbs, |
725 | | mbedtls_mpi_uint mm, |
726 | | const mbedtls_mpi_uint *RR, |
727 | | size_t welem, |
728 | | mbedtls_mpi_uint *Wtable, |
729 | | mbedtls_mpi_uint *temp) |
730 | 1.69k | { |
731 | | /* W[0] = 1 (in Montgomery presentation) */ |
732 | 1.69k | memset(Wtable, 0, AN_limbs * ciL); |
733 | 1.69k | Wtable[0] = 1; |
734 | 1.69k | mbedtls_mpi_core_montmul(Wtable, Wtable, RR, AN_limbs, N, AN_limbs, mm, temp); |
735 | | |
736 | | /* W[1] = A (already in Montgomery presentation) */ |
737 | 1.69k | mbedtls_mpi_uint *W1 = Wtable + AN_limbs; |
738 | 1.69k | memcpy(W1, A, AN_limbs * ciL); |
739 | | |
740 | | /* W[i+1] = W[i] * W[1], i >= 2 */ |
741 | 1.69k | mbedtls_mpi_uint *Wprev = W1; |
742 | 8.90k | for (size_t i = 2; i < welem; i++) { |
743 | 7.21k | mbedtls_mpi_uint *Wcur = Wprev + AN_limbs; |
744 | 7.21k | mbedtls_mpi_core_montmul(Wcur, Wprev, W1, AN_limbs, N, AN_limbs, mm, temp); |
745 | 7.21k | Wprev = Wcur; |
746 | 7.21k | } |
747 | 1.69k | } |
748 | | |
749 | | #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C) |
750 | | void (*mbedtls_safe_codepath_hook)(void) = NULL; |
751 | | void (*mbedtls_unsafe_codepath_hook)(void) = NULL; |
752 | | #endif |
753 | | |
754 | | /* |
755 | | * This function calculates the indices of the exponent where the exponentiation algorithm should |
756 | | * start processing. |
757 | | * |
758 | | * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value, |
759 | | * this function is not constant time with respect to the exponent (parameter E). |
760 | | */ |
761 | | static inline void exp_mod_calc_first_bit_optionally_safe(const mbedtls_mpi_uint *E, |
762 | | size_t E_limbs, |
763 | | int E_public, |
764 | | size_t *E_limb_index, |
765 | | size_t *E_bit_index) |
766 | 1.69k | { |
767 | 1.69k | if (E_public == MBEDTLS_MPI_IS_PUBLIC) { |
768 | | /* |
769 | | * Skip leading zero bits. |
770 | | */ |
771 | 0 | size_t E_bits = mbedtls_mpi_core_bitlen(E, E_limbs); |
772 | 0 | if (E_bits == 0) { |
773 | | /* |
774 | | * If E is 0 mbedtls_mpi_core_bitlen() returns 0. Even if that is the case, we will want |
775 | | * to represent it as a single 0 bit and as such the bitlength will be 1. |
776 | | */ |
777 | 0 | E_bits = 1; |
778 | 0 | } |
779 | |
|
780 | 0 | *E_limb_index = E_bits / biL; |
781 | 0 | *E_bit_index = E_bits % biL; |
782 | |
|
783 | | #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C) |
784 | | if (mbedtls_unsafe_codepath_hook != NULL) { |
785 | | mbedtls_unsafe_codepath_hook(); |
786 | | } |
787 | | #endif |
788 | 1.69k | } else { |
789 | | /* |
790 | | * Here we need to be constant time with respect to E and can't do anything better than |
791 | | * start at the first allocated bit. |
792 | | */ |
793 | 1.69k | *E_limb_index = E_limbs; |
794 | 1.69k | *E_bit_index = 0; |
795 | | #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C) |
796 | | if (mbedtls_safe_codepath_hook != NULL) { |
797 | | mbedtls_safe_codepath_hook(); |
798 | | } |
799 | | #endif |
800 | 1.69k | } |
801 | 1.69k | } |
802 | | |
803 | | /* |
804 | | * Warning! If the parameter window_public has MBEDTLS_MPI_IS_PUBLIC as its value, this function is |
805 | | * not constant time with respect to the window parameter and consequently the exponent of the |
806 | | * exponentiation (parameter E of mbedtls_mpi_core_exp_mod_optionally_safe). |
807 | | */ |
808 | | static inline void exp_mod_table_lookup_optionally_safe(mbedtls_mpi_uint *Wselect, |
809 | | mbedtls_mpi_uint *Wtable, |
810 | | size_t AN_limbs, size_t welem, |
811 | | mbedtls_mpi_uint window, |
812 | | int window_public) |
813 | 412k | { |
814 | 412k | if (window_public == MBEDTLS_MPI_IS_PUBLIC) { |
815 | 0 | memcpy(Wselect, Wtable + window * AN_limbs, AN_limbs * ciL); |
816 | | #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C) |
817 | | if (mbedtls_unsafe_codepath_hook != NULL) { |
818 | | mbedtls_unsafe_codepath_hook(); |
819 | | } |
820 | | #endif |
821 | 412k | } else { |
822 | | /* Select Wtable[window] without leaking window through |
823 | | * memory access patterns. */ |
824 | 412k | mbedtls_mpi_core_ct_uint_table_lookup(Wselect, Wtable, |
825 | 412k | AN_limbs, welem, window); |
826 | | #if defined(MBEDTLS_TEST_HOOKS) && !defined(MBEDTLS_THREADING_C) |
827 | | if (mbedtls_safe_codepath_hook != NULL) { |
828 | | mbedtls_safe_codepath_hook(); |
829 | | } |
830 | | #endif |
831 | 412k | } |
832 | 412k | } |
833 | | |
834 | | /* Exponentiation: X := A^E mod N. |
835 | | * |
836 | | * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value, |
837 | | * this function is not constant time with respect to the exponent (parameter E). |
838 | | * |
839 | | * A must already be in Montgomery form. |
840 | | * |
841 | | * As in other bignum functions, assume that AN_limbs and E_limbs are nonzero. |
842 | | * |
843 | | * RR must contain 2^{2*biL} mod N. |
844 | | * |
845 | | * The algorithm is a variant of Left-to-right k-ary exponentiation: HAC 14.82 |
846 | | * (The difference is that the body in our loop processes a single bit instead |
847 | | * of a full window.) |
848 | | */ |
849 | | static void mbedtls_mpi_core_exp_mod_optionally_safe(mbedtls_mpi_uint *X, |
850 | | const mbedtls_mpi_uint *A, |
851 | | const mbedtls_mpi_uint *N, |
852 | | size_t AN_limbs, |
853 | | const mbedtls_mpi_uint *E, |
854 | | size_t E_limbs, |
855 | | int E_public, |
856 | | const mbedtls_mpi_uint *RR, |
857 | | mbedtls_mpi_uint *T) |
858 | 1.69k | { |
859 | | /* We'll process the bits of E from most significant |
860 | | * (limb_index=E_limbs-1, E_bit_index=biL-1) to least significant |
861 | | * (limb_index=0, E_bit_index=0). */ |
862 | 1.69k | size_t E_limb_index = E_limbs; |
863 | 1.69k | size_t E_bit_index = 0; |
864 | 1.69k | exp_mod_calc_first_bit_optionally_safe(E, E_limbs, E_public, |
865 | 1.69k | &E_limb_index, &E_bit_index); |
866 | | |
867 | 1.69k | const size_t wsize = exp_mod_get_window_size(E_limb_index * biL); |
868 | 1.69k | const size_t welem = ((size_t) 1) << wsize; |
869 | | |
870 | | /* This is how we will use the temporary storage T, which must have space |
871 | | * for table_limbs, select_limbs and (2 * AN_limbs + 1) for montmul. */ |
872 | 1.69k | const size_t table_limbs = welem * AN_limbs; |
873 | 1.69k | const size_t select_limbs = AN_limbs; |
874 | | |
875 | | /* Pointers to specific parts of the temporary working memory pool */ |
876 | 1.69k | mbedtls_mpi_uint *const Wtable = T; |
877 | 1.69k | mbedtls_mpi_uint *const Wselect = Wtable + table_limbs; |
878 | 1.69k | mbedtls_mpi_uint *const temp = Wselect + select_limbs; |
879 | | |
880 | | /* |
881 | | * Window precomputation |
882 | | */ |
883 | | |
884 | 1.69k | const mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N); |
885 | | |
886 | | /* Set Wtable[i] = A^i (in Montgomery representation) */ |
887 | 1.69k | exp_mod_precompute_window(A, N, AN_limbs, |
888 | 1.69k | mm, RR, |
889 | 1.69k | welem, Wtable, temp); |
890 | | |
891 | | /* |
892 | | * Fixed window exponentiation |
893 | | */ |
894 | | |
895 | | /* X = 1 (in Montgomery presentation) initially */ |
896 | 1.69k | memcpy(X, Wtable, AN_limbs * ciL); |
897 | | |
898 | | /* At any given time, window contains window_bits bits from E. |
899 | | * window_bits can go up to wsize. */ |
900 | 1.69k | size_t window_bits = 0; |
901 | 1.69k | mbedtls_mpi_uint window = 0; |
902 | | |
903 | 1.17M | do { |
904 | | /* Square */ |
905 | 1.17M | mbedtls_mpi_core_montmul(X, X, X, AN_limbs, N, AN_limbs, mm, temp); |
906 | | |
907 | | /* Move to the next bit of the exponent */ |
908 | 1.17M | if (E_bit_index == 0) { |
909 | 18.3k | --E_limb_index; |
910 | 18.3k | E_bit_index = biL - 1; |
911 | 1.15M | } else { |
912 | 1.15M | --E_bit_index; |
913 | 1.15M | } |
914 | | /* Insert next exponent bit into window */ |
915 | 1.17M | ++window_bits; |
916 | 1.17M | window <<= 1; |
917 | 1.17M | window |= (E[E_limb_index] >> E_bit_index) & 1; |
918 | | |
919 | | /* Clear window if it's full. Also clear the window at the end, |
920 | | * when we've finished processing the exponent. */ |
921 | 1.17M | if (window_bits == wsize || |
922 | 1.17M | (E_bit_index == 0 && E_limb_index == 0)) { |
923 | | |
924 | 412k | exp_mod_table_lookup_optionally_safe(Wselect, Wtable, AN_limbs, welem, |
925 | 412k | window, E_public); |
926 | | /* Multiply X by the selected element. */ |
927 | 412k | mbedtls_mpi_core_montmul(X, X, Wselect, AN_limbs, N, AN_limbs, mm, |
928 | 412k | temp); |
929 | 412k | window = 0; |
930 | 412k | window_bits = 0; |
931 | 412k | } |
932 | 1.17M | } while (!(E_bit_index == 0 && E_limb_index == 0)); |
933 | 1.69k | } |
934 | | |
935 | | void mbedtls_mpi_core_exp_mod(mbedtls_mpi_uint *X, |
936 | | const mbedtls_mpi_uint *A, |
937 | | const mbedtls_mpi_uint *N, size_t AN_limbs, |
938 | | const mbedtls_mpi_uint *E, size_t E_limbs, |
939 | | const mbedtls_mpi_uint *RR, |
940 | | mbedtls_mpi_uint *T) |
941 | 1.69k | { |
942 | 1.69k | mbedtls_mpi_core_exp_mod_optionally_safe(X, |
943 | 1.69k | A, |
944 | 1.69k | N, |
945 | 1.69k | AN_limbs, |
946 | 1.69k | E, |
947 | 1.69k | E_limbs, |
948 | 1.69k | MBEDTLS_MPI_IS_SECRET, |
949 | 1.69k | RR, |
950 | 1.69k | T); |
951 | 1.69k | } |
952 | | |
953 | | void mbedtls_mpi_core_exp_mod_unsafe(mbedtls_mpi_uint *X, |
954 | | const mbedtls_mpi_uint *A, |
955 | | const mbedtls_mpi_uint *N, size_t AN_limbs, |
956 | | const mbedtls_mpi_uint *E, size_t E_limbs, |
957 | | const mbedtls_mpi_uint *RR, |
958 | | mbedtls_mpi_uint *T) |
959 | 0 | { |
960 | 0 | mbedtls_mpi_core_exp_mod_optionally_safe(X, |
961 | 0 | A, |
962 | 0 | N, |
963 | 0 | AN_limbs, |
964 | 0 | E, |
965 | 0 | E_limbs, |
966 | 0 | MBEDTLS_MPI_IS_PUBLIC, |
967 | 0 | RR, |
968 | 0 | T); |
969 | 0 | } |
970 | | |
971 | | mbedtls_mpi_uint mbedtls_mpi_core_sub_int(mbedtls_mpi_uint *X, |
972 | | const mbedtls_mpi_uint *A, |
973 | | mbedtls_mpi_uint c, /* doubles as carry */ |
974 | | size_t limbs) |
975 | 2.04M | { |
976 | 16.6M | for (size_t i = 0; i < limbs; i++) { |
977 | 14.6M | mbedtls_mpi_uint s = A[i]; |
978 | 14.6M | mbedtls_mpi_uint t = s - c; |
979 | 14.6M | c = (t > s); |
980 | 14.6M | X[i] = t; |
981 | 14.6M | } |
982 | | |
983 | 2.04M | return c; |
984 | 2.04M | } |
985 | | |
986 | | mbedtls_ct_condition_t mbedtls_mpi_core_check_zero_ct(const mbedtls_mpi_uint *A, |
987 | | size_t limbs) |
988 | 0 | { |
989 | 0 | volatile const mbedtls_mpi_uint *force_read_A = A; |
990 | 0 | mbedtls_mpi_uint bits = 0; |
991 | |
|
992 | 0 | for (size_t i = 0; i < limbs; i++) { |
993 | 0 | bits |= force_read_A[i]; |
994 | 0 | } |
995 | |
|
996 | 0 | return mbedtls_ct_bool(bits); |
997 | 0 | } |
998 | | |
999 | | void mbedtls_mpi_core_to_mont_rep(mbedtls_mpi_uint *X, |
1000 | | const mbedtls_mpi_uint *A, |
1001 | | const mbedtls_mpi_uint *N, |
1002 | | size_t AN_limbs, |
1003 | | mbedtls_mpi_uint mm, |
1004 | | const mbedtls_mpi_uint *rr, |
1005 | | mbedtls_mpi_uint *T) |
1006 | 1.69k | { |
1007 | 1.69k | mbedtls_mpi_core_montmul(X, A, rr, AN_limbs, N, AN_limbs, mm, T); |
1008 | 1.69k | } |
1009 | | |
1010 | | void mbedtls_mpi_core_from_mont_rep(mbedtls_mpi_uint *X, |
1011 | | const mbedtls_mpi_uint *A, |
1012 | | const mbedtls_mpi_uint *N, |
1013 | | size_t AN_limbs, |
1014 | | mbedtls_mpi_uint mm, |
1015 | | mbedtls_mpi_uint *T) |
1016 | 1.69k | { |
1017 | 1.69k | const mbedtls_mpi_uint Rinv = 1; /* 1/R in Mont. rep => 1 */ |
1018 | | |
1019 | 1.69k | mbedtls_mpi_core_montmul(X, A, &Rinv, 1, N, AN_limbs, mm, T); |
1020 | 1.69k | } |
1021 | | |
1022 | | #endif /* MBEDTLS_BIGNUM_C */ |