Mercurial > dropbear
comparison libtommath/tommath_private.h @ 1692:1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
* update C files
* update other files
* update headers
* update makefiles
* remove mp_set/get_double()
* use ltm 1.2.0 API
* update ltm_desc
* use bundled tommath if system-tommath is too old
* XMALLOC etc. were changed to MP_MALLOC etc.
author | Steffen Jaeckel <s@jaeckel.eu> |
---|---|
date | Tue, 26 May 2020 17:36:47 +0200 |
parents | f52919ffd3b1 |
children |
comparison
equal
deleted
inserted
replaced
1691:2d3745d58843 | 1692:1051e4eea25a |
---|---|
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 * SPDX-License-Identifier: Unlicense | |
11 */ | |
12 #ifndef TOMMATH_PRIV_H_ | 4 #ifndef TOMMATH_PRIV_H_ |
13 #define TOMMATH_PRIV_H_ | 5 #define TOMMATH_PRIV_H_ |
14 | 6 |
15 #include "tommath.h" | 7 #include "tommath.h" |
16 #include <ctype.h> | 8 #include "tommath_class.h" |
17 | 9 |
18 #ifndef MIN | 10 /* |
19 #define MIN(x, y) (((x) < (y)) ? (x) : (y)) | 11 * Private symbols |
20 #endif | 12 * --------------- |
21 | 13 * |
22 #ifndef MAX | 14 * On Unix symbols can be marked as hidden if libtommath is compiled |
23 #define MAX(x, y) (((x) > (y)) ? (x) : (y)) | 15 * as a shared object. By default, symbols are visible. |
24 #endif | 16 * As of now, this feature is opt-in via the MP_PRIVATE_SYMBOLS define. |
25 | 17 * |
26 #ifdef __cplusplus | 18 * On Win32 a .def file must be used to specify the exported symbols. |
27 extern "C" { | 19 */ |
28 | 20 #if defined (MP_PRIVATE_SYMBOLS) && defined(__GNUC__) && __GNUC__ >= 4 |
29 /* C++ compilers don't like assigning void * to mp_digit * */ | 21 # define MP_PRIVATE __attribute__ ((visibility ("hidden"))) |
30 #define OPT_CAST(x) (x *) | 22 #else |
31 | 23 # define MP_PRIVATE |
32 #else | 24 #endif |
33 | 25 |
34 /* C on the other hand doesn't care */ | 26 /* Hardening libtommath |
35 #define OPT_CAST(x) | 27 * -------------------- |
36 | 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 | |
37 #endif | 125 #endif |
38 | 126 |
39 /* define heap macros */ | 127 /* define heap macros */ |
40 #ifndef XMALLOC | 128 #ifndef MP_MALLOC |
41 /* default to libc stuff */ | 129 /* default to libc stuff */ |
42 # define XMALLOC malloc | 130 # include <stdlib.h> |
43 # define XFREE free | 131 # define MP_MALLOC(size) malloc(size) |
44 # define XREALLOC realloc | 132 # define MP_REALLOC(mem, oldsize, newsize) realloc((mem), (newsize)) |
45 # define XCALLOC calloc | 133 # define MP_CALLOC(nmemb, size) calloc((nmemb), (size)) |
134 # define MP_FREE(mem, size) free(mem) | |
46 #else | 135 #else |
47 /* prototypes for our heap functions */ | 136 /* prototypes for our heap functions */ |
48 extern void *XMALLOC(size_t n); | 137 extern void *MP_MALLOC(size_t size); |
49 extern void *XREALLOC(void *p, size_t n); | 138 extern void *MP_REALLOC(void *mem, size_t oldsize, size_t newsize); |
50 extern void *XCALLOC(size_t n, size_t s); | 139 extern void *MP_CALLOC(size_t nmemb, size_t size); |
51 extern void XFREE(void *p); | 140 extern void MP_FREE(void *mem, size_t size); |
52 #endif | 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); | |
53 | 187 |
54 /* lowlevel functions, do not call! */ | 188 /* lowlevel functions, do not call! */ |
55 int s_mp_add(const mp_int *a, const mp_int *b, mp_int *c); | 189 MP_PRIVATE mp_bool s_mp_get_bit(const mp_int *a, unsigned int b); |
56 int s_mp_sub(const mp_int *a, const 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; |
57 #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; |
58 int fast_s_mp_mul_digs(const mp_int *a, const 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; |
59 int s_mp_mul_digs(const mp_int *a, const 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; |
60 int fast_s_mp_mul_high_digs(const mp_int *a, const 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; |
61 int s_mp_mul_high_digs(const mp_int *a, const 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; |
62 int fast_s_mp_sqr(const mp_int *a, mp_int *b); | 196 MP_PRIVATE mp_err s_mp_sqr_fast(const mp_int *a, mp_int *b) MP_WUR; |
63 int s_mp_sqr(const mp_int *a, mp_int *b); | 197 MP_PRIVATE mp_err s_mp_sqr(const mp_int *a, mp_int *b) MP_WUR; |
64 int mp_karatsuba_mul(const mp_int *a, const 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; |
65 int mp_toom_mul(const mp_int *a, const 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; |
66 int mp_karatsuba_sqr(const 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; |
67 int mp_toom_sqr(const mp_int *a, mp_int *b); | 201 MP_PRIVATE mp_err s_mp_karatsuba_sqr(const mp_int *a, mp_int *b) MP_WUR; |
68 int fast_mp_invmod(const mp_int *a, const mp_int *b, mp_int *c); | 202 MP_PRIVATE mp_err s_mp_toom_sqr(const mp_int *a, mp_int *b) MP_WUR; |
69 int mp_invmod_slow(const mp_int *a, const 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; |
70 int fast_mp_montgomery_reduce(mp_int *x, const 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; |
71 int mp_exptmod_fast(const mp_int *G, const mp_int *X, const 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; |
72 int s_mp_exptmod(const mp_int *G, const mp_int *X, const 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; |
73 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; |
74 | 208 MP_PRIVATE mp_err s_mp_rand_platform(void *p, size_t n) MP_WUR; |
75 extern const char *const 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); |
76 extern const uint8_t mp_s_rmap_reverse[]; | 210 MP_PRIVATE void s_mp_reverse(unsigned char *s, size_t len); |
77 extern const size_t mp_s_rmap_reverse_sz; | 211 MP_PRIVATE mp_err s_mp_prime_is_divisible(const mp_int *a, mp_bool *result); |
78 | 212 |
79 /* Fancy macro to set an MPI from another type. | 213 /* TODO: jenkins prng is not thread safe as of now */ |
80 * There are several things assumed: | 214 MP_PRIVATE mp_err s_mp_rand_jenkins(void *p, size_t n) MP_WUR; |
81 * x is the counter and unsigned | 215 MP_PRIVATE void s_mp_rand_jenkins_init(uint64_t seed); |
82 * a is the pointer to the MPI | 216 |
83 * b is the original value that should be set in the MPI. | 217 extern MP_PRIVATE const char *const mp_s_rmap; |
84 */ | 218 extern MP_PRIVATE const uint8_t mp_s_rmap_reverse[]; |
85 #define MP_SET_XLONG(func_name, type) \ | 219 extern MP_PRIVATE const size_t mp_s_rmap_reverse_sz; |
86 int func_name (mp_int * a, type b) \ | 220 extern MP_PRIVATE const mp_digit *s_mp_prime_tab; |
87 { \ | 221 |
88 unsigned int x; \ | 222 /* deprecated functions */ |
89 int res; \ | 223 MP_DEPRECATED(s_mp_invmod_fast) mp_err fast_mp_invmod(const mp_int *a, const mp_int *b, mp_int *c); |
90 \ | 224 MP_DEPRECATED(s_mp_montgomery_reduce_fast) mp_err fast_mp_montgomery_reduce(mp_int *x, const mp_int *n, |
91 mp_zero (a); \ | 225 mp_digit rho); |
92 \ | 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, |
93 /* set four bits at a time */ \ | 227 int digs); |
94 for (x = 0; x < (sizeof(type) * 2u); x++) { \ | 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, |
95 /* shift the number up four bits */ \ | 229 mp_int *c, |
96 if ((res = mp_mul_2d (a, 4, a)) != MP_OKAY) { \ | 230 int digs); |
97 return res; \ | 231 MP_DEPRECATED(s_mp_sqr_fast) mp_err fast_s_mp_sqr(const mp_int *a, mp_int *b); |
98 } \ | 232 MP_DEPRECATED(s_mp_balance_mul) mp_err mp_balance_mul(const mp_int *a, const mp_int *b, mp_int *c); |
99 \ | 233 MP_DEPRECATED(s_mp_exptmod_fast) mp_err mp_exptmod_fast(const mp_int *G, const mp_int *X, const mp_int *P, |
100 /* OR in the top four bits of the source */ \ | 234 mp_int *Y, |
101 a->dp[0] |= (mp_digit)(b >> ((sizeof(type) * 8u) - 4u)) & 15uL;\ | 235 int redmode); |
102 \ | 236 MP_DEPRECATED(s_mp_invmod_slow) mp_err mp_invmod_slow(const mp_int *a, const mp_int *b, mp_int *c); |
103 /* shift the source up to the next four bits */ \ | 237 MP_DEPRECATED(s_mp_karatsuba_mul) mp_err mp_karatsuba_mul(const mp_int *a, const mp_int *b, mp_int *c); |
104 b <<= 4; \ | 238 MP_DEPRECATED(s_mp_karatsuba_sqr) mp_err mp_karatsuba_sqr(const mp_int *a, mp_int *b); |
105 \ | 239 MP_DEPRECATED(s_mp_toom_mul) mp_err mp_toom_mul(const mp_int *a, const mp_int *b, mp_int *c); |
106 /* ensure that digits are not clamped off */ \ | 240 MP_DEPRECATED(s_mp_toom_sqr) mp_err mp_toom_sqr(const mp_int *a, mp_int *b); |
107 a->used += 1; \ | 241 MP_DEPRECATED(s_mp_reverse) void bn_reverse(unsigned char *s, int len); |
108 } \ | 242 |
109 mp_clamp (a); \ | 243 #define MP_GET_ENDIANNESS(x) \ |
110 return MP_OKAY; \ | 244 do{\ |
111 } | 245 int16_t n = 0x1; \ |
112 | 246 char *p = (char *)&n; \ |
113 #ifdef __cplusplus | 247 x = (p[0] == '\x01') ? MP_LITTLE_ENDIAN : MP_BIG_ENDIAN; \ |
114 } | 248 } while (0) |
115 #endif | 249 |
116 | 250 /* code-generating macros */ |
117 #endif | 251 #define MP_SET_UNSIGNED(name, type) \ |
118 | 252 void name(mp_int * a, type b) \ |
119 | 253 { \ |
120 /* ref: HEAD -> master, tag: v1.1.0 */ | 254 int i = 0; \ |
121 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ | 255 while (b != 0u) { \ |
122 /* commit time: 2019-01-28 20:32:32 +0100 */ | 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 |