blob: c513525e713b6f776ed74842a27ef88db29c99a3 [file] [log] [blame]
Paul Bakker5121ce52009-01-03 21:22:43 +00001/*
2 * Multi-precision integer library
3 *
Manuel Pégourié-Gonnard6fb81872015-07-27 11:11:48 +02004 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
Manuel Pégourié-Gonnard37ff1402015-09-04 14:21:07 +02005 * SPDX-License-Identifier: Apache-2.0
6 *
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.
Paul Bakkerb96f1542010-07-18 20:36:00 +000018 *
Manuel Pégourié-Gonnardfe446432015-03-06 13:17:10 +000019 * This file is part of mbed TLS (https://tls.mbed.org)
Paul Bakker5121ce52009-01-03 21:22:43 +000020 */
Simon Butcher15b15d12015-11-26 19:35:03 +000021
Paul Bakker5121ce52009-01-03 21:22:43 +000022/*
Simon Butcher15b15d12015-11-26 19:35:03 +000023 * The following sources were referenced in the design of this Multi-precision
24 * Integer library:
Paul Bakker5121ce52009-01-03 21:22:43 +000025 *
Simon Butcher15b15d12015-11-26 19:35:03 +000026 * [1] Handbook of Applied Cryptography - 1997
27 * Menezes, van Oorschot and Vanstone
28 *
29 * [2] Multi-Precision Math
30 * Tom St Denis
31 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
32 *
33 * [3] GNU Multi-Precision Arithmetic Library
34 * https://gmplib.org/manual/index.html
35 *
Simon Butcherf5ba0452015-12-27 23:01:55 +000036 */
Paul Bakker5121ce52009-01-03 21:22:43 +000037
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020038#if !defined(MBEDTLS_CONFIG_FILE)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000039#include "mbedtls/config.h"
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020040#else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020041#include MBEDTLS_CONFIG_FILE
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020042#endif
Paul Bakker5121ce52009-01-03 21:22:43 +000043
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020044#if defined(MBEDTLS_BIGNUM_C)
Paul Bakker5121ce52009-01-03 21:22:43 +000045
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000046#include "mbedtls/bignum.h"
47#include "mbedtls/bn_mul.h"
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050048#include "mbedtls/platform_util.h"
Paul Bakker5121ce52009-01-03 21:22:43 +000049
Rich Evans00ab4702015-02-06 13:43:58 +000050#include <string.h>
51
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020052#if defined(MBEDTLS_PLATFORM_C)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000053#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020054#else
Rich Evans00ab4702015-02-06 13:43:58 +000055#include <stdio.h>
56#include <stdlib.h>
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020057#define mbedtls_printf printf
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +020058#define mbedtls_calloc calloc
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020059#define mbedtls_free free
Paul Bakker6e339b52013-07-03 13:37:05 +020060#endif
61
Hanno Becker73d7d792018-12-11 10:35:51 +000062#define MPI_VALIDATE_RET( cond ) \
63 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
64#define MPI_VALIDATE( cond ) \
65 MBEDTLS_INTERNAL_VALIDATE( cond )
66
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020067#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
Paul Bakker5121ce52009-01-03 21:22:43 +000068#define biL (ciL << 3) /* bits in limb */
69#define biH (ciL << 2) /* half limb size */
70
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +010071#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
72
Paul Bakker5121ce52009-01-03 21:22:43 +000073/*
74 * Convert between bits/chars and number of limbs
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020075 * Divide first in order to avoid potential overflows
Paul Bakker5121ce52009-01-03 21:22:43 +000076 */
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020077#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
78#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
Paul Bakker5121ce52009-01-03 21:22:43 +000079
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050080/* Implementation that should never be optimized out by the compiler */
Andres Amaya Garcia6698d2f2018-04-24 08:39:07 -050081static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
82{
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050083 mbedtls_platform_zeroize( v, ciL * n );
84}
85
Paul Bakker5121ce52009-01-03 21:22:43 +000086/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000087 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000088 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020089void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000090{
Hanno Becker73d7d792018-12-11 10:35:51 +000091 MPI_VALIDATE( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +000092
Paul Bakker6c591fa2011-05-05 11:49:20 +000093 X->s = 1;
94 X->n = 0;
95 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +000096}
97
98/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000099 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +0000100 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200101void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000102{
Paul Bakker6c591fa2011-05-05 11:49:20 +0000103 if( X == NULL )
104 return;
Paul Bakker5121ce52009-01-03 21:22:43 +0000105
Paul Bakker6c591fa2011-05-05 11:49:20 +0000106 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +0000107 {
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200108 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200109 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000110 }
111
Paul Bakker6c591fa2011-05-05 11:49:20 +0000112 X->s = 1;
113 X->n = 0;
114 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000115}
116
117/*
118 * Enlarge to the specified number of limbs
119 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200120int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000121{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200122 mbedtls_mpi_uint *p;
Hanno Becker73d7d792018-12-11 10:35:51 +0000123 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000124
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200125 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200126 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000127
Paul Bakker5121ce52009-01-03 21:22:43 +0000128 if( X->n < nblimbs )
129 {
Simon Butcher29176892016-05-20 00:19:09 +0100130 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200131 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000132
Paul Bakker5121ce52009-01-03 21:22:43 +0000133 if( X->p != NULL )
134 {
135 memcpy( p, X->p, X->n * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200136 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200137 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000138 }
139
140 X->n = nblimbs;
141 X->p = p;
142 }
143
144 return( 0 );
145}
146
147/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100148 * Resize down as much as possible,
149 * while keeping at least the specified number of limbs
150 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200151int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100152{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200153 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100154 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000155 MPI_VALIDATE_RET( X != NULL );
156
157 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
158 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100159
Gilles Peskine27c15c72020-01-20 21:17:43 +0100160 /* Actually resize up if there are currently fewer than nblimbs limbs. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100161 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200162 return( mbedtls_mpi_grow( X, nblimbs ) );
Gilles Peskine56427c22020-01-21 13:59:51 +0100163 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100164
165 for( i = X->n - 1; i > 0; i-- )
166 if( X->p[i] != 0 )
167 break;
168 i++;
169
170 if( i < nblimbs )
171 i = nblimbs;
172
Simon Butcher29176892016-05-20 00:19:09 +0100173 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200174 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100175
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100176 if( X->p != NULL )
177 {
178 memcpy( p, X->p, i * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200179 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200180 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100181 }
182
183 X->n = i;
184 X->p = p;
185
186 return( 0 );
187}
188
189/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000190 * Copy the contents of Y into X
191 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200192int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000193{
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100194 int ret = 0;
Paul Bakker23986e52011-04-24 08:57:21 +0000195 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000196 MPI_VALIDATE_RET( X != NULL );
197 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000198
199 if( X == Y )
200 return( 0 );
201
Gilles Peskine3e9f5222020-01-20 21:12:50 +0100202 if( Y->n == 0 )
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200203 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200204 mbedtls_mpi_free( X );
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200205 return( 0 );
206 }
207
Paul Bakker5121ce52009-01-03 21:22:43 +0000208 for( i = Y->n - 1; i > 0; i-- )
209 if( Y->p[i] != 0 )
210 break;
211 i++;
212
213 X->s = Y->s;
214
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100215 if( X->n < i )
216 {
217 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
218 }
219 else
220 {
221 memset( X->p + i, 0, ( X->n - i ) * ciL );
222 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000223
Paul Bakker5121ce52009-01-03 21:22:43 +0000224 memcpy( X->p, Y->p, i * ciL );
225
226cleanup:
227
228 return( ret );
229}
230
231/*
232 * Swap the contents of X and Y
233 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200234void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000235{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200236 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000237 MPI_VALIDATE( X != NULL );
238 MPI_VALIDATE( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000239
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200240 memcpy( &T, X, sizeof( mbedtls_mpi ) );
241 memcpy( X, Y, sizeof( mbedtls_mpi ) );
242 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000243}
244
245/*
Gilles Peskinec81c5882020-06-04 19:14:58 +0200246 * Conditionally assign dest = src, without leaking information
247 * about whether the assignment was made or not.
248 * dest and src must be arrays of limbs of size n.
249 * assign must be 0 or 1.
250 */
251static void mpi_safe_cond_assign( size_t n,
252 mbedtls_mpi_uint *dest,
253 const mbedtls_mpi_uint *src,
254 unsigned char assign )
255{
256 size_t i;
257 for( i = 0; i < n; i++ )
258 dest[i] = dest[i] * ( 1 - assign ) + src[i] * assign;
259}
260
261/*
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100262 * Conditionally assign X = Y, without leaking information
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100263 * about whether the assignment was made or not.
264 * (Leaking information about the respective sizes of X and Y is ok however.)
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100265 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200266int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100267{
268 int ret = 0;
269 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000270 MPI_VALIDATE_RET( X != NULL );
271 MPI_VALIDATE_RET( Y != NULL );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100272
Pascal Junodb99183d2015-03-11 16:49:45 +0100273 /* make sure assign is 0 or 1 in a time-constant manner */
274 assign = (assign | (unsigned char)-assign) >> 7;
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100275
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200276 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100277
Paul Bakker66d5d072014-06-17 16:39:18 +0200278 X->s = X->s * ( 1 - assign ) + Y->s * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100279
Gilles Peskinec81c5882020-06-04 19:14:58 +0200280 mpi_safe_cond_assign( Y->n, X->p, Y->p, assign );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100281
Gilles Peskinec81c5882020-06-04 19:14:58 +0200282 for( i = Y->n; i < X->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200283 X->p[i] *= ( 1 - assign );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100284
285cleanup:
286 return( ret );
287}
288
289/*
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100290 * Conditionally swap X and Y, without leaking information
291 * about whether the swap was made or not.
292 * Here it is not ok to simply swap the pointers, which whould lead to
293 * different memory access patterns when X and Y are used afterwards.
294 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200295int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100296{
297 int ret, s;
298 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200299 mbedtls_mpi_uint tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +0000300 MPI_VALIDATE_RET( X != NULL );
301 MPI_VALIDATE_RET( Y != NULL );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100302
303 if( X == Y )
304 return( 0 );
305
Pascal Junodb99183d2015-03-11 16:49:45 +0100306 /* make sure swap is 0 or 1 in a time-constant manner */
307 swap = (swap | (unsigned char)-swap) >> 7;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100308
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200309 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
310 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100311
312 s = X->s;
Paul Bakker66d5d072014-06-17 16:39:18 +0200313 X->s = X->s * ( 1 - swap ) + Y->s * swap;
314 Y->s = Y->s * ( 1 - swap ) + s * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100315
316
317 for( i = 0; i < X->n; i++ )
318 {
319 tmp = X->p[i];
Paul Bakker66d5d072014-06-17 16:39:18 +0200320 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
321 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100322 }
323
324cleanup:
325 return( ret );
326}
327
328/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000329 * Set value from integer
330 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200331int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000332{
333 int ret;
Hanno Becker73d7d792018-12-11 10:35:51 +0000334 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000335
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200336 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000337 memset( X->p, 0, X->n * ciL );
338
339 X->p[0] = ( z < 0 ) ? -z : z;
340 X->s = ( z < 0 ) ? -1 : 1;
341
342cleanup:
343
344 return( ret );
345}
346
347/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000348 * Get a specific bit
349 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200350int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000351{
Hanno Becker73d7d792018-12-11 10:35:51 +0000352 MPI_VALIDATE_RET( X != NULL );
353
Paul Bakker2f5947e2011-05-18 15:47:11 +0000354 if( X->n * biL <= pos )
355 return( 0 );
356
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200357 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000358}
359
Gilles Peskine11cdb052018-11-20 16:47:47 +0100360/* Get a specific byte, without range checks. */
361#define GET_BYTE( X, i ) \
362 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
363
Paul Bakker2f5947e2011-05-18 15:47:11 +0000364/*
365 * Set a bit to a specific value of 0 or 1
366 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200367int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000368{
369 int ret = 0;
370 size_t off = pos / biL;
371 size_t idx = pos % biL;
Hanno Becker73d7d792018-12-11 10:35:51 +0000372 MPI_VALIDATE_RET( X != NULL );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000373
374 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200375 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200376
Paul Bakker2f5947e2011-05-18 15:47:11 +0000377 if( X->n * biL <= pos )
378 {
379 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200380 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000381
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200382 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000383 }
384
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200385 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
386 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000387
388cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200389
Paul Bakker2f5947e2011-05-18 15:47:11 +0000390 return( ret );
391}
392
393/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200394 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000395 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200396size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000397{
Paul Bakker23986e52011-04-24 08:57:21 +0000398 size_t i, j, count = 0;
Hanno Beckerf25ee7f2018-12-19 16:51:02 +0000399 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000400
401 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000402 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000403 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
404 return( count );
405
406 return( 0 );
407}
408
409/*
Simon Butcher15b15d12015-11-26 19:35:03 +0000410 * Count leading zero bits in a given integer
411 */
412static size_t mbedtls_clz( const mbedtls_mpi_uint x )
413{
414 size_t j;
Manuel Pégourié-Gonnarde3e8edf2015-12-01 09:31:52 +0100415 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
Simon Butcher15b15d12015-11-26 19:35:03 +0000416
417 for( j = 0; j < biL; j++ )
418 {
419 if( x & mask ) break;
420
421 mask >>= 1;
422 }
423
424 return j;
425}
426
427/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200428 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000429 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200430size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000431{
Paul Bakker23986e52011-04-24 08:57:21 +0000432 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000433
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200434 if( X->n == 0 )
435 return( 0 );
436
Paul Bakker5121ce52009-01-03 21:22:43 +0000437 for( i = X->n - 1; i > 0; i-- )
438 if( X->p[i] != 0 )
439 break;
440
Simon Butcher15b15d12015-11-26 19:35:03 +0000441 j = biL - mbedtls_clz( X->p[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +0000442
Paul Bakker23986e52011-04-24 08:57:21 +0000443 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000444}
445
446/*
447 * Return the total size in bytes
448 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200449size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000450{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200451 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000452}
453
454/*
455 * Convert an ASCII character to digit value
456 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200457static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000458{
459 *d = 255;
460
461 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
462 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
463 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
464
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200465 if( *d >= (mbedtls_mpi_uint) radix )
466 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000467
468 return( 0 );
469}
470
471/*
472 * Import from an ASCII string
473 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200474int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000475{
Paul Bakker23986e52011-04-24 08:57:21 +0000476 int ret;
477 size_t i, j, slen, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200478 mbedtls_mpi_uint d;
479 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000480 MPI_VALIDATE_RET( X != NULL );
481 MPI_VALIDATE_RET( s != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000482
483 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000484 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000485
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200486 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000487
Paul Bakkerff60ee62010-03-16 21:09:09 +0000488 slen = strlen( s );
489
Paul Bakker5121ce52009-01-03 21:22:43 +0000490 if( radix == 16 )
491 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100492 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200493 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
494
Paul Bakkerff60ee62010-03-16 21:09:09 +0000495 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000496
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200497 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
498 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000499
Paul Bakker23986e52011-04-24 08:57:21 +0000500 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000501 {
Paul Bakker23986e52011-04-24 08:57:21 +0000502 if( i == 1 && s[i - 1] == '-' )
Paul Bakker5121ce52009-01-03 21:22:43 +0000503 {
504 X->s = -1;
505 break;
506 }
507
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200508 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200509 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000510 }
511 }
512 else
513 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200514 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000515
Paul Bakkerff60ee62010-03-16 21:09:09 +0000516 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000517 {
518 if( i == 0 && s[i] == '-' )
519 {
520 X->s = -1;
521 continue;
522 }
523
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200524 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
525 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000526
527 if( X->s == 1 )
528 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200529 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000530 }
531 else
532 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200533 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000534 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000535 }
536 }
537
538cleanup:
539
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200540 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000541
542 return( ret );
543}
544
545/*
Ron Eldora16fa292018-11-20 14:07:01 +0200546 * Helper to write the digits high-order first.
Paul Bakker5121ce52009-01-03 21:22:43 +0000547 */
Ron Eldora16fa292018-11-20 14:07:01 +0200548static int mpi_write_hlp( mbedtls_mpi *X, int radix,
549 char **p, const size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000550{
551 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200552 mbedtls_mpi_uint r;
Ron Eldora16fa292018-11-20 14:07:01 +0200553 size_t length = 0;
554 char *p_end = *p + buflen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000555
Ron Eldora16fa292018-11-20 14:07:01 +0200556 do
557 {
558 if( length >= buflen )
559 {
560 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
561 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000562
Ron Eldora16fa292018-11-20 14:07:01 +0200563 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
564 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
565 /*
566 * Write the residue in the current position, as an ASCII character.
567 */
568 if( r < 0xA )
569 *(--p_end) = (char)( '0' + r );
570 else
571 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000572
Ron Eldora16fa292018-11-20 14:07:01 +0200573 length++;
574 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000575
Ron Eldora16fa292018-11-20 14:07:01 +0200576 memmove( *p, p_end, length );
577 *p += length;
Paul Bakker5121ce52009-01-03 21:22:43 +0000578
579cleanup:
580
581 return( ret );
582}
583
584/*
585 * Export into an ASCII string
586 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100587int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
588 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000589{
Paul Bakker23986e52011-04-24 08:57:21 +0000590 int ret = 0;
591 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000592 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200593 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000594 MPI_VALIDATE_RET( X != NULL );
595 MPI_VALIDATE_RET( olen != NULL );
596 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000597
598 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000599 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000600
Hanno Beckerc1fa6cd2019-02-04 09:45:07 +0000601 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
602 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
603 * `n`. If radix > 4, this might be a strict
604 * overapproximation of the number of
605 * radix-adic digits needed to present `n`. */
606 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
607 * present `n`. */
608
Janos Follath870ed002019-03-06 13:43:02 +0000609 n += 1; /* Terminating null byte */
Hanno Beckerc1fa6cd2019-02-04 09:45:07 +0000610 n += 1; /* Compensate for the divisions above, which round down `n`
611 * in case it's not even. */
612 n += 1; /* Potential '-'-sign. */
613 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
614 * which always uses an even number of hex-digits. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000615
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100616 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000617 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100618 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200619 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000620 }
621
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100622 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200623 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000624
625 if( X->s == -1 )
Hanno Beckeraf97cae2019-02-01 16:41:30 +0000626 {
Paul Bakker5121ce52009-01-03 21:22:43 +0000627 *p++ = '-';
Hanno Beckeraf97cae2019-02-01 16:41:30 +0000628 buflen--;
629 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000630
631 if( radix == 16 )
632 {
Paul Bakker23986e52011-04-24 08:57:21 +0000633 int c;
634 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000635
Paul Bakker23986e52011-04-24 08:57:21 +0000636 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000637 {
Paul Bakker23986e52011-04-24 08:57:21 +0000638 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000639 {
Paul Bakker23986e52011-04-24 08:57:21 +0000640 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000641
Paul Bakker6c343d72014-07-10 14:36:19 +0200642 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000643 continue;
644
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000645 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000646 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000647 k = 1;
648 }
649 }
650 }
651 else
652 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200653 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000654
655 if( T.s == -1 )
656 T.s = 1;
657
Ron Eldora16fa292018-11-20 14:07:01 +0200658 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000659 }
660
661 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100662 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000663
664cleanup:
665
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200666 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000667
668 return( ret );
669}
670
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200671#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000672/*
673 * Read X from an opened file
674 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200675int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000676{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200677 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000678 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000679 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000680 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000681 * Buffer should have space for (short) label and decimal formatted MPI,
682 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000683 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200684 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000685
Hanno Becker73d7d792018-12-11 10:35:51 +0000686 MPI_VALIDATE_RET( X != NULL );
687 MPI_VALIDATE_RET( fin != NULL );
688
689 if( radix < 2 || radix > 16 )
690 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
691
Paul Bakker5121ce52009-01-03 21:22:43 +0000692 memset( s, 0, sizeof( s ) );
693 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200694 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000695
696 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000697 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200698 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000699
Hanno Beckerb2034b72017-04-26 11:46:46 +0100700 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
701 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000702
703 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100704 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000705 if( mpi_get_digit( &d, radix, *p ) != 0 )
706 break;
707
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200708 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000709}
710
711/*
712 * Write X into an opened file (or stdout if fout == NULL)
713 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200714int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000715{
Paul Bakker23986e52011-04-24 08:57:21 +0000716 int ret;
717 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000718 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000719 * Buffer should have space for (short) label and decimal formatted MPI,
720 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000721 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200722 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Hanno Becker73d7d792018-12-11 10:35:51 +0000723 MPI_VALIDATE_RET( X != NULL );
724
725 if( radix < 2 || radix > 16 )
726 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000727
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100728 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000729
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100730 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000731
732 if( p == NULL ) p = "";
733
734 plen = strlen( p );
735 slen = strlen( s );
736 s[slen++] = '\r';
737 s[slen++] = '\n';
738
739 if( fout != NULL )
740 {
741 if( fwrite( p, 1, plen, fout ) != plen ||
742 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200743 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000744 }
745 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200746 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000747
748cleanup:
749
750 return( ret );
751}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200752#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000753
Hanno Beckerda1655a2017-10-18 14:21:44 +0100754
755/* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
756 * into the storage form used by mbedtls_mpi. */
Hanno Beckerf8720072018-11-08 11:53:49 +0000757
758static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x )
759{
760 uint8_t i;
Hanno Becker92c98932019-05-01 17:09:11 +0100761 unsigned char *x_ptr;
Hanno Beckerf8720072018-11-08 11:53:49 +0000762 mbedtls_mpi_uint tmp = 0;
Hanno Becker92c98932019-05-01 17:09:11 +0100763
764 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ )
765 {
766 tmp <<= CHAR_BIT;
767 tmp |= (mbedtls_mpi_uint) *x_ptr;
768 }
769
Hanno Beckerf8720072018-11-08 11:53:49 +0000770 return( tmp );
771}
772
773static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x )
774{
775#if defined(__BYTE_ORDER__)
776
777/* Nothing to do on bigendian systems. */
778#if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ )
779 return( x );
780#endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
781
782#if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ )
783
784/* For GCC and Clang, have builtins for byte swapping. */
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000785#if defined(__GNUC__) && defined(__GNUC_PREREQ)
786#if __GNUC_PREREQ(4,3)
Hanno Beckerf8720072018-11-08 11:53:49 +0000787#define have_bswap
788#endif
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000789#endif
790
791#if defined(__clang__) && defined(__has_builtin)
792#if __has_builtin(__builtin_bswap32) && \
793 __has_builtin(__builtin_bswap64)
794#define have_bswap
795#endif
796#endif
797
Hanno Beckerf8720072018-11-08 11:53:49 +0000798#if defined(have_bswap)
799 /* The compiler is hopefully able to statically evaluate this! */
800 switch( sizeof(mbedtls_mpi_uint) )
801 {
802 case 4:
803 return( __builtin_bswap32(x) );
804 case 8:
805 return( __builtin_bswap64(x) );
806 }
807#endif
808#endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */
809#endif /* __BYTE_ORDER__ */
810
811 /* Fall back to C-based reordering if we don't know the byte order
812 * or we couldn't use a compiler-specific builtin. */
813 return( mpi_uint_bigendian_to_host_c( x ) );
814}
815
Hanno Becker2be8a552018-10-25 12:40:09 +0100816static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs )
Hanno Beckerda1655a2017-10-18 14:21:44 +0100817{
Hanno Beckerda1655a2017-10-18 14:21:44 +0100818 mbedtls_mpi_uint *cur_limb_left;
819 mbedtls_mpi_uint *cur_limb_right;
Hanno Becker2be8a552018-10-25 12:40:09 +0100820 if( limbs == 0 )
821 return;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100822
823 /*
824 * Traverse limbs and
825 * - adapt byte-order in each limb
826 * - swap the limbs themselves.
827 * For that, simultaneously traverse the limbs from left to right
828 * and from right to left, as long as the left index is not bigger
829 * than the right index (it's not a problem if limbs is odd and the
830 * indices coincide in the last iteration).
831 */
Hanno Beckerda1655a2017-10-18 14:21:44 +0100832 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 );
833 cur_limb_left <= cur_limb_right;
834 cur_limb_left++, cur_limb_right-- )
835 {
Hanno Beckerf8720072018-11-08 11:53:49 +0000836 mbedtls_mpi_uint tmp;
837 /* Note that if cur_limb_left == cur_limb_right,
838 * this code effectively swaps the bytes only once. */
839 tmp = mpi_uint_bigendian_to_host( *cur_limb_left );
840 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right );
841 *cur_limb_right = tmp;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100842 }
Hanno Beckerda1655a2017-10-18 14:21:44 +0100843}
844
Paul Bakker5121ce52009-01-03 21:22:43 +0000845/*
846 * Import X from unsigned binary data, big endian
847 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200848int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000849{
Paul Bakker23986e52011-04-24 08:57:21 +0000850 int ret;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100851 size_t const limbs = CHARS_TO_LIMBS( buflen );
852 size_t const overhead = ( limbs * ciL ) - buflen;
853 unsigned char *Xp;
Paul Bakker5121ce52009-01-03 21:22:43 +0000854
Hanno Becker8ce11a32018-12-19 16:18:52 +0000855 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +0000856 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
857
Hanno Becker073c1992017-10-17 15:17:27 +0100858 /* Ensure that target MPI has exactly the necessary number of limbs */
859 if( X->n != limbs )
860 {
861 mbedtls_mpi_free( X );
862 mbedtls_mpi_init( X );
863 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
864 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200865 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000866
Hanno Becker0e810b92019-01-03 17:13:11 +0000867 /* Avoid calling `memcpy` with NULL source argument,
868 * even if buflen is 0. */
869 if( buf != NULL )
870 {
871 Xp = (unsigned char*) X->p;
872 memcpy( Xp + overhead, buf, buflen );
Hanno Beckerda1655a2017-10-18 14:21:44 +0100873
Hanno Becker0e810b92019-01-03 17:13:11 +0000874 mpi_bigendian_to_host( X->p, limbs );
875 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000876
877cleanup:
878
879 return( ret );
880}
881
882/*
883 * Export X into unsigned binary data, big endian
884 */
Gilles Peskine11cdb052018-11-20 16:47:47 +0100885int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
886 unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000887{
Hanno Becker73d7d792018-12-11 10:35:51 +0000888 size_t stored_bytes;
Gilles Peskine11cdb052018-11-20 16:47:47 +0100889 size_t bytes_to_copy;
890 unsigned char *p;
891 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000892
Hanno Becker73d7d792018-12-11 10:35:51 +0000893 MPI_VALIDATE_RET( X != NULL );
894 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
895
896 stored_bytes = X->n * ciL;
897
Gilles Peskine11cdb052018-11-20 16:47:47 +0100898 if( stored_bytes < buflen )
899 {
900 /* There is enough space in the output buffer. Write initial
901 * null bytes and record the position at which to start
902 * writing the significant bytes. In this case, the execution
903 * trace of this function does not depend on the value of the
904 * number. */
905 bytes_to_copy = stored_bytes;
906 p = buf + buflen - stored_bytes;
907 memset( buf, 0, buflen - stored_bytes );
908 }
909 else
910 {
911 /* The output buffer is smaller than the allocated size of X.
912 * However X may fit if its leading bytes are zero. */
913 bytes_to_copy = buflen;
914 p = buf;
915 for( i = bytes_to_copy; i < stored_bytes; i++ )
916 {
917 if( GET_BYTE( X, i ) != 0 )
918 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
919 }
920 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000921
Gilles Peskine11cdb052018-11-20 16:47:47 +0100922 for( i = 0; i < bytes_to_copy; i++ )
923 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
Paul Bakker5121ce52009-01-03 21:22:43 +0000924
925 return( 0 );
926}
927
928/*
929 * Left-shift: X <<= count
930 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200931int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000932{
Paul Bakker23986e52011-04-24 08:57:21 +0000933 int ret;
934 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200935 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000936 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000937
938 v0 = count / (biL );
939 t1 = count & (biL - 1);
940
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200941 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000942
Paul Bakkerf9688572011-05-05 10:00:45 +0000943 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200944 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000945
946 ret = 0;
947
948 /*
949 * shift by count / limb_size
950 */
951 if( v0 > 0 )
952 {
Paul Bakker23986e52011-04-24 08:57:21 +0000953 for( i = X->n; i > v0; i-- )
954 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000955
Paul Bakker23986e52011-04-24 08:57:21 +0000956 for( ; i > 0; i-- )
957 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000958 }
959
960 /*
961 * shift by count % limb_size
962 */
963 if( t1 > 0 )
964 {
965 for( i = v0; i < X->n; i++ )
966 {
967 r1 = X->p[i] >> (biL - t1);
968 X->p[i] <<= t1;
969 X->p[i] |= r0;
970 r0 = r1;
971 }
972 }
973
974cleanup:
975
976 return( ret );
977}
978
979/*
980 * Right-shift: X >>= count
981 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200982int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000983{
Paul Bakker23986e52011-04-24 08:57:21 +0000984 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200985 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000986 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000987
988 v0 = count / biL;
989 v1 = count & (biL - 1);
990
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100991 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200992 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100993
Paul Bakker5121ce52009-01-03 21:22:43 +0000994 /*
995 * shift by count / limb_size
996 */
997 if( v0 > 0 )
998 {
999 for( i = 0; i < X->n - v0; i++ )
1000 X->p[i] = X->p[i + v0];
1001
1002 for( ; i < X->n; i++ )
1003 X->p[i] = 0;
1004 }
1005
1006 /*
1007 * shift by count % limb_size
1008 */
1009 if( v1 > 0 )
1010 {
Paul Bakker23986e52011-04-24 08:57:21 +00001011 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001012 {
Paul Bakker23986e52011-04-24 08:57:21 +00001013 r1 = X->p[i - 1] << (biL - v1);
1014 X->p[i - 1] >>= v1;
1015 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001016 r0 = r1;
1017 }
1018 }
1019
1020 return( 0 );
1021}
1022
1023/*
1024 * Compare unsigned values
1025 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001026int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001027{
Paul Bakker23986e52011-04-24 08:57:21 +00001028 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001029 MPI_VALIDATE_RET( X != NULL );
1030 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001031
Paul Bakker23986e52011-04-24 08:57:21 +00001032 for( i = X->n; i > 0; i-- )
1033 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001034 break;
1035
Paul Bakker23986e52011-04-24 08:57:21 +00001036 for( j = Y->n; j > 0; j-- )
1037 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001038 break;
1039
Paul Bakker23986e52011-04-24 08:57:21 +00001040 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001041 return( 0 );
1042
1043 if( i > j ) return( 1 );
1044 if( j > i ) return( -1 );
1045
Paul Bakker23986e52011-04-24 08:57:21 +00001046 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001047 {
Paul Bakker23986e52011-04-24 08:57:21 +00001048 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
1049 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001050 }
1051
1052 return( 0 );
1053}
1054
1055/*
1056 * Compare signed values
1057 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001058int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001059{
Paul Bakker23986e52011-04-24 08:57:21 +00001060 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001061 MPI_VALIDATE_RET( X != NULL );
1062 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001063
Paul Bakker23986e52011-04-24 08:57:21 +00001064 for( i = X->n; i > 0; i-- )
1065 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001066 break;
1067
Paul Bakker23986e52011-04-24 08:57:21 +00001068 for( j = Y->n; j > 0; j-- )
1069 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001070 break;
1071
Paul Bakker23986e52011-04-24 08:57:21 +00001072 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001073 return( 0 );
1074
1075 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +00001076 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001077
1078 if( X->s > 0 && Y->s < 0 ) return( 1 );
1079 if( Y->s > 0 && X->s < 0 ) return( -1 );
1080
Paul Bakker23986e52011-04-24 08:57:21 +00001081 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001082 {
Paul Bakker23986e52011-04-24 08:57:21 +00001083 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
1084 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001085 }
1086
1087 return( 0 );
1088}
1089
Janos Follath45ec9902019-10-14 09:09:32 +01001090/** Decide if an integer is less than the other, without branches.
1091 *
1092 * \param x First integer.
1093 * \param y Second integer.
1094 *
1095 * \return 1 if \p x is less than \p y, 0 otherwise
1096 */
Janos Follath867a3ab2019-10-11 14:21:53 +01001097static unsigned ct_lt_mpi_uint( const mbedtls_mpi_uint x,
1098 const mbedtls_mpi_uint y )
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001099{
1100 mbedtls_mpi_uint ret;
1101 mbedtls_mpi_uint cond;
1102
1103 /*
1104 * Check if the most significant bits (MSB) of the operands are different.
1105 */
1106 cond = ( x ^ y );
1107 /*
1108 * If the MSB are the same then the difference x-y will be negative (and
1109 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
1110 */
1111 ret = ( x - y ) & ~cond;
1112 /*
1113 * If the MSB are different, then the operand with the MSB of 1 is the
1114 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
1115 * the MSB of y is 0.)
1116 */
1117 ret |= y & cond;
1118
1119
Janos Follath7a34bcf2019-10-14 08:59:14 +01001120 ret = ret >> ( biL - 1 );
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001121
Janos Follath359a01e2019-10-29 15:08:46 +00001122 return (unsigned) ret;
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001123}
1124
1125/*
1126 * Compare signed values in constant time
1127 */
Janos Follath867a3ab2019-10-11 14:21:53 +01001128int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
1129 unsigned *ret )
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001130{
1131 size_t i;
Janos Follathbd87a592019-10-28 12:23:18 +00001132 /* The value of any of these variables is either 0 or 1 at all times. */
Janos Follath1f21c1d2019-10-28 12:31:34 +00001133 unsigned cond, done, X_is_negative, Y_is_negative;
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001134
1135 MPI_VALIDATE_RET( X != NULL );
1136 MPI_VALIDATE_RET( Y != NULL );
1137 MPI_VALIDATE_RET( ret != NULL );
1138
1139 if( X->n != Y->n )
1140 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1141
1142 /*
Janos Follath58525182019-10-28 12:12:15 +00001143 * Set sign_N to 1 if N >= 0, 0 if N < 0.
1144 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001145 */
Janos Follath1f21c1d2019-10-28 12:31:34 +00001146 X_is_negative = ( X->s & 2 ) >> 1;
1147 Y_is_negative = ( Y->s & 2 ) >> 1;
Janos Follath867a3ab2019-10-11 14:21:53 +01001148
1149 /*
1150 * If the signs are different, then the positive operand is the bigger.
Janos Follath1f21c1d2019-10-28 12:31:34 +00001151 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
1152 * is false if X is positive (X_is_negative == 0).
Janos Follath867a3ab2019-10-11 14:21:53 +01001153 */
Janos Follath1f21c1d2019-10-28 12:31:34 +00001154 cond = ( X_is_negative ^ Y_is_negative );
1155 *ret = cond & X_is_negative;
Janos Follath867a3ab2019-10-11 14:21:53 +01001156
1157 /*
Janos Follathbd87a592019-10-28 12:23:18 +00001158 * This is a constant-time function. We might have the result, but we still
Janos Follath867a3ab2019-10-11 14:21:53 +01001159 * need to go through the loop. Record if we have the result already.
1160 */
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001161 done = cond;
1162
1163 for( i = X->n; i > 0; i-- )
1164 {
1165 /*
Janos Follathe25f1ee2019-11-05 12:24:52 +00001166 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
1167 * X and Y are negative.
Janos Follath867a3ab2019-10-11 14:21:53 +01001168 *
1169 * Again even if we can make a decision, we just mark the result and
1170 * the fact that we are done and continue looping.
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001171 */
Janos Follathe25f1ee2019-11-05 12:24:52 +00001172 cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] );
1173 *ret |= cond & ( 1 - done ) & X_is_negative;
Janos Follathfbe4c942019-10-28 12:37:21 +00001174 done |= cond;
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001175
1176 /*
Janos Follathe25f1ee2019-11-05 12:24:52 +00001177 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
1178 * X and Y are positive.
Janos Follath867a3ab2019-10-11 14:21:53 +01001179 *
1180 * Again even if we can make a decision, we just mark the result and
1181 * the fact that we are done and continue looping.
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001182 */
Janos Follathe25f1ee2019-11-05 12:24:52 +00001183 cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] );
1184 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
Janos Follathfbe4c942019-10-28 12:37:21 +00001185 done |= cond;
Janos Follathb9f6f9b2019-09-05 14:47:19 +01001186 }
1187
1188 return( 0 );
1189}
1190
Paul Bakker5121ce52009-01-03 21:22:43 +00001191/*
1192 * Compare signed values
1193 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001194int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +00001195{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001196 mbedtls_mpi Y;
1197 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001198 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001199
1200 *p = ( z < 0 ) ? -z : z;
1201 Y.s = ( z < 0 ) ? -1 : 1;
1202 Y.n = 1;
1203 Y.p = p;
1204
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001205 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001206}
1207
1208/*
1209 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1210 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001211int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001212{
Paul Bakker23986e52011-04-24 08:57:21 +00001213 int ret;
1214 size_t i, j;
Janos Follath6c922682015-10-30 17:43:11 +01001215 mbedtls_mpi_uint *o, *p, c, tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +00001216 MPI_VALIDATE_RET( X != NULL );
1217 MPI_VALIDATE_RET( A != NULL );
1218 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001219
1220 if( X == B )
1221 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001222 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +00001223 }
1224
1225 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001226 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +02001227
Paul Bakkerf7ca7b92009-06-20 10:31:06 +00001228 /*
1229 * X should always be positive as a result of unsigned additions.
1230 */
1231 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001232
Paul Bakker23986e52011-04-24 08:57:21 +00001233 for( j = B->n; j > 0; j-- )
1234 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001235 break;
1236
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001237 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001238
1239 o = B->p; p = X->p; c = 0;
1240
Janos Follath6c922682015-10-30 17:43:11 +01001241 /*
1242 * tmp is used because it might happen that p == o
1243 */
Paul Bakker23986e52011-04-24 08:57:21 +00001244 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001245 {
Janos Follath6c922682015-10-30 17:43:11 +01001246 tmp= *o;
Paul Bakker5121ce52009-01-03 21:22:43 +00001247 *p += c; c = ( *p < c );
Janos Follath6c922682015-10-30 17:43:11 +01001248 *p += tmp; c += ( *p < tmp );
Paul Bakker5121ce52009-01-03 21:22:43 +00001249 }
1250
1251 while( c != 0 )
1252 {
1253 if( i >= X->n )
1254 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001255 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001256 p = X->p + i;
1257 }
1258
Paul Bakker2d319fd2012-09-16 21:34:26 +00001259 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +00001260 }
1261
1262cleanup:
1263
1264 return( ret );
1265}
1266
1267/*
Gilles Peskine3ce3ddf2020-06-04 15:00:49 +02001268 * Helper for mbedtls_mpi subtraction:
1269 * d -= s where d and s have the same size and d >= s.
Paul Bakker5121ce52009-01-03 21:22:43 +00001270 */
Gilles Peskinee9073a62020-06-04 15:01:32 +02001271static void mpi_sub_hlp( size_t n,
1272 const mbedtls_mpi_uint *s,
1273 mbedtls_mpi_uint *d )
Paul Bakker5121ce52009-01-03 21:22:43 +00001274{
Paul Bakker23986e52011-04-24 08:57:21 +00001275 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001276 mbedtls_mpi_uint c, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001277
1278 for( i = c = 0; i < n; i++, s++, d++ )
1279 {
1280 z = ( *d < c ); *d -= c;
1281 c = ( *d < *s ) + z; *d -= *s;
1282 }
1283
1284 while( c != 0 )
1285 {
1286 z = ( *d < c ); *d -= c;
Alexey Skalozub8e75e682016-01-13 21:59:27 +02001287 c = z; d++;
Paul Bakker5121ce52009-01-03 21:22:43 +00001288 }
1289}
1290
1291/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001292 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
Paul Bakker5121ce52009-01-03 21:22:43 +00001293 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001294int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001295{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001296 mbedtls_mpi TB;
Paul Bakker23986e52011-04-24 08:57:21 +00001297 int ret;
1298 size_t n;
Hanno Becker73d7d792018-12-11 10:35:51 +00001299 MPI_VALIDATE_RET( X != NULL );
1300 MPI_VALIDATE_RET( A != NULL );
1301 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001302
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001303 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1304 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001305
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001306 mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001307
1308 if( X == B )
1309 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001310 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001311 B = &TB;
1312 }
1313
1314 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001315 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001316
Paul Bakker1ef7a532009-06-20 10:50:55 +00001317 /*
Paul Bakker60b1d102013-10-29 10:02:51 +01001318 * X should always be positive as a result of unsigned subtractions.
Paul Bakker1ef7a532009-06-20 10:50:55 +00001319 */
1320 X->s = 1;
1321
Paul Bakker5121ce52009-01-03 21:22:43 +00001322 ret = 0;
1323
Paul Bakker23986e52011-04-24 08:57:21 +00001324 for( n = B->n; n > 0; n-- )
1325 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001326 break;
1327
Paul Bakker23986e52011-04-24 08:57:21 +00001328 mpi_sub_hlp( n, B->p, X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +00001329
1330cleanup:
1331
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001332 mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001333
1334 return( ret );
1335}
1336
1337/*
1338 * Signed addition: X = A + B
1339 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001340int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001341{
Hanno Becker73d7d792018-12-11 10:35:51 +00001342 int ret, s;
1343 MPI_VALIDATE_RET( X != NULL );
1344 MPI_VALIDATE_RET( A != NULL );
1345 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001346
Hanno Becker73d7d792018-12-11 10:35:51 +00001347 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001348 if( A->s * B->s < 0 )
1349 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001350 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001351 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001352 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001353 X->s = s;
1354 }
1355 else
1356 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001357 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001358 X->s = -s;
1359 }
1360 }
1361 else
1362 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001363 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001364 X->s = s;
1365 }
1366
1367cleanup:
1368
1369 return( ret );
1370}
1371
1372/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001373 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001374 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001375int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001376{
Hanno Becker73d7d792018-12-11 10:35:51 +00001377 int ret, s;
1378 MPI_VALIDATE_RET( X != NULL );
1379 MPI_VALIDATE_RET( A != NULL );
1380 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001381
Hanno Becker73d7d792018-12-11 10:35:51 +00001382 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001383 if( A->s * B->s > 0 )
1384 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001385 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001386 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001387 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001388 X->s = s;
1389 }
1390 else
1391 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001392 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001393 X->s = -s;
1394 }
1395 }
1396 else
1397 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001398 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001399 X->s = s;
1400 }
1401
1402cleanup:
1403
1404 return( ret );
1405}
1406
1407/*
1408 * Signed addition: X = A + b
1409 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001410int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001411{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001412 mbedtls_mpi _B;
1413 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001414 MPI_VALIDATE_RET( X != NULL );
1415 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001416
1417 p[0] = ( b < 0 ) ? -b : b;
1418 _B.s = ( b < 0 ) ? -1 : 1;
1419 _B.n = 1;
1420 _B.p = p;
1421
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001422 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001423}
1424
1425/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001426 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001427 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001428int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001429{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001430 mbedtls_mpi _B;
1431 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001432 MPI_VALIDATE_RET( X != NULL );
1433 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001434
1435 p[0] = ( b < 0 ) ? -b : b;
1436 _B.s = ( b < 0 ) ? -1 : 1;
1437 _B.n = 1;
1438 _B.p = p;
1439
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001440 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001441}
1442
1443/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001444 * Helper for mbedtls_mpi multiplication
Paul Bakkerfc4f46f2013-06-24 19:23:56 +02001445 */
1446static
1447#if defined(__APPLE__) && defined(__arm__)
1448/*
1449 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1450 * appears to need this to prevent bad ARM code generation at -O3.
1451 */
1452__attribute__ ((noinline))
1453#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001454void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001455{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001456 mbedtls_mpi_uint c = 0, t = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001457
1458#if defined(MULADDC_HUIT)
1459 for( ; i >= 8; i -= 8 )
1460 {
1461 MULADDC_INIT
1462 MULADDC_HUIT
1463 MULADDC_STOP
1464 }
1465
1466 for( ; i > 0; i-- )
1467 {
1468 MULADDC_INIT
1469 MULADDC_CORE
1470 MULADDC_STOP
1471 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001472#else /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001473 for( ; i >= 16; i -= 16 )
1474 {
1475 MULADDC_INIT
1476 MULADDC_CORE MULADDC_CORE
1477 MULADDC_CORE MULADDC_CORE
1478 MULADDC_CORE MULADDC_CORE
1479 MULADDC_CORE MULADDC_CORE
1480
1481 MULADDC_CORE MULADDC_CORE
1482 MULADDC_CORE MULADDC_CORE
1483 MULADDC_CORE MULADDC_CORE
1484 MULADDC_CORE MULADDC_CORE
1485 MULADDC_STOP
1486 }
1487
1488 for( ; i >= 8; i -= 8 )
1489 {
1490 MULADDC_INIT
1491 MULADDC_CORE MULADDC_CORE
1492 MULADDC_CORE MULADDC_CORE
1493
1494 MULADDC_CORE MULADDC_CORE
1495 MULADDC_CORE MULADDC_CORE
1496 MULADDC_STOP
1497 }
1498
1499 for( ; i > 0; i-- )
1500 {
1501 MULADDC_INIT
1502 MULADDC_CORE
1503 MULADDC_STOP
1504 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001505#endif /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001506
1507 t++;
1508
1509 do {
1510 *d += c; c = ( *d < c ); d++;
1511 }
1512 while( c != 0 );
1513}
1514
1515/*
1516 * Baseline multiplication: X = A * B (HAC 14.12)
1517 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001518int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001519{
Paul Bakker23986e52011-04-24 08:57:21 +00001520 int ret;
1521 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001522 mbedtls_mpi TA, TB;
Hanno Becker73d7d792018-12-11 10:35:51 +00001523 MPI_VALIDATE_RET( X != NULL );
1524 MPI_VALIDATE_RET( A != NULL );
1525 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001526
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001527 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001528
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001529 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1530 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001531
Paul Bakker23986e52011-04-24 08:57:21 +00001532 for( i = A->n; i > 0; i-- )
1533 if( A->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001534 break;
1535
Paul Bakker23986e52011-04-24 08:57:21 +00001536 for( j = B->n; j > 0; j-- )
1537 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001538 break;
1539
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001540 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1541 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001542
Alexey Skalozub8e75e682016-01-13 21:59:27 +02001543 for( ; j > 0; j-- )
1544 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001545
1546 X->s = A->s * B->s;
1547
1548cleanup:
1549
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001550 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001551
1552 return( ret );
1553}
1554
1555/*
1556 * Baseline multiplication: X = A * b
1557 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001558int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001559{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001560 mbedtls_mpi _B;
1561 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001562 MPI_VALIDATE_RET( X != NULL );
1563 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001564
1565 _B.s = 1;
1566 _B.n = 1;
1567 _B.p = p;
1568 p[0] = b;
1569
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001570 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001571}
1572
1573/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001574 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1575 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001576 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001577static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1578 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001579{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001580#if defined(MBEDTLS_HAVE_UDBL)
1581 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001582#else
Simon Butcher9803d072016-01-03 00:24:34 +00001583 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1584 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001585 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1586 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001587 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001588#endif
1589
Simon Butcher15b15d12015-11-26 19:35:03 +00001590 /*
1591 * Check for overflow
1592 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001593 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001594 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001595 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001596
Simon Butcherf5ba0452015-12-27 23:01:55 +00001597 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001598 }
1599
1600#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001601 dividend = (mbedtls_t_udbl) u1 << biL;
1602 dividend |= (mbedtls_t_udbl) u0;
1603 quotient = dividend / d;
1604 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1605 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1606
1607 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001608 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001609
1610 return (mbedtls_mpi_uint) quotient;
1611#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001612
1613 /*
1614 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1615 * Vol. 2 - Seminumerical Algorithms, Knuth
1616 */
1617
1618 /*
1619 * Normalize the divisor, d, and dividend, u0, u1
1620 */
1621 s = mbedtls_clz( d );
1622 d = d << s;
1623
1624 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001625 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001626 u0 = u0 << s;
1627
1628 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001629 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001630
1631 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001632 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001633
1634 /*
1635 * Find the first quotient and remainder
1636 */
1637 q1 = u1 / d1;
1638 r0 = u1 - d1 * q1;
1639
1640 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1641 {
1642 q1 -= 1;
1643 r0 += d1;
1644
1645 if ( r0 >= radix ) break;
1646 }
1647
Simon Butcherf5ba0452015-12-27 23:01:55 +00001648 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001649 q0 = rAX / d1;
1650 r0 = rAX - q0 * d1;
1651
1652 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1653 {
1654 q0 -= 1;
1655 r0 += d1;
1656
1657 if ( r0 >= radix ) break;
1658 }
1659
1660 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001661 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001662
1663 quotient = q1 * radix + q0;
1664
1665 return quotient;
1666#endif
1667}
1668
1669/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001670 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001671 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001672int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1673 const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001674{
Paul Bakker23986e52011-04-24 08:57:21 +00001675 int ret;
1676 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001677 mbedtls_mpi X, Y, Z, T1, T2;
Hanno Becker73d7d792018-12-11 10:35:51 +00001678 MPI_VALIDATE_RET( A != NULL );
1679 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001680
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001681 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1682 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001683
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001684 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1685 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001686
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001687 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001688 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001689 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1690 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001691 return( 0 );
1692 }
1693
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001694 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1695 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001696 X.s = Y.s = 1;
1697
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001698 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1699 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1700 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1701 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001702
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001703 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001704 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001705 {
1706 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001707 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1708 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001709 }
1710 else k = 0;
1711
1712 n = X.n - 1;
1713 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001714 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001715
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001716 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001717 {
1718 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001719 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001720 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001721 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001722
1723 for( i = n; i > t ; i-- )
1724 {
1725 if( X.p[i] >= Y.p[t] )
1726 Z.p[i - t - 1] = ~0;
1727 else
1728 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001729 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1730 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001731 }
1732
1733 Z.p[i - t - 1]++;
1734 do
1735 {
1736 Z.p[i - t - 1]--;
1737
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001738 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001739 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001740 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001741 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001742
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001743 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001744 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1745 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001746 T2.p[2] = X.p[i];
1747 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001748 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001749
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001750 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1751 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1752 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001753
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001754 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001755 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001756 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1757 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1758 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001759 Z.p[i - t - 1]--;
1760 }
1761 }
1762
1763 if( Q != NULL )
1764 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001765 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001766 Q->s = A->s * B->s;
1767 }
1768
1769 if( R != NULL )
1770 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001771 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001772 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001773 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001774
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001775 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001776 R->s = 1;
1777 }
1778
1779cleanup:
1780
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001781 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1782 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001783
1784 return( ret );
1785}
1786
1787/*
1788 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001789 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001790int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1791 const mbedtls_mpi *A,
1792 mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001793{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001794 mbedtls_mpi _B;
1795 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001796 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001797
1798 p[0] = ( b < 0 ) ? -b : b;
1799 _B.s = ( b < 0 ) ? -1 : 1;
1800 _B.n = 1;
1801 _B.p = p;
1802
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001803 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001804}
1805
1806/*
1807 * Modulo: R = A mod B
1808 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001809int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001810{
1811 int ret;
Hanno Becker73d7d792018-12-11 10:35:51 +00001812 MPI_VALIDATE_RET( R != NULL );
1813 MPI_VALIDATE_RET( A != NULL );
1814 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001815
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001816 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1817 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001818
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001819 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001820
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001821 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1822 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001823
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001824 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1825 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001826
1827cleanup:
1828
1829 return( ret );
1830}
1831
1832/*
1833 * Modulo: r = A mod b
1834 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001835int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001836{
Paul Bakker23986e52011-04-24 08:57:21 +00001837 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001838 mbedtls_mpi_uint x, y, z;
Hanno Becker73d7d792018-12-11 10:35:51 +00001839 MPI_VALIDATE_RET( r != NULL );
1840 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001841
1842 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001843 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001844
1845 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001846 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001847
1848 /*
1849 * handle trivial cases
1850 */
1851 if( b == 1 )
1852 {
1853 *r = 0;
1854 return( 0 );
1855 }
1856
1857 if( b == 2 )
1858 {
1859 *r = A->p[0] & 1;
1860 return( 0 );
1861 }
1862
1863 /*
1864 * general case
1865 */
Paul Bakker23986e52011-04-24 08:57:21 +00001866 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001867 {
Paul Bakker23986e52011-04-24 08:57:21 +00001868 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001869 y = ( y << biH ) | ( x >> biH );
1870 z = y / b;
1871 y -= z * b;
1872
1873 x <<= biH;
1874 y = ( y << biH ) | ( x >> biH );
1875 z = y / b;
1876 y -= z * b;
1877 }
1878
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001879 /*
1880 * If A is negative, then the current y represents a negative value.
1881 * Flipping it to the positive side.
1882 */
1883 if( A->s < 0 && y != 0 )
1884 y = b - y;
1885
Paul Bakker5121ce52009-01-03 21:22:43 +00001886 *r = y;
1887
1888 return( 0 );
1889}
1890
1891/*
1892 * Fast Montgomery initialization (thanks to Tom St Denis)
1893 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001894static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001895{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001896 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001897 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00001898
1899 x = m0;
1900 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001901
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001902 for( i = biL; i >= 8; i /= 2 )
1903 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001904
1905 *mm = ~x + 1;
1906}
1907
Gilles Peskine3ce3ddf2020-06-04 15:00:49 +02001908/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1909 *
1910 * \param[in,out] A One of the numbers to multiply.
1911 * It must have at least one more limb than N
1912 * (A->n >= N->n + 1).
1913 * On successful completion, A contains the result of
1914 * the multiplication A * B * R^-1 mod N where
1915 * R = (2^ciL)^n.
1916 * \param[in] B One of the numbers to multiply.
1917 * It must be nonzero and must not have more limbs than N
1918 * (B->n <= N->n).
1919 * \param[in] N The modulo. N must be odd.
1920 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1921 * This is -N^-1 mod 2^ciL.
1922 * \param[in,out] T A bignum for temporary storage.
1923 * It must be at least twice the limb size of N plus 2
1924 * (T->n >= 2 * (N->n + 1)).
1925 * Its initial content is unused and
1926 * its final content is indeterminate.
1927 * Note that unlike the usual convention in the library
1928 * for `const mbedtls_mpi*`, the content of T can change.
Paul Bakker5121ce52009-01-03 21:22:43 +00001929 */
Gilles Peskinebdcb3962020-06-04 20:55:15 +02001930static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001931 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001932{
Paul Bakker23986e52011-04-24 08:57:21 +00001933 size_t i, n, m;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001934 mbedtls_mpi_uint u0, u1, *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00001935
1936 memset( T->p, 0, T->n * ciL );
1937
1938 d = T->p;
1939 n = N->n;
1940 m = ( B->n < n ) ? B->n : n;
1941
1942 for( i = 0; i < n; i++ )
1943 {
1944 /*
1945 * T = (T + u0*B + u1*N) / 2^biL
1946 */
1947 u0 = A->p[i];
1948 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1949
1950 mpi_mul_hlp( m, B->p, d, u0 );
1951 mpi_mul_hlp( n, N->p, d, u1 );
1952
1953 *d++ = u0; d[n + 1] = 0;
1954 }
1955
Paul Bakker66d5d072014-06-17 16:39:18 +02001956 memcpy( A->p, d, ( n + 1 ) * ciL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001957
Gilles Peskine3ce3ddf2020-06-04 15:00:49 +02001958 /* If A >= N then A -= N. Do the subtraction unconditionally to prevent
1959 * timing attacks. Modify T as a side effect. */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001960 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001961 mpi_sub_hlp( n, N->p, A->p );
1962 else
1963 /* prevent timing attacks */
1964 mpi_sub_hlp( n, A->p, T->p );
1965}
1966
1967/*
1968 * Montgomery reduction: A = A * R^-1 mod N
Gilles Peskine3ce3ddf2020-06-04 15:00:49 +02001969 *
1970 * See mpi_montmul() regarding constraints and guarantees on the parameters.
Paul Bakker5121ce52009-01-03 21:22:43 +00001971 */
Gilles Peskinebdcb3962020-06-04 20:55:15 +02001972static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
1973 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001974{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001975 mbedtls_mpi_uint z = 1;
1976 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001977
Paul Bakker8ddb6452013-02-27 14:56:33 +01001978 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001979 U.p = &z;
1980
Gilles Peskinebdcb3962020-06-04 20:55:15 +02001981 mpi_montmul( A, &U, N, mm, T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001982}
1983
1984/*
1985 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1986 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001987int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
1988 const mbedtls_mpi *E, const mbedtls_mpi *N,
1989 mbedtls_mpi *_RR )
Paul Bakker5121ce52009-01-03 21:22:43 +00001990{
Paul Bakker23986e52011-04-24 08:57:21 +00001991 int ret;
1992 size_t wbits, wsize, one = 1;
1993 size_t i, j, nblimbs;
1994 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001995 mbedtls_mpi_uint ei, mm, state;
1996 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00001997 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001998
Hanno Becker73d7d792018-12-11 10:35:51 +00001999 MPI_VALIDATE_RET( X != NULL );
2000 MPI_VALIDATE_RET( A != NULL );
2001 MPI_VALIDATE_RET( E != NULL );
2002 MPI_VALIDATE_RET( N != NULL );
2003
Hanno Becker8d1dd1b2017-09-28 11:02:24 +01002004 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002005 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002006
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002007 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
2008 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002009
2010 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00002011 * Init temps and window size
2012 */
2013 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002014 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
2015 mbedtls_mpi_init( &Apos );
Paul Bakker5121ce52009-01-03 21:22:43 +00002016 memset( W, 0, sizeof( W ) );
2017
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002018 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00002019
2020 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2021 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2022
Peter Kolbusb83d41d2018-12-11 14:01:44 -06002023#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002024 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2025 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Peter Kolbusb83d41d2018-12-11 14:01:44 -06002026#endif
Paul Bakkerb6d5f082011-11-25 11:52:11 +00002027
Paul Bakker5121ce52009-01-03 21:22:43 +00002028 j = N->n + 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002029 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2030 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2031 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002032
2033 /*
Paul Bakker50546922012-05-19 08:40:49 +00002034 * Compensate for negative A (and correct at the end)
2035 */
2036 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00002037 if( neg )
2038 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002039 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00002040 Apos.s = 1;
2041 A = &Apos;
2042 }
2043
2044 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00002045 * If 1st call, pre-compute R^2 mod N
2046 */
2047 if( _RR == NULL || _RR->p == NULL )
2048 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002049 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2050 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2051 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002052
2053 if( _RR != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002054 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002055 }
2056 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002057 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002058
2059 /*
2060 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2061 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002062 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
2063 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Paul Bakkerc2024f42014-01-23 20:38:35 +01002064 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002065 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002066
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002067 mpi_montmul( &W[1], &RR, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002068
2069 /*
2070 * X = R^2 * R^-1 mod N = R mod N
2071 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002072 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002073 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002074
2075 if( wsize > 1 )
2076 {
2077 /*
2078 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2079 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002080 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002081
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002082 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2083 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002084
2085 for( i = 0; i < wsize - 1; i++ )
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002086 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01002087
Paul Bakker5121ce52009-01-03 21:22:43 +00002088 /*
2089 * W[i] = W[i - 1] * W[1]
2090 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002091 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002092 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002093 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2094 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002095
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002096 mpi_montmul( &W[i], &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002097 }
2098 }
2099
2100 nblimbs = E->n;
2101 bufsize = 0;
2102 nbits = 0;
2103 wbits = 0;
2104 state = 0;
2105
2106 while( 1 )
2107 {
2108 if( bufsize == 0 )
2109 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01002110 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002111 break;
2112
Paul Bakker0d7702c2013-10-29 16:18:35 +01002113 nblimbs--;
2114
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002115 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00002116 }
2117
2118 bufsize--;
2119
2120 ei = (E->p[nblimbs] >> bufsize) & 1;
2121
2122 /*
2123 * skip leading 0s
2124 */
2125 if( ei == 0 && state == 0 )
2126 continue;
2127
2128 if( ei == 0 && state == 1 )
2129 {
2130 /*
2131 * out of window, square X
2132 */
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002133 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002134 continue;
2135 }
2136
2137 /*
2138 * add ei to current window
2139 */
2140 state = 2;
2141
2142 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02002143 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002144
2145 if( nbits == wsize )
2146 {
2147 /*
2148 * X = X^wsize R^-1 mod N
2149 */
2150 for( i = 0; i < wsize; i++ )
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002151 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002152
2153 /*
2154 * X = X * W[wbits] R^-1 mod N
2155 */
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002156 mpi_montmul( X, &W[wbits], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002157
2158 state--;
2159 nbits = 0;
2160 wbits = 0;
2161 }
2162 }
2163
2164 /*
2165 * process the remaining bits
2166 */
2167 for( i = 0; i < nbits; i++ )
2168 {
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002169 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002170
2171 wbits <<= 1;
2172
Paul Bakker66d5d072014-06-17 16:39:18 +02002173 if( ( wbits & ( one << wsize ) ) != 0 )
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002174 mpi_montmul( X, &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002175 }
2176
2177 /*
2178 * X = A^E * R * R^-1 mod N = A^E mod N
2179 */
Gilles Peskinebdcb3962020-06-04 20:55:15 +02002180 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002181
Hanno Beckera4af1c42017-04-18 09:07:45 +01002182 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00002183 {
2184 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002185 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002186 }
2187
Paul Bakker5121ce52009-01-03 21:22:43 +00002188cleanup:
2189
Paul Bakker66d5d072014-06-17 16:39:18 +02002190 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002191 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00002192
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002193 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Paul Bakker6c591fa2011-05-05 11:49:20 +00002194
Paul Bakker75a28602014-03-31 12:08:17 +02002195 if( _RR == NULL || _RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002196 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002197
2198 return( ret );
2199}
2200
Paul Bakker5121ce52009-01-03 21:22:43 +00002201/*
2202 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2203 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002204int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00002205{
Paul Bakker23986e52011-04-24 08:57:21 +00002206 int ret;
2207 size_t lz, lzt;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002208 mbedtls_mpi TG, TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00002209
Hanno Becker73d7d792018-12-11 10:35:51 +00002210 MPI_VALIDATE_RET( G != NULL );
2211 MPI_VALIDATE_RET( A != NULL );
2212 MPI_VALIDATE_RET( B != NULL );
2213
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002214 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002215
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002216 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2217 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002218
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002219 lz = mbedtls_mpi_lsb( &TA );
2220 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002221
Paul Bakker66d5d072014-06-17 16:39:18 +02002222 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002223 lz = lzt;
2224
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002225 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
2226 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002227
Paul Bakker5121ce52009-01-03 21:22:43 +00002228 TA.s = TB.s = 1;
2229
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002230 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002231 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002232 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2233 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002234
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002235 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002236 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002237 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2238 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002239 }
2240 else
2241 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002242 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2243 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002244 }
2245 }
2246
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002247 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2248 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002249
2250cleanup:
2251
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002252 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002253
2254 return( ret );
2255}
2256
Paul Bakker33dc46b2014-04-30 16:11:39 +02002257/*
2258 * Fill X with size bytes of random.
2259 *
2260 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02002261 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02002262 * deterministic, eg for tests).
2263 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002264int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002265 int (*f_rng)(void *, unsigned char *, size_t),
2266 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00002267{
Paul Bakker23986e52011-04-24 08:57:21 +00002268 int ret;
Hanno Becker6dab6202019-01-02 16:42:29 +00002269 size_t const limbs = CHARS_TO_LIMBS( size );
Hanno Beckerda1655a2017-10-18 14:21:44 +01002270 size_t const overhead = ( limbs * ciL ) - size;
2271 unsigned char *Xp;
2272
Hanno Becker8ce11a32018-12-19 16:18:52 +00002273 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002274 MPI_VALIDATE_RET( f_rng != NULL );
Paul Bakker33dc46b2014-04-30 16:11:39 +02002275
Hanno Beckerda1655a2017-10-18 14:21:44 +01002276 /* Ensure that target MPI has exactly the necessary number of limbs */
2277 if( X->n != limbs )
2278 {
2279 mbedtls_mpi_free( X );
2280 mbedtls_mpi_init( X );
2281 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
2282 }
2283 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker287781a2011-03-26 13:18:49 +00002284
Hanno Beckerda1655a2017-10-18 14:21:44 +01002285 Xp = (unsigned char*) X->p;
2286 f_rng( p_rng, Xp + overhead, size );
2287
Hanno Becker2be8a552018-10-25 12:40:09 +01002288 mpi_bigendian_to_host( X->p, limbs );
Paul Bakker287781a2011-03-26 13:18:49 +00002289
2290cleanup:
2291 return( ret );
2292}
2293
Paul Bakker5121ce52009-01-03 21:22:43 +00002294/*
2295 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2296 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002297int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00002298{
2299 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002300 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Hanno Becker73d7d792018-12-11 10:35:51 +00002301 MPI_VALIDATE_RET( X != NULL );
2302 MPI_VALIDATE_RET( A != NULL );
2303 MPI_VALIDATE_RET( N != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00002304
Hanno Becker4bcb4912017-04-18 15:49:39 +01002305 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002306 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002307
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002308 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2309 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2310 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002311
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002312 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002313
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002314 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002315 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002316 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002317 goto cleanup;
2318 }
2319
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002320 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2321 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2322 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2323 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002324
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002325 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2326 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2327 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2328 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002329
2330 do
2331 {
2332 while( ( TU.p[0] & 1 ) == 0 )
2333 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002334 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002335
2336 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2337 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002338 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2339 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002340 }
2341
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002342 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2343 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002344 }
2345
2346 while( ( TV.p[0] & 1 ) == 0 )
2347 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002348 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002349
2350 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2351 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002352 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2353 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002354 }
2355
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002356 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2357 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002358 }
2359
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002360 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002361 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002362 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2363 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2364 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002365 }
2366 else
2367 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002368 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2369 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2370 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002371 }
2372 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002373 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002374
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002375 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2376 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002377
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002378 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2379 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002380
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002381 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002382
2383cleanup:
2384
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002385 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2386 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2387 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002388
2389 return( ret );
2390}
2391
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002392#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00002393
Paul Bakker5121ce52009-01-03 21:22:43 +00002394static const int small_prime[] =
2395{
2396 3, 5, 7, 11, 13, 17, 19, 23,
2397 29, 31, 37, 41, 43, 47, 53, 59,
2398 61, 67, 71, 73, 79, 83, 89, 97,
2399 101, 103, 107, 109, 113, 127, 131, 137,
2400 139, 149, 151, 157, 163, 167, 173, 179,
2401 181, 191, 193, 197, 199, 211, 223, 227,
2402 229, 233, 239, 241, 251, 257, 263, 269,
2403 271, 277, 281, 283, 293, 307, 311, 313,
2404 317, 331, 337, 347, 349, 353, 359, 367,
2405 373, 379, 383, 389, 397, 401, 409, 419,
2406 421, 431, 433, 439, 443, 449, 457, 461,
2407 463, 467, 479, 487, 491, 499, 503, 509,
2408 521, 523, 541, 547, 557, 563, 569, 571,
2409 577, 587, 593, 599, 601, 607, 613, 617,
2410 619, 631, 641, 643, 647, 653, 659, 661,
2411 673, 677, 683, 691, 701, 709, 719, 727,
2412 733, 739, 743, 751, 757, 761, 769, 773,
2413 787, 797, 809, 811, 821, 823, 827, 829,
2414 839, 853, 857, 859, 863, 877, 881, 883,
2415 887, 907, 911, 919, 929, 937, 941, 947,
2416 953, 967, 971, 977, 983, 991, 997, -103
2417};
2418
2419/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002420 * Small divisors test (X must be positive)
2421 *
2422 * Return values:
2423 * 0: no small factor (possible prime, more tests needed)
2424 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002425 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002426 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002427 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002428static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002429{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002430 int ret = 0;
2431 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002432 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002433
Paul Bakker5121ce52009-01-03 21:22:43 +00002434 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002435 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002436
2437 for( i = 0; small_prime[i] > 0; i++ )
2438 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002439 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002440 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002441
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002442 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002443
2444 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002445 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002446 }
2447
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002448cleanup:
2449 return( ret );
2450}
2451
2452/*
2453 * Miller-Rabin pseudo-primality test (HAC 4.24)
2454 */
Janos Follathda31fa12018-09-03 14:45:23 +01002455static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002456 int (*f_rng)(void *, unsigned char *, size_t),
2457 void *p_rng )
2458{
Pascal Junodb99183d2015-03-11 16:49:45 +01002459 int ret, count;
Janos Follathda31fa12018-09-03 14:45:23 +01002460 size_t i, j, k, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002461 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002462
Hanno Becker8ce11a32018-12-19 16:18:52 +00002463 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002464 MPI_VALIDATE_RET( f_rng != NULL );
2465
2466 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2467 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002468 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002469
Paul Bakker5121ce52009-01-03 21:22:43 +00002470 /*
2471 * W = |X| - 1
2472 * R = W >> lsb( W )
2473 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002474 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2475 s = mbedtls_mpi_lsb( &W );
2476 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2477 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002478
Janos Follathda31fa12018-09-03 14:45:23 +01002479 for( i = 0; i < rounds; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002480 {
2481 /*
2482 * pick a random A, 1 < A < |X| - 1
2483 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002484 count = 0;
2485 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002486 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002487
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002488 j = mbedtls_mpi_bitlen( &A );
2489 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002490 if (j > k) {
Darryl Greene3f95ed2018-10-02 13:21:35 +01002491 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Pascal Junodb99183d2015-03-11 16:49:45 +01002492 }
2493
2494 if (count++ > 30) {
Jens Wiklanderdfd447e2019-01-17 13:30:57 +01002495 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2496 goto cleanup;
Pascal Junodb99183d2015-03-11 16:49:45 +01002497 }
2498
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002499 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2500 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002501
2502 /*
2503 * A = A^R mod |X|
2504 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002505 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002506
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002507 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2508 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002509 continue;
2510
2511 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002512 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002513 {
2514 /*
2515 * A = A * A mod |X|
2516 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002517 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2518 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002519
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002520 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002521 break;
2522
2523 j++;
2524 }
2525
2526 /*
2527 * not prime if A != |X| - 1 or A == 1
2528 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002529 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2530 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002531 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002532 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002533 break;
2534 }
2535 }
2536
2537cleanup:
Hanno Becker73d7d792018-12-11 10:35:51 +00002538 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2539 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002540 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002541
2542 return( ret );
2543}
2544
2545/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002546 * Pseudo-primality test: small factors, then Miller-Rabin
2547 */
Janos Follatha0b67c22018-09-18 14:48:23 +01002548int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2549 int (*f_rng)(void *, unsigned char *, size_t),
2550 void *p_rng )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002551{
2552 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002553 mbedtls_mpi XX;
Hanno Becker8ce11a32018-12-19 16:18:52 +00002554 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002555 MPI_VALIDATE_RET( f_rng != NULL );
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002556
2557 XX.s = 1;
2558 XX.n = X->n;
2559 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002560
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002561 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2562 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2563 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002564
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002565 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002566 return( 0 );
2567
2568 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2569 {
2570 if( ret == 1 )
2571 return( 0 );
2572
2573 return( ret );
2574 }
2575
Janos Follathda31fa12018-09-03 14:45:23 +01002576 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
Janos Follathf301d232018-08-14 13:34:01 +01002577}
2578
Janos Follatha0b67c22018-09-18 14:48:23 +01002579#if !defined(MBEDTLS_DEPRECATED_REMOVED)
Janos Follathf301d232018-08-14 13:34:01 +01002580/*
2581 * Pseudo-primality test, error probability 2^-80
2582 */
2583int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2584 int (*f_rng)(void *, unsigned char *, size_t),
2585 void *p_rng )
2586{
Hanno Becker8ce11a32018-12-19 16:18:52 +00002587 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002588 MPI_VALIDATE_RET( f_rng != NULL );
2589
Janos Follatha0b67c22018-09-18 14:48:23 +01002590 /*
2591 * In the past our key generation aimed for an error rate of at most
2592 * 2^-80. Since this function is deprecated, aim for the same certainty
2593 * here as well.
2594 */
Hanno Becker73d7d792018-12-11 10:35:51 +00002595 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002596}
Janos Follatha0b67c22018-09-18 14:48:23 +01002597#endif
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002598
2599/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002600 * Prime number generation
Jethro Beekman66689272018-02-14 19:24:10 -08002601 *
Janos Follathf301d232018-08-14 13:34:01 +01002602 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2603 * be either 1024 bits or 1536 bits long, and flags must contain
2604 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Paul Bakker5121ce52009-01-03 21:22:43 +00002605 */
Janos Follath7c025a92018-08-14 11:08:41 +01002606int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002607 int (*f_rng)(void *, unsigned char *, size_t),
2608 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002609{
Jethro Beekman66689272018-02-14 19:24:10 -08002610#ifdef MBEDTLS_HAVE_INT64
2611// ceil(2^63.5)
2612#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2613#else
2614// ceil(2^31.5)
2615#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2616#endif
2617 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker23986e52011-04-24 08:57:21 +00002618 size_t k, n;
Janos Follathda31fa12018-09-03 14:45:23 +01002619 int rounds;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002620 mbedtls_mpi_uint r;
2621 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002622
Hanno Becker8ce11a32018-12-19 16:18:52 +00002623 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002624 MPI_VALIDATE_RET( f_rng != NULL );
2625
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002626 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2627 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002628
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002629 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002630
2631 n = BITS_TO_LIMBS( nbits );
2632
Janos Follathda31fa12018-09-03 14:45:23 +01002633 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2634 {
2635 /*
2636 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2637 */
2638 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2639 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2640 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2641 }
2642 else
2643 {
2644 /*
2645 * 2^-100 error probability, number of rounds computed based on HAC,
2646 * fact 4.48
2647 */
2648 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2649 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2650 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2651 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2652 }
2653
Jethro Beekman66689272018-02-14 19:24:10 -08002654 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002655 {
Jethro Beekman66689272018-02-14 19:24:10 -08002656 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2657 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2658 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2659
2660 k = n * biL;
2661 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2662 X->p[0] |= 1;
2663
Janos Follath7c025a92018-08-14 11:08:41 +01002664 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002665 {
Janos Follatha0b67c22018-09-18 14:48:23 +01002666 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
Jethro Beekman66689272018-02-14 19:24:10 -08002667
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002668 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002669 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002670 }
Jethro Beekman66689272018-02-14 19:24:10 -08002671 else
Paul Bakker5121ce52009-01-03 21:22:43 +00002672 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002673 /*
Jethro Beekman66689272018-02-14 19:24:10 -08002674 * An necessary condition for Y and X = 2Y + 1 to be prime
2675 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2676 * Make sure it is satisfied, while keeping X = 3 mod 4
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002677 */
Jethro Beekman66689272018-02-14 19:24:10 -08002678
2679 X->p[0] |= 2;
2680
2681 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2682 if( r == 0 )
2683 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2684 else if( r == 1 )
2685 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2686
2687 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2688 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2689 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2690
2691 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002692 {
Jethro Beekman66689272018-02-14 19:24:10 -08002693 /*
2694 * First, check small factors for X and Y
2695 * before doing Miller-Rabin on any of them
2696 */
2697 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2698 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002699 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002700 == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002701 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002702 == 0 )
Jethro Beekman66689272018-02-14 19:24:10 -08002703 goto cleanup;
2704
2705 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2706 goto cleanup;
2707
2708 /*
2709 * Next candidates. We want to preserve Y = (X-1) / 2 and
2710 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2711 * so up Y by 6 and X by 12.
2712 */
2713 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2714 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002715 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002716 }
2717 }
2718
2719cleanup:
2720
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002721 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002722
2723 return( ret );
2724}
2725
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002726#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002727
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002728#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002729
Paul Bakker23986e52011-04-24 08:57:21 +00002730#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002731
2732static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2733{
2734 { 693, 609, 21 },
2735 { 1764, 868, 28 },
2736 { 768454923, 542167814, 1 }
2737};
2738
Paul Bakker5121ce52009-01-03 21:22:43 +00002739/*
2740 * Checkup routine
2741 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002742int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002743{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002744 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002745 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002746
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002747 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2748 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002749
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002750 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002751 "EFE021C2645FD1DC586E69184AF4A31E" \
2752 "D5F53E93B5F123FA41680867BA110131" \
2753 "944FE7952E2517337780CB0DB80E61AA" \
2754 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2755
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002756 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002757 "B2E7EFD37075B9F03FF989C7C5051C20" \
2758 "34D2A323810251127E7BF8625A4F49A5" \
2759 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2760 "5B5C25763222FEFCCFC38B832366C29E" ) );
2761
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002762 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002763 "0066A198186C18C10B2F5ED9B522752A" \
2764 "9830B69916E535C8F047518A889A43A5" \
2765 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2766
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002767 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002768
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002769 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002770 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2771 "9E857EA95A03512E2BAE7391688D264A" \
2772 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2773 "8001B72E848A38CAE1C65F78E56ABDEF" \
2774 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2775 "ECF677152EF804370C1A305CAF3B5BF1" \
2776 "30879B56C61DE584A0F53A2447A51E" ) );
2777
2778 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002779 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002780
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002781 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002782 {
2783 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002784 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002785
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002786 ret = 1;
2787 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002788 }
2789
2790 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002791 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002792
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002793 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002794
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002795 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002796 "256567336059E52CAE22925474705F39A94" ) );
2797
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002798 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002799 "6613F26162223DF488E9CD48CC132C7A" \
2800 "0AC93C701B001B092E4E5B9F73BCD27B" \
2801 "9EE50D0657C77F374E903CDFA4C642" ) );
2802
2803 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002804 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002805
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002806 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2807 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002808 {
2809 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002810 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002811
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002812 ret = 1;
2813 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002814 }
2815
2816 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002817 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002818
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002819 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002820
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002821 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002822 "36E139AEA55215609D2816998ED020BB" \
2823 "BD96C37890F65171D948E9BC7CBAA4D9" \
2824 "325D24D6A3C12710F10A09FA08AB87" ) );
2825
2826 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002827 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002828
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002829 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002830 {
2831 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002832 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002833
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002834 ret = 1;
2835 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002836 }
2837
2838 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002839 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002840
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002841 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002842
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002843 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002844 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2845 "C3DBA76456363A10869622EAC2DD84EC" \
2846 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2847
2848 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002849 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002850
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002851 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002852 {
2853 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002854 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002855
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002856 ret = 1;
2857 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002858 }
2859
2860 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002861 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002862
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002863 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002864 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002865
Paul Bakker66d5d072014-06-17 16:39:18 +02002866 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002867 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002868 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2869 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002870
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002871 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002872
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002873 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002874 {
2875 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002876 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002877
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002878 ret = 1;
2879 goto cleanup;
2880 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002881 }
2882
2883 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002884 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002885
Paul Bakker5121ce52009-01-03 21:22:43 +00002886cleanup:
2887
2888 if( ret != 0 && verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002889 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002890
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002891 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2892 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002893
2894 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002895 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002896
2897 return( ret );
2898}
2899
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002900#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002901
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002902#endif /* MBEDTLS_BIGNUM_C */