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