1 /*
2 * Multi-precision integer library
3 *
4 * Copyright The Mbed TLS Contributors
5 * 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.
18 */
19
20 /*
21 * The following sources were referenced in the design of this Multi-precision
22 * Integer library:
23 *
24 * [1] Handbook of Applied Cryptography - 1997
25 * Menezes, van Oorschot and Vanstone
26 *
27 * [2] Multi-Precision Math
28 * Tom St Denis
29 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
30 *
31 * [3] GNU Multi-Precision Arithmetic Library
32 * https://gmplib.org/manual/index.html
33 *
34 */
35
36 #include "common.h"
37
38 #if defined(MBEDTLS_BIGNUM_C)
39
40 #include "mbedtls/bignum.h"
41 #include "mbedtls/bn_mul.h"
42 #include "mbedtls/platform_util.h"
43 #include "mbedtls/error.h"
44 #include "constant_time_internal.h"
45
46 #include <limits.h>
47 #include <string.h>
48
49 #if defined(MBEDTLS_PLATFORM_C)
50 #include "mbedtls/platform.h"
51 #else
52 #include <stdio.h>
53 #include <stdlib.h>
54 #define mbedtls_printf printf
55 #define mbedtls_calloc calloc
56 #define mbedtls_free free
57 #endif
58
59 #include <mempool.h>
60 #include <util.h>
61
62 #define MPI_VALIDATE_RET( cond ) \
63 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_MPI_BAD_INPUT_DATA )
64 #define MPI_VALIDATE( cond ) \
65 MBEDTLS_INTERNAL_VALIDATE( cond )
66
67 #define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
68 #define biL (ciL << 3) /* bits in limb */
69 #define biH (ciL << 2) /* half limb size */
70
71 #define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
72
73 /*
74 * Convert between bits/chars and number of limbs
75 * Divide first in order to avoid potential overflows
76 */
77 #define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
78 #define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
79
80 void *mbedtls_mpi_mempool;
81
82 /* Implementation that should never be optimized out by the compiler */
mbedtls_mpi_zeroize(mbedtls_mpi_uint * v,size_t n)83 static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
84 {
85 mbedtls_platform_zeroize( v, ciL * n );
86 }
87
88 /*
89 * Initialize one MPI
90 */
mpi_init(mbedtls_mpi * X,short use_mempool)91 static void mpi_init( mbedtls_mpi *X, short use_mempool )
92 {
93 MPI_VALIDATE( X != NULL );
94
95 X->s = 1;
96 X->use_mempool = use_mempool;
97 X->n = 0;
98 X->p = NULL;
99 }
100
mbedtls_mpi_init(mbedtls_mpi * X)101 void mbedtls_mpi_init( mbedtls_mpi *X )
102 {
103 mpi_init( X, 0 /*use_mempool*/ );
104 }
105
mbedtls_mpi_init_mempool(mbedtls_mpi * X)106 void mbedtls_mpi_init_mempool( mbedtls_mpi *X )
107 {
108 mpi_init( X, !!mbedtls_mpi_mempool /*use_mempool*/ );
109 }
110
111 /*
112 * Unallocate one MPI
113 */
mbedtls_mpi_free(mbedtls_mpi * X)114 void mbedtls_mpi_free( mbedtls_mpi *X )
115 {
116 if( X == NULL )
117 return;
118
119 if( X->p != NULL )
120 {
121 mbedtls_mpi_zeroize( X->p, X->n );
122 if( X->use_mempool )
123 mempool_free( mbedtls_mpi_mempool, X->p );
124 else
125 mbedtls_free( X->p );
126 }
127
128 X->s = 1;
129 X->n = 0;
130 X->p = NULL;
131 }
132
133 /*
134 * Enlarge to the specified number of limbs
135 */
mbedtls_mpi_grow(mbedtls_mpi * X,size_t nblimbs)136 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs )
137 {
138 mbedtls_mpi_uint *p;
139 MPI_VALIDATE_RET( X != NULL );
140
141 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
142 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
143
144 if( X->n < nblimbs )
145 {
146 if( X->use_mempool )
147 {
148 p = mempool_alloc( mbedtls_mpi_mempool, nblimbs * ciL );
149 if( p == NULL )
150 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
151 memset( p, 0, nblimbs * ciL );
152 }
153 else
154 {
155 p = (mbedtls_mpi_uint*)mbedtls_calloc( nblimbs, ciL );
156 if( p == NULL )
157 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
158 }
159
160 if( X->p != NULL )
161 {
162 memcpy( p, X->p, X->n * ciL );
163 mbedtls_mpi_zeroize( X->p, X->n );
164 if( X->use_mempool )
165 mempool_free( mbedtls_mpi_mempool, X->p);
166 else
167 mbedtls_free( X->p );
168 }
169
170 X->n = nblimbs;
171 X->p = p;
172 }
173
174 return( 0 );
175 }
176
177 /*
178 * Resize down as much as possible,
179 * while keeping at least the specified number of limbs
180 */
mbedtls_mpi_shrink(mbedtls_mpi * X,size_t nblimbs)181 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs )
182 {
183 mbedtls_mpi_uint *p;
184 size_t i;
185 MPI_VALIDATE_RET( X != NULL );
186
187 if( nblimbs > MBEDTLS_MPI_MAX_LIMBS )
188 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
189
190 /* Actually resize up if there are currently fewer than nblimbs limbs. */
191 if( X->n <= nblimbs )
192 return( mbedtls_mpi_grow( X, nblimbs ) );
193 /* After this point, then X->n > nblimbs and in particular X->n > 0. */
194
195 for( i = X->n - 1; i > 0; i-- )
196 if( X->p[i] != 0 )
197 break;
198 i++;
199
200 if( i < nblimbs )
201 i = nblimbs;
202
203 if( X->use_mempool )
204 {
205 p = mempool_alloc( mbedtls_mpi_mempool, i * ciL );
206 if( p == NULL )
207 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
208 memset( p, 0, i * ciL );
209 }
210 else
211 {
212 p = (mbedtls_mpi_uint*)mbedtls_calloc( i, ciL );
213 if( p == NULL )
214 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
215 }
216
217 if( X->p != NULL )
218 {
219 memcpy( p, X->p, i * ciL );
220 mbedtls_mpi_zeroize( X->p, X->n );
221 if( X->use_mempool )
222 mempool_free( mbedtls_mpi_mempool, X->p );
223 else
224 mbedtls_free( X->p );
225 }
226
227 X->n = i;
228 X->p = p;
229
230 return( 0 );
231 }
232
233 /* Resize X to have exactly n limbs and set it to 0. */
mbedtls_mpi_resize_clear(mbedtls_mpi * X,size_t limbs)234 static int mbedtls_mpi_resize_clear( mbedtls_mpi *X, size_t limbs )
235 {
236 if( limbs == 0 )
237 {
238 mbedtls_mpi_free( X );
239 return( 0 );
240 }
241 else if( X->n == limbs )
242 {
243 memset( X->p, 0, limbs * ciL );
244 X->s = 1;
245 return( 0 );
246 }
247 else
248 {
249 mbedtls_mpi_free( X );
250 return( mbedtls_mpi_grow( X, limbs ) );
251 }
252 }
253
254 /*
255 * Copy the contents of Y into X.
256 *
257 * This function is not constant-time. Leading zeros in Y may be removed.
258 *
259 * Ensure that X does not shrink. This is not guaranteed by the public API,
260 * but some code in the bignum module relies on this property, for example
261 * in mbedtls_mpi_exp_mod().
262 */
mbedtls_mpi_copy(mbedtls_mpi * X,const mbedtls_mpi * Y)263 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y )
264 {
265 int ret = 0;
266 size_t i;
267 MPI_VALIDATE_RET( X != NULL );
268 MPI_VALIDATE_RET( Y != NULL );
269
270 if( X == Y )
271 return( 0 );
272
273 if( Y->n == 0 )
274 {
275 if( X->n != 0 )
276 {
277 X->s = 1;
278 memset( X->p, 0, X->n * ciL );
279 }
280 return( 0 );
281 }
282
283 for( i = Y->n - 1; i > 0; i-- )
284 if( Y->p[i] != 0 )
285 break;
286 i++;
287
288 X->s = Y->s;
289
290 if( X->n < i )
291 {
292 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i ) );
293 }
294 else
295 {
296 memset( X->p + i, 0, ( X->n - i ) * ciL );
297 }
298
299 memcpy( X->p, Y->p, i * ciL );
300
301 cleanup:
302
303 return( ret );
304 }
305
306 /*
307 * Swap the contents of X and Y
308 */
mbedtls_mpi_swap(mbedtls_mpi * X,mbedtls_mpi * Y)309 void mbedtls_mpi_swap( mbedtls_mpi *X, mbedtls_mpi *Y )
310 {
311 mbedtls_mpi T;
312 MPI_VALIDATE( X != NULL );
313 MPI_VALIDATE( Y != NULL );
314
315 memcpy( &T, X, sizeof( mbedtls_mpi ) );
316 memcpy( X, Y, sizeof( mbedtls_mpi ) );
317 memcpy( Y, &T, sizeof( mbedtls_mpi ) );
318 }
319
320 /*
321 * Set value from integer
322 */
mbedtls_mpi_lset(mbedtls_mpi * X,mbedtls_mpi_sint z)323 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z )
324 {
325 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
326 MPI_VALIDATE_RET( X != NULL );
327
328 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, 1 ) );
329 memset( X->p, 0, X->n * ciL );
330
331 X->p[0] = ( z < 0 ) ? -z : z;
332 X->s = ( z < 0 ) ? -1 : 1;
333
334 cleanup:
335
336 return( ret );
337 }
338
339 /*
340 * Get a specific bit
341 */
mbedtls_mpi_get_bit(const mbedtls_mpi * X,size_t pos)342 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos )
343 {
344 MPI_VALIDATE_RET( X != NULL );
345
346 if( X->n * biL <= pos )
347 return( 0 );
348
349 return( ( X->p[pos / biL] >> ( pos % biL ) ) & 0x01 );
350 }
351
352 /* Get a specific byte, without range checks. */
353 #define GET_BYTE( X, i ) \
354 ( ( ( X )->p[( i ) / ciL] >> ( ( ( i ) % ciL ) * 8 ) ) & 0xff )
355
356 /*
357 * Set a bit to a specific value of 0 or 1
358 */
mbedtls_mpi_set_bit(mbedtls_mpi * X,size_t pos,unsigned char val)359 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val )
360 {
361 int ret = 0;
362 size_t off = pos / biL;
363 size_t idx = pos % biL;
364 MPI_VALIDATE_RET( X != NULL );
365
366 if( val != 0 && val != 1 )
367 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
368
369 if( X->n * biL <= pos )
370 {
371 if( val == 0 )
372 return( 0 );
373
374 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, off + 1 ) );
375 }
376
377 X->p[off] &= ~( (mbedtls_mpi_uint) 0x01 << idx );
378 X->p[off] |= (mbedtls_mpi_uint) val << idx;
379
380 cleanup:
381
382 return( ret );
383 }
384
385 /*
386 * Return the number of less significant zero-bits
387 */
mbedtls_mpi_lsb(const mbedtls_mpi * X)388 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X )
389 {
390 size_t i, j, count = 0;
391 MBEDTLS_INTERNAL_VALIDATE_RET( X != NULL, 0 );
392
393 for( i = 0; i < X->n; i++ )
394 for( j = 0; j < biL; j++, count++ )
395 if( ( ( X->p[i] >> j ) & 1 ) != 0 )
396 return( count );
397
398 return( 0 );
399 }
400
401 /*
402 * Count leading zero bits in a given integer
403 */
mbedtls_clz(const mbedtls_mpi_uint x)404 static size_t mbedtls_clz( const mbedtls_mpi_uint x )
405 {
406 size_t j;
407 mbedtls_mpi_uint mask = (mbedtls_mpi_uint) 1 << (biL - 1);
408
409 for( j = 0; j < biL; j++ )
410 {
411 if( x & mask ) break;
412
413 mask >>= 1;
414 }
415
416 return j;
417 }
418
419 /*
420 * Return the number of bits
421 */
mbedtls_mpi_bitlen(const mbedtls_mpi * X)422 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X )
423 {
424 size_t i, j;
425
426 if( X->n == 0 )
427 return( 0 );
428
429 for( i = X->n - 1; i > 0; i-- )
430 if( X->p[i] != 0 )
431 break;
432
433 j = biL - mbedtls_clz( X->p[i] );
434
435 return( ( i * biL ) + j );
436 }
437
438 /*
439 * Return the total size in bytes
440 */
mbedtls_mpi_size(const mbedtls_mpi * X)441 size_t mbedtls_mpi_size( const mbedtls_mpi *X )
442 {
443 return( ( mbedtls_mpi_bitlen( X ) + 7 ) >> 3 );
444 }
445
446 /*
447 * Convert an ASCII character to digit value
448 */
mpi_get_digit(mbedtls_mpi_uint * d,int radix,char c)449 static int mpi_get_digit( mbedtls_mpi_uint *d, int radix, char c )
450 {
451 *d = 255;
452
453 if( c >= 0x30 && c <= 0x39 ) *d = c - 0x30;
454 if( c >= 0x41 && c <= 0x46 ) *d = c - 0x37;
455 if( c >= 0x61 && c <= 0x66 ) *d = c - 0x57;
456
457 if( *d >= (mbedtls_mpi_uint) radix )
458 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER );
459
460 return( 0 );
461 }
462
463 /*
464 * Import from an ASCII string
465 */
mbedtls_mpi_read_string(mbedtls_mpi * X,int radix,const char * s)466 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s )
467 {
468 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
469 size_t i, j, slen, n;
470 int sign = 1;
471 mbedtls_mpi_uint d;
472 mbedtls_mpi T;
473 MPI_VALIDATE_RET( X != NULL );
474 MPI_VALIDATE_RET( s != NULL );
475
476 if( radix < 2 || radix > 16 )
477 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
478
479 mbedtls_mpi_init_mempool( &T );
480
481 if( s[0] == 0 )
482 {
483 mbedtls_mpi_free( X );
484 return( 0 );
485 }
486
487 if( s[0] == '-' )
488 {
489 ++s;
490 sign = -1;
491 }
492
493 slen = strlen( s );
494
495 if( radix == 16 )
496 {
497 if( slen > MPI_SIZE_T_MAX >> 2 )
498 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
499
500 n = BITS_TO_LIMBS( slen << 2 );
501
502 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n ) );
503 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
504
505 for( i = slen, j = 0; i > 0; i--, j++ )
506 {
507 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i - 1] ) );
508 X->p[j / ( 2 * ciL )] |= d << ( ( j % ( 2 * ciL ) ) << 2 );
509 }
510 }
511 else
512 {
513 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
514
515 for( i = 0; i < slen; i++ )
516 {
517 MBEDTLS_MPI_CHK( mpi_get_digit( &d, radix, s[i] ) );
518 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T, X, radix ) );
519 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, &T, d ) );
520 }
521 }
522
523 if( sign < 0 && mbedtls_mpi_bitlen( X ) != 0 )
524 X->s = -1;
525
526 cleanup:
527
528 mbedtls_mpi_free( &T );
529
530 return( ret );
531 }
532
533 /*
534 * Helper to write the digits high-order first.
535 */
mpi_write_hlp(mbedtls_mpi * X,int radix,char ** p,const size_t buflen)536 static int mpi_write_hlp( mbedtls_mpi *X, int radix,
537 char **p, const size_t buflen )
538 {
539 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
540 mbedtls_mpi_uint r;
541 size_t length = 0;
542 char *p_end = *p + buflen;
543
544 do
545 {
546 if( length >= buflen )
547 {
548 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
549 }
550
551 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, radix ) );
552 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X, NULL, X, radix ) );
553 /*
554 * Write the residue in the current position, as an ASCII character.
555 */
556 if( r < 0xA )
557 *(--p_end) = (char)( '0' + r );
558 else
559 *(--p_end) = (char)( 'A' + ( r - 0xA ) );
560
561 length++;
562 } while( mbedtls_mpi_cmp_int( X, 0 ) != 0 );
563
564 memmove( *p, p_end, length );
565 *p += length;
566
567 cleanup:
568
569 return( ret );
570 }
571
572 /*
573 * Export into an ASCII string
574 */
mbedtls_mpi_write_string(const mbedtls_mpi * X,int radix,char * buf,size_t buflen,size_t * olen)575 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
576 char *buf, size_t buflen, size_t *olen )
577 {
578 int ret = 0;
579 size_t n;
580 char *p;
581 mbedtls_mpi T;
582 MPI_VALIDATE_RET( X != NULL );
583 MPI_VALIDATE_RET( olen != NULL );
584 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
585
586 if( radix < 2 || radix > 16 )
587 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
588
589 n = mbedtls_mpi_bitlen( X ); /* Number of bits necessary to present `n`. */
590 if( radix >= 4 ) n >>= 1; /* Number of 4-adic digits necessary to present
591 * `n`. If radix > 4, this might be a strict
592 * overapproximation of the number of
593 * radix-adic digits needed to present `n`. */
594 if( radix >= 16 ) n >>= 1; /* Number of hexadecimal digits necessary to
595 * present `n`. */
596
597 n += 1; /* Terminating null byte */
598 n += 1; /* Compensate for the divisions above, which round down `n`
599 * in case it's not even. */
600 n += 1; /* Potential '-'-sign. */
601 n += ( n & 1 ); /* Make n even to have enough space for hexadecimal writing,
602 * which always uses an even number of hex-digits. */
603
604 if( buflen < n )
605 {
606 *olen = n;
607 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
608 }
609
610 p = buf;
611 mbedtls_mpi_init_mempool( &T );
612
613 if( X->s == -1 )
614 {
615 *p++ = '-';
616 buflen--;
617 }
618
619 if( radix == 16 )
620 {
621 int c;
622 size_t i, j, k;
623
624 for( i = X->n, k = 0; i > 0; i-- )
625 {
626 for( j = ciL; j > 0; j-- )
627 {
628 c = ( X->p[i - 1] >> ( ( j - 1 ) << 3) ) & 0xFF;
629
630 if( c == 0 && k == 0 && ( i + j ) != 2 )
631 continue;
632
633 *(p++) = "0123456789ABCDEF" [c / 16];
634 *(p++) = "0123456789ABCDEF" [c % 16];
635 k = 1;
636 }
637 }
638 }
639 else
640 {
641 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T, X ) );
642
643 if( T.s == -1 )
644 T.s = 1;
645
646 MBEDTLS_MPI_CHK( mpi_write_hlp( &T, radix, &p, buflen ) );
647 }
648
649 *p++ = '\0';
650 *olen = p - buf;
651
652 cleanup:
653
654 mbedtls_mpi_free( &T );
655
656 return( ret );
657 }
658
659 #if defined(MBEDTLS_FS_IO)
660 /*
661 * Read X from an opened file
662 */
mbedtls_mpi_read_file(mbedtls_mpi * X,int radix,FILE * fin)663 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin )
664 {
665 mbedtls_mpi_uint d;
666 size_t slen;
667 char *p;
668 /*
669 * Buffer should have space for (short) label and decimal formatted MPI,
670 * newline characters and '\0'
671 */
672 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
673
674 MPI_VALIDATE_RET( X != NULL );
675 MPI_VALIDATE_RET( fin != NULL );
676
677 if( radix < 2 || radix > 16 )
678 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
679
680 memset( s, 0, sizeof( s ) );
681 if( fgets( s, sizeof( s ) - 1, fin ) == NULL )
682 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
683
684 slen = strlen( s );
685 if( slen == sizeof( s ) - 2 )
686 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
687
688 if( slen > 0 && s[slen - 1] == '\n' ) { slen--; s[slen] = '\0'; }
689 if( slen > 0 && s[slen - 1] == '\r' ) { slen--; s[slen] = '\0'; }
690
691 p = s + slen;
692 while( p-- > s )
693 if( mpi_get_digit( &d, radix, *p ) != 0 )
694 break;
695
696 return( mbedtls_mpi_read_string( X, radix, p + 1 ) );
697 }
698
699 /*
700 * Write X into an opened file (or stdout if fout == NULL)
701 */
mbedtls_mpi_write_file(const char * p,const mbedtls_mpi * X,int radix,FILE * fout)702 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout )
703 {
704 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
705 size_t n, slen, plen;
706 /*
707 * Buffer should have space for (short) label and decimal formatted MPI,
708 * newline characters and '\0'
709 */
710 char s[ MBEDTLS_MPI_RW_BUFFER_SIZE ];
711 MPI_VALIDATE_RET( X != NULL );
712
713 if( radix < 2 || radix > 16 )
714 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
715
716 memset( s, 0, sizeof( s ) );
717
718 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X, radix, s, sizeof( s ) - 2, &n ) );
719
720 if( p == NULL ) p = "";
721
722 plen = strlen( p );
723 slen = strlen( s );
724 s[slen++] = '\r';
725 s[slen++] = '\n';
726
727 if( fout != NULL )
728 {
729 if( fwrite( p, 1, plen, fout ) != plen ||
730 fwrite( s, 1, slen, fout ) != slen )
731 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR );
732 }
733 else
734 mbedtls_printf( "%s%s", p, s );
735
736 cleanup:
737
738 return( ret );
739 }
740 #endif /* MBEDTLS_FS_IO */
741
742
743 /* Convert a big-endian byte array aligned to the size of mbedtls_mpi_uint
744 * into the storage form used by mbedtls_mpi. */
745
mpi_uint_bigendian_to_host_c(mbedtls_mpi_uint x)746 static mbedtls_mpi_uint mpi_uint_bigendian_to_host_c( mbedtls_mpi_uint x )
747 {
748 uint8_t i;
749 unsigned char *x_ptr;
750 mbedtls_mpi_uint tmp = 0;
751
752 for( i = 0, x_ptr = (unsigned char*) &x; i < ciL; i++, x_ptr++ )
753 {
754 tmp <<= CHAR_BIT;
755 tmp |= (mbedtls_mpi_uint) *x_ptr;
756 }
757
758 return( tmp );
759 }
760
mpi_uint_bigendian_to_host(mbedtls_mpi_uint x)761 static mbedtls_mpi_uint mpi_uint_bigendian_to_host( mbedtls_mpi_uint x )
762 {
763 #if defined(__BYTE_ORDER__)
764
765 /* Nothing to do on bigendian systems. */
766 #if ( __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ )
767 return( x );
768 #endif /* __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__ */
769
770 #if ( __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ )
771
772 /* For GCC and Clang, have builtins for byte swapping. */
773 #if defined(__GNUC__) && defined(__GNUC_PREREQ)
774 #if __GNUC_PREREQ(4,3)
775 #define have_bswap
776 #endif
777 #endif
778
779 #if defined(__clang__) && defined(__has_builtin)
780 #if __has_builtin(__builtin_bswap32) && \
781 __has_builtin(__builtin_bswap64)
782 #define have_bswap
783 #endif
784 #endif
785
786 #if defined(have_bswap)
787 /* The compiler is hopefully able to statically evaluate this! */
788 switch( sizeof(mbedtls_mpi_uint) )
789 {
790 case 4:
791 return( __builtin_bswap32(x) );
792 case 8:
793 return( __builtin_bswap64(x) );
794 }
795 #endif
796 #endif /* __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__ */
797 #endif /* __BYTE_ORDER__ */
798
799 /* Fall back to C-based reordering if we don't know the byte order
800 * or we couldn't use a compiler-specific builtin. */
801 return( mpi_uint_bigendian_to_host_c( x ) );
802 }
803
mpi_bigendian_to_host(mbedtls_mpi_uint * const p,size_t limbs)804 static void mpi_bigendian_to_host( mbedtls_mpi_uint * const p, size_t limbs )
805 {
806 mbedtls_mpi_uint *cur_limb_left;
807 mbedtls_mpi_uint *cur_limb_right;
808 if( limbs == 0 )
809 return;
810
811 /*
812 * Traverse limbs and
813 * - adapt byte-order in each limb
814 * - swap the limbs themselves.
815 * For that, simultaneously traverse the limbs from left to right
816 * and from right to left, as long as the left index is not bigger
817 * than the right index (it's not a problem if limbs is odd and the
818 * indices coincide in the last iteration).
819 */
820 for( cur_limb_left = p, cur_limb_right = p + ( limbs - 1 );
821 cur_limb_left <= cur_limb_right;
822 cur_limb_left++, cur_limb_right-- )
823 {
824 mbedtls_mpi_uint tmp;
825 /* Note that if cur_limb_left == cur_limb_right,
826 * this code effectively swaps the bytes only once. */
827 tmp = mpi_uint_bigendian_to_host( *cur_limb_left );
828 *cur_limb_left = mpi_uint_bigendian_to_host( *cur_limb_right );
829 *cur_limb_right = tmp;
830 }
831 }
832
833 /*
834 * Import X from unsigned binary data, little endian
835 */
mbedtls_mpi_read_binary_le(mbedtls_mpi * X,const unsigned char * buf,size_t buflen)836 int mbedtls_mpi_read_binary_le( mbedtls_mpi *X,
837 const unsigned char *buf, size_t buflen )
838 {
839 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
840 size_t i;
841 size_t const limbs = CHARS_TO_LIMBS( buflen );
842
843 /* Ensure that target MPI has exactly the necessary number of limbs */
844 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
845
846 for( i = 0; i < buflen; i++ )
847 X->p[i / ciL] |= ((mbedtls_mpi_uint) buf[i]) << ((i % ciL) << 3);
848
849 cleanup:
850
851 /*
852 * This function is also used to import keys. However, wiping the buffers
853 * upon failure is not necessary because failure only can happen before any
854 * input is copied.
855 */
856 return( ret );
857 }
858
859 /*
860 * Import X from unsigned binary data, big endian
861 */
mbedtls_mpi_read_binary(mbedtls_mpi * X,const unsigned char * buf,size_t buflen)862 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen )
863 {
864 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
865 size_t const limbs = CHARS_TO_LIMBS( buflen );
866 size_t const overhead = ( limbs * ciL ) - buflen;
867 unsigned char *Xp;
868
869 MPI_VALIDATE_RET( X != NULL );
870 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
871
872 /* Ensure that target MPI has exactly the necessary number of limbs */
873 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
874
875 /* Avoid calling `memcpy` with NULL source or destination argument,
876 * even if buflen is 0. */
877 if( buflen != 0 )
878 {
879 Xp = (unsigned char*) X->p;
880 memcpy( Xp + overhead, buf, buflen );
881
882 mpi_bigendian_to_host( X->p, limbs );
883 }
884
885 cleanup:
886
887 /*
888 * This function is also used to import keys. However, wiping the buffers
889 * upon failure is not necessary because failure only can happen before any
890 * input is copied.
891 */
892 return( ret );
893 }
894
895 /*
896 * Export X into unsigned binary data, little endian
897 */
mbedtls_mpi_write_binary_le(const mbedtls_mpi * X,unsigned char * buf,size_t buflen)898 int mbedtls_mpi_write_binary_le( const mbedtls_mpi *X,
899 unsigned char *buf, size_t buflen )
900 {
901 size_t stored_bytes = X->n * ciL;
902 size_t bytes_to_copy;
903 size_t i;
904
905 if( stored_bytes < buflen )
906 {
907 bytes_to_copy = stored_bytes;
908 }
909 else
910 {
911 bytes_to_copy = buflen;
912
913 /* The output buffer is smaller than the allocated size of X.
914 * However X may fit if its leading bytes are zero. */
915 for( i = bytes_to_copy; i < stored_bytes; i++ )
916 {
917 if( GET_BYTE( X, i ) != 0 )
918 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
919 }
920 }
921
922 for( i = 0; i < bytes_to_copy; i++ )
923 buf[i] = GET_BYTE( X, i );
924
925 if( stored_bytes < buflen )
926 {
927 /* Write trailing 0 bytes */
928 memset( buf + stored_bytes, 0, buflen - stored_bytes );
929 }
930
931 return( 0 );
932 }
933
934 /*
935 * Export X into unsigned binary data, big endian
936 */
mbedtls_mpi_write_binary(const mbedtls_mpi * X,unsigned char * buf,size_t buflen)937 int mbedtls_mpi_write_binary( const mbedtls_mpi *X,
938 unsigned char *buf, size_t buflen )
939 {
940 size_t stored_bytes;
941 size_t bytes_to_copy;
942 unsigned char *p;
943 size_t i;
944
945 MPI_VALIDATE_RET( X != NULL );
946 MPI_VALIDATE_RET( buflen == 0 || buf != NULL );
947
948 stored_bytes = X->n * ciL;
949
950 if( stored_bytes < buflen )
951 {
952 /* There is enough space in the output buffer. Write initial
953 * null bytes and record the position at which to start
954 * writing the significant bytes. In this case, the execution
955 * trace of this function does not depend on the value of the
956 * number. */
957 bytes_to_copy = stored_bytes;
958 p = buf + buflen - stored_bytes;
959 memset( buf, 0, buflen - stored_bytes );
960 }
961 else
962 {
963 /* The output buffer is smaller than the allocated size of X.
964 * However X may fit if its leading bytes are zero. */
965 bytes_to_copy = buflen;
966 p = buf;
967 for( i = bytes_to_copy; i < stored_bytes; i++ )
968 {
969 if( GET_BYTE( X, i ) != 0 )
970 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL );
971 }
972 }
973
974 for( i = 0; i < bytes_to_copy; i++ )
975 p[bytes_to_copy - i - 1] = GET_BYTE( X, i );
976
977 return( 0 );
978 }
979
980 /*
981 * Left-shift: X <<= count
982 */
mbedtls_mpi_shift_l(mbedtls_mpi * X,size_t count)983 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count )
984 {
985 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
986 size_t i, v0, t1;
987 mbedtls_mpi_uint r0 = 0, r1;
988 MPI_VALIDATE_RET( X != NULL );
989
990 v0 = count / (biL );
991 t1 = count & (biL - 1);
992
993 i = mbedtls_mpi_bitlen( X ) + count;
994
995 if( X->n * biL < i )
996 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, BITS_TO_LIMBS( i ) ) );
997
998 ret = 0;
999
1000 /*
1001 * shift by count / limb_size
1002 */
1003 if( v0 > 0 )
1004 {
1005 for( i = X->n; i > v0; i-- )
1006 X->p[i - 1] = X->p[i - v0 - 1];
1007
1008 for( ; i > 0; i-- )
1009 X->p[i - 1] = 0;
1010 }
1011
1012 /*
1013 * shift by count % limb_size
1014 */
1015 if( t1 > 0 )
1016 {
1017 for( i = v0; i < X->n; i++ )
1018 {
1019 r1 = X->p[i] >> (biL - t1);
1020 X->p[i] <<= t1;
1021 X->p[i] |= r0;
1022 r0 = r1;
1023 }
1024 }
1025
1026 cleanup:
1027
1028 return( ret );
1029 }
1030
1031 /*
1032 * Right-shift: X >>= count
1033 */
mbedtls_mpi_shift_r(mbedtls_mpi * X,size_t count)1034 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count )
1035 {
1036 size_t i, v0, v1;
1037 mbedtls_mpi_uint r0 = 0, r1;
1038 MPI_VALIDATE_RET( X != NULL );
1039
1040 v0 = count / biL;
1041 v1 = count & (biL - 1);
1042
1043 if( v0 > X->n || ( v0 == X->n && v1 > 0 ) )
1044 return mbedtls_mpi_lset( X, 0 );
1045
1046 /*
1047 * shift by count / limb_size
1048 */
1049 if( v0 > 0 )
1050 {
1051 for( i = 0; i < X->n - v0; i++ )
1052 X->p[i] = X->p[i + v0];
1053
1054 for( ; i < X->n; i++ )
1055 X->p[i] = 0;
1056 }
1057
1058 /*
1059 * shift by count % limb_size
1060 */
1061 if( v1 > 0 )
1062 {
1063 for( i = X->n; i > 0; i-- )
1064 {
1065 r1 = X->p[i - 1] << (biL - v1);
1066 X->p[i - 1] >>= v1;
1067 X->p[i - 1] |= r0;
1068 r0 = r1;
1069 }
1070 }
1071
1072 return( 0 );
1073 }
1074
1075 /*
1076 * Compare unsigned values
1077 */
mbedtls_mpi_cmp_abs(const mbedtls_mpi * X,const mbedtls_mpi * Y)1078 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y )
1079 {
1080 size_t i, j;
1081 MPI_VALIDATE_RET( X != NULL );
1082 MPI_VALIDATE_RET( Y != NULL );
1083
1084 for( i = X->n; i > 0; i-- )
1085 if( X->p[i - 1] != 0 )
1086 break;
1087
1088 for( j = Y->n; j > 0; j-- )
1089 if( Y->p[j - 1] != 0 )
1090 break;
1091
1092 if( i == 0 && j == 0 )
1093 return( 0 );
1094
1095 if( i > j ) return( 1 );
1096 if( j > i ) return( -1 );
1097
1098 for( ; i > 0; i-- )
1099 {
1100 if( X->p[i - 1] > Y->p[i - 1] ) return( 1 );
1101 if( X->p[i - 1] < Y->p[i - 1] ) return( -1 );
1102 }
1103
1104 return( 0 );
1105 }
1106
1107 /*
1108 * Compare signed values
1109 */
mbedtls_mpi_cmp_mpi(const mbedtls_mpi * X,const mbedtls_mpi * Y)1110 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y )
1111 {
1112 size_t i, j;
1113 MPI_VALIDATE_RET( X != NULL );
1114 MPI_VALIDATE_RET( Y != NULL );
1115
1116 for( i = X->n; i > 0; i-- )
1117 if( X->p[i - 1] != 0 )
1118 break;
1119
1120 for( j = Y->n; j > 0; j-- )
1121 if( Y->p[j - 1] != 0 )
1122 break;
1123
1124 if( i == 0 && j == 0 )
1125 return( 0 );
1126
1127 if( i > j ) return( X->s );
1128 if( j > i ) return( -Y->s );
1129
1130 if( X->s > 0 && Y->s < 0 ) return( 1 );
1131 if( Y->s > 0 && X->s < 0 ) return( -1 );
1132
1133 for( ; i > 0; i-- )
1134 {
1135 if( X->p[i - 1] > Y->p[i - 1] ) return( X->s );
1136 if( X->p[i - 1] < Y->p[i - 1] ) return( -X->s );
1137 }
1138
1139 return( 0 );
1140 }
1141
1142 /*
1143 * Compare signed values
1144 */
mbedtls_mpi_cmp_int(const mbedtls_mpi * X,mbedtls_mpi_sint z)1145 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z )
1146 {
1147 mbedtls_mpi Y;
1148 mbedtls_mpi_uint p[1];
1149 MPI_VALIDATE_RET( X != NULL );
1150
1151 *p = ( z < 0 ) ? -z : z;
1152 Y.s = ( z < 0 ) ? -1 : 1;
1153 Y.n = 1;
1154 Y.p = p;
1155
1156 return( mbedtls_mpi_cmp_mpi( X, &Y ) );
1157 }
1158
1159 /*
1160 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1161 */
mbedtls_mpi_add_abs(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1162 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1163 {
1164 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1165 size_t i, j;
1166 mbedtls_mpi_uint *o, *p, c, tmp;
1167 MPI_VALIDATE_RET( X != NULL );
1168 MPI_VALIDATE_RET( A != NULL );
1169 MPI_VALIDATE_RET( B != NULL );
1170
1171 if( X == B )
1172 {
1173 const mbedtls_mpi *T = A; A = X; B = T;
1174 }
1175
1176 if( X != A )
1177 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
1178
1179 /*
1180 * X should always be positive as a result of unsigned additions.
1181 */
1182 X->s = 1;
1183
1184 for( j = B->n; j > 0; j-- )
1185 if( B->p[j - 1] != 0 )
1186 break;
1187
1188 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
1189
1190 o = B->p; p = X->p; c = 0;
1191
1192 /*
1193 * tmp is used because it might happen that p == o
1194 */
1195 for( i = 0; i < j; i++, o++, p++ )
1196 {
1197 tmp= *o;
1198 *p += c; c = ( *p < c );
1199 *p += tmp; c += ( *p < tmp );
1200 }
1201
1202 while( c != 0 )
1203 {
1204 if( i >= X->n )
1205 {
1206 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + 1 ) );
1207 p = X->p + i;
1208 }
1209
1210 *p += c; c = ( *p < c ); i++; p++;
1211 }
1212
1213 cleanup:
1214
1215 return( ret );
1216 }
1217
1218 /**
1219 * Helper for mbedtls_mpi subtraction.
1220 *
1221 * Calculate l - r where l and r have the same size.
1222 * This function operates modulo (2^ciL)^n and returns the carry
1223 * (1 if there was a wraparound, i.e. if `l < r`, and 0 otherwise).
1224 *
1225 * d may be aliased to l or r.
1226 *
1227 * \param n Number of limbs of \p d, \p l and \p r.
1228 * \param[out] d The result of the subtraction.
1229 * \param[in] l The left operand.
1230 * \param[in] r The right operand.
1231 *
1232 * \return 1 if `l < r`.
1233 * 0 if `l >= r`.
1234 */
mpi_sub_hlp(size_t n,mbedtls_mpi_uint * d,const mbedtls_mpi_uint * l,const mbedtls_mpi_uint * r)1235 static mbedtls_mpi_uint mpi_sub_hlp( size_t n,
1236 mbedtls_mpi_uint *d,
1237 const mbedtls_mpi_uint *l,
1238 const mbedtls_mpi_uint *r )
1239 {
1240 size_t i;
1241 mbedtls_mpi_uint c = 0, t, z;
1242
1243 for( i = 0; i < n; i++ )
1244 {
1245 z = ( l[i] < c ); t = l[i] - c;
1246 c = ( t < r[i] ) + z; d[i] = t - r[i];
1247 }
1248
1249 return( c );
1250 }
1251
1252 /*
1253 * Unsigned subtraction: X = |A| - |B| (HAC 14.9, 14.10)
1254 */
mbedtls_mpi_sub_abs(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1255 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1256 {
1257 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1258 size_t n;
1259 mbedtls_mpi_uint carry;
1260 MPI_VALIDATE_RET( X != NULL );
1261 MPI_VALIDATE_RET( A != NULL );
1262 MPI_VALIDATE_RET( B != NULL );
1263
1264 for( n = B->n; n > 0; n-- )
1265 if( B->p[n - 1] != 0 )
1266 break;
1267 if( n > A->n )
1268 {
1269 /* B >= (2^ciL)^n > A */
1270 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1271 goto cleanup;
1272 }
1273
1274 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, A->n ) );
1275
1276 /* Set the high limbs of X to match A. Don't touch the lower limbs
1277 * because X might be aliased to B, and we must not overwrite the
1278 * significant digits of B. */
1279 if( A->n > n )
1280 memcpy( X->p + n, A->p + n, ( A->n - n ) * ciL );
1281 if( X->n > A->n )
1282 memset( X->p + A->n, 0, ( X->n - A->n ) * ciL );
1283
1284 carry = mpi_sub_hlp( n, X->p, A->p, B->p );
1285 if( carry != 0 )
1286 {
1287 /* Propagate the carry to the first nonzero limb of X. */
1288 for( ; n < X->n && X->p[n] == 0; n++ )
1289 --X->p[n];
1290 /* If we ran out of space for the carry, it means that the result
1291 * is negative. */
1292 if( n == X->n )
1293 {
1294 ret = MBEDTLS_ERR_MPI_NEGATIVE_VALUE;
1295 goto cleanup;
1296 }
1297 --X->p[n];
1298 }
1299
1300 /* X should always be positive as a result of unsigned subtractions. */
1301 X->s = 1;
1302
1303 cleanup:
1304 return( ret );
1305 }
1306
1307 /*
1308 * Signed addition: X = A + B
1309 */
mbedtls_mpi_add_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1310 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1311 {
1312 int ret, s;
1313 MPI_VALIDATE_RET( X != NULL );
1314 MPI_VALIDATE_RET( A != NULL );
1315 MPI_VALIDATE_RET( B != NULL );
1316
1317 s = A->s;
1318 if( A->s * B->s < 0 )
1319 {
1320 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1321 {
1322 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1323 X->s = s;
1324 }
1325 else
1326 {
1327 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1328 X->s = -s;
1329 }
1330 }
1331 else
1332 {
1333 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1334 X->s = s;
1335 }
1336
1337 cleanup:
1338
1339 return( ret );
1340 }
1341
1342 /*
1343 * Signed subtraction: X = A - B
1344 */
mbedtls_mpi_sub_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1345 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1346 {
1347 int ret, s;
1348 MPI_VALIDATE_RET( X != NULL );
1349 MPI_VALIDATE_RET( A != NULL );
1350 MPI_VALIDATE_RET( B != NULL );
1351
1352 s = A->s;
1353 if( A->s * B->s > 0 )
1354 {
1355 if( mbedtls_mpi_cmp_abs( A, B ) >= 0 )
1356 {
1357 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, A, B ) );
1358 X->s = s;
1359 }
1360 else
1361 {
1362 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X, B, A ) );
1363 X->s = -s;
1364 }
1365 }
1366 else
1367 {
1368 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X, A, B ) );
1369 X->s = s;
1370 }
1371
1372 cleanup:
1373
1374 return( ret );
1375 }
1376
1377 /*
1378 * Signed addition: X = A + b
1379 */
mbedtls_mpi_add_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_sint b)1380 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1381 {
1382 mbedtls_mpi B;
1383 mbedtls_mpi_uint p[1];
1384 MPI_VALIDATE_RET( X != NULL );
1385 MPI_VALIDATE_RET( A != NULL );
1386
1387 p[0] = ( b < 0 ) ? -b : b;
1388 B.s = ( b < 0 ) ? -1 : 1;
1389 B.n = 1;
1390 B.p = p;
1391
1392 return( mbedtls_mpi_add_mpi( X, A, &B ) );
1393 }
1394
1395 /*
1396 * Signed subtraction: X = A - b
1397 */
mbedtls_mpi_sub_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_sint b)1398 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1399 {
1400 mbedtls_mpi B;
1401 mbedtls_mpi_uint p[1];
1402 MPI_VALIDATE_RET( X != NULL );
1403 MPI_VALIDATE_RET( A != NULL );
1404
1405 p[0] = ( b < 0 ) ? -b : b;
1406 B.s = ( b < 0 ) ? -1 : 1;
1407 B.n = 1;
1408 B.p = p;
1409
1410 return( mbedtls_mpi_sub_mpi( X, A, &B ) );
1411 }
1412
1413 /** Helper for mbedtls_mpi multiplication.
1414 *
1415 * Add \p b * \p s to \p d.
1416 *
1417 * \param i The number of limbs of \p s.
1418 * \param[in] s A bignum to multiply, of size \p i.
1419 * It may overlap with \p d, but only if
1420 * \p d <= \p s.
1421 * Its leading limb must not be \c 0.
1422 * \param[in,out] d The bignum to add to.
1423 * It must be sufficiently large to store the
1424 * result of the multiplication. This means
1425 * \p i + 1 limbs if \p d[\p i - 1] started as 0 and \p b
1426 * is not known a priori.
1427 * \param b A scalar to multiply.
1428 */
1429 static
1430 #if defined(__APPLE__) && defined(__arm__)
1431 /*
1432 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1433 * appears to need this to prevent bad ARM code generation at -O3.
1434 */
1435 __attribute__ ((noinline))
1436 #endif
mpi_mul_hlp(size_t i,const mbedtls_mpi_uint * s,mbedtls_mpi_uint * d,mbedtls_mpi_uint b)1437 void mpi_mul_hlp( size_t i,
1438 const mbedtls_mpi_uint *s,
1439 mbedtls_mpi_uint *d,
1440 mbedtls_mpi_uint b )
1441 {
1442 mbedtls_mpi_uint c = 0, t = 0;
1443
1444 #if defined(MULADDC_HUIT)
1445 for( ; i >= 8; i -= 8 )
1446 {
1447 MULADDC_INIT
1448 MULADDC_HUIT
1449 MULADDC_STOP
1450 }
1451
1452 for( ; i > 0; i-- )
1453 {
1454 MULADDC_INIT
1455 MULADDC_CORE
1456 MULADDC_STOP
1457 }
1458 #else /* MULADDC_HUIT */
1459 for( ; i >= 16; i -= 16 )
1460 {
1461 MULADDC_INIT
1462 MULADDC_CORE MULADDC_CORE
1463 MULADDC_CORE MULADDC_CORE
1464 MULADDC_CORE MULADDC_CORE
1465 MULADDC_CORE MULADDC_CORE
1466
1467 MULADDC_CORE MULADDC_CORE
1468 MULADDC_CORE MULADDC_CORE
1469 MULADDC_CORE MULADDC_CORE
1470 MULADDC_CORE MULADDC_CORE
1471 MULADDC_STOP
1472 }
1473
1474 for( ; i >= 8; i -= 8 )
1475 {
1476 MULADDC_INIT
1477 MULADDC_CORE MULADDC_CORE
1478 MULADDC_CORE MULADDC_CORE
1479
1480 MULADDC_CORE MULADDC_CORE
1481 MULADDC_CORE MULADDC_CORE
1482 MULADDC_STOP
1483 }
1484
1485 for( ; i > 0; i-- )
1486 {
1487 MULADDC_INIT
1488 MULADDC_CORE
1489 MULADDC_STOP
1490 }
1491 #endif /* MULADDC_HUIT */
1492
1493 t++;
1494
1495 while( c != 0 )
1496 {
1497 *d += c; c = ( *d < c ); d++;
1498 }
1499 }
1500
1501 /*
1502 * Baseline multiplication: X = A * B (HAC 14.12)
1503 */
mbedtls_mpi_mul_mpi(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * B)1504 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1505 {
1506 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1507 size_t i, j;
1508 mbedtls_mpi TA, TB;
1509 int result_is_zero = 0;
1510 MPI_VALIDATE_RET( X != NULL );
1511 MPI_VALIDATE_RET( A != NULL );
1512 MPI_VALIDATE_RET( B != NULL );
1513
1514 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB );
1515
1516 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1517 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
1518
1519 for( i = A->n; i > 0; i-- )
1520 if( A->p[i - 1] != 0 )
1521 break;
1522 if( i == 0 )
1523 result_is_zero = 1;
1524
1525 for( j = B->n; j > 0; j-- )
1526 if( B->p[j - 1] != 0 )
1527 break;
1528 if( j == 0 )
1529 result_is_zero = 1;
1530
1531 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1532 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
1533
1534 for( ; j > 0; j-- )
1535 mpi_mul_hlp( i, A->p, X->p + j - 1, B->p[j - 1] );
1536
1537 /* If the result is 0, we don't shortcut the operation, which reduces
1538 * but does not eliminate side channels leaking the zero-ness. We do
1539 * need to take care to set the sign bit properly since the library does
1540 * not fully support an MPI object with a value of 0 and s == -1. */
1541 if( result_is_zero )
1542 X->s = 1;
1543 else
1544 X->s = A->s * B->s;
1545
1546 cleanup:
1547
1548 mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TA );
1549
1550 return( ret );
1551 }
1552
1553 /*
1554 * Baseline multiplication: X = A * b
1555 */
mbedtls_mpi_mul_int(mbedtls_mpi * X,const mbedtls_mpi * A,mbedtls_mpi_uint b)1556 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
1557 {
1558 MPI_VALIDATE_RET( X != NULL );
1559 MPI_VALIDATE_RET( A != NULL );
1560
1561 /* mpi_mul_hlp can't deal with a leading 0. */
1562 size_t n = A->n;
1563 while( n > 0 && A->p[n - 1] == 0 )
1564 --n;
1565
1566 /* The general method below doesn't work if n==0 or b==0. By chance
1567 * calculating the result is trivial in those cases. */
1568 if( b == 0 || n == 0 )
1569 {
1570 return( mbedtls_mpi_lset( X, 0 ) );
1571 }
1572
1573 /* Calculate A*b as A + A*(b-1) to take advantage of mpi_mul_hlp */
1574 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1575 /* In general, A * b requires 1 limb more than b. If
1576 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1577 * number of limbs as A and the call to grow() is not required since
1578 * copy() will take care of the growth if needed. However, experimentally,
1579 * making the call to grow() unconditional causes slightly fewer
1580 * calls to calloc() in ECP code, presumably because it reuses the
1581 * same mpi for a while and this way the mpi is more likely to directly
1582 * grow to its final size. */
1583 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n + 1 ) );
1584 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
1585 mpi_mul_hlp( n, A->p, X->p, b - 1 );
1586
1587 cleanup:
1588 return( ret );
1589 }
1590
1591 /*
1592 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1593 * mbedtls_mpi_uint divisor, d
1594 */
mbedtls_int_div_int(mbedtls_mpi_uint u1,mbedtls_mpi_uint u0,mbedtls_mpi_uint d,mbedtls_mpi_uint * r)1595 static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1596 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
1597 {
1598 #if defined(MBEDTLS_HAVE_UDBL)
1599 mbedtls_t_udbl dividend, quotient;
1600 #else
1601 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1602 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
1603 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1604 mbedtls_mpi_uint u0_msw, u0_lsw;
1605 size_t s;
1606 #endif
1607
1608 /*
1609 * Check for overflow
1610 */
1611 if( 0 == d || u1 >= d )
1612 {
1613 if (r != NULL) *r = ~0;
1614
1615 return ( ~0 );
1616 }
1617
1618 #if defined(MBEDTLS_HAVE_UDBL)
1619 dividend = (mbedtls_t_udbl) u1 << biL;
1620 dividend |= (mbedtls_t_udbl) u0;
1621 quotient = dividend / d;
1622 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1623 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1624
1625 if( r != NULL )
1626 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
1627
1628 return (mbedtls_mpi_uint) quotient;
1629 #else
1630
1631 /*
1632 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1633 * Vol. 2 - Seminumerical Algorithms, Knuth
1634 */
1635
1636 /*
1637 * Normalize the divisor, d, and dividend, u0, u1
1638 */
1639 s = mbedtls_clz( d );
1640 d = d << s;
1641
1642 u1 = u1 << s;
1643 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
1644 u0 = u0 << s;
1645
1646 d1 = d >> biH;
1647 d0 = d & uint_halfword_mask;
1648
1649 u0_msw = u0 >> biH;
1650 u0_lsw = u0 & uint_halfword_mask;
1651
1652 /*
1653 * Find the first quotient and remainder
1654 */
1655 q1 = u1 / d1;
1656 r0 = u1 - d1 * q1;
1657
1658 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1659 {
1660 q1 -= 1;
1661 r0 += d1;
1662
1663 if ( r0 >= radix ) break;
1664 }
1665
1666 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
1667 q0 = rAX / d1;
1668 r0 = rAX - q0 * d1;
1669
1670 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1671 {
1672 q0 -= 1;
1673 r0 += d1;
1674
1675 if ( r0 >= radix ) break;
1676 }
1677
1678 if (r != NULL)
1679 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
1680
1681 quotient = q1 * radix + q0;
1682
1683 return quotient;
1684 #endif
1685 }
1686
1687 /*
1688 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1689 */
mbedtls_mpi_div_mpi(mbedtls_mpi * Q,mbedtls_mpi * R,const mbedtls_mpi * A,const mbedtls_mpi * B)1690 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1691 const mbedtls_mpi *B )
1692 {
1693 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1694 size_t i, n, t, k;
1695 mbedtls_mpi X, Y, Z, T1, T2;
1696 mbedtls_mpi_uint TP2[3];
1697 MPI_VALIDATE_RET( A != NULL );
1698 MPI_VALIDATE_RET( B != NULL );
1699
1700 if( mbedtls_mpi_cmp_int( B, 0 ) == 0 )
1701 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1702
1703 mbedtls_mpi_init_mempool( &X ); mbedtls_mpi_init_mempool( &Y );
1704 mbedtls_mpi_init_mempool( &Z ); mbedtls_mpi_init_mempool( &T1 );
1705 /*
1706 * Avoid dynamic memory allocations for constant-size T2.
1707 *
1708 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1709 * so nobody increase the size of the MPI and we're safe to use an on-stack
1710 * buffer.
1711 */
1712 T2.s = 1;
1713 T2.n = sizeof( TP2 ) / sizeof( *TP2 );
1714 T2.p = TP2;
1715
1716 if( mbedtls_mpi_cmp_abs( A, B ) < 0 )
1717 {
1718 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1719 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
1720 return( 0 );
1721 }
1722
1723 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1724 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
1725 X.s = Y.s = 1;
1726
1727 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1728 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1729 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, A->n + 2 ) );
1730
1731 k = mbedtls_mpi_bitlen( &Y ) % biL;
1732 if( k < biL - 1 )
1733 {
1734 k = biL - 1 - k;
1735 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1736 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
1737 }
1738 else k = 0;
1739
1740 n = X.n - 1;
1741 t = Y.n - 1;
1742 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
1743
1744 while( mbedtls_mpi_cmp_mpi( &X, &Y ) >= 0 )
1745 {
1746 Z.p[n - t]++;
1747 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
1748 }
1749 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
1750
1751 for( i = n; i > t ; i-- )
1752 {
1753 if( X.p[i] >= Y.p[t] )
1754 Z.p[i - t - 1] = ~0;
1755 else
1756 {
1757 Z.p[i - t - 1] = mbedtls_int_div_int( X.p[i], X.p[i - 1],
1758 Y.p[t], NULL);
1759 }
1760
1761 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1762 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1763 T2.p[2] = X.p[i];
1764
1765 Z.p[i - t - 1]++;
1766 do
1767 {
1768 Z.p[i - t - 1]--;
1769
1770 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
1771 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
1772 T1.p[1] = Y.p[t];
1773 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1774 }
1775 while( mbedtls_mpi_cmp_mpi( &T1, &T2 ) > 0 );
1776
1777 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1778 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1779 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
1780
1781 if( mbedtls_mpi_cmp_int( &X, 0 ) < 0 )
1782 {
1783 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1784 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1785 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
1786 Z.p[i - t - 1]--;
1787 }
1788 }
1789
1790 if( Q != NULL )
1791 {
1792 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
1793 Q->s = A->s * B->s;
1794 }
1795
1796 if( R != NULL )
1797 {
1798 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
1799 X.s = A->s;
1800 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
1801
1802 if( mbedtls_mpi_cmp_int( R, 0 ) == 0 )
1803 R->s = 1;
1804 }
1805
1806 cleanup:
1807
1808 mbedtls_mpi_free( &X ); mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &Z );
1809 mbedtls_mpi_free( &T1 );
1810 mbedtls_platform_zeroize( TP2, sizeof( TP2 ) );
1811
1812 return( ret );
1813 }
1814
1815 /*
1816 * Division by int: A = Q * b + R
1817 */
mbedtls_mpi_div_int(mbedtls_mpi * Q,mbedtls_mpi * R,const mbedtls_mpi * A,mbedtls_mpi_sint b)1818 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1819 const mbedtls_mpi *A,
1820 mbedtls_mpi_sint b )
1821 {
1822 mbedtls_mpi B;
1823 mbedtls_mpi_uint p[1];
1824 MPI_VALIDATE_RET( A != NULL );
1825
1826 p[0] = ( b < 0 ) ? -b : b;
1827 B.s = ( b < 0 ) ? -1 : 1;
1828 B.n = 1;
1829 B.p = p;
1830
1831 return( mbedtls_mpi_div_mpi( Q, R, A, &B ) );
1832 }
1833
1834 /*
1835 * Modulo: R = A mod B
1836 */
mbedtls_mpi_mod_mpi(mbedtls_mpi * R,const mbedtls_mpi * A,const mbedtls_mpi * B)1837 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1838 {
1839 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1840 MPI_VALIDATE_RET( R != NULL );
1841 MPI_VALIDATE_RET( A != NULL );
1842 MPI_VALIDATE_RET( B != NULL );
1843
1844 if( mbedtls_mpi_cmp_int( B, 0 ) < 0 )
1845 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1846
1847 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
1848
1849 while( mbedtls_mpi_cmp_int( R, 0 ) < 0 )
1850 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
1851
1852 while( mbedtls_mpi_cmp_mpi( R, B ) >= 0 )
1853 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
1854
1855 cleanup:
1856
1857 return( ret );
1858 }
1859
1860 /*
1861 * Modulo: r = A mod b
1862 */
mbedtls_mpi_mod_int(mbedtls_mpi_uint * r,const mbedtls_mpi * A,mbedtls_mpi_sint b)1863 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1864 {
1865 size_t i;
1866 mbedtls_mpi_uint x, y, z;
1867 MPI_VALIDATE_RET( r != NULL );
1868 MPI_VALIDATE_RET( A != NULL );
1869
1870 if( b == 0 )
1871 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1872
1873 if( b < 0 )
1874 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1875
1876 /*
1877 * handle trivial cases
1878 */
1879 if( b == 1 || A->n == 0 )
1880 {
1881 *r = 0;
1882 return( 0 );
1883 }
1884
1885 if( b == 2 )
1886 {
1887 *r = A->p[0] & 1;
1888 return( 0 );
1889 }
1890
1891 /*
1892 * general case
1893 */
1894 for( i = A->n, y = 0; i > 0; i-- )
1895 {
1896 x = A->p[i - 1];
1897 y = ( y << biH ) | ( x >> biH );
1898 z = y / b;
1899 y -= z * b;
1900
1901 x <<= biH;
1902 y = ( y << biH ) | ( x >> biH );
1903 z = y / b;
1904 y -= z * b;
1905 }
1906
1907 /*
1908 * If A is negative, then the current y represents a negative value.
1909 * Flipping it to the positive side.
1910 */
1911 if( A->s < 0 && y != 0 )
1912 y = b - y;
1913
1914 *r = y;
1915
1916 return( 0 );
1917 }
1918
1919 /*
1920 * Fast Montgomery initialization (thanks to Tom St Denis)
1921 */
mpi_montg_init(mbedtls_mpi_uint * mm,const mbedtls_mpi * N)1922 static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
1923 {
1924 mbedtls_mpi_uint x, m0 = N->p[0];
1925 unsigned int i;
1926
1927 x = m0;
1928 x += ( ( m0 + 2 ) & 4 ) << 1;
1929
1930 for( i = biL; i >= 8; i /= 2 )
1931 x *= ( 2 - ( m0 * x ) );
1932
1933 *mm = ~x + 1;
1934 }
1935
mbedtls_mpi_montg_init(mbedtls_mpi_uint * mm,const mbedtls_mpi * N)1936 void mbedtls_mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
1937 {
1938 mpi_montg_init( mm, N );
1939 }
1940
1941 /** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1942 *
1943 * \param[in,out] A One of the numbers to multiply.
1944 * It must have at least as many limbs as N
1945 * (A->n >= N->n), and any limbs beyond n are ignored.
1946 * On successful completion, A contains the result of
1947 * the multiplication A * B * R^-1 mod N where
1948 * R = (2^ciL)^n.
1949 * \param[in] B One of the numbers to multiply.
1950 * It must be nonzero and must not have more limbs than N
1951 * (B->n <= N->n).
1952 * \param[in] N The modulo. N must be odd.
1953 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1954 * This is -N^-1 mod 2^ciL.
1955 * \param[in,out] T A bignum for temporary storage.
1956 * It must be at least twice the limb size of N plus 2
1957 * (T->n >= 2 * (N->n + 1)).
1958 * Its initial content is unused and
1959 * its final content is indeterminate.
1960 * Note that unlike the usual convention in the library
1961 * for `const mbedtls_mpi*`, the content of T can change.
1962 */
mpi_montmul(mbedtls_mpi * A,const mbedtls_mpi * B,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)1963 static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1964 const mbedtls_mpi *T )
1965 {
1966 size_t i, n, m;
1967 mbedtls_mpi_uint u0, u1, *d;
1968
1969 memset( T->p, 0, T->n * ciL );
1970
1971 d = T->p;
1972 n = N->n;
1973 m = ( B->n < n ) ? B->n : n;
1974
1975 for( i = 0; i < n; i++ )
1976 {
1977 /*
1978 * T = (T + u0*B + u1*N) / 2^biL
1979 */
1980 u0 = A->p[i];
1981 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1982
1983 mpi_mul_hlp( m, B->p, d, u0 );
1984 mpi_mul_hlp( n, N->p, d, u1 );
1985
1986 *d++ = u0; d[n + 1] = 0;
1987 }
1988
1989 /* At this point, d is either the desired result or the desired result
1990 * plus N. We now potentially subtract N, avoiding leaking whether the
1991 * subtraction is performed through side channels. */
1992
1993 /* Copy the n least significant limbs of d to A, so that
1994 * A = d if d < N (recall that N has n limbs). */
1995 memcpy( A->p, d, n * ciL );
1996 /* If d >= N then we want to set A to d - N. To prevent timing attacks,
1997 * do the calculation without using conditional tests. */
1998 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
1999 d[n] += 1;
2000 d[n] -= mpi_sub_hlp( n, d, d, N->p );
2001 /* If d0 < N then d < (2^biL)^n
2002 * so d[n] == 0 and we want to keep A as it is.
2003 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
2004 * so d[n] == 1 and we want to set A to the result of the subtraction
2005 * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
2006 * This exactly corresponds to a conditional assignment. */
2007 mbedtls_ct_mpi_uint_cond_assign( n, A->p, d, (unsigned char) d[n] );
2008 }
2009
mbedtls_mpi_montmul(mbedtls_mpi * A,const mbedtls_mpi * B,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)2010 void mbedtls_mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
2011 const mbedtls_mpi *T )
2012 {
2013 mpi_montmul( A, B, N, mm, T);
2014 }
2015
2016 /*
2017 * Montgomery reduction: A = A * R^-1 mod N
2018 *
2019 * See mpi_montmul() regarding constraints and guarantees on the parameters.
2020 */
mpi_montred(mbedtls_mpi * A,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)2021 static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
2022 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
2023 {
2024 mbedtls_mpi_uint z = 1;
2025 mbedtls_mpi U;
2026
2027 U.n = U.s = (int) z;
2028 U.p = &z;
2029
2030 mpi_montmul( A, &U, N, mm, T );
2031 }
2032
mbedtls_mpi_montred(mbedtls_mpi * A,const mbedtls_mpi * N,mbedtls_mpi_uint mm,const mbedtls_mpi * T)2033 void mbedtls_mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
2034 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
2035 {
2036 mpi_montred( A, N, mm, T );
2037 }
2038
2039 /**
2040 * Select an MPI from a table without leaking the index.
2041 *
2042 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
2043 * reads the entire table in order to avoid leaking the value of idx to an
2044 * attacker able to observe memory access patterns.
2045 *
2046 * \param[out] R Where to write the selected MPI.
2047 * \param[in] T The table to read from.
2048 * \param[in] T_size The number of elements in the table.
2049 * \param[in] idx The index of the element to select;
2050 * this must satisfy 0 <= idx < T_size.
2051 *
2052 * \return \c 0 on success, or a negative error code.
2053 */
mpi_select(mbedtls_mpi * R,const mbedtls_mpi * T,size_t T_size,size_t idx)2054 static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx )
2055 {
2056 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2057
2058 for( size_t i = 0; i < T_size; i++ )
2059 {
2060 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i],
2061 (unsigned char) mbedtls_ct_size_bool_eq( i, idx ) ) );
2062 }
2063
2064 cleanup:
2065 return( ret );
2066 }
2067
2068 /*
2069 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
2070 */
mbedtls_mpi_exp_mod(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * E,const mbedtls_mpi * N,mbedtls_mpi * prec_RR)2071 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
2072 const mbedtls_mpi *E, const mbedtls_mpi *N,
2073 mbedtls_mpi *prec_RR )
2074 {
2075 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2076 size_t wbits, wsize, one = 1;
2077 size_t i, j, nblimbs;
2078 size_t bufsize, nbits;
2079 mbedtls_mpi_uint ei, mm, state;
2080 mbedtls_mpi RR, T, WW, Apos;
2081 mbedtls_mpi *W = NULL;
2082 const size_t array_size_W = 2 << MBEDTLS_MPI_WINDOW_SIZE;
2083 int neg;
2084
2085 MPI_VALIDATE_RET( X != NULL );
2086 MPI_VALIDATE_RET( A != NULL );
2087 MPI_VALIDATE_RET( E != NULL );
2088 MPI_VALIDATE_RET( N != NULL );
2089
2090 if( mbedtls_mpi_cmp_int( N, 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
2091 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2092
2093 if( mbedtls_mpi_cmp_int( E, 0 ) < 0 )
2094 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2095
2096 if( mbedtls_mpi_bitlen( E ) > MBEDTLS_MPI_MAX_BITS ||
2097 mbedtls_mpi_bitlen( N ) > MBEDTLS_MPI_MAX_BITS )
2098 return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2099
2100 /*
2101 * Init temps and window size
2102 */
2103 mpi_montg_init( &mm, N );
2104 mbedtls_mpi_init_mempool( &RR ); mbedtls_mpi_init( &T );
2105 mbedtls_mpi_init_mempool( &Apos );
2106 mbedtls_mpi_init_mempool( &WW );
2107
2108 i = mbedtls_mpi_bitlen( E );
2109
2110 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2111 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2112
2113 #if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
2114 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2115 wsize = MBEDTLS_MPI_WINDOW_SIZE;
2116 #endif
2117
2118 j = N->n + 1;
2119 /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
2120 * and mpi_montred() calls later. Here we ensure that W[1] and X are
2121 * large enough, and later we'll grow other W[i] to the same length.
2122 * They must not be shrunk midway through this function!
2123 */
2124 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2125
2126 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
2127
2128 /*
2129 * Compensate for negative A (and correct at the end)
2130 */
2131 neg = ( A->s == -1 );
2132 if( neg )
2133 {
2134 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
2135 Apos.s = 1;
2136 A = &Apos;
2137 }
2138
2139 /*
2140 * If 1st call, pre-compute R^2 mod N
2141 */
2142 if( prec_RR == NULL || prec_RR->p == NULL )
2143 {
2144 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2145 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2146 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
2147
2148 if( prec_RR != NULL )
2149 memcpy( prec_RR, &RR, sizeof( mbedtls_mpi ) );
2150 }
2151 else
2152 memcpy( &RR, prec_RR, sizeof( mbedtls_mpi ) );
2153
2154 W = mempool_alloc( mbedtls_mpi_mempool,
2155 sizeof( mbedtls_mpi ) * array_size_W );
2156 if( W == NULL ) {
2157 ret = MBEDTLS_ERR_MPI_ALLOC_FAILED;
2158 goto cleanup;
2159 }
2160 for( i = 0; i < array_size_W; i++ )
2161 mbedtls_mpi_init_mempool( W + i );
2162 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2163
2164 /*
2165 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2166 */
2167 if( mbedtls_mpi_cmp_mpi( A, N ) >= 0 )
2168 {
2169 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
2170 /* This should be a no-op because W[1] is already that large before
2171 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
2172 * in mpi_montmul() below, so let's make sure. */
2173 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n + 1 ) );
2174 }
2175 else
2176 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
2177
2178 /* Note that this is safe because W[1] always has at least N->n limbs
2179 * (it grew above and was preserved by mbedtls_mpi_copy()). */
2180 mpi_montmul( &W[1], &RR, N, mm, &T );
2181
2182 /*
2183 * X = R^2 * R^-1 mod N = R mod N
2184 */
2185 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
2186 mpi_montred( X, N, mm, &T );
2187
2188 if( wsize > 1 )
2189 {
2190 /*
2191 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2192 */
2193 j = one << ( wsize - 1 );
2194
2195 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2196 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
2197
2198 for( i = 0; i < wsize - 1; i++ )
2199 mpi_montmul( &W[j], &W[j], N, mm, &T );
2200
2201 /*
2202 * W[i] = W[i - 1] * W[1]
2203 */
2204 for( i = j + 1; i < ( one << wsize ); i++ )
2205 {
2206 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2207 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
2208
2209 mpi_montmul( &W[i], &W[1], N, mm, &T );
2210 }
2211 }
2212
2213 nblimbs = E->n;
2214 bufsize = 0;
2215 nbits = 0;
2216 wbits = 0;
2217 state = 0;
2218
2219 while( 1 )
2220 {
2221 if( bufsize == 0 )
2222 {
2223 if( nblimbs == 0 )
2224 break;
2225
2226 nblimbs--;
2227
2228 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
2229 }
2230
2231 bufsize--;
2232
2233 ei = (E->p[nblimbs] >> bufsize) & 1;
2234
2235 /*
2236 * skip leading 0s
2237 */
2238 if( ei == 0 && state == 0 )
2239 continue;
2240
2241 if( ei == 0 && state == 1 )
2242 {
2243 /*
2244 * out of window, square X
2245 */
2246 mpi_montmul( X, X, N, mm, &T );
2247 continue;
2248 }
2249
2250 /*
2251 * add ei to current window
2252 */
2253 state = 2;
2254
2255 nbits++;
2256 wbits |= ( ei << ( wsize - nbits ) );
2257
2258 if( nbits == wsize )
2259 {
2260 /*
2261 * X = X^wsize R^-1 mod N
2262 */
2263 for( i = 0; i < wsize; i++ )
2264 mpi_montmul( X, X, N, mm, &T );
2265
2266 /*
2267 * X = X * W[wbits] R^-1 mod N
2268 */
2269 MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) );
2270 mpi_montmul( X, &WW, N, mm, &T );
2271
2272 state--;
2273 nbits = 0;
2274 wbits = 0;
2275 }
2276 }
2277
2278 /*
2279 * process the remaining bits
2280 */
2281 for( i = 0; i < nbits; i++ )
2282 {
2283 mpi_montmul( X, X, N, mm, &T );
2284
2285 wbits <<= 1;
2286
2287 if( ( wbits & ( one << wsize ) ) != 0 )
2288 mpi_montmul( X, &W[1], N, mm, &T );
2289 }
2290
2291 /*
2292 * X = A^E * R * R^-1 mod N = A^E mod N
2293 */
2294 mpi_montred( X, N, mm, &T );
2295
2296 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
2297 {
2298 X->s = -1;
2299 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
2300 }
2301
2302 cleanup:
2303
2304 if( W )
2305 for( i = 0; i < array_size_W; i++ )
2306 mbedtls_mpi_free( W + i );
2307 mempool_free( mbedtls_mpi_mempool , W );
2308
2309 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &Apos );
2310 mbedtls_mpi_free( &WW );
2311
2312 if( prec_RR == NULL || prec_RR->p == NULL )
2313 mbedtls_mpi_free( &RR );
2314
2315 return( ret );
2316 }
2317
2318 /*
2319 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2320 */
mbedtls_mpi_gcd(mbedtls_mpi * G,const mbedtls_mpi * A,const mbedtls_mpi * B)2321 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
2322 {
2323 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2324 size_t lz, lzt;
2325 mbedtls_mpi TA, TB;
2326
2327 MPI_VALIDATE_RET( G != NULL );
2328 MPI_VALIDATE_RET( A != NULL );
2329 MPI_VALIDATE_RET( B != NULL );
2330
2331 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TB );
2332
2333 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2334 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
2335
2336 lz = mbedtls_mpi_lsb( &TA );
2337 lzt = mbedtls_mpi_lsb( &TB );
2338
2339 /* The loop below gives the correct result when A==0 but not when B==0.
2340 * So have a special case for B==0. Leverage the fact that we just
2341 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
2342 * slightly more efficient than cmp_int(). */
2343 if( lzt == 0 && mbedtls_mpi_get_bit( &TB, 0 ) == 0 )
2344 {
2345 ret = mbedtls_mpi_copy( G, A );
2346 goto cleanup;
2347 }
2348
2349 if( lzt < lz )
2350 lz = lzt;
2351
2352 TA.s = TB.s = 1;
2353
2354 /* We mostly follow the procedure described in HAC 14.54, but with some
2355 * minor differences:
2356 * - Sequences of multiplications or divisions by 2 are grouped into a
2357 * single shift operation.
2358 * - The procedure in HAC assumes that 0 < TB <= TA.
2359 * - The condition TB <= TA is not actually necessary for correctness.
2360 * TA and TB have symmetric roles except for the loop termination
2361 * condition, and the shifts at the beginning of the loop body
2362 * remove any significance from the ordering of TA vs TB before
2363 * the shifts.
2364 * - If TA = 0, the loop goes through 0 iterations and the result is
2365 * correctly TB.
2366 * - The case TB = 0 was short-circuited above.
2367 *
2368 * For the correctness proof below, decompose the original values of
2369 * A and B as
2370 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
2371 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
2372 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
2373 * and gcd(A',B') is odd or 0.
2374 *
2375 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
2376 * The code maintains the following invariant:
2377 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
2378 */
2379
2380 /* Proof that the loop terminates:
2381 * At each iteration, either the right-shift by 1 is made on a nonzero
2382 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
2383 * by at least 1, or the right-shift by 1 is made on zero and then
2384 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
2385 * since in that case TB is calculated from TB-TA with the condition TB>TA).
2386 */
2387 while( mbedtls_mpi_cmp_int( &TA, 0 ) != 0 )
2388 {
2389 /* Divisions by 2 preserve the invariant (I). */
2390 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2391 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
2392
2393 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
2394 * TA-TB is even so the division by 2 has an integer result.
2395 * Invariant (I) is preserved since any odd divisor of both TA and TB
2396 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
2397 * also divides TB, and any odd divisor of both TB and |TA-TB|/2 also
2398 * divides TA.
2399 */
2400 if( mbedtls_mpi_cmp_mpi( &TA, &TB ) >= 0 )
2401 {
2402 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2403 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
2404 }
2405 else
2406 {
2407 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2408 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
2409 }
2410 /* Note that one of TA or TB is still odd. */
2411 }
2412
2413 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
2414 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
2415 * - If there was at least one loop iteration, then one of TA or TB is odd,
2416 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
2417 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
2418 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
2419 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
2420 */
2421
2422 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2423 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
2424
2425 cleanup:
2426
2427 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TB );
2428
2429 return( ret );
2430 }
2431
2432 /* Fill X with n_bytes random bytes.
2433 * X must already have room for those bytes.
2434 * The ordering of the bytes returned from the RNG is suitable for
2435 * deterministic ECDSA (see RFC 6979 §3.3 and mbedtls_mpi_random()).
2436 * The size and sign of X are unchanged.
2437 * n_bytes must not be 0.
2438 */
mpi_fill_random_internal(mbedtls_mpi * X,size_t n_bytes,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2439 static int mpi_fill_random_internal(
2440 mbedtls_mpi *X, size_t n_bytes,
2441 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2442 {
2443 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2444 const size_t limbs = CHARS_TO_LIMBS( n_bytes );
2445 const size_t overhead = ( limbs * ciL ) - n_bytes;
2446
2447 if( X->n < limbs )
2448 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2449
2450 memset( X->p, 0, overhead );
2451 memset( (unsigned char *) X->p + limbs * ciL, 0, ( X->n - limbs ) * ciL );
2452 MBEDTLS_MPI_CHK( f_rng( p_rng, (unsigned char *) X->p + overhead, n_bytes ) );
2453 mpi_bigendian_to_host( X->p, limbs );
2454
2455 cleanup:
2456 return( ret );
2457 }
2458
2459 /*
2460 * Fill X with size bytes of random.
2461 *
2462 * Use a temporary bytes representation to make sure the result is the same
2463 * regardless of the platform endianness (useful when f_rng is actually
2464 * deterministic, eg for tests).
2465 */
mbedtls_mpi_fill_random(mbedtls_mpi * X,size_t size,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2466 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
2467 int (*f_rng)(void *, unsigned char *, size_t),
2468 void *p_rng )
2469 {
2470 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2471 size_t const limbs = CHARS_TO_LIMBS( size );
2472
2473 MPI_VALIDATE_RET( X != NULL );
2474 MPI_VALIDATE_RET( f_rng != NULL );
2475
2476 /* Ensure that target MPI has exactly the necessary number of limbs */
2477 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
2478 if( size == 0 )
2479 return( 0 );
2480
2481 ret = mpi_fill_random_internal( X, size, f_rng, p_rng );
2482
2483 cleanup:
2484 return( ret );
2485 }
2486
mbedtls_mpi_random(mbedtls_mpi * X,mbedtls_mpi_sint min,const mbedtls_mpi * N,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2487 int mbedtls_mpi_random( mbedtls_mpi *X,
2488 mbedtls_mpi_sint min,
2489 const mbedtls_mpi *N,
2490 int (*f_rng)(void *, unsigned char *, size_t),
2491 void *p_rng )
2492 {
2493 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2494 int count;
2495 unsigned lt_lower = 1, lt_upper = 0;
2496 size_t n_bits = mbedtls_mpi_bitlen( N );
2497 size_t n_bytes = ( n_bits + 7 ) / 8;
2498 mbedtls_mpi lower_bound;
2499
2500 if( min < 0 )
2501 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2502 if( mbedtls_mpi_cmp_int( N, min ) <= 0 )
2503 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2504
2505 /*
2506 * When min == 0, each try has at worst a probability 1/2 of failing
2507 * (the msb has a probability 1/2 of being 0, and then the result will
2508 * be < N), so after 30 tries failure probability is a most 2**(-30).
2509 *
2510 * When N is just below a power of 2, as is the case when generating
2511 * a random scalar on most elliptic curves, 1 try is enough with
2512 * overwhelming probability. When N is just above a power of 2,
2513 * as when generating a random scalar on secp224k1, each try has
2514 * a probability of failing that is almost 1/2.
2515 *
2516 * The probabilities are almost the same if min is nonzero but negligible
2517 * compared to N. This is always the case when N is crypto-sized, but
2518 * it's convenient to support small N for testing purposes. When N
2519 * is small, use a higher repeat count, otherwise the probability of
2520 * failure is macroscopic.
2521 */
2522 count = ( n_bytes > 4 ? 30 : 250 );
2523
2524 mbedtls_mpi_init( &lower_bound );
2525
2526 /* Ensure that target MPI has exactly the same number of limbs
2527 * as the upper bound, even if the upper bound has leading zeros.
2528 * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
2529 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) );
2530 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) );
2531 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) );
2532
2533 /*
2534 * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
2535 * when f_rng is a suitably parametrized instance of HMAC_DRBG:
2536 * - use the same byte ordering;
2537 * - keep the leftmost n_bits bits of the generated octet string;
2538 * - try until result is in the desired range.
2539 * This also avoids any bias, which is especially important for ECDSA.
2540 */
2541 do
2542 {
2543 MBEDTLS_MPI_CHK( mpi_fill_random_internal( X, n_bytes, f_rng, p_rng ) );
2544 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, 8 * n_bytes - n_bits ) );
2545
2546 if( --count == 0 )
2547 {
2548 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2549 goto cleanup;
2550 }
2551
2552 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, <_lower ) );
2553 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, <_upper ) );
2554 }
2555 while( lt_lower != 0 || lt_upper == 0 );
2556
2557 cleanup:
2558 mbedtls_mpi_free( &lower_bound );
2559 return( ret );
2560 }
2561
2562 /*
2563 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2564 */
mbedtls_mpi_inv_mod(mbedtls_mpi * X,const mbedtls_mpi * A,const mbedtls_mpi * N)2565 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
2566 {
2567 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2568 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
2569 MPI_VALIDATE_RET( X != NULL );
2570 MPI_VALIDATE_RET( A != NULL );
2571 MPI_VALIDATE_RET( N != NULL );
2572
2573 if( mbedtls_mpi_cmp_int( N, 1 ) <= 0 )
2574 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2575
2576 mbedtls_mpi_init_mempool( &TA ); mbedtls_mpi_init_mempool( &TU );
2577 mbedtls_mpi_init_mempool( &U1 ); mbedtls_mpi_init_mempool( &U2 );
2578 mbedtls_mpi_init_mempool( &G ); mbedtls_mpi_init_mempool( &TB );
2579 mbedtls_mpi_init_mempool( &TV ); mbedtls_mpi_init_mempool( &V1 );
2580 mbedtls_mpi_init_mempool( &V2 );
2581
2582 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
2583
2584 if( mbedtls_mpi_cmp_int( &G, 1 ) != 0 )
2585 {
2586 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2587 goto cleanup;
2588 }
2589
2590 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2591 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2592 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2593 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
2594
2595 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2596 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2597 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2598 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
2599
2600 do
2601 {
2602 while( ( TU.p[0] & 1 ) == 0 )
2603 {
2604 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
2605
2606 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2607 {
2608 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2609 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
2610 }
2611
2612 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2613 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
2614 }
2615
2616 while( ( TV.p[0] & 1 ) == 0 )
2617 {
2618 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
2619
2620 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2621 {
2622 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2623 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
2624 }
2625
2626 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2627 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
2628 }
2629
2630 if( mbedtls_mpi_cmp_mpi( &TU, &TV ) >= 0 )
2631 {
2632 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2633 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2634 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
2635 }
2636 else
2637 {
2638 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2639 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2640 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
2641 }
2642 }
2643 while( mbedtls_mpi_cmp_int( &TU, 0 ) != 0 );
2644
2645 while( mbedtls_mpi_cmp_int( &V1, 0 ) < 0 )
2646 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
2647
2648 while( mbedtls_mpi_cmp_mpi( &V1, N ) >= 0 )
2649 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
2650
2651 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
2652
2653 cleanup:
2654
2655 mbedtls_mpi_free( &TA ); mbedtls_mpi_free( &TU ); mbedtls_mpi_free( &U1 ); mbedtls_mpi_free( &U2 );
2656 mbedtls_mpi_free( &G ); mbedtls_mpi_free( &TB ); mbedtls_mpi_free( &TV );
2657 mbedtls_mpi_free( &V1 ); mbedtls_mpi_free( &V2 );
2658
2659 return( ret );
2660 }
2661
2662 #if defined(MBEDTLS_GENPRIME)
2663
2664 static const int small_prime[] =
2665 {
2666 3, 5, 7, 11, 13, 17, 19, 23,
2667 29, 31, 37, 41, 43, 47, 53, 59,
2668 61, 67, 71, 73, 79, 83, 89, 97,
2669 101, 103, 107, 109, 113, 127, 131, 137,
2670 139, 149, 151, 157, 163, 167, 173, 179,
2671 181, 191, 193, 197, 199, 211, 223, 227,
2672 229, 233, 239, 241, 251, 257, 263, 269,
2673 271, 277, 281, 283, 293, 307, 311, 313,
2674 317, 331, 337, 347, 349, 353, 359, 367,
2675 373, 379, 383, 389, 397, 401, 409, 419,
2676 421, 431, 433, 439, 443, 449, 457, 461,
2677 463, 467, 479, 487, 491, 499, 503, 509,
2678 521, 523, 541, 547, 557, 563, 569, 571,
2679 577, 587, 593, 599, 601, 607, 613, 617,
2680 619, 631, 641, 643, 647, 653, 659, 661,
2681 673, 677, 683, 691, 701, 709, 719, 727,
2682 733, 739, 743, 751, 757, 761, 769, 773,
2683 787, 797, 809, 811, 821, 823, 827, 829,
2684 839, 853, 857, 859, 863, 877, 881, 883,
2685 887, 907, 911, 919, 929, 937, 941, 947,
2686 953, 967, 971, 977, 983, 991, 997, -103
2687 };
2688
2689 /*
2690 * Small divisors test (X must be positive)
2691 *
2692 * Return values:
2693 * 0: no small factor (possible prime, more tests needed)
2694 * 1: certain prime
2695 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2696 * other negative: error
2697 */
mpi_check_small_factors(const mbedtls_mpi * X)2698 static int mpi_check_small_factors( const mbedtls_mpi *X )
2699 {
2700 int ret = 0;
2701 size_t i;
2702 mbedtls_mpi_uint r;
2703
2704 if( ( X->p[0] & 1 ) == 0 )
2705 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2706
2707 for( i = 0; small_prime[i] > 0; i++ )
2708 {
2709 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
2710 return( 1 );
2711
2712 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
2713
2714 if( r == 0 )
2715 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2716 }
2717
2718 cleanup:
2719 return( ret );
2720 }
2721
2722 /*
2723 * Miller-Rabin pseudo-primality test (HAC 4.24)
2724 */
mpi_miller_rabin(const mbedtls_mpi * X,size_t rounds,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2725 static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
2726 int (*f_rng)(void *, unsigned char *, size_t),
2727 void *p_rng )
2728 {
2729 int ret, count;
2730 size_t i, j, k, s;
2731 mbedtls_mpi W, R, T, A, RR;
2732
2733 MPI_VALIDATE_RET( X != NULL );
2734 MPI_VALIDATE_RET( f_rng != NULL );
2735
2736 mbedtls_mpi_init_mempool( &W ); mbedtls_mpi_init_mempool( &R );
2737 mbedtls_mpi_init_mempool( &T ); mbedtls_mpi_init_mempool( &A );
2738 mbedtls_mpi_init_mempool( &RR );
2739
2740 /*
2741 * W = |X| - 1
2742 * R = W >> lsb( W )
2743 */
2744 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2745 s = mbedtls_mpi_lsb( &W );
2746 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2747 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
2748
2749 for( i = 0; i < rounds; i++ )
2750 {
2751 /*
2752 * pick a random A, 1 < A < |X| - 1
2753 */
2754 count = 0;
2755 do {
2756 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
2757
2758 j = mbedtls_mpi_bitlen( &A );
2759 k = mbedtls_mpi_bitlen( &W );
2760 if (j > k) {
2761 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
2762 }
2763
2764 if (count++ > 300) {
2765 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2766 goto cleanup;
2767 }
2768
2769 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2770 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
2771
2772 /*
2773 * A = A^R mod |X|
2774 */
2775 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
2776
2777 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2778 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2779 continue;
2780
2781 j = 1;
2782 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
2783 {
2784 /*
2785 * A = A * A mod |X|
2786 */
2787 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2788 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
2789
2790 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2791 break;
2792
2793 j++;
2794 }
2795
2796 /*
2797 * not prime if A != |X| - 1 or A == 1
2798 */
2799 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2800 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2801 {
2802 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2803 break;
2804 }
2805 }
2806
2807 cleanup:
2808 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2809 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2810 mbedtls_mpi_free( &RR );
2811
2812 return( ret );
2813 }
2814
2815 /*
2816 * Pseudo-primality test: small factors, then Miller-Rabin
2817 */
mbedtls_mpi_is_prime_ext(const mbedtls_mpi * X,int rounds,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2818 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2819 int (*f_rng)(void *, unsigned char *, size_t),
2820 void *p_rng )
2821 {
2822 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2823 mbedtls_mpi XX;
2824 MPI_VALIDATE_RET( X != NULL );
2825 MPI_VALIDATE_RET( f_rng != NULL );
2826
2827 XX.s = 1;
2828 XX.n = X->n;
2829 XX.p = X->p;
2830
2831 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2832 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2833 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2834
2835 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
2836 return( 0 );
2837
2838 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2839 {
2840 if( ret == 1 )
2841 return( 0 );
2842
2843 return( ret );
2844 }
2845
2846 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
2847 }
2848
2849 #if !defined(MBEDTLS_DEPRECATED_REMOVED)
2850 /*
2851 * Pseudo-primality test, error probability 2^-80
2852 */
mbedtls_mpi_is_prime(const mbedtls_mpi * X,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2853 int mbedtls_mpi_is_prime( const mbedtls_mpi *X,
2854 int (*f_rng)(void *, unsigned char *, size_t),
2855 void *p_rng )
2856 {
2857 MPI_VALIDATE_RET( X != NULL );
2858 MPI_VALIDATE_RET( f_rng != NULL );
2859
2860 /*
2861 * In the past our key generation aimed for an error rate of at most
2862 * 2^-80. Since this function is deprecated, aim for the same certainty
2863 * here as well.
2864 */
2865 return( mbedtls_mpi_is_prime_ext( X, 40, f_rng, p_rng ) );
2866 }
2867 #endif
2868
2869 /*
2870 * Prime number generation
2871 *
2872 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2873 * be either 1024 bits or 1536 bits long, and flags must contain
2874 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
2875 */
mbedtls_mpi_gen_prime(mbedtls_mpi * X,size_t nbits,int flags,int (* f_rng)(void *,unsigned char *,size_t),void * p_rng)2876 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
2877 int (*f_rng)(void *, unsigned char *, size_t),
2878 void *p_rng )
2879 {
2880 #ifdef MBEDTLS_HAVE_INT64
2881 // ceil(2^63.5)
2882 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2883 #else
2884 // ceil(2^31.5)
2885 #define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2886 #endif
2887 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2888 size_t k, n;
2889 int rounds;
2890 mbedtls_mpi_uint r;
2891 mbedtls_mpi Y;
2892
2893 MPI_VALIDATE_RET( X != NULL );
2894 MPI_VALIDATE_RET( f_rng != NULL );
2895
2896 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2897 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2898
2899 mbedtls_mpi_init_mempool( &Y );
2900
2901 n = BITS_TO_LIMBS( nbits );
2902
2903 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2904 {
2905 /*
2906 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2907 */
2908 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2909 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2910 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2911 }
2912 else
2913 {
2914 /*
2915 * 2^-100 error probability, number of rounds computed based on HAC,
2916 * fact 4.48
2917 */
2918 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2919 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2920 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2921 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2922 }
2923
2924 while( 1 )
2925 {
2926 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2927 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2928 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2929
2930 k = n * biL;
2931 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2932 X->p[0] |= 1;
2933
2934 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
2935 {
2936 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
2937
2938 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2939 goto cleanup;
2940 }
2941 else
2942 {
2943 /*
2944 * An necessary condition for Y and X = 2Y + 1 to be prime
2945 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2946 * Make sure it is satisfied, while keeping X = 3 mod 4
2947 */
2948
2949 X->p[0] |= 2;
2950
2951 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2952 if( r == 0 )
2953 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2954 else if( r == 1 )
2955 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2956
2957 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2958 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2959 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2960
2961 while( 1 )
2962 {
2963 /*
2964 * First, check small factors for X and Y
2965 * before doing Miller-Rabin on any of them
2966 */
2967 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2968 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2969 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
2970 == 0 &&
2971 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
2972 == 0 )
2973 goto cleanup;
2974
2975 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2976 goto cleanup;
2977
2978 /*
2979 * Next candidates. We want to preserve Y = (X-1) / 2 and
2980 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2981 * so up Y by 6 and X by 12.
2982 */
2983 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2984 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
2985 }
2986 }
2987 }
2988
2989 cleanup:
2990
2991 mbedtls_mpi_free( &Y );
2992
2993 return( ret );
2994 }
2995
2996 #endif /* MBEDTLS_GENPRIME */
2997
2998 #if defined(MBEDTLS_SELF_TEST)
2999
3000 #define GCD_PAIR_COUNT 3
3001
3002 static const int gcd_pairs[GCD_PAIR_COUNT][3] =
3003 {
3004 { 693, 609, 21 },
3005 { 1764, 868, 28 },
3006 { 768454923, 542167814, 1 }
3007 };
3008
3009 /*
3010 * Checkup routine
3011 */
mbedtls_mpi_self_test(int verbose)3012 int mbedtls_mpi_self_test( int verbose )
3013 {
3014 int ret, i;
3015 mbedtls_mpi A, E, N, X, Y, U, V;
3016
3017 mbedtls_mpi_init_mempool( &A ); mbedtls_mpi_init_mempool( &E );
3018 mbedtls_mpi_init_mempool( &N ); mbedtls_mpi_init_mempool( &X );
3019 mbedtls_mpi_init_mempool( &Y ); mbedtls_mpi_init_mempool( &U );
3020 mbedtls_mpi_init_mempool( &V );
3021
3022 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
3023 "EFE021C2645FD1DC586E69184AF4A31E" \
3024 "D5F53E93B5F123FA41680867BA110131" \
3025 "944FE7952E2517337780CB0DB80E61AA" \
3026 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
3027
3028 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
3029 "B2E7EFD37075B9F03FF989C7C5051C20" \
3030 "34D2A323810251127E7BF8625A4F49A5" \
3031 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
3032 "5B5C25763222FEFCCFC38B832366C29E" ) );
3033
3034 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
3035 "0066A198186C18C10B2F5ED9B522752A" \
3036 "9830B69916E535C8F047518A889A43A5" \
3037 "94B6BED27A168D31D4A52F88925AA8F5" ) );
3038
3039 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
3040
3041 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3042 "602AB7ECA597A3D6B56FF9829A5E8B85" \
3043 "9E857EA95A03512E2BAE7391688D264A" \
3044 "A5663B0341DB9CCFD2C4C5F421FEC814" \
3045 "8001B72E848A38CAE1C65F78E56ABDEF" \
3046 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
3047 "ECF677152EF804370C1A305CAF3B5BF1" \
3048 "30879B56C61DE584A0F53A2447A51E" ) );
3049
3050 if( verbose != 0 )
3051 mbedtls_printf( " MPI test #1 (mul_mpi): " );
3052
3053 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
3054 {
3055 if( verbose != 0 )
3056 mbedtls_printf( "failed\n" );
3057
3058 ret = 1;
3059 goto cleanup;
3060 }
3061
3062 if( verbose != 0 )
3063 mbedtls_printf( "passed\n" );
3064
3065 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
3066
3067 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3068 "256567336059E52CAE22925474705F39A94" ) );
3069
3070 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
3071 "6613F26162223DF488E9CD48CC132C7A" \
3072 "0AC93C701B001B092E4E5B9F73BCD27B" \
3073 "9EE50D0657C77F374E903CDFA4C642" ) );
3074
3075 if( verbose != 0 )
3076 mbedtls_printf( " MPI test #2 (div_mpi): " );
3077
3078 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
3079 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
3080 {
3081 if( verbose != 0 )
3082 mbedtls_printf( "failed\n" );
3083
3084 ret = 1;
3085 goto cleanup;
3086 }
3087
3088 if( verbose != 0 )
3089 mbedtls_printf( "passed\n" );
3090
3091 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
3092
3093 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3094 "36E139AEA55215609D2816998ED020BB" \
3095 "BD96C37890F65171D948E9BC7CBAA4D9" \
3096 "325D24D6A3C12710F10A09FA08AB87" ) );
3097
3098 if( verbose != 0 )
3099 mbedtls_printf( " MPI test #3 (exp_mod): " );
3100
3101 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
3102 {
3103 if( verbose != 0 )
3104 mbedtls_printf( "failed\n" );
3105
3106 ret = 1;
3107 goto cleanup;
3108 }
3109
3110 if( verbose != 0 )
3111 mbedtls_printf( "passed\n" );
3112
3113 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X, &A, &N ) );
3114
3115 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3116 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
3117 "C3DBA76456363A10869622EAC2DD84EC" \
3118 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
3119
3120 if( verbose != 0 )
3121 mbedtls_printf( " MPI test #4 (inv_mod): " );
3122
3123 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
3124 {
3125 if( verbose != 0 )
3126 mbedtls_printf( "failed\n" );
3127
3128 ret = 1;
3129 goto cleanup;
3130 }
3131
3132 if( verbose != 0 )
3133 mbedtls_printf( "passed\n" );
3134
3135 if( verbose != 0 )
3136 mbedtls_printf( " MPI test #5 (simple gcd): " );
3137
3138 for( i = 0; i < GCD_PAIR_COUNT; i++ )
3139 {
3140 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
3141 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
3142
3143 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
3144
3145 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
3146 {
3147 if( verbose != 0 )
3148 mbedtls_printf( "failed at %d\n", i );
3149
3150 ret = 1;
3151 goto cleanup;
3152 }
3153 }
3154
3155 if( verbose != 0 )
3156 mbedtls_printf( "passed\n" );
3157
3158 cleanup:
3159
3160 if( ret != 0 && verbose != 0 )
3161 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret );
3162
3163 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
3164 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
3165
3166 if( verbose != 0 )
3167 mbedtls_printf( "\n" );
3168
3169 return( ret );
3170 }
3171
3172 #endif /* MBEDTLS_SELF_TEST */
3173
3174 #endif /* MBEDTLS_BIGNUM_C */
3175