Xuyi Wang / wolfcrypt

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   OS

src/wolfmath.c@0:1387ff3eed4a, 2019-11-20 (annotated)

Committer:
sPymbed
Date:
Wed Nov 20 13:28:01 2019 +0000
Revision:
0:1387ff3eed4a
initial version

Who changed what in which revision?

UserRevisionLine numberNew contents of line
sPymbed 0:1387ff3eed4a 1 /* wolfmath.c
sPymbed 0:1387ff3eed4a 2 *
sPymbed 0:1387ff3eed4a 3 * Copyright (C) 2006-2017 wolfSSL Inc.
sPymbed 0:1387ff3eed4a 4 *
sPymbed 0:1387ff3eed4a 5 * This file is part of wolfSSL.
sPymbed 0:1387ff3eed4a 6 *
sPymbed 0:1387ff3eed4a 7 * wolfSSL is free software; you can redistribute it and/or modify
sPymbed 0:1387ff3eed4a 8 * it under the terms of the GNU General Public License as published by
sPymbed 0:1387ff3eed4a 9 * the Free Software Foundation; either version 2 of the License, or
sPymbed 0:1387ff3eed4a 10 * (at your option) any later version.
sPymbed 0:1387ff3eed4a 11 *
sPymbed 0:1387ff3eed4a 12 * wolfSSL is distributed in the hope that it will be useful,
sPymbed 0:1387ff3eed4a 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
sPymbed 0:1387ff3eed4a 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
sPymbed 0:1387ff3eed4a 15 * GNU General Public License for more details.
sPymbed 0:1387ff3eed4a 16 *
sPymbed 0:1387ff3eed4a 17 * You should have received a copy of the GNU General Public License
sPymbed 0:1387ff3eed4a 18 * along with this program; if not, write to the Free Software
sPymbed 0:1387ff3eed4a 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
sPymbed 0:1387ff3eed4a 20 */
sPymbed 0:1387ff3eed4a 21
sPymbed 0:1387ff3eed4a 22
sPymbed 0:1387ff3eed4a 23 /* common functions for either math library */
sPymbed 0:1387ff3eed4a 24
sPymbed 0:1387ff3eed4a 25 #ifdef HAVE_CONFIG_H
sPymbed 0:1387ff3eed4a 26 #include <config.h>
sPymbed 0:1387ff3eed4a 27 #endif
sPymbed 0:1387ff3eed4a 28
sPymbed 0:1387ff3eed4a 29 /* in case user set USE_FAST_MATH there */
sPymbed 0:1387ff3eed4a 30 #include <wolfcrypt/settings.h>
sPymbed 0:1387ff3eed4a 31
sPymbed 0:1387ff3eed4a 32 #ifdef USE_FAST_MATH
sPymbed 0:1387ff3eed4a 33 #include <wolfcrypt/tfm.h>
sPymbed 0:1387ff3eed4a 34 #else
sPymbed 0:1387ff3eed4a 35 #include <wolfcrypt/integer.h>
sPymbed 0:1387ff3eed4a 36 #endif
sPymbed 0:1387ff3eed4a 37
sPymbed 0:1387ff3eed4a 38 #include <wolfcrypt/error-crypt.h>
sPymbed 0:1387ff3eed4a 39 #include <wolfcrypt/logging.h>
sPymbed 0:1387ff3eed4a 40
sPymbed 0:1387ff3eed4a 41 #if defined(USE_FAST_MATH) || !defined(NO_BIG_INT)
sPymbed 0:1387ff3eed4a 42
sPymbed 0:1387ff3eed4a 43 #ifdef WOLFSSL_ASYNC_CRYPT
sPymbed 0:1387ff3eed4a 44 #include <wolfcrypt/async.h>
sPymbed 0:1387ff3eed4a 45 #endif
sPymbed 0:1387ff3eed4a 46
sPymbed 0:1387ff3eed4a 47 #ifdef NO_INLINE
sPymbed 0:1387ff3eed4a 48 #include <wolfcrypt/misc.h>
sPymbed 0:1387ff3eed4a 49 #else
sPymbed 0:1387ff3eed4a 50 #define WOLFSSL_MISC_INCLUDED
sPymbed 0:1387ff3eed4a 51 #include <wolfcrypt/src/misc.c>
sPymbed 0:1387ff3eed4a 52 #endif
sPymbed 0:1387ff3eed4a 53
sPymbed 0:1387ff3eed4a 54
sPymbed 0:1387ff3eed4a 55 #if !defined(WC_NO_CACHE_RESISTANT) && \
sPymbed 0:1387ff3eed4a 56 ((defined(HAVE_ECC) && defined(ECC_TIMING_RESISTANT)) || \
sPymbed 0:1387ff3eed4a 57 (defined(USE_FAST_MATH) && defined(TFM_TIMING_RESISTANT)))
sPymbed 0:1387ff3eed4a 58
sPymbed 0:1387ff3eed4a 59 /* all off / all on pointer addresses for constant calculations */
sPymbed 0:1387ff3eed4a 60 /* ecc.c uses same table */
sPymbed 0:1387ff3eed4a 61 const wolfssl_word wc_off_on_addr[2] =
sPymbed 0:1387ff3eed4a 62 {
sPymbed 0:1387ff3eed4a 63 #if defined(WC_64BIT_CPU)
sPymbed 0:1387ff3eed4a 64 W64LIT(0x0000000000000000),
sPymbed 0:1387ff3eed4a 65 W64LIT(0xffffffffffffffff)
sPymbed 0:1387ff3eed4a 66 #elif defined(WC_16BIT_CPU)
sPymbed 0:1387ff3eed4a 67 0x0000U,
sPymbed 0:1387ff3eed4a 68 0xffffU
sPymbed 0:1387ff3eed4a 69 #else
sPymbed 0:1387ff3eed4a 70 /* 32 bit */
sPymbed 0:1387ff3eed4a 71 0x00000000U,
sPymbed 0:1387ff3eed4a 72 0xffffffffU
sPymbed 0:1387ff3eed4a 73 #endif
sPymbed 0:1387ff3eed4a 74 };
sPymbed 0:1387ff3eed4a 75 #endif
sPymbed 0:1387ff3eed4a 76
sPymbed 0:1387ff3eed4a 77
sPymbed 0:1387ff3eed4a 78 int get_digit_count(mp_int* a)
sPymbed 0:1387ff3eed4a 79 {
sPymbed 0:1387ff3eed4a 80 if (a == NULL)
sPymbed 0:1387ff3eed4a 81 return 0;
sPymbed 0:1387ff3eed4a 82
sPymbed 0:1387ff3eed4a 83 return a->used;
sPymbed 0:1387ff3eed4a 84 }
sPymbed 0:1387ff3eed4a 85
sPymbed 0:1387ff3eed4a 86 mp_digit get_digit(mp_int* a, int n)
sPymbed 0:1387ff3eed4a 87 {
sPymbed 0:1387ff3eed4a 88 if (a == NULL)
sPymbed 0:1387ff3eed4a 89 return 0;
sPymbed 0:1387ff3eed4a 90
sPymbed 0:1387ff3eed4a 91 return (n >= a->used || n < 0) ? 0 : a->dp[n];
sPymbed 0:1387ff3eed4a 92 }
sPymbed 0:1387ff3eed4a 93
sPymbed 0:1387ff3eed4a 94 int get_rand_digit(WC_RNG* rng, mp_digit* d)
sPymbed 0:1387ff3eed4a 95 {
sPymbed 0:1387ff3eed4a 96 return wc_RNG_GenerateBlock(rng, (byte*)d, sizeof(mp_digit));
sPymbed 0:1387ff3eed4a 97 }
sPymbed 0:1387ff3eed4a 98
sPymbed 0:1387ff3eed4a 99 #ifdef WC_RSA_BLINDING
sPymbed 0:1387ff3eed4a 100 int mp_rand(mp_int* a, int digits, WC_RNG* rng)
sPymbed 0:1387ff3eed4a 101 {
sPymbed 0:1387ff3eed4a 102 int ret = 0;
sPymbed 0:1387ff3eed4a 103 DECLARE_VAR(d, mp_digit, 1, rng->heap);
sPymbed 0:1387ff3eed4a 104
sPymbed 0:1387ff3eed4a 105 if (rng == NULL) {
sPymbed 0:1387ff3eed4a 106 ret = MISSING_RNG_E; goto exit;
sPymbed 0:1387ff3eed4a 107 }
sPymbed 0:1387ff3eed4a 108
sPymbed 0:1387ff3eed4a 109 if (a == NULL
sPymbed 0:1387ff3eed4a 110 #ifdef WOLFSSL_ASYNC_CRYPT
sPymbed 0:1387ff3eed4a 111 || d == NULL
sPymbed 0:1387ff3eed4a 112 #endif
sPymbed 0:1387ff3eed4a 113 ) {
sPymbed 0:1387ff3eed4a 114 ret = BAD_FUNC_ARG; goto exit;
sPymbed 0:1387ff3eed4a 115 }
sPymbed 0:1387ff3eed4a 116
sPymbed 0:1387ff3eed4a 117 mp_zero(a);
sPymbed 0:1387ff3eed4a 118 if (digits <= 0) {
sPymbed 0:1387ff3eed4a 119 ret = MP_OKAY; goto exit;
sPymbed 0:1387ff3eed4a 120 }
sPymbed 0:1387ff3eed4a 121
sPymbed 0:1387ff3eed4a 122 /* first place a random non-zero digit */
sPymbed 0:1387ff3eed4a 123 do {
sPymbed 0:1387ff3eed4a 124 ret = get_rand_digit(rng, d);
sPymbed 0:1387ff3eed4a 125 if (ret != 0) {
sPymbed 0:1387ff3eed4a 126 goto exit;
sPymbed 0:1387ff3eed4a 127 }
sPymbed 0:1387ff3eed4a 128 } while (*d == 0);
sPymbed 0:1387ff3eed4a 129
sPymbed 0:1387ff3eed4a 130 if ((ret = mp_add_d(a, *d, a)) != MP_OKAY) {
sPymbed 0:1387ff3eed4a 131 goto exit;
sPymbed 0:1387ff3eed4a 132 }
sPymbed 0:1387ff3eed4a 133
sPymbed 0:1387ff3eed4a 134 while (--digits > 0) {
sPymbed 0:1387ff3eed4a 135 if ((ret = mp_lshd(a, 1)) != MP_OKAY) {
sPymbed 0:1387ff3eed4a 136 goto exit;
sPymbed 0:1387ff3eed4a 137 }
sPymbed 0:1387ff3eed4a 138 if ((ret = get_rand_digit(rng, d)) != 0) {
sPymbed 0:1387ff3eed4a 139 goto exit;
sPymbed 0:1387ff3eed4a 140 }
sPymbed 0:1387ff3eed4a 141 if ((ret = mp_add_d(a, *d, a)) != MP_OKAY) {
sPymbed 0:1387ff3eed4a 142 goto exit;
sPymbed 0:1387ff3eed4a 143 }
sPymbed 0:1387ff3eed4a 144 }
sPymbed 0:1387ff3eed4a 145
sPymbed 0:1387ff3eed4a 146 exit:
sPymbed 0:1387ff3eed4a 147 FREE_VAR(d, rng->heap);
sPymbed 0:1387ff3eed4a 148
sPymbed 0:1387ff3eed4a 149 return ret;
sPymbed 0:1387ff3eed4a 150 }
sPymbed 0:1387ff3eed4a 151 #endif /* WC_RSA_BLINDING */
sPymbed 0:1387ff3eed4a 152
sPymbed 0:1387ff3eed4a 153
sPymbed 0:1387ff3eed4a 154 #ifdef HAVE_WOLF_BIGINT
sPymbed 0:1387ff3eed4a 155 void wc_bigint_init(WC_BIGINT* a)
sPymbed 0:1387ff3eed4a 156 {
sPymbed 0:1387ff3eed4a 157 if (a != NULL) {
sPymbed 0:1387ff3eed4a 158 a->buf = NULL;
sPymbed 0:1387ff3eed4a 159 a->len = 0;
sPymbed 0:1387ff3eed4a 160 a->heap = NULL;
sPymbed 0:1387ff3eed4a 161 }
sPymbed 0:1387ff3eed4a 162 }
sPymbed 0:1387ff3eed4a 163
sPymbed 0:1387ff3eed4a 164 int wc_bigint_alloc(WC_BIGINT* a, word32 sz)
sPymbed 0:1387ff3eed4a 165 {
sPymbed 0:1387ff3eed4a 166 int err = MP_OKAY;
sPymbed 0:1387ff3eed4a 167
sPymbed 0:1387ff3eed4a 168 if (a == NULL)
sPymbed 0:1387ff3eed4a 169 return BAD_FUNC_ARG;
sPymbed 0:1387ff3eed4a 170
sPymbed 0:1387ff3eed4a 171 if (sz > 0) {
sPymbed 0:1387ff3eed4a 172 if (a->buf && sz > a->len) {
sPymbed 0:1387ff3eed4a 173 wc_bigint_free(a);
sPymbed 0:1387ff3eed4a 174 }
sPymbed 0:1387ff3eed4a 175 if (a->buf == NULL) {
sPymbed 0:1387ff3eed4a 176 a->buf = (byte*)XMALLOC(sz, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
sPymbed 0:1387ff3eed4a 177 }
sPymbed 0:1387ff3eed4a 178 if (a->buf == NULL) {
sPymbed 0:1387ff3eed4a 179 err = MP_MEM;
sPymbed 0:1387ff3eed4a 180 }
sPymbed 0:1387ff3eed4a 181 else {
sPymbed 0:1387ff3eed4a 182 XMEMSET(a->buf, 0, sz);
sPymbed 0:1387ff3eed4a 183 }
sPymbed 0:1387ff3eed4a 184 }
sPymbed 0:1387ff3eed4a 185 a->len = sz;
sPymbed 0:1387ff3eed4a 186
sPymbed 0:1387ff3eed4a 187 return err;
sPymbed 0:1387ff3eed4a 188 }
sPymbed 0:1387ff3eed4a 189
sPymbed 0:1387ff3eed4a 190 /* assumes input is big endian format */
sPymbed 0:1387ff3eed4a 191 int wc_bigint_from_unsigned_bin(WC_BIGINT* a, const byte* in, word32 inlen)
sPymbed 0:1387ff3eed4a 192 {
sPymbed 0:1387ff3eed4a 193 int err;
sPymbed 0:1387ff3eed4a 194
sPymbed 0:1387ff3eed4a 195 if (a == NULL || in == NULL || inlen == 0)
sPymbed 0:1387ff3eed4a 196 return BAD_FUNC_ARG;
sPymbed 0:1387ff3eed4a 197
sPymbed 0:1387ff3eed4a 198 err = wc_bigint_alloc(a, inlen);
sPymbed 0:1387ff3eed4a 199 if (err == 0) {
sPymbed 0:1387ff3eed4a 200 XMEMCPY(a->buf, in, inlen);
sPymbed 0:1387ff3eed4a 201 }
sPymbed 0:1387ff3eed4a 202
sPymbed 0:1387ff3eed4a 203 return err;
sPymbed 0:1387ff3eed4a 204 }
sPymbed 0:1387ff3eed4a 205
sPymbed 0:1387ff3eed4a 206 int wc_bigint_to_unsigned_bin(WC_BIGINT* a, byte* out, word32* outlen)
sPymbed 0:1387ff3eed4a 207 {
sPymbed 0:1387ff3eed4a 208 word32 sz;
sPymbed 0:1387ff3eed4a 209
sPymbed 0:1387ff3eed4a 210 if (a == NULL || out == NULL || outlen == NULL || *outlen == 0)
sPymbed 0:1387ff3eed4a 211 return BAD_FUNC_ARG;
sPymbed 0:1387ff3eed4a 212
sPymbed 0:1387ff3eed4a 213 /* trim to fit into output buffer */
sPymbed 0:1387ff3eed4a 214 sz = a->len;
sPymbed 0:1387ff3eed4a 215 if (a->len > *outlen) {
sPymbed 0:1387ff3eed4a 216 WOLFSSL_MSG("wc_bigint_export: Truncating output");
sPymbed 0:1387ff3eed4a 217 sz = *outlen;
sPymbed 0:1387ff3eed4a 218 }
sPymbed 0:1387ff3eed4a 219
sPymbed 0:1387ff3eed4a 220 if (a->buf) {
sPymbed 0:1387ff3eed4a 221 XMEMCPY(out, a->buf, sz);
sPymbed 0:1387ff3eed4a 222 }
sPymbed 0:1387ff3eed4a 223
sPymbed 0:1387ff3eed4a 224 *outlen = sz;
sPymbed 0:1387ff3eed4a 225
sPymbed 0:1387ff3eed4a 226 return MP_OKAY;
sPymbed 0:1387ff3eed4a 227 }
sPymbed 0:1387ff3eed4a 228
sPymbed 0:1387ff3eed4a 229 void wc_bigint_zero(WC_BIGINT* a)
sPymbed 0:1387ff3eed4a 230 {
sPymbed 0:1387ff3eed4a 231 if (a && a->buf) {
sPymbed 0:1387ff3eed4a 232 ForceZero(a->buf, a->len);
sPymbed 0:1387ff3eed4a 233 }
sPymbed 0:1387ff3eed4a 234 }
sPymbed 0:1387ff3eed4a 235
sPymbed 0:1387ff3eed4a 236 void wc_bigint_free(WC_BIGINT* a)
sPymbed 0:1387ff3eed4a 237 {
sPymbed 0:1387ff3eed4a 238 if (a) {
sPymbed 0:1387ff3eed4a 239 if (a->buf) {
sPymbed 0:1387ff3eed4a 240 XFREE(a->buf, a->heap, DYNAMIC_TYPE_WOLF_BIGINT);
sPymbed 0:1387ff3eed4a 241 }
sPymbed 0:1387ff3eed4a 242 a->buf = NULL;
sPymbed 0:1387ff3eed4a 243 a->len = 0;
sPymbed 0:1387ff3eed4a 244 }
sPymbed 0:1387ff3eed4a 245 }
sPymbed 0:1387ff3eed4a 246
sPymbed 0:1387ff3eed4a 247 /* sz: make sure the buffer is at least that size and zero padded.
sPymbed 0:1387ff3eed4a 248 * A `sz == 0` will use the size of `src`.
sPymbed 0:1387ff3eed4a 249 * The calulcates sz is stored into dst->len in `wc_bigint_alloc`.
sPymbed 0:1387ff3eed4a 250 */
sPymbed 0:1387ff3eed4a 251 int wc_mp_to_bigint_sz(mp_int* src, WC_BIGINT* dst, word32 sz)
sPymbed 0:1387ff3eed4a 252 {
sPymbed 0:1387ff3eed4a 253 int err;
sPymbed 0:1387ff3eed4a 254 word32 x, y;
sPymbed 0:1387ff3eed4a 255
sPymbed 0:1387ff3eed4a 256 if (src == NULL || dst == NULL)
sPymbed 0:1387ff3eed4a 257 return BAD_FUNC_ARG;
sPymbed 0:1387ff3eed4a 258
sPymbed 0:1387ff3eed4a 259 /* get size of source */
sPymbed 0:1387ff3eed4a 260 x = mp_unsigned_bin_size(src);
sPymbed 0:1387ff3eed4a 261 if (sz < x)
sPymbed 0:1387ff3eed4a 262 sz = x;
sPymbed 0:1387ff3eed4a 263
sPymbed 0:1387ff3eed4a 264 /* make sure destination is allocated and large enough */
sPymbed 0:1387ff3eed4a 265 err = wc_bigint_alloc(dst, sz);
sPymbed 0:1387ff3eed4a 266 if (err == MP_OKAY) {
sPymbed 0:1387ff3eed4a 267
sPymbed 0:1387ff3eed4a 268 /* leading zero pad */
sPymbed 0:1387ff3eed4a 269 y = sz - x;
sPymbed 0:1387ff3eed4a 270 XMEMSET(dst->buf, 0, y);
sPymbed 0:1387ff3eed4a 271
sPymbed 0:1387ff3eed4a 272 /* export src as unsigned bin to destination buf */
sPymbed 0:1387ff3eed4a 273 err = mp_to_unsigned_bin(src, dst->buf + y);
sPymbed 0:1387ff3eed4a 274 }
sPymbed 0:1387ff3eed4a 275
sPymbed 0:1387ff3eed4a 276 return err;
sPymbed 0:1387ff3eed4a 277 }
sPymbed 0:1387ff3eed4a 278
sPymbed 0:1387ff3eed4a 279 int wc_mp_to_bigint(mp_int* src, WC_BIGINT* dst)
sPymbed 0:1387ff3eed4a 280 {
sPymbed 0:1387ff3eed4a 281 if (src == NULL || dst == NULL)
sPymbed 0:1387ff3eed4a 282 return BAD_FUNC_ARG;
sPymbed 0:1387ff3eed4a 283
sPymbed 0:1387ff3eed4a 284 return wc_mp_to_bigint_sz(src, dst, 0);
sPymbed 0:1387ff3eed4a 285 }
sPymbed 0:1387ff3eed4a 286
sPymbed 0:1387ff3eed4a 287 int wc_bigint_to_mp(WC_BIGINT* src, mp_int* dst)
sPymbed 0:1387ff3eed4a 288 {
sPymbed 0:1387ff3eed4a 289 int err;
sPymbed 0:1387ff3eed4a 290
sPymbed 0:1387ff3eed4a 291 if (src == NULL || dst == NULL)
sPymbed 0:1387ff3eed4a 292 return BAD_FUNC_ARG;
sPymbed 0:1387ff3eed4a 293
sPymbed 0:1387ff3eed4a 294 if (src->buf == NULL)
sPymbed 0:1387ff3eed4a 295 return BAD_FUNC_ARG;
sPymbed 0:1387ff3eed4a 296
sPymbed 0:1387ff3eed4a 297 err = mp_read_unsigned_bin(dst, src->buf, src->len);
sPymbed 0:1387ff3eed4a 298 wc_bigint_free(src);
sPymbed 0:1387ff3eed4a 299
sPymbed 0:1387ff3eed4a 300 return err;
sPymbed 0:1387ff3eed4a 301 }
sPymbed 0:1387ff3eed4a 302
sPymbed 0:1387ff3eed4a 303 #endif /* HAVE_WOLF_BIGINT */
sPymbed 0:1387ff3eed4a 304
sPymbed 0:1387ff3eed4a 305 #endif /* USE_FAST_MATH || !NO_BIG_INT */
sPymbed 0:1387ff3eed4a 306