Xuyi Wang / wolfSSL

Important changes to repositories hosted on mbed.com

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

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

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

Dependents:   OS

wolfcrypt/src/sp_int.c@16:048e5e270a58, 2019-11-19 (annotated)

Committer:
sPymbed
Date:
Tue Nov 19 14:32:16 2019 +0000
Revision:
16:048e5e270a58
Parent:
14:167253f4e170 
working ssl

Who changed what in which revision?

UserRevisionLine numberNew contents of line
wolfSSL 14:167253f4e170 1 /* sp_int.c
wolfSSL 14:167253f4e170 2 *
wolfSSL 14:167253f4e170 3 * Copyright (C) 2006-2017 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 14:167253f4e170 37
wolfSSL 14:167253f4e170 38 #ifdef WOLFSSL_SP_MATH
wolfSSL 14:167253f4e170 39
wolfSSL 14:167253f4e170 40 #include <wolfssl/wolfcrypt/sp_int.h>
wolfSSL 14:167253f4e170 41
wolfSSL 14:167253f4e170 42 /* Initialize the big number to be zero.
wolfSSL 14:167253f4e170 43 *
wolfSSL 14:167253f4e170 44 * a SP integer.
wolfSSL 14:167253f4e170 45 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 46 */
wolfSSL 14:167253f4e170 47 int sp_init(sp_int* a)
wolfSSL 14:167253f4e170 48 {
wolfSSL 14:167253f4e170 49 a->used = 0;
wolfSSL 14:167253f4e170 50 a->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 51
wolfSSL 14:167253f4e170 52 return MP_OKAY;
wolfSSL 14:167253f4e170 53 }
wolfSSL 14:167253f4e170 54
wolfSSL 14:167253f4e170 55 /* Initialize up to six big numbers to be zero.
wolfSSL 14:167253f4e170 56 *
wolfSSL 14:167253f4e170 57 * a SP integer.
wolfSSL 14:167253f4e170 58 * b SP integer.
wolfSSL 14:167253f4e170 59 * c SP integer.
wolfSSL 14:167253f4e170 60 * d SP integer.
wolfSSL 14:167253f4e170 61 * e SP integer.
wolfSSL 14:167253f4e170 62 * f SP integer.
wolfSSL 14:167253f4e170 63 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 64 */
wolfSSL 14:167253f4e170 65 int sp_init_multi(sp_int* a, sp_int* b, sp_int* c, sp_int* d, sp_int* e,
wolfSSL 14:167253f4e170 66 sp_int* f)
wolfSSL 14:167253f4e170 67 {
wolfSSL 14:167253f4e170 68 if (a != NULL) {
wolfSSL 14:167253f4e170 69 a->used = 0;
wolfSSL 14:167253f4e170 70 a->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 71 }
wolfSSL 14:167253f4e170 72 if (b != NULL) {
wolfSSL 14:167253f4e170 73 b->used = 0;
wolfSSL 14:167253f4e170 74 b->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 75 }
wolfSSL 14:167253f4e170 76 if (c != NULL) {
wolfSSL 14:167253f4e170 77 c->used = 0;
wolfSSL 14:167253f4e170 78 c->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 79 }
wolfSSL 14:167253f4e170 80 if (d != NULL) {
wolfSSL 14:167253f4e170 81 d->used = 0;
wolfSSL 14:167253f4e170 82 d->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 83 }
wolfSSL 14:167253f4e170 84 if (e != NULL) {
wolfSSL 14:167253f4e170 85 e->used = 0;
wolfSSL 14:167253f4e170 86 e->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 87 }
wolfSSL 14:167253f4e170 88 if (f != NULL) {
wolfSSL 14:167253f4e170 89 f->used = 0;
wolfSSL 14:167253f4e170 90 f->size = SP_INT_DIGITS;
wolfSSL 14:167253f4e170 91 }
wolfSSL 14:167253f4e170 92
wolfSSL 14:167253f4e170 93 return MP_OKAY;
wolfSSL 14:167253f4e170 94 }
wolfSSL 14:167253f4e170 95
wolfSSL 14:167253f4e170 96 /* Clear the data from the big number and set to zero.
wolfSSL 14:167253f4e170 97 *
wolfSSL 14:167253f4e170 98 * a SP integer.
wolfSSL 14:167253f4e170 99 */
wolfSSL 14:167253f4e170 100 void sp_clear(sp_int* a)
wolfSSL 14:167253f4e170 101 {
wolfSSL 14:167253f4e170 102 int i;
wolfSSL 14:167253f4e170 103
wolfSSL 14:167253f4e170 104 for (i=0; i<a->used; i++)
wolfSSL 14:167253f4e170 105 a->dp[i] = 0;
wolfSSL 14:167253f4e170 106 a->used = 0;
wolfSSL 14:167253f4e170 107 }
wolfSSL 14:167253f4e170 108
wolfSSL 14:167253f4e170 109 /* Calculate the number of 8-bit values required to represent the big number.
wolfSSL 14:167253f4e170 110 *
wolfSSL 14:167253f4e170 111 * a SP integer.
wolfSSL 14:167253f4e170 112 * returns the count.
wolfSSL 14:167253f4e170 113 */
wolfSSL 14:167253f4e170 114 int sp_unsigned_bin_size(sp_int* a)
wolfSSL 14:167253f4e170 115 {
wolfSSL 14:167253f4e170 116 int size = sp_count_bits(a);
wolfSSL 14:167253f4e170 117 return (size + 7) / 8;
wolfSSL 14:167253f4e170 118 }
wolfSSL 14:167253f4e170 119
wolfSSL 14:167253f4e170 120 /* Convert a number as an array of bytes in big-endian format to a big number.
wolfSSL 14:167253f4e170 121 *
wolfSSL 14:167253f4e170 122 * a SP integer.
wolfSSL 14:167253f4e170 123 * in Array of bytes.
wolfSSL 14:167253f4e170 124 * inSz Number of data bytes in array.
wolfSSL 14:167253f4e170 125 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 126 */
wolfSSL 14:167253f4e170 127 int sp_read_unsigned_bin(sp_int* a, const byte* in, word32 inSz)
wolfSSL 14:167253f4e170 128 {
wolfSSL 14:167253f4e170 129 int i, j = 0, s = 0;
wolfSSL 14:167253f4e170 130
wolfSSL 14:167253f4e170 131 a->dp[0] = 0;
wolfSSL 14:167253f4e170 132 for (i = inSz-1; i >= 0; i--) {
wolfSSL 14:167253f4e170 133 a->dp[j] |= ((sp_int_digit)in[i]) << s;
wolfSSL 14:167253f4e170 134 if (s == DIGIT_BIT - 8) {
wolfSSL 14:167253f4e170 135 a->dp[++j] = 0;
wolfSSL 14:167253f4e170 136 s = 0;
wolfSSL 14:167253f4e170 137 }
wolfSSL 14:167253f4e170 138 else if (s > DIGIT_BIT - 8) {
wolfSSL 14:167253f4e170 139 s = DIGIT_BIT - s;
wolfSSL 14:167253f4e170 140 if (j + 1 >= a->size)
wolfSSL 14:167253f4e170 141 break;
wolfSSL 14:167253f4e170 142 a->dp[++j] = in[i] >> s;
wolfSSL 14:167253f4e170 143 s = 8 - s;
wolfSSL 14:167253f4e170 144 }
wolfSSL 14:167253f4e170 145 else
wolfSSL 14:167253f4e170 146 s += 8;
wolfSSL 14:167253f4e170 147 }
wolfSSL 14:167253f4e170 148
wolfSSL 14:167253f4e170 149 a->used = j + 1;
wolfSSL 14:167253f4e170 150 if (a->dp[j] == 0)
wolfSSL 14:167253f4e170 151 a->used--;
wolfSSL 14:167253f4e170 152
wolfSSL 14:167253f4e170 153 for (j++; j < a->size; j++)
wolfSSL 14:167253f4e170 154 a->dp[j] = 0;
wolfSSL 14:167253f4e170 155
wolfSSL 14:167253f4e170 156 return MP_OKAY;
wolfSSL 14:167253f4e170 157 }
wolfSSL 14:167253f4e170 158
wolfSSL 14:167253f4e170 159 /* Convert a number as string in big-endian format to a big number.
wolfSSL 14:167253f4e170 160 * Only supports base-16 (hexadecimal).
wolfSSL 14:167253f4e170 161 * Negative values not supported.
wolfSSL 14:167253f4e170 162 *
wolfSSL 14:167253f4e170 163 * a SP integer.
wolfSSL 14:167253f4e170 164 * in NUL terminated string.
wolfSSL 14:167253f4e170 165 * radix Number of values in a digit.
wolfSSL 14:167253f4e170 166 * returns BAD_FUNC_ARG when radix not supported or value is negative, MP_VAL
wolfSSL 14:167253f4e170 167 * when a character is not valid and MP_OKAY otherwise.
wolfSSL 14:167253f4e170 168 */
wolfSSL 14:167253f4e170 169 int sp_read_radix(sp_int* a, const char* in, int radix)
wolfSSL 14:167253f4e170 170 {
wolfSSL 14:167253f4e170 171 int i, j, k;
wolfSSL 14:167253f4e170 172 char ch;
wolfSSL 14:167253f4e170 173
wolfSSL 14:167253f4e170 174 if (radix != 16)
wolfSSL 14:167253f4e170 175 return BAD_FUNC_ARG;
wolfSSL 14:167253f4e170 176
wolfSSL 14:167253f4e170 177 if (*in == '-') {
wolfSSL 14:167253f4e170 178 return BAD_FUNC_ARG;
wolfSSL 14:167253f4e170 179 }
wolfSSL 14:167253f4e170 180
wolfSSL 14:167253f4e170 181 j = 0;
wolfSSL 14:167253f4e170 182 k = 0;
wolfSSL 14:167253f4e170 183 a->dp[0] = 0;
wolfSSL 14:167253f4e170 184 for (i = (int)(XSTRLEN(in) - 1); i >= 0; i--) {
wolfSSL 14:167253f4e170 185 ch = in[i];
wolfSSL 14:167253f4e170 186 if (ch >= '0' && ch <= '9')
wolfSSL 14:167253f4e170 187 ch -= '0';
wolfSSL 14:167253f4e170 188 else if (ch >= 'A' && ch <= 'F')
wolfSSL 14:167253f4e170 189 ch -= 'A' - 10;
wolfSSL 14:167253f4e170 190 else if (ch >= 'a' && ch <= 'f')
wolfSSL 14:167253f4e170 191 ch -= 'a' - 10;
wolfSSL 14:167253f4e170 192 else
wolfSSL 14:167253f4e170 193 return MP_VAL;
wolfSSL 14:167253f4e170 194
wolfSSL 14:167253f4e170 195 a->dp[k] |= ((sp_int_digit)ch) << j;
wolfSSL 14:167253f4e170 196 j += 4;
wolfSSL 14:167253f4e170 197 if (j == DIGIT_BIT && k < SP_INT_DIGITS)
wolfSSL 14:167253f4e170 198 a->dp[++k] = 0;
wolfSSL 14:167253f4e170 199 j &= DIGIT_BIT - 1;
wolfSSL 14:167253f4e170 200 }
wolfSSL 14:167253f4e170 201
wolfSSL 14:167253f4e170 202 a->used = k + 1;
wolfSSL 14:167253f4e170 203 if (a->dp[k] == 0)
wolfSSL 14:167253f4e170 204 a->used--;
wolfSSL 14:167253f4e170 205
wolfSSL 14:167253f4e170 206 for (k++; k < a->size; k++)
wolfSSL 14:167253f4e170 207 a->dp[k] = 0;
wolfSSL 14:167253f4e170 208
wolfSSL 14:167253f4e170 209 return MP_OKAY;
wolfSSL 14:167253f4e170 210 }
wolfSSL 14:167253f4e170 211
wolfSSL 14:167253f4e170 212 /* Compare two big numbers.
wolfSSL 14:167253f4e170 213 *
wolfSSL 14:167253f4e170 214 * a SP integer.
wolfSSL 14:167253f4e170 215 * b SP integer.
wolfSSL 14:167253f4e170 216 * returns MP_GT if a is greater than b, MP_LT if a is less than b and MP_EQ
wolfSSL 14:167253f4e170 217 * when a equals b.
wolfSSL 14:167253f4e170 218 */
wolfSSL 14:167253f4e170 219 int sp_cmp(sp_int* a, sp_int* b)
wolfSSL 14:167253f4e170 220 {
wolfSSL 14:167253f4e170 221 int i;
wolfSSL 14:167253f4e170 222
wolfSSL 14:167253f4e170 223 if (a->used > b->used)
wolfSSL 14:167253f4e170 224 return MP_GT;
wolfSSL 14:167253f4e170 225 else if (a->used < b->used)
wolfSSL 14:167253f4e170 226 return MP_LT;
wolfSSL 14:167253f4e170 227
wolfSSL 14:167253f4e170 228 for (i = a->used - 1; i >= 0; i--) {
wolfSSL 14:167253f4e170 229 if (a->dp[i] > b->dp[i])
wolfSSL 14:167253f4e170 230 return MP_GT;
wolfSSL 14:167253f4e170 231 else if (a->dp[i] < b->dp[i])
wolfSSL 14:167253f4e170 232 return MP_LT;
wolfSSL 14:167253f4e170 233 }
wolfSSL 14:167253f4e170 234 return MP_EQ;
wolfSSL 14:167253f4e170 235 }
wolfSSL 14:167253f4e170 236
wolfSSL 14:167253f4e170 237 /* Count the number of bits in the big number.
wolfSSL 14:167253f4e170 238 *
wolfSSL 14:167253f4e170 239 * a SP integer.
wolfSSL 14:167253f4e170 240 * returns the number of bits.
wolfSSL 14:167253f4e170 241 */
wolfSSL 14:167253f4e170 242 int sp_count_bits(sp_int* a)
wolfSSL 14:167253f4e170 243 {
wolfSSL 14:167253f4e170 244 int r = 0;
wolfSSL 14:167253f4e170 245 sp_int_digit d;
wolfSSL 14:167253f4e170 246
wolfSSL 14:167253f4e170 247 r = a->used - 1;
wolfSSL 14:167253f4e170 248 while (r >= 0 && a->dp[r] == 0)
wolfSSL 14:167253f4e170 249 r--;
wolfSSL 14:167253f4e170 250 if (r < 0)
wolfSSL 14:167253f4e170 251 r = 0;
wolfSSL 14:167253f4e170 252 else {
wolfSSL 14:167253f4e170 253 d = a->dp[r];
wolfSSL 14:167253f4e170 254 r *= DIGIT_BIT;
wolfSSL 14:167253f4e170 255 while (d != 0) {
wolfSSL 14:167253f4e170 256 r++;
wolfSSL 14:167253f4e170 257 d >>= 1;
wolfSSL 14:167253f4e170 258 }
wolfSSL 14:167253f4e170 259 }
wolfSSL 14:167253f4e170 260
wolfSSL 14:167253f4e170 261 return r;
wolfSSL 14:167253f4e170 262 }
wolfSSL 14:167253f4e170 263
wolfSSL 14:167253f4e170 264 /* Determine if the most significant byte of the encoded big number as the top
wolfSSL 14:167253f4e170 265 * bit set.
wolfSSL 14:167253f4e170 266 *
wolfSSL 14:167253f4e170 267 * a SP integer.
wolfSSL 14:167253f4e170 268 * returns 1 when the top bit is set and 0 otherwise.
wolfSSL 14:167253f4e170 269 */
wolfSSL 14:167253f4e170 270 int sp_leading_bit(sp_int* a)
wolfSSL 14:167253f4e170 271 {
wolfSSL 14:167253f4e170 272 int bit = 0;
wolfSSL 14:167253f4e170 273 sp_int_digit d;
wolfSSL 14:167253f4e170 274
wolfSSL 14:167253f4e170 275 if (a->used > 0) {
wolfSSL 14:167253f4e170 276 d = a->dp[a->used - 1];
wolfSSL 14:167253f4e170 277 while (d > (sp_int_digit)0xff)
wolfSSL 14:167253f4e170 278 d >>= 8;
wolfSSL 14:167253f4e170 279 bit = (int)(d >> 7);
wolfSSL 14:167253f4e170 280 }
wolfSSL 14:167253f4e170 281
wolfSSL 14:167253f4e170 282 return bit;
wolfSSL 14:167253f4e170 283 }
wolfSSL 14:167253f4e170 284
wolfSSL 14:167253f4e170 285 /* Convert the big number to an array of bytes in big-endian format.
wolfSSL 14:167253f4e170 286 * The array must be large enough for encoded number - use mp_unsigned_bin_size
wolfSSL 14:167253f4e170 287 * to calculate the number of bytes required.
wolfSSL 14:167253f4e170 288 *
wolfSSL 14:167253f4e170 289 * a SP integer.
wolfSSL 14:167253f4e170 290 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 291 */
wolfSSL 14:167253f4e170 292 int sp_to_unsigned_bin(sp_int* a, byte* out)
wolfSSL 14:167253f4e170 293 {
wolfSSL 14:167253f4e170 294 int i, j, b;
wolfSSL 14:167253f4e170 295
wolfSSL 14:167253f4e170 296 j = sp_unsigned_bin_size(a) - 1;
wolfSSL 14:167253f4e170 297 for (i=0; j>=0; i++) {
wolfSSL 14:167253f4e170 298 for (b = 0; b < SP_WORD_SIZE; b += 8) {
wolfSSL 14:167253f4e170 299 out[j--] = a->dp[i] >> b;
wolfSSL 14:167253f4e170 300 if (j < 0)
wolfSSL 14:167253f4e170 301 break;
wolfSSL 14:167253f4e170 302 }
wolfSSL 14:167253f4e170 303 }
wolfSSL 14:167253f4e170 304
wolfSSL 14:167253f4e170 305 return MP_OKAY;
wolfSSL 14:167253f4e170 306 }
wolfSSL 14:167253f4e170 307
wolfSSL 14:167253f4e170 308 /* Ensure the data in the big number is zeroed.
wolfSSL 14:167253f4e170 309 *
wolfSSL 14:167253f4e170 310 * a SP integer.
wolfSSL 14:167253f4e170 311 */
wolfSSL 14:167253f4e170 312 void sp_forcezero(sp_int* a)
wolfSSL 14:167253f4e170 313 {
wolfSSL 14:167253f4e170 314 ForceZero(a->dp, a->used * sizeof(sp_int_digit));
wolfSSL 14:167253f4e170 315 a->used = 0;
wolfSSL 14:167253f4e170 316 }
wolfSSL 14:167253f4e170 317
wolfSSL 14:167253f4e170 318 /* Copy value of big number a into b.
wolfSSL 14:167253f4e170 319 *
wolfSSL 14:167253f4e170 320 * a SP integer.
wolfSSL 14:167253f4e170 321 * b SP integer.
wolfSSL 14:167253f4e170 322 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 323 */
wolfSSL 14:167253f4e170 324 int sp_copy(sp_int* a, sp_int* b)
wolfSSL 14:167253f4e170 325 {
wolfSSL 14:167253f4e170 326 if (a != b) {
wolfSSL 14:167253f4e170 327 XMEMCPY(b->dp, a->dp, a->used * sizeof(sp_int_digit));
wolfSSL 14:167253f4e170 328 b->used = a->used;
wolfSSL 14:167253f4e170 329 }
wolfSSL 14:167253f4e170 330 return MP_OKAY;
wolfSSL 14:167253f4e170 331 }
wolfSSL 14:167253f4e170 332
wolfSSL 14:167253f4e170 333 /* Set the big number to be the value of the digit.
wolfSSL 14:167253f4e170 334 *
wolfSSL 14:167253f4e170 335 * a SP integer.
wolfSSL 14:167253f4e170 336 * d Digit to be set.
wolfSSL 14:167253f4e170 337 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 338 */
wolfSSL 14:167253f4e170 339 int sp_set(sp_int* a, sp_int_digit d)
wolfSSL 14:167253f4e170 340 {
wolfSSL 14:167253f4e170 341 a->dp[0] = d;
wolfSSL 14:167253f4e170 342 a->used = 1;
wolfSSL 14:167253f4e170 343 return MP_OKAY;
wolfSSL 14:167253f4e170 344 }
wolfSSL 14:167253f4e170 345
wolfSSL 14:167253f4e170 346 /* Checks whether the value of the big number is zero.
wolfSSL 14:167253f4e170 347 *
wolfSSL 14:167253f4e170 348 * a SP integer.
wolfSSL 14:167253f4e170 349 * returns 1 when value is zero and 0 otherwise.
wolfSSL 14:167253f4e170 350 */
wolfSSL 14:167253f4e170 351 int sp_iszero(sp_int* a)
wolfSSL 14:167253f4e170 352 {
wolfSSL 14:167253f4e170 353 return a->used == 0;
wolfSSL 14:167253f4e170 354 }
wolfSSL 14:167253f4e170 355
wolfSSL 14:167253f4e170 356 /* Recalculate the number of digits used.
wolfSSL 14:167253f4e170 357 *
wolfSSL 14:167253f4e170 358 * a SP integer.
wolfSSL 14:167253f4e170 359 */
wolfSSL 14:167253f4e170 360 void sp_clamp(sp_int* a)
wolfSSL 14:167253f4e170 361 {
wolfSSL 14:167253f4e170 362 int i;
wolfSSL 14:167253f4e170 363
wolfSSL 14:167253f4e170 364 for (i = a->used - 1; i >= 0 && a->dp[i] == 0; i--) {
wolfSSL 14:167253f4e170 365 }
wolfSSL 14:167253f4e170 366 a->used = i + 1;
wolfSSL 14:167253f4e170 367 }
wolfSSL 14:167253f4e170 368
wolfSSL 14:167253f4e170 369 /* Grow big number to be able to hold l digits.
wolfSSL 14:167253f4e170 370 * This function does nothing as the number of digits is fixed.
wolfSSL 14:167253f4e170 371 *
wolfSSL 14:167253f4e170 372 * a SP integer.
wolfSSL 14:167253f4e170 373 * l Number of digits.
wolfSSL 14:167253f4e170 374 * retuns MP_MEM if the number of digits requested is more than available and
wolfSSL 14:167253f4e170 375 * MP_OKAY otherwise.
wolfSSL 14:167253f4e170 376 */
wolfSSL 14:167253f4e170 377 int sp_grow(sp_int* a, int l)
wolfSSL 14:167253f4e170 378 {
wolfSSL 14:167253f4e170 379 if (l > a->size)
wolfSSL 14:167253f4e170 380 return MP_MEM;
wolfSSL 14:167253f4e170 381 (void)a;
wolfSSL 14:167253f4e170 382 (void)l;
wolfSSL 14:167253f4e170 383 return MP_OKAY;
wolfSSL 14:167253f4e170 384 }
wolfSSL 14:167253f4e170 385
wolfSSL 14:167253f4e170 386 /* Sub a one digit number from the big number.
wolfSSL 14:167253f4e170 387 *
wolfSSL 14:167253f4e170 388 * a SP integer.
wolfSSL 14:167253f4e170 389 * d Digit to subtract.
wolfSSL 14:167253f4e170 390 * r SP integer - result.
wolfSSL 14:167253f4e170 391 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 392 */
wolfSSL 14:167253f4e170 393 int sp_sub_d(sp_int* a, sp_int_digit d, sp_int* r)
wolfSSL 14:167253f4e170 394 {
wolfSSL 14:167253f4e170 395 int i = 0;
wolfSSL 14:167253f4e170 396
wolfSSL 14:167253f4e170 397 r->used = a->used;
wolfSSL 14:167253f4e170 398 r->dp[0] = a->dp[0] - d;
wolfSSL 14:167253f4e170 399 if (r->dp[i] > a->dp[i]) {
wolfSSL 14:167253f4e170 400 for (; i < a->used; i++) {
wolfSSL 14:167253f4e170 401 r->dp[i] = a->dp[i] - 1;
wolfSSL 14:167253f4e170 402 if (r->dp[i] != (sp_int_digit)-1)
wolfSSL 14:167253f4e170 403 break;
wolfSSL 14:167253f4e170 404 }
wolfSSL 14:167253f4e170 405 }
wolfSSL 14:167253f4e170 406 for (; i < a->used; i++)
wolfSSL 14:167253f4e170 407 r->dp[i] = a->dp[i];
wolfSSL 14:167253f4e170 408
wolfSSL 14:167253f4e170 409 return MP_OKAY;
wolfSSL 14:167253f4e170 410 }
wolfSSL 14:167253f4e170 411
wolfSSL 14:167253f4e170 412 /* Compare a one digit number with a big number.
wolfSSL 14:167253f4e170 413 *
wolfSSL 14:167253f4e170 414 * a SP integer.
wolfSSL 14:167253f4e170 415 * d Digit to compare with.
wolfSSL 14:167253f4e170 416 * returns MP_GT if a is greater than d, MP_LT if a is less than d and MP_EQ
wolfSSL 14:167253f4e170 417 * when a equals d.
wolfSSL 14:167253f4e170 418 */
wolfSSL 14:167253f4e170 419 int sp_cmp_d(sp_int *a, sp_int_digit d)
wolfSSL 14:167253f4e170 420 {
wolfSSL 14:167253f4e170 421 /* special case for zero*/
wolfSSL 14:167253f4e170 422 if (a->used == 0) {
wolfSSL 14:167253f4e170 423 if (d == 0)
wolfSSL 14:167253f4e170 424 return MP_EQ;
wolfSSL 14:167253f4e170 425 else
wolfSSL 14:167253f4e170 426 return MP_LT;
wolfSSL 14:167253f4e170 427 }
wolfSSL 14:167253f4e170 428 else if (a->used > 1)
wolfSSL 14:167253f4e170 429 return MP_GT;
wolfSSL 14:167253f4e170 430
wolfSSL 14:167253f4e170 431 /* compare the only digit of a to d */
wolfSSL 14:167253f4e170 432 if (a->dp[0] > d)
wolfSSL 14:167253f4e170 433 return MP_GT;
wolfSSL 14:167253f4e170 434 else if (a->dp[0] < d)
wolfSSL 14:167253f4e170 435 return MP_LT;
wolfSSL 14:167253f4e170 436 return MP_EQ;
wolfSSL 14:167253f4e170 437 }
wolfSSL 14:167253f4e170 438
wolfSSL 14:167253f4e170 439 /* Left shift the number by number of bits.
wolfSSL 14:167253f4e170 440 * Bits may be larger than the word size.
wolfSSL 14:167253f4e170 441 *
wolfSSL 14:167253f4e170 442 * a SP integer.
wolfSSL 14:167253f4e170 443 * n Number of bits to shift.
wolfSSL 14:167253f4e170 444 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 445 */
wolfSSL 14:167253f4e170 446 static int sp_lshb(sp_int* a, int n)
wolfSSL 14:167253f4e170 447 {
wolfSSL 14:167253f4e170 448 int i;
wolfSSL 14:167253f4e170 449
wolfSSL 14:167253f4e170 450 if (n >= SP_WORD_SIZE) {
wolfSSL 14:167253f4e170 451 sp_lshd(a, n / SP_WORD_SIZE);
wolfSSL 14:167253f4e170 452 n %= SP_WORD_SIZE;
wolfSSL 14:167253f4e170 453 }
wolfSSL 14:167253f4e170 454
wolfSSL 14:167253f4e170 455 if (n == 0)
wolfSSL 14:167253f4e170 456 return MP_OKAY;
wolfSSL 14:167253f4e170 457
wolfSSL 14:167253f4e170 458 a->dp[a->used] = 0;
wolfSSL 14:167253f4e170 459 for (i = a->used - 1; i >= 0; i--) {
wolfSSL 14:167253f4e170 460 a->dp[i+1] |= a->dp[i] >> (SP_WORD_SIZE - n);
wolfSSL 14:167253f4e170 461 a->dp[i] = a->dp[i] << n;
wolfSSL 14:167253f4e170 462 }
wolfSSL 14:167253f4e170 463 if (a->dp[a->used] != 0)
wolfSSL 14:167253f4e170 464 a->used++;
wolfSSL 14:167253f4e170 465
wolfSSL 14:167253f4e170 466 return MP_OKAY;
wolfSSL 14:167253f4e170 467 }
wolfSSL 14:167253f4e170 468
wolfSSL 14:167253f4e170 469 /* Subtract two large numbers into result: r = a - b
wolfSSL 14:167253f4e170 470 * a must be greater than b.
wolfSSL 14:167253f4e170 471 *
wolfSSL 14:167253f4e170 472 * a SP integer.
wolfSSL 14:167253f4e170 473 * b SP integer.
wolfSSL 14:167253f4e170 474 * r SP integer.
wolfSSL 14:167253f4e170 475 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 476 */
wolfSSL 14:167253f4e170 477 static int sp_sub(sp_int* a, sp_int* b, sp_int* r)
wolfSSL 14:167253f4e170 478 {
wolfSSL 14:167253f4e170 479 int i;
wolfSSL 14:167253f4e170 480 sp_int_digit c = 0;
wolfSSL 14:167253f4e170 481 sp_int_digit t;
wolfSSL 14:167253f4e170 482
wolfSSL 14:167253f4e170 483 for (i = 0; i < a->used && i < b->used; i++) {
wolfSSL 14:167253f4e170 484 t = a->dp[i] - b->dp[i] - c;
wolfSSL 14:167253f4e170 485 if (c == 0)
wolfSSL 14:167253f4e170 486 c = t > a->dp[i];
wolfSSL 14:167253f4e170 487 else
wolfSSL 14:167253f4e170 488 c = t >= a->dp[i];
wolfSSL 14:167253f4e170 489 r->dp[i] = t;
wolfSSL 14:167253f4e170 490 }
wolfSSL 14:167253f4e170 491 for (; i < a->used; i++) {
wolfSSL 14:167253f4e170 492 r->dp[i] = a->dp[i] - c;
wolfSSL 14:167253f4e170 493 c = r->dp[i] == (sp_int_digit)-1;
wolfSSL 14:167253f4e170 494 }
wolfSSL 14:167253f4e170 495 r->used = i;
wolfSSL 14:167253f4e170 496 sp_clamp(r);
wolfSSL 14:167253f4e170 497
wolfSSL 14:167253f4e170 498 return MP_OKAY;
wolfSSL 14:167253f4e170 499 }
wolfSSL 14:167253f4e170 500
wolfSSL 14:167253f4e170 501 /* Calculate the r = a mod m.
wolfSSL 14:167253f4e170 502 *
wolfSSL 14:167253f4e170 503 * a SP integer.
wolfSSL 14:167253f4e170 504 * m SP integer.
wolfSSL 14:167253f4e170 505 * r SP integer.
wolfSSL 14:167253f4e170 506 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 507 */
wolfSSL 14:167253f4e170 508 int sp_mod(sp_int* a, sp_int* m, sp_int* r)
wolfSSL 14:167253f4e170 509 {
wolfSSL 14:167253f4e170 510 sp_int t;
wolfSSL 14:167253f4e170 511 int mBits = sp_count_bits(m);
wolfSSL 14:167253f4e170 512 int rBits;
wolfSSL 14:167253f4e170 513
wolfSSL 14:167253f4e170 514 if (a != r)
wolfSSL 14:167253f4e170 515 sp_copy(a, r);
wolfSSL 14:167253f4e170 516 sp_init(&t);
wolfSSL 14:167253f4e170 517
wolfSSL 14:167253f4e170 518 rBits = sp_count_bits(r);
wolfSSL 14:167253f4e170 519 while (rBits > mBits) {
wolfSSL 14:167253f4e170 520 sp_copy(m, &t);
wolfSSL 14:167253f4e170 521 sp_lshb(&t, rBits - mBits);
wolfSSL 14:167253f4e170 522
wolfSSL 14:167253f4e170 523 if (sp_cmp(&t, r) == MP_GT) {
wolfSSL 14:167253f4e170 524 sp_copy(m, &t);
wolfSSL 14:167253f4e170 525 sp_lshb(&t, rBits - mBits - 1);
wolfSSL 14:167253f4e170 526 }
wolfSSL 14:167253f4e170 527 sp_sub(r, &t, r);
wolfSSL 14:167253f4e170 528
wolfSSL 14:167253f4e170 529 rBits = sp_count_bits(r);
wolfSSL 14:167253f4e170 530 }
wolfSSL 14:167253f4e170 531 if (sp_cmp(r, m) != MP_LT)
wolfSSL 14:167253f4e170 532 sp_sub(r, m, r);
wolfSSL 14:167253f4e170 533
wolfSSL 14:167253f4e170 534 return MP_OKAY;
wolfSSL 14:167253f4e170 535 }
wolfSSL 14:167253f4e170 536
wolfSSL 14:167253f4e170 537 #if defined(USE_FAST_MATH) || !defined(NO_BIG_INT)
wolfSSL 14:167253f4e170 538 /* Clear all data in the big number and sets value to zero.
wolfSSL 14:167253f4e170 539 *
wolfSSL 14:167253f4e170 540 * a SP integer.
wolfSSL 14:167253f4e170 541 */
wolfSSL 14:167253f4e170 542 void sp_zero(sp_int* a)
wolfSSL 14:167253f4e170 543 {
wolfSSL 14:167253f4e170 544 XMEMSET(a->dp, 0, a->size);
wolfSSL 14:167253f4e170 545 a->used = 0;
wolfSSL 14:167253f4e170 546 }
wolfSSL 14:167253f4e170 547
wolfSSL 14:167253f4e170 548 /* Add a one digit number to the big number.
wolfSSL 14:167253f4e170 549 *
wolfSSL 14:167253f4e170 550 * a SP integer.
wolfSSL 14:167253f4e170 551 * d Digit to add.
wolfSSL 14:167253f4e170 552 * r SP integer - result.
wolfSSL 14:167253f4e170 553 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 554 */
wolfSSL 14:167253f4e170 555 int sp_add_d(sp_int* a, sp_int_digit d, sp_int* r)
wolfSSL 14:167253f4e170 556 {
wolfSSL 14:167253f4e170 557 int i = 0;
wolfSSL 14:167253f4e170 558
wolfSSL 14:167253f4e170 559 r->used = a->used;
wolfSSL 14:167253f4e170 560 r->dp[0] = a->dp[0] + d;
wolfSSL 14:167253f4e170 561 if (r->dp[i] < a->dp[i]) {
wolfSSL 14:167253f4e170 562 for (; i < a->used; i++) {
wolfSSL 14:167253f4e170 563 r->dp[i] = a->dp[i] + 1;
wolfSSL 14:167253f4e170 564 if (r->dp[i] != 0)
wolfSSL 14:167253f4e170 565 break;
wolfSSL 14:167253f4e170 566 }
wolfSSL 14:167253f4e170 567
wolfSSL 14:167253f4e170 568 if (i == a->used) {
wolfSSL 14:167253f4e170 569 r->used++;
wolfSSL 14:167253f4e170 570 r->dp[i] = 1;
wolfSSL 14:167253f4e170 571 }
wolfSSL 14:167253f4e170 572 }
wolfSSL 14:167253f4e170 573 for (; i < a->used; i++)
wolfSSL 14:167253f4e170 574 r->dp[i] = a->dp[i];
wolfSSL 14:167253f4e170 575
wolfSSL 14:167253f4e170 576 return MP_OKAY;
wolfSSL 14:167253f4e170 577 }
wolfSSL 14:167253f4e170 578
wolfSSL 14:167253f4e170 579 /* Left shift the big number by a number of digits.
wolfSSL 14:167253f4e170 580 * WIll chop off digits overflowing maximum size.
wolfSSL 14:167253f4e170 581 *
wolfSSL 14:167253f4e170 582 * a SP integer.
wolfSSL 14:167253f4e170 583 * s Number of digits to shift.
wolfSSL 14:167253f4e170 584 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 585 */
wolfSSL 14:167253f4e170 586 int sp_lshd(sp_int* a, int s)
wolfSSL 14:167253f4e170 587 {
wolfSSL 14:167253f4e170 588 if (a->used + s > a->size)
wolfSSL 14:167253f4e170 589 a->used = a->size - s;
wolfSSL 14:167253f4e170 590
wolfSSL 14:167253f4e170 591 XMEMMOVE(a->dp + s, a->dp, a->used * SP_INT_DIGITS);
wolfSSL 14:167253f4e170 592 a->used += s;
wolfSSL 14:167253f4e170 593 XMEMSET(a->dp, 0, s * sizeof(sp_int_digit));
wolfSSL 14:167253f4e170 594
wolfSSL 14:167253f4e170 595 return MP_OKAY;
wolfSSL 14:167253f4e170 596 }
wolfSSL 14:167253f4e170 597 #endif
wolfSSL 14:167253f4e170 598
wolfSSL 14:167253f4e170 599 #ifndef NO_PWDBASED
wolfSSL 14:167253f4e170 600 /* Add two large numbers into result: r = a + b
wolfSSL 14:167253f4e170 601 *
wolfSSL 14:167253f4e170 602 * a SP integer.
wolfSSL 14:167253f4e170 603 * b SP integer.
wolfSSL 14:167253f4e170 604 * r SP integer.
wolfSSL 14:167253f4e170 605 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 606 */
wolfSSL 14:167253f4e170 607 int sp_add(sp_int* a, sp_int* b, sp_int* r)
wolfSSL 14:167253f4e170 608 {
wolfSSL 14:167253f4e170 609 int i;
wolfSSL 14:167253f4e170 610 sp_digit c = 0;
wolfSSL 14:167253f4e170 611 sp_digit t;
wolfSSL 14:167253f4e170 612
wolfSSL 14:167253f4e170 613 for (i = 0; i < a->used && i < b->used; i++) {
wolfSSL 14:167253f4e170 614 t = a->dp[i] + b->dp[i] + c;
wolfSSL 14:167253f4e170 615 if (c == 0)
wolfSSL 14:167253f4e170 616 c = t < a->dp[i];
wolfSSL 14:167253f4e170 617 else
wolfSSL 14:167253f4e170 618 c = t <= a->dp[i];
wolfSSL 14:167253f4e170 619 r->dp[i] = t;
wolfSSL 14:167253f4e170 620 }
wolfSSL 14:167253f4e170 621 for (; i < a->used; i++) {
wolfSSL 14:167253f4e170 622 r->dp[i] = a->dp[i] + c;
wolfSSL 14:167253f4e170 623 c = r->dp[i] == 0;
wolfSSL 14:167253f4e170 624 }
wolfSSL 14:167253f4e170 625 for (; i < b->used; i++) {
wolfSSL 14:167253f4e170 626 r->dp[i] = b->dp[i] + c;
wolfSSL 14:167253f4e170 627 c = r->dp[i] == 0;
wolfSSL 14:167253f4e170 628 }
wolfSSL 14:167253f4e170 629 r->dp[i] = c;
wolfSSL 14:167253f4e170 630 r->used = (int)(i + c);
wolfSSL 14:167253f4e170 631
wolfSSL 14:167253f4e170 632 return MP_OKAY;
wolfSSL 14:167253f4e170 633 }
wolfSSL 14:167253f4e170 634 #endif
wolfSSL 14:167253f4e170 635
wolfSSL 14:167253f4e170 636 #ifndef NO_RSA
wolfSSL 14:167253f4e170 637 /* Set a number into the big number.
wolfSSL 14:167253f4e170 638 *
wolfSSL 14:167253f4e170 639 * a SP integer.
wolfSSL 14:167253f4e170 640 * b Value to set.
wolfSSL 14:167253f4e170 641 * returns MP_OKAY always.
wolfSSL 14:167253f4e170 642 */
wolfSSL 14:167253f4e170 643 int sp_set_int(sp_int* a, unsigned long b)
wolfSSL 14:167253f4e170 644 {
wolfSSL 14:167253f4e170 645 a->used = 1;
wolfSSL 14:167253f4e170 646 a->dp[0] = b;
wolfSSL 14:167253f4e170 647
wolfSSL 14:167253f4e170 648 return MP_OKAY;
wolfSSL 14:167253f4e170 649 }
wolfSSL 14:167253f4e170 650 #endif
wolfSSL 14:167253f4e170 651
wolfSSL 14:167253f4e170 652 #if !defined(USE_FAST_MATH)
wolfSSL 14:167253f4e170 653 /* Returns the run time settings.
wolfSSL 14:167253f4e170 654 *
wolfSSL 14:167253f4e170 655 * returns the settings value.
wolfSSL 14:167253f4e170 656 */
wolfSSL 14:167253f4e170 657 word32 CheckRunTimeSettings(void)
wolfSSL 14:167253f4e170 658 {
wolfSSL 14:167253f4e170 659 return CTC_SETTINGS;
wolfSSL 14:167253f4e170 660 }
wolfSSL 14:167253f4e170 661 #endif
wolfSSL 14:167253f4e170 662
wolfSSL 14:167253f4e170 663 #endif
wolfSSL 14:167253f4e170 664
wolfSSL 14:167253f4e170 665