legacy-libs/grpc/deps/grpc/third_party/boringssl/crypto/fipsmodule/bn/gcd.c

   1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
   2  * All rights reserved.
   3  *
   4  * This package is an SSL implementation written
   5  * by Eric Young (eay@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@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@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@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@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@cryptsoft.com).  This product includes software written by Tim
 107  * Hudson (tjh@cryptsoft.com). */
 108
 109 #include <openssl/bn.h>
 110
 111 #include <assert.h>
 112
 113 #include <openssl/err.h>
 114
 115 #include "internal.h"
 116
 117
 118 static BN_ULONG word_is_odd_mask(BN_ULONG a) { return (BN_ULONG)0 - (a & 1); }
 119
 120 static void maybe_rshift1_words(BN_ULONG *a, BN_ULONG mask, BN_ULONG *tmp,
 121                                 size_t num) {
 122   bn_rshift1_words(tmp, a, num);
 123   bn_select_words(a, mask, tmp, a, num);
 124 }
 125
 126 static void maybe_rshift1_words_carry(BN_ULONG *a, BN_ULONG carry,
 127                                       BN_ULONG mask, BN_ULONG *tmp,
 128                                       size_t num) {
 129   maybe_rshift1_words(a, mask, tmp, num);
 130   if (num != 0) {
 131     carry &= mask;
 132     a[num - 1] |= carry << (BN_BITS2-1);
 133   }
 134 }
 135
 136 static BN_ULONG maybe_add_words(BN_ULONG *a, BN_ULONG mask, const BN_ULONG *b,
 137                                 BN_ULONG *tmp, size_t num) {
 138   BN_ULONG carry = bn_add_words(tmp, a, b, num);
 139   bn_select_words(a, mask, tmp, a, num);
 140   return carry & mask;
 141 }
 142
 143 static int bn_gcd_consttime(BIGNUM *r, unsigned *out_shift, const BIGNUM *x,
 144                             const BIGNUM *y, BN_CTX *ctx) {
 145   size_t width = x->width > y->width ? x->width : y->width;
 146   if (width == 0) {
 147     *out_shift = 0;
 148     BN_zero(r);
 149     return 1;
 150   }
 151
 152   // This is a constant-time implementation of Stein's algorithm (binary GCD).
 153   int ret = 0;
 154   BN_CTX_start(ctx);
 155   BIGNUM *u = BN_CTX_get(ctx);
 156   BIGNUM *v = BN_CTX_get(ctx);
 157   BIGNUM *tmp = BN_CTX_get(ctx);
 158   if (u == NULL || v == NULL || tmp == NULL ||
 159       !BN_copy(u, x) ||
 160       !BN_copy(v, y) ||
 161       !bn_resize_words(u, width) ||
 162       !bn_resize_words(v, width) ||
 163       !bn_resize_words(tmp, width)) {
 164     goto err;
 165   }
 166
 167   // Each loop iteration halves at least one of |u| and |v|. Thus we need at
 168   // most the combined bit width of inputs for at least one value to be zero.
 169   unsigned x_bits = x->width * BN_BITS2, y_bits = y->width * BN_BITS2;
 170   unsigned num_iters = x_bits + y_bits;
 171   if (num_iters < x_bits) {
 172     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
 173     goto err;
 174   }
 175
 176   unsigned shift = 0;
 177   for (unsigned i = 0; i < num_iters; i++) {
 178     BN_ULONG both_odd = word_is_odd_mask(u->d[0]) & word_is_odd_mask(v->d[0]);
 179
 180     // If both |u| and |v| are odd, subtract the smaller from the larger.
 181     BN_ULONG u_less_than_v =
 182         (BN_ULONG)0 - bn_sub_words(tmp->d, u->d, v->d, width);
 183     bn_select_words(u->d, both_odd & ~u_less_than_v, tmp->d, u->d, width);
 184     bn_sub_words(tmp->d, v->d, u->d, width);
 185     bn_select_words(v->d, both_odd & u_less_than_v, tmp->d, v->d, width);
 186
 187     // At least one of |u| and |v| is now even.
 188     BN_ULONG u_is_odd = word_is_odd_mask(u->d[0]);
 189     BN_ULONG v_is_odd = word_is_odd_mask(v->d[0]);
 190     assert(!(u_is_odd & v_is_odd));
 191
 192     // If both are even, the final GCD gains a factor of two.
 193     shift += 1 & (~u_is_odd & ~v_is_odd);
 194
 195     // Halve any which are even.
 196     maybe_rshift1_words(u->d, ~u_is_odd, tmp->d, width);
 197     maybe_rshift1_words(v->d, ~v_is_odd, tmp->d, width);
 198   }
 199
 200   // One of |u| or |v| is zero at this point. The algorithm usually makes |u|
 201   // zero, unless |y| was already zero on input. Fix this by combining the
 202   // values.
 203   assert(BN_is_zero(u) || BN_is_zero(v));
 204   for (size_t i = 0; i < width; i++) {
 205     v->d[i] |= u->d[i];
 206   }
 207
 208   *out_shift = shift;
 209   ret = bn_set_words(r, v->d, width);
 210
 211 err:
 212   BN_CTX_end(ctx);
 213   return ret;
 214 }
 215
 216 int BN_gcd(BIGNUM *r, const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx) {
 217   unsigned shift;
 218   return bn_gcd_consttime(r, &shift, x, y, ctx) &&
 219          BN_lshift(r, r, shift);
 220 }
 221
 222 int bn_is_relatively_prime(int *out_relatively_prime, const BIGNUM *x,
 223                            const BIGNUM *y, BN_CTX *ctx) {
 224   int ret = 0;
 225   BN_CTX_start(ctx);
 226   unsigned shift;
 227   BIGNUM *gcd = BN_CTX_get(ctx);
 228   if (gcd == NULL ||
 229       !bn_gcd_consttime(gcd, &shift, x, y, ctx)) {
 230     goto err;
 231   }
 232
 233   // Check that 2^|shift| * |gcd| is one.
 234   if (gcd->width == 0) {
 235     *out_relatively_prime = 0;
 236   } else {
 237     BN_ULONG mask = shift | (gcd->d[0] ^ 1);
 238     for (int i = 1; i < gcd->width; i++) {
 239       mask |= gcd->d[i];
 240     }
 241     *out_relatively_prime = mask == 0;
 242   }
 243   ret = 1;
 244
 245 err:
 246   BN_CTX_end(ctx);
 247   return ret;
 248 }
 249
 250 int bn_lcm_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) {
 251   BN_CTX_start(ctx);
 252   unsigned shift;
 253   BIGNUM *gcd = BN_CTX_get(ctx);
 254   int ret = gcd != NULL &&
 255             bn_mul_consttime(r, a, b, ctx) &&
 256             bn_gcd_consttime(gcd, &shift, a, b, ctx) &&
 257             bn_div_consttime(r, NULL, r, gcd, ctx) &&
 258             bn_rshift_secret_shift(r, r, shift, ctx);
 259   BN_CTX_end(ctx);
 260   return ret;
 261 }
 262
 263 int bn_mod_inverse_consttime(BIGNUM *r, int *out_no_inverse, const BIGNUM *a,
 264                              const BIGNUM *n, BN_CTX *ctx) {
 265   *out_no_inverse = 0;
 266   if (BN_is_negative(a) || BN_ucmp(a, n) >= 0) {
 267     OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
 268     return 0;
 269   }
 270   if (BN_is_zero(a)) {
 271     if (BN_is_one(n)) {
 272       BN_zero(r);
 273       return 1;
 274     }
 275     *out_no_inverse = 1;
 276     OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE);
 277     return 0;
 278   }
 279
 280   // This is a constant-time implementation of the extended binary GCD
 281   // algorithm. It is adapted from the Handbook of Applied Cryptography, section
 282   // 14.4.3, algorithm 14.51, and modified to bound coefficients and avoid
 283   // negative numbers.
 284   //
 285   // For more details and proof of correctness, see
 286   // https://github.com/mit-plv/fiat-crypto/pull/333. In particular, see |step|
 287   // and |mod_inverse_consttime| for the algorithm in Gallina and see
 288   // |mod_inverse_consttime_spec| for the correctness result.
 289
 290   if (!BN_is_odd(a) && !BN_is_odd(n)) {
 291     *out_no_inverse = 1;
 292     OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE);
 293     return 0;
 294   }
 295
 296   // This function exists to compute the RSA private exponent, where |a| is one
 297   // word. We'll thus use |a_width| when available.
 298   size_t n_width = n->width, a_width = a->width;
 299   if (a_width > n_width) {
 300     a_width = n_width;
 301   }
 302
 303   int ret = 0;
 304   BN_CTX_start(ctx);
 305   BIGNUM *u = BN_CTX_get(ctx);
 306   BIGNUM *v = BN_CTX_get(ctx);
 307   BIGNUM *A = BN_CTX_get(ctx);
 308   BIGNUM *B = BN_CTX_get(ctx);
 309   BIGNUM *C = BN_CTX_get(ctx);
 310   BIGNUM *D = BN_CTX_get(ctx);
 311   BIGNUM *tmp = BN_CTX_get(ctx);
 312   BIGNUM *tmp2 = BN_CTX_get(ctx);
 313   if (u == NULL || v == NULL || A == NULL || B == NULL || C == NULL ||
 314       D == NULL || tmp == NULL || tmp2 == NULL ||
 315       !BN_copy(u, a) ||
 316       !BN_copy(v, n) ||
 317       !BN_one(A) ||
 318       !BN_one(D) ||
 319       // For convenience, size |u| and |v| equivalently.
 320       !bn_resize_words(u, n_width) ||
 321       !bn_resize_words(v, n_width) ||
 322       // |A| and |C| are bounded by |m|.
 323       !bn_resize_words(A, n_width) ||
 324       !bn_resize_words(C, n_width) ||
 325       // |B| and |D| are bounded by |a|.
 326       !bn_resize_words(B, a_width) ||
 327       !bn_resize_words(D, a_width) ||
 328       // |tmp| and |tmp2| may be used at either size.
 329       !bn_resize_words(tmp, n_width) ||
 330       !bn_resize_words(tmp2, n_width)) {
 331     goto err;
 332   }
 333
 334   // Each loop iteration halves at least one of |u| and |v|. Thus we need at
 335   // most the combined bit width of inputs for at least one value to be zero.
 336   unsigned a_bits = a_width * BN_BITS2, n_bits = n_width * BN_BITS2;
 337   unsigned num_iters = a_bits + n_bits;
 338   if (num_iters < a_bits) {
 339     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
 340     goto err;
 341   }
 342
 343   // Before and after each loop iteration, the following hold:
 344   //
 345   //   u = A*a - B*n
 346   //   v = D*n - C*a
 347   //   0 < u <= a
 348   //   0 <= v <= n
 349   //   0 <= A < n
 350   //   0 <= B <= a
 351   //   0 <= C < n
 352   //   0 <= D <= a
 353   //
 354   // After each loop iteration, u and v only get smaller, and at least one of
 355   // them shrinks by at least a factor of two.
 356   for (unsigned i = 0; i < num_iters; i++) {
 357     BN_ULONG both_odd = word_is_odd_mask(u->d[0]) & word_is_odd_mask(v->d[0]);
 358
 359     // If both |u| and |v| are odd, subtract the smaller from the larger.
 360     BN_ULONG v_less_than_u =
 361         (BN_ULONG)0 - bn_sub_words(tmp->d, v->d, u->d, n_width);
 362     bn_select_words(v->d, both_odd & ~v_less_than_u, tmp->d, v->d, n_width);
 363     bn_sub_words(tmp->d, u->d, v->d, n_width);
 364     bn_select_words(u->d, both_odd & v_less_than_u, tmp->d, u->d, n_width);
 365
 366     // If we updated one of the values, update the corresponding coefficient.
 367     BN_ULONG carry = bn_add_words(tmp->d, A->d, C->d, n_width);
 368     carry -= bn_sub_words(tmp2->d, tmp->d, n->d, n_width);
 369     bn_select_words(tmp->d, carry, tmp->d, tmp2->d, n_width);
 370     bn_select_words(A->d, both_odd & v_less_than_u, tmp->d, A->d, n_width);
 371     bn_select_words(C->d, both_odd & ~v_less_than_u, tmp->d, C->d, n_width);
 372
 373     bn_add_words(tmp->d, B->d, D->d, a_width);
 374     bn_sub_words(tmp2->d, tmp->d, a->d, a_width);
 375     bn_select_words(tmp->d, carry, tmp->d, tmp2->d, a_width);
 376     bn_select_words(B->d, both_odd & v_less_than_u, tmp->d, B->d, a_width);
 377     bn_select_words(D->d, both_odd & ~v_less_than_u, tmp->d, D->d, a_width);
 378
 379     // Our loop invariants hold at this point. Additionally, exactly one of |u|
 380     // and |v| is now even.
 381     BN_ULONG u_is_even = ~word_is_odd_mask(u->d[0]);
 382     BN_ULONG v_is_even = ~word_is_odd_mask(v->d[0]);
 383     assert(u_is_even != v_is_even);
 384
 385     // Halve the even one and adjust the corresponding coefficient.
 386     maybe_rshift1_words(u->d, u_is_even, tmp->d, n_width);
 387     BN_ULONG A_or_B_is_odd =
 388         word_is_odd_mask(A->d[0]) | word_is_odd_mask(B->d[0]);
 389     BN_ULONG A_carry =
 390         maybe_add_words(A->d, A_or_B_is_odd & u_is_even, n->d, tmp->d, n_width);
 391     BN_ULONG B_carry =
 392         maybe_add_words(B->d, A_or_B_is_odd & u_is_even, a->d, tmp->d, a_width);
 393     maybe_rshift1_words_carry(A->d, A_carry, u_is_even, tmp->d, n_width);
 394     maybe_rshift1_words_carry(B->d, B_carry, u_is_even, tmp->d, a_width);
 395
 396     maybe_rshift1_words(v->d, v_is_even, tmp->d, n_width);
 397     BN_ULONG C_or_D_is_odd =
 398         word_is_odd_mask(C->d[0]) | word_is_odd_mask(D->d[0]);
 399     BN_ULONG C_carry =
 400         maybe_add_words(C->d, C_or_D_is_odd & v_is_even, n->d, tmp->d, n_width);
 401     BN_ULONG D_carry =
 402         maybe_add_words(D->d, C_or_D_is_odd & v_is_even, a->d, tmp->d, a_width);
 403     maybe_rshift1_words_carry(C->d, C_carry, v_is_even, tmp->d, n_width);
 404     maybe_rshift1_words_carry(D->d, D_carry, v_is_even, tmp->d, a_width);
 405   }
 406
 407   assert(BN_is_zero(v));
 408   if (!BN_is_one(u)) {
 409     *out_no_inverse = 1;
 410     OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE);
 411     goto err;
 412   }
 413
 414   ret = BN_copy(r, A) != NULL;
 415
 416 err:
 417   BN_CTX_end(ctx);
 418   return ret;
 419 }
 420
 421 int BN_mod_inverse_odd(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
 422                        const BIGNUM *n, BN_CTX *ctx) {
 423   *out_no_inverse = 0;
 424
 425   if (!BN_is_odd(n)) {
 426     OPENSSL_PUT_ERROR(BN, BN_R_CALLED_WITH_EVEN_MODULUS);
 427     return 0;
 428   }
 429
 430   if (BN_is_negative(a) || BN_cmp(a, n) >= 0) {
 431     OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
 432     return 0;
 433   }
 434
 435   BIGNUM *A, *B, *X, *Y;
 436   int ret = 0;
 437   int sign;
 438
 439   BN_CTX_start(ctx);
 440   A = BN_CTX_get(ctx);
 441   B = BN_CTX_get(ctx);
 442   X = BN_CTX_get(ctx);
 443   Y = BN_CTX_get(ctx);
 444   if (Y == NULL) {
 445     goto err;
 446   }
 447
 448   BIGNUM *R = out;
 449
 450   BN_zero(Y);
 451   if (!BN_one(X) || BN_copy(B, a) == NULL || BN_copy(A, n) == NULL) {
 452     goto err;
 453   }
 454   A->neg = 0;
 455   sign = -1;
 456   // From  B = a mod |n|,  A = |n|  it follows that
 457   //
 458   //      0 <= B < A,
 459   //     -sign*X*a  ==  B   (mod |n|),
 460   //      sign*Y*a  ==  A   (mod |n|).
 461
 462   // Binary inversion algorithm; requires odd modulus. This is faster than the
 463   // general algorithm if the modulus is sufficiently small (about 400 .. 500
 464   // bits on 32-bit systems, but much more on 64-bit systems)
 465   int shift;
 466
 467   while (!BN_is_zero(B)) {
 468     //      0 < B < |n|,
 469     //      0 < A <= |n|,
 470     // (1) -sign*X*a  ==  B   (mod |n|),
 471     // (2)  sign*Y*a  ==  A   (mod |n|)
 472
 473     // Now divide  B  by the maximum possible power of two in the integers,
 474     // and divide  X  by the same value mod |n|.
 475     // When we're done, (1) still holds.
 476     shift = 0;
 477     while (!BN_is_bit_set(B, shift)) {
 478       // note that 0 < B
 479       shift++;
 480
 481       if (BN_is_odd(X)) {
 482         if (!BN_uadd(X, X, n)) {
 483           goto err;
 484         }
 485       }
 486       // now X is even, so we can easily divide it by two
 487       if (!BN_rshift1(X, X)) {
 488         goto err;
 489       }
 490     }
 491     if (shift > 0) {
 492       if (!BN_rshift(B, B, shift)) {
 493         goto err;
 494       }
 495     }
 496
 497     // Same for A and Y. Afterwards, (2) still holds.
 498     shift = 0;
 499     while (!BN_is_bit_set(A, shift)) {
 500       // note that 0 < A
 501       shift++;
 502
 503       if (BN_is_odd(Y)) {
 504         if (!BN_uadd(Y, Y, n)) {
 505           goto err;
 506         }
 507       }
 508       // now Y is even
 509       if (!BN_rshift1(Y, Y)) {
 510         goto err;
 511       }
 512     }
 513     if (shift > 0) {
 514       if (!BN_rshift(A, A, shift)) {
 515         goto err;
 516       }
 517     }
 518
 519     // We still have (1) and (2).
 520     // Both  A  and  B  are odd.
 521     // The following computations ensure that
 522     //
 523     //     0 <= B < |n|,
 524     //      0 < A < |n|,
 525     // (1) -sign*X*a  ==  B   (mod |n|),
 526     // (2)  sign*Y*a  ==  A   (mod |n|),
 527     //
 528     // and that either  A  or  B  is even in the next iteration.
 529     if (BN_ucmp(B, A) >= 0) {
 530       // -sign*(X + Y)*a == B - A  (mod |n|)
 531       if (!BN_uadd(X, X, Y)) {
 532         goto err;
 533       }
 534       // NB: we could use BN_mod_add_quick(X, X, Y, n), but that
 535       // actually makes the algorithm slower
 536       if (!BN_usub(B, B, A)) {
 537         goto err;
 538       }
 539     } else {
 540       //  sign*(X + Y)*a == A - B  (mod |n|)
 541       if (!BN_uadd(Y, Y, X)) {
 542         goto err;
 543       }
 544       // as above, BN_mod_add_quick(Y, Y, X, n) would slow things down
 545       if (!BN_usub(A, A, B)) {
 546         goto err;
 547       }
 548     }
 549   }
 550
 551   if (!BN_is_one(A)) {
 552     *out_no_inverse = 1;
 553     OPENSSL_PUT_ERROR(BN, BN_R_NO_INVERSE);
 554     goto err;
 555   }
 556
 557   // The while loop (Euclid's algorithm) ends when
 558   //      A == gcd(a,n);
 559   // we have
 560   //       sign*Y*a  ==  A  (mod |n|),
 561   // where  Y  is non-negative.
 562
 563   if (sign < 0) {
 564     if (!BN_sub(Y, n, Y)) {
 565       goto err;
 566     }
 567   }
 568   // Now  Y*a  ==  A  (mod |n|).
 569
 570   // Y*a == 1  (mod |n|)
 571   if (!Y->neg && BN_ucmp(Y, n) < 0) {
 572     if (!BN_copy(R, Y)) {
 573       goto err;
 574     }
 575   } else {
 576     if (!BN_nnmod(R, Y, n, ctx)) {
 577       goto err;
 578     }
 579   }
 580
 581   ret = 1;
 582
 583 err:
 584   BN_CTX_end(ctx);
 585   return ret;
 586 }
 587
 588 BIGNUM *BN_mod_inverse(BIGNUM *out, const BIGNUM *a, const BIGNUM *n,
 589                        BN_CTX *ctx) {
 590   BIGNUM *new_out = NULL;
 591   if (out == NULL) {
 592     new_out = BN_new();
 593     if (new_out == NULL) {
 594       OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
 595       return NULL;
 596     }
 597     out = new_out;
 598   }
 599
 600   int ok = 0;
 601   BIGNUM *a_reduced = NULL;
 602   if (a->neg || BN_ucmp(a, n) >= 0) {
 603     a_reduced = BN_dup(a);
 604     if (a_reduced == NULL) {
 605       goto err;
 606     }
 607     if (!BN_nnmod(a_reduced, a_reduced, n, ctx)) {
 608       goto err;
 609     }
 610     a = a_reduced;
 611   }
 612
 613   int no_inverse;
 614   if (!BN_is_odd(n)) {
 615     if (!bn_mod_inverse_consttime(out, &no_inverse, a, n, ctx)) {
 616       goto err;
 617     }
 618   } else if (!BN_mod_inverse_odd(out, &no_inverse, a, n, ctx)) {
 619     goto err;
 620   }
 621
 622   ok = 1;
 623
 624 err:
 625   if (!ok) {
 626     BN_free(new_out);
 627     out = NULL;
 628   }
 629   BN_free(a_reduced);
 630   return out;
 631 }
 632
 633 int BN_mod_inverse_blinded(BIGNUM *out, int *out_no_inverse, const BIGNUM *a,
 634                            const BN_MONT_CTX *mont, BN_CTX *ctx) {
 635   *out_no_inverse = 0;
 636
 637   if (BN_is_negative(a) || BN_cmp(a, &mont->N) >= 0) {
 638     OPENSSL_PUT_ERROR(BN, BN_R_INPUT_NOT_REDUCED);
 639     return 0;
 640   }
 641
 642   int ret = 0;
 643   BIGNUM blinding_factor;
 644   BN_init(&blinding_factor);
 645
 646   if (!BN_rand_range_ex(&blinding_factor, 1, &mont->N) ||
 647       !BN_mod_mul_montgomery(out, &blinding_factor, a, mont, ctx) ||
 648       !BN_mod_inverse_odd(out, out_no_inverse, out, &mont->N, ctx) ||
 649       !BN_mod_mul_montgomery(out, &blinding_factor, out, mont, ctx)) {
 650     OPENSSL_PUT_ERROR(BN, ERR_R_BN_LIB);
 651     goto err;
 652   }
 653
 654   ret = 1;
 655
 656 err:
 657   BN_free(&blinding_factor);
 658   return ret;
 659 }
 660
 661 int bn_mod_inverse_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p,
 662                          BN_CTX *ctx, const BN_MONT_CTX *mont_p) {
 663   BN_CTX_start(ctx);
 664   BIGNUM *p_minus_2 = BN_CTX_get(ctx);
 665   int ok = p_minus_2 != NULL &&
 666            BN_copy(p_minus_2, p) &&
 667            BN_sub_word(p_minus_2, 2) &&
 668            BN_mod_exp_mont(out, a, p_minus_2, p, ctx, mont_p);
 669   BN_CTX_end(ctx);
 670   return ok;
 671 }
 672
 673 int bn_mod_inverse_secret_prime(BIGNUM *out, const BIGNUM *a, const BIGNUM *p,
 674                                 BN_CTX *ctx, const BN_MONT_CTX *mont_p) {
 675   BN_CTX_start(ctx);
 676   BIGNUM *p_minus_2 = BN_CTX_get(ctx);
 677   int ok = p_minus_2 != NULL &&
 678            BN_copy(p_minus_2, p) &&
 679            BN_sub_word(p_minus_2, 2) &&
 680            BN_mod_exp_mont_consttime(out, a, p_minus_2, p, ctx, mont_p);
 681   BN_CTX_end(ctx);
 682   return ok;
 683 }