Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/openssl/src/crypto/bn/bn_mod.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||
---|---|---|---|---|---|---|---|---|
1 | /* | - | ||||||
2 | * Copyright 1998-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 "bn_lcl.h" | - | ||||||
12 | - | |||||||
13 | int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) | - | ||||||
14 | { | - | ||||||
15 | /* | - | ||||||
16 | * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d| | - | ||||||
17 | * always holds) | - | ||||||
18 | */ | - | ||||||
19 | - | |||||||
20 | if (!(BN_mod(r, m, d, ctx)))
| 2-4223126 | ||||||
21 | return 0; executed 2 times by 1 test: return 0; Executed by:
| 2 | ||||||
22 | if (!r->neg)
| 46681-4176445 | ||||||
23 | return 1; executed 4176445 times by 2 tests: return 1; Executed by:
| 4176445 | ||||||
24 | /* now -|d| < r < 0, so we have to set r := r + |d| */ | - | ||||||
25 | return (d->neg ? BN_sub : BN_add) (r, r, d); executed 46681 times by 2 tests: return (d->neg ? BN_sub : BN_add) (r, r, d); Executed by:
| 208-46681 | ||||||
26 | } | - | ||||||
27 | - | |||||||
28 | int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
29 | BN_CTX *ctx) | - | ||||||
30 | { | - | ||||||
31 | if (!BN_add(r, a, b))
| 0-104 | ||||||
32 | return 0; never executed: return 0; | 0 | ||||||
33 | return BN_nnmod(r, r, m, ctx); executed 104 times by 2 tests: return BN_nnmod(r, r, m, ctx); Executed by:
| 104 | ||||||
34 | } | - | ||||||
35 | - | |||||||
36 | /* | - | ||||||
37 | * BN_mod_add variant that may be used if both a and b are non-negative and | - | ||||||
38 | * less than m. The original algorithm was | - | ||||||
39 | * | - | ||||||
40 | * if (!BN_uadd(r, a, b)) | - | ||||||
41 | * return 0; | - | ||||||
42 | * if (BN_ucmp(r, m) >= 0) | - | ||||||
43 | * return BN_usub(r, r, m); | - | ||||||
44 | * | - | ||||||
45 | * which is replaced with addition, subtracting modulus, and conditional | - | ||||||
46 | * move depending on whether or not subtraction borrowed. | - | ||||||
47 | */ | - | ||||||
48 | int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | - | ||||||
49 | const BIGNUM *m) | - | ||||||
50 | { | - | ||||||
51 | size_t i, ai, bi, mtop = m->top; | - | ||||||
52 | BN_ULONG storage[1024 / BN_BITS2]; | - | ||||||
53 | BN_ULONG carry, temp, mask, *rp, *tp = storage; | - | ||||||
54 | const BN_ULONG *ap, *bp; | - | ||||||
55 | - | |||||||
56 | if (bn_wexpand(r, mtop) == NULL)
| 0-4337421 | ||||||
57 | return 0; never executed: return 0; | 0 | ||||||
58 | - | |||||||
59 | if (mtop > sizeof(storage) / sizeof(storage[0])
| 1868-4335553 | ||||||
60 | && (tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG))) == NULL)
| 0-1868 | ||||||
61 | return 0; never executed: return 0; | 0 | ||||||
62 | - | |||||||
63 | ap = a->d != NULL ? a->d : tp;
| 0-4337421 | ||||||
64 | bp = b->d != NULL ? b->d : tp;
| 298-4337123 | ||||||
65 | - | |||||||
66 | for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) {
| 4337421-27221631 | ||||||
67 | mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); | - | ||||||
68 | temp = ((ap[ai] & mask) + carry) & BN_MASK2; | - | ||||||
69 | carry = (temp < carry); | - | ||||||
70 | - | |||||||
71 | mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); | - | ||||||
72 | tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2; | - | ||||||
73 | carry += (tp[i] < temp); | - | ||||||
74 | - | |||||||
75 | i++; | - | ||||||
76 | ai += (i - a->dmax) >> (8 * sizeof(i) - 1); | - | ||||||
77 | bi += (i - b->dmax) >> (8 * sizeof(i) - 1); | - | ||||||
78 | } executed 27221631 times by 2 tests: end of block Executed by:
| 27221631 | ||||||
79 | rp = r->d; | - | ||||||
80 | carry -= bn_sub_words(rp, tp, m->d, mtop); | - | ||||||
81 | for (i = 0; i < mtop; i++) {
| 4337421-27221631 | ||||||
82 | rp[i] = (carry & tp[i]) | (~carry & rp[i]); | - | ||||||
83 | ((volatile BN_ULONG *)tp)[i] = 0; | - | ||||||
84 | } executed 27221631 times by 2 tests: end of block Executed by:
| 27221631 | ||||||
85 | r->top = mtop; | - | ||||||
86 | r->flags |= BN_FLG_FIXED_TOP; | - | ||||||
87 | r->neg = 0; | - | ||||||
88 | - | |||||||
89 | if (tp != storage)
| 1868-4335553 | ||||||
90 | OPENSSL_free(tp); executed 1868 times by 1 test: CRYPTO_free(tp, __FILE__, 90); Executed by:
| 1868 | ||||||
91 | - | |||||||
92 | return 1; executed 4337421 times by 2 tests: return 1; Executed by:
| 4337421 | ||||||
93 | } | - | ||||||
94 | - | |||||||
95 | int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | - | ||||||
96 | const BIGNUM *m) | - | ||||||
97 | { | - | ||||||
98 | int ret = bn_mod_add_fixed_top(r, a, b, m); | - | ||||||
99 | - | |||||||
100 | if (ret)
| 0-4334680 | ||||||
101 | bn_correct_top(r); executed 4334680 times by 2 tests: bn_correct_top(r); Executed by:
| 4334680 | ||||||
102 | - | |||||||
103 | return ret; executed 4334680 times by 2 tests: return ret; Executed by:
| 4334680 | ||||||
104 | } | - | ||||||
105 | - | |||||||
106 | int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
107 | BN_CTX *ctx) | - | ||||||
108 | { | - | ||||||
109 | if (!BN_sub(r, a, b))
| 0-13 | ||||||
110 | return 0; never executed: return 0; | 0 | ||||||
111 | return BN_nnmod(r, r, m, ctx); executed 13 times by 1 test: return BN_nnmod(r, r, m, ctx); Executed by:
| 13 | ||||||
112 | } | - | ||||||
113 | - | |||||||
114 | /* | - | ||||||
115 | * BN_mod_sub variant that may be used if both a and b are non-negative, | - | ||||||
116 | * a is less than m, while b is of same bit width as m. It's implemented | - | ||||||
117 | * as subtraction followed by two conditional additions. | - | ||||||
118 | * | - | ||||||
119 | * 0 <= a < m | - | ||||||
120 | * 0 <= b < 2^w < 2*m | - | ||||||
121 | * | - | ||||||
122 | * after subtraction | - | ||||||
123 | * | - | ||||||
124 | * -2*m < r = a - b < m | - | ||||||
125 | * | - | ||||||
126 | * Thus it takes up to two conditional additions to make |r| positive. | - | ||||||
127 | */ | - | ||||||
128 | int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | - | ||||||
129 | const BIGNUM *m) | - | ||||||
130 | { | - | ||||||
131 | size_t i, ai, bi, mtop = m->top; | - | ||||||
132 | BN_ULONG borrow, carry, ta, tb, mask, *rp; | - | ||||||
133 | const BN_ULONG *ap, *bp; | - | ||||||
134 | - | |||||||
135 | if (bn_wexpand(r, mtop) == NULL)
| 0-2374 | ||||||
136 | return 0; never executed: return 0; | 0 | ||||||
137 | - | |||||||
138 | rp = r->d; | - | ||||||
139 | ap = a->d != NULL ? a->d : rp;
| 0-2374 | ||||||
140 | bp = b->d != NULL ? b->d : rp;
| 0-2374 | ||||||
141 | - | |||||||
142 | for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) {
| 2374-32678 | ||||||
143 | mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); | - | ||||||
144 | ta = ap[ai] & mask; | - | ||||||
145 | - | |||||||
146 | mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); | - | ||||||
147 | tb = bp[bi] & mask; | - | ||||||
148 | rp[i] = ta - tb - borrow; | - | ||||||
149 | if (ta != tb)
| 43-32635 | ||||||
150 | borrow = (ta < tb); executed 32635 times by 1 test: borrow = (ta < tb); Executed by:
| 32635 | ||||||
151 | - | |||||||
152 | i++; | - | ||||||
153 | ai += (i - a->dmax) >> (8 * sizeof(i) - 1); | - | ||||||
154 | bi += (i - b->dmax) >> (8 * sizeof(i) - 1); | - | ||||||
155 | } executed 32678 times by 1 test: end of block Executed by:
| 32678 | ||||||
156 | ap = m->d; | - | ||||||
157 | for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
| 2374-32678 | ||||||
158 | ta = ((ap[i] & mask) + carry) & BN_MASK2; | - | ||||||
159 | carry = (ta < carry); | - | ||||||
160 | rp[i] = (rp[i] + ta) & BN_MASK2; | - | ||||||
161 | carry += (rp[i] < ta); | - | ||||||
162 | } executed 32678 times by 1 test: end of block Executed by:
| 32678 | ||||||
163 | borrow -= carry; | - | ||||||
164 | for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) {
| 2374-32678 | ||||||
165 | ta = ((ap[i] & mask) + carry) & BN_MASK2; | - | ||||||
166 | carry = (ta < carry); | - | ||||||
167 | rp[i] = (rp[i] + ta) & BN_MASK2; | - | ||||||
168 | carry += (rp[i] < ta); | - | ||||||
169 | } executed 32678 times by 1 test: end of block Executed by:
| 32678 | ||||||
170 | - | |||||||
171 | r->top = mtop; | - | ||||||
172 | r->flags |= BN_FLG_FIXED_TOP; | - | ||||||
173 | r->neg = 0; | - | ||||||
174 | - | |||||||
175 | return 1; executed 2374 times by 1 test: return 1; Executed by:
| 2374 | ||||||
176 | } | - | ||||||
177 | - | |||||||
178 | /* | - | ||||||
179 | * BN_mod_sub variant that may be used if both a and b are non-negative and | - | ||||||
180 | * less than m | - | ||||||
181 | */ | - | ||||||
182 | int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | - | ||||||
183 | const BIGNUM *m) | - | ||||||
184 | { | - | ||||||
185 | if (!BN_sub(r, a, b))
| 0-4650717 | ||||||
186 | return 0; never executed: return 0; | 0 | ||||||
187 | if (r->neg)
| 2309212-2341505 | ||||||
188 | return BN_add(r, r, m); executed 2309212 times by 2 tests: return BN_add(r, r, m); Executed by:
| 2309212 | ||||||
189 | return 1; executed 2341505 times by 2 tests: return 1; Executed by:
| 2341505 | ||||||
190 | } | - | ||||||
191 | - | |||||||
192 | /* slow but works */ | - | ||||||
193 | int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
194 | BN_CTX *ctx) | - | ||||||
195 | { | - | ||||||
196 | BIGNUM *t; | - | ||||||
197 | int ret = 0; | - | ||||||
198 | - | |||||||
199 | bn_check_top(a); | - | ||||||
200 | bn_check_top(b); | - | ||||||
201 | bn_check_top(m); | - | ||||||
202 | - | |||||||
203 | BN_CTX_start(ctx); | - | ||||||
204 | if ((t = BN_CTX_get(ctx)) == NULL)
| 0-3791466 | ||||||
205 | goto err; never executed: goto err; | 0 | ||||||
206 | if (a == b) {
| 189583-3601883 | ||||||
207 | if (!BN_sqr(t, a, ctx))
| 0-3601883 | ||||||
208 | goto err; never executed: goto err; | 0 | ||||||
209 | } else { executed 3601883 times by 1 test: end of block Executed by:
| 3601883 | ||||||
210 | if (!BN_mul(t, a, b, ctx))
| 0-189583 | ||||||
211 | goto err; never executed: goto err; | 0 | ||||||
212 | } executed 189583 times by 2 tests: end of block Executed by:
| 189583 | ||||||
213 | if (!BN_nnmod(r, t, m, ctx))
| 1-3791465 | ||||||
214 | goto err; executed 1 time by 1 test: goto err; Executed by:
| 1 | ||||||
215 | bn_check_top(r); | - | ||||||
216 | ret = 1; | - | ||||||
217 | err: code before this statement executed 3791465 times by 2 tests: err: Executed by:
| 3791465 | ||||||
218 | BN_CTX_end(ctx); | - | ||||||
219 | return ret; executed 3791466 times by 2 tests: return ret; Executed by:
| 3791466 | ||||||
220 | } | - | ||||||
221 | - | |||||||
222 | int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
223 | { | - | ||||||
224 | if (!BN_sqr(r, a, ctx))
| 0-147879 | ||||||
225 | return 0; never executed: return 0; | 0 | ||||||
226 | /* r->neg == 0, thus we don't need BN_nnmod */ | - | ||||||
227 | return BN_mod(r, r, m, ctx); executed 147879 times by 2 tests: return BN_div( ((void *)0) ,(r),(r),(m),(ctx)); Executed by:
| 147879 | ||||||
228 | } | - | ||||||
229 | - | |||||||
230 | int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
231 | { | - | ||||||
232 | if (!BN_lshift1(r, a))
| 0 | ||||||
233 | return 0; never executed: return 0; | 0 | ||||||
234 | bn_check_top(r); | - | ||||||
235 | return BN_nnmod(r, r, m, ctx); never executed: return BN_nnmod(r, r, m, ctx); | 0 | ||||||
236 | } | - | ||||||
237 | - | |||||||
238 | /* | - | ||||||
239 | * BN_mod_lshift1 variant that may be used if a is non-negative and less than | - | ||||||
240 | * m | - | ||||||
241 | */ | - | ||||||
242 | int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) | - | ||||||
243 | { | - | ||||||
244 | if (!BN_lshift1(r, a))
| 0-1775606 | ||||||
245 | return 0; never executed: return 0; | 0 | ||||||
246 | bn_check_top(r); | - | ||||||
247 | if (BN_cmp(r, m) >= 0)
| 883028-892578 | ||||||
248 | return BN_sub(r, r, m); executed 892578 times by 2 tests: return BN_sub(r, r, m); Executed by:
| 892578 | ||||||
249 | return 1; executed 883028 times by 2 tests: return 1; Executed by:
| 883028 | ||||||
250 | } | - | ||||||
251 | - | |||||||
252 | int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, | - | ||||||
253 | BN_CTX *ctx) | - | ||||||
254 | { | - | ||||||
255 | BIGNUM *abs_m = NULL; | - | ||||||
256 | int ret; | - | ||||||
257 | - | |||||||
258 | if (!BN_nnmod(r, a, m, ctx))
| 0 | ||||||
259 | return 0; never executed: return 0; | 0 | ||||||
260 | - | |||||||
261 | if (m->neg) {
| 0 | ||||||
262 | abs_m = BN_dup(m); | - | ||||||
263 | if (abs_m == NULL)
| 0 | ||||||
264 | return 0; never executed: return 0; | 0 | ||||||
265 | abs_m->neg = 0; | - | ||||||
266 | } never executed: end of block | 0 | ||||||
267 | - | |||||||
268 | ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); | - | ||||||
269 | bn_check_top(r); | - | ||||||
270 | - | |||||||
271 | BN_free(abs_m); | - | ||||||
272 | return ret; never executed: return ret; | 0 | ||||||
273 | } | - | ||||||
274 | - | |||||||
275 | /* | - | ||||||
276 | * BN_mod_lshift variant that may be used if a is non-negative and less than | - | ||||||
277 | * m | - | ||||||
278 | */ | - | ||||||
279 | int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) | - | ||||||
280 | { | - | ||||||
281 | if (r != a) {
| 151159-783904 | ||||||
282 | if (BN_copy(r, a) == NULL)
| 0-783904 | ||||||
283 | return 0; never executed: return 0; | 0 | ||||||
284 | } executed 783904 times by 2 tests: end of block Executed by:
| 783904 | ||||||
285 | - | |||||||
286 | while (n > 0) {
| 935063-1530937 | ||||||
287 | int max_shift; | - | ||||||
288 | - | |||||||
289 | /* 0 < r < m */ | - | ||||||
290 | max_shift = BN_num_bits(m) - BN_num_bits(r); | - | ||||||
291 | /* max_shift >= 0 */ | - | ||||||
292 | - | |||||||
293 | if (max_shift < 0) {
| 0-1530937 | ||||||
294 | BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED); | - | ||||||
295 | return 0; never executed: return 0; | 0 | ||||||
296 | } | - | ||||||
297 | - | |||||||
298 | if (max_shift > n)
| 185297-1345640 | ||||||
299 | max_shift = n; executed 185297 times by 2 tests: max_shift = n; Executed by:
| 185297 | ||||||
300 | - | |||||||
301 | if (max_shift) {
| 694555-836382 | ||||||
302 | if (!BN_lshift(r, r, max_shift))
| 0-836382 | ||||||
303 | return 0; never executed: return 0; | 0 | ||||||
304 | n -= max_shift; | - | ||||||
305 | } else { executed 836382 times by 2 tests: end of block Executed by:
| 836382 | ||||||
306 | if (!BN_lshift1(r, r))
| 0-694555 | ||||||
307 | return 0; never executed: return 0; | 0 | ||||||
308 | --n; | - | ||||||
309 | } executed 694555 times by 2 tests: end of block Executed by:
| 694555 | ||||||
310 | - | |||||||
311 | /* BN_num_bits(r) <= BN_num_bits(m) */ | - | ||||||
312 | - | |||||||
313 | if (BN_cmp(r, m) >= 0) {
| 730613-800324 | ||||||
314 | if (!BN_sub(r, r, m))
| 0-800324 | ||||||
315 | return 0; never executed: return 0; | 0 | ||||||
316 | } executed 800324 times by 2 tests: end of block Executed by:
| 800324 | ||||||
317 | } executed 1530937 times by 2 tests: end of block Executed by:
| 1530937 | ||||||
318 | bn_check_top(r); | - | ||||||
319 | - | |||||||
320 | return 1; executed 935063 times by 2 tests: return 1; Executed by:
| 935063 | ||||||
321 | } | - | ||||||
Source code | Switch to Preprocessed file |