1109998Smarkm/* crypto/bn/bn_mod.c */ 2296465Sdelphij/* 3296465Sdelphij * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 4296465Sdelphij * for the OpenSSL project. 5296465Sdelphij */ 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 14296465Sdelphij * 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. 65296465Sdelphij * 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). 72296465Sdelphij * 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. 79296465Sdelphij * 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 :-). 94296465Sdelphij * 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)" 97296465Sdelphij * 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. 109296465Sdelphij * 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 119296465Sdelphij#if 0 /* now just a #define */ 120109998Smarkmint BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 121296465Sdelphij{ 122296465Sdelphij return (BN_div(NULL, rem, m, d, ctx)); 123296465Sdelphij /* note that rem->neg == m->neg (unless the remainder is zero) */ 124296465Sdelphij} 125109998Smarkm#endif 126109998Smarkm 127109998Smarkmint BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 128296465Sdelphij{ 129296465Sdelphij /* 130296465Sdelphij * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d| 131296465Sdelphij * always holds) 132296465Sdelphij */ 133109998Smarkm 134296465Sdelphij if (!(BN_mod(r, m, d, ctx))) 135296465Sdelphij return 0; 136296465Sdelphij if (!r->neg) 137296465Sdelphij return 1; 138296465Sdelphij /* now -|d| < r < 0, so we have to set r := r + |d| */ 139296465Sdelphij return (d->neg ? BN_sub : BN_add) (r, r, d); 140109998Smarkm} 141109998Smarkm 142296465Sdelphijint BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 143296465Sdelphij BN_CTX *ctx) 144296465Sdelphij{ 145296465Sdelphij if (!BN_add(r, a, b)) 146296465Sdelphij return 0; 147296465Sdelphij return BN_nnmod(r, r, m, ctx); 148296465Sdelphij} 149109998Smarkm 150296465Sdelphij/* 151296465Sdelphij * BN_mod_add variant that may be used if both a and b are non-negative and 152296465Sdelphij * less than m 153296465Sdelphij */ 154296465Sdelphijint BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 155296465Sdelphij const BIGNUM *m) 156296465Sdelphij{ 157296465Sdelphij if (!BN_uadd(r, a, b)) 158296465Sdelphij return 0; 159296465Sdelphij if (BN_ucmp(r, m) >= 0) 160296465Sdelphij return BN_usub(r, r, m); 161296465Sdelphij return 1; 162296465Sdelphij} 163109998Smarkm 164296465Sdelphijint BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 165296465Sdelphij BN_CTX *ctx) 166296465Sdelphij{ 167296465Sdelphij if (!BN_sub(r, a, b)) 168296465Sdelphij return 0; 169296465Sdelphij return BN_nnmod(r, r, m, ctx); 170296465Sdelphij} 171109998Smarkm 172296465Sdelphij/* 173296465Sdelphij * BN_mod_sub variant that may be used if both a and b are non-negative and 174296465Sdelphij * less than m 175296465Sdelphij */ 176296465Sdelphijint BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, 177296465Sdelphij const BIGNUM *m) 178296465Sdelphij{ 179296465Sdelphij if (!BN_sub(r, a, b)) 180296465Sdelphij return 0; 181296465Sdelphij if (r->neg) 182296465Sdelphij return BN_add(r, r, m); 183296465Sdelphij return 1; 184296465Sdelphij} 185109998Smarkm 186109998Smarkm/* slow but works */ 187109998Smarkmint BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 188296465Sdelphij BN_CTX *ctx) 189296465Sdelphij{ 190296465Sdelphij BIGNUM *t; 191296465Sdelphij int ret = 0; 192109998Smarkm 193296465Sdelphij bn_check_top(a); 194296465Sdelphij bn_check_top(b); 195296465Sdelphij bn_check_top(m); 196109998Smarkm 197296465Sdelphij BN_CTX_start(ctx); 198296465Sdelphij if ((t = BN_CTX_get(ctx)) == NULL) 199296465Sdelphij goto err; 200296465Sdelphij if (a == b) { 201296465Sdelphij if (!BN_sqr(t, a, ctx)) 202296465Sdelphij goto err; 203296465Sdelphij } else { 204296465Sdelphij if (!BN_mul(t, a, b, ctx)) 205296465Sdelphij goto err; 206296465Sdelphij } 207296465Sdelphij if (!BN_nnmod(r, t, m, ctx)) 208296465Sdelphij goto err; 209296465Sdelphij bn_check_top(r); 210296465Sdelphij ret = 1; 211296465Sdelphij err: 212296465Sdelphij BN_CTX_end(ctx); 213296465Sdelphij return (ret); 214296465Sdelphij} 215109998Smarkm 216109998Smarkmint BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 217296465Sdelphij{ 218296465Sdelphij if (!BN_sqr(r, a, ctx)) 219296465Sdelphij return 0; 220296465Sdelphij /* r->neg == 0, thus we don't need BN_nnmod */ 221296465Sdelphij return BN_mod(r, r, m, ctx); 222296465Sdelphij} 223109998Smarkm 224109998Smarkmint BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 225296465Sdelphij{ 226296465Sdelphij if (!BN_lshift1(r, a)) 227296465Sdelphij return 0; 228296465Sdelphij bn_check_top(r); 229296465Sdelphij return BN_nnmod(r, r, m, ctx); 230296465Sdelphij} 231109998Smarkm 232296465Sdelphij/* 233296465Sdelphij * BN_mod_lshift1 variant that may be used if a is non-negative and less than 234296465Sdelphij * m 235296465Sdelphij */ 236109998Smarkmint BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) 237296465Sdelphij{ 238296465Sdelphij if (!BN_lshift1(r, a)) 239296465Sdelphij return 0; 240296465Sdelphij bn_check_top(r); 241296465Sdelphij if (BN_cmp(r, m) >= 0) 242296465Sdelphij return BN_sub(r, r, m); 243296465Sdelphij return 1; 244296465Sdelphij} 245109998Smarkm 246296465Sdelphijint BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, 247296465Sdelphij BN_CTX *ctx) 248296465Sdelphij{ 249296465Sdelphij BIGNUM *abs_m = NULL; 250296465Sdelphij int ret; 251109998Smarkm 252296465Sdelphij if (!BN_nnmod(r, a, m, ctx)) 253296465Sdelphij return 0; 254109998Smarkm 255296465Sdelphij if (m->neg) { 256296465Sdelphij abs_m = BN_dup(m); 257296465Sdelphij if (abs_m == NULL) 258296465Sdelphij return 0; 259296465Sdelphij abs_m->neg = 0; 260296465Sdelphij } 261109998Smarkm 262296465Sdelphij ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 263296465Sdelphij bn_check_top(r); 264109998Smarkm 265296465Sdelphij if (abs_m) 266296465Sdelphij BN_free(abs_m); 267296465Sdelphij return ret; 268296465Sdelphij} 269109998Smarkm 270296465Sdelphij/* 271296465Sdelphij * BN_mod_lshift variant that may be used if a is non-negative and less than 272296465Sdelphij * m 273296465Sdelphij */ 274109998Smarkmint BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) 275296465Sdelphij{ 276296465Sdelphij if (r != a) { 277296465Sdelphij if (BN_copy(r, a) == NULL) 278296465Sdelphij return 0; 279296465Sdelphij } 280109998Smarkm 281296465Sdelphij while (n > 0) { 282296465Sdelphij int max_shift; 283109998Smarkm 284296465Sdelphij /* 0 < r < m */ 285296465Sdelphij max_shift = BN_num_bits(m) - BN_num_bits(r); 286296465Sdelphij /* max_shift >= 0 */ 287109998Smarkm 288296465Sdelphij if (max_shift < 0) { 289296465Sdelphij BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED); 290296465Sdelphij return 0; 291296465Sdelphij } 292109998Smarkm 293296465Sdelphij if (max_shift > n) 294296465Sdelphij max_shift = n; 295109998Smarkm 296296465Sdelphij if (max_shift) { 297296465Sdelphij if (!BN_lshift(r, r, max_shift)) 298296465Sdelphij return 0; 299296465Sdelphij n -= max_shift; 300296465Sdelphij } else { 301296465Sdelphij if (!BN_lshift1(r, r)) 302296465Sdelphij return 0; 303296465Sdelphij --n; 304296465Sdelphij } 305109998Smarkm 306296465Sdelphij /* BN_num_bits(r) <= BN_num_bits(m) */ 307296465Sdelphij 308296465Sdelphij if (BN_cmp(r, m) >= 0) { 309296465Sdelphij if (!BN_sub(r, r, m)) 310296465Sdelphij return 0; 311296465Sdelphij } 312296465Sdelphij } 313296465Sdelphij bn_check_top(r); 314296465Sdelphij 315296465Sdelphij return 1; 316296465Sdelphij} 317