1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh (at) cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay (at) cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh (at) cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] 56 */ 57 /* ==================================================================== 58 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 59 * 60 * Redistribution and use in source and binary forms, with or without 61 * modification, are permitted provided that the following conditions 62 * are met: 63 * 64 * 1. Redistributions of source code must retain the above copyright 65 * notice, this list of conditions and the following disclaimer. 66 * 67 * 2. Redistributions in binary form must reproduce the above copyright 68 * notice, this list of conditions and the following disclaimer in 69 * the documentation and/or other materials provided with the 70 * distribution. 71 * 72 * 3. All advertising materials mentioning features or use of this 73 * software must display the following acknowledgment: 74 * "This product includes software developed by the OpenSSL Project 75 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 76 * 77 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 78 * endorse or promote products derived from this software without 79 * prior written permission. For written permission, please contact 80 * openssl-core (at) openssl.org. 81 * 82 * 5. Products derived from this software may not be called "OpenSSL" 83 * nor may "OpenSSL" appear in their names without prior written 84 * permission of the OpenSSL Project. 85 * 86 * 6. Redistributions of any form whatsoever must retain the following 87 * acknowledgment: 88 * "This product includes software developed by the OpenSSL Project 89 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 90 * 91 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 92 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 93 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 94 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 95 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 96 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 97 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 98 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 99 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 100 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 101 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 102 * OF THE POSSIBILITY OF SUCH DAMAGE. 103 * ==================================================================== 104 * 105 * This product includes cryptographic software written by Eric Young 106 * (eay (at) cryptsoft.com). This product includes software written by Tim 107 * Hudson (tjh (at) cryptsoft.com). */ 108 109 #include <openssl/bn.h> 110 111 #include <openssl/err.h> 112 113 #include "internal.h" 114 115 116 int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, 117 const BIGNUM *n, BN_CTX *ctx) { 118 *out_no_inverse = 0; 119 120 if (!BN_is_odd(n)) { 121 OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS); 122 return 0; 123 } 124 125 if (BN_is_negative(a) || BN_cmp(a, n) >= 0) { 126 OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); 127 return 0; 128 } 129 130 BIGNUM *A, *B, *X, *Y; 131 int ret = 0; 132 int sign; 133 134 BN_CTX_start(ctx); 135 A = BN_CTX_get(ctx); 136 B = BN_CTX_get(ctx); 137 X = BN_CTX_get(ctx); 138 Y = BN_CTX_get(ctx); 139 if (Y == NULL) { 140 goto err; 141 } 142 143 BIGNUM *R = out; 144 145 BN_zero(Y); 146 if (!BN_one(X) || BN_copy(B, a) == NULL || BN_copy(A, n) == NULL) { 147 goto err; 148 } 149 A->neg = 0; 150 sign = -1; 151 // From B = a mod |n|, A = |n| it follows that 152 // 153 // 0 <= B < A, 154 // -sign*X*a == B (mod |n|), 155 // sign*Y*a == A (mod |n|). 156 157 // Binary inversion algorithm; requires odd modulus. This is faster than the 158 // general algorithm if the modulus is sufficiently small (about 400 .. 500 159 // bits on 32-bit systems, but much more on 64-bit systems) 160 int shift; 161 162 while (!BN_is_zero(B)) { 163 // 0 < B < |n|, 164 // 0 < A <= |n|, 165 // (1) -sign*X*a == B (mod |n|), 166 // (2) sign*Y*a == A (mod |n|) 167 168 // Now divide B by the maximum possible power of two in the integers, 169 // and divide X by the same value mod |n|. 170 // When we're done, (1) still holds. 171 shift = 0; 172 while (!BN_is_bit_set(B, shift)) { 173 // note that 0 < B 174 shift++; 175 176 if (BN_is_odd(X)) { 177 if (!BN_uadd(X, X, n)) { 178 goto err; 179 } 180 } 181 // now X is even, so we can easily divide it by two 182 if (!BN_rshift1(X, X)) { 183 goto err; 184 } 185 } 186 if (shift > 0) { 187 if (!BN_rshift(B, B, shift)) { 188 goto err; 189 } 190 } 191 192 // Same for A and Y. Afterwards, (2) still holds. 193 shift = 0; 194 while (!BN_is_bit_set(A, shift)) { 195 // note that 0 < A 196 shift++; 197 198 if (BN_is_odd(Y)) { 199 if (!BN_uadd(Y, Y, n)) { 200 goto err; 201 } 202 } 203 // now Y is even 204 if (!BN_rshift1(Y, Y)) { 205 goto err; 206 } 207 } 208 if (shift > 0) { 209 if (!BN_rshift(A, A, shift)) { 210 goto err; 211 } 212 } 213 214 // We still have (1) and (2). 215 // Both A and B are odd. 216 // The following computations ensure that 217 // 218 // 0 <= B < |n|, 219 // 0 < A < |n|, 220 // (1) -sign*X*a == B (mod |n|), 221 // (2) sign*Y*a == A (mod |n|), 222 // 223 // and that either A or B is even in the next iteration. 224 if (BN_ucmp(B, A) >= 0) { 225 // -sign*(X + Y)*a == B - A (mod |n|) 226 if (!BN_uadd(X, X, Y)) { 227 goto err; 228 } 229 // NB: we could use BN_mod_add_quick(X, X, Y, n), but that 230 // actually makes the algorithm slower 231 if (!BN_usub(B, B, A)) { 232 goto err; 233 } 234 } else { 235 // sign*(X + Y)*a == A - B (mod |n|) 236 if (!BN_uadd(Y, Y, X)) { 237 goto err; 238 } 239 // as above, BN_mod_add_quick(Y, Y, X, n) would slow things down 240 if (!BN_usub(A, A, B)) { 241 goto err; 242 } 243 } 244 } 245 246 if (!BN_is_one(A)) { 247 *out_no_inverse = 1; 248 OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE); 249 goto err; 250 } 251 252 // The while loop (Euclid's algorithm) ends when 253 // A == gcd(a,n); 254 // we have 255 // sign*Y*a == A (mod |n|), 256 // where Y is non-negative. 257 258 if (sign < 0) { 259 if (!BN_sub(Y, n, Y)) { 260 goto err; 261 } 262 } 263 // Now Y*a == A (mod |n|). 264 265 // Y*a == 1 (mod |n|) 266 if (!Y->neg && BN_ucmp(Y, n) < 0) { 267 if (!BN_copy(R, Y)) { 268 goto err; 269 } 270 } else { 271 if (!BN_nnmod(R, Y, n, ctx)) { 272 goto err; 273 } 274 } 275 276 ret = 1; 277 278 err: 279 BN_CTX_end(ctx); 280 return ret; 281 } 282 283 BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n, 284 BN_CTX *ctx) { 285 BIGNUM *new_out = NULL; 286 if (out == NULL) { 287 new_out = BN_new(); 288 if (new_out == NULL) { 289 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 290 return NULL; 291 } 292 out = new_out; 293 } 294 295 int ok = 0; 296 BIGNUM *a_reduced = NULL; 297 if (a->neg || BN_ucmp(a, n) >= 0) { 298 a_reduced = BN_dup(a); 299 if (a_reduced == NULL) { 300 goto err; 301 } 302 if (!BN_nnmod(a_reduced, a_reduced, n, ctx)) { 303 goto err; 304 } 305 a = a_reduced; 306 } 307 308 int no_inverse; 309 if (!BN_is_odd(n)) { 310 if (!bn_mod_inverse_consttime(out, &no_inverse, a, n, ctx)) { 311 goto err; 312 } 313 } else if (!BN_mod_inverse_odd(out, &no_inverse, a, n, ctx)) { 314 goto err; 315 } 316 317 ok = 1; 318 319 err: 320 if (!ok) { 321 BN_free(new_out); 322 out = NULL; 323 } 324 BN_free(a_reduced); 325 return out; 326 } 327 328 int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a, 329 const BN_MONT_CTX *mont, BN_CTX *ctx) { 330 *out_no_inverse = 0; 331 332 if (BN_is_negative(a) || BN_cmp(a, &mont->N) >= 0) { 333 OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED); 334 return 0; 335 } 336 337 int ret = 0; 338 BIGNUM blinding_factor; 339 BN_init(&blinding_factor); 340 341 if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) || 342 !BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) || 343 !BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) || 344 !BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) { 345 OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB); 346 goto err; 347 } 348 349 ret = 1; 350 351 err: 352 BN_free(&blinding_factor); 353 return ret; 354 } 355 356 int bn_mod_inverse_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, 357 BN_CTX *ctx, const BN_MONT_CTX *mont_p) { 358 BN_CTX_start(ctx); 359 BIGNUM *p_minus_2 = BN_CTX_get(ctx); 360 int ok = p_minus_2 != NULL && 361 BN_copy(p_minus_2, p) && 362 BN_sub_word(p_minus_2, 2) && 363 BN_mod_exp_mont(out, a, p_minus_2, p, ctx, mont_p); 364 BN_CTX_end(ctx); 365 return ok; 366 } 367 368 int bn_mod_inverse_secret_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p, 369 BN_CTX *ctx, const BN_MONT_CTX *mont_p) { 370 BN_CTX_start(ctx); 371 BIGNUM *p_minus_2 = BN_CTX_get(ctx); 372 int ok = p_minus_2 != NULL && 373 BN_copy(p_minus_2, p) && 374 BN_sub_word(p_minus_2, 2) && 375 BN_mod_exp_mont_consttime(out, a, p_minus_2, p, ctx, mont_p); 376 BN_CTX_end(ctx); 377 return ok; 378 } 379
