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 "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 */
78static void mbedtls_mpi_zeroize( mbedtls_mpi_uint *v, size_t n )
79{
80 mbedtls_platform_zeroize( buf: v, ciL * n );
81}
82
83/*
84 * Initialize one MPI
85 */
86void 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 */
98void mbedtls_mpi_free( mbedtls_mpi *X )
99{
100 if( X == NULL )
101 return;
102
103 if( X->p != NULL )
104 {
105 mbedtls_mpi_zeroize( v: X->p, n: X->n );
106 mbedtls_free( ptr: 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 */
117int 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( nmemb: nblimbs, ciL ) ) == NULL )
128 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
129
130 if( X->p != NULL )
131 {
132 memcpy( dest: p, src: X->p, n: X->n * ciL );
133 mbedtls_mpi_zeroize( v: X->p, n: X->n );
134 mbedtls_free( ptr: 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 */
148int 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( nmemb: i, ciL ) ) == NULL )
171 return( MBEDTLS_ERR_MPI_ALLOC_FAILED );
172
173 if( X->p != NULL )
174 {
175 memcpy( dest: p, src: X->p, n: i * ciL );
176 mbedtls_mpi_zeroize( v: X->p, n: X->n );
177 mbedtls_free( ptr: 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. */
187static 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( s: X->p, c: 0, n: limbs * ciL );
197 X->s = 1;
198 return( 0 );
199 }
200 else
201 {
202 mbedtls_mpi_free( X );
203 return( mbedtls_mpi_grow( X, nblimbs: 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 */
216int 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( s: X->p, c: 0, n: 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( s: X->p + i, c: 0, n: ( X->n - i ) * ciL );
250 }
251
252 memcpy( dest: X->p, src: Y->p, n: i * ciL );
253
254cleanup:
255
256 return( ret );
257}
258
259/*
260 * Swap the contents of X and Y
261 */
262void 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( dest: &T, src: X, n: sizeof( mbedtls_mpi ) );
269 memcpy( dest: X, src: Y, n: sizeof( mbedtls_mpi ) );
270 memcpy( dest: Y, src: &T, n: sizeof( mbedtls_mpi ) );
271}
272
273/*
274 * Set value from integer
275 */
276int 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( s: X->p, c: 0, n: X->n * ciL );
283
284 X->p[0] = ( z < 0 ) ? -z : z;
285 X->s = ( z < 0 ) ? -1 : 1;
286
287cleanup:
288
289 return( ret );
290}
291
292/*
293 * Get a specific bit
294 */
295int 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 */
312int 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
333cleanup:
334
335 return( ret );
336}
337
338/*
339 * Return the number of less significant zero-bits
340 */
341size_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 */
357static 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 */
375size_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: X->p[i] );
387
388 return( ( i * biL ) + j );
389}
390
391/*
392 * Return the total size in bytes
393 */
394size_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 */
402static 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 */
419int 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( X: &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: 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
479cleanup:
480
481 mbedtls_mpi_free( X: &T );
482
483 return( ret );
484}
485
486/*
487 * Helper to write the digits high-order first.
488 */
489static 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, z: 0 ) != 0 );
516
517 memmove( dest: *p, src: p_end, n: length );
518 *p += length;
519
520cleanup:
521
522 return( ret );
523}
524
525/*
526 * Export into an ASCII string
527 */
528int 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( X: &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
605cleanup:
606
607 mbedtls_mpi_free( X: &T );
608
609 return( ret );
610}
611
612#if defined(MBEDTLS_FS_IO)
613/*
614 * Read X from an opened file
615 */
616int 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 */
655int 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
689cleanup:
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
699static 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
714static 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
757static 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( x: *cur_limb_left );
781 *cur_limb_left = mpi_uint_bigendian_to_host( x: *cur_limb_right );
782 *cur_limb_right = tmp;
783 }
784}
785
786/*
787 * Import X from unsigned binary data, little endian
788 */
789int 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
802cleanup:
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 */
815int 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( dest: Xp + overhead, src: buf, n: buflen );
834
835 mpi_bigendian_to_host( p: X->p, limbs );
836 }
837
838cleanup:
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 */
851int 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( s: buf + stored_bytes, c: 0, n: buflen - stored_bytes );
882 }
883
884 return( 0 );
885}
886
887/*
888 * Export X into unsigned binary data, big endian
889 */
890int 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( s: buf, c: 0, n: 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 */
936int 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
979cleanup:
980
981 return( ret );
982}
983
984/*
985 * Right-shift: X >>= count
986 */
987int 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, z: 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 */
1031int 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 */
1063int 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 */
1098int 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: &Y ) );
1110}
1111
1112/*
1113 * Unsigned addition: X = |A| + |B| (HAC 14.7)
1114 */
1115int 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
1166cleanup:
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 */
1188static 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 */
1208int 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( dest: X->p + n, src: A->p + n, n: ( A->n - n ) * ciL );
1234 if( X->n > A->n )
1235 memset( s: X->p + A->n, c: 0, n: ( X->n - A->n ) * ciL );
1236
1237 carry = mpi_sub_hlp( n, d: X->p, l: A->p, r: 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
1256cleanup:
1257 return( ret );
1258}
1259
1260/*
1261 * Signed addition: X = A + B
1262 */
1263int 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( X: A, Y: 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
1290cleanup:
1291
1292 return( ret );
1293}
1294
1295/*
1296 * Signed subtraction: X = A - B
1297 */
1298int 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( X: A, Y: 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
1325cleanup:
1326
1327 return( ret );
1328}
1329
1330/*
1331 * Signed addition: X = A + b
1332 */
1333int 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: &B ) );
1346}
1347
1348/*
1349 * Signed subtraction: X = A - b
1350 */
1351int 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: &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 */
1382static
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
1390void 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;
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 while( c != 0 )
1447 {
1448 *d += c; c = ( *d < c ); d++;
1449 }
1450}
1451
1452/*
1453 * Baseline multiplication: X = A * B (HAC 14.12)
1454 */
1455int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B )
1456{
1457 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1458 size_t i, j;
1459 mbedtls_mpi TA, TB;
1460 int result_is_zero = 0;
1461 MPI_VALIDATE_RET( X != NULL );
1462 MPI_VALIDATE_RET( A != NULL );
1463 MPI_VALIDATE_RET( B != NULL );
1464
1465 mbedtls_mpi_init( X: &TA ); mbedtls_mpi_init( X: &TB );
1466
1467 if( X == A ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) ); A = &TA; }
1468 if( X == B ) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) ); B = &TB; }
1469
1470 for( i = A->n; i > 0; i-- )
1471 if( A->p[i - 1] != 0 )
1472 break;
1473 if( i == 0 )
1474 result_is_zero = 1;
1475
1476 for( j = B->n; j > 0; j-- )
1477 if( B->p[j - 1] != 0 )
1478 break;
1479 if( j == 0 )
1480 result_is_zero = 1;
1481
1482 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, i + j ) );
1483 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X, 0 ) );
1484
1485 for( ; j > 0; j-- )
1486 mpi_mul_hlp( i, s: A->p, d: X->p + j - 1, b: B->p[j - 1] );
1487
1488 /* If the result is 0, we don't shortcut the operation, which reduces
1489 * but does not eliminate side channels leaking the zero-ness. We do
1490 * need to take care to set the sign bit properly since the library does
1491 * not fully support an MPI object with a value of 0 and s == -1. */
1492 if( result_is_zero )
1493 X->s = 1;
1494 else
1495 X->s = A->s * B->s;
1496
1497cleanup:
1498
1499 mbedtls_mpi_free( X: &TB ); mbedtls_mpi_free( X: &TA );
1500
1501 return( ret );
1502}
1503
1504/*
1505 * Baseline multiplication: X = A * b
1506 */
1507int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b )
1508{
1509 MPI_VALIDATE_RET( X != NULL );
1510 MPI_VALIDATE_RET( A != NULL );
1511
1512 /* mpi_mul_hlp can't deal with a leading 0. */
1513 size_t n = A->n;
1514 while( n > 0 && A->p[n - 1] == 0 )
1515 --n;
1516
1517 /* The general method below doesn't work if n==0 or b==0. By chance
1518 * calculating the result is trivial in those cases. */
1519 if( b == 0 || n == 0 )
1520 {
1521 return( mbedtls_mpi_lset( X, z: 0 ) );
1522 }
1523
1524 /* Calculate A*b as A + A*(b-1) to take advantage of mpi_mul_hlp */
1525 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1526 /* In general, A * b requires 1 limb more than b. If
1527 * A->p[n - 1] * b / b == A->p[n - 1], then A * b fits in the same
1528 * number of limbs as A and the call to grow() is not required since
1529 * copy() will take care of the growth if needed. However, experimentally,
1530 * making the call to grow() unconditional causes slightly fewer
1531 * calls to calloc() in ECP code, presumably because it reuses the
1532 * same mpi for a while and this way the mpi is more likely to directly
1533 * grow to its final size. */
1534 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, n + 1 ) );
1535 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, A ) );
1536 mpi_mul_hlp( i: n, s: A->p, d: X->p, b: b - 1 );
1537
1538cleanup:
1539 return( ret );
1540}
1541
1542/*
1543 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1544 * mbedtls_mpi_uint divisor, d
1545 */
1546static mbedtls_mpi_uint mbedtls_int_div_int( mbedtls_mpi_uint u1,
1547 mbedtls_mpi_uint u0, mbedtls_mpi_uint d, mbedtls_mpi_uint *r )
1548{
1549#if defined(MBEDTLS_HAVE_UDBL)
1550 mbedtls_t_udbl dividend, quotient;
1551#else
1552 const mbedtls_mpi_uint radix = (mbedtls_mpi_uint) 1 << biH;
1553 const mbedtls_mpi_uint uint_halfword_mask = ( (mbedtls_mpi_uint) 1 << biH ) - 1;
1554 mbedtls_mpi_uint d0, d1, q0, q1, rAX, r0, quotient;
1555 mbedtls_mpi_uint u0_msw, u0_lsw;
1556 size_t s;
1557#endif
1558
1559 /*
1560 * Check for overflow
1561 */
1562 if( 0 == d || u1 >= d )
1563 {
1564 if (r != NULL) *r = ~0;
1565
1566 return ( ~0 );
1567 }
1568
1569#if defined(MBEDTLS_HAVE_UDBL)
1570 dividend = (mbedtls_t_udbl) u1 << biL;
1571 dividend |= (mbedtls_t_udbl) u0;
1572 quotient = dividend / d;
1573 if( quotient > ( (mbedtls_t_udbl) 1 << biL ) - 1 )
1574 quotient = ( (mbedtls_t_udbl) 1 << biL ) - 1;
1575
1576 if( r != NULL )
1577 *r = (mbedtls_mpi_uint)( dividend - (quotient * d ) );
1578
1579 return (mbedtls_mpi_uint) quotient;
1580#else
1581
1582 /*
1583 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1584 * Vol. 2 - Seminumerical Algorithms, Knuth
1585 */
1586
1587 /*
1588 * Normalize the divisor, d, and dividend, u0, u1
1589 */
1590 s = mbedtls_clz( d );
1591 d = d << s;
1592
1593 u1 = u1 << s;
1594 u1 |= ( u0 >> ( biL - s ) ) & ( -(mbedtls_mpi_sint)s >> ( biL - 1 ) );
1595 u0 = u0 << s;
1596
1597 d1 = d >> biH;
1598 d0 = d & uint_halfword_mask;
1599
1600 u0_msw = u0 >> biH;
1601 u0_lsw = u0 & uint_halfword_mask;
1602
1603 /*
1604 * Find the first quotient and remainder
1605 */
1606 q1 = u1 / d1;
1607 r0 = u1 - d1 * q1;
1608
1609 while( q1 >= radix || ( q1 * d0 > radix * r0 + u0_msw ) )
1610 {
1611 q1 -= 1;
1612 r0 += d1;
1613
1614 if ( r0 >= radix ) break;
1615 }
1616
1617 rAX = ( u1 * radix ) + ( u0_msw - q1 * d );
1618 q0 = rAX / d1;
1619 r0 = rAX - q0 * d1;
1620
1621 while( q0 >= radix || ( q0 * d0 > radix * r0 + u0_lsw ) )
1622 {
1623 q0 -= 1;
1624 r0 += d1;
1625
1626 if ( r0 >= radix ) break;
1627 }
1628
1629 if (r != NULL)
1630 *r = ( rAX * radix + u0_lsw - q0 * d ) >> s;
1631
1632 quotient = q1 * radix + q0;
1633
1634 return quotient;
1635#endif
1636}
1637
1638/*
1639 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1640 */
1641int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A,
1642 const mbedtls_mpi *B )
1643{
1644 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1645 size_t i, n, t, k;
1646 mbedtls_mpi X, Y, Z, T1, T2;
1647 mbedtls_mpi_uint TP2[3];
1648 MPI_VALIDATE_RET( A != NULL );
1649 MPI_VALIDATE_RET( B != NULL );
1650
1651 if( mbedtls_mpi_cmp_int( X: B, z: 0 ) == 0 )
1652 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1653
1654 mbedtls_mpi_init( X: &X ); mbedtls_mpi_init( X: &Y ); mbedtls_mpi_init( X: &Z );
1655 mbedtls_mpi_init( X: &T1 );
1656 /*
1657 * Avoid dynamic memory allocations for constant-size T2.
1658 *
1659 * T2 is used for comparison only and the 3 limbs are assigned explicitly,
1660 * so nobody increase the size of the MPI and we're safe to use an on-stack
1661 * buffer.
1662 */
1663 T2.s = 1;
1664 T2.n = sizeof( TP2 ) / sizeof( *TP2 );
1665 T2.p = TP2;
1666
1667 if( mbedtls_mpi_cmp_abs( X: A, Y: B ) < 0 )
1668 {
1669 if( Q != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q, 0 ) );
1670 if( R != NULL ) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, A ) );
1671 return( 0 );
1672 }
1673
1674 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X, A ) );
1675 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, B ) );
1676 X.s = Y.s = 1;
1677
1678 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z, A->n + 2 ) );
1679 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z, 0 ) );
1680 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1, A->n + 2 ) );
1681
1682 k = mbedtls_mpi_bitlen( X: &Y ) % biL;
1683 if( k < biL - 1 )
1684 {
1685 k = biL - 1 - k;
1686 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X, k ) );
1687 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, k ) );
1688 }
1689 else k = 0;
1690
1691 n = X.n - 1;
1692 t = Y.n - 1;
1693 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y, biL * ( n - t ) ) );
1694
1695 while( mbedtls_mpi_cmp_mpi( X: &X, Y: &Y ) >= 0 )
1696 {
1697 Z.p[n - t]++;
1698 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &Y ) );
1699 }
1700 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, biL * ( n - t ) ) );
1701
1702 for( i = n; i > t ; i-- )
1703 {
1704 if( X.p[i] >= Y.p[t] )
1705 Z.p[i - t - 1] = ~0;
1706 else
1707 {
1708 Z.p[i - t - 1] = mbedtls_int_div_int( u1: X.p[i], u0: X.p[i - 1],
1709 d: Y.p[t], NULL);
1710 }
1711
1712 T2.p[0] = ( i < 2 ) ? 0 : X.p[i - 2];
1713 T2.p[1] = ( i < 1 ) ? 0 : X.p[i - 1];
1714 T2.p[2] = X.p[i];
1715
1716 Z.p[i - t - 1]++;
1717 do
1718 {
1719 Z.p[i - t - 1]--;
1720
1721 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1, 0 ) );
1722 T1.p[0] = ( t < 1 ) ? 0 : Y.p[t - 1];
1723 T1.p[1] = Y.p[t];
1724 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &T1, Z.p[i - t - 1] ) );
1725 }
1726 while( mbedtls_mpi_cmp_mpi( X: &T1, Y: &T2 ) > 0 );
1727
1728 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1, &Y, Z.p[i - t - 1] ) );
1729 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1730 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X, &X, &T1 ) );
1731
1732 if( mbedtls_mpi_cmp_int( X: &X, z: 0 ) < 0 )
1733 {
1734 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1, &Y ) );
1735 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1, biL * ( i - t - 1 ) ) );
1736 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X, &X, &T1 ) );
1737 Z.p[i - t - 1]--;
1738 }
1739 }
1740
1741 if( Q != NULL )
1742 {
1743 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q, &Z ) );
1744 Q->s = A->s * B->s;
1745 }
1746
1747 if( R != NULL )
1748 {
1749 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X, k ) );
1750 X.s = A->s;
1751 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R, &X ) );
1752
1753 if( mbedtls_mpi_cmp_int( X: R, z: 0 ) == 0 )
1754 R->s = 1;
1755 }
1756
1757cleanup:
1758
1759 mbedtls_mpi_free( X: &X ); mbedtls_mpi_free( X: &Y ); mbedtls_mpi_free( X: &Z );
1760 mbedtls_mpi_free( X: &T1 );
1761 mbedtls_platform_zeroize( buf: TP2, len: sizeof( TP2 ) );
1762
1763 return( ret );
1764}
1765
1766/*
1767 * Division by int: A = Q * b + R
1768 */
1769int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R,
1770 const mbedtls_mpi *A,
1771 mbedtls_mpi_sint b )
1772{
1773 mbedtls_mpi B;
1774 mbedtls_mpi_uint p[1];
1775 MPI_VALIDATE_RET( A != NULL );
1776
1777 p[0] = ( b < 0 ) ? -b : b;
1778 B.s = ( b < 0 ) ? -1 : 1;
1779 B.n = 1;
1780 B.p = p;
1781
1782 return( mbedtls_mpi_div_mpi( Q, R, A, B: &B ) );
1783}
1784
1785/*
1786 * Modulo: R = A mod B
1787 */
1788int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B )
1789{
1790 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1791 MPI_VALIDATE_RET( R != NULL );
1792 MPI_VALIDATE_RET( A != NULL );
1793 MPI_VALIDATE_RET( B != NULL );
1794
1795 if( mbedtls_mpi_cmp_int( X: B, z: 0 ) < 0 )
1796 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1797
1798 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL, R, A, B ) );
1799
1800 while( mbedtls_mpi_cmp_int( X: R, z: 0 ) < 0 )
1801 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R, R, B ) );
1802
1803 while( mbedtls_mpi_cmp_mpi( X: R, Y: B ) >= 0 )
1804 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R, R, B ) );
1805
1806cleanup:
1807
1808 return( ret );
1809}
1810
1811/*
1812 * Modulo: r = A mod b
1813 */
1814int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b )
1815{
1816 size_t i;
1817 mbedtls_mpi_uint x, y, z;
1818 MPI_VALIDATE_RET( r != NULL );
1819 MPI_VALIDATE_RET( A != NULL );
1820
1821 if( b == 0 )
1822 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO );
1823
1824 if( b < 0 )
1825 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE );
1826
1827 /*
1828 * handle trivial cases
1829 */
1830 if( b == 1 )
1831 {
1832 *r = 0;
1833 return( 0 );
1834 }
1835
1836 if( b == 2 )
1837 {
1838 *r = A->p[0] & 1;
1839 return( 0 );
1840 }
1841
1842 /*
1843 * general case
1844 */
1845 for( i = A->n, y = 0; i > 0; i-- )
1846 {
1847 x = A->p[i - 1];
1848 y = ( y << biH ) | ( x >> biH );
1849 z = y / b;
1850 y -= z * b;
1851
1852 x <<= biH;
1853 y = ( y << biH ) | ( x >> biH );
1854 z = y / b;
1855 y -= z * b;
1856 }
1857
1858 /*
1859 * If A is negative, then the current y represents a negative value.
1860 * Flipping it to the positive side.
1861 */
1862 if( A->s < 0 && y != 0 )
1863 y = b - y;
1864
1865 *r = y;
1866
1867 return( 0 );
1868}
1869
1870/*
1871 * Fast Montgomery initialization (thanks to Tom St Denis)
1872 */
1873static void mpi_montg_init( mbedtls_mpi_uint *mm, const mbedtls_mpi *N )
1874{
1875 mbedtls_mpi_uint x, m0 = N->p[0];
1876 unsigned int i;
1877
1878 x = m0;
1879 x += ( ( m0 + 2 ) & 4 ) << 1;
1880
1881 for( i = biL; i >= 8; i /= 2 )
1882 x *= ( 2 - ( m0 * x ) );
1883
1884 *mm = ~x + 1;
1885}
1886
1887/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1888 *
1889 * \param[in,out] A One of the numbers to multiply.
1890 * It must have at least as many limbs as N
1891 * (A->n >= N->n), and any limbs beyond n are ignored.
1892 * On successful completion, A contains the result of
1893 * the multiplication A * B * R^-1 mod N where
1894 * R = (2^ciL)^n.
1895 * \param[in] B One of the numbers to multiply.
1896 * It must be nonzero and must not have more limbs than N
1897 * (B->n <= N->n).
1898 * \param[in] N The modulo. N must be odd.
1899 * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
1900 * This is -N^-1 mod 2^ciL.
1901 * \param[in,out] T A bignum for temporary storage.
1902 * It must be at least twice the limb size of N plus 2
1903 * (T->n >= 2 * (N->n + 1)).
1904 * Its initial content is unused and
1905 * its final content is indeterminate.
1906 * Note that unlike the usual convention in the library
1907 * for `const mbedtls_mpi*`, the content of T can change.
1908 */
1909static void mpi_montmul( mbedtls_mpi *A, const mbedtls_mpi *B, const mbedtls_mpi *N, mbedtls_mpi_uint mm,
1910 const mbedtls_mpi *T )
1911{
1912 size_t i, n, m;
1913 mbedtls_mpi_uint u0, u1, *d;
1914
1915 memset( s: T->p, c: 0, n: T->n * ciL );
1916
1917 d = T->p;
1918 n = N->n;
1919 m = ( B->n < n ) ? B->n : n;
1920
1921 for( i = 0; i < n; i++ )
1922 {
1923 /*
1924 * T = (T + u0*B + u1*N) / 2^biL
1925 */
1926 u0 = A->p[i];
1927 u1 = ( d[0] + u0 * B->p[0] ) * mm;
1928
1929 mpi_mul_hlp( i: m, s: B->p, d, b: u0 );
1930 mpi_mul_hlp( i: n, s: N->p, d, b: u1 );
1931
1932 *d++ = u0; d[n + 1] = 0;
1933 }
1934
1935 /* At this point, d is either the desired result or the desired result
1936 * plus N. We now potentially subtract N, avoiding leaking whether the
1937 * subtraction is performed through side channels. */
1938
1939 /* Copy the n least significant limbs of d to A, so that
1940 * A = d if d < N (recall that N has n limbs). */
1941 memcpy( dest: A->p, src: d, n: n * ciL );
1942 /* If d >= N then we want to set A to d - N. To prevent timing attacks,
1943 * do the calculation without using conditional tests. */
1944 /* Set d to d0 + (2^biL)^n - N where d0 is the current value of d. */
1945 d[n] += 1;
1946 d[n] -= mpi_sub_hlp( n, d, l: d, r: N->p );
1947 /* If d0 < N then d < (2^biL)^n
1948 * so d[n] == 0 and we want to keep A as it is.
1949 * If d0 >= N then d >= (2^biL)^n, and d <= (2^biL)^n + N < 2 * (2^biL)^n
1950 * so d[n] == 1 and we want to set A to the result of the subtraction
1951 * which is d - (2^biL)^n, i.e. the n least significant limbs of d.
1952 * This exactly corresponds to a conditional assignment. */
1953 mbedtls_ct_mpi_uint_cond_assign( n, dest: A->p, src: d, condition: (unsigned char) d[n] );
1954}
1955
1956/*
1957 * Montgomery reduction: A = A * R^-1 mod N
1958 *
1959 * See mpi_montmul() regarding constraints and guarantees on the parameters.
1960 */
1961static void mpi_montred( mbedtls_mpi *A, const mbedtls_mpi *N,
1962 mbedtls_mpi_uint mm, const mbedtls_mpi *T )
1963{
1964 mbedtls_mpi_uint z = 1;
1965 mbedtls_mpi U;
1966
1967 U.n = U.s = (int) z;
1968 U.p = &z;
1969
1970 mpi_montmul( A, B: &U, N, mm, T );
1971}
1972
1973/**
1974 * Select an MPI from a table without leaking the index.
1975 *
1976 * This is functionally equivalent to mbedtls_mpi_copy(R, T[idx]) except it
1977 * reads the entire table in order to avoid leaking the value of idx to an
1978 * attacker able to observe memory access patterns.
1979 *
1980 * \param[out] R Where to write the selected MPI.
1981 * \param[in] T The table to read from.
1982 * \param[in] T_size The number of elements in the table.
1983 * \param[in] idx The index of the element to select;
1984 * this must satisfy 0 <= idx < T_size.
1985 *
1986 * \return \c 0 on success, or a negative error code.
1987 */
1988static int mpi_select( mbedtls_mpi *R, const mbedtls_mpi *T, size_t T_size, size_t idx )
1989{
1990 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
1991
1992 for( size_t i = 0; i < T_size; i++ )
1993 {
1994 MBEDTLS_MPI_CHK( mbedtls_mpi_safe_cond_assign( R, &T[i],
1995 (unsigned char) mbedtls_ct_size_bool_eq( i, idx ) ) );
1996 }
1997
1998cleanup:
1999 return( ret );
2000}
2001
2002/*
2003 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
2004 */
2005int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A,
2006 const mbedtls_mpi *E, const mbedtls_mpi *N,
2007 mbedtls_mpi *prec_RR )
2008{
2009 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2010 size_t wbits, wsize, one = 1;
2011 size_t i, j, nblimbs;
2012 size_t bufsize, nbits;
2013 mbedtls_mpi_uint ei, mm, state;
2014 mbedtls_mpi RR, T, W[ 1 << MBEDTLS_MPI_WINDOW_SIZE ], WW, Apos;
2015 int neg;
2016
2017 MPI_VALIDATE_RET( X != NULL );
2018 MPI_VALIDATE_RET( A != NULL );
2019 MPI_VALIDATE_RET( E != NULL );
2020 MPI_VALIDATE_RET( N != NULL );
2021
2022 if( mbedtls_mpi_cmp_int( X: N, z: 0 ) <= 0 || ( N->p[0] & 1 ) == 0 )
2023 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2024
2025 if( mbedtls_mpi_cmp_int( X: E, z: 0 ) < 0 )
2026 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2027
2028 if( mbedtls_mpi_bitlen( X: E ) > MBEDTLS_MPI_MAX_BITS ||
2029 mbedtls_mpi_bitlen( X: N ) > MBEDTLS_MPI_MAX_BITS )
2030 return ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2031
2032 /*
2033 * Init temps and window size
2034 */
2035 mpi_montg_init( mm: &mm, N );
2036 mbedtls_mpi_init( X: &RR ); mbedtls_mpi_init( X: &T );
2037 mbedtls_mpi_init( X: &Apos );
2038 mbedtls_mpi_init( X: &WW );
2039 memset( s: W, c: 0, n: sizeof( W ) );
2040
2041 i = mbedtls_mpi_bitlen( X: E );
2042
2043 wsize = ( i > 671 ) ? 6 : ( i > 239 ) ? 5 :
2044 ( i > 79 ) ? 4 : ( i > 23 ) ? 3 : 1;
2045
2046#if( MBEDTLS_MPI_WINDOW_SIZE < 6 )
2047 if( wsize > MBEDTLS_MPI_WINDOW_SIZE )
2048 wsize = MBEDTLS_MPI_WINDOW_SIZE;
2049#endif
2050
2051 j = N->n + 1;
2052 /* All W[i] and X must have at least N->n limbs for the mpi_montmul()
2053 * and mpi_montred() calls later. Here we ensure that W[1] and X are
2054 * large enough, and later we'll grow other W[i] to the same length.
2055 * They must not be shrunk midway through this function!
2056 */
2057 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X, j ) );
2058 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], j ) );
2059 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T, j * 2 ) );
2060
2061 /*
2062 * Compensate for negative A (and correct at the end)
2063 */
2064 neg = ( A->s == -1 );
2065 if( neg )
2066 {
2067 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos, A ) );
2068 Apos.s = 1;
2069 A = &Apos;
2070 }
2071
2072 /*
2073 * If 1st call, pre-compute R^2 mod N
2074 */
2075 if( prec_RR == NULL || prec_RR->p == NULL )
2076 {
2077 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR, 1 ) );
2078 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR, N->n * 2 * biL ) );
2079 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR, &RR, N ) );
2080
2081 if( prec_RR != NULL )
2082 memcpy( dest: prec_RR, src: &RR, n: sizeof( mbedtls_mpi ) );
2083 }
2084 else
2085 memcpy( dest: &RR, src: prec_RR, n: sizeof( mbedtls_mpi ) );
2086
2087 /*
2088 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
2089 */
2090 if( mbedtls_mpi_cmp_mpi( X: A, Y: N ) >= 0 )
2091 {
2092 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W[1], A, N ) );
2093 /* This should be a no-op because W[1] is already that large before
2094 * mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
2095 * in mpi_montmul() below, so let's make sure. */
2096 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[1], N->n + 1 ) );
2097 }
2098 else
2099 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[1], A ) );
2100
2101 /* Note that this is safe because W[1] always has at least N->n limbs
2102 * (it grew above and was preserved by mbedtls_mpi_copy()). */
2103 mpi_montmul( A: &W[1], B: &RR, N, mm, T: &T );
2104
2105 /*
2106 * X = R^2 * R^-1 mod N = R mod N
2107 */
2108 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &RR ) );
2109 mpi_montred( A: X, N, mm, T: &T );
2110
2111 if( wsize > 1 )
2112 {
2113 /*
2114 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
2115 */
2116 j = one << ( wsize - 1 );
2117
2118 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[j], N->n + 1 ) );
2119 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[j], &W[1] ) );
2120
2121 for( i = 0; i < wsize - 1; i++ )
2122 mpi_montmul( A: &W[j], B: &W[j], N, mm, T: &T );
2123
2124 /*
2125 * W[i] = W[i - 1] * W[1]
2126 */
2127 for( i = j + 1; i < ( one << wsize ); i++ )
2128 {
2129 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W[i], N->n + 1 ) );
2130 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W[i], &W[i - 1] ) );
2131
2132 mpi_montmul( A: &W[i], B: &W[1], N, mm, T: &T );
2133 }
2134 }
2135
2136 nblimbs = E->n;
2137 bufsize = 0;
2138 nbits = 0;
2139 wbits = 0;
2140 state = 0;
2141
2142 while( 1 )
2143 {
2144 if( bufsize == 0 )
2145 {
2146 if( nblimbs == 0 )
2147 break;
2148
2149 nblimbs--;
2150
2151 bufsize = sizeof( mbedtls_mpi_uint ) << 3;
2152 }
2153
2154 bufsize--;
2155
2156 ei = (E->p[nblimbs] >> bufsize) & 1;
2157
2158 /*
2159 * skip leading 0s
2160 */
2161 if( ei == 0 && state == 0 )
2162 continue;
2163
2164 if( ei == 0 && state == 1 )
2165 {
2166 /*
2167 * out of window, square X
2168 */
2169 mpi_montmul( A: X, B: X, N, mm, T: &T );
2170 continue;
2171 }
2172
2173 /*
2174 * add ei to current window
2175 */
2176 state = 2;
2177
2178 nbits++;
2179 wbits |= ( ei << ( wsize - nbits ) );
2180
2181 if( nbits == wsize )
2182 {
2183 /*
2184 * X = X^wsize R^-1 mod N
2185 */
2186 for( i = 0; i < wsize; i++ )
2187 mpi_montmul( A: X, B: X, N, mm, T: &T );
2188
2189 /*
2190 * X = X * W[wbits] R^-1 mod N
2191 */
2192 MBEDTLS_MPI_CHK( mpi_select( &WW, W, (size_t) 1 << wsize, wbits ) );
2193 mpi_montmul( A: X, B: &WW, N, mm, T: &T );
2194
2195 state--;
2196 nbits = 0;
2197 wbits = 0;
2198 }
2199 }
2200
2201 /*
2202 * process the remaining bits
2203 */
2204 for( i = 0; i < nbits; i++ )
2205 {
2206 mpi_montmul( A: X, B: X, N, mm, T: &T );
2207
2208 wbits <<= 1;
2209
2210 if( ( wbits & ( one << wsize ) ) != 0 )
2211 mpi_montmul( A: X, B: &W[1], N, mm, T: &T );
2212 }
2213
2214 /*
2215 * X = A^E * R * R^-1 mod N = A^E mod N
2216 */
2217 mpi_montred( A: X, N, mm, T: &T );
2218
2219 if( neg && E->n != 0 && ( E->p[0] & 1 ) != 0 )
2220 {
2221 X->s = -1;
2222 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X, N, X ) );
2223 }
2224
2225cleanup:
2226
2227 for( i = ( one << ( wsize - 1 ) ); i < ( one << wsize ); i++ )
2228 mbedtls_mpi_free( X: &W[i] );
2229
2230 mbedtls_mpi_free( X: &W[1] ); mbedtls_mpi_free( X: &T ); mbedtls_mpi_free( X: &Apos );
2231 mbedtls_mpi_free( X: &WW );
2232
2233 if( prec_RR == NULL || prec_RR->p == NULL )
2234 mbedtls_mpi_free( X: &RR );
2235
2236 return( ret );
2237}
2238
2239/*
2240 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
2241 */
2242int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B )
2243{
2244 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2245 size_t lz, lzt;
2246 mbedtls_mpi TA, TB;
2247
2248 MPI_VALIDATE_RET( G != NULL );
2249 MPI_VALIDATE_RET( A != NULL );
2250 MPI_VALIDATE_RET( B != NULL );
2251
2252 mbedtls_mpi_init( X: &TA ); mbedtls_mpi_init( X: &TB );
2253
2254 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA, A ) );
2255 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, B ) );
2256
2257 lz = mbedtls_mpi_lsb( X: &TA );
2258 lzt = mbedtls_mpi_lsb( X: &TB );
2259
2260 /* The loop below gives the correct result when A==0 but not when B==0.
2261 * So have a special case for B==0. Leverage the fact that we just
2262 * calculated the lsb and lsb(B)==0 iff B is odd or 0 to make the test
2263 * slightly more efficient than cmp_int(). */
2264 if( lzt == 0 && mbedtls_mpi_get_bit( X: &TB, pos: 0 ) == 0 )
2265 {
2266 ret = mbedtls_mpi_copy( X: G, Y: A );
2267 goto cleanup;
2268 }
2269
2270 if( lzt < lz )
2271 lz = lzt;
2272
2273 TA.s = TB.s = 1;
2274
2275 /* We mostly follow the procedure described in HAC 14.54, but with some
2276 * minor differences:
2277 * - Sequences of multiplications or divisions by 2 are grouped into a
2278 * single shift operation.
2279 * - The procedure in HAC assumes that 0 < TB <= TA.
2280 * - The condition TB <= TA is not actually necessary for correctness.
2281 * TA and TB have symmetric roles except for the loop termination
2282 * condition, and the shifts at the beginning of the loop body
2283 * remove any significance from the ordering of TA vs TB before
2284 * the shifts.
2285 * - If TA = 0, the loop goes through 0 iterations and the result is
2286 * correctly TB.
2287 * - The case TB = 0 was short-circuited above.
2288 *
2289 * For the correctness proof below, decompose the original values of
2290 * A and B as
2291 * A = sa * 2^a * A' with A'=0 or A' odd, and sa = +-1
2292 * B = sb * 2^b * B' with B'=0 or B' odd, and sb = +-1
2293 * Then gcd(A, B) = 2^{min(a,b)} * gcd(A',B'),
2294 * and gcd(A',B') is odd or 0.
2295 *
2296 * At the beginning, we have TA = |A| and TB = |B| so gcd(A,B) = gcd(TA,TB).
2297 * The code maintains the following invariant:
2298 * gcd(A,B) = 2^k * gcd(TA,TB) for some k (I)
2299 */
2300
2301 /* Proof that the loop terminates:
2302 * At each iteration, either the right-shift by 1 is made on a nonzero
2303 * value and the nonnegative integer bitlen(TA) + bitlen(TB) decreases
2304 * by at least 1, or the right-shift by 1 is made on zero and then
2305 * TA becomes 0 which ends the loop (TB cannot be 0 if it is right-shifted
2306 * since in that case TB is calculated from TB-TA with the condition TB>TA).
2307 */
2308 while( mbedtls_mpi_cmp_int( X: &TA, z: 0 ) != 0 )
2309 {
2310 /* Divisions by 2 preserve the invariant (I). */
2311 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, mbedtls_mpi_lsb( &TA ) ) );
2312 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, mbedtls_mpi_lsb( &TB ) ) );
2313
2314 /* Set either TA or TB to |TA-TB|/2. Since TA and TB are both odd,
2315 * TA-TB is even so the division by 2 has an integer result.
2316 * Invariant (I) is preserved since any odd divisor of both TA and TB
2317 * also divides |TA-TB|/2, and any odd divisor of both TA and |TA-TB|/2
2318 * also divides TB, and any odd divisior of both TB and |TA-TB|/2 also
2319 * divides TA.
2320 */
2321 if( mbedtls_mpi_cmp_mpi( X: &TA, Y: &TB ) >= 0 )
2322 {
2323 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA, &TA, &TB ) );
2324 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA, 1 ) );
2325 }
2326 else
2327 {
2328 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB, &TB, &TA ) );
2329 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB, 1 ) );
2330 }
2331 /* Note that one of TA or TB is still odd. */
2332 }
2333
2334 /* By invariant (I), gcd(A,B) = 2^k * gcd(TA,TB) for some k.
2335 * At the loop exit, TA = 0, so gcd(TA,TB) = TB.
2336 * - If there was at least one loop iteration, then one of TA or TB is odd,
2337 * and TA = 0, so TB is odd and gcd(TA,TB) = gcd(A',B'). In this case,
2338 * lz = min(a,b) so gcd(A,B) = 2^lz * TB.
2339 * - If there was no loop iteration, then A was 0, and gcd(A,B) = B.
2340 * In this case, lz = 0 and B = TB so gcd(A,B) = B = 2^lz * TB as well.
2341 */
2342
2343 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB, lz ) );
2344 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G, &TB ) );
2345
2346cleanup:
2347
2348 mbedtls_mpi_free( X: &TA ); mbedtls_mpi_free( X: &TB );
2349
2350 return( ret );
2351}
2352
2353/* Fill X with n_bytes random bytes.
2354 * X must already have room for those bytes.
2355 * The ordering of the bytes returned from the RNG is suitable for
2356 * deterministic ECDSA (see RFC 6979 §3.3 and mbedtls_mpi_random()).
2357 * The size and sign of X are unchanged.
2358 * n_bytes must not be 0.
2359 */
2360static int mpi_fill_random_internal(
2361 mbedtls_mpi *X, size_t n_bytes,
2362 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
2363{
2364 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2365 const size_t limbs = CHARS_TO_LIMBS( n_bytes );
2366 const size_t overhead = ( limbs * ciL ) - n_bytes;
2367
2368 if( X->n < limbs )
2369 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2370
2371 memset( s: X->p, c: 0, n: overhead );
2372 memset( s: (unsigned char *) X->p + limbs * ciL, c: 0, n: ( X->n - limbs ) * ciL );
2373 MBEDTLS_MPI_CHK( f_rng( p_rng, (unsigned char *) X->p + overhead, n_bytes ) );
2374 mpi_bigendian_to_host( p: X->p, limbs );
2375
2376cleanup:
2377 return( ret );
2378}
2379
2380/*
2381 * Fill X with size bytes of random.
2382 *
2383 * Use a temporary bytes representation to make sure the result is the same
2384 * regardless of the platform endianness (useful when f_rng is actually
2385 * deterministic, eg for tests).
2386 */
2387int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
2388 int (*f_rng)(void *, unsigned char *, size_t),
2389 void *p_rng )
2390{
2391 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2392 size_t const limbs = CHARS_TO_LIMBS( size );
2393
2394 MPI_VALIDATE_RET( X != NULL );
2395 MPI_VALIDATE_RET( f_rng != NULL );
2396
2397 /* Ensure that target MPI has exactly the necessary number of limbs */
2398 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, limbs ) );
2399 if( size == 0 )
2400 return( 0 );
2401
2402 ret = mpi_fill_random_internal( X, n_bytes: size, f_rng, p_rng );
2403
2404cleanup:
2405 return( ret );
2406}
2407
2408int mbedtls_mpi_random( mbedtls_mpi *X,
2409 mbedtls_mpi_sint min,
2410 const mbedtls_mpi *N,
2411 int (*f_rng)(void *, unsigned char *, size_t),
2412 void *p_rng )
2413{
2414 int ret = MBEDTLS_ERR_MPI_BAD_INPUT_DATA;
2415 int count;
2416 unsigned lt_lower = 1, lt_upper = 0;
2417 size_t n_bits = mbedtls_mpi_bitlen( X: N );
2418 size_t n_bytes = ( n_bits + 7 ) / 8;
2419 mbedtls_mpi lower_bound;
2420
2421 if( min < 0 )
2422 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2423 if( mbedtls_mpi_cmp_int( X: N, z: min ) <= 0 )
2424 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2425
2426 /*
2427 * When min == 0, each try has at worst a probability 1/2 of failing
2428 * (the msb has a probability 1/2 of being 0, and then the result will
2429 * be < N), so after 30 tries failure probability is a most 2**(-30).
2430 *
2431 * When N is just below a power of 2, as is the case when generating
2432 * a random scalar on most elliptic curves, 1 try is enough with
2433 * overwhelming probability. When N is just above a power of 2,
2434 * as when generating a random scalar on secp224k1, each try has
2435 * a probability of failing that is almost 1/2.
2436 *
2437 * The probabilities are almost the same if min is nonzero but negligible
2438 * compared to N. This is always the case when N is crypto-sized, but
2439 * it's convenient to support small N for testing purposes. When N
2440 * is small, use a higher repeat count, otherwise the probability of
2441 * failure is macroscopic.
2442 */
2443 count = ( n_bytes > 4 ? 30 : 250 );
2444
2445 mbedtls_mpi_init( X: &lower_bound );
2446
2447 /* Ensure that target MPI has exactly the same number of limbs
2448 * as the upper bound, even if the upper bound has leading zeros.
2449 * This is necessary for the mbedtls_mpi_lt_mpi_ct() check. */
2450 MBEDTLS_MPI_CHK( mbedtls_mpi_resize_clear( X, N->n ) );
2451 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &lower_bound, N->n ) );
2452 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &lower_bound, min ) );
2453
2454 /*
2455 * Match the procedure given in RFC 6979 §3.3 (deterministic ECDSA)
2456 * when f_rng is a suitably parametrized instance of HMAC_DRBG:
2457 * - use the same byte ordering;
2458 * - keep the leftmost n_bits bits of the generated octet string;
2459 * - try until result is in the desired range.
2460 * This also avoids any bias, which is especially important for ECDSA.
2461 */
2462 do
2463 {
2464 MBEDTLS_MPI_CHK( mpi_fill_random_internal( X, n_bytes, f_rng, p_rng ) );
2465 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, 8 * n_bytes - n_bits ) );
2466
2467 if( --count == 0 )
2468 {
2469 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2470 goto cleanup;
2471 }
2472
2473 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, &lower_bound, &lt_lower ) );
2474 MBEDTLS_MPI_CHK( mbedtls_mpi_lt_mpi_ct( X, N, &lt_upper ) );
2475 }
2476 while( lt_lower != 0 || lt_upper == 0 );
2477
2478cleanup:
2479 mbedtls_mpi_free( X: &lower_bound );
2480 return( ret );
2481}
2482
2483/*
2484 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
2485 */
2486int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N )
2487{
2488 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2489 mbedtls_mpi G, TA, TU, U1, U2, TB, TV, V1, V2;
2490 MPI_VALIDATE_RET( X != NULL );
2491 MPI_VALIDATE_RET( A != NULL );
2492 MPI_VALIDATE_RET( N != NULL );
2493
2494 if( mbedtls_mpi_cmp_int( X: N, z: 1 ) <= 0 )
2495 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2496
2497 mbedtls_mpi_init( X: &TA ); mbedtls_mpi_init( X: &TU ); mbedtls_mpi_init( X: &U1 ); mbedtls_mpi_init( X: &U2 );
2498 mbedtls_mpi_init( X: &G ); mbedtls_mpi_init( X: &TB ); mbedtls_mpi_init( X: &TV );
2499 mbedtls_mpi_init( X: &V1 ); mbedtls_mpi_init( X: &V2 );
2500
2501 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G, A, N ) );
2502
2503 if( mbedtls_mpi_cmp_int( X: &G, z: 1 ) != 0 )
2504 {
2505 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2506 goto cleanup;
2507 }
2508
2509 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA, A, N ) );
2510 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU, &TA ) );
2511 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB, N ) );
2512 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV, N ) );
2513
2514 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1, 1 ) );
2515 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2, 0 ) );
2516 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1, 0 ) );
2517 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2, 1 ) );
2518
2519 do
2520 {
2521 while( ( TU.p[0] & 1 ) == 0 )
2522 {
2523 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU, 1 ) );
2524
2525 if( ( U1.p[0] & 1 ) != 0 || ( U2.p[0] & 1 ) != 0 )
2526 {
2527 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1, &U1, &TB ) );
2528 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &TA ) );
2529 }
2530
2531 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1, 1 ) );
2532 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2, 1 ) );
2533 }
2534
2535 while( ( TV.p[0] & 1 ) == 0 )
2536 {
2537 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV, 1 ) );
2538
2539 if( ( V1.p[0] & 1 ) != 0 || ( V2.p[0] & 1 ) != 0 )
2540 {
2541 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, &TB ) );
2542 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &TA ) );
2543 }
2544
2545 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1, 1 ) );
2546 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2, 1 ) );
2547 }
2548
2549 if( mbedtls_mpi_cmp_mpi( X: &TU, Y: &TV ) >= 0 )
2550 {
2551 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU, &TU, &TV ) );
2552 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1, &U1, &V1 ) );
2553 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2, &U2, &V2 ) );
2554 }
2555 else
2556 {
2557 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV, &TV, &TU ) );
2558 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, &U1 ) );
2559 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2, &V2, &U2 ) );
2560 }
2561 }
2562 while( mbedtls_mpi_cmp_int( X: &TU, z: 0 ) != 0 );
2563
2564 while( mbedtls_mpi_cmp_int( X: &V1, z: 0 ) < 0 )
2565 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1, &V1, N ) );
2566
2567 while( mbedtls_mpi_cmp_mpi( X: &V1, Y: N ) >= 0 )
2568 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1, &V1, N ) );
2569
2570 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X, &V1 ) );
2571
2572cleanup:
2573
2574 mbedtls_mpi_free( X: &TA ); mbedtls_mpi_free( X: &TU ); mbedtls_mpi_free( X: &U1 ); mbedtls_mpi_free( X: &U2 );
2575 mbedtls_mpi_free( X: &G ); mbedtls_mpi_free( X: &TB ); mbedtls_mpi_free( X: &TV );
2576 mbedtls_mpi_free( X: &V1 ); mbedtls_mpi_free( X: &V2 );
2577
2578 return( ret );
2579}
2580
2581#if defined(MBEDTLS_GENPRIME)
2582
2583static const int small_prime[] =
2584{
2585 3, 5, 7, 11, 13, 17, 19, 23,
2586 29, 31, 37, 41, 43, 47, 53, 59,
2587 61, 67, 71, 73, 79, 83, 89, 97,
2588 101, 103, 107, 109, 113, 127, 131, 137,
2589 139, 149, 151, 157, 163, 167, 173, 179,
2590 181, 191, 193, 197, 199, 211, 223, 227,
2591 229, 233, 239, 241, 251, 257, 263, 269,
2592 271, 277, 281, 283, 293, 307, 311, 313,
2593 317, 331, 337, 347, 349, 353, 359, 367,
2594 373, 379, 383, 389, 397, 401, 409, 419,
2595 421, 431, 433, 439, 443, 449, 457, 461,
2596 463, 467, 479, 487, 491, 499, 503, 509,
2597 521, 523, 541, 547, 557, 563, 569, 571,
2598 577, 587, 593, 599, 601, 607, 613, 617,
2599 619, 631, 641, 643, 647, 653, 659, 661,
2600 673, 677, 683, 691, 701, 709, 719, 727,
2601 733, 739, 743, 751, 757, 761, 769, 773,
2602 787, 797, 809, 811, 821, 823, 827, 829,
2603 839, 853, 857, 859, 863, 877, 881, 883,
2604 887, 907, 911, 919, 929, 937, 941, 947,
2605 953, 967, 971, 977, 983, 991, 997, -103
2606};
2607
2608/*
2609 * Small divisors test (X must be positive)
2610 *
2611 * Return values:
2612 * 0: no small factor (possible prime, more tests needed)
2613 * 1: certain prime
2614 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2615 * other negative: error
2616 */
2617static int mpi_check_small_factors( const mbedtls_mpi *X )
2618{
2619 int ret = 0;
2620 size_t i;
2621 mbedtls_mpi_uint r;
2622
2623 if( ( X->p[0] & 1 ) == 0 )
2624 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2625
2626 for( i = 0; small_prime[i] > 0; i++ )
2627 {
2628 if( mbedtls_mpi_cmp_int( X, small_prime[i] ) <= 0 )
2629 return( 1 );
2630
2631 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, small_prime[i] ) );
2632
2633 if( r == 0 )
2634 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2635 }
2636
2637cleanup:
2638 return( ret );
2639}
2640
2641/*
2642 * Miller-Rabin pseudo-primality test (HAC 4.24)
2643 */
2644static int mpi_miller_rabin( const mbedtls_mpi *X, size_t rounds,
2645 int (*f_rng)(void *, unsigned char *, size_t),
2646 void *p_rng )
2647{
2648 int ret, count;
2649 size_t i, j, k, s;
2650 mbedtls_mpi W, R, T, A, RR;
2651
2652 MPI_VALIDATE_RET( X != NULL );
2653 MPI_VALIDATE_RET( f_rng != NULL );
2654
2655 mbedtls_mpi_init( &W ); mbedtls_mpi_init( &R );
2656 mbedtls_mpi_init( &T ); mbedtls_mpi_init( &A );
2657 mbedtls_mpi_init( &RR );
2658
2659 /*
2660 * W = |X| - 1
2661 * R = W >> lsb( W )
2662 */
2663 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W, X, 1 ) );
2664 s = mbedtls_mpi_lsb( &W );
2665 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R, &W ) );
2666 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R, s ) );
2667
2668 for( i = 0; i < rounds; i++ )
2669 {
2670 /*
2671 * pick a random A, 1 < A < |X| - 1
2672 */
2673 count = 0;
2674 do {
2675 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A, X->n * ciL, f_rng, p_rng ) );
2676
2677 j = mbedtls_mpi_bitlen( &A );
2678 k = mbedtls_mpi_bitlen( &W );
2679 if (j > k) {
2680 A.p[A.n - 1] &= ( (mbedtls_mpi_uint) 1 << ( k - ( A.n - 1 ) * biL - 1 ) ) - 1;
2681 }
2682
2683 if (count++ > 30) {
2684 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2685 goto cleanup;
2686 }
2687
2688 } while ( mbedtls_mpi_cmp_mpi( &A, &W ) >= 0 ||
2689 mbedtls_mpi_cmp_int( &A, 1 ) <= 0 );
2690
2691 /*
2692 * A = A^R mod |X|
2693 */
2694 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A, &A, &R, X, &RR ) );
2695
2696 if( mbedtls_mpi_cmp_mpi( &A, &W ) == 0 ||
2697 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2698 continue;
2699
2700 j = 1;
2701 while( j < s && mbedtls_mpi_cmp_mpi( &A, &W ) != 0 )
2702 {
2703 /*
2704 * A = A * A mod |X|
2705 */
2706 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T, &A, &A ) );
2707 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A, &T, X ) );
2708
2709 if( mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2710 break;
2711
2712 j++;
2713 }
2714
2715 /*
2716 * not prime if A != |X| - 1 or A == 1
2717 */
2718 if( mbedtls_mpi_cmp_mpi( &A, &W ) != 0 ||
2719 mbedtls_mpi_cmp_int( &A, 1 ) == 0 )
2720 {
2721 ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2722 break;
2723 }
2724 }
2725
2726cleanup:
2727 mbedtls_mpi_free( &W ); mbedtls_mpi_free( &R );
2728 mbedtls_mpi_free( &T ); mbedtls_mpi_free( &A );
2729 mbedtls_mpi_free( &RR );
2730
2731 return( ret );
2732}
2733
2734/*
2735 * Pseudo-primality test: small factors, then Miller-Rabin
2736 */
2737int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
2738 int (*f_rng)(void *, unsigned char *, size_t),
2739 void *p_rng )
2740{
2741 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
2742 mbedtls_mpi XX;
2743 MPI_VALIDATE_RET( X != NULL );
2744 MPI_VALIDATE_RET( f_rng != NULL );
2745
2746 XX.s = 1;
2747 XX.n = X->n;
2748 XX.p = X->p;
2749
2750 if( mbedtls_mpi_cmp_int( &XX, 0 ) == 0 ||
2751 mbedtls_mpi_cmp_int( &XX, 1 ) == 0 )
2752 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
2753
2754 if( mbedtls_mpi_cmp_int( &XX, 2 ) == 0 )
2755 return( 0 );
2756
2757 if( ( ret = mpi_check_small_factors( &XX ) ) != 0 )
2758 {
2759 if( ret == 1 )
2760 return( 0 );
2761
2762 return( ret );
2763 }
2764
2765 return( mpi_miller_rabin( &XX, rounds, f_rng, p_rng ) );
2766}
2767
2768/*
2769 * Prime number generation
2770 *
2771 * To generate an RSA key in a way recommended by FIPS 186-4, both primes must
2772 * be either 1024 bits or 1536 bits long, and flags must contain
2773 * MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR.
2774 */
2775int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
2776 int (*f_rng)(void *, unsigned char *, size_t),
2777 void *p_rng )
2778{
2779#ifdef MBEDTLS_HAVE_INT64
2780// ceil(2^63.5)
2781#define CEIL_MAXUINT_DIV_SQRT2 0xb504f333f9de6485ULL
2782#else
2783// ceil(2^31.5)
2784#define CEIL_MAXUINT_DIV_SQRT2 0xb504f334U
2785#endif
2786 int ret = MBEDTLS_ERR_MPI_NOT_ACCEPTABLE;
2787 size_t k, n;
2788 int rounds;
2789 mbedtls_mpi_uint r;
2790 mbedtls_mpi Y;
2791
2792 MPI_VALIDATE_RET( X != NULL );
2793 MPI_VALIDATE_RET( f_rng != NULL );
2794
2795 if( nbits < 3 || nbits > MBEDTLS_MPI_MAX_BITS )
2796 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA );
2797
2798 mbedtls_mpi_init( &Y );
2799
2800 n = BITS_TO_LIMBS( nbits );
2801
2802 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_LOW_ERR ) == 0 )
2803 {
2804 /*
2805 * 2^-80 error probability, number of rounds chosen per HAC, table 4.4
2806 */
2807 rounds = ( ( nbits >= 1300 ) ? 2 : ( nbits >= 850 ) ? 3 :
2808 ( nbits >= 650 ) ? 4 : ( nbits >= 350 ) ? 8 :
2809 ( nbits >= 250 ) ? 12 : ( nbits >= 150 ) ? 18 : 27 );
2810 }
2811 else
2812 {
2813 /*
2814 * 2^-100 error probability, number of rounds computed based on HAC,
2815 * fact 4.48
2816 */
2817 rounds = ( ( nbits >= 1450 ) ? 4 : ( nbits >= 1150 ) ? 5 :
2818 ( nbits >= 1000 ) ? 6 : ( nbits >= 850 ) ? 7 :
2819 ( nbits >= 750 ) ? 8 : ( nbits >= 500 ) ? 13 :
2820 ( nbits >= 250 ) ? 28 : ( nbits >= 150 ) ? 40 : 51 );
2821 }
2822
2823 while( 1 )
2824 {
2825 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X, n * ciL, f_rng, p_rng ) );
2826 /* make sure generated number is at least (nbits-1)+0.5 bits (FIPS 186-4 §B.3.3 steps 4.4, 5.5) */
2827 if( X->p[n-1] < CEIL_MAXUINT_DIV_SQRT2 ) continue;
2828
2829 k = n * biL;
2830 if( k > nbits ) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X, k - nbits ) );
2831 X->p[0] |= 1;
2832
2833 if( ( flags & MBEDTLS_MPI_GEN_PRIME_FLAG_DH ) == 0 )
2834 {
2835 ret = mbedtls_mpi_is_prime_ext( X, rounds, f_rng, p_rng );
2836
2837 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2838 goto cleanup;
2839 }
2840 else
2841 {
2842 /*
2843 * An necessary condition for Y and X = 2Y + 1 to be prime
2844 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2845 * Make sure it is satisfied, while keeping X = 3 mod 4
2846 */
2847
2848 X->p[0] |= 2;
2849
2850 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r, X, 3 ) );
2851 if( r == 0 )
2852 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 8 ) );
2853 else if( r == 1 )
2854 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 4 ) );
2855
2856 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2857 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y, X ) );
2858 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y, 1 ) );
2859
2860 while( 1 )
2861 {
2862 /*
2863 * First, check small factors for X and Y
2864 * before doing Miller-Rabin on any of them
2865 */
2866 if( ( ret = mpi_check_small_factors( X ) ) == 0 &&
2867 ( ret = mpi_check_small_factors( &Y ) ) == 0 &&
2868 ( ret = mpi_miller_rabin( X, rounds, f_rng, p_rng ) )
2869 == 0 &&
2870 ( ret = mpi_miller_rabin( &Y, rounds, f_rng, p_rng ) )
2871 == 0 )
2872 goto cleanup;
2873
2874 if( ret != MBEDTLS_ERR_MPI_NOT_ACCEPTABLE )
2875 goto cleanup;
2876
2877 /*
2878 * Next candidates. We want to preserve Y = (X-1) / 2 and
2879 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2880 * so up Y by 6 and X by 12.
2881 */
2882 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X, X, 12 ) );
2883 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y, &Y, 6 ) );
2884 }
2885 }
2886 }
2887
2888cleanup:
2889
2890 mbedtls_mpi_free( &Y );
2891
2892 return( ret );
2893}
2894
2895#endif /* MBEDTLS_GENPRIME */
2896
2897#if defined(MBEDTLS_SELF_TEST)
2898
2899#define GCD_PAIR_COUNT 3
2900
2901static const int gcd_pairs[GCD_PAIR_COUNT][3] =
2902{
2903 { 693, 609, 21 },
2904 { 1764, 868, 28 },
2905 { 768454923, 542167814, 1 }
2906};
2907
2908/*
2909 * Checkup routine
2910 */
2911int mbedtls_mpi_self_test( int verbose )
2912{
2913 int ret, i;
2914 mbedtls_mpi A, E, N, X, Y, U, V;
2915
2916 mbedtls_mpi_init( &A ); mbedtls_mpi_init( &E ); mbedtls_mpi_init( &N ); mbedtls_mpi_init( &X );
2917 mbedtls_mpi_init( &Y ); mbedtls_mpi_init( &U ); mbedtls_mpi_init( &V );
2918
2919 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A, 16,
2920 "EFE021C2645FD1DC586E69184AF4A31E" \
2921 "D5F53E93B5F123FA41680867BA110131" \
2922 "944FE7952E2517337780CB0DB80E61AA" \
2923 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2924
2925 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E, 16,
2926 "B2E7EFD37075B9F03FF989C7C5051C20" \
2927 "34D2A323810251127E7BF8625A4F49A5" \
2928 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2929 "5B5C25763222FEFCCFC38B832366C29E" ) );
2930
2931 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N, 16,
2932 "0066A198186C18C10B2F5ED9B522752A" \
2933 "9830B69916E535C8F047518A889A43A5" \
2934 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2935
2936 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X, &A, &N ) );
2937
2938 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2939 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2940 "9E857EA95A03512E2BAE7391688D264A" \
2941 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2942 "8001B72E848A38CAE1C65F78E56ABDEF" \
2943 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2944 "ECF677152EF804370C1A305CAF3B5BF1" \
2945 "30879B56C61DE584A0F53A2447A51E" ) );
2946
2947 if( verbose != 0 )
2948 mbedtls_printf( " MPI test #1 (mul_mpi): " );
2949
2950 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 )
2951 {
2952 if( verbose != 0 )
2953 mbedtls_printf( "failed\n" );
2954
2955 ret = 1;
2956 goto cleanup;
2957 }
2958
2959 if( verbose != 0 )
2960 mbedtls_printf( "passed\n" );
2961
2962 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X, &Y, &A, &N ) );
2963
2964 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2965 "256567336059E52CAE22925474705F39A94" ) );
2966
2967 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V, 16,
2968 "6613F26162223DF488E9CD48CC132C7A" \
2969 "0AC93C701B001B092E4E5B9F73BCD27B" \
2970 "9EE50D0657C77F374E903CDFA4C642" ) );
2971
2972 if( verbose != 0 )
2973 mbedtls_printf( " MPI test #2 (div_mpi): " );
2974
2975 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 0 ||
2976 mbedtls_mpi_cmp_mpi( &Y, &V ) != 0 )
2977 {
2978 if( verbose != 0 )
2979 mbedtls_printf( "failed\n" );
2980
2981 ret = 1;
2982 goto cleanup;
2983 }
2984
2985 if( verbose != 0 )
2986 mbedtls_printf( "passed\n" );
2987
2988 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X, &A, &E, &N, NULL ) );
2989
2990 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
2991 "36E139AEA55215609D2816998ED020BB" \
2992 "BD96C37890F65171D948E9BC7CBAA4D9" \
2993 "325D24D6A3C12710F10A09FA08AB87" ) );
2994
2995 if( verbose != 0 )
2996 mbedtls_printf( " MPI test #3 (exp_mod): " );
2997
2998 if( mbedtls_mpi_cmp_mpi( &X, &U ) != 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_inv_mod( &X, &A, &N ) );
3011
3012 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U, 16,
3013 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
3014 "C3DBA76456363A10869622EAC2DD84EC" \
3015 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
3016
3017 if( verbose != 0 )
3018 mbedtls_printf( " MPI test #4 (inv_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 if( verbose != 0 )
3033 mbedtls_printf( " MPI test #5 (simple gcd): " );
3034
3035 for( i = 0; i < GCD_PAIR_COUNT; i++ )
3036 {
3037 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X, gcd_pairs[i][0] ) );
3038 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y, gcd_pairs[i][1] ) );
3039
3040 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A, &X, &Y ) );
3041
3042 if( mbedtls_mpi_cmp_int( &A, gcd_pairs[i][2] ) != 0 )
3043 {
3044 if( verbose != 0 )
3045 mbedtls_printf( "failed at %d\n", i );
3046
3047 ret = 1;
3048 goto cleanup;
3049 }
3050 }
3051
3052 if( verbose != 0 )
3053 mbedtls_printf( "passed\n" );
3054
3055cleanup:
3056
3057 if( ret != 0 && verbose != 0 )
3058 mbedtls_printf( "Unexpected error, return code = %08X\n", (unsigned int) ret );
3059
3060 mbedtls_mpi_free( &A ); mbedtls_mpi_free( &E ); mbedtls_mpi_free( &N ); mbedtls_mpi_free( &X );
3061 mbedtls_mpi_free( &Y ); mbedtls_mpi_free( &U ); mbedtls_mpi_free( &V );
3062
3063 if( verbose != 0 )
3064 mbedtls_printf( "\n" );
3065
3066 return( ret );
3067}
3068
3069#endif /* MBEDTLS_SELF_TEST */
3070
3071#endif /* MBEDTLS_BIGNUM_C */
3072