My Project
Loading...
Searching...
No Matches
integer.h
1/* integer.h
2 *
3 * Copyright (C) 2006-2020 wolfSSL Inc.
4 *
5 * This file is part of wolfSSL.
6 *
7 * wolfSSL is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * wolfSSL is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
20 */
21
22
23/*
24 * Based on public domain LibTomMath 0.38 by Tom St Denis, tomstdenis@iahu.ca,
25 * http://math.libtomcrypt.com
26 */
27
28
29#ifndef WOLF_CRYPT_INTEGER_H
30#define WOLF_CRYPT_INTEGER_H
31
32/* may optionally use fast math instead, not yet supported on all platforms and
33 may not be faster on all
34*/
35#include <wolfssl/wolfcrypt/types.h> /* will set MP_xxBIT if not default */
36#ifdef WOLFSSL_SP_MATH
37 #include <wolfssl/wolfcrypt/sp_int.h>
38#elif defined(USE_FAST_MATH)
39 #include <wolfssl/wolfcrypt/tfm.h>
40#else
41
42#include <wolfssl/wolfcrypt/random.h>
43
44#ifndef CHAR_BIT
45 #include <limits.h>
46#endif
47
48#include <wolfssl/wolfcrypt/mpi_class.h>
49
50
51#ifdef __cplusplus
52extern "C" {
53
54/* C++ compilers don't like assigning void * to mp_digit * */
55#define OPT_CAST(x) (x *)
56
57#elif defined(_SH3)
58
59/* SuperH SH3 compiler doesn't like assigning voi* to mp_digit* */
60#define OPT_CAST(x) (x *)
61
62#else
63
64/* C on the other hand doesn't care */
65#define OPT_CAST(x)
66
67#endif /* __cplusplus */
68
69
70/* detect 64-bit mode if possible */
71#if defined(__x86_64__) && !(defined (_MSC_VER) && defined(__clang__))
72 #if !(defined(MP_64BIT) && defined(MP_16BIT) && defined(MP_8BIT))
73 #define MP_64BIT
74 #endif
75#endif
76/* if intel compiler doesn't provide 128 bit type don't turn on 64bit */
77#if defined(MP_64BIT) && defined(__INTEL_COMPILER) && !defined(HAVE___UINT128_T)
78 #undef MP_64BIT
79#endif
80
81
82/* allow user to define on mp_digit, mp_word, DIGIT_BIT types */
83#ifndef WOLFSSL_BIGINT_TYPES
84
85/* some default configurations.
86 *
87 * A "mp_digit" must be able to hold DIGIT_BIT + 1 bits
88 * A "mp_word" must be able to hold 2*DIGIT_BIT + 1 bits
89 *
90 * At the very least a mp_digit must be able to hold 7 bits
91 * [any size beyond that is ok provided it doesn't overflow the data type]
92 */
93#ifdef MP_8BIT
94 /* 8-bit */
95 typedef unsigned char mp_digit;
96 typedef unsigned short mp_word;
97 /* don't define DIGIT_BIT, so its calculated below */
98#elif defined(MP_16BIT)
99 /* 16-bit */
100 typedef unsigned int mp_digit;
101 typedef unsigned long mp_word;
102 /* don't define DIGIT_BIT, so its calculated below */
103#elif defined(NO_64BIT)
104 /* 32-bit forced to 16-bit */
105 typedef unsigned short mp_digit;
106 typedef unsigned int mp_word;
107 #define DIGIT_BIT 12
108#elif defined(MP_64BIT)
109 /* 64-bit */
110 /* for GCC only on supported platforms */
111 typedef unsigned long long mp_digit; /* 64 bit type, 128 uses mode(TI) */
112 typedef unsigned long mp_word __attribute__ ((mode(TI)));
113 #define DIGIT_BIT 60
114#else
115 /* 32-bit default case */
116
117 #if defined(_MSC_VER) || defined(__BORLANDC__)
118 typedef unsigned __int64 ulong64;
119 #else
120 typedef unsigned long long ulong64;
121 #endif
122
123 typedef unsigned int mp_digit; /* long could be 64 now, changed TAO */
124 typedef ulong64 mp_word;
125
126 #ifdef MP_31BIT
127 /* this is an extension that uses 31-bit digits */
128 #define DIGIT_BIT 31
129 #else
130 /* default case is 28-bit digits, defines MP_28BIT as a handy test macro */
131 #define DIGIT_BIT 28
132 #define MP_28BIT
133 #endif
134#endif
135
136#endif /* WOLFSSL_BIGINT_TYPES */
137
138/* otherwise the bits per digit is calculated automatically from the size of
139 a mp_digit */
140#ifndef DIGIT_BIT
141 #define DIGIT_BIT ((int)((CHAR_BIT * sizeof(mp_digit) - 1)))
142 /* bits per digit */
143#endif
144
145#define MP_DIGIT_BIT DIGIT_BIT
146#define MP_MASK ((((mp_digit)1)<<((mp_digit)DIGIT_BIT))-((mp_digit)1))
147#define MP_DIGIT_MAX MP_MASK
148
149/* equalities */
150#define MP_LT -1 /* less than */
151#define MP_EQ 0 /* equal to */
152#define MP_GT 1 /* greater than */
153
154#define MP_ZPOS 0 /* positive integer */
155#define MP_NEG 1 /* negative */
156
157#define MP_OKAY 0 /* ok result */
158#define MP_MEM -2 /* out of mem */
159#define MP_VAL -3 /* invalid input */
160#define MP_NOT_INF -4 /* point not at infinity */
161#define MP_RANGE MP_NOT_INF
162
163#define MP_YES 1 /* yes response */
164#define MP_NO 0 /* no response */
165
166/* Primality generation flags */
167#define LTM_PRIME_BBS 0x0001 /* BBS style prime */
168#define LTM_PRIME_SAFE 0x0002 /* Safe prime (p-1)/2 == prime */
169#define LTM_PRIME_2MSB_ON 0x0008 /* force 2nd MSB to 1 */
170
171typedef int mp_err;
172
173/* define this to use lower memory usage routines (exptmods mostly) */
174#define MP_LOW_MEM
175
176/* default precision */
177#ifndef MP_PREC
178 #ifndef MP_LOW_MEM
179 #define MP_PREC 32 /* default digits of precision */
180 #else
181 #define MP_PREC 1 /* default digits of precision */
182 #endif
183#endif
184
185/* size of comba arrays, should be at least 2 * 2**(BITS_PER_WORD -
186 BITS_PER_DIGIT*2) */
187#define MP_WARRAY ((mp_word)1 << (sizeof(mp_word) * CHAR_BIT - 2 * DIGIT_BIT + 1))
188
189#ifdef HAVE_WOLF_BIGINT
190 /* raw big integer */
191 typedef struct WC_BIGINT {
192 byte* buf;
193 word32 len;
194 void* heap;
195 } WC_BIGINT;
196 #define WOLF_BIGINT_DEFINED
197#endif
198
199/* the mp_int structure */
200typedef struct mp_int {
201 int used, alloc, sign;
202 mp_digit *dp;
203
204#ifdef HAVE_WOLF_BIGINT
205 struct WC_BIGINT raw; /* unsigned binary (big endian) */
206#endif
207} mp_int;
208
209/* wolf big int and common functions */
210#include <wolfssl/wolfcrypt/wolfmath.h>
211
212
213/* callback for mp_prime_random, should fill dst with random bytes and return
214 how many read [up to len] */
215typedef int ltm_prime_callback(unsigned char *dst, int len, void *dat);
216
217
218#define USED(m) ((m)->used)
219#define DIGIT(m,k) ((m)->dp[(k)])
220#define SIGN(m) ((m)->sign)
221
222
223/* ---> Basic Manipulations <--- */
224#define mp_iszero(a) (((a)->used == 0) ? MP_YES : MP_NO)
225#define mp_isone(a) \
226 (((((a)->used == 1)) && ((a)->dp[0] == 1u)) ? MP_YES : MP_NO)
227#define mp_iseven(a) \
228 (((a)->used > 0 && (((a)->dp[0] & 1u) == 0u)) ? MP_YES : MP_NO)
229#define mp_isodd(a) \
230 (((a)->used > 0 && (((a)->dp[0] & 1u) == 1u)) ? MP_YES : MP_NO)
231#define mp_isneg(a) (((a)->sign != MP_ZPOS) ? MP_YES : MP_NO)
232#define mp_isword(a, w) \
233 ((((a)->used == 1) && ((a)->dp[0] == w)) || ((w == 0) && ((a)->used == 0)) \
234 ? MP_YES : MP_NO)
235
236/* number of primes */
237#ifdef MP_8BIT
238 #define PRIME_SIZE 31
239#else
240 #define PRIME_SIZE 256
241#endif
242
243#ifndef MAX_INVMOD_SZ
244 #if defined(WOLFSSL_MYSQL_COMPATIBLE)
245 #define MAX_INVMOD_SZ 8192
246 #else
247 #define MAX_INVMOD_SZ 4096
248 #endif
249#endif
250
251#define mp_prime_random(a, t, size, bbs, cb, dat) \
252 mp_prime_random_ex(a, t, ((size) * 8) + 1, (bbs==1)?LTM_PRIME_BBS:0, cb, dat)
253
254#define mp_read_raw(mp, str, len) mp_read_signed_bin((mp), (str), (len))
255#define mp_raw_size(mp) mp_signed_bin_size(mp)
256#define mp_toraw(mp, str) mp_to_signed_bin((mp), (str))
257#define mp_read_mag(mp, str, len) mp_read_unsigned_bin((mp), (str), (len))
258#define mp_mag_size(mp) mp_unsigned_bin_size(mp)
259#define mp_tomag(mp, str) mp_to_unsigned_bin((mp), (str))
260
261#define MP_RADIX_BIN 2
262#define MP_RADIX_OCT 8
263#define MP_RADIX_DEC 10
264#define MP_RADIX_HEX 16
265#define MP_RADIX_MAX 64
266
267#define mp_tobinary(M, S) mp_toradix((M), (S), MP_RADIX_BIN)
268#define mp_tooctal(M, S) mp_toradix((M), (S), MP_RADIX_OCT)
269#define mp_todecimal(M, S) mp_toradix((M), (S), MP_RADIX_DEC)
270#define mp_tohex(M, S) mp_toradix((M), (S), MP_RADIX_HEX)
271
272#define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1)
273
274#if defined(HAVE_ECC) || defined(WOLFSSL_KEY_GEN) || defined(HAVE_COMP_KEY) || \
275 defined(WOLFSSL_DEBUG_MATH) || defined(DEBUG_WOLFSSL)
276extern const char *mp_s_rmap;
277#endif
278
279/* 6 functions needed by Rsa */
280MP_API int mp_init (mp_int * a);
281MP_API void mp_clear (mp_int * a);
282MP_API void mp_free (mp_int * a);
283MP_API void mp_forcezero(mp_int * a);
284MP_API int mp_unsigned_bin_size(mp_int * a);
285MP_API int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c);
286MP_API int mp_to_unsigned_bin_at_pos(int x, mp_int *t, unsigned char *b);
287MP_API int mp_to_unsigned_bin (mp_int * a, unsigned char *b);
288MP_API int mp_to_unsigned_bin_len(mp_int * a, unsigned char *b, int c);
289MP_API int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y);
290MP_API int mp_exptmod_ex (mp_int * G, mp_int * X, int digits, mp_int * P,
291 mp_int * Y);
292/* end functions needed by Rsa */
293
294/* functions added to support above needed, removed TOOM and KARATSUBA */
295MP_API int mp_count_bits (mp_int * a);
296MP_API int mp_leading_bit (mp_int * a);
297MP_API int mp_init_copy (mp_int * a, mp_int * b);
298MP_API int mp_copy (mp_int * a, mp_int * b);
299MP_API int mp_grow (mp_int * a, int size);
300MP_API int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d);
301MP_API void mp_zero (mp_int * a);
302MP_API void mp_clamp (mp_int * a);
303MP_API void mp_exch (mp_int * a, mp_int * b);
304MP_API void mp_rshd (mp_int * a, int b);
305MP_API void mp_rshb (mp_int * a, int b);
306MP_API int mp_mod_2d (mp_int * a, int b, mp_int * c);
307MP_API int mp_mul_2d (mp_int * a, int b, mp_int * c);
308MP_API int mp_lshd (mp_int * a, int b);
309MP_API int mp_abs (mp_int * a, mp_int * b);
310MP_API int mp_invmod (mp_int * a, mp_int * b, mp_int * c);
311int fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c);
312MP_API int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c);
313MP_API int mp_cmp_mag (mp_int * a, mp_int * b);
314MP_API int mp_cmp (mp_int * a, mp_int * b);
315MP_API int mp_cmp_d(mp_int * a, mp_digit b);
316MP_API int mp_set (mp_int * a, mp_digit b);
317MP_API int mp_is_bit_set (mp_int * a, mp_digit b);
318MP_API int mp_mod (mp_int * a, mp_int * b, mp_int * c);
319MP_API int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d);
320MP_API int mp_div_2(mp_int * a, mp_int * b);
321MP_API int mp_add (mp_int * a, mp_int * b, mp_int * c);
322int s_mp_add (mp_int * a, mp_int * b, mp_int * c);
323int s_mp_sub (mp_int * a, mp_int * b, mp_int * c);
324MP_API int mp_sub (mp_int * a, mp_int * b, mp_int * c);
325MP_API int mp_reduce_is_2k_l(mp_int *a);
326MP_API int mp_reduce_is_2k(mp_int *a);
327MP_API int mp_dr_is_modulus(mp_int *a);
328MP_API int mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y,
329 int);
330MP_API int mp_exptmod_base_2 (mp_int * X, mp_int * P, mp_int * Y);
331#define mp_exptmod_nct(G,X,P,Y) mp_exptmod_fast(G,X,P,Y,0)
332MP_API int mp_montgomery_setup (mp_int * n, mp_digit * rho);
333int fast_mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho);
334MP_API int mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho);
335MP_API void mp_dr_setup(mp_int *a, mp_digit *d);
336MP_API int mp_dr_reduce (mp_int * x, mp_int * n, mp_digit k);
337MP_API int mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d);
338int fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs);
339int s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs);
340MP_API int mp_reduce_2k_setup_l(mp_int *a, mp_int *d);
341MP_API int mp_reduce_2k_l(mp_int *a, mp_int *n, mp_int *d);
342MP_API int mp_reduce (mp_int * x, mp_int * m, mp_int * mu);
343MP_API int mp_reduce_setup (mp_int * a, mp_int * b);
344int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode);
345MP_API int mp_montgomery_calc_normalization (mp_int * a, mp_int * b);
346int s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs);
347int s_mp_sqr (mp_int * a, mp_int * b);
348int fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs);
349int fast_s_mp_sqr (mp_int * a, mp_int * b);
350MP_API int mp_init_size (mp_int * a, int size);
351MP_API int mp_div_3 (mp_int * a, mp_int *c, mp_digit * d);
352MP_API int mp_mul_2(mp_int * a, mp_int * b);
353MP_API int mp_mul (mp_int * a, mp_int * b, mp_int * c);
354MP_API int mp_sqr (mp_int * a, mp_int * b);
355MP_API int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d);
356MP_API int mp_submod (mp_int* a, mp_int* b, mp_int* c, mp_int* d);
357MP_API int mp_addmod (mp_int* a, mp_int* b, mp_int* c, mp_int* d);
358MP_API int mp_mul_d (mp_int * a, mp_digit b, mp_int * c);
359MP_API int mp_2expt (mp_int * a, int b);
360MP_API int mp_set_bit (mp_int * a, int b);
361MP_API int mp_reduce_2k_setup(mp_int *a, mp_digit *d);
362MP_API int mp_add_d (mp_int* a, mp_digit b, mp_int* c);
363MP_API int mp_set_int (mp_int * a, unsigned long b);
364MP_API int mp_sub_d (mp_int * a, mp_digit b, mp_int * c);
365/* end support added functions */
366
367/* added */
368MP_API int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d, mp_int* e,
369 mp_int* f);
370MP_API int mp_toradix (mp_int *a, char *str, int radix);
371MP_API int mp_radix_size (mp_int * a, int radix, int *size);
372
373#ifdef WOLFSSL_DEBUG_MATH
374 MP_API void mp_dump(const char* desc, mp_int* a, byte verbose);
375#else
376 #define mp_dump(desc, a, verbose)
377#endif
378
379#if defined(HAVE_ECC) || defined(WOLFSSL_KEY_GEN) || !defined(NO_RSA) || \
380 !defined(NO_DSA) || !defined(NO_DH)
381 MP_API int mp_sqrmod(mp_int* a, mp_int* b, mp_int* c);
382#endif
383#if !defined(NO_DSA) || defined(HAVE_ECC)
384 MP_API int mp_read_radix(mp_int* a, const char* str, int radix);
385#endif
386
387#if defined(WOLFSSL_KEY_GEN) || !defined(NO_RSA) || !defined(NO_DSA) || !defined(NO_DH)
388 MP_API int mp_prime_is_prime (mp_int * a, int t, int *result);
389 MP_API int mp_prime_is_prime_ex (mp_int * a, int t, int *result, WC_RNG*);
390#endif /* WOLFSSL_KEY_GEN NO_RSA NO_DSA NO_DH */
391#ifdef WOLFSSL_KEY_GEN
392 MP_API int mp_gcd (mp_int * a, mp_int * b, mp_int * c);
393 MP_API int mp_lcm (mp_int * a, mp_int * b, mp_int * c);
394 MP_API int mp_rand_prime(mp_int* N, int len, WC_RNG* rng, void* heap);
395#endif
396
397MP_API int mp_cnt_lsb(mp_int *a);
398MP_API int mp_mod_d(mp_int* a, mp_digit b, mp_digit* c);
399
400
401#ifdef __cplusplus
402 }
403#endif
404
405
406#endif /* USE_FAST_MATH */
407
408#endif /* WOLF_CRYPT_INTEGER_H */
409
WC_BIGINT
Definition integer.h:191
WC_RNG
Definition random.h:153
mp_int
Definition integer.h:200