1*7bb0769bSjsing /* $OpenBSD: bn_mod.c,v 1.15 2023/02/03 04:47:59 jsing Exp $ */ 2da347917Sbeck /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> 3da347917Sbeck * for the OpenSSL project. */ 4da347917Sbeck /* ==================================================================== 5da347917Sbeck * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. 6da347917Sbeck * 7da347917Sbeck * Redistribution and use in source and binary forms, with or without 8da347917Sbeck * modification, are permitted provided that the following conditions 9da347917Sbeck * are met: 10da347917Sbeck * 11da347917Sbeck * 1. Redistributions of source code must retain the above copyright 12da347917Sbeck * notice, this list of conditions and the following disclaimer. 13da347917Sbeck * 14da347917Sbeck * 2. Redistributions in binary form must reproduce the above copyright 15da347917Sbeck * notice, this list of conditions and the following disclaimer in 16da347917Sbeck * the documentation and/or other materials provided with the 17da347917Sbeck * distribution. 18da347917Sbeck * 19da347917Sbeck * 3. All advertising materials mentioning features or use of this 20da347917Sbeck * software must display the following acknowledgment: 21da347917Sbeck * "This product includes software developed by the OpenSSL Project 22da347917Sbeck * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 23da347917Sbeck * 24da347917Sbeck * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 25da347917Sbeck * endorse or promote products derived from this software without 26da347917Sbeck * prior written permission. For written permission, please contact 27da347917Sbeck * openssl-core@openssl.org. 28da347917Sbeck * 29da347917Sbeck * 5. Products derived from this software may not be called "OpenSSL" 30da347917Sbeck * nor may "OpenSSL" appear in their names without prior written 31da347917Sbeck * permission of the OpenSSL Project. 32da347917Sbeck * 33da347917Sbeck * 6. Redistributions of any form whatsoever must retain the following 34da347917Sbeck * acknowledgment: 35da347917Sbeck * "This product includes software developed by the OpenSSL Project 36da347917Sbeck * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 37da347917Sbeck * 38da347917Sbeck * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 39da347917Sbeck * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 40da347917Sbeck * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 41da347917Sbeck * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 42da347917Sbeck * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 43da347917Sbeck * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 44da347917Sbeck * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 45da347917Sbeck * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 46da347917Sbeck * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 47da347917Sbeck * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 48da347917Sbeck * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 49da347917Sbeck * OF THE POSSIBILITY OF SUCH DAMAGE. 50da347917Sbeck * ==================================================================== 51da347917Sbeck * 52da347917Sbeck * This product includes cryptographic software written by Eric Young 53da347917Sbeck * (eay@cryptsoft.com). This product includes software written by Tim 54da347917Sbeck * Hudson (tjh@cryptsoft.com). 55da347917Sbeck * 56da347917Sbeck */ 57da347917Sbeck /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 58da347917Sbeck * All rights reserved. 59da347917Sbeck * 60da347917Sbeck * This package is an SSL implementation written 61da347917Sbeck * by Eric Young (eay@cryptsoft.com). 62da347917Sbeck * The implementation was written so as to conform with Netscapes SSL. 63da347917Sbeck * 64da347917Sbeck * This library is free for commercial and non-commercial use as long as 65da347917Sbeck * the following conditions are aheared to. The following conditions 66da347917Sbeck * apply to all code found in this distribution, be it the RC4, RSA, 67da347917Sbeck * lhash, DES, etc., code; not just the SSL code. The SSL documentation 68da347917Sbeck * included with this distribution is covered by the same copyright terms 69da347917Sbeck * except that the holder is Tim Hudson (tjh@cryptsoft.com). 70da347917Sbeck * 71da347917Sbeck * Copyright remains Eric Young's, and as such any Copyright notices in 72da347917Sbeck * the code are not to be removed. 73da347917Sbeck * If this package is used in a product, Eric Young should be given attribution 74da347917Sbeck * as the author of the parts of the library used. 75da347917Sbeck * This can be in the form of a textual message at program startup or 76da347917Sbeck * in documentation (online or textual) provided with the package. 77da347917Sbeck * 78da347917Sbeck * Redistribution and use in source and binary forms, with or without 79da347917Sbeck * modification, are permitted provided that the following conditions 80da347917Sbeck * are met: 81da347917Sbeck * 1. Redistributions of source code must retain the copyright 82da347917Sbeck * notice, this list of conditions and the following disclaimer. 83da347917Sbeck * 2. Redistributions in binary form must reproduce the above copyright 84da347917Sbeck * notice, this list of conditions and the following disclaimer in the 85da347917Sbeck * documentation and/or other materials provided with the distribution. 86da347917Sbeck * 3. All advertising materials mentioning features or use of this software 87da347917Sbeck * must display the following acknowledgement: 88da347917Sbeck * "This product includes cryptographic software written by 89da347917Sbeck * Eric Young (eay@cryptsoft.com)" 90da347917Sbeck * The word 'cryptographic' can be left out if the rouines from the library 91da347917Sbeck * being used are not cryptographic related :-). 92da347917Sbeck * 4. If you include any Windows specific code (or a derivative thereof) from 93da347917Sbeck * the apps directory (application code) you must include an acknowledgement: 94da347917Sbeck * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 95da347917Sbeck * 96da347917Sbeck * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 97da347917Sbeck * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 98da347917Sbeck * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 99da347917Sbeck * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 100da347917Sbeck * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 101da347917Sbeck * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 102da347917Sbeck * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 103da347917Sbeck * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 104da347917Sbeck * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 105da347917Sbeck * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 106da347917Sbeck * SUCH DAMAGE. 107da347917Sbeck * 108da347917Sbeck * The licence and distribution terms for any publically available version or 109da347917Sbeck * derivative of this code cannot be changed. i.e. this code cannot simply be 110da347917Sbeck * copied and put under another distribution licence 111da347917Sbeck * [including the GNU Public Licence.] 112da347917Sbeck */ 113da347917Sbeck 114b6ab114eSjsing #include <openssl/err.h> 115b6ab114eSjsing 116c9675a23Stb #include "bn_local.h" 117da347917Sbeck 1182bd9bb84Sjsing int 119*7bb0769bSjsing BN_mod_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 120*7bb0769bSjsing { 121*7bb0769bSjsing return BN_div_ct(NULL, r, a, m, ctx); 122*7bb0769bSjsing } 123*7bb0769bSjsing 124*7bb0769bSjsing int 125*7bb0769bSjsing BN_mod_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 126*7bb0769bSjsing { 127*7bb0769bSjsing return BN_div_nonct(NULL, r, a, m, ctx); 128*7bb0769bSjsing } 129*7bb0769bSjsing 130*7bb0769bSjsing int 1312bd9bb84Sjsing BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) 132da347917Sbeck { 133da347917Sbeck /* like BN_mod, but returns non-negative remainder 134da347917Sbeck * (i.e., 0 <= r < |d| always holds) */ 135da347917Sbeck 13644adc1eaSbeck if (!(BN_mod_ct(r, m,d, ctx))) 137da347917Sbeck return 0; 138da347917Sbeck if (!r->neg) 139da347917Sbeck return 1; 140da347917Sbeck /* now -|d| < r < 0, so we have to set r := r + |d| */ 141d8091d7fSmiod if (d->neg) 142d8091d7fSmiod return BN_sub(r, r, d); 143d8091d7fSmiod else 144d8091d7fSmiod return BN_add(r, r, d); 145da347917Sbeck } 146da347917Sbeck 1472bd9bb84Sjsing int 1482bd9bb84Sjsing BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 1492bd9bb84Sjsing BN_CTX *ctx) 150da347917Sbeck { 1512bd9bb84Sjsing if (!BN_add(r, a, b)) 1522bd9bb84Sjsing return 0; 153da347917Sbeck return BN_nnmod(r, r, m, ctx); 154da347917Sbeck } 155da347917Sbeck 156da347917Sbeck /* BN_mod_add variant that may be used if both a and b are non-negative 157da347917Sbeck * and less than m */ 1582bd9bb84Sjsing int 1592bd9bb84Sjsing BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) 160da347917Sbeck { 1612bd9bb84Sjsing if (!BN_uadd(r, a, b)) 1622bd9bb84Sjsing return 0; 163da347917Sbeck if (BN_ucmp(r, m) >= 0) 164da347917Sbeck return BN_usub(r, r, m); 165da347917Sbeck return 1; 166da347917Sbeck } 167da347917Sbeck 1682bd9bb84Sjsing int 1692bd9bb84Sjsing BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 1702bd9bb84Sjsing BN_CTX *ctx) 171da347917Sbeck { 1722bd9bb84Sjsing if (!BN_sub(r, a, b)) 1732bd9bb84Sjsing return 0; 174da347917Sbeck return BN_nnmod(r, r, m, ctx); 175da347917Sbeck } 176da347917Sbeck 177da347917Sbeck /* BN_mod_sub variant that may be used if both a and b are non-negative 178da347917Sbeck * and less than m */ 1792bd9bb84Sjsing int 1802bd9bb84Sjsing BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m) 181da347917Sbeck { 1822bd9bb84Sjsing if (!BN_sub(r, a, b)) 1832bd9bb84Sjsing return 0; 184da347917Sbeck if (r->neg) 185da347917Sbeck return BN_add(r, r, m); 186da347917Sbeck return 1; 187da347917Sbeck } 188da347917Sbeck 189da347917Sbeck /* slow but works */ 1902bd9bb84Sjsing int 1912bd9bb84Sjsing BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, 192da347917Sbeck BN_CTX *ctx) 193da347917Sbeck { 194da347917Sbeck BIGNUM *t; 195da347917Sbeck int ret = 0; 196da347917Sbeck 197da347917Sbeck 198da347917Sbeck BN_CTX_start(ctx); 1992bd9bb84Sjsing if ((t = BN_CTX_get(ctx)) == NULL) 2002bd9bb84Sjsing goto err; 2012bd9bb84Sjsing if (a == b) { 2022bd9bb84Sjsing if (!BN_sqr(t, a, ctx)) 2032bd9bb84Sjsing goto err; 2042bd9bb84Sjsing } else { 2052bd9bb84Sjsing if (!BN_mul(t, a,b, ctx)) 2062bd9bb84Sjsing goto err; 2072bd9bb84Sjsing } 2082bd9bb84Sjsing if (!BN_nnmod(r, t,m, ctx)) 2092bd9bb84Sjsing goto err; 210da347917Sbeck ret = 1; 2112bd9bb84Sjsing 212da347917Sbeck err: 213da347917Sbeck BN_CTX_end(ctx); 214da347917Sbeck return (ret); 215da347917Sbeck } 216da347917Sbeck 2172bd9bb84Sjsing int 2182bd9bb84Sjsing BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 219da347917Sbeck { 2202bd9bb84Sjsing if (!BN_sqr(r, a, ctx)) 2212bd9bb84Sjsing return 0; 222da347917Sbeck /* r->neg == 0, thus we don't need BN_nnmod */ 22344adc1eaSbeck return BN_mod_ct(r, r, m, ctx); 224da347917Sbeck } 225da347917Sbeck 2262bd9bb84Sjsing int 2272bd9bb84Sjsing BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) 228da347917Sbeck { 2292bd9bb84Sjsing if (!BN_lshift1(r, a)) 2302bd9bb84Sjsing return 0; 231da347917Sbeck return BN_nnmod(r, r, m, ctx); 232da347917Sbeck } 233da347917Sbeck 234da347917Sbeck /* BN_mod_lshift1 variant that may be used if a is non-negative 235da347917Sbeck * and less than m */ 2362bd9bb84Sjsing int 2372bd9bb84Sjsing BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) 238da347917Sbeck { 2392bd9bb84Sjsing if (!BN_lshift1(r, a)) 2402bd9bb84Sjsing return 0; 241da347917Sbeck if (BN_cmp(r, m) >= 0) 242da347917Sbeck return BN_sub(r, r, m); 243da347917Sbeck return 1; 244da347917Sbeck } 245da347917Sbeck 2462bd9bb84Sjsing int 2472bd9bb84Sjsing BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx) 248da347917Sbeck { 249da347917Sbeck BIGNUM *abs_m = NULL; 250da347917Sbeck int ret; 251da347917Sbeck 2522bd9bb84Sjsing if (!BN_nnmod(r, a, m, ctx)) 2532bd9bb84Sjsing return 0; 254da347917Sbeck 2552bd9bb84Sjsing if (m->neg) { 256da347917Sbeck abs_m = BN_dup(m); 2572bd9bb84Sjsing if (abs_m == NULL) 2582bd9bb84Sjsing return 0; 259da347917Sbeck abs_m->neg = 0; 260da347917Sbeck } 261da347917Sbeck 262da347917Sbeck ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); 263da347917Sbeck 264da347917Sbeck BN_free(abs_m); 265da347917Sbeck return ret; 266da347917Sbeck } 267da347917Sbeck 268da347917Sbeck /* BN_mod_lshift variant that may be used if a is non-negative 269da347917Sbeck * and less than m */ 2702bd9bb84Sjsing int 2712bd9bb84Sjsing BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) 272da347917Sbeck { 2732bd9bb84Sjsing if (r != a) { 2742bd9bb84Sjsing if (BN_copy(r, a) == NULL) 2752bd9bb84Sjsing return 0; 276da347917Sbeck } 277da347917Sbeck 2782bd9bb84Sjsing while (n > 0) { 279da347917Sbeck int max_shift; 280da347917Sbeck 281da347917Sbeck /* 0 < r < m */ 282da347917Sbeck max_shift = BN_num_bits(m) - BN_num_bits(r); 283da347917Sbeck /* max_shift >= 0 */ 284da347917Sbeck 2852bd9bb84Sjsing if (max_shift < 0) { 2865067ae9fSbeck BNerror(BN_R_INPUT_NOT_REDUCED); 287da347917Sbeck return 0; 288da347917Sbeck } 289da347917Sbeck 290da347917Sbeck if (max_shift > n) 291da347917Sbeck max_shift = n; 292da347917Sbeck 2932bd9bb84Sjsing if (max_shift) { 2942bd9bb84Sjsing if (!BN_lshift(r, r, max_shift)) 2952bd9bb84Sjsing return 0; 296da347917Sbeck n -= max_shift; 2972bd9bb84Sjsing } else { 2982bd9bb84Sjsing if (!BN_lshift1(r, r)) 2992bd9bb84Sjsing return 0; 300da347917Sbeck --n; 301da347917Sbeck } 302da347917Sbeck 303da347917Sbeck /* BN_num_bits(r) <= BN_num_bits(m) */ 304da347917Sbeck 3052bd9bb84Sjsing if (BN_cmp(r, m) >= 0) { 3062bd9bb84Sjsing if (!BN_sub(r, r, m)) 3072bd9bb84Sjsing return 0; 308da347917Sbeck } 309da347917Sbeck } 310da347917Sbeck 311da347917Sbeck return 1; 312da347917Sbeck } 313