blob: 9f13da4421309423693fcf53094edd56d4cbdea3 [file] [log] [blame]
Paul Bakker5121ce52009-01-03 21:22:43 +00001/*
2 * Multi-precision integer library
3 *
Manuel Pégourié-Gonnard6fb81872015-07-27 11:11:48 +02004 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
Manuel Pégourié-Gonnard37ff1402015-09-04 14:21:07 +02005 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
Paul Bakkerb96f1542010-07-18 20:36:00 +000018 *
Manuel Pégourié-Gonnardfe446432015-03-06 13:17:10 +000019 * This file is part of mbed TLS (https://tls.mbed.org)
Paul Bakker5121ce52009-01-03 21:22:43 +000020 */
Simon Butcher15b15d12015-11-26 19:35:03 +000021
Paul Bakker5121ce52009-01-03 21:22:43 +000022/*
Simon Butcher15b15d12015-11-26 19:35:03 +000023 * The following sources were referenced in the design of this Multi-precision
24 * Integer library:
Paul Bakker5121ce52009-01-03 21:22:43 +000025 *
Simon Butcher15b15d12015-11-26 19:35:03 +000026 * [1] Handbook of Applied Cryptography - 1997
27 * Menezes, van Oorschot and Vanstone
28 *
29 * [2] Multi-Precision Math
30 * Tom St Denis
31 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
32 *
33 * [3] GNU Multi-Precision Arithmetic Library
34 * https://gmplib.org/manual/index.html
35 *
Simon Butcherf5ba0452015-12-27 23:01:55 +000036 */
Paul Bakker5121ce52009-01-03 21:22:43 +000037
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020038#if !defined(MBEDTLS_CONFIG_FILE)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000039#include "mbedtls/config.h"
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020040#else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020041#include MBEDTLS_CONFIG_FILE
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020042#endif
Paul Bakker5121ce52009-01-03 21:22:43 +000043
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020044#if defined(MBEDTLS_BIGNUM_C)
Paul Bakker5121ce52009-01-03 21:22:43 +000045
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000046#include "mbedtls/bignum.h"
47#include "mbedtls/bn_mul.h"
Paul Bakker5121ce52009-01-03 21:22:43 +000048
Rich Evans00ab4702015-02-06 13:43:58 +000049#include <string.h>
50
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020051#if defined(MBEDTLS_PLATFORM_C)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000052#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020053#else
Rich Evans00ab4702015-02-06 13:43:58 +000054#include <stdio.h>
55#include <stdlib.h>
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020056#define mbedtls_printf printf
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +020057#define mbedtls_calloc calloc
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020058#define mbedtls_free free
Paul Bakker6e339b52013-07-03 13:37:05 +020059#endif
60
Paul Bakker34617722014-06-13 17:20:13 +020061/* Implementation that should never be optimized out by the compiler */
Alexey Skalozube17a8da2016-01-13 17:19:33 +020062static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n ) {
Alexey Skalozub3d53f412016-01-13 16:53:40 +020063 volatile mbedtls_mpi_uint *p = v; while( n-- ) *p++ = 0;
Paul Bakker34617722014-06-13 17:20:13 +020064}
65
Hanno Becker88807112017-10-18 12:41:30 +010066/* Implementation that should never be optimized out by the compiler */
67static void mbedtls_zeroize( void *v, size_t n ) {
68 volatile unsigned char *p = v; while( n-- ) *p++ = 0;
69}
70
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020071#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
Paul Bakker5121ce52009-01-03 21:22:43 +000072#define biL (ciL << 3) /* bits in limb */
73#define biH (ciL << 2) /* half limb size */
74
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +010075#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
76
Paul Bakker5121ce52009-01-03 21:22:43 +000077/*
78 * Convert between bits/chars and number of limbs
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020079 * Divide first in order to avoid potential overflows
Paul Bakker5121ce52009-01-03 21:22:43 +000080 */
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020081#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
82#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
Paul Bakker5121ce52009-01-03 21:22:43 +000083
84/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000085 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000086 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020087void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000088{
Paul Bakker6c591fa2011-05-05 11:49:20 +000089 if( X == NULL )
90 return;
Paul Bakker5121ce52009-01-03 21:22:43 +000091
Paul Bakker6c591fa2011-05-05 11:49:20 +000092 X->s = 1;
93 X->n = 0;
94 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +000095}
96
97/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000098 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000099 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200100void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000101{
Paul Bakker6c591fa2011-05-05 11:49:20 +0000102 if( X == NULL )
103 return;
Paul Bakker5121ce52009-01-03 21:22:43 +0000104
Paul Bakker6c591fa2011-05-05 11:49:20 +0000105 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +0000106 {
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200107 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200108 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000109 }
110
Paul Bakker6c591fa2011-05-05 11:49:20 +0000111 X->s = 1;
112 X->n = 0;
113 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000114}
115
116/*
117 * Enlarge to the specified number of limbs
118 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200119int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000120{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200121 mbedtls_mpi_uint *p;
Paul Bakker5121ce52009-01-03 21:22:43 +0000122
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200123 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200124 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000125
Paul Bakker5121ce52009-01-03 21:22:43 +0000126 if( X->n < nblimbs )
127 {
Simon Butcher29176892016-05-20 00:19:09 +0100128 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200129 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000130
Paul Bakker5121ce52009-01-03 21:22:43 +0000131 if( X->p != NULL )
132 {
133 memcpy( p, X->p, X->n * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200134 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200135 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000136 }
137
138 X->n = nblimbs;
139 X->p = p;
140 }
141
142 return( 0 );
143}
144
145/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100146 * Resize down as much as possible,
147 * while keeping at least the specified number of limbs
148 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200149int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100150{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200151 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100152 size_t i;
153
154 /* Actually resize up in this case */
155 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200156 return( mbedtls_mpi_grow( X, nblimbs ) );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100157
158 for( i = X->n - 1; i > 0; i-- )
159 if( X->p[i] != 0 )
160 break;
161 i++;
162
163 if( i < nblimbs )
164 i = nblimbs;
165
Simon Butcher29176892016-05-20 00:19:09 +0100166 if( ( p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200167 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100168
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100169 if( X->p != NULL )
170 {
171 memcpy( p, X->p, i * ciL );
Alexey Skalozube17a8da2016-01-13 17:19:33 +0200172 mbedtls_mpi_zeroize( X->p, X->n );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200173 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100174 }
175
176 X->n = i;
177 X->p = p;
178
179 return( 0 );
180}
181
182/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000183 * Copy the contents of Y into X
184 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200185int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000186{
Paul Bakker23986e52011-04-24 08:57:21 +0000187 int ret;
188 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000189
190 if( X == Y )
191 return( 0 );
192
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200193 if( Y->p == NULL )
194 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200195 mbedtls_mpi_free( X );
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200196 return( 0 );
197 }
198
Paul Bakker5121ce52009-01-03 21:22:43 +0000199 for( i = Y->n - 1; i > 0; i-- )
200 if( Y->p[i] != 0 )
201 break;
202 i++;
203
204 X->s = Y->s;
205
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200206 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000207
208 memset( X->p, 0, X->n * ciL );
209 memcpy( X->p, Y->p, i * ciL );
210
211cleanup:
212
213 return( ret );
214}
215
216/*
217 * Swap the contents of X and Y
218 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200219void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000220{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200221 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000222
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200223 memcpy( &T, X, sizeof( mbedtls_mpi ) );
224 memcpy( X, Y, sizeof( mbedtls_mpi ) );
225 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000226}
227
228/*
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100229 * Conditionally assign X = Y, without leaking information
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100230 * about whether the assignment was made or not.
231 * (Leaking information about the respective sizes of X and Y is ok however.)
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100232 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200233int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100234{
235 int ret = 0;
236 size_t i;
237
Pascal Junodb99183d2015-03-11 16:49:45 +0100238 /* make sure assign is 0 or 1 in a time-constant manner */
239 assign = (assign | (unsigned char)-assign) >> 7;
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100240
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200241 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100242
Paul Bakker66d5d072014-06-17 16:39:18 +0200243 X->s = X->s * ( 1 - assign ) + Y->s * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100244
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100245 for( i = 0; i < Y->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200246 X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100247
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100248 for( ; i < X->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200249 X->p[i] *= ( 1 - assign );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100250
251cleanup:
252 return( ret );
253}
254
255/*
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100256 * Conditionally swap X and Y, without leaking information
257 * about whether the swap was made or not.
258 * Here it is not ok to simply swap the pointers, which whould lead to
259 * different memory access patterns when X and Y are used afterwards.
260 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200261int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100262{
263 int ret, s;
264 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200265 mbedtls_mpi_uint tmp;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100266
267 if( X == Y )
268 return( 0 );
269
Pascal Junodb99183d2015-03-11 16:49:45 +0100270 /* make sure swap is 0 or 1 in a time-constant manner */
271 swap = (swap | (unsigned char)-swap) >> 7;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100272
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200273 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
274 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100275
276 s = X->s;
Paul Bakker66d5d072014-06-17 16:39:18 +0200277 X->s = X->s * ( 1 - swap ) + Y->s * swap;
278 Y->s = Y->s * ( 1 - swap ) + s * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100279
280
281 for( i = 0; i < X->n; i++ )
282 {
283 tmp = X->p[i];
Paul Bakker66d5d072014-06-17 16:39:18 +0200284 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
285 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100286 }
287
288cleanup:
289 return( ret );
290}
291
292/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000293 * Set value from integer
294 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200295int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000296{
297 int ret;
298
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200299 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000300 memset( X->p, 0, X->n * ciL );
301
302 X->p[0] = ( z < 0 ) ? -z : z;
303 X->s = ( z < 0 ) ? -1 : 1;
304
305cleanup:
306
307 return( ret );
308}
309
310/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000311 * Get a specific bit
312 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200313int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000314{
315 if( X->n * biL <= pos )
316 return( 0 );
317
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200318 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000319}
320
321/*
322 * Set a bit to a specific value of 0 or 1
323 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200324int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000325{
326 int ret = 0;
327 size_t off = pos / biL;
328 size_t idx = pos % biL;
329
330 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200331 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200332
Paul Bakker2f5947e2011-05-18 15:47:11 +0000333 if( X->n * biL <= pos )
334 {
335 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200336 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000337
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200338 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000339 }
340
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200341 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
342 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000343
344cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200345
Paul Bakker2f5947e2011-05-18 15:47:11 +0000346 return( ret );
347}
348
349/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200350 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000351 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200352size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000353{
Paul Bakker23986e52011-04-24 08:57:21 +0000354 size_t i, j, count = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000355
356 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000357 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000358 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
359 return( count );
360
361 return( 0 );
362}
363
364/*
Simon Butcher15b15d12015-11-26 19:35:03 +0000365 * Count leading zero bits in a given integer
366 */
367static size_t mbedtls_clz( const mbedtls_mpi_uint x )
368{
369 size_t j;
Manuel Pégourié-Gonnarde3e8edf2015-12-01 09:31:52 +0100370 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
Simon Butcher15b15d12015-11-26 19:35:03 +0000371
372 for( j = 0; j < biL; j++ )
373 {
374 if( x & mask ) break;
375
376 mask >>= 1;
377 }
378
379 return j;
380}
381
382/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200383 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000384 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200385size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000386{
Paul Bakker23986e52011-04-24 08:57:21 +0000387 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000388
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200389 if( X->n == 0 )
390 return( 0 );
391
Paul Bakker5121ce52009-01-03 21:22:43 +0000392 for( i = X->n - 1; i > 0; i-- )
393 if( X->p[i] != 0 )
394 break;
395
Simon Butcher15b15d12015-11-26 19:35:03 +0000396 j = biL - mbedtls_clz( X->p[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +0000397
Paul Bakker23986e52011-04-24 08:57:21 +0000398 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000399}
400
401/*
402 * Return the total size in bytes
403 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200404size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000405{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200406 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000407}
408
409/*
410 * Convert an ASCII character to digit value
411 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200412static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000413{
414 *d = 255;
415
416 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
417 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
418 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
419
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200420 if( *d >= (mbedtls_mpi_uint) radix )
421 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000422
423 return( 0 );
424}
425
426/*
427 * Import from an ASCII string
428 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200429int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000430{
Paul Bakker23986e52011-04-24 08:57:21 +0000431 int ret;
432 size_t i, j, slen, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200433 mbedtls_mpi_uint d;
434 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000435
436 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200437 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000438
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200439 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000440
Paul Bakkerff60ee62010-03-16 21:09:09 +0000441 slen = strlen( s );
442
Paul Bakker5121ce52009-01-03 21:22:43 +0000443 if( radix == 16 )
444 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100445 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200446 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
447
Paul Bakkerff60ee62010-03-16 21:09:09 +0000448 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000449
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200450 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
451 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000452
Paul Bakker23986e52011-04-24 08:57:21 +0000453 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000454 {
Paul Bakker23986e52011-04-24 08:57:21 +0000455 if( i == 1 && s[i - 1] == '-' )
Paul Bakker5121ce52009-01-03 21:22:43 +0000456 {
457 X->s = -1;
458 break;
459 }
460
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200461 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200462 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000463 }
464 }
465 else
466 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200467 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000468
Paul Bakkerff60ee62010-03-16 21:09:09 +0000469 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000470 {
471 if( i == 0 && s[i] == '-' )
472 {
473 X->s = -1;
474 continue;
475 }
476
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200477 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
478 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000479
480 if( X->s == 1 )
481 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200482 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000483 }
484 else
485 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200486 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000487 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000488 }
489 }
490
491cleanup:
492
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200493 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000494
495 return( ret );
496}
497
498/*
499 * Helper to write the digits high-order first
500 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200501static int mpi_write_hlp( mbedtls_mpi *X, int radix, char **p )
Paul Bakker5121ce52009-01-03 21:22:43 +0000502{
503 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200504 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +0000505
506 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200507 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000508
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200509 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
510 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000511
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200512 if( mbedtls_mpi_cmp_int( X, 0 ) != 0 )
513 MBEDTLS_MPI_CHK( mpi_write_hlp( X, radix, p ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000514
515 if( r < 10 )
516 *(*p)++ = (char)( r + 0x30 );
517 else
518 *(*p)++ = (char)( r + 0x37 );
519
520cleanup:
521
522 return( ret );
523}
524
525/*
526 * Export into an ASCII string
527 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100528int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
529 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000530{
Paul Bakker23986e52011-04-24 08:57:21 +0000531 int ret = 0;
532 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000533 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200534 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000535
536 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200537 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000538
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200539 n = mbedtls_mpi_bitlen( X );
Paul Bakker5121ce52009-01-03 21:22:43 +0000540 if( radix >= 4 ) n >>= 1;
541 if( radix >= 16 ) n >>= 1;
Andres AGd1cc7f62017-01-06 13:17:35 +0000542 /*
543 * Round up the buffer length to an even value to ensure that there is
544 * enough room for hexadecimal values that can be represented in an odd
545 * number of digits.
546 */
547 n += 3 + ( ( n + 1 ) & 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000548
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100549 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000550 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100551 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200552 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000553 }
554
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100555 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200556 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000557
558 if( X->s == -1 )
559 *p++ = '-';
560
561 if( radix == 16 )
562 {
Paul Bakker23986e52011-04-24 08:57:21 +0000563 int c;
564 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000565
Paul Bakker23986e52011-04-24 08:57:21 +0000566 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000567 {
Paul Bakker23986e52011-04-24 08:57:21 +0000568 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000569 {
Paul Bakker23986e52011-04-24 08:57:21 +0000570 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000571
Paul Bakker6c343d72014-07-10 14:36:19 +0200572 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000573 continue;
574
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000575 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000576 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000577 k = 1;
578 }
579 }
580 }
581 else
582 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200583 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000584
585 if( T.s == -1 )
586 T.s = 1;
587
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200588 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000589 }
590
591 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100592 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000593
594cleanup:
595
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200596 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000597
598 return( ret );
599}
600
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200601#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000602/*
603 * Read X from an opened file
604 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200605int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000606{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200607 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000608 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000609 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000610 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000611 * Buffer should have space for (short) label and decimal formatted MPI,
612 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000613 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200614 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000615
616 memset( s, 0, sizeof( s ) );
617 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200618 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000619
620 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000621 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200622 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000623
Hanno Beckerb2034b72017-04-26 11:46:46 +0100624 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
625 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
Paul Bakker5121ce52009-01-03 21:22:43 +0000626
627 p = s + slen;
Hanno Beckerb2034b72017-04-26 11:46:46 +0100628 while( p-- > s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000629 if( mpi_get_digit( &d, radix, *p ) != 0 )
630 break;
631
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200632 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000633}
634
635/*
636 * Write X into an opened file (or stdout if fout == NULL)
637 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200638int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000639{
Paul Bakker23986e52011-04-24 08:57:21 +0000640 int ret;
641 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000642 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000643 * Buffer should have space for (short) label and decimal formatted MPI,
644 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000645 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200646 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000647
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100648 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000649
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100650 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000651
652 if( p == NULL ) p = "";
653
654 plen = strlen( p );
655 slen = strlen( s );
656 s[slen++] = '\r';
657 s[slen++] = '\n';
658
659 if( fout != NULL )
660 {
661 if( fwrite( p, 1, plen, fout ) != plen ||
662 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200663 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000664 }
665 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200666 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000667
668cleanup:
669
670 return( ret );
671}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200672#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000673
674/*
675 * Import X from unsigned binary data, big endian
676 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200677int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000678{
Paul Bakker23986e52011-04-24 08:57:21 +0000679 int ret;
Hanno Becker073c1992017-10-17 15:17:27 +0100680 size_t i, j;
681 size_t const limbs = CHARS_TO_LIMBS( buflen );
Paul Bakker5121ce52009-01-03 21:22:43 +0000682
Hanno Becker073c1992017-10-17 15:17:27 +0100683 /* Ensure that target MPI has exactly the necessary number of limbs */
684 if( X->n != limbs )
685 {
686 mbedtls_mpi_free( X );
687 mbedtls_mpi_init( X );
688 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
689 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000690
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200691 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000692
Hanno Becker073c1992017-10-17 15:17:27 +0100693 for( i = buflen, j = 0; i > 0; i--, j++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200694 X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
Paul Bakker5121ce52009-01-03 21:22:43 +0000695
696cleanup:
697
698 return( ret );
699}
700
701/*
702 * Export X into unsigned binary data, big endian
703 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200704int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000705{
Paul Bakker23986e52011-04-24 08:57:21 +0000706 size_t i, j, n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000707
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200708 n = mbedtls_mpi_size( X );
Paul Bakker5121ce52009-01-03 21:22:43 +0000709
710 if( buflen < n )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200711 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000712
713 memset( buf, 0, buflen );
714
715 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
716 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
717
718 return( 0 );
719}
720
721/*
722 * Left-shift: X <<= count
723 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200724int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000725{
Paul Bakker23986e52011-04-24 08:57:21 +0000726 int ret;
727 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200728 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000729
730 v0 = count / (biL );
731 t1 = count & (biL - 1);
732
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200733 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000734
Paul Bakkerf9688572011-05-05 10:00:45 +0000735 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200736 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000737
738 ret = 0;
739
740 /*
741 * shift by count / limb_size
742 */
743 if( v0 > 0 )
744 {
Paul Bakker23986e52011-04-24 08:57:21 +0000745 for( i = X->n; i > v0; i-- )
746 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000747
Paul Bakker23986e52011-04-24 08:57:21 +0000748 for( ; i > 0; i-- )
749 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000750 }
751
752 /*
753 * shift by count % limb_size
754 */
755 if( t1 > 0 )
756 {
757 for( i = v0; i < X->n; i++ )
758 {
759 r1 = X->p[i] >> (biL - t1);
760 X->p[i] <<= t1;
761 X->p[i] |= r0;
762 r0 = r1;
763 }
764 }
765
766cleanup:
767
768 return( ret );
769}
770
771/*
772 * Right-shift: X >>= count
773 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200774int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000775{
Paul Bakker23986e52011-04-24 08:57:21 +0000776 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200777 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000778
779 v0 = count / biL;
780 v1 = count & (biL - 1);
781
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100782 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200783 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100784
Paul Bakker5121ce52009-01-03 21:22:43 +0000785 /*
786 * shift by count / limb_size
787 */
788 if( v0 > 0 )
789 {
790 for( i = 0; i < X->n - v0; i++ )
791 X->p[i] = X->p[i + v0];
792
793 for( ; i < X->n; i++ )
794 X->p[i] = 0;
795 }
796
797 /*
798 * shift by count % limb_size
799 */
800 if( v1 > 0 )
801 {
Paul Bakker23986e52011-04-24 08:57:21 +0000802 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000803 {
Paul Bakker23986e52011-04-24 08:57:21 +0000804 r1 = X->p[i - 1] << (biL - v1);
805 X->p[i - 1] >>= v1;
806 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000807 r0 = r1;
808 }
809 }
810
811 return( 0 );
812}
813
814/*
815 * Compare unsigned values
816 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200817int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000818{
Paul Bakker23986e52011-04-24 08:57:21 +0000819 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000820
Paul Bakker23986e52011-04-24 08:57:21 +0000821 for( i = X->n; i > 0; i-- )
822 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000823 break;
824
Paul Bakker23986e52011-04-24 08:57:21 +0000825 for( j = Y->n; j > 0; j-- )
826 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000827 break;
828
Paul Bakker23986e52011-04-24 08:57:21 +0000829 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000830 return( 0 );
831
832 if( i > j ) return( 1 );
833 if( j > i ) return( -1 );
834
Paul Bakker23986e52011-04-24 08:57:21 +0000835 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000836 {
Paul Bakker23986e52011-04-24 08:57:21 +0000837 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
838 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000839 }
840
841 return( 0 );
842}
843
844/*
845 * Compare signed values
846 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200847int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000848{
Paul Bakker23986e52011-04-24 08:57:21 +0000849 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000850
Paul Bakker23986e52011-04-24 08:57:21 +0000851 for( i = X->n; i > 0; i-- )
852 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000853 break;
854
Paul Bakker23986e52011-04-24 08:57:21 +0000855 for( j = Y->n; j > 0; j-- )
856 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000857 break;
858
Paul Bakker23986e52011-04-24 08:57:21 +0000859 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000860 return( 0 );
861
862 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +0000863 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000864
865 if( X->s > 0 && Y->s < 0 ) return( 1 );
866 if( Y->s > 0 && X->s < 0 ) return( -1 );
867
Paul Bakker23986e52011-04-24 08:57:21 +0000868 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000869 {
Paul Bakker23986e52011-04-24 08:57:21 +0000870 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
871 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000872 }
873
874 return( 0 );
875}
876
877/*
878 * Compare signed values
879 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200880int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000881{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200882 mbedtls_mpi Y;
883 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000884
885 *p = ( z < 0 ) ? -z : z;
886 Y.s = ( z < 0 ) ? -1 : 1;
887 Y.n = 1;
888 Y.p = p;
889
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200890 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000891}
892
893/*
894 * Unsigned addition: X = |A| + |B| (HAC 14.7)
895 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200896int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000897{
Paul Bakker23986e52011-04-24 08:57:21 +0000898 int ret;
899 size_t i, j;
Janos Follath6c922682015-10-30 17:43:11 +0100900 mbedtls_mpi_uint *o, *p, c, tmp;
Paul Bakker5121ce52009-01-03 21:22:43 +0000901
902 if( X == B )
903 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200904 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000905 }
906
907 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200908 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +0200909
Paul Bakkerf7ca7b92009-06-20 10:31:06 +0000910 /*
911 * X should always be positive as a result of unsigned additions.
912 */
913 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000914
Paul Bakker23986e52011-04-24 08:57:21 +0000915 for( j = B->n; j > 0; j-- )
916 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000917 break;
918
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200919 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000920
921 o = B->p; p = X->p; c = 0;
922
Janos Follath6c922682015-10-30 17:43:11 +0100923 /*
924 * tmp is used because it might happen that p == o
925 */
Paul Bakker23986e52011-04-24 08:57:21 +0000926 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000927 {
Janos Follath6c922682015-10-30 17:43:11 +0100928 tmp= *o;
Paul Bakker5121ce52009-01-03 21:22:43 +0000929 *p += c; c = ( *p < c );
Janos Follath6c922682015-10-30 17:43:11 +0100930 *p += tmp; c += ( *p < tmp );
Paul Bakker5121ce52009-01-03 21:22:43 +0000931 }
932
933 while( c != 0 )
934 {
935 if( i >= X->n )
936 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200937 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000938 p = X->p + i;
939 }
940
Paul Bakker2d319fd2012-09-16 21:34:26 +0000941 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +0000942 }
943
944cleanup:
945
946 return( ret );
947}
948
949/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200950 * Helper for mbedtls_mpi subtraction
Paul Bakker5121ce52009-01-03 21:22:43 +0000951 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200952static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d )
Paul Bakker5121ce52009-01-03 21:22:43 +0000953{
Paul Bakker23986e52011-04-24 08:57:21 +0000954 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200955 mbedtls_mpi_uint c, z;
Paul Bakker5121ce52009-01-03 21:22:43 +0000956
957 for( i = c = 0; i < n; i++, s++, d++ )
958 {
959 z = ( *d < c ); *d -= c;
960 c = ( *d < *s ) + z; *d -= *s;
961 }
962
963 while( c != 0 )
964 {
965 z = ( *d < c ); *d -= c;
966 c = z; i++; d++;
967 }
968}
969
970/*
Paul Bakker60b1d102013-10-29 10:02:51 +0100971 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
Paul Bakker5121ce52009-01-03 21:22:43 +0000972 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200973int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000974{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200975 mbedtls_mpi TB;
Paul Bakker23986e52011-04-24 08:57:21 +0000976 int ret;
977 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000978
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200979 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
980 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +0000981
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200982 mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +0000983
984 if( X == B )
985 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200986 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000987 B = &TB;
988 }
989
990 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200991 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000992
Paul Bakker1ef7a532009-06-20 10:50:55 +0000993 /*
Paul Bakker60b1d102013-10-29 10:02:51 +0100994 * X should always be positive as a result of unsigned subtractions.
Paul Bakker1ef7a532009-06-20 10:50:55 +0000995 */
996 X->s = 1;
997
Paul Bakker5121ce52009-01-03 21:22:43 +0000998 ret = 0;
999
Paul Bakker23986e52011-04-24 08:57:21 +00001000 for( n = B->n; n > 0; n-- )
1001 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001002 break;
1003
Paul Bakker23986e52011-04-24 08:57:21 +00001004 mpi_sub_hlp( n, B->p, X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +00001005
1006cleanup:
1007
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001008 mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001009
1010 return( ret );
1011}
1012
1013/*
1014 * Signed addition: X = A + B
1015 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001016int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001017{
1018 int ret, s = A->s;
1019
1020 if( A->s * B->s < 0 )
1021 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001022 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001023 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001024 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001025 X->s = s;
1026 }
1027 else
1028 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001029 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001030 X->s = -s;
1031 }
1032 }
1033 else
1034 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001035 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001036 X->s = s;
1037 }
1038
1039cleanup:
1040
1041 return( ret );
1042}
1043
1044/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001045 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001046 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001047int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001048{
1049 int ret, s = A->s;
1050
1051 if( A->s * B->s > 0 )
1052 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001053 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001054 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001055 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001056 X->s = s;
1057 }
1058 else
1059 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001060 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001061 X->s = -s;
1062 }
1063 }
1064 else
1065 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001066 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001067 X->s = s;
1068 }
1069
1070cleanup:
1071
1072 return( ret );
1073}
1074
1075/*
1076 * Signed addition: X = A + b
1077 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001078int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001079{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001080 mbedtls_mpi _B;
1081 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001082
1083 p[0] = ( b < 0 ) ? -b : b;
1084 _B.s = ( b < 0 ) ? -1 : 1;
1085 _B.n = 1;
1086 _B.p = p;
1087
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001088 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001089}
1090
1091/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001092 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001093 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001094int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001095{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001096 mbedtls_mpi _B;
1097 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001098
1099 p[0] = ( b < 0 ) ? -b : b;
1100 _B.s = ( b < 0 ) ? -1 : 1;
1101 _B.n = 1;
1102 _B.p = p;
1103
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001104 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001105}
1106
1107/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001108 * Helper for mbedtls_mpi multiplication
Paul Bakkerfc4f46f2013-06-24 19:23:56 +02001109 */
1110static
1111#if defined(__APPLE__) && defined(__arm__)
1112/*
1113 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1114 * appears to need this to prevent bad ARM code generation at -O3.
1115 */
1116__attribute__ ((noinline))
1117#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001118void 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 +00001119{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001120 mbedtls_mpi_uint c = 0, t = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001121
1122#if defined(MULADDC_HUIT)
1123 for( ; i >= 8; i -= 8 )
1124 {
1125 MULADDC_INIT
1126 MULADDC_HUIT
1127 MULADDC_STOP
1128 }
1129
1130 for( ; i > 0; i-- )
1131 {
1132 MULADDC_INIT
1133 MULADDC_CORE
1134 MULADDC_STOP
1135 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001136#else /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001137 for( ; i >= 16; i -= 16 )
1138 {
1139 MULADDC_INIT
1140 MULADDC_CORE MULADDC_CORE
1141 MULADDC_CORE MULADDC_CORE
1142 MULADDC_CORE MULADDC_CORE
1143 MULADDC_CORE MULADDC_CORE
1144
1145 MULADDC_CORE MULADDC_CORE
1146 MULADDC_CORE MULADDC_CORE
1147 MULADDC_CORE MULADDC_CORE
1148 MULADDC_CORE MULADDC_CORE
1149 MULADDC_STOP
1150 }
1151
1152 for( ; i >= 8; i -= 8 )
1153 {
1154 MULADDC_INIT
1155 MULADDC_CORE MULADDC_CORE
1156 MULADDC_CORE MULADDC_CORE
1157
1158 MULADDC_CORE MULADDC_CORE
1159 MULADDC_CORE MULADDC_CORE
1160 MULADDC_STOP
1161 }
1162
1163 for( ; i > 0; i-- )
1164 {
1165 MULADDC_INIT
1166 MULADDC_CORE
1167 MULADDC_STOP
1168 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001169#endif /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001170
1171 t++;
1172
1173 do {
1174 *d += c; c = ( *d < c ); d++;
1175 }
1176 while( c != 0 );
1177}
1178
1179/*
1180 * Baseline multiplication: X = A * B (HAC 14.12)
1181 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001182int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001183{
Paul Bakker23986e52011-04-24 08:57:21 +00001184 int ret;
1185 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001186 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001187
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001188 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001189
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001190 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1191 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001192
Paul Bakker23986e52011-04-24 08:57:21 +00001193 for( i = A->n; i > 0; i-- )
1194 if( A->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001195 break;
1196
Paul Bakker23986e52011-04-24 08:57:21 +00001197 for( j = B->n; j > 0; j-- )
1198 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001199 break;
1200
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001201 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1202 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001203
Paul Bakker23986e52011-04-24 08:57:21 +00001204 for( i++; j > 0; j-- )
1205 mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001206
1207 X->s = A->s * B->s;
1208
1209cleanup:
1210
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001211 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001212
1213 return( ret );
1214}
1215
1216/*
1217 * Baseline multiplication: X = A * b
1218 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001219int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001220{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001221 mbedtls_mpi _B;
1222 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001223
1224 _B.s = 1;
1225 _B.n = 1;
1226 _B.p = p;
1227 p[0] = b;
1228
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001229 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001230}
1231
1232/*
Simon Butcherf5ba0452015-12-27 23:01:55 +00001233 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1234 * mbedtls_mpi_uint divisor, d
Simon Butcher15b15d12015-11-26 19:35:03 +00001235 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001236static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1237 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
Simon Butcher15b15d12015-11-26 19:35:03 +00001238{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001239#if defined(MBEDTLS_HAVE_UDBL)
1240 mbedtls_t_udbl dividend, quotient;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001241#else
Simon Butcher9803d072016-01-03 00:24:34 +00001242 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1243 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
Simon Butcherf5ba0452015-12-27 23:01:55 +00001244 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1245 mbedtls_mpi_uint u0_msw, u0_lsw;
Simon Butcher9803d072016-01-03 00:24:34 +00001246 size_t s;
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001247#endif
1248
Simon Butcher15b15d12015-11-26 19:35:03 +00001249 /*
1250 * Check for overflow
1251 */
Simon Butcherf5ba0452015-12-27 23:01:55 +00001252 if( 0 == d || u1 >= d )
Simon Butcher15b15d12015-11-26 19:35:03 +00001253 {
Simon Butcherf5ba0452015-12-27 23:01:55 +00001254 if (r != NULL) *r = ~0;
Simon Butcher15b15d12015-11-26 19:35:03 +00001255
Simon Butcherf5ba0452015-12-27 23:01:55 +00001256 return ( ~0 );
Simon Butcher15b15d12015-11-26 19:35:03 +00001257 }
1258
1259#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001260 dividend = (mbedtls_t_udbl) u1 << biL;
1261 dividend |= (mbedtls_t_udbl) u0;
1262 quotient = dividend / d;
1263 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1264 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1265
1266 if( r != NULL )
Simon Butcher9803d072016-01-03 00:24:34 +00001267 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001268
1269 return (mbedtls_mpi_uint) quotient;
1270#else
Simon Butcher15b15d12015-11-26 19:35:03 +00001271
1272 /*
1273 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1274 * Vol. 2 - Seminumerical Algorithms, Knuth
1275 */
1276
1277 /*
1278 * Normalize the divisor, d, and dividend, u0, u1
1279 */
1280 s = mbedtls_clz( d );
1281 d = d << s;
1282
1283 u1 = u1 << s;
Simon Butcher9803d072016-01-03 00:24:34 +00001284 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
Simon Butcher15b15d12015-11-26 19:35:03 +00001285 u0 = u0 << s;
1286
1287 d1 = d >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001288 d0 = d & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001289
1290 u0_msw = u0 >> biH;
Simon Butcher9803d072016-01-03 00:24:34 +00001291 u0_lsw = u0 & uint_halfword_mask;
Simon Butcher15b15d12015-11-26 19:35:03 +00001292
1293 /*
1294 * Find the first quotient and remainder
1295 */
1296 q1 = u1 / d1;
1297 r0 = u1 - d1 * q1;
1298
1299 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1300 {
1301 q1 -= 1;
1302 r0 += d1;
1303
1304 if ( r0 >= radix ) break;
1305 }
1306
Simon Butcherf5ba0452015-12-27 23:01:55 +00001307 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
Simon Butcher15b15d12015-11-26 19:35:03 +00001308 q0 = rAX / d1;
1309 r0 = rAX - q0 * d1;
1310
1311 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1312 {
1313 q0 -= 1;
1314 r0 += d1;
1315
1316 if ( r0 >= radix ) break;
1317 }
1318
1319 if (r != NULL)
Simon Butcherf5ba0452015-12-27 23:01:55 +00001320 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
Simon Butcher15b15d12015-11-26 19:35:03 +00001321
1322 quotient = q1 * radix + q0;
1323
1324 return quotient;
1325#endif
1326}
1327
1328/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001329 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001330 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001331int 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 +00001332{
Paul Bakker23986e52011-04-24 08:57:21 +00001333 int ret;
1334 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001335 mbedtls_mpi X, Y, Z, T1, T2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001336
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001337 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1338 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001339
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001340 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1341 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001342
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001343 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001344 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001345 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1346 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001347 return( 0 );
1348 }
1349
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001350 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1351 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001352 X.s = Y.s = 1;
1353
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001354 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1355 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1356 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1357 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001358
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001359 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001360 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001361 {
1362 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001363 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1364 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001365 }
1366 else k = 0;
1367
1368 n = X.n - 1;
1369 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001370 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001371
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001372 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001373 {
1374 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001375 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001376 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001377 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001378
1379 for( i = n; i > t ; i-- )
1380 {
1381 if( X.p[i] >= Y.p[t] )
1382 Z.p[i - t - 1] = ~0;
1383 else
1384 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001385 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1386 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001387 }
1388
1389 Z.p[i - t - 1]++;
1390 do
1391 {
1392 Z.p[i - t - 1]--;
1393
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001394 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001395 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001396 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001397 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001398
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001399 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001400 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1401 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001402 T2.p[2] = X.p[i];
1403 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001404 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001405
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001406 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1407 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1408 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001409
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001410 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001411 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001412 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1413 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1414 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001415 Z.p[i - t - 1]--;
1416 }
1417 }
1418
1419 if( Q != NULL )
1420 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001421 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001422 Q->s = A->s * B->s;
1423 }
1424
1425 if( R != NULL )
1426 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001427 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001428 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001429 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001430
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001431 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001432 R->s = 1;
1433 }
1434
1435cleanup:
1436
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001437 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1438 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001439
1440 return( ret );
1441}
1442
1443/*
1444 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001445 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001446int 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 +00001447{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001448 mbedtls_mpi _B;
1449 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001450
1451 p[0] = ( b < 0 ) ? -b : b;
1452 _B.s = ( b < 0 ) ? -1 : 1;
1453 _B.n = 1;
1454 _B.p = p;
1455
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001456 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001457}
1458
1459/*
1460 * Modulo: R = A mod B
1461 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001462int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001463{
1464 int ret;
1465
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001466 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1467 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001468
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001469 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001470
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001471 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1472 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001473
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001474 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1475 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001476
1477cleanup:
1478
1479 return( ret );
1480}
1481
1482/*
1483 * Modulo: r = A mod b
1484 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001485int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001486{
Paul Bakker23986e52011-04-24 08:57:21 +00001487 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001488 mbedtls_mpi_uint x, y, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001489
1490 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001491 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001492
1493 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001494 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001495
1496 /*
1497 * handle trivial cases
1498 */
1499 if( b == 1 )
1500 {
1501 *r = 0;
1502 return( 0 );
1503 }
1504
1505 if( b == 2 )
1506 {
1507 *r = A->p[0] & 1;
1508 return( 0 );
1509 }
1510
1511 /*
1512 * general case
1513 */
Paul Bakker23986e52011-04-24 08:57:21 +00001514 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001515 {
Paul Bakker23986e52011-04-24 08:57:21 +00001516 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001517 y = ( y << biH ) | ( x >> biH );
1518 z = y / b;
1519 y -= z * b;
1520
1521 x <<= biH;
1522 y = ( y << biH ) | ( x >> biH );
1523 z = y / b;
1524 y -= z * b;
1525 }
1526
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001527 /*
1528 * If A is negative, then the current y represents a negative value.
1529 * Flipping it to the positive side.
1530 */
1531 if( A->s < 0 && y != 0 )
1532 y = b - y;
1533
Paul Bakker5121ce52009-01-03 21:22:43 +00001534 *r = y;
1535
1536 return( 0 );
1537}
1538
1539/*
1540 * Fast Montgomery initialization (thanks to Tom St Denis)
1541 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001542static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001543{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001544 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001545 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00001546
1547 x = m0;
1548 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001549
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001550 for( i = biL; i >= 8; i /= 2 )
1551 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001552
1553 *mm = ~x + 1;
1554}
1555
1556/*
1557 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1558 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001559static int mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001560 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001561{
Paul Bakker23986e52011-04-24 08:57:21 +00001562 size_t i, n, m;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001563 mbedtls_mpi_uint u0, u1, *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00001564
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001565 if( T->n < N->n + 1 || T->p == NULL )
1566 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1567
Paul Bakker5121ce52009-01-03 21:22:43 +00001568 memset( T->p, 0, T->n * ciL );
1569
1570 d = T->p;
1571 n = N->n;
1572 m = ( B->n < n ) ? B->n : n;
1573
1574 for( i = 0; i < n; i++ )
1575 {
1576 /*
1577 * T = (T + u0*B + u1*N) / 2^biL
1578 */
1579 u0 = A->p[i];
1580 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1581
1582 mpi_mul_hlp( m, B->p, d, u0 );
1583 mpi_mul_hlp( n, N->p, d, u1 );
1584
1585 *d++ = u0; d[n + 1] = 0;
1586 }
1587
Paul Bakker66d5d072014-06-17 16:39:18 +02001588 memcpy( A->p, d, ( n + 1 ) * ciL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001589
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001590 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001591 mpi_sub_hlp( n, N->p, A->p );
1592 else
1593 /* prevent timing attacks */
1594 mpi_sub_hlp( n, A->p, T->p );
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001595
1596 return( 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001597}
1598
1599/*
1600 * Montgomery reduction: A = A * R^-1 mod N
1601 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001602static int mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001603{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001604 mbedtls_mpi_uint z = 1;
1605 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001606
Paul Bakker8ddb6452013-02-27 14:56:33 +01001607 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001608 U.p = &z;
1609
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001610 return( mpi_montmul( A, &U, N, mm, T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001611}
1612
1613/*
1614 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1615 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001616int 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 +00001617{
Paul Bakker23986e52011-04-24 08:57:21 +00001618 int ret;
1619 size_t wbits, wsize, one = 1;
1620 size_t i, j, nblimbs;
1621 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001622 mbedtls_mpi_uint ei, mm, state;
1623 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00001624 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001625
Hanno Becker930ec7d2018-03-09 10:48:00 +00001626 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001627 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001628
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001629 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1630 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001631
1632 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001633 * Init temps and window size
1634 */
1635 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001636 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
1637 mbedtls_mpi_init( &Apos );
Paul Bakker5121ce52009-01-03 21:22:43 +00001638 memset( W, 0, sizeof( W ) );
1639
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001640 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00001641
1642 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1643 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1644
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001645 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1646 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Paul Bakkerb6d5f082011-11-25 11:52:11 +00001647
Paul Bakker5121ce52009-01-03 21:22:43 +00001648 j = N->n + 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001649 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1650 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1651 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001652
1653 /*
Paul Bakker50546922012-05-19 08:40:49 +00001654 * Compensate for negative A (and correct at the end)
1655 */
1656 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00001657 if( neg )
1658 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001659 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00001660 Apos.s = 1;
1661 A = &Apos;
1662 }
1663
1664 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001665 * If 1st call, pre-compute R^2 mod N
1666 */
1667 if( _RR == NULL || _RR->p == NULL )
1668 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001669 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1670 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1671 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001672
1673 if( _RR != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001674 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001675 }
1676 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001677 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001678
1679 /*
1680 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1681 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001682 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
1683 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Paul Bakkerc2024f42014-01-23 20:38:35 +01001684 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001685 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001686
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001687 MBEDTLS_MPI_CHK( mpi_montmul( &W[1], &RR, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001688
1689 /*
1690 * X = R^2 * R^-1 mod N = R mod N
1691 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001692 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001693 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001694
1695 if( wsize > 1 )
1696 {
1697 /*
1698 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1699 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001700 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001701
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001702 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1703 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001704
1705 for( i = 0; i < wsize - 1; i++ )
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001706 MBEDTLS_MPI_CHK( mpi_montmul( &W[j], &W[j], N, mm, &T ) );
Paul Bakker0d7702c2013-10-29 16:18:35 +01001707
Paul Bakker5121ce52009-01-03 21:22:43 +00001708 /*
1709 * W[i] = W[i - 1] * W[1]
1710 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001711 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001712 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001713 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1714 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001715
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001716 MBEDTLS_MPI_CHK( mpi_montmul( &W[i], &W[1], N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001717 }
1718 }
1719
1720 nblimbs = E->n;
1721 bufsize = 0;
1722 nbits = 0;
1723 wbits = 0;
1724 state = 0;
1725
1726 while( 1 )
1727 {
1728 if( bufsize == 0 )
1729 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01001730 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001731 break;
1732
Paul Bakker0d7702c2013-10-29 16:18:35 +01001733 nblimbs--;
1734
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001735 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00001736 }
1737
1738 bufsize--;
1739
1740 ei = (E->p[nblimbs] >> bufsize) & 1;
1741
1742 /*
1743 * skip leading 0s
1744 */
1745 if( ei == 0 && state == 0 )
1746 continue;
1747
1748 if( ei == 0 && state == 1 )
1749 {
1750 /*
1751 * out of window, square X
1752 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001753 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001754 continue;
1755 }
1756
1757 /*
1758 * add ei to current window
1759 */
1760 state = 2;
1761
1762 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02001763 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001764
1765 if( nbits == wsize )
1766 {
1767 /*
1768 * X = X^wsize R^-1 mod N
1769 */
1770 for( i = 0; i < wsize; i++ )
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001771 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001772
1773 /*
1774 * X = X * W[wbits] R^-1 mod N
1775 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001776 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[wbits], N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001777
1778 state--;
1779 nbits = 0;
1780 wbits = 0;
1781 }
1782 }
1783
1784 /*
1785 * process the remaining bits
1786 */
1787 for( i = 0; i < nbits; i++ )
1788 {
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001789 MBEDTLS_MPI_CHK( mpi_montmul( X, X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001790
1791 wbits <<= 1;
1792
Paul Bakker66d5d072014-06-17 16:39:18 +02001793 if( ( wbits & ( one << wsize ) ) != 0 )
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001794 MBEDTLS_MPI_CHK( mpi_montmul( X, &W[1], N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001795 }
1796
1797 /*
1798 * X = A^E * R * R^-1 mod N = A^E mod N
1799 */
Nicholas Wilson91c68a52016-04-13 11:44:29 +01001800 MBEDTLS_MPI_CHK( mpi_montred( X, N, mm, &T ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001801
Hanno Beckera4af1c42017-04-18 09:07:45 +01001802 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
Paul Bakkerf6198c12012-05-16 08:02:29 +00001803 {
1804 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001805 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001806 }
1807
Paul Bakker5121ce52009-01-03 21:22:43 +00001808cleanup:
1809
Paul Bakker66d5d072014-06-17 16:39:18 +02001810 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001811 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001812
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001813 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Paul Bakker6c591fa2011-05-05 11:49:20 +00001814
Paul Bakker75a28602014-03-31 12:08:17 +02001815 if( _RR == NULL || _RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001816 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00001817
1818 return( ret );
1819}
1820
Paul Bakker5121ce52009-01-03 21:22:43 +00001821/*
1822 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1823 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001824int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001825{
Paul Bakker23986e52011-04-24 08:57:21 +00001826 int ret;
1827 size_t lz, lzt;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001828 mbedtls_mpi TG, TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001829
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001830 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001831
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001832 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
1833 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001834
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001835 lz = mbedtls_mpi_lsb( &TA );
1836 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001837
Paul Bakker66d5d072014-06-17 16:39:18 +02001838 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001839 lz = lzt;
1840
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001841 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
1842 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001843
Paul Bakker5121ce52009-01-03 21:22:43 +00001844 TA.s = TB.s = 1;
1845
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001846 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001847 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001848 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
1849 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001850
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001851 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001852 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001853 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
1854 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001855 }
1856 else
1857 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001858 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
1859 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001860 }
1861 }
1862
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001863 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
1864 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001865
1866cleanup:
1867
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001868 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001869
1870 return( ret );
1871}
1872
Paul Bakker33dc46b2014-04-30 16:11:39 +02001873/*
1874 * Fill X with size bytes of random.
1875 *
1876 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02001877 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02001878 * deterministic, eg for tests).
1879 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001880int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00001881 int (*f_rng)(void *, unsigned char *, size_t),
1882 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00001883{
Paul Bakker23986e52011-04-24 08:57:21 +00001884 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001885 unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
Paul Bakker33dc46b2014-04-30 16:11:39 +02001886
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001887 if( size > MBEDTLS_MPI_MAX_SIZE )
1888 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker287781a2011-03-26 13:18:49 +00001889
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001890 MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) );
1891 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) );
Paul Bakker287781a2011-03-26 13:18:49 +00001892
1893cleanup:
Hanno Becker88807112017-10-18 12:41:30 +01001894 mbedtls_zeroize( buf, sizeof( buf ) );
Paul Bakker287781a2011-03-26 13:18:49 +00001895 return( ret );
1896}
1897
Paul Bakker5121ce52009-01-03 21:22:43 +00001898/*
1899 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1900 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001901int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001902{
1903 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001904 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001905
Hanno Becker4bcb4912017-04-18 15:49:39 +01001906 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001907 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001908
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001909 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
1910 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
1911 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001912
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001913 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001914
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001915 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001916 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001917 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00001918 goto cleanup;
1919 }
1920
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001921 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
1922 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
1923 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
1924 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001925
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001926 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
1927 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
1928 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
1929 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001930
1931 do
1932 {
1933 while( ( TU.p[0] & 1 ) == 0 )
1934 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001935 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001936
1937 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1938 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001939 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
1940 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001941 }
1942
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001943 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
1944 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001945 }
1946
1947 while( ( TV.p[0] & 1 ) == 0 )
1948 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001949 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001950
1951 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1952 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001953 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
1954 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001955 }
1956
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001957 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
1958 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001959 }
1960
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001961 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001962 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001963 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
1964 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
1965 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001966 }
1967 else
1968 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001969 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
1970 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
1971 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001972 }
1973 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001974 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001975
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001976 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
1977 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001978
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001979 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
1980 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001981
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001982 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001983
1984cleanup:
1985
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001986 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
1987 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
1988 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001989
1990 return( ret );
1991}
1992
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001993#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00001994
Paul Bakker5121ce52009-01-03 21:22:43 +00001995static const int small_prime[] =
1996{
1997 3, 5, 7, 11, 13, 17, 19, 23,
1998 29, 31, 37, 41, 43, 47, 53, 59,
1999 61, 67, 71, 73, 79, 83, 89, 97,
2000 101, 103, 107, 109, 113, 127, 131, 137,
2001 139, 149, 151, 157, 163, 167, 173, 179,
2002 181, 191, 193, 197, 199, 211, 223, 227,
2003 229, 233, 239, 241, 251, 257, 263, 269,
2004 271, 277, 281, 283, 293, 307, 311, 313,
2005 317, 331, 337, 347, 349, 353, 359, 367,
2006 373, 379, 383, 389, 397, 401, 409, 419,
2007 421, 431, 433, 439, 443, 449, 457, 461,
2008 463, 467, 479, 487, 491, 499, 503, 509,
2009 521, 523, 541, 547, 557, 563, 569, 571,
2010 577, 587, 593, 599, 601, 607, 613, 617,
2011 619, 631, 641, 643, 647, 653, 659, 661,
2012 673, 677, 683, 691, 701, 709, 719, 727,
2013 733, 739, 743, 751, 757, 761, 769, 773,
2014 787, 797, 809, 811, 821, 823, 827, 829,
2015 839, 853, 857, 859, 863, 877, 881, 883,
2016 887, 907, 911, 919, 929, 937, 941, 947,
2017 953, 967, 971, 977, 983, 991, 997, -103
2018};
2019
2020/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002021 * Small divisors test (X must be positive)
2022 *
2023 * Return values:
2024 * 0: no small factor (possible prime, more tests needed)
2025 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002026 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002027 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002028 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002029static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002030{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002031 int ret = 0;
2032 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002033 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002034
Paul Bakker5121ce52009-01-03 21:22:43 +00002035 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002036 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002037
2038 for( i = 0; small_prime[i] > 0; i++ )
2039 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002040 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002041 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002042
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002043 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002044
2045 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002046 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002047 }
2048
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002049cleanup:
2050 return( ret );
2051}
2052
2053/*
2054 * Miller-Rabin pseudo-primality test (HAC 4.24)
2055 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002056static int mpi_miller_rabin( const mbedtls_mpi *X,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002057 int (*f_rng)(void *, unsigned char *, size_t),
2058 void *p_rng )
2059{
Pascal Junodb99183d2015-03-11 16:49:45 +01002060 int ret, count;
2061 size_t i, j, k, n, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002062 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002063
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002064 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
2065 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002066
Paul Bakker5121ce52009-01-03 21:22:43 +00002067 /*
2068 * W = |X| - 1
2069 * R = W >> lsb( W )
2070 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002071 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2072 s = mbedtls_mpi_lsb( &W );
2073 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2074 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002075
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002076 i = mbedtls_mpi_bitlen( X );
Paul Bakker5121ce52009-01-03 21:22:43 +00002077 /*
2078 * HAC, table 4.4
2079 */
2080 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
2081 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
2082 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
2083
2084 for( i = 0; i < n; i++ )
2085 {
2086 /*
2087 * pick a random A, 1 < A < |X| - 1
2088 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002089 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002090
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002091 if( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 )
Paul Bakkerb94081b2011-01-05 15:53:06 +00002092 {
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002093 j = mbedtls_mpi_bitlen( &A ) - mbedtls_mpi_bitlen( &W );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002094 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j + 1 ) );
Paul Bakkerb94081b2011-01-05 15:53:06 +00002095 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002096 A.p[0] |= 3;
2097
Pascal Junodb99183d2015-03-11 16:49:45 +01002098 count = 0;
2099 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002100 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002101
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002102 j = mbedtls_mpi_bitlen( &A );
2103 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002104 if (j > k) {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002105 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j - k ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002106 }
2107
2108 if (count++ > 30) {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002109 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Pascal Junodb99183d2015-03-11 16:49:45 +01002110 }
2111
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002112 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2113 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002114
2115 /*
2116 * A = A^R mod |X|
2117 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002118 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002119
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002120 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2121 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002122 continue;
2123
2124 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002125 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002126 {
2127 /*
2128 * A = A * A mod |X|
2129 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002130 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2131 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002132
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002133 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002134 break;
2135
2136 j++;
2137 }
2138
2139 /*
2140 * not prime if A != |X| - 1 or A == 1
2141 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002142 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2143 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002144 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002145 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002146 break;
2147 }
2148 }
2149
2150cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002151 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2152 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002153
2154 return( ret );
2155}
2156
2157/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002158 * Pseudo-primality test: small factors, then Miller-Rabin
2159 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002160int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002161 int (*f_rng)(void *, unsigned char *, size_t),
2162 void *p_rng )
2163{
2164 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002165 mbedtls_mpi XX;
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002166
2167 XX.s = 1;
2168 XX.n = X->n;
2169 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002170
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002171 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2172 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2173 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002174
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002175 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002176 return( 0 );
2177
2178 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2179 {
2180 if( ret == 1 )
2181 return( 0 );
2182
2183 return( ret );
2184 }
2185
2186 return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
2187}
2188
2189/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002190 * Prime number generation
2191 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002192int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002193 int (*f_rng)(void *, unsigned char *, size_t),
2194 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002195{
Paul Bakker23986e52011-04-24 08:57:21 +00002196 int ret;
2197 size_t k, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002198 mbedtls_mpi_uint r;
2199 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002200
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002201 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2202 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002203
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002204 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002205
2206 n = BITS_TO_LIMBS( nbits );
2207
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002208 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002209
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002210 k = mbedtls_mpi_bitlen( X );
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002211 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002212
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002213 mbedtls_mpi_set_bit( X, nbits-1, 1 );
Pascal Junodb99183d2015-03-11 16:49:45 +01002214
2215 X->p[0] |= 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00002216
2217 if( dh_flag == 0 )
2218 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002219 while( ( ret = mbedtls_mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002220 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002221 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002222 goto cleanup;
2223
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002224 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002225 }
2226 }
2227 else
2228 {
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002229 /*
2230 * An necessary condition for Y and X = 2Y + 1 to be prime
2231 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2232 * Make sure it is satisfied, while keeping X = 3 mod 4
2233 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002234
2235 X->p[0] |= 2;
2236
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002237 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002238 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002239 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002240 else if( r == 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002241 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002242
2243 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002244 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2245 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002246
2247 while( 1 )
2248 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002249 /*
2250 * First, check small factors for X and Y
2251 * before doing Miller-Rabin on any of them
2252 */
2253 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2254 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2255 ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
2256 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002257 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002258 break;
Paul Bakker5121ce52009-01-03 21:22:43 +00002259 }
2260
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002261 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002262 goto cleanup;
2263
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002264 /*
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002265 * Next candidates. We want to preserve Y = (X-1) / 2 and
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002266 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2267 * so up Y by 6 and X by 12.
2268 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002269 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2270 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002271 }
2272 }
2273
2274cleanup:
2275
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002276 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002277
2278 return( ret );
2279}
2280
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002281#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002282
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002283#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002284
Paul Bakker23986e52011-04-24 08:57:21 +00002285#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002286
2287static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2288{
2289 { 693, 609, 21 },
2290 { 1764, 868, 28 },
2291 { 768454923, 542167814, 1 }
2292};
2293
Paul Bakker5121ce52009-01-03 21:22:43 +00002294/*
2295 * Checkup routine
2296 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002297int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002298{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002299 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002300 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002301
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002302 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2303 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002304
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002305 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002306 "EFE021C2645FD1DC586E69184AF4A31E" \
2307 "D5F53E93B5F123FA41680867BA110131" \
2308 "944FE7952E2517337780CB0DB80E61AA" \
2309 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2310
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002311 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002312 "B2E7EFD37075B9F03FF989C7C5051C20" \
2313 "34D2A323810251127E7BF8625A4F49A5" \
2314 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2315 "5B5C25763222FEFCCFC38B832366C29E" ) );
2316
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002317 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002318 "0066A198186C18C10B2F5ED9B522752A" \
2319 "9830B69916E535C8F047518A889A43A5" \
2320 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2321
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002322 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002323
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002324 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002325 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2326 "9E857EA95A03512E2BAE7391688D264A" \
2327 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2328 "8001B72E848A38CAE1C65F78E56ABDEF" \
2329 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2330 "ECF677152EF804370C1A305CAF3B5BF1" \
2331 "30879B56C61DE584A0F53A2447A51E" ) );
2332
2333 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002334 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002335
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002336 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002337 {
2338 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002339 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002340
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002341 ret = 1;
2342 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002343 }
2344
2345 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002346 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002347
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002348 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002349
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002350 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002351 "256567336059E52CAE22925474705F39A94" ) );
2352
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002353 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002354 "6613F26162223DF488E9CD48CC132C7A" \
2355 "0AC93C701B001B092E4E5B9F73BCD27B" \
2356 "9EE50D0657C77F374E903CDFA4C642" ) );
2357
2358 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002359 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002360
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002361 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2362 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002363 {
2364 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002365 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002366
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002367 ret = 1;
2368 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002369 }
2370
2371 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002372 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002373
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002374 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002375
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002376 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002377 "36E139AEA55215609D2816998ED020BB" \
2378 "BD96C37890F65171D948E9BC7CBAA4D9" \
2379 "325D24D6A3C12710F10A09FA08AB87" ) );
2380
2381 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002382 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002383
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002384 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002385 {
2386 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002387 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002388
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002389 ret = 1;
2390 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002391 }
2392
2393 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002394 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002395
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002396 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002397
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002398 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002399 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2400 "C3DBA76456363A10869622EAC2DD84EC" \
2401 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2402
2403 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002404 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002405
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002406 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002407 {
2408 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002409 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002410
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002411 ret = 1;
2412 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002413 }
2414
2415 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002416 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002417
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002418 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002419 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002420
Paul Bakker66d5d072014-06-17 16:39:18 +02002421 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002422 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002423 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2424 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002425
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002426 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002427
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002428 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002429 {
2430 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002431 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002432
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002433 ret = 1;
2434 goto cleanup;
2435 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002436 }
2437
2438 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002439 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002440
Paul Bakker5121ce52009-01-03 21:22:43 +00002441cleanup:
2442
2443 if( ret != 0 && verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002444 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002445
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002446 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2447 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002448
2449 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002450 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002451
2452 return( ret );
2453}
2454
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002455#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002456
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002457#endif /* MBEDTLS_BIGNUM_C */