Absolute File Name: | /home/opencoverage/opencoverage/guest-scripts/libressl/src/crypto/bn/bn_mod.c |
Source code | Switch to Preprocessed file |
Line | Source | Count | ||||||
---|---|---|---|---|---|---|---|---|
1 | /* $OpenBSD: bn_mod.c,v 1.12 2017/01/29 17:49:22 beck Exp $ */ | - | ||||||
2 | /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> | - | ||||||
3 | * for the OpenSSL project. */ | - | ||||||
4 | /* ==================================================================== | - | ||||||
5 | * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. | - | ||||||
6 | * | - | ||||||
7 | * Redistribution and use in source and binary forms, with or without | - | ||||||
8 | * modification, are permitted provided that the following conditions | - | ||||||
9 | * are met: | - | ||||||
10 | * | - | ||||||
11 | * 1. Redistributions of source code must retain the above copyright | - | ||||||
12 | * notice, this list of conditions and the following disclaimer. | - | ||||||
13 | * | - | ||||||
14 | * 2. Redistributions in binary form must reproduce the above copyright | - | ||||||
15 | * notice, this list of conditions and the following disclaimer in | - | ||||||
16 | * the documentation and/or other materials provided with the | - | ||||||
17 | * distribution. | - | ||||||
18 | * | - | ||||||
19 | * 3. All advertising materials mentioning features or use of this | - | ||||||
20 | * software must display the following acknowledgment: | - | ||||||
21 | * "This product includes software developed by the OpenSSL Project | - | ||||||
22 | * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" | - | ||||||
23 | * | - | ||||||
24 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | - | ||||||
25 | * endorse or promote products derived from this software without | - | ||||||
26 | * prior written permission. For written permission, please contact | - | ||||||
27 | * openssl-core@openssl.org. | - | ||||||
28 | * | - | ||||||
29 | * 5. Products derived from this software may not be called "OpenSSL" | - | ||||||
30 | * nor may "OpenSSL" appear in their names without prior written | - | ||||||
31 | * permission of the OpenSSL Project. | - | ||||||
32 | * | - | ||||||
33 | * 6. Redistributions of any form whatsoever must retain the following | - | ||||||
34 | * acknowledgment: | - | ||||||
35 | * "This product includes software developed by the OpenSSL Project | - | ||||||
36 | * for use in the OpenSSL Toolkit (http://www.openssl.org/)" | - | ||||||
37 | * | - | ||||||
38 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | - | ||||||
39 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | - | ||||||
40 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | - | ||||||
41 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | - | ||||||
42 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | - | ||||||
43 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | - | ||||||
44 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | - | ||||||
45 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | - | ||||||
46 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | - | ||||||
47 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | - | ||||||
48 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | - | ||||||
49 | * OF THE POSSIBILITY OF SUCH DAMAGE. | - | ||||||
50 | * ==================================================================== | - | ||||||
51 | * | - | ||||||
52 | * This product includes cryptographic software written by Eric Young | - | ||||||
53 | * (eay@cryptsoft.com). This product includes software written by Tim | - | ||||||
54 | * Hudson (tjh@cryptsoft.com). | - | ||||||
55 | * | - | ||||||
56 | */ | - | ||||||
57 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) | - | ||||||
58 | * All rights reserved. | - | ||||||
59 | * | - | ||||||
60 | * This package is an SSL implementation written | - | ||||||
61 | * by Eric Young (eay@cryptsoft.com). | - | ||||||
62 | * The implementation was written so as to conform with Netscapes SSL. | - | ||||||
63 | * | - | ||||||
64 | * This library is free for commercial and non-commercial use as long as | - | ||||||
65 | * the following conditions are aheared to. The following conditions | - | ||||||
66 | * apply to all code found in this distribution, be it the RC4, RSA, | - | ||||||
67 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | - | ||||||
68 | * included with this distribution is covered by the same copyright terms | - | ||||||
69 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | - | ||||||
70 | * | - | ||||||
71 | * Copyright remains Eric Young's, and as such any Copyright notices in | - | ||||||
72 | * the code are not to be removed. | - | ||||||
73 | * If this package is used in a product, Eric Young should be given attribution | - | ||||||
74 | * as the author of the parts of the library used. | - | ||||||
75 | * This can be in the form of a textual message at program startup or | - | ||||||
76 | * in documentation (online or textual) provided with the package. | - | ||||||
77 | * | - | ||||||
78 | * Redistribution and use in source and binary forms, with or without | - | ||||||
79 | * modification, are permitted provided that the following conditions | - | ||||||
80 | * are met: | - | ||||||
81 | * 1. Redistributions of source code must retain the copyright | - | ||||||
82 | * notice, this list of conditions and the following disclaimer. | - | ||||||
83 | * 2. Redistributions in binary form must reproduce the above copyright | - | ||||||
84 | * notice, this list of conditions and the following disclaimer in the | - | ||||||
85 | * documentation and/or other materials provided with the distribution. | - | ||||||
86 | * 3. All advertising materials mentioning features or use of this software | - | ||||||
87 | * must display the following acknowledgement: | - | ||||||
88 | * "This product includes cryptographic software written by | - | ||||||
89 | * Eric Young (eay@cryptsoft.com)" | - | ||||||
90 | * The word 'cryptographic' can be left out if the rouines from the library | - | ||||||
91 | * being used are not cryptographic related :-). | - | ||||||
92 | * 4. If you include any Windows specific code (or a derivative thereof) from | - | ||||||
93 | * the apps directory (application code) you must include an acknowledgement: | - | ||||||
94 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | - | ||||||
95 | * | - | ||||||
96 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND | - | ||||||
97 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | - | ||||||
98 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | - | ||||||
99 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | - | ||||||
100 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | - | ||||||
101 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | - | ||||||
102 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | - | ||||||
103 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | - | ||||||
104 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | - | ||||||
105 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | - | ||||||
106 | * SUCH DAMAGE. | - | ||||||
107 | * | - | ||||||
108 | * The licence and distribution terms for any publically available version or | - | ||||||
109 | * derivative of this code cannot be changed. i.e. this code cannot simply be | - | ||||||
110 | * copied and put under another distribution licence | - | ||||||
111 | * [including the GNU Public Licence.] | - | ||||||
112 | */ | - | ||||||
113 | - | |||||||
114 | #include <openssl/err.h> | - | ||||||
115 | - | |||||||
116 | #include "bn_lcl.h" | - | ||||||
117 | - | |||||||
118 | int | - | ||||||
119 | BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) | - | ||||||
120 | { | - | ||||||
121 | /* like BN_mod, but returns non-negative remainder | - | ||||||
122 | * (i.e., 0 <= r < |d| always holds) */ | - | ||||||
123 | - | |||||||
124 | if (!(BN_mod_ct(r, m,d, ctx)))
| 5-112872 | ||||||
125 | return 0; executed 5 times by 1 test: return 0; Executed by:
| 5 | ||||||
126 | if (!r->neg)
| 243-112629 | ||||||
127 | return 1; executed 112629 times by 14 tests: return 1; Executed by:
| 112629 | ||||||
128 | /* now -|d| < r < 0, so we have to set r := r + |d| */ | - | ||||||
129 | if (d->neg)
| 0-243 | ||||||
130 | return BN_sub(r, r, d); never executed: return BN_sub(r, r, d); | 0 | ||||||
131 | else | - | ||||||
132 | return BN_add(r, r, d); executed 243 times by 2 tests: return BN_add(r, r, d); Executed by:
| 243 | ||||||
133 | } | - | ||||||
134 | - | |||||||
135 | int | - | ||||||
136 | BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
137 | BN_CTX *ctx) | - | ||||||
138 | { | - | ||||||
139 | if (!BN_add(r, a, b))
| 0-120 | ||||||
140 | return 0; never executed: return 0; | 0 | ||||||
141 | return BN_nnmod(r, r, m, ctx); executed 120 times by 4 tests: return BN_nnmod(r, r, m, ctx); Executed by:
| 120 | ||||||
142 | } | - | ||||||
143 | - | |||||||
144 | /* BN_mod_add variant that may be used if both a and b are non-negative | - | ||||||
145 | * and less than m */ | - | ||||||
146 | int | - | ||||||
147 | BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) | - | ||||||
148 | { | - | ||||||
149 | if (!BN_uadd(r, a, b))
| 0-585006 | ||||||
150 | return 0; never executed: return 0; | 0 | ||||||
151 | if (BN_ucmp(r, m) >= 0)
| 287369-297637 | ||||||
152 | return BN_usub(r, r, m); executed 287369 times by 4 tests: return BN_usub(r, r, m); Executed by:
| 287369 | ||||||
153 | return 1; executed 297637 times by 4 tests: return 1; Executed by:
| 297637 | ||||||
154 | } | - | ||||||
155 | - | |||||||
156 | int | - | ||||||
157 | BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
158 | BN_CTX *ctx) | - | ||||||
159 | { | - | ||||||
160 | if (!BN_sub(r, a, b))
| 0 | ||||||
161 | return 0; never executed: return 0; | 0 | ||||||
162 | return BN_nnmod(r, r, m, ctx); never executed: return BN_nnmod(r, r, m, ctx); | 0 | ||||||
163 | } | - | ||||||
164 | - | |||||||
165 | /* BN_mod_sub variant that may be used if both a and b are non-negative | - | ||||||
166 | * and less than m */ | - | ||||||
167 | int | - | ||||||
168 | BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) | - | ||||||
169 | { | - | ||||||
170 | if (!BN_sub(r, a, b))
| 0-1256535 | ||||||
171 | return 0; never executed: return 0; | 0 | ||||||
172 | if (r->neg)
| 628051-628484 | ||||||
173 | return BN_add(r, r, m); executed 628484 times by 4 tests: return BN_add(r, r, m); Executed by:
| 628484 | ||||||
174 | return 1; executed 628051 times by 4 tests: return 1; Executed by:
| 628051 | ||||||
175 | } | - | ||||||
176 | - | |||||||
177 | /* slow but works */ | - | ||||||
178 | int | - | ||||||
179 | BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, | - | ||||||
180 | BN_CTX *ctx) | - | ||||||
181 | { | - | ||||||
182 | BIGNUM *t; | - | ||||||
183 | int ret = 0; | - | ||||||
184 | - | |||||||
185 | bn_check_top(a); | - | ||||||
186 | bn_check_top(b); | - | ||||||
187 | bn_check_top(m); | - | ||||||
188 | - | |||||||
189 | BN_CTX_start(ctx); | - | ||||||
190 | if ((t = BN_CTX_get(ctx)) == NULL)
| 0-88348 | ||||||
191 | goto err; never executed: goto err; | 0 | ||||||
192 | if (a == b) {
| 17056-71292 | ||||||
193 | if (!BN_sqr(t, a, ctx))
| 0-71292 | ||||||
194 | goto err; never executed: goto err; | 0 | ||||||
195 | } else { executed 71292 times by 9 tests: end of block Executed by:
| 71292 | ||||||
196 | if (!BN_mul(t, a,b, ctx))
| 0-17056 | ||||||
197 | goto err; never executed: goto err; | 0 | ||||||
198 | } executed 17056 times by 12 tests: end of block Executed by:
| 17056 | ||||||
199 | if (!BN_nnmod(r, t,m, ctx))
| 1-88347 | ||||||
200 | goto err; executed 1 time by 1 test: goto err; Executed by:
| 1 | ||||||
201 | bn_check_top(r); | - | ||||||
202 | ret = 1; | - | ||||||
203 | - | |||||||
204 | err: code before this statement executed 88347 times by 14 tests: err: Executed by:
| 88347 | ||||||
205 | BN_CTX_end(ctx); | - | ||||||
206 | return (ret); executed 88348 times by 14 tests: return (ret); Executed by:
| 88348 | ||||||
207 | } | - | ||||||
208 | - | |||||||
209 | int | - | ||||||
210 | BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
211 | { | - | ||||||
212 | if (!BN_sqr(r, a, ctx))
| 0-934 | ||||||
213 | return 0; never executed: return 0; | 0 | ||||||
214 | /* r->neg == 0, thus we don't need BN_nnmod */ | - | ||||||
215 | return BN_mod_ct(r, r, m, ctx); executed 934 times by 5 tests: return BN_div_ct( ((void *)0) ,(r),(r),(m),(ctx)); Executed by:
| 934 | ||||||
216 | } | - | ||||||
217 | - | |||||||
218 | int | - | ||||||
219 | BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
220 | { | - | ||||||
221 | if (!BN_lshift1(r, a))
| 0 | ||||||
222 | return 0; never executed: return 0; | 0 | ||||||
223 | bn_check_top(r); | - | ||||||
224 | return BN_nnmod(r, r, m, ctx); never executed: return BN_nnmod(r, r, m, ctx); | 0 | ||||||
225 | } | - | ||||||
226 | - | |||||||
227 | /* BN_mod_lshift1 variant that may be used if a is non-negative | - | ||||||
228 | * and less than m */ | - | ||||||
229 | int | - | ||||||
230 | BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) | - | ||||||
231 | { | - | ||||||
232 | if (!BN_lshift1(r, a))
| 0-618748 | ||||||
233 | return 0; never executed: return 0; | 0 | ||||||
234 | bn_check_top(r); | - | ||||||
235 | if (BN_cmp(r, m) >= 0)
| 309036-309712 | ||||||
236 | return BN_sub(r, r, m); executed 309036 times by 5 tests: return BN_sub(r, r, m); Executed by:
| 309036 | ||||||
237 | return 1; executed 309712 times by 5 tests: return 1; Executed by:
| 309712 | ||||||
238 | } | - | ||||||
239 | - | |||||||
240 | int | - | ||||||
241 | BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx) | - | ||||||
242 | { | - | ||||||
243 | BIGNUM *abs_m = NULL; | - | ||||||
244 | int ret; | - | ||||||
245 | - | |||||||
246 | if (!BN_nnmod(r, a, m, ctx))
| 0 | ||||||
247 | return 0; never executed: return 0; | 0 | ||||||
248 | - | |||||||
249 | if (m->neg) {
| 0 | ||||||
250 | abs_m = BN_dup(m); | - | ||||||
251 | if (abs_m == NULL)
| 0 | ||||||
252 | return 0; never executed: return 0; | 0 | ||||||
253 | abs_m->neg = 0; | - | ||||||
254 | } never executed: end of block | 0 | ||||||
255 | - | |||||||
256 | ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); | - | ||||||
257 | bn_check_top(r); | - | ||||||
258 | - | |||||||
259 | BN_free(abs_m); | - | ||||||
260 | return ret; never executed: return ret; | 0 | ||||||
261 | } | - | ||||||
262 | - | |||||||
263 | /* BN_mod_lshift variant that may be used if a is non-negative | - | ||||||
264 | * and less than m */ | - | ||||||
265 | int | - | ||||||
266 | BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) | - | ||||||
267 | { | - | ||||||
268 | if (r != a) {
| 163199 | ||||||
269 | if (BN_copy(r, a) == NULL)
| 0-163199 | ||||||
270 | return 0; never executed: return 0; | 0 | ||||||
271 | } executed 163199 times by 4 tests: end of block Executed by:
| 163199 | ||||||
272 | - | |||||||
273 | while (n > 0) {
| 326398-664617 | ||||||
274 | int max_shift; | - | ||||||
275 | - | |||||||
276 | /* 0 < r < m */ | - | ||||||
277 | max_shift = BN_num_bits(m) - BN_num_bits(r); | - | ||||||
278 | /* max_shift >= 0 */ | - | ||||||
279 | - | |||||||
280 | if (max_shift < 0) {
| 0-664617 | ||||||
281 | BNerror(BN_R_INPUT_NOT_REDUCED); | - | ||||||
282 | return 0; never executed: return 0; | 0 | ||||||
283 | } | - | ||||||
284 | - | |||||||
285 | if (max_shift > n)
| 100868-563749 | ||||||
286 | max_shift = n; executed 100868 times by 4 tests: max_shift = n; Executed by:
| 100868 | ||||||
287 | - | |||||||
288 | if (max_shift) {
| 313521-351096 | ||||||
289 | if (!BN_lshift(r, r, max_shift))
| 0-351096 | ||||||
290 | return 0; never executed: return 0; | 0 | ||||||
291 | n -= max_shift; | - | ||||||
292 | } else { executed 351096 times by 4 tests: end of block Executed by:
| 351096 | ||||||
293 | if (!BN_lshift1(r, r))
| 0-313521 | ||||||
294 | return 0; never executed: return 0; | 0 | ||||||
295 | --n; | - | ||||||
296 | } executed 313521 times by 4 tests: end of block Executed by:
| 313521 | ||||||
297 | - | |||||||
298 | /* BN_num_bits(r) <= BN_num_bits(m) */ | - | ||||||
299 | - | |||||||
300 | if (BN_cmp(r, m) >= 0) {
| 257533-407084 | ||||||
301 | if (!BN_sub(r, r, m))
| 0-407084 | ||||||
302 | return 0; never executed: return 0; | 0 | ||||||
303 | } executed 407084 times by 4 tests: end of block Executed by:
| 407084 | ||||||
304 | } executed 664617 times by 4 tests: end of block Executed by:
| 664617 | ||||||
305 | bn_check_top(r); | - | ||||||
306 | - | |||||||
307 | return 1; executed 326398 times by 4 tests: return 1; Executed by:
| 326398 | ||||||
308 | } | - | ||||||
Source code | Switch to Preprocessed file |