blob: ca05f7731f81e85cc7546d3dbc60a69bcb7b30b5 [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 *
36*/
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 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020062static void mbedtls_zeroize( void *v, size_t n ) {
Paul Bakker34617722014-06-13 17:20:13 +020063 volatile unsigned char *p = v; while( n-- ) *p++ = 0;
64}
65
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020066#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
Paul Bakker5121ce52009-01-03 21:22:43 +000067#define biL (ciL << 3) /* bits in limb */
68#define biH (ciL << 2) /* half limb size */
69
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +010070#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
71
Paul Bakker5121ce52009-01-03 21:22:43 +000072/*
73 * Convert between bits/chars and number of limbs
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020074 * Divide first in order to avoid potential overflows
Paul Bakker5121ce52009-01-03 21:22:43 +000075 */
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020076#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
77#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
Paul Bakker5121ce52009-01-03 21:22:43 +000078
79/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000080 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000081 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020082void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000083{
Paul Bakker6c591fa2011-05-05 11:49:20 +000084 if( X == NULL )
85 return;
Paul Bakker5121ce52009-01-03 21:22:43 +000086
Paul Bakker6c591fa2011-05-05 11:49:20 +000087 X->s = 1;
88 X->n = 0;
89 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +000090}
91
92/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000093 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000094 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020095void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000096{
Paul Bakker6c591fa2011-05-05 11:49:20 +000097 if( X == NULL )
98 return;
Paul Bakker5121ce52009-01-03 21:22:43 +000099
Paul Bakker6c591fa2011-05-05 11:49:20 +0000100 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +0000101 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200102 mbedtls_zeroize( X->p, X->n * ciL );
103 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000104 }
105
Paul Bakker6c591fa2011-05-05 11:49:20 +0000106 X->s = 1;
107 X->n = 0;
108 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000109}
110
111/*
112 * Enlarge to the specified number of limbs
113 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200114int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000115{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200116 mbedtls_mpi_uint *p;
Paul Bakker5121ce52009-01-03 21:22:43 +0000117
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200118 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200119 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000120
Paul Bakker5121ce52009-01-03 21:22:43 +0000121 if( X->n < nblimbs )
122 {
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +0200123 if( ( p = mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200124 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000125
Paul Bakker5121ce52009-01-03 21:22:43 +0000126 if( X->p != NULL )
127 {
128 memcpy( p, X->p, X->n * ciL );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200129 mbedtls_zeroize( X->p, X->n * ciL );
130 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000131 }
132
133 X->n = nblimbs;
134 X->p = p;
135 }
136
137 return( 0 );
138}
139
140/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100141 * Resize down as much as possible,
142 * while keeping at least the specified number of limbs
143 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200144int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100145{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200146 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100147 size_t i;
148
149 /* Actually resize up in this case */
150 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200151 return( mbedtls_mpi_grow( X, nblimbs ) );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100152
153 for( i = X->n - 1; i > 0; i-- )
154 if( X->p[i] != 0 )
155 break;
156 i++;
157
158 if( i < nblimbs )
159 i = nblimbs;
160
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +0200161 if( ( p = mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200162 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100163
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100164 if( X->p != NULL )
165 {
166 memcpy( p, X->p, i * ciL );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200167 mbedtls_zeroize( X->p, X->n * ciL );
168 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100169 }
170
171 X->n = i;
172 X->p = p;
173
174 return( 0 );
175}
176
177/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000178 * Copy the contents of Y into X
179 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200180int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000181{
Paul Bakker23986e52011-04-24 08:57:21 +0000182 int ret;
183 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000184
185 if( X == Y )
186 return( 0 );
187
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200188 if( Y->p == NULL )
189 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200190 mbedtls_mpi_free( X );
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200191 return( 0 );
192 }
193
Paul Bakker5121ce52009-01-03 21:22:43 +0000194 for( i = Y->n - 1; i > 0; i-- )
195 if( Y->p[i] != 0 )
196 break;
197 i++;
198
199 X->s = Y->s;
200
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200201 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000202
203 memset( X->p, 0, X->n * ciL );
204 memcpy( X->p, Y->p, i * ciL );
205
206cleanup:
207
208 return( ret );
209}
210
211/*
212 * Swap the contents of X and Y
213 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200214void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000215{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200216 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000217
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200218 memcpy( &T, X, sizeof( mbedtls_mpi ) );
219 memcpy( X, Y, sizeof( mbedtls_mpi ) );
220 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000221}
222
223/*
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100224 * Conditionally assign X = Y, without leaking information
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100225 * about whether the assignment was made or not.
226 * (Leaking information about the respective sizes of X and Y is ok however.)
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100227 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200228int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100229{
230 int ret = 0;
231 size_t i;
232
Pascal Junodb99183d2015-03-11 16:49:45 +0100233 /* make sure assign is 0 or 1 in a time-constant manner */
234 assign = (assign | (unsigned char)-assign) >> 7;
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100235
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200236 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100237
Paul Bakker66d5d072014-06-17 16:39:18 +0200238 X->s = X->s * ( 1 - assign ) + Y->s * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100239
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100240 for( i = 0; i < Y->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200241 X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100242
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100243 for( ; i < X->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200244 X->p[i] *= ( 1 - assign );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100245
246cleanup:
247 return( ret );
248}
249
250/*
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100251 * Conditionally swap X and Y, without leaking information
252 * about whether the swap was made or not.
253 * Here it is not ok to simply swap the pointers, which whould lead to
254 * different memory access patterns when X and Y are used afterwards.
255 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200256int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100257{
258 int ret, s;
259 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200260 mbedtls_mpi_uint tmp;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100261
262 if( X == Y )
263 return( 0 );
264
Pascal Junodb99183d2015-03-11 16:49:45 +0100265 /* make sure swap is 0 or 1 in a time-constant manner */
266 swap = (swap | (unsigned char)-swap) >> 7;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100267
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200268 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
269 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100270
271 s = X->s;
Paul Bakker66d5d072014-06-17 16:39:18 +0200272 X->s = X->s * ( 1 - swap ) + Y->s * swap;
273 Y->s = Y->s * ( 1 - swap ) + s * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100274
275
276 for( i = 0; i < X->n; i++ )
277 {
278 tmp = X->p[i];
Paul Bakker66d5d072014-06-17 16:39:18 +0200279 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
280 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100281 }
282
283cleanup:
284 return( ret );
285}
286
287/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000288 * Set value from integer
289 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200290int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000291{
292 int ret;
293
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200294 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000295 memset( X->p, 0, X->n * ciL );
296
297 X->p[0] = ( z < 0 ) ? -z : z;
298 X->s = ( z < 0 ) ? -1 : 1;
299
300cleanup:
301
302 return( ret );
303}
304
305/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000306 * Get a specific bit
307 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200308int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000309{
310 if( X->n * biL <= pos )
311 return( 0 );
312
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200313 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000314}
315
316/*
317 * Set a bit to a specific value of 0 or 1
318 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200319int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000320{
321 int ret = 0;
322 size_t off = pos / biL;
323 size_t idx = pos % biL;
324
325 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200326 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200327
Paul Bakker2f5947e2011-05-18 15:47:11 +0000328 if( X->n * biL <= pos )
329 {
330 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200331 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000332
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200333 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000334 }
335
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200336 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
337 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000338
339cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200340
Paul Bakker2f5947e2011-05-18 15:47:11 +0000341 return( ret );
342}
343
344/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200345 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000346 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200347size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000348{
Paul Bakker23986e52011-04-24 08:57:21 +0000349 size_t i, j, count = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000350
351 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000352 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000353 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
354 return( count );
355
356 return( 0 );
357}
358
359/*
Simon Butcher15b15d12015-11-26 19:35:03 +0000360 * Count leading zero bits in a given integer
361 */
362static size_t mbedtls_clz( const mbedtls_mpi_uint x )
363{
364 size_t j;
Manuel Pégourié-Gonnarde3e8edf2015-12-01 09:31:52 +0100365 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
Simon Butcher15b15d12015-11-26 19:35:03 +0000366
367 for( j = 0; j < biL; j++ )
368 {
369 if( x & mask ) break;
370
371 mask >>= 1;
372 }
373
374 return j;
375}
376
377/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200378 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000379 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200380size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000381{
Paul Bakker23986e52011-04-24 08:57:21 +0000382 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000383
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200384 if( X->n == 0 )
385 return( 0 );
386
Paul Bakker5121ce52009-01-03 21:22:43 +0000387 for( i = X->n - 1; i > 0; i-- )
388 if( X->p[i] != 0 )
389 break;
390
Simon Butcher15b15d12015-11-26 19:35:03 +0000391 j = biL - mbedtls_clz( X->p[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +0000392
Paul Bakker23986e52011-04-24 08:57:21 +0000393 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000394}
395
396/*
397 * Return the total size in bytes
398 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200399size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000400{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200401 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000402}
403
404/*
405 * Convert an ASCII character to digit value
406 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200407static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000408{
409 *d = 255;
410
411 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
412 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
413 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
414
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200415 if( *d >= (mbedtls_mpi_uint) radix )
416 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000417
418 return( 0 );
419}
420
421/*
422 * Import from an ASCII string
423 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200424int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000425{
Paul Bakker23986e52011-04-24 08:57:21 +0000426 int ret;
427 size_t i, j, slen, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200428 mbedtls_mpi_uint d;
429 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000430
431 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200432 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000433
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200434 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000435
Paul Bakkerff60ee62010-03-16 21:09:09 +0000436 slen = strlen( s );
437
Paul Bakker5121ce52009-01-03 21:22:43 +0000438 if( radix == 16 )
439 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100440 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200441 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
442
Paul Bakkerff60ee62010-03-16 21:09:09 +0000443 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000444
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200445 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
446 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000447
Paul Bakker23986e52011-04-24 08:57:21 +0000448 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000449 {
Paul Bakker23986e52011-04-24 08:57:21 +0000450 if( i == 1 && s[i - 1] == '-' )
Paul Bakker5121ce52009-01-03 21:22:43 +0000451 {
452 X->s = -1;
453 break;
454 }
455
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200456 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200457 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000458 }
459 }
460 else
461 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200462 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000463
Paul Bakkerff60ee62010-03-16 21:09:09 +0000464 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000465 {
466 if( i == 0 && s[i] == '-' )
467 {
468 X->s = -1;
469 continue;
470 }
471
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200472 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
473 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000474
475 if( X->s == 1 )
476 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200477 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000478 }
479 else
480 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200481 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000482 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000483 }
484 }
485
486cleanup:
487
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200488 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000489
490 return( ret );
491}
492
493/*
494 * Helper to write the digits high-order first
495 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200496static int mpi_write_hlp( mbedtls_mpi *X, int radix, char **p )
Paul Bakker5121ce52009-01-03 21:22:43 +0000497{
498 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200499 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +0000500
501 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200502 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000503
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200504 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
505 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000506
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200507 if( mbedtls_mpi_cmp_int( X, 0 ) != 0 )
508 MBEDTLS_MPI_CHK( mpi_write_hlp( X, radix, p ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000509
510 if( r < 10 )
511 *(*p)++ = (char)( r + 0x30 );
512 else
513 *(*p)++ = (char)( r + 0x37 );
514
515cleanup:
516
517 return( ret );
518}
519
520/*
521 * Export into an ASCII string
522 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100523int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
524 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000525{
Paul Bakker23986e52011-04-24 08:57:21 +0000526 int ret = 0;
527 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000528 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200529 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000530
531 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200532 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000533
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200534 n = mbedtls_mpi_bitlen( X );
Paul Bakker5121ce52009-01-03 21:22:43 +0000535 if( radix >= 4 ) n >>= 1;
536 if( radix >= 16 ) n >>= 1;
537 n += 3;
538
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100539 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000540 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100541 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200542 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000543 }
544
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100545 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200546 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000547
548 if( X->s == -1 )
549 *p++ = '-';
550
551 if( radix == 16 )
552 {
Paul Bakker23986e52011-04-24 08:57:21 +0000553 int c;
554 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000555
Paul Bakker23986e52011-04-24 08:57:21 +0000556 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000557 {
Paul Bakker23986e52011-04-24 08:57:21 +0000558 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000559 {
Paul Bakker23986e52011-04-24 08:57:21 +0000560 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000561
Paul Bakker6c343d72014-07-10 14:36:19 +0200562 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000563 continue;
564
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000565 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000566 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000567 k = 1;
568 }
569 }
570 }
571 else
572 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200573 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000574
575 if( T.s == -1 )
576 T.s = 1;
577
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200578 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000579 }
580
581 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100582 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000583
584cleanup:
585
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200586 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000587
588 return( ret );
589}
590
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200591#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000592/*
593 * Read X from an opened file
594 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200595int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000596{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200597 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000598 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000599 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000600 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000601 * Buffer should have space for (short) label and decimal formatted MPI,
602 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000603 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200604 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000605
606 memset( s, 0, sizeof( s ) );
607 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200608 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000609
610 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000611 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200612 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000613
Paul Bakker5121ce52009-01-03 21:22:43 +0000614 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
615 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
616
617 p = s + slen;
618 while( --p >= s )
619 if( mpi_get_digit( &d, radix, *p ) != 0 )
620 break;
621
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200622 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000623}
624
625/*
626 * Write X into an opened file (or stdout if fout == NULL)
627 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200628int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000629{
Paul Bakker23986e52011-04-24 08:57:21 +0000630 int ret;
631 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000632 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000633 * Buffer should have space for (short) label and decimal formatted MPI,
634 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000635 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200636 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000637
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100638 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000639
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100640 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000641
642 if( p == NULL ) p = "";
643
644 plen = strlen( p );
645 slen = strlen( s );
646 s[slen++] = '\r';
647 s[slen++] = '\n';
648
649 if( fout != NULL )
650 {
651 if( fwrite( p, 1, plen, fout ) != plen ||
652 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200653 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000654 }
655 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200656 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000657
658cleanup:
659
660 return( ret );
661}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200662#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000663
664/*
665 * Import X from unsigned binary data, big endian
666 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200667int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000668{
Paul Bakker23986e52011-04-24 08:57:21 +0000669 int ret;
670 size_t i, j, n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000671
672 for( n = 0; n < buflen; n++ )
673 if( buf[n] != 0 )
674 break;
675
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200676 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
677 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000678
Paul Bakker23986e52011-04-24 08:57:21 +0000679 for( i = buflen, j = 0; i > n; i--, j++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200680 X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
Paul Bakker5121ce52009-01-03 21:22:43 +0000681
682cleanup:
683
684 return( ret );
685}
686
687/*
688 * Export X into unsigned binary data, big endian
689 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200690int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000691{
Paul Bakker23986e52011-04-24 08:57:21 +0000692 size_t i, j, n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000693
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200694 n = mbedtls_mpi_size( X );
Paul Bakker5121ce52009-01-03 21:22:43 +0000695
696 if( buflen < n )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200697 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000698
699 memset( buf, 0, buflen );
700
701 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
702 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
703
704 return( 0 );
705}
706
707/*
708 * Left-shift: X <<= count
709 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200710int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000711{
Paul Bakker23986e52011-04-24 08:57:21 +0000712 int ret;
713 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200714 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000715
716 v0 = count / (biL );
717 t1 = count & (biL - 1);
718
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200719 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000720
Paul Bakkerf9688572011-05-05 10:00:45 +0000721 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200722 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000723
724 ret = 0;
725
726 /*
727 * shift by count / limb_size
728 */
729 if( v0 > 0 )
730 {
Paul Bakker23986e52011-04-24 08:57:21 +0000731 for( i = X->n; i > v0; i-- )
732 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000733
Paul Bakker23986e52011-04-24 08:57:21 +0000734 for( ; i > 0; i-- )
735 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000736 }
737
738 /*
739 * shift by count % limb_size
740 */
741 if( t1 > 0 )
742 {
743 for( i = v0; i < X->n; i++ )
744 {
745 r1 = X->p[i] >> (biL - t1);
746 X->p[i] <<= t1;
747 X->p[i] |= r0;
748 r0 = r1;
749 }
750 }
751
752cleanup:
753
754 return( ret );
755}
756
757/*
758 * Right-shift: X >>= count
759 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200760int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000761{
Paul Bakker23986e52011-04-24 08:57:21 +0000762 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200763 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000764
765 v0 = count / biL;
766 v1 = count & (biL - 1);
767
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100768 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200769 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100770
Paul Bakker5121ce52009-01-03 21:22:43 +0000771 /*
772 * shift by count / limb_size
773 */
774 if( v0 > 0 )
775 {
776 for( i = 0; i < X->n - v0; i++ )
777 X->p[i] = X->p[i + v0];
778
779 for( ; i < X->n; i++ )
780 X->p[i] = 0;
781 }
782
783 /*
784 * shift by count % limb_size
785 */
786 if( v1 > 0 )
787 {
Paul Bakker23986e52011-04-24 08:57:21 +0000788 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000789 {
Paul Bakker23986e52011-04-24 08:57:21 +0000790 r1 = X->p[i - 1] << (biL - v1);
791 X->p[i - 1] >>= v1;
792 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000793 r0 = r1;
794 }
795 }
796
797 return( 0 );
798}
799
800/*
801 * Compare unsigned values
802 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200803int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000804{
Paul Bakker23986e52011-04-24 08:57:21 +0000805 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000806
Paul Bakker23986e52011-04-24 08:57:21 +0000807 for( i = X->n; i > 0; i-- )
808 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000809 break;
810
Paul Bakker23986e52011-04-24 08:57:21 +0000811 for( j = Y->n; j > 0; j-- )
812 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000813 break;
814
Paul Bakker23986e52011-04-24 08:57:21 +0000815 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000816 return( 0 );
817
818 if( i > j ) return( 1 );
819 if( j > i ) return( -1 );
820
Paul Bakker23986e52011-04-24 08:57:21 +0000821 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000822 {
Paul Bakker23986e52011-04-24 08:57:21 +0000823 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
824 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000825 }
826
827 return( 0 );
828}
829
830/*
831 * Compare signed values
832 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200833int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000834{
Paul Bakker23986e52011-04-24 08:57:21 +0000835 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000836
Paul Bakker23986e52011-04-24 08:57:21 +0000837 for( i = X->n; i > 0; i-- )
838 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000839 break;
840
Paul Bakker23986e52011-04-24 08:57:21 +0000841 for( j = Y->n; j > 0; j-- )
842 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000843 break;
844
Paul Bakker23986e52011-04-24 08:57:21 +0000845 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000846 return( 0 );
847
848 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +0000849 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000850
851 if( X->s > 0 && Y->s < 0 ) return( 1 );
852 if( Y->s > 0 && X->s < 0 ) return( -1 );
853
Paul Bakker23986e52011-04-24 08:57:21 +0000854 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000855 {
Paul Bakker23986e52011-04-24 08:57:21 +0000856 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
857 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000858 }
859
860 return( 0 );
861}
862
863/*
864 * Compare signed values
865 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200866int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000867{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200868 mbedtls_mpi Y;
869 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000870
871 *p = ( z < 0 ) ? -z : z;
872 Y.s = ( z < 0 ) ? -1 : 1;
873 Y.n = 1;
874 Y.p = p;
875
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200876 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000877}
878
879/*
880 * Unsigned addition: X = |A| + |B| (HAC 14.7)
881 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200882int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000883{
Paul Bakker23986e52011-04-24 08:57:21 +0000884 int ret;
885 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200886 mbedtls_mpi_uint *o, *p, c;
Paul Bakker5121ce52009-01-03 21:22:43 +0000887
888 if( X == B )
889 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200890 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000891 }
892
893 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200894 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +0200895
Paul Bakkerf7ca7b92009-06-20 10:31:06 +0000896 /*
897 * X should always be positive as a result of unsigned additions.
898 */
899 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000900
Paul Bakker23986e52011-04-24 08:57:21 +0000901 for( j = B->n; j > 0; j-- )
902 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000903 break;
904
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200905 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000906
907 o = B->p; p = X->p; c = 0;
908
Paul Bakker23986e52011-04-24 08:57:21 +0000909 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000910 {
911 *p += c; c = ( *p < c );
912 *p += *o; c += ( *p < *o );
913 }
914
915 while( c != 0 )
916 {
917 if( i >= X->n )
918 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200919 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000920 p = X->p + i;
921 }
922
Paul Bakker2d319fd2012-09-16 21:34:26 +0000923 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +0000924 }
925
926cleanup:
927
928 return( ret );
929}
930
931/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200932 * Helper for mbedtls_mpi subtraction
Paul Bakker5121ce52009-01-03 21:22:43 +0000933 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200934static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d )
Paul Bakker5121ce52009-01-03 21:22:43 +0000935{
Paul Bakker23986e52011-04-24 08:57:21 +0000936 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200937 mbedtls_mpi_uint c, z;
Paul Bakker5121ce52009-01-03 21:22:43 +0000938
939 for( i = c = 0; i < n; i++, s++, d++ )
940 {
941 z = ( *d < c ); *d -= c;
942 c = ( *d < *s ) + z; *d -= *s;
943 }
944
945 while( c != 0 )
946 {
947 z = ( *d < c ); *d -= c;
948 c = z; i++; d++;
949 }
950}
951
952/*
Paul Bakker60b1d102013-10-29 10:02:51 +0100953 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
Paul Bakker5121ce52009-01-03 21:22:43 +0000954 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200955int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000956{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200957 mbedtls_mpi TB;
Paul Bakker23986e52011-04-24 08:57:21 +0000958 int ret;
959 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000960
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200961 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
962 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +0000963
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200964 mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +0000965
966 if( X == B )
967 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200968 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000969 B = &TB;
970 }
971
972 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200973 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000974
Paul Bakker1ef7a532009-06-20 10:50:55 +0000975 /*
Paul Bakker60b1d102013-10-29 10:02:51 +0100976 * X should always be positive as a result of unsigned subtractions.
Paul Bakker1ef7a532009-06-20 10:50:55 +0000977 */
978 X->s = 1;
979
Paul Bakker5121ce52009-01-03 21:22:43 +0000980 ret = 0;
981
Paul Bakker23986e52011-04-24 08:57:21 +0000982 for( n = B->n; n > 0; n-- )
983 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000984 break;
985
Paul Bakker23986e52011-04-24 08:57:21 +0000986 mpi_sub_hlp( n, B->p, X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000987
988cleanup:
989
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200990 mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +0000991
992 return( ret );
993}
994
995/*
996 * Signed addition: X = A + B
997 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200998int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000999{
1000 int ret, s = A->s;
1001
1002 if( A->s * B->s < 0 )
1003 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001004 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001005 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001006 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001007 X->s = s;
1008 }
1009 else
1010 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001011 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001012 X->s = -s;
1013 }
1014 }
1015 else
1016 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001017 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001018 X->s = s;
1019 }
1020
1021cleanup:
1022
1023 return( ret );
1024}
1025
1026/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001027 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001028 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001029int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001030{
1031 int ret, s = A->s;
1032
1033 if( A->s * B->s > 0 )
1034 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001035 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001036 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001037 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001038 X->s = s;
1039 }
1040 else
1041 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001042 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001043 X->s = -s;
1044 }
1045 }
1046 else
1047 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001048 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001049 X->s = s;
1050 }
1051
1052cleanup:
1053
1054 return( ret );
1055}
1056
1057/*
1058 * Signed addition: X = A + b
1059 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001060int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001061{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001062 mbedtls_mpi _B;
1063 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001064
1065 p[0] = ( b < 0 ) ? -b : b;
1066 _B.s = ( b < 0 ) ? -1 : 1;
1067 _B.n = 1;
1068 _B.p = p;
1069
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001070 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001071}
1072
1073/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001074 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001075 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001076int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001077{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001078 mbedtls_mpi _B;
1079 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001080
1081 p[0] = ( b < 0 ) ? -b : b;
1082 _B.s = ( b < 0 ) ? -1 : 1;
1083 _B.n = 1;
1084 _B.p = p;
1085
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001086 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001087}
1088
1089/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001090 * Helper for mbedtls_mpi multiplication
Paul Bakkerfc4f46f2013-06-24 19:23:56 +02001091 */
1092static
1093#if defined(__APPLE__) && defined(__arm__)
1094/*
1095 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1096 * appears to need this to prevent bad ARM code generation at -O3.
1097 */
1098__attribute__ ((noinline))
1099#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001100void 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 +00001101{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001102 mbedtls_mpi_uint c = 0, t = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001103
1104#if defined(MULADDC_HUIT)
1105 for( ; i >= 8; i -= 8 )
1106 {
1107 MULADDC_INIT
1108 MULADDC_HUIT
1109 MULADDC_STOP
1110 }
1111
1112 for( ; i > 0; i-- )
1113 {
1114 MULADDC_INIT
1115 MULADDC_CORE
1116 MULADDC_STOP
1117 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001118#else /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001119 for( ; i >= 16; i -= 16 )
1120 {
1121 MULADDC_INIT
1122 MULADDC_CORE MULADDC_CORE
1123 MULADDC_CORE MULADDC_CORE
1124 MULADDC_CORE MULADDC_CORE
1125 MULADDC_CORE MULADDC_CORE
1126
1127 MULADDC_CORE MULADDC_CORE
1128 MULADDC_CORE MULADDC_CORE
1129 MULADDC_CORE MULADDC_CORE
1130 MULADDC_CORE MULADDC_CORE
1131 MULADDC_STOP
1132 }
1133
1134 for( ; i >= 8; i -= 8 )
1135 {
1136 MULADDC_INIT
1137 MULADDC_CORE MULADDC_CORE
1138 MULADDC_CORE MULADDC_CORE
1139
1140 MULADDC_CORE MULADDC_CORE
1141 MULADDC_CORE MULADDC_CORE
1142 MULADDC_STOP
1143 }
1144
1145 for( ; i > 0; i-- )
1146 {
1147 MULADDC_INIT
1148 MULADDC_CORE
1149 MULADDC_STOP
1150 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001151#endif /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001152
1153 t++;
1154
1155 do {
1156 *d += c; c = ( *d < c ); d++;
1157 }
1158 while( c != 0 );
1159}
1160
1161/*
1162 * Baseline multiplication: X = A * B (HAC 14.12)
1163 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001164int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001165{
Paul Bakker23986e52011-04-24 08:57:21 +00001166 int ret;
1167 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001168 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001169
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001170 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001171
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001172 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1173 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001174
Paul Bakker23986e52011-04-24 08:57:21 +00001175 for( i = A->n; i > 0; i-- )
1176 if( A->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001177 break;
1178
Paul Bakker23986e52011-04-24 08:57:21 +00001179 for( j = B->n; j > 0; j-- )
1180 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001181 break;
1182
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001183 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1184 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001185
Paul Bakker23986e52011-04-24 08:57:21 +00001186 for( i++; j > 0; j-- )
1187 mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001188
1189 X->s = A->s * B->s;
1190
1191cleanup:
1192
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001193 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001194
1195 return( ret );
1196}
1197
1198/*
1199 * Baseline multiplication: X = A * b
1200 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001201int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001202{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001203 mbedtls_mpi _B;
1204 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001205
1206 _B.s = 1;
1207 _B.n = 1;
1208 _B.p = p;
1209 p[0] = b;
1210
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001211 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001212}
1213
1214/*
Simon Butcher15b15d12015-11-26 19:35:03 +00001215 * Unsigned integer divide - 64bit dividend and 32bit divisor
1216 */
1217static mbedtls_mpi_uint mbedtls_int_div_int(mbedtls_mpi_uint u1,
1218 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r)
1219{
Manuel Pégourié-Gonnard16308882015-12-01 10:27:00 +01001220#if defined(MBEDTLS_HAVE_UDBL)
1221 mbedtls_t_udbl dividend, quotient;
1222#endif
1223
Simon Butcher15b15d12015-11-26 19:35:03 +00001224 /*
1225 * Check for overflow
1226 */
1227 if(( 0 == d ) || ( u1 >= d ))
1228 {
1229 if (r != NULL) *r = (~0);
1230
1231 return (~0);
1232 }
1233
1234#if defined(MBEDTLS_HAVE_UDBL)
Simon Butcher15b15d12015-11-26 19:35:03 +00001235 dividend = (mbedtls_t_udbl) u1 << biL;
1236 dividend |= (mbedtls_t_udbl) u0;
1237 quotient = dividend / d;
1238 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1239 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1240
1241 if( r != NULL )
1242 *r = dividend - (quotient * d);
1243
1244 return (mbedtls_mpi_uint) quotient;
1245#else
1246 const mbedtls_mpi_uint radix = 1 << biH;
1247 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1248 mbedtls_mpi_uint u0_msw, u0_lsw;
1249 int s;
1250
1251 /*
1252 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1253 * Vol. 2 - Seminumerical Algorithms, Knuth
1254 */
1255
1256 /*
1257 * Normalize the divisor, d, and dividend, u0, u1
1258 */
1259 s = mbedtls_clz( d );
1260 d = d << s;
1261
1262 u1 = u1 << s;
1263 u1 |= (u0 >> (32 - s)) & ( (-s) >> 31);
1264 u0 = u0 << s;
1265
1266 d1 = d >> biH;
1267 d0 = d & 0xffff;
1268
1269 u0_msw = u0 >> biH;
1270 u0_lsw = u0 & 0xffff;
1271
1272 /*
1273 * Find the first quotient and remainder
1274 */
1275 q1 = u1 / d1;
1276 r0 = u1 - d1 * q1;
1277
1278 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1279 {
1280 q1 -= 1;
1281 r0 += d1;
1282
1283 if ( r0 >= radix ) break;
1284 }
1285
1286 rAX = (u1 * radix) + (u0_msw - q1 * d);
1287 q0 = rAX / d1;
1288 r0 = rAX - q0 * d1;
1289
1290 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1291 {
1292 q0 -= 1;
1293 r0 += d1;
1294
1295 if ( r0 >= radix ) break;
1296 }
1297
1298 if (r != NULL)
1299 *r = (rAX * radix + u0_lsw - q0 * d) >> s;
1300
1301 quotient = q1 * radix + q0;
1302
1303 return quotient;
1304#endif
1305}
1306
1307/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001308 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001309 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001310int 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 +00001311{
Paul Bakker23986e52011-04-24 08:57:21 +00001312 int ret;
1313 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001314 mbedtls_mpi X, Y, Z, T1, T2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001315
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001316 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1317 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001318
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001319 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1320 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001321
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001322 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001323 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001324 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1325 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001326 return( 0 );
1327 }
1328
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001329 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1330 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001331 X.s = Y.s = 1;
1332
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001333 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1334 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1335 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1336 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001337
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001338 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001339 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001340 {
1341 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001342 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1343 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001344 }
1345 else k = 0;
1346
1347 n = X.n - 1;
1348 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001349 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001350
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001351 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001352 {
1353 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001354 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001355 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001356 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001357
1358 for( i = n; i > t ; i-- )
1359 {
1360 if( X.p[i] >= Y.p[t] )
1361 Z.p[i - t - 1] = ~0;
1362 else
1363 {
Simon Butcher15b15d12015-11-26 19:35:03 +00001364 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1365 Y.p[t], NULL);
Paul Bakker5121ce52009-01-03 21:22:43 +00001366 }
1367
1368 Z.p[i - t - 1]++;
1369 do
1370 {
1371 Z.p[i - t - 1]--;
1372
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001373 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001374 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001375 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001376 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001377
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001378 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001379 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1380 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001381 T2.p[2] = X.p[i];
1382 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001383 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001384
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001385 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1386 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1387 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001388
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001389 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001390 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001391 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1392 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1393 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001394 Z.p[i - t - 1]--;
1395 }
1396 }
1397
1398 if( Q != NULL )
1399 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001400 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001401 Q->s = A->s * B->s;
1402 }
1403
1404 if( R != NULL )
1405 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001406 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001407 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001408 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001409
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001410 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001411 R->s = 1;
1412 }
1413
1414cleanup:
1415
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001416 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1417 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001418
1419 return( ret );
1420}
1421
1422/*
1423 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001424 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001425int 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 +00001426{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001427 mbedtls_mpi _B;
1428 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001429
1430 p[0] = ( b < 0 ) ? -b : b;
1431 _B.s = ( b < 0 ) ? -1 : 1;
1432 _B.n = 1;
1433 _B.p = p;
1434
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001435 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001436}
1437
1438/*
1439 * Modulo: R = A mod B
1440 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001441int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001442{
1443 int ret;
1444
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001445 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1446 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001447
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001448 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001449
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001450 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1451 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001452
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001453 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1454 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001455
1456cleanup:
1457
1458 return( ret );
1459}
1460
1461/*
1462 * Modulo: r = A mod b
1463 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001464int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001465{
Paul Bakker23986e52011-04-24 08:57:21 +00001466 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001467 mbedtls_mpi_uint x, y, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001468
1469 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001470 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001471
1472 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001473 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001474
1475 /*
1476 * handle trivial cases
1477 */
1478 if( b == 1 )
1479 {
1480 *r = 0;
1481 return( 0 );
1482 }
1483
1484 if( b == 2 )
1485 {
1486 *r = A->p[0] & 1;
1487 return( 0 );
1488 }
1489
1490 /*
1491 * general case
1492 */
Paul Bakker23986e52011-04-24 08:57:21 +00001493 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001494 {
Paul Bakker23986e52011-04-24 08:57:21 +00001495 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001496 y = ( y << biH ) | ( x >> biH );
1497 z = y / b;
1498 y -= z * b;
1499
1500 x <<= biH;
1501 y = ( y << biH ) | ( x >> biH );
1502 z = y / b;
1503 y -= z * b;
1504 }
1505
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001506 /*
1507 * If A is negative, then the current y represents a negative value.
1508 * Flipping it to the positive side.
1509 */
1510 if( A->s < 0 && y != 0 )
1511 y = b - y;
1512
Paul Bakker5121ce52009-01-03 21:22:43 +00001513 *r = y;
1514
1515 return( 0 );
1516}
1517
1518/*
1519 * Fast Montgomery initialization (thanks to Tom St Denis)
1520 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001521static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001522{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001523 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001524 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00001525
1526 x = m0;
1527 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001528
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001529 for( i = biL; i >= 8; i /= 2 )
1530 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001531
1532 *mm = ~x + 1;
1533}
1534
1535/*
1536 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1537 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001538static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1539 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001540{
Paul Bakker23986e52011-04-24 08:57:21 +00001541 size_t i, n, m;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001542 mbedtls_mpi_uint u0, u1, *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00001543
1544 memset( T->p, 0, T->n * ciL );
1545
1546 d = T->p;
1547 n = N->n;
1548 m = ( B->n < n ) ? B->n : n;
1549
1550 for( i = 0; i < n; i++ )
1551 {
1552 /*
1553 * T = (T + u0*B + u1*N) / 2^biL
1554 */
1555 u0 = A->p[i];
1556 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1557
1558 mpi_mul_hlp( m, B->p, d, u0 );
1559 mpi_mul_hlp( n, N->p, d, u1 );
1560
1561 *d++ = u0; d[n + 1] = 0;
1562 }
1563
Paul Bakker66d5d072014-06-17 16:39:18 +02001564 memcpy( A->p, d, ( n + 1 ) * ciL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001565
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001566 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001567 mpi_sub_hlp( n, N->p, A->p );
1568 else
1569 /* prevent timing attacks */
1570 mpi_sub_hlp( n, A->p, T->p );
1571}
1572
1573/*
1574 * Montgomery reduction: A = A * R^-1 mod N
1575 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001576static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N, mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001577{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001578 mbedtls_mpi_uint z = 1;
1579 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001580
Paul Bakker8ddb6452013-02-27 14:56:33 +01001581 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001582 U.p = &z;
1583
1584 mpi_montmul( A, &U, N, mm, T );
1585}
1586
1587/*
1588 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1589 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001590int 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 +00001591{
Paul Bakker23986e52011-04-24 08:57:21 +00001592 int ret;
1593 size_t wbits, wsize, one = 1;
1594 size_t i, j, nblimbs;
1595 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001596 mbedtls_mpi_uint ei, mm, state;
1597 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00001598 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001599
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001600 if( mbedtls_mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
1601 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001602
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001603 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1604 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001605
1606 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001607 * Init temps and window size
1608 */
1609 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001610 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
1611 mbedtls_mpi_init( &Apos );
Paul Bakker5121ce52009-01-03 21:22:43 +00001612 memset( W, 0, sizeof( W ) );
1613
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001614 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00001615
1616 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1617 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1618
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001619 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1620 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Paul Bakkerb6d5f082011-11-25 11:52:11 +00001621
Paul Bakker5121ce52009-01-03 21:22:43 +00001622 j = N->n + 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001623 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1624 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1625 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001626
1627 /*
Paul Bakker50546922012-05-19 08:40:49 +00001628 * Compensate for negative A (and correct at the end)
1629 */
1630 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00001631 if( neg )
1632 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001633 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00001634 Apos.s = 1;
1635 A = &Apos;
1636 }
1637
1638 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001639 * If 1st call, pre-compute R^2 mod N
1640 */
1641 if( _RR == NULL || _RR->p == NULL )
1642 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001643 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1644 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1645 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001646
1647 if( _RR != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001648 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001649 }
1650 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001651 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001652
1653 /*
1654 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1655 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001656 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
1657 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Paul Bakkerc2024f42014-01-23 20:38:35 +01001658 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001659 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001660
1661 mpi_montmul( &W[1], &RR, N, mm, &T );
1662
1663 /*
1664 * X = R^2 * R^-1 mod N = R mod N
1665 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001666 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001667 mpi_montred( X, N, mm, &T );
1668
1669 if( wsize > 1 )
1670 {
1671 /*
1672 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1673 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001674 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001675
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001676 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1677 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001678
1679 for( i = 0; i < wsize - 1; i++ )
1680 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01001681
Paul Bakker5121ce52009-01-03 21:22:43 +00001682 /*
1683 * W[i] = W[i - 1] * W[1]
1684 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001685 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001686 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001687 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1688 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001689
1690 mpi_montmul( &W[i], &W[1], N, mm, &T );
1691 }
1692 }
1693
1694 nblimbs = E->n;
1695 bufsize = 0;
1696 nbits = 0;
1697 wbits = 0;
1698 state = 0;
1699
1700 while( 1 )
1701 {
1702 if( bufsize == 0 )
1703 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01001704 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001705 break;
1706
Paul Bakker0d7702c2013-10-29 16:18:35 +01001707 nblimbs--;
1708
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001709 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00001710 }
1711
1712 bufsize--;
1713
1714 ei = (E->p[nblimbs] >> bufsize) & 1;
1715
1716 /*
1717 * skip leading 0s
1718 */
1719 if( ei == 0 && state == 0 )
1720 continue;
1721
1722 if( ei == 0 && state == 1 )
1723 {
1724 /*
1725 * out of window, square X
1726 */
1727 mpi_montmul( X, X, N, mm, &T );
1728 continue;
1729 }
1730
1731 /*
1732 * add ei to current window
1733 */
1734 state = 2;
1735
1736 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02001737 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001738
1739 if( nbits == wsize )
1740 {
1741 /*
1742 * X = X^wsize R^-1 mod N
1743 */
1744 for( i = 0; i < wsize; i++ )
1745 mpi_montmul( X, X, N, mm, &T );
1746
1747 /*
1748 * X = X * W[wbits] R^-1 mod N
1749 */
1750 mpi_montmul( X, &W[wbits], N, mm, &T );
1751
1752 state--;
1753 nbits = 0;
1754 wbits = 0;
1755 }
1756 }
1757
1758 /*
1759 * process the remaining bits
1760 */
1761 for( i = 0; i < nbits; i++ )
1762 {
1763 mpi_montmul( X, X, N, mm, &T );
1764
1765 wbits <<= 1;
1766
Paul Bakker66d5d072014-06-17 16:39:18 +02001767 if( ( wbits & ( one << wsize ) ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001768 mpi_montmul( X, &W[1], N, mm, &T );
1769 }
1770
1771 /*
1772 * X = A^E * R * R^-1 mod N = A^E mod N
1773 */
1774 mpi_montred( X, N, mm, &T );
1775
Paul Bakkerf6198c12012-05-16 08:02:29 +00001776 if( neg )
1777 {
1778 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001779 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001780 }
1781
Paul Bakker5121ce52009-01-03 21:22:43 +00001782cleanup:
1783
Paul Bakker66d5d072014-06-17 16:39:18 +02001784 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001785 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001786
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001787 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Paul Bakker6c591fa2011-05-05 11:49:20 +00001788
Paul Bakker75a28602014-03-31 12:08:17 +02001789 if( _RR == NULL || _RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001790 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00001791
1792 return( ret );
1793}
1794
Paul Bakker5121ce52009-01-03 21:22:43 +00001795/*
1796 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1797 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001798int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001799{
Paul Bakker23986e52011-04-24 08:57:21 +00001800 int ret;
1801 size_t lz, lzt;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001802 mbedtls_mpi TG, TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001803
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001804 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001805
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001806 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
1807 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001808
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001809 lz = mbedtls_mpi_lsb( &TA );
1810 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001811
Paul Bakker66d5d072014-06-17 16:39:18 +02001812 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001813 lz = lzt;
1814
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001815 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
1816 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001817
Paul Bakker5121ce52009-01-03 21:22:43 +00001818 TA.s = TB.s = 1;
1819
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001820 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001821 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001822 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
1823 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001824
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001825 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001826 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001827 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
1828 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001829 }
1830 else
1831 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001832 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
1833 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001834 }
1835 }
1836
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001837 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
1838 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001839
1840cleanup:
1841
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001842 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001843
1844 return( ret );
1845}
1846
Paul Bakker33dc46b2014-04-30 16:11:39 +02001847/*
1848 * Fill X with size bytes of random.
1849 *
1850 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02001851 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02001852 * deterministic, eg for tests).
1853 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001854int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00001855 int (*f_rng)(void *, unsigned char *, size_t),
1856 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00001857{
Paul Bakker23986e52011-04-24 08:57:21 +00001858 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001859 unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
Paul Bakker33dc46b2014-04-30 16:11:39 +02001860
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001861 if( size > MBEDTLS_MPI_MAX_SIZE )
1862 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker287781a2011-03-26 13:18:49 +00001863
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001864 MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) );
1865 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) );
Paul Bakker287781a2011-03-26 13:18:49 +00001866
1867cleanup:
1868 return( ret );
1869}
1870
Paul Bakker5121ce52009-01-03 21:22:43 +00001871/*
1872 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1873 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001874int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001875{
1876 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001877 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001878
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001879 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 )
1880 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001881
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001882 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
1883 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
1884 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001885
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001886 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001887
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001888 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001889 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001890 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00001891 goto cleanup;
1892 }
1893
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001894 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
1895 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
1896 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
1897 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001898
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001899 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
1900 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
1901 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
1902 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001903
1904 do
1905 {
1906 while( ( TU.p[0] & 1 ) == 0 )
1907 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001908 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001909
1910 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1911 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001912 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
1913 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001914 }
1915
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001916 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
1917 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001918 }
1919
1920 while( ( TV.p[0] & 1 ) == 0 )
1921 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001922 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001923
1924 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1925 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001926 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
1927 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001928 }
1929
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001930 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
1931 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001932 }
1933
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001934 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001935 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001936 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
1937 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
1938 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001939 }
1940 else
1941 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001942 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
1943 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
1944 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001945 }
1946 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001947 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001948
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001949 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
1950 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001951
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001952 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
1953 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001954
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001955 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001956
1957cleanup:
1958
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001959 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
1960 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
1961 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001962
1963 return( ret );
1964}
1965
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001966#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00001967
Paul Bakker5121ce52009-01-03 21:22:43 +00001968static const int small_prime[] =
1969{
1970 3, 5, 7, 11, 13, 17, 19, 23,
1971 29, 31, 37, 41, 43, 47, 53, 59,
1972 61, 67, 71, 73, 79, 83, 89, 97,
1973 101, 103, 107, 109, 113, 127, 131, 137,
1974 139, 149, 151, 157, 163, 167, 173, 179,
1975 181, 191, 193, 197, 199, 211, 223, 227,
1976 229, 233, 239, 241, 251, 257, 263, 269,
1977 271, 277, 281, 283, 293, 307, 311, 313,
1978 317, 331, 337, 347, 349, 353, 359, 367,
1979 373, 379, 383, 389, 397, 401, 409, 419,
1980 421, 431, 433, 439, 443, 449, 457, 461,
1981 463, 467, 479, 487, 491, 499, 503, 509,
1982 521, 523, 541, 547, 557, 563, 569, 571,
1983 577, 587, 593, 599, 601, 607, 613, 617,
1984 619, 631, 641, 643, 647, 653, 659, 661,
1985 673, 677, 683, 691, 701, 709, 719, 727,
1986 733, 739, 743, 751, 757, 761, 769, 773,
1987 787, 797, 809, 811, 821, 823, 827, 829,
1988 839, 853, 857, 859, 863, 877, 881, 883,
1989 887, 907, 911, 919, 929, 937, 941, 947,
1990 953, 967, 971, 977, 983, 991, 997, -103
1991};
1992
1993/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001994 * Small divisors test (X must be positive)
1995 *
1996 * Return values:
1997 * 0: no small factor (possible prime, more tests needed)
1998 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001999 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002000 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00002001 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002002static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00002003{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002004 int ret = 0;
2005 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002006 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00002007
Paul Bakker5121ce52009-01-03 21:22:43 +00002008 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002009 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002010
2011 for( i = 0; small_prime[i] > 0; i++ )
2012 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002013 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002014 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002015
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002016 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002017
2018 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002019 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00002020 }
2021
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002022cleanup:
2023 return( ret );
2024}
2025
2026/*
2027 * Miller-Rabin pseudo-primality test (HAC 4.24)
2028 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002029static int mpi_miller_rabin( const mbedtls_mpi *X,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002030 int (*f_rng)(void *, unsigned char *, size_t),
2031 void *p_rng )
2032{
Pascal Junodb99183d2015-03-11 16:49:45 +01002033 int ret, count;
2034 size_t i, j, k, n, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002035 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002036
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002037 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
2038 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002039
Paul Bakker5121ce52009-01-03 21:22:43 +00002040 /*
2041 * W = |X| - 1
2042 * R = W >> lsb( W )
2043 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002044 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2045 s = mbedtls_mpi_lsb( &W );
2046 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2047 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002048
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002049 i = mbedtls_mpi_bitlen( X );
Paul Bakker5121ce52009-01-03 21:22:43 +00002050 /*
2051 * HAC, table 4.4
2052 */
2053 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
2054 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
2055 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
2056
2057 for( i = 0; i < n; i++ )
2058 {
2059 /*
2060 * pick a random A, 1 < A < |X| - 1
2061 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002062 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002063
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002064 if( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 )
Paul Bakkerb94081b2011-01-05 15:53:06 +00002065 {
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002066 j = mbedtls_mpi_bitlen( &A ) - mbedtls_mpi_bitlen( &W );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002067 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j + 1 ) );
Paul Bakkerb94081b2011-01-05 15:53:06 +00002068 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002069 A.p[0] |= 3;
2070
Pascal Junodb99183d2015-03-11 16:49:45 +01002071 count = 0;
2072 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002073 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002074
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002075 j = mbedtls_mpi_bitlen( &A );
2076 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002077 if (j > k) {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002078 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j - k ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002079 }
2080
2081 if (count++ > 30) {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002082 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Pascal Junodb99183d2015-03-11 16:49:45 +01002083 }
2084
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002085 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2086 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002087
2088 /*
2089 * A = A^R mod |X|
2090 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002091 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002092
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002093 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2094 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002095 continue;
2096
2097 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002098 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002099 {
2100 /*
2101 * A = A * A mod |X|
2102 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002103 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2104 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002105
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002106 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002107 break;
2108
2109 j++;
2110 }
2111
2112 /*
2113 * not prime if A != |X| - 1 or A == 1
2114 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002115 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2116 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002117 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002118 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002119 break;
2120 }
2121 }
2122
2123cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002124 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2125 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002126
2127 return( ret );
2128}
2129
2130/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002131 * Pseudo-primality test: small factors, then Miller-Rabin
2132 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002133int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002134 int (*f_rng)(void *, unsigned char *, size_t),
2135 void *p_rng )
2136{
2137 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002138 mbedtls_mpi XX;
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002139
2140 XX.s = 1;
2141 XX.n = X->n;
2142 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002143
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002144 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2145 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2146 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002147
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002148 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002149 return( 0 );
2150
2151 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2152 {
2153 if( ret == 1 )
2154 return( 0 );
2155
2156 return( ret );
2157 }
2158
2159 return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
2160}
2161
2162/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002163 * Prime number generation
2164 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002165int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002166 int (*f_rng)(void *, unsigned char *, size_t),
2167 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002168{
Paul Bakker23986e52011-04-24 08:57:21 +00002169 int ret;
2170 size_t k, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002171 mbedtls_mpi_uint r;
2172 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002173
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002174 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2175 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002176
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002177 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002178
2179 n = BITS_TO_LIMBS( nbits );
2180
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002181 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002182
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002183 k = mbedtls_mpi_bitlen( X );
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002184 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002185
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002186 mbedtls_mpi_set_bit( X, nbits-1, 1 );
Pascal Junodb99183d2015-03-11 16:49:45 +01002187
2188 X->p[0] |= 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00002189
2190 if( dh_flag == 0 )
2191 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002192 while( ( ret = mbedtls_mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002193 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002194 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002195 goto cleanup;
2196
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002197 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002198 }
2199 }
2200 else
2201 {
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002202 /*
2203 * An necessary condition for Y and X = 2Y + 1 to be prime
2204 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2205 * Make sure it is satisfied, while keeping X = 3 mod 4
2206 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002207
2208 X->p[0] |= 2;
2209
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002210 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002211 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002212 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002213 else if( r == 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002214 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002215
2216 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002217 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2218 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002219
2220 while( 1 )
2221 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002222 /*
2223 * First, check small factors for X and Y
2224 * before doing Miller-Rabin on any of them
2225 */
2226 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2227 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2228 ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
2229 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002230 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002231 break;
Paul Bakker5121ce52009-01-03 21:22:43 +00002232 }
2233
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002234 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002235 goto cleanup;
2236
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002237 /*
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002238 * Next candidates. We want to preserve Y = (X-1) / 2 and
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002239 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2240 * so up Y by 6 and X by 12.
2241 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002242 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2243 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002244 }
2245 }
2246
2247cleanup:
2248
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002249 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002250
2251 return( ret );
2252}
2253
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002254#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002255
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002256#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002257
Paul Bakker23986e52011-04-24 08:57:21 +00002258#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002259
2260static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2261{
2262 { 693, 609, 21 },
2263 { 1764, 868, 28 },
2264 { 768454923, 542167814, 1 }
2265};
2266
Paul Bakker5121ce52009-01-03 21:22:43 +00002267/*
2268 * Checkup routine
2269 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002270int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002271{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002272 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002273 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002274
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002275 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2276 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002277
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002278 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002279 "EFE021C2645FD1DC586E69184AF4A31E" \
2280 "D5F53E93B5F123FA41680867BA110131" \
2281 "944FE7952E2517337780CB0DB80E61AA" \
2282 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2283
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002284 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002285 "B2E7EFD37075B9F03FF989C7C5051C20" \
2286 "34D2A323810251127E7BF8625A4F49A5" \
2287 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2288 "5B5C25763222FEFCCFC38B832366C29E" ) );
2289
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002290 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002291 "0066A198186C18C10B2F5ED9B522752A" \
2292 "9830B69916E535C8F047518A889A43A5" \
2293 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2294
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002295 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002296
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002297 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002298 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2299 "9E857EA95A03512E2BAE7391688D264A" \
2300 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2301 "8001B72E848A38CAE1C65F78E56ABDEF" \
2302 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2303 "ECF677152EF804370C1A305CAF3B5BF1" \
2304 "30879B56C61DE584A0F53A2447A51E" ) );
2305
2306 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002307 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002308
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002309 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002310 {
2311 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002312 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002313
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002314 ret = 1;
2315 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002316 }
2317
2318 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002319 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002320
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002321 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002322
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002323 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002324 "256567336059E52CAE22925474705F39A94" ) );
2325
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002326 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002327 "6613F26162223DF488E9CD48CC132C7A" \
2328 "0AC93C701B001B092E4E5B9F73BCD27B" \
2329 "9EE50D0657C77F374E903CDFA4C642" ) );
2330
2331 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002332 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002333
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002334 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2335 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002336 {
2337 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002338 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002339
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002340 ret = 1;
2341 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002342 }
2343
2344 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002345 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002346
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002347 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002348
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002349 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002350 "36E139AEA55215609D2816998ED020BB" \
2351 "BD96C37890F65171D948E9BC7CBAA4D9" \
2352 "325D24D6A3C12710F10A09FA08AB87" ) );
2353
2354 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002355 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002356
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002357 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002358 {
2359 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002360 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002361
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002362 ret = 1;
2363 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002364 }
2365
2366 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002367 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002368
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002369 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002370
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002371 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002372 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2373 "C3DBA76456363A10869622EAC2DD84EC" \
2374 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2375
2376 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002377 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002378
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002379 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002380 {
2381 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002382 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002383
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002384 ret = 1;
2385 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002386 }
2387
2388 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002389 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002390
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002391 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002392 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002393
Paul Bakker66d5d072014-06-17 16:39:18 +02002394 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002395 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002396 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2397 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002398
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002399 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002400
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002401 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002402 {
2403 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002404 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002405
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002406 ret = 1;
2407 goto cleanup;
2408 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002409 }
2410
2411 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002412 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002413
Paul Bakker5121ce52009-01-03 21:22:43 +00002414cleanup:
2415
2416 if( ret != 0 && verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002417 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002418
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002419 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2420 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002421
2422 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002423 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002424
2425 return( ret );
2426}
2427
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002428#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002429
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002430#endif /* MBEDTLS_BIGNUM_C */