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"
53 #if defined(MBEDTLS_PLATFORM_C)
54 #include "mbedtls/platform.h"
58 #define mbedtls_printf printf
59 #define mbedtls_calloc calloc
60 #define mbedtls_free free
63 /* Implementation that should never be optimized out by the compiler */
64 static void mbedtls_mpi_zeroize( mbedtls_mpi_uint
*v
, size_t n
) {
65 volatile mbedtls_mpi_uint
*p
= v
; while( n
-- ) *p
++ = 0;
68 #define ciL (sizeof(mbedtls_mpi_uint)) /* chars in limb */
69 #define biL (ciL << 3) /* bits in limb */
70 #define biH (ciL << 2) /* half limb size */
72 #define MPI_SIZE_T_MAX ( (size_t) -1 ) /* SIZE_T_MAX is not standard */
75 * Convert between bits/chars and number of limbs
76 * Divide first in order to avoid potential overflows
78 #define BITS_TO_LIMBS(i) ( (i) / biL + ( (i) % biL != 0 ) )
79 #define CHARS_TO_LIMBS(i) ( (i) / ciL + ( (i) % ciL != 0 ) )
84 void mbedtls_mpi_init( mbedtls_mpi
*X
)
97 void mbedtls_mpi_free( mbedtls_mpi
*X
)
104 mbedtls_mpi_zeroize( X
->p
, X
->n
);
105 mbedtls_free( X
->p
);
114 * Enlarge to the specified number of limbs
116 int mbedtls_mpi_grow( mbedtls_mpi
*X
, size_t nblimbs
)
120 if( nblimbs
> MBEDTLS_MPI_MAX_LIMBS
)
121 return( MBEDTLS_ERR_MPI_ALLOC_FAILED
);
125 if( ( p
= (mbedtls_mpi_uint
*)mbedtls_calloc( nblimbs
, ciL
) ) == NULL
)
126 return( MBEDTLS_ERR_MPI_ALLOC_FAILED
);
130 memcpy( p
, X
->p
, X
->n
* ciL
);
131 mbedtls_mpi_zeroize( X
->p
, X
->n
);
132 mbedtls_free( X
->p
);
143 * Resize down as much as possible,
144 * while keeping at least the specified number of limbs
146 int mbedtls_mpi_shrink( mbedtls_mpi
*X
, size_t nblimbs
)
151 /* Actually resize up in this case */
152 if( X
->n
<= nblimbs
)
153 return( mbedtls_mpi_grow( X
, nblimbs
) );
155 for( i
= X
->n
- 1; i
> 0; i
-- )
163 if( ( p
= (mbedtls_mpi_uint
*)mbedtls_calloc( i
, ciL
) ) == NULL
)
164 return( MBEDTLS_ERR_MPI_ALLOC_FAILED
);
168 memcpy( p
, X
->p
, i
* ciL
);
169 mbedtls_mpi_zeroize( X
->p
, X
->n
);
170 mbedtls_free( X
->p
);
180 * Copy the contents of Y into X
182 int mbedtls_mpi_copy( mbedtls_mpi
*X
, const mbedtls_mpi
*Y
)
192 mbedtls_mpi_free( X
);
196 for( i
= Y
->n
- 1; i
> 0; i
-- )
203 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, i
) );
205 memset( X
->p
, 0, X
->n
* ciL
);
206 memcpy( X
->p
, Y
->p
, i
* ciL
);
214 * Swap the contents of X and Y
216 void mbedtls_mpi_swap( mbedtls_mpi
*X
, mbedtls_mpi
*Y
)
220 memcpy( &T
, X
, sizeof( mbedtls_mpi
) );
221 memcpy( X
, Y
, sizeof( mbedtls_mpi
) );
222 memcpy( Y
, &T
, sizeof( mbedtls_mpi
) );
226 * Conditionally assign X = Y, without leaking information
227 * about whether the assignment was made or not.
228 * (Leaking information about the respective sizes of X and Y is ok however.)
230 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi
*X
, const mbedtls_mpi
*Y
, unsigned char assign
)
235 /* make sure assign is 0 or 1 in a time-constant manner */
236 assign
= (assign
| (unsigned char)-assign
) >> 7;
238 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, Y
->n
) );
240 X
->s
= X
->s
* ( 1 - assign
) + Y
->s
* assign
;
242 for( i
= 0; i
< Y
->n
; i
++ )
243 X
->p
[i
] = X
->p
[i
] * ( 1 - assign
) + Y
->p
[i
] * assign
;
245 for( ; i
< X
->n
; i
++ )
246 X
->p
[i
] *= ( 1 - assign
);
253 * Conditionally swap X and Y, without leaking information
254 * about whether the swap was made or not.
255 * Here it is not ok to simply swap the pointers, which whould lead to
256 * different memory access patterns when X and Y are used afterwards.
258 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi
*X
, mbedtls_mpi
*Y
, unsigned char swap
)
262 mbedtls_mpi_uint tmp
;
267 /* make sure swap is 0 or 1 in a time-constant manner */
268 swap
= (swap
| (unsigned char)-swap
) >> 7;
270 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, Y
->n
) );
271 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( Y
, X
->n
) );
274 X
->s
= X
->s
* ( 1 - swap
) + Y
->s
* swap
;
275 Y
->s
= Y
->s
* ( 1 - swap
) + s
* swap
;
278 for( i
= 0; i
< X
->n
; i
++ )
281 X
->p
[i
] = X
->p
[i
] * ( 1 - swap
) + Y
->p
[i
] * swap
;
282 Y
->p
[i
] = Y
->p
[i
] * ( 1 - swap
) + tmp
* swap
;
290 * Set value from integer
292 int mbedtls_mpi_lset( mbedtls_mpi
*X
, mbedtls_mpi_sint z
)
296 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, 1 ) );
297 memset( X
->p
, 0, X
->n
* ciL
);
299 X
->p
[0] = ( z
< 0 ) ? -z
: z
;
300 X
->s
= ( z
< 0 ) ? -1 : 1;
310 int mbedtls_mpi_get_bit( const mbedtls_mpi
*X
, size_t pos
)
312 if( X
->n
* biL
<= pos
)
315 return( ( X
->p
[pos
/ biL
] >> ( pos
% biL
) ) & 0x01 );
319 * Set a bit to a specific value of 0 or 1
321 int mbedtls_mpi_set_bit( mbedtls_mpi
*X
, size_t pos
, unsigned char val
)
324 size_t off
= pos
/ biL
;
325 size_t idx
= pos
% biL
;
327 if( val
!= 0 && val
!= 1 )
328 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
330 if( X
->n
* biL
<= pos
)
335 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, off
+ 1 ) );
338 X
->p
[off
] &= ~( (mbedtls_mpi_uint
) 0x01 << idx
);
339 X
->p
[off
] |= (mbedtls_mpi_uint
) val
<< idx
;
347 * Return the number of less significant zero-bits
349 size_t mbedtls_mpi_lsb( const mbedtls_mpi
*X
)
351 size_t i
, j
, count
= 0;
353 for( i
= 0; i
< X
->n
; i
++ )
354 for( j
= 0; j
< biL
; j
++, count
++ )
355 if( ( ( X
->p
[i
] >> j
) & 1 ) != 0 )
362 * Count leading zero bits in a given integer
364 static size_t mbedtls_clz( const mbedtls_mpi_uint x
)
367 mbedtls_mpi_uint mask
= (mbedtls_mpi_uint
) 1 << (biL
- 1);
369 for( j
= 0; j
< biL
; j
++ )
371 if( x
& mask
) break;
380 * Return the number of bits
382 size_t mbedtls_mpi_bitlen( const mbedtls_mpi
*X
)
389 for( i
= X
->n
- 1; i
> 0; i
-- )
393 j
= biL
- mbedtls_clz( X
->p
[i
] );
395 return( ( i
* biL
) + j
);
399 * Return the total size in bytes
401 size_t mbedtls_mpi_size( const mbedtls_mpi
*X
)
403 return( ( mbedtls_mpi_bitlen( X
) + 7 ) >> 3 );
407 * Convert an ASCII character to digit value
409 static int mpi_get_digit( mbedtls_mpi_uint
*d
, int radix
, char c
)
413 if( c
>= 0x30 && c
<= 0x39 ) *d
= c
- 0x30;
414 if( c
>= 0x41 && c
<= 0x46 ) *d
= c
- 0x37;
415 if( c
>= 0x61 && c
<= 0x66 ) *d
= c
- 0x57;
417 if( *d
>= (mbedtls_mpi_uint
) radix
)
418 return( MBEDTLS_ERR_MPI_INVALID_CHARACTER
);
424 * Import from an ASCII string
426 int mbedtls_mpi_read_string( mbedtls_mpi
*X
, int radix
, const char *s
)
429 size_t i
, j
, slen
, n
;
433 if( radix
< 2 || radix
> 16 )
434 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
436 mbedtls_mpi_init( &T
);
442 if( slen
> MPI_SIZE_T_MAX
>> 2 )
443 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
445 n
= BITS_TO_LIMBS( slen
<< 2 );
447 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, n
) );
448 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
450 for( i
= slen
, j
= 0; i
> 0; i
--, j
++ )
452 if( i
== 1 && s
[i
- 1] == '-' )
458 MBEDTLS_MPI_CHK( mpi_get_digit( &d
, radix
, s
[i
- 1] ) );
459 X
->p
[j
/ ( 2 * ciL
)] |= d
<< ( ( j
% ( 2 * ciL
) ) << 2 );
464 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
466 for( i
= 0; i
< slen
; i
++ )
468 if( i
== 0 && s
[i
] == '-' )
474 MBEDTLS_MPI_CHK( mpi_get_digit( &d
, radix
, s
[i
] ) );
475 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T
, X
, radix
) );
479 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, &T
, d
) );
483 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( X
, &T
, d
) );
490 mbedtls_mpi_free( &T
);
496 * Helper to write the digits high-order first
498 static int mpi_write_hlp( mbedtls_mpi
*X
, int radix
, char **p
)
503 if( radix
< 2 || radix
> 16 )
504 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
506 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r
, X
, radix
) );
507 MBEDTLS_MPI_CHK( mbedtls_mpi_div_int( X
, NULL
, X
, radix
) );
509 if( mbedtls_mpi_cmp_int( X
, 0 ) != 0 )
510 MBEDTLS_MPI_CHK( mpi_write_hlp( X
, radix
, p
) );
513 *(*p
)++ = (char)( r
+ 0x30 );
515 *(*p
)++ = (char)( r
+ 0x37 );
523 * Export into an ASCII string
525 int mbedtls_mpi_write_string( const mbedtls_mpi
*X
, int radix
,
526 char *buf
, size_t buflen
, size_t *olen
)
533 if( radix
< 2 || radix
> 16 )
534 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
536 n
= mbedtls_mpi_bitlen( X
);
537 if( radix
>= 4 ) n
>>= 1;
538 if( radix
>= 16 ) n
>>= 1;
540 * Round up the buffer length to an even value to ensure that there is
541 * enough room for hexadecimal values that can be represented in an odd
544 n
+= 3 + ( ( n
+ 1 ) & 1 );
549 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL
);
553 mbedtls_mpi_init( &T
);
563 for( i
= X
->n
, k
= 0; i
> 0; i
-- )
565 for( j
= ciL
; j
> 0; j
-- )
567 c
= ( X
->p
[i
- 1] >> ( ( j
- 1 ) << 3) ) & 0xFF;
569 if( c
== 0 && k
== 0 && ( i
+ j
) != 2 )
572 *(p
++) = "0123456789ABCDEF" [c
/ 16];
573 *(p
++) = "0123456789ABCDEF" [c
% 16];
580 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T
, X
) );
585 MBEDTLS_MPI_CHK( mpi_write_hlp( &T
, radix
, &p
) );
593 mbedtls_mpi_free( &T
);
598 #if defined(MBEDTLS_FS_IO)
600 * Read X from an opened file
602 int mbedtls_mpi_read_file( mbedtls_mpi
*X
, int radix
, FILE *fin
)
608 * Buffer should have space for (short) label and decimal formatted MPI,
609 * newline characters and '\0'
611 char s
[ MBEDTLS_MPI_RW_BUFFER_SIZE
];
613 memset( s
, 0, sizeof( s
) );
614 if( fgets( s
, sizeof( s
) - 1, fin
) == NULL
)
615 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR
);
618 if( slen
== sizeof( s
) - 2 )
619 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL
);
621 if( slen
> 0 && s
[slen
- 1] == '\n' ) { slen
--; s
[slen
] = '\0'; }
622 if( slen
> 0 && s
[slen
- 1] == '\r' ) { slen
--; s
[slen
] = '\0'; }
626 if( mpi_get_digit( &d
, radix
, *p
) != 0 )
629 return( mbedtls_mpi_read_string( X
, radix
, p
+ 1 ) );
633 * Write X into an opened file (or stdout if fout == NULL)
635 int mbedtls_mpi_write_file( const char *p
, const mbedtls_mpi
*X
, int radix
, FILE *fout
)
638 size_t n
, slen
, plen
;
640 * Buffer should have space for (short) label and decimal formatted MPI,
641 * newline characters and '\0'
643 char s
[ MBEDTLS_MPI_RW_BUFFER_SIZE
];
645 memset( s
, 0, sizeof( s
) );
647 MBEDTLS_MPI_CHK( mbedtls_mpi_write_string( X
, radix
, s
, sizeof( s
) - 2, &n
) );
649 if( p
== NULL
) p
= "";
658 if( fwrite( p
, 1, plen
, fout
) != plen
||
659 fwrite( s
, 1, slen
, fout
) != slen
)
660 return( MBEDTLS_ERR_MPI_FILE_IO_ERROR
);
663 mbedtls_printf( "%s%s", p
, s
);
669 #endif /* MBEDTLS_FS_IO */
672 * Import X from unsigned binary data, big endian
674 int mbedtls_mpi_read_binary( mbedtls_mpi
*X
, const unsigned char *buf
, size_t buflen
)
679 for( n
= 0; n
< buflen
; n
++ )
683 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, CHARS_TO_LIMBS( buflen
- n
) ) );
684 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
686 for( i
= buflen
, j
= 0; i
> n
; i
--, j
++ )
687 X
->p
[j
/ ciL
] |= ((mbedtls_mpi_uint
) buf
[i
- 1]) << ((j
% ciL
) << 3);
695 * Export X into unsigned binary data, big endian
697 int mbedtls_mpi_write_binary( const mbedtls_mpi
*X
, unsigned char *buf
, size_t buflen
)
701 n
= mbedtls_mpi_size( X
);
704 return( MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL
);
706 memset( buf
, 0, buflen
);
708 for( i
= buflen
- 1, j
= 0; n
> 0; i
--, j
++, n
-- )
709 buf
[i
] = (unsigned char)( X
->p
[j
/ ciL
] >> ((j
% ciL
) << 3) );
715 * Left-shift: X <<= count
717 int mbedtls_mpi_shift_l( mbedtls_mpi
*X
, size_t count
)
721 mbedtls_mpi_uint r0
= 0, r1
;
724 t1
= count
& (biL
- 1);
726 i
= mbedtls_mpi_bitlen( X
) + count
;
729 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, BITS_TO_LIMBS( i
) ) );
734 * shift by count / limb_size
738 for( i
= X
->n
; i
> v0
; i
-- )
739 X
->p
[i
- 1] = X
->p
[i
- v0
- 1];
746 * shift by count % limb_size
750 for( i
= v0
; i
< X
->n
; i
++ )
752 r1
= X
->p
[i
] >> (biL
- t1
);
765 * Right-shift: X >>= count
767 int mbedtls_mpi_shift_r( mbedtls_mpi
*X
, size_t count
)
770 mbedtls_mpi_uint r0
= 0, r1
;
773 v1
= count
& (biL
- 1);
775 if( v0
> X
->n
|| ( v0
== X
->n
&& v1
> 0 ) )
776 return mbedtls_mpi_lset( X
, 0 );
779 * shift by count / limb_size
783 for( i
= 0; i
< X
->n
- v0
; i
++ )
784 X
->p
[i
] = X
->p
[i
+ v0
];
786 for( ; i
< X
->n
; i
++ )
791 * shift by count % limb_size
795 for( i
= X
->n
; i
> 0; i
-- )
797 r1
= X
->p
[i
- 1] << (biL
- v1
);
808 * Compare unsigned values
810 int mbedtls_mpi_cmp_abs( const mbedtls_mpi
*X
, const mbedtls_mpi
*Y
)
814 for( i
= X
->n
; i
> 0; i
-- )
815 if( X
->p
[i
- 1] != 0 )
818 for( j
= Y
->n
; j
> 0; j
-- )
819 if( Y
->p
[j
- 1] != 0 )
822 if( i
== 0 && j
== 0 )
825 if( i
> j
) return( 1 );
826 if( j
> i
) return( -1 );
830 if( X
->p
[i
- 1] > Y
->p
[i
- 1] ) return( 1 );
831 if( X
->p
[i
- 1] < Y
->p
[i
- 1] ) return( -1 );
838 * Compare signed values
840 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi
*X
, const mbedtls_mpi
*Y
)
844 for( i
= X
->n
; i
> 0; i
-- )
845 if( X
->p
[i
- 1] != 0 )
848 for( j
= Y
->n
; j
> 0; j
-- )
849 if( Y
->p
[j
- 1] != 0 )
852 if( i
== 0 && j
== 0 )
855 if( i
> j
) return( X
->s
);
856 if( j
> i
) return( -Y
->s
);
858 if( X
->s
> 0 && Y
->s
< 0 ) return( 1 );
859 if( Y
->s
> 0 && X
->s
< 0 ) return( -1 );
863 if( X
->p
[i
- 1] > Y
->p
[i
- 1] ) return( X
->s
);
864 if( X
->p
[i
- 1] < Y
->p
[i
- 1] ) return( -X
->s
);
871 * Compare signed values
873 int mbedtls_mpi_cmp_int( const mbedtls_mpi
*X
, mbedtls_mpi_sint z
)
876 mbedtls_mpi_uint p
[1];
878 *p
= ( z
< 0 ) ? -z
: z
;
879 Y
.s
= ( z
< 0 ) ? -1 : 1;
883 return( mbedtls_mpi_cmp_mpi( X
, &Y
) );
887 * Unsigned addition: X = |A| + |B| (HAC 14.7)
889 int mbedtls_mpi_add_abs( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
893 mbedtls_mpi_uint
*o
, *p
, c
, tmp
;
897 const mbedtls_mpi
*T
= A
; A
= X
; B
= T
;
901 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, A
) );
904 * X should always be positive as a result of unsigned additions.
908 for( j
= B
->n
; j
> 0; j
-- )
909 if( B
->p
[j
- 1] != 0 )
912 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, j
) );
914 o
= B
->p
; p
= X
->p
; c
= 0;
917 * tmp is used because it might happen that p == o
919 for( i
= 0; i
< j
; i
++, o
++, p
++ )
922 *p
+= c
; c
= ( *p
< c
);
923 *p
+= tmp
; c
+= ( *p
< tmp
);
930 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, i
+ 1 ) );
934 *p
+= c
; c
= ( *p
< c
); i
++; p
++;
943 * Helper for mbedtls_mpi subtraction
945 static void mpi_sub_hlp( size_t n
, mbedtls_mpi_uint
*s
, mbedtls_mpi_uint
*d
)
948 mbedtls_mpi_uint c
, z
;
950 for( i
= c
= 0; i
< n
; i
++, s
++, d
++ )
952 z
= ( *d
< c
); *d
-= c
;
953 c
= ( *d
< *s
) + z
; *d
-= *s
;
958 z
= ( *d
< c
); *d
-= c
;
964 * Unsigned subtraction: X = |A| - |B| (HAC 14.9)
966 int mbedtls_mpi_sub_abs( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
972 if( mbedtls_mpi_cmp_abs( A
, B
) < 0 )
973 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE
);
975 mbedtls_mpi_init( &TB
);
979 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, B
) );
984 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, A
) );
987 * X should always be positive as a result of unsigned subtractions.
993 for( n
= B
->n
; n
> 0; n
-- )
994 if( B
->p
[n
- 1] != 0 )
997 mpi_sub_hlp( n
, B
->p
, X
->p
);
1001 mbedtls_mpi_free( &TB
);
1007 * Signed addition: X = A + B
1009 int mbedtls_mpi_add_mpi( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1013 if( A
->s
* B
->s
< 0 )
1015 if( mbedtls_mpi_cmp_abs( A
, B
) >= 0 )
1017 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, A
, B
) );
1022 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, B
, A
) );
1028 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X
, A
, B
) );
1038 * Signed subtraction: X = A - B
1040 int mbedtls_mpi_sub_mpi( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1044 if( A
->s
* B
->s
> 0 )
1046 if( mbedtls_mpi_cmp_abs( A
, B
) >= 0 )
1048 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, A
, B
) );
1053 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( X
, B
, A
) );
1059 MBEDTLS_MPI_CHK( mbedtls_mpi_add_abs( X
, A
, B
) );
1069 * Signed addition: X = A + b
1071 int mbedtls_mpi_add_int( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1074 mbedtls_mpi_uint p
[1];
1076 p
[0] = ( b
< 0 ) ? -b
: b
;
1077 _B
.s
= ( b
< 0 ) ? -1 : 1;
1081 return( mbedtls_mpi_add_mpi( X
, A
, &_B
) );
1085 * Signed subtraction: X = A - b
1087 int mbedtls_mpi_sub_int( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1090 mbedtls_mpi_uint p
[1];
1092 p
[0] = ( b
< 0 ) ? -b
: b
;
1093 _B
.s
= ( b
< 0 ) ? -1 : 1;
1097 return( mbedtls_mpi_sub_mpi( X
, A
, &_B
) );
1101 * Helper for mbedtls_mpi multiplication
1104 #if defined(__APPLE__) && defined(__arm__)
1106 * Apple LLVM version 4.2 (clang-425.0.24) (based on LLVM 3.2svn)
1107 * appears to need this to prevent bad ARM code generation at -O3.
1109 __attribute__ ((noinline
))
1111 void mpi_mul_hlp( size_t i
, mbedtls_mpi_uint
*s
, mbedtls_mpi_uint
*d
, mbedtls_mpi_uint b
)
1113 mbedtls_mpi_uint c
= 0, t
= 0;
1115 #if defined(MULADDC_HUIT)
1116 for( ; i
>= 8; i
-= 8 )
1129 #else /* MULADDC_HUIT */
1130 for( ; i
>= 16; i
-= 16 )
1133 MULADDC_CORE MULADDC_CORE
1134 MULADDC_CORE MULADDC_CORE
1135 MULADDC_CORE MULADDC_CORE
1136 MULADDC_CORE MULADDC_CORE
1138 MULADDC_CORE MULADDC_CORE
1139 MULADDC_CORE MULADDC_CORE
1140 MULADDC_CORE MULADDC_CORE
1141 MULADDC_CORE MULADDC_CORE
1145 for( ; i
>= 8; i
-= 8 )
1148 MULADDC_CORE MULADDC_CORE
1149 MULADDC_CORE MULADDC_CORE
1151 MULADDC_CORE MULADDC_CORE
1152 MULADDC_CORE MULADDC_CORE
1162 #endif /* MULADDC_HUIT */
1167 *d
+= c
; c
= ( *d
< c
); d
++;
1173 * Baseline multiplication: X = A * B (HAC 14.12)
1175 int mbedtls_mpi_mul_mpi( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1181 mbedtls_mpi_init( &TA
); mbedtls_mpi_init( &TB
);
1183 if( X
== A
) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA
, A
) ); A
= &TA
; }
1184 if( X
== B
) { MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, B
) ); B
= &TB
; }
1186 for( i
= A
->n
; i
> 0; i
-- )
1187 if( A
->p
[i
- 1] != 0 )
1190 for( j
= B
->n
; j
> 0; j
-- )
1191 if( B
->p
[j
- 1] != 0 )
1194 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, i
+ j
) );
1195 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( X
, 0 ) );
1197 for( i
++; j
> 0; j
-- )
1198 mpi_mul_hlp( i
- 1, A
->p
, X
->p
+ j
- 1, B
->p
[j
- 1] );
1204 mbedtls_mpi_free( &TB
); mbedtls_mpi_free( &TA
);
1210 * Baseline multiplication: X = A * b
1212 int mbedtls_mpi_mul_int( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, mbedtls_mpi_uint b
)
1215 mbedtls_mpi_uint p
[1];
1222 return( mbedtls_mpi_mul_mpi( X
, A
, &_B
) );
1226 * Unsigned integer divide - double mbedtls_mpi_uint dividend, u1/u0, and
1227 * mbedtls_mpi_uint divisor, d
1229 static mbedtls_mpi_uint
mbedtls_int_div_int( mbedtls_mpi_uint u1
,
1230 mbedtls_mpi_uint u0
, mbedtls_mpi_uint d
, mbedtls_mpi_uint
*r
)
1232 #if defined(MBEDTLS_HAVE_UDBL)
1233 mbedtls_t_udbl dividend
, quotient
;
1235 const mbedtls_mpi_uint radix
= (mbedtls_mpi_uint
) 1 << biH
;
1236 const mbedtls_mpi_uint uint_halfword_mask
= ( (mbedtls_mpi_uint
) 1 << biH
) - 1;
1237 mbedtls_mpi_uint d0
, d1
, q0
, q1
, rAX
, r0
, quotient
;
1238 mbedtls_mpi_uint u0_msw
, u0_lsw
;
1243 * Check for overflow
1245 if( 0 == d
|| u1
>= d
)
1247 if (r
!= NULL
) *r
= ~0;
1252 #if defined(MBEDTLS_HAVE_UDBL)
1253 dividend
= (mbedtls_t_udbl
) u1
<< biL
;
1254 dividend
|= (mbedtls_t_udbl
) u0
;
1255 quotient
= dividend
/ d
;
1256 if( quotient
> ( (mbedtls_t_udbl
) 1 << biL
) - 1 )
1257 quotient
= ( (mbedtls_t_udbl
) 1 << biL
) - 1;
1260 *r
= (mbedtls_mpi_uint
)( dividend
- (quotient
* d
) );
1262 return (mbedtls_mpi_uint
) quotient
;
1266 * Algorithm D, Section 4.3.1 - The Art of Computer Programming
1267 * Vol. 2 - Seminumerical Algorithms, Knuth
1271 * Normalize the divisor, d, and dividend, u0, u1
1273 s
= mbedtls_clz( d
);
1277 u1
|= ( u0
>> ( biL
- s
) ) & ( -(mbedtls_mpi_sint
)s
>> ( biL
- 1 ) );
1281 d0
= d
& uint_halfword_mask
;
1284 u0_lsw
= u0
& uint_halfword_mask
;
1287 * Find the first quotient and remainder
1292 while( q1
>= radix
|| ( q1
* d0
> radix
* r0
+ u0_msw
) )
1297 if ( r0
>= radix
) break;
1300 rAX
= ( u1
* radix
) + ( u0_msw
- q1
* d
);
1304 while( q0
>= radix
|| ( q0
* d0
> radix
* r0
+ u0_lsw
) )
1309 if ( r0
>= radix
) break;
1313 *r
= ( rAX
* radix
+ u0_lsw
- q0
* d
) >> s
;
1315 quotient
= q1
* radix
+ q0
;
1322 * Division by mbedtls_mpi: A = Q * B + R (HAC 14.20)
1324 int mbedtls_mpi_div_mpi( mbedtls_mpi
*Q
, mbedtls_mpi
*R
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1328 mbedtls_mpi X
, Y
, Z
, T1
, T2
;
1330 if( mbedtls_mpi_cmp_int( B
, 0 ) == 0 )
1331 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO
);
1333 mbedtls_mpi_init( &X
); mbedtls_mpi_init( &Y
); mbedtls_mpi_init( &Z
);
1334 mbedtls_mpi_init( &T1
); mbedtls_mpi_init( &T2
);
1336 if( mbedtls_mpi_cmp_abs( A
, B
) < 0 )
1338 if( Q
!= NULL
) MBEDTLS_MPI_CHK( mbedtls_mpi_lset( Q
, 0 ) );
1339 if( R
!= NULL
) MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R
, A
) );
1343 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &X
, A
) );
1344 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y
, B
) );
1347 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &Z
, A
->n
+ 2 ) );
1348 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Z
, 0 ) );
1349 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T1
, 2 ) );
1350 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T2
, 3 ) );
1352 k
= mbedtls_mpi_bitlen( &Y
) % biL
;
1356 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &X
, k
) );
1357 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y
, k
) );
1363 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &Y
, biL
* ( n
- t
) ) );
1365 while( mbedtls_mpi_cmp_mpi( &X
, &Y
) >= 0 )
1368 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X
, &X
, &Y
) );
1370 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y
, biL
* ( n
- t
) ) );
1372 for( i
= n
; i
> t
; i
-- )
1374 if( X
.p
[i
] >= Y
.p
[t
] )
1375 Z
.p
[i
- t
- 1] = ~0;
1378 Z
.p
[i
- t
- 1] = mbedtls_int_div_int( X
.p
[i
], X
.p
[i
- 1],
1387 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T1
, 0 ) );
1388 T1
.p
[0] = ( t
< 1 ) ? 0 : Y
.p
[t
- 1];
1390 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1
, &T1
, Z
.p
[i
- t
- 1] ) );
1392 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &T2
, 0 ) );
1393 T2
.p
[0] = ( i
< 2 ) ? 0 : X
.p
[i
- 2];
1394 T2
.p
[1] = ( i
< 1 ) ? 0 : X
.p
[i
- 1];
1397 while( mbedtls_mpi_cmp_mpi( &T1
, &T2
) > 0 );
1399 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_int( &T1
, &Y
, Z
.p
[i
- t
- 1] ) );
1400 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1
, biL
* ( i
- t
- 1 ) ) );
1401 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &X
, &X
, &T1
) );
1403 if( mbedtls_mpi_cmp_int( &X
, 0 ) < 0 )
1405 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &T1
, &Y
) );
1406 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &T1
, biL
* ( i
- t
- 1 ) ) );
1407 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &X
, &X
, &T1
) );
1414 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( Q
, &Z
) );
1420 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &X
, k
) );
1422 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( R
, &X
) );
1424 if( mbedtls_mpi_cmp_int( R
, 0 ) == 0 )
1430 mbedtls_mpi_free( &X
); mbedtls_mpi_free( &Y
); mbedtls_mpi_free( &Z
);
1431 mbedtls_mpi_free( &T1
); mbedtls_mpi_free( &T2
);
1437 * Division by int: A = Q * b + R
1439 int mbedtls_mpi_div_int( mbedtls_mpi
*Q
, mbedtls_mpi
*R
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1442 mbedtls_mpi_uint p
[1];
1444 p
[0] = ( b
< 0 ) ? -b
: b
;
1445 _B
.s
= ( b
< 0 ) ? -1 : 1;
1449 return( mbedtls_mpi_div_mpi( Q
, R
, A
, &_B
) );
1453 * Modulo: R = A mod B
1455 int mbedtls_mpi_mod_mpi( mbedtls_mpi
*R
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1459 if( mbedtls_mpi_cmp_int( B
, 0 ) < 0 )
1460 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE
);
1462 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( NULL
, R
, A
, B
) );
1464 while( mbedtls_mpi_cmp_int( R
, 0 ) < 0 )
1465 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( R
, R
, B
) );
1467 while( mbedtls_mpi_cmp_mpi( R
, B
) >= 0 )
1468 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( R
, R
, B
) );
1476 * Modulo: r = A mod b
1478 int mbedtls_mpi_mod_int( mbedtls_mpi_uint
*r
, const mbedtls_mpi
*A
, mbedtls_mpi_sint b
)
1481 mbedtls_mpi_uint x
, y
, z
;
1484 return( MBEDTLS_ERR_MPI_DIVISION_BY_ZERO
);
1487 return( MBEDTLS_ERR_MPI_NEGATIVE_VALUE
);
1490 * handle trivial cases
1507 for( i
= A
->n
, y
= 0; i
> 0; i
-- )
1510 y
= ( y
<< biH
) | ( x
>> biH
);
1515 y
= ( y
<< biH
) | ( x
>> biH
);
1521 * If A is negative, then the current y represents a negative value.
1522 * Flipping it to the positive side.
1524 if( A
->s
< 0 && y
!= 0 )
1533 * Fast Montgomery initialization (thanks to Tom St Denis)
1535 static void mpi_montg_init( mbedtls_mpi_uint
*mm
, const mbedtls_mpi
*N
)
1537 mbedtls_mpi_uint x
, m0
= N
->p
[0];
1541 x
+= ( ( m0
+ 2 ) & 4 ) << 1;
1543 for( i
= biL
; i
>= 8; i
/= 2 )
1544 x
*= ( 2 - ( m0
* x
) );
1550 * Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
1552 static int mpi_montmul( mbedtls_mpi
*A
, const mbedtls_mpi
*B
, const mbedtls_mpi
*N
, mbedtls_mpi_uint mm
,
1553 const mbedtls_mpi
*T
)
1556 mbedtls_mpi_uint u0
, u1
, *d
;
1558 if( T
->n
< N
->n
+ 1 || T
->p
== NULL
)
1559 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1561 memset( T
->p
, 0, T
->n
* ciL
);
1565 m
= ( B
->n
< n
) ? B
->n
: n
;
1567 for( i
= 0; i
< n
; i
++ )
1570 * T = (T + u0*B + u1*N) / 2^biL
1573 u1
= ( d
[0] + u0
* B
->p
[0] ) * mm
;
1575 mpi_mul_hlp( m
, B
->p
, d
, u0
);
1576 mpi_mul_hlp( n
, N
->p
, d
, u1
);
1578 *d
++ = u0
; d
[n
+ 1] = 0;
1581 memcpy( A
->p
, d
, ( n
+ 1 ) * ciL
);
1583 if( mbedtls_mpi_cmp_abs( A
, N
) >= 0 )
1584 mpi_sub_hlp( n
, N
->p
, A
->p
);
1586 /* prevent timing attacks */
1587 mpi_sub_hlp( n
, A
->p
, T
->p
);
1593 * Montgomery reduction: A = A * R^-1 mod N
1595 static int mpi_montred( mbedtls_mpi
*A
, const mbedtls_mpi
*N
, mbedtls_mpi_uint mm
, const mbedtls_mpi
*T
)
1597 mbedtls_mpi_uint z
= 1;
1600 U
.n
= U
.s
= (int) z
;
1603 return( mpi_montmul( A
, &U
, N
, mm
, T
) );
1607 * Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
1609 int mbedtls_mpi_exp_mod( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*E
, const mbedtls_mpi
*N
, mbedtls_mpi
*_RR
)
1612 size_t wbits
, wsize
, one
= 1;
1613 size_t i
, j
, nblimbs
;
1614 size_t bufsize
, nbits
;
1615 mbedtls_mpi_uint ei
, mm
, state
;
1616 mbedtls_mpi RR
, T
, W
[ 2 << MBEDTLS_MPI_WINDOW_SIZE
], Apos
;
1619 if( mbedtls_mpi_cmp_int( N
, 0 ) < 0 || ( N
->p
[0] & 1 ) == 0 )
1620 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1622 if( mbedtls_mpi_cmp_int( E
, 0 ) < 0 )
1623 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1626 * Init temps and window size
1628 mpi_montg_init( &mm
, N
);
1629 mbedtls_mpi_init( &RR
); mbedtls_mpi_init( &T
);
1630 mbedtls_mpi_init( &Apos
);
1631 memset( W
, 0, sizeof( W
) );
1633 i
= mbedtls_mpi_bitlen( E
);
1635 wsize
= ( i
> 671 ) ? 6 : ( i
> 239 ) ? 5 :
1636 ( i
> 79 ) ? 4 : ( i
> 23 ) ? 3 : 1;
1638 if( wsize
> MBEDTLS_MPI_WINDOW_SIZE
)
1639 wsize
= MBEDTLS_MPI_WINDOW_SIZE
;
1642 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( X
, j
) );
1643 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W
[1], j
) );
1644 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &T
, j
* 2 ) );
1647 * Compensate for negative A (and correct at the end)
1649 neg
= ( A
->s
== -1 );
1652 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Apos
, A
) );
1658 * If 1st call, pre-compute R^2 mod N
1660 if( _RR
== NULL
|| _RR
->p
== NULL
)
1662 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &RR
, 1 ) );
1663 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &RR
, N
->n
* 2 * biL
) );
1664 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &RR
, &RR
, N
) );
1667 memcpy( _RR
, &RR
, sizeof( mbedtls_mpi
) );
1670 memcpy( &RR
, _RR
, sizeof( mbedtls_mpi
) );
1673 * W[1] = A * R^2 * R^-1 mod N = A * R mod N
1675 if( mbedtls_mpi_cmp_mpi( A
, N
) >= 0 )
1676 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &W
[1], A
, N
) );
1678 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W
[1], A
) );
1680 MBEDTLS_MPI_CHK( mpi_montmul( &W
[1], &RR
, N
, mm
, &T
) );
1683 * X = R^2 * R^-1 mod N = R mod N
1685 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, &RR
) );
1686 MBEDTLS_MPI_CHK( mpi_montred( X
, N
, mm
, &T
) );
1691 * W[1 << (wsize - 1)] = W[1] ^ (wsize - 1)
1693 j
= one
<< ( wsize
- 1 );
1695 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W
[j
], N
->n
+ 1 ) );
1696 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W
[j
], &W
[1] ) );
1698 for( i
= 0; i
< wsize
- 1; i
++ )
1699 MBEDTLS_MPI_CHK( mpi_montmul( &W
[j
], &W
[j
], N
, mm
, &T
) );
1702 * W[i] = W[i - 1] * W[1]
1704 for( i
= j
+ 1; i
< ( one
<< wsize
); i
++ )
1706 MBEDTLS_MPI_CHK( mbedtls_mpi_grow( &W
[i
], N
->n
+ 1 ) );
1707 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &W
[i
], &W
[i
- 1] ) );
1709 MBEDTLS_MPI_CHK( mpi_montmul( &W
[i
], &W
[1], N
, mm
, &T
) );
1728 bufsize
= sizeof( mbedtls_mpi_uint
) << 3;
1733 ei
= (E
->p
[nblimbs
] >> bufsize
) & 1;
1738 if( ei
== 0 && state
== 0 )
1741 if( ei
== 0 && state
== 1 )
1744 * out of window, square X
1746 MBEDTLS_MPI_CHK( mpi_montmul( X
, X
, N
, mm
, &T
) );
1751 * add ei to current window
1756 wbits
|= ( ei
<< ( wsize
- nbits
) );
1758 if( nbits
== wsize
)
1761 * X = X^wsize R^-1 mod N
1763 for( i
= 0; i
< wsize
; i
++ )
1764 MBEDTLS_MPI_CHK( mpi_montmul( X
, X
, N
, mm
, &T
) );
1767 * X = X * W[wbits] R^-1 mod N
1769 MBEDTLS_MPI_CHK( mpi_montmul( X
, &W
[wbits
], N
, mm
, &T
) );
1778 * process the remaining bits
1780 for( i
= 0; i
< nbits
; i
++ )
1782 MBEDTLS_MPI_CHK( mpi_montmul( X
, X
, N
, mm
, &T
) );
1786 if( ( wbits
& ( one
<< wsize
) ) != 0 )
1787 MBEDTLS_MPI_CHK( mpi_montmul( X
, &W
[1], N
, mm
, &T
) );
1791 * X = A^E * R * R^-1 mod N = A^E mod N
1793 MBEDTLS_MPI_CHK( mpi_montred( X
, N
, mm
, &T
) );
1795 if( neg
&& E
->n
!= 0 && ( E
->p
[0] & 1 ) != 0 )
1798 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( X
, N
, X
) );
1803 for( i
= ( one
<< ( wsize
- 1 ) ); i
< ( one
<< wsize
); i
++ )
1804 mbedtls_mpi_free( &W
[i
] );
1806 mbedtls_mpi_free( &W
[1] ); mbedtls_mpi_free( &T
); mbedtls_mpi_free( &Apos
);
1808 if( _RR
== NULL
|| _RR
->p
== NULL
)
1809 mbedtls_mpi_free( &RR
);
1815 * Greatest common divisor: G = gcd(A, B) (HAC 14.54)
1817 int mbedtls_mpi_gcd( mbedtls_mpi
*G
, const mbedtls_mpi
*A
, const mbedtls_mpi
*B
)
1821 mbedtls_mpi TG
, TA
, TB
;
1823 mbedtls_mpi_init( &TG
); mbedtls_mpi_init( &TA
); mbedtls_mpi_init( &TB
);
1825 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TA
, A
) );
1826 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, B
) );
1828 lz
= mbedtls_mpi_lsb( &TA
);
1829 lzt
= mbedtls_mpi_lsb( &TB
);
1834 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA
, lz
) );
1835 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB
, lz
) );
1839 while( mbedtls_mpi_cmp_int( &TA
, 0 ) != 0 )
1841 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA
, mbedtls_mpi_lsb( &TA
) ) );
1842 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB
, mbedtls_mpi_lsb( &TB
) ) );
1844 if( mbedtls_mpi_cmp_mpi( &TA
, &TB
) >= 0 )
1846 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TA
, &TA
, &TB
) );
1847 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TA
, 1 ) );
1851 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_abs( &TB
, &TB
, &TA
) );
1852 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TB
, 1 ) );
1856 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_l( &TB
, lz
) );
1857 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( G
, &TB
) );
1861 mbedtls_mpi_free( &TG
); mbedtls_mpi_free( &TA
); mbedtls_mpi_free( &TB
);
1867 * Fill X with size bytes of random.
1869 * Use a temporary bytes representation to make sure the result is the same
1870 * regardless of the platform endianness (useful when f_rng is actually
1871 * deterministic, eg for tests).
1873 int mbedtls_mpi_fill_random( mbedtls_mpi
*X
, size_t size
,
1874 int (*f_rng
)(void *, unsigned char *, size_t),
1878 unsigned char buf
[MBEDTLS_MPI_MAX_SIZE
];
1880 if( size
> MBEDTLS_MPI_MAX_SIZE
)
1881 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1883 MBEDTLS_MPI_CHK( f_rng( p_rng
, buf
, size
) );
1884 MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( X
, buf
, size
) );
1891 * Modular inverse: X = A^-1 mod N (HAC 14.61 / 14.64)
1893 int mbedtls_mpi_inv_mod( mbedtls_mpi
*X
, const mbedtls_mpi
*A
, const mbedtls_mpi
*N
)
1896 mbedtls_mpi G
, TA
, TU
, U1
, U2
, TB
, TV
, V1
, V2
;
1898 if( mbedtls_mpi_cmp_int( N
, 1 ) <= 0 )
1899 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
1901 mbedtls_mpi_init( &TA
); mbedtls_mpi_init( &TU
); mbedtls_mpi_init( &U1
); mbedtls_mpi_init( &U2
);
1902 mbedtls_mpi_init( &G
); mbedtls_mpi_init( &TB
); mbedtls_mpi_init( &TV
);
1903 mbedtls_mpi_init( &V1
); mbedtls_mpi_init( &V2
);
1905 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &G
, A
, N
) );
1907 if( mbedtls_mpi_cmp_int( &G
, 1 ) != 0 )
1909 ret
= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
;
1913 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &TA
, A
, N
) );
1914 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TU
, &TA
) );
1915 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TB
, N
) );
1916 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &TV
, N
) );
1918 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U1
, 1 ) );
1919 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &U2
, 0 ) );
1920 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V1
, 0 ) );
1921 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &V2
, 1 ) );
1925 while( ( TU
.p
[0] & 1 ) == 0 )
1927 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TU
, 1 ) );
1929 if( ( U1
.p
[0] & 1 ) != 0 || ( U2
.p
[0] & 1 ) != 0 )
1931 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &U1
, &U1
, &TB
) );
1932 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2
, &U2
, &TA
) );
1935 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U1
, 1 ) );
1936 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &U2
, 1 ) );
1939 while( ( TV
.p
[0] & 1 ) == 0 )
1941 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &TV
, 1 ) );
1943 if( ( V1
.p
[0] & 1 ) != 0 || ( V2
.p
[0] & 1 ) != 0 )
1945 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1
, &V1
, &TB
) );
1946 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2
, &V2
, &TA
) );
1949 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V1
, 1 ) );
1950 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &V2
, 1 ) );
1953 if( mbedtls_mpi_cmp_mpi( &TU
, &TV
) >= 0 )
1955 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TU
, &TU
, &TV
) );
1956 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U1
, &U1
, &V1
) );
1957 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &U2
, &U2
, &V2
) );
1961 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &TV
, &TV
, &TU
) );
1962 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1
, &V1
, &U1
) );
1963 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V2
, &V2
, &U2
) );
1966 while( mbedtls_mpi_cmp_int( &TU
, 0 ) != 0 );
1968 while( mbedtls_mpi_cmp_int( &V1
, 0 ) < 0 )
1969 MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &V1
, &V1
, N
) );
1971 while( mbedtls_mpi_cmp_mpi( &V1
, N
) >= 0 )
1972 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( &V1
, &V1
, N
) );
1974 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( X
, &V1
) );
1978 mbedtls_mpi_free( &TA
); mbedtls_mpi_free( &TU
); mbedtls_mpi_free( &U1
); mbedtls_mpi_free( &U2
);
1979 mbedtls_mpi_free( &G
); mbedtls_mpi_free( &TB
); mbedtls_mpi_free( &TV
);
1980 mbedtls_mpi_free( &V1
); mbedtls_mpi_free( &V2
);
1985 #if defined(MBEDTLS_GENPRIME)
1987 static const int small_prime
[] =
1989 3, 5, 7, 11, 13, 17, 19, 23,
1990 29, 31, 37, 41, 43, 47, 53, 59,
1991 61, 67, 71, 73, 79, 83, 89, 97,
1992 101, 103, 107, 109, 113, 127, 131, 137,
1993 139, 149, 151, 157, 163, 167, 173, 179,
1994 181, 191, 193, 197, 199, 211, 223, 227,
1995 229, 233, 239, 241, 251, 257, 263, 269,
1996 271, 277, 281, 283, 293, 307, 311, 313,
1997 317, 331, 337, 347, 349, 353, 359, 367,
1998 373, 379, 383, 389, 397, 401, 409, 419,
1999 421, 431, 433, 439, 443, 449, 457, 461,
2000 463, 467, 479, 487, 491, 499, 503, 509,
2001 521, 523, 541, 547, 557, 563, 569, 571,
2002 577, 587, 593, 599, 601, 607, 613, 617,
2003 619, 631, 641, 643, 647, 653, 659, 661,
2004 673, 677, 683, 691, 701, 709, 719, 727,
2005 733, 739, 743, 751, 757, 761, 769, 773,
2006 787, 797, 809, 811, 821, 823, 827, 829,
2007 839, 853, 857, 859, 863, 877, 881, 883,
2008 887, 907, 911, 919, 929, 937, 941, 947,
2009 953, 967, 971, 977, 983, 991, 997, -103
2013 * Small divisors test (X must be positive)
2016 * 0: no small factor (possible prime, more tests needed)
2018 * MBEDTLS_ERR_MPI_NOT_ACCEPTABLE: certain non-prime
2019 * other negative: error
2021 static int mpi_check_small_factors( const mbedtls_mpi
*X
)
2027 if( ( X
->p
[0] & 1 ) == 0 )
2028 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
);
2030 for( i
= 0; small_prime
[i
] > 0; i
++ )
2032 if( mbedtls_mpi_cmp_int( X
, small_prime
[i
] ) <= 0 )
2035 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r
, X
, small_prime
[i
] ) );
2038 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
);
2046 * Miller-Rabin pseudo-primality test (HAC 4.24)
2048 static int mpi_miller_rabin( const mbedtls_mpi
*X
,
2049 int (*f_rng
)(void *, unsigned char *, size_t),
2053 size_t i
, j
, k
, n
, s
;
2054 mbedtls_mpi W
, R
, T
, A
, RR
;
2056 mbedtls_mpi_init( &W
); mbedtls_mpi_init( &R
); mbedtls_mpi_init( &T
); mbedtls_mpi_init( &A
);
2057 mbedtls_mpi_init( &RR
);
2063 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &W
, X
, 1 ) );
2064 s
= mbedtls_mpi_lsb( &W
);
2065 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &R
, &W
) );
2066 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &R
, s
) );
2068 i
= mbedtls_mpi_bitlen( X
);
2072 n
= ( ( i
>= 1300 ) ? 2 : ( i
>= 850 ) ? 3 :
2073 ( i
>= 650 ) ? 4 : ( i
>= 350 ) ? 8 :
2074 ( i
>= 250 ) ? 12 : ( i
>= 150 ) ? 18 : 27 );
2076 for( i
= 0; i
< n
; i
++ )
2079 * pick a random A, 1 < A < |X| - 1
2081 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A
, X
->n
* ciL
, f_rng
, p_rng
) );
2083 if( mbedtls_mpi_cmp_mpi( &A
, &W
) >= 0 )
2085 j
= mbedtls_mpi_bitlen( &A
) - mbedtls_mpi_bitlen( &W
);
2086 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A
, j
+ 1 ) );
2092 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &A
, X
->n
* ciL
, f_rng
, p_rng
) );
2094 j
= mbedtls_mpi_bitlen( &A
);
2095 k
= mbedtls_mpi_bitlen( &W
);
2097 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &A
, j
- k
) );
2101 return MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
;
2104 } while ( mbedtls_mpi_cmp_mpi( &A
, &W
) >= 0 ||
2105 mbedtls_mpi_cmp_int( &A
, 1 ) <= 0 );
2110 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &A
, &A
, &R
, X
, &RR
) );
2112 if( mbedtls_mpi_cmp_mpi( &A
, &W
) == 0 ||
2113 mbedtls_mpi_cmp_int( &A
, 1 ) == 0 )
2117 while( j
< s
&& mbedtls_mpi_cmp_mpi( &A
, &W
) != 0 )
2122 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &T
, &A
, &A
) );
2123 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &A
, &T
, X
) );
2125 if( mbedtls_mpi_cmp_int( &A
, 1 ) == 0 )
2132 * not prime if A != |X| - 1 or A == 1
2134 if( mbedtls_mpi_cmp_mpi( &A
, &W
) != 0 ||
2135 mbedtls_mpi_cmp_int( &A
, 1 ) == 0 )
2137 ret
= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
;
2143 mbedtls_mpi_free( &W
); mbedtls_mpi_free( &R
); mbedtls_mpi_free( &T
); mbedtls_mpi_free( &A
);
2144 mbedtls_mpi_free( &RR
);
2150 * Pseudo-primality test: small factors, then Miller-Rabin
2152 int mbedtls_mpi_is_prime( const mbedtls_mpi
*X
,
2153 int (*f_rng
)(void *, unsigned char *, size_t),
2163 if( mbedtls_mpi_cmp_int( &XX
, 0 ) == 0 ||
2164 mbedtls_mpi_cmp_int( &XX
, 1 ) == 0 )
2165 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
);
2167 if( mbedtls_mpi_cmp_int( &XX
, 2 ) == 0 )
2170 if( ( ret
= mpi_check_small_factors( &XX
) ) != 0 )
2178 return( mpi_miller_rabin( &XX
, f_rng
, p_rng
) );
2182 * Prime number generation
2184 int mbedtls_mpi_gen_prime( mbedtls_mpi
*X
, size_t nbits
, int dh_flag
,
2185 int (*f_rng
)(void *, unsigned char *, size_t),
2193 if( nbits
< 3 || nbits
> MBEDTLS_MPI_MAX_BITS
)
2194 return( MBEDTLS_ERR_MPI_BAD_INPUT_DATA
);
2196 mbedtls_mpi_init( &Y
);
2198 n
= BITS_TO_LIMBS( nbits
);
2200 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( X
, n
* ciL
, f_rng
, p_rng
) );
2202 k
= mbedtls_mpi_bitlen( X
);
2203 if( k
> nbits
) MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( X
, k
- nbits
+ 1 ) );
2205 mbedtls_mpi_set_bit( X
, nbits
-1, 1 );
2211 while( ( ret
= mbedtls_mpi_is_prime( X
, f_rng
, p_rng
) ) != 0 )
2213 if( ret
!= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
)
2216 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 2 ) );
2222 * An necessary condition for Y and X = 2Y + 1 to be prime
2223 * is X = 2 mod 3 (which is equivalent to Y = 2 mod 3).
2224 * Make sure it is satisfied, while keeping X = 3 mod 4
2229 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_int( &r
, X
, 3 ) );
2231 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 8 ) );
2233 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 4 ) );
2235 /* Set Y = (X-1) / 2, which is X / 2 because X is odd */
2236 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &Y
, X
) );
2237 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &Y
, 1 ) );
2242 * First, check small factors for X and Y
2243 * before doing Miller-Rabin on any of them
2245 if( ( ret
= mpi_check_small_factors( X
) ) == 0 &&
2246 ( ret
= mpi_check_small_factors( &Y
) ) == 0 &&
2247 ( ret
= mpi_miller_rabin( X
, f_rng
, p_rng
) ) == 0 &&
2248 ( ret
= mpi_miller_rabin( &Y
, f_rng
, p_rng
) ) == 0 )
2253 if( ret
!= MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
)
2257 * Next candidates. We want to preserve Y = (X-1) / 2 and
2258 * Y = 1 mod 2 and Y = 2 mod 3 (eq X = 3 mod 4 and X = 2 mod 3)
2259 * so up Y by 6 and X by 12.
2261 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( X
, X
, 12 ) );
2262 MBEDTLS_MPI_CHK( mbedtls_mpi_add_int( &Y
, &Y
, 6 ) );
2268 mbedtls_mpi_free( &Y
);
2273 #endif /* MBEDTLS_GENPRIME */
2275 #if defined(MBEDTLS_SELF_TEST)
2277 #define GCD_PAIR_COUNT 3
2279 static const int gcd_pairs
[GCD_PAIR_COUNT
][3] =
2283 { 768454923, 542167814, 1 }
2289 int mbedtls_mpi_self_test( int verbose
)
2292 mbedtls_mpi A
, E
, N
, X
, Y
, U
, V
;
2294 mbedtls_mpi_init( &A
); mbedtls_mpi_init( &E
); mbedtls_mpi_init( &N
); mbedtls_mpi_init( &X
);
2295 mbedtls_mpi_init( &Y
); mbedtls_mpi_init( &U
); mbedtls_mpi_init( &V
);
2297 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &A
, 16,
2298 "EFE021C2645FD1DC586E69184AF4A31E" \
2299 "D5F53E93B5F123FA41680867BA110131" \
2300 "944FE7952E2517337780CB0DB80E61AA" \
2301 "E7C8DDC6C5C6AADEB34EB38A2F40D5E6" ) );
2303 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &E
, 16,
2304 "B2E7EFD37075B9F03FF989C7C5051C20" \
2305 "34D2A323810251127E7BF8625A4F49A5" \
2306 "F3E27F4DA8BD59C47D6DAABA4C8127BD" \
2307 "5B5C25763222FEFCCFC38B832366C29E" ) );
2309 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &N
, 16,
2310 "0066A198186C18C10B2F5ED9B522752A" \
2311 "9830B69916E535C8F047518A889A43A5" \
2312 "94B6BED27A168D31D4A52F88925AA8F5" ) );
2314 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &X
, &A
, &N
) );
2316 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2317 "602AB7ECA597A3D6B56FF9829A5E8B85" \
2318 "9E857EA95A03512E2BAE7391688D264A" \
2319 "A5663B0341DB9CCFD2C4C5F421FEC814" \
2320 "8001B72E848A38CAE1C65F78E56ABDEF" \
2321 "E12D3C039B8A02D6BE593F0BBBDA56F1" \
2322 "ECF677152EF804370C1A305CAF3B5BF1" \
2323 "30879B56C61DE584A0F53A2447A51E" ) );
2326 mbedtls_printf( " MPI test #1 (mul_mpi): " );
2328 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 )
2331 mbedtls_printf( "failed\n" );
2338 mbedtls_printf( "passed\n" );
2340 MBEDTLS_MPI_CHK( mbedtls_mpi_div_mpi( &X
, &Y
, &A
, &N
) );
2342 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2343 "256567336059E52CAE22925474705F39A94" ) );
2345 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &V
, 16,
2346 "6613F26162223DF488E9CD48CC132C7A" \
2347 "0AC93C701B001B092E4E5B9F73BCD27B" \
2348 "9EE50D0657C77F374E903CDFA4C642" ) );
2351 mbedtls_printf( " MPI test #2 (div_mpi): " );
2353 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 ||
2354 mbedtls_mpi_cmp_mpi( &Y
, &V
) != 0 )
2357 mbedtls_printf( "failed\n" );
2364 mbedtls_printf( "passed\n" );
2366 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &X
, &A
, &E
, &N
, NULL
) );
2368 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2369 "36E139AEA55215609D2816998ED020BB" \
2370 "BD96C37890F65171D948E9BC7CBAA4D9" \
2371 "325D24D6A3C12710F10A09FA08AB87" ) );
2374 mbedtls_printf( " MPI test #3 (exp_mod): " );
2376 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 )
2379 mbedtls_printf( "failed\n" );
2386 mbedtls_printf( "passed\n" );
2388 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &X
, &A
, &N
) );
2390 MBEDTLS_MPI_CHK( mbedtls_mpi_read_string( &U
, 16,
2391 "003A0AAEDD7E784FC07D8F9EC6E3BFD5" \
2392 "C3DBA76456363A10869622EAC2DD84EC" \
2393 "C5B8A74DAC4D09E03B5E0BE779F2DF61" ) );
2396 mbedtls_printf( " MPI test #4 (inv_mod): " );
2398 if( mbedtls_mpi_cmp_mpi( &X
, &U
) != 0 )
2401 mbedtls_printf( "failed\n" );
2408 mbedtls_printf( "passed\n" );
2411 mbedtls_printf( " MPI test #5 (simple gcd): " );
2413 for( i
= 0; i
< GCD_PAIR_COUNT
; i
++ )
2415 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &X
, gcd_pairs
[i
][0] ) );
2416 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &Y
, gcd_pairs
[i
][1] ) );
2418 MBEDTLS_MPI_CHK( mbedtls_mpi_gcd( &A
, &X
, &Y
) );
2420 if( mbedtls_mpi_cmp_int( &A
, gcd_pairs
[i
][2] ) != 0 )
2423 mbedtls_printf( "failed at %d\n", i
);
2431 mbedtls_printf( "passed\n" );
2435 if( ret
!= 0 && verbose
!= 0 )
2436 mbedtls_printf( "Unexpected error, return code = %08X\n", ret
);
2438 mbedtls_mpi_free( &A
); mbedtls_mpi_free( &E
); mbedtls_mpi_free( &N
); mbedtls_mpi_free( &X
);
2439 mbedtls_mpi_free( &Y
); mbedtls_mpi_free( &U
); mbedtls_mpi_free( &V
);
2442 mbedtls_printf( "\n" );
2447 #endif /* MBEDTLS_SELF_TEST */
2449 #endif /* MBEDTLS_BIGNUM_C */