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