2 * Multi-precision integer library
4 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
5 * SPDX-License-Identifier: GPL-2.0
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License along
18 * with this program; if not, write to the Free Software Foundation, Inc.,
19 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 * This file is part of mbed TLS (https://tls.mbed.org)
25 * The following sources were referenced in the design of this Multi-precision
28 * [1] Handbook of Applied Cryptography - 1997
29 * Menezes, van Oorschot and Vanstone
31 * [2] Multi-Precision Math
33 * https://github.com/libtom/libtommath/blob/develop/tommath.pdf
35 * [3] GNU Multi-Precision Arithmetic Library
36 * https://gmplib.org/manual/index.html
40 #if !defined(MBEDTLS_CONFIG_FILE)
41 #include "mbedtls/config.h"
43 #include MBEDTLS_CONFIG_FILE
46 #if defined(MBEDTLS_BIGNUM_C)
48 #include "mbedtls/bignum.h"
49 #include "mbedtls/bn_mul.h"
51 #if defined(MBEDTLS_PLATFORM_C)
52 #include "mbedtls/platform.h"
56 #define mbedtls_printf printf
57 #define mbedtls_calloc calloc
58 #define mbedtls_free free
61 /* Implementation that should never be optimized out by the compiler */
62 static void mbedtls_mpi_zeroize( mbedtls_mpi_uint
*v
, size_t n
) {
63 volatile mbedtls_mpi_uint
*p
= v
; while( n
-- ) *p
++ = 0;
66 #define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
67 #define biL (ciL << 3) /* bits in limb */
68 #define biH (ciL << 2) /* half limb size */
70 #define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
73 * Convert between bits/chars and number of limbs
74 * Divide first in order to avoid potential overflows
76 #define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
77 #define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
82 void mbedtls_mpi_init( mbedtls_mpi
*X
)
95 void mbedtls_mpi_free( mbedtls_mpi
*X
)
102 mbedtls_mpi_zeroize( X
->p
, X
->n
);
103 mbedtls_free( X
->p
);
112 * Enlarge to the specified number of limbs
114 int mbedtls_mpi_grow( mbedtls_mpi
*X
, size_t nblimbs
)
118 if( nblimbs
> MBEDTLS_MPI_MAX_LIMBS
)
119 return( MBEDTLS_ERR_MPI_ALLOC_FAILED
);
123 if( ( p
= (mbedtls_mpi_uint
*)mbedtls_calloc( nblimbs
, ciL
) ) == NULL
)
124 return( MBEDTLS_ERR_MPI_ALLOC_FAILED
);
128 memcpy( p
, X
->p
, X
->n
* ciL
);
129 mbedtls_mpi_zeroize( X
->p
, X
->n
);
130 mbedtls_free( X
->p
);
141 * Resize down as much as possible,
142 * while keeping at least the specified number of limbs
144 int mbedtls_mpi_shrink( mbedtls_mpi
*X
, size_t nblimbs
)
149 /* Actually resize up in this case */
150 if( X
->n
<= nblimbs
)
151 return( mbedtls_mpi_grow( X
, nblimbs
) );
153 for( i
= X
->n
- 1; i
> 0; i
-- )
161 if( ( p
= (mbedtls_mpi_uint
*)mbedtls_calloc( i
, ciL
) ) == NULL
)
162 return( MBEDTLS_ERR_MPI_ALLOC_FAILED
);
166 memcpy( p
, X
->p
, i
* ciL
);
167 mbedtls_mpi_zeroize( X
->p
, X
->n
);
168 mbedtls_free( X
->p
);
178 * Copy the contents of Y into X
180 int mbedtls_mpi_copy( mbedtls_mpi
*X
, const mbedtls_mpi
*Y
)
190 mbedtls_mpi_free( X
);
194 for( i
= Y
->n
- 1; i
> 0; i
-- )
201 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, i
) );
203 memset( X
->p
, 0, X
->n
* ciL
);
204 memcpy( X
->p
, Y
->p
, i
* ciL
);
212 * Swap the contents of X and Y
214 void mbedtls_mpi_swap( mbedtls_mpi
*X
, mbedtls_mpi
*Y
)
218 memcpy( &T
, X
, sizeof( mbedtls_mpi
) );
219 memcpy( X
, Y
, sizeof( mbedtls_mpi
) );
220 memcpy( Y
, &T
, sizeof( mbedtls_mpi
) );
224 * Conditionally assign X = Y, without leaking information
225 * about whether the assignment was made or not.
226 * (Leaking information about the respective sizes of X and Y is ok however.)
228 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi
*X
, const mbedtls_mpi
*Y
, unsigned char assign
)
233 /* make sure assign is 0 or 1 in a time-constant manner */
234 assign
= (assign
| (unsigned char)-assign
) >> 7;
236 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, Y
->n
) );
238 X
->s
= X
->s
* ( 1 - assign
) + Y
->s
* assign
;
240 for( i
= 0; i
< Y
->n
; i
++ )
241 X
->p
[i
] = X
->p
[i
] * ( 1 - assign
) + Y
->p
[i
] * assign
;
243 for( ; i
< X
->n
; i
++ )
244 X
->p
[i
] *= ( 1 - assign
);
251 * Conditionally swap X and Y, without leaking information
252 * about whether the swap was made or not.
253 * Here it is not ok to simply swap the pointers, which whould lead to
254 * different memory access patterns when X and Y are used afterwards.
256 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi
*X
, mbedtls_mpi
*Y
, unsigned char swap
)
260 mbedtls_mpi_uint tmp
;
265 /* make sure swap is 0 or 1 in a time-constant manner */
266 swap
= (swap
| (unsigned char)-swap
) >> 7;
268 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, Y
->n
) );
269 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y
, X
->n
) );
272 X
->s
= X
->s
* ( 1 - swap
) + Y
->s
* swap
;
273 Y
->s
= Y
->s
* ( 1 - swap
) + s
* swap
;
276 for( i
= 0; i
< X
->n
; i
++ )
279 X
->p
[i
] = X
->p
[i
] * ( 1 - swap
) + Y
->p
[i
] * swap
;
280 Y
->p
[i
] = Y
->p
[i
] * ( 1 - swap
) + tmp
* swap
;
288 * Set value from integer
290 int mbedtls_mpi_lset( mbedtls_mpi
*X
, mbedtls_mpi_sint z
)
294 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, 1 ) );
295 memset( X
->p
, 0, X
->n
* ciL
);
297 X
->p
[0] = ( z
< 0 ) ? -z
: z
;
298 X
->s
= ( z
< 0 ) ? -1 : 1;
308 int mbedtls_mpi_get_bit( const mbedtls_mpi
*X
, size_t pos
)
310 if( X
->n
* biL
<= pos
)
313 return( ( X
->p
[pos
/ biL
] >> ( pos
% biL
) ) & 0x01 );
317 * Set a bit to a specific value of 0 or 1
319 int mbedtls_mpi_set_bit( mbedtls_mpi
*X
, size_t pos
, unsigned char val
)
322 size_t off
= pos
/ biL
;
323 size_t idx
= pos
% biL
;
325 if( val
!= 0 && val
!= 1 )
326 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
328 if( X
->n
* biL
<= pos
)
333 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, off
+ 1 ) );
336 X
->p
[off
] &= ~( (mbedtls_mpi_uint
) 0x01 << idx
);
337 X
->p
[off
] |= (mbedtls_mpi_uint
) val
<< idx
;
345 * Return the number of less significant zero-bits
347 size_t mbedtls_mpi_lsb( const mbedtls_mpi
*X
)
349 size_t i
, j
, count
= 0;
351 for( i
= 0; i
< X
->n
; i
++ )
352 for( j
= 0; j
< biL
; j
++, count
++ )
353 if( ( ( X
->p
[i
] >> j
) & 1 ) != 0 )
360 * Count leading zero bits in a given integer
362 static size_t mbedtls_clz( const mbedtls_mpi_uint x
)
365 mbedtls_mpi_uint mask
= (mbedtls_mpi_uint
) 1 << (biL
- 1);
367 for( j
= 0; j
< biL
; j
++ )
369 if( x
& mask
) break;
378 * Return the number of bits
380 size_t mbedtls_mpi_bitlen( const mbedtls_mpi
*X
)
387 for( i
= X
->n
- 1; i
> 0; i
-- )
391 j
= biL
- mbedtls_clz( X
->p
[i
] );
393 return( ( i
* biL
) + j
);
397 * Return the total size in bytes
399 size_t mbedtls_mpi_size( const mbedtls_mpi
*X
)
401 return( ( mbedtls_mpi_bitlen( X
) + 7 ) >> 3 );
405 * Convert an ASCII character to digit value
407 static int mpi_get_digit( mbedtls_mpi_uint
*d
, int radix
, char c
)
411 if( c
>= 0x30 && c
<= 0x39 ) *d
= c
- 0x30;
412 if( c
>= 0x41 && c
<= 0x46 ) *d
= c
- 0x37;
413 if( c
>= 0x61 && c
<= 0x66 ) *d
= c
- 0x57;
415 if( *d
>= (mbedtls_mpi_uint
) radix
)
416 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER
);
422 * Import from an ASCII string
424 int mbedtls_mpi_read_string( mbedtls_mpi
*X
, int radix
, const char *s
)
427 size_t i
, j
, slen
, n
;
431 if( radix
< 2 || radix
> 16 )
432 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
434 mbedtls_mpi_init( &T
);
440 if( slen
> MPI_SIZE_T_MAX
>> 2 )
441 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
443 n
= BITS_TO_LIMBS( slen
<< 2 );
445 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, n
) );
446 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
448 for( i
= slen
, j
= 0; i
> 0; i
--, j
++ )
450 if( i
== 1 && s
[i
- 1] == '-' )
456 MBEDTLS_MPI_CHK( mpi_get_digit( &d
, radix
, s
[i
- 1] ) );
457 X
->p
[j
/ ( 2 * ciL
)] |= d
<< ( ( j
% ( 2 * ciL
) ) << 2 );
462 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
464 for( i
= 0; i
< slen
; i
++ )
466 if( i
== 0 && s
[i
] == '-' )
472 MBEDTLS_MPI_CHK( mpi_get_digit( &d
, radix
, s
[i
] ) );
473 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T
, X
, radix
) );
477 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, &T
, d
) );
481 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X
, &T
, d
) );
488 mbedtls_mpi_free( &T
);
494 * Helper to write the digits high-order first
496 static int mpi_write_hlp( mbedtls_mpi
*X
, int radix
, char **p
)
501 if( radix
< 2 || radix
> 16 )
502 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
504 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r
, X
, radix
) );
505 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X
, NULL
, X
, radix
) );
507 if( mbedtls_mpi_cmp_int( X
, 0 ) != 0 )
508 MBEDTLS_MPI_CHK( mpi_write_hlp( X
, radix
, p
) );
511 *(*p
)++ = (char)( r
+ 0x30 );
513 *(*p
)++ = (char)( r
+ 0x37 );
521 * Export into an ASCII string
523 int mbedtls_mpi_write_string( const mbedtls_mpi
*X
, int radix
,
524 char *buf
, size_t buflen
, size_t *olen
)
531 if( radix
< 2 || radix
> 16 )
532 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
534 n
= mbedtls_mpi_bitlen( X
);
535 if( radix
>= 4 ) n
>>= 1;
536 if( radix
>= 16 ) n
>>= 1;
538 * Round up the buffer length to an even value to ensure that there is
539 * enough room for hexadecimal values that can be represented in an odd
542 n
+= 3 + ( ( n
+ 1 ) & 1 );
547 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL
);
551 mbedtls_mpi_init( &T
);
561 for( i
= X
->n
, k
= 0; i
> 0; i
-- )
563 for( j
= ciL
; j
> 0; j
-- )
565 c
= ( X
->p
[i
- 1] >> ( ( j
- 1 ) << 3) ) & 0xFF;
567 if( c
== 0 && k
== 0 && ( i
+ j
) != 2 )
570 *(p
++) = "0123456789ABCDEF" [c
/ 16];
571 *(p
++) = "0123456789ABCDEF" [c
% 16];
578 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T
, X
) );
583 MBEDTLS_MPI_CHK( mpi_write_hlp( &T
, radix
, &p
) );
591 mbedtls_mpi_free( &T
);
596 #if defined(MBEDTLS_FS_IO)
598 * Read X from an opened file
600 int mbedtls_mpi_read_file( mbedtls_mpi
*X
, int radix
, FILE *fin
)
606 * Buffer should have space for (short) label and decimal formatted MPI,
607 * newline characters and '\0'
609 char s
[ MBEDTLS_MPI_RW_BUFFER_SIZE
];
611 memset( s
, 0, sizeof( s
) );
612 if( fgets( s
, sizeof( s
) - 1, fin
) == NULL
)
613 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR
);
616 if( slen
== sizeof( s
) - 2 )
617 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL
);
619 if( slen
> 0 && s
[slen
- 1] == '\n' ) { slen
--; s
[slen
] = '\0'; }
620 if( slen
> 0 && s
[slen
- 1] == '\r' ) { slen
--; s
[slen
] = '\0'; }
624 if( mpi_get_digit( &d
, radix
, *p
) != 0 )
627 return( mbedtls_mpi_read_string( X
, radix
, p
+ 1 ) );
631 * Write X into an opened file (or stdout if fout == NULL)
633 int mbedtls_mpi_write_file( const char *p
, const mbedtls_mpi
*X
, int radix
, FILE *fout
)
636 size_t n
, slen
, plen
;
638 * Buffer should have space for (short) label and decimal formatted MPI,
639 * newline characters and '\0'
641 char s
[ MBEDTLS_MPI_RW_BUFFER_SIZE
];
643 memset( s
, 0, sizeof( s
) );
645 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X
, radix
, s
, sizeof( s
) - 2, &n
) );
647 if( p
== NULL
) p
= "";
656 if( fwrite( p
, 1, plen
, fout
) != plen
||
657 fwrite( s
, 1, slen
, fout
) != slen
)
658 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR
);
661 mbedtls_printf( "%s%s", p
, s
);
667 #endif /* MBEDTLS_FS_IO */
670 * Import X from unsigned binary data, big endian
672 int mbedtls_mpi_read_binary( mbedtls_mpi
*X
, const unsigned char *buf
, size_t buflen
)
677 for( n
= 0; n
< buflen
; n
++ )
681 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, CHARS_TO_LIMBS( buflen
- n
) ) );
682 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
684 for( i
= buflen
, j
= 0; i
> n
; i
--, j
++ )
685 X
->p
[j
/ ciL
] |= ((mbedtls_mpi_uint
) buf
[i
- 1]) << ((j
% ciL
) << 3);
693 * Export X into unsigned binary data, big endian
695 int mbedtls_mpi_write_binary( const mbedtls_mpi
*X
, unsigned char *buf
, size_t buflen
)
699 n
= mbedtls_mpi_size( X
);
702 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL
);
704 memset( buf
, 0, buflen
);
706 for( i
= buflen
- 1, j
= 0; n
> 0; i
--, j
++, n
-- )
707 buf
[i
] = (unsigned char)( X
->p
[j
/ ciL
] >> ((j
% ciL
) << 3) );
713 * Left-shift: X <<= count
715 int mbedtls_mpi_shift_l( mbedtls_mpi
*X
, size_t count
)
719 mbedtls_mpi_uint r0
= 0, r1
;
722 t1
= count
& (biL
- 1);
724 i
= mbedtls_mpi_bitlen( X
) + count
;
727 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, BITS_TO_LIMBS( i
) ) );
732 * shift by count / limb_size
736 for( i
= X
->n
; i
> v0
; i
-- )
737 X
->p
[i
- 1] = X
->p
[i
- v0
- 1];
744 * shift by count % limb_size
748 for( i
= v0
; i
< X
->n
; i
++ )
750 r1
= X
->p
[i
] >> (biL
- t1
);
763 * Right-shift: X >>= count
765 int mbedtls_mpi_shift_r( mbedtls_mpi
*X
, size_t count
)
768 mbedtls_mpi_uint r0
= 0, r1
;
771 v1
= count
& (biL
- 1);
773 if( v0
> X
->n
|| ( v0
== X
->n
&& v1
> 0 ) )
774 return mbedtls_mpi_lset( X
, 0 );
777 * shift by count / limb_size
781 for( i
= 0; i
< X
->n
- v0
; i
++ )
782 X
->p
[i
] = X
->p
[i
+ v0
];
784 for( ; i
< X
->n
; i
++ )
789 * shift by count % limb_size
793 for( i
= X
->n
; i
> 0; i
-- )
795 r1
= X
->p
[i
- 1] << (biL
- v1
);
806 * Compare unsigned values
808 int mbedtls_mpi_cmp_abs( const mbedtls_mpi
*X
, const mbedtls_mpi
*Y
)
812 for( i
= X
->n
; i
> 0; i
-- )
813 if( X
->p
[i
- 1] != 0 )
816 for( j
= Y
->n
; j
> 0; j
-- )
817 if( Y
->p
[j
- 1] != 0 )
820 if( i
== 0 && j
== 0 )
823 if( i
> j
) return( 1 );
824 if( j
> i
) return( -1 );
828 if( X
->p
[i
- 1] > Y
->p
[i
- 1] ) return( 1 );
829 if( X
->p
[i
- 1] < Y
->p
[i
- 1] ) return( -1 );
836 * Compare signed values
838 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi
*X
, const mbedtls_mpi
*Y
)
842 for( i
= X
->n
; i
> 0; i
-- )
843 if( X
->p
[i
- 1] != 0 )
846 for( j
= Y
->n
; j
> 0; j
-- )
847 if( Y
->p
[j
- 1] != 0 )
850 if( i
== 0 && j
== 0 )
853 if( i
> j
) return( X
->s
);
854 if( j
> i
) return( -Y
->s
);
856 if( X
->s
> 0 && Y
->s
< 0 ) return( 1 );
857 if( Y
->s
> 0 && X
->s
< 0 ) return( -1 );
861 if( X
->p
[i
- 1] > Y
->p
[i
- 1] ) return( X
->s
);
862 if( X
->p
[i
- 1] < Y
->p
[i
- 1] ) return( -X
->s
);
869 * Compare signed values
871 int mbedtls_mpi_cmp_int( const mbedtls_mpi
*X
, mbedtls_mpi_sint z
)
874 mbedtls_mpi_uint p
[1];
876 *p
= ( z
< 0 ) ? -z
: z
;
877 Y
.s
= ( z
< 0 ) ? -1 : 1;
881 return( mbedtls_mpi_cmp_mpi( X
, &Y
) );
885 * Unsigned addition: X = |A| + |B| (HAC 14.7)
887 int mbedtls_mpi_add_abs( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
891 mbedtls_mpi_uint
*o
, *p
, c
, tmp
;
895 const mbedtls_mpi
*T
= A
; A
= X
; B
= T
;
899 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, A
) );
902 * X should always be positive as a result of unsigned additions.
906 for( j
= B
->n
; j
> 0; j
-- )
907 if( B
->p
[j
- 1] != 0 )
910 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, j
) );
912 o
= B
->p
; p
= X
->p
; c
= 0;
915 * tmp is used because it might happen that p == o
917 for( i
= 0; i
< j
; i
++, o
++, p
++ )
920 *p
+= c
; c
= ( *p
< c
);
921 *p
+= tmp
; c
+= ( *p
< tmp
);
928 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, i
+ 1 ) );
932 *p
+= c
; c
= ( *p
< c
); i
++; p
++;
941 * Helper for mbedtls_mpi subtraction
943 static void mpi_sub_hlp( size_t n
, mbedtls_mpi_uint
*s
, mbedtls_mpi_uint
*d
)
946 mbedtls_mpi_uint c
, z
;
948 for( i
= c
= 0; i
< n
; i
++, s
++, d
++ )
950 z
= ( *d
< c
); *d
-= c
;
951 c
= ( *d
< *s
) + z
; *d
-= *s
;
956 z
= ( *d
< c
); *d
-= c
;
962 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
964 int mbedtls_mpi_sub_abs( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
970 if( mbedtls_mpi_cmp_abs( A
, B
) < 0 )
971 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE
);
973 mbedtls_mpi_init( &TB
);
977 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, B
) );
982 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, A
) );
985 * X should always be positive as a result of unsigned subtractions.
991 for( n
= B
->n
; n
> 0; n
-- )
992 if( B
->p
[n
- 1] != 0 )
995 mpi_sub_hlp( n
, B
->p
, X
->p
);
999 mbedtls_mpi_free( &TB
);
1005 * Signed addition: X = A + B
1007 int mbedtls_mpi_add_mpi( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1011 if( A
->s
* B
->s
< 0 )
1013 if( mbedtls_mpi_cmp_abs( A
, B
) >= 0 )
1015 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, A
, B
) );
1020 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, B
, A
) );
1026 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X
, A
, B
) );
1036 * Signed subtraction: X = A - B
1038 int mbedtls_mpi_sub_mpi( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1042 if( A
->s
* B
->s
> 0 )
1044 if( mbedtls_mpi_cmp_abs( A
, B
) >= 0 )
1046 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, A
, B
) );
1051 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, B
, A
) );
1057 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X
, A
, B
) );
1067 * Signed addition: X = A + b
1069 int mbedtls_mpi_add_int( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1072 mbedtls_mpi_uint p
[1];
1074 p
[0] = ( b
< 0 ) ? -b
: b
;
1075 _B
.s
= ( b
< 0 ) ? -1 : 1;
1079 return( mbedtls_mpi_add_mpi( X
, A
, &_B
) );
1083 * Signed subtraction: X = A - b
1085 int mbedtls_mpi_sub_int( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1088 mbedtls_mpi_uint p
[1];
1090 p
[0] = ( b
< 0 ) ? -b
: b
;
1091 _B
.s
= ( b
< 0 ) ? -1 : 1;
1095 return( mbedtls_mpi_sub_mpi( X
, A
, &_B
) );
1099 * Helper for mbedtls_mpi multiplication
1102 #if defined(__APPLE__) && defined(__arm__)
1104 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1105 * appears to need this to prevent bad ARM code generation at -O3.
1107 __attribute__ ((noinline
))
1109 void mpi_mul_hlp( size_t i
, mbedtls_mpi_uint
*s
, mbedtls_mpi_uint
*d
, mbedtls_mpi_uint b
)
1111 mbedtls_mpi_uint c
= 0, t
= 0;
1113 #if defined(MULADDC_HUIT)
1114 for( ; i
>= 8; i
-= 8 )
1127 #else /* MULADDC_HUIT */
1128 for( ; i
>= 16; i
-= 16 )
1131 MULADDC_CORE MULADDC_CORE
1132 MULADDC_CORE MULADDC_CORE
1133 MULADDC_CORE MULADDC_CORE
1134 MULADDC_CORE MULADDC_CORE
1136 MULADDC_CORE MULADDC_CORE
1137 MULADDC_CORE MULADDC_CORE
1138 MULADDC_CORE MULADDC_CORE
1139 MULADDC_CORE MULADDC_CORE
1143 for( ; i
>= 8; i
-= 8 )
1146 MULADDC_CORE MULADDC_CORE
1147 MULADDC_CORE MULADDC_CORE
1149 MULADDC_CORE MULADDC_CORE
1150 MULADDC_CORE MULADDC_CORE
1160 #endif /* MULADDC_HUIT */
1165 *d
+= c
; c
= ( *d
< c
); d
++;
1171 * Baseline multiplication: X = A * B (HAC 14.12)
1173 int mbedtls_mpi_mul_mpi( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1179 mbedtls_mpi_init( &TA
); mbedtls_mpi_init( &TB
);
1181 if( X
== A
) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA
, A
) ); A
= &TA
; }
1182 if( X
== B
) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, B
) ); B
= &TB
; }
1184 for( i
= A
->n
; i
> 0; i
-- )
1185 if( A
->p
[i
- 1] != 0 )
1188 for( j
= B
->n
; j
> 0; j
-- )
1189 if( B
->p
[j
- 1] != 0 )
1192 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, i
+ j
) );
1193 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
1195 for( i
++; j
> 0; j
-- )
1196 mpi_mul_hlp( i
- 1, A
->p
, X
->p
+ j
- 1, B
->p
[j
- 1] );
1202 mbedtls_mpi_free( &TB
); mbedtls_mpi_free( &TA
);
1208 * Baseline multiplication: X = A * b
1210 int mbedtls_mpi_mul_int( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, mbedtls_mpi_uint b
)
1213 mbedtls_mpi_uint p
[1];
1220 return( mbedtls_mpi_mul_mpi( X
, A
, &_B
) );
1224 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1225 * mbedtls_mpi_uint divisor, d
1227 static mbedtls_mpi_uint
mbedtls_int_div_int( mbedtls_mpi_uint u1
,
1228 mbedtls_mpi_uint u0
, mbedtls_mpi_uint d
, mbedtls_mpi_uint
*r
)
1230 #if defined(MBEDTLS_HAVE_UDBL)
1231 mbedtls_t_udbl dividend
, quotient
;
1233 const mbedtls_mpi_uint radix
= (mbedtls_mpi_uint
) 1 << biH
;
1234 const mbedtls_mpi_uint uint_halfword_mask
= ( (mbedtls_mpi_uint
) 1 << biH
) - 1;
1235 mbedtls_mpi_uint d0
, d1
, q0
, q1
, rAX
, r0
, quotient
;
1236 mbedtls_mpi_uint u0_msw
, u0_lsw
;
1241 * Check for overflow
1243 if( 0 == d
|| u1
>= d
)
1245 if (r
!= NULL
) *r
= ~0;
1250 #if defined(MBEDTLS_HAVE_UDBL)
1251 dividend
= (mbedtls_t_udbl
) u1
<< biL
;
1252 dividend
|= (mbedtls_t_udbl
) u0
;
1253 quotient
= dividend
/ d
;
1254 if( quotient
> ( (mbedtls_t_udbl
) 1 << biL
) - 1 )
1255 quotient
= ( (mbedtls_t_udbl
) 1 << biL
) - 1;
1258 *r
= (mbedtls_mpi_uint
)( dividend
- (quotient
* d
) );
1260 return (mbedtls_mpi_uint
) quotient
;
1264 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1265 * Vol. 2 - Seminumerical Algorithms, Knuth
1269 * Normalize the divisor, d, and dividend, u0, u1
1271 s
= mbedtls_clz( d
);
1275 u1
|= ( u0
>> ( biL
- s
) ) & ( -(mbedtls_mpi_sint
)s
>> ( biL
- 1 ) );
1279 d0
= d
& uint_halfword_mask
;
1282 u0_lsw
= u0
& uint_halfword_mask
;
1285 * Find the first quotient and remainder
1290 while( q1
>= radix
|| ( q1
* d0
> radix
* r0
+ u0_msw
) )
1295 if ( r0
>= radix
) break;
1298 rAX
= ( u1
* radix
) + ( u0_msw
- q1
* d
);
1302 while( q0
>= radix
|| ( q0
* d0
> radix
* r0
+ u0_lsw
) )
1307 if ( r0
>= radix
) break;
1311 *r
= ( rAX
* radix
+ u0_lsw
- q0
* d
) >> s
;
1313 quotient
= q1
* radix
+ q0
;
1320 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1322 int mbedtls_mpi_div_mpi( mbedtls_mpi
*Q
, mbedtls_mpi
*R
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1326 mbedtls_mpi X
, Y
, Z
, T1
, T2
;
1328 if( mbedtls_mpi_cmp_int( B
, 0 ) == 0 )
1329 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO
);
1331 mbedtls_mpi_init( &X
); mbedtls_mpi_init( &Y
); mbedtls_mpi_init( &Z
);
1332 mbedtls_mpi_init( &T1
); mbedtls_mpi_init( &T2
);
1334 if( mbedtls_mpi_cmp_abs( A
, B
) < 0 )
1336 if( Q
!= NULL
) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q
, 0 ) );
1337 if( R
!= NULL
) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R
, A
) );
1341 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X
, A
) );
1342 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y
, B
) );
1345 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z
, A
->n
+ 2 ) );
1346 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z
, 0 ) );
1347 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1
, 2 ) );
1348 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2
, 3 ) );
1350 k
= mbedtls_mpi_bitlen( &Y
) % biL
;
1354 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X
, k
) );
1355 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y
, k
) );
1361 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y
, biL
* ( n
- t
) ) );
1363 while( mbedtls_mpi_cmp_mpi( &X
, &Y
) >= 0 )
1366 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X
, &X
, &Y
) );
1368 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y
, biL
* ( n
- t
) ) );
1370 for( i
= n
; i
> t
; i
-- )
1372 if( X
.p
[i
] >= Y
.p
[t
] )
1373 Z
.p
[i
- t
- 1] = ~0;
1376 Z
.p
[i
- t
- 1] = mbedtls_int_div_int( X
.p
[i
], X
.p
[i
- 1],
1385 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1
, 0 ) );
1386 T1
.p
[0] = ( t
< 1 ) ? 0 : Y
.p
[t
- 1];
1388 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1
, &T1
, Z
.p
[i
- t
- 1] ) );
1390 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2
, 0 ) );
1391 T2
.p
[0] = ( i
< 2 ) ? 0 : X
.p
[i
- 2];
1392 T2
.p
[1] = ( i
< 1 ) ? 0 : X
.p
[i
- 1];
1395 while( mbedtls_mpi_cmp_mpi( &T1
, &T2
) > 0 );
1397 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1
, &Y
, Z
.p
[i
- t
- 1] ) );
1398 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1
, biL
* ( i
- t
- 1 ) ) );
1399 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X
, &X
, &T1
) );
1401 if( mbedtls_mpi_cmp_int( &X
, 0 ) < 0 )
1403 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1
, &Y
) );
1404 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1
, biL
* ( i
- t
- 1 ) ) );
1405 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X
, &X
, &T1
) );
1412 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q
, &Z
) );
1418 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X
, k
) );
1420 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R
, &X
) );
1422 if( mbedtls_mpi_cmp_int( R
, 0 ) == 0 )
1428 mbedtls_mpi_free( &X
); mbedtls_mpi_free( &Y
); mbedtls_mpi_free( &Z
);
1429 mbedtls_mpi_free( &T1
); mbedtls_mpi_free( &T2
);
1435 * Division by int: A = Q * b + R
1437 int mbedtls_mpi_div_int( mbedtls_mpi
*Q
, mbedtls_mpi
*R
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1440 mbedtls_mpi_uint p
[1];
1442 p
[0] = ( b
< 0 ) ? -b
: b
;
1443 _B
.s
= ( b
< 0 ) ? -1 : 1;
1447 return( mbedtls_mpi_div_mpi( Q
, R
, A
, &_B
) );
1451 * Modulo: R = A mod B
1453 int mbedtls_mpi_mod_mpi( mbedtls_mpi
*R
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1457 if( mbedtls_mpi_cmp_int( B
, 0 ) < 0 )
1458 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE
);
1460 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL
, R
, A
, B
) );
1462 while( mbedtls_mpi_cmp_int( R
, 0 ) < 0 )
1463 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R
, R
, B
) );
1465 while( mbedtls_mpi_cmp_mpi( R
, B
) >= 0 )
1466 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R
, R
, B
) );
1474 * Modulo: r = A mod b
1476 int mbedtls_mpi_mod_int( mbedtls_mpi_uint
*r
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1479 mbedtls_mpi_uint x
, y
, z
;
1482 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO
);
1485 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE
);
1488 * handle trivial cases
1505 for( i
= A
->n
, y
= 0; i
> 0; i
-- )
1508 y
= ( y
<< biH
) | ( x
>> biH
);
1513 y
= ( y
<< biH
) | ( x
>> biH
);
1519 * If A is negative, then the current y represents a negative value.
1520 * Flipping it to the positive side.
1522 if( A
->s
< 0 && y
!= 0 )
1531 * Fast Montgomery initialization (thanks to Tom St Denis)
1533 static void mpi_montg_init( mbedtls_mpi_uint
*mm
, const mbedtls_mpi
*N
)
1535 mbedtls_mpi_uint x
, m0
= N
->p
[0];
1539 x
+= ( ( m0
+ 2 ) & 4 ) << 1;
1541 for( i
= biL
; i
>= 8; i
/= 2 )
1542 x
*= ( 2 - ( m0
* x
) );
1548 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1550 static int mpi_montmul( mbedtls_mpi
*A
, const mbedtls_mpi
*B
, const mbedtls_mpi
*N
, mbedtls_mpi_uint mm
,
1551 const mbedtls_mpi
*T
)
1554 mbedtls_mpi_uint u0
, u1
, *d
;
1556 if( T
->n
< N
->n
+ 1 || T
->p
== NULL
)
1557 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1559 memset( T
->p
, 0, T
->n
* ciL
);
1563 m
= ( B
->n
< n
) ? B
->n
: n
;
1565 for( i
= 0; i
< n
; i
++ )
1568 * T = (T + u0*B + u1*N) / 2^biL
1571 u1
= ( d
[0] + u0
* B
->p
[0] ) * mm
;
1573 mpi_mul_hlp( m
, B
->p
, d
, u0
);
1574 mpi_mul_hlp( n
, N
->p
, d
, u1
);
1576 *d
++ = u0
; d
[n
+ 1] = 0;
1579 memcpy( A
->p
, d
, ( n
+ 1 ) * ciL
);
1581 if( mbedtls_mpi_cmp_abs( A
, N
) >= 0 )
1582 mpi_sub_hlp( n
, N
->p
, A
->p
);
1584 /* prevent timing attacks */
1585 mpi_sub_hlp( n
, A
->p
, T
->p
);
1591 * Montgomery reduction: A = A * R^-1 mod N
1593 static int mpi_montred( mbedtls_mpi
*A
, const mbedtls_mpi
*N
, mbedtls_mpi_uint mm
, const mbedtls_mpi
*T
)
1595 mbedtls_mpi_uint z
= 1;
1598 U
.n
= U
.s
= (int) z
;
1601 return( mpi_montmul( A
, &U
, N
, mm
, T
) );
1605 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1607 int mbedtls_mpi_exp_mod( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*E
, const mbedtls_mpi
*N
, mbedtls_mpi
*_RR
)
1610 size_t wbits
, wsize
, one
= 1;
1611 size_t i
, j
, nblimbs
;
1612 size_t bufsize
, nbits
;
1613 mbedtls_mpi_uint ei
, mm
, state
;
1615 mbedtls_mpi RR
, T
, W
[ 2 << MBEDTLS_MPI_WINDOW_SIZE
], Apos
;
1616 } *ctx
= kzalloc(sizeof(*ctx
), GFP_KERNEL
);
1622 if( mbedtls_mpi_cmp_int( N
, 0 ) < 0 || ( N
->p
[0] & 1 ) == 0 ) {
1623 ret
= ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1627 if( mbedtls_mpi_cmp_int( E
, 0 ) < 0 ) {
1628 ret
= ( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1633 * Init temps and window size
1635 mpi_montg_init( &mm
, N
);
1636 mbedtls_mpi_init( &ctx
->RR
); mbedtls_mpi_init( &ctx
->T
);
1637 mbedtls_mpi_init( &ctx
->Apos
);
1638 memset( ctx
->W
, 0, sizeof( ctx
->W
) );
1640 i
= mbedtls_mpi_bitlen( E
);
1642 wsize
= ( i
> 671 ) ? 6 : ( i
> 239 ) ? 5 :
1643 ( i
> 79 ) ? 4 : ( i
> 23 ) ? 3 : 1;
1645 if( wsize
> MBEDTLS_MPI_WINDOW_SIZE
)
1646 wsize
= MBEDTLS_MPI_WINDOW_SIZE
;
1649 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, j
) );
1650 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &ctx
->W
[1], j
) );
1651 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &ctx
->T
, j
* 2 ) );
1654 * Compensate for negative A (and correct at the end)
1656 neg
= ( A
->s
== -1 );
1659 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &ctx
->Apos
, A
) );
1665 * If 1st call, pre-compute R^2 mod N
1667 if( _RR
== NULL
|| _RR
->p
== NULL
)
1669 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &ctx
->RR
, 1 ) );
1670 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &ctx
->RR
, N
->n
* 2 * biL
) );
1671 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx
->RR
, &ctx
->RR
, N
) );
1674 memcpy( _RR
, &ctx
->RR
, sizeof( mbedtls_mpi
) );
1677 memcpy( &ctx
->RR
, _RR
, sizeof( mbedtls_mpi
) );
1680 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1682 if( mbedtls_mpi_cmp_mpi( A
, N
) >= 0 )
1683 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx
->W
[1], A
, N
) );
1685 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &ctx
->W
[1], A
) );
1687 MBEDTLS_MPI_CHK( mpi_montmul( &ctx
->W
[1], &ctx
->RR
, N
, mm
, &ctx
->T
) );
1690 * X = R^2 * R^-1 mod N = R mod N
1692 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, &ctx
->RR
) );
1693 MBEDTLS_MPI_CHK( mpi_montred( X
, N
, mm
, &ctx
->T
) );
1698 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1700 j
= one
<< ( wsize
- 1 );
1702 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &ctx
->W
[j
], N
->n
+ 1 ) );
1703 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &ctx
->W
[j
], &ctx
->W
[1] ) );
1705 for( i
= 0; i
< wsize
- 1; i
++ )
1706 MBEDTLS_MPI_CHK( mpi_montmul( &ctx
->W
[j
], &ctx
->W
[j
], N
, mm
, &ctx
->T
) );
1709 * W[i] = W[i - 1] * W[1]
1711 for( i
= j
+ 1; i
< ( one
<< wsize
); i
++ )
1713 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &ctx
->W
[i
], N
->n
+ 1 ) );
1714 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &ctx
->W
[i
], &ctx
->W
[i
- 1] ) );
1716 MBEDTLS_MPI_CHK( mpi_montmul( &ctx
->W
[i
], &ctx
->W
[1], N
, mm
, &ctx
->T
) );
1735 bufsize
= sizeof( mbedtls_mpi_uint
) << 3;
1740 ei
= (E
->p
[nblimbs
] >> bufsize
) & 1;
1745 if( ei
== 0 && state
== 0 )
1748 if( ei
== 0 && state
== 1 )
1751 * out of window, square X
1753 MBEDTLS_MPI_CHK( mpi_montmul( X
, X
, N
, mm
, &ctx
->T
) );
1758 * add ei to current window
1763 wbits
|= ( ei
<< ( wsize
- nbits
) );
1765 if( nbits
== wsize
)
1768 * X = X^wsize R^-1 mod N
1770 for( i
= 0; i
< wsize
; i
++ )
1771 MBEDTLS_MPI_CHK( mpi_montmul( X
, X
, N
, mm
, &ctx
->T
) );
1774 * X = X * W[wbits] R^-1 mod N
1776 MBEDTLS_MPI_CHK( mpi_montmul( X
, &ctx
->W
[wbits
], N
, mm
, &ctx
->T
) );
1785 * process the remaining bits
1787 for( i
= 0; i
< nbits
; i
++ )
1789 MBEDTLS_MPI_CHK( mpi_montmul( X
, X
, N
, mm
, &ctx
->T
) );
1793 if( ( wbits
& ( one
<< wsize
) ) != 0 )
1794 MBEDTLS_MPI_CHK( mpi_montmul( X
, &ctx
->W
[1], N
, mm
, &ctx
->T
) );
1798 * X = A^E * R * R^-1 mod N = A^E mod N
1800 MBEDTLS_MPI_CHK( mpi_montred( X
, N
, mm
, &ctx
->T
) );
1802 if( neg
&& E
->n
!= 0 && ( E
->p
[0] & 1 ) != 0 )
1805 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X
, N
, X
) );
1810 for( i
= ( one
<< ( wsize
- 1 ) ); i
< ( one
<< wsize
); i
++ )
1811 mbedtls_mpi_free( &ctx
->W
[i
] );
1813 mbedtls_mpi_free( &ctx
->W
[1] ); mbedtls_mpi_free( &ctx
->T
); mbedtls_mpi_free( &ctx
->Apos
);
1815 if( _RR
== NULL
|| _RR
->p
== NULL
)
1816 mbedtls_mpi_free( &ctx
->RR
);
1824 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1826 int mbedtls_mpi_gcd( mbedtls_mpi
*G
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1830 mbedtls_mpi TG
, TA
, TB
;
1832 mbedtls_mpi_init( &TG
); mbedtls_mpi_init( &TA
); mbedtls_mpi_init( &TB
);
1834 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA
, A
) );
1835 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, B
) );
1837 lz
= mbedtls_mpi_lsb( &TA
);
1838 lzt
= mbedtls_mpi_lsb( &TB
);
1843 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA
, lz
) );
1844 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB
, lz
) );
1848 while( mbedtls_mpi_cmp_int( &TA
, 0 ) != 0 )
1850 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA
, mbedtls_mpi_lsb( &TA
) ) );
1851 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB
, mbedtls_mpi_lsb( &TB
) ) );
1853 if( mbedtls_mpi_cmp_mpi( &TA
, &TB
) >= 0 )
1855 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA
, &TA
, &TB
) );
1856 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA
, 1 ) );
1860 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB
, &TB
, &TA
) );
1861 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB
, 1 ) );
1865 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB
, lz
) );
1866 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G
, &TB
) );
1870 mbedtls_mpi_free( &TG
); mbedtls_mpi_free( &TA
); mbedtls_mpi_free( &TB
);
1876 * Fill X with size bytes of random.
1878 * Use a temporary bytes representation to make sure the result is the same
1879 * regardless of the platform endianness (useful when f_rng is actually
1880 * deterministic, eg for tests).
1882 int mbedtls_mpi_fill_random( mbedtls_mpi
*X
, size_t size
,
1883 int (*f_rng
)(void *, unsigned char *, size_t),
1887 unsigned char buf
[MBEDTLS_MPI_MAX_SIZE
];
1889 if( size
> MBEDTLS_MPI_MAX_SIZE
)
1890 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1892 MBEDTLS_MPI_CHK( f_rng( p_rng
, buf
, size
) );
1893 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X
, buf
, size
) );
1900 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1902 int mbedtls_mpi_inv_mod( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*N
)
1905 mbedtls_mpi G
, TA
, TU
, U1
, U2
, TB
, TV
, V1
, V2
;
1907 if( mbedtls_mpi_cmp_int( N
, 1 ) <= 0 )
1908 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1910 mbedtls_mpi_init( &TA
); mbedtls_mpi_init( &TU
); mbedtls_mpi_init( &U1
); mbedtls_mpi_init( &U2
);
1911 mbedtls_mpi_init( &G
); mbedtls_mpi_init( &TB
); mbedtls_mpi_init( &TV
);
1912 mbedtls_mpi_init( &V1
); mbedtls_mpi_init( &V2
);
1914 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G
, A
, N
) );
1916 if( mbedtls_mpi_cmp_int( &G
, 1 ) != 0 )
1918 ret
= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
;
1922 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA
, A
, N
) );
1923 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU
, &TA
) );
1924 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, N
) );
1925 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV
, N
) );
1927 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1
, 1 ) );
1928 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2
, 0 ) );
1929 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1
, 0 ) );
1930 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2
, 1 ) );
1934 while( ( TU
.p
[0] & 1 ) == 0 )
1936 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU
, 1 ) );
1938 if( ( U1
.p
[0] & 1 ) != 0 || ( U2
.p
[0] & 1 ) != 0 )
1940 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1
, &U1
, &TB
) );
1941 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2
, &U2
, &TA
) );
1944 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1
, 1 ) );
1945 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2
, 1 ) );
1948 while( ( TV
.p
[0] & 1 ) == 0 )
1950 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV
, 1 ) );
1952 if( ( V1
.p
[0] & 1 ) != 0 || ( V2
.p
[0] & 1 ) != 0 )
1954 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1
, &V1
, &TB
) );
1955 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2
, &V2
, &TA
) );
1958 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1
, 1 ) );
1959 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2
, 1 ) );
1962 if( mbedtls_mpi_cmp_mpi( &TU
, &TV
) >= 0 )
1964 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU
, &TU
, &TV
) );
1965 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1
, &U1
, &V1
) );
1966 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2
, &U2
, &V2
) );
1970 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV
, &TV
, &TU
) );
1971 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1
, &V1
, &U1
) );
1972 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2
, &V2
, &U2
) );
1975 while( mbedtls_mpi_cmp_int( &TU
, 0 ) != 0 );
1977 while( mbedtls_mpi_cmp_int( &V1
, 0 ) < 0 )
1978 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1
, &V1
, N
) );
1980 while( mbedtls_mpi_cmp_mpi( &V1
, N
) >= 0 )
1981 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1
, &V1
, N
) );
1983 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, &V1
) );
1987 mbedtls_mpi_free( &TA
); mbedtls_mpi_free( &TU
); mbedtls_mpi_free( &U1
); mbedtls_mpi_free( &U2
);
1988 mbedtls_mpi_free( &G
); mbedtls_mpi_free( &TB
); mbedtls_mpi_free( &TV
);
1989 mbedtls_mpi_free( &V1
); mbedtls_mpi_free( &V2
);
1994 #if defined(MBEDTLS_GENPRIME)
1996 static const int small_prime
[] =
1998 3, 5, 7, 11, 13, 17, 19, 23,
1999 29, 31, 37, 41, 43, 47, 53, 59,
2000 61, 67, 71, 73, 79, 83, 89, 97,
2001 101, 103, 107, 109, 113, 127, 131, 137,
2002 139, 149, 151, 157, 163, 167, 173, 179,
2003 181, 191, 193, 197, 199, 211, 223, 227,
2004 229, 233, 239, 241, 251, 257, 263, 269,
2005 271, 277, 281, 283, 293, 307, 311, 313,
2006 317, 331, 337, 347, 349, 353, 359, 367,
2007 373, 379, 383, 389, 397, 401, 409, 419,
2008 421, 431, 433, 439, 443, 449, 457, 461,
2009 463, 467, 479, 487, 491, 499, 503, 509,
2010 521, 523, 541, 547, 557, 563, 569, 571,
2011 577, 587, 593, 599, 601, 607, 613, 617,
2012 619, 631, 641, 643, 647, 653, 659, 661,
2013 673, 677, 683, 691, 701, 709, 719, 727,
2014 733, 739, 743, 751, 757, 761, 769, 773,
2015 787, 797, 809, 811, 821, 823, 827, 829,
2016 839, 853, 857, 859, 863, 877, 881, 883,
2017 887, 907, 911, 919, 929, 937, 941, 947,
2018 953, 967, 971, 977, 983, 991, 997, -103
2022 * Small divisors test (X must be positive)
2025 * 0: no small factor (possible prime, more tests needed)
2027 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2028 * other negative: error
2030 static int mpi_check_small_factors( const mbedtls_mpi
*X
)
2036 if( ( X
->p
[0] & 1 ) == 0 )
2037 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
);
2039 for( i
= 0; small_prime
[i
] > 0; i
++ )
2041 if( mbedtls_mpi_cmp_int( X
, small_prime
[i
] ) <= 0 )
2044 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r
, X
, small_prime
[i
] ) );
2047 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
);
2055 * Miller-Rabin pseudo-primality test (HAC 4.24)
2057 static int mpi_miller_rabin( const mbedtls_mpi
*X
,
2058 int (*f_rng
)(void *, unsigned char *, size_t),
2062 size_t i
, j
, k
, n
, s
;
2063 mbedtls_mpi W
, R
, T
, A
, RR
;
2065 mbedtls_mpi_init( &W
); mbedtls_mpi_init( &R
); mbedtls_mpi_init( &T
); mbedtls_mpi_init( &A
);
2066 mbedtls_mpi_init( &RR
);
2072 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W
, X
, 1 ) );
2073 s
= mbedtls_mpi_lsb( &W
);
2074 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
, &W
) );
2075 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R
, s
) );
2077 i
= mbedtls_mpi_bitlen( X
);
2081 n
= ( ( i
>= 1300 ) ? 2 : ( i
>= 850 ) ? 3 :
2082 ( i
>= 650 ) ? 4 : ( i
>= 350 ) ? 8 :
2083 ( i
>= 250 ) ? 12 : ( i
>= 150 ) ? 18 : 27 );
2085 for( i
= 0; i
< n
; i
++ )
2088 * pick a random A, 1 < A < |X| - 1
2090 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A
, X
->n
* ciL
, f_rng
, p_rng
) );
2092 if( mbedtls_mpi_cmp_mpi( &A
, &W
) >= 0 )
2094 j
= mbedtls_mpi_bitlen( &A
) - mbedtls_mpi_bitlen( &W
);
2095 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A
, j
+ 1 ) );
2101 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A
, X
->n
* ciL
, f_rng
, p_rng
) );
2103 j
= mbedtls_mpi_bitlen( &A
);
2104 k
= mbedtls_mpi_bitlen( &W
);
2106 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A
, j
- k
) );
2110 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
;
2113 } while ( mbedtls_mpi_cmp_mpi( &A
, &W
) >= 0 ||
2114 mbedtls_mpi_cmp_int( &A
, 1 ) <= 0 );
2119 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A
, &A
, &R
, X
, &RR
) );
2121 if( mbedtls_mpi_cmp_mpi( &A
, &W
) == 0 ||
2122 mbedtls_mpi_cmp_int( &A
, 1 ) == 0 )
2126 while( j
< s
&& mbedtls_mpi_cmp_mpi( &A
, &W
) != 0 )
2131 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
, &A
, &A
) );
2132 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A
, &T
, X
) );
2134 if( mbedtls_mpi_cmp_int( &A
, 1 ) == 0 )
2141 * not prime if A != |X| - 1 or A == 1
2143 if( mbedtls_mpi_cmp_mpi( &A
, &W
) != 0 ||
2144 mbedtls_mpi_cmp_int( &A
, 1 ) == 0 )
2146 ret
= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
;
2152 mbedtls_mpi_free( &W
); mbedtls_mpi_free( &R
); mbedtls_mpi_free( &T
); mbedtls_mpi_free( &A
);
2153 mbedtls_mpi_free( &RR
);
2159 * Pseudo-primality test: small factors, then Miller-Rabin
2161 int mbedtls_mpi_is_prime( const mbedtls_mpi
*X
,
2162 int (*f_rng
)(void *, unsigned char *, size_t),
2172 if( mbedtls_mpi_cmp_int( &XX
, 0 ) == 0 ||
2173 mbedtls_mpi_cmp_int( &XX
, 1 ) == 0 )
2174 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
);
2176 if( mbedtls_mpi_cmp_int( &XX
, 2 ) == 0 )
2179 if( ( ret
= mpi_check_small_factors( &XX
) ) != 0 )
2187 return( mpi_miller_rabin( &XX
, f_rng
, p_rng
) );
2191 * Prime number generation
2193 int mbedtls_mpi_gen_prime( mbedtls_mpi
*X
, size_t nbits
, int dh_flag
,
2194 int (*f_rng
)(void *, unsigned char *, size_t),
2202 if( nbits
< 3 || nbits
> MBEDTLS_MPI_MAX_BITS
)
2203 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
2205 mbedtls_mpi_init( &Y
);
2207 n
= BITS_TO_LIMBS( nbits
);
2209 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X
, n
* ciL
, f_rng
, p_rng
) );
2211 k
= mbedtls_mpi_bitlen( X
);
2212 if( k
> nbits
) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X
, k
- nbits
+ 1 ) );
2214 mbedtls_mpi_set_bit( X
, nbits
-1, 1 );
2220 while( ( ret
= mbedtls_mpi_is_prime( X
, f_rng
, p_rng
) ) != 0 )
2222 if( ret
!= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
)
2225 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 2 ) );
2231 * An necessary condition for Y and X = 2Y + 1 to be prime
2232 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2233 * Make sure it is satisfied, while keeping X = 3 mod 4
2238 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r
, X
, 3 ) );
2240 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 8 ) );
2242 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 4 ) );
2244 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2245 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y
, X
) );
2246 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y
, 1 ) );
2251 * First, check small factors for X and Y
2252 * before doing Miller-Rabin on any of them
2254 if( ( ret
= mpi_check_small_factors( X
) ) == 0 &&
2255 ( ret
= mpi_check_small_factors( &Y
) ) == 0 &&
2256 ( ret
= mpi_miller_rabin( X
, f_rng
, p_rng
) ) == 0 &&
2257 ( ret
= mpi_miller_rabin( &Y
, f_rng
, p_rng
) ) == 0 )
2262 if( ret
!= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
)
2266 * Next candidates. We want to preserve Y = (X-1) / 2 and
2267 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2268 * so up Y by 6 and X by 12.
2270 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 12 ) );
2271 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y
, &Y
, 6 ) );
2277 mbedtls_mpi_free( &Y
);
2282 #endif /* MBEDTLS_GENPRIME */
2284 #if defined(MBEDTLS_SELF_TEST)
2286 #define GCD_PAIR_COUNT 3
2288 static const int gcd_pairs
[GCD_PAIR_COUNT
][3] =
2292 { 768454923, 542167814, 1 }
2298 int mbedtls_mpi_self_test( int verbose
)
2301 mbedtls_mpi A
, E
, N
, X
, Y
, U
, V
;
2303 mbedtls_mpi_init( &A
); mbedtls_mpi_init( &E
); mbedtls_mpi_init( &N
); mbedtls_mpi_init( &X
);
2304 mbedtls_mpi_init( &Y
); mbedtls_mpi_init( &U
); mbedtls_mpi_init( &V
);
2306 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A
, 16,
2307 "EFE021C2645FD1DC586E69184AF4A31E" \
2308 "D5F53E93B5F123FA41680867BA110131" \
2309 "944FE7952E2517337780CB0DB80E61AA" \
2310 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2312 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E
, 16,
2313 "B2E7EFD37075B9F03FF989C7C5051C20" \
2314 "34D2A323810251127E7BF8625A4F49A5" \
2315 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2316 "5B5C25763222FEFCCFC38B832366C29E" ) );
2318 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N
, 16,
2319 "0066A198186C18C10B2F5ED9B522752A" \
2320 "9830B69916E535C8F047518A889A43A5" \
2321 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2323 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X
, &A
, &N
) );
2325 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2326 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2327 "9E857EA95A03512E2BAE7391688D264A" \
2328 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2329 "8001B72E848A38CAE1C65F78E56ABDEF" \
2330 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2331 "ECF677152EF804370C1A305CAF3B5BF1" \
2332 "30879B56C61DE584A0F53A2447A51E" ) );
2335 mbedtls_printf( " MPI test #1 (mul_mpi): " );
2337 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 )
2340 mbedtls_printf( "failed\n" );
2347 mbedtls_printf( "passed\n" );
2349 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X
, &Y
, &A
, &N
) );
2351 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2352 "256567336059E52CAE22925474705F39A94" ) );
2354 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V
, 16,
2355 "6613F26162223DF488E9CD48CC132C7A" \
2356 "0AC93C701B001B092E4E5B9F73BCD27B" \
2357 "9EE50D0657C77F374E903CDFA4C642" ) );
2360 mbedtls_printf( " MPI test #2 (div_mpi): " );
2362 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 ||
2363 mbedtls_mpi_cmp_mpi( &Y
, &V
) != 0 )
2366 mbedtls_printf( "failed\n" );
2373 mbedtls_printf( "passed\n" );
2375 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X
, &A
, &E
, &N
, NULL
) );
2377 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2378 "36E139AEA55215609D2816998ED020BB" \
2379 "BD96C37890F65171D948E9BC7CBAA4D9" \
2380 "325D24D6A3C12710F10A09FA08AB87" ) );
2383 mbedtls_printf( " MPI test #3 (exp_mod): " );
2385 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 )
2388 mbedtls_printf( "failed\n" );
2395 mbedtls_printf( "passed\n" );
2397 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X
, &A
, &N
) );
2399 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2400 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2401 "C3DBA76456363A10869622EAC2DD84EC" \
2402 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2405 mbedtls_printf( " MPI test #4 (inv_mod): " );
2407 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 )
2410 mbedtls_printf( "failed\n" );
2417 mbedtls_printf( "passed\n" );
2420 mbedtls_printf( " MPI test #5 (simple gcd): " );
2422 for( i
= 0; i
< GCD_PAIR_COUNT
; i
++ )
2424 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X
, gcd_pairs
[i
][0] ) );
2425 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y
, gcd_pairs
[i
][1] ) );
2427 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A
, &X
, &Y
) );
2429 if( mbedtls_mpi_cmp_int( &A
, gcd_pairs
[i
][2] ) != 0 )
2432 mbedtls_printf( "failed at %d\n", i
);
2440 mbedtls_printf( "passed\n" );
2444 if( ret
!= 0 && verbose
!= 0 )
2445 mbedtls_printf( "Unexpected error, return code = %08X\n", ret
);
2447 mbedtls_mpi_free( &A
); mbedtls_mpi_free( &E
); mbedtls_mpi_free( &N
); mbedtls_mpi_free( &X
);
2448 mbedtls_mpi_free( &Y
); mbedtls_mpi_free( &U
); mbedtls_mpi_free( &V
);
2451 mbedtls_printf( "\n" );
2456 #endif /* MBEDTLS_SELF_TEST */
2458 #endif /* MBEDTLS_BIGNUM_C */