1 /* crypto/bn/bn_mod.c */

     2 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>

     3  * for the OpenSSL project. */

     4 /* ====================================================================

     5  * Copyright (c) 1998-2000 The OpenSSL Project.  All rights reserved.

     6  *

     7  * Redistribution and use in source and binary forms, with or without

     8  * modification, are permitted provided that the following conditions

     9  * are met:

    10  *

    11  * 1. Redistributions of source code must retain the above copyright

    12  *    notice, this list of conditions and the following disclaimer. 

    13  *

    14  * 2. Redistributions in binary form must reproduce the above copyright

    15  *    notice, this list of conditions and the following disclaimer in

    16  *    the documentation and/or other materials provided with the

    17  *    distribution.

    18  *

    19  * 3. All advertising materials mentioning features or use of this

    20  *    software must display the following acknowledgment:

    21  *    "This product includes software developed by the OpenSSL Project

    22  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"

    23  *

    24  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to

    25  *    endorse or promote products derived from this software without

    26  *    prior written permission. For written permission, please contact

    27  *    openssl-core@openssl.org.

    28  *

    29  * 5. Products derived from this software may not be called "OpenSSL"

    30  *    nor may "OpenSSL" appear in their names without prior written

    31  *    permission of the OpenSSL Project.

    32  *

    33  * 6. Redistributions of any form whatsoever must retain the following

    34  *    acknowledgment:

    35  *    "This product includes software developed by the OpenSSL Project

    36  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"

    37  *

    38  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY

    39  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    40  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

    41  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR

    42  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

    43  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT

    44  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

    45  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

    46  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,

    47  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

    48  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED

    49  * OF THE POSSIBILITY OF SUCH DAMAGE.

    50  * ====================================================================

    51  *

    52  * This product includes cryptographic software written by Eric Young

    53  * (eay@cryptsoft.com).  This product includes software written by Tim

    54  * Hudson (tjh@cryptsoft.com).

    55  *

    56  */

    57 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)

    58  * All rights reserved.

    59  *

    60  * This package is an SSL implementation written

    61  * by Eric Young (eay@cryptsoft.com).

    62  * The implementation was written so as to conform with Netscapes SSL.

    63  * 

    64  * This library is free for commercial and non-commercial use as long as

    65  * the following conditions are aheared to.  The following conditions

    66  * apply to all code found in this distribution, be it the RC4, RSA,

    67  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation

    68  * included with this distribution is covered by the same copyright terms

    69  * except that the holder is Tim Hudson (tjh@cryptsoft.com).

    70  * 

    71  * Copyright remains Eric Young's, and as such any Copyright notices in

    72  * the code are not to be removed.

    73  * If this package is used in a product, Eric Young should be given attribution

    74  * as the author of the parts of the library used.

    75  * This can be in the form of a textual message at program startup or

    76  * in documentation (online or textual) provided with the package.

    77  * 

    78  * Redistribution and use in source and binary forms, with or without

    79  * modification, are permitted provided that the following conditions

    80  * are met:

    81  * 1. Redistributions of source code must retain the copyright

    82  *    notice, this list of conditions and the following disclaimer.

    83  * 2. Redistributions in binary form must reproduce the above copyright

    84  *    notice, this list of conditions and the following disclaimer in the

    85  *    documentation and/or other materials provided with the distribution.

    86  * 3. All advertising materials mentioning features or use of this software

    87  *    must display the following acknowledgement:

    88  *    "This product includes cryptographic software written by

    89  *     Eric Young (eay@cryptsoft.com)"

    90  *    The word 'cryptographic' can be left out if the rouines from the library

    91  *    being used are not cryptographic related :-).

    92  * 4. If you include any Windows specific code (or a derivative thereof) from 

    93  *    the apps directory (application code) you must include an acknowledgement:

    94  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"

    95  * 

    96  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND

    97  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    98  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

    99  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE

   100  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL

   101  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS

   102  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

   103  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

   104  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

   105  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

   106  * SUCH DAMAGE.

   107  * 

   108  * The licence and distribution terms for any publically available version or

   109  * derivative of this code cannot be changed.  i.e. this code cannot simply be

   110  * copied and put under another distribution licence

   111  * [including the GNU Public Licence.]

   112  */

   113 

   114 #include "cryptlib.h"

   115 #include "bn_lcl.h"

   116 

   117 

   118 #if 0 /* now just a #define */

   119 EXPORT_C int BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)

   120 	{

   121 	return(BN_div(NULL,rem,m,d,ctx));

   122 	/* note that  rem->neg == m->neg  (unless the remainder is zero) */

   123 	}

   124 #endif

   125 

   126 

   127 EXPORT_C int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)

   128 	{

   129 	/* like BN_mod, but returns non-negative remainder

   130 	 * (i.e.,  0 <= r < |d|  always holds) */

   131 

   132 	if (!(BN_mod(r,m,d,ctx)))

   133 		return 0;

   134 	if (!r->neg)

   135 		return 1;

   136 	/* now   -|d| < r < 0,  so we have to set  r := r + |d| */

   137 	return (d->neg ? BN_sub : BN_add)(r, r, d);

   138 }

   139 

   140 

   141 EXPORT_C int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)

   142 	{

   143 	if (!BN_add(r, a, b)) return 0;

   144 	return BN_nnmod(r, r, m, ctx);

   145 	}

   146 

   147 

   148 /* BN_mod_add variant that may be used if both  a  and  b  are non-negative

   149  * and less than  m */

   150 EXPORT_C int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)

   151 	{

   152 	if (!BN_uadd(r, a, b)) return 0;

   153 	if (BN_ucmp(r, m) >= 0)

   154 		return BN_usub(r, r, m);

   155 	return 1;

   156 	}

   157 

   158 

   159 EXPORT_C int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)

   160 	{

   161 	if (!BN_sub(r, a, b)) return 0;

   162 	return BN_nnmod(r, r, m, ctx);

   163 	}

   164 

   165 

   166 /* BN_mod_sub variant that may be used if both  a  and  b  are non-negative

   167  * and less than  m */

   168 EXPORT_C int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)

   169 	{

   170 	if (!BN_sub(r, a, b)) return 0;

   171 	if (r->neg)

   172 		return BN_add(r, r, m);

   173 	return 1;

   174 	}

   175 

   176 

   177 /* slow but works */

   178 EXPORT_C 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) goto err;

   190 	if (a == b)

   191 		{ if (!BN_sqr(t,a,ctx)) goto err; }

   192 	else

   193 		{ if (!BN_mul(t,a,b,ctx)) goto err; }

   194 	if (!BN_nnmod(r,t,m,ctx)) goto err;

   195 	bn_check_top(r);

   196 	ret=1;

   197 err:

   198 	BN_CTX_end(ctx);

   199 	return(ret);

   200 	}

   201 

   202 

   203 EXPORT_C int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)

   204 	{

   205 	if (!BN_sqr(r, a, ctx)) return 0;

   206 	/* r->neg == 0,  thus we don't need BN_nnmod */

   207 	return BN_mod(r, r, m, ctx);

   208 	}

   209 

   210 

   211 EXPORT_C int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)

   212 	{

   213 	if (!BN_lshift1(r, a)) return 0;

   214 	bn_check_top(r);

   215 	return BN_nnmod(r, r, m, ctx);

   216 	}

   217 

   218 

   219 /* BN_mod_lshift1 variant that may be used if  a  is non-negative

   220  * and less than  m */

   221 EXPORT_C int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)

   222 	{

   223 	if (!BN_lshift1(r, a)) return 0;

   224 	bn_check_top(r);

   225 	if (BN_cmp(r, m) >= 0)

   226 		return BN_sub(r, r, m);

   227 	return 1;

   228 	}

   229 

   230 

   231 EXPORT_C int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)

   232 	{

   233 	BIGNUM *abs_m = NULL;

   234 	int ret;

   235 

   236 	if (!BN_nnmod(r, a, m, ctx)) return 0;

   237 

   238 	if (m->neg)

   239 		{

   240 		abs_m = BN_dup(m);

   241 		if (abs_m == NULL) return 0;

   242 		abs_m->neg = 0;

   243 		}

   244 	

   245 	ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));

   246 	bn_check_top(r);

   247 

   248 	if (abs_m)

   249 		BN_free(abs_m);

   250 	return ret;

   251 	}

   252 

   253 

   254 /* BN_mod_lshift variant that may be used if  a  is non-negative

   255  * and less than  m */

   256 EXPORT_C int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)

   257 	{

   258 	if (r != a)

   259 		{

   260 		if (BN_copy(r, a) == NULL) return 0;

   261 		}

   262 

   263 	while (n > 0)

   264 		{

   265 		int max_shift;

   266 		

   267 		/* 0 < r < m */

   268 		max_shift = BN_num_bits(m) - BN_num_bits(r);

   269 		/* max_shift >= 0 */

   270 

   271 		if (max_shift < 0)

   272 			{

   273 			BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);

   274 			return 0;

   275 			}

   276 

   277 		if (max_shift > n)

   278 			max_shift = n;

   279 

   280 		if (max_shift)

   281 			{

   282 			if (!BN_lshift(r, r, max_shift)) return 0;

   283 			n -= max_shift;

   284 			}

   285 		else

   286 			{

   287 			if (!BN_lshift1(r, r)) return 0;

   288 			--n;

   289 			}

   290 

   291 		/* BN_num_bits(r) <= BN_num_bits(m) */

   292 

   293 		if (BN_cmp(r, m) >= 0) 

   294 			{

   295 			if (!BN_sub(r, r, m)) return 0;

   296 			}

   297 		}

   298 	bn_check_top(r);

   299 	

   300 	return 1;

   301 	}