blob: b6733b7d86080bdf2e2c226a1ddc5030ab7e664e [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
5 * SPDX-License-Identifier: Apache-2.0
Jens Wiklander817466c2018-05-22 13:49:31 +02006 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
Jens Wiklander817466c2018-05-22 13:49:31 +020018 */
19
20/*
21 * The following sources were referenced in the design of this Multi-precision
22 * Integer library:
23 *
24 * [1] Handbook of Applied Cryptography - 1997
25 * Menezes, van Oorschot and Vanstone
26 *
27 * [2] Multi-Precision Math
28 * Tom St Denis
29 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
30 *
31 * [3] GNU Multi-Precision Arithmetic Library
32 * https://gmplib.org/manual/index.html
33 *
34 */
35
Jerome Forissier79013242021-07-28 10:24:04 +020036#include "common.h"
Jens Wiklander817466c2018-05-22 13:49:31 +020037
38#if defined(MBEDTLS_BIGNUM_C)
39
40#include "mbedtls/bignum.h"
Jens Wiklander32b31802023-10-06 16:59:46 +020041#include "bignum_core.h"
42#include "bn_mul.h"
Jens Wiklander3d3b0592019-03-20 15:30:29 +010043#include "mbedtls/platform_util.h"
Jerome Forissier11fa71b2020-04-20 17:17:56 +020044#include "mbedtls/error.h"
Jerome Forissier039e02d2022-08-09 17:10:15 +020045#include "constant_time_internal.h"
Jens Wiklander817466c2018-05-22 13:49:31 +020046
Jerome Forissier039e02d2022-08-09 17:10:15 +020047#include <limits.h>
Jens Wiklander817466c2018-05-22 13:49:31 +020048#include <string.h>
49
Jens Wiklander817466c2018-05-22 13:49:31 +020050#include "mbedtls/platform.h"
Jens Wiklander817466c2018-05-22 13:49:31 +020051
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010052#include <mempool.h>
Jens Wiklanderb99a4a12019-04-17 12:25:20 +020053#include <util.h>
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010054
Jens Wiklander32b31802023-10-06 16:59:46 +020055#define MPI_VALIDATE_RET(cond) \
56 MBEDTLS_INTERNAL_VALIDATE_RET(cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA)
57#define MPI_VALIDATE(cond) \
58 MBEDTLS_INTERNAL_VALIDATE(cond)
Jens Wiklander817466c2018-05-22 13:49:31 +020059
Jens Wiklander32b31802023-10-06 16:59:46 +020060#define MPI_SIZE_T_MAX ((size_t) -1) /* SIZE_T_MAX is not standard */
Jens Wiklander817466c2018-05-22 13:49:31 +020061
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010062void *mbedtls_mpi_mempool;
63
Jens Wiklander3d3b0592019-03-20 15:30:29 +010064/* Implementation that should never be optimized out by the compiler */
Jens Wiklander32b31802023-10-06 16:59:46 +020065static void mbedtls_mpi_zeroize(mbedtls_mpi_uint *v, size_t n)
Jens Wiklander3d3b0592019-03-20 15:30:29 +010066{
Jens Wiklander32b31802023-10-06 16:59:46 +020067 mbedtls_platform_zeroize(v, ciL * n);
Jens Wiklander3d3b0592019-03-20 15:30:29 +010068}
69
Jens Wiklander817466c2018-05-22 13:49:31 +020070/*
71 * Initialize one MPI
72 */
Jens Wiklander32b31802023-10-06 16:59:46 +020073static void mpi_init(mbedtls_mpi *X, short use_mempool)
Jens Wiklander817466c2018-05-22 13:49:31 +020074{
Jens Wiklander32b31802023-10-06 16:59:46 +020075 MPI_VALIDATE(X != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +020076
Jens Wiklander3d3b0592019-03-20 15:30:29 +010077 X->s = 1;
78 X->use_mempool = use_mempool;
79 X->n = 0;
80 X->p = NULL;
Jens Wiklander817466c2018-05-22 13:49:31 +020081}
82
Jens Wiklander32b31802023-10-06 16:59:46 +020083void mbedtls_mpi_init(mbedtls_mpi *X)
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010084{
Jens Wiklander32b31802023-10-06 16:59:46 +020085 mpi_init(X, 0 /*use_mempool*/);
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010086}
87
Jens Wiklander32b31802023-10-06 16:59:46 +020088void mbedtls_mpi_init_mempool(mbedtls_mpi *X)
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010089{
Jens Wiklander32b31802023-10-06 16:59:46 +020090 mpi_init(X, !!mbedtls_mpi_mempool /*use_mempool*/);
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010091}
92
Jens Wiklander817466c2018-05-22 13:49:31 +020093/*
94 * Unallocate one MPI
95 */
Jens Wiklander32b31802023-10-06 16:59:46 +020096void mbedtls_mpi_free(mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +020097{
Jens Wiklander32b31802023-10-06 16:59:46 +020098 if (X == NULL) {
Jens Wiklander817466c2018-05-22 13:49:31 +020099 return;
Jens Wiklander32b31802023-10-06 16:59:46 +0200100 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200101
Jens Wiklander32b31802023-10-06 16:59:46 +0200102 if (X->p != NULL) {
103 mbedtls_mpi_zeroize(X->p, X->n);
104 if(X->use_mempool)
105 mempool_free(mbedtls_mpi_mempool, X->p);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100106 else
Jens Wiklander32b31802023-10-06 16:59:46 +0200107 mbedtls_free(X->p);
Jens Wiklander817466c2018-05-22 13:49:31 +0200108 }
109
110 X->s = 1;
111 X->n = 0;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100112 X->p = NULL;
Jens Wiklander817466c2018-05-22 13:49:31 +0200113}
114
115/*
116 * Enlarge to the specified number of limbs
117 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200118int mbedtls_mpi_grow(mbedtls_mpi *X, size_t nblimbs)
Jens Wiklander817466c2018-05-22 13:49:31 +0200119{
120 mbedtls_mpi_uint *p;
Jens Wiklander32b31802023-10-06 16:59:46 +0200121 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200122
Jens Wiklander32b31802023-10-06 16:59:46 +0200123 if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
124 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
125 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200126
Jens Wiklander32b31802023-10-06 16:59:46 +0200127 if (X->n < nblimbs) {
128 if(X->use_mempool) {
129 p = mempool_alloc(mbedtls_mpi_mempool, nblimbs * ciL);
130 if(p == NULL)
131 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
132 memset(p, 0, nblimbs * ciL);
133 } else {
134 p = (mbedtls_mpi_uint *) mbedtls_calloc(nblimbs, ciL);
135 if (p == NULL)
136 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100137 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200138
Jens Wiklander32b31802023-10-06 16:59:46 +0200139 if (X->p != NULL) {
140 memcpy(p, X->p, X->n * ciL);
141 mbedtls_mpi_zeroize(X->p, X->n);
142 if (X->use_mempool)
143 mempool_free(mbedtls_mpi_mempool, X->p);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100144 else
Jens Wiklander32b31802023-10-06 16:59:46 +0200145 mbedtls_free(X->p);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100146 }
147
148 X->n = nblimbs;
149 X->p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +0200150 }
151
Jens Wiklander32b31802023-10-06 16:59:46 +0200152 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200153}
154
155/*
156 * Resize down as much as possible,
157 * while keeping at least the specified number of limbs
158 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200159int mbedtls_mpi_shrink(mbedtls_mpi *X, size_t nblimbs)
Jens Wiklander817466c2018-05-22 13:49:31 +0200160{
161 mbedtls_mpi_uint *p;
162 size_t i;
Jens Wiklander32b31802023-10-06 16:59:46 +0200163 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100164
Jens Wiklander32b31802023-10-06 16:59:46 +0200165 if (nblimbs > MBEDTLS_MPI_MAX_LIMBS) {
166 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
167 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200168
Jerome Forissier5b25c762020-04-07 11:18:49 +0200169 /* Actually resize up if there are currently fewer than nblimbs limbs. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200170 if (X->n <= nblimbs) {
171 return mbedtls_mpi_grow(X, nblimbs);
172 }
Jerome Forissier5b25c762020-04-07 11:18:49 +0200173 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
Jens Wiklander817466c2018-05-22 13:49:31 +0200174
Jens Wiklander32b31802023-10-06 16:59:46 +0200175 for (i = X->n - 1; i > 0; i--) {
176 if (X->p[i] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200177 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200178 }
179 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200180 i++;
181
Jens Wiklander32b31802023-10-06 16:59:46 +0200182 if (i < nblimbs) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200183 i = nblimbs;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100184 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200185
Jens Wiklander32b31802023-10-06 16:59:46 +0200186 if (X->use_mempool) {
187 p = mempool_alloc(mbedtls_mpi_mempool, i * ciL);
188 if (p == NULL)
189 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
190 memset(p, 0, i * ciL);
191 } else {
192 if ((p = (mbedtls_mpi_uint *) mbedtls_calloc(i, ciL)) == NULL)
193 return MBEDTLS_ERR_MPI_ALLOC_FAILED;
194 }
195
196 if (X->p != NULL) {
197 memcpy(p, X->p, i * ciL);
198 mbedtls_mpi_zeroize(X->p, X->n);
199 if (X->use_mempool)
200 mempool_free(mbedtls_mpi_mempool, X->p);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100201 else
Jens Wiklander32b31802023-10-06 16:59:46 +0200202 mbedtls_free(X->p);
Jens Wiklander817466c2018-05-22 13:49:31 +0200203 }
204
Jens Wiklander18c51482018-11-12 13:53:08 +0100205 X->n = i;
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100206 X->p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +0200207
Jens Wiklander32b31802023-10-06 16:59:46 +0200208 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200209}
210
Jerome Forissier79013242021-07-28 10:24:04 +0200211/* Resize X to have exactly n limbs and set it to 0. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200212static int mbedtls_mpi_resize_clear(mbedtls_mpi *X, size_t limbs)
Jerome Forissier79013242021-07-28 10:24:04 +0200213{
Jens Wiklander32b31802023-10-06 16:59:46 +0200214 if (limbs == 0) {
215 mbedtls_mpi_free(X);
216 return 0;
217 } else if (X->n == limbs) {
218 memset(X->p, 0, limbs * ciL);
Jerome Forissier79013242021-07-28 10:24:04 +0200219 X->s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +0200220 return 0;
221 } else {
222 mbedtls_mpi_free(X);
223 return mbedtls_mpi_grow(X, limbs);
Jerome Forissier79013242021-07-28 10:24:04 +0200224 }
225}
226
Jens Wiklander817466c2018-05-22 13:49:31 +0200227/*
Jerome Forissier79013242021-07-28 10:24:04 +0200228 * Copy the contents of Y into X.
229 *
230 * This function is not constant-time. Leading zeros in Y may be removed.
231 *
232 * Ensure that X does not shrink. This is not guaranteed by the public API,
233 * but some code in the bignum module relies on this property, for example
234 * in mbedtls_mpi_exp_mod().
Jens Wiklander817466c2018-05-22 13:49:31 +0200235 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200236int mbedtls_mpi_copy(mbedtls_mpi *X, const mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200237{
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100238 int ret = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200239 size_t i;
Jens Wiklander32b31802023-10-06 16:59:46 +0200240 MPI_VALIDATE_RET(X != NULL);
241 MPI_VALIDATE_RET(Y != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200242
Jens Wiklander32b31802023-10-06 16:59:46 +0200243 if (X == Y) {
244 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200245 }
246
Jens Wiklander32b31802023-10-06 16:59:46 +0200247 if (Y->n == 0) {
248 if (X->n != 0) {
249 X->s = 1;
250 memset(X->p, 0, X->n * ciL);
251 }
252 return 0;
253 }
254
255 for (i = Y->n - 1; i > 0; i--) {
256 if (Y->p[i] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200257 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200258 }
259 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200260 i++;
261
262 X->s = Y->s;
263
Jens Wiklander32b31802023-10-06 16:59:46 +0200264 if (X->n < i) {
265 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i));
266 } else {
267 memset(X->p + i, 0, (X->n - i) * ciL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100268 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200269
Jens Wiklander32b31802023-10-06 16:59:46 +0200270 memcpy(X->p, Y->p, i * ciL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200271
272cleanup:
273
Jens Wiklander32b31802023-10-06 16:59:46 +0200274 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200275}
276
277/*
278 * Swap the contents of X and Y
279 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200280void mbedtls_mpi_swap(mbedtls_mpi *X, mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200281{
282 mbedtls_mpi T;
Jens Wiklander32b31802023-10-06 16:59:46 +0200283 MPI_VALIDATE(X != NULL);
284 MPI_VALIDATE(Y != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200285
Jens Wiklander32b31802023-10-06 16:59:46 +0200286 memcpy(&T, X, sizeof(mbedtls_mpi));
287 memcpy(X, Y, sizeof(mbedtls_mpi));
288 memcpy(Y, &T, sizeof(mbedtls_mpi));
289}
290
291static inline mbedtls_mpi_uint mpi_sint_abs(mbedtls_mpi_sint z)
292{
293 if (z >= 0) {
294 return z;
295 }
296 /* Take care to handle the most negative value (-2^(biL-1)) correctly.
297 * A naive -z would have undefined behavior.
298 * Write this in a way that makes popular compilers happy (GCC, Clang,
299 * MSVC). */
300 return (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z;
Jens Wiklander817466c2018-05-22 13:49:31 +0200301}
302
Jens Wiklander817466c2018-05-22 13:49:31 +0200303/*
304 * Set value from integer
305 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200306int mbedtls_mpi_lset(mbedtls_mpi *X, mbedtls_mpi_sint z)
Jens Wiklander817466c2018-05-22 13:49:31 +0200307{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200308 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +0200309 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200310
Jens Wiklander32b31802023-10-06 16:59:46 +0200311 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, 1));
312 memset(X->p, 0, X->n * ciL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200313
Jens Wiklander32b31802023-10-06 16:59:46 +0200314 X->p[0] = mpi_sint_abs(z);
315 X->s = (z < 0) ? -1 : 1;
Jens Wiklander817466c2018-05-22 13:49:31 +0200316
317cleanup:
318
Jens Wiklander32b31802023-10-06 16:59:46 +0200319 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200320}
321
322/*
323 * Get a specific bit
324 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200325int mbedtls_mpi_get_bit(const mbedtls_mpi *X, size_t pos)
Jens Wiklander817466c2018-05-22 13:49:31 +0200326{
Jens Wiklander32b31802023-10-06 16:59:46 +0200327 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100328
Jens Wiklander32b31802023-10-06 16:59:46 +0200329 if (X->n * biL <= pos) {
330 return 0;
331 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200332
Jens Wiklander32b31802023-10-06 16:59:46 +0200333 return (X->p[pos / biL] >> (pos % biL)) & 0x01;
Jens Wiklander817466c2018-05-22 13:49:31 +0200334}
335
336/*
337 * Set a bit to a specific value of 0 or 1
338 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200339int mbedtls_mpi_set_bit(mbedtls_mpi *X, size_t pos, unsigned char val)
Jens Wiklander817466c2018-05-22 13:49:31 +0200340{
341 int ret = 0;
342 size_t off = pos / biL;
343 size_t idx = pos % biL;
Jens Wiklander32b31802023-10-06 16:59:46 +0200344 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200345
Jens Wiklander32b31802023-10-06 16:59:46 +0200346 if (val != 0 && val != 1) {
347 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Jens Wiklander817466c2018-05-22 13:49:31 +0200348 }
349
Jens Wiklander32b31802023-10-06 16:59:46 +0200350 if (X->n * biL <= pos) {
351 if (val == 0) {
352 return 0;
353 }
354
355 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, off + 1));
356 }
357
358 X->p[off] &= ~((mbedtls_mpi_uint) 0x01 << idx);
Jens Wiklander817466c2018-05-22 13:49:31 +0200359 X->p[off] |= (mbedtls_mpi_uint) val << idx;
360
361cleanup:
362
Jens Wiklander32b31802023-10-06 16:59:46 +0200363 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200364}
365
366/*
367 * Return the number of less significant zero-bits
368 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200369size_t mbedtls_mpi_lsb(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +0200370{
371 size_t i, j, count = 0;
Jens Wiklander32b31802023-10-06 16:59:46 +0200372 MBEDTLS_INTERNAL_VALIDATE_RET(X != NULL, 0);
Jens Wiklander817466c2018-05-22 13:49:31 +0200373
Jens Wiklander32b31802023-10-06 16:59:46 +0200374 for (i = 0; i < X->n; i++) {
375 for (j = 0; j < biL; j++, count++) {
376 if (((X->p[i] >> j) & 1) != 0) {
377 return count;
378 }
379 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200380 }
381
Jens Wiklander32b31802023-10-06 16:59:46 +0200382 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200383}
384
385/*
386 * Return the number of bits
387 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200388size_t mbedtls_mpi_bitlen(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +0200389{
Jens Wiklander32b31802023-10-06 16:59:46 +0200390 return mbedtls_mpi_core_bitlen(X->p, X->n);
Jens Wiklander817466c2018-05-22 13:49:31 +0200391}
392
393/*
394 * Return the total size in bytes
395 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200396size_t mbedtls_mpi_size(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +0200397{
Jens Wiklander32b31802023-10-06 16:59:46 +0200398 return (mbedtls_mpi_bitlen(X) + 7) >> 3;
Jens Wiklander817466c2018-05-22 13:49:31 +0200399}
400
401/*
402 * Convert an ASCII character to digit value
403 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200404static int mpi_get_digit(mbedtls_mpi_uint *d, int radix, char c)
Jens Wiklander817466c2018-05-22 13:49:31 +0200405{
406 *d = 255;
407
Jens Wiklander32b31802023-10-06 16:59:46 +0200408 if (c >= 0x30 && c <= 0x39) {
409 *d = c - 0x30;
410 }
411 if (c >= 0x41 && c <= 0x46) {
412 *d = c - 0x37;
413 }
414 if (c >= 0x61 && c <= 0x66) {
415 *d = c - 0x57;
416 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200417
Jens Wiklander32b31802023-10-06 16:59:46 +0200418 if (*d >= (mbedtls_mpi_uint) radix) {
419 return MBEDTLS_ERR_MPI_INVALID_CHARACTER;
420 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200421
Jens Wiklander32b31802023-10-06 16:59:46 +0200422 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200423}
424
425/*
426 * Import from an ASCII string
427 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200428int mbedtls_mpi_read_string(mbedtls_mpi *X, int radix, const char *s)
Jens Wiklander817466c2018-05-22 13:49:31 +0200429{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200430 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200431 size_t i, j, slen, n;
Jerome Forissier79013242021-07-28 10:24:04 +0200432 int sign = 1;
Jens Wiklander817466c2018-05-22 13:49:31 +0200433 mbedtls_mpi_uint d;
434 mbedtls_mpi T;
Jens Wiklander32b31802023-10-06 16:59:46 +0200435 MPI_VALIDATE_RET(X != NULL);
436 MPI_VALIDATE_RET(s != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200437
Jens Wiklander32b31802023-10-06 16:59:46 +0200438 if (radix < 2 || radix > 16) {
439 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Jerome Forissier79013242021-07-28 10:24:04 +0200440 }
441
Jens Wiklander32b31802023-10-06 16:59:46 +0200442 mbedtls_mpi_init_mempool(&T);
443
444 if (s[0] == 0) {
445 mbedtls_mpi_free(X);
446 return 0;
447 }
448
449 if (s[0] == '-') {
Jerome Forissier79013242021-07-28 10:24:04 +0200450 ++s;
451 sign = -1;
452 }
453
Jens Wiklander32b31802023-10-06 16:59:46 +0200454 slen = strlen(s);
Jens Wiklander817466c2018-05-22 13:49:31 +0200455
Jens Wiklander32b31802023-10-06 16:59:46 +0200456 if (radix == 16) {
457 if (slen > MPI_SIZE_T_MAX >> 2) {
458 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Jens Wiklander817466c2018-05-22 13:49:31 +0200459 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200460
Jens Wiklander32b31802023-10-06 16:59:46 +0200461 n = BITS_TO_LIMBS(slen << 2);
462
463 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n));
464 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
465
466 for (i = slen, j = 0; i > 0; i--, j++) {
467 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i - 1]));
468 X->p[j / (2 * ciL)] |= d << ((j % (2 * ciL)) << 2);
469 }
470 } else {
471 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
472
473 for (i = 0; i < slen; i++) {
474 MBEDTLS_MPI_CHK(mpi_get_digit(&d, radix, s[i]));
475 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T, X, radix));
476 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, &T, d));
Jens Wiklander817466c2018-05-22 13:49:31 +0200477 }
478 }
479
Jens Wiklander32b31802023-10-06 16:59:46 +0200480 if (sign < 0 && mbedtls_mpi_bitlen(X) != 0) {
Jerome Forissier79013242021-07-28 10:24:04 +0200481 X->s = -1;
Jens Wiklander32b31802023-10-06 16:59:46 +0200482 }
Jerome Forissier79013242021-07-28 10:24:04 +0200483
Jens Wiklander817466c2018-05-22 13:49:31 +0200484cleanup:
485
Jens Wiklander32b31802023-10-06 16:59:46 +0200486 mbedtls_mpi_free(&T);
Jens Wiklander817466c2018-05-22 13:49:31 +0200487
Jens Wiklander32b31802023-10-06 16:59:46 +0200488 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200489}
490
491/*
Jerome Forissier5b25c762020-04-07 11:18:49 +0200492 * Helper to write the digits high-order first.
Jens Wiklander817466c2018-05-22 13:49:31 +0200493 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200494static int mpi_write_hlp(mbedtls_mpi *X, int radix,
495 char **p, const size_t buflen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200496{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200497 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200498 mbedtls_mpi_uint r;
Jerome Forissier5b25c762020-04-07 11:18:49 +0200499 size_t length = 0;
500 char *p_end = *p + buflen;
Jens Wiklander817466c2018-05-22 13:49:31 +0200501
Jens Wiklander32b31802023-10-06 16:59:46 +0200502 do {
503 if (length >= buflen) {
504 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
Jerome Forissier5b25c762020-04-07 11:18:49 +0200505 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200506
Jens Wiklander32b31802023-10-06 16:59:46 +0200507 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, radix));
508 MBEDTLS_MPI_CHK(mbedtls_mpi_div_int(X, NULL, X, radix));
Jerome Forissier5b25c762020-04-07 11:18:49 +0200509 /*
510 * Write the residue in the current position, as an ASCII character.
511 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200512 if (r < 0xA) {
513 *(--p_end) = (char) ('0' + r);
514 } else {
515 *(--p_end) = (char) ('A' + (r - 0xA));
516 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200517
Jerome Forissier5b25c762020-04-07 11:18:49 +0200518 length++;
Jens Wiklander32b31802023-10-06 16:59:46 +0200519 } while (mbedtls_mpi_cmp_int(X, 0) != 0);
Jens Wiklander817466c2018-05-22 13:49:31 +0200520
Jens Wiklander32b31802023-10-06 16:59:46 +0200521 memmove(*p, p_end, length);
Jerome Forissier5b25c762020-04-07 11:18:49 +0200522 *p += length;
Jens Wiklander817466c2018-05-22 13:49:31 +0200523
524cleanup:
525
Jens Wiklander32b31802023-10-06 16:59:46 +0200526 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200527}
528
529/*
530 * Export into an ASCII string
531 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200532int mbedtls_mpi_write_string(const mbedtls_mpi *X, int radix,
533 char *buf, size_t buflen, size_t *olen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200534{
535 int ret = 0;
536 size_t n;
537 char *p;
538 mbedtls_mpi T;
Jens Wiklander32b31802023-10-06 16:59:46 +0200539 MPI_VALIDATE_RET(X != NULL);
540 MPI_VALIDATE_RET(olen != NULL);
541 MPI_VALIDATE_RET(buflen == 0 || buf != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200542
Jens Wiklander32b31802023-10-06 16:59:46 +0200543 if (radix < 2 || radix > 16) {
544 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
545 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200546
Jens Wiklander32b31802023-10-06 16:59:46 +0200547 n = mbedtls_mpi_bitlen(X); /* Number of bits necessary to present `n`. */
548 if (radix >= 4) {
549 n >>= 1; /* Number of 4-adic digits necessary to present
Jerome Forissier5b25c762020-04-07 11:18:49 +0200550 * `n`. If radix > 4, this might be a strict
551 * overapproximation of the number of
552 * radix-adic digits needed to present `n`. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200553 }
554 if (radix >= 16) {
555 n >>= 1; /* Number of hexadecimal digits necessary to
Jerome Forissier5b25c762020-04-07 11:18:49 +0200556 * present `n`. */
557
Jens Wiklander32b31802023-10-06 16:59:46 +0200558 }
Jerome Forissier5b25c762020-04-07 11:18:49 +0200559 n += 1; /* Terminating null byte */
560 n += 1; /* Compensate for the divisions above, which round down `n`
561 * in case it's not even. */
562 n += 1; /* Potential '-'-sign. */
Jens Wiklander32b31802023-10-06 16:59:46 +0200563 n += (n & 1); /* Make n even to have enough space for hexadecimal writing,
Jerome Forissier5b25c762020-04-07 11:18:49 +0200564 * which always uses an even number of hex-digits. */
Jens Wiklander817466c2018-05-22 13:49:31 +0200565
Jens Wiklander32b31802023-10-06 16:59:46 +0200566 if (buflen < n) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200567 *olen = n;
Jens Wiklander32b31802023-10-06 16:59:46 +0200568 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
Jens Wiklander817466c2018-05-22 13:49:31 +0200569 }
570
571 p = buf;
Jens Wiklander32b31802023-10-06 16:59:46 +0200572 mbedtls_mpi_init_mempool(&T);
Jens Wiklander817466c2018-05-22 13:49:31 +0200573
Jens Wiklander32b31802023-10-06 16:59:46 +0200574 if (X->s == -1) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200575 *p++ = '-';
Jerome Forissier5b25c762020-04-07 11:18:49 +0200576 buflen--;
577 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200578
Jens Wiklander32b31802023-10-06 16:59:46 +0200579 if (radix == 16) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200580 int c;
581 size_t i, j, k;
582
Jens Wiklander32b31802023-10-06 16:59:46 +0200583 for (i = X->n, k = 0; i > 0; i--) {
584 for (j = ciL; j > 0; j--) {
585 c = (X->p[i - 1] >> ((j - 1) << 3)) & 0xFF;
Jens Wiklander817466c2018-05-22 13:49:31 +0200586
Jens Wiklander32b31802023-10-06 16:59:46 +0200587 if (c == 0 && k == 0 && (i + j) != 2) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200588 continue;
Jens Wiklander32b31802023-10-06 16:59:46 +0200589 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200590
591 *(p++) = "0123456789ABCDEF" [c / 16];
592 *(p++) = "0123456789ABCDEF" [c % 16];
593 k = 1;
594 }
595 }
Jens Wiklander32b31802023-10-06 16:59:46 +0200596 } else {
597 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T, X));
Jens Wiklander817466c2018-05-22 13:49:31 +0200598
Jens Wiklander32b31802023-10-06 16:59:46 +0200599 if (T.s == -1) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200600 T.s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +0200601 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200602
Jens Wiklander32b31802023-10-06 16:59:46 +0200603 MBEDTLS_MPI_CHK(mpi_write_hlp(&T, radix, &p, buflen));
Jens Wiklander817466c2018-05-22 13:49:31 +0200604 }
605
606 *p++ = '\0';
607 *olen = p - buf;
608
609cleanup:
610
Jens Wiklander32b31802023-10-06 16:59:46 +0200611 mbedtls_mpi_free(&T);
Jens Wiklander817466c2018-05-22 13:49:31 +0200612
Jens Wiklander32b31802023-10-06 16:59:46 +0200613 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200614}
615
616#if defined(MBEDTLS_FS_IO)
617/*
618 * Read X from an opened file
619 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200620int mbedtls_mpi_read_file(mbedtls_mpi *X, int radix, FILE *fin)
Jens Wiklander817466c2018-05-22 13:49:31 +0200621{
622 mbedtls_mpi_uint d;
623 size_t slen;
624 char *p;
625 /*
626 * Buffer should have space for (short) label and decimal formatted MPI,
627 * newline characters and '\0'
628 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200629 char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
Jens Wiklander817466c2018-05-22 13:49:31 +0200630
Jens Wiklander32b31802023-10-06 16:59:46 +0200631 MPI_VALIDATE_RET(X != NULL);
632 MPI_VALIDATE_RET(fin != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100633
Jens Wiklander32b31802023-10-06 16:59:46 +0200634 if (radix < 2 || radix > 16) {
635 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
636 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100637
Jens Wiklander32b31802023-10-06 16:59:46 +0200638 memset(s, 0, sizeof(s));
639 if (fgets(s, sizeof(s) - 1, fin) == NULL) {
640 return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
641 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200642
Jens Wiklander32b31802023-10-06 16:59:46 +0200643 slen = strlen(s);
644 if (slen == sizeof(s) - 2) {
645 return MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL;
646 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200647
Jens Wiklander32b31802023-10-06 16:59:46 +0200648 if (slen > 0 && s[slen - 1] == '\n') {
649 slen--; s[slen] = '\0';
650 }
651 if (slen > 0 && s[slen - 1] == '\r') {
652 slen--; s[slen] = '\0';
653 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200654
655 p = s + slen;
Jens Wiklander32b31802023-10-06 16:59:46 +0200656 while (p-- > s) {
657 if (mpi_get_digit(&d, radix, *p) != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200658 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200659 }
660 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200661
Jens Wiklander32b31802023-10-06 16:59:46 +0200662 return mbedtls_mpi_read_string(X, radix, p + 1);
Jens Wiklander817466c2018-05-22 13:49:31 +0200663}
664
665/*
666 * Write X into an opened file (or stdout if fout == NULL)
667 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200668int mbedtls_mpi_write_file(const char *p, const mbedtls_mpi *X, int radix, FILE *fout)
Jens Wiklander817466c2018-05-22 13:49:31 +0200669{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200670 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200671 size_t n, slen, plen;
672 /*
673 * Buffer should have space for (short) label and decimal formatted MPI,
674 * newline characters and '\0'
675 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200676 char s[MBEDTLS_MPI_RW_BUFFER_SIZE];
677 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100678
Jens Wiklander32b31802023-10-06 16:59:46 +0200679 if (radix < 2 || radix > 16) {
680 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
681 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200682
Jens Wiklander32b31802023-10-06 16:59:46 +0200683 memset(s, 0, sizeof(s));
Jens Wiklander817466c2018-05-22 13:49:31 +0200684
Jens Wiklander32b31802023-10-06 16:59:46 +0200685 MBEDTLS_MPI_CHK(mbedtls_mpi_write_string(X, radix, s, sizeof(s) - 2, &n));
Jens Wiklander817466c2018-05-22 13:49:31 +0200686
Jens Wiklander32b31802023-10-06 16:59:46 +0200687 if (p == NULL) {
688 p = "";
689 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200690
Jens Wiklander32b31802023-10-06 16:59:46 +0200691 plen = strlen(p);
692 slen = strlen(s);
Jens Wiklander817466c2018-05-22 13:49:31 +0200693 s[slen++] = '\r';
694 s[slen++] = '\n';
695
Jens Wiklander32b31802023-10-06 16:59:46 +0200696 if (fout != NULL) {
697 if (fwrite(p, 1, plen, fout) != plen ||
698 fwrite(s, 1, slen, fout) != slen) {
699 return MBEDTLS_ERR_MPI_FILE_IO_ERROR;
700 }
701 } else {
702 mbedtls_printf("%s%s", p, s);
Jens Wiklander817466c2018-05-22 13:49:31 +0200703 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200704
705cleanup:
706
Jens Wiklander32b31802023-10-06 16:59:46 +0200707 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200708}
709#endif /* MBEDTLS_FS_IO */
710
711/*
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200712 * Import X from unsigned binary data, little endian
Jens Wiklander32b31802023-10-06 16:59:46 +0200713 *
714 * This function is guaranteed to return an MPI with exactly the necessary
715 * number of limbs (in particular, it does not skip 0s in the input).
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200716 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200717int mbedtls_mpi_read_binary_le(mbedtls_mpi *X,
718 const unsigned char *buf, size_t buflen)
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200719{
720 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +0200721 const size_t limbs = CHARS_TO_LIMBS(buflen);
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200722
723 /* Ensure that target MPI has exactly the necessary number of limbs */
Jens Wiklander32b31802023-10-06 16:59:46 +0200724 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200725
Jens Wiklander32b31802023-10-06 16:59:46 +0200726 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_le(X->p, X->n, buf, buflen));
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200727
728cleanup:
729
730 /*
731 * This function is also used to import keys. However, wiping the buffers
732 * upon failure is not necessary because failure only can happen before any
733 * input is copied.
734 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200735 return ret;
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200736}
737
738/*
Jens Wiklander817466c2018-05-22 13:49:31 +0200739 * Import X from unsigned binary data, big endian
Jens Wiklander32b31802023-10-06 16:59:46 +0200740 *
741 * This function is guaranteed to return an MPI with exactly the necessary
742 * number of limbs (in particular, it does not skip 0s in the input).
Jens Wiklander817466c2018-05-22 13:49:31 +0200743 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200744int mbedtls_mpi_read_binary(mbedtls_mpi *X, const unsigned char *buf, size_t buflen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200745{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200746 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +0200747 const size_t limbs = CHARS_TO_LIMBS(buflen);
Jens Wiklander817466c2018-05-22 13:49:31 +0200748
Jens Wiklander32b31802023-10-06 16:59:46 +0200749 MPI_VALIDATE_RET(X != NULL);
750 MPI_VALIDATE_RET(buflen == 0 || buf != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200751
Jens Wiklander3d3b0592019-03-20 15:30:29 +0100752 /* Ensure that target MPI has exactly the necessary number of limbs */
Jens Wiklander32b31802023-10-06 16:59:46 +0200753 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
Jens Wiklander29762732019-04-17 12:28:43 +0200754
Jens Wiklander32b31802023-10-06 16:59:46 +0200755 MBEDTLS_MPI_CHK(mbedtls_mpi_core_read_be(X->p, X->n, buf, buflen));
Jens Wiklander817466c2018-05-22 13:49:31 +0200756
757cleanup:
758
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200759 /*
760 * This function is also used to import keys. However, wiping the buffers
761 * upon failure is not necessary because failure only can happen before any
762 * input is copied.
763 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200764 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200765}
766
767/*
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200768 * Export X into unsigned binary data, little endian
769 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200770int mbedtls_mpi_write_binary_le(const mbedtls_mpi *X,
771 unsigned char *buf, size_t buflen)
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200772{
Jens Wiklander32b31802023-10-06 16:59:46 +0200773 return mbedtls_mpi_core_write_le(X->p, X->n, buf, buflen);
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200774}
775
776/*
Jens Wiklander817466c2018-05-22 13:49:31 +0200777 * Export X into unsigned binary data, big endian
778 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200779int mbedtls_mpi_write_binary(const mbedtls_mpi *X,
780 unsigned char *buf, size_t buflen)
Jens Wiklander817466c2018-05-22 13:49:31 +0200781{
Jens Wiklander32b31802023-10-06 16:59:46 +0200782 return mbedtls_mpi_core_write_be(X->p, X->n, buf, buflen);
Jens Wiklander817466c2018-05-22 13:49:31 +0200783}
784
785/*
786 * Left-shift: X <<= count
787 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200788int mbedtls_mpi_shift_l(mbedtls_mpi *X, size_t count)
Jens Wiklander817466c2018-05-22 13:49:31 +0200789{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200790 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +0200791 size_t i, v0, t1;
792 mbedtls_mpi_uint r0 = 0, r1;
Jens Wiklander32b31802023-10-06 16:59:46 +0200793 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200794
Jens Wiklander32b31802023-10-06 16:59:46 +0200795 v0 = count / (biL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200796 t1 = count & (biL - 1);
797
Jens Wiklander32b31802023-10-06 16:59:46 +0200798 i = mbedtls_mpi_bitlen(X) + count;
Jens Wiklander817466c2018-05-22 13:49:31 +0200799
Jens Wiklander32b31802023-10-06 16:59:46 +0200800 if (X->n * biL < i) {
801 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, BITS_TO_LIMBS(i)));
802 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200803
804 ret = 0;
805
806 /*
807 * shift by count / limb_size
808 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200809 if (v0 > 0) {
810 for (i = X->n; i > v0; i--) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200811 X->p[i - 1] = X->p[i - v0 - 1];
Jens Wiklander32b31802023-10-06 16:59:46 +0200812 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200813
Jens Wiklander32b31802023-10-06 16:59:46 +0200814 for (; i > 0; i--) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200815 X->p[i - 1] = 0;
Jens Wiklander32b31802023-10-06 16:59:46 +0200816 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200817 }
818
819 /*
820 * shift by count % limb_size
821 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200822 if (t1 > 0) {
823 for (i = v0; i < X->n; i++) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200824 r1 = X->p[i] >> (biL - t1);
825 X->p[i] <<= t1;
826 X->p[i] |= r0;
827 r0 = r1;
828 }
829 }
830
831cleanup:
832
Jens Wiklander32b31802023-10-06 16:59:46 +0200833 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +0200834}
835
836/*
837 * Right-shift: X >>= count
838 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200839int mbedtls_mpi_shift_r(mbedtls_mpi *X, size_t count)
Jens Wiklander817466c2018-05-22 13:49:31 +0200840{
Jens Wiklander32b31802023-10-06 16:59:46 +0200841 MPI_VALIDATE_RET(X != NULL);
842 if (X->n != 0) {
843 mbedtls_mpi_core_shift_r(X->p, X->n, count);
Jens Wiklander817466c2018-05-22 13:49:31 +0200844 }
Jens Wiklander32b31802023-10-06 16:59:46 +0200845 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200846}
847
848/*
849 * Compare unsigned values
850 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200851int mbedtls_mpi_cmp_abs(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200852{
853 size_t i, j;
Jens Wiklander32b31802023-10-06 16:59:46 +0200854 MPI_VALIDATE_RET(X != NULL);
855 MPI_VALIDATE_RET(Y != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200856
Jens Wiklander32b31802023-10-06 16:59:46 +0200857 for (i = X->n; i > 0; i--) {
858 if (X->p[i - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200859 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200860 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200861 }
862
Jens Wiklander32b31802023-10-06 16:59:46 +0200863 for (j = Y->n; j > 0; j--) {
864 if (Y->p[j - 1] != 0) {
865 break;
866 }
867 }
868
869 if (i == 0 && j == 0) {
870 return 0;
871 }
872
873 if (i > j) {
874 return 1;
875 }
876 if (j > i) {
877 return -1;
878 }
879
880 for (; i > 0; i--) {
881 if (X->p[i - 1] > Y->p[i - 1]) {
882 return 1;
883 }
884 if (X->p[i - 1] < Y->p[i - 1]) {
885 return -1;
886 }
887 }
888
889 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200890}
891
892/*
893 * Compare signed values
894 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200895int mbedtls_mpi_cmp_mpi(const mbedtls_mpi *X, const mbedtls_mpi *Y)
Jens Wiklander817466c2018-05-22 13:49:31 +0200896{
897 size_t i, j;
Jens Wiklander32b31802023-10-06 16:59:46 +0200898 MPI_VALIDATE_RET(X != NULL);
899 MPI_VALIDATE_RET(Y != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200900
Jens Wiklander32b31802023-10-06 16:59:46 +0200901 for (i = X->n; i > 0; i--) {
902 if (X->p[i - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200903 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200904 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200905 }
906
Jens Wiklander32b31802023-10-06 16:59:46 +0200907 for (j = Y->n; j > 0; j--) {
908 if (Y->p[j - 1] != 0) {
909 break;
910 }
911 }
912
913 if (i == 0 && j == 0) {
914 return 0;
915 }
916
917 if (i > j) {
918 return X->s;
919 }
920 if (j > i) {
921 return -Y->s;
922 }
923
924 if (X->s > 0 && Y->s < 0) {
925 return 1;
926 }
927 if (Y->s > 0 && X->s < 0) {
928 return -1;
929 }
930
931 for (; i > 0; i--) {
932 if (X->p[i - 1] > Y->p[i - 1]) {
933 return X->s;
934 }
935 if (X->p[i - 1] < Y->p[i - 1]) {
936 return -X->s;
937 }
938 }
939
940 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200941}
942
943/*
944 * Compare signed values
945 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200946int mbedtls_mpi_cmp_int(const mbedtls_mpi *X, mbedtls_mpi_sint z)
Jens Wiklander817466c2018-05-22 13:49:31 +0200947{
948 mbedtls_mpi Y;
949 mbedtls_mpi_uint p[1];
Jens Wiklander32b31802023-10-06 16:59:46 +0200950 MPI_VALIDATE_RET(X != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200951
Jens Wiklander32b31802023-10-06 16:59:46 +0200952 *p = mpi_sint_abs(z);
953 Y.s = (z < 0) ? -1 : 1;
Jens Wiklander817466c2018-05-22 13:49:31 +0200954 Y.n = 1;
955 Y.p = p;
956
Jens Wiklander32b31802023-10-06 16:59:46 +0200957 return mbedtls_mpi_cmp_mpi(X, &Y);
Jens Wiklander817466c2018-05-22 13:49:31 +0200958}
959
960/*
961 * Unsigned addition: X = |A| + |B| (HAC 14.7)
962 */
Jens Wiklander32b31802023-10-06 16:59:46 +0200963int mbedtls_mpi_add_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +0200964{
Jerome Forissier11fa71b2020-04-20 17:17:56 +0200965 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +0200966 size_t j;
967 MPI_VALIDATE_RET(X != NULL);
968 MPI_VALIDATE_RET(A != NULL);
969 MPI_VALIDATE_RET(B != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +0200970
Jens Wiklander32b31802023-10-06 16:59:46 +0200971 if (X == B) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200972 const mbedtls_mpi *T = A; A = X; B = T;
973 }
974
Jens Wiklander32b31802023-10-06 16:59:46 +0200975 if (X != A) {
976 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
977 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200978
979 /*
Jens Wiklander32b31802023-10-06 16:59:46 +0200980 * X must always be positive as a result of unsigned additions.
Jens Wiklander817466c2018-05-22 13:49:31 +0200981 */
982 X->s = 1;
983
Jens Wiklander32b31802023-10-06 16:59:46 +0200984 for (j = B->n; j > 0; j--) {
985 if (B->p[j - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +0200986 break;
Jens Wiklander32b31802023-10-06 16:59:46 +0200987 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200988 }
989
Jens Wiklander32b31802023-10-06 16:59:46 +0200990 /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
991 * and B is 0 (of any size). */
992 if (j == 0) {
993 return 0;
994 }
995
996 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j));
997
998 /* j is the number of non-zero limbs of B. Add those to X. */
999
1000 mbedtls_mpi_uint *p = X->p;
1001
1002 mbedtls_mpi_uint c = mbedtls_mpi_core_add(p, p, B->p, j);
1003
1004 p += j;
1005
1006 /* Now propagate any carry */
1007
1008 while (c != 0) {
1009 if (j >= X->n) {
1010 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, j + 1));
1011 p = X->p + j;
Jens Wiklander817466c2018-05-22 13:49:31 +02001012 }
1013
Jens Wiklander32b31802023-10-06 16:59:46 +02001014 *p += c; c = (*p < c); j++; p++;
Jens Wiklander817466c2018-05-22 13:49:31 +02001015 }
1016
1017cleanup:
1018
Jens Wiklander32b31802023-10-06 16:59:46 +02001019 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001020}
1021
1022/*
Jerome Forissier79013242021-07-28 10:24:04 +02001023 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
Jens Wiklander817466c2018-05-22 13:49:31 +02001024 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001025int mbedtls_mpi_sub_abs(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001026{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001027 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02001028 size_t n;
Jerome Forissier79013242021-07-28 10:24:04 +02001029 mbedtls_mpi_uint carry;
Jens Wiklander32b31802023-10-06 16:59:46 +02001030 MPI_VALIDATE_RET(X != NULL);
1031 MPI_VALIDATE_RET(A != NULL);
1032 MPI_VALIDATE_RET(B != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001033
Jens Wiklander32b31802023-10-06 16:59:46 +02001034 for (n = B->n; n > 0; n--) {
1035 if (B->p[n - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001036 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001037 }
1038 }
1039 if (n > A->n) {
Jerome Forissier79013242021-07-28 10:24:04 +02001040 /* B >= (2^ciL)^n > A */
1041 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1042 goto cleanup;
1043 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001044
Jens Wiklander32b31802023-10-06 16:59:46 +02001045 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, A->n));
Jerome Forissier79013242021-07-28 10:24:04 +02001046
1047 /* Set the high limbs of X to match A. Don't touch the lower limbs
1048 * because X might be aliased to B, and we must not overwrite the
1049 * significant digits of B. */
Jens Wiklander32b31802023-10-06 16:59:46 +02001050 if (A->n > n && A != X) {
1051 memcpy(X->p + n, A->p + n, (A->n - n) * ciL);
1052 }
1053 if (X->n > A->n) {
1054 memset(X->p + A->n, 0, (X->n - A->n) * ciL);
1055 }
Jerome Forissier79013242021-07-28 10:24:04 +02001056
Jens Wiklander32b31802023-10-06 16:59:46 +02001057 carry = mbedtls_mpi_core_sub(X->p, A->p, B->p, n);
1058 if (carry != 0) {
1059 /* Propagate the carry through the rest of X. */
1060 carry = mbedtls_mpi_core_sub_int(X->p + n, X->p + n, carry, X->n - n);
1061
1062 /* If we have further carry/borrow, the result is negative. */
1063 if (carry != 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001064 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1065 goto cleanup;
1066 }
Jerome Forissier79013242021-07-28 10:24:04 +02001067 }
1068
1069 /* X should always be positive as a result of unsigned subtractions. */
1070 X->s = 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02001071
1072cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02001073 return ret;
1074}
1075
1076/* Common function for signed addition and subtraction.
1077 * Calculate A + B * flip_B where flip_B is 1 or -1.
1078 */
1079static int add_sub_mpi(mbedtls_mpi *X,
1080 const mbedtls_mpi *A, const mbedtls_mpi *B,
1081 int flip_B)
1082{
1083 int ret, s;
1084 MPI_VALIDATE_RET(X != NULL);
1085 MPI_VALIDATE_RET(A != NULL);
1086 MPI_VALIDATE_RET(B != NULL);
1087
1088 s = A->s;
1089 if (A->s * B->s * flip_B < 0) {
1090 int cmp = mbedtls_mpi_cmp_abs(A, B);
1091 if (cmp >= 0) {
1092 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, A, B));
1093 /* If |A| = |B|, the result is 0 and we must set the sign bit
1094 * to +1 regardless of which of A or B was negative. Otherwise,
1095 * since |A| > |B|, the sign is the sign of A. */
1096 X->s = cmp == 0 ? 1 : s;
1097 } else {
1098 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(X, B, A));
1099 /* Since |A| < |B|, the sign is the opposite of A. */
1100 X->s = -s;
1101 }
1102 } else {
1103 MBEDTLS_MPI_CHK(mbedtls_mpi_add_abs(X, A, B));
1104 X->s = s;
1105 }
1106
1107cleanup:
1108
1109 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001110}
1111
1112/*
1113 * Signed addition: X = A + B
1114 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001115int mbedtls_mpi_add_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001116{
Jens Wiklander32b31802023-10-06 16:59:46 +02001117 return add_sub_mpi(X, A, B, 1);
Jens Wiklander817466c2018-05-22 13:49:31 +02001118}
1119
1120/*
1121 * Signed subtraction: X = A - B
1122 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001123int mbedtls_mpi_sub_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001124{
Jens Wiklander32b31802023-10-06 16:59:46 +02001125 return add_sub_mpi(X, A, B, -1);
Jens Wiklander817466c2018-05-22 13:49:31 +02001126}
1127
1128/*
1129 * Signed addition: X = A + b
1130 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001131int mbedtls_mpi_add_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001132{
Jerome Forissier039e02d2022-08-09 17:10:15 +02001133 mbedtls_mpi B;
Jens Wiklander817466c2018-05-22 13:49:31 +02001134 mbedtls_mpi_uint p[1];
Jens Wiklander32b31802023-10-06 16:59:46 +02001135 MPI_VALIDATE_RET(X != NULL);
1136 MPI_VALIDATE_RET(A != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001137
Jens Wiklander32b31802023-10-06 16:59:46 +02001138 p[0] = mpi_sint_abs(b);
1139 B.s = (b < 0) ? -1 : 1;
Jerome Forissier039e02d2022-08-09 17:10:15 +02001140 B.n = 1;
1141 B.p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +02001142
Jens Wiklander32b31802023-10-06 16:59:46 +02001143 return mbedtls_mpi_add_mpi(X, A, &B);
Jens Wiklander817466c2018-05-22 13:49:31 +02001144}
1145
1146/*
1147 * Signed subtraction: X = A - b
1148 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001149int mbedtls_mpi_sub_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001150{
Jerome Forissier039e02d2022-08-09 17:10:15 +02001151 mbedtls_mpi B;
Jens Wiklander817466c2018-05-22 13:49:31 +02001152 mbedtls_mpi_uint p[1];
Jens Wiklander32b31802023-10-06 16:59:46 +02001153 MPI_VALIDATE_RET(X != NULL);
1154 MPI_VALIDATE_RET(A != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001155
Jens Wiklander32b31802023-10-06 16:59:46 +02001156 p[0] = mpi_sint_abs(b);
1157 B.s = (b < 0) ? -1 : 1;
Jerome Forissier039e02d2022-08-09 17:10:15 +02001158 B.n = 1;
1159 B.p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +02001160
Jens Wiklander32b31802023-10-06 16:59:46 +02001161 return mbedtls_mpi_sub_mpi(X, A, &B);
Jens Wiklander817466c2018-05-22 13:49:31 +02001162}
1163
1164/*
1165 * Baseline multiplication: X = A * B (HAC 14.12)
1166 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001167int mbedtls_mpi_mul_mpi(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001168{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001169 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02001170 size_t i, j;
1171 mbedtls_mpi TA, TB;
Jerome Forissier79013242021-07-28 10:24:04 +02001172 int result_is_zero = 0;
Jens Wiklander32b31802023-10-06 16:59:46 +02001173 MPI_VALIDATE_RET(X != NULL);
1174 MPI_VALIDATE_RET(A != NULL);
1175 MPI_VALIDATE_RET(B != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001176
Jens Wiklander32b31802023-10-06 16:59:46 +02001177 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02001178
Jens Wiklander32b31802023-10-06 16:59:46 +02001179 if (X == A) {
1180 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A)); A = &TA;
1181 }
1182 if (X == B) {
1183 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B)); B = &TB;
1184 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001185
Jens Wiklander32b31802023-10-06 16:59:46 +02001186 for (i = A->n; i > 0; i--) {
1187 if (A->p[i - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001188 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001189 }
1190 }
1191 if (i == 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001192 result_is_zero = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001193 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001194
Jens Wiklander32b31802023-10-06 16:59:46 +02001195 for (j = B->n; j > 0; j--) {
1196 if (B->p[j - 1] != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001197 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001198 }
1199 }
1200 if (j == 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001201 result_is_zero = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001202 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001203
Jens Wiklander32b31802023-10-06 16:59:46 +02001204 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, i + j));
1205 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 0));
Jens Wiklander817466c2018-05-22 13:49:31 +02001206
Jens Wiklander32b31802023-10-06 16:59:46 +02001207 for (size_t k = 0; k < j; k++) {
1208 /* We know that there cannot be any carry-out since we're
1209 * iterating from bottom to top. */
1210 (void) mbedtls_mpi_core_mla(X->p + k, i + 1,
1211 A->p, i,
1212 B->p[k]);
1213 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001214
Jerome Forissier79013242021-07-28 10:24:04 +02001215 /* If the result is 0, we don't shortcut the operation, which reduces
1216 * but does not eliminate side channels leaking the zero-ness. We do
1217 * need to take care to set the sign bit properly since the library does
1218 * not fully support an MPI object with a value of 0 and s == -1. */
Jens Wiklander32b31802023-10-06 16:59:46 +02001219 if (result_is_zero) {
Jerome Forissier79013242021-07-28 10:24:04 +02001220 X->s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001221 } else {
Jerome Forissier79013242021-07-28 10:24:04 +02001222 X->s = A->s * B->s;
Jens Wiklander32b31802023-10-06 16:59:46 +02001223 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001224
1225cleanup:
1226
Jens Wiklander32b31802023-10-06 16:59:46 +02001227 mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TA);
Jens Wiklander817466c2018-05-22 13:49:31 +02001228
Jens Wiklander32b31802023-10-06 16:59:46 +02001229 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001230}
1231
1232/*
1233 * Baseline multiplication: X = A * b
1234 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001235int mbedtls_mpi_mul_int(mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001236{
Jens Wiklander32b31802023-10-06 16:59:46 +02001237 MPI_VALIDATE_RET(X != NULL);
1238 MPI_VALIDATE_RET(A != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001239
Jerome Forissier79013242021-07-28 10:24:04 +02001240 size_t n = A->n;
Jens Wiklander32b31802023-10-06 16:59:46 +02001241 while (n > 0 && A->p[n - 1] == 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02001242 --n;
Jerome Forissier79013242021-07-28 10:24:04 +02001243 }
1244
Jens Wiklander32b31802023-10-06 16:59:46 +02001245 /* The general method below doesn't work if b==0. */
1246 if (b == 0 || n == 0) {
1247 return mbedtls_mpi_lset(X, 0);
1248 }
1249
1250 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
Jerome Forissier79013242021-07-28 10:24:04 +02001251 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1252 /* In general, A * b requires 1 limb more than b. If
1253 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1254 * number of limbs as A and the call to grow() is not required since
1255 * copy() will take care of the growth if needed. However, experimentally,
1256 * making the call to grow() unconditional causes slightly fewer
1257 * calls to calloc() in ECP code, presumably because it reuses the
1258 * same mpi for a while and this way the mpi is more likely to directly
Jens Wiklander32b31802023-10-06 16:59:46 +02001259 * grow to its final size.
1260 *
1261 * Note that calculating A*b as 0 + A*b doesn't work as-is because
1262 * A,X can be the same. */
1263 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(X, n + 1));
1264 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, A));
1265 mbedtls_mpi_core_mla(X->p, X->n, A->p, n, b - 1);
Jerome Forissier79013242021-07-28 10:24:04 +02001266
1267cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02001268 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001269}
1270
1271/*
1272 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1273 * mbedtls_mpi_uint divisor, d
1274 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001275static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1,
1276 mbedtls_mpi_uint u0,
1277 mbedtls_mpi_uint d,
1278 mbedtls_mpi_uint *r)
Jens Wiklander817466c2018-05-22 13:49:31 +02001279{
1280#if defined(MBEDTLS_HAVE_UDBL)
1281 mbedtls_t_udbl dividend, quotient;
1282#else
1283 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
Jens Wiklander32b31802023-10-06 16:59:46 +02001284 const mbedtls_mpi_uint uint_halfword_mask = ((mbedtls_mpi_uint) 1 << biH) - 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02001285 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1286 mbedtls_mpi_uint u0_msw, u0_lsw;
1287 size_t s;
1288#endif
1289
1290 /*
1291 * Check for overflow
1292 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001293 if (0 == d || u1 >= d) {
1294 if (r != NULL) {
1295 *r = ~(mbedtls_mpi_uint) 0u;
1296 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001297
Jens Wiklander32b31802023-10-06 16:59:46 +02001298 return ~(mbedtls_mpi_uint) 0u;
Jens Wiklander817466c2018-05-22 13:49:31 +02001299 }
1300
1301#if defined(MBEDTLS_HAVE_UDBL)
1302 dividend = (mbedtls_t_udbl) u1 << biL;
1303 dividend |= (mbedtls_t_udbl) u0;
1304 quotient = dividend / d;
Jens Wiklander32b31802023-10-06 16:59:46 +02001305 if (quotient > ((mbedtls_t_udbl) 1 << biL) - 1) {
1306 quotient = ((mbedtls_t_udbl) 1 << biL) - 1;
1307 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001308
Jens Wiklander32b31802023-10-06 16:59:46 +02001309 if (r != NULL) {
1310 *r = (mbedtls_mpi_uint) (dividend - (quotient * d));
1311 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001312
1313 return (mbedtls_mpi_uint) quotient;
1314#else
1315
1316 /*
1317 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1318 * Vol. 2 - Seminumerical Algorithms, Knuth
1319 */
1320
1321 /*
1322 * Normalize the divisor, d, and dividend, u0, u1
1323 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001324 s = mbedtls_mpi_core_clz(d);
Jens Wiklander817466c2018-05-22 13:49:31 +02001325 d = d << s;
1326
1327 u1 = u1 << s;
Jens Wiklander32b31802023-10-06 16:59:46 +02001328 u1 |= (u0 >> (biL - s)) & (-(mbedtls_mpi_sint) s >> (biL - 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02001329 u0 = u0 << s;
1330
1331 d1 = d >> biH;
1332 d0 = d & uint_halfword_mask;
1333
1334 u0_msw = u0 >> biH;
1335 u0_lsw = u0 & uint_halfword_mask;
1336
1337 /*
1338 * Find the first quotient and remainder
1339 */
1340 q1 = u1 / d1;
1341 r0 = u1 - d1 * q1;
1342
Jens Wiklander32b31802023-10-06 16:59:46 +02001343 while (q1 >= radix || (q1 * d0 > radix * r0 + u0_msw)) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001344 q1 -= 1;
1345 r0 += d1;
1346
Jens Wiklander32b31802023-10-06 16:59:46 +02001347 if (r0 >= radix) {
1348 break;
1349 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001350 }
1351
Jens Wiklander32b31802023-10-06 16:59:46 +02001352 rAX = (u1 * radix) + (u0_msw - q1 * d);
Jens Wiklander817466c2018-05-22 13:49:31 +02001353 q0 = rAX / d1;
1354 r0 = rAX - q0 * d1;
1355
Jens Wiklander32b31802023-10-06 16:59:46 +02001356 while (q0 >= radix || (q0 * d0 > radix * r0 + u0_lsw)) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001357 q0 -= 1;
1358 r0 += d1;
1359
Jens Wiklander32b31802023-10-06 16:59:46 +02001360 if (r0 >= radix) {
1361 break;
1362 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001363 }
1364
Jens Wiklander32b31802023-10-06 16:59:46 +02001365 if (r != NULL) {
1366 *r = (rAX * radix + u0_lsw - q0 * d) >> s;
1367 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001368
1369 quotient = q1 * radix + q0;
1370
1371 return quotient;
1372#endif
1373}
1374
1375/*
1376 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1377 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001378int mbedtls_mpi_div_mpi(mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1379 const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001380{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001381 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02001382 size_t i, n, t, k;
1383 mbedtls_mpi X, Y, Z, T1, T2;
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001384 mbedtls_mpi_uint TP2[3];
Jens Wiklander32b31802023-10-06 16:59:46 +02001385 MPI_VALIDATE_RET(A != NULL);
1386 MPI_VALIDATE_RET(B != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001387
Jens Wiklander32b31802023-10-06 16:59:46 +02001388 if (mbedtls_mpi_cmp_int(B, 0) == 0) {
1389 return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1390 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001391
Jens Wiklander32b31802023-10-06 16:59:46 +02001392 mbedtls_mpi_init_mempool(&X); mbedtls_mpi_init_mempool(&Y);
1393 mbedtls_mpi_init_mempool(&Z); mbedtls_mpi_init_mempool(&T1);
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001394 /*
1395 * Avoid dynamic memory allocations for constant-size T2.
1396 *
1397 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1398 * so nobody increase the size of the MPI and we're safe to use an on-stack
1399 * buffer.
1400 */
1401 T2.s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001402 T2.n = sizeof(TP2) / sizeof(*TP2);
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001403 T2.p = TP2;
Jens Wiklander817466c2018-05-22 13:49:31 +02001404
Jens Wiklander32b31802023-10-06 16:59:46 +02001405 if (mbedtls_mpi_cmp_abs(A, B) < 0) {
1406 if (Q != NULL) {
1407 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(Q, 0));
1408 }
1409 if (R != NULL) {
1410 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, A));
1411 }
1412 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001413 }
1414
Jens Wiklander32b31802023-10-06 16:59:46 +02001415 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&X, A));
1416 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, B));
Jens Wiklander817466c2018-05-22 13:49:31 +02001417 X.s = Y.s = 1;
1418
Jens Wiklander32b31802023-10-06 16:59:46 +02001419 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&Z, A->n + 2));
1420 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Z, 0));
1421 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T1, A->n + 2));
Jens Wiklander817466c2018-05-22 13:49:31 +02001422
Jens Wiklander32b31802023-10-06 16:59:46 +02001423 k = mbedtls_mpi_bitlen(&Y) % biL;
1424 if (k < biL - 1) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001425 k = biL - 1 - k;
Jens Wiklander32b31802023-10-06 16:59:46 +02001426 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&X, k));
1427 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, k));
1428 } else {
1429 k = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001430 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001431
1432 n = X.n - 1;
1433 t = Y.n - 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001434 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&Y, biL * (n - t)));
Jens Wiklander817466c2018-05-22 13:49:31 +02001435
Jens Wiklander32b31802023-10-06 16:59:46 +02001436 while (mbedtls_mpi_cmp_mpi(&X, &Y) >= 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001437 Z.p[n - t]++;
Jens Wiklander32b31802023-10-06 16:59:46 +02001438 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &Y));
Jens Wiklander817466c2018-05-22 13:49:31 +02001439 }
Jens Wiklander32b31802023-10-06 16:59:46 +02001440 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, biL * (n - t)));
Jens Wiklander817466c2018-05-22 13:49:31 +02001441
Jens Wiklander32b31802023-10-06 16:59:46 +02001442 for (i = n; i > t; i--) {
1443 if (X.p[i] >= Y.p[t]) {
1444 Z.p[i - t - 1] = ~(mbedtls_mpi_uint) 0u;
1445 } else {
1446 Z.p[i - t - 1] = mbedtls_int_div_int(X.p[i], X.p[i - 1],
1447 Y.p[t], NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001448 }
1449
Jens Wiklander32b31802023-10-06 16:59:46 +02001450 T2.p[0] = (i < 2) ? 0 : X.p[i - 2];
1451 T2.p[1] = (i < 1) ? 0 : X.p[i - 1];
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001452 T2.p[2] = X.p[i];
1453
Jens Wiklander817466c2018-05-22 13:49:31 +02001454 Z.p[i - t - 1]++;
Jens Wiklander32b31802023-10-06 16:59:46 +02001455 do {
Jens Wiklander817466c2018-05-22 13:49:31 +02001456 Z.p[i - t - 1]--;
1457
Jens Wiklander32b31802023-10-06 16:59:46 +02001458 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&T1, 0));
1459 T1.p[0] = (t < 1) ? 0 : Y.p[t - 1];
Jens Wiklander817466c2018-05-22 13:49:31 +02001460 T1.p[1] = Y.p[t];
Jens Wiklander32b31802023-10-06 16:59:46 +02001461 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &T1, Z.p[i - t - 1]));
1462 } while (mbedtls_mpi_cmp_mpi(&T1, &T2) > 0);
Jens Wiklander817466c2018-05-22 13:49:31 +02001463
Jens Wiklander32b31802023-10-06 16:59:46 +02001464 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_int(&T1, &Y, Z.p[i - t - 1]));
1465 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1466 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&X, &X, &T1));
Jens Wiklander817466c2018-05-22 13:49:31 +02001467
Jens Wiklander32b31802023-10-06 16:59:46 +02001468 if (mbedtls_mpi_cmp_int(&X, 0) < 0) {
1469 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&T1, &Y));
1470 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&T1, biL * (i - t - 1)));
1471 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&X, &X, &T1));
Jens Wiklander817466c2018-05-22 13:49:31 +02001472 Z.p[i - t - 1]--;
1473 }
1474 }
1475
Jens Wiklander32b31802023-10-06 16:59:46 +02001476 if (Q != NULL) {
1477 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(Q, &Z));
Jens Wiklander817466c2018-05-22 13:49:31 +02001478 Q->s = A->s * B->s;
1479 }
1480
Jens Wiklander32b31802023-10-06 16:59:46 +02001481 if (R != NULL) {
1482 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&X, k));
Jens Wiklander817466c2018-05-22 13:49:31 +02001483 X.s = A->s;
Jens Wiklander32b31802023-10-06 16:59:46 +02001484 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(R, &X));
Jens Wiklander817466c2018-05-22 13:49:31 +02001485
Jens Wiklander32b31802023-10-06 16:59:46 +02001486 if (mbedtls_mpi_cmp_int(R, 0) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001487 R->s = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001488 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001489 }
1490
1491cleanup:
1492
Jens Wiklander32b31802023-10-06 16:59:46 +02001493 mbedtls_mpi_free(&X); mbedtls_mpi_free(&Y); mbedtls_mpi_free(&Z);
1494 mbedtls_mpi_free(&T1);
1495 mbedtls_platform_zeroize(TP2, sizeof(TP2));
Jens Wiklander817466c2018-05-22 13:49:31 +02001496
Jens Wiklander32b31802023-10-06 16:59:46 +02001497 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001498}
1499
1500/*
1501 * Division by int: A = Q * b + R
1502 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001503int mbedtls_mpi_div_int(mbedtls_mpi *Q, mbedtls_mpi *R,
1504 const mbedtls_mpi *A,
1505 mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001506{
Jerome Forissier039e02d2022-08-09 17:10:15 +02001507 mbedtls_mpi B;
Jens Wiklander817466c2018-05-22 13:49:31 +02001508 mbedtls_mpi_uint p[1];
Jens Wiklander32b31802023-10-06 16:59:46 +02001509 MPI_VALIDATE_RET(A != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001510
Jens Wiklander32b31802023-10-06 16:59:46 +02001511 p[0] = mpi_sint_abs(b);
1512 B.s = (b < 0) ? -1 : 1;
Jerome Forissier039e02d2022-08-09 17:10:15 +02001513 B.n = 1;
1514 B.p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +02001515
Jens Wiklander32b31802023-10-06 16:59:46 +02001516 return mbedtls_mpi_div_mpi(Q, R, A, &B);
Jens Wiklander817466c2018-05-22 13:49:31 +02001517}
1518
1519/*
1520 * Modulo: R = A mod B
1521 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001522int mbedtls_mpi_mod_mpi(mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02001523{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001524 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +02001525 MPI_VALIDATE_RET(R != NULL);
1526 MPI_VALIDATE_RET(A != NULL);
1527 MPI_VALIDATE_RET(B != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001528
Jens Wiklander32b31802023-10-06 16:59:46 +02001529 if (mbedtls_mpi_cmp_int(B, 0) < 0) {
1530 return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1531 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001532
Jens Wiklander32b31802023-10-06 16:59:46 +02001533 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(NULL, R, A, B));
Jens Wiklander817466c2018-05-22 13:49:31 +02001534
Jens Wiklander32b31802023-10-06 16:59:46 +02001535 while (mbedtls_mpi_cmp_int(R, 0) < 0) {
1536 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(R, R, B));
1537 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001538
Jens Wiklander32b31802023-10-06 16:59:46 +02001539 while (mbedtls_mpi_cmp_mpi(R, B) >= 0) {
1540 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(R, R, B));
1541 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001542
1543cleanup:
1544
Jens Wiklander32b31802023-10-06 16:59:46 +02001545 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001546}
1547
1548/*
1549 * Modulo: r = A mod b
1550 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001551int mbedtls_mpi_mod_int(mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b)
Jens Wiklander817466c2018-05-22 13:49:31 +02001552{
1553 size_t i;
1554 mbedtls_mpi_uint x, y, z;
Jens Wiklander32b31802023-10-06 16:59:46 +02001555 MPI_VALIDATE_RET(r != NULL);
1556 MPI_VALIDATE_RET(A != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02001557
Jens Wiklander32b31802023-10-06 16:59:46 +02001558 if (b == 0) {
1559 return MBEDTLS_ERR_MPI_DIVISION_BY_ZERO;
1560 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001561
Jens Wiklander32b31802023-10-06 16:59:46 +02001562 if (b < 0) {
1563 return MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1564 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001565
1566 /*
1567 * handle trivial cases
1568 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001569 if (b == 1 || A->n == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001570 *r = 0;
Jens Wiklander32b31802023-10-06 16:59:46 +02001571 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001572 }
1573
Jens Wiklander32b31802023-10-06 16:59:46 +02001574 if (b == 2) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001575 *r = A->p[0] & 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02001576 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001577 }
1578
1579 /*
1580 * general case
1581 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001582 for (i = A->n, y = 0; i > 0; i--) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001583 x = A->p[i - 1];
Jens Wiklander32b31802023-10-06 16:59:46 +02001584 y = (y << biH) | (x >> biH);
Jens Wiklander817466c2018-05-22 13:49:31 +02001585 z = y / b;
1586 y -= z * b;
1587
1588 x <<= biH;
Jens Wiklander32b31802023-10-06 16:59:46 +02001589 y = (y << biH) | (x >> biH);
Jens Wiklander817466c2018-05-22 13:49:31 +02001590 z = y / b;
1591 y -= z * b;
1592 }
1593
1594 /*
1595 * If A is negative, then the current y represents a negative value.
1596 * Flipping it to the positive side.
1597 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001598 if (A->s < 0 && y != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001599 y = b - y;
Jens Wiklander32b31802023-10-06 16:59:46 +02001600 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001601
1602 *r = y;
1603
Jens Wiklander32b31802023-10-06 16:59:46 +02001604 return 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001605}
1606
Jens Wiklander32b31802023-10-06 16:59:46 +02001607static void mpi_montg_init(mbedtls_mpi_uint *mm, const mbedtls_mpi *N)
Jens Wiklander817466c2018-05-22 13:49:31 +02001608{
Jens Wiklander32b31802023-10-06 16:59:46 +02001609 *mm = mbedtls_mpi_core_montmul_init(N->p);
Jens Wiklander817466c2018-05-22 13:49:31 +02001610}
1611
Jerome Forissier79013242021-07-28 10:24:04 +02001612void mbedtls_mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
1613{
1614 mpi_montg_init( mm, N );
1615}
1616
1617/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1618 *
1619 * \param[in,out] A One of the numbers to multiply.
1620 * It must have at least as many limbs as N
1621 * (A->n >= N->n), and any limbs beyond n are ignored.
1622 * On successful completion, A contains the result of
1623 * the multiplication A * B * R^-1 mod N where
1624 * R = (2^ciL)^n.
1625 * \param[in] B One of the numbers to multiply.
1626 * It must be nonzero and must not have more limbs than N
1627 * (B->n <= N->n).
Jens Wiklander32b31802023-10-06 16:59:46 +02001628 * \param[in] N The modulus. \p N must be odd.
Jerome Forissier79013242021-07-28 10:24:04 +02001629 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1630 * This is -N^-1 mod 2^ciL.
1631 * \param[in,out] T A bignum for temporary storage.
Jens Wiklander32b31802023-10-06 16:59:46 +02001632 * It must be at least twice the limb size of N plus 1
1633 * (T->n >= 2 * N->n + 1).
Jerome Forissier79013242021-07-28 10:24:04 +02001634 * Its initial content is unused and
1635 * its final content is indeterminate.
Jens Wiklander32b31802023-10-06 16:59:46 +02001636 * It does not get reallocated.
Jens Wiklander817466c2018-05-22 13:49:31 +02001637 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001638static void mpi_montmul(mbedtls_mpi *A, const mbedtls_mpi *B,
1639 const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1640 mbedtls_mpi *T)
Jens Wiklander817466c2018-05-22 13:49:31 +02001641{
Jens Wiklander32b31802023-10-06 16:59:46 +02001642 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 +02001643}
Jens Wiklander817466c2018-05-22 13:49:31 +02001644
Jens Wiklander32b31802023-10-06 16:59:46 +02001645void mbedtls_mpi_montmul(mbedtls_mpi *A, const mbedtls_mpi *B,
1646 const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1647 mbedtls_mpi *T )
Jerome Forissier79013242021-07-28 10:24:04 +02001648{
1649 mpi_montmul( A, B, N, mm, T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001650}
1651
1652/*
1653 * Montgomery reduction: A = A * R^-1 mod N
Jerome Forissier79013242021-07-28 10:24:04 +02001654 *
1655 * See mpi_montmul() regarding constraints and guarantees on the parameters.
Jens Wiklander817466c2018-05-22 13:49:31 +02001656 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001657static void mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N,
1658 mbedtls_mpi_uint mm, mbedtls_mpi *T)
Jens Wiklander817466c2018-05-22 13:49:31 +02001659{
1660 mbedtls_mpi_uint z = 1;
1661 mbedtls_mpi U;
1662
1663 U.n = U.s = (int) z;
1664 U.p = &z;
1665
Jens Wiklander32b31802023-10-06 16:59:46 +02001666 mpi_montmul(A, &U, N, mm, T);
Jerome Forissier79013242021-07-28 10:24:04 +02001667}
1668
Jens Wiklander32b31802023-10-06 16:59:46 +02001669void mbedtls_mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N,
1670 mbedtls_mpi_uint mm, mbedtls_mpi *T)
Jerome Forissier79013242021-07-28 10:24:04 +02001671{
Jens Wiklander32b31802023-10-06 16:59:46 +02001672 mpi_montred(A, N, mm, T);
Jerome Forissier79013242021-07-28 10:24:04 +02001673}
1674
Jerome Forissier79013242021-07-28 10:24:04 +02001675/**
1676 * Select an MPI from a table without leaking the index.
1677 *
1678 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
1679 * reads the entire table in order to avoid leaking the value of idx to an
1680 * attacker able to observe memory access patterns.
1681 *
1682 * \param[out] R Where to write the selected MPI.
1683 * \param[in] T The table to read from.
1684 * \param[in] T_size The number of elements in the table.
1685 * \param[in] idx The index of the element to select;
1686 * this must satisfy 0 <= idx < T_size.
1687 *
1688 * \return \c 0 on success, or a negative error code.
1689 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001690static int mpi_select(mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx)
Jerome Forissier79013242021-07-28 10:24:04 +02001691{
1692 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1693
Jens Wiklander32b31802023-10-06 16:59:46 +02001694 for (size_t i = 0; i < T_size; i++) {
1695 MBEDTLS_MPI_CHK(mbedtls_mpi_safe_cond_assign(R, &T[i],
1696 (unsigned char) mbedtls_ct_size_bool_eq(i,
1697 idx)));
Jerome Forissier79013242021-07-28 10:24:04 +02001698 }
1699
1700cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02001701 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02001702}
1703
1704/*
1705 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1706 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001707int mbedtls_mpi_exp_mod(mbedtls_mpi *X, const mbedtls_mpi *A,
1708 const mbedtls_mpi *E, const mbedtls_mpi *N,
1709 mbedtls_mpi *prec_RR)
Jens Wiklander817466c2018-05-22 13:49:31 +02001710{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02001711 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +02001712 size_t window_bitsize;
Jens Wiklander817466c2018-05-22 13:49:31 +02001713 size_t i, j, nblimbs;
1714 size_t bufsize, nbits;
Jens Wiklander32b31802023-10-06 16:59:46 +02001715 size_t exponent_bits_in_window = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001716 mbedtls_mpi_uint ei, mm, state;
Jerome Forissier79013242021-07-28 10:24:04 +02001717 mbedtls_mpi RR, T, WW, Apos;
Jens Wiklander32b31802023-10-06 16:59:46 +02001718 mbedtls_mpi *W;
Jens Wiklander41e5aa82019-05-21 22:52:10 +02001719 const size_t array_size_W = 2 << MBEDTLS_MPI_WINDOW_SIZE;
Jens Wiklander817466c2018-05-22 13:49:31 +02001720 int neg;
1721
Jens Wiklander32b31802023-10-06 16:59:46 +02001722 MPI_VALIDATE_RET(X != NULL);
1723 MPI_VALIDATE_RET(A != NULL);
1724 MPI_VALIDATE_RET(E != NULL);
1725 MPI_VALIDATE_RET(N != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01001726
Jens Wiklander32b31802023-10-06 16:59:46 +02001727 if (mbedtls_mpi_cmp_int(N, 0) <= 0 || (N->p[0] & 1) == 0) {
1728 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1729 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001730
Jens Wiklander32b31802023-10-06 16:59:46 +02001731 if (mbedtls_mpi_cmp_int(E, 0) < 0) {
1732 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1733 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001734
Jens Wiklander32b31802023-10-06 16:59:46 +02001735 if (mbedtls_mpi_bitlen(E) > MBEDTLS_MPI_MAX_BITS ||
1736 mbedtls_mpi_bitlen(N) > MBEDTLS_MPI_MAX_BITS) {
1737 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1738 }
Jerome Forissier79013242021-07-28 10:24:04 +02001739
Jens Wiklander817466c2018-05-22 13:49:31 +02001740 /*
1741 * Init temps and window size
1742 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001743 mpi_montg_init(&mm, N);
1744 mbedtls_mpi_init_mempool(&RR); mbedtls_mpi_init(&T);
1745 mbedtls_mpi_init_mempool(&Apos);
1746 mbedtls_mpi_init_mempool(&WW);
Jens Wiklander817466c2018-05-22 13:49:31 +02001747
Jens Wiklander32b31802023-10-06 16:59:46 +02001748 i = mbedtls_mpi_bitlen(E);
Jens Wiklander817466c2018-05-22 13:49:31 +02001749
Jens Wiklander32b31802023-10-06 16:59:46 +02001750 window_bitsize = (i > 671) ? 6 : (i > 239) ? 5 :
1751 (i > 79) ? 4 : (i > 23) ? 3 : 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02001752
Jens Wiklander32b31802023-10-06 16:59:46 +02001753#if (MBEDTLS_MPI_WINDOW_SIZE < 6)
1754 if (window_bitsize > MBEDTLS_MPI_WINDOW_SIZE) {
1755 window_bitsize = MBEDTLS_MPI_WINDOW_SIZE;
1756 }
Jerome Forissier5b25c762020-04-07 11:18:49 +02001757#endif
Jens Wiklander817466c2018-05-22 13:49:31 +02001758
Jens Wiklander32b31802023-10-06 16:59:46 +02001759 const size_t w_table_used_size = (size_t) 1 << window_bitsize;
1760
1761 W = mempool_alloc(mbedtls_mpi_mempool,
1762 sizeof( mbedtls_mpi ) * array_size_W);
1763 if (W == NULL) {
1764 ret = MBEDTLS_ERR_MPI_ALLOC_FAILED;
1765 goto cleanup;
1766 }
1767 for (i = 0; i < array_size_W; i++)
1768 mbedtls_mpi_init_mempool(W + i);
1769 /*
1770 * This function is not constant-trace: its memory accesses depend on the
1771 * exponent value. To defend against timing attacks, callers (such as RSA
1772 * and DHM) should use exponent blinding. However this is not enough if the
1773 * adversary can find the exponent in a single trace, so this function
1774 * takes extra precautions against adversaries who can observe memory
1775 * access patterns.
1776 *
1777 * This function performs a series of multiplications by table elements and
1778 * squarings, and we want the prevent the adversary from finding out which
1779 * table element was used, and from distinguishing between multiplications
1780 * and squarings. Firstly, when multiplying by an element of the window
1781 * W[i], we do a constant-trace table lookup to obfuscate i. This leaves
1782 * squarings as having a different memory access patterns from other
1783 * multiplications. So secondly, we put the accumulator X in the table as
1784 * well, and also do a constant-trace table lookup to multiply by X.
1785 *
1786 * This way, all multiplications take the form of a lookup-and-multiply.
1787 * The number of lookup-and-multiply operations inside each iteration of
1788 * the main loop still depends on the bits of the exponent, but since the
1789 * other operations in the loop don't have an easily recognizable memory
1790 * trace, an adversary is unlikely to be able to observe the exact
1791 * patterns.
1792 *
1793 * An adversary may still be able to recover the exponent if they can
1794 * observe both memory accesses and branches. However, branch prediction
1795 * exploitation typically requires many traces of execution over the same
1796 * data, which is defeated by randomized blinding.
1797 *
1798 * To achieve this, we make a copy of X and we use the table entry in each
1799 * calculation from this point on.
1800 */
1801 const size_t x_index = 0;
1802 mbedtls_mpi_copy(&W[x_index], X);
1803
Jens Wiklander817466c2018-05-22 13:49:31 +02001804 j = N->n + 1;
Jerome Forissier79013242021-07-28 10:24:04 +02001805 /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
1806 * and mpi_montred() calls later. Here we ensure that W[1] and X are
1807 * large enough, and later we'll grow other W[i] to the same length.
1808 * They must not be shrunk midway through this function!
1809 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001810 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[x_index], j));
Jens Wiklanderad443202019-05-27 16:42:58 +02001811
Jens Wiklander32b31802023-10-06 16:59:46 +02001812 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&T, j * 2));
Jens Wiklander817466c2018-05-22 13:49:31 +02001813
1814 /*
1815 * Compensate for negative A (and correct at the end)
1816 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001817 neg = (A->s == -1);
1818 if (neg) {
1819 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Apos, A));
Jens Wiklander817466c2018-05-22 13:49:31 +02001820 Apos.s = 1;
1821 A = &Apos;
1822 }
1823
1824 /*
1825 * If 1st call, pre-compute R^2 mod N
1826 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001827 if (prec_RR == NULL || prec_RR->p == NULL) {
1828 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&RR, 1));
1829 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&RR, N->n * 2 * biL));
1830 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&RR, &RR, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02001831
Jens Wiklander32b31802023-10-06 16:59:46 +02001832 if (prec_RR != NULL) {
1833 memcpy(prec_RR, &RR, sizeof(mbedtls_mpi));
1834 }
1835 } else {
1836 memcpy(&RR, prec_RR, sizeof(mbedtls_mpi));
Jens Wiklander817466c2018-05-22 13:49:31 +02001837 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001838
Jens Wiklander32b31802023-10-06 16:59:46 +02001839 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], j));
Jens Wiklanderad443202019-05-27 16:42:58 +02001840
Jens Wiklander817466c2018-05-22 13:49:31 +02001841 /*
1842 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1843 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001844 if (mbedtls_mpi_cmp_mpi(A, N) >= 0) {
1845 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&W[1], A, N));
Jerome Forissier79013242021-07-28 10:24:04 +02001846 /* This should be a no-op because W[1] is already that large before
1847 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
1848 * in mpi_montmul() below, so let's make sure. */
Jens Wiklander32b31802023-10-06 16:59:46 +02001849 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], N->n + 1));
1850 } else {
1851 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[1], A));
Jerome Forissier79013242021-07-28 10:24:04 +02001852 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001853
Jerome Forissier79013242021-07-28 10:24:04 +02001854 /* Note that this is safe because W[1] always has at least N->n limbs
1855 * (it grew above and was preserved by mbedtls_mpi_copy()). */
Jens Wiklander32b31802023-10-06 16:59:46 +02001856 mpi_montmul(&W[1], &RR, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001857
1858 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001859 * W[x_index] = R^2 * R^-1 mod N = R mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02001860 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001861 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[x_index], &RR));
1862 mpi_montred(&W[x_index], N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001863
Jens Wiklander32b31802023-10-06 16:59:46 +02001864
1865 if (window_bitsize > 1) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001866 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001867 * W[i] = W[1] ^ i
1868 *
1869 * The first bit of the sliding window is always 1 and therefore we
1870 * only need to store the second half of the table.
1871 *
1872 * (There are two special elements in the table: W[0] for the
1873 * accumulator/result and W[1] for A in Montgomery form. Both of these
1874 * are already set at this point.)
Jens Wiklander817466c2018-05-22 13:49:31 +02001875 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001876 j = w_table_used_size / 2;
Jens Wiklander817466c2018-05-22 13:49:31 +02001877
Jens Wiklander32b31802023-10-06 16:59:46 +02001878 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[j], N->n + 1));
1879 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[j], &W[1]));
Jens Wiklander817466c2018-05-22 13:49:31 +02001880
Jens Wiklander32b31802023-10-06 16:59:46 +02001881 for (i = 0; i < window_bitsize - 1; i++) {
1882 mpi_montmul(&W[j], &W[j], N, mm, &T);
1883 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001884
1885 /*
1886 * W[i] = W[i - 1] * W[1]
1887 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001888 for (i = j + 1; i < w_table_used_size; i++) {
1889 MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[i], N->n + 1));
1890 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[i], &W[i - 1]));
Jens Wiklander817466c2018-05-22 13:49:31 +02001891
Jens Wiklander32b31802023-10-06 16:59:46 +02001892 mpi_montmul(&W[i], &W[1], N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001893 }
1894 }
1895
1896 nblimbs = E->n;
1897 bufsize = 0;
1898 nbits = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001899 state = 0;
1900
Jens Wiklander32b31802023-10-06 16:59:46 +02001901 while (1) {
1902 if (bufsize == 0) {
1903 if (nblimbs == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001904 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02001905 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001906
1907 nblimbs--;
1908
Jens Wiklander32b31802023-10-06 16:59:46 +02001909 bufsize = sizeof(mbedtls_mpi_uint) << 3;
Jens Wiklander817466c2018-05-22 13:49:31 +02001910 }
1911
1912 bufsize--;
1913
1914 ei = (E->p[nblimbs] >> bufsize) & 1;
1915
1916 /*
1917 * skip leading 0s
1918 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001919 if (ei == 0 && state == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001920 continue;
Jens Wiklander32b31802023-10-06 16:59:46 +02001921 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001922
Jens Wiklander32b31802023-10-06 16:59:46 +02001923 if (ei == 0 && state == 1) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001924 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001925 * out of window, square W[x_index]
Jens Wiklander817466c2018-05-22 13:49:31 +02001926 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001927 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
1928 mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001929 continue;
1930 }
1931
1932 /*
1933 * add ei to current window
1934 */
1935 state = 2;
1936
1937 nbits++;
Jens Wiklander32b31802023-10-06 16:59:46 +02001938 exponent_bits_in_window |= (ei << (window_bitsize - nbits));
Jens Wiklander817466c2018-05-22 13:49:31 +02001939
Jens Wiklander32b31802023-10-06 16:59:46 +02001940 if (nbits == window_bitsize) {
Jens Wiklander817466c2018-05-22 13:49:31 +02001941 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001942 * W[x_index] = W[x_index]^window_bitsize R^-1 mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02001943 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001944 for (i = 0; i < window_bitsize; i++) {
1945 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
1946 x_index));
1947 mpi_montmul(&W[x_index], &WW, N, mm, &T);
1948 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001949
1950 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001951 * W[x_index] = W[x_index] * W[exponent_bits_in_window] R^-1 mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02001952 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001953 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
1954 exponent_bits_in_window));
1955 mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001956
1957 state--;
1958 nbits = 0;
Jens Wiklander32b31802023-10-06 16:59:46 +02001959 exponent_bits_in_window = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +02001960 }
1961 }
1962
1963 /*
1964 * process the remaining bits
1965 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001966 for (i = 0; i < nbits; i++) {
1967 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
1968 mpi_montmul(&W[x_index], &WW, N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001969
Jens Wiklander32b31802023-10-06 16:59:46 +02001970 exponent_bits_in_window <<= 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02001971
Jens Wiklander32b31802023-10-06 16:59:46 +02001972 if ((exponent_bits_in_window & ((size_t) 1 << window_bitsize)) != 0) {
1973 MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, 1));
1974 mpi_montmul(&W[x_index], &WW, N, mm, &T);
1975 }
Jens Wiklander817466c2018-05-22 13:49:31 +02001976 }
1977
1978 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02001979 * W[x_index] = A^E * R * R^-1 mod N = A^E mod N
Jens Wiklander817466c2018-05-22 13:49:31 +02001980 */
Jens Wiklander32b31802023-10-06 16:59:46 +02001981 mpi_montred(&W[x_index], N, mm, &T);
Jens Wiklander817466c2018-05-22 13:49:31 +02001982
Jens Wiklander32b31802023-10-06 16:59:46 +02001983 if (neg && E->n != 0 && (E->p[0] & 1) != 0) {
1984 W[x_index].s = -1;
1985 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&W[x_index], N, &W[x_index]));
Jens Wiklander817466c2018-05-22 13:49:31 +02001986 }
1987
Jens Wiklander32b31802023-10-06 16:59:46 +02001988 /*
1989 * Load the result in the output variable.
1990 */
1991 mbedtls_mpi_copy(X, &W[x_index]);
1992
Jens Wiklander817466c2018-05-22 13:49:31 +02001993cleanup:
1994
Jens Wiklander32b31802023-10-06 16:59:46 +02001995 if (W)
1996 for (i = 0; i < array_size_W; i++)
1997 mbedtls_mpi_free(W + i);
1998 mempool_free(mbedtls_mpi_mempool , W);
Jens Wiklander817466c2018-05-22 13:49:31 +02001999
Jens Wiklander32b31802023-10-06 16:59:46 +02002000 mbedtls_mpi_free(&T);
2001 mbedtls_mpi_free(&Apos);
2002 mbedtls_mpi_free(&WW);
Jens Wiklander817466c2018-05-22 13:49:31 +02002003
Jens Wiklander32b31802023-10-06 16:59:46 +02002004 if (prec_RR == NULL || prec_RR->p == NULL) {
2005 mbedtls_mpi_free(&RR);
2006 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002007
Jens Wiklander32b31802023-10-06 16:59:46 +02002008 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002009}
2010
2011/*
2012 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2013 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002014int mbedtls_mpi_gcd(mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B)
Jens Wiklander817466c2018-05-22 13:49:31 +02002015{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002016 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02002017 size_t lz, lzt;
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002018 mbedtls_mpi TA, TB;
Jens Wiklander817466c2018-05-22 13:49:31 +02002019
Jens Wiklander32b31802023-10-06 16:59:46 +02002020 MPI_VALIDATE_RET(G != NULL);
2021 MPI_VALIDATE_RET(A != NULL);
2022 MPI_VALIDATE_RET(B != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002023
Jens Wiklander32b31802023-10-06 16:59:46 +02002024 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02002025
Jens Wiklander32b31802023-10-06 16:59:46 +02002026 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TA, A));
2027 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, B));
Jens Wiklander817466c2018-05-22 13:49:31 +02002028
Jens Wiklander32b31802023-10-06 16:59:46 +02002029 lz = mbedtls_mpi_lsb(&TA);
2030 lzt = mbedtls_mpi_lsb(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02002031
Jerome Forissier79013242021-07-28 10:24:04 +02002032 /* The loop below gives the correct result when A==0 but not when B==0.
2033 * So have a special case for B==0. Leverage the fact that we just
2034 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
2035 * slightly more efficient than cmp_int(). */
Jens Wiklander32b31802023-10-06 16:59:46 +02002036 if (lzt == 0 && mbedtls_mpi_get_bit(&TB, 0) == 0) {
2037 ret = mbedtls_mpi_copy(G, A);
Jerome Forissier79013242021-07-28 10:24:04 +02002038 goto cleanup;
2039 }
2040
Jens Wiklander32b31802023-10-06 16:59:46 +02002041 if (lzt < lz) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002042 lz = lzt;
Jens Wiklander32b31802023-10-06 16:59:46 +02002043 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002044
Jens Wiklander817466c2018-05-22 13:49:31 +02002045 TA.s = TB.s = 1;
2046
Jerome Forissier79013242021-07-28 10:24:04 +02002047 /* We mostly follow the procedure described in HAC 14.54, but with some
2048 * minor differences:
2049 * - Sequences of multiplications or divisions by 2 are grouped into a
2050 * single shift operation.
2051 * - The procedure in HAC assumes that 0 < TB <= TA.
2052 * - The condition TB <= TA is not actually necessary for correctness.
2053 * TA and TB have symmetric roles except for the loop termination
2054 * condition, and the shifts at the beginning of the loop body
2055 * remove any significance from the ordering of TA vs TB before
2056 * the shifts.
2057 * - If TA = 0, the loop goes through 0 iterations and the result is
2058 * correctly TB.
2059 * - The case TB = 0 was short-circuited above.
2060 *
2061 * For the correctness proof below, decompose the original values of
2062 * A and B as
2063 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
2064 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
2065 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
2066 * and gcd(A',B') is odd or 0.
2067 *
2068 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
2069 * The code maintains the following invariant:
2070 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
2071 */
2072
2073 /* Proof that the loop terminates:
2074 * At each iteration, either the right-shift by 1 is made on a nonzero
2075 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
2076 * by at least 1, or the right-shift by 1 is made on zero and then
2077 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
2078 * since in that case TB is calculated from TB-TA with the condition TB>TA).
2079 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002080 while (mbedtls_mpi_cmp_int(&TA, 0) != 0) {
Jerome Forissier79013242021-07-28 10:24:04 +02002081 /* Divisions by 2 preserve the invariant (I). */
Jens Wiklander32b31802023-10-06 16:59:46 +02002082 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, mbedtls_mpi_lsb(&TA)));
2083 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, mbedtls_mpi_lsb(&TB)));
Jens Wiklander817466c2018-05-22 13:49:31 +02002084
Jerome Forissier79013242021-07-28 10:24:04 +02002085 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
2086 * TA-TB is even so the division by 2 has an integer result.
2087 * Invariant (I) is preserved since any odd divisor of both TA and TB
2088 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
Jerome Forissier039e02d2022-08-09 17:10:15 +02002089 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
Jerome Forissier79013242021-07-28 10:24:04 +02002090 * divides TA.
2091 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002092 if (mbedtls_mpi_cmp_mpi(&TA, &TB) >= 0) {
2093 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TA, &TA, &TB));
2094 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TA, 1));
2095 } else {
2096 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_abs(&TB, &TB, &TA));
2097 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TB, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002098 }
Jerome Forissier79013242021-07-28 10:24:04 +02002099 /* Note that one of TA or TB is still odd. */
Jens Wiklander817466c2018-05-22 13:49:31 +02002100 }
2101
Jerome Forissier79013242021-07-28 10:24:04 +02002102 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
2103 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
2104 * - If there was at least one loop iteration, then one of TA or TB is odd,
2105 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
2106 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
2107 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
2108 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
2109 */
2110
Jens Wiklander32b31802023-10-06 16:59:46 +02002111 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&TB, lz));
2112 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(G, &TB));
Jens Wiklander817466c2018-05-22 13:49:31 +02002113
2114cleanup:
2115
Jens Wiklander32b31802023-10-06 16:59:46 +02002116 mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TB);
Jens Wiklander817466c2018-05-22 13:49:31 +02002117
Jens Wiklander32b31802023-10-06 16:59:46 +02002118 return ret;
Jerome Forissier79013242021-07-28 10:24:04 +02002119}
2120
Jens Wiklander817466c2018-05-22 13:49:31 +02002121/*
2122 * Fill X with size bytes of random.
Jens Wiklander32b31802023-10-06 16:59:46 +02002123 * The bytes returned from the RNG are used in a specific order which
2124 * is suitable for deterministic ECDSA (see the specification of
2125 * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()).
Jens Wiklander817466c2018-05-22 13:49:31 +02002126 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002127int mbedtls_mpi_fill_random(mbedtls_mpi *X, size_t size,
2128 int (*f_rng)(void *, unsigned char *, size_t),
2129 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002130{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002131 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander32b31802023-10-06 16:59:46 +02002132 const size_t limbs = CHARS_TO_LIMBS(size);
Jerome Forissier5b25c762020-04-07 11:18:49 +02002133
Jens Wiklander32b31802023-10-06 16:59:46 +02002134 MPI_VALIDATE_RET(X != NULL);
2135 MPI_VALIDATE_RET(f_rng != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02002136
Jerome Forissier5b25c762020-04-07 11:18:49 +02002137 /* Ensure that target MPI has exactly the necessary number of limbs */
Jens Wiklander32b31802023-10-06 16:59:46 +02002138 MBEDTLS_MPI_CHK(mbedtls_mpi_resize_clear(X, limbs));
2139 if (size == 0) {
2140 return 0;
2141 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002142
Jens Wiklander32b31802023-10-06 16:59:46 +02002143 ret = mbedtls_mpi_core_fill_random(X->p, X->n, size, f_rng, p_rng);
Jens Wiklander817466c2018-05-22 13:49:31 +02002144
2145cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02002146 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002147}
2148
Jens Wiklander32b31802023-10-06 16:59:46 +02002149int mbedtls_mpi_random(mbedtls_mpi *X,
2150 mbedtls_mpi_sint min,
2151 const mbedtls_mpi *N,
2152 int (*f_rng)(void *, unsigned char *, size_t),
2153 void *p_rng)
Jerome Forissier79013242021-07-28 10:24:04 +02002154{
Jens Wiklander32b31802023-10-06 16:59:46 +02002155 if (min < 0) {
2156 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2157 }
2158 if (mbedtls_mpi_cmp_int(N, min) <= 0) {
2159 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2160 }
Jerome Forissier79013242021-07-28 10:24:04 +02002161
2162 /* Ensure that target MPI has exactly the same number of limbs
2163 * as the upper bound, even if the upper bound has leading zeros.
Jens Wiklander32b31802023-10-06 16:59:46 +02002164 * This is necessary for mbedtls_mpi_core_random. */
2165 int ret = mbedtls_mpi_resize_clear(X, N->n);
2166 if (ret != 0) {
2167 return ret;
Jerome Forissier79013242021-07-28 10:24:04 +02002168 }
Jerome Forissier79013242021-07-28 10:24:04 +02002169
Jens Wiklander32b31802023-10-06 16:59:46 +02002170 return mbedtls_mpi_core_random(X->p, min, N->p, X->n, f_rng, p_rng);
Jerome Forissier79013242021-07-28 10:24:04 +02002171}
2172
Jens Wiklander817466c2018-05-22 13:49:31 +02002173/*
2174 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2175 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002176int mbedtls_mpi_inv_mod(mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N)
Jens Wiklander817466c2018-05-22 13:49:31 +02002177{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002178 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02002179 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Jens Wiklander32b31802023-10-06 16:59:46 +02002180 MPI_VALIDATE_RET(X != NULL);
2181 MPI_VALIDATE_RET(A != NULL);
2182 MPI_VALIDATE_RET(N != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02002183
Jens Wiklander32b31802023-10-06 16:59:46 +02002184 if (mbedtls_mpi_cmp_int(N, 1) <= 0) {
2185 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2186 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002187
Jens Wiklander32b31802023-10-06 16:59:46 +02002188 mbedtls_mpi_init_mempool(&TA); mbedtls_mpi_init_mempool(&TU);
2189 mbedtls_mpi_init_mempool(&U1); mbedtls_mpi_init_mempool(&U2);
2190 mbedtls_mpi_init_mempool(&G); mbedtls_mpi_init_mempool(&TB);
2191 mbedtls_mpi_init_mempool(&TV); mbedtls_mpi_init_mempool(&V1);
2192 mbedtls_mpi_init_mempool(&V2);
Jens Wiklander817466c2018-05-22 13:49:31 +02002193
Jens Wiklander32b31802023-10-06 16:59:46 +02002194 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&G, A, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002195
Jens Wiklander32b31802023-10-06 16:59:46 +02002196 if (mbedtls_mpi_cmp_int(&G, 1) != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002197 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2198 goto cleanup;
2199 }
2200
Jens Wiklander32b31802023-10-06 16:59:46 +02002201 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&TA, A, N));
2202 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TU, &TA));
2203 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TB, N));
2204 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&TV, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002205
Jens Wiklander32b31802023-10-06 16:59:46 +02002206 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U1, 1));
2207 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&U2, 0));
2208 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V1, 0));
2209 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&V2, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002210
Jens Wiklander32b31802023-10-06 16:59:46 +02002211 do {
2212 while ((TU.p[0] & 1) == 0) {
2213 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TU, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002214
Jens Wiklander32b31802023-10-06 16:59:46 +02002215 if ((U1.p[0] & 1) != 0 || (U2.p[0] & 1) != 0) {
2216 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&U1, &U1, &TB));
2217 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &TA));
Jens Wiklander817466c2018-05-22 13:49:31 +02002218 }
2219
Jens Wiklander32b31802023-10-06 16:59:46 +02002220 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U1, 1));
2221 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&U2, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002222 }
2223
Jens Wiklander32b31802023-10-06 16:59:46 +02002224 while ((TV.p[0] & 1) == 0) {
2225 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&TV, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002226
Jens Wiklander32b31802023-10-06 16:59:46 +02002227 if ((V1.p[0] & 1) != 0 || (V2.p[0] & 1) != 0) {
2228 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, &TB));
2229 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &TA));
Jens Wiklander817466c2018-05-22 13:49:31 +02002230 }
2231
Jens Wiklander32b31802023-10-06 16:59:46 +02002232 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V1, 1));
2233 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&V2, 1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002234 }
2235
Jens Wiklander32b31802023-10-06 16:59:46 +02002236 if (mbedtls_mpi_cmp_mpi(&TU, &TV) >= 0) {
2237 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TU, &TU, &TV));
2238 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U1, &U1, &V1));
2239 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&U2, &U2, &V2));
2240 } else {
2241 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&TV, &TV, &TU));
2242 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, &U1));
2243 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V2, &V2, &U2));
Jens Wiklander817466c2018-05-22 13:49:31 +02002244 }
Jens Wiklander32b31802023-10-06 16:59:46 +02002245 } while (mbedtls_mpi_cmp_int(&TU, 0) != 0);
2246
2247 while (mbedtls_mpi_cmp_int(&V1, 0) < 0) {
2248 MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&V1, &V1, N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002249 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002250
Jens Wiklander32b31802023-10-06 16:59:46 +02002251 while (mbedtls_mpi_cmp_mpi(&V1, N) >= 0) {
2252 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(&V1, &V1, N));
2253 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002254
Jens Wiklander32b31802023-10-06 16:59:46 +02002255 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(X, &V1));
Jens Wiklander817466c2018-05-22 13:49:31 +02002256
2257cleanup:
2258
Jens Wiklander32b31802023-10-06 16:59:46 +02002259 mbedtls_mpi_free(&TA); mbedtls_mpi_free(&TU); mbedtls_mpi_free(&U1); mbedtls_mpi_free(&U2);
2260 mbedtls_mpi_free(&G); mbedtls_mpi_free(&TB); mbedtls_mpi_free(&TV);
2261 mbedtls_mpi_free(&V1); mbedtls_mpi_free(&V2);
Jens Wiklander817466c2018-05-22 13:49:31 +02002262
Jens Wiklander32b31802023-10-06 16:59:46 +02002263 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002264}
2265
2266#if defined(MBEDTLS_GENPRIME)
2267
2268static const int small_prime[] =
2269{
Jens Wiklander32b31802023-10-06 16:59:46 +02002270 3, 5, 7, 11, 13, 17, 19, 23,
2271 29, 31, 37, 41, 43, 47, 53, 59,
2272 61, 67, 71, 73, 79, 83, 89, 97,
2273 101, 103, 107, 109, 113, 127, 131, 137,
2274 139, 149, 151, 157, 163, 167, 173, 179,
2275 181, 191, 193, 197, 199, 211, 223, 227,
2276 229, 233, 239, 241, 251, 257, 263, 269,
2277 271, 277, 281, 283, 293, 307, 311, 313,
2278 317, 331, 337, 347, 349, 353, 359, 367,
2279 373, 379, 383, 389, 397, 401, 409, 419,
2280 421, 431, 433, 439, 443, 449, 457, 461,
2281 463, 467, 479, 487, 491, 499, 503, 509,
2282 521, 523, 541, 547, 557, 563, 569, 571,
2283 577, 587, 593, 599, 601, 607, 613, 617,
2284 619, 631, 641, 643, 647, 653, 659, 661,
2285 673, 677, 683, 691, 701, 709, 719, 727,
2286 733, 739, 743, 751, 757, 761, 769, 773,
2287 787, 797, 809, 811, 821, 823, 827, 829,
2288 839, 853, 857, 859, 863, 877, 881, 883,
2289 887, 907, 911, 919, 929, 937, 941, 947,
2290 953, 967, 971, 977, 983, 991, 997, -103
Jens Wiklander817466c2018-05-22 13:49:31 +02002291};
2292
2293/*
2294 * Small divisors test (X must be positive)
2295 *
2296 * Return values:
2297 * 0: no small factor (possible prime, more tests needed)
2298 * 1: certain prime
2299 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2300 * other negative: error
2301 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002302static int mpi_check_small_factors(const mbedtls_mpi *X)
Jens Wiklander817466c2018-05-22 13:49:31 +02002303{
2304 int ret = 0;
2305 size_t i;
2306 mbedtls_mpi_uint r;
2307
Jens Wiklander32b31802023-10-06 16:59:46 +02002308 if ((X->p[0] & 1) == 0) {
2309 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2310 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002311
Jens Wiklander32b31802023-10-06 16:59:46 +02002312 for (i = 0; small_prime[i] > 0; i++) {
2313 if (mbedtls_mpi_cmp_int(X, small_prime[i]) <= 0) {
2314 return 1;
2315 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002316
Jens Wiklander32b31802023-10-06 16:59:46 +02002317 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, small_prime[i]));
Jens Wiklander817466c2018-05-22 13:49:31 +02002318
Jens Wiklander32b31802023-10-06 16:59:46 +02002319 if (r == 0) {
2320 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2321 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002322 }
2323
2324cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02002325 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002326}
2327
2328/*
2329 * Miller-Rabin pseudo-primality test (HAC 4.24)
2330 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002331static int mpi_miller_rabin(const mbedtls_mpi *X, size_t rounds,
2332 int (*f_rng)(void *, unsigned char *, size_t),
2333 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002334{
2335 int ret, count;
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002336 size_t i, j, k, s;
Jens Wiklander817466c2018-05-22 13:49:31 +02002337 mbedtls_mpi W, R, T, A, RR;
2338
Jens Wiklander32b31802023-10-06 16:59:46 +02002339 MPI_VALIDATE_RET(X != NULL);
2340 MPI_VALIDATE_RET(f_rng != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002341
Jens Wiklander32b31802023-10-06 16:59:46 +02002342 mbedtls_mpi_init_mempool(&W); mbedtls_mpi_init_mempool(&R);
2343 mbedtls_mpi_init_mempool(&T); mbedtls_mpi_init_mempool(&A);
2344 mbedtls_mpi_init_mempool(&RR);
Jens Wiklander817466c2018-05-22 13:49:31 +02002345
2346 /*
2347 * W = |X| - 1
2348 * R = W >> lsb( W )
2349 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002350 MBEDTLS_MPI_CHK(mbedtls_mpi_sub_int(&W, X, 1));
2351 s = mbedtls_mpi_lsb(&W);
2352 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&R, &W));
2353 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&R, s));
Jens Wiklander817466c2018-05-22 13:49:31 +02002354
Jens Wiklander32b31802023-10-06 16:59:46 +02002355 for (i = 0; i < rounds; i++) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002356 /*
2357 * pick a random A, 1 < A < |X| - 1
2358 */
Jens Wiklander817466c2018-05-22 13:49:31 +02002359 count = 0;
2360 do {
Jens Wiklander32b31802023-10-06 16:59:46 +02002361 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(&A, X->n * ciL, f_rng, p_rng));
Jens Wiklander817466c2018-05-22 13:49:31 +02002362
Jens Wiklander32b31802023-10-06 16:59:46 +02002363 j = mbedtls_mpi_bitlen(&A);
2364 k = mbedtls_mpi_bitlen(&W);
Jens Wiklander817466c2018-05-22 13:49:31 +02002365 if (j > k) {
Jens Wiklander32b31802023-10-06 16:59:46 +02002366 A.p[A.n - 1] &= ((mbedtls_mpi_uint) 1 << (k - (A.n - 1) * biL - 1)) - 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02002367 }
2368
Jens Wiklander117cce92018-11-27 12:21:24 +01002369 if (count++ > 300) {
Jens Wiklander336e3292019-01-17 11:14:38 +01002370 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2371 goto cleanup;
Jens Wiklander817466c2018-05-22 13:49:31 +02002372 }
2373
Jens Wiklander32b31802023-10-06 16:59:46 +02002374 } while (mbedtls_mpi_cmp_mpi(&A, &W) >= 0 ||
2375 mbedtls_mpi_cmp_int(&A, 1) <= 0);
Jens Wiklander817466c2018-05-22 13:49:31 +02002376
2377 /*
2378 * A = A^R mod |X|
2379 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002380 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&A, &A, &R, X, &RR));
Jens Wiklander817466c2018-05-22 13:49:31 +02002381
Jens Wiklander32b31802023-10-06 16:59:46 +02002382 if (mbedtls_mpi_cmp_mpi(&A, &W) == 0 ||
2383 mbedtls_mpi_cmp_int(&A, 1) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002384 continue;
Jens Wiklander32b31802023-10-06 16:59:46 +02002385 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002386
2387 j = 1;
Jens Wiklander32b31802023-10-06 16:59:46 +02002388 while (j < s && mbedtls_mpi_cmp_mpi(&A, &W) != 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002389 /*
2390 * A = A * A mod |X|
2391 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002392 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &A, &A));
2393 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&A, &T, X));
Jens Wiklander817466c2018-05-22 13:49:31 +02002394
Jens Wiklander32b31802023-10-06 16:59:46 +02002395 if (mbedtls_mpi_cmp_int(&A, 1) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002396 break;
Jens Wiklander32b31802023-10-06 16:59:46 +02002397 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002398
2399 j++;
2400 }
2401
2402 /*
2403 * not prime if A != |X| - 1 or A == 1
2404 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002405 if (mbedtls_mpi_cmp_mpi(&A, &W) != 0 ||
2406 mbedtls_mpi_cmp_int(&A, 1) == 0) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002407 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2408 break;
2409 }
2410 }
2411
2412cleanup:
Jens Wiklander32b31802023-10-06 16:59:46 +02002413 mbedtls_mpi_free(&W); mbedtls_mpi_free(&R);
2414 mbedtls_mpi_free(&T); mbedtls_mpi_free(&A);
2415 mbedtls_mpi_free(&RR);
Jens Wiklander817466c2018-05-22 13:49:31 +02002416
Jens Wiklander32b31802023-10-06 16:59:46 +02002417 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002418}
2419
2420/*
2421 * Pseudo-primality test: small factors, then Miller-Rabin
2422 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002423int mbedtls_mpi_is_prime_ext(const mbedtls_mpi *X, int rounds,
2424 int (*f_rng)(void *, unsigned char *, size_t),
2425 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002426{
Jerome Forissier11fa71b2020-04-20 17:17:56 +02002427 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Jens Wiklander817466c2018-05-22 13:49:31 +02002428 mbedtls_mpi XX;
Jens Wiklander32b31802023-10-06 16:59:46 +02002429 MPI_VALIDATE_RET(X != NULL);
2430 MPI_VALIDATE_RET(f_rng != NULL);
Jens Wiklander817466c2018-05-22 13:49:31 +02002431
2432 XX.s = 1;
2433 XX.n = X->n;
2434 XX.p = X->p;
2435
Jens Wiklander32b31802023-10-06 16:59:46 +02002436 if (mbedtls_mpi_cmp_int(&XX, 0) == 0 ||
2437 mbedtls_mpi_cmp_int(&XX, 1) == 0) {
2438 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Jens Wiklander817466c2018-05-22 13:49:31 +02002439 }
2440
Jens Wiklander32b31802023-10-06 16:59:46 +02002441 if (mbedtls_mpi_cmp_int(&XX, 2) == 0) {
2442 return 0;
2443 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002444
Jens Wiklander32b31802023-10-06 16:59:46 +02002445 if ((ret = mpi_check_small_factors(&XX)) != 0) {
2446 if (ret == 1) {
2447 return 0;
2448 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002449
Jens Wiklander32b31802023-10-06 16:59:46 +02002450 return ret;
2451 }
2452
2453 return mpi_miller_rabin(&XX, rounds, f_rng, p_rng);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002454}
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002455
Jens Wiklander817466c2018-05-22 13:49:31 +02002456/*
2457 * Prime number generation
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002458 *
2459 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2460 * be either 1024 bits or 1536 bits long, and flags must contain
2461 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Jens Wiklander817466c2018-05-22 13:49:31 +02002462 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002463int mbedtls_mpi_gen_prime(mbedtls_mpi *X, size_t nbits, int flags,
2464 int (*f_rng)(void *, unsigned char *, size_t),
2465 void *p_rng)
Jens Wiklander817466c2018-05-22 13:49:31 +02002466{
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002467#ifdef MBEDTLS_HAVE_INT64
2468// ceil(2^63.5)
2469#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2470#else
2471// ceil(2^31.5)
2472#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2473#endif
2474 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Jens Wiklander817466c2018-05-22 13:49:31 +02002475 size_t k, n;
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002476 int rounds;
Jens Wiklander817466c2018-05-22 13:49:31 +02002477 mbedtls_mpi_uint r;
2478 mbedtls_mpi Y;
2479
Jens Wiklander32b31802023-10-06 16:59:46 +02002480 MPI_VALIDATE_RET(X != NULL);
2481 MPI_VALIDATE_RET(f_rng != NULL);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002482
Jens Wiklander32b31802023-10-06 16:59:46 +02002483 if (nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS) {
2484 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2485 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002486
Jens Wiklander32b31802023-10-06 16:59:46 +02002487 mbedtls_mpi_init_mempool(&Y);
Jens Wiklander817466c2018-05-22 13:49:31 +02002488
Jens Wiklander32b31802023-10-06 16:59:46 +02002489 n = BITS_TO_LIMBS(nbits);
Jens Wiklander817466c2018-05-22 13:49:31 +02002490
Jens Wiklander32b31802023-10-06 16:59:46 +02002491 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR) == 0) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002492 /*
2493 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2494 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002495 rounds = ((nbits >= 1300) ? 2 : (nbits >= 850) ? 3 :
2496 (nbits >= 650) ? 4 : (nbits >= 350) ? 8 :
2497 (nbits >= 250) ? 12 : (nbits >= 150) ? 18 : 27);
2498 } else {
Jens Wiklander817466c2018-05-22 13:49:31 +02002499 /*
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002500 * 2^-100 error probability, number of rounds computed based on HAC,
2501 * fact 4.48
Jens Wiklander817466c2018-05-22 13:49:31 +02002502 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002503 rounds = ((nbits >= 1450) ? 4 : (nbits >= 1150) ? 5 :
2504 (nbits >= 1000) ? 6 : (nbits >= 850) ? 7 :
2505 (nbits >= 750) ? 8 : (nbits >= 500) ? 13 :
2506 (nbits >= 250) ? 28 : (nbits >= 150) ? 40 : 51);
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002507 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002508
Jens Wiklander32b31802023-10-06 16:59:46 +02002509 while (1) {
2510 MBEDTLS_MPI_CHK(mbedtls_mpi_fill_random(X, n * ciL, f_rng, p_rng));
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002511 /* 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 +02002512 if (X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2) {
2513 continue;
2514 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002515
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002516 k = n * biL;
Jens Wiklander32b31802023-10-06 16:59:46 +02002517 if (k > nbits) {
2518 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(X, k - nbits));
2519 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002520 X->p[0] |= 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02002521
Jens Wiklander32b31802023-10-06 16:59:46 +02002522 if ((flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH) == 0) {
2523 ret = mbedtls_mpi_is_prime_ext(X, rounds, f_rng, p_rng);
Jens Wiklander817466c2018-05-22 13:49:31 +02002524
Jens Wiklander32b31802023-10-06 16:59:46 +02002525 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
Jens Wiklander817466c2018-05-22 13:49:31 +02002526 goto cleanup;
Jens Wiklander32b31802023-10-06 16:59:46 +02002527 }
2528 } else {
Jens Wiklander817466c2018-05-22 13:49:31 +02002529 /*
Jens Wiklander32b31802023-10-06 16:59:46 +02002530 * A necessary condition for Y and X = 2Y + 1 to be prime
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002531 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2532 * Make sure it is satisfied, while keeping X = 3 mod 4
Jens Wiklander817466c2018-05-22 13:49:31 +02002533 */
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002534
2535 X->p[0] |= 2;
2536
Jens Wiklander32b31802023-10-06 16:59:46 +02002537 MBEDTLS_MPI_CHK(mbedtls_mpi_mod_int(&r, X, 3));
2538 if (r == 0) {
2539 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 8));
2540 } else if (r == 1) {
2541 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 4));
2542 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002543
2544 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
Jens Wiklander32b31802023-10-06 16:59:46 +02002545 MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&Y, X));
2546 MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(&Y, 1));
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002547
Jens Wiklander32b31802023-10-06 16:59:46 +02002548 while (1) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002549 /*
2550 * First, check small factors for X and Y
2551 * before doing Miller-Rabin on any of them
2552 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002553 if ((ret = mpi_check_small_factors(X)) == 0 &&
2554 (ret = mpi_check_small_factors(&Y)) == 0 &&
2555 (ret = mpi_miller_rabin(X, rounds, f_rng, p_rng))
2556 == 0 &&
2557 (ret = mpi_miller_rabin(&Y, rounds, f_rng, p_rng))
2558 == 0) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002559 goto cleanup;
Jens Wiklander32b31802023-10-06 16:59:46 +02002560 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002561
Jens Wiklander32b31802023-10-06 16:59:46 +02002562 if (ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE) {
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002563 goto cleanup;
Jens Wiklander32b31802023-10-06 16:59:46 +02002564 }
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002565
2566 /*
2567 * Next candidates. We want to preserve Y = (X-1) / 2 and
2568 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2569 * so up Y by 6 and X by 12.
2570 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002571 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(X, X, 12));
2572 MBEDTLS_MPI_CHK(mbedtls_mpi_add_int(&Y, &Y, 6));
Jens Wiklander3d3b0592019-03-20 15:30:29 +01002573 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002574 }
2575 }
2576
2577cleanup:
2578
Jens Wiklander32b31802023-10-06 16:59:46 +02002579 mbedtls_mpi_free(&Y);
Jens Wiklander817466c2018-05-22 13:49:31 +02002580
Jens Wiklander32b31802023-10-06 16:59:46 +02002581 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002582}
2583
2584#endif /* MBEDTLS_GENPRIME */
2585
2586#if defined(MBEDTLS_SELF_TEST)
2587
2588#define GCD_PAIR_COUNT 3
2589
2590static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2591{
2592 { 693, 609, 21 },
2593 { 1764, 868, 28 },
2594 { 768454923, 542167814, 1 }
2595};
2596
2597/*
2598 * Checkup routine
2599 */
Jens Wiklander32b31802023-10-06 16:59:46 +02002600int mbedtls_mpi_self_test(int verbose)
Jens Wiklander817466c2018-05-22 13:49:31 +02002601{
2602 int ret, i;
2603 mbedtls_mpi A, E, N, X, Y, U, V;
2604
Jens Wiklander32b31802023-10-06 16:59:46 +02002605 mbedtls_mpi_init_mempool(&A); mbedtls_mpi_init_mempool(&E);
2606 mbedtls_mpi_init_mempool(&N); mbedtls_mpi_init_mempool(&X);
2607 mbedtls_mpi_init_mempool(&Y); mbedtls_mpi_init_mempool(&U);
2608 mbedtls_mpi_init_mempool(&V);
Jens Wiklander817466c2018-05-22 13:49:31 +02002609
Jens Wiklander32b31802023-10-06 16:59:46 +02002610 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&A, 16,
2611 "EFE021C2645FD1DC586E69184AF4A31E" \
2612 "D5F53E93B5F123FA41680867BA110131" \
2613 "944FE7952E2517337780CB0DB80E61AA" \
2614 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002615
Jens Wiklander32b31802023-10-06 16:59:46 +02002616 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&E, 16,
2617 "B2E7EFD37075B9F03FF989C7C5051C20" \
2618 "34D2A323810251127E7BF8625A4F49A5" \
2619 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2620 "5B5C25763222FEFCCFC38B832366C29E"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002621
Jens Wiklander32b31802023-10-06 16:59:46 +02002622 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&N, 16,
2623 "0066A198186C18C10B2F5ED9B522752A" \
2624 "9830B69916E535C8F047518A889A43A5" \
2625 "94B6BED27A168D31D4A52F88925AA8F5"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002626
Jens Wiklander32b31802023-10-06 16:59:46 +02002627 MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&X, &A, &N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002628
Jens Wiklander32b31802023-10-06 16:59:46 +02002629 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2630 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2631 "9E857EA95A03512E2BAE7391688D264A" \
2632 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2633 "8001B72E848A38CAE1C65F78E56ABDEF" \
2634 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2635 "ECF677152EF804370C1A305CAF3B5BF1" \
2636 "30879B56C61DE584A0F53A2447A51E"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002637
Jens Wiklander32b31802023-10-06 16:59:46 +02002638 if (verbose != 0) {
2639 mbedtls_printf(" MPI test #1 (mul_mpi): ");
2640 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002641
Jens Wiklander32b31802023-10-06 16:59:46 +02002642 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2643 if (verbose != 0) {
2644 mbedtls_printf("failed\n");
2645 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002646
2647 ret = 1;
2648 goto cleanup;
2649 }
2650
Jens Wiklander32b31802023-10-06 16:59:46 +02002651 if (verbose != 0) {
2652 mbedtls_printf("passed\n");
2653 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002654
Jens Wiklander32b31802023-10-06 16:59:46 +02002655 MBEDTLS_MPI_CHK(mbedtls_mpi_div_mpi(&X, &Y, &A, &N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002656
Jens Wiklander32b31802023-10-06 16:59:46 +02002657 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2658 "256567336059E52CAE22925474705F39A94"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002659
Jens Wiklander32b31802023-10-06 16:59:46 +02002660 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&V, 16,
2661 "6613F26162223DF488E9CD48CC132C7A" \
2662 "0AC93C701B001B092E4E5B9F73BCD27B" \
2663 "9EE50D0657C77F374E903CDFA4C642"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002664
Jens Wiklander32b31802023-10-06 16:59:46 +02002665 if (verbose != 0) {
2666 mbedtls_printf(" MPI test #2 (div_mpi): ");
2667 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002668
Jens Wiklander32b31802023-10-06 16:59:46 +02002669 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0 ||
2670 mbedtls_mpi_cmp_mpi(&Y, &V) != 0) {
2671 if (verbose != 0) {
2672 mbedtls_printf("failed\n");
2673 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002674
2675 ret = 1;
2676 goto cleanup;
2677 }
2678
Jens Wiklander32b31802023-10-06 16:59:46 +02002679 if (verbose != 0) {
2680 mbedtls_printf("passed\n");
2681 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002682
Jens Wiklander32b31802023-10-06 16:59:46 +02002683 MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&X, &A, &E, &N, NULL));
Jens Wiklander817466c2018-05-22 13:49:31 +02002684
Jens Wiklander32b31802023-10-06 16:59:46 +02002685 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2686 "36E139AEA55215609D2816998ED020BB" \
2687 "BD96C37890F65171D948E9BC7CBAA4D9" \
2688 "325D24D6A3C12710F10A09FA08AB87"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002689
Jens Wiklander32b31802023-10-06 16:59:46 +02002690 if (verbose != 0) {
2691 mbedtls_printf(" MPI test #3 (exp_mod): ");
2692 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002693
Jens Wiklander32b31802023-10-06 16:59:46 +02002694 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2695 if (verbose != 0) {
2696 mbedtls_printf("failed\n");
2697 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002698
2699 ret = 1;
2700 goto cleanup;
2701 }
2702
Jens Wiklander32b31802023-10-06 16:59:46 +02002703 if (verbose != 0) {
2704 mbedtls_printf("passed\n");
2705 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002706
Jens Wiklander32b31802023-10-06 16:59:46 +02002707 MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&X, &A, &N));
Jens Wiklander817466c2018-05-22 13:49:31 +02002708
Jens Wiklander32b31802023-10-06 16:59:46 +02002709 MBEDTLS_MPI_CHK(mbedtls_mpi_read_string(&U, 16,
2710 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2711 "C3DBA76456363A10869622EAC2DD84EC" \
2712 "C5B8A74DAC4D09E03B5E0BE779F2DF61"));
Jens Wiklander817466c2018-05-22 13:49:31 +02002713
Jens Wiklander32b31802023-10-06 16:59:46 +02002714 if (verbose != 0) {
2715 mbedtls_printf(" MPI test #4 (inv_mod): ");
2716 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002717
Jens Wiklander32b31802023-10-06 16:59:46 +02002718 if (mbedtls_mpi_cmp_mpi(&X, &U) != 0) {
2719 if (verbose != 0) {
2720 mbedtls_printf("failed\n");
2721 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002722
2723 ret = 1;
2724 goto cleanup;
2725 }
2726
Jens Wiklander32b31802023-10-06 16:59:46 +02002727 if (verbose != 0) {
2728 mbedtls_printf("passed\n");
2729 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002730
Jens Wiklander32b31802023-10-06 16:59:46 +02002731 if (verbose != 0) {
2732 mbedtls_printf(" MPI test #5 (simple gcd): ");
2733 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002734
Jens Wiklander32b31802023-10-06 16:59:46 +02002735 for (i = 0; i < GCD_PAIR_COUNT; i++) {
2736 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&X, gcd_pairs[i][0]));
2737 MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&Y, gcd_pairs[i][1]));
Jens Wiklander817466c2018-05-22 13:49:31 +02002738
Jens Wiklander32b31802023-10-06 16:59:46 +02002739 MBEDTLS_MPI_CHK(mbedtls_mpi_gcd(&A, &X, &Y));
Jens Wiklander817466c2018-05-22 13:49:31 +02002740
Jens Wiklander32b31802023-10-06 16:59:46 +02002741 if (mbedtls_mpi_cmp_int(&A, gcd_pairs[i][2]) != 0) {
2742 if (verbose != 0) {
2743 mbedtls_printf("failed at %d\n", i);
2744 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002745
2746 ret = 1;
2747 goto cleanup;
2748 }
2749 }
2750
Jens Wiklander32b31802023-10-06 16:59:46 +02002751 if (verbose != 0) {
2752 mbedtls_printf("passed\n");
2753 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002754
2755cleanup:
2756
Jens Wiklander32b31802023-10-06 16:59:46 +02002757 if (ret != 0 && verbose != 0) {
2758 mbedtls_printf("Unexpected error, return code = %08X\n", (unsigned int) ret);
2759 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002760
Jens Wiklander32b31802023-10-06 16:59:46 +02002761 mbedtls_mpi_free(&A); mbedtls_mpi_free(&E); mbedtls_mpi_free(&N); mbedtls_mpi_free(&X);
2762 mbedtls_mpi_free(&Y); mbedtls_mpi_free(&U); mbedtls_mpi_free(&V);
Jens Wiklander817466c2018-05-22 13:49:31 +02002763
Jens Wiklander32b31802023-10-06 16:59:46 +02002764 if (verbose != 0) {
2765 mbedtls_printf("\n");
2766 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002767
Jens Wiklander32b31802023-10-06 16:59:46 +02002768 return ret;
Jens Wiklander817466c2018-05-22 13:49:31 +02002769}
2770
2771#endif /* MBEDTLS_SELF_TEST */
2772
2773#endif /* MBEDTLS_BIGNUM_C */