sp_int.c

00001 /* sp_int.c
00002  *
00003  * Copyright (C) 2006-2017 wolfSSL Inc.
00004  *
00005  * This file is part of wolfSSL.
00006  *
00007  * wolfSSL is free software; you can redistribute it and/or modify
00008  * it under the terms of the GNU General Public License as published by
00009  * the Free Software Foundation; either version 2 of the License, or
00010  * (at your option) any later version.
00011  *
00012  * wolfSSL is distributed in the hope that it will be useful,
00013  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  * GNU General Public License for more details.
00016  *
00017  * You should have received a copy of the GNU General Public License
00018  * along with this program; if not, write to the Free Software
00019  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
00020  */
00021 
00022 /* Implementation by Sean Parkinson. */
00023 
00024 #ifdef HAVE_CONFIG_H
00025     #include <config.h>
00026 #endif
00027 
00028 #include <wolfcrypt/settings.h>
00029 #include <wolfcrypt/error-crypt.h>
00030 #ifdef NO_INLINE
00031     #include <wolfcrypt/misc.h>
00032 #else
00033     #define WOLFSSL_MISC_INCLUDED
00034     #include <wolfcrypt/src/misc.c>
00035 #endif
00036 
00037 
00038 #ifdef WOLFSSL_SP_MATH
00039 
00040 #include <wolfcrypt/sp_int.h>
00041 
00042 /* Initialize the big number to be zero.
00043  *
00044  * a  SP integer.
00045  * returns MP_OKAY always.
00046  */
00047 int sp_init(sp_int* a)
00048 {
00049     a->used = 0;
00050     a->size = SP_INT_DIGITS;
00051 
00052     return MP_OKAY;
00053 }
00054 
00055 /* Initialize up to six big numbers to be zero.
00056  *
00057  * a  SP integer.
00058  * b  SP integer.
00059  * c  SP integer.
00060  * d  SP integer.
00061  * e  SP integer.
00062  * f  SP integer.
00063  * returns MP_OKAY always.
00064  */
00065 int sp_init_multi(sp_int* a, sp_int* b, sp_int* c, sp_int* d, sp_int* e,
00066                   sp_int* f)
00067 {
00068     if (a != NULL) {
00069         a->used = 0;
00070         a->size = SP_INT_DIGITS;
00071     }
00072     if (b != NULL) {
00073         b->used = 0;
00074         b->size = SP_INT_DIGITS;
00075     }
00076     if (c != NULL) {
00077         c->used = 0;
00078         c->size = SP_INT_DIGITS;
00079     }
00080     if (d != NULL) {
00081         d->used = 0;
00082         d->size = SP_INT_DIGITS;
00083     }
00084     if (e != NULL) {
00085         e->used = 0;
00086         e->size = SP_INT_DIGITS;
00087     }
00088     if (f != NULL) {
00089         f->used = 0;
00090         f->size = SP_INT_DIGITS;
00091     }
00092 
00093     return MP_OKAY;
00094 }
00095 
00096 /* Clear the data from the big number and set to zero.
00097  *
00098  * a  SP integer.
00099  */
00100 void sp_clear(sp_int* a)
00101 {
00102     int i;
00103 
00104     for (i=0; i<a->used; i++)
00105         a->dp[i] = 0;
00106     a->used = 0;
00107 }
00108 
00109 /* Calculate the number of 8-bit values required to represent the big number.
00110  *
00111  * a  SP integer.
00112  * returns the count.
00113  */
00114 int sp_unsigned_bin_size(sp_int* a)
00115 {
00116     int size = sp_count_bits(a);
00117     return (size + 7) / 8;
00118 }
00119 
00120 /* Convert a number as an array of bytes in big-endian format to a big number.
00121  *
00122  * a     SP integer.
00123  * in    Array of bytes.
00124  * inSz  Number of data bytes in array.
00125  * returns MP_OKAY always.
00126  */
00127 int sp_read_unsigned_bin(sp_int* a, const byte* in, word32 inSz)
00128 {
00129     int i, j = 0, s = 0;
00130 
00131     a->dp[0] = 0;
00132     for (i = inSz-1; i >= 0; i--) {
00133         a->dp[j] |= ((sp_int_digit)in[i]) << s;
00134         if (s == DIGIT_BIT - 8) {
00135             a->dp[++j] = 0;
00136             s = 0;
00137         }
00138         else if (s > DIGIT_BIT - 8) {
00139             s = DIGIT_BIT - s;
00140             if (j + 1 >= a->size)
00141                 break;
00142             a->dp[++j] = in[i] >> s;
00143             s = 8 - s;
00144         }
00145         else
00146             s += 8;
00147     }
00148 
00149     a->used = j + 1;
00150     if (a->dp[j] == 0)
00151         a->used--;
00152 
00153     for (j++; j < a->size; j++)
00154         a->dp[j] = 0;
00155 
00156     return MP_OKAY;
00157 }
00158 
00159 /* Convert a number as string in big-endian format to a big number.
00160  * Only supports base-16 (hexadecimal).
00161  * Negative values not supported.
00162  *
00163  * a      SP integer.
00164  * in     NUL terminated string.
00165  * radix  Number of values in a digit.
00166  * returns BAD_FUNC_ARG when radix not supported or value is negative, MP_VAL
00167  * when a character is not valid and MP_OKAY otherwise.
00168  */
00169 int sp_read_radix(sp_int* a, const char* in, int radix)
00170 {
00171     int     i, j, k;
00172     char    ch;
00173 
00174     if (radix != 16)
00175         return BAD_FUNC_ARG;
00176 
00177     if (*in == '-') {
00178         return BAD_FUNC_ARG;
00179     }
00180 
00181     j = 0;
00182     k = 0;
00183     a->dp[0] = 0;
00184     for (i = (int)(XSTRLEN(in) - 1); i >= 0; i--) {
00185         ch = in[i];
00186         if (ch >= '0' && ch <= '9')
00187             ch -= '0';
00188         else if (ch >= 'A' && ch <= 'F')
00189             ch -= 'A' - 10;
00190         else if (ch >= 'a' && ch <= 'f')
00191             ch -= 'a' - 10;
00192         else
00193             return MP_VAL;
00194 
00195         a->dp[k] |= ((sp_int_digit)ch) << j;
00196         j += 4;
00197         if (j == DIGIT_BIT && k < SP_INT_DIGITS)
00198             a->dp[++k] = 0;
00199         j &= DIGIT_BIT - 1;
00200     }
00201 
00202     a->used = k + 1;
00203     if (a->dp[k] == 0)
00204         a->used--;
00205 
00206     for (k++; k < a->size; k++)
00207         a->dp[k] = 0;
00208 
00209     return MP_OKAY;
00210 }
00211 
00212 /* Compare two big numbers.
00213  *
00214  * a  SP integer.
00215  * b  SP integer.
00216  * returns MP_GT if a is greater than b, MP_LT if a is less than b and MP_EQ
00217  * when a equals b.
00218  */
00219 int sp_cmp(sp_int* a, sp_int* b)
00220 {
00221     int i;
00222 
00223     if (a->used > b->used)
00224         return MP_GT;
00225     else if (a->used < b->used)
00226         return MP_LT;
00227 
00228     for (i = a->used - 1; i >= 0; i--) {
00229         if (a->dp[i] > b->dp[i])
00230             return MP_GT;
00231         else if (a->dp[i] < b->dp[i])
00232             return MP_LT;
00233     }
00234     return MP_EQ;
00235 }
00236 
00237 /* Count the number of bits in the big number.
00238  *
00239  * a  SP integer.
00240  * returns the number of bits.
00241  */
00242 int sp_count_bits(sp_int* a)
00243 {
00244     int r = 0;
00245     sp_int_digit d;
00246 
00247     r = a->used - 1;
00248     while (r >= 0 && a->dp[r] == 0)
00249         r--;
00250     if (r < 0)
00251         r = 0;
00252     else {
00253         d = a->dp[r];
00254         r *= DIGIT_BIT;
00255         while (d != 0) {
00256             r++;
00257             d >>= 1;
00258         }
00259     }
00260 
00261     return r;
00262 }
00263 
00264 /* Determine if the most significant byte of the encoded big number as the top
00265  * bit set.
00266  *
00267  * a  SP integer.
00268  * returns 1 when the top bit is set and 0 otherwise.
00269  */
00270 int sp_leading_bit(sp_int* a)
00271 {
00272     int bit = 0;
00273     sp_int_digit d;
00274 
00275     if (a->used > 0) {
00276         d = a->dp[a->used - 1];
00277         while (d > (sp_int_digit)0xff)
00278             d >>= 8;
00279         bit = (int)(d >> 7);
00280     }
00281 
00282     return bit;
00283 }
00284 
00285 /* Convert the big number to an array of bytes in big-endian format.
00286  * The array must be large enough for encoded number - use mp_unsigned_bin_size
00287  * to calculate the number of bytes required.
00288  *
00289  * a  SP integer.
00290  * returns MP_OKAY always.
00291  */
00292 int sp_to_unsigned_bin(sp_int* a, byte* out)
00293 {
00294     int i, j, b;
00295 
00296     j = sp_unsigned_bin_size(a) - 1;
00297     for (i=0; j>=0; i++) {
00298         for (b = 0; b < SP_WORD_SIZE; b += 8) {
00299             out[j--] = a->dp[i] >> b;
00300             if (j < 0)
00301                 break;
00302         }
00303     }
00304 
00305     return MP_OKAY;
00306 }
00307 
00308 /* Ensure the data in the big number is zeroed.
00309  *
00310  * a  SP integer.
00311  */
00312 void sp_forcezero(sp_int* a)
00313 {
00314     ForceZero(a->dp, a->used * sizeof(sp_int_digit));
00315     a->used = 0;
00316 }
00317 
00318 /* Copy value of big number a into b.
00319  *
00320  * a  SP integer.
00321  * b  SP integer.
00322  * returns MP_OKAY always.
00323  */
00324 int sp_copy(sp_int* a, sp_int* b)
00325 {
00326     if (a != b) {
00327         XMEMCPY(b->dp, a->dp, a->used * sizeof(sp_int_digit));
00328         b->used = a->used;
00329     }
00330     return MP_OKAY;
00331 }
00332 
00333 /* Set the big number to be the value of the digit.
00334  *
00335  * a  SP integer.
00336  * d  Digit to be set.
00337  * returns MP_OKAY always.
00338  */
00339 int sp_set(sp_int* a, sp_int_digit d)
00340 {
00341     a->dp[0] = d;
00342     a->used = 1;
00343     return MP_OKAY;
00344 }
00345 
00346 /* Checks whether the value of the big number is zero.
00347  *
00348  * a  SP integer.
00349  * returns 1 when value is zero and 0 otherwise.
00350  */
00351 int sp_iszero(sp_int* a)
00352 {
00353     return a->used == 0;
00354 }
00355 
00356 /* Recalculate the number of digits used.
00357  *
00358  * a  SP integer.
00359  */
00360 void sp_clamp(sp_int* a)
00361 {
00362     int i;
00363 
00364     for (i = a->used - 1; i >= 0 && a->dp[i] == 0; i--) {
00365     }
00366     a->used = i + 1;
00367 }
00368 
00369 /* Grow big number to be able to hold l digits.
00370  * This function does nothing as the number of digits is fixed.
00371  *
00372  * a  SP integer.
00373  * l  Number of digits.
00374  * retuns MP_MEM if the number of digits requested is more than available and
00375  * MP_OKAY otherwise.
00376  */
00377 int sp_grow(sp_int* a, int l)
00378 {
00379     if (l > a->size)
00380         return MP_MEM;
00381     (void)a;
00382     (void)l;
00383     return MP_OKAY;
00384 }
00385 
00386 /* Sub a one digit number from the big number.
00387  *
00388  * a  SP integer.
00389  * d  Digit to subtract.
00390  * r  SP integer - result.
00391  * returns MP_OKAY always.
00392  */
00393 int sp_sub_d(sp_int* a, sp_int_digit d, sp_int* r)
00394 {
00395     int i = 0;
00396 
00397     r->used = a->used;
00398     r->dp[0] = a->dp[0] - d;
00399     if (r->dp[i] > a->dp[i]) {
00400         for (; i < a->used; i++) {
00401             r->dp[i] = a->dp[i] - 1;
00402             if (r->dp[i] != (sp_int_digit)-1)
00403                break;
00404         }
00405     }
00406     for (; i < a->used; i++)
00407         r->dp[i] = a->dp[i];
00408 
00409     return MP_OKAY;
00410 }
00411 
00412 /* Compare a one digit number with a big number.
00413  *
00414  * a  SP integer.
00415  * d  Digit to compare with.
00416  * returns MP_GT if a is greater than d, MP_LT if a is less than d and MP_EQ
00417  * when a equals d.
00418  */
00419 int sp_cmp_d(sp_int *a, sp_int_digit d)
00420 {
00421     /* special case for zero*/
00422     if (a->used == 0) {
00423         if (d == 0)
00424             return MP_EQ;
00425         else
00426             return MP_LT;
00427     }
00428     else if (a->used > 1)
00429         return MP_GT;
00430 
00431     /* compare the only digit of a to d */
00432     if (a->dp[0] > d)
00433         return MP_GT;
00434     else if (a->dp[0] < d)
00435         return MP_LT;
00436     return MP_EQ;
00437 }
00438 
00439 /* Left shift the number by number of bits.
00440  * Bits may be larger than the word size.
00441  *
00442  * a  SP integer.
00443  * n  Number of bits to shift.
00444  * returns MP_OKAY always.
00445  */
00446 static int sp_lshb(sp_int* a, int n)
00447 {
00448     int i;
00449 
00450     if (n >= SP_WORD_SIZE) {
00451         sp_lshd(a, n / SP_WORD_SIZE);
00452         n %= SP_WORD_SIZE;
00453     }
00454 
00455     if (n == 0)
00456         return MP_OKAY;
00457 
00458     a->dp[a->used] = 0;
00459     for (i = a->used - 1; i >= 0; i--) {
00460         a->dp[i+1] |= a->dp[i] >> (SP_WORD_SIZE - n);
00461         a->dp[i] = a->dp[i] << n;
00462     }
00463     if (a->dp[a->used] != 0)
00464         a->used++;
00465 
00466     return MP_OKAY;
00467 }
00468 
00469 /* Subtract two large numbers into result: r = a - b
00470  * a must be greater than b.
00471  *
00472  * a  SP integer.
00473  * b  SP integer.
00474  * r  SP integer.
00475  * returns MP_OKAY always.
00476  */
00477 static int sp_sub(sp_int* a, sp_int* b, sp_int* r)
00478 {
00479     int i;
00480     sp_int_digit c = 0;
00481     sp_int_digit t;
00482 
00483     for (i = 0; i < a->used && i < b->used; i++) {
00484         t = a->dp[i] - b->dp[i] - c;
00485         if (c == 0)
00486             c = t > a->dp[i];
00487         else
00488             c = t >= a->dp[i];
00489         r->dp[i] = t;
00490     }
00491     for (; i < a->used; i++) {
00492         r->dp[i] = a->dp[i] - c;
00493         c = r->dp[i] == (sp_int_digit)-1;
00494     }
00495     r->used = i;
00496     sp_clamp(r);
00497 
00498     return MP_OKAY;
00499 }
00500 
00501 /* Calculate the r = a mod m.
00502  *
00503  * a  SP integer.
00504  * m  SP integer.
00505  * r  SP integer.
00506  * returns MP_OKAY always.
00507  */
00508 int sp_mod(sp_int* a, sp_int* m, sp_int* r)
00509 {
00510     sp_int t;
00511     int mBits = sp_count_bits(m);
00512     int rBits;
00513 
00514     if (a != r)
00515         sp_copy(a, r);
00516     sp_init(&t);
00517 
00518     rBits = sp_count_bits(r);
00519     while (rBits > mBits) {
00520         sp_copy(m, &t);
00521         sp_lshb(&t, rBits - mBits);
00522 
00523         if (sp_cmp(&t, r) == MP_GT) {
00524             sp_copy(m, &t);
00525             sp_lshb(&t, rBits - mBits - 1);
00526         }
00527         sp_sub(r, &t, r);
00528 
00529         rBits = sp_count_bits(r);
00530     }
00531     if (sp_cmp(r, m) != MP_LT)
00532         sp_sub(r, m, r);
00533 
00534     return MP_OKAY;
00535 }
00536 
00537 #if defined(USE_FAST_MATH) || !defined(NO_BIG_INT)
00538 /* Clear all data in the big number and sets value to zero.
00539  *
00540  * a  SP integer.
00541  */
00542 void sp_zero(sp_int* a)
00543 {
00544     XMEMSET(a->dp, 0, a->size);
00545     a->used = 0;
00546 }
00547 
00548 /* Add a one digit number to the big number.
00549  *
00550  * a  SP integer.
00551  * d  Digit to add.
00552  * r  SP integer - result.
00553  * returns MP_OKAY always.
00554  */
00555 int sp_add_d(sp_int* a, sp_int_digit d, sp_int* r)
00556 {
00557     int i = 0;
00558 
00559     r->used = a->used;
00560     r->dp[0] = a->dp[0] + d;
00561     if (r->dp[i] < a->dp[i]) {
00562         for (; i < a->used; i++) {
00563             r->dp[i] = a->dp[i] + 1;
00564             if (r->dp[i] != 0)
00565                break;
00566         }
00567 
00568         if (i == a->used) {
00569             r->used++;
00570             r->dp[i] = 1;
00571         }
00572     }
00573     for (; i < a->used; i++)
00574         r->dp[i] = a->dp[i];
00575 
00576     return MP_OKAY;
00577 }
00578 
00579 /* Left shift the big number by a number of digits.
00580  * WIll chop off digits overflowing maximum size.
00581  *
00582  * a  SP integer.
00583  * s  Number of digits to shift.
00584  * returns MP_OKAY always.
00585  */
00586 int sp_lshd(sp_int* a, int s)
00587 {
00588     if (a->used + s > a->size)
00589         a->used = a->size - s;
00590 
00591     XMEMMOVE(a->dp + s, a->dp, a->used * SP_INT_DIGITS);
00592     a->used += s;
00593     XMEMSET(a->dp, 0, s * sizeof(sp_int_digit));
00594 
00595     return MP_OKAY;
00596 }
00597 #endif
00598 
00599 #ifndef NO_PWDBASED
00600 /* Add two large numbers into result: r = a + b
00601  *
00602  * a  SP integer.
00603  * b  SP integer.
00604  * r  SP integer.
00605  * returns MP_OKAY always.
00606  */
00607 int sp_add(sp_int* a, sp_int* b, sp_int* r)
00608 {
00609     int i;
00610     sp_digit c = 0;
00611     sp_digit t;
00612 
00613     for (i = 0; i < a->used && i < b->used; i++) {
00614         t = a->dp[i] + b->dp[i] + c;
00615         if (c == 0)
00616             c = t < a->dp[i];
00617         else
00618             c = t <= a->dp[i];
00619         r->dp[i] = t;
00620     }
00621     for (; i < a->used; i++) {
00622         r->dp[i] = a->dp[i] + c;
00623         c = r->dp[i] == 0;
00624     }
00625     for (; i < b->used; i++) {
00626         r->dp[i] = b->dp[i] + c;
00627         c = r->dp[i] == 0;
00628     }
00629     r->dp[i] = c;
00630     r->used = (int)(i + c);
00631 
00632     return MP_OKAY;
00633 }
00634 #endif
00635 
00636 #ifndef NO_RSA
00637 /* Set a number into the big number.
00638  *
00639  * a  SP integer.
00640  * b  Value to set.
00641  * returns MP_OKAY always.
00642  */
00643 int sp_set_int(sp_int* a, unsigned long b)
00644 {
00645     a->used = 1;
00646     a->dp[0] = b;
00647 
00648     return MP_OKAY;
00649 }
00650 #endif
00651 
00652 #if !defined(USE_FAST_MATH)
00653 /* Returns the run time settings.
00654  *
00655  * returns the settings value.
00656  */
00657 word32 CheckRunTimeSettings(void)
00658 {
00659     return CTC_SETTINGS;
00660 }
00661 #endif
00662 
00663 #endif
00664 
00665