mbed TLS v2.14.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: Apache-2.0
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License"); you may
11  * not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
18  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  *
22  * This file is part of mbed TLS (https://tls.mbed.org)
23  */
24 #ifndef MBEDTLS_BIGNUM_H
25 #define MBEDTLS_BIGNUM_H
26 
27 #if !defined(MBEDTLS_CONFIG_FILE)
28 #include "config.h"
29 #else
30 #include MBEDTLS_CONFIG_FILE
31 #endif
32 
33 #include <stddef.h>
34 #include <stdint.h>
35 
36 #if defined(MBEDTLS_FS_IO)
37 #include <stdio.h>
38 #endif
39 
40 #define MBEDTLS_ERR_MPI_FILE_IO_ERROR -0x0002
41 #define MBEDTLS_ERR_MPI_BAD_INPUT_DATA -0x0004
42 #define MBEDTLS_ERR_MPI_INVALID_CHARACTER -0x0006
43 #define MBEDTLS_ERR_MPI_BUFFER_TOO_SMALL -0x0008
44 #define MBEDTLS_ERR_MPI_NEGATIVE_VALUE -0x000A
45 #define MBEDTLS_ERR_MPI_DIVISION_BY_ZERO -0x000C
46 #define MBEDTLS_ERR_MPI_NOT_ACCEPTABLE -0x000E
47 #define MBEDTLS_ERR_MPI_ALLOC_FAILED -0x0010
49 #define MBEDTLS_MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
50 
51 /*
52  * Maximum size MPIs are allowed to grow to in number of limbs.
53  */
54 #define MBEDTLS_MPI_MAX_LIMBS 10000
55 
56 #if !defined(MBEDTLS_MPI_WINDOW_SIZE)
57 /*
58  * Maximum window size used for modular exponentiation. Default: 6
59  * Minimum value: 1. Maximum value: 6.
60  *
61  * Result is an array of ( 2 << MBEDTLS_MPI_WINDOW_SIZE ) MPIs used
62  * for the sliding window calculation. (So 64 by default)
63  *
64  * Reduction in size, reduces speed.
65  */
66 #define MBEDTLS_MPI_WINDOW_SIZE 6
67 #endif /* !MBEDTLS_MPI_WINDOW_SIZE */
68 
69 #if !defined(MBEDTLS_MPI_MAX_SIZE)
70 /*
71  * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
72  * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
73  *
74  * Note: Calculations can temporarily result in larger MPIs. So the number
75  * of limbs required (MBEDTLS_MPI_MAX_LIMBS) is higher.
76  */
77 #define MBEDTLS_MPI_MAX_SIZE 1024
78 #endif /* !MBEDTLS_MPI_MAX_SIZE */
79 
80 #define MBEDTLS_MPI_MAX_BITS ( 8 * MBEDTLS_MPI_MAX_SIZE )
82 /*
83  * When reading from files with mbedtls_mpi_read_file() and writing to files with
84  * mbedtls_mpi_write_file() the buffer should have space
85  * for a (short) label, the MPI (in the provided radix), the newline
86  * characters and the '\0'.
87  *
88  * By default we assume at least a 10 char label, a minimum radix of 10
89  * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
90  * Autosized at compile time for at least a 10 char label, a minimum radix
91  * of 10 (decimal) for a number of MBEDTLS_MPI_MAX_BITS size.
92  *
93  * This used to be statically sized to 1250 for a maximum of 4096 bit
94  * numbers (1234 decimal chars).
95  *
96  * Calculate using the formula:
97  * MBEDTLS_MPI_RW_BUFFER_SIZE = ceil(MBEDTLS_MPI_MAX_BITS / ln(10) * ln(2)) +
98  * LabelSize + 6
99  */
100 #define MBEDTLS_MPI_MAX_BITS_SCALE100 ( 100 * MBEDTLS_MPI_MAX_BITS )
101 #define MBEDTLS_LN_2_DIV_LN_10_SCALE100 332
102 #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 )
103 
104 /*
105  * Define the base integer type, architecture-wise.
106  *
107  * 32 or 64-bit integer types can be forced regardless of the underlying
108  * architecture by defining MBEDTLS_HAVE_INT32 or MBEDTLS_HAVE_INT64
109  * respectively and undefining MBEDTLS_HAVE_ASM.
110  *
111  * Double-width integers (e.g. 128-bit in 64-bit architectures) can be
112  * disabled by defining MBEDTLS_NO_UDBL_DIVISION.
113  */
114 #if !defined(MBEDTLS_HAVE_INT32)
115  #if defined(_MSC_VER) && defined(_M_AMD64)
116  /* Always choose 64-bit when using MSC */
117  #if !defined(MBEDTLS_HAVE_INT64)
118  #define MBEDTLS_HAVE_INT64
119  #endif /* !MBEDTLS_HAVE_INT64 */
120  typedef int64_t mbedtls_mpi_sint;
121  typedef uint64_t mbedtls_mpi_uint;
122  #elif defined(__GNUC__) && ( \
123  defined(__amd64__) || defined(__x86_64__) || \
124  defined(__ppc64__) || defined(__powerpc64__) || \
125  defined(__ia64__) || defined(__alpha__) || \
126  ( defined(__sparc__) && defined(__arch64__) ) || \
127  defined(__s390x__) || defined(__mips64) )
128  #if !defined(MBEDTLS_HAVE_INT64)
129  #define MBEDTLS_HAVE_INT64
130  #endif /* MBEDTLS_HAVE_INT64 */
131  typedef int64_t mbedtls_mpi_sint;
132  typedef uint64_t mbedtls_mpi_uint;
133  #if !defined(MBEDTLS_NO_UDBL_DIVISION)
134  /* mbedtls_t_udbl defined as 128-bit unsigned int */
135  typedef unsigned int mbedtls_t_udbl __attribute__((mode(TI)));
136  #define MBEDTLS_HAVE_UDBL
137  #endif /* !MBEDTLS_NO_UDBL_DIVISION */
138  #elif defined(__ARMCC_VERSION) && defined(__aarch64__)
139  /*
140  * __ARMCC_VERSION is defined for both armcc and armclang and
141  * __aarch64__ is only defined by armclang when compiling 64-bit code
142  */
143  #if !defined(MBEDTLS_HAVE_INT64)
144  #define MBEDTLS_HAVE_INT64
145  #endif /* !MBEDTLS_HAVE_INT64 */
146  typedef int64_t mbedtls_mpi_sint;
147  typedef uint64_t mbedtls_mpi_uint;
148  #if !defined(MBEDTLS_NO_UDBL_DIVISION)
149  /* mbedtls_t_udbl defined as 128-bit unsigned int */
150  typedef __uint128_t mbedtls_t_udbl;
151  #define MBEDTLS_HAVE_UDBL
152  #endif /* !MBEDTLS_NO_UDBL_DIVISION */
153  #elif defined(MBEDTLS_HAVE_INT64)
154  /* Force 64-bit integers with unknown compiler */
155  typedef int64_t mbedtls_mpi_sint;
156  typedef uint64_t mbedtls_mpi_uint;
157  #endif
158 #endif /* !MBEDTLS_HAVE_INT32 */
159 
160 #if !defined(MBEDTLS_HAVE_INT64)
161  /* Default to 32-bit compilation */
162  #if !defined(MBEDTLS_HAVE_INT32)
163  #define MBEDTLS_HAVE_INT32
164  #endif /* !MBEDTLS_HAVE_INT32 */
165  typedef int32_t mbedtls_mpi_sint;
166  typedef uint32_t mbedtls_mpi_uint;
167  #if !defined(MBEDTLS_NO_UDBL_DIVISION)
168  typedef uint64_t mbedtls_t_udbl;
169  #define MBEDTLS_HAVE_UDBL
170  #endif /* !MBEDTLS_NO_UDBL_DIVISION */
171 #endif /* !MBEDTLS_HAVE_INT64 */
172 
173 #ifdef __cplusplus
174 extern "C" {
175 #endif
176 
180 typedef struct mbedtls_mpi
181 {
182  int s;
183  size_t n;
184  mbedtls_mpi_uint *p;
185 }
187 
195 void mbedtls_mpi_init( mbedtls_mpi *X );
196 
202 void mbedtls_mpi_free( mbedtls_mpi *X );
203 
215 int mbedtls_mpi_grow( mbedtls_mpi *X, size_t nblimbs );
216 
230 int mbedtls_mpi_shrink( mbedtls_mpi *X, size_t nblimbs );
231 
241 int mbedtls_mpi_copy( mbedtls_mpi *X, const mbedtls_mpi *Y );
242 
250 
268 int mbedtls_mpi_safe_cond_assign( mbedtls_mpi *X, const mbedtls_mpi *Y, unsigned char assign );
269 
287 int mbedtls_mpi_safe_cond_swap( mbedtls_mpi *X, mbedtls_mpi *Y, unsigned char assign );
288 
298 int mbedtls_mpi_lset( mbedtls_mpi *X, mbedtls_mpi_sint z );
299 
308 int mbedtls_mpi_get_bit( const mbedtls_mpi *X, size_t pos );
309 
324 int mbedtls_mpi_set_bit( mbedtls_mpi *X, size_t pos, unsigned char val );
325 
334 size_t mbedtls_mpi_lsb( const mbedtls_mpi *X );
335 
344 size_t mbedtls_mpi_bitlen( const mbedtls_mpi *X );
345 
351 size_t mbedtls_mpi_size( const mbedtls_mpi *X );
352 
362 int mbedtls_mpi_read_string( mbedtls_mpi *X, int radix, const char *s );
363 
380 int mbedtls_mpi_write_string( const mbedtls_mpi *X, int radix,
381  char *buf, size_t buflen, size_t *olen );
382 
383 #if defined(MBEDTLS_FS_IO)
384 
404 int mbedtls_mpi_read_file( mbedtls_mpi *X, int radix, FILE *fin );
405 
418 int mbedtls_mpi_write_file( const char *p, const mbedtls_mpi *X, int radix, FILE *fout );
419 #endif /* MBEDTLS_FS_IO */
420 
431 int mbedtls_mpi_read_binary( mbedtls_mpi *X, const unsigned char *buf, size_t buflen );
432 
445 int mbedtls_mpi_write_binary( const mbedtls_mpi *X, unsigned char *buf, size_t buflen );
446 
456 int mbedtls_mpi_shift_l( mbedtls_mpi *X, size_t count );
457 
467 int mbedtls_mpi_shift_r( mbedtls_mpi *X, size_t count );
468 
479 int mbedtls_mpi_cmp_abs( const mbedtls_mpi *X, const mbedtls_mpi *Y );
480 
491 int mbedtls_mpi_cmp_mpi( const mbedtls_mpi *X, const mbedtls_mpi *Y );
492 
503 int mbedtls_mpi_cmp_int( const mbedtls_mpi *X, mbedtls_mpi_sint z );
504 
515 int mbedtls_mpi_add_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
516 
527 int mbedtls_mpi_sub_abs( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
528 
539 int mbedtls_mpi_add_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
540 
551 int mbedtls_mpi_sub_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
552 
563 int mbedtls_mpi_add_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b );
564 
575 int mbedtls_mpi_sub_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_sint b );
576 
587 int mbedtls_mpi_mul_mpi( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *B );
588 
601 int mbedtls_mpi_mul_int( mbedtls_mpi *X, const mbedtls_mpi *A, mbedtls_mpi_uint b );
602 
617 int mbedtls_mpi_div_mpi( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B );
618 
633 int mbedtls_mpi_div_int( mbedtls_mpi *Q, mbedtls_mpi *R, const mbedtls_mpi *A, mbedtls_mpi_sint b );
634 
647 int mbedtls_mpi_mod_mpi( mbedtls_mpi *R, const mbedtls_mpi *A, const mbedtls_mpi *B );
648 
661 int mbedtls_mpi_mod_int( mbedtls_mpi_uint *r, const mbedtls_mpi *A, mbedtls_mpi_sint b );
662 
681 int mbedtls_mpi_exp_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *E, const mbedtls_mpi *N, mbedtls_mpi *_RR );
682 
698 int mbedtls_mpi_fill_random( mbedtls_mpi *X, size_t size,
699  int (*f_rng)(void *, unsigned char *, size_t),
700  void *p_rng );
701 
712 int mbedtls_mpi_gcd( mbedtls_mpi *G, const mbedtls_mpi *A, const mbedtls_mpi *B );
713 
726 int mbedtls_mpi_inv_mod( mbedtls_mpi *X, const mbedtls_mpi *A, const mbedtls_mpi *N );
727 
728 #if !defined(MBEDTLS_DEPRECATED_REMOVED)
729 #if defined(MBEDTLS_DEPRECATED_WARNING)
730 #define MBEDTLS_DEPRECATED __attribute__((deprecated))
731 #else
732 #define MBEDTLS_DEPRECATED
733 #endif
734 
750  int (*f_rng)(void *, unsigned char *, size_t),
751  void *p_rng );
752 #undef MBEDTLS_DEPRECATED
753 #endif /* !MBEDTLS_DEPRECATED_REMOVED */
754 
778 int mbedtls_mpi_is_prime_ext( const mbedtls_mpi *X, int rounds,
779  int (*f_rng)(void *, unsigned char *, size_t),
780  void *p_rng );
787 typedef enum {
791 
806 int mbedtls_mpi_gen_prime( mbedtls_mpi *X, size_t nbits, int flags,
807  int (*f_rng)(void *, unsigned char *, size_t),
808  void *p_rng );
809 
815 int mbedtls_mpi_self_test( int verbose );
816 
817 #ifdef __cplusplus
818 }
819 #endif
820 
821 #endif /* bignum.h */