blob: dbf5295052868006ac723fed789850fae7150ca1 [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"
Hanno Beckeraef9cc42022-04-11 06:36:29 +010041#include "bignum_internal.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é-Gonnard2cf5a7c2015-04-08 12:49:31 +020050#if defined(MBEDTLS_PLATFORM_C)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000051#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020052#else
Rich Evans00ab4702015-02-06 13:43:58 +000053#include <stdio.h>
54#include <stdlib.h>
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020055#define mbedtls_printf printf
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +020056#define mbedtls_calloc calloc
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020057#define mbedtls_free free
Paul Bakker6e339b52013-07-03 13:37:05 +020058#endif
59
Hanno Becker73d7d792018-12-11 10:35:51 +000060#define MPI_VALIDATE_RET( cond ) \
61 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
62#define MPI_VALIDATE( cond ) \
63 MBEDTLS_INTERNAL_VALIDATE( cond )
64
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020065#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
Paul Bakker5121ce52009-01-03 21:22:43 +000066#define biL (ciL << 3) /* bits in limb */
67#define biH (ciL << 2) /* half limb size */
68
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +010069#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
70
Paul Bakker5121ce52009-01-03 21:22:43 +000071/*
72 * Convert between bits/chars and number of limbs
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020073 * Divide first in order to avoid potential overflows
Paul Bakker5121ce52009-01-03 21:22:43 +000074 */
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020075#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
76#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
Paul Bakker5121ce52009-01-03 21:22:43 +000077
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050078/* Implementation that should never be optimized out by the compiler */
Andres Amaya Garcia6698d2f2018-04-24 08:39:07 -050079static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
80{
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050081 mbedtls_platform_zeroize( v, ciL * n );
82}
83
Paul Bakker5121ce52009-01-03 21:22:43 +000084/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000085 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000086 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020087void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000088{
Hanno Becker73d7d792018-12-11 10:35:51 +000089 MPI_VALIDATE( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +000090
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/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000097 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000098 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020099void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000100{
Paul Bakker6c591fa2011-05-05 11:49:20 +0000101 if( X == NULL )
102 return;
Paul Bakker5121ce52009-01-03 21:22:43 +0000103
Paul Bakker6c591fa2011-05-05 11:49:20 +0000104 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +0000105 {
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200106 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200107 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000108 }
109
Paul Bakker6c591fa2011-05-05 11:49:20 +0000110 X->s = 1;
111 X->n = 0;
112 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000113}
114
115/*
116 * Enlarge to the specified number of limbs
117 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200118int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000119{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200120 mbedtls_mpi_uint *p;
Hanno Becker73d7d792018-12-11 10:35:51 +0000121 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000122
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200123 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200124 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000125
Paul Bakker5121ce52009-01-03 21:22:43 +0000126 if( X->n < nblimbs )
127 {
Simon Butcher29176892016-05-20 00:19:09 +0100128 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200129 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000130
Paul Bakker5121ce52009-01-03 21:22:43 +0000131 if( X->p != NULL )
132 {
133 memcpy( p, X->p, X->n * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200134 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200135 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000136 }
137
138 X->n = nblimbs;
139 X->p = p;
140 }
141
142 return( 0 );
143}
144
145/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100146 * Resize down as much as possible,
147 * while keeping at least the specified number of limbs
148 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200149int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100150{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200151 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100152 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000153 MPI_VALIDATE_RET( X != NULL );
154
155 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
156 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100157
Gilles Peskinee2f563e2020-01-20 21:17:43 +0100158 /* Actually resize up if there are currently fewer than nblimbs limbs. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100159 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200160 return( mbedtls_mpi_grow( X, nblimbs ) );
Gilles Peskine322752b2020-01-21 13:59:51 +0100161 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100162
163 for( i = X->n - 1; i > 0; i-- )
164 if( X->p[i] != 0 )
165 break;
166 i++;
167
168 if( i < nblimbs )
169 i = nblimbs;
170
Simon Butcher29176892016-05-20 00:19:09 +0100171 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200172 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100173
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100174 if( X->p != NULL )
175 {
176 memcpy( p, X->p, i * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200177 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200178 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100179 }
180
181 X->n = i;
182 X->p = p;
183
184 return( 0 );
185}
186
Gilles Peskineed32b572021-06-02 22:17:52 +0200187/* Resize X to have exactly n limbs and set it to 0. */
188static int mbedtls_mpi_resize_clear( mbedtls_mpi *X, size_t limbs )
189{
190 if( limbs == 0 )
191 {
192 mbedtls_mpi_free( X );
193 return( 0 );
194 }
195 else if( X->n == limbs )
196 {
197 memset( X->p, 0, limbs * ciL );
198 X->s = 1;
199 return( 0 );
200 }
201 else
202 {
203 mbedtls_mpi_free( X );
204 return( mbedtls_mpi_grow( X, limbs ) );
205 }
206}
207
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100208/*
Gilles Peskine3da1a8f2021-06-08 23:17:42 +0200209 * Copy the contents of Y into X.
210 *
211 * This function is not constant-time. Leading zeros in Y may be removed.
212 *
213 * Ensure that X does not shrink. This is not guaranteed by the public API,
214 * but some code in the bignum module relies on this property, for example
215 * in mbedtls_mpi_exp_mod().
Paul Bakker5121ce52009-01-03 21:22:43 +0000216 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200217int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000218{
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100219 int ret = 0;
Paul Bakker23986e52011-04-24 08:57:21 +0000220 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000221 MPI_VALIDATE_RET( X != NULL );
222 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000223
224 if( X == Y )
225 return( 0 );
226
Gilles Peskinedb420622020-01-20 21:12:50 +0100227 if( Y->n == 0 )
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200228 {
Gilles Peskine3da1a8f2021-06-08 23:17:42 +0200229 if( X->n != 0 )
230 {
231 X->s = 1;
232 memset( X->p, 0, X->n * ciL );
233 }
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200234 return( 0 );
235 }
236
Paul Bakker5121ce52009-01-03 21:22:43 +0000237 for( i = Y->n - 1; i > 0; i-- )
238 if( Y->p[i] != 0 )
239 break;
240 i++;
241
242 X->s = Y->s;
243
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100244 if( X->n < i )
245 {
246 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
247 }
248 else
249 {
250 memset( X->p + i, 0, ( X->n - i ) * ciL );
251 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000252
Paul Bakker5121ce52009-01-03 21:22:43 +0000253 memcpy( X->p, Y->p, i * ciL );
254
255cleanup:
256
257 return( ret );
258}
259
260/*
261 * Swap the contents of X and Y
262 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200263void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000264{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200265 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000266 MPI_VALIDATE( X != NULL );
267 MPI_VALIDATE( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000268
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200269 memcpy( &T, X, sizeof( mbedtls_mpi ) );
270 memcpy( X, Y, sizeof( mbedtls_mpi ) );
271 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000272}
273
274/*
275 * Set value from integer
276 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200277int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000278{
Janos Follath24eed8d2019-11-22 13:21:35 +0000279 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +0000280 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000281
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200282 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000283 memset( X->p, 0, X->n * ciL );
284
285 X->p[0] = ( z < 0 ) ? -z : z;
286 X->s = ( z < 0 ) ? -1 : 1;
287
288cleanup:
289
290 return( ret );
291}
292
293/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000294 * Get a specific bit
295 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200296int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000297{
Hanno Becker73d7d792018-12-11 10:35:51 +0000298 MPI_VALIDATE_RET( X != NULL );
299
Paul Bakker2f5947e2011-05-18 15:47:11 +0000300 if( X->n * biL <= pos )
301 return( 0 );
302
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200303 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000304}
305
Gilles Peskine11cdb052018-11-20 16:47:47 +0100306/* Get a specific byte, without range checks. */
307#define GET_BYTE( X, i ) \
308 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
309
Paul Bakker2f5947e2011-05-18 15:47:11 +0000310/*
311 * Set a bit to a specific value of 0 or 1
312 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200313int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000314{
315 int ret = 0;
316 size_t off = pos / biL;
317 size_t idx = pos % biL;
Hanno Becker73d7d792018-12-11 10:35:51 +0000318 MPI_VALIDATE_RET( X != NULL );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000319
320 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200321 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200322
Paul Bakker2f5947e2011-05-18 15:47:11 +0000323 if( X->n * biL <= pos )
324 {
325 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200326 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000327
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200328 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000329 }
330
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200331 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
332 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000333
334cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200335
Paul Bakker2f5947e2011-05-18 15:47:11 +0000336 return( ret );
337}
338
339/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200340 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000341 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200342size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000343{
Paul Bakker23986e52011-04-24 08:57:21 +0000344 size_t i, j, count = 0;
Hanno Beckerf25ee7f2018-12-19 16:51:02 +0000345 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000346
347 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000348 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000349 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
350 return( count );
351
352 return( 0 );
353}
354
355/*
Simon Butcher15b15d12015-11-26 19:35:03 +0000356 * Count leading zero bits in a given integer
357 */
358static size_t mbedtls_clz( const mbedtls_mpi_uint x )
359{
360 size_t j;
Manuel Pégourié-Gonnarde3e8edf2015-12-01 09:31:52 +0100361 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
Simon Butcher15b15d12015-11-26 19:35:03 +0000362
363 for( j = 0; j < biL; j++ )
364 {
365 if( x & mask ) break;
366
367 mask >>= 1;
368 }
369
370 return j;
371}
372
373/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200374 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000375 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200376size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000377{
Paul Bakker23986e52011-04-24 08:57:21 +0000378 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000379
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200380 if( X->n == 0 )
381 return( 0 );
382
Paul Bakker5121ce52009-01-03 21:22:43 +0000383 for( i = X->n - 1; i > 0; i-- )
384 if( X->p[i] != 0 )
385 break;
386
Simon Butcher15b15d12015-11-26 19:35:03 +0000387 j = biL - mbedtls_clz( X->p[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +0000388
Paul Bakker23986e52011-04-24 08:57:21 +0000389 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000390}
391
392/*
393 * Return the total size in bytes
394 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200395size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000396{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200397 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000398}
399
400/*
401 * Convert an ASCII character to digit value
402 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200403static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000404{
405 *d = 255;
406
407 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
408 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
409 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
410
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200411 if( *d >= (mbedtls_mpi_uint) radix )
412 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000413
414 return( 0 );
415}
416
417/*
418 * Import from an ASCII string
419 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200420int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000421{
Janos Follath24eed8d2019-11-22 13:21:35 +0000422 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000423 size_t i, j, slen, n;
Gilles Peskine80f56732021-04-03 18:26:13 +0200424 int sign = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200425 mbedtls_mpi_uint d;
426 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000427 MPI_VALIDATE_RET( X != NULL );
428 MPI_VALIDATE_RET( s != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000429
430 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000431 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000432
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200433 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000434
Gilles Peskine7cba8592021-06-08 18:32:34 +0200435 if( s[0] == 0 )
436 {
437 mbedtls_mpi_free( X );
438 return( 0 );
439 }
440
Gilles Peskine80f56732021-04-03 18:26:13 +0200441 if( s[0] == '-' )
442 {
443 ++s;
444 sign = -1;
445 }
446
Paul Bakkerff60ee62010-03-16 21:09:09 +0000447 slen = strlen( s );
448
Paul Bakker5121ce52009-01-03 21:22:43 +0000449 if( radix == 16 )
450 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100451 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200452 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
453
Paul Bakkerff60ee62010-03-16 21:09:09 +0000454 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000455
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200456 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
457 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000458
Paul Bakker23986e52011-04-24 08:57:21 +0000459 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000460 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200461 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200462 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000463 }
464 }
465 else
466 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200467 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000468
Paul Bakkerff60ee62010-03-16 21:09:09 +0000469 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000470 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200471 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
472 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Gilles Peskine80f56732021-04-03 18:26:13 +0200473 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000474 }
475 }
476
Gilles Peskine80f56732021-04-03 18:26:13 +0200477 if( sign < 0 && mbedtls_mpi_bitlen( X ) != 0 )
478 X->s = -1;
479
Paul Bakker5121ce52009-01-03 21:22:43 +0000480cleanup:
481
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200482 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000483
484 return( ret );
485}
486
487/*
Ron Eldora16fa292018-11-20 14:07:01 +0200488 * Helper to write the digits high-order first.
Paul Bakker5121ce52009-01-03 21:22:43 +0000489 */
Ron Eldora16fa292018-11-20 14:07:01 +0200490static int mpi_write_hlp( mbedtls_mpi *X, int radix,
491 char **p, const size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000492{
Janos Follath24eed8d2019-11-22 13:21:35 +0000493 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200494 mbedtls_mpi_uint r;
Ron Eldora16fa292018-11-20 14:07:01 +0200495 size_t length = 0;
496 char *p_end = *p + buflen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000497
Ron Eldora16fa292018-11-20 14:07:01 +0200498 do
499 {
500 if( length >= buflen )
501 {
502 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
503 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000504
Ron Eldora16fa292018-11-20 14:07:01 +0200505 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
506 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
507 /*
508 * Write the residue in the current position, as an ASCII character.
509 */
510 if( r < 0xA )
511 *(--p_end) = (char)( '0' + r );
512 else
513 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000514
Ron Eldora16fa292018-11-20 14:07:01 +0200515 length++;
516 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000517
Ron Eldora16fa292018-11-20 14:07:01 +0200518 memmove( *p, p_end, length );
519 *p += length;
Paul Bakker5121ce52009-01-03 21:22:43 +0000520
521cleanup:
522
523 return( ret );
524}
525
526/*
527 * Export into an ASCII string
528 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100529int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
530 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000531{
Paul Bakker23986e52011-04-24 08:57:21 +0000532 int ret = 0;
533 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000534 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200535 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000536 MPI_VALIDATE_RET( X != NULL );
537 MPI_VALIDATE_RET( olen != NULL );
538 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000539
540 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000541 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000542
Hanno Becker23cfea02019-02-04 09:45:07 +0000543 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
544 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
545 * `n`. If radix > 4, this might be a strict
546 * overapproximation of the number of
547 * radix-adic digits needed to present `n`. */
548 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
549 * present `n`. */
550
Janos Follath80470622019-03-06 13:43:02 +0000551 n += 1; /* Terminating null byte */
Hanno Becker23cfea02019-02-04 09:45:07 +0000552 n += 1; /* Compensate for the divisions above, which round down `n`
553 * in case it's not even. */
554 n += 1; /* Potential '-'-sign. */
555 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
556 * which always uses an even number of hex-digits. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000557
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100558 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000559 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100560 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200561 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000562 }
563
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100564 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200565 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000566
567 if( X->s == -1 )
Hanno Beckerc983c812019-02-01 16:41:30 +0000568 {
Paul Bakker5121ce52009-01-03 21:22:43 +0000569 *p++ = '-';
Hanno Beckerc983c812019-02-01 16:41:30 +0000570 buflen--;
571 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000572
573 if( radix == 16 )
574 {
Paul Bakker23986e52011-04-24 08:57:21 +0000575 int c;
576 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000577
Paul Bakker23986e52011-04-24 08:57:21 +0000578 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000579 {
Paul Bakker23986e52011-04-24 08:57:21 +0000580 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000581 {
Paul Bakker23986e52011-04-24 08:57:21 +0000582 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000583
Paul Bakker6c343d72014-07-10 14:36:19 +0200584 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000585 continue;
586
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000587 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000588 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000589 k = 1;
590 }
591 }
592 }
593 else
594 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200595 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000596
597 if( T.s == -1 )
598 T.s = 1;
599
Ron Eldora16fa292018-11-20 14:07:01 +0200600 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000601 }
602
603 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100604 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000605
606cleanup:
607
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200608 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000609
610 return( ret );
611}
612
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200613#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000614/*
615 * Read X from an opened file
616 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200617int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000618{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200619 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000620 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000621 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000622 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000623 * Buffer should have space for (short) label and decimal formatted MPI,
624 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000625 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200626 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000627
Hanno Becker73d7d792018-12-11 10:35:51 +0000628 MPI_VALIDATE_RET( X != NULL );
629 MPI_VALIDATE_RET( fin != NULL );
630
631 if( radix < 2 || radix > 16 )
632 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
633
Paul Bakker5121ce52009-01-03 21:22:43 +0000634 memset( s, 0, sizeof( s ) );
635 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200636 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000637
638 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000639 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200640 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000641
Hanno Beckerb2034b72017-04-26 11:46:46 +0100642 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
643 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000644
645 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100646 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000647 if( mpi_get_digit( &d, radix, *p ) != 0 )
648 break;
649
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200650 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000651}
652
653/*
654 * Write X into an opened file (or stdout if fout == NULL)
655 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200656int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000657{
Janos Follath24eed8d2019-11-22 13:21:35 +0000658 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000659 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000660 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000661 * Buffer should have space for (short) label and decimal formatted MPI,
662 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000663 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200664 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Hanno Becker73d7d792018-12-11 10:35:51 +0000665 MPI_VALIDATE_RET( X != NULL );
666
667 if( radix < 2 || radix > 16 )
668 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000669
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100670 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000671
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100672 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000673
674 if( p == NULL ) p = "";
675
676 plen = strlen( p );
677 slen = strlen( s );
678 s[slen++] = '\r';
679 s[slen++] = '\n';
680
681 if( fout != NULL )
682 {
683 if( fwrite( p, 1, plen, fout ) != plen ||
684 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200685 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000686 }
687 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200688 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000689
690cleanup:
691
692 return( ret );
693}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200694#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000695
Hanno Beckerda1655a2017-10-18 14:21:44 +0100696
697/* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
698 * into the storage form used by mbedtls_mpi. */
Hanno Beckerf8720072018-11-08 11:53:49 +0000699
700static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x )
701{
702 uint8_t i;
Hanno Becker031d6332019-05-01 17:09:11 +0100703 unsigned char *x_ptr;
Hanno Beckerf8720072018-11-08 11:53:49 +0000704 mbedtls_mpi_uint tmp = 0;
Hanno Becker031d6332019-05-01 17:09:11 +0100705
706 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ )
707 {
708 tmp <<= CHAR_BIT;
709 tmp |= (mbedtls_mpi_uint) *x_ptr;
710 }
711
Hanno Beckerf8720072018-11-08 11:53:49 +0000712 return( tmp );
713}
714
715static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x )
716{
717#if defined(__BYTE_ORDER__)
718
719/* Nothing to do on bigendian systems. */
720#if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ )
721 return( x );
722#endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
723
724#if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ )
725
726/* For GCC and Clang, have builtins for byte swapping. */
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000727#if defined(__GNUC__) && defined(__GNUC_PREREQ)
728#if __GNUC_PREREQ(4,3)
Hanno Beckerf8720072018-11-08 11:53:49 +0000729#define have_bswap
730#endif
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000731#endif
732
733#if defined(__clang__) && defined(__has_builtin)
734#if __has_builtin(__builtin_bswap32) && \
735 __has_builtin(__builtin_bswap64)
736#define have_bswap
737#endif
738#endif
739
Hanno Beckerf8720072018-11-08 11:53:49 +0000740#if defined(have_bswap)
741 /* The compiler is hopefully able to statically evaluate this! */
742 switch( sizeof(mbedtls_mpi_uint) )
743 {
744 case 4:
745 return( __builtin_bswap32(x) );
746 case 8:
747 return( __builtin_bswap64(x) );
748 }
749#endif
750#endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */
751#endif /* __BYTE_ORDER__ */
752
753 /* Fall back to C-based reordering if we don't know the byte order
754 * or we couldn't use a compiler-specific builtin. */
755 return( mpi_uint_bigendian_to_host_c( x ) );
756}
757
Hanno Becker2be8a552018-10-25 12:40:09 +0100758static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs )
Hanno Beckerda1655a2017-10-18 14:21:44 +0100759{
Hanno Beckerda1655a2017-10-18 14:21:44 +0100760 mbedtls_mpi_uint *cur_limb_left;
761 mbedtls_mpi_uint *cur_limb_right;
Hanno Becker2be8a552018-10-25 12:40:09 +0100762 if( limbs == 0 )
763 return;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100764
765 /*
766 * Traverse limbs and
767 * - adapt byte-order in each limb
768 * - swap the limbs themselves.
769 * For that, simultaneously traverse the limbs from left to right
770 * and from right to left, as long as the left index is not bigger
771 * than the right index (it's not a problem if limbs is odd and the
772 * indices coincide in the last iteration).
773 */
Hanno Beckerda1655a2017-10-18 14:21:44 +0100774 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 );
775 cur_limb_left <= cur_limb_right;
776 cur_limb_left++, cur_limb_right-- )
777 {
Hanno Beckerf8720072018-11-08 11:53:49 +0000778 mbedtls_mpi_uint tmp;
779 /* Note that if cur_limb_left == cur_limb_right,
780 * this code effectively swaps the bytes only once. */
781 tmp = mpi_uint_bigendian_to_host( *cur_limb_left );
782 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right );
783 *cur_limb_right = tmp;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100784 }
Hanno Beckerda1655a2017-10-18 14:21:44 +0100785}
786
Paul Bakker5121ce52009-01-03 21:22:43 +0000787/*
Janos Follatha778a942019-02-13 10:28:28 +0000788 * Import X from unsigned binary data, little endian
Przemyslaw Stekiel76960a72022-02-21 13:42:09 +0100789 *
790 * This function is guaranteed to return an MPI with exactly the necessary
791 * number of limbs (in particular, it does not skip 0s in the input).
Janos Follatha778a942019-02-13 10:28:28 +0000792 */
793int mbedtls_mpi_read_binary_le( mbedtls_mpi *X,
794 const unsigned char *buf, size_t buflen )
795{
Janos Follath24eed8d2019-11-22 13:21:35 +0000796 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follatha778a942019-02-13 10:28:28 +0000797 size_t i;
798 size_t const limbs = CHARS_TO_LIMBS( buflen );
799
800 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +0200801 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Janos Follatha778a942019-02-13 10:28:28 +0000802
803 for( i = 0; i < buflen; i++ )
804 X->p[i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3);
805
806cleanup:
807
Janos Follath171a7ef2019-02-15 16:17:45 +0000808 /*
809 * This function is also used to import keys. However, wiping the buffers
810 * upon failure is not necessary because failure only can happen before any
811 * input is copied.
812 */
Janos Follatha778a942019-02-13 10:28:28 +0000813 return( ret );
814}
815
816/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000817 * Import X from unsigned binary data, big endian
Przemyslaw Stekiel76960a72022-02-21 13:42:09 +0100818 *
819 * This function is guaranteed to return an MPI with exactly the necessary
820 * number of limbs (in particular, it does not skip 0s in the input).
Paul Bakker5121ce52009-01-03 21:22:43 +0000821 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200822int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000823{
Janos Follath24eed8d2019-11-22 13:21:35 +0000824 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100825 size_t const limbs = CHARS_TO_LIMBS( buflen );
826 size_t const overhead = ( limbs * ciL ) - buflen;
827 unsigned char *Xp;
Paul Bakker5121ce52009-01-03 21:22:43 +0000828
Hanno Becker8ce11a32018-12-19 16:18:52 +0000829 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +0000830 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
831
Hanno Becker073c1992017-10-17 15:17:27 +0100832 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +0200833 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000834
Gilles Peskineed32b572021-06-02 22:17:52 +0200835 /* Avoid calling `memcpy` with NULL source or destination argument,
Hanno Becker0e810b92019-01-03 17:13:11 +0000836 * even if buflen is 0. */
Gilles Peskineed32b572021-06-02 22:17:52 +0200837 if( buflen != 0 )
Hanno Becker0e810b92019-01-03 17:13:11 +0000838 {
839 Xp = (unsigned char*) X->p;
840 memcpy( Xp + overhead, buf, buflen );
Hanno Beckerda1655a2017-10-18 14:21:44 +0100841
Hanno Becker0e810b92019-01-03 17:13:11 +0000842 mpi_bigendian_to_host( X->p, limbs );
843 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000844
845cleanup:
846
Janos Follath171a7ef2019-02-15 16:17:45 +0000847 /*
848 * This function is also used to import keys. However, wiping the buffers
849 * upon failure is not necessary because failure only can happen before any
850 * input is copied.
851 */
Paul Bakker5121ce52009-01-03 21:22:43 +0000852 return( ret );
853}
854
855/*
Janos Follathe344d0f2019-02-19 16:17:40 +0000856 * Export X into unsigned binary data, little endian
857 */
858int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X,
859 unsigned char *buf, size_t buflen )
860{
861 size_t stored_bytes = X->n * ciL;
862 size_t bytes_to_copy;
863 size_t i;
864
865 if( stored_bytes < buflen )
866 {
867 bytes_to_copy = stored_bytes;
868 }
869 else
870 {
871 bytes_to_copy = buflen;
872
873 /* The output buffer is smaller than the allocated size of X.
874 * However X may fit if its leading bytes are zero. */
875 for( i = bytes_to_copy; i < stored_bytes; i++ )
876 {
877 if( GET_BYTE( X, i ) != 0 )
878 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
879 }
880 }
881
882 for( i = 0; i < bytes_to_copy; i++ )
883 buf[i] = GET_BYTE( X, i );
884
885 if( stored_bytes < buflen )
886 {
887 /* Write trailing 0 bytes */
888 memset( buf + stored_bytes, 0, buflen - stored_bytes );
889 }
890
891 return( 0 );
892}
893
894/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000895 * Export X into unsigned binary data, big endian
896 */
Gilles Peskine11cdb052018-11-20 16:47:47 +0100897int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
898 unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000899{
Hanno Becker73d7d792018-12-11 10:35:51 +0000900 size_t stored_bytes;
Gilles Peskine11cdb052018-11-20 16:47:47 +0100901 size_t bytes_to_copy;
902 unsigned char *p;
903 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000904
Hanno Becker73d7d792018-12-11 10:35:51 +0000905 MPI_VALIDATE_RET( X != NULL );
906 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
907
908 stored_bytes = X->n * ciL;
909
Gilles Peskine11cdb052018-11-20 16:47:47 +0100910 if( stored_bytes < buflen )
911 {
912 /* There is enough space in the output buffer. Write initial
913 * null bytes and record the position at which to start
914 * writing the significant bytes. In this case, the execution
915 * trace of this function does not depend on the value of the
916 * number. */
917 bytes_to_copy = stored_bytes;
918 p = buf + buflen - stored_bytes;
919 memset( buf, 0, buflen - stored_bytes );
920 }
921 else
922 {
923 /* The output buffer is smaller than the allocated size of X.
924 * However X may fit if its leading bytes are zero. */
925 bytes_to_copy = buflen;
926 p = buf;
927 for( i = bytes_to_copy; i < stored_bytes; i++ )
928 {
929 if( GET_BYTE( X, i ) != 0 )
930 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
931 }
932 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000933
Gilles Peskine11cdb052018-11-20 16:47:47 +0100934 for( i = 0; i < bytes_to_copy; i++ )
935 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
Paul Bakker5121ce52009-01-03 21:22:43 +0000936
937 return( 0 );
938}
939
940/*
941 * Left-shift: X <<= count
942 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200943int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000944{
Janos Follath24eed8d2019-11-22 13:21:35 +0000945 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000946 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200947 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000948 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000949
950 v0 = count / (biL );
951 t1 = count & (biL - 1);
952
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200953 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000954
Paul Bakkerf9688572011-05-05 10:00:45 +0000955 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200956 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000957
958 ret = 0;
959
960 /*
961 * shift by count / limb_size
962 */
963 if( v0 > 0 )
964 {
Paul Bakker23986e52011-04-24 08:57:21 +0000965 for( i = X->n; i > v0; i-- )
966 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000967
Paul Bakker23986e52011-04-24 08:57:21 +0000968 for( ; i > 0; i-- )
969 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000970 }
971
972 /*
973 * shift by count % limb_size
974 */
975 if( t1 > 0 )
976 {
977 for( i = v0; i < X->n; i++ )
978 {
979 r1 = X->p[i] >> (biL - t1);
980 X->p[i] <<= t1;
981 X->p[i] |= r0;
982 r0 = r1;
983 }
984 }
985
986cleanup:
987
988 return( ret );
989}
990
991/*
992 * Right-shift: X >>= count
993 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200994int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000995{
Paul Bakker23986e52011-04-24 08:57:21 +0000996 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200997 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000998 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000999
1000 v0 = count / biL;
1001 v1 = count & (biL - 1);
1002
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +01001003 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001004 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +01001005
Paul Bakker5121ce52009-01-03 21:22:43 +00001006 /*
1007 * shift by count / limb_size
1008 */
1009 if( v0 > 0 )
1010 {
1011 for( i = 0; i < X->n - v0; i++ )
1012 X->p[i] = X->p[i + v0];
1013
1014 for( ; i < X->n; i++ )
1015 X->p[i] = 0;
1016 }
1017
1018 /*
1019 * shift by count % limb_size
1020 */
1021 if( v1 > 0 )
1022 {
Paul Bakker23986e52011-04-24 08:57:21 +00001023 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001024 {
Paul Bakker23986e52011-04-24 08:57:21 +00001025 r1 = X->p[i - 1] << (biL - v1);
1026 X->p[i - 1] >>= v1;
1027 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001028 r0 = r1;
1029 }
1030 }
1031
1032 return( 0 );
1033}
1034
1035/*
1036 * Compare unsigned values
1037 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001038int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001039{
Paul Bakker23986e52011-04-24 08:57:21 +00001040 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001041 MPI_VALIDATE_RET( X != NULL );
1042 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001043
Paul Bakker23986e52011-04-24 08:57:21 +00001044 for( i = X->n; i > 0; i-- )
1045 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001046 break;
1047
Paul Bakker23986e52011-04-24 08:57:21 +00001048 for( j = Y->n; j > 0; j-- )
1049 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001050 break;
1051
Paul Bakker23986e52011-04-24 08:57:21 +00001052 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001053 return( 0 );
1054
1055 if( i > j ) return( 1 );
1056 if( j > i ) return( -1 );
1057
Paul Bakker23986e52011-04-24 08:57:21 +00001058 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001059 {
Paul Bakker23986e52011-04-24 08:57:21 +00001060 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
1061 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001062 }
1063
1064 return( 0 );
1065}
1066
1067/*
1068 * Compare signed values
1069 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001070int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001071{
Paul Bakker23986e52011-04-24 08:57:21 +00001072 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001073 MPI_VALIDATE_RET( X != NULL );
1074 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001075
Paul Bakker23986e52011-04-24 08:57:21 +00001076 for( i = X->n; i > 0; i-- )
1077 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001078 break;
1079
Paul Bakker23986e52011-04-24 08:57:21 +00001080 for( j = Y->n; j > 0; j-- )
1081 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001082 break;
1083
Paul Bakker23986e52011-04-24 08:57:21 +00001084 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001085 return( 0 );
1086
1087 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +00001088 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001089
1090 if( X->s > 0 && Y->s < 0 ) return( 1 );
1091 if( Y->s > 0 && X->s < 0 ) return( -1 );
1092
Paul Bakker23986e52011-04-24 08:57:21 +00001093 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001094 {
Paul Bakker23986e52011-04-24 08:57:21 +00001095 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
1096 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001097 }
1098
1099 return( 0 );
1100}
1101
Janos Follathee6abce2019-09-05 14:47:19 +01001102/*
Paul Bakker5121ce52009-01-03 21:22:43 +00001103 * Compare signed values
1104 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001105int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +00001106{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001107 mbedtls_mpi Y;
1108 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001109 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001110
1111 *p = ( z < 0 ) ? -z : z;
1112 Y.s = ( z < 0 ) ? -1 : 1;
1113 Y.n = 1;
1114 Y.p = p;
1115
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001116 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001117}
1118
1119/*
1120 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1121 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001122int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001123{
Janos Follath24eed8d2019-11-22 13:21:35 +00001124 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001125 size_t i, j;
Janos Follath6c922682015-10-30 17:43:11 +01001126 mbedtls_mpi_uint *o, *p, c, tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +00001127 MPI_VALIDATE_RET( X != NULL );
1128 MPI_VALIDATE_RET( A != NULL );
1129 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001130
1131 if( X == B )
1132 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001133 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +00001134 }
1135
1136 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001137 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +02001138
Paul Bakkerf7ca7b92009-06-20 10:31:06 +00001139 /*
1140 * X should always be positive as a result of unsigned additions.
1141 */
1142 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001143
Paul Bakker23986e52011-04-24 08:57:21 +00001144 for( j = B->n; j > 0; j-- )
1145 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001146 break;
1147
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001148 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001149
1150 o = B->p; p = X->p; c = 0;
1151
Janos Follath6c922682015-10-30 17:43:11 +01001152 /*
1153 * tmp is used because it might happen that p == o
1154 */
Paul Bakker23986e52011-04-24 08:57:21 +00001155 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001156 {
Janos Follath6c922682015-10-30 17:43:11 +01001157 tmp= *o;
Paul Bakker5121ce52009-01-03 21:22:43 +00001158 *p += c; c = ( *p < c );
Janos Follath6c922682015-10-30 17:43:11 +01001159 *p += tmp; c += ( *p < tmp );
Paul Bakker5121ce52009-01-03 21:22:43 +00001160 }
1161
1162 while( c != 0 )
1163 {
1164 if( i >= X->n )
1165 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001166 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001167 p = X->p + i;
1168 }
1169
Paul Bakker2d319fd2012-09-16 21:34:26 +00001170 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +00001171 }
1172
1173cleanup:
1174
1175 return( ret );
1176}
1177
Gilles Peskine09ec10a2020-06-09 10:39:38 +02001178/**
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001179 * Helper for mbedtls_mpi subtraction.
1180 *
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001181 * Calculate l - r where l and r have the same size.
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001182 * This function operates modulo (2^ciL)^n and returns the carry
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001183 * (1 if there was a wraparound, i.e. if `l < r`, and 0 otherwise).
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001184 *
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001185 * d may be aliased to l or r.
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001186 *
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001187 * \param n Number of limbs of \p d, \p l and \p r.
1188 * \param[out] d The result of the subtraction.
1189 * \param[in] l The left operand.
1190 * \param[in] r The right operand.
1191 *
1192 * \return 1 if `l < r`.
1193 * 0 if `l >= r`.
Paul Bakker5121ce52009-01-03 21:22:43 +00001194 */
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001195static mbedtls_mpi_uint mpi_sub_hlp( size_t n,
1196 mbedtls_mpi_uint *d,
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001197 const mbedtls_mpi_uint *l,
1198 const mbedtls_mpi_uint *r )
Paul Bakker5121ce52009-01-03 21:22:43 +00001199{
Paul Bakker23986e52011-04-24 08:57:21 +00001200 size_t i;
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001201 mbedtls_mpi_uint c = 0, t, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001202
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001203 for( i = 0; i < n; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001204 {
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001205 z = ( l[i] < c ); t = l[i] - c;
1206 c = ( t < r[i] ) + z; d[i] = t - r[i];
Paul Bakker5121ce52009-01-03 21:22:43 +00001207 }
1208
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001209 return( c );
Paul Bakker5121ce52009-01-03 21:22:43 +00001210}
1211
1212/*
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001213 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
Paul Bakker5121ce52009-01-03 21:22:43 +00001214 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001215int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001216{
Janos Follath24eed8d2019-11-22 13:21:35 +00001217 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001218 size_t n;
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001219 mbedtls_mpi_uint carry;
Hanno Becker73d7d792018-12-11 10:35:51 +00001220 MPI_VALIDATE_RET( X != NULL );
1221 MPI_VALIDATE_RET( A != NULL );
1222 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001223
Paul Bakker23986e52011-04-24 08:57:21 +00001224 for( n = B->n; n > 0; n-- )
1225 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001226 break;
Gilles Peskinec8a91772021-01-27 22:30:43 +01001227 if( n > A->n )
1228 {
1229 /* B >= (2^ciL)^n > A */
1230 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1231 goto cleanup;
1232 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001233
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001234 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, A->n ) );
1235
1236 /* Set the high limbs of X to match A. Don't touch the lower limbs
1237 * because X might be aliased to B, and we must not overwrite the
1238 * significant digits of B. */
1239 if( A->n > n )
1240 memcpy( X->p + n, A->p + n, ( A->n - n ) * ciL );
1241 if( X->n > A->n )
1242 memset( X->p + A->n, 0, ( X->n - A->n ) * ciL );
1243
1244 carry = mpi_sub_hlp( n, X->p, A->p, B->p );
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001245 if( carry != 0 )
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001246 {
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001247 /* Propagate the carry to the first nonzero limb of X. */
1248 for( ; n < X->n && X->p[n] == 0; n++ )
1249 --X->p[n];
1250 /* If we ran out of space for the carry, it means that the result
1251 * is negative. */
1252 if( n == X->n )
Gilles Peskine89b41302020-07-23 01:16:46 +02001253 {
1254 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1255 goto cleanup;
1256 }
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001257 --X->p[n];
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001258 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001259
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001260 /* X should always be positive as a result of unsigned subtractions. */
1261 X->s = 1;
1262
Paul Bakker5121ce52009-01-03 21:22:43 +00001263cleanup:
Paul Bakker5121ce52009-01-03 21:22:43 +00001264 return( ret );
1265}
1266
1267/*
1268 * Signed addition: X = A + B
1269 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001270int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001271{
Hanno Becker73d7d792018-12-11 10:35:51 +00001272 int ret, s;
1273 MPI_VALIDATE_RET( X != NULL );
1274 MPI_VALIDATE_RET( A != NULL );
1275 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001276
Hanno Becker73d7d792018-12-11 10:35:51 +00001277 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001278 if( A->s * B->s < 0 )
1279 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001280 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001281 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001282 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001283 X->s = s;
1284 }
1285 else
1286 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001287 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001288 X->s = -s;
1289 }
1290 }
1291 else
1292 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001293 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001294 X->s = s;
1295 }
1296
1297cleanup:
1298
1299 return( ret );
1300}
1301
1302/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001303 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001304 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001305int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001306{
Hanno Becker73d7d792018-12-11 10:35:51 +00001307 int ret, s;
1308 MPI_VALIDATE_RET( X != NULL );
1309 MPI_VALIDATE_RET( A != NULL );
1310 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001311
Hanno Becker73d7d792018-12-11 10:35:51 +00001312 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001313 if( A->s * B->s > 0 )
1314 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001315 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001316 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001317 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001318 X->s = s;
1319 }
1320 else
1321 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001322 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001323 X->s = -s;
1324 }
1325 }
1326 else
1327 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001328 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001329 X->s = s;
1330 }
1331
1332cleanup:
1333
1334 return( ret );
1335}
1336
1337/*
1338 * Signed addition: X = A + b
1339 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001340int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001341{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001342 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001343 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001344 MPI_VALIDATE_RET( X != NULL );
1345 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001346
1347 p[0] = ( b < 0 ) ? -b : b;
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001348 B.s = ( b < 0 ) ? -1 : 1;
1349 B.n = 1;
1350 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001351
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001352 return( mbedtls_mpi_add_mpi( X, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001353}
1354
1355/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001356 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001357 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001358int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001359{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001360 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001361 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001362 MPI_VALIDATE_RET( X != NULL );
1363 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001364
1365 p[0] = ( b < 0 ) ? -b : b;
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001366 B.s = ( b < 0 ) ? -1 : 1;
1367 B.n = 1;
1368 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001369
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001370 return( mbedtls_mpi_sub_mpi( X, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001371}
1372
Hanno Becker284d7782022-04-11 09:19:24 +01001373mbedtls_mpi_uint mbedtls_mpi_core_mla( mbedtls_mpi_uint *d, size_t d_len,
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001374 const mbedtls_mpi_uint *s, size_t s_len,
1375 mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001376{
Hanno Beckere7f14a32022-04-06 06:11:26 +01001377 mbedtls_mpi_uint c = 0; /* carry */
Hanno Becker5d4ceeb2022-04-11 09:46:47 +01001378 size_t excess_len = d_len - s_len;
Hanno Beckerdefe5692022-04-06 06:12:09 +01001379
Hanno Becker63eb28c2022-04-06 11:30:51 +01001380 size_t steps_x8 = s_len / 8;
1381 size_t steps_x1 = s_len & 7;
1382
1383 while( steps_x8-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001384 {
Hanno Beckereacf3b92022-04-06 11:25:22 +01001385 MULADDC_X8_INIT
1386 MULADDC_X8_CORE
1387 MULADDC_X8_STOP
Paul Bakker5121ce52009-01-03 21:22:43 +00001388 }
1389
Hanno Becker63eb28c2022-04-06 11:30:51 +01001390 while( steps_x1-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001391 {
Hanno Beckereacf3b92022-04-06 11:25:22 +01001392 MULADDC_X1_INIT
1393 MULADDC_X1_CORE
1394 MULADDC_X1_STOP
Paul Bakker5121ce52009-01-03 21:22:43 +00001395 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001396
Hanno Becker284d7782022-04-11 09:19:24 +01001397 while( excess_len-- )
Gilles Peskine8e464c42020-07-24 00:08:38 +02001398 {
Paul Bakker5121ce52009-01-03 21:22:43 +00001399 *d += c; c = ( *d < c ); d++;
1400 }
Hanno Beckerdefe5692022-04-06 06:12:09 +01001401
1402 return( c );
Paul Bakker5121ce52009-01-03 21:22:43 +00001403}
1404
1405/*
1406 * Baseline multiplication: X = A * B (HAC 14.12)
1407 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001408int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001409{
Janos Follath24eed8d2019-11-22 13:21:35 +00001410 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker1772e052022-04-13 06:51:40 +01001411 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001412 mbedtls_mpi TA, TB;
Hanno Beckerda763de2022-04-13 06:50:02 +01001413 int result_is_zero = 0;
Hanno Becker73d7d792018-12-11 10:35:51 +00001414 MPI_VALIDATE_RET( X != NULL );
1415 MPI_VALIDATE_RET( A != NULL );
1416 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001417
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001418 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001419
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001420 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1421 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001422
Hanno Beckerda763de2022-04-13 06:50:02 +01001423 for( i = A->n; i > 0; i-- )
1424 if( A->p[i - 1] != 0 )
1425 break;
1426 if( i == 0 )
1427 result_is_zero = 1;
1428
1429 for( j = B->n; j > 0; j-- )
1430 if( B->p[j - 1] != 0 )
1431 break;
1432 if( j == 0 )
1433 result_is_zero = 1;
1434
1435 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001436 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001437
Hanno Becker1772e052022-04-13 06:51:40 +01001438 for( size_t k = 0; k < j; k++ )
Hanno Beckerfee261a2022-04-06 06:20:22 +01001439 {
1440 /* We know that there cannot be any carry-out since we're
1441 * iterating from bottom to top. */
Hanno Beckerda763de2022-04-13 06:50:02 +01001442 (void) mbedtls_mpi_core_mla( X->p + k, i + 1,
1443 A->p, i,
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001444 B->p[k] );
Hanno Beckerfee261a2022-04-06 06:20:22 +01001445 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001446
Hanno Beckerda763de2022-04-13 06:50:02 +01001447 /* If the result is 0, we don't shortcut the operation, which reduces
1448 * but does not eliminate side channels leaking the zero-ness. We do
1449 * need to take care to set the sign bit properly since the library does
1450 * not fully support an MPI object with a value of 0 and s == -1. */
1451 if( result_is_zero )
1452 X->s = 1;
1453 else
1454 X->s = A->s * B->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001455
1456cleanup:
1457
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001458 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001459
1460 return( ret );
1461}
1462
1463/*
1464 * Baseline multiplication: X = A * b
1465 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001466int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001467{
Hanno Becker73d7d792018-12-11 10:35:51 +00001468 MPI_VALIDATE_RET( X != NULL );
1469 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001470
Hanno Becker35771312022-04-14 11:52:11 +01001471 size_t n = A->n;
1472 while( n > 0 && A->p[n - 1] == 0 )
1473 --n;
1474
Hanno Becker74a11a32022-04-06 06:27:00 +01001475 /* The general method below doesn't work if b==0. */
Hanno Becker35771312022-04-14 11:52:11 +01001476 if( b == 0 || n == 0 )
Paul Elliott986b55a2021-04-20 21:46:29 +01001477 return( mbedtls_mpi_lset( X, 0 ) );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001478
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001479 /* Calculate A*b as A + A*(b-1) to take advantage of mbedtls_mpi_core_mla */
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001480 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Gilles Peskinecd0dbf32020-07-24 00:09:04 +02001481 /* In general, A * b requires 1 limb more than b. If
1482 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1483 * number of limbs as A and the call to grow() is not required since
Gilles Peskinee1bba7c2021-03-10 23:44:10 +01001484 * copy() will take care of the growth if needed. However, experimentally,
1485 * making the call to grow() unconditional causes slightly fewer
Gilles Peskinecd0dbf32020-07-24 00:09:04 +02001486 * calls to calloc() in ECP code, presumably because it reuses the
1487 * same mpi for a while and this way the mpi is more likely to directly
Hanno Becker9137b9c2022-04-12 10:51:54 +01001488 * grow to its final size.
1489 *
1490 * Note that calculating A*b as 0 + A*b doesn't work as-is because
1491 * A,X can be the same. */
Hanno Becker35771312022-04-14 11:52:11 +01001492 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n + 1 ) );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001493 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Hanno Becker35771312022-04-14 11:52:11 +01001494 mbedtls_mpi_core_mla( X->p, X->n, A->p, n, b - 1 );
Gilles Peskine8fd95c62020-07-23 21:58:50 +02001495
1496cleanup:
1497 return( ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00001498}
1499
1500/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001501 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1502 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001503 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001504static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1505 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001506{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001507#if defined(MBEDTLS_HAVE_UDBL)
1508 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001509#else
Simon Butcher9803d072016-01-03 00:24:34 +00001510 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1511 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001512 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1513 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001514 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001515#endif
1516
Simon Butcher15b15d12015-11-26 19:35:03 +00001517 /*
1518 * Check for overflow
1519 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001520 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001521 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001522 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001523
Simon Butcherf5ba0452015-12-27 23:01:55 +00001524 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001525 }
1526
1527#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001528 dividend = (mbedtls_t_udbl) u1 << biL;
1529 dividend |= (mbedtls_t_udbl) u0;
1530 quotient = dividend / d;
1531 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1532 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1533
1534 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001535 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001536
1537 return (mbedtls_mpi_uint) quotient;
1538#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001539
1540 /*
1541 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1542 * Vol. 2 - Seminumerical Algorithms, Knuth
1543 */
1544
1545 /*
1546 * Normalize the divisor, d, and dividend, u0, u1
1547 */
1548 s = mbedtls_clz( d );
1549 d = d << s;
1550
1551 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001552 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001553 u0 = u0 << s;
1554
1555 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001556 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001557
1558 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001559 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001560
1561 /*
1562 * Find the first quotient and remainder
1563 */
1564 q1 = u1 / d1;
1565 r0 = u1 - d1 * q1;
1566
1567 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1568 {
1569 q1 -= 1;
1570 r0 += d1;
1571
1572 if ( r0 >= radix ) break;
1573 }
1574
Simon Butcherf5ba0452015-12-27 23:01:55 +00001575 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001576 q0 = rAX / d1;
1577 r0 = rAX - q0 * d1;
1578
1579 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1580 {
1581 q0 -= 1;
1582 r0 += d1;
1583
1584 if ( r0 >= radix ) break;
1585 }
1586
1587 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001588 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001589
1590 quotient = q1 * radix + q0;
1591
1592 return quotient;
1593#endif
1594}
1595
1596/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001597 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001598 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001599int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1600 const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001601{
Janos Follath24eed8d2019-11-22 13:21:35 +00001602 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001603 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001604 mbedtls_mpi X, Y, Z, T1, T2;
Alexander Kd19a1932019-11-01 18:20:42 +03001605 mbedtls_mpi_uint TP2[3];
Hanno Becker73d7d792018-12-11 10:35:51 +00001606 MPI_VALIDATE_RET( A != NULL );
1607 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001608
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001609 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1610 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001611
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001612 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001613 mbedtls_mpi_init( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001614 /*
1615 * Avoid dynamic memory allocations for constant-size T2.
1616 *
1617 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1618 * so nobody increase the size of the MPI and we're safe to use an on-stack
1619 * buffer.
1620 */
Alexander K35d6d462019-10-31 14:46:45 +03001621 T2.s = 1;
Alexander Kd19a1932019-11-01 18:20:42 +03001622 T2.n = sizeof( TP2 ) / sizeof( *TP2 );
1623 T2.p = TP2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001624
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001625 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001626 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001627 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1628 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001629 return( 0 );
1630 }
1631
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001632 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1633 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001634 X.s = Y.s = 1;
1635
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001636 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1637 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
Gilles Peskine2536aa72020-07-24 00:12:59 +02001638 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, A->n + 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001639
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001640 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001641 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001642 {
1643 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001644 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1645 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001646 }
1647 else k = 0;
1648
1649 n = X.n - 1;
1650 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001651 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001652
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001653 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001654 {
1655 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001656 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001657 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001658 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001659
1660 for( i = n; i > t ; i-- )
1661 {
1662 if( X.p[i] >= Y.p[t] )
1663 Z.p[i - t - 1] = ~0;
1664 else
1665 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001666 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1667 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001668 }
1669
Alexander K35d6d462019-10-31 14:46:45 +03001670 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1671 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1672 T2.p[2] = X.p[i];
1673
Paul Bakker5121ce52009-01-03 21:22:43 +00001674 Z.p[i - t - 1]++;
1675 do
1676 {
1677 Z.p[i - t - 1]--;
1678
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001679 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001680 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001681 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001682 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001683 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001684 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001685
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001686 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1687 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1688 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001689
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001690 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001691 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001692 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1693 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1694 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001695 Z.p[i - t - 1]--;
1696 }
1697 }
1698
1699 if( Q != NULL )
1700 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001701 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001702 Q->s = A->s * B->s;
1703 }
1704
1705 if( R != NULL )
1706 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001707 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001708 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001709 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001710
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001711 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001712 R->s = 1;
1713 }
1714
1715cleanup:
1716
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001717 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001718 mbedtls_mpi_free( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001719 mbedtls_platform_zeroize( TP2, sizeof( TP2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001720
1721 return( ret );
1722}
1723
1724/*
1725 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001726 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001727int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1728 const mbedtls_mpi *A,
1729 mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001730{
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001731 mbedtls_mpi B;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001732 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001733 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001734
1735 p[0] = ( b < 0 ) ? -b : b;
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001736 B.s = ( b < 0 ) ? -1 : 1;
1737 B.n = 1;
1738 B.p = p;
Paul Bakker5121ce52009-01-03 21:22:43 +00001739
Yuto Takano36c8ddc2021-07-05 09:10:52 +01001740 return( mbedtls_mpi_div_mpi( Q, R, A, &B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001741}
1742
1743/*
1744 * Modulo: R = A mod B
1745 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001746int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001747{
Janos Follath24eed8d2019-11-22 13:21:35 +00001748 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +00001749 MPI_VALIDATE_RET( R != NULL );
1750 MPI_VALIDATE_RET( A != NULL );
1751 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001752
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001753 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1754 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001755
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001756 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001757
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001758 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1759 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001760
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001761 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1762 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001763
1764cleanup:
1765
1766 return( ret );
1767}
1768
1769/*
1770 * Modulo: r = A mod b
1771 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001772int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001773{
Paul Bakker23986e52011-04-24 08:57:21 +00001774 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001775 mbedtls_mpi_uint x, y, z;
Hanno Becker73d7d792018-12-11 10:35:51 +00001776 MPI_VALIDATE_RET( r != NULL );
1777 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001778
1779 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001780 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001781
1782 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001783 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001784
1785 /*
1786 * handle trivial cases
1787 */
Gilles Peskineae25bb02022-06-09 19:32:46 +02001788 if( b == 1 || A->n == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001789 {
1790 *r = 0;
1791 return( 0 );
1792 }
1793
1794 if( b == 2 )
1795 {
1796 *r = A->p[0] & 1;
1797 return( 0 );
1798 }
1799
1800 /*
1801 * general case
1802 */
Paul Bakker23986e52011-04-24 08:57:21 +00001803 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001804 {
Paul Bakker23986e52011-04-24 08:57:21 +00001805 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001806 y = ( y << biH ) | ( x >> biH );
1807 z = y / b;
1808 y -= z * b;
1809
1810 x <<= biH;
1811 y = ( y << biH ) | ( x >> biH );
1812 z = y / b;
1813 y -= z * b;
1814 }
1815
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001816 /*
1817 * If A is negative, then the current y represents a negative value.
1818 * Flipping it to the positive side.
1819 */
1820 if( A->s < 0 && y != 0 )
1821 y = b - y;
1822
Paul Bakker5121ce52009-01-03 21:22:43 +00001823 *r = y;
1824
1825 return( 0 );
1826}
1827
1828/*
1829 * Fast Montgomery initialization (thanks to Tom St Denis)
1830 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001831static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001832{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001833 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001834 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00001835
1836 x = m0;
1837 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001838
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001839 for( i = biL; i >= 8; i /= 2 )
1840 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001841
1842 *mm = ~x + 1;
1843}
1844
Gilles Peskine2a82f722020-06-04 15:00:49 +02001845/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1846 *
1847 * \param[in,out] A One of the numbers to multiply.
Gilles Peskine221626f2020-06-08 22:37:50 +02001848 * It must have at least as many limbs as N
1849 * (A->n >= N->n), and any limbs beyond n are ignored.
Gilles Peskine2a82f722020-06-04 15:00:49 +02001850 * On successful completion, A contains the result of
1851 * the multiplication A * B * R^-1 mod N where
1852 * R = (2^ciL)^n.
1853 * \param[in] B One of the numbers to multiply.
1854 * It must be nonzero and must not have more limbs than N
1855 * (B->n <= N->n).
1856 * \param[in] N The modulo. N must be odd.
1857 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1858 * This is -N^-1 mod 2^ciL.
1859 * \param[in,out] T A bignum for temporary storage.
Hanno Beckere1417022022-04-06 06:45:45 +01001860 * It must be at least twice the limb size of N plus 1
1861 * (T->n >= 2 * N->n + 1).
Gilles Peskine2a82f722020-06-04 15:00:49 +02001862 * Its initial content is unused and
1863 * its final content is indeterminate.
1864 * Note that unlike the usual convention in the library
1865 * for `const mbedtls_mpi*`, the content of T can change.
Paul Bakker5121ce52009-01-03 21:22:43 +00001866 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02001867static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001868 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001869{
Hanno Becker0235f752022-04-12 10:54:46 +01001870 size_t n, m;
1871 mbedtls_mpi_uint *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00001872
1873 memset( T->p, 0, T->n * ciL );
1874
1875 d = T->p;
1876 n = N->n;
1877 m = ( B->n < n ) ? B->n : n;
1878
Hanno Becker0235f752022-04-12 10:54:46 +01001879 for( size_t i = 0; i < n; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001880 {
Hanno Becker0235f752022-04-12 10:54:46 +01001881 mbedtls_mpi_uint u0, u1;
1882
Paul Bakker5121ce52009-01-03 21:22:43 +00001883 /*
1884 * T = (T + u0*B + u1*N) / 2^biL
1885 */
1886 u0 = A->p[i];
1887 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1888
Hanno Beckeraef9cc42022-04-11 06:36:29 +01001889 (void) mbedtls_mpi_core_mla( d, n + 2,
1890 B->p, m,
1891 u0 );
1892 (void) mbedtls_mpi_core_mla( d, n + 2,
1893 N->p, n,
1894 u1 );
Hanno Beckere1417022022-04-06 06:45:45 +01001895 d++;
Paul Bakker5121ce52009-01-03 21:22:43 +00001896 }
1897
Gilles Peskine221626f2020-06-08 22:37:50 +02001898 /* At this point, d is either the desired result or the desired result
1899 * plus N. We now potentially subtract N, avoiding leaking whether the
1900 * subtraction is performed through side channels. */
Paul Bakker5121ce52009-01-03 21:22:43 +00001901
Gilles Peskine221626f2020-06-08 22:37:50 +02001902 /* Copy the n least significant limbs of d to A, so that
1903 * A = d if d < N (recall that N has n limbs). */
1904 memcpy( A->p, d, n * ciL );
Gilles Peskine09ec10a2020-06-09 10:39:38 +02001905 /* If d >= N then we want to set A to d - N. To prevent timing attacks,
Gilles Peskine221626f2020-06-08 22:37:50 +02001906 * do the calculation without using conditional tests. */
1907 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
Gilles Peskine132c0972020-06-04 21:05:24 +02001908 d[n] += 1;
Gilles Peskine1acf7cb2020-07-23 01:03:22 +02001909 d[n] -= mpi_sub_hlp( n, d, d, N->p );
Gilles Peskine221626f2020-06-08 22:37:50 +02001910 /* If d0 < N then d < (2^biL)^n
1911 * so d[n] == 0 and we want to keep A as it is.
1912 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
1913 * so d[n] == 1 and we want to set A to the result of the subtraction
1914 * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
1915 * This exactly corresponds to a conditional assignment. */
Gabor Mezei90437e32021-10-20 11:59:27 +02001916 mbedtls_ct_mpi_uint_cond_assign( n, A->p, d, (unsigned char) d[n] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001917}
1918
1919/*
1920 * Montgomery reduction: A = A * R^-1 mod N
Gilles Peskine2a82f722020-06-04 15:00:49 +02001921 *
1922 * See mpi_montmul() regarding constraints and guarantees on the parameters.
Paul Bakker5121ce52009-01-03 21:22:43 +00001923 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02001924static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
1925 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001926{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001927 mbedtls_mpi_uint z = 1;
1928 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001929
Paul Bakker8ddb6452013-02-27 14:56:33 +01001930 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001931 U.p = &z;
1932
Gilles Peskine4e91d472020-06-04 20:55:15 +02001933 mpi_montmul( A, &U, N, mm, T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001934}
1935
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001936/**
1937 * Select an MPI from a table without leaking the index.
1938 *
1939 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
1940 * reads the entire table in order to avoid leaking the value of idx to an
1941 * attacker able to observe memory access patterns.
1942 *
1943 * \param[out] R Where to write the selected MPI.
1944 * \param[in] T The table to read from.
1945 * \param[in] T_size The number of elements in the table.
1946 * \param[in] idx The index of the element to select;
1947 * this must satisfy 0 <= idx < T_size.
1948 *
1949 * \return \c 0 on success, or a negative error code.
1950 */
1951static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx )
1952{
1953 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1954
1955 for( size_t i = 0; i < T_size; i++ )
Manuel Pégourié-Gonnard92413ef2021-06-03 10:42:46 +02001956 {
1957 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i],
Gabor Mezei90437e32021-10-20 11:59:27 +02001958 (unsigned char) mbedtls_ct_size_bool_eq( i, idx ) ) );
Manuel Pégourié-Gonnard92413ef2021-06-03 10:42:46 +02001959 }
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01001960
1961cleanup:
1962 return( ret );
1963}
1964
Paul Bakker5121ce52009-01-03 21:22:43 +00001965/*
1966 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1967 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001968int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
1969 const mbedtls_mpi *E, const mbedtls_mpi *N,
Yuto Takano538a0cb2021-07-14 10:20:09 +01001970 mbedtls_mpi *prec_RR )
Paul Bakker5121ce52009-01-03 21:22:43 +00001971{
Janos Follath24eed8d2019-11-22 13:21:35 +00001972 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001973 size_t wbits, wsize, one = 1;
1974 size_t i, j, nblimbs;
1975 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001976 mbedtls_mpi_uint ei, mm, state;
Janos Follath8e7d6a02022-10-04 13:27:40 +01001977 mbedtls_mpi RR, T, W[ ( 1 << MBEDTLS_MPI_WINDOW_SIZE ) + 1 ], WW, Apos;
Janos Follathb764ee12022-10-04 14:00:09 +01001978 const size_t w_count = sizeof( W ) / sizeof( W[0] );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001979 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001980
Hanno Becker73d7d792018-12-11 10:35:51 +00001981 MPI_VALIDATE_RET( X != NULL );
1982 MPI_VALIDATE_RET( A != NULL );
1983 MPI_VALIDATE_RET( E != NULL );
1984 MPI_VALIDATE_RET( N != NULL );
1985
Hanno Becker8d1dd1b2017-09-28 11:02:24 +01001986 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001987 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001988
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001989 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1990 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001991
Chris Jones9246d042020-11-25 15:12:39 +00001992 if( mbedtls_mpi_bitlen( E ) > MBEDTLS_MPI_MAX_BITS ||
1993 mbedtls_mpi_bitlen( N ) > MBEDTLS_MPI_MAX_BITS )
1994 return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1995
Paul Bakkerf6198c12012-05-16 08:02:29 +00001996 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001997 * Init temps and window size
1998 */
1999 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002000 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
2001 mbedtls_mpi_init( &Apos );
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01002002 mbedtls_mpi_init( &WW );
Paul Bakker5121ce52009-01-03 21:22:43 +00002003 memset( W, 0, sizeof( W ) );
2004
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002005 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00002006
2007 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2008 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2009
Peter Kolbuse6bcad32018-12-11 14:01:44 -06002010#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002011 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2012 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Peter Kolbuse6bcad32018-12-11 14:01:44 -06002013#endif
Paul Bakkerb6d5f082011-11-25 11:52:11 +00002014
Paul Bakker5121ce52009-01-03 21:22:43 +00002015 j = N->n + 1;
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02002016 /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
2017 * and mpi_montred() calls later. Here we ensure that W[1] and X are
2018 * large enough, and later we'll grow other W[i] to the same length.
2019 * They must not be shrunk midway through this function!
2020 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002021 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2022 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2023 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002024
2025 /*
Janos Follathf08b40e2022-11-11 15:56:38 +00002026 * If we call mpi_montmul() without doing a table lookup first, we leak
2027 * through timing side channels the fact that a squaring is happening. In
2028 * some strong attack settings this can be enough to defeat blinding.
2029 *
2030 * To prevent this leak, we append the output variable to the end of the
2031 * table. This allows as to always do a constant time lookup whenever we
2032 * call mpi_montmul().
Janos Follath8e7d6a02022-10-04 13:27:40 +01002033 */
Janos Follathb764ee12022-10-04 14:00:09 +01002034 const size_t x_index = w_count - 1;
Janos Follathf08b40e2022-11-11 15:56:38 +00002035 /*
2036 * To prevent the leak, we need to use the table entry in each calculation
2037 * from this point on. This makes it safe to load X into the table by a
2038 * simple assignment.
2039 */
Janos Follath8e7d6a02022-10-04 13:27:40 +01002040 W[x_index] = *X;
2041
2042 /*
Paul Bakker50546922012-05-19 08:40:49 +00002043 * Compensate for negative A (and correct at the end)
2044 */
2045 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00002046 if( neg )
2047 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002048 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00002049 Apos.s = 1;
2050 A = &Apos;
2051 }
2052
2053 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00002054 * If 1st call, pre-compute R^2 mod N
2055 */
Yuto Takano538a0cb2021-07-14 10:20:09 +01002056 if( prec_RR == NULL || prec_RR->p == NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +00002057 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002058 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2059 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2060 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002061
Yuto Takano538a0cb2021-07-14 10:20:09 +01002062 if( prec_RR != NULL )
2063 memcpy( prec_RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002064 }
2065 else
Yuto Takano538a0cb2021-07-14 10:20:09 +01002066 memcpy( &RR, prec_RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002067
2068 /*
2069 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2070 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002071 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02002072 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002073 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02002074 /* This should be a no-op because W[1] is already that large before
2075 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
2076 * in mpi_montmul() below, so let's make sure. */
Gilles Peskine2aa3f162021-06-15 21:22:48 +02002077 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n + 1 ) );
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02002078 }
Paul Bakkerc2024f42014-01-23 20:38:35 +01002079 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002080 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002081
Gilles Peskine3da1a8f2021-06-08 23:17:42 +02002082 /* Note that this is safe because W[1] always has at least N->n limbs
2083 * (it grew above and was preserved by mbedtls_mpi_copy()). */
Gilles Peskine4e91d472020-06-04 20:55:15 +02002084 mpi_montmul( &W[1], &RR, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002085
2086 /*
Janos Follath8e7d6a02022-10-04 13:27:40 +01002087 * W[x_index] = R^2 * R^-1 mod N = R mod N
Paul Bakker5121ce52009-01-03 21:22:43 +00002088 */
Janos Follath8e7d6a02022-10-04 13:27:40 +01002089 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[x_index], &RR ) );
2090 mpi_montred( &W[x_index], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002091
2092 if( wsize > 1 )
2093 {
2094 /*
2095 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2096 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002097 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002098
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002099 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2100 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002101
2102 for( i = 0; i < wsize - 1; i++ )
Gilles Peskine4e91d472020-06-04 20:55:15 +02002103 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01002104
Paul Bakker5121ce52009-01-03 21:22:43 +00002105 /*
2106 * W[i] = W[i - 1] * W[1]
2107 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002108 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002109 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002110 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2111 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002112
Gilles Peskine4e91d472020-06-04 20:55:15 +02002113 mpi_montmul( &W[i], &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002114 }
2115 }
2116
2117 nblimbs = E->n;
2118 bufsize = 0;
2119 nbits = 0;
2120 wbits = 0;
2121 state = 0;
2122
2123 while( 1 )
2124 {
2125 if( bufsize == 0 )
2126 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01002127 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002128 break;
2129
Paul Bakker0d7702c2013-10-29 16:18:35 +01002130 nblimbs--;
2131
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002132 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00002133 }
2134
2135 bufsize--;
2136
2137 ei = (E->p[nblimbs] >> bufsize) & 1;
2138
2139 /*
2140 * skip leading 0s
2141 */
2142 if( ei == 0 && state == 0 )
2143 continue;
2144
2145 if( ei == 0 && state == 1 )
2146 {
2147 /*
Janos Follath8e7d6a02022-10-04 13:27:40 +01002148 * out of window, square W[x_index]
Paul Bakker5121ce52009-01-03 21:22:43 +00002149 */
Janos Follathb764ee12022-10-04 14:00:09 +01002150 MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, x_index ) );
2151 mpi_montmul( &W[x_index], &WW, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002152 continue;
2153 }
2154
2155 /*
2156 * add ei to current window
2157 */
2158 state = 2;
2159
2160 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02002161 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002162
2163 if( nbits == wsize )
2164 {
2165 /*
Janos Follath8e7d6a02022-10-04 13:27:40 +01002166 * W[x_index] = W[x_index]^wsize R^-1 mod N
Paul Bakker5121ce52009-01-03 21:22:43 +00002167 */
2168 for( i = 0; i < wsize; i++ )
Janos Follathb764ee12022-10-04 14:00:09 +01002169 {
2170 MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, x_index ) );
2171 mpi_montmul( &W[x_index], &WW, N, mm, &T );
2172 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002173
2174 /*
Janos Follath8e7d6a02022-10-04 13:27:40 +01002175 * W[x_index] = W[x_index] * W[wbits] R^-1 mod N
Paul Bakker5121ce52009-01-03 21:22:43 +00002176 */
Janos Follathb764ee12022-10-04 14:00:09 +01002177 MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, wbits ) );
Janos Follath8e7d6a02022-10-04 13:27:40 +01002178 mpi_montmul( &W[x_index], &WW, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002179
2180 state--;
2181 nbits = 0;
2182 wbits = 0;
2183 }
2184 }
2185
2186 /*
2187 * process the remaining bits
2188 */
2189 for( i = 0; i < nbits; i++ )
2190 {
Janos Follathb764ee12022-10-04 14:00:09 +01002191 MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, x_index ) );
2192 mpi_montmul( &W[x_index], &WW, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002193
2194 wbits <<= 1;
2195
Paul Bakker66d5d072014-06-17 16:39:18 +02002196 if( ( wbits & ( one << wsize ) ) != 0 )
Janos Follathb764ee12022-10-04 14:00:09 +01002197 {
2198 MBEDTLS_MPI_CHK( mpi_select( &WW, W, w_count, 1 ) );
2199 mpi_montmul( &W[x_index], &WW, N, mm, &T );
2200 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002201 }
2202
2203 /*
Janos Follath8e7d6a02022-10-04 13:27:40 +01002204 * W[x_index] = A^E * R * R^-1 mod N = A^E mod N
Paul Bakker5121ce52009-01-03 21:22:43 +00002205 */
Janos Follath8e7d6a02022-10-04 13:27:40 +01002206 mpi_montred( &W[x_index], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002207
Hanno Beckera4af1c42017-04-18 09:07:45 +01002208 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00002209 {
Janos Follath8e7d6a02022-10-04 13:27:40 +01002210 W[x_index].s = -1;
2211 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &W[x_index], N, &W[x_index] ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002212 }
2213
Janos Follath8e7d6a02022-10-04 13:27:40 +01002214 /*
2215 * Load the result in the output variable.
2216 */
2217 *X = W[x_index];
2218
Paul Bakker5121ce52009-01-03 21:22:43 +00002219cleanup:
2220
Paul Bakker66d5d072014-06-17 16:39:18 +02002221 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002222 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00002223
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002224 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Manuel Pégourié-Gonnard1297ef32021-03-09 11:22:20 +01002225 mbedtls_mpi_free( &WW );
Paul Bakker6c591fa2011-05-05 11:49:20 +00002226
Yuto Takano538a0cb2021-07-14 10:20:09 +01002227 if( prec_RR == NULL || prec_RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002228 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002229
2230 return( ret );
2231}
2232
Paul Bakker5121ce52009-01-03 21:22:43 +00002233/*
2234 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2235 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002236int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00002237{
Janos Follath24eed8d2019-11-22 13:21:35 +00002238 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00002239 size_t lz, lzt;
Alexander Ke8ad49f2019-08-16 16:16:07 +03002240 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00002241
Hanno Becker73d7d792018-12-11 10:35:51 +00002242 MPI_VALIDATE_RET( G != NULL );
2243 MPI_VALIDATE_RET( A != NULL );
2244 MPI_VALIDATE_RET( B != NULL );
2245
Alexander Ke8ad49f2019-08-16 16:16:07 +03002246 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002247
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002248 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2249 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002250
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002251 lz = mbedtls_mpi_lsb( &TA );
2252 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002253
Gilles Peskine27253bc2021-06-09 13:26:43 +02002254 /* The loop below gives the correct result when A==0 but not when B==0.
2255 * So have a special case for B==0. Leverage the fact that we just
2256 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
2257 * slightly more efficient than cmp_int(). */
2258 if( lzt == 0 && mbedtls_mpi_get_bit( &TB, 0 ) == 0 )
2259 {
2260 ret = mbedtls_mpi_copy( G, A );
2261 goto cleanup;
2262 }
2263
Paul Bakker66d5d072014-06-17 16:39:18 +02002264 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002265 lz = lzt;
2266
Paul Bakker5121ce52009-01-03 21:22:43 +00002267 TA.s = TB.s = 1;
2268
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002269 /* We mostly follow the procedure described in HAC 14.54, but with some
2270 * minor differences:
2271 * - Sequences of multiplications or divisions by 2 are grouped into a
2272 * single shift operation.
Gilles Peskineb09c7ee2021-06-21 18:58:39 +02002273 * - The procedure in HAC assumes that 0 < TB <= TA.
2274 * - The condition TB <= TA is not actually necessary for correctness.
2275 * TA and TB have symmetric roles except for the loop termination
2276 * condition, and the shifts at the beginning of the loop body
2277 * remove any significance from the ordering of TA vs TB before
2278 * the shifts.
2279 * - If TA = 0, the loop goes through 0 iterations and the result is
2280 * correctly TB.
2281 * - The case TB = 0 was short-circuited above.
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002282 *
2283 * For the correctness proof below, decompose the original values of
2284 * A and B as
2285 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
2286 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
2287 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
2288 * and gcd(A',B') is odd or 0.
2289 *
2290 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
2291 * The code maintains the following invariant:
2292 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
Gilles Peskine4df3f1f2021-06-15 22:09:39 +02002293 */
2294
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002295 /* Proof that the loop terminates:
2296 * At each iteration, either the right-shift by 1 is made on a nonzero
2297 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
2298 * by at least 1, or the right-shift by 1 is made on zero and then
2299 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
2300 * since in that case TB is calculated from TB-TA with the condition TB>TA).
2301 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002302 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002303 {
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002304 /* Divisions by 2 preserve the invariant (I). */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002305 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2306 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002307
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002308 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
2309 * TA-TB is even so the division by 2 has an integer result.
2310 * Invariant (I) is preserved since any odd divisor of both TA and TB
2311 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
Shaun Case8b0ecbc2021-12-20 21:14:10 -08002312 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002313 * divides TA.
2314 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002315 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002316 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002317 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2318 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002319 }
2320 else
2321 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002322 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2323 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002324 }
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002325 /* Note that one of TA or TB is still odd. */
Paul Bakker5121ce52009-01-03 21:22:43 +00002326 }
2327
Gilles Peskine2a63c5b2021-06-16 13:42:04 +02002328 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
2329 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
2330 * - If there was at least one loop iteration, then one of TA or TB is odd,
2331 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
2332 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
2333 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
Gilles Peskine4d3fd362021-06-21 11:40:38 +02002334 * 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 +02002335 */
2336
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002337 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2338 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002339
2340cleanup:
2341
Alexander Ke8ad49f2019-08-16 16:16:07 +03002342 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002343
2344 return( ret );
2345}
2346
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002347/* Fill X with n_bytes random bytes.
2348 * X must already have room for those bytes.
Gilles Peskineafb2bd22021-06-03 11:51:09 +02002349 * The ordering of the bytes returned from the RNG is suitable for
2350 * deterministic ECDSA (see RFC 6979 §3.3 and mbedtls_mpi_random()).
Gilles Peskineebe9b6a2021-04-13 21:55:35 +02002351 * The size and sign of X are unchanged.
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002352 * n_bytes must not be 0.
2353 */
2354static int mpi_fill_random_internal(
2355 mbedtls_mpi *X, size_t n_bytes,
2356 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2357{
2358 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2359 const size_t limbs = CHARS_TO_LIMBS( n_bytes );
2360 const size_t overhead = ( limbs * ciL ) - n_bytes;
2361
2362 if( X->n < limbs )
2363 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002364
Gilles Peskineebe9b6a2021-04-13 21:55:35 +02002365 memset( X->p, 0, overhead );
2366 memset( (unsigned char *) X->p + limbs * ciL, 0, ( X->n - limbs ) * ciL );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002367 MBEDTLS_MPI_CHK( f_rng( p_rng, (unsigned char *) X->p + overhead, n_bytes ) );
2368 mpi_bigendian_to_host( X->p, limbs );
2369
2370cleanup:
2371 return( ret );
2372}
2373
Paul Bakker33dc46b2014-04-30 16:11:39 +02002374/*
2375 * Fill X with size bytes of random.
2376 *
2377 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02002378 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02002379 * deterministic, eg for tests).
2380 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002381int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002382 int (*f_rng)(void *, unsigned char *, size_t),
2383 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00002384{
Janos Follath24eed8d2019-11-22 13:21:35 +00002385 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker6dab6202019-01-02 16:42:29 +00002386 size_t const limbs = CHARS_TO_LIMBS( size );
Hanno Beckerda1655a2017-10-18 14:21:44 +01002387
Hanno Becker8ce11a32018-12-19 16:18:52 +00002388 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002389 MPI_VALIDATE_RET( f_rng != NULL );
Paul Bakker33dc46b2014-04-30 16:11:39 +02002390
Hanno Beckerda1655a2017-10-18 14:21:44 +01002391 /* Ensure that target MPI has exactly the necessary number of limbs */
Gilles Peskineed32b572021-06-02 22:17:52 +02002392 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002393 if( size == 0 )
2394 return( 0 );
Paul Bakker287781a2011-03-26 13:18:49 +00002395
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002396 ret = mpi_fill_random_internal( X, size, f_rng, p_rng );
Paul Bakker287781a2011-03-26 13:18:49 +00002397
2398cleanup:
2399 return( ret );
2400}
2401
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002402int mbedtls_mpi_random( mbedtls_mpi *X,
2403 mbedtls_mpi_sint min,
2404 const mbedtls_mpi *N,
2405 int (*f_rng)(void *, unsigned char *, size_t),
2406 void *p_rng )
2407{
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002408 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
Gilles Peskinee5381682021-04-13 21:23:25 +02002409 int count;
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002410 unsigned lt_lower = 1, lt_upper = 0;
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002411 size_t n_bits = mbedtls_mpi_bitlen( N );
2412 size_t n_bytes = ( n_bits + 7 ) / 8;
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002413 mbedtls_mpi lower_bound;
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002414
Gilles Peskine1e918f42021-03-29 22:14:51 +02002415 if( min < 0 )
2416 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2417 if( mbedtls_mpi_cmp_int( N, min ) <= 0 )
2418 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2419
Gilles Peskinee5381682021-04-13 21:23:25 +02002420 /*
2421 * When min == 0, each try has at worst a probability 1/2 of failing
2422 * (the msb has a probability 1/2 of being 0, and then the result will
2423 * be < N), so after 30 tries failure probability is a most 2**(-30).
2424 *
2425 * When N is just below a power of 2, as is the case when generating
Gilles Peskinee842e582021-04-15 11:45:19 +02002426 * a random scalar on most elliptic curves, 1 try is enough with
Gilles Peskinee5381682021-04-13 21:23:25 +02002427 * overwhelming probability. When N is just above a power of 2,
Gilles Peskinee842e582021-04-15 11:45:19 +02002428 * as when generating a random scalar on secp224k1, each try has
Gilles Peskinee5381682021-04-13 21:23:25 +02002429 * a probability of failing that is almost 1/2.
2430 *
2431 * The probabilities are almost the same if min is nonzero but negligible
2432 * compared to N. This is always the case when N is crypto-sized, but
2433 * it's convenient to support small N for testing purposes. When N
2434 * is small, use a higher repeat count, otherwise the probability of
2435 * failure is macroscopic.
2436 */
Gilles Peskine87823d72021-06-02 21:18:59 +02002437 count = ( n_bytes > 4 ? 30 : 250 );
Gilles Peskinee5381682021-04-13 21:23:25 +02002438
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002439 mbedtls_mpi_init( &lower_bound );
2440
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002441 /* Ensure that target MPI has exactly the same number of limbs
2442 * as the upper bound, even if the upper bound has leading zeros.
2443 * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
Gilles Peskineed32b572021-06-02 22:17:52 +02002444 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) );
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002445 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) );
2446 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) );
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002447
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002448 /*
2449 * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
2450 * when f_rng is a suitably parametrized instance of HMAC_DRBG:
2451 * - use the same byte ordering;
2452 * - keep the leftmost n_bits bits of the generated octet string;
2453 * - try until result is in the desired range.
2454 * This also avoids any bias, which is especially important for ECDSA.
2455 */
2456 do
2457 {
Gilles Peskine1a7df4e2021-04-01 15:57:18 +02002458 MBEDTLS_MPI_CHK( mpi_fill_random_internal( X, n_bytes, f_rng, p_rng ) );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002459 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, 8 * n_bytes - n_bits ) );
2460
Gilles Peskinee5381682021-04-13 21:23:25 +02002461 if( --count == 0 )
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002462 {
2463 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2464 goto cleanup;
2465 }
2466
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002467 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, &lt_lower ) );
2468 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, &lt_upper ) );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002469 }
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002470 while( lt_lower != 0 || lt_upper == 0 );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002471
2472cleanup:
Gilles Peskine5b0589e2021-04-13 21:09:10 +02002473 mbedtls_mpi_free( &lower_bound );
Gilles Peskine02ac93a2021-03-29 22:02:55 +02002474 return( ret );
2475}
2476
Paul Bakker5121ce52009-01-03 21:22:43 +00002477/*
2478 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2479 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002480int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00002481{
Janos Follath24eed8d2019-11-22 13:21:35 +00002482 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002483 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Hanno Becker73d7d792018-12-11 10:35:51 +00002484 MPI_VALIDATE_RET( X != NULL );
2485 MPI_VALIDATE_RET( A != NULL );
2486 MPI_VALIDATE_RET( N != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00002487
Hanno Becker4bcb4912017-04-18 15:49:39 +01002488 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002489 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002490
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002491 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2492 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2493 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002494
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002495 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002496
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002497 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002498 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002499 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002500 goto cleanup;
2501 }
2502
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002503 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2504 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2505 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2506 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002507
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002508 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2509 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2510 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2511 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002512
2513 do
2514 {
2515 while( ( TU.p[0] & 1 ) == 0 )
2516 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002517 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002518
2519 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2520 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002521 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2522 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002523 }
2524
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002525 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2526 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002527 }
2528
2529 while( ( TV.p[0] & 1 ) == 0 )
2530 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002531 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002532
2533 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2534 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002535 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2536 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002537 }
2538
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002539 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2540 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002541 }
2542
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002543 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002544 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002545 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2546 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2547 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002548 }
2549 else
2550 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002551 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2552 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2553 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002554 }
2555 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002556 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002557
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002558 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2559 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002560
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002561 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2562 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002563
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002564 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002565
2566cleanup:
2567
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002568 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2569 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2570 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002571
2572 return( ret );
2573}
2574
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002575#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00002576
Paul Bakker5121ce52009-01-03 21:22:43 +00002577static const int small_prime[] =
2578{
2579 3, 5, 7, 11, 13, 17, 19, 23,
2580 29, 31, 37, 41, 43, 47, 53, 59,
2581 61, 67, 71, 73, 79, 83, 89, 97,
2582 101, 103, 107, 109, 113, 127, 131, 137,
2583 139, 149, 151, 157, 163, 167, 173, 179,
2584 181, 191, 193, 197, 199, 211, 223, 227,
2585 229, 233, 239, 241, 251, 257, 263, 269,
2586 271, 277, 281, 283, 293, 307, 311, 313,
2587 317, 331, 337, 347, 349, 353, 359, 367,
2588 373, 379, 383, 389, 397, 401, 409, 419,
2589 421, 431, 433, 439, 443, 449, 457, 461,
2590 463, 467, 479, 487, 491, 499, 503, 509,
2591 521, 523, 541, 547, 557, 563, 569, 571,
2592 577, 587, 593, 599, 601, 607, 613, 617,
2593 619, 631, 641, 643, 647, 653, 659, 661,
2594 673, 677, 683, 691, 701, 709, 719, 727,
2595 733, 739, 743, 751, 757, 761, 769, 773,
2596 787, 797, 809, 811, 821, 823, 827, 829,
2597 839, 853, 857, 859, 863, 877, 881, 883,
2598 887, 907, 911, 919, 929, 937, 941, 947,
2599 953, 967, 971, 977, 983, 991, 997, -103
2600};
2601
2602/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002603 * Small divisors test (X must be positive)
2604 *
2605 * Return values:
2606 * 0: no small factor (possible prime, more tests needed)
2607 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002608 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002609 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002610 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002611static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002612{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002613 int ret = 0;
2614 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002615 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002616
Paul Bakker5121ce52009-01-03 21:22:43 +00002617 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002618 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002619
2620 for( i = 0; small_prime[i] > 0; i++ )
2621 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002622 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002623 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002624
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002625 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002626
2627 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002628 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002629 }
2630
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002631cleanup:
2632 return( ret );
2633}
2634
2635/*
2636 * Miller-Rabin pseudo-primality test (HAC 4.24)
2637 */
Janos Follathda31fa12018-09-03 14:45:23 +01002638static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002639 int (*f_rng)(void *, unsigned char *, size_t),
2640 void *p_rng )
2641{
Pascal Junodb99183d2015-03-11 16:49:45 +01002642 int ret, count;
Janos Follathda31fa12018-09-03 14:45:23 +01002643 size_t i, j, k, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002644 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002645
Hanno Becker8ce11a32018-12-19 16:18:52 +00002646 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002647 MPI_VALIDATE_RET( f_rng != NULL );
2648
2649 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2650 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002651 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002652
Paul Bakker5121ce52009-01-03 21:22:43 +00002653 /*
2654 * W = |X| - 1
2655 * R = W >> lsb( W )
2656 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002657 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2658 s = mbedtls_mpi_lsb( &W );
2659 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2660 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002661
Janos Follathda31fa12018-09-03 14:45:23 +01002662 for( i = 0; i < rounds; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002663 {
2664 /*
2665 * pick a random A, 1 < A < |X| - 1
2666 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002667 count = 0;
2668 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002669 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002670
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002671 j = mbedtls_mpi_bitlen( &A );
2672 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002673 if (j > k) {
Darryl Greene3f95ed2018-10-02 13:21:35 +01002674 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Pascal Junodb99183d2015-03-11 16:49:45 +01002675 }
2676
2677 if (count++ > 30) {
Jens Wiklanderf08aa3e2019-01-17 13:30:57 +01002678 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2679 goto cleanup;
Pascal Junodb99183d2015-03-11 16:49:45 +01002680 }
2681
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002682 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2683 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002684
2685 /*
2686 * A = A^R mod |X|
2687 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002688 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002689
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002690 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2691 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002692 continue;
2693
2694 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002695 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002696 {
2697 /*
2698 * A = A * A mod |X|
2699 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002700 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2701 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002702
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002703 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002704 break;
2705
2706 j++;
2707 }
2708
2709 /*
2710 * not prime if A != |X| - 1 or A == 1
2711 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002712 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2713 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002714 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002715 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002716 break;
2717 }
2718 }
2719
2720cleanup:
Hanno Becker73d7d792018-12-11 10:35:51 +00002721 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2722 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002723 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002724
2725 return( ret );
2726}
2727
2728/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002729 * Pseudo-primality test: small factors, then Miller-Rabin
2730 */
Janos Follatha0b67c22018-09-18 14:48:23 +01002731int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2732 int (*f_rng)(void *, unsigned char *, size_t),
2733 void *p_rng )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002734{
Janos Follath24eed8d2019-11-22 13:21:35 +00002735 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002736 mbedtls_mpi XX;
Hanno Becker8ce11a32018-12-19 16:18:52 +00002737 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002738 MPI_VALIDATE_RET( f_rng != NULL );
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002739
2740 XX.s = 1;
2741 XX.n = X->n;
2742 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002743
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002744 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2745 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2746 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002747
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002748 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002749 return( 0 );
2750
2751 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2752 {
2753 if( ret == 1 )
2754 return( 0 );
2755
2756 return( ret );
2757 }
2758
Janos Follathda31fa12018-09-03 14:45:23 +01002759 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
Janos Follathf301d232018-08-14 13:34:01 +01002760}
2761
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002762/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002763 * Prime number generation
Jethro Beekman66689272018-02-14 19:24:10 -08002764 *
Janos Follathf301d232018-08-14 13:34:01 +01002765 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2766 * be either 1024 bits or 1536 bits long, and flags must contain
2767 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Paul Bakker5121ce52009-01-03 21:22:43 +00002768 */
Janos Follath7c025a92018-08-14 11:08:41 +01002769int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002770 int (*f_rng)(void *, unsigned char *, size_t),
2771 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002772{
Jethro Beekman66689272018-02-14 19:24:10 -08002773#ifdef MBEDTLS_HAVE_INT64
2774// ceil(2^63.5)
2775#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2776#else
2777// ceil(2^31.5)
2778#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2779#endif
2780 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker23986e52011-04-24 08:57:21 +00002781 size_t k, n;
Janos Follathda31fa12018-09-03 14:45:23 +01002782 int rounds;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002783 mbedtls_mpi_uint r;
2784 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002785
Hanno Becker8ce11a32018-12-19 16:18:52 +00002786 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002787 MPI_VALIDATE_RET( f_rng != NULL );
2788
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002789 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2790 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002791
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002792 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002793
2794 n = BITS_TO_LIMBS( nbits );
2795
Janos Follathda31fa12018-09-03 14:45:23 +01002796 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2797 {
2798 /*
2799 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2800 */
2801 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2802 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2803 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2804 }
2805 else
2806 {
2807 /*
2808 * 2^-100 error probability, number of rounds computed based on HAC,
2809 * fact 4.48
2810 */
2811 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2812 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2813 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2814 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2815 }
2816
Jethro Beekman66689272018-02-14 19:24:10 -08002817 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002818 {
Jethro Beekman66689272018-02-14 19:24:10 -08002819 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2820 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2821 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2822
2823 k = n * biL;
2824 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2825 X->p[0] |= 1;
2826
Janos Follath7c025a92018-08-14 11:08:41 +01002827 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002828 {
Janos Follatha0b67c22018-09-18 14:48:23 +01002829 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
Jethro Beekman66689272018-02-14 19:24:10 -08002830
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002831 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002832 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002833 }
Jethro Beekman66689272018-02-14 19:24:10 -08002834 else
Paul Bakker5121ce52009-01-03 21:22:43 +00002835 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002836 /*
Jethro Beekman66689272018-02-14 19:24:10 -08002837 * An necessary condition for Y and X = 2Y + 1 to be prime
2838 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2839 * Make sure it is satisfied, while keeping X = 3 mod 4
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002840 */
Jethro Beekman66689272018-02-14 19:24:10 -08002841
2842 X->p[0] |= 2;
2843
2844 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2845 if( r == 0 )
2846 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2847 else if( r == 1 )
2848 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2849
2850 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2851 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2852 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2853
2854 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002855 {
Jethro Beekman66689272018-02-14 19:24:10 -08002856 /*
2857 * First, check small factors for X and Y
2858 * before doing Miller-Rabin on any of them
2859 */
2860 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2861 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002862 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002863 == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002864 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002865 == 0 )
Jethro Beekman66689272018-02-14 19:24:10 -08002866 goto cleanup;
2867
2868 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2869 goto cleanup;
2870
2871 /*
2872 * Next candidates. We want to preserve Y = (X-1) / 2 and
2873 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2874 * so up Y by 6 and X by 12.
2875 */
2876 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2877 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002878 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002879 }
2880 }
2881
2882cleanup:
2883
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002884 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002885
2886 return( ret );
2887}
2888
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002889#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002890
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002891#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002892
Paul Bakker23986e52011-04-24 08:57:21 +00002893#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002894
2895static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2896{
2897 { 693, 609, 21 },
2898 { 1764, 868, 28 },
2899 { 768454923, 542167814, 1 }
2900};
2901
Paul Bakker5121ce52009-01-03 21:22:43 +00002902/*
2903 * Checkup routine
2904 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002905int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002906{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002907 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002908 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002909
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002910 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2911 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002912
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002913 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002914 "EFE021C2645FD1DC586E69184AF4A31E" \
2915 "D5F53E93B5F123FA41680867BA110131" \
2916 "944FE7952E2517337780CB0DB80E61AA" \
2917 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2918
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002919 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002920 "B2E7EFD37075B9F03FF989C7C5051C20" \
2921 "34D2A323810251127E7BF8625A4F49A5" \
2922 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2923 "5B5C25763222FEFCCFC38B832366C29E" ) );
2924
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002925 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002926 "0066A198186C18C10B2F5ED9B522752A" \
2927 "9830B69916E535C8F047518A889A43A5" \
2928 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2929
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002930 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002931
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002932 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002933 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2934 "9E857EA95A03512E2BAE7391688D264A" \
2935 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2936 "8001B72E848A38CAE1C65F78E56ABDEF" \
2937 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2938 "ECF677152EF804370C1A305CAF3B5BF1" \
2939 "30879B56C61DE584A0F53A2447A51E" ) );
2940
2941 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002942 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002943
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002944 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002945 {
2946 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002947 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002948
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002949 ret = 1;
2950 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002951 }
2952
2953 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002954 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002955
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002956 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002957
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002958 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002959 "256567336059E52CAE22925474705F39A94" ) );
2960
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002961 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002962 "6613F26162223DF488E9CD48CC132C7A" \
2963 "0AC93C701B001B092E4E5B9F73BCD27B" \
2964 "9EE50D0657C77F374E903CDFA4C642" ) );
2965
2966 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002967 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002968
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002969 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2970 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002971 {
2972 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002973 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002974
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002975 ret = 1;
2976 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002977 }
2978
2979 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002980 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002981
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002982 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002983
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002984 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002985 "36E139AEA55215609D2816998ED020BB" \
2986 "BD96C37890F65171D948E9BC7CBAA4D9" \
2987 "325D24D6A3C12710F10A09FA08AB87" ) );
2988
2989 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002990 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002991
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002992 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002993 {
2994 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002995 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002996
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002997 ret = 1;
2998 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002999 }
3000
3001 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003002 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00003003
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003004 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00003005
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003006 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00003007 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
3008 "C3DBA76456363A10869622EAC2DD84EC" \
3009 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
3010
3011 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003012 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00003013
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003014 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00003015 {
3016 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003017 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00003018
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01003019 ret = 1;
3020 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00003021 }
3022
3023 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003024 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00003025
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003026 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003027 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003028
Paul Bakker66d5d072014-06-17 16:39:18 +02003029 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003030 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003031 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
3032 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003033
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003034 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003035
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003036 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01003037 {
3038 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003039 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003040
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01003041 ret = 1;
3042 goto cleanup;
3043 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003044 }
3045
3046 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003047 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00003048
Paul Bakker5121ce52009-01-03 21:22:43 +00003049cleanup:
3050
3051 if( ret != 0 && verbose != 0 )
Kenneth Soerensen518d4352020-04-01 17:22:45 +02003052 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00003053
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003054 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
3055 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00003056
3057 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003058 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00003059
3060 return( ret );
3061}
3062
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003063#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00003064
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003065#endif /* MBEDTLS_BIGNUM_C */