sl@0: /* crypto/bn/bn_mod.c */ sl@0: /* Includes code written by Lenka Fibikova sl@0: * for the OpenSSL project. */ sl@0: /* ==================================================================== sl@0: * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. sl@0: * sl@0: * Redistribution and use in source and binary forms, with or without sl@0: * modification, are permitted provided that the following conditions sl@0: * are met: sl@0: * sl@0: * 1. Redistributions of source code must retain the above copyright sl@0: * notice, this list of conditions and the following disclaimer. sl@0: * sl@0: * 2. Redistributions in binary form must reproduce the above copyright sl@0: * notice, this list of conditions and the following disclaimer in sl@0: * the documentation and/or other materials provided with the sl@0: * distribution. sl@0: * sl@0: * 3. All advertising materials mentioning features or use of this sl@0: * software must display the following acknowledgment: sl@0: * "This product includes software developed by the OpenSSL Project sl@0: * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" sl@0: * sl@0: * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to sl@0: * endorse or promote products derived from this software without sl@0: * prior written permission. For written permission, please contact sl@0: * openssl-core@openssl.org. sl@0: * sl@0: * 5. Products derived from this software may not be called "OpenSSL" sl@0: * nor may "OpenSSL" appear in their names without prior written sl@0: * permission of the OpenSSL Project. sl@0: * sl@0: * 6. Redistributions of any form whatsoever must retain the following sl@0: * acknowledgment: sl@0: * "This product includes software developed by the OpenSSL Project sl@0: * for use in the OpenSSL Toolkit (http://www.openssl.org/)" sl@0: * sl@0: * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY sl@0: * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE sl@0: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR sl@0: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR sl@0: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, sl@0: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT sl@0: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; sl@0: * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) sl@0: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, sl@0: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) sl@0: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED sl@0: * OF THE POSSIBILITY OF SUCH DAMAGE. sl@0: * ==================================================================== sl@0: * sl@0: * This product includes cryptographic software written by Eric Young sl@0: * (eay@cryptsoft.com). This product includes software written by Tim sl@0: * Hudson (tjh@cryptsoft.com). sl@0: * sl@0: */ sl@0: /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) sl@0: * All rights reserved. sl@0: * sl@0: * This package is an SSL implementation written sl@0: * by Eric Young (eay@cryptsoft.com). sl@0: * The implementation was written so as to conform with Netscapes SSL. sl@0: * sl@0: * This library is free for commercial and non-commercial use as long as sl@0: * the following conditions are aheared to. The following conditions sl@0: * apply to all code found in this distribution, be it the RC4, RSA, sl@0: * lhash, DES, etc., code; not just the SSL code. The SSL documentation sl@0: * included with this distribution is covered by the same copyright terms sl@0: * except that the holder is Tim Hudson (tjh@cryptsoft.com). sl@0: * sl@0: * Copyright remains Eric Young's, and as such any Copyright notices in sl@0: * the code are not to be removed. sl@0: * If this package is used in a product, Eric Young should be given attribution sl@0: * as the author of the parts of the library used. sl@0: * This can be in the form of a textual message at program startup or sl@0: * in documentation (online or textual) provided with the package. sl@0: * sl@0: * Redistribution and use in source and binary forms, with or without sl@0: * modification, are permitted provided that the following conditions sl@0: * are met: sl@0: * 1. Redistributions of source code must retain the copyright sl@0: * notice, this list of conditions and the following disclaimer. sl@0: * 2. Redistributions in binary form must reproduce the above copyright sl@0: * notice, this list of conditions and the following disclaimer in the sl@0: * documentation and/or other materials provided with the distribution. sl@0: * 3. All advertising materials mentioning features or use of this software sl@0: * must display the following acknowledgement: sl@0: * "This product includes cryptographic software written by sl@0: * Eric Young (eay@cryptsoft.com)" sl@0: * The word 'cryptographic' can be left out if the rouines from the library sl@0: * being used are not cryptographic related :-). sl@0: * 4. If you include any Windows specific code (or a derivative thereof) from sl@0: * the apps directory (application code) you must include an acknowledgement: sl@0: * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" sl@0: * sl@0: * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND sl@0: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE sl@0: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE sl@0: * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE sl@0: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL sl@0: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS sl@0: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) sl@0: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT sl@0: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY sl@0: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF sl@0: * SUCH DAMAGE. sl@0: * sl@0: * The licence and distribution terms for any publically available version or sl@0: * derivative of this code cannot be changed. i.e. this code cannot simply be sl@0: * copied and put under another distribution licence sl@0: * [including the GNU Public Licence.] sl@0: */ sl@0: sl@0: #include "cryptlib.h" sl@0: #include "bn_lcl.h" sl@0: sl@0: sl@0: #if 0 /* now just a #define */ sl@0: EXPORT_C int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) sl@0: { sl@0: return(BN_div(NULL,rem,m,d,ctx)); sl@0: /* note that rem->neg == m->neg (unless the remainder is zero) */ sl@0: } sl@0: #endif sl@0: sl@0: sl@0: EXPORT_C int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) sl@0: { sl@0: /* like BN_mod, but returns non-negative remainder sl@0: * (i.e., 0 <= r < |d| always holds) */ sl@0: sl@0: if (!(BN_mod(r,m,d,ctx))) sl@0: return 0; sl@0: if (!r->neg) sl@0: return 1; sl@0: /* now -|d| < r < 0, so we have to set r := r + |d| */ sl@0: return (d->neg ? BN_sub : BN_add)(r, r, d); sl@0: } sl@0: sl@0: sl@0: EXPORT_C int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) sl@0: { sl@0: if (!BN_add(r, a, b)) return 0; sl@0: return BN_nnmod(r, r, m, ctx); sl@0: } sl@0: sl@0: sl@0: /* BN_mod_add variant that may be used if both a and b are non-negative sl@0: * and less than m */ sl@0: EXPORT_C int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) sl@0: { sl@0: if (!BN_uadd(r, a, b)) return 0; sl@0: if (BN_ucmp(r, m) >= 0) sl@0: return BN_usub(r, r, m); sl@0: return 1; sl@0: } sl@0: sl@0: sl@0: EXPORT_C int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) sl@0: { sl@0: if (!BN_sub(r, a, b)) return 0; sl@0: return BN_nnmod(r, r, m, ctx); sl@0: } sl@0: sl@0: sl@0: /* BN_mod_sub variant that may be used if both a and b are non-negative sl@0: * and less than m */ sl@0: EXPORT_C int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) sl@0: { sl@0: if (!BN_sub(r, a, b)) return 0; sl@0: if (r->neg) sl@0: return BN_add(r, r, m); sl@0: return 1; sl@0: } sl@0: sl@0: sl@0: /* slow but works */ sl@0: EXPORT_C int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, sl@0: BN_CTX *ctx) sl@0: { sl@0: BIGNUM *t; sl@0: int ret=0; sl@0: sl@0: bn_check_top(a); sl@0: bn_check_top(b); sl@0: bn_check_top(m); sl@0: sl@0: BN_CTX_start(ctx); sl@0: if ((t = BN_CTX_get(ctx)) == NULL) goto err; sl@0: if (a == b) sl@0: { if (!BN_sqr(t,a,ctx)) goto err; } sl@0: else sl@0: { if (!BN_mul(t,a,b,ctx)) goto err; } sl@0: if (!BN_nnmod(r,t,m,ctx)) goto err; sl@0: bn_check_top(r); sl@0: ret=1; sl@0: err: sl@0: BN_CTX_end(ctx); sl@0: return(ret); sl@0: } sl@0: sl@0: sl@0: EXPORT_C int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) sl@0: { sl@0: if (!BN_sqr(r, a, ctx)) return 0; sl@0: /* r->neg == 0, thus we don't need BN_nnmod */ sl@0: return BN_mod(r, r, m, ctx); sl@0: } sl@0: sl@0: sl@0: EXPORT_C int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) sl@0: { sl@0: if (!BN_lshift1(r, a)) return 0; sl@0: bn_check_top(r); sl@0: return BN_nnmod(r, r, m, ctx); sl@0: } sl@0: sl@0: sl@0: /* BN_mod_lshift1 variant that may be used if a is non-negative sl@0: * and less than m */ sl@0: EXPORT_C int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) sl@0: { sl@0: if (!BN_lshift1(r, a)) return 0; sl@0: bn_check_top(r); sl@0: if (BN_cmp(r, m) >= 0) sl@0: return BN_sub(r, r, m); sl@0: return 1; sl@0: } sl@0: sl@0: sl@0: EXPORT_C int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx) sl@0: { sl@0: BIGNUM *abs_m = NULL; sl@0: int ret; sl@0: sl@0: if (!BN_nnmod(r, a, m, ctx)) return 0; sl@0: sl@0: if (m->neg) sl@0: { sl@0: abs_m = BN_dup(m); sl@0: if (abs_m == NULL) return 0; sl@0: abs_m->neg = 0; sl@0: } sl@0: sl@0: ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); sl@0: bn_check_top(r); sl@0: sl@0: if (abs_m) sl@0: BN_free(abs_m); sl@0: return ret; sl@0: } sl@0: sl@0: sl@0: /* BN_mod_lshift variant that may be used if a is non-negative sl@0: * and less than m */ sl@0: EXPORT_C int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) sl@0: { sl@0: if (r != a) sl@0: { sl@0: if (BN_copy(r, a) == NULL) return 0; sl@0: } sl@0: sl@0: while (n > 0) sl@0: { sl@0: int max_shift; sl@0: sl@0: /* 0 < r < m */ sl@0: max_shift = BN_num_bits(m) - BN_num_bits(r); sl@0: /* max_shift >= 0 */ sl@0: sl@0: if (max_shift < 0) sl@0: { sl@0: BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED); sl@0: return 0; sl@0: } sl@0: sl@0: if (max_shift > n) sl@0: max_shift = n; sl@0: sl@0: if (max_shift) sl@0: { sl@0: if (!BN_lshift(r, r, max_shift)) return 0; sl@0: n -= max_shift; sl@0: } sl@0: else sl@0: { sl@0: if (!BN_lshift1(r, r)) return 0; sl@0: --n; sl@0: } sl@0: sl@0: /* BN_num_bits(r) <= BN_num_bits(m) */ sl@0: sl@0: if (BN_cmp(r, m) >= 0) sl@0: { sl@0: if (!BN_sub(r, r, m)) return 0; sl@0: } sl@0: } sl@0: bn_check_top(r); sl@0: sl@0: return 1; sl@0: }