annotate bn_mp_exptmod_fast.c @ 1:22d5cf7d4b1a libtommath

Renaming branch
author Matt Johnston <matt@ucc.asn.au>
date Mon, 31 May 2004 18:23:46 +0000
parents
children d29b64170cf0
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
1 /* LibTomMath, multiple-precision integer library -- Tom St Denis
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
2 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
3 * LibTomMath is a library that provides multiple-precision
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
4 * integer arithmetic as well as number theoretic functionality.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
5 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
6 * The library was designed directly after the MPI library by
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
7 * Michael Fromberger but has been written from scratch with
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
8 * additional optimizations in place.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
9 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
10 * The library is free for all purposes without any express
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
11 * guarantee it works.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
12 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
13 * Tom St Denis, [email protected], http://math.libtomcrypt.org
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
14 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
15 #include <tommath.h>
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
16
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
17 /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
18 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
19 * Uses a left-to-right k-ary sliding window to compute the modular exponentiation.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
20 * The value of k changes based on the size of the exponent.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
21 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
22 * Uses Montgomery or Diminished Radix reduction [whichever appropriate]
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
23 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
24
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
25 #ifdef MP_LOW_MEM
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
26 #define TAB_SIZE 32
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
27 #else
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
28 #define TAB_SIZE 256
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
29 #endif
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
30
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
31 int
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
32 mp_exptmod_fast (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode)
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
33 {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
34 mp_int M[TAB_SIZE], res;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
35 mp_digit buf, mp;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
36 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
37
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
38 /* use a pointer to the reduction algorithm. This allows us to use
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
39 * one of many reduction algorithms without modding the guts of
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
40 * the code with if statements everywhere.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
41 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
42 int (*redux)(mp_int*,mp_int*,mp_digit);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
43
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
44 /* find window size */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
45 x = mp_count_bits (X);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
46 if (x <= 7) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
47 winsize = 2;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
48 } else if (x <= 36) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
49 winsize = 3;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
50 } else if (x <= 140) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
51 winsize = 4;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
52 } else if (x <= 450) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
53 winsize = 5;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
54 } else if (x <= 1303) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
55 winsize = 6;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
56 } else if (x <= 3529) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
57 winsize = 7;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
58 } else {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
59 winsize = 8;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
60 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
61
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
62 #ifdef MP_LOW_MEM
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
63 if (winsize > 5) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
64 winsize = 5;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
65 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
66 #endif
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
67
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
68 /* init M array */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
69 /* init first cell */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
70 if ((err = mp_init(&M[1])) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
71 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
72 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
73
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
74 /* now init the second half of the array */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
75 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
76 if ((err = mp_init(&M[x])) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
77 for (y = 1<<(winsize-1); y < x; y++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
78 mp_clear (&M[y]);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
79 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
80 mp_clear(&M[1]);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
81 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
82 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
83 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
84
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
85 /* determine and setup reduction code */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
86 if (redmode == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
87 /* now setup montgomery */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
88 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
89 goto __M;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
90 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
91
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
92 /* automatically pick the comba one if available (saves quite a few calls/ifs) */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
93 if (((P->used * 2 + 1) < MP_WARRAY) &&
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
94 P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
95 redux = fast_mp_montgomery_reduce;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
96 } else {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
97 /* use slower baseline Montgomery method */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
98 redux = mp_montgomery_reduce;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
99 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
100 } else if (redmode == 1) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
101 /* setup DR reduction for moduli of the form B**k - b */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
102 mp_dr_setup(P, &mp);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
103 redux = mp_dr_reduce;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
104 } else {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
105 /* setup DR reduction for moduli of the form 2**k - b */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
106 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
107 goto __M;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
108 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
109 redux = mp_reduce_2k;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
110 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
111
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
112 /* setup result */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
113 if ((err = mp_init (&res)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
114 goto __M;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
115 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
116
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
117 /* create M table
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
118 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
119 * The M table contains powers of the input base, e.g. M[x] = G^x mod P
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
120 *
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
121 * The first half of the table is not computed though accept for M[0] and M[1]
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
122 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
123
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
124 if (redmode == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
125 /* now we need R mod m */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
126 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
127 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
128 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
129
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
130 /* now set M[1] to G * R mod m */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
131 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
132 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
133 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
134 } else {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
135 mp_set(&res, 1);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
136 if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
137 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
138 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
139 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
140
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
141 /* compute the value at M[1<<(winsize-1)] by squaring M[1] (winsize-1) times */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
142 if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
143 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
144 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
145
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
146 for (x = 0; x < (winsize - 1); x++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
147 if ((err = mp_sqr (&M[1 << (winsize - 1)], &M[1 << (winsize - 1)])) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
148 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
149 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
150 if ((err = redux (&M[1 << (winsize - 1)], P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
151 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
152 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
153 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
154
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
155 /* create upper table */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
156 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
157 if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
158 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
159 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
160 if ((err = redux (&M[x], P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
161 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
162 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
163 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
164
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
165 /* set initial mode and bit cnt */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
166 mode = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
167 bitcnt = 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
168 buf = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
169 digidx = X->used - 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
170 bitcpy = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
171 bitbuf = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
172
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
173 for (;;) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
174 /* grab next digit as required */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
175 if (--bitcnt == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
176 /* if digidx == -1 we are out of digits so break */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
177 if (digidx == -1) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
178 break;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
179 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
180 /* read next digit and reset bitcnt */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
181 buf = X->dp[digidx--];
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
182 bitcnt = (int)DIGIT_BIT;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
183 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
184
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
185 /* grab the next msb from the exponent */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
186 y = (mp_digit)(buf >> (DIGIT_BIT - 1)) & 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
187 buf <<= (mp_digit)1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
188
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
189 /* if the bit is zero and mode == 0 then we ignore it
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
190 * These represent the leading zero bits before the first 1 bit
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
191 * in the exponent. Technically this opt is not required but it
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
192 * does lower the # of trivial squaring/reductions used
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
193 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
194 if (mode == 0 && y == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
195 continue;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
196 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
197
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
198 /* if the bit is zero and mode == 1 then we square */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
199 if (mode == 1 && y == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
200 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
201 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
202 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
203 if ((err = redux (&res, P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
204 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
205 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
206 continue;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
207 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
208
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
209 /* else we add it to the window */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
210 bitbuf |= (y << (winsize - ++bitcpy));
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
211 mode = 2;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
212
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
213 if (bitcpy == winsize) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
214 /* ok window is filled so square as required and multiply */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
215 /* square first */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
216 for (x = 0; x < winsize; x++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
217 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
218 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
219 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
220 if ((err = redux (&res, P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
221 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
222 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
223 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
224
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
225 /* then multiply */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
226 if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
227 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
228 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
229 if ((err = redux (&res, P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
230 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
231 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
232
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
233 /* empty window and reset */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
234 bitcpy = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
235 bitbuf = 0;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
236 mode = 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
237 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
238 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
239
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
240 /* if bits remain then square/multiply */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
241 if (mode == 2 && bitcpy > 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
242 /* square then multiply if the bit is set */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
243 for (x = 0; x < bitcpy; x++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
244 if ((err = mp_sqr (&res, &res)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
245 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
246 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
247 if ((err = redux (&res, P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
248 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
249 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
250
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
251 /* get next bit of the window */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
252 bitbuf <<= 1;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
253 if ((bitbuf & (1 << winsize)) != 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
254 /* then multiply */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
255 if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
256 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
257 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
258 if ((err = redux (&res, P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
259 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
260 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
261 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
262 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
263 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
264
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
265 if (redmode == 0) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
266 /* fixup result if Montgomery reduction is used
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
267 * recall that any value in a Montgomery system is
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
268 * actually multiplied by R mod n. So we have
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
269 * to reduce one more time to cancel out the factor
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
270 * of R.
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
271 */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
272 if ((err = mp_montgomery_reduce (&res, P, mp)) != MP_OKAY) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
273 goto __RES;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
274 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
275 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
276
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
277 /* swap res with Y */
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
278 mp_exch (&res, Y);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
279 err = MP_OKAY;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
280 __RES:mp_clear (&res);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
281 __M:
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
282 mp_clear(&M[1]);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
283 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
284 mp_clear (&M[x]);
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
285 }
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
286 return err;
22d5cf7d4b1a Renaming branch
Matt Johnston <matt@ucc.asn.au>
parents:
diff changeset
287 }