PolarSSL v1.3.8
bignum.h
Go to the documentation of this file.
1 
27 #ifndef POLARSSL_BIGNUM_H
28 #define POLARSSL_BIGNUM_H
29 
30 #include <stdio.h>
31 #include <string.h>
32 
33 #if !defined(POLARSSL_CONFIG_FILE)
34 #include "config.h"
35 #else
36 #include POLARSSL_CONFIG_FILE
37 #endif
38 
39 #if defined(_MSC_VER) && !defined(EFIX64) && !defined(EFI32)
40 #include <basetsd.h>
41 #if (_MSC_VER <= 1200)
42 typedef signed short int16_t;
43 typedef unsigned short uint16_t;
44 #else
45 typedef INT16 int16_t;
46 typedef UINT16 uint16_t;
47 #endif
48 typedef INT32 int32_t;
49 typedef INT64 int64_t;
50 typedef UINT32 uint32_t;
51 typedef UINT64 uint64_t;
52 #else
53 #include <inttypes.h>
54 #endif /* _MSC_VER && !EFIX64 && !EFI32 */
55 
56 #define POLARSSL_ERR_MPI_FILE_IO_ERROR -0x0002
57 #define POLARSSL_ERR_MPI_BAD_INPUT_DATA -0x0004
58 #define POLARSSL_ERR_MPI_INVALID_CHARACTER -0x0006
59 #define POLARSSL_ERR_MPI_BUFFER_TOO_SMALL -0x0008
60 #define POLARSSL_ERR_MPI_NEGATIVE_VALUE -0x000A
61 #define POLARSSL_ERR_MPI_DIVISION_BY_ZERO -0x000C
62 #define POLARSSL_ERR_MPI_NOT_ACCEPTABLE -0x000E
63 #define POLARSSL_ERR_MPI_MALLOC_FAILED -0x0010
65 #define MPI_CHK(f) do { if( ( ret = f ) != 0 ) goto cleanup; } while( 0 )
66 
67 /*
68  * Maximum size MPIs are allowed to grow to in number of limbs.
69  */
70 #define POLARSSL_MPI_MAX_LIMBS 10000
71 
72 #if !defined(POLARSSL_MPI_WINDOW_SIZE)
73 /*
74  * Maximum window size used for modular exponentiation. Default: 6
75  * Minimum value: 1. Maximum value: 6.
76  *
77  * Result is an array of ( 2 << POLARSSL_MPI_WINDOW_SIZE ) MPIs used
78  * for the sliding window calculation. (So 64 by default)
79  *
80  * Reduction in size, reduces speed.
81  */
82 #define POLARSSL_MPI_WINDOW_SIZE 6
83 #endif /* !POLARSSL_MPI_WINDOW_SIZE */
84 
85 #if !defined(POLARSSL_MPI_MAX_SIZE)
86 /*
87  * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
88  * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
89  *
90  * Note: Calculations can results temporarily in larger MPIs. So the number
91  * of limbs required (POLARSSL_MPI_MAX_LIMBS) is higher.
92  */
93 #define POLARSSL_MPI_MAX_SIZE 512
94 #endif /* !POLARSSL_MPI_MAX_SIZE */
95 
96 #define POLARSSL_MPI_MAX_BITS ( 8 * POLARSSL_MPI_MAX_SIZE )
98 /*
99  * When reading from files with mpi_read_file() and writing to files with
100  * mpi_write_file() the buffer should have space
101  * for a (short) label, the MPI (in the provided radix), the newline
102  * characters and the '\0'.
103  *
104  * By default we assume at least a 10 char label, a minimum radix of 10
105  * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
106  * Autosized at compile time for at least a 10 char label, a minimum radix
107  * of 10 (decimal) for a number of POLARSSL_MPI_MAX_BITS size.
108  *
109  * This used to be statically sized to 1250 for a maximum of 4096 bit
110  * numbers (1234 decimal chars).
111  *
112  * Calculate using the formula:
113  * POLARSSL_MPI_RW_BUFFER_SIZE = ceil(POLARSSL_MPI_MAX_BITS / ln(10) * ln(2)) +
114  * LabelSize + 6
115  */
116 #define POLARSSL_MPI_MAX_BITS_SCALE100 ( 100 * POLARSSL_MPI_MAX_BITS )
117 #define LN_2_DIV_LN_10_SCALE100 332
118 #define POLARSSL_MPI_RW_BUFFER_SIZE ( ((POLARSSL_MPI_MAX_BITS_SCALE100 + LN_2_DIV_LN_10_SCALE100 - 1) / LN_2_DIV_LN_10_SCALE100) + 10 + 6 )
119 
120 /*
121  * Define the base integer type, architecture-wise
122  */
123 #if defined(POLARSSL_HAVE_INT8)
124 typedef signed char t_sint;
125 typedef unsigned char t_uint;
126 typedef uint16_t t_udbl;
127 #define POLARSSL_HAVE_UDBL
128 #else
129 #if defined(POLARSSL_HAVE_INT16)
130 typedef int16_t t_sint;
131 typedef uint16_t t_uint;
132 typedef uint32_t t_udbl;
133 #define POLARSSL_HAVE_UDBL
134 #else
135  /*
136  * 32-bit integers can be forced on 64-bit arches (eg. for testing purposes)
137  * by defining POLARSSL_HAVE_INT32 and undefining POLARSSL_HAVE_ASM
138  */
139  #if ( ! defined(POLARSSL_HAVE_INT32) && \
140  defined(_MSC_VER) && defined(_M_AMD64) )
141  #define POLARSSL_HAVE_INT64
142  typedef int64_t t_sint;
143  typedef uint64_t t_uint;
144  #else
145  #if ( ! defined(POLARSSL_HAVE_INT32) && \
146  defined(__GNUC__) && ( \
147  defined(__amd64__) || defined(__x86_64__) || \
148  defined(__ppc64__) || defined(__powerpc64__) || \
149  defined(__ia64__) || defined(__alpha__) || \
150  (defined(__sparc__) && defined(__arch64__)) || \
151  defined(__s390x__) ) )
152  #define POLARSSL_HAVE_INT64
153  typedef int64_t t_sint;
154  typedef uint64_t t_uint;
155  typedef unsigned int t_udbl __attribute__((mode(TI)));
156  #define POLARSSL_HAVE_UDBL
157  #else
158  #define POLARSSL_HAVE_INT32
159  typedef int32_t t_sint;
160  typedef uint32_t t_uint;
161  #if ( defined(_MSC_VER) && defined(_M_IX86) )
162  typedef uint64_t t_udbl;
163  #define POLARSSL_HAVE_UDBL
164  #else
165  #if defined( POLARSSL_HAVE_LONGLONG )
166  typedef unsigned long long t_udbl;
167  #define POLARSSL_HAVE_UDBL
168  #endif
169  #endif
170  #endif /* !POLARSSL_HAVE_INT32 && __GNUC__ && 64-bit platform */
171  #endif /* !POLARSSL_HAVE_INT32 && _MSC_VER && _M_AMD64 */
172 #endif /* POLARSSL_HAVE_INT16 */
173 #endif /* POLARSSL_HAVE_INT8 */
174 
175 #ifdef __cplusplus
176 extern "C" {
177 #endif
178 
182 typedef struct
183 {
184  int s;
185  size_t n;
186  t_uint *p;
187 }
188 mpi;
189 
195 void mpi_init( mpi *X );
196 
202 void mpi_free( mpi *X );
203 
213 int mpi_grow( mpi *X, size_t nblimbs );
214 
224 int mpi_shrink( mpi *X, size_t nblimbs );
225 
235 int mpi_copy( mpi *X, const mpi *Y );
236 
243 void mpi_swap( mpi *X, mpi *Y );
244 
262 int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign );
263 
281 int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char assign );
282 
292 int mpi_lset( mpi *X, t_sint z );
293 
302 int mpi_get_bit( const mpi *X, size_t pos );
303 
318 int mpi_set_bit( mpi *X, size_t pos, unsigned char val );
319 
328 size_t mpi_lsb( const mpi *X );
329 
338 size_t mpi_msb( const mpi *X );
339 
345 size_t mpi_size( const mpi *X );
346 
356 int mpi_read_string( mpi *X, int radix, const char *s );
357 
373 int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen );
374 
375 #if defined(POLARSSL_FS_IO)
376 
387 int mpi_read_file( mpi *X, int radix, FILE *fin );
388 
401 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout );
402 #endif /* POLARSSL_FS_IO */
403 
414 int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen );
415 
428 int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen );
429 
439 int mpi_shift_l( mpi *X, size_t count );
440 
450 int mpi_shift_r( mpi *X, size_t count );
451 
462 int mpi_cmp_abs( const mpi *X, const mpi *Y );
463 
474 int mpi_cmp_mpi( const mpi *X, const mpi *Y );
475 
486 int mpi_cmp_int( const mpi *X, t_sint z );
487 
498 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B );
499 
510 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B );
511 
522 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B );
523 
534 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B );
535 
546 int mpi_add_int( mpi *X, const mpi *A, t_sint b );
547 
558 int mpi_sub_int( mpi *X, const mpi *A, t_sint b );
559 
570 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B );
571 
585 int mpi_mul_int( mpi *X, const mpi *A, t_sint b );
586 
601 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B );
602 
617 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b );
618 
631 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B );
632 
645 int mpi_mod_int( t_uint *r, const mpi *A, t_sint b );
646 
665 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR );
666 
678 int mpi_fill_random( mpi *X, size_t size,
679  int (*f_rng)(void *, unsigned char *, size_t),
680  void *p_rng );
681 
692 int mpi_gcd( mpi *G, const mpi *A, const mpi *B );
693 
706 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N );
707 
719 int mpi_is_prime( mpi *X,
720  int (*f_rng)(void *, unsigned char *, size_t),
721  void *p_rng );
722 
737 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
738  int (*f_rng)(void *, unsigned char *, size_t),
739  void *p_rng );
740 
746 int mpi_self_test( int verbose );
747 
748 #ifdef __cplusplus
749 }
750 #endif
751 
752 #endif /* bignum.h */