Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/openssl/src/crypto/bn/bn_exp.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | /* | - | ||||||||||||||||||||||||
2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. | - | ||||||||||||||||||||||||
3 | * | - | ||||||||||||||||||||||||
4 | * Licensed under the OpenSSL license (the "License"). You may not use | - | ||||||||||||||||||||||||
5 | * this file except in compliance with the License. You can obtain a copy | - | ||||||||||||||||||||||||
6 | * in the file LICENSE in the source distribution or at | - | ||||||||||||||||||||||||
7 | * https://www.openssl.org/source/license.html | - | ||||||||||||||||||||||||
8 | */ | - | ||||||||||||||||||||||||
9 | - | |||||||||||||||||||||||||
10 | #include "internal/cryptlib.h" | - | ||||||||||||||||||||||||
11 | #include "internal/constant_time_locl.h" | - | ||||||||||||||||||||||||
12 | #include "bn_lcl.h" | - | ||||||||||||||||||||||||
13 | - | |||||||||||||||||||||||||
14 | #include <stdlib.h> | - | ||||||||||||||||||||||||
15 | #ifdef _WIN32 | - | ||||||||||||||||||||||||
16 | # include <malloc.h> | - | ||||||||||||||||||||||||
17 | # ifndef alloca | - | ||||||||||||||||||||||||
18 | # define alloca _alloca | - | ||||||||||||||||||||||||
19 | # endif | - | ||||||||||||||||||||||||
20 | #elif defined(__GNUC__) | - | ||||||||||||||||||||||||
21 | # ifndef alloca | - | ||||||||||||||||||||||||
22 | # define alloca(s) __builtin_alloca((s)) | - | ||||||||||||||||||||||||
23 | # endif | - | ||||||||||||||||||||||||
24 | #elif defined(__sun) | - | ||||||||||||||||||||||||
25 | # include <alloca.h> | - | ||||||||||||||||||||||||
26 | #endif | - | ||||||||||||||||||||||||
27 | - | |||||||||||||||||||||||||
28 | #include "rsaz_exp.h" | - | ||||||||||||||||||||||||
29 | - | |||||||||||||||||||||||||
30 | #undef SPARC_T4_MONT | - | ||||||||||||||||||||||||
31 | #if defined(OPENSSL_BN_ASM_MONT) && (defined(__sparc__) || defined(__sparc)) | - | ||||||||||||||||||||||||
32 | # include "sparc_arch.h" | - | ||||||||||||||||||||||||
33 | extern unsigned int OPENSSL_sparcv9cap_P[]; | - | ||||||||||||||||||||||||
34 | # define SPARC_T4_MONT | - | ||||||||||||||||||||||||
35 | #endif | - | ||||||||||||||||||||||||
36 | - | |||||||||||||||||||||||||
37 | /* maximum precomputation table size for *variable* sliding windows */ | - | ||||||||||||||||||||||||
38 | #define TABLE_SIZE 32 | - | ||||||||||||||||||||||||
39 | - | |||||||||||||||||||||||||
40 | /* this one works - simple but works */ | - | ||||||||||||||||||||||||
41 | int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx) | - | ||||||||||||||||||||||||
42 | { | - | ||||||||||||||||||||||||
43 | int i, bits, ret = 0; | - | ||||||||||||||||||||||||
44 | BIGNUM *v, *rr; | - | ||||||||||||||||||||||||
45 | - | |||||||||||||||||||||||||
46 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
| 0-5 | ||||||||||||||||||||||||
47 | || BN_get_flags(a, BN_FLG_CONSTTIME) != 0) {
| 0-5 | ||||||||||||||||||||||||
48 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ | - | ||||||||||||||||||||||||
49 | BNerr(BN_F_BN_EXP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | - | ||||||||||||||||||||||||
50 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
51 | } | - | ||||||||||||||||||||||||
52 | - | |||||||||||||||||||||||||
53 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||
54 | rr = ((r == a) || (r == p)) ? BN_CTX_get(ctx) : r;
| 0-5 | ||||||||||||||||||||||||
55 | v = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
56 | if (rr == NULL || v == NULL)
| 0-5 | ||||||||||||||||||||||||
57 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
58 | - | |||||||||||||||||||||||||
59 | if (BN_copy(v, a) == NULL)
| 0-5 | ||||||||||||||||||||||||
60 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
61 | bits = BN_num_bits(p); | - | ||||||||||||||||||||||||
62 | - | |||||||||||||||||||||||||
63 | if (BN_is_odd(p)) {
| 2-3 | ||||||||||||||||||||||||
64 | if (BN_copy(rr, a) == NULL)
| 0-2 | ||||||||||||||||||||||||
65 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
66 | } else { executed 2 times by 1 test: end of block Executed by:
| 2 | ||||||||||||||||||||||||
67 | if (!BN_one(rr))
| 0-3 | ||||||||||||||||||||||||
68 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
69 | } executed 3 times by 1 test: end of block Executed by:
| 3 | ||||||||||||||||||||||||
70 | - | |||||||||||||||||||||||||
71 | for (i = 1; i < bits; i++) {
| 5-15 | ||||||||||||||||||||||||
72 | if (!BN_sqr(v, v, ctx))
| 0-15 | ||||||||||||||||||||||||
73 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
74 | if (BN_is_bit_set(p, i)) {
| 5-10 | ||||||||||||||||||||||||
75 | if (!BN_mul(rr, rr, v, ctx))
| 0-10 | ||||||||||||||||||||||||
76 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
77 | } executed 10 times by 1 test: end of block Executed by:
| 10 | ||||||||||||||||||||||||
78 | } executed 15 times by 1 test: end of block Executed by:
| 15 | ||||||||||||||||||||||||
79 | if (r != rr && BN_copy(r, rr) == NULL)
| 0-5 | ||||||||||||||||||||||||
80 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
81 | - | |||||||||||||||||||||||||
82 | ret = 1; | - | ||||||||||||||||||||||||
83 | err: code before this statement executed 5 times by 1 test: err: Executed by:
| 5 | ||||||||||||||||||||||||
84 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
85 | bn_check_top(r); | - | ||||||||||||||||||||||||
86 | return ret; executed 5 times by 1 test: return ret; Executed by:
| 5 | ||||||||||||||||||||||||
87 | } | - | ||||||||||||||||||||||||
88 | - | |||||||||||||||||||||||||
89 | int BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, | - | ||||||||||||||||||||||||
90 | BN_CTX *ctx) | - | ||||||||||||||||||||||||
91 | { | - | ||||||||||||||||||||||||
92 | int ret; | - | ||||||||||||||||||||||||
93 | - | |||||||||||||||||||||||||
94 | bn_check_top(a); | - | ||||||||||||||||||||||||
95 | bn_check_top(p); | - | ||||||||||||||||||||||||
96 | bn_check_top(m); | - | ||||||||||||||||||||||||
97 | - | |||||||||||||||||||||||||
98 | /*- | - | ||||||||||||||||||||||||
99 | * For even modulus m = 2^k*m_odd, it might make sense to compute | - | ||||||||||||||||||||||||
100 | * a^p mod m_odd and a^p mod 2^k separately (with Montgomery | - | ||||||||||||||||||||||||
101 | * exponentiation for the odd part), using appropriate exponent | - | ||||||||||||||||||||||||
102 | * reductions, and combine the results using the CRT. | - | ||||||||||||||||||||||||
103 | * | - | ||||||||||||||||||||||||
104 | * For now, we use Montgomery only if the modulus is odd; otherwise, | - | ||||||||||||||||||||||||
105 | * exponentiation using the reciprocal-based quick remaindering | - | ||||||||||||||||||||||||
106 | * algorithm is used. | - | ||||||||||||||||||||||||
107 | * | - | ||||||||||||||||||||||||
108 | * (Timing obtained with expspeed.c [computations a^p mod m | - | ||||||||||||||||||||||||
109 | * where a, p, m are of the same length: 256, 512, 1024, 2048, | - | ||||||||||||||||||||||||
110 | * 4096, 8192 bits], compared to the running time of the | - | ||||||||||||||||||||||||
111 | * standard algorithm: | - | ||||||||||||||||||||||||
112 | * | - | ||||||||||||||||||||||||
113 | * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration] | - | ||||||||||||||||||||||||
114 | * 55 .. 77 % [UltraSparc processor, but | - | ||||||||||||||||||||||||
115 | * debug-solaris-sparcv8-gcc conf.] | - | ||||||||||||||||||||||||
116 | * | - | ||||||||||||||||||||||||
117 | * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration] | - | ||||||||||||||||||||||||
118 | * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc] | - | ||||||||||||||||||||||||
119 | * | - | ||||||||||||||||||||||||
120 | * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont | - | ||||||||||||||||||||||||
121 | * at 2048 and more bits, but at 512 and 1024 bits, it was | - | ||||||||||||||||||||||||
122 | * slower even than the standard algorithm! | - | ||||||||||||||||||||||||
123 | * | - | ||||||||||||||||||||||||
124 | * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations] | - | ||||||||||||||||||||||||
125 | * should be obtained when the new Montgomery reduction code | - | ||||||||||||||||||||||||
126 | * has been integrated into OpenSSL.) | - | ||||||||||||||||||||||||
127 | */ | - | ||||||||||||||||||||||||
128 | - | |||||||||||||||||||||||||
129 | #define MONT_MUL_MOD | - | ||||||||||||||||||||||||
130 | #define MONT_EXP_WORD | - | ||||||||||||||||||||||||
131 | #define RECP_MUL_MOD | - | ||||||||||||||||||||||||
132 | - | |||||||||||||||||||||||||
133 | #ifdef MONT_MUL_MOD | - | ||||||||||||||||||||||||
134 | if (BN_is_odd(m)) {
| 279-8967 | ||||||||||||||||||||||||
135 | # ifdef MONT_EXP_WORD | - | ||||||||||||||||||||||||
136 | if (a->top == 1 && !a->neg
| 92-6150 | ||||||||||||||||||||||||
137 | && (BN_get_flags(p, BN_FLG_CONSTTIME) == 0)
| 0-2725 | ||||||||||||||||||||||||
138 | && (BN_get_flags(a, BN_FLG_CONSTTIME) == 0)
| 0-2725 | ||||||||||||||||||||||||
139 | && (BN_get_flags(m, BN_FLG_CONSTTIME) == 0)) {
| 0-2725 | ||||||||||||||||||||||||
140 | BN_ULONG A = a->d[0]; | - | ||||||||||||||||||||||||
141 | ret = BN_mod_exp_mont_word(r, A, p, m, ctx, NULL); | - | ||||||||||||||||||||||||
142 | } else executed 2725 times by 1 test: end of block Executed by:
| 2725 | ||||||||||||||||||||||||
143 | # endif | - | ||||||||||||||||||||||||
144 | ret = BN_mod_exp_mont(r, a, p, m, ctx, NULL); executed 6242 times by 1 test: ret = BN_mod_exp_mont(r, a, p, m, ctx, ((void *)0) ); Executed by:
| 6242 | ||||||||||||||||||||||||
145 | } else | - | ||||||||||||||||||||||||
146 | #endif | - | ||||||||||||||||||||||||
147 | #ifdef RECP_MUL_MOD | - | ||||||||||||||||||||||||
148 | { | - | ||||||||||||||||||||||||
149 | ret = BN_mod_exp_recp(r, a, p, m, ctx); | - | ||||||||||||||||||||||||
150 | } executed 279 times by 1 test: end of block Executed by:
| 279 | ||||||||||||||||||||||||
151 | #else | - | ||||||||||||||||||||||||
152 | { | - | ||||||||||||||||||||||||
153 | ret = BN_mod_exp_simple(r, a, p, m, ctx); | - | ||||||||||||||||||||||||
154 | } | - | ||||||||||||||||||||||||
155 | #endif | - | ||||||||||||||||||||||||
156 | - | |||||||||||||||||||||||||
157 | bn_check_top(r); | - | ||||||||||||||||||||||||
158 | return ret; executed 9246 times by 1 test: return ret; Executed by:
| 9246 | ||||||||||||||||||||||||
159 | } | - | ||||||||||||||||||||||||
160 | - | |||||||||||||||||||||||||
161 | int BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | - | ||||||||||||||||||||||||
162 | const BIGNUM *m, BN_CTX *ctx) | - | ||||||||||||||||||||||||
163 | { | - | ||||||||||||||||||||||||
164 | int i, j, bits, ret = 0, wstart, wend, window, wvalue; | - | ||||||||||||||||||||||||
165 | int start = 1; | - | ||||||||||||||||||||||||
166 | BIGNUM *aa; | - | ||||||||||||||||||||||||
167 | /* Table of variables obtained from 'ctx' */ | - | ||||||||||||||||||||||||
168 | BIGNUM *val[TABLE_SIZE]; | - | ||||||||||||||||||||||||
169 | BN_RECP_CTX recp; | - | ||||||||||||||||||||||||
170 | - | |||||||||||||||||||||||||
171 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
| 0-582 | ||||||||||||||||||||||||
172 | || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
| 0-582 | ||||||||||||||||||||||||
173 | || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
| 0-582 | ||||||||||||||||||||||||
174 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ | - | ||||||||||||||||||||||||
175 | BNerr(BN_F_BN_MOD_EXP_RECP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | - | ||||||||||||||||||||||||
176 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
177 | } | - | ||||||||||||||||||||||||
178 | - | |||||||||||||||||||||||||
179 | bits = BN_num_bits(p); | - | ||||||||||||||||||||||||
180 | if (bits == 0) {
| 5-577 | ||||||||||||||||||||||||
181 | /* x**0 mod 1, or x**0 mod -1 is still zero. */ | - | ||||||||||||||||||||||||
182 | if (BN_abs_is_word(m, 1)) {
| 2-3 | ||||||||||||||||||||||||
183 | ret = 1; | - | ||||||||||||||||||||||||
184 | BN_zero(r); | - | ||||||||||||||||||||||||
185 | } else { executed 3 times by 1 test: end of block Executed by:
| 3 | ||||||||||||||||||||||||
186 | ret = BN_one(r); | - | ||||||||||||||||||||||||
187 | } executed 2 times by 1 test: end of block Executed by:
| 2 | ||||||||||||||||||||||||
188 | return ret; executed 5 times by 1 test: return ret; Executed by:
| 5 | ||||||||||||||||||||||||
189 | } | - | ||||||||||||||||||||||||
190 | - | |||||||||||||||||||||||||
191 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||
192 | aa = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
193 | val[0] = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
194 | if (val[0] == NULL)
| 0-577 | ||||||||||||||||||||||||
195 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
196 | - | |||||||||||||||||||||||||
197 | BN_RECP_CTX_init(&recp); | - | ||||||||||||||||||||||||
198 | if (m->neg) {
| 92-485 | ||||||||||||||||||||||||
199 | /* ignore sign of 'm' */ | - | ||||||||||||||||||||||||
200 | if (!BN_copy(aa, m))
| 0-92 | ||||||||||||||||||||||||
201 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
202 | aa->neg = 0; | - | ||||||||||||||||||||||||
203 | if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0)
| 0-92 | ||||||||||||||||||||||||
204 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
205 | } else { executed 92 times by 1 test: end of block Executed by:
| 92 | ||||||||||||||||||||||||
206 | if (BN_RECP_CTX_set(&recp, m, ctx) <= 0)
| 0-485 | ||||||||||||||||||||||||
207 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
208 | } executed 485 times by 1 test: end of block Executed by:
| 485 | ||||||||||||||||||||||||
209 | - | |||||||||||||||||||||||||
210 | if (!BN_nnmod(val[0], a, m, ctx))
| 1-576 | ||||||||||||||||||||||||
211 | goto err; /* 1 */ executed 1 time by 1 test: goto err; Executed by:
| 1 | ||||||||||||||||||||||||
212 | if (BN_is_zero(val[0])) {
| 4-572 | ||||||||||||||||||||||||
213 | BN_zero(r); | - | ||||||||||||||||||||||||
214 | ret = 1; | - | ||||||||||||||||||||||||
215 | goto err; executed 4 times by 1 test: goto err; Executed by:
| 4 | ||||||||||||||||||||||||
216 | } | - | ||||||||||||||||||||||||
217 | - | |||||||||||||||||||||||||
218 | window = BN_window_bits_for_exponent_size(bits);
| 13-559 | ||||||||||||||||||||||||
219 | if (window > 1) {
| 166-406 | ||||||||||||||||||||||||
220 | if (!BN_mod_mul_reciprocal(aa, val[0], val[0], &recp, ctx))
| 0-406 | ||||||||||||||||||||||||
221 | goto err; /* 2 */ never executed: goto err; | 0 | ||||||||||||||||||||||||
222 | j = 1 << (window - 1); | - | ||||||||||||||||||||||||
223 | for (i = 1; i < j; i++) {
| 406-5422 | ||||||||||||||||||||||||
224 | if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
| 0-5422 | ||||||||||||||||||||||||
225 | !BN_mod_mul_reciprocal(val[i], val[i - 1], aa, &recp, ctx))
| 0-5422 | ||||||||||||||||||||||||
226 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
227 | } executed 5422 times by 1 test: end of block Executed by:
| 5422 | ||||||||||||||||||||||||
228 | } executed 406 times by 1 test: end of block Executed by:
| 406 | ||||||||||||||||||||||||
229 | - | |||||||||||||||||||||||||
230 | start = 1; /* This is used to avoid multiplication etc | - | ||||||||||||||||||||||||
231 | * when there is only the value '1' in the | - | ||||||||||||||||||||||||
232 | * buffer. */ | - | ||||||||||||||||||||||||
233 | wvalue = 0; /* The 'value' of the window */ | - | ||||||||||||||||||||||||
234 | wstart = bits - 1; /* The top bit of the window */ | - | ||||||||||||||||||||||||
235 | wend = 0; /* The bottom bit of the window */ | - | ||||||||||||||||||||||||
236 | - | |||||||||||||||||||||||||
237 | if (!BN_one(r))
| 0-572 | ||||||||||||||||||||||||
238 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
239 | - | |||||||||||||||||||||||||
240 | for (;;) { | - | ||||||||||||||||||||||||
241 | if (BN_is_bit_set(p, wstart) == 0) {
| 23919-51529 | ||||||||||||||||||||||||
242 | if (!start)
| 0-51529 | ||||||||||||||||||||||||
243 | if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
| 0-51529 | ||||||||||||||||||||||||
244 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
245 | if (wstart == 0)
| 320-51209 | ||||||||||||||||||||||||
246 | break; executed 320 times by 1 test: break; Executed by:
| 320 | ||||||||||||||||||||||||
247 | wstart--; | - | ||||||||||||||||||||||||
248 | continue; executed 51209 times by 1 test: continue; Executed by:
| 51209 | ||||||||||||||||||||||||
249 | } | - | ||||||||||||||||||||||||
250 | /* | - | ||||||||||||||||||||||||
251 | * We now have wstart on a 'set' bit, we now need to work out how bit | - | ||||||||||||||||||||||||
252 | * a window to do. To do this we need to scan forward until the last | - | ||||||||||||||||||||||||
253 | * set bit before the end of the window | - | ||||||||||||||||||||||||
254 | */ | - | ||||||||||||||||||||||||
255 | j = wstart; | - | ||||||||||||||||||||||||
256 | wvalue = 1; | - | ||||||||||||||||||||||||
257 | wend = 0; | - | ||||||||||||||||||||||||
258 | for (i = 1; i < window; i++) {
| 23754-91140 | ||||||||||||||||||||||||
259 | if (wstart - i < 0)
| 165-90975 | ||||||||||||||||||||||||
260 | break; executed 165 times by 1 test: break; Executed by:
| 165 | ||||||||||||||||||||||||
261 | if (BN_is_bit_set(p, wstart - i)) {
| 43249-47726 | ||||||||||||||||||||||||
262 | wvalue <<= (i - wend); | - | ||||||||||||||||||||||||
263 | wvalue |= 1; | - | ||||||||||||||||||||||||
264 | wend = i; | - | ||||||||||||||||||||||||
265 | } executed 47726 times by 1 test: end of block Executed by:
| 47726 | ||||||||||||||||||||||||
266 | } executed 90975 times by 1 test: end of block Executed by:
| 90975 | ||||||||||||||||||||||||
267 | - | |||||||||||||||||||||||||
268 | /* wend is the size of the current window */ | - | ||||||||||||||||||||||||
269 | j = wend + 1; | - | ||||||||||||||||||||||||
270 | /* add the 'bytes above' */ | - | ||||||||||||||||||||||||
271 | if (!start)
| 572-23347 | ||||||||||||||||||||||||
272 | for (i = 0; i < j; i++) {
| 23347-91488 | ||||||||||||||||||||||||
273 | if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
| 0-91488 | ||||||||||||||||||||||||
274 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
275 | } executed 91488 times by 1 test: end of block Executed by:
| 91488 | ||||||||||||||||||||||||
276 | - | |||||||||||||||||||||||||
277 | /* wvalue will be an odd number < 2^window */ | - | ||||||||||||||||||||||||
278 | if (!BN_mod_mul_reciprocal(r, r, val[wvalue >> 1], &recp, ctx))
| 0-23919 | ||||||||||||||||||||||||
279 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
280 | - | |||||||||||||||||||||||||
281 | /* move the 'window' down further */ | - | ||||||||||||||||||||||||
282 | wstart -= wend + 1; | - | ||||||||||||||||||||||||
283 | wvalue = 0; | - | ||||||||||||||||||||||||
284 | start = 0; | - | ||||||||||||||||||||||||
285 | if (wstart < 0)
| 252-23667 | ||||||||||||||||||||||||
286 | break; executed 252 times by 1 test: break; Executed by:
| 252 | ||||||||||||||||||||||||
287 | } executed 23667 times by 1 test: end of block Executed by:
| 23667 | ||||||||||||||||||||||||
288 | ret = 1; | - | ||||||||||||||||||||||||
289 | err: code before this statement executed 572 times by 1 test: err: Executed by:
| 572 | ||||||||||||||||||||||||
290 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
291 | BN_RECP_CTX_free(&recp); | - | ||||||||||||||||||||||||
292 | bn_check_top(r); | - | ||||||||||||||||||||||||
293 | return ret; executed 577 times by 1 test: return ret; Executed by:
| 577 | ||||||||||||||||||||||||
294 | } | - | ||||||||||||||||||||||||
295 | - | |||||||||||||||||||||||||
296 | int BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, | - | ||||||||||||||||||||||||
297 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | - | ||||||||||||||||||||||||
298 | { | - | ||||||||||||||||||||||||
299 | int i, j, bits, ret = 0, wstart, wend, window, wvalue; | - | ||||||||||||||||||||||||
300 | int start = 1; | - | ||||||||||||||||||||||||
301 | BIGNUM *d, *r; | - | ||||||||||||||||||||||||
302 | const BIGNUM *aa; | - | ||||||||||||||||||||||||
303 | /* Table of variables obtained from 'ctx' */ | - | ||||||||||||||||||||||||
304 | BIGNUM *val[TABLE_SIZE]; | - | ||||||||||||||||||||||||
305 | BN_MONT_CTX *mont = NULL; | - | ||||||||||||||||||||||||
306 | - | |||||||||||||||||||||||||
307 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
| 592-17148 | ||||||||||||||||||||||||
308 | || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
| 0-17148 | ||||||||||||||||||||||||
309 | || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
| 5448-11700 | ||||||||||||||||||||||||
310 | return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); executed 6040 times by 1 test: return BN_mod_exp_mont_consttime(rr, a, p, m, ctx, in_mont); Executed by:
| 6040 | ||||||||||||||||||||||||
311 | } | - | ||||||||||||||||||||||||
312 | - | |||||||||||||||||||||||||
313 | bn_check_top(a); | - | ||||||||||||||||||||||||
314 | bn_check_top(p); | - | ||||||||||||||||||||||||
315 | bn_check_top(m); | - | ||||||||||||||||||||||||
316 | - | |||||||||||||||||||||||||
317 | if (!BN_is_odd(m)) {
| 2-11698 | ||||||||||||||||||||||||
318 | BNerr(BN_F_BN_MOD_EXP_MONT, BN_R_CALLED_WITH_EVEN_MODULUS); | - | ||||||||||||||||||||||||
319 | return 0; executed 2 times by 1 test: return 0; Executed by:
| 2 | ||||||||||||||||||||||||
320 | } | - | ||||||||||||||||||||||||
321 | bits = BN_num_bits(p); | - | ||||||||||||||||||||||||
322 | if (bits == 0) {
| 34-11664 | ||||||||||||||||||||||||
323 | /* x**0 mod 1, or x**0 mod -1 is still zero. */ | - | ||||||||||||||||||||||||
324 | if (BN_abs_is_word(m, 1)) {
| 8-26 | ||||||||||||||||||||||||
325 | ret = 1; | - | ||||||||||||||||||||||||
326 | BN_zero(rr); | - | ||||||||||||||||||||||||
327 | } else { executed 8 times by 1 test: end of block Executed by:
| 8 | ||||||||||||||||||||||||
328 | ret = BN_one(rr); | - | ||||||||||||||||||||||||
329 | } executed 26 times by 1 test: end of block Executed by:
| 26 | ||||||||||||||||||||||||
330 | return ret; executed 34 times by 1 test: return ret; Executed by:
| 34 | ||||||||||||||||||||||||
331 | } | - | ||||||||||||||||||||||||
332 | - | |||||||||||||||||||||||||
333 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||
334 | d = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
335 | r = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
336 | val[0] = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
337 | if (val[0] == NULL)
| 0-11664 | ||||||||||||||||||||||||
338 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
339 | - | |||||||||||||||||||||||||
340 | /* | - | ||||||||||||||||||||||||
341 | * If this is not done, things will break in the montgomery part | - | ||||||||||||||||||||||||
342 | */ | - | ||||||||||||||||||||||||
343 | - | |||||||||||||||||||||||||
344 | if (in_mont != NULL)
| 4715-6949 | ||||||||||||||||||||||||
345 | mont = in_mont; executed 6949 times by 2 tests: mont = in_mont; Executed by:
| 6949 | ||||||||||||||||||||||||
346 | else { | - | ||||||||||||||||||||||||
347 | if ((mont = BN_MONT_CTX_new()) == NULL)
| 0-4715 | ||||||||||||||||||||||||
348 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
349 | if (!BN_MONT_CTX_set(mont, m, ctx))
| 0-4715 | ||||||||||||||||||||||||
350 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
351 | } executed 4715 times by 1 test: end of block Executed by:
| 4715 | ||||||||||||||||||||||||
352 | - | |||||||||||||||||||||||||
353 | if (a->neg || BN_ucmp(a, m) >= 0) {
| 33-11561 | ||||||||||||||||||||||||
354 | if (!BN_nnmod(val[0], a, m, ctx))
| 0-136 | ||||||||||||||||||||||||
355 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
356 | aa = val[0]; | - | ||||||||||||||||||||||||
357 | } else executed 136 times by 1 test: end of block Executed by:
| 136 | ||||||||||||||||||||||||
358 | aa = a; executed 11528 times by 2 tests: aa = a; Executed by:
| 11528 | ||||||||||||||||||||||||
359 | if (!bn_to_mont_fixed_top(val[0], aa, mont, ctx))
| 0-11664 | ||||||||||||||||||||||||
360 | goto err; /* 1 */ never executed: goto err; | 0 | ||||||||||||||||||||||||
361 | - | |||||||||||||||||||||||||
362 | window = BN_window_bits_for_exponent_size(bits);
| 213-11451 | ||||||||||||||||||||||||
363 | if (window > 1) {
| 5631-6033 | ||||||||||||||||||||||||
364 | if (!bn_mul_mont_fixed_top(d, val[0], val[0], mont, ctx))
| 0-6033 | ||||||||||||||||||||||||
365 | goto err; /* 2 */ never executed: goto err; | 0 | ||||||||||||||||||||||||
366 | j = 1 << (window - 1); | - | ||||||||||||||||||||||||
367 | for (i = 1; i < j; i++) {
| 6033-65607 | ||||||||||||||||||||||||
368 | if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
| 0-65607 | ||||||||||||||||||||||||
369 | !bn_mul_mont_fixed_top(val[i], val[i - 1], d, mont, ctx))
| 0-65607 | ||||||||||||||||||||||||
370 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
371 | } executed 65607 times by 2 tests: end of block Executed by:
| 65607 | ||||||||||||||||||||||||
372 | } executed 6033 times by 2 tests: end of block Executed by:
| 6033 | ||||||||||||||||||||||||
373 | - | |||||||||||||||||||||||||
374 | start = 1; /* This is used to avoid multiplication etc | - | ||||||||||||||||||||||||
375 | * when there is only the value '1' in the | - | ||||||||||||||||||||||||
376 | * buffer. */ | - | ||||||||||||||||||||||||
377 | wvalue = 0; /* The 'value' of the window */ | - | ||||||||||||||||||||||||
378 | wstart = bits - 1; /* The top bit of the window */ | - | ||||||||||||||||||||||||
379 | wend = 0; /* The bottom bit of the window */ | - | ||||||||||||||||||||||||
380 | - | |||||||||||||||||||||||||
381 | #if 1 /* by Shay Gueron's suggestion */ | - | ||||||||||||||||||||||||
382 | j = m->top; /* borrow j */ | - | ||||||||||||||||||||||||
383 | if (m->d[j - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
| 4856-6808 | ||||||||||||||||||||||||
384 | if (bn_wexpand(r, j) == NULL)
| 0-6808 | ||||||||||||||||||||||||
385 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
386 | /* 2^(top*BN_BITS2) - m */ | - | ||||||||||||||||||||||||
387 | r->d[0] = (0 - m->d[0]) & BN_MASK2; | - | ||||||||||||||||||||||||
388 | for (i = 1; i < j; i++)
| 6808-163595 | ||||||||||||||||||||||||
389 | r->d[i] = (~m->d[i]) & BN_MASK2; executed 163595 times by 2 tests: r->d[i] = (~m->d[i]) & (0xffffffffffffffffL); Executed by:
| 163595 | ||||||||||||||||||||||||
390 | r->top = j; | - | ||||||||||||||||||||||||
391 | r->flags |= BN_FLG_FIXED_TOP; | - | ||||||||||||||||||||||||
392 | } else executed 6808 times by 2 tests: end of block Executed by:
| 6808 | ||||||||||||||||||||||||
393 | #endif | - | ||||||||||||||||||||||||
394 | if (!bn_to_mont_fixed_top(r, BN_value_one(), mont, ctx))
| 0-4856 | ||||||||||||||||||||||||
395 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
396 | for (;;) { | - | ||||||||||||||||||||||||
397 | if (BN_is_bit_set(p, wstart) == 0) {
| 246538-808705 | ||||||||||||||||||||||||
398 | if (!start) {
| 0-808705 | ||||||||||||||||||||||||
399 | if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx))
| 0-808705 | ||||||||||||||||||||||||
400 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
401 | } executed 808705 times by 2 tests: end of block Executed by:
| 808705 | ||||||||||||||||||||||||
402 | if (wstart == 0)
| 1938-806767 | ||||||||||||||||||||||||
403 | break; executed 1938 times by 1 test: break; Executed by:
| 1938 | ||||||||||||||||||||||||
404 | wstart--; | - | ||||||||||||||||||||||||
405 | continue; executed 806767 times by 2 tests: continue; Executed by:
| 806767 | ||||||||||||||||||||||||
406 | } | - | ||||||||||||||||||||||||
407 | /* | - | ||||||||||||||||||||||||
408 | * We now have wstart on a 'set' bit, we now need to work out how bit | - | ||||||||||||||||||||||||
409 | * a window to do. To do this we need to scan forward until the last | - | ||||||||||||||||||||||||
410 | * set bit before the end of the window | - | ||||||||||||||||||||||||
411 | */ | - | ||||||||||||||||||||||||
412 | j = wstart; | - | ||||||||||||||||||||||||
413 | wvalue = 1; | - | ||||||||||||||||||||||||
414 | wend = 0; | - | ||||||||||||||||||||||||
415 | for (i = 1; i < window; i++) {
| 242914-861621 | ||||||||||||||||||||||||
416 | if (wstart - i < 0)
| 3624-857997 | ||||||||||||||||||||||||
417 | break; executed 3624 times by 2 tests: break; Executed by:
| 3624 | ||||||||||||||||||||||||
418 | if (BN_is_bit_set(p, wstart - i)) {
| 211830-646167 | ||||||||||||||||||||||||
419 | wvalue <<= (i - wend); | - | ||||||||||||||||||||||||
420 | wvalue |= 1; | - | ||||||||||||||||||||||||
421 | wend = i; | - | ||||||||||||||||||||||||
422 | } executed 646167 times by 2 tests: end of block Executed by:
| 646167 | ||||||||||||||||||||||||
423 | } executed 857997 times by 2 tests: end of block Executed by:
| 857997 | ||||||||||||||||||||||||
424 | - | |||||||||||||||||||||||||
425 | /* wend is the size of the current window */ | - | ||||||||||||||||||||||||
426 | j = wend + 1; | - | ||||||||||||||||||||||||
427 | /* add the 'bytes above' */ | - | ||||||||||||||||||||||||
428 | if (!start)
| 11664-234874 | ||||||||||||||||||||||||
429 | for (i = 0; i < j; i++) {
| 234874-974897 | ||||||||||||||||||||||||
430 | if (!bn_mul_mont_fixed_top(r, r, r, mont, ctx))
| 0-974897 | ||||||||||||||||||||||||
431 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
432 | } executed 974897 times by 2 tests: end of block Executed by:
| 974897 | ||||||||||||||||||||||||
433 | - | |||||||||||||||||||||||||
434 | /* wvalue will be an odd number < 2^window */ | - | ||||||||||||||||||||||||
435 | if (!bn_mul_mont_fixed_top(r, r, val[wvalue >> 1], mont, ctx))
| 0-246538 | ||||||||||||||||||||||||
436 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
437 | - | |||||||||||||||||||||||||
438 | /* move the 'window' down further */ | - | ||||||||||||||||||||||||
439 | wstart -= wend + 1; | - | ||||||||||||||||||||||||
440 | wvalue = 0; | - | ||||||||||||||||||||||||
441 | start = 0; | - | ||||||||||||||||||||||||
442 | if (wstart < 0)
| 9726-236812 | ||||||||||||||||||||||||
443 | break; executed 9726 times by 2 tests: break; Executed by:
| 9726 | ||||||||||||||||||||||||
444 | } executed 236812 times by 2 tests: end of block Executed by:
| 236812 | ||||||||||||||||||||||||
445 | /* | - | ||||||||||||||||||||||||
446 | * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery | - | ||||||||||||||||||||||||
447 | * removes padding [if any] and makes return value suitable for public | - | ||||||||||||||||||||||||
448 | * API consumer. | - | ||||||||||||||||||||||||
449 | */ | - | ||||||||||||||||||||||||
450 | #if defined(SPARC_T4_MONT) | - | ||||||||||||||||||||||||
451 | if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) { | - | ||||||||||||||||||||||||
452 | j = mont->N.top; /* borrow j */ | - | ||||||||||||||||||||||||
453 | val[0]->d[0] = 1; /* borrow val[0] */ | - | ||||||||||||||||||||||||
454 | for (i = 1; i < j; i++) | - | ||||||||||||||||||||||||
455 | val[0]->d[i] = 0; | - | ||||||||||||||||||||||||
456 | val[0]->top = j; | - | ||||||||||||||||||||||||
457 | if (!BN_mod_mul_montgomery(rr, r, val[0], mont, ctx)) | - | ||||||||||||||||||||||||
458 | goto err; | - | ||||||||||||||||||||||||
459 | } else | - | ||||||||||||||||||||||||
460 | #endif | - | ||||||||||||||||||||||||
461 | if (!BN_from_montgomery(rr, r, mont, ctx))
| 0-11664 | ||||||||||||||||||||||||
462 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
463 | ret = 1; | - | ||||||||||||||||||||||||
464 | err: code before this statement executed 11664 times by 2 tests: err: Executed by:
| 11664 | ||||||||||||||||||||||||
465 | if (in_mont == NULL)
| 4715-6949 | ||||||||||||||||||||||||
466 | BN_MONT_CTX_free(mont); executed 4715 times by 1 test: BN_MONT_CTX_free(mont); Executed by:
| 4715 | ||||||||||||||||||||||||
467 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
468 | bn_check_top(rr); | - | ||||||||||||||||||||||||
469 | return ret; executed 11664 times by 2 tests: return ret; Executed by:
| 11664 | ||||||||||||||||||||||||
470 | } | - | ||||||||||||||||||||||||
471 | - | |||||||||||||||||||||||||
472 | static BN_ULONG bn_get_bits(const BIGNUM *a, int bitpos) | - | ||||||||||||||||||||||||
473 | { | - | ||||||||||||||||||||||||
474 | BN_ULONG ret = 0; | - | ||||||||||||||||||||||||
475 | int wordpos; | - | ||||||||||||||||||||||||
476 | - | |||||||||||||||||||||||||
477 | wordpos = bitpos / BN_BITS2; | - | ||||||||||||||||||||||||
478 | bitpos %= BN_BITS2; | - | ||||||||||||||||||||||||
479 | if (wordpos >= 0 && wordpos < a->top) {
| 0-96938 | ||||||||||||||||||||||||
480 | ret = a->d[wordpos] & BN_MASK2; | - | ||||||||||||||||||||||||
481 | if (bitpos) {
| 4896-92042 | ||||||||||||||||||||||||
482 | ret >>= bitpos; | - | ||||||||||||||||||||||||
483 | if (++wordpos < a->top)
| 34740-57302 | ||||||||||||||||||||||||
484 | ret |= a->d[wordpos] << (BN_BITS2 - bitpos); executed 34740 times by 1 test: ret |= a->d[wordpos] << ((8 * 8) - bitpos); Executed by:
| 34740 | ||||||||||||||||||||||||
485 | } executed 92042 times by 1 test: end of block Executed by:
| 92042 | ||||||||||||||||||||||||
486 | } executed 96938 times by 1 test: end of block Executed by:
| 96938 | ||||||||||||||||||||||||
487 | - | |||||||||||||||||||||||||
488 | return ret & BN_MASK2; executed 96938 times by 1 test: return ret & (0xffffffffffffffffL); Executed by:
| 96938 | ||||||||||||||||||||||||
489 | } | - | ||||||||||||||||||||||||
490 | - | |||||||||||||||||||||||||
491 | /* | - | ||||||||||||||||||||||||
492 | * BN_mod_exp_mont_consttime() stores the precomputed powers in a specific | - | ||||||||||||||||||||||||
493 | * layout so that accessing any of these table values shows the same access | - | ||||||||||||||||||||||||
494 | * pattern as far as cache lines are concerned. The following functions are | - | ||||||||||||||||||||||||
495 | * used to transfer a BIGNUM from/to that table. | - | ||||||||||||||||||||||||
496 | */ | - | ||||||||||||||||||||||||
497 | - | |||||||||||||||||||||||||
498 | static int MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top, | - | ||||||||||||||||||||||||
499 | unsigned char *buf, int idx, | - | ||||||||||||||||||||||||
500 | int window) | - | ||||||||||||||||||||||||
501 | { | - | ||||||||||||||||||||||||
502 | int i, j; | - | ||||||||||||||||||||||||
503 | int width = 1 << window; | - | ||||||||||||||||||||||||
504 | BN_ULONG *table = (BN_ULONG *)buf; | - | ||||||||||||||||||||||||
505 | - | |||||||||||||||||||||||||
506 | if (top > b->top)
| 0-26960 | ||||||||||||||||||||||||
507 | top = b->top; /* this works because 'buf' is explicitly never executed: top = b->top; | 0 | ||||||||||||||||||||||||
508 | * zeroed */ | - | ||||||||||||||||||||||||
509 | for (i = 0, j = idx; i < top; i++, j += width) {
| 26960-528840 | ||||||||||||||||||||||||
510 | table[j] = b->d[i]; | - | ||||||||||||||||||||||||
511 | } executed 528840 times by 1 test: end of block Executed by:
| 528840 | ||||||||||||||||||||||||
512 | - | |||||||||||||||||||||||||
513 | return 1; executed 26960 times by 1 test: return 1; Executed by:
| 26960 | ||||||||||||||||||||||||
514 | } | - | ||||||||||||||||||||||||
515 | - | |||||||||||||||||||||||||
516 | static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top, | - | ||||||||||||||||||||||||
517 | unsigned char *buf, int idx, | - | ||||||||||||||||||||||||
518 | int window) | - | ||||||||||||||||||||||||
519 | { | - | ||||||||||||||||||||||||
520 | int i, j; | - | ||||||||||||||||||||||||
521 | int width = 1 << window; | - | ||||||||||||||||||||||||
522 | /* | - | ||||||||||||||||||||||||
523 | * We declare table 'volatile' in order to discourage compiler | - | ||||||||||||||||||||||||
524 | * from reordering loads from the table. Concern is that if | - | ||||||||||||||||||||||||
525 | * reordered in specific manner loads might give away the | - | ||||||||||||||||||||||||
526 | * information we are trying to conceal. Some would argue that | - | ||||||||||||||||||||||||
527 | * compiler can reorder them anyway, but it can as well be | - | ||||||||||||||||||||||||
528 | * argued that doing so would be violation of standard... | - | ||||||||||||||||||||||||
529 | */ | - | ||||||||||||||||||||||||
530 | volatile BN_ULONG *table = (volatile BN_ULONG *)buf; | - | ||||||||||||||||||||||||
531 | - | |||||||||||||||||||||||||
532 | if (bn_wexpand(b, top) == NULL)
| 0-89076 | ||||||||||||||||||||||||
533 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
534 | - | |||||||||||||||||||||||||
535 | if (window <= 3) {
| 39380-49696 | ||||||||||||||||||||||||
536 | for (i = 0; i < top; i++, table += width) {
| 39380-1222738 | ||||||||||||||||||||||||
537 | BN_ULONG acc = 0; | - | ||||||||||||||||||||||||
538 | - | |||||||||||||||||||||||||
539 | for (j = 0; j < width; j++) {
| 1222738-9781904 | ||||||||||||||||||||||||
540 | acc |= table[j] & | - | ||||||||||||||||||||||||
541 | ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1)); | - | ||||||||||||||||||||||||
542 | } executed 9781904 times by 1 test: end of block Executed by:
| 9781904 | ||||||||||||||||||||||||
543 | - | |||||||||||||||||||||||||
544 | b->d[i] = acc; | - | ||||||||||||||||||||||||
545 | } executed 1222738 times by 1 test: end of block Executed by:
| 1222738 | ||||||||||||||||||||||||
546 | } else { executed 39380 times by 1 test: end of block Executed by:
| 39380 | ||||||||||||||||||||||||
547 | int xstride = 1 << (window - 2); | - | ||||||||||||||||||||||||
548 | BN_ULONG y0, y1, y2, y3; | - | ||||||||||||||||||||||||
549 | - | |||||||||||||||||||||||||
550 | i = idx >> (window - 2); /* equivalent of idx / xstride */ | - | ||||||||||||||||||||||||
551 | idx &= xstride - 1; /* equivalent of idx % xstride */ | - | ||||||||||||||||||||||||
552 | - | |||||||||||||||||||||||||
553 | y0 = (BN_ULONG)0 - (constant_time_eq_int(i,0)&1); | - | ||||||||||||||||||||||||
554 | y1 = (BN_ULONG)0 - (constant_time_eq_int(i,1)&1); | - | ||||||||||||||||||||||||
555 | y2 = (BN_ULONG)0 - (constant_time_eq_int(i,2)&1); | - | ||||||||||||||||||||||||
556 | y3 = (BN_ULONG)0 - (constant_time_eq_int(i,3)&1); | - | ||||||||||||||||||||||||
557 | - | |||||||||||||||||||||||||
558 | for (i = 0; i < top; i++, table += width) {
| 49696-323264 | ||||||||||||||||||||||||
559 | BN_ULONG acc = 0; | - | ||||||||||||||||||||||||
560 | - | |||||||||||||||||||||||||
561 | for (j = 0; j < xstride; j++) {
| 323264-1293056 | ||||||||||||||||||||||||
562 | acc |= ( (table[j + 0 * xstride] & y0) | | - | ||||||||||||||||||||||||
563 | (table[j + 1 * xstride] & y1) | | - | ||||||||||||||||||||||||
564 | (table[j + 2 * xstride] & y2) | | - | ||||||||||||||||||||||||
565 | (table[j + 3 * xstride] & y3) ) | - | ||||||||||||||||||||||||
566 | & ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1)); | - | ||||||||||||||||||||||||
567 | } executed 1293056 times by 1 test: end of block Executed by:
| 1293056 | ||||||||||||||||||||||||
568 | - | |||||||||||||||||||||||||
569 | b->d[i] = acc; | - | ||||||||||||||||||||||||
570 | } executed 323264 times by 1 test: end of block Executed by:
| 323264 | ||||||||||||||||||||||||
571 | } executed 49696 times by 1 test: end of block Executed by:
| 49696 | ||||||||||||||||||||||||
572 | - | |||||||||||||||||||||||||
573 | b->top = top; | - | ||||||||||||||||||||||||
574 | b->flags |= BN_FLG_FIXED_TOP; | - | ||||||||||||||||||||||||
575 | return 1; executed 89076 times by 1 test: return 1; Executed by:
| 89076 | ||||||||||||||||||||||||
576 | } | - | ||||||||||||||||||||||||
577 | - | |||||||||||||||||||||||||
578 | /* | - | ||||||||||||||||||||||||
579 | * Given a pointer value, compute the next address that is a cache line | - | ||||||||||||||||||||||||
580 | * multiple. | - | ||||||||||||||||||||||||
581 | */ | - | ||||||||||||||||||||||||
582 | #define MOD_EXP_CTIME_ALIGN(x_) \ | - | ||||||||||||||||||||||||
583 | ((unsigned char*)(x_) + (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - (((size_t)(x_)) & (MOD_EXP_CTIME_MIN_CACHE_LINE_MASK)))) | - | ||||||||||||||||||||||||
584 | - | |||||||||||||||||||||||||
585 | /* | - | ||||||||||||||||||||||||
586 | * This variant of BN_mod_exp_mont() uses fixed windows and the special | - | ||||||||||||||||||||||||
587 | * precomputation memory layout to limit data-dependency to a minimum to | - | ||||||||||||||||||||||||
588 | * protect secret exponents (cf. the hyper-threading timing attacks pointed | - | ||||||||||||||||||||||||
589 | * out by Colin Percival, | - | ||||||||||||||||||||||||
590 | * http://www.daemonology.net/hyperthreading-considered-harmful/) | - | ||||||||||||||||||||||||
591 | */ | - | ||||||||||||||||||||||||
592 | int BN_mod_exp_mont_consttime(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p, | - | ||||||||||||||||||||||||
593 | const BIGNUM *m, BN_CTX *ctx, | - | ||||||||||||||||||||||||
594 | BN_MONT_CTX *in_mont) | - | ||||||||||||||||||||||||
595 | { | - | ||||||||||||||||||||||||
596 | int i, bits, ret = 0, window, wvalue, wmask, window0; | - | ||||||||||||||||||||||||
597 | int top; | - | ||||||||||||||||||||||||
598 | BN_MONT_CTX *mont = NULL; | - | ||||||||||||||||||||||||
599 | - | |||||||||||||||||||||||||
600 | int numPowers; | - | ||||||||||||||||||||||||
601 | unsigned char *powerbufFree = NULL; | - | ||||||||||||||||||||||||
602 | int powerbufLen = 0; | - | ||||||||||||||||||||||||
603 | unsigned char *powerbuf = NULL; | - | ||||||||||||||||||||||||
604 | BIGNUM tmp, am; | - | ||||||||||||||||||||||||
605 | #if defined(SPARC_T4_MONT) | - | ||||||||||||||||||||||||
606 | unsigned int t4 = 0; | - | ||||||||||||||||||||||||
607 | #endif | - | ||||||||||||||||||||||||
608 | - | |||||||||||||||||||||||||
609 | bn_check_top(a); | - | ||||||||||||||||||||||||
610 | bn_check_top(p); | - | ||||||||||||||||||||||||
611 | bn_check_top(m); | - | ||||||||||||||||||||||||
612 | - | |||||||||||||||||||||||||
613 | if (!BN_is_odd(m)) {
| 2-11073 | ||||||||||||||||||||||||
614 | BNerr(BN_F_BN_MOD_EXP_MONT_CONSTTIME, BN_R_CALLED_WITH_EVEN_MODULUS); | - | ||||||||||||||||||||||||
615 | return 0; executed 2 times by 1 test: return 0; Executed by:
| 2 | ||||||||||||||||||||||||
616 | } | - | ||||||||||||||||||||||||
617 | - | |||||||||||||||||||||||||
618 | top = m->top; | - | ||||||||||||||||||||||||
619 | - | |||||||||||||||||||||||||
620 | /* | - | ||||||||||||||||||||||||
621 | * Use all bits stored in |p|, rather than |BN_num_bits|, so we do not leak | - | ||||||||||||||||||||||||
622 | * whether the top bits are zero. | - | ||||||||||||||||||||||||
623 | */ | - | ||||||||||||||||||||||||
624 | bits = p->top * BN_BITS2; | - | ||||||||||||||||||||||||
625 | if (bits == 0) {
| 15-11058 | ||||||||||||||||||||||||
626 | /* x**0 mod 1, or x**0 mod -1 is still zero. */ | - | ||||||||||||||||||||||||
627 | if (BN_abs_is_word(m, 1)) {
| 4-11 | ||||||||||||||||||||||||
628 | ret = 1; | - | ||||||||||||||||||||||||
629 | BN_zero(rr); | - | ||||||||||||||||||||||||
630 | } else { executed 4 times by 1 test: end of block Executed by:
| 4 | ||||||||||||||||||||||||
631 | ret = BN_one(rr); | - | ||||||||||||||||||||||||
632 | } executed 11 times by 1 test: end of block Executed by:
| 11 | ||||||||||||||||||||||||
633 | return ret; executed 15 times by 1 test: return ret; Executed by:
| 15 | ||||||||||||||||||||||||
634 | } | - | ||||||||||||||||||||||||
635 | - | |||||||||||||||||||||||||
636 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||
637 | - | |||||||||||||||||||||||||
638 | /* | - | ||||||||||||||||||||||||
639 | * Allocate a montgomery context if it was not supplied by the caller. If | - | ||||||||||||||||||||||||
640 | * this is not done, things will break in the montgomery part. | - | ||||||||||||||||||||||||
641 | */ | - | ||||||||||||||||||||||||
642 | if (in_mont != NULL)
| 2043-9015 | ||||||||||||||||||||||||
643 | mont = in_mont; executed 9015 times by 1 test: mont = in_mont; Executed by:
| 9015 | ||||||||||||||||||||||||
644 | else { | - | ||||||||||||||||||||||||
645 | if ((mont = BN_MONT_CTX_new()) == NULL)
| 0-2043 | ||||||||||||||||||||||||
646 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
647 | if (!BN_MONT_CTX_set(mont, m, ctx))
| 0-2043 | ||||||||||||||||||||||||
648 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
649 | } executed 2043 times by 1 test: end of block Executed by:
| 2043 | ||||||||||||||||||||||||
650 | - | |||||||||||||||||||||||||
651 | #ifdef RSAZ_ENABLED | - | ||||||||||||||||||||||||
652 | if (!a->neg) {
| 0-11058 | ||||||||||||||||||||||||
653 | /* | - | ||||||||||||||||||||||||
654 | * If the size of the operands allow it, perform the optimized | - | ||||||||||||||||||||||||
655 | * RSAZ exponentiation. For further information see | - | ||||||||||||||||||||||||
656 | * crypto/bn/rsaz_exp.c and accompanying assembly modules. | - | ||||||||||||||||||||||||
657 | */ | - | ||||||||||||||||||||||||
658 | if ((16 == a->top) && (16 == p->top) && (BN_num_bits(m) == 1024)
| 1-5759 | ||||||||||||||||||||||||
659 | && rsaz_avx2_eligible()) {
| 0-5174 | ||||||||||||||||||||||||
660 | if (NULL == bn_wexpand(rr, 16))
| 0 | ||||||||||||||||||||||||
661 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
662 | RSAZ_1024_mod_exp_avx2(rr->d, a->d, p->d, m->d, mont->RR.d, | - | ||||||||||||||||||||||||
663 | mont->n0[0]); | - | ||||||||||||||||||||||||
664 | rr->top = 16; | - | ||||||||||||||||||||||||
665 | rr->neg = 0; | - | ||||||||||||||||||||||||
666 | bn_correct_top(rr); | - | ||||||||||||||||||||||||
667 | ret = 1; | - | ||||||||||||||||||||||||
668 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
669 | } else if ((8 == a->top) && (8 == p->top) && (BN_num_bits(m) == 512)) {
| 19-10389 | ||||||||||||||||||||||||
670 | if (NULL == bn_wexpand(rr, 8))
| 0-616 | ||||||||||||||||||||||||
671 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
672 | RSAZ_512_mod_exp(rr->d, a->d, p->d, m->d, mont->n0[0], mont->RR.d); | - | ||||||||||||||||||||||||
673 | rr->top = 8; | - | ||||||||||||||||||||||||
674 | rr->neg = 0; | - | ||||||||||||||||||||||||
675 | bn_correct_top(rr); | - | ||||||||||||||||||||||||
676 | ret = 1; | - | ||||||||||||||||||||||||
677 | goto err; executed 616 times by 1 test: goto err; Executed by:
| 616 | ||||||||||||||||||||||||
678 | } | - | ||||||||||||||||||||||||
679 | } executed 10442 times by 1 test: end of block Executed by:
| 10442 | ||||||||||||||||||||||||
680 | #endif | - | ||||||||||||||||||||||||
681 | - | |||||||||||||||||||||||||
682 | /* Get the window size to use with size of p. */ | - | ||||||||||||||||||||||||
683 | window = BN_window_bits_for_ctime_exponent_size(bits);
| 0-7269 | ||||||||||||||||||||||||
684 | #if defined(SPARC_T4_MONT) | - | ||||||||||||||||||||||||
685 | if (window >= 5 && (top & 15) == 0 && top <= 64 && | - | ||||||||||||||||||||||||
686 | (OPENSSL_sparcv9cap_P[1] & (CFR_MONTMUL | CFR_MONTSQR)) == | - | ||||||||||||||||||||||||
687 | (CFR_MONTMUL | CFR_MONTSQR) && (t4 = OPENSSL_sparcv9cap_P[0])) | - | ||||||||||||||||||||||||
688 | window = 5; | - | ||||||||||||||||||||||||
689 | else | - | ||||||||||||||||||||||||
690 | #endif | - | ||||||||||||||||||||||||
691 | #if defined(OPENSSL_BN_ASM_MONT5) | - | ||||||||||||||||||||||||
692 | if (window >= 5) {
| 2580-7862 | ||||||||||||||||||||||||
693 | window = 5; /* ~5% improvement for RSA2048 sign, and even | - | ||||||||||||||||||||||||
694 | * for RSA4096 */ | - | ||||||||||||||||||||||||
695 | /* reserve space for mont->N.d[] copy */ | - | ||||||||||||||||||||||||
696 | powerbufLen += top * sizeof(mont->N.d[0]); | - | ||||||||||||||||||||||||
697 | } executed 7862 times by 1 test: end of block Executed by:
| 7862 | ||||||||||||||||||||||||
698 | #endif | - | ||||||||||||||||||||||||
699 | (void)0; | - | ||||||||||||||||||||||||
700 | - | |||||||||||||||||||||||||
701 | /* | - | ||||||||||||||||||||||||
702 | * Allocate a buffer large enough to hold all of the pre-computed powers | - | ||||||||||||||||||||||||
703 | * of am, am itself and tmp. | - | ||||||||||||||||||||||||
704 | */ | - | ||||||||||||||||||||||||
705 | numPowers = 1 << window; | - | ||||||||||||||||||||||||
706 | powerbufLen += sizeof(m->d[0]) * (top * numPowers + | - | ||||||||||||||||||||||||
707 | ((2 * top) > | - | ||||||||||||||||||||||||
708 | numPowers ? (2 * top) : numPowers)); | - | ||||||||||||||||||||||||
709 | #ifdef alloca | - | ||||||||||||||||||||||||
710 | if (powerbufLen < 3072)
| 2799-7643 | ||||||||||||||||||||||||
711 | powerbufFree = executed 2799 times by 1 test: powerbufFree = __builtin_alloca ( powerbufLen + ( 64 ) ) ; Executed by:
| 2799 | ||||||||||||||||||||||||
712 | alloca(powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH); executed 2799 times by 1 test: powerbufFree = __builtin_alloca ( powerbufLen + ( 64 ) ) ; Executed by:
| 2799 | ||||||||||||||||||||||||
713 | else | - | ||||||||||||||||||||||||
714 | #endif | - | ||||||||||||||||||||||||
715 | if ((powerbufFree =
| 0-7643 | ||||||||||||||||||||||||
716 | OPENSSL_malloc(powerbufLen + MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH))
| 0-7643 | ||||||||||||||||||||||||
717 | == NULL)
| 0-7643 | ||||||||||||||||||||||||
718 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
719 | - | |||||||||||||||||||||||||
720 | powerbuf = MOD_EXP_CTIME_ALIGN(powerbufFree); | - | ||||||||||||||||||||||||
721 | memset(powerbuf, 0, powerbufLen); | - | ||||||||||||||||||||||||
722 | - | |||||||||||||||||||||||||
723 | #ifdef alloca | - | ||||||||||||||||||||||||
724 | if (powerbufLen < 3072)
| 2799-7643 | ||||||||||||||||||||||||
725 | powerbufFree = NULL; executed 2799 times by 1 test: powerbufFree = ((void *)0) ; Executed by:
| 2799 | ||||||||||||||||||||||||
726 | #endif | - | ||||||||||||||||||||||||
727 | - | |||||||||||||||||||||||||
728 | /* lay down tmp and am right after powers table */ | - | ||||||||||||||||||||||||
729 | tmp.d = (BN_ULONG *)(powerbuf + sizeof(m->d[0]) * top * numPowers); | - | ||||||||||||||||||||||||
730 | am.d = tmp.d + top; | - | ||||||||||||||||||||||||
731 | tmp.top = am.top = 0; | - | ||||||||||||||||||||||||
732 | tmp.dmax = am.dmax = top; | - | ||||||||||||||||||||||||
733 | tmp.neg = am.neg = 0; | - | ||||||||||||||||||||||||
734 | tmp.flags = am.flags = BN_FLG_STATIC_DATA; | - | ||||||||||||||||||||||||
735 | - | |||||||||||||||||||||||||
736 | /* prepare a^0 in Montgomery domain */ | - | ||||||||||||||||||||||||
737 | #if 1 /* by Shay Gueron's suggestion */ | - | ||||||||||||||||||||||||
738 | if (m->d[top - 1] & (((BN_ULONG)1) << (BN_BITS2 - 1))) {
| 2717-7725 | ||||||||||||||||||||||||
739 | /* 2^(top*BN_BITS2) - m */ | - | ||||||||||||||||||||||||
740 | tmp.d[0] = (0 - m->d[0]) & BN_MASK2; | - | ||||||||||||||||||||||||
741 | for (i = 1; i < top; i++)
| 7725-141477 | ||||||||||||||||||||||||
742 | tmp.d[i] = (~m->d[i]) & BN_MASK2; executed 141477 times by 1 test: tmp.d[i] = (~m->d[i]) & (0xffffffffffffffffL); Executed by:
| 141477 | ||||||||||||||||||||||||
743 | tmp.top = top; | - | ||||||||||||||||||||||||
744 | } else executed 7725 times by 1 test: end of block Executed by:
| 7725 | ||||||||||||||||||||||||
745 | #endif | - | ||||||||||||||||||||||||
746 | if (!bn_to_mont_fixed_top(&tmp, BN_value_one(), mont, ctx))
| 0-2717 | ||||||||||||||||||||||||
747 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
748 | - | |||||||||||||||||||||||||
749 | /* prepare a^1 in Montgomery domain */ | - | ||||||||||||||||||||||||
750 | if (a->neg || BN_ucmp(a, m) >= 0) {
| 0-10442 | ||||||||||||||||||||||||
751 | if (!BN_nnmod(&am, a, m, ctx))
| 0-22 | ||||||||||||||||||||||||
752 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
753 | if (!bn_to_mont_fixed_top(&am, &am, mont, ctx))
| 0-22 | ||||||||||||||||||||||||
754 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
755 | } else if (!bn_to_mont_fixed_top(&am, a, mont, ctx)) executed 22 times by 1 test: end of block Executed by:
| 0-10420 | ||||||||||||||||||||||||
756 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
757 | - | |||||||||||||||||||||||||
758 | #if defined(SPARC_T4_MONT) | - | ||||||||||||||||||||||||
759 | if (t4) { | - | ||||||||||||||||||||||||
760 | typedef int (*bn_pwr5_mont_f) (BN_ULONG *tp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
761 | const BN_ULONG *n0, const void *table, | - | ||||||||||||||||||||||||
762 | int power, int bits); | - | ||||||||||||||||||||||||
763 | int bn_pwr5_mont_t4_8(BN_ULONG *tp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
764 | const BN_ULONG *n0, const void *table, | - | ||||||||||||||||||||||||
765 | int power, int bits); | - | ||||||||||||||||||||||||
766 | int bn_pwr5_mont_t4_16(BN_ULONG *tp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
767 | const BN_ULONG *n0, const void *table, | - | ||||||||||||||||||||||||
768 | int power, int bits); | - | ||||||||||||||||||||||||
769 | int bn_pwr5_mont_t4_24(BN_ULONG *tp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
770 | const BN_ULONG *n0, const void *table, | - | ||||||||||||||||||||||||
771 | int power, int bits); | - | ||||||||||||||||||||||||
772 | int bn_pwr5_mont_t4_32(BN_ULONG *tp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
773 | const BN_ULONG *n0, const void *table, | - | ||||||||||||||||||||||||
774 | int power, int bits); | - | ||||||||||||||||||||||||
775 | static const bn_pwr5_mont_f pwr5_funcs[4] = { | - | ||||||||||||||||||||||||
776 | bn_pwr5_mont_t4_8, bn_pwr5_mont_t4_16, | - | ||||||||||||||||||||||||
777 | bn_pwr5_mont_t4_24, bn_pwr5_mont_t4_32 | - | ||||||||||||||||||||||||
778 | }; | - | ||||||||||||||||||||||||
779 | bn_pwr5_mont_f pwr5_worker = pwr5_funcs[top / 16 - 1]; | - | ||||||||||||||||||||||||
780 | - | |||||||||||||||||||||||||
781 | typedef int (*bn_mul_mont_f) (BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
782 | const void *bp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
783 | const BN_ULONG *n0); | - | ||||||||||||||||||||||||
784 | int bn_mul_mont_t4_8(BN_ULONG *rp, const BN_ULONG *ap, const void *bp, | - | ||||||||||||||||||||||||
785 | const BN_ULONG *np, const BN_ULONG *n0); | - | ||||||||||||||||||||||||
786 | int bn_mul_mont_t4_16(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
787 | const void *bp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
788 | const BN_ULONG *n0); | - | ||||||||||||||||||||||||
789 | int bn_mul_mont_t4_24(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
790 | const void *bp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
791 | const BN_ULONG *n0); | - | ||||||||||||||||||||||||
792 | int bn_mul_mont_t4_32(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
793 | const void *bp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
794 | const BN_ULONG *n0); | - | ||||||||||||||||||||||||
795 | static const bn_mul_mont_f mul_funcs[4] = { | - | ||||||||||||||||||||||||
796 | bn_mul_mont_t4_8, bn_mul_mont_t4_16, | - | ||||||||||||||||||||||||
797 | bn_mul_mont_t4_24, bn_mul_mont_t4_32 | - | ||||||||||||||||||||||||
798 | }; | - | ||||||||||||||||||||||||
799 | bn_mul_mont_f mul_worker = mul_funcs[top / 16 - 1]; | - | ||||||||||||||||||||||||
800 | - | |||||||||||||||||||||||||
801 | void bn_mul_mont_vis3(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
802 | const void *bp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
803 | const BN_ULONG *n0, int num); | - | ||||||||||||||||||||||||
804 | void bn_mul_mont_t4(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
805 | const void *bp, const BN_ULONG *np, | - | ||||||||||||||||||||||||
806 | const BN_ULONG *n0, int num); | - | ||||||||||||||||||||||||
807 | void bn_mul_mont_gather5_t4(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
808 | const void *table, const BN_ULONG *np, | - | ||||||||||||||||||||||||
809 | const BN_ULONG *n0, int num, int power); | - | ||||||||||||||||||||||||
810 | void bn_flip_n_scatter5_t4(const BN_ULONG *inp, size_t num, | - | ||||||||||||||||||||||||
811 | void *table, size_t power); | - | ||||||||||||||||||||||||
812 | void bn_gather5_t4(BN_ULONG *out, size_t num, | - | ||||||||||||||||||||||||
813 | void *table, size_t power); | - | ||||||||||||||||||||||||
814 | void bn_flip_t4(BN_ULONG *dst, BN_ULONG *src, size_t num); | - | ||||||||||||||||||||||||
815 | - | |||||||||||||||||||||||||
816 | BN_ULONG *np = mont->N.d, *n0 = mont->n0; | - | ||||||||||||||||||||||||
817 | int stride = 5 * (6 - (top / 16 - 1)); /* multiple of 5, but less | - | ||||||||||||||||||||||||
818 | * than 32 */ | - | ||||||||||||||||||||||||
819 | - | |||||||||||||||||||||||||
820 | /* | - | ||||||||||||||||||||||||
821 | * BN_to_montgomery can contaminate words above .top [in | - | ||||||||||||||||||||||||
822 | * BN_DEBUG[_DEBUG] build]... | - | ||||||||||||||||||||||||
823 | */ | - | ||||||||||||||||||||||||
824 | for (i = am.top; i < top; i++) | - | ||||||||||||||||||||||||
825 | am.d[i] = 0; | - | ||||||||||||||||||||||||
826 | for (i = tmp.top; i < top; i++) | - | ||||||||||||||||||||||||
827 | tmp.d[i] = 0; | - | ||||||||||||||||||||||||
828 | - | |||||||||||||||||||||||||
829 | bn_flip_n_scatter5_t4(tmp.d, top, powerbuf, 0); | - | ||||||||||||||||||||||||
830 | bn_flip_n_scatter5_t4(am.d, top, powerbuf, 1); | - | ||||||||||||||||||||||||
831 | if (!(*mul_worker) (tmp.d, am.d, am.d, np, n0) && | - | ||||||||||||||||||||||||
832 | !(*mul_worker) (tmp.d, am.d, am.d, np, n0)) | - | ||||||||||||||||||||||||
833 | bn_mul_mont_vis3(tmp.d, am.d, am.d, np, n0, top); | - | ||||||||||||||||||||||||
834 | bn_flip_n_scatter5_t4(tmp.d, top, powerbuf, 2); | - | ||||||||||||||||||||||||
835 | - | |||||||||||||||||||||||||
836 | for (i = 3; i < 32; i++) { | - | ||||||||||||||||||||||||
837 | /* Calculate a^i = a^(i-1) * a */ | - | ||||||||||||||||||||||||
838 | if (!(*mul_worker) (tmp.d, tmp.d, am.d, np, n0) && | - | ||||||||||||||||||||||||
839 | !(*mul_worker) (tmp.d, tmp.d, am.d, np, n0)) | - | ||||||||||||||||||||||||
840 | bn_mul_mont_vis3(tmp.d, tmp.d, am.d, np, n0, top); | - | ||||||||||||||||||||||||
841 | bn_flip_n_scatter5_t4(tmp.d, top, powerbuf, i); | - | ||||||||||||||||||||||||
842 | } | - | ||||||||||||||||||||||||
843 | - | |||||||||||||||||||||||||
844 | /* switch to 64-bit domain */ | - | ||||||||||||||||||||||||
845 | np = alloca(top * sizeof(BN_ULONG)); | - | ||||||||||||||||||||||||
846 | top /= 2; | - | ||||||||||||||||||||||||
847 | bn_flip_t4(np, mont->N.d, top); | - | ||||||||||||||||||||||||
848 | - | |||||||||||||||||||||||||
849 | /* | - | ||||||||||||||||||||||||
850 | * The exponent may not have a whole number of fixed-size windows. | - | ||||||||||||||||||||||||
851 | * To simplify the main loop, the initial window has between 1 and | - | ||||||||||||||||||||||||
852 | * full-window-size bits such that what remains is always a whole | - | ||||||||||||||||||||||||
853 | * number of windows | - | ||||||||||||||||||||||||
854 | */ | - | ||||||||||||||||||||||||
855 | window0 = (bits - 1) % 5 + 1; | - | ||||||||||||||||||||||||
856 | wmask = (1 << window0) - 1; | - | ||||||||||||||||||||||||
857 | bits -= window0; | - | ||||||||||||||||||||||||
858 | wvalue = bn_get_bits(p, bits) & wmask; | - | ||||||||||||||||||||||||
859 | bn_gather5_t4(tmp.d, top, powerbuf, wvalue); | - | ||||||||||||||||||||||||
860 | - | |||||||||||||||||||||||||
861 | /* | - | ||||||||||||||||||||||||
862 | * Scan the exponent one window at a time starting from the most | - | ||||||||||||||||||||||||
863 | * significant bits. | - | ||||||||||||||||||||||||
864 | */ | - | ||||||||||||||||||||||||
865 | while (bits > 0) { | - | ||||||||||||||||||||||||
866 | if (bits < stride) | - | ||||||||||||||||||||||||
867 | stride = bits; | - | ||||||||||||||||||||||||
868 | bits -= stride; | - | ||||||||||||||||||||||||
869 | wvalue = bn_get_bits(p, bits); | - | ||||||||||||||||||||||||
870 | - | |||||||||||||||||||||||||
871 | if ((*pwr5_worker) (tmp.d, np, n0, powerbuf, wvalue, stride)) | - | ||||||||||||||||||||||||
872 | continue; | - | ||||||||||||||||||||||||
873 | /* retry once and fall back */ | - | ||||||||||||||||||||||||
874 | if ((*pwr5_worker) (tmp.d, np, n0, powerbuf, wvalue, stride)) | - | ||||||||||||||||||||||||
875 | continue; | - | ||||||||||||||||||||||||
876 | - | |||||||||||||||||||||||||
877 | bits += stride - 5; | - | ||||||||||||||||||||||||
878 | wvalue >>= stride - 5; | - | ||||||||||||||||||||||||
879 | wvalue &= 31; | - | ||||||||||||||||||||||||
880 | bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
881 | bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
882 | bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
883 | bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
884 | bn_mul_mont_t4(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
885 | bn_mul_mont_gather5_t4(tmp.d, tmp.d, powerbuf, np, n0, top, | - | ||||||||||||||||||||||||
886 | wvalue); | - | ||||||||||||||||||||||||
887 | } | - | ||||||||||||||||||||||||
888 | - | |||||||||||||||||||||||||
889 | bn_flip_t4(tmp.d, tmp.d, top); | - | ||||||||||||||||||||||||
890 | top *= 2; | - | ||||||||||||||||||||||||
891 | /* back to 32-bit domain */ | - | ||||||||||||||||||||||||
892 | tmp.top = top; | - | ||||||||||||||||||||||||
893 | bn_correct_top(&tmp); | - | ||||||||||||||||||||||||
894 | OPENSSL_cleanse(np, top * sizeof(BN_ULONG)); | - | ||||||||||||||||||||||||
895 | } else | - | ||||||||||||||||||||||||
896 | #endif | - | ||||||||||||||||||||||||
897 | #if defined(OPENSSL_BN_ASM_MONT5) | - | ||||||||||||||||||||||||
898 | if (window == 5 && top > 1) {
| 0-7862 | ||||||||||||||||||||||||
899 | /* | - | ||||||||||||||||||||||||
900 | * This optimization uses ideas from http://eprint.iacr.org/2011/239, | - | ||||||||||||||||||||||||
901 | * specifically optimization of cache-timing attack countermeasures | - | ||||||||||||||||||||||||
902 | * and pre-computation optimization. | - | ||||||||||||||||||||||||
903 | */ | - | ||||||||||||||||||||||||
904 | - | |||||||||||||||||||||||||
905 | /* | - | ||||||||||||||||||||||||
906 | * Dedicated window==4 case improves 512-bit RSA sign by ~15%, but as | - | ||||||||||||||||||||||||
907 | * 512-bit RSA is hardly relevant, we omit it to spare size... | - | ||||||||||||||||||||||||
908 | */ | - | ||||||||||||||||||||||||
909 | void bn_mul_mont_gather5(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
910 | const void *table, const BN_ULONG *np, | - | ||||||||||||||||||||||||
911 | const BN_ULONG *n0, int num, int power); | - | ||||||||||||||||||||||||
912 | void bn_scatter5(const BN_ULONG *inp, size_t num, | - | ||||||||||||||||||||||||
913 | void *table, size_t power); | - | ||||||||||||||||||||||||
914 | void bn_gather5(BN_ULONG *out, size_t num, void *table, size_t power); | - | ||||||||||||||||||||||||
915 | void bn_power5(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
916 | const void *table, const BN_ULONG *np, | - | ||||||||||||||||||||||||
917 | const BN_ULONG *n0, int num, int power); | - | ||||||||||||||||||||||||
918 | int bn_get_bits5(const BN_ULONG *ap, int off); | - | ||||||||||||||||||||||||
919 | int bn_from_montgomery(BN_ULONG *rp, const BN_ULONG *ap, | - | ||||||||||||||||||||||||
920 | const BN_ULONG *not_used, const BN_ULONG *np, | - | ||||||||||||||||||||||||
921 | const BN_ULONG *n0, int num); | - | ||||||||||||||||||||||||
922 | - | |||||||||||||||||||||||||
923 | BN_ULONG *n0 = mont->n0, *np; | - | ||||||||||||||||||||||||
924 | - | |||||||||||||||||||||||||
925 | /* | - | ||||||||||||||||||||||||
926 | * BN_to_montgomery can contaminate words above .top [in | - | ||||||||||||||||||||||||
927 | * BN_DEBUG[_DEBUG] build]... | - | ||||||||||||||||||||||||
928 | */ | - | ||||||||||||||||||||||||
929 | for (i = am.top; i < top; i++)
| 0-7862 | ||||||||||||||||||||||||
930 | am.d[i] = 0; never executed: am.d[i] = 0; | 0 | ||||||||||||||||||||||||
931 | for (i = tmp.top; i < top; i++)
| 0-7862 | ||||||||||||||||||||||||
932 | tmp.d[i] = 0; never executed: tmp.d[i] = 0; | 0 | ||||||||||||||||||||||||
933 | - | |||||||||||||||||||||||||
934 | /* | - | ||||||||||||||||||||||||
935 | * copy mont->N.d[] to improve cache locality | - | ||||||||||||||||||||||||
936 | */ | - | ||||||||||||||||||||||||
937 | for (np = am.d + top, i = 0; i < top; i++)
| 7862-145430 | ||||||||||||||||||||||||
938 | np[i] = mont->N.d[i]; executed 145430 times by 1 test: np[i] = mont->N.d[i]; Executed by:
| 145430 | ||||||||||||||||||||||||
939 | - | |||||||||||||||||||||||||
940 | bn_scatter5(tmp.d, top, powerbuf, 0); | - | ||||||||||||||||||||||||
941 | bn_scatter5(am.d, am.top, powerbuf, 1); | - | ||||||||||||||||||||||||
942 | bn_mul_mont(tmp.d, am.d, am.d, np, n0, top); | - | ||||||||||||||||||||||||
943 | bn_scatter5(tmp.d, top, powerbuf, 2); | - | ||||||||||||||||||||||||
944 | - | |||||||||||||||||||||||||
945 | # if 0 | - | ||||||||||||||||||||||||
946 | for (i = 3; i < 32; i++) { | - | ||||||||||||||||||||||||
947 | /* Calculate a^i = a^(i-1) * a */ | - | ||||||||||||||||||||||||
948 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1); | - | ||||||||||||||||||||||||
949 | bn_scatter5(tmp.d, top, powerbuf, i); | - | ||||||||||||||||||||||||
950 | } | - | ||||||||||||||||||||||||
951 | # else | - | ||||||||||||||||||||||||
952 | /* same as above, but uses squaring for 1/2 of operations */ | - | ||||||||||||||||||||||||
953 | for (i = 4; i < 32; i *= 2) {
| 7862-23586 | ||||||||||||||||||||||||
954 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
955 | bn_scatter5(tmp.d, top, powerbuf, i); | - | ||||||||||||||||||||||||
956 | } executed 23586 times by 1 test: end of block Executed by:
| 23586 | ||||||||||||||||||||||||
957 | for (i = 3; i < 8; i += 2) {
| 7862-23586 | ||||||||||||||||||||||||
958 | int j; | - | ||||||||||||||||||||||||
959 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1); | - | ||||||||||||||||||||||||
960 | bn_scatter5(tmp.d, top, powerbuf, i); | - | ||||||||||||||||||||||||
961 | for (j = 2 * i; j < 32; j *= 2) {
| 23586-55034 | ||||||||||||||||||||||||
962 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
963 | bn_scatter5(tmp.d, top, powerbuf, j); | - | ||||||||||||||||||||||||
964 | } executed 55034 times by 1 test: end of block Executed by:
| 55034 | ||||||||||||||||||||||||
965 | } executed 23586 times by 1 test: end of block Executed by:
| 23586 | ||||||||||||||||||||||||
966 | for (; i < 16; i += 2) {
| 7862-31448 | ||||||||||||||||||||||||
967 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1); | - | ||||||||||||||||||||||||
968 | bn_scatter5(tmp.d, top, powerbuf, i); | - | ||||||||||||||||||||||||
969 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
970 | bn_scatter5(tmp.d, top, powerbuf, 2 * i); | - | ||||||||||||||||||||||||
971 | } executed 31448 times by 1 test: end of block Executed by:
| 31448 | ||||||||||||||||||||||||
972 | for (; i < 32; i += 2) {
| 7862-62896 | ||||||||||||||||||||||||
973 | bn_mul_mont_gather5(tmp.d, am.d, powerbuf, np, n0, top, i - 1); | - | ||||||||||||||||||||||||
974 | bn_scatter5(tmp.d, top, powerbuf, i); | - | ||||||||||||||||||||||||
975 | } executed 62896 times by 1 test: end of block Executed by:
| 62896 | ||||||||||||||||||||||||
976 | # endif | - | ||||||||||||||||||||||||
977 | /* | - | ||||||||||||||||||||||||
978 | * The exponent may not have a whole number of fixed-size windows. | - | ||||||||||||||||||||||||
979 | * To simplify the main loop, the initial window has between 1 and | - | ||||||||||||||||||||||||
980 | * full-window-size bits such that what remains is always a whole | - | ||||||||||||||||||||||||
981 | * number of windows | - | ||||||||||||||||||||||||
982 | */ | - | ||||||||||||||||||||||||
983 | window0 = (bits - 1) % 5 + 1; | - | ||||||||||||||||||||||||
984 | wmask = (1 << window0) - 1; | - | ||||||||||||||||||||||||
985 | bits -= window0; | - | ||||||||||||||||||||||||
986 | wvalue = bn_get_bits(p, bits) & wmask; | - | ||||||||||||||||||||||||
987 | bn_gather5(tmp.d, top, powerbuf, wvalue); | - | ||||||||||||||||||||||||
988 | - | |||||||||||||||||||||||||
989 | /* | - | ||||||||||||||||||||||||
990 | * Scan the exponent one window at a time starting from the most | - | ||||||||||||||||||||||||
991 | * significant bits. | - | ||||||||||||||||||||||||
992 | */ | - | ||||||||||||||||||||||||
993 | if (top & 7) {
| 2340-5522 | ||||||||||||||||||||||||
994 | while (bits > 0) {
| 2340-686189 | ||||||||||||||||||||||||
995 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
996 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
997 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
998 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
999 | bn_mul_mont(tmp.d, tmp.d, tmp.d, np, n0, top); | - | ||||||||||||||||||||||||
1000 | bn_mul_mont_gather5(tmp.d, tmp.d, powerbuf, np, n0, top, | - | ||||||||||||||||||||||||
1001 | bn_get_bits5(p->d, bits -= 5)); | - | ||||||||||||||||||||||||
1002 | } executed 686189 times by 1 test: end of block Executed by:
| 686189 | ||||||||||||||||||||||||
1003 | } else { executed 2340 times by 1 test: end of block Executed by:
| 2340 | ||||||||||||||||||||||||
1004 | while (bits > 0) {
| 5522-1135874 | ||||||||||||||||||||||||
1005 | bn_power5(tmp.d, tmp.d, powerbuf, np, n0, top, | - | ||||||||||||||||||||||||
1006 | bn_get_bits5(p->d, bits -= 5)); | - | ||||||||||||||||||||||||
1007 | } executed 1135874 times by 1 test: end of block Executed by:
| 1135874 | ||||||||||||||||||||||||
1008 | } executed 5522 times by 1 test: end of block Executed by:
| 5522 | ||||||||||||||||||||||||
1009 | - | |||||||||||||||||||||||||
1010 | ret = bn_from_montgomery(tmp.d, tmp.d, NULL, np, n0, top); | - | ||||||||||||||||||||||||
1011 | tmp.top = top; | - | ||||||||||||||||||||||||
1012 | bn_correct_top(&tmp); | - | ||||||||||||||||||||||||
1013 | if (ret) {
| 2340-5522 | ||||||||||||||||||||||||
1014 | if (!BN_copy(rr, &tmp))
| 0-5522 | ||||||||||||||||||||||||
1015 | ret = 0; never executed: ret = 0; | 0 | ||||||||||||||||||||||||
1016 | goto err; /* non-zero ret means it's not error */ executed 5522 times by 1 test: goto err; Executed by:
| 5522 | ||||||||||||||||||||||||
1017 | } | - | ||||||||||||||||||||||||
1018 | } else executed 2340 times by 1 test: end of block Executed by:
| 2340 | ||||||||||||||||||||||||
1019 | #endif | - | ||||||||||||||||||||||||
1020 | { | - | ||||||||||||||||||||||||
1021 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0, window))
| 0-2580 | ||||||||||||||||||||||||
1022 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1023 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am, top, powerbuf, 1, window))
| 0-2580 | ||||||||||||||||||||||||
1024 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1025 | - | |||||||||||||||||||||||||
1026 | /* | - | ||||||||||||||||||||||||
1027 | * If the window size is greater than 1, then calculate | - | ||||||||||||||||||||||||
1028 | * val[i=2..2^winsize-1]. Powers are computed as a*a^(i-1) (even | - | ||||||||||||||||||||||||
1029 | * powers could instead be computed as (a^(i/2))^2 to use the slight | - | ||||||||||||||||||||||||
1030 | * performance advantage of sqr over mul). | - | ||||||||||||||||||||||||
1031 | */ | - | ||||||||||||||||||||||||
1032 | if (window > 1) {
| 0-2580 | ||||||||||||||||||||||||
1033 | if (!bn_mul_mont_fixed_top(&tmp, &am, &am, mont, ctx))
| 0-2580 | ||||||||||||||||||||||||
1034 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1035 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 2,
| 0-2580 | ||||||||||||||||||||||||
1036 | window))
| 0-2580 | ||||||||||||||||||||||||
1037 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1038 | for (i = 3; i < numPowers; i++) {
| 2580-19220 | ||||||||||||||||||||||||
1039 | /* Calculate a^i = a^(i-1) * a */ | - | ||||||||||||||||||||||||
1040 | if (!bn_mul_mont_fixed_top(&tmp, &am, &tmp, mont, ctx))
| 0-19220 | ||||||||||||||||||||||||
1041 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1042 | if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, i,
| 0-19220 | ||||||||||||||||||||||||
1043 | window))
| 0-19220 | ||||||||||||||||||||||||
1044 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1045 | } executed 19220 times by 1 test: end of block Executed by:
| 19220 | ||||||||||||||||||||||||
1046 | } executed 2580 times by 1 test: end of block Executed by:
| 2580 | ||||||||||||||||||||||||
1047 | - | |||||||||||||||||||||||||
1048 | /* | - | ||||||||||||||||||||||||
1049 | * The exponent may not have a whole number of fixed-size windows. | - | ||||||||||||||||||||||||
1050 | * To simplify the main loop, the initial window has between 1 and | - | ||||||||||||||||||||||||
1051 | * full-window-size bits such that what remains is always a whole | - | ||||||||||||||||||||||||
1052 | * number of windows | - | ||||||||||||||||||||||||
1053 | */ | - | ||||||||||||||||||||||||
1054 | window0 = (bits - 1) % window + 1; | - | ||||||||||||||||||||||||
1055 | wmask = (1 << window0) - 1; | - | ||||||||||||||||||||||||
1056 | bits -= window0; | - | ||||||||||||||||||||||||
1057 | wvalue = bn_get_bits(p, bits) & wmask; | - | ||||||||||||||||||||||||
1058 | if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&tmp, top, powerbuf, wvalue,
| 0-2580 | ||||||||||||||||||||||||
1059 | window))
| 0-2580 | ||||||||||||||||||||||||
1060 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1061 | - | |||||||||||||||||||||||||
1062 | wmask = (1 << window) - 1; | - | ||||||||||||||||||||||||
1063 | /* | - | ||||||||||||||||||||||||
1064 | * Scan the exponent one window at a time starting from the most | - | ||||||||||||||||||||||||
1065 | * significant bits. | - | ||||||||||||||||||||||||
1066 | */ | - | ||||||||||||||||||||||||
1067 | while (bits > 0) {
| 2580-86496 | ||||||||||||||||||||||||
1068 | - | |||||||||||||||||||||||||
1069 | /* Square the result window-size times */ | - | ||||||||||||||||||||||||
1070 | for (i = 0; i < window; i++)
| 86496-308394 | ||||||||||||||||||||||||
1071 | if (!bn_mul_mont_fixed_top(&tmp, &tmp, &tmp, mont, ctx))
| 0-308394 | ||||||||||||||||||||||||
1072 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1073 | - | |||||||||||||||||||||||||
1074 | /* | - | ||||||||||||||||||||||||
1075 | * Get a window's worth of bits from the exponent | - | ||||||||||||||||||||||||
1076 | * This avoids calling BN_is_bit_set for each bit, which | - | ||||||||||||||||||||||||
1077 | * is not only slower but also makes each bit vulnerable to | - | ||||||||||||||||||||||||
1078 | * EM (and likely other) side-channel attacks like One&Done | - | ||||||||||||||||||||||||
1079 | * (for details see "One&Done: A Single-Decryption EM-Based | - | ||||||||||||||||||||||||
1080 | * Attack on OpenSSL’s Constant-Time Blinded RSA" by M. Alam, | - | ||||||||||||||||||||||||
1081 | * H. Khan, M. Dey, N. Sinha, R. Callan, A. Zajic, and | - | ||||||||||||||||||||||||
1082 | * M. Prvulovic, in USENIX Security'18) | - | ||||||||||||||||||||||||
1083 | */ | - | ||||||||||||||||||||||||
1084 | bits -= window; | - | ||||||||||||||||||||||||
1085 | wvalue = bn_get_bits(p, bits) & wmask; | - | ||||||||||||||||||||||||
1086 | /* | - | ||||||||||||||||||||||||
1087 | * Fetch the appropriate pre-computed value from the pre-buf | - | ||||||||||||||||||||||||
1088 | */ | - | ||||||||||||||||||||||||
1089 | if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&am, top, powerbuf, wvalue,
| 0-86496 | ||||||||||||||||||||||||
1090 | window))
| 0-86496 | ||||||||||||||||||||||||
1091 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1092 | - | |||||||||||||||||||||||||
1093 | /* Multiply the result into the intermediate result */ | - | ||||||||||||||||||||||||
1094 | if (!bn_mul_mont_fixed_top(&tmp, &tmp, &am, mont, ctx))
| 0-86496 | ||||||||||||||||||||||||
1095 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1096 | } executed 86496 times by 1 test: end of block Executed by:
| 86496 | ||||||||||||||||||||||||
1097 | } executed 2580 times by 1 test: end of block Executed by:
| 2580 | ||||||||||||||||||||||||
1098 | - | |||||||||||||||||||||||||
1099 | /* | - | ||||||||||||||||||||||||
1100 | * Done with zero-padded intermediate BIGNUMs. Final BN_from_montgomery | - | ||||||||||||||||||||||||
1101 | * removes padding [if any] and makes return value suitable for public | - | ||||||||||||||||||||||||
1102 | * API consumer. | - | ||||||||||||||||||||||||
1103 | */ | - | ||||||||||||||||||||||||
1104 | #if defined(SPARC_T4_MONT) | - | ||||||||||||||||||||||||
1105 | if (OPENSSL_sparcv9cap_P[0] & (SPARCV9_VIS3 | SPARCV9_PREFER_FPU)) { | - | ||||||||||||||||||||||||
1106 | am.d[0] = 1; /* borrow am */ | - | ||||||||||||||||||||||||
1107 | for (i = 1; i < top; i++) | - | ||||||||||||||||||||||||
1108 | am.d[i] = 0; | - | ||||||||||||||||||||||||
1109 | if (!BN_mod_mul_montgomery(rr, &tmp, &am, mont, ctx)) | - | ||||||||||||||||||||||||
1110 | goto err; | - | ||||||||||||||||||||||||
1111 | } else | - | ||||||||||||||||||||||||
1112 | #endif | - | ||||||||||||||||||||||||
1113 | if (!BN_from_montgomery(rr, &tmp, mont, ctx))
| 0-4920 | ||||||||||||||||||||||||
1114 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1115 | ret = 1; | - | ||||||||||||||||||||||||
1116 | err: code before this statement executed 4920 times by 1 test: err: Executed by:
| 4920 | ||||||||||||||||||||||||
1117 | if (in_mont == NULL)
| 2043-9015 | ||||||||||||||||||||||||
1118 | BN_MONT_CTX_free(mont); executed 2043 times by 1 test: BN_MONT_CTX_free(mont); Executed by:
| 2043 | ||||||||||||||||||||||||
1119 | if (powerbuf != NULL) {
| 616-10442 | ||||||||||||||||||||||||
1120 | OPENSSL_cleanse(powerbuf, powerbufLen); | - | ||||||||||||||||||||||||
1121 | OPENSSL_free(powerbufFree); | - | ||||||||||||||||||||||||
1122 | } executed 10442 times by 1 test: end of block Executed by:
| 10442 | ||||||||||||||||||||||||
1123 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
1124 | return ret; executed 11058 times by 1 test: return ret; Executed by:
| 11058 | ||||||||||||||||||||||||
1125 | } | - | ||||||||||||||||||||||||
1126 | - | |||||||||||||||||||||||||
1127 | int BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p, | - | ||||||||||||||||||||||||
1128 | const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont) | - | ||||||||||||||||||||||||
1129 | { | - | ||||||||||||||||||||||||
1130 | BN_MONT_CTX *mont = NULL; | - | ||||||||||||||||||||||||
1131 | int b, bits, ret = 0; | - | ||||||||||||||||||||||||
1132 | int r_is_one; | - | ||||||||||||||||||||||||
1133 | BN_ULONG w, next_w; | - | ||||||||||||||||||||||||
1134 | BIGNUM *r, *t; | - | ||||||||||||||||||||||||
1135 | BIGNUM *swap_tmp; | - | ||||||||||||||||||||||||
1136 | #define BN_MOD_MUL_WORD(r, w, m) \ | - | ||||||||||||||||||||||||
1137 | (BN_mul_word(r, (w)) && \ | - | ||||||||||||||||||||||||
1138 | (/* BN_ucmp(r, (m)) < 0 ? 1 :*/ \ | - | ||||||||||||||||||||||||
1139 | (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1)))) | - | ||||||||||||||||||||||||
1140 | /* | - | ||||||||||||||||||||||||
1141 | * BN_MOD_MUL_WORD is only used with 'w' large, so the BN_ucmp test is | - | ||||||||||||||||||||||||
1142 | * probably more overhead than always using BN_mod (which uses BN_copy if | - | ||||||||||||||||||||||||
1143 | * a similar test returns true). | - | ||||||||||||||||||||||||
1144 | */ | - | ||||||||||||||||||||||||
1145 | /* | - | ||||||||||||||||||||||||
1146 | * We can use BN_mod and do not need BN_nnmod because our accumulator is | - | ||||||||||||||||||||||||
1147 | * never negative (the result of BN_mod does not depend on the sign of | - | ||||||||||||||||||||||||
1148 | * the modulus). | - | ||||||||||||||||||||||||
1149 | */ | - | ||||||||||||||||||||||||
1150 | #define BN_TO_MONTGOMERY_WORD(r, w, mont) \ | - | ||||||||||||||||||||||||
1151 | (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx)) | - | ||||||||||||||||||||||||
1152 | - | |||||||||||||||||||||||||
1153 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
| 0-2729 | ||||||||||||||||||||||||
1154 | || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
| 0-2729 | ||||||||||||||||||||||||
1155 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ | - | ||||||||||||||||||||||||
1156 | BNerr(BN_F_BN_MOD_EXP_MONT_WORD, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | - | ||||||||||||||||||||||||
1157 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
1158 | } | - | ||||||||||||||||||||||||
1159 | - | |||||||||||||||||||||||||
1160 | bn_check_top(p); | - | ||||||||||||||||||||||||
1161 | bn_check_top(m); | - | ||||||||||||||||||||||||
1162 | - | |||||||||||||||||||||||||
1163 | if (!BN_is_odd(m)) {
| 0-2729 | ||||||||||||||||||||||||
1164 | BNerr(BN_F_BN_MOD_EXP_MONT_WORD, BN_R_CALLED_WITH_EVEN_MODULUS); | - | ||||||||||||||||||||||||
1165 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
1166 | } | - | ||||||||||||||||||||||||
1167 | if (m->top == 1)
| 112-2617 | ||||||||||||||||||||||||
1168 | a %= m->d[0]; /* make sure that 'a' is reduced */ executed 112 times by 1 test: a %= m->d[0]; Executed by:
| 112 | ||||||||||||||||||||||||
1169 | - | |||||||||||||||||||||||||
1170 | bits = BN_num_bits(p); | - | ||||||||||||||||||||||||
1171 | if (bits == 0) {
| 10-2719 | ||||||||||||||||||||||||
1172 | /* x**0 mod 1, or x**0 mod -1 is still zero. */ | - | ||||||||||||||||||||||||
1173 | if (BN_abs_is_word(m, 1)) {
| 3-7 | ||||||||||||||||||||||||
1174 | ret = 1; | - | ||||||||||||||||||||||||
1175 | BN_zero(rr); | - | ||||||||||||||||||||||||
1176 | } else { executed 7 times by 1 test: end of block Executed by:
| 7 | ||||||||||||||||||||||||
1177 | ret = BN_one(rr); | - | ||||||||||||||||||||||||
1178 | } executed 3 times by 1 test: end of block Executed by:
| 3 | ||||||||||||||||||||||||
1179 | return ret; executed 10 times by 1 test: return ret; Executed by:
| 10 | ||||||||||||||||||||||||
1180 | } | - | ||||||||||||||||||||||||
1181 | if (a == 0) {
| 2-2717 | ||||||||||||||||||||||||
1182 | BN_zero(rr); | - | ||||||||||||||||||||||||
1183 | ret = 1; | - | ||||||||||||||||||||||||
1184 | return ret; executed 2 times by 1 test: return ret; Executed by:
| 2 | ||||||||||||||||||||||||
1185 | } | - | ||||||||||||||||||||||||
1186 | - | |||||||||||||||||||||||||
1187 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||
1188 | r = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
1189 | t = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
1190 | if (t == NULL)
| 0-2717 | ||||||||||||||||||||||||
1191 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1192 | - | |||||||||||||||||||||||||
1193 | if (in_mont != NULL)
| 0-2717 | ||||||||||||||||||||||||
1194 | mont = in_mont; never executed: mont = in_mont; | 0 | ||||||||||||||||||||||||
1195 | else { | - | ||||||||||||||||||||||||
1196 | if ((mont = BN_MONT_CTX_new()) == NULL)
| 0-2717 | ||||||||||||||||||||||||
1197 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1198 | if (!BN_MONT_CTX_set(mont, m, ctx))
| 0-2717 | ||||||||||||||||||||||||
1199 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1200 | } executed 2717 times by 1 test: end of block Executed by:
| 2717 | ||||||||||||||||||||||||
1201 | - | |||||||||||||||||||||||||
1202 | r_is_one = 1; /* except for Montgomery factor */ | - | ||||||||||||||||||||||||
1203 | - | |||||||||||||||||||||||||
1204 | /* bits-1 >= 0 */ | - | ||||||||||||||||||||||||
1205 | - | |||||||||||||||||||||||||
1206 | /* The result is accumulated in the product r*w. */ | - | ||||||||||||||||||||||||
1207 | w = a; /* bit 'bits-1' of 'p' is always set */ | - | ||||||||||||||||||||||||
1208 | for (b = bits - 2; b >= 0; b--) {
| 2717-373922 | ||||||||||||||||||||||||
1209 | /* First, square r*w. */ | - | ||||||||||||||||||||||||
1210 | next_w = w * w; | - | ||||||||||||||||||||||||
1211 | if ((next_w / w) != w) { /* overflow */
| 83268-290654 | ||||||||||||||||||||||||
1212 | if (r_is_one) {
| 2403-80865 | ||||||||||||||||||||||||
1213 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
| 0-2403 | ||||||||||||||||||||||||
1214 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1215 | r_is_one = 0; | - | ||||||||||||||||||||||||
1216 | } else { executed 2403 times by 1 test: end of block Executed by:
| 2403 | ||||||||||||||||||||||||
1217 | if (!BN_MOD_MUL_WORD(r, w, m))
| 0-80865 | ||||||||||||||||||||||||
1218 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1219 | } executed 80865 times by 1 test: end of block Executed by:
| 80865 | ||||||||||||||||||||||||
1220 | next_w = 1; | - | ||||||||||||||||||||||||
1221 | } executed 83268 times by 1 test: end of block Executed by:
| 83268 | ||||||||||||||||||||||||
1222 | w = next_w; | - | ||||||||||||||||||||||||
1223 | if (!r_is_one) {
| 7308-366614 | ||||||||||||||||||||||||
1224 | if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
| 0-366614 | ||||||||||||||||||||||||
1225 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1226 | } executed 366614 times by 1 test: end of block Executed by:
| 366614 | ||||||||||||||||||||||||
1227 | - | |||||||||||||||||||||||||
1228 | /* Second, multiply r*w by 'a' if exponent bit is set. */ | - | ||||||||||||||||||||||||
1229 | if (BN_is_bit_set(p, b)) {
| 30032-343890 | ||||||||||||||||||||||||
1230 | next_w = w * a; | - | ||||||||||||||||||||||||
1231 | if ((next_w / a) != w) { /* overflow */
| 51661-292229 | ||||||||||||||||||||||||
1232 | if (r_is_one) {
| 270-51391 | ||||||||||||||||||||||||
1233 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
| 0-270 | ||||||||||||||||||||||||
1234 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1235 | r_is_one = 0; | - | ||||||||||||||||||||||||
1236 | } else { executed 270 times by 1 test: end of block Executed by:
| 270 | ||||||||||||||||||||||||
1237 | if (!BN_MOD_MUL_WORD(r, w, m))
| 0-51391 | ||||||||||||||||||||||||
1238 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1239 | } executed 51391 times by 1 test: end of block Executed by:
| 51391 | ||||||||||||||||||||||||
1240 | next_w = a; | - | ||||||||||||||||||||||||
1241 | } executed 51661 times by 1 test: end of block Executed by:
| 51661 | ||||||||||||||||||||||||
1242 | w = next_w; | - | ||||||||||||||||||||||||
1243 | } executed 343890 times by 1 test: end of block Executed by:
| 343890 | ||||||||||||||||||||||||
1244 | } executed 373922 times by 1 test: end of block Executed by:
| 373922 | ||||||||||||||||||||||||
1245 | - | |||||||||||||||||||||||||
1246 | /* Finally, set r:=r*w. */ | - | ||||||||||||||||||||||||
1247 | if (w != 1) {
| 157-2560 | ||||||||||||||||||||||||
1248 | if (r_is_one) {
| 39-2521 | ||||||||||||||||||||||||
1249 | if (!BN_TO_MONTGOMERY_WORD(r, w, mont))
| 0-39 | ||||||||||||||||||||||||
1250 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1251 | r_is_one = 0; | - | ||||||||||||||||||||||||
1252 | } else { executed 39 times by 1 test: end of block Executed by:
| 39 | ||||||||||||||||||||||||
1253 | if (!BN_MOD_MUL_WORD(r, w, m))
| 0-2521 | ||||||||||||||||||||||||
1254 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1255 | } executed 2521 times by 1 test: end of block Executed by:
| 2521 | ||||||||||||||||||||||||
1256 | } | - | ||||||||||||||||||||||||
1257 | - | |||||||||||||||||||||||||
1258 | if (r_is_one) { /* can happen only if a == 1 */
| 5-2712 | ||||||||||||||||||||||||
1259 | if (!BN_one(rr))
| 0-5 | ||||||||||||||||||||||||
1260 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1261 | } else { executed 5 times by 1 test: end of block Executed by:
| 5 | ||||||||||||||||||||||||
1262 | if (!BN_from_montgomery(rr, r, mont, ctx))
| 0-2712 | ||||||||||||||||||||||||
1263 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1264 | } executed 2712 times by 1 test: end of block Executed by:
| 2712 | ||||||||||||||||||||||||
1265 | ret = 1; | - | ||||||||||||||||||||||||
1266 | err: code before this statement executed 2717 times by 1 test: err: Executed by:
| 2717 | ||||||||||||||||||||||||
1267 | if (in_mont == NULL)
| 0-2717 | ||||||||||||||||||||||||
1268 | BN_MONT_CTX_free(mont); executed 2717 times by 1 test: BN_MONT_CTX_free(mont); Executed by:
| 2717 | ||||||||||||||||||||||||
1269 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
1270 | bn_check_top(rr); | - | ||||||||||||||||||||||||
1271 | return ret; executed 2717 times by 1 test: return ret; Executed by:
| 2717 | ||||||||||||||||||||||||
1272 | } | - | ||||||||||||||||||||||||
1273 | - | |||||||||||||||||||||||||
1274 | /* The old fallback, simple version :-) */ | - | ||||||||||||||||||||||||
1275 | int BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, | - | ||||||||||||||||||||||||
1276 | const BIGNUM *m, BN_CTX *ctx) | - | ||||||||||||||||||||||||
1277 | { | - | ||||||||||||||||||||||||
1278 | int i, j, bits, ret = 0, wstart, wend, window, wvalue; | - | ||||||||||||||||||||||||
1279 | int start = 1; | - | ||||||||||||||||||||||||
1280 | BIGNUM *d; | - | ||||||||||||||||||||||||
1281 | /* Table of variables obtained from 'ctx' */ | - | ||||||||||||||||||||||||
1282 | BIGNUM *val[TABLE_SIZE]; | - | ||||||||||||||||||||||||
1283 | - | |||||||||||||||||||||||||
1284 | if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0
| 0-728 | ||||||||||||||||||||||||
1285 | || BN_get_flags(a, BN_FLG_CONSTTIME) != 0
| 0-728 | ||||||||||||||||||||||||
1286 | || BN_get_flags(m, BN_FLG_CONSTTIME) != 0) {
| 0-728 | ||||||||||||||||||||||||
1287 | /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */ | - | ||||||||||||||||||||||||
1288 | BNerr(BN_F_BN_MOD_EXP_SIMPLE, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); | - | ||||||||||||||||||||||||
1289 | return 0; never executed: return 0; | 0 | ||||||||||||||||||||||||
1290 | } | - | ||||||||||||||||||||||||
1291 | - | |||||||||||||||||||||||||
1292 | bits = BN_num_bits(p); | - | ||||||||||||||||||||||||
1293 | if (bits == 0) {
| 12-716 | ||||||||||||||||||||||||
1294 | /* x**0 mod 1, or x**0 mod -1 is still zero. */ | - | ||||||||||||||||||||||||
1295 | if (BN_abs_is_word(m, 1)) {
| 6 | ||||||||||||||||||||||||
1296 | ret = 1; | - | ||||||||||||||||||||||||
1297 | BN_zero(r); | - | ||||||||||||||||||||||||
1298 | } else { executed 6 times by 1 test: end of block Executed by:
| 6 | ||||||||||||||||||||||||
1299 | ret = BN_one(r); | - | ||||||||||||||||||||||||
1300 | } executed 6 times by 1 test: end of block Executed by:
| 6 | ||||||||||||||||||||||||
1301 | return ret; executed 12 times by 1 test: return ret; Executed by:
| 12 | ||||||||||||||||||||||||
1302 | } | - | ||||||||||||||||||||||||
1303 | - | |||||||||||||||||||||||||
1304 | BN_CTX_start(ctx); | - | ||||||||||||||||||||||||
1305 | d = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
1306 | val[0] = BN_CTX_get(ctx); | - | ||||||||||||||||||||||||
1307 | if (val[0] == NULL)
| 0-716 | ||||||||||||||||||||||||
1308 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1309 | - | |||||||||||||||||||||||||
1310 | if (!BN_nnmod(val[0], a, m, ctx))
| 0-716 | ||||||||||||||||||||||||
1311 | goto err; /* 1 */ never executed: goto err; | 0 | ||||||||||||||||||||||||
1312 | if (BN_is_zero(val[0])) {
| 56-660 | ||||||||||||||||||||||||
1313 | BN_zero(r); | - | ||||||||||||||||||||||||
1314 | ret = 1; | - | ||||||||||||||||||||||||
1315 | goto err; executed 56 times by 1 test: goto err; Executed by:
| 56 | ||||||||||||||||||||||||
1316 | } | - | ||||||||||||||||||||||||
1317 | - | |||||||||||||||||||||||||
1318 | window = BN_window_bits_for_exponent_size(bits);
| 39-621 | ||||||||||||||||||||||||
1319 | if (window > 1) {
| 247-413 | ||||||||||||||||||||||||
1320 | if (!BN_mod_mul(d, val[0], val[0], m, ctx))
| 0-413 | ||||||||||||||||||||||||
1321 | goto err; /* 2 */ never executed: goto err; | 0 | ||||||||||||||||||||||||
1322 | j = 1 << (window - 1); | - | ||||||||||||||||||||||||
1323 | for (i = 1; i < j; i++) {
| 413-5343 | ||||||||||||||||||||||||
1324 | if (((val[i] = BN_CTX_get(ctx)) == NULL) ||
| 0-5343 | ||||||||||||||||||||||||
1325 | !BN_mod_mul(val[i], val[i - 1], d, m, ctx))
| 0-5343 | ||||||||||||||||||||||||
1326 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1327 | } executed 5343 times by 1 test: end of block Executed by:
| 5343 | ||||||||||||||||||||||||
1328 | } executed 413 times by 1 test: end of block Executed by:
| 413 | ||||||||||||||||||||||||
1329 | - | |||||||||||||||||||||||||
1330 | start = 1; /* This is used to avoid multiplication etc | - | ||||||||||||||||||||||||
1331 | * when there is only the value '1' in the | - | ||||||||||||||||||||||||
1332 | * buffer. */ | - | ||||||||||||||||||||||||
1333 | wvalue = 0; /* The 'value' of the window */ | - | ||||||||||||||||||||||||
1334 | wstart = bits - 1; /* The top bit of the window */ | - | ||||||||||||||||||||||||
1335 | wend = 0; /* The bottom bit of the window */ | - | ||||||||||||||||||||||||
1336 | - | |||||||||||||||||||||||||
1337 | if (!BN_one(r))
| 0-660 | ||||||||||||||||||||||||
1338 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1339 | - | |||||||||||||||||||||||||
1340 | for (;;) { | - | ||||||||||||||||||||||||
1341 | if (BN_is_bit_set(p, wstart) == 0) {
| 23776-64116 | ||||||||||||||||||||||||
1342 | if (!start)
| 0-64116 | ||||||||||||||||||||||||
1343 | if (!BN_mod_mul(r, r, r, m, ctx))
| 0-64116 | ||||||||||||||||||||||||
1344 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1345 | if (wstart == 0)
| 298-63818 | ||||||||||||||||||||||||
1346 | break; executed 298 times by 1 test: break; Executed by:
| 298 | ||||||||||||||||||||||||
1347 | wstart--; | - | ||||||||||||||||||||||||
1348 | continue; executed 63818 times by 1 test: continue; Executed by:
| 63818 | ||||||||||||||||||||||||
1349 | } | - | ||||||||||||||||||||||||
1350 | /* | - | ||||||||||||||||||||||||
1351 | * We now have wstart on a 'set' bit, we now need to work out how bit | - | ||||||||||||||||||||||||
1352 | * a window to do. To do this we need to scan forward until the last | - | ||||||||||||||||||||||||
1353 | * set bit before the end of the window | - | ||||||||||||||||||||||||
1354 | */ | - | ||||||||||||||||||||||||
1355 | j = wstart; | - | ||||||||||||||||||||||||
1356 | wvalue = 1; | - | ||||||||||||||||||||||||
1357 | wend = 0; | - | ||||||||||||||||||||||||
1358 | for (i = 1; i < window; i++) {
| 23547-93047 | ||||||||||||||||||||||||
1359 | if (wstart - i < 0)
| 229-92818 | ||||||||||||||||||||||||
1360 | break; executed 229 times by 1 test: break; Executed by:
| 229 | ||||||||||||||||||||||||
1361 | if (BN_is_bit_set(p, wstart - i)) {
| 40957-51861 | ||||||||||||||||||||||||
1362 | wvalue <<= (i - wend); | - | ||||||||||||||||||||||||
1363 | wvalue |= 1; | - | ||||||||||||||||||||||||
1364 | wend = i; | - | ||||||||||||||||||||||||
1365 | } executed 51861 times by 1 test: end of block Executed by:
| 51861 | ||||||||||||||||||||||||
1366 | } executed 92818 times by 1 test: end of block Executed by:
| 92818 | ||||||||||||||||||||||||
1367 | - | |||||||||||||||||||||||||
1368 | /* wend is the size of the current window */ | - | ||||||||||||||||||||||||
1369 | j = wend + 1; | - | ||||||||||||||||||||||||
1370 | /* add the 'bytes above' */ | - | ||||||||||||||||||||||||
1371 | if (!start)
| 660-23116 | ||||||||||||||||||||||||
1372 | for (i = 0; i < j; i++) {
| 23116-94651 | ||||||||||||||||||||||||
1373 | if (!BN_mod_mul(r, r, r, m, ctx))
| 0-94651 | ||||||||||||||||||||||||
1374 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1375 | } executed 94651 times by 1 test: end of block Executed by:
| 94651 | ||||||||||||||||||||||||
1376 | - | |||||||||||||||||||||||||
1377 | /* wvalue will be an odd number < 2^window */ | - | ||||||||||||||||||||||||
1378 | if (!BN_mod_mul(r, r, val[wvalue >> 1], m, ctx))
| 0-23776 | ||||||||||||||||||||||||
1379 | goto err; never executed: goto err; | 0 | ||||||||||||||||||||||||
1380 | - | |||||||||||||||||||||||||
1381 | /* move the 'window' down further */ | - | ||||||||||||||||||||||||
1382 | wstart -= wend + 1; | - | ||||||||||||||||||||||||
1383 | wvalue = 0; | - | ||||||||||||||||||||||||
1384 | start = 0; | - | ||||||||||||||||||||||||
1385 | if (wstart < 0)
| 362-23414 | ||||||||||||||||||||||||
1386 | break; executed 362 times by 1 test: break; Executed by:
| 362 | ||||||||||||||||||||||||
1387 | } executed 23414 times by 1 test: end of block Executed by:
| 23414 | ||||||||||||||||||||||||
1388 | ret = 1; | - | ||||||||||||||||||||||||
1389 | err: code before this statement executed 660 times by 1 test: err: Executed by:
| 660 | ||||||||||||||||||||||||
1390 | BN_CTX_end(ctx); | - | ||||||||||||||||||||||||
1391 | bn_check_top(r); | - | ||||||||||||||||||||||||
1392 | return ret; executed 716 times by 1 test: return ret; Executed by:
| 716 | ||||||||||||||||||||||||
1393 | } | - | ||||||||||||||||||||||||
Source code | Switch to Preprocessed file |