Mercurial > dropbear
comparison libtommath/bn_s_mp_exptmod.c @ 1692:1051e4eea25a
Update LibTomMath to 1.2.0 (#84)
* update C files
* update other files
* update headers
* update makefiles
* remove mp_set/get_double()
* use ltm 1.2.0 API
* update ltm_desc
* use bundled tommath if system-tommath is too old
* XMALLOC etc. were changed to MP_MALLOC etc.
author | Steffen Jaeckel <s@jaeckel.eu> |
---|---|
date | Tue, 26 May 2020 17:36:47 +0200 |
parents | f52919ffd3b1 |
children |
comparison
equal
deleted
inserted
replaced
1691:2d3745d58843 | 1692:1051e4eea25a |
---|---|
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 | |
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 * SPDX-License-Identifier: Unlicense | |
13 */ | |
14 | 5 |
15 #ifdef MP_LOW_MEM | 6 #ifdef MP_LOW_MEM |
16 # define TAB_SIZE 32 | 7 # define TAB_SIZE 32 |
8 # define MAX_WINSIZE 5 | |
17 #else | 9 #else |
18 # define TAB_SIZE 256 | 10 # define TAB_SIZE 256 |
11 # define MAX_WINSIZE 0 | |
19 #endif | 12 #endif |
20 | 13 |
21 int s_mp_exptmod(const mp_int *G, const mp_int *X, const 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) |
22 { | 15 { |
23 mp_int M[TAB_SIZE], res, mu; | 16 mp_int M[TAB_SIZE], res, mu; |
24 mp_digit buf; | 17 mp_digit buf; |
25 int err, bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; | 18 mp_err err; |
26 int (*redux)(mp_int *x, const mp_int *m, const mp_int *mu); | 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); | |
27 | 21 |
28 /* find window size */ | 22 /* find window size */ |
29 x = mp_count_bits(X); | 23 x = mp_count_bits(X); |
30 if (x <= 7) { | 24 if (x <= 7) { |
31 winsize = 2; | 25 winsize = 2; |
41 winsize = 7; | 35 winsize = 7; |
42 } else { | 36 } else { |
43 winsize = 8; | 37 winsize = 8; |
44 } | 38 } |
45 | 39 |
46 #ifdef MP_LOW_MEM | 40 winsize = MAX_WINSIZE ? MP_MIN(MAX_WINSIZE, winsize) : winsize; |
47 if (winsize > 5) { | |
48 winsize = 5; | |
49 } | |
50 #endif | |
51 | 41 |
52 /* init M array */ | 42 /* init M array */ |
53 /* init first cell */ | 43 /* init first cell */ |
54 if ((err = mp_init(&M[1])) != MP_OKAY) { | 44 if ((err = mp_init(&M[1])) != MP_OKAY) { |
55 return err; | 45 return err; |
65 return err; | 55 return err; |
66 } | 56 } |
67 } | 57 } |
68 | 58 |
69 /* create mu, used for Barrett reduction */ | 59 /* create mu, used for Barrett reduction */ |
70 if ((err = mp_init(&mu)) != MP_OKAY) { | 60 if ((err = mp_init(&mu)) != MP_OKAY) goto LBL_M; |
71 goto LBL_M; | |
72 } | |
73 | 61 |
74 if (redmode == 0) { | 62 if (redmode == 0) { |
75 if ((err = mp_reduce_setup(&mu, P)) != MP_OKAY) { | 63 if ((err = mp_reduce_setup(&mu, P)) != MP_OKAY) goto LBL_MU; |
76 goto LBL_MU; | |
77 } | |
78 redux = mp_reduce; | 64 redux = mp_reduce; |
79 } else { | 65 } else { |
80 if ((err = mp_reduce_2k_setup_l(P, &mu)) != MP_OKAY) { | 66 if ((err = mp_reduce_2k_setup_l(P, &mu)) != MP_OKAY) goto LBL_MU; |
81 goto LBL_MU; | |
82 } | |
83 redux = mp_reduce_2k_l; | 67 redux = mp_reduce_2k_l; |
84 } | 68 } |
85 | 69 |
86 /* create M table | 70 /* create M table |
87 * | 71 * |
89 * e.g. M[x] = G**x mod P | 73 * e.g. M[x] = G**x mod P |
90 * | 74 * |
91 * The first half of the table is not | 75 * The first half of the table is not |
92 * computed though accept for M[0] and M[1] | 76 * computed though accept for M[0] and M[1] |
93 */ | 77 */ |
94 if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) { | 78 if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) goto LBL_MU; |
95 goto LBL_MU; | |
96 } | |
97 | 79 |
98 /* compute the value at M[1<<(winsize-1)] by squaring | 80 /* compute the value at M[1<<(winsize-1)] by squaring |
99 * M[1] (winsize-1) times | 81 * M[1] (winsize-1) times |
100 */ | 82 */ |
101 if ((err = mp_copy(&M[1], &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) { | 83 if ((err = mp_copy(&M[1], &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU; |
102 goto LBL_MU; | |
103 } | |
104 | 84 |
105 for (x = 0; x < (winsize - 1); x++) { | 85 for (x = 0; x < (winsize - 1); x++) { |
106 /* square it */ | 86 /* square it */ |
107 if ((err = mp_sqr(&M[(size_t)1 << (winsize - 1)], | 87 if ((err = mp_sqr(&M[(size_t)1 << (winsize - 1)], |
108 &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) { | 88 &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU; |
109 goto LBL_MU; | |
110 } | |
111 | 89 |
112 /* reduce modulo P */ | 90 /* reduce modulo P */ |
113 if ((err = redux(&M[(size_t)1 << (winsize - 1)], P, &mu)) != MP_OKAY) { | 91 if ((err = redux(&M[(size_t)1 << (winsize - 1)], P, &mu)) != MP_OKAY) goto LBL_MU; |
114 goto LBL_MU; | |
115 } | |
116 } | 92 } |
117 | 93 |
118 /* create upper table, that is M[x] = M[x-1] * M[1] (mod P) | 94 /* 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) | 95 * for x = (2**(winsize - 1) + 1) to (2**winsize - 1) |
120 */ | 96 */ |
121 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { | 97 for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { |
122 if ((err = mp_mul(&M[x - 1], &M[1], &M[x])) != MP_OKAY) { | 98 if ((err = mp_mul(&M[x - 1], &M[1], &M[x])) != MP_OKAY) goto LBL_MU; |
123 goto LBL_MU; | 99 if ((err = redux(&M[x], P, &mu)) != MP_OKAY) goto LBL_MU; |
124 } | |
125 if ((err = redux(&M[x], P, &mu)) != MP_OKAY) { | |
126 goto LBL_MU; | |
127 } | |
128 } | 100 } |
129 | 101 |
130 /* setup result */ | 102 /* setup result */ |
131 if ((err = mp_init(&res)) != MP_OKAY) { | 103 if ((err = mp_init(&res)) != MP_OKAY) goto LBL_MU; |
132 goto LBL_MU; | |
133 } | |
134 mp_set(&res, 1uL); | 104 mp_set(&res, 1uL); |
135 | 105 |
136 /* set initial mode and bit cnt */ | 106 /* set initial mode and bit cnt */ |
137 mode = 0; | 107 mode = 0; |
138 bitcnt = 1; | 108 bitcnt = 1; |
148 if (digidx == -1) { | 118 if (digidx == -1) { |
149 break; | 119 break; |
150 } | 120 } |
151 /* read next digit and reset the bitcnt */ | 121 /* read next digit and reset the bitcnt */ |
152 buf = X->dp[digidx--]; | 122 buf = X->dp[digidx--]; |
153 bitcnt = (int)DIGIT_BIT; | 123 bitcnt = (int)MP_DIGIT_BIT; |
154 } | 124 } |
155 | 125 |
156 /* grab the next msb from the exponent */ | 126 /* grab the next msb from the exponent */ |
157 y = (buf >> (mp_digit)(DIGIT_BIT - 1)) & 1; | 127 y = (buf >> (mp_digit)(MP_DIGIT_BIT - 1)) & 1uL; |
158 buf <<= (mp_digit)1; | 128 buf <<= (mp_digit)1; |
159 | 129 |
160 /* if the bit is zero and mode == 0 then we ignore it | 130 /* if the bit is zero and mode == 0 then we ignore it |
161 * These represent the leading zero bits before the first 1 bit | 131 * These represent the leading zero bits before the first 1 bit |
162 * in the exponent. Technically this opt is not required but it | 132 * in the exponent. Technically this opt is not required but it |
166 continue; | 136 continue; |
167 } | 137 } |
168 | 138 |
169 /* if the bit is zero and mode == 1 then we square */ | 139 /* if the bit is zero and mode == 1 then we square */ |
170 if ((mode == 1) && (y == 0)) { | 140 if ((mode == 1) && (y == 0)) { |
171 if ((err = mp_sqr(&res, &res)) != MP_OKAY) { | 141 if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
172 goto LBL_RES; | 142 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
173 } | |
174 if ((err = redux(&res, P, &mu)) != MP_OKAY) { | |
175 goto LBL_RES; | |
176 } | |
177 continue; | 143 continue; |
178 } | 144 } |
179 | 145 |
180 /* else we add it to the window */ | 146 /* else we add it to the window */ |
181 bitbuf |= (y << (winsize - ++bitcpy)); | 147 bitbuf |= (y << (winsize - ++bitcpy)); |
183 | 149 |
184 if (bitcpy == winsize) { | 150 if (bitcpy == winsize) { |
185 /* ok window is filled so square as required and multiply */ | 151 /* ok window is filled so square as required and multiply */ |
186 /* square first */ | 152 /* square first */ |
187 for (x = 0; x < winsize; x++) { | 153 for (x = 0; x < winsize; x++) { |
188 if ((err = mp_sqr(&res, &res)) != MP_OKAY) { | 154 if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
189 goto LBL_RES; | 155 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
190 } | |
191 if ((err = redux(&res, P, &mu)) != MP_OKAY) { | |
192 goto LBL_RES; | |
193 } | |
194 } | 156 } |
195 | 157 |
196 /* then multiply */ | 158 /* then multiply */ |
197 if ((err = mp_mul(&res, &M[bitbuf], &res)) != MP_OKAY) { | 159 if ((err = mp_mul(&res, &M[bitbuf], &res)) != MP_OKAY) goto LBL_RES; |
198 goto LBL_RES; | 160 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
199 } | |
200 if ((err = redux(&res, P, &mu)) != MP_OKAY) { | |
201 goto LBL_RES; | |
202 } | |
203 | 161 |
204 /* empty window and reset */ | 162 /* empty window and reset */ |
205 bitcpy = 0; | 163 bitcpy = 0; |
206 bitbuf = 0; | 164 bitbuf = 0; |
207 mode = 1; | 165 mode = 1; |
210 | 168 |
211 /* if bits remain then square/multiply */ | 169 /* if bits remain then square/multiply */ |
212 if ((mode == 2) && (bitcpy > 0)) { | 170 if ((mode == 2) && (bitcpy > 0)) { |
213 /* square then multiply if the bit is set */ | 171 /* square then multiply if the bit is set */ |
214 for (x = 0; x < bitcpy; x++) { | 172 for (x = 0; x < bitcpy; x++) { |
215 if ((err = mp_sqr(&res, &res)) != MP_OKAY) { | 173 if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
216 goto LBL_RES; | 174 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
217 } | |
218 if ((err = redux(&res, P, &mu)) != MP_OKAY) { | |
219 goto LBL_RES; | |
220 } | |
221 | 175 |
222 bitbuf <<= 1; | 176 bitbuf <<= 1; |
223 if ((bitbuf & (1 << winsize)) != 0) { | 177 if ((bitbuf & (1 << winsize)) != 0) { |
224 /* then multiply */ | 178 /* then multiply */ |
225 if ((err = mp_mul(&res, &M[1], &res)) != MP_OKAY) { | 179 if ((err = mp_mul(&res, &M[1], &res)) != MP_OKAY) goto LBL_RES; |
226 goto LBL_RES; | 180 if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
227 } | |
228 if ((err = redux(&res, P, &mu)) != MP_OKAY) { | |
229 goto LBL_RES; | |
230 } | |
231 } | 181 } |
232 } | 182 } |
233 } | 183 } |
234 | 184 |
235 mp_exch(&res, Y); | 185 mp_exch(&res, Y); |
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: HEAD -> master, tag: v1.1.0 */ | |
251 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */ | |
252 /* commit time: 2019-01-28 20:32:32 +0100 */ |