bn_mod.c revision 296465 
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 */
120int 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
127int 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    if (!(BN_mod(r, m, d, ctx)))
135        return 0;
136    if (!r->neg)
137        return 1;
138    /* now   -|d| < r < 0,  so we have to set  r := r + |d| */
139    return (d->neg ? BN_sub : BN_add) (r, r, d);
140}
141
142int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
143               BN_CTX *ctx)
144{
145    if (!BN_add(r, a, b))
146        return 0;
147    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 */
154int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
155                     const BIGNUM *m)
156{
157    if (!BN_uadd(r, a, b))
158        return 0;
159    if (BN_ucmp(r, m) >= 0)
160        return BN_usub(r, r, m);
161    return 1;
162}
163
164int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m,
165               BN_CTX *ctx)
166{
167    if (!BN_sub(r, a, b))
168        return 0;
169    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 */
176int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
177                     const BIGNUM *m)
178{
179    if (!BN_sub(r, a, b))
180        return 0;
181    if (r->neg)
182        return BN_add(r, r, m);
183    return 1;
184}
185
186/* slow but works */
187int 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    BN_CTX_start(ctx);
198    if ((t = BN_CTX_get(ctx)) == NULL)
199        goto err;
200    if (a == b) {
201        if (!BN_sqr(t, a, ctx))
202            goto err;
203    } else {
204        if (!BN_mul(t, a, b, ctx))
205            goto err;
206    }
207    if (!BN_nnmod(r, t, m, ctx))
208        goto err;
209    bn_check_top(r);
210    ret = 1;
211 err:
212    BN_CTX_end(ctx);
213    return (ret);
214}
215
216int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
217{
218    if (!BN_sqr(r, a, ctx))
219        return 0;
220    /* r->neg == 0,  thus we don't need BN_nnmod */
221    return BN_mod(r, r, m, ctx);
222}
223
224int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
225{
226    if (!BN_lshift1(r, a))
227        return 0;
228    bn_check_top(r);
229    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 */
236int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
237{
238    if (!BN_lshift1(r, a))
239        return 0;
240    bn_check_top(r);
241    if (BN_cmp(r, m) >= 0)
242        return BN_sub(r, r, m);
243    return 1;
244}
245
246int 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    if (!BN_nnmod(r, a, m, ctx))
253        return 0;
254
255    if (m->neg) {
256        abs_m = BN_dup(m);
257        if (abs_m == NULL)
258            return 0;
259        abs_m->neg = 0;
260    }
261
262    ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
263    bn_check_top(r);
264
265    if (abs_m)
266        BN_free(abs_m);
267    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 */
274int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
275{
276    if (r != a) {
277        if (BN_copy(r, a) == NULL)
278            return 0;
279    }
280
281    while (n > 0) {
282        int max_shift;
283
284        /* 0 < r < m */
285        max_shift = BN_num_bits(m) - BN_num_bits(r);
286        /* max_shift >= 0 */
287
288        if (max_shift < 0) {
289            BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
290            return 0;
291        }
292
293        if (max_shift > n)
294            max_shift = n;
295
296        if (max_shift) {
297            if (!BN_lshift(r, r, max_shift))
298                return 0;
299            n -= max_shift;
300        } else {
301            if (!BN_lshift1(r, r))
302                return 0;
303            --n;
304        }
305
306        /* BN_num_bits(r) <= BN_num_bits(m) */
307
308        if (BN_cmp(r, m) >= 0) {
309            if (!BN_sub(r, r, m))
310                return 0;
311        }
312    }
313    bn_check_top(r);
314
315    return 1;
316}
317