1109998Smarkm/* crypto/bn/bn_mod.c */ 2280304Sjkim/* 3280304Sjkim * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 4280304Sjkim * for the OpenSSL project. 5280304Sjkim */ 6109998Smarkm/* ==================================================================== 7109998Smarkm * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. 8109998Smarkm * 9109998Smarkm * Redistribution and use in source and binary forms, with or without 10109998Smarkm * modification, are permitted provided that the following conditions 11109998Smarkm * are met: 12109998Smarkm * 13109998Smarkm * 1. Redistributions of source code must retain the above copyright 14280304Sjkim * notice, this list of conditions and the following disclaimer. 15109998Smarkm * 16109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 17109998Smarkm * notice, this list of conditions and the following disclaimer in 18109998Smarkm * the documentation and/or other materials provided with the 19109998Smarkm * distribution. 20109998Smarkm * 21109998Smarkm * 3. All advertising materials mentioning features or use of this 22109998Smarkm * software must display the following acknowledgment: 23109998Smarkm * "This product includes software developed by the OpenSSL Project 24109998Smarkm * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 25109998Smarkm * 26109998Smarkm * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 27109998Smarkm * endorse or promote products derived from this software without 28109998Smarkm * prior written permission. For written permission, please contact 29109998Smarkm * openssl-core@openssl.org. 30109998Smarkm * 31109998Smarkm * 5. Products derived from this software may not be called "OpenSSL" 32109998Smarkm * nor may "OpenSSL" appear in their names without prior written 33109998Smarkm * permission of the OpenSSL Project. 34109998Smarkm * 35109998Smarkm * 6. Redistributions of any form whatsoever must retain the following 36109998Smarkm * acknowledgment: 37109998Smarkm * "This product includes software developed by the OpenSSL Project 38109998Smarkm * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 39109998Smarkm * 40109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 41109998Smarkm * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 43109998Smarkm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 44109998Smarkm * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 45109998Smarkm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 46109998Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 47109998Smarkm * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 49109998Smarkm * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 50109998Smarkm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 51109998Smarkm * OF THE POSSIBILITY OF SUCH DAMAGE. 52109998Smarkm * ==================================================================== 53109998Smarkm * 54109998Smarkm * This product includes cryptographic software written by Eric Young 55109998Smarkm * (eay@cryptsoft.com). This product includes software written by Tim 56109998Smarkm * Hudson (tjh@cryptsoft.com). 57109998Smarkm * 58109998Smarkm */ 59109998Smarkm/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 60109998Smarkm * All rights reserved. 61109998Smarkm * 62109998Smarkm * This package is an SSL implementation written 63109998Smarkm * by Eric Young (eay@cryptsoft.com). 64109998Smarkm * The implementation was written so as to conform with Netscapes SSL. 65280304Sjkim * 66109998Smarkm * This library is free for commercial and non-commercial use as long as 67109998Smarkm * the following conditions are aheared to. The following conditions 68109998Smarkm * apply to all code found in this distribution, be it the RC4, RSA, 69109998Smarkm * lhash, DES, etc., code; not just the SSL code. The SSL documentation 70109998Smarkm * included with this distribution is covered by the same copyright terms 71109998Smarkm * except that the holder is Tim Hudson (tjh@cryptsoft.com). 72280304Sjkim * 73109998Smarkm * Copyright remains Eric Young's, and as such any Copyright notices in 74109998Smarkm * the code are not to be removed. 75109998Smarkm * If this package is used in a product, Eric Young should be given attribution 76109998Smarkm * as the author of the parts of the library used. 77109998Smarkm * This can be in the form of a textual message at program startup or 78109998Smarkm * in documentation (online or textual) provided with the package. 79280304Sjkim * 80109998Smarkm * Redistribution and use in source and binary forms, with or without 81109998Smarkm * modification, are permitted provided that the following conditions 82109998Smarkm * are met: 83109998Smarkm * 1. Redistributions of source code must retain the copyright 84109998Smarkm * notice, this list of conditions and the following disclaimer. 85109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 86109998Smarkm * notice, this list of conditions and the following disclaimer in the 87109998Smarkm * documentation and/or other materials provided with the distribution. 88109998Smarkm * 3. All advertising materials mentioning features or use of this software 89109998Smarkm * must display the following acknowledgement: 90109998Smarkm * "This product includes cryptographic software written by 91109998Smarkm * Eric Young (eay@cryptsoft.com)" 92109998Smarkm * The word 'cryptographic' can be left out if the rouines from the library 93109998Smarkm * being used are not cryptographic related :-). 94280304Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from 95109998Smarkm * the apps directory (application code) you must include an acknowledgement: 96109998Smarkm * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 97280304Sjkim * 98109998Smarkm * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 99109998Smarkm * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 100109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 101109998Smarkm * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 102109998Smarkm * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 103109998Smarkm * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 104109998Smarkm * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 105109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 106109998Smarkm * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 107109998Smarkm * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 108109998Smarkm * SUCH DAMAGE. 109280304Sjkim * 110109998Smarkm * The licence and distribution terms for any publically available version or 111109998Smarkm * derivative of this code cannot be changed. i.e. this code cannot simply be 112109998Smarkm * copied and put under another distribution licence 113109998Smarkm * [including the GNU Public Licence.] 114109998Smarkm */ 115109998Smarkm 116109998Smarkm#include "cryptlib.h" 117109998Smarkm#include "bn_lcl.h" 118109998Smarkm 119280304Sjkim#if 0 /* now just a #define */ 120109998Smarkmint BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 121280304Sjkim{ 122280304Sjkim return (BN_div(NULL, rem, m, d, ctx)); 123280304Sjkim /* note that rem->neg == m->neg (unless the remainder is zero) */ 124280304Sjkim} 125109998Smarkm#endif 126109998Smarkm 127109998Smarkmint BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 128280304Sjkim{ 129280304Sjkim /* 130280304Sjkim * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d| 131280304Sjkim * always holds) 132280304Sjkim */ 133109998Smarkm 134280304Sjkim if (!(BN_mod(r, m, d, ctx))) 135280304Sjkim return 0; 136280304Sjkim if (!r->neg) 137280304Sjkim return 1; 138280304Sjkim /* now -|d| < r < 0, so we have to set r := r + |d| */ 139280304Sjkim return (d->neg ? BN_sub : BN_add) (r, r, d); 140109998Smarkm} 141109998Smarkm 142280304Sjkimint BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 143280304Sjkim BN_CTX *ctx) 144280304Sjkim{ 145280304Sjkim if (!BN_add(r, a, b)) 146280304Sjkim return 0; 147280304Sjkim return BN_nnmod(r, r, m, ctx); 148280304Sjkim} 149109998Smarkm 150280304Sjkim/* 151280304Sjkim * BN_mod_add variant that may be used if both a and b are non-negative and 152280304Sjkim * less than m 153280304Sjkim */ 154280304Sjkimint BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 155280304Sjkim const BIGNUM *m) 156280304Sjkim{ 157280304Sjkim if (!BN_uadd(r, a, b)) 158280304Sjkim return 0; 159280304Sjkim if (BN_ucmp(r, m) >= 0) 160280304Sjkim return BN_usub(r, r, m); 161280304Sjkim return 1; 162280304Sjkim} 163109998Smarkm 164280304Sjkimint BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 165280304Sjkim BN_CTX *ctx) 166280304Sjkim{ 167280304Sjkim if (!BN_sub(r, a, b)) 168280304Sjkim return 0; 169280304Sjkim return BN_nnmod(r, r, m, ctx); 170280304Sjkim} 171109998Smarkm 172280304Sjkim/* 173280304Sjkim * BN_mod_sub variant that may be used if both a and b are non-negative and 174280304Sjkim * less than m 175280304Sjkim */ 176280304Sjkimint BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 177280304Sjkim const BIGNUM *m) 178280304Sjkim{ 179280304Sjkim if (!BN_sub(r, a, b)) 180280304Sjkim return 0; 181280304Sjkim if (r->neg) 182280304Sjkim return BN_add(r, r, m); 183280304Sjkim return 1; 184280304Sjkim} 185109998Smarkm 186109998Smarkm/* slow but works */ 187109998Smarkmint BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 188280304Sjkim BN_CTX *ctx) 189280304Sjkim{ 190280304Sjkim BIGNUM *t; 191280304Sjkim int ret = 0; 192109998Smarkm 193280304Sjkim bn_check_top(a); 194280304Sjkim bn_check_top(b); 195280304Sjkim bn_check_top(m); 196109998Smarkm 197280304Sjkim BN_CTX_start(ctx); 198280304Sjkim if ((t = BN_CTX_get(ctx)) == NULL) 199280304Sjkim goto err; 200280304Sjkim if (a == b) { 201280304Sjkim if (!BN_sqr(t, a, ctx)) 202280304Sjkim goto err; 203280304Sjkim } else { 204280304Sjkim if (!BN_mul(t, a, b, ctx)) 205280304Sjkim goto err; 206280304Sjkim } 207280304Sjkim if (!BN_nnmod(r, t, m, ctx)) 208280304Sjkim goto err; 209280304Sjkim bn_check_top(r); 210280304Sjkim ret = 1; 211280304Sjkim err: 212280304Sjkim BN_CTX_end(ctx); 213280304Sjkim return (ret); 214280304Sjkim} 215109998Smarkm 216109998Smarkmint BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 217280304Sjkim{ 218280304Sjkim if (!BN_sqr(r, a, ctx)) 219280304Sjkim return 0; 220280304Sjkim /* r->neg == 0, thus we don't need BN_nnmod */ 221280304Sjkim return BN_mod(r, r, m, ctx); 222280304Sjkim} 223109998Smarkm 224109998Smarkmint BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 225280304Sjkim{ 226280304Sjkim if (!BN_lshift1(r, a)) 227280304Sjkim return 0; 228280304Sjkim bn_check_top(r); 229280304Sjkim return BN_nnmod(r, r, m, ctx); 230280304Sjkim} 231109998Smarkm 232280304Sjkim/* 233280304Sjkim * BN_mod_lshift1 variant that may be used if a is non-negative and less than 234280304Sjkim * m 235280304Sjkim */ 236109998Smarkmint BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) 237280304Sjkim{ 238280304Sjkim if (!BN_lshift1(r, a)) 239280304Sjkim return 0; 240280304Sjkim bn_check_top(r); 241280304Sjkim if (BN_cmp(r, m) >= 0) 242280304Sjkim return BN_sub(r, r, m); 243280304Sjkim return 1; 244280304Sjkim} 245109998Smarkm 246280304Sjkimint BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 247280304Sjkim BN_CTX *ctx) 248280304Sjkim{ 249280304Sjkim BIGNUM *abs_m = NULL; 250280304Sjkim int ret; 251109998Smarkm 252280304Sjkim if (!BN_nnmod(r, a, m, ctx)) 253280304Sjkim return 0; 254109998Smarkm 255280304Sjkim if (m->neg) { 256280304Sjkim abs_m = BN_dup(m); 257280304Sjkim if (abs_m == NULL) 258280304Sjkim return 0; 259280304Sjkim abs_m->neg = 0; 260280304Sjkim } 261109998Smarkm 262280304Sjkim ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 263280304Sjkim bn_check_top(r); 264109998Smarkm 265280304Sjkim if (abs_m) 266280304Sjkim BN_free(abs_m); 267280304Sjkim return ret; 268280304Sjkim} 269109998Smarkm 270280304Sjkim/* 271280304Sjkim * BN_mod_lshift variant that may be used if a is non-negative and less than 272280304Sjkim * m 273280304Sjkim */ 274109998Smarkmint BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) 275280304Sjkim{ 276280304Sjkim if (r != a) { 277280304Sjkim if (BN_copy(r, a) == NULL) 278280304Sjkim return 0; 279280304Sjkim } 280109998Smarkm 281280304Sjkim while (n > 0) { 282280304Sjkim int max_shift; 283109998Smarkm 284280304Sjkim /* 0 < r < m */ 285280304Sjkim max_shift = BN_num_bits(m) - BN_num_bits(r); 286280304Sjkim /* max_shift >= 0 */ 287109998Smarkm 288280304Sjkim if (max_shift < 0) { 289280304Sjkim BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED); 290280304Sjkim return 0; 291280304Sjkim } 292109998Smarkm 293280304Sjkim if (max_shift > n) 294280304Sjkim max_shift = n; 295109998Smarkm 296280304Sjkim if (max_shift) { 297280304Sjkim if (!BN_lshift(r, r, max_shift)) 298280304Sjkim return 0; 299280304Sjkim n -= max_shift; 300280304Sjkim } else { 301280304Sjkim if (!BN_lshift1(r, r)) 302280304Sjkim return 0; 303280304Sjkim --n; 304280304Sjkim } 305109998Smarkm 306280304Sjkim /* BN_num_bits(r) <= BN_num_bits(m) */ 307280304Sjkim 308280304Sjkim if (BN_cmp(r, m) >= 0) { 309280304Sjkim if (!BN_sub(r, r, m)) 310280304Sjkim return 0; 311280304Sjkim } 312280304Sjkim } 313280304Sjkim bn_check_top(r); 314280304Sjkim 315280304Sjkim return 1; 316280304Sjkim} 317