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