Mercurial > dropbear

comparison bn_mp_exptmod_fast.c @ 142:d29b64170cf0 libtommath-orig

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
import of libtommath 0.32
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:33:56 +0000
parents 86e0b50a9b58
children d8254fc979e9
comparison
equal deleted inserted replaced
19:e1037a1e12e7 142:d29b64170cf0
1 #include <tommath.h>
2 #ifdef BN_MP_EXPTMOD_FAST_C
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2 * 4 *
3 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
4 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
5 * 7 *
10 * The library is free for all purposes without any express 12 * The library is free for all purposes without any express
11 * guarantee it works. 13 * guarantee it works.
12 * 14 *
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org 15 * Tom St Denis, [email protected], http://math.libtomcrypt.org
14 */ 16 */
15 #include <tommath.h>
16 17
17 /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85 18 /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85
18 * 19 *
19 * Uses a left-to-right k-ary sliding window to compute the modular exponentiation. 20 * Uses a left-to-right k-ary sliding window to compute the modular exponentiation.
20 * The value of k changes based on the size of the exponent. 21 * The value of k changes based on the size of the exponent.
82 } 83 }
83 } 84 }
84 85
85 /* determine and setup reduction code */ 86 /* determine and setup reduction code */
86 if (redmode == 0) { 87 if (redmode == 0) {
88 #ifdef BN_MP_MONTGOMERY_SETUP_C
87 /* now setup montgomery */ 89 /* now setup montgomery */
88 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) { 90 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) {
89 goto __M; 91 goto __M;
90 } 92 }
93 #else
94 err = MP_VAL;
95 goto __M;
96 #endif
91 97
92 /* automatically pick the comba one if available (saves quite a few calls/ifs) */ 98 /* automatically pick the comba one if available (saves quite a few calls/ifs) */
99 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
93 if (((P->used * 2 + 1) < MP_WARRAY) && 100 if (((P->used * 2 + 1) < MP_WARRAY) &&
94 P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 101 P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
95 redux = fast_mp_montgomery_reduce; 102 redux = fast_mp_montgomery_reduce;
96 } else { 103 } else
104 #endif
105 {
106 #ifdef BN_MP_MONTGOMERY_REDUCE_C
97 /* use slower baseline Montgomery method */ 107 /* use slower baseline Montgomery method */
98 redux = mp_montgomery_reduce; 108 redux = mp_montgomery_reduce;
109 #else
110 err = MP_VAL;
111 goto __M;
112 #endif
99 } 113 }
100 } else if (redmode == 1) { 114 } else if (redmode == 1) {
115 #if defined(BN_MP_DR_SETUP_C) && defined(BN_MP_DR_REDUCE_C)
101 /* setup DR reduction for moduli of the form B**k - b */ 116 /* setup DR reduction for moduli of the form B**k - b */
102 mp_dr_setup(P, &mp); 117 mp_dr_setup(P, &mp);
103 redux = mp_dr_reduce; 118 redux = mp_dr_reduce;
119 #else
120 err = MP_VAL;
121 goto __M;
122 #endif
104 } else { 123 } else {
124 #if defined(BN_MP_REDUCE_2K_SETUP_C) && defined(BN_MP_REDUCE_2K_C)
105 /* setup DR reduction for moduli of the form 2**k - b */ 125 /* setup DR reduction for moduli of the form 2**k - b */
106 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) { 126 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) {
107 goto __M; 127 goto __M;
108 } 128 }
109 redux = mp_reduce_2k; 129 redux = mp_reduce_2k;
130 #else
131 err = MP_VAL;
132 goto __M;
133 #endif
110 } 134 }
111 135
112 /* setup result */ 136 /* setup result */
113 if ((err = mp_init (&res)) != MP_OKAY) { 137 if ((err = mp_init (&res)) != MP_OKAY) {
114 goto __M; 138 goto __M;
115 } 139 }
116 140
117 /* create M table 141 /* create M table
118 * 142 *
119 * The M table contains powers of the input base, e.g. M[x] = G^x mod P 143
120 * 144 *
121 * The first half of the table is not computed though accept for M[0] and M[1] 145 * The first half of the table is not computed though accept for M[0] and M[1]
122 */ 146 */
123 147
124 if (redmode == 0) { 148 if (redmode == 0) {
149 #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C
125 /* now we need R mod m */ 150 /* now we need R mod m */
126 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) { 151 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) {
127 goto __RES; 152 goto __RES;
128 } 153 }
154 #else
155 err = MP_VAL;
156 goto __RES;
157 #endif
129 158
130 /* now set M[1] to G * R mod m */ 159 /* now set M[1] to G * R mod m */
131 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) { 160 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) {
132 goto __RES; 161 goto __RES;
133 } 162 }
267 * recall that any value in a Montgomery system is 296 * recall that any value in a Montgomery system is
268 * actually multiplied by R mod n. So we have 297 * actually multiplied by R mod n. So we have
269 * to reduce one more time to cancel out the factor 298 * to reduce one more time to cancel out the factor
270 * of R. 299 * of R.
271 */ 300 */
272 if ((err = mp_montgomery_reduce (&res, P, mp)) != MP_OKAY) { 301 if ((err = redux(&res, P, mp)) != MP_OKAY) {
273 goto __RES; 302 goto __RES;
274 } 303 }
275 } 304 }
276 305
277 /* swap res with Y */ 306 /* swap res with Y */
283 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { 312 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
284 mp_clear (&M[x]); 313 mp_clear (&M[x]);
285 } 314 }
286 return err; 315 return err;
287 } 316 }
317 #endif
318