blob: c022a61d1786cb15cdd5275177f0710876e19ba1 [file] [log] [blame]
Jens Wiklander817466c2018-05-22 13:49:31 +02001/*
2 * Multi-precision integer library
3 *
Jerome Forissier79013242021-07-28 10:24:04 +02004 * Copyright The Mbed TLS Contributors
Tom Van Eyckb0563632024-06-13 16:20:14 +02005 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
Jens Wiklander817466c2018-05-22 13:49:31 +02006 */
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
Jerome Forissier79013242021-07-28 10:24:04 +020024#include "common.h"
Jens Wiklander817466c2018-05-22 13:49:31 +020025
26#if defined(MBEDTLS_BIGNUM_C)
27
28#include "mbedtls/bignum.h"
Jens Wiklander32b31802023-10-06 16:59:46 +020029#include "bignum_core.h"
30#include "bn_mul.h"
Jens Wiklander3d3b0592019-03-20 15:30:29 +010031#include "mbedtls/platform_util.h"
Jerome Forissier11fa71b2020-04-20 17:17:56 +020032#include "mbedtls/error.h"
Jerome Forissier039e02d2022-08-09 17:10:15 +020033#include "constant_time_internal.h"
Jens Wiklander817466c2018-05-22 13:49:31 +020034
Jerome Forissier039e02d2022-08-09 17:10:15 +020035#include <limits.h>
Jens Wiklander817466c2018-05-22 13:49:31 +020036#include <string.h>
37
Jens Wiklander817466c2018-05-22 13:49:31 +020038#include "mbedtls/platform.h"
Jens Wiklander817466c2018-05-22 13:49:31 +020039
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010040#include <mempool.h>
Jens Wiklander817466c2018-05-22 13:49:31 +020041
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010042void *mbedtls_mpi_mempool;
43
Tom Van Eyckb0563632024-06-13 16:20:14 +020044
45/*
46 * Conditionally select an MPI sign in constant time.
47 * (MPI sign is the field s in mbedtls_mpi. It is unsigned short and only 1 and -1 are valid
48 * values.)
49 */
50static inline signed short mbedtls_ct_mpi_sign_if(mbedtls_ct_condition_t cond,
51 signed short sign1, signed short sign2)
Jens Wiklander3d3b0592019-03-20 15:30:29 +010052{
Tom Van Eyckb0563632024-06-13 16:20:14 +020053 return (signed short) mbedtls_ct_uint_if(cond, sign1 + 1, sign2 + 1) - 1;
Jens Wiklander3d3b0592019-03-20 15:30:29 +010054}
55
Jens Wiklander817466c2018-05-22 13:49:31 +020056/*
Tom Van Eyckb0563632024-06-13 16:20:14 +020057 * Compare signed values in constant time
58 */
59int mbedtls_mpi_lt_mpi_ct(const mbedtls_mpi *X,
60 const mbedtls_mpi *Y,
61 unsigned *ret)
62{
63 mbedtls_ct_condition_t different_sign, X_is_negative, Y_is_negative, result;
64
65 if (X->n != Y->n) {
66 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
67 }
68
69 /*
70 * Set N_is_negative to MBEDTLS_CT_FALSE if N >= 0, MBEDTLS_CT_TRUE if N < 0.
71 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
72 */
73 X_is_negative = mbedtls_ct_bool((X->s & 2) >> 1);
74 Y_is_negative = mbedtls_ct_bool((Y->s & 2) >> 1);
75
76 /*
77 * If the signs are different, then the positive operand is the bigger.
78 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
79 * is false if X is positive (X_is_negative == 0).
80 */
81 different_sign = mbedtls_ct_bool_ne(X_is_negative, Y_is_negative); // true if different sign
82 result = mbedtls_ct_bool_and(different_sign, X_is_negative);
83
84 /*
85 * Assuming signs are the same, compare X and Y. We switch the comparison
86 * order if they are negative so that we get the right result, regardles of
87 * sign.
88 */
89
90 /* This array is used to conditionally swap the pointers in const time */
91 void * const p[2] = { X->p, Y->p };
92 size_t i = mbedtls_ct_size_if_else_0(X_is_negative, 1);
93 mbedtls_ct_condition_t lt = mbedtls_mpi_core_lt_ct(p[i], p[i ^ 1], X->n);
94
95 /*
96 * Store in result iff the signs are the same (i.e., iff different_sign == false). If
97 * the signs differ, result has already been set, so we don't change it.
98 */
99 result = mbedtls_ct_bool_or(result,
100 mbedtls_ct_bool_and(mbedtls_ct_bool_not(different_sign), lt));
101
102 *ret = mbedtls_ct_uint_if_else_0(result, 1);
103
104 return 0;
105}
106
107/*
108 * Conditionally assign X = Y, without leaking information
109 * about whether the assignment was made or not.
110 * (Leaking information about the respective sizes of X and Y is ok however.)
111 */
112#if defined(_MSC_VER) && defined(MBEDTLS_PLATFORM_IS_WINDOWS_ON_ARM64) && \
113 (_MSC_FULL_VER < 193131103)
114/*
115 * MSVC miscompiles this function if it's inlined prior to Visual Studio 2022 version 17.1. See:
116 * https://developercommunity.visualstudio.com/t/c-compiler-miscompiles-part-of-mbedtls-library-on/1646989
117 */
118__declspec(noinline)
119#endif
120int mbedtls_mpi_safe_cond_assign(mbedtls_mpi *X,
121 const mbedtls_mpi *Y,
122 unsigned char assign)
123{
124 int ret = 0;
125
126 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
127
128 {
129 mbedtls_ct_condition_t do_assign = mbedtls_ct_bool(assign);
130
131 X->s = mbedtls_ct_mpi_sign_if(do_assign, Y->s, X->s);
132
133 mbedtls_mpi_core_cond_assign(X->p, Y->p, Y->n, do_assign);
134
135 mbedtls_ct_condition_t do_not_assign = mbedtls_ct_bool_not(do_assign);
136 for (size_t i = Y->n; i < X->n; i++) {
137 X->p[i] = mbedtls_ct_mpi_uint_if_else_0(do_not_assign, X->p[i]);
138 }
139 }
140
141cleanup:
142 return ret;
143}
144
145/*
146 * Conditionally swap X and Y, without leaking information
147 * about whether the swap was made or not.
148 * Here it is not ok to simply swap the pointers, which would lead to
149 * different memory access patterns when X and Y are used afterwards.
150 */
151int mbedtls_mpi_safe_cond_swap(mbedtls_mpi *X,
152 mbedtls_mpi *Y,
153 unsigned char swap)
154{
155 int ret = 0;
156 int s;
157
158 if (X == Y) {
159 return 0;
160 }
161
162 mbedtls_ct_condition_t do_swap = mbedtls_ct_bool(swap);
163
164 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, Y->n));
165 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Y, X->n));
166
167 s = X->s;
168 X->s = mbedtls_ct_mpi_sign_if(do_swap, Y->s, X->s);
169 Y->s = mbedtls_ct_mpi_sign_if(do_swap, s, Y->s);
170
171 mbedtls_mpi_core_cond_swap(X->p, Y->p, X->n, do_swap);
172
173cleanup:
174 return ret;
175}
176
177/* Implementation that should never be optimized out by the compiler */
178#define mbedtls_mpi_zeroize_and_free(v, n) mbedtls_zeroize_and_free(v, ciL * (n))
179
180/*
181 * Implementation that should never be optimized out by the compiler.
182 * Reintroduced to allow use of mempool.
183 */
184#define mbedtls_mpi_zeroize(v, n) mbedtls_platform_zeroize(v, ciL * (n))
185
186/*
Jens Wiklander817466c2018-05-22 13:49:31 +0200187 * Initialize one MPI
188 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200189static void mpi_init(mbedtls_mpi *X, short use_mempool)
Jens Wiklander817466c2018-05-22 13:49:31 +0200190{
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100191 X->s = 1;
192 X->use_mempool = use_mempool;
193 X->n = 0;
194 X->p = NULL;
Jens Wiklander817466c2018-05-22 13:49:31 +0200195}
196
Jens Wiklander32b31802023-10-06 16:59:46 +0200197void mbedtls_mpi_init(mbedtls_mpi *X)
Jens Wiklander98bd5fe2018-11-08 11:18:22 +0100198{
Jens Wiklander32b31802023-10-06 16:59:46 +0200199 mpi_init(X, 0 /*use_mempool*/);
Jens Wiklander98bd5fe2018-11-08 11:18:22 +0100200}
201
Jens Wiklander32b31802023-10-06 16:59:46 +0200202void mbedtls_mpi_init_mempool(mbedtls_mpi *X)
Jens Wiklander98bd5fe2018-11-08 11:18:22 +0100203{
Jens Wiklander32b31802023-10-06 16:59:46 +0200204 mpi_init(X, !!mbedtls_mpi_mempool /*use_mempool*/);
Jens Wiklander98bd5fe2018-11-08 11:18:22 +0100205}
206
Jens Wiklander817466c2018-05-22 13:49:31 +0200207/*
208 * Unallocate one MPI
209 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200210void mbedtls_mpi_free(mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +0200211{
Jens Wiklander32b31802023-10-06 16:59:46 +0200212 if (X == NULL) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200213 return;
Jens Wiklander32b31802023-10-06 16:59:46 +0200214 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200215
Jens Wiklander32b31802023-10-06 16:59:46 +0200216 if (X->p != NULL) {
Tom Van Eyckb0563632024-06-13 16:20:14 +0200217 if(X->use_mempool) {
218 mbedtls_mpi_zeroize(X->p, X->n);
Jens Wiklander32b31802023-10-06 16:59:46 +0200219 mempool_free(mbedtls_mpi_mempool, X->p);
Tom Van Eyckb0563632024-06-13 16:20:14 +0200220 } else {
221 mbedtls_mpi_zeroize_and_free(X->p, X->n);
222 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200223 }
224
225 X->s = 1;
226 X->n = 0;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100227 X->p = NULL;
Jens Wiklander817466c2018-05-22 13:49:31 +0200228}
229
230/*
231 * Enlarge to the specified number of limbs
232 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200233int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
Jens Wiklander817466c2018-05-22 13:49:31 +0200234{
235 mbedtls_mpi_uint *p;
236
Jens Wiklander32b31802023-10-06 16:59:46 +0200237 if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
238 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
239 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200240
Jens Wiklander32b31802023-10-06 16:59:46 +0200241 if (X->n < nblimbs) {
242 if(X->use_mempool) {
243 p = mempool_alloc(mbedtls_mpi_mempool, nblimbs * ciL);
244 if(p == NULL)
245 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
246 memset(p, 0, nblimbs * ciL);
247 } else {
248 p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL);
249 if (p == NULL)
250 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100251 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200252
Jens Wiklander32b31802023-10-06 16:59:46 +0200253 if (X->p != NULL) {
254 memcpy(p, X->p, X->n * ciL);
Tom Van Eyckb0563632024-06-13 16:20:14 +0200255
256 if (X->use_mempool) {
257 mbedtls_mpi_zeroize(X->p, X->n);
Jens Wiklander32b31802023-10-06 16:59:46 +0200258 mempool_free(mbedtls_mpi_mempool, X->p);
Tom Van Eyckb0563632024-06-13 16:20:14 +0200259 } else {
260 mbedtls_mpi_zeroize_and_free(X->p, X->n);
261 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100262 }
263
Tom Van Eyckb0563632024-06-13 16:20:14 +0200264 /* nblimbs fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
265 * fits, and we've checked that nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
266 X->n = (unsigned short) nblimbs;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100267 X->p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +0200268 }
269
Jens Wiklander32b31802023-10-06 16:59:46 +0200270 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200271}
272
273/*
274 * Resize down as much as possible,
275 * while keeping at least the specified number of limbs
276 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200277int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
Jens Wiklander817466c2018-05-22 13:49:31 +0200278{
279 mbedtls_mpi_uint *p;
280 size_t i;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100281
Jens Wiklander32b31802023-10-06 16:59:46 +0200282 if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
283 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
284 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200285
Jerome Forissier5b25c762020-04-07 11:18:49 +0200286 /* Actually resize up if there are currently fewer than nblimbs limbs. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200287 if (X->n <= nblimbs) {
288 return mbedtls_mpi_grow(X, nblimbs);
289 }
Jerome Forissier5b25c762020-04-07 11:18:49 +0200290 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
Jens Wiklander817466c2018-05-22 13:49:31 +0200291
Jens Wiklander32b31802023-10-06 16:59:46 +0200292 for (i = X->n - 1; i > 0; i--) {
293 if (X->p[i] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200294 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200295 }
296 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200297 i++;
298
Jens Wiklander32b31802023-10-06 16:59:46 +0200299 if (i < nblimbs) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200300 i = nblimbs;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100301 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200302
Jens Wiklander32b31802023-10-06 16:59:46 +0200303 if (X->use_mempool) {
304 p = mempool_alloc(mbedtls_mpi_mempool, i * ciL);
305 if (p == NULL)
306 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
307 memset(p, 0, i * ciL);
308 } else {
309 if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL)
310 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
311 }
312
313 if (X->p != NULL) {
314 memcpy(p, X->p, i * ciL);
Tom Van Eyckb0563632024-06-13 16:20:14 +0200315
316 if (X->use_mempool) {
317 mbedtls_mpi_zeroize(X->p, X->n);
Jens Wiklander32b31802023-10-06 16:59:46 +0200318 mempool_free(mbedtls_mpi_mempool, X->p);
Tom Van Eyckb0563632024-06-13 16:20:14 +0200319 }
320 else {
321 mbedtls_mpi_zeroize_and_free(X->p, X->n);
322 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200323 }
324
Tom Van Eyckb0563632024-06-13 16:20:14 +0200325 /* i fits in n because we ensure that MBEDTLS_MPI_MAX_LIMBS
326 * fits, and we've checked that i <= nblimbs <= MBEDTLS_MPI_MAX_LIMBS. */
327 X->n = (unsigned short) i;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100328 X->p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +0200329
Jens Wiklander32b31802023-10-06 16:59:46 +0200330 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200331}
332
Jerome Forissier79013242021-07-28 10:24:04 +0200333/* Resize X to have exactly n limbs and set it to 0. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200334static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
Jerome Forissier79013242021-07-28 10:24:04 +0200335{
Jens Wiklander32b31802023-10-06 16:59:46 +0200336 if (limbs == 0) {
337 mbedtls_mpi_free(X);
338 return 0;
339 } else if (X->n == limbs) {
340 memset(X->p, 0, limbs * ciL);
Jerome Forissier79013242021-07-28 10:24:04 +0200341 X->s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +0200342 return 0;
343 } else {
344 mbedtls_mpi_free(X);
345 return mbedtls_mpi_grow(X, limbs);
Jerome Forissier79013242021-07-28 10:24:04 +0200346 }
347}
348
Jens Wiklander817466c2018-05-22 13:49:31 +0200349/*
Jerome Forissier79013242021-07-28 10:24:04 +0200350 * Copy the contents of Y into X.
351 *
352 * This function is not constant-time. Leading zeros in Y may be removed.
353 *
354 * Ensure that X does not shrink. This is not guaranteed by the public API,
Tom Van Eyckb0563632024-06-13 16:20:14 +0200355 * but some code in the bignum module might still rely on this property.
Jens Wiklander817466c2018-05-22 13:49:31 +0200356 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200357int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200358{
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100359 int ret = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200360 size_t i;
361
Jens Wiklander32b31802023-10-06 16:59:46 +0200362 if (X == Y) {
363 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200364 }
365
Jens Wiklander32b31802023-10-06 16:59:46 +0200366 if (Y->n == 0) {
367 if (X->n != 0) {
368 X->s = 1;
369 memset(X->p, 0, X->n * ciL);
370 }
371 return 0;
372 }
373
374 for (i = Y->n - 1; i > 0; i--) {
375 if (Y->p[i] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200376 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200377 }
378 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200379 i++;
380
381 X->s = Y->s;
382
Jens Wiklander32b31802023-10-06 16:59:46 +0200383 if (X->n < i) {
384 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i));
385 } else {
386 memset(X->p + i, 0, (X->n - i) * ciL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100387 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200388
Jens Wiklander32b31802023-10-06 16:59:46 +0200389 memcpy(X->p, Y->p, i * ciL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200390
391cleanup:
392
Jens Wiklander32b31802023-10-06 16:59:46 +0200393 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200394}
395
396/*
397 * Swap the contents of X and Y
398 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200399void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200400{
401 mbedtls_mpi T;
402
Jens Wiklander32b31802023-10-06 16:59:46 +0200403 memcpy(&T, X, sizeof(mbedtls_mpi));
404 memcpy(X, Y, sizeof(mbedtls_mpi));
405 memcpy(Y, &T, sizeof(mbedtls_mpi));
406}
407
408static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
409{
410 if (z >= 0) {
411 return z;
412 }
413 /* Take care to handle the most negative value (-2^(biL-1)) correctly.
414 * A naive -z would have undefined behavior.
415 * Write this in a way that makes popular compilers happy (GCC, Clang,
416 * MSVC). */
417 return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
Jens Wiklander817466c2018-05-22 13:49:31 +0200418}
419
Tom Van Eyckb0563632024-06-13 16:20:14 +0200420/* Convert x to a sign, i.e. to 1, if x is positive, or -1, if x is negative.
421 * This looks awkward but generates smaller code than (x < 0 ? -1 : 1) */
422#define TO_SIGN(x) ((mbedtls_mpi_sint) (((mbedtls_mpi_uint) x) >> (biL - 1)) * -2 + 1)
423
Jens Wiklander817466c2018-05-22 13:49:31 +0200424/*
425 * Set value from integer
426 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200427int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
Jens Wiklander817466c2018-05-22 13:49:31 +0200428{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200429 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200430
Jens Wiklander32b31802023-10-06 16:59:46 +0200431 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1));
432 memset(X->p, 0, X->n * ciL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200433
Jens Wiklander32b31802023-10-06 16:59:46 +0200434 X->p[0] = mpi_sint_abs(z);
Tom Van Eyckb0563632024-06-13 16:20:14 +0200435 X->s = TO_SIGN(z);
Jens Wiklander817466c2018-05-22 13:49:31 +0200436
437cleanup:
438
Jens Wiklander32b31802023-10-06 16:59:46 +0200439 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200440}
441
442/*
443 * Get a specific bit
444 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200445int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
Jens Wiklander817466c2018-05-22 13:49:31 +0200446{
Jens Wiklander32b31802023-10-06 16:59:46 +0200447 if (X->n * biL <= pos) {
448 return 0;
449 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200450
Jens Wiklander32b31802023-10-06 16:59:46 +0200451 return (X->p[pos / biL] >> (pos % biL)) & 0x01;
Jens Wiklander817466c2018-05-22 13:49:31 +0200452}
453
454/*
455 * Set a bit to a specific value of 0 or 1
456 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200457int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
Jens Wiklander817466c2018-05-22 13:49:31 +0200458{
459 int ret = 0;
460 size_t off = pos / biL;
461 size_t idx = pos % biL;
462
Jens Wiklander32b31802023-10-06 16:59:46 +0200463 if (val != 0 && val != 1) {
464 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Jens Wiklander817466c2018-05-22 13:49:31 +0200465 }
466
Jens Wiklander32b31802023-10-06 16:59:46 +0200467 if (X->n * biL <= pos) {
468 if (val == 0) {
469 return 0;
470 }
471
472 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1));
473 }
474
475 X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx);
Jens Wiklander817466c2018-05-22 13:49:31 +0200476 X->p[off] |= (mbedtls_mpi_uint) val << idx;
477
478cleanup:
479
Jens Wiklander32b31802023-10-06 16:59:46 +0200480 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200481}
482
483/*
484 * Return the number of less significant zero-bits
485 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200486size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +0200487{
Tom Van Eyckb0563632024-06-13 16:20:14 +0200488 size_t i;
Jens Wiklander817466c2018-05-22 13:49:31 +0200489
Tom Van Eyckb0563632024-06-13 16:20:14 +0200490#if defined(__has_builtin)
491#if (MBEDTLS_MPI_UINT_MAX == UINT_MAX) && __has_builtin(__builtin_ctz)
492 #define mbedtls_mpi_uint_ctz __builtin_ctz
493#elif (MBEDTLS_MPI_UINT_MAX == ULONG_MAX) && __has_builtin(__builtin_ctzl)
494 #define mbedtls_mpi_uint_ctz __builtin_ctzl
495#elif (MBEDTLS_MPI_UINT_MAX == ULLONG_MAX) && __has_builtin(__builtin_ctzll)
496 #define mbedtls_mpi_uint_ctz __builtin_ctzll
497#endif
498#endif
499
500#if defined(mbedtls_mpi_uint_ctz)
Jens Wiklander32b31802023-10-06 16:59:46 +0200501 for (i = 0; i < X->n; i++) {
Tom Van Eyckb0563632024-06-13 16:20:14 +0200502 if (X->p[i] != 0) {
503 return i * biL + mbedtls_mpi_uint_ctz(X->p[i]);
504 }
505 }
506#else
507 size_t count = 0;
508 for (i = 0; i < X->n; i++) {
509 for (size_t j = 0; j < biL; j++, count++) {
Jens Wiklander32b31802023-10-06 16:59:46 +0200510 if (((X->p[i] >> j) & 1) != 0) {
511 return count;
512 }
513 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200514 }
Tom Van Eyckb0563632024-06-13 16:20:14 +0200515#endif
Jens Wiklander817466c2018-05-22 13:49:31 +0200516
Jens Wiklander32b31802023-10-06 16:59:46 +0200517 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200518}
519
520/*
521 * Return the number of bits
522 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200523size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +0200524{
Jens Wiklander32b31802023-10-06 16:59:46 +0200525 return mbedtls_mpi_core_bitlen(X->p, X->n);
Jens Wiklander817466c2018-05-22 13:49:31 +0200526}
527
528/*
529 * Return the total size in bytes
530 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200531size_t mbedtls_mpi_size(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +0200532{
Jens Wiklander32b31802023-10-06 16:59:46 +0200533 return (mbedtls_mpi_bitlen(X) + 7) >> 3;
Jens Wiklander817466c2018-05-22 13:49:31 +0200534}
535
536/*
537 * Convert an ASCII character to digit value
538 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200539static int mpi_get_digit(mbedtls_mpi_uint *d, int radix, char c)
Jens Wiklander817466c2018-05-22 13:49:31 +0200540{
541 *d = 255;
542
Jens Wiklander32b31802023-10-06 16:59:46 +0200543 if (c >= 0x30 && c <= 0x39) {
544 *d = c - 0x30;
545 }
546 if (c >= 0x41 && c <= 0x46) {
547 *d = c - 0x37;
548 }
549 if (c >= 0x61 && c <= 0x66) {
550 *d = c - 0x57;
551 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200552
Jens Wiklander32b31802023-10-06 16:59:46 +0200553 if (*d >= (mbedtls_mpi_uint) radix) {
554 return MBEDTLS_ERR_MPI_INVALID_CHARACTER;
555 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200556
Jens Wiklander32b31802023-10-06 16:59:46 +0200557 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200558}
559
560/*
561 * Import from an ASCII string
562 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200563int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
Jens Wiklander817466c2018-05-22 13:49:31 +0200564{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200565 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200566 size_t i, j, slen, n;
Jerome Forissier79013242021-07-28 10:24:04 +0200567 int sign = 1;
Jens Wiklander817466c2018-05-22 13:49:31 +0200568 mbedtls_mpi_uint d;
569 mbedtls_mpi T;
570
Jens Wiklander32b31802023-10-06 16:59:46 +0200571 if (radix < 2 || radix > 16) {
572 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Jerome Forissier79013242021-07-28 10:24:04 +0200573 }
574
Jens Wiklander32b31802023-10-06 16:59:46 +0200575 mbedtls_mpi_init_mempool(&T);
576
577 if (s[0] == 0) {
578 mbedtls_mpi_free(X);
579 return 0;
580 }
581
582 if (s[0] == '-') {
Jerome Forissier79013242021-07-28 10:24:04 +0200583 ++s;
584 sign = -1;
585 }
586
Jens Wiklander32b31802023-10-06 16:59:46 +0200587 slen = strlen(s);
Jens Wiklander817466c2018-05-22 13:49:31 +0200588
Jens Wiklander32b31802023-10-06 16:59:46 +0200589 if (radix == 16) {
Tom Van Eyckb0563632024-06-13 16:20:14 +0200590 if (slen > SIZE_MAX >> 2) {
Jens Wiklander32b31802023-10-06 16:59:46 +0200591 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Jens Wiklander817466c2018-05-22 13:49:31 +0200592 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200593
Jens Wiklander32b31802023-10-06 16:59:46 +0200594 n = BITS_TO_LIMBS(slen << 2);
595
596 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n));
597 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
598
599 for (i = slen, j = 0; i > 0; i--, j++) {
600 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1]));
601 X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2);
602 }
603 } else {
604 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
605
606 for (i = 0; i < slen; i++) {
607 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i]));
608 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix));
609 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d));
Jens Wiklander817466c2018-05-22 13:49:31 +0200610 }
611 }
612
Jens Wiklander32b31802023-10-06 16:59:46 +0200613 if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) {
Jerome Forissier79013242021-07-28 10:24:04 +0200614 X->s = -1;
Jens Wiklander32b31802023-10-06 16:59:46 +0200615 }
Jerome Forissier79013242021-07-28 10:24:04 +0200616
Jens Wiklander817466c2018-05-22 13:49:31 +0200617cleanup:
618
Jens Wiklander32b31802023-10-06 16:59:46 +0200619 mbedtls_mpi_free(&T);
Jens Wiklander817466c2018-05-22 13:49:31 +0200620
Jens Wiklander32b31802023-10-06 16:59:46 +0200621 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200622}
623
624/*
Jerome Forissier5b25c762020-04-07 11:18:49 +0200625 * Helper to write the digits high-order first.
Jens Wiklander817466c2018-05-22 13:49:31 +0200626 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200627static int mpi_write_hlp(mbedtls_mpi *X, int radix,
628 char **p, const size_t buflen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200629{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200630 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200631 mbedtls_mpi_uint r;
Jerome Forissier5b25c762020-04-07 11:18:49 +0200632 size_t length = 0;
633 char *p_end = *p + buflen;
Jens Wiklander817466c2018-05-22 13:49:31 +0200634
Jens Wiklander32b31802023-10-06 16:59:46 +0200635 do {
636 if (length >= buflen) {
637 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
Jerome Forissier5b25c762020-04-07 11:18:49 +0200638 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200639
Jens Wiklander32b31802023-10-06 16:59:46 +0200640 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix));
641 MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix));
Jerome Forissier5b25c762020-04-07 11:18:49 +0200642 /*
643 * Write the residue in the current position, as an ASCII character.
644 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200645 if (r < 0xA) {
646 *(--p_end) = (char) ('0' + r);
647 } else {
648 *(--p_end) = (char) ('A' + (r - 0xA));
649 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200650
Jerome Forissier5b25c762020-04-07 11:18:49 +0200651 length++;
Jens Wiklander32b31802023-10-06 16:59:46 +0200652 } while (mbedtls_mpi_cmp_int(X, 0) != 0);
Jens Wiklander817466c2018-05-22 13:49:31 +0200653
Jens Wiklander32b31802023-10-06 16:59:46 +0200654 memmove(*p, p_end, length);
Jerome Forissier5b25c762020-04-07 11:18:49 +0200655 *p += length;
Jens Wiklander817466c2018-05-22 13:49:31 +0200656
657cleanup:
658
Jens Wiklander32b31802023-10-06 16:59:46 +0200659 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200660}
661
662/*
663 * Export into an ASCII string
664 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200665int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix,
666 char *buf, size_t buflen, size_t *olen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200667{
668 int ret = 0;
669 size_t n;
670 char *p;
671 mbedtls_mpi T;
672
Jens Wiklander32b31802023-10-06 16:59:46 +0200673 if (radix < 2 || radix > 16) {
674 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
675 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200676
Jens Wiklander32b31802023-10-06 16:59:46 +0200677 n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */
678 if (radix >= 4) {
679 n >>= 1; /* Number of 4-adic digits necessary to present
Jerome Forissier5b25c762020-04-07 11:18:49 +0200680 * `n`. If radix > 4, this might be a strict
681 * overapproximation of the number of
682 * radix-adic digits needed to present `n`. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200683 }
684 if (radix >= 16) {
685 n >>= 1; /* Number of hexadecimal digits necessary to
Jerome Forissier5b25c762020-04-07 11:18:49 +0200686 * present `n`. */
687
Jens Wiklander32b31802023-10-06 16:59:46 +0200688 }
Jerome Forissier5b25c762020-04-07 11:18:49 +0200689 n += 1; /* Terminating null byte */
690 n += 1; /* Compensate for the divisions above, which round down `n`
691 * in case it's not even. */
692 n += 1; /* Potential '-'-sign. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200693 n += (n & 1); /* Make n even to have enough space for hexadecimal writing,
Jerome Forissier5b25c762020-04-07 11:18:49 +0200694 * which always uses an even number of hex-digits. */
Jens Wiklander817466c2018-05-22 13:49:31 +0200695
Jens Wiklander32b31802023-10-06 16:59:46 +0200696 if (buflen < n) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200697 *olen = n;
Jens Wiklander32b31802023-10-06 16:59:46 +0200698 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
Jens Wiklander817466c2018-05-22 13:49:31 +0200699 }
700
701 p = buf;
Jens Wiklander32b31802023-10-06 16:59:46 +0200702 mbedtls_mpi_init_mempool(&T);
Jens Wiklander817466c2018-05-22 13:49:31 +0200703
Jens Wiklander32b31802023-10-06 16:59:46 +0200704 if (X->s == -1) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200705 *p++ = '-';
Jerome Forissier5b25c762020-04-07 11:18:49 +0200706 buflen--;
707 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200708
Jens Wiklander32b31802023-10-06 16:59:46 +0200709 if (radix == 16) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200710 int c;
711 size_t i, j, k;
712
Jens Wiklander32b31802023-10-06 16:59:46 +0200713 for (i = X->n, k = 0; i > 0; i--) {
714 for (j = ciL; j > 0; j--) {
715 c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF;
Jens Wiklander817466c2018-05-22 13:49:31 +0200716
Jens Wiklander32b31802023-10-06 16:59:46 +0200717 if (c == 0 && k == 0 && (i + j) != 2) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200718 continue;
Jens Wiklander32b31802023-10-06 16:59:46 +0200719 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200720
721 *(p++) = "0123456789ABCDEF" [c / 16];
722 *(p++) = "0123456789ABCDEF" [c % 16];
723 k = 1;
724 }
725 }
Jens Wiklander32b31802023-10-06 16:59:46 +0200726 } else {
727 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X));
Jens Wiklander817466c2018-05-22 13:49:31 +0200728
Jens Wiklander32b31802023-10-06 16:59:46 +0200729 if (T.s == -1) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200730 T.s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +0200731 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200732
Jens Wiklander32b31802023-10-06 16:59:46 +0200733 MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen));
Jens Wiklander817466c2018-05-22 13:49:31 +0200734 }
735
736 *p++ = '\0';
Tom Van Eyckb0563632024-06-13 16:20:14 +0200737 *olen = (size_t) (p - buf);
Jens Wiklander817466c2018-05-22 13:49:31 +0200738
739cleanup:
740
Jens Wiklander32b31802023-10-06 16:59:46 +0200741 mbedtls_mpi_free(&T);
Jens Wiklander817466c2018-05-22 13:49:31 +0200742
Jens Wiklander32b31802023-10-06 16:59:46 +0200743 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200744}
745
746#if defined(MBEDTLS_FS_IO)
747/*
748 * Read X from an opened file
749 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200750int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin)
Jens Wiklander817466c2018-05-22 13:49:31 +0200751{
752 mbedtls_mpi_uint d;
753 size_t slen;
754 char *p;
755 /*
756 * Buffer should have space for (short) label and decimal formatted MPI,
757 * newline characters and '\0'
758 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200759 char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
Jens Wiklander817466c2018-05-22 13:49:31 +0200760
Jens Wiklander32b31802023-10-06 16:59:46 +0200761 if (radix < 2 || radix > 16) {
762 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
763 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100764
Jens Wiklander32b31802023-10-06 16:59:46 +0200765 memset(s, 0, sizeof(s));
766 if (fgets(s, sizeof(s) - 1, fin) == NULL) {
767 return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
768 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200769
Jens Wiklander32b31802023-10-06 16:59:46 +0200770 slen = strlen(s);
771 if (slen == sizeof(s) - 2) {
772 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
773 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200774
Jens Wiklander32b31802023-10-06 16:59:46 +0200775 if (slen > 0 && s[slen - 1] == '\n') {
776 slen--; s[slen] = '\0';
777 }
778 if (slen > 0 && s[slen - 1] == '\r') {
779 slen--; s[slen] = '\0';
780 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200781
782 p = s + slen;
Jens Wiklander32b31802023-10-06 16:59:46 +0200783 while (p-- > s) {
784 if (mpi_get_digit(&d, radix, *p) != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200785 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200786 }
787 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200788
Jens Wiklander32b31802023-10-06 16:59:46 +0200789 return mbedtls_mpi_read_string(X, radix, p + 1);
Jens Wiklander817466c2018-05-22 13:49:31 +0200790}
791
792/*
793 * Write X into an opened file (or stdout if fout == NULL)
794 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200795int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout)
Jens Wiklander817466c2018-05-22 13:49:31 +0200796{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200797 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200798 size_t n, slen, plen;
799 /*
800 * Buffer should have space for (short) label and decimal formatted MPI,
801 * newline characters and '\0'
802 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200803 char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100804
Jens Wiklander32b31802023-10-06 16:59:46 +0200805 if (radix < 2 || radix > 16) {
806 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
807 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200808
Jens Wiklander32b31802023-10-06 16:59:46 +0200809 memset(s, 0, sizeof(s));
Jens Wiklander817466c2018-05-22 13:49:31 +0200810
Jens Wiklander32b31802023-10-06 16:59:46 +0200811 MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n));
Jens Wiklander817466c2018-05-22 13:49:31 +0200812
Jens Wiklander32b31802023-10-06 16:59:46 +0200813 if (p == NULL) {
814 p = "";
815 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200816
Jens Wiklander32b31802023-10-06 16:59:46 +0200817 plen = strlen(p);
818 slen = strlen(s);
Jens Wiklander817466c2018-05-22 13:49:31 +0200819 s[slen++] = '\r';
820 s[slen++] = '\n';
821
Jens Wiklander32b31802023-10-06 16:59:46 +0200822 if (fout != NULL) {
823 if (fwrite(p, 1, plen, fout) != plen ||
824 fwrite(s, 1, slen, fout) != slen) {
825 return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
826 }
827 } else {
828 mbedtls_printf("%s%s", p, s);
Jens Wiklander817466c2018-05-22 13:49:31 +0200829 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200830
831cleanup:
832
Jens Wiklander32b31802023-10-06 16:59:46 +0200833 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200834}
835#endif /* MBEDTLS_FS_IO */
836
837/*
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200838 * Import X from unsigned binary data, little endian
Jens Wiklander32b31802023-10-06 16:59:46 +0200839 *
840 * This function is guaranteed to return an MPI with exactly the necessary
841 * number of limbs (in particular, it does not skip 0s in the input).
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200842 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200843int mbedtls_mpi_read_binary_le(mbedtls_mpi *X,
844 const unsigned char *buf, size_t buflen)
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200845{
846 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +0200847 const size_t limbs = CHARS_TO_LIMBS(buflen);
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200848
849 /* Ensure that target MPI has exactly the necessary number of limbs */
Jens Wiklander32b31802023-10-06 16:59:46 +0200850 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200851
Jens Wiklander32b31802023-10-06 16:59:46 +0200852 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen));
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200853
854cleanup:
855
856 /*
857 * This function is also used to import keys. However, wiping the buffers
858 * upon failure is not necessary because failure only can happen before any
859 * input is copied.
860 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200861 return ret;
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200862}
863
864/*
Jens Wiklander817466c2018-05-22 13:49:31 +0200865 * Import X from unsigned binary data, big endian
Jens Wiklander32b31802023-10-06 16:59:46 +0200866 *
867 * This function is guaranteed to return an MPI with exactly the necessary
868 * number of limbs (in particular, it does not skip 0s in the input).
Jens Wiklander817466c2018-05-22 13:49:31 +0200869 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200870int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200871{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200872 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +0200873 const size_t limbs = CHARS_TO_LIMBS(buflen);
Jens Wiklander817466c2018-05-22 13:49:31 +0200874
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100875 /* Ensure that target MPI has exactly the necessary number of limbs */
Jens Wiklander32b31802023-10-06 16:59:46 +0200876 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
Jens Wiklander29762732019-04-17 12:28:43 +0200877
Jens Wiklander32b31802023-10-06 16:59:46 +0200878 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
Jens Wiklander817466c2018-05-22 13:49:31 +0200879
880cleanup:
881
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200882 /*
883 * This function is also used to import keys. However, wiping the buffers
884 * upon failure is not necessary because failure only can happen before any
885 * input is copied.
886 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200887 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200888}
889
890/*
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200891 * Export X into unsigned binary data, little endian
892 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200893int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X,
894 unsigned char *buf, size_t buflen)
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200895{
Jens Wiklander32b31802023-10-06 16:59:46 +0200896 return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen);
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200897}
898
899/*
Jens Wiklander817466c2018-05-22 13:49:31 +0200900 * Export X into unsigned binary data, big endian
901 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200902int mbedtls_mpi_write_binary(const mbedtls_mpi *X,
903 unsigned char *buf, size_t buflen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200904{
Jens Wiklander32b31802023-10-06 16:59:46 +0200905 return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
Jens Wiklander817466c2018-05-22 13:49:31 +0200906}
907
908/*
909 * Left-shift: X <<= count
910 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200911int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
Jens Wiklander817466c2018-05-22 13:49:31 +0200912{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200913 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Tom Van Eyckb0563632024-06-13 16:20:14 +0200914 size_t i;
Jens Wiklander817466c2018-05-22 13:49:31 +0200915
Jens Wiklander32b31802023-10-06 16:59:46 +0200916 i = mbedtls_mpi_bitlen(X) + count;
Jens Wiklander817466c2018-05-22 13:49:31 +0200917
Jens Wiklander32b31802023-10-06 16:59:46 +0200918 if (X->n * biL < i) {
919 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i)));
920 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200921
922 ret = 0;
923
Tom Van Eyckb0563632024-06-13 16:20:14 +0200924 mbedtls_mpi_core_shift_l(X->p, X->n, count);
Jens Wiklander817466c2018-05-22 13:49:31 +0200925cleanup:
926
Jens Wiklander32b31802023-10-06 16:59:46 +0200927 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200928}
929
930/*
931 * Right-shift: X >>= count
932 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200933int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
Jens Wiklander817466c2018-05-22 13:49:31 +0200934{
Jens Wiklander32b31802023-10-06 16:59:46 +0200935 if (X->n != 0) {
936 mbedtls_mpi_core_shift_r(X->p, X->n, count);
Jens Wiklander817466c2018-05-22 13:49:31 +0200937 }
Jens Wiklander32b31802023-10-06 16:59:46 +0200938 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200939}
940
941/*
942 * Compare unsigned values
943 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200944int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200945{
946 size_t i, j;
947
Jens Wiklander32b31802023-10-06 16:59:46 +0200948 for (i = X->n; i > 0; i--) {
949 if (X->p[i - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200950 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200951 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200952 }
953
Jens Wiklander32b31802023-10-06 16:59:46 +0200954 for (j = Y->n; j > 0; j--) {
955 if (Y->p[j - 1] != 0) {
956 break;
957 }
958 }
959
Tom Van Eyckb0563632024-06-13 16:20:14 +0200960 /* If i == j == 0, i.e. abs(X) == abs(Y),
961 * we end up returning 0 at the end of the function. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200962
963 if (i > j) {
964 return 1;
965 }
966 if (j > i) {
967 return -1;
968 }
969
970 for (; i > 0; i--) {
971 if (X->p[i - 1] > Y->p[i - 1]) {
972 return 1;
973 }
974 if (X->p[i - 1] < Y->p[i - 1]) {
975 return -1;
976 }
977 }
978
979 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200980}
981
982/*
983 * Compare signed values
984 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200985int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200986{
987 size_t i, j;
988
Jens Wiklander32b31802023-10-06 16:59:46 +0200989 for (i = X->n; i > 0; i--) {
990 if (X->p[i - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200991 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200992 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200993 }
994
Jens Wiklander32b31802023-10-06 16:59:46 +0200995 for (j = Y->n; j > 0; j--) {
996 if (Y->p[j - 1] != 0) {
997 break;
998 }
999 }
1000
1001 if (i == 0 && j == 0) {
1002 return 0;
1003 }
1004
1005 if (i > j) {
1006 return X->s;
1007 }
1008 if (j > i) {
1009 return -Y->s;
1010 }
1011
1012 if (X->s > 0 && Y->s < 0) {
1013 return 1;
1014 }
1015 if (Y->s > 0 && X->s < 0) {
1016 return -1;
1017 }
1018
1019 for (; i > 0; i--) {
1020 if (X->p[i - 1] > Y->p[i - 1]) {
1021 return X->s;
1022 }
1023 if (X->p[i - 1] < Y->p[i - 1]) {
1024 return -X->s;
1025 }
1026 }
1027
1028 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001029}
1030
1031/*
1032 * Compare signed values
1033 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001034int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
Jens Wiklander817466c2018-05-22 13:49:31 +02001035{
1036 mbedtls_mpi Y;
1037 mbedtls_mpi_uint p[1];
1038
Jens Wiklander32b31802023-10-06 16:59:46 +02001039 *p = mpi_sint_abs(z);
Tom Van Eyckb0563632024-06-13 16:20:14 +02001040 Y.s = TO_SIGN(z);
Jens Wiklander817466c2018-05-22 13:49:31 +02001041 Y.n = 1;
1042 Y.p = p;
1043
Jens Wiklander32b31802023-10-06 16:59:46 +02001044 return mbedtls_mpi_cmp_mpi(X, &Y);
Jens Wiklander817466c2018-05-22 13:49:31 +02001045}
1046
1047/*
1048 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1049 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001050int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001051{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001052 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +02001053 size_t j;
Tom Van Eyckb0563632024-06-13 16:20:14 +02001054 mbedtls_mpi_uint *p;
1055 mbedtls_mpi_uint c;
Jens Wiklander817466c2018-05-22 13:49:31 +02001056
Jens Wiklander32b31802023-10-06 16:59:46 +02001057 if (X == B) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001058 const mbedtls_mpi *T = A; A = X; B = T;
1059 }
1060
Jens Wiklander32b31802023-10-06 16:59:46 +02001061 if (X != A) {
1062 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1063 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001064
1065 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001066 * X must always be positive as a result of unsigned additions.
Jens Wiklander817466c2018-05-22 13:49:31 +02001067 */
1068 X->s = 1;
1069
Jens Wiklander32b31802023-10-06 16:59:46 +02001070 for (j = B->n; j > 0; j--) {
1071 if (B->p[j - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001072 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001073 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001074 }
1075
Jens Wiklander32b31802023-10-06 16:59:46 +02001076 /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
1077 * and B is 0 (of any size). */
1078 if (j == 0) {
1079 return 0;
1080 }
1081
1082 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j));
1083
1084 /* j is the number of non-zero limbs of B. Add those to X. */
1085
Tom Van Eyckb0563632024-06-13 16:20:14 +02001086 p = X->p;
Jens Wiklander32b31802023-10-06 16:59:46 +02001087
Tom Van Eyckb0563632024-06-13 16:20:14 +02001088 c = mbedtls_mpi_core_add(p, p, B->p, j);
Jens Wiklander32b31802023-10-06 16:59:46 +02001089
1090 p += j;
1091
1092 /* Now propagate any carry */
1093
1094 while (c != 0) {
1095 if (j >= X->n) {
1096 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
1097 p = X->p + j;
Jens Wiklander817466c2018-05-22 13:49:31 +02001098 }
1099
Jens Wiklander32b31802023-10-06 16:59:46 +02001100 *p += c; c = (*p < c); j++; p++;
Jens Wiklander817466c2018-05-22 13:49:31 +02001101 }
1102
1103cleanup:
1104
Jens Wiklander32b31802023-10-06 16:59:46 +02001105 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001106}
1107
1108/*
Jerome Forissier79013242021-07-28 10:24:04 +02001109 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
Jens Wiklander817466c2018-05-22 13:49:31 +02001110 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001111int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001112{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001113 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02001114 size_t n;
Jerome Forissier79013242021-07-28 10:24:04 +02001115 mbedtls_mpi_uint carry;
Jens Wiklander817466c2018-05-22 13:49:31 +02001116
Jens Wiklander32b31802023-10-06 16:59:46 +02001117 for (n = B->n; n > 0; n--) {
1118 if (B->p[n - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001119 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001120 }
1121 }
1122 if (n > A->n) {
Jerome Forissier79013242021-07-28 10:24:04 +02001123 /* B >= (2^ciL)^n > A */
1124 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1125 goto cleanup;
1126 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001127
Jens Wiklander32b31802023-10-06 16:59:46 +02001128 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n));
Jerome Forissier79013242021-07-28 10:24:04 +02001129
1130 /* Set the high limbs of X to match A. Don't touch the lower limbs
1131 * because X might be aliased to B, and we must not overwrite the
1132 * significant digits of B. */
Jens Wiklander32b31802023-10-06 16:59:46 +02001133 if (A->n > n && A != X) {
1134 memcpy(X->p + n, A->p + n, (A->n - n) * ciL);
1135 }
1136 if (X->n > A->n) {
1137 memset(X->p + A->n, 0, (X->n - A->n) * ciL);
1138 }
Jerome Forissier79013242021-07-28 10:24:04 +02001139
Jens Wiklander32b31802023-10-06 16:59:46 +02001140 carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
1141 if (carry != 0) {
1142 /* Propagate the carry through the rest of X. */
1143 carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n);
1144
1145 /* If we have further carry/borrow, the result is negative. */
1146 if (carry != 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001147 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1148 goto cleanup;
1149 }
Jerome Forissier79013242021-07-28 10:24:04 +02001150 }
1151
1152 /* X should always be positive as a result of unsigned subtractions. */
1153 X->s = 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02001154
1155cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02001156 return ret;
1157}
1158
1159/* Common function for signed addition and subtraction.
1160 * Calculate A + B * flip_B where flip_B is 1 or -1.
1161 */
1162static int add_sub_mpi(mbedtls_mpi *X,
1163 const mbedtls_mpi *A, const mbedtls_mpi *B,
1164 int flip_B)
1165{
1166 int ret, s;
Jens Wiklander32b31802023-10-06 16:59:46 +02001167
1168 s = A->s;
1169 if (A->s * B->s * flip_B < 0) {
1170 int cmp = mbedtls_mpi_cmp_abs(A, B);
1171 if (cmp >= 0) {
1172 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B));
1173 /* If |A| = |B|, the result is 0 and we must set the sign bit
1174 * to +1 regardless of which of A or B was negative. Otherwise,
1175 * since |A| > |B|, the sign is the sign of A. */
1176 X->s = cmp == 0 ? 1 : s;
1177 } else {
1178 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A));
1179 /* Since |A| < |B|, the sign is the opposite of A. */
1180 X->s = -s;
1181 }
1182 } else {
1183 MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B));
1184 X->s = s;
1185 }
1186
1187cleanup:
1188
1189 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001190}
1191
1192/*
1193 * Signed addition: X = A + B
1194 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001195int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001196{
Jens Wiklander32b31802023-10-06 16:59:46 +02001197 return add_sub_mpi(X, A, B, 1);
Jens Wiklander817466c2018-05-22 13:49:31 +02001198}
1199
1200/*
1201 * Signed subtraction: X = A - B
1202 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001203int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001204{
Jens Wiklander32b31802023-10-06 16:59:46 +02001205 return add_sub_mpi(X, A, B, -1);
Jens Wiklander817466c2018-05-22 13:49:31 +02001206}
1207
1208/*
1209 * Signed addition: X = A + b
1210 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001211int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001212{
Jerome Forissier039e02d2022-08-09 17:10:15 +02001213 mbedtls_mpi B;
Jens Wiklander817466c2018-05-22 13:49:31 +02001214 mbedtls_mpi_uint p[1];
1215
Jens Wiklander32b31802023-10-06 16:59:46 +02001216 p[0] = mpi_sint_abs(b);
Tom Van Eyckb0563632024-06-13 16:20:14 +02001217 B.s = TO_SIGN(b);
Jerome Forissier039e02d2022-08-09 17:10:15 +02001218 B.n = 1;
1219 B.p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +02001220
Jens Wiklander32b31802023-10-06 16:59:46 +02001221 return mbedtls_mpi_add_mpi(X, A, &B);
Jens Wiklander817466c2018-05-22 13:49:31 +02001222}
1223
1224/*
1225 * Signed subtraction: X = A - b
1226 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001227int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001228{
Jerome Forissier039e02d2022-08-09 17:10:15 +02001229 mbedtls_mpi B;
Jens Wiklander817466c2018-05-22 13:49:31 +02001230 mbedtls_mpi_uint p[1];
1231
Jens Wiklander32b31802023-10-06 16:59:46 +02001232 p[0] = mpi_sint_abs(b);
Tom Van Eyckb0563632024-06-13 16:20:14 +02001233 B.s = TO_SIGN(b);
Jerome Forissier039e02d2022-08-09 17:10:15 +02001234 B.n = 1;
1235 B.p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +02001236
Jens Wiklander32b31802023-10-06 16:59:46 +02001237 return mbedtls_mpi_sub_mpi(X, A, &B);
Jens Wiklander817466c2018-05-22 13:49:31 +02001238}
1239
1240/*
1241 * Baseline multiplication: X = A * B (HAC 14.12)
1242 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001243int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001244{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001245 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02001246 size_t i, j;
1247 mbedtls_mpi TA, TB;
Jerome Forissier79013242021-07-28 10:24:04 +02001248 int result_is_zero = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001249
Tom Van Eyckb0563632024-06-13 16:20:14 +02001250 mbedtls_mpi_init_mempool(&TA);
1251 mbedtls_mpi_init_mempool(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02001252
Jens Wiklander32b31802023-10-06 16:59:46 +02001253 if (X == A) {
1254 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
1255 }
1256 if (X == B) {
1257 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
1258 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001259
Jens Wiklander32b31802023-10-06 16:59:46 +02001260 for (i = A->n; i > 0; i--) {
1261 if (A->p[i - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001262 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001263 }
1264 }
1265 if (i == 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001266 result_is_zero = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001267 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001268
Jens Wiklander32b31802023-10-06 16:59:46 +02001269 for (j = B->n; j > 0; j--) {
1270 if (B->p[j - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001271 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001272 }
1273 }
1274 if (j == 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001275 result_is_zero = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001276 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001277
Jens Wiklander32b31802023-10-06 16:59:46 +02001278 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
1279 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
Jens Wiklander817466c2018-05-22 13:49:31 +02001280
Tom Van Eyckb0563632024-06-13 16:20:14 +02001281 mbedtls_mpi_core_mul(X->p, A->p, i, B->p, j);
Jens Wiklander817466c2018-05-22 13:49:31 +02001282
Jerome Forissier79013242021-07-28 10:24:04 +02001283 /* If the result is 0, we don't shortcut the operation, which reduces
1284 * but does not eliminate side channels leaking the zero-ness. We do
1285 * need to take care to set the sign bit properly since the library does
1286 * not fully support an MPI object with a value of 0 and s == -1. */
Jens Wiklander32b31802023-10-06 16:59:46 +02001287 if (result_is_zero) {
Jerome Forissier79013242021-07-28 10:24:04 +02001288 X->s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001289 } else {
Jerome Forissier79013242021-07-28 10:24:04 +02001290 X->s = A->s * B->s;
Jens Wiklander32b31802023-10-06 16:59:46 +02001291 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001292
1293cleanup:
1294
Jens Wiklander32b31802023-10-06 16:59:46 +02001295 mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA);
Jens Wiklander817466c2018-05-22 13:49:31 +02001296
Jens Wiklander32b31802023-10-06 16:59:46 +02001297 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001298}
1299
1300/*
1301 * Baseline multiplication: X = A * b
1302 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001303int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001304{
Jerome Forissier79013242021-07-28 10:24:04 +02001305 size_t n = A->n;
Jens Wiklander32b31802023-10-06 16:59:46 +02001306 while (n > 0 && A->p[n - 1] == 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001307 --n;
Jerome Forissier79013242021-07-28 10:24:04 +02001308 }
1309
Jens Wiklander32b31802023-10-06 16:59:46 +02001310 /* The general method below doesn't work if b==0. */
1311 if (b == 0 || n == 0) {
1312 return mbedtls_mpi_lset(X, 0);
1313 }
1314
1315 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
Jerome Forissier79013242021-07-28 10:24:04 +02001316 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1317 /* In general, A * b requires 1 limb more than b. If
1318 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1319 * number of limbs as A and the call to grow() is not required since
1320 * copy() will take care of the growth if needed. However, experimentally,
1321 * making the call to grow() unconditional causes slightly fewer
1322 * calls to calloc() in ECP code, presumably because it reuses the
1323 * same mpi for a while and this way the mpi is more likely to directly
Jens Wiklander32b31802023-10-06 16:59:46 +02001324 * grow to its final size.
1325 *
1326 * Note that calculating A*b as 0 + A*b doesn't work as-is because
1327 * A,X can be the same. */
1328 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1));
1329 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1330 mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
Jerome Forissier79013242021-07-28 10:24:04 +02001331
1332cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02001333 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001334}
1335
1336/*
1337 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1338 * mbedtls_mpi_uint divisor, d
1339 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001340static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1,
1341 mbedtls_mpi_uint u0,
1342 mbedtls_mpi_uint d,
1343 mbedtls_mpi_uint *r)
Jens Wiklander817466c2018-05-22 13:49:31 +02001344{
1345#if defined(MBEDTLS_HAVE_UDBL)
1346 mbedtls_t_udbl dividend, quotient;
1347#else
1348 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
Jens Wiklander32b31802023-10-06 16:59:46 +02001349 const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02001350 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1351 mbedtls_mpi_uint u0_msw, u0_lsw;
1352 size_t s;
1353#endif
1354
1355 /*
1356 * Check for overflow
1357 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001358 if (0 == d || u1 >= d) {
1359 if (r != NULL) {
1360 *r = ~(mbedtls_mpi_uint) 0u;
1361 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001362
Jens Wiklander32b31802023-10-06 16:59:46 +02001363 return ~(mbedtls_mpi_uint) 0u;
Jens Wiklander817466c2018-05-22 13:49:31 +02001364 }
1365
1366#if defined(MBEDTLS_HAVE_UDBL)
1367 dividend = (mbedtls_t_udbl) u1 << biL;
1368 dividend |= (mbedtls_t_udbl) u0;
1369 quotient = dividend / d;
Jens Wiklander32b31802023-10-06 16:59:46 +02001370 if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) {
1371 quotient = ((mbedtls_t_udbl) 1 << biL) - 1;
1372 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001373
Jens Wiklander32b31802023-10-06 16:59:46 +02001374 if (r != NULL) {
1375 *r = (mbedtls_mpi_uint) (dividend - (quotient * d));
1376 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001377
1378 return (mbedtls_mpi_uint) quotient;
1379#else
1380
1381 /*
1382 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1383 * Vol. 2 - Seminumerical Algorithms, Knuth
1384 */
1385
1386 /*
1387 * Normalize the divisor, d, and dividend, u0, u1
1388 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001389 s = mbedtls_mpi_core_clz(d);
Jens Wiklander817466c2018-05-22 13:49:31 +02001390 d = d << s;
1391
1392 u1 = u1 << s;
Jens Wiklander32b31802023-10-06 16:59:46 +02001393 u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02001394 u0 = u0 << s;
1395
1396 d1 = d >> biH;
1397 d0 = d & uint_halfword_mask;
1398
1399 u0_msw = u0 >> biH;
1400 u0_lsw = u0 & uint_halfword_mask;
1401
1402 /*
1403 * Find the first quotient and remainder
1404 */
1405 q1 = u1 / d1;
1406 r0 = u1 - d1 * q1;
1407
Jens Wiklander32b31802023-10-06 16:59:46 +02001408 while (q1 >= radix || (q1 * d0 > radix * r0 + u0_msw)) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001409 q1 -= 1;
1410 r0 += d1;
1411
Jens Wiklander32b31802023-10-06 16:59:46 +02001412 if (r0 >= radix) {
1413 break;
1414 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001415 }
1416
Jens Wiklander32b31802023-10-06 16:59:46 +02001417 rAX = (u1 * radix) + (u0_msw - q1 * d);
Jens Wiklander817466c2018-05-22 13:49:31 +02001418 q0 = rAX / d1;
1419 r0 = rAX - q0 * d1;
1420
Jens Wiklander32b31802023-10-06 16:59:46 +02001421 while (q0 >= radix || (q0 * d0 > radix * r0 + u0_lsw)) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001422 q0 -= 1;
1423 r0 += d1;
1424
Jens Wiklander32b31802023-10-06 16:59:46 +02001425 if (r0 >= radix) {
1426 break;
1427 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001428 }
1429
Jens Wiklander32b31802023-10-06 16:59:46 +02001430 if (r != NULL) {
1431 *r = (rAX * radix + u0_lsw - q0 * d) >> s;
1432 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001433
1434 quotient = q1 * radix + q0;
1435
1436 return quotient;
1437#endif
1438}
1439
1440/*
1441 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1442 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001443int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1444 const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001445{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001446 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02001447 size_t i, n, t, k;
1448 mbedtls_mpi X, Y, Z, T1, T2;
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001449 mbedtls_mpi_uint TP2[3];
Jens Wiklander817466c2018-05-22 13:49:31 +02001450
Jens Wiklander32b31802023-10-06 16:59:46 +02001451 if (mbedtls_mpi_cmp_int(B, 0) == 0) {
1452 return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1453 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001454
Jens Wiklander32b31802023-10-06 16:59:46 +02001455 mbedtls_mpi_init_mempool(&X); mbedtls_mpi_init_mempool(&Y);
1456 mbedtls_mpi_init_mempool(&Z); mbedtls_mpi_init_mempool(&T1);
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001457 /*
1458 * Avoid dynamic memory allocations for constant-size T2.
1459 *
1460 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1461 * so nobody increase the size of the MPI and we're safe to use an on-stack
1462 * buffer.
1463 */
1464 T2.s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001465 T2.n = sizeof(TP2) / sizeof(*TP2);
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001466 T2.p = TP2;
Jens Wiklander817466c2018-05-22 13:49:31 +02001467
Jens Wiklander32b31802023-10-06 16:59:46 +02001468 if (mbedtls_mpi_cmp_abs(A, B) < 0) {
1469 if (Q != NULL) {
1470 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0));
1471 }
1472 if (R != NULL) {
1473 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A));
1474 }
1475 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001476 }
1477
Jens Wiklander32b31802023-10-06 16:59:46 +02001478 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A));
1479 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B));
Jens Wiklander817466c2018-05-22 13:49:31 +02001480 X.s = Y.s = 1;
1481
Jens Wiklander32b31802023-10-06 16:59:46 +02001482 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2));
1483 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z, 0));
1484 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2));
Jens Wiklander817466c2018-05-22 13:49:31 +02001485
Jens Wiklander32b31802023-10-06 16:59:46 +02001486 k = mbedtls_mpi_bitlen(&Y) % biL;
1487 if (k < biL - 1) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001488 k = biL - 1 - k;
Jens Wiklander32b31802023-10-06 16:59:46 +02001489 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k));
1490 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k));
1491 } else {
1492 k = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001493 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001494
1495 n = X.n - 1;
1496 t = Y.n - 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001497 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t)));
Jens Wiklander817466c2018-05-22 13:49:31 +02001498
Jens Wiklander32b31802023-10-06 16:59:46 +02001499 while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001500 Z.p[n - t]++;
Jens Wiklander32b31802023-10-06 16:59:46 +02001501 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y));
Jens Wiklander817466c2018-05-22 13:49:31 +02001502 }
Jens Wiklander32b31802023-10-06 16:59:46 +02001503 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t)));
Jens Wiklander817466c2018-05-22 13:49:31 +02001504
Jens Wiklander32b31802023-10-06 16:59:46 +02001505 for (i = n; i > t; i--) {
1506 if (X.p[i] >= Y.p[t]) {
1507 Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u;
1508 } else {
1509 Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1],
1510 Y.p[t], NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001511 }
1512
Jens Wiklander32b31802023-10-06 16:59:46 +02001513 T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1514 T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001515 T2.p[2] = X.p[i];
1516
Jens Wiklander817466c2018-05-22 13:49:31 +02001517 Z.p[i - t - 1]++;
Jens Wiklander32b31802023-10-06 16:59:46 +02001518 do {
Jens Wiklander817466c2018-05-22 13:49:31 +02001519 Z.p[i - t - 1]--;
1520
Jens Wiklander32b31802023-10-06 16:59:46 +02001521 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0));
1522 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
Jens Wiklander817466c2018-05-22 13:49:31 +02001523 T1.p[1] = Y.p[t];
Jens Wiklander32b31802023-10-06 16:59:46 +02001524 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1]));
1525 } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0);
Jens Wiklander817466c2018-05-22 13:49:31 +02001526
Jens Wiklander32b31802023-10-06 16:59:46 +02001527 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1]));
1528 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1529 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1));
Jens Wiklander817466c2018-05-22 13:49:31 +02001530
Jens Wiklander32b31802023-10-06 16:59:46 +02001531 if (mbedtls_mpi_cmp_int(&X, 0) < 0) {
1532 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &Y));
1533 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1534 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1));
Jens Wiklander817466c2018-05-22 13:49:31 +02001535 Z.p[i - t - 1]--;
1536 }
1537 }
1538
Jens Wiklander32b31802023-10-06 16:59:46 +02001539 if (Q != NULL) {
1540 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z));
Jens Wiklander817466c2018-05-22 13:49:31 +02001541 Q->s = A->s * B->s;
1542 }
1543
Jens Wiklander32b31802023-10-06 16:59:46 +02001544 if (R != NULL) {
1545 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k));
Jens Wiklander817466c2018-05-22 13:49:31 +02001546 X.s = A->s;
Jens Wiklander32b31802023-10-06 16:59:46 +02001547 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X));
Jens Wiklander817466c2018-05-22 13:49:31 +02001548
Jens Wiklander32b31802023-10-06 16:59:46 +02001549 if (mbedtls_mpi_cmp_int(R, 0) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001550 R->s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001551 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001552 }
1553
1554cleanup:
1555
Jens Wiklander32b31802023-10-06 16:59:46 +02001556 mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
1557 mbedtls_mpi_free(&T1);
1558 mbedtls_platform_zeroize(TP2, sizeof(TP2));
Jens Wiklander817466c2018-05-22 13:49:31 +02001559
Jens Wiklander32b31802023-10-06 16:59:46 +02001560 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001561}
1562
1563/*
1564 * Division by int: A = Q * b + R
1565 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001566int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R,
1567 const mbedtls_mpi *A,
1568 mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001569{
Jerome Forissier039e02d2022-08-09 17:10:15 +02001570 mbedtls_mpi B;
Jens Wiklander817466c2018-05-22 13:49:31 +02001571 mbedtls_mpi_uint p[1];
1572
Jens Wiklander32b31802023-10-06 16:59:46 +02001573 p[0] = mpi_sint_abs(b);
Tom Van Eyckb0563632024-06-13 16:20:14 +02001574 B.s = TO_SIGN(b);
Jerome Forissier039e02d2022-08-09 17:10:15 +02001575 B.n = 1;
1576 B.p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +02001577
Jens Wiklander32b31802023-10-06 16:59:46 +02001578 return mbedtls_mpi_div_mpi(Q, R, A, &B);
Jens Wiklander817466c2018-05-22 13:49:31 +02001579}
1580
1581/*
1582 * Modulo: R = A mod B
1583 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001584int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001585{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001586 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02001587
Jens Wiklander32b31802023-10-06 16:59:46 +02001588 if (mbedtls_mpi_cmp_int(B, 0) < 0) {
1589 return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1590 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001591
Jens Wiklander32b31802023-10-06 16:59:46 +02001592 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B));
Jens Wiklander817466c2018-05-22 13:49:31 +02001593
Jens Wiklander32b31802023-10-06 16:59:46 +02001594 while (mbedtls_mpi_cmp_int(R, 0) < 0) {
1595 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B));
1596 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001597
Jens Wiklander32b31802023-10-06 16:59:46 +02001598 while (mbedtls_mpi_cmp_mpi(R, B) >= 0) {
1599 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B));
1600 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001601
1602cleanup:
1603
Jens Wiklander32b31802023-10-06 16:59:46 +02001604 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001605}
1606
1607/*
1608 * Modulo: r = A mod b
1609 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001610int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001611{
1612 size_t i;
1613 mbedtls_mpi_uint x, y, z;
1614
Jens Wiklander32b31802023-10-06 16:59:46 +02001615 if (b == 0) {
1616 return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1617 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001618
Jens Wiklander32b31802023-10-06 16:59:46 +02001619 if (b < 0) {
1620 return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1621 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001622
1623 /*
1624 * handle trivial cases
1625 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001626 if (b == 1 || A->n == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001627 *r = 0;
Jens Wiklander32b31802023-10-06 16:59:46 +02001628 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001629 }
1630
Jens Wiklander32b31802023-10-06 16:59:46 +02001631 if (b == 2) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001632 *r = A->p[0] & 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001633 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001634 }
1635
1636 /*
1637 * general case
1638 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001639 for (i = A->n, y = 0; i > 0; i--) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001640 x = A->p[i - 1];
Jens Wiklander32b31802023-10-06 16:59:46 +02001641 y = (y << biH) | (x >> biH);
Jens Wiklander817466c2018-05-22 13:49:31 +02001642 z = y / b;
1643 y -= z * b;
1644
1645 x <<= biH;
Jens Wiklander32b31802023-10-06 16:59:46 +02001646 y = (y << biH) | (x >> biH);
Jens Wiklander817466c2018-05-22 13:49:31 +02001647 z = y / b;
1648 y -= z * b;
1649 }
1650
1651 /*
1652 * If A is negative, then the current y represents a negative value.
1653 * Flipping it to the positive side.
1654 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001655 if (A->s < 0 && y != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001656 y = b - y;
Jens Wiklander32b31802023-10-06 16:59:46 +02001657 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001658
1659 *r = y;
1660
Jens Wiklander32b31802023-10-06 16:59:46 +02001661 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001662}
1663
Tom Van Eyckb0563632024-06-13 16:20:14 +02001664/**
1665 * \remark Replaced by our own because the original has been removed since
1666 * mbedtls v3.6.0.
1667*/
1668void mbedtls_mpi_montg_init(mbedtls_mpi_uint *mm, const mbedtls_mpi *N)
Jens Wiklander817466c2018-05-22 13:49:31 +02001669{
Jens Wiklander32b31802023-10-06 16:59:46 +02001670 *mm = mbedtls_mpi_core_montmul_init(N->p);
Jens Wiklander817466c2018-05-22 13:49:31 +02001671}
1672
Jerome Forissier79013242021-07-28 10:24:04 +02001673/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
Tom Van Eyckb0563632024-06-13 16:20:14 +02001674 *
Jerome Forissier79013242021-07-28 10:24:04 +02001675 * \param[in,out] A One of the numbers to multiply.
1676 * It must have at least as many limbs as N
1677 * (A->n >= N->n), and any limbs beyond n are ignored.
1678 * On successful completion, A contains the result of
1679 * the multiplication A * B * R^-1 mod N where
1680 * R = (2^ciL)^n.
1681 * \param[in] B One of the numbers to multiply.
1682 * It must be nonzero and must not have more limbs than N
1683 * (B->n <= N->n).
Jens Wiklander32b31802023-10-06 16:59:46 +02001684 * \param[in] N The modulus. \p N must be odd.
Jerome Forissier79013242021-07-28 10:24:04 +02001685 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1686 * This is -N^-1 mod 2^ciL.
1687 * \param[in,out] T A bignum for temporary storage.
Jens Wiklander32b31802023-10-06 16:59:46 +02001688 * It must be at least twice the limb size of N plus 1
1689 * (T->n >= 2 * N->n + 1).
Jerome Forissier79013242021-07-28 10:24:04 +02001690 * Its initial content is unused and
1691 * its final content is indeterminate.
Jens Wiklander32b31802023-10-06 16:59:46 +02001692 * It does not get reallocated.
Tom Van Eyckb0563632024-06-13 16:20:14 +02001693 * \remark Replaced by our own because the original has been removed since
1694 * mbedtls v3.6.0.
Jens Wiklander817466c2018-05-22 13:49:31 +02001695 */
Tom Van Eyckb0563632024-06-13 16:20:14 +02001696void mbedtls_mpi_montmul(mbedtls_mpi *A, const mbedtls_mpi *B,
Jens Wiklander32b31802023-10-06 16:59:46 +02001697 const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1698 mbedtls_mpi *T)
Jens Wiklander817466c2018-05-22 13:49:31 +02001699{
Jens Wiklander32b31802023-10-06 16:59:46 +02001700 mbedtls_mpi_core_montmul(A->p, A->p, B->p, B->n, N->p, N->n, mm, T->p);
Jerome Forissier79013242021-07-28 10:24:04 +02001701}
Jens Wiklander817466c2018-05-22 13:49:31 +02001702
Tom Van Eyckb0563632024-06-13 16:20:14 +02001703/**
Jens Wiklander817466c2018-05-22 13:49:31 +02001704 * Montgomery reduction: A = A * R^-1 mod N
Jerome Forissier79013242021-07-28 10:24:04 +02001705 *
Tom Van Eyckb0563632024-06-13 16:20:14 +02001706 * See mbedtls_mpi_montmul() regarding constraints and guarantees on the parameters.
1707 *
1708 * \remark Replaced by our own because the original has been removed since
1709 * mbedtls v3.6.0.
Jens Wiklander817466c2018-05-22 13:49:31 +02001710 */
Tom Van Eyckb0563632024-06-13 16:20:14 +02001711void mbedtls_mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N,
Jens Wiklander32b31802023-10-06 16:59:46 +02001712 mbedtls_mpi_uint mm, mbedtls_mpi *T)
Jens Wiklander817466c2018-05-22 13:49:31 +02001713{
1714 mbedtls_mpi_uint z = 1;
1715 mbedtls_mpi U;
1716
1717 U.n = U.s = (int) z;
1718 U.p = &z;
1719
Tom Van Eyckb0563632024-06-13 16:20:14 +02001720 mbedtls_mpi_montmul(A, &U, N, mm, T);
Jerome Forissier79013242021-07-28 10:24:04 +02001721}
1722
Jerome Forissier79013242021-07-28 10:24:04 +02001723/**
1724 * Select an MPI from a table without leaking the index.
1725 *
1726 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
1727 * reads the entire table in order to avoid leaking the value of idx to an
1728 * attacker able to observe memory access patterns.
1729 *
1730 * \param[out] R Where to write the selected MPI.
1731 * \param[in] T The table to read from.
1732 * \param[in] T_size The number of elements in the table.
1733 * \param[in] idx The index of the element to select;
1734 * this must satisfy 0 <= idx < T_size.
1735 *
1736 * \return \c 0 on success, or a negative error code.
1737 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001738static int mpi_select(mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx)
Jerome Forissier79013242021-07-28 10:24:04 +02001739{
1740 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1741
Jens Wiklander32b31802023-10-06 16:59:46 +02001742 for (size_t i = 0; i < T_size; i++) {
1743 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(R, &T[i],
Tom Van Eyckb0563632024-06-13 16:20:14 +02001744 (unsigned char) mbedtls_ct_uint_eq(i, idx)));
Jerome Forissier79013242021-07-28 10:24:04 +02001745 }
Jerome Forissier79013242021-07-28 10:24:04 +02001746cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02001747 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001748}
1749
1750/*
1751 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1752 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001753int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A,
1754 const mbedtls_mpi *E, const mbedtls_mpi *N,
1755 mbedtls_mpi *prec_RR)
Jens Wiklander817466c2018-05-22 13:49:31 +02001756{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001757 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +02001758 size_t window_bitsize;
Jens Wiklander817466c2018-05-22 13:49:31 +02001759 size_t i, j, nblimbs;
1760 size_t bufsize, nbits;
Jens Wiklander32b31802023-10-06 16:59:46 +02001761 size_t exponent_bits_in_window = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001762 mbedtls_mpi_uint ei, mm, state;
Tom Van Eyckb0563632024-06-13 16:20:14 +02001763 mbedtls_mpi RR, T, W[(size_t) 1 << MBEDTLS_MPI_WINDOW_SIZE], WW, Apos;
Jens Wiklander817466c2018-05-22 13:49:31 +02001764 int neg;
1765
Jens Wiklander32b31802023-10-06 16:59:46 +02001766 if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
1767 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1768 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001769
Jens Wiklander32b31802023-10-06 16:59:46 +02001770 if (mbedtls_mpi_cmp_int(E, 0) < 0) {
1771 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1772 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001773
Jens Wiklander32b31802023-10-06 16:59:46 +02001774 if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS ||
1775 mbedtls_mpi_bitlen(N) > MBEDTLS_MPI_MAX_BITS) {
1776 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1777 }
Jerome Forissier79013242021-07-28 10:24:04 +02001778
Jens Wiklander817466c2018-05-22 13:49:31 +02001779 /*
1780 * Init temps and window size
1781 */
Tom Van Eyckb0563632024-06-13 16:20:14 +02001782 mbedtls_mpi_montg_init(&mm, N);
1783 mbedtls_mpi_init(&RR); mbedtls_mpi_init(&T);
1784 mbedtls_mpi_init(&Apos);
1785 mbedtls_mpi_init(&WW);
1786 memset(W, 0, sizeof(W));
Jens Wiklander817466c2018-05-22 13:49:31 +02001787
Jens Wiklander32b31802023-10-06 16:59:46 +02001788 i = mbedtls_mpi_bitlen(E);
Jens Wiklander817466c2018-05-22 13:49:31 +02001789
Jens Wiklander32b31802023-10-06 16:59:46 +02001790 window_bitsize = (i > 671) ? 6 : (i > 239) ? 5 :
1791 (i > 79) ? 4 : (i > 23) ? 3 : 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02001792
Jens Wiklander32b31802023-10-06 16:59:46 +02001793#if (MBEDTLS_MPI_WINDOW_SIZE < 6)
1794 if (window_bitsize > MBEDTLS_MPI_WINDOW_SIZE) {
1795 window_bitsize = MBEDTLS_MPI_WINDOW_SIZE;
1796 }
Jerome Forissier5b25c762020-04-07 11:18:49 +02001797#endif
Jens Wiklander817466c2018-05-22 13:49:31 +02001798
Jens Wiklander32b31802023-10-06 16:59:46 +02001799 const size_t w_table_used_size = (size_t) 1 << window_bitsize;
1800
Jens Wiklander32b31802023-10-06 16:59:46 +02001801 /*
1802 * This function is not constant-trace: its memory accesses depend on the
1803 * exponent value. To defend against timing attacks, callers (such as RSA
1804 * and DHM) should use exponent blinding. However this is not enough if the
1805 * adversary can find the exponent in a single trace, so this function
1806 * takes extra precautions against adversaries who can observe memory
1807 * access patterns.
1808 *
1809 * This function performs a series of multiplications by table elements and
1810 * squarings, and we want the prevent the adversary from finding out which
1811 * table element was used, and from distinguishing between multiplications
1812 * and squarings. Firstly, when multiplying by an element of the window
1813 * W[i], we do a constant-trace table lookup to obfuscate i. This leaves
1814 * squarings as having a different memory access patterns from other
Tom Van Eyckb0563632024-06-13 16:20:14 +02001815 * multiplications. So secondly, we put the accumulator in the table as
1816 * well, and also do a constant-trace table lookup to multiply by the
1817 * accumulator which is W[x_index].
Jens Wiklander32b31802023-10-06 16:59:46 +02001818 *
1819 * This way, all multiplications take the form of a lookup-and-multiply.
1820 * The number of lookup-and-multiply operations inside each iteration of
1821 * the main loop still depends on the bits of the exponent, but since the
1822 * other operations in the loop don't have an easily recognizable memory
1823 * trace, an adversary is unlikely to be able to observe the exact
1824 * patterns.
1825 *
1826 * An adversary may still be able to recover the exponent if they can
1827 * observe both memory accesses and branches. However, branch prediction
1828 * exploitation typically requires many traces of execution over the same
1829 * data, which is defeated by randomized blinding.
Jens Wiklander32b31802023-10-06 16:59:46 +02001830 */
1831 const size_t x_index = 0;
Tom Van Eyckb0563632024-06-13 16:20:14 +02001832 mbedtls_mpi_init(&W[x_index]);
Jens Wiklander32b31802023-10-06 16:59:46 +02001833
Jens Wiklander817466c2018-05-22 13:49:31 +02001834 j = N->n + 1;
Tom Van Eyckb0563632024-06-13 16:20:14 +02001835 /* All W[i] including the accumulator must have at least N->n limbs for
1836 * the mbedtls_mpi_montmul() and mbedtls_mpi_montred() calls later.
1837 * Here we ensure that
1838 * W[1] and the accumulator W[x_index] are large enough. later we'll grow
1839 * other W[i] to the same length. They must not be shrunk midway through
1840 * this function!
Jerome Forissier79013242021-07-28 10:24:04 +02001841 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001842 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[x_index], j));
Tom Van Eyckb0563632024-06-13 16:20:14 +02001843 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], j));
Jens Wiklander32b31802023-10-06 16:59:46 +02001844 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T, j * 2));
Jens Wiklander817466c2018-05-22 13:49:31 +02001845
1846 /*
1847 * Compensate for negative A (and correct at the end)
1848 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001849 neg = (A->s == -1);
1850 if (neg) {
1851 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Apos, A));
Jens Wiklander817466c2018-05-22 13:49:31 +02001852 Apos.s = 1;
1853 A = &Apos;
1854 }
1855
1856 /*
1857 * If 1st call, pre-compute R^2 mod N
1858 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001859 if (prec_RR == NULL || prec_RR->p == NULL) {
1860 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&RR, 1));
1861 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&RR, N->n * 2 * biL));
1862 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&RR, &RR, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02001863
Jens Wiklander32b31802023-10-06 16:59:46 +02001864 if (prec_RR != NULL) {
1865 memcpy(prec_RR, &RR, sizeof(mbedtls_mpi));
1866 }
1867 } else {
1868 memcpy(&RR, prec_RR, sizeof(mbedtls_mpi));
Jens Wiklander817466c2018-05-22 13:49:31 +02001869 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001870
1871 /*
1872 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1873 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001874 if (mbedtls_mpi_cmp_mpi(A, N) >= 0) {
1875 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&W[1], A, N));
Jerome Forissier79013242021-07-28 10:24:04 +02001876 /* This should be a no-op because W[1] is already that large before
1877 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
Tom Van Eyckb0563632024-06-13 16:20:14 +02001878 * in mbedtls_mpi_montmul() below, so let's make sure. */
Jens Wiklander32b31802023-10-06 16:59:46 +02001879 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], N->n + 1));
1880 } else {
1881 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[1], A));
Jerome Forissier79013242021-07-28 10:24:04 +02001882 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001883
Jerome Forissier79013242021-07-28 10:24:04 +02001884 /* Note that this is safe because W[1] always has at least N->n limbs
1885 * (it grew above and was preserved by mbedtls_mpi_copy()). */
Tom Van Eyckb0563632024-06-13 16:20:14 +02001886 mbedtls_mpi_montmul(&W[1], &RR, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001887
1888 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001889 * W[x_index] = R^2 * R^-1 mod N = R mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02001890 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001891 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[x_index], &RR));
Tom Van Eyckb0563632024-06-13 16:20:14 +02001892 mbedtls_mpi_montred(&W[x_index], N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001893
Jens Wiklander32b31802023-10-06 16:59:46 +02001894
1895 if (window_bitsize > 1) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001896 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001897 * W[i] = W[1] ^ i
1898 *
1899 * The first bit of the sliding window is always 1 and therefore we
1900 * only need to store the second half of the table.
1901 *
1902 * (There are two special elements in the table: W[0] for the
1903 * accumulator/result and W[1] for A in Montgomery form. Both of these
1904 * are already set at this point.)
Jens Wiklander817466c2018-05-22 13:49:31 +02001905 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001906 j = w_table_used_size / 2;
Jens Wiklander817466c2018-05-22 13:49:31 +02001907
Jens Wiklander32b31802023-10-06 16:59:46 +02001908 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[j], N->n + 1));
1909 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[j], &W[1]));
Jens Wiklander817466c2018-05-22 13:49:31 +02001910
Jens Wiklander32b31802023-10-06 16:59:46 +02001911 for (i = 0; i < window_bitsize - 1; i++) {
Tom Van Eyckb0563632024-06-13 16:20:14 +02001912 mbedtls_mpi_montmul(&W[j], &W[j], N, mm, &T);
Jens Wiklander32b31802023-10-06 16:59:46 +02001913 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001914
1915 /*
1916 * W[i] = W[i - 1] * W[1]
1917 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001918 for (i = j + 1; i < w_table_used_size; i++) {
1919 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[i], N->n + 1));
1920 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[i], &W[i - 1]));
Jens Wiklander817466c2018-05-22 13:49:31 +02001921
Tom Van Eyckb0563632024-06-13 16:20:14 +02001922 mbedtls_mpi_montmul(&W[i], &W[1], N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001923 }
1924 }
1925
1926 nblimbs = E->n;
1927 bufsize = 0;
1928 nbits = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001929 state = 0;
1930
Jens Wiklander32b31802023-10-06 16:59:46 +02001931 while (1) {
1932 if (bufsize == 0) {
1933 if (nblimbs == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001934 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001935 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001936
1937 nblimbs--;
1938
Jens Wiklander32b31802023-10-06 16:59:46 +02001939 bufsize = sizeof(mbedtls_mpi_uint) << 3;
Jens Wiklander817466c2018-05-22 13:49:31 +02001940 }
1941
1942 bufsize--;
1943
1944 ei = (E->p[nblimbs] >> bufsize) & 1;
1945
1946 /*
1947 * skip leading 0s
1948 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001949 if (ei == 0 && state == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001950 continue;
Jens Wiklander32b31802023-10-06 16:59:46 +02001951 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001952
Jens Wiklander32b31802023-10-06 16:59:46 +02001953 if (ei == 0 && state == 1) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001954 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001955 * out of window, square W[x_index]
Jens Wiklander817466c2018-05-22 13:49:31 +02001956 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001957 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
Tom Van Eyckb0563632024-06-13 16:20:14 +02001958 mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001959 continue;
1960 }
1961
1962 /*
1963 * add ei to current window
1964 */
1965 state = 2;
1966
1967 nbits++;
Jens Wiklander32b31802023-10-06 16:59:46 +02001968 exponent_bits_in_window |= (ei << (window_bitsize - nbits));
Jens Wiklander817466c2018-05-22 13:49:31 +02001969
Jens Wiklander32b31802023-10-06 16:59:46 +02001970 if (nbits == window_bitsize) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001971 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001972 * W[x_index] = W[x_index]^window_bitsize R^-1 mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02001973 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001974 for (i = 0; i < window_bitsize; i++) {
1975 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
1976 x_index));
Tom Van Eyckb0563632024-06-13 16:20:14 +02001977 mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander32b31802023-10-06 16:59:46 +02001978 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001979
1980 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001981 * W[x_index] = W[x_index] * W[exponent_bits_in_window] R^-1 mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02001982 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001983 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
1984 exponent_bits_in_window));
Tom Van Eyckb0563632024-06-13 16:20:14 +02001985 mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001986
1987 state--;
1988 nbits = 0;
Jens Wiklander32b31802023-10-06 16:59:46 +02001989 exponent_bits_in_window = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001990 }
1991 }
1992
1993 /*
1994 * process the remaining bits
1995 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001996 for (i = 0; i < nbits; i++) {
1997 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
Tom Van Eyckb0563632024-06-13 16:20:14 +02001998 mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001999
Jens Wiklander32b31802023-10-06 16:59:46 +02002000 exponent_bits_in_window <<= 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02002001
Jens Wiklander32b31802023-10-06 16:59:46 +02002002 if ((exponent_bits_in_window & ((size_t) 1 << window_bitsize)) != 0) {
2003 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, 1));
Tom Van Eyckb0563632024-06-13 16:20:14 +02002004 mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander32b31802023-10-06 16:59:46 +02002005 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002006 }
2007
2008 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02002009 * W[x_index] = A^E * R * R^-1 mod N = A^E mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02002010 */
Tom Van Eyckb0563632024-06-13 16:20:14 +02002011 mbedtls_mpi_montred(&W[x_index], N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02002012
Jens Wiklander32b31802023-10-06 16:59:46 +02002013 if (neg && E->n != 0 && (E->p[0] & 1) != 0) {
2014 W[x_index].s = -1;
2015 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&W[x_index], N, &W[x_index]));
Jens Wiklander817466c2018-05-22 13:49:31 +02002016 }
2017
Jens Wiklander32b31802023-10-06 16:59:46 +02002018 /*
2019 * Load the result in the output variable.
2020 */
Tom Van Eyckb0563632024-06-13 16:20:14 +02002021 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &W[x_index]));
Jens Wiklander32b31802023-10-06 16:59:46 +02002022
Jens Wiklander817466c2018-05-22 13:49:31 +02002023cleanup:
2024
Tom Van Eyckb0563632024-06-13 16:20:14 +02002025 /* The first bit of the sliding window is always 1 and therefore the first
2026 * half of the table was unused. */
2027 for (i = w_table_used_size/2; i < w_table_used_size; i++) {
2028 mbedtls_mpi_free(&W[i]);
2029 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002030
Tom Van Eyckb0563632024-06-13 16:20:14 +02002031 mbedtls_mpi_free(&W[x_index]);
2032 mbedtls_mpi_free(&W[1]);
Jens Wiklander32b31802023-10-06 16:59:46 +02002033 mbedtls_mpi_free(&T);
2034 mbedtls_mpi_free(&Apos);
2035 mbedtls_mpi_free(&WW);
Jens Wiklander817466c2018-05-22 13:49:31 +02002036
Jens Wiklander32b31802023-10-06 16:59:46 +02002037 if (prec_RR == NULL || prec_RR->p == NULL) {
2038 mbedtls_mpi_free(&RR);
2039 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002040
Jens Wiklander32b31802023-10-06 16:59:46 +02002041 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002042}
2043
2044/*
2045 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2046 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002047int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02002048{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002049 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02002050 size_t lz, lzt;
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002051 mbedtls_mpi TA, TB;
Jens Wiklander817466c2018-05-22 13:49:31 +02002052
Jens Wiklander32b31802023-10-06 16:59:46 +02002053 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02002054
Jens Wiklander32b31802023-10-06 16:59:46 +02002055 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A));
2056 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B));
Jens Wiklander817466c2018-05-22 13:49:31 +02002057
Jens Wiklander32b31802023-10-06 16:59:46 +02002058 lz = mbedtls_mpi_lsb(&TA);
2059 lzt = mbedtls_mpi_lsb(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02002060
Jerome Forissier79013242021-07-28 10:24:04 +02002061 /* The loop below gives the correct result when A==0 but not when B==0.
2062 * So have a special case for B==0. Leverage the fact that we just
2063 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
2064 * slightly more efficient than cmp_int(). */
Jens Wiklander32b31802023-10-06 16:59:46 +02002065 if (lzt == 0 && mbedtls_mpi_get_bit(&TB, 0) == 0) {
2066 ret = mbedtls_mpi_copy(G, A);
Jerome Forissier79013242021-07-28 10:24:04 +02002067 goto cleanup;
2068 }
2069
Jens Wiklander32b31802023-10-06 16:59:46 +02002070 if (lzt < lz) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002071 lz = lzt;
Jens Wiklander32b31802023-10-06 16:59:46 +02002072 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002073
Jens Wiklander817466c2018-05-22 13:49:31 +02002074 TA.s = TB.s = 1;
2075
Jerome Forissier79013242021-07-28 10:24:04 +02002076 /* We mostly follow the procedure described in HAC 14.54, but with some
2077 * minor differences:
2078 * - Sequences of multiplications or divisions by 2 are grouped into a
2079 * single shift operation.
2080 * - The procedure in HAC assumes that 0 < TB <= TA.
2081 * - The condition TB <= TA is not actually necessary for correctness.
2082 * TA and TB have symmetric roles except for the loop termination
2083 * condition, and the shifts at the beginning of the loop body
2084 * remove any significance from the ordering of TA vs TB before
2085 * the shifts.
2086 * - If TA = 0, the loop goes through 0 iterations and the result is
2087 * correctly TB.
2088 * - The case TB = 0 was short-circuited above.
2089 *
2090 * For the correctness proof below, decompose the original values of
2091 * A and B as
2092 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
2093 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
2094 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
2095 * and gcd(A',B') is odd or 0.
2096 *
2097 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
2098 * The code maintains the following invariant:
2099 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
2100 */
2101
2102 /* Proof that the loop terminates:
2103 * At each iteration, either the right-shift by 1 is made on a nonzero
2104 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
2105 * by at least 1, or the right-shift by 1 is made on zero and then
2106 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
2107 * since in that case TB is calculated from TB-TA with the condition TB>TA).
2108 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002109 while (mbedtls_mpi_cmp_int(&TA, 0) != 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02002110 /* Divisions by 2 preserve the invariant (I). */
Jens Wiklander32b31802023-10-06 16:59:46 +02002111 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, mbedtls_mpi_lsb(&TA)));
2112 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, mbedtls_mpi_lsb(&TB)));
Jens Wiklander817466c2018-05-22 13:49:31 +02002113
Jerome Forissier79013242021-07-28 10:24:04 +02002114 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
2115 * TA-TB is even so the division by 2 has an integer result.
2116 * Invariant (I) is preserved since any odd divisor of both TA and TB
2117 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
Jerome Forissier039e02d2022-08-09 17:10:15 +02002118 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
Jerome Forissier79013242021-07-28 10:24:04 +02002119 * divides TA.
2120 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002121 if (mbedtls_mpi_cmp_mpi(&TA, &TB) >= 0) {
2122 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TA, &TA, &TB));
2123 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, 1));
2124 } else {
2125 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TB, &TB, &TA));
2126 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002127 }
Jerome Forissier79013242021-07-28 10:24:04 +02002128 /* Note that one of TA or TB is still odd. */
Jens Wiklander817466c2018-05-22 13:49:31 +02002129 }
2130
Jerome Forissier79013242021-07-28 10:24:04 +02002131 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
2132 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
2133 * - If there was at least one loop iteration, then one of TA or TB is odd,
2134 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
2135 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
2136 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
2137 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
2138 */
2139
Jens Wiklander32b31802023-10-06 16:59:46 +02002140 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&TB, lz));
2141 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB));
Jens Wiklander817466c2018-05-22 13:49:31 +02002142
2143cleanup:
2144
Jens Wiklander32b31802023-10-06 16:59:46 +02002145 mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02002146
Jens Wiklander32b31802023-10-06 16:59:46 +02002147 return ret;
Jerome Forissier79013242021-07-28 10:24:04 +02002148}
2149
Jens Wiklander817466c2018-05-22 13:49:31 +02002150/*
2151 * Fill X with size bytes of random.
Jens Wiklander32b31802023-10-06 16:59:46 +02002152 * The bytes returned from the RNG are used in a specific order which
2153 * is suitable for deterministic ECDSA (see the specification of
2154 * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()).
Jens Wiklander817466c2018-05-22 13:49:31 +02002155 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002156int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size,
2157 int (*f_rng)(void *, unsigned char *, size_t),
2158 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002159{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002160 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +02002161 const size_t limbs = CHARS_TO_LIMBS(size);
Jerome Forissier5b25c762020-04-07 11:18:49 +02002162
Jerome Forissier5b25c762020-04-07 11:18:49 +02002163 /* Ensure that target MPI has exactly the necessary number of limbs */
Jens Wiklander32b31802023-10-06 16:59:46 +02002164 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
2165 if (size == 0) {
2166 return 0;
2167 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002168
Jens Wiklander32b31802023-10-06 16:59:46 +02002169 ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng);
Jens Wiklander817466c2018-05-22 13:49:31 +02002170
2171cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02002172 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002173}
2174
Jens Wiklander32b31802023-10-06 16:59:46 +02002175int mbedtls_mpi_random(mbedtls_mpi *X,
2176 mbedtls_mpi_sint min,
2177 const mbedtls_mpi *N,
2178 int (*f_rng)(void *, unsigned char *, size_t),
2179 void *p_rng)
Jerome Forissier79013242021-07-28 10:24:04 +02002180{
Jens Wiklander32b31802023-10-06 16:59:46 +02002181 if (min < 0) {
2182 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2183 }
2184 if (mbedtls_mpi_cmp_int(N, min) <= 0) {
2185 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2186 }
Jerome Forissier79013242021-07-28 10:24:04 +02002187
2188 /* Ensure that target MPI has exactly the same number of limbs
2189 * as the upper bound, even if the upper bound has leading zeros.
Jens Wiklander32b31802023-10-06 16:59:46 +02002190 * This is necessary for mbedtls_mpi_core_random. */
2191 int ret = mbedtls_mpi_resize_clear(X, N->n);
2192 if (ret != 0) {
2193 return ret;
Jerome Forissier79013242021-07-28 10:24:04 +02002194 }
Jerome Forissier79013242021-07-28 10:24:04 +02002195
Jens Wiklander32b31802023-10-06 16:59:46 +02002196 return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng);
Jerome Forissier79013242021-07-28 10:24:04 +02002197}
2198
Jens Wiklander817466c2018-05-22 13:49:31 +02002199/*
2200 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2201 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002202int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
Jens Wiklander817466c2018-05-22 13:49:31 +02002203{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002204 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02002205 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
2206
Jens Wiklander32b31802023-10-06 16:59:46 +02002207 if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
2208 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2209 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002210
Jens Wiklander32b31802023-10-06 16:59:46 +02002211 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TU);
2212 mbedtls_mpi_init_mempool(&U1); mbedtls_mpi_init_mempool(&U2);
2213 mbedtls_mpi_init_mempool(&G); mbedtls_mpi_init_mempool(&TB);
2214 mbedtls_mpi_init_mempool(&TV); mbedtls_mpi_init_mempool(&V1);
2215 mbedtls_mpi_init_mempool(&V2);
Jens Wiklander817466c2018-05-22 13:49:31 +02002216
Jens Wiklander32b31802023-10-06 16:59:46 +02002217 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002218
Jens Wiklander32b31802023-10-06 16:59:46 +02002219 if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002220 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2221 goto cleanup;
2222 }
2223
Jens Wiklander32b31802023-10-06 16:59:46 +02002224 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&TA, A, N));
2225 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA));
2226 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, N));
2227 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TV, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002228
Jens Wiklander32b31802023-10-06 16:59:46 +02002229 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U1, 1));
2230 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U2, 0));
2231 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V1, 0));
2232 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V2, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002233
Jens Wiklander32b31802023-10-06 16:59:46 +02002234 do {
2235 while ((TU.p[0] & 1) == 0) {
2236 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TU, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002237
Jens Wiklander32b31802023-10-06 16:59:46 +02002238 if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) {
2239 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB));
2240 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA));
Jens Wiklander817466c2018-05-22 13:49:31 +02002241 }
2242
Jens Wiklander32b31802023-10-06 16:59:46 +02002243 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U1, 1));
2244 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U2, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002245 }
2246
Jens Wiklander32b31802023-10-06 16:59:46 +02002247 while ((TV.p[0] & 1) == 0) {
2248 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TV, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002249
Jens Wiklander32b31802023-10-06 16:59:46 +02002250 if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) {
2251 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB));
2252 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA));
Jens Wiklander817466c2018-05-22 13:49:31 +02002253 }
2254
Jens Wiklander32b31802023-10-06 16:59:46 +02002255 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V1, 1));
2256 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V2, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002257 }
2258
Jens Wiklander32b31802023-10-06 16:59:46 +02002259 if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) {
2260 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV));
2261 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1));
2262 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2));
2263 } else {
2264 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU));
2265 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1));
2266 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2));
Jens Wiklander817466c2018-05-22 13:49:31 +02002267 }
Jens Wiklander32b31802023-10-06 16:59:46 +02002268 } while (mbedtls_mpi_cmp_int(&TU, 0) != 0);
2269
2270 while (mbedtls_mpi_cmp_int(&V1, 0) < 0) {
2271 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002272 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002273
Jens Wiklander32b31802023-10-06 16:59:46 +02002274 while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) {
2275 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, N));
2276 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002277
Jens Wiklander32b31802023-10-06 16:59:46 +02002278 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002279
2280cleanup:
2281
Jens Wiklander32b31802023-10-06 16:59:46 +02002282 mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TU); mbedtls_mpi_free(&U1); mbedtls_mpi_free(&U2);
2283 mbedtls_mpi_free(&G); mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TV);
2284 mbedtls_mpi_free(&V1); mbedtls_mpi_free(&V2);
Jens Wiklander817466c2018-05-22 13:49:31 +02002285
Jens Wiklander32b31802023-10-06 16:59:46 +02002286 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002287}
2288
2289#if defined(MBEDTLS_GENPRIME)
2290
Tom Van Eyckb0563632024-06-13 16:20:14 +02002291/* Gaps between primes, starting at 3. https://oeis.org/A001223 */
2292static const unsigned char small_prime_gaps[] = {
2293 2, 2, 4, 2, 4, 2, 4, 6,
2294 2, 6, 4, 2, 4, 6, 6, 2,
2295 6, 4, 2, 6, 4, 6, 8, 4,
2296 2, 4, 2, 4, 14, 4, 6, 2,
2297 10, 2, 6, 6, 4, 6, 6, 2,
2298 10, 2, 4, 2, 12, 12, 4, 2,
2299 4, 6, 2, 10, 6, 6, 6, 2,
2300 6, 4, 2, 10, 14, 4, 2, 4,
2301 14, 6, 10, 2, 4, 6, 8, 6,
2302 6, 4, 6, 8, 4, 8, 10, 2,
2303 10, 2, 6, 4, 6, 8, 4, 2,
2304 4, 12, 8, 4, 8, 4, 6, 12,
2305 2, 18, 6, 10, 6, 6, 2, 6,
2306 10, 6, 6, 2, 6, 6, 4, 2,
2307 12, 10, 2, 4, 6, 6, 2, 12,
2308 4, 6, 8, 10, 8, 10, 8, 6,
2309 6, 4, 8, 6, 4, 8, 4, 14,
2310 10, 12, 2, 10, 2, 4, 2, 10,
2311 14, 4, 2, 4, 14, 4, 2, 4,
2312 20, 4, 8, 10, 8, 4, 6, 6,
2313 14, 4, 6, 6, 8, 6, /*reaches 997*/
2314 0 /* the last entry is effectively unused */
Jens Wiklander817466c2018-05-22 13:49:31 +02002315};
2316
2317/*
2318 * Small divisors test (X must be positive)
2319 *
2320 * Return values:
2321 * 0: no small factor (possible prime, more tests needed)
2322 * 1: certain prime
2323 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2324 * other negative: error
2325 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002326static int mpi_check_small_factors(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +02002327{
2328 int ret = 0;
2329 size_t i;
2330 mbedtls_mpi_uint r;
Tom Van Eyckb0563632024-06-13 16:20:14 +02002331 unsigned p = 3; /* The first odd prime */
Jens Wiklander817466c2018-05-22 13:49:31 +02002332
Jens Wiklander32b31802023-10-06 16:59:46 +02002333 if ((X->p[0] & 1) == 0) {
2334 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2335 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002336
Tom Van Eyckb0563632024-06-13 16:20:14 +02002337 for (i = 0; i < sizeof(small_prime_gaps); p += small_prime_gaps[i], i++) {
2338 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, p));
Jens Wiklander32b31802023-10-06 16:59:46 +02002339 if (r == 0) {
Tom Van Eyckb0563632024-06-13 16:20:14 +02002340 if (mbedtls_mpi_cmp_int(X, p) == 0) {
2341 return 1;
2342 } else {
2343 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2344 }
Jens Wiklander32b31802023-10-06 16:59:46 +02002345 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002346 }
2347
2348cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02002349 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002350}
2351
2352/*
2353 * Miller-Rabin pseudo-primality test (HAC 4.24)
2354 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002355static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds,
2356 int (*f_rng)(void *, unsigned char *, size_t),
2357 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002358{
2359 int ret, count;
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002360 size_t i, j, k, s;
Jens Wiklander817466c2018-05-22 13:49:31 +02002361 mbedtls_mpi W, R, T, A, RR;
2362
Jens Wiklander32b31802023-10-06 16:59:46 +02002363 mbedtls_mpi_init_mempool(&W); mbedtls_mpi_init_mempool(&R);
2364 mbedtls_mpi_init_mempool(&T); mbedtls_mpi_init_mempool(&A);
2365 mbedtls_mpi_init_mempool(&RR);
Jens Wiklander817466c2018-05-22 13:49:31 +02002366
2367 /*
2368 * W = |X| - 1
2369 * R = W >> lsb( W )
2370 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002371 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1));
2372 s = mbedtls_mpi_lsb(&W);
2373 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W));
2374 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s));
Jens Wiklander817466c2018-05-22 13:49:31 +02002375
Jens Wiklander32b31802023-10-06 16:59:46 +02002376 for (i = 0; i < rounds; i++) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002377 /*
2378 * pick a random A, 1 < A < |X| - 1
2379 */
Jens Wiklander817466c2018-05-22 13:49:31 +02002380 count = 0;
2381 do {
Jens Wiklander32b31802023-10-06 16:59:46 +02002382 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng));
Jens Wiklander817466c2018-05-22 13:49:31 +02002383
Jens Wiklander32b31802023-10-06 16:59:46 +02002384 j = mbedtls_mpi_bitlen(&A);
2385 k = mbedtls_mpi_bitlen(&W);
Jens Wiklander817466c2018-05-22 13:49:31 +02002386 if (j > k) {
Jens Wiklander32b31802023-10-06 16:59:46 +02002387 A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02002388 }
2389
Jens Wiklander117cce92018-11-27 12:21:24 +01002390 if (count++ > 300) {
Jens Wiklander336e3292019-01-17 11:14:38 +01002391 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2392 goto cleanup;
Jens Wiklander817466c2018-05-22 13:49:31 +02002393 }
2394
Jens Wiklander32b31802023-10-06 16:59:46 +02002395 } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 ||
2396 mbedtls_mpi_cmp_int(&A, 1) <= 0);
Jens Wiklander817466c2018-05-22 13:49:31 +02002397
2398 /*
2399 * A = A^R mod |X|
2400 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002401 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR));
Jens Wiklander817466c2018-05-22 13:49:31 +02002402
Jens Wiklander32b31802023-10-06 16:59:46 +02002403 if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 ||
2404 mbedtls_mpi_cmp_int(&A, 1) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002405 continue;
Jens Wiklander32b31802023-10-06 16:59:46 +02002406 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002407
2408 j = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02002409 while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002410 /*
2411 * A = A * A mod |X|
2412 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002413 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A));
2414 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X));
Jens Wiklander817466c2018-05-22 13:49:31 +02002415
Jens Wiklander32b31802023-10-06 16:59:46 +02002416 if (mbedtls_mpi_cmp_int(&A, 1) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002417 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02002418 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002419
2420 j++;
2421 }
2422
2423 /*
2424 * not prime if A != |X| - 1 or A == 1
2425 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002426 if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 ||
2427 mbedtls_mpi_cmp_int(&A, 1) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002428 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2429 break;
2430 }
2431 }
2432
2433cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02002434 mbedtls_mpi_free(&W); mbedtls_mpi_free(&R);
2435 mbedtls_mpi_free(&T); mbedtls_mpi_free(&A);
2436 mbedtls_mpi_free(&RR);
Jens Wiklander817466c2018-05-22 13:49:31 +02002437
Jens Wiklander32b31802023-10-06 16:59:46 +02002438 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002439}
2440
2441/*
2442 * Pseudo-primality test: small factors, then Miller-Rabin
2443 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002444int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds,
2445 int (*f_rng)(void *, unsigned char *, size_t),
2446 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002447{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002448 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02002449 mbedtls_mpi XX;
2450
2451 XX.s = 1;
2452 XX.n = X->n;
2453 XX.p = X->p;
2454
Jens Wiklander32b31802023-10-06 16:59:46 +02002455 if (mbedtls_mpi_cmp_int(&XX, 0) == 0 ||
2456 mbedtls_mpi_cmp_int(&XX, 1) == 0) {
2457 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Jens Wiklander817466c2018-05-22 13:49:31 +02002458 }
2459
Jens Wiklander32b31802023-10-06 16:59:46 +02002460 if (mbedtls_mpi_cmp_int(&XX, 2) == 0) {
2461 return 0;
2462 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002463
Jens Wiklander32b31802023-10-06 16:59:46 +02002464 if ((ret = mpi_check_small_factors(&XX)) != 0) {
2465 if (ret == 1) {
2466 return 0;
2467 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002468
Jens Wiklander32b31802023-10-06 16:59:46 +02002469 return ret;
2470 }
2471
2472 return mpi_miller_rabin(&XX, rounds, f_rng, p_rng);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002473}
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002474
Jens Wiklander817466c2018-05-22 13:49:31 +02002475/*
2476 * Prime number generation
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002477 *
2478 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2479 * be either 1024 bits or 1536 bits long, and flags must contain
2480 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Jens Wiklander817466c2018-05-22 13:49:31 +02002481 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002482int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags,
2483 int (*f_rng)(void *, unsigned char *, size_t),
2484 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002485{
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002486#ifdef MBEDTLS_HAVE_INT64
2487// ceil(2^63.5)
2488#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2489#else
2490// ceil(2^31.5)
2491#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2492#endif
2493 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Jens Wiklander817466c2018-05-22 13:49:31 +02002494 size_t k, n;
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002495 int rounds;
Jens Wiklander817466c2018-05-22 13:49:31 +02002496 mbedtls_mpi_uint r;
2497 mbedtls_mpi Y;
2498
Jens Wiklander32b31802023-10-06 16:59:46 +02002499 if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) {
2500 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2501 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002502
Jens Wiklander32b31802023-10-06 16:59:46 +02002503 mbedtls_mpi_init_mempool(&Y);
Jens Wiklander817466c2018-05-22 13:49:31 +02002504
Jens Wiklander32b31802023-10-06 16:59:46 +02002505 n = BITS_TO_LIMBS(nbits);
Jens Wiklander817466c2018-05-22 13:49:31 +02002506
Jens Wiklander32b31802023-10-06 16:59:46 +02002507 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR) == 0) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002508 /*
2509 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2510 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002511 rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 :
2512 (nbits >= 650) ? 4 : (nbits >= 350) ? 8 :
2513 (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27);
2514 } else {
Jens Wiklander817466c2018-05-22 13:49:31 +02002515 /*
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002516 * 2^-100 error probability, number of rounds computed based on HAC,
2517 * fact 4.48
Jens Wiklander817466c2018-05-22 13:49:31 +02002518 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002519 rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 :
2520 (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 :
2521 (nbits >= 750) ? 8 : (nbits >= 500) ? 13 :
2522 (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002523 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002524
Jens Wiklander32b31802023-10-06 16:59:46 +02002525 while (1) {
2526 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng));
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002527 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
Jens Wiklander32b31802023-10-06 16:59:46 +02002528 if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) {
2529 continue;
2530 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002531
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002532 k = n * biL;
Jens Wiklander32b31802023-10-06 16:59:46 +02002533 if (k > nbits) {
2534 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits));
2535 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002536 X->p[0] |= 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02002537
Jens Wiklander32b31802023-10-06 16:59:46 +02002538 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) {
2539 ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng);
Jens Wiklander817466c2018-05-22 13:49:31 +02002540
Jens Wiklander32b31802023-10-06 16:59:46 +02002541 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002542 goto cleanup;
Jens Wiklander32b31802023-10-06 16:59:46 +02002543 }
2544 } else {
Jens Wiklander817466c2018-05-22 13:49:31 +02002545 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02002546 * A necessary condition for Y and X = 2Y + 1 to be prime
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002547 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2548 * Make sure it is satisfied, while keeping X = 3 mod 4
Jens Wiklander817466c2018-05-22 13:49:31 +02002549 */
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002550
2551 X->p[0] |= 2;
2552
Jens Wiklander32b31802023-10-06 16:59:46 +02002553 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3));
2554 if (r == 0) {
2555 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8));
2556 } else if (r == 1) {
2557 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4));
2558 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002559
2560 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
Jens Wiklander32b31802023-10-06 16:59:46 +02002561 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X));
2562 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, 1));
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002563
Jens Wiklander32b31802023-10-06 16:59:46 +02002564 while (1) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002565 /*
2566 * First, check small factors for X and Y
2567 * before doing Miller-Rabin on any of them
2568 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002569 if ((ret = mpi_check_small_factors(X)) == 0 &&
2570 (ret = mpi_check_small_factors(&Y)) == 0 &&
2571 (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng))
2572 == 0 &&
2573 (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng))
2574 == 0) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002575 goto cleanup;
Jens Wiklander32b31802023-10-06 16:59:46 +02002576 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002577
Jens Wiklander32b31802023-10-06 16:59:46 +02002578 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002579 goto cleanup;
Jens Wiklander32b31802023-10-06 16:59:46 +02002580 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002581
2582 /*
2583 * Next candidates. We want to preserve Y = (X-1) / 2 and
2584 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2585 * so up Y by 6 and X by 12.
2586 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002587 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12));
2588 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6));
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002589 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002590 }
2591 }
2592
2593cleanup:
2594
Jens Wiklander32b31802023-10-06 16:59:46 +02002595 mbedtls_mpi_free(&Y);
Jens Wiklander817466c2018-05-22 13:49:31 +02002596
Jens Wiklander32b31802023-10-06 16:59:46 +02002597 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002598}
2599
2600#endif /* MBEDTLS_GENPRIME */
2601
2602#if defined(MBEDTLS_SELF_TEST)
2603
2604#define GCD_PAIR_COUNT 3
2605
2606static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2607{
2608 { 693, 609, 21 },
2609 { 1764, 868, 28 },
2610 { 768454923, 542167814, 1 }
2611};
2612
2613/*
2614 * Checkup routine
2615 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002616int mbedtls_mpi_self_test(int verbose)
Jens Wiklander817466c2018-05-22 13:49:31 +02002617{
2618 int ret, i;
2619 mbedtls_mpi A, E, N, X, Y, U, V;
2620
Jens Wiklander32b31802023-10-06 16:59:46 +02002621 mbedtls_mpi_init_mempool(&A); mbedtls_mpi_init_mempool(&E);
2622 mbedtls_mpi_init_mempool(&N); mbedtls_mpi_init_mempool(&X);
2623 mbedtls_mpi_init_mempool(&Y); mbedtls_mpi_init_mempool(&U);
2624 mbedtls_mpi_init_mempool(&V);
Jens Wiklander817466c2018-05-22 13:49:31 +02002625
Jens Wiklander32b31802023-10-06 16:59:46 +02002626 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16,
2627 "EFE021C2645FD1DC586E69184AF4A31E" \
2628 "D5F53E93B5F123FA41680867BA110131" \
2629 "944FE7952E2517337780CB0DB80E61AA" \
2630 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002631
Jens Wiklander32b31802023-10-06 16:59:46 +02002632 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16,
2633 "B2E7EFD37075B9F03FF989C7C5051C20" \
2634 "34D2A323810251127E7BF8625A4F49A5" \
2635 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2636 "5B5C25763222FEFCCFC38B832366C29E"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002637
Jens Wiklander32b31802023-10-06 16:59:46 +02002638 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16,
2639 "0066A198186C18C10B2F5ED9B522752A" \
2640 "9830B69916E535C8F047518A889A43A5" \
2641 "94B6BED27A168D31D4A52F88925AA8F5"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002642
Jens Wiklander32b31802023-10-06 16:59:46 +02002643 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002644
Jens Wiklander32b31802023-10-06 16:59:46 +02002645 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2646 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2647 "9E857EA95A03512E2BAE7391688D264A" \
2648 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2649 "8001B72E848A38CAE1C65F78E56ABDEF" \
2650 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2651 "ECF677152EF804370C1A305CAF3B5BF1" \
2652 "30879B56C61DE584A0F53A2447A51E"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002653
Jens Wiklander32b31802023-10-06 16:59:46 +02002654 if (verbose != 0) {
2655 mbedtls_printf(" MPI test #1 (mul_mpi): ");
2656 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002657
Jens Wiklander32b31802023-10-06 16:59:46 +02002658 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2659 if (verbose != 0) {
2660 mbedtls_printf("failed\n");
2661 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002662
2663 ret = 1;
2664 goto cleanup;
2665 }
2666
Jens Wiklander32b31802023-10-06 16:59:46 +02002667 if (verbose != 0) {
2668 mbedtls_printf("passed\n");
2669 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002670
Jens Wiklander32b31802023-10-06 16:59:46 +02002671 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002672
Jens Wiklander32b31802023-10-06 16:59:46 +02002673 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2674 "256567336059E52CAE22925474705F39A94"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002675
Jens Wiklander32b31802023-10-06 16:59:46 +02002676 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16,
2677 "6613F26162223DF488E9CD48CC132C7A" \
2678 "0AC93C701B001B092E4E5B9F73BCD27B" \
2679 "9EE50D0657C77F374E903CDFA4C642"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002680
Jens Wiklander32b31802023-10-06 16:59:46 +02002681 if (verbose != 0) {
2682 mbedtls_printf(" MPI test #2 (div_mpi): ");
2683 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002684
Jens Wiklander32b31802023-10-06 16:59:46 +02002685 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 ||
2686 mbedtls_mpi_cmp_mpi(&Y, &V) != 0) {
2687 if (verbose != 0) {
2688 mbedtls_printf("failed\n");
2689 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002690
2691 ret = 1;
2692 goto cleanup;
2693 }
2694
Jens Wiklander32b31802023-10-06 16:59:46 +02002695 if (verbose != 0) {
2696 mbedtls_printf("passed\n");
2697 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002698
Jens Wiklander32b31802023-10-06 16:59:46 +02002699 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL));
Jens Wiklander817466c2018-05-22 13:49:31 +02002700
Jens Wiklander32b31802023-10-06 16:59:46 +02002701 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2702 "36E139AEA55215609D2816998ED020BB" \
2703 "BD96C37890F65171D948E9BC7CBAA4D9" \
2704 "325D24D6A3C12710F10A09FA08AB87"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002705
Jens Wiklander32b31802023-10-06 16:59:46 +02002706 if (verbose != 0) {
2707 mbedtls_printf(" MPI test #3 (exp_mod): ");
2708 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002709
Jens Wiklander32b31802023-10-06 16:59:46 +02002710 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2711 if (verbose != 0) {
2712 mbedtls_printf("failed\n");
2713 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002714
2715 ret = 1;
2716 goto cleanup;
2717 }
2718
Jens Wiklander32b31802023-10-06 16:59:46 +02002719 if (verbose != 0) {
2720 mbedtls_printf("passed\n");
2721 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002722
Jens Wiklander32b31802023-10-06 16:59:46 +02002723 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002724
Jens Wiklander32b31802023-10-06 16:59:46 +02002725 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2726 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2727 "C3DBA76456363A10869622EAC2DD84EC" \
2728 "C5B8A74DAC4D09E03B5E0BE779F2DF61"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002729
Jens Wiklander32b31802023-10-06 16:59:46 +02002730 if (verbose != 0) {
2731 mbedtls_printf(" MPI test #4 (inv_mod): ");
2732 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002733
Jens Wiklander32b31802023-10-06 16:59:46 +02002734 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2735 if (verbose != 0) {
2736 mbedtls_printf("failed\n");
2737 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002738
2739 ret = 1;
2740 goto cleanup;
2741 }
2742
Jens Wiklander32b31802023-10-06 16:59:46 +02002743 if (verbose != 0) {
2744 mbedtls_printf("passed\n");
2745 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002746
Jens Wiklander32b31802023-10-06 16:59:46 +02002747 if (verbose != 0) {
2748 mbedtls_printf(" MPI test #5 (simple gcd): ");
2749 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002750
Jens Wiklander32b31802023-10-06 16:59:46 +02002751 for (i = 0; i < GCD_PAIR_COUNT; i++) {
2752 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0]));
2753 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1]));
Jens Wiklander817466c2018-05-22 13:49:31 +02002754
Jens Wiklander32b31802023-10-06 16:59:46 +02002755 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y));
Jens Wiklander817466c2018-05-22 13:49:31 +02002756
Jens Wiklander32b31802023-10-06 16:59:46 +02002757 if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) {
2758 if (verbose != 0) {
2759 mbedtls_printf("failed at %d\n", i);
2760 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002761
2762 ret = 1;
2763 goto cleanup;
2764 }
2765 }
2766
Jens Wiklander32b31802023-10-06 16:59:46 +02002767 if (verbose != 0) {
2768 mbedtls_printf("passed\n");
2769 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002770
2771cleanup:
2772
Jens Wiklander32b31802023-10-06 16:59:46 +02002773 if (ret != 0 && verbose != 0) {
2774 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
2775 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002776
Jens Wiklander32b31802023-10-06 16:59:46 +02002777 mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X);
2778 mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V);
Jens Wiklander817466c2018-05-22 13:49:31 +02002779
Jens Wiklander32b31802023-10-06 16:59:46 +02002780 if (verbose != 0) {
2781 mbedtls_printf("\n");
2782 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002783
Jens Wiklander32b31802023-10-06 16:59:46 +02002784 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002785}
2786
2787#endif /* MBEDTLS_SELF_TEST */
2788
2789#endif /* MBEDTLS_BIGNUM_C */