Branch data Line data Source code
1 : : /* crypto/bn/bn_mod.c */
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 : : #define OPENSSL_FIPSAPI
115 : :
116 : : #include "cryptlib.h"
117 : : #include "bn_lcl.h"
118 : :
119 : :
120 : : #if 0 /* now just a #define */
121 : : int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
122 : : {
123 : : return(BN_div(NULL,rem,m,d,ctx));
124 : : /* note that rem->neg == m->neg (unless the remainder is zero) */
125 : : }
126 : : #endif
127 : :
128 : :
129 : 130340 : int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
130 : : {
131 : : /* like BN_mod, but returns non-negative remainder
132 : : * (i.e., 0 <= r < |d| always holds) */
133 : :
134 [ + - ]: 130340 : if (!(BN_mod(r,m,d,ctx)))
135 : : return 0;
136 [ + + ]: 130340 : if (!r->neg)
137 : : return 1;
138 : : /* now -|d| < r < 0, so we have to set r := r + |d| */
139 [ + - ]: 10300 : return (d->neg ? BN_sub : BN_add)(r, r, d);
140 : : }
141 : :
142 : :
143 : 81 : int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
144 : : {
145 [ + - ]: 81 : if (!BN_add(r, a, b)) return 0;
146 : 81 : return BN_nnmod(r, r, m, ctx);
147 : : }
148 : :
149 : :
150 : : /* BN_mod_add variant that may be used if both a and b are non-negative
151 : : * and less than m */
152 : 290019 : int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
153 : : {
154 [ + - ]: 290019 : if (!BN_uadd(r, a, b)) return 0;
155 [ + + ]: 290019 : if (BN_ucmp(r, m) >= 0)
156 : 139656 : return BN_usub(r, r, m);
157 : : return 1;
158 : : }
159 : :
160 : :
161 : 24 : int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
162 : : {
163 [ + - ]: 24 : if (!BN_sub(r, a, b)) return 0;
164 : 24 : return BN_nnmod(r, r, m, ctx);
165 : : }
166 : :
167 : :
168 : : /* BN_mod_sub variant that may be used if both a and b are non-negative
169 : : * and less than m */
170 : 572862 : int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
171 : : {
172 [ + - ]: 572862 : if (!BN_sub(r, a, b)) return 0;
173 [ + + ]: 572862 : if (r->neg)
174 : 286611 : return BN_add(r, r, m);
175 : : return 1;
176 : : }
177 : :
178 : :
179 : : /* slow but works */
180 : 89487 : int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
181 : : BN_CTX *ctx)
182 : : {
183 : : BIGNUM *t;
184 : 89487 : int ret=0;
185 : :
186 : : bn_check_top(a);
187 : : bn_check_top(b);
188 : : bn_check_top(m);
189 : :
190 : 89487 : BN_CTX_start(ctx);
191 [ + - ]: 89487 : if ((t = BN_CTX_get(ctx)) == NULL) goto err;
192 [ + + ]: 89487 : if (a == b)
193 [ + - ]: 71158 : { if (!BN_sqr(t,a,ctx)) goto err; }
194 : : else
195 [ + - ]: 18329 : { if (!BN_mul(t,a,b,ctx)) goto err; }
196 [ + - ]: 89487 : if (!BN_nnmod(r,t,m,ctx)) goto err;
197 : : bn_check_top(r);
198 : 89487 : ret=1;
199 : : err:
200 : 89487 : BN_CTX_end(ctx);
201 : 89487 : return(ret);
202 : : }
203 : :
204 : :
205 : 785 : int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
206 : : {
207 [ + - ]: 785 : if (!BN_sqr(r, a, ctx)) return 0;
208 : : /* r->neg == 0, thus we don't need BN_nnmod */
209 : 785 : return BN_mod(r, r, m, ctx);
210 : : }
211 : :
212 : :
213 : 0 : int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
214 : : {
215 [ # # ]: 0 : if (!BN_lshift1(r, a)) return 0;
216 : : bn_check_top(r);
217 : 0 : return BN_nnmod(r, r, m, ctx);
218 : : }
219 : :
220 : :
221 : : /* BN_mod_lshift1 variant that may be used if a is non-negative
222 : : * and less than m */
223 : 370761 : int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
224 : : {
225 [ + - ]: 370761 : if (!BN_lshift1(r, a)) return 0;
226 : : bn_check_top(r);
227 [ + + ]: 370761 : if (BN_cmp(r, m) >= 0)
228 : 185047 : return BN_sub(r, r, m);
229 : : return 1;
230 : : }
231 : :
232 : :
233 : 0 : int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)
234 : : {
235 : 0 : BIGNUM *abs_m = NULL;
236 : : int ret;
237 : :
238 [ # # ]: 0 : if (!BN_nnmod(r, a, m, ctx)) return 0;
239 : :
240 [ # # ]: 0 : if (m->neg)
241 : : {
242 : 0 : abs_m = BN_dup(m);
243 [ # # ]: 0 : if (abs_m == NULL) return 0;
244 : 0 : abs_m->neg = 0;
245 : : }
246 : :
247 [ # # ]: 0 : ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
248 : : bn_check_top(r);
249 : :
250 [ # # ]: 0 : if (abs_m)
251 : 0 : BN_free(abs_m);
252 : 0 : return ret;
253 : : }
254 : :
255 : :
256 : : /* BN_mod_lshift variant that may be used if a is non-negative
257 : : * and less than m */
258 : 225836 : int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
259 : : {
260 [ + + ]: 338754 : if (r != a)
261 : : {
262 [ + - ]: 112918 : if (BN_copy(r, a) == NULL) return 0;
263 : : }
264 : :
265 [ + + ]: 688763 : while (n > 0)
266 : : {
267 : : int max_shift;
268 : :
269 : : /* 0 < r < m */
270 : 462927 : max_shift = BN_num_bits(m) - BN_num_bits(r);
271 : : /* max_shift >= 0 */
272 : :
273 [ - + ]: 462927 : if (max_shift < 0)
274 : : {
275 : 0 : BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
276 : 0 : return 0;
277 : : }
278 : :
279 [ + + ]: 462927 : if (max_shift > n)
280 : 67568 : max_shift = n;
281 : :
282 [ + + ]: 462927 : if (max_shift)
283 : : {
284 [ + - ]: 236227 : if (!BN_lshift(r, r, max_shift)) return 0;
285 : 236227 : n -= max_shift;
286 : : }
287 : : else
288 : : {
289 [ + - ]: 226700 : if (!BN_lshift1(r, r)) return 0;
290 : 226700 : --n;
291 : : }
292 : :
293 : : /* BN_num_bits(r) <= BN_num_bits(m) */
294 : :
295 [ + + ]: 462927 : if (BN_cmp(r, m) >= 0)
296 : : {
297 [ + - ]: 462927 : if (!BN_sub(r, r, m)) return 0;
298 : : }
299 : : }
300 : : bn_check_top(r);
301 : :
302 : : return 1;
303 : : }
|
