mbed TLS v2.16.1
bignum.h
Go to the documentation of this file.
1 
6 /*
7  * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
8  * SPDX-License-Identifier: GPL-2.0
9  *
10  * This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License along
21  * with this program; if not, write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23  *
24  * This file is part of mbed TLS (https://tls.mbed.org)
25  */
26 #ifndef MBEDTLS_BIGNUM_H
27 #define MBEDTLS_BIGNUM_H
28 
29 #if !defined(MBEDTLS_CONFIG_FILE)
30 #include "config.h"
31 #else
32 #include MBEDTLS_CONFIG_FILE
33 #endif
34 
35 #include <stddef.h>
36 #include <stdint.h>
37 
38 #if defined(MBEDTLS_FS_IO)
39 #include <stdio.h>
40 #endif
41 
42 #define MBEDTLS_ERR_MPI_FILE_IO_ERROR -0x0002
43 #define MBEDTLS_ERR_MPI_BAD_INPUT_DATA -0x0004
44 #define MBEDTLS_ERR_MPI_INVALID_CHARACTER -0x0006
45 #define MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL -0x0008
46 #define MBEDTLS_ERR_MPI_NEGATIVE_VALUE -0x000A
47 #define MBEDTLS_ERR_MPI_DIVISION_BY_ZERO -0x000C
48 #define MBEDTLS_ERR_MPI_NOT_ACCEPTABLE -0x000E
49 #define MBEDTLS_ERR_MPI_ALLOC_FAILED -0x0010
51 #define MBEDTLS_MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
52 
53 /*
54  * Maximum size MPIs are allowed to grow to in number of limbs.
55  */
56 #define MBEDTLS_MPI_MAX_LIMBS 10000
57 
58 #if !defined(MBEDTLS_MPI_WINDOW_SIZE)
59 /*
60  * Maximum window size used for modular exponentiation. Default: 6
61  * Minimum value: 1. Maximum value: 6.
62  *
63  * Result is an array of ( 2 << MBEDTLS_MPI_WINDOW_SIZE ) MPIs used
64  * for the sliding window calculation. (So 64 by default)
65  *
66  * Reduction in size, reduces speed.
67  */
68 #define MBEDTLS_MPI_WINDOW_SIZE 6
69 #endif /* !MBEDTLS_MPI_WINDOW_SIZE */
70 
71 #if !defined(MBEDTLS_MPI_MAX_SIZE)
72 /*
73  * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
74  * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
75  *
76  * Note: Calculations can temporarily result in larger MPIs. So the number
77  * of limbs required (MBEDTLS_MPI_MAX_LIMBS) is higher.
78  */
79 #define MBEDTLS_MPI_MAX_SIZE 1024
80 #endif /* !MBEDTLS_MPI_MAX_SIZE */
81 
82 #define MBEDTLS_MPI_MAX_BITS ( 8 * MBEDTLS_MPI_MAX_SIZE )
84 /*
85  * When reading from files with mbedtls_mpi_read_file() and writing to files with
86  * mbedtls_mpi_write_file() the buffer should have space
87  * for a (short) label, the MPI (in the provided radix), the newline
88  * characters and the '\0'.
89  *
90  * By default we assume at least a 10 char label, a minimum radix of 10
91  * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
92  * Autosized at compile time for at least a 10 char label, a minimum radix
93  * of 10 (decimal) for a number of MBEDTLS_MPI_MAX_BITS size.
94  *
95  * This used to be statically sized to 1250 for a maximum of 4096 bit
96  * numbers (1234 decimal chars).
97  *
98  * Calculate using the formula:
99  * MBEDTLS_MPI_RW_BUFFER_SIZE = ceil(MBEDTLS_MPI_MAX_BITS / ln(10) * ln(2)) +
100  * LabelSize + 6
101  */
102 #define MBEDTLS_MPI_MAX_BITS_SCALE100 ( 100 * MBEDTLS_MPI_MAX_BITS )
103 #define MBEDTLS_LN_2_DIV_LN_10_SCALE100 332
104 #define MBEDTLS_MPI_RW_BUFFER_SIZE ( ((MBEDTLS_MPI_MAX_BITS_SCALE100 + MBEDTLS_LN_2_DIV_LN_10_SCALE100 - 1) / MBEDTLS_LN_2_DIV_LN_10_SCALE100) + 10 + 6 )
105 
106 /*
107  * Define the base integer type, architecture-wise.
108  *
109  * 32 or 64-bit integer types can be forced regardless of the underlying
110  * architecture by defining MBEDTLS_HAVE_INT32 or MBEDTLS_HAVE_INT64
111  * respectively and undefining MBEDTLS_HAVE_ASM.
112  *
113  * Double-width integers (e.g. 128-bit in 64-bit architectures) can be
114  * disabled by defining MBEDTLS_NO_UDBL_DIVISION.
115  */
116 #if !defined(MBEDTLS_HAVE_INT32)
117  #if defined(_MSC_VER) && defined(_M_AMD64)
118  /* Always choose 64-bit when using MSC */
119  #if !defined(MBEDTLS_HAVE_INT64)
120  #define MBEDTLS_HAVE_INT64
121  #endif /* !MBEDTLS_HAVE_INT64 */
122  typedef int64_t mbedtls_mpi_sint;
123  typedef uint64_t mbedtls_mpi_uint;
124  #elif defined(__GNUC__) && ( \
125  defined(__amd64__) || defined(__x86_64__) || \
126  defined(__ppc64__) || defined(__powerpc64__) || \
127  defined(__ia64__) || defined(__alpha__) || \
128  ( defined(__sparc__) && defined(__arch64__) ) || \
129  defined(__s390x__) || defined(__mips64) )
130  #if !defined(MBEDTLS_HAVE_INT64)
131  #define MBEDTLS_HAVE_INT64
132  #endif /* MBEDTLS_HAVE_INT64 */
133  typedef int64_t mbedtls_mpi_sint;
134  typedef uint64_t mbedtls_mpi_uint;
135  #if !defined(MBEDTLS_NO_UDBL_DIVISION)
136  /* mbedtls_t_udbl defined as 128-bit unsigned int */
137  typedef unsigned int mbedtls_t_udbl __attribute__((mode(TI)));
138  #define MBEDTLS_HAVE_UDBL
139  #endif /* !MBEDTLS_NO_UDBL_DIVISION */
140  #elif defined(__ARMCC_VERSION) && defined(__aarch64__)
141  /*
142  * __ARMCC_VERSION is defined for both armcc and armclang and
143  * __aarch64__ is only defined by armclang when compiling 64-bit code
144  */
145  #if !defined(MBEDTLS_HAVE_INT64)
146  #define MBEDTLS_HAVE_INT64
147  #endif /* !MBEDTLS_HAVE_INT64 */
148  typedef int64_t mbedtls_mpi_sint;
149  typedef uint64_t mbedtls_mpi_uint;
150  #if !defined(MBEDTLS_NO_UDBL_DIVISION)
151  /* mbedtls_t_udbl defined as 128-bit unsigned int */
152  typedef __uint128_t mbedtls_t_udbl;
153  #define MBEDTLS_HAVE_UDBL
154  #endif /* !MBEDTLS_NO_UDBL_DIVISION */
155  #elif defined(MBEDTLS_HAVE_INT64)
156  /* Force 64-bit integers with unknown compiler */
157  typedef int64_t mbedtls_mpi_sint;
158  typedef uint64_t mbedtls_mpi_uint;
159  #endif
160 #endif /* !MBEDTLS_HAVE_INT32 */
161 
162 #if !defined(MBEDTLS_HAVE_INT64)
163  /* Default to 32-bit compilation */
164  #if !defined(MBEDTLS_HAVE_INT32)
165  #define MBEDTLS_HAVE_INT32
166  #endif /* !MBEDTLS_HAVE_INT32 */
167  typedef int32_t mbedtls_mpi_sint;
168  typedef uint32_t mbedtls_mpi_uint;
169  #if !defined(MBEDTLS_NO_UDBL_DIVISION)
170  typedef uint64_t mbedtls_t_udbl;
171  #define MBEDTLS_HAVE_UDBL
172  #endif /* !MBEDTLS_NO_UDBL_DIVISION */
173 #endif /* !MBEDTLS_HAVE_INT64 */
174 
175 #ifdef __cplusplus
176 extern "C" {
177 #endif
178 
182 typedef struct mbedtls_mpi
183 {
184  int s;
185  size_t n;
186  mbedtls_mpi_uint *p;
187 }
189 
198 void mbedtls_mpi_init( mbedtls_mpi *X );
199 
207 void mbedtls_mpi_free( mbedtls_mpi *X );
208 
222 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs );
223 
239 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs );
240 
254 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y );
255 
263 
288 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign );
289 
313 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign );
314 
325 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z );
326 
337 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos );
338 
354 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val );
355 
368 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X );
369 
382 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X );
383 
397 size_t mbedtls_mpi_size( const mbedtls_mpi *X );
398 
409 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s );
410 
433 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
434  char *buf, size_t buflen, size_t *olen );
435 
436 #if defined(MBEDTLS_FS_IO)
437 
458 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin );
459 
475 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X,
476  int radix, FILE *fout );
477 #endif /* MBEDTLS_FS_IO */
478 
491 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf,
492  size_t buflen );
493 
508 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf,
509  size_t buflen );
510 
521 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count );
522 
533 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count );
534 
545 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y );
546 
557 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y );
558 
569 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z );
570 
583  const mbedtls_mpi *B );
584 
598  const mbedtls_mpi *B );
599 
612  const mbedtls_mpi *B );
613 
626  const mbedtls_mpi *B );
627 
640  mbedtls_mpi_sint b );
641 
655  mbedtls_mpi_sint b );
656 
670  const mbedtls_mpi *B );
671 
686  mbedtls_mpi_uint b );
687 
707  const mbedtls_mpi *B );
708 
728  mbedtls_mpi_sint b );
729 
748  const mbedtls_mpi *B );
749 
766 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A,
767  mbedtls_mpi_sint b );
768 
796  const mbedtls_mpi *E, const mbedtls_mpi *N,
797  mbedtls_mpi *_RR );
798 
816 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
817  int (*f_rng)(void *, unsigned char *, size_t),
818  void *p_rng );
819 
831 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A,
832  const mbedtls_mpi *B );
833 
851  const mbedtls_mpi *N );
852 
853 #if !defined(MBEDTLS_DEPRECATED_REMOVED)
854 #if defined(MBEDTLS_DEPRECATED_WARNING)
855 #define MBEDTLS_DEPRECATED __attribute__((deprecated))
856 #else
857 #define MBEDTLS_DEPRECATED
858 #endif
859 
879  int (*f_rng)(void *, unsigned char *, size_t),
880  void *p_rng );
881 #undef MBEDTLS_DEPRECATED
882 #endif /* !MBEDTLS_DEPRECATED_REMOVED */
883 
911 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
912  int (*f_rng)(void *, unsigned char *, size_t),
913  void *p_rng );
920 typedef enum {
924 
944 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
945  int (*f_rng)(void *, unsigned char *, size_t),
946  void *p_rng );
947 
948 #if defined(MBEDTLS_SELF_TEST)
949 
955 int mbedtls_mpi_self_test( int verbose );
956 
957 #endif /* MBEDTLS_SELF_TEST */
958 
959 #ifdef __cplusplus
960 }
961 #endif
962 
963 #endif /* bignum.h */