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 #if 0 /* now just a #define */
120 int BN_mod(BIGNUM
*rem
, const BIGNUM
*m
, const BIGNUM
*d
, BN_CTX
*ctx
)
122 return (BN_div(NULL
, rem
, m
, d
, ctx
));
123 /* note that rem->neg == m->neg (unless the remainder is zero) */
127 int BN_nnmod(BIGNUM
*r
, const BIGNUM
*m
, const BIGNUM
*d
, BN_CTX
*ctx
)
130 * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d|
134 if (!(BN_mod(r
, m
, d
, ctx
)))
138 /* now -|d| < r < 0, so we have to set r := r + |d| */
139 return (d
->neg
? BN_sub
: BN_add
) (r
, r
, d
);
142 int BN_mod_add(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
,
145 if (!BN_add(r
, a
, b
))
147 return BN_nnmod(r
, r
, m
, ctx
);
151 * BN_mod_add variant that may be used if both a and b are non-negative and
154 int BN_mod_add_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
157 if (!BN_uadd(r
, a
, b
))
159 if (BN_ucmp(r
, m
) >= 0)
160 return BN_usub(r
, r
, m
);
164 int BN_mod_sub(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
,
167 if (!BN_sub(r
, a
, b
))
169 return BN_nnmod(r
, r
, m
, ctx
);
173 * BN_mod_sub variant that may be used if both a and b are non-negative and
176 int BN_mod_sub_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
179 if (!BN_sub(r
, a
, b
))
182 return BN_add(r
, r
, m
);
187 int BN_mod_mul(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
,
198 if ((t
= BN_CTX_get(ctx
)) == NULL
)
201 if (!BN_sqr(t
, a
, ctx
))
204 if (!BN_mul(t
, a
, b
, ctx
))
207 if (!BN_nnmod(r
, t
, m
, ctx
))
216 int BN_mod_sqr(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
, BN_CTX
*ctx
)
218 if (!BN_sqr(r
, a
, ctx
))
220 /* r->neg == 0, thus we don't need BN_nnmod */
221 return BN_mod(r
, r
, m
, ctx
);
224 int BN_mod_lshift1(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
, BN_CTX
*ctx
)
226 if (!BN_lshift1(r
, a
))
229 return BN_nnmod(r
, r
, m
, ctx
);
233 * BN_mod_lshift1 variant that may be used if a is non-negative and less than
236 int BN_mod_lshift1_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
)
238 if (!BN_lshift1(r
, a
))
241 if (BN_cmp(r
, m
) >= 0)
242 return BN_sub(r
, r
, m
);
246 int BN_mod_lshift(BIGNUM
*r
, const BIGNUM
*a
, int n
, const BIGNUM
*m
,
249 BIGNUM
*abs_m
= NULL
;
252 if (!BN_nnmod(r
, a
, m
, ctx
))
262 ret
= BN_mod_lshift_quick(r
, r
, n
, (abs_m
? abs_m
: m
));
271 * BN_mod_lshift variant that may be used if a is non-negative and less than
274 int BN_mod_lshift_quick(BIGNUM
*r
, const BIGNUM
*a
, int n
, const BIGNUM
*m
)
277 if (BN_copy(r
, a
) == NULL
)
285 max_shift
= BN_num_bits(m
) - BN_num_bits(r
);
289 BNerr(BN_F_BN_MOD_LSHIFT_QUICK
, BN_R_INPUT_NOT_REDUCED
);
297 if (!BN_lshift(r
, r
, max_shift
))
301 if (!BN_lshift1(r
, r
))
306 /* BN_num_bits(r) <= BN_num_bits(m) */
308 if (BN_cmp(r
, m
) >= 0) {
309 if (!BN_sub(r
, r
, m
))