blob: 1c7f9197f0b47319bf6f8be43a9d14ad31c2eb83 [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
255/*
256 * Set value from integer
257 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200258int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000259{
Janos Follath24eed8d2019-11-22 13:21:35 +0000260 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +0000261 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000262
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200263 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000264 memset( X->p, 0, X->n * ciL );
265
266 X->p[0] = ( z < 0 ) ? -z : z;
267 X->s = ( z < 0 ) ? -1 : 1;
268
269cleanup:
270
271 return( ret );
272}
273
274/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000275 * Get a specific bit
276 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200277int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000278{
Hanno Becker73d7d792018-12-11 10:35:51 +0000279 MPI_VALIDATE_RET( X != NULL );
280
Paul Bakker2f5947e2011-05-18 15:47:11 +0000281 if( X->n * biL <= pos )
282 return( 0 );
283
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200284 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000285}
286
287/*
288 * Set a bit to a specific value of 0 or 1
289 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200290int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000291{
292 int ret = 0;
293 size_t off = pos / biL;
294 size_t idx = pos % biL;
Hanno Becker73d7d792018-12-11 10:35:51 +0000295 MPI_VALIDATE_RET( X != NULL );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000296
297 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200298 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200299
Paul Bakker2f5947e2011-05-18 15:47:11 +0000300 if( X->n * biL <= pos )
301 {
302 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200303 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000304
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200305 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000306 }
307
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200308 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
309 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000310
311cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200312
Paul Bakker2f5947e2011-05-18 15:47:11 +0000313 return( ret );
314}
315
316/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200317 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000318 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200319size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000320{
Paul Bakker23986e52011-04-24 08:57:21 +0000321 size_t i, j, count = 0;
Hanno Beckerf25ee7f2018-12-19 16:51:02 +0000322 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000323
324 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000325 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000326 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
327 return( count );
328
329 return( 0 );
330}
331
332/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200333 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000334 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200335size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000336{
Gabor Mezei89e31462022-08-12 15:36:56 +0200337 return( mbedtls_mpi_core_bitlen( X->p, X->n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000338}
339
340/*
341 * Return the total size in bytes
342 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200343size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000344{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200345 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000346}
347
348/*
349 * Convert an ASCII character to digit value
350 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200351static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000352{
353 *d = 255;
354
355 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
356 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
357 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
358
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200359 if( *d >= (mbedtls_mpi_uint) radix )
360 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000361
362 return( 0 );
363}
364
365/*
366 * Import from an ASCII string
367 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200368int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000369{
Janos Follath24eed8d2019-11-22 13:21:35 +0000370 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000371 size_t i, j, slen, n;
Gilles Peskine80f56732021-04-03 18:26:13 +0200372 int sign = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200373 mbedtls_mpi_uint d;
374 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000375 MPI_VALIDATE_RET( X != NULL );
376 MPI_VALIDATE_RET( s != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000377
378 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000379 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000380
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200381 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000382
Gilles Peskine7cba8592021-06-08 18:32:34 +0200383 if( s[0] == 0 )
384 {
385 mbedtls_mpi_free( X );
386 return( 0 );
387 }
388
Gilles Peskine80f56732021-04-03 18:26:13 +0200389 if( s[0] == '-' )
390 {
391 ++s;
392 sign = -1;
393 }
394
Paul Bakkerff60ee62010-03-16 21:09:09 +0000395 slen = strlen( s );
396
Paul Bakker5121ce52009-01-03 21:22:43 +0000397 if( radix == 16 )
398 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100399 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200400 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
401
Paul Bakkerff60ee62010-03-16 21:09:09 +0000402 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000403
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200404 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
405 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000406
Paul Bakker23986e52011-04-24 08:57:21 +0000407 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000408 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200409 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200410 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000411 }
412 }
413 else
414 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200415 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000416
Paul Bakkerff60ee62010-03-16 21:09:09 +0000417 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000418 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200419 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
420 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Gilles Peskine80f56732021-04-03 18:26:13 +0200421 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000422 }
423 }
424
Gilles Peskine80f56732021-04-03 18:26:13 +0200425 if( sign < 0 && mbedtls_mpi_bitlen( X ) != 0 )
426 X->s = -1;
427
Paul Bakker5121ce52009-01-03 21:22:43 +0000428cleanup:
429
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200430 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000431
432 return( ret );
433}
434
435/*
Ron Eldora16fa292018-11-20 14:07:01 +0200436 * Helper to write the digits high-order first.
Paul Bakker5121ce52009-01-03 21:22:43 +0000437 */
Ron Eldora16fa292018-11-20 14:07:01 +0200438static int mpi_write_hlp( mbedtls_mpi *X, int radix,
439 char **p, const size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000440{
Janos Follath24eed8d2019-11-22 13:21:35 +0000441 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200442 mbedtls_mpi_uint r;
Ron Eldora16fa292018-11-20 14:07:01 +0200443 size_t length = 0;
444 char *p_end = *p + buflen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000445
Ron Eldora16fa292018-11-20 14:07:01 +0200446 do
447 {
448 if( length >= buflen )
449 {
450 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
451 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000452
Ron Eldora16fa292018-11-20 14:07:01 +0200453 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
454 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
455 /*
456 * Write the residue in the current position, as an ASCII character.
457 */
458 if( r < 0xA )
459 *(--p_end) = (char)( '0' + r );
460 else
461 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000462
Ron Eldora16fa292018-11-20 14:07:01 +0200463 length++;
464 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000465
Ron Eldora16fa292018-11-20 14:07:01 +0200466 memmove( *p, p_end, length );
467 *p += length;
Paul Bakker5121ce52009-01-03 21:22:43 +0000468
469cleanup:
470
471 return( ret );
472}
473
474/*
475 * Export into an ASCII string
476 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100477int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
478 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000479{
Paul Bakker23986e52011-04-24 08:57:21 +0000480 int ret = 0;
481 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000482 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200483 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000484 MPI_VALIDATE_RET( X != NULL );
485 MPI_VALIDATE_RET( olen != NULL );
486 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000487
488 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000489 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000490
Hanno Becker23cfea02019-02-04 09:45:07 +0000491 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
492 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
493 * `n`. If radix > 4, this might be a strict
494 * overapproximation of the number of
495 * radix-adic digits needed to present `n`. */
496 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
497 * present `n`. */
498
Janos Follath80470622019-03-06 13:43:02 +0000499 n += 1; /* Terminating null byte */
Hanno Becker23cfea02019-02-04 09:45:07 +0000500 n += 1; /* Compensate for the divisions above, which round down `n`
501 * in case it's not even. */
502 n += 1; /* Potential '-'-sign. */
503 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
504 * which always uses an even number of hex-digits. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000505
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100506 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000507 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100508 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200509 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000510 }
511
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100512 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200513 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000514
515 if( X->s == -1 )
Hanno Beckerc983c812019-02-01 16:41:30 +0000516 {
Paul Bakker5121ce52009-01-03 21:22:43 +0000517 *p++ = '-';
Hanno Beckerc983c812019-02-01 16:41:30 +0000518 buflen--;
519 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000520
521 if( radix == 16 )
522 {
Paul Bakker23986e52011-04-24 08:57:21 +0000523 int c;
524 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000525
Paul Bakker23986e52011-04-24 08:57:21 +0000526 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000527 {
Paul Bakker23986e52011-04-24 08:57:21 +0000528 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000529 {
Paul Bakker23986e52011-04-24 08:57:21 +0000530 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000531
Paul Bakker6c343d72014-07-10 14:36:19 +0200532 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000533 continue;
534
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000535 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000536 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000537 k = 1;
538 }
539 }
540 }
541 else
542 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200543 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000544
545 if( T.s == -1 )
546 T.s = 1;
547
Ron Eldora16fa292018-11-20 14:07:01 +0200548 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000549 }
550
551 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100552 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000553
554cleanup:
555
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200556 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000557
558 return( ret );
559}
560
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200561#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000562/*
563 * Read X from an opened file
564 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200565int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000566{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200567 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000568 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000569 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000570 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000571 * Buffer should have space for (short) label and decimal formatted MPI,
572 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000573 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200574 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000575
Hanno Becker73d7d792018-12-11 10:35:51 +0000576 MPI_VALIDATE_RET( X != NULL );
577 MPI_VALIDATE_RET( fin != NULL );
578
579 if( radix < 2 || radix > 16 )
580 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
581
Paul Bakker5121ce52009-01-03 21:22:43 +0000582 memset( s, 0, sizeof( s ) );
583 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200584 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000585
586 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000587 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200588 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000589
Hanno Beckerb2034b72017-04-26 11:46:46 +0100590 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
591 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000592
593 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100594 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000595 if( mpi_get_digit( &d, radix, *p ) != 0 )
596 break;
597
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200598 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000599}
600
601/*
602 * Write X into an opened file (or stdout if fout == NULL)
603 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200604int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000605{
Janos Follath24eed8d2019-11-22 13:21:35 +0000606 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000607 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000608 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000609 * Buffer should have space for (short) label and decimal formatted MPI,
610 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000611 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200612 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Hanno Becker73d7d792018-12-11 10:35:51 +0000613 MPI_VALIDATE_RET( X != NULL );
614
615 if( radix < 2 || radix > 16 )
616 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000617
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100618 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000619
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100620 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000621
622 if( p == NULL ) p = "";
623
624 plen = strlen( p );
625 slen = strlen( s );
626 s[slen++] = '\r';
627 s[slen++] = '\n';
628
629 if( fout != NULL )
630 {
631 if( fwrite( p, 1, plen, fout ) != plen ||
632 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200633 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000634 }
635 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200636 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000637
638cleanup:
639
640 return( ret );
641}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200642#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000643
644/*
Janos Follatha778a942019-02-13 10:28:28 +0000645 * Import X from unsigned binary data, little endian
Przemyslaw Stekiel76960a72022-02-21 13:42:09 +0100646 *
647 * This function is guaranteed to return an MPI with exactly the necessary
648 * number of limbs (in particular, it does not skip 0s in the input).
Janos Follatha778a942019-02-13 10:28:28 +0000649 */
650int mbedtls_mpi_read_binary_le( mbedtls_mpi *X,
651 const unsigned char *buf, size_t buflen )
652{
Janos Follath24eed8d2019-11-22 13:21:35 +0000653 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follath620c58c2022-08-15 11:58:42 +0100654 const size_t limbs = CHARS_TO_LIMBS( buflen );
Janos Follatha778a942019-02-13 10:28:28 +0000655
656 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +0200657 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Janos Follatha778a942019-02-13 10:28:28 +0000658
Janos Follath5f016652022-07-22 16:18:41 +0100659 MBEDTLS_MPI_CHK( mbedtls_mpi_core_read_le( X->p, X->n, buf, buflen ) );
Janos Follatha778a942019-02-13 10:28:28 +0000660
661cleanup:
662
Janos Follath171a7ef2019-02-15 16:17:45 +0000663 /*
664 * This function is also used to import keys. However, wiping the buffers
665 * upon failure is not necessary because failure only can happen before any
666 * input is copied.
667 */
Janos Follatha778a942019-02-13 10:28:28 +0000668 return( ret );
669}
670
671/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000672 * Import X from unsigned binary data, big endian
Przemyslaw Stekiel76960a72022-02-21 13:42:09 +0100673 *
674 * This function is guaranteed to return an MPI with exactly the necessary
675 * number of limbs (in particular, it does not skip 0s in the input).
Paul Bakker5121ce52009-01-03 21:22:43 +0000676 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200677int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000678{
Janos Follath24eed8d2019-11-22 13:21:35 +0000679 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follath620c58c2022-08-15 11:58:42 +0100680 const size_t limbs = CHARS_TO_LIMBS( buflen );
Paul Bakker5121ce52009-01-03 21:22:43 +0000681
Hanno Becker8ce11a32018-12-19 16:18:52 +0000682 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +0000683 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
684
Hanno Becker073c1992017-10-17 15:17:27 +0100685 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +0200686 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000687
Janos Follath5f016652022-07-22 16:18:41 +0100688 MBEDTLS_MPI_CHK( mbedtls_mpi_core_read_be( X->p, X->n, buf, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000689
690cleanup:
691
Janos Follath171a7ef2019-02-15 16:17:45 +0000692 /*
693 * This function is also used to import keys. However, wiping the buffers
694 * upon failure is not necessary because failure only can happen before any
695 * input is copied.
696 */
Paul Bakker5121ce52009-01-03 21:22:43 +0000697 return( ret );
698}
699
700/*
Janos Follathe344d0f2019-02-19 16:17:40 +0000701 * Export X into unsigned binary data, little endian
702 */
703int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X,
704 unsigned char *buf, size_t buflen )
705{
Janos Follathca5688e2022-08-19 12:05:28 +0100706 return( mbedtls_mpi_core_write_le( X->p, X->n, buf, buflen ) );
Janos Follathe344d0f2019-02-19 16:17:40 +0000707}
708
709/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000710 * Export X into unsigned binary data, big endian
711 */
Gilles Peskine11cdb052018-11-20 16:47:47 +0100712int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
713 unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000714{
Janos Follath5f016652022-07-22 16:18:41 +0100715 return( mbedtls_mpi_core_write_be( X->p, X->n, buf, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000716}
717
718/*
719 * Left-shift: X <<= count
720 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200721int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000722{
Janos Follath24eed8d2019-11-22 13:21:35 +0000723 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000724 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200725 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000726 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000727
728 v0 = count / (biL );
729 t1 = count & (biL - 1);
730
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200731 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000732
Paul Bakkerf9688572011-05-05 10:00:45 +0000733 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200734 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000735
736 ret = 0;
737
738 /*
739 * shift by count / limb_size
740 */
741 if( v0 > 0 )
742 {
Paul Bakker23986e52011-04-24 08:57:21 +0000743 for( i = X->n; i > v0; i-- )
744 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000745
Paul Bakker23986e52011-04-24 08:57:21 +0000746 for( ; i > 0; i-- )
747 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000748 }
749
750 /*
751 * shift by count % limb_size
752 */
753 if( t1 > 0 )
754 {
755 for( i = v0; i < X->n; i++ )
756 {
757 r1 = X->p[i] >> (biL - t1);
758 X->p[i] <<= t1;
759 X->p[i] |= r0;
760 r0 = r1;
761 }
762 }
763
764cleanup:
765
766 return( ret );
767}
768
769/*
770 * Right-shift: X >>= count
771 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200772int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000773{
Paul Bakker23986e52011-04-24 08:57:21 +0000774 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200775 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000776 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000777
778 v0 = count / biL;
779 v1 = count & (biL - 1);
780
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100781 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200782 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100783
Paul Bakker5121ce52009-01-03 21:22:43 +0000784 /*
785 * shift by count / limb_size
786 */
787 if( v0 > 0 )
788 {
789 for( i = 0; i < X->n - v0; i++ )
790 X->p[i] = X->p[i + v0];
791
792 for( ; i < X->n; i++ )
793 X->p[i] = 0;
794 }
795
796 /*
797 * shift by count % limb_size
798 */
799 if( v1 > 0 )
800 {
Paul Bakker23986e52011-04-24 08:57:21 +0000801 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000802 {
Paul Bakker23986e52011-04-24 08:57:21 +0000803 r1 = X->p[i - 1] << (biL - v1);
804 X->p[i - 1] >>= v1;
805 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000806 r0 = r1;
807 }
808 }
809
810 return( 0 );
811}
812
813/*
814 * Compare unsigned values
815 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200816int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000817{
Paul Bakker23986e52011-04-24 08:57:21 +0000818 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +0000819 MPI_VALIDATE_RET( X != NULL );
820 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000821
Paul Bakker23986e52011-04-24 08:57:21 +0000822 for( i = X->n; i > 0; i-- )
823 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000824 break;
825
Paul Bakker23986e52011-04-24 08:57:21 +0000826 for( j = Y->n; j > 0; j-- )
827 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000828 break;
829
Paul Bakker23986e52011-04-24 08:57:21 +0000830 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000831 return( 0 );
832
833 if( i > j ) return( 1 );
834 if( j > i ) return( -1 );
835
Paul Bakker23986e52011-04-24 08:57:21 +0000836 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000837 {
Paul Bakker23986e52011-04-24 08:57:21 +0000838 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
839 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000840 }
841
842 return( 0 );
843}
844
845/*
846 * Compare signed values
847 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200848int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000849{
Paul Bakker23986e52011-04-24 08:57:21 +0000850 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +0000851 MPI_VALIDATE_RET( X != NULL );
852 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000853
Paul Bakker23986e52011-04-24 08:57:21 +0000854 for( i = X->n; i > 0; i-- )
855 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000856 break;
857
Paul Bakker23986e52011-04-24 08:57:21 +0000858 for( j = Y->n; j > 0; j-- )
859 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000860 break;
861
Paul Bakker23986e52011-04-24 08:57:21 +0000862 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000863 return( 0 );
864
865 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +0000866 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000867
868 if( X->s > 0 && Y->s < 0 ) return( 1 );
869 if( Y->s > 0 && X->s < 0 ) return( -1 );
870
Paul Bakker23986e52011-04-24 08:57:21 +0000871 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000872 {
Paul Bakker23986e52011-04-24 08:57:21 +0000873 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
874 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000875 }
876
877 return( 0 );
878}
879
Janos Follathee6abce2019-09-05 14:47:19 +0100880/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000881 * Compare signed values
882 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200883int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000884{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200885 mbedtls_mpi Y;
886 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +0000887 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000888
889 *p = ( z < 0 ) ? -z : z;
890 Y.s = ( z < 0 ) ? -1 : 1;
891 Y.n = 1;
892 Y.p = p;
893
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200894 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000895}
896
897/*
898 * Unsigned addition: X = |A| + |B| (HAC 14.7)
899 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200900int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000901{
Janos Follath24eed8d2019-11-22 13:21:35 +0000902 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000903 size_t i, j;
Janos Follath6c922682015-10-30 17:43:11 +0100904 mbedtls_mpi_uint *o, *p, c, tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +0000905 MPI_VALIDATE_RET( X != NULL );
906 MPI_VALIDATE_RET( A != NULL );
907 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000908
909 if( X == B )
910 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200911 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000912 }
913
914 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200915 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +0200916
Paul Bakkerf7ca7b92009-06-20 10:31:06 +0000917 /*
918 * X should always be positive as a result of unsigned additions.
919 */
920 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000921
Paul Bakker23986e52011-04-24 08:57:21 +0000922 for( j = B->n; j > 0; j-- )
923 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000924 break;
925
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200926 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000927
928 o = B->p; p = X->p; c = 0;
929
Janos Follath6c922682015-10-30 17:43:11 +0100930 /*
931 * tmp is used because it might happen that p == o
932 */
Paul Bakker23986e52011-04-24 08:57:21 +0000933 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000934 {
Janos Follath6c922682015-10-30 17:43:11 +0100935 tmp= *o;
Paul Bakker5121ce52009-01-03 21:22:43 +0000936 *p += c; c = ( *p < c );
Janos Follath6c922682015-10-30 17:43:11 +0100937 *p += tmp; c += ( *p < tmp );
Paul Bakker5121ce52009-01-03 21:22:43 +0000938 }
939
940 while( c != 0 )
941 {
942 if( i >= X->n )
943 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200944 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000945 p = X->p + i;
946 }
947
Paul Bakker2d319fd2012-09-16 21:34:26 +0000948 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +0000949 }
950
951cleanup:
952
953 return( ret );
954}
955
Paul Bakker5121ce52009-01-03 21:22:43 +0000956/*
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200957 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
Paul Bakker5121ce52009-01-03 21:22:43 +0000958 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200959int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000960{
Janos Follath24eed8d2019-11-22 13:21:35 +0000961 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000962 size_t n;
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200963 mbedtls_mpi_uint carry;
Hanno Becker73d7d792018-12-11 10:35:51 +0000964 MPI_VALIDATE_RET( X != NULL );
965 MPI_VALIDATE_RET( A != NULL );
966 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000967
Paul Bakker23986e52011-04-24 08:57:21 +0000968 for( n = B->n; n > 0; n-- )
969 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000970 break;
Gilles Peskinec8a91772021-01-27 22:30:43 +0100971 if( n > A->n )
972 {
973 /* B >= (2^ciL)^n > A */
974 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
975 goto cleanup;
976 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000977
Gilles Peskine1acf7cb2020-07-23 01:03:22 +0200978 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, A->n ) );
979
980 /* Set the high limbs of X to match A. Don't touch the lower limbs
981 * because X might be aliased to B, and we must not overwrite the
982 * significant digits of B. */
983 if( A->n > n )
984 memcpy( X->p + n, A->p + n, ( A->n - n ) * ciL );
985 if( X->n > A->n )
986 memset( X->p + A->n, 0, ( X->n - A->n ) * ciL );
987
Tom Cosgrove7e655f72022-07-20 14:02:11 +0100988 carry = mbedtls_mpi_core_sub( X->p, A->p, B->p, n );
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200989 if( carry != 0 )
Gilles Peskinec097e9e2020-06-08 21:58:22 +0200990 {
Gilles Peskine0e5faf62020-06-08 22:50:35 +0200991 /* Propagate the carry to the first nonzero limb of X. */
992 for( ; n < X->n && X->p[n] == 0; n++ )
993 --X->p[n];
994 /* If we ran out of space for the carry, it means that the result
995 * is negative. */
996 if( n == X->n )
Gilles Peskine89b41302020-07-23 01:16:46 +0200997 {
998 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
999 goto cleanup;
1000 }
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001001 --X->p[n];
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001002 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001003
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001004 /* X should always be positive as a result of unsigned subtractions. */
1005 X->s = 1;
1006
Paul Bakker5121ce52009-01-03 21:22:43 +00001007cleanup:
Paul Bakker5121ce52009-01-03 21:22:43 +00001008 return( ret );
1009}
1010
1011/*
1012 * Signed addition: X = A + B
1013 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001014int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001015{
Hanno Becker73d7d792018-12-11 10:35:51 +00001016 int ret, s;
1017 MPI_VALIDATE_RET( X != NULL );
1018 MPI_VALIDATE_RET( A != NULL );
1019 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001020
Hanno Becker73d7d792018-12-11 10:35:51 +00001021 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001022 if( A->s * B->s < 0 )
1023 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001024 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001025 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001026 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001027 X->s = s;
1028 }
1029 else
1030 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001031 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001032 X->s = -s;
1033 }
1034 }
1035 else
1036 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001037 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001038 X->s = s;
1039 }
1040
1041cleanup:
1042
1043 return( ret );
1044}
1045
1046/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001047 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001048 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001049int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001050{
Hanno Becker73d7d792018-12-11 10:35:51 +00001051 int ret, s;
1052 MPI_VALIDATE_RET( X != NULL );
1053 MPI_VALIDATE_RET( A != NULL );
1054 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001055
Hanno Becker73d7d792018-12-11 10:35:51 +00001056 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001057 if( A->s * B->s > 0 )
1058 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001059 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001060 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001061 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001062 X->s = s;
1063 }
1064 else
1065 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001066 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001067 X->s = -s;
1068 }
1069 }
1070 else
1071 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001072 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001073 X->s = s;
1074 }
1075
1076cleanup:
1077
1078 return( ret );
1079}
1080
1081/*
1082 * Signed addition: X = A + b
1083 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001084int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001085{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001086 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001087 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001088 MPI_VALIDATE_RET( X != NULL );
1089 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001090
1091 p[0] = ( b < 0 ) ? -b : b;
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001092 B.s = ( b < 0 ) ? -1 : 1;
1093 B.n = 1;
1094 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001095
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001096 return( mbedtls_mpi_add_mpi( X, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001097}
1098
1099/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001100 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001101 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001102int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001103{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001104 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001105 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001106 MPI_VALIDATE_RET( X != NULL );
1107 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001108
1109 p[0] = ( b < 0 ) ? -b : b;
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001110 B.s = ( b < 0 ) ? -1 : 1;
1111 B.n = 1;
1112 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001113
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001114 return( mbedtls_mpi_sub_mpi( X, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001115}
1116
Paul Bakker5121ce52009-01-03 21:22:43 +00001117/*
1118 * Baseline multiplication: X = A * B (HAC 14.12)
1119 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001120int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001121{
Janos Follath24eed8d2019-11-22 13:21:35 +00001122 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker1772e052022-04-13 06:51:40 +01001123 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001124 mbedtls_mpi TA, TB;
Hanno Beckerda763de2022-04-13 06:50:02 +01001125 int result_is_zero = 0;
Hanno Becker73d7d792018-12-11 10:35:51 +00001126 MPI_VALIDATE_RET( X != NULL );
1127 MPI_VALIDATE_RET( A != NULL );
1128 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001129
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001130 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001131
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001132 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1133 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001134
Hanno Beckerda763de2022-04-13 06:50:02 +01001135 for( i = A->n; i > 0; i-- )
1136 if( A->p[i - 1] != 0 )
1137 break;
1138 if( i == 0 )
1139 result_is_zero = 1;
1140
1141 for( j = B->n; j > 0; j-- )
1142 if( B->p[j - 1] != 0 )
1143 break;
1144 if( j == 0 )
1145 result_is_zero = 1;
1146
1147 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001148 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001149
Hanno Becker1772e052022-04-13 06:51:40 +01001150 for( size_t k = 0; k < j; k++ )
Hanno Beckerfee261a2022-04-06 06:20:22 +01001151 {
1152 /* We know that there cannot be any carry-out since we're
1153 * iterating from bottom to top. */
Hanno Beckerda763de2022-04-13 06:50:02 +01001154 (void) mbedtls_mpi_core_mla( X->p + k, i + 1,
1155 A->p, i,
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001156 B->p[k] );
Hanno Beckerfee261a2022-04-06 06:20:22 +01001157 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001158
Hanno Beckerda763de2022-04-13 06:50:02 +01001159 /* If the result is 0, we don't shortcut the operation, which reduces
1160 * but does not eliminate side channels leaking the zero-ness. We do
1161 * need to take care to set the sign bit properly since the library does
1162 * not fully support an MPI object with a value of 0 and s == -1. */
1163 if( result_is_zero )
1164 X->s = 1;
1165 else
1166 X->s = A->s * B->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001167
1168cleanup:
1169
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001170 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001171
1172 return( ret );
1173}
1174
1175/*
1176 * Baseline multiplication: X = A * b
1177 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001178int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001179{
Hanno Becker73d7d792018-12-11 10:35:51 +00001180 MPI_VALIDATE_RET( X != NULL );
1181 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001182
Hanno Becker35771312022-04-14 11:52:11 +01001183 size_t n = A->n;
1184 while( n > 0 && A->p[n - 1] == 0 )
1185 --n;
1186
Hanno Becker74a11a32022-04-06 06:27:00 +01001187 /* The general method below doesn't work if b==0. */
Hanno Becker35771312022-04-14 11:52:11 +01001188 if( b == 0 || n == 0 )
Paul Elliott986b55a2021-04-20 21:46:29 +01001189 return( mbedtls_mpi_lset( X, 0 ) );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001190
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001191 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001192 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Gilles Peskinecd0dbf32020-07-24 00:09:04 +02001193 /* In general, A * b requires 1 limb more than b. If
1194 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1195 * number of limbs as A and the call to grow() is not required since
Gilles Peskinee1bba7c2021-03-10 23:44:10 +01001196 * copy() will take care of the growth if needed. However, experimentally,
1197 * making the call to grow() unconditional causes slightly fewer
Gilles Peskinecd0dbf32020-07-24 00:09:04 +02001198 * calls to calloc() in ECP code, presumably because it reuses the
1199 * same mpi for a while and this way the mpi is more likely to directly
Hanno Becker9137b9c2022-04-12 10:51:54 +01001200 * grow to its final size.
1201 *
1202 * Note that calculating A*b as 0 + A*b doesn't work as-is because
1203 * A,X can be the same. */
Hanno Becker35771312022-04-14 11:52:11 +01001204 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n + 1 ) );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001205 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Hanno Becker35771312022-04-14 11:52:11 +01001206 mbedtls_mpi_core_mla( X->p, X->n, A->p, n, b - 1 );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001207
1208cleanup:
1209 return( ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00001210}
1211
1212/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001213 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1214 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001215 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001216static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1217 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001218{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001219#if defined(MBEDTLS_HAVE_UDBL)
1220 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001221#else
Simon Butcher9803d072016-01-03 00:24:34 +00001222 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1223 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001224 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1225 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001226 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001227#endif
1228
Simon Butcher15b15d12015-11-26 19:35:03 +00001229 /*
1230 * Check for overflow
1231 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001232 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001233 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001234 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001235
Simon Butcherf5ba0452015-12-27 23:01:55 +00001236 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001237 }
1238
1239#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001240 dividend = (mbedtls_t_udbl) u1 << biL;
1241 dividend |= (mbedtls_t_udbl) u0;
1242 quotient = dividend / d;
1243 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1244 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1245
1246 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001247 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001248
1249 return (mbedtls_mpi_uint) quotient;
1250#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001251
1252 /*
1253 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1254 * Vol. 2 - Seminumerical Algorithms, Knuth
1255 */
1256
1257 /*
1258 * Normalize the divisor, d, and dividend, u0, u1
1259 */
Janos Follath4670f882022-07-21 18:25:42 +01001260 s = mbedtls_mpi_core_clz( d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001261 d = d << s;
1262
1263 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001264 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001265 u0 = u0 << s;
1266
1267 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001268 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001269
1270 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001271 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001272
1273 /*
1274 * Find the first quotient and remainder
1275 */
1276 q1 = u1 / d1;
1277 r0 = u1 - d1 * q1;
1278
1279 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1280 {
1281 q1 -= 1;
1282 r0 += d1;
1283
1284 if ( r0 >= radix ) break;
1285 }
1286
Simon Butcherf5ba0452015-12-27 23:01:55 +00001287 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001288 q0 = rAX / d1;
1289 r0 = rAX - q0 * d1;
1290
1291 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1292 {
1293 q0 -= 1;
1294 r0 += d1;
1295
1296 if ( r0 >= radix ) break;
1297 }
1298
1299 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001300 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001301
1302 quotient = q1 * radix + q0;
1303
1304 return quotient;
1305#endif
1306}
1307
1308/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001309 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001310 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001311int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1312 const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001313{
Janos Follath24eed8d2019-11-22 13:21:35 +00001314 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001315 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001316 mbedtls_mpi X, Y, Z, T1, T2;
Alexander Kd19a1932019-11-01 18:20:42 +03001317 mbedtls_mpi_uint TP2[3];
Hanno Becker73d7d792018-12-11 10:35:51 +00001318 MPI_VALIDATE_RET( A != NULL );
1319 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001320
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001321 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1322 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001323
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001324 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001325 mbedtls_mpi_init( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001326 /*
1327 * Avoid dynamic memory allocations for constant-size T2.
1328 *
1329 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1330 * so nobody increase the size of the MPI and we're safe to use an on-stack
1331 * buffer.
1332 */
Alexander K35d6d462019-10-31 14:46:45 +03001333 T2.s = 1;
Alexander Kd19a1932019-11-01 18:20:42 +03001334 T2.n = sizeof( TP2 ) / sizeof( *TP2 );
1335 T2.p = TP2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001336
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001337 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001338 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001339 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1340 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001341 return( 0 );
1342 }
1343
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001344 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1345 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001346 X.s = Y.s = 1;
1347
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001348 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1349 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
Gilles Peskine2536aa72020-07-24 00:12:59 +02001350 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, A->n + 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001351
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001352 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001353 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001354 {
1355 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001356 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1357 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001358 }
1359 else k = 0;
1360
1361 n = X.n - 1;
1362 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001363 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001364
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001365 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001366 {
1367 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001368 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001369 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001370 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001371
1372 for( i = n; i > t ; i-- )
1373 {
1374 if( X.p[i] >= Y.p[t] )
1375 Z.p[i - t - 1] = ~0;
1376 else
1377 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001378 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1379 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001380 }
1381
Alexander K35d6d462019-10-31 14:46:45 +03001382 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1383 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1384 T2.p[2] = X.p[i];
1385
Paul Bakker5121ce52009-01-03 21:22:43 +00001386 Z.p[i - t - 1]++;
1387 do
1388 {
1389 Z.p[i - t - 1]--;
1390
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001391 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001392 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001393 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001394 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001395 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001396 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001397
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001398 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1399 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1400 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001401
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001402 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001403 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001404 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1405 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1406 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001407 Z.p[i - t - 1]--;
1408 }
1409 }
1410
1411 if( Q != NULL )
1412 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001413 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001414 Q->s = A->s * B->s;
1415 }
1416
1417 if( R != NULL )
1418 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001419 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001420 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001421 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001422
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001423 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001424 R->s = 1;
1425 }
1426
1427cleanup:
1428
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001429 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001430 mbedtls_mpi_free( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001431 mbedtls_platform_zeroize( TP2, sizeof( TP2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001432
1433 return( ret );
1434}
1435
1436/*
1437 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001438 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001439int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1440 const mbedtls_mpi *A,
1441 mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001442{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001443 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001444 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001445 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001446
1447 p[0] = ( b < 0 ) ? -b : b;
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001448 B.s = ( b < 0 ) ? -1 : 1;
1449 B.n = 1;
1450 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001451
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001452 return( mbedtls_mpi_div_mpi( Q, R, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001453}
1454
1455/*
1456 * Modulo: R = A mod B
1457 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001458int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001459{
Janos Follath24eed8d2019-11-22 13:21:35 +00001460 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +00001461 MPI_VALIDATE_RET( R != NULL );
1462 MPI_VALIDATE_RET( A != NULL );
1463 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001464
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001465 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1466 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001467
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001468 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001469
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001470 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1471 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001472
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001473 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1474 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001475
1476cleanup:
1477
1478 return( ret );
1479}
1480
1481/*
1482 * Modulo: r = A mod b
1483 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001484int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001485{
Paul Bakker23986e52011-04-24 08:57:21 +00001486 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001487 mbedtls_mpi_uint x, y, z;
Hanno Becker73d7d792018-12-11 10:35:51 +00001488 MPI_VALIDATE_RET( r != NULL );
1489 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001490
1491 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001492 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001493
1494 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001495 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001496
1497 /*
1498 * handle trivial cases
1499 */
Gilles Peskineae25bb02022-06-09 19:32:46 +02001500 if( b == 1 || A->n == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001501 {
1502 *r = 0;
1503 return( 0 );
1504 }
1505
1506 if( b == 2 )
1507 {
1508 *r = A->p[0] & 1;
1509 return( 0 );
1510 }
1511
1512 /*
1513 * general case
1514 */
Paul Bakker23986e52011-04-24 08:57:21 +00001515 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001516 {
Paul Bakker23986e52011-04-24 08:57:21 +00001517 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001518 y = ( y << biH ) | ( x >> biH );
1519 z = y / b;
1520 y -= z * b;
1521
1522 x <<= biH;
1523 y = ( y << biH ) | ( x >> biH );
1524 z = y / b;
1525 y -= z * b;
1526 }
1527
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001528 /*
1529 * If A is negative, then the current y represents a negative value.
1530 * Flipping it to the positive side.
1531 */
1532 if( A->s < 0 && y != 0 )
1533 y = b - y;
1534
Paul Bakker5121ce52009-01-03 21:22:43 +00001535 *r = y;
1536
1537 return( 0 );
1538}
1539
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001540static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001541{
Tom Cosgroveb7438d12022-09-15 15:05:59 +01001542 *mm = mbedtls_mpi_core_montmul_init( N->p );
Paul Bakker5121ce52009-01-03 21:22:43 +00001543}
1544
Tom Cosgrove93842842022-08-05 16:59:43 +01001545/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1546 *
1547 * \param[in,out] A One of the numbers to multiply.
1548 * It must have at least as many limbs as N
1549 * (A->n >= N->n), and any limbs beyond n are ignored.
1550 * On successful completion, A contains the result of
1551 * the multiplication A * B * R^-1 mod N where
1552 * R = (2^ciL)^n.
1553 * \param[in] B One of the numbers to multiply.
1554 * It must be nonzero and must not have more limbs than N
1555 * (B->n <= N->n).
Tom Cosgrove40d22942022-08-17 06:42:44 +01001556 * \param[in] N The modulus. \p N must be odd.
Tom Cosgrove93842842022-08-05 16:59:43 +01001557 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1558 * This is -N^-1 mod 2^ciL.
1559 * \param[in,out] T A bignum for temporary storage.
1560 * It must be at least twice the limb size of N plus 1
1561 * (T->n >= 2 * N->n + 1).
1562 * Its initial content is unused and
1563 * its final content is indeterminate.
Tom Cosgrove5dd97e62022-08-30 14:31:49 +01001564 * It does not get reallocated.
Tom Cosgrove93842842022-08-05 16:59:43 +01001565 */
1566static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B,
1567 const mbedtls_mpi *N, mbedtls_mpi_uint mm,
Tom Cosgrovef88b47e2022-08-17 08:42:58 +01001568 mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001569{
Tom Cosgrove93842842022-08-05 16:59:43 +01001570 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 +00001571}
1572
1573/*
1574 * Montgomery reduction: A = A * R^-1 mod N
Gilles Peskine2a82f722020-06-04 15:00:49 +02001575 *
Tom Cosgrove93842842022-08-05 16:59:43 +01001576 * See mpi_montmul() regarding constraints and guarantees on the parameters.
Paul Bakker5121ce52009-01-03 21:22:43 +00001577 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02001578static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
Tom Cosgrovef88b47e2022-08-17 08:42:58 +01001579 mbedtls_mpi_uint mm, mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001580{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001581 mbedtls_mpi_uint z = 1;
1582 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001583
Paul Bakker8ddb6452013-02-27 14:56:33 +01001584 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001585 U.p = &z;
1586
Tom Cosgrove93842842022-08-05 16:59:43 +01001587 mpi_montmul( A, &U, N, mm, T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001588}
1589
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001590/**
1591 * Select an MPI from a table without leaking the index.
1592 *
1593 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
1594 * reads the entire table in order to avoid leaking the value of idx to an
1595 * attacker able to observe memory access patterns.
1596 *
1597 * \param[out] R Where to write the selected MPI.
1598 * \param[in] T The table to read from.
1599 * \param[in] T_size The number of elements in the table.
1600 * \param[in] idx The index of the element to select;
1601 * this must satisfy 0 <= idx < T_size.
1602 *
1603 * \return \c 0 on success, or a negative error code.
1604 */
1605static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx )
1606{
1607 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1608
1609 for( size_t i = 0; i < T_size; i++ )
Manuel Pégourié-Gonnard92413ef2021-06-03 10:42:46 +02001610 {
1611 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i],
Gabor Mezei90437e32021-10-20 11:59:27 +02001612 (unsigned char) mbedtls_ct_size_bool_eq( i, idx ) ) );
Manuel Pégourié-Gonnard92413ef2021-06-03 10:42:46 +02001613 }
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001614
1615cleanup:
1616 return( ret );
1617}
1618
Paul Bakker5121ce52009-01-03 21:22:43 +00001619/*
1620 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1621 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001622int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
1623 const mbedtls_mpi *E, const mbedtls_mpi *N,
Yuto Takano538a0cb2021-07-14 10:20:09 +01001624 mbedtls_mpi *prec_RR )
Paul Bakker5121ce52009-01-03 21:22:43 +00001625{
Janos Follath24eed8d2019-11-22 13:21:35 +00001626 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001627 size_t wbits, wsize, one = 1;
1628 size_t i, j, nblimbs;
1629 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001630 mbedtls_mpi_uint ei, mm, state;
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001631 mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00001632 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001633
Hanno Becker73d7d792018-12-11 10:35:51 +00001634 MPI_VALIDATE_RET( X != NULL );
1635 MPI_VALIDATE_RET( A != NULL );
1636 MPI_VALIDATE_RET( E != NULL );
1637 MPI_VALIDATE_RET( N != NULL );
1638
Hanno Becker8d1dd1b2017-09-28 11:02:24 +01001639 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001640 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001641
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001642 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1643 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001644
Chris Jones9246d042020-11-25 15:12:39 +00001645 if( mbedtls_mpi_bitlen( E ) > MBEDTLS_MPI_MAX_BITS ||
1646 mbedtls_mpi_bitlen( N ) > MBEDTLS_MPI_MAX_BITS )
1647 return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1648
Paul Bakkerf6198c12012-05-16 08:02:29 +00001649 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001650 * Init temps and window size
1651 */
1652 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001653 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
1654 mbedtls_mpi_init( &Apos );
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001655 mbedtls_mpi_init( &WW );
Paul Bakker5121ce52009-01-03 21:22:43 +00001656 memset( W, 0, sizeof( W ) );
1657
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001658 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00001659
1660 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1661 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1662
Peter Kolbuse6bcad32018-12-11 14:01:44 -06001663#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001664 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1665 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Peter Kolbuse6bcad32018-12-11 14:01:44 -06001666#endif
Paul Bakkerb6d5f082011-11-25 11:52:11 +00001667
Paul Bakker5121ce52009-01-03 21:22:43 +00001668 j = N->n + 1;
Tom Cosgrove93842842022-08-05 16:59:43 +01001669 /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001670 * and mpi_montred() calls later. Here we ensure that W[1] and X are
1671 * large enough, and later we'll grow other W[i] to the same length.
1672 * They must not be shrunk midway through this function!
1673 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001674 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1675 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1676 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001677
1678 /*
Paul Bakker50546922012-05-19 08:40:49 +00001679 * Compensate for negative A (and correct at the end)
1680 */
1681 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00001682 if( neg )
1683 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001684 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00001685 Apos.s = 1;
1686 A = &Apos;
1687 }
1688
1689 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001690 * If 1st call, pre-compute R^2 mod N
1691 */
Yuto Takano538a0cb2021-07-14 10:20:09 +01001692 if( prec_RR == NULL || prec_RR->p == NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +00001693 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001694 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1695 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1696 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001697
Yuto Takano538a0cb2021-07-14 10:20:09 +01001698 if( prec_RR != NULL )
1699 memcpy( prec_RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001700 }
1701 else
Yuto Takano538a0cb2021-07-14 10:20:09 +01001702 memcpy( &RR, prec_RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001703
1704 /*
1705 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1706 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001707 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001708 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001709 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001710 /* This should be a no-op because W[1] is already that large before
1711 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
Tom Cosgrove93842842022-08-05 16:59:43 +01001712 * in mpi_montmul() below, so let's make sure. */
Gilles Peskine2aa3f162021-06-15 21:22:48 +02001713 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n + 1 ) );
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001714 }
Paul Bakkerc2024f42014-01-23 20:38:35 +01001715 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001716 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001717
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02001718 /* Note that this is safe because W[1] always has at least N->n limbs
1719 * (it grew above and was preserved by mbedtls_mpi_copy()). */
Tom Cosgrove93842842022-08-05 16:59:43 +01001720 mpi_montmul( &W[1], &RR, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001721
1722 /*
1723 * X = R^2 * R^-1 mod N = R mod N
1724 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001725 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Gilles Peskine4e91d472020-06-04 20:55:15 +02001726 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001727
1728 if( wsize > 1 )
1729 {
1730 /*
1731 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1732 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001733 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001734
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001735 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1736 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001737
1738 for( i = 0; i < wsize - 1; i++ )
Tom Cosgrove93842842022-08-05 16:59:43 +01001739 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01001740
Paul Bakker5121ce52009-01-03 21:22:43 +00001741 /*
1742 * W[i] = W[i - 1] * W[1]
1743 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001744 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001745 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001746 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1747 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001748
Tom Cosgrove93842842022-08-05 16:59:43 +01001749 mpi_montmul( &W[i], &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001750 }
1751 }
1752
1753 nblimbs = E->n;
1754 bufsize = 0;
1755 nbits = 0;
1756 wbits = 0;
1757 state = 0;
1758
1759 while( 1 )
1760 {
1761 if( bufsize == 0 )
1762 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01001763 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001764 break;
1765
Paul Bakker0d7702c2013-10-29 16:18:35 +01001766 nblimbs--;
1767
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001768 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00001769 }
1770
1771 bufsize--;
1772
1773 ei = (E->p[nblimbs] >> bufsize) & 1;
1774
1775 /*
1776 * skip leading 0s
1777 */
1778 if( ei == 0 && state == 0 )
1779 continue;
1780
1781 if( ei == 0 && state == 1 )
1782 {
1783 /*
1784 * out of window, square X
1785 */
Tom Cosgrove93842842022-08-05 16:59:43 +01001786 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001787 continue;
1788 }
1789
1790 /*
1791 * add ei to current window
1792 */
1793 state = 2;
1794
1795 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02001796 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001797
1798 if( nbits == wsize )
1799 {
1800 /*
1801 * X = X^wsize R^-1 mod N
1802 */
1803 for( i = 0; i < wsize; i++ )
Tom Cosgrove93842842022-08-05 16:59:43 +01001804 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001805
1806 /*
1807 * X = X * W[wbits] R^-1 mod N
1808 */
Manuel Pégourié-Gonnarde22176e2021-06-10 09:34:00 +02001809 MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) );
Tom Cosgrove93842842022-08-05 16:59:43 +01001810 mpi_montmul( X, &WW, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001811
1812 state--;
1813 nbits = 0;
1814 wbits = 0;
1815 }
1816 }
1817
1818 /*
1819 * process the remaining bits
1820 */
1821 for( i = 0; i < nbits; i++ )
1822 {
Tom Cosgrove93842842022-08-05 16:59:43 +01001823 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001824
1825 wbits <<= 1;
1826
Paul Bakker66d5d072014-06-17 16:39:18 +02001827 if( ( wbits & ( one << wsize ) ) != 0 )
Tom Cosgrove93842842022-08-05 16:59:43 +01001828 mpi_montmul( X, &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001829 }
1830
1831 /*
1832 * X = A^E * R * R^-1 mod N = A^E mod N
1833 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02001834 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001835
Hanno Beckera4af1c42017-04-18 09:07:45 +01001836 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00001837 {
1838 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001839 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001840 }
1841
Paul Bakker5121ce52009-01-03 21:22:43 +00001842cleanup:
1843
Paul Bakker66d5d072014-06-17 16:39:18 +02001844 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001845 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001846
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001847 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001848 mbedtls_mpi_free( &WW );
Paul Bakker6c591fa2011-05-05 11:49:20 +00001849
Yuto Takano538a0cb2021-07-14 10:20:09 +01001850 if( prec_RR == NULL || prec_RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001851 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00001852
1853 return( ret );
1854}
1855
Paul Bakker5121ce52009-01-03 21:22:43 +00001856/*
1857 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1858 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001859int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001860{
Janos Follath24eed8d2019-11-22 13:21:35 +00001861 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001862 size_t lz, lzt;
Alexander Ke8ad49f2019-08-16 16:16:07 +03001863 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001864
Hanno Becker73d7d792018-12-11 10:35:51 +00001865 MPI_VALIDATE_RET( G != NULL );
1866 MPI_VALIDATE_RET( A != NULL );
1867 MPI_VALIDATE_RET( B != NULL );
1868
Alexander Ke8ad49f2019-08-16 16:16:07 +03001869 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001870
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001871 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
1872 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001873
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001874 lz = mbedtls_mpi_lsb( &TA );
1875 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001876
Gilles Peskine27253bc2021-06-09 13:26:43 +02001877 /* The loop below gives the correct result when A==0 but not when B==0.
1878 * So have a special case for B==0. Leverage the fact that we just
1879 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
1880 * slightly more efficient than cmp_int(). */
1881 if( lzt == 0 && mbedtls_mpi_get_bit( &TB, 0 ) == 0 )
1882 {
1883 ret = mbedtls_mpi_copy( G, A );
1884 goto cleanup;
1885 }
1886
Paul Bakker66d5d072014-06-17 16:39:18 +02001887 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001888 lz = lzt;
1889
Paul Bakker5121ce52009-01-03 21:22:43 +00001890 TA.s = TB.s = 1;
1891
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001892 /* We mostly follow the procedure described in HAC 14.54, but with some
1893 * minor differences:
1894 * - Sequences of multiplications or divisions by 2 are grouped into a
1895 * single shift operation.
Gilles Peskineb09c7ee2021-06-21 18:58:39 +02001896 * - The procedure in HAC assumes that 0 < TB <= TA.
1897 * - The condition TB <= TA is not actually necessary for correctness.
1898 * TA and TB have symmetric roles except for the loop termination
1899 * condition, and the shifts at the beginning of the loop body
1900 * remove any significance from the ordering of TA vs TB before
1901 * the shifts.
1902 * - If TA = 0, the loop goes through 0 iterations and the result is
1903 * correctly TB.
1904 * - The case TB = 0 was short-circuited above.
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001905 *
1906 * For the correctness proof below, decompose the original values of
1907 * A and B as
1908 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
1909 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
1910 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
1911 * and gcd(A',B') is odd or 0.
1912 *
1913 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
1914 * The code maintains the following invariant:
1915 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
Gilles Peskine4df3f1f2021-06-15 22:09:39 +02001916 */
1917
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001918 /* Proof that the loop terminates:
1919 * At each iteration, either the right-shift by 1 is made on a nonzero
1920 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
1921 * by at least 1, or the right-shift by 1 is made on zero and then
1922 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
1923 * since in that case TB is calculated from TB-TA with the condition TB>TA).
1924 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001925 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001926 {
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001927 /* Divisions by 2 preserve the invariant (I). */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001928 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
1929 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001930
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001931 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
1932 * TA-TB is even so the division by 2 has an integer result.
1933 * Invariant (I) is preserved since any odd divisor of both TA and TB
1934 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
Shaun Case8b0ecbc2021-12-20 21:14:10 -08001935 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001936 * divides TA.
1937 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001938 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001939 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001940 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
1941 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001942 }
1943 else
1944 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001945 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
1946 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001947 }
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001948 /* Note that one of TA or TB is still odd. */
Paul Bakker5121ce52009-01-03 21:22:43 +00001949 }
1950
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02001951 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
1952 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
1953 * - If there was at least one loop iteration, then one of TA or TB is odd,
1954 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
1955 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
1956 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
Gilles Peskine4d3fd362021-06-21 11:40:38 +02001957 * 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 +02001958 */
1959
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001960 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
1961 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001962
1963cleanup:
1964
Alexander Ke8ad49f2019-08-16 16:16:07 +03001965 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001966
1967 return( ret );
1968}
1969
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02001970/* Fill X with n_bytes random bytes.
1971 * X must already have room for those bytes.
Gilles Peskineafb2bd22021-06-03 11:51:09 +02001972 * The ordering of the bytes returned from the RNG is suitable for
1973 * deterministic ECDSA (see RFC 6979 §3.3 and mbedtls_mpi_random()).
Gilles Peskineebe9b6a2021-04-13 21:55:35 +02001974 * The size and sign of X are unchanged.
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02001975 * n_bytes must not be 0.
1976 */
1977static int mpi_fill_random_internal(
1978 mbedtls_mpi *X, size_t n_bytes,
1979 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
1980{
1981 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1982 const size_t limbs = CHARS_TO_LIMBS( n_bytes );
1983 const size_t overhead = ( limbs * ciL ) - n_bytes;
1984
1985 if( X->n < limbs )
1986 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02001987
Gilles Peskineebe9b6a2021-04-13 21:55:35 +02001988 memset( X->p, 0, overhead );
1989 memset( (unsigned char *) X->p + limbs * ciL, 0, ( X->n - limbs ) * ciL );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02001990 MBEDTLS_MPI_CHK( f_rng( p_rng, (unsigned char *) X->p + overhead, n_bytes ) );
Janos Follath4670f882022-07-21 18:25:42 +01001991 mbedtls_mpi_core_bigendian_to_host( X->p, limbs );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02001992
1993cleanup:
1994 return( ret );
1995}
1996
Paul Bakker33dc46b2014-04-30 16:11:39 +02001997/*
1998 * Fill X with size bytes of random.
1999 *
2000 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02002001 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02002002 * deterministic, eg for tests).
2003 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002004int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002005 int (*f_rng)(void *, unsigned char *, size_t),
2006 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00002007{
Janos Follath24eed8d2019-11-22 13:21:35 +00002008 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follath620c58c2022-08-15 11:58:42 +01002009 const size_t limbs = CHARS_TO_LIMBS( size );
Hanno Beckerda1655a2017-10-18 14:21:44 +01002010
Hanno Becker8ce11a32018-12-19 16:18:52 +00002011 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002012 MPI_VALIDATE_RET( f_rng != NULL );
Paul Bakker33dc46b2014-04-30 16:11:39 +02002013
Hanno Beckerda1655a2017-10-18 14:21:44 +01002014 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +02002015 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002016 if( size == 0 )
2017 return( 0 );
Paul Bakker287781a2011-03-26 13:18:49 +00002018
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002019 ret = mpi_fill_random_internal( X, size, f_rng, p_rng );
Paul Bakker287781a2011-03-26 13:18:49 +00002020
2021cleanup:
2022 return( ret );
2023}
2024
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002025int mbedtls_mpi_random( mbedtls_mpi *X,
2026 mbedtls_mpi_sint min,
2027 const mbedtls_mpi *N,
2028 int (*f_rng)(void *, unsigned char *, size_t),
2029 void *p_rng )
2030{
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002031 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Gilles Peskinee5381682021-04-13 21:23:25 +02002032 int count;
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002033 unsigned lt_lower = 1, lt_upper = 0;
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002034 size_t n_bits = mbedtls_mpi_bitlen( N );
2035 size_t n_bytes = ( n_bits + 7 ) / 8;
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002036 mbedtls_mpi lower_bound;
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002037
Gilles Peskine1e918f42021-03-29 22:14:51 +02002038 if( min < 0 )
2039 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2040 if( mbedtls_mpi_cmp_int( N, min ) <= 0 )
2041 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2042
Gilles Peskinee5381682021-04-13 21:23:25 +02002043 /*
2044 * When min == 0, each try has at worst a probability 1/2 of failing
2045 * (the msb has a probability 1/2 of being 0, and then the result will
2046 * be < N), so after 30 tries failure probability is a most 2**(-30).
2047 *
2048 * When N is just below a power of 2, as is the case when generating
Gilles Peskinee842e582021-04-15 11:45:19 +02002049 * a random scalar on most elliptic curves, 1 try is enough with
Gilles Peskinee5381682021-04-13 21:23:25 +02002050 * overwhelming probability. When N is just above a power of 2,
Gilles Peskinee842e582021-04-15 11:45:19 +02002051 * as when generating a random scalar on secp224k1, each try has
Gilles Peskinee5381682021-04-13 21:23:25 +02002052 * a probability of failing that is almost 1/2.
2053 *
2054 * The probabilities are almost the same if min is nonzero but negligible
2055 * compared to N. This is always the case when N is crypto-sized, but
2056 * it's convenient to support small N for testing purposes. When N
2057 * is small, use a higher repeat count, otherwise the probability of
2058 * failure is macroscopic.
2059 */
Gilles Peskine87823d72021-06-02 21:18:59 +02002060 count = ( n_bytes > 4 ? 30 : 250 );
Gilles Peskinee5381682021-04-13 21:23:25 +02002061
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002062 mbedtls_mpi_init( &lower_bound );
2063
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002064 /* Ensure that target MPI has exactly the same number of limbs
2065 * as the upper bound, even if the upper bound has leading zeros.
2066 * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
Gilles Peskineed32b572021-06-02 22:17:52 +02002067 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) );
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002068 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) );
2069 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002070
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002071 /*
2072 * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
2073 * when f_rng is a suitably parametrized instance of HMAC_DRBG:
2074 * - use the same byte ordering;
2075 * - keep the leftmost n_bits bits of the generated octet string;
2076 * - try until result is in the desired range.
2077 * This also avoids any bias, which is especially important for ECDSA.
2078 */
2079 do
2080 {
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002081 MBEDTLS_MPI_CHK( mpi_fill_random_internal( X, n_bytes, f_rng, p_rng ) );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002082 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, 8 * n_bytes - n_bits ) );
2083
Gilles Peskinee5381682021-04-13 21:23:25 +02002084 if( --count == 0 )
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002085 {
2086 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2087 goto cleanup;
2088 }
2089
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002090 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, &lt_lower ) );
2091 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, &lt_upper ) );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002092 }
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002093 while( lt_lower != 0 || lt_upper == 0 );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002094
2095cleanup:
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002096 mbedtls_mpi_free( &lower_bound );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002097 return( ret );
2098}
2099
Paul Bakker5121ce52009-01-03 21:22:43 +00002100/*
2101 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2102 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002103int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00002104{
Janos Follath24eed8d2019-11-22 13:21:35 +00002105 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002106 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Hanno Becker73d7d792018-12-11 10:35:51 +00002107 MPI_VALIDATE_RET( X != NULL );
2108 MPI_VALIDATE_RET( A != NULL );
2109 MPI_VALIDATE_RET( N != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00002110
Hanno Becker4bcb4912017-04-18 15:49:39 +01002111 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002112 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002113
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002114 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2115 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2116 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002117
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002118 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002119
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002120 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002121 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002122 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002123 goto cleanup;
2124 }
2125
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002126 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2127 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2128 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2129 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002130
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002131 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2132 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2133 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2134 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002135
2136 do
2137 {
2138 while( ( TU.p[0] & 1 ) == 0 )
2139 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002140 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002141
2142 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2143 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002144 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2145 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002146 }
2147
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002148 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2149 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002150 }
2151
2152 while( ( TV.p[0] & 1 ) == 0 )
2153 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002154 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002155
2156 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2157 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002158 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2159 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002160 }
2161
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002162 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2163 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002164 }
2165
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002166 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002167 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002168 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2169 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2170 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002171 }
2172 else
2173 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002174 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2175 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2176 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002177 }
2178 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002179 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002180
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002181 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2182 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002183
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002184 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2185 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002186
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002187 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002188
2189cleanup:
2190
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002191 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2192 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2193 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002194
2195 return( ret );
2196}
2197
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002198#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00002199
Paul Bakker5121ce52009-01-03 21:22:43 +00002200static const int small_prime[] =
2201{
2202 3, 5, 7, 11, 13, 17, 19, 23,
2203 29, 31, 37, 41, 43, 47, 53, 59,
2204 61, 67, 71, 73, 79, 83, 89, 97,
2205 101, 103, 107, 109, 113, 127, 131, 137,
2206 139, 149, 151, 157, 163, 167, 173, 179,
2207 181, 191, 193, 197, 199, 211, 223, 227,
2208 229, 233, 239, 241, 251, 257, 263, 269,
2209 271, 277, 281, 283, 293, 307, 311, 313,
2210 317, 331, 337, 347, 349, 353, 359, 367,
2211 373, 379, 383, 389, 397, 401, 409, 419,
2212 421, 431, 433, 439, 443, 449, 457, 461,
2213 463, 467, 479, 487, 491, 499, 503, 509,
2214 521, 523, 541, 547, 557, 563, 569, 571,
2215 577, 587, 593, 599, 601, 607, 613, 617,
2216 619, 631, 641, 643, 647, 653, 659, 661,
2217 673, 677, 683, 691, 701, 709, 719, 727,
2218 733, 739, 743, 751, 757, 761, 769, 773,
2219 787, 797, 809, 811, 821, 823, 827, 829,
2220 839, 853, 857, 859, 863, 877, 881, 883,
2221 887, 907, 911, 919, 929, 937, 941, 947,
2222 953, 967, 971, 977, 983, 991, 997, -103
2223};
2224
2225/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002226 * Small divisors test (X must be positive)
2227 *
2228 * Return values:
2229 * 0: no small factor (possible prime, more tests needed)
2230 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002231 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002232 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002233 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002234static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002235{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002236 int ret = 0;
2237 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002238 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002239
Paul Bakker5121ce52009-01-03 21:22:43 +00002240 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002241 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002242
2243 for( i = 0; small_prime[i] > 0; i++ )
2244 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002245 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002246 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002247
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002248 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002249
2250 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002251 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002252 }
2253
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002254cleanup:
2255 return( ret );
2256}
2257
2258/*
2259 * Miller-Rabin pseudo-primality test (HAC 4.24)
2260 */
Janos Follathda31fa12018-09-03 14:45:23 +01002261static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002262 int (*f_rng)(void *, unsigned char *, size_t),
2263 void *p_rng )
2264{
Pascal Junodb99183d2015-03-11 16:49:45 +01002265 int ret, count;
Janos Follathda31fa12018-09-03 14:45:23 +01002266 size_t i, j, k, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002267 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002268
Hanno Becker8ce11a32018-12-19 16:18:52 +00002269 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002270 MPI_VALIDATE_RET( f_rng != NULL );
2271
2272 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2273 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002274 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002275
Paul Bakker5121ce52009-01-03 21:22:43 +00002276 /*
2277 * W = |X| - 1
2278 * R = W >> lsb( W )
2279 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002280 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2281 s = mbedtls_mpi_lsb( &W );
2282 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2283 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002284
Janos Follathda31fa12018-09-03 14:45:23 +01002285 for( i = 0; i < rounds; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002286 {
2287 /*
2288 * pick a random A, 1 < A < |X| - 1
2289 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002290 count = 0;
2291 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002292 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002293
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002294 j = mbedtls_mpi_bitlen( &A );
2295 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002296 if (j > k) {
Darryl Greene3f95ed2018-10-02 13:21:35 +01002297 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Pascal Junodb99183d2015-03-11 16:49:45 +01002298 }
2299
2300 if (count++ > 30) {
Jens Wiklanderf08aa3e2019-01-17 13:30:57 +01002301 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2302 goto cleanup;
Pascal Junodb99183d2015-03-11 16:49:45 +01002303 }
2304
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002305 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2306 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002307
2308 /*
2309 * A = A^R mod |X|
2310 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002311 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002312
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002313 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2314 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002315 continue;
2316
2317 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002318 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002319 {
2320 /*
2321 * A = A * A mod |X|
2322 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002323 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2324 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002325
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002326 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002327 break;
2328
2329 j++;
2330 }
2331
2332 /*
2333 * not prime if A != |X| - 1 or A == 1
2334 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002335 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2336 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002337 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002338 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002339 break;
2340 }
2341 }
2342
2343cleanup:
Hanno Becker73d7d792018-12-11 10:35:51 +00002344 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2345 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002346 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002347
2348 return( ret );
2349}
2350
2351/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002352 * Pseudo-primality test: small factors, then Miller-Rabin
2353 */
Janos Follatha0b67c22018-09-18 14:48:23 +01002354int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2355 int (*f_rng)(void *, unsigned char *, size_t),
2356 void *p_rng )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002357{
Janos Follath24eed8d2019-11-22 13:21:35 +00002358 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002359 mbedtls_mpi XX;
Hanno Becker8ce11a32018-12-19 16:18:52 +00002360 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002361 MPI_VALIDATE_RET( f_rng != NULL );
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002362
2363 XX.s = 1;
2364 XX.n = X->n;
2365 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002366
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002367 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2368 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2369 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002370
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002371 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002372 return( 0 );
2373
2374 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2375 {
2376 if( ret == 1 )
2377 return( 0 );
2378
2379 return( ret );
2380 }
2381
Janos Follathda31fa12018-09-03 14:45:23 +01002382 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
Janos Follathf301d232018-08-14 13:34:01 +01002383}
2384
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002385/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002386 * Prime number generation
Jethro Beekman66689272018-02-14 19:24:10 -08002387 *
Janos Follathf301d232018-08-14 13:34:01 +01002388 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2389 * be either 1024 bits or 1536 bits long, and flags must contain
2390 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Paul Bakker5121ce52009-01-03 21:22:43 +00002391 */
Janos Follath7c025a92018-08-14 11:08:41 +01002392int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002393 int (*f_rng)(void *, unsigned char *, size_t),
2394 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002395{
Jethro Beekman66689272018-02-14 19:24:10 -08002396#ifdef MBEDTLS_HAVE_INT64
2397// ceil(2^63.5)
2398#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2399#else
2400// ceil(2^31.5)
2401#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2402#endif
2403 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker23986e52011-04-24 08:57:21 +00002404 size_t k, n;
Janos Follathda31fa12018-09-03 14:45:23 +01002405 int rounds;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002406 mbedtls_mpi_uint r;
2407 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002408
Hanno Becker8ce11a32018-12-19 16:18:52 +00002409 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002410 MPI_VALIDATE_RET( f_rng != NULL );
2411
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002412 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2413 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002414
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002415 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002416
2417 n = BITS_TO_LIMBS( nbits );
2418
Janos Follathda31fa12018-09-03 14:45:23 +01002419 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2420 {
2421 /*
2422 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2423 */
2424 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2425 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2426 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2427 }
2428 else
2429 {
2430 /*
2431 * 2^-100 error probability, number of rounds computed based on HAC,
2432 * fact 4.48
2433 */
2434 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2435 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2436 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2437 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2438 }
2439
Jethro Beekman66689272018-02-14 19:24:10 -08002440 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002441 {
Jethro Beekman66689272018-02-14 19:24:10 -08002442 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2443 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2444 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2445
2446 k = n * biL;
2447 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2448 X->p[0] |= 1;
2449
Janos Follath7c025a92018-08-14 11:08:41 +01002450 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002451 {
Janos Follatha0b67c22018-09-18 14:48:23 +01002452 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
Jethro Beekman66689272018-02-14 19:24:10 -08002453
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002454 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002455 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002456 }
Jethro Beekman66689272018-02-14 19:24:10 -08002457 else
Paul Bakker5121ce52009-01-03 21:22:43 +00002458 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002459 /*
Tom Cosgrovece7f18c2022-07-28 05:50:56 +01002460 * A necessary condition for Y and X = 2Y + 1 to be prime
Jethro Beekman66689272018-02-14 19:24:10 -08002461 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2462 * Make sure it is satisfied, while keeping X = 3 mod 4
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002463 */
Jethro Beekman66689272018-02-14 19:24:10 -08002464
2465 X->p[0] |= 2;
2466
2467 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2468 if( r == 0 )
2469 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2470 else if( r == 1 )
2471 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2472
2473 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2474 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2475 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2476
2477 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002478 {
Jethro Beekman66689272018-02-14 19:24:10 -08002479 /*
2480 * First, check small factors for X and Y
2481 * before doing Miller-Rabin on any of them
2482 */
2483 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2484 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002485 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002486 == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002487 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002488 == 0 )
Jethro Beekman66689272018-02-14 19:24:10 -08002489 goto cleanup;
2490
2491 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2492 goto cleanup;
2493
2494 /*
2495 * Next candidates. We want to preserve Y = (X-1) / 2 and
2496 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2497 * so up Y by 6 and X by 12.
2498 */
2499 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2500 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002501 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002502 }
2503 }
2504
2505cleanup:
2506
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002507 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002508
2509 return( ret );
2510}
2511
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002512#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002513
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002514#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002515
Paul Bakker23986e52011-04-24 08:57:21 +00002516#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002517
2518static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2519{
2520 { 693, 609, 21 },
2521 { 1764, 868, 28 },
2522 { 768454923, 542167814, 1 }
2523};
2524
Paul Bakker5121ce52009-01-03 21:22:43 +00002525/*
2526 * Checkup routine
2527 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002528int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002529{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002530 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002531 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002532
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002533 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2534 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002535
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002536 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002537 "EFE021C2645FD1DC586E69184AF4A31E" \
2538 "D5F53E93B5F123FA41680867BA110131" \
2539 "944FE7952E2517337780CB0DB80E61AA" \
2540 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2541
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002542 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002543 "B2E7EFD37075B9F03FF989C7C5051C20" \
2544 "34D2A323810251127E7BF8625A4F49A5" \
2545 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2546 "5B5C25763222FEFCCFC38B832366C29E" ) );
2547
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002548 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002549 "0066A198186C18C10B2F5ED9B522752A" \
2550 "9830B69916E535C8F047518A889A43A5" \
2551 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2552
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002553 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002554
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002555 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002556 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2557 "9E857EA95A03512E2BAE7391688D264A" \
2558 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2559 "8001B72E848A38CAE1C65F78E56ABDEF" \
2560 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2561 "ECF677152EF804370C1A305CAF3B5BF1" \
2562 "30879B56C61DE584A0F53A2447A51E" ) );
2563
2564 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002565 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002566
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002567 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002568 {
2569 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002570 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002571
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002572 ret = 1;
2573 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002574 }
2575
2576 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002577 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002578
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002579 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002580
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002581 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002582 "256567336059E52CAE22925474705F39A94" ) );
2583
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002584 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002585 "6613F26162223DF488E9CD48CC132C7A" \
2586 "0AC93C701B001B092E4E5B9F73BCD27B" \
2587 "9EE50D0657C77F374E903CDFA4C642" ) );
2588
2589 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002590 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002591
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002592 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2593 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002594 {
2595 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002596 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002597
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002598 ret = 1;
2599 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002600 }
2601
2602 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002603 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002604
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002605 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002606
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002607 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002608 "36E139AEA55215609D2816998ED020BB" \
2609 "BD96C37890F65171D948E9BC7CBAA4D9" \
2610 "325D24D6A3C12710F10A09FA08AB87" ) );
2611
2612 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002613 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002614
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002615 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002616 {
2617 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002618 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002619
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002620 ret = 1;
2621 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002622 }
2623
2624 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002625 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002626
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002627 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002628
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002629 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002630 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2631 "C3DBA76456363A10869622EAC2DD84EC" \
2632 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2633
2634 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002635 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002636
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002637 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002638 {
2639 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002640 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002641
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002642 ret = 1;
2643 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002644 }
2645
2646 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002647 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002648
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002649 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002650 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002651
Paul Bakker66d5d072014-06-17 16:39:18 +02002652 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002653 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002654 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2655 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002656
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002657 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002658
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002659 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002660 {
2661 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002662 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002663
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002664 ret = 1;
2665 goto cleanup;
2666 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002667 }
2668
2669 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002670 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002671
Paul Bakker5121ce52009-01-03 21:22:43 +00002672cleanup:
2673
2674 if( ret != 0 && verbose != 0 )
Kenneth Soerensen518d4352020-04-01 17:22:45 +02002675 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002676
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002677 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2678 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002679
2680 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002681 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002682
2683 return( ret );
2684}
2685
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002686#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002687
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002688#endif /* MBEDTLS_BIGNUM_C */