blob: ba0398825425f2f7c5953c449c319b0750ce2e3f [file] [log] [blame]
Paul Bakker5121ce52009-01-03 21:22:43 +00001/*
2 * Multi-precision integer library
3 *
Bence Szépkúti1e148272020-08-07 13:07:28 +02004 * Copyright The Mbed TLS Contributors
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 Bakker5121ce52009-01-03 21:22:43 +000018 */
Simon Butcher15b15d12015-11-26 19:35:03 +000019
Paul Bakker5121ce52009-01-03 21:22:43 +000020/*
Simon Butcher15b15d12015-11-26 19:35:03 +000021 * The following sources were referenced in the design of this Multi-precision
22 * Integer library:
Paul Bakker5121ce52009-01-03 21:22:43 +000023 *
Simon Butcher15b15d12015-11-26 19:35:03 +000024 * [1] Handbook of Applied Cryptography - 1997
25 * Menezes, van Oorschot and Vanstone
26 *
27 * [2] Multi-Precision Math
28 * Tom St Denis
29 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
30 *
31 * [3] GNU Multi-Precision Arithmetic Library
32 * https://gmplib.org/manual/index.html
33 *
Simon Butcherf5ba0452015-12-27 23:01:55 +000034 */
Paul Bakker5121ce52009-01-03 21:22:43 +000035
Gilles Peskinedb09ef62020-06-03 01:43:33 +020036#include "common.h"
Paul Bakker5121ce52009-01-03 21:22:43 +000037
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020038#if defined(MBEDTLS_BIGNUM_C)
Paul Bakker5121ce52009-01-03 21:22:43 +000039
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000040#include "mbedtls/bignum.h"
Janos Follath4614b9a2022-07-21 15:34:47 +010041#include "bignum_core.h"
Chris Jones4c5819c2021-03-03 17:45:34 +000042#include "bn_mul.h"
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050043#include "mbedtls/platform_util.h"
Janos Follath24eed8d2019-11-22 13:21:35 +000044#include "mbedtls/error.h"
Gabor Mezei22c9a6f2021-10-20 12:09:35 +020045#include "constant_time_internal.h"
Paul Bakker5121ce52009-01-03 21:22:43 +000046
Dave Rodgman351c71b2021-12-06 17:50:53 +000047#include <limits.h>
Rich Evans00ab4702015-02-06 13:43:58 +000048#include <string.h>
49
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000050#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020051
Gabor Mezei66669142022-08-03 12:52:26 +020052#define MPI_VALIDATE_RET( cond ) \
53 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
54#define MPI_VALIDATE( cond ) \
55 MBEDTLS_INTERNAL_VALIDATE( cond )
56
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +010057#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
58
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050059/* Implementation that should never be optimized out by the compiler */
Andres Amaya Garcia6698d2f2018-04-24 08:39:07 -050060static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
61{
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050062 mbedtls_platform_zeroize( v, ciL * n );
63}
64
Paul Bakker5121ce52009-01-03 21:22:43 +000065/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000066 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000067 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020068void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000069{
Hanno Becker73d7d792018-12-11 10:35:51 +000070 MPI_VALIDATE( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +000071
Paul Bakker6c591fa2011-05-05 11:49:20 +000072 X->s = 1;
73 X->n = 0;
74 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +000075}
76
77/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000078 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000079 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020080void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000081{
Paul Bakker6c591fa2011-05-05 11:49:20 +000082 if( X == NULL )
83 return;
Paul Bakker5121ce52009-01-03 21:22:43 +000084
Paul Bakker6c591fa2011-05-05 11:49:20 +000085 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +000086 {
Alexey Skalozube17a8da2016-01-13 17:19:33 +020087 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020088 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +000089 }
90
Paul Bakker6c591fa2011-05-05 11:49:20 +000091 X->s = 1;
92 X->n = 0;
93 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +000094}
95
96/*
97 * Enlarge to the specified number of limbs
98 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020099int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000100{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200101 mbedtls_mpi_uint *p;
Hanno Becker73d7d792018-12-11 10:35:51 +0000102 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000103
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200104 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200105 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000106
Paul Bakker5121ce52009-01-03 21:22:43 +0000107 if( X->n < nblimbs )
108 {
Simon Butcher29176892016-05-20 00:19:09 +0100109 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200110 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000111
Paul Bakker5121ce52009-01-03 21:22:43 +0000112 if( X->p != NULL )
113 {
114 memcpy( p, X->p, X->n * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200115 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200116 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000117 }
118
119 X->n = nblimbs;
120 X->p = p;
121 }
122
123 return( 0 );
124}
125
126/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100127 * Resize down as much as possible,
128 * while keeping at least the specified number of limbs
129 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200130int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100131{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200132 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100133 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000134 MPI_VALIDATE_RET( X != NULL );
135
136 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
137 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100138
Gilles Peskinee2f563e2020-01-20 21:17:43 +0100139 /* Actually resize up if there are currently fewer than nblimbs limbs. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100140 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200141 return( mbedtls_mpi_grow( X, nblimbs ) );
Gilles Peskine322752b2020-01-21 13:59:51 +0100142 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100143
144 for( i = X->n - 1; i > 0; i-- )
145 if( X->p[i] != 0 )
146 break;
147 i++;
148
149 if( i < nblimbs )
150 i = nblimbs;
151
Simon Butcher29176892016-05-20 00:19:09 +0100152 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200153 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100154
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100155 if( X->p != NULL )
156 {
157 memcpy( p, X->p, i * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200158 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200159 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100160 }
161
162 X->n = i;
163 X->p = p;
164
165 return( 0 );
166}
167
Gilles Peskineed32b572021-06-02 22:17:52 +0200168/* Resize X to have exactly n limbs and set it to 0. */
169static int mbedtls_mpi_resize_clear( mbedtls_mpi *X, size_t limbs )
170{
171 if( limbs == 0 )
172 {
173 mbedtls_mpi_free( X );
174 return( 0 );
175 }
176 else if( X->n == limbs )
177 {
178 memset( X->p, 0, limbs * ciL );
179 X->s = 1;
180 return( 0 );
181 }
182 else
183 {
184 mbedtls_mpi_free( X );
185 return( mbedtls_mpi_grow( X, limbs ) );
186 }
187}
188
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100189/*
Gilles Peskine3da1a8f2021-06-08 23:17:42 +0200190 * Copy the contents of Y into X.
191 *
192 * This function is not constant-time. Leading zeros in Y may be removed.
193 *
194 * Ensure that X does not shrink. This is not guaranteed by the public API,
195 * but some code in the bignum module relies on this property, for example
196 * in mbedtls_mpi_exp_mod().
Paul Bakker5121ce52009-01-03 21:22:43 +0000197 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200198int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000199{
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100200 int ret = 0;
Paul Bakker23986e52011-04-24 08:57:21 +0000201 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000202 MPI_VALIDATE_RET( X != NULL );
203 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000204
205 if( X == Y )
206 return( 0 );
207
Gilles Peskinedb420622020-01-20 21:12:50 +0100208 if( Y->n == 0 )
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200209 {
Gilles Peskine3da1a8f2021-06-08 23:17:42 +0200210 if( X->n != 0 )
211 {
212 X->s = 1;
213 memset( X->p, 0, X->n * ciL );
214 }
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200215 return( 0 );
216 }
217
Paul Bakker5121ce52009-01-03 21:22:43 +0000218 for( i = Y->n - 1; i > 0; i-- )
219 if( Y->p[i] != 0 )
220 break;
221 i++;
222
223 X->s = Y->s;
224
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100225 if( X->n < i )
226 {
227 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
228 }
229 else
230 {
231 memset( X->p + i, 0, ( X->n - i ) * ciL );
232 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000233
Paul Bakker5121ce52009-01-03 21:22:43 +0000234 memcpy( X->p, Y->p, i * ciL );
235
236cleanup:
237
238 return( ret );
239}
240
241/*
242 * Swap the contents of X and Y
243 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200244void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000245{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200246 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000247 MPI_VALIDATE( X != NULL );
248 MPI_VALIDATE( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000249
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200250 memcpy( &T, X, sizeof( mbedtls_mpi ) );
251 memcpy( X, Y, sizeof( mbedtls_mpi ) );
252 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000253}
254
Gilles Peskineef7f4e42022-11-15 23:25:27 +0100255static inline mbedtls_mpi_uint mpi_sint_abs( mbedtls_mpi_sint z )
256{
257 if( z >= 0 )
258 return( z );
259 /* Take care to handle the most negative value (-2^(biL-1)) correctly.
260 * A naive -z would have undefined behavior.
261 * Write this in a way that makes popular compilers happy (GCC, Clang,
262 * MSVC). */
263 return( (mbedtls_mpi_uint) 0 - (mbedtls_mpi_uint) z );
264}
265
Paul Bakker5121ce52009-01-03 21:22:43 +0000266/*
267 * Set value from integer
268 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200269int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000270{
Janos Follath24eed8d2019-11-22 13:21:35 +0000271 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +0000272 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000273
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200274 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000275 memset( X->p, 0, X->n * ciL );
276
Gilles Peskineef7f4e42022-11-15 23:25:27 +0100277 X->p[0] = mpi_sint_abs( z );
Paul Bakker5121ce52009-01-03 21:22:43 +0000278 X->s = ( z < 0 ) ? -1 : 1;
279
280cleanup:
281
282 return( ret );
283}
284
285/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000286 * Get a specific bit
287 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200288int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000289{
Hanno Becker73d7d792018-12-11 10:35:51 +0000290 MPI_VALIDATE_RET( X != NULL );
291
Paul Bakker2f5947e2011-05-18 15:47:11 +0000292 if( X->n * biL <= pos )
293 return( 0 );
294
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200295 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000296}
297
298/*
299 * Set a bit to a specific value of 0 or 1
300 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200301int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000302{
303 int ret = 0;
304 size_t off = pos / biL;
305 size_t idx = pos % biL;
Hanno Becker73d7d792018-12-11 10:35:51 +0000306 MPI_VALIDATE_RET( X != NULL );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000307
308 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200309 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200310
Paul Bakker2f5947e2011-05-18 15:47:11 +0000311 if( X->n * biL <= pos )
312 {
313 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200314 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000315
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200316 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000317 }
318
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200319 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
320 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000321
322cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200323
Paul Bakker2f5947e2011-05-18 15:47:11 +0000324 return( ret );
325}
326
327/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200328 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000329 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200330size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000331{
Paul Bakker23986e52011-04-24 08:57:21 +0000332 size_t i, j, count = 0;
Hanno Beckerf25ee7f2018-12-19 16:51:02 +0000333 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000334
335 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000336 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000337 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
338 return( count );
339
340 return( 0 );
341}
342
343/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200344 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000345 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200346size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000347{
Gabor Mezei89e31462022-08-12 15:36:56 +0200348 return( mbedtls_mpi_core_bitlen( X->p, X->n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000349}
350
351/*
352 * Return the total size in bytes
353 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200354size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000355{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200356 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000357}
358
359/*
360 * Convert an ASCII character to digit value
361 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200362static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000363{
364 *d = 255;
365
366 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
367 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
368 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
369
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200370 if( *d >= (mbedtls_mpi_uint) radix )
371 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000372
373 return( 0 );
374}
375
376/*
377 * Import from an ASCII string
378 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200379int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000380{
Janos Follath24eed8d2019-11-22 13:21:35 +0000381 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000382 size_t i, j, slen, n;
Gilles Peskine80f56732021-04-03 18:26:13 +0200383 int sign = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200384 mbedtls_mpi_uint d;
385 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000386 MPI_VALIDATE_RET( X != NULL );
387 MPI_VALIDATE_RET( s != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000388
389 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000390 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000391
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200392 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000393
Gilles Peskine7cba8592021-06-08 18:32:34 +0200394 if( s[0] == 0 )
395 {
396 mbedtls_mpi_free( X );
397 return( 0 );
398 }
399
Gilles Peskine80f56732021-04-03 18:26:13 +0200400 if( s[0] == '-' )
401 {
402 ++s;
403 sign = -1;
404 }
405
Paul Bakkerff60ee62010-03-16 21:09:09 +0000406 slen = strlen( s );
407
Paul Bakker5121ce52009-01-03 21:22:43 +0000408 if( radix == 16 )
409 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100410 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200411 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
412
Paul Bakkerff60ee62010-03-16 21:09:09 +0000413 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000414
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200415 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
416 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000417
Paul Bakker23986e52011-04-24 08:57:21 +0000418 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000419 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200420 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200421 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000422 }
423 }
424 else
425 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200426 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000427
Paul Bakkerff60ee62010-03-16 21:09:09 +0000428 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000429 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200430 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
431 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Gilles Peskine80f56732021-04-03 18:26:13 +0200432 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000433 }
434 }
435
Gilles Peskine80f56732021-04-03 18:26:13 +0200436 if( sign < 0 && mbedtls_mpi_bitlen( X ) != 0 )
437 X->s = -1;
438
Paul Bakker5121ce52009-01-03 21:22:43 +0000439cleanup:
440
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200441 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000442
443 return( ret );
444}
445
446/*
Ron Eldora16fa292018-11-20 14:07:01 +0200447 * Helper to write the digits high-order first.
Paul Bakker5121ce52009-01-03 21:22:43 +0000448 */
Ron Eldora16fa292018-11-20 14:07:01 +0200449static int mpi_write_hlp( mbedtls_mpi *X, int radix,
450 char **p, const size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000451{
Janos Follath24eed8d2019-11-22 13:21:35 +0000452 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200453 mbedtls_mpi_uint r;
Ron Eldora16fa292018-11-20 14:07:01 +0200454 size_t length = 0;
455 char *p_end = *p + buflen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000456
Ron Eldora16fa292018-11-20 14:07:01 +0200457 do
458 {
459 if( length >= buflen )
460 {
461 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
462 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000463
Ron Eldora16fa292018-11-20 14:07:01 +0200464 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
465 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
466 /*
467 * Write the residue in the current position, as an ASCII character.
468 */
469 if( r < 0xA )
470 *(--p_end) = (char)( '0' + r );
471 else
472 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000473
Ron Eldora16fa292018-11-20 14:07:01 +0200474 length++;
475 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000476
Ron Eldora16fa292018-11-20 14:07:01 +0200477 memmove( *p, p_end, length );
478 *p += length;
Paul Bakker5121ce52009-01-03 21:22:43 +0000479
480cleanup:
481
482 return( ret );
483}
484
485/*
486 * Export into an ASCII string
487 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100488int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
489 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000490{
Paul Bakker23986e52011-04-24 08:57:21 +0000491 int ret = 0;
492 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000493 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200494 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000495 MPI_VALIDATE_RET( X != NULL );
496 MPI_VALIDATE_RET( olen != NULL );
497 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000498
499 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000500 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000501
Hanno Becker23cfea02019-02-04 09:45:07 +0000502 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
503 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
504 * `n`. If radix > 4, this might be a strict
505 * overapproximation of the number of
506 * radix-adic digits needed to present `n`. */
507 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
508 * present `n`. */
509
Janos Follath80470622019-03-06 13:43:02 +0000510 n += 1; /* Terminating null byte */
Hanno Becker23cfea02019-02-04 09:45:07 +0000511 n += 1; /* Compensate for the divisions above, which round down `n`
512 * in case it's not even. */
513 n += 1; /* Potential '-'-sign. */
514 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
515 * which always uses an even number of hex-digits. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000516
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100517 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000518 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100519 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200520 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000521 }
522
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100523 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200524 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000525
526 if( X->s == -1 )
Hanno Beckerc983c812019-02-01 16:41:30 +0000527 {
Paul Bakker5121ce52009-01-03 21:22:43 +0000528 *p++ = '-';
Hanno Beckerc983c812019-02-01 16:41:30 +0000529 buflen--;
530 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000531
532 if( radix == 16 )
533 {
Paul Bakker23986e52011-04-24 08:57:21 +0000534 int c;
535 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000536
Paul Bakker23986e52011-04-24 08:57:21 +0000537 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000538 {
Paul Bakker23986e52011-04-24 08:57:21 +0000539 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000540 {
Paul Bakker23986e52011-04-24 08:57:21 +0000541 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000542
Paul Bakker6c343d72014-07-10 14:36:19 +0200543 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000544 continue;
545
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000546 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000547 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000548 k = 1;
549 }
550 }
551 }
552 else
553 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200554 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000555
556 if( T.s == -1 )
557 T.s = 1;
558
Ron Eldora16fa292018-11-20 14:07:01 +0200559 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000560 }
561
562 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100563 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000564
565cleanup:
566
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200567 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000568
569 return( ret );
570}
571
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200572#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000573/*
574 * Read X from an opened file
575 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200576int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000577{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200578 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000579 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000580 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000581 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000582 * Buffer should have space for (short) label and decimal formatted MPI,
583 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000584 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200585 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000586
Hanno Becker73d7d792018-12-11 10:35:51 +0000587 MPI_VALIDATE_RET( X != NULL );
588 MPI_VALIDATE_RET( fin != NULL );
589
590 if( radix < 2 || radix > 16 )
591 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
592
Paul Bakker5121ce52009-01-03 21:22:43 +0000593 memset( s, 0, sizeof( s ) );
594 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200595 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000596
597 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000598 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200599 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000600
Hanno Beckerb2034b72017-04-26 11:46:46 +0100601 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
602 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000603
604 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100605 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000606 if( mpi_get_digit( &d, radix, *p ) != 0 )
607 break;
608
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200609 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000610}
611
612/*
613 * Write X into an opened file (or stdout if fout == NULL)
614 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200615int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000616{
Janos Follath24eed8d2019-11-22 13:21:35 +0000617 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000618 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000619 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000620 * Buffer should have space for (short) label and decimal formatted MPI,
621 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000622 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200623 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Hanno Becker73d7d792018-12-11 10:35:51 +0000624 MPI_VALIDATE_RET( X != NULL );
625
626 if( radix < 2 || radix > 16 )
627 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000628
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100629 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000630
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100631 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000632
633 if( p == NULL ) p = "";
634
635 plen = strlen( p );
636 slen = strlen( s );
637 s[slen++] = '\r';
638 s[slen++] = '\n';
639
640 if( fout != NULL )
641 {
642 if( fwrite( p, 1, plen, fout ) != plen ||
643 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200644 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000645 }
646 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200647 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000648
649cleanup:
650
651 return( ret );
652}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200653#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000654
655/*
Janos Follatha778a942019-02-13 10:28:28 +0000656 * Import X from unsigned binary data, little endian
Przemyslaw Stekiel76960a72022-02-21 13:42:09 +0100657 *
658 * This function is guaranteed to return an MPI with exactly the necessary
659 * number of limbs (in particular, it does not skip 0s in the input).
Janos Follatha778a942019-02-13 10:28:28 +0000660 */
661int mbedtls_mpi_read_binary_le( mbedtls_mpi *X,
662 const unsigned char *buf, size_t buflen )
663{
Janos Follath24eed8d2019-11-22 13:21:35 +0000664 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follath620c58c2022-08-15 11:58:42 +0100665 const size_t limbs = CHARS_TO_LIMBS( buflen );
Janos Follatha778a942019-02-13 10:28:28 +0000666
667 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +0200668 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Janos Follatha778a942019-02-13 10:28:28 +0000669
Janos Follath5f016652022-07-22 16:18:41 +0100670 MBEDTLS_MPI_CHK( mbedtls_mpi_core_read_le( X->p, X->n, buf, buflen ) );
Janos Follatha778a942019-02-13 10:28:28 +0000671
672cleanup:
673
Janos Follath171a7ef2019-02-15 16:17:45 +0000674 /*
675 * This function is also used to import keys. However, wiping the buffers
676 * upon failure is not necessary because failure only can happen before any
677 * input is copied.
678 */
Janos Follatha778a942019-02-13 10:28:28 +0000679 return( ret );
680}
681
682/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000683 * Import X from unsigned binary data, big endian
Przemyslaw Stekiel76960a72022-02-21 13:42:09 +0100684 *
685 * This function is guaranteed to return an MPI with exactly the necessary
686 * number of limbs (in particular, it does not skip 0s in the input).
Paul Bakker5121ce52009-01-03 21:22:43 +0000687 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200688int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000689{
Janos Follath24eed8d2019-11-22 13:21:35 +0000690 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follath620c58c2022-08-15 11:58:42 +0100691 const size_t limbs = CHARS_TO_LIMBS( buflen );
Paul Bakker5121ce52009-01-03 21:22:43 +0000692
Hanno Becker8ce11a32018-12-19 16:18:52 +0000693 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +0000694 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
695
Hanno Becker073c1992017-10-17 15:17:27 +0100696 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +0200697 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000698
Janos Follath5f016652022-07-22 16:18:41 +0100699 MBEDTLS_MPI_CHK( mbedtls_mpi_core_read_be( X->p, X->n, buf, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000700
701cleanup:
702
Janos Follath171a7ef2019-02-15 16:17:45 +0000703 /*
704 * This function is also used to import keys. However, wiping the buffers
705 * upon failure is not necessary because failure only can happen before any
706 * input is copied.
707 */
Paul Bakker5121ce52009-01-03 21:22:43 +0000708 return( ret );
709}
710
711/*
Janos Follathe344d0f2019-02-19 16:17:40 +0000712 * Export X into unsigned binary data, little endian
713 */
714int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X,
715 unsigned char *buf, size_t buflen )
716{
Janos Follathca5688e2022-08-19 12:05:28 +0100717 return( mbedtls_mpi_core_write_le( X->p, X->n, buf, buflen ) );
Janos Follathe344d0f2019-02-19 16:17:40 +0000718}
719
720/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000721 * Export X into unsigned binary data, big endian
722 */
Gilles Peskine11cdb052018-11-20 16:47:47 +0100723int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
724 unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000725{
Janos Follath5f016652022-07-22 16:18:41 +0100726 return( mbedtls_mpi_core_write_be( X->p, X->n, buf, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000727}
728
729/*
730 * Left-shift: X <<= count
731 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200732int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000733{
Janos Follath24eed8d2019-11-22 13:21:35 +0000734 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000735 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200736 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000737 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000738
739 v0 = count / (biL );
740 t1 = count & (biL - 1);
741
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200742 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000743
Paul Bakkerf9688572011-05-05 10:00:45 +0000744 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200745 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000746
747 ret = 0;
748
749 /*
750 * shift by count / limb_size
751 */
752 if( v0 > 0 )
753 {
Paul Bakker23986e52011-04-24 08:57:21 +0000754 for( i = X->n; i > v0; i-- )
755 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000756
Paul Bakker23986e52011-04-24 08:57:21 +0000757 for( ; i > 0; i-- )
758 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000759 }
760
761 /*
762 * shift by count % limb_size
763 */
764 if( t1 > 0 )
765 {
766 for( i = v0; i < X->n; i++ )
767 {
768 r1 = X->p[i] >> (biL - t1);
769 X->p[i] <<= t1;
770 X->p[i] |= r0;
771 r0 = r1;
772 }
773 }
774
775cleanup:
776
777 return( ret );
778}
779
780/*
781 * Right-shift: X >>= count
782 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200783int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000784{
Gilles Peskine66414202022-09-21 15:36:16 +0200785 MPI_VALIDATE_RET( X != NULL );
786 if( X->n != 0 )
787 mbedtls_mpi_core_shift_r( X->p, X->n, count );
788 return( 0 );
789}
790
Paul Bakker5121ce52009-01-03 21:22:43 +0000791/*
792 * Compare unsigned values
793 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200794int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000795{
Paul Bakker23986e52011-04-24 08:57:21 +0000796 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +0000797 MPI_VALIDATE_RET( X != NULL );
798 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000799
Paul Bakker23986e52011-04-24 08:57:21 +0000800 for( i = X->n; i > 0; i-- )
801 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000802 break;
803
Paul Bakker23986e52011-04-24 08:57:21 +0000804 for( j = Y->n; j > 0; j-- )
805 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000806 break;
807
Paul Bakker23986e52011-04-24 08:57:21 +0000808 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000809 return( 0 );
810
811 if( i > j ) return( 1 );
812 if( j > i ) return( -1 );
813
Paul Bakker23986e52011-04-24 08:57:21 +0000814 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000815 {
Paul Bakker23986e52011-04-24 08:57:21 +0000816 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
817 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000818 }
819
820 return( 0 );
821}
822
823/*
824 * Compare signed values
825 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200826int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000827{
Paul Bakker23986e52011-04-24 08:57:21 +0000828 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +0000829 MPI_VALIDATE_RET( X != NULL );
830 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000831
Paul Bakker23986e52011-04-24 08:57:21 +0000832 for( i = X->n; i > 0; i-- )
833 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000834 break;
835
Paul Bakker23986e52011-04-24 08:57:21 +0000836 for( j = Y->n; j > 0; j-- )
837 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000838 break;
839
Paul Bakker23986e52011-04-24 08:57:21 +0000840 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000841 return( 0 );
842
843 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +0000844 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000845
846 if( X->s > 0 && Y->s < 0 ) return( 1 );
847 if( Y->s > 0 && X->s < 0 ) return( -1 );
848
Paul Bakker23986e52011-04-24 08:57:21 +0000849 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000850 {
Paul Bakker23986e52011-04-24 08:57:21 +0000851 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
852 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000853 }
854
855 return( 0 );
856}
857
Janos Follathee6abce2019-09-05 14:47:19 +0100858/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000859 * Compare signed values
860 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200861int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000862{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200863 mbedtls_mpi Y;
864 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +0000865 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000866
Gilles Peskineef7f4e42022-11-15 23:25:27 +0100867 *p = mpi_sint_abs( z );
Paul Bakker5121ce52009-01-03 21:22:43 +0000868 Y.s = ( z < 0 ) ? -1 : 1;
869 Y.n = 1;
870 Y.p = p;
871
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200872 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000873}
874
875/*
876 * Unsigned addition: X = |A| + |B| (HAC 14.7)
877 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200878int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000879{
Janos Follath24eed8d2019-11-22 13:21:35 +0000880 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100881 size_t j;
Hanno Becker73d7d792018-12-11 10:35:51 +0000882 MPI_VALIDATE_RET( X != NULL );
883 MPI_VALIDATE_RET( A != NULL );
884 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000885
886 if( X == B )
887 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200888 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000889 }
890
891 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200892 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +0200893
Paul Bakkerf7ca7b92009-06-20 10:31:06 +0000894 /*
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100895 * X must always be positive as a result of unsigned additions.
Paul Bakkerf7ca7b92009-06-20 10:31:06 +0000896 */
897 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000898
Paul Bakker23986e52011-04-24 08:57:21 +0000899 for( j = B->n; j > 0; j-- )
900 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000901 break;
902
Gilles Peskinedb14a9d2022-11-15 22:59:00 +0100903 /* Exit early to avoid undefined behavior on NULL+0 when X->n == 0
904 * and B is 0 (of any size). */
905 if( j == 0 )
906 return( 0 );
907
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200908 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000909
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100910 /* j is the number of non-zero limbs of B. Add those to X. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000911
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100912 mbedtls_mpi_uint *p = X->p;
913
Tom Cosgrove6469fdf2022-10-25 12:46:13 +0100914 mbedtls_mpi_uint c = mbedtls_mpi_core_add( p, p, B->p, j );
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100915
916 p += j;
917
918 /* Now propagate any carry */
Paul Bakker5121ce52009-01-03 21:22:43 +0000919
920 while( c != 0 )
921 {
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100922 if( j >= X->n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000923 {
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100924 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j + 1 ) );
925 p = X->p + j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000926 }
927
Tom Cosgroveaf7d44b2022-08-24 14:05:26 +0100928 *p += c; c = ( *p < c ); j++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +0000929 }
930
931cleanup:
932
933 return( ret );
934}
935
Paul Bakker5121ce52009-01-03 21:22:43 +0000936/*
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200937 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
Paul Bakker5121ce52009-01-03 21:22:43 +0000938 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200939int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000940{
Janos Follath24eed8d2019-11-22 13:21:35 +0000941 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000942 size_t n;
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200943 mbedtls_mpi_uint carry;
Hanno Becker73d7d792018-12-11 10:35:51 +0000944 MPI_VALIDATE_RET( X != NULL );
945 MPI_VALIDATE_RET( A != NULL );
946 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000947
Paul Bakker23986e52011-04-24 08:57:21 +0000948 for( n = B->n; n > 0; n-- )
949 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000950 break;
Gilles Peskinec8a91772021-01-27 22:30:43 +0100951 if( n > A->n )
952 {
953 /* B >= (2^ciL)^n > A */
954 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
955 goto cleanup;
956 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000957
Gilles Peskine1acf7cb2020-07-23 01:03:22 +0200958 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, A->n ) );
959
960 /* Set the high limbs of X to match A. Don't touch the lower limbs
961 * because X might be aliased to B, and we must not overwrite the
962 * significant digits of B. */
963 if( A->n > n )
964 memcpy( X->p + n, A->p + n, ( A->n - n ) * ciL );
965 if( X->n > A->n )
966 memset( X->p + A->n, 0, ( X->n - A->n ) * ciL );
967
Tom Cosgrove7e655f72022-07-20 14:02:11 +0100968 carry = mbedtls_mpi_core_sub( X->p, A->p, B->p, n );
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200969 if( carry != 0 )
Gilles Peskinec097e9e2020-06-08 21:58:22 +0200970 {
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200971 /* Propagate the carry to the first nonzero limb of X. */
972 for( ; n < X->n && X->p[n] == 0; n++ )
973 --X->p[n];
974 /* If we ran out of space for the carry, it means that the result
975 * is negative. */
976 if( n == X->n )
Gilles Peskine89b41302020-07-23 01:16:46 +0200977 {
978 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
979 goto cleanup;
980 }
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200981 --X->p[n];
Gilles Peskinec097e9e2020-06-08 21:58:22 +0200982 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000983
Gilles Peskine1acf7cb2020-07-23 01:03:22 +0200984 /* X should always be positive as a result of unsigned subtractions. */
985 X->s = 1;
986
Paul Bakker5121ce52009-01-03 21:22:43 +0000987cleanup:
Paul Bakker5121ce52009-01-03 21:22:43 +0000988 return( ret );
989}
990
Gilles Peskine72ee1e32022-11-09 21:34:09 +0100991/* Common function for signed addition and subtraction.
992 * Calculate A + B * flip_B where flip_B is 1 or -1.
Paul Bakker5121ce52009-01-03 21:22:43 +0000993 */
Gilles Peskine72ee1e32022-11-09 21:34:09 +0100994static int add_sub_mpi( mbedtls_mpi *X,
995 const mbedtls_mpi *A, const mbedtls_mpi *B,
996 int flip_B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000997{
Hanno Becker73d7d792018-12-11 10:35:51 +0000998 int ret, s;
999 MPI_VALIDATE_RET( X != NULL );
1000 MPI_VALIDATE_RET( A != NULL );
1001 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001002
Hanno Becker73d7d792018-12-11 10:35:51 +00001003 s = A->s;
Gilles Peskine72ee1e32022-11-09 21:34:09 +01001004 if( A->s * B->s * flip_B < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001005 {
Gilles Peskine4a768dd2022-11-09 22:02:16 +01001006 int cmp = mbedtls_mpi_cmp_abs( A, B );
1007 if( cmp >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001008 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001009 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Gilles Peskine4a768dd2022-11-09 22:02:16 +01001010 /* If |A| = |B|, the result is 0 and we must set the sign bit
1011 * to +1 regardless of which of A or B was negative. Otherwise,
1012 * since |A| > |B|, the sign is the sign of A. */
1013 X->s = cmp == 0 ? 1 : s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001014 }
1015 else
1016 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001017 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Gilles Peskine4a768dd2022-11-09 22:02:16 +01001018 /* Since |A| < |B|, the sign is the opposite of A. */
Paul Bakker5121ce52009-01-03 21:22:43 +00001019 X->s = -s;
1020 }
1021 }
1022 else
1023 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001024 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001025 X->s = s;
1026 }
1027
1028cleanup:
1029
1030 return( ret );
1031}
1032
1033/*
Gilles Peskine72ee1e32022-11-09 21:34:09 +01001034 * Signed addition: X = A + B
1035 */
1036int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1037{
1038 return( add_sub_mpi( X, A, B, 1 ) );
1039}
1040
1041/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001042 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001043 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001044int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001045{
Gilles Peskine72ee1e32022-11-09 21:34:09 +01001046 return( add_sub_mpi( X, A, B, -1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001047}
1048
1049/*
1050 * Signed addition: X = A + b
1051 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001052int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001053{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001054 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001055 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001056 MPI_VALIDATE_RET( X != NULL );
1057 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001058
Gilles Peskineef7f4e42022-11-15 23:25:27 +01001059 p[0] = mpi_sint_abs( b );
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001060 B.s = ( b < 0 ) ? -1 : 1;
1061 B.n = 1;
1062 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001063
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001064 return( mbedtls_mpi_add_mpi( X, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001065}
1066
1067/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001068 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001069 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001070int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001071{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001072 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001073 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001074 MPI_VALIDATE_RET( X != NULL );
1075 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001076
Gilles Peskineef7f4e42022-11-15 23:25:27 +01001077 p[0] = mpi_sint_abs( b );
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001078 B.s = ( b < 0 ) ? -1 : 1;
1079 B.n = 1;
1080 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001081
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001082 return( mbedtls_mpi_sub_mpi( X, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001083}
1084
Paul Bakker5121ce52009-01-03 21:22:43 +00001085/*
1086 * Baseline multiplication: X = A * B (HAC 14.12)
1087 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001088int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001089{
Janos Follath24eed8d2019-11-22 13:21:35 +00001090 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker1772e052022-04-13 06:51:40 +01001091 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001092 mbedtls_mpi TA, TB;
Hanno Beckerda763de2022-04-13 06:50:02 +01001093 int result_is_zero = 0;
Hanno Becker73d7d792018-12-11 10:35:51 +00001094 MPI_VALIDATE_RET( X != NULL );
1095 MPI_VALIDATE_RET( A != NULL );
1096 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001097
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001098 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001099
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001100 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1101 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001102
Hanno Beckerda763de2022-04-13 06:50:02 +01001103 for( i = A->n; i > 0; i-- )
1104 if( A->p[i - 1] != 0 )
1105 break;
1106 if( i == 0 )
1107 result_is_zero = 1;
1108
1109 for( j = B->n; j > 0; j-- )
1110 if( B->p[j - 1] != 0 )
1111 break;
1112 if( j == 0 )
1113 result_is_zero = 1;
1114
1115 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001116 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001117
Hanno Becker1772e052022-04-13 06:51:40 +01001118 for( size_t k = 0; k < j; k++ )
Hanno Beckerfee261a2022-04-06 06:20:22 +01001119 {
1120 /* We know that there cannot be any carry-out since we're
1121 * iterating from bottom to top. */
Hanno Beckerda763de2022-04-13 06:50:02 +01001122 (void) mbedtls_mpi_core_mla( X->p + k, i + 1,
1123 A->p, i,
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001124 B->p[k] );
Hanno Beckerfee261a2022-04-06 06:20:22 +01001125 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001126
Hanno Beckerda763de2022-04-13 06:50:02 +01001127 /* If the result is 0, we don't shortcut the operation, which reduces
1128 * but does not eliminate side channels leaking the zero-ness. We do
1129 * need to take care to set the sign bit properly since the library does
1130 * not fully support an MPI object with a value of 0 and s == -1. */
1131 if( result_is_zero )
1132 X->s = 1;
1133 else
1134 X->s = A->s * B->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001135
1136cleanup:
1137
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001138 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001139
1140 return( ret );
1141}
1142
1143/*
1144 * Baseline multiplication: X = A * b
1145 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001146int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001147{
Hanno Becker73d7d792018-12-11 10:35:51 +00001148 MPI_VALIDATE_RET( X != NULL );
1149 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001150
Hanno Becker35771312022-04-14 11:52:11 +01001151 size_t n = A->n;
1152 while( n > 0 && A->p[n - 1] == 0 )
1153 --n;
1154
Hanno Becker74a11a32022-04-06 06:27:00 +01001155 /* The general method below doesn't work if b==0. */
Hanno Becker35771312022-04-14 11:52:11 +01001156 if( b == 0 || n == 0 )
Paul Elliott986b55a2021-04-20 21:46:29 +01001157 return( mbedtls_mpi_lset( X, 0 ) );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001158
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001159 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001160 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Gilles Peskinecd0dbf32020-07-24 00:09:04 +02001161 /* In general, A * b requires 1 limb more than b. If
1162 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1163 * number of limbs as A and the call to grow() is not required since
Gilles Peskinee1bba7c2021-03-10 23:44:10 +01001164 * copy() will take care of the growth if needed. However, experimentally,
1165 * making the call to grow() unconditional causes slightly fewer
Gilles Peskinecd0dbf32020-07-24 00:09:04 +02001166 * calls to calloc() in ECP code, presumably because it reuses the
1167 * same mpi for a while and this way the mpi is more likely to directly
Hanno Becker9137b9c2022-04-12 10:51:54 +01001168 * grow to its final size.
1169 *
1170 * Note that calculating A*b as 0 + A*b doesn't work as-is because
1171 * A,X can be the same. */
Hanno Becker35771312022-04-14 11:52:11 +01001172 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n + 1 ) );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001173 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Hanno Becker35771312022-04-14 11:52:11 +01001174 mbedtls_mpi_core_mla( X->p, X->n, A->p, n, b - 1 );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001175
1176cleanup:
1177 return( ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00001178}
1179
1180/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001181 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1182 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001183 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001184static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1185 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001186{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001187#if defined(MBEDTLS_HAVE_UDBL)
1188 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001189#else
Simon Butcher9803d072016-01-03 00:24:34 +00001190 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1191 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001192 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1193 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001194 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001195#endif
1196
Simon Butcher15b15d12015-11-26 19:35:03 +00001197 /*
1198 * Check for overflow
1199 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001200 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001201 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001202 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001203
Simon Butcherf5ba0452015-12-27 23:01:55 +00001204 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001205 }
1206
1207#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001208 dividend = (mbedtls_t_udbl) u1 << biL;
1209 dividend |= (mbedtls_t_udbl) u0;
1210 quotient = dividend / d;
1211 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1212 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1213
1214 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001215 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001216
1217 return (mbedtls_mpi_uint) quotient;
1218#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001219
1220 /*
1221 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1222 * Vol. 2 - Seminumerical Algorithms, Knuth
1223 */
1224
1225 /*
1226 * Normalize the divisor, d, and dividend, u0, u1
1227 */
Janos Follath4670f882022-07-21 18:25:42 +01001228 s = mbedtls_mpi_core_clz( d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001229 d = d << s;
1230
1231 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001232 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001233 u0 = u0 << s;
1234
1235 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001236 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001237
1238 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001239 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001240
1241 /*
1242 * Find the first quotient and remainder
1243 */
1244 q1 = u1 / d1;
1245 r0 = u1 - d1 * q1;
1246
1247 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1248 {
1249 q1 -= 1;
1250 r0 += d1;
1251
1252 if ( r0 >= radix ) break;
1253 }
1254
Simon Butcherf5ba0452015-12-27 23:01:55 +00001255 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001256 q0 = rAX / d1;
1257 r0 = rAX - q0 * d1;
1258
1259 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1260 {
1261 q0 -= 1;
1262 r0 += d1;
1263
1264 if ( r0 >= radix ) break;
1265 }
1266
1267 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001268 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001269
1270 quotient = q1 * radix + q0;
1271
1272 return quotient;
1273#endif
1274}
1275
1276/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001277 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001278 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001279int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1280 const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001281{
Janos Follath24eed8d2019-11-22 13:21:35 +00001282 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001283 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001284 mbedtls_mpi X, Y, Z, T1, T2;
Alexander Kd19a1932019-11-01 18:20:42 +03001285 mbedtls_mpi_uint TP2[3];
Hanno Becker73d7d792018-12-11 10:35:51 +00001286 MPI_VALIDATE_RET( A != NULL );
1287 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001288
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001289 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1290 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001291
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001292 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001293 mbedtls_mpi_init( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001294 /*
1295 * Avoid dynamic memory allocations for constant-size T2.
1296 *
1297 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1298 * so nobody increase the size of the MPI and we're safe to use an on-stack
1299 * buffer.
1300 */
Alexander K35d6d462019-10-31 14:46:45 +03001301 T2.s = 1;
Alexander Kd19a1932019-11-01 18:20:42 +03001302 T2.n = sizeof( TP2 ) / sizeof( *TP2 );
1303 T2.p = TP2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001304
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001305 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001306 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001307 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1308 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001309 return( 0 );
1310 }
1311
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001312 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1313 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001314 X.s = Y.s = 1;
1315
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001316 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1317 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
Gilles Peskine2536aa72020-07-24 00:12:59 +02001318 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, A->n + 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001319
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001320 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001321 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001322 {
1323 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001324 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1325 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001326 }
1327 else k = 0;
1328
1329 n = X.n - 1;
1330 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001331 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001332
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001333 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001334 {
1335 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001336 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001337 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001338 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001339
1340 for( i = n; i > t ; i-- )
1341 {
1342 if( X.p[i] >= Y.p[t] )
1343 Z.p[i - t - 1] = ~0;
1344 else
1345 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001346 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1347 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001348 }
1349
Alexander K35d6d462019-10-31 14:46:45 +03001350 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1351 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1352 T2.p[2] = X.p[i];
1353
Paul Bakker5121ce52009-01-03 21:22:43 +00001354 Z.p[i - t - 1]++;
1355 do
1356 {
1357 Z.p[i - t - 1]--;
1358
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001359 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001360 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001361 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001362 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001363 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001364 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001365
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001366 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1367 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1368 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001369
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001370 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001371 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001372 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1373 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1374 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001375 Z.p[i - t - 1]--;
1376 }
1377 }
1378
1379 if( Q != NULL )
1380 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001381 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001382 Q->s = A->s * B->s;
1383 }
1384
1385 if( R != NULL )
1386 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001387 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001388 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001389 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001390
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001391 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001392 R->s = 1;
1393 }
1394
1395cleanup:
1396
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001397 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001398 mbedtls_mpi_free( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001399 mbedtls_platform_zeroize( TP2, sizeof( TP2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001400
1401 return( ret );
1402}
1403
1404/*
1405 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001406 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001407int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1408 const mbedtls_mpi *A,
1409 mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001410{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001411 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001412 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001413 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001414
Gilles Peskineef7f4e42022-11-15 23:25:27 +01001415 p[0] = mpi_sint_abs( b );
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001416 B.s = ( b < 0 ) ? -1 : 1;
1417 B.n = 1;
1418 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001419
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001420 return( mbedtls_mpi_div_mpi( Q, R, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001421}
1422
1423/*
1424 * Modulo: R = A mod B
1425 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001426int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001427{
Janos Follath24eed8d2019-11-22 13:21:35 +00001428 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +00001429 MPI_VALIDATE_RET( R != NULL );
1430 MPI_VALIDATE_RET( A != NULL );
1431 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001432
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001433 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1434 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001435
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001436 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001437
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001438 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1439 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001440
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001441 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1442 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001443
1444cleanup:
1445
1446 return( ret );
1447}
1448
1449/*
1450 * Modulo: r = A mod b
1451 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001452int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001453{
Paul Bakker23986e52011-04-24 08:57:21 +00001454 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001455 mbedtls_mpi_uint x, y, z;
Hanno Becker73d7d792018-12-11 10:35:51 +00001456 MPI_VALIDATE_RET( r != NULL );
1457 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001458
1459 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001460 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001461
1462 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001463 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001464
1465 /*
1466 * handle trivial cases
1467 */
Gilles Peskineae25bb02022-06-09 19:32:46 +02001468 if( b == 1 || A->n == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001469 {
1470 *r = 0;
1471 return( 0 );
1472 }
1473
1474 if( b == 2 )
1475 {
1476 *r = A->p[0] & 1;
1477 return( 0 );
1478 }
1479
1480 /*
1481 * general case
1482 */
Paul Bakker23986e52011-04-24 08:57:21 +00001483 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001484 {
Paul Bakker23986e52011-04-24 08:57:21 +00001485 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001486 y = ( y << biH ) | ( x >> biH );
1487 z = y / b;
1488 y -= z * b;
1489
1490 x <<= biH;
1491 y = ( y << biH ) | ( x >> biH );
1492 z = y / b;
1493 y -= z * b;
1494 }
1495
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001496 /*
1497 * If A is negative, then the current y represents a negative value.
1498 * Flipping it to the positive side.
1499 */
1500 if( A->s < 0 && y != 0 )
1501 y = b - y;
1502
Paul Bakker5121ce52009-01-03 21:22:43 +00001503 *r = y;
1504
1505 return( 0 );
1506}
1507
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001508static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001509{
Tom Cosgroveb7438d12022-09-15 15:05:59 +01001510 *mm = mbedtls_mpi_core_montmul_init( N->p );
Paul Bakker5121ce52009-01-03 21:22:43 +00001511}
1512
Tom Cosgrove93842842022-08-05 16:59:43 +01001513/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1514 *
1515 * \param[in,out] A One of the numbers to multiply.
1516 * It must have at least as many limbs as N
1517 * (A->n >= N->n), and any limbs beyond n are ignored.
1518 * On successful completion, A contains the result of
1519 * the multiplication A * B * R^-1 mod N where
1520 * R = (2^ciL)^n.
1521 * \param[in] B One of the numbers to multiply.
1522 * It must be nonzero and must not have more limbs than N
1523 * (B->n <= N->n).
Tom Cosgrove40d22942022-08-17 06:42:44 +01001524 * \param[in] N The modulus. \p N must be odd.
Tom Cosgrove93842842022-08-05 16:59:43 +01001525 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1526 * This is -N^-1 mod 2^ciL.
1527 * \param[in,out] T A bignum for temporary storage.
1528 * It must be at least twice the limb size of N plus 1
1529 * (T->n >= 2 * N->n + 1).
1530 * Its initial content is unused and
1531 * its final content is indeterminate.
Tom Cosgrove5dd97e62022-08-30 14:31:49 +01001532 * It does not get reallocated.
Tom Cosgrove93842842022-08-05 16:59:43 +01001533 */
1534static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B,
1535 const mbedtls_mpi *N, mbedtls_mpi_uint mm,
Tom Cosgrovef88b47e2022-08-17 08:42:58 +01001536 mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001537{
Tom Cosgrove93842842022-08-05 16:59:43 +01001538 mbedtls_mpi_core_montmul( A->p, A->p, B->p, B->n, N->p, N->n, mm, T->p );
Paul Bakker5121ce52009-01-03 21:22:43 +00001539}
1540
1541/*
1542 * Montgomery reduction: A = A * R^-1 mod N
Gilles Peskine2a82f722020-06-04 15:00:49 +02001543 *
Tom Cosgrove93842842022-08-05 16:59:43 +01001544 * See mpi_montmul() regarding constraints and guarantees on the parameters.
Paul Bakker5121ce52009-01-03 21:22:43 +00001545 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02001546static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
Tom Cosgrovef88b47e2022-08-17 08:42:58 +01001547 mbedtls_mpi_uint mm, mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001548{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001549 mbedtls_mpi_uint z = 1;
1550 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001551
Paul Bakker8ddb6452013-02-27 14:56:33 +01001552 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001553 U.p = &z;
1554
Tom Cosgrove93842842022-08-05 16:59:43 +01001555 mpi_montmul( A, &U, N, mm, T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001556}
1557
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001558/**
1559 * Select an MPI from a table without leaking the index.
1560 *
1561 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
1562 * reads the entire table in order to avoid leaking the value of idx to an
1563 * attacker able to observe memory access patterns.
1564 *
1565 * \param[out] R Where to write the selected MPI.
1566 * \param[in] T The table to read from.
1567 * \param[in] T_size The number of elements in the table.
1568 * \param[in] idx The index of the element to select;
1569 * this must satisfy 0 <= idx < T_size.
1570 *
1571 * \return \c 0 on success, or a negative error code.
1572 */
1573static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx )
1574{
1575 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1576
1577 for( size_t i = 0; i < T_size; i++ )
Manuel Pégourié-Gonnard92413ef2021-06-03 10:42:46 +02001578 {
1579 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i],
Gabor Mezei90437e32021-10-20 11:59:27 +02001580 (unsigned char) mbedtls_ct_size_bool_eq( i, idx ) ) );
Manuel Pégourié-Gonnard92413ef2021-06-03 10:42:46 +02001581 }
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001582
1583cleanup:
1584 return( ret );
1585}
1586
Paul Bakker5121ce52009-01-03 21:22:43 +00001587/*
1588 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1589 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001590int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
1591 const mbedtls_mpi *E, const mbedtls_mpi *N,
Yuto Takano538a0cb2021-07-14 10:20:09 +01001592 mbedtls_mpi *prec_RR )
Paul Bakker5121ce52009-01-03 21:22:43 +00001593{
Janos Follath24eed8d2019-11-22 13:21:35 +00001594 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001595 size_t wbits, wsize, one = 1;
1596 size_t i, j, nblimbs;
1597 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001598 mbedtls_mpi_uint ei, mm, state;
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001599 mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00001600 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001601
Hanno Becker73d7d792018-12-11 10:35:51 +00001602 MPI_VALIDATE_RET( X != NULL );
1603 MPI_VALIDATE_RET( A != NULL );
1604 MPI_VALIDATE_RET( E != NULL );
1605 MPI_VALIDATE_RET( N != NULL );
1606
Hanno Becker8d1dd1b2017-09-28 11:02:24 +01001607 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001608 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001609
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001610 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1611 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001612
Chris Jones9246d042020-11-25 15:12:39 +00001613 if( mbedtls_mpi_bitlen( E ) > MBEDTLS_MPI_MAX_BITS ||
1614 mbedtls_mpi_bitlen( N ) > MBEDTLS_MPI_MAX_BITS )
1615 return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1616
Paul Bakkerf6198c12012-05-16 08:02:29 +00001617 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001618 * Init temps and window size
1619 */
1620 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001621 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
1622 mbedtls_mpi_init( &Apos );
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001623 mbedtls_mpi_init( &WW );
Paul Bakker5121ce52009-01-03 21:22:43 +00001624 memset( W, 0, sizeof( W ) );
1625
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001626 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00001627
1628 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1629 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1630
Peter Kolbuse6bcad32018-12-11 14:01:44 -06001631#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001632 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1633 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Peter Kolbuse6bcad32018-12-11 14:01:44 -06001634#endif
Paul Bakkerb6d5f082011-11-25 11:52:11 +00001635
Paul Bakker5121ce52009-01-03 21:22:43 +00001636 j = N->n + 1;
Tom Cosgrove93842842022-08-05 16:59:43 +01001637 /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001638 * and mpi_montred() calls later. Here we ensure that W[1] and X are
1639 * large enough, and later we'll grow other W[i] to the same length.
1640 * They must not be shrunk midway through this function!
1641 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001642 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1643 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1644 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001645
1646 /*
Paul Bakker50546922012-05-19 08:40:49 +00001647 * Compensate for negative A (and correct at the end)
1648 */
1649 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00001650 if( neg )
1651 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001652 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00001653 Apos.s = 1;
1654 A = &Apos;
1655 }
1656
1657 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001658 * If 1st call, pre-compute R^2 mod N
1659 */
Yuto Takano538a0cb2021-07-14 10:20:09 +01001660 if( prec_RR == NULL || prec_RR->p == NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +00001661 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001662 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1663 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1664 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001665
Yuto Takano538a0cb2021-07-14 10:20:09 +01001666 if( prec_RR != NULL )
1667 memcpy( prec_RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001668 }
1669 else
Yuto Takano538a0cb2021-07-14 10:20:09 +01001670 memcpy( &RR, prec_RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001671
1672 /*
1673 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1674 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001675 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001676 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001677 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001678 /* This should be a no-op because W[1] is already that large before
1679 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
Tom Cosgrove93842842022-08-05 16:59:43 +01001680 * in mpi_montmul() below, so let's make sure. */
Gilles Peskine2aa3f162021-06-15 21:22:48 +02001681 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n + 1 ) );
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001682 }
Paul Bakkerc2024f42014-01-23 20:38:35 +01001683 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001684 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001685
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001686 /* Note that this is safe because W[1] always has at least N->n limbs
1687 * (it grew above and was preserved by mbedtls_mpi_copy()). */
Tom Cosgrove93842842022-08-05 16:59:43 +01001688 mpi_montmul( &W[1], &RR, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001689
1690 /*
1691 * X = R^2 * R^-1 mod N = R mod N
1692 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001693 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Gilles Peskine4e91d472020-06-04 20:55:15 +02001694 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001695
1696 if( wsize > 1 )
1697 {
1698 /*
1699 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1700 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001701 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001702
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001703 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1704 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001705
1706 for( i = 0; i < wsize - 1; i++ )
Tom Cosgrove93842842022-08-05 16:59:43 +01001707 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01001708
Paul Bakker5121ce52009-01-03 21:22:43 +00001709 /*
1710 * W[i] = W[i - 1] * W[1]
1711 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001712 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001713 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001714 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1715 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001716
Tom Cosgrove93842842022-08-05 16:59:43 +01001717 mpi_montmul( &W[i], &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001718 }
1719 }
1720
1721 nblimbs = E->n;
1722 bufsize = 0;
1723 nbits = 0;
1724 wbits = 0;
1725 state = 0;
1726
1727 while( 1 )
1728 {
1729 if( bufsize == 0 )
1730 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01001731 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001732 break;
1733
Paul Bakker0d7702c2013-10-29 16:18:35 +01001734 nblimbs--;
1735
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001736 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00001737 }
1738
1739 bufsize--;
1740
1741 ei = (E->p[nblimbs] >> bufsize) & 1;
1742
1743 /*
1744 * skip leading 0s
1745 */
1746 if( ei == 0 && state == 0 )
1747 continue;
1748
1749 if( ei == 0 && state == 1 )
1750 {
1751 /*
1752 * out of window, square X
1753 */
Tom Cosgrove93842842022-08-05 16:59:43 +01001754 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001755 continue;
1756 }
1757
1758 /*
1759 * add ei to current window
1760 */
1761 state = 2;
1762
1763 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02001764 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001765
1766 if( nbits == wsize )
1767 {
1768 /*
1769 * X = X^wsize R^-1 mod N
1770 */
1771 for( i = 0; i < wsize; i++ )
Tom Cosgrove93842842022-08-05 16:59:43 +01001772 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001773
1774 /*
1775 * X = X * W[wbits] R^-1 mod N
1776 */
Manuel Pégourié-Gonnarde22176e2021-06-10 09:34:00 +02001777 MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) );
Tom Cosgrove93842842022-08-05 16:59:43 +01001778 mpi_montmul( X, &WW, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001779
1780 state--;
1781 nbits = 0;
1782 wbits = 0;
1783 }
1784 }
1785
1786 /*
1787 * process the remaining bits
1788 */
1789 for( i = 0; i < nbits; i++ )
1790 {
Tom Cosgrove93842842022-08-05 16:59:43 +01001791 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001792
1793 wbits <<= 1;
1794
Paul Bakker66d5d072014-06-17 16:39:18 +02001795 if( ( wbits & ( one << wsize ) ) != 0 )
Tom Cosgrove93842842022-08-05 16:59:43 +01001796 mpi_montmul( X, &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001797 }
1798
1799 /*
1800 * X = A^E * R * R^-1 mod N = A^E mod N
1801 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02001802 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001803
Hanno Beckera4af1c42017-04-18 09:07:45 +01001804 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00001805 {
1806 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001807 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001808 }
1809
Paul Bakker5121ce52009-01-03 21:22:43 +00001810cleanup:
1811
Paul Bakker66d5d072014-06-17 16:39:18 +02001812 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001813 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001814
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001815 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001816 mbedtls_mpi_free( &WW );
Paul Bakker6c591fa2011-05-05 11:49:20 +00001817
Yuto Takano538a0cb2021-07-14 10:20:09 +01001818 if( prec_RR == NULL || prec_RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001819 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00001820
1821 return( ret );
1822}
1823
Paul Bakker5121ce52009-01-03 21:22:43 +00001824/*
1825 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1826 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001827int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001828{
Janos Follath24eed8d2019-11-22 13:21:35 +00001829 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001830 size_t lz, lzt;
Alexander Ke8ad49f2019-08-16 16:16:07 +03001831 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001832
Hanno Becker73d7d792018-12-11 10:35:51 +00001833 MPI_VALIDATE_RET( G != NULL );
1834 MPI_VALIDATE_RET( A != NULL );
1835 MPI_VALIDATE_RET( B != NULL );
1836
Alexander Ke8ad49f2019-08-16 16:16:07 +03001837 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001838
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001839 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
1840 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001841
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001842 lz = mbedtls_mpi_lsb( &TA );
1843 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001844
Gilles Peskine27253bc2021-06-09 13:26:43 +02001845 /* The loop below gives the correct result when A==0 but not when B==0.
1846 * So have a special case for B==0. Leverage the fact that we just
1847 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
1848 * slightly more efficient than cmp_int(). */
1849 if( lzt == 0 && mbedtls_mpi_get_bit( &TB, 0 ) == 0 )
1850 {
1851 ret = mbedtls_mpi_copy( G, A );
1852 goto cleanup;
1853 }
1854
Paul Bakker66d5d072014-06-17 16:39:18 +02001855 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001856 lz = lzt;
1857
Paul Bakker5121ce52009-01-03 21:22:43 +00001858 TA.s = TB.s = 1;
1859
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001860 /* We mostly follow the procedure described in HAC 14.54, but with some
1861 * minor differences:
1862 * - Sequences of multiplications or divisions by 2 are grouped into a
1863 * single shift operation.
Gilles Peskineb09c7ee2021-06-21 18:58:39 +02001864 * - The procedure in HAC assumes that 0 < TB <= TA.
1865 * - The condition TB <= TA is not actually necessary for correctness.
1866 * TA and TB have symmetric roles except for the loop termination
1867 * condition, and the shifts at the beginning of the loop body
1868 * remove any significance from the ordering of TA vs TB before
1869 * the shifts.
1870 * - If TA = 0, the loop goes through 0 iterations and the result is
1871 * correctly TB.
1872 * - The case TB = 0 was short-circuited above.
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001873 *
1874 * For the correctness proof below, decompose the original values of
1875 * A and B as
1876 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
1877 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
1878 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
1879 * and gcd(A',B') is odd or 0.
1880 *
1881 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
1882 * The code maintains the following invariant:
1883 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
Gilles Peskine4df3f1f2021-06-15 22:09:39 +02001884 */
1885
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001886 /* Proof that the loop terminates:
1887 * At each iteration, either the right-shift by 1 is made on a nonzero
1888 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
1889 * by at least 1, or the right-shift by 1 is made on zero and then
1890 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
1891 * since in that case TB is calculated from TB-TA with the condition TB>TA).
1892 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001893 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001894 {
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001895 /* Divisions by 2 preserve the invariant (I). */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001896 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
1897 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001898
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001899 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
1900 * TA-TB is even so the division by 2 has an integer result.
1901 * Invariant (I) is preserved since any odd divisor of both TA and TB
1902 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
Shaun Case8b0ecbc2021-12-20 21:14:10 -08001903 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001904 * divides TA.
1905 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001906 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001907 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001908 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
1909 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001910 }
1911 else
1912 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001913 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
1914 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001915 }
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001916 /* Note that one of TA or TB is still odd. */
Paul Bakker5121ce52009-01-03 21:22:43 +00001917 }
1918
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001919 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
1920 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
1921 * - If there was at least one loop iteration, then one of TA or TB is odd,
1922 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
1923 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
1924 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
Gilles Peskine4d3fd362021-06-21 11:40:38 +02001925 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001926 */
1927
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001928 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
1929 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001930
1931cleanup:
1932
Alexander Ke8ad49f2019-08-16 16:16:07 +03001933 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001934
1935 return( ret );
1936}
1937
Paul Bakker33dc46b2014-04-30 16:11:39 +02001938/*
1939 * Fill X with size bytes of random.
Gilles Peskine22cdd0c2022-10-27 20:15:13 +02001940 * The bytes returned from the RNG are used in a specific order which
1941 * is suitable for deterministic ECDSA (see the specification of
1942 * mbedtls_mpi_random() and the implementation in mbedtls_mpi_fill_random()).
Paul Bakker33dc46b2014-04-30 16:11:39 +02001943 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001944int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00001945 int (*f_rng)(void *, unsigned char *, size_t),
1946 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00001947{
Janos Follath24eed8d2019-11-22 13:21:35 +00001948 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follath620c58c2022-08-15 11:58:42 +01001949 const size_t limbs = CHARS_TO_LIMBS( size );
Hanno Beckerda1655a2017-10-18 14:21:44 +01001950
Hanno Becker8ce11a32018-12-19 16:18:52 +00001951 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00001952 MPI_VALIDATE_RET( f_rng != NULL );
Paul Bakker33dc46b2014-04-30 16:11:39 +02001953
Hanno Beckerda1655a2017-10-18 14:21:44 +01001954 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +02001955 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02001956 if( size == 0 )
1957 return( 0 );
Paul Bakker287781a2011-03-26 13:18:49 +00001958
Gilles Peskine5980f2b2022-09-09 20:55:53 +02001959 ret = mbedtls_mpi_core_fill_random( X->p, X->n, size, f_rng, p_rng );
Paul Bakker287781a2011-03-26 13:18:49 +00001960
1961cleanup:
1962 return( ret );
1963}
1964
Gilles Peskine02ac93a2021-03-29 22:02:55 +02001965int mbedtls_mpi_random( mbedtls_mpi *X,
1966 mbedtls_mpi_sint min,
1967 const mbedtls_mpi *N,
1968 int (*f_rng)(void *, unsigned char *, size_t),
1969 void *p_rng )
1970{
Gilles Peskine02ac93a2021-03-29 22:02:55 +02001971 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Gilles Peskinee5381682021-04-13 21:23:25 +02001972 int count;
Gilles Peskine5b0589e2021-04-13 21:09:10 +02001973 unsigned lt_lower = 1, lt_upper = 0;
Gilles Peskine02ac93a2021-03-29 22:02:55 +02001974 size_t n_bits = mbedtls_mpi_bitlen( N );
1975 size_t n_bytes = ( n_bits + 7 ) / 8;
Gilles Peskine5b0589e2021-04-13 21:09:10 +02001976 mbedtls_mpi lower_bound;
Gilles Peskine02ac93a2021-03-29 22:02:55 +02001977
Gilles Peskine1e918f42021-03-29 22:14:51 +02001978 if( min < 0 )
1979 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1980 if( mbedtls_mpi_cmp_int( N, min ) <= 0 )
1981 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1982
Gilles Peskinee5381682021-04-13 21:23:25 +02001983 /*
1984 * When min == 0, each try has at worst a probability 1/2 of failing
1985 * (the msb has a probability 1/2 of being 0, and then the result will
1986 * be < N), so after 30 tries failure probability is a most 2**(-30).
1987 *
1988 * When N is just below a power of 2, as is the case when generating
Gilles Peskinee842e582021-04-15 11:45:19 +02001989 * a random scalar on most elliptic curves, 1 try is enough with
Gilles Peskinee5381682021-04-13 21:23:25 +02001990 * overwhelming probability. When N is just above a power of 2,
Gilles Peskinee842e582021-04-15 11:45:19 +02001991 * as when generating a random scalar on secp224k1, each try has
Gilles Peskinee5381682021-04-13 21:23:25 +02001992 * a probability of failing that is almost 1/2.
1993 *
1994 * The probabilities are almost the same if min is nonzero but negligible
1995 * compared to N. This is always the case when N is crypto-sized, but
1996 * it's convenient to support small N for testing purposes. When N
1997 * is small, use a higher repeat count, otherwise the probability of
1998 * failure is macroscopic.
1999 */
Gilles Peskine87823d72021-06-02 21:18:59 +02002000 count = ( n_bytes > 4 ? 30 : 250 );
Gilles Peskinee5381682021-04-13 21:23:25 +02002001
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002002 mbedtls_mpi_init( &lower_bound );
2003
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002004 /* Ensure that target MPI has exactly the same number of limbs
2005 * as the upper bound, even if the upper bound has leading zeros.
2006 * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
Gilles Peskineed32b572021-06-02 22:17:52 +02002007 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) );
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002008 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) );
2009 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002010
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002011 /*
2012 * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
2013 * when f_rng is a suitably parametrized instance of HMAC_DRBG:
2014 * - use the same byte ordering;
2015 * - keep the leftmost n_bits bits of the generated octet string;
2016 * - try until result is in the desired range.
2017 * This also avoids any bias, which is especially important for ECDSA.
2018 */
2019 do
2020 {
Gilles Peskine5980f2b2022-09-09 20:55:53 +02002021 MBEDTLS_MPI_CHK( mbedtls_mpi_core_fill_random( X->p, X->n,
2022 n_bytes,
2023 f_rng, p_rng ) );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002024 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, 8 * n_bytes - n_bits ) );
2025
Gilles Peskinee5381682021-04-13 21:23:25 +02002026 if( --count == 0 )
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002027 {
2028 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2029 goto cleanup;
2030 }
2031
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002032 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, &lt_lower ) );
2033 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, &lt_upper ) );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002034 }
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002035 while( lt_lower != 0 || lt_upper == 0 );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002036
2037cleanup:
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002038 mbedtls_mpi_free( &lower_bound );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002039 return( ret );
2040}
2041
Paul Bakker5121ce52009-01-03 21:22:43 +00002042/*
2043 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2044 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002045int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00002046{
Janos Follath24eed8d2019-11-22 13:21:35 +00002047 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002048 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Hanno Becker73d7d792018-12-11 10:35:51 +00002049 MPI_VALIDATE_RET( X != NULL );
2050 MPI_VALIDATE_RET( A != NULL );
2051 MPI_VALIDATE_RET( N != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00002052
Hanno Becker4bcb4912017-04-18 15:49:39 +01002053 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002054 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002055
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002056 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2057 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2058 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002059
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002060 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002061
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002062 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002063 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002064 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002065 goto cleanup;
2066 }
2067
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002068 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2069 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2070 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2071 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002072
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002073 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2074 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2075 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2076 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002077
2078 do
2079 {
2080 while( ( TU.p[0] & 1 ) == 0 )
2081 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002082 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002083
2084 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2085 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002086 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2087 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002088 }
2089
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002090 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2091 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002092 }
2093
2094 while( ( TV.p[0] & 1 ) == 0 )
2095 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002096 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002097
2098 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2099 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002100 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2101 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002102 }
2103
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002104 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2105 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002106 }
2107
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002108 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002109 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002110 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2111 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2112 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002113 }
2114 else
2115 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002116 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2117 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2118 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002119 }
2120 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002121 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002122
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002123 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2124 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002125
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002126 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2127 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002128
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002129 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002130
2131cleanup:
2132
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002133 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2134 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2135 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002136
2137 return( ret );
2138}
2139
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002140#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00002141
Paul Bakker5121ce52009-01-03 21:22:43 +00002142static const int small_prime[] =
2143{
2144 3, 5, 7, 11, 13, 17, 19, 23,
2145 29, 31, 37, 41, 43, 47, 53, 59,
2146 61, 67, 71, 73, 79, 83, 89, 97,
2147 101, 103, 107, 109, 113, 127, 131, 137,
2148 139, 149, 151, 157, 163, 167, 173, 179,
2149 181, 191, 193, 197, 199, 211, 223, 227,
2150 229, 233, 239, 241, 251, 257, 263, 269,
2151 271, 277, 281, 283, 293, 307, 311, 313,
2152 317, 331, 337, 347, 349, 353, 359, 367,
2153 373, 379, 383, 389, 397, 401, 409, 419,
2154 421, 431, 433, 439, 443, 449, 457, 461,
2155 463, 467, 479, 487, 491, 499, 503, 509,
2156 521, 523, 541, 547, 557, 563, 569, 571,
2157 577, 587, 593, 599, 601, 607, 613, 617,
2158 619, 631, 641, 643, 647, 653, 659, 661,
2159 673, 677, 683, 691, 701, 709, 719, 727,
2160 733, 739, 743, 751, 757, 761, 769, 773,
2161 787, 797, 809, 811, 821, 823, 827, 829,
2162 839, 853, 857, 859, 863, 877, 881, 883,
2163 887, 907, 911, 919, 929, 937, 941, 947,
2164 953, 967, 971, 977, 983, 991, 997, -103
2165};
2166
2167/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002168 * Small divisors test (X must be positive)
2169 *
2170 * Return values:
2171 * 0: no small factor (possible prime, more tests needed)
2172 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002173 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002174 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002175 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002176static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002177{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002178 int ret = 0;
2179 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002180 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002181
Paul Bakker5121ce52009-01-03 21:22:43 +00002182 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002183 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002184
2185 for( i = 0; small_prime[i] > 0; i++ )
2186 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002187 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002188 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002189
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002190 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002191
2192 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002193 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002194 }
2195
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002196cleanup:
2197 return( ret );
2198}
2199
2200/*
2201 * Miller-Rabin pseudo-primality test (HAC 4.24)
2202 */
Janos Follathda31fa12018-09-03 14:45:23 +01002203static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002204 int (*f_rng)(void *, unsigned char *, size_t),
2205 void *p_rng )
2206{
Pascal Junodb99183d2015-03-11 16:49:45 +01002207 int ret, count;
Janos Follathda31fa12018-09-03 14:45:23 +01002208 size_t i, j, k, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002209 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002210
Hanno Becker8ce11a32018-12-19 16:18:52 +00002211 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002212 MPI_VALIDATE_RET( f_rng != NULL );
2213
2214 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2215 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002216 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002217
Paul Bakker5121ce52009-01-03 21:22:43 +00002218 /*
2219 * W = |X| - 1
2220 * R = W >> lsb( W )
2221 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002222 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2223 s = mbedtls_mpi_lsb( &W );
2224 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2225 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002226
Janos Follathda31fa12018-09-03 14:45:23 +01002227 for( i = 0; i < rounds; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002228 {
2229 /*
2230 * pick a random A, 1 < A < |X| - 1
2231 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002232 count = 0;
2233 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002234 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002235
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002236 j = mbedtls_mpi_bitlen( &A );
2237 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002238 if (j > k) {
Darryl Greene3f95ed2018-10-02 13:21:35 +01002239 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Pascal Junodb99183d2015-03-11 16:49:45 +01002240 }
2241
2242 if (count++ > 30) {
Jens Wiklanderf08aa3e2019-01-17 13:30:57 +01002243 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2244 goto cleanup;
Pascal Junodb99183d2015-03-11 16:49:45 +01002245 }
2246
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002247 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2248 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002249
2250 /*
2251 * A = A^R mod |X|
2252 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002253 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002254
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002255 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2256 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002257 continue;
2258
2259 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002260 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002261 {
2262 /*
2263 * A = A * A mod |X|
2264 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002265 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2266 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002267
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002268 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002269 break;
2270
2271 j++;
2272 }
2273
2274 /*
2275 * not prime if A != |X| - 1 or A == 1
2276 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002277 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2278 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002279 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002280 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002281 break;
2282 }
2283 }
2284
2285cleanup:
Hanno Becker73d7d792018-12-11 10:35:51 +00002286 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2287 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002288 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002289
2290 return( ret );
2291}
2292
2293/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002294 * Pseudo-primality test: small factors, then Miller-Rabin
2295 */
Janos Follatha0b67c22018-09-18 14:48:23 +01002296int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2297 int (*f_rng)(void *, unsigned char *, size_t),
2298 void *p_rng )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002299{
Janos Follath24eed8d2019-11-22 13:21:35 +00002300 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002301 mbedtls_mpi XX;
Hanno Becker8ce11a32018-12-19 16:18:52 +00002302 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002303 MPI_VALIDATE_RET( f_rng != NULL );
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002304
2305 XX.s = 1;
2306 XX.n = X->n;
2307 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002308
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002309 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2310 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2311 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002312
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002313 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002314 return( 0 );
2315
2316 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2317 {
2318 if( ret == 1 )
2319 return( 0 );
2320
2321 return( ret );
2322 }
2323
Janos Follathda31fa12018-09-03 14:45:23 +01002324 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
Janos Follathf301d232018-08-14 13:34:01 +01002325}
2326
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002327/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002328 * Prime number generation
Jethro Beekman66689272018-02-14 19:24:10 -08002329 *
Janos Follathf301d232018-08-14 13:34:01 +01002330 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2331 * be either 1024 bits or 1536 bits long, and flags must contain
2332 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Paul Bakker5121ce52009-01-03 21:22:43 +00002333 */
Janos Follath7c025a92018-08-14 11:08:41 +01002334int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002335 int (*f_rng)(void *, unsigned char *, size_t),
2336 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002337{
Jethro Beekman66689272018-02-14 19:24:10 -08002338#ifdef MBEDTLS_HAVE_INT64
2339// ceil(2^63.5)
2340#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2341#else
2342// ceil(2^31.5)
2343#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2344#endif
2345 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker23986e52011-04-24 08:57:21 +00002346 size_t k, n;
Janos Follathda31fa12018-09-03 14:45:23 +01002347 int rounds;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002348 mbedtls_mpi_uint r;
2349 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002350
Hanno Becker8ce11a32018-12-19 16:18:52 +00002351 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002352 MPI_VALIDATE_RET( f_rng != NULL );
2353
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002354 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2355 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002356
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002357 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002358
2359 n = BITS_TO_LIMBS( nbits );
2360
Janos Follathda31fa12018-09-03 14:45:23 +01002361 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2362 {
2363 /*
2364 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2365 */
2366 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2367 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2368 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2369 }
2370 else
2371 {
2372 /*
2373 * 2^-100 error probability, number of rounds computed based on HAC,
2374 * fact 4.48
2375 */
2376 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2377 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2378 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2379 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2380 }
2381
Jethro Beekman66689272018-02-14 19:24:10 -08002382 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002383 {
Jethro Beekman66689272018-02-14 19:24:10 -08002384 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2385 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2386 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2387
2388 k = n * biL;
2389 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2390 X->p[0] |= 1;
2391
Janos Follath7c025a92018-08-14 11:08:41 +01002392 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002393 {
Janos Follatha0b67c22018-09-18 14:48:23 +01002394 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
Jethro Beekman66689272018-02-14 19:24:10 -08002395
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002396 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002397 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002398 }
Jethro Beekman66689272018-02-14 19:24:10 -08002399 else
Paul Bakker5121ce52009-01-03 21:22:43 +00002400 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002401 /*
Tom Cosgrovece7f18c2022-07-28 05:50:56 +01002402 * A necessary condition for Y and X = 2Y + 1 to be prime
Jethro Beekman66689272018-02-14 19:24:10 -08002403 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2404 * Make sure it is satisfied, while keeping X = 3 mod 4
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002405 */
Jethro Beekman66689272018-02-14 19:24:10 -08002406
2407 X->p[0] |= 2;
2408
2409 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2410 if( r == 0 )
2411 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2412 else if( r == 1 )
2413 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2414
2415 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2416 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2417 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2418
2419 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002420 {
Jethro Beekman66689272018-02-14 19:24:10 -08002421 /*
2422 * First, check small factors for X and Y
2423 * before doing Miller-Rabin on any of them
2424 */
2425 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2426 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002427 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002428 == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002429 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002430 == 0 )
Jethro Beekman66689272018-02-14 19:24:10 -08002431 goto cleanup;
2432
2433 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2434 goto cleanup;
2435
2436 /*
2437 * Next candidates. We want to preserve Y = (X-1) / 2 and
2438 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2439 * so up Y by 6 and X by 12.
2440 */
2441 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2442 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002443 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002444 }
2445 }
2446
2447cleanup:
2448
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002449 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002450
2451 return( ret );
2452}
2453
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002454#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002455
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002456#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002457
Paul Bakker23986e52011-04-24 08:57:21 +00002458#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002459
2460static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2461{
2462 { 693, 609, 21 },
2463 { 1764, 868, 28 },
2464 { 768454923, 542167814, 1 }
2465};
2466
Paul Bakker5121ce52009-01-03 21:22:43 +00002467/*
2468 * Checkup routine
2469 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002470int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002471{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002472 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002473 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002474
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002475 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2476 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002477
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002478 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002479 "EFE021C2645FD1DC586E69184AF4A31E" \
2480 "D5F53E93B5F123FA41680867BA110131" \
2481 "944FE7952E2517337780CB0DB80E61AA" \
2482 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2483
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002484 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002485 "B2E7EFD37075B9F03FF989C7C5051C20" \
2486 "34D2A323810251127E7BF8625A4F49A5" \
2487 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2488 "5B5C25763222FEFCCFC38B832366C29E" ) );
2489
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002490 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002491 "0066A198186C18C10B2F5ED9B522752A" \
2492 "9830B69916E535C8F047518A889A43A5" \
2493 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2494
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002495 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002496
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002497 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002498 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2499 "9E857EA95A03512E2BAE7391688D264A" \
2500 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2501 "8001B72E848A38CAE1C65F78E56ABDEF" \
2502 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2503 "ECF677152EF804370C1A305CAF3B5BF1" \
2504 "30879B56C61DE584A0F53A2447A51E" ) );
2505
2506 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002507 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002508
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002509 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002510 {
2511 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002512 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002513
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002514 ret = 1;
2515 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002516 }
2517
2518 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002519 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002520
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002521 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002522
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002523 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002524 "256567336059E52CAE22925474705F39A94" ) );
2525
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002526 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002527 "6613F26162223DF488E9CD48CC132C7A" \
2528 "0AC93C701B001B092E4E5B9F73BCD27B" \
2529 "9EE50D0657C77F374E903CDFA4C642" ) );
2530
2531 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002532 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002533
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002534 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2535 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002536 {
2537 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002538 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002539
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002540 ret = 1;
2541 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002542 }
2543
2544 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002545 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002546
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002547 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002548
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002549 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002550 "36E139AEA55215609D2816998ED020BB" \
2551 "BD96C37890F65171D948E9BC7CBAA4D9" \
2552 "325D24D6A3C12710F10A09FA08AB87" ) );
2553
2554 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002555 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002556
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002557 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002558 {
2559 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002560 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002561
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002562 ret = 1;
2563 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002564 }
2565
2566 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002567 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002568
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002569 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002570
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002571 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002572 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2573 "C3DBA76456363A10869622EAC2DD84EC" \
2574 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2575
2576 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002577 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002578
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002579 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002580 {
2581 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002582 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002583
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002584 ret = 1;
2585 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002586 }
2587
2588 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002589 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002590
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002591 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002592 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002593
Paul Bakker66d5d072014-06-17 16:39:18 +02002594 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002595 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002596 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2597 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002598
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002599 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002600
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002601 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002602 {
2603 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002604 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002605
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002606 ret = 1;
2607 goto cleanup;
2608 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002609 }
2610
2611 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002612 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002613
Paul Bakker5121ce52009-01-03 21:22:43 +00002614cleanup:
2615
2616 if( ret != 0 && verbose != 0 )
Kenneth Soerensen518d4352020-04-01 17:22:45 +02002617 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002618
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002619 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2620 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002621
2622 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002623 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002624
2625 return( ret );
2626}
2627
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002628#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002629
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002630#endif /* MBEDTLS_BIGNUM_C */