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