/src/mbedtls/library/bignum.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Multi-precision integer library |
3 | | * |
4 | | * Copyright The Mbed TLS Contributors |
5 | | * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later |
6 | | */ |
7 | | |
8 | | /* |
9 | | * The following sources were referenced in the design of this Multi-precision |
10 | | * Integer library: |
11 | | * |
12 | | * [1] Handbook of Applied Cryptography - 1997 |
13 | | * Menezes, van Oorschot and Vanstone |
14 | | * |
15 | | * [2] Multi-Precision Math |
16 | | * Tom St Denis |
17 | | * https://github.com/libtom/libtommath/blob/develop/tommath.pdf |
18 | | * |
19 | | * [3] GNU Multi-Precision Arithmetic Library |
20 | | * https://gmplib.org/manual/index.html |
21 | | * |
22 | | */ |
23 | | |
24 | | #include "common.h" |
25 | | |
26 | | #if defined(MBEDTLS_BIGNUM_C) |
27 | | |
28 | | #include "mbedtls/bignum.h" |
29 | | #include "bignum_core.h" |
30 | | #include "bignum_internal.h" |
31 | | #include "bn_mul.h" |
32 | | #include "mbedtls/platform_util.h" |
33 | | #include "mbedtls/error.h" |
34 | | #include "constant_time_internal.h" |
35 | | |
36 | | #include <limits.h> |
37 | | #include <string.h> |
38 | | |
39 | | #include "mbedtls/platform.h" |
40 | | |
41 | | |
42 | | |
43 | | /* |
44 | | * Conditionally select an MPI sign in constant time. |
45 | | * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid |
46 | | * values.) |
47 | | */ |
48 | | static inline signed short mbedtls_ct_mpi_sign_if(mbedtls_ct_condition_t cond, |
49 | | signed short sign1, signed short sign2) |
50 | 3.48M | { |
51 | 3.48M | return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1; |
52 | 3.48M | } |
53 | | |
54 | | /* |
55 | | * Compare signed values in constant time |
56 | | */ |
57 | | int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X, |
58 | | const mbedtls_mpi *Y, |
59 | | unsigned *ret) |
60 | 30 | { |
61 | 30 | mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result; |
62 | | |
63 | 30 | if (X->n != Y->n) { |
64 | 14 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
65 | 14 | } |
66 | | |
67 | | /* |
68 | | * Set N_is_negative to MBEDTLS_CT_FALSE if N >= 0, MBEDTLS_CT_TRUE if N < 0. |
69 | | * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0. |
70 | | */ |
71 | 16 | X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1); |
72 | 16 | Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1); |
73 | | |
74 | | /* |
75 | | * If the signs are different, then the positive operand is the bigger. |
76 | | * That is if X is negative (X_is_negative == 1), then X < Y is true and it |
77 | | * is false if X is positive (X_is_negative == 0). |
78 | | */ |
79 | 16 | different_sign = mbedtls_ct_bool_ne(X_is_negative, Y_is_negative); // true if different sign |
80 | 16 | result = mbedtls_ct_bool_and(different_sign, X_is_negative); |
81 | | |
82 | | /* |
83 | | * Assuming signs are the same, compare X and Y. We switch the comparison |
84 | | * order if they are negative so that we get the right result, regardles of |
85 | | * sign. |
86 | | */ |
87 | | |
88 | | /* This array is used to conditionally swap the pointers in const time */ |
89 | 16 | void * const p[2] = { X->p, Y->p }; |
90 | 16 | size_t i = mbedtls_ct_size_if_else_0(X_is_negative, 1); |
91 | 16 | mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n); |
92 | | |
93 | | /* |
94 | | * Store in result iff the signs are the same (i.e., iff different_sign == false). If |
95 | | * the signs differ, result has already been set, so we don't change it. |
96 | | */ |
97 | 16 | result = mbedtls_ct_bool_or(result, |
98 | 16 | mbedtls_ct_bool_and(mbedtls_ct_bool_not(different_sign), lt)); |
99 | | |
100 | 16 | *ret = mbedtls_ct_uint_if_else_0(result, 1); |
101 | | |
102 | 16 | return 0; |
103 | 30 | } |
104 | | |
105 | | /* |
106 | | * Conditionally assign X = Y, without leaking information |
107 | | * about whether the assignment was made or not. |
108 | | * (Leaking information about the respective sizes of X and Y is ok however.) |
109 | | */ |
110 | | #if defined(_MSC_VER) && defined(MBEDTLS_PLATFORM_IS_WINDOWS_ON_ARM64) && \ |
111 | | (_MSC_FULL_VER < 193131103) |
112 | | /* |
113 | | * MSVC miscompiles this function if it's inlined prior to Visual Studio 2022 version 17.1. See: |
114 | | * https://developercommunity.visualstudio.com/t/c-compiler-miscompiles-part-of-mbedtls-library-on/1646989 |
115 | | */ |
116 | | __declspec(noinline) |
117 | | #endif |
118 | | int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X, |
119 | | const mbedtls_mpi *Y, |
120 | | unsigned char assign) |
121 | 3.48M | { |
122 | 3.48M | int ret = 0; |
123 | | |
124 | 3.48M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n)); |
125 | | |
126 | 3.48M | { |
127 | 3.48M | mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign); |
128 | | |
129 | 3.48M | X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s); |
130 | | |
131 | 3.48M | mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign); |
132 | | |
133 | 3.48M | mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign); |
134 | 3.49M | for (size_t i = Y->n; i < X->n; i++) { |
135 | 8.76k | X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]); |
136 | 8.76k | } |
137 | 3.48M | } |
138 | | |
139 | 3.48M | cleanup: |
140 | 3.48M | return ret; |
141 | 3.48M | } |
142 | | |
143 | | /* |
144 | | * Conditionally swap X and Y, without leaking information |
145 | | * about whether the swap was made or not. |
146 | | * Here it is not ok to simply swap the pointers, which would lead to |
147 | | * different memory access patterns when X and Y are used afterwards. |
148 | | */ |
149 | | int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X, |
150 | | mbedtls_mpi *Y, |
151 | | unsigned char swap) |
152 | 25 | { |
153 | 25 | int ret = 0; |
154 | 25 | int s; |
155 | | |
156 | 25 | if (X == Y) { |
157 | 0 | return 0; |
158 | 0 | } |
159 | | |
160 | 25 | mbedtls_ct_condition_t do_swap = mbedtls_ct_bool(swap); |
161 | | |
162 | 25 | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n)); |
163 | 25 | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n)); |
164 | | |
165 | 25 | s = X->s; |
166 | 25 | X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s); |
167 | 25 | Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s); |
168 | | |
169 | 25 | mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap); |
170 | | |
171 | 25 | cleanup: |
172 | 25 | return ret; |
173 | 25 | } |
174 | | |
175 | | /* Implementation that should never be optimized out by the compiler */ |
176 | 5.81M | #define mbedtls_mpi_zeroize_and_free(v, n) mbedtls_zeroize_and_free(v, ciL * (n)) |
177 | | |
178 | | /* |
179 | | * Initialize one MPI |
180 | | */ |
181 | | void mbedtls_mpi_init(mbedtls_mpi *X) |
182 | 8.54M | { |
183 | 8.54M | X->s = 1; |
184 | 8.54M | X->n = 0; |
185 | 8.54M | X->p = NULL; |
186 | 8.54M | } |
187 | | |
188 | | /* |
189 | | * Unallocate one MPI |
190 | | */ |
191 | | void mbedtls_mpi_free(mbedtls_mpi *X) |
192 | 8.55M | { |
193 | 8.55M | if (X == NULL) { |
194 | 0 | return; |
195 | 0 | } |
196 | | |
197 | 8.55M | if (X->p != NULL) { |
198 | 3.20M | mbedtls_mpi_zeroize_and_free(X->p, X->n); |
199 | 3.20M | } |
200 | | |
201 | 8.55M | X->s = 1; |
202 | 8.55M | X->n = 0; |
203 | 8.55M | X->p = NULL; |
204 | 8.55M | } |
205 | | |
206 | | /* |
207 | | * Enlarge to the specified number of limbs |
208 | | */ |
209 | | int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs) |
210 | 67.4M | { |
211 | 67.4M | mbedtls_mpi_uint *p; |
212 | | |
213 | 67.4M | if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) { |
214 | 0 | return MBEDTLS_ERR_MPI_ALLOC_FAILED; |
215 | 0 | } |
216 | | |
217 | 67.4M | if (X->n < nblimbs) { |
218 | 5.80M | if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL)) == NULL) { |
219 | 0 | return MBEDTLS_ERR_MPI_ALLOC_FAILED; |
220 | 0 | } |
221 | | |
222 | 5.80M | if (X->p != NULL) { |
223 | 2.59M | memcpy(p, X->p, X->n * ciL); |
224 | 2.59M | mbedtls_mpi_zeroize_and_free(X->p, X->n); |
225 | 2.59M | } |
226 | | |
227 | | /* nblimbs fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS |
228 | | * fits, and we've checked that nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */ |
229 | 5.80M | X->n = (unsigned short) nblimbs; |
230 | 5.80M | X->p = p; |
231 | 5.80M | } |
232 | | |
233 | 67.4M | return 0; |
234 | 67.4M | } |
235 | | |
236 | | /* |
237 | | * Resize down as much as possible, |
238 | | * while keeping at least the specified number of limbs |
239 | | */ |
240 | | int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs) |
241 | 11.9k | { |
242 | 11.9k | mbedtls_mpi_uint *p; |
243 | 11.9k | size_t i; |
244 | | |
245 | 11.9k | if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) { |
246 | 0 | return MBEDTLS_ERR_MPI_ALLOC_FAILED; |
247 | 0 | } |
248 | | |
249 | | /* Actually resize up if there are currently fewer than nblimbs limbs. */ |
250 | 11.9k | if (X->n <= nblimbs) { |
251 | 0 | return mbedtls_mpi_grow(X, nblimbs); |
252 | 0 | } |
253 | | /* After this point, then X->n > nblimbs and in particular X->n > 0. */ |
254 | | |
255 | 106k | for (i = X->n - 1; i > 0; i--) { |
256 | 106k | if (X->p[i] != 0) { |
257 | 11.6k | break; |
258 | 11.6k | } |
259 | 106k | } |
260 | 11.9k | i++; |
261 | | |
262 | 11.9k | if (i < nblimbs) { |
263 | 252 | i = nblimbs; |
264 | 252 | } |
265 | | |
266 | 11.9k | if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL) { |
267 | 0 | return MBEDTLS_ERR_MPI_ALLOC_FAILED; |
268 | 0 | } |
269 | | |
270 | 11.9k | if (X->p != NULL) { |
271 | 11.9k | memcpy(p, X->p, i * ciL); |
272 | 11.9k | mbedtls_mpi_zeroize_and_free(X->p, X->n); |
273 | 11.9k | } |
274 | | |
275 | | /* i fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS |
276 | | * fits, and we've checked that i <= nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */ |
277 | 11.9k | X->n = (unsigned short) i; |
278 | 11.9k | X->p = p; |
279 | | |
280 | 11.9k | return 0; |
281 | 11.9k | } |
282 | | |
283 | | /* Resize X to have exactly n limbs and set it to 0. */ |
284 | | static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs) |
285 | 2.74k | { |
286 | 2.74k | if (limbs == 0) { |
287 | 0 | mbedtls_mpi_free(X); |
288 | 0 | return 0; |
289 | 2.74k | } else if (X->n == limbs) { |
290 | 0 | memset(X->p, 0, limbs * ciL); |
291 | 0 | X->s = 1; |
292 | 0 | return 0; |
293 | 2.74k | } else { |
294 | 2.74k | mbedtls_mpi_free(X); |
295 | 2.74k | return mbedtls_mpi_grow(X, limbs); |
296 | 2.74k | } |
297 | 2.74k | } |
298 | | |
299 | | /* |
300 | | * Copy the contents of Y into X. |
301 | | * |
302 | | * This function is not constant-time. Leading zeros in Y may be removed. |
303 | | * |
304 | | * Ensure that X does not shrink. This is not guaranteed by the public API, |
305 | | * but some code in the bignum module might still rely on this property. |
306 | | */ |
307 | | int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y) |
308 | 36.7M | { |
309 | 36.7M | int ret = 0; |
310 | 36.7M | size_t i; |
311 | | |
312 | 36.7M | if (X == Y) { |
313 | 3.30M | return 0; |
314 | 3.30M | } |
315 | | |
316 | 33.4M | if (Y->n == 0) { |
317 | 0 | if (X->n != 0) { |
318 | 0 | X->s = 1; |
319 | 0 | memset(X->p, 0, X->n * ciL); |
320 | 0 | } |
321 | 0 | return 0; |
322 | 0 | } |
323 | | |
324 | 79.9M | for (i = Y->n - 1; i > 0; i--) { |
325 | 77.7M | if (Y->p[i] != 0) { |
326 | 31.2M | break; |
327 | 31.2M | } |
328 | 77.7M | } |
329 | 33.4M | i++; |
330 | | |
331 | 33.4M | X->s = Y->s; |
332 | | |
333 | 33.4M | if (X->n < i) { |
334 | 2.76M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i)); |
335 | 30.7M | } else { |
336 | 30.7M | memset(X->p + i, 0, (X->n - i) * ciL); |
337 | 30.7M | } |
338 | | |
339 | 33.4M | memcpy(X->p, Y->p, i * ciL); |
340 | | |
341 | 33.4M | cleanup: |
342 | | |
343 | 33.4M | return ret; |
344 | 33.4M | } |
345 | | |
346 | | /* |
347 | | * Swap the contents of X and Y |
348 | | */ |
349 | | void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y) |
350 | 15 | { |
351 | 15 | mbedtls_mpi T; |
352 | | |
353 | 15 | memcpy(&T, X, sizeof(mbedtls_mpi)); |
354 | 15 | memcpy(X, Y, sizeof(mbedtls_mpi)); |
355 | 15 | memcpy(Y, &T, sizeof(mbedtls_mpi)); |
356 | 15 | } |
357 | | |
358 | | static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z) |
359 | 31.7M | { |
360 | 31.7M | if (z >= 0) { |
361 | 31.7M | return z; |
362 | 31.7M | } |
363 | | /* Take care to handle the most negative value (-2^(biL-1)) correctly. |
364 | | * A naive -z would have undefined behavior. |
365 | | * Write this in a way that makes popular compilers happy (GCC, Clang, |
366 | | * MSVC). */ |
367 | 836 | return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z; |
368 | 31.7M | } |
369 | | |
370 | | /* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative. |
371 | | * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */ |
372 | 31.7M | #define TO_SIGN(x) ((mbedtls_mpi_sint) (((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1) |
373 | | |
374 | | /* |
375 | | * Set value from integer |
376 | | */ |
377 | | int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z) |
378 | 7.23M | { |
379 | 7.23M | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
380 | | |
381 | 7.23M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1)); |
382 | 7.23M | memset(X->p, 0, X->n * ciL); |
383 | | |
384 | 7.23M | X->p[0] = mpi_sint_abs(z); |
385 | 7.23M | X->s = TO_SIGN(z); |
386 | | |
387 | 7.23M | cleanup: |
388 | | |
389 | 7.23M | return ret; |
390 | 7.23M | } |
391 | | |
392 | | /* |
393 | | * Get a specific bit |
394 | | */ |
395 | | int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos) |
396 | 551k | { |
397 | 551k | if (X->n * biL <= pos) { |
398 | 2.54k | return 0; |
399 | 2.54k | } |
400 | | |
401 | 549k | return (X->p[pos / biL] >> (pos % biL)) & 0x01; |
402 | 551k | } |
403 | | |
404 | | /* |
405 | | * Set a bit to a specific value of 0 or 1 |
406 | | */ |
407 | | int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val) |
408 | 55 | { |
409 | 55 | int ret = 0; |
410 | 55 | size_t off = pos / biL; |
411 | 55 | size_t idx = pos % biL; |
412 | | |
413 | 55 | if (val != 0 && val != 1) { |
414 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
415 | 0 | } |
416 | | |
417 | 55 | if (X->n * biL <= pos) { |
418 | 30 | if (val == 0) { |
419 | 1 | return 0; |
420 | 1 | } |
421 | | |
422 | 29 | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1)); |
423 | 29 | } |
424 | | |
425 | 54 | X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx); |
426 | 54 | X->p[off] |= (mbedtls_mpi_uint) val << idx; |
427 | | |
428 | 54 | cleanup: |
429 | | |
430 | 54 | return ret; |
431 | 54 | } |
432 | | |
433 | | /* |
434 | | * Return the number of less significant zero-bits |
435 | | */ |
436 | | size_t mbedtls_mpi_lsb(const mbedtls_mpi *X) |
437 | 5.41M | { |
438 | 5.41M | size_t i; |
439 | | |
440 | 5.41M | #if defined(__has_builtin) |
441 | | #if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz) |
442 | | #define mbedtls_mpi_uint_ctz __builtin_ctz |
443 | | #elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl) |
444 | 5.41M | #define mbedtls_mpi_uint_ctz __builtin_ctzl |
445 | | #elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll) |
446 | | #define mbedtls_mpi_uint_ctz __builtin_ctzll |
447 | | #endif |
448 | 5.41M | #endif |
449 | | |
450 | 5.41M | #if defined(mbedtls_mpi_uint_ctz) |
451 | 5.41M | for (i = 0; i < X->n; i++) { |
452 | 5.41M | if (X->p[i] != 0) { |
453 | 5.41M | return i * biL + mbedtls_mpi_uint_ctz(X->p[i]); |
454 | 5.41M | } |
455 | 5.41M | } |
456 | | #else |
457 | | size_t count = 0; |
458 | | for (i = 0; i < X->n; i++) { |
459 | | for (size_t j = 0; j < biL; j++, count++) { |
460 | | if (((X->p[i] >> j) & 1) != 0) { |
461 | | return count; |
462 | | } |
463 | | } |
464 | | } |
465 | | #endif |
466 | | |
467 | 19 | return 0; |
468 | 5.41M | } |
469 | | |
470 | | /* |
471 | | * Return the number of bits |
472 | | */ |
473 | | size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X) |
474 | 7.56M | { |
475 | 7.56M | return mbedtls_mpi_core_bitlen(X->p, X->n); |
476 | 7.56M | } |
477 | | |
478 | | /* |
479 | | * Return the total size in bytes |
480 | | */ |
481 | | size_t mbedtls_mpi_size(const mbedtls_mpi *X) |
482 | 0 | { |
483 | 0 | return (mbedtls_mpi_bitlen(X) + 7) >> 3; |
484 | 0 | } |
485 | | |
486 | | /* |
487 | | * Convert an ASCII character to digit value |
488 | | */ |
489 | | static int mpi_get_digit(mbedtls_mpi_uint *d, int radix, char c) |
490 | 13.8M | { |
491 | 13.8M | *d = 255; |
492 | | |
493 | 13.8M | if (c >= 0x30 && c <= 0x39) { |
494 | 13.8M | *d = c - 0x30; |
495 | 13.8M | } |
496 | 13.8M | if (c >= 0x41 && c <= 0x46) { |
497 | 0 | *d = c - 0x37; |
498 | 0 | } |
499 | 13.8M | if (c >= 0x61 && c <= 0x66) { |
500 | 0 | *d = c - 0x57; |
501 | 0 | } |
502 | | |
503 | 13.8M | if (*d >= (mbedtls_mpi_uint) radix) { |
504 | 0 | return MBEDTLS_ERR_MPI_INVALID_CHARACTER; |
505 | 0 | } |
506 | | |
507 | 13.8M | return 0; |
508 | 13.8M | } |
509 | | |
510 | | /* |
511 | | * Import from an ASCII string |
512 | | */ |
513 | | int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s) |
514 | 72.3k | { |
515 | 72.3k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
516 | 72.3k | size_t i, j, slen, n; |
517 | 72.3k | int sign = 1; |
518 | 72.3k | mbedtls_mpi_uint d; |
519 | 72.3k | mbedtls_mpi T; |
520 | | |
521 | 72.3k | if (radix < 2 || radix > 16) { |
522 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
523 | 0 | } |
524 | | |
525 | 72.3k | mbedtls_mpi_init(&T); |
526 | | |
527 | 72.3k | if (s[0] == 0) { |
528 | 0 | mbedtls_mpi_free(X); |
529 | 0 | return 0; |
530 | 0 | } |
531 | | |
532 | 72.3k | if (s[0] == '-') { |
533 | 32 | ++s; |
534 | 32 | sign = -1; |
535 | 32 | } |
536 | | |
537 | 72.3k | slen = strlen(s); |
538 | | |
539 | 72.3k | if (radix == 16) { |
540 | 0 | if (slen > SIZE_MAX >> 2) { |
541 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
542 | 0 | } |
543 | | |
544 | 0 | n = BITS_TO_LIMBS(slen << 2); |
545 | |
|
546 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n)); |
547 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); |
548 | | |
549 | 0 | for (i = slen, j = 0; i > 0; i--, j++) { |
550 | 0 | MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1])); |
551 | 0 | X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2); |
552 | 0 | } |
553 | 72.3k | } else { |
554 | 72.3k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); |
555 | | |
556 | 13.8M | for (i = 0; i < slen; i++) { |
557 | 13.8M | MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i])); |
558 | 13.8M | MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix)); |
559 | 13.8M | MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d)); |
560 | 13.8M | } |
561 | 72.3k | } |
562 | | |
563 | 72.3k | if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) { |
564 | 32 | X->s = -1; |
565 | 32 | } |
566 | | |
567 | 72.3k | cleanup: |
568 | | |
569 | 72.3k | mbedtls_mpi_free(&T); |
570 | | |
571 | 72.3k | return ret; |
572 | 72.3k | } |
573 | | |
574 | | /* |
575 | | * Helper to write the digits high-order first. |
576 | | */ |
577 | | static int mpi_write_hlp(mbedtls_mpi *X, int radix, |
578 | | char **p, const size_t buflen) |
579 | 1.46k | { |
580 | 1.46k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
581 | 1.46k | mbedtls_mpi_uint r; |
582 | 1.46k | size_t length = 0; |
583 | 1.46k | char *p_end = *p + buflen; |
584 | | |
585 | 136k | do { |
586 | 136k | if (length >= buflen) { |
587 | 0 | return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; |
588 | 0 | } |
589 | | |
590 | 136k | MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix)); |
591 | 136k | MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix)); |
592 | | /* |
593 | | * Write the residue in the current position, as an ASCII character. |
594 | | */ |
595 | 136k | if (r < 0xA) { |
596 | 136k | *(--p_end) = (char) ('0' + r); |
597 | 136k | } else { |
598 | 0 | *(--p_end) = (char) ('A' + (r - 0xA)); |
599 | 0 | } |
600 | | |
601 | 136k | length++; |
602 | 136k | } while (mbedtls_mpi_cmp_int(X, 0) != 0); |
603 | | |
604 | 1.46k | memmove(*p, p_end, length); |
605 | 1.46k | *p += length; |
606 | | |
607 | 1.46k | cleanup: |
608 | | |
609 | 1.46k | return ret; |
610 | 1.46k | } |
611 | | |
612 | | /* |
613 | | * Export into an ASCII string |
614 | | */ |
615 | | int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix, |
616 | | char *buf, size_t buflen, size_t *olen) |
617 | 12.9k | { |
618 | 12.9k | int ret = 0; |
619 | 12.9k | size_t n; |
620 | 12.9k | char *p; |
621 | 12.9k | mbedtls_mpi T; |
622 | | |
623 | 12.9k | if (radix < 2 || radix > 16) { |
624 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
625 | 0 | } |
626 | | |
627 | 12.9k | n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */ |
628 | 12.9k | if (radix >= 4) { |
629 | 12.9k | n >>= 1; /* Number of 4-adic digits necessary to present |
630 | | * `n`. If radix > 4, this might be a strict |
631 | | * overapproximation of the number of |
632 | | * radix-adic digits needed to present `n`. */ |
633 | 12.9k | } |
634 | 12.9k | if (radix >= 16) { |
635 | 9.98k | n >>= 1; /* Number of hexadecimal digits necessary to |
636 | | * present `n`. */ |
637 | | |
638 | 9.98k | } |
639 | 12.9k | n += 1; /* Terminating null byte */ |
640 | 12.9k | n += 1; /* Compensate for the divisions above, which round down `n` |
641 | | * in case it's not even. */ |
642 | 12.9k | n += 1; /* Potential '-'-sign. */ |
643 | 12.9k | n += (n & 1); /* Make n even to have enough space for hexadecimal writing, |
644 | | * which always uses an even number of hex-digits. */ |
645 | | |
646 | 12.9k | if (buflen < n) { |
647 | 6.45k | *olen = n; |
648 | 6.45k | return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; |
649 | 6.45k | } |
650 | | |
651 | 6.45k | p = buf; |
652 | 6.45k | mbedtls_mpi_init(&T); |
653 | | |
654 | 6.45k | if (X->s == -1) { |
655 | 165 | *p++ = '-'; |
656 | 165 | buflen--; |
657 | 165 | } |
658 | | |
659 | 6.45k | if (radix == 16) { |
660 | 4.99k | int c; |
661 | 4.99k | size_t i, j, k; |
662 | | |
663 | 108k | for (i = X->n, k = 0; i > 0; i--) { |
664 | 927k | for (j = ciL; j > 0; j--) { |
665 | 824k | c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF; |
666 | | |
667 | 824k | if (c == 0 && k == 0 && (i + j) != 2) { |
668 | 147k | continue; |
669 | 147k | } |
670 | | |
671 | 677k | *(p++) = "0123456789ABCDEF" [c / 16]; |
672 | 677k | *(p++) = "0123456789ABCDEF" [c % 16]; |
673 | 677k | k = 1; |
674 | 677k | } |
675 | 103k | } |
676 | 4.99k | } else { |
677 | 1.46k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X)); |
678 | | |
679 | 1.46k | if (T.s == -1) { |
680 | 0 | T.s = 1; |
681 | 0 | } |
682 | | |
683 | 1.46k | MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen)); |
684 | 1.46k | } |
685 | | |
686 | 6.45k | *p++ = '\0'; |
687 | 6.45k | *olen = (size_t) (p - buf); |
688 | | |
689 | 6.45k | cleanup: |
690 | | |
691 | 6.45k | mbedtls_mpi_free(&T); |
692 | | |
693 | 6.45k | return ret; |
694 | 6.45k | } |
695 | | |
696 | | #if defined(MBEDTLS_FS_IO) |
697 | | /* |
698 | | * Read X from an opened file |
699 | | */ |
700 | | int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin) |
701 | 0 | { |
702 | 0 | mbedtls_mpi_uint d; |
703 | 0 | size_t slen; |
704 | 0 | char *p; |
705 | | /* |
706 | | * Buffer should have space for (short) label and decimal formatted MPI, |
707 | | * newline characters and '\0' |
708 | | */ |
709 | 0 | char s[MBEDTLS_MPI_RW_BUFFER_SIZE]; |
710 | |
|
711 | 0 | if (radix < 2 || radix > 16) { |
712 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
713 | 0 | } |
714 | | |
715 | 0 | memset(s, 0, sizeof(s)); |
716 | 0 | if (fgets(s, sizeof(s) - 1, fin) == NULL) { |
717 | 0 | return MBEDTLS_ERR_MPI_FILE_IO_ERROR; |
718 | 0 | } |
719 | | |
720 | 0 | slen = strlen(s); |
721 | 0 | if (slen == sizeof(s) - 2) { |
722 | 0 | return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL; |
723 | 0 | } |
724 | | |
725 | 0 | if (slen > 0 && s[slen - 1] == '\n') { |
726 | 0 | slen--; s[slen] = '\0'; |
727 | 0 | } |
728 | 0 | if (slen > 0 && s[slen - 1] == '\r') { |
729 | 0 | slen--; s[slen] = '\0'; |
730 | 0 | } |
731 | |
|
732 | 0 | p = s + slen; |
733 | 0 | while (p-- > s) { |
734 | 0 | if (mpi_get_digit(&d, radix, *p) != 0) { |
735 | 0 | break; |
736 | 0 | } |
737 | 0 | } |
738 | |
|
739 | 0 | return mbedtls_mpi_read_string(X, radix, p + 1); |
740 | 0 | } |
741 | | |
742 | | /* |
743 | | * Write X into an opened file (or stdout if fout == NULL) |
744 | | */ |
745 | | int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout) |
746 | 0 | { |
747 | 0 | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
748 | 0 | size_t n, slen, plen; |
749 | | /* |
750 | | * Buffer should have space for (short) label and decimal formatted MPI, |
751 | | * newline characters and '\0' |
752 | | */ |
753 | 0 | char s[MBEDTLS_MPI_RW_BUFFER_SIZE]; |
754 | |
|
755 | 0 | if (radix < 2 || radix > 16) { |
756 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
757 | 0 | } |
758 | | |
759 | 0 | memset(s, 0, sizeof(s)); |
760 | |
|
761 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n)); |
762 | | |
763 | 0 | if (p == NULL) { |
764 | 0 | p = ""; |
765 | 0 | } |
766 | |
|
767 | 0 | plen = strlen(p); |
768 | 0 | slen = strlen(s); |
769 | 0 | s[slen++] = '\r'; |
770 | 0 | s[slen++] = '\n'; |
771 | |
|
772 | 0 | if (fout != NULL) { |
773 | 0 | if (fwrite(p, 1, plen, fout) != plen || |
774 | 0 | fwrite(s, 1, slen, fout) != slen) { |
775 | 0 | return MBEDTLS_ERR_MPI_FILE_IO_ERROR; |
776 | 0 | } |
777 | 0 | } else { |
778 | 0 | mbedtls_printf("%s%s", p, s); |
779 | 0 | } |
780 | | |
781 | 0 | cleanup: |
782 | |
|
783 | 0 | return ret; |
784 | 0 | } |
785 | | #endif /* MBEDTLS_FS_IO */ |
786 | | |
787 | | /* |
788 | | * Import X from unsigned binary data, little endian |
789 | | * |
790 | | * This function is guaranteed to return an MPI with exactly the necessary |
791 | | * number of limbs (in particular, it does not skip 0s in the input). |
792 | | */ |
793 | | int mbedtls_mpi_read_binary_le(mbedtls_mpi *X, |
794 | | const unsigned char *buf, size_t buflen) |
795 | 0 | { |
796 | 0 | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
797 | 0 | const size_t limbs = CHARS_TO_LIMBS(buflen); |
798 | | |
799 | | /* Ensure that target MPI has exactly the necessary number of limbs */ |
800 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); |
801 | | |
802 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen)); |
803 | | |
804 | 0 | cleanup: |
805 | | |
806 | | /* |
807 | | * This function is also used to import keys. However, wiping the buffers |
808 | | * upon failure is not necessary because failure only can happen before any |
809 | | * input is copied. |
810 | | */ |
811 | 0 | return ret; |
812 | 0 | } |
813 | | |
814 | | /* |
815 | | * Import X from unsigned binary data, big endian |
816 | | * |
817 | | * This function is guaranteed to return an MPI with exactly the necessary |
818 | | * number of limbs (in particular, it does not skip 0s in the input). |
819 | | */ |
820 | | int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen) |
821 | 476 | { |
822 | 476 | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
823 | 476 | const size_t limbs = CHARS_TO_LIMBS(buflen); |
824 | | |
825 | | /* Ensure that target MPI has exactly the necessary number of limbs */ |
826 | 476 | MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); |
827 | | |
828 | 476 | MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen)); |
829 | | |
830 | 476 | cleanup: |
831 | | |
832 | | /* |
833 | | * This function is also used to import keys. However, wiping the buffers |
834 | | * upon failure is not necessary because failure only can happen before any |
835 | | * input is copied. |
836 | | */ |
837 | 476 | return ret; |
838 | 476 | } |
839 | | |
840 | | /* |
841 | | * Export X into unsigned binary data, little endian |
842 | | */ |
843 | | int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X, |
844 | | unsigned char *buf, size_t buflen) |
845 | 246 | { |
846 | 246 | return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen); |
847 | 246 | } |
848 | | |
849 | | /* |
850 | | * Export X into unsigned binary data, big endian |
851 | | */ |
852 | | int mbedtls_mpi_write_binary(const mbedtls_mpi *X, |
853 | | unsigned char *buf, size_t buflen) |
854 | 3.50k | { |
855 | 3.50k | return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen); |
856 | 3.50k | } |
857 | | |
858 | | /* |
859 | | * Left-shift: X <<= count |
860 | | */ |
861 | | int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count) |
862 | 4.52M | { |
863 | 4.52M | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
864 | 4.52M | size_t i; |
865 | | |
866 | 4.52M | i = mbedtls_mpi_bitlen(X) + count; |
867 | | |
868 | 4.52M | if (X->n * biL < i) { |
869 | 1.10M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i))); |
870 | 1.10M | } |
871 | | |
872 | 4.52M | ret = 0; |
873 | | |
874 | 4.52M | mbedtls_mpi_core_shift_l(X->p, X->n, count); |
875 | 4.52M | cleanup: |
876 | | |
877 | 4.52M | return ret; |
878 | 4.52M | } |
879 | | |
880 | | /* |
881 | | * Right-shift: X >>= count |
882 | | */ |
883 | | int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count) |
884 | 19.7M | { |
885 | 19.7M | if (X->n != 0) { |
886 | 19.7M | mbedtls_mpi_core_shift_r(X->p, X->n, count); |
887 | 19.7M | } |
888 | 19.7M | return 0; |
889 | 19.7M | } |
890 | | |
891 | | /* |
892 | | * Compare unsigned values |
893 | | */ |
894 | | int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y) |
895 | 11.4M | { |
896 | 11.4M | size_t i, j; |
897 | | |
898 | 86.9M | for (i = X->n; i > 0; i--) { |
899 | 86.9M | if (X->p[i - 1] != 0) { |
900 | 11.4M | break; |
901 | 11.4M | } |
902 | 86.9M | } |
903 | | |
904 | 77.0M | for (j = Y->n; j > 0; j--) { |
905 | 77.0M | if (Y->p[j - 1] != 0) { |
906 | 11.4M | break; |
907 | 11.4M | } |
908 | 77.0M | } |
909 | | |
910 | | /* If i == j == 0, i.e. abs(X) == abs(Y), |
911 | | * we end up returning 0 at the end of the function. */ |
912 | | |
913 | 11.4M | if (i > j) { |
914 | 1.18M | return 1; |
915 | 1.18M | } |
916 | 10.2M | if (j > i) { |
917 | 118k | return -1; |
918 | 118k | } |
919 | | |
920 | 12.7M | for (; i > 0; i--) { |
921 | 12.7M | if (X->p[i - 1] > Y->p[i - 1]) { |
922 | 5.76M | return 1; |
923 | 5.76M | } |
924 | 6.94M | if (X->p[i - 1] < Y->p[i - 1]) { |
925 | 4.31M | return -1; |
926 | 4.31M | } |
927 | 6.94M | } |
928 | | |
929 | 62.3k | return 0; |
930 | 10.1M | } |
931 | | |
932 | | /* |
933 | | * Compare signed values |
934 | | */ |
935 | | int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y) |
936 | 24.8M | { |
937 | 24.8M | size_t i, j; |
938 | | |
939 | 348M | for (i = X->n; i > 0; i--) { |
940 | 348M | if (X->p[i - 1] != 0) { |
941 | 24.8M | break; |
942 | 24.8M | } |
943 | 348M | } |
944 | | |
945 | 168M | for (j = Y->n; j > 0; j--) { |
946 | 158M | if (Y->p[j - 1] != 0) { |
947 | 14.4M | break; |
948 | 14.4M | } |
949 | 158M | } |
950 | | |
951 | 24.8M | if (i == 0 && j == 0) { |
952 | 40.7k | return 0; |
953 | 40.7k | } |
954 | | |
955 | 24.8M | if (i > j) { |
956 | 12.2M | return X->s; |
957 | 12.2M | } |
958 | 12.6M | if (j > i) { |
959 | 730k | return -Y->s; |
960 | 730k | } |
961 | | |
962 | 11.8M | if (X->s > 0 && Y->s < 0) { |
963 | 36 | return 1; |
964 | 36 | } |
965 | 11.8M | if (Y->s > 0 && X->s < 0) { |
966 | 0 | return -1; |
967 | 0 | } |
968 | | |
969 | 14.8M | for (; i > 0; i--) { |
970 | 14.7M | if (X->p[i - 1] > Y->p[i - 1]) { |
971 | 2.99M | return X->s; |
972 | 2.99M | } |
973 | 11.7M | if (X->p[i - 1] < Y->p[i - 1]) { |
974 | 8.75M | return -X->s; |
975 | 8.75M | } |
976 | 11.7M | } |
977 | | |
978 | 135k | return 0; |
979 | 11.8M | } |
980 | | |
981 | | /* |
982 | | * Compare signed values |
983 | | */ |
984 | | int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z) |
985 | 10.5M | { |
986 | 10.5M | mbedtls_mpi Y; |
987 | 10.5M | mbedtls_mpi_uint p[1]; |
988 | | |
989 | 10.5M | *p = mpi_sint_abs(z); |
990 | 10.5M | Y.s = TO_SIGN(z); |
991 | 10.5M | Y.n = 1; |
992 | 10.5M | Y.p = p; |
993 | | |
994 | 10.5M | return mbedtls_mpi_cmp_mpi(X, &Y); |
995 | 10.5M | } |
996 | | |
997 | | /* |
998 | | * Unsigned addition: X = |A| + |B| (HAC 14.7) |
999 | | */ |
1000 | | int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) |
1001 | 18.1M | { |
1002 | 18.1M | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1003 | 18.1M | size_t j; |
1004 | 18.1M | mbedtls_mpi_uint *p; |
1005 | 18.1M | mbedtls_mpi_uint c; |
1006 | | |
1007 | 18.1M | if (X == B) { |
1008 | 0 | const mbedtls_mpi *T = A; A = X; B = T; |
1009 | 0 | } |
1010 | | |
1011 | 18.1M | if (X != A) { |
1012 | 13.9M | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); |
1013 | 13.9M | } |
1014 | | |
1015 | | /* |
1016 | | * X must always be positive as a result of unsigned additions. |
1017 | | */ |
1018 | 18.1M | X->s = 1; |
1019 | | |
1020 | 27.3M | for (j = B->n; j > 0; j--) { |
1021 | 20.6M | if (B->p[j - 1] != 0) { |
1022 | 11.4M | break; |
1023 | 11.4M | } |
1024 | 20.6M | } |
1025 | | |
1026 | | /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0 |
1027 | | * and B is 0 (of any size). */ |
1028 | 18.1M | if (j == 0) { |
1029 | 6.72M | return 0; |
1030 | 6.72M | } |
1031 | | |
1032 | 11.4M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j)); |
1033 | | |
1034 | | /* j is the number of non-zero limbs of B. Add those to X. */ |
1035 | | |
1036 | 11.4M | p = X->p; |
1037 | | |
1038 | 11.4M | c = mbedtls_mpi_core_add(p, p, B->p, j); |
1039 | | |
1040 | 11.4M | p += j; |
1041 | | |
1042 | | /* Now propagate any carry */ |
1043 | | |
1044 | 12.1M | while (c != 0) { |
1045 | 699k | if (j >= X->n) { |
1046 | 5.71k | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1)); |
1047 | 5.71k | p = X->p + j; |
1048 | 5.71k | } |
1049 | | |
1050 | 699k | *p += c; c = (*p < c); j++; p++; |
1051 | 699k | } |
1052 | | |
1053 | 11.4M | cleanup: |
1054 | | |
1055 | 11.4M | return ret; |
1056 | 11.4M | } |
1057 | | |
1058 | | /* |
1059 | | * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10) |
1060 | | */ |
1061 | | int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) |
1062 | 15.5M | { |
1063 | 15.5M | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1064 | 15.5M | size_t n; |
1065 | 15.5M | mbedtls_mpi_uint carry; |
1066 | | |
1067 | 158M | for (n = B->n; n > 0; n--) { |
1068 | 158M | if (B->p[n - 1] != 0) { |
1069 | 15.5M | break; |
1070 | 15.5M | } |
1071 | 158M | } |
1072 | 15.5M | if (n > A->n) { |
1073 | | /* B >= (2^ciL)^n > A */ |
1074 | 29 | ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; |
1075 | 29 | goto cleanup; |
1076 | 29 | } |
1077 | | |
1078 | 15.5M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n)); |
1079 | | |
1080 | | /* Set the high limbs of X to match A. Don't touch the lower limbs |
1081 | | * because X might be aliased to B, and we must not overwrite the |
1082 | | * significant digits of B. */ |
1083 | 15.5M | if (A->n > n && A != X) { |
1084 | 1.36M | memcpy(X->p + n, A->p + n, (A->n - n) * ciL); |
1085 | 1.36M | } |
1086 | 15.5M | if (X->n > A->n) { |
1087 | 1.86M | memset(X->p + A->n, 0, (X->n - A->n) * ciL); |
1088 | 1.86M | } |
1089 | | |
1090 | 15.5M | carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n); |
1091 | 15.5M | if (carry != 0) { |
1092 | | /* Propagate the carry through the rest of X. */ |
1093 | 2.04M | carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n); |
1094 | | |
1095 | | /* If we have further carry/borrow, the result is negative. */ |
1096 | 2.04M | if (carry != 0) { |
1097 | 8 | ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE; |
1098 | 8 | goto cleanup; |
1099 | 8 | } |
1100 | 2.04M | } |
1101 | | |
1102 | | /* X should always be positive as a result of unsigned subtractions. */ |
1103 | 15.5M | X->s = 1; |
1104 | | |
1105 | 15.5M | cleanup: |
1106 | 15.5M | return ret; |
1107 | 15.5M | } |
1108 | | |
1109 | | /* Common function for signed addition and subtraction. |
1110 | | * Calculate A + B * flip_B where flip_B is 1 or -1. |
1111 | | */ |
1112 | | static int add_sub_mpi(mbedtls_mpi *X, |
1113 | | const mbedtls_mpi *A, const mbedtls_mpi *B, |
1114 | | int flip_B) |
1115 | 28.6M | { |
1116 | 28.6M | int ret, s; |
1117 | | |
1118 | 28.6M | s = A->s; |
1119 | 28.6M | if (A->s * B->s * flip_B < 0) { |
1120 | 11.0M | int cmp = mbedtls_mpi_cmp_abs(A, B); |
1121 | 11.0M | if (cmp >= 0) { |
1122 | 6.59M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B)); |
1123 | | /* If |A| = |B|, the result is 0 and we must set the sign bit |
1124 | | * to +1 regardless of which of A or B was negative. Otherwise, |
1125 | | * since |A| > |B|, the sign is the sign of A. */ |
1126 | 6.59M | X->s = cmp == 0 ? 1 : s; |
1127 | 6.59M | } else { |
1128 | 4.43M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A)); |
1129 | | /* Since |A| < |B|, the sign is the opposite of A. */ |
1130 | 4.43M | X->s = -s; |
1131 | 4.43M | } |
1132 | 17.6M | } else { |
1133 | 17.6M | MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B)); |
1134 | 17.6M | X->s = s; |
1135 | 17.6M | } |
1136 | | |
1137 | 28.6M | cleanup: |
1138 | | |
1139 | 28.6M | return ret; |
1140 | 28.6M | } |
1141 | | |
1142 | | /* |
1143 | | * Signed addition: X = A + B |
1144 | | */ |
1145 | | int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) |
1146 | 17.5M | { |
1147 | 17.5M | return add_sub_mpi(X, A, B, 1); |
1148 | 17.5M | } |
1149 | | |
1150 | | /* |
1151 | | * Signed subtraction: X = A - B |
1152 | | */ |
1153 | | int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) |
1154 | 11.1M | { |
1155 | 11.1M | return add_sub_mpi(X, A, B, -1); |
1156 | 11.1M | } |
1157 | | |
1158 | | /* |
1159 | | * Signed addition: X = A + b |
1160 | | */ |
1161 | | int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) |
1162 | 13.8M | { |
1163 | 13.8M | mbedtls_mpi B; |
1164 | 13.8M | mbedtls_mpi_uint p[1]; |
1165 | | |
1166 | 13.8M | p[0] = mpi_sint_abs(b); |
1167 | 13.8M | B.s = TO_SIGN(b); |
1168 | 13.8M | B.n = 1; |
1169 | 13.8M | B.p = p; |
1170 | | |
1171 | 13.8M | return mbedtls_mpi_add_mpi(X, A, &B); |
1172 | 13.8M | } |
1173 | | |
1174 | | /* |
1175 | | * Signed subtraction: X = A - b |
1176 | | */ |
1177 | | int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b) |
1178 | 2.26k | { |
1179 | 2.26k | mbedtls_mpi B; |
1180 | 2.26k | mbedtls_mpi_uint p[1]; |
1181 | | |
1182 | 2.26k | p[0] = mpi_sint_abs(b); |
1183 | 2.26k | B.s = TO_SIGN(b); |
1184 | 2.26k | B.n = 1; |
1185 | 2.26k | B.p = p; |
1186 | | |
1187 | 2.26k | return mbedtls_mpi_sub_mpi(X, A, &B); |
1188 | 2.26k | } |
1189 | | |
1190 | | /* |
1191 | | * Baseline multiplication: X = A * B (HAC 14.12) |
1192 | | */ |
1193 | | int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B) |
1194 | 3.21M | { |
1195 | 3.21M | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1196 | 3.21M | size_t i, j; |
1197 | 3.21M | mbedtls_mpi TA, TB; |
1198 | 3.21M | int result_is_zero = 0; |
1199 | | |
1200 | 3.21M | mbedtls_mpi_init(&TA); |
1201 | 3.21M | mbedtls_mpi_init(&TB); |
1202 | | |
1203 | 3.21M | if (X == A) { |
1204 | 1.17M | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA; |
1205 | 1.17M | } |
1206 | 3.21M | if (X == B) { |
1207 | 8.42k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB; |
1208 | 8.42k | } |
1209 | | |
1210 | 11.7M | for (i = A->n; i > 0; i--) { |
1211 | 11.7M | if (A->p[i - 1] != 0) { |
1212 | 3.21M | break; |
1213 | 3.21M | } |
1214 | 11.7M | } |
1215 | 3.21M | if (i == 0) { |
1216 | 2.55k | result_is_zero = 1; |
1217 | 2.55k | } |
1218 | | |
1219 | 15.3M | for (j = B->n; j > 0; j--) { |
1220 | 15.3M | if (B->p[j - 1] != 0) { |
1221 | 3.21M | break; |
1222 | 3.21M | } |
1223 | 15.3M | } |
1224 | 3.21M | if (j == 0) { |
1225 | 273 | result_is_zero = 1; |
1226 | 273 | } |
1227 | | |
1228 | 3.21M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j)); |
1229 | 3.21M | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0)); |
1230 | | |
1231 | 3.21M | mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j); |
1232 | | |
1233 | | /* If the result is 0, we don't shortcut the operation, which reduces |
1234 | | * but does not eliminate side channels leaking the zero-ness. We do |
1235 | | * need to take care to set the sign bit properly since the library does |
1236 | | * not fully support an MPI object with a value of 0 and s == -1. */ |
1237 | 3.21M | if (result_is_zero) { |
1238 | 2.62k | X->s = 1; |
1239 | 3.21M | } else { |
1240 | 3.21M | X->s = A->s * B->s; |
1241 | 3.21M | } |
1242 | | |
1243 | 3.21M | cleanup: |
1244 | | |
1245 | 3.21M | mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA); |
1246 | | |
1247 | 3.21M | return ret; |
1248 | 3.21M | } |
1249 | | |
1250 | | /* |
1251 | | * Baseline multiplication: X = A * b |
1252 | | */ |
1253 | | int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b) |
1254 | 19.6M | { |
1255 | 19.6M | size_t n = A->n; |
1256 | 93.5M | while (n > 0 && A->p[n - 1] == 0) { |
1257 | 73.9M | --n; |
1258 | 73.9M | } |
1259 | | |
1260 | | /* The general method below doesn't work if b==0. */ |
1261 | 19.6M | if (b == 0 || n == 0) { |
1262 | 101k | return mbedtls_mpi_lset(X, 0); |
1263 | 101k | } |
1264 | | |
1265 | | /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */ |
1266 | 19.5M | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1267 | | /* In general, A * b requires 1 limb more than b. If |
1268 | | * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same |
1269 | | * number of limbs as A and the call to grow() is not required since |
1270 | | * copy() will take care of the growth if needed. However, experimentally, |
1271 | | * making the call to grow() unconditional causes slightly fewer |
1272 | | * calls to calloc() in ECP code, presumably because it reuses the |
1273 | | * same mpi for a while and this way the mpi is more likely to directly |
1274 | | * grow to its final size. |
1275 | | * |
1276 | | * Note that calculating A*b as 0 + A*b doesn't work as-is because |
1277 | | * A,X can be the same. */ |
1278 | 19.5M | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1)); |
1279 | 19.5M | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); |
1280 | 19.5M | mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1); |
1281 | | |
1282 | 19.5M | cleanup: |
1283 | 19.5M | return ret; |
1284 | 19.5M | } |
1285 | | |
1286 | | /* |
1287 | | * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and |
1288 | | * mbedtls_mpi_uint divisor, d |
1289 | | */ |
1290 | | static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1, |
1291 | | mbedtls_mpi_uint u0, |
1292 | | mbedtls_mpi_uint d, |
1293 | | mbedtls_mpi_uint *r) |
1294 | 2.31M | { |
1295 | 2.31M | #if defined(MBEDTLS_HAVE_UDBL) |
1296 | 2.31M | mbedtls_t_udbl dividend, quotient; |
1297 | | #else |
1298 | | const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH; |
1299 | | const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1; |
1300 | | mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient; |
1301 | | mbedtls_mpi_uint u0_msw, u0_lsw; |
1302 | | size_t s; |
1303 | | #endif |
1304 | | |
1305 | | /* |
1306 | | * Check for overflow |
1307 | | */ |
1308 | 2.31M | if (0 == d || u1 >= d) { |
1309 | 0 | if (r != NULL) { |
1310 | 0 | *r = ~(mbedtls_mpi_uint) 0u; |
1311 | 0 | } |
1312 | |
|
1313 | 0 | return ~(mbedtls_mpi_uint) 0u; |
1314 | 0 | } |
1315 | | |
1316 | 2.31M | #if defined(MBEDTLS_HAVE_UDBL) |
1317 | 2.31M | dividend = (mbedtls_t_udbl) u1 << biL; |
1318 | 2.31M | dividend |= (mbedtls_t_udbl) u0; |
1319 | 2.31M | quotient = dividend / d; |
1320 | 2.31M | if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) { |
1321 | 0 | quotient = ((mbedtls_t_udbl) 1 << biL) - 1; |
1322 | 0 | } |
1323 | | |
1324 | 2.31M | if (r != NULL) { |
1325 | 0 | *r = (mbedtls_mpi_uint) (dividend - (quotient * d)); |
1326 | 0 | } |
1327 | | |
1328 | 2.31M | return (mbedtls_mpi_uint) quotient; |
1329 | | #else |
1330 | | |
1331 | | /* |
1332 | | * Algorithm D, Section 4.3.1 - The Art of Computer Programming |
1333 | | * Vol. 2 - Seminumerical Algorithms, Knuth |
1334 | | */ |
1335 | | |
1336 | | /* |
1337 | | * Normalize the divisor, d, and dividend, u0, u1 |
1338 | | */ |
1339 | | s = mbedtls_mpi_core_clz(d); |
1340 | | d = d << s; |
1341 | | |
1342 | | u1 = u1 << s; |
1343 | | u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1)); |
1344 | | u0 = u0 << s; |
1345 | | |
1346 | | d1 = d >> biH; |
1347 | | d0 = d & uint_halfword_mask; |
1348 | | |
1349 | | u0_msw = u0 >> biH; |
1350 | | u0_lsw = u0 & uint_halfword_mask; |
1351 | | |
1352 | | /* |
1353 | | * Find the first quotient and remainder |
1354 | | */ |
1355 | | q1 = u1 / d1; |
1356 | | r0 = u1 - d1 * q1; |
1357 | | |
1358 | | while (q1 >= radix || (q1 * d0 > radix * r0 + u0_msw)) { |
1359 | | q1 -= 1; |
1360 | | r0 += d1; |
1361 | | |
1362 | | if (r0 >= radix) { |
1363 | | break; |
1364 | | } |
1365 | | } |
1366 | | |
1367 | | rAX = (u1 * radix) + (u0_msw - q1 * d); |
1368 | | q0 = rAX / d1; |
1369 | | r0 = rAX - q0 * d1; |
1370 | | |
1371 | | while (q0 >= radix || (q0 * d0 > radix * r0 + u0_lsw)) { |
1372 | | q0 -= 1; |
1373 | | r0 += d1; |
1374 | | |
1375 | | if (r0 >= radix) { |
1376 | | break; |
1377 | | } |
1378 | | } |
1379 | | |
1380 | | if (r != NULL) { |
1381 | | *r = (rAX * radix + u0_lsw - q0 * d) >> s; |
1382 | | } |
1383 | | |
1384 | | quotient = q1 * radix + q0; |
1385 | | |
1386 | | return quotient; |
1387 | | #endif |
1388 | 2.31M | } |
1389 | | |
1390 | | /* |
1391 | | * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20) |
1392 | | */ |
1393 | | int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, |
1394 | | const mbedtls_mpi *B) |
1395 | 423k | { |
1396 | 423k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1397 | 423k | size_t i, n, t, k; |
1398 | 423k | mbedtls_mpi X, Y, Z, T1, T2; |
1399 | 423k | mbedtls_mpi_uint TP2[3]; |
1400 | | |
1401 | 423k | if (mbedtls_mpi_cmp_int(B, 0) == 0) { |
1402 | 113 | return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO; |
1403 | 113 | } |
1404 | | |
1405 | 423k | mbedtls_mpi_init(&X); mbedtls_mpi_init(&Y); mbedtls_mpi_init(&Z); |
1406 | 423k | mbedtls_mpi_init(&T1); |
1407 | | /* |
1408 | | * Avoid dynamic memory allocations for constant-size T2. |
1409 | | * |
1410 | | * T2 is used for comparison only and the 3 limbs are assigned explicitly, |
1411 | | * so nobody increase the size of the MPI and we're safe to use an on-stack |
1412 | | * buffer. |
1413 | | */ |
1414 | 423k | T2.s = 1; |
1415 | 423k | T2.n = sizeof(TP2) / sizeof(*TP2); |
1416 | 423k | T2.p = TP2; |
1417 | | |
1418 | 423k | if (mbedtls_mpi_cmp_abs(A, B) < 0) { |
1419 | 6.94k | if (Q != NULL) { |
1420 | 1.50k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0)); |
1421 | 1.50k | } |
1422 | 6.94k | if (R != NULL) { |
1423 | 5.43k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A)); |
1424 | 5.43k | } |
1425 | 6.94k | return 0; |
1426 | 6.94k | } |
1427 | | |
1428 | 416k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A)); |
1429 | 416k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B)); |
1430 | 416k | X.s = Y.s = 1; |
1431 | | |
1432 | 416k | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2)); |
1433 | 416k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z, 0)); |
1434 | 416k | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2)); |
1435 | | |
1436 | 416k | k = mbedtls_mpi_bitlen(&Y) % biL; |
1437 | 416k | if (k < biL - 1) { |
1438 | 415k | k = biL - 1 - k; |
1439 | 415k | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k)); |
1440 | 415k | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k)); |
1441 | 415k | } else { |
1442 | 112 | k = 0; |
1443 | 112 | } |
1444 | | |
1445 | 416k | n = X.n - 1; |
1446 | 416k | t = Y.n - 1; |
1447 | 416k | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t))); |
1448 | | |
1449 | 422k | while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) { |
1450 | 6.03k | Z.p[n - t]++; |
1451 | 6.03k | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y)); |
1452 | 6.03k | } |
1453 | 416k | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t))); |
1454 | | |
1455 | 2.72M | for (i = n; i > t; i--) { |
1456 | 2.31M | if (X.p[i] >= Y.p[t]) { |
1457 | 34 | Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u; |
1458 | 2.31M | } else { |
1459 | 2.31M | Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1], |
1460 | 2.31M | Y.p[t], NULL); |
1461 | 2.31M | } |
1462 | | |
1463 | 2.31M | T2.p[0] = (i < 2) ? 0 : X.p[i - 2]; |
1464 | 2.31M | T2.p[1] = (i < 1) ? 0 : X.p[i - 1]; |
1465 | 2.31M | T2.p[2] = X.p[i]; |
1466 | | |
1467 | 2.31M | Z.p[i - t - 1]++; |
1468 | 3.30M | do { |
1469 | 3.30M | Z.p[i - t - 1]--; |
1470 | | |
1471 | 3.30M | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0)); |
1472 | 3.30M | T1.p[0] = (t < 1) ? 0 : Y.p[t - 1]; |
1473 | 3.30M | T1.p[1] = Y.p[t]; |
1474 | 3.30M | MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1])); |
1475 | 3.30M | } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0); |
1476 | | |
1477 | 2.31M | MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1])); |
1478 | 2.31M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); |
1479 | 2.31M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1)); |
1480 | | |
1481 | 2.31M | if (mbedtls_mpi_cmp_int(&X, 0) < 0) { |
1482 | 29 | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &Y)); |
1483 | 29 | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1))); |
1484 | 29 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1)); |
1485 | 29 | Z.p[i - t - 1]--; |
1486 | 29 | } |
1487 | 2.31M | } |
1488 | | |
1489 | 416k | if (Q != NULL) { |
1490 | 134k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z)); |
1491 | 134k | Q->s = A->s * B->s; |
1492 | 134k | } |
1493 | | |
1494 | 416k | if (R != NULL) { |
1495 | 281k | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k)); |
1496 | 281k | X.s = A->s; |
1497 | 281k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X)); |
1498 | | |
1499 | 281k | if (mbedtls_mpi_cmp_int(R, 0) == 0) { |
1500 | 80 | R->s = 1; |
1501 | 80 | } |
1502 | 281k | } |
1503 | | |
1504 | 416k | cleanup: |
1505 | | |
1506 | 416k | mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z); |
1507 | 416k | mbedtls_mpi_free(&T1); |
1508 | 416k | mbedtls_platform_zeroize(TP2, sizeof(TP2)); |
1509 | | |
1510 | 416k | return ret; |
1511 | 416k | } |
1512 | | |
1513 | | /* |
1514 | | * Division by int: A = Q * b + R |
1515 | | */ |
1516 | | int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R, |
1517 | | const mbedtls_mpi *A, |
1518 | | mbedtls_mpi_sint b) |
1519 | 136k | { |
1520 | 136k | mbedtls_mpi B; |
1521 | 136k | mbedtls_mpi_uint p[1]; |
1522 | | |
1523 | 136k | p[0] = mpi_sint_abs(b); |
1524 | 136k | B.s = TO_SIGN(b); |
1525 | 136k | B.n = 1; |
1526 | 136k | B.p = p; |
1527 | | |
1528 | 136k | return mbedtls_mpi_div_mpi(Q, R, A, &B); |
1529 | 136k | } |
1530 | | |
1531 | | /* |
1532 | | * Modulo: R = A mod B |
1533 | | */ |
1534 | | int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B) |
1535 | 286k | { |
1536 | 286k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1537 | | |
1538 | 286k | if (mbedtls_mpi_cmp_int(B, 0) < 0) { |
1539 | 0 | return MBEDTLS_ERR_MPI_NEGATIVE_VALUE; |
1540 | 0 | } |
1541 | | |
1542 | 286k | MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B)); |
1543 | | |
1544 | 286k | while (mbedtls_mpi_cmp_int(R, 0) < 0) { |
1545 | 74 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B)); |
1546 | 74 | } |
1547 | | |
1548 | 286k | while (mbedtls_mpi_cmp_mpi(R, B) >= 0) { |
1549 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B)); |
1550 | 0 | } |
1551 | | |
1552 | 286k | cleanup: |
1553 | | |
1554 | 286k | return ret; |
1555 | 286k | } |
1556 | | |
1557 | | /* |
1558 | | * Modulo: r = A mod b |
1559 | | */ |
1560 | | int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b) |
1561 | 136k | { |
1562 | 136k | size_t i; |
1563 | 136k | mbedtls_mpi_uint x, y, z; |
1564 | | |
1565 | 136k | if (b == 0) { |
1566 | 0 | return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO; |
1567 | 0 | } |
1568 | | |
1569 | 136k | if (b < 0) { |
1570 | 0 | return MBEDTLS_ERR_MPI_NEGATIVE_VALUE; |
1571 | 0 | } |
1572 | | |
1573 | | /* |
1574 | | * handle trivial cases |
1575 | | */ |
1576 | 136k | if (b == 1 || A->n == 0) { |
1577 | 0 | *r = 0; |
1578 | 0 | return 0; |
1579 | 0 | } |
1580 | | |
1581 | 136k | if (b == 2) { |
1582 | 0 | *r = A->p[0] & 1; |
1583 | 0 | return 0; |
1584 | 0 | } |
1585 | | |
1586 | | /* |
1587 | | * general case |
1588 | | */ |
1589 | 861k | for (i = A->n, y = 0; i > 0; i--) { |
1590 | 725k | x = A->p[i - 1]; |
1591 | 725k | y = (y << biH) | (x >> biH); |
1592 | 725k | z = y / b; |
1593 | 725k | y -= z * b; |
1594 | | |
1595 | 725k | x <<= biH; |
1596 | 725k | y = (y << biH) | (x >> biH); |
1597 | 725k | z = y / b; |
1598 | 725k | y -= z * b; |
1599 | 725k | } |
1600 | | |
1601 | | /* |
1602 | | * If A is negative, then the current y represents a negative value. |
1603 | | * Flipping it to the positive side. |
1604 | | */ |
1605 | 136k | if (A->s < 0 && y != 0) { |
1606 | 0 | y = b - y; |
1607 | 0 | } |
1608 | | |
1609 | 136k | *r = y; |
1610 | | |
1611 | 136k | return 0; |
1612 | 136k | } |
1613 | | |
1614 | | /* |
1615 | | * Warning! If the parameter E_public has MBEDTLS_MPI_IS_PUBLIC as its value, |
1616 | | * this function is not constant time with respect to the exponent (parameter E). |
1617 | | */ |
1618 | | static int mbedtls_mpi_exp_mod_optionally_safe(mbedtls_mpi *X, const mbedtls_mpi *A, |
1619 | | const mbedtls_mpi *E, int E_public, |
1620 | | const mbedtls_mpi *N, mbedtls_mpi *prec_RR) |
1621 | 4.33k | { |
1622 | 4.33k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1623 | | |
1624 | 4.33k | if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) { |
1625 | 2.53k | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
1626 | 2.53k | } |
1627 | | |
1628 | 1.79k | if (mbedtls_mpi_cmp_int(E, 0) < 0) { |
1629 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
1630 | 0 | } |
1631 | | |
1632 | 1.79k | if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS || |
1633 | 1.79k | mbedtls_mpi_bitlen(N) > MBEDTLS_MPI_MAX_BITS) { |
1634 | 106 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
1635 | 106 | } |
1636 | | |
1637 | | /* |
1638 | | * Ensure that the exponent that we are passing to the core is not NULL. |
1639 | | */ |
1640 | 1.69k | if (E->n == 0) { |
1641 | 0 | ret = mbedtls_mpi_lset(X, 1); |
1642 | 0 | return ret; |
1643 | 0 | } |
1644 | | |
1645 | | /* |
1646 | | * Allocate working memory for mbedtls_mpi_core_exp_mod() |
1647 | | */ |
1648 | 1.69k | size_t T_limbs = mbedtls_mpi_core_exp_mod_working_limbs(N->n, E->n); |
1649 | 1.69k | mbedtls_mpi_uint *T = (mbedtls_mpi_uint *) mbedtls_calloc(T_limbs, sizeof(mbedtls_mpi_uint)); |
1650 | 1.69k | if (T == NULL) { |
1651 | 0 | return MBEDTLS_ERR_MPI_ALLOC_FAILED; |
1652 | 0 | } |
1653 | | |
1654 | 1.69k | mbedtls_mpi RR; |
1655 | 1.69k | mbedtls_mpi_init(&RR); |
1656 | | |
1657 | | /* |
1658 | | * If 1st call, pre-compute R^2 mod N |
1659 | | */ |
1660 | 1.69k | if (prec_RR == NULL || prec_RR->p == NULL) { |
1661 | 1.69k | MBEDTLS_MPI_CHK(mbedtls_mpi_core_get_mont_r2_unsafe(&RR, N)); |
1662 | | |
1663 | 1.69k | if (prec_RR != NULL) { |
1664 | 0 | *prec_RR = RR; |
1665 | 0 | } |
1666 | 1.69k | } else { |
1667 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(prec_RR, N->n)); |
1668 | 0 | RR = *prec_RR; |
1669 | 0 | } |
1670 | | |
1671 | | /* |
1672 | | * To preserve constness we need to make a copy of A. Using X for this to |
1673 | | * save memory. |
1674 | | */ |
1675 | 1.69k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A)); |
1676 | | |
1677 | | /* |
1678 | | * Compensate for negative A (and correct at the end). |
1679 | | */ |
1680 | 1.69k | X->s = 1; |
1681 | | |
1682 | | /* |
1683 | | * Make sure that X is in a form that is safe for consumption by |
1684 | | * the core functions. |
1685 | | * |
1686 | | * - The core functions will not touch the limbs of X above N->n. The |
1687 | | * result will be correct if those limbs are 0, which the mod call |
1688 | | * ensures. |
1689 | | * - Also, X must have at least as many limbs as N for the calls to the |
1690 | | * core functions. |
1691 | | */ |
1692 | 1.69k | if (mbedtls_mpi_cmp_mpi(X, N) >= 0) { |
1693 | 422 | MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N)); |
1694 | 422 | } |
1695 | 1.69k | MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, N->n)); |
1696 | | |
1697 | | /* |
1698 | | * Convert to and from Montgomery around mbedtls_mpi_core_exp_mod(). |
1699 | | */ |
1700 | 1.69k | { |
1701 | 1.69k | mbedtls_mpi_uint mm = mbedtls_mpi_core_montmul_init(N->p); |
1702 | 1.69k | mbedtls_mpi_core_to_mont_rep(X->p, X->p, N->p, N->n, mm, RR.p, T); |
1703 | 1.69k | if (E_public == MBEDTLS_MPI_IS_PUBLIC) { |
1704 | 0 | mbedtls_mpi_core_exp_mod_unsafe(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); |
1705 | 1.69k | } else { |
1706 | 1.69k | mbedtls_mpi_core_exp_mod(X->p, X->p, N->p, N->n, E->p, E->n, RR.p, T); |
1707 | 1.69k | } |
1708 | 1.69k | mbedtls_mpi_core_from_mont_rep(X->p, X->p, N->p, N->n, mm, T); |
1709 | 1.69k | } |
1710 | | |
1711 | | /* |
1712 | | * Correct for negative A. |
1713 | | */ |
1714 | 1.69k | if (A->s == -1 && (E->p[0] & 1) != 0) { |
1715 | 0 | mbedtls_ct_condition_t is_x_non_zero = mbedtls_mpi_core_check_zero_ct(X->p, X->n); |
1716 | 0 | X->s = mbedtls_ct_mpi_sign_if(is_x_non_zero, -1, 1); |
1717 | |
|
1718 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(X, N, X)); |
1719 | 0 | } |
1720 | | |
1721 | 1.69k | cleanup: |
1722 | | |
1723 | 1.69k | mbedtls_mpi_zeroize_and_free(T, T_limbs); |
1724 | | |
1725 | 1.69k | if (prec_RR == NULL || prec_RR->p == NULL) { |
1726 | 1.69k | mbedtls_mpi_free(&RR); |
1727 | 1.69k | } |
1728 | | |
1729 | 1.69k | return ret; |
1730 | 1.69k | } |
1731 | | |
1732 | | int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A, |
1733 | | const mbedtls_mpi *E, const mbedtls_mpi *N, |
1734 | | mbedtls_mpi *prec_RR) |
1735 | 4.33k | { |
1736 | 4.33k | return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_SECRET, N, prec_RR); |
1737 | 4.33k | } |
1738 | | |
1739 | | int mbedtls_mpi_exp_mod_unsafe(mbedtls_mpi *X, const mbedtls_mpi *A, |
1740 | | const mbedtls_mpi *E, const mbedtls_mpi *N, |
1741 | | mbedtls_mpi *prec_RR) |
1742 | 0 | { |
1743 | 0 | return mbedtls_mpi_exp_mod_optionally_safe(X, A, E, MBEDTLS_MPI_IS_PUBLIC, N, prec_RR); |
1744 | 0 | } |
1745 | | |
1746 | | /* |
1747 | | * Greatest common divisor: G = gcd(A, B) (HAC 14.54) |
1748 | | */ |
1749 | | int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B) |
1750 | 4.98k | { |
1751 | 4.98k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1752 | 4.98k | size_t lz, lzt; |
1753 | 4.98k | mbedtls_mpi TA, TB; |
1754 | | |
1755 | 4.98k | mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TB); |
1756 | | |
1757 | 4.98k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); |
1758 | 4.98k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); |
1759 | | |
1760 | 4.98k | lz = mbedtls_mpi_lsb(&TA); |
1761 | 4.98k | lzt = mbedtls_mpi_lsb(&TB); |
1762 | | |
1763 | | /* The loop below gives the correct result when A==0 but not when B==0. |
1764 | | * So have a special case for B==0. Leverage the fact that we just |
1765 | | * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test |
1766 | | * slightly more efficient than cmp_int(). */ |
1767 | 4.98k | if (lzt == 0 && mbedtls_mpi_get_bit(&TB, 0) == 0) { |
1768 | 0 | ret = mbedtls_mpi_copy(G, A); |
1769 | 0 | goto cleanup; |
1770 | 0 | } |
1771 | | |
1772 | 4.98k | if (lzt < lz) { |
1773 | 2.00k | lz = lzt; |
1774 | 2.00k | } |
1775 | | |
1776 | 4.98k | TA.s = TB.s = 1; |
1777 | | |
1778 | | /* We mostly follow the procedure described in HAC 14.54, but with some |
1779 | | * minor differences: |
1780 | | * - Sequences of multiplications or divisions by 2 are grouped into a |
1781 | | * single shift operation. |
1782 | | * - The procedure in HAC assumes that 0 < TB <= TA. |
1783 | | * - The condition TB <= TA is not actually necessary for correctness. |
1784 | | * TA and TB have symmetric roles except for the loop termination |
1785 | | * condition, and the shifts at the beginning of the loop body |
1786 | | * remove any significance from the ordering of TA vs TB before |
1787 | | * the shifts. |
1788 | | * - If TA = 0, the loop goes through 0 iterations and the result is |
1789 | | * correctly TB. |
1790 | | * - The case TB = 0 was short-circuited above. |
1791 | | * |
1792 | | * For the correctness proof below, decompose the original values of |
1793 | | * A and B as |
1794 | | * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1 |
1795 | | * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1 |
1796 | | * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'), |
1797 | | * and gcd(A',B') is odd or 0. |
1798 | | * |
1799 | | * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB). |
1800 | | * The code maintains the following invariant: |
1801 | | * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I) |
1802 | | */ |
1803 | | |
1804 | | /* Proof that the loop terminates: |
1805 | | * At each iteration, either the right-shift by 1 is made on a nonzero |
1806 | | * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases |
1807 | | * by at least 1, or the right-shift by 1 is made on zero and then |
1808 | | * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted |
1809 | | * since in that case TB is calculated from TB-TA with the condition TB>TA). |
1810 | | */ |
1811 | 2.70M | while (mbedtls_mpi_cmp_int(&TA, 0) != 0) { |
1812 | | /* Divisions by 2 preserve the invariant (I). */ |
1813 | 2.70M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, mbedtls_mpi_lsb(&TA))); |
1814 | 2.70M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, mbedtls_mpi_lsb(&TB))); |
1815 | | |
1816 | | /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd, |
1817 | | * TA-TB is even so the division by 2 has an integer result. |
1818 | | * Invariant (I) is preserved since any odd divisor of both TA and TB |
1819 | | * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2 |
1820 | | * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also |
1821 | | * divides TA. |
1822 | | */ |
1823 | 2.70M | if (mbedtls_mpi_cmp_mpi(&TA, &TB) >= 0) { |
1824 | 1.22M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TA, &TA, &TB)); |
1825 | 1.22M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, 1)); |
1826 | 1.48M | } else { |
1827 | 1.48M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TB, &TB, &TA)); |
1828 | 1.48M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, 1)); |
1829 | 1.48M | } |
1830 | | /* Note that one of TA or TB is still odd. */ |
1831 | 2.70M | } |
1832 | | |
1833 | | /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k. |
1834 | | * At the loop exit, TA = 0, so gcd(TA,TB) = TB. |
1835 | | * - If there was at least one loop iteration, then one of TA or TB is odd, |
1836 | | * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case, |
1837 | | * lz = min(a,b) so gcd(A,B) = 2^lz * TB. |
1838 | | * - If there was no loop iteration, then A was 0, and gcd(A,B) = B. |
1839 | | * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well. |
1840 | | */ |
1841 | | |
1842 | 4.98k | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&TB, lz)); |
1843 | 4.98k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB)); |
1844 | | |
1845 | 4.98k | cleanup: |
1846 | | |
1847 | 4.98k | mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB); |
1848 | | |
1849 | 4.98k | return ret; |
1850 | 4.98k | } |
1851 | | |
1852 | | /* |
1853 | | * Fill X with size bytes of random. |
1854 | | * The bytes returned from the RNG are used in a specific order which |
1855 | | * is suitable for deterministic ECDSA (see the specification of |
1856 | | * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()). |
1857 | | */ |
1858 | | int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size, |
1859 | | int (*f_rng)(void *, unsigned char *, size_t), |
1860 | | void *p_rng) |
1861 | 0 | { |
1862 | 0 | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1863 | 0 | const size_t limbs = CHARS_TO_LIMBS(size); |
1864 | | |
1865 | | /* Ensure that target MPI has exactly the necessary number of limbs */ |
1866 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs)); |
1867 | 0 | if (size == 0) { |
1868 | 0 | return 0; |
1869 | 0 | } |
1870 | | |
1871 | 0 | ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng); |
1872 | |
|
1873 | 0 | cleanup: |
1874 | 0 | return ret; |
1875 | 0 | } |
1876 | | |
1877 | | int mbedtls_mpi_random(mbedtls_mpi *X, |
1878 | | mbedtls_mpi_sint min, |
1879 | | const mbedtls_mpi *N, |
1880 | | int (*f_rng)(void *, unsigned char *, size_t), |
1881 | | void *p_rng) |
1882 | 2.26k | { |
1883 | 2.26k | if (min < 0) { |
1884 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
1885 | 0 | } |
1886 | 2.26k | if (mbedtls_mpi_cmp_int(N, min) <= 0) { |
1887 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
1888 | 0 | } |
1889 | | |
1890 | | /* Ensure that target MPI has exactly the same number of limbs |
1891 | | * as the upper bound, even if the upper bound has leading zeros. |
1892 | | * This is necessary for mbedtls_mpi_core_random. */ |
1893 | 2.26k | int ret = mbedtls_mpi_resize_clear(X, N->n); |
1894 | 2.26k | if (ret != 0) { |
1895 | 0 | return ret; |
1896 | 0 | } |
1897 | | |
1898 | 2.26k | return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng); |
1899 | 2.26k | } |
1900 | | |
1901 | | /* |
1902 | | * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64) |
1903 | | */ |
1904 | | int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N) |
1905 | 4.61k | { |
1906 | 4.61k | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
1907 | 4.61k | mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2; |
1908 | | |
1909 | 4.61k | if (mbedtls_mpi_cmp_int(N, 1) <= 0) { |
1910 | 29 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
1911 | 29 | } |
1912 | | |
1913 | 4.58k | mbedtls_mpi_init(&TA); mbedtls_mpi_init(&TU); mbedtls_mpi_init(&U1); mbedtls_mpi_init(&U2); |
1914 | 4.58k | mbedtls_mpi_init(&G); mbedtls_mpi_init(&TB); mbedtls_mpi_init(&TV); |
1915 | 4.58k | mbedtls_mpi_init(&V1); mbedtls_mpi_init(&V2); |
1916 | | |
1917 | 4.58k | MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N)); |
1918 | | |
1919 | 4.58k | if (mbedtls_mpi_cmp_int(&G, 1) != 0) { |
1920 | 398 | ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
1921 | 398 | goto cleanup; |
1922 | 398 | } |
1923 | | |
1924 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&TA, A, N)); |
1925 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA)); |
1926 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, N)); |
1927 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TV, N)); |
1928 | | |
1929 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U1, 1)); |
1930 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U2, 0)); |
1931 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V1, 0)); |
1932 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V2, 1)); |
1933 | | |
1934 | 1.77M | do { |
1935 | 3.30M | while ((TU.p[0] & 1) == 0) { |
1936 | 1.53M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TU, 1)); |
1937 | | |
1938 | 1.53M | if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) { |
1939 | 747k | MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB)); |
1940 | 747k | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA)); |
1941 | 747k | } |
1942 | | |
1943 | 1.53M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U1, 1)); |
1944 | 1.53M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U2, 1)); |
1945 | 1.53M | } |
1946 | | |
1947 | 3.81M | while ((TV.p[0] & 1) == 0) { |
1948 | 2.04M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TV, 1)); |
1949 | | |
1950 | 2.04M | if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) { |
1951 | 1.01M | MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB)); |
1952 | 1.01M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA)); |
1953 | 1.01M | } |
1954 | | |
1955 | 2.04M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V1, 1)); |
1956 | 2.04M | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V2, 1)); |
1957 | 2.04M | } |
1958 | | |
1959 | 1.77M | if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) { |
1960 | 765k | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV)); |
1961 | 765k | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1)); |
1962 | 765k | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2)); |
1963 | 1.00M | } else { |
1964 | 1.00M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU)); |
1965 | 1.00M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1)); |
1966 | 1.00M | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2)); |
1967 | 1.00M | } |
1968 | 1.77M | } while (mbedtls_mpi_cmp_int(&TU, 0) != 0); |
1969 | | |
1970 | 4.89k | while (mbedtls_mpi_cmp_int(&V1, 0) < 0) { |
1971 | 704 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, N)); |
1972 | 704 | } |
1973 | | |
1974 | 4.23k | while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) { |
1975 | 50 | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, N)); |
1976 | 50 | } |
1977 | | |
1978 | 4.18k | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1)); |
1979 | | |
1980 | 4.58k | cleanup: |
1981 | | |
1982 | 4.58k | mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TU); mbedtls_mpi_free(&U1); mbedtls_mpi_free(&U2); |
1983 | 4.58k | mbedtls_mpi_free(&G); mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TV); |
1984 | 4.58k | mbedtls_mpi_free(&V1); mbedtls_mpi_free(&V2); |
1985 | | |
1986 | 4.58k | return ret; |
1987 | 4.18k | } |
1988 | | |
1989 | | #if defined(MBEDTLS_GENPRIME) |
1990 | | |
1991 | | /* Gaps between primes, starting at 3. https://oeis.org/A001223 */ |
1992 | | static const unsigned char small_prime_gaps[] = { |
1993 | | 2, 2, 4, 2, 4, 2, 4, 6, |
1994 | | 2, 6, 4, 2, 4, 6, 6, 2, |
1995 | | 6, 4, 2, 6, 4, 6, 8, 4, |
1996 | | 2, 4, 2, 4, 14, 4, 6, 2, |
1997 | | 10, 2, 6, 6, 4, 6, 6, 2, |
1998 | | 10, 2, 4, 2, 12, 12, 4, 2, |
1999 | | 4, 6, 2, 10, 6, 6, 6, 2, |
2000 | | 6, 4, 2, 10, 14, 4, 2, 4, |
2001 | | 14, 6, 10, 2, 4, 6, 8, 6, |
2002 | | 6, 4, 6, 8, 4, 8, 10, 2, |
2003 | | 10, 2, 6, 4, 6, 8, 4, 2, |
2004 | | 4, 12, 8, 4, 8, 4, 6, 12, |
2005 | | 2, 18, 6, 10, 6, 6, 2, 6, |
2006 | | 10, 6, 6, 2, 6, 6, 4, 2, |
2007 | | 12, 10, 2, 4, 6, 6, 2, 12, |
2008 | | 4, 6, 8, 10, 8, 10, 8, 6, |
2009 | | 6, 4, 8, 6, 4, 8, 4, 14, |
2010 | | 10, 12, 2, 10, 2, 4, 2, 10, |
2011 | | 14, 4, 2, 4, 14, 4, 2, 4, |
2012 | | 20, 4, 8, 10, 8, 4, 6, 6, |
2013 | | 14, 4, 6, 6, 8, 6, /*reaches 997*/ |
2014 | | 0 /* the last entry is effectively unused */ |
2015 | | }; |
2016 | | |
2017 | | /* |
2018 | | * Small divisors test (X must be positive) |
2019 | | * |
2020 | | * Return values: |
2021 | | * 0: no small factor (possible prime, more tests needed) |
2022 | | * 1: certain prime |
2023 | | * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime |
2024 | | * other negative: error |
2025 | | */ |
2026 | | static int mpi_check_small_factors(const mbedtls_mpi *X) |
2027 | 0 | { |
2028 | 0 | int ret = 0; |
2029 | 0 | size_t i; |
2030 | 0 | mbedtls_mpi_uint r; |
2031 | 0 | unsigned p = 3; /* The first odd prime */ |
2032 | |
|
2033 | 0 | if ((X->p[0] & 1) == 0) { |
2034 | 0 | return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
2035 | 0 | } |
2036 | | |
2037 | 0 | for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) { |
2038 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p)); |
2039 | 0 | if (r == 0) { |
2040 | 0 | if (mbedtls_mpi_cmp_int(X, p) == 0) { |
2041 | 0 | return 1; |
2042 | 0 | } else { |
2043 | 0 | return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
2044 | 0 | } |
2045 | 0 | } |
2046 | 0 | } |
2047 | | |
2048 | 0 | cleanup: |
2049 | 0 | return ret; |
2050 | 0 | } |
2051 | | |
2052 | | /* |
2053 | | * Miller-Rabin pseudo-primality test (HAC 4.24) |
2054 | | */ |
2055 | | static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds, |
2056 | | int (*f_rng)(void *, unsigned char *, size_t), |
2057 | | void *p_rng) |
2058 | 0 | { |
2059 | 0 | int ret, count; |
2060 | 0 | size_t i, j, k, s; |
2061 | 0 | mbedtls_mpi W, R, T, A, RR; |
2062 | |
|
2063 | 0 | mbedtls_mpi_init(&W); mbedtls_mpi_init(&R); |
2064 | 0 | mbedtls_mpi_init(&T); mbedtls_mpi_init(&A); |
2065 | 0 | mbedtls_mpi_init(&RR); |
2066 | | |
2067 | | /* |
2068 | | * W = |X| - 1 |
2069 | | * R = W >> lsb( W ) |
2070 | | */ |
2071 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1)); |
2072 | 0 | s = mbedtls_mpi_lsb(&W); |
2073 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W)); |
2074 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s)); |
2075 | | |
2076 | 0 | for (i = 0; i < rounds; i++) { |
2077 | | /* |
2078 | | * pick a random A, 1 < A < |X| - 1 |
2079 | | */ |
2080 | 0 | count = 0; |
2081 | 0 | do { |
2082 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng)); |
2083 | | |
2084 | 0 | j = mbedtls_mpi_bitlen(&A); |
2085 | 0 | k = mbedtls_mpi_bitlen(&W); |
2086 | 0 | if (j > k) { |
2087 | 0 | A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1; |
2088 | 0 | } |
2089 | |
|
2090 | 0 | if (count++ > 30) { |
2091 | 0 | ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
2092 | 0 | goto cleanup; |
2093 | 0 | } |
2094 | |
|
2095 | 0 | } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 || |
2096 | 0 | mbedtls_mpi_cmp_int(&A, 1) <= 0); |
2097 | | |
2098 | | /* |
2099 | | * A = A^R mod |X| |
2100 | | */ |
2101 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR)); |
2102 | | |
2103 | 0 | if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 || |
2104 | 0 | mbedtls_mpi_cmp_int(&A, 1) == 0) { |
2105 | 0 | continue; |
2106 | 0 | } |
2107 | | |
2108 | 0 | j = 1; |
2109 | 0 | while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) { |
2110 | | /* |
2111 | | * A = A * A mod |X| |
2112 | | */ |
2113 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A)); |
2114 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X)); |
2115 | | |
2116 | 0 | if (mbedtls_mpi_cmp_int(&A, 1) == 0) { |
2117 | 0 | break; |
2118 | 0 | } |
2119 | | |
2120 | 0 | j++; |
2121 | 0 | } |
2122 | | |
2123 | | /* |
2124 | | * not prime if A != |X| - 1 or A == 1 |
2125 | | */ |
2126 | 0 | if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 || |
2127 | 0 | mbedtls_mpi_cmp_int(&A, 1) == 0) { |
2128 | 0 | ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
2129 | 0 | break; |
2130 | 0 | } |
2131 | 0 | } |
2132 | | |
2133 | 0 | cleanup: |
2134 | 0 | mbedtls_mpi_free(&W); mbedtls_mpi_free(&R); |
2135 | 0 | mbedtls_mpi_free(&T); mbedtls_mpi_free(&A); |
2136 | 0 | mbedtls_mpi_free(&RR); |
2137 | |
|
2138 | 0 | return ret; |
2139 | 0 | } |
2140 | | |
2141 | | /* |
2142 | | * Pseudo-primality test: small factors, then Miller-Rabin |
2143 | | */ |
2144 | | int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds, |
2145 | | int (*f_rng)(void *, unsigned char *, size_t), |
2146 | | void *p_rng) |
2147 | 0 | { |
2148 | 0 | int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED; |
2149 | 0 | mbedtls_mpi XX; |
2150 | |
|
2151 | 0 | XX.s = 1; |
2152 | 0 | XX.n = X->n; |
2153 | 0 | XX.p = X->p; |
2154 | |
|
2155 | 0 | if (mbedtls_mpi_cmp_int(&XX, 0) == 0 || |
2156 | 0 | mbedtls_mpi_cmp_int(&XX, 1) == 0) { |
2157 | 0 | return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
2158 | 0 | } |
2159 | | |
2160 | 0 | if (mbedtls_mpi_cmp_int(&XX, 2) == 0) { |
2161 | 0 | return 0; |
2162 | 0 | } |
2163 | | |
2164 | 0 | if ((ret = mpi_check_small_factors(&XX)) != 0) { |
2165 | 0 | if (ret == 1) { |
2166 | 0 | return 0; |
2167 | 0 | } |
2168 | | |
2169 | 0 | return ret; |
2170 | 0 | } |
2171 | | |
2172 | 0 | return mpi_miller_rabin(&XX, rounds, f_rng, p_rng); |
2173 | 0 | } |
2174 | | |
2175 | | /* |
2176 | | * Prime number generation |
2177 | | * |
2178 | | * To generate an RSA key in a way recommended by FIPS 186-4, both primes must |
2179 | | * be either 1024 bits or 1536 bits long, and flags must contain |
2180 | | * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR. |
2181 | | */ |
2182 | | int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags, |
2183 | | int (*f_rng)(void *, unsigned char *, size_t), |
2184 | | void *p_rng) |
2185 | 0 | { |
2186 | 0 | #ifdef MBEDTLS_HAVE_INT64 |
2187 | | // ceil(2^63.5) |
2188 | 0 | #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL |
2189 | | #else |
2190 | | // ceil(2^31.5) |
2191 | | #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U |
2192 | | #endif |
2193 | 0 | int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE; |
2194 | 0 | size_t k, n; |
2195 | 0 | int rounds; |
2196 | 0 | mbedtls_mpi_uint r; |
2197 | 0 | mbedtls_mpi Y; |
2198 | |
|
2199 | 0 | if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) { |
2200 | 0 | return MBEDTLS_ERR_MPI_BAD_INPUT_DATA; |
2201 | 0 | } |
2202 | | |
2203 | 0 | mbedtls_mpi_init(&Y); |
2204 | |
|
2205 | 0 | n = BITS_TO_LIMBS(nbits); |
2206 | |
|
2207 | 0 | if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR) == 0) { |
2208 | | /* |
2209 | | * 2^-80 error probability, number of rounds chosen per HAC, table 4.4 |
2210 | | */ |
2211 | 0 | rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 : |
2212 | 0 | (nbits >= 650) ? 4 : (nbits >= 350) ? 8 : |
2213 | 0 | (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27); |
2214 | 0 | } else { |
2215 | | /* |
2216 | | * 2^-100 error probability, number of rounds computed based on HAC, |
2217 | | * fact 4.48 |
2218 | | */ |
2219 | 0 | rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 : |
2220 | 0 | (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 : |
2221 | 0 | (nbits >= 750) ? 8 : (nbits >= 500) ? 13 : |
2222 | 0 | (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51); |
2223 | 0 | } |
2224 | |
|
2225 | 0 | while (1) { |
2226 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng)); |
2227 | | /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */ |
2228 | 0 | if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) { |
2229 | 0 | continue; |
2230 | 0 | } |
2231 | | |
2232 | 0 | k = n * biL; |
2233 | 0 | if (k > nbits) { |
2234 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits)); |
2235 | 0 | } |
2236 | 0 | X->p[0] |= 1; |
2237 | |
|
2238 | 0 | if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) { |
2239 | 0 | ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng); |
2240 | |
|
2241 | 0 | if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { |
2242 | 0 | goto cleanup; |
2243 | 0 | } |
2244 | 0 | } else { |
2245 | | /* |
2246 | | * A necessary condition for Y and X = 2Y + 1 to be prime |
2247 | | * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3). |
2248 | | * Make sure it is satisfied, while keeping X = 3 mod 4 |
2249 | | */ |
2250 | |
|
2251 | 0 | X->p[0] |= 2; |
2252 | |
|
2253 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3)); |
2254 | 0 | if (r == 0) { |
2255 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8)); |
2256 | 0 | } else if (r == 1) { |
2257 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4)); |
2258 | 0 | } |
2259 | | |
2260 | | /* Set Y = (X-1) / 2, which is X / 2 because X is odd */ |
2261 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X)); |
2262 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, 1)); |
2263 | | |
2264 | 0 | while (1) { |
2265 | | /* |
2266 | | * First, check small factors for X and Y |
2267 | | * before doing Miller-Rabin on any of them |
2268 | | */ |
2269 | 0 | if ((ret = mpi_check_small_factors(X)) == 0 && |
2270 | 0 | (ret = mpi_check_small_factors(&Y)) == 0 && |
2271 | 0 | (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng)) |
2272 | 0 | == 0 && |
2273 | 0 | (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng)) |
2274 | 0 | == 0) { |
2275 | 0 | goto cleanup; |
2276 | 0 | } |
2277 | | |
2278 | 0 | if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) { |
2279 | 0 | goto cleanup; |
2280 | 0 | } |
2281 | | |
2282 | | /* |
2283 | | * Next candidates. We want to preserve Y = (X-1) / 2 and |
2284 | | * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3) |
2285 | | * so up Y by 6 and X by 12. |
2286 | | */ |
2287 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12)); |
2288 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6)); |
2289 | 0 | } |
2290 | 0 | } |
2291 | 0 | } |
2292 | | |
2293 | 0 | cleanup: |
2294 | |
|
2295 | 0 | mbedtls_mpi_free(&Y); |
2296 | |
|
2297 | 0 | return ret; |
2298 | 0 | } |
2299 | | |
2300 | | #endif /* MBEDTLS_GENPRIME */ |
2301 | | |
2302 | | #if defined(MBEDTLS_SELF_TEST) |
2303 | | |
2304 | 0 | #define GCD_PAIR_COUNT 3 |
2305 | | |
2306 | | static const int gcd_pairs[GCD_PAIR_COUNT][3] = |
2307 | | { |
2308 | | { 693, 609, 21 }, |
2309 | | { 1764, 868, 28 }, |
2310 | | { 768454923, 542167814, 1 } |
2311 | | }; |
2312 | | |
2313 | | /* |
2314 | | * Checkup routine |
2315 | | */ |
2316 | | int mbedtls_mpi_self_test(int verbose) |
2317 | 0 | { |
2318 | 0 | int ret, i; |
2319 | 0 | mbedtls_mpi A, E, N, X, Y, U, V; |
2320 | |
|
2321 | 0 | mbedtls_mpi_init(&A); mbedtls_mpi_init(&E); mbedtls_mpi_init(&N); mbedtls_mpi_init(&X); |
2322 | 0 | mbedtls_mpi_init(&Y); mbedtls_mpi_init(&U); mbedtls_mpi_init(&V); |
2323 | |
|
2324 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16, |
2325 | 0 | "EFE021C2645FD1DC586E69184AF4A31E" \ |
2326 | 0 | "D5F53E93B5F123FA41680867BA110131" \ |
2327 | 0 | "944FE7952E2517337780CB0DB80E61AA" \ |
2328 | 0 | "E7C8DDC6C5C6AADEB34EB38A2F40D5E6")); |
2329 | | |
2330 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16, |
2331 | 0 | "B2E7EFD37075B9F03FF989C7C5051C20" \ |
2332 | 0 | "34D2A323810251127E7BF8625A4F49A5" \ |
2333 | 0 | "F3E27F4DA8BD59C47D6DAABA4C8127BD" \ |
2334 | 0 | "5B5C25763222FEFCCFC38B832366C29E")); |
2335 | | |
2336 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16, |
2337 | 0 | "0066A198186C18C10B2F5ED9B522752A" \ |
2338 | 0 | "9830B69916E535C8F047518A889A43A5" \ |
2339 | 0 | "94B6BED27A168D31D4A52F88925AA8F5")); |
2340 | | |
2341 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N)); |
2342 | | |
2343 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, |
2344 | 0 | "602AB7ECA597A3D6B56FF9829A5E8B85" \ |
2345 | 0 | "9E857EA95A03512E2BAE7391688D264A" \ |
2346 | 0 | "A5663B0341DB9CCFD2C4C5F421FEC814" \ |
2347 | 0 | "8001B72E848A38CAE1C65F78E56ABDEF" \ |
2348 | 0 | "E12D3C039B8A02D6BE593F0BBBDA56F1" \ |
2349 | 0 | "ECF677152EF804370C1A305CAF3B5BF1" \ |
2350 | 0 | "30879B56C61DE584A0F53A2447A51E")); |
2351 | | |
2352 | 0 | if (verbose != 0) { |
2353 | 0 | mbedtls_printf(" MPI test #1 (mul_mpi): "); |
2354 | 0 | } |
2355 | |
|
2356 | 0 | if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { |
2357 | 0 | if (verbose != 0) { |
2358 | 0 | mbedtls_printf("failed\n"); |
2359 | 0 | } |
2360 | |
|
2361 | 0 | ret = 1; |
2362 | 0 | goto cleanup; |
2363 | 0 | } |
2364 | | |
2365 | 0 | if (verbose != 0) { |
2366 | 0 | mbedtls_printf("passed\n"); |
2367 | 0 | } |
2368 | |
|
2369 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N)); |
2370 | | |
2371 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, |
2372 | 0 | "256567336059E52CAE22925474705F39A94")); |
2373 | | |
2374 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16, |
2375 | 0 | "6613F26162223DF488E9CD48CC132C7A" \ |
2376 | 0 | "0AC93C701B001B092E4E5B9F73BCD27B" \ |
2377 | 0 | "9EE50D0657C77F374E903CDFA4C642")); |
2378 | | |
2379 | 0 | if (verbose != 0) { |
2380 | 0 | mbedtls_printf(" MPI test #2 (div_mpi): "); |
2381 | 0 | } |
2382 | |
|
2383 | 0 | if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 || |
2384 | 0 | mbedtls_mpi_cmp_mpi(&Y, &V) != 0) { |
2385 | 0 | if (verbose != 0) { |
2386 | 0 | mbedtls_printf("failed\n"); |
2387 | 0 | } |
2388 | |
|
2389 | 0 | ret = 1; |
2390 | 0 | goto cleanup; |
2391 | 0 | } |
2392 | | |
2393 | 0 | if (verbose != 0) { |
2394 | 0 | mbedtls_printf("passed\n"); |
2395 | 0 | } |
2396 | |
|
2397 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL)); |
2398 | | |
2399 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, |
2400 | 0 | "36E139AEA55215609D2816998ED020BB" \ |
2401 | 0 | "BD96C37890F65171D948E9BC7CBAA4D9" \ |
2402 | 0 | "325D24D6A3C12710F10A09FA08AB87")); |
2403 | | |
2404 | 0 | if (verbose != 0) { |
2405 | 0 | mbedtls_printf(" MPI test #3 (exp_mod): "); |
2406 | 0 | } |
2407 | |
|
2408 | 0 | if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { |
2409 | 0 | if (verbose != 0) { |
2410 | 0 | mbedtls_printf("failed\n"); |
2411 | 0 | } |
2412 | |
|
2413 | 0 | ret = 1; |
2414 | 0 | goto cleanup; |
2415 | 0 | } |
2416 | | |
2417 | 0 | if (verbose != 0) { |
2418 | 0 | mbedtls_printf("passed\n"); |
2419 | 0 | } |
2420 | |
|
2421 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N)); |
2422 | | |
2423 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16, |
2424 | 0 | "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \ |
2425 | 0 | "C3DBA76456363A10869622EAC2DD84EC" \ |
2426 | 0 | "C5B8A74DAC4D09E03B5E0BE779F2DF61")); |
2427 | | |
2428 | 0 | if (verbose != 0) { |
2429 | 0 | mbedtls_printf(" MPI test #4 (inv_mod): "); |
2430 | 0 | } |
2431 | |
|
2432 | 0 | if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) { |
2433 | 0 | if (verbose != 0) { |
2434 | 0 | mbedtls_printf("failed\n"); |
2435 | 0 | } |
2436 | |
|
2437 | 0 | ret = 1; |
2438 | 0 | goto cleanup; |
2439 | 0 | } |
2440 | | |
2441 | 0 | if (verbose != 0) { |
2442 | 0 | mbedtls_printf("passed\n"); |
2443 | 0 | } |
2444 | |
|
2445 | 0 | if (verbose != 0) { |
2446 | 0 | mbedtls_printf(" MPI test #5 (simple gcd): "); |
2447 | 0 | } |
2448 | |
|
2449 | 0 | for (i = 0; i < GCD_PAIR_COUNT; i++) { |
2450 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0])); |
2451 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1])); |
2452 | | |
2453 | 0 | MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y)); |
2454 | | |
2455 | 0 | if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) { |
2456 | 0 | if (verbose != 0) { |
2457 | 0 | mbedtls_printf("failed at %d\n", i); |
2458 | 0 | } |
2459 | |
|
2460 | 0 | ret = 1; |
2461 | 0 | goto cleanup; |
2462 | 0 | } |
2463 | 0 | } |
2464 | | |
2465 | 0 | if (verbose != 0) { |
2466 | 0 | mbedtls_printf("passed\n"); |
2467 | 0 | } |
2468 | |
|
2469 | 0 | cleanup: |
2470 | |
|
2471 | 0 | if (ret != 0 && verbose != 0) { |
2472 | 0 | mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret); |
2473 | 0 | } |
2474 | |
|
2475 | 0 | mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X); |
2476 | 0 | mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V); |
2477 | |
|
2478 | 0 | if (verbose != 0) { |
2479 | 0 | mbedtls_printf("\n"); |
2480 | 0 | } |
2481 | |
|
2482 | 0 | return ret; |
2483 | 0 | } |
2484 | | |
2485 | | #endif /* MBEDTLS_SELF_TEST */ |
2486 | | |
2487 | | #endif /* MBEDTLS_BIGNUM_C */ |