blob: d9ab6f68bb3b2e6279a4858110fa8a9ac4273f00 [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/*
Gilles Peskinef04d11e2020-06-04 19:14:58 +0200247 * Conditionally assign dest = src, without leaking information
248 * about whether the assignment was made or not.
249 * dest and src must be arrays of limbs of size n.
250 * assign must be 0 or 1.
251 */
252static void mpi_safe_cond_assign( size_t n,
253 mbedtls_mpi_uint *dest,
254 const mbedtls_mpi_uint *src,
255 unsigned char assign )
256{
257 size_t i;
258 for( i = 0; i < n; i++ )
259 dest[i] = dest[i] * ( 1 - assign ) + src[i] * assign;
260}
261
262/*
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100263 * Conditionally assign X = Y, without leaking information
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100264 * about whether the assignment was made or not.
265 * (Leaking information about the respective sizes of X and Y is ok however.)
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100266 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200267int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100268{
269 int ret = 0;
270 size_t i;
Hanno Becker73d7d792018-12-11 10:35:51 +0000271 MPI_VALIDATE_RET( X != NULL );
272 MPI_VALIDATE_RET( Y != NULL );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100273
Pascal Junodb99183d2015-03-11 16:49:45 +0100274 /* make sure assign is 0 or 1 in a time-constant manner */
275 assign = (assign | (unsigned char)-assign) >> 7;
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100276
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200277 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100278
Paul Bakker66d5d072014-06-17 16:39:18 +0200279 X->s = X->s * ( 1 - assign ) + Y->s * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100280
Gilles Peskinef04d11e2020-06-04 19:14:58 +0200281 mpi_safe_cond_assign( Y->n, X->p, Y->p, assign );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100282
Gilles Peskinef04d11e2020-06-04 19:14:58 +0200283 for( i = Y->n; i < X->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200284 X->p[i] *= ( 1 - assign );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100285
286cleanup:
287 return( ret );
288}
289
290/*
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100291 * Conditionally swap X and Y, without leaking information
292 * about whether the swap was made or not.
293 * Here it is not ok to simply swap the pointers, which whould lead to
294 * different memory access patterns when X and Y are used afterwards.
295 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200296int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100297{
298 int ret, s;
299 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200300 mbedtls_mpi_uint tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +0000301 MPI_VALIDATE_RET( X != NULL );
302 MPI_VALIDATE_RET( Y != NULL );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100303
304 if( X == Y )
305 return( 0 );
306
Pascal Junodb99183d2015-03-11 16:49:45 +0100307 /* make sure swap is 0 or 1 in a time-constant manner */
308 swap = (swap | (unsigned char)-swap) >> 7;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100309
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200310 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
311 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100312
313 s = X->s;
Paul Bakker66d5d072014-06-17 16:39:18 +0200314 X->s = X->s * ( 1 - swap ) + Y->s * swap;
315 Y->s = Y->s * ( 1 - swap ) + s * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100316
317
318 for( i = 0; i < X->n; i++ )
319 {
320 tmp = X->p[i];
Paul Bakker66d5d072014-06-17 16:39:18 +0200321 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
322 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100323 }
324
325cleanup:
326 return( ret );
327}
328
329/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000330 * Set value from integer
331 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200332int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000333{
Janos Follath24eed8d2019-11-22 13:21:35 +0000334 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +0000335 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000336
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200337 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000338 memset( X->p, 0, X->n * ciL );
339
340 X->p[0] = ( z < 0 ) ? -z : z;
341 X->s = ( z < 0 ) ? -1 : 1;
342
343cleanup:
344
345 return( ret );
346}
347
348/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000349 * Get a specific bit
350 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200351int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000352{
Hanno Becker73d7d792018-12-11 10:35:51 +0000353 MPI_VALIDATE_RET( X != NULL );
354
Paul Bakker2f5947e2011-05-18 15:47:11 +0000355 if( X->n * biL <= pos )
356 return( 0 );
357
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200358 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000359}
360
Gilles Peskine11cdb052018-11-20 16:47:47 +0100361/* Get a specific byte, without range checks. */
362#define GET_BYTE( X, i ) \
363 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
364
Paul Bakker2f5947e2011-05-18 15:47:11 +0000365/*
366 * Set a bit to a specific value of 0 or 1
367 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200368int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000369{
370 int ret = 0;
371 size_t off = pos / biL;
372 size_t idx = pos % biL;
Hanno Becker73d7d792018-12-11 10:35:51 +0000373 MPI_VALIDATE_RET( X != NULL );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000374
375 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200376 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200377
Paul Bakker2f5947e2011-05-18 15:47:11 +0000378 if( X->n * biL <= pos )
379 {
380 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200381 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000382
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200383 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000384 }
385
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200386 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
387 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000388
389cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200390
Paul Bakker2f5947e2011-05-18 15:47:11 +0000391 return( ret );
392}
393
394/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200395 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000396 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200397size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000398{
Paul Bakker23986e52011-04-24 08:57:21 +0000399 size_t i, j, count = 0;
Hanno Beckerf25ee7f2018-12-19 16:51:02 +0000400 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000401
402 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000403 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000404 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
405 return( count );
406
407 return( 0 );
408}
409
410/*
Simon Butcher15b15d12015-11-26 19:35:03 +0000411 * Count leading zero bits in a given integer
412 */
413static size_t mbedtls_clz( const mbedtls_mpi_uint x )
414{
415 size_t j;
Manuel Pégourié-Gonnarde3e8edf2015-12-01 09:31:52 +0100416 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
Simon Butcher15b15d12015-11-26 19:35:03 +0000417
418 for( j = 0; j < biL; j++ )
419 {
420 if( x & mask ) break;
421
422 mask >>= 1;
423 }
424
425 return j;
426}
427
428/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200429 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000430 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200431size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000432{
Paul Bakker23986e52011-04-24 08:57:21 +0000433 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000434
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200435 if( X->n == 0 )
436 return( 0 );
437
Paul Bakker5121ce52009-01-03 21:22:43 +0000438 for( i = X->n - 1; i > 0; i-- )
439 if( X->p[i] != 0 )
440 break;
441
Simon Butcher15b15d12015-11-26 19:35:03 +0000442 j = biL - mbedtls_clz( X->p[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +0000443
Paul Bakker23986e52011-04-24 08:57:21 +0000444 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000445}
446
447/*
448 * Return the total size in bytes
449 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200450size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000451{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200452 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000453}
454
455/*
456 * Convert an ASCII character to digit value
457 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200458static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000459{
460 *d = 255;
461
462 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
463 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
464 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
465
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200466 if( *d >= (mbedtls_mpi_uint) radix )
467 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000468
469 return( 0 );
470}
471
472/*
473 * Import from an ASCII string
474 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200475int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000476{
Janos Follath24eed8d2019-11-22 13:21:35 +0000477 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000478 size_t i, j, slen, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200479 mbedtls_mpi_uint d;
480 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000481 MPI_VALIDATE_RET( X != NULL );
482 MPI_VALIDATE_RET( s != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000483
484 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000485 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000486
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200487 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000488
Paul Bakkerff60ee62010-03-16 21:09:09 +0000489 slen = strlen( s );
490
Paul Bakker5121ce52009-01-03 21:22:43 +0000491 if( radix == 16 )
492 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100493 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200494 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
495
Paul Bakkerff60ee62010-03-16 21:09:09 +0000496 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000497
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200498 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
499 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000500
Paul Bakker23986e52011-04-24 08:57:21 +0000501 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000502 {
Paul Bakker23986e52011-04-24 08:57:21 +0000503 if( i == 1 && s[i - 1] == '-' )
Paul Bakker5121ce52009-01-03 21:22:43 +0000504 {
505 X->s = -1;
506 break;
507 }
508
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200509 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200510 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000511 }
512 }
513 else
514 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200515 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000516
Paul Bakkerff60ee62010-03-16 21:09:09 +0000517 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000518 {
519 if( i == 0 && s[i] == '-' )
520 {
521 X->s = -1;
522 continue;
523 }
524
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200525 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
526 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000527
528 if( X->s == 1 )
529 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200530 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000531 }
532 else
533 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200534 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000535 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000536 }
537 }
538
539cleanup:
540
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200541 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000542
543 return( ret );
544}
545
546/*
Ron Eldora16fa292018-11-20 14:07:01 +0200547 * Helper to write the digits high-order first.
Paul Bakker5121ce52009-01-03 21:22:43 +0000548 */
Ron Eldora16fa292018-11-20 14:07:01 +0200549static int mpi_write_hlp( mbedtls_mpi *X, int radix,
550 char **p, const size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000551{
Janos Follath24eed8d2019-11-22 13:21:35 +0000552 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200553 mbedtls_mpi_uint r;
Ron Eldora16fa292018-11-20 14:07:01 +0200554 size_t length = 0;
555 char *p_end = *p + buflen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000556
Ron Eldora16fa292018-11-20 14:07:01 +0200557 do
558 {
559 if( length >= buflen )
560 {
561 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
562 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000563
Ron Eldora16fa292018-11-20 14:07:01 +0200564 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
565 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
566 /*
567 * Write the residue in the current position, as an ASCII character.
568 */
569 if( r < 0xA )
570 *(--p_end) = (char)( '0' + r );
571 else
572 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000573
Ron Eldora16fa292018-11-20 14:07:01 +0200574 length++;
575 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000576
Ron Eldora16fa292018-11-20 14:07:01 +0200577 memmove( *p, p_end, length );
578 *p += length;
Paul Bakker5121ce52009-01-03 21:22:43 +0000579
580cleanup:
581
582 return( ret );
583}
584
585/*
586 * Export into an ASCII string
587 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100588int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
589 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000590{
Paul Bakker23986e52011-04-24 08:57:21 +0000591 int ret = 0;
592 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000593 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200594 mbedtls_mpi T;
Hanno Becker73d7d792018-12-11 10:35:51 +0000595 MPI_VALIDATE_RET( X != NULL );
596 MPI_VALIDATE_RET( olen != NULL );
597 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000598
599 if( radix < 2 || radix > 16 )
Hanno Becker54c91dd2018-12-12 13:37:06 +0000600 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000601
Hanno Becker23cfea02019-02-04 09:45:07 +0000602 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
603 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
604 * `n`. If radix > 4, this might be a strict
605 * overapproximation of the number of
606 * radix-adic digits needed to present `n`. */
607 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
608 * present `n`. */
609
Janos Follath80470622019-03-06 13:43:02 +0000610 n += 1; /* Terminating null byte */
Hanno Becker23cfea02019-02-04 09:45:07 +0000611 n += 1; /* Compensate for the divisions above, which round down `n`
612 * in case it's not even. */
613 n += 1; /* Potential '-'-sign. */
614 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
615 * which always uses an even number of hex-digits. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000616
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100617 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000618 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100619 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200620 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000621 }
622
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100623 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200624 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000625
626 if( X->s == -1 )
Hanno Beckerc983c812019-02-01 16:41:30 +0000627 {
Paul Bakker5121ce52009-01-03 21:22:43 +0000628 *p++ = '-';
Hanno Beckerc983c812019-02-01 16:41:30 +0000629 buflen--;
630 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000631
632 if( radix == 16 )
633 {
Paul Bakker23986e52011-04-24 08:57:21 +0000634 int c;
635 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000636
Paul Bakker23986e52011-04-24 08:57:21 +0000637 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000638 {
Paul Bakker23986e52011-04-24 08:57:21 +0000639 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000640 {
Paul Bakker23986e52011-04-24 08:57:21 +0000641 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000642
Paul Bakker6c343d72014-07-10 14:36:19 +0200643 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000644 continue;
645
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000646 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000647 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000648 k = 1;
649 }
650 }
651 }
652 else
653 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200654 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000655
656 if( T.s == -1 )
657 T.s = 1;
658
Ron Eldora16fa292018-11-20 14:07:01 +0200659 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000660 }
661
662 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100663 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000664
665cleanup:
666
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200667 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000668
669 return( ret );
670}
671
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200672#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000673/*
674 * Read X from an opened file
675 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200676int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000677{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200678 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000679 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000680 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000681 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000682 * Buffer should have space for (short) label and decimal formatted MPI,
683 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000684 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200685 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000686
Hanno Becker73d7d792018-12-11 10:35:51 +0000687 MPI_VALIDATE_RET( X != NULL );
688 MPI_VALIDATE_RET( fin != NULL );
689
690 if( radix < 2 || radix > 16 )
691 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
692
Paul Bakker5121ce52009-01-03 21:22:43 +0000693 memset( s, 0, sizeof( s ) );
694 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200695 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000696
697 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000698 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200699 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000700
Hanno Beckerb2034b72017-04-26 11:46:46 +0100701 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
702 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000703
704 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100705 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000706 if( mpi_get_digit( &d, radix, *p ) != 0 )
707 break;
708
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200709 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000710}
711
712/*
713 * Write X into an opened file (or stdout if fout == NULL)
714 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200715int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000716{
Janos Follath24eed8d2019-11-22 13:21:35 +0000717 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +0000718 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000719 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000720 * Buffer should have space for (short) label and decimal formatted MPI,
721 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000722 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200723 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Hanno Becker73d7d792018-12-11 10:35:51 +0000724 MPI_VALIDATE_RET( X != NULL );
725
726 if( radix < 2 || radix > 16 )
727 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000728
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100729 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000730
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100731 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000732
733 if( p == NULL ) p = "";
734
735 plen = strlen( p );
736 slen = strlen( s );
737 s[slen++] = '\r';
738 s[slen++] = '\n';
739
740 if( fout != NULL )
741 {
742 if( fwrite( p, 1, plen, fout ) != plen ||
743 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200744 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000745 }
746 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200747 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000748
749cleanup:
750
751 return( ret );
752}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200753#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000754
Hanno Beckerda1655a2017-10-18 14:21:44 +0100755
756/* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
757 * into the storage form used by mbedtls_mpi. */
Hanno Beckerf8720072018-11-08 11:53:49 +0000758
759static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x )
760{
761 uint8_t i;
Hanno Becker031d6332019-05-01 17:09:11 +0100762 unsigned char *x_ptr;
Hanno Beckerf8720072018-11-08 11:53:49 +0000763 mbedtls_mpi_uint tmp = 0;
Hanno Becker031d6332019-05-01 17:09:11 +0100764
765 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ )
766 {
767 tmp <<= CHAR_BIT;
768 tmp |= (mbedtls_mpi_uint) *x_ptr;
769 }
770
Hanno Beckerf8720072018-11-08 11:53:49 +0000771 return( tmp );
772}
773
774static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x )
775{
776#if defined(__BYTE_ORDER__)
777
778/* Nothing to do on bigendian systems. */
779#if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ )
780 return( x );
781#endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
782
783#if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ )
784
785/* For GCC and Clang, have builtins for byte swapping. */
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000786#if defined(__GNUC__) && defined(__GNUC_PREREQ)
787#if __GNUC_PREREQ(4,3)
Hanno Beckerf8720072018-11-08 11:53:49 +0000788#define have_bswap
789#endif
Hanno Becker9f6d16a2019-01-02 17:15:06 +0000790#endif
791
792#if defined(__clang__) && defined(__has_builtin)
793#if __has_builtin(__builtin_bswap32) && \
794 __has_builtin(__builtin_bswap64)
795#define have_bswap
796#endif
797#endif
798
Hanno Beckerf8720072018-11-08 11:53:49 +0000799#if defined(have_bswap)
800 /* The compiler is hopefully able to statically evaluate this! */
801 switch( sizeof(mbedtls_mpi_uint) )
802 {
803 case 4:
804 return( __builtin_bswap32(x) );
805 case 8:
806 return( __builtin_bswap64(x) );
807 }
808#endif
809#endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */
810#endif /* __BYTE_ORDER__ */
811
812 /* Fall back to C-based reordering if we don't know the byte order
813 * or we couldn't use a compiler-specific builtin. */
814 return( mpi_uint_bigendian_to_host_c( x ) );
815}
816
Hanno Becker2be8a552018-10-25 12:40:09 +0100817static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs )
Hanno Beckerda1655a2017-10-18 14:21:44 +0100818{
Hanno Beckerda1655a2017-10-18 14:21:44 +0100819 mbedtls_mpi_uint *cur_limb_left;
820 mbedtls_mpi_uint *cur_limb_right;
Hanno Becker2be8a552018-10-25 12:40:09 +0100821 if( limbs == 0 )
822 return;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100823
824 /*
825 * Traverse limbs and
826 * - adapt byte-order in each limb
827 * - swap the limbs themselves.
828 * For that, simultaneously traverse the limbs from left to right
829 * and from right to left, as long as the left index is not bigger
830 * than the right index (it's not a problem if limbs is odd and the
831 * indices coincide in the last iteration).
832 */
Hanno Beckerda1655a2017-10-18 14:21:44 +0100833 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 );
834 cur_limb_left <= cur_limb_right;
835 cur_limb_left++, cur_limb_right-- )
836 {
Hanno Beckerf8720072018-11-08 11:53:49 +0000837 mbedtls_mpi_uint tmp;
838 /* Note that if cur_limb_left == cur_limb_right,
839 * this code effectively swaps the bytes only once. */
840 tmp = mpi_uint_bigendian_to_host( *cur_limb_left );
841 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right );
842 *cur_limb_right = tmp;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100843 }
Hanno Beckerda1655a2017-10-18 14:21:44 +0100844}
845
Paul Bakker5121ce52009-01-03 21:22:43 +0000846/*
Janos Follatha778a942019-02-13 10:28:28 +0000847 * Import X from unsigned binary data, little endian
848 */
849int mbedtls_mpi_read_binary_le( mbedtls_mpi *X,
850 const unsigned char *buf, size_t buflen )
851{
Janos Follath24eed8d2019-11-22 13:21:35 +0000852 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Janos Follatha778a942019-02-13 10:28:28 +0000853 size_t i;
854 size_t const limbs = CHARS_TO_LIMBS( buflen );
855
856 /* Ensure that target MPI has exactly the necessary number of limbs */
857 if( X->n != limbs )
858 {
859 mbedtls_mpi_free( X );
860 mbedtls_mpi_init( X );
861 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
862 }
863
864 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
865
866 for( i = 0; i < buflen; i++ )
867 X->p[i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3);
868
869cleanup:
870
Janos Follath171a7ef2019-02-15 16:17:45 +0000871 /*
872 * This function is also used to import keys. However, wiping the buffers
873 * upon failure is not necessary because failure only can happen before any
874 * input is copied.
875 */
Janos Follatha778a942019-02-13 10:28:28 +0000876 return( ret );
877}
878
879/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000880 * Import X from unsigned binary data, big endian
881 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200882int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000883{
Janos Follath24eed8d2019-11-22 13:21:35 +0000884 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Beckerda1655a2017-10-18 14:21:44 +0100885 size_t const limbs = CHARS_TO_LIMBS( buflen );
886 size_t const overhead = ( limbs * ciL ) - buflen;
887 unsigned char *Xp;
Paul Bakker5121ce52009-01-03 21:22:43 +0000888
Hanno Becker8ce11a32018-12-19 16:18:52 +0000889 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +0000890 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
891
Hanno Becker073c1992017-10-17 15:17:27 +0100892 /* Ensure that target MPI has exactly the necessary number of limbs */
893 if( X->n != limbs )
894 {
895 mbedtls_mpi_free( X );
896 mbedtls_mpi_init( X );
897 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
898 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200899 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000900
Hanno Becker0e810b92019-01-03 17:13:11 +0000901 /* Avoid calling `memcpy` with NULL source argument,
902 * even if buflen is 0. */
903 if( buf != NULL )
904 {
905 Xp = (unsigned char*) X->p;
906 memcpy( Xp + overhead, buf, buflen );
Hanno Beckerda1655a2017-10-18 14:21:44 +0100907
Hanno Becker0e810b92019-01-03 17:13:11 +0000908 mpi_bigendian_to_host( X->p, limbs );
909 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000910
911cleanup:
912
Janos Follath171a7ef2019-02-15 16:17:45 +0000913 /*
914 * This function is also used to import keys. However, wiping the buffers
915 * upon failure is not necessary because failure only can happen before any
916 * input is copied.
917 */
Paul Bakker5121ce52009-01-03 21:22:43 +0000918 return( ret );
919}
920
921/*
Janos Follathe344d0f2019-02-19 16:17:40 +0000922 * Export X into unsigned binary data, little endian
923 */
924int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X,
925 unsigned char *buf, size_t buflen )
926{
927 size_t stored_bytes = X->n * ciL;
928 size_t bytes_to_copy;
929 size_t i;
930
931 if( stored_bytes < buflen )
932 {
933 bytes_to_copy = stored_bytes;
934 }
935 else
936 {
937 bytes_to_copy = buflen;
938
939 /* The output buffer is smaller than the allocated size of X.
940 * However X may fit if its leading bytes are zero. */
941 for( i = bytes_to_copy; i < stored_bytes; i++ )
942 {
943 if( GET_BYTE( X, i ) != 0 )
944 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
945 }
946 }
947
948 for( i = 0; i < bytes_to_copy; i++ )
949 buf[i] = GET_BYTE( X, i );
950
951 if( stored_bytes < buflen )
952 {
953 /* Write trailing 0 bytes */
954 memset( buf + stored_bytes, 0, buflen - stored_bytes );
955 }
956
957 return( 0 );
958}
959
960/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000961 * Export X into unsigned binary data, big endian
962 */
Gilles Peskine11cdb052018-11-20 16:47:47 +0100963int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
964 unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000965{
Hanno Becker73d7d792018-12-11 10:35:51 +0000966 size_t stored_bytes;
Gilles Peskine11cdb052018-11-20 16:47:47 +0100967 size_t bytes_to_copy;
968 unsigned char *p;
969 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000970
Hanno Becker73d7d792018-12-11 10:35:51 +0000971 MPI_VALIDATE_RET( X != NULL );
972 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
973
974 stored_bytes = X->n * ciL;
975
Gilles Peskine11cdb052018-11-20 16:47:47 +0100976 if( stored_bytes < buflen )
977 {
978 /* There is enough space in the output buffer. Write initial
979 * null bytes and record the position at which to start
980 * writing the significant bytes. In this case, the execution
981 * trace of this function does not depend on the value of the
982 * number. */
983 bytes_to_copy = stored_bytes;
984 p = buf + buflen - stored_bytes;
985 memset( buf, 0, buflen - stored_bytes );
986 }
987 else
988 {
989 /* The output buffer is smaller than the allocated size of X.
990 * However X may fit if its leading bytes are zero. */
991 bytes_to_copy = buflen;
992 p = buf;
993 for( i = bytes_to_copy; i < stored_bytes; i++ )
994 {
995 if( GET_BYTE( X, i ) != 0 )
996 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
997 }
998 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000999
Gilles Peskine11cdb052018-11-20 16:47:47 +01001000 for( i = 0; i < bytes_to_copy; i++ )
1001 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
Paul Bakker5121ce52009-01-03 21:22:43 +00001002
1003 return( 0 );
1004}
1005
1006/*
1007 * Left-shift: X <<= count
1008 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001009int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +00001010{
Janos Follath24eed8d2019-11-22 13:21:35 +00001011 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001012 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001013 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +00001014 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001015
1016 v0 = count / (biL );
1017 t1 = count & (biL - 1);
1018
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001019 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +00001020
Paul Bakkerf9688572011-05-05 10:00:45 +00001021 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001022 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001023
1024 ret = 0;
1025
1026 /*
1027 * shift by count / limb_size
1028 */
1029 if( v0 > 0 )
1030 {
Paul Bakker23986e52011-04-24 08:57:21 +00001031 for( i = X->n; i > v0; i-- )
1032 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001033
Paul Bakker23986e52011-04-24 08:57:21 +00001034 for( ; i > 0; i-- )
1035 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001036 }
1037
1038 /*
1039 * shift by count % limb_size
1040 */
1041 if( t1 > 0 )
1042 {
1043 for( i = v0; i < X->n; i++ )
1044 {
1045 r1 = X->p[i] >> (biL - t1);
1046 X->p[i] <<= t1;
1047 X->p[i] |= r0;
1048 r0 = r1;
1049 }
1050 }
1051
1052cleanup:
1053
1054 return( ret );
1055}
1056
1057/*
1058 * Right-shift: X >>= count
1059 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001060int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +00001061{
Paul Bakker23986e52011-04-24 08:57:21 +00001062 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001063 mbedtls_mpi_uint r0 = 0, r1;
Hanno Becker73d7d792018-12-11 10:35:51 +00001064 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001065
1066 v0 = count / biL;
1067 v1 = count & (biL - 1);
1068
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +01001069 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001070 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +01001071
Paul Bakker5121ce52009-01-03 21:22:43 +00001072 /*
1073 * shift by count / limb_size
1074 */
1075 if( v0 > 0 )
1076 {
1077 for( i = 0; i < X->n - v0; i++ )
1078 X->p[i] = X->p[i + v0];
1079
1080 for( ; i < X->n; i++ )
1081 X->p[i] = 0;
1082 }
1083
1084 /*
1085 * shift by count % limb_size
1086 */
1087 if( v1 > 0 )
1088 {
Paul Bakker23986e52011-04-24 08:57:21 +00001089 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001090 {
Paul Bakker23986e52011-04-24 08:57:21 +00001091 r1 = X->p[i - 1] << (biL - v1);
1092 X->p[i - 1] >>= v1;
1093 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001094 r0 = r1;
1095 }
1096 }
1097
1098 return( 0 );
1099}
1100
1101/*
1102 * Compare unsigned values
1103 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001104int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001105{
Paul Bakker23986e52011-04-24 08:57:21 +00001106 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001107 MPI_VALIDATE_RET( X != NULL );
1108 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001109
Paul Bakker23986e52011-04-24 08:57:21 +00001110 for( i = X->n; i > 0; i-- )
1111 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001112 break;
1113
Paul Bakker23986e52011-04-24 08:57:21 +00001114 for( j = Y->n; j > 0; j-- )
1115 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001116 break;
1117
Paul Bakker23986e52011-04-24 08:57:21 +00001118 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001119 return( 0 );
1120
1121 if( i > j ) return( 1 );
1122 if( j > i ) return( -1 );
1123
Paul Bakker23986e52011-04-24 08:57:21 +00001124 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001125 {
Paul Bakker23986e52011-04-24 08:57:21 +00001126 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
1127 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001128 }
1129
1130 return( 0 );
1131}
1132
1133/*
1134 * Compare signed values
1135 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001136int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +00001137{
Paul Bakker23986e52011-04-24 08:57:21 +00001138 size_t i, j;
Hanno Becker73d7d792018-12-11 10:35:51 +00001139 MPI_VALIDATE_RET( X != NULL );
1140 MPI_VALIDATE_RET( Y != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001141
Paul Bakker23986e52011-04-24 08:57:21 +00001142 for( i = X->n; i > 0; i-- )
1143 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001144 break;
1145
Paul Bakker23986e52011-04-24 08:57:21 +00001146 for( j = Y->n; j > 0; j-- )
1147 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001148 break;
1149
Paul Bakker23986e52011-04-24 08:57:21 +00001150 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001151 return( 0 );
1152
1153 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +00001154 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001155
1156 if( X->s > 0 && Y->s < 0 ) return( 1 );
1157 if( Y->s > 0 && X->s < 0 ) return( -1 );
1158
Paul Bakker23986e52011-04-24 08:57:21 +00001159 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001160 {
Paul Bakker23986e52011-04-24 08:57:21 +00001161 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
1162 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +00001163 }
1164
1165 return( 0 );
1166}
1167
Janos Follath3f6f0e42019-10-14 09:09:32 +01001168/** Decide if an integer is less than the other, without branches.
1169 *
1170 * \param x First integer.
1171 * \param y Second integer.
1172 *
1173 * \return 1 if \p x is less than \p y, 0 otherwise
1174 */
Janos Follath0e5532d2019-10-11 14:21:53 +01001175static unsigned ct_lt_mpi_uint( const mbedtls_mpi_uint x,
1176 const mbedtls_mpi_uint y )
Janos Follathee6abce2019-09-05 14:47:19 +01001177{
1178 mbedtls_mpi_uint ret;
1179 mbedtls_mpi_uint cond;
1180
1181 /*
1182 * Check if the most significant bits (MSB) of the operands are different.
1183 */
1184 cond = ( x ^ y );
1185 /*
1186 * If the MSB are the same then the difference x-y will be negative (and
1187 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
1188 */
1189 ret = ( x - y ) & ~cond;
1190 /*
1191 * If the MSB are different, then the operand with the MSB of 1 is the
1192 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
1193 * the MSB of y is 0.)
1194 */
1195 ret |= y & cond;
1196
1197
Janos Follatha0f732b2019-10-14 08:59:14 +01001198 ret = ret >> ( biL - 1 );
Janos Follathee6abce2019-09-05 14:47:19 +01001199
Janos Follath67ce6472019-10-29 15:08:46 +00001200 return (unsigned) ret;
Janos Follathee6abce2019-09-05 14:47:19 +01001201}
1202
1203/*
1204 * Compare signed values in constant time
1205 */
Janos Follath0e5532d2019-10-11 14:21:53 +01001206int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
1207 unsigned *ret )
Janos Follathee6abce2019-09-05 14:47:19 +01001208{
1209 size_t i;
Janos Follathbb5147f2019-10-28 12:23:18 +00001210 /* The value of any of these variables is either 0 or 1 at all times. */
Janos Follath5e614ce2019-10-28 12:31:34 +00001211 unsigned cond, done, X_is_negative, Y_is_negative;
Janos Follathee6abce2019-09-05 14:47:19 +01001212
1213 MPI_VALIDATE_RET( X != NULL );
1214 MPI_VALIDATE_RET( Y != NULL );
1215 MPI_VALIDATE_RET( ret != NULL );
1216
1217 if( X->n != Y->n )
1218 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1219
1220 /*
Janos Follath73ba9ec2019-10-28 12:12:15 +00001221 * Set sign_N to 1 if N >= 0, 0 if N < 0.
1222 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
Janos Follathee6abce2019-09-05 14:47:19 +01001223 */
Janos Follath5e614ce2019-10-28 12:31:34 +00001224 X_is_negative = ( X->s & 2 ) >> 1;
1225 Y_is_negative = ( Y->s & 2 ) >> 1;
Janos Follath0e5532d2019-10-11 14:21:53 +01001226
1227 /*
1228 * If the signs are different, then the positive operand is the bigger.
Janos Follath5e614ce2019-10-28 12:31:34 +00001229 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
1230 * is false if X is positive (X_is_negative == 0).
Janos Follath0e5532d2019-10-11 14:21:53 +01001231 */
Janos Follath5e614ce2019-10-28 12:31:34 +00001232 cond = ( X_is_negative ^ Y_is_negative );
1233 *ret = cond & X_is_negative;
Janos Follath0e5532d2019-10-11 14:21:53 +01001234
1235 /*
Janos Follathbb5147f2019-10-28 12:23:18 +00001236 * This is a constant-time function. We might have the result, but we still
Janos Follath0e5532d2019-10-11 14:21:53 +01001237 * need to go through the loop. Record if we have the result already.
1238 */
Janos Follathee6abce2019-09-05 14:47:19 +01001239 done = cond;
1240
1241 for( i = X->n; i > 0; i-- )
1242 {
1243 /*
Janos Follath30702422019-11-05 12:24:52 +00001244 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
1245 * X and Y are negative.
Janos Follath0e5532d2019-10-11 14:21:53 +01001246 *
1247 * Again even if we can make a decision, we just mark the result and
1248 * the fact that we are done and continue looping.
Janos Follathee6abce2019-09-05 14:47:19 +01001249 */
Janos Follath30702422019-11-05 12:24:52 +00001250 cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] );
1251 *ret |= cond & ( 1 - done ) & X_is_negative;
Janos Follathc50e6d52019-10-28 12:37:21 +00001252 done |= cond;
Janos Follathee6abce2019-09-05 14:47:19 +01001253
1254 /*
Janos Follath30702422019-11-05 12:24:52 +00001255 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
1256 * X and Y are positive.
Janos Follath0e5532d2019-10-11 14:21:53 +01001257 *
1258 * Again even if we can make a decision, we just mark the result and
1259 * the fact that we are done and continue looping.
Janos Follathee6abce2019-09-05 14:47:19 +01001260 */
Janos Follath30702422019-11-05 12:24:52 +00001261 cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] );
1262 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
Janos Follathc50e6d52019-10-28 12:37:21 +00001263 done |= cond;
Janos Follathee6abce2019-09-05 14:47:19 +01001264 }
1265
1266 return( 0 );
1267}
1268
Paul Bakker5121ce52009-01-03 21:22:43 +00001269/*
1270 * Compare signed values
1271 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001272int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +00001273{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001274 mbedtls_mpi Y;
1275 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001276 MPI_VALIDATE_RET( X != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001277
1278 *p = ( z < 0 ) ? -z : z;
1279 Y.s = ( z < 0 ) ? -1 : 1;
1280 Y.n = 1;
1281 Y.p = p;
1282
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001283 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001284}
1285
1286/*
1287 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1288 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001289int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001290{
Janos Follath24eed8d2019-11-22 13:21:35 +00001291 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001292 size_t i, j;
Janos Follath6c922682015-10-30 17:43:11 +01001293 mbedtls_mpi_uint *o, *p, c, tmp;
Hanno Becker73d7d792018-12-11 10:35:51 +00001294 MPI_VALIDATE_RET( X != NULL );
1295 MPI_VALIDATE_RET( A != NULL );
1296 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001297
1298 if( X == B )
1299 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001300 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +00001301 }
1302
1303 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001304 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +02001305
Paul Bakkerf7ca7b92009-06-20 10:31:06 +00001306 /*
1307 * X should always be positive as a result of unsigned additions.
1308 */
1309 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001310
Paul Bakker23986e52011-04-24 08:57:21 +00001311 for( j = B->n; j > 0; j-- )
1312 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001313 break;
1314
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001315 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001316
1317 o = B->p; p = X->p; c = 0;
1318
Janos Follath6c922682015-10-30 17:43:11 +01001319 /*
1320 * tmp is used because it might happen that p == o
1321 */
Paul Bakker23986e52011-04-24 08:57:21 +00001322 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001323 {
Janos Follath6c922682015-10-30 17:43:11 +01001324 tmp= *o;
Paul Bakker5121ce52009-01-03 21:22:43 +00001325 *p += c; c = ( *p < c );
Janos Follath6c922682015-10-30 17:43:11 +01001326 *p += tmp; c += ( *p < tmp );
Paul Bakker5121ce52009-01-03 21:22:43 +00001327 }
1328
1329 while( c != 0 )
1330 {
1331 if( i >= X->n )
1332 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001333 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001334 p = X->p + i;
1335 }
1336
Paul Bakker2d319fd2012-09-16 21:34:26 +00001337 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +00001338 }
1339
1340cleanup:
1341
1342 return( ret );
1343}
1344
Gilles Peskine09ec10a2020-06-09 10:39:38 +02001345/**
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001346 * Helper for mbedtls_mpi subtraction.
1347 *
1348 * Calculate d - s where d and s have the same size.
1349 * This function operates modulo (2^ciL)^n and returns the carry
1350 * (1 if there was a wraparound, i.e. if `d < s`, and 0 otherwise).
1351 *
1352 * \param n Number of limbs of \p d and \p s.
1353 * \param[in,out] d On input, the left operand.
1354 * On output, the result of the subtraction:
Gilles Peskine09ec10a2020-06-09 10:39:38 +02001355 * \param[in] s The right operand.
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001356 *
1357 * \return 1 if `d < s`.
1358 * 0 if `d >= s`.
Paul Bakker5121ce52009-01-03 21:22:43 +00001359 */
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001360static mbedtls_mpi_uint mpi_sub_hlp( size_t n,
1361 mbedtls_mpi_uint *d,
1362 const mbedtls_mpi_uint *s )
Paul Bakker5121ce52009-01-03 21:22:43 +00001363{
Paul Bakker23986e52011-04-24 08:57:21 +00001364 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001365 mbedtls_mpi_uint c, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001366
1367 for( i = c = 0; i < n; i++, s++, d++ )
1368 {
1369 z = ( *d < c ); *d -= c;
1370 c = ( *d < *s ) + z; *d -= *s;
1371 }
1372
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001373 return( c );
Paul Bakker5121ce52009-01-03 21:22:43 +00001374}
1375
1376/*
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001377 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
Paul Bakker5121ce52009-01-03 21:22:43 +00001378 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001379int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001380{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001381 mbedtls_mpi TB;
Janos Follath24eed8d2019-11-22 13:21:35 +00001382 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001383 size_t n;
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001384 mbedtls_mpi_uint carry;
Hanno Becker73d7d792018-12-11 10:35:51 +00001385 MPI_VALIDATE_RET( X != NULL );
1386 MPI_VALIDATE_RET( A != NULL );
1387 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001388
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001389 mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001390
1391 if( X == B )
1392 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001393 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001394 B = &TB;
1395 }
1396
1397 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001398 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001399
Paul Bakker1ef7a532009-06-20 10:50:55 +00001400 /*
Paul Bakker60b1d102013-10-29 10:02:51 +01001401 * X should always be positive as a result of unsigned subtractions.
Paul Bakker1ef7a532009-06-20 10:50:55 +00001402 */
1403 X->s = 1;
1404
Paul Bakker5121ce52009-01-03 21:22:43 +00001405 ret = 0;
1406
Paul Bakker23986e52011-04-24 08:57:21 +00001407 for( n = B->n; n > 0; n-- )
1408 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001409 break;
1410
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001411 carry = mpi_sub_hlp( n, X->p, B->p );
1412 if( carry != 0 )
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001413 {
Gilles Peskine0e5faf62020-06-08 22:50:35 +02001414 /* Propagate the carry to the first nonzero limb of X. */
1415 for( ; n < X->n && X->p[n] == 0; n++ )
1416 --X->p[n];
1417 /* If we ran out of space for the carry, it means that the result
1418 * is negative. */
1419 if( n == X->n )
1420 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1421 --X->p[n];
Gilles Peskinec097e9e2020-06-08 21:58:22 +02001422 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001423
1424cleanup:
1425
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001426 mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001427
1428 return( ret );
1429}
1430
1431/*
1432 * Signed addition: X = A + B
1433 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001434int mbedtls_mpi_add_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/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001467 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001468 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001469int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001470{
Hanno Becker73d7d792018-12-11 10:35:51 +00001471 int ret, s;
1472 MPI_VALIDATE_RET( X != NULL );
1473 MPI_VALIDATE_RET( A != NULL );
1474 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001475
Hanno Becker73d7d792018-12-11 10:35:51 +00001476 s = A->s;
Paul Bakker5121ce52009-01-03 21:22:43 +00001477 if( A->s * B->s > 0 )
1478 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001479 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001480 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001481 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001482 X->s = s;
1483 }
1484 else
1485 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001486 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001487 X->s = -s;
1488 }
1489 }
1490 else
1491 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001492 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001493 X->s = s;
1494 }
1495
1496cleanup:
1497
1498 return( ret );
1499}
1500
1501/*
1502 * Signed addition: X = A + b
1503 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001504int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001505{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001506 mbedtls_mpi _B;
1507 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001508 MPI_VALIDATE_RET( X != NULL );
1509 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001510
1511 p[0] = ( b < 0 ) ? -b : b;
1512 _B.s = ( b < 0 ) ? -1 : 1;
1513 _B.n = 1;
1514 _B.p = p;
1515
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001516 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001517}
1518
1519/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001520 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001521 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001522int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001523{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001524 mbedtls_mpi _B;
1525 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001526 MPI_VALIDATE_RET( X != NULL );
1527 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001528
1529 p[0] = ( b < 0 ) ? -b : b;
1530 _B.s = ( b < 0 ) ? -1 : 1;
1531 _B.n = 1;
1532 _B.p = p;
1533
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001534 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001535}
1536
1537/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001538 * Helper for mbedtls_mpi multiplication
Paul Bakkerfc4f46f2013-06-24 19:23:56 +02001539 */
1540static
1541#if defined(__APPLE__) && defined(__arm__)
1542/*
1543 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1544 * appears to need this to prevent bad ARM code generation at -O3.
1545 */
1546__attribute__ ((noinline))
1547#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001548void 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 +00001549{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001550 mbedtls_mpi_uint c = 0, t = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001551
1552#if defined(MULADDC_HUIT)
1553 for( ; i >= 8; i -= 8 )
1554 {
1555 MULADDC_INIT
1556 MULADDC_HUIT
1557 MULADDC_STOP
1558 }
1559
1560 for( ; i > 0; i-- )
1561 {
1562 MULADDC_INIT
1563 MULADDC_CORE
1564 MULADDC_STOP
1565 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001566#else /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001567 for( ; i >= 16; i -= 16 )
1568 {
1569 MULADDC_INIT
1570 MULADDC_CORE MULADDC_CORE
1571 MULADDC_CORE MULADDC_CORE
1572 MULADDC_CORE MULADDC_CORE
1573 MULADDC_CORE MULADDC_CORE
1574
1575 MULADDC_CORE MULADDC_CORE
1576 MULADDC_CORE MULADDC_CORE
1577 MULADDC_CORE MULADDC_CORE
1578 MULADDC_CORE MULADDC_CORE
1579 MULADDC_STOP
1580 }
1581
1582 for( ; i >= 8; i -= 8 )
1583 {
1584 MULADDC_INIT
1585 MULADDC_CORE MULADDC_CORE
1586 MULADDC_CORE MULADDC_CORE
1587
1588 MULADDC_CORE MULADDC_CORE
1589 MULADDC_CORE MULADDC_CORE
1590 MULADDC_STOP
1591 }
1592
1593 for( ; i > 0; i-- )
1594 {
1595 MULADDC_INIT
1596 MULADDC_CORE
1597 MULADDC_STOP
1598 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001599#endif /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001600
1601 t++;
1602
1603 do {
1604 *d += c; c = ( *d < c ); d++;
1605 }
1606 while( c != 0 );
1607}
1608
1609/*
1610 * Baseline multiplication: X = A * B (HAC 14.12)
1611 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001612int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001613{
Janos Follath24eed8d2019-11-22 13:21:35 +00001614 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001615 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001616 mbedtls_mpi TA, TB;
Hanno Becker73d7d792018-12-11 10:35:51 +00001617 MPI_VALIDATE_RET( X != NULL );
1618 MPI_VALIDATE_RET( A != NULL );
1619 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001620
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001621 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001622
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001623 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1624 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001625
Paul Bakker23986e52011-04-24 08:57:21 +00001626 for( i = A->n; i > 0; i-- )
1627 if( A->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001628 break;
1629
Paul Bakker23986e52011-04-24 08:57:21 +00001630 for( j = B->n; j > 0; j-- )
1631 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001632 break;
1633
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001634 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1635 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001636
Alexey Skalozub8e75e682016-01-13 21:59:27 +02001637 for( ; j > 0; j-- )
1638 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001639
1640 X->s = A->s * B->s;
1641
1642cleanup:
1643
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001644 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001645
1646 return( ret );
1647}
1648
1649/*
1650 * Baseline multiplication: X = A * b
1651 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001652int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001653{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001654 mbedtls_mpi _B;
1655 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001656 MPI_VALIDATE_RET( X != NULL );
1657 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001658
1659 _B.s = 1;
1660 _B.n = 1;
1661 _B.p = p;
1662 p[0] = b;
1663
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001664 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001665}
1666
1667/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001668 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1669 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001670 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001671static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1672 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001673{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001674#if defined(MBEDTLS_HAVE_UDBL)
1675 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001676#else
Simon Butcher9803d072016-01-03 00:24:34 +00001677 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1678 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001679 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1680 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001681 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001682#endif
1683
Simon Butcher15b15d12015-11-26 19:35:03 +00001684 /*
1685 * Check for overflow
1686 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001687 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001688 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001689 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001690
Simon Butcherf5ba0452015-12-27 23:01:55 +00001691 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001692 }
1693
1694#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001695 dividend = (mbedtls_t_udbl) u1 << biL;
1696 dividend |= (mbedtls_t_udbl) u0;
1697 quotient = dividend / d;
1698 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1699 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1700
1701 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001702 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001703
1704 return (mbedtls_mpi_uint) quotient;
1705#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001706
1707 /*
1708 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1709 * Vol. 2 - Seminumerical Algorithms, Knuth
1710 */
1711
1712 /*
1713 * Normalize the divisor, d, and dividend, u0, u1
1714 */
1715 s = mbedtls_clz( d );
1716 d = d << s;
1717
1718 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001719 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001720 u0 = u0 << s;
1721
1722 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001723 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001724
1725 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001726 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001727
1728 /*
1729 * Find the first quotient and remainder
1730 */
1731 q1 = u1 / d1;
1732 r0 = u1 - d1 * q1;
1733
1734 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1735 {
1736 q1 -= 1;
1737 r0 += d1;
1738
1739 if ( r0 >= radix ) break;
1740 }
1741
Simon Butcherf5ba0452015-12-27 23:01:55 +00001742 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001743 q0 = rAX / d1;
1744 r0 = rAX - q0 * d1;
1745
1746 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1747 {
1748 q0 -= 1;
1749 r0 += d1;
1750
1751 if ( r0 >= radix ) break;
1752 }
1753
1754 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001755 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001756
1757 quotient = q1 * radix + q0;
1758
1759 return quotient;
1760#endif
1761}
1762
1763/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001764 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001765 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001766int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1767 const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001768{
Janos Follath24eed8d2019-11-22 13:21:35 +00001769 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00001770 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001771 mbedtls_mpi X, Y, Z, T1, T2;
Alexander Kd19a1932019-11-01 18:20:42 +03001772 mbedtls_mpi_uint TP2[3];
Hanno Becker73d7d792018-12-11 10:35:51 +00001773 MPI_VALIDATE_RET( A != NULL );
1774 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001775
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001776 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1777 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001778
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001779 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001780 mbedtls_mpi_init( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001781 /*
1782 * Avoid dynamic memory allocations for constant-size T2.
1783 *
1784 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1785 * so nobody increase the size of the MPI and we're safe to use an on-stack
1786 * buffer.
1787 */
Alexander K35d6d462019-10-31 14:46:45 +03001788 T2.s = 1;
Alexander Kd19a1932019-11-01 18:20:42 +03001789 T2.n = sizeof( TP2 ) / sizeof( *TP2 );
1790 T2.p = TP2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001791
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001792 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001793 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001794 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1795 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001796 return( 0 );
1797 }
1798
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001799 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1800 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001801 X.s = Y.s = 1;
1802
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001803 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1804 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1805 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001806
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001807 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001808 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001809 {
1810 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001811 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1812 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001813 }
1814 else k = 0;
1815
1816 n = X.n - 1;
1817 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001818 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001819
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001820 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001821 {
1822 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001823 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001824 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001825 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001826
1827 for( i = n; i > t ; i-- )
1828 {
1829 if( X.p[i] >= Y.p[t] )
1830 Z.p[i - t - 1] = ~0;
1831 else
1832 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001833 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1834 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001835 }
1836
Alexander K35d6d462019-10-31 14:46:45 +03001837 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1838 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1839 T2.p[2] = X.p[i];
1840
Paul Bakker5121ce52009-01-03 21:22:43 +00001841 Z.p[i - t - 1]++;
1842 do
1843 {
1844 Z.p[i - t - 1]--;
1845
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001846 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001847 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001848 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001849 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001850 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001851 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001852
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001853 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1854 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1855 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001856
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001857 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001858 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001859 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1860 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1861 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001862 Z.p[i - t - 1]--;
1863 }
1864 }
1865
1866 if( Q != NULL )
1867 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001868 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001869 Q->s = A->s * B->s;
1870 }
1871
1872 if( R != NULL )
1873 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001874 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001875 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001876 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001877
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001878 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001879 R->s = 1;
1880 }
1881
1882cleanup:
1883
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001884 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
Alexander K35d6d462019-10-31 14:46:45 +03001885 mbedtls_mpi_free( &T1 );
Alexander Kd19a1932019-11-01 18:20:42 +03001886 mbedtls_platform_zeroize( TP2, sizeof( TP2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001887
1888 return( ret );
1889}
1890
1891/*
1892 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001893 */
Hanno Becker73d7d792018-12-11 10:35:51 +00001894int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1895 const mbedtls_mpi *A,
1896 mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001897{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001898 mbedtls_mpi _B;
1899 mbedtls_mpi_uint p[1];
Hanno Becker73d7d792018-12-11 10:35:51 +00001900 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001901
1902 p[0] = ( b < 0 ) ? -b : b;
1903 _B.s = ( b < 0 ) ? -1 : 1;
1904 _B.n = 1;
1905 _B.p = p;
1906
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001907 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001908}
1909
1910/*
1911 * Modulo: R = A mod B
1912 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001913int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001914{
Janos Follath24eed8d2019-11-22 13:21:35 +00001915 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker73d7d792018-12-11 10:35:51 +00001916 MPI_VALIDATE_RET( R != NULL );
1917 MPI_VALIDATE_RET( A != NULL );
1918 MPI_VALIDATE_RET( B != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001919
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001920 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1921 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001922
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001923 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001924
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001925 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1926 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001927
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001928 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1929 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001930
1931cleanup:
1932
1933 return( ret );
1934}
1935
1936/*
1937 * Modulo: r = A mod b
1938 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001939int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001940{
Paul Bakker23986e52011-04-24 08:57:21 +00001941 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001942 mbedtls_mpi_uint x, y, z;
Hanno Becker73d7d792018-12-11 10:35:51 +00001943 MPI_VALIDATE_RET( r != NULL );
1944 MPI_VALIDATE_RET( A != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001945
1946 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001947 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001948
1949 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001950 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001951
1952 /*
1953 * handle trivial cases
1954 */
1955 if( b == 1 )
1956 {
1957 *r = 0;
1958 return( 0 );
1959 }
1960
1961 if( b == 2 )
1962 {
1963 *r = A->p[0] & 1;
1964 return( 0 );
1965 }
1966
1967 /*
1968 * general case
1969 */
Paul Bakker23986e52011-04-24 08:57:21 +00001970 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001971 {
Paul Bakker23986e52011-04-24 08:57:21 +00001972 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001973 y = ( y << biH ) | ( x >> biH );
1974 z = y / b;
1975 y -= z * b;
1976
1977 x <<= biH;
1978 y = ( y << biH ) | ( x >> biH );
1979 z = y / b;
1980 y -= z * b;
1981 }
1982
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001983 /*
1984 * If A is negative, then the current y represents a negative value.
1985 * Flipping it to the positive side.
1986 */
1987 if( A->s < 0 && y != 0 )
1988 y = b - y;
1989
Paul Bakker5121ce52009-01-03 21:22:43 +00001990 *r = y;
1991
1992 return( 0 );
1993}
1994
1995/*
1996 * Fast Montgomery initialization (thanks to Tom St Denis)
1997 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001998static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001999{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002000 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01002001 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00002002
2003 x = m0;
2004 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00002005
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01002006 for( i = biL; i >= 8; i /= 2 )
2007 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002008
2009 *mm = ~x + 1;
2010}
2011
Gilles Peskine2a82f722020-06-04 15:00:49 +02002012/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
2013 *
2014 * \param[in,out] A One of the numbers to multiply.
Gilles Peskine221626f2020-06-08 22:37:50 +02002015 * It must have at least as many limbs as N
2016 * (A->n >= N->n), and any limbs beyond n are ignored.
Gilles Peskine2a82f722020-06-04 15:00:49 +02002017 * On successful completion, A contains the result of
2018 * the multiplication A * B * R^-1 mod N where
2019 * R = (2^ciL)^n.
2020 * \param[in] B One of the numbers to multiply.
2021 * It must be nonzero and must not have more limbs than N
2022 * (B->n <= N->n).
2023 * \param[in] N The modulo. N must be odd.
2024 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
2025 * This is -N^-1 mod 2^ciL.
2026 * \param[in,out] T A bignum for temporary storage.
2027 * It must be at least twice the limb size of N plus 2
2028 * (T->n >= 2 * (N->n + 1)).
2029 * Its initial content is unused and
2030 * its final content is indeterminate.
2031 * Note that unlike the usual convention in the library
2032 * for `const mbedtls_mpi*`, the content of T can change.
Paul Bakker5121ce52009-01-03 21:22:43 +00002033 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02002034static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002035 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00002036{
Paul Bakker23986e52011-04-24 08:57:21 +00002037 size_t i, n, m;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002038 mbedtls_mpi_uint u0, u1, *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00002039
2040 memset( T->p, 0, T->n * ciL );
2041
2042 d = T->p;
2043 n = N->n;
2044 m = ( B->n < n ) ? B->n : n;
2045
2046 for( i = 0; i < n; i++ )
2047 {
2048 /*
2049 * T = (T + u0*B + u1*N) / 2^biL
2050 */
2051 u0 = A->p[i];
2052 u1 = ( d[0] + u0 * B->p[0] ) * mm;
2053
2054 mpi_mul_hlp( m, B->p, d, u0 );
2055 mpi_mul_hlp( n, N->p, d, u1 );
2056
2057 *d++ = u0; d[n + 1] = 0;
2058 }
2059
Gilles Peskine221626f2020-06-08 22:37:50 +02002060 /* At this point, d is either the desired result or the desired result
2061 * plus N. We now potentially subtract N, avoiding leaking whether the
2062 * subtraction is performed through side channels. */
Paul Bakker5121ce52009-01-03 21:22:43 +00002063
Gilles Peskine221626f2020-06-08 22:37:50 +02002064 /* Copy the n least significant limbs of d to A, so that
2065 * A = d if d < N (recall that N has n limbs). */
2066 memcpy( A->p, d, n * ciL );
Gilles Peskine09ec10a2020-06-09 10:39:38 +02002067 /* If d >= N then we want to set A to d - N. To prevent timing attacks,
Gilles Peskine221626f2020-06-08 22:37:50 +02002068 * do the calculation without using conditional tests. */
2069 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
Gilles Peskine132c0972020-06-04 21:05:24 +02002070 d[n] += 1;
Gilles Peskinec097e9e2020-06-08 21:58:22 +02002071 d[n] -= mpi_sub_hlp( n, d, N->p );
Gilles Peskine221626f2020-06-08 22:37:50 +02002072 /* If d0 < N then d < (2^biL)^n
2073 * so d[n] == 0 and we want to keep A as it is.
2074 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
2075 * so d[n] == 1 and we want to set A to the result of the subtraction
2076 * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
2077 * This exactly corresponds to a conditional assignment. */
2078 mpi_safe_cond_assign( n, A->p, d, (unsigned char) d[n] );
Paul Bakker5121ce52009-01-03 21:22:43 +00002079}
2080
2081/*
2082 * Montgomery reduction: A = A * R^-1 mod N
Gilles Peskine2a82f722020-06-04 15:00:49 +02002083 *
2084 * See mpi_montmul() regarding constraints and guarantees on the parameters.
Paul Bakker5121ce52009-01-03 21:22:43 +00002085 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02002086static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
2087 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00002088{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002089 mbedtls_mpi_uint z = 1;
2090 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00002091
Paul Bakker8ddb6452013-02-27 14:56:33 +01002092 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00002093 U.p = &z;
2094
Gilles Peskine4e91d472020-06-04 20:55:15 +02002095 mpi_montmul( A, &U, N, mm, T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002096}
2097
2098/*
2099 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
2100 */
Hanno Becker73d7d792018-12-11 10:35:51 +00002101int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
2102 const mbedtls_mpi *E, const mbedtls_mpi *N,
2103 mbedtls_mpi *_RR )
Paul Bakker5121ce52009-01-03 21:22:43 +00002104{
Janos Follath24eed8d2019-11-22 13:21:35 +00002105 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00002106 size_t wbits, wsize, one = 1;
2107 size_t i, j, nblimbs;
2108 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002109 mbedtls_mpi_uint ei, mm, state;
2110 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00002111 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00002112
Hanno Becker73d7d792018-12-11 10:35:51 +00002113 MPI_VALIDATE_RET( X != NULL );
2114 MPI_VALIDATE_RET( A != NULL );
2115 MPI_VALIDATE_RET( E != NULL );
2116 MPI_VALIDATE_RET( N != NULL );
2117
Hanno Becker8d1dd1b2017-09-28 11:02:24 +01002118 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002119 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002120
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002121 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
2122 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002123
2124 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00002125 * Init temps and window size
2126 */
2127 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002128 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
2129 mbedtls_mpi_init( &Apos );
Paul Bakker5121ce52009-01-03 21:22:43 +00002130 memset( W, 0, sizeof( W ) );
2131
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002132 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00002133
2134 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2135 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2136
Peter Kolbuse6bcad32018-12-11 14:01:44 -06002137#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002138 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2139 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Peter Kolbuse6bcad32018-12-11 14:01:44 -06002140#endif
Paul Bakkerb6d5f082011-11-25 11:52:11 +00002141
Paul Bakker5121ce52009-01-03 21:22:43 +00002142 j = N->n + 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002143 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2144 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2145 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002146
2147 /*
Paul Bakker50546922012-05-19 08:40:49 +00002148 * Compensate for negative A (and correct at the end)
2149 */
2150 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00002151 if( neg )
2152 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002153 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00002154 Apos.s = 1;
2155 A = &Apos;
2156 }
2157
2158 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00002159 * If 1st call, pre-compute R^2 mod N
2160 */
2161 if( _RR == NULL || _RR->p == NULL )
2162 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002163 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2164 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2165 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002166
2167 if( _RR != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002168 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002169 }
2170 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002171 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002172
2173 /*
2174 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2175 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002176 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
2177 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Paul Bakkerc2024f42014-01-23 20:38:35 +01002178 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002179 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002180
Gilles Peskine4e91d472020-06-04 20:55:15 +02002181 mpi_montmul( &W[1], &RR, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002182
2183 /*
2184 * X = R^2 * R^-1 mod N = R mod N
2185 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002186 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Gilles Peskine4e91d472020-06-04 20:55:15 +02002187 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002188
2189 if( wsize > 1 )
2190 {
2191 /*
2192 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2193 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002194 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002195
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002196 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2197 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002198
2199 for( i = 0; i < wsize - 1; i++ )
Gilles Peskine4e91d472020-06-04 20:55:15 +02002200 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01002201
Paul Bakker5121ce52009-01-03 21:22:43 +00002202 /*
2203 * W[i] = W[i - 1] * W[1]
2204 */
Paul Bakker66d5d072014-06-17 16:39:18 +02002205 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002206 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002207 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2208 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002209
Gilles Peskine4e91d472020-06-04 20:55:15 +02002210 mpi_montmul( &W[i], &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002211 }
2212 }
2213
2214 nblimbs = E->n;
2215 bufsize = 0;
2216 nbits = 0;
2217 wbits = 0;
2218 state = 0;
2219
2220 while( 1 )
2221 {
2222 if( bufsize == 0 )
2223 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01002224 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002225 break;
2226
Paul Bakker0d7702c2013-10-29 16:18:35 +01002227 nblimbs--;
2228
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002229 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00002230 }
2231
2232 bufsize--;
2233
2234 ei = (E->p[nblimbs] >> bufsize) & 1;
2235
2236 /*
2237 * skip leading 0s
2238 */
2239 if( ei == 0 && state == 0 )
2240 continue;
2241
2242 if( ei == 0 && state == 1 )
2243 {
2244 /*
2245 * out of window, square X
2246 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02002247 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002248 continue;
2249 }
2250
2251 /*
2252 * add ei to current window
2253 */
2254 state = 2;
2255
2256 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02002257 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002258
2259 if( nbits == wsize )
2260 {
2261 /*
2262 * X = X^wsize R^-1 mod N
2263 */
2264 for( i = 0; i < wsize; i++ )
Gilles Peskine4e91d472020-06-04 20:55:15 +02002265 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002266
2267 /*
2268 * X = X * W[wbits] R^-1 mod N
2269 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02002270 mpi_montmul( X, &W[wbits], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002271
2272 state--;
2273 nbits = 0;
2274 wbits = 0;
2275 }
2276 }
2277
2278 /*
2279 * process the remaining bits
2280 */
2281 for( i = 0; i < nbits; i++ )
2282 {
Gilles Peskine4e91d472020-06-04 20:55:15 +02002283 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002284
2285 wbits <<= 1;
2286
Paul Bakker66d5d072014-06-17 16:39:18 +02002287 if( ( wbits & ( one << wsize ) ) != 0 )
Gilles Peskine4e91d472020-06-04 20:55:15 +02002288 mpi_montmul( X, &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002289 }
2290
2291 /*
2292 * X = A^E * R * R^-1 mod N = A^E mod N
2293 */
Gilles Peskine4e91d472020-06-04 20:55:15 +02002294 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002295
Hanno Beckera4af1c42017-04-18 09:07:45 +01002296 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00002297 {
2298 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002299 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002300 }
2301
Paul Bakker5121ce52009-01-03 21:22:43 +00002302cleanup:
2303
Paul Bakker66d5d072014-06-17 16:39:18 +02002304 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002305 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00002306
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002307 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Paul Bakker6c591fa2011-05-05 11:49:20 +00002308
Paul Bakker75a28602014-03-31 12:08:17 +02002309 if( _RR == NULL || _RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002310 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002311
2312 return( ret );
2313}
2314
Paul Bakker5121ce52009-01-03 21:22:43 +00002315/*
2316 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2317 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002318int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00002319{
Janos Follath24eed8d2019-11-22 13:21:35 +00002320 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Paul Bakker23986e52011-04-24 08:57:21 +00002321 size_t lz, lzt;
Alexander Ke8ad49f2019-08-16 16:16:07 +03002322 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00002323
Hanno Becker73d7d792018-12-11 10:35:51 +00002324 MPI_VALIDATE_RET( G != NULL );
2325 MPI_VALIDATE_RET( A != NULL );
2326 MPI_VALIDATE_RET( B != NULL );
2327
Alexander Ke8ad49f2019-08-16 16:16:07 +03002328 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002329
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002330 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2331 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002332
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002333 lz = mbedtls_mpi_lsb( &TA );
2334 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002335
Paul Bakker66d5d072014-06-17 16:39:18 +02002336 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002337 lz = lzt;
2338
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002339 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
2340 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002341
Paul Bakker5121ce52009-01-03 21:22:43 +00002342 TA.s = TB.s = 1;
2343
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002344 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002345 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002346 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2347 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002348
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002349 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002350 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002351 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2352 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002353 }
2354 else
2355 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002356 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2357 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002358 }
2359 }
2360
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002361 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2362 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002363
2364cleanup:
2365
Alexander Ke8ad49f2019-08-16 16:16:07 +03002366 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002367
2368 return( ret );
2369}
2370
Paul Bakker33dc46b2014-04-30 16:11:39 +02002371/*
2372 * Fill X with size bytes of random.
2373 *
2374 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02002375 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02002376 * deterministic, eg for tests).
2377 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002378int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002379 int (*f_rng)(void *, unsigned char *, size_t),
2380 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00002381{
Janos Follath24eed8d2019-11-22 13:21:35 +00002382 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Hanno Becker6dab6202019-01-02 16:42:29 +00002383 size_t const limbs = CHARS_TO_LIMBS( size );
Hanno Beckerda1655a2017-10-18 14:21:44 +01002384 size_t const overhead = ( limbs * ciL ) - size;
2385 unsigned char *Xp;
2386
Hanno Becker8ce11a32018-12-19 16:18:52 +00002387 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002388 MPI_VALIDATE_RET( f_rng != NULL );
Paul Bakker33dc46b2014-04-30 16:11:39 +02002389
Hanno Beckerda1655a2017-10-18 14:21:44 +01002390 /* Ensure that target MPI has exactly the necessary number of limbs */
2391 if( X->n != limbs )
2392 {
2393 mbedtls_mpi_free( X );
2394 mbedtls_mpi_init( X );
2395 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
2396 }
2397 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker287781a2011-03-26 13:18:49 +00002398
Hanno Beckerda1655a2017-10-18 14:21:44 +01002399 Xp = (unsigned char*) X->p;
2400 f_rng( p_rng, Xp + overhead, size );
2401
Hanno Becker2be8a552018-10-25 12:40:09 +01002402 mpi_bigendian_to_host( X->p, limbs );
Paul Bakker287781a2011-03-26 13:18:49 +00002403
2404cleanup:
2405 return( ret );
2406}
2407
Paul Bakker5121ce52009-01-03 21:22:43 +00002408/*
2409 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2410 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002411int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00002412{
Janos Follath24eed8d2019-11-22 13:21:35 +00002413 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002414 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Hanno Becker73d7d792018-12-11 10:35:51 +00002415 MPI_VALIDATE_RET( X != NULL );
2416 MPI_VALIDATE_RET( A != NULL );
2417 MPI_VALIDATE_RET( N != NULL );
Paul Bakker5121ce52009-01-03 21:22:43 +00002418
Hanno Becker4bcb4912017-04-18 15:49:39 +01002419 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002420 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002421
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002422 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2423 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2424 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002425
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002426 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002427
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002428 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002429 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002430 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002431 goto cleanup;
2432 }
2433
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002434 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2435 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2436 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2437 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002438
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002439 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2440 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2441 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2442 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002443
2444 do
2445 {
2446 while( ( TU.p[0] & 1 ) == 0 )
2447 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002448 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002449
2450 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2451 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002452 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2453 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002454 }
2455
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002456 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2457 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002458 }
2459
2460 while( ( TV.p[0] & 1 ) == 0 )
2461 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002462 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002463
2464 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2465 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002466 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2467 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002468 }
2469
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002470 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2471 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002472 }
2473
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002474 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002475 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002476 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2477 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2478 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002479 }
2480 else
2481 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002482 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2483 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2484 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002485 }
2486 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002487 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002488
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002489 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2490 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002491
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002492 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2493 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002494
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002495 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002496
2497cleanup:
2498
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002499 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2500 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2501 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002502
2503 return( ret );
2504}
2505
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002506#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00002507
Paul Bakker5121ce52009-01-03 21:22:43 +00002508static const int small_prime[] =
2509{
2510 3, 5, 7, 11, 13, 17, 19, 23,
2511 29, 31, 37, 41, 43, 47, 53, 59,
2512 61, 67, 71, 73, 79, 83, 89, 97,
2513 101, 103, 107, 109, 113, 127, 131, 137,
2514 139, 149, 151, 157, 163, 167, 173, 179,
2515 181, 191, 193, 197, 199, 211, 223, 227,
2516 229, 233, 239, 241, 251, 257, 263, 269,
2517 271, 277, 281, 283, 293, 307, 311, 313,
2518 317, 331, 337, 347, 349, 353, 359, 367,
2519 373, 379, 383, 389, 397, 401, 409, 419,
2520 421, 431, 433, 439, 443, 449, 457, 461,
2521 463, 467, 479, 487, 491, 499, 503, 509,
2522 521, 523, 541, 547, 557, 563, 569, 571,
2523 577, 587, 593, 599, 601, 607, 613, 617,
2524 619, 631, 641, 643, 647, 653, 659, 661,
2525 673, 677, 683, 691, 701, 709, 719, 727,
2526 733, 739, 743, 751, 757, 761, 769, 773,
2527 787, 797, 809, 811, 821, 823, 827, 829,
2528 839, 853, 857, 859, 863, 877, 881, 883,
2529 887, 907, 911, 919, 929, 937, 941, 947,
2530 953, 967, 971, 977, 983, 991, 997, -103
2531};
2532
2533/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002534 * Small divisors test (X must be positive)
2535 *
2536 * Return values:
2537 * 0: no small factor (possible prime, more tests needed)
2538 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002539 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002540 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002541 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002542static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002543{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002544 int ret = 0;
2545 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002546 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002547
Paul Bakker5121ce52009-01-03 21:22:43 +00002548 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002549 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002550
2551 for( i = 0; small_prime[i] > 0; i++ )
2552 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002553 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002554 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002555
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002556 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002557
2558 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002559 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002560 }
2561
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002562cleanup:
2563 return( ret );
2564}
2565
2566/*
2567 * Miller-Rabin pseudo-primality test (HAC 4.24)
2568 */
Janos Follathda31fa12018-09-03 14:45:23 +01002569static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002570 int (*f_rng)(void *, unsigned char *, size_t),
2571 void *p_rng )
2572{
Pascal Junodb99183d2015-03-11 16:49:45 +01002573 int ret, count;
Janos Follathda31fa12018-09-03 14:45:23 +01002574 size_t i, j, k, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002575 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002576
Hanno Becker8ce11a32018-12-19 16:18:52 +00002577 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002578 MPI_VALIDATE_RET( f_rng != NULL );
2579
2580 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2581 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002582 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002583
Paul Bakker5121ce52009-01-03 21:22:43 +00002584 /*
2585 * W = |X| - 1
2586 * R = W >> lsb( W )
2587 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002588 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2589 s = mbedtls_mpi_lsb( &W );
2590 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2591 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002592
Janos Follathda31fa12018-09-03 14:45:23 +01002593 for( i = 0; i < rounds; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002594 {
2595 /*
2596 * pick a random A, 1 < A < |X| - 1
2597 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002598 count = 0;
2599 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002600 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002601
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002602 j = mbedtls_mpi_bitlen( &A );
2603 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002604 if (j > k) {
Darryl Greene3f95ed2018-10-02 13:21:35 +01002605 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Pascal Junodb99183d2015-03-11 16:49:45 +01002606 }
2607
2608 if (count++ > 30) {
Jens Wiklanderf08aa3e2019-01-17 13:30:57 +01002609 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2610 goto cleanup;
Pascal Junodb99183d2015-03-11 16:49:45 +01002611 }
2612
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002613 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2614 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002615
2616 /*
2617 * A = A^R mod |X|
2618 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002619 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002620
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002621 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2622 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002623 continue;
2624
2625 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002626 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002627 {
2628 /*
2629 * A = A * A mod |X|
2630 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002631 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2632 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002633
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002634 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002635 break;
2636
2637 j++;
2638 }
2639
2640 /*
2641 * not prime if A != |X| - 1 or A == 1
2642 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002643 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2644 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002645 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002646 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002647 break;
2648 }
2649 }
2650
2651cleanup:
Hanno Becker73d7d792018-12-11 10:35:51 +00002652 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2653 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002654 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002655
2656 return( ret );
2657}
2658
2659/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002660 * Pseudo-primality test: small factors, then Miller-Rabin
2661 */
Janos Follatha0b67c22018-09-18 14:48:23 +01002662int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2663 int (*f_rng)(void *, unsigned char *, size_t),
2664 void *p_rng )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002665{
Janos Follath24eed8d2019-11-22 13:21:35 +00002666 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002667 mbedtls_mpi XX;
Hanno Becker8ce11a32018-12-19 16:18:52 +00002668 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002669 MPI_VALIDATE_RET( f_rng != NULL );
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002670
2671 XX.s = 1;
2672 XX.n = X->n;
2673 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002674
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002675 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2676 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2677 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002678
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002679 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002680 return( 0 );
2681
2682 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2683 {
2684 if( ret == 1 )
2685 return( 0 );
2686
2687 return( ret );
2688 }
2689
Janos Follathda31fa12018-09-03 14:45:23 +01002690 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
Janos Follathf301d232018-08-14 13:34:01 +01002691}
2692
Janos Follatha0b67c22018-09-18 14:48:23 +01002693#if !defined(MBEDTLS_DEPRECATED_REMOVED)
Janos Follathf301d232018-08-14 13:34:01 +01002694/*
2695 * Pseudo-primality test, error probability 2^-80
2696 */
2697int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2698 int (*f_rng)(void *, unsigned char *, size_t),
2699 void *p_rng )
2700{
Hanno Becker8ce11a32018-12-19 16:18:52 +00002701 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002702 MPI_VALIDATE_RET( f_rng != NULL );
2703
Janos Follatha0b67c22018-09-18 14:48:23 +01002704 /*
2705 * In the past our key generation aimed for an error rate of at most
2706 * 2^-80. Since this function is deprecated, aim for the same certainty
2707 * here as well.
2708 */
Hanno Becker73d7d792018-12-11 10:35:51 +00002709 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002710}
Janos Follatha0b67c22018-09-18 14:48:23 +01002711#endif
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002712
2713/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002714 * Prime number generation
Jethro Beekman66689272018-02-14 19:24:10 -08002715 *
Janos Follathf301d232018-08-14 13:34:01 +01002716 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2717 * be either 1024 bits or 1536 bits long, and flags must contain
2718 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Paul Bakker5121ce52009-01-03 21:22:43 +00002719 */
Janos Follath7c025a92018-08-14 11:08:41 +01002720int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002721 int (*f_rng)(void *, unsigned char *, size_t),
2722 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002723{
Jethro Beekman66689272018-02-14 19:24:10 -08002724#ifdef MBEDTLS_HAVE_INT64
2725// ceil(2^63.5)
2726#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2727#else
2728// ceil(2^31.5)
2729#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2730#endif
2731 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker23986e52011-04-24 08:57:21 +00002732 size_t k, n;
Janos Follathda31fa12018-09-03 14:45:23 +01002733 int rounds;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002734 mbedtls_mpi_uint r;
2735 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002736
Hanno Becker8ce11a32018-12-19 16:18:52 +00002737 MPI_VALIDATE_RET( X != NULL );
Hanno Becker73d7d792018-12-11 10:35:51 +00002738 MPI_VALIDATE_RET( f_rng != NULL );
2739
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002740 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2741 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002742
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002743 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002744
2745 n = BITS_TO_LIMBS( nbits );
2746
Janos Follathda31fa12018-09-03 14:45:23 +01002747 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2748 {
2749 /*
2750 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2751 */
2752 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2753 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2754 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2755 }
2756 else
2757 {
2758 /*
2759 * 2^-100 error probability, number of rounds computed based on HAC,
2760 * fact 4.48
2761 */
2762 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2763 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2764 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2765 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2766 }
2767
Jethro Beekman66689272018-02-14 19:24:10 -08002768 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002769 {
Jethro Beekman66689272018-02-14 19:24:10 -08002770 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2771 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2772 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2773
2774 k = n * biL;
2775 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2776 X->p[0] |= 1;
2777
Janos Follath7c025a92018-08-14 11:08:41 +01002778 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002779 {
Janos Follatha0b67c22018-09-18 14:48:23 +01002780 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
Jethro Beekman66689272018-02-14 19:24:10 -08002781
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002782 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002783 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002784 }
Jethro Beekman66689272018-02-14 19:24:10 -08002785 else
Paul Bakker5121ce52009-01-03 21:22:43 +00002786 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002787 /*
Jethro Beekman66689272018-02-14 19:24:10 -08002788 * An necessary condition for Y and X = 2Y + 1 to be prime
2789 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2790 * Make sure it is satisfied, while keeping X = 3 mod 4
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002791 */
Jethro Beekman66689272018-02-14 19:24:10 -08002792
2793 X->p[0] |= 2;
2794
2795 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2796 if( r == 0 )
2797 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2798 else if( r == 1 )
2799 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2800
2801 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2802 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2803 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2804
2805 while( 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002806 {
Jethro Beekman66689272018-02-14 19:24:10 -08002807 /*
2808 * First, check small factors for X and Y
2809 * before doing Miller-Rabin on any of them
2810 */
2811 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2812 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002813 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002814 == 0 &&
Janos Follathda31fa12018-09-03 14:45:23 +01002815 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
Janos Follathf301d232018-08-14 13:34:01 +01002816 == 0 )
Jethro Beekman66689272018-02-14 19:24:10 -08002817 goto cleanup;
2818
2819 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2820 goto cleanup;
2821
2822 /*
2823 * Next candidates. We want to preserve Y = (X-1) / 2 and
2824 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2825 * so up Y by 6 and X by 12.
2826 */
2827 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2828 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002829 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002830 }
2831 }
2832
2833cleanup:
2834
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002835 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002836
2837 return( ret );
2838}
2839
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002840#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002841
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002842#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002843
Paul Bakker23986e52011-04-24 08:57:21 +00002844#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002845
2846static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2847{
2848 { 693, 609, 21 },
2849 { 1764, 868, 28 },
2850 { 768454923, 542167814, 1 }
2851};
2852
Paul Bakker5121ce52009-01-03 21:22:43 +00002853/*
2854 * Checkup routine
2855 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002856int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002857{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002858 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002859 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002860
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002861 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2862 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002863
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002864 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002865 "EFE021C2645FD1DC586E69184AF4A31E" \
2866 "D5F53E93B5F123FA41680867BA110131" \
2867 "944FE7952E2517337780CB0DB80E61AA" \
2868 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2869
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002870 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002871 "B2E7EFD37075B9F03FF989C7C5051C20" \
2872 "34D2A323810251127E7BF8625A4F49A5" \
2873 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2874 "5B5C25763222FEFCCFC38B832366C29E" ) );
2875
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002876 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002877 "0066A198186C18C10B2F5ED9B522752A" \
2878 "9830B69916E535C8F047518A889A43A5" \
2879 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2880
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002881 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002882
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002883 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002884 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2885 "9E857EA95A03512E2BAE7391688D264A" \
2886 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2887 "8001B72E848A38CAE1C65F78E56ABDEF" \
2888 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2889 "ECF677152EF804370C1A305CAF3B5BF1" \
2890 "30879B56C61DE584A0F53A2447A51E" ) );
2891
2892 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002893 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002894
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002895 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002896 {
2897 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002898 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002899
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002900 ret = 1;
2901 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002902 }
2903
2904 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002905 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002906
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002907 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002908
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002909 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002910 "256567336059E52CAE22925474705F39A94" ) );
2911
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002912 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002913 "6613F26162223DF488E9CD48CC132C7A" \
2914 "0AC93C701B001B092E4E5B9F73BCD27B" \
2915 "9EE50D0657C77F374E903CDFA4C642" ) );
2916
2917 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002918 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002919
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002920 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2921 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002922 {
2923 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002924 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002925
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002926 ret = 1;
2927 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002928 }
2929
2930 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002931 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002932
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002933 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002934
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002935 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002936 "36E139AEA55215609D2816998ED020BB" \
2937 "BD96C37890F65171D948E9BC7CBAA4D9" \
2938 "325D24D6A3C12710F10A09FA08AB87" ) );
2939
2940 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002941 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002942
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002943 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002944 {
2945 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002946 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002947
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002948 ret = 1;
2949 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002950 }
2951
2952 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002953 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002954
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002955 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002956
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002957 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002958 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2959 "C3DBA76456363A10869622EAC2DD84EC" \
2960 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2961
2962 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002963 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002964
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002965 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002966 {
2967 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002968 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002969
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002970 ret = 1;
2971 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002972 }
2973
2974 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002975 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002976
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002977 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002978 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002979
Paul Bakker66d5d072014-06-17 16:39:18 +02002980 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002981 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002982 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2983 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002984
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002985 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002986
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002987 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002988 {
2989 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002990 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002991
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002992 ret = 1;
2993 goto cleanup;
2994 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002995 }
2996
2997 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002998 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002999
Paul Bakker5121ce52009-01-03 21:22:43 +00003000cleanup:
3001
3002 if( ret != 0 && verbose != 0 )
Kenneth Soerensen518d4352020-04-01 17:22:45 +02003003 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00003004
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003005 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
3006 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00003007
3008 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003009 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00003010
3011 return( ret );
3012}
3013
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003014#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00003015
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02003016#endif /* MBEDTLS_BIGNUM_C */