Mercurial > dropbear

comparison libtommath/tommath_private.h @ 1739:13d834efc376 fuzz

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge from main
author Matt Johnston <matt@ucc.asn.au>
date Thu, 15 Oct 2020 19:55:15 +0800
parents 1051e4eea25a
children
comparison
equal deleted inserted replaced
1562:768ebf737aa0 1739:13d834efc376
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
2 * 2 /* SPDX-License-Identifier: Unlicense */
3 * LibTomMath is a library that provides multiple-precision 3
4 * integer arithmetic as well as number theoretic functionality.
5 *
6 * The library was designed directly after the MPI library by
7 * Michael Fromberger but has been written from scratch with
8 * additional optimizations in place.
9 *
10 * The library is free for all purposes without any express
11 * guarantee it works.
12 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.com
14 */
15 #ifndef TOMMATH_PRIV_H_ 4 #ifndef TOMMATH_PRIV_H_
16 #define TOMMATH_PRIV_H_ 5 #define TOMMATH_PRIV_H_
17 6
18 #include <tommath.h> 7 #include "tommath.h"
19 #include <ctype.h> 8 #include "tommath_class.h"
20 9
21 #ifndef MIN 10 /*
22 #define MIN(x,y) (((x) < (y)) ? (x) : (y)) 11 * Private symbols
23 #endif 12 * ---------------
24 13 *
25 #ifndef MAX 14 * On Unix symbols can be marked as hidden if libtommath is compiled
26 #define MAX(x,y) (((x) > (y)) ? (x) : (y)) 15 * as a shared object. By default, symbols are visible.
27 #endif 16 * As of now, this feature is opt-in via the MP_PRIVATE_SYMBOLS define.
28 17 *
29 #ifdef __cplusplus 18 * On Win32 a .def file must be used to specify the exported symbols.
30 extern "C" { 19 */
31 20 #if defined (MP_PRIVATE_SYMBOLS) && defined(__GNUC__) && __GNUC__ >= 4
32 /* C++ compilers don't like assigning void * to mp_digit * */ 21 # define MP_PRIVATE __attribute__ ((visibility ("hidden")))
33 #define OPT_CAST(x) (x *) 22 #else
34 23 # define MP_PRIVATE
35 #else 24 #endif
36 25
37 /* C on the other hand doesn't care */ 26 /* Hardening libtommath
38 #define OPT_CAST(x) 27 * --------------------
39 28 *
29 * By default memory is zeroed before calling
30 * MP_FREE to avoid leaking data. This is good
31 * practice in cryptographical applications.
32 *
33 * Note however that memory allocators used
34 * in cryptographical applications can often
35 * be configured by itself to clear memory,
36 * rendering the clearing in tommath unnecessary.
37 * See for example https://github.com/GrapheneOS/hardened_malloc
38 * and the option CONFIG_ZERO_ON_FREE.
39 *
40 * Furthermore there are applications which
41 * value performance more and want this
42 * feature to be disabled. For such applications
43 * define MP_NO_ZERO_ON_FREE during compilation.
44 */
45 #ifdef MP_NO_ZERO_ON_FREE
46 # define MP_FREE_BUFFER(mem, size) MP_FREE((mem), (size))
47 # define MP_FREE_DIGITS(mem, digits) MP_FREE((mem), sizeof (mp_digit) * (size_t)(digits))
48 #else
49 # define MP_FREE_BUFFER(mem, size) \
50 do { \
51 size_t fs_ = (size); \
52 void* fm_ = (mem); \
53 if (fm_ != NULL) { \
54 MP_ZERO_BUFFER(fm_, fs_); \
55 MP_FREE(fm_, fs_); \
56 } \
57 } while (0)
58 # define MP_FREE_DIGITS(mem, digits) \
59 do { \
60 int fd_ = (digits); \
61 void* fm_ = (mem); \
62 if (fm_ != NULL) { \
63 size_t fs_ = sizeof (mp_digit) * (size_t)fd_; \
64 MP_ZERO_BUFFER(fm_, fs_); \
65 MP_FREE(fm_, fs_); \
66 } \
67 } while (0)
68 #endif
69
70 #ifdef MP_USE_MEMSET
71 # include <string.h>
72 # define MP_ZERO_BUFFER(mem, size) memset((mem), 0, (size))
73 # define MP_ZERO_DIGITS(mem, digits) \
74 do { \
75 int zd_ = (digits); \
76 if (zd_ > 0) { \
77 memset((mem), 0, sizeof(mp_digit) * (size_t)zd_); \
78 } \
79 } while (0)
80 #else
81 # define MP_ZERO_BUFFER(mem, size) \
82 do { \
83 size_t zs_ = (size); \
84 char* zm_ = (char*)(mem); \
85 while (zs_-- > 0u) { \
86 *zm_++ = '\0'; \
87 } \
88 } while (0)
89 # define MP_ZERO_DIGITS(mem, digits) \
90 do { \
91 int zd_ = (digits); \
92 mp_digit* zm_ = (mem); \
93 while (zd_-- > 0) { \
94 *zm_++ = 0; \
95 } \
96 } while (0)
97 #endif
98
99 /* Tunable cutoffs
100 * ---------------
101 *
102 * - In the default settings, a cutoff X can be modified at runtime
103 * by adjusting the corresponding X_CUTOFF variable.
104 *
105 * - Tunability of the library can be disabled at compile time
106 * by defining the MP_FIXED_CUTOFFS macro.
107 *
108 * - There is an additional file tommath_cutoffs.h, which defines
109 * the default cutoffs. These can be adjusted manually or by the
110 * autotuner.
111 *
112 */
113
114 #ifdef MP_FIXED_CUTOFFS
115 # include "tommath_cutoffs.h"
116 # define MP_KARATSUBA_MUL_CUTOFF MP_DEFAULT_KARATSUBA_MUL_CUTOFF
117 # define MP_KARATSUBA_SQR_CUTOFF MP_DEFAULT_KARATSUBA_SQR_CUTOFF
118 # define MP_TOOM_MUL_CUTOFF MP_DEFAULT_TOOM_MUL_CUTOFF
119 # define MP_TOOM_SQR_CUTOFF MP_DEFAULT_TOOM_SQR_CUTOFF
120 #else
121 # define MP_KARATSUBA_MUL_CUTOFF KARATSUBA_MUL_CUTOFF
122 # define MP_KARATSUBA_SQR_CUTOFF KARATSUBA_SQR_CUTOFF
123 # define MP_TOOM_MUL_CUTOFF TOOM_MUL_CUTOFF
124 # define MP_TOOM_SQR_CUTOFF TOOM_SQR_CUTOFF
40 #endif 125 #endif
41 126
42 /* define heap macros */ 127 /* define heap macros */
43 #ifndef XMALLOC 128 #ifndef MP_MALLOC
44 /* default to libc stuff */ 129 /* default to libc stuff */
45 #define XMALLOC malloc 130 # include <stdlib.h>
46 #define XFREE free 131 # define MP_MALLOC(size) malloc(size)
47 #define XREALLOC realloc 132 # define MP_REALLOC(mem, oldsize, newsize) realloc((mem), (newsize))
48 #define XCALLOC calloc 133 # define MP_CALLOC(nmemb, size) calloc((nmemb), (size))
49 #else 134 # define MP_FREE(mem, size) free(mem)
50 /* prototypes for our heap functions */ 135 #else
51 extern void *XMALLOC(size_t n); 136 /* prototypes for our heap functions */
52 extern void *XREALLOC(void *p, size_t n); 137 extern void *MP_MALLOC(size_t size);
53 extern void *XCALLOC(size_t n, size_t s); 138 extern void *MP_REALLOC(void *mem, size_t oldsize, size_t newsize);
54 extern void XFREE(void *p); 139 extern void *MP_CALLOC(size_t nmemb, size_t size);
55 #endif 140 extern void MP_FREE(void *mem, size_t size);
141 #endif
142
143 /* feature detection macro */
144 #ifdef _MSC_VER
145 /* Prevent false positive: not enough arguments for function-like macro invocation */
146 #pragma warning(disable: 4003)
147 #endif
148 #define MP_STRINGIZE(x) MP__STRINGIZE(x)
149 #define MP__STRINGIZE(x) ""#x""
150 #define MP_HAS(x) (sizeof(MP_STRINGIZE(BN_##x##_C)) == 1u)
151
152 /* TODO: Remove private_mp_word as soon as deprecated mp_word is removed from tommath. */
153 #undef mp_word
154 typedef private_mp_word mp_word;
155
156 #define MP_MIN(x, y) (((x) < (y)) ? (x) : (y))
157 #define MP_MAX(x, y) (((x) > (y)) ? (x) : (y))
158
159 /* Static assertion */
160 #define MP_STATIC_ASSERT(msg, cond) typedef char mp_static_assert_##msg[(cond) ? 1 : -1];
161
162 /* ---> Basic Manipulations <--- */
163 #define MP_IS_ZERO(a) ((a)->used == 0)
164 #define MP_IS_EVEN(a) (((a)->used == 0) || (((a)->dp[0] & 1u) == 0u))
165 #define MP_IS_ODD(a) (((a)->used > 0) && (((a)->dp[0] & 1u) == 1u))
166
167 #define MP_SIZEOF_BITS(type) ((size_t)CHAR_BIT * sizeof(type))
168 #define MP_MAXFAST (int)(1uL << (MP_SIZEOF_BITS(mp_word) - (2u * (size_t)MP_DIGIT_BIT)))
169
170 /* TODO: Remove PRIVATE_MP_WARRAY as soon as deprecated MP_WARRAY is removed from tommath.h */
171 #undef MP_WARRAY
172 #define MP_WARRAY PRIVATE_MP_WARRAY
173
174 /* TODO: Remove PRIVATE_MP_PREC as soon as deprecated MP_PREC is removed from tommath.h */
175 #ifdef PRIVATE_MP_PREC
176 # undef MP_PREC
177 # define MP_PREC PRIVATE_MP_PREC
178 #endif
179
180 /* Minimum number of available digits in mp_int, MP_PREC >= MP_MIN_PREC */
181 #define MP_MIN_PREC ((((int)MP_SIZEOF_BITS(long long) + MP_DIGIT_BIT) - 1) / MP_DIGIT_BIT)
182
183 MP_STATIC_ASSERT(prec_geq_min_prec, MP_PREC >= MP_MIN_PREC)
184
185 /* random number source */
186 extern MP_PRIVATE mp_err(*s_mp_rand_source)(void *out, size_t size);
56 187
57 /* lowlevel functions, do not call! */ 188 /* lowlevel functions, do not call! */
58 int s_mp_add(mp_int *a, mp_int *b, mp_int *c); 189 MP_PRIVATE mp_bool s_mp_get_bit(const mp_int *a, unsigned int b);
59 int s_mp_sub(mp_int *a, mp_int *b, mp_int *c); 190 MP_PRIVATE mp_err s_mp_add(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
60 #define s_mp_mul(a, b, c) s_mp_mul_digs(a, b, c, (a)->used + (b)->used + 1) 191 MP_PRIVATE mp_err s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
61 int fast_s_mp_mul_digs(mp_int *a, mp_int *b, mp_int *c, int digs); 192 MP_PRIVATE mp_err s_mp_mul_digs_fast(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
62 int s_mp_mul_digs(mp_int *a, mp_int *b, mp_int *c, int digs); 193 MP_PRIVATE mp_err s_mp_mul_digs(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
63 int fast_s_mp_mul_high_digs(mp_int *a, mp_int *b, mp_int *c, int digs); 194 MP_PRIVATE mp_err s_mp_mul_high_digs_fast(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
64 int s_mp_mul_high_digs(mp_int *a, mp_int *b, mp_int *c, int digs); 195 MP_PRIVATE mp_err s_mp_mul_high_digs(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
65 int fast_s_mp_sqr(mp_int *a, mp_int *b); 196 MP_PRIVATE mp_err s_mp_sqr_fast(const mp_int *a, mp_int *b) MP_WUR;
66 int s_mp_sqr(mp_int *a, mp_int *b); 197 MP_PRIVATE mp_err s_mp_sqr(const mp_int *a, mp_int *b) MP_WUR;
67 int mp_karatsuba_mul(mp_int *a, mp_int *b, mp_int *c); 198 MP_PRIVATE mp_err s_mp_balance_mul(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
68 int mp_toom_mul(mp_int *a, mp_int *b, mp_int *c); 199 MP_PRIVATE mp_err s_mp_karatsuba_mul(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
69 int mp_karatsuba_sqr(mp_int *a, mp_int *b); 200 MP_PRIVATE mp_err s_mp_toom_mul(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
70 int mp_toom_sqr(mp_int *a, mp_int *b); 201 MP_PRIVATE mp_err s_mp_karatsuba_sqr(const mp_int *a, mp_int *b) MP_WUR;
71 int fast_mp_invmod(mp_int *a, mp_int *b, mp_int *c); 202 MP_PRIVATE mp_err s_mp_toom_sqr(const mp_int *a, mp_int *b) MP_WUR;
72 int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c); 203 MP_PRIVATE mp_err s_mp_invmod_fast(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
73 int fast_mp_montgomery_reduce(mp_int *x, mp_int *n, mp_digit rho); 204 MP_PRIVATE mp_err s_mp_invmod_slow(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
74 int mp_exptmod_fast(mp_int *G, mp_int *X, mp_int *P, mp_int *Y, int redmode); 205 MP_PRIVATE mp_err s_mp_montgomery_reduce_fast(mp_int *x, const mp_int *n, mp_digit rho) MP_WUR;
75 int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode); 206 MP_PRIVATE mp_err s_mp_exptmod_fast(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y, int redmode) MP_WUR;
76 void bn_reverse(unsigned char *s, int len); 207 MP_PRIVATE mp_err s_mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y, int redmode) MP_WUR;
77 208 MP_PRIVATE mp_err s_mp_rand_platform(void *p, size_t n) MP_WUR;
78 extern const char *mp_s_rmap; 209 MP_PRIVATE mp_err s_mp_prime_random_ex(mp_int *a, int t, int size, int flags, private_mp_prime_callback cb, void *dat);
79 210 MP_PRIVATE void s_mp_reverse(unsigned char *s, size_t len);
80 /* Fancy macro to set an MPI from another type. 211 MP_PRIVATE mp_err s_mp_prime_is_divisible(const mp_int *a, mp_bool *result);
81 * There are several things assumed: 212
82 * x is the counter and unsigned 213 /* TODO: jenkins prng is not thread safe as of now */
83 * a is the pointer to the MPI 214 MP_PRIVATE mp_err s_mp_rand_jenkins(void *p, size_t n) MP_WUR;
84 * b is the original value that should be set in the MPI. 215 MP_PRIVATE void s_mp_rand_jenkins_init(uint64_t seed);
85 */ 216
86 #define MP_SET_XLONG(func_name, type) \ 217 extern MP_PRIVATE const char *const mp_s_rmap;
87 int func_name (mp_int * a, type b) \ 218 extern MP_PRIVATE const uint8_t mp_s_rmap_reverse[];
88 { \ 219 extern MP_PRIVATE const size_t mp_s_rmap_reverse_sz;
89 unsigned int x; \ 220 extern MP_PRIVATE const mp_digit *s_mp_prime_tab;
90 int res; \ 221
91 \ 222 /* deprecated functions */
92 mp_zero (a); \ 223 MP_DEPRECATED(s_mp_invmod_fast) mp_err fast_mp_invmod(const mp_int *a, const mp_int *b, mp_int *c);
93 \ 224 MP_DEPRECATED(s_mp_montgomery_reduce_fast) mp_err fast_mp_montgomery_reduce(mp_int *x, const mp_int *n,
94 /* set four bits at a time */ \ 225 mp_digit rho);
95 for (x = 0; x < (sizeof(type) * 2u); x++) { \ 226 MP_DEPRECATED(s_mp_mul_digs_fast) mp_err fast_s_mp_mul_digs(const mp_int *a, const mp_int *b, mp_int *c,
96 /* shift the number up four bits */ \ 227 int digs);
97 if ((res = mp_mul_2d (a, 4, a)) != MP_OKAY) { \ 228 MP_DEPRECATED(s_mp_mul_high_digs_fast) mp_err fast_s_mp_mul_high_digs(const mp_int *a, const mp_int *b,
98 return res; \ 229 mp_int *c,
99 } \ 230 int digs);
100 \ 231 MP_DEPRECATED(s_mp_sqr_fast) mp_err fast_s_mp_sqr(const mp_int *a, mp_int *b);
101 /* OR in the top four bits of the source */ \ 232 MP_DEPRECATED(s_mp_balance_mul) mp_err mp_balance_mul(const mp_int *a, const mp_int *b, mp_int *c);
102 a->dp[0] |= (b >> ((sizeof(type) * 8u) - 4u)) & 15u; \ 233 MP_DEPRECATED(s_mp_exptmod_fast) mp_err mp_exptmod_fast(const mp_int *G, const mp_int *X, const mp_int *P,
103 \ 234 mp_int *Y,
104 /* shift the source up to the next four bits */ \ 235 int redmode);
105 b <<= 4; \ 236 MP_DEPRECATED(s_mp_invmod_slow) mp_err mp_invmod_slow(const mp_int *a, const mp_int *b, mp_int *c);
106 \ 237 MP_DEPRECATED(s_mp_karatsuba_mul) mp_err mp_karatsuba_mul(const mp_int *a, const mp_int *b, mp_int *c);
107 /* ensure that digits are not clamped off */ \ 238 MP_DEPRECATED(s_mp_karatsuba_sqr) mp_err mp_karatsuba_sqr(const mp_int *a, mp_int *b);
108 a->used += 1; \ 239 MP_DEPRECATED(s_mp_toom_mul) mp_err mp_toom_mul(const mp_int *a, const mp_int *b, mp_int *c);
109 } \ 240 MP_DEPRECATED(s_mp_toom_sqr) mp_err mp_toom_sqr(const mp_int *a, mp_int *b);
110 mp_clamp (a); \ 241 MP_DEPRECATED(s_mp_reverse) void bn_reverse(unsigned char *s, int len);
111 return MP_OKAY; \ 242
112 } 243 #define MP_GET_ENDIANNESS(x) \
113 244 do{\
114 #ifdef __cplusplus 245 int16_t n = 0x1; \
115 } 246 char *p = (char *)&n; \
116 #endif 247 x = (p[0] == '\x01') ? MP_LITTLE_ENDIAN : MP_BIG_ENDIAN; \
117 248 } while (0)
118 #endif 249
119 250 /* code-generating macros */
120 251 #define MP_SET_UNSIGNED(name, type) \
121 /* ref: $Format:%D$ */ 252 void name(mp_int * a, type b) \
122 /* git commit: $Format:%H$ */ 253 { \
123 /* commit time: $Format:%ai$ */ 254 int i = 0; \
255 while (b != 0u) { \
256 a->dp[i++] = ((mp_digit)b & MP_MASK); \
257 if (MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) { break; } \
258 b >>= ((MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) ? 0 : MP_DIGIT_BIT); \
259 } \
260 a->used = i; \
261 a->sign = MP_ZPOS; \
262 MP_ZERO_DIGITS(a->dp + a->used, a->alloc - a->used); \
263 }
264
265 #define MP_SET_SIGNED(name, uname, type, utype) \
266 void name(mp_int * a, type b) \
267 { \
268 uname(a, (b < 0) ? -(utype)b : (utype)b); \
269 if (b < 0) { a->sign = MP_NEG; } \
270 }
271
272 #define MP_INIT_INT(name , set, type) \
273 mp_err name(mp_int * a, type b) \
274 { \
275 mp_err err; \
276 if ((err = mp_init(a)) != MP_OKAY) { \
277 return err; \
278 } \
279 set(a, b); \
280 return MP_OKAY; \
281 }
282
283 #define MP_GET_MAG(name, type) \
284 type name(const mp_int* a) \
285 { \
286 unsigned i = MP_MIN((unsigned)a->used, (unsigned)((MP_SIZEOF_BITS(type) + MP_DIGIT_BIT - 1) / MP_DIGIT_BIT)); \
287 type res = 0u; \
288 while (i --> 0u) { \
289 res <<= ((MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) ? 0 : MP_DIGIT_BIT); \
290 res |= (type)a->dp[i]; \
291 if (MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) { break; } \
292 } \
293 return res; \
294 }
295
296 #define MP_GET_SIGNED(name, mag, type, utype) \
297 type name(const mp_int* a) \
298 { \
299 utype res = mag(a); \
300 return (a->sign == MP_NEG) ? (type)-res : (type)res; \
301 }
302
303 #endif