Mercurial > dropbear
comparison libtommath/bn_s_mp_exptmod.c @ 1733:d529a52b2f7c coverity coverity
merge coverity from main
author | Matt Johnston <matt@ucc.asn.au> |
---|---|
date | Fri, 26 Jun 2020 21:07:34 +0800 |
parents | 1051e4eea25a |
children |
comparison
equal
deleted
inserted
replaced
1643:b59623a64678 | 1733:d529a52b2f7c |
---|---|
1 #include <tommath_private.h> | 1 #include "tommath_private.h" |
2 #ifdef BN_S_MP_EXPTMOD_C | 2 #ifdef BN_S_MP_EXPTMOD_C |
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis | 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 * | 4 /* SPDX-License-Identifier: Unlicense */ |
5 * LibTomMath is a library that provides multiple-precision | 5 |
6 * integer arithmetic as well as number theoretic functionality. | |
7 * | |
8 * The library was designed directly after the MPI library by | |
9 * Michael Fromberger but has been written from scratch with | |
10 * additional optimizations in place. | |
11 * | |
12 * The library is free for all purposes without any express | |
13 * guarantee it works. | |
14 * | |
15 * Tom St Denis, [email protected], http://libtom.org | |
16 */ | |
17 #ifdef MP_LOW_MEM | 6 #ifdef MP_LOW_MEM |
18 #define TAB_SIZE 32 | 7 # define TAB_SIZE 32 |
8 # define MAX_WINSIZE 5 | |
19 #else | 9 #else |
20 #define TAB_SIZE 256 | 10 # define TAB_SIZE 256 |
11 # define MAX_WINSIZE 0 | |
21 #endif | 12 #endif |
22 | 13 |
23 int s_mp_exptmod (mp_int * G, mp_int * X, mp_int * P, mp_int * Y, int redmode) | 14 mp_err s_mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y, int redmode) |
24 { | 15 { |
25 mp_int M[TAB_SIZE], res, mu; | 16 mp_int M[TAB_SIZE], res, mu; |
26 mp_digit buf; | 17 mp_digit buf; |
27 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; | 18 mp_err err; |
28 int (*redux)(mp_int*,mp_int*,mp_int*); | 19 int bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; |
20 mp_err(*redux)(mp_int *x, const mp_int *m, const mp_int *mu); | |
29 | 21 |
30 /* find window size */ | 22 /* find window size */ |
31 x = mp_count_bits (X); | 23 x = mp_count_bits(X); |
32 if (x <= 7) { | 24 if (x <= 7) { |
33 winsize = 2; | 25 winsize = 2; |
34 } else if (x <= 36) { | 26 } else if (x <= 36) { |
35 winsize = 3; | 27 winsize = 3; |
36 } else if (x <= 140) { | 28 } else if (x <= 140) { |
37 winsize = 4; | 29 winsize = 4; |
38 } else if (x <= 450) { | 30 } else if (x <= 450) { |
39 winsize = 5; | 31 winsize = 5; |
40 } else if (x <= 1303) { | 32 } else if (x <= 1303) { |
41 winsize = 6; | 33 winsize = 6; |
42 } else if (x <= 3529) { | 34 } else if (x <= 3529) { |
43 winsize = 7; | 35 winsize = 7; |
44 } else { | 36 } else { |
45 winsize = 8; | 37 winsize = 8; |
46 } | 38 } |
47 | 39 |
48 #ifdef MP_LOW_MEM | 40 winsize = MAX_WINSIZE ? MP_MIN(MAX_WINSIZE, winsize) : winsize; |
49 if (winsize > 5) { | |
50 winsize = 5; | |
51 } | |
52 #endif | |
53 | 41 |
54 /* init M array */ | 42 /* init M array */ |
55 /* init first cell */ | 43 /* init first cell */ |
56 if ((err = mp_init(&M[1])) != MP_OKAY) { | 44 if ((err = mp_init(&M[1])) != MP_OKAY) { |
57 return err; | 45 return err; |
58 } | 46 } |
59 | 47 |
60 /* now init the second half of the array */ | 48 /* now init the second half of the array */ |
61 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { | 49 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { |
62 if ((err = mp_init(&M[x])) != MP_OKAY) { | 50 if ((err = mp_init(&M[x])) != MP_OKAY) { |
63 for (y = 1<<(winsize-1); y < x; y++) { | 51 for (y = 1<<(winsize-1); y < x; y++) { |
64 mp_clear (&M[y]); | 52 mp_clear(&M[y]); |
53 } | |
54 mp_clear(&M[1]); | |
55 return err; | |
65 } | 56 } |
66 mp_clear(&M[1]); | 57 } |
67 return err; | |
68 } | |
69 } | |
70 | 58 |
71 /* create mu, used for Barrett reduction */ | 59 /* create mu, used for Barrett reduction */ |
72 if ((err = mp_init (&mu)) != MP_OKAY) { | 60 if ((err = mp_init(&mu)) != MP_OKAY) goto LBL_M; |
73 goto LBL_M; | |
74 } | |
75 | |
76 if (redmode == 0) { | |
77 if ((err = mp_reduce_setup (&mu, P)) != MP_OKAY) { | |
78 goto LBL_MU; | |
79 } | |
80 redux = mp_reduce; | |
81 } else { | |
82 if ((err = mp_reduce_2k_setup_l (P, &mu)) != MP_OKAY) { | |
83 goto LBL_MU; | |
84 } | |
85 redux = mp_reduce_2k_l; | |
86 } | |
87 | 61 |
88 /* create M table | 62 if (redmode == 0) { |
89 * | 63 if ((err = mp_reduce_setup(&mu, P)) != MP_OKAY) goto LBL_MU; |
90 * The M table contains powers of the base, | 64 redux = mp_reduce; |
91 * e.g. M[x] = G**x mod P | 65 } else { |
92 * | 66 if ((err = mp_reduce_2k_setup_l(P, &mu)) != MP_OKAY) goto LBL_MU; |
93 * The first half of the table is not | 67 redux = mp_reduce_2k_l; |
94 * computed though accept for M[0] and M[1] | 68 } |
95 */ | |
96 if ((err = mp_mod (G, P, &M[1])) != MP_OKAY) { | |
97 goto LBL_MU; | |
98 } | |
99 | 69 |
100 /* compute the value at M[1<<(winsize-1)] by squaring | 70 /* create M table |
101 * M[1] (winsize-1) times | 71 * |
102 */ | 72 * The M table contains powers of the base, |
103 if ((err = mp_copy (&M[1], &M[1 << (winsize - 1)])) != MP_OKAY) { | 73 * e.g. M[x] = G**x mod P |
104 goto LBL_MU; | 74 * |
105 } | 75 * The first half of the table is not |
76 * computed though accept for M[0] and M[1] | |
77 */ | |
78 if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) goto LBL_MU; | |
106 | 79 |
107 for (x = 0; x < (winsize - 1); x++) { | 80 /* compute the value at M[1<<(winsize-1)] by squaring |
108 /* square it */ | 81 * M[1] (winsize-1) times |
109 if ((err = mp_sqr (&M[1 << (winsize - 1)], | 82 */ |
110 &M[1 << (winsize - 1)])) != MP_OKAY) { | 83 if ((err = mp_copy(&M[1], &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU; |
111 goto LBL_MU; | |
112 } | |
113 | 84 |
114 /* reduce modulo P */ | 85 for (x = 0; x < (winsize - 1); x++) { |
115 if ((err = redux (&M[1 << (winsize - 1)], P, &mu)) != MP_OKAY) { | 86 /* square it */ |
116 goto LBL_MU; | 87 if ((err = mp_sqr(&M[(size_t)1 << (winsize - 1)], |
117 } | 88 &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU; |
118 } | |
119 | 89 |
120 /* create upper table, that is M[x] = M[x-1] * M[1] (mod P) | 90 /* reduce modulo P */ |
121 * for x = (2**(winsize - 1) + 1) to (2**winsize - 1) | 91 if ((err = redux(&M[(size_t)1 << (winsize - 1)], P, &mu)) != MP_OKAY) goto LBL_MU; |
122 */ | 92 } |
123 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { | |
124 if ((err = mp_mul (&M[x - 1], &M[1], &M[x])) != MP_OKAY) { | |
125 goto LBL_MU; | |
126 } | |
127 if ((err = redux (&M[x], P, &mu)) != MP_OKAY) { | |
128 goto LBL_MU; | |
129 } | |
130 } | |
131 | 93 |
132 /* setup result */ | 94 /* create upper table, that is M[x] = M[x-1] * M[1] (mod P) |
133 if ((err = mp_init (&res)) != MP_OKAY) { | 95 * for x = (2**(winsize - 1) + 1) to (2**winsize - 1) |
134 goto LBL_MU; | 96 */ |
135 } | 97 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { |
136 mp_set (&res, 1); | 98 if ((err = mp_mul(&M[x - 1], &M[1], &M[x])) != MP_OKAY) goto LBL_MU; |
99 if ((err = redux(&M[x], P, &mu)) != MP_OKAY) goto LBL_MU; | |
100 } | |
137 | 101 |
138 /* set initial mode and bit cnt */ | 102 /* setup result */ |
139 mode = 0; | 103 if ((err = mp_init(&res)) != MP_OKAY) goto LBL_MU; |
140 bitcnt = 1; | 104 mp_set(&res, 1uL); |
141 buf = 0; | |
142 digidx = X->used - 1; | |
143 bitcpy = 0; | |
144 bitbuf = 0; | |
145 | 105 |
146 for (;;) { | 106 /* set initial mode and bit cnt */ |
147 /* grab next digit as required */ | 107 mode = 0; |
148 if (--bitcnt == 0) { | 108 bitcnt = 1; |
149 /* if digidx == -1 we are out of digits */ | 109 buf = 0; |
150 if (digidx == -1) { | 110 digidx = X->used - 1; |
151 break; | 111 bitcpy = 0; |
152 } | 112 bitbuf = 0; |
153 /* read next digit and reset the bitcnt */ | |
154 buf = X->dp[digidx--]; | |
155 bitcnt = (int) DIGIT_BIT; | |
156 } | |
157 | 113 |
158 /* grab the next msb from the exponent */ | 114 for (;;) { |
159 y = (buf >> (mp_digit)(DIGIT_BIT - 1)) & 1; | 115 /* grab next digit as required */ |
160 buf <<= (mp_digit)1; | 116 if (--bitcnt == 0) { |
161 | 117 /* if digidx == -1 we are out of digits */ |
162 /* if the bit is zero and mode == 0 then we ignore it | 118 if (digidx == -1) { |
163 * These represent the leading zero bits before the first 1 bit | 119 break; |
164 * in the exponent. Technically this opt is not required but it | 120 } |
165 * does lower the # of trivial squaring/reductions used | 121 /* read next digit and reset the bitcnt */ |
166 */ | 122 buf = X->dp[digidx--]; |
167 if ((mode == 0) && (y == 0)) { | 123 bitcnt = (int)MP_DIGIT_BIT; |
168 continue; | |
169 } | |
170 | |
171 /* if the bit is zero and mode == 1 then we square */ | |
172 if ((mode == 1) && (y == 0)) { | |
173 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { | |
174 goto LBL_RES; | |
175 } | |
176 if ((err = redux (&res, P, &mu)) != MP_OKAY) { | |
177 goto LBL_RES; | |
178 } | |
179 continue; | |
180 } | |
181 | |
182 /* else we add it to the window */ | |
183 bitbuf |= (y << (winsize - ++bitcpy)); | |
184 mode = 2; | |
185 | |
186 if (bitcpy == winsize) { | |
187 /* ok window is filled so square as required and multiply */ | |
188 /* square first */ | |
189 for (x = 0; x < winsize; x++) { | |
190 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { | |
191 goto LBL_RES; | |
192 } | |
193 if ((err = redux (&res, P, &mu)) != MP_OKAY) { | |
194 goto LBL_RES; | |
195 } | |
196 } | 124 } |
197 | 125 |
198 /* then multiply */ | 126 /* grab the next msb from the exponent */ |
199 if ((err = mp_mul (&res, &M[bitbuf], &res)) != MP_OKAY) { | 127 y = (buf >> (mp_digit)(MP_DIGIT_BIT - 1)) & 1uL; |
200 goto LBL_RES; | 128 buf <<= (mp_digit)1; |
201 } | 129 |
202 if ((err = redux (&res, P, &mu)) != MP_OKAY) { | 130 /* if the bit is zero and mode == 0 then we ignore it |
203 goto LBL_RES; | 131 * These represent the leading zero bits before the first 1 bit |
132 * in the exponent. Technically this opt is not required but it | |
133 * does lower the # of trivial squaring/reductions used | |
134 */ | |
135 if ((mode == 0) && (y == 0)) { | |
136 continue; | |
204 } | 137 } |
205 | 138 |
206 /* empty window and reset */ | 139 /* if the bit is zero and mode == 1 then we square */ |
207 bitcpy = 0; | 140 if ((mode == 1) && (y == 0)) { |
208 bitbuf = 0; | 141 if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
209 mode = 1; | 142 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
210 } | 143 continue; |
211 } | |
212 | |
213 /* if bits remain then square/multiply */ | |
214 if ((mode == 2) && (bitcpy > 0)) { | |
215 /* square then multiply if the bit is set */ | |
216 for (x = 0; x < bitcpy; x++) { | |
217 if ((err = mp_sqr (&res, &res)) != MP_OKAY) { | |
218 goto LBL_RES; | |
219 } | |
220 if ((err = redux (&res, P, &mu)) != MP_OKAY) { | |
221 goto LBL_RES; | |
222 } | 144 } |
223 | 145 |
224 bitbuf <<= 1; | 146 /* else we add it to the window */ |
225 if ((bitbuf & (1 << winsize)) != 0) { | 147 bitbuf |= (y << (winsize - ++bitcpy)); |
226 /* then multiply */ | 148 mode = 2; |
227 if ((err = mp_mul (&res, &M[1], &res)) != MP_OKAY) { | 149 |
228 goto LBL_RES; | 150 if (bitcpy == winsize) { |
229 } | 151 /* ok window is filled so square as required and multiply */ |
230 if ((err = redux (&res, P, &mu)) != MP_OKAY) { | 152 /* square first */ |
231 goto LBL_RES; | 153 for (x = 0; x < winsize; x++) { |
232 } | 154 if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
155 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; | |
156 } | |
157 | |
158 /* then multiply */ | |
159 if ((err = mp_mul(&res, &M[bitbuf], &res)) != MP_OKAY) goto LBL_RES; | |
160 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; | |
161 | |
162 /* empty window and reset */ | |
163 bitcpy = 0; | |
164 bitbuf = 0; | |
165 mode = 1; | |
233 } | 166 } |
234 } | 167 } |
235 } | |
236 | 168 |
237 mp_exch (&res, Y); | 169 /* if bits remain then square/multiply */ |
238 err = MP_OKAY; | 170 if ((mode == 2) && (bitcpy > 0)) { |
239 LBL_RES:mp_clear (&res); | 171 /* square then multiply if the bit is set */ |
240 LBL_MU:mp_clear (&mu); | 172 for (x = 0; x < bitcpy; x++) { |
173 if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; | |
174 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; | |
175 | |
176 bitbuf <<= 1; | |
177 if ((bitbuf & (1 << winsize)) != 0) { | |
178 /* then multiply */ | |
179 if ((err = mp_mul(&res, &M[1], &res)) != MP_OKAY) goto LBL_RES; | |
180 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; | |
181 } | |
182 } | |
183 } | |
184 | |
185 mp_exch(&res, Y); | |
186 err = MP_OKAY; | |
187 LBL_RES: | |
188 mp_clear(&res); | |
189 LBL_MU: | |
190 mp_clear(&mu); | |
241 LBL_M: | 191 LBL_M: |
242 mp_clear(&M[1]); | 192 mp_clear(&M[1]); |
243 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { | 193 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { |
244 mp_clear (&M[x]); | 194 mp_clear(&M[x]); |
245 } | 195 } |
246 return err; | 196 return err; |
247 } | 197 } |
248 #endif | 198 #endif |
249 | |
250 /* ref: $Format:%D$ */ | |
251 /* git commit: $Format:%H$ */ | |
252 /* commit time: $Format:%ai$ */ |