blob: 84a43c8cba8301f07cc21a5368a84422069d8860 [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
Bence Szépkúti4e9f7122020-06-05 13:02:18 +02005 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
6 *
7 * This file is provided under the Apache License 2.0, or the
8 * GNU General Public License v2.0 or later.
9 *
10 * **********
11 * Apache License 2.0:
Manuel Pégourié-Gonnard37ff1402015-09-04 14:21:07 +020012 *
13 * Licensed under the Apache License, Version 2.0 (the "License"); you may
14 * not use this file except in compliance with the License.
15 * You may obtain a copy of the License at
16 *
17 * http://www.apache.org/licenses/LICENSE-2.0
18 *
19 * Unless required by applicable law or agreed to in writing, software
20 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
21 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
22 * See the License for the specific language governing permissions and
23 * limitations under the License.
Paul Bakkerb96f1542010-07-18 20:36:00 +000024 *
Bence Szépkúti4e9f7122020-06-05 13:02:18 +020025 * **********
26 *
27 * **********
28 * GNU General Public License v2.0 or later:
29 *
30 * This program is free software; you can redistribute it and/or modify
31 * it under the terms of the GNU General Public License as published by
32 * the Free Software Foundation; either version 2 of the License, or
33 * (at your option) any later version.
34 *
35 * This program is distributed in the hope that it will be useful,
36 * but WITHOUT ANY WARRANTY; without even the implied warranty of
37 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
38 * GNU General Public License for more details.
39 *
40 * You should have received a copy of the GNU General Public License along
41 * with this program; if not, write to the Free Software Foundation, Inc.,
42 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
43 *
44 * **********
45 *
Manuel Pégourié-Gonnardfe446432015-03-06 13:17:10 +000046 * This file is part of mbed TLS (https://tls.mbed.org)
Paul Bakker5121ce52009-01-03 21:22:43 +000047 */
Simon Butcher15b15d12015-11-26 19:35:03 +000048
Paul Bakker5121ce52009-01-03 21:22:43 +000049/*
Simon Butcher15b15d12015-11-26 19:35:03 +000050 * The following sources were referenced in the design of this Multi-precision
51 * Integer library:
Paul Bakker5121ce52009-01-03 21:22:43 +000052 *
Simon Butcher15b15d12015-11-26 19:35:03 +000053 * [1] Handbook of Applied Cryptography - 1997
54 * Menezes, van Oorschot and Vanstone
55 *
56 * [2] Multi-Precision Math
57 * Tom St Denis
58 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
59 *
60 * [3] GNU Multi-Precision Arithmetic Library
61 * https://gmplib.org/manual/index.html
62 *
Simon Butcherf5ba0452015-12-27 23:01:55 +000063 */
Paul Bakker5121ce52009-01-03 21:22:43 +000064
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020065#if !defined(MBEDTLS_CONFIG_FILE)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000066#include "mbedtls/config.h"
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020067#else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020068#include MBEDTLS_CONFIG_FILE
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020069#endif
Paul Bakker5121ce52009-01-03 21:22:43 +000070
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020071#if defined(MBEDTLS_BIGNUM_C)
Paul Bakker5121ce52009-01-03 21:22:43 +000072
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000073#include "mbedtls/bignum.h"
74#include "mbedtls/bn_mul.h"
Paul Bakker5121ce52009-01-03 21:22:43 +000075
Rich Evans00ab4702015-02-06 13:43:58 +000076#include <string.h>
77
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020078#if defined(MBEDTLS_PLATFORM_C)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000079#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020080#else
Rich Evans00ab4702015-02-06 13:43:58 +000081#include <stdio.h>
82#include <stdlib.h>
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020083#define mbedtls_printf printf
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +020084#define mbedtls_calloc calloc
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020085#define mbedtls_free free
Paul Bakker6e339b52013-07-03 13:37:05 +020086#endif
87
Paul Bakker34617722014-06-13 17:20:13 +020088/* Implementation that should never be optimized out by the compiler */
Alexey Skalozube17a8da2016-01-13 17:19:33 +020089static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n ) {
Alexey Skalozub3d53f412016-01-13 16:53:40 +020090 volatile mbedtls_mpi_uint *p = v; while( n-- ) *p++ = 0;
Paul Bakker34617722014-06-13 17:20:13 +020091}
92
Hanno Becker88807112017-10-18 12:41:30 +010093/* Implementation that should never be optimized out by the compiler */
94static void mbedtls_zeroize( void *v, size_t n ) {
95 volatile unsigned char *p = v; while( n-- ) *p++ = 0;
96}
97
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020098#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
Paul Bakker5121ce52009-01-03 21:22:43 +000099#define biL (ciL << 3) /* bits in limb */
100#define biH (ciL << 2) /* half limb size */
101
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100102#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
103
Paul Bakker5121ce52009-01-03 21:22:43 +0000104/*
105 * Convert between bits/chars and number of limbs
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200106 * Divide first in order to avoid potential overflows
Paul Bakker5121ce52009-01-03 21:22:43 +0000107 */
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200108#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
109#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
Paul Bakker5121ce52009-01-03 21:22:43 +0000110
111/*
Paul Bakker6c591fa2011-05-05 11:49:20 +0000112 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +0000113 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200114void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000115{
Paul Bakker6c591fa2011-05-05 11:49:20 +0000116 if( X == NULL )
117 return;
Paul Bakker5121ce52009-01-03 21:22:43 +0000118
Paul Bakker6c591fa2011-05-05 11:49:20 +0000119 X->s = 1;
120 X->n = 0;
121 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000122}
123
124/*
Paul Bakker6c591fa2011-05-05 11:49:20 +0000125 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +0000126 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200127void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000128{
Paul Bakker6c591fa2011-05-05 11:49:20 +0000129 if( X == NULL )
130 return;
Paul Bakker5121ce52009-01-03 21:22:43 +0000131
Paul Bakker6c591fa2011-05-05 11:49:20 +0000132 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +0000133 {
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200134 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200135 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000136 }
137
Paul Bakker6c591fa2011-05-05 11:49:20 +0000138 X->s = 1;
139 X->n = 0;
140 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000141}
142
143/*
144 * Enlarge to the specified number of limbs
145 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200146int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000147{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200148 mbedtls_mpi_uint *p;
Paul Bakker5121ce52009-01-03 21:22:43 +0000149
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200150 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200151 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000152
Paul Bakker5121ce52009-01-03 21:22:43 +0000153 if( X->n < nblimbs )
154 {
Simon Butcher29176892016-05-20 00:19:09 +0100155 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200156 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000157
Paul Bakker5121ce52009-01-03 21:22:43 +0000158 if( X->p != NULL )
159 {
160 memcpy( p, X->p, X->n * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200161 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200162 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000163 }
164
165 X->n = nblimbs;
166 X->p = p;
167 }
168
169 return( 0 );
170}
171
172/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100173 * Resize down as much as possible,
174 * while keeping at least the specified number of limbs
175 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200176int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100177{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200178 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100179 size_t i;
180
Gilles Peskine6a269672020-01-20 21:17:43 +0100181 /* Actually resize up if there are currently fewer than nblimbs limbs. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100182 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200183 return( mbedtls_mpi_grow( X, nblimbs ) );
Gilles Peskine774c1632020-01-21 13:59:51 +0100184 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100185
186 for( i = X->n - 1; i > 0; i-- )
187 if( X->p[i] != 0 )
188 break;
189 i++;
190
191 if( i < nblimbs )
192 i = nblimbs;
193
Simon Butcher29176892016-05-20 00:19:09 +0100194 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200195 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100196
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100197 if( X->p != NULL )
198 {
199 memcpy( p, X->p, i * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200200 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200201 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100202 }
203
204 X->n = i;
205 X->p = p;
206
207 return( 0 );
208}
209
210/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000211 * Copy the contents of Y into X
212 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200213int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000214{
Paul Bakker23986e52011-04-24 08:57:21 +0000215 int ret;
216 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000217
218 if( X == Y )
219 return( 0 );
220
Gilles Peskine2aeab872020-01-20 21:12:50 +0100221 if( Y->n == 0 )
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200222 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200223 mbedtls_mpi_free( X );
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200224 return( 0 );
225 }
226
Paul Bakker5121ce52009-01-03 21:22:43 +0000227 for( i = Y->n - 1; i > 0; i-- )
228 if( Y->p[i] != 0 )
229 break;
230 i++;
231
232 X->s = Y->s;
233
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200234 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000235
236 memset( X->p, 0, X->n * ciL );
237 memcpy( X->p, Y->p, i * ciL );
238
239cleanup:
240
241 return( ret );
242}
243
244/*
245 * Swap the contents of X and Y
246 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200247void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000248{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200249 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000250
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200251 memcpy( &T, X, sizeof( mbedtls_mpi ) );
252 memcpy( X, Y, sizeof( mbedtls_mpi ) );
253 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000254}
255
256/*
Gilles Peskine3c44c652020-06-04 19:14:58 +0200257 * Conditionally assign dest = src, without leaking information
258 * about whether the assignment was made or not.
259 * dest and src must be arrays of limbs of size n.
260 * assign must be 0 or 1.
261 */
262static void mpi_safe_cond_assign( size_t n,
263 mbedtls_mpi_uint *dest,
264 const mbedtls_mpi_uint *src,
265 unsigned char assign )
266{
267 size_t i;
268 for( i = 0; i < n; i++ )
269 dest[i] = dest[i] * ( 1 - assign ) + src[i] * assign;
270}
271
272/*
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100273 * Conditionally assign X = Y, without leaking information
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100274 * about whether the assignment was made or not.
275 * (Leaking information about the respective sizes of X and Y is ok however.)
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100276 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200277int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100278{
279 int ret = 0;
280 size_t i;
281
Pascal Junodb99183d2015-03-11 16:49:45 +0100282 /* make sure assign is 0 or 1 in a time-constant manner */
283 assign = (assign | (unsigned char)-assign) >> 7;
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100284
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200285 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100286
Paul Bakker66d5d072014-06-17 16:39:18 +0200287 X->s = X->s * ( 1 - assign ) + Y->s * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100288
Gilles Peskine3c44c652020-06-04 19:14:58 +0200289 mpi_safe_cond_assign( Y->n, X->p, Y->p, assign );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100290
Gilles Peskine3c44c652020-06-04 19:14:58 +0200291 for( i = Y->n; i < X->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200292 X->p[i] *= ( 1 - assign );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100293
294cleanup:
295 return( ret );
296}
297
298/*
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100299 * Conditionally swap X and Y, without leaking information
300 * about whether the swap was made or not.
301 * Here it is not ok to simply swap the pointers, which whould lead to
302 * different memory access patterns when X and Y are used afterwards.
303 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200304int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100305{
306 int ret, s;
307 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200308 mbedtls_mpi_uint tmp;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100309
310 if( X == Y )
311 return( 0 );
312
Pascal Junodb99183d2015-03-11 16:49:45 +0100313 /* make sure swap is 0 or 1 in a time-constant manner */
314 swap = (swap | (unsigned char)-swap) >> 7;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100315
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200316 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
317 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100318
319 s = X->s;
Paul Bakker66d5d072014-06-17 16:39:18 +0200320 X->s = X->s * ( 1 - swap ) + Y->s * swap;
321 Y->s = Y->s * ( 1 - swap ) + s * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100322
323
324 for( i = 0; i < X->n; i++ )
325 {
326 tmp = X->p[i];
Paul Bakker66d5d072014-06-17 16:39:18 +0200327 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
328 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100329 }
330
331cleanup:
332 return( ret );
333}
334
335/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000336 * Set value from integer
337 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200338int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000339{
340 int ret;
341
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200342 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000343 memset( X->p, 0, X->n * ciL );
344
345 X->p[0] = ( z < 0 ) ? -z : z;
346 X->s = ( z < 0 ) ? -1 : 1;
347
348cleanup:
349
350 return( ret );
351}
352
353/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000354 * Get a specific bit
355 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200356int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000357{
358 if( X->n * biL <= pos )
359 return( 0 );
360
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200361 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000362}
363
Gilles Peskine220cc172018-11-20 16:47:47 +0100364/* Get a specific byte, without range checks. */
365#define GET_BYTE( X, i ) \
366 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
367
Paul Bakker2f5947e2011-05-18 15:47:11 +0000368/*
369 * Set a bit to a specific value of 0 or 1
370 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200371int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000372{
373 int ret = 0;
374 size_t off = pos / biL;
375 size_t idx = pos % biL;
376
377 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200378 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200379
Paul Bakker2f5947e2011-05-18 15:47:11 +0000380 if( X->n * biL <= pos )
381 {
382 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200383 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000384
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200385 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000386 }
387
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200388 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
389 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000390
391cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200392
Paul Bakker2f5947e2011-05-18 15:47:11 +0000393 return( ret );
394}
395
396/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200397 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000398 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200399size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000400{
Paul Bakker23986e52011-04-24 08:57:21 +0000401 size_t i, j, count = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000402
403 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000404 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000405 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
406 return( count );
407
408 return( 0 );
409}
410
411/*
Simon Butcher15b15d12015-11-26 19:35:03 +0000412 * Count leading zero bits in a given integer
413 */
414static size_t mbedtls_clz( const mbedtls_mpi_uint x )
415{
416 size_t j;
Manuel Pégourié-Gonnarde3e8edf2015-12-01 09:31:52 +0100417 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
Simon Butcher15b15d12015-11-26 19:35:03 +0000418
419 for( j = 0; j < biL; j++ )
420 {
421 if( x & mask ) break;
422
423 mask >>= 1;
424 }
425
426 return j;
427}
428
429/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200430 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000431 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200432size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000433{
Paul Bakker23986e52011-04-24 08:57:21 +0000434 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000435
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200436 if( X->n == 0 )
437 return( 0 );
438
Paul Bakker5121ce52009-01-03 21:22:43 +0000439 for( i = X->n - 1; i > 0; i-- )
440 if( X->p[i] != 0 )
441 break;
442
Simon Butcher15b15d12015-11-26 19:35:03 +0000443 j = biL - mbedtls_clz( X->p[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +0000444
Paul Bakker23986e52011-04-24 08:57:21 +0000445 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000446}
447
448/*
449 * Return the total size in bytes
450 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200451size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000452{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200453 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000454}
455
456/*
457 * Convert an ASCII character to digit value
458 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200459static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000460{
461 *d = 255;
462
463 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
464 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
465 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
466
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200467 if( *d >= (mbedtls_mpi_uint) radix )
468 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000469
470 return( 0 );
471}
472
473/*
474 * Import from an ASCII string
475 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200476int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000477{
Paul Bakker23986e52011-04-24 08:57:21 +0000478 int ret;
479 size_t i, j, slen, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200480 mbedtls_mpi_uint d;
481 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000482
483 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200484 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000485
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200486 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000487
Paul Bakkerff60ee62010-03-16 21:09:09 +0000488 slen = strlen( s );
489
Paul Bakker5121ce52009-01-03 21:22:43 +0000490 if( radix == 16 )
491 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100492 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200493 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
494
Paul Bakkerff60ee62010-03-16 21:09:09 +0000495 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000496
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200497 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
498 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000499
Paul Bakker23986e52011-04-24 08:57:21 +0000500 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000501 {
Paul Bakker23986e52011-04-24 08:57:21 +0000502 if( i == 1 && s[i - 1] == '-' )
Paul Bakker5121ce52009-01-03 21:22:43 +0000503 {
504 X->s = -1;
505 break;
506 }
507
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200508 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200509 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000510 }
511 }
512 else
513 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200514 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000515
Paul Bakkerff60ee62010-03-16 21:09:09 +0000516 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000517 {
518 if( i == 0 && s[i] == '-' )
519 {
520 X->s = -1;
521 continue;
522 }
523
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200524 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
525 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000526
527 if( X->s == 1 )
528 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200529 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000530 }
531 else
532 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200533 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000534 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000535 }
536 }
537
538cleanup:
539
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200540 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000541
542 return( ret );
543}
544
545/*
Ron Eldore6cbfc32018-11-20 14:07:01 +0200546 * Helper to write the digits high-order first.
Paul Bakker5121ce52009-01-03 21:22:43 +0000547 */
Ron Eldore6cbfc32018-11-20 14:07:01 +0200548static int mpi_write_hlp( mbedtls_mpi *X, int radix,
549 char **p, const size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000550{
551 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200552 mbedtls_mpi_uint r;
Ron Eldore6cbfc32018-11-20 14:07:01 +0200553 size_t length = 0;
554 char *p_end = *p + buflen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000555
Ron Eldore6cbfc32018-11-20 14:07:01 +0200556 do
557 {
558 if( length >= buflen )
559 {
560 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
561 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000562
Ron Eldore6cbfc32018-11-20 14:07:01 +0200563 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
564 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
565 /*
566 * Write the residue in the current position, as an ASCII character.
567 */
568 if( r < 0xA )
569 *(--p_end) = (char)( '0' + r );
570 else
571 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000572
Ron Eldore6cbfc32018-11-20 14:07:01 +0200573 length++;
574 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000575
Ron Eldore6cbfc32018-11-20 14:07:01 +0200576 memmove( *p, p_end, length );
577 *p += length;
Paul Bakker5121ce52009-01-03 21:22:43 +0000578
579cleanup:
580
581 return( ret );
582}
583
584/*
585 * Export into an ASCII string
586 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100587int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
588 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000589{
Paul Bakker23986e52011-04-24 08:57:21 +0000590 int ret = 0;
591 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000592 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200593 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000594
595 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200596 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000597
Hanno Beckera277d4c2019-02-04 09:45:07 +0000598 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
599 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
600 * `n`. If radix > 4, this might be a strict
601 * overapproximation of the number of
602 * radix-adic digits needed to present `n`. */
603 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
604 * present `n`. */
605
Janos Follath216e7382019-03-06 13:43:02 +0000606 n += 1; /* Terminating null byte */
Hanno Beckera277d4c2019-02-04 09:45:07 +0000607 n += 1; /* Compensate for the divisions above, which round down `n`
608 * in case it's not even. */
609 n += 1; /* Potential '-'-sign. */
610 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
611 * which always uses an even number of hex-digits. */
Paul Bakker5121ce52009-01-03 21:22:43 +0000612
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100613 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000614 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100615 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200616 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000617 }
618
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100619 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200620 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000621
622 if( X->s == -1 )
Hanno Beckereff335d2019-02-01 16:41:30 +0000623 {
Paul Bakker5121ce52009-01-03 21:22:43 +0000624 *p++ = '-';
Hanno Beckereff335d2019-02-01 16:41:30 +0000625 buflen--;
626 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000627
628 if( radix == 16 )
629 {
Paul Bakker23986e52011-04-24 08:57:21 +0000630 int c;
631 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000632
Paul Bakker23986e52011-04-24 08:57:21 +0000633 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000634 {
Paul Bakker23986e52011-04-24 08:57:21 +0000635 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000636 {
Paul Bakker23986e52011-04-24 08:57:21 +0000637 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000638
Paul Bakker6c343d72014-07-10 14:36:19 +0200639 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000640 continue;
641
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000642 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000643 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000644 k = 1;
645 }
646 }
647 }
648 else
649 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200650 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000651
652 if( T.s == -1 )
653 T.s = 1;
654
Ron Eldore6cbfc32018-11-20 14:07:01 +0200655 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000656 }
657
658 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100659 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000660
661cleanup:
662
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200663 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000664
665 return( ret );
666}
667
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200668#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000669/*
670 * Read X from an opened file
671 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200672int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000673{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200674 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000675 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000676 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000677 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000678 * Buffer should have space for (short) label and decimal formatted MPI,
679 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000680 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200681 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000682
683 memset( s, 0, sizeof( s ) );
684 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200685 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000686
687 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000688 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200689 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000690
Hanno Beckerb2034b72017-04-26 11:46:46 +0100691 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
692 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000693
694 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100695 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000696 if( mpi_get_digit( &d, radix, *p ) != 0 )
697 break;
698
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200699 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000700}
701
702/*
703 * Write X into an opened file (or stdout if fout == NULL)
704 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200705int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000706{
Paul Bakker23986e52011-04-24 08:57:21 +0000707 int ret;
708 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000709 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000710 * Buffer should have space for (short) label and decimal formatted MPI,
711 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000712 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200713 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000714
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100715 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000716
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100717 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000718
719 if( p == NULL ) p = "";
720
721 plen = strlen( p );
722 slen = strlen( s );
723 s[slen++] = '\r';
724 s[slen++] = '\n';
725
726 if( fout != NULL )
727 {
728 if( fwrite( p, 1, plen, fout ) != plen ||
729 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200730 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000731 }
732 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200733 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000734
735cleanup:
736
737 return( ret );
738}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200739#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000740
741/*
742 * Import X from unsigned binary data, big endian
743 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200744int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000745{
Paul Bakker23986e52011-04-24 08:57:21 +0000746 int ret;
Hanno Becker073c1992017-10-17 15:17:27 +0100747 size_t i, j;
748 size_t const limbs = CHARS_TO_LIMBS( buflen );
Paul Bakker5121ce52009-01-03 21:22:43 +0000749
Hanno Becker073c1992017-10-17 15:17:27 +0100750 /* Ensure that target MPI has exactly the necessary number of limbs */
751 if( X->n != limbs )
752 {
753 mbedtls_mpi_free( X );
754 mbedtls_mpi_init( X );
755 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
756 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000757
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200758 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000759
Hanno Becker073c1992017-10-17 15:17:27 +0100760 for( i = buflen, j = 0; i > 0; i--, j++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200761 X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
Paul Bakker5121ce52009-01-03 21:22:43 +0000762
763cleanup:
764
765 return( ret );
766}
767
768/*
769 * Export X into unsigned binary data, big endian
770 */
Gilles Peskine220cc172018-11-20 16:47:47 +0100771int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
772 unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000773{
Gilles Peskine220cc172018-11-20 16:47:47 +0100774 size_t stored_bytes = X->n * ciL;
775 size_t bytes_to_copy;
776 unsigned char *p;
777 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000778
Gilles Peskine220cc172018-11-20 16:47:47 +0100779 if( stored_bytes < buflen )
780 {
781 /* There is enough space in the output buffer. Write initial
782 * null bytes and record the position at which to start
783 * writing the significant bytes. In this case, the execution
784 * trace of this function does not depend on the value of the
785 * number. */
786 bytes_to_copy = stored_bytes;
787 p = buf + buflen - stored_bytes;
788 memset( buf, 0, buflen - stored_bytes );
789 }
790 else
791 {
792 /* The output buffer is smaller than the allocated size of X.
793 * However X may fit if its leading bytes are zero. */
794 bytes_to_copy = buflen;
795 p = buf;
796 for( i = bytes_to_copy; i < stored_bytes; i++ )
797 {
798 if( GET_BYTE( X, i ) != 0 )
799 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
800 }
801 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000802
Gilles Peskine220cc172018-11-20 16:47:47 +0100803 for( i = 0; i < bytes_to_copy; i++ )
804 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
Paul Bakker5121ce52009-01-03 21:22:43 +0000805
806 return( 0 );
807}
808
809/*
810 * Left-shift: X <<= count
811 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200812int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000813{
Paul Bakker23986e52011-04-24 08:57:21 +0000814 int ret;
815 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200816 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000817
818 v0 = count / (biL );
819 t1 = count & (biL - 1);
820
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200821 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000822
Paul Bakkerf9688572011-05-05 10:00:45 +0000823 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200824 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000825
826 ret = 0;
827
828 /*
829 * shift by count / limb_size
830 */
831 if( v0 > 0 )
832 {
Paul Bakker23986e52011-04-24 08:57:21 +0000833 for( i = X->n; i > v0; i-- )
834 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000835
Paul Bakker23986e52011-04-24 08:57:21 +0000836 for( ; i > 0; i-- )
837 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000838 }
839
840 /*
841 * shift by count % limb_size
842 */
843 if( t1 > 0 )
844 {
845 for( i = v0; i < X->n; i++ )
846 {
847 r1 = X->p[i] >> (biL - t1);
848 X->p[i] <<= t1;
849 X->p[i] |= r0;
850 r0 = r1;
851 }
852 }
853
854cleanup:
855
856 return( ret );
857}
858
859/*
860 * Right-shift: X >>= count
861 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200862int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000863{
Paul Bakker23986e52011-04-24 08:57:21 +0000864 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200865 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000866
867 v0 = count / biL;
868 v1 = count & (biL - 1);
869
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100870 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200871 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100872
Paul Bakker5121ce52009-01-03 21:22:43 +0000873 /*
874 * shift by count / limb_size
875 */
876 if( v0 > 0 )
877 {
878 for( i = 0; i < X->n - v0; i++ )
879 X->p[i] = X->p[i + v0];
880
881 for( ; i < X->n; i++ )
882 X->p[i] = 0;
883 }
884
885 /*
886 * shift by count % limb_size
887 */
888 if( v1 > 0 )
889 {
Paul Bakker23986e52011-04-24 08:57:21 +0000890 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000891 {
Paul Bakker23986e52011-04-24 08:57:21 +0000892 r1 = X->p[i - 1] << (biL - v1);
893 X->p[i - 1] >>= v1;
894 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000895 r0 = r1;
896 }
897 }
898
899 return( 0 );
900}
901
902/*
903 * Compare unsigned values
904 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200905int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000906{
Paul Bakker23986e52011-04-24 08:57:21 +0000907 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000908
Paul Bakker23986e52011-04-24 08:57:21 +0000909 for( i = X->n; i > 0; i-- )
910 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000911 break;
912
Paul Bakker23986e52011-04-24 08:57:21 +0000913 for( j = Y->n; j > 0; j-- )
914 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000915 break;
916
Paul Bakker23986e52011-04-24 08:57:21 +0000917 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000918 return( 0 );
919
920 if( i > j ) return( 1 );
921 if( j > i ) return( -1 );
922
Paul Bakker23986e52011-04-24 08:57:21 +0000923 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000924 {
Paul Bakker23986e52011-04-24 08:57:21 +0000925 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
926 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000927 }
928
929 return( 0 );
930}
931
932/*
933 * Compare signed values
934 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200935int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000936{
Paul Bakker23986e52011-04-24 08:57:21 +0000937 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000938
Paul Bakker23986e52011-04-24 08:57:21 +0000939 for( i = X->n; i > 0; i-- )
940 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000941 break;
942
Paul Bakker23986e52011-04-24 08:57:21 +0000943 for( j = Y->n; j > 0; j-- )
944 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000945 break;
946
Paul Bakker23986e52011-04-24 08:57:21 +0000947 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000948 return( 0 );
949
950 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +0000951 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000952
953 if( X->s > 0 && Y->s < 0 ) return( 1 );
954 if( Y->s > 0 && X->s < 0 ) return( -1 );
955
Paul Bakker23986e52011-04-24 08:57:21 +0000956 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000957 {
Paul Bakker23986e52011-04-24 08:57:21 +0000958 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
959 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000960 }
961
962 return( 0 );
963}
964
Janos Follath3173a532019-10-14 09:09:32 +0100965/** Decide if an integer is less than the other, without branches.
966 *
967 * \param x First integer.
968 * \param y Second integer.
969 *
970 * \return 1 if \p x is less than \p y, 0 otherwise
971 */
Janos Follathc3b376e2019-10-11 14:21:53 +0100972static unsigned ct_lt_mpi_uint( const mbedtls_mpi_uint x,
973 const mbedtls_mpi_uint y )
Janos Follathe0187b92019-09-05 14:47:19 +0100974{
975 mbedtls_mpi_uint ret;
976 mbedtls_mpi_uint cond;
977
978 /*
979 * Check if the most significant bits (MSB) of the operands are different.
980 */
981 cond = ( x ^ y );
982 /*
983 * If the MSB are the same then the difference x-y will be negative (and
984 * have its MSB set to 1 during conversion to unsigned) if and only if x<y.
985 */
986 ret = ( x - y ) & ~cond;
987 /*
988 * If the MSB are different, then the operand with the MSB of 1 is the
989 * bigger. (That is if y has MSB of 1, then x<y is true and it is false if
990 * the MSB of y is 0.)
991 */
992 ret |= y & cond;
993
994
Janos Follathdb9f4492019-10-14 08:59:14 +0100995 ret = ret >> ( biL - 1 );
Janos Follathe0187b92019-09-05 14:47:19 +0100996
Janos Follath58239612019-10-29 15:08:46 +0000997 return (unsigned) ret;
Janos Follathe0187b92019-09-05 14:47:19 +0100998}
999
1000/*
1001 * Compare signed values in constant time
1002 */
Janos Follathc3b376e2019-10-11 14:21:53 +01001003int mbedtls_mpi_lt_mpi_ct( const mbedtls_mpi *X, const mbedtls_mpi *Y,
1004 unsigned *ret )
Janos Follathe0187b92019-09-05 14:47:19 +01001005{
1006 size_t i;
Janos Follatha2b9a962019-10-28 12:23:18 +00001007 /* The value of any of these variables is either 0 or 1 at all times. */
Janos Follath8ec2a952019-10-28 12:31:34 +00001008 unsigned cond, done, X_is_negative, Y_is_negative;
Janos Follathe0187b92019-09-05 14:47:19 +01001009
1010 if( X->n != Y->n )
1011 return MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
1012
1013 /*
Janos Follath51ed14e2019-10-28 12:12:15 +00001014 * Set sign_N to 1 if N >= 0, 0 if N < 0.
1015 * We know that N->s == 1 if N >= 0 and N->s == -1 if N < 0.
Janos Follathe0187b92019-09-05 14:47:19 +01001016 */
Janos Follath8ec2a952019-10-28 12:31:34 +00001017 X_is_negative = ( X->s & 2 ) >> 1;
1018 Y_is_negative = ( Y->s & 2 ) >> 1;
Janos Follathc3b376e2019-10-11 14:21:53 +01001019
1020 /*
1021 * If the signs are different, then the positive operand is the bigger.
Janos Follath8ec2a952019-10-28 12:31:34 +00001022 * That is if X is negative (X_is_negative == 1), then X < Y is true and it
1023 * is false if X is positive (X_is_negative == 0).
Janos Follathc3b376e2019-10-11 14:21:53 +01001024 */
Janos Follath8ec2a952019-10-28 12:31:34 +00001025 cond = ( X_is_negative ^ Y_is_negative );
1026 *ret = cond & X_is_negative;
Janos Follathc3b376e2019-10-11 14:21:53 +01001027
1028 /*
Janos Follatha2b9a962019-10-28 12:23:18 +00001029 * This is a constant-time function. We might have the result, but we still
Janos Follathc3b376e2019-10-11 14:21:53 +01001030 * need to go through the loop. Record if we have the result already.
1031 */
Janos Follathe0187b92019-09-05 14:47:19 +01001032 done = cond;
1033
1034 for( i = X->n; i > 0; i-- )
1035 {
1036 /*
Janos Follathb4edac52019-11-05 12:24:52 +00001037 * If Y->p[i - 1] < X->p[i - 1] then X < Y is true if and only if both
1038 * X and Y are negative.
Janos Follathc3b376e2019-10-11 14:21:53 +01001039 *
1040 * Again even if we can make a decision, we just mark the result and
1041 * the fact that we are done and continue looping.
Janos Follathe0187b92019-09-05 14:47:19 +01001042 */
Janos Follathb4edac52019-11-05 12:24:52 +00001043 cond = ct_lt_mpi_uint( Y->p[i - 1], X->p[i - 1] );
1044 *ret |= cond & ( 1 - done ) & X_is_negative;
Janos Follathcff9e6e2019-10-28 12:37:21 +00001045 done |= cond;
Janos Follathe0187b92019-09-05 14:47:19 +01001046
1047 /*
Janos Follathb4edac52019-11-05 12:24:52 +00001048 * If X->p[i - 1] < Y->p[i - 1] then X < Y is true if and only if both
1049 * X and Y are positive.
Janos Follathc3b376e2019-10-11 14:21:53 +01001050 *
1051 * Again even if we can make a decision, we just mark the result and
1052 * the fact that we are done and continue looping.
Janos Follathe0187b92019-09-05 14:47:19 +01001053 */
Janos Follathb4edac52019-11-05 12:24:52 +00001054 cond = ct_lt_mpi_uint( X->p[i - 1], Y->p[i - 1] );
1055 *ret |= cond & ( 1 - done ) & ( 1 - X_is_negative );
Janos Follathcff9e6e2019-10-28 12:37:21 +00001056 done |= cond;
Janos Follathe0187b92019-09-05 14:47:19 +01001057 }
1058
1059 return( 0 );
1060}
1061
Paul Bakker5121ce52009-01-03 21:22:43 +00001062/*
1063 * Compare signed values
1064 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001065int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +00001066{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001067 mbedtls_mpi Y;
1068 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001069
1070 *p = ( z < 0 ) ? -z : z;
1071 Y.s = ( z < 0 ) ? -1 : 1;
1072 Y.n = 1;
1073 Y.p = p;
1074
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001075 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001076}
1077
1078/*
1079 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1080 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001081int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001082{
Paul Bakker23986e52011-04-24 08:57:21 +00001083 int ret;
1084 size_t i, j;
Janos Follath6c922682015-10-30 17:43:11 +01001085 mbedtls_mpi_uint *o, *p, c, tmp;
Paul Bakker5121ce52009-01-03 21:22:43 +00001086
1087 if( X == B )
1088 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001089 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +00001090 }
1091
1092 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001093 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +02001094
Paul Bakkerf7ca7b92009-06-20 10:31:06 +00001095 /*
1096 * X should always be positive as a result of unsigned additions.
1097 */
1098 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001099
Paul Bakker23986e52011-04-24 08:57:21 +00001100 for( j = B->n; j > 0; j-- )
1101 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001102 break;
1103
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001104 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001105
1106 o = B->p; p = X->p; c = 0;
1107
Janos Follath6c922682015-10-30 17:43:11 +01001108 /*
1109 * tmp is used because it might happen that p == o
1110 */
Paul Bakker23986e52011-04-24 08:57:21 +00001111 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001112 {
Janos Follath6c922682015-10-30 17:43:11 +01001113 tmp= *o;
Paul Bakker5121ce52009-01-03 21:22:43 +00001114 *p += c; c = ( *p < c );
Janos Follath6c922682015-10-30 17:43:11 +01001115 *p += tmp; c += ( *p < tmp );
Paul Bakker5121ce52009-01-03 21:22:43 +00001116 }
1117
1118 while( c != 0 )
1119 {
1120 if( i >= X->n )
1121 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001122 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001123 p = X->p + i;
1124 }
1125
Paul Bakker2d319fd2012-09-16 21:34:26 +00001126 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +00001127 }
1128
1129cleanup:
1130
1131 return( ret );
1132}
1133
Gilles Peskinef3317e62020-06-09 10:39:38 +02001134/**
Gilles Peskine6f3b68d2020-06-08 21:58:22 +02001135 * Helper for mbedtls_mpi subtraction.
1136 *
1137 * Calculate d - s where d and s have the same size.
1138 * This function operates modulo (2^ciL)^n and returns the carry
1139 * (1 if there was a wraparound, i.e. if `d < s`, and 0 otherwise).
1140 *
1141 * \param n Number of limbs of \p d and \p s.
1142 * \param[in,out] d On input, the left operand.
1143 * On output, the result of the subtraction:
Gilles Peskinef3317e62020-06-09 10:39:38 +02001144 * \param[in] s The right operand.
Gilles Peskine6f3b68d2020-06-08 21:58:22 +02001145 *
1146 * \return 1 if `d < s`.
1147 * 0 if `d >= s`.
Paul Bakker5121ce52009-01-03 21:22:43 +00001148 */
Gilles Peskine6f3b68d2020-06-08 21:58:22 +02001149static mbedtls_mpi_uint mpi_sub_hlp( size_t n,
1150 mbedtls_mpi_uint *d,
1151 const mbedtls_mpi_uint *s )
Paul Bakker5121ce52009-01-03 21:22:43 +00001152{
Paul Bakker23986e52011-04-24 08:57:21 +00001153 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001154 mbedtls_mpi_uint c, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001155
1156 for( i = c = 0; i < n; i++, s++, d++ )
1157 {
1158 z = ( *d < c ); *d -= c;
1159 c = ( *d < *s ) + z; *d -= *s;
1160 }
1161
Gilles Peskine6f3b68d2020-06-08 21:58:22 +02001162 return( c );
Paul Bakker5121ce52009-01-03 21:22:43 +00001163}
1164
1165/*
Gilles Peskinefa85cc22020-06-08 22:50:35 +02001166 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
Paul Bakker5121ce52009-01-03 21:22:43 +00001167 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001168int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001169{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001170 mbedtls_mpi TB;
Paul Bakker23986e52011-04-24 08:57:21 +00001171 int ret;
1172 size_t n;
Gilles Peskinefa85cc22020-06-08 22:50:35 +02001173 mbedtls_mpi_uint carry;
Paul Bakker5121ce52009-01-03 21:22:43 +00001174
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001175 mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001176
1177 if( X == B )
1178 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001179 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001180 B = &TB;
1181 }
1182
1183 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001184 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001185
Paul Bakker1ef7a532009-06-20 10:50:55 +00001186 /*
Paul Bakker60b1d102013-10-29 10:02:51 +01001187 * X should always be positive as a result of unsigned subtractions.
Paul Bakker1ef7a532009-06-20 10:50:55 +00001188 */
1189 X->s = 1;
1190
Paul Bakker5121ce52009-01-03 21:22:43 +00001191 ret = 0;
1192
Paul Bakker23986e52011-04-24 08:57:21 +00001193 for( n = B->n; n > 0; n-- )
1194 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001195 break;
1196
Gilles Peskinefa85cc22020-06-08 22:50:35 +02001197 carry = mpi_sub_hlp( n, X->p, B->p );
1198 if( carry != 0 )
Gilles Peskine6f3b68d2020-06-08 21:58:22 +02001199 {
Gilles Peskinefa85cc22020-06-08 22:50:35 +02001200 /* Propagate the carry to the first nonzero limb of X. */
1201 for( ; n < X->n && X->p[n] == 0; n++ )
1202 --X->p[n];
1203 /* If we ran out of space for the carry, it means that the result
1204 * is negative. */
1205 if( n == X->n )
1206 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1207 --X->p[n];
Gilles Peskine6f3b68d2020-06-08 21:58:22 +02001208 }
Paul Bakker5121ce52009-01-03 21:22:43 +00001209
1210cleanup:
1211
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001212 mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001213
1214 return( ret );
1215}
1216
1217/*
1218 * Signed addition: X = A + B
1219 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001220int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001221{
1222 int ret, s = A->s;
1223
1224 if( A->s * B->s < 0 )
1225 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001226 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001227 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001228 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001229 X->s = s;
1230 }
1231 else
1232 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001233 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001234 X->s = -s;
1235 }
1236 }
1237 else
1238 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001239 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001240 X->s = s;
1241 }
1242
1243cleanup:
1244
1245 return( ret );
1246}
1247
1248/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001249 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001250 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001251int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001252{
1253 int ret, s = A->s;
1254
1255 if( A->s * B->s > 0 )
1256 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001257 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001258 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001259 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001260 X->s = s;
1261 }
1262 else
1263 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001264 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001265 X->s = -s;
1266 }
1267 }
1268 else
1269 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001270 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001271 X->s = s;
1272 }
1273
1274cleanup:
1275
1276 return( ret );
1277}
1278
1279/*
1280 * Signed addition: X = A + b
1281 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001282int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001283{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001284 mbedtls_mpi _B;
1285 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001286
1287 p[0] = ( b < 0 ) ? -b : b;
1288 _B.s = ( b < 0 ) ? -1 : 1;
1289 _B.n = 1;
1290 _B.p = p;
1291
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001292 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001293}
1294
1295/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001296 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001297 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001298int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001299{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001300 mbedtls_mpi _B;
1301 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001302
1303 p[0] = ( b < 0 ) ? -b : b;
1304 _B.s = ( b < 0 ) ? -1 : 1;
1305 _B.n = 1;
1306 _B.p = p;
1307
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001308 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001309}
1310
1311/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001312 * Helper for mbedtls_mpi multiplication
Paul Bakkerfc4f46f2013-06-24 19:23:56 +02001313 */
1314static
1315#if defined(__APPLE__) && defined(__arm__)
1316/*
1317 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1318 * appears to need this to prevent bad ARM code generation at -O3.
1319 */
1320__attribute__ ((noinline))
1321#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001322void 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 +00001323{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001324 mbedtls_mpi_uint c = 0, t = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001325
1326#if defined(MULADDC_HUIT)
1327 for( ; i >= 8; i -= 8 )
1328 {
1329 MULADDC_INIT
1330 MULADDC_HUIT
1331 MULADDC_STOP
1332 }
1333
1334 for( ; i > 0; i-- )
1335 {
1336 MULADDC_INIT
1337 MULADDC_CORE
1338 MULADDC_STOP
1339 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001340#else /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001341 for( ; i >= 16; i -= 16 )
1342 {
1343 MULADDC_INIT
1344 MULADDC_CORE MULADDC_CORE
1345 MULADDC_CORE MULADDC_CORE
1346 MULADDC_CORE MULADDC_CORE
1347 MULADDC_CORE MULADDC_CORE
1348
1349 MULADDC_CORE MULADDC_CORE
1350 MULADDC_CORE MULADDC_CORE
1351 MULADDC_CORE MULADDC_CORE
1352 MULADDC_CORE MULADDC_CORE
1353 MULADDC_STOP
1354 }
1355
1356 for( ; i >= 8; i -= 8 )
1357 {
1358 MULADDC_INIT
1359 MULADDC_CORE MULADDC_CORE
1360 MULADDC_CORE MULADDC_CORE
1361
1362 MULADDC_CORE MULADDC_CORE
1363 MULADDC_CORE MULADDC_CORE
1364 MULADDC_STOP
1365 }
1366
1367 for( ; i > 0; i-- )
1368 {
1369 MULADDC_INIT
1370 MULADDC_CORE
1371 MULADDC_STOP
1372 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001373#endif /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001374
1375 t++;
1376
1377 do {
1378 *d += c; c = ( *d < c ); d++;
1379 }
1380 while( c != 0 );
1381}
1382
1383/*
1384 * Baseline multiplication: X = A * B (HAC 14.12)
1385 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001386int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001387{
Paul Bakker23986e52011-04-24 08:57:21 +00001388 int ret;
1389 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001390 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001391
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001392 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001393
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001394 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1395 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001396
Paul Bakker23986e52011-04-24 08:57:21 +00001397 for( i = A->n; i > 0; i-- )
1398 if( A->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001399 break;
1400
Paul Bakker23986e52011-04-24 08:57:21 +00001401 for( j = B->n; j > 0; j-- )
1402 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001403 break;
1404
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001405 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1406 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001407
Paul Bakker23986e52011-04-24 08:57:21 +00001408 for( i++; j > 0; j-- )
1409 mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001410
1411 X->s = A->s * B->s;
1412
1413cleanup:
1414
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001415 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001416
1417 return( ret );
1418}
1419
1420/*
1421 * Baseline multiplication: X = A * b
1422 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001423int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001424{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001425 mbedtls_mpi _B;
1426 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001427
1428 _B.s = 1;
1429 _B.n = 1;
1430 _B.p = p;
1431 p[0] = b;
1432
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001433 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001434}
1435
1436/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001437 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1438 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001439 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001440static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1441 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001442{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001443#if defined(MBEDTLS_HAVE_UDBL)
1444 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001445#else
Simon Butcher9803d072016-01-03 00:24:34 +00001446 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1447 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001448 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1449 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001450 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001451#endif
1452
Simon Butcher15b15d12015-11-26 19:35:03 +00001453 /*
1454 * Check for overflow
1455 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001456 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001457 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001458 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001459
Simon Butcherf5ba0452015-12-27 23:01:55 +00001460 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001461 }
1462
1463#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001464 dividend = (mbedtls_t_udbl) u1 << biL;
1465 dividend |= (mbedtls_t_udbl) u0;
1466 quotient = dividend / d;
1467 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1468 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1469
1470 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001471 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001472
1473 return (mbedtls_mpi_uint) quotient;
1474#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001475
1476 /*
1477 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1478 * Vol. 2 - Seminumerical Algorithms, Knuth
1479 */
1480
1481 /*
1482 * Normalize the divisor, d, and dividend, u0, u1
1483 */
1484 s = mbedtls_clz( d );
1485 d = d << s;
1486
1487 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001488 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001489 u0 = u0 << s;
1490
1491 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001492 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001493
1494 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001495 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001496
1497 /*
1498 * Find the first quotient and remainder
1499 */
1500 q1 = u1 / d1;
1501 r0 = u1 - d1 * q1;
1502
1503 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1504 {
1505 q1 -= 1;
1506 r0 += d1;
1507
1508 if ( r0 >= radix ) break;
1509 }
1510
Simon Butcherf5ba0452015-12-27 23:01:55 +00001511 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001512 q0 = rAX / d1;
1513 r0 = rAX - q0 * d1;
1514
1515 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1516 {
1517 q0 -= 1;
1518 r0 += d1;
1519
1520 if ( r0 >= radix ) break;
1521 }
1522
1523 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001524 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001525
1526 quotient = q1 * radix + q0;
1527
1528 return quotient;
1529#endif
1530}
1531
1532/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001533 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001534 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001535int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001536{
Paul Bakker23986e52011-04-24 08:57:21 +00001537 int ret;
1538 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001539 mbedtls_mpi X, Y, Z, T1, T2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001540
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001541 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1542 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001543
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001544 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1545 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001546
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001547 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001548 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001549 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1550 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001551 return( 0 );
1552 }
1553
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001554 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1555 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001556 X.s = Y.s = 1;
1557
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001558 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1559 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1560 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1561 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001562
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001563 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001564 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001565 {
1566 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001567 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1568 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001569 }
1570 else k = 0;
1571
1572 n = X.n - 1;
1573 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001574 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001575
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001576 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001577 {
1578 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001579 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001580 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001581 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001582
1583 for( i = n; i > t ; i-- )
1584 {
1585 if( X.p[i] >= Y.p[t] )
1586 Z.p[i - t - 1] = ~0;
1587 else
1588 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001589 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1590 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001591 }
1592
1593 Z.p[i - t - 1]++;
1594 do
1595 {
1596 Z.p[i - t - 1]--;
1597
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001598 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001599 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001600 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001601 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001602
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001603 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001604 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1605 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001606 T2.p[2] = X.p[i];
1607 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001608 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001609
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001610 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1611 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1612 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001613
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001614 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001615 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001616 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1617 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1618 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001619 Z.p[i - t - 1]--;
1620 }
1621 }
1622
1623 if( Q != NULL )
1624 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001625 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001626 Q->s = A->s * B->s;
1627 }
1628
1629 if( R != NULL )
1630 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001631 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001632 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001633 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001634
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001635 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001636 R->s = 1;
1637 }
1638
1639cleanup:
1640
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001641 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1642 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001643
1644 return( ret );
1645}
1646
1647/*
1648 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001649 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001650int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001651{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001652 mbedtls_mpi _B;
1653 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001654
1655 p[0] = ( b < 0 ) ? -b : b;
1656 _B.s = ( b < 0 ) ? -1 : 1;
1657 _B.n = 1;
1658 _B.p = p;
1659
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001660 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001661}
1662
1663/*
1664 * Modulo: R = A mod B
1665 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001666int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001667{
1668 int ret;
1669
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001670 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1671 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001672
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001673 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001674
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001675 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1676 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001677
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001678 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1679 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001680
1681cleanup:
1682
1683 return( ret );
1684}
1685
1686/*
1687 * Modulo: r = A mod b
1688 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001689int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001690{
Paul Bakker23986e52011-04-24 08:57:21 +00001691 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001692 mbedtls_mpi_uint x, y, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001693
1694 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001695 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001696
1697 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001698 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001699
1700 /*
1701 * handle trivial cases
1702 */
1703 if( b == 1 )
1704 {
1705 *r = 0;
1706 return( 0 );
1707 }
1708
1709 if( b == 2 )
1710 {
1711 *r = A->p[0] & 1;
1712 return( 0 );
1713 }
1714
1715 /*
1716 * general case
1717 */
Paul Bakker23986e52011-04-24 08:57:21 +00001718 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001719 {
Paul Bakker23986e52011-04-24 08:57:21 +00001720 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001721 y = ( y << biH ) | ( x >> biH );
1722 z = y / b;
1723 y -= z * b;
1724
1725 x <<= biH;
1726 y = ( y << biH ) | ( x >> biH );
1727 z = y / b;
1728 y -= z * b;
1729 }
1730
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001731 /*
1732 * If A is negative, then the current y represents a negative value.
1733 * Flipping it to the positive side.
1734 */
1735 if( A->s < 0 && y != 0 )
1736 y = b - y;
1737
Paul Bakker5121ce52009-01-03 21:22:43 +00001738 *r = y;
1739
1740 return( 0 );
1741}
1742
1743/*
1744 * Fast Montgomery initialization (thanks to Tom St Denis)
1745 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001746static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001747{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001748 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001749 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00001750
1751 x = m0;
1752 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001753
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001754 for( i = biL; i >= 8; i /= 2 )
1755 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001756
1757 *mm = ~x + 1;
1758}
1759
Gilles Peskined108d072020-06-04 15:00:49 +02001760/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1761 *
1762 * \param[in,out] A One of the numbers to multiply.
Gilles Peskinecc6a6bf2020-06-08 22:37:50 +02001763 * It must have at least as many limbs as N
1764 * (A->n >= N->n), and any limbs beyond n are ignored.
Gilles Peskined108d072020-06-04 15:00:49 +02001765 * On successful completion, A contains the result of
1766 * the multiplication A * B * R^-1 mod N where
1767 * R = (2^ciL)^n.
1768 * \param[in] B One of the numbers to multiply.
1769 * It must be nonzero and must not have more limbs than N
1770 * (B->n <= N->n).
1771 * \param[in] N The modulo. N must be odd.
1772 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1773 * This is -N^-1 mod 2^ciL.
1774 * \param[in,out] T A bignum for temporary storage.
1775 * It must be at least twice the limb size of N plus 2
1776 * (T->n >= 2 * (N->n + 1)).
1777 * Its initial content is unused and
1778 * its final content is indeterminate.
1779 * Note that unlike the usual convention in the library
1780 * for `const mbedtls_mpi*`, the content of T can change.
Paul Bakker5121ce52009-01-03 21:22:43 +00001781 */
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001782static 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 +02001783 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001784{
Paul Bakker23986e52011-04-24 08:57:21 +00001785 size_t i, n, m;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001786 mbedtls_mpi_uint u0, u1, *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00001787
1788 memset( T->p, 0, T->n * ciL );
1789
1790 d = T->p;
1791 n = N->n;
1792 m = ( B->n < n ) ? B->n : n;
1793
1794 for( i = 0; i < n; i++ )
1795 {
1796 /*
1797 * T = (T + u0*B + u1*N) / 2^biL
1798 */
1799 u0 = A->p[i];
1800 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1801
1802 mpi_mul_hlp( m, B->p, d, u0 );
1803 mpi_mul_hlp( n, N->p, d, u1 );
1804
1805 *d++ = u0; d[n + 1] = 0;
1806 }
1807
Gilles Peskinecc6a6bf2020-06-08 22:37:50 +02001808 /* At this point, d is either the desired result or the desired result
1809 * plus N. We now potentially subtract N, avoiding leaking whether the
1810 * subtraction is performed through side channels. */
Paul Bakker5121ce52009-01-03 21:22:43 +00001811
Gilles Peskinecc6a6bf2020-06-08 22:37:50 +02001812 /* Copy the n least significant limbs of d to A, so that
1813 * A = d if d < N (recall that N has n limbs). */
1814 memcpy( A->p, d, n * ciL );
Gilles Peskinef3317e62020-06-09 10:39:38 +02001815 /* If d >= N then we want to set A to d - N. To prevent timing attacks,
Gilles Peskinecc6a6bf2020-06-08 22:37:50 +02001816 * do the calculation without using conditional tests. */
1817 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
Gilles Peskine7ff812e2020-06-04 21:05:24 +02001818 d[n] += 1;
Gilles Peskine6f3b68d2020-06-08 21:58:22 +02001819 d[n] -= mpi_sub_hlp( n, d, N->p );
Gilles Peskinecc6a6bf2020-06-08 22:37:50 +02001820 /* If d0 < N then d < (2^biL)^n
1821 * so d[n] == 0 and we want to keep A as it is.
1822 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
1823 * so d[n] == 1 and we want to set A to the result of the subtraction
1824 * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
1825 * This exactly corresponds to a conditional assignment. */
1826 mpi_safe_cond_assign( n, A->p, d, (unsigned char) d[n] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001827}
1828
1829/*
1830 * Montgomery reduction: A = A * R^-1 mod N
Gilles Peskined108d072020-06-04 15:00:49 +02001831 *
1832 * See mpi_montmul() regarding constraints and guarantees on the parameters.
Paul Bakker5121ce52009-01-03 21:22:43 +00001833 */
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001834static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001835{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001836 mbedtls_mpi_uint z = 1;
1837 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001838
Paul Bakker8ddb6452013-02-27 14:56:33 +01001839 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001840 U.p = &z;
1841
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001842 mpi_montmul( A, &U, N, mm, T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001843}
1844
1845/*
1846 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1847 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001848int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR )
Paul Bakker5121ce52009-01-03 21:22:43 +00001849{
Paul Bakker23986e52011-04-24 08:57:21 +00001850 int ret;
1851 size_t wbits, wsize, one = 1;
1852 size_t i, j, nblimbs;
1853 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001854 mbedtls_mpi_uint ei, mm, state;
1855 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00001856 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001857
Hanno Becker930ec7d2018-03-09 10:48:00 +00001858 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001859 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001860
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001861 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1862 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001863
1864 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001865 * Init temps and window size
1866 */
1867 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001868 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
1869 mbedtls_mpi_init( &Apos );
Paul Bakker5121ce52009-01-03 21:22:43 +00001870 memset( W, 0, sizeof( W ) );
1871
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001872 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00001873
1874 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1875 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1876
Peter Kolbusf5d153d2018-12-11 14:01:44 -06001877#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001878 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1879 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Peter Kolbusf5d153d2018-12-11 14:01:44 -06001880#endif
Paul Bakkerb6d5f082011-11-25 11:52:11 +00001881
Paul Bakker5121ce52009-01-03 21:22:43 +00001882 j = N->n + 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001883 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1884 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1885 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001886
1887 /*
Paul Bakker50546922012-05-19 08:40:49 +00001888 * Compensate for negative A (and correct at the end)
1889 */
1890 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00001891 if( neg )
1892 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001893 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00001894 Apos.s = 1;
1895 A = &Apos;
1896 }
1897
1898 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001899 * If 1st call, pre-compute R^2 mod N
1900 */
1901 if( _RR == NULL || _RR->p == NULL )
1902 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001903 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1904 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1905 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001906
1907 if( _RR != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001908 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001909 }
1910 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001911 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001912
1913 /*
1914 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1915 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001916 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
1917 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Paul Bakkerc2024f42014-01-23 20:38:35 +01001918 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001919 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001920
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001921 mpi_montmul( &W[1], &RR, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001922
1923 /*
1924 * X = R^2 * R^-1 mod N = R mod N
1925 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001926 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001927 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001928
1929 if( wsize > 1 )
1930 {
1931 /*
1932 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1933 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001934 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001935
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001936 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1937 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001938
1939 for( i = 0; i < wsize - 1; i++ )
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001940 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01001941
Paul Bakker5121ce52009-01-03 21:22:43 +00001942 /*
1943 * W[i] = W[i - 1] * W[1]
1944 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001945 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001946 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001947 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1948 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001949
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001950 mpi_montmul( &W[i], &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001951 }
1952 }
1953
1954 nblimbs = E->n;
1955 bufsize = 0;
1956 nbits = 0;
1957 wbits = 0;
1958 state = 0;
1959
1960 while( 1 )
1961 {
1962 if( bufsize == 0 )
1963 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01001964 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001965 break;
1966
Paul Bakker0d7702c2013-10-29 16:18:35 +01001967 nblimbs--;
1968
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001969 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00001970 }
1971
1972 bufsize--;
1973
1974 ei = (E->p[nblimbs] >> bufsize) & 1;
1975
1976 /*
1977 * skip leading 0s
1978 */
1979 if( ei == 0 && state == 0 )
1980 continue;
1981
1982 if( ei == 0 && state == 1 )
1983 {
1984 /*
1985 * out of window, square X
1986 */
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02001987 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00001988 continue;
1989 }
1990
1991 /*
1992 * add ei to current window
1993 */
1994 state = 2;
1995
1996 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02001997 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001998
1999 if( nbits == wsize )
2000 {
2001 /*
2002 * X = X^wsize R^-1 mod N
2003 */
2004 for( i = 0; i < wsize; i++ )
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02002005 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002006
2007 /*
2008 * X = X * W[wbits] R^-1 mod N
2009 */
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02002010 mpi_montmul( X, &W[wbits], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002011
2012 state--;
2013 nbits = 0;
2014 wbits = 0;
2015 }
2016 }
2017
2018 /*
2019 * process the remaining bits
2020 */
2021 for( i = 0; i < nbits; i++ )
2022 {
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02002023 mpi_montmul( X, X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002024
2025 wbits <<= 1;
2026
Paul Bakker66d5d072014-06-17 16:39:18 +02002027 if( ( wbits & ( one << wsize ) ) != 0 )
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02002028 mpi_montmul( X, &W[1], N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002029 }
2030
2031 /*
2032 * X = A^E * R * R^-1 mod N = A^E mod N
2033 */
Gilles Peskine8ff7cc92020-06-04 20:55:15 +02002034 mpi_montred( X, N, mm, &T );
Paul Bakker5121ce52009-01-03 21:22:43 +00002035
Hanno Beckera4af1c42017-04-18 09:07:45 +01002036 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00002037 {
2038 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002039 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00002040 }
2041
Paul Bakker5121ce52009-01-03 21:22:43 +00002042cleanup:
2043
Paul Bakker66d5d072014-06-17 16:39:18 +02002044 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002045 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00002046
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002047 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Paul Bakker6c591fa2011-05-05 11:49:20 +00002048
Paul Bakker75a28602014-03-31 12:08:17 +02002049 if( _RR == NULL || _RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002050 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002051
2052 return( ret );
2053}
2054
Paul Bakker5121ce52009-01-03 21:22:43 +00002055/*
2056 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2057 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002058int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00002059{
Paul Bakker23986e52011-04-24 08:57:21 +00002060 int ret;
2061 size_t lz, lzt;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002062 mbedtls_mpi TG, TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00002063
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002064 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002065
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002066 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2067 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002068
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002069 lz = mbedtls_mpi_lsb( &TA );
2070 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002071
Paul Bakker66d5d072014-06-17 16:39:18 +02002072 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002073 lz = lzt;
2074
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002075 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
2076 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002077
Paul Bakker5121ce52009-01-03 21:22:43 +00002078 TA.s = TB.s = 1;
2079
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002080 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002081 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002082 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2083 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002084
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002085 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002086 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002087 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2088 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002089 }
2090 else
2091 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002092 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2093 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002094 }
2095 }
2096
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002097 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2098 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002099
2100cleanup:
2101
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002102 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00002103
2104 return( ret );
2105}
2106
Paul Bakker33dc46b2014-04-30 16:11:39 +02002107/*
2108 * Fill X with size bytes of random.
2109 *
2110 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02002111 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02002112 * deterministic, eg for tests).
2113 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002114int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002115 int (*f_rng)(void *, unsigned char *, size_t),
2116 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00002117{
Paul Bakker23986e52011-04-24 08:57:21 +00002118 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002119 unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
Paul Bakker33dc46b2014-04-30 16:11:39 +02002120
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002121 if( size > MBEDTLS_MPI_MAX_SIZE )
2122 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker287781a2011-03-26 13:18:49 +00002123
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002124 MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) );
2125 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) );
Paul Bakker287781a2011-03-26 13:18:49 +00002126
2127cleanup:
Hanno Becker88807112017-10-18 12:41:30 +01002128 mbedtls_zeroize( buf, sizeof( buf ) );
Paul Bakker287781a2011-03-26 13:18:49 +00002129 return( ret );
2130}
2131
Paul Bakker5121ce52009-01-03 21:22:43 +00002132/*
2133 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2134 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002135int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00002136{
2137 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002138 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Paul Bakker5121ce52009-01-03 21:22:43 +00002139
Hanno Becker4bcb4912017-04-18 15:49:39 +01002140 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002141 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002142
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002143 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
2144 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
2145 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002146
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002147 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002148
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002149 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002150 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002151 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002152 goto cleanup;
2153 }
2154
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002155 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2156 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2157 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2158 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002159
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002160 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2161 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2162 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2163 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002164
2165 do
2166 {
2167 while( ( TU.p[0] & 1 ) == 0 )
2168 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002169 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002170
2171 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2172 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002173 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2174 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002175 }
2176
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002177 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2178 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002179 }
2180
2181 while( ( TV.p[0] & 1 ) == 0 )
2182 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002183 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002184
2185 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2186 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002187 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2188 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002189 }
2190
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002191 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2192 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002193 }
2194
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002195 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002196 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002197 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2198 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2199 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002200 }
2201 else
2202 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002203 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2204 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2205 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002206 }
2207 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002208 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002209
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002210 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2211 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002212
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002213 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2214 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002215
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002216 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002217
2218cleanup:
2219
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002220 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2221 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2222 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002223
2224 return( ret );
2225}
2226
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002227#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00002228
Paul Bakker5121ce52009-01-03 21:22:43 +00002229static const int small_prime[] =
2230{
2231 3, 5, 7, 11, 13, 17, 19, 23,
2232 29, 31, 37, 41, 43, 47, 53, 59,
2233 61, 67, 71, 73, 79, 83, 89, 97,
2234 101, 103, 107, 109, 113, 127, 131, 137,
2235 139, 149, 151, 157, 163, 167, 173, 179,
2236 181, 191, 193, 197, 199, 211, 223, 227,
2237 229, 233, 239, 241, 251, 257, 263, 269,
2238 271, 277, 281, 283, 293, 307, 311, 313,
2239 317, 331, 337, 347, 349, 353, 359, 367,
2240 373, 379, 383, 389, 397, 401, 409, 419,
2241 421, 431, 433, 439, 443, 449, 457, 461,
2242 463, 467, 479, 487, 491, 499, 503, 509,
2243 521, 523, 541, 547, 557, 563, 569, 571,
2244 577, 587, 593, 599, 601, 607, 613, 617,
2245 619, 631, 641, 643, 647, 653, 659, 661,
2246 673, 677, 683, 691, 701, 709, 719, 727,
2247 733, 739, 743, 751, 757, 761, 769, 773,
2248 787, 797, 809, 811, 821, 823, 827, 829,
2249 839, 853, 857, 859, 863, 877, 881, 883,
2250 887, 907, 911, 919, 929, 937, 941, 947,
2251 953, 967, 971, 977, 983, 991, 997, -103
2252};
2253
2254/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002255 * Small divisors test (X must be positive)
2256 *
2257 * Return values:
2258 * 0: no small factor (possible prime, more tests needed)
2259 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002260 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002261 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002262 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002263static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002264{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002265 int ret = 0;
2266 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002267 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002268
Paul Bakker5121ce52009-01-03 21:22:43 +00002269 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002270 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002271
2272 for( i = 0; small_prime[i] > 0; i++ )
2273 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002274 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002275 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002276
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002277 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002278
2279 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002280 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002281 }
2282
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002283cleanup:
2284 return( ret );
2285}
2286
2287/*
2288 * Miller-Rabin pseudo-primality test (HAC 4.24)
2289 */
Janos Follath72d555d2018-09-03 14:45:23 +01002290static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002291 int (*f_rng)(void *, unsigned char *, size_t),
2292 void *p_rng )
2293{
Pascal Junodb99183d2015-03-11 16:49:45 +01002294 int ret, count;
Janos Follath72d555d2018-09-03 14:45:23 +01002295 size_t i, j, k, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002296 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002297
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002298 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
2299 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002300
Paul Bakker5121ce52009-01-03 21:22:43 +00002301 /*
2302 * W = |X| - 1
2303 * R = W >> lsb( W )
2304 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002305 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2306 s = mbedtls_mpi_lsb( &W );
2307 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2308 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002309
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002310 i = mbedtls_mpi_bitlen( X );
Paul Bakker5121ce52009-01-03 21:22:43 +00002311
Janos Follath72d555d2018-09-03 14:45:23 +01002312 for( i = 0; i < rounds; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00002313 {
2314 /*
2315 * pick a random A, 1 < A < |X| - 1
2316 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002317 count = 0;
2318 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002319 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002320
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002321 j = mbedtls_mpi_bitlen( &A );
2322 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002323 if (j > k) {
Darryl Green56d7cc42018-10-02 13:21:35 +01002324 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Pascal Junodb99183d2015-03-11 16:49:45 +01002325 }
2326
2327 if (count++ > 30) {
Jens Wiklanderb2aa9382019-01-17 13:30:57 +01002328 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2329 goto cleanup;
Pascal Junodb99183d2015-03-11 16:49:45 +01002330 }
2331
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002332 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2333 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002334
2335 /*
2336 * A = A^R mod |X|
2337 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002338 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002339
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002340 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2341 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002342 continue;
2343
2344 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002345 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002346 {
2347 /*
2348 * A = A * A mod |X|
2349 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002350 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2351 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002352
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002353 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002354 break;
2355
2356 j++;
2357 }
2358
2359 /*
2360 * not prime if A != |X| - 1 or A == 1
2361 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002362 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2363 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002364 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002365 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002366 break;
2367 }
2368 }
2369
2370cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002371 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2372 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002373
2374 return( ret );
2375}
2376
2377/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002378 * Pseudo-primality test: small factors, then Miller-Rabin
2379 */
Darryl Green94759f62018-10-16 15:09:19 +01002380static int mpi_is_prime_internal( const mbedtls_mpi *X, int rounds,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002381 int (*f_rng)(void *, unsigned char *, size_t),
2382 void *p_rng )
2383{
2384 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002385 mbedtls_mpi XX;
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002386
2387 XX.s = 1;
2388 XX.n = X->n;
2389 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002390
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002391 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2392 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2393 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002394
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002395 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002396 return( 0 );
2397
2398 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2399 {
2400 if( ret == 1 )
2401 return( 0 );
2402
2403 return( ret );
2404 }
2405
Janos Follath72d555d2018-09-03 14:45:23 +01002406 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
2407}
2408
2409/*
2410 * Pseudo-primality test, error probability 2^-80
2411 */
2412int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2413 int (*f_rng)(void *, unsigned char *, size_t),
2414 void *p_rng )
2415{
2416 return mpi_is_prime_internal( X, 40, f_rng, p_rng );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002417}
2418
2419/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002420 * Prime number generation
2421 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002422int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002423 int (*f_rng)(void *, unsigned char *, size_t),
2424 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002425{
Paul Bakker23986e52011-04-24 08:57:21 +00002426 int ret;
2427 size_t k, n;
Janos Follath72d555d2018-09-03 14:45:23 +01002428 int rounds;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002429 mbedtls_mpi_uint r;
2430 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002431
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002432 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2433 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002434
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002435 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002436
2437 n = BITS_TO_LIMBS( nbits );
2438
Janos Follath72d555d2018-09-03 14:45:23 +01002439 /*
2440 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2441 */
2442 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2443 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2444 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2445
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002446 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002447
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002448 k = mbedtls_mpi_bitlen( X );
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002449 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002450
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002451 mbedtls_mpi_set_bit( X, nbits-1, 1 );
Pascal Junodb99183d2015-03-11 16:49:45 +01002452
2453 X->p[0] |= 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00002454
2455 if( dh_flag == 0 )
2456 {
Janos Follath72d555d2018-09-03 14:45:23 +01002457 while( ( ret = mpi_is_prime_internal( X, rounds, f_rng, p_rng ) ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002458 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002459 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002460 goto cleanup;
2461
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002462 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002463 }
2464 }
2465 else
2466 {
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002467 /*
2468 * An necessary condition for Y and X = 2Y + 1 to be prime
2469 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2470 * Make sure it is satisfied, while keeping X = 3 mod 4
2471 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002472
2473 X->p[0] |= 2;
2474
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002475 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002476 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002477 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002478 else if( r == 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002479 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002480
2481 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002482 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2483 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002484
2485 while( 1 )
2486 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002487 /*
2488 * First, check small factors for X and Y
2489 * before doing Miller-Rabin on any of them
2490 */
2491 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2492 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
Janos Follath72d555d2018-09-03 14:45:23 +01002493 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
2494 == 0 &&
2495 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
2496 == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002497 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002498 break;
Paul Bakker5121ce52009-01-03 21:22:43 +00002499 }
2500
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002501 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002502 goto cleanup;
2503
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002504 /*
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002505 * Next candidates. We want to preserve Y = (X-1) / 2 and
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002506 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2507 * so up Y by 6 and X by 12.
2508 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002509 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2510 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002511 }
2512 }
2513
2514cleanup:
2515
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002516 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002517
2518 return( ret );
2519}
2520
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002521#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002522
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002523#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002524
Paul Bakker23986e52011-04-24 08:57:21 +00002525#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002526
2527static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2528{
2529 { 693, 609, 21 },
2530 { 1764, 868, 28 },
2531 { 768454923, 542167814, 1 }
2532};
2533
Paul Bakker5121ce52009-01-03 21:22:43 +00002534/*
2535 * Checkup routine
2536 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002537int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002538{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002539 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002540 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002541
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002542 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2543 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002544
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002545 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002546 "EFE021C2645FD1DC586E69184AF4A31E" \
2547 "D5F53E93B5F123FA41680867BA110131" \
2548 "944FE7952E2517337780CB0DB80E61AA" \
2549 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2550
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002551 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002552 "B2E7EFD37075B9F03FF989C7C5051C20" \
2553 "34D2A323810251127E7BF8625A4F49A5" \
2554 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2555 "5B5C25763222FEFCCFC38B832366C29E" ) );
2556
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002557 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002558 "0066A198186C18C10B2F5ED9B522752A" \
2559 "9830B69916E535C8F047518A889A43A5" \
2560 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2561
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002562 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002563
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002564 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002565 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2566 "9E857EA95A03512E2BAE7391688D264A" \
2567 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2568 "8001B72E848A38CAE1C65F78E56ABDEF" \
2569 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2570 "ECF677152EF804370C1A305CAF3B5BF1" \
2571 "30879B56C61DE584A0F53A2447A51E" ) );
2572
2573 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002574 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002575
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002576 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002577 {
2578 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002579 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002580
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002581 ret = 1;
2582 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002583 }
2584
2585 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002586 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002587
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002588 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002589
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002590 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002591 "256567336059E52CAE22925474705F39A94" ) );
2592
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002593 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002594 "6613F26162223DF488E9CD48CC132C7A" \
2595 "0AC93C701B001B092E4E5B9F73BCD27B" \
2596 "9EE50D0657C77F374E903CDFA4C642" ) );
2597
2598 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002599 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002600
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002601 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2602 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002603 {
2604 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002605 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002606
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002607 ret = 1;
2608 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002609 }
2610
2611 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002612 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002613
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002614 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002615
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002616 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002617 "36E139AEA55215609D2816998ED020BB" \
2618 "BD96C37890F65171D948E9BC7CBAA4D9" \
2619 "325D24D6A3C12710F10A09FA08AB87" ) );
2620
2621 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002622 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002623
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002624 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002625 {
2626 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002627 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002628
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002629 ret = 1;
2630 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002631 }
2632
2633 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002634 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002635
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002636 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002637
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002638 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002639 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2640 "C3DBA76456363A10869622EAC2DD84EC" \
2641 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2642
2643 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002644 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002645
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002646 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002647 {
2648 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002649 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002650
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002651 ret = 1;
2652 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002653 }
2654
2655 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002656 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002657
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002658 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002659 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002660
Paul Bakker66d5d072014-06-17 16:39:18 +02002661 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002662 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002663 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2664 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002665
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002666 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002667
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002668 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002669 {
2670 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002671 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002672
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002673 ret = 1;
2674 goto cleanup;
2675 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002676 }
2677
2678 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002679 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002680
Paul Bakker5121ce52009-01-03 21:22:43 +00002681cleanup:
2682
2683 if( ret != 0 && verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002684 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002685
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002686 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2687 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002688
2689 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002690 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002691
2692 return( ret );
2693}
2694
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002695#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002696
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002697#endif /* MBEDTLS_BIGNUM_C */