blob: 41daf579c4766a387f818cdae495e55db55495b1 [file] [log] [blame]
Paul Bakker5121ce52009-01-03 21:22:43 +00001/*
2 * Multi-precision integer library
3 *
Manuel Pégourié-Gonnard6fb81872015-07-27 11:11:48 +02004 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
Manuel Pégourié-Gonnard37ff1402015-09-04 14:21:07 +02005 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
Paul Bakkerb96f1542010-07-18 20:36:00 +000018 *
Manuel Pégourié-Gonnardfe446432015-03-06 13:17:10 +000019 * This file is part of mbed TLS (https://tls.mbed.org)
Paul Bakker5121ce52009-01-03 21:22:43 +000020 */
Simon Butcher15b15d12015-11-26 19:35:03 +000021
Paul Bakker5121ce52009-01-03 21:22:43 +000022/*
Simon Butcher15b15d12015-11-26 19:35:03 +000023 * The following sources were referenced in the design of this Multi-precision
24 * Integer library:
Paul Bakker5121ce52009-01-03 21:22:43 +000025 *
Simon Butcher15b15d12015-11-26 19:35:03 +000026 * [1] Handbook of Applied Cryptography - 1997
27 * Menezes, van Oorschot and Vanstone
28 *
29 * [2] Multi-Precision Math
30 * Tom St Denis
31 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
32 *
33 * [3] GNU Multi-Precision Arithmetic Library
34 * https://gmplib.org/manual/index.html
35 *
Simon Butcherf5ba0452015-12-27 23:01:55 +000036 */
Paul Bakker5121ce52009-01-03 21:22:43 +000037
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020038#if !defined(MBEDTLS_CONFIG_FILE)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000039#include "mbedtls/config.h"
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020040#else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020041#include MBEDTLS_CONFIG_FILE
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020042#endif
Paul Bakker5121ce52009-01-03 21:22:43 +000043
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020044#if defined(MBEDTLS_BIGNUM_C)
Paul Bakker5121ce52009-01-03 21:22:43 +000045
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000046#include "mbedtls/bignum.h"
47#include "mbedtls/bn_mul.h"
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050048#include "mbedtls/platform_util.h"
Janos Follath24eed8d2019-11-22 13:21:35 +000049#include "mbedtls/error.h"
Paul Bakker5121ce52009-01-03 21:22:43 +000050
Rich Evans00ab4702015-02-06 13:43:58 +000051#include <string.h>
52
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020053#if defined(MBEDTLS_PLATFORM_C)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000054#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020055#else
Rich Evans00ab4702015-02-06 13:43:58 +000056#include <stdio.h>
57#include <stdlib.h>
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020058#define mbedtls_printf printf
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +020059#define mbedtls_calloc calloc
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020060#define mbedtls_free free
Paul Bakker6e339b52013-07-03 13:37:05 +020061#endif
62
Hanno Becker73d7d792018-12-11 10:35:51 +000063#define MPI_VALIDATE_RET( cond ) \
64 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
65#define MPI_VALIDATE( cond ) \
66 MBEDTLS_INTERNAL_VALIDATE( cond )
67
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020068#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
Paul Bakker5121ce52009-01-03 21:22:43 +000069#define biL (ciL << 3) /* bits in limb */
70#define biH (ciL << 2) /* half limb size */
71
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +010072#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
73
Paul Bakker5121ce52009-01-03 21:22:43 +000074/*
75 * Convert between bits/chars and number of limbs
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020076 * Divide first in order to avoid potential overflows
Paul Bakker5121ce52009-01-03 21:22:43 +000077 */
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020078#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
79#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
Paul Bakker5121ce52009-01-03 21:22:43 +000080
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050081/* Implementation that should never be optimized out by the compiler */
Andres Amaya Garcia6698d2f2018-04-24 08:39:07 -050082static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
83{
Andres Amaya Garcia1f6301b2018-04-17 09:51:09 -050084 mbedtls_platform_zeroize( v, ciL * n );
85}
86
Paul Bakker5121ce52009-01-03 21:22:43 +000087/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000088 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000089 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020090void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000091{
Hanno Becker73d7d792018-12-11 10:35:51 +000092 MPI_VALIDATE( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +000093
Paul Bakker6c591fa2011-05-05 11:49:20 +000094 X->s = 1;
95 X->n = 0;
96 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +000097}
98
99/*
Paul Bakker6c591fa2011-05-05 11:49:20 +0000100 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +0000101 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200102void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000103{
Paul Bakker6c591fa2011-05-05 11:49:20 +0000104 if( X == NULL )
105 return;
Paul Bakker5121ce52009-01-03 21:22:43 +0000106
Paul Bakker6c591fa2011-05-05 11:49:20 +0000107 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +0000108 {
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200109 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200110 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000111 }
112
Paul Bakker6c591fa2011-05-05 11:49:20 +0000113 X->s = 1;
114 X->n = 0;
115 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000116}
117
118/*
119 * Enlarge to the specified number of limbs
120 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200121int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000122{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200123 mbedtls_mpi_uint *p;
Hanno Becker73d7d792018-12-11 10:35:51 +0000124 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000125
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200126 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200127 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000128
Paul Bakker5121ce52009-01-03 21:22:43 +0000129 if( X->n < nblimbs )
130 {
Simon Butcher29176892016-05-20 00:19:09 +0100131 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200132 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000133
Paul Bakker5121ce52009-01-03 21:22:43 +0000134 if( X->p != NULL )
135 {
136 memcpy( p, X->p, X->n * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200137 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200138 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000139 }
140
141 X->n = nblimbs;
142 X->p = p;
143 }
144
145 return( 0 );
146}
147
148/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100149 * Resize down as much as possible,
150 * while keeping at least the specified number of limbs
151 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200152int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100153{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200154 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100155 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000156 MPI_VALIDATE_RET( X != NULL );
157
158 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
159 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100160
Gilles Peskinee2f563e2020-01-20 21:17:43 +0100161 /* Actually resize up if there are currently fewer than nblimbs limbs. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100162 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200163 return( mbedtls_mpi_grow( X, nblimbs ) );
Gilles Peskine322752b2020-01-21 13:59:51 +0100164 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100165
166 for( i = X->n - 1; i > 0; i-- )
167 if( X->p[i] != 0 )
168 break;
169 i++;
170
171 if( i < nblimbs )
172 i = nblimbs;
173
Simon Butcher29176892016-05-20 00:19:09 +0100174 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200175 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100176
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100177 if( X->p != NULL )
178 {
179 memcpy( p, X->p, i * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200180 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200181 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100182 }
183
184 X->n = i;
185 X->p = p;
186
187 return( 0 );
188}
189
190/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000191 * Copy the contents of Y into X
192 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200193int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000194{
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100195 int ret = 0;
Paul Bakker23986e52011-04-24 08:57:21 +0000196 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000197 MPI_VALIDATE_RET( X != NULL );
198 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000199
200 if( X == Y )
201 return( 0 );
202
Gilles Peskinedb420622020-01-20 21:12:50 +0100203 if( Y->n == 0 )
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200204 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200205 mbedtls_mpi_free( X );
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200206 return( 0 );
207 }
208
Paul Bakker5121ce52009-01-03 21:22:43 +0000209 for( i = Y->n - 1; i > 0; i-- )
210 if( Y->p[i] != 0 )
211 break;
212 i++;
213
214 X->s = Y->s;
215
Gilles Peskine4e4be7c2018-03-21 16:29:03 +0100216 if( X->n < i )
217 {
218 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
219 }
220 else
221 {
222 memset( X->p + i, 0, ( X->n - i ) * ciL );
223 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000224
Paul Bakker5121ce52009-01-03 21:22:43 +0000225 memcpy( X->p, Y->p, i * ciL );
226
227cleanup:
228
229 return( ret );
230}
231
232/*
233 * Swap the contents of X and Y
234 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200235void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000236{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200237 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000238 MPI_VALIDATE( X != NULL );
239 MPI_VALIDATE( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000240
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200241 memcpy( &T, X, sizeof( mbedtls_mpi ) );
242 memcpy( X, Y, sizeof( mbedtls_mpi ) );
243 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000244}
245
246/*
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100247 * Conditionally assign X = Y, without leaking information
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100248 * about whether the assignment was made or not.
249 * (Leaking information about the respective sizes of X and Y is ok however.)
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100250 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200251int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100252{
253 int ret = 0;
254 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000255 MPI_VALIDATE_RET( X != NULL );
256 MPI_VALIDATE_RET( Y != NULL );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100257
Pascal Junodb99183d2015-03-11 16:49:45 +0100258 /* make sure assign is 0 or 1 in a time-constant manner */
259 assign = (assign | (unsigned char)-assign) >> 7;
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100260
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200261 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100262
Paul Bakker66d5d072014-06-17 16:39:18 +0200263 X->s = X->s * ( 1 - assign ) + Y->s * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100264
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100265 for( i = 0; i < Y->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200266 X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100267
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100268 for( ; i < X->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200269 X->p[i] *= ( 1 - assign );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100270
271cleanup:
272 return( ret );
273}
274
275/*
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100276 * Conditionally swap X and Y, without leaking information
277 * about whether the swap was made or not.
278 * Here it is not ok to simply swap the pointers, which whould lead to
279 * different memory access patterns when X and Y are used afterwards.
280 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200281int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100282{
283 int ret, s;
284 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200285 mbedtls_mpi_uint tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +0000286 MPI_VALIDATE_RET( X != NULL );
287 MPI_VALIDATE_RET( Y != NULL );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100288
289 if( X == Y )
290 return( 0 );
291
Pascal Junodb99183d2015-03-11 16:49:45 +0100292 /* make sure swap is 0 or 1 in a time-constant manner */
293 swap = (swap | (unsigned char)-swap) >> 7;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100294
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200295 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
296 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100297
298 s = X->s;
Paul Bakker66d5d072014-06-17 16:39:18 +0200299 X->s = X->s * ( 1 - swap ) + Y->s * swap;
300 Y->s = Y->s * ( 1 - swap ) + s * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100301
302
303 for( i = 0; i < X->n; i++ )
304 {
305 tmp = X->p[i];
Paul Bakker66d5d072014-06-17 16:39:18 +0200306 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
307 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100308 }
309
310cleanup:
311 return( ret );
312}
313
314/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000315 * Set value from integer
316 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200317int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000318{
Janos Follath24eed8d2019-11-22 13:21:35 +0000319 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +0000320 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000321
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200322 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000323 memset( X->p, 0, X->n * ciL );
324
325 X->p[0] = ( z < 0 ) ? -z : z;
326 X->s = ( z < 0 ) ? -1 : 1;
327
328cleanup:
329
330 return( ret );
331}
332
333/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000334 * Get a specific bit
335 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200336int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000337{
Hanno Becker73d7d792018-12-11 10:35:51 +0000338 MPI_VALIDATE_RET( X != NULL );
339
Paul Bakker2f5947e2011-05-18 15:47:11 +0000340 if( X->n * biL <= pos )
341 return( 0 );
342
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200343 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000344}
345
Gilles Peskine11cdb052018-11-20 16:47:47 +0100346/* Get a specific byte, without range checks. */
347#define GET_BYTE( X, i ) \
348 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
349
Paul Bakker2f5947e2011-05-18 15:47:11 +0000350/*
351 * Set a bit to a specific value of 0 or 1
352 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200353int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000354{
355 int ret = 0;
356 size_t off = pos / biL;
357 size_t idx = pos % biL;
Hanno Becker73d7d792018-12-11 10:35:51 +0000358 MPI_VALIDATE_RET( X != NULL );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000359
360 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200361 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200362
Paul Bakker2f5947e2011-05-18 15:47:11 +0000363 if( X->n * biL <= pos )
364 {
365 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200366 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000367
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200368 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000369 }
370
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200371 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
372 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000373
374cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200375
Paul Bakker2f5947e2011-05-18 15:47:11 +0000376 return( ret );
377}
378
379/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200380 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000381 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200382size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000383{
Paul Bakker23986e52011-04-24 08:57:21 +0000384 size_t i, j, count = 0;
Hanno Beckerf25ee7f2018-12-19 16:51:02 +0000385 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000386
387 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000388 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000389 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
390 return( count );
391
392 return( 0 );
393}
394
395/*
Simon Butcher15b15d12015-11-26 19:35:03 +0000396 * Count leading zero bits in a given integer
397 */
398static size_t mbedtls_clz( const mbedtls_mpi_uint x )
399{
400 size_t j;
Manuel Pégourié-Gonnarde3e8edf2015-12-01 09:31:52 +0100401 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
Simon Butcher15b15d12015-11-26 19:35:03 +0000402
403 for( j = 0; j < biL; j++ )
404 {
405 if( x & mask ) break;
406
407 mask >>= 1;
408 }
409
410 return j;
411}
412
413/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200414 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000415 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200416size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000417{
Paul Bakker23986e52011-04-24 08:57:21 +0000418 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000419
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200420 if( X->n == 0 )
421 return( 0 );
422
Paul Bakker5121ce52009-01-03 21:22:43 +0000423 for( i = X->n - 1; i > 0; i-- )
424 if( X->p[i] != 0 )
425 break;
426
Simon Butcher15b15d12015-11-26 19:35:03 +0000427 j = biL - mbedtls_clz( X->p[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +0000428
Paul Bakker23986e52011-04-24 08:57:21 +0000429 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000430}
431
432/*
433 * Return the total size in bytes
434 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200435size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000436{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200437 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000438}
439
440/*
441 * Convert an ASCII character to digit value
442 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200443static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000444{
445 *d = 255;
446
447 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
448 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
449 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
450
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200451 if( *d >= (mbedtls_mpi_uint) radix )
452 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000453
454 return( 0 );
455}
456
457/*
458 * Import from an ASCII string
459 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200460int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000461{
Janos Follath24eed8d2019-11-22 13:21:35 +0000462 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000463 size_t i, j, slen, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200464 mbedtls_mpi_uint d;
465 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000466 MPI_VALIDATE_RET( X != NULL );
467 MPI_VALIDATE_RET( s != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000468
469 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000470 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000471
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200472 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000473
Paul Bakkerff60ee62010-03-16 21:09:09 +0000474 slen = strlen( s );
475
Paul Bakker5121ce52009-01-03 21:22:43 +0000476 if( radix == 16 )
477 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100478 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200479 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
480
Paul Bakkerff60ee62010-03-16 21:09:09 +0000481 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000482
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200483 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
484 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000485
Paul Bakker23986e52011-04-24 08:57:21 +0000486 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000487 {
Paul Bakker23986e52011-04-24 08:57:21 +0000488 if( i == 1 && s[i - 1] == '-' )
Paul Bakker5121ce52009-01-03 21:22:43 +0000489 {
490 X->s = -1;
491 break;
492 }
493
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200494 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200495 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000496 }
497 }
498 else
499 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200500 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000501
Paul Bakkerff60ee62010-03-16 21:09:09 +0000502 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000503 {
504 if( i == 0 && s[i] == '-' )
505 {
506 X->s = -1;
507 continue;
508 }
509
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200510 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
511 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000512
513 if( X->s == 1 )
514 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200515 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000516 }
517 else
518 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200519 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000520 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000521 }
522 }
523
524cleanup:
525
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200526 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000527
528 return( ret );
529}
530
531/*
Ron Eldora16fa292018-11-20 14:07:01 +0200532 * Helper to write the digits high-order first.
Paul Bakker5121ce52009-01-03 21:22:43 +0000533 */
Ron Eldora16fa292018-11-20 14:07:01 +0200534static int mpi_write_hlp( mbedtls_mpi *X, int radix,
535 char **p, const size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000536{
Janos Follath24eed8d2019-11-22 13:21:35 +0000537 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200538 mbedtls_mpi_uint r;
Ron Eldora16fa292018-11-20 14:07:01 +0200539 size_t length = 0;
540 char *p_end = *p + buflen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000541
Ron Eldora16fa292018-11-20 14:07:01 +0200542 do
543 {
544 if( length >= buflen )
545 {
546 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
547 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000548
Ron Eldora16fa292018-11-20 14:07:01 +0200549 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
550 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
551 /*
552 * Write the residue in the current position, as an ASCII character.
553 */
554 if( r < 0xA )
555 *(--p_end) = (char)( '0' + r );
556 else
557 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000558
Ron Eldora16fa292018-11-20 14:07:01 +0200559 length++;
560 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000561
Ron Eldora16fa292018-11-20 14:07:01 +0200562 memmove( *p, p_end, length );
563 *p += length;
Paul Bakker5121ce52009-01-03 21:22:43 +0000564
565cleanup:
566
567 return( ret );
568}
569
570/*
571 * Export into an ASCII string
572 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100573int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
574 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000575{
Paul Bakker23986e52011-04-24 08:57:21 +0000576 int ret = 0;
577 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000578 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200579 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000580 MPI_VALIDATE_RET( X != NULL );
581 MPI_VALIDATE_RET( olen != NULL );
582 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000583
584 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000585 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000586
Hanno Becker23cfea02019-02-04 09:45:07 +0000587 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
588 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
589 * `n`. If radix > 4, this might be a strict
590 * overapproximation of the number of
591 * radix-adic digits needed to present `n`. */
592 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
593 * present `n`. */
594
Janos Follath80470622019-03-06 13:43:02 +0000595 n += 1; /* Terminating null byte */
Hanno Becker23cfea02019-02-04 09:45:07 +0000596 n += 1; /* Compensate for the divisions above, which round down `n`
597 * in case it's not even. */
598 n += 1; /* Potential '-'-sign. */
599 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
600 * which always uses an even number of hex-digits. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000601
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100602 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000603 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100604 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200605 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000606 }
607
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100608 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200609 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000610
611 if( X->s == -1 )
Hanno Beckerc983c812019-02-01 16:41:30 +0000612 {
Paul Bakker5121ce52009-01-03 21:22:43 +0000613 *p++ = '-';
Hanno Beckerc983c812019-02-01 16:41:30 +0000614 buflen--;
615 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000616
617 if( radix == 16 )
618 {
Paul Bakker23986e52011-04-24 08:57:21 +0000619 int c;
620 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000621
Paul Bakker23986e52011-04-24 08:57:21 +0000622 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000623 {
Paul Bakker23986e52011-04-24 08:57:21 +0000624 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000625 {
Paul Bakker23986e52011-04-24 08:57:21 +0000626 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000627
Paul Bakker6c343d72014-07-10 14:36:19 +0200628 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000629 continue;
630
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000631 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000632 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000633 k = 1;
634 }
635 }
636 }
637 else
638 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200639 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000640
641 if( T.s == -1 )
642 T.s = 1;
643
Ron Eldora16fa292018-11-20 14:07:01 +0200644 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000645 }
646
647 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100648 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000649
650cleanup:
651
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200652 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000653
654 return( ret );
655}
656
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200657#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000658/*
659 * Read X from an opened file
660 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200661int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000662{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200663 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000664 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000665 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000666 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000667 * Buffer should have space for (short) label and decimal formatted MPI,
668 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000669 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200670 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000671
Hanno Becker73d7d792018-12-11 10:35:51 +0000672 MPI_VALIDATE_RET( X != NULL );
673 MPI_VALIDATE_RET( fin != NULL );
674
675 if( radix < 2 || radix > 16 )
676 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
677
Paul Bakker5121ce52009-01-03 21:22:43 +0000678 memset( s, 0, sizeof( s ) );
679 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200680 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000681
682 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000683 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200684 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000685
Hanno Beckerb2034b72017-04-26 11:46:46 +0100686 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
687 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000688
689 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100690 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000691 if( mpi_get_digit( &d, radix, *p ) != 0 )
692 break;
693
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200694 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000695}
696
697/*
698 * Write X into an opened file (or stdout if fout == NULL)
699 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200700int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000701{
Janos Follath24eed8d2019-11-22 13:21:35 +0000702 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000703 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000704 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000705 * Buffer should have space for (short) label and decimal formatted MPI,
706 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000707 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200708 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Hanno Becker73d7d792018-12-11 10:35:51 +0000709 MPI_VALIDATE_RET( X != NULL );
710
711 if( radix < 2 || radix > 16 )
712 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000713
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100714 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000715
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100716 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000717
718 if( p == NULL ) p = "";
719
720 plen = strlen( p );
721 slen = strlen( s );
722 s[slen++] = '\r';
723 s[slen++] = '\n';
724
725 if( fout != NULL )
726 {
727 if( fwrite( p, 1, plen, fout ) != plen ||
728 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200729 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000730 }
731 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200732 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000733
734cleanup:
735
736 return( ret );
737}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200738#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000739
Hanno Beckerda1655a2017-10-18 14:21:44 +0100740
741/* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
742 * into the storage form used by mbedtls_mpi. */
Hanno Beckerf8720072018-11-08 11:53:49 +0000743
744static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x )
745{
746 uint8_t i;
Hanno Becker031d6332019-05-01 17:09:11 +0100747 unsigned char *x_ptr;
Hanno Beckerf8720072018-11-08 11:53:49 +0000748 mbedtls_mpi_uint tmp = 0;
Hanno Becker031d6332019-05-01 17:09:11 +0100749
750 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ )
751 {
752 tmp <<= CHAR_BIT;
753 tmp |= (mbedtls_mpi_uint) *x_ptr;
754 }
755
Hanno Beckerf8720072018-11-08 11:53:49 +0000756 return( tmp );
757}
758
759static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x )
760{
761#if defined(__BYTE_ORDER__)
762
763/* Nothing to do on bigendian systems. */
764#if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ )
765 return( x );
766#endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
767
768#if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ )
769
770/* For GCC and Clang, have builtins for byte swapping. */
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000771#if defined(__GNUC__) && defined(__GNUC_PREREQ)
772#if __GNUC_PREREQ(4,3)
Hanno Beckerf8720072018-11-08 11:53:49 +0000773#define have_bswap
774#endif
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000775#endif
776
777#if defined(__clang__) && defined(__has_builtin)
778#if __has_builtin(__builtin_bswap32) && \
779 __has_builtin(__builtin_bswap64)
780#define have_bswap
781#endif
782#endif
783
Hanno Beckerf8720072018-11-08 11:53:49 +0000784#if defined(have_bswap)
785 /* The compiler is hopefully able to statically evaluate this! */
786 switch( sizeof(mbedtls_mpi_uint) )
787 {
788 case 4:
789 return( __builtin_bswap32(x) );
790 case 8:
791 return( __builtin_bswap64(x) );
792 }
793#endif
794#endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */
795#endif /* __BYTE_ORDER__ */
796
797 /* Fall back to C-based reordering if we don't know the byte order
798 * or we couldn't use a compiler-specific builtin. */
799 return( mpi_uint_bigendian_to_host_c( x ) );
800}
801
Hanno Becker2be8a552018-10-25 12:40:09 +0100802static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs )
Hanno Beckerda1655a2017-10-18 14:21:44 +0100803{
Hanno Beckerda1655a2017-10-18 14:21:44 +0100804 mbedtls_mpi_uint *cur_limb_left;
805 mbedtls_mpi_uint *cur_limb_right;
Hanno Becker2be8a552018-10-25 12:40:09 +0100806 if( limbs == 0 )
807 return;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100808
809 /*
810 * Traverse limbs and
811 * - adapt byte-order in each limb
812 * - swap the limbs themselves.
813 * For that, simultaneously traverse the limbs from left to right
814 * and from right to left, as long as the left index is not bigger
815 * than the right index (it's not a problem if limbs is odd and the
816 * indices coincide in the last iteration).
817 */
Hanno Beckerda1655a2017-10-18 14:21:44 +0100818 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 );
819 cur_limb_left <= cur_limb_right;
820 cur_limb_left++, cur_limb_right-- )
821 {
Hanno Beckerf8720072018-11-08 11:53:49 +0000822 mbedtls_mpi_uint tmp;
823 /* Note that if cur_limb_left == cur_limb_right,
824 * this code effectively swaps the bytes only once. */
825 tmp = mpi_uint_bigendian_to_host( *cur_limb_left );
826 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right );
827 *cur_limb_right = tmp;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100828 }
Hanno Beckerda1655a2017-10-18 14:21:44 +0100829}
830
Paul Bakker5121ce52009-01-03 21:22:43 +0000831/*
Janos Follatha778a942019-02-13 10:28:28 +0000832 * Import X from unsigned binary data, little endian
833 */
834int mbedtls_mpi_read_binary_le( mbedtls_mpi *X,
835 const unsigned char *buf, size_t buflen )
836{
Janos Follath24eed8d2019-11-22 13:21:35 +0000837 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follatha778a942019-02-13 10:28:28 +0000838 size_t i;
839 size_t const limbs = CHARS_TO_LIMBS( buflen );
840
841 /* Ensure that target MPI has exactly the necessary number of limbs */
842 if( X->n != limbs )
843 {
844 mbedtls_mpi_free( X );
845 mbedtls_mpi_init( X );
846 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
847 }
848
849 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
850
851 for( i = 0; i < buflen; i++ )
852 X->p[i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3);
853
854cleanup:
855
Janos Follath171a7ef2019-02-15 16:17:45 +0000856 /*
857 * This function is also used to import keys. However, wiping the buffers
858 * upon failure is not necessary because failure only can happen before any
859 * input is copied.
860 */
Janos Follatha778a942019-02-13 10:28:28 +0000861 return( ret );
862}
863
864/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000865 * Import X from unsigned binary data, big endian
866 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200867int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000868{
Janos Follath24eed8d2019-11-22 13:21:35 +0000869 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100870 size_t const limbs = CHARS_TO_LIMBS( buflen );
871 size_t const overhead = ( limbs * ciL ) - buflen;
872 unsigned char *Xp;
Paul Bakker5121ce52009-01-03 21:22:43 +0000873
Hanno Becker8ce11a32018-12-19 16:18:52 +0000874 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +0000875 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
876
Hanno Becker073c1992017-10-17 15:17:27 +0100877 /* Ensure that target MPI has exactly the necessary number of limbs */
878 if( X->n != limbs )
879 {
880 mbedtls_mpi_free( X );
881 mbedtls_mpi_init( X );
882 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
883 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200884 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000885
Hanno Becker0e810b92019-01-03 17:13:11 +0000886 /* Avoid calling `memcpy` with NULL source argument,
887 * even if buflen is 0. */
888 if( buf != NULL )
889 {
890 Xp = (unsigned char*) X->p;
891 memcpy( Xp + overhead, buf, buflen );
Hanno Beckerda1655a2017-10-18 14:21:44 +0100892
Hanno Becker0e810b92019-01-03 17:13:11 +0000893 mpi_bigendian_to_host( X->p, limbs );
894 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000895
896cleanup:
897
Janos Follath171a7ef2019-02-15 16:17:45 +0000898 /*
899 * This function is also used to import keys. However, wiping the buffers
900 * upon failure is not necessary because failure only can happen before any
901 * input is copied.
902 */
Paul Bakker5121ce52009-01-03 21:22:43 +0000903 return( ret );
904}
905
906/*
Janos Follathe344d0f2019-02-19 16:17:40 +0000907 * Export X into unsigned binary data, little endian
908 */
909int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X,
910 unsigned char *buf, size_t buflen )
911{
912 size_t stored_bytes = X->n * ciL;
913 size_t bytes_to_copy;
914 size_t i;
915
916 if( stored_bytes < buflen )
917 {
918 bytes_to_copy = stored_bytes;
919 }
920 else
921 {
922 bytes_to_copy = buflen;
923
924 /* The output buffer is smaller than the allocated size of X.
925 * However X may fit if its leading bytes are zero. */
926 for( i = bytes_to_copy; i < stored_bytes; i++ )
927 {
928 if( GET_BYTE( X, i ) != 0 )
929 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
930 }
931 }
932
933 for( i = 0; i < bytes_to_copy; i++ )
934 buf[i] = GET_BYTE( X, i );
935
936 if( stored_bytes < buflen )
937 {
938 /* Write trailing 0 bytes */
939 memset( buf + stored_bytes, 0, buflen - stored_bytes );
940 }
941
942 return( 0 );
943}
944
945/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000946 * Export X into unsigned binary data, big endian
947 */
Gilles Peskine11cdb052018-11-20 16:47:47 +0100948int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
949 unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000950{
Hanno Becker73d7d792018-12-11 10:35:51 +0000951 size_t stored_bytes;
Gilles Peskine11cdb052018-11-20 16:47:47 +0100952 size_t bytes_to_copy;
953 unsigned char *p;
954 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000955
Hanno Becker73d7d792018-12-11 10:35:51 +0000956 MPI_VALIDATE_RET( X != NULL );
957 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
958
959 stored_bytes = X->n * ciL;
960
Gilles Peskine11cdb052018-11-20 16:47:47 +0100961 if( stored_bytes < buflen )
962 {
963 /* There is enough space in the output buffer. Write initial
964 * null bytes and record the position at which to start
965 * writing the significant bytes. In this case, the execution
966 * trace of this function does not depend on the value of the
967 * number. */
968 bytes_to_copy = stored_bytes;
969 p = buf + buflen - stored_bytes;
970 memset( buf, 0, buflen - stored_bytes );
971 }
972 else
973 {
974 /* The output buffer is smaller than the allocated size of X.
975 * However X may fit if its leading bytes are zero. */
976 bytes_to_copy = buflen;
977 p = buf;
978 for( i = bytes_to_copy; i < stored_bytes; i++ )
979 {
980 if( GET_BYTE( X, i ) != 0 )
981 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
982 }
983 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000984
Gilles Peskine11cdb052018-11-20 16:47:47 +0100985 for( i = 0; i < bytes_to_copy; i++ )
986 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
Paul Bakker5121ce52009-01-03 21:22:43 +0000987
988 return( 0 );
989}
990
991/*
992 * Left-shift: X <<= count
993 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200994int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000995{
Janos Follath24eed8d2019-11-22 13:21:35 +0000996 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000997 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200998 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +0000999 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001000
1001 v0 = count / (biL );
1002 t1 = count & (biL - 1);
1003
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001004 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +00001005
Paul Bakkerf9688572011-05-05 10:00:45 +00001006 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001007 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001008
1009 ret = 0;
1010
1011 /*
1012 * shift by count / limb_size
1013 */
1014 if( v0 > 0 )
1015 {
Paul Bakker23986e52011-04-24 08:57:21 +00001016 for( i = X->n; i > v0; i-- )
1017 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001018
Paul Bakker23986e52011-04-24 08:57:21 +00001019 for( ; i > 0; i-- )
1020 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001021 }
1022
1023 /*
1024 * shift by count % limb_size
1025 */
1026 if( t1 > 0 )
1027 {
1028 for( i = v0; i < X->n; i++ )
1029 {
1030 r1 = X->p[i] >> (biL - t1);
1031 X->p[i] <<= t1;
1032 X->p[i] |= r0;
1033 r0 = r1;
1034 }
1035 }
1036
1037cleanup:
1038
1039 return( ret );
1040}
1041
1042/*
1043 * Right-shift: X >>= count
1044 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001045int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +00001046{
Paul Bakker23986e52011-04-24 08:57:21 +00001047 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001048 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +00001049 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001050
1051 v0 = count / biL;
1052 v1 = count & (biL - 1);
1053
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +01001054 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001055 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +01001056
Paul Bakker5121ce52009-01-03 21:22:43 +00001057 /*
1058 * shift by count / limb_size
1059 */
1060 if( v0 > 0 )
1061 {
1062 for( i = 0; i < X->n - v0; i++ )
1063 X->p[i] = X->p[i + v0];
1064
1065 for( ; i < X->n; i++ )
1066 X->p[i] = 0;
1067 }
1068
1069 /*
1070 * shift by count % limb_size
1071 */
1072 if( v1 > 0 )
1073 {
Paul Bakker23986e52011-04-24 08:57:21 +00001074 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001075 {
Paul Bakker23986e52011-04-24 08:57:21 +00001076 r1 = X->p[i - 1] << (biL - v1);
1077 X->p[i - 1] >>= v1;
1078 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001079 r0 = r1;
1080 }
1081 }
1082
1083 return( 0 );
1084}
1085
1086/*
1087 * Compare unsigned values
1088 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001089int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001090{
Paul Bakker23986e52011-04-24 08:57:21 +00001091 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001092 MPI_VALIDATE_RET( X != NULL );
1093 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001094
Paul Bakker23986e52011-04-24 08:57:21 +00001095 for( i = X->n; i > 0; i-- )
1096 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001097 break;
1098
Paul Bakker23986e52011-04-24 08:57:21 +00001099 for( j = Y->n; j > 0; j-- )
1100 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001101 break;
1102
Paul Bakker23986e52011-04-24 08:57:21 +00001103 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001104 return( 0 );
1105
1106 if( i > j ) return( 1 );
1107 if( j > i ) return( -1 );
1108
Paul Bakker23986e52011-04-24 08:57:21 +00001109 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001110 {
Paul Bakker23986e52011-04-24 08:57:21 +00001111 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
1112 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001113 }
1114
1115 return( 0 );
1116}
1117
1118/*
1119 * Compare signed values
1120 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001121int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001122{
Paul Bakker23986e52011-04-24 08:57:21 +00001123 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001124 MPI_VALIDATE_RET( X != NULL );
1125 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001126
Paul Bakker23986e52011-04-24 08:57:21 +00001127 for( i = X->n; i > 0; i-- )
1128 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001129 break;
1130
Paul Bakker23986e52011-04-24 08:57:21 +00001131 for( j = Y->n; j > 0; j-- )
1132 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001133 break;
1134
Paul Bakker23986e52011-04-24 08:57:21 +00001135 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001136 return( 0 );
1137
1138 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +00001139 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001140
1141 if( X->s > 0 && Y->s < 0 ) return( 1 );
1142 if( Y->s > 0 && X->s < 0 ) return( -1 );
1143
Paul Bakker23986e52011-04-24 08:57:21 +00001144 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001145 {
Paul Bakker23986e52011-04-24 08:57:21 +00001146 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
1147 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001148 }
1149
1150 return( 0 );
1151}
1152
Janos Follath3f6f0e42019-10-14 09:09:32 +01001153/** Decide if an integer is less than the other, without branches.
1154 *
1155 * \param x First integer.
1156 * \param y Second integer.
1157 *
1158 * \return 1 if \p x is less than \p y, 0 otherwise
1159 */
Janos Follath0e5532d2019-10-11 14:21:53 +01001160static unsigned ct_lt_mpi_uint( const mbedtls_mpi_uint x,
1161 const mbedtls_mpi_uint y )
Janos Follathee6abce2019-09-05 14:47:19 +01001162{
1163 mbedtls_mpi_uint ret;
1164 mbedtls_mpi_uint cond;
1165
1166 /*
1167 * Check if the most significant bits (MSB) of the operands are different.
1168 */
1169 cond = ( x ^ y );
1170 /*
1171 * If the MSB are the same then the difference x-y will be negative (and
1172 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
1173 */
1174 ret = ( x - y ) & ~cond;
1175 /*
1176 * If the MSB are different, then the operand with the MSB of 1 is the
1177 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
1178 * the MSB of y is 0.)
1179 */
1180 ret |= y & cond;
1181
1182
Janos Follatha0f732b2019-10-14 08:59:14 +01001183 ret = ret >> ( biL - 1 );
Janos Follathee6abce2019-09-05 14:47:19 +01001184
Janos Follath67ce6472019-10-29 15:08:46 +00001185 return (unsigned) ret;
Janos Follathee6abce2019-09-05 14:47:19 +01001186}
1187
1188/*
1189 * Compare signed values in constant time
1190 */
Janos Follath0e5532d2019-10-11 14:21:53 +01001191int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
1192 unsigned *ret )
Janos Follathee6abce2019-09-05 14:47:19 +01001193{
1194 size_t i;
Janos Follathbb5147f2019-10-28 12:23:18 +00001195 /* The value of any of these variables is either 0 or 1 at all times. */
Janos Follath5e614ce2019-10-28 12:31:34 +00001196 unsigned cond, done, X_is_negative, Y_is_negative;
Janos Follathee6abce2019-09-05 14:47:19 +01001197
1198 MPI_VALIDATE_RET( X != NULL );
1199 MPI_VALIDATE_RET( Y != NULL );
1200 MPI_VALIDATE_RET( ret != NULL );
1201
1202 if( X->n != Y->n )
1203 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1204
1205 /*
Janos Follath73ba9ec2019-10-28 12:12:15 +00001206 * Set sign_N to 1 if N >= 0, 0 if N < 0.
1207 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
Janos Follathee6abce2019-09-05 14:47:19 +01001208 */
Janos Follath5e614ce2019-10-28 12:31:34 +00001209 X_is_negative = ( X->s & 2 ) >> 1;
1210 Y_is_negative = ( Y->s & 2 ) >> 1;
Janos Follath0e5532d2019-10-11 14:21:53 +01001211
1212 /*
1213 * If the signs are different, then the positive operand is the bigger.
Janos Follath5e614ce2019-10-28 12:31:34 +00001214 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
1215 * is false if X is positive (X_is_negative == 0).
Janos Follath0e5532d2019-10-11 14:21:53 +01001216 */
Janos Follath5e614ce2019-10-28 12:31:34 +00001217 cond = ( X_is_negative ^ Y_is_negative );
1218 *ret = cond & X_is_negative;
Janos Follath0e5532d2019-10-11 14:21:53 +01001219
1220 /*
Janos Follathbb5147f2019-10-28 12:23:18 +00001221 * This is a constant-time function. We might have the result, but we still
Janos Follath0e5532d2019-10-11 14:21:53 +01001222 * need to go through the loop. Record if we have the result already.
1223 */
Janos Follathee6abce2019-09-05 14:47:19 +01001224 done = cond;
1225
1226 for( i = X->n; i > 0; i-- )
1227 {
1228 /*
Janos Follath30702422019-11-05 12:24:52 +00001229 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
1230 * X and Y are negative.
Janos Follath0e5532d2019-10-11 14:21:53 +01001231 *
1232 * Again even if we can make a decision, we just mark the result and
1233 * the fact that we are done and continue looping.
Janos Follathee6abce2019-09-05 14:47:19 +01001234 */
Janos Follath30702422019-11-05 12:24:52 +00001235 cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] );
1236 *ret |= cond & ( 1 - done ) & X_is_negative;
Janos Follathc50e6d52019-10-28 12:37:21 +00001237 done |= cond;
Janos Follathee6abce2019-09-05 14:47:19 +01001238
1239 /*
Janos Follath30702422019-11-05 12:24:52 +00001240 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
1241 * X and Y are positive.
Janos Follath0e5532d2019-10-11 14:21:53 +01001242 *
1243 * Again even if we can make a decision, we just mark the result and
1244 * the fact that we are done and continue looping.
Janos Follathee6abce2019-09-05 14:47:19 +01001245 */
Janos Follath30702422019-11-05 12:24:52 +00001246 cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] );
1247 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
Janos Follathc50e6d52019-10-28 12:37:21 +00001248 done |= cond;
Janos Follathee6abce2019-09-05 14:47:19 +01001249 }
1250
1251 return( 0 );
1252}
1253
Paul Bakker5121ce52009-01-03 21:22:43 +00001254/*
1255 * Compare signed values
1256 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001257int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +00001258{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001259 mbedtls_mpi Y;
1260 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001261 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001262
1263 *p = ( z < 0 ) ? -z : z;
1264 Y.s = ( z < 0 ) ? -1 : 1;
1265 Y.n = 1;
1266 Y.p = p;
1267
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001268 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001269}
1270
1271/*
1272 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1273 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001274int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001275{
Janos Follath24eed8d2019-11-22 13:21:35 +00001276 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001277 size_t i, j;
Janos Follath6c922682015-10-30 17:43:11 +01001278 mbedtls_mpi_uint *o, *p, c, tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +00001279 MPI_VALIDATE_RET( X != NULL );
1280 MPI_VALIDATE_RET( A != NULL );
1281 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001282
1283 if( X == B )
1284 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001285 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +00001286 }
1287
1288 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001289 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +02001290
Paul Bakkerf7ca7b92009-06-20 10:31:06 +00001291 /*
1292 * X should always be positive as a result of unsigned additions.
1293 */
1294 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001295
Paul Bakker23986e52011-04-24 08:57:21 +00001296 for( j = B->n; j > 0; j-- )
1297 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001298 break;
1299
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001300 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001301
1302 o = B->p; p = X->p; c = 0;
1303
Janos Follath6c922682015-10-30 17:43:11 +01001304 /*
1305 * tmp is used because it might happen that p == o
1306 */
Paul Bakker23986e52011-04-24 08:57:21 +00001307 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001308 {
Janos Follath6c922682015-10-30 17:43:11 +01001309 tmp= *o;
Paul Bakker5121ce52009-01-03 21:22:43 +00001310 *p += c; c = ( *p < c );
Janos Follath6c922682015-10-30 17:43:11 +01001311 *p += tmp; c += ( *p < tmp );
Paul Bakker5121ce52009-01-03 21:22:43 +00001312 }
1313
1314 while( c != 0 )
1315 {
1316 if( i >= X->n )
1317 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001318 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001319 p = X->p + i;
1320 }
1321
Paul Bakker2d319fd2012-09-16 21:34:26 +00001322 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +00001323 }
1324
1325cleanup:
1326
1327 return( ret );
1328}
1329
1330/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001331 * Helper for mbedtls_mpi subtraction
Paul Bakker5121ce52009-01-03 21:22:43 +00001332 */
Eric Adamsoneeb91a62020-02-19 21:33:49 -05001333static void mpi_sub_hlp( const mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001334{
Paul Bakker23986e52011-04-24 08:57:21 +00001335 size_t i;
Eric Adamson70b1a802020-02-12 07:08:50 -05001336 mbedtls_mpi_uint c = 0;
Eric Adamsoneeb91a62020-02-19 21:33:49 -05001337 size_t width = A->n > B->n ? B->n : A->n;
Eric Adamsone78e12b2020-02-11 22:18:00 -05001338
1339 for( i = 0; i < width; i++ )
1340 {
1341 mbedtls_mpi_uint a = A->p[i];
1342 mbedtls_mpi_uint b = B->p[i];
1343 mbedtls_mpi_uint z = a < c;
1344
1345 X->p[i] = a - c;
1346 c = ( X->p[i] < b ) + z;
1347 X->p[i] -= b;
1348 }
1349
1350 for( ; i < A->n && c > 0; i++ )
1351 {
1352 mbedtls_mpi_uint a = A->p[i];
1353 mbedtls_mpi_uint z = a < c;
1354 X->p[i] = a - c;
1355 c = z;
1356 }
1357
1358 for( ; i < A->n; i++ )
1359 {
1360 X->p[i] = A->p[i];
1361 }
1362
1363 for( ; i < X->n; i++ )
1364 {
1365 X->p[i] = 0;
1366 }
Eric Adamsoneeb91a62020-02-19 21:33:49 -05001367}
1368
1369/*
1370 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
1371 */
1372int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1373{
1374 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1375
1376 MPI_VALIDATE_RET( X != NULL );
1377 MPI_VALIDATE_RET( A != NULL );
1378 MPI_VALIDATE_RET( B != NULL );
1379
1380 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1381 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1382
1383 /*
1384 * X should always be positive as a result of unsigned subtractions.
1385 */
1386 X->s = 1;
1387 ret = 0;
1388
1389 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, A->n ) );
1390 mpi_sub_hlp( X, A, B );
Paul Bakker5121ce52009-01-03 21:22:43 +00001391
1392cleanup:
Paul Bakker5121ce52009-01-03 21:22:43 +00001393 return( ret );
1394}
1395
1396/*
1397 * Signed addition: X = A + B
1398 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001399int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001400{
Hanno Becker73d7d792018-12-11 10:35:51 +00001401 int ret, s;
1402 MPI_VALIDATE_RET( X != NULL );
1403 MPI_VALIDATE_RET( A != NULL );
1404 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001405
Hanno Becker73d7d792018-12-11 10:35:51 +00001406 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001407 if( A->s * B->s < 0 )
1408 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001409 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001410 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001411 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001412 X->s = s;
1413 }
1414 else
1415 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001416 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001417 X->s = -s;
1418 }
1419 }
1420 else
1421 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001422 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001423 X->s = s;
1424 }
1425
1426cleanup:
1427
1428 return( ret );
1429}
1430
1431/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001432 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001433 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001434int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001435{
Hanno Becker73d7d792018-12-11 10:35:51 +00001436 int ret, s;
1437 MPI_VALIDATE_RET( X != NULL );
1438 MPI_VALIDATE_RET( A != NULL );
1439 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001440
Hanno Becker73d7d792018-12-11 10:35:51 +00001441 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001442 if( A->s * B->s > 0 )
1443 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001444 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001445 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001446 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001447 X->s = s;
1448 }
1449 else
1450 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001451 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001452 X->s = -s;
1453 }
1454 }
1455 else
1456 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001457 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001458 X->s = s;
1459 }
1460
1461cleanup:
1462
1463 return( ret );
1464}
1465
1466/*
1467 * Signed addition: X = A + b
1468 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001469int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001470{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001471 mbedtls_mpi _B;
1472 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001473 MPI_VALIDATE_RET( X != NULL );
1474 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001475
1476 p[0] = ( b < 0 ) ? -b : b;
1477 _B.s = ( b < 0 ) ? -1 : 1;
1478 _B.n = 1;
1479 _B.p = p;
1480
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001481 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001482}
1483
1484/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001485 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001486 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001487int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001488{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001489 mbedtls_mpi _B;
1490 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001491 MPI_VALIDATE_RET( X != NULL );
1492 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001493
1494 p[0] = ( b < 0 ) ? -b : b;
1495 _B.s = ( b < 0 ) ? -1 : 1;
1496 _B.n = 1;
1497 _B.p = p;
1498
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001499 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001500}
1501
1502/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001503 * Helper for mbedtls_mpi multiplication
Paul Bakkerfc4f46f2013-06-24 19:23:56 +02001504 */
1505static
1506#if defined(__APPLE__) && defined(__arm__)
1507/*
1508 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1509 * appears to need this to prevent bad ARM code generation at -O3.
1510 */
1511__attribute__ ((noinline))
1512#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001513void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001514{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001515 mbedtls_mpi_uint c = 0, t = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001516
1517#if defined(MULADDC_HUIT)
1518 for( ; i >= 8; i -= 8 )
1519 {
1520 MULADDC_INIT
1521 MULADDC_HUIT
1522 MULADDC_STOP
1523 }
1524
1525 for( ; i > 0; i-- )
1526 {
1527 MULADDC_INIT
1528 MULADDC_CORE
1529 MULADDC_STOP
1530 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001531#else /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001532 for( ; i >= 16; i -= 16 )
1533 {
1534 MULADDC_INIT
1535 MULADDC_CORE MULADDC_CORE
1536 MULADDC_CORE MULADDC_CORE
1537 MULADDC_CORE MULADDC_CORE
1538 MULADDC_CORE MULADDC_CORE
1539
1540 MULADDC_CORE MULADDC_CORE
1541 MULADDC_CORE MULADDC_CORE
1542 MULADDC_CORE MULADDC_CORE
1543 MULADDC_CORE MULADDC_CORE
1544 MULADDC_STOP
1545 }
1546
1547 for( ; i >= 8; i -= 8 )
1548 {
1549 MULADDC_INIT
1550 MULADDC_CORE MULADDC_CORE
1551 MULADDC_CORE MULADDC_CORE
1552
1553 MULADDC_CORE MULADDC_CORE
1554 MULADDC_CORE MULADDC_CORE
1555 MULADDC_STOP
1556 }
1557
1558 for( ; i > 0; i-- )
1559 {
1560 MULADDC_INIT
1561 MULADDC_CORE
1562 MULADDC_STOP
1563 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001564#endif /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001565
1566 t++;
1567
1568 do {
1569 *d += c; c = ( *d < c ); d++;
1570 }
1571 while( c != 0 );
1572}
1573
1574/*
1575 * Baseline multiplication: X = A * B (HAC 14.12)
1576 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001577int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001578{
Janos Follath24eed8d2019-11-22 13:21:35 +00001579 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001580 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001581 mbedtls_mpi TA, TB;
Hanno Becker73d7d792018-12-11 10:35:51 +00001582 MPI_VALIDATE_RET( X != NULL );
1583 MPI_VALIDATE_RET( A != NULL );
1584 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001585
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001586 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001587
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001588 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1589 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001590
Paul Bakker23986e52011-04-24 08:57:21 +00001591 for( i = A->n; i > 0; i-- )
1592 if( A->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001593 break;
1594
Paul Bakker23986e52011-04-24 08:57:21 +00001595 for( j = B->n; j > 0; j-- )
1596 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001597 break;
1598
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001599 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1600 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001601
Alexey Skalozub8e75e682016-01-13 21:59:27 +02001602 for( ; j > 0; j-- )
1603 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001604
1605 X->s = A->s * B->s;
1606
1607cleanup:
1608
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001609 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001610
1611 return( ret );
1612}
1613
1614/*
1615 * Baseline multiplication: X = A * b
1616 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001617int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001618{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001619 mbedtls_mpi _B;
1620 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001621 MPI_VALIDATE_RET( X != NULL );
1622 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001623
1624 _B.s = 1;
1625 _B.n = 1;
1626 _B.p = p;
1627 p[0] = b;
1628
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001629 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001630}
1631
1632/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001633 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1634 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001635 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001636static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1637 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001638{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001639#if defined(MBEDTLS_HAVE_UDBL)
1640 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001641#else
Simon Butcher9803d072016-01-03 00:24:34 +00001642 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1643 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001644 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1645 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001646 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001647#endif
1648
Simon Butcher15b15d12015-11-26 19:35:03 +00001649 /*
1650 * Check for overflow
1651 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001652 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001653 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001654 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001655
Simon Butcherf5ba0452015-12-27 23:01:55 +00001656 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001657 }
1658
1659#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001660 dividend = (mbedtls_t_udbl) u1 << biL;
1661 dividend |= (mbedtls_t_udbl) u0;
1662 quotient = dividend / d;
1663 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1664 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1665
1666 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001667 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001668
1669 return (mbedtls_mpi_uint) quotient;
1670#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001671
1672 /*
1673 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1674 * Vol. 2 - Seminumerical Algorithms, Knuth
1675 */
1676
1677 /*
1678 * Normalize the divisor, d, and dividend, u0, u1
1679 */
1680 s = mbedtls_clz( d );
1681 d = d << s;
1682
1683 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001684 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001685 u0 = u0 << s;
1686
1687 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001688 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001689
1690 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001691 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001692
1693 /*
1694 * Find the first quotient and remainder
1695 */
1696 q1 = u1 / d1;
1697 r0 = u1 - d1 * q1;
1698
1699 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1700 {
1701 q1 -= 1;
1702 r0 += d1;
1703
1704 if ( r0 >= radix ) break;
1705 }
1706
Simon Butcherf5ba0452015-12-27 23:01:55 +00001707 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001708 q0 = rAX / d1;
1709 r0 = rAX - q0 * d1;
1710
1711 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1712 {
1713 q0 -= 1;
1714 r0 += d1;
1715
1716 if ( r0 >= radix ) break;
1717 }
1718
1719 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001720 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001721
1722 quotient = q1 * radix + q0;
1723
1724 return quotient;
1725#endif
1726}
1727
1728/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001729 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001730 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001731int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1732 const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001733{
Janos Follath24eed8d2019-11-22 13:21:35 +00001734 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001735 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001736 mbedtls_mpi X, Y, Z, T1, T2;
Alexander Kd19a1932019-11-01 18:20:42 +03001737 mbedtls_mpi_uint TP2[3];
Hanno Becker73d7d792018-12-11 10:35:51 +00001738 MPI_VALIDATE_RET( A != NULL );
1739 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001740
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001741 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1742 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001743
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001744 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001745 mbedtls_mpi_init( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001746 /*
1747 * Avoid dynamic memory allocations for constant-size T2.
1748 *
1749 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1750 * so nobody increase the size of the MPI and we're safe to use an on-stack
1751 * buffer.
1752 */
Alexander K35d6d462019-10-31 14:46:45 +03001753 T2.s = 1;
Alexander Kd19a1932019-11-01 18:20:42 +03001754 T2.n = sizeof( TP2 ) / sizeof( *TP2 );
1755 T2.p = TP2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001756
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001757 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001758 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001759 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1760 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001761 return( 0 );
1762 }
1763
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001764 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1765 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001766 X.s = Y.s = 1;
1767
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001768 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1769 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1770 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001771
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001772 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001773 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001774 {
1775 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001776 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1777 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001778 }
1779 else k = 0;
1780
1781 n = X.n - 1;
1782 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001783 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001784
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001785 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001786 {
1787 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001788 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001789 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001790 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001791
1792 for( i = n; i > t ; i-- )
1793 {
1794 if( X.p[i] >= Y.p[t] )
1795 Z.p[i - t - 1] = ~0;
1796 else
1797 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001798 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1799 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001800 }
1801
Alexander K35d6d462019-10-31 14:46:45 +03001802 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1803 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1804 T2.p[2] = X.p[i];
1805
Paul Bakker5121ce52009-01-03 21:22:43 +00001806 Z.p[i - t - 1]++;
1807 do
1808 {
1809 Z.p[i - t - 1]--;
1810
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001811 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001812 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001813 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001814 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001815 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001816 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001817
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001818 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1819 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1820 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001821
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001822 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001823 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001824 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1825 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1826 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001827 Z.p[i - t - 1]--;
1828 }
1829 }
1830
1831 if( Q != NULL )
1832 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001833 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001834 Q->s = A->s * B->s;
1835 }
1836
1837 if( R != NULL )
1838 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001839 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001840 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001841 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001842
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001843 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001844 R->s = 1;
1845 }
1846
1847cleanup:
1848
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001849 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001850 mbedtls_mpi_free( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001851 mbedtls_platform_zeroize( TP2, sizeof( TP2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001852
1853 return( ret );
1854}
1855
1856/*
1857 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001858 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001859int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1860 const mbedtls_mpi *A,
1861 mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001862{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001863 mbedtls_mpi _B;
1864 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001865 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001866
1867 p[0] = ( b < 0 ) ? -b : b;
1868 _B.s = ( b < 0 ) ? -1 : 1;
1869 _B.n = 1;
1870 _B.p = p;
1871
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001872 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001873}
1874
1875/*
1876 * Modulo: R = A mod B
1877 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001878int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001879{
Janos Follath24eed8d2019-11-22 13:21:35 +00001880 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +00001881 MPI_VALIDATE_RET( R != NULL );
1882 MPI_VALIDATE_RET( A != NULL );
1883 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001884
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001885 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1886 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001887
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001888 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001889
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001890 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1891 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001892
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001893 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1894 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001895
1896cleanup:
1897
1898 return( ret );
1899}
1900
1901/*
1902 * Modulo: r = A mod b
1903 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001904int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001905{
Paul Bakker23986e52011-04-24 08:57:21 +00001906 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001907 mbedtls_mpi_uint x, y, z;
Hanno Becker73d7d792018-12-11 10:35:51 +00001908 MPI_VALIDATE_RET( r != NULL );
1909 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001910
1911 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001912 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001913
1914 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001915 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001916
1917 /*
1918 * handle trivial cases
1919 */
1920 if( b == 1 )
1921 {
1922 *r = 0;
1923 return( 0 );
1924 }
1925
1926 if( b == 2 )
1927 {
1928 *r = A->p[0] & 1;
1929 return( 0 );
1930 }
1931
1932 /*
1933 * general case
1934 */
Paul Bakker23986e52011-04-24 08:57:21 +00001935 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001936 {
Paul Bakker23986e52011-04-24 08:57:21 +00001937 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001938 y = ( y << biH ) | ( x >> biH );
1939 z = y / b;
1940 y -= z * b;
1941
1942 x <<= biH;
1943 y = ( y << biH ) | ( x >> biH );
1944 z = y / b;
1945 y -= z * b;
1946 }
1947
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001948 /*
1949 * If A is negative, then the current y represents a negative value.
1950 * Flipping it to the positive side.
1951 */
1952 if( A->s < 0 && y != 0 )
1953 y = b - y;
1954
Paul Bakker5121ce52009-01-03 21:22:43 +00001955 *r = y;
1956
1957 return( 0 );
1958}
1959
1960/*
1961 * Fast Montgomery initialization (thanks to Tom St Denis)
1962 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001963static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001964{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001965 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001966 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00001967
1968 x = m0;
1969 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001970
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001971 for( i = biL; i >= 8; i /= 2 )
1972 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001973
1974 *mm = ~x + 1;
1975}
1976
1977/*
1978 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1979 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001980static int 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 +02001981 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001982{
Paul Bakker23986e52011-04-24 08:57:21 +00001983 size_t i, n, m;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001984 mbedtls_mpi_uint u0, u1, *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00001985
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001986 if( T->n < N->n + 1 || T->p == NULL )
1987 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1988
Paul Bakker5121ce52009-01-03 21:22:43 +00001989 memset( T->p, 0, T->n * ciL );
1990
1991 d = T->p;
1992 n = N->n;
1993 m = ( B->n < n ) ? B->n : n;
1994
1995 for( i = 0; i < n; i++ )
1996 {
1997 /*
1998 * T = (T + u0*B + u1*N) / 2^biL
1999 */
2000 u0 = A->p[i];
2001 u1 = ( d[0] + u0 * B->p[0] ) * mm;
2002
2003 mpi_mul_hlp( m, B->p, d, u0 );
2004 mpi_mul_hlp( n, N->p, d, u1 );
2005
2006 *d++ = u0; d[n + 1] = 0;
2007 }
2008
Paul Bakker66d5d072014-06-17 16:39:18 +02002009 memcpy( A->p, d, ( n + 1 ) * ciL );
Paul Bakker5121ce52009-01-03 21:22:43 +00002010
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002011 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
Eric Adamsoneeb91a62020-02-19 21:33:49 -05002012 mpi_sub_hlp( A, A, N );
Paul Bakker5121ce52009-01-03 21:22:43 +00002013 else
2014 /* prevent timing attacks */
Eric Adamsoneeb91a62020-02-19 21:33:49 -05002015 mpi_sub_hlp( T, T, A );
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002016
2017 return( 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002018}
2019
2020/*
2021 * Montgomery reduction: A = A * R^-1 mod N
2022 */
Hanno Becker73d7d792018-12-11 10:35:51 +00002023static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
2024 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00002025{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002026 mbedtls_mpi_uint z = 1;
2027 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00002028
Paul Bakker8ddb6452013-02-27 14:56:33 +01002029 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00002030 U.p = &z;
2031
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002032 return( mpi_montmul( A, &U, N, mm, T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002033}
2034
2035/*
2036 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
2037 */
Hanno Becker73d7d792018-12-11 10:35:51 +00002038int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
2039 const mbedtls_mpi *E, const mbedtls_mpi *N,
2040 mbedtls_mpi *_RR )
Paul Bakker5121ce52009-01-03 21:22:43 +00002041{
Janos Follath24eed8d2019-11-22 13:21:35 +00002042 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00002043 size_t wbits, wsize, one = 1;
2044 size_t i, j, nblimbs;
2045 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002046 mbedtls_mpi_uint ei, mm, state;
2047 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00002048 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00002049
Hanno Becker73d7d792018-12-11 10:35:51 +00002050 MPI_VALIDATE_RET( X != NULL );
2051 MPI_VALIDATE_RET( A != NULL );
2052 MPI_VALIDATE_RET( E != NULL );
2053 MPI_VALIDATE_RET( N != NULL );
2054
Hanno Becker8d1dd1b2017-09-28 11:02:24 +01002055 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002056 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002057
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002058 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
2059 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002060
2061 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00002062 * Init temps and window size
2063 */
2064 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002065 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
2066 mbedtls_mpi_init( &Apos );
Paul Bakker5121ce52009-01-03 21:22:43 +00002067 memset( W, 0, sizeof( W ) );
2068
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002069 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00002070
2071 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2072 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2073
Peter Kolbuse6bcad32018-12-11 14:01:44 -06002074#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002075 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2076 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Peter Kolbuse6bcad32018-12-11 14:01:44 -06002077#endif
Paul Bakkerb6d5f082011-11-25 11:52:11 +00002078
Paul Bakker5121ce52009-01-03 21:22:43 +00002079 j = N->n + 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002080 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2081 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2082 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002083
2084 /*
Paul Bakker50546922012-05-19 08:40:49 +00002085 * Compensate for negative A (and correct at the end)
2086 */
2087 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00002088 if( neg )
2089 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002090 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00002091 Apos.s = 1;
2092 A = &Apos;
2093 }
2094
2095 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00002096 * If 1st call, pre-compute R^2 mod N
2097 */
2098 if( _RR == NULL || _RR->p == NULL )
2099 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002100 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2101 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2102 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002103
2104 if( _RR != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002105 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002106 }
2107 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002108 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002109
2110 /*
2111 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2112 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002113 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
2114 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Paul Bakkerc2024f42014-01-23 20:38:35 +01002115 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002116 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002117
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002118 MBEDTLS_MPI_CHK( mpi_montmul( &W[1], &RR, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002119
2120 /*
2121 * X = R^2 * R^-1 mod N = R mod N
2122 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002123 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002124 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002125
2126 if( wsize > 1 )
2127 {
2128 /*
2129 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2130 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002131 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002132
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002133 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2134 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002135
2136 for( i = 0; i < wsize - 1; i++ )
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002137 MBEDTLS_MPI_CHK( mpi_montmul( &W[j], &W[j], N, mm, &T ) );
Paul Bakker0d7702c2013-10-29 16:18:35 +01002138
Paul Bakker5121ce52009-01-03 21:22:43 +00002139 /*
2140 * W[i] = W[i - 1] * W[1]
2141 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002142 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002143 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002144 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2145 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002146
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002147 MBEDTLS_MPI_CHK( mpi_montmul( &W[i], &W[1], N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002148 }
2149 }
2150
2151 nblimbs = E->n;
2152 bufsize = 0;
2153 nbits = 0;
2154 wbits = 0;
2155 state = 0;
2156
2157 while( 1 )
2158 {
2159 if( bufsize == 0 )
2160 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01002161 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002162 break;
2163
Paul Bakker0d7702c2013-10-29 16:18:35 +01002164 nblimbs--;
2165
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002166 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00002167 }
2168
2169 bufsize--;
2170
2171 ei = (E->p[nblimbs] >> bufsize) & 1;
2172
2173 /*
2174 * skip leading 0s
2175 */
2176 if( ei == 0 && state == 0 )
2177 continue;
2178
2179 if( ei == 0 && state == 1 )
2180 {
2181 /*
2182 * out of window, square X
2183 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002184 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002185 continue;
2186 }
2187
2188 /*
2189 * add ei to current window
2190 */
2191 state = 2;
2192
2193 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02002194 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002195
2196 if( nbits == wsize )
2197 {
2198 /*
2199 * X = X^wsize R^-1 mod N
2200 */
2201 for( i = 0; i < wsize; i++ )
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002202 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002203
2204 /*
2205 * X = X * W[wbits] R^-1 mod N
2206 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002207 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[wbits], N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002208
2209 state--;
2210 nbits = 0;
2211 wbits = 0;
2212 }
2213 }
2214
2215 /*
2216 * process the remaining bits
2217 */
2218 for( i = 0; i < nbits; i++ )
2219 {
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002220 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002221
2222 wbits <<= 1;
2223
Paul Bakker66d5d072014-06-17 16:39:18 +02002224 if( ( wbits & ( one << wsize ) ) != 0 )
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002225 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[1], N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002226 }
2227
2228 /*
2229 * X = A^E * R * R^-1 mod N = A^E mod N
2230 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01002231 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002232
Hanno Beckera4af1c42017-04-18 09:07:45 +01002233 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00002234 {
2235 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002236 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002237 }
2238
Paul Bakker5121ce52009-01-03 21:22:43 +00002239cleanup:
2240
Paul Bakker66d5d072014-06-17 16:39:18 +02002241 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002242 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00002243
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002244 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Paul Bakker6c591fa2011-05-05 11:49:20 +00002245
Paul Bakker75a28602014-03-31 12:08:17 +02002246 if( _RR == NULL || _RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002247 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002248
2249 return( ret );
2250}
2251
Paul Bakker5121ce52009-01-03 21:22:43 +00002252/*
2253 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2254 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002255int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00002256{
Janos Follath24eed8d2019-11-22 13:21:35 +00002257 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00002258 size_t lz, lzt;
Alexander Ke8ad49f2019-08-16 16:16:07 +03002259 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00002260
Hanno Becker73d7d792018-12-11 10:35:51 +00002261 MPI_VALIDATE_RET( G != NULL );
2262 MPI_VALIDATE_RET( A != NULL );
2263 MPI_VALIDATE_RET( B != NULL );
2264
Alexander Ke8ad49f2019-08-16 16:16:07 +03002265 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002266
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002267 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2268 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002269
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002270 lz = mbedtls_mpi_lsb( &TA );
2271 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002272
Paul Bakker66d5d072014-06-17 16:39:18 +02002273 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002274 lz = lzt;
2275
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002276 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
2277 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002278
Paul Bakker5121ce52009-01-03 21:22:43 +00002279 TA.s = TB.s = 1;
2280
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002281 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002282 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002283 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2284 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002285
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002286 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002287 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002288 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2289 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002290 }
2291 else
2292 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002293 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2294 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002295 }
2296 }
2297
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002298 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2299 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002300
2301cleanup:
2302
Alexander Ke8ad49f2019-08-16 16:16:07 +03002303 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002304
2305 return( ret );
2306}
2307
Paul Bakker33dc46b2014-04-30 16:11:39 +02002308/*
2309 * Fill X with size bytes of random.
2310 *
2311 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02002312 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02002313 * deterministic, eg for tests).
2314 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002315int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002316 int (*f_rng)(void *, unsigned char *, size_t),
2317 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00002318{
Janos Follath24eed8d2019-11-22 13:21:35 +00002319 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker6dab6202019-01-02 16:42:29 +00002320 size_t const limbs = CHARS_TO_LIMBS( size );
Hanno Beckerda1655a2017-10-18 14:21:44 +01002321 size_t const overhead = ( limbs * ciL ) - size;
2322 unsigned char *Xp;
2323
Hanno Becker8ce11a32018-12-19 16:18:52 +00002324 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002325 MPI_VALIDATE_RET( f_rng != NULL );
Paul Bakker33dc46b2014-04-30 16:11:39 +02002326
Hanno Beckerda1655a2017-10-18 14:21:44 +01002327 /* Ensure that target MPI has exactly the necessary number of limbs */
2328 if( X->n != limbs )
2329 {
2330 mbedtls_mpi_free( X );
2331 mbedtls_mpi_init( X );
2332 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
2333 }
2334 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker287781a2011-03-26 13:18:49 +00002335
Hanno Beckerda1655a2017-10-18 14:21:44 +01002336 Xp = (unsigned char*) X->p;
2337 f_rng( p_rng, Xp + overhead, size );
2338
Hanno Becker2be8a552018-10-25 12:40:09 +01002339 mpi_bigendian_to_host( X->p, limbs );
Paul Bakker287781a2011-03-26 13:18:49 +00002340
2341cleanup:
2342 return( ret );
2343}
2344
Paul Bakker5121ce52009-01-03 21:22:43 +00002345/*
2346 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2347 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002348int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00002349{
Janos Follath24eed8d2019-11-22 13:21:35 +00002350 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002351 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Hanno Becker73d7d792018-12-11 10:35:51 +00002352 MPI_VALIDATE_RET( X != NULL );
2353 MPI_VALIDATE_RET( A != NULL );
2354 MPI_VALIDATE_RET( N != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00002355
Hanno Becker4bcb4912017-04-18 15:49:39 +01002356 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002357 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002358
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002359 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2360 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2361 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002362
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002363 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002364
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002365 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002366 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002367 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002368 goto cleanup;
2369 }
2370
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002371 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2372 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2373 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2374 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002375
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002376 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2377 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2378 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2379 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002380
2381 do
2382 {
2383 while( ( TU.p[0] & 1 ) == 0 )
2384 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002385 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002386
2387 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2388 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002389 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2390 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002391 }
2392
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002393 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2394 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002395 }
2396
2397 while( ( TV.p[0] & 1 ) == 0 )
2398 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002399 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002400
2401 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2402 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002403 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2404 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002405 }
2406
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002407 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2408 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002409 }
2410
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002411 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002412 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002413 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2414 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2415 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002416 }
2417 else
2418 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002419 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2420 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2421 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002422 }
2423 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002424 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002425
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002426 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2427 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002428
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002429 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2430 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002431
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002432 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002433
2434cleanup:
2435
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002436 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2437 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2438 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002439
2440 return( ret );
2441}
2442
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002443#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00002444
Paul Bakker5121ce52009-01-03 21:22:43 +00002445static const int small_prime[] =
2446{
2447 3, 5, 7, 11, 13, 17, 19, 23,
2448 29, 31, 37, 41, 43, 47, 53, 59,
2449 61, 67, 71, 73, 79, 83, 89, 97,
2450 101, 103, 107, 109, 113, 127, 131, 137,
2451 139, 149, 151, 157, 163, 167, 173, 179,
2452 181, 191, 193, 197, 199, 211, 223, 227,
2453 229, 233, 239, 241, 251, 257, 263, 269,
2454 271, 277, 281, 283, 293, 307, 311, 313,
2455 317, 331, 337, 347, 349, 353, 359, 367,
2456 373, 379, 383, 389, 397, 401, 409, 419,
2457 421, 431, 433, 439, 443, 449, 457, 461,
2458 463, 467, 479, 487, 491, 499, 503, 509,
2459 521, 523, 541, 547, 557, 563, 569, 571,
2460 577, 587, 593, 599, 601, 607, 613, 617,
2461 619, 631, 641, 643, 647, 653, 659, 661,
2462 673, 677, 683, 691, 701, 709, 719, 727,
2463 733, 739, 743, 751, 757, 761, 769, 773,
2464 787, 797, 809, 811, 821, 823, 827, 829,
2465 839, 853, 857, 859, 863, 877, 881, 883,
2466 887, 907, 911, 919, 929, 937, 941, 947,
2467 953, 967, 971, 977, 983, 991, 997, -103
2468};
2469
2470/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002471 * Small divisors test (X must be positive)
2472 *
2473 * Return values:
2474 * 0: no small factor (possible prime, more tests needed)
2475 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002476 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002477 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002478 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002479static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002480{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002481 int ret = 0;
2482 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002483 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002484
Paul Bakker5121ce52009-01-03 21:22:43 +00002485 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002486 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002487
2488 for( i = 0; small_prime[i] > 0; i++ )
2489 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002490 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002491 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002492
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002493 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002494
2495 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002496 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002497 }
2498
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002499cleanup:
2500 return( ret );
2501}
2502
2503/*
2504 * Miller-Rabin pseudo-primality test (HAC 4.24)
2505 */
Janos Follathda31fa12018-09-03 14:45:23 +01002506static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002507 int (*f_rng)(void *, unsigned char *, size_t),
2508 void *p_rng )
2509{
Pascal Junodb99183d2015-03-11 16:49:45 +01002510 int ret, count;
Janos Follathda31fa12018-09-03 14:45:23 +01002511 size_t i, j, k, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002512 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002513
Hanno Becker8ce11a32018-12-19 16:18:52 +00002514 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002515 MPI_VALIDATE_RET( f_rng != NULL );
2516
2517 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2518 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002519 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002520
Paul Bakker5121ce52009-01-03 21:22:43 +00002521 /*
2522 * W = |X| - 1
2523 * R = W >> lsb( W )
2524 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002525 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2526 s = mbedtls_mpi_lsb( &W );
2527 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2528 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002529
Janos Follathda31fa12018-09-03 14:45:23 +01002530 for( i = 0; i < rounds; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002531 {
2532 /*
2533 * pick a random A, 1 < A < |X| - 1
2534 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002535 count = 0;
2536 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002537 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002538
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002539 j = mbedtls_mpi_bitlen( &A );
2540 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002541 if (j > k) {
Darryl Greene3f95ed2018-10-02 13:21:35 +01002542 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Pascal Junodb99183d2015-03-11 16:49:45 +01002543 }
2544
2545 if (count++ > 30) {
Jens Wiklanderf08aa3e2019-01-17 13:30:57 +01002546 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2547 goto cleanup;
Pascal Junodb99183d2015-03-11 16:49:45 +01002548 }
2549
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002550 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2551 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002552
2553 /*
2554 * A = A^R mod |X|
2555 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002556 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002557
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002558 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2559 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002560 continue;
2561
2562 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002563 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002564 {
2565 /*
2566 * A = A * A mod |X|
2567 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002568 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2569 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002570
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002571 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002572 break;
2573
2574 j++;
2575 }
2576
2577 /*
2578 * not prime if A != |X| - 1 or A == 1
2579 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002580 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2581 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002582 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002583 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002584 break;
2585 }
2586 }
2587
2588cleanup:
Hanno Becker73d7d792018-12-11 10:35:51 +00002589 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2590 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002591 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002592
2593 return( ret );
2594}
2595
2596/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002597 * Pseudo-primality test: small factors, then Miller-Rabin
2598 */
Janos Follatha0b67c22018-09-18 14:48:23 +01002599int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2600 int (*f_rng)(void *, unsigned char *, size_t),
2601 void *p_rng )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002602{
Janos Follath24eed8d2019-11-22 13:21:35 +00002603 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002604 mbedtls_mpi XX;
Hanno Becker8ce11a32018-12-19 16:18:52 +00002605 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002606 MPI_VALIDATE_RET( f_rng != NULL );
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002607
2608 XX.s = 1;
2609 XX.n = X->n;
2610 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002611
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002612 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2613 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2614 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002615
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002616 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002617 return( 0 );
2618
2619 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2620 {
2621 if( ret == 1 )
2622 return( 0 );
2623
2624 return( ret );
2625 }
2626
Janos Follathda31fa12018-09-03 14:45:23 +01002627 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
Janos Follathf301d232018-08-14 13:34:01 +01002628}
2629
Janos Follatha0b67c22018-09-18 14:48:23 +01002630#if !defined(MBEDTLS_DEPRECATED_REMOVED)
Janos Follathf301d232018-08-14 13:34:01 +01002631/*
2632 * Pseudo-primality test, error probability 2^-80
2633 */
2634int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2635 int (*f_rng)(void *, unsigned char *, size_t),
2636 void *p_rng )
2637{
Hanno Becker8ce11a32018-12-19 16:18:52 +00002638 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002639 MPI_VALIDATE_RET( f_rng != NULL );
2640
Janos Follatha0b67c22018-09-18 14:48:23 +01002641 /*
2642 * In the past our key generation aimed for an error rate of at most
2643 * 2^-80. Since this function is deprecated, aim for the same certainty
2644 * here as well.
2645 */
Hanno Becker73d7d792018-12-11 10:35:51 +00002646 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002647}
Janos Follatha0b67c22018-09-18 14:48:23 +01002648#endif
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002649
2650/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002651 * Prime number generation
Jethro Beekman66689272018-02-14 19:24:10 -08002652 *
Janos Follathf301d232018-08-14 13:34:01 +01002653 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2654 * be either 1024 bits or 1536 bits long, and flags must contain
2655 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Paul Bakker5121ce52009-01-03 21:22:43 +00002656 */
Janos Follath7c025a92018-08-14 11:08:41 +01002657int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002658 int (*f_rng)(void *, unsigned char *, size_t),
2659 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002660{
Jethro Beekman66689272018-02-14 19:24:10 -08002661#ifdef MBEDTLS_HAVE_INT64
2662// ceil(2^63.5)
2663#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2664#else
2665// ceil(2^31.5)
2666#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2667#endif
2668 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker23986e52011-04-24 08:57:21 +00002669 size_t k, n;
Janos Follathda31fa12018-09-03 14:45:23 +01002670 int rounds;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002671 mbedtls_mpi_uint r;
2672 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002673
Hanno Becker8ce11a32018-12-19 16:18:52 +00002674 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002675 MPI_VALIDATE_RET( f_rng != NULL );
2676
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002677 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2678 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002679
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002680 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002681
2682 n = BITS_TO_LIMBS( nbits );
2683
Janos Follathda31fa12018-09-03 14:45:23 +01002684 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2685 {
2686 /*
2687 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2688 */
2689 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2690 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2691 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2692 }
2693 else
2694 {
2695 /*
2696 * 2^-100 error probability, number of rounds computed based on HAC,
2697 * fact 4.48
2698 */
2699 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2700 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2701 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2702 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2703 }
2704
Jethro Beekman66689272018-02-14 19:24:10 -08002705 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002706 {
Jethro Beekman66689272018-02-14 19:24:10 -08002707 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2708 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2709 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2710
2711 k = n * biL;
2712 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2713 X->p[0] |= 1;
2714
Janos Follath7c025a92018-08-14 11:08:41 +01002715 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002716 {
Janos Follatha0b67c22018-09-18 14:48:23 +01002717 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
Jethro Beekman66689272018-02-14 19:24:10 -08002718
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002719 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002720 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002721 }
Jethro Beekman66689272018-02-14 19:24:10 -08002722 else
Paul Bakker5121ce52009-01-03 21:22:43 +00002723 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002724 /*
Jethro Beekman66689272018-02-14 19:24:10 -08002725 * An necessary condition for Y and X = 2Y + 1 to be prime
2726 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2727 * Make sure it is satisfied, while keeping X = 3 mod 4
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002728 */
Jethro Beekman66689272018-02-14 19:24:10 -08002729
2730 X->p[0] |= 2;
2731
2732 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2733 if( r == 0 )
2734 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2735 else if( r == 1 )
2736 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2737
2738 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2739 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2740 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2741
2742 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002743 {
Jethro Beekman66689272018-02-14 19:24:10 -08002744 /*
2745 * First, check small factors for X and Y
2746 * before doing Miller-Rabin on any of them
2747 */
2748 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2749 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002750 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002751 == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002752 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002753 == 0 )
Jethro Beekman66689272018-02-14 19:24:10 -08002754 goto cleanup;
2755
2756 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2757 goto cleanup;
2758
2759 /*
2760 * Next candidates. We want to preserve Y = (X-1) / 2 and
2761 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2762 * so up Y by 6 and X by 12.
2763 */
2764 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2765 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002766 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002767 }
2768 }
2769
2770cleanup:
2771
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002772 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002773
2774 return( ret );
2775}
2776
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002777#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002778
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002779#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002780
Paul Bakker23986e52011-04-24 08:57:21 +00002781#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002782
2783static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2784{
2785 { 693, 609, 21 },
2786 { 1764, 868, 28 },
2787 { 768454923, 542167814, 1 }
2788};
2789
Paul Bakker5121ce52009-01-03 21:22:43 +00002790/*
2791 * Checkup routine
2792 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002793int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002794{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002795 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002796 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002797
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002798 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2799 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002800
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002801 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002802 "EFE021C2645FD1DC586E69184AF4A31E" \
2803 "D5F53E93B5F123FA41680867BA110131" \
2804 "944FE7952E2517337780CB0DB80E61AA" \
2805 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2806
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002807 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002808 "B2E7EFD37075B9F03FF989C7C5051C20" \
2809 "34D2A323810251127E7BF8625A4F49A5" \
2810 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2811 "5B5C25763222FEFCCFC38B832366C29E" ) );
2812
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002813 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002814 "0066A198186C18C10B2F5ED9B522752A" \
2815 "9830B69916E535C8F047518A889A43A5" \
2816 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2817
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002818 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002819
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002820 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002821 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2822 "9E857EA95A03512E2BAE7391688D264A" \
2823 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2824 "8001B72E848A38CAE1C65F78E56ABDEF" \
2825 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2826 "ECF677152EF804370C1A305CAF3B5BF1" \
2827 "30879B56C61DE584A0F53A2447A51E" ) );
2828
2829 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002830 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002831
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002832 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002833 {
2834 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002835 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002836
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002837 ret = 1;
2838 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002839 }
2840
2841 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002842 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002843
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002844 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002845
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002846 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002847 "256567336059E52CAE22925474705F39A94" ) );
2848
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002849 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002850 "6613F26162223DF488E9CD48CC132C7A" \
2851 "0AC93C701B001B092E4E5B9F73BCD27B" \
2852 "9EE50D0657C77F374E903CDFA4C642" ) );
2853
2854 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002855 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002856
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002857 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2858 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002859 {
2860 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002861 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002862
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002863 ret = 1;
2864 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002865 }
2866
2867 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002868 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002869
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002870 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002871
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002872 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002873 "36E139AEA55215609D2816998ED020BB" \
2874 "BD96C37890F65171D948E9BC7CBAA4D9" \
2875 "325D24D6A3C12710F10A09FA08AB87" ) );
2876
2877 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002878 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002879
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002880 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002881 {
2882 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002883 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002884
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002885 ret = 1;
2886 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002887 }
2888
2889 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002890 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002891
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002892 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002893
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002894 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002895 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2896 "C3DBA76456363A10869622EAC2DD84EC" \
2897 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2898
2899 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002900 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002901
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002902 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002903 {
2904 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002905 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002906
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002907 ret = 1;
2908 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002909 }
2910
2911 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002912 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002913
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002914 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002915 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002916
Paul Bakker66d5d072014-06-17 16:39:18 +02002917 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002918 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002919 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2920 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002921
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002922 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002923
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002924 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002925 {
2926 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002927 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002928
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002929 ret = 1;
2930 goto cleanup;
2931 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002932 }
2933
2934 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002935 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002936
Paul Bakker5121ce52009-01-03 21:22:43 +00002937cleanup:
2938
2939 if( ret != 0 && verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002940 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002941
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002942 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2943 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002944
2945 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002946 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002947
2948 return( ret );
2949}
2950
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002951#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002952
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002953#endif /* MBEDTLS_BIGNUM_C */