PolarSSL v1.3.7
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_CONFIG_OPTIONS)
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
84 /*
85  * Maximum size of MPIs allowed in bits and bytes for user-MPIs.
86  * ( Default: 512 bytes => 4096 bits, Maximum tested: 2048 bytes => 16384 bits )
87  *
88  * Note: Calculations can results temporarily in larger MPIs. So the number
89  * of limbs required (POLARSSL_MPI_MAX_LIMBS) is higher.
90  */
91 #define POLARSSL_MPI_MAX_SIZE 512
93 #endif /* !POLARSSL_CONFIG_OPTIONS */
94 
95 #define POLARSSL_MPI_MAX_BITS ( 8 * POLARSSL_MPI_MAX_SIZE )
97 /*
98  * When reading from files with mpi_read_file() and writing to files with
99  * mpi_write_file() the buffer should have space
100  * for a (short) label, the MPI (in the provided radix), the newline
101  * characters and the '\0'.
102  *
103  * By default we assume at least a 10 char label, a minimum radix of 10
104  * (decimal) and a maximum of 4096 bit numbers (1234 decimal chars).
105  * Autosized at compile time for at least a 10 char label, a minimum radix
106  * of 10 (decimal) for a number of POLARSSL_MPI_MAX_BITS size.
107  *
108  * This used to be statically sized to 1250 for a maximum of 4096 bit
109  * numbers (1234 decimal chars).
110  *
111  * Calculate using the formula:
112  * POLARSSL_MPI_RW_BUFFER_SIZE = ceil(POLARSSL_MPI_MAX_BITS / ln(10) * ln(2)) +
113  * LabelSize + 6
114  */
115 #define POLARSSL_MPI_MAX_BITS_SCALE100 ( 100 * POLARSSL_MPI_MAX_BITS )
116 #define LN_2_DIV_LN_10_SCALE100 332
117 #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 )
118 
119 /*
120  * Define the base integer type, architecture-wise
121  */
122 #if defined(POLARSSL_HAVE_INT8)
123 typedef signed char t_sint;
124 typedef unsigned char t_uint;
125 typedef uint16_t t_udbl;
126 #define POLARSSL_HAVE_UDBL
127 #else
128 #if defined(POLARSSL_HAVE_INT16)
129 typedef int16_t t_sint;
130 typedef uint16_t t_uint;
131 typedef uint32_t t_udbl;
132 #define POLARSSL_HAVE_UDBL
133 #else
134  /*
135  * 32-bit integers can be forced on 64-bit arches (eg. for testing purposes)
136  * by defining POLARSSL_HAVE_INT32 and undefining POARSSL_HAVE_ASM
137  */
138  #if ( ! defined(POLARSSL_HAVE_INT32) && \
139  defined(_MSC_VER) && defined(_M_AMD64) )
140  #define POLARSSL_HAVE_INT64
141  typedef int64_t t_sint;
142  typedef uint64_t t_uint;
143  #else
144  #if ( ! defined(POLARSSL_HAVE_INT32) && \
145  defined(__GNUC__) && ( \
146  defined(__amd64__) || defined(__x86_64__) || \
147  defined(__ppc64__) || defined(__powerpc64__) || \
148  defined(__ia64__) || defined(__alpha__) || \
149  (defined(__sparc__) && defined(__arch64__)) || \
150  defined(__s390x__) ) )
151  #define POLARSSL_HAVE_INT64
152  typedef int64_t t_sint;
153  typedef uint64_t t_uint;
154  typedef unsigned int t_udbl __attribute__((mode(TI)));
155  #define POLARSSL_HAVE_UDBL
156  #else
157  #define POLARSSL_HAVE_INT32
158  typedef int32_t t_sint;
159  typedef uint32_t t_uint;
160  #if ( defined(_MSC_VER) && defined(_M_IX86) )
161  typedef uint64_t t_udbl;
162  #define POLARSSL_HAVE_UDBL
163  #else
164  #if defined( POLARSSL_HAVE_LONGLONG )
165  typedef unsigned long long t_udbl;
166  #define POLARSSL_HAVE_UDBL
167  #endif
168  #endif
169  #endif
170  #endif
171 #endif /* POLARSSL_HAVE_INT16 */
172 #endif /* POLARSSL_HAVE_INT8 */
173 
174 #ifdef __cplusplus
175 extern "C" {
176 #endif
177 
181 typedef struct
182 {
183  int s;
184  size_t n;
185  t_uint *p;
186 }
187 mpi;
188 
194 void mpi_init( mpi *X );
195 
201 void mpi_free( mpi *X );
202 
212 int mpi_grow( mpi *X, size_t nblimbs );
213 
223 int mpi_shrink( mpi *X, size_t nblimbs );
224 
234 int mpi_copy( mpi *X, const mpi *Y );
235 
242 void mpi_swap( mpi *X, mpi *Y );
243 
261 int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign );
262 
280 int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char assign );
281 
291 int mpi_lset( mpi *X, t_sint z );
292 
301 int mpi_get_bit( const mpi *X, size_t pos );
302 
317 int mpi_set_bit( mpi *X, size_t pos, unsigned char val );
318 
327 size_t mpi_lsb( const mpi *X );
328 
337 size_t mpi_msb( const mpi *X );
338 
344 size_t mpi_size( const mpi *X );
345 
355 int mpi_read_string( mpi *X, int radix, const char *s );
356 
372 int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen );
373 
374 #if defined(POLARSSL_FS_IO)
375 
386 int mpi_read_file( mpi *X, int radix, FILE *fin );
387 
400 int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout );
401 #endif /* POLARSSL_FS_IO */
402 
413 int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen );
414 
425 int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen );
426 
436 int mpi_shift_l( mpi *X, size_t count );
437 
447 int mpi_shift_r( mpi *X, size_t count );
448 
459 int mpi_cmp_abs( const mpi *X, const mpi *Y );
460 
471 int mpi_cmp_mpi( const mpi *X, const mpi *Y );
472 
483 int mpi_cmp_int( const mpi *X, t_sint z );
484 
495 int mpi_add_abs( mpi *X, const mpi *A, const mpi *B );
496 
507 int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B );
508 
519 int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B );
520 
531 int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B );
532 
543 int mpi_add_int( mpi *X, const mpi *A, t_sint b );
544 
555 int mpi_sub_int( mpi *X, const mpi *A, t_sint b );
556 
567 int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B );
568 
582 int mpi_mul_int( mpi *X, const mpi *A, t_sint b );
583 
598 int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B );
599 
614 int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b );
615 
628 int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B );
629 
642 int mpi_mod_int( t_uint *r, const mpi *A, t_sint b );
643 
662 int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR );
663 
675 int mpi_fill_random( mpi *X, size_t size,
676  int (*f_rng)(void *, unsigned char *, size_t),
677  void *p_rng );
678 
689 int mpi_gcd( mpi *G, const mpi *A, const mpi *B );
690 
703 int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N );
704 
716 int mpi_is_prime( mpi *X,
717  int (*f_rng)(void *, unsigned char *, size_t),
718  void *p_rng );
719 
734 int mpi_gen_prime( mpi *X, size_t nbits, int dh_flag,
735  int (*f_rng)(void *, unsigned char *, size_t),
736  void *p_rng );
737 
743 int mpi_self_test( int verbose );
744 
745 #ifdef __cplusplus
746 }
747 #endif
748 
749 #endif /* bignum.h */
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
void mpi_swap(mpi *X, mpi *Y)
Swap the contents of X and Y.
int mpi_shrink(mpi *X, size_t nblimbs)
Resize down, keeping at least the specified number of limbs.
int mpi_safe_cond_assign(mpi *X, const mpi *Y, unsigned char assign)
Safe conditional assignement X = Y if assign is 1.
uint32_t t_uint
Definition: bignum.h:159
int mpi_div_int(mpi *Q, mpi *R, const mpi *A, t_sint b)
Division by int: A = Q * b + R.
int mpi_gcd(mpi *G, const mpi *A, const mpi *B)
Greatest common divisor: G = gcd(A, B)
int s
Definition: bignum.h:183
int mpi_fill_random(mpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an MPI X with size bytes of random.
int mpi_sub_abs(mpi *X, const mpi *A, const mpi *B)
Unsigned subtraction: X = |A| - |B|.
int mpi_cmp_abs(const mpi *X, const mpi *Y)
Compare unsigned values.
Configuration options (set of defines)
int mpi_add_int(mpi *X, const mpi *A, t_sint b)
Signed addition: X = A + b.
int mpi_read_file(mpi *X, int radix, FILE *fin)
Read X from an opened file.
int mpi_div_mpi(mpi *Q, mpi *R, const mpi *A, const mpi *B)
Division by mpi: A = Q * B + R.
int mpi_lset(mpi *X, t_sint z)
Set value from integer.
int mpi_is_prime(mpi *X, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Miller-Rabin primality test.
MPI structure.
Definition: bignum.h:181
int mpi_write_file(const char *p, const mpi *X, int radix, FILE *fout)
Write X into an opened file, or stdout if fout is NULL.
void mpi_init(mpi *X)
Initialize one MPI.
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
unsigned long long t_udbl
Definition: bignum.h:165
int mpi_shift_r(mpi *X, size_t count)
Right-shift: X &gt;&gt;= count.
int mpi_add_mpi(mpi *X, const mpi *A, const mpi *B)
Signed addition: X = A + B.
asn1_buf val
The named value.
Definition: asn1.h:155
int mpi_write_string(const mpi *X, int radix, char *s, size_t *slen)
Export into an ASCII string.
int32_t t_sint
Definition: bignum.h:158
size_t mpi_lsb(const mpi *X)
Return the number of zero-bits before the least significant &#39;1&#39; bit.
int mpi_inv_mod(mpi *X, const mpi *A, const mpi *N)
Modular inverse: X = A^-1 mod N.
void mpi_free(mpi *X)
Unallocate one MPI.
int mpi_mul_int(mpi *X, const mpi *A, t_sint b)
Baseline multiplication: X = A * b Note: despite the functon signature, b is treated as a t_uint...
int mpi_grow(mpi *X, size_t nblimbs)
Enlarge to the specified number of limbs.
int mpi_mod_int(t_uint *r, const mpi *A, t_sint b)
Modulo: r = A mod b.
int mpi_exp_mod(mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR)
Sliding-window exponentiation: X = A^E mod N.
int mpi_gen_prime(mpi *X, size_t nbits, int dh_flag, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Prime number generation.
size_t mpi_msb(const mpi *X)
Return the number of bits up to and including the most significant &#39;1&#39; bit&#39;.
int mpi_add_abs(mpi *X, const mpi *A, const mpi *B)
Unsigned addition: X = |A| + |B|.
int mpi_read_string(mpi *X, int radix, const char *s)
Import from an ASCII string.
t_uint * p
Definition: bignum.h:185
int mpi_read_binary(mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, big endian.
int mpi_self_test(int verbose)
Checkup routine.
size_t mpi_size(const mpi *X)
Return the total size in bytes.
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
size_t n
Definition: bignum.h:184
int mpi_mod_mpi(mpi *R, const mpi *A, const mpi *B)
Modulo: R = A mod B.
int mpi_get_bit(const mpi *X, size_t pos)
Get a specific bit from X.
int mpi_write_binary(const mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, big endian.
int mpi_shift_l(mpi *X, size_t count)
Left-shift: X &lt;&lt;= count.
int mpi_safe_cond_swap(mpi *X, mpi *Y, unsigned char assign)
Safe conditional swap X &lt;-&gt; Y if swap is 1.
int mpi_mul_mpi(mpi *X, const mpi *A, const mpi *B)
Baseline multiplication: X = A * B.
int mpi_sub_mpi(mpi *X, const mpi *A, const mpi *B)
Signed subtraction: X = A - B.
int mpi_set_bit(mpi *X, size_t pos, unsigned char val)
Set a bit of X to a specific value of 0 or 1.
int mpi_sub_int(mpi *X, const mpi *A, t_sint b)
Signed subtraction: X = A - b.