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