3 * Copyright (C) 2006-2014 wolfSSL Inc.
5 * This file is part of CyaSSL.
7 * CyaSSL is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
12 * CyaSSL is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24 * Based on public domain TomsFastMath 0.10 by Tom St Denis, tomstdenis@iahu.ca,
25 * http://math.libtomcrypt.com
29 * Edited by Moisés Guimarães (moisesguimaraesm@gmail.com)
30 * to fit CyaSSL's needs.
37 /* in case user set USE_FAST_MATH there */
38 #include <cyassl/ctaocrypt/settings.h>
42 #include <cyassl/ctaocrypt/tfm.h>
43 #include <ctaocrypt/src/asm.c> /* will define asm MACROS or C ones */
46 /* math settings check */
47 word32 CheckRunTimeSettings(void)
53 /* math settings size check */
54 word32 CheckRunTimeFastMath(void)
62 void fp_add(fp_int *a, fp_int *b, fp_int *c)
66 /* get sign of both inputs */
70 /* handle two cases, not four */
72 /* both positive or both negative */
73 /* add their magnitudes, copy the sign */
77 /* one positive, the other negative */
78 /* subtract the one with the greater magnitude from */
79 /* the one of the lesser magnitude. The result gets */
80 /* the sign of the one with the greater magnitude. */
81 if (fp_cmp_mag (a, b) == FP_LT) {
91 /* unsigned addition */
92 void s_fp_add(fp_int *a, fp_int *b, fp_int *c)
97 y = MAX(a->used, b->used);
98 oldused = MAX(c->used, FP_SIZE); /* help static analysis w/ max size */
102 for (x = 0; x < y; x++) {
103 t += ((fp_word)a->dp[x]) + ((fp_word)b->dp[x]);
104 c->dp[x] = (fp_digit)t;
107 if (t != 0 && x < FP_SIZE) {
108 c->dp[c->used++] = (fp_digit)t;
113 for (; x < oldused; x++) {
120 void fp_sub(fp_int *a, fp_int *b, fp_int *c)
128 /* subtract a negative from a positive, OR */
129 /* subtract a positive from a negative. */
130 /* In either case, ADD their magnitudes, */
131 /* and use the sign of the first number. */
135 /* subtract a positive from a positive, OR */
136 /* subtract a negative from a negative. */
137 /* First, take the difference between their */
138 /* magnitudes, then... */
139 if (fp_cmp_mag (a, b) != FP_LT) {
140 /* Copy the sign from the first */
142 /* The first has a larger or equal magnitude */
145 /* The result has the *opposite* sign from */
146 /* the first number. */
147 c->sign = (sa == FP_ZPOS) ? FP_NEG : FP_ZPOS;
148 /* The second has a larger magnitude */
154 /* unsigned subtraction ||a|| >= ||b|| ALWAYS! */
155 void s_fp_sub(fp_int *a, fp_int *b, fp_int *c)
157 int x, oldbused, oldused;
164 for (x = 0; x < oldbused; x++) {
165 t = ((fp_word)a->dp[x]) - (((fp_word)b->dp[x]) + t);
166 c->dp[x] = (fp_digit)t;
167 t = (t >> DIGIT_BIT)&1;
169 for (; x < a->used; x++) {
170 t = ((fp_word)a->dp[x]) - t;
171 c->dp[x] = (fp_digit)t;
172 t = (t >> DIGIT_BIT)&1;
174 for (; x < oldused; x++) {
181 void fp_mul(fp_int *A, fp_int *B, fp_int *C)
185 y = MAX(A->used, B->used);
186 yy = MIN(A->used, B->used);
188 /* call generic if we're out of range */
189 if (y + yy > FP_SIZE) {
190 fp_mul_comba(A, B, C);
194 /* pick a comba (unrolled 4/8/16/32 x or rolled) based on the size
195 of the largest input. We also want to avoid doing excess mults if the
196 inputs are not close to the next power of two. That is, for example,
197 if say y=17 then we would do (32-17)^2 = 225 unneeded multiplications
202 fp_mul_comba3(A,B,C);
208 fp_mul_comba4(A,B,C);
214 fp_mul_comba6(A,B,C);
220 fp_mul_comba7(A,B,C);
226 fp_mul_comba8(A,B,C);
232 fp_mul_comba9(A,B,C);
238 fp_mul_comba12(A,B,C);
244 fp_mul_comba17(A,B,C);
251 fp_mul_comba_small(A,B,C);
255 #if defined(TFM_MUL20)
257 fp_mul_comba20(A,B,C);
261 #if defined(TFM_MUL24)
262 if (yy >= 16 && y <= 24) {
263 fp_mul_comba24(A,B,C);
267 #if defined(TFM_MUL28)
268 if (yy >= 20 && y <= 28) {
269 fp_mul_comba28(A,B,C);
273 #if defined(TFM_MUL32)
274 if (yy >= 24 && y <= 32) {
275 fp_mul_comba32(A,B,C);
279 #if defined(TFM_MUL48)
280 if (yy >= 40 && y <= 48) {
281 fp_mul_comba48(A,B,C);
285 #if defined(TFM_MUL64)
286 if (yy >= 56 && y <= 64) {
287 fp_mul_comba64(A,B,C);
294 void fp_mul_2(fp_int * a, fp_int * b)
302 register fp_digit r, rr, *tmpa, *tmpb;
304 /* alias for source */
312 for (x = 0; x < a->used; x++) {
314 /* get what will be the *next* carry bit from the
315 * MSB of the current digit
317 rr = *tmpa >> ((fp_digit)(DIGIT_BIT - 1));
319 /* now shift up this digit, add in the carry [from the previous] */
320 *tmpb++ = ((*tmpa++ << ((fp_digit)1)) | r);
322 /* copy the carry that would be from the source
323 * digit into the next iteration
328 /* new leading digit? */
329 if (r != 0 && b->used != (FP_SIZE-1)) {
330 /* add a MSB which is always 1 at this point */
335 /* now zero any excess digits on the destination
336 * that we didn't write to
338 tmpb = b->dp + b->used;
339 for (x = b->used; x < oldused; x++) {
347 void fp_mul_d(fp_int *a, fp_digit b, fp_int *c)
356 for (x = 0; x < a->used; x++) {
357 w = ((fp_word)a->dp[x]) * ((fp_word)b) + w;
358 c->dp[x] = (fp_digit)w;
361 if (w != 0 && (a->used != FP_SIZE)) {
362 c->dp[c->used++] = (fp_digit) w;
365 for (; x < oldused; x++) {
372 void fp_mul_2d(fp_int *a, int b, fp_int *c)
374 fp_digit carry, carrytmp, shift;
380 /* handle whole digits */
381 if (b >= DIGIT_BIT) {
382 fp_lshd(c, b/DIGIT_BIT);
386 /* shift the digits */
389 shift = DIGIT_BIT - b;
390 for (x = 0; x < c->used; x++) {
391 carrytmp = c->dp[x] >> shift;
392 c->dp[x] = (c->dp[x] << b) + carry;
395 /* store last carry if room */
396 if (carry && x < FP_SIZE) {
397 c->dp[c->used++] = carry;
403 /* generic PxQ multiplier */
404 void fp_mul_comba(fp_int *A, fp_int *B, fp_int *C)
406 int ix, iy, iz, tx, ty, pa;
407 fp_digit c0, c1, c2, *tmpx, *tmpy;
413 /* get size of output and trim */
414 pa = A->used + B->used;
419 if (A == C || B == C) {
427 for (ix = 0; ix < pa; ix++) {
428 /* get offsets into the two bignums */
429 ty = MIN(ix, B->used-1);
432 /* setup temp aliases */
436 /* this is the number of times the loop will iterrate, essentially its
437 while (tx++ < a->used && ty-- >= 0) { ... }
439 iy = MIN(A->used-tx, ty+1);
443 for (iz = 0; iz < iy; ++iz) {
444 /* TAO change COMBA_ADD back to MULADD */
445 MULADD(*tmpx++, *tmpy--);
449 COMBA_STORE(dst->dp[ix]);
454 dst->sign = A->sign ^ B->sign;
459 /* a/b => cb + d == a */
460 int fp_div(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
462 fp_int q, x, y, t1, t2;
463 int n, t, i, norm, neg;
465 /* is divisor zero ? */
466 if (fp_iszero (b) == 1) {
470 /* if a < b then q=0, r = a */
471 if (fp_cmp_mag (a, b) == FP_LT) {
482 q.used = a->used + 2;
490 neg = (a->sign == b->sign) ? FP_ZPOS : FP_NEG;
491 x.sign = y.sign = FP_ZPOS;
493 /* normalize both x and y, ensure that y >= b/2, [b == 2**DIGIT_BIT] */
494 norm = fp_count_bits(&y) % DIGIT_BIT;
495 if (norm < (int)(DIGIT_BIT-1)) {
496 norm = (DIGIT_BIT-1) - norm;
497 fp_mul_2d (&x, norm, &x);
498 fp_mul_2d (&y, norm, &y);
503 /* note hac does 0 based, so if used==5 then its 0,1,2,3,4, e.g. use 4 */
507 /* while (x >= y*b**n-t) do { q[n-t] += 1; x -= y*b**{n-t} } */
508 fp_lshd (&y, n - t); /* y = y*b**{n-t} */
510 while (fp_cmp (&x, &y) != FP_LT) {
515 /* reset y by shifting it back down */
518 /* step 3. for i from n down to (t + 1) */
519 for (i = n; i >= (t + 1); i--) {
524 /* step 3.1 if xi == yt then set q{i-t-1} to b-1,
525 * otherwise set q{i-t-1} to (xi*b + x{i-1})/yt */
526 if (x.dp[i] == y.dp[t]) {
527 q.dp[i - t - 1] = (fp_digit) ((((fp_word)1) << DIGIT_BIT) - 1);
530 tmp = ((fp_word) x.dp[i]) << ((fp_word) DIGIT_BIT);
531 tmp |= ((fp_word) x.dp[i - 1]);
532 tmp /= ((fp_word)y.dp[t]);
533 q.dp[i - t - 1] = (fp_digit) (tmp);
536 /* while (q{i-t-1} * (yt * b + y{t-1})) >
537 xi * b**2 + xi-1 * b + xi-2
541 q.dp[i - t - 1] = (q.dp[i - t - 1] + 1);
543 q.dp[i - t - 1] = (q.dp[i - t - 1] - 1);
547 t1.dp[0] = (t - 1 < 0) ? 0 : y.dp[t - 1];
550 fp_mul_d (&t1, q.dp[i - t - 1], &t1);
552 /* find right hand */
553 t2.dp[0] = (i - 2 < 0) ? 0 : x.dp[i - 2];
554 t2.dp[1] = (i - 1 < 0) ? 0 : x.dp[i - 1];
557 } while (fp_cmp_mag(&t1, &t2) == FP_GT);
559 /* step 3.3 x = x - q{i-t-1} * y * b**{i-t-1} */
560 fp_mul_d (&y, q.dp[i - t - 1], &t1);
561 fp_lshd (&t1, i - t - 1);
562 fp_sub (&x, &t1, &x);
564 /* if x < 0 then { x = x + y*b**{i-t-1}; q{i-t-1} -= 1; } */
565 if (x.sign == FP_NEG) {
567 fp_lshd (&t1, i - t - 1);
568 fp_add (&x, &t1, &x);
569 q.dp[i - t - 1] = q.dp[i - t - 1] - 1;
573 /* now q is the quotient and x is the remainder
574 * [which we have to normalize]
577 /* get sign before writing to c */
578 x.sign = x.used == 0 ? FP_ZPOS : a->sign;
587 fp_div_2d (&x, norm, &x, NULL);
589 /* the following is a kludge, essentially we were seeing the right remainder but
590 with excess digits that should have been zero
592 for (i = b->used; i < x.used; i++) {
603 void fp_div_2(fp_int * a, fp_int * b)
610 register fp_digit r, rr, *tmpa, *tmpb;
613 tmpa = a->dp + b->used - 1;
616 tmpb = b->dp + b->used - 1;
620 for (x = b->used - 1; x >= 0; x--) {
621 /* get the carry for the next iteration */
624 /* shift the current digit, add in carry and store */
625 *tmpb-- = (*tmpa-- >> 1) | (r << (DIGIT_BIT - 1));
627 /* forward carry to next iteration */
631 /* zero excess digits */
632 tmpb = b->dp + b->used;
633 for (x = b->used; x < oldused; x++) {
642 void fp_div_2d(fp_int *a, int b, fp_int *c, fp_int *d)
647 /* if the shift count is <= 0 then we do no work */
658 /* get the remainder */
660 fp_mod_2d (a, b, &t);
666 /* shift by as many digits in the bit count */
667 if (b >= (int)DIGIT_BIT) {
668 fp_rshd (c, b / DIGIT_BIT);
671 /* shift any bit count < DIGIT_BIT */
682 /* c = a mod b, 0 <= c < b */
683 int fp_mod(fp_int *a, fp_int *b, fp_int *c)
689 if ((err = fp_div(a, b, NULL, &t)) != FP_OKAY) {
692 if (t.sign != b->sign) {
701 void fp_mod_2d(fp_int *a, int b, fp_int *c)
705 /* zero if count less than or equal to zero */
711 /* get copy of input */
714 /* if 2**d is larger than we just return */
715 if (b >= (DIGIT_BIT * a->used)) {
719 /* zero digits above the last digit of the modulus */
720 for (x = (b / DIGIT_BIT) + ((b % DIGIT_BIT) == 0 ? 0 : 1); x < c->used; x++) {
723 /* clear the digit that is not completely outside/inside the modulus */
724 c->dp[b / DIGIT_BIT] &= ~((fp_digit)0) >> (DIGIT_BIT - b);
728 static int fp_invmod_slow (fp_int * a, fp_int * b, fp_int * c)
730 fp_int x, y, u, v, A, B, C, D;
733 /* b cannot be negative */
734 if (b->sign == FP_NEG || fp_iszero(b) == 1) {
739 fp_init(&x); fp_init(&y);
740 fp_init(&u); fp_init(&v);
741 fp_init(&A); fp_init(&B);
742 fp_init(&C); fp_init(&D);
745 if ((res = fp_mod(a, b, &x)) != FP_OKAY) {
750 /* 2. [modified] if x,y are both even then return an error! */
751 if (fp_iseven (&x) == 1 && fp_iseven (&y) == 1) {
755 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
762 /* 4. while u is even do */
763 while (fp_iseven (&u) == 1) {
767 /* 4.2 if A or B is odd then */
768 if (fp_isodd (&A) == 1 || fp_isodd (&B) == 1) {
769 /* A = (A+y)/2, B = (B-x)/2 */
773 /* A = A/2, B = B/2 */
778 /* 5. while v is even do */
779 while (fp_iseven (&v) == 1) {
783 /* 5.2 if C or D is odd then */
784 if (fp_isodd (&C) == 1 || fp_isodd (&D) == 1) {
785 /* C = (C+y)/2, D = (D-x)/2 */
789 /* C = C/2, D = D/2 */
794 /* 6. if u >= v then */
795 if (fp_cmp (&u, &v) != FP_LT) {
796 /* u = u - v, A = A - C, B = B - D */
801 /* v - v - u, C = C - A, D = D - B */
807 /* if not zero goto step 4 */
808 if (fp_iszero (&u) == 0)
811 /* now a = C, b = D, gcd == g*v */
813 /* if v != 1 then there is no inverse */
814 if (fp_cmp_d (&v, 1) != FP_EQ) {
819 while (fp_cmp_d(&C, 0) == FP_LT) {
824 while (fp_cmp_mag(&C, b) != FP_LT) {
828 /* C is now the inverse */
833 /* c = 1/a (mod b) for odd b only */
834 int fp_invmod(fp_int *a, fp_int *b, fp_int *c)
836 fp_int x, y, u, v, B, D;
839 /* 2. [modified] b must be odd */
840 if (fp_iseven (b) == FP_YES) {
841 return fp_invmod_slow(a,b,c);
844 /* init all our temps */
845 fp_init(&x); fp_init(&y);
846 fp_init(&u); fp_init(&v);
847 fp_init(&B); fp_init(&D);
849 /* x == modulus, y == value to invert */
852 /* we need y = |a| */
855 /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
861 /* 4. while u is even do */
862 while (fp_iseven (&u) == FP_YES) {
866 /* 4.2 if B is odd then */
867 if (fp_isodd (&B) == FP_YES) {
874 /* 5. while v is even do */
875 while (fp_iseven (&v) == FP_YES) {
879 /* 5.2 if D is odd then */
880 if (fp_isodd (&D) == FP_YES) {
888 /* 6. if u >= v then */
889 if (fp_cmp (&u, &v) != FP_LT) {
890 /* u = u - v, B = B - D */
894 /* v - v - u, D = D - B */
899 /* if not zero goto step 4 */
900 if (fp_iszero (&u) == FP_NO) {
904 /* now a = C, b = D, gcd == g*v */
906 /* if v != 1 then there is no inverse */
907 if (fp_cmp_d (&v, 1) != FP_EQ) {
911 /* b is now the inverse */
913 while (D.sign == FP_NEG) {
921 /* d = a * b (mod c) */
922 int fp_mulmod(fp_int *a, fp_int *b, fp_int *c, fp_int *d)
927 return fp_mod(&tmp, c, d);
930 #ifdef TFM_TIMING_RESISTANT
932 /* timing resistant montgomery ladder based exptmod
934 Based on work by Marc Joye, Sung-Ming Yen, "The Montgomery Powering Ladder", Cryptographic Hardware and Embedded Systems, CHES 2002
936 static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
940 int err, bitcnt, digidx, y;
942 /* now setup montgomery */
943 if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
950 /* now we need R mod m */
951 fp_montgomery_calc_normalization (&R[0], P);
953 /* now set R[0][1] to G * R mod m */
954 if (fp_cmp_mag(P, G) != FP_GT) {
955 /* G > P so we reduce it first */
960 fp_mulmod (&R[1], &R[0], P, &R[1]);
962 /* for j = t-1 downto 0 do
963 r_!k = R0*R1; r_k = r_k^2
966 /* set initial mode and bit cnt */
969 digidx = X->used - 1;
972 /* grab next digit as required */
974 /* if digidx == -1 we are out of digits so break */
978 /* read next digit and reset bitcnt */
979 buf = X->dp[digidx--];
980 bitcnt = (int)DIGIT_BIT;
983 /* grab the next msb from the exponent */
984 y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
988 fp_mul(&R[0], &R[1], &R[y^1]); fp_montgomery_reduce(&R[y^1], P, mp);
989 fp_sqr(&R[y], &R[y]); fp_montgomery_reduce(&R[y], P, mp);
992 fp_montgomery_reduce(&R[0], P, mp);
1000 * Some restrictions... x must be positive and < b
1002 static int _fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
1006 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
1008 /* find window size */
1009 x = fp_count_bits (X);
1012 } else if (x <= 36) {
1014 } else if (x <= 140) {
1016 } else if (x <= 450) {
1023 XMEMSET(M, 0, sizeof(M));
1025 /* now setup montgomery */
1026 if ((err = fp_montgomery_setup (P, &mp)) != FP_OKAY) {
1035 * The M table contains powers of the input base, e.g. M[x] = G^x mod P
1037 * The first half of the table is not computed though accept for M[0] and M[1]
1040 /* now we need R mod m */
1041 fp_montgomery_calc_normalization (&res, P);
1043 /* now set M[1] to G * R mod m */
1044 if (fp_cmp_mag(P, G) != FP_GT) {
1045 /* G > P so we reduce it first */
1046 fp_mod(G, P, &M[1]);
1050 fp_mulmod (&M[1], &res, P, &M[1]);
1052 /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */
1053 fp_copy (&M[1], &M[1 << (winsize - 1)]);
1054 for (x = 0; x < (winsize - 1); x++) {
1055 fp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)]);
1056 fp_montgomery_reduce (&M[1 << (winsize - 1)], P, mp);
1059 /* create upper table */
1060 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
1061 fp_mul(&M[x - 1], &M[1], &M[x]);
1062 fp_montgomery_reduce(&M[x], P, mp);
1065 /* set initial mode and bit cnt */
1069 digidx = X->used - 1;
1074 /* grab next digit as required */
1075 if (--bitcnt == 0) {
1076 /* if digidx == -1 we are out of digits so break */
1080 /* read next digit and reset bitcnt */
1081 buf = X->dp[digidx--];
1082 bitcnt = (int)DIGIT_BIT;
1085 /* grab the next msb from the exponent */
1086 y = (int)(buf >> (DIGIT_BIT - 1)) & 1;
1087 buf <<= (fp_digit)1;
1089 /* if the bit is zero and mode == 0 then we ignore it
1090 * These represent the leading zero bits before the first 1 bit
1091 * in the exponent. Technically this opt is not required but it
1092 * does lower the # of trivial squaring/reductions used
1094 if (mode == 0 && y == 0) {
1098 /* if the bit is zero and mode == 1 then we square */
1099 if (mode == 1 && y == 0) {
1101 fp_montgomery_reduce(&res, P, mp);
1105 /* else we add it to the window */
1106 bitbuf |= (y << (winsize - ++bitcpy));
1109 if (bitcpy == winsize) {
1110 /* ok window is filled so square as required and multiply */
1112 for (x = 0; x < winsize; x++) {
1114 fp_montgomery_reduce(&res, P, mp);
1118 fp_mul(&res, &M[bitbuf], &res);
1119 fp_montgomery_reduce(&res, P, mp);
1121 /* empty window and reset */
1128 /* if bits remain then square/multiply */
1129 if (mode == 2 && bitcpy > 0) {
1130 /* square then multiply if the bit is set */
1131 for (x = 0; x < bitcpy; x++) {
1133 fp_montgomery_reduce(&res, P, mp);
1135 /* get next bit of the window */
1137 if ((bitbuf & (1 << winsize)) != 0) {
1139 fp_mul(&res, &M[1], &res);
1140 fp_montgomery_reduce(&res, P, mp);
1145 /* fixup result if Montgomery reduction is used
1146 * recall that any value in a Montgomery system is
1147 * actually multiplied by R mod n. So we have
1148 * to reduce one more time to cancel out the factor
1151 fp_montgomery_reduce(&res, P, mp);
1153 /* swap res with Y */
1160 int fp_exptmod(fp_int * G, fp_int * X, fp_int * P, fp_int * Y)
1162 /* prevent overflows */
1163 if (P->used > (FP_SIZE/2)) {
1167 if (X->sign == FP_NEG) {
1168 #ifndef POSITIVE_EXP_ONLY /* reduce stack if assume no negatives */
1172 /* yes, copy G and invmod it */
1174 if ((err = fp_invmod(&tmp, P, &tmp)) != FP_OKAY) {
1178 err = _fp_exptmod(&tmp, X, P, Y);
1188 /* Positive exponent so just exptmod */
1189 return _fp_exptmod(G, X, P, Y);
1193 /* computes a = 2**b */
1194 void fp_2expt(fp_int *a, int b)
1198 /* zero a as per default */
1210 /* set the used count of where the bit will go */
1213 /* put the single bit in its place */
1214 a->dp[z] = ((fp_digit)1) << (b % DIGIT_BIT);
1218 void fp_sqr(fp_int *A, fp_int *B)
1222 /* call generic if we're out of range */
1223 if (y + y > FP_SIZE) {
1228 #if defined(TFM_SQR3)
1234 #if defined(TFM_SQR4)
1240 #if defined(TFM_SQR6)
1246 #if defined(TFM_SQR7)
1252 #if defined(TFM_SQR8)
1258 #if defined(TFM_SQR9)
1264 #if defined(TFM_SQR12)
1266 fp_sqr_comba12(A,B);
1270 #if defined(TFM_SQR17)
1272 fp_sqr_comba17(A,B);
1276 #if defined(TFM_SMALL_SET)
1278 fp_sqr_comba_small(A,B);
1282 #if defined(TFM_SQR20)
1284 fp_sqr_comba20(A,B);
1288 #if defined(TFM_SQR24)
1290 fp_sqr_comba24(A,B);
1294 #if defined(TFM_SQR28)
1296 fp_sqr_comba28(A,B);
1300 #if defined(TFM_SQR32)
1302 fp_sqr_comba32(A,B);
1306 #if defined(TFM_SQR48)
1308 fp_sqr_comba48(A,B);
1312 #if defined(TFM_SQR64)
1314 fp_sqr_comba64(A,B);
1321 /* generic comba squarer */
1322 void fp_sqr_comba(fp_int *A, fp_int *B)
1325 fp_digit c0, c1, c2;
1331 /* get size of output and trim */
1332 pa = A->used + A->used;
1333 if (pa >= FP_SIZE) {
1337 /* number of output digits to produce */
1349 for (ix = 0; ix < pa; ix++) {
1351 fp_digit *tmpy, *tmpx;
1353 /* get offsets into the two bignums */
1354 ty = MIN(A->used-1, ix);
1357 /* setup temp aliases */
1361 /* this is the number of times the loop will iterrate,
1362 while (tx++ < a->used && ty-- >= 0) { ... }
1364 iy = MIN(A->used-tx, ty+1);
1366 /* now for squaring tx can never equal ty
1367 * we halve the distance since they approach
1368 * at a rate of 2x and we have to round because
1369 * odd cases need to be executed
1371 iy = MIN(iy, (ty-tx+1)>>1);
1373 /* forward carries */
1377 for (iz = 0; iz < iy; iz++) {
1378 SQRADD2(*tmpx++, *tmpy--);
1381 /* even columns have the square term in them */
1383 /* TAO change COMBA_ADD back to SQRADD */
1384 SQRADD(A->dp[ix>>1], A->dp[ix>>1]);
1388 COMBA_STORE(dst->dp[ix]);
1401 int fp_cmp(fp_int *a, fp_int *b)
1403 if (a->sign == FP_NEG && b->sign == FP_ZPOS) {
1405 } else if (a->sign == FP_ZPOS && b->sign == FP_NEG) {
1408 /* compare digits */
1409 if (a->sign == FP_NEG) {
1410 /* if negative compare opposite direction */
1411 return fp_cmp_mag(b, a);
1413 return fp_cmp_mag(a, b);
1418 /* compare against a single digit */
1419 int fp_cmp_d(fp_int *a, fp_digit b)
1421 /* compare based on sign */
1422 if ((b && a->used == 0) || a->sign == FP_NEG) {
1426 /* compare based on magnitude */
1431 /* compare the only digit of a to b */
1434 } else if (a->dp[0] < b) {
1442 int fp_cmp_mag(fp_int *a, fp_int *b)
1446 if (a->used > b->used) {
1448 } else if (a->used < b->used) {
1451 for (x = a->used - 1; x >= 0; x--) {
1452 if (a->dp[x] > b->dp[x]) {
1454 } else if (a->dp[x] < b->dp[x]) {
1462 /* setups the montgomery reduction */
1463 int fp_montgomery_setup(fp_int *a, fp_digit *rho)
1467 /* fast inversion mod 2**k
1469 * Based on the fact that
1471 * XA = 1 (mod 2**n) => (X(2-XA)) A = 1 (mod 2**2n)
1472 * => 2*X*A - X*X*A*A = 1
1473 * => 2*(1) - (1) = 1
1481 x = (((b + 2) & 4) << 1) + b; /* here x*a==1 mod 2**4 */
1482 x *= 2 - b * x; /* here x*a==1 mod 2**8 */
1483 x *= 2 - b * x; /* here x*a==1 mod 2**16 */
1484 x *= 2 - b * x; /* here x*a==1 mod 2**32 */
1486 x *= 2 - b * x; /* here x*a==1 mod 2**64 */
1489 /* rho = -1/m mod b */
1490 *rho = (fp_digit) (((fp_word) 1 << ((fp_word) DIGIT_BIT)) - ((fp_word)x));
1495 /* computes a = B**n mod b without division or multiplication useful for
1496 * normalizing numbers in a Montgomery system.
1498 void fp_montgomery_calc_normalization(fp_int *a, fp_int *b)
1502 /* how many bits of last digit does b use */
1503 bits = fp_count_bits (b) % DIGIT_BIT;
1504 if (!bits) bits = DIGIT_BIT;
1506 /* compute A = B^(n-1) * 2^(bits-1) */
1508 fp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1);
1514 /* now compute C = A * B mod b */
1515 for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
1517 if (fp_cmp_mag (a, b) != FP_LT) {
1524 #ifdef TFM_SMALL_MONT_SET
1525 #include "fp_mont_small.i"
1528 /* computes x/R == x (mod N) via Montgomery Reduction */
1529 void fp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp)
1531 fp_digit c[FP_SIZE], *_c, *tmpm, mu = 0;
1532 int oldused, x, y, pa;
1534 /* bail if too large */
1535 if (m->used > (FP_SIZE/2)) {
1536 (void)mu; /* shut up compiler */
1540 #ifdef TFM_SMALL_MONT_SET
1541 if (m->used <= 16) {
1542 fp_montgomery_reduce_small(a, m, mp);
1548 /* now zero the buff */
1549 XMEMSET(c, 0, sizeof c);
1552 /* copy the input */
1554 for (x = 0; x < oldused; x++) {
1559 for (x = 0; x < pa; x++) {
1561 /* get Mu for this round */
1566 #if (defined(TFM_SSE2) || defined(TFM_X86_64))
1567 for (; y < (pa & ~7); y += 8) {
1574 for (; y < pa; y++) {
1588 for (x = 0; x < pa+1; x++) {
1592 for (; x < oldused; x++) {
1601 /* if A >= m then A = A - m */
1602 if (fp_cmp_mag (a, m) != FP_LT) {
1607 void fp_read_unsigned_bin(fp_int *a, unsigned char *b, int c)
1612 /* If we know the endianness of this architecture, and we're using
1613 32-bit fp_digits, we can optimize this */
1614 #if (defined(LITTLE_ENDIAN_ORDER) || defined(BIG_ENDIAN_ORDER)) && !defined(FP_64BIT)
1615 /* But not for both simultaneously */
1616 #if defined(LITTLE_ENDIAN_ORDER) && defined(BIG_ENDIAN_ORDER)
1617 #error Both LITTLE_ENDIAN_ORDER and BIG_ENDIAN_ORDER defined.
1620 unsigned char *pd = (unsigned char *)a->dp;
1622 if ((unsigned)c > (FP_SIZE * sizeof(fp_digit))) {
1623 int excess = c - (FP_SIZE * sizeof(fp_digit));
1627 a->used = (c + sizeof(fp_digit) - 1)/sizeof(fp_digit);
1628 /* read the bytes in */
1629 #ifdef BIG_ENDIAN_ORDER
1631 /* Use Duff's device to unroll the loop. */
1632 int idx = (c - 1) & ~3;
1634 case 0: do { pd[idx+0] = *b++;
1635 case 3: pd[idx+1] = *b++;
1636 case 2: pd[idx+2] = *b++;
1637 case 1: pd[idx+3] = *b++;
1639 } while ((c -= 4) > 0);
1643 for (c -= 1; c >= 0; c -= 1) {
1649 /* read the bytes in */
1650 for (; c > 0; c--) {
1651 fp_mul_2d (a, 8, a);
1659 void fp_to_unsigned_bin(fp_int *a, unsigned char *b)
1664 fp_init_copy(&t, a);
1667 while (fp_iszero (&t) == FP_NO) {
1668 b[x++] = (unsigned char) (t.dp[0] & 255);
1669 fp_div_2d (&t, 8, &t, NULL);
1674 int fp_unsigned_bin_size(fp_int *a)
1676 int size = fp_count_bits (a);
1677 return (size / 8 + ((size & 7) != 0 ? 1 : 0));
1680 void fp_set(fp_int *a, fp_digit b)
1684 a->used = a->dp[0] ? 1 : 0;
1687 int fp_count_bits (fp_int * a)
1697 /* get number of digits and add that */
1698 r = (a->used - 1) * DIGIT_BIT;
1700 /* take the last digit and count the bits in it */
1701 q = a->dp[a->used - 1];
1702 while (q > ((fp_digit) 0)) {
1704 q >>= ((fp_digit) 1);
1709 int fp_leading_bit(fp_int *a)
1714 fp_digit q = a->dp[a->used - 1];
1715 int qSz = sizeof(fp_digit);
1718 if ((unsigned char)q != 0)
1719 bit = (q & 0x80) != 0;
1728 void fp_lshd(fp_int *a, int x)
1732 /* move up and truncate as required */
1733 y = MIN(a->used + x - 1, (int)(FP_SIZE-1));
1735 /* store new size */
1739 for (; y >= x; y--) {
1740 a->dp[y] = a->dp[y-x];
1743 /* zero lower digits */
1744 for (; y >= 0; y--) {
1753 /* right shift by bit count */
1754 void fp_rshb(fp_int *c, int x)
1756 register fp_digit *tmpc, mask, shift;
1761 mask = (((fp_digit)1) << D) - 1;
1764 shift = DIGIT_BIT - D;
1767 tmpc = c->dp + (c->used - 1);
1771 for (x = c->used - 1; x >= 0; x--) {
1772 /* get the lower bits of this word in a temp */
1775 /* shift the current word and mix in the carry bits from previous word */
1776 *tmpc = (*tmpc >> D) | (r << shift);
1779 /* set the carry to the carry bits of the current word found above */
1785 void fp_rshd(fp_int *a, int x)
1789 /* too many digits just zero and return */
1796 for (y = 0; y < a->used - x; y++) {
1797 a->dp[y] = a->dp[y+x];
1801 for (; y < a->used; y++) {
1805 /* decrement count */
1810 /* reverse an array, used for radix code */
1811 void fp_reverse (unsigned char *s, int len)
1829 void fp_sub_d(fp_int *a, fp_digit b, fp_int *c)
1837 /* CyaSSL callers from normal lib */
1839 /* init a new mp_int */
1840 int mp_init (mp_int * a)
1847 /* clear one (frees) */
1848 void mp_clear (mp_int * a)
1853 /* handle up to 6 inits */
1854 int mp_init_multi(mp_int* a, mp_int* b, mp_int* c, mp_int* d, mp_int* e, mp_int* f)
1872 /* high level addition (handles signs) */
1873 int mp_add (mp_int * a, mp_int * b, mp_int * c)
1879 /* high level subtraction (handles signs) */
1880 int mp_sub (mp_int * a, mp_int * b, mp_int * c)
1886 /* high level multiplication (handles sign) */
1887 int mp_mul (mp_int * a, mp_int * b, mp_int * c)
1893 /* d = a * b (mod c) */
1894 int mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
1896 return fp_mulmod(a, b, c, d);
1899 /* c = a mod b, 0 <= c < b */
1900 int mp_mod (mp_int * a, mp_int * b, mp_int * c)
1902 return fp_mod (a, b, c);
1905 /* hac 14.61, pp608 */
1906 int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
1908 return fp_invmod(a, b, c);
1911 /* this is a shell function that calls either the normal or Montgomery
1912 * exptmod functions. Originally the call to the montgomery code was
1913 * embedded in the normal function but that wasted alot of stack space
1914 * for nothing (since 99% of the time the Montgomery code would be called)
1916 int mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y)
1918 return fp_exptmod(G, X, P, Y);
1921 /* compare two ints (signed)*/
1922 int mp_cmp (mp_int * a, mp_int * b)
1924 return fp_cmp(a, b);
1927 /* compare a digit */
1928 int mp_cmp_d(mp_int * a, mp_digit b)
1930 return fp_cmp_d(a, b);
1933 /* get the size for an unsigned equivalent */
1934 int mp_unsigned_bin_size (mp_int * a)
1936 return fp_unsigned_bin_size(a);
1939 /* store in unsigned [big endian] format */
1940 int mp_to_unsigned_bin (mp_int * a, unsigned char *b)
1942 fp_to_unsigned_bin(a,b);
1946 /* reads a unsigned char array, assumes the msb is stored first [big endian] */
1947 int mp_read_unsigned_bin (mp_int * a, const unsigned char *b, int c)
1949 fp_read_unsigned_bin(a, (unsigned char *)b, c);
1954 int mp_sub_d(fp_int *a, fp_digit b, fp_int *c)
1961 /* fast math conversion */
1962 int mp_copy(fp_int* a, fp_int* b)
1969 /* fast math conversion */
1970 int mp_isodd(mp_int* a)
1976 /* fast math conversion */
1977 int mp_iszero(mp_int* a)
1979 return fp_iszero(a);
1983 /* fast math conversion */
1984 int mp_count_bits (mp_int* a)
1986 return fp_count_bits(a);
1990 int mp_leading_bit (mp_int* a)
1992 return fp_leading_bit(a);
1996 /* fast math conversion */
1997 void mp_rshb (mp_int* a, int x)
2003 /* fast math wrappers */
2004 int mp_set_int(fp_int *a, fp_digit b)
2011 #if defined(CYASSL_KEY_GEN) || defined (HAVE_ECC)
2013 /* c = a * a (mod b) */
2014 int fp_sqrmod(fp_int *a, fp_int *b, fp_int *c)
2019 return fp_mod(&tmp, b, c);
2022 /* fast math conversion */
2023 int mp_sqrmod(mp_int *a, mp_int *b, mp_int *c)
2025 return fp_sqrmod(a, b, c);
2028 /* fast math conversion */
2029 int mp_montgomery_calc_normalization(mp_int *a, mp_int *b)
2031 fp_montgomery_calc_normalization(a, b);
2035 #endif /* CYASSL_KEYGEN || HAVE_ECC */
2038 #ifdef CYASSL_KEY_GEN
2040 void fp_gcd(fp_int *a, fp_int *b, fp_int *c);
2041 void fp_lcm(fp_int *a, fp_int *b, fp_int *c);
2042 int fp_isprime(fp_int *a);
2043 int fp_cnt_lsb(fp_int *a);
2045 int mp_gcd(fp_int *a, fp_int *b, fp_int *c)
2052 int mp_lcm(fp_int *a, fp_int *b, fp_int *c)
2059 int mp_prime_is_prime(mp_int* a, int t, int* result)
2062 *result = fp_isprime(a);
2068 static int s_is_power_of_two(fp_digit b, int *p)
2072 /* fast return if no power of two */
2073 if ((b==0) || (b & (b-1))) {
2077 for (x = 0; x < DIGIT_BIT; x++) {
2078 if (b == (((fp_digit)1)<<x)) {
2086 /* a/b => cb + d == a */
2087 static int fp_div_d(fp_int *a, fp_digit b, fp_int *c, fp_digit *d)
2094 /* cannot divide by zero */
2100 if (b == 1 || fp_iszero(a) == 1) {
2110 /* power of two ? */
2111 if (s_is_power_of_two(b, &ix) == 1) {
2113 *d = a->dp[0] & ((((fp_digit)1)<<ix) - 1);
2116 fp_div_2d(a, ix, c, NULL);
2121 /* no easy answer [c'est la vie]. Just division */
2127 for (ix = a->used - 1; ix >= 0; ix--) {
2128 w = (w << ((fp_word)DIGIT_BIT)) | ((fp_word)a->dp[ix]);
2131 t = (fp_digit)(w / b);
2132 w -= ((fp_word)t) * ((fp_word)b);
2136 q.dp[ix] = (fp_digit)t;
2152 /* c = a mod b, 0 <= c < b */
2153 static int fp_mod_d(fp_int *a, fp_digit b, fp_digit *c)
2155 return fp_div_d(a, b, NULL, c);
2159 /* Miller-Rabin test of "a" to the base of "b" as described in
2160 * HAC pp. 139 Algorithm 4.24
2162 * Sets result to 0 if definitely composite or 1 if probably prime.
2163 * Randomly the chance of error is no more than 1/4 and often
2166 static void fp_prime_miller_rabin (fp_int * a, fp_int * b, int *result)
2175 if (fp_cmp_d(b, 1) != FP_GT) {
2179 /* get n1 = a - 1 */
2180 fp_init_copy(&n1, a);
2181 fp_sub_d(&n1, 1, &n1);
2183 /* set 2**s * r = n1 */
2184 fp_init_copy(&r, &n1);
2186 /* count the number of least significant bits
2191 /* now divide n - 1 by 2**s */
2192 fp_div_2d (&r, s, &r, NULL);
2194 /* compute y = b**r mod a */
2196 fp_exptmod(b, &r, a, &y);
2198 /* if y != 1 and y != n1 do */
2199 if (fp_cmp_d (&y, 1) != FP_EQ && fp_cmp (&y, &n1) != FP_EQ) {
2201 /* while j <= s-1 and y != n1 */
2202 while ((j <= (s - 1)) && fp_cmp (&y, &n1) != FP_EQ) {
2203 fp_sqrmod (&y, a, &y);
2205 /* if y == 1 then composite */
2206 if (fp_cmp_d (&y, 1) == FP_EQ) {
2212 /* if y != n1 then composite */
2213 if (fp_cmp (&y, &n1) != FP_EQ) {
2218 /* probably prime now */
2224 static const fp_digit primes[256] = {
2225 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
2226 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
2227 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
2228 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
2229 0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
2230 0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
2231 0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
2232 0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
2234 0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
2235 0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
2236 0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
2237 0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
2238 0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
2239 0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
2240 0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
2241 0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
2243 0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
2244 0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
2245 0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
2246 0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
2247 0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
2248 0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
2249 0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
2250 0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
2252 0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
2253 0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
2254 0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
2255 0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
2256 0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
2257 0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
2258 0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
2259 0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
2262 int fp_isprime(fp_int *a)
2268 /* do trial division */
2269 for (r = 0; r < 256; r++) {
2270 fp_mod_d(a, primes[r], &d);
2276 /* now do 8 miller rabins */
2278 for (r = 0; r < 8; r++) {
2279 fp_set(&b, primes[r]);
2280 fp_prime_miller_rabin(a, &b, &res);
2290 void fp_lcm(fp_int *a, fp_int *b, fp_int *c)
2297 if (fp_cmp_mag(a, b) == FP_GT) {
2298 fp_div(a, &t1, &t2, NULL);
2301 fp_div(b, &t1, &t2, NULL);
2307 static const int lnz[16] = {
2308 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
2311 /* Counts the number of lsbs which are zero before the first zero bit */
2312 int fp_cnt_lsb(fp_int *a)
2318 if (fp_iszero(a) == 1) {
2322 /* scan lower digits until non-zero */
2323 for (x = 0; x < a->used && a->dp[x] == 0; x++);
2327 /* now scan this digit until a 1 is found */
2340 void fp_gcd(fp_int *a, fp_int *b, fp_int *c)
2344 /* either zero than gcd is the largest */
2345 if (fp_iszero (a) == 1 && fp_iszero (b) == 0) {
2349 if (fp_iszero (a) == 0 && fp_iszero (b) == 1) {
2354 /* optimized. At this point if a == 0 then
2355 * b must equal zero too
2357 if (fp_iszero (a) == 1) {
2363 if (fp_cmp_mag(a, b) != FP_LT) {
2364 fp_init_copy(&u, a);
2365 fp_init_copy(&v, b);
2367 fp_init_copy(&u, b);
2368 fp_init_copy(&v, a);
2372 while (fp_iszero(&v) == FP_NO) {
2380 #endif /* CYASSL_KEY_GEN */
2383 #if defined(HAVE_ECC) || !defined(NO_PWDBASED)
2385 void fp_add_d(fp_int *a, fp_digit b, fp_int *c)
2392 /* external compatibility */
2393 int mp_add_d(fp_int *a, fp_digit b, fp_int *c)
2399 #endif /* HAVE_ECC || !NO_PWDBASED */
2404 /* chars used in radix conversions */
2405 static const char *fp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
2407 static int fp_read_radix(fp_int *a, const char *str, int radix)
2412 /* make sure the radix is ok */
2413 if (radix < 2 || radix > 64) {
2417 /* if the leading digit is a
2418 * minus set the sign to negative.
2427 /* set the integer to the default of zero */
2430 /* process each digit of the string */
2432 /* if the radix < 36 the conversion is case insensitive
2433 * this allows numbers like 1AB and 1ab to represent the same value
2436 ch = (char) ((radix < 36) ? XTOUPPER(*str) : *str);
2437 for (y = 0; y < 64; y++) {
2438 if (ch == fp_s_rmap[y]) {
2443 /* if the char was found in the map
2444 * and is less than the given radix add it
2445 * to the number, otherwise exit the loop.
2448 fp_mul_d (a, (fp_digit) radix, a);
2449 fp_add_d (a, (fp_digit) y, a);
2456 /* set the sign only if a != 0 */
2457 if (fp_iszero(a) != FP_YES) {
2463 /* fast math conversion */
2464 int mp_read_radix(mp_int *a, const char *str, int radix)
2466 return fp_read_radix(a, str, radix);
2469 /* fast math conversion */
2470 int mp_set(fp_int *a, fp_digit b)
2476 /* fast math conversion */
2477 int mp_sqr(fp_int *A, fp_int *B)
2483 /* fast math conversion */
2484 int mp_montgomery_reduce(fp_int *a, fp_int *m, fp_digit mp)
2486 fp_montgomery_reduce(a, m, mp);
2491 /* fast math conversion */
2492 int mp_montgomery_setup(fp_int *a, fp_digit *rho)
2494 return fp_montgomery_setup(a, rho);
2497 int mp_div_2(fp_int * a, fp_int * b)
2504 int mp_init_copy(fp_int * a, fp_int * b)
2512 #endif /* HAVE_ECC */
2514 #endif /* USE_FAST_MATH */