123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524 |
- /* wolfmath.c
- *
- * Copyright (C) 2006-2023 wolfSSL Inc.
- *
- * This file is part of wolfSSL.
- *
- * wolfSSL is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * wolfSSL is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
- */
- /* common functions between all math libraries */
- /* HAVE_WOLF_BIGINT: Used with asynchronous crypto hardware where "raw" math
- * buffers are required.
- * NO_BIG_INT: Disable support for all multi-precision math libraries
- */
- #ifdef HAVE_CONFIG_H
- #include <config.h>
- #endif
- /* in case user set USE_FAST_MATH there */
- #include <wolfssl/wolfcrypt/settings.h>
- #include <wolfssl/wolfcrypt/wolfmath.h>
- #include <wolfssl/wolfcrypt/error-crypt.h>
- #include <wolfssl/wolfcrypt/logging.h>
- #ifdef WOLFSSL_ASYNC_CRYPT
- #include <wolfssl/wolfcrypt/async.h>
- #endif
- #ifdef NO_INLINE
- #include <wolfssl/wolfcrypt/misc.h>
- #else
- #define WOLFSSL_MISC_INCLUDED
- #include <wolfcrypt/src/misc.c>
- #endif
- #if !defined(NO_BIG_INT) || defined(WOLFSSL_SP_MATH)
- #if !defined(WC_NO_CACHE_RESISTANT) && \
- ((defined(HAVE_ECC) && defined(ECC_TIMING_RESISTANT)) || \
- (defined(USE_FAST_MATH) && defined(TFM_TIMING_RESISTANT)))
- /* all off / all on pointer addresses for constant calculations */
- /* ecc.c uses same table */
- const wc_ptr_t wc_off_on_addr[2] =
- {
- #if defined(WC_64BIT_CPU)
- W64LIT(0x0000000000000000),
- W64LIT(0xffffffffffffffff)
- #elif defined(WC_16BIT_CPU)
- 0x0000U,
- 0xffffU
- #else
- /* 32 bit */
- 0x00000000U,
- 0xffffffffU
- #endif
- };
- #endif
- /* reverse an array, used for radix code */
- void mp_reverse(unsigned char *s, int len)
- {
- int ix, iy;
- if (s == NULL)
- return;
- ix = 0;
- iy = len - 1;
- while (ix < iy) {
- unsigned char t = s[ix];
- s[ix] = s[iy];
- s[iy] = t;
- ++ix;
- --iy;
- }
- }
- int get_digit_count(const mp_int* a)
- {
- if (a == NULL)
- return 0;
- return (int)a->used;
- }
- mp_digit get_digit(const mp_int* a, int n)
- {
- if (a == NULL)
- return 0;
- return (n < 0 || (unsigned int)n >= (unsigned int)a->used) ? 0 : a->dp[n];
- }
- #if defined(HAVE_ECC) || defined(WOLFSSL_MP_COND_COPY)
- /* Conditionally copy a into b. Performed in constant time.
- *
- * a MP integer to copy.
- * copy On 1, copy a into b. on 0 leave b unchanged.
- * b MP integer to copy into.
- * returns BAD_FUNC_ARG when a or b is NULL, MEMORY_E when growing b fails and
- * MP_OKAY otherwise.
- */
- int mp_cond_copy(mp_int* a, int copy, mp_int* b)
- {
- int err = MP_OKAY;
- #if defined(SP_WORD_SIZE) && SP_WORD_SIZE == 8
- unsigned int mask = (unsigned int)0 - copy;
- #else
- mp_digit mask = (mp_digit)0 - (mp_digit)copy;
- #endif
- if (a == NULL || b == NULL)
- err = BAD_FUNC_ARG;
- /* Ensure b has enough space to copy a into */
- if (err == MP_OKAY)
- err = mp_grow(b, (int)a->used + 1);
- if (err == MP_OKAY) {
- #if defined(WOLFSSL_SP_MATH) || defined(WOLFSSL_SP_MATH_ALL)
- unsigned int i;
- #else
- int i;
- #endif
- /* When mask 0, b is unchanged2
- * When mask all set, b ^ b ^ a = a
- */
- /* Conditionally copy all digits and then number of used digits.
- * get_digit() returns 0 when index greater than available digit.
- */
- for (i = 0; i < a->used; i++) {
- b->dp[i] ^= (get_digit(a, (int)i) ^ get_digit(b, (int)i)) & mask;
- }
- for (; i < b->used; i++) {
- b->dp[i] ^= (get_digit(a, (int)i) ^ get_digit(b, (int)i)) & mask;
- }
- b->used ^= (a->used ^ b->used) & (unsigned int)mask;
- #if (!defined(WOLFSSL_SP_MATH) && !defined(WOLFSSL_SP_MATH_ALL)) || \
- defined(WOLFSSL_SP_INT_NEGATIVE)
- b->sign ^= (a->sign ^ b->sign) & (unsigned int)mask;
- #endif
- }
- return err;
- }
- #endif /* HAVE_ECC || WOLFSSL_MP_COND_COPY */
- #ifndef WC_NO_RNG
- int get_rand_digit(WC_RNG* rng, mp_digit* d)
- {
- return wc_RNG_GenerateBlock(rng, (byte*)d, sizeof(mp_digit));
- }
- #if defined(WC_RSA_BLINDING) || defined(WOLFCRYPT_HAVE_SAKKE)
- int mp_rand(mp_int* a, int digits, WC_RNG* rng)
- {
- int ret = 0;
- int cnt = digits * (int)sizeof(mp_digit);
- if (rng == NULL) {
- ret = MISSING_RNG_E;
- }
- else if (a == NULL || digits <= 0) {
- ret = BAD_FUNC_ARG;
- }
- #ifdef USE_INTEGER_HEAP_MATH
- /* allocate space for digits */
- if (ret == MP_OKAY) {
- ret = mp_set_bit(a, digits * DIGIT_BIT - 1);
- }
- #else
- #if defined(WOLFSSL_SP_MATH) || defined(WOLFSSL_SP_MATH_ALL)
- if ((ret == MP_OKAY) && ((unsigned int)digits > a->size))
- #else
- if ((ret == MP_OKAY) && (digits > FP_SIZE))
- #endif
- {
- ret = BAD_FUNC_ARG;
- }
- if (ret == MP_OKAY) {
- a->used = (word32)digits;
- }
- #endif
- /* fill the data with random bytes */
- if (ret == MP_OKAY) {
- ret = wc_RNG_GenerateBlock(rng, (byte*)a->dp, (word32)cnt);
- }
- if (ret == MP_OKAY) {
- #ifdef USE_INTEGER_HEAP_MATH
- int i;
- /* Mask down each digit to only bits used */
- for (i = 0; i < a->used; i++) {
- a->dp[i] &= MP_MASK;
- }
- #endif
- /* ensure top digit is not zero */
- while ((ret == MP_OKAY) && (a->dp[a->used - 1] == 0)) {
- ret = get_rand_digit(rng, &a->dp[a->used - 1]);
- #ifdef USE_INTEGER_HEAP_MATH
- a->dp[a->used - 1] &= MP_MASK;
- #endif
- }
- }
- return ret;
- }
- #endif /* WC_RSA_BLINDING || WOLFCRYPT_HAVE_SAKKE */
- #endif /* !WC_NO_RNG */
- #if defined(HAVE_ECC) || defined(WOLFSSL_EXPORT_INT)
- /* export an mp_int as unsigned char or hex string
- * encType is WC_TYPE_UNSIGNED_BIN or WC_TYPE_HEX_STR
- * return MP_OKAY on success */
- int wc_export_int(mp_int* mp, byte* buf, word32* len, word32 keySz,
- int encType)
- {
- int err;
- if (mp == NULL || buf == NULL || len == NULL)
- return BAD_FUNC_ARG;
- if (encType == WC_TYPE_HEX_STR) {
- /* for WC_TYPE_HEX_STR the keySz is not used.
- * The size is computed via mp_radix_size and checked with len input */
- #ifdef WC_MP_TO_RADIX
- int size = 0;
- err = mp_radix_size(mp, MP_RADIX_HEX, &size);
- if (err == MP_OKAY) {
- /* make sure we can fit result */
- if (*len < (word32)size) {
- *len = (word32)size;
- return BUFFER_E;
- }
- *len = (word32)size;
- err = mp_tohex(mp, (char*)buf);
- }
- #else
- err = NOT_COMPILED_IN;
- #endif
- }
- else {
- /* for WC_TYPE_UNSIGNED_BIN keySz is used to zero pad.
- * The key size is always returned as the size */
- if (*len < keySz) {
- *len = keySz;
- return BUFFER_E;
- }
- *len = keySz;
- XMEMSET(buf, 0, *len);
- err = mp_to_unsigned_bin(mp, buf +
- (keySz - (word32)mp_unsigned_bin_size(mp)));
- }
- return err;
- }
- #endif
- #ifdef HAVE_WOLF_BIGINT
- void wc_bigint_init(WC_BIGINT* a)
- {
- if (a != NULL) {
- a->buf = NULL;
- a->len = 0;
- a->heap = NULL;
- }
- }
- int wc_bigint_alloc(WC_BIGINT* a, word32 sz)
- {
- int err = MP_OKAY;
- if (a == NULL)
- return BAD_FUNC_ARG;
- if (sz > 0) {
- if (a->buf && sz > a->len) {
- wc_bigint_free(a);
- }
- if (a->buf == NULL) {
- a->buf = (byte*)XMALLOC(sz, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
- if (a->buf == NULL) {
- err = MP_MEM;
- }
- }
- else {
- XMEMSET(a->buf, 0, sz);
- }
- }
- a->len = sz;
- return err;
- }
- /* assumes input is big endian format */
- int wc_bigint_from_unsigned_bin(WC_BIGINT* a, const byte* in, word32 inlen)
- {
- int err;
- if (a == NULL || in == NULL || inlen == 0)
- return BAD_FUNC_ARG;
- err = wc_bigint_alloc(a, inlen);
- if (err == 0) {
- XMEMCPY(a->buf, in, inlen);
- }
- return err;
- }
- int wc_bigint_to_unsigned_bin(WC_BIGINT* a, byte* out, word32* outlen)
- {
- word32 sz;
- if (a == NULL || out == NULL || outlen == NULL || *outlen == 0)
- return BAD_FUNC_ARG;
- /* trim to fit into output buffer */
- sz = a->len;
- if (a->len > *outlen) {
- WOLFSSL_MSG("wc_bigint_export: Truncating output");
- sz = *outlen;
- }
- if (a->buf) {
- XMEMCPY(out, a->buf, sz);
- }
- *outlen = sz;
- return MP_OKAY;
- }
- void wc_bigint_zero(WC_BIGINT* a)
- {
- if (a && a->buf) {
- ForceZero(a->buf, a->len);
- }
- }
- void wc_bigint_free(WC_BIGINT* a)
- {
- if (a) {
- if (a->buf) {
- XFREE(a->buf, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
- }
- a->buf = NULL;
- a->len = 0;
- }
- }
- /* sz: make sure the buffer is at least that size and zero padded.
- * A `sz == 0` will use the size of `src`.
- * The calculated sz is stored into dst->len in `wc_bigint_alloc`.
- */
- int wc_mp_to_bigint_sz(mp_int* src, WC_BIGINT* dst, word32 sz)
- {
- int err;
- word32 x;
- if (src == NULL || dst == NULL)
- return BAD_FUNC_ARG;
- /* get size of source */
- x = mp_unsigned_bin_size(src);
- if (sz < x)
- sz = x;
- /* make sure destination is allocated and large enough */
- err = wc_bigint_alloc(dst, sz);
- if (err == MP_OKAY && sz > 0) {
- /* leading zero pad */
- word32 y = sz - x;
- XMEMSET(dst->buf, 0, y);
- /* export src as unsigned bin to destination buf */
- err = mp_to_unsigned_bin(src, dst->buf + y);
- }
- return err;
- }
- int wc_mp_to_bigint(mp_int* src, WC_BIGINT* dst)
- {
- if (src == NULL || dst == NULL)
- return BAD_FUNC_ARG;
- return wc_mp_to_bigint_sz(src, dst, 0);
- }
- int wc_bigint_to_mp(WC_BIGINT* src, mp_int* dst)
- {
- int err;
- if (src == NULL || dst == NULL)
- return BAD_FUNC_ARG;
- if (src->buf == NULL)
- return BAD_FUNC_ARG;
- err = mp_read_unsigned_bin(dst, src->buf, src->len);
- wc_bigint_free(src);
- return err;
- }
- #endif /* HAVE_WOLF_BIGINT */
- #endif /* !NO_BIG_INT || WOLFSSL_SP_MATH */
- #ifdef HAVE_WC_INTROSPECTION
- const char *wc_GetMathInfo(void)
- {
- return
- "\tMulti-Precision: "
- #ifdef WOLFSSL_SP_MATH_ALL
- "Wolf(SP)"
- #ifdef WOLFSSL_SP_NO_DYN_STACK
- " no-dyn-stack"
- #endif
- " word-size=" WC_STRINGIFY(SP_WORD_SIZE)
- " bits=" WC_STRINGIFY(SP_INT_BITS)
- " sp_int.c"
- #elif defined(USE_FAST_MATH)
- "Fast"
- " max-bits=" WC_STRINGIFY(FP_MAX_BITS)
- #ifndef TFM_TIMING_RESISTANT
- " not-constant-time"
- #endif
- " tfm.c"
- #elif defined(USE_INTEGER_HEAP_MATH)
- "Heap"
- " not-constant-time"
- " integer.c"
- #elif defined(NO_BIG_INT) || defined(WOLFSSL_SP_MATH)
- "Disabled"
- #else
- "Unknown"
- #endif
- #if defined(WOLFSSL_HAVE_SP_ECC) || defined(WOLFSSL_HAVE_SP_DH) || \
- defined(WOLFSSL_HAVE_SP_RSA)
- "\n\tSingle Precision:"
- #ifdef WOLFSSL_HAVE_SP_ECC
- " ecc"
- #ifndef WOLFSSL_SP_NO_256
- " 256"
- #endif
- #ifdef WOLFSSL_SP_384
- " 384"
- #endif
- #ifdef WOLFSSL_SP_521
- " 521"
- #endif
- #endif
- #if defined(WOLFSSL_HAVE_SP_RSA) && defined(WOLFSSL_HAVE_SP_DH)
- " rsa/dh"
- #elif defined(WOLFSSL_HAVE_SP_RSA)
- " rsa"
- #elif defined(WOLFSSL_HAVE_SP_DH)
- " dh"
- #endif
- #ifndef WOLFSSL_SP_NO_2048
- " 2048"
- #endif
- #ifndef WOLFSSL_SP_NO_3072
- " 3072"
- #endif
- #ifdef WOLFSSL_SP_4096
- " 4096"
- #endif
- #ifdef WOLFSSL_SP_ASM
- " asm"
- #endif
- #if !defined(WOLFSSL_SP_ASM)
- #if defined(SP_WORD_SIZE) && SP_WORD_SIZE == 32
- " sp_c32.c"
- #else
- " sp_c64.c"
- #endif
- #elif defined(WOLFSSL_SP_ARM32_ASM)
- " sp_arm32.c"
- #elif defined(WOLFSSL_SP_ARM64_ASM)
- " sp_arm64.c"
- #elif defined(WOLFSSL_SP_ARM_THUMB_ASM)
- " sp_armthumb.c"
- #elif defined(WOLFSSL_SP_ARM_CORTEX_M_ASM)
- " sp_cortexm.c"
- #elif defined(WOLFSSL_SP_X86_64_ASM)
- " sp_x86_64.c"
- #else
- " sp_[arch].c"
- #endif
- #endif
- /* other SP math options */
- #if defined(WOLFSSL_SP_MATH_ALL) || defined(WOLFSSL_HAVE_SP_ECC) || \
- defined(WOLFSSL_HAVE_SP_DH) || defined(WOLFSSL_HAVE_SP_RSA)
- #ifdef WOLFSSL_SP_SMALL
- " small"
- #endif
- #ifdef WOLFSSL_SP_NO_MALLOC
- " no-malloc"
- #endif
- #endif
- ;
- }
- #endif /* HAVE_WC_INTROSPECTION */
|