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