1109998Smarkm/* crypto/bn/bn_mod.c */ 2109998Smarkm/* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 3109998Smarkm * for the OpenSSL project. */ 4109998Smarkm/* ==================================================================== 5109998Smarkm * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. 6109998Smarkm * 7109998Smarkm * Redistribution and use in source and binary forms, with or without 8109998Smarkm * modification, are permitted provided that the following conditions 9109998Smarkm * are met: 10109998Smarkm * 11109998Smarkm * 1. Redistributions of source code must retain the above copyright 12109998Smarkm * notice, this list of conditions and the following disclaimer. 13109998Smarkm * 14109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 15109998Smarkm * notice, this list of conditions and the following disclaimer in 16109998Smarkm * the documentation and/or other materials provided with the 17109998Smarkm * distribution. 18109998Smarkm * 19109998Smarkm * 3. All advertising materials mentioning features or use of this 20109998Smarkm * software must display the following acknowledgment: 21109998Smarkm * "This product includes software developed by the OpenSSL Project 22109998Smarkm * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 23109998Smarkm * 24109998Smarkm * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 25109998Smarkm * endorse or promote products derived from this software without 26109998Smarkm * prior written permission. For written permission, please contact 27109998Smarkm * openssl-core@openssl.org. 28109998Smarkm * 29109998Smarkm * 5. Products derived from this software may not be called "OpenSSL" 30109998Smarkm * nor may "OpenSSL" appear in their names without prior written 31109998Smarkm * permission of the OpenSSL Project. 32109998Smarkm * 33109998Smarkm * 6. Redistributions of any form whatsoever must retain the following 34109998Smarkm * acknowledgment: 35109998Smarkm * "This product includes software developed by the OpenSSL Project 36109998Smarkm * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 37109998Smarkm * 38109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 39109998Smarkm * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 40109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 41109998Smarkm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 42109998Smarkm * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 43109998Smarkm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 44109998Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 45109998Smarkm * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 46109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 47109998Smarkm * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 48109998Smarkm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 49109998Smarkm * OF THE POSSIBILITY OF SUCH DAMAGE. 50109998Smarkm * ==================================================================== 51109998Smarkm * 52109998Smarkm * This product includes cryptographic software written by Eric Young 53109998Smarkm * (eay@cryptsoft.com). This product includes software written by Tim 54109998Smarkm * Hudson (tjh@cryptsoft.com). 55109998Smarkm * 56109998Smarkm */ 57109998Smarkm/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 58109998Smarkm * All rights reserved. 59109998Smarkm * 60109998Smarkm * This package is an SSL implementation written 61109998Smarkm * by Eric Young (eay@cryptsoft.com). 62109998Smarkm * The implementation was written so as to conform with Netscapes SSL. 63109998Smarkm * 64109998Smarkm * This library is free for commercial and non-commercial use as long as 65109998Smarkm * the following conditions are aheared to. The following conditions 66109998Smarkm * apply to all code found in this distribution, be it the RC4, RSA, 67109998Smarkm * lhash, DES, etc., code; not just the SSL code. The SSL documentation 68109998Smarkm * included with this distribution is covered by the same copyright terms 69109998Smarkm * except that the holder is Tim Hudson (tjh@cryptsoft.com). 70109998Smarkm * 71109998Smarkm * Copyright remains Eric Young's, and as such any Copyright notices in 72109998Smarkm * the code are not to be removed. 73109998Smarkm * If this package is used in a product, Eric Young should be given attribution 74109998Smarkm * as the author of the parts of the library used. 75109998Smarkm * This can be in the form of a textual message at program startup or 76109998Smarkm * in documentation (online or textual) provided with the package. 77109998Smarkm * 78109998Smarkm * Redistribution and use in source and binary forms, with or without 79109998Smarkm * modification, are permitted provided that the following conditions 80109998Smarkm * are met: 81109998Smarkm * 1. Redistributions of source code must retain the copyright 82109998Smarkm * notice, this list of conditions and the following disclaimer. 83109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 84109998Smarkm * notice, this list of conditions and the following disclaimer in the 85109998Smarkm * documentation and/or other materials provided with the distribution. 86109998Smarkm * 3. All advertising materials mentioning features or use of this software 87109998Smarkm * must display the following acknowledgement: 88109998Smarkm * "This product includes cryptographic software written by 89109998Smarkm * Eric Young (eay@cryptsoft.com)" 90109998Smarkm * The word 'cryptographic' can be left out if the rouines from the library 91109998Smarkm * being used are not cryptographic related :-). 92109998Smarkm * 4. If you include any Windows specific code (or a derivative thereof) from 93109998Smarkm * the apps directory (application code) you must include an acknowledgement: 94109998Smarkm * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 95109998Smarkm * 96109998Smarkm * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 97109998Smarkm * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 98109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 99109998Smarkm * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 100109998Smarkm * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 101109998Smarkm * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 102109998Smarkm * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 103109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 104109998Smarkm * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 105109998Smarkm * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 106109998Smarkm * SUCH DAMAGE. 107109998Smarkm * 108109998Smarkm * The licence and distribution terms for any publically available version or 109109998Smarkm * derivative of this code cannot be changed. i.e. this code cannot simply be 110109998Smarkm * copied and put under another distribution licence 111109998Smarkm * [including the GNU Public Licence.] 112109998Smarkm */ 113109998Smarkm 114109998Smarkm#include "cryptlib.h" 115109998Smarkm#include "bn_lcl.h" 116109998Smarkm 117109998Smarkm 118109998Smarkm#if 0 /* now just a #define */ 119109998Smarkmint BN_mod(BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 120109998Smarkm { 121109998Smarkm return(BN_div(NULL,rem,m,d,ctx)); 122109998Smarkm /* note that rem->neg == m->neg (unless the remainder is zero) */ 123109998Smarkm } 124109998Smarkm#endif 125109998Smarkm 126109998Smarkm 127109998Smarkmint BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 128109998Smarkm { 129109998Smarkm /* like BN_mod, but returns non-negative remainder 130109998Smarkm * (i.e., 0 <= r < |d| always holds) */ 131109998Smarkm 132109998Smarkm if (!(BN_mod(r,m,d,ctx))) 133109998Smarkm return 0; 134109998Smarkm if (!r->neg) 135109998Smarkm return 1; 136109998Smarkm /* now -|d| < r < 0, so we have to set r := r + |d| */ 137109998Smarkm return (d->neg ? BN_sub : BN_add)(r, r, d); 138109998Smarkm} 139109998Smarkm 140109998Smarkm 141109998Smarkmint BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) 142109998Smarkm { 143109998Smarkm if (!BN_add(r, a, b)) return 0; 144109998Smarkm return BN_nnmod(r, r, m, ctx); 145109998Smarkm } 146109998Smarkm 147109998Smarkm 148109998Smarkm/* BN_mod_add variant that may be used if both a and b are non-negative 149109998Smarkm * and less than m */ 150109998Smarkmint BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) 151109998Smarkm { 152160814Ssimon if (!BN_uadd(r, a, b)) return 0; 153109998Smarkm if (BN_ucmp(r, m) >= 0) 154109998Smarkm return BN_usub(r, r, m); 155109998Smarkm return 1; 156109998Smarkm } 157109998Smarkm 158109998Smarkm 159109998Smarkmint BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx) 160109998Smarkm { 161109998Smarkm if (!BN_sub(r, a, b)) return 0; 162109998Smarkm return BN_nnmod(r, r, m, ctx); 163109998Smarkm } 164109998Smarkm 165109998Smarkm 166109998Smarkm/* BN_mod_sub variant that may be used if both a and b are non-negative 167109998Smarkm * and less than m */ 168109998Smarkmint BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) 169109998Smarkm { 170109998Smarkm if (!BN_sub(r, a, b)) return 0; 171109998Smarkm if (r->neg) 172109998Smarkm return BN_add(r, r, m); 173109998Smarkm return 1; 174109998Smarkm } 175109998Smarkm 176109998Smarkm 177109998Smarkm/* slow but works */ 178109998Smarkmint BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 179109998Smarkm BN_CTX *ctx) 180109998Smarkm { 181109998Smarkm BIGNUM *t; 182109998Smarkm int ret=0; 183109998Smarkm 184109998Smarkm bn_check_top(a); 185109998Smarkm bn_check_top(b); 186109998Smarkm bn_check_top(m); 187109998Smarkm 188109998Smarkm BN_CTX_start(ctx); 189109998Smarkm if ((t = BN_CTX_get(ctx)) == NULL) goto err; 190109998Smarkm if (a == b) 191109998Smarkm { if (!BN_sqr(t,a,ctx)) goto err; } 192109998Smarkm else 193109998Smarkm { if (!BN_mul(t,a,b,ctx)) goto err; } 194109998Smarkm if (!BN_nnmod(r,t,m,ctx)) goto err; 195160814Ssimon bn_check_top(r); 196109998Smarkm ret=1; 197109998Smarkmerr: 198109998Smarkm BN_CTX_end(ctx); 199109998Smarkm return(ret); 200109998Smarkm } 201109998Smarkm 202109998Smarkm 203109998Smarkmint BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 204109998Smarkm { 205109998Smarkm if (!BN_sqr(r, a, ctx)) return 0; 206109998Smarkm /* r->neg == 0, thus we don't need BN_nnmod */ 207109998Smarkm return BN_mod(r, r, m, ctx); 208109998Smarkm } 209109998Smarkm 210109998Smarkm 211109998Smarkmint BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 212109998Smarkm { 213109998Smarkm if (!BN_lshift1(r, a)) return 0; 214160814Ssimon bn_check_top(r); 215109998Smarkm return BN_nnmod(r, r, m, ctx); 216109998Smarkm } 217109998Smarkm 218109998Smarkm 219109998Smarkm/* BN_mod_lshift1 variant that may be used if a is non-negative 220109998Smarkm * and less than m */ 221109998Smarkmint BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) 222109998Smarkm { 223109998Smarkm if (!BN_lshift1(r, a)) return 0; 224160814Ssimon bn_check_top(r); 225109998Smarkm if (BN_cmp(r, m) >= 0) 226109998Smarkm return BN_sub(r, r, m); 227109998Smarkm return 1; 228109998Smarkm } 229109998Smarkm 230109998Smarkm 231109998Smarkmint BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx) 232109998Smarkm { 233109998Smarkm BIGNUM *abs_m = NULL; 234109998Smarkm int ret; 235109998Smarkm 236109998Smarkm if (!BN_nnmod(r, a, m, ctx)) return 0; 237109998Smarkm 238109998Smarkm if (m->neg) 239109998Smarkm { 240109998Smarkm abs_m = BN_dup(m); 241109998Smarkm if (abs_m == NULL) return 0; 242109998Smarkm abs_m->neg = 0; 243109998Smarkm } 244109998Smarkm 245109998Smarkm ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 246160814Ssimon bn_check_top(r); 247109998Smarkm 248109998Smarkm if (abs_m) 249109998Smarkm BN_free(abs_m); 250109998Smarkm return ret; 251109998Smarkm } 252109998Smarkm 253109998Smarkm 254109998Smarkm/* BN_mod_lshift variant that may be used if a is non-negative 255109998Smarkm * and less than m */ 256109998Smarkmint BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) 257109998Smarkm { 258109998Smarkm if (r != a) 259109998Smarkm { 260109998Smarkm if (BN_copy(r, a) == NULL) return 0; 261109998Smarkm } 262109998Smarkm 263109998Smarkm while (n > 0) 264109998Smarkm { 265109998Smarkm int max_shift; 266109998Smarkm 267109998Smarkm /* 0 < r < m */ 268109998Smarkm max_shift = BN_num_bits(m) - BN_num_bits(r); 269109998Smarkm /* max_shift >= 0 */ 270109998Smarkm 271109998Smarkm if (max_shift < 0) 272109998Smarkm { 273109998Smarkm BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED); 274109998Smarkm return 0; 275109998Smarkm } 276109998Smarkm 277109998Smarkm if (max_shift > n) 278109998Smarkm max_shift = n; 279109998Smarkm 280109998Smarkm if (max_shift) 281109998Smarkm { 282109998Smarkm if (!BN_lshift(r, r, max_shift)) return 0; 283109998Smarkm n -= max_shift; 284109998Smarkm } 285109998Smarkm else 286109998Smarkm { 287109998Smarkm if (!BN_lshift1(r, r)) return 0; 288109998Smarkm --n; 289109998Smarkm } 290109998Smarkm 291109998Smarkm /* BN_num_bits(r) <= BN_num_bits(m) */ 292109998Smarkm 293109998Smarkm if (BN_cmp(r, m) >= 0) 294109998Smarkm { 295109998Smarkm if (!BN_sub(r, r, m)) return 0; 296109998Smarkm } 297109998Smarkm } 298160814Ssimon bn_check_top(r); 299109998Smarkm 300109998Smarkm return 1; 301109998Smarkm } 302