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/tfm.c@13:f67a6c6013ca, 2017-08-22 (annotated)

Committer:
wolfSSL
Date:
Tue Aug 22 10:48:22 2017 +0000
Revision:
13:f67a6c6013ca
wolfSSL3.12.0 with TLS1.3

Who changed what in which revision?

UserRevisionLine numberNew contents of line
wolfSSL 13:f67a6c6013ca 1 /* tfm.c
wolfSSL 13:f67a6c6013ca 2 *
wolfSSL 13:f67a6c6013ca 3 * Copyright (C) 2006-2016 wolfSSL Inc.
wolfSSL 13:f67a6c6013ca 4 *
wolfSSL 13:f67a6c6013ca 5 * This file is part of wolfSSL.
wolfSSL 13:f67a6c6013ca 6 *
wolfSSL 13:f67a6c6013ca 7 * wolfSSL is free software; you can redistribute it and/or modify
wolfSSL 13:f67a6c6013ca 8 * it under the terms of the GNU General Public License as published by
wolfSSL 13:f67a6c6013ca 9 * the Free Software Foundation; either version 2 of the License, or
wolfSSL 13:f67a6c6013ca 10 * (at your option) any later version.
wolfSSL 13:f67a6c6013ca 11 *
wolfSSL 13:f67a6c6013ca 12 * wolfSSL is distributed in the hope that it will be useful,
wolfSSL 13:f67a6c6013ca 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
wolfSSL 13:f67a6c6013ca 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
wolfSSL 13:f67a6c6013ca 15 * GNU General Public License for more details.
wolfSSL 13:f67a6c6013ca 16 *
wolfSSL 13:f67a6c6013ca 17 * You should have received a copy of the GNU General Public License
wolfSSL 13:f67a6c6013ca 18 * along with this program; if not, write to the Free Software
wolfSSL 13:f67a6c6013ca 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
wolfSSL 13:f67a6c6013ca 20 */
wolfSSL 13:f67a6c6013ca 21
wolfSSL 13:f67a6c6013ca 22
wolfSSL 13:f67a6c6013ca 23
wolfSSL 13:f67a6c6013ca 24 /*
wolfSSL 13:f67a6c6013ca 25 * Based on public domain TomsFastMath 0.10 by Tom St Denis, tomstdenis@iahu.ca,
wolfSSL 13:f67a6c6013ca 26 * http://math.libtomcrypt.com
wolfSSL 13:f67a6c6013ca 27 */
wolfSSL 13:f67a6c6013ca 28
wolfSSL 13:f67a6c6013ca 29 /**
wolfSSL 13:f67a6c6013ca 30 * Edited by Moises Guimaraes (moisesguimaraesm@gmail.com)
wolfSSL 13:f67a6c6013ca 31 * to fit CyaSSL's needs.
wolfSSL 13:f67a6c6013ca 32 */
wolfSSL 13:f67a6c6013ca 33
wolfSSL 13:f67a6c6013ca 34 #ifdef HAVE_CONFIG_H
wolfSSL 13:f67a6c6013ca 35 #include <config.h>
wolfSSL 13:f67a6c6013ca 36 #endif
wolfSSL 13:f67a6c6013ca 37
wolfSSL 13:f67a6c6013ca 38 /* in case user set USE_FAST_MATH there */
wolfSSL 13:f67a6c6013ca 39 #include <wolfssl/wolfcrypt/settings.h>
wolfSSL 13:f67a6c6013ca 40 #ifdef NO_INLINE
wolfSSL 13:f67a6c6013ca 41 #include <wolfssl/wolfcrypt/misc.h>
wolfSSL 13:f67a6c6013ca 42 #else
wolfSSL 13:f67a6c6013ca 43 #define WOLFSSL_MISC_INCLUDED
wolfSSL 13:f67a6c6013ca 44 #include <wolfcrypt/src/misc.c>
wolfSSL 13:f67a6c6013ca 45 #endif
wolfSSL 13:f67a6c6013ca 46
wolfSSL 13:f67a6c6013ca 47 #ifdef USE_FAST_MATH
wolfSSL 13:f67a6c6013ca 48
wolfSSL 13:f67a6c6013ca 49 #include <wolfssl/wolfcrypt/random.h>
wolfSSL 13:f67a6c6013ca 50 #include <wolfssl/wolfcrypt/tfm.h>
wolfSSL 13:f67a6c6013ca 51 #include <wolfcrypt/src/asm.c> /* will define asm MACROS or C ones */
wolfSSL 13:f67a6c6013ca 52 #include <wolfssl/wolfcrypt/wolfmath.h> /* common functions */
wolfSSL 13:f67a6c6013ca 53
wolfSSL 13:f67a6c6013ca 54 #if defined(FREESCALE_LTC_TFM)
wolfSSL 13:f67a6c6013ca 55 #include <wolfssl/wolfcrypt/port/nxp/ksdk_port.h>
wolfSSL 13:f67a6c6013ca 56 #endif
wolfSSL 13:f67a6c6013ca 57 #ifdef WOLFSSL_DEBUG_MATH
wolfSSL 13:f67a6c6013ca 58 #include <stdio.h>
wolfSSL 13:f67a6c6013ca 59 #endif
wolfSSL 13:f67a6c6013ca 60
wolfSSL 13:f67a6c6013ca 61
wolfSSL 13:f67a6c6013ca 62 /* math settings check */
wolfSSL 13:f67a6c6013ca 63 word32 CheckRunTimeSettings(void)
wolfSSL 13:f67a6c6013ca 64 {
wolfSSL 13:f67a6c6013ca 65 return CTC_SETTINGS;
wolfSSL 13:f67a6c6013ca 66 }
wolfSSL 13:f67a6c6013ca 67
wolfSSL 13:f67a6c6013ca 68
wolfSSL 13:f67a6c6013ca 69 /* math settings size check */
wolfSSL 13:f67a6c6013ca 70 word32 CheckRunTimeFastMath(void)
wolfSSL 13:f67a6c6013ca 71 {
wolfSSL 13:f67a6c6013ca 72 return FP_SIZE;
wolfSSL 13:f67a6c6013ca 73 }
wolfSSL 13:f67a6c6013ca 74
wolfSSL 13:f67a6c6013ca 75
wolfSSL 13:f67a6c6013ca 76 /* Functions */
wolfSSL 13:f67a6c6013ca 77
wolfSSL 13:f67a6c6013ca 78 void fp_add(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 79 {
wolfSSL 13:f67a6c6013ca 80 int sa, sb;
wolfSSL 13:f67a6c6013ca 81
wolfSSL 13:f67a6c6013ca 82 /* get sign of both inputs */
wolfSSL 13:f67a6c6013ca 83 sa = a->sign;
wolfSSL 13:f67a6c6013ca 84 sb = b->sign;
wolfSSL 13:f67a6c6013ca 85
wolfSSL 13:f67a6c6013ca 86 /* handle two cases, not four */
wolfSSL 13:f67a6c6013ca 87 if (sa == sb) {
wolfSSL 13:f67a6c6013ca 88 /* both positive or both negative */
wolfSSL 13:f67a6c6013ca 89 /* add their magnitudes, copy the sign */
wolfSSL 13:f67a6c6013ca 90 c->sign = sa;
wolfSSL 13:f67a6c6013ca 91 s_fp_add (a, b, c);
wolfSSL 13:f67a6c6013ca 92 } else {
wolfSSL 13:f67a6c6013ca 93 /* one positive, the other negative */
wolfSSL 13:f67a6c6013ca 94 /* subtract the one with the greater magnitude from */
wolfSSL 13:f67a6c6013ca 95 /* the one of the lesser magnitude. The result gets */
wolfSSL 13:f67a6c6013ca 96 /* the sign of the one with the greater magnitude. */
wolfSSL 13:f67a6c6013ca 97 if (fp_cmp_mag (a, b) == FP_LT) {
wolfSSL 13:f67a6c6013ca 98 c->sign = sb;
wolfSSL 13:f67a6c6013ca 99 s_fp_sub (b, a, c);
wolfSSL 13:f67a6c6013ca 100 } else {
wolfSSL 13:f67a6c6013ca 101 c->sign = sa;
wolfSSL 13:f67a6c6013ca 102 s_fp_sub (a, b, c);
wolfSSL 13:f67a6c6013ca 103 }
wolfSSL 13:f67a6c6013ca 104 }
wolfSSL 13:f67a6c6013ca 105 }
wolfSSL 13:f67a6c6013ca 106
wolfSSL 13:f67a6c6013ca 107 /* unsigned addition */
wolfSSL 13:f67a6c6013ca 108 void s_fp_add(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 109 {
wolfSSL 13:f67a6c6013ca 110 int x, y, oldused;
wolfSSL 13:f67a6c6013ca 111 fp_word t;
wolfSSL 13:f67a6c6013ca 112
wolfSSL 13:f67a6c6013ca 113 y = MAX(a->used, b->used);
wolfSSL 13:f67a6c6013ca 114 oldused = MIN(c->used, FP_SIZE); /* help static analysis w/ largest size */
wolfSSL 13:f67a6c6013ca 115 c->used = y;
wolfSSL 13:f67a6c6013ca 116
wolfSSL 13:f67a6c6013ca 117 t = 0;
wolfSSL 13:f67a6c6013ca 118 for (x = 0; x < y; x++) {
wolfSSL 13:f67a6c6013ca 119 t += ((fp_word)a->dp[x]) + ((fp_word)b->dp[x]);
wolfSSL 13:f67a6c6013ca 120 c->dp[x] = (fp_digit)t;
wolfSSL 13:f67a6c6013ca 121 t >>= DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 122 }
wolfSSL 13:f67a6c6013ca 123 if (t != 0 && x < FP_SIZE) {
wolfSSL 13:f67a6c6013ca 124 c->dp[c->used++] = (fp_digit)t;
wolfSSL 13:f67a6c6013ca 125 ++x;
wolfSSL 13:f67a6c6013ca 126 }
wolfSSL 13:f67a6c6013ca 127
wolfSSL 13:f67a6c6013ca 128 c->used = x;
wolfSSL 13:f67a6c6013ca 129
wolfSSL 13:f67a6c6013ca 130 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 131 for (; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 132 c->dp[x] = 0;
wolfSSL 13:f67a6c6013ca 133 }
wolfSSL 13:f67a6c6013ca 134 fp_clamp(c);
wolfSSL 13:f67a6c6013ca 135 }
wolfSSL 13:f67a6c6013ca 136
wolfSSL 13:f67a6c6013ca 137 /* c = a - b */
wolfSSL 13:f67a6c6013ca 138 void fp_sub(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 139 {
wolfSSL 13:f67a6c6013ca 140 int sa, sb;
wolfSSL 13:f67a6c6013ca 141
wolfSSL 13:f67a6c6013ca 142 sa = a->sign;
wolfSSL 13:f67a6c6013ca 143 sb = b->sign;
wolfSSL 13:f67a6c6013ca 144
wolfSSL 13:f67a6c6013ca 145 if (sa != sb) {
wolfSSL 13:f67a6c6013ca 146 /* subtract a negative from a positive, OR */
wolfSSL 13:f67a6c6013ca 147 /* subtract a positive from a negative. */
wolfSSL 13:f67a6c6013ca 148 /* In either case, ADD their magnitudes, */
wolfSSL 13:f67a6c6013ca 149 /* and use the sign of the first number. */
wolfSSL 13:f67a6c6013ca 150 c->sign = sa;
wolfSSL 13:f67a6c6013ca 151 s_fp_add (a, b, c);
wolfSSL 13:f67a6c6013ca 152 } else {
wolfSSL 13:f67a6c6013ca 153 /* subtract a positive from a positive, OR */
wolfSSL 13:f67a6c6013ca 154 /* subtract a negative from a negative. */
wolfSSL 13:f67a6c6013ca 155 /* First, take the difference between their */
wolfSSL 13:f67a6c6013ca 156 /* magnitudes, then... */
wolfSSL 13:f67a6c6013ca 157 if (fp_cmp_mag (a, b) != FP_LT) {
wolfSSL 13:f67a6c6013ca 158 /* Copy the sign from the first */
wolfSSL 13:f67a6c6013ca 159 c->sign = sa;
wolfSSL 13:f67a6c6013ca 160 /* The first has a larger or equal magnitude */
wolfSSL 13:f67a6c6013ca 161 s_fp_sub (a, b, c);
wolfSSL 13:f67a6c6013ca 162 } else {
wolfSSL 13:f67a6c6013ca 163 /* The result has the *opposite* sign from */
wolfSSL 13:f67a6c6013ca 164 /* the first number. */
wolfSSL 13:f67a6c6013ca 165 c->sign = (sa == FP_ZPOS) ? FP_NEG : FP_ZPOS;
wolfSSL 13:f67a6c6013ca 166 /* The second has a larger magnitude */
wolfSSL 13:f67a6c6013ca 167 s_fp_sub (b, a, c);
wolfSSL 13:f67a6c6013ca 168 }
wolfSSL 13:f67a6c6013ca 169 }
wolfSSL 13:f67a6c6013ca 170 }
wolfSSL 13:f67a6c6013ca 171
wolfSSL 13:f67a6c6013ca 172 /* unsigned subtraction ||a|| >= ||b|| ALWAYS! */
wolfSSL 13:f67a6c6013ca 173 void s_fp_sub(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 174 {
wolfSSL 13:f67a6c6013ca 175 int x, oldbused, oldused;
wolfSSL 13:f67a6c6013ca 176 fp_word t;
wolfSSL 13:f67a6c6013ca 177
wolfSSL 13:f67a6c6013ca 178 oldused = c->used;
wolfSSL 13:f67a6c6013ca 179 oldbused = b->used;
wolfSSL 13:f67a6c6013ca 180 c->used = a->used;
wolfSSL 13:f67a6c6013ca 181 t = 0;
wolfSSL 13:f67a6c6013ca 182 for (x = 0; x < oldbused; x++) {
wolfSSL 13:f67a6c6013ca 183 t = ((fp_word)a->dp[x]) - (((fp_word)b->dp[x]) + t);
wolfSSL 13:f67a6c6013ca 184 c->dp[x] = (fp_digit)t;
wolfSSL 13:f67a6c6013ca 185 t = (t >> DIGIT_BIT)&1;
wolfSSL 13:f67a6c6013ca 186 }
wolfSSL 13:f67a6c6013ca 187 for (; x < a->used; x++) {
wolfSSL 13:f67a6c6013ca 188 t = ((fp_word)a->dp[x]) - t;
wolfSSL 13:f67a6c6013ca 189 c->dp[x] = (fp_digit)t;
wolfSSL 13:f67a6c6013ca 190 t = (t >> DIGIT_BIT)&1;
wolfSSL 13:f67a6c6013ca 191 }
wolfSSL 13:f67a6c6013ca 192
wolfSSL 13:f67a6c6013ca 193 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 194 for (; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 195 c->dp[x] = 0;
wolfSSL 13:f67a6c6013ca 196 }
wolfSSL 13:f67a6c6013ca 197 fp_clamp(c);
wolfSSL 13:f67a6c6013ca 198 }
wolfSSL 13:f67a6c6013ca 199
wolfSSL 13:f67a6c6013ca 200 /* c = a * b */
wolfSSL 13:f67a6c6013ca 201 void fp_mul(fp_int *A, fp_int *B, fp_int *C)
wolfSSL 13:f67a6c6013ca 202 {
wolfSSL 13:f67a6c6013ca 203 int y, yy, oldused;
wolfSSL 13:f67a6c6013ca 204
wolfSSL 13:f67a6c6013ca 205 oldused = C->used;
wolfSSL 13:f67a6c6013ca 206
wolfSSL 13:f67a6c6013ca 207 y = MAX(A->used, B->used);
wolfSSL 13:f67a6c6013ca 208 yy = MIN(A->used, B->used);
wolfSSL 13:f67a6c6013ca 209
wolfSSL 13:f67a6c6013ca 210 /* call generic if we're out of range */
wolfSSL 13:f67a6c6013ca 211 if (y + yy > FP_SIZE) {
wolfSSL 13:f67a6c6013ca 212 fp_mul_comba(A, B, C);
wolfSSL 13:f67a6c6013ca 213 goto clean;
wolfSSL 13:f67a6c6013ca 214 }
wolfSSL 13:f67a6c6013ca 215
wolfSSL 13:f67a6c6013ca 216 /* pick a comba (unrolled 4/8/16/32 x or rolled) based on the size
wolfSSL 13:f67a6c6013ca 217 of the largest input. We also want to avoid doing excess mults if the
wolfSSL 13:f67a6c6013ca 218 inputs are not close to the next power of two. That is, for example,
wolfSSL 13:f67a6c6013ca 219 if say y=17 then we would do (32-17)^2 = 225 unneeded multiplications
wolfSSL 13:f67a6c6013ca 220 */
wolfSSL 13:f67a6c6013ca 221
wolfSSL 13:f67a6c6013ca 222 #if defined(TFM_MUL3) && FP_SIZE >= 6
wolfSSL 13:f67a6c6013ca 223 if (y <= 3) {
wolfSSL 13:f67a6c6013ca 224 fp_mul_comba3(A,B,C);
wolfSSL 13:f67a6c6013ca 225 goto clean;
wolfSSL 13:f67a6c6013ca 226 }
wolfSSL 13:f67a6c6013ca 227 #endif
wolfSSL 13:f67a6c6013ca 228 #if defined(TFM_MUL4) && FP_SIZE >= 8
wolfSSL 13:f67a6c6013ca 229 if (y == 4) {
wolfSSL 13:f67a6c6013ca 230 fp_mul_comba4(A,B,C);
wolfSSL 13:f67a6c6013ca 231 goto clean;
wolfSSL 13:f67a6c6013ca 232 }
wolfSSL 13:f67a6c6013ca 233 #endif
wolfSSL 13:f67a6c6013ca 234 #if defined(TFM_MUL6) && FP_SIZE >= 12
wolfSSL 13:f67a6c6013ca 235 if (y <= 6) {
wolfSSL 13:f67a6c6013ca 236 fp_mul_comba6(A,B,C);
wolfSSL 13:f67a6c6013ca 237 goto clean;
wolfSSL 13:f67a6c6013ca 238 }
wolfSSL 13:f67a6c6013ca 239 #endif
wolfSSL 13:f67a6c6013ca 240 #if defined(TFM_MUL7) && FP_SIZE >= 14
wolfSSL 13:f67a6c6013ca 241 if (y == 7) {
wolfSSL 13:f67a6c6013ca 242 fp_mul_comba7(A,B,C);
wolfSSL 13:f67a6c6013ca 243 goto clean;
wolfSSL 13:f67a6c6013ca 244 }
wolfSSL 13:f67a6c6013ca 245 #endif
wolfSSL 13:f67a6c6013ca 246 #if defined(TFM_MUL8) && FP_SIZE >= 16
wolfSSL 13:f67a6c6013ca 247 if (y == 8) {
wolfSSL 13:f67a6c6013ca 248 fp_mul_comba8(A,B,C);
wolfSSL 13:f67a6c6013ca 249 goto clean;
wolfSSL 13:f67a6c6013ca 250 }
wolfSSL 13:f67a6c6013ca 251 #endif
wolfSSL 13:f67a6c6013ca 252 #if defined(TFM_MUL9) && FP_SIZE >= 18
wolfSSL 13:f67a6c6013ca 253 if (y == 9) {
wolfSSL 13:f67a6c6013ca 254 fp_mul_comba9(A,B,C);
wolfSSL 13:f67a6c6013ca 255 goto clean;
wolfSSL 13:f67a6c6013ca 256 }
wolfSSL 13:f67a6c6013ca 257 #endif
wolfSSL 13:f67a6c6013ca 258 #if defined(TFM_MUL12) && FP_SIZE >= 24
wolfSSL 13:f67a6c6013ca 259 if (y <= 12) {
wolfSSL 13:f67a6c6013ca 260 fp_mul_comba12(A,B,C);
wolfSSL 13:f67a6c6013ca 261 goto clean;
wolfSSL 13:f67a6c6013ca 262 }
wolfSSL 13:f67a6c6013ca 263 #endif
wolfSSL 13:f67a6c6013ca 264 #if defined(TFM_MUL17) && FP_SIZE >= 34
wolfSSL 13:f67a6c6013ca 265 if (y <= 17) {
wolfSSL 13:f67a6c6013ca 266 fp_mul_comba17(A,B,C);
wolfSSL 13:f67a6c6013ca 267 goto clean;
wolfSSL 13:f67a6c6013ca 268 }
wolfSSL 13:f67a6c6013ca 269 #endif
wolfSSL 13:f67a6c6013ca 270
wolfSSL 13:f67a6c6013ca 271 #if defined(TFM_SMALL_SET) && FP_SIZE >= 32
wolfSSL 13:f67a6c6013ca 272 if (y <= 16) {
wolfSSL 13:f67a6c6013ca 273 fp_mul_comba_small(A,B,C);
wolfSSL 13:f67a6c6013ca 274 goto clean;
wolfSSL 13:f67a6c6013ca 275 }
wolfSSL 13:f67a6c6013ca 276 #endif
wolfSSL 13:f67a6c6013ca 277 #if defined(TFM_MUL20) && FP_SIZE >= 40
wolfSSL 13:f67a6c6013ca 278 if (y <= 20) {
wolfSSL 13:f67a6c6013ca 279 fp_mul_comba20(A,B,C);
wolfSSL 13:f67a6c6013ca 280 goto clean;
wolfSSL 13:f67a6c6013ca 281 }
wolfSSL 13:f67a6c6013ca 282 #endif
wolfSSL 13:f67a6c6013ca 283 #if defined(TFM_MUL24) && FP_SIZE >= 48
wolfSSL 13:f67a6c6013ca 284 if (yy >= 16 && y <= 24) {
wolfSSL 13:f67a6c6013ca 285 fp_mul_comba24(A,B,C);
wolfSSL 13:f67a6c6013ca 286 goto clean;
wolfSSL 13:f67a6c6013ca 287 }
wolfSSL 13:f67a6c6013ca 288 #endif
wolfSSL 13:f67a6c6013ca 289 #if defined(TFM_MUL28) && FP_SIZE >= 56
wolfSSL 13:f67a6c6013ca 290 if (yy >= 20 && y <= 28) {
wolfSSL 13:f67a6c6013ca 291 fp_mul_comba28(A,B,C);
wolfSSL 13:f67a6c6013ca 292 goto clean;
wolfSSL 13:f67a6c6013ca 293 }
wolfSSL 13:f67a6c6013ca 294 #endif
wolfSSL 13:f67a6c6013ca 295 #if defined(TFM_MUL32) && FP_SIZE >= 64
wolfSSL 13:f67a6c6013ca 296 if (yy >= 24 && y <= 32) {
wolfSSL 13:f67a6c6013ca 297 fp_mul_comba32(A,B,C);
wolfSSL 13:f67a6c6013ca 298 goto clean;
wolfSSL 13:f67a6c6013ca 299 }
wolfSSL 13:f67a6c6013ca 300 #endif
wolfSSL 13:f67a6c6013ca 301 #if defined(TFM_MUL48) && FP_SIZE >= 96
wolfSSL 13:f67a6c6013ca 302 if (yy >= 40 && y <= 48) {
wolfSSL 13:f67a6c6013ca 303 fp_mul_comba48(A,B,C);
wolfSSL 13:f67a6c6013ca 304 goto clean;
wolfSSL 13:f67a6c6013ca 305 }
wolfSSL 13:f67a6c6013ca 306 #endif
wolfSSL 13:f67a6c6013ca 307 #if defined(TFM_MUL64) && FP_SIZE >= 128
wolfSSL 13:f67a6c6013ca 308 if (yy >= 56 && y <= 64) {
wolfSSL 13:f67a6c6013ca 309 fp_mul_comba64(A,B,C);
wolfSSL 13:f67a6c6013ca 310 goto clean;
wolfSSL 13:f67a6c6013ca 311 }
wolfSSL 13:f67a6c6013ca 312 #endif
wolfSSL 13:f67a6c6013ca 313 fp_mul_comba(A,B,C);
wolfSSL 13:f67a6c6013ca 314
wolfSSL 13:f67a6c6013ca 315 clean:
wolfSSL 13:f67a6c6013ca 316 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 317 for (y = C->used; y >= 0 && y < oldused; y++) {
wolfSSL 13:f67a6c6013ca 318 C->dp[y] = 0;
wolfSSL 13:f67a6c6013ca 319 }
wolfSSL 13:f67a6c6013ca 320 }
wolfSSL 13:f67a6c6013ca 321
wolfSSL 13:f67a6c6013ca 322 void fp_mul_2(fp_int * a, fp_int * b)
wolfSSL 13:f67a6c6013ca 323 {
wolfSSL 13:f67a6c6013ca 324 int x, oldused;
wolfSSL 13:f67a6c6013ca 325
wolfSSL 13:f67a6c6013ca 326 oldused = b->used;
wolfSSL 13:f67a6c6013ca 327 b->used = a->used;
wolfSSL 13:f67a6c6013ca 328
wolfSSL 13:f67a6c6013ca 329 {
wolfSSL 13:f67a6c6013ca 330 fp_digit r, rr, *tmpa, *tmpb;
wolfSSL 13:f67a6c6013ca 331
wolfSSL 13:f67a6c6013ca 332 /* alias for source */
wolfSSL 13:f67a6c6013ca 333 tmpa = a->dp;
wolfSSL 13:f67a6c6013ca 334
wolfSSL 13:f67a6c6013ca 335 /* alias for dest */
wolfSSL 13:f67a6c6013ca 336 tmpb = b->dp;
wolfSSL 13:f67a6c6013ca 337
wolfSSL 13:f67a6c6013ca 338 /* carry */
wolfSSL 13:f67a6c6013ca 339 r = 0;
wolfSSL 13:f67a6c6013ca 340 for (x = 0; x < a->used; x++) {
wolfSSL 13:f67a6c6013ca 341
wolfSSL 13:f67a6c6013ca 342 /* get what will be the *next* carry bit from the
wolfSSL 13:f67a6c6013ca 343 * MSB of the current digit
wolfSSL 13:f67a6c6013ca 344 */
wolfSSL 13:f67a6c6013ca 345 rr = *tmpa >> ((fp_digit)(DIGIT_BIT - 1));
wolfSSL 13:f67a6c6013ca 346
wolfSSL 13:f67a6c6013ca 347 /* now shift up this digit, add in the carry [from the previous] */
wolfSSL 13:f67a6c6013ca 348 *tmpb++ = ((*tmpa++ << ((fp_digit)1)) | r);
wolfSSL 13:f67a6c6013ca 349
wolfSSL 13:f67a6c6013ca 350 /* copy the carry that would be from the source
wolfSSL 13:f67a6c6013ca 351 * digit into the next iteration
wolfSSL 13:f67a6c6013ca 352 */
wolfSSL 13:f67a6c6013ca 353 r = rr;
wolfSSL 13:f67a6c6013ca 354 }
wolfSSL 13:f67a6c6013ca 355
wolfSSL 13:f67a6c6013ca 356 /* new leading digit? */
wolfSSL 13:f67a6c6013ca 357 if (r != 0 && b->used != (FP_SIZE-1)) {
wolfSSL 13:f67a6c6013ca 358 /* add a MSB which is always 1 at this point */
wolfSSL 13:f67a6c6013ca 359 *tmpb = 1;
wolfSSL 13:f67a6c6013ca 360 ++(b->used);
wolfSSL 13:f67a6c6013ca 361 }
wolfSSL 13:f67a6c6013ca 362
wolfSSL 13:f67a6c6013ca 363 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 364 tmpb = b->dp + b->used;
wolfSSL 13:f67a6c6013ca 365 for (x = b->used; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 366 *tmpb++ = 0;
wolfSSL 13:f67a6c6013ca 367 }
wolfSSL 13:f67a6c6013ca 368 }
wolfSSL 13:f67a6c6013ca 369 b->sign = a->sign;
wolfSSL 13:f67a6c6013ca 370 }
wolfSSL 13:f67a6c6013ca 371
wolfSSL 13:f67a6c6013ca 372 /* c = a * b */
wolfSSL 13:f67a6c6013ca 373 void fp_mul_d(fp_int *a, fp_digit b, fp_int *c)
wolfSSL 13:f67a6c6013ca 374 {
wolfSSL 13:f67a6c6013ca 375 fp_word w;
wolfSSL 13:f67a6c6013ca 376 int x, oldused;
wolfSSL 13:f67a6c6013ca 377
wolfSSL 13:f67a6c6013ca 378 oldused = c->used;
wolfSSL 13:f67a6c6013ca 379 c->used = a->used;
wolfSSL 13:f67a6c6013ca 380 c->sign = a->sign;
wolfSSL 13:f67a6c6013ca 381 w = 0;
wolfSSL 13:f67a6c6013ca 382 for (x = 0; x < a->used; x++) {
wolfSSL 13:f67a6c6013ca 383 w = ((fp_word)a->dp[x]) * ((fp_word)b) + w;
wolfSSL 13:f67a6c6013ca 384 c->dp[x] = (fp_digit)w;
wolfSSL 13:f67a6c6013ca 385 w = w >> DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 386 }
wolfSSL 13:f67a6c6013ca 387 if (w != 0 && (a->used != FP_SIZE)) {
wolfSSL 13:f67a6c6013ca 388 c->dp[c->used++] = (fp_digit) w;
wolfSSL 13:f67a6c6013ca 389 ++x;
wolfSSL 13:f67a6c6013ca 390 }
wolfSSL 13:f67a6c6013ca 391
wolfSSL 13:f67a6c6013ca 392 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 393 for (; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 394 c->dp[x] = 0;
wolfSSL 13:f67a6c6013ca 395 }
wolfSSL 13:f67a6c6013ca 396 fp_clamp(c);
wolfSSL 13:f67a6c6013ca 397 }
wolfSSL 13:f67a6c6013ca 398
wolfSSL 13:f67a6c6013ca 399 /* c = a * 2**d */
wolfSSL 13:f67a6c6013ca 400 void fp_mul_2d(fp_int *a, int b, fp_int *c)
wolfSSL 13:f67a6c6013ca 401 {
wolfSSL 13:f67a6c6013ca 402 fp_digit carry, carrytmp, shift;
wolfSSL 13:f67a6c6013ca 403 int x;
wolfSSL 13:f67a6c6013ca 404
wolfSSL 13:f67a6c6013ca 405 /* copy it */
wolfSSL 13:f67a6c6013ca 406 fp_copy(a, c);
wolfSSL 13:f67a6c6013ca 407
wolfSSL 13:f67a6c6013ca 408 /* handle whole digits */
wolfSSL 13:f67a6c6013ca 409 if (b >= DIGIT_BIT) {
wolfSSL 13:f67a6c6013ca 410 fp_lshd(c, b/DIGIT_BIT);
wolfSSL 13:f67a6c6013ca 411 }
wolfSSL 13:f67a6c6013ca 412 b %= DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 413
wolfSSL 13:f67a6c6013ca 414 /* shift the digits */
wolfSSL 13:f67a6c6013ca 415 if (b != 0) {
wolfSSL 13:f67a6c6013ca 416 carry = 0;
wolfSSL 13:f67a6c6013ca 417 shift = DIGIT_BIT - b;
wolfSSL 13:f67a6c6013ca 418 for (x = 0; x < c->used; x++) {
wolfSSL 13:f67a6c6013ca 419 carrytmp = c->dp[x] >> shift;
wolfSSL 13:f67a6c6013ca 420 c->dp[x] = (c->dp[x] << b) + carry;
wolfSSL 13:f67a6c6013ca 421 carry = carrytmp;
wolfSSL 13:f67a6c6013ca 422 }
wolfSSL 13:f67a6c6013ca 423 /* store last carry if room */
wolfSSL 13:f67a6c6013ca 424 if (carry && x < FP_SIZE) {
wolfSSL 13:f67a6c6013ca 425 c->dp[c->used++] = carry;
wolfSSL 13:f67a6c6013ca 426 }
wolfSSL 13:f67a6c6013ca 427 }
wolfSSL 13:f67a6c6013ca 428 fp_clamp(c);
wolfSSL 13:f67a6c6013ca 429 }
wolfSSL 13:f67a6c6013ca 430
wolfSSL 13:f67a6c6013ca 431 /* generic PxQ multiplier */
wolfSSL 13:f67a6c6013ca 432 #if defined(HAVE_INTEL_MULX)
wolfSSL 13:f67a6c6013ca 433
wolfSSL 13:f67a6c6013ca 434 INLINE static void fp_mul_comba_mulx(fp_int *A, fp_int *B, fp_int *C)
wolfSSL 13:f67a6c6013ca 435
wolfSSL 13:f67a6c6013ca 436 {
wolfSSL 13:f67a6c6013ca 437 int ix, iy, iz, pa;
wolfSSL 13:f67a6c6013ca 438 fp_int tmp, *dst;
wolfSSL 13:f67a6c6013ca 439
wolfSSL 13:f67a6c6013ca 440 /* get size of output and trim */
wolfSSL 13:f67a6c6013ca 441 pa = A->used + B->used;
wolfSSL 13:f67a6c6013ca 442 if (pa >= FP_SIZE) {
wolfSSL 13:f67a6c6013ca 443 pa = FP_SIZE-1;
wolfSSL 13:f67a6c6013ca 444 }
wolfSSL 13:f67a6c6013ca 445
wolfSSL 13:f67a6c6013ca 446 /* Always take branch to use tmp variable. This avoids a cache attack for
wolfSSL 13:f67a6c6013ca 447 * determining if C equals A */
wolfSSL 13:f67a6c6013ca 448 if (1) {
wolfSSL 13:f67a6c6013ca 449 fp_init(&tmp);
wolfSSL 13:f67a6c6013ca 450 dst = &tmp;
wolfSSL 13:f67a6c6013ca 451 }
wolfSSL 13:f67a6c6013ca 452
wolfSSL 13:f67a6c6013ca 453 TFM_INTEL_MUL_COMBA(A, B, dst) ;
wolfSSL 13:f67a6c6013ca 454
wolfSSL 13:f67a6c6013ca 455 dst->used = pa;
wolfSSL 13:f67a6c6013ca 456 dst->sign = A->sign ^ B->sign;
wolfSSL 13:f67a6c6013ca 457 fp_clamp(dst);
wolfSSL 13:f67a6c6013ca 458 fp_copy(dst, C);
wolfSSL 13:f67a6c6013ca 459 }
wolfSSL 13:f67a6c6013ca 460 #endif
wolfSSL 13:f67a6c6013ca 461
wolfSSL 13:f67a6c6013ca 462 void fp_mul_comba(fp_int *A, fp_int *B, fp_int *C)
wolfSSL 13:f67a6c6013ca 463 {
wolfSSL 13:f67a6c6013ca 464 int ix, iy, iz, tx, ty, pa;
wolfSSL 13:f67a6c6013ca 465 fp_digit c0, c1, c2, *tmpx, *tmpy;
wolfSSL 13:f67a6c6013ca 466 fp_int tmp, *dst;
wolfSSL 13:f67a6c6013ca 467
wolfSSL 13:f67a6c6013ca 468 IF_HAVE_INTEL_MULX(fp_mul_comba_mulx(A, B, C), return) ;
wolfSSL 13:f67a6c6013ca 469
wolfSSL 13:f67a6c6013ca 470 COMBA_START;
wolfSSL 13:f67a6c6013ca 471 COMBA_CLEAR;
wolfSSL 13:f67a6c6013ca 472
wolfSSL 13:f67a6c6013ca 473 /* get size of output and trim */
wolfSSL 13:f67a6c6013ca 474 pa = A->used + B->used;
wolfSSL 13:f67a6c6013ca 475 if (pa >= FP_SIZE) {
wolfSSL 13:f67a6c6013ca 476 pa = FP_SIZE-1;
wolfSSL 13:f67a6c6013ca 477 }
wolfSSL 13:f67a6c6013ca 478
wolfSSL 13:f67a6c6013ca 479 /* Always take branch to use tmp variable. This avoids a cache attack for
wolfSSL 13:f67a6c6013ca 480 * determining if C equals A */
wolfSSL 13:f67a6c6013ca 481 if (1) {
wolfSSL 13:f67a6c6013ca 482 fp_init(&tmp);
wolfSSL 13:f67a6c6013ca 483 dst = &tmp;
wolfSSL 13:f67a6c6013ca 484 }
wolfSSL 13:f67a6c6013ca 485
wolfSSL 13:f67a6c6013ca 486 for (ix = 0; ix < pa; ix++) {
wolfSSL 13:f67a6c6013ca 487 /* get offsets into the two bignums */
wolfSSL 13:f67a6c6013ca 488 ty = MIN(ix, B->used-1);
wolfSSL 13:f67a6c6013ca 489 tx = ix - ty;
wolfSSL 13:f67a6c6013ca 490
wolfSSL 13:f67a6c6013ca 491 /* setup temp aliases */
wolfSSL 13:f67a6c6013ca 492 tmpx = A->dp + tx;
wolfSSL 13:f67a6c6013ca 493 tmpy = B->dp + ty;
wolfSSL 13:f67a6c6013ca 494
wolfSSL 13:f67a6c6013ca 495 /* this is the number of times the loop will iterate, essentially its
wolfSSL 13:f67a6c6013ca 496 while (tx++ < a->used && ty-- >= 0) { ... }
wolfSSL 13:f67a6c6013ca 497 */
wolfSSL 13:f67a6c6013ca 498 iy = MIN(A->used-tx, ty+1);
wolfSSL 13:f67a6c6013ca 499
wolfSSL 13:f67a6c6013ca 500 /* execute loop */
wolfSSL 13:f67a6c6013ca 501 COMBA_FORWARD;
wolfSSL 13:f67a6c6013ca 502 for (iz = 0; iz < iy; ++iz) {
wolfSSL 13:f67a6c6013ca 503 fp_digit _tmpx = *tmpx++;
wolfSSL 13:f67a6c6013ca 504 fp_digit _tmpy = *tmpy--;
wolfSSL 13:f67a6c6013ca 505 MULADD(_tmpx, _tmpy);
wolfSSL 13:f67a6c6013ca 506 }
wolfSSL 13:f67a6c6013ca 507
wolfSSL 13:f67a6c6013ca 508 /* store term */
wolfSSL 13:f67a6c6013ca 509 COMBA_STORE(dst->dp[ix]);
wolfSSL 13:f67a6c6013ca 510 }
wolfSSL 13:f67a6c6013ca 511 COMBA_FINI;
wolfSSL 13:f67a6c6013ca 512
wolfSSL 13:f67a6c6013ca 513 dst->used = pa;
wolfSSL 13:f67a6c6013ca 514 dst->sign = A->sign ^ B->sign;
wolfSSL 13:f67a6c6013ca 515 fp_clamp(dst);
wolfSSL 13:f67a6c6013ca 516 fp_copy(dst, C);
wolfSSL 13:f67a6c6013ca 517 }
wolfSSL 13:f67a6c6013ca 518
wolfSSL 13:f67a6c6013ca 519 /* a/b => cb + d == a */
wolfSSL 13:f67a6c6013ca 520 int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
wolfSSL 13:f67a6c6013ca 521 {
wolfSSL 13:f67a6c6013ca 522 fp_int q, x, y, t1, t2;
wolfSSL 13:f67a6c6013ca 523 int n, t, i, norm, neg;
wolfSSL 13:f67a6c6013ca 524
wolfSSL 13:f67a6c6013ca 525 /* is divisor zero ? */
wolfSSL 13:f67a6c6013ca 526 if (fp_iszero (b) == FP_YES) {
wolfSSL 13:f67a6c6013ca 527 return FP_VAL;
wolfSSL 13:f67a6c6013ca 528 }
wolfSSL 13:f67a6c6013ca 529
wolfSSL 13:f67a6c6013ca 530 /* if a < b then q=0, r = a */
wolfSSL 13:f67a6c6013ca 531 if (fp_cmp_mag (a, b) == FP_LT) {
wolfSSL 13:f67a6c6013ca 532 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 533 fp_copy (a, d);
wolfSSL 13:f67a6c6013ca 534 }
wolfSSL 13:f67a6c6013ca 535 if (c != NULL) {
wolfSSL 13:f67a6c6013ca 536 fp_zero (c);
wolfSSL 13:f67a6c6013ca 537 }
wolfSSL 13:f67a6c6013ca 538 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 539 }
wolfSSL 13:f67a6c6013ca 540
wolfSSL 13:f67a6c6013ca 541 fp_init(&q);
wolfSSL 13:f67a6c6013ca 542 q.used = a->used + 2;
wolfSSL 13:f67a6c6013ca 543
wolfSSL 13:f67a6c6013ca 544 fp_init(&t1);
wolfSSL 13:f67a6c6013ca 545 fp_init(&t2);
wolfSSL 13:f67a6c6013ca 546 fp_init_copy(&x, a);
wolfSSL 13:f67a6c6013ca 547 fp_init_copy(&y, b);
wolfSSL 13:f67a6c6013ca 548
wolfSSL 13:f67a6c6013ca 549 /* fix the sign */
wolfSSL 13:f67a6c6013ca 550 neg = (a->sign == b->sign) ? FP_ZPOS : FP_NEG;
wolfSSL 13:f67a6c6013ca 551 x.sign = y.sign = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 552
wolfSSL 13:f67a6c6013ca 553 /* normalize both x and y, ensure that y >= b/2, [b == 2**DIGIT_BIT] */
wolfSSL 13:f67a6c6013ca 554 norm = fp_count_bits(&y) % DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 555 if (norm < (int)(DIGIT_BIT-1)) {
wolfSSL 13:f67a6c6013ca 556 norm = (DIGIT_BIT-1) - norm;
wolfSSL 13:f67a6c6013ca 557 fp_mul_2d (&x, norm, &x);
wolfSSL 13:f67a6c6013ca 558 fp_mul_2d (&y, norm, &y);
wolfSSL 13:f67a6c6013ca 559 } else {
wolfSSL 13:f67a6c6013ca 560 norm = 0;
wolfSSL 13:f67a6c6013ca 561 }
wolfSSL 13:f67a6c6013ca 562
wolfSSL 13:f67a6c6013ca 563 /* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */
wolfSSL 13:f67a6c6013ca 564 n = x.used - 1;
wolfSSL 13:f67a6c6013ca 565 t = y.used - 1;
wolfSSL 13:f67a6c6013ca 566
wolfSSL 13:f67a6c6013ca 567 /* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */
wolfSSL 13:f67a6c6013ca 568 fp_lshd (&y, n - t); /* y = y*b**{n-t} */
wolfSSL 13:f67a6c6013ca 569
wolfSSL 13:f67a6c6013ca 570 while (fp_cmp (&x, &y) != FP_LT) {
wolfSSL 13:f67a6c6013ca 571 ++(q.dp[n - t]);
wolfSSL 13:f67a6c6013ca 572 fp_sub (&x, &y, &x);
wolfSSL 13:f67a6c6013ca 573 }
wolfSSL 13:f67a6c6013ca 574
wolfSSL 13:f67a6c6013ca 575 /* reset y by shifting it back down */
wolfSSL 13:f67a6c6013ca 576 fp_rshd (&y, n - t);
wolfSSL 13:f67a6c6013ca 577
wolfSSL 13:f67a6c6013ca 578 /* step 3. for i from n down to (t + 1) */
wolfSSL 13:f67a6c6013ca 579 for (i = n; i >= (t + 1); i--) {
wolfSSL 13:f67a6c6013ca 580 if (i > x.used) {
wolfSSL 13:f67a6c6013ca 581 continue;
wolfSSL 13:f67a6c6013ca 582 }
wolfSSL 13:f67a6c6013ca 583
wolfSSL 13:f67a6c6013ca 584 /* step 3.1 if xi == yt then set q{i-t-1} to b-1,
wolfSSL 13:f67a6c6013ca 585 * otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */
wolfSSL 13:f67a6c6013ca 586 if (x.dp[i] == y.dp[t]) {
wolfSSL 13:f67a6c6013ca 587 q.dp[i - t - 1] = (fp_digit) ((((fp_word)1) << DIGIT_BIT) - 1);
wolfSSL 13:f67a6c6013ca 588 } else {
wolfSSL 13:f67a6c6013ca 589 fp_word tmp;
wolfSSL 13:f67a6c6013ca 590 tmp = ((fp_word) x.dp[i]) << ((fp_word) DIGIT_BIT);
wolfSSL 13:f67a6c6013ca 591 tmp |= ((fp_word) x.dp[i - 1]);
wolfSSL 13:f67a6c6013ca 592 tmp /= ((fp_word)y.dp[t]);
wolfSSL 13:f67a6c6013ca 593 q.dp[i - t - 1] = (fp_digit) (tmp);
wolfSSL 13:f67a6c6013ca 594 }
wolfSSL 13:f67a6c6013ca 595
wolfSSL 13:f67a6c6013ca 596 /* while (q{i-t-1} * (yt * b + y{t-1})) >
wolfSSL 13:f67a6c6013ca 597 xi * b**2 + xi-1 * b + xi-2
wolfSSL 13:f67a6c6013ca 598
wolfSSL 13:f67a6c6013ca 599 do q{i-t-1} -= 1;
wolfSSL 13:f67a6c6013ca 600 */
wolfSSL 13:f67a6c6013ca 601 q.dp[i - t - 1] = (q.dp[i - t - 1] + 1);
wolfSSL 13:f67a6c6013ca 602 do {
wolfSSL 13:f67a6c6013ca 603 q.dp[i - t - 1] = (q.dp[i - t - 1] - 1);
wolfSSL 13:f67a6c6013ca 604
wolfSSL 13:f67a6c6013ca 605 /* find left hand */
wolfSSL 13:f67a6c6013ca 606 fp_zero (&t1);
wolfSSL 13:f67a6c6013ca 607 t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
wolfSSL 13:f67a6c6013ca 608 t1.dp[1] = y.dp[t];
wolfSSL 13:f67a6c6013ca 609 t1.used = 2;
wolfSSL 13:f67a6c6013ca 610 fp_mul_d (&t1, q.dp[i - t - 1], &t1);
wolfSSL 13:f67a6c6013ca 611
wolfSSL 13:f67a6c6013ca 612 /* find right hand */
wolfSSL 13:f67a6c6013ca 613 t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
wolfSSL 13:f67a6c6013ca 614 t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
wolfSSL 13:f67a6c6013ca 615 t2.dp[2] = x.dp[i];
wolfSSL 13:f67a6c6013ca 616 t2.used = 3;
wolfSSL 13:f67a6c6013ca 617 } while (fp_cmp_mag(&t1, &t2) == FP_GT);
wolfSSL 13:f67a6c6013ca 618
wolfSSL 13:f67a6c6013ca 619 /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */
wolfSSL 13:f67a6c6013ca 620 fp_mul_d (&y, q.dp[i - t - 1], &t1);
wolfSSL 13:f67a6c6013ca 621 fp_lshd (&t1, i - t - 1);
wolfSSL 13:f67a6c6013ca 622 fp_sub (&x, &t1, &x);
wolfSSL 13:f67a6c6013ca 623
wolfSSL 13:f67a6c6013ca 624 /* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */
wolfSSL 13:f67a6c6013ca 625 if (x.sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 626 fp_copy (&y, &t1);
wolfSSL 13:f67a6c6013ca 627 fp_lshd (&t1, i - t - 1);
wolfSSL 13:f67a6c6013ca 628 fp_add (&x, &t1, &x);
wolfSSL 13:f67a6c6013ca 629 q.dp[i - t - 1] = q.dp[i - t - 1] - 1;
wolfSSL 13:f67a6c6013ca 630 }
wolfSSL 13:f67a6c6013ca 631 }
wolfSSL 13:f67a6c6013ca 632
wolfSSL 13:f67a6c6013ca 633 /* now q is the quotient and x is the remainder
wolfSSL 13:f67a6c6013ca 634 * [which we have to normalize]
wolfSSL 13:f67a6c6013ca 635 */
wolfSSL 13:f67a6c6013ca 636
wolfSSL 13:f67a6c6013ca 637 /* get sign before writing to c */
wolfSSL 13:f67a6c6013ca 638 x.sign = x.used == 0 ? FP_ZPOS : a->sign;
wolfSSL 13:f67a6c6013ca 639
wolfSSL 13:f67a6c6013ca 640 if (c != NULL) {
wolfSSL 13:f67a6c6013ca 641 fp_clamp (&q);
wolfSSL 13:f67a6c6013ca 642 fp_copy (&q, c);
wolfSSL 13:f67a6c6013ca 643 c->sign = neg;
wolfSSL 13:f67a6c6013ca 644 }
wolfSSL 13:f67a6c6013ca 645
wolfSSL 13:f67a6c6013ca 646 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 647 fp_div_2d (&x, norm, &x, NULL);
wolfSSL 13:f67a6c6013ca 648
wolfSSL 13:f67a6c6013ca 649 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 650 for (i = b->used; i < x.used; i++) {
wolfSSL 13:f67a6c6013ca 651 x.dp[i] = 0;
wolfSSL 13:f67a6c6013ca 652 }
wolfSSL 13:f67a6c6013ca 653 fp_clamp(&x);
wolfSSL 13:f67a6c6013ca 654 fp_copy (&x, d);
wolfSSL 13:f67a6c6013ca 655 }
wolfSSL 13:f67a6c6013ca 656
wolfSSL 13:f67a6c6013ca 657 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 658 }
wolfSSL 13:f67a6c6013ca 659
wolfSSL 13:f67a6c6013ca 660 /* b = a/2 */
wolfSSL 13:f67a6c6013ca 661 void fp_div_2(fp_int * a, fp_int * b)
wolfSSL 13:f67a6c6013ca 662 {
wolfSSL 13:f67a6c6013ca 663 int x, oldused;
wolfSSL 13:f67a6c6013ca 664
wolfSSL 13:f67a6c6013ca 665 oldused = b->used;
wolfSSL 13:f67a6c6013ca 666 b->used = a->used;
wolfSSL 13:f67a6c6013ca 667 {
wolfSSL 13:f67a6c6013ca 668 fp_digit r, rr, *tmpa, *tmpb;
wolfSSL 13:f67a6c6013ca 669
wolfSSL 13:f67a6c6013ca 670 /* source alias */
wolfSSL 13:f67a6c6013ca 671 tmpa = a->dp + b->used - 1;
wolfSSL 13:f67a6c6013ca 672
wolfSSL 13:f67a6c6013ca 673 /* dest alias */
wolfSSL 13:f67a6c6013ca 674 tmpb = b->dp + b->used - 1;
wolfSSL 13:f67a6c6013ca 675
wolfSSL 13:f67a6c6013ca 676 /* carry */
wolfSSL 13:f67a6c6013ca 677 r = 0;
wolfSSL 13:f67a6c6013ca 678 for (x = b->used - 1; x >= 0; x--) {
wolfSSL 13:f67a6c6013ca 679 /* get the carry for the next iteration */
wolfSSL 13:f67a6c6013ca 680 rr = *tmpa & 1;
wolfSSL 13:f67a6c6013ca 681
wolfSSL 13:f67a6c6013ca 682 /* shift the current digit, add in carry and store */
wolfSSL 13:f67a6c6013ca 683 *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
wolfSSL 13:f67a6c6013ca 684
wolfSSL 13:f67a6c6013ca 685 /* forward carry to next iteration */
wolfSSL 13:f67a6c6013ca 686 r = rr;
wolfSSL 13:f67a6c6013ca 687 }
wolfSSL 13:f67a6c6013ca 688
wolfSSL 13:f67a6c6013ca 689 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 690 tmpb = b->dp + b->used;
wolfSSL 13:f67a6c6013ca 691 for (x = b->used; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 692 *tmpb++ = 0;
wolfSSL 13:f67a6c6013ca 693 }
wolfSSL 13:f67a6c6013ca 694 }
wolfSSL 13:f67a6c6013ca 695 b->sign = a->sign;
wolfSSL 13:f67a6c6013ca 696 fp_clamp (b);
wolfSSL 13:f67a6c6013ca 697 }
wolfSSL 13:f67a6c6013ca 698
wolfSSL 13:f67a6c6013ca 699 /* c = a / 2**b */
wolfSSL 13:f67a6c6013ca 700 void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d)
wolfSSL 13:f67a6c6013ca 701 {
wolfSSL 13:f67a6c6013ca 702 int D;
wolfSSL 13:f67a6c6013ca 703 fp_int t;
wolfSSL 13:f67a6c6013ca 704
wolfSSL 13:f67a6c6013ca 705 /* if the shift count is <= 0 then we do no work */
wolfSSL 13:f67a6c6013ca 706 if (b <= 0) {
wolfSSL 13:f67a6c6013ca 707 fp_copy (a, c);
wolfSSL 13:f67a6c6013ca 708 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 709 fp_zero (d);
wolfSSL 13:f67a6c6013ca 710 }
wolfSSL 13:f67a6c6013ca 711 return;
wolfSSL 13:f67a6c6013ca 712 }
wolfSSL 13:f67a6c6013ca 713
wolfSSL 13:f67a6c6013ca 714 fp_init(&t);
wolfSSL 13:f67a6c6013ca 715
wolfSSL 13:f67a6c6013ca 716 /* get the remainder */
wolfSSL 13:f67a6c6013ca 717 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 718 fp_mod_2d (a, b, &t);
wolfSSL 13:f67a6c6013ca 719 }
wolfSSL 13:f67a6c6013ca 720
wolfSSL 13:f67a6c6013ca 721 /* copy */
wolfSSL 13:f67a6c6013ca 722 fp_copy(a, c);
wolfSSL 13:f67a6c6013ca 723
wolfSSL 13:f67a6c6013ca 724 /* shift by as many digits in the bit count */
wolfSSL 13:f67a6c6013ca 725 if (b >= (int)DIGIT_BIT) {
wolfSSL 13:f67a6c6013ca 726 fp_rshd (c, b / DIGIT_BIT);
wolfSSL 13:f67a6c6013ca 727 }
wolfSSL 13:f67a6c6013ca 728
wolfSSL 13:f67a6c6013ca 729 /* shift any bit count < DIGIT_BIT */
wolfSSL 13:f67a6c6013ca 730 D = (b % DIGIT_BIT);
wolfSSL 13:f67a6c6013ca 731 if (D != 0) {
wolfSSL 13:f67a6c6013ca 732 fp_rshb(c, D);
wolfSSL 13:f67a6c6013ca 733 }
wolfSSL 13:f67a6c6013ca 734 fp_clamp (c);
wolfSSL 13:f67a6c6013ca 735 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 736 fp_copy (&t, d);
wolfSSL 13:f67a6c6013ca 737 }
wolfSSL 13:f67a6c6013ca 738 }
wolfSSL 13:f67a6c6013ca 739
wolfSSL 13:f67a6c6013ca 740 /* c = a mod b, 0 <= c < b */
wolfSSL 13:f67a6c6013ca 741 int fp_mod(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 742 {
wolfSSL 13:f67a6c6013ca 743 fp_int t;
wolfSSL 13:f67a6c6013ca 744 int err;
wolfSSL 13:f67a6c6013ca 745
wolfSSL 13:f67a6c6013ca 746 fp_init(&t);
wolfSSL 13:f67a6c6013ca 747 if ((err = fp_div(a, b, NULL, &t)) != FP_OKAY) {
wolfSSL 13:f67a6c6013ca 748 return err;
wolfSSL 13:f67a6c6013ca 749 }
wolfSSL 13:f67a6c6013ca 750 if (t.sign != b->sign) {
wolfSSL 13:f67a6c6013ca 751 fp_add(&t, b, c);
wolfSSL 13:f67a6c6013ca 752 } else {
wolfSSL 13:f67a6c6013ca 753 fp_copy(&t, c);
wolfSSL 13:f67a6c6013ca 754 }
wolfSSL 13:f67a6c6013ca 755 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 756 }
wolfSSL 13:f67a6c6013ca 757
wolfSSL 13:f67a6c6013ca 758 /* c = a mod 2**d */
wolfSSL 13:f67a6c6013ca 759 void fp_mod_2d(fp_int *a, int b, fp_int *c)
wolfSSL 13:f67a6c6013ca 760 {
wolfSSL 13:f67a6c6013ca 761 int x;
wolfSSL 13:f67a6c6013ca 762
wolfSSL 13:f67a6c6013ca 763 /* zero if count less than or equal to zero */
wolfSSL 13:f67a6c6013ca 764 if (b <= 0) {
wolfSSL 13:f67a6c6013ca 765 fp_zero(c);
wolfSSL 13:f67a6c6013ca 766 return;
wolfSSL 13:f67a6c6013ca 767 }
wolfSSL 13:f67a6c6013ca 768
wolfSSL 13:f67a6c6013ca 769 /* get copy of input */
wolfSSL 13:f67a6c6013ca 770 fp_copy(a, c);
wolfSSL 13:f67a6c6013ca 771
wolfSSL 13:f67a6c6013ca 772 /* if 2**d is larger than we just return */
wolfSSL 13:f67a6c6013ca 773 if (b >= (DIGIT_BIT * a->used)) {
wolfSSL 13:f67a6c6013ca 774 return;
wolfSSL 13:f67a6c6013ca 775 }
wolfSSL 13:f67a6c6013ca 776
wolfSSL 13:f67a6c6013ca 777 /* zero digits above the last digit of the modulus */
wolfSSL 13:f67a6c6013ca 778 for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++) {
wolfSSL 13:f67a6c6013ca 779 c->dp[x] = 0;
wolfSSL 13:f67a6c6013ca 780 }
wolfSSL 13:f67a6c6013ca 781 /* clear the digit that is not completely outside/inside the modulus */
wolfSSL 13:f67a6c6013ca 782 c->dp[b / DIGIT_BIT] &= ~((fp_digit)0) >> (DIGIT_BIT - b);
wolfSSL 13:f67a6c6013ca 783 fp_clamp (c);
wolfSSL 13:f67a6c6013ca 784 }
wolfSSL 13:f67a6c6013ca 785
wolfSSL 13:f67a6c6013ca 786 static int fp_invmod_slow (fp_int * a, fp_int * b, fp_int * c)
wolfSSL 13:f67a6c6013ca 787 {
wolfSSL 13:f67a6c6013ca 788 fp_int x, y, u, v, A, B, C, D;
wolfSSL 13:f67a6c6013ca 789 int res;
wolfSSL 13:f67a6c6013ca 790
wolfSSL 13:f67a6c6013ca 791 /* b cannot be negative */
wolfSSL 13:f67a6c6013ca 792 if (b->sign == FP_NEG || fp_iszero(b) == FP_YES) {
wolfSSL 13:f67a6c6013ca 793 return FP_VAL;
wolfSSL 13:f67a6c6013ca 794 }
wolfSSL 13:f67a6c6013ca 795
wolfSSL 13:f67a6c6013ca 796 /* init temps */
wolfSSL 13:f67a6c6013ca 797 fp_init(&x); fp_init(&y);
wolfSSL 13:f67a6c6013ca 798 fp_init(&u); fp_init(&v);
wolfSSL 13:f67a6c6013ca 799 fp_init(&A); fp_init(&B);
wolfSSL 13:f67a6c6013ca 800 fp_init(&C); fp_init(&D);
wolfSSL 13:f67a6c6013ca 801
wolfSSL 13:f67a6c6013ca 802 /* x = a, y = b */
wolfSSL 13:f67a6c6013ca 803 if ((res = fp_mod(a, b, &x)) != FP_OKAY) {
wolfSSL 13:f67a6c6013ca 804 return res;
wolfSSL 13:f67a6c6013ca 805 }
wolfSSL 13:f67a6c6013ca 806 fp_copy(b, &y);
wolfSSL 13:f67a6c6013ca 807
wolfSSL 13:f67a6c6013ca 808 /* 2. [modified] if x,y are both even then return an error! */
wolfSSL 13:f67a6c6013ca 809 if (fp_iseven (&x) == FP_YES && fp_iseven (&y) == FP_YES) {
wolfSSL 13:f67a6c6013ca 810 return FP_VAL;
wolfSSL 13:f67a6c6013ca 811 }
wolfSSL 13:f67a6c6013ca 812
wolfSSL 13:f67a6c6013ca 813 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
wolfSSL 13:f67a6c6013ca 814 fp_copy (&x, &u);
wolfSSL 13:f67a6c6013ca 815 fp_copy (&y, &v);
wolfSSL 13:f67a6c6013ca 816 fp_set (&A, 1);
wolfSSL 13:f67a6c6013ca 817 fp_set (&D, 1);
wolfSSL 13:f67a6c6013ca 818
wolfSSL 13:f67a6c6013ca 819 top:
wolfSSL 13:f67a6c6013ca 820 /* 4. while u is even do */
wolfSSL 13:f67a6c6013ca 821 while (fp_iseven (&u) == FP_YES) {
wolfSSL 13:f67a6c6013ca 822 /* 4.1 u = u/2 */
wolfSSL 13:f67a6c6013ca 823 fp_div_2 (&u, &u);
wolfSSL 13:f67a6c6013ca 824
wolfSSL 13:f67a6c6013ca 825 /* 4.2 if A or B is odd then */
wolfSSL 13:f67a6c6013ca 826 if (fp_isodd (&A) == FP_YES || fp_isodd (&B) == FP_YES) {
wolfSSL 13:f67a6c6013ca 827 /* A = (A+y)/2, B = (B-x)/2 */
wolfSSL 13:f67a6c6013ca 828 fp_add (&A, &y, &A);
wolfSSL 13:f67a6c6013ca 829 fp_sub (&B, &x, &B);
wolfSSL 13:f67a6c6013ca 830 }
wolfSSL 13:f67a6c6013ca 831 /* A = A/2, B = B/2 */
wolfSSL 13:f67a6c6013ca 832 fp_div_2 (&A, &A);
wolfSSL 13:f67a6c6013ca 833 fp_div_2 (&B, &B);
wolfSSL 13:f67a6c6013ca 834 }
wolfSSL 13:f67a6c6013ca 835
wolfSSL 13:f67a6c6013ca 836 /* 5. while v is even do */
wolfSSL 13:f67a6c6013ca 837 while (fp_iseven (&v) == FP_YES) {
wolfSSL 13:f67a6c6013ca 838 /* 5.1 v = v/2 */
wolfSSL 13:f67a6c6013ca 839 fp_div_2 (&v, &v);
wolfSSL 13:f67a6c6013ca 840
wolfSSL 13:f67a6c6013ca 841 /* 5.2 if C or D is odd then */
wolfSSL 13:f67a6c6013ca 842 if (fp_isodd (&C) == FP_YES || fp_isodd (&D) == FP_YES) {
wolfSSL 13:f67a6c6013ca 843 /* C = (C+y)/2, D = (D-x)/2 */
wolfSSL 13:f67a6c6013ca 844 fp_add (&C, &y, &C);
wolfSSL 13:f67a6c6013ca 845 fp_sub (&D, &x, &D);
wolfSSL 13:f67a6c6013ca 846 }
wolfSSL 13:f67a6c6013ca 847 /* C = C/2, D = D/2 */
wolfSSL 13:f67a6c6013ca 848 fp_div_2 (&C, &C);
wolfSSL 13:f67a6c6013ca 849 fp_div_2 (&D, &D);
wolfSSL 13:f67a6c6013ca 850 }
wolfSSL 13:f67a6c6013ca 851
wolfSSL 13:f67a6c6013ca 852 /* 6. if u >= v then */
wolfSSL 13:f67a6c6013ca 853 if (fp_cmp (&u, &v) != FP_LT) {
wolfSSL 13:f67a6c6013ca 854 /* u = u - v, A = A - C, B = B - D */
wolfSSL 13:f67a6c6013ca 855 fp_sub (&u, &v, &u);
wolfSSL 13:f67a6c6013ca 856 fp_sub (&A, &C, &A);
wolfSSL 13:f67a6c6013ca 857 fp_sub (&B, &D, &B);
wolfSSL 13:f67a6c6013ca 858 } else {
wolfSSL 13:f67a6c6013ca 859 /* v - v - u, C = C - A, D = D - B */
wolfSSL 13:f67a6c6013ca 860 fp_sub (&v, &u, &v);
wolfSSL 13:f67a6c6013ca 861 fp_sub (&C, &A, &C);
wolfSSL 13:f67a6c6013ca 862 fp_sub (&D, &B, &D);
wolfSSL 13:f67a6c6013ca 863 }
wolfSSL 13:f67a6c6013ca 864
wolfSSL 13:f67a6c6013ca 865 /* if not zero goto step 4 */
wolfSSL 13:f67a6c6013ca 866 if (fp_iszero (&u) == FP_NO)
wolfSSL 13:f67a6c6013ca 867 goto top;
wolfSSL 13:f67a6c6013ca 868
wolfSSL 13:f67a6c6013ca 869 /* now a = C, b = D, gcd == g*v */
wolfSSL 13:f67a6c6013ca 870
wolfSSL 13:f67a6c6013ca 871 /* if v != 1 then there is no inverse */
wolfSSL 13:f67a6c6013ca 872 if (fp_cmp_d (&v, 1) != FP_EQ) {
wolfSSL 13:f67a6c6013ca 873 return FP_VAL;
wolfSSL 13:f67a6c6013ca 874 }
wolfSSL 13:f67a6c6013ca 875
wolfSSL 13:f67a6c6013ca 876 /* if its too low */
wolfSSL 13:f67a6c6013ca 877 while (fp_cmp_d(&C, 0) == FP_LT) {
wolfSSL 13:f67a6c6013ca 878 fp_add(&C, b, &C);
wolfSSL 13:f67a6c6013ca 879 }
wolfSSL 13:f67a6c6013ca 880
wolfSSL 13:f67a6c6013ca 881 /* too big */
wolfSSL 13:f67a6c6013ca 882 while (fp_cmp_mag(&C, b) != FP_LT) {
wolfSSL 13:f67a6c6013ca 883 fp_sub(&C, b, &C);
wolfSSL 13:f67a6c6013ca 884 }
wolfSSL 13:f67a6c6013ca 885
wolfSSL 13:f67a6c6013ca 886 /* C is now the inverse */
wolfSSL 13:f67a6c6013ca 887 fp_copy(&C, c);
wolfSSL 13:f67a6c6013ca 888 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 889 }
wolfSSL 13:f67a6c6013ca 890
wolfSSL 13:f67a6c6013ca 891 /* c = 1/a (mod b) for odd b only */
wolfSSL 13:f67a6c6013ca 892 int fp_invmod(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 893 {
wolfSSL 13:f67a6c6013ca 894 fp_int x, y, u, v, B, D;
wolfSSL 13:f67a6c6013ca 895 int neg;
wolfSSL 13:f67a6c6013ca 896
wolfSSL 13:f67a6c6013ca 897 /* 2. [modified] b must be odd */
wolfSSL 13:f67a6c6013ca 898 if (fp_iseven (b) == FP_YES) {
wolfSSL 13:f67a6c6013ca 899 return fp_invmod_slow(a,b,c);
wolfSSL 13:f67a6c6013ca 900 }
wolfSSL 13:f67a6c6013ca 901
wolfSSL 13:f67a6c6013ca 902 /* init all our temps */
wolfSSL 13:f67a6c6013ca 903 fp_init(&x); fp_init(&y);
wolfSSL 13:f67a6c6013ca 904 fp_init(&u); fp_init(&v);
wolfSSL 13:f67a6c6013ca 905 fp_init(&B); fp_init(&D);
wolfSSL 13:f67a6c6013ca 906
wolfSSL 13:f67a6c6013ca 907 /* x == modulus, y == value to invert */
wolfSSL 13:f67a6c6013ca 908 fp_copy(b, &x);
wolfSSL 13:f67a6c6013ca 909
wolfSSL 13:f67a6c6013ca 910 /* we need y = |a| */
wolfSSL 13:f67a6c6013ca 911 fp_abs(a, &y);
wolfSSL 13:f67a6c6013ca 912
wolfSSL 13:f67a6c6013ca 913 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
wolfSSL 13:f67a6c6013ca 914 fp_copy(&x, &u);
wolfSSL 13:f67a6c6013ca 915 fp_copy(&y, &v);
wolfSSL 13:f67a6c6013ca 916 fp_set (&D, 1);
wolfSSL 13:f67a6c6013ca 917
wolfSSL 13:f67a6c6013ca 918 top:
wolfSSL 13:f67a6c6013ca 919 /* 4. while u is even do */
wolfSSL 13:f67a6c6013ca 920 while (fp_iseven (&u) == FP_YES) {
wolfSSL 13:f67a6c6013ca 921 /* 4.1 u = u/2 */
wolfSSL 13:f67a6c6013ca 922 fp_div_2 (&u, &u);
wolfSSL 13:f67a6c6013ca 923
wolfSSL 13:f67a6c6013ca 924 /* 4.2 if B is odd then */
wolfSSL 13:f67a6c6013ca 925 if (fp_isodd (&B) == FP_YES) {
wolfSSL 13:f67a6c6013ca 926 fp_sub (&B, &x, &B);
wolfSSL 13:f67a6c6013ca 927 }
wolfSSL 13:f67a6c6013ca 928 /* B = B/2 */
wolfSSL 13:f67a6c6013ca 929 fp_div_2 (&B, &B);
wolfSSL 13:f67a6c6013ca 930 }
wolfSSL 13:f67a6c6013ca 931
wolfSSL 13:f67a6c6013ca 932 /* 5. while v is even do */
wolfSSL 13:f67a6c6013ca 933 while (fp_iseven (&v) == FP_YES) {
wolfSSL 13:f67a6c6013ca 934 /* 5.1 v = v/2 */
wolfSSL 13:f67a6c6013ca 935 fp_div_2 (&v, &v);
wolfSSL 13:f67a6c6013ca 936
wolfSSL 13:f67a6c6013ca 937 /* 5.2 if D is odd then */
wolfSSL 13:f67a6c6013ca 938 if (fp_isodd (&D) == FP_YES) {
wolfSSL 13:f67a6c6013ca 939 /* D = (D-x)/2 */
wolfSSL 13:f67a6c6013ca 940 fp_sub (&D, &x, &D);
wolfSSL 13:f67a6c6013ca 941 }
wolfSSL 13:f67a6c6013ca 942 /* D = D/2 */
wolfSSL 13:f67a6c6013ca 943 fp_div_2 (&D, &D);
wolfSSL 13:f67a6c6013ca 944 }
wolfSSL 13:f67a6c6013ca 945
wolfSSL 13:f67a6c6013ca 946 /* 6. if u >= v then */
wolfSSL 13:f67a6c6013ca 947 if (fp_cmp (&u, &v) != FP_LT) {
wolfSSL 13:f67a6c6013ca 948 /* u = u - v, B = B - D */
wolfSSL 13:f67a6c6013ca 949 fp_sub (&u, &v, &u);
wolfSSL 13:f67a6c6013ca 950 fp_sub (&B, &D, &B);
wolfSSL 13:f67a6c6013ca 951 } else {
wolfSSL 13:f67a6c6013ca 952 /* v - v - u, D = D - B */
wolfSSL 13:f67a6c6013ca 953 fp_sub (&v, &u, &v);
wolfSSL 13:f67a6c6013ca 954 fp_sub (&D, &B, &D);
wolfSSL 13:f67a6c6013ca 955 }
wolfSSL 13:f67a6c6013ca 956
wolfSSL 13:f67a6c6013ca 957 /* if not zero goto step 4 */
wolfSSL 13:f67a6c6013ca 958 if (fp_iszero (&u) == FP_NO) {
wolfSSL 13:f67a6c6013ca 959 goto top;
wolfSSL 13:f67a6c6013ca 960 }
wolfSSL 13:f67a6c6013ca 961
wolfSSL 13:f67a6c6013ca 962 /* now a = C, b = D, gcd == g*v */
wolfSSL 13:f67a6c6013ca 963
wolfSSL 13:f67a6c6013ca 964 /* if v != 1 then there is no inverse */
wolfSSL 13:f67a6c6013ca 965 if (fp_cmp_d (&v, 1) != FP_EQ) {
wolfSSL 13:f67a6c6013ca 966 return FP_VAL;
wolfSSL 13:f67a6c6013ca 967 }
wolfSSL 13:f67a6c6013ca 968
wolfSSL 13:f67a6c6013ca 969 /* b is now the inverse */
wolfSSL 13:f67a6c6013ca 970 neg = a->sign;
wolfSSL 13:f67a6c6013ca 971 while (D.sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 972 fp_add (&D, b, &D);
wolfSSL 13:f67a6c6013ca 973 }
wolfSSL 13:f67a6c6013ca 974 /* too big */
wolfSSL 13:f67a6c6013ca 975 while (fp_cmp_mag(&D, b) != FP_LT) {
wolfSSL 13:f67a6c6013ca 976 fp_sub(&D, b, &D);
wolfSSL 13:f67a6c6013ca 977 }
wolfSSL 13:f67a6c6013ca 978 fp_copy (&D, c);
wolfSSL 13:f67a6c6013ca 979 c->sign = neg;
wolfSSL 13:f67a6c6013ca 980 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 981 }
wolfSSL 13:f67a6c6013ca 982
wolfSSL 13:f67a6c6013ca 983 /* d = a * b (mod c) */
wolfSSL 13:f67a6c6013ca 984 int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
wolfSSL 13:f67a6c6013ca 985 {
wolfSSL 13:f67a6c6013ca 986 int err;
wolfSSL 13:f67a6c6013ca 987 fp_int t;
wolfSSL 13:f67a6c6013ca 988
wolfSSL 13:f67a6c6013ca 989 fp_init(&t);
wolfSSL 13:f67a6c6013ca 990 fp_mul(a, b, &t);
wolfSSL 13:f67a6c6013ca 991 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 992 if (d->size < FP_SIZE) {
wolfSSL 13:f67a6c6013ca 993 err = fp_mod(&t, c, &t);
wolfSSL 13:f67a6c6013ca 994 fp_copy(&t, d);
wolfSSL 13:f67a6c6013ca 995 } else
wolfSSL 13:f67a6c6013ca 996 #endif
wolfSSL 13:f67a6c6013ca 997 {
wolfSSL 13:f67a6c6013ca 998 err = fp_mod(&t, c, d);
wolfSSL 13:f67a6c6013ca 999 }
wolfSSL 13:f67a6c6013ca 1000
wolfSSL 13:f67a6c6013ca 1001 return err;
wolfSSL 13:f67a6c6013ca 1002 }
wolfSSL 13:f67a6c6013ca 1003
wolfSSL 13:f67a6c6013ca 1004 /* d = a - b (mod c) */
wolfSSL 13:f67a6c6013ca 1005 int fp_submod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
wolfSSL 13:f67a6c6013ca 1006 {
wolfSSL 13:f67a6c6013ca 1007 int err;
wolfSSL 13:f67a6c6013ca 1008 fp_int t;
wolfSSL 13:f67a6c6013ca 1009
wolfSSL 13:f67a6c6013ca 1010 fp_init(&t);
wolfSSL 13:f67a6c6013ca 1011 fp_sub(a, b, &t);
wolfSSL 13:f67a6c6013ca 1012 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 1013 if (d->size < FP_SIZE) {
wolfSSL 13:f67a6c6013ca 1014 err = fp_mod(&t, c, &t);
wolfSSL 13:f67a6c6013ca 1015 fp_copy(&t, d);
wolfSSL 13:f67a6c6013ca 1016 } else
wolfSSL 13:f67a6c6013ca 1017 #endif
wolfSSL 13:f67a6c6013ca 1018 {
wolfSSL 13:f67a6c6013ca 1019 err = fp_mod(&t, c, d);
wolfSSL 13:f67a6c6013ca 1020 }
wolfSSL 13:f67a6c6013ca 1021
wolfSSL 13:f67a6c6013ca 1022 return err;
wolfSSL 13:f67a6c6013ca 1023 }
wolfSSL 13:f67a6c6013ca 1024
wolfSSL 13:f67a6c6013ca 1025 /* d = a + b (mod c) */
wolfSSL 13:f67a6c6013ca 1026 int fp_addmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
wolfSSL 13:f67a6c6013ca 1027 {
wolfSSL 13:f67a6c6013ca 1028 int err;
wolfSSL 13:f67a6c6013ca 1029 fp_int t;
wolfSSL 13:f67a6c6013ca 1030
wolfSSL 13:f67a6c6013ca 1031 fp_init(&t);
wolfSSL 13:f67a6c6013ca 1032 fp_add(a, b, &t);
wolfSSL 13:f67a6c6013ca 1033 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 1034 if (d->size < FP_SIZE) {
wolfSSL 13:f67a6c6013ca 1035 err = fp_mod(&t, c, &t);
wolfSSL 13:f67a6c6013ca 1036 fp_copy(&t, d);
wolfSSL 13:f67a6c6013ca 1037 } else
wolfSSL 13:f67a6c6013ca 1038 #endif
wolfSSL 13:f67a6c6013ca 1039 {
wolfSSL 13:f67a6c6013ca 1040 err = fp_mod(&t, c, d);
wolfSSL 13:f67a6c6013ca 1041 }
wolfSSL 13:f67a6c6013ca 1042
wolfSSL 13:f67a6c6013ca 1043 return err;
wolfSSL 13:f67a6c6013ca 1044 }
wolfSSL 13:f67a6c6013ca 1045
wolfSSL 13:f67a6c6013ca 1046 #ifdef TFM_TIMING_RESISTANT
wolfSSL 13:f67a6c6013ca 1047
wolfSSL 13:f67a6c6013ca 1048 /* timing resistant montgomery ladder based exptmod
wolfSSL 13:f67a6c6013ca 1049 Based on work by Marc Joye, Sung-Ming Yen, "The Montgomery Powering Ladder",
wolfSSL 13:f67a6c6013ca 1050 Cryptographic Hardware and Embedded Systems, CHES 2002
wolfSSL 13:f67a6c6013ca 1051 */
wolfSSL 13:f67a6c6013ca 1052 static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
wolfSSL 13:f67a6c6013ca 1053 {
wolfSSL 13:f67a6c6013ca 1054 #ifdef WC_NO_CACHE_RESISTANT
wolfSSL 13:f67a6c6013ca 1055 fp_int R[2];
wolfSSL 13:f67a6c6013ca 1056 #else
wolfSSL 13:f67a6c6013ca 1057 fp_int R[3]; /* need a temp for cache resistance */
wolfSSL 13:f67a6c6013ca 1058 #endif
wolfSSL 13:f67a6c6013ca 1059 fp_digit buf, mp;
wolfSSL 13:f67a6c6013ca 1060 int err, bitcnt, digidx, y;
wolfSSL 13:f67a6c6013ca 1061
wolfSSL 13:f67a6c6013ca 1062 /* now setup montgomery */
wolfSSL 13:f67a6c6013ca 1063 if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
wolfSSL 13:f67a6c6013ca 1064 return err;
wolfSSL 13:f67a6c6013ca 1065 }
wolfSSL 13:f67a6c6013ca 1066
wolfSSL 13:f67a6c6013ca 1067 fp_init(&R[0]);
wolfSSL 13:f67a6c6013ca 1068 fp_init(&R[1]);
wolfSSL 13:f67a6c6013ca 1069 #ifndef WC_NO_CACHE_RESISTANT
wolfSSL 13:f67a6c6013ca 1070 fp_init(&R[2]);
wolfSSL 13:f67a6c6013ca 1071 #endif
wolfSSL 13:f67a6c6013ca 1072
wolfSSL 13:f67a6c6013ca 1073 /* now we need R mod m */
wolfSSL 13:f67a6c6013ca 1074 fp_montgomery_calc_normalization (&R[0], P);
wolfSSL 13:f67a6c6013ca 1075
wolfSSL 13:f67a6c6013ca 1076 /* now set R[0][1] to G * R mod m */
wolfSSL 13:f67a6c6013ca 1077 if (fp_cmp_mag(P, G) != FP_GT) {
wolfSSL 13:f67a6c6013ca 1078 /* G > P so we reduce it first */
wolfSSL 13:f67a6c6013ca 1079 fp_mod(G, P, &R[1]);
wolfSSL 13:f67a6c6013ca 1080 } else {
wolfSSL 13:f67a6c6013ca 1081 fp_copy(G, &R[1]);
wolfSSL 13:f67a6c6013ca 1082 }
wolfSSL 13:f67a6c6013ca 1083 fp_mulmod (&R[1], &R[0], P, &R[1]);
wolfSSL 13:f67a6c6013ca 1084
wolfSSL 13:f67a6c6013ca 1085 /* for j = t-1 downto 0 do
wolfSSL 13:f67a6c6013ca 1086 r_!k = R0*R1; r_k = r_k^2
wolfSSL 13:f67a6c6013ca 1087 */
wolfSSL 13:f67a6c6013ca 1088
wolfSSL 13:f67a6c6013ca 1089 /* set initial mode and bit cnt */
wolfSSL 13:f67a6c6013ca 1090 bitcnt = 1;
wolfSSL 13:f67a6c6013ca 1091 buf = 0;
wolfSSL 13:f67a6c6013ca 1092 digidx = X->used - 1;
wolfSSL 13:f67a6c6013ca 1093
wolfSSL 13:f67a6c6013ca 1094 for (;;) {
wolfSSL 13:f67a6c6013ca 1095 /* grab next digit as required */
wolfSSL 13:f67a6c6013ca 1096 if (--bitcnt == 0) {
wolfSSL 13:f67a6c6013ca 1097 /* if digidx == -1 we are out of digits so break */
wolfSSL 13:f67a6c6013ca 1098 if (digidx == -1) {
wolfSSL 13:f67a6c6013ca 1099 break;
wolfSSL 13:f67a6c6013ca 1100 }
wolfSSL 13:f67a6c6013ca 1101 /* read next digit and reset bitcnt */
wolfSSL 13:f67a6c6013ca 1102 buf = X->dp[digidx--];
wolfSSL 13:f67a6c6013ca 1103 bitcnt = (int)DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 1104 }
wolfSSL 13:f67a6c6013ca 1105
wolfSSL 13:f67a6c6013ca 1106 /* grab the next msb from the exponent */
wolfSSL 13:f67a6c6013ca 1107 y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
wolfSSL 13:f67a6c6013ca 1108 buf <<= (fp_digit)1;
wolfSSL 13:f67a6c6013ca 1109
wolfSSL 13:f67a6c6013ca 1110 /* do ops */
wolfSSL 13:f67a6c6013ca 1111 fp_mul(&R[0], &R[1], &R[y^1]); fp_montgomery_reduce(&R[y^1], P, mp);
wolfSSL 13:f67a6c6013ca 1112
wolfSSL 13:f67a6c6013ca 1113 #ifdef WC_NO_CACHE_RESISTANT
wolfSSL 13:f67a6c6013ca 1114 fp_sqr(&R[y], &R[y]); fp_montgomery_reduce(&R[y], P, mp);
wolfSSL 13:f67a6c6013ca 1115 #else
wolfSSL 13:f67a6c6013ca 1116 /* instead of using R[y] for sqr, which leaks key bit to cache monitor,
wolfSSL 13:f67a6c6013ca 1117 * use R[2] as temp, make sure address calc is constant, keep
wolfSSL 13:f67a6c6013ca 1118 * &R[0] and &R[1] in cache */
wolfSSL 13:f67a6c6013ca 1119 fp_copy((fp_int*) ( ((wolfssl_word)&R[0] & wc_off_on_addr[y^1]) +
wolfSSL 13:f67a6c6013ca 1120 ((wolfssl_word)&R[1] & wc_off_on_addr[y]) ),
wolfSSL 13:f67a6c6013ca 1121 &R[2]);
wolfSSL 13:f67a6c6013ca 1122 fp_sqr(&R[2], &R[2]); fp_montgomery_reduce(&R[2], P, mp);
wolfSSL 13:f67a6c6013ca 1123 fp_copy(&R[2],
wolfSSL 13:f67a6c6013ca 1124 (fp_int*) ( ((wolfssl_word)&R[0] & wc_off_on_addr[y^1]) +
wolfSSL 13:f67a6c6013ca 1125 ((wolfssl_word)&R[1] & wc_off_on_addr[y]) ) );
wolfSSL 13:f67a6c6013ca 1126 #endif /* WC_NO_CACHE_RESISTANT */
wolfSSL 13:f67a6c6013ca 1127 }
wolfSSL 13:f67a6c6013ca 1128
wolfSSL 13:f67a6c6013ca 1129 fp_montgomery_reduce(&R[0], P, mp);
wolfSSL 13:f67a6c6013ca 1130 fp_copy(&R[0], Y);
wolfSSL 13:f67a6c6013ca 1131 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 1132 }
wolfSSL 13:f67a6c6013ca 1133
wolfSSL 13:f67a6c6013ca 1134 #else /* TFM_TIMING_RESISTANT */
wolfSSL 13:f67a6c6013ca 1135
wolfSSL 13:f67a6c6013ca 1136 /* y = g**x (mod b)
wolfSSL 13:f67a6c6013ca 1137 * Some restrictions... x must be positive and < b
wolfSSL 13:f67a6c6013ca 1138 */
wolfSSL 13:f67a6c6013ca 1139 static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
wolfSSL 13:f67a6c6013ca 1140 {
wolfSSL 13:f67a6c6013ca 1141 fp_int res;
wolfSSL 13:f67a6c6013ca 1142 fp_digit buf, mp;
wolfSSL 13:f67a6c6013ca 1143 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
wolfSSL 13:f67a6c6013ca 1144 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 13:f67a6c6013ca 1145 fp_int *M;
wolfSSL 13:f67a6c6013ca 1146 #else
wolfSSL 13:f67a6c6013ca 1147 fp_int M[64];
wolfSSL 13:f67a6c6013ca 1148 #endif
wolfSSL 13:f67a6c6013ca 1149
wolfSSL 13:f67a6c6013ca 1150 /* find window size */
wolfSSL 13:f67a6c6013ca 1151 x = fp_count_bits (X);
wolfSSL 13:f67a6c6013ca 1152 if (x <= 21) {
wolfSSL 13:f67a6c6013ca 1153 winsize = 1;
wolfSSL 13:f67a6c6013ca 1154 } else if (x <= 36) {
wolfSSL 13:f67a6c6013ca 1155 winsize = 3;
wolfSSL 13:f67a6c6013ca 1156 } else if (x <= 140) {
wolfSSL 13:f67a6c6013ca 1157 winsize = 4;
wolfSSL 13:f67a6c6013ca 1158 } else if (x <= 450) {
wolfSSL 13:f67a6c6013ca 1159 winsize = 5;
wolfSSL 13:f67a6c6013ca 1160 } else {
wolfSSL 13:f67a6c6013ca 1161 winsize = 6;
wolfSSL 13:f67a6c6013ca 1162 }
wolfSSL 13:f67a6c6013ca 1163
wolfSSL 13:f67a6c6013ca 1164 /* now setup montgomery */
wolfSSL 13:f67a6c6013ca 1165 if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
wolfSSL 13:f67a6c6013ca 1166 return err;
wolfSSL 13:f67a6c6013ca 1167 }
wolfSSL 13:f67a6c6013ca 1168
wolfSSL 13:f67a6c6013ca 1169 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 13:f67a6c6013ca 1170 /* only allocate space for what's needed */
wolfSSL 13:f67a6c6013ca 1171 M = (fp_int*)XMALLOC(sizeof(fp_int)*(1 << winsize), NULL, DYNAMIC_TYPE_TMP_BUFFER);
wolfSSL 13:f67a6c6013ca 1172 if (M == NULL) {
wolfSSL 13:f67a6c6013ca 1173 return FP_MEM;
wolfSSL 13:f67a6c6013ca 1174 }
wolfSSL 13:f67a6c6013ca 1175 #endif
wolfSSL 13:f67a6c6013ca 1176
wolfSSL 13:f67a6c6013ca 1177 /* init M array */
wolfSSL 13:f67a6c6013ca 1178 for(x = 0; x < (1 << winsize); x++)
wolfSSL 13:f67a6c6013ca 1179 fp_init(&M[x]);
wolfSSL 13:f67a6c6013ca 1180
wolfSSL 13:f67a6c6013ca 1181 /* setup result */
wolfSSL 13:f67a6c6013ca 1182 fp_init(&res);
wolfSSL 13:f67a6c6013ca 1183
wolfSSL 13:f67a6c6013ca 1184 /* create M table
wolfSSL 13:f67a6c6013ca 1185 *
wolfSSL 13:f67a6c6013ca 1186 * The M table contains powers of the input base, e.g. M[x] = G^x mod P
wolfSSL 13:f67a6c6013ca 1187 *
wolfSSL 13:f67a6c6013ca 1188 * The first half of the table is not computed though except for M[0] and M[1]
wolfSSL 13:f67a6c6013ca 1189 */
wolfSSL 13:f67a6c6013ca 1190
wolfSSL 13:f67a6c6013ca 1191 /* now we need R mod m */
wolfSSL 13:f67a6c6013ca 1192 fp_montgomery_calc_normalization (&res, P);
wolfSSL 13:f67a6c6013ca 1193
wolfSSL 13:f67a6c6013ca 1194 /* now set M[1] to G * R mod m */
wolfSSL 13:f67a6c6013ca 1195 if (fp_cmp_mag(P, G) != FP_GT) {
wolfSSL 13:f67a6c6013ca 1196 /* G > P so we reduce it first */
wolfSSL 13:f67a6c6013ca 1197 fp_mod(G, P, &M[1]);
wolfSSL 13:f67a6c6013ca 1198 } else {
wolfSSL 13:f67a6c6013ca 1199 fp_copy(G, &M[1]);
wolfSSL 13:f67a6c6013ca 1200 }
wolfSSL 13:f67a6c6013ca 1201 fp_mulmod (&M[1], &res, P, &M[1]);
wolfSSL 13:f67a6c6013ca 1202
wolfSSL 13:f67a6c6013ca 1203 /* compute the value at M[1<<(winsize-1)] by
wolfSSL 13:f67a6c6013ca 1204 * squaring M[1] (winsize-1) times */
wolfSSL 13:f67a6c6013ca 1205 fp_copy (&M[1], &M[1 << (winsize - 1)]);
wolfSSL 13:f67a6c6013ca 1206 for (x = 0; x < (winsize - 1); x++) {
wolfSSL 13:f67a6c6013ca 1207 fp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)]);
wolfSSL 13:f67a6c6013ca 1208 fp_montgomery_reduce (&M[1 << (winsize - 1)], P, mp);
wolfSSL 13:f67a6c6013ca 1209 }
wolfSSL 13:f67a6c6013ca 1210
wolfSSL 13:f67a6c6013ca 1211 /* create upper table */
wolfSSL 13:f67a6c6013ca 1212 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
wolfSSL 13:f67a6c6013ca 1213 fp_mul(&M[x - 1], &M[1], &M[x]);
wolfSSL 13:f67a6c6013ca 1214 fp_montgomery_reduce(&M[x], P, mp);
wolfSSL 13:f67a6c6013ca 1215 }
wolfSSL 13:f67a6c6013ca 1216
wolfSSL 13:f67a6c6013ca 1217 /* set initial mode and bit cnt */
wolfSSL 13:f67a6c6013ca 1218 mode = 0;
wolfSSL 13:f67a6c6013ca 1219 bitcnt = 1;
wolfSSL 13:f67a6c6013ca 1220 buf = 0;
wolfSSL 13:f67a6c6013ca 1221 digidx = X->used - 1;
wolfSSL 13:f67a6c6013ca 1222 bitcpy = 0;
wolfSSL 13:f67a6c6013ca 1223 bitbuf = 0;
wolfSSL 13:f67a6c6013ca 1224
wolfSSL 13:f67a6c6013ca 1225 for (;;) {
wolfSSL 13:f67a6c6013ca 1226 /* grab next digit as required */
wolfSSL 13:f67a6c6013ca 1227 if (--bitcnt == 0) {
wolfSSL 13:f67a6c6013ca 1228 /* if digidx == -1 we are out of digits so break */
wolfSSL 13:f67a6c6013ca 1229 if (digidx == -1) {
wolfSSL 13:f67a6c6013ca 1230 break;
wolfSSL 13:f67a6c6013ca 1231 }
wolfSSL 13:f67a6c6013ca 1232 /* read next digit and reset bitcnt */
wolfSSL 13:f67a6c6013ca 1233 buf = X->dp[digidx--];
wolfSSL 13:f67a6c6013ca 1234 bitcnt = (int)DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 1235 }
wolfSSL 13:f67a6c6013ca 1236
wolfSSL 13:f67a6c6013ca 1237 /* grab the next msb from the exponent */
wolfSSL 13:f67a6c6013ca 1238 y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
wolfSSL 13:f67a6c6013ca 1239 buf <<= (fp_digit)1;
wolfSSL 13:f67a6c6013ca 1240
wolfSSL 13:f67a6c6013ca 1241 /* if the bit is zero and mode == 0 then we ignore it
wolfSSL 13:f67a6c6013ca 1242 * These represent the leading zero bits before the first 1 bit
wolfSSL 13:f67a6c6013ca 1243 * in the exponent. Technically this opt is not required but it
wolfSSL 13:f67a6c6013ca 1244 * does lower the # of trivial squaring/reductions used
wolfSSL 13:f67a6c6013ca 1245 */
wolfSSL 13:f67a6c6013ca 1246 if (mode == 0 && y == 0) {
wolfSSL 13:f67a6c6013ca 1247 continue;
wolfSSL 13:f67a6c6013ca 1248 }
wolfSSL 13:f67a6c6013ca 1249
wolfSSL 13:f67a6c6013ca 1250 /* if the bit is zero and mode == 1 then we square */
wolfSSL 13:f67a6c6013ca 1251 if (mode == 1 && y == 0) {
wolfSSL 13:f67a6c6013ca 1252 fp_sqr(&res, &res);
wolfSSL 13:f67a6c6013ca 1253 fp_montgomery_reduce(&res, P, mp);
wolfSSL 13:f67a6c6013ca 1254 continue;
wolfSSL 13:f67a6c6013ca 1255 }
wolfSSL 13:f67a6c6013ca 1256
wolfSSL 13:f67a6c6013ca 1257 /* else we add it to the window */
wolfSSL 13:f67a6c6013ca 1258 bitbuf |= (y << (winsize - ++bitcpy));
wolfSSL 13:f67a6c6013ca 1259 mode = 2;
wolfSSL 13:f67a6c6013ca 1260
wolfSSL 13:f67a6c6013ca 1261 if (bitcpy == winsize) {
wolfSSL 13:f67a6c6013ca 1262 /* ok window is filled so square as required and multiply */
wolfSSL 13:f67a6c6013ca 1263 /* square first */
wolfSSL 13:f67a6c6013ca 1264 for (x = 0; x < winsize; x++) {
wolfSSL 13:f67a6c6013ca 1265 fp_sqr(&res, &res);
wolfSSL 13:f67a6c6013ca 1266 fp_montgomery_reduce(&res, P, mp);
wolfSSL 13:f67a6c6013ca 1267 }
wolfSSL 13:f67a6c6013ca 1268
wolfSSL 13:f67a6c6013ca 1269 /* then multiply */
wolfSSL 13:f67a6c6013ca 1270 fp_mul(&res, &M[bitbuf], &res);
wolfSSL 13:f67a6c6013ca 1271 fp_montgomery_reduce(&res, P, mp);
wolfSSL 13:f67a6c6013ca 1272
wolfSSL 13:f67a6c6013ca 1273 /* empty window and reset */
wolfSSL 13:f67a6c6013ca 1274 bitcpy = 0;
wolfSSL 13:f67a6c6013ca 1275 bitbuf = 0;
wolfSSL 13:f67a6c6013ca 1276 mode = 1;
wolfSSL 13:f67a6c6013ca 1277 }
wolfSSL 13:f67a6c6013ca 1278 }
wolfSSL 13:f67a6c6013ca 1279
wolfSSL 13:f67a6c6013ca 1280 /* if bits remain then square/multiply */
wolfSSL 13:f67a6c6013ca 1281 if (mode == 2 && bitcpy > 0) {
wolfSSL 13:f67a6c6013ca 1282 /* square then multiply if the bit is set */
wolfSSL 13:f67a6c6013ca 1283 for (x = 0; x < bitcpy; x++) {
wolfSSL 13:f67a6c6013ca 1284 fp_sqr(&res, &res);
wolfSSL 13:f67a6c6013ca 1285 fp_montgomery_reduce(&res, P, mp);
wolfSSL 13:f67a6c6013ca 1286
wolfSSL 13:f67a6c6013ca 1287 /* get next bit of the window */
wolfSSL 13:f67a6c6013ca 1288 bitbuf <<= 1;
wolfSSL 13:f67a6c6013ca 1289 if ((bitbuf & (1 << winsize)) != 0) {
wolfSSL 13:f67a6c6013ca 1290 /* then multiply */
wolfSSL 13:f67a6c6013ca 1291 fp_mul(&res, &M[1], &res);
wolfSSL 13:f67a6c6013ca 1292 fp_montgomery_reduce(&res, P, mp);
wolfSSL 13:f67a6c6013ca 1293 }
wolfSSL 13:f67a6c6013ca 1294 }
wolfSSL 13:f67a6c6013ca 1295 }
wolfSSL 13:f67a6c6013ca 1296
wolfSSL 13:f67a6c6013ca 1297 /* fixup result if Montgomery reduction is used
wolfSSL 13:f67a6c6013ca 1298 * recall that any value in a Montgomery system is
wolfSSL 13:f67a6c6013ca 1299 * actually multiplied by R mod n. So we have
wolfSSL 13:f67a6c6013ca 1300 * to reduce one more time to cancel out the factor
wolfSSL 13:f67a6c6013ca 1301 * of R.
wolfSSL 13:f67a6c6013ca 1302 */
wolfSSL 13:f67a6c6013ca 1303 fp_montgomery_reduce(&res, P, mp);
wolfSSL 13:f67a6c6013ca 1304
wolfSSL 13:f67a6c6013ca 1305 /* swap res with Y */
wolfSSL 13:f67a6c6013ca 1306 fp_copy (&res, Y);
wolfSSL 13:f67a6c6013ca 1307
wolfSSL 13:f67a6c6013ca 1308 #ifdef WOLFSSL_SMALL_STACK
wolfSSL 13:f67a6c6013ca 1309 XFREE(M, NULL, DYNAMIC_TYPE_TMP_BUFFER);
wolfSSL 13:f67a6c6013ca 1310 #endif
wolfSSL 13:f67a6c6013ca 1311
wolfSSL 13:f67a6c6013ca 1312 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 1313 }
wolfSSL 13:f67a6c6013ca 1314
wolfSSL 13:f67a6c6013ca 1315 #endif /* TFM_TIMING_RESISTANT */
wolfSSL 13:f67a6c6013ca 1316
wolfSSL 13:f67a6c6013ca 1317 int fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
wolfSSL 13:f67a6c6013ca 1318 {
wolfSSL 13:f67a6c6013ca 1319 /* prevent overflows */
wolfSSL 13:f67a6c6013ca 1320 if (P->used > (FP_SIZE/2)) {
wolfSSL 13:f67a6c6013ca 1321 return FP_VAL;
wolfSSL 13:f67a6c6013ca 1322 }
wolfSSL 13:f67a6c6013ca 1323
wolfSSL 13:f67a6c6013ca 1324 if (X->sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 1325 #ifndef POSITIVE_EXP_ONLY /* reduce stack if assume no negatives */
wolfSSL 13:f67a6c6013ca 1326 int err;
wolfSSL 13:f67a6c6013ca 1327 fp_int tmp;
wolfSSL 13:f67a6c6013ca 1328
wolfSSL 13:f67a6c6013ca 1329 /* yes, copy G and invmod it */
wolfSSL 13:f67a6c6013ca 1330 fp_init_copy(&tmp, G);
wolfSSL 13:f67a6c6013ca 1331 if ((err = fp_invmod(&tmp, P, &tmp)) != FP_OKAY) {
wolfSSL 13:f67a6c6013ca 1332 return err;
wolfSSL 13:f67a6c6013ca 1333 }
wolfSSL 13:f67a6c6013ca 1334 X->sign = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 1335 err = _fp_exptmod(&tmp, X, P, Y);
wolfSSL 13:f67a6c6013ca 1336 if (X != Y) {
wolfSSL 13:f67a6c6013ca 1337 X->sign = FP_NEG;
wolfSSL 13:f67a6c6013ca 1338 }
wolfSSL 13:f67a6c6013ca 1339 return err;
wolfSSL 13:f67a6c6013ca 1340 #else
wolfSSL 13:f67a6c6013ca 1341 return FP_VAL;
wolfSSL 13:f67a6c6013ca 1342 #endif
wolfSSL 13:f67a6c6013ca 1343 }
wolfSSL 13:f67a6c6013ca 1344 else {
wolfSSL 13:f67a6c6013ca 1345 /* Positive exponent so just exptmod */
wolfSSL 13:f67a6c6013ca 1346 return _fp_exptmod(G, X, P, Y);
wolfSSL 13:f67a6c6013ca 1347 }
wolfSSL 13:f67a6c6013ca 1348 }
wolfSSL 13:f67a6c6013ca 1349
wolfSSL 13:f67a6c6013ca 1350 /* computes a = 2**b */
wolfSSL 13:f67a6c6013ca 1351 void fp_2expt(fp_int *a, int b)
wolfSSL 13:f67a6c6013ca 1352 {
wolfSSL 13:f67a6c6013ca 1353 int z;
wolfSSL 13:f67a6c6013ca 1354
wolfSSL 13:f67a6c6013ca 1355 /* zero a as per default */
wolfSSL 13:f67a6c6013ca 1356 fp_zero (a);
wolfSSL 13:f67a6c6013ca 1357
wolfSSL 13:f67a6c6013ca 1358 if (b < 0) {
wolfSSL 13:f67a6c6013ca 1359 return;
wolfSSL 13:f67a6c6013ca 1360 }
wolfSSL 13:f67a6c6013ca 1361
wolfSSL 13:f67a6c6013ca 1362 z = b / DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 1363 if (z >= FP_SIZE) {
wolfSSL 13:f67a6c6013ca 1364 return;
wolfSSL 13:f67a6c6013ca 1365 }
wolfSSL 13:f67a6c6013ca 1366
wolfSSL 13:f67a6c6013ca 1367 /* set the used count of where the bit will go */
wolfSSL 13:f67a6c6013ca 1368 a->used = z + 1;
wolfSSL 13:f67a6c6013ca 1369
wolfSSL 13:f67a6c6013ca 1370 /* put the single bit in its place */
wolfSSL 13:f67a6c6013ca 1371 a->dp[z] = ((fp_digit)1) << (b % DIGIT_BIT);
wolfSSL 13:f67a6c6013ca 1372 }
wolfSSL 13:f67a6c6013ca 1373
wolfSSL 13:f67a6c6013ca 1374 /* b = a*a */
wolfSSL 13:f67a6c6013ca 1375 void fp_sqr(fp_int *A, fp_int *B)
wolfSSL 13:f67a6c6013ca 1376 {
wolfSSL 13:f67a6c6013ca 1377 int y, oldused;
wolfSSL 13:f67a6c6013ca 1378
wolfSSL 13:f67a6c6013ca 1379 oldused = B->used;
wolfSSL 13:f67a6c6013ca 1380 y = A->used;
wolfSSL 13:f67a6c6013ca 1381
wolfSSL 13:f67a6c6013ca 1382 /* call generic if we're out of range */
wolfSSL 13:f67a6c6013ca 1383 if (y + y > FP_SIZE) {
wolfSSL 13:f67a6c6013ca 1384 fp_sqr_comba(A, B);
wolfSSL 13:f67a6c6013ca 1385 goto clean;
wolfSSL 13:f67a6c6013ca 1386 }
wolfSSL 13:f67a6c6013ca 1387
wolfSSL 13:f67a6c6013ca 1388 #if defined(TFM_SQR3) && FP_SIZE >= 6
wolfSSL 13:f67a6c6013ca 1389 if (y <= 3) {
wolfSSL 13:f67a6c6013ca 1390 fp_sqr_comba3(A,B);
wolfSSL 13:f67a6c6013ca 1391 goto clean;
wolfSSL 13:f67a6c6013ca 1392 }
wolfSSL 13:f67a6c6013ca 1393 #endif
wolfSSL 13:f67a6c6013ca 1394 #if defined(TFM_SQR4) && FP_SIZE >= 8
wolfSSL 13:f67a6c6013ca 1395 if (y == 4) {
wolfSSL 13:f67a6c6013ca 1396 fp_sqr_comba4(A,B);
wolfSSL 13:f67a6c6013ca 1397 goto clean;
wolfSSL 13:f67a6c6013ca 1398 }
wolfSSL 13:f67a6c6013ca 1399 #endif
wolfSSL 13:f67a6c6013ca 1400 #if defined(TFM_SQR6) && FP_SIZE >= 12
wolfSSL 13:f67a6c6013ca 1401 if (y <= 6) {
wolfSSL 13:f67a6c6013ca 1402 fp_sqr_comba6(A,B);
wolfSSL 13:f67a6c6013ca 1403 goto clean;
wolfSSL 13:f67a6c6013ca 1404 }
wolfSSL 13:f67a6c6013ca 1405 #endif
wolfSSL 13:f67a6c6013ca 1406 #if defined(TFM_SQR7) && FP_SIZE >= 14
wolfSSL 13:f67a6c6013ca 1407 if (y == 7) {
wolfSSL 13:f67a6c6013ca 1408 fp_sqr_comba7(A,B);
wolfSSL 13:f67a6c6013ca 1409 goto clean;
wolfSSL 13:f67a6c6013ca 1410 }
wolfSSL 13:f67a6c6013ca 1411 #endif
wolfSSL 13:f67a6c6013ca 1412 #if defined(TFM_SQR8) && FP_SIZE >= 16
wolfSSL 13:f67a6c6013ca 1413 if (y == 8) {
wolfSSL 13:f67a6c6013ca 1414 fp_sqr_comba8(A,B);
wolfSSL 13:f67a6c6013ca 1415 goto clean;
wolfSSL 13:f67a6c6013ca 1416 }
wolfSSL 13:f67a6c6013ca 1417 #endif
wolfSSL 13:f67a6c6013ca 1418 #if defined(TFM_SQR9) && FP_SIZE >= 18
wolfSSL 13:f67a6c6013ca 1419 if (y == 9) {
wolfSSL 13:f67a6c6013ca 1420 fp_sqr_comba9(A,B);
wolfSSL 13:f67a6c6013ca 1421 goto clean;
wolfSSL 13:f67a6c6013ca 1422 }
wolfSSL 13:f67a6c6013ca 1423 #endif
wolfSSL 13:f67a6c6013ca 1424 #if defined(TFM_SQR12) && FP_SIZE >= 24
wolfSSL 13:f67a6c6013ca 1425 if (y <= 12) {
wolfSSL 13:f67a6c6013ca 1426 fp_sqr_comba12(A,B);
wolfSSL 13:f67a6c6013ca 1427 goto clean;
wolfSSL 13:f67a6c6013ca 1428 }
wolfSSL 13:f67a6c6013ca 1429 #endif
wolfSSL 13:f67a6c6013ca 1430 #if defined(TFM_SQR17) && FP_SIZE >= 34
wolfSSL 13:f67a6c6013ca 1431 if (y <= 17) {
wolfSSL 13:f67a6c6013ca 1432 fp_sqr_comba17(A,B);
wolfSSL 13:f67a6c6013ca 1433 goto clean;
wolfSSL 13:f67a6c6013ca 1434 }
wolfSSL 13:f67a6c6013ca 1435 #endif
wolfSSL 13:f67a6c6013ca 1436 #if defined(TFM_SMALL_SET)
wolfSSL 13:f67a6c6013ca 1437 if (y <= 16) {
wolfSSL 13:f67a6c6013ca 1438 fp_sqr_comba_small(A,B);
wolfSSL 13:f67a6c6013ca 1439 goto clean;
wolfSSL 13:f67a6c6013ca 1440 }
wolfSSL 13:f67a6c6013ca 1441 #endif
wolfSSL 13:f67a6c6013ca 1442 #if defined(TFM_SQR20) && FP_SIZE >= 40
wolfSSL 13:f67a6c6013ca 1443 if (y <= 20) {
wolfSSL 13:f67a6c6013ca 1444 fp_sqr_comba20(A,B);
wolfSSL 13:f67a6c6013ca 1445 goto clean;
wolfSSL 13:f67a6c6013ca 1446 }
wolfSSL 13:f67a6c6013ca 1447 #endif
wolfSSL 13:f67a6c6013ca 1448 #if defined(TFM_SQR24) && FP_SIZE >= 48
wolfSSL 13:f67a6c6013ca 1449 if (y <= 24) {
wolfSSL 13:f67a6c6013ca 1450 fp_sqr_comba24(A,B);
wolfSSL 13:f67a6c6013ca 1451 goto clean;
wolfSSL 13:f67a6c6013ca 1452 }
wolfSSL 13:f67a6c6013ca 1453 #endif
wolfSSL 13:f67a6c6013ca 1454 #if defined(TFM_SQR28) && FP_SIZE >= 56
wolfSSL 13:f67a6c6013ca 1455 if (y <= 28) {
wolfSSL 13:f67a6c6013ca 1456 fp_sqr_comba28(A,B);
wolfSSL 13:f67a6c6013ca 1457 goto clean;
wolfSSL 13:f67a6c6013ca 1458 }
wolfSSL 13:f67a6c6013ca 1459 #endif
wolfSSL 13:f67a6c6013ca 1460 #if defined(TFM_SQR32) && FP_SIZE >= 64
wolfSSL 13:f67a6c6013ca 1461 if (y <= 32) {
wolfSSL 13:f67a6c6013ca 1462 fp_sqr_comba32(A,B);
wolfSSL 13:f67a6c6013ca 1463 goto clean;
wolfSSL 13:f67a6c6013ca 1464 }
wolfSSL 13:f67a6c6013ca 1465 #endif
wolfSSL 13:f67a6c6013ca 1466 #if defined(TFM_SQR48) && FP_SIZE >= 96
wolfSSL 13:f67a6c6013ca 1467 if (y <= 48) {
wolfSSL 13:f67a6c6013ca 1468 fp_sqr_comba48(A,B);
wolfSSL 13:f67a6c6013ca 1469 goto clean;
wolfSSL 13:f67a6c6013ca 1470 }
wolfSSL 13:f67a6c6013ca 1471 #endif
wolfSSL 13:f67a6c6013ca 1472 #if defined(TFM_SQR64) && FP_SIZE >= 128
wolfSSL 13:f67a6c6013ca 1473 if (y <= 64) {
wolfSSL 13:f67a6c6013ca 1474 fp_sqr_comba64(A,B);
wolfSSL 13:f67a6c6013ca 1475 goto clean;
wolfSSL 13:f67a6c6013ca 1476 }
wolfSSL 13:f67a6c6013ca 1477 #endif
wolfSSL 13:f67a6c6013ca 1478 fp_sqr_comba(A, B);
wolfSSL 13:f67a6c6013ca 1479
wolfSSL 13:f67a6c6013ca 1480 clean:
wolfSSL 13:f67a6c6013ca 1481 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 1482 for (y = B->used; y >= 0 && y < oldused; y++) {
wolfSSL 13:f67a6c6013ca 1483 B->dp[y] = 0;
wolfSSL 13:f67a6c6013ca 1484 }
wolfSSL 13:f67a6c6013ca 1485 }
wolfSSL 13:f67a6c6013ca 1486
wolfSSL 13:f67a6c6013ca 1487 /* generic comba squarer */
wolfSSL 13:f67a6c6013ca 1488 void fp_sqr_comba(fp_int *A, fp_int *B)
wolfSSL 13:f67a6c6013ca 1489 {
wolfSSL 13:f67a6c6013ca 1490 int pa, ix, iz;
wolfSSL 13:f67a6c6013ca 1491 fp_digit c0, c1, c2;
wolfSSL 13:f67a6c6013ca 1492 fp_int tmp, *dst;
wolfSSL 13:f67a6c6013ca 1493 #ifdef TFM_ISO
wolfSSL 13:f67a6c6013ca 1494 fp_word tt;
wolfSSL 13:f67a6c6013ca 1495 #endif
wolfSSL 13:f67a6c6013ca 1496
wolfSSL 13:f67a6c6013ca 1497 /* get size of output and trim */
wolfSSL 13:f67a6c6013ca 1498 pa = A->used + A->used;
wolfSSL 13:f67a6c6013ca 1499 if (pa >= FP_SIZE) {
wolfSSL 13:f67a6c6013ca 1500 pa = FP_SIZE-1;
wolfSSL 13:f67a6c6013ca 1501 }
wolfSSL 13:f67a6c6013ca 1502
wolfSSL 13:f67a6c6013ca 1503 /* number of output digits to produce */
wolfSSL 13:f67a6c6013ca 1504 COMBA_START;
wolfSSL 13:f67a6c6013ca 1505 COMBA_CLEAR;
wolfSSL 13:f67a6c6013ca 1506
wolfSSL 13:f67a6c6013ca 1507 if (A == B) {
wolfSSL 13:f67a6c6013ca 1508 fp_init(&tmp);
wolfSSL 13:f67a6c6013ca 1509 dst = &tmp;
wolfSSL 13:f67a6c6013ca 1510 } else {
wolfSSL 13:f67a6c6013ca 1511 fp_zero(B);
wolfSSL 13:f67a6c6013ca 1512 dst = B;
wolfSSL 13:f67a6c6013ca 1513 }
wolfSSL 13:f67a6c6013ca 1514
wolfSSL 13:f67a6c6013ca 1515 for (ix = 0; ix < pa; ix++) {
wolfSSL 13:f67a6c6013ca 1516 int tx, ty, iy;
wolfSSL 13:f67a6c6013ca 1517 fp_digit *tmpy, *tmpx;
wolfSSL 13:f67a6c6013ca 1518
wolfSSL 13:f67a6c6013ca 1519 /* get offsets into the two bignums */
wolfSSL 13:f67a6c6013ca 1520 ty = MIN(A->used-1, ix);
wolfSSL 13:f67a6c6013ca 1521 tx = ix - ty;
wolfSSL 13:f67a6c6013ca 1522
wolfSSL 13:f67a6c6013ca 1523 /* setup temp aliases */
wolfSSL 13:f67a6c6013ca 1524 tmpx = A->dp + tx;
wolfSSL 13:f67a6c6013ca 1525 tmpy = A->dp + ty;
wolfSSL 13:f67a6c6013ca 1526
wolfSSL 13:f67a6c6013ca 1527 /* this is the number of times the loop will iterate,
wolfSSL 13:f67a6c6013ca 1528 while (tx++ < a->used && ty-- >= 0) { ... }
wolfSSL 13:f67a6c6013ca 1529 */
wolfSSL 13:f67a6c6013ca 1530 iy = MIN(A->used-tx, ty+1);
wolfSSL 13:f67a6c6013ca 1531
wolfSSL 13:f67a6c6013ca 1532 /* now for squaring tx can never equal ty
wolfSSL 13:f67a6c6013ca 1533 * we halve the distance since they approach
wolfSSL 13:f67a6c6013ca 1534 * at a rate of 2x and we have to round because
wolfSSL 13:f67a6c6013ca 1535 * odd cases need to be executed
wolfSSL 13:f67a6c6013ca 1536 */
wolfSSL 13:f67a6c6013ca 1537 iy = MIN(iy, (ty-tx+1)>>1);
wolfSSL 13:f67a6c6013ca 1538
wolfSSL 13:f67a6c6013ca 1539 /* forward carries */
wolfSSL 13:f67a6c6013ca 1540 COMBA_FORWARD;
wolfSSL 13:f67a6c6013ca 1541
wolfSSL 13:f67a6c6013ca 1542 /* execute loop */
wolfSSL 13:f67a6c6013ca 1543 for (iz = 0; iz < iy; iz++) {
wolfSSL 13:f67a6c6013ca 1544 SQRADD2(*tmpx++, *tmpy--);
wolfSSL 13:f67a6c6013ca 1545 }
wolfSSL 13:f67a6c6013ca 1546
wolfSSL 13:f67a6c6013ca 1547 /* even columns have the square term in them */
wolfSSL 13:f67a6c6013ca 1548 if ((ix&1) == 0) {
wolfSSL 13:f67a6c6013ca 1549 /* TAO change COMBA_ADD back to SQRADD */
wolfSSL 13:f67a6c6013ca 1550 SQRADD(A->dp[ix>>1], A->dp[ix>>1]);
wolfSSL 13:f67a6c6013ca 1551 }
wolfSSL 13:f67a6c6013ca 1552
wolfSSL 13:f67a6c6013ca 1553 /* store it */
wolfSSL 13:f67a6c6013ca 1554 COMBA_STORE(dst->dp[ix]);
wolfSSL 13:f67a6c6013ca 1555 }
wolfSSL 13:f67a6c6013ca 1556
wolfSSL 13:f67a6c6013ca 1557 COMBA_FINI;
wolfSSL 13:f67a6c6013ca 1558
wolfSSL 13:f67a6c6013ca 1559 /* setup dest */
wolfSSL 13:f67a6c6013ca 1560 dst->used = pa;
wolfSSL 13:f67a6c6013ca 1561 fp_clamp (dst);
wolfSSL 13:f67a6c6013ca 1562 if (dst != B) {
wolfSSL 13:f67a6c6013ca 1563 fp_copy(dst, B);
wolfSSL 13:f67a6c6013ca 1564 }
wolfSSL 13:f67a6c6013ca 1565 }
wolfSSL 13:f67a6c6013ca 1566
wolfSSL 13:f67a6c6013ca 1567 int fp_cmp(fp_int *a, fp_int *b)
wolfSSL 13:f67a6c6013ca 1568 {
wolfSSL 13:f67a6c6013ca 1569 if (a->sign == FP_NEG && b->sign == FP_ZPOS) {
wolfSSL 13:f67a6c6013ca 1570 return FP_LT;
wolfSSL 13:f67a6c6013ca 1571 } else if (a->sign == FP_ZPOS && b->sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 1572 return FP_GT;
wolfSSL 13:f67a6c6013ca 1573 } else {
wolfSSL 13:f67a6c6013ca 1574 /* compare digits */
wolfSSL 13:f67a6c6013ca 1575 if (a->sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 1576 /* if negative compare opposite direction */
wolfSSL 13:f67a6c6013ca 1577 return fp_cmp_mag(b, a);
wolfSSL 13:f67a6c6013ca 1578 } else {
wolfSSL 13:f67a6c6013ca 1579 return fp_cmp_mag(a, b);
wolfSSL 13:f67a6c6013ca 1580 }
wolfSSL 13:f67a6c6013ca 1581 }
wolfSSL 13:f67a6c6013ca 1582 }
wolfSSL 13:f67a6c6013ca 1583
wolfSSL 13:f67a6c6013ca 1584 /* compare against a single digit */
wolfSSL 13:f67a6c6013ca 1585 int fp_cmp_d(fp_int *a, fp_digit b)
wolfSSL 13:f67a6c6013ca 1586 {
wolfSSL 13:f67a6c6013ca 1587 /* special case for zero*/
wolfSSL 13:f67a6c6013ca 1588 if (a->used == 0 && b == 0)
wolfSSL 13:f67a6c6013ca 1589 return FP_EQ;
wolfSSL 13:f67a6c6013ca 1590
wolfSSL 13:f67a6c6013ca 1591 /* compare based on sign */
wolfSSL 13:f67a6c6013ca 1592 if ((b && a->used == 0) || a->sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 1593 return FP_LT;
wolfSSL 13:f67a6c6013ca 1594 }
wolfSSL 13:f67a6c6013ca 1595
wolfSSL 13:f67a6c6013ca 1596 /* compare based on magnitude */
wolfSSL 13:f67a6c6013ca 1597 if (a->used > 1) {
wolfSSL 13:f67a6c6013ca 1598 return FP_GT;
wolfSSL 13:f67a6c6013ca 1599 }
wolfSSL 13:f67a6c6013ca 1600
wolfSSL 13:f67a6c6013ca 1601 /* compare the only digit of a to b */
wolfSSL 13:f67a6c6013ca 1602 if (a->dp[0] > b) {
wolfSSL 13:f67a6c6013ca 1603 return FP_GT;
wolfSSL 13:f67a6c6013ca 1604 } else if (a->dp[0] < b) {
wolfSSL 13:f67a6c6013ca 1605 return FP_LT;
wolfSSL 13:f67a6c6013ca 1606 } else {
wolfSSL 13:f67a6c6013ca 1607 return FP_EQ;
wolfSSL 13:f67a6c6013ca 1608 }
wolfSSL 13:f67a6c6013ca 1609
wolfSSL 13:f67a6c6013ca 1610 }
wolfSSL 13:f67a6c6013ca 1611
wolfSSL 13:f67a6c6013ca 1612 int fp_cmp_mag(fp_int *a, fp_int *b)
wolfSSL 13:f67a6c6013ca 1613 {
wolfSSL 13:f67a6c6013ca 1614 int x;
wolfSSL 13:f67a6c6013ca 1615
wolfSSL 13:f67a6c6013ca 1616 if (a->used > b->used) {
wolfSSL 13:f67a6c6013ca 1617 return FP_GT;
wolfSSL 13:f67a6c6013ca 1618 } else if (a->used < b->used) {
wolfSSL 13:f67a6c6013ca 1619 return FP_LT;
wolfSSL 13:f67a6c6013ca 1620 } else {
wolfSSL 13:f67a6c6013ca 1621 for (x = a->used - 1; x >= 0; x--) {
wolfSSL 13:f67a6c6013ca 1622 if (a->dp[x] > b->dp[x]) {
wolfSSL 13:f67a6c6013ca 1623 return FP_GT;
wolfSSL 13:f67a6c6013ca 1624 } else if (a->dp[x] < b->dp[x]) {
wolfSSL 13:f67a6c6013ca 1625 return FP_LT;
wolfSSL 13:f67a6c6013ca 1626 }
wolfSSL 13:f67a6c6013ca 1627 }
wolfSSL 13:f67a6c6013ca 1628 }
wolfSSL 13:f67a6c6013ca 1629 return FP_EQ;
wolfSSL 13:f67a6c6013ca 1630 }
wolfSSL 13:f67a6c6013ca 1631
wolfSSL 13:f67a6c6013ca 1632 /* sets up the montgomery reduction */
wolfSSL 13:f67a6c6013ca 1633 int fp_montgomery_setup(fp_int *a, fp_digit *rho)
wolfSSL 13:f67a6c6013ca 1634 {
wolfSSL 13:f67a6c6013ca 1635 fp_digit x, b;
wolfSSL 13:f67a6c6013ca 1636
wolfSSL 13:f67a6c6013ca 1637 /* fast inversion mod 2**k
wolfSSL 13:f67a6c6013ca 1638 *
wolfSSL 13:f67a6c6013ca 1639 * Based on the fact that
wolfSSL 13:f67a6c6013ca 1640 *
wolfSSL 13:f67a6c6013ca 1641 * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
wolfSSL 13:f67a6c6013ca 1642 * => 2*X*A - X*X*A*A = 1
wolfSSL 13:f67a6c6013ca 1643 * => 2*(1) - (1) = 1
wolfSSL 13:f67a6c6013ca 1644 */
wolfSSL 13:f67a6c6013ca 1645 b = a->dp[0];
wolfSSL 13:f67a6c6013ca 1646
wolfSSL 13:f67a6c6013ca 1647 if ((b & 1) == 0) {
wolfSSL 13:f67a6c6013ca 1648 return FP_VAL;
wolfSSL 13:f67a6c6013ca 1649 }
wolfSSL 13:f67a6c6013ca 1650
wolfSSL 13:f67a6c6013ca 1651 x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
wolfSSL 13:f67a6c6013ca 1652 x *= 2 - b * x; /* here x*a==1 mod 2**8 */
wolfSSL 13:f67a6c6013ca 1653 x *= 2 - b * x; /* here x*a==1 mod 2**16 */
wolfSSL 13:f67a6c6013ca 1654 x *= 2 - b * x; /* here x*a==1 mod 2**32 */
wolfSSL 13:f67a6c6013ca 1655 #ifdef FP_64BIT
wolfSSL 13:f67a6c6013ca 1656 x *= 2 - b * x; /* here x*a==1 mod 2**64 */
wolfSSL 13:f67a6c6013ca 1657 #endif
wolfSSL 13:f67a6c6013ca 1658
wolfSSL 13:f67a6c6013ca 1659 /* rho = -1/m mod b */
wolfSSL 13:f67a6c6013ca 1660 *rho = (fp_digit) (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
wolfSSL 13:f67a6c6013ca 1661
wolfSSL 13:f67a6c6013ca 1662 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 1663 }
wolfSSL 13:f67a6c6013ca 1664
wolfSSL 13:f67a6c6013ca 1665 /* computes a = B**n mod b without division or multiplication useful for
wolfSSL 13:f67a6c6013ca 1666 * normalizing numbers in a Montgomery system.
wolfSSL 13:f67a6c6013ca 1667 */
wolfSSL 13:f67a6c6013ca 1668 void fp_montgomery_calc_normalization(fp_int *a, fp_int *b)
wolfSSL 13:f67a6c6013ca 1669 {
wolfSSL 13:f67a6c6013ca 1670 int x, bits;
wolfSSL 13:f67a6c6013ca 1671
wolfSSL 13:f67a6c6013ca 1672 /* how many bits of last digit does b use */
wolfSSL 13:f67a6c6013ca 1673 bits = fp_count_bits (b) % DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 1674 if (!bits) bits = DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 1675
wolfSSL 13:f67a6c6013ca 1676 /* compute A = B^(n-1) * 2^(bits-1) */
wolfSSL 13:f67a6c6013ca 1677 if (b->used > 1) {
wolfSSL 13:f67a6c6013ca 1678 fp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1);
wolfSSL 13:f67a6c6013ca 1679 } else {
wolfSSL 13:f67a6c6013ca 1680 fp_set(a, 1);
wolfSSL 13:f67a6c6013ca 1681 bits = 1;
wolfSSL 13:f67a6c6013ca 1682 }
wolfSSL 13:f67a6c6013ca 1683
wolfSSL 13:f67a6c6013ca 1684 /* now compute C = A * B mod b */
wolfSSL 13:f67a6c6013ca 1685 for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
wolfSSL 13:f67a6c6013ca 1686 fp_mul_2 (a, a);
wolfSSL 13:f67a6c6013ca 1687 if (fp_cmp_mag (a, b) != FP_LT) {
wolfSSL 13:f67a6c6013ca 1688 s_fp_sub (a, b, a);
wolfSSL 13:f67a6c6013ca 1689 }
wolfSSL 13:f67a6c6013ca 1690 }
wolfSSL 13:f67a6c6013ca 1691 }
wolfSSL 13:f67a6c6013ca 1692
wolfSSL 13:f67a6c6013ca 1693
wolfSSL 13:f67a6c6013ca 1694 #ifdef TFM_SMALL_MONT_SET
wolfSSL 13:f67a6c6013ca 1695 #include "fp_mont_small.i"
wolfSSL 13:f67a6c6013ca 1696 #endif
wolfSSL 13:f67a6c6013ca 1697
wolfSSL 13:f67a6c6013ca 1698 #ifdef HAVE_INTEL_MULX
wolfSSL 13:f67a6c6013ca 1699 static INLINE void innermul8_mulx(fp_digit *c_mulx, fp_digit *cy_mulx, fp_digit *tmpm, fp_digit mu)
wolfSSL 13:f67a6c6013ca 1700 {
wolfSSL 13:f67a6c6013ca 1701 fp_digit _c0, _c1, _c2, _c3, _c4, _c5, _c6, _c7, cy ;
wolfSSL 13:f67a6c6013ca 1702
wolfSSL 13:f67a6c6013ca 1703 cy = *cy_mulx ;
wolfSSL 13:f67a6c6013ca 1704 _c0=c_mulx[0]; _c1=c_mulx[1]; _c2=c_mulx[2]; _c3=c_mulx[3]; _c4=c_mulx[4]; _c5=c_mulx[5]; _c6=c_mulx[6]; _c7=c_mulx[7];
wolfSSL 13:f67a6c6013ca 1705 INNERMUL8_MULX ;
wolfSSL 13:f67a6c6013ca 1706 c_mulx[0]=_c0; c_mulx[1]=_c1; c_mulx[2]=_c2; c_mulx[3]=_c3; c_mulx[4]=_c4; c_mulx[5]=_c5; c_mulx[6]=_c6; c_mulx[7]=_c7;
wolfSSL 13:f67a6c6013ca 1707 *cy_mulx = cy ;
wolfSSL 13:f67a6c6013ca 1708 }
wolfSSL 13:f67a6c6013ca 1709
wolfSSL 13:f67a6c6013ca 1710 /* computes x/R == x (mod N) via Montgomery Reduction */
wolfSSL 13:f67a6c6013ca 1711 static void fp_montgomery_reduce_mulx(fp_int *a, fp_int *m, fp_digit mp)
wolfSSL 13:f67a6c6013ca 1712 {
wolfSSL 13:f67a6c6013ca 1713 fp_digit c[FP_SIZE+1], *_c, *tmpm, mu = 0;
wolfSSL 13:f67a6c6013ca 1714 int oldused, x, y, pa;
wolfSSL 13:f67a6c6013ca 1715
wolfSSL 13:f67a6c6013ca 1716 /* bail if too large */
wolfSSL 13:f67a6c6013ca 1717 if (m->used > (FP_SIZE/2)) {
wolfSSL 13:f67a6c6013ca 1718 (void)mu; /* shut up compiler */
wolfSSL 13:f67a6c6013ca 1719 return;
wolfSSL 13:f67a6c6013ca 1720 }
wolfSSL 13:f67a6c6013ca 1721
wolfSSL 13:f67a6c6013ca 1722 #ifdef TFM_SMALL_MONT_SET
wolfSSL 13:f67a6c6013ca 1723 if (m->used <= 16) {
wolfSSL 13:f67a6c6013ca 1724 fp_montgomery_reduce_small(a, m, mp);
wolfSSL 13:f67a6c6013ca 1725 return;
wolfSSL 13:f67a6c6013ca 1726 }
wolfSSL 13:f67a6c6013ca 1727 #endif
wolfSSL 13:f67a6c6013ca 1728
wolfSSL 13:f67a6c6013ca 1729
wolfSSL 13:f67a6c6013ca 1730 /* now zero the buff */
wolfSSL 13:f67a6c6013ca 1731 XMEMSET(c, 0, sizeof(c));
wolfSSL 13:f67a6c6013ca 1732 pa = m->used;
wolfSSL 13:f67a6c6013ca 1733
wolfSSL 13:f67a6c6013ca 1734 /* copy the input */
wolfSSL 13:f67a6c6013ca 1735 oldused = a->used;
wolfSSL 13:f67a6c6013ca 1736 for (x = 0; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 1737 c[x] = a->dp[x];
wolfSSL 13:f67a6c6013ca 1738 }
wolfSSL 13:f67a6c6013ca 1739 MONT_START;
wolfSSL 13:f67a6c6013ca 1740
wolfSSL 13:f67a6c6013ca 1741 for (x = 0; x < pa; x++) {
wolfSSL 13:f67a6c6013ca 1742 fp_digit cy = 0;
wolfSSL 13:f67a6c6013ca 1743 /* get Mu for this round */
wolfSSL 13:f67a6c6013ca 1744 LOOP_START;
wolfSSL 13:f67a6c6013ca 1745 _c = c + x;
wolfSSL 13:f67a6c6013ca 1746 tmpm = m->dp;
wolfSSL 13:f67a6c6013ca 1747 y = 0;
wolfSSL 13:f67a6c6013ca 1748 for (; y < (pa & ~7); y += 8) {
wolfSSL 13:f67a6c6013ca 1749 innermul8_mulx(_c, &cy, tmpm, mu) ;
wolfSSL 13:f67a6c6013ca 1750 _c += 8;
wolfSSL 13:f67a6c6013ca 1751 tmpm += 8;
wolfSSL 13:f67a6c6013ca 1752 }
wolfSSL 13:f67a6c6013ca 1753 for (; y < pa; y++) {
wolfSSL 13:f67a6c6013ca 1754 INNERMUL;
wolfSSL 13:f67a6c6013ca 1755 ++_c;
wolfSSL 13:f67a6c6013ca 1756 }
wolfSSL 13:f67a6c6013ca 1757 LOOP_END;
wolfSSL 13:f67a6c6013ca 1758 while (cy) {
wolfSSL 13:f67a6c6013ca 1759 PROPCARRY;
wolfSSL 13:f67a6c6013ca 1760 ++_c;
wolfSSL 13:f67a6c6013ca 1761 }
wolfSSL 13:f67a6c6013ca 1762 }
wolfSSL 13:f67a6c6013ca 1763
wolfSSL 13:f67a6c6013ca 1764 /* now copy out */
wolfSSL 13:f67a6c6013ca 1765 _c = c + pa;
wolfSSL 13:f67a6c6013ca 1766 tmpm = a->dp;
wolfSSL 13:f67a6c6013ca 1767 for (x = 0; x < pa+1; x++) {
wolfSSL 13:f67a6c6013ca 1768 *tmpm++ = *_c++;
wolfSSL 13:f67a6c6013ca 1769 }
wolfSSL 13:f67a6c6013ca 1770
wolfSSL 13:f67a6c6013ca 1771 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 1772 for (; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 1773 *tmpm++ = 0;
wolfSSL 13:f67a6c6013ca 1774 }
wolfSSL 13:f67a6c6013ca 1775
wolfSSL 13:f67a6c6013ca 1776 MONT_FINI;
wolfSSL 13:f67a6c6013ca 1777
wolfSSL 13:f67a6c6013ca 1778 a->used = pa+1;
wolfSSL 13:f67a6c6013ca 1779 fp_clamp(a);
wolfSSL 13:f67a6c6013ca 1780
wolfSSL 13:f67a6c6013ca 1781 /* if A >= m then A = A - m */
wolfSSL 13:f67a6c6013ca 1782 if (fp_cmp_mag (a, m) != FP_LT) {
wolfSSL 13:f67a6c6013ca 1783 s_fp_sub (a, m, a);
wolfSSL 13:f67a6c6013ca 1784 }
wolfSSL 13:f67a6c6013ca 1785 }
wolfSSL 13:f67a6c6013ca 1786 #endif
wolfSSL 13:f67a6c6013ca 1787
wolfSSL 13:f67a6c6013ca 1788 /* computes x/R == x (mod N) via Montgomery Reduction */
wolfSSL 13:f67a6c6013ca 1789 void fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp)
wolfSSL 13:f67a6c6013ca 1790 {
wolfSSL 13:f67a6c6013ca 1791 fp_digit c[FP_SIZE+1], *_c, *tmpm, mu = 0;
wolfSSL 13:f67a6c6013ca 1792 int oldused, x, y, pa;
wolfSSL 13:f67a6c6013ca 1793
wolfSSL 13:f67a6c6013ca 1794 IF_HAVE_INTEL_MULX(fp_montgomery_reduce_mulx(a, m, mp), return) ;
wolfSSL 13:f67a6c6013ca 1795
wolfSSL 13:f67a6c6013ca 1796 /* bail if too large */
wolfSSL 13:f67a6c6013ca 1797 if (m->used > (FP_SIZE/2)) {
wolfSSL 13:f67a6c6013ca 1798 (void)mu; /* shut up compiler */
wolfSSL 13:f67a6c6013ca 1799 return;
wolfSSL 13:f67a6c6013ca 1800 }
wolfSSL 13:f67a6c6013ca 1801
wolfSSL 13:f67a6c6013ca 1802 #ifdef TFM_SMALL_MONT_SET
wolfSSL 13:f67a6c6013ca 1803 if (m->used <= 16) {
wolfSSL 13:f67a6c6013ca 1804 fp_montgomery_reduce_small(a, m, mp);
wolfSSL 13:f67a6c6013ca 1805 return;
wolfSSL 13:f67a6c6013ca 1806 }
wolfSSL 13:f67a6c6013ca 1807 #endif
wolfSSL 13:f67a6c6013ca 1808
wolfSSL 13:f67a6c6013ca 1809
wolfSSL 13:f67a6c6013ca 1810 /* now zero the buff */
wolfSSL 13:f67a6c6013ca 1811 XMEMSET(c, 0, sizeof(c));
wolfSSL 13:f67a6c6013ca 1812 pa = m->used;
wolfSSL 13:f67a6c6013ca 1813
wolfSSL 13:f67a6c6013ca 1814 /* copy the input */
wolfSSL 13:f67a6c6013ca 1815 oldused = a->used;
wolfSSL 13:f67a6c6013ca 1816 for (x = 0; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 1817 c[x] = a->dp[x];
wolfSSL 13:f67a6c6013ca 1818 }
wolfSSL 13:f67a6c6013ca 1819 MONT_START;
wolfSSL 13:f67a6c6013ca 1820
wolfSSL 13:f67a6c6013ca 1821 for (x = 0; x < pa; x++) {
wolfSSL 13:f67a6c6013ca 1822 fp_digit cy = 0;
wolfSSL 13:f67a6c6013ca 1823 /* get Mu for this round */
wolfSSL 13:f67a6c6013ca 1824 LOOP_START;
wolfSSL 13:f67a6c6013ca 1825 _c = c + x;
wolfSSL 13:f67a6c6013ca 1826 tmpm = m->dp;
wolfSSL 13:f67a6c6013ca 1827 y = 0;
wolfSSL 13:f67a6c6013ca 1828 #if defined(INNERMUL8)
wolfSSL 13:f67a6c6013ca 1829 for (; y < (pa & ~7); y += 8) {
wolfSSL 13:f67a6c6013ca 1830 INNERMUL8 ;
wolfSSL 13:f67a6c6013ca 1831 _c += 8;
wolfSSL 13:f67a6c6013ca 1832 tmpm += 8;
wolfSSL 13:f67a6c6013ca 1833 }
wolfSSL 13:f67a6c6013ca 1834 #endif
wolfSSL 13:f67a6c6013ca 1835 for (; y < pa; y++) {
wolfSSL 13:f67a6c6013ca 1836 INNERMUL;
wolfSSL 13:f67a6c6013ca 1837 ++_c;
wolfSSL 13:f67a6c6013ca 1838 }
wolfSSL 13:f67a6c6013ca 1839 LOOP_END;
wolfSSL 13:f67a6c6013ca 1840 while (cy) {
wolfSSL 13:f67a6c6013ca 1841 PROPCARRY;
wolfSSL 13:f67a6c6013ca 1842 ++_c;
wolfSSL 13:f67a6c6013ca 1843 }
wolfSSL 13:f67a6c6013ca 1844 }
wolfSSL 13:f67a6c6013ca 1845
wolfSSL 13:f67a6c6013ca 1846 /* now copy out */
wolfSSL 13:f67a6c6013ca 1847 _c = c + pa;
wolfSSL 13:f67a6c6013ca 1848 tmpm = a->dp;
wolfSSL 13:f67a6c6013ca 1849 for (x = 0; x < pa+1; x++) {
wolfSSL 13:f67a6c6013ca 1850 *tmpm++ = *_c++;
wolfSSL 13:f67a6c6013ca 1851 }
wolfSSL 13:f67a6c6013ca 1852
wolfSSL 13:f67a6c6013ca 1853 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 1854 for (; x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 1855 *tmpm++ = 0;
wolfSSL 13:f67a6c6013ca 1856 }
wolfSSL 13:f67a6c6013ca 1857
wolfSSL 13:f67a6c6013ca 1858 MONT_FINI;
wolfSSL 13:f67a6c6013ca 1859
wolfSSL 13:f67a6c6013ca 1860 a->used = pa+1;
wolfSSL 13:f67a6c6013ca 1861 fp_clamp(a);
wolfSSL 13:f67a6c6013ca 1862
wolfSSL 13:f67a6c6013ca 1863 /* if A >= m then A = A - m */
wolfSSL 13:f67a6c6013ca 1864 if (fp_cmp_mag (a, m) != FP_LT) {
wolfSSL 13:f67a6c6013ca 1865 s_fp_sub (a, m, a);
wolfSSL 13:f67a6c6013ca 1866 }
wolfSSL 13:f67a6c6013ca 1867 }
wolfSSL 13:f67a6c6013ca 1868
wolfSSL 13:f67a6c6013ca 1869 void fp_read_unsigned_bin(fp_int *a, const unsigned char *b, int c)
wolfSSL 13:f67a6c6013ca 1870 {
wolfSSL 13:f67a6c6013ca 1871 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 1872 const word32 maxC = (a->size * sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 1873 #else
wolfSSL 13:f67a6c6013ca 1874 const word32 maxC = (FP_SIZE * sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 1875 #endif
wolfSSL 13:f67a6c6013ca 1876
wolfSSL 13:f67a6c6013ca 1877 /* zero the int */
wolfSSL 13:f67a6c6013ca 1878 fp_zero (a);
wolfSSL 13:f67a6c6013ca 1879
wolfSSL 13:f67a6c6013ca 1880 /* if input b excess max, then truncate */
wolfSSL 13:f67a6c6013ca 1881 if (c > 0 && (word32)c > maxC) {
wolfSSL 13:f67a6c6013ca 1882 int excess = (c - maxC);
wolfSSL 13:f67a6c6013ca 1883 c -= excess;
wolfSSL 13:f67a6c6013ca 1884 b += excess;
wolfSSL 13:f67a6c6013ca 1885 }
wolfSSL 13:f67a6c6013ca 1886
wolfSSL 13:f67a6c6013ca 1887 /* If we know the endianness of this architecture, and we're using
wolfSSL 13:f67a6c6013ca 1888 32-bit fp_digits, we can optimize this */
wolfSSL 13:f67a6c6013ca 1889 #if (defined(LITTLE_ENDIAN_ORDER) || defined(BIG_ENDIAN_ORDER)) && \
wolfSSL 13:f67a6c6013ca 1890 defined(FP_32BIT)
wolfSSL 13:f67a6c6013ca 1891 /* But not for both simultaneously */
wolfSSL 13:f67a6c6013ca 1892 #if defined(LITTLE_ENDIAN_ORDER) && defined(BIG_ENDIAN_ORDER)
wolfSSL 13:f67a6c6013ca 1893 #error Both LITTLE_ENDIAN_ORDER and BIG_ENDIAN_ORDER defined.
wolfSSL 13:f67a6c6013ca 1894 #endif
wolfSSL 13:f67a6c6013ca 1895 {
wolfSSL 13:f67a6c6013ca 1896 unsigned char *pd = (unsigned char *)a->dp;
wolfSSL 13:f67a6c6013ca 1897
wolfSSL 13:f67a6c6013ca 1898 a->used = (c + sizeof(fp_digit) - 1)/sizeof(fp_digit);
wolfSSL 13:f67a6c6013ca 1899 /* read the bytes in */
wolfSSL 13:f67a6c6013ca 1900 #ifdef BIG_ENDIAN_ORDER
wolfSSL 13:f67a6c6013ca 1901 {
wolfSSL 13:f67a6c6013ca 1902 /* Use Duff's device to unroll the loop. */
wolfSSL 13:f67a6c6013ca 1903 int idx = (c - 1) & ~3;
wolfSSL 13:f67a6c6013ca 1904 switch (c % 4) {
wolfSSL 13:f67a6c6013ca 1905 case 0: do { pd[idx+0] = *b++;
wolfSSL 13:f67a6c6013ca 1906 case 3: pd[idx+1] = *b++;
wolfSSL 13:f67a6c6013ca 1907 case 2: pd[idx+2] = *b++;
wolfSSL 13:f67a6c6013ca 1908 case 1: pd[idx+3] = *b++;
wolfSSL 13:f67a6c6013ca 1909 idx -= 4;
wolfSSL 13:f67a6c6013ca 1910 } while ((c -= 4) > 0);
wolfSSL 13:f67a6c6013ca 1911 }
wolfSSL 13:f67a6c6013ca 1912 }
wolfSSL 13:f67a6c6013ca 1913 #else
wolfSSL 13:f67a6c6013ca 1914 for (c -= 1; c >= 0; c -= 1) {
wolfSSL 13:f67a6c6013ca 1915 pd[c] = *b++;
wolfSSL 13:f67a6c6013ca 1916 }
wolfSSL 13:f67a6c6013ca 1917 #endif
wolfSSL 13:f67a6c6013ca 1918 }
wolfSSL 13:f67a6c6013ca 1919 #else
wolfSSL 13:f67a6c6013ca 1920 /* read the bytes in */
wolfSSL 13:f67a6c6013ca 1921 for (; c > 0; c--) {
wolfSSL 13:f67a6c6013ca 1922 fp_mul_2d (a, 8, a);
wolfSSL 13:f67a6c6013ca 1923 a->dp[0] |= *b++;
wolfSSL 13:f67a6c6013ca 1924
wolfSSL 13:f67a6c6013ca 1925 if (a->used == 0) {
wolfSSL 13:f67a6c6013ca 1926 a->used = 1;
wolfSSL 13:f67a6c6013ca 1927 }
wolfSSL 13:f67a6c6013ca 1928 }
wolfSSL 13:f67a6c6013ca 1929 #endif
wolfSSL 13:f67a6c6013ca 1930 fp_clamp (a);
wolfSSL 13:f67a6c6013ca 1931 }
wolfSSL 13:f67a6c6013ca 1932
wolfSSL 13:f67a6c6013ca 1933 int fp_to_unsigned_bin_at_pos(int x, fp_int *t, unsigned char *b)
wolfSSL 13:f67a6c6013ca 1934 {
wolfSSL 13:f67a6c6013ca 1935 while (fp_iszero (t) == FP_NO) {
wolfSSL 13:f67a6c6013ca 1936 b[x++] = (unsigned char) (t->dp[0] & 255);
wolfSSL 13:f67a6c6013ca 1937 fp_div_2d (t, 8, t, NULL);
wolfSSL 13:f67a6c6013ca 1938 }
wolfSSL 13:f67a6c6013ca 1939 return x;
wolfSSL 13:f67a6c6013ca 1940 }
wolfSSL 13:f67a6c6013ca 1941
wolfSSL 13:f67a6c6013ca 1942 void fp_to_unsigned_bin(fp_int *a, unsigned char *b)
wolfSSL 13:f67a6c6013ca 1943 {
wolfSSL 13:f67a6c6013ca 1944 int x;
wolfSSL 13:f67a6c6013ca 1945 fp_int t;
wolfSSL 13:f67a6c6013ca 1946
wolfSSL 13:f67a6c6013ca 1947 fp_init_copy(&t, a);
wolfSSL 13:f67a6c6013ca 1948
wolfSSL 13:f67a6c6013ca 1949 x = fp_to_unsigned_bin_at_pos(0, &t, b);
wolfSSL 13:f67a6c6013ca 1950 fp_reverse (b, x);
wolfSSL 13:f67a6c6013ca 1951 }
wolfSSL 13:f67a6c6013ca 1952
wolfSSL 13:f67a6c6013ca 1953 int fp_unsigned_bin_size(fp_int *a)
wolfSSL 13:f67a6c6013ca 1954 {
wolfSSL 13:f67a6c6013ca 1955 int size = fp_count_bits (a);
wolfSSL 13:f67a6c6013ca 1956 return (size / 8 + ((size & 7) != 0 ? 1 : 0));
wolfSSL 13:f67a6c6013ca 1957 }
wolfSSL 13:f67a6c6013ca 1958
wolfSSL 13:f67a6c6013ca 1959 void fp_set(fp_int *a, fp_digit b)
wolfSSL 13:f67a6c6013ca 1960 {
wolfSSL 13:f67a6c6013ca 1961 fp_zero(a);
wolfSSL 13:f67a6c6013ca 1962 a->dp[0] = b;
wolfSSL 13:f67a6c6013ca 1963 a->used = a->dp[0] ? 1 : 0;
wolfSSL 13:f67a6c6013ca 1964 }
wolfSSL 13:f67a6c6013ca 1965
wolfSSL 13:f67a6c6013ca 1966
wolfSSL 13:f67a6c6013ca 1967 #ifndef MP_SET_CHUNK_BITS
wolfSSL 13:f67a6c6013ca 1968 #define MP_SET_CHUNK_BITS 4
wolfSSL 13:f67a6c6013ca 1969 #endif
wolfSSL 13:f67a6c6013ca 1970 void fp_set_int(fp_int *a, unsigned long b)
wolfSSL 13:f67a6c6013ca 1971 {
wolfSSL 13:f67a6c6013ca 1972 int x;
wolfSSL 13:f67a6c6013ca 1973
wolfSSL 13:f67a6c6013ca 1974 /* use direct fp_set if b is less than fp_digit max */
wolfSSL 13:f67a6c6013ca 1975 if (b < FP_DIGIT_MAX) {
wolfSSL 13:f67a6c6013ca 1976 fp_set (a, b);
wolfSSL 13:f67a6c6013ca 1977 return;
wolfSSL 13:f67a6c6013ca 1978 }
wolfSSL 13:f67a6c6013ca 1979
wolfSSL 13:f67a6c6013ca 1980 fp_zero (a);
wolfSSL 13:f67a6c6013ca 1981
wolfSSL 13:f67a6c6013ca 1982 /* set chunk bits at a time */
wolfSSL 13:f67a6c6013ca 1983 for (x = 0; x < (int)(sizeof(b) * 8) / MP_SET_CHUNK_BITS; x++) {
wolfSSL 13:f67a6c6013ca 1984 fp_mul_2d (a, MP_SET_CHUNK_BITS, a);
wolfSSL 13:f67a6c6013ca 1985
wolfSSL 13:f67a6c6013ca 1986 /* OR in the top bits of the source */
wolfSSL 13:f67a6c6013ca 1987 a->dp[0] |= (b >> ((sizeof(b) * 8) - MP_SET_CHUNK_BITS)) &
wolfSSL 13:f67a6c6013ca 1988 ((1 << MP_SET_CHUNK_BITS) - 1);
wolfSSL 13:f67a6c6013ca 1989
wolfSSL 13:f67a6c6013ca 1990 /* shift the source up to the next chunk bits */
wolfSSL 13:f67a6c6013ca 1991 b <<= MP_SET_CHUNK_BITS;
wolfSSL 13:f67a6c6013ca 1992
wolfSSL 13:f67a6c6013ca 1993 /* ensure that digits are not clamped off */
wolfSSL 13:f67a6c6013ca 1994 a->used += 1;
wolfSSL 13:f67a6c6013ca 1995 }
wolfSSL 13:f67a6c6013ca 1996
wolfSSL 13:f67a6c6013ca 1997 /* clamp digits */
wolfSSL 13:f67a6c6013ca 1998 fp_clamp(a);
wolfSSL 13:f67a6c6013ca 1999 }
wolfSSL 13:f67a6c6013ca 2000
wolfSSL 13:f67a6c6013ca 2001 /* check if a bit is set */
wolfSSL 13:f67a6c6013ca 2002 int fp_is_bit_set (fp_int *a, fp_digit b)
wolfSSL 13:f67a6c6013ca 2003 {
wolfSSL 13:f67a6c6013ca 2004 fp_digit i;
wolfSSL 13:f67a6c6013ca 2005
wolfSSL 13:f67a6c6013ca 2006 if (b > FP_MAX_BITS)
wolfSSL 13:f67a6c6013ca 2007 return 0;
wolfSSL 13:f67a6c6013ca 2008 else
wolfSSL 13:f67a6c6013ca 2009 i = b/DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 2010
wolfSSL 13:f67a6c6013ca 2011 if ((fp_digit)a->used < i)
wolfSSL 13:f67a6c6013ca 2012 return 0;
wolfSSL 13:f67a6c6013ca 2013
wolfSSL 13:f67a6c6013ca 2014 return (int)((a->dp[i] >> b%DIGIT_BIT) & (fp_digit)1);
wolfSSL 13:f67a6c6013ca 2015 }
wolfSSL 13:f67a6c6013ca 2016
wolfSSL 13:f67a6c6013ca 2017 /* set the b bit of a */
wolfSSL 13:f67a6c6013ca 2018 int fp_set_bit (fp_int * a, fp_digit b)
wolfSSL 13:f67a6c6013ca 2019 {
wolfSSL 13:f67a6c6013ca 2020 fp_digit i;
wolfSSL 13:f67a6c6013ca 2021
wolfSSL 13:f67a6c6013ca 2022 if (b > FP_MAX_BITS)
wolfSSL 13:f67a6c6013ca 2023 return 0;
wolfSSL 13:f67a6c6013ca 2024 else
wolfSSL 13:f67a6c6013ca 2025 i = b/DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 2026
wolfSSL 13:f67a6c6013ca 2027 /* set the used count of where the bit will go if required */
wolfSSL 13:f67a6c6013ca 2028 if (a->used < (int)(i+1))
wolfSSL 13:f67a6c6013ca 2029 a->used = (int)(i+1);
wolfSSL 13:f67a6c6013ca 2030
wolfSSL 13:f67a6c6013ca 2031 /* put the single bit in its place */
wolfSSL 13:f67a6c6013ca 2032 a->dp[i] |= ((fp_digit)1) << (b % DIGIT_BIT);
wolfSSL 13:f67a6c6013ca 2033
wolfSSL 13:f67a6c6013ca 2034 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2035 }
wolfSSL 13:f67a6c6013ca 2036
wolfSSL 13:f67a6c6013ca 2037 int fp_count_bits (fp_int * a)
wolfSSL 13:f67a6c6013ca 2038 {
wolfSSL 13:f67a6c6013ca 2039 int r;
wolfSSL 13:f67a6c6013ca 2040 fp_digit q;
wolfSSL 13:f67a6c6013ca 2041
wolfSSL 13:f67a6c6013ca 2042 /* shortcut */
wolfSSL 13:f67a6c6013ca 2043 if (a->used == 0) {
wolfSSL 13:f67a6c6013ca 2044 return 0;
wolfSSL 13:f67a6c6013ca 2045 }
wolfSSL 13:f67a6c6013ca 2046
wolfSSL 13:f67a6c6013ca 2047 /* get number of digits and add that */
wolfSSL 13:f67a6c6013ca 2048 r = (a->used - 1) * DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 2049
wolfSSL 13:f67a6c6013ca 2050 /* take the last digit and count the bits in it */
wolfSSL 13:f67a6c6013ca 2051 q = a->dp[a->used - 1];
wolfSSL 13:f67a6c6013ca 2052 while (q > ((fp_digit) 0)) {
wolfSSL 13:f67a6c6013ca 2053 ++r;
wolfSSL 13:f67a6c6013ca 2054 q >>= ((fp_digit) 1);
wolfSSL 13:f67a6c6013ca 2055 }
wolfSSL 13:f67a6c6013ca 2056
wolfSSL 13:f67a6c6013ca 2057 return r;
wolfSSL 13:f67a6c6013ca 2058 }
wolfSSL 13:f67a6c6013ca 2059
wolfSSL 13:f67a6c6013ca 2060 int fp_leading_bit(fp_int *a)
wolfSSL 13:f67a6c6013ca 2061 {
wolfSSL 13:f67a6c6013ca 2062 int bit = 0;
wolfSSL 13:f67a6c6013ca 2063
wolfSSL 13:f67a6c6013ca 2064 if (a->used != 0) {
wolfSSL 13:f67a6c6013ca 2065 fp_digit q = a->dp[a->used - 1];
wolfSSL 13:f67a6c6013ca 2066 int qSz = sizeof(fp_digit);
wolfSSL 13:f67a6c6013ca 2067
wolfSSL 13:f67a6c6013ca 2068 while (qSz > 0) {
wolfSSL 13:f67a6c6013ca 2069 if ((unsigned char)q != 0)
wolfSSL 13:f67a6c6013ca 2070 bit = (q & 0x80) != 0;
wolfSSL 13:f67a6c6013ca 2071 q >>= 8;
wolfSSL 13:f67a6c6013ca 2072 qSz--;
wolfSSL 13:f67a6c6013ca 2073 }
wolfSSL 13:f67a6c6013ca 2074 }
wolfSSL 13:f67a6c6013ca 2075
wolfSSL 13:f67a6c6013ca 2076 return bit;
wolfSSL 13:f67a6c6013ca 2077 }
wolfSSL 13:f67a6c6013ca 2078
wolfSSL 13:f67a6c6013ca 2079 void fp_lshd(fp_int *a, int x)
wolfSSL 13:f67a6c6013ca 2080 {
wolfSSL 13:f67a6c6013ca 2081 int y;
wolfSSL 13:f67a6c6013ca 2082
wolfSSL 13:f67a6c6013ca 2083 /* move up and truncate as required */
wolfSSL 13:f67a6c6013ca 2084 y = MIN(a->used + x - 1, (int)(FP_SIZE-1));
wolfSSL 13:f67a6c6013ca 2085
wolfSSL 13:f67a6c6013ca 2086 /* store new size */
wolfSSL 13:f67a6c6013ca 2087 a->used = y + 1;
wolfSSL 13:f67a6c6013ca 2088
wolfSSL 13:f67a6c6013ca 2089 /* move digits */
wolfSSL 13:f67a6c6013ca 2090 for (; y >= x; y--) {
wolfSSL 13:f67a6c6013ca 2091 a->dp[y] = a->dp[y-x];
wolfSSL 13:f67a6c6013ca 2092 }
wolfSSL 13:f67a6c6013ca 2093
wolfSSL 13:f67a6c6013ca 2094 /* zero lower digits */
wolfSSL 13:f67a6c6013ca 2095 for (; y >= 0; y--) {
wolfSSL 13:f67a6c6013ca 2096 a->dp[y] = 0;
wolfSSL 13:f67a6c6013ca 2097 }
wolfSSL 13:f67a6c6013ca 2098
wolfSSL 13:f67a6c6013ca 2099 /* clamp digits */
wolfSSL 13:f67a6c6013ca 2100 fp_clamp(a);
wolfSSL 13:f67a6c6013ca 2101 }
wolfSSL 13:f67a6c6013ca 2102
wolfSSL 13:f67a6c6013ca 2103
wolfSSL 13:f67a6c6013ca 2104 /* right shift by bit count */
wolfSSL 13:f67a6c6013ca 2105 void fp_rshb(fp_int *c, int x)
wolfSSL 13:f67a6c6013ca 2106 {
wolfSSL 13:f67a6c6013ca 2107 fp_digit *tmpc, mask, shift;
wolfSSL 13:f67a6c6013ca 2108 fp_digit r, rr;
wolfSSL 13:f67a6c6013ca 2109 fp_digit D = x;
wolfSSL 13:f67a6c6013ca 2110
wolfSSL 13:f67a6c6013ca 2111 /* mask */
wolfSSL 13:f67a6c6013ca 2112 mask = (((fp_digit)1) << D) - 1;
wolfSSL 13:f67a6c6013ca 2113
wolfSSL 13:f67a6c6013ca 2114 /* shift for lsb */
wolfSSL 13:f67a6c6013ca 2115 shift = DIGIT_BIT - D;
wolfSSL 13:f67a6c6013ca 2116
wolfSSL 13:f67a6c6013ca 2117 /* alias */
wolfSSL 13:f67a6c6013ca 2118 tmpc = c->dp + (c->used - 1);
wolfSSL 13:f67a6c6013ca 2119
wolfSSL 13:f67a6c6013ca 2120 /* carry */
wolfSSL 13:f67a6c6013ca 2121 r = 0;
wolfSSL 13:f67a6c6013ca 2122 for (x = c->used - 1; x >= 0; x--) {
wolfSSL 13:f67a6c6013ca 2123 /* get the lower bits of this word in a temp */
wolfSSL 13:f67a6c6013ca 2124 rr = *tmpc & mask;
wolfSSL 13:f67a6c6013ca 2125
wolfSSL 13:f67a6c6013ca 2126 /* shift the current word and mix in the carry bits from previous word */
wolfSSL 13:f67a6c6013ca 2127 *tmpc = (*tmpc >> D) | (r << shift);
wolfSSL 13:f67a6c6013ca 2128 --tmpc;
wolfSSL 13:f67a6c6013ca 2129
wolfSSL 13:f67a6c6013ca 2130 /* set the carry to the carry bits of the current word found above */
wolfSSL 13:f67a6c6013ca 2131 r = rr;
wolfSSL 13:f67a6c6013ca 2132 }
wolfSSL 13:f67a6c6013ca 2133
wolfSSL 13:f67a6c6013ca 2134 /* clamp digits */
wolfSSL 13:f67a6c6013ca 2135 fp_clamp(c);
wolfSSL 13:f67a6c6013ca 2136 }
wolfSSL 13:f67a6c6013ca 2137
wolfSSL 13:f67a6c6013ca 2138
wolfSSL 13:f67a6c6013ca 2139 void fp_rshd(fp_int *a, int x)
wolfSSL 13:f67a6c6013ca 2140 {
wolfSSL 13:f67a6c6013ca 2141 int y;
wolfSSL 13:f67a6c6013ca 2142
wolfSSL 13:f67a6c6013ca 2143 /* too many digits just zero and return */
wolfSSL 13:f67a6c6013ca 2144 if (x >= a->used) {
wolfSSL 13:f67a6c6013ca 2145 fp_zero(a);
wolfSSL 13:f67a6c6013ca 2146 return;
wolfSSL 13:f67a6c6013ca 2147 }
wolfSSL 13:f67a6c6013ca 2148
wolfSSL 13:f67a6c6013ca 2149 /* shift */
wolfSSL 13:f67a6c6013ca 2150 for (y = 0; y < a->used - x; y++) {
wolfSSL 13:f67a6c6013ca 2151 a->dp[y] = a->dp[y+x];
wolfSSL 13:f67a6c6013ca 2152 }
wolfSSL 13:f67a6c6013ca 2153
wolfSSL 13:f67a6c6013ca 2154 /* zero rest */
wolfSSL 13:f67a6c6013ca 2155 for (; y < a->used; y++) {
wolfSSL 13:f67a6c6013ca 2156 a->dp[y] = 0;
wolfSSL 13:f67a6c6013ca 2157 }
wolfSSL 13:f67a6c6013ca 2158
wolfSSL 13:f67a6c6013ca 2159 /* decrement count */
wolfSSL 13:f67a6c6013ca 2160 a->used -= x;
wolfSSL 13:f67a6c6013ca 2161 fp_clamp(a);
wolfSSL 13:f67a6c6013ca 2162 }
wolfSSL 13:f67a6c6013ca 2163
wolfSSL 13:f67a6c6013ca 2164 /* reverse an array, used for radix code */
wolfSSL 13:f67a6c6013ca 2165 void fp_reverse (unsigned char *s, int len)
wolfSSL 13:f67a6c6013ca 2166 {
wolfSSL 13:f67a6c6013ca 2167 int ix, iy;
wolfSSL 13:f67a6c6013ca 2168 unsigned char t;
wolfSSL 13:f67a6c6013ca 2169
wolfSSL 13:f67a6c6013ca 2170 ix = 0;
wolfSSL 13:f67a6c6013ca 2171 iy = len - 1;
wolfSSL 13:f67a6c6013ca 2172 while (ix < iy) {
wolfSSL 13:f67a6c6013ca 2173 t = s[ix];
wolfSSL 13:f67a6c6013ca 2174 s[ix] = s[iy];
wolfSSL 13:f67a6c6013ca 2175 s[iy] = t;
wolfSSL 13:f67a6c6013ca 2176 ++ix;
wolfSSL 13:f67a6c6013ca 2177 --iy;
wolfSSL 13:f67a6c6013ca 2178 }
wolfSSL 13:f67a6c6013ca 2179 }
wolfSSL 13:f67a6c6013ca 2180
wolfSSL 13:f67a6c6013ca 2181
wolfSSL 13:f67a6c6013ca 2182 /* c = a - b */
wolfSSL 13:f67a6c6013ca 2183 void fp_sub_d(fp_int *a, fp_digit b, fp_int *c)
wolfSSL 13:f67a6c6013ca 2184 {
wolfSSL 13:f67a6c6013ca 2185 fp_int tmp;
wolfSSL 13:f67a6c6013ca 2186 fp_init(&tmp);
wolfSSL 13:f67a6c6013ca 2187 fp_set(&tmp, b);
wolfSSL 13:f67a6c6013ca 2188 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 2189 if (c->size < FP_SIZE) {
wolfSSL 13:f67a6c6013ca 2190 fp_sub(a, &tmp, &tmp);
wolfSSL 13:f67a6c6013ca 2191 fp_copy(&tmp, c);
wolfSSL 13:f67a6c6013ca 2192 } else
wolfSSL 13:f67a6c6013ca 2193 #endif
wolfSSL 13:f67a6c6013ca 2194 {
wolfSSL 13:f67a6c6013ca 2195 fp_sub(a, &tmp, c);
wolfSSL 13:f67a6c6013ca 2196 }
wolfSSL 13:f67a6c6013ca 2197 }
wolfSSL 13:f67a6c6013ca 2198
wolfSSL 13:f67a6c6013ca 2199
wolfSSL 13:f67a6c6013ca 2200 /* wolfSSL callers from normal lib */
wolfSSL 13:f67a6c6013ca 2201
wolfSSL 13:f67a6c6013ca 2202 /* init a new mp_int */
wolfSSL 13:f67a6c6013ca 2203 int mp_init (mp_int * a)
wolfSSL 13:f67a6c6013ca 2204 {
wolfSSL 13:f67a6c6013ca 2205 if (a)
wolfSSL 13:f67a6c6013ca 2206 fp_init(a);
wolfSSL 13:f67a6c6013ca 2207 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2208 }
wolfSSL 13:f67a6c6013ca 2209
wolfSSL 13:f67a6c6013ca 2210 void fp_init(fp_int *a)
wolfSSL 13:f67a6c6013ca 2211 {
wolfSSL 13:f67a6c6013ca 2212 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 2213 a->size = FP_SIZE;
wolfSSL 13:f67a6c6013ca 2214 #endif
wolfSSL 13:f67a6c6013ca 2215 #ifdef HAVE_WOLF_BIGINT
wolfSSL 13:f67a6c6013ca 2216 wc_bigint_init(&a->raw);
wolfSSL 13:f67a6c6013ca 2217 #endif
wolfSSL 13:f67a6c6013ca 2218 fp_zero(a);
wolfSSL 13:f67a6c6013ca 2219 }
wolfSSL 13:f67a6c6013ca 2220
wolfSSL 13:f67a6c6013ca 2221 void fp_zero(fp_int *a)
wolfSSL 13:f67a6c6013ca 2222 {
wolfSSL 13:f67a6c6013ca 2223 int size = FP_SIZE;
wolfSSL 13:f67a6c6013ca 2224 a->used = 0;
wolfSSL 13:f67a6c6013ca 2225 a->sign = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 2226 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 2227 size = a->size;
wolfSSL 13:f67a6c6013ca 2228 #endif
wolfSSL 13:f67a6c6013ca 2229 XMEMSET(a->dp, 0, size * sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 2230 }
wolfSSL 13:f67a6c6013ca 2231
wolfSSL 13:f67a6c6013ca 2232 void fp_clear(fp_int *a)
wolfSSL 13:f67a6c6013ca 2233 {
wolfSSL 13:f67a6c6013ca 2234 int size = FP_SIZE;
wolfSSL 13:f67a6c6013ca 2235 a->used = 0;
wolfSSL 13:f67a6c6013ca 2236 a->sign = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 2237 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 2238 size = a->size;
wolfSSL 13:f67a6c6013ca 2239 #endif
wolfSSL 13:f67a6c6013ca 2240 XMEMSET(a->dp, 0, size * sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 2241 fp_free(a);
wolfSSL 13:f67a6c6013ca 2242 }
wolfSSL 13:f67a6c6013ca 2243
wolfSSL 13:f67a6c6013ca 2244 void fp_forcezero (mp_int * a)
wolfSSL 13:f67a6c6013ca 2245 {
wolfSSL 13:f67a6c6013ca 2246 int size = FP_SIZE;
wolfSSL 13:f67a6c6013ca 2247 a->used = 0;
wolfSSL 13:f67a6c6013ca 2248 a->sign = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 2249 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 2250 size = a->size;
wolfSSL 13:f67a6c6013ca 2251 #endif
wolfSSL 13:f67a6c6013ca 2252 ForceZero(a->dp, size * sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 2253 #ifdef HAVE_WOLF_BIGINT
wolfSSL 13:f67a6c6013ca 2254 wc_bigint_zero(&a->raw);
wolfSSL 13:f67a6c6013ca 2255 #endif
wolfSSL 13:f67a6c6013ca 2256 fp_free(a);
wolfSSL 13:f67a6c6013ca 2257 }
wolfSSL 13:f67a6c6013ca 2258
wolfSSL 13:f67a6c6013ca 2259 void mp_forcezero (mp_int * a)
wolfSSL 13:f67a6c6013ca 2260 {
wolfSSL 13:f67a6c6013ca 2261 fp_forcezero(a);
wolfSSL 13:f67a6c6013ca 2262 }
wolfSSL 13:f67a6c6013ca 2263
wolfSSL 13:f67a6c6013ca 2264 void fp_free(fp_int* a)
wolfSSL 13:f67a6c6013ca 2265 {
wolfSSL 13:f67a6c6013ca 2266 #ifdef HAVE_WOLF_BIGINT
wolfSSL 13:f67a6c6013ca 2267 wc_bigint_free(&a->raw);
wolfSSL 13:f67a6c6013ca 2268 #else
wolfSSL 13:f67a6c6013ca 2269 (void)a;
wolfSSL 13:f67a6c6013ca 2270 #endif
wolfSSL 13:f67a6c6013ca 2271 }
wolfSSL 13:f67a6c6013ca 2272
wolfSSL 13:f67a6c6013ca 2273
wolfSSL 13:f67a6c6013ca 2274 /* clear one (frees) */
wolfSSL 13:f67a6c6013ca 2275 void mp_clear (mp_int * a)
wolfSSL 13:f67a6c6013ca 2276 {
wolfSSL 13:f67a6c6013ca 2277 if (a == NULL)
wolfSSL 13:f67a6c6013ca 2278 return;
wolfSSL 13:f67a6c6013ca 2279 fp_clear(a);
wolfSSL 13:f67a6c6013ca 2280 }
wolfSSL 13:f67a6c6013ca 2281
wolfSSL 13:f67a6c6013ca 2282 void mp_free(mp_int* a)
wolfSSL 13:f67a6c6013ca 2283 {
wolfSSL 13:f67a6c6013ca 2284 fp_free(a);
wolfSSL 13:f67a6c6013ca 2285 }
wolfSSL 13:f67a6c6013ca 2286
wolfSSL 13:f67a6c6013ca 2287 /* handle up to 6 inits */
wolfSSL 13:f67a6c6013ca 2288 int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d,
wolfSSL 13:f67a6c6013ca 2289 mp_int* e, mp_int* f)
wolfSSL 13:f67a6c6013ca 2290 {
wolfSSL 13:f67a6c6013ca 2291 if (a)
wolfSSL 13:f67a6c6013ca 2292 fp_init(a);
wolfSSL 13:f67a6c6013ca 2293 if (b)
wolfSSL 13:f67a6c6013ca 2294 fp_init(b);
wolfSSL 13:f67a6c6013ca 2295 if (c)
wolfSSL 13:f67a6c6013ca 2296 fp_init(c);
wolfSSL 13:f67a6c6013ca 2297 if (d)
wolfSSL 13:f67a6c6013ca 2298 fp_init(d);
wolfSSL 13:f67a6c6013ca 2299 if (e)
wolfSSL 13:f67a6c6013ca 2300 fp_init(e);
wolfSSL 13:f67a6c6013ca 2301 if (f)
wolfSSL 13:f67a6c6013ca 2302 fp_init(f);
wolfSSL 13:f67a6c6013ca 2303
wolfSSL 13:f67a6c6013ca 2304 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2305 }
wolfSSL 13:f67a6c6013ca 2306
wolfSSL 13:f67a6c6013ca 2307 /* high level addition (handles signs) */
wolfSSL 13:f67a6c6013ca 2308 int mp_add (mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2309 {
wolfSSL 13:f67a6c6013ca 2310 fp_add(a, b, c);
wolfSSL 13:f67a6c6013ca 2311 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2312 }
wolfSSL 13:f67a6c6013ca 2313
wolfSSL 13:f67a6c6013ca 2314 /* high level subtraction (handles signs) */
wolfSSL 13:f67a6c6013ca 2315 int mp_sub (mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2316 {
wolfSSL 13:f67a6c6013ca 2317 fp_sub(a, b, c);
wolfSSL 13:f67a6c6013ca 2318 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2319 }
wolfSSL 13:f67a6c6013ca 2320
wolfSSL 13:f67a6c6013ca 2321 /* high level multiplication (handles sign) */
wolfSSL 13:f67a6c6013ca 2322 #if defined(FREESCALE_LTC_TFM)
wolfSSL 13:f67a6c6013ca 2323 int wolfcrypt_mp_mul(mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2324 #else
wolfSSL 13:f67a6c6013ca 2325 int mp_mul (mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2326 #endif
wolfSSL 13:f67a6c6013ca 2327 {
wolfSSL 13:f67a6c6013ca 2328 fp_mul(a, b, c);
wolfSSL 13:f67a6c6013ca 2329 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2330 }
wolfSSL 13:f67a6c6013ca 2331
wolfSSL 13:f67a6c6013ca 2332 int mp_mul_d (mp_int * a, mp_digit b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2333 {
wolfSSL 13:f67a6c6013ca 2334 fp_mul_d(a, b, c);
wolfSSL 13:f67a6c6013ca 2335 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2336 }
wolfSSL 13:f67a6c6013ca 2337
wolfSSL 13:f67a6c6013ca 2338 /* d = a * b (mod c) */
wolfSSL 13:f67a6c6013ca 2339 #if defined(FREESCALE_LTC_TFM)
wolfSSL 13:f67a6c6013ca 2340 int wolfcrypt_mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
wolfSSL 13:f67a6c6013ca 2341 #else
wolfSSL 13:f67a6c6013ca 2342 int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
wolfSSL 13:f67a6c6013ca 2343 #endif
wolfSSL 13:f67a6c6013ca 2344 {
wolfSSL 13:f67a6c6013ca 2345 return fp_mulmod(a, b, c, d);
wolfSSL 13:f67a6c6013ca 2346 }
wolfSSL 13:f67a6c6013ca 2347
wolfSSL 13:f67a6c6013ca 2348 /* d = a - b (mod c) */
wolfSSL 13:f67a6c6013ca 2349 int mp_submod(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
wolfSSL 13:f67a6c6013ca 2350 {
wolfSSL 13:f67a6c6013ca 2351 return fp_submod(a, b, c, d);
wolfSSL 13:f67a6c6013ca 2352 }
wolfSSL 13:f67a6c6013ca 2353
wolfSSL 13:f67a6c6013ca 2354 /* d = a + b (mod c) */
wolfSSL 13:f67a6c6013ca 2355 int mp_addmod(mp_int *a, mp_int *b, mp_int *c, mp_int *d)
wolfSSL 13:f67a6c6013ca 2356 {
wolfSSL 13:f67a6c6013ca 2357 return fp_addmod(a, b, c, d);
wolfSSL 13:f67a6c6013ca 2358 }
wolfSSL 13:f67a6c6013ca 2359
wolfSSL 13:f67a6c6013ca 2360 /* c = a mod b, 0 <= c < b */
wolfSSL 13:f67a6c6013ca 2361 #if defined(FREESCALE_LTC_TFM)
wolfSSL 13:f67a6c6013ca 2362 int wolfcrypt_mp_mod (mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2363 #else
wolfSSL 13:f67a6c6013ca 2364 int mp_mod (mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2365 #endif
wolfSSL 13:f67a6c6013ca 2366 {
wolfSSL 13:f67a6c6013ca 2367 return fp_mod (a, b, c);
wolfSSL 13:f67a6c6013ca 2368 }
wolfSSL 13:f67a6c6013ca 2369
wolfSSL 13:f67a6c6013ca 2370 /* hac 14.61, pp608 */
wolfSSL 13:f67a6c6013ca 2371 #if defined(FREESCALE_LTC_TFM)
wolfSSL 13:f67a6c6013ca 2372 int wolfcrypt_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2373 #else
wolfSSL 13:f67a6c6013ca 2374 int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
wolfSSL 13:f67a6c6013ca 2375 #endif
wolfSSL 13:f67a6c6013ca 2376 {
wolfSSL 13:f67a6c6013ca 2377 return fp_invmod(a, b, c);
wolfSSL 13:f67a6c6013ca 2378 }
wolfSSL 13:f67a6c6013ca 2379
wolfSSL 13:f67a6c6013ca 2380 /* this is a shell function that calls either the normal or Montgomery
wolfSSL 13:f67a6c6013ca 2381 * exptmod functions. Originally the call to the montgomery code was
wolfSSL 13:f67a6c6013ca 2382 * embedded in the normal function but that wasted alot of stack space
wolfSSL 13:f67a6c6013ca 2383 * for nothing (since 99% of the time the Montgomery code would be called)
wolfSSL 13:f67a6c6013ca 2384 */
wolfSSL 13:f67a6c6013ca 2385 #if defined(FREESCALE_LTC_TFM)
wolfSSL 13:f67a6c6013ca 2386 int wolfcrypt_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
wolfSSL 13:f67a6c6013ca 2387 #else
wolfSSL 13:f67a6c6013ca 2388 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
wolfSSL 13:f67a6c6013ca 2389 #endif
wolfSSL 13:f67a6c6013ca 2390 {
wolfSSL 13:f67a6c6013ca 2391 return fp_exptmod(G, X, P, Y);
wolfSSL 13:f67a6c6013ca 2392 }
wolfSSL 13:f67a6c6013ca 2393
wolfSSL 13:f67a6c6013ca 2394 /* compare two ints (signed)*/
wolfSSL 13:f67a6c6013ca 2395 int mp_cmp (mp_int * a, mp_int * b)
wolfSSL 13:f67a6c6013ca 2396 {
wolfSSL 13:f67a6c6013ca 2397 return fp_cmp(a, b);
wolfSSL 13:f67a6c6013ca 2398 }
wolfSSL 13:f67a6c6013ca 2399
wolfSSL 13:f67a6c6013ca 2400 /* compare a digit */
wolfSSL 13:f67a6c6013ca 2401 int mp_cmp_d(mp_int * a, mp_digit b)
wolfSSL 13:f67a6c6013ca 2402 {
wolfSSL 13:f67a6c6013ca 2403 return fp_cmp_d(a, b);
wolfSSL 13:f67a6c6013ca 2404 }
wolfSSL 13:f67a6c6013ca 2405
wolfSSL 13:f67a6c6013ca 2406 /* get the size for an unsigned equivalent */
wolfSSL 13:f67a6c6013ca 2407 int mp_unsigned_bin_size (mp_int * a)
wolfSSL 13:f67a6c6013ca 2408 {
wolfSSL 13:f67a6c6013ca 2409 return fp_unsigned_bin_size(a);
wolfSSL 13:f67a6c6013ca 2410 }
wolfSSL 13:f67a6c6013ca 2411
wolfSSL 13:f67a6c6013ca 2412 int mp_to_unsigned_bin_at_pos(int x, fp_int *t, unsigned char *b)
wolfSSL 13:f67a6c6013ca 2413 {
wolfSSL 13:f67a6c6013ca 2414 return fp_to_unsigned_bin_at_pos(x, t, b);
wolfSSL 13:f67a6c6013ca 2415 }
wolfSSL 13:f67a6c6013ca 2416
wolfSSL 13:f67a6c6013ca 2417 /* store in unsigned [big endian] format */
wolfSSL 13:f67a6c6013ca 2418 int mp_to_unsigned_bin (mp_int * a, unsigned char *b)
wolfSSL 13:f67a6c6013ca 2419 {
wolfSSL 13:f67a6c6013ca 2420 fp_to_unsigned_bin(a,b);
wolfSSL 13:f67a6c6013ca 2421 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2422 }
wolfSSL 13:f67a6c6013ca 2423
wolfSSL 13:f67a6c6013ca 2424 /* reads a unsigned char array, assumes the msb is stored first [big endian] */
wolfSSL 13:f67a6c6013ca 2425 int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
wolfSSL 13:f67a6c6013ca 2426 {
wolfSSL 13:f67a6c6013ca 2427 fp_read_unsigned_bin(a, b, c);
wolfSSL 13:f67a6c6013ca 2428 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2429 }
wolfSSL 13:f67a6c6013ca 2430
wolfSSL 13:f67a6c6013ca 2431
wolfSSL 13:f67a6c6013ca 2432 int mp_sub_d(fp_int *a, fp_digit b, fp_int *c)
wolfSSL 13:f67a6c6013ca 2433 {
wolfSSL 13:f67a6c6013ca 2434 fp_sub_d(a, b, c);
wolfSSL 13:f67a6c6013ca 2435 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2436 }
wolfSSL 13:f67a6c6013ca 2437
wolfSSL 13:f67a6c6013ca 2438 int mp_mul_2d(fp_int *a, int b, fp_int *c)
wolfSSL 13:f67a6c6013ca 2439 {
wolfSSL 13:f67a6c6013ca 2440 fp_mul_2d(a, b, c);
wolfSSL 13:f67a6c6013ca 2441 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2442 }
wolfSSL 13:f67a6c6013ca 2443
wolfSSL 13:f67a6c6013ca 2444 int mp_div(fp_int * a, fp_int * b, fp_int * c, fp_int * d)
wolfSSL 13:f67a6c6013ca 2445 {
wolfSSL 13:f67a6c6013ca 2446 return fp_div(a, b, c, d);
wolfSSL 13:f67a6c6013ca 2447 }
wolfSSL 13:f67a6c6013ca 2448
wolfSSL 13:f67a6c6013ca 2449 int mp_div_2d(fp_int* a, int b, fp_int* c, fp_int* d)
wolfSSL 13:f67a6c6013ca 2450 {
wolfSSL 13:f67a6c6013ca 2451 fp_div_2d(a, b, c, d);
wolfSSL 13:f67a6c6013ca 2452 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2453 }
wolfSSL 13:f67a6c6013ca 2454
wolfSSL 13:f67a6c6013ca 2455 void fp_copy(fp_int *a, fp_int *b)
wolfSSL 13:f67a6c6013ca 2456 {
wolfSSL 13:f67a6c6013ca 2457 /* if source and destination are different */
wolfSSL 13:f67a6c6013ca 2458 if (a != b) {
wolfSSL 13:f67a6c6013ca 2459 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 2460 /* verify a will fit in b */
wolfSSL 13:f67a6c6013ca 2461 if (b->size >= a->used) {
wolfSSL 13:f67a6c6013ca 2462 int x, oldused;
wolfSSL 13:f67a6c6013ca 2463 oldused = b->used;
wolfSSL 13:f67a6c6013ca 2464 b->used = a->used;
wolfSSL 13:f67a6c6013ca 2465 b->sign = a->sign;
wolfSSL 13:f67a6c6013ca 2466
wolfSSL 13:f67a6c6013ca 2467 XMEMCPY(b->dp, a->dp, a->used * sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 2468
wolfSSL 13:f67a6c6013ca 2469 /* zero any excess digits on the destination that we didn't write to */
wolfSSL 13:f67a6c6013ca 2470 for (x = b->used; x >= 0 && x < oldused; x++) {
wolfSSL 13:f67a6c6013ca 2471 b->dp[x] = 0;
wolfSSL 13:f67a6c6013ca 2472 }
wolfSSL 13:f67a6c6013ca 2473 }
wolfSSL 13:f67a6c6013ca 2474 else {
wolfSSL 13:f67a6c6013ca 2475 /* TODO: Handle error case */
wolfSSL 13:f67a6c6013ca 2476 }
wolfSSL 13:f67a6c6013ca 2477 #else
wolfSSL 13:f67a6c6013ca 2478 /* all dp's are same size, so do straight copy */
wolfSSL 13:f67a6c6013ca 2479 b->used = a->used;
wolfSSL 13:f67a6c6013ca 2480 b->sign = a->sign;
wolfSSL 13:f67a6c6013ca 2481 XMEMCPY(b->dp, a->dp, FP_SIZE * sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 2482 #endif
wolfSSL 13:f67a6c6013ca 2483 }
wolfSSL 13:f67a6c6013ca 2484 }
wolfSSL 13:f67a6c6013ca 2485
wolfSSL 13:f67a6c6013ca 2486 void fp_init_copy(fp_int *a, fp_int* b)
wolfSSL 13:f67a6c6013ca 2487 {
wolfSSL 13:f67a6c6013ca 2488 if (a != b) {
wolfSSL 13:f67a6c6013ca 2489 fp_init(a);
wolfSSL 13:f67a6c6013ca 2490 fp_copy(b, a);
wolfSSL 13:f67a6c6013ca 2491 }
wolfSSL 13:f67a6c6013ca 2492 }
wolfSSL 13:f67a6c6013ca 2493
wolfSSL 13:f67a6c6013ca 2494 /* fast math wrappers */
wolfSSL 13:f67a6c6013ca 2495 int mp_copy(fp_int* a, fp_int* b)
wolfSSL 13:f67a6c6013ca 2496 {
wolfSSL 13:f67a6c6013ca 2497 fp_copy(a, b);
wolfSSL 13:f67a6c6013ca 2498 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2499 }
wolfSSL 13:f67a6c6013ca 2500
wolfSSL 13:f67a6c6013ca 2501 int mp_isodd(mp_int* a)
wolfSSL 13:f67a6c6013ca 2502 {
wolfSSL 13:f67a6c6013ca 2503 return fp_isodd(a);
wolfSSL 13:f67a6c6013ca 2504 }
wolfSSL 13:f67a6c6013ca 2505
wolfSSL 13:f67a6c6013ca 2506 int mp_iszero(mp_int* a)
wolfSSL 13:f67a6c6013ca 2507 {
wolfSSL 13:f67a6c6013ca 2508 return fp_iszero(a);
wolfSSL 13:f67a6c6013ca 2509 }
wolfSSL 13:f67a6c6013ca 2510
wolfSSL 13:f67a6c6013ca 2511 int mp_count_bits (mp_int* a)
wolfSSL 13:f67a6c6013ca 2512 {
wolfSSL 13:f67a6c6013ca 2513 return fp_count_bits(a);
wolfSSL 13:f67a6c6013ca 2514 }
wolfSSL 13:f67a6c6013ca 2515
wolfSSL 13:f67a6c6013ca 2516 int mp_leading_bit (mp_int* a)
wolfSSL 13:f67a6c6013ca 2517 {
wolfSSL 13:f67a6c6013ca 2518 return fp_leading_bit(a);
wolfSSL 13:f67a6c6013ca 2519 }
wolfSSL 13:f67a6c6013ca 2520
wolfSSL 13:f67a6c6013ca 2521 void mp_rshb (mp_int* a, int x)
wolfSSL 13:f67a6c6013ca 2522 {
wolfSSL 13:f67a6c6013ca 2523 fp_rshb(a, x);
wolfSSL 13:f67a6c6013ca 2524 }
wolfSSL 13:f67a6c6013ca 2525
wolfSSL 13:f67a6c6013ca 2526 void mp_rshd (mp_int* a, int x)
wolfSSL 13:f67a6c6013ca 2527 {
wolfSSL 13:f67a6c6013ca 2528 fp_rshd(a, x);
wolfSSL 13:f67a6c6013ca 2529 }
wolfSSL 13:f67a6c6013ca 2530
wolfSSL 13:f67a6c6013ca 2531 int mp_set_int(mp_int *a, unsigned long b)
wolfSSL 13:f67a6c6013ca 2532 {
wolfSSL 13:f67a6c6013ca 2533 fp_set_int(a, b);
wolfSSL 13:f67a6c6013ca 2534 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2535 }
wolfSSL 13:f67a6c6013ca 2536
wolfSSL 13:f67a6c6013ca 2537 int mp_is_bit_set (mp_int *a, mp_digit b)
wolfSSL 13:f67a6c6013ca 2538 {
wolfSSL 13:f67a6c6013ca 2539 return fp_is_bit_set(a, b);
wolfSSL 13:f67a6c6013ca 2540 }
wolfSSL 13:f67a6c6013ca 2541
wolfSSL 13:f67a6c6013ca 2542 int mp_set_bit(mp_int *a, mp_digit b)
wolfSSL 13:f67a6c6013ca 2543 {
wolfSSL 13:f67a6c6013ca 2544 return fp_set_bit(a, b);
wolfSSL 13:f67a6c6013ca 2545 }
wolfSSL 13:f67a6c6013ca 2546
wolfSSL 13:f67a6c6013ca 2547 #if defined(WOLFSSL_KEY_GEN) || defined (HAVE_ECC)
wolfSSL 13:f67a6c6013ca 2548
wolfSSL 13:f67a6c6013ca 2549 /* c = a * a (mod b) */
wolfSSL 13:f67a6c6013ca 2550 int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 2551 {
wolfSSL 13:f67a6c6013ca 2552 int err;
wolfSSL 13:f67a6c6013ca 2553 fp_int t;
wolfSSL 13:f67a6c6013ca 2554
wolfSSL 13:f67a6c6013ca 2555 fp_init(&t);
wolfSSL 13:f67a6c6013ca 2556 fp_sqr(a, &t);
wolfSSL 13:f67a6c6013ca 2557
wolfSSL 13:f67a6c6013ca 2558 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 2559 if (c->size < FP_SIZE) {
wolfSSL 13:f67a6c6013ca 2560 err = fp_mod(&t, b, &t);
wolfSSL 13:f67a6c6013ca 2561 fp_copy(&t, c);
wolfSSL 13:f67a6c6013ca 2562 }
wolfSSL 13:f67a6c6013ca 2563 else
wolfSSL 13:f67a6c6013ca 2564 #endif
wolfSSL 13:f67a6c6013ca 2565 {
wolfSSL 13:f67a6c6013ca 2566 err = fp_mod(&t, b, c);
wolfSSL 13:f67a6c6013ca 2567 }
wolfSSL 13:f67a6c6013ca 2568
wolfSSL 13:f67a6c6013ca 2569 return err;
wolfSSL 13:f67a6c6013ca 2570 }
wolfSSL 13:f67a6c6013ca 2571
wolfSSL 13:f67a6c6013ca 2572 /* fast math conversion */
wolfSSL 13:f67a6c6013ca 2573 int mp_sqrmod(mp_int *a, mp_int *b, mp_int *c)
wolfSSL 13:f67a6c6013ca 2574 {
wolfSSL 13:f67a6c6013ca 2575 return fp_sqrmod(a, b, c);
wolfSSL 13:f67a6c6013ca 2576 }
wolfSSL 13:f67a6c6013ca 2577
wolfSSL 13:f67a6c6013ca 2578 /* fast math conversion */
wolfSSL 13:f67a6c6013ca 2579 int mp_montgomery_calc_normalization(mp_int *a, mp_int *b)
wolfSSL 13:f67a6c6013ca 2580 {
wolfSSL 13:f67a6c6013ca 2581 fp_montgomery_calc_normalization(a, b);
wolfSSL 13:f67a6c6013ca 2582 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2583 }
wolfSSL 13:f67a6c6013ca 2584
wolfSSL 13:f67a6c6013ca 2585 #endif /* WOLFSSL_KEYGEN || HAVE_ECC */
wolfSSL 13:f67a6c6013ca 2586
wolfSSL 13:f67a6c6013ca 2587
wolfSSL 13:f67a6c6013ca 2588 #if defined(WOLFSSL_KEY_GEN) || defined(HAVE_COMP_KEY) || \
wolfSSL 13:f67a6c6013ca 2589 defined(WOLFSSL_DEBUG_MATH)
wolfSSL 13:f67a6c6013ca 2590
wolfSSL 13:f67a6c6013ca 2591 #ifdef WOLFSSL_KEY_GEN
wolfSSL 13:f67a6c6013ca 2592 /* swap the elements of two integers, for cases where you can't simply swap the
wolfSSL 13:f67a6c6013ca 2593 * mp_int pointers around
wolfSSL 13:f67a6c6013ca 2594 */
wolfSSL 13:f67a6c6013ca 2595 static void fp_exch (fp_int * a, fp_int * b)
wolfSSL 13:f67a6c6013ca 2596 {
wolfSSL 13:f67a6c6013ca 2597 fp_int t;
wolfSSL 13:f67a6c6013ca 2598
wolfSSL 13:f67a6c6013ca 2599 t = *a;
wolfSSL 13:f67a6c6013ca 2600 *a = *b;
wolfSSL 13:f67a6c6013ca 2601 *b = t;
wolfSSL 13:f67a6c6013ca 2602 }
wolfSSL 13:f67a6c6013ca 2603 #endif
wolfSSL 13:f67a6c6013ca 2604
wolfSSL 13:f67a6c6013ca 2605 static const int lnz[16] = {
wolfSSL 13:f67a6c6013ca 2606 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
wolfSSL 13:f67a6c6013ca 2607 };
wolfSSL 13:f67a6c6013ca 2608
wolfSSL 13:f67a6c6013ca 2609 /* Counts the number of lsbs which are zero before the first zero bit */
wolfSSL 13:f67a6c6013ca 2610 int fp_cnt_lsb(fp_int *a)
wolfSSL 13:f67a6c6013ca 2611 {
wolfSSL 13:f67a6c6013ca 2612 int x;
wolfSSL 13:f67a6c6013ca 2613 fp_digit q, qq;
wolfSSL 13:f67a6c6013ca 2614
wolfSSL 13:f67a6c6013ca 2615 /* easy out */
wolfSSL 13:f67a6c6013ca 2616 if (fp_iszero(a) == FP_YES) {
wolfSSL 13:f67a6c6013ca 2617 return 0;
wolfSSL 13:f67a6c6013ca 2618 }
wolfSSL 13:f67a6c6013ca 2619
wolfSSL 13:f67a6c6013ca 2620 /* scan lower digits until non-zero */
wolfSSL 13:f67a6c6013ca 2621 for (x = 0; x < a->used && a->dp[x] == 0; x++) {}
wolfSSL 13:f67a6c6013ca 2622 q = a->dp[x];
wolfSSL 13:f67a6c6013ca 2623 x *= DIGIT_BIT;
wolfSSL 13:f67a6c6013ca 2624
wolfSSL 13:f67a6c6013ca 2625 /* now scan this digit until a 1 is found */
wolfSSL 13:f67a6c6013ca 2626 if ((q & 1) == 0) {
wolfSSL 13:f67a6c6013ca 2627 do {
wolfSSL 13:f67a6c6013ca 2628 qq = q & 15;
wolfSSL 13:f67a6c6013ca 2629 x += lnz[qq];
wolfSSL 13:f67a6c6013ca 2630 q >>= 4;
wolfSSL 13:f67a6c6013ca 2631 } while (qq == 0);
wolfSSL 13:f67a6c6013ca 2632 }
wolfSSL 13:f67a6c6013ca 2633 return x;
wolfSSL 13:f67a6c6013ca 2634 }
wolfSSL 13:f67a6c6013ca 2635
wolfSSL 13:f67a6c6013ca 2636
wolfSSL 13:f67a6c6013ca 2637 static int s_is_power_of_two(fp_digit b, int *p)
wolfSSL 13:f67a6c6013ca 2638 {
wolfSSL 13:f67a6c6013ca 2639 int x;
wolfSSL 13:f67a6c6013ca 2640
wolfSSL 13:f67a6c6013ca 2641 /* fast return if no power of two */
wolfSSL 13:f67a6c6013ca 2642 if ((b==0) || (b & (b-1))) {
wolfSSL 13:f67a6c6013ca 2643 return FP_NO;
wolfSSL 13:f67a6c6013ca 2644 }
wolfSSL 13:f67a6c6013ca 2645
wolfSSL 13:f67a6c6013ca 2646 for (x = 0; x < DIGIT_BIT; x++) {
wolfSSL 13:f67a6c6013ca 2647 if (b == (((fp_digit)1)<<x)) {
wolfSSL 13:f67a6c6013ca 2648 *p = x;
wolfSSL 13:f67a6c6013ca 2649 return FP_YES;
wolfSSL 13:f67a6c6013ca 2650 }
wolfSSL 13:f67a6c6013ca 2651 }
wolfSSL 13:f67a6c6013ca 2652 return FP_NO;
wolfSSL 13:f67a6c6013ca 2653 }
wolfSSL 13:f67a6c6013ca 2654
wolfSSL 13:f67a6c6013ca 2655 /* a/b => cb + d == a */
wolfSSL 13:f67a6c6013ca 2656 static int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d)
wolfSSL 13:f67a6c6013ca 2657 {
wolfSSL 13:f67a6c6013ca 2658 fp_int q;
wolfSSL 13:f67a6c6013ca 2659 fp_word w;
wolfSSL 13:f67a6c6013ca 2660 fp_digit t;
wolfSSL 13:f67a6c6013ca 2661 int ix;
wolfSSL 13:f67a6c6013ca 2662
wolfSSL 13:f67a6c6013ca 2663 /* cannot divide by zero */
wolfSSL 13:f67a6c6013ca 2664 if (b == 0) {
wolfSSL 13:f67a6c6013ca 2665 return FP_VAL;
wolfSSL 13:f67a6c6013ca 2666 }
wolfSSL 13:f67a6c6013ca 2667
wolfSSL 13:f67a6c6013ca 2668 /* quick outs */
wolfSSL 13:f67a6c6013ca 2669 if (b == 1 || fp_iszero(a) == FP_YES) {
wolfSSL 13:f67a6c6013ca 2670 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 2671 *d = 0;
wolfSSL 13:f67a6c6013ca 2672 }
wolfSSL 13:f67a6c6013ca 2673 if (c != NULL) {
wolfSSL 13:f67a6c6013ca 2674 fp_copy(a, c);
wolfSSL 13:f67a6c6013ca 2675 }
wolfSSL 13:f67a6c6013ca 2676 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 2677 }
wolfSSL 13:f67a6c6013ca 2678
wolfSSL 13:f67a6c6013ca 2679 /* power of two ? */
wolfSSL 13:f67a6c6013ca 2680 if (s_is_power_of_two(b, &ix) == FP_YES) {
wolfSSL 13:f67a6c6013ca 2681 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 2682 *d = a->dp[0] & ((((fp_digit)1)<<ix) - 1);
wolfSSL 13:f67a6c6013ca 2683 }
wolfSSL 13:f67a6c6013ca 2684 if (c != NULL) {
wolfSSL 13:f67a6c6013ca 2685 fp_div_2d(a, ix, c, NULL);
wolfSSL 13:f67a6c6013ca 2686 }
wolfSSL 13:f67a6c6013ca 2687 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 2688 }
wolfSSL 13:f67a6c6013ca 2689
wolfSSL 13:f67a6c6013ca 2690 if (c != NULL) {
wolfSSL 13:f67a6c6013ca 2691 /* no easy answer [c'est la vie]. Just division */
wolfSSL 13:f67a6c6013ca 2692 fp_init(&q);
wolfSSL 13:f67a6c6013ca 2693
wolfSSL 13:f67a6c6013ca 2694 q.used = a->used;
wolfSSL 13:f67a6c6013ca 2695 q.sign = a->sign;
wolfSSL 13:f67a6c6013ca 2696 }
wolfSSL 13:f67a6c6013ca 2697
wolfSSL 13:f67a6c6013ca 2698 w = 0;
wolfSSL 13:f67a6c6013ca 2699 for (ix = a->used - 1; ix >= 0; ix--) {
wolfSSL 13:f67a6c6013ca 2700 w = (w << ((fp_word)DIGIT_BIT)) | ((fp_word)a->dp[ix]);
wolfSSL 13:f67a6c6013ca 2701
wolfSSL 13:f67a6c6013ca 2702 if (w >= b) {
wolfSSL 13:f67a6c6013ca 2703 t = (fp_digit)(w / b);
wolfSSL 13:f67a6c6013ca 2704 w -= ((fp_word)t) * ((fp_word)b);
wolfSSL 13:f67a6c6013ca 2705 } else {
wolfSSL 13:f67a6c6013ca 2706 t = 0;
wolfSSL 13:f67a6c6013ca 2707 }
wolfSSL 13:f67a6c6013ca 2708 if (c != NULL)
wolfSSL 13:f67a6c6013ca 2709 q.dp[ix] = (fp_digit)t;
wolfSSL 13:f67a6c6013ca 2710 }
wolfSSL 13:f67a6c6013ca 2711
wolfSSL 13:f67a6c6013ca 2712 if (d != NULL) {
wolfSSL 13:f67a6c6013ca 2713 *d = (fp_digit)w;
wolfSSL 13:f67a6c6013ca 2714 }
wolfSSL 13:f67a6c6013ca 2715
wolfSSL 13:f67a6c6013ca 2716 if (c != NULL) {
wolfSSL 13:f67a6c6013ca 2717 fp_clamp(&q);
wolfSSL 13:f67a6c6013ca 2718 fp_copy(&q, c);
wolfSSL 13:f67a6c6013ca 2719 }
wolfSSL 13:f67a6c6013ca 2720
wolfSSL 13:f67a6c6013ca 2721 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 2722 }
wolfSSL 13:f67a6c6013ca 2723
wolfSSL 13:f67a6c6013ca 2724
wolfSSL 13:f67a6c6013ca 2725 /* c = a mod b, 0 <= c < b */
wolfSSL 13:f67a6c6013ca 2726 static int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c)
wolfSSL 13:f67a6c6013ca 2727 {
wolfSSL 13:f67a6c6013ca 2728 return fp_div_d(a, b, NULL, c);
wolfSSL 13:f67a6c6013ca 2729 }
wolfSSL 13:f67a6c6013ca 2730
wolfSSL 13:f67a6c6013ca 2731 int mp_mod_d(fp_int *a, fp_digit b, fp_digit *c)
wolfSSL 13:f67a6c6013ca 2732 {
wolfSSL 13:f67a6c6013ca 2733 return fp_mod_d(a, b, c);
wolfSSL 13:f67a6c6013ca 2734 }
wolfSSL 13:f67a6c6013ca 2735
wolfSSL 13:f67a6c6013ca 2736 #endif /* defined(WOLFSSL_KEY_GEN) || defined(HAVE_COMP_KEY) || defined(WOLFSSL_DEBUG_MATH) */
wolfSSL 13:f67a6c6013ca 2737
wolfSSL 13:f67a6c6013ca 2738 #ifdef WOLFSSL_KEY_GEN
wolfSSL 13:f67a6c6013ca 2739
wolfSSL 13:f67a6c6013ca 2740 static void fp_gcd(fp_int *a, fp_int *b, fp_int *c);
wolfSSL 13:f67a6c6013ca 2741 static void fp_lcm(fp_int *a, fp_int *b, fp_int *c);
wolfSSL 13:f67a6c6013ca 2742 static int fp_isprime_ex(fp_int *a, int t);
wolfSSL 13:f67a6c6013ca 2743 static int fp_isprime(fp_int *a);
wolfSSL 13:f67a6c6013ca 2744 static int fp_randprime(fp_int* N, int len, WC_RNG* rng, void* heap);
wolfSSL 13:f67a6c6013ca 2745
wolfSSL 13:f67a6c6013ca 2746 int mp_gcd(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 2747 {
wolfSSL 13:f67a6c6013ca 2748 fp_gcd(a, b, c);
wolfSSL 13:f67a6c6013ca 2749 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2750 }
wolfSSL 13:f67a6c6013ca 2751
wolfSSL 13:f67a6c6013ca 2752
wolfSSL 13:f67a6c6013ca 2753 int mp_lcm(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 2754 {
wolfSSL 13:f67a6c6013ca 2755 fp_lcm(a, b, c);
wolfSSL 13:f67a6c6013ca 2756 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2757 }
wolfSSL 13:f67a6c6013ca 2758
wolfSSL 13:f67a6c6013ca 2759
wolfSSL 13:f67a6c6013ca 2760 int mp_prime_is_prime(mp_int* a, int t, int* result)
wolfSSL 13:f67a6c6013ca 2761 {
wolfSSL 13:f67a6c6013ca 2762 (void)t;
wolfSSL 13:f67a6c6013ca 2763 *result = fp_isprime(a);
wolfSSL 13:f67a6c6013ca 2764 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2765 }
wolfSSL 13:f67a6c6013ca 2766
wolfSSL 13:f67a6c6013ca 2767 int mp_rand_prime(mp_int* N, int len, WC_RNG* rng, void* heap)
wolfSSL 13:f67a6c6013ca 2768 {
wolfSSL 13:f67a6c6013ca 2769 int err;
wolfSSL 13:f67a6c6013ca 2770
wolfSSL 13:f67a6c6013ca 2771 err = fp_randprime(N, len, rng, heap);
wolfSSL 13:f67a6c6013ca 2772 switch(err) {
wolfSSL 13:f67a6c6013ca 2773 case FP_VAL:
wolfSSL 13:f67a6c6013ca 2774 return MP_VAL;
wolfSSL 13:f67a6c6013ca 2775 case FP_MEM:
wolfSSL 13:f67a6c6013ca 2776 return MP_MEM;
wolfSSL 13:f67a6c6013ca 2777 default:
wolfSSL 13:f67a6c6013ca 2778 break;
wolfSSL 13:f67a6c6013ca 2779 }
wolfSSL 13:f67a6c6013ca 2780
wolfSSL 13:f67a6c6013ca 2781 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2782 }
wolfSSL 13:f67a6c6013ca 2783
wolfSSL 13:f67a6c6013ca 2784 int mp_exch (mp_int * a, mp_int * b)
wolfSSL 13:f67a6c6013ca 2785 {
wolfSSL 13:f67a6c6013ca 2786 fp_exch(a, b);
wolfSSL 13:f67a6c6013ca 2787 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 2788 }
wolfSSL 13:f67a6c6013ca 2789
wolfSSL 13:f67a6c6013ca 2790 /* Miller-Rabin test of "a" to the base of "b" as described in
wolfSSL 13:f67a6c6013ca 2791 * HAC pp. 139 Algorithm 4.24
wolfSSL 13:f67a6c6013ca 2792 *
wolfSSL 13:f67a6c6013ca 2793 * Sets result to 0 if definitely composite or 1 if probably prime.
wolfSSL 13:f67a6c6013ca 2794 * Randomly the chance of error is no more than 1/4 and often
wolfSSL 13:f67a6c6013ca 2795 * very much lower.
wolfSSL 13:f67a6c6013ca 2796 */
wolfSSL 13:f67a6c6013ca 2797 static void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result)
wolfSSL 13:f67a6c6013ca 2798 {
wolfSSL 13:f67a6c6013ca 2799 fp_int n1, y, r;
wolfSSL 13:f67a6c6013ca 2800 int s, j;
wolfSSL 13:f67a6c6013ca 2801
wolfSSL 13:f67a6c6013ca 2802 /* default */
wolfSSL 13:f67a6c6013ca 2803 *result = FP_NO;
wolfSSL 13:f67a6c6013ca 2804
wolfSSL 13:f67a6c6013ca 2805 /* ensure b > 1 */
wolfSSL 13:f67a6c6013ca 2806 if (fp_cmp_d(b, 1) != FP_GT) {
wolfSSL 13:f67a6c6013ca 2807 return;
wolfSSL 13:f67a6c6013ca 2808 }
wolfSSL 13:f67a6c6013ca 2809
wolfSSL 13:f67a6c6013ca 2810 /* get n1 = a - 1 */
wolfSSL 13:f67a6c6013ca 2811 fp_init_copy(&n1, a);
wolfSSL 13:f67a6c6013ca 2812 fp_sub_d(&n1, 1, &n1);
wolfSSL 13:f67a6c6013ca 2813
wolfSSL 13:f67a6c6013ca 2814 /* set 2**s * r = n1 */
wolfSSL 13:f67a6c6013ca 2815 fp_init_copy(&r, &n1);
wolfSSL 13:f67a6c6013ca 2816
wolfSSL 13:f67a6c6013ca 2817 /* count the number of least significant bits
wolfSSL 13:f67a6c6013ca 2818 * which are zero
wolfSSL 13:f67a6c6013ca 2819 */
wolfSSL 13:f67a6c6013ca 2820 s = fp_cnt_lsb(&r);
wolfSSL 13:f67a6c6013ca 2821
wolfSSL 13:f67a6c6013ca 2822 /* now divide n - 1 by 2**s */
wolfSSL 13:f67a6c6013ca 2823 fp_div_2d (&r, s, &r, NULL);
wolfSSL 13:f67a6c6013ca 2824
wolfSSL 13:f67a6c6013ca 2825 /* compute y = b**r mod a */
wolfSSL 13:f67a6c6013ca 2826 fp_init(&y);
wolfSSL 13:f67a6c6013ca 2827 fp_exptmod(b, &r, a, &y);
wolfSSL 13:f67a6c6013ca 2828
wolfSSL 13:f67a6c6013ca 2829 /* if y != 1 and y != n1 do */
wolfSSL 13:f67a6c6013ca 2830 if (fp_cmp_d (&y, 1) != FP_EQ && fp_cmp (&y, &n1) != FP_EQ) {
wolfSSL 13:f67a6c6013ca 2831 j = 1;
wolfSSL 13:f67a6c6013ca 2832 /* while j <= s-1 and y != n1 */
wolfSSL 13:f67a6c6013ca 2833 while ((j <= (s - 1)) && fp_cmp (&y, &n1) != FP_EQ) {
wolfSSL 13:f67a6c6013ca 2834 fp_sqrmod (&y, a, &y);
wolfSSL 13:f67a6c6013ca 2835
wolfSSL 13:f67a6c6013ca 2836 /* if y == 1 then composite */
wolfSSL 13:f67a6c6013ca 2837 if (fp_cmp_d (&y, 1) == FP_EQ) {
wolfSSL 13:f67a6c6013ca 2838 return;
wolfSSL 13:f67a6c6013ca 2839 }
wolfSSL 13:f67a6c6013ca 2840 ++j;
wolfSSL 13:f67a6c6013ca 2841 }
wolfSSL 13:f67a6c6013ca 2842
wolfSSL 13:f67a6c6013ca 2843 /* if y != n1 then composite */
wolfSSL 13:f67a6c6013ca 2844 if (fp_cmp (&y, &n1) != FP_EQ) {
wolfSSL 13:f67a6c6013ca 2845 return;
wolfSSL 13:f67a6c6013ca 2846 }
wolfSSL 13:f67a6c6013ca 2847 }
wolfSSL 13:f67a6c6013ca 2848
wolfSSL 13:f67a6c6013ca 2849 /* probably prime now */
wolfSSL 13:f67a6c6013ca 2850 *result = FP_YES;
wolfSSL 13:f67a6c6013ca 2851 }
wolfSSL 13:f67a6c6013ca 2852
wolfSSL 13:f67a6c6013ca 2853
wolfSSL 13:f67a6c6013ca 2854 /* a few primes */
wolfSSL 13:f67a6c6013ca 2855 static const fp_digit primes[FP_PRIME_SIZE] = {
wolfSSL 13:f67a6c6013ca 2856 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
wolfSSL 13:f67a6c6013ca 2857 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
wolfSSL 13:f67a6c6013ca 2858 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
wolfSSL 13:f67a6c6013ca 2859 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
wolfSSL 13:f67a6c6013ca 2860 0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
wolfSSL 13:f67a6c6013ca 2861 0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
wolfSSL 13:f67a6c6013ca 2862 0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
wolfSSL 13:f67a6c6013ca 2863 0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
wolfSSL 13:f67a6c6013ca 2864
wolfSSL 13:f67a6c6013ca 2865 0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
wolfSSL 13:f67a6c6013ca 2866 0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
wolfSSL 13:f67a6c6013ca 2867 0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
wolfSSL 13:f67a6c6013ca 2868 0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
wolfSSL 13:f67a6c6013ca 2869 0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
wolfSSL 13:f67a6c6013ca 2870 0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
wolfSSL 13:f67a6c6013ca 2871 0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
wolfSSL 13:f67a6c6013ca 2872 0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
wolfSSL 13:f67a6c6013ca 2873
wolfSSL 13:f67a6c6013ca 2874 0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
wolfSSL 13:f67a6c6013ca 2875 0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
wolfSSL 13:f67a6c6013ca 2876 0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
wolfSSL 13:f67a6c6013ca 2877 0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
wolfSSL 13:f67a6c6013ca 2878 0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
wolfSSL 13:f67a6c6013ca 2879 0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
wolfSSL 13:f67a6c6013ca 2880 0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
wolfSSL 13:f67a6c6013ca 2881 0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
wolfSSL 13:f67a6c6013ca 2882
wolfSSL 13:f67a6c6013ca 2883 0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
wolfSSL 13:f67a6c6013ca 2884 0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
wolfSSL 13:f67a6c6013ca 2885 0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
wolfSSL 13:f67a6c6013ca 2886 0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
wolfSSL 13:f67a6c6013ca 2887 0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
wolfSSL 13:f67a6c6013ca 2888 0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
wolfSSL 13:f67a6c6013ca 2889 0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
wolfSSL 13:f67a6c6013ca 2890 0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
wolfSSL 13:f67a6c6013ca 2891 };
wolfSSL 13:f67a6c6013ca 2892
wolfSSL 13:f67a6c6013ca 2893 int fp_isprime_ex(fp_int *a, int t)
wolfSSL 13:f67a6c6013ca 2894 {
wolfSSL 13:f67a6c6013ca 2895 fp_int b;
wolfSSL 13:f67a6c6013ca 2896 fp_digit d;
wolfSSL 13:f67a6c6013ca 2897 int r, res;
wolfSSL 13:f67a6c6013ca 2898
wolfSSL 13:f67a6c6013ca 2899 if (t <= 0 || t > FP_PRIME_SIZE) {
wolfSSL 13:f67a6c6013ca 2900 return FP_NO;
wolfSSL 13:f67a6c6013ca 2901 }
wolfSSL 13:f67a6c6013ca 2902
wolfSSL 13:f67a6c6013ca 2903 /* do trial division */
wolfSSL 13:f67a6c6013ca 2904 for (r = 0; r < FP_PRIME_SIZE; r++) {
wolfSSL 13:f67a6c6013ca 2905 fp_mod_d(a, primes[r], &d);
wolfSSL 13:f67a6c6013ca 2906 if (d == 0) {
wolfSSL 13:f67a6c6013ca 2907 return FP_NO;
wolfSSL 13:f67a6c6013ca 2908 }
wolfSSL 13:f67a6c6013ca 2909 }
wolfSSL 13:f67a6c6013ca 2910
wolfSSL 13:f67a6c6013ca 2911 /* now do 't' miller rabins */
wolfSSL 13:f67a6c6013ca 2912 fp_init(&b);
wolfSSL 13:f67a6c6013ca 2913 for (r = 0; r < t; r++) {
wolfSSL 13:f67a6c6013ca 2914 fp_set(&b, primes[r]);
wolfSSL 13:f67a6c6013ca 2915 fp_prime_miller_rabin(a, &b, &res);
wolfSSL 13:f67a6c6013ca 2916 if (res == FP_NO) {
wolfSSL 13:f67a6c6013ca 2917 return FP_NO;
wolfSSL 13:f67a6c6013ca 2918 }
wolfSSL 13:f67a6c6013ca 2919 }
wolfSSL 13:f67a6c6013ca 2920 return FP_YES;
wolfSSL 13:f67a6c6013ca 2921 }
wolfSSL 13:f67a6c6013ca 2922
wolfSSL 13:f67a6c6013ca 2923 int fp_isprime(fp_int *a)
wolfSSL 13:f67a6c6013ca 2924 {
wolfSSL 13:f67a6c6013ca 2925 return fp_isprime_ex(a, 8);
wolfSSL 13:f67a6c6013ca 2926 }
wolfSSL 13:f67a6c6013ca 2927
wolfSSL 13:f67a6c6013ca 2928 int fp_randprime(fp_int* N, int len, WC_RNG* rng, void* heap)
wolfSSL 13:f67a6c6013ca 2929 {
wolfSSL 13:f67a6c6013ca 2930 static const int USE_BBS = 1;
wolfSSL 13:f67a6c6013ca 2931 int err, type;
wolfSSL 13:f67a6c6013ca 2932 byte* buf;
wolfSSL 13:f67a6c6013ca 2933
wolfSSL 13:f67a6c6013ca 2934 /* get type */
wolfSSL 13:f67a6c6013ca 2935 if (len < 0) {
wolfSSL 13:f67a6c6013ca 2936 type = USE_BBS;
wolfSSL 13:f67a6c6013ca 2937 len = -len;
wolfSSL 13:f67a6c6013ca 2938 } else {
wolfSSL 13:f67a6c6013ca 2939 type = 0;
wolfSSL 13:f67a6c6013ca 2940 }
wolfSSL 13:f67a6c6013ca 2941
wolfSSL 13:f67a6c6013ca 2942 /* allow sizes between 2 and 512 bytes for a prime size */
wolfSSL 13:f67a6c6013ca 2943 if (len < 2 || len > 512) {
wolfSSL 13:f67a6c6013ca 2944 return FP_VAL;
wolfSSL 13:f67a6c6013ca 2945 }
wolfSSL 13:f67a6c6013ca 2946
wolfSSL 13:f67a6c6013ca 2947 /* allocate buffer to work with */
wolfSSL 13:f67a6c6013ca 2948 buf = (byte*)XMALLOC(len, heap, DYNAMIC_TYPE_TMP_BUFFER);
wolfSSL 13:f67a6c6013ca 2949 if (buf == NULL) {
wolfSSL 13:f67a6c6013ca 2950 return FP_MEM;
wolfSSL 13:f67a6c6013ca 2951 }
wolfSSL 13:f67a6c6013ca 2952 XMEMSET(buf, 0, len);
wolfSSL 13:f67a6c6013ca 2953
wolfSSL 13:f67a6c6013ca 2954 do {
wolfSSL 13:f67a6c6013ca 2955 #ifdef SHOW_GEN
wolfSSL 13:f67a6c6013ca 2956 printf(".");
wolfSSL 13:f67a6c6013ca 2957 fflush(stdout);
wolfSSL 13:f67a6c6013ca 2958 #endif
wolfSSL 13:f67a6c6013ca 2959 /* generate value */
wolfSSL 13:f67a6c6013ca 2960 err = wc_RNG_GenerateBlock(rng, buf, len);
wolfSSL 13:f67a6c6013ca 2961 if (err != 0) {
wolfSSL 13:f67a6c6013ca 2962 XFREE(buf, heap, DYNAMIC_TYPE_TMP_BUFFER);
wolfSSL 13:f67a6c6013ca 2963 return FP_VAL;
wolfSSL 13:f67a6c6013ca 2964 }
wolfSSL 13:f67a6c6013ca 2965
wolfSSL 13:f67a6c6013ca 2966 /* munge bits */
wolfSSL 13:f67a6c6013ca 2967 buf[0] |= 0x80 | 0x40;
wolfSSL 13:f67a6c6013ca 2968 buf[len-1] |= 0x01 | ((type & USE_BBS) ? 0x02 : 0x00);
wolfSSL 13:f67a6c6013ca 2969
wolfSSL 13:f67a6c6013ca 2970 /* load value */
wolfSSL 13:f67a6c6013ca 2971 fp_read_unsigned_bin(N, buf, len);
wolfSSL 13:f67a6c6013ca 2972
wolfSSL 13:f67a6c6013ca 2973 /* test */
wolfSSL 13:f67a6c6013ca 2974 } while (fp_isprime(N) == FP_NO);
wolfSSL 13:f67a6c6013ca 2975
wolfSSL 13:f67a6c6013ca 2976 XMEMSET(buf, 0, len);
wolfSSL 13:f67a6c6013ca 2977 XFREE(buf, heap, DYNAMIC_TYPE_TMP_BUFFER);
wolfSSL 13:f67a6c6013ca 2978
wolfSSL 13:f67a6c6013ca 2979 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 2980 }
wolfSSL 13:f67a6c6013ca 2981
wolfSSL 13:f67a6c6013ca 2982 /* c = [a, b] */
wolfSSL 13:f67a6c6013ca 2983 void fp_lcm(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 2984 {
wolfSSL 13:f67a6c6013ca 2985 fp_int t1, t2;
wolfSSL 13:f67a6c6013ca 2986
wolfSSL 13:f67a6c6013ca 2987 fp_init(&t1);
wolfSSL 13:f67a6c6013ca 2988 fp_init(&t2);
wolfSSL 13:f67a6c6013ca 2989 fp_gcd(a, b, &t1);
wolfSSL 13:f67a6c6013ca 2990 if (fp_cmp_mag(a, b) == FP_GT) {
wolfSSL 13:f67a6c6013ca 2991 fp_div(a, &t1, &t2, NULL);
wolfSSL 13:f67a6c6013ca 2992 fp_mul(b, &t2, c);
wolfSSL 13:f67a6c6013ca 2993 } else {
wolfSSL 13:f67a6c6013ca 2994 fp_div(b, &t1, &t2, NULL);
wolfSSL 13:f67a6c6013ca 2995 fp_mul(a, &t2, c);
wolfSSL 13:f67a6c6013ca 2996 }
wolfSSL 13:f67a6c6013ca 2997 }
wolfSSL 13:f67a6c6013ca 2998
wolfSSL 13:f67a6c6013ca 2999
wolfSSL 13:f67a6c6013ca 3000
wolfSSL 13:f67a6c6013ca 3001 /* c = (a, b) */
wolfSSL 13:f67a6c6013ca 3002 void fp_gcd(fp_int *a, fp_int *b, fp_int *c)
wolfSSL 13:f67a6c6013ca 3003 {
wolfSSL 13:f67a6c6013ca 3004 fp_int u, v, r;
wolfSSL 13:f67a6c6013ca 3005
wolfSSL 13:f67a6c6013ca 3006 /* either zero than gcd is the largest */
wolfSSL 13:f67a6c6013ca 3007 if (fp_iszero (a) == FP_YES && fp_iszero (b) == FP_NO) {
wolfSSL 13:f67a6c6013ca 3008 fp_abs (b, c);
wolfSSL 13:f67a6c6013ca 3009 return;
wolfSSL 13:f67a6c6013ca 3010 }
wolfSSL 13:f67a6c6013ca 3011 if (fp_iszero (a) == FP_NO && fp_iszero (b) == FP_YES) {
wolfSSL 13:f67a6c6013ca 3012 fp_abs (a, c);
wolfSSL 13:f67a6c6013ca 3013 return;
wolfSSL 13:f67a6c6013ca 3014 }
wolfSSL 13:f67a6c6013ca 3015
wolfSSL 13:f67a6c6013ca 3016 /* optimized. At this point if a == 0 then
wolfSSL 13:f67a6c6013ca 3017 * b must equal zero too
wolfSSL 13:f67a6c6013ca 3018 */
wolfSSL 13:f67a6c6013ca 3019 if (fp_iszero (a) == FP_YES) {
wolfSSL 13:f67a6c6013ca 3020 fp_zero(c);
wolfSSL 13:f67a6c6013ca 3021 return;
wolfSSL 13:f67a6c6013ca 3022 }
wolfSSL 13:f67a6c6013ca 3023
wolfSSL 13:f67a6c6013ca 3024 /* sort inputs */
wolfSSL 13:f67a6c6013ca 3025 if (fp_cmp_mag(a, b) != FP_LT) {
wolfSSL 13:f67a6c6013ca 3026 fp_init_copy(&u, a);
wolfSSL 13:f67a6c6013ca 3027 fp_init_copy(&v, b);
wolfSSL 13:f67a6c6013ca 3028 } else {
wolfSSL 13:f67a6c6013ca 3029 fp_init_copy(&u, b);
wolfSSL 13:f67a6c6013ca 3030 fp_init_copy(&v, a);
wolfSSL 13:f67a6c6013ca 3031 }
wolfSSL 13:f67a6c6013ca 3032
wolfSSL 13:f67a6c6013ca 3033 fp_init(&r);
wolfSSL 13:f67a6c6013ca 3034 while (fp_iszero(&v) == FP_NO) {
wolfSSL 13:f67a6c6013ca 3035 fp_mod(&u, &v, &r);
wolfSSL 13:f67a6c6013ca 3036 fp_copy(&v, &u);
wolfSSL 13:f67a6c6013ca 3037 fp_copy(&r, &v);
wolfSSL 13:f67a6c6013ca 3038 }
wolfSSL 13:f67a6c6013ca 3039 fp_copy(&u, c);
wolfSSL 13:f67a6c6013ca 3040 }
wolfSSL 13:f67a6c6013ca 3041
wolfSSL 13:f67a6c6013ca 3042 #endif /* WOLFSSL_KEY_GEN */
wolfSSL 13:f67a6c6013ca 3043
wolfSSL 13:f67a6c6013ca 3044
wolfSSL 13:f67a6c6013ca 3045 #if defined(HAVE_ECC) || !defined(NO_PWDBASED) || defined(OPENSSL_EXTRA) || \
wolfSSL 13:f67a6c6013ca 3046 defined(WC_RSA_BLINDING)
wolfSSL 13:f67a6c6013ca 3047 /* c = a + b */
wolfSSL 13:f67a6c6013ca 3048 void fp_add_d(fp_int *a, fp_digit b, fp_int *c)
wolfSSL 13:f67a6c6013ca 3049 {
wolfSSL 13:f67a6c6013ca 3050 fp_int tmp;
wolfSSL 13:f67a6c6013ca 3051 fp_init(&tmp);
wolfSSL 13:f67a6c6013ca 3052 fp_set(&tmp, b);
wolfSSL 13:f67a6c6013ca 3053 fp_add(a, &tmp, c);
wolfSSL 13:f67a6c6013ca 3054 }
wolfSSL 13:f67a6c6013ca 3055
wolfSSL 13:f67a6c6013ca 3056 /* external compatibility */
wolfSSL 13:f67a6c6013ca 3057 int mp_add_d(fp_int *a, fp_digit b, fp_int *c)
wolfSSL 13:f67a6c6013ca 3058 {
wolfSSL 13:f67a6c6013ca 3059 fp_add_d(a, b, c);
wolfSSL 13:f67a6c6013ca 3060 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 3061 }
wolfSSL 13:f67a6c6013ca 3062
wolfSSL 13:f67a6c6013ca 3063 #endif /* HAVE_ECC || !NO_PWDBASED */
wolfSSL 13:f67a6c6013ca 3064
wolfSSL 13:f67a6c6013ca 3065
wolfSSL 13:f67a6c6013ca 3066 #if defined(HAVE_ECC) || defined(WOLFSSL_KEY_GEN) || defined(HAVE_COMP_KEY)
wolfSSL 13:f67a6c6013ca 3067
wolfSSL 13:f67a6c6013ca 3068 /* chars used in radix conversions */
wolfSSL 13:f67a6c6013ca 3069 static const char *fp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\
wolfSSL 13:f67a6c6013ca 3070 abcdefghijklmnopqrstuvwxyz+/";
wolfSSL 13:f67a6c6013ca 3071 #endif
wolfSSL 13:f67a6c6013ca 3072
wolfSSL 13:f67a6c6013ca 3073 #ifdef HAVE_ECC
wolfSSL 13:f67a6c6013ca 3074 static int fp_read_radix(fp_int *a, const char *str, int radix)
wolfSSL 13:f67a6c6013ca 3075 {
wolfSSL 13:f67a6c6013ca 3076 int y, neg;
wolfSSL 13:f67a6c6013ca 3077 char ch;
wolfSSL 13:f67a6c6013ca 3078
wolfSSL 13:f67a6c6013ca 3079 /* set the integer to the default of zero */
wolfSSL 13:f67a6c6013ca 3080 fp_zero (a);
wolfSSL 13:f67a6c6013ca 3081
wolfSSL 13:f67a6c6013ca 3082 /* make sure the radix is ok */
wolfSSL 13:f67a6c6013ca 3083 if (radix < 2 || radix > 64) {
wolfSSL 13:f67a6c6013ca 3084 return FP_VAL;
wolfSSL 13:f67a6c6013ca 3085 }
wolfSSL 13:f67a6c6013ca 3086
wolfSSL 13:f67a6c6013ca 3087 /* if the leading digit is a
wolfSSL 13:f67a6c6013ca 3088 * minus set the sign to negative.
wolfSSL 13:f67a6c6013ca 3089 */
wolfSSL 13:f67a6c6013ca 3090 if (*str == '-') {
wolfSSL 13:f67a6c6013ca 3091 ++str;
wolfSSL 13:f67a6c6013ca 3092 neg = FP_NEG;
wolfSSL 13:f67a6c6013ca 3093 } else {
wolfSSL 13:f67a6c6013ca 3094 neg = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 3095 }
wolfSSL 13:f67a6c6013ca 3096
wolfSSL 13:f67a6c6013ca 3097 /* process each digit of the string */
wolfSSL 13:f67a6c6013ca 3098 while (*str) {
wolfSSL 13:f67a6c6013ca 3099 /* if the radix <= 36 the conversion is case insensitive
wolfSSL 13:f67a6c6013ca 3100 * this allows numbers like 1AB and 1ab to represent the same value
wolfSSL 13:f67a6c6013ca 3101 * [e.g. in hex]
wolfSSL 13:f67a6c6013ca 3102 */
wolfSSL 13:f67a6c6013ca 3103 ch = (char)((radix <= 36) ? XTOUPPER((unsigned char)*str) : *str);
wolfSSL 13:f67a6c6013ca 3104 for (y = 0; y < 64; y++) {
wolfSSL 13:f67a6c6013ca 3105 if (ch == fp_s_rmap[y]) {
wolfSSL 13:f67a6c6013ca 3106 break;
wolfSSL 13:f67a6c6013ca 3107 }
wolfSSL 13:f67a6c6013ca 3108 }
wolfSSL 13:f67a6c6013ca 3109
wolfSSL 13:f67a6c6013ca 3110 /* if the char was found in the map
wolfSSL 13:f67a6c6013ca 3111 * and is less than the given radix add it
wolfSSL 13:f67a6c6013ca 3112 * to the number, otherwise exit the loop.
wolfSSL 13:f67a6c6013ca 3113 */
wolfSSL 13:f67a6c6013ca 3114 if (y < radix) {
wolfSSL 13:f67a6c6013ca 3115 fp_mul_d (a, (fp_digit) radix, a);
wolfSSL 13:f67a6c6013ca 3116 fp_add_d (a, (fp_digit) y, a);
wolfSSL 13:f67a6c6013ca 3117 } else {
wolfSSL 13:f67a6c6013ca 3118 break;
wolfSSL 13:f67a6c6013ca 3119 }
wolfSSL 13:f67a6c6013ca 3120 ++str;
wolfSSL 13:f67a6c6013ca 3121 }
wolfSSL 13:f67a6c6013ca 3122
wolfSSL 13:f67a6c6013ca 3123 /* set the sign only if a != 0 */
wolfSSL 13:f67a6c6013ca 3124 if (fp_iszero(a) != FP_YES) {
wolfSSL 13:f67a6c6013ca 3125 a->sign = neg;
wolfSSL 13:f67a6c6013ca 3126 }
wolfSSL 13:f67a6c6013ca 3127 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 3128 }
wolfSSL 13:f67a6c6013ca 3129
wolfSSL 13:f67a6c6013ca 3130 /* fast math conversion */
wolfSSL 13:f67a6c6013ca 3131 int mp_read_radix(mp_int *a, const char *str, int radix)
wolfSSL 13:f67a6c6013ca 3132 {
wolfSSL 13:f67a6c6013ca 3133 return fp_read_radix(a, str, radix);
wolfSSL 13:f67a6c6013ca 3134 }
wolfSSL 13:f67a6c6013ca 3135
wolfSSL 13:f67a6c6013ca 3136 /* fast math conversion */
wolfSSL 13:f67a6c6013ca 3137 int mp_sqr(fp_int *A, fp_int *B)
wolfSSL 13:f67a6c6013ca 3138 {
wolfSSL 13:f67a6c6013ca 3139 fp_sqr(A, B);
wolfSSL 13:f67a6c6013ca 3140 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 3141 }
wolfSSL 13:f67a6c6013ca 3142
wolfSSL 13:f67a6c6013ca 3143 /* fast math conversion */
wolfSSL 13:f67a6c6013ca 3144 int mp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp)
wolfSSL 13:f67a6c6013ca 3145 {
wolfSSL 13:f67a6c6013ca 3146 fp_montgomery_reduce(a, m, mp);
wolfSSL 13:f67a6c6013ca 3147 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 3148 }
wolfSSL 13:f67a6c6013ca 3149
wolfSSL 13:f67a6c6013ca 3150
wolfSSL 13:f67a6c6013ca 3151 /* fast math conversion */
wolfSSL 13:f67a6c6013ca 3152 int mp_montgomery_setup(fp_int *a, fp_digit *rho)
wolfSSL 13:f67a6c6013ca 3153 {
wolfSSL 13:f67a6c6013ca 3154 return fp_montgomery_setup(a, rho);
wolfSSL 13:f67a6c6013ca 3155 }
wolfSSL 13:f67a6c6013ca 3156
wolfSSL 13:f67a6c6013ca 3157 int mp_div_2(fp_int * a, fp_int * b)
wolfSSL 13:f67a6c6013ca 3158 {
wolfSSL 13:f67a6c6013ca 3159 fp_div_2(a, b);
wolfSSL 13:f67a6c6013ca 3160 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 3161 }
wolfSSL 13:f67a6c6013ca 3162
wolfSSL 13:f67a6c6013ca 3163
wolfSSL 13:f67a6c6013ca 3164 int mp_init_copy(fp_int * a, fp_int * b)
wolfSSL 13:f67a6c6013ca 3165 {
wolfSSL 13:f67a6c6013ca 3166 fp_init_copy(a, b);
wolfSSL 13:f67a6c6013ca 3167 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 3168 }
wolfSSL 13:f67a6c6013ca 3169
wolfSSL 13:f67a6c6013ca 3170 #ifdef HAVE_COMP_KEY
wolfSSL 13:f67a6c6013ca 3171
wolfSSL 13:f67a6c6013ca 3172 int mp_cnt_lsb(fp_int* a)
wolfSSL 13:f67a6c6013ca 3173 {
wolfSSL 13:f67a6c6013ca 3174 return fp_cnt_lsb(a);
wolfSSL 13:f67a6c6013ca 3175 }
wolfSSL 13:f67a6c6013ca 3176
wolfSSL 13:f67a6c6013ca 3177 #endif /* HAVE_COMP_KEY */
wolfSSL 13:f67a6c6013ca 3178
wolfSSL 13:f67a6c6013ca 3179 #endif /* HAVE_ECC */
wolfSSL 13:f67a6c6013ca 3180
wolfSSL 13:f67a6c6013ca 3181 #if defined(HAVE_ECC) || !defined(NO_RSA) || !defined(NO_DSA)
wolfSSL 13:f67a6c6013ca 3182 /* fast math conversion */
wolfSSL 13:f67a6c6013ca 3183 int mp_set(fp_int *a, fp_digit b)
wolfSSL 13:f67a6c6013ca 3184 {
wolfSSL 13:f67a6c6013ca 3185 fp_set(a,b);
wolfSSL 13:f67a6c6013ca 3186 return MP_OKAY;
wolfSSL 13:f67a6c6013ca 3187 }
wolfSSL 13:f67a6c6013ca 3188 #endif
wolfSSL 13:f67a6c6013ca 3189
wolfSSL 13:f67a6c6013ca 3190 #if defined(WOLFSSL_KEY_GEN) || defined(HAVE_COMP_KEY) || \
wolfSSL 13:f67a6c6013ca 3191 defined(WOLFSSL_DEBUG_MATH)
wolfSSL 13:f67a6c6013ca 3192
wolfSSL 13:f67a6c6013ca 3193 /* returns size of ASCII representation */
wolfSSL 13:f67a6c6013ca 3194 int mp_radix_size (mp_int *a, int radix, int *size)
wolfSSL 13:f67a6c6013ca 3195 {
wolfSSL 13:f67a6c6013ca 3196 int res, digs;
wolfSSL 13:f67a6c6013ca 3197 fp_int t;
wolfSSL 13:f67a6c6013ca 3198 fp_digit d;
wolfSSL 13:f67a6c6013ca 3199
wolfSSL 13:f67a6c6013ca 3200 *size = 0;
wolfSSL 13:f67a6c6013ca 3201
wolfSSL 13:f67a6c6013ca 3202 /* special case for binary */
wolfSSL 13:f67a6c6013ca 3203 if (radix == 2) {
wolfSSL 13:f67a6c6013ca 3204 *size = fp_count_bits (a) + (a->sign == FP_NEG ? 1 : 0) + 1;
wolfSSL 13:f67a6c6013ca 3205 return FP_YES;
wolfSSL 13:f67a6c6013ca 3206 }
wolfSSL 13:f67a6c6013ca 3207
wolfSSL 13:f67a6c6013ca 3208 /* make sure the radix is in range */
wolfSSL 13:f67a6c6013ca 3209 if (radix < 2 || radix > 64) {
wolfSSL 13:f67a6c6013ca 3210 return FP_VAL;
wolfSSL 13:f67a6c6013ca 3211 }
wolfSSL 13:f67a6c6013ca 3212
wolfSSL 13:f67a6c6013ca 3213 if (fp_iszero(a) == MP_YES) {
wolfSSL 13:f67a6c6013ca 3214 *size = 2;
wolfSSL 13:f67a6c6013ca 3215 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 3216 }
wolfSSL 13:f67a6c6013ca 3217
wolfSSL 13:f67a6c6013ca 3218 /* digs is the digit count */
wolfSSL 13:f67a6c6013ca 3219 digs = 0;
wolfSSL 13:f67a6c6013ca 3220
wolfSSL 13:f67a6c6013ca 3221 /* if it's negative add one for the sign */
wolfSSL 13:f67a6c6013ca 3222 if (a->sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 3223 ++digs;
wolfSSL 13:f67a6c6013ca 3224 }
wolfSSL 13:f67a6c6013ca 3225
wolfSSL 13:f67a6c6013ca 3226 /* init a copy of the input */
wolfSSL 13:f67a6c6013ca 3227 fp_init_copy (&t, a);
wolfSSL 13:f67a6c6013ca 3228
wolfSSL 13:f67a6c6013ca 3229 /* force temp to positive */
wolfSSL 13:f67a6c6013ca 3230 t.sign = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 3231
wolfSSL 13:f67a6c6013ca 3232 /* fetch out all of the digits */
wolfSSL 13:f67a6c6013ca 3233 while (fp_iszero (&t) == FP_NO) {
wolfSSL 13:f67a6c6013ca 3234 if ((res = fp_div_d (&t, (mp_digit) radix, &t, &d)) != FP_OKAY) {
wolfSSL 13:f67a6c6013ca 3235 fp_zero (&t);
wolfSSL 13:f67a6c6013ca 3236 return res;
wolfSSL 13:f67a6c6013ca 3237 }
wolfSSL 13:f67a6c6013ca 3238 ++digs;
wolfSSL 13:f67a6c6013ca 3239 }
wolfSSL 13:f67a6c6013ca 3240 fp_zero (&t);
wolfSSL 13:f67a6c6013ca 3241
wolfSSL 13:f67a6c6013ca 3242 /* return digs + 1, the 1 is for the NULL byte that would be required. */
wolfSSL 13:f67a6c6013ca 3243 *size = digs + 1;
wolfSSL 13:f67a6c6013ca 3244 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 3245 }
wolfSSL 13:f67a6c6013ca 3246
wolfSSL 13:f67a6c6013ca 3247 /* stores a bignum as a ASCII string in a given radix (2..64) */
wolfSSL 13:f67a6c6013ca 3248 int mp_toradix (mp_int *a, char *str, int radix)
wolfSSL 13:f67a6c6013ca 3249 {
wolfSSL 13:f67a6c6013ca 3250 int res, digs;
wolfSSL 13:f67a6c6013ca 3251 fp_int t;
wolfSSL 13:f67a6c6013ca 3252 fp_digit d;
wolfSSL 13:f67a6c6013ca 3253 char *_s = str;
wolfSSL 13:f67a6c6013ca 3254
wolfSSL 13:f67a6c6013ca 3255 /* check range of the radix */
wolfSSL 13:f67a6c6013ca 3256 if (radix < 2 || radix > 64) {
wolfSSL 13:f67a6c6013ca 3257 return FP_VAL;
wolfSSL 13:f67a6c6013ca 3258 }
wolfSSL 13:f67a6c6013ca 3259
wolfSSL 13:f67a6c6013ca 3260 /* quick out if its zero */
wolfSSL 13:f67a6c6013ca 3261 if (fp_iszero(a) == FP_YES) {
wolfSSL 13:f67a6c6013ca 3262 *str++ = '0';
wolfSSL 13:f67a6c6013ca 3263 *str = '\0';
wolfSSL 13:f67a6c6013ca 3264 return FP_YES;
wolfSSL 13:f67a6c6013ca 3265 }
wolfSSL 13:f67a6c6013ca 3266
wolfSSL 13:f67a6c6013ca 3267 /* init a copy of the input */
wolfSSL 13:f67a6c6013ca 3268 fp_init_copy (&t, a);
wolfSSL 13:f67a6c6013ca 3269
wolfSSL 13:f67a6c6013ca 3270 /* if it is negative output a - */
wolfSSL 13:f67a6c6013ca 3271 if (t.sign == FP_NEG) {
wolfSSL 13:f67a6c6013ca 3272 ++_s;
wolfSSL 13:f67a6c6013ca 3273 *str++ = '-';
wolfSSL 13:f67a6c6013ca 3274 t.sign = FP_ZPOS;
wolfSSL 13:f67a6c6013ca 3275 }
wolfSSL 13:f67a6c6013ca 3276
wolfSSL 13:f67a6c6013ca 3277 digs = 0;
wolfSSL 13:f67a6c6013ca 3278 while (fp_iszero (&t) == FP_NO) {
wolfSSL 13:f67a6c6013ca 3279 if ((res = fp_div_d (&t, (fp_digit) radix, &t, &d)) != FP_OKAY) {
wolfSSL 13:f67a6c6013ca 3280 fp_zero (&t);
wolfSSL 13:f67a6c6013ca 3281 return res;
wolfSSL 13:f67a6c6013ca 3282 }
wolfSSL 13:f67a6c6013ca 3283 *str++ = fp_s_rmap[d];
wolfSSL 13:f67a6c6013ca 3284 ++digs;
wolfSSL 13:f67a6c6013ca 3285 }
wolfSSL 13:f67a6c6013ca 3286
wolfSSL 13:f67a6c6013ca 3287 /* reverse the digits of the string. In this case _s points
wolfSSL 13:f67a6c6013ca 3288 * to the first digit [excluding the sign] of the number]
wolfSSL 13:f67a6c6013ca 3289 */
wolfSSL 13:f67a6c6013ca 3290 fp_reverse ((unsigned char *)_s, digs);
wolfSSL 13:f67a6c6013ca 3291
wolfSSL 13:f67a6c6013ca 3292 /* append a NULL so the string is properly terminated */
wolfSSL 13:f67a6c6013ca 3293 *str = '\0';
wolfSSL 13:f67a6c6013ca 3294
wolfSSL 13:f67a6c6013ca 3295 fp_zero (&t);
wolfSSL 13:f67a6c6013ca 3296 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 3297 }
wolfSSL 13:f67a6c6013ca 3298
wolfSSL 13:f67a6c6013ca 3299 #ifdef WOLFSSL_DEBUG_MATH
wolfSSL 13:f67a6c6013ca 3300 void mp_dump(const char* desc, mp_int* a, byte verbose)
wolfSSL 13:f67a6c6013ca 3301 {
wolfSSL 13:f67a6c6013ca 3302 char buffer[FP_SIZE * sizeof(fp_digit) * 2];
wolfSSL 13:f67a6c6013ca 3303 int size = FP_SIZE;
wolfSSL 13:f67a6c6013ca 3304
wolfSSL 13:f67a6c6013ca 3305 #if defined(ALT_ECC_SIZE) || defined(HAVE_WOLF_BIGINT)
wolfSSL 13:f67a6c6013ca 3306 size = a->size;
wolfSSL 13:f67a6c6013ca 3307 #endif
wolfSSL 13:f67a6c6013ca 3308
wolfSSL 13:f67a6c6013ca 3309 printf("%s: ptr=%p, used=%d, sign=%d, size=%d, fpd=%d\n",
wolfSSL 13:f67a6c6013ca 3310 desc, a, a->used, a->sign, size, (int)sizeof(fp_digit));
wolfSSL 13:f67a6c6013ca 3311
wolfSSL 13:f67a6c6013ca 3312 mp_toradix(a, buffer, 16);
wolfSSL 13:f67a6c6013ca 3313 printf(" %s\n ", buffer);
wolfSSL 13:f67a6c6013ca 3314
wolfSSL 13:f67a6c6013ca 3315 if (verbose) {
wolfSSL 13:f67a6c6013ca 3316 int i;
wolfSSL 13:f67a6c6013ca 3317 for(i=0; i<size * (int)sizeof(fp_digit); i++) {
wolfSSL 13:f67a6c6013ca 3318 printf("%x ", *(((byte*)a->dp) + i));
wolfSSL 13:f67a6c6013ca 3319 }
wolfSSL 13:f67a6c6013ca 3320 printf("\n");
wolfSSL 13:f67a6c6013ca 3321 }
wolfSSL 13:f67a6c6013ca 3322 }
wolfSSL 13:f67a6c6013ca 3323 #endif /* WOLFSSL_DEBUG_MATH */
wolfSSL 13:f67a6c6013ca 3324
wolfSSL 13:f67a6c6013ca 3325 #endif /* defined(WOLFSSL_KEY_GEN) || defined(HAVE_COMP_KEY) || defined(WOLFSSL_DEBUG_MATH) */
wolfSSL 13:f67a6c6013ca 3326
wolfSSL 13:f67a6c6013ca 3327
wolfSSL 13:f67a6c6013ca 3328 int mp_lshd (mp_int * a, int b)
wolfSSL 13:f67a6c6013ca 3329 {
wolfSSL 13:f67a6c6013ca 3330 fp_lshd(a, b);
wolfSSL 13:f67a6c6013ca 3331 return FP_OKAY;
wolfSSL 13:f67a6c6013ca 3332 }
wolfSSL 13:f67a6c6013ca 3333
wolfSSL 13:f67a6c6013ca 3334 #endif /* USE_FAST_MATH */
wolfSSL 13:f67a6c6013ca 3335