blob: 58a4cd2de515b0fe7d9bc1670a9d2d8159ae9ba9 [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 */
21/*
22 * This MPI implementation is based on:
23 *
24 * http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf
Simon Butcher334a87b2015-10-14 22:56:44 +010025 * http://www.stillhq.com/extracted/gnupg-api/mpi/
Paul Bakker5121ce52009-01-03 21:22:43 +000026 * http://math.libtomcrypt.com/files/tommath.pdf
27 */
28
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020029#if !defined(MBEDTLS_CONFIG_FILE)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000030#include "mbedtls/config.h"
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020031#else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020032#include MBEDTLS_CONFIG_FILE
Manuel Pégourié-Gonnardcef4ad22014-04-29 12:39:06 +020033#endif
Paul Bakker5121ce52009-01-03 21:22:43 +000034
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020035#if defined(MBEDTLS_BIGNUM_C)
Paul Bakker5121ce52009-01-03 21:22:43 +000036
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000037#include "mbedtls/bignum.h"
38#include "mbedtls/bn_mul.h"
Paul Bakker5121ce52009-01-03 21:22:43 +000039
Rich Evans00ab4702015-02-06 13:43:58 +000040#include <string.h>
41
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020042#if defined(MBEDTLS_PLATFORM_C)
Manuel Pégourié-Gonnard7f809972015-03-09 17:05:11 +000043#include "mbedtls/platform.h"
Paul Bakker6e339b52013-07-03 13:37:05 +020044#else
Rich Evans00ab4702015-02-06 13:43:58 +000045#include <stdio.h>
46#include <stdlib.h>
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020047#define mbedtls_printf printf
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +020048#define mbedtls_calloc calloc
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020049#define mbedtls_free free
Paul Bakker6e339b52013-07-03 13:37:05 +020050#endif
51
Paul Bakker34617722014-06-13 17:20:13 +020052/* Implementation that should never be optimized out by the compiler */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020053static void mbedtls_zeroize( void *v, size_t n ) {
Paul Bakker34617722014-06-13 17:20:13 +020054 volatile unsigned char *p = v; while( n-- ) *p++ = 0;
55}
56
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020057#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
Paul Bakker5121ce52009-01-03 21:22:43 +000058#define biL (ciL << 3) /* bits in limb */
59#define biH (ciL << 2) /* half limb size */
60
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +010061#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
62
Paul Bakker5121ce52009-01-03 21:22:43 +000063/*
64 * Convert between bits/chars and number of limbs
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020065 * Divide first in order to avoid potential overflows
Paul Bakker5121ce52009-01-03 21:22:43 +000066 */
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +020067#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
68#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
Paul Bakker5121ce52009-01-03 21:22:43 +000069
70/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000071 * Initialize one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000072 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020073void mbedtls_mpi_init( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000074{
Paul Bakker6c591fa2011-05-05 11:49:20 +000075 if( X == NULL )
76 return;
Paul Bakker5121ce52009-01-03 21:22:43 +000077
Paul Bakker6c591fa2011-05-05 11:49:20 +000078 X->s = 1;
79 X->n = 0;
80 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +000081}
82
83/*
Paul Bakker6c591fa2011-05-05 11:49:20 +000084 * Unallocate one MPI
Paul Bakker5121ce52009-01-03 21:22:43 +000085 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020086void mbedtls_mpi_free( mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +000087{
Paul Bakker6c591fa2011-05-05 11:49:20 +000088 if( X == NULL )
89 return;
Paul Bakker5121ce52009-01-03 21:22:43 +000090
Paul Bakker6c591fa2011-05-05 11:49:20 +000091 if( X->p != NULL )
Paul Bakker5121ce52009-01-03 21:22:43 +000092 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +020093 mbedtls_zeroize( X->p, X->n * ciL );
94 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +000095 }
96
Paul Bakker6c591fa2011-05-05 11:49:20 +000097 X->s = 1;
98 X->n = 0;
99 X->p = NULL;
Paul Bakker5121ce52009-01-03 21:22:43 +0000100}
101
102/*
103 * Enlarge to the specified number of limbs
104 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200105int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
Paul Bakker5121ce52009-01-03 21:22:43 +0000106{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200107 mbedtls_mpi_uint *p;
Paul Bakker5121ce52009-01-03 21:22:43 +0000108
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200109 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200110 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakkerf9688572011-05-05 10:00:45 +0000111
Paul Bakker5121ce52009-01-03 21:22:43 +0000112 if( X->n < nblimbs )
113 {
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +0200114 if( ( p = mbedtls_calloc( nblimbs, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200115 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Paul Bakker5121ce52009-01-03 21:22:43 +0000116
Paul Bakker5121ce52009-01-03 21:22:43 +0000117 if( X->p != NULL )
118 {
119 memcpy( p, X->p, X->n * ciL );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200120 mbedtls_zeroize( X->p, X->n * ciL );
121 mbedtls_free( X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000122 }
123
124 X->n = nblimbs;
125 X->p = p;
126 }
127
128 return( 0 );
129}
130
131/*
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100132 * Resize down as much as possible,
133 * while keeping at least the specified number of limbs
134 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200135int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100136{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200137 mbedtls_mpi_uint *p;
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100138 size_t i;
139
140 /* Actually resize up in this case */
141 if( X->n <= nblimbs )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200142 return( mbedtls_mpi_grow( X, nblimbs ) );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100143
144 for( i = X->n - 1; i > 0; i-- )
145 if( X->p[i] != 0 )
146 break;
147 i++;
148
149 if( i < nblimbs )
150 i = nblimbs;
151
Manuel Pégourié-Gonnard7551cb92015-05-26 16:04:06 +0200152 if( ( p = mbedtls_calloc( i, ciL ) ) == NULL )
Manuel Pégourié-Gonnard6a8ca332015-05-28 09:33:39 +0200153 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100154
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100155 if( X->p != NULL )
156 {
157 memcpy( p, X->p, i * ciL );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200158 mbedtls_zeroize( X->p, X->n * ciL );
159 mbedtls_free( X->p );
Manuel Pégourié-Gonnard58681632013-11-21 10:39:37 +0100160 }
161
162 X->n = i;
163 X->p = p;
164
165 return( 0 );
166}
167
168/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000169 * Copy the contents of Y into X
170 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200171int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000172{
Paul Bakker23986e52011-04-24 08:57:21 +0000173 int ret;
174 size_t i;
Paul Bakker5121ce52009-01-03 21:22:43 +0000175
176 if( X == Y )
177 return( 0 );
178
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200179 if( Y->p == NULL )
180 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200181 mbedtls_mpi_free( X );
Manuel Pégourié-Gonnardf4999932013-08-12 17:02:59 +0200182 return( 0 );
183 }
184
Paul Bakker5121ce52009-01-03 21:22:43 +0000185 for( i = Y->n - 1; i > 0; i-- )
186 if( Y->p[i] != 0 )
187 break;
188 i++;
189
190 X->s = Y->s;
191
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200192 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000193
194 memset( X->p, 0, X->n * ciL );
195 memcpy( X->p, Y->p, i * ciL );
196
197cleanup:
198
199 return( ret );
200}
201
202/*
203 * Swap the contents of X and Y
204 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200205void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000206{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200207 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000208
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200209 memcpy( &T, X, sizeof( mbedtls_mpi ) );
210 memcpy( X, Y, sizeof( mbedtls_mpi ) );
211 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000212}
213
214/*
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100215 * Conditionally assign X = Y, without leaking information
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100216 * about whether the assignment was made or not.
217 * (Leaking information about the respective sizes of X and Y is ok however.)
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100218 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200219int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100220{
221 int ret = 0;
222 size_t i;
223
Pascal Junodb99183d2015-03-11 16:49:45 +0100224 /* make sure assign is 0 or 1 in a time-constant manner */
225 assign = (assign | (unsigned char)-assign) >> 7;
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100226
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200227 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100228
Paul Bakker66d5d072014-06-17 16:39:18 +0200229 X->s = X->s * ( 1 - assign ) + Y->s * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100230
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100231 for( i = 0; i < Y->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200232 X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100233
Manuel Pégourié-Gonnard96c7a922013-11-25 18:28:53 +0100234 for( ; i < X->n; i++ )
Paul Bakker66d5d072014-06-17 16:39:18 +0200235 X->p[i] *= ( 1 - assign );
Manuel Pégourié-Gonnard71c2c212013-11-21 16:56:39 +0100236
237cleanup:
238 return( ret );
239}
240
241/*
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100242 * Conditionally swap X and Y, without leaking information
243 * about whether the swap was made or not.
244 * Here it is not ok to simply swap the pointers, which whould lead to
245 * different memory access patterns when X and Y are used afterwards.
246 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200247int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100248{
249 int ret, s;
250 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200251 mbedtls_mpi_uint tmp;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100252
253 if( X == Y )
254 return( 0 );
255
Pascal Junodb99183d2015-03-11 16:49:45 +0100256 /* make sure swap is 0 or 1 in a time-constant manner */
257 swap = (swap | (unsigned char)-swap) >> 7;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100258
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200259 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
260 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100261
262 s = X->s;
Paul Bakker66d5d072014-06-17 16:39:18 +0200263 X->s = X->s * ( 1 - swap ) + Y->s * swap;
264 Y->s = Y->s * ( 1 - swap ) + s * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100265
266
267 for( i = 0; i < X->n; i++ )
268 {
269 tmp = X->p[i];
Paul Bakker66d5d072014-06-17 16:39:18 +0200270 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
271 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
Manuel Pégourié-Gonnarda60fe892013-12-04 21:41:50 +0100272 }
273
274cleanup:
275 return( ret );
276}
277
278/*
Paul Bakker5121ce52009-01-03 21:22:43 +0000279 * Set value from integer
280 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200281int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000282{
283 int ret;
284
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200285 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000286 memset( X->p, 0, X->n * ciL );
287
288 X->p[0] = ( z < 0 ) ? -z : z;
289 X->s = ( z < 0 ) ? -1 : 1;
290
291cleanup:
292
293 return( ret );
294}
295
296/*
Paul Bakker2f5947e2011-05-18 15:47:11 +0000297 * Get a specific bit
298 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200299int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000300{
301 if( X->n * biL <= pos )
302 return( 0 );
303
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200304 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000305}
306
307/*
308 * Set a bit to a specific value of 0 or 1
309 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200310int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
Paul Bakker2f5947e2011-05-18 15:47:11 +0000311{
312 int ret = 0;
313 size_t off = pos / biL;
314 size_t idx = pos % biL;
315
316 if( val != 0 && val != 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200317 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker9af723c2014-05-01 13:03:14 +0200318
Paul Bakker2f5947e2011-05-18 15:47:11 +0000319 if( X->n * biL <= pos )
320 {
321 if( val == 0 )
Paul Bakkerd8bb8262014-06-17 14:06:49 +0200322 return( 0 );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000323
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200324 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
Paul Bakker2f5947e2011-05-18 15:47:11 +0000325 }
326
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200327 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
328 X->p[off] |= (mbedtls_mpi_uint) val << idx;
Paul Bakker2f5947e2011-05-18 15:47:11 +0000329
330cleanup:
Paul Bakker9af723c2014-05-01 13:03:14 +0200331
Paul Bakker2f5947e2011-05-18 15:47:11 +0000332 return( ret );
333}
334
335/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200336 * Return the number of less significant zero-bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000337 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200338size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000339{
Paul Bakker23986e52011-04-24 08:57:21 +0000340 size_t i, j, count = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000341
342 for( i = 0; i < X->n; i++ )
Paul Bakkerf9688572011-05-05 10:00:45 +0000343 for( j = 0; j < biL; j++, count++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000344 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
345 return( count );
346
347 return( 0 );
348}
349
350/*
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200351 * Return the number of bits
Paul Bakker5121ce52009-01-03 21:22:43 +0000352 */
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200353size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000354{
Paul Bakker23986e52011-04-24 08:57:21 +0000355 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000356
Manuel Pégourié-Gonnard770b5e12015-04-29 17:02:01 +0200357 if( X->n == 0 )
358 return( 0 );
359
Paul Bakker5121ce52009-01-03 21:22:43 +0000360 for( i = X->n - 1; i > 0; i-- )
361 if( X->p[i] != 0 )
362 break;
363
Paul Bakker23986e52011-04-24 08:57:21 +0000364 for( j = biL; j > 0; j-- )
365 if( ( ( X->p[i] >> ( j - 1 ) ) & 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000366 break;
367
Paul Bakker23986e52011-04-24 08:57:21 +0000368 return( ( i * biL ) + j );
Paul Bakker5121ce52009-01-03 21:22:43 +0000369}
370
371/*
372 * Return the total size in bytes
373 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200374size_t mbedtls_mpi_size( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +0000375{
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200376 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000377}
378
379/*
380 * Convert an ASCII character to digit value
381 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200382static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
Paul Bakker5121ce52009-01-03 21:22:43 +0000383{
384 *d = 255;
385
386 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
387 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
388 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
389
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200390 if( *d >= (mbedtls_mpi_uint) radix )
391 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
Paul Bakker5121ce52009-01-03 21:22:43 +0000392
393 return( 0 );
394}
395
396/*
397 * Import from an ASCII string
398 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200399int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
Paul Bakker5121ce52009-01-03 21:22:43 +0000400{
Paul Bakker23986e52011-04-24 08:57:21 +0000401 int ret;
402 size_t i, j, slen, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200403 mbedtls_mpi_uint d;
404 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000405
406 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200407 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000408
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200409 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000410
Paul Bakkerff60ee62010-03-16 21:09:09 +0000411 slen = strlen( s );
412
Paul Bakker5121ce52009-01-03 21:22:43 +0000413 if( radix == 16 )
414 {
Manuel Pégourié-Gonnard2d708342015-10-05 15:23:11 +0100415 if( slen > MPI_SIZE_T_MAX >> 2 )
Manuel Pégourié-Gonnard58fb4952015-09-28 13:48:04 +0200416 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
417
Paul Bakkerff60ee62010-03-16 21:09:09 +0000418 n = BITS_TO_LIMBS( slen << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000419
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200420 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
421 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000422
Paul Bakker23986e52011-04-24 08:57:21 +0000423 for( i = slen, j = 0; i > 0; i--, j++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000424 {
Paul Bakker23986e52011-04-24 08:57:21 +0000425 if( i == 1 && s[i - 1] == '-' )
Paul Bakker5121ce52009-01-03 21:22:43 +0000426 {
427 X->s = -1;
428 break;
429 }
430
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200431 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
Paul Bakker66d5d072014-06-17 16:39:18 +0200432 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000433 }
434 }
435 else
436 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200437 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000438
Paul Bakkerff60ee62010-03-16 21:09:09 +0000439 for( i = 0; i < slen; i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000440 {
441 if( i == 0 && s[i] == '-' )
442 {
443 X->s = -1;
444 continue;
445 }
446
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200447 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
448 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000449
450 if( X->s == 1 )
451 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200452 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000453 }
454 else
455 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200456 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
Paul Bakker05feca62009-06-20 08:22:43 +0000457 }
Paul Bakker5121ce52009-01-03 21:22:43 +0000458 }
459 }
460
461cleanup:
462
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200463 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000464
465 return( ret );
466}
467
468/*
469 * Helper to write the digits high-order first
470 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200471static int mpi_write_hlp( mbedtls_mpi *X, int radix, char **p )
Paul Bakker5121ce52009-01-03 21:22:43 +0000472{
473 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200474 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +0000475
476 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200477 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000478
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200479 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
480 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000481
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200482 if( mbedtls_mpi_cmp_int( X, 0 ) != 0 )
483 MBEDTLS_MPI_CHK( mpi_write_hlp( X, radix, p ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000484
485 if( r < 10 )
486 *(*p)++ = (char)( r + 0x30 );
487 else
488 *(*p)++ = (char)( r + 0x37 );
489
490cleanup:
491
492 return( ret );
493}
494
495/*
496 * Export into an ASCII string
497 */
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100498int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
499 char *buf, size_t buflen, size_t *olen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000500{
Paul Bakker23986e52011-04-24 08:57:21 +0000501 int ret = 0;
502 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000503 char *p;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200504 mbedtls_mpi T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000505
506 if( radix < 2 || radix > 16 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200507 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +0000508
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200509 n = mbedtls_mpi_bitlen( X );
Paul Bakker5121ce52009-01-03 21:22:43 +0000510 if( radix >= 4 ) n >>= 1;
511 if( radix >= 16 ) n >>= 1;
512 n += 3;
513
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100514 if( buflen < n )
Paul Bakker5121ce52009-01-03 21:22:43 +0000515 {
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100516 *olen = n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200517 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000518 }
519
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100520 p = buf;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200521 mbedtls_mpi_init( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000522
523 if( X->s == -1 )
524 *p++ = '-';
525
526 if( radix == 16 )
527 {
Paul Bakker23986e52011-04-24 08:57:21 +0000528 int c;
529 size_t i, j, k;
Paul Bakker5121ce52009-01-03 21:22:43 +0000530
Paul Bakker23986e52011-04-24 08:57:21 +0000531 for( i = X->n, k = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000532 {
Paul Bakker23986e52011-04-24 08:57:21 +0000533 for( j = ciL; j > 0; j-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000534 {
Paul Bakker23986e52011-04-24 08:57:21 +0000535 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
Paul Bakker5121ce52009-01-03 21:22:43 +0000536
Paul Bakker6c343d72014-07-10 14:36:19 +0200537 if( c == 0 && k == 0 && ( i + j ) != 2 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000538 continue;
539
Paul Bakker98fe5ea2012-10-24 11:17:48 +0000540 *(p++) = "0123456789ABCDEF" [c / 16];
Paul Bakkerd2c167e2012-10-30 07:49:19 +0000541 *(p++) = "0123456789ABCDEF" [c % 16];
Paul Bakker5121ce52009-01-03 21:22:43 +0000542 k = 1;
543 }
544 }
545 }
546 else
547 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200548 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
Paul Bakkerce40a6d2009-06-23 19:46:08 +0000549
550 if( T.s == -1 )
551 T.s = 1;
552
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200553 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000554 }
555
556 *p++ = '\0';
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100557 *olen = p - buf;
Paul Bakker5121ce52009-01-03 21:22:43 +0000558
559cleanup:
560
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200561 mbedtls_mpi_free( &T );
Paul Bakker5121ce52009-01-03 21:22:43 +0000562
563 return( ret );
564}
565
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200566#if defined(MBEDTLS_FS_IO)
Paul Bakker5121ce52009-01-03 21:22:43 +0000567/*
568 * Read X from an opened file
569 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200570int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
Paul Bakker5121ce52009-01-03 21:22:43 +0000571{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200572 mbedtls_mpi_uint d;
Paul Bakker23986e52011-04-24 08:57:21 +0000573 size_t slen;
Paul Bakker5121ce52009-01-03 21:22:43 +0000574 char *p;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000575 /*
Paul Bakkercb37aa52011-11-30 16:00:20 +0000576 * Buffer should have space for (short) label and decimal formatted MPI,
577 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000578 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200579 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000580
581 memset( s, 0, sizeof( s ) );
582 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200583 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000584
585 slen = strlen( s );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000586 if( slen == sizeof( s ) - 2 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200587 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakkercb37aa52011-11-30 16:00:20 +0000588
Paul Bakker5121ce52009-01-03 21:22:43 +0000589 if( s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
590 if( s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
591
592 p = s + slen;
593 while( --p >= s )
594 if( mpi_get_digit( &d, radix, *p ) != 0 )
595 break;
596
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200597 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000598}
599
600/*
601 * Write X into an opened file (or stdout if fout == NULL)
602 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200603int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
Paul Bakker5121ce52009-01-03 21:22:43 +0000604{
Paul Bakker23986e52011-04-24 08:57:21 +0000605 int ret;
606 size_t n, slen, plen;
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000607 /*
Paul Bakker5531c6d2012-09-26 19:20:46 +0000608 * Buffer should have space for (short) label and decimal formatted MPI,
609 * newline characters and '\0'
Paul Bakkerfe3256e2011-11-25 12:11:43 +0000610 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200611 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Paul Bakker5121ce52009-01-03 21:22:43 +0000612
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100613 memset( s, 0, sizeof( s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000614
Manuel Pégourié-Gonnardf79b4252015-06-02 15:41:48 +0100615 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000616
617 if( p == NULL ) p = "";
618
619 plen = strlen( p );
620 slen = strlen( s );
621 s[slen++] = '\r';
622 s[slen++] = '\n';
623
624 if( fout != NULL )
625 {
626 if( fwrite( p, 1, plen, fout ) != plen ||
627 fwrite( s, 1, slen, fout ) != slen )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200628 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
Paul Bakker5121ce52009-01-03 21:22:43 +0000629 }
630 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200631 mbedtls_printf( "%s%s", p, s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000632
633cleanup:
634
635 return( ret );
636}
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200637#endif /* MBEDTLS_FS_IO */
Paul Bakker5121ce52009-01-03 21:22:43 +0000638
639/*
640 * Import X from unsigned binary data, big endian
641 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200642int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000643{
Paul Bakker23986e52011-04-24 08:57:21 +0000644 int ret;
645 size_t i, j, n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000646
647 for( n = 0; n < buflen; n++ )
648 if( buf[n] != 0 )
649 break;
650
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200651 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, CHARS_TO_LIMBS( buflen - n ) ) );
652 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000653
Paul Bakker23986e52011-04-24 08:57:21 +0000654 for( i = buflen, j = 0; i > n; i--, j++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200655 X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
Paul Bakker5121ce52009-01-03 21:22:43 +0000656
657cleanup:
658
659 return( ret );
660}
661
662/*
663 * Export X into unsigned binary data, big endian
664 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200665int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen )
Paul Bakker5121ce52009-01-03 21:22:43 +0000666{
Paul Bakker23986e52011-04-24 08:57:21 +0000667 size_t i, j, n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000668
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200669 n = mbedtls_mpi_size( X );
Paul Bakker5121ce52009-01-03 21:22:43 +0000670
671 if( buflen < n )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200672 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
Paul Bakker5121ce52009-01-03 21:22:43 +0000673
674 memset( buf, 0, buflen );
675
676 for( i = buflen - 1, j = 0; n > 0; i--, j++, n-- )
677 buf[i] = (unsigned char)( X->p[j / ciL] >> ((j % ciL) << 3) );
678
679 return( 0 );
680}
681
682/*
683 * Left-shift: X <<= count
684 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200685int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000686{
Paul Bakker23986e52011-04-24 08:57:21 +0000687 int ret;
688 size_t i, v0, t1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200689 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000690
691 v0 = count / (biL );
692 t1 = count & (biL - 1);
693
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +0200694 i = mbedtls_mpi_bitlen( X ) + count;
Paul Bakker5121ce52009-01-03 21:22:43 +0000695
Paul Bakkerf9688572011-05-05 10:00:45 +0000696 if( X->n * biL < i )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200697 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000698
699 ret = 0;
700
701 /*
702 * shift by count / limb_size
703 */
704 if( v0 > 0 )
705 {
Paul Bakker23986e52011-04-24 08:57:21 +0000706 for( i = X->n; i > v0; i-- )
707 X->p[i - 1] = X->p[i - v0 - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000708
Paul Bakker23986e52011-04-24 08:57:21 +0000709 for( ; i > 0; i-- )
710 X->p[i - 1] = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000711 }
712
713 /*
714 * shift by count % limb_size
715 */
716 if( t1 > 0 )
717 {
718 for( i = v0; i < X->n; i++ )
719 {
720 r1 = X->p[i] >> (biL - t1);
721 X->p[i] <<= t1;
722 X->p[i] |= r0;
723 r0 = r1;
724 }
725 }
726
727cleanup:
728
729 return( ret );
730}
731
732/*
733 * Right-shift: X >>= count
734 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200735int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
Paul Bakker5121ce52009-01-03 21:22:43 +0000736{
Paul Bakker23986e52011-04-24 08:57:21 +0000737 size_t i, v0, v1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200738 mbedtls_mpi_uint r0 = 0, r1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000739
740 v0 = count / biL;
741 v1 = count & (biL - 1);
742
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100743 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200744 return mbedtls_mpi_lset( X, 0 );
Manuel Pégourié-Gonnarde44ec102012-11-17 12:42:51 +0100745
Paul Bakker5121ce52009-01-03 21:22:43 +0000746 /*
747 * shift by count / limb_size
748 */
749 if( v0 > 0 )
750 {
751 for( i = 0; i < X->n - v0; i++ )
752 X->p[i] = X->p[i + v0];
753
754 for( ; i < X->n; i++ )
755 X->p[i] = 0;
756 }
757
758 /*
759 * shift by count % limb_size
760 */
761 if( v1 > 0 )
762 {
Paul Bakker23986e52011-04-24 08:57:21 +0000763 for( i = X->n; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000764 {
Paul Bakker23986e52011-04-24 08:57:21 +0000765 r1 = X->p[i - 1] << (biL - v1);
766 X->p[i - 1] >>= v1;
767 X->p[i - 1] |= r0;
Paul Bakker5121ce52009-01-03 21:22:43 +0000768 r0 = r1;
769 }
770 }
771
772 return( 0 );
773}
774
775/*
776 * Compare unsigned values
777 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200778int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000779{
Paul Bakker23986e52011-04-24 08:57:21 +0000780 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000781
Paul Bakker23986e52011-04-24 08:57:21 +0000782 for( i = X->n; i > 0; i-- )
783 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000784 break;
785
Paul Bakker23986e52011-04-24 08:57:21 +0000786 for( j = Y->n; j > 0; j-- )
787 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000788 break;
789
Paul Bakker23986e52011-04-24 08:57:21 +0000790 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000791 return( 0 );
792
793 if( i > j ) return( 1 );
794 if( j > i ) return( -1 );
795
Paul Bakker23986e52011-04-24 08:57:21 +0000796 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000797 {
Paul Bakker23986e52011-04-24 08:57:21 +0000798 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
799 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
Paul Bakker5121ce52009-01-03 21:22:43 +0000800 }
801
802 return( 0 );
803}
804
805/*
806 * Compare signed values
807 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200808int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
Paul Bakker5121ce52009-01-03 21:22:43 +0000809{
Paul Bakker23986e52011-04-24 08:57:21 +0000810 size_t i, j;
Paul Bakker5121ce52009-01-03 21:22:43 +0000811
Paul Bakker23986e52011-04-24 08:57:21 +0000812 for( i = X->n; i > 0; i-- )
813 if( X->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000814 break;
815
Paul Bakker23986e52011-04-24 08:57:21 +0000816 for( j = Y->n; j > 0; j-- )
817 if( Y->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000818 break;
819
Paul Bakker23986e52011-04-24 08:57:21 +0000820 if( i == 0 && j == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000821 return( 0 );
822
823 if( i > j ) return( X->s );
Paul Bakker0c8f73b2012-03-22 14:08:57 +0000824 if( j > i ) return( -Y->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000825
826 if( X->s > 0 && Y->s < 0 ) return( 1 );
827 if( Y->s > 0 && X->s < 0 ) return( -1 );
828
Paul Bakker23986e52011-04-24 08:57:21 +0000829 for( ; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +0000830 {
Paul Bakker23986e52011-04-24 08:57:21 +0000831 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
832 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
Paul Bakker5121ce52009-01-03 21:22:43 +0000833 }
834
835 return( 0 );
836}
837
838/*
839 * Compare signed values
840 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200841int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
Paul Bakker5121ce52009-01-03 21:22:43 +0000842{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200843 mbedtls_mpi Y;
844 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +0000845
846 *p = ( z < 0 ) ? -z : z;
847 Y.s = ( z < 0 ) ? -1 : 1;
848 Y.n = 1;
849 Y.p = p;
850
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200851 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000852}
853
854/*
855 * Unsigned addition: X = |A| + |B| (HAC 14.7)
856 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200857int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000858{
Paul Bakker23986e52011-04-24 08:57:21 +0000859 int ret;
860 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200861 mbedtls_mpi_uint *o, *p, c;
Paul Bakker5121ce52009-01-03 21:22:43 +0000862
863 if( X == B )
864 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200865 const mbedtls_mpi *T = A; A = X; B = T;
Paul Bakker5121ce52009-01-03 21:22:43 +0000866 }
867
868 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200869 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker9af723c2014-05-01 13:03:14 +0200870
Paul Bakkerf7ca7b92009-06-20 10:31:06 +0000871 /*
872 * X should always be positive as a result of unsigned additions.
873 */
874 X->s = 1;
Paul Bakker5121ce52009-01-03 21:22:43 +0000875
Paul Bakker23986e52011-04-24 08:57:21 +0000876 for( j = B->n; j > 0; j-- )
877 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000878 break;
879
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200880 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000881
882 o = B->p; p = X->p; c = 0;
883
Paul Bakker23986e52011-04-24 08:57:21 +0000884 for( i = 0; i < j; i++, o++, p++ )
Paul Bakker5121ce52009-01-03 21:22:43 +0000885 {
886 *p += c; c = ( *p < c );
887 *p += *o; c += ( *p < *o );
888 }
889
890 while( c != 0 )
891 {
892 if( i >= X->n )
893 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200894 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000895 p = X->p + i;
896 }
897
Paul Bakker2d319fd2012-09-16 21:34:26 +0000898 *p += c; c = ( *p < c ); i++; p++;
Paul Bakker5121ce52009-01-03 21:22:43 +0000899 }
900
901cleanup:
902
903 return( ret );
904}
905
906/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200907 * Helper for mbedtls_mpi subtraction
Paul Bakker5121ce52009-01-03 21:22:43 +0000908 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200909static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d )
Paul Bakker5121ce52009-01-03 21:22:43 +0000910{
Paul Bakker23986e52011-04-24 08:57:21 +0000911 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200912 mbedtls_mpi_uint c, z;
Paul Bakker5121ce52009-01-03 21:22:43 +0000913
914 for( i = c = 0; i < n; i++, s++, d++ )
915 {
916 z = ( *d < c ); *d -= c;
917 c = ( *d < *s ) + z; *d -= *s;
918 }
919
920 while( c != 0 )
921 {
922 z = ( *d < c ); *d -= c;
923 c = z; i++; d++;
924 }
925}
926
927/*
Paul Bakker60b1d102013-10-29 10:02:51 +0100928 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
Paul Bakker5121ce52009-01-03 21:22:43 +0000929 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200930int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000931{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200932 mbedtls_mpi TB;
Paul Bakker23986e52011-04-24 08:57:21 +0000933 int ret;
934 size_t n;
Paul Bakker5121ce52009-01-03 21:22:43 +0000935
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200936 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
937 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +0000938
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200939 mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +0000940
941 if( X == B )
942 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200943 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000944 B = &TB;
945 }
946
947 if( X != A )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200948 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000949
Paul Bakker1ef7a532009-06-20 10:50:55 +0000950 /*
Paul Bakker60b1d102013-10-29 10:02:51 +0100951 * X should always be positive as a result of unsigned subtractions.
Paul Bakker1ef7a532009-06-20 10:50:55 +0000952 */
953 X->s = 1;
954
Paul Bakker5121ce52009-01-03 21:22:43 +0000955 ret = 0;
956
Paul Bakker23986e52011-04-24 08:57:21 +0000957 for( n = B->n; n > 0; n-- )
958 if( B->p[n - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000959 break;
960
Paul Bakker23986e52011-04-24 08:57:21 +0000961 mpi_sub_hlp( n, B->p, X->p );
Paul Bakker5121ce52009-01-03 21:22:43 +0000962
963cleanup:
964
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200965 mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +0000966
967 return( ret );
968}
969
970/*
971 * Signed addition: X = A + B
972 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200973int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +0000974{
975 int ret, s = A->s;
976
977 if( A->s * B->s < 0 )
978 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200979 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +0000980 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200981 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000982 X->s = s;
983 }
984 else
985 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200986 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000987 X->s = -s;
988 }
989 }
990 else
991 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +0200992 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +0000993 X->s = s;
994 }
995
996cleanup:
997
998 return( ret );
999}
1000
1001/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001002 * Signed subtraction: X = A - B
Paul Bakker5121ce52009-01-03 21:22:43 +00001003 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001004int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001005{
1006 int ret, s = A->s;
1007
1008 if( A->s * B->s > 0 )
1009 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001010 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001011 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001012 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001013 X->s = s;
1014 }
1015 else
1016 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001017 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001018 X->s = -s;
1019 }
1020 }
1021 else
1022 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001023 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001024 X->s = s;
1025 }
1026
1027cleanup:
1028
1029 return( ret );
1030}
1031
1032/*
1033 * Signed addition: X = A + b
1034 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001035int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001036{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001037 mbedtls_mpi _B;
1038 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001039
1040 p[0] = ( b < 0 ) ? -b : b;
1041 _B.s = ( b < 0 ) ? -1 : 1;
1042 _B.n = 1;
1043 _B.p = p;
1044
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001045 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001046}
1047
1048/*
Paul Bakker60b1d102013-10-29 10:02:51 +01001049 * Signed subtraction: X = A - b
Paul Bakker5121ce52009-01-03 21:22:43 +00001050 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001051int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001052{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001053 mbedtls_mpi _B;
1054 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001055
1056 p[0] = ( b < 0 ) ? -b : b;
1057 _B.s = ( b < 0 ) ? -1 : 1;
1058 _B.n = 1;
1059 _B.p = p;
1060
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001061 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001062}
1063
1064/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001065 * Helper for mbedtls_mpi multiplication
Paul Bakkerfc4f46f2013-06-24 19:23:56 +02001066 */
1067static
1068#if defined(__APPLE__) && defined(__arm__)
1069/*
1070 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1071 * appears to need this to prevent bad ARM code generation at -O3.
1072 */
1073__attribute__ ((noinline))
1074#endif
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001075void 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 +00001076{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001077 mbedtls_mpi_uint c = 0, t = 0;
Paul Bakker5121ce52009-01-03 21:22:43 +00001078
1079#if defined(MULADDC_HUIT)
1080 for( ; i >= 8; i -= 8 )
1081 {
1082 MULADDC_INIT
1083 MULADDC_HUIT
1084 MULADDC_STOP
1085 }
1086
1087 for( ; i > 0; i-- )
1088 {
1089 MULADDC_INIT
1090 MULADDC_CORE
1091 MULADDC_STOP
1092 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001093#else /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001094 for( ; i >= 16; i -= 16 )
1095 {
1096 MULADDC_INIT
1097 MULADDC_CORE MULADDC_CORE
1098 MULADDC_CORE MULADDC_CORE
1099 MULADDC_CORE MULADDC_CORE
1100 MULADDC_CORE MULADDC_CORE
1101
1102 MULADDC_CORE MULADDC_CORE
1103 MULADDC_CORE MULADDC_CORE
1104 MULADDC_CORE MULADDC_CORE
1105 MULADDC_CORE MULADDC_CORE
1106 MULADDC_STOP
1107 }
1108
1109 for( ; i >= 8; i -= 8 )
1110 {
1111 MULADDC_INIT
1112 MULADDC_CORE MULADDC_CORE
1113 MULADDC_CORE MULADDC_CORE
1114
1115 MULADDC_CORE MULADDC_CORE
1116 MULADDC_CORE MULADDC_CORE
1117 MULADDC_STOP
1118 }
1119
1120 for( ; i > 0; i-- )
1121 {
1122 MULADDC_INIT
1123 MULADDC_CORE
1124 MULADDC_STOP
1125 }
Paul Bakker9af723c2014-05-01 13:03:14 +02001126#endif /* MULADDC_HUIT */
Paul Bakker5121ce52009-01-03 21:22:43 +00001127
1128 t++;
1129
1130 do {
1131 *d += c; c = ( *d < c ); d++;
1132 }
1133 while( c != 0 );
1134}
1135
1136/*
1137 * Baseline multiplication: X = A * B (HAC 14.12)
1138 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001139int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001140{
Paul Bakker23986e52011-04-24 08:57:21 +00001141 int ret;
1142 size_t i, j;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001143 mbedtls_mpi TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001144
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001145 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001146
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001147 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1148 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
Paul Bakker5121ce52009-01-03 21:22:43 +00001149
Paul Bakker23986e52011-04-24 08:57:21 +00001150 for( i = A->n; i > 0; i-- )
1151 if( A->p[i - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001152 break;
1153
Paul Bakker23986e52011-04-24 08:57:21 +00001154 for( j = B->n; j > 0; j-- )
1155 if( B->p[j - 1] != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001156 break;
1157
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001158 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1159 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001160
Paul Bakker23986e52011-04-24 08:57:21 +00001161 for( i++; j > 0; j-- )
1162 mpi_mul_hlp( i - 1, A->p, X->p + j - 1, B->p[j - 1] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001163
1164 X->s = A->s * B->s;
1165
1166cleanup:
1167
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001168 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001169
1170 return( ret );
1171}
1172
1173/*
1174 * Baseline multiplication: X = A * b
1175 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001176int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001177{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001178 mbedtls_mpi _B;
1179 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001180
1181 _B.s = 1;
1182 _B.n = 1;
1183 _B.p = p;
1184 p[0] = b;
1185
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001186 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001187}
1188
1189/*
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001190 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
Paul Bakker5121ce52009-01-03 21:22:43 +00001191 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001192int 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 +00001193{
Paul Bakker23986e52011-04-24 08:57:21 +00001194 int ret;
1195 size_t i, n, t, k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001196 mbedtls_mpi X, Y, Z, T1, T2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001197
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001198 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1199 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001200
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001201 mbedtls_mpi_init( &X ); mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &Z );
1202 mbedtls_mpi_init( &T1 ); mbedtls_mpi_init( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001203
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001204 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001205 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001206 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1207 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001208 return( 0 );
1209 }
1210
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001211 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1212 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001213 X.s = Y.s = 1;
1214
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001215 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1216 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1217 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1218 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001219
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001220 k = mbedtls_mpi_bitlen( &Y ) % biL;
Paul Bakkerf9688572011-05-05 10:00:45 +00001221 if( k < biL - 1 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001222 {
1223 k = biL - 1 - k;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001224 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1225 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001226 }
1227 else k = 0;
1228
1229 n = X.n - 1;
1230 t = Y.n - 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001231 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001232
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001233 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001234 {
1235 Z.p[n - t]++;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001236 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001237 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001238 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001239
1240 for( i = n; i > t ; i-- )
1241 {
1242 if( X.p[i] >= Y.p[t] )
1243 Z.p[i - t - 1] = ~0;
1244 else
1245 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001246#if defined(MBEDTLS_HAVE_UDBL)
1247 mbedtls_t_udbl r;
Paul Bakker5121ce52009-01-03 21:22:43 +00001248
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001249 r = (mbedtls_t_udbl) X.p[i] << biL;
1250 r |= (mbedtls_t_udbl) X.p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001251 r /= Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001252 if( r > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1253 r = ( (mbedtls_t_udbl) 1 << biL ) - 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001254
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001255 Z.p[i - t - 1] = (mbedtls_mpi_uint) r;
Paul Bakker5121ce52009-01-03 21:22:43 +00001256#else
1257 /*
1258 * __udiv_qrnnd_c, from gmp/longlong.h
1259 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001260 mbedtls_mpi_uint q0, q1, r0, r1;
1261 mbedtls_mpi_uint d0, d1, d, m;
Paul Bakker5121ce52009-01-03 21:22:43 +00001262
1263 d = Y.p[t];
1264 d0 = ( d << biH ) >> biH;
1265 d1 = ( d >> biH );
1266
1267 q1 = X.p[i] / d1;
1268 r1 = X.p[i] - d1 * q1;
1269 r1 <<= biH;
1270 r1 |= ( X.p[i - 1] >> biH );
1271
1272 m = q1 * d0;
1273 if( r1 < m )
1274 {
1275 q1--, r1 += d;
1276 while( r1 >= d && r1 < m )
1277 q1--, r1 += d;
1278 }
1279 r1 -= m;
1280
1281 q0 = r1 / d1;
1282 r0 = r1 - d1 * q0;
1283 r0 <<= biH;
1284 r0 |= ( X.p[i - 1] << biH ) >> biH;
1285
1286 m = q0 * d0;
1287 if( r0 < m )
1288 {
1289 q0--, r0 += d;
1290 while( r0 >= d && r0 < m )
1291 q0--, r0 += d;
1292 }
1293 r0 -= m;
1294
1295 Z.p[i - t - 1] = ( q1 << biH ) | q0;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001296#endif /* MBEDTLS_HAVE_UDBL && !64-bit Apple with Clang 5.0 */
Paul Bakker5121ce52009-01-03 21:22:43 +00001297 }
1298
1299 Z.p[i - t - 1]++;
1300 do
1301 {
1302 Z.p[i - t - 1]--;
1303
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001304 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001305 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001306 T1.p[1] = Y.p[t];
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001307 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001308
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001309 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
Paul Bakker66d5d072014-06-17 16:39:18 +02001310 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1311 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001312 T2.p[2] = X.p[i];
1313 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001314 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001315
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001316 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1317 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1318 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001319
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001320 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001321 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001322 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1323 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1324 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001325 Z.p[i - t - 1]--;
1326 }
1327 }
1328
1329 if( Q != NULL )
1330 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001331 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001332 Q->s = A->s * B->s;
1333 }
1334
1335 if( R != NULL )
1336 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001337 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
Paul Bakkerf02c5642012-11-13 10:25:21 +00001338 X.s = A->s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001339 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001340
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001341 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001342 R->s = 1;
1343 }
1344
1345cleanup:
1346
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001347 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1348 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001349
1350 return( ret );
1351}
1352
1353/*
1354 * Division by int: A = Q * b + R
Paul Bakker5121ce52009-01-03 21:22:43 +00001355 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001356int 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 +00001357{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001358 mbedtls_mpi _B;
1359 mbedtls_mpi_uint p[1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001360
1361 p[0] = ( b < 0 ) ? -b : b;
1362 _B.s = ( b < 0 ) ? -1 : 1;
1363 _B.n = 1;
1364 _B.p = p;
1365
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001366 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001367}
1368
1369/*
1370 * Modulo: R = A mod B
1371 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001372int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001373{
1374 int ret;
1375
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001376 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1377 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001378
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001379 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001380
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001381 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1382 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001383
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001384 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1385 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001386
1387cleanup:
1388
1389 return( ret );
1390}
1391
1392/*
1393 * Modulo: r = A mod b
1394 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001395int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
Paul Bakker5121ce52009-01-03 21:22:43 +00001396{
Paul Bakker23986e52011-04-24 08:57:21 +00001397 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001398 mbedtls_mpi_uint x, y, z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001399
1400 if( b == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001401 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
Paul Bakker5121ce52009-01-03 21:22:43 +00001402
1403 if( b < 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001404 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001405
1406 /*
1407 * handle trivial cases
1408 */
1409 if( b == 1 )
1410 {
1411 *r = 0;
1412 return( 0 );
1413 }
1414
1415 if( b == 2 )
1416 {
1417 *r = A->p[0] & 1;
1418 return( 0 );
1419 }
1420
1421 /*
1422 * general case
1423 */
Paul Bakker23986e52011-04-24 08:57:21 +00001424 for( i = A->n, y = 0; i > 0; i-- )
Paul Bakker5121ce52009-01-03 21:22:43 +00001425 {
Paul Bakker23986e52011-04-24 08:57:21 +00001426 x = A->p[i - 1];
Paul Bakker5121ce52009-01-03 21:22:43 +00001427 y = ( y << biH ) | ( x >> biH );
1428 z = y / b;
1429 y -= z * b;
1430
1431 x <<= biH;
1432 y = ( y << biH ) | ( x >> biH );
1433 z = y / b;
1434 y -= z * b;
1435 }
1436
Paul Bakkerce40a6d2009-06-23 19:46:08 +00001437 /*
1438 * If A is negative, then the current y represents a negative value.
1439 * Flipping it to the positive side.
1440 */
1441 if( A->s < 0 && y != 0 )
1442 y = b - y;
1443
Paul Bakker5121ce52009-01-03 21:22:43 +00001444 *r = y;
1445
1446 return( 0 );
1447}
1448
1449/*
1450 * Fast Montgomery initialization (thanks to Tom St Denis)
1451 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001452static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001453{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001454 mbedtls_mpi_uint x, m0 = N->p[0];
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001455 unsigned int i;
Paul Bakker5121ce52009-01-03 21:22:43 +00001456
1457 x = m0;
1458 x += ( ( m0 + 2 ) & 4 ) << 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00001459
Manuel Pégourié-Gonnardfdf3f0e2014-03-11 13:47:05 +01001460 for( i = biL; i >= 8; i /= 2 )
1461 x *= ( 2 - ( m0 * x ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001462
1463 *mm = ~x + 1;
1464}
1465
1466/*
1467 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1468 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001469static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1470 const mbedtls_mpi *T )
Paul Bakker5121ce52009-01-03 21:22:43 +00001471{
Paul Bakker23986e52011-04-24 08:57:21 +00001472 size_t i, n, m;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001473 mbedtls_mpi_uint u0, u1, *d;
Paul Bakker5121ce52009-01-03 21:22:43 +00001474
1475 memset( T->p, 0, T->n * ciL );
1476
1477 d = T->p;
1478 n = N->n;
1479 m = ( B->n < n ) ? B->n : n;
1480
1481 for( i = 0; i < n; i++ )
1482 {
1483 /*
1484 * T = (T + u0*B + u1*N) / 2^biL
1485 */
1486 u0 = A->p[i];
1487 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1488
1489 mpi_mul_hlp( m, B->p, d, u0 );
1490 mpi_mul_hlp( n, N->p, d, u1 );
1491
1492 *d++ = u0; d[n + 1] = 0;
1493 }
1494
Paul Bakker66d5d072014-06-17 16:39:18 +02001495 memcpy( A->p, d, ( n + 1 ) * ciL );
Paul Bakker5121ce52009-01-03 21:22:43 +00001496
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001497 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001498 mpi_sub_hlp( n, N->p, A->p );
1499 else
1500 /* prevent timing attacks */
1501 mpi_sub_hlp( n, A->p, T->p );
1502}
1503
1504/*
1505 * Montgomery reduction: A = A * R^-1 mod N
1506 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001507static 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 +00001508{
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001509 mbedtls_mpi_uint z = 1;
1510 mbedtls_mpi U;
Paul Bakker5121ce52009-01-03 21:22:43 +00001511
Paul Bakker8ddb6452013-02-27 14:56:33 +01001512 U.n = U.s = (int) z;
Paul Bakker5121ce52009-01-03 21:22:43 +00001513 U.p = &z;
1514
1515 mpi_montmul( A, &U, N, mm, T );
1516}
1517
1518/*
1519 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1520 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001521int 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 +00001522{
Paul Bakker23986e52011-04-24 08:57:21 +00001523 int ret;
1524 size_t wbits, wsize, one = 1;
1525 size_t i, j, nblimbs;
1526 size_t bufsize, nbits;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001527 mbedtls_mpi_uint ei, mm, state;
1528 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
Paul Bakkerf6198c12012-05-16 08:02:29 +00001529 int neg;
Paul Bakker5121ce52009-01-03 21:22:43 +00001530
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001531 if( mbedtls_mpi_cmp_int( N, 0 ) < 0 || ( N->p[0] & 1 ) == 0 )
1532 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001533
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001534 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1535 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001536
1537 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001538 * Init temps and window size
1539 */
1540 mpi_montg_init( &mm, N );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001541 mbedtls_mpi_init( &RR ); mbedtls_mpi_init( &T );
1542 mbedtls_mpi_init( &Apos );
Paul Bakker5121ce52009-01-03 21:22:43 +00001543 memset( W, 0, sizeof( W ) );
1544
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001545 i = mbedtls_mpi_bitlen( E );
Paul Bakker5121ce52009-01-03 21:22:43 +00001546
1547 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1548 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1549
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001550 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1551 wsize = MBEDTLS_MPI_WINDOW_SIZE;
Paul Bakkerb6d5f082011-11-25 11:52:11 +00001552
Paul Bakker5121ce52009-01-03 21:22:43 +00001553 j = N->n + 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001554 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1555 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1556 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001557
1558 /*
Paul Bakker50546922012-05-19 08:40:49 +00001559 * Compensate for negative A (and correct at the end)
1560 */
1561 neg = ( A->s == -1 );
Paul Bakker50546922012-05-19 08:40:49 +00001562 if( neg )
1563 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001564 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
Paul Bakker50546922012-05-19 08:40:49 +00001565 Apos.s = 1;
1566 A = &Apos;
1567 }
1568
1569 /*
Paul Bakker5121ce52009-01-03 21:22:43 +00001570 * If 1st call, pre-compute R^2 mod N
1571 */
1572 if( _RR == NULL || _RR->p == NULL )
1573 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001574 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1575 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1576 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001577
1578 if( _RR != NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001579 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001580 }
1581 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001582 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001583
1584 /*
1585 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1586 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001587 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
1588 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
Paul Bakkerc2024f42014-01-23 20:38:35 +01001589 else
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001590 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001591
1592 mpi_montmul( &W[1], &RR, N, mm, &T );
1593
1594 /*
1595 * X = R^2 * R^-1 mod N = R mod N
1596 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001597 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001598 mpi_montred( X, N, mm, &T );
1599
1600 if( wsize > 1 )
1601 {
1602 /*
1603 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1604 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001605 j = one << ( wsize - 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001606
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001607 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1608 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001609
1610 for( i = 0; i < wsize - 1; i++ )
1611 mpi_montmul( &W[j], &W[j], N, mm, &T );
Paul Bakker0d7702c2013-10-29 16:18:35 +01001612
Paul Bakker5121ce52009-01-03 21:22:43 +00001613 /*
1614 * W[i] = W[i - 1] * W[1]
1615 */
Paul Bakker66d5d072014-06-17 16:39:18 +02001616 for( i = j + 1; i < ( one << wsize ); i++ )
Paul Bakker5121ce52009-01-03 21:22:43 +00001617 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001618 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1619 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001620
1621 mpi_montmul( &W[i], &W[1], N, mm, &T );
1622 }
1623 }
1624
1625 nblimbs = E->n;
1626 bufsize = 0;
1627 nbits = 0;
1628 wbits = 0;
1629 state = 0;
1630
1631 while( 1 )
1632 {
1633 if( bufsize == 0 )
1634 {
Paul Bakker0d7702c2013-10-29 16:18:35 +01001635 if( nblimbs == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001636 break;
1637
Paul Bakker0d7702c2013-10-29 16:18:35 +01001638 nblimbs--;
1639
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001640 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
Paul Bakker5121ce52009-01-03 21:22:43 +00001641 }
1642
1643 bufsize--;
1644
1645 ei = (E->p[nblimbs] >> bufsize) & 1;
1646
1647 /*
1648 * skip leading 0s
1649 */
1650 if( ei == 0 && state == 0 )
1651 continue;
1652
1653 if( ei == 0 && state == 1 )
1654 {
1655 /*
1656 * out of window, square X
1657 */
1658 mpi_montmul( X, X, N, mm, &T );
1659 continue;
1660 }
1661
1662 /*
1663 * add ei to current window
1664 */
1665 state = 2;
1666
1667 nbits++;
Paul Bakker66d5d072014-06-17 16:39:18 +02001668 wbits |= ( ei << ( wsize - nbits ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001669
1670 if( nbits == wsize )
1671 {
1672 /*
1673 * X = X^wsize R^-1 mod N
1674 */
1675 for( i = 0; i < wsize; i++ )
1676 mpi_montmul( X, X, N, mm, &T );
1677
1678 /*
1679 * X = X * W[wbits] R^-1 mod N
1680 */
1681 mpi_montmul( X, &W[wbits], N, mm, &T );
1682
1683 state--;
1684 nbits = 0;
1685 wbits = 0;
1686 }
1687 }
1688
1689 /*
1690 * process the remaining bits
1691 */
1692 for( i = 0; i < nbits; i++ )
1693 {
1694 mpi_montmul( X, X, N, mm, &T );
1695
1696 wbits <<= 1;
1697
Paul Bakker66d5d072014-06-17 16:39:18 +02001698 if( ( wbits & ( one << wsize ) ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001699 mpi_montmul( X, &W[1], N, mm, &T );
1700 }
1701
1702 /*
1703 * X = A^E * R * R^-1 mod N = A^E mod N
1704 */
1705 mpi_montred( X, N, mm, &T );
1706
Paul Bakkerf6198c12012-05-16 08:02:29 +00001707 if( neg )
1708 {
1709 X->s = -1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001710 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
Paul Bakkerf6198c12012-05-16 08:02:29 +00001711 }
1712
Paul Bakker5121ce52009-01-03 21:22:43 +00001713cleanup:
1714
Paul Bakker66d5d072014-06-17 16:39:18 +02001715 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001716 mbedtls_mpi_free( &W[i] );
Paul Bakker5121ce52009-01-03 21:22:43 +00001717
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001718 mbedtls_mpi_free( &W[1] ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Paul Bakker6c591fa2011-05-05 11:49:20 +00001719
Paul Bakker75a28602014-03-31 12:08:17 +02001720 if( _RR == NULL || _RR->p == NULL )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001721 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00001722
1723 return( ret );
1724}
1725
Paul Bakker5121ce52009-01-03 21:22:43 +00001726/*
1727 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1728 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001729int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
Paul Bakker5121ce52009-01-03 21:22:43 +00001730{
Paul Bakker23986e52011-04-24 08:57:21 +00001731 int ret;
1732 size_t lz, lzt;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001733 mbedtls_mpi TG, TA, TB;
Paul Bakker5121ce52009-01-03 21:22:43 +00001734
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001735 mbedtls_mpi_init( &TG ); mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001736
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001737 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
1738 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001739
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001740 lz = mbedtls_mpi_lsb( &TA );
1741 lzt = mbedtls_mpi_lsb( &TB );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001742
Paul Bakker66d5d072014-06-17 16:39:18 +02001743 if( lzt < lz )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001744 lz = lzt;
1745
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001746 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
1747 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00001748
Paul Bakker5121ce52009-01-03 21:22:43 +00001749 TA.s = TB.s = 1;
1750
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001751 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001752 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001753 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
1754 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001755
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001756 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001757 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001758 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
1759 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001760 }
1761 else
1762 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001763 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
1764 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001765 }
1766 }
1767
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001768 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
1769 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001770
1771cleanup:
1772
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001773 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
Paul Bakker5121ce52009-01-03 21:22:43 +00001774
1775 return( ret );
1776}
1777
Paul Bakker33dc46b2014-04-30 16:11:39 +02001778/*
1779 * Fill X with size bytes of random.
1780 *
1781 * Use a temporary bytes representation to make sure the result is the same
Paul Bakkerc37b0ac2014-05-01 14:19:23 +02001782 * regardless of the platform endianness (useful when f_rng is actually
Paul Bakker33dc46b2014-04-30 16:11:39 +02001783 * deterministic, eg for tests).
1784 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001785int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
Paul Bakkera3d195c2011-11-27 21:07:34 +00001786 int (*f_rng)(void *, unsigned char *, size_t),
1787 void *p_rng )
Paul Bakker287781a2011-03-26 13:18:49 +00001788{
Paul Bakker23986e52011-04-24 08:57:21 +00001789 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001790 unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
Paul Bakker33dc46b2014-04-30 16:11:39 +02001791
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001792 if( size > MBEDTLS_MPI_MAX_SIZE )
1793 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker287781a2011-03-26 13:18:49 +00001794
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001795 MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) );
1796 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) );
Paul Bakker287781a2011-03-26 13:18:49 +00001797
1798cleanup:
1799 return( ret );
1800}
1801
Paul Bakker5121ce52009-01-03 21:22:43 +00001802/*
1803 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1804 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001805int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
Paul Bakker5121ce52009-01-03 21:22:43 +00001806{
1807 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001808 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Paul Bakker5121ce52009-01-03 21:22:43 +00001809
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001810 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 )
1811 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00001812
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001813 mbedtls_mpi_init( &TA ); mbedtls_mpi_init( &TU ); mbedtls_mpi_init( &U1 ); mbedtls_mpi_init( &U2 );
1814 mbedtls_mpi_init( &G ); mbedtls_mpi_init( &TB ); mbedtls_mpi_init( &TV );
1815 mbedtls_mpi_init( &V1 ); mbedtls_mpi_init( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001816
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001817 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001818
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001819 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001820 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001821 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00001822 goto cleanup;
1823 }
1824
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001825 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
1826 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
1827 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
1828 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001829
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001830 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
1831 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
1832 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
1833 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001834
1835 do
1836 {
1837 while( ( TU.p[0] & 1 ) == 0 )
1838 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001839 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001840
1841 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
1842 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001843 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
1844 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001845 }
1846
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001847 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
1848 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001849 }
1850
1851 while( ( TV.p[0] & 1 ) == 0 )
1852 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001853 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001854
1855 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
1856 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001857 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
1858 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001859 }
1860
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001861 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
1862 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001863 }
1864
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001865 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00001866 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001867 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
1868 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
1869 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001870 }
1871 else
1872 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001873 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
1874 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
1875 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001876 }
1877 }
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001878 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001879
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001880 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
1881 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001882
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001883 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
1884 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001885
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001886 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001887
1888cleanup:
1889
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001890 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
1891 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
1892 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001893
1894 return( ret );
1895}
1896
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001897#if defined(MBEDTLS_GENPRIME)
Paul Bakkerd9374b02012-11-02 11:02:58 +00001898
Paul Bakker5121ce52009-01-03 21:22:43 +00001899static const int small_prime[] =
1900{
1901 3, 5, 7, 11, 13, 17, 19, 23,
1902 29, 31, 37, 41, 43, 47, 53, 59,
1903 61, 67, 71, 73, 79, 83, 89, 97,
1904 101, 103, 107, 109, 113, 127, 131, 137,
1905 139, 149, 151, 157, 163, 167, 173, 179,
1906 181, 191, 193, 197, 199, 211, 223, 227,
1907 229, 233, 239, 241, 251, 257, 263, 269,
1908 271, 277, 281, 283, 293, 307, 311, 313,
1909 317, 331, 337, 347, 349, 353, 359, 367,
1910 373, 379, 383, 389, 397, 401, 409, 419,
1911 421, 431, 433, 439, 443, 449, 457, 461,
1912 463, 467, 479, 487, 491, 499, 503, 509,
1913 521, 523, 541, 547, 557, 563, 569, 571,
1914 577, 587, 593, 599, 601, 607, 613, 617,
1915 619, 631, 641, 643, 647, 653, 659, 661,
1916 673, 677, 683, 691, 701, 709, 719, 727,
1917 733, 739, 743, 751, 757, 761, 769, 773,
1918 787, 797, 809, 811, 821, 823, 827, 829,
1919 839, 853, 857, 859, 863, 877, 881, 883,
1920 887, 907, 911, 919, 929, 937, 941, 947,
1921 953, 967, 971, 977, 983, 991, 997, -103
1922};
1923
1924/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001925 * Small divisors test (X must be positive)
1926 *
1927 * Return values:
1928 * 0: no small factor (possible prime, more tests needed)
1929 * 1: certain prime
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001930 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001931 * other negative: error
Paul Bakker5121ce52009-01-03 21:22:43 +00001932 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001933static int mpi_check_small_factors( const mbedtls_mpi *X )
Paul Bakker5121ce52009-01-03 21:22:43 +00001934{
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001935 int ret = 0;
1936 size_t i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001937 mbedtls_mpi_uint r;
Paul Bakker5121ce52009-01-03 21:22:43 +00001938
Paul Bakker5121ce52009-01-03 21:22:43 +00001939 if( ( X->p[0] & 1 ) == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001940 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001941
1942 for( i = 0; small_prime[i] > 0; i++ )
1943 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001944 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001945 return( 1 );
Paul Bakker5121ce52009-01-03 21:22:43 +00001946
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001947 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001948
1949 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001950 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Paul Bakker5121ce52009-01-03 21:22:43 +00001951 }
1952
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001953cleanup:
1954 return( ret );
1955}
1956
1957/*
1958 * Miller-Rabin pseudo-primality test (HAC 4.24)
1959 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001960static int mpi_miller_rabin( const mbedtls_mpi *X,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001961 int (*f_rng)(void *, unsigned char *, size_t),
1962 void *p_rng )
1963{
Pascal Junodb99183d2015-03-11 16:49:45 +01001964 int ret, count;
1965 size_t i, j, k, n, s;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001966 mbedtls_mpi W, R, T, A, RR;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001967
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001968 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R ); mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
1969 mbedtls_mpi_init( &RR );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01001970
Paul Bakker5121ce52009-01-03 21:22:43 +00001971 /*
1972 * W = |X| - 1
1973 * R = W >> lsb( W )
1974 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001975 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
1976 s = mbedtls_mpi_lsb( &W );
1977 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
1978 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001979
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001980 i = mbedtls_mpi_bitlen( X );
Paul Bakker5121ce52009-01-03 21:22:43 +00001981 /*
1982 * HAC, table 4.4
1983 */
1984 n = ( ( i >= 1300 ) ? 2 : ( i >= 850 ) ? 3 :
1985 ( i >= 650 ) ? 4 : ( i >= 350 ) ? 8 :
1986 ( i >= 250 ) ? 12 : ( i >= 150 ) ? 18 : 27 );
1987
1988 for( i = 0; i < n; i++ )
1989 {
1990 /*
1991 * pick a random A, 1 < A < |X| - 1
1992 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001993 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00001994
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001995 if( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 )
Paul Bakkerb94081b2011-01-05 15:53:06 +00001996 {
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02001997 j = mbedtls_mpi_bitlen( &A ) - mbedtls_mpi_bitlen( &W );
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02001998 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j + 1 ) );
Paul Bakkerb94081b2011-01-05 15:53:06 +00001999 }
Paul Bakker5121ce52009-01-03 21:22:43 +00002000 A.p[0] |= 3;
2001
Pascal Junodb99183d2015-03-11 16:49:45 +01002002 count = 0;
2003 do {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002004 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002005
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002006 j = mbedtls_mpi_bitlen( &A );
2007 k = mbedtls_mpi_bitlen( &W );
Pascal Junodb99183d2015-03-11 16:49:45 +01002008 if (j > k) {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002009 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A, j - k ) );
Pascal Junodb99183d2015-03-11 16:49:45 +01002010 }
2011
2012 if (count++ > 30) {
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002013 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Pascal Junodb99183d2015-03-11 16:49:45 +01002014 }
2015
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002016 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2017 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
Paul Bakker5121ce52009-01-03 21:22:43 +00002018
2019 /*
2020 * A = A^R mod |X|
2021 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002022 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002023
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002024 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2025 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002026 continue;
2027
2028 j = 1;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002029 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002030 {
2031 /*
2032 * A = A * A mod |X|
2033 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002034 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2035 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002036
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002037 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002038 break;
2039
2040 j++;
2041 }
2042
2043 /*
2044 * not prime if A != |X| - 1 or A == 1
2045 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002046 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2047 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002048 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002049 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Paul Bakker5121ce52009-01-03 21:22:43 +00002050 break;
2051 }
2052 }
2053
2054cleanup:
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002055 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R ); mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2056 mbedtls_mpi_free( &RR );
Paul Bakker5121ce52009-01-03 21:22:43 +00002057
2058 return( ret );
2059}
2060
2061/*
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002062 * Pseudo-primality test: small factors, then Miller-Rabin
2063 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002064int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002065 int (*f_rng)(void *, unsigned char *, size_t),
2066 void *p_rng )
2067{
2068 int ret;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002069 mbedtls_mpi XX;
Manuel Pégourié-Gonnard7f4ed672014-10-14 20:56:02 +02002070
2071 XX.s = 1;
2072 XX.n = X->n;
2073 XX.p = X->p;
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002074
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002075 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2076 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2077 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002078
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002079 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
Manuel Pégourié-Gonnard378fb4b2013-11-22 18:39:18 +01002080 return( 0 );
2081
2082 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2083 {
2084 if( ret == 1 )
2085 return( 0 );
2086
2087 return( ret );
2088 }
2089
2090 return( mpi_miller_rabin( &XX, f_rng, p_rng ) );
2091}
2092
2093/*
Paul Bakker5121ce52009-01-03 21:22:43 +00002094 * Prime number generation
2095 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002096int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int dh_flag,
Paul Bakkera3d195c2011-11-27 21:07:34 +00002097 int (*f_rng)(void *, unsigned char *, size_t),
2098 void *p_rng )
Paul Bakker5121ce52009-01-03 21:22:43 +00002099{
Paul Bakker23986e52011-04-24 08:57:21 +00002100 int ret;
2101 size_t k, n;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002102 mbedtls_mpi_uint r;
2103 mbedtls_mpi Y;
Paul Bakker5121ce52009-01-03 21:22:43 +00002104
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002105 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2106 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Paul Bakker5121ce52009-01-03 21:22:43 +00002107
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002108 mbedtls_mpi_init( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002109
2110 n = BITS_TO_LIMBS( nbits );
2111
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002112 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002113
Manuel Pégourié-Gonnardc0696c22015-06-18 16:47:17 +02002114 k = mbedtls_mpi_bitlen( X );
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002115 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits + 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002116
Manuel Pégourié-Gonnard53c76c02015-04-17 20:15:36 +02002117 mbedtls_mpi_set_bit( X, nbits-1, 1 );
Pascal Junodb99183d2015-03-11 16:49:45 +01002118
2119 X->p[0] |= 1;
Paul Bakker5121ce52009-01-03 21:22:43 +00002120
2121 if( dh_flag == 0 )
2122 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002123 while( ( ret = mbedtls_mpi_is_prime( X, f_rng, p_rng ) ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002124 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002125 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002126 goto cleanup;
2127
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002128 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 2 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002129 }
2130 }
2131 else
2132 {
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002133 /*
2134 * An necessary condition for Y and X = 2Y + 1 to be prime
2135 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2136 * Make sure it is satisfied, while keeping X = 3 mod 4
2137 */
Pascal Junodb99183d2015-03-11 16:49:45 +01002138
2139 X->p[0] |= 2;
2140
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002141 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002142 if( r == 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002143 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002144 else if( r == 1 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002145 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002146
2147 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002148 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2149 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002150
2151 while( 1 )
2152 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002153 /*
2154 * First, check small factors for X and Y
2155 * before doing Miller-Rabin on any of them
2156 */
2157 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2158 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2159 ( ret = mpi_miller_rabin( X, f_rng, p_rng ) ) == 0 &&
2160 ( ret = mpi_miller_rabin( &Y, f_rng, p_rng ) ) == 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002161 {
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002162 break;
Paul Bakker5121ce52009-01-03 21:22:43 +00002163 }
2164
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002165 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
Paul Bakker5121ce52009-01-03 21:22:43 +00002166 goto cleanup;
2167
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002168 /*
Manuel Pégourié-Gonnardddf76152013-11-22 19:58:22 +01002169 * Next candidates. We want to preserve Y = (X-1) / 2 and
Manuel Pégourié-Gonnard0160eac2013-11-22 17:54:59 +01002170 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2171 * so up Y by 6 and X by 12.
2172 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002173 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2174 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002175 }
2176 }
2177
2178cleanup:
2179
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002180 mbedtls_mpi_free( &Y );
Paul Bakker5121ce52009-01-03 21:22:43 +00002181
2182 return( ret );
2183}
2184
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002185#endif /* MBEDTLS_GENPRIME */
Paul Bakker5121ce52009-01-03 21:22:43 +00002186
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002187#if defined(MBEDTLS_SELF_TEST)
Paul Bakker5121ce52009-01-03 21:22:43 +00002188
Paul Bakker23986e52011-04-24 08:57:21 +00002189#define GCD_PAIR_COUNT 3
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002190
2191static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2192{
2193 { 693, 609, 21 },
2194 { 1764, 868, 28 },
2195 { 768454923, 542167814, 1 }
2196};
2197
Paul Bakker5121ce52009-01-03 21:22:43 +00002198/*
2199 * Checkup routine
2200 */
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002201int mbedtls_mpi_self_test( int verbose )
Paul Bakker5121ce52009-01-03 21:22:43 +00002202{
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002203 int ret, i;
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002204 mbedtls_mpi A, E, N, X, Y, U, V;
Paul Bakker5121ce52009-01-03 21:22:43 +00002205
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002206 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2207 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002208
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002209 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002210 "EFE021C2645FD1DC586E69184AF4A31E" \
2211 "D5F53E93B5F123FA41680867BA110131" \
2212 "944FE7952E2517337780CB0DB80E61AA" \
2213 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2214
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002215 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002216 "B2E7EFD37075B9F03FF989C7C5051C20" \
2217 "34D2A323810251127E7BF8625A4F49A5" \
2218 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2219 "5B5C25763222FEFCCFC38B832366C29E" ) );
2220
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002221 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002222 "0066A198186C18C10B2F5ED9B522752A" \
2223 "9830B69916E535C8F047518A889A43A5" \
2224 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2225
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002226 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002227
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002228 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002229 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2230 "9E857EA95A03512E2BAE7391688D264A" \
2231 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2232 "8001B72E848A38CAE1C65F78E56ABDEF" \
2233 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2234 "ECF677152EF804370C1A305CAF3B5BF1" \
2235 "30879B56C61DE584A0F53A2447A51E" ) );
2236
2237 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002238 mbedtls_printf( " MPI test #1 (mul_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002239
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002240 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002241 {
2242 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002243 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002244
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002245 ret = 1;
2246 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002247 }
2248
2249 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002250 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002251
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002252 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002253
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002254 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002255 "256567336059E52CAE22925474705F39A94" ) );
2256
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002257 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002258 "6613F26162223DF488E9CD48CC132C7A" \
2259 "0AC93C701B001B092E4E5B9F73BCD27B" \
2260 "9EE50D0657C77F374E903CDFA4C642" ) );
2261
2262 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002263 mbedtls_printf( " MPI test #2 (div_mpi): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002264
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002265 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2266 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002267 {
2268 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002269 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002270
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002271 ret = 1;
2272 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002273 }
2274
2275 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002276 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002277
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002278 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002279
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002280 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002281 "36E139AEA55215609D2816998ED020BB" \
2282 "BD96C37890F65171D948E9BC7CBAA4D9" \
2283 "325D24D6A3C12710F10A09FA08AB87" ) );
2284
2285 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002286 mbedtls_printf( " MPI test #3 (exp_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002287
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002288 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002289 {
2290 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002291 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002292
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002293 ret = 1;
2294 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002295 }
2296
2297 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002298 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002299
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002300 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
Paul Bakker5121ce52009-01-03 21:22:43 +00002301
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002302 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
Paul Bakker5121ce52009-01-03 21:22:43 +00002303 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2304 "C3DBA76456363A10869622EAC2DD84EC" \
2305 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2306
2307 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002308 mbedtls_printf( " MPI test #4 (inv_mod): " );
Paul Bakker5121ce52009-01-03 21:22:43 +00002309
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002310 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
Paul Bakker5121ce52009-01-03 21:22:43 +00002311 {
2312 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002313 mbedtls_printf( "failed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002314
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002315 ret = 1;
2316 goto cleanup;
Paul Bakker5121ce52009-01-03 21:22:43 +00002317 }
2318
2319 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002320 mbedtls_printf( "passed\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002321
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002322 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002323 mbedtls_printf( " MPI test #5 (simple gcd): " );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002324
Paul Bakker66d5d072014-06-17 16:39:18 +02002325 for( i = 0; i < GCD_PAIR_COUNT; i++ )
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002326 {
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002327 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2328 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002329
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002330 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002331
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002332 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002333 {
2334 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002335 mbedtls_printf( "failed at %d\n", i );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002336
Manuel Pégourié-Gonnard9e987ed2014-01-20 10:03:15 +01002337 ret = 1;
2338 goto cleanup;
2339 }
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002340 }
2341
2342 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002343 mbedtls_printf( "passed\n" );
Paul Bakker4e0d7ca2009-01-29 22:24:33 +00002344
Paul Bakker5121ce52009-01-03 21:22:43 +00002345cleanup:
2346
2347 if( ret != 0 && verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002348 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
Paul Bakker5121ce52009-01-03 21:22:43 +00002349
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002350 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2351 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
Paul Bakker5121ce52009-01-03 21:22:43 +00002352
2353 if( verbose != 0 )
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002354 mbedtls_printf( "\n" );
Paul Bakker5121ce52009-01-03 21:22:43 +00002355
2356 return( ret );
2357}
2358
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002359#endif /* MBEDTLS_SELF_TEST */
Paul Bakker5121ce52009-01-03 21:22:43 +00002360
Manuel Pégourié-Gonnard2cf5a7c2015-04-08 12:49:31 +02002361#endif /* MBEDTLS_BIGNUM_C */