tommath_private.h

   1 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
   2 /* SPDX-License-Identifier: Unlicense */
   3
   4 #ifndef TOMMATH_PRIVATE_H_
   5 #define TOMMATH_PRIVATE_H_
   6
   7 #include "tommath.h"
   8 #include "tommath_class.h"
   9 #include <limits.h>
  10
  11 /*
  12  * Private symbols
  13  * ---------------
  14  *
  15  * On Unix symbols can be marked as hidden if libtommath is compiled
  16  * as a shared object. By default, symbols are visible.
  17  * On Win32 a .def file must be used to specify the exported symbols.
  18  */
  19 #if defined(__GNUC__) && __GNUC__ >= 4 && !defined(_WIN32) && !defined(__CYGWIN__)
  20 #   define MP_PRIVATE __attribute__ ((visibility ("hidden")))
  21 #else
  22 #   define MP_PRIVATE
  23 #endif
  24
  25 /* Hardening libtommath
  26  * --------------------
  27  *
  28  * By default memory is zeroed before calling
  29  * MP_FREE to avoid leaking data. This is good
  30  * practice in cryptographical applications.
  31  *
  32  * Note however that memory allocators used
  33  * in cryptographical applications can often
  34  * be configured by itself to clear memory,
  35  * rendering the clearing in tommath unnecessary.
  36  * See for example https://github.com/GrapheneOS/hardened_malloc
  37  * and the option CONFIG_ZERO_ON_FREE.
  38  *
  39  * Furthermore there are applications which
  40  * value performance more and want this
  41  * feature to be disabled. For such applications
  42  * define MP_NO_ZERO_ON_FREE during compilation.
  43  */
  44 #ifdef MP_NO_ZERO_ON_FREE
  45 #  define MP_FREE_BUF(mem, size)   MP_FREE((mem), (size))
  46 #  define MP_FREE_DIGS(mem, digits) MP_FREE((mem), sizeof (mp_digit) * (size_t)(digits))
  47 #else
  48 #  define MP_FREE_BUF(mem, size)                        \
  49 do {                                                    \
  50    size_t fs_ = (size);                                 \
  51    void* fm_ = (mem);                                   \
  52    if (fm_ != NULL) {                                   \
  53       s_mp_zero_buf(fm_, fs_);                          \
  54       MP_FREE(fm_, fs_);                                \
  55    }                                                    \
  56 } while (0)
  57 #  define MP_FREE_DIGS(mem, digits)                     \
  58 do {                                                    \
  59    int fd_ = (digits);                                  \
  60    mp_digit* fm_ = (mem);                               \
  61    if (fm_ != NULL) {                                   \
  62       s_mp_zero_digs(fm_, fd_);                         \
  63       MP_FREE(fm_, sizeof (mp_digit) * (size_t)fd_);    \
  64    }                                                    \
  65 } while (0)
  66 #endif
  67
  68 /* Tunable cutoffs
  69  * ---------------
  70  *
  71  *  - In the default settings, a cutoff X can be modified at runtime
  72  *    by adjusting the corresponding X_CUTOFF variable.
  73  *
  74  *  - Tunability of the library can be disabled at compile time
  75  *    by defining the MP_FIXED_CUTOFFS macro.
  76  *
  77  *  - There is an additional file tommath_cutoffs.h, which defines
  78  *    the default cutoffs. These can be adjusted manually or by the
  79  *    autotuner.
  80  *
  81  */
  82
  83 #ifdef MP_FIXED_CUTOFFS
  84 #  include "tommath_cutoffs.h"
  85 #  define MP_MUL_KARATSUBA_CUTOFF MP_DEFAULT_MUL_KARATSUBA_CUTOFF
  86 #  define MP_SQR_KARATSUBA_CUTOFF MP_DEFAULT_SQR_KARATSUBA_CUTOFF
  87 #  define MP_MUL_TOOM_CUTOFF      MP_DEFAULT_MUL_TOOM_CUTOFF
  88 #  define MP_SQR_TOOM_CUTOFF      MP_DEFAULT_SQR_TOOM_CUTOFF
  89 #endif
  90
  91 /* define heap macros */
  92 #ifndef MP_MALLOC
  93 /* default to libc stuff */
  94 #   include <stdlib.h>
  95 #   define MP_MALLOC(size)                   malloc(size)
  96 #   define MP_REALLOC(mem, oldsize, newsize) realloc((mem), (newsize))
  97 #   define MP_CALLOC(nmemb, size)            calloc((nmemb), (size))
  98 #   define MP_FREE(mem, size)                free(mem)
  99 #else
 100 /* prototypes for our heap functions */
 101 extern void *MP_MALLOC(size_t size);
 102 extern void *MP_REALLOC(void *mem, size_t oldsize, size_t newsize);
 103 extern void *MP_CALLOC(size_t nmemb, size_t size);
 104 extern void MP_FREE(void *mem, size_t size);
 105 #endif
 106
 107 /* feature detection macro */
 108 #ifdef _MSC_VER
 109 /* Prevent false positive: not enough arguments for function-like macro invocation */
 110 #pragma warning(disable: 4003)
 111 #endif
 112 #define MP_STRINGIZE(x)  MP__STRINGIZE(x)
 113 #define MP__STRINGIZE(x) ""#x""
 114 #define MP_HAS(x)        (sizeof(MP_STRINGIZE(x##_C)) == 1u)
 115
 116 #define MP_MIN(x, y) (((x) < (y)) ? (x) : (y))
 117 #define MP_MAX(x, y) (((x) > (y)) ? (x) : (y))
 118
 119 #define MP_TOUPPER(c) ((((c) >= 'a') && ((c) <= 'z')) ? (((c) + 'A') - 'a') : (c))
 120
 121 #define MP_EXCH(t, a, b) do { t _c = a; a = b; b = _c; } while (0)
 122
 123 #define MP_IS_2EXPT(x) (((x) != 0u) && (((x) & ((x) - 1u)) == 0u))
 124
 125 /* TODO: same as above for bigint, merge (is it used elsewhere?) or change name */
 126 #define MP_IS_POWER_OF_TWO(a)    (((mp_count_bits((a)) - 1) ==  mp_cnt_lsb((a))) )
 127
 128 /* Static assertion */
 129 #define MP_STATIC_ASSERT(msg, cond) typedef char mp_static_assert_##msg[(cond) ? 1 : -1];
 130
 131 #define MP_SIZEOF_BITS(type)    ((size_t)CHAR_BIT * sizeof(type))
 132
 133 #define MP_MAX_COMBA            (int)(1uL << (MP_SIZEOF_BITS(mp_word) - (2u * (size_t)MP_DIGIT_BIT)))
 134 #define MP_WARRAY               (int)(1uL << ((MP_SIZEOF_BITS(mp_word) - (2u * (size_t)MP_DIGIT_BIT)) + 1u))
 135
 136 #if defined(MP_16BIT)
 137 typedef uint32_t mp_word;
 138 #define MP_WORD_SIZE  4
 139 #elif ((defined (MP_64BIT)) && !(defined(MP_31BIT)) )
 140 typedef unsigned long mp_word __attribute__((mode(TI)));
 141 #define MP_WORD_SIZE  16
 142 #else
 143 typedef uint64_t mp_word;
 144 #define MP_WORD_SIZE  8
 145 #endif
 146
 147 MP_STATIC_ASSERT(correct_word_size, sizeof(mp_word) == (2u * sizeof(mp_digit)))
 148
 149 /* default number of digits */
 150 #ifndef MP_DEFAULT_DIGIT_COUNT
 151 #   ifndef MP_LOW_MEM
 152 #      define MP_DEFAULT_DIGIT_COUNT 32
 153 #   else
 154 #      define MP_DEFAULT_DIGIT_COUNT 8
 155 #   endif
 156 #endif
 157
 158 /* Minimum number of available digits in mp_int, MP_DEFAULT_DIGIT_COUNT >= MP_MIN_DIGIT_COUNT
 159  * - Must be at least 3 for s_mp_div_school.
 160  * - Must be large enough such that the mp_set_u64 setter can
 161  *   store uint64_t in the mp_int without growing
 162  */
 163 #ifndef MP_MIN_DIGIT_COUNT
 164 #    define MP_MIN_DIGIT_COUNT MP_MAX(3, (((int)MP_SIZEOF_BITS(uint64_t) + MP_DIGIT_BIT) - 1) / MP_DIGIT_BIT)
 165 #endif
 166 MP_STATIC_ASSERT(prec_geq_min_prec, MP_DEFAULT_DIGIT_COUNT >= MP_MIN_DIGIT_COUNT)
 167 MP_STATIC_ASSERT(min_prec_geq_3, MP_MIN_DIGIT_COUNT >= 3)
 168 MP_STATIC_ASSERT(min_prec_geq_uint64size,
 169                  MP_MIN_DIGIT_COUNT >= ((((int)MP_SIZEOF_BITS(uint64_t) + MP_DIGIT_BIT) - 1) / MP_DIGIT_BIT))
 170
 171 /* Maximum number of digits.
 172  * - Must be small enough such that mp_bit_count does not overflow.
 173  * - Must be small enough such that mp_radix_size for base 2 does not overflow.
 174  *   mp_radix_size needs two additional bytes for zero termination and sign.
 175  */
 176 #define MP_MAX_DIGIT_COUNT ((INT_MAX - 2) / MP_DIGIT_BIT)
 177
 178 #if defined(__STDC_IEC_559__) || defined(__GCC_IEC_559) \
 179    || defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) \
 180    || defined(__i386__) || defined(_M_X86) || defined(_M_IX86) \
 181    || defined(__aarch64__) || defined(__arm__)
 182 #define MP_HAS_SET_DOUBLE
 183 #endif
 184
 185 /*
 186   The mp_log functions rely on the size of mp_word being larger than INT_MAX and in case
 187   there is a really weird architecture we try to check for it. Not a 100% reliable
 188   test but it has a safe fallback.
 189  */
 190 #if !(((UINT_MAX == UINT32_MAX) && (MP_WORD_SIZE > 4)) \
 191       || ((UINT_MAX == UINT16_MAX) && (MP_WORD_SIZE > 2)))
 192 #define S_MP_WORD_TOO_SMALL_C
 193 #endif
 194
 195 /* random number source */
 196 extern MP_PRIVATE mp_err(*s_mp_rand_source)(void *out, size_t size);
 197
 198 /* lowlevel functions, do not call! */
 199 MP_PRIVATE bool s_mp_get_bit(const mp_int *a, int b) MP_WUR;
 200 MP_PRIVATE int s_mp_log_2expt(const mp_int *a, mp_digit base) MP_WUR;
 201
 202 MP_PRIVATE mp_err s_mp_add(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
 203 MP_PRIVATE mp_err s_mp_div_3(const mp_int *a, mp_int *c, mp_digit *d) MP_WUR;
 204 MP_PRIVATE mp_err s_mp_div_recursive(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r) MP_WUR;
 205 MP_PRIVATE mp_err s_mp_div_school(const mp_int *a, const mp_int *b, mp_int *c, mp_int *d) MP_WUR;
 206 MP_PRIVATE mp_err s_mp_div_small(const mp_int *a, const mp_int *b, mp_int *c, mp_int *d) MP_WUR;
 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;
 208 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;
 209 MP_PRIVATE mp_err s_mp_invmod(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
 210 MP_PRIVATE mp_err s_mp_invmod_odd(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
 211
 212 MP_PRIVATE mp_err s_mp_montgomery_reduce_comba(mp_int *x, const mp_int *n, mp_digit rho) MP_WUR;
 213 MP_PRIVATE mp_err s_mp_mul(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
 214 MP_PRIVATE mp_err s_mp_mul_balance(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
 215 MP_PRIVATE mp_err s_mp_mul_comba(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
 216 MP_PRIVATE mp_err s_mp_mul_high(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
 217 MP_PRIVATE mp_err s_mp_mul_high_comba(const mp_int *a, const mp_int *b, mp_int *c, int digs) MP_WUR;
 218 MP_PRIVATE mp_err s_mp_mul_karatsuba(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
 219 MP_PRIVATE mp_err s_mp_mul_toom(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
 220 MP_PRIVATE mp_err s_mp_prime_is_divisible(const mp_int *a, bool *result) MP_WUR;
 221 MP_PRIVATE mp_err s_mp_rand_platform(void *p, size_t n) MP_WUR;
 222 MP_PRIVATE mp_err s_mp_sqr(const mp_int *a, mp_int *b) MP_WUR;
 223 MP_PRIVATE mp_err s_mp_sqr_comba(const mp_int *a, mp_int *b) MP_WUR;
 224 MP_PRIVATE mp_err s_mp_sqr_karatsuba(const mp_int *a, mp_int *b) MP_WUR;
 225 MP_PRIVATE mp_err s_mp_sqr_toom(const mp_int *a, mp_int *b) MP_WUR;
 226 MP_PRIVATE mp_err s_mp_sub(const mp_int *a, const mp_int *b, mp_int *c) MP_WUR;
 227 MP_PRIVATE void s_mp_copy_digs(mp_digit *d, const mp_digit *s, int digits);
 228 MP_PRIVATE void s_mp_zero_buf(void *mem, size_t size);
 229 MP_PRIVATE void s_mp_zero_digs(mp_digit *d, int digits);
 230 MP_PRIVATE mp_err s_mp_radix_size_overestimate(const mp_int *a, const int radix, size_t *size);
 231
 232 #define MP_PRECISION_FIXED_LOG   ( (int) (((sizeof(mp_word) * CHAR_BIT) / 2) - 1))
 233 #define MP_UPPER_LIMIT_FIXED_LOG ( (int) ( (sizeof(mp_word) * CHAR_BIT) - 1))
 234 MP_PRIVATE mp_err s_mp_fp_log(const mp_int *a, mp_int *c) MP_WUR;
 235 MP_PRIVATE mp_err s_mp_fp_log_d(const mp_int *a, mp_word *c) MP_WUR;
 236
 237 #ifdef MP_SMALL_STACK_SIZE
 238
 239 #if defined(__GNUC__)
 240 /* We use TLS (Thread Local Storage) to manage the instance of the WARRAY
 241  * per thread.
 242  * The compilers we're usually looking at are GCC, Clang and MSVC.
 243  * Both GCC and Clang are straight-forward with TLS, so it's enabled there.
 244  * Using MSVC the tests were OK with the static library, but failed when
 245  * the library was built as a DLL. As a result we completely disable
 246  * support for MSVC.
 247  * If your compiler can handle TLS properly without too much hocus pocus,
 248  * feel free to open a PR to add support for it.
 249  */
 250 #define mp_thread __thread
 251 #else
 252 #error "MP_SMALL_STACK_SIZE not supported with your compiler"
 253 #endif
 254
 255 #define MP_SMALL_STACK_SIZE_C
 256 #define MP_ALLOC_WARRAY(name) *name = s_mp_warray_get()
 257 #define MP_FREE_WARRAY(name) s_mp_warray_put(name)
 258 #define MP_CHECK_WARRAY(name) do { if ((name) == NULL) { return MP_MEM; } } while(0)
 259 #else
 260 #define MP_ALLOC_WARRAY(name) name[MP_WARRAY]
 261 #define MP_FREE_WARRAY(name)
 262 #define MP_CHECK_WARRAY(name)
 263 #endif
 264
 265 #ifndef mp_thread
 266 #define mp_thread
 267 #endif
 268
 269 typedef struct {
 270    void *w_free, *w_used;
 271 } st_warray;
 272
 273 extern MP_PRIVATE mp_thread st_warray s_mp_warray;
 274
 275 MP_PRIVATE void *s_mp_warray_get(void);
 276 MP_PRIVATE void s_mp_warray_put(void *w);
 277
 278 #define MP_RADIX_MAP_REVERSE_SIZE 80u
 279 extern MP_PRIVATE const char s_mp_radix_map[];
 280 extern MP_PRIVATE const uint8_t s_mp_radix_map_reverse[];
 281 extern MP_PRIVATE const mp_digit s_mp_prime_tab[];
 282
 283 /* number of primes */
 284 #define MP_PRIME_TAB_SIZE 256
 285
 286 #define MP_GET_ENDIANNESS(x) \
 287    do{\
 288       int16_t n = 0x1;                                          \
 289       char *p = (char *)&n;                                     \
 290       x = (p[0] == '\x01') ? MP_LITTLE_ENDIAN : MP_BIG_ENDIAN;  \
 291    } while (0)
 292
 293 /* code-generating macros */
 294 #define MP_SET_UNSIGNED(name, type)                                                    \
 295     void name(mp_int * a, type b)                                                      \
 296     {                                                                                  \
 297         int i = 0;                                                                     \
 298         while (b != 0u) {                                                              \
 299             a->dp[i++] = ((mp_digit)b & MP_MASK);                                      \
 300             if (MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) { break; }                       \
 301             b >>= ((MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) ? 0 : MP_DIGIT_BIT);         \
 302         }                                                                              \
 303         a->used = i;                                                                   \
 304         a->sign = MP_ZPOS;                                                             \
 305         s_mp_zero_digs(a->dp + a->used, a->alloc - a->used);                         \
 306     }
 307
 308 #define MP_SET_SIGNED(name, uname, type, utype)          \
 309     void name(mp_int * a, type b)                        \
 310     {                                                    \
 311         uname(a, (b < 0) ? -(utype)b : (utype)b);        \
 312         if (b < 0) { a->sign = MP_NEG; }                 \
 313     }
 314
 315 #define MP_INIT_INT(name , set, type)                    \
 316     mp_err name(mp_int * a, type b)                      \
 317     {                                                    \
 318         mp_err err;                                      \
 319         if ((err = mp_init(a)) != MP_OKAY) {             \
 320             return err;                                  \
 321         }                                                \
 322         set(a, b);                                       \
 323         return MP_OKAY;                                  \
 324     }
 325
 326 #define MP_GET_MAG(name, type)                                                         \
 327     type name(const mp_int* a)                                                         \
 328     {                                                                                  \
 329         int i = MP_MIN(a->used, (int)((MP_SIZEOF_BITS(type) + MP_DIGIT_BIT - 1) / MP_DIGIT_BIT)); \
 330         type res = 0u;                                                                 \
 331         while (i --> 0) {                                                              \
 332             res <<= ((MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) ? 0 : MP_DIGIT_BIT);       \
 333             res |= (type)a->dp[i];                                                     \
 334             if (MP_SIZEOF_BITS(type) <= MP_DIGIT_BIT) { break; }                       \
 335         }                                                                              \
 336         return res;                                                                    \
 337     }
 338
 339 #define MP_GET_SIGNED(name, mag, type, utype)                 \
 340     type name(const mp_int* a)                                \
 341     {                                                         \
 342         utype res = mag(a);                                   \
 343         return mp_isneg(a) ? (type)-res : (type)res;          \
 344     }
 345
 346 #endif