/src/dropbear/libtommath/bn_s_mp_exptmod.c
Line | Count | Source (jump to first uncovered line) |
1 | | #include "tommath_private.h" |
2 | | #ifdef BN_S_MP_EXPTMOD_C |
3 | | /* LibTomMath, multiple-precision integer library -- Tom St Denis */ |
4 | | /* SPDX-License-Identifier: Unlicense */ |
5 | | |
6 | | #ifdef MP_LOW_MEM |
7 | | # define TAB_SIZE 32 |
8 | | # define MAX_WINSIZE 5 |
9 | | #else |
10 | | # define TAB_SIZE 256 |
11 | 465 | # define MAX_WINSIZE 0 |
12 | | #endif |
13 | | |
14 | | mp_err s_mp_exptmod(const mp_int *G, const mp_int *X, const mp_int *P, mp_int *Y, int redmode) |
15 | 465 | { |
16 | 465 | mp_int M[TAB_SIZE], res, mu; |
17 | 465 | mp_digit buf; |
18 | 465 | mp_err err; |
19 | 465 | int bitbuf, bitcpy, bitcnt, mode, digidx, x, y, winsize; |
20 | 465 | mp_err(*redux)(mp_int *x, const mp_int *m, const mp_int *mu); |
21 | | |
22 | | /* find window size */ |
23 | 465 | x = mp_count_bits(X); |
24 | 465 | if (x <= 7) { |
25 | 126 | winsize = 2; |
26 | 339 | } else if (x <= 36) { |
27 | 51 | winsize = 3; |
28 | 288 | } else if (x <= 140) { |
29 | 159 | winsize = 4; |
30 | 159 | } else if (x <= 450) { |
31 | 129 | winsize = 5; |
32 | 129 | } else if (x <= 1303) { |
33 | 0 | winsize = 6; |
34 | 0 | } else if (x <= 3529) { |
35 | 0 | winsize = 7; |
36 | 0 | } else { |
37 | 0 | winsize = 8; |
38 | 0 | } |
39 | | |
40 | 465 | winsize = MAX_WINSIZE ? MP_MIN(MAX_WINSIZE, winsize) : winsize; |
41 | | |
42 | | /* init M array */ |
43 | | /* init first cell */ |
44 | 465 | if ((err = mp_init(&M[1])) != MP_OKAY) { |
45 | 0 | return err; |
46 | 0 | } |
47 | | |
48 | | /* now init the second half of the array */ |
49 | 4.25k | for (x = 1<<(winsize-1); x < (1 << winsize); x++) { |
50 | 3.79k | if ((err = mp_init(&M[x])) != MP_OKAY) { |
51 | 0 | for (y = 1<<(winsize-1); y < x; y++) { |
52 | 0 | mp_clear(&M[y]); |
53 | 0 | } |
54 | 0 | mp_clear(&M[1]); |
55 | 0 | return err; |
56 | 0 | } |
57 | 3.79k | } |
58 | | |
59 | | /* create mu, used for Barrett reduction */ |
60 | 465 | if ((err = mp_init(&mu)) != MP_OKAY) goto LBL_M; |
61 | | |
62 | 465 | if (redmode == 0) { |
63 | 335 | if ((err = mp_reduce_setup(&mu, P)) != MP_OKAY) goto LBL_MU; |
64 | 335 | redux = mp_reduce; |
65 | 335 | } else { |
66 | 130 | if ((err = mp_reduce_2k_setup_l(P, &mu)) != MP_OKAY) goto LBL_MU; |
67 | 130 | redux = mp_reduce_2k_l; |
68 | 130 | } |
69 | | |
70 | | /* create M table |
71 | | * |
72 | | * The M table contains powers of the base, |
73 | | * e.g. M[x] = G**x mod P |
74 | | * |
75 | | * The first half of the table is not |
76 | | * computed though accept for M[0] and M[1] |
77 | | */ |
78 | 465 | if ((err = mp_mod(G, P, &M[1])) != MP_OKAY) goto LBL_MU; |
79 | | |
80 | | /* compute the value at M[1<<(winsize-1)] by squaring |
81 | | * M[1] (winsize-1) times |
82 | | */ |
83 | 465 | if ((err = mp_copy(&M[1], &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU; |
84 | | |
85 | 1.68k | for (x = 0; x < (winsize - 1); x++) { |
86 | | /* square it */ |
87 | 1.22k | if ((err = mp_sqr(&M[(size_t)1 << (winsize - 1)], |
88 | 1.22k | &M[(size_t)1 << (winsize - 1)])) != MP_OKAY) goto LBL_MU; |
89 | | |
90 | | /* reduce modulo P */ |
91 | 1.22k | if ((err = redux(&M[(size_t)1 << (winsize - 1)], P, &mu)) != MP_OKAY) goto LBL_MU; |
92 | 1.22k | } |
93 | | |
94 | | /* create upper table, that is M[x] = M[x-1] * M[1] (mod P) |
95 | | * for x = (2**(winsize - 1) + 1) to (2**winsize - 1) |
96 | | */ |
97 | 3.79k | for (x = (1 << (winsize - 1)) + 1; x < (1 << winsize); x++) { |
98 | 3.32k | if ((err = mp_mul(&M[x - 1], &M[1], &M[x])) != MP_OKAY) goto LBL_MU; |
99 | 3.32k | if ((err = redux(&M[x], P, &mu)) != MP_OKAY) goto LBL_MU; |
100 | 3.32k | } |
101 | | |
102 | | /* setup result */ |
103 | 465 | if ((err = mp_init(&res)) != MP_OKAY) goto LBL_MU; |
104 | 465 | mp_set(&res, 1uL); |
105 | | |
106 | | /* set initial mode and bit cnt */ |
107 | 465 | mode = 0; |
108 | 465 | bitcnt = 1; |
109 | 465 | buf = 0; |
110 | 465 | digidx = X->used - 1; |
111 | 465 | bitcpy = 0; |
112 | 465 | bitbuf = 0; |
113 | | |
114 | 39.1k | for (;;) { |
115 | | /* grab next digit as required */ |
116 | 39.1k | if (--bitcnt == 0) { |
117 | | /* if digidx == -1 we are out of digits */ |
118 | 1.10k | if (digidx == -1) { |
119 | 465 | break; |
120 | 465 | } |
121 | | /* read next digit and reset the bitcnt */ |
122 | 644 | buf = X->dp[digidx--]; |
123 | 644 | bitcnt = (int)MP_DIGIT_BIT; |
124 | 644 | } |
125 | | |
126 | | /* grab the next msb from the exponent */ |
127 | 38.6k | y = (buf >> (mp_digit)(MP_DIGIT_BIT - 1)) & 1uL; |
128 | 38.6k | buf <<= (mp_digit)1; |
129 | | |
130 | | /* if the bit is zero and mode == 0 then we ignore it |
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 | 38.6k | if ((mode == 0) && (y == 0)) { |
136 | 7.86k | continue; |
137 | 7.86k | } |
138 | | |
139 | | /* if the bit is zero and mode == 1 then we square */ |
140 | 30.7k | if ((mode == 1) && (y == 0)) { |
141 | 8.44k | if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
142 | 8.44k | if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
143 | 8.44k | continue; |
144 | 8.44k | } |
145 | | |
146 | | /* else we add it to the window */ |
147 | 22.3k | bitbuf |= (y << (winsize - ++bitcpy)); |
148 | 22.3k | mode = 2; |
149 | | |
150 | 22.3k | if (bitcpy == winsize) { |
151 | | /* ok window is filled so square as required and multiply */ |
152 | | /* square first */ |
153 | 26.5k | for (x = 0; x < winsize; x++) { |
154 | 21.8k | if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
155 | 21.8k | if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
156 | 21.8k | } |
157 | | |
158 | | /* then multiply */ |
159 | 4.70k | if ((err = mp_mul(&res, &M[bitbuf], &res)) != MP_OKAY) goto LBL_RES; |
160 | 4.70k | if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
161 | | |
162 | | /* empty window and reset */ |
163 | 4.70k | bitcpy = 0; |
164 | 4.70k | bitbuf = 0; |
165 | 4.70k | mode = 1; |
166 | 4.70k | } |
167 | 22.3k | } |
168 | | |
169 | | /* if bits remain then square/multiply */ |
170 | 465 | if ((mode == 2) && (bitcpy > 0)) { |
171 | | /* square then multiply if the bit is set */ |
172 | 666 | for (x = 0; x < bitcpy; x++) { |
173 | 459 | if ((err = mp_sqr(&res, &res)) != MP_OKAY) goto LBL_RES; |
174 | 459 | if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
175 | | |
176 | 459 | bitbuf <<= 1; |
177 | 459 | if ((bitbuf & (1 << winsize)) != 0) { |
178 | | /* then multiply */ |
179 | 359 | if ((err = mp_mul(&res, &M[1], &res)) != MP_OKAY) goto LBL_RES; |
180 | 359 | if ((err = redux(&res, P, &mu)) != MP_OKAY) goto LBL_RES; |
181 | 359 | } |
182 | 459 | } |
183 | 207 | } |
184 | | |
185 | 465 | mp_exch(&res, Y); |
186 | 465 | err = MP_OKAY; |
187 | 465 | LBL_RES: |
188 | 465 | mp_clear(&res); |
189 | 465 | LBL_MU: |
190 | 465 | mp_clear(&mu); |
191 | 465 | LBL_M: |
192 | 465 | mp_clear(&M[1]); |
193 | 4.25k | for (x = 1<<(winsize-1); x < (1 << winsize); x++) { |
194 | 3.79k | mp_clear(&M[x]); |
195 | 3.79k | } |
196 | 465 | return err; |
197 | 465 | } |
198 | | #endif |