crypto/bn/bn_gf2m.c

   1 /*
   2  * Copyright 2002-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
   4  *
   5  * Licensed under the OpenSSL license (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  */
  10
  11 #include <assert.h>
  12 #include <limits.h>
  13 #include <stdio.h>
  14 #include "internal/cryptlib.h"
  15 #include "bn_lcl.h"
  16
  17 #ifndef OPENSSL_NO_EC2M
  18
  19 /*
  20  * Maximum number of iterations before BN_GF2m_mod_solve_quad_arr should
  21  * fail.
  22  */
  23 # define MAX_ITERATIONS 50
  24
  25 static const BN_ULONG SQR_tb[16] = { 0, 1, 4, 5, 16, 17, 20, 21,
  26     64, 65, 68, 69, 80, 81, 84, 85
  27 };
  28
  29 /* Platform-specific macros to accelerate squaring. */
  30 # if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
  31 #  define SQR1(w) \
  32     SQR_tb[(w) >> 60 & 0xF] << 56 | SQR_tb[(w) >> 56 & 0xF] << 48 | \
  33     SQR_tb[(w) >> 52 & 0xF] << 40 | SQR_tb[(w) >> 48 & 0xF] << 32 | \
  34     SQR_tb[(w) >> 44 & 0xF] << 24 | SQR_tb[(w) >> 40 & 0xF] << 16 | \
  35     SQR_tb[(w) >> 36 & 0xF] <<  8 | SQR_tb[(w) >> 32 & 0xF]
  36 #  define SQR0(w) \
  37     SQR_tb[(w) >> 28 & 0xF] << 56 | SQR_tb[(w) >> 24 & 0xF] << 48 | \
  38     SQR_tb[(w) >> 20 & 0xF] << 40 | SQR_tb[(w) >> 16 & 0xF] << 32 | \
  39     SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >>  8 & 0xF] << 16 | \
  40     SQR_tb[(w) >>  4 & 0xF] <<  8 | SQR_tb[(w)       & 0xF]
  41 # endif
  42 # ifdef THIRTY_TWO_BIT
  43 #  define SQR1(w) \
  44     SQR_tb[(w) >> 28 & 0xF] << 24 | SQR_tb[(w) >> 24 & 0xF] << 16 | \
  45     SQR_tb[(w) >> 20 & 0xF] <<  8 | SQR_tb[(w) >> 16 & 0xF]
  46 #  define SQR0(w) \
  47     SQR_tb[(w) >> 12 & 0xF] << 24 | SQR_tb[(w) >>  8 & 0xF] << 16 | \
  48     SQR_tb[(w) >>  4 & 0xF] <<  8 | SQR_tb[(w)       & 0xF]
  49 # endif
  50
  51 # if !defined(OPENSSL_BN_ASM_GF2m)
  52 /*
  53  * Product of two polynomials a, b each with degree < BN_BITS2 - 1, result is
  54  * a polynomial r with degree < 2 * BN_BITS - 1 The caller MUST ensure that
  55  * the variables have the right amount of space allocated.
  56  */
  57 #  ifdef THIRTY_TWO_BIT
  58 static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a,
  59                             const BN_ULONG b)
  60 {
  61     register BN_ULONG h, l, s;
  62     BN_ULONG tab[8], top2b = a >> 30;
  63     register BN_ULONG a1, a2, a4;
  64
  65     a1 = a & (0x3FFFFFFF);
  66     a2 = a1 << 1;
  67     a4 = a2 << 1;
  68
  69     tab[0] = 0;
  70     tab[1] = a1;
  71     tab[2] = a2;
  72     tab[3] = a1 ^ a2;
  73     tab[4] = a4;
  74     tab[5] = a1 ^ a4;
  75     tab[6] = a2 ^ a4;
  76     tab[7] = a1 ^ a2 ^ a4;
  77
  78     s = tab[b & 0x7];
  79     l = s;
  80     s = tab[b >> 3 & 0x7];
  81     l ^= s << 3;
  82     h = s >> 29;
  83     s = tab[b >> 6 & 0x7];
  84     l ^= s << 6;
  85     h ^= s >> 26;
  86     s = tab[b >> 9 & 0x7];
  87     l ^= s << 9;
  88     h ^= s >> 23;
  89     s = tab[b >> 12 & 0x7];
  90     l ^= s << 12;
  91     h ^= s >> 20;
  92     s = tab[b >> 15 & 0x7];
  93     l ^= s << 15;
  94     h ^= s >> 17;
  95     s = tab[b >> 18 & 0x7];
  96     l ^= s << 18;
  97     h ^= s >> 14;
  98     s = tab[b >> 21 & 0x7];
  99     l ^= s << 21;
 100     h ^= s >> 11;
 101     s = tab[b >> 24 & 0x7];
 102     l ^= s << 24;
 103     h ^= s >> 8;
 104     s = tab[b >> 27 & 0x7];
 105     l ^= s << 27;
 106     h ^= s >> 5;
 107     s = tab[b >> 30];
 108     l ^= s << 30;
 109     h ^= s >> 2;
 110
 111     /* compensate for the top two bits of a */
 112
 113     if (top2b & 01) {
 114         l ^= b << 30;
 115         h ^= b >> 2;
 116     }
 117     if (top2b & 02) {
 118         l ^= b << 31;
 119         h ^= b >> 1;
 120     }
 121
 122     *r1 = h;
 123     *r0 = l;
 124 }
 125 #  endif
 126 #  if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
 127 static void bn_GF2m_mul_1x1(BN_ULONG *r1, BN_ULONG *r0, const BN_ULONG a,
 128                             const BN_ULONG b)
 129 {
 130     register BN_ULONG h, l, s;
 131     BN_ULONG tab[16], top3b = a >> 61;
 132     register BN_ULONG a1, a2, a4, a8;
 133
 134     a1 = a & (0x1FFFFFFFFFFFFFFFULL);
 135     a2 = a1 << 1;
 136     a4 = a2 << 1;
 137     a8 = a4 << 1;
 138
 139     tab[0] = 0;
 140     tab[1] = a1;
 141     tab[2] = a2;
 142     tab[3] = a1 ^ a2;
 143     tab[4] = a4;
 144     tab[5] = a1 ^ a4;
 145     tab[6] = a2 ^ a4;
 146     tab[7] = a1 ^ a2 ^ a4;
 147     tab[8] = a8;
 148     tab[9] = a1 ^ a8;
 149     tab[10] = a2 ^ a8;
 150     tab[11] = a1 ^ a2 ^ a8;
 151     tab[12] = a4 ^ a8;
 152     tab[13] = a1 ^ a4 ^ a8;
 153     tab[14] = a2 ^ a4 ^ a8;
 154     tab[15] = a1 ^ a2 ^ a4 ^ a8;
 155
 156     s = tab[b & 0xF];
 157     l = s;
 158     s = tab[b >> 4 & 0xF];
 159     l ^= s << 4;
 160     h = s >> 60;
 161     s = tab[b >> 8 & 0xF];
 162     l ^= s << 8;
 163     h ^= s >> 56;
 164     s = tab[b >> 12 & 0xF];
 165     l ^= s << 12;
 166     h ^= s >> 52;
 167     s = tab[b >> 16 & 0xF];
 168     l ^= s << 16;
 169     h ^= s >> 48;
 170     s = tab[b >> 20 & 0xF];
 171     l ^= s << 20;
 172     h ^= s >> 44;
 173     s = tab[b >> 24 & 0xF];
 174     l ^= s << 24;
 175     h ^= s >> 40;
 176     s = tab[b >> 28 & 0xF];
 177     l ^= s << 28;
 178     h ^= s >> 36;
 179     s = tab[b >> 32 & 0xF];
 180     l ^= s << 32;
 181     h ^= s >> 32;
 182     s = tab[b >> 36 & 0xF];
 183     l ^= s << 36;
 184     h ^= s >> 28;
 185     s = tab[b >> 40 & 0xF];
 186     l ^= s << 40;
 187     h ^= s >> 24;
 188     s = tab[b >> 44 & 0xF];
 189     l ^= s << 44;
 190     h ^= s >> 20;
 191     s = tab[b >> 48 & 0xF];
 192     l ^= s << 48;
 193     h ^= s >> 16;
 194     s = tab[b >> 52 & 0xF];
 195     l ^= s << 52;
 196     h ^= s >> 12;
 197     s = tab[b >> 56 & 0xF];
 198     l ^= s << 56;
 199     h ^= s >> 8;
 200     s = tab[b >> 60];
 201     l ^= s << 60;
 202     h ^= s >> 4;
 203
 204     /* compensate for the top three bits of a */
 205
 206     if (top3b & 01) {
 207         l ^= b << 61;
 208         h ^= b >> 3;
 209     }
 210     if (top3b & 02) {
 211         l ^= b << 62;
 212         h ^= b >> 2;
 213     }
 214     if (top3b & 04) {
 215         l ^= b << 63;
 216         h ^= b >> 1;
 217     }
 218
 219     *r1 = h;
 220     *r0 = l;
 221 }
 222 #  endif
 223
 224 /*
 225  * Product of two polynomials a, b each with degree < 2 * BN_BITS2 - 1,
 226  * result is a polynomial r with degree < 4 * BN_BITS2 - 1 The caller MUST
 227  * ensure that the variables have the right amount of space allocated.
 228  */
 229 static void bn_GF2m_mul_2x2(BN_ULONG *r, const BN_ULONG a1, const BN_ULONG a0,
 230                             const BN_ULONG b1, const BN_ULONG b0)
 231 {
 232     BN_ULONG m1, m0;
 233     /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
 234     bn_GF2m_mul_1x1(r + 3, r + 2, a1, b1);
 235     bn_GF2m_mul_1x1(r + 1, r, a0, b0);
 236     bn_GF2m_mul_1x1(&m1, &m0, a0 ^ a1, b0 ^ b1);
 237     /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
 238     r[2] ^= m1 ^ r[1] ^ r[3];   /* h0 ^= m1 ^ l1 ^ h1; */
 239     r[1] = r[3] ^ r[2] ^ r[0] ^ m1 ^ m0; /* l1 ^= l0 ^ h0 ^ m0; */
 240 }
 241 # else
 242 void bn_GF2m_mul_2x2(BN_ULONG *r, BN_ULONG a1, BN_ULONG a0, BN_ULONG b1,
 243                      BN_ULONG b0);
 244 # endif
 245
 246 /*
 247  * Add polynomials a and b and store result in r; r could be a or b, a and b
 248  * could be equal; r is the bitwise XOR of a and b.
 249  */
 250 int BN_GF2m_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
 251 {
 252     int i;
 253     const BIGNUM *at, *bt;
 254
 255     bn_check_top(a);
 256     bn_check_top(b);
 257
 258     if (a->top < b->top) {
 259         at = b;
 260         bt = a;
 261     } else {
 262         at = a;
 263         bt = b;
 264     }
 265
 266     if (bn_wexpand(r, at->top) == NULL)
 267         return 0;
 268
 269     for (i = 0; i < bt->top; i++) {
 270         r->d[i] = at->d[i] ^ bt->d[i];
 271     }
 272     for (; i < at->top; i++) {
 273         r->d[i] = at->d[i];
 274     }
 275
 276     r->top = at->top;
 277     bn_correct_top(r);
 278
 279     return 1;
 280 }
 281
 282 /*-
 283  * Some functions allow for representation of the irreducible polynomials
 284  * as an int[], say p.  The irreducible f(t) is then of the form:
 285  *     t^p[0] + t^p[1] + ... + t^p[k]
 286  * where m = p[0] > p[1] > ... > p[k] = 0.
 287  */
 288
 289 /* Performs modular reduction of a and store result in r.  r could be a. */
 290 int BN_GF2m_mod_arr(BIGNUM *r, const BIGNUM *a, const int p[])
 291 {
 292     int j, k;
 293     int n, dN, d0, d1;
 294     BN_ULONG zz, *z;
 295
 296     bn_check_top(a);
 297
 298     if (!p[0]) {
 299         /* reduction mod 1 => return 0 */
 300         BN_zero(r);
 301         return 1;
 302     }
 303
 304     /*
 305      * Since the algorithm does reduction in the r value, if a != r, copy the
 306      * contents of a into r so we can do reduction in r.
 307      */
 308     if (a != r) {
 309         if (!bn_wexpand(r, a->top))
 310             return 0;
 311         for (j = 0; j < a->top; j++) {
 312             r->d[j] = a->d[j];
 313         }
 314         r->top = a->top;
 315     }
 316     z = r->d;
 317
 318     /* start reduction */
 319     dN = p[0] / BN_BITS2;
 320     for (j = r->top - 1; j > dN;) {
 321         zz = z[j];
 322         if (z[j] == 0) {
 323             j--;
 324             continue;
 325         }
 326         z[j] = 0;
 327
 328         for (k = 1; p[k] != 0; k++) {
 329             /* reducing component t^p[k] */
 330             n = p[0] - p[k];
 331             d0 = n % BN_BITS2;
 332             d1 = BN_BITS2 - d0;
 333             n /= BN_BITS2;
 334             z[j - n] ^= (zz >> d0);
 335             if (d0)
 336                 z[j - n - 1] ^= (zz << d1);
 337         }
 338
 339         /* reducing component t^0 */
 340         n = dN;
 341         d0 = p[0] % BN_BITS2;
 342         d1 = BN_BITS2 - d0;
 343         z[j - n] ^= (zz >> d0);
 344         if (d0)
 345             z[j - n - 1] ^= (zz << d1);
 346     }
 347
 348     /* final round of reduction */
 349     while (j == dN) {
 350
 351         d0 = p[0] % BN_BITS2;
 352         zz = z[dN] >> d0;
 353         if (zz == 0)
 354             break;
 355         d1 = BN_BITS2 - d0;
 356
 357         /* clear up the top d1 bits */
 358         if (d0)
 359             z[dN] = (z[dN] << d1) >> d1;
 360         else
 361             z[dN] = 0;
 362         z[0] ^= zz;             /* reduction t^0 component */
 363
 364         for (k = 1; p[k] != 0; k++) {
 365             BN_ULONG tmp_ulong;
 366
 367             /* reducing component t^p[k] */
 368             n = p[k] / BN_BITS2;
 369             d0 = p[k] % BN_BITS2;
 370             d1 = BN_BITS2 - d0;
 371             z[n] ^= (zz << d0);
 372             if (d0 && (tmp_ulong = zz >> d1))
 373                 z[n + 1] ^= tmp_ulong;
 374         }
 375
 376     }
 377
 378     bn_correct_top(r);
 379     return 1;
 380 }
 381
 382 /*
 383  * Performs modular reduction of a by p and store result in r.  r could be a.
 384  * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper
 385  * function is only provided for convenience; for best performance, use the
 386  * BN_GF2m_mod_arr function.
 387  */
 388 int BN_GF2m_mod(BIGNUM *r, const BIGNUM *a, const BIGNUM *p)
 389 {
 390     int ret = 0;
 391     int arr[6];
 392     bn_check_top(a);
 393     bn_check_top(p);
 394     ret = BN_GF2m_poly2arr(p, arr, OSSL_NELEM(arr));
 395     if (!ret || ret > (int)OSSL_NELEM(arr)) {
 396         BNerr(BN_F_BN_GF2M_MOD, BN_R_INVALID_LENGTH);
 397         return 0;
 398     }
 399     ret = BN_GF2m_mod_arr(r, a, arr);
 400     bn_check_top(r);
 401     return ret;
 402 }
 403
 404 /*
 405  * Compute the product of two polynomials a and b, reduce modulo p, and store
 406  * the result in r.  r could be a or b; a could be b.
 407  */
 408 int BN_GF2m_mod_mul_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 409                         const int p[], BN_CTX *ctx)
 410 {
 411     int zlen, i, j, k, ret = 0;
 412     BIGNUM *s;
 413     BN_ULONG x1, x0, y1, y0, zz[4];
 414
 415     bn_check_top(a);
 416     bn_check_top(b);
 417
 418     if (a == b) {
 419         return BN_GF2m_mod_sqr_arr(r, a, p, ctx);
 420     }
 421
 422     BN_CTX_start(ctx);
 423     if ((s = BN_CTX_get(ctx)) == NULL)
 424         goto err;
 425
 426     zlen = a->top + b->top + 4;
 427     if (!bn_wexpand(s, zlen))
 428         goto err;
 429     s->top = zlen;
 430
 431     for (i = 0; i < zlen; i++)
 432         s->d[i] = 0;
 433
 434     for (j = 0; j < b->top; j += 2) {
 435         y0 = b->d[j];
 436         y1 = ((j + 1) == b->top) ? 0 : b->d[j + 1];
 437         for (i = 0; i < a->top; i += 2) {
 438             x0 = a->d[i];
 439             x1 = ((i + 1) == a->top) ? 0 : a->d[i + 1];
 440             bn_GF2m_mul_2x2(zz, x1, x0, y1, y0);
 441             for (k = 0; k < 4; k++)
 442                 s->d[i + j + k] ^= zz[k];
 443         }
 444     }
 445
 446     bn_correct_top(s);
 447     if (BN_GF2m_mod_arr(r, s, p))
 448         ret = 1;
 449     bn_check_top(r);
 450
 451  err:
 452     BN_CTX_end(ctx);
 453     return ret;
 454 }
 455
 456 /*
 457  * Compute the product of two polynomials a and b, reduce modulo p, and store
 458  * the result in r.  r could be a or b; a could equal b. This function calls
 459  * down to the BN_GF2m_mod_mul_arr implementation; this wrapper function is
 460  * only provided for convenience; for best performance, use the
 461  * BN_GF2m_mod_mul_arr function.
 462  */
 463 int BN_GF2m_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 464                     const BIGNUM *p, BN_CTX *ctx)
 465 {
 466     int ret = 0;
 467     const int max = BN_num_bits(p) + 1;
 468     int *arr = NULL;
 469     bn_check_top(a);
 470     bn_check_top(b);
 471     bn_check_top(p);
 472     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
 473         goto err;
 474     ret = BN_GF2m_poly2arr(p, arr, max);
 475     if (!ret || ret > max) {
 476         BNerr(BN_F_BN_GF2M_MOD_MUL, BN_R_INVALID_LENGTH);
 477         goto err;
 478     }
 479     ret = BN_GF2m_mod_mul_arr(r, a, b, arr, ctx);
 480     bn_check_top(r);
 481  err:
 482     OPENSSL_free(arr);
 483     return ret;
 484 }
 485
 486 /* Square a, reduce the result mod p, and store it in a.  r could be a. */
 487 int BN_GF2m_mod_sqr_arr(BIGNUM *r, const BIGNUM *a, const int p[],
 488                         BN_CTX *ctx)
 489 {
 490     int i, ret = 0;
 491     BIGNUM *s;
 492
 493     bn_check_top(a);
 494     BN_CTX_start(ctx);
 495     if ((s = BN_CTX_get(ctx)) == NULL)
 496         goto err;
 497     if (!bn_wexpand(s, 2 * a->top))
 498         goto err;
 499
 500     for (i = a->top - 1; i >= 0; i--) {
 501         s->d[2 * i + 1] = SQR1(a->d[i]);
 502         s->d[2 * i] = SQR0(a->d[i]);
 503     }
 504
 505     s->top = 2 * a->top;
 506     bn_correct_top(s);
 507     if (!BN_GF2m_mod_arr(r, s, p))
 508         goto err;
 509     bn_check_top(r);
 510     ret = 1;
 511  err:
 512     BN_CTX_end(ctx);
 513     return ret;
 514 }
 515
 516 /*
 517  * Square a, reduce the result mod p, and store it in a.  r could be a. This
 518  * function calls down to the BN_GF2m_mod_sqr_arr implementation; this
 519  * wrapper function is only provided for convenience; for best performance,
 520  * use the BN_GF2m_mod_sqr_arr function.
 521  */
 522 int BN_GF2m_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 523 {
 524     int ret = 0;
 525     const int max = BN_num_bits(p) + 1;
 526     int *arr = NULL;
 527
 528     bn_check_top(a);
 529     bn_check_top(p);
 530     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
 531         goto err;
 532     ret = BN_GF2m_poly2arr(p, arr, max);
 533     if (!ret || ret > max) {
 534         BNerr(BN_F_BN_GF2M_MOD_SQR, BN_R_INVALID_LENGTH);
 535         goto err;
 536     }
 537     ret = BN_GF2m_mod_sqr_arr(r, a, arr, ctx);
 538     bn_check_top(r);
 539  err:
 540     OPENSSL_free(arr);
 541     return ret;
 542 }
 543
 544 /*
 545  * Invert a, reduce modulo p, and store the result in r. r could be a. Uses
 546  * Modified Almost Inverse Algorithm (Algorithm 10) from Hankerson, D.,
 547  * Hernandez, J.L., and Menezes, A.  "Software Implementation of Elliptic
 548  * Curve Cryptography Over Binary Fields".
 549  */
 550 int BN_GF2m_mod_inv(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 551 {
 552     BIGNUM *b, *c = NULL, *u = NULL, *v = NULL, *tmp;
 553     int ret = 0;
 554
 555     bn_check_top(a);
 556     bn_check_top(p);
 557
 558     BN_CTX_start(ctx);
 559
 560     if ((b = BN_CTX_get(ctx)) == NULL)
 561         goto err;
 562     if ((c = BN_CTX_get(ctx)) == NULL)
 563         goto err;
 564     if ((u = BN_CTX_get(ctx)) == NULL)
 565         goto err;
 566     if ((v = BN_CTX_get(ctx)) == NULL)
 567         goto err;
 568
 569     if (!BN_GF2m_mod(u, a, p))
 570         goto err;
 571     if (BN_is_zero(u))
 572         goto err;
 573
 574     if (!BN_copy(v, p))
 575         goto err;
 576 # if 0
 577     if (!BN_one(b))
 578         goto err;
 579
 580     while (1) {
 581         while (!BN_is_odd(u)) {
 582             if (BN_is_zero(u))
 583                 goto err;
 584             if (!BN_rshift1(u, u))
 585                 goto err;
 586             if (BN_is_odd(b)) {
 587                 if (!BN_GF2m_add(b, b, p))
 588                     goto err;
 589             }
 590             if (!BN_rshift1(b, b))
 591                 goto err;
 592         }
 593
 594         if (BN_abs_is_word(u, 1))
 595             break;
 596
 597         if (BN_num_bits(u) < BN_num_bits(v)) {
 598             tmp = u;
 599             u = v;
 600             v = tmp;
 601             tmp = b;
 602             b = c;
 603             c = tmp;
 604         }
 605
 606         if (!BN_GF2m_add(u, u, v))
 607             goto err;
 608         if (!BN_GF2m_add(b, b, c))
 609             goto err;
 610     }
 611 # else
 612     {
 613         int i;
 614         int ubits = BN_num_bits(u);
 615         int vbits = BN_num_bits(v); /* v is copy of p */
 616         int top = p->top;
 617         BN_ULONG *udp, *bdp, *vdp, *cdp;
 618
 619         if (!bn_wexpand(u, top))
 620             goto err;
 621         udp = u->d;
 622         for (i = u->top; i < top; i++)
 623             udp[i] = 0;
 624         u->top = top;
 625         if (!bn_wexpand(b, top))
 626           goto err;
 627         bdp = b->d;
 628         bdp[0] = 1;
 629         for (i = 1; i < top; i++)
 630             bdp[i] = 0;
 631         b->top = top;
 632         if (!bn_wexpand(c, top))
 633           goto err;
 634         cdp = c->d;
 635         for (i = 0; i < top; i++)
 636             cdp[i] = 0;
 637         c->top = top;
 638         vdp = v->d;             /* It pays off to "cache" *->d pointers,
 639                                  * because it allows optimizer to be more
 640                                  * aggressive. But we don't have to "cache"
 641                                  * p->d, because *p is declared 'const'... */
 642         while (1) {
 643             while (ubits && !(udp[0] & 1)) {
 644                 BN_ULONG u0, u1, b0, b1, mask;
 645
 646                 u0 = udp[0];
 647                 b0 = bdp[0];
 648                 mask = (BN_ULONG)0 - (b0 & 1);
 649                 b0 ^= p->d[0] & mask;
 650                 for (i = 0; i < top - 1; i++) {
 651                     u1 = udp[i + 1];
 652                     udp[i] = ((u0 >> 1) | (u1 << (BN_BITS2 - 1))) & BN_MASK2;
 653                     u0 = u1;
 654                     b1 = bdp[i + 1] ^ (p->d[i + 1] & mask);
 655                     bdp[i] = ((b0 >> 1) | (b1 << (BN_BITS2 - 1))) & BN_MASK2;
 656                     b0 = b1;
 657                 }
 658                 udp[i] = u0 >> 1;
 659                 bdp[i] = b0 >> 1;
 660                 ubits--;
 661             }
 662
 663             if (ubits <= BN_BITS2) {
 664                 if (udp[0] == 0) /* poly was reducible */
 665                     goto err;
 666                 if (udp[0] == 1)
 667                     break;
 668             }
 669
 670             if (ubits < vbits) {
 671                 i = ubits;
 672                 ubits = vbits;
 673                 vbits = i;
 674                 tmp = u;
 675                 u = v;
 676                 v = tmp;
 677                 tmp = b;
 678                 b = c;
 679                 c = tmp;
 680                 udp = vdp;
 681                 vdp = v->d;
 682                 bdp = cdp;
 683                 cdp = c->d;
 684             }
 685             for (i = 0; i < top; i++) {
 686                 udp[i] ^= vdp[i];
 687                 bdp[i] ^= cdp[i];
 688             }
 689             if (ubits == vbits) {
 690                 BN_ULONG ul;
 691                 int utop = (ubits - 1) / BN_BITS2;
 692
 693                 while ((ul = udp[utop]) == 0 && utop)
 694                     utop--;
 695                 ubits = utop * BN_BITS2 + BN_num_bits_word(ul);
 696             }
 697         }
 698         bn_correct_top(b);
 699     }
 700 # endif
 701
 702     if (!BN_copy(r, b))
 703         goto err;
 704     bn_check_top(r);
 705     ret = 1;
 706
 707  err:
 708 # ifdef BN_DEBUG                /* BN_CTX_end would complain about the
 709                                  * expanded form */
 710     bn_correct_top(c);
 711     bn_correct_top(u);
 712     bn_correct_top(v);
 713 # endif
 714     BN_CTX_end(ctx);
 715     return ret;
 716 }
 717
 718 /*
 719  * Invert xx, reduce modulo p, and store the result in r. r could be xx.
 720  * This function calls down to the BN_GF2m_mod_inv implementation; this
 721  * wrapper function is only provided for convenience; for best performance,
 722  * use the BN_GF2m_mod_inv function.
 723  */
 724 int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[],
 725                         BN_CTX *ctx)
 726 {
 727     BIGNUM *field;
 728     int ret = 0;
 729
 730     bn_check_top(xx);
 731     BN_CTX_start(ctx);
 732     if ((field = BN_CTX_get(ctx)) == NULL)
 733         goto err;
 734     if (!BN_GF2m_arr2poly(p, field))
 735         goto err;
 736
 737     ret = BN_GF2m_mod_inv(r, xx, field, ctx);
 738     bn_check_top(r);
 739
 740  err:
 741     BN_CTX_end(ctx);
 742     return ret;
 743 }
 744
 745 # ifndef OPENSSL_SUN_GF2M_DIV
 746 /*
 747  * Divide y by x, reduce modulo p, and store the result in r. r could be x
 748  * or y, x could equal y.
 749  */
 750 int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x,
 751                     const BIGNUM *p, BN_CTX *ctx)
 752 {
 753     BIGNUM *xinv = NULL;
 754     int ret = 0;
 755
 756     bn_check_top(y);
 757     bn_check_top(x);
 758     bn_check_top(p);
 759
 760     BN_CTX_start(ctx);
 761     xinv = BN_CTX_get(ctx);
 762     if (xinv == NULL)
 763         goto err;
 764
 765     if (!BN_GF2m_mod_inv(xinv, x, p, ctx))
 766         goto err;
 767     if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx))
 768         goto err;
 769     bn_check_top(r);
 770     ret = 1;
 771
 772  err:
 773     BN_CTX_end(ctx);
 774     return ret;
 775 }
 776 # else
 777 /*
 778  * Divide y by x, reduce modulo p, and store the result in r. r could be x
 779  * or y, x could equal y. Uses algorithm Modular_Division_GF(2^m) from
 780  * Chang-Shantz, S.  "From Euclid's GCD to Montgomery Multiplication to the
 781  * Great Divide".
 782  */
 783 int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x,
 784                     const BIGNUM *p, BN_CTX *ctx)
 785 {
 786     BIGNUM *a, *b, *u, *v;
 787     int ret = 0;
 788
 789     bn_check_top(y);
 790     bn_check_top(x);
 791     bn_check_top(p);
 792
 793     BN_CTX_start(ctx);
 794
 795     a = BN_CTX_get(ctx);
 796     b = BN_CTX_get(ctx);
 797     u = BN_CTX_get(ctx);
 798     v = BN_CTX_get(ctx);
 799     if (v == NULL)
 800         goto err;
 801
 802     /* reduce x and y mod p */
 803     if (!BN_GF2m_mod(u, y, p))
 804         goto err;
 805     if (!BN_GF2m_mod(a, x, p))
 806         goto err;
 807     if (!BN_copy(b, p))
 808         goto err;
 809
 810     while (!BN_is_odd(a)) {
 811         if (!BN_rshift1(a, a))
 812             goto err;
 813         if (BN_is_odd(u))
 814             if (!BN_GF2m_add(u, u, p))
 815                 goto err;
 816         if (!BN_rshift1(u, u))
 817             goto err;
 818     }
 819
 820     do {
 821         if (BN_GF2m_cmp(b, a) > 0) {
 822             if (!BN_GF2m_add(b, b, a))
 823                 goto err;
 824             if (!BN_GF2m_add(v, v, u))
 825                 goto err;
 826             do {
 827                 if (!BN_rshift1(b, b))
 828                     goto err;
 829                 if (BN_is_odd(v))
 830                     if (!BN_GF2m_add(v, v, p))
 831                         goto err;
 832                 if (!BN_rshift1(v, v))
 833                     goto err;
 834             } while (!BN_is_odd(b));
 835         } else if (BN_abs_is_word(a, 1))
 836             break;
 837         else {
 838             if (!BN_GF2m_add(a, a, b))
 839                 goto err;
 840             if (!BN_GF2m_add(u, u, v))
 841                 goto err;
 842             do {
 843                 if (!BN_rshift1(a, a))
 844                     goto err;
 845                 if (BN_is_odd(u))
 846                     if (!BN_GF2m_add(u, u, p))
 847                         goto err;
 848                 if (!BN_rshift1(u, u))
 849                     goto err;
 850             } while (!BN_is_odd(a));
 851         }
 852     } while (1);
 853
 854     if (!BN_copy(r, u))
 855         goto err;
 856     bn_check_top(r);
 857     ret = 1;
 858
 859  err:
 860     BN_CTX_end(ctx);
 861     return ret;
 862 }
 863 # endif
 864
 865 /*
 866  * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx
 867  * * or yy, xx could equal yy. This function calls down to the
 868  * BN_GF2m_mod_div implementation; this wrapper function is only provided for
 869  * convenience; for best performance, use the BN_GF2m_mod_div function.
 870  */
 871 int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx,
 872                         const int p[], BN_CTX *ctx)
 873 {
 874     BIGNUM *field;
 875     int ret = 0;
 876
 877     bn_check_top(yy);
 878     bn_check_top(xx);
 879
 880     BN_CTX_start(ctx);
 881     if ((field = BN_CTX_get(ctx)) == NULL)
 882         goto err;
 883     if (!BN_GF2m_arr2poly(p, field))
 884         goto err;
 885
 886     ret = BN_GF2m_mod_div(r, yy, xx, field, ctx);
 887     bn_check_top(r);
 888
 889  err:
 890     BN_CTX_end(ctx);
 891     return ret;
 892 }
 893
 894 /*
 895  * Compute the bth power of a, reduce modulo p, and store the result in r.  r
 896  * could be a. Uses simple square-and-multiply algorithm A.5.1 from IEEE
 897  * P1363.
 898  */
 899 int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 900                         const int p[], BN_CTX *ctx)
 901 {
 902     int ret = 0, i, n;
 903     BIGNUM *u;
 904
 905     bn_check_top(a);
 906     bn_check_top(b);
 907
 908     if (BN_is_zero(b))
 909         return (BN_one(r));
 910
 911     if (BN_abs_is_word(b, 1))
 912         return (BN_copy(r, a) != NULL);
 913
 914     BN_CTX_start(ctx);
 915     if ((u = BN_CTX_get(ctx)) == NULL)
 916         goto err;
 917
 918     if (!BN_GF2m_mod_arr(u, a, p))
 919         goto err;
 920
 921     n = BN_num_bits(b) - 1;
 922     for (i = n - 1; i >= 0; i--) {
 923         if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx))
 924             goto err;
 925         if (BN_is_bit_set(b, i)) {
 926             if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx))
 927                 goto err;
 928         }
 929     }
 930     if (!BN_copy(r, u))
 931         goto err;
 932     bn_check_top(r);
 933     ret = 1;
 934  err:
 935     BN_CTX_end(ctx);
 936     return ret;
 937 }
 938
 939 /*
 940  * Compute the bth power of a, reduce modulo p, and store the result in r.  r
 941  * could be a. This function calls down to the BN_GF2m_mod_exp_arr
 942  * implementation; this wrapper function is only provided for convenience;
 943  * for best performance, use the BN_GF2m_mod_exp_arr function.
 944  */
 945 int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
 946                     const BIGNUM *p, BN_CTX *ctx)
 947 {
 948     int ret = 0;
 949     const int max = BN_num_bits(p) + 1;
 950     int *arr = NULL;
 951     bn_check_top(a);
 952     bn_check_top(b);
 953     bn_check_top(p);
 954     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
 955         goto err;
 956     ret = BN_GF2m_poly2arr(p, arr, max);
 957     if (!ret || ret > max) {
 958         BNerr(BN_F_BN_GF2M_MOD_EXP, BN_R_INVALID_LENGTH);
 959         goto err;
 960     }
 961     ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx);
 962     bn_check_top(r);
 963  err:
 964     OPENSSL_free(arr);
 965     return ret;
 966 }
 967
 968 /*
 969  * Compute the square root of a, reduce modulo p, and store the result in r.
 970  * r could be a. Uses exponentiation as in algorithm A.4.1 from IEEE P1363.
 971  */
 972 int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[],
 973                          BN_CTX *ctx)
 974 {
 975     int ret = 0;
 976     BIGNUM *u;
 977
 978     bn_check_top(a);
 979
 980     if (!p[0]) {
 981         /* reduction mod 1 => return 0 */
 982         BN_zero(r);
 983         return 1;
 984     }
 985
 986     BN_CTX_start(ctx);
 987     if ((u = BN_CTX_get(ctx)) == NULL)
 988         goto err;
 989
 990     if (!BN_set_bit(u, p[0] - 1))
 991         goto err;
 992     ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx);
 993     bn_check_top(r);
 994
 995  err:
 996     BN_CTX_end(ctx);
 997     return ret;
 998 }
 999
1000 /*
1001  * Compute the square root of a, reduce modulo p, and store the result in r.
1002  * r could be a. This function calls down to the BN_GF2m_mod_sqrt_arr
1003  * implementation; this wrapper function is only provided for convenience;
1004  * for best performance, use the BN_GF2m_mod_sqrt_arr function.
1005  */
1006 int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
1007 {
1008     int ret = 0;
1009     const int max = BN_num_bits(p) + 1;
1010     int *arr = NULL;
1011     bn_check_top(a);
1012     bn_check_top(p);
1013     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
1014         goto err;
1015     ret = BN_GF2m_poly2arr(p, arr, max);
1016     if (!ret || ret > max) {
1017         BNerr(BN_F_BN_GF2M_MOD_SQRT, BN_R_INVALID_LENGTH);
1018         goto err;
1019     }
1020     ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx);
1021     bn_check_top(r);
1022  err:
1023     OPENSSL_free(arr);
1024     return ret;
1025 }
1026
1027 /*
1028  * Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns
1029  * 0. Uses algorithms A.4.7 and A.4.6 from IEEE P1363.
1030  */
1031 int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const int p[],
1032                                BN_CTX *ctx)
1033 {
1034     int ret = 0, count = 0, j;
1035     BIGNUM *a, *z, *rho, *w, *w2, *tmp;
1036
1037     bn_check_top(a_);
1038
1039     if (!p[0]) {
1040         /* reduction mod 1 => return 0 */
1041         BN_zero(r);
1042         return 1;
1043     }
1044
1045     BN_CTX_start(ctx);
1046     a = BN_CTX_get(ctx);
1047     z = BN_CTX_get(ctx);
1048     w = BN_CTX_get(ctx);
1049     if (w == NULL)
1050         goto err;
1051
1052     if (!BN_GF2m_mod_arr(a, a_, p))
1053         goto err;
1054
1055     if (BN_is_zero(a)) {
1056         BN_zero(r);
1057         ret = 1;
1058         goto err;
1059     }
1060
1061     if (p[0] & 0x1) {           /* m is odd */
1062         /* compute half-trace of a */
1063         if (!BN_copy(z, a))
1064             goto err;
1065         for (j = 1; j <= (p[0] - 1) / 2; j++) {
1066             if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx))
1067                 goto err;
1068             if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx))
1069                 goto err;
1070             if (!BN_GF2m_add(z, z, a))
1071                 goto err;
1072         }
1073
1074     } else {                    /* m is even */
1075
1076         rho = BN_CTX_get(ctx);
1077         w2 = BN_CTX_get(ctx);
1078         tmp = BN_CTX_get(ctx);
1079         if (tmp == NULL)
1080             goto err;
1081         do {
1082             if (!BN_rand(rho, p[0], BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
1083                 goto err;
1084             if (!BN_GF2m_mod_arr(rho, rho, p))
1085                 goto err;
1086             BN_zero(z);
1087             if (!BN_copy(w, rho))
1088                 goto err;
1089             for (j = 1; j <= p[0] - 1; j++) {
1090                 if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx))
1091                     goto err;
1092                 if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx))
1093                     goto err;
1094                 if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx))
1095                     goto err;
1096                 if (!BN_GF2m_add(z, z, tmp))
1097                     goto err;
1098                 if (!BN_GF2m_add(w, w2, rho))
1099                     goto err;
1100             }
1101             count++;
1102         } while (BN_is_zero(w) && (count < MAX_ITERATIONS));
1103         if (BN_is_zero(w)) {
1104             BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_TOO_MANY_ITERATIONS);
1105             goto err;
1106         }
1107     }
1108
1109     if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx))
1110         goto err;
1111     if (!BN_GF2m_add(w, z, w))
1112         goto err;
1113     if (BN_GF2m_cmp(w, a)) {
1114         BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION);
1115         goto err;
1116     }
1117
1118     if (!BN_copy(r, z))
1119         goto err;
1120     bn_check_top(r);
1121
1122     ret = 1;
1123
1124  err:
1125     BN_CTX_end(ctx);
1126     return ret;
1127 }
1128
1129 /*
1130  * Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns
1131  * 0. This function calls down to the BN_GF2m_mod_solve_quad_arr
1132  * implementation; this wrapper function is only provided for convenience;
1133  * for best performance, use the BN_GF2m_mod_solve_quad_arr function.
1134  */
1135 int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
1136                            BN_CTX *ctx)
1137 {
1138     int ret = 0;
1139     const int max = BN_num_bits(p) + 1;
1140     int *arr = NULL;
1141     bn_check_top(a);
1142     bn_check_top(p);
1143     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
1144         goto err;
1145     ret = BN_GF2m_poly2arr(p, arr, max);
1146     if (!ret || ret > max) {
1147         BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD, BN_R_INVALID_LENGTH);
1148         goto err;
1149     }
1150     ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx);
1151     bn_check_top(r);
1152  err:
1153     OPENSSL_free(arr);
1154     return ret;
1155 }
1156
1157 /*
1158  * Convert the bit-string representation of a polynomial ( \sum_{i=0}^n a_i *
1159  * x^i) into an array of integers corresponding to the bits with non-zero
1160  * coefficient.  Array is terminated with -1. Up to max elements of the array
1161  * will be filled.  Return value is total number of array elements that would
1162  * be filled if array was large enough.
1163  */
1164 int BN_GF2m_poly2arr(const BIGNUM *a, int p[], int max)
1165 {
1166     int i, j, k = 0;
1167     BN_ULONG mask;
1168
1169     if (BN_is_zero(a))
1170         return 0;
1171
1172     for (i = a->top - 1; i >= 0; i--) {
1173         if (!a->d[i])
1174             /* skip word if a->d[i] == 0 */
1175             continue;
1176         mask = BN_TBIT;
1177         for (j = BN_BITS2 - 1; j >= 0; j--) {
1178             if (a->d[i] & mask) {
1179                 if (k < max)
1180                     p[k] = BN_BITS2 * i + j;
1181                 k++;
1182             }
1183             mask >>= 1;
1184         }
1185     }
1186
1187     if (k < max) {
1188         p[k] = -1;
1189         k++;
1190     }
1191
1192     return k;
1193 }
1194
1195 /*
1196  * Convert the coefficient array representation of a polynomial to a
1197  * bit-string.  The array must be terminated by -1.
1198  */
1199 int BN_GF2m_arr2poly(const int p[], BIGNUM *a)
1200 {
1201     int i;
1202
1203     bn_check_top(a);
1204     BN_zero(a);
1205     for (i = 0; p[i] != -1; i++) {
1206         if (BN_set_bit(a, p[i]) == 0)
1207             return 0;
1208     }
1209     bn_check_top(a);
1210
1211     return 1;
1212 }
1213
1214 #endif