1 /* $OpenBSD: bn_recp.c,v 1.30 2025/01/22 12:53:16 tb Exp $ */ 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 59 #include <stdio.h> 60 61 #include <openssl/err.h> 62 63 #include "bn_local.h" 64 65 struct bn_recp_ctx_st { 66 BIGNUM *N; /* the divisor */ 67 BIGNUM *Nr; /* the reciprocal 2^shift / N */ 68 int num_bits; /* number of bits in N */ 69 int shift; 70 } /* BN_RECP_CTX */; 71 72 BN_RECP_CTX * 73 BN_RECP_CTX_create(const BIGNUM *N) 74 { 75 BN_RECP_CTX *recp; 76 77 if ((recp = calloc(1, sizeof(*recp))) == NULL) 78 goto err; 79 80 if ((recp->N = BN_dup(N)) == NULL) 81 goto err; 82 BN_set_negative(recp->N, 0); 83 recp->num_bits = BN_num_bits(recp->N); 84 85 if ((recp->Nr = BN_new()) == NULL) 86 goto err; 87 88 return recp; 89 90 err: 91 BN_RECP_CTX_free(recp); 92 93 return NULL; 94 } 95 96 void 97 BN_RECP_CTX_free(BN_RECP_CTX *recp) 98 { 99 if (recp == NULL) 100 return; 101 102 BN_free(recp->N); 103 BN_free(recp->Nr); 104 freezero(recp, sizeof(*recp)); 105 } 106 107 /* len is the expected size of the result 108 * We actually calculate with an extra word of precision, so 109 * we can do faster division if the remainder is not required. 110 */ 111 /* r := 2^len / m */ 112 static int 113 BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx) 114 { 115 int ret = -1; 116 BIGNUM *t; 117 118 BN_CTX_start(ctx); 119 if ((t = BN_CTX_get(ctx)) == NULL) 120 goto err; 121 122 if (!BN_set_bit(t, len)) 123 goto err; 124 125 if (!BN_div_ct(r, NULL, t, m, ctx)) 126 goto err; 127 128 ret = len; 129 130 err: 131 BN_CTX_end(ctx); 132 return ret; 133 } 134 135 int 136 BN_div_reciprocal(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp, 137 BN_CTX *ctx) 138 { 139 int i, j, ret = 0; 140 BIGNUM *a, *b, *d, *r; 141 142 BN_CTX_start(ctx); 143 a = BN_CTX_get(ctx); 144 b = BN_CTX_get(ctx); 145 if (dv != NULL) 146 d = dv; 147 else 148 d = BN_CTX_get(ctx); 149 if (rem != NULL) 150 r = rem; 151 else 152 r = BN_CTX_get(ctx); 153 if (a == NULL || b == NULL || d == NULL || r == NULL) 154 goto err; 155 156 if (BN_ucmp(m, recp->N) < 0) { 157 BN_zero(d); 158 if (!bn_copy(r, m)) { 159 BN_CTX_end(ctx); 160 return 0; 161 } 162 BN_CTX_end(ctx); 163 return 1; 164 } 165 166 /* We want the remainder 167 * Given input of ABCDEF / ab 168 * we need multiply ABCDEF by 3 digests of the reciprocal of ab 169 * 170 */ 171 172 /* i := max(BN_num_bits(m), 2*BN_num_bits(N)) */ 173 i = BN_num_bits(m); 174 j = recp->num_bits << 1; 175 if (j > i) 176 i = j; 177 178 /* Nr := round(2^i / N) */ 179 if (i != recp->shift) 180 recp->shift = BN_reciprocal(recp->Nr, recp->N, i, ctx); 181 182 /* BN_reciprocal returns i, or -1 for an error */ 183 if (recp->shift == -1) 184 goto err; 185 186 /* d := |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))| 187 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))| 188 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)| 189 * = |m/N| 190 */ 191 if (!BN_rshift(a, m, recp->num_bits)) 192 goto err; 193 if (!BN_mul(b, a, recp->Nr, ctx)) 194 goto err; 195 if (!BN_rshift(d, b, i - recp->num_bits)) 196 goto err; 197 d->neg = 0; 198 199 if (!BN_mul(b, recp->N, d, ctx)) 200 goto err; 201 if (!BN_usub(r, m, b)) 202 goto err; 203 r->neg = 0; 204 205 #if 1 206 j = 0; 207 while (BN_ucmp(r, recp->N) >= 0) { 208 if (j++ > 2) { 209 BNerror(BN_R_BAD_RECIPROCAL); 210 goto err; 211 } 212 if (!BN_usub(r, r, recp->N)) 213 goto err; 214 if (!BN_add_word(d, 1)) 215 goto err; 216 } 217 #endif 218 219 BN_set_negative(r, m->neg); 220 BN_set_negative(d, m->neg ^ recp->N->neg); 221 222 ret = 1; 223 224 err: 225 BN_CTX_end(ctx); 226 return ret; 227 } 228 229 /* Compute r = (x * y) % m. */ 230 int 231 BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, 232 BN_RECP_CTX *recp, BN_CTX *ctx) 233 { 234 if (!BN_mul(r, x, y, ctx)) 235 return 0; 236 237 return BN_div_reciprocal(NULL, r, r, recp, ctx); 238 } 239 240 /* Compute r = x^2 % m. */ 241 int 242 BN_mod_sqr_reciprocal(BIGNUM *r, const BIGNUM *x, BN_RECP_CTX *recp, BN_CTX *ctx) 243 { 244 if (!BN_sqr(r, x, ctx)) 245 return 0; 246 247 return BN_div_reciprocal(NULL, r, r, recp, ctx); 248 } 249