crypto/bn/bn_gcd.c

   1 /*
   2  * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the Apache License 2.0 (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "internal/cryptlib.h"
  11 #include "bn_local.h"
  12 #include "internal/constant_time.h"
  13
  14 /*
  15  * bn_mod_inverse_no_branch is a special version of BN_mod_inverse. It does
  16  * not contain branches that may leak sensitive information.
  17  *
  18  * This is a static function, we ensure all callers in this file pass valid
  19  * arguments: all passed pointers here are non-NULL.
  20  */
  21 static ossl_inline
  22 BIGNUM *bn_mod_inverse_no_branch(BIGNUM *in,
  23                                  const BIGNUM *a, const BIGNUM *n,
  24                                  BN_CTX *ctx, int *pnoinv)
  25 {
  26     BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
  27     BIGNUM *ret = NULL;
  28     int sign;
  29
  30     bn_check_top(a);
  31     bn_check_top(n);
  32
  33     BN_CTX_start(ctx);
  34     A = BN_CTX_get(ctx);
  35     B = BN_CTX_get(ctx);
  36     X = BN_CTX_get(ctx);
  37     D = BN_CTX_get(ctx);
  38     M = BN_CTX_get(ctx);
  39     Y = BN_CTX_get(ctx);
  40     T = BN_CTX_get(ctx);
  41     if (T == NULL)
  42         goto err;
  43
  44     if (in == NULL)
  45         R = BN_new();
  46     else
  47         R = in;
  48     if (R == NULL)
  49         goto err;
  50
  51     if (!BN_one(X))
  52         goto err;
  53     BN_zero(Y);
  54     if (BN_copy(B, a) == NULL)
  55         goto err;
  56     if (BN_copy(A, n) == NULL)
  57         goto err;
  58     A->neg = 0;
  59
  60     if (B->neg || (BN_ucmp(B, A) >= 0)) {
  61         /*
  62          * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
  63          * BN_div_no_branch will be called eventually.
  64          */
  65          {
  66             BIGNUM local_B;
  67             bn_init(&local_B);
  68             BN_with_flags(&local_B, B, BN_FLG_CONSTTIME);
  69             if (!BN_nnmod(B, &local_B, A, ctx))
  70                 goto err;
  71             /* Ensure local_B goes out of scope before any further use of B */
  72         }
  73     }
  74     sign = -1;
  75     /*-
  76      * From  B = a mod |n|,  A = |n|  it follows that
  77      *
  78      *      0 <= B < A,
  79      *     -sign*X*a  ==  B   (mod |n|),
  80      *      sign*Y*a  ==  A   (mod |n|).
  81      */
  82
  83     while (!BN_is_zero(B)) {
  84         BIGNUM *tmp;
  85
  86         /*-
  87          *      0 < B < A,
  88          * (*) -sign*X*a  ==  B   (mod |n|),
  89          *      sign*Y*a  ==  A   (mod |n|)
  90          */
  91
  92         /*
  93          * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked,
  94          * BN_div_no_branch will be called eventually.
  95          */
  96         {
  97             BIGNUM local_A;
  98             bn_init(&local_A);
  99             BN_with_flags(&local_A, A, BN_FLG_CONSTTIME);
 100
 101             /* (D, M) := (A/B, A%B) ... */
 102             if (!BN_div(D, M, &local_A, B, ctx))
 103                 goto err;
 104             /* Ensure local_A goes out of scope before any further use of A */
 105         }
 106
 107         /*-
 108          * Now
 109          *      A = D*B + M;
 110          * thus we have
 111          * (**)  sign*Y*a  ==  D*B + M   (mod |n|).
 112          */
 113
 114         tmp = A;                /* keep the BIGNUM object, the value does not
 115                                  * matter */
 116
 117         /* (A, B) := (B, A mod B) ... */
 118         A = B;
 119         B = M;
 120         /* ... so we have  0 <= B < A  again */
 121
 122         /*-
 123          * Since the former  M  is now  B  and the former  B  is now  A,
 124          * (**) translates into
 125          *       sign*Y*a  ==  D*A + B    (mod |n|),
 126          * i.e.
 127          *       sign*Y*a - D*A  ==  B    (mod |n|).
 128          * Similarly, (*) translates into
 129          *      -sign*X*a  ==  A          (mod |n|).
 130          *
 131          * Thus,
 132          *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),
 133          * i.e.
 134          *        sign*(Y + D*X)*a  ==  B  (mod |n|).
 135          *
 136          * So if we set  (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
 137          *      -sign*X*a  ==  B   (mod |n|),
 138          *       sign*Y*a  ==  A   (mod |n|).
 139          * Note that  X  and  Y  stay non-negative all the time.
 140          */
 141
 142         if (!BN_mul(tmp, D, X, ctx))
 143             goto err;
 144         if (!BN_add(tmp, tmp, Y))
 145             goto err;
 146
 147         M = Y;                  /* keep the BIGNUM object, the value does not
 148                                  * matter */
 149         Y = X;
 150         X = tmp;
 151         sign = -sign;
 152     }
 153
 154     /*-
 155      * The while loop (Euclid's algorithm) ends when
 156      *      A == gcd(a,n);
 157      * we have
 158      *       sign*Y*a  ==  A  (mod |n|),
 159      * where  Y  is non-negative.
 160      */
 161
 162     if (sign < 0) {
 163         if (!BN_sub(Y, n, Y))
 164             goto err;
 165     }
 166     /* Now  Y*a  ==  A  (mod |n|).  */
 167
 168     if (BN_is_one(A)) {
 169         /* Y*a == 1  (mod |n|) */
 170         if (!Y->neg && BN_ucmp(Y, n) < 0) {
 171             if (!BN_copy(R, Y))
 172                 goto err;
 173         } else {
 174             if (!BN_nnmod(R, Y, n, ctx))
 175                 goto err;
 176         }
 177     } else {
 178         *pnoinv = 1;
 179         /* caller sets the BN_R_NO_INVERSE error */
 180         goto err;
 181     }
 182
 183     ret = R;
 184     *pnoinv = 0;
 185
 186  err:
 187     if ((ret == NULL) && (in == NULL))
 188         BN_free(R);
 189     BN_CTX_end(ctx);
 190     bn_check_top(ret);
 191     return ret;
 192 }
 193
 194 /*
 195  * This is an internal function, we assume all callers pass valid arguments:
 196  * all pointers passed here are assumed non-NULL.
 197  */
 198 BIGNUM *int_bn_mod_inverse(BIGNUM *in,
 199                            const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx,
 200                            int *pnoinv)
 201 {
 202     BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
 203     BIGNUM *ret = NULL;
 204     int sign;
 205
 206     /* This is invalid input so we don't worry about constant time here */
 207     if (BN_abs_is_word(n, 1) || BN_is_zero(n)) {
 208         *pnoinv = 1;
 209         return NULL;
 210     }
 211
 212     *pnoinv = 0;
 213
 214     if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0)
 215         || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) {
 216         return bn_mod_inverse_no_branch(in, a, n, ctx, pnoinv);
 217     }
 218
 219     bn_check_top(a);
 220     bn_check_top(n);
 221
 222     BN_CTX_start(ctx);
 223     A = BN_CTX_get(ctx);
 224     B = BN_CTX_get(ctx);
 225     X = BN_CTX_get(ctx);
 226     D = BN_CTX_get(ctx);
 227     M = BN_CTX_get(ctx);
 228     Y = BN_CTX_get(ctx);
 229     T = BN_CTX_get(ctx);
 230     if (T == NULL)
 231         goto err;
 232
 233     if (in == NULL)
 234         R = BN_new();
 235     else
 236         R = in;
 237     if (R == NULL)
 238         goto err;
 239
 240     if (!BN_one(X))
 241         goto err;
 242     BN_zero(Y);
 243     if (BN_copy(B, a) == NULL)
 244         goto err;
 245     if (BN_copy(A, n) == NULL)
 246         goto err;
 247     A->neg = 0;
 248     if (B->neg || (BN_ucmp(B, A) >= 0)) {
 249         if (!BN_nnmod(B, B, A, ctx))
 250             goto err;
 251     }
 252     sign = -1;
 253     /*-
 254      * From  B = a mod |n|,  A = |n|  it follows that
 255      *
 256      *      0 <= B < A,
 257      *     -sign*X*a  ==  B   (mod |n|),
 258      *      sign*Y*a  ==  A   (mod |n|).
 259      */
 260
 261     if (BN_is_odd(n) && (BN_num_bits(n) <= 2048)) {
 262         /*
 263          * Binary inversion algorithm; requires odd modulus. This is faster
 264          * than the general algorithm if the modulus is sufficiently small
 265          * (about 400 .. 500 bits on 32-bit systems, but much more on 64-bit
 266          * systems)
 267          */
 268         int shift;
 269
 270         while (!BN_is_zero(B)) {
 271             /*-
 272              *      0 < B < |n|,
 273              *      0 < A <= |n|,
 274              * (1) -sign*X*a  ==  B   (mod |n|),
 275              * (2)  sign*Y*a  ==  A   (mod |n|)
 276              */
 277
 278             /*
 279              * Now divide B by the maximum possible power of two in the
 280              * integers, and divide X by the same value mod |n|. When we're
 281              * done, (1) still holds.
 282              */
 283             shift = 0;
 284             while (!BN_is_bit_set(B, shift)) { /* note that 0 < B */
 285                 shift++;
 286
 287                 if (BN_is_odd(X)) {
 288                     if (!BN_uadd(X, X, n))
 289                         goto err;
 290                 }
 291                 /*
 292                  * now X is even, so we can easily divide it by two
 293                  */
 294                 if (!BN_rshift1(X, X))
 295                     goto err;
 296             }
 297             if (shift > 0) {
 298                 if (!BN_rshift(B, B, shift))
 299                     goto err;
 300             }
 301
 302             /*
 303              * Same for A and Y.  Afterwards, (2) still holds.
 304              */
 305             shift = 0;
 306             while (!BN_is_bit_set(A, shift)) { /* note that 0 < A */
 307                 shift++;
 308
 309                 if (BN_is_odd(Y)) {
 310                     if (!BN_uadd(Y, Y, n))
 311                         goto err;
 312                 }
 313                 /* now Y is even */
 314                 if (!BN_rshift1(Y, Y))
 315                     goto err;
 316             }
 317             if (shift > 0) {
 318                 if (!BN_rshift(A, A, shift))
 319                     goto err;
 320             }
 321
 322             /*-
 323              * We still have (1) and (2).
 324              * Both  A  and  B  are odd.
 325              * The following computations ensure that
 326              *
 327              *     0 <= B < |n|,
 328              *      0 < A < |n|,
 329              * (1) -sign*X*a  ==  B   (mod |n|),
 330              * (2)  sign*Y*a  ==  A   (mod |n|),
 331              *
 332              * and that either  A  or  B  is even in the next iteration.
 333              */
 334             if (BN_ucmp(B, A) >= 0) {
 335                 /* -sign*(X + Y)*a == B - A  (mod |n|) */
 336                 if (!BN_uadd(X, X, Y))
 337                     goto err;
 338                 /*
 339                  * NB: we could use BN_mod_add_quick(X, X, Y, n), but that
 340                  * actually makes the algorithm slower
 341                  */
 342                 if (!BN_usub(B, B, A))
 343                     goto err;
 344             } else {
 345                 /*  sign*(X + Y)*a == A - B  (mod |n|) */
 346                 if (!BN_uadd(Y, Y, X))
 347                     goto err;
 348                 /*
 349                  * as above, BN_mod_add_quick(Y, Y, X, n) would slow things down
 350                  */
 351                 if (!BN_usub(A, A, B))
 352                     goto err;
 353             }
 354         }
 355     } else {
 356         /* general inversion algorithm */
 357
 358         while (!BN_is_zero(B)) {
 359             BIGNUM *tmp;
 360
 361             /*-
 362              *      0 < B < A,
 363              * (*) -sign*X*a  ==  B   (mod |n|),
 364              *      sign*Y*a  ==  A   (mod |n|)
 365              */
 366
 367             /* (D, M) := (A/B, A%B) ... */
 368             if (BN_num_bits(A) == BN_num_bits(B)) {
 369                 if (!BN_one(D))
 370                     goto err;
 371                 if (!BN_sub(M, A, B))
 372                     goto err;
 373             } else if (BN_num_bits(A) == BN_num_bits(B) + 1) {
 374                 /* A/B is 1, 2, or 3 */
 375                 if (!BN_lshift1(T, B))
 376                     goto err;
 377                 if (BN_ucmp(A, T) < 0) {
 378                     /* A < 2*B, so D=1 */
 379                     if (!BN_one(D))
 380                         goto err;
 381                     if (!BN_sub(M, A, B))
 382                         goto err;
 383                 } else {
 384                     /* A >= 2*B, so D=2 or D=3 */
 385                     if (!BN_sub(M, A, T))
 386                         goto err;
 387                     if (!BN_add(D, T, B))
 388                         goto err; /* use D (:= 3*B) as temp */
 389                     if (BN_ucmp(A, D) < 0) {
 390                         /* A < 3*B, so D=2 */
 391                         if (!BN_set_word(D, 2))
 392                             goto err;
 393                         /*
 394                          * M (= A - 2*B) already has the correct value
 395                          */
 396                     } else {
 397                         /* only D=3 remains */
 398                         if (!BN_set_word(D, 3))
 399                             goto err;
 400                         /*
 401                          * currently M = A - 2*B, but we need M = A - 3*B
 402                          */
 403                         if (!BN_sub(M, M, B))
 404                             goto err;
 405                     }
 406                 }
 407             } else {
 408                 if (!BN_div(D, M, A, B, ctx))
 409                     goto err;
 410             }
 411
 412             /*-
 413              * Now
 414              *      A = D*B + M;
 415              * thus we have
 416              * (**)  sign*Y*a  ==  D*B + M   (mod |n|).
 417              */
 418
 419             tmp = A;    /* keep the BIGNUM object, the value does not matter */
 420
 421             /* (A, B) := (B, A mod B) ... */
 422             A = B;
 423             B = M;
 424             /* ... so we have  0 <= B < A  again */
 425
 426             /*-
 427              * Since the former  M  is now  B  and the former  B  is now  A,
 428              * (**) translates into
 429              *       sign*Y*a  ==  D*A + B    (mod |n|),
 430              * i.e.
 431              *       sign*Y*a - D*A  ==  B    (mod |n|).
 432              * Similarly, (*) translates into
 433              *      -sign*X*a  ==  A          (mod |n|).
 434              *
 435              * Thus,
 436              *   sign*Y*a + D*sign*X*a  ==  B  (mod |n|),
 437              * i.e.
 438              *        sign*(Y + D*X)*a  ==  B  (mod |n|).
 439              *
 440              * So if we set  (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at
 441              *      -sign*X*a  ==  B   (mod |n|),
 442              *       sign*Y*a  ==  A   (mod |n|).
 443              * Note that  X  and  Y  stay non-negative all the time.
 444              */
 445
 446             /*
 447              * most of the time D is very small, so we can optimize tmp := D*X+Y
 448              */
 449             if (BN_is_one(D)) {
 450                 if (!BN_add(tmp, X, Y))
 451                     goto err;
 452             } else {
 453                 if (BN_is_word(D, 2)) {
 454                     if (!BN_lshift1(tmp, X))
 455                         goto err;
 456                 } else if (BN_is_word(D, 4)) {
 457                     if (!BN_lshift(tmp, X, 2))
 458                         goto err;
 459                 } else if (D->top == 1) {
 460                     if (!BN_copy(tmp, X))
 461                         goto err;
 462                     if (!BN_mul_word(tmp, D->d[0]))
 463                         goto err;
 464                 } else {
 465                     if (!BN_mul(tmp, D, X, ctx))
 466                         goto err;
 467                 }
 468                 if (!BN_add(tmp, tmp, Y))
 469                     goto err;
 470             }
 471
 472             M = Y;      /* keep the BIGNUM object, the value does not matter */
 473             Y = X;
 474             X = tmp;
 475             sign = -sign;
 476         }
 477     }
 478
 479     /*-
 480      * The while loop (Euclid's algorithm) ends when
 481      *      A == gcd(a,n);
 482      * we have
 483      *       sign*Y*a  ==  A  (mod |n|),
 484      * where  Y  is non-negative.
 485      */
 486
 487     if (sign < 0) {
 488         if (!BN_sub(Y, n, Y))
 489             goto err;
 490     }
 491     /* Now  Y*a  ==  A  (mod |n|).  */
 492
 493     if (BN_is_one(A)) {
 494         /* Y*a == 1  (mod |n|) */
 495         if (!Y->neg && BN_ucmp(Y, n) < 0) {
 496             if (!BN_copy(R, Y))
 497                 goto err;
 498         } else {
 499             if (!BN_nnmod(R, Y, n, ctx))
 500                 goto err;
 501         }
 502     } else {
 503         *pnoinv = 1;
 504         goto err;
 505     }
 506     ret = R;
 507  err:
 508     if ((ret == NULL) && (in == NULL))
 509         BN_free(R);
 510     BN_CTX_end(ctx);
 511     bn_check_top(ret);
 512     return ret;
 513 }
 514
 515 /* solves ax == 1 (mod n) */
 516 BIGNUM *BN_mod_inverse(BIGNUM *in,
 517                        const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
 518 {
 519     BN_CTX *new_ctx = NULL;
 520     BIGNUM *rv;
 521     int noinv = 0;
 522
 523     if (ctx == NULL) {
 524         ctx = new_ctx = BN_CTX_new_ex(NULL);
 525         if (ctx == NULL) {
 526             ERR_raise(ERR_LIB_BN, ERR_R_BN_LIB);
 527             return NULL;
 528         }
 529     }
 530
 531     rv = int_bn_mod_inverse(in, a, n, ctx, &noinv);
 532     if (noinv)
 533         ERR_raise(ERR_LIB_BN, BN_R_NO_INVERSE);
 534     BN_CTX_free(new_ctx);
 535     return rv;
 536 }
 537
 538 /*
 539  * The numbers a and b are coprime if the only positive integer that is a
 540  * divisor of both of them is 1.
 541  * i.e. gcd(a,b) = 1.
 542  *
 543  * Coprimes have the property: b has a multiplicative inverse modulo a
 544  * i.e there is some value x such that bx = 1 (mod a).
 545  *
 546  * Testing the modulo inverse is currently much faster than the constant
 547  * time version of BN_gcd().
 548  */
 549 int BN_are_coprime(BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 550 {
 551     int ret = 0;
 552     BIGNUM *tmp;
 553
 554     BN_CTX_start(ctx);
 555     tmp = BN_CTX_get(ctx);
 556     if (tmp == NULL)
 557         goto end;
 558
 559     ERR_set_mark();
 560     BN_set_flags(a, BN_FLG_CONSTTIME);
 561     ret = (BN_mod_inverse(tmp, a, b, ctx) != NULL);
 562     /* Clear any errors (an error is returned if there is no inverse) */
 563     ERR_pop_to_mark();
 564 end:
 565     BN_CTX_end(ctx);
 566     return ret;
 567 }
 568
 569 /*-
 570  * This function is based on the constant-time GCD work by Bernstein and Yang:
 571  * https://eprint.iacr.org/2019/266
 572  * Generalized fast GCD function to allow even inputs.
 573  * The algorithm first finds the shared powers of 2 between
 574  * the inputs, and removes them, reducing at least one of the
 575  * inputs to an odd value. Then it proceeds to calculate the GCD.
 576  * Before returning the resulting GCD, we take care of adding
 577  * back the powers of two removed at the beginning.
 578  * Note 1: we assume the bit length of both inputs is public information,
 579  * since access to top potentially leaks this information.
 580  */
 581 int BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
 582 {
 583     BIGNUM *g, *temp = NULL;
 584     BN_ULONG pow2_numbits, pow2_numbits_temp, pow2_condition_mask, pow2_flag;
 585     int i, j, top, rlen, glen, m, delta = 1, cond = 0, pow2_shifts, ret = 0;
 586
 587     /* Note 2: zero input corner cases are not constant-time since they are
 588      * handled immediately. An attacker can run an attack under this
 589      * assumption without the need of side-channel information. */
 590     if (BN_is_zero(in_b)) {
 591         ret = BN_copy(r, in_a) != NULL;
 592         r->neg = 0;
 593         return ret;
 594     }
 595     if (BN_is_zero(in_a)) {
 596         ret = BN_copy(r, in_b) != NULL;
 597         r->neg = 0;
 598         return ret;
 599     }
 600
 601     bn_check_top(in_a);
 602     bn_check_top(in_b);
 603
 604     BN_CTX_start(ctx);
 605     temp = BN_CTX_get(ctx);
 606     g = BN_CTX_get(ctx);
 607
 608     /* make r != 0, g != 0 even, so BN_rshift is not a potential nop */
 609     if (g == NULL
 610         || !BN_lshift1(g, in_b)
 611         || !BN_lshift1(r, in_a))
 612         goto err;
 613
 614     /* find shared powers of two, i.e. "shifts" >= 1 */
 615     pow2_flag = 1;
 616     pow2_shifts = 0;
 617     pow2_numbits = 0;
 618     for (i = 0; i < r->dmax && i < g->dmax; i++) {
 619         pow2_numbits_temp = r->d[i] | g->d[i];
 620         pow2_condition_mask = constant_time_is_zero_bn(pow2_flag);
 621         pow2_flag &= constant_time_is_zero_bn(pow2_numbits_temp);
 622         pow2_shifts += pow2_flag;
 623         pow2_numbits = constant_time_select_bn(pow2_condition_mask,
 624                                                pow2_numbits, pow2_numbits_temp);
 625     }
 626     pow2_numbits = ~pow2_numbits;
 627     pow2_shifts *= BN_BITS2;
 628     pow2_flag = 1;
 629     for (j = 0; j < BN_BITS2; j++) {
 630         pow2_flag &= pow2_numbits;
 631         pow2_shifts += pow2_flag;
 632         pow2_numbits >>= 1;
 633     }
 634
 635     /* subtract shared powers of two; shifts >= 1 */
 636     if (!BN_rshift(r, r, pow2_shifts)
 637         || !BN_rshift(g, g, pow2_shifts))
 638         goto err;
 639
 640     /* expand to biggest nword, with room for a possible extra word */
 641     top = 1 + ((r->top >= g->top) ? r->top : g->top);
 642     if (bn_wexpand(r, top) == NULL
 643         || bn_wexpand(g, top) == NULL
 644         || bn_wexpand(temp, top) == NULL)
 645         goto err;
 646
 647     /* re arrange inputs s.t. r is odd */
 648     BN_consttime_swap((~r->d[0]) & 1, r, g, top);
 649
 650     /* compute the number of iterations */
 651     rlen = BN_num_bits(r);
 652     glen = BN_num_bits(g);
 653     m = 4 + 3 * ((rlen >= glen) ? rlen : glen);
 654
 655     for (i = 0; i < m; i++) {
 656         /* conditionally flip signs if delta is positive and g is odd */
 657         cond = ((unsigned int)-delta >> (8 * sizeof(delta) - 1)) & g->d[0] & 1
 658             /* make sure g->top > 0 (i.e. if top == 0 then g == 0 always) */
 659             & (~((unsigned int)(g->top - 1) >> (sizeof(g->top) * 8 - 1)));
 660         delta = (-cond & -delta) | ((cond - 1) & delta);
 661         r->neg ^= cond;
 662         /* swap */
 663         BN_consttime_swap(cond, r, g, top);
 664
 665         /* elimination step */
 666         delta++;
 667         if (!BN_add(temp, g, r))
 668             goto err;
 669         BN_consttime_swap(g->d[0] & 1 /* g is odd */
 670                 /* make sure g->top > 0 (i.e. if top == 0 then g == 0 always) */
 671                 & (~((unsigned int)(g->top - 1) >> (sizeof(g->top) * 8 - 1))),
 672                 g, temp, top);
 673         if (!BN_rshift1(g, g))
 674             goto err;
 675     }
 676
 677     /* remove possible negative sign */
 678     r->neg = 0;
 679     /* add powers of 2 removed, then correct the artificial shift */
 680     if (!BN_lshift(r, r, pow2_shifts)
 681         || !BN_rshift1(r, r))
 682         goto err;
 683
 684     ret = 1;
 685
 686  err:
 687     BN_CTX_end(ctx);
 688     bn_check_top(r);
 689     return ret;
 690 }