]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_mod.c
1 /* crypto/bn/bn_mod.c */
3 * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
4 * for the OpenSSL project.
6 /* ====================================================================
7 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
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
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/)"
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.
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.
35 * 6. Redistributions of any form whatsoever must retain the following
37 * "This product includes software developed by the OpenSSL Project
38 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
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 * ====================================================================
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).
59 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
60 * All rights reserved.
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.
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).
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.
80 * Redistribution and use in source and binary forms, with or without
81 * modification, are permitted provided that the following conditions
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)"
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
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.]
116 #include "cryptlib.h"
119 int BN_nnmod(BIGNUM
*r
, const BIGNUM
*m
, const BIGNUM
*d
, BN_CTX
*ctx
)
122 * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
126 if (!(BN_mod(r
, m
, d
, ctx
)))
130 /* now -|d| < r < 0, so we have to set r := r + |d| */
131 return (d
->neg
? BN_sub
: BN_add
) (r
, r
, d
);
134 int BN_mod_add(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
,
137 if (!BN_add(r
, a
, b
))
139 return BN_nnmod(r
, r
, m
, ctx
);
143 * BN_mod_add variant that may be used if both a and b are non-negative and
146 int BN_mod_add_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
149 if (!BN_uadd(r
, a
, b
))
151 if (BN_ucmp(r
, m
) >= 0)
152 return BN_usub(r
, r
, m
);
156 int BN_mod_sub(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
,
159 if (!BN_sub(r
, a
, b
))
161 return BN_nnmod(r
, r
, m
, ctx
);
165 * BN_mod_sub variant that may be used if both a and b are non-negative and
168 int BN_mod_sub_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
171 if (!BN_sub(r
, a
, b
))
174 return BN_add(r
, r
, m
);
179 int BN_mod_mul(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
,
190 if ((t
= BN_CTX_get(ctx
)) == NULL
)
193 if (!BN_sqr(t
, a
, ctx
))
196 if (!BN_mul(t
, a
, b
, ctx
))
199 if (!BN_nnmod(r
, t
, m
, ctx
))
208 int BN_mod_sqr(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
, BN_CTX
*ctx
)
210 if (!BN_sqr(r
, a
, ctx
))
212 /* r->neg == 0, thus we don't need BN_nnmod */
213 return BN_mod(r
, r
, m
, ctx
);
216 int BN_mod_lshift1(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
, BN_CTX
*ctx
)
218 if (!BN_lshift1(r
, a
))
221 return BN_nnmod(r
, r
, m
, ctx
);
225 * BN_mod_lshift1 variant that may be used if a is non-negative and less than
228 int BN_mod_lshift1_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
)
230 if (!BN_lshift1(r
, a
))
233 if (BN_cmp(r
, m
) >= 0)
234 return BN_sub(r
, r
, m
);
238 int BN_mod_lshift(BIGNUM
*r
, const BIGNUM
*a
, int n
, const BIGNUM
*m
,
241 BIGNUM
*abs_m
= NULL
;
244 if (!BN_nnmod(r
, a
, m
, ctx
))
254 ret
= BN_mod_lshift_quick(r
, r
, n
, (abs_m
? abs_m
: m
));
262 * BN_mod_lshift variant that may be used if a is non-negative and less than
265 int BN_mod_lshift_quick(BIGNUM
*r
, const BIGNUM
*a
, int n
, const BIGNUM
*m
)
268 if (BN_copy(r
, a
) == NULL
)
276 max_shift
= BN_num_bits(m
) - BN_num_bits(r
);
280 BNerr(BN_F_BN_MOD_LSHIFT_QUICK
, BN_R_INPUT_NOT_REDUCED
);
288 if (!BN_lshift(r
, r
, max_shift
))
292 if (!BN_lshift1(r
, r
))
297 /* BN_num_bits(r) <= BN_num_bits(m) */
299 if (BN_cmp(r
, m
) >= 0) {
300 if (!BN_sub(r
, r
, m
))