wolfmath.c

00001 /* wolfmath.c
00002  *
00003  * Copyright (C) 2006-2020 wolfSSL Inc.
00004  *
00005  * This file is part of wolfSSL.
00006  *
00007  * wolfSSL is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 2 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * wolfSSL is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
00020  */
00021 
00022 
00023 /* common functions for either math library */
00024 
00025 #ifdef HAVE_CONFIG_H
00026     #include <config.h>
00027 #endif
00028 
00029 /* in case user set USE_FAST_MATH there */
00030 #include <wolfssl/wolfcrypt/settings.h>
00031 
00032 #include <wolfssl/wolfcrypt/integer.h>
00033 
00034 #include <wolfssl/wolfcrypt/error-crypt.h >
00035 #include <wolfssl/wolfcrypt/logging.h >
00036 
00037 #if defined(USE_FAST_MATH) || !defined(NO_BIG_INT)
00038 
00039 #ifdef WOLFSSL_ASYNC_CRYPT
00040     #include <wolfssl/wolfcrypt/async.h>
00041 #endif
00042 
00043 #ifdef NO_INLINE
00044     #include <wolfssl/wolfcrypt/misc.h>
00045 #else
00046     #define WOLFSSL_MISC_INCLUDED
00047     #include <wolfcrypt/src/misc.c>
00048 #endif
00049 
00050 
00051 #if !defined(WC_NO_CACHE_RESISTANT) && \
00052     ((defined(HAVE_ECC) && defined(ECC_TIMING_RESISTANT)) || \
00053      (defined(USE_FAST_MATH) && defined(TFM_TIMING_RESISTANT)))
00054 
00055     /* all off / all on pointer addresses for constant calculations */
00056     /* ecc.c uses same table */
00057     const wolfssl_word wc_off_on_addr[2] =
00058     {
00059     #if defined(WC_64BIT_CPU)
00060         W64LIT(0x0000000000000000),
00061         W64LIT(0xffffffffffffffff)
00062     #elif defined(WC_16BIT_CPU)
00063         0x0000U,
00064         0xffffU
00065     #else
00066         /* 32 bit */
00067         0x00000000U,
00068         0xffffffffU
00069     #endif
00070     };
00071 #endif
00072 
00073 
00074 #if !defined(WOLFSSL_SP_MATH)
00075 int get_digit_count(mp_int* a)
00076 {
00077     if (a == NULL)
00078         return 0;
00079 
00080     return a->used;
00081 }
00082 #endif
00083 
00084 mp_digit get_digit(mp_int* a, int n)
00085 {
00086     if (a == NULL)
00087         return 0;
00088 
00089     return (n >= a->used || n < 0) ? 0 : a->dp[n];
00090 }
00091 
00092 /* Conditionally copy a into b. Performed in constant time.
00093  *
00094  * a     MP integer to copy.
00095  * copy  On 1, copy a into b. on 0 leave b unchanged.
00096  * b     MP integer to copy into.
00097  * returns BAD_FUNC_ARG when a or b is NULL, MEMORY_E when growing b fails and
00098  *         MP_OKAY otherwise.
00099  */
00100 int mp_cond_copy(mp_int* a, int copy, mp_int* b)
00101 {
00102     int err = MP_OKAY;
00103     int i;
00104     mp_digit mask = (mp_digit)0 - copy;
00105 
00106     if (a == NULL || b == NULL)
00107         err = BAD_FUNC_ARG;
00108 
00109     /* Ensure b has enough space to copy a into */
00110     if (err == MP_OKAY)
00111         err = mp_grow(b, a->used + 1);
00112     if (err == MP_OKAY) {
00113         /* When mask 0, b is unchanged2
00114          * When mask all set, b ^ b ^ a = a
00115          */
00116         /* Conditionaly copy all digits and then number of used diigits.
00117          * get_digit() returns 0 when index greater than available digit.
00118          */
00119         for (i = 0; i < a->used; i++) {
00120             b->dp[i] ^= (get_digit(a, i) ^ get_digit(b, i)) & mask;
00121         }
00122         for (; i < b->used; i++) {
00123             b->dp[i] ^= (get_digit(a, i) ^ get_digit(b, i)) & mask;
00124         }
00125         b->used ^= (a->used ^ b->used) & (int)mask;
00126     }
00127 
00128     return err;
00129 }
00130 
00131 #ifndef WC_NO_RNG
00132 int get_rand_digit(WC_RNG* rng, mp_digit* d)
00133 {
00134     return wc_RNG_GenerateBlock(rng, (byte*)d, sizeof(mp_digit));
00135 }
00136 
00137 #ifdef WC_RSA_BLINDING
00138 int mp_rand(mp_int* a, int digits, WC_RNG* rng)
00139 {
00140     int ret = 0;
00141     int cnt = digits * sizeof(mp_digit);
00142 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
00143     int i;
00144 #endif
00145 
00146     if (rng == NULL) {
00147         ret = MISSING_RNG_E;
00148     }
00149     else if (a == NULL) {
00150         ret = BAD_FUNC_ARG;
00151     }
00152 
00153 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
00154     /* allocate space for digits */
00155     if (ret == MP_OKAY) {
00156         ret = mp_set_bit(a, digits * DIGIT_BIT - 1);
00157     }
00158 #else
00159 #if defined(WOLFSSL_SP_MATH)
00160     if ((ret == MP_OKAY) && (digits > SP_INT_DIGITS))
00161 #else
00162     if ((ret == MP_OKAY) && (digits > FP_SIZE))
00163 #endif
00164     {
00165         ret = BAD_FUNC_ARG;
00166     }
00167     if (ret == MP_OKAY) {
00168         a->used = digits;
00169     }
00170 #endif
00171     /* fill the data with random bytes */
00172     if (ret == MP_OKAY) {
00173         ret = wc_RNG_GenerateBlock(rng, (byte*)a->dp, cnt);
00174     }
00175     if (ret == MP_OKAY) {
00176 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
00177         /* Mask down each digit to only bits used */
00178         for (i = 0; i < a->used; i++) {
00179             a->dp[i] &= MP_MASK;
00180         }
00181 #endif
00182         /* ensure top digit is not zero */
00183         while ((ret == MP_OKAY) && (a->dp[a->used - 1] == 0)) {
00184             ret = get_rand_digit(rng, &a->dp[a->used - 1]);
00185 #if !defined(USE_FAST_MATH) && !defined(WOLFSSL_SP_MATH)
00186             a->dp[a->used - 1] &= MP_MASK;
00187 #endif
00188         }
00189     }
00190 
00191     return ret;
00192 }
00193 #endif /* WC_RSA_BLINDING */
00194 #endif
00195 
00196 /* export an mp_int as unsigned char or hex string
00197  * encType is WC_TYPE_UNSIGNED_BIN or WC_TYPE_HEX_STR
00198  * return MP_OKAY on success */
00199 int wc_export_int(mp_int* mp, byte* buf, word32* len, word32 keySz,
00200     int encType)
00201 {
00202     int err;
00203 
00204     if (mp == NULL)
00205         return BAD_FUNC_ARG;
00206 
00207     /* check buffer size */
00208     if (*len < keySz) {
00209         *len = keySz;
00210         return BUFFER_E;
00211     }
00212 
00213     *len = keySz;
00214     XMEMSET(buf, 0, *len);
00215 
00216     if (encType == WC_TYPE_HEX_STR) {
00217     #ifdef WC_MP_TO_RADIX
00218         err = mp_tohex(mp, (char*)buf);
00219     #else
00220         err = NOT_COMPILED_IN;
00221     #endif
00222     }
00223     else {
00224         err = mp_to_unsigned_bin(mp, buf + (keySz - mp_unsigned_bin_size(mp)));
00225     }
00226 
00227     return err;
00228 }
00229 
00230 
00231 #ifdef HAVE_WOLF_BIGINT
00232 void wc_bigint_init(WC_BIGINT* a)
00233 {
00234     if (a != NULL) {
00235         a->buf = NULL;
00236         a->len = 0;
00237         a->heap = NULL;
00238     }
00239 }
00240 
00241 int wc_bigint_alloc(WC_BIGINT* a, word32 sz)
00242 {
00243     int err = MP_OKAY;
00244 
00245     if (a == NULL)
00246         return BAD_FUNC_ARG;
00247 
00248     if (sz > 0) {
00249         if (a->buf && sz > a->len) {
00250             wc_bigint_free(a);
00251         }
00252         if (a->buf == NULL) {
00253             a->buf = (byte*)XMALLOC(sz, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
00254             if (a->buf == NULL) {
00255                 err = MP_MEM;
00256             }
00257         }
00258         else {
00259             XMEMSET(a->buf, 0, sz);
00260         }
00261     }
00262     a->len = sz;
00263 
00264     return err;
00265 }
00266 
00267 /* assumes input is big endian format */
00268 int wc_bigint_from_unsigned_bin(WC_BIGINT* a, const byte* in, word32 inlen)
00269 {
00270     int err;
00271 
00272     if (a == NULL || in == NULL || inlen == 0)
00273         return BAD_FUNC_ARG;
00274 
00275     err = wc_bigint_alloc(a, inlen);
00276     if (err == 0) {
00277         XMEMCPY(a->buf, in, inlen);
00278     }
00279 
00280     return err;
00281 }
00282 
00283 int wc_bigint_to_unsigned_bin(WC_BIGINT* a, byte* out, word32* outlen)
00284 {
00285     word32 sz;
00286 
00287     if (a == NULL || out == NULL || outlen == NULL || *outlen == 0)
00288         return BAD_FUNC_ARG;
00289 
00290     /* trim to fit into output buffer */
00291     sz = a->len;
00292     if (a->len > *outlen) {
00293         WOLFSSL_MSG("wc_bigint_export: Truncating output");
00294         sz = *outlen;
00295     }
00296 
00297     if (a->buf) {
00298         XMEMCPY(out, a->buf, sz);
00299     }
00300 
00301     *outlen = sz;
00302 
00303     return MP_OKAY;
00304 }
00305 
00306 void wc_bigint_zero(WC_BIGINT* a)
00307 {
00308     if (a && a->buf) {
00309         ForceZero(a->buf, a->len);
00310     }
00311 }
00312 
00313 void wc_bigint_free(WC_BIGINT* a)
00314 {
00315     if (a) {
00316         if (a->buf) {
00317           XFREE(a->buf, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
00318         }
00319         a->buf = NULL;
00320         a->len = 0;
00321     }
00322 }
00323 
00324 /* sz: make sure the buffer is at least that size and zero padded.
00325  *     A `sz == 0` will use the size of `src`.
00326  *     The calulcates sz is stored into dst->len in `wc_bigint_alloc`.
00327  */
00328 int wc_mp_to_bigint_sz(mp_int* src, WC_BIGINT* dst, word32 sz)
00329 {
00330     int err;
00331     word32 x, y;
00332 
00333     if (src == NULL || dst == NULL)
00334         return BAD_FUNC_ARG;
00335 
00336     /* get size of source */
00337     x = mp_unsigned_bin_size(src);
00338     if (sz < x)
00339         sz = x;
00340 
00341     /* make sure destination is allocated and large enough */
00342     err = wc_bigint_alloc(dst, sz);
00343     if (err == MP_OKAY) {
00344 
00345         /* leading zero pad */
00346         y = sz - x;
00347         XMEMSET(dst->buf, 0, y);
00348 
00349         /* export src as unsigned bin to destination buf */
00350         err = mp_to_unsigned_bin(src, dst->buf + y);
00351     }
00352 
00353     return err;
00354 }
00355 
00356 int wc_mp_to_bigint(mp_int* src, WC_BIGINT* dst)
00357 {
00358     if (src == NULL || dst == NULL)
00359         return BAD_FUNC_ARG;
00360 
00361     return wc_mp_to_bigint_sz(src, dst, 0);
00362 }
00363 
00364 int wc_bigint_to_mp(WC_BIGINT* src, mp_int* dst)
00365 {
00366     int err;
00367 
00368     if (src == NULL || dst == NULL)
00369         return BAD_FUNC_ARG;
00370 
00371     if (src->buf == NULL)
00372         return BAD_FUNC_ARG;
00373 
00374     err = mp_read_unsigned_bin(dst, src->buf, src->len);
00375     wc_bigint_free(src);
00376 
00377     return err;
00378 }
00379 #endif /* HAVE_WOLF_BIGINT */
00380 
00381 #endif /* USE_FAST_MATH || !NO_BIG_INT */
00382