blob: 5d4beca4e2a5572e134e6309d09d39bb4ecca9e7 [file] [log] [blame]
Edison Ai7b079202018-02-28 15:01:47 +08001// SPDX-License-Identifier: Apache-2.0
Jens Wiklander817466c2018-05-22 13:49:31 +02002/*
3 * Multi-precision integer library
4 *
5 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
Jens Wiklander817466c2018-05-22 13:49:31 +02006 *
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.
18 *
19 * This file is part of mbed TLS (https://tls.mbed.org)
20 */
21
22/*
23 * The following sources were referenced in the design of this Multi-precision
24 * Integer library:
25 *
26 * [1] Handbook of Applied Cryptography - 1997
27 * Menezes, van Oorschot and Vanstone
28 *
29 * [2] Multi-Precision Math
30 * Tom St Denis
31 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
32 *
33 * [3] GNU Multi-Precision Arithmetic Library
34 * https://gmplib.org/manual/index.html
35 *
36 */
37
38#if !defined(MBEDTLS_CONFIG_FILE)
39#include "mbedtls/config.h"
40#else
41#include MBEDTLS_CONFIG_FILE
42#endif
43
44#if defined(MBEDTLS_BIGNUM_C)
45
46#include "mbedtls/bignum.h"
47#include "mbedtls/bn_mul.h"
Jens Wiklander50a57cf2019-03-13 10:41:54 +010048#include "mbedtls/platform_util.h"
Jens Wiklander817466c2018-05-22 13:49:31 +020049
50#include <string.h>
51
52#if defined(MBEDTLS_PLATFORM_C)
53#include "mbedtls/platform.h"
54#else
55#include <stdio.h>
56#include <stdlib.h>
57#define mbedtls_printf printf
58#define mbedtls_calloc calloc
59#define mbedtls_free free
60#endif
61
Jens Wiklanderd831db42018-11-08 11:18:22 +010062#include <mempool.h>
Jens Wiklanderae499f62019-04-17 12:25:20 +020063#include <util.h>
Jens Wiklanderd831db42018-11-08 11:18:22 +010064
Jens Wiklander50a57cf2019-03-13 10:41:54 +010065#define MPI_VALIDATE_RET( cond ) \
66 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
67#define MPI_VALIDATE( cond ) \
68 MBEDTLS_INTERNAL_VALIDATE( cond )
Jens Wiklander817466c2018-05-22 13:49:31 +020069
70#define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
71#define biL (ciL << 3) /* bits in limb */
72#define biH (ciL << 2) /* half limb size */
73
74#define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
75
76/*
77 * Convert between bits/chars and number of limbs
78 * Divide first in order to avoid potential overflows
79 */
80#define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
81#define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
82
Jens Wiklanderd831db42018-11-08 11:18:22 +010083void *mbedtls_mpi_mempool;
84
Jens Wiklander50a57cf2019-03-13 10:41:54 +010085/* Implementation that should never be optimized out by the compiler */
86static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
87{
88 mbedtls_platform_zeroize( v, ciL * n );
89}
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010090
Jens Wiklander817466c2018-05-22 13:49:31 +020091/*
92 * Initialize one MPI
93 */
Jens Wiklanderd831db42018-11-08 11:18:22 +010094static void mpi_init( mbedtls_mpi *X, short use_mempool )
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010095{
Jens Wiklander50a57cf2019-03-13 10:41:54 +010096 MPI_VALIDATE( X != NULL );
Jens Wiklander98bd5fe2018-11-08 11:18:22 +010097
Jens Wiklander50a57cf2019-03-13 10:41:54 +010098 X->s = 1;
Jens Wiklanderd831db42018-11-08 11:18:22 +010099 X->use_mempool = use_mempool;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100100 X->n = 0;
101 X->p = NULL;
Jens Wiklander98bd5fe2018-11-08 11:18:22 +0100102}
103
Jens Wiklanderd831db42018-11-08 11:18:22 +0100104void mbedtls_mpi_init( mbedtls_mpi *X )
105{
106 mpi_init( X, 0 /*use_mempool*/ );
107}
108
109void mbedtls_mpi_init_mempool( mbedtls_mpi *X )
110{
111 mpi_init( X, !!mbedtls_mpi_mempool /*use_mempool*/ );
112}
113
Jens Wiklander817466c2018-05-22 13:49:31 +0200114/*
115 * Unallocate one MPI
116 */
117void mbedtls_mpi_free( mbedtls_mpi *X )
118{
119 if( X == NULL )
120 return;
121
122 if( X->p != NULL )
123 {
124 mbedtls_mpi_zeroize( X->p, X->n );
Jens Wiklanderd831db42018-11-08 11:18:22 +0100125 if( X->use_mempool )
126 mempool_free( mbedtls_mpi_mempool, X->p );
127 else
128 mbedtls_free( X->p );
Jens Wiklander817466c2018-05-22 13:49:31 +0200129 }
130
131 X->s = 1;
132 X->n = 0;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100133 X->p = NULL;
Jens Wiklander817466c2018-05-22 13:49:31 +0200134}
135
136/*
137 * Enlarge to the specified number of limbs
138 */
139int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
140{
141 mbedtls_mpi_uint *p;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100142 MPI_VALIDATE_RET( X != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200143
144 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
145 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
146
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100147 if( X->n < nblimbs )
148 {
Jens Wiklanderd831db42018-11-08 11:18:22 +0100149 if( X->use_mempool )
150 {
151 p = mempool_alloc( mbedtls_mpi_mempool, nblimbs * ciL );
152 if( p == NULL )
153 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
154 memset( p, 0, nblimbs * ciL );
155 }
156 else
157 {
158 p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL );
159 if( p == NULL )
160 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
161 }
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100162
163 if( X->p != NULL )
164 {
165 memcpy( p, X->p, X->n * ciL );
166 mbedtls_mpi_zeroize( X->p, X->n );
Jens Wiklanderd831db42018-11-08 11:18:22 +0100167 if( X->use_mempool )
168 mempool_free( mbedtls_mpi_mempool, X->p);
169 else
170 mbedtls_free( X->p );
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100171 }
172
173 X->n = nblimbs;
174 X->p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +0200175 }
176
177 return( 0 );
178}
179
180/*
181 * Resize down as much as possible,
182 * while keeping at least the specified number of limbs
183 */
184int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
185{
186 mbedtls_mpi_uint *p;
187 size_t i;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100188 MPI_VALIDATE_RET( X != NULL );
189
190 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
191 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
Jens Wiklander817466c2018-05-22 13:49:31 +0200192
193 /* Actually resize up in this case */
194 if( X->n <= nblimbs )
195 return( mbedtls_mpi_grow( X, nblimbs ) );
196
197 for( i = X->n - 1; i > 0; i-- )
198 if( X->p[i] != 0 )
199 break;
200 i++;
201
202 if( i < nblimbs )
203 i = nblimbs;
204
Jens Wiklanderd831db42018-11-08 11:18:22 +0100205 if( X->use_mempool )
206 {
207 p = mempool_alloc( mbedtls_mpi_mempool, nblimbs * ciL );
208 if( p == NULL )
209 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
210 memset( p, 0, nblimbs * ciL );
211 }
212 else
213 {
214 p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL );
215 if( p == NULL )
216 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
217 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200218
219 if( X->p != NULL )
220 {
221 memcpy( p, X->p, i * ciL );
222 mbedtls_mpi_zeroize( X->p, X->n );
Jens Wiklanderd831db42018-11-08 11:18:22 +0100223 if( X->use_mempool )
224 mempool_free( mbedtls_mpi_mempool, X->p );
225 else
226 mbedtls_free( X->p );
Jens Wiklander817466c2018-05-22 13:49:31 +0200227 }
228
Jens Wiklander18c51482018-11-12 13:53:08 +0100229 X->n = i;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100230 X->p = p;
Jens Wiklander817466c2018-05-22 13:49:31 +0200231
232 return( 0 );
233}
234
235/*
236 * Copy the contents of Y into X
237 */
238int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
239{
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100240 int ret = 0;
Jens Wiklander817466c2018-05-22 13:49:31 +0200241 size_t i;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100242 MPI_VALIDATE_RET( X != NULL );
243 MPI_VALIDATE_RET( Y != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200244
245 if( X == Y )
246 return( 0 );
247
248 if( Y->p == NULL )
249 {
250 mbedtls_mpi_free( X );
251 return( 0 );
252 }
253
254 for( i = Y->n - 1; i > 0; i-- )
255 if( Y->p[i] != 0 )
256 break;
257 i++;
258
259 X->s = Y->s;
260
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100261 if( X->n < i )
262 {
263 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
264 }
265 else
266 {
267 memset( X->p + i, 0, ( X->n - i ) * ciL );
268 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200269
Jens Wiklander817466c2018-05-22 13:49:31 +0200270 memcpy( X->p, Y->p, i * ciL );
271
272cleanup:
273
274 return( ret );
275}
276
277/*
278 * Swap the contents of X and Y
279 */
280void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
281{
282 mbedtls_mpi T;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100283 MPI_VALIDATE( X != NULL );
284 MPI_VALIDATE( Y != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200285
286 memcpy( &T, X, sizeof( mbedtls_mpi ) );
287 memcpy( X, Y, sizeof( mbedtls_mpi ) );
288 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
289}
290
291/*
292 * Conditionally assign X = Y, without leaking information
293 * about whether the assignment was made or not.
294 * (Leaking information about the respective sizes of X and Y is ok however.)
295 */
296int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign )
297{
298 int ret = 0;
299 size_t i;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100300 MPI_VALIDATE_RET( X != NULL );
301 MPI_VALIDATE_RET( Y != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200302
303 /* make sure assign is 0 or 1 in a time-constant manner */
304 assign = (assign | (unsigned char)-assign) >> 7;
305
306 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
307
308 X->s = X->s * ( 1 - assign ) + Y->s * assign;
309
310 for( i = 0; i < Y->n; i++ )
311 X->p[i] = X->p[i] * ( 1 - assign ) + Y->p[i] * assign;
312
313 for( ; i < X->n; i++ )
314 X->p[i] *= ( 1 - assign );
315
316cleanup:
317 return( ret );
318}
319
320/*
321 * Conditionally swap X and Y, without leaking information
322 * about whether the swap was made or not.
323 * Here it is not ok to simply swap the pointers, which whould lead to
324 * different memory access patterns when X and Y are used afterwards.
325 */
326int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char swap )
327{
328 int ret, s;
329 size_t i;
330 mbedtls_mpi_uint tmp;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100331 MPI_VALIDATE_RET( X != NULL );
332 MPI_VALIDATE_RET( Y != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200333
334 if( X == Y )
335 return( 0 );
336
337 /* make sure swap is 0 or 1 in a time-constant manner */
338 swap = (swap | (unsigned char)-swap) >> 7;
339
340 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, Y->n ) );
341 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y, X->n ) );
342
343 s = X->s;
344 X->s = X->s * ( 1 - swap ) + Y->s * swap;
345 Y->s = Y->s * ( 1 - swap ) + s * swap;
346
347
348 for( i = 0; i < X->n; i++ )
349 {
350 tmp = X->p[i];
351 X->p[i] = X->p[i] * ( 1 - swap ) + Y->p[i] * swap;
352 Y->p[i] = Y->p[i] * ( 1 - swap ) + tmp * swap;
353 }
354
355cleanup:
356 return( ret );
357}
358
359/*
360 * Set value from integer
361 */
362int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
363{
364 int ret;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100365 MPI_VALIDATE_RET( X != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200366
367 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
368 memset( X->p, 0, X->n * ciL );
369
370 X->p[0] = ( z < 0 ) ? -z : z;
371 X->s = ( z < 0 ) ? -1 : 1;
372
373cleanup:
374
375 return( ret );
376}
377
378/*
379 * Get a specific bit
380 */
381int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
382{
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100383 MPI_VALIDATE_RET( X != NULL );
384
Jens Wiklander817466c2018-05-22 13:49:31 +0200385 if( X->n * biL <= pos )
386 return( 0 );
387
388 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
389}
390
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100391/* Get a specific byte, without range checks. */
392#define GET_BYTE( X, i ) \
393 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
394
Jens Wiklander817466c2018-05-22 13:49:31 +0200395/*
396 * Set a bit to a specific value of 0 or 1
397 */
398int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
399{
400 int ret = 0;
401 size_t off = pos / biL;
402 size_t idx = pos % biL;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100403 MPI_VALIDATE_RET( X != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200404
405 if( val != 0 && val != 1 )
406 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
407
408 if( X->n * biL <= pos )
409 {
410 if( val == 0 )
411 return( 0 );
412
413 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
414 }
415
416 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
417 X->p[off] |= (mbedtls_mpi_uint) val << idx;
418
419cleanup:
420
421 return( ret );
422}
423
424/*
425 * Return the number of less significant zero-bits
426 */
427size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
428{
429 size_t i, j, count = 0;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100430 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
Jens Wiklander817466c2018-05-22 13:49:31 +0200431
432 for( i = 0; i < X->n; i++ )
433 for( j = 0; j < biL; j++, count++ )
434 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
435 return( count );
436
437 return( 0 );
438}
439
440/*
441 * Count leading zero bits in a given integer
442 */
443static size_t mbedtls_clz( const mbedtls_mpi_uint x )
444{
445 size_t j;
446 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
447
448 for( j = 0; j < biL; j++ )
449 {
450 if( x & mask ) break;
451
452 mask >>= 1;
453 }
454
455 return j;
456}
457
458/*
459 * Return the number of bits
460 */
461size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
462{
463 size_t i, j;
464
465 if( X->n == 0 )
466 return( 0 );
467
468 for( i = X->n - 1; i > 0; i-- )
469 if( X->p[i] != 0 )
470 break;
471
472 j = biL - mbedtls_clz( X->p[i] );
473
474 return( ( i * biL ) + j );
475}
476
477/*
478 * Return the total size in bytes
479 */
480size_t mbedtls_mpi_size( const mbedtls_mpi *X )
481{
482 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
483}
484
485/*
486 * Convert an ASCII character to digit value
487 */
488static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
489{
490 *d = 255;
491
492 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
493 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
494 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
495
496 if( *d >= (mbedtls_mpi_uint) radix )
497 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
498
499 return( 0 );
500}
501
502/*
503 * Import from an ASCII string
504 */
505int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
506{
507 int ret;
508 size_t i, j, slen, n;
509 mbedtls_mpi_uint d;
510 mbedtls_mpi T;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100511 MPI_VALIDATE_RET( X != NULL );
512 MPI_VALIDATE_RET( s != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200513
514 if( radix < 2 || radix > 16 )
515 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
516
Jens Wiklanderd831db42018-11-08 11:18:22 +0100517 mbedtls_mpi_init_mempool( &T );
Jens Wiklander817466c2018-05-22 13:49:31 +0200518
519 slen = strlen( s );
520
521 if( radix == 16 )
522 {
523 if( slen > MPI_SIZE_T_MAX >> 2 )
524 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
525
526 n = BITS_TO_LIMBS( slen << 2 );
527
528 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
529 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
530
531 for( i = slen, j = 0; i > 0; i--, j++ )
532 {
533 if( i == 1 && s[i - 1] == '-' )
534 {
535 X->s = -1;
536 break;
537 }
538
539 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
540 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
541 }
542 }
543 else
544 {
545 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
546
547 for( i = 0; i < slen; i++ )
548 {
549 if( i == 0 && s[i] == '-' )
550 {
551 X->s = -1;
552 continue;
553 }
554
555 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
556 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
557
558 if( X->s == 1 )
559 {
560 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
561 }
562 else
563 {
564 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X, &T, d ) );
565 }
566 }
567 }
568
569cleanup:
570
571 mbedtls_mpi_free( &T );
572
573 return( ret );
574}
575
576/*
577 * Helper to write the digits high-order first
578 */
579static int mpi_write_hlp( mbedtls_mpi *X, int radix, char **p )
580{
581 int ret;
582 mbedtls_mpi_uint r;
583
584 if( radix < 2 || radix > 16 )
585 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
586
587 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
588 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
589
590 if( mbedtls_mpi_cmp_int( X, 0 ) != 0 )
591 MBEDTLS_MPI_CHK( mpi_write_hlp( X, radix, p ) );
592
593 if( r < 10 )
594 *(*p)++ = (char)( r + 0x30 );
595 else
596 *(*p)++ = (char)( r + 0x37 );
597
598cleanup:
599
600 return( ret );
601}
602
603/*
604 * Export into an ASCII string
605 */
606int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
607 char *buf, size_t buflen, size_t *olen )
608{
609 int ret = 0;
610 size_t n;
611 char *p;
612 mbedtls_mpi T;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100613 MPI_VALIDATE_RET( X != NULL );
614 MPI_VALIDATE_RET( olen != NULL );
615 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200616
617 if( radix < 2 || radix > 16 )
618 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
619
620 n = mbedtls_mpi_bitlen( X );
621 if( radix >= 4 ) n >>= 1;
622 if( radix >= 16 ) n >>= 1;
623 /*
624 * Round up the buffer length to an even value to ensure that there is
625 * enough room for hexadecimal values that can be represented in an odd
626 * number of digits.
627 */
628 n += 3 + ( ( n + 1 ) & 1 );
629
630 if( buflen < n )
631 {
632 *olen = n;
633 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
634 }
635
636 p = buf;
Jens Wiklanderd831db42018-11-08 11:18:22 +0100637 mbedtls_mpi_init_mempool( &T );
Jens Wiklander817466c2018-05-22 13:49:31 +0200638
639 if( X->s == -1 )
640 *p++ = '-';
641
642 if( radix == 16 )
643 {
644 int c;
645 size_t i, j, k;
646
647 for( i = X->n, k = 0; i > 0; i-- )
648 {
649 for( j = ciL; j > 0; j-- )
650 {
651 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
652
653 if( c == 0 && k == 0 && ( i + j ) != 2 )
654 continue;
655
656 *(p++) = "0123456789ABCDEF" [c / 16];
657 *(p++) = "0123456789ABCDEF" [c % 16];
658 k = 1;
659 }
660 }
661 }
662 else
663 {
664 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
665
666 if( T.s == -1 )
667 T.s = 1;
668
669 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p ) );
670 }
671
672 *p++ = '\0';
673 *olen = p - buf;
674
675cleanup:
676
677 mbedtls_mpi_free( &T );
678
679 return( ret );
680}
681
682#if defined(MBEDTLS_FS_IO)
683/*
684 * Read X from an opened file
685 */
686int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
687{
688 mbedtls_mpi_uint d;
689 size_t slen;
690 char *p;
691 /*
692 * Buffer should have space for (short) label and decimal formatted MPI,
693 * newline characters and '\0'
694 */
695 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
696
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100697 MPI_VALIDATE_RET( X != NULL );
698 MPI_VALIDATE_RET( fin != NULL );
699
700 if( radix < 2 || radix > 16 )
701 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
702
Jens Wiklander817466c2018-05-22 13:49:31 +0200703 memset( s, 0, sizeof( s ) );
704 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
705 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
706
707 slen = strlen( s );
708 if( slen == sizeof( s ) - 2 )
709 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
710
711 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
712 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
713
714 p = s + slen;
715 while( p-- > s )
716 if( mpi_get_digit( &d, radix, *p ) != 0 )
717 break;
718
719 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
720}
721
722/*
723 * Write X into an opened file (or stdout if fout == NULL)
724 */
725int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
726{
727 int ret;
728 size_t n, slen, plen;
729 /*
730 * Buffer should have space for (short) label and decimal formatted MPI,
731 * newline characters and '\0'
732 */
733 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100734 MPI_VALIDATE_RET( X != NULL );
735
736 if( radix < 2 || radix > 16 )
737 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
Jens Wiklander817466c2018-05-22 13:49:31 +0200738
739 memset( s, 0, sizeof( s ) );
740
741 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
742
743 if( p == NULL ) p = "";
744
745 plen = strlen( p );
746 slen = strlen( s );
747 s[slen++] = '\r';
748 s[slen++] = '\n';
749
750 if( fout != NULL )
751 {
752 if( fwrite( p, 1, plen, fout ) != plen ||
753 fwrite( s, 1, slen, fout ) != slen )
754 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
755 }
756 else
757 mbedtls_printf( "%s%s", p, s );
758
759cleanup:
760
761 return( ret );
762}
763#endif /* MBEDTLS_FS_IO */
764
765/*
766 * Import X from unsigned binary data, big endian
767 */
768int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
769{
770 int ret;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100771 size_t i, j;
772 size_t const limbs = CHARS_TO_LIMBS( buflen );
Jens Wiklander817466c2018-05-22 13:49:31 +0200773
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100774 MPI_VALIDATE_RET( X != NULL );
775 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200776
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100777 /* Ensure that target MPI has exactly the necessary number of limbs */
778 if( X->n != limbs )
779 {
780 mbedtls_mpi_free( X );
781 mbedtls_mpi_init( X );
782 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, limbs ) );
783 }
784
Jens Wiklander817466c2018-05-22 13:49:31 +0200785 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
786
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100787 for( i = buflen, j = 0; i > 0; i--, j++ )
Jens Wiklander817466c2018-05-22 13:49:31 +0200788 X->p[j / ciL] |= ((mbedtls_mpi_uint) buf[i - 1]) << ((j % ciL) << 3);
789
790cleanup:
791
792 return( ret );
793}
794
795/*
796 * Export X into unsigned binary data, big endian
797 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100798int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
799 unsigned char *buf, size_t buflen )
Jens Wiklander817466c2018-05-22 13:49:31 +0200800{
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100801 size_t stored_bytes;
802 size_t bytes_to_copy;
803 unsigned char *p;
804 size_t i;
Jens Wiklander817466c2018-05-22 13:49:31 +0200805
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100806 MPI_VALIDATE_RET( X != NULL );
807 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200808
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100809 stored_bytes = X->n * ciL;
Jens Wiklander817466c2018-05-22 13:49:31 +0200810
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100811 if( stored_bytes < buflen )
812 {
813 /* There is enough space in the output buffer. Write initial
814 * null bytes and record the position at which to start
815 * writing the significant bytes. In this case, the execution
816 * trace of this function does not depend on the value of the
817 * number. */
818 bytes_to_copy = stored_bytes;
819 p = buf + buflen - stored_bytes;
820 memset( buf, 0, buflen - stored_bytes );
821 }
822 else
823 {
824 /* The output buffer is smaller than the allocated size of X.
825 * However X may fit if its leading bytes are zero. */
826 bytes_to_copy = buflen;
827 p = buf;
828 for( i = bytes_to_copy; i < stored_bytes; i++ )
829 {
830 if( GET_BYTE( X, i ) != 0 )
831 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
832 }
833 }
Jens Wiklander817466c2018-05-22 13:49:31 +0200834
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100835 for( i = 0; i < bytes_to_copy; i++ )
836 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
Jens Wiklander817466c2018-05-22 13:49:31 +0200837
838 return( 0 );
839}
840
841/*
842 * Left-shift: X <<= count
843 */
844int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
845{
846 int ret;
847 size_t i, v0, t1;
848 mbedtls_mpi_uint r0 = 0, r1;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100849 MPI_VALIDATE_RET( X != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200850
851 v0 = count / (biL );
852 t1 = count & (biL - 1);
853
854 i = mbedtls_mpi_bitlen( X ) + count;
855
856 if( X->n * biL < i )
857 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
858
859 ret = 0;
860
861 /*
862 * shift by count / limb_size
863 */
864 if( v0 > 0 )
865 {
866 for( i = X->n; i > v0; i-- )
867 X->p[i - 1] = X->p[i - v0 - 1];
868
869 for( ; i > 0; i-- )
870 X->p[i - 1] = 0;
871 }
872
873 /*
874 * shift by count % limb_size
875 */
876 if( t1 > 0 )
877 {
878 for( i = v0; i < X->n; i++ )
879 {
880 r1 = X->p[i] >> (biL - t1);
881 X->p[i] <<= t1;
882 X->p[i] |= r0;
883 r0 = r1;
884 }
885 }
886
887cleanup:
888
889 return( ret );
890}
891
892/*
893 * Right-shift: X >>= count
894 */
895int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
896{
897 size_t i, v0, v1;
898 mbedtls_mpi_uint r0 = 0, r1;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100899 MPI_VALIDATE_RET( X != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200900
901 v0 = count / biL;
902 v1 = count & (biL - 1);
903
904 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
905 return mbedtls_mpi_lset( X, 0 );
906
907 /*
908 * shift by count / limb_size
909 */
910 if( v0 > 0 )
911 {
912 for( i = 0; i < X->n - v0; i++ )
913 X->p[i] = X->p[i + v0];
914
915 for( ; i < X->n; i++ )
916 X->p[i] = 0;
917 }
918
919 /*
920 * shift by count % limb_size
921 */
922 if( v1 > 0 )
923 {
924 for( i = X->n; i > 0; i-- )
925 {
926 r1 = X->p[i - 1] << (biL - v1);
927 X->p[i - 1] >>= v1;
928 X->p[i - 1] |= r0;
929 r0 = r1;
930 }
931 }
932
933 return( 0 );
934}
935
936/*
937 * Compare unsigned values
938 */
939int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
940{
941 size_t i, j;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100942 MPI_VALIDATE_RET( X != NULL );
943 MPI_VALIDATE_RET( Y != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200944
945 for( i = X->n; i > 0; i-- )
946 if( X->p[i - 1] != 0 )
947 break;
948
949 for( j = Y->n; j > 0; j-- )
950 if( Y->p[j - 1] != 0 )
951 break;
952
953 if( i == 0 && j == 0 )
954 return( 0 );
955
956 if( i > j ) return( 1 );
957 if( j > i ) return( -1 );
958
959 for( ; i > 0; i-- )
960 {
961 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
962 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
963 }
964
965 return( 0 );
966}
967
968/*
969 * Compare signed values
970 */
971int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
972{
973 size_t i, j;
Jens Wiklander50a57cf2019-03-13 10:41:54 +0100974 MPI_VALIDATE_RET( X != NULL );
975 MPI_VALIDATE_RET( Y != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +0200976
977 for( i = X->n; i > 0; i-- )
978 if( X->p[i - 1] != 0 )
979 break;
980
981 for( j = Y->n; j > 0; j-- )
982 if( Y->p[j - 1] != 0 )
983 break;
984
985 if( i == 0 && j == 0 )
986 return( 0 );
987
988 if( i > j ) return( X->s );
989 if( j > i ) return( -Y->s );
990
991 if( X->s > 0 && Y->s < 0 ) return( 1 );
992 if( Y->s > 0 && X->s < 0 ) return( -1 );
993
994 for( ; i > 0; i-- )
995 {
996 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
997 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
998 }
999
1000 return( 0 );
1001}
1002
1003/*
1004 * Compare signed values
1005 */
1006int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
1007{
1008 mbedtls_mpi Y;
1009 mbedtls_mpi_uint p[1];
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001010 MPI_VALIDATE_RET( X != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001011
1012 *p = ( z < 0 ) ? -z : z;
1013 Y.s = ( z < 0 ) ? -1 : 1;
1014 Y.n = 1;
1015 Y.p = p;
1016
1017 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
1018}
1019
1020/*
1021 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1022 */
1023int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1024{
1025 int ret;
1026 size_t i, j;
1027 mbedtls_mpi_uint *o, *p, c, tmp;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001028 MPI_VALIDATE_RET( X != NULL );
1029 MPI_VALIDATE_RET( A != NULL );
1030 MPI_VALIDATE_RET( B != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001031
1032 if( X == B )
1033 {
1034 const mbedtls_mpi *T = A; A = X; B = T;
1035 }
1036
1037 if( X != A )
1038 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
1039
1040 /*
1041 * X should always be positive as a result of unsigned additions.
1042 */
1043 X->s = 1;
1044
1045 for( j = B->n; j > 0; j-- )
1046 if( B->p[j - 1] != 0 )
1047 break;
1048
1049 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1050
1051 o = B->p; p = X->p; c = 0;
1052
1053 /*
1054 * tmp is used because it might happen that p == o
1055 */
1056 for( i = 0; i < j; i++, o++, p++ )
1057 {
1058 tmp= *o;
1059 *p += c; c = ( *p < c );
1060 *p += tmp; c += ( *p < tmp );
1061 }
1062
1063 while( c != 0 )
1064 {
1065 if( i >= X->n )
1066 {
1067 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
1068 p = X->p + i;
1069 }
1070
1071 *p += c; c = ( *p < c ); i++; p++;
1072 }
1073
1074cleanup:
1075
1076 return( ret );
1077}
1078
1079/*
1080 * Helper for mbedtls_mpi subtraction
1081 */
1082static void mpi_sub_hlp( size_t n, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d )
1083{
1084 size_t i;
1085 mbedtls_mpi_uint c, z;
1086
1087 for( i = c = 0; i < n; i++, s++, d++ )
1088 {
1089 z = ( *d < c ); *d -= c;
1090 c = ( *d < *s ) + z; *d -= *s;
1091 }
1092
1093 while( c != 0 )
1094 {
1095 z = ( *d < c ); *d -= c;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001096 c = z; d++;
Jens Wiklander817466c2018-05-22 13:49:31 +02001097 }
1098}
1099
1100/*
1101 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
1102 */
1103int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1104{
1105 mbedtls_mpi TB;
1106 int ret;
1107 size_t n;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001108 MPI_VALIDATE_RET( X != NULL );
1109 MPI_VALIDATE_RET( A != NULL );
1110 MPI_VALIDATE_RET( B != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001111
1112 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1113 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1114
Jens Wiklanderd831db42018-11-08 11:18:22 +01001115 mbedtls_mpi_init_mempool( &TB );
Jens Wiklander817466c2018-05-22 13:49:31 +02001116
1117 if( X == B )
1118 {
1119 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
1120 B = &TB;
1121 }
1122
1123 if( X != A )
1124 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
1125
1126 /*
1127 * X should always be positive as a result of unsigned subtractions.
1128 */
1129 X->s = 1;
1130
1131 ret = 0;
1132
1133 for( n = B->n; n > 0; n-- )
1134 if( B->p[n - 1] != 0 )
1135 break;
1136
1137 mpi_sub_hlp( n, B->p, X->p );
1138
1139cleanup:
1140
1141 mbedtls_mpi_free( &TB );
1142
1143 return( ret );
1144}
1145
1146/*
1147 * Signed addition: X = A + B
1148 */
1149int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1150{
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001151 int ret, s;
1152 MPI_VALIDATE_RET( X != NULL );
1153 MPI_VALIDATE_RET( A != NULL );
1154 MPI_VALIDATE_RET( B != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001155
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001156 s = A->s;
Jens Wiklander817466c2018-05-22 13:49:31 +02001157 if( A->s * B->s < 0 )
1158 {
1159 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1160 {
1161 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1162 X->s = s;
1163 }
1164 else
1165 {
1166 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1167 X->s = -s;
1168 }
1169 }
1170 else
1171 {
1172 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1173 X->s = s;
1174 }
1175
1176cleanup:
1177
1178 return( ret );
1179}
1180
1181/*
1182 * Signed subtraction: X = A - B
1183 */
1184int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1185{
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001186 int ret, s;
1187 MPI_VALIDATE_RET( X != NULL );
1188 MPI_VALIDATE_RET( A != NULL );
1189 MPI_VALIDATE_RET( B != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001190
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001191 s = A->s;
Jens Wiklander817466c2018-05-22 13:49:31 +02001192 if( A->s * B->s > 0 )
1193 {
1194 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1195 {
1196 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1197 X->s = s;
1198 }
1199 else
1200 {
1201 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1202 X->s = -s;
1203 }
1204 }
1205 else
1206 {
1207 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1208 X->s = s;
1209 }
1210
1211cleanup:
1212
1213 return( ret );
1214}
1215
1216/*
1217 * Signed addition: X = A + b
1218 */
1219int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1220{
1221 mbedtls_mpi _B;
1222 mbedtls_mpi_uint p[1];
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001223 MPI_VALIDATE_RET( X != NULL );
1224 MPI_VALIDATE_RET( A != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001225
1226 p[0] = ( b < 0 ) ? -b : b;
1227 _B.s = ( b < 0 ) ? -1 : 1;
1228 _B.n = 1;
1229 _B.p = p;
1230
1231 return( mbedtls_mpi_add_mpi( X, A, &_B ) );
1232}
1233
1234/*
1235 * Signed subtraction: X = A - b
1236 */
1237int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1238{
1239 mbedtls_mpi _B;
1240 mbedtls_mpi_uint p[1];
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001241 MPI_VALIDATE_RET( X != NULL );
1242 MPI_VALIDATE_RET( A != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001243
1244 p[0] = ( b < 0 ) ? -b : b;
1245 _B.s = ( b < 0 ) ? -1 : 1;
1246 _B.n = 1;
1247 _B.p = p;
1248
1249 return( mbedtls_mpi_sub_mpi( X, A, &_B ) );
1250}
1251
1252/*
1253 * Helper for mbedtls_mpi multiplication
1254 */
1255static
1256#if defined(__APPLE__) && defined(__arm__)
1257/*
1258 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1259 * appears to need this to prevent bad ARM code generation at -O3.
1260 */
1261__attribute__ ((noinline))
1262#endif
1263void mpi_mul_hlp( size_t i, mbedtls_mpi_uint *s, mbedtls_mpi_uint *d, mbedtls_mpi_uint b )
1264{
1265 mbedtls_mpi_uint c = 0, t = 0;
1266
1267#if defined(MULADDC_HUIT)
1268 for( ; i >= 8; i -= 8 )
1269 {
1270 MULADDC_INIT
1271 MULADDC_HUIT
1272 MULADDC_STOP
1273 }
1274
1275 for( ; i > 0; i-- )
1276 {
1277 MULADDC_INIT
1278 MULADDC_CORE
1279 MULADDC_STOP
1280 }
1281#else /* MULADDC_HUIT */
1282 for( ; i >= 16; i -= 16 )
1283 {
1284 MULADDC_INIT
1285 MULADDC_CORE MULADDC_CORE
1286 MULADDC_CORE MULADDC_CORE
1287 MULADDC_CORE MULADDC_CORE
1288 MULADDC_CORE MULADDC_CORE
1289
1290 MULADDC_CORE MULADDC_CORE
1291 MULADDC_CORE MULADDC_CORE
1292 MULADDC_CORE MULADDC_CORE
1293 MULADDC_CORE MULADDC_CORE
1294 MULADDC_STOP
1295 }
1296
1297 for( ; i >= 8; i -= 8 )
1298 {
1299 MULADDC_INIT
1300 MULADDC_CORE MULADDC_CORE
1301 MULADDC_CORE MULADDC_CORE
1302
1303 MULADDC_CORE MULADDC_CORE
1304 MULADDC_CORE MULADDC_CORE
1305 MULADDC_STOP
1306 }
1307
1308 for( ; i > 0; i-- )
1309 {
1310 MULADDC_INIT
1311 MULADDC_CORE
1312 MULADDC_STOP
1313 }
1314#endif /* MULADDC_HUIT */
1315
1316 t++;
1317
1318 do {
1319 *d += c; c = ( *d < c ); d++;
1320 }
1321 while( c != 0 );
1322}
1323
1324/*
1325 * Baseline multiplication: X = A * B (HAC 14.12)
1326 */
1327int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1328{
1329 int ret;
1330 size_t i, j;
1331 mbedtls_mpi TA, TB;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001332 MPI_VALIDATE_RET( X != NULL );
1333 MPI_VALIDATE_RET( A != NULL );
1334 MPI_VALIDATE_RET( B != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001335
Jens Wiklanderd831db42018-11-08 11:18:22 +01001336 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB );
Jens Wiklander817466c2018-05-22 13:49:31 +02001337
1338 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1339 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
1340
1341 for( i = A->n; i > 0; i-- )
1342 if( A->p[i - 1] != 0 )
1343 break;
1344
1345 for( j = B->n; j > 0; j-- )
1346 if( B->p[j - 1] != 0 )
1347 break;
1348
1349 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1350 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
1351
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001352 for( ; j > 0; j-- )
1353 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
Jens Wiklander817466c2018-05-22 13:49:31 +02001354
1355 X->s = A->s * B->s;
1356
1357cleanup:
1358
1359 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
1360
1361 return( ret );
1362}
1363
1364/*
1365 * Baseline multiplication: X = A * b
1366 */
1367int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
1368{
1369 mbedtls_mpi _B;
1370 mbedtls_mpi_uint p[1];
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001371 MPI_VALIDATE_RET( X != NULL );
1372 MPI_VALIDATE_RET( A != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001373
1374 _B.s = 1;
1375 _B.n = 1;
1376 _B.p = p;
1377 p[0] = b;
1378
1379 return( mbedtls_mpi_mul_mpi( X, A, &_B ) );
1380}
1381
1382/*
1383 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1384 * mbedtls_mpi_uint divisor, d
1385 */
1386static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1387 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
1388{
1389#if defined(MBEDTLS_HAVE_UDBL)
1390 mbedtls_t_udbl dividend, quotient;
1391#else
1392 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1393 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
1394 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1395 mbedtls_mpi_uint u0_msw, u0_lsw;
1396 size_t s;
1397#endif
1398
1399 /*
1400 * Check for overflow
1401 */
1402 if( 0 == d || u1 >= d )
1403 {
1404 if (r != NULL) *r = ~0;
1405
1406 return ( ~0 );
1407 }
1408
1409#if defined(MBEDTLS_HAVE_UDBL)
1410 dividend = (mbedtls_t_udbl) u1 << biL;
1411 dividend |= (mbedtls_t_udbl) u0;
1412 quotient = dividend / d;
1413 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1414 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1415
1416 if( r != NULL )
1417 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
1418
1419 return (mbedtls_mpi_uint) quotient;
1420#else
1421
1422 /*
1423 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1424 * Vol. 2 - Seminumerical Algorithms, Knuth
1425 */
1426
1427 /*
1428 * Normalize the divisor, d, and dividend, u0, u1
1429 */
1430 s = mbedtls_clz( d );
1431 d = d << s;
1432
1433 u1 = u1 << s;
1434 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
1435 u0 = u0 << s;
1436
1437 d1 = d >> biH;
1438 d0 = d & uint_halfword_mask;
1439
1440 u0_msw = u0 >> biH;
1441 u0_lsw = u0 & uint_halfword_mask;
1442
1443 /*
1444 * Find the first quotient and remainder
1445 */
1446 q1 = u1 / d1;
1447 r0 = u1 - d1 * q1;
1448
1449 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1450 {
1451 q1 -= 1;
1452 r0 += d1;
1453
1454 if ( r0 >= radix ) break;
1455 }
1456
1457 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
1458 q0 = rAX / d1;
1459 r0 = rAX - q0 * d1;
1460
1461 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1462 {
1463 q0 -= 1;
1464 r0 += d1;
1465
1466 if ( r0 >= radix ) break;
1467 }
1468
1469 if (r != NULL)
1470 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
1471
1472 quotient = q1 * radix + q0;
1473
1474 return quotient;
1475#endif
1476}
1477
1478/*
1479 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1480 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001481int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1482 const mbedtls_mpi *B )
Jens Wiklander817466c2018-05-22 13:49:31 +02001483{
1484 int ret;
1485 size_t i, n, t, k;
1486 mbedtls_mpi X, Y, Z, T1, T2;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001487 MPI_VALIDATE_RET( A != NULL );
1488 MPI_VALIDATE_RET( B != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001489
1490 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1491 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1492
Jens Wiklanderd831db42018-11-08 11:18:22 +01001493 mbedtls_mpi_init_mempool( &X ); mbedtls_mpi_init_mempool( &Y );
1494 mbedtls_mpi_init_mempool( &Z ); mbedtls_mpi_init_mempool( &T1 );
1495 mbedtls_mpi_init_mempool( &T2 );
Jens Wiklander817466c2018-05-22 13:49:31 +02001496
1497 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1498 {
1499 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1500 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
1501 return( 0 );
1502 }
1503
1504 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1505 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
1506 X.s = Y.s = 1;
1507
1508 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1509 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1510 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, 2 ) );
1511 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2, 3 ) );
1512
1513 k = mbedtls_mpi_bitlen( &Y ) % biL;
1514 if( k < biL - 1 )
1515 {
1516 k = biL - 1 - k;
1517 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1518 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
1519 }
1520 else k = 0;
1521
1522 n = X.n - 1;
1523 t = Y.n - 1;
1524 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
1525
1526 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
1527 {
1528 Z.p[n - t]++;
1529 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
1530 }
1531 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
1532
1533 for( i = n; i > t ; i-- )
1534 {
1535 if( X.p[i] >= Y.p[t] )
1536 Z.p[i - t - 1] = ~0;
1537 else
1538 {
1539 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1540 Y.p[t], NULL);
1541 }
1542
1543 Z.p[i - t - 1]++;
1544 do
1545 {
1546 Z.p[i - t - 1]--;
1547
1548 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
1549 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
1550 T1.p[1] = Y.p[t];
1551 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1552
1553 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2, 0 ) );
1554 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1555 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1556 T2.p[2] = X.p[i];
1557 }
1558 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
1559
1560 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1561 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1562 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
1563
1564 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
1565 {
1566 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1567 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1568 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
1569 Z.p[i - t - 1]--;
1570 }
1571 }
1572
1573 if( Q != NULL )
1574 {
1575 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
1576 Q->s = A->s * B->s;
1577 }
1578
1579 if( R != NULL )
1580 {
1581 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
1582 X.s = A->s;
1583 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
1584
1585 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
1586 R->s = 1;
1587 }
1588
1589cleanup:
1590
1591 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1592 mbedtls_mpi_free( &T1 ); mbedtls_mpi_free( &T2 );
1593
1594 return( ret );
1595}
1596
1597/*
1598 * Division by int: A = Q * b + R
1599 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001600int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1601 const mbedtls_mpi *A,
1602 mbedtls_mpi_sint b )
Jens Wiklander817466c2018-05-22 13:49:31 +02001603{
1604 mbedtls_mpi _B;
1605 mbedtls_mpi_uint p[1];
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001606 MPI_VALIDATE_RET( A != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001607
1608 p[0] = ( b < 0 ) ? -b : b;
1609 _B.s = ( b < 0 ) ? -1 : 1;
1610 _B.n = 1;
1611 _B.p = p;
1612
1613 return( mbedtls_mpi_div_mpi( Q, R, A, &_B ) );
1614}
1615
1616/*
1617 * Modulo: R = A mod B
1618 */
1619int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1620{
1621 int ret;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001622 MPI_VALIDATE_RET( R != NULL );
1623 MPI_VALIDATE_RET( A != NULL );
1624 MPI_VALIDATE_RET( B != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001625
1626 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1627 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1628
1629 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
1630
1631 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1632 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
1633
1634 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1635 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
1636
1637cleanup:
1638
1639 return( ret );
1640}
1641
1642/*
1643 * Modulo: r = A mod b
1644 */
1645int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1646{
1647 size_t i;
1648 mbedtls_mpi_uint x, y, z;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001649 MPI_VALIDATE_RET( r != NULL );
1650 MPI_VALIDATE_RET( A != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02001651
1652 if( b == 0 )
1653 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1654
1655 if( b < 0 )
1656 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1657
1658 /*
1659 * handle trivial cases
1660 */
1661 if( b == 1 )
1662 {
1663 *r = 0;
1664 return( 0 );
1665 }
1666
1667 if( b == 2 )
1668 {
1669 *r = A->p[0] & 1;
1670 return( 0 );
1671 }
1672
1673 /*
1674 * general case
1675 */
1676 for( i = A->n, y = 0; i > 0; i-- )
1677 {
1678 x = A->p[i - 1];
1679 y = ( y << biH ) | ( x >> biH );
1680 z = y / b;
1681 y -= z * b;
1682
1683 x <<= biH;
1684 y = ( y << biH ) | ( x >> biH );
1685 z = y / b;
1686 y -= z * b;
1687 }
1688
1689 /*
1690 * If A is negative, then the current y represents a negative value.
1691 * Flipping it to the positive side.
1692 */
1693 if( A->s < 0 && y != 0 )
1694 y = b - y;
1695
1696 *r = y;
1697
1698 return( 0 );
1699}
1700
1701/*
1702 * Fast Montgomery initialization (thanks to Tom St Denis)
1703 */
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001704void mbedtls_mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
Jens Wiklander817466c2018-05-22 13:49:31 +02001705{
1706 mbedtls_mpi_uint x, m0 = N->p[0];
1707 unsigned int i;
1708
1709 x = m0;
1710 x += ( ( m0 + 2 ) & 4 ) << 1;
1711
1712 for( i = biL; i >= 8; i /= 2 )
1713 x *= ( 2 - ( m0 * x ) );
1714
1715 *mm = ~x + 1;
1716}
1717
1718/*
1719 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1720 */
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001721int mbedtls_mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B,
1722 const mbedtls_mpi *N, mbedtls_mpi_uint mm,
Jens Wiklander817466c2018-05-22 13:49:31 +02001723 const mbedtls_mpi *T )
1724{
1725 size_t i, n, m;
1726 mbedtls_mpi_uint u0, u1, *d;
1727
1728 if( T->n < N->n + 1 || T->p == NULL )
1729 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1730
1731 memset( T->p, 0, T->n * ciL );
1732
1733 d = T->p;
1734 n = N->n;
1735 m = ( B->n < n ) ? B->n : n;
1736
1737 for( i = 0; i < n; i++ )
1738 {
1739 /*
1740 * T = (T + u0*B + u1*N) / 2^biL
1741 */
1742 u0 = A->p[i];
1743 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1744
1745 mpi_mul_hlp( m, B->p, d, u0 );
1746 mpi_mul_hlp( n, N->p, d, u1 );
1747
1748 *d++ = u0; d[n + 1] = 0;
1749 }
1750
1751 memcpy( A->p, d, ( n + 1 ) * ciL );
1752
1753 if( mbedtls_mpi_cmp_abs( A, N ) >= 0 )
1754 mpi_sub_hlp( n, N->p, A->p );
1755 else
1756 /* prevent timing attacks */
1757 mpi_sub_hlp( n, A->p, T->p );
1758
1759 return( 0 );
1760}
1761
1762/*
1763 * Montgomery reduction: A = A * R^-1 mod N
1764 */
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001765int mbedtls_mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
1766 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
Jens Wiklander817466c2018-05-22 13:49:31 +02001767{
1768 mbedtls_mpi_uint z = 1;
1769 mbedtls_mpi U;
1770
1771 U.n = U.s = (int) z;
1772 U.p = &z;
1773
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001774 return( mbedtls_mpi_montmul( A, &U, N, mm, T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001775}
1776
1777/*
1778 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1779 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001780int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
1781 const mbedtls_mpi *E, const mbedtls_mpi *N,
1782 mbedtls_mpi *_RR )
Jens Wiklander817466c2018-05-22 13:49:31 +02001783{
1784 int ret;
1785 size_t wbits, wsize, one = 1;
1786 size_t i, j, nblimbs;
1787 size_t bufsize, nbits;
1788 mbedtls_mpi_uint ei, mm, state;
1789 mbedtls_mpi RR, T, W[ 2 << MBEDTLS_MPI_WINDOW_SIZE ], Apos;
1790 int neg;
1791
Jens Wiklander50a57cf2019-03-13 10:41:54 +01001792 MPI_VALIDATE_RET( X != NULL );
1793 MPI_VALIDATE_RET( A != NULL );
1794 MPI_VALIDATE_RET( E != NULL );
1795 MPI_VALIDATE_RET( N != NULL );
1796
1797 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
Jens Wiklander817466c2018-05-22 13:49:31 +02001798 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1799
1800 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
1801 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
1802
1803 /*
1804 * Init temps and window size
1805 */
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001806 mbedtls_mpi_montg_init( &mm, N );
Jens Wiklanderd831db42018-11-08 11:18:22 +01001807 mbedtls_mpi_init_mempool( &RR ); mbedtls_mpi_init_mempool( &T );
1808 mbedtls_mpi_init_mempool( &Apos );
Jens Wiklanderae499f62019-04-17 12:25:20 +02001809 for( i = 0; i < ARRAY_SIZE(W); i++ )
1810 mbedtls_mpi_init_mempool( W + i );
Jens Wiklander817466c2018-05-22 13:49:31 +02001811
1812 i = mbedtls_mpi_bitlen( E );
1813
1814 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
1815 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
1816
1817 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
1818 wsize = MBEDTLS_MPI_WINDOW_SIZE;
1819
1820 j = N->n + 1;
1821 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1822 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
1823 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
1824
1825 /*
1826 * Compensate for negative A (and correct at the end)
1827 */
1828 neg = ( A->s == -1 );
1829 if( neg )
1830 {
1831 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
1832 Apos.s = 1;
1833 A = &Apos;
1834 }
1835
1836 /*
1837 * If 1st call, pre-compute R^2 mod N
1838 */
1839 if( _RR == NULL || _RR->p == NULL )
1840 {
1841 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
1842 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
1843 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
1844
1845 if( _RR != NULL )
1846 memcpy( _RR, &RR, sizeof( mbedtls_mpi ) );
1847 }
1848 else
1849 memcpy( &RR, _RR, sizeof( mbedtls_mpi ) );
1850
1851 /*
1852 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1853 */
1854 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
1855 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
1856 else
1857 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
1858
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001859 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( &W[1], &RR, N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001860
1861 /*
1862 * X = R^2 * R^-1 mod N = R mod N
1863 */
1864 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001865 MBEDTLS_MPI_CHK( mbedtls_mpi_montred( X, N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001866
1867 if( wsize > 1 )
1868 {
1869 /*
1870 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1871 */
1872 j = one << ( wsize - 1 );
1873
1874 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
1875 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
1876
1877 for( i = 0; i < wsize - 1; i++ )
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001878 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( &W[j], &W[j], N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001879
1880 /*
1881 * W[i] = W[i - 1] * W[1]
1882 */
1883 for( i = j + 1; i < ( one << wsize ); i++ )
1884 {
1885 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
1886 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
1887
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001888 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( &W[i], &W[1], N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001889 }
1890 }
1891
1892 nblimbs = E->n;
1893 bufsize = 0;
1894 nbits = 0;
1895 wbits = 0;
1896 state = 0;
1897
1898 while( 1 )
1899 {
1900 if( bufsize == 0 )
1901 {
1902 if( nblimbs == 0 )
1903 break;
1904
1905 nblimbs--;
1906
1907 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
1908 }
1909
1910 bufsize--;
1911
1912 ei = (E->p[nblimbs] >> bufsize) & 1;
1913
1914 /*
1915 * skip leading 0s
1916 */
1917 if( ei == 0 && state == 0 )
1918 continue;
1919
1920 if( ei == 0 && state == 1 )
1921 {
1922 /*
1923 * out of window, square X
1924 */
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001925 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001926 continue;
1927 }
1928
1929 /*
1930 * add ei to current window
1931 */
1932 state = 2;
1933
1934 nbits++;
1935 wbits |= ( ei << ( wsize - nbits ) );
1936
1937 if( nbits == wsize )
1938 {
1939 /*
1940 * X = X^wsize R^-1 mod N
1941 */
1942 for( i = 0; i < wsize; i++ )
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001943 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001944
1945 /*
1946 * X = X * W[wbits] R^-1 mod N
1947 */
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001948 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, &W[wbits], N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001949
1950 state--;
1951 nbits = 0;
1952 wbits = 0;
1953 }
1954 }
1955
1956 /*
1957 * process the remaining bits
1958 */
1959 for( i = 0; i < nbits; i++ )
1960 {
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001961 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, X, N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001962
1963 wbits <<= 1;
1964
1965 if( ( wbits & ( one << wsize ) ) != 0 )
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001966 MBEDTLS_MPI_CHK( mbedtls_mpi_montmul( X, &W[1], N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001967 }
1968
1969 /*
1970 * X = A^E * R * R^-1 mod N = A^E mod N
1971 */
Jens Wiklanderdf0f4882018-11-07 08:11:29 +01001972 MBEDTLS_MPI_CHK( mbedtls_mpi_montred( X, N, mm, &T ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02001973
1974 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
1975 {
1976 X->s = -1;
1977 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
1978 }
1979
1980cleanup:
1981
Jens Wiklanderae499f62019-04-17 12:25:20 +02001982 for( i = 0; i < ARRAY_SIZE(W); i++ )
1983 mbedtls_mpi_free( W + i );
Jens Wiklander817466c2018-05-22 13:49:31 +02001984
Jens Wiklanderae499f62019-04-17 12:25:20 +02001985 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
Jens Wiklander817466c2018-05-22 13:49:31 +02001986
1987 if( _RR == NULL || _RR->p == NULL )
1988 mbedtls_mpi_free( &RR );
1989
1990 return( ret );
1991}
1992
1993/*
1994 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1995 */
1996int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
1997{
1998 int ret;
1999 size_t lz, lzt;
2000 mbedtls_mpi TG, TA, TB;
2001
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002002 MPI_VALIDATE_RET( G != NULL );
2003 MPI_VALIDATE_RET( A != NULL );
2004 MPI_VALIDATE_RET( B != NULL );
2005
Jens Wiklanderd831db42018-11-08 11:18:22 +01002006 mbedtls_mpi_init_mempool( &TG ); mbedtls_mpi_init_mempool( &TA );
2007 mbedtls_mpi_init_mempool( &TB );
Jens Wiklander817466c2018-05-22 13:49:31 +02002008
2009 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2010 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
2011
2012 lz = mbedtls_mpi_lsb( &TA );
2013 lzt = mbedtls_mpi_lsb( &TB );
2014
2015 if( lzt < lz )
2016 lz = lzt;
2017
2018 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, lz ) );
2019 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, lz ) );
2020
2021 TA.s = TB.s = 1;
2022
2023 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
2024 {
2025 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2026 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
2027
2028 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
2029 {
2030 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2031 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
2032 }
2033 else
2034 {
2035 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2036 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
2037 }
2038 }
2039
2040 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2041 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
2042
2043cleanup:
2044
2045 mbedtls_mpi_free( &TG ); mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
2046
2047 return( ret );
2048}
2049
2050/*
2051 * Fill X with size bytes of random.
2052 *
2053 * Use a temporary bytes representation to make sure the result is the same
2054 * regardless of the platform endianness (useful when f_rng is actually
2055 * deterministic, eg for tests).
2056 */
2057int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
2058 int (*f_rng)(void *, unsigned char *, size_t),
2059 void *p_rng )
2060{
2061 int ret;
2062 unsigned char buf[MBEDTLS_MPI_MAX_SIZE];
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002063 MPI_VALIDATE_RET( X != NULL );
2064 MPI_VALIDATE_RET( f_rng != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02002065
2066 if( size > MBEDTLS_MPI_MAX_SIZE )
2067 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2068
2069 MBEDTLS_MPI_CHK( f_rng( p_rng, buf, size ) );
2070 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X, buf, size ) );
2071
2072cleanup:
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002073 mbedtls_platform_zeroize( buf, sizeof( buf ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02002074 return( ret );
2075}
2076
2077/*
2078 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2079 */
2080int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
2081{
2082 int ret;
2083 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002084 MPI_VALIDATE_RET( X != NULL );
2085 MPI_VALIDATE_RET( A != NULL );
2086 MPI_VALIDATE_RET( N != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02002087
2088 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
2089 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2090
Jens Wiklanderd831db42018-11-08 11:18:22 +01002091 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TU );
2092 mbedtls_mpi_init_mempool( &U1 ); mbedtls_mpi_init_mempool( &U2 );
2093 mbedtls_mpi_init_mempool( &G ); mbedtls_mpi_init_mempool( &TB );
2094 mbedtls_mpi_init_mempool( &TV ); mbedtls_mpi_init_mempool( &V1 );
2095 mbedtls_mpi_init_mempool( &V2 );
Jens Wiklander817466c2018-05-22 13:49:31 +02002096
2097 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
2098
2099 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
2100 {
2101 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2102 goto cleanup;
2103 }
2104
2105 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2106 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2107 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2108 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
2109
2110 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2111 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2112 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2113 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
2114
2115 do
2116 {
2117 while( ( TU.p[0] & 1 ) == 0 )
2118 {
2119 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
2120
2121 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2122 {
2123 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2124 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
2125 }
2126
2127 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2128 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
2129 }
2130
2131 while( ( TV.p[0] & 1 ) == 0 )
2132 {
2133 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
2134
2135 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2136 {
2137 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2138 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
2139 }
2140
2141 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2142 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
2143 }
2144
2145 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
2146 {
2147 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2148 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2149 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
2150 }
2151 else
2152 {
2153 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2154 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2155 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
2156 }
2157 }
2158 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
2159
2160 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2161 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
2162
2163 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2164 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
2165
2166 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
2167
2168cleanup:
2169
2170 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2171 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2172 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
2173
2174 return( ret );
2175}
2176
2177#if defined(MBEDTLS_GENPRIME)
2178
2179static const int small_prime[] =
2180{
2181 3, 5, 7, 11, 13, 17, 19, 23,
2182 29, 31, 37, 41, 43, 47, 53, 59,
2183 61, 67, 71, 73, 79, 83, 89, 97,
2184 101, 103, 107, 109, 113, 127, 131, 137,
2185 139, 149, 151, 157, 163, 167, 173, 179,
2186 181, 191, 193, 197, 199, 211, 223, 227,
2187 229, 233, 239, 241, 251, 257, 263, 269,
2188 271, 277, 281, 283, 293, 307, 311, 313,
2189 317, 331, 337, 347, 349, 353, 359, 367,
2190 373, 379, 383, 389, 397, 401, 409, 419,
2191 421, 431, 433, 439, 443, 449, 457, 461,
2192 463, 467, 479, 487, 491, 499, 503, 509,
2193 521, 523, 541, 547, 557, 563, 569, 571,
2194 577, 587, 593, 599, 601, 607, 613, 617,
2195 619, 631, 641, 643, 647, 653, 659, 661,
2196 673, 677, 683, 691, 701, 709, 719, 727,
2197 733, 739, 743, 751, 757, 761, 769, 773,
2198 787, 797, 809, 811, 821, 823, 827, 829,
2199 839, 853, 857, 859, 863, 877, 881, 883,
2200 887, 907, 911, 919, 929, 937, 941, 947,
2201 953, 967, 971, 977, 983, 991, 997, -103
2202};
2203
2204/*
2205 * Small divisors test (X must be positive)
2206 *
2207 * Return values:
2208 * 0: no small factor (possible prime, more tests needed)
2209 * 1: certain prime
2210 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2211 * other negative: error
2212 */
2213static int mpi_check_small_factors( const mbedtls_mpi *X )
2214{
2215 int ret = 0;
2216 size_t i;
2217 mbedtls_mpi_uint r;
2218
2219 if( ( X->p[0] & 1 ) == 0 )
2220 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2221
2222 for( i = 0; small_prime[i] > 0; i++ )
2223 {
2224 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
2225 return( 1 );
2226
2227 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
2228
2229 if( r == 0 )
2230 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2231 }
2232
2233cleanup:
2234 return( ret );
2235}
2236
2237/*
2238 * Miller-Rabin pseudo-primality test (HAC 4.24)
2239 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002240static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
Jens Wiklander817466c2018-05-22 13:49:31 +02002241 int (*f_rng)(void *, unsigned char *, size_t),
2242 void *p_rng )
2243{
2244 int ret, count;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002245 size_t i, j, k, s;
Jens Wiklander817466c2018-05-22 13:49:31 +02002246 mbedtls_mpi W, R, T, A, RR;
2247
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002248 MPI_VALIDATE_RET( X != NULL );
2249 MPI_VALIDATE_RET( f_rng != NULL );
2250
Jens Wiklanderd831db42018-11-08 11:18:22 +01002251 mbedtls_mpi_init_mempool( &W ); mbedtls_mpi_init_mempool( &R );
2252 mbedtls_mpi_init_mempool( &T ); mbedtls_mpi_init_mempool( &A );
2253 mbedtls_mpi_init_mempool( &RR );
Jens Wiklander817466c2018-05-22 13:49:31 +02002254
2255 /*
2256 * W = |X| - 1
2257 * R = W >> lsb( W )
2258 */
2259 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2260 s = mbedtls_mpi_lsb( &W );
2261 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2262 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
2263
2264 i = mbedtls_mpi_bitlen( X );
Jens Wiklander817466c2018-05-22 13:49:31 +02002265
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002266 for( i = 0; i < rounds; i++ )
Jens Wiklander817466c2018-05-22 13:49:31 +02002267 {
2268 /*
2269 * pick a random A, 1 < A < |X| - 1
2270 */
Jens Wiklander817466c2018-05-22 13:49:31 +02002271 count = 0;
2272 do {
2273 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
2274
2275 j = mbedtls_mpi_bitlen( &A );
2276 k = mbedtls_mpi_bitlen( &W );
2277 if (j > k) {
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002278 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02002279 }
2280
Jens Wiklander2d6644e2018-11-27 12:21:24 +01002281 if (count++ > 300) {
Jens Wiklander9b0818d2019-01-17 11:14:38 +01002282 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2283 goto cleanup;
Jens Wiklander817466c2018-05-22 13:49:31 +02002284 }
2285
2286 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2287 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
2288
2289 /*
2290 * A = A^R mod |X|
2291 */
2292 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
2293
2294 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2295 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2296 continue;
2297
2298 j = 1;
2299 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
2300 {
2301 /*
2302 * A = A * A mod |X|
2303 */
2304 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2305 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
2306
2307 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2308 break;
2309
2310 j++;
2311 }
2312
2313 /*
2314 * not prime if A != |X| - 1 or A == 1
2315 */
2316 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2317 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2318 {
2319 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2320 break;
2321 }
2322 }
2323
2324cleanup:
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002325 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2326 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
Jens Wiklander817466c2018-05-22 13:49:31 +02002327 mbedtls_mpi_free( &RR );
2328
2329 return( ret );
2330}
2331
2332/*
2333 * Pseudo-primality test: small factors, then Miller-Rabin
2334 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002335int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2336 int (*f_rng)(void *, unsigned char *, size_t),
2337 void *p_rng )
Jens Wiklander817466c2018-05-22 13:49:31 +02002338{
2339 int ret;
2340 mbedtls_mpi XX;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002341 MPI_VALIDATE_RET( X != NULL );
2342 MPI_VALIDATE_RET( f_rng != NULL );
Jens Wiklander817466c2018-05-22 13:49:31 +02002343
2344 XX.s = 1;
2345 XX.n = X->n;
2346 XX.p = X->p;
2347
2348 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2349 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2350 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2351
2352 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
2353 return( 0 );
2354
2355 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2356 {
2357 if( ret == 1 )
2358 return( 0 );
2359
2360 return( ret );
2361 }
2362
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002363 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
Jens Wiklander817466c2018-05-22 13:49:31 +02002364}
2365
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002366#if !defined(MBEDTLS_DEPRECATED_REMOVED)
2367/*
2368 * Pseudo-primality test, error probability 2^-80
2369 */
2370int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2371 int (*f_rng)(void *, unsigned char *, size_t),
2372 void *p_rng )
2373{
2374 MPI_VALIDATE_RET( X != NULL );
2375 MPI_VALIDATE_RET( f_rng != NULL );
2376
2377 /*
2378 * In the past our key generation aimed for an error rate of at most
2379 * 2^-80. Since this function is deprecated, aim for the same certainty
2380 * here as well.
2381 */
2382 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
2383}
2384#endif
2385
Jens Wiklander817466c2018-05-22 13:49:31 +02002386/*
2387 * Prime number generation
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002388 *
2389 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2390 * be either 1024 bits or 1536 bits long, and flags must contain
2391 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
Jens Wiklander817466c2018-05-22 13:49:31 +02002392 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002393int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
Jens Wiklander817466c2018-05-22 13:49:31 +02002394 int (*f_rng)(void *, unsigned char *, size_t),
2395 void *p_rng )
2396{
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002397#ifdef MBEDTLS_HAVE_INT64
2398// ceil(2^63.5)
2399#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2400#else
2401// ceil(2^31.5)
2402#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2403#endif
2404 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
Jens Wiklander817466c2018-05-22 13:49:31 +02002405 size_t k, n;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002406 int rounds;
Jens Wiklander817466c2018-05-22 13:49:31 +02002407 mbedtls_mpi_uint r;
2408 mbedtls_mpi Y;
2409
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002410 MPI_VALIDATE_RET( X != NULL );
2411 MPI_VALIDATE_RET( f_rng != NULL );
2412
Jens Wiklander817466c2018-05-22 13:49:31 +02002413 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2414 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2415
Jens Wiklanderd831db42018-11-08 11:18:22 +01002416 mbedtls_mpi_init_mempool( &Y );
Jens Wiklander817466c2018-05-22 13:49:31 +02002417
2418 n = BITS_TO_LIMBS( nbits );
2419
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002420 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
Jens Wiklander817466c2018-05-22 13:49:31 +02002421 {
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002422 /*
2423 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2424 */
2425 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2426 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2427 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
Jens Wiklander817466c2018-05-22 13:49:31 +02002428 }
2429 else
2430 {
2431 /*
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002432 * 2^-100 error probability, number of rounds computed based on HAC,
2433 * fact 4.48
Jens Wiklander817466c2018-05-22 13:49:31 +02002434 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002435 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2436 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2437 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2438 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2439 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002440
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002441 while( 1 )
2442 {
2443 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2444 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2445 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
Jens Wiklander817466c2018-05-22 13:49:31 +02002446
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002447 k = n * biL;
2448 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2449 X->p[0] |= 1;
Jens Wiklander817466c2018-05-22 13:49:31 +02002450
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002451 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
Jens Wiklander817466c2018-05-22 13:49:31 +02002452 {
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002453 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
Jens Wiklander817466c2018-05-22 13:49:31 +02002454
2455 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2456 goto cleanup;
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002457 }
2458 else
2459 {
Jens Wiklander817466c2018-05-22 13:49:31 +02002460 /*
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002461 * An necessary condition for Y and X = 2Y + 1 to be prime
2462 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2463 * Make sure it is satisfied, while keeping X = 3 mod 4
Jens Wiklander817466c2018-05-22 13:49:31 +02002464 */
Jens Wiklander50a57cf2019-03-13 10:41:54 +01002465
2466 X->p[0] |= 2;
2467
2468 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2469 if( r == 0 )
2470 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2471 else if( r == 1 )
2472 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2473
2474 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2475 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2476 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2477
2478 while( 1 )
2479 {
2480 /*
2481 * First, check small factors for X and Y
2482 * before doing Miller-Rabin on any of them
2483 */
2484 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2485 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2486 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
2487 == 0 &&
2488 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
2489 == 0 )
2490 goto cleanup;
2491
2492 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2493 goto cleanup;
2494
2495 /*
2496 * Next candidates. We want to preserve Y = (X-1) / 2 and
2497 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2498 * so up Y by 6 and X by 12.
2499 */
2500 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2501 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
2502 }
Jens Wiklander817466c2018-05-22 13:49:31 +02002503 }
2504 }
2505
2506cleanup:
2507
2508 mbedtls_mpi_free( &Y );
2509
2510 return( ret );
2511}
2512
2513#endif /* MBEDTLS_GENPRIME */
2514
2515#if defined(MBEDTLS_SELF_TEST)
2516
2517#define GCD_PAIR_COUNT 3
2518
2519static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2520{
2521 { 693, 609, 21 },
2522 { 1764, 868, 28 },
2523 { 768454923, 542167814, 1 }
2524};
2525
2526/*
2527 * Checkup routine
2528 */
2529int mbedtls_mpi_self_test( int verbose )
2530{
2531 int ret, i;
2532 mbedtls_mpi A, E, N, X, Y, U, V;
2533
Jens Wiklanderd831db42018-11-08 11:18:22 +01002534 mbedtls_mpi_init_mempool( &A ); mbedtls_mpi_init_mempool( &E );
2535 mbedtls_mpi_init_mempool( &N ); mbedtls_mpi_init_mempool( &X );
2536 mbedtls_mpi_init_mempool( &Y ); mbedtls_mpi_init_mempool( &U );
2537 mbedtls_mpi_init_mempool( &V );
Jens Wiklander817466c2018-05-22 13:49:31 +02002538
2539 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
2540 "EFE021C2645FD1DC586E69184AF4A31E" \
2541 "D5F53E93B5F123FA41680867BA110131" \
2542 "944FE7952E2517337780CB0DB80E61AA" \
2543 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2544
2545 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
2546 "B2E7EFD37075B9F03FF989C7C5051C20" \
2547 "34D2A323810251127E7BF8625A4F49A5" \
2548 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2549 "5B5C25763222FEFCCFC38B832366C29E" ) );
2550
2551 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
2552 "0066A198186C18C10B2F5ED9B522752A" \
2553 "9830B69916E535C8F047518A889A43A5" \
2554 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2555
2556 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
2557
2558 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2559 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2560 "9E857EA95A03512E2BAE7391688D264A" \
2561 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2562 "8001B72E848A38CAE1C65F78E56ABDEF" \
2563 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2564 "ECF677152EF804370C1A305CAF3B5BF1" \
2565 "30879B56C61DE584A0F53A2447A51E" ) );
2566
2567 if( verbose != 0 )
2568 mbedtls_printf( " MPI test #1 (mul_mpi): " );
2569
2570 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2571 {
2572 if( verbose != 0 )
2573 mbedtls_printf( "failed\n" );
2574
2575 ret = 1;
2576 goto cleanup;
2577 }
2578
2579 if( verbose != 0 )
2580 mbedtls_printf( "passed\n" );
2581
2582 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
2583
2584 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2585 "256567336059E52CAE22925474705F39A94" ) );
2586
2587 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
2588 "6613F26162223DF488E9CD48CC132C7A" \
2589 "0AC93C701B001B092E4E5B9F73BCD27B" \
2590 "9EE50D0657C77F374E903CDFA4C642" ) );
2591
2592 if( verbose != 0 )
2593 mbedtls_printf( " MPI test #2 (div_mpi): " );
2594
2595 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2596 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
2597 {
2598 if( verbose != 0 )
2599 mbedtls_printf( "failed\n" );
2600
2601 ret = 1;
2602 goto cleanup;
2603 }
2604
2605 if( verbose != 0 )
2606 mbedtls_printf( "passed\n" );
2607
2608 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
2609
2610 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2611 "36E139AEA55215609D2816998ED020BB" \
2612 "BD96C37890F65171D948E9BC7CBAA4D9" \
2613 "325D24D6A3C12710F10A09FA08AB87" ) );
2614
2615 if( verbose != 0 )
2616 mbedtls_printf( " MPI test #3 (exp_mod): " );
2617
2618 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2619 {
2620 if( verbose != 0 )
2621 mbedtls_printf( "failed\n" );
2622
2623 ret = 1;
2624 goto cleanup;
2625 }
2626
2627 if( verbose != 0 )
2628 mbedtls_printf( "passed\n" );
2629
2630 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
2631
2632 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2633 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2634 "C3DBA76456363A10869622EAC2DD84EC" \
2635 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2636
2637 if( verbose != 0 )
2638 mbedtls_printf( " MPI test #4 (inv_mod): " );
2639
2640 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2641 {
2642 if( verbose != 0 )
2643 mbedtls_printf( "failed\n" );
2644
2645 ret = 1;
2646 goto cleanup;
2647 }
2648
2649 if( verbose != 0 )
2650 mbedtls_printf( "passed\n" );
2651
2652 if( verbose != 0 )
2653 mbedtls_printf( " MPI test #5 (simple gcd): " );
2654
2655 for( i = 0; i < GCD_PAIR_COUNT; i++ )
2656 {
2657 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
2658 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
2659
2660 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
2661
2662 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
2663 {
2664 if( verbose != 0 )
2665 mbedtls_printf( "failed at %d\n", i );
2666
2667 ret = 1;
2668 goto cleanup;
2669 }
2670 }
2671
2672 if( verbose != 0 )
2673 mbedtls_printf( "passed\n" );
2674
2675cleanup:
2676
2677 if( ret != 0 && verbose != 0 )
2678 mbedtls_printf( "Unexpected error, return code = %08X\n", ret );
2679
2680 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
2681 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
2682
2683 if( verbose != 0 )
2684 mbedtls_printf( "\n" );
2685
2686 return( ret );
2687}
2688
2689#endif /* MBEDTLS_SELF_TEST */
2690
2691#endif /* MBEDTLS_BIGNUM_C */