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