wolf SSL / wolfSSL

wolfSSL SSL/TLS library, support up to TLS1.3

Dependents:   CyaSSL-Twitter-OAuth4Tw Example-client-tls-cert TwitterReader TweetTest ... more

wolfcrypt/src/sp_int.c@17:a5f916481144, 2020-06-05 (annotated)

Committer:
wolfSSL
Date:
Fri Jun 05 00:11:07 2020 +0000
Revision:
17:a5f916481144
Parent:
16:8e0d178b1d1e 
wolfSSL 4.4.0

Who changed what in which revision?

UserRevisionLine numberNew contents of line
wolfSSL 14:167253f4e170 1 /* sp_int.c
wolfSSL 14:167253f4e170 2 *
wolfSSL 16:8e0d178b1d1e 3 * Copyright (C) 2006-2020 wolfSSL Inc.
wolfSSL 14:167253f4e170 4 *
wolfSSL 14:167253f4e170 5 * This file is part of wolfSSL.
wolfSSL 14:167253f4e170 6 *
wolfSSL 14:167253f4e170 7 * wolfSSL is free software; you can redistribute it and/or modify
wolfSSL 14:167253f4e170 8 * it under the terms of the GNU General Public License as published by
wolfSSL 14:167253f4e170 9 * the Free Software Foundation; either version 2 of the License, or
wolfSSL 14:167253f4e170 10 * (at your option) any later version.
wolfSSL 14:167253f4e170 11 *
wolfSSL 14:167253f4e170 12 * wolfSSL is distributed in the hope that it will be useful,
wolfSSL 14:167253f4e170 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
wolfSSL 14:167253f4e170 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
wolfSSL 14:167253f4e170 15 * GNU General Public License for more details.
wolfSSL 14:167253f4e170 16 *
wolfSSL 14:167253f4e170 17 * You should have received a copy of the GNU General Public License
wolfSSL 14:167253f4e170 18 * along with this program; if not, write to the Free Software
wolfSSL 14:167253f4e170 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
wolfSSL 14:167253f4e170 20 */
wolfSSL 14:167253f4e170 21
wolfSSL 14:167253f4e170 22 /* Implementation by Sean Parkinson. */
wolfSSL 14:167253f4e170 23
wolfSSL 14:167253f4e170 24 #ifdef HAVE_CONFIG_H
wolfSSL 14:167253f4e170 25 #include <config.h>
wolfSSL 14:167253f4e170 26 #endif
wolfSSL 14:167253f4e170 27
wolfSSL 14:167253f4e170 28 #include <wolfssl/wolfcrypt/settings.h>
wolfSSL 14:167253f4e170 29 #include <wolfssl/wolfcrypt/error-crypt.h>
wolfSSL 14:167253f4e170 30 #ifdef NO_INLINE
wolfSSL 14:167253f4e170 31 #include <wolfssl/wolfcrypt/misc.h>
wolfSSL 14:167253f4e170 32 #else
wolfSSL 14:167253f4e170 33 #define WOLFSSL_MISC_INCLUDED
wolfSSL 14:167253f4e170 34 #include <wolfcrypt/src/misc.c>
wolfSSL 14:167253f4e170 35 #endif
wolfSSL 14:167253f4e170 36
wolfSSL 16:8e0d178b1d1e 37 /* SP Build Options:
wolfSSL 16:8e0d178b1d1e 38 * WOLFSSL_HAVE_SP_RSA: Enable SP RSA support
wolfSSL 16:8e0d178b1d1e 39 * WOLFSSL_HAVE_SP_DH: Enable SP DH support
wolfSSL 16:8e0d178b1d1e 40 * WOLFSSL_HAVE_SP_ECC: Enable SP ECC support
wolfSSL 16:8e0d178b1d1e 41 * WOLFSSL_SP_MATH: Use only single precision math and algorithms it supports (no fastmath tfm.c or normal integer.c)
wolfSSL 16:8e0d178b1d1e 42 * WOLFSSL_SP_SMALL: Use smaller version of code and avoid large stack variables
wolfSSL 16:8e0d178b1d1e 43 * WOLFSSL_SP_NO_MALLOC: Always use stack, no heap XMALLOC/XFREE allowed
wolfSSL 16:8e0d178b1d1e 44 * WOLFSSL_SP_NO_3072: Disable RSA/DH 3072-bit support
wolfSSL 16:8e0d178b1d1e 45 * WOLFSSL_SP_NO_2048: Disable RSA/DH 2048-bit support
wolfSSL 16:8e0d178b1d1e 46 * WOLFSSL_SP_4096: Enable RSA/RH 4096-bit support
wolfSSL 16:8e0d178b1d1e 47 * WOLFSSL_SP_384 Enable ECC 384-bit SECP384R1 support
wolfSSL 16:8e0d178b1d1e 48 * WOLFSSL_SP_NO_256 Disable ECC 256-bit SECP256R1 support
wolfSSL 16:8e0d178b1d1e 49 * WOLFSSL_SP_CACHE_RESISTANT Enable cache resistantant code
wolfSSL 16:8e0d178b1d1e 50 * WOLFSSL_SP_ASM Enable assembly speedups (detect platform)
wolfSSL 16:8e0d178b1d1e 51 * WOLFSSL_SP_X86_64_ASM Enable Intel x86 assembly speedups like AVX/AVX2
wolfSSL 16:8e0d178b1d1e 52 * WOLFSSL_SP_ARM32_ASM Enable Aarch32 assembly speedups
wolfSSL 16:8e0d178b1d1e 53 * WOLFSSL_SP_ARM64_ASM Enable Aarch64 assembly speedups
wolfSSL 16:8e0d178b1d1e 54 * WOLFSSL_SP_ARM_CORTEX_M_ASM Enable Cortex-M assembly speedups
wolfSSL 16:8e0d178b1d1e 55 * WOLFSSL_SP_ARM_THUMB_ASM Enable ARM Thumb assembly speedups (used with -mthumb)
wolfSSL 16:8e0d178b1d1e 56 */
wolfSSL 14:167253f4e170 57
wolfSSL 14:167253f4e170 58 #ifdef WOLFSSL_SP_MATH
wolfSSL 14:167253f4e170 59
wolfSSL 14:167253f4e170 60 #include <wolfssl/wolfcrypt/sp_int.h>
wolfSSL 14:167253f4e170 61
wolfSSL 16:8e0d178b1d1e 62 #if defined(WOLFSSL_HAVE_SP_DH) || defined(WOLFSSL_HAVE_SP_RSA)
wolfSSL 16:8e0d178b1d1e 63
wolfSSL 16:8e0d178b1d1e 64 WOLFSSL_LOCAL int sp_ModExp_1024(sp_int* base, sp_int* exp, sp_int* mod,
wolfSSL 16:8e0d178b1d1e 65 sp_int* res);
wolfSSL 16:8e0d178b1d1e 66 WOLFSSL_LOCAL int sp_ModExp_1536(sp_int* base, sp_int* exp, sp_int* mod,
wolfSSL 16:8e0d178b1d1e 67 sp_int* res);
wolfSSL 16:8e0d178b1d1e 68 WOLFSSL_LOCAL int sp_ModExp_2048(sp_int* base, sp_int* exp, sp_int* mod,
wolfSSL 16:8e0d178b1d1e 69 sp_int* res);
wolfSSL 16:8e0d178b1d1e 70 WOLFSSL_LOCAL int sp_ModExp_3072(sp_int* base, sp_int* exp, sp_int* mod,
wolfSSL 16:8e0d178b1d1e 71 sp_int* res);
wolfSSL 16:8e0d178b1d1e 72 WOLFSSL_LOCAL int sp_ModExp_4096(sp_int* base, sp_int* exp, sp_int* mod,
wolfSSL 16:8e0d178b1d1e 73 sp_int* res);
wolfSSL 16:8e0d178b1d1e 74
wolfSSL 16:8e0d178b1d1e 75 #endif
wolfSSL 16:8e0d178b1d1e 76
wolfSSL 16:8e0d178b1d1e 77 int sp_get_digit_count(sp_int *a)
wolfSSL 16:8e0d178b1d1e 78 {
wolfSSL 16:8e0d178b1d1e 79 int ret;
wolfSSL 16:8e0d178b1d1e 80 if (!a)
wolfSSL 16:8e0d178b1d1e 81 ret = 0;
wolfSSL 16:8e0d178b1d1e 82 else
wolfSSL 16:8e0d178b1d1e 83 ret = a->used;
wolfSSL 16:8e0d178b1d1e 84 return ret;
wolfSSL 16:8e0d178b1d1e 85 }
wolfSSL 16:8e0d178b1d1e 86
wolfSSL 14:167253f4e170 87 /* Initialize the big number to be zero.
wolfSSL 14:167253f4e170 88 *
wolfSSL 14:167253f4e170 89 * a SP integer.
wolfSSL 14:167253f4e170 90 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 91 */
wolfSSL 14:167253f4e170 92 int sp_init(sp_int* a)
wolfSSL 14:167253f4e170 93 {
wolfSSL 14:167253f4e170 94 a->used = 0;
wolfSSL 14:167253f4e170 95 a->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 96
wolfSSL 14:167253f4e170 97 return MP_OKAY;
wolfSSL 14:167253f4e170 98 }
wolfSSL 14:167253f4e170 99
wolfSSL 16:8e0d178b1d1e 100 #if !defined(WOLFSSL_RSA_PUBLIC_ONLY) || (!defined(NO_DH) || defined(HAVE_ECC))
wolfSSL 14:167253f4e170 101 /* Initialize up to six big numbers to be zero.
wolfSSL 14:167253f4e170 102 *
wolfSSL 14:167253f4e170 103 * a SP integer.
wolfSSL 14:167253f4e170 104 * b SP integer.
wolfSSL 14:167253f4e170 105 * c SP integer.
wolfSSL 14:167253f4e170 106 * d SP integer.
wolfSSL 14:167253f4e170 107 * e SP integer.
wolfSSL 14:167253f4e170 108 * f SP integer.
wolfSSL 14:167253f4e170 109 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 110 */
wolfSSL 14:167253f4e170 111 int sp_init_multi(sp_int* a, sp_int* b, sp_int* c, sp_int* d, sp_int* e,
wolfSSL 14:167253f4e170 112 sp_int* f)
wolfSSL 14:167253f4e170 113 {
wolfSSL 14:167253f4e170 114 if (a != NULL) {
wolfSSL 14:167253f4e170 115 a->used = 0;
wolfSSL 14:167253f4e170 116 a->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 117 }
wolfSSL 14:167253f4e170 118 if (b != NULL) {
wolfSSL 14:167253f4e170 119 b->used = 0;
wolfSSL 14:167253f4e170 120 b->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 121 }
wolfSSL 14:167253f4e170 122 if (c != NULL) {
wolfSSL 14:167253f4e170 123 c->used = 0;
wolfSSL 14:167253f4e170 124 c->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 125 }
wolfSSL 14:167253f4e170 126 if (d != NULL) {
wolfSSL 14:167253f4e170 127 d->used = 0;
wolfSSL 14:167253f4e170 128 d->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 129 }
wolfSSL 14:167253f4e170 130 if (e != NULL) {
wolfSSL 14:167253f4e170 131 e->used = 0;
wolfSSL 14:167253f4e170 132 e->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 133 }
wolfSSL 14:167253f4e170 134 if (f != NULL) {
wolfSSL 14:167253f4e170 135 f->used = 0;
wolfSSL 14:167253f4e170 136 f->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 137 }
wolfSSL 14:167253f4e170 138
wolfSSL 14:167253f4e170 139 return MP_OKAY;
wolfSSL 14:167253f4e170 140 }
wolfSSL 16:8e0d178b1d1e 141 #endif
wolfSSL 14:167253f4e170 142
wolfSSL 14:167253f4e170 143 /* Clear the data from the big number and set to zero.
wolfSSL 14:167253f4e170 144 *
wolfSSL 14:167253f4e170 145 * a SP integer.
wolfSSL 14:167253f4e170 146 */
wolfSSL 14:167253f4e170 147 void sp_clear(sp_int* a)
wolfSSL 14:167253f4e170 148 {
wolfSSL 16:8e0d178b1d1e 149 if (a != NULL) {
wolfSSL 16:8e0d178b1d1e 150 int i;
wolfSSL 14:167253f4e170 151
wolfSSL 16:8e0d178b1d1e 152 for (i=0; i<a->used; i++)
wolfSSL 16:8e0d178b1d1e 153 a->dp[i] = 0;
wolfSSL 16:8e0d178b1d1e 154 a->used = 0;
wolfSSL 16:8e0d178b1d1e 155 }
wolfSSL 14:167253f4e170 156 }
wolfSSL 14:167253f4e170 157
wolfSSL 14:167253f4e170 158 /* Calculate the number of 8-bit values required to represent the big number.
wolfSSL 14:167253f4e170 159 *
wolfSSL 14:167253f4e170 160 * a SP integer.
wolfSSL 14:167253f4e170 161 * returns the count.
wolfSSL 14:167253f4e170 162 */
wolfSSL 14:167253f4e170 163 int sp_unsigned_bin_size(sp_int* a)
wolfSSL 14:167253f4e170 164 {
wolfSSL 14:167253f4e170 165 int size = sp_count_bits(a);
wolfSSL 14:167253f4e170 166 return (size + 7) / 8;
wolfSSL 14:167253f4e170 167 }
wolfSSL 14:167253f4e170 168
wolfSSL 14:167253f4e170 169 /* Convert a number as an array of bytes in big-endian format to a big number.
wolfSSL 14:167253f4e170 170 *
wolfSSL 14:167253f4e170 171 * a SP integer.
wolfSSL 14:167253f4e170 172 * in Array of bytes.
wolfSSL 14:167253f4e170 173 * inSz Number of data bytes in array.
wolfSSL 16:8e0d178b1d1e 174 * returns BAD_FUNC_ARG when the number is too big to fit in an SP and
wolfSSL 16:8e0d178b1d1e 175 MP_OKAY otherwise.
wolfSSL 14:167253f4e170 176 */
wolfSSL 16:8e0d178b1d1e 177 int sp_read_unsigned_bin(sp_int* a, const byte* in, int inSz)
wolfSSL 14:167253f4e170 178 {
wolfSSL 16:8e0d178b1d1e 179 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 180 int i, j = 0, k;
wolfSSL 14:167253f4e170 181
wolfSSL 16:8e0d178b1d1e 182 if (inSz > SP_INT_DIGITS * (int)sizeof(a->dp[0])) {
wolfSSL 16:8e0d178b1d1e 183 err = MP_VAL;
wolfSSL 14:167253f4e170 184 }
wolfSSL 14:167253f4e170 185
wolfSSL 16:8e0d178b1d1e 186 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 187 for (i = inSz-1; i >= (SP_WORD_SIZE/8); i -= (SP_WORD_SIZE/8), j++) {
wolfSSL 16:8e0d178b1d1e 188 a->dp[j] = (((sp_int_digit)in[i-0]) << (0*8))
wolfSSL 16:8e0d178b1d1e 189 | (((sp_int_digit)in[i-1]) << (1*8))
wolfSSL 16:8e0d178b1d1e 190 | (((sp_int_digit)in[i-2]) << (2*8))
wolfSSL 16:8e0d178b1d1e 191 | (((sp_int_digit)in[i-3]) << (3*8));
wolfSSL 16:8e0d178b1d1e 192 #if SP_WORD_SIZE == 64
wolfSSL 16:8e0d178b1d1e 193 a->dp[j] |= (((sp_int_digit)in[i-4]) << (4*8))
wolfSSL 16:8e0d178b1d1e 194 | (((sp_int_digit)in[i-5]) << (5*8))
wolfSSL 16:8e0d178b1d1e 195 | (((sp_int_digit)in[i-6]) << (6*8))
wolfSSL 16:8e0d178b1d1e 196 | (((sp_int_digit)in[i-7]) << (7*8));
wolfSSL 16:8e0d178b1d1e 197 #endif
wolfSSL 16:8e0d178b1d1e 198 }
wolfSSL 16:8e0d178b1d1e 199 if (i >= 0) {
wolfSSL 16:8e0d178b1d1e 200 a->dp[j] = 0;
wolfSSL 16:8e0d178b1d1e 201 for (k = 0; k <= i; k++) {
wolfSSL 16:8e0d178b1d1e 202 a->dp[j] <<= 8;
wolfSSL 16:8e0d178b1d1e 203 a->dp[j] |= in[k];
wolfSSL 16:8e0d178b1d1e 204 }
wolfSSL 16:8e0d178b1d1e 205 }
wolfSSL 16:8e0d178b1d1e 206 a->used = j + 1;
wolfSSL 16:8e0d178b1d1e 207 }
wolfSSL 14:167253f4e170 208
wolfSSL 16:8e0d178b1d1e 209 sp_clamp(a);
wolfSSL 14:167253f4e170 210
wolfSSL 16:8e0d178b1d1e 211 return err;
wolfSSL 14:167253f4e170 212 }
wolfSSL 14:167253f4e170 213
wolfSSL 16:8e0d178b1d1e 214 #ifdef HAVE_ECC
wolfSSL 14:167253f4e170 215 /* Convert a number as string in big-endian format to a big number.
wolfSSL 14:167253f4e170 216 * Only supports base-16 (hexadecimal).
wolfSSL 14:167253f4e170 217 * Negative values not supported.
wolfSSL 14:167253f4e170 218 *
wolfSSL 14:167253f4e170 219 * a SP integer.
wolfSSL 14:167253f4e170 220 * in NUL terminated string.
wolfSSL 14:167253f4e170 221 * radix Number of values in a digit.
wolfSSL 14:167253f4e170 222 * returns BAD_FUNC_ARG when radix not supported or value is negative, MP_VAL
wolfSSL 14:167253f4e170 223 * when a character is not valid and MP_OKAY otherwise.
wolfSSL 14:167253f4e170 224 */
wolfSSL 14:167253f4e170 225 int sp_read_radix(sp_int* a, const char* in, int radix)
wolfSSL 14:167253f4e170 226 {
wolfSSL 16:8e0d178b1d1e 227 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 228 int i, j = 0, k = 0;
wolfSSL 16:8e0d178b1d1e 229 char ch;
wolfSSL 14:167253f4e170 230
wolfSSL 16:8e0d178b1d1e 231 if ((radix != 16) || (*in == '-')) {
wolfSSL 16:8e0d178b1d1e 232 err = BAD_FUNC_ARG;
wolfSSL 16:8e0d178b1d1e 233 }
wolfSSL 14:167253f4e170 234
wolfSSL 16:8e0d178b1d1e 235 while (*in == '0') {
wolfSSL 16:8e0d178b1d1e 236 in++;
wolfSSL 14:167253f4e170 237 }
wolfSSL 14:167253f4e170 238
wolfSSL 16:8e0d178b1d1e 239 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 240 a->dp[0] = 0;
wolfSSL 16:8e0d178b1d1e 241 for (i = (int)(XSTRLEN(in) - 1); i >= 0; i--) {
wolfSSL 16:8e0d178b1d1e 242 ch = in[i];
wolfSSL 16:8e0d178b1d1e 243 if (ch >= '0' && ch <= '9')
wolfSSL 16:8e0d178b1d1e 244 ch -= '0';
wolfSSL 16:8e0d178b1d1e 245 else if (ch >= 'A' && ch <= 'F')
wolfSSL 16:8e0d178b1d1e 246 ch -= 'A' - 10;
wolfSSL 16:8e0d178b1d1e 247 else if (ch >= 'a' && ch <= 'f')
wolfSSL 16:8e0d178b1d1e 248 ch -= 'a' - 10;
wolfSSL 16:8e0d178b1d1e 249 else {
wolfSSL 16:8e0d178b1d1e 250 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 251 break;
wolfSSL 16:8e0d178b1d1e 252 }
wolfSSL 14:167253f4e170 253
wolfSSL 16:8e0d178b1d1e 254 a->dp[k] |= ((sp_int_digit)ch) << j;
wolfSSL 16:8e0d178b1d1e 255 j += 4;
wolfSSL 16:8e0d178b1d1e 256 if (k >= SP_INT_DIGITS - 1) {
wolfSSL 16:8e0d178b1d1e 257 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 258 break;
wolfSSL 16:8e0d178b1d1e 259 }
wolfSSL 16:8e0d178b1d1e 260 if (j == DIGIT_BIT)
wolfSSL 16:8e0d178b1d1e 261 a->dp[++k] = 0;
wolfSSL 16:8e0d178b1d1e 262 j &= SP_WORD_SIZE - 1;
wolfSSL 16:8e0d178b1d1e 263 }
wolfSSL 14:167253f4e170 264 }
wolfSSL 14:167253f4e170 265
wolfSSL 16:8e0d178b1d1e 266 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 267 a->used = k + 1;
wolfSSL 16:8e0d178b1d1e 268 if (a->dp[k] == 0)
wolfSSL 16:8e0d178b1d1e 269 a->used--;
wolfSSL 14:167253f4e170 270
wolfSSL 16:8e0d178b1d1e 271 for (k++; k < a->size; k++)
wolfSSL 16:8e0d178b1d1e 272 a->dp[k] = 0;
wolfSSL 14:167253f4e170 273
wolfSSL 16:8e0d178b1d1e 274 sp_clamp(a);
wolfSSL 16:8e0d178b1d1e 275 }
wolfSSL 16:8e0d178b1d1e 276
wolfSSL 16:8e0d178b1d1e 277 return err;
wolfSSL 14:167253f4e170 278 }
wolfSSL 16:8e0d178b1d1e 279 #endif
wolfSSL 14:167253f4e170 280
wolfSSL 14:167253f4e170 281 /* Compare two big numbers.
wolfSSL 14:167253f4e170 282 *
wolfSSL 14:167253f4e170 283 * a SP integer.
wolfSSL 14:167253f4e170 284 * b SP integer.
wolfSSL 14:167253f4e170 285 * returns MP_GT if a is greater than b, MP_LT if a is less than b and MP_EQ
wolfSSL 14:167253f4e170 286 * when a equals b.
wolfSSL 14:167253f4e170 287 */
wolfSSL 14:167253f4e170 288 int sp_cmp(sp_int* a, sp_int* b)
wolfSSL 14:167253f4e170 289 {
wolfSSL 16:8e0d178b1d1e 290 int ret = MP_EQ;
wolfSSL 14:167253f4e170 291 int i;
wolfSSL 14:167253f4e170 292
wolfSSL 14:167253f4e170 293 if (a->used > b->used)
wolfSSL 16:8e0d178b1d1e 294 ret = MP_GT;
wolfSSL 14:167253f4e170 295 else if (a->used < b->used)
wolfSSL 16:8e0d178b1d1e 296 ret = MP_LT;
wolfSSL 16:8e0d178b1d1e 297 else {
wolfSSL 16:8e0d178b1d1e 298 for (i = a->used - 1; i >= 0; i--) {
wolfSSL 16:8e0d178b1d1e 299 if (a->dp[i] > b->dp[i]) {
wolfSSL 16:8e0d178b1d1e 300 ret = MP_GT;
wolfSSL 16:8e0d178b1d1e 301 break;
wolfSSL 16:8e0d178b1d1e 302 }
wolfSSL 16:8e0d178b1d1e 303 else if (a->dp[i] < b->dp[i]) {
wolfSSL 16:8e0d178b1d1e 304 ret = MP_LT;
wolfSSL 16:8e0d178b1d1e 305 break;
wolfSSL 16:8e0d178b1d1e 306 }
wolfSSL 16:8e0d178b1d1e 307 }
wolfSSL 14:167253f4e170 308 }
wolfSSL 16:8e0d178b1d1e 309 return ret;
wolfSSL 14:167253f4e170 310 }
wolfSSL 14:167253f4e170 311
wolfSSL 14:167253f4e170 312 /* Count the number of bits in the big number.
wolfSSL 14:167253f4e170 313 *
wolfSSL 14:167253f4e170 314 * a SP integer.
wolfSSL 14:167253f4e170 315 * returns the number of bits.
wolfSSL 14:167253f4e170 316 */
wolfSSL 14:167253f4e170 317 int sp_count_bits(sp_int* a)
wolfSSL 14:167253f4e170 318 {
wolfSSL 14:167253f4e170 319 int r = 0;
wolfSSL 14:167253f4e170 320 sp_int_digit d;
wolfSSL 14:167253f4e170 321
wolfSSL 14:167253f4e170 322 r = a->used - 1;
wolfSSL 14:167253f4e170 323 while (r >= 0 && a->dp[r] == 0)
wolfSSL 14:167253f4e170 324 r--;
wolfSSL 14:167253f4e170 325 if (r < 0)
wolfSSL 14:167253f4e170 326 r = 0;
wolfSSL 14:167253f4e170 327 else {
wolfSSL 14:167253f4e170 328 d = a->dp[r];
wolfSSL 16:8e0d178b1d1e 329 r *= SP_WORD_SIZE;
wolfSSL 16:8e0d178b1d1e 330 if (d >= (1L << (SP_WORD_SIZE / 2))) {
wolfSSL 16:8e0d178b1d1e 331 r += SP_WORD_SIZE;
wolfSSL 16:8e0d178b1d1e 332 while ((d & (1UL << (SP_WORD_SIZE - 1))) == 0) {
wolfSSL 16:8e0d178b1d1e 333 r--;
wolfSSL 16:8e0d178b1d1e 334 d <<= 1;
wolfSSL 16:8e0d178b1d1e 335 }
wolfSSL 16:8e0d178b1d1e 336 }
wolfSSL 16:8e0d178b1d1e 337 else {
wolfSSL 16:8e0d178b1d1e 338 while (d != 0) {
wolfSSL 16:8e0d178b1d1e 339 r++;
wolfSSL 16:8e0d178b1d1e 340 d >>= 1;
wolfSSL 16:8e0d178b1d1e 341 }
wolfSSL 14:167253f4e170 342 }
wolfSSL 14:167253f4e170 343 }
wolfSSL 14:167253f4e170 344
wolfSSL 14:167253f4e170 345 return r;
wolfSSL 14:167253f4e170 346 }
wolfSSL 14:167253f4e170 347
wolfSSL 14:167253f4e170 348 /* Determine if the most significant byte of the encoded big number as the top
wolfSSL 14:167253f4e170 349 * bit set.
wolfSSL 14:167253f4e170 350 *
wolfSSL 14:167253f4e170 351 * a SP integer.
wolfSSL 14:167253f4e170 352 * returns 1 when the top bit is set and 0 otherwise.
wolfSSL 14:167253f4e170 353 */
wolfSSL 14:167253f4e170 354 int sp_leading_bit(sp_int* a)
wolfSSL 14:167253f4e170 355 {
wolfSSL 14:167253f4e170 356 int bit = 0;
wolfSSL 14:167253f4e170 357 sp_int_digit d;
wolfSSL 14:167253f4e170 358
wolfSSL 14:167253f4e170 359 if (a->used > 0) {
wolfSSL 14:167253f4e170 360 d = a->dp[a->used - 1];
wolfSSL 14:167253f4e170 361 while (d > (sp_int_digit)0xff)
wolfSSL 14:167253f4e170 362 d >>= 8;
wolfSSL 14:167253f4e170 363 bit = (int)(d >> 7);
wolfSSL 14:167253f4e170 364 }
wolfSSL 14:167253f4e170 365
wolfSSL 14:167253f4e170 366 return bit;
wolfSSL 14:167253f4e170 367 }
wolfSSL 14:167253f4e170 368
wolfSSL 16:8e0d178b1d1e 369 #if !defined(NO_DH) || defined(HAVE_ECC) || defined(WC_RSA_BLINDING) || \
wolfSSL 16:8e0d178b1d1e 370 !defined(WOLFSSL_RSA_VERIFY_ONLY)
wolfSSL 14:167253f4e170 371 /* Convert the big number to an array of bytes in big-endian format.
wolfSSL 14:167253f4e170 372 * The array must be large enough for encoded number - use mp_unsigned_bin_size
wolfSSL 14:167253f4e170 373 * to calculate the number of bytes required.
wolfSSL 14:167253f4e170 374 *
wolfSSL 16:8e0d178b1d1e 375 * a SP integer.
wolfSSL 16:8e0d178b1d1e 376 * out Array to put encoding into.
wolfSSL 14:167253f4e170 377 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 378 */
wolfSSL 14:167253f4e170 379 int sp_to_unsigned_bin(sp_int* a, byte* out)
wolfSSL 14:167253f4e170 380 {
wolfSSL 14:167253f4e170 381 int i, j, b;
wolfSSL 16:8e0d178b1d1e 382 sp_int_digit d;
wolfSSL 14:167253f4e170 383
wolfSSL 14:167253f4e170 384 j = sp_unsigned_bin_size(a) - 1;
wolfSSL 14:167253f4e170 385 for (i=0; j>=0; i++) {
wolfSSL 16:8e0d178b1d1e 386 d = a->dp[i];
wolfSSL 16:8e0d178b1d1e 387 for (b = 0; b < SP_WORD_SIZE / 8; b++) {
wolfSSL 16:8e0d178b1d1e 388 out[j] = d;
wolfSSL 16:8e0d178b1d1e 389 if (--j < 0) {
wolfSSL 16:8e0d178b1d1e 390 break;
wolfSSL 16:8e0d178b1d1e 391 }
wolfSSL 16:8e0d178b1d1e 392 d >>= 8;
wolfSSL 16:8e0d178b1d1e 393 }
wolfSSL 16:8e0d178b1d1e 394 }
wolfSSL 16:8e0d178b1d1e 395
wolfSSL 16:8e0d178b1d1e 396 return MP_OKAY;
wolfSSL 16:8e0d178b1d1e 397 }
wolfSSL 16:8e0d178b1d1e 398 #endif
wolfSSL 16:8e0d178b1d1e 399
wolfSSL 16:8e0d178b1d1e 400 /* Convert the big number to an array of bytes in big-endian format.
wolfSSL 16:8e0d178b1d1e 401 * The array must be large enough for encoded number - use mp_unsigned_bin_size
wolfSSL 16:8e0d178b1d1e 402 * to calculate the number of bytes required.
wolfSSL 16:8e0d178b1d1e 403 * Front-pads the output array with zeros make number the size of the array.
wolfSSL 16:8e0d178b1d1e 404 *
wolfSSL 16:8e0d178b1d1e 405 * a SP integer.
wolfSSL 16:8e0d178b1d1e 406 * out Array to put encoding into.
wolfSSL 16:8e0d178b1d1e 407 * outSz Size of the array.
wolfSSL 16:8e0d178b1d1e 408 * returns MP_OKAY always.
wolfSSL 16:8e0d178b1d1e 409 */
wolfSSL 16:8e0d178b1d1e 410 int sp_to_unsigned_bin_len(sp_int* a, byte* out, int outSz)
wolfSSL 16:8e0d178b1d1e 411 {
wolfSSL 16:8e0d178b1d1e 412 int i, j, b;
wolfSSL 16:8e0d178b1d1e 413
wolfSSL 16:8e0d178b1d1e 414 j = outSz - 1;
wolfSSL 16:8e0d178b1d1e 415 for (i=0; j>=0; i++) {
wolfSSL 14:167253f4e170 416 for (b = 0; b < SP_WORD_SIZE; b += 8) {
wolfSSL 14:167253f4e170 417 out[j--] = a->dp[i] >> b;
wolfSSL 14:167253f4e170 418 if (j < 0)
wolfSSL 14:167253f4e170 419 break;
wolfSSL 14:167253f4e170 420 }
wolfSSL 14:167253f4e170 421 }
wolfSSL 14:167253f4e170 422
wolfSSL 14:167253f4e170 423 return MP_OKAY;
wolfSSL 14:167253f4e170 424 }
wolfSSL 14:167253f4e170 425
wolfSSL 16:8e0d178b1d1e 426 #if !defined(WOLFSSL_RSA_PUBLIC_ONLY) || (!defined(NO_DH) || defined(HAVE_ECC))
wolfSSL 14:167253f4e170 427 /* Ensure the data in the big number is zeroed.
wolfSSL 14:167253f4e170 428 *
wolfSSL 14:167253f4e170 429 * a SP integer.
wolfSSL 14:167253f4e170 430 */
wolfSSL 14:167253f4e170 431 void sp_forcezero(sp_int* a)
wolfSSL 14:167253f4e170 432 {
wolfSSL 14:167253f4e170 433 ForceZero(a->dp, a->used * sizeof(sp_int_digit));
wolfSSL 14:167253f4e170 434 a->used = 0;
wolfSSL 14:167253f4e170 435 }
wolfSSL 16:8e0d178b1d1e 436 #endif
wolfSSL 14:167253f4e170 437
wolfSSL 16:8e0d178b1d1e 438 #if !defined(WOLFSSL_RSA_VERIFY_ONLY) || (!defined(NO_DH) || defined(HAVE_ECC))
wolfSSL 16:8e0d178b1d1e 439 /* Copy value of big number a into r.
wolfSSL 14:167253f4e170 440 *
wolfSSL 14:167253f4e170 441 * a SP integer.
wolfSSL 16:8e0d178b1d1e 442 * r SP integer.
wolfSSL 14:167253f4e170 443 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 444 */
wolfSSL 16:8e0d178b1d1e 445 int sp_copy(sp_int* a, sp_int* r)
wolfSSL 14:167253f4e170 446 {
wolfSSL 16:8e0d178b1d1e 447 if (a != r) {
wolfSSL 16:8e0d178b1d1e 448 XMEMCPY(r->dp, a->dp, a->used * sizeof(sp_int_digit));
wolfSSL 16:8e0d178b1d1e 449 r->used = a->used;
wolfSSL 14:167253f4e170 450 }
wolfSSL 14:167253f4e170 451 return MP_OKAY;
wolfSSL 14:167253f4e170 452 }
wolfSSL 14:167253f4e170 453
wolfSSL 16:8e0d178b1d1e 454 /* creates "a" then copies b into it */
wolfSSL 16:8e0d178b1d1e 455 int sp_init_copy (sp_int * a, sp_int * b)
wolfSSL 16:8e0d178b1d1e 456 {
wolfSSL 16:8e0d178b1d1e 457 int err;
wolfSSL 16:8e0d178b1d1e 458 if ((err = sp_init(a)) == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 459 if((err = sp_copy (b, a)) != MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 460 sp_clear(a);
wolfSSL 16:8e0d178b1d1e 461 }
wolfSSL 16:8e0d178b1d1e 462 }
wolfSSL 16:8e0d178b1d1e 463 return err;
wolfSSL 16:8e0d178b1d1e 464 }
wolfSSL 16:8e0d178b1d1e 465 #endif
wolfSSL 16:8e0d178b1d1e 466
wolfSSL 14:167253f4e170 467 /* Set the big number to be the value of the digit.
wolfSSL 14:167253f4e170 468 *
wolfSSL 14:167253f4e170 469 * a SP integer.
wolfSSL 14:167253f4e170 470 * d Digit to be set.
wolfSSL 14:167253f4e170 471 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 472 */
wolfSSL 14:167253f4e170 473 int sp_set(sp_int* a, sp_int_digit d)
wolfSSL 14:167253f4e170 474 {
wolfSSL 16:8e0d178b1d1e 475 if (d == 0) {
wolfSSL 16:8e0d178b1d1e 476 a->dp[0] = d;
wolfSSL 16:8e0d178b1d1e 477 a->used = 0;
wolfSSL 16:8e0d178b1d1e 478 }
wolfSSL 16:8e0d178b1d1e 479 else {
wolfSSL 16:8e0d178b1d1e 480 a->dp[0] = d;
wolfSSL 16:8e0d178b1d1e 481 a->used = 1;
wolfSSL 16:8e0d178b1d1e 482 }
wolfSSL 14:167253f4e170 483 return MP_OKAY;
wolfSSL 14:167253f4e170 484 }
wolfSSL 14:167253f4e170 485
wolfSSL 14:167253f4e170 486 /* Recalculate the number of digits used.
wolfSSL 14:167253f4e170 487 *
wolfSSL 14:167253f4e170 488 * a SP integer.
wolfSSL 14:167253f4e170 489 */
wolfSSL 14:167253f4e170 490 void sp_clamp(sp_int* a)
wolfSSL 14:167253f4e170 491 {
wolfSSL 14:167253f4e170 492 int i;
wolfSSL 14:167253f4e170 493
wolfSSL 14:167253f4e170 494 for (i = a->used - 1; i >= 0 && a->dp[i] == 0; i--) {
wolfSSL 14:167253f4e170 495 }
wolfSSL 14:167253f4e170 496 a->used = i + 1;
wolfSSL 14:167253f4e170 497 }
wolfSSL 14:167253f4e170 498
wolfSSL 16:8e0d178b1d1e 499 #if !defined(WOLFSSL_RSA_VERIFY_ONLY) || (!defined(NO_DH) || defined(HAVE_ECC))
wolfSSL 14:167253f4e170 500 /* Grow big number to be able to hold l digits.
wolfSSL 14:167253f4e170 501 * This function does nothing as the number of digits is fixed.
wolfSSL 14:167253f4e170 502 *
wolfSSL 14:167253f4e170 503 * a SP integer.
wolfSSL 14:167253f4e170 504 * l Number of digits.
wolfSSL 16:8e0d178b1d1e 505 * returns MP_MEM if the number of digits requested is more than available and
wolfSSL 14:167253f4e170 506 * MP_OKAY otherwise.
wolfSSL 14:167253f4e170 507 */
wolfSSL 14:167253f4e170 508 int sp_grow(sp_int* a, int l)
wolfSSL 14:167253f4e170 509 {
wolfSSL 16:8e0d178b1d1e 510 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 511
wolfSSL 14:167253f4e170 512 if (l > a->size)
wolfSSL 16:8e0d178b1d1e 513 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 514
wolfSSL 16:8e0d178b1d1e 515 return err;
wolfSSL 14:167253f4e170 516 }
wolfSSL 14:167253f4e170 517
wolfSSL 14:167253f4e170 518 /* Sub a one digit number from the big number.
wolfSSL 14:167253f4e170 519 *
wolfSSL 14:167253f4e170 520 * a SP integer.
wolfSSL 14:167253f4e170 521 * d Digit to subtract.
wolfSSL 14:167253f4e170 522 * r SP integer - result.
wolfSSL 14:167253f4e170 523 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 524 */
wolfSSL 14:167253f4e170 525 int sp_sub_d(sp_int* a, sp_int_digit d, sp_int* r)
wolfSSL 14:167253f4e170 526 {
wolfSSL 14:167253f4e170 527 int i = 0;
wolfSSL 16:8e0d178b1d1e 528 sp_int_digit t;
wolfSSL 14:167253f4e170 529
wolfSSL 14:167253f4e170 530 r->used = a->used;
wolfSSL 16:8e0d178b1d1e 531 t = a->dp[0] - d;
wolfSSL 16:8e0d178b1d1e 532 if (t > a->dp[0]) {
wolfSSL 16:8e0d178b1d1e 533 for (++i; i < a->used; i++) {
wolfSSL 14:167253f4e170 534 r->dp[i] = a->dp[i] - 1;
wolfSSL 14:167253f4e170 535 if (r->dp[i] != (sp_int_digit)-1)
wolfSSL 14:167253f4e170 536 break;
wolfSSL 14:167253f4e170 537 }
wolfSSL 14:167253f4e170 538 }
wolfSSL 16:8e0d178b1d1e 539 r->dp[0] = t;
wolfSSL 16:8e0d178b1d1e 540 if (r != a) {
wolfSSL 16:8e0d178b1d1e 541 for (++i; i < a->used; i++)
wolfSSL 16:8e0d178b1d1e 542 r->dp[i] = a->dp[i];
wolfSSL 16:8e0d178b1d1e 543 }
wolfSSL 16:8e0d178b1d1e 544 sp_clamp(r);
wolfSSL 14:167253f4e170 545
wolfSSL 14:167253f4e170 546 return MP_OKAY;
wolfSSL 14:167253f4e170 547 }
wolfSSL 16:8e0d178b1d1e 548 #endif
wolfSSL 14:167253f4e170 549
wolfSSL 14:167253f4e170 550 /* Compare a one digit number with a big number.
wolfSSL 14:167253f4e170 551 *
wolfSSL 14:167253f4e170 552 * a SP integer.
wolfSSL 14:167253f4e170 553 * d Digit to compare with.
wolfSSL 14:167253f4e170 554 * returns MP_GT if a is greater than d, MP_LT if a is less than d and MP_EQ
wolfSSL 14:167253f4e170 555 * when a equals d.
wolfSSL 14:167253f4e170 556 */
wolfSSL 14:167253f4e170 557 int sp_cmp_d(sp_int *a, sp_int_digit d)
wolfSSL 14:167253f4e170 558 {
wolfSSL 16:8e0d178b1d1e 559 int ret = MP_EQ;
wolfSSL 16:8e0d178b1d1e 560
wolfSSL 14:167253f4e170 561 /* special case for zero*/
wolfSSL 14:167253f4e170 562 if (a->used == 0) {
wolfSSL 14:167253f4e170 563 if (d == 0)
wolfSSL 16:8e0d178b1d1e 564 ret = MP_EQ;
wolfSSL 14:167253f4e170 565 else
wolfSSL 16:8e0d178b1d1e 566 ret = MP_LT;
wolfSSL 14:167253f4e170 567 }
wolfSSL 14:167253f4e170 568 else if (a->used > 1)
wolfSSL 16:8e0d178b1d1e 569 ret = MP_GT;
wolfSSL 16:8e0d178b1d1e 570 else {
wolfSSL 16:8e0d178b1d1e 571 /* compare the only digit of a to d */
wolfSSL 16:8e0d178b1d1e 572 if (a->dp[0] > d)
wolfSSL 16:8e0d178b1d1e 573 ret = MP_GT;
wolfSSL 16:8e0d178b1d1e 574 else if (a->dp[0] < d)
wolfSSL 16:8e0d178b1d1e 575 ret = MP_LT;
wolfSSL 16:8e0d178b1d1e 576 }
wolfSSL 14:167253f4e170 577
wolfSSL 16:8e0d178b1d1e 578 return ret;
wolfSSL 14:167253f4e170 579 }
wolfSSL 14:167253f4e170 580
wolfSSL 16:8e0d178b1d1e 581 #if !defined(NO_DH) || defined(HAVE_ECC) || !defined(WOLFSSL_RSA_VERIFY_ONLY)
wolfSSL 14:167253f4e170 582 /* Left shift the number by number of bits.
wolfSSL 14:167253f4e170 583 * Bits may be larger than the word size.
wolfSSL 14:167253f4e170 584 *
wolfSSL 14:167253f4e170 585 * a SP integer.
wolfSSL 14:167253f4e170 586 * n Number of bits to shift.
wolfSSL 14:167253f4e170 587 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 588 */
wolfSSL 14:167253f4e170 589 static int sp_lshb(sp_int* a, int n)
wolfSSL 14:167253f4e170 590 {
wolfSSL 14:167253f4e170 591 int i;
wolfSSL 14:167253f4e170 592
wolfSSL 14:167253f4e170 593 if (n >= SP_WORD_SIZE) {
wolfSSL 14:167253f4e170 594 sp_lshd(a, n / SP_WORD_SIZE);
wolfSSL 14:167253f4e170 595 n %= SP_WORD_SIZE;
wolfSSL 14:167253f4e170 596 }
wolfSSL 14:167253f4e170 597
wolfSSL 16:8e0d178b1d1e 598 if (n != 0) {
wolfSSL 16:8e0d178b1d1e 599 a->dp[a->used] = 0;
wolfSSL 16:8e0d178b1d1e 600 for (i = a->used - 1; i >= 0; i--) {
wolfSSL 16:8e0d178b1d1e 601 a->dp[i+1] |= a->dp[i] >> (SP_WORD_SIZE - n);
wolfSSL 16:8e0d178b1d1e 602 a->dp[i] = a->dp[i] << n;
wolfSSL 16:8e0d178b1d1e 603 }
wolfSSL 16:8e0d178b1d1e 604 if (a->dp[a->used] != 0)
wolfSSL 16:8e0d178b1d1e 605 a->used++;
wolfSSL 14:167253f4e170 606 }
wolfSSL 14:167253f4e170 607
wolfSSL 14:167253f4e170 608 return MP_OKAY;
wolfSSL 14:167253f4e170 609 }
wolfSSL 14:167253f4e170 610
wolfSSL 14:167253f4e170 611 /* Subtract two large numbers into result: r = a - b
wolfSSL 14:167253f4e170 612 * a must be greater than b.
wolfSSL 14:167253f4e170 613 *
wolfSSL 14:167253f4e170 614 * a SP integer.
wolfSSL 14:167253f4e170 615 * b SP integer.
wolfSSL 14:167253f4e170 616 * r SP integer.
wolfSSL 14:167253f4e170 617 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 618 */
wolfSSL 16:8e0d178b1d1e 619 int sp_sub(sp_int* a, sp_int* b, sp_int* r)
wolfSSL 14:167253f4e170 620 {
wolfSSL 14:167253f4e170 621 int i;
wolfSSL 14:167253f4e170 622 sp_int_digit c = 0;
wolfSSL 14:167253f4e170 623 sp_int_digit t;
wolfSSL 14:167253f4e170 624
wolfSSL 14:167253f4e170 625 for (i = 0; i < a->used && i < b->used; i++) {
wolfSSL 14:167253f4e170 626 t = a->dp[i] - b->dp[i] - c;
wolfSSL 14:167253f4e170 627 if (c == 0)
wolfSSL 14:167253f4e170 628 c = t > a->dp[i];
wolfSSL 14:167253f4e170 629 else
wolfSSL 14:167253f4e170 630 c = t >= a->dp[i];
wolfSSL 14:167253f4e170 631 r->dp[i] = t;
wolfSSL 14:167253f4e170 632 }
wolfSSL 14:167253f4e170 633 for (; i < a->used; i++) {
wolfSSL 14:167253f4e170 634 r->dp[i] = a->dp[i] - c;
wolfSSL 16:8e0d178b1d1e 635 c &= (r->dp[i] == (sp_int_digit)-1);
wolfSSL 14:167253f4e170 636 }
wolfSSL 14:167253f4e170 637 r->used = i;
wolfSSL 14:167253f4e170 638 sp_clamp(r);
wolfSSL 14:167253f4e170 639
wolfSSL 14:167253f4e170 640 return MP_OKAY;
wolfSSL 14:167253f4e170 641 }
wolfSSL 14:167253f4e170 642
wolfSSL 16:8e0d178b1d1e 643 /* Shift a right by n bits into r: r = a >> n
wolfSSL 16:8e0d178b1d1e 644 *
wolfSSL 16:8e0d178b1d1e 645 * a SP integer operand.
wolfSSL 16:8e0d178b1d1e 646 * n Number of bits to shift.
wolfSSL 16:8e0d178b1d1e 647 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 648 */
wolfSSL 16:8e0d178b1d1e 649 void sp_rshb(sp_int* a, int n, sp_int* r)
wolfSSL 16:8e0d178b1d1e 650 {
wolfSSL 16:8e0d178b1d1e 651 int i;
wolfSSL 16:8e0d178b1d1e 652 int j;
wolfSSL 16:8e0d178b1d1e 653
wolfSSL 16:8e0d178b1d1e 654 for (i = n / SP_WORD_SIZE, j = 0; i < a->used-1; i++, j++)
wolfSSL 16:8e0d178b1d1e 655 r->dp[i] = (a->dp[j] >> n) | (a->dp[j+1] << (SP_WORD_SIZE - n));
wolfSSL 16:8e0d178b1d1e 656 r->dp[i] = a->dp[j] >> n;
wolfSSL 16:8e0d178b1d1e 657 r->used = j + 1;
wolfSSL 16:8e0d178b1d1e 658 sp_clamp(r);
wolfSSL 16:8e0d178b1d1e 659 }
wolfSSL 16:8e0d178b1d1e 660
wolfSSL 16:8e0d178b1d1e 661 /* Multiply a by digit n and put result into r shifting up o digits.
wolfSSL 16:8e0d178b1d1e 662 * r = (a * n) << (o * SP_WORD_SIZE)
wolfSSL 16:8e0d178b1d1e 663 *
wolfSSL 16:8e0d178b1d1e 664 * a SP integer to be multiplied.
wolfSSL 16:8e0d178b1d1e 665 * n Number to multiply by.
wolfSSL 16:8e0d178b1d1e 666 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 667 * o Number of digits to move result up by.
wolfSSL 16:8e0d178b1d1e 668 */
wolfSSL 16:8e0d178b1d1e 669 static void _sp_mul_d(sp_int* a, sp_int_digit n, sp_int* r, int o)
wolfSSL 16:8e0d178b1d1e 670 {
wolfSSL 16:8e0d178b1d1e 671 int i;
wolfSSL 16:8e0d178b1d1e 672 sp_int_word t = 0;
wolfSSL 16:8e0d178b1d1e 673
wolfSSL 16:8e0d178b1d1e 674 for (i = 0; i < o; i++)
wolfSSL 16:8e0d178b1d1e 675 r->dp[i] = 0;
wolfSSL 16:8e0d178b1d1e 676
wolfSSL 16:8e0d178b1d1e 677 for (i = 0; i < a->used; i++) {
wolfSSL 16:8e0d178b1d1e 678 t += (sp_int_word)n * a->dp[i];
wolfSSL 16:8e0d178b1d1e 679 r->dp[i + o] = (sp_int_digit)t;
wolfSSL 16:8e0d178b1d1e 680 t >>= SP_WORD_SIZE;
wolfSSL 16:8e0d178b1d1e 681 }
wolfSSL 16:8e0d178b1d1e 682
wolfSSL 16:8e0d178b1d1e 683 r->dp[i+o] = (sp_int_digit)t;
wolfSSL 16:8e0d178b1d1e 684 r->used = i+o+1;
wolfSSL 16:8e0d178b1d1e 685 sp_clamp(r);
wolfSSL 16:8e0d178b1d1e 686 }
wolfSSL 16:8e0d178b1d1e 687
wolfSSL 16:8e0d178b1d1e 688 /* Divide a by d and return the quotient in r and the remainder in rem.
wolfSSL 16:8e0d178b1d1e 689 * r = a / d; rem = a % d
wolfSSL 16:8e0d178b1d1e 690 *
wolfSSL 16:8e0d178b1d1e 691 * a SP integer to be divided.
wolfSSL 16:8e0d178b1d1e 692 * d SP integer to divide by.
wolfSSL 16:8e0d178b1d1e 693 * r SP integer of quotient.
wolfSSL 16:8e0d178b1d1e 694 * rem SP integer of remainder.
wolfSSL 16:8e0d178b1d1e 695 * returns MP_VAL when d is 0, MP_MEM when dynamic memory allocation fails and
wolfSSL 16:8e0d178b1d1e 696 * MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 697 */
wolfSSL 16:8e0d178b1d1e 698 static int sp_div(sp_int* a, sp_int* d, sp_int* r, sp_int* rem)
wolfSSL 16:8e0d178b1d1e 699 {
wolfSSL 16:8e0d178b1d1e 700 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 701 int ret;
wolfSSL 16:8e0d178b1d1e 702 int done = 0;
wolfSSL 16:8e0d178b1d1e 703 int i;
wolfSSL 16:8e0d178b1d1e 704 int s;
wolfSSL 16:8e0d178b1d1e 705 #ifndef WOLFSSL_SP_DIV_32
wolfSSL 16:8e0d178b1d1e 706 sp_int_word w = 0;
wolfSSL 16:8e0d178b1d1e 707 #endif
wolfSSL 16:8e0d178b1d1e 708 sp_int_digit dt;
wolfSSL 16:8e0d178b1d1e 709 sp_int_digit t;
wolfSSL 16:8e0d178b1d1e 710 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 711 sp_int* sa = NULL;
wolfSSL 16:8e0d178b1d1e 712 sp_int* sd;
wolfSSL 16:8e0d178b1d1e 713 sp_int* tr;
wolfSSL 16:8e0d178b1d1e 714 sp_int* trial;
wolfSSL 16:8e0d178b1d1e 715 #else
wolfSSL 16:8e0d178b1d1e 716 sp_int sa[1];
wolfSSL 16:8e0d178b1d1e 717 sp_int sd[1];
wolfSSL 16:8e0d178b1d1e 718 sp_int tr[1];
wolfSSL 16:8e0d178b1d1e 719 sp_int trial[1];
wolfSSL 16:8e0d178b1d1e 720 #endif
wolfSSL 16:8e0d178b1d1e 721
wolfSSL 16:8e0d178b1d1e 722 if (sp_iszero(d))
wolfSSL 16:8e0d178b1d1e 723 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 724
wolfSSL 16:8e0d178b1d1e 725 ret = sp_cmp(a, d);
wolfSSL 16:8e0d178b1d1e 726 if (ret == MP_LT) {
wolfSSL 16:8e0d178b1d1e 727 if (rem != NULL) {
wolfSSL 16:8e0d178b1d1e 728 sp_copy(a, rem);
wolfSSL 16:8e0d178b1d1e 729 }
wolfSSL 16:8e0d178b1d1e 730 if (r != NULL) {
wolfSSL 16:8e0d178b1d1e 731 sp_set(r, 0);
wolfSSL 16:8e0d178b1d1e 732 }
wolfSSL 16:8e0d178b1d1e 733 done = 1;
wolfSSL 16:8e0d178b1d1e 734 }
wolfSSL 16:8e0d178b1d1e 735 else if (ret == MP_EQ) {
wolfSSL 16:8e0d178b1d1e 736 if (rem != NULL) {
wolfSSL 16:8e0d178b1d1e 737 sp_set(rem, 0);
wolfSSL 16:8e0d178b1d1e 738 }
wolfSSL 16:8e0d178b1d1e 739 if (r != NULL) {
wolfSSL 16:8e0d178b1d1e 740 sp_set(r, 1);
wolfSSL 16:8e0d178b1d1e 741 }
wolfSSL 16:8e0d178b1d1e 742 done = 1;
wolfSSL 16:8e0d178b1d1e 743 }
wolfSSL 16:8e0d178b1d1e 744 else if (sp_count_bits(a) == sp_count_bits(d)) {
wolfSSL 16:8e0d178b1d1e 745 /* a is greater than d but same bit length */
wolfSSL 16:8e0d178b1d1e 746 if (rem != NULL) {
wolfSSL 16:8e0d178b1d1e 747 sp_sub(a, d, rem);
wolfSSL 16:8e0d178b1d1e 748 }
wolfSSL 16:8e0d178b1d1e 749 if (r != NULL) {
wolfSSL 16:8e0d178b1d1e 750 sp_set(r, 1);
wolfSSL 16:8e0d178b1d1e 751 }
wolfSSL 16:8e0d178b1d1e 752 done = 1;
wolfSSL 16:8e0d178b1d1e 753 }
wolfSSL 16:8e0d178b1d1e 754
wolfSSL 16:8e0d178b1d1e 755 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 756 if (!done && err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 757 sa = (sp_int*)XMALLOC(sizeof(sp_int) * 4, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 758 if (sa == NULL) {
wolfSSL 16:8e0d178b1d1e 759 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 760 }
wolfSSL 16:8e0d178b1d1e 761 }
wolfSSL 16:8e0d178b1d1e 762 #endif
wolfSSL 16:8e0d178b1d1e 763
wolfSSL 16:8e0d178b1d1e 764 if (!done && err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 765 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 766 sd = &sa[1];
wolfSSL 16:8e0d178b1d1e 767 tr = &sa[2];
wolfSSL 16:8e0d178b1d1e 768 trial = &sa[3];
wolfSSL 16:8e0d178b1d1e 769 #endif
wolfSSL 16:8e0d178b1d1e 770
wolfSSL 16:8e0d178b1d1e 771 sp_init(sa);
wolfSSL 16:8e0d178b1d1e 772 sp_init(sd);
wolfSSL 16:8e0d178b1d1e 773 sp_init(tr);
wolfSSL 16:8e0d178b1d1e 774 sp_init(trial);
wolfSSL 16:8e0d178b1d1e 775
wolfSSL 16:8e0d178b1d1e 776 s = sp_count_bits(d);
wolfSSL 16:8e0d178b1d1e 777 s = SP_WORD_SIZE - (s % SP_WORD_SIZE);
wolfSSL 16:8e0d178b1d1e 778 sp_copy(a, sa);
wolfSSL 16:8e0d178b1d1e 779 if (s != SP_WORD_SIZE) {
wolfSSL 16:8e0d178b1d1e 780 sp_lshb(sa, s);
wolfSSL 16:8e0d178b1d1e 781 sp_copy(d, sd);
wolfSSL 16:8e0d178b1d1e 782 sp_lshb(sd, s);
wolfSSL 16:8e0d178b1d1e 783 d = sd;
wolfSSL 16:8e0d178b1d1e 784 }
wolfSSL 16:8e0d178b1d1e 785
wolfSSL 16:8e0d178b1d1e 786 tr->used = sa->used - d->used + 1;
wolfSSL 16:8e0d178b1d1e 787 sp_clear(tr);
wolfSSL 16:8e0d178b1d1e 788 tr->used = sa->used - d->used + 1;
wolfSSL 16:8e0d178b1d1e 789 dt = d->dp[d->used-1];
wolfSSL 16:8e0d178b1d1e 790 #ifndef WOLFSSL_SP_DIV_32
wolfSSL 16:8e0d178b1d1e 791 for (i = sa->used - 1; i >= d->used; ) {
wolfSSL 16:8e0d178b1d1e 792 if (sa->dp[i] > dt) {
wolfSSL 16:8e0d178b1d1e 793 t = (sp_int_digit)-1;
wolfSSL 16:8e0d178b1d1e 794 }
wolfSSL 16:8e0d178b1d1e 795 else {
wolfSSL 16:8e0d178b1d1e 796 w = ((sp_int_word)sa->dp[i] << SP_WORD_SIZE) | sa->dp[i-1];
wolfSSL 16:8e0d178b1d1e 797 w /= dt;
wolfSSL 16:8e0d178b1d1e 798 if (w > (sp_int_digit)-1) {
wolfSSL 16:8e0d178b1d1e 799 t = (sp_int_digit)-1;
wolfSSL 16:8e0d178b1d1e 800 }
wolfSSL 16:8e0d178b1d1e 801 else {
wolfSSL 16:8e0d178b1d1e 802 t = (sp_int_digit)w;
wolfSSL 16:8e0d178b1d1e 803 }
wolfSSL 16:8e0d178b1d1e 804 }
wolfSSL 16:8e0d178b1d1e 805
wolfSSL 16:8e0d178b1d1e 806 if (t > 0) {
wolfSSL 16:8e0d178b1d1e 807 _sp_mul_d(d, t, trial, i - d->used);
wolfSSL 16:8e0d178b1d1e 808 while (sp_cmp(trial, sa) == MP_GT) {
wolfSSL 16:8e0d178b1d1e 809 t--;
wolfSSL 16:8e0d178b1d1e 810 _sp_mul_d(d, t, trial, i - d->used);
wolfSSL 16:8e0d178b1d1e 811 }
wolfSSL 16:8e0d178b1d1e 812 sp_sub(sa, trial, sa);
wolfSSL 16:8e0d178b1d1e 813 tr->dp[i - d->used] += t;
wolfSSL 16:8e0d178b1d1e 814 if (tr->dp[i - d->used] < t)
wolfSSL 16:8e0d178b1d1e 815 tr->dp[i + 1 - d->used]++;
wolfSSL 16:8e0d178b1d1e 816 }
wolfSSL 16:8e0d178b1d1e 817 i = sa->used - 1;
wolfSSL 16:8e0d178b1d1e 818 }
wolfSSL 16:8e0d178b1d1e 819 #else
wolfSSL 16:8e0d178b1d1e 820 {
wolfSSL 16:8e0d178b1d1e 821 sp_int_digit div = (dt >> (SP_WORD_SIZE / 2)) + 1;
wolfSSL 16:8e0d178b1d1e 822 for (i = sa->used - 1; i >= d->used; ) {
wolfSSL 16:8e0d178b1d1e 823 t = sa->dp[i] / div;
wolfSSL 16:8e0d178b1d1e 824 if ((t > 0) && (t << (SP_WORD_SIZE / 2) == 0))
wolfSSL 16:8e0d178b1d1e 825 t = (sp_int_digit)-1;
wolfSSL 16:8e0d178b1d1e 826 t <<= SP_WORD_SIZE / 2;
wolfSSL 16:8e0d178b1d1e 827 if (t == 0) {
wolfSSL 16:8e0d178b1d1e 828 t = sa->dp[i] << (SP_WORD_SIZE / 2);
wolfSSL 16:8e0d178b1d1e 829 t += sa->dp[i-1] >> (SP_WORD_SIZE / 2);
wolfSSL 16:8e0d178b1d1e 830 t /= div;
wolfSSL 16:8e0d178b1d1e 831 }
wolfSSL 16:8e0d178b1d1e 832
wolfSSL 16:8e0d178b1d1e 833 if (t > 0) {
wolfSSL 16:8e0d178b1d1e 834 _sp_mul_d(d, t, trial, i - d->used);
wolfSSL 16:8e0d178b1d1e 835 while (sp_cmp(trial, sa) == MP_GT) {
wolfSSL 16:8e0d178b1d1e 836 t--;
wolfSSL 16:8e0d178b1d1e 837 _sp_mul_d(d, t, trial, i - d->used);
wolfSSL 16:8e0d178b1d1e 838 }
wolfSSL 16:8e0d178b1d1e 839 sp_sub(sa, trial, sa);
wolfSSL 16:8e0d178b1d1e 840 tr->dp[i - d->used] += t;
wolfSSL 16:8e0d178b1d1e 841 if (tr->dp[i - d->used] < t)
wolfSSL 16:8e0d178b1d1e 842 tr->dp[i + 1 - d->used]++;
wolfSSL 16:8e0d178b1d1e 843 }
wolfSSL 16:8e0d178b1d1e 844 i = sa->used - 1;
wolfSSL 16:8e0d178b1d1e 845 }
wolfSSL 16:8e0d178b1d1e 846
wolfSSL 16:8e0d178b1d1e 847 while (sp_cmp(sa, d) != MP_LT) {
wolfSSL 16:8e0d178b1d1e 848 sp_sub(sa, d, sa);
wolfSSL 16:8e0d178b1d1e 849 sp_add_d(tr, 1, tr);
wolfSSL 16:8e0d178b1d1e 850 }
wolfSSL 16:8e0d178b1d1e 851 }
wolfSSL 16:8e0d178b1d1e 852 #endif
wolfSSL 16:8e0d178b1d1e 853
wolfSSL 16:8e0d178b1d1e 854 sp_clamp(tr);
wolfSSL 16:8e0d178b1d1e 855
wolfSSL 16:8e0d178b1d1e 856 if (rem != NULL) {
wolfSSL 16:8e0d178b1d1e 857 if (s != SP_WORD_SIZE)
wolfSSL 16:8e0d178b1d1e 858 sp_rshb(sa, s, sa);
wolfSSL 16:8e0d178b1d1e 859 sp_copy(sa, rem);
wolfSSL 16:8e0d178b1d1e 860 }
wolfSSL 16:8e0d178b1d1e 861 if (r != NULL)
wolfSSL 16:8e0d178b1d1e 862 sp_copy(tr, r);
wolfSSL 16:8e0d178b1d1e 863 }
wolfSSL 16:8e0d178b1d1e 864
wolfSSL 16:8e0d178b1d1e 865 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 866 if (sa != NULL)
wolfSSL 16:8e0d178b1d1e 867 XFREE(sa, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 868 #endif
wolfSSL 16:8e0d178b1d1e 869
wolfSSL 16:8e0d178b1d1e 870 return err;
wolfSSL 16:8e0d178b1d1e 871 }
wolfSSL 16:8e0d178b1d1e 872
wolfSSL 16:8e0d178b1d1e 873
wolfSSL 16:8e0d178b1d1e 874 #ifndef FREESCALE_LTC_TFM
wolfSSL 16:8e0d178b1d1e 875 /* Calculate the remainder of dividing a by m: r = a mod m.
wolfSSL 14:167253f4e170 876 *
wolfSSL 14:167253f4e170 877 * a SP integer.
wolfSSL 14:167253f4e170 878 * m SP integer.
wolfSSL 14:167253f4e170 879 * r SP integer.
wolfSSL 16:8e0d178b1d1e 880 * returns MP_VAL when m is 0 and MP_OKAY otherwise.
wolfSSL 14:167253f4e170 881 */
wolfSSL 14:167253f4e170 882 int sp_mod(sp_int* a, sp_int* m, sp_int* r)
wolfSSL 14:167253f4e170 883 {
wolfSSL 16:8e0d178b1d1e 884 return sp_div(a, m, NULL, r);
wolfSSL 16:8e0d178b1d1e 885 }
wolfSSL 16:8e0d178b1d1e 886 #endif
wolfSSL 16:8e0d178b1d1e 887 #endif
wolfSSL 14:167253f4e170 888
wolfSSL 14:167253f4e170 889 /* Clear all data in the big number and sets value to zero.
wolfSSL 14:167253f4e170 890 *
wolfSSL 14:167253f4e170 891 * a SP integer.
wolfSSL 14:167253f4e170 892 */
wolfSSL 14:167253f4e170 893 void sp_zero(sp_int* a)
wolfSSL 14:167253f4e170 894 {
wolfSSL 16:8e0d178b1d1e 895 XMEMSET(a->dp, 0, a->size * sizeof(*a->dp));
wolfSSL 14:167253f4e170 896 a->used = 0;
wolfSSL 14:167253f4e170 897 }
wolfSSL 14:167253f4e170 898
wolfSSL 14:167253f4e170 899 /* Add a one digit number to the big number.
wolfSSL 14:167253f4e170 900 *
wolfSSL 14:167253f4e170 901 * a SP integer.
wolfSSL 14:167253f4e170 902 * d Digit to add.
wolfSSL 14:167253f4e170 903 * r SP integer - result.
wolfSSL 14:167253f4e170 904 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 905 */
wolfSSL 14:167253f4e170 906 int sp_add_d(sp_int* a, sp_int_digit d, sp_int* r)
wolfSSL 14:167253f4e170 907 {
wolfSSL 14:167253f4e170 908 int i = 0;
wolfSSL 14:167253f4e170 909
wolfSSL 14:167253f4e170 910 r->used = a->used;
wolfSSL 16:8e0d178b1d1e 911 if (a->used == 0) {
wolfSSL 16:8e0d178b1d1e 912 r->used = 1;
wolfSSL 16:8e0d178b1d1e 913 }
wolfSSL 14:167253f4e170 914 r->dp[0] = a->dp[0] + d;
wolfSSL 14:167253f4e170 915 if (r->dp[i] < a->dp[i]) {
wolfSSL 14:167253f4e170 916 for (; i < a->used; i++) {
wolfSSL 14:167253f4e170 917 r->dp[i] = a->dp[i] + 1;
wolfSSL 14:167253f4e170 918 if (r->dp[i] != 0)
wolfSSL 14:167253f4e170 919 break;
wolfSSL 14:167253f4e170 920 }
wolfSSL 14:167253f4e170 921
wolfSSL 14:167253f4e170 922 if (i == a->used) {
wolfSSL 14:167253f4e170 923 r->used++;
wolfSSL 14:167253f4e170 924 r->dp[i] = 1;
wolfSSL 14:167253f4e170 925 }
wolfSSL 14:167253f4e170 926 }
wolfSSL 14:167253f4e170 927 for (; i < a->used; i++)
wolfSSL 14:167253f4e170 928 r->dp[i] = a->dp[i];
wolfSSL 14:167253f4e170 929
wolfSSL 14:167253f4e170 930 return MP_OKAY;
wolfSSL 14:167253f4e170 931 }
wolfSSL 14:167253f4e170 932
wolfSSL 16:8e0d178b1d1e 933 #if !defined(NO_DH) || defined(HAVE_ECC) || defined(WC_RSA_BLINDING) || \
wolfSSL 16:8e0d178b1d1e 934 !defined(WOLFSSL_RSA_VERIFY_ONLY)
wolfSSL 14:167253f4e170 935 /* Left shift the big number by a number of digits.
wolfSSL 14:167253f4e170 936 * WIll chop off digits overflowing maximum size.
wolfSSL 14:167253f4e170 937 *
wolfSSL 14:167253f4e170 938 * a SP integer.
wolfSSL 14:167253f4e170 939 * s Number of digits to shift.
wolfSSL 14:167253f4e170 940 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 941 */
wolfSSL 14:167253f4e170 942 int sp_lshd(sp_int* a, int s)
wolfSSL 14:167253f4e170 943 {
wolfSSL 14:167253f4e170 944 if (a->used + s > a->size)
wolfSSL 14:167253f4e170 945 a->used = a->size - s;
wolfSSL 14:167253f4e170 946
wolfSSL 16:8e0d178b1d1e 947 XMEMMOVE(a->dp + s, a->dp, a->used * sizeof(sp_int_digit));
wolfSSL 14:167253f4e170 948 a->used += s;
wolfSSL 14:167253f4e170 949 XMEMSET(a->dp, 0, s * sizeof(sp_int_digit));
wolfSSL 16:8e0d178b1d1e 950 sp_clamp(a);
wolfSSL 14:167253f4e170 951
wolfSSL 14:167253f4e170 952 return MP_OKAY;
wolfSSL 14:167253f4e170 953 }
wolfSSL 14:167253f4e170 954 #endif
wolfSSL 14:167253f4e170 955
wolfSSL 16:8e0d178b1d1e 956 #if !defined(NO_PWDBASED) || defined(WOLFSSL_KEY_GEN) || !defined(NO_DH)
wolfSSL 14:167253f4e170 957 /* Add two large numbers into result: r = a + b
wolfSSL 14:167253f4e170 958 *
wolfSSL 14:167253f4e170 959 * a SP integer.
wolfSSL 14:167253f4e170 960 * b SP integer.
wolfSSL 14:167253f4e170 961 * r SP integer.
wolfSSL 14:167253f4e170 962 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 963 */
wolfSSL 14:167253f4e170 964 int sp_add(sp_int* a, sp_int* b, sp_int* r)
wolfSSL 14:167253f4e170 965 {
wolfSSL 14:167253f4e170 966 int i;
wolfSSL 16:8e0d178b1d1e 967 sp_int_digit c = 0;
wolfSSL 16:8e0d178b1d1e 968 sp_int_digit t;
wolfSSL 14:167253f4e170 969
wolfSSL 14:167253f4e170 970 for (i = 0; i < a->used && i < b->used; i++) {
wolfSSL 14:167253f4e170 971 t = a->dp[i] + b->dp[i] + c;
wolfSSL 14:167253f4e170 972 if (c == 0)
wolfSSL 14:167253f4e170 973 c = t < a->dp[i];
wolfSSL 14:167253f4e170 974 else
wolfSSL 14:167253f4e170 975 c = t <= a->dp[i];
wolfSSL 14:167253f4e170 976 r->dp[i] = t;
wolfSSL 14:167253f4e170 977 }
wolfSSL 14:167253f4e170 978 for (; i < a->used; i++) {
wolfSSL 14:167253f4e170 979 r->dp[i] = a->dp[i] + c;
wolfSSL 16:8e0d178b1d1e 980 c = (a->dp[i] != 0) && (r->dp[i] == 0);
wolfSSL 14:167253f4e170 981 }
wolfSSL 14:167253f4e170 982 for (; i < b->used; i++) {
wolfSSL 14:167253f4e170 983 r->dp[i] = b->dp[i] + c;
wolfSSL 16:8e0d178b1d1e 984 c = (b->dp[i] != 0) && (r->dp[i] == 0);
wolfSSL 14:167253f4e170 985 }
wolfSSL 14:167253f4e170 986 r->dp[i] = c;
wolfSSL 14:167253f4e170 987 r->used = (int)(i + c);
wolfSSL 14:167253f4e170 988
wolfSSL 14:167253f4e170 989 return MP_OKAY;
wolfSSL 14:167253f4e170 990 }
wolfSSL 16:8e0d178b1d1e 991 #endif /* !NO_PWDBASED || WOLFSSL_KEY_GEN || !NO_DH */
wolfSSL 14:167253f4e170 992
wolfSSL 14:167253f4e170 993 #ifndef NO_RSA
wolfSSL 14:167253f4e170 994 /* Set a number into the big number.
wolfSSL 14:167253f4e170 995 *
wolfSSL 14:167253f4e170 996 * a SP integer.
wolfSSL 14:167253f4e170 997 * b Value to set.
wolfSSL 14:167253f4e170 998 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 999 */
wolfSSL 14:167253f4e170 1000 int sp_set_int(sp_int* a, unsigned long b)
wolfSSL 14:167253f4e170 1001 {
wolfSSL 16:8e0d178b1d1e 1002 if (b == 0) {
wolfSSL 16:8e0d178b1d1e 1003 a->used = 0;
wolfSSL 16:8e0d178b1d1e 1004 a->dp[0] = 0;
wolfSSL 16:8e0d178b1d1e 1005 }
wolfSSL 16:8e0d178b1d1e 1006 else {
wolfSSL 16:8e0d178b1d1e 1007 a->used = 1;
wolfSSL 16:8e0d178b1d1e 1008 a->dp[0] = (sp_int_digit)b;
wolfSSL 16:8e0d178b1d1e 1009 }
wolfSSL 16:8e0d178b1d1e 1010
wolfSSL 16:8e0d178b1d1e 1011 return MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1012 }
wolfSSL 16:8e0d178b1d1e 1013 #endif /* !NO_RSA */
wolfSSL 16:8e0d178b1d1e 1014
wolfSSL 16:8e0d178b1d1e 1015 #ifdef WC_MP_TO_RADIX
wolfSSL 16:8e0d178b1d1e 1016 /* Hex string characters. */
wolfSSL 16:8e0d178b1d1e 1017 static const char sp_hex_char[16] = {
wolfSSL 16:8e0d178b1d1e 1018 '0', '1', '2', '3', '4', '5', '6', '7',
wolfSSL 16:8e0d178b1d1e 1019 '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'
wolfSSL 16:8e0d178b1d1e 1020 };
wolfSSL 16:8e0d178b1d1e 1021
wolfSSL 16:8e0d178b1d1e 1022 /* Put the hex string version, big-endian, of a in str.
wolfSSL 16:8e0d178b1d1e 1023 *
wolfSSL 16:8e0d178b1d1e 1024 * a SP integer.
wolfSSL 16:8e0d178b1d1e 1025 * str Hex string is stored here.
wolfSSL 16:8e0d178b1d1e 1026 * returns MP_OKAY always.
wolfSSL 16:8e0d178b1d1e 1027 */
wolfSSL 16:8e0d178b1d1e 1028 int sp_tohex(sp_int* a, char* str)
wolfSSL 16:8e0d178b1d1e 1029 {
wolfSSL 16:8e0d178b1d1e 1030 int i, j;
wolfSSL 16:8e0d178b1d1e 1031
wolfSSL 16:8e0d178b1d1e 1032 /* quick out if its zero */
wolfSSL 16:8e0d178b1d1e 1033 if (sp_iszero(a) == MP_YES) {
wolfSSL 16:8e0d178b1d1e 1034 *str++ = '0';
wolfSSL 16:8e0d178b1d1e 1035 *str = '\0';
wolfSSL 16:8e0d178b1d1e 1036 }
wolfSSL 16:8e0d178b1d1e 1037 else {
wolfSSL 16:8e0d178b1d1e 1038 i = a->used - 1;
wolfSSL 16:8e0d178b1d1e 1039 for (j = SP_WORD_SIZE - 4; j >= 0; j -= 4) {
wolfSSL 16:8e0d178b1d1e 1040 if (((a->dp[i] >> j) & 0xf) != 0)
wolfSSL 16:8e0d178b1d1e 1041 break;
wolfSSL 16:8e0d178b1d1e 1042 }
wolfSSL 16:8e0d178b1d1e 1043 for (; j >= 0; j -= 4)
wolfSSL 16:8e0d178b1d1e 1044 *(str++) = sp_hex_char[(a->dp[i] >> j) & 0xf];
wolfSSL 16:8e0d178b1d1e 1045 for (--i; i >= 0; i--) {
wolfSSL 16:8e0d178b1d1e 1046 for (j = SP_WORD_SIZE - 4; j >= 0; j -= 4)
wolfSSL 16:8e0d178b1d1e 1047 *(str++) = sp_hex_char[(a->dp[i] >> j) & 0xf];
wolfSSL 16:8e0d178b1d1e 1048 }
wolfSSL 16:8e0d178b1d1e 1049 *str = '\0';
wolfSSL 16:8e0d178b1d1e 1050 }
wolfSSL 16:8e0d178b1d1e 1051
wolfSSL 16:8e0d178b1d1e 1052 return MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1053 }
wolfSSL 16:8e0d178b1d1e 1054 #endif /* WC_MP_TO_RADIX */
wolfSSL 16:8e0d178b1d1e 1055
wolfSSL 16:8e0d178b1d1e 1056 #if defined(WOLFSSL_KEY_GEN) || !defined(NO_DH) && !defined(WC_NO_RNG)
wolfSSL 16:8e0d178b1d1e 1057 /* Set a bit of a: a |= 1 << i
wolfSSL 16:8e0d178b1d1e 1058 * The field 'used' is updated in a.
wolfSSL 16:8e0d178b1d1e 1059 *
wolfSSL 16:8e0d178b1d1e 1060 * a SP integer to modify.
wolfSSL 16:8e0d178b1d1e 1061 * i Index of bit to set.
wolfSSL 16:8e0d178b1d1e 1062 * returns MP_OKAY always.
wolfSSL 16:8e0d178b1d1e 1063 */
wolfSSL 16:8e0d178b1d1e 1064 int sp_set_bit(sp_int* a, int i)
wolfSSL 16:8e0d178b1d1e 1065 {
wolfSSL 16:8e0d178b1d1e 1066 int ret = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1067
wolfSSL 16:8e0d178b1d1e 1068 if ((a == NULL) || (i / SP_WORD_SIZE >= SP_INT_DIGITS)) {
wolfSSL 16:8e0d178b1d1e 1069 ret = BAD_FUNC_ARG;
wolfSSL 16:8e0d178b1d1e 1070 }
wolfSSL 16:8e0d178b1d1e 1071 else {
wolfSSL 16:8e0d178b1d1e 1072 a->dp[i/SP_WORD_SIZE] |= (sp_int_digit)1 << (i % SP_WORD_SIZE);
wolfSSL 16:8e0d178b1d1e 1073 if (a->used <= i / SP_WORD_SIZE)
wolfSSL 16:8e0d178b1d1e 1074 a->used = (i / SP_WORD_SIZE) + 1;
wolfSSL 16:8e0d178b1d1e 1075 }
wolfSSL 16:8e0d178b1d1e 1076 return ret;
wolfSSL 16:8e0d178b1d1e 1077 }
wolfSSL 16:8e0d178b1d1e 1078
wolfSSL 16:8e0d178b1d1e 1079 /* Exponentiate 2 to the power of e: a = 2^e
wolfSSL 16:8e0d178b1d1e 1080 * This is done by setting the 'e'th bit.
wolfSSL 16:8e0d178b1d1e 1081 *
wolfSSL 16:8e0d178b1d1e 1082 * a SP integer.
wolfSSL 16:8e0d178b1d1e 1083 * e Exponent.
wolfSSL 16:8e0d178b1d1e 1084 * returns MP_OKAY always.
wolfSSL 16:8e0d178b1d1e 1085 */
wolfSSL 16:8e0d178b1d1e 1086 int sp_2expt(sp_int* a, int e)
wolfSSL 16:8e0d178b1d1e 1087 {
wolfSSL 16:8e0d178b1d1e 1088 sp_zero(a);
wolfSSL 16:8e0d178b1d1e 1089 return sp_set_bit(a, e);
wolfSSL 16:8e0d178b1d1e 1090 }
wolfSSL 16:8e0d178b1d1e 1091
wolfSSL 16:8e0d178b1d1e 1092 /* Generate a random prime for RSA only.
wolfSSL 16:8e0d178b1d1e 1093 *
wolfSSL 16:8e0d178b1d1e 1094 * r SP integer
wolfSSL 16:8e0d178b1d1e 1095 * len Number of bytes to prime.
wolfSSL 16:8e0d178b1d1e 1096 * rng Random number generator.
wolfSSL 16:8e0d178b1d1e 1097 * heap Unused
wolfSSL 16:8e0d178b1d1e 1098 * returns MP_OKAY on success and MP_VAL when length is not supported or random
wolfSSL 16:8e0d178b1d1e 1099 * number genrator fails.
wolfSSL 16:8e0d178b1d1e 1100 */
wolfSSL 16:8e0d178b1d1e 1101 int sp_rand_prime(sp_int* r, int len, WC_RNG* rng, void* heap)
wolfSSL 16:8e0d178b1d1e 1102 {
wolfSSL 16:8e0d178b1d1e 1103 static const int USE_BBS = 1;
wolfSSL 16:8e0d178b1d1e 1104 int err = 0, type;
wolfSSL 16:8e0d178b1d1e 1105 int isPrime = MP_NO;
wolfSSL 16:8e0d178b1d1e 1106
wolfSSL 16:8e0d178b1d1e 1107 (void)heap;
wolfSSL 16:8e0d178b1d1e 1108
wolfSSL 16:8e0d178b1d1e 1109 /* get type */
wolfSSL 16:8e0d178b1d1e 1110 if (len < 0) {
wolfSSL 16:8e0d178b1d1e 1111 type = USE_BBS;
wolfSSL 16:8e0d178b1d1e 1112 len = -len;
wolfSSL 16:8e0d178b1d1e 1113 }
wolfSSL 16:8e0d178b1d1e 1114 else {
wolfSSL 16:8e0d178b1d1e 1115 type = 0;
wolfSSL 16:8e0d178b1d1e 1116 }
wolfSSL 16:8e0d178b1d1e 1117
wolfSSL 16:8e0d178b1d1e 1118 #if defined(WOLFSSL_HAVE_SP_DH) && defined(WOLFSSL_KEY_GEN)
wolfSSL 16:8e0d178b1d1e 1119 if (len == 32) {
wolfSSL 16:8e0d178b1d1e 1120 }
wolfSSL 16:8e0d178b1d1e 1121 else
wolfSSL 16:8e0d178b1d1e 1122 #endif
wolfSSL 16:8e0d178b1d1e 1123 /* Generate RSA primes that are half the modulus length. */
wolfSSL 16:8e0d178b1d1e 1124 #ifndef WOLFSSL_SP_NO_3072
wolfSSL 16:8e0d178b1d1e 1125 if (len != 128 && len != 192)
wolfSSL 16:8e0d178b1d1e 1126 #else
wolfSSL 16:8e0d178b1d1e 1127 if (len != 128)
wolfSSL 16:8e0d178b1d1e 1128 #endif
wolfSSL 16:8e0d178b1d1e 1129 {
wolfSSL 16:8e0d178b1d1e 1130 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1131 }
wolfSSL 16:8e0d178b1d1e 1132
wolfSSL 16:8e0d178b1d1e 1133 r->used = len / (SP_WORD_SIZE / 8);
wolfSSL 16:8e0d178b1d1e 1134
wolfSSL 16:8e0d178b1d1e 1135 /* Assume the candidate is probably prime and then test until
wolfSSL 16:8e0d178b1d1e 1136 * it is proven composite. */
wolfSSL 16:8e0d178b1d1e 1137 while (err == 0 && isPrime == MP_NO) {
wolfSSL 16:8e0d178b1d1e 1138 #ifdef SHOW_GEN
wolfSSL 16:8e0d178b1d1e 1139 printf(".");
wolfSSL 16:8e0d178b1d1e 1140 fflush(stdout);
wolfSSL 16:8e0d178b1d1e 1141 #endif
wolfSSL 16:8e0d178b1d1e 1142 /* generate value */
wolfSSL 16:8e0d178b1d1e 1143 err = wc_RNG_GenerateBlock(rng, (byte*)r->dp, len);
wolfSSL 16:8e0d178b1d1e 1144 if (err != 0) {
wolfSSL 16:8e0d178b1d1e 1145 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1146 break;
wolfSSL 16:8e0d178b1d1e 1147 }
wolfSSL 16:8e0d178b1d1e 1148
wolfSSL 16:8e0d178b1d1e 1149 /* munge bits */
wolfSSL 16:8e0d178b1d1e 1150 ((byte*)r->dp)[len-1] |= 0x80 | 0x40;
wolfSSL 16:8e0d178b1d1e 1151 r->dp[0] |= 0x01 | ((type & USE_BBS) ? 0x02 : 0x00);
wolfSSL 16:8e0d178b1d1e 1152
wolfSSL 16:8e0d178b1d1e 1153 /* test */
wolfSSL 16:8e0d178b1d1e 1154 /* Running Miller-Rabin up to 3 times gives us a 2^{-80} chance
wolfSSL 16:8e0d178b1d1e 1155 * of a 1024-bit candidate being a false positive, when it is our
wolfSSL 16:8e0d178b1d1e 1156 * prime candidate. (Note 4.49 of Handbook of Applied Cryptography.)
wolfSSL 16:8e0d178b1d1e 1157 * Using 8 because we've always used 8 */
wolfSSL 16:8e0d178b1d1e 1158 sp_prime_is_prime_ex(r, 8, &isPrime, rng);
wolfSSL 16:8e0d178b1d1e 1159 }
wolfSSL 16:8e0d178b1d1e 1160
wolfSSL 16:8e0d178b1d1e 1161 return err;
wolfSSL 16:8e0d178b1d1e 1162 }
wolfSSL 16:8e0d178b1d1e 1163
wolfSSL 16:8e0d178b1d1e 1164 /* Multiply a by b and store in r: r = a * b
wolfSSL 16:8e0d178b1d1e 1165 *
wolfSSL 16:8e0d178b1d1e 1166 * a SP integer to multiply.
wolfSSL 16:8e0d178b1d1e 1167 * b SP integer to multiply.
wolfSSL 16:8e0d178b1d1e 1168 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1169 * returns MP_OKAY always.
wolfSSL 16:8e0d178b1d1e 1170 */
wolfSSL 16:8e0d178b1d1e 1171 int sp_mul(sp_int* a, sp_int* b, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1172 {
wolfSSL 16:8e0d178b1d1e 1173 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1174 int i;
wolfSSL 16:8e0d178b1d1e 1175 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1176 sp_int* t = NULL;
wolfSSL 16:8e0d178b1d1e 1177 sp_int* tr;
wolfSSL 16:8e0d178b1d1e 1178 #else
wolfSSL 16:8e0d178b1d1e 1179 sp_int t[1];
wolfSSL 16:8e0d178b1d1e 1180 sp_int tr[1];
wolfSSL 16:8e0d178b1d1e 1181 #endif
wolfSSL 16:8e0d178b1d1e 1182
wolfSSL 16:8e0d178b1d1e 1183 if (a->used + b->used > SP_INT_DIGITS)
wolfSSL 16:8e0d178b1d1e 1184 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1185
wolfSSL 16:8e0d178b1d1e 1186 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1187 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1188 t = (sp_int*)XMALLOC(sizeof(sp_int) * 2, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1189 if (t == NULL)
wolfSSL 16:8e0d178b1d1e 1190 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 1191 else
wolfSSL 16:8e0d178b1d1e 1192 tr = &t[1];
wolfSSL 16:8e0d178b1d1e 1193 }
wolfSSL 16:8e0d178b1d1e 1194 #endif
wolfSSL 16:8e0d178b1d1e 1195
wolfSSL 16:8e0d178b1d1e 1196 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1197 sp_init(t);
wolfSSL 16:8e0d178b1d1e 1198 sp_init(tr);
wolfSSL 16:8e0d178b1d1e 1199
wolfSSL 16:8e0d178b1d1e 1200 for (i = 0; i < b->used; i++) {
wolfSSL 16:8e0d178b1d1e 1201 _sp_mul_d(a, b->dp[i], t, i);
wolfSSL 16:8e0d178b1d1e 1202 sp_add(tr, t, tr);
wolfSSL 16:8e0d178b1d1e 1203 }
wolfSSL 16:8e0d178b1d1e 1204 sp_copy(tr, r);
wolfSSL 16:8e0d178b1d1e 1205 }
wolfSSL 16:8e0d178b1d1e 1206
wolfSSL 16:8e0d178b1d1e 1207 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1208 if (t != NULL)
wolfSSL 16:8e0d178b1d1e 1209 XFREE(t, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1210 #endif
wolfSSL 16:8e0d178b1d1e 1211
wolfSSL 16:8e0d178b1d1e 1212 return err;
wolfSSL 16:8e0d178b1d1e 1213 }
wolfSSL 16:8e0d178b1d1e 1214
wolfSSL 16:8e0d178b1d1e 1215 /* Square a mod m and store in r: r = (a * a) mod m
wolfSSL 16:8e0d178b1d1e 1216 *
wolfSSL 16:8e0d178b1d1e 1217 * a SP integer to square.
wolfSSL 16:8e0d178b1d1e 1218 * m SP integer modulus.
wolfSSL 16:8e0d178b1d1e 1219 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1220 * returns MP_VAL when m is 0, MP_MEM when dynamic memory allocation fails,
wolfSSL 16:8e0d178b1d1e 1221 * BAD_FUNC_ARG when a is to big and MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1222 */
wolfSSL 16:8e0d178b1d1e 1223 static int sp_sqrmod(sp_int* a, sp_int* m, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1224 {
wolfSSL 16:8e0d178b1d1e 1225 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1226
wolfSSL 16:8e0d178b1d1e 1227 if (a->used * 2 > SP_INT_DIGITS)
wolfSSL 16:8e0d178b1d1e 1228 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1229
wolfSSL 16:8e0d178b1d1e 1230 if (err == MP_OKAY)
wolfSSL 16:8e0d178b1d1e 1231 err = sp_mul(a, a, r);
wolfSSL 16:8e0d178b1d1e 1232 if (err == MP_OKAY)
wolfSSL 16:8e0d178b1d1e 1233 err = sp_mod(r, m, r);
wolfSSL 16:8e0d178b1d1e 1234
wolfSSL 16:8e0d178b1d1e 1235 return err;
wolfSSL 16:8e0d178b1d1e 1236 }
wolfSSL 16:8e0d178b1d1e 1237
wolfSSL 16:8e0d178b1d1e 1238 #if defined(WOLFSSL_HAVE_SP_DH) || defined(WOLFSSL_KEY_GEN)
wolfSSL 16:8e0d178b1d1e 1239 /* Multiply a by b mod m and store in r: r = (a * b) mod m
wolfSSL 16:8e0d178b1d1e 1240 *
wolfSSL 16:8e0d178b1d1e 1241 * a SP integer to multiply.
wolfSSL 16:8e0d178b1d1e 1242 * b SP integer to multiply.
wolfSSL 16:8e0d178b1d1e 1243 * m SP integer modulus.
wolfSSL 16:8e0d178b1d1e 1244 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1245 * returns MP_VAL when m is 0, MP_MEM when dynamic memory allocation fails and
wolfSSL 16:8e0d178b1d1e 1246 * MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1247 */
wolfSSL 16:8e0d178b1d1e 1248 int sp_mulmod(sp_int* a, sp_int* b, sp_int* m, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1249 {
wolfSSL 16:8e0d178b1d1e 1250 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1251 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1252 sp_int* t = NULL;
wolfSSL 16:8e0d178b1d1e 1253 #else
wolfSSL 16:8e0d178b1d1e 1254 sp_int t[1];
wolfSSL 16:8e0d178b1d1e 1255 #endif
wolfSSL 16:8e0d178b1d1e 1256
wolfSSL 16:8e0d178b1d1e 1257 if (a->used + b->used > SP_INT_DIGITS)
wolfSSL 16:8e0d178b1d1e 1258 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1259
wolfSSL 16:8e0d178b1d1e 1260 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1261 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1262 t = (sp_int*)XMALLOC(sizeof(sp_int), NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1263 if (t == NULL) {
wolfSSL 16:8e0d178b1d1e 1264 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 1265 }
wolfSSL 16:8e0d178b1d1e 1266 }
wolfSSL 16:8e0d178b1d1e 1267 #endif
wolfSSL 16:8e0d178b1d1e 1268 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1269 err = sp_mul(a, b, t);
wolfSSL 16:8e0d178b1d1e 1270 }
wolfSSL 16:8e0d178b1d1e 1271 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1272 err = sp_mod(t, m, r);
wolfSSL 16:8e0d178b1d1e 1273 }
wolfSSL 16:8e0d178b1d1e 1274
wolfSSL 16:8e0d178b1d1e 1275 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1276 if (t != NULL)
wolfSSL 16:8e0d178b1d1e 1277 XFREE(t, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1278 #endif
wolfSSL 16:8e0d178b1d1e 1279 return err;
wolfSSL 16:8e0d178b1d1e 1280 }
wolfSSL 16:8e0d178b1d1e 1281 #endif
wolfSSL 16:8e0d178b1d1e 1282
wolfSSL 16:8e0d178b1d1e 1283 /* Calculate a modulo the digit d into r: r = a mod d
wolfSSL 16:8e0d178b1d1e 1284 *
wolfSSL 16:8e0d178b1d1e 1285 * a SP integer to square.
wolfSSL 16:8e0d178b1d1e 1286 * d SP integer digit, modulus.
wolfSSL 16:8e0d178b1d1e 1287 * r SP integer digit, result.
wolfSSL 16:8e0d178b1d1e 1288 * returns MP_VAL when d is 0 and MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1289 */
wolfSSL 16:8e0d178b1d1e 1290 static int sp_mod_d(sp_int* a, const sp_int_digit d, sp_int_digit* r)
wolfSSL 16:8e0d178b1d1e 1291 {
wolfSSL 16:8e0d178b1d1e 1292 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1293 int i;
wolfSSL 16:8e0d178b1d1e 1294 sp_int_word w = 0;
wolfSSL 16:8e0d178b1d1e 1295 sp_int_digit t;
wolfSSL 16:8e0d178b1d1e 1296
wolfSSL 16:8e0d178b1d1e 1297 if (d == 0)
wolfSSL 16:8e0d178b1d1e 1298 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1299
wolfSSL 16:8e0d178b1d1e 1300 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1301 for (i = a->used - 1; i >= 0; i--) {
wolfSSL 16:8e0d178b1d1e 1302 w = (w << SP_WORD_SIZE) | a->dp[i];
wolfSSL 16:8e0d178b1d1e 1303 t = (sp_int_digit)(w / d);
wolfSSL 16:8e0d178b1d1e 1304 w -= (sp_int_word)t * d;
wolfSSL 16:8e0d178b1d1e 1305 }
wolfSSL 16:8e0d178b1d1e 1306
wolfSSL 16:8e0d178b1d1e 1307 *r = (sp_int_digit)w;
wolfSSL 16:8e0d178b1d1e 1308 }
wolfSSL 16:8e0d178b1d1e 1309
wolfSSL 16:8e0d178b1d1e 1310 return err;
wolfSSL 16:8e0d178b1d1e 1311 }
wolfSSL 16:8e0d178b1d1e 1312
wolfSSL 16:8e0d178b1d1e 1313 /* Calculates the Greatest Common Denominator (GCD) of a and b into r.
wolfSSL 16:8e0d178b1d1e 1314 *
wolfSSL 16:8e0d178b1d1e 1315 * a SP integer operand.
wolfSSL 16:8e0d178b1d1e 1316 * b SP integer operand.
wolfSSL 16:8e0d178b1d1e 1317 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1318 * returns MP_MEM when dynamic memory allocation fails and MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1319 */
wolfSSL 16:8e0d178b1d1e 1320 int sp_gcd(sp_int* a, sp_int* b, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1321 {
wolfSSL 16:8e0d178b1d1e 1322 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1323 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1324 sp_int* u = NULL;
wolfSSL 16:8e0d178b1d1e 1325 sp_int* v;
wolfSSL 16:8e0d178b1d1e 1326 sp_int* t;
wolfSSL 16:8e0d178b1d1e 1327 #else
wolfSSL 16:8e0d178b1d1e 1328 sp_int u[1], v[1], t[1];
wolfSSL 16:8e0d178b1d1e 1329 #endif
wolfSSL 16:8e0d178b1d1e 1330
wolfSSL 16:8e0d178b1d1e 1331 if (sp_iszero(a))
wolfSSL 16:8e0d178b1d1e 1332 sp_copy(b, r);
wolfSSL 16:8e0d178b1d1e 1333 else if (sp_iszero(b))
wolfSSL 16:8e0d178b1d1e 1334 sp_copy(a, r);
wolfSSL 16:8e0d178b1d1e 1335 else {
wolfSSL 16:8e0d178b1d1e 1336 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1337 u = (sp_int*)XMALLOC(sizeof(sp_int) * 3, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1338 if (u == NULL)
wolfSSL 16:8e0d178b1d1e 1339 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 1340 else {
wolfSSL 16:8e0d178b1d1e 1341 v = &u[1];
wolfSSL 16:8e0d178b1d1e 1342 t = &u[2];
wolfSSL 16:8e0d178b1d1e 1343 }
wolfSSL 16:8e0d178b1d1e 1344 #endif
wolfSSL 16:8e0d178b1d1e 1345
wolfSSL 16:8e0d178b1d1e 1346 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1347 sp_init(u);
wolfSSL 16:8e0d178b1d1e 1348 sp_init(v);
wolfSSL 16:8e0d178b1d1e 1349 sp_init(t);
wolfSSL 16:8e0d178b1d1e 1350
wolfSSL 16:8e0d178b1d1e 1351 if (sp_cmp(a, b) != MP_LT) {
wolfSSL 16:8e0d178b1d1e 1352 sp_copy(b, u);
wolfSSL 16:8e0d178b1d1e 1353 /* First iteration - u = a, v = b */
wolfSSL 16:8e0d178b1d1e 1354 if (b->used == 1) {
wolfSSL 16:8e0d178b1d1e 1355 err = sp_mod_d(a, b->dp[0], &v->dp[0]);
wolfSSL 16:8e0d178b1d1e 1356 if (err == MP_OKAY)
wolfSSL 16:8e0d178b1d1e 1357 v->used = (v->dp[0] != 0);
wolfSSL 16:8e0d178b1d1e 1358 }
wolfSSL 16:8e0d178b1d1e 1359 else
wolfSSL 16:8e0d178b1d1e 1360 err = sp_mod(a, b, v);
wolfSSL 16:8e0d178b1d1e 1361 }
wolfSSL 16:8e0d178b1d1e 1362 else {
wolfSSL 16:8e0d178b1d1e 1363 sp_copy(a, u);
wolfSSL 16:8e0d178b1d1e 1364 /* First iteration - u = b, v = a */
wolfSSL 16:8e0d178b1d1e 1365 if (a->used == 1) {
wolfSSL 16:8e0d178b1d1e 1366 err = sp_mod_d(b, a->dp[0], &v->dp[0]);
wolfSSL 16:8e0d178b1d1e 1367 if (err == MP_OKAY)
wolfSSL 16:8e0d178b1d1e 1368 v->used = (v->dp[0] != 0);
wolfSSL 16:8e0d178b1d1e 1369 }
wolfSSL 16:8e0d178b1d1e 1370 else
wolfSSL 16:8e0d178b1d1e 1371 err = sp_mod(b, a, v);
wolfSSL 16:8e0d178b1d1e 1372 }
wolfSSL 16:8e0d178b1d1e 1373 }
wolfSSL 16:8e0d178b1d1e 1374
wolfSSL 16:8e0d178b1d1e 1375 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1376 while (!sp_iszero(v)) {
wolfSSL 16:8e0d178b1d1e 1377 if (v->used == 1) {
wolfSSL 16:8e0d178b1d1e 1378 sp_mod_d(u, v->dp[0], &t->dp[0]);
wolfSSL 16:8e0d178b1d1e 1379 t->used = (t->dp[0] != 0);
wolfSSL 16:8e0d178b1d1e 1380 }
wolfSSL 16:8e0d178b1d1e 1381 else
wolfSSL 16:8e0d178b1d1e 1382 sp_mod(u, v, t);
wolfSSL 16:8e0d178b1d1e 1383 sp_copy(v, u);
wolfSSL 16:8e0d178b1d1e 1384 sp_copy(t, v);
wolfSSL 16:8e0d178b1d1e 1385 }
wolfSSL 16:8e0d178b1d1e 1386 sp_copy(u, r);
wolfSSL 16:8e0d178b1d1e 1387 }
wolfSSL 16:8e0d178b1d1e 1388 }
wolfSSL 16:8e0d178b1d1e 1389
wolfSSL 16:8e0d178b1d1e 1390 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1391 if (u != NULL)
wolfSSL 16:8e0d178b1d1e 1392 XFREE(u, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1393 #endif
wolfSSL 16:8e0d178b1d1e 1394
wolfSSL 16:8e0d178b1d1e 1395 return err;
wolfSSL 16:8e0d178b1d1e 1396 }
wolfSSL 16:8e0d178b1d1e 1397
wolfSSL 16:8e0d178b1d1e 1398 /* Divides a by 2 and stores in r: r = a >> 1
wolfSSL 16:8e0d178b1d1e 1399 *
wolfSSL 16:8e0d178b1d1e 1400 * a SP integer to divide.
wolfSSL 16:8e0d178b1d1e 1401 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1402 * returns MP_OKAY always.
wolfSSL 16:8e0d178b1d1e 1403 */
wolfSSL 16:8e0d178b1d1e 1404 static int sp_div_2(sp_int* a, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1405 {
wolfSSL 16:8e0d178b1d1e 1406 int i;
wolfSSL 16:8e0d178b1d1e 1407
wolfSSL 16:8e0d178b1d1e 1408 for (i = 0; i < a->used-1; i++)
wolfSSL 16:8e0d178b1d1e 1409 r->dp[i] = (a->dp[i] >> 1) | (a->dp[i+1] << (SP_WORD_SIZE - 1));
wolfSSL 16:8e0d178b1d1e 1410 r->dp[i] = a->dp[i] >> 1;
wolfSSL 16:8e0d178b1d1e 1411 r->used = i + 1;
wolfSSL 16:8e0d178b1d1e 1412 sp_clamp(r);
wolfSSL 16:8e0d178b1d1e 1413
wolfSSL 16:8e0d178b1d1e 1414 return MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1415 }
wolfSSL 16:8e0d178b1d1e 1416
wolfSSL 16:8e0d178b1d1e 1417
wolfSSL 16:8e0d178b1d1e 1418 /* Calculates the multiplicative inverse in the field.
wolfSSL 16:8e0d178b1d1e 1419 *
wolfSSL 16:8e0d178b1d1e 1420 * a SP integer to invert.
wolfSSL 16:8e0d178b1d1e 1421 * m SP integer that is the modulus of the field.
wolfSSL 16:8e0d178b1d1e 1422 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1423 * returns MP_VAL when a or m is 0, MP_MEM when dynamic memory allocation fails
wolfSSL 16:8e0d178b1d1e 1424 * and MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1425 */
wolfSSL 16:8e0d178b1d1e 1426 int sp_invmod(sp_int* a, sp_int* m, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1427 {
wolfSSL 16:8e0d178b1d1e 1428 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1429 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1430 sp_int* u = NULL;
wolfSSL 16:8e0d178b1d1e 1431 sp_int* v;
wolfSSL 16:8e0d178b1d1e 1432 sp_int* b;
wolfSSL 16:8e0d178b1d1e 1433 sp_int* c;
wolfSSL 16:8e0d178b1d1e 1434 #else
wolfSSL 16:8e0d178b1d1e 1435 sp_int u[1], v[1], b[1], c[1];
wolfSSL 16:8e0d178b1d1e 1436 #endif
wolfSSL 16:8e0d178b1d1e 1437
wolfSSL 16:8e0d178b1d1e 1438 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1439 u = (sp_int*)XMALLOC(sizeof(sp_int) * 4, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1440 if (u == NULL) {
wolfSSL 16:8e0d178b1d1e 1441 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 1442 }
wolfSSL 16:8e0d178b1d1e 1443 #endif
wolfSSL 16:8e0d178b1d1e 1444
wolfSSL 16:8e0d178b1d1e 1445 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1446 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1447 v = &u[1];
wolfSSL 16:8e0d178b1d1e 1448 b = &u[2];
wolfSSL 16:8e0d178b1d1e 1449 c = &u[3];
wolfSSL 16:8e0d178b1d1e 1450 #endif
wolfSSL 16:8e0d178b1d1e 1451 sp_init(v);
wolfSSL 16:8e0d178b1d1e 1452
wolfSSL 16:8e0d178b1d1e 1453 if (sp_cmp(a, m) != MP_LT) {
wolfSSL 16:8e0d178b1d1e 1454 err = sp_mod(a, m, v);
wolfSSL 16:8e0d178b1d1e 1455 a = v;
wolfSSL 16:8e0d178b1d1e 1456 }
wolfSSL 16:8e0d178b1d1e 1457 }
wolfSSL 16:8e0d178b1d1e 1458
wolfSSL 16:8e0d178b1d1e 1459 /* 0 != n*m + 1 (+ve m), r*a mod 0 is always 0 (never 1) */
wolfSSL 16:8e0d178b1d1e 1460 if ((err == MP_OKAY) && (sp_iszero(a) || sp_iszero(m))) {
wolfSSL 16:8e0d178b1d1e 1461 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1462 }
wolfSSL 16:8e0d178b1d1e 1463 /* r*2*x != n*2*y + 1 */
wolfSSL 16:8e0d178b1d1e 1464 if ((err == MP_OKAY) && sp_iseven(a) && sp_iseven(m)) {
wolfSSL 16:8e0d178b1d1e 1465 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1466 }
wolfSSL 16:8e0d178b1d1e 1467
wolfSSL 16:8e0d178b1d1e 1468 /* 1*1 = 0*m + 1 */
wolfSSL 16:8e0d178b1d1e 1469 if ((err == MP_OKAY) && sp_isone(a)) {
wolfSSL 16:8e0d178b1d1e 1470 sp_set(r, 1);
wolfSSL 16:8e0d178b1d1e 1471 }
wolfSSL 16:8e0d178b1d1e 1472 else if (err != MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1473 }
wolfSSL 16:8e0d178b1d1e 1474 else if (sp_iseven(m)) {
wolfSSL 16:8e0d178b1d1e 1475 /* a^-1 mod m = m + (1 - m*(m^-1 % a)) / a
wolfSSL 16:8e0d178b1d1e 1476 * = m - (m*(m^-1 % a) - 1) / a
wolfSSL 16:8e0d178b1d1e 1477 */
wolfSSL 16:8e0d178b1d1e 1478 err = sp_invmod(m, a, r);
wolfSSL 16:8e0d178b1d1e 1479 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1480 err = sp_mul(r, m, r);
wolfSSL 16:8e0d178b1d1e 1481 }
wolfSSL 16:8e0d178b1d1e 1482 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1483 sp_sub_d(r, 1, r);
wolfSSL 16:8e0d178b1d1e 1484 sp_div(r, a, r, NULL);
wolfSSL 16:8e0d178b1d1e 1485 sp_sub(m, r, r);
wolfSSL 16:8e0d178b1d1e 1486 }
wolfSSL 16:8e0d178b1d1e 1487 }
wolfSSL 16:8e0d178b1d1e 1488 else {
wolfSSL 16:8e0d178b1d1e 1489 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1490 sp_init(u);
wolfSSL 16:8e0d178b1d1e 1491 sp_init(b);
wolfSSL 16:8e0d178b1d1e 1492 sp_init(c);
wolfSSL 16:8e0d178b1d1e 1493
wolfSSL 16:8e0d178b1d1e 1494 sp_copy(m, u);
wolfSSL 16:8e0d178b1d1e 1495 sp_copy(a, v);
wolfSSL 16:8e0d178b1d1e 1496 sp_zero(b);
wolfSSL 16:8e0d178b1d1e 1497 sp_set(c, 1);
wolfSSL 16:8e0d178b1d1e 1498
wolfSSL 16:8e0d178b1d1e 1499 while (!sp_isone(v) && !sp_iszero(u)) {
wolfSSL 16:8e0d178b1d1e 1500 if (sp_iseven(u)) {
wolfSSL 16:8e0d178b1d1e 1501 sp_div_2(u, u);
wolfSSL 16:8e0d178b1d1e 1502 if (sp_isodd(b)) {
wolfSSL 16:8e0d178b1d1e 1503 sp_add(b, m, b);
wolfSSL 16:8e0d178b1d1e 1504 }
wolfSSL 16:8e0d178b1d1e 1505 sp_div_2(b, b);
wolfSSL 16:8e0d178b1d1e 1506 }
wolfSSL 16:8e0d178b1d1e 1507 else if (sp_iseven(v)) {
wolfSSL 16:8e0d178b1d1e 1508 sp_div_2(v, v);
wolfSSL 16:8e0d178b1d1e 1509 if (sp_isodd(c)) {
wolfSSL 16:8e0d178b1d1e 1510 sp_add(c, m, c);
wolfSSL 16:8e0d178b1d1e 1511 }
wolfSSL 16:8e0d178b1d1e 1512 sp_div_2(c, c);
wolfSSL 16:8e0d178b1d1e 1513 }
wolfSSL 16:8e0d178b1d1e 1514 else if (sp_cmp(u, v) != MP_LT) {
wolfSSL 16:8e0d178b1d1e 1515 sp_sub(u, v, u);
wolfSSL 16:8e0d178b1d1e 1516 if (sp_cmp(b, c) == MP_LT) {
wolfSSL 16:8e0d178b1d1e 1517 sp_add(b, m, b);
wolfSSL 16:8e0d178b1d1e 1518 }
wolfSSL 16:8e0d178b1d1e 1519 sp_sub(b, c, b);
wolfSSL 16:8e0d178b1d1e 1520 }
wolfSSL 16:8e0d178b1d1e 1521 else {
wolfSSL 16:8e0d178b1d1e 1522 sp_sub(v, u, v);
wolfSSL 16:8e0d178b1d1e 1523 if (sp_cmp(c, b) == MP_LT) {
wolfSSL 16:8e0d178b1d1e 1524 sp_add(c, m, c);
wolfSSL 16:8e0d178b1d1e 1525 }
wolfSSL 16:8e0d178b1d1e 1526 sp_sub(c, b, c);
wolfSSL 16:8e0d178b1d1e 1527 }
wolfSSL 16:8e0d178b1d1e 1528 }
wolfSSL 16:8e0d178b1d1e 1529 if (sp_iszero(u)) {
wolfSSL 16:8e0d178b1d1e 1530 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1531 }
wolfSSL 16:8e0d178b1d1e 1532 else {
wolfSSL 16:8e0d178b1d1e 1533 sp_copy(c, r);
wolfSSL 16:8e0d178b1d1e 1534 }
wolfSSL 16:8e0d178b1d1e 1535 }
wolfSSL 16:8e0d178b1d1e 1536 }
wolfSSL 16:8e0d178b1d1e 1537
wolfSSL 16:8e0d178b1d1e 1538 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1539 if (u != NULL) {
wolfSSL 16:8e0d178b1d1e 1540 XFREE(u, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1541 }
wolfSSL 16:8e0d178b1d1e 1542 #endif
wolfSSL 16:8e0d178b1d1e 1543
wolfSSL 16:8e0d178b1d1e 1544 return err;
wolfSSL 16:8e0d178b1d1e 1545 }
wolfSSL 16:8e0d178b1d1e 1546
wolfSSL 16:8e0d178b1d1e 1547 /* Calculates the Lowest Common Multiple (LCM) of a and b and stores in r.
wolfSSL 16:8e0d178b1d1e 1548 *
wolfSSL 16:8e0d178b1d1e 1549 * a SP integer operand.
wolfSSL 16:8e0d178b1d1e 1550 * b SP integer operand.
wolfSSL 16:8e0d178b1d1e 1551 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1552 * returns MP_MEM when dynamic memory allocation fails and MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1553 */
wolfSSL 16:8e0d178b1d1e 1554 int sp_lcm(sp_int* a, sp_int* b, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1555 {
wolfSSL 16:8e0d178b1d1e 1556 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1557 #ifndef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1558 sp_int t[2];
wolfSSL 16:8e0d178b1d1e 1559 #else
wolfSSL 16:8e0d178b1d1e 1560 sp_int *t = NULL;
wolfSSL 16:8e0d178b1d1e 1561 #endif
wolfSSL 16:8e0d178b1d1e 1562
wolfSSL 16:8e0d178b1d1e 1563 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1564 t = (sp_int*)XMALLOC(sizeof(sp_int) * 2, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1565 if (t == NULL) {
wolfSSL 16:8e0d178b1d1e 1566 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 1567 }
wolfSSL 16:8e0d178b1d1e 1568 #endif
wolfSSL 16:8e0d178b1d1e 1569
wolfSSL 16:8e0d178b1d1e 1570 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1571 sp_init(&t[0]);
wolfSSL 16:8e0d178b1d1e 1572 sp_init(&t[1]);
wolfSSL 16:8e0d178b1d1e 1573 err = sp_gcd(a, b, &t[0]);
wolfSSL 16:8e0d178b1d1e 1574 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1575 if (sp_cmp(a, b) == MP_GT) {
wolfSSL 16:8e0d178b1d1e 1576 err = sp_div(a, &t[0], &t[1], NULL);
wolfSSL 16:8e0d178b1d1e 1577 if (err == MP_OKAY)
wolfSSL 16:8e0d178b1d1e 1578 err = sp_mul(b, &t[1], r);
wolfSSL 16:8e0d178b1d1e 1579 }
wolfSSL 16:8e0d178b1d1e 1580 else {
wolfSSL 16:8e0d178b1d1e 1581 err = sp_div(b, &t[0], &t[1], NULL);
wolfSSL 16:8e0d178b1d1e 1582 if (err == MP_OKAY)
wolfSSL 16:8e0d178b1d1e 1583 err = sp_mul(a, &t[1], r);
wolfSSL 16:8e0d178b1d1e 1584 }
wolfSSL 16:8e0d178b1d1e 1585 }
wolfSSL 16:8e0d178b1d1e 1586 }
wolfSSL 16:8e0d178b1d1e 1587
wolfSSL 16:8e0d178b1d1e 1588 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1589 if (t != NULL)
wolfSSL 16:8e0d178b1d1e 1590 XFREE(t, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1591 #endif
wolfSSL 16:8e0d178b1d1e 1592 return err;
wolfSSL 16:8e0d178b1d1e 1593 }
wolfSSL 14:167253f4e170 1594
wolfSSL 16:8e0d178b1d1e 1595 /* Exponentiates b to the power of e modulo m into r: r = b ^ e mod m
wolfSSL 16:8e0d178b1d1e 1596 *
wolfSSL 16:8e0d178b1d1e 1597 * b SP integer base.
wolfSSL 16:8e0d178b1d1e 1598 * e SP integer exponent.
wolfSSL 16:8e0d178b1d1e 1599 * m SP integer modulus.
wolfSSL 16:8e0d178b1d1e 1600 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 1601 * returns MP_VAL when m is not 1024, 2048, 1536 or 3072 bits and otherwise
wolfSSL 16:8e0d178b1d1e 1602 * MP_OKAY.
wolfSSL 16:8e0d178b1d1e 1603 */
wolfSSL 16:8e0d178b1d1e 1604 int sp_exptmod(sp_int* b, sp_int* e, sp_int* m, sp_int* r)
wolfSSL 16:8e0d178b1d1e 1605 {
wolfSSL 16:8e0d178b1d1e 1606 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1607 int done = 0;
wolfSSL 16:8e0d178b1d1e 1608 int mBits = sp_count_bits(m);
wolfSSL 16:8e0d178b1d1e 1609 int bBits = sp_count_bits(b);
wolfSSL 16:8e0d178b1d1e 1610 int eBits = sp_count_bits(e);
wolfSSL 16:8e0d178b1d1e 1611
wolfSSL 16:8e0d178b1d1e 1612 if (sp_iszero(m)) {
wolfSSL 16:8e0d178b1d1e 1613 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1614 }
wolfSSL 16:8e0d178b1d1e 1615 else if (sp_isone(m)) {
wolfSSL 16:8e0d178b1d1e 1616 sp_set(r, 0);
wolfSSL 16:8e0d178b1d1e 1617 done = 1;
wolfSSL 16:8e0d178b1d1e 1618 }
wolfSSL 16:8e0d178b1d1e 1619 else if (sp_iszero(e)) {
wolfSSL 16:8e0d178b1d1e 1620 sp_set(r, 1);
wolfSSL 16:8e0d178b1d1e 1621 done = 1;
wolfSSL 16:8e0d178b1d1e 1622 }
wolfSSL 16:8e0d178b1d1e 1623 else if (sp_iszero(b)) {
wolfSSL 16:8e0d178b1d1e 1624 sp_set(r, 0);
wolfSSL 16:8e0d178b1d1e 1625 done = 1;
wolfSSL 16:8e0d178b1d1e 1626 }
wolfSSL 16:8e0d178b1d1e 1627 else if (m->used * 2 > SP_INT_DIGITS) {
wolfSSL 16:8e0d178b1d1e 1628 err = BAD_FUNC_ARG;
wolfSSL 16:8e0d178b1d1e 1629 }
wolfSSL 16:8e0d178b1d1e 1630
wolfSSL 16:8e0d178b1d1e 1631 if (!done && (err == MP_OKAY)) {
wolfSSL 16:8e0d178b1d1e 1632 #ifndef WOLFSSL_SP_NO_2048
wolfSSL 16:8e0d178b1d1e 1633 if ((mBits == 1024) && sp_isodd(m) && (bBits <= 1024) &&
wolfSSL 16:8e0d178b1d1e 1634 (eBits <= 1024)) {
wolfSSL 16:8e0d178b1d1e 1635 err = sp_ModExp_1024(b, e, m, r);
wolfSSL 16:8e0d178b1d1e 1636 done = 1;
wolfSSL 16:8e0d178b1d1e 1637 }
wolfSSL 16:8e0d178b1d1e 1638 else if ((mBits == 2048) && sp_isodd(m) && (bBits <= 2048) &&
wolfSSL 16:8e0d178b1d1e 1639 (eBits <= 2048)) {
wolfSSL 16:8e0d178b1d1e 1640 err = sp_ModExp_2048(b, e, m, r);
wolfSSL 16:8e0d178b1d1e 1641 done = 1;
wolfSSL 16:8e0d178b1d1e 1642 }
wolfSSL 16:8e0d178b1d1e 1643 else
wolfSSL 16:8e0d178b1d1e 1644 #endif
wolfSSL 16:8e0d178b1d1e 1645 #ifndef WOLFSSL_SP_NO_3072
wolfSSL 16:8e0d178b1d1e 1646 if ((mBits == 1536) && sp_isodd(m) && (bBits <= 1536) &&
wolfSSL 16:8e0d178b1d1e 1647 (eBits <= 1536)) {
wolfSSL 16:8e0d178b1d1e 1648 err = sp_ModExp_1536(b, e, m, r);
wolfSSL 16:8e0d178b1d1e 1649 done = 1;
wolfSSL 16:8e0d178b1d1e 1650 }
wolfSSL 16:8e0d178b1d1e 1651 else if ((mBits == 3072) && sp_isodd(m) && (bBits <= 3072) &&
wolfSSL 16:8e0d178b1d1e 1652 (eBits <= 3072)) {
wolfSSL 16:8e0d178b1d1e 1653 err = sp_ModExp_3072(b, e, m, r);
wolfSSL 16:8e0d178b1d1e 1654 done = 1;
wolfSSL 16:8e0d178b1d1e 1655 }
wolfSSL 16:8e0d178b1d1e 1656 else
wolfSSL 16:8e0d178b1d1e 1657 #endif
wolfSSL 16:8e0d178b1d1e 1658 #ifdef WOLFSSL_SP_NO_4096
wolfSSL 16:8e0d178b1d1e 1659 if ((mBits == 4096) && sp_isodd(m) && (bBits <= 4096) &&
wolfSSL 16:8e0d178b1d1e 1660 (eBits <= 4096)) {
wolfSSL 16:8e0d178b1d1e 1661 err = sp_ModExp_4096(b, e, m, r);
wolfSSL 16:8e0d178b1d1e 1662 done = 1;
wolfSSL 16:8e0d178b1d1e 1663 }
wolfSSL 16:8e0d178b1d1e 1664 else
wolfSSL 16:8e0d178b1d1e 1665 #endif
wolfSSL 16:8e0d178b1d1e 1666 {
wolfSSL 16:8e0d178b1d1e 1667 }
wolfSSL 16:8e0d178b1d1e 1668 }
wolfSSL 16:8e0d178b1d1e 1669 #if defined(WOLFSSL_HAVE_SP_DH) && defined(WOLFSSL_KEY_GEN)
wolfSSL 16:8e0d178b1d1e 1670 if (!done && (err == MP_OKAY)) {
wolfSSL 16:8e0d178b1d1e 1671 int i;
wolfSSL 16:8e0d178b1d1e 1672
wolfSSL 16:8e0d178b1d1e 1673 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1674 sp_int* t = NULL;
wolfSSL 16:8e0d178b1d1e 1675 #else
wolfSSL 16:8e0d178b1d1e 1676 sp_int t[1];
wolfSSL 16:8e0d178b1d1e 1677 #endif
wolfSSL 16:8e0d178b1d1e 1678
wolfSSL 16:8e0d178b1d1e 1679 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1680 if (!done && (err == MP_OKAY)) {
wolfSSL 16:8e0d178b1d1e 1681 t = (sp_int*)XMALLOC(sizeof(sp_int), NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1682 if (t == NULL) {
wolfSSL 16:8e0d178b1d1e 1683 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 1684 }
wolfSSL 16:8e0d178b1d1e 1685 }
wolfSSL 16:8e0d178b1d1e 1686 #endif
wolfSSL 16:8e0d178b1d1e 1687 if (!done && (err == MP_OKAY)) {
wolfSSL 16:8e0d178b1d1e 1688 sp_init(t);
wolfSSL 16:8e0d178b1d1e 1689
wolfSSL 16:8e0d178b1d1e 1690 if (sp_cmp(b, m) != MP_LT) {
wolfSSL 16:8e0d178b1d1e 1691 err = sp_mod(b, m, t);
wolfSSL 16:8e0d178b1d1e 1692 if (err == MP_OKAY && sp_iszero(t)) {
wolfSSL 16:8e0d178b1d1e 1693 sp_set(r, 0);
wolfSSL 16:8e0d178b1d1e 1694 done = 1;
wolfSSL 16:8e0d178b1d1e 1695 }
wolfSSL 16:8e0d178b1d1e 1696 }
wolfSSL 16:8e0d178b1d1e 1697 else {
wolfSSL 16:8e0d178b1d1e 1698 sp_copy(b, t);
wolfSSL 16:8e0d178b1d1e 1699 }
wolfSSL 16:8e0d178b1d1e 1700
wolfSSL 16:8e0d178b1d1e 1701 if (!done && (err == MP_OKAY)) {
wolfSSL 16:8e0d178b1d1e 1702 for (i = eBits-2; err == MP_OKAY && i >= 0; i--) {
wolfSSL 16:8e0d178b1d1e 1703 err = sp_sqrmod(t, m, t);
wolfSSL 16:8e0d178b1d1e 1704 if (err == MP_OKAY && (e->dp[i / SP_WORD_SIZE] >>
wolfSSL 16:8e0d178b1d1e 1705 (i % SP_WORD_SIZE)) & 1) {
wolfSSL 16:8e0d178b1d1e 1706 err = sp_mulmod(t, b, m, t);
wolfSSL 16:8e0d178b1d1e 1707 }
wolfSSL 16:8e0d178b1d1e 1708 }
wolfSSL 16:8e0d178b1d1e 1709 }
wolfSSL 16:8e0d178b1d1e 1710 }
wolfSSL 16:8e0d178b1d1e 1711 if (!done && (err == MP_OKAY)) {
wolfSSL 16:8e0d178b1d1e 1712 sp_copy(t, r);
wolfSSL 16:8e0d178b1d1e 1713 }
wolfSSL 16:8e0d178b1d1e 1714
wolfSSL 16:8e0d178b1d1e 1715 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1716 if (t != NULL) {
wolfSSL 16:8e0d178b1d1e 1717 XFREE(t, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1718 }
wolfSSL 16:8e0d178b1d1e 1719 #endif
wolfSSL 16:8e0d178b1d1e 1720 }
wolfSSL 16:8e0d178b1d1e 1721 #else
wolfSSL 16:8e0d178b1d1e 1722 if (!done && (err == MP_OKAY)) {
wolfSSL 16:8e0d178b1d1e 1723 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1724 }
wolfSSL 16:8e0d178b1d1e 1725 #endif
wolfSSL 16:8e0d178b1d1e 1726
wolfSSL 16:8e0d178b1d1e 1727 (void)mBits;
wolfSSL 16:8e0d178b1d1e 1728 (void)bBits;
wolfSSL 16:8e0d178b1d1e 1729 (void)eBits;
wolfSSL 16:8e0d178b1d1e 1730
wolfSSL 16:8e0d178b1d1e 1731 return err;
wolfSSL 16:8e0d178b1d1e 1732 }
wolfSSL 16:8e0d178b1d1e 1733
wolfSSL 16:8e0d178b1d1e 1734
wolfSSL 16:8e0d178b1d1e 1735 /* Number of entries in array of number of least significant zero bits. */
wolfSSL 16:8e0d178b1d1e 1736 #define SP_LNZ_CNT 16
wolfSSL 16:8e0d178b1d1e 1737 /* Number of bits the array checks. */
wolfSSL 16:8e0d178b1d1e 1738 #define SP_LNZ_BITS 4
wolfSSL 16:8e0d178b1d1e 1739 /* Mask to apply to check with array. */
wolfSSL 16:8e0d178b1d1e 1740 #define SP_LNZ_MASK 0xf
wolfSSL 16:8e0d178b1d1e 1741 /* Number of least significant zero bits in first SP_LNZ_CNT numbers. */
wolfSSL 16:8e0d178b1d1e 1742 static const int lnz[SP_LNZ_CNT] = {
wolfSSL 16:8e0d178b1d1e 1743 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
wolfSSL 16:8e0d178b1d1e 1744 };
wolfSSL 16:8e0d178b1d1e 1745
wolfSSL 16:8e0d178b1d1e 1746 /* Count the number of least significant zero bits.
wolfSSL 16:8e0d178b1d1e 1747 *
wolfSSL 16:8e0d178b1d1e 1748 * a Number to check
wolfSSL 16:8e0d178b1d1e 1749 * returns the count of least significant zero bits.
wolfSSL 16:8e0d178b1d1e 1750 */
wolfSSL 16:8e0d178b1d1e 1751 static int sp_cnt_lsb(sp_int* a)
wolfSSL 16:8e0d178b1d1e 1752 {
wolfSSL 16:8e0d178b1d1e 1753 int i, j;
wolfSSL 16:8e0d178b1d1e 1754 int cnt = 0;
wolfSSL 16:8e0d178b1d1e 1755 int bc = 0;
wolfSSL 16:8e0d178b1d1e 1756
wolfSSL 16:8e0d178b1d1e 1757 if (!sp_iszero(a)) {
wolfSSL 16:8e0d178b1d1e 1758 for (i = 0; i < a->used && a->dp[i] == 0; i++, cnt += SP_WORD_SIZE) {
wolfSSL 16:8e0d178b1d1e 1759 }
wolfSSL 16:8e0d178b1d1e 1760
wolfSSL 16:8e0d178b1d1e 1761 for (j = 0; j < SP_WORD_SIZE; j += SP_LNZ_BITS) {
wolfSSL 16:8e0d178b1d1e 1762 bc = lnz[(a->dp[i] >> j) & SP_LNZ_MASK];
wolfSSL 16:8e0d178b1d1e 1763 if (bc != 4) {
wolfSSL 16:8e0d178b1d1e 1764 bc += cnt + j;
wolfSSL 16:8e0d178b1d1e 1765 break;
wolfSSL 16:8e0d178b1d1e 1766 }
wolfSSL 16:8e0d178b1d1e 1767 }
wolfSSL 16:8e0d178b1d1e 1768 }
wolfSSL 16:8e0d178b1d1e 1769
wolfSSL 16:8e0d178b1d1e 1770 return bc;
wolfSSL 16:8e0d178b1d1e 1771 }
wolfSSL 16:8e0d178b1d1e 1772
wolfSSL 16:8e0d178b1d1e 1773 /* Miller-Rabin test of "a" to the base of "b" as described in
wolfSSL 16:8e0d178b1d1e 1774 * HAC pp. 139 Algorithm 4.24
wolfSSL 16:8e0d178b1d1e 1775 *
wolfSSL 16:8e0d178b1d1e 1776 * Sets result to 0 if definitely composite or 1 if probably prime.
wolfSSL 16:8e0d178b1d1e 1777 * Randomly the chance of error is no more than 1/4 and often
wolfSSL 16:8e0d178b1d1e 1778 * very much lower.
wolfSSL 16:8e0d178b1d1e 1779 *
wolfSSL 16:8e0d178b1d1e 1780 * a SP integer to check.
wolfSSL 16:8e0d178b1d1e 1781 * b SP integer small prime.
wolfSSL 16:8e0d178b1d1e 1782 * result Whether a is likely prime: MP_YES or MP_NO.
wolfSSL 16:8e0d178b1d1e 1783 * n1 SP integer operand.
wolfSSL 16:8e0d178b1d1e 1784 * y SP integer operand.
wolfSSL 16:8e0d178b1d1e 1785 * r SP integer operand.
wolfSSL 16:8e0d178b1d1e 1786 * returns MP_VAL when a is not 1024, 2048, 1536 or 3072 and MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1787 */
wolfSSL 16:8e0d178b1d1e 1788 static int sp_prime_miller_rabin_ex(sp_int * a, sp_int * b, int *result,
wolfSSL 16:8e0d178b1d1e 1789 sp_int *n1, sp_int *y, sp_int *r)
wolfSSL 16:8e0d178b1d1e 1790 {
wolfSSL 16:8e0d178b1d1e 1791 int s, j;
wolfSSL 16:8e0d178b1d1e 1792 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1793
wolfSSL 16:8e0d178b1d1e 1794 /* default */
wolfSSL 16:8e0d178b1d1e 1795 *result = MP_NO;
wolfSSL 16:8e0d178b1d1e 1796
wolfSSL 16:8e0d178b1d1e 1797 /* ensure b > 1 */
wolfSSL 16:8e0d178b1d1e 1798 if (sp_cmp_d(b, 1) == MP_GT) {
wolfSSL 16:8e0d178b1d1e 1799 /* get n1 = a - 1 */
wolfSSL 16:8e0d178b1d1e 1800 sp_copy(a, n1);
wolfSSL 16:8e0d178b1d1e 1801 sp_sub_d(n1, 1, n1);
wolfSSL 16:8e0d178b1d1e 1802 /* set 2**s * r = n1 */
wolfSSL 16:8e0d178b1d1e 1803 sp_copy(n1, r);
wolfSSL 16:8e0d178b1d1e 1804
wolfSSL 16:8e0d178b1d1e 1805 /* count the number of least significant bits
wolfSSL 16:8e0d178b1d1e 1806 * which are zero
wolfSSL 16:8e0d178b1d1e 1807 */
wolfSSL 16:8e0d178b1d1e 1808 s = sp_cnt_lsb(r);
wolfSSL 16:8e0d178b1d1e 1809
wolfSSL 16:8e0d178b1d1e 1810 /* now divide n - 1 by 2**s */
wolfSSL 16:8e0d178b1d1e 1811 sp_rshb(r, s, r);
wolfSSL 16:8e0d178b1d1e 1812
wolfSSL 16:8e0d178b1d1e 1813 /* compute y = b**r mod a */
wolfSSL 16:8e0d178b1d1e 1814 sp_zero(y);
wolfSSL 16:8e0d178b1d1e 1815
wolfSSL 16:8e0d178b1d1e 1816 err = sp_exptmod(b, r, a, y);
wolfSSL 16:8e0d178b1d1e 1817
wolfSSL 16:8e0d178b1d1e 1818 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1819 /* probably prime until shown otherwise */
wolfSSL 16:8e0d178b1d1e 1820 *result = MP_YES;
wolfSSL 16:8e0d178b1d1e 1821
wolfSSL 16:8e0d178b1d1e 1822 /* if y != 1 and y != n1 do */
wolfSSL 16:8e0d178b1d1e 1823 if (sp_cmp_d(y, 1) != MP_EQ && sp_cmp(y, n1) != MP_EQ) {
wolfSSL 16:8e0d178b1d1e 1824 j = 1;
wolfSSL 16:8e0d178b1d1e 1825 /* while j <= s-1 and y != n1 */
wolfSSL 16:8e0d178b1d1e 1826 while ((j <= (s - 1)) && sp_cmp(y, n1) != MP_EQ) {
wolfSSL 16:8e0d178b1d1e 1827 sp_sqrmod(y, a, y);
wolfSSL 16:8e0d178b1d1e 1828
wolfSSL 16:8e0d178b1d1e 1829 /* if y == 1 then composite */
wolfSSL 16:8e0d178b1d1e 1830 if (sp_cmp_d(y, 1) == MP_EQ) {
wolfSSL 16:8e0d178b1d1e 1831 *result = MP_NO;
wolfSSL 16:8e0d178b1d1e 1832 break;
wolfSSL 16:8e0d178b1d1e 1833 }
wolfSSL 16:8e0d178b1d1e 1834 ++j;
wolfSSL 16:8e0d178b1d1e 1835 }
wolfSSL 16:8e0d178b1d1e 1836
wolfSSL 16:8e0d178b1d1e 1837 /* if y != n1 then composite */
wolfSSL 16:8e0d178b1d1e 1838 if (*result == MP_YES && sp_cmp(y, n1) != MP_EQ)
wolfSSL 16:8e0d178b1d1e 1839 *result = MP_NO;
wolfSSL 16:8e0d178b1d1e 1840 }
wolfSSL 16:8e0d178b1d1e 1841 }
wolfSSL 16:8e0d178b1d1e 1842 }
wolfSSL 16:8e0d178b1d1e 1843
wolfSSL 16:8e0d178b1d1e 1844 return err;
wolfSSL 16:8e0d178b1d1e 1845 }
wolfSSL 16:8e0d178b1d1e 1846
wolfSSL 16:8e0d178b1d1e 1847 /* Miller-Rabin test of "a" to the base of "b" as described in
wolfSSL 16:8e0d178b1d1e 1848 * HAC pp. 139 Algorithm 4.24
wolfSSL 16:8e0d178b1d1e 1849 *
wolfSSL 16:8e0d178b1d1e 1850 * Sets result to 0 if definitely composite or 1 if probably prime.
wolfSSL 16:8e0d178b1d1e 1851 * Randomly the chance of error is no more than 1/4 and often
wolfSSL 16:8e0d178b1d1e 1852 * very much lower.
wolfSSL 16:8e0d178b1d1e 1853 *
wolfSSL 16:8e0d178b1d1e 1854 * a SP integer to check.
wolfSSL 16:8e0d178b1d1e 1855 * b SP integer small prime.
wolfSSL 16:8e0d178b1d1e 1856 * result Whether a is likely prime: MP_YES or MP_NO.
wolfSSL 16:8e0d178b1d1e 1857 * returns MP_MEM when dynamic memory allocation fails, MP_VAL when a is not
wolfSSL 16:8e0d178b1d1e 1858 * 1024, 2048, 1536 or 3072 and MP_OKAY otherwise.
wolfSSL 16:8e0d178b1d1e 1859 */
wolfSSL 16:8e0d178b1d1e 1860 static int sp_prime_miller_rabin(sp_int * a, sp_int * b, int *result)
wolfSSL 16:8e0d178b1d1e 1861 {
wolfSSL 16:8e0d178b1d1e 1862 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1863 #ifndef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1864 sp_int n1[1], y[1], r[1];
wolfSSL 16:8e0d178b1d1e 1865 #else
wolfSSL 16:8e0d178b1d1e 1866 sp_int *n1 = NULL, *y, *r;
wolfSSL 16:8e0d178b1d1e 1867 #endif
wolfSSL 16:8e0d178b1d1e 1868
wolfSSL 16:8e0d178b1d1e 1869 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1870 n1 = (sp_int*)XMALLOC(sizeof(sp_int) * 3, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1871 if (n1 == NULL)
wolfSSL 16:8e0d178b1d1e 1872 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 1873 else {
wolfSSL 16:8e0d178b1d1e 1874 y = &n1[1];
wolfSSL 16:8e0d178b1d1e 1875 r = &n1[2];
wolfSSL 16:8e0d178b1d1e 1876 }
wolfSSL 16:8e0d178b1d1e 1877 #endif
wolfSSL 16:8e0d178b1d1e 1878
wolfSSL 16:8e0d178b1d1e 1879 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 1880 sp_init(n1);
wolfSSL 16:8e0d178b1d1e 1881 sp_init(y);
wolfSSL 16:8e0d178b1d1e 1882 sp_init(r);
wolfSSL 16:8e0d178b1d1e 1883
wolfSSL 16:8e0d178b1d1e 1884 err = sp_prime_miller_rabin_ex(a, b, result, n1, y, r);
wolfSSL 16:8e0d178b1d1e 1885
wolfSSL 16:8e0d178b1d1e 1886 sp_clear(n1);
wolfSSL 16:8e0d178b1d1e 1887 sp_clear(y);
wolfSSL 16:8e0d178b1d1e 1888 sp_clear(r);
wolfSSL 16:8e0d178b1d1e 1889 }
wolfSSL 16:8e0d178b1d1e 1890
wolfSSL 16:8e0d178b1d1e 1891 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1892 if (n1 != NULL)
wolfSSL 16:8e0d178b1d1e 1893 XFREE(n1, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 1894 #endif
wolfSSL 16:8e0d178b1d1e 1895
wolfSSL 16:8e0d178b1d1e 1896 return err;
wolfSSL 16:8e0d178b1d1e 1897 }
wolfSSL 16:8e0d178b1d1e 1898
wolfSSL 16:8e0d178b1d1e 1899 /* Number of pre-computed primes. First n primes. */
wolfSSL 16:8e0d178b1d1e 1900 #define SP_PRIME_SIZE 256
wolfSSL 16:8e0d178b1d1e 1901
wolfSSL 16:8e0d178b1d1e 1902 /* a few primes */
wolfSSL 16:8e0d178b1d1e 1903 static const sp_int_digit primes[SP_PRIME_SIZE] = {
wolfSSL 16:8e0d178b1d1e 1904 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
wolfSSL 16:8e0d178b1d1e 1905 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
wolfSSL 16:8e0d178b1d1e 1906 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
wolfSSL 16:8e0d178b1d1e 1907 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
wolfSSL 16:8e0d178b1d1e 1908 0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
wolfSSL 16:8e0d178b1d1e 1909 0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
wolfSSL 16:8e0d178b1d1e 1910 0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
wolfSSL 16:8e0d178b1d1e 1911 0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
wolfSSL 16:8e0d178b1d1e 1912
wolfSSL 16:8e0d178b1d1e 1913 0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
wolfSSL 16:8e0d178b1d1e 1914 0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
wolfSSL 16:8e0d178b1d1e 1915 0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
wolfSSL 16:8e0d178b1d1e 1916 0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
wolfSSL 16:8e0d178b1d1e 1917 0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
wolfSSL 16:8e0d178b1d1e 1918 0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
wolfSSL 16:8e0d178b1d1e 1919 0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
wolfSSL 16:8e0d178b1d1e 1920 0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
wolfSSL 16:8e0d178b1d1e 1921
wolfSSL 16:8e0d178b1d1e 1922 0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
wolfSSL 16:8e0d178b1d1e 1923 0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
wolfSSL 16:8e0d178b1d1e 1924 0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
wolfSSL 16:8e0d178b1d1e 1925 0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
wolfSSL 16:8e0d178b1d1e 1926 0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
wolfSSL 16:8e0d178b1d1e 1927 0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
wolfSSL 16:8e0d178b1d1e 1928 0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
wolfSSL 16:8e0d178b1d1e 1929 0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
wolfSSL 16:8e0d178b1d1e 1930
wolfSSL 16:8e0d178b1d1e 1931 0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
wolfSSL 16:8e0d178b1d1e 1932 0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
wolfSSL 16:8e0d178b1d1e 1933 0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
wolfSSL 16:8e0d178b1d1e 1934 0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
wolfSSL 16:8e0d178b1d1e 1935 0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
wolfSSL 16:8e0d178b1d1e 1936 0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
wolfSSL 16:8e0d178b1d1e 1937 0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
wolfSSL 16:8e0d178b1d1e 1938 0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
wolfSSL 16:8e0d178b1d1e 1939 };
wolfSSL 16:8e0d178b1d1e 1940
wolfSSL 16:8e0d178b1d1e 1941
wolfSSL 16:8e0d178b1d1e 1942 /* Check whether a is prime.
wolfSSL 16:8e0d178b1d1e 1943 * Checks against a number of small primes and does t iterations of
wolfSSL 16:8e0d178b1d1e 1944 * Miller-Rabin.
wolfSSL 16:8e0d178b1d1e 1945 *
wolfSSL 16:8e0d178b1d1e 1946 * a SP integer to check.
wolfSSL 16:8e0d178b1d1e 1947 * t Number of iterations of Muller-Rabin to perform.
wolfSSL 16:8e0d178b1d1e 1948 * result MP_YES when prime.
wolfSSL 16:8e0d178b1d1e 1949 * MP_NO when not prime.
wolfSSL 16:8e0d178b1d1e 1950 * returns MP_VAL when t is out of range, MP_MEM when dynamic memory allocation
wolfSSL 16:8e0d178b1d1e 1951 * fails and otherwise MP_OKAY.
wolfSSL 16:8e0d178b1d1e 1952 */
wolfSSL 16:8e0d178b1d1e 1953 int sp_prime_is_prime(sp_int *a, int t, int* result)
wolfSSL 16:8e0d178b1d1e 1954 {
wolfSSL 16:8e0d178b1d1e 1955 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1956 int i;
wolfSSL 16:8e0d178b1d1e 1957 int haveRes = 0;
wolfSSL 16:8e0d178b1d1e 1958 #ifndef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1959 sp_int b[1];
wolfSSL 16:8e0d178b1d1e 1960 #else
wolfSSL 16:8e0d178b1d1e 1961 sp_int *b = NULL;
wolfSSL 16:8e0d178b1d1e 1962 #endif
wolfSSL 16:8e0d178b1d1e 1963 sp_int_digit d;
wolfSSL 16:8e0d178b1d1e 1964
wolfSSL 16:8e0d178b1d1e 1965 if (t <= 0 || t > SP_PRIME_SIZE) {
wolfSSL 16:8e0d178b1d1e 1966 *result = MP_NO;
wolfSSL 16:8e0d178b1d1e 1967 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 1968 }
wolfSSL 16:8e0d178b1d1e 1969
wolfSSL 16:8e0d178b1d1e 1970 if (sp_isone(a)) {
wolfSSL 16:8e0d178b1d1e 1971 *result = MP_NO;
wolfSSL 16:8e0d178b1d1e 1972 return MP_OKAY;
wolfSSL 16:8e0d178b1d1e 1973 }
wolfSSL 16:8e0d178b1d1e 1974
wolfSSL 16:8e0d178b1d1e 1975 if (err == MP_OKAY && a->used == 1) {
wolfSSL 16:8e0d178b1d1e 1976 /* check against primes table */
wolfSSL 16:8e0d178b1d1e 1977 for (i = 0; i < SP_PRIME_SIZE; i++) {
wolfSSL 16:8e0d178b1d1e 1978 if (sp_cmp_d(a, primes[i]) == MP_EQ) {
wolfSSL 16:8e0d178b1d1e 1979 *result = MP_YES;
wolfSSL 16:8e0d178b1d1e 1980 haveRes = 1;
wolfSSL 16:8e0d178b1d1e 1981 break;
wolfSSL 16:8e0d178b1d1e 1982 }
wolfSSL 16:8e0d178b1d1e 1983 }
wolfSSL 16:8e0d178b1d1e 1984 }
wolfSSL 16:8e0d178b1d1e 1985
wolfSSL 16:8e0d178b1d1e 1986 if (err == MP_OKAY && !haveRes) {
wolfSSL 16:8e0d178b1d1e 1987 /* do trial division */
wolfSSL 16:8e0d178b1d1e 1988 for (i = 0; i < SP_PRIME_SIZE; i++) {
wolfSSL 16:8e0d178b1d1e 1989 err = sp_mod_d(a, primes[i], &d);
wolfSSL 16:8e0d178b1d1e 1990 if (err != MP_OKAY || d == 0) {
wolfSSL 16:8e0d178b1d1e 1991 *result = MP_NO;
wolfSSL 16:8e0d178b1d1e 1992 haveRes = 1;
wolfSSL 16:8e0d178b1d1e 1993 break;
wolfSSL 16:8e0d178b1d1e 1994 }
wolfSSL 16:8e0d178b1d1e 1995 }
wolfSSL 16:8e0d178b1d1e 1996 }
wolfSSL 16:8e0d178b1d1e 1997
wolfSSL 16:8e0d178b1d1e 1998 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 1999 if (err == MP_OKAY && !haveRes) {
wolfSSL 16:8e0d178b1d1e 2000 b = (sp_int*)XMALLOC(sizeof(sp_int), NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 2001 if (b == NULL)
wolfSSL 16:8e0d178b1d1e 2002 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 2003 }
wolfSSL 16:8e0d178b1d1e 2004 #endif
wolfSSL 16:8e0d178b1d1e 2005
wolfSSL 16:8e0d178b1d1e 2006 if (err == MP_OKAY && !haveRes) {
wolfSSL 16:8e0d178b1d1e 2007 /* now do 't' miller rabins */
wolfSSL 16:8e0d178b1d1e 2008 sp_init(b);
wolfSSL 16:8e0d178b1d1e 2009 for (i = 0; i < t; i++) {
wolfSSL 16:8e0d178b1d1e 2010 sp_set(b, primes[i]);
wolfSSL 16:8e0d178b1d1e 2011 err = sp_prime_miller_rabin(a, b, result);
wolfSSL 16:8e0d178b1d1e 2012 if (err != MP_OKAY || *result == MP_NO)
wolfSSL 16:8e0d178b1d1e 2013 break;
wolfSSL 16:8e0d178b1d1e 2014 }
wolfSSL 16:8e0d178b1d1e 2015 }
wolfSSL 16:8e0d178b1d1e 2016
wolfSSL 16:8e0d178b1d1e 2017 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 2018 if (b != NULL)
wolfSSL 16:8e0d178b1d1e 2019 XFREE(b, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 2020 #endif
wolfSSL 16:8e0d178b1d1e 2021
wolfSSL 16:8e0d178b1d1e 2022 return err;
wolfSSL 16:8e0d178b1d1e 2023 }
wolfSSL 16:8e0d178b1d1e 2024
wolfSSL 16:8e0d178b1d1e 2025 /* Check whether a is prime.
wolfSSL 16:8e0d178b1d1e 2026 * Checks against a number of small primes and does t iterations of
wolfSSL 16:8e0d178b1d1e 2027 * Miller-Rabin.
wolfSSL 16:8e0d178b1d1e 2028 *
wolfSSL 16:8e0d178b1d1e 2029 * a SP integer to check.
wolfSSL 16:8e0d178b1d1e 2030 * t Number of iterations of Muller-Rabin to perform.
wolfSSL 16:8e0d178b1d1e 2031 * result MP_YES when prime.
wolfSSL 16:8e0d178b1d1e 2032 * MP_NO when not prime.
wolfSSL 16:8e0d178b1d1e 2033 * rng Random number generator.
wolfSSL 16:8e0d178b1d1e 2034 * returns MP_VAL when t is out of range, MP_MEM when dynamic memory allocation
wolfSSL 16:8e0d178b1d1e 2035 * fails and otherwise MP_OKAY.
wolfSSL 16:8e0d178b1d1e 2036 */
wolfSSL 16:8e0d178b1d1e 2037 int sp_prime_is_prime_ex(sp_int* a, int t, int* result, WC_RNG* rng)
wolfSSL 16:8e0d178b1d1e 2038 {
wolfSSL 16:8e0d178b1d1e 2039 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 2040 int ret = MP_YES;
wolfSSL 16:8e0d178b1d1e 2041 int haveRes = 0;
wolfSSL 16:8e0d178b1d1e 2042 int i;
wolfSSL 16:8e0d178b1d1e 2043 #ifndef WC_NO_RNG
wolfSSL 16:8e0d178b1d1e 2044 #ifndef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 2045 sp_int b[1], c[1], n1[1], y[1], r[1];
wolfSSL 16:8e0d178b1d1e 2046 #else
wolfSSL 16:8e0d178b1d1e 2047 sp_int *b = NULL, *c = NULL, *n1 = NULL, *y = NULL, *r = NULL;
wolfSSL 16:8e0d178b1d1e 2048 #endif
wolfSSL 16:8e0d178b1d1e 2049 word32 baseSz;
wolfSSL 16:8e0d178b1d1e 2050 #endif
wolfSSL 16:8e0d178b1d1e 2051
wolfSSL 16:8e0d178b1d1e 2052 if (a == NULL || result == NULL || rng == NULL)
wolfSSL 16:8e0d178b1d1e 2053 err = MP_VAL;
wolfSSL 16:8e0d178b1d1e 2054
wolfSSL 16:8e0d178b1d1e 2055 if (sp_isone(a)) {
wolfSSL 16:8e0d178b1d1e 2056 *result = MP_NO;
wolfSSL 16:8e0d178b1d1e 2057 return MP_OKAY;
wolfSSL 16:8e0d178b1d1e 2058 }
wolfSSL 16:8e0d178b1d1e 2059
wolfSSL 16:8e0d178b1d1e 2060 if (err == MP_OKAY && a->used == 1) {
wolfSSL 16:8e0d178b1d1e 2061 /* check against primes table */
wolfSSL 16:8e0d178b1d1e 2062 for (i = 0; i < SP_PRIME_SIZE; i++) {
wolfSSL 16:8e0d178b1d1e 2063 if (sp_cmp_d(a, primes[i]) == MP_EQ) {
wolfSSL 16:8e0d178b1d1e 2064 ret = MP_YES;
wolfSSL 16:8e0d178b1d1e 2065 haveRes = 1;
wolfSSL 16:8e0d178b1d1e 2066 break;
wolfSSL 16:8e0d178b1d1e 2067 }
wolfSSL 16:8e0d178b1d1e 2068 }
wolfSSL 16:8e0d178b1d1e 2069 }
wolfSSL 16:8e0d178b1d1e 2070
wolfSSL 16:8e0d178b1d1e 2071 if (err == MP_OKAY && !haveRes) {
wolfSSL 16:8e0d178b1d1e 2072 sp_int_digit d;
wolfSSL 16:8e0d178b1d1e 2073
wolfSSL 16:8e0d178b1d1e 2074 /* do trial division */
wolfSSL 16:8e0d178b1d1e 2075 for (i = 0; i < SP_PRIME_SIZE; i++) {
wolfSSL 16:8e0d178b1d1e 2076 err = sp_mod_d(a, primes[i], &d);
wolfSSL 16:8e0d178b1d1e 2077 if (err != MP_OKAY || d == 0) {
wolfSSL 16:8e0d178b1d1e 2078 ret = MP_NO;
wolfSSL 16:8e0d178b1d1e 2079 haveRes = 1;
wolfSSL 16:8e0d178b1d1e 2080 break;
wolfSSL 16:8e0d178b1d1e 2081 }
wolfSSL 16:8e0d178b1d1e 2082 }
wolfSSL 16:8e0d178b1d1e 2083 }
wolfSSL 16:8e0d178b1d1e 2084
wolfSSL 16:8e0d178b1d1e 2085 #ifndef WC_NO_RNG
wolfSSL 16:8e0d178b1d1e 2086 /* now do a miller rabin with up to t random numbers, this should
wolfSSL 16:8e0d178b1d1e 2087 * give a (1/4)^t chance of a false prime. */
wolfSSL 16:8e0d178b1d1e 2088 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 2089 if (err == MP_OKAY && !haveRes) {
wolfSSL 16:8e0d178b1d1e 2090 b = (sp_int*)XMALLOC(sizeof(sp_int) * 5, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 2091 if (b == NULL) {
wolfSSL 16:8e0d178b1d1e 2092 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 2093 }
wolfSSL 16:8e0d178b1d1e 2094 else {
wolfSSL 16:8e0d178b1d1e 2095 c = &b[1]; n1 = &b[2]; y= &b[3]; r = &b[4];
wolfSSL 16:8e0d178b1d1e 2096 }
wolfSSL 16:8e0d178b1d1e 2097 }
wolfSSL 16:8e0d178b1d1e 2098 #endif
wolfSSL 16:8e0d178b1d1e 2099
wolfSSL 16:8e0d178b1d1e 2100 if (err == MP_OKAY && !haveRes) {
wolfSSL 16:8e0d178b1d1e 2101 sp_init(b);
wolfSSL 16:8e0d178b1d1e 2102 sp_init(c);
wolfSSL 16:8e0d178b1d1e 2103 sp_init(n1);
wolfSSL 16:8e0d178b1d1e 2104 sp_init(y);
wolfSSL 16:8e0d178b1d1e 2105 sp_init(r);
wolfSSL 16:8e0d178b1d1e 2106
wolfSSL 16:8e0d178b1d1e 2107 err = sp_sub_d(a, 2, c);
wolfSSL 16:8e0d178b1d1e 2108 }
wolfSSL 16:8e0d178b1d1e 2109
wolfSSL 16:8e0d178b1d1e 2110 if (err == MP_OKAY && !haveRes) {
wolfSSL 16:8e0d178b1d1e 2111 baseSz = (sp_count_bits(a) + 7) / 8;
wolfSSL 16:8e0d178b1d1e 2112
wolfSSL 16:8e0d178b1d1e 2113 while (t > 0) {
wolfSSL 16:8e0d178b1d1e 2114 err = wc_RNG_GenerateBlock(rng, (byte*)b->dp, baseSz);
wolfSSL 16:8e0d178b1d1e 2115 if (err != MP_OKAY)
wolfSSL 16:8e0d178b1d1e 2116 break;
wolfSSL 16:8e0d178b1d1e 2117 b->used = a->used;
wolfSSL 16:8e0d178b1d1e 2118
wolfSSL 16:8e0d178b1d1e 2119 if (sp_cmp_d(b, 2) != MP_GT || sp_cmp(b, c) != MP_LT)
wolfSSL 16:8e0d178b1d1e 2120 continue;
wolfSSL 16:8e0d178b1d1e 2121
wolfSSL 16:8e0d178b1d1e 2122 err = sp_prime_miller_rabin_ex(a, b, &ret, n1, y, r);
wolfSSL 16:8e0d178b1d1e 2123 if (err != MP_OKAY || ret == MP_NO)
wolfSSL 16:8e0d178b1d1e 2124 break;
wolfSSL 16:8e0d178b1d1e 2125
wolfSSL 16:8e0d178b1d1e 2126 t--;
wolfSSL 16:8e0d178b1d1e 2127 }
wolfSSL 16:8e0d178b1d1e 2128
wolfSSL 16:8e0d178b1d1e 2129 sp_clear(n1);
wolfSSL 16:8e0d178b1d1e 2130 sp_clear(y);
wolfSSL 16:8e0d178b1d1e 2131 sp_clear(r);
wolfSSL 16:8e0d178b1d1e 2132 sp_clear(b);
wolfSSL 16:8e0d178b1d1e 2133 sp_clear(c);
wolfSSL 16:8e0d178b1d1e 2134 }
wolfSSL 16:8e0d178b1d1e 2135
wolfSSL 16:8e0d178b1d1e 2136 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 2137 if (b != NULL)
wolfSSL 16:8e0d178b1d1e 2138 XFREE(b, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 2139 #endif
wolfSSL 16:8e0d178b1d1e 2140 #else
wolfSSL 16:8e0d178b1d1e 2141 (void)t;
wolfSSL 16:8e0d178b1d1e 2142 #endif /* !WC_NO_RNG */
wolfSSL 16:8e0d178b1d1e 2143
wolfSSL 16:8e0d178b1d1e 2144 *result = ret;
wolfSSL 16:8e0d178b1d1e 2145 return err;
wolfSSL 16:8e0d178b1d1e 2146 }
wolfSSL 16:8e0d178b1d1e 2147
wolfSSL 16:8e0d178b1d1e 2148 #ifndef NO_DH
wolfSSL 16:8e0d178b1d1e 2149 int sp_exch(sp_int* a, sp_int* b)
wolfSSL 16:8e0d178b1d1e 2150 {
wolfSSL 16:8e0d178b1d1e 2151 int err = MP_OKAY;
wolfSSL 16:8e0d178b1d1e 2152 #ifndef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 2153 sp_int t[1];
wolfSSL 16:8e0d178b1d1e 2154 #else
wolfSSL 16:8e0d178b1d1e 2155 sp_int *t = NULL;
wolfSSL 16:8e0d178b1d1e 2156 #endif
wolfSSL 16:8e0d178b1d1e 2157
wolfSSL 16:8e0d178b1d1e 2158 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 2159 t = (sp_int*)XMALLOC(sizeof(sp_int), NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 2160 if (t == NULL)
wolfSSL 16:8e0d178b1d1e 2161 err = MP_MEM;
wolfSSL 16:8e0d178b1d1e 2162 #endif
wolfSSL 16:8e0d178b1d1e 2163
wolfSSL 16:8e0d178b1d1e 2164 if (err == MP_OKAY) {
wolfSSL 16:8e0d178b1d1e 2165 *t = *a;
wolfSSL 16:8e0d178b1d1e 2166 *a = *b;
wolfSSL 16:8e0d178b1d1e 2167 *b = *t;
wolfSSL 16:8e0d178b1d1e 2168 }
wolfSSL 16:8e0d178b1d1e 2169
wolfSSL 16:8e0d178b1d1e 2170 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 16:8e0d178b1d1e 2171 if (t != NULL)
wolfSSL 16:8e0d178b1d1e 2172 XFREE(t, NULL, DYNAMIC_TYPE_BIGINT);
wolfSSL 16:8e0d178b1d1e 2173 #endif
wolfSSL 16:8e0d178b1d1e 2174 return MP_OKAY;
wolfSSL 16:8e0d178b1d1e 2175 }
wolfSSL 16:8e0d178b1d1e 2176 #endif
wolfSSL 16:8e0d178b1d1e 2177 #endif
wolfSSL 16:8e0d178b1d1e 2178
wolfSSL 16:8e0d178b1d1e 2179 #if defined(WOLFSSL_KEY_GEN) && !defined(NO_RSA)
wolfSSL 16:8e0d178b1d1e 2180 /* Multiply a by digit n and put result into r. r = a * n
wolfSSL 16:8e0d178b1d1e 2181 *
wolfSSL 16:8e0d178b1d1e 2182 * a SP integer to be multiplied.
wolfSSL 16:8e0d178b1d1e 2183 * n Number to multiply by.
wolfSSL 16:8e0d178b1d1e 2184 * r SP integer result.
wolfSSL 16:8e0d178b1d1e 2185 * returns MP_OKAY always.
wolfSSL 16:8e0d178b1d1e 2186 */
wolfSSL 16:8e0d178b1d1e 2187 int sp_mul_d(sp_int* a, sp_int_digit n, sp_int* r)
wolfSSL 16:8e0d178b1d1e 2188 {
wolfSSL 16:8e0d178b1d1e 2189 _sp_mul_d(a, n, r, 0);
wolfSSL 14:167253f4e170 2190 return MP_OKAY;
wolfSSL 14:167253f4e170 2191 }
wolfSSL 14:167253f4e170 2192 #endif
wolfSSL 14:167253f4e170 2193
wolfSSL 14:167253f4e170 2194 /* Returns the run time settings.
wolfSSL 14:167253f4e170 2195 *
wolfSSL 14:167253f4e170 2196 * returns the settings value.
wolfSSL 14:167253f4e170 2197 */
wolfSSL 14:167253f4e170 2198 word32 CheckRunTimeSettings(void)
wolfSSL 14:167253f4e170 2199 {
wolfSSL 14:167253f4e170 2200 return CTC_SETTINGS;
wolfSSL 14:167253f4e170 2201 }
wolfSSL 14:167253f4e170 2202
wolfSSL 16:8e0d178b1d1e 2203 #endif /* WOLFSSL_SP_MATH */
wolfSSL 14:167253f4e170 2204