PolarSSL v1.3.9
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)
42typedef signed short int16_t;
43typedef unsigned short uint16_t;
44#else
45typedef INT16 int16_t;
46typedef UINT16 uint16_t;
47#endif
48typedef INT32 int32_t;
49typedef INT64 int64_t;
50typedef UINT32 uint32_t;
51typedef 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 1024
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)
124typedef signed char t_sint;
125typedef unsigned char t_uint;
126typedef uint16_t t_udbl;
127#define POLARSSL_HAVE_UDBL
128#else
129#if defined(POLARSSL_HAVE_INT16)
130typedef int16_t t_sint;
131typedef uint16_t t_uint;
132typedef 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
176extern "C" {
177#endif
178
182typedef struct
183{
184 int s;
185 size_t n;
186 t_uint *p;
187}
188mpi;
189
195void mpi_init( mpi *X );
196
202void mpi_free( mpi *X );
203
213int mpi_grow( mpi *X, size_t nblimbs );
214
224int mpi_shrink( mpi *X, size_t nblimbs );
225
235int mpi_copy( mpi *X, const mpi *Y );
236
243void mpi_swap( mpi *X, mpi *Y );
244
262int mpi_safe_cond_assign( mpi *X, const mpi *Y, unsigned char assign );
263
281int mpi_safe_cond_swap( mpi *X, mpi *Y, unsigned char assign );
282
292int mpi_lset( mpi *X, t_sint z );
293
302int mpi_get_bit( const mpi *X, size_t pos );
303
318int mpi_set_bit( mpi *X, size_t pos, unsigned char val );
319
328size_t mpi_lsb( const mpi *X );
329
338size_t mpi_msb( const mpi *X );
339
345size_t mpi_size( const mpi *X );
346
356int mpi_read_string( mpi *X, int radix, const char *s );
357
373int mpi_write_string( const mpi *X, int radix, char *s, size_t *slen );
374
375#if defined(POLARSSL_FS_IO)
387int mpi_read_file( mpi *X, int radix, FILE *fin );
388
401int mpi_write_file( const char *p, const mpi *X, int radix, FILE *fout );
402#endif /* POLARSSL_FS_IO */
403
414int mpi_read_binary( mpi *X, const unsigned char *buf, size_t buflen );
415
428int mpi_write_binary( const mpi *X, unsigned char *buf, size_t buflen );
429
439int mpi_shift_l( mpi *X, size_t count );
440
450int mpi_shift_r( mpi *X, size_t count );
451
462int mpi_cmp_abs( const mpi *X, const mpi *Y );
463
474int mpi_cmp_mpi( const mpi *X, const mpi *Y );
475
486int mpi_cmp_int( const mpi *X, t_sint z );
487
498int mpi_add_abs( mpi *X, const mpi *A, const mpi *B );
499
510int mpi_sub_abs( mpi *X, const mpi *A, const mpi *B );
511
522int mpi_add_mpi( mpi *X, const mpi *A, const mpi *B );
523
534int mpi_sub_mpi( mpi *X, const mpi *A, const mpi *B );
535
546int mpi_add_int( mpi *X, const mpi *A, t_sint b );
547
558int mpi_sub_int( mpi *X, const mpi *A, t_sint b );
559
570int mpi_mul_mpi( mpi *X, const mpi *A, const mpi *B );
571
585int mpi_mul_int( mpi *X, const mpi *A, t_sint b );
586
601int mpi_div_mpi( mpi *Q, mpi *R, const mpi *A, const mpi *B );
602
617int mpi_div_int( mpi *Q, mpi *R, const mpi *A, t_sint b );
618
631int mpi_mod_mpi( mpi *R, const mpi *A, const mpi *B );
632
645int mpi_mod_int( t_uint *r, const mpi *A, t_sint b );
646
665int mpi_exp_mod( mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR );
666
678int mpi_fill_random( mpi *X, size_t size,
679 int (*f_rng)(void *, unsigned char *, size_t),
680 void *p_rng );
681
692int mpi_gcd( mpi *G, const mpi *A, const mpi *B );
693
706int mpi_inv_mod( mpi *X, const mpi *A, const mpi *N );
707
719int mpi_is_prime( mpi *X,
720 int (*f_rng)(void *, unsigned char *, size_t),
721 void *p_rng );
722
737int 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
746int mpi_self_test( int verbose );
747
748#ifdef __cplusplus
749}
750#endif
751
752#endif /* bignum.h */
mpi_lset
int mpi_lset(mpi *X, t_sint z)
Set value from integer.
mpi_shift_r
int mpi_shift_r(mpi *X, size_t count)
Right-shift: X >>= count.
mpi_read_binary
int mpi_read_binary(mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, big endian.
mpi_mod_mpi
int mpi_mod_mpi(mpi *R, const mpi *A, const mpi *B)
Modulo: R = A mod B.
mpi_div_mpi
int mpi_div_mpi(mpi *Q, mpi *R, const mpi *A, const mpi *B)
Division by mpi: A = Q * B + R.
mpi_inv_mod
int mpi_inv_mod(mpi *X, const mpi *A, const mpi *N)
Modular inverse: X = A^-1 mod N.
mpi_sub_mpi
int mpi_sub_mpi(mpi *X, const mpi *A, const mpi *B)
Signed subtraction: X = A - B.
t_udbl
unsigned long long t_udbl
Definition bignum.h:166
mpi_shift_l
int mpi_shift_l(mpi *X, size_t count)
Left-shift: X <<= count.
mpi_sub_abs
int mpi_sub_abs(mpi *X, const mpi *A, const mpi *B)
Unsigned subtraction: X = |A| - |B|.
mpi_init
void mpi_init(mpi *X)
Initialize one MPI.
mpi_gen_prime
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.
mpi_add_int
int mpi_add_int(mpi *X, const mpi *A, t_sint b)
Signed addition: X = A + b.
mpi_safe_cond_assign
int mpi_safe_cond_assign(mpi *X, const mpi *Y, unsigned char assign)
Safe conditional assignement X = Y if assign is 1.
mpi_msb
size_t mpi_msb(const mpi *X)
Return the number of bits up to and including the most significant '1' bit'.
mpi_swap
void mpi_swap(mpi *X, mpi *Y)
Swap the contents of X and Y.
mpi_div_int
int mpi_div_int(mpi *Q, mpi *R, const mpi *A, t_sint b)
Division by int: A = Q * b + R.
mpi_fill_random
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.
mpi_add_abs
int mpi_add_abs(mpi *X, const mpi *A, const mpi *B)
Unsigned addition: X = |A| + |B|.
mpi_write_binary
int mpi_write_binary(const mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, big endian.
mpi_write_file
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.
mpi_cmp_abs
int mpi_cmp_abs(const mpi *X, const mpi *Y)
Compare unsigned values.
mpi_lsb
size_t mpi_lsb(const mpi *X)
Return the number of zero-bits before the least significant '1' bit.
mpi_copy
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
mpi_read_string
int mpi_read_string(mpi *X, int radix, const char *s)
Import from an ASCII string.
mpi_mul_int
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.
mpi_exp_mod
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.
mpi_size
size_t mpi_size(const mpi *X)
Return the total size in bytes.
mpi_mod_int
int mpi_mod_int(t_uint *r, const mpi *A, t_sint b)
Modulo: r = A mod b.
mpi_safe_cond_swap
int mpi_safe_cond_swap(mpi *X, mpi *Y, unsigned char assign)
Safe conditional swap X <-> Y if swap is 1.
mpi_get_bit
int mpi_get_bit(const mpi *X, size_t pos)
Get a specific bit from X.
mpi_read_file
int mpi_read_file(mpi *X, int radix, FILE *fin)
Read X from an opened file.
mpi_write_string
int mpi_write_string(const mpi *X, int radix, char *s, size_t *slen)
Export into an ASCII string.
mpi_gcd
int mpi_gcd(mpi *G, const mpi *A, const mpi *B)
Greatest common divisor: G = gcd(A, B)
mpi_self_test
int mpi_self_test(int verbose)
Checkup routine.
mpi_mul_mpi
int mpi_mul_mpi(mpi *X, const mpi *A, const mpi *B)
Baseline multiplication: X = A * B.
t_sint
int32_t t_sint
Definition bignum.h:159
mpi_grow
int mpi_grow(mpi *X, size_t nblimbs)
Enlarge to the specified number of limbs.
mpi_set_bit
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.
mpi_sub_int
int mpi_sub_int(mpi *X, const mpi *A, t_sint b)
Signed subtraction: X = A - b.
t_uint
uint32_t t_uint
Definition bignum.h:160
mpi_shrink
int mpi_shrink(mpi *X, size_t nblimbs)
Resize down, keeping at least the specified number of limbs.
mpi_is_prime
int mpi_is_prime(mpi *X, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Miller-Rabin primality test.
mpi_add_mpi
int mpi_add_mpi(mpi *X, const mpi *A, const mpi *B)
Signed addition: X = A + B.
mpi_free
void mpi_free(mpi *X)
Unallocate one MPI.
mpi_cmp_mpi
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
mpi_cmp_int
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
config.h
Configuration options (set of defines)
mpi
MPI structure.
Definition bignum.h:183
mpi::p
t_uint * p
Definition bignum.h:186
mpi::n
size_t n
Definition bignum.h:185
mpi::s
int s
Definition bignum.h:184
Generated on Tue Feb 20 2024 18:30:49 for PolarSSL v1.3.9 by doxygen 1.9.8