Mercurial > dropbear

comparison libtommath/bn_s_mp_exptmod.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 */