Ensure we test all parameters for BN_FLG_CONSTTIME
[openssl.git] / crypto / bn / bn_gf2m.c
1 /*
2  * Copyright 2002-2017 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     b = BN_CTX_get(ctx);
561     c = BN_CTX_get(ctx);
562     u = BN_CTX_get(ctx);
563     v = BN_CTX_get(ctx);
564     if (v == NULL)
565         goto err;
566
567     if (!BN_GF2m_mod(u, a, p))
568         goto err;
569     if (BN_is_zero(u))
570         goto err;
571
572     if (!BN_copy(v, p))
573         goto err;
574 # if 0
575     if (!BN_one(b))
576         goto err;
577
578     while (1) {
579         while (!BN_is_odd(u)) {
580             if (BN_is_zero(u))
581                 goto err;
582             if (!BN_rshift1(u, u))
583                 goto err;
584             if (BN_is_odd(b)) {
585                 if (!BN_GF2m_add(b, b, p))
586                     goto err;
587             }
588             if (!BN_rshift1(b, b))
589                 goto err;
590         }
591
592         if (BN_abs_is_word(u, 1))
593             break;
594
595         if (BN_num_bits(u) < BN_num_bits(v)) {
596             tmp = u;
597             u = v;
598             v = tmp;
599             tmp = b;
600             b = c;
601             c = tmp;
602         }
603
604         if (!BN_GF2m_add(u, u, v))
605             goto err;
606         if (!BN_GF2m_add(b, b, c))
607             goto err;
608     }
609 # else
610     {
611         int i;
612         int ubits = BN_num_bits(u);
613         int vbits = BN_num_bits(v); /* v is copy of p */
614         int top = p->top;
615         BN_ULONG *udp, *bdp, *vdp, *cdp;
616
617         if (!bn_wexpand(u, top))
618             goto err;
619         udp = u->d;
620         for (i = u->top; i < top; i++)
621             udp[i] = 0;
622         u->top = top;
623         if (!bn_wexpand(b, top))
624           goto err;
625         bdp = b->d;
626         bdp[0] = 1;
627         for (i = 1; i < top; i++)
628             bdp[i] = 0;
629         b->top = top;
630         if (!bn_wexpand(c, top))
631           goto err;
632         cdp = c->d;
633         for (i = 0; i < top; i++)
634             cdp[i] = 0;
635         c->top = top;
636         vdp = v->d;             /* It pays off to "cache" *->d pointers,
637                                  * because it allows optimizer to be more
638                                  * aggressive. But we don't have to "cache"
639                                  * p->d, because *p is declared 'const'... */
640         while (1) {
641             while (ubits && !(udp[0] & 1)) {
642                 BN_ULONG u0, u1, b0, b1, mask;
643
644                 u0 = udp[0];
645                 b0 = bdp[0];
646                 mask = (BN_ULONG)0 - (b0 & 1);
647                 b0 ^= p->d[0] & mask;
648                 for (i = 0; i < top - 1; i++) {
649                     u1 = udp[i + 1];
650                     udp[i] = ((u0 >> 1) | (u1 << (BN_BITS2 - 1))) & BN_MASK2;
651                     u0 = u1;
652                     b1 = bdp[i + 1] ^ (p->d[i + 1] & mask);
653                     bdp[i] = ((b0 >> 1) | (b1 << (BN_BITS2 - 1))) & BN_MASK2;
654                     b0 = b1;
655                 }
656                 udp[i] = u0 >> 1;
657                 bdp[i] = b0 >> 1;
658                 ubits--;
659             }
660
661             if (ubits <= BN_BITS2) {
662                 if (udp[0] == 0) /* poly was reducible */
663                     goto err;
664                 if (udp[0] == 1)
665                     break;
666             }
667
668             if (ubits < vbits) {
669                 i = ubits;
670                 ubits = vbits;
671                 vbits = i;
672                 tmp = u;
673                 u = v;
674                 v = tmp;
675                 tmp = b;
676                 b = c;
677                 c = tmp;
678                 udp = vdp;
679                 vdp = v->d;
680                 bdp = cdp;
681                 cdp = c->d;
682             }
683             for (i = 0; i < top; i++) {
684                 udp[i] ^= vdp[i];
685                 bdp[i] ^= cdp[i];
686             }
687             if (ubits == vbits) {
688                 BN_ULONG ul;
689                 int utop = (ubits - 1) / BN_BITS2;
690
691                 while ((ul = udp[utop]) == 0 && utop)
692                     utop--;
693                 ubits = utop * BN_BITS2 + BN_num_bits_word(ul);
694             }
695         }
696         bn_correct_top(b);
697     }
698 # endif
699
700     if (!BN_copy(r, b))
701         goto err;
702     bn_check_top(r);
703     ret = 1;
704
705  err:
706 # ifdef BN_DEBUG                /* BN_CTX_end would complain about the
707                                  * expanded form */
708     bn_correct_top(c);
709     bn_correct_top(u);
710     bn_correct_top(v);
711 # endif
712     BN_CTX_end(ctx);
713     return ret;
714 }
715
716 /*
717  * Invert xx, reduce modulo p, and store the result in r. r could be xx.
718  * This function calls down to the BN_GF2m_mod_inv implementation; this
719  * wrapper function is only provided for convenience; for best performance,
720  * use the BN_GF2m_mod_inv function.
721  */
722 int BN_GF2m_mod_inv_arr(BIGNUM *r, const BIGNUM *xx, const int p[],
723                         BN_CTX *ctx)
724 {
725     BIGNUM *field;
726     int ret = 0;
727
728     bn_check_top(xx);
729     BN_CTX_start(ctx);
730     if ((field = BN_CTX_get(ctx)) == NULL)
731         goto err;
732     if (!BN_GF2m_arr2poly(p, field))
733         goto err;
734
735     ret = BN_GF2m_mod_inv(r, xx, field, ctx);
736     bn_check_top(r);
737
738  err:
739     BN_CTX_end(ctx);
740     return ret;
741 }
742
743 # ifndef OPENSSL_SUN_GF2M_DIV
744 /*
745  * Divide y by x, reduce modulo p, and store the result in r. r could be x
746  * or y, x could equal y.
747  */
748 int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x,
749                     const BIGNUM *p, BN_CTX *ctx)
750 {
751     BIGNUM *xinv = NULL;
752     int ret = 0;
753
754     bn_check_top(y);
755     bn_check_top(x);
756     bn_check_top(p);
757
758     BN_CTX_start(ctx);
759     xinv = BN_CTX_get(ctx);
760     if (xinv == NULL)
761         goto err;
762
763     if (!BN_GF2m_mod_inv(xinv, x, p, ctx))
764         goto err;
765     if (!BN_GF2m_mod_mul(r, y, xinv, p, ctx))
766         goto err;
767     bn_check_top(r);
768     ret = 1;
769
770  err:
771     BN_CTX_end(ctx);
772     return ret;
773 }
774 # else
775 /*
776  * Divide y by x, reduce modulo p, and store the result in r. r could be x
777  * or y, x could equal y. Uses algorithm Modular_Division_GF(2^m) from
778  * Chang-Shantz, S.  "From Euclid's GCD to Montgomery Multiplication to the
779  * Great Divide".
780  */
781 int BN_GF2m_mod_div(BIGNUM *r, const BIGNUM *y, const BIGNUM *x,
782                     const BIGNUM *p, BN_CTX *ctx)
783 {
784     BIGNUM *a, *b, *u, *v;
785     int ret = 0;
786
787     bn_check_top(y);
788     bn_check_top(x);
789     bn_check_top(p);
790
791     BN_CTX_start(ctx);
792
793     a = BN_CTX_get(ctx);
794     b = BN_CTX_get(ctx);
795     u = BN_CTX_get(ctx);
796     v = BN_CTX_get(ctx);
797     if (v == NULL)
798         goto err;
799
800     /* reduce x and y mod p */
801     if (!BN_GF2m_mod(u, y, p))
802         goto err;
803     if (!BN_GF2m_mod(a, x, p))
804         goto err;
805     if (!BN_copy(b, p))
806         goto err;
807
808     while (!BN_is_odd(a)) {
809         if (!BN_rshift1(a, a))
810             goto err;
811         if (BN_is_odd(u))
812             if (!BN_GF2m_add(u, u, p))
813                 goto err;
814         if (!BN_rshift1(u, u))
815             goto err;
816     }
817
818     do {
819         if (BN_GF2m_cmp(b, a) > 0) {
820             if (!BN_GF2m_add(b, b, a))
821                 goto err;
822             if (!BN_GF2m_add(v, v, u))
823                 goto err;
824             do {
825                 if (!BN_rshift1(b, b))
826                     goto err;
827                 if (BN_is_odd(v))
828                     if (!BN_GF2m_add(v, v, p))
829                         goto err;
830                 if (!BN_rshift1(v, v))
831                     goto err;
832             } while (!BN_is_odd(b));
833         } else if (BN_abs_is_word(a, 1))
834             break;
835         else {
836             if (!BN_GF2m_add(a, a, b))
837                 goto err;
838             if (!BN_GF2m_add(u, u, v))
839                 goto err;
840             do {
841                 if (!BN_rshift1(a, a))
842                     goto err;
843                 if (BN_is_odd(u))
844                     if (!BN_GF2m_add(u, u, p))
845                         goto err;
846                 if (!BN_rshift1(u, u))
847                     goto err;
848             } while (!BN_is_odd(a));
849         }
850     } while (1);
851
852     if (!BN_copy(r, u))
853         goto err;
854     bn_check_top(r);
855     ret = 1;
856
857  err:
858     BN_CTX_end(ctx);
859     return ret;
860 }
861 # endif
862
863 /*
864  * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx
865  * * or yy, xx could equal yy. This function calls down to the
866  * BN_GF2m_mod_div implementation; this wrapper function is only provided for
867  * convenience; for best performance, use the BN_GF2m_mod_div function.
868  */
869 int BN_GF2m_mod_div_arr(BIGNUM *r, const BIGNUM *yy, const BIGNUM *xx,
870                         const int p[], BN_CTX *ctx)
871 {
872     BIGNUM *field;
873     int ret = 0;
874
875     bn_check_top(yy);
876     bn_check_top(xx);
877
878     BN_CTX_start(ctx);
879     if ((field = BN_CTX_get(ctx)) == NULL)
880         goto err;
881     if (!BN_GF2m_arr2poly(p, field))
882         goto err;
883
884     ret = BN_GF2m_mod_div(r, yy, xx, field, ctx);
885     bn_check_top(r);
886
887  err:
888     BN_CTX_end(ctx);
889     return ret;
890 }
891
892 /*
893  * Compute the bth power of a, reduce modulo p, and store the result in r.  r
894  * could be a. Uses simple square-and-multiply algorithm A.5.1 from IEEE
895  * P1363.
896  */
897 int BN_GF2m_mod_exp_arr(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
898                         const int p[], BN_CTX *ctx)
899 {
900     int ret = 0, i, n;
901     BIGNUM *u;
902
903     bn_check_top(a);
904     bn_check_top(b);
905
906     if (BN_is_zero(b))
907         return (BN_one(r));
908
909     if (BN_abs_is_word(b, 1))
910         return (BN_copy(r, a) != NULL);
911
912     BN_CTX_start(ctx);
913     if ((u = BN_CTX_get(ctx)) == NULL)
914         goto err;
915
916     if (!BN_GF2m_mod_arr(u, a, p))
917         goto err;
918
919     n = BN_num_bits(b) - 1;
920     for (i = n - 1; i >= 0; i--) {
921         if (!BN_GF2m_mod_sqr_arr(u, u, p, ctx))
922             goto err;
923         if (BN_is_bit_set(b, i)) {
924             if (!BN_GF2m_mod_mul_arr(u, u, a, p, ctx))
925                 goto err;
926         }
927     }
928     if (!BN_copy(r, u))
929         goto err;
930     bn_check_top(r);
931     ret = 1;
932  err:
933     BN_CTX_end(ctx);
934     return ret;
935 }
936
937 /*
938  * Compute the bth power of a, reduce modulo p, and store the result in r.  r
939  * could be a. This function calls down to the BN_GF2m_mod_exp_arr
940  * implementation; this wrapper function is only provided for convenience;
941  * for best performance, use the BN_GF2m_mod_exp_arr function.
942  */
943 int BN_GF2m_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *b,
944                     const BIGNUM *p, BN_CTX *ctx)
945 {
946     int ret = 0;
947     const int max = BN_num_bits(p) + 1;
948     int *arr = NULL;
949     bn_check_top(a);
950     bn_check_top(b);
951     bn_check_top(p);
952     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
953         goto err;
954     ret = BN_GF2m_poly2arr(p, arr, max);
955     if (!ret || ret > max) {
956         BNerr(BN_F_BN_GF2M_MOD_EXP, BN_R_INVALID_LENGTH);
957         goto err;
958     }
959     ret = BN_GF2m_mod_exp_arr(r, a, b, arr, ctx);
960     bn_check_top(r);
961  err:
962     OPENSSL_free(arr);
963     return ret;
964 }
965
966 /*
967  * Compute the square root of a, reduce modulo p, and store the result in r.
968  * r could be a. Uses exponentiation as in algorithm A.4.1 from IEEE P1363.
969  */
970 int BN_GF2m_mod_sqrt_arr(BIGNUM *r, const BIGNUM *a, const int p[],
971                          BN_CTX *ctx)
972 {
973     int ret = 0;
974     BIGNUM *u;
975
976     bn_check_top(a);
977
978     if (!p[0]) {
979         /* reduction mod 1 => return 0 */
980         BN_zero(r);
981         return 1;
982     }
983
984     BN_CTX_start(ctx);
985     if ((u = BN_CTX_get(ctx)) == NULL)
986         goto err;
987
988     if (!BN_set_bit(u, p[0] - 1))
989         goto err;
990     ret = BN_GF2m_mod_exp_arr(r, a, u, p, ctx);
991     bn_check_top(r);
992
993  err:
994     BN_CTX_end(ctx);
995     return ret;
996 }
997
998 /*
999  * Compute the square root of a, reduce modulo p, and store the result in r.
1000  * r could be a. This function calls down to the BN_GF2m_mod_sqrt_arr
1001  * implementation; this wrapper function is only provided for convenience;
1002  * for best performance, use the BN_GF2m_mod_sqrt_arr function.
1003  */
1004 int BN_GF2m_mod_sqrt(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
1005 {
1006     int ret = 0;
1007     const int max = BN_num_bits(p) + 1;
1008     int *arr = NULL;
1009     bn_check_top(a);
1010     bn_check_top(p);
1011     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
1012         goto err;
1013     ret = BN_GF2m_poly2arr(p, arr, max);
1014     if (!ret || ret > max) {
1015         BNerr(BN_F_BN_GF2M_MOD_SQRT, BN_R_INVALID_LENGTH);
1016         goto err;
1017     }
1018     ret = BN_GF2m_mod_sqrt_arr(r, a, arr, ctx);
1019     bn_check_top(r);
1020  err:
1021     OPENSSL_free(arr);
1022     return ret;
1023 }
1024
1025 /*
1026  * Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns
1027  * 0. Uses algorithms A.4.7 and A.4.6 from IEEE P1363.
1028  */
1029 int BN_GF2m_mod_solve_quad_arr(BIGNUM *r, const BIGNUM *a_, const int p[],
1030                                BN_CTX *ctx)
1031 {
1032     int ret = 0, count = 0, j;
1033     BIGNUM *a, *z, *rho, *w, *w2, *tmp;
1034
1035     bn_check_top(a_);
1036
1037     if (!p[0]) {
1038         /* reduction mod 1 => return 0 */
1039         BN_zero(r);
1040         return 1;
1041     }
1042
1043     BN_CTX_start(ctx);
1044     a = BN_CTX_get(ctx);
1045     z = BN_CTX_get(ctx);
1046     w = BN_CTX_get(ctx);
1047     if (w == NULL)
1048         goto err;
1049
1050     if (!BN_GF2m_mod_arr(a, a_, p))
1051         goto err;
1052
1053     if (BN_is_zero(a)) {
1054         BN_zero(r);
1055         ret = 1;
1056         goto err;
1057     }
1058
1059     if (p[0] & 0x1) {           /* m is odd */
1060         /* compute half-trace of a */
1061         if (!BN_copy(z, a))
1062             goto err;
1063         for (j = 1; j <= (p[0] - 1) / 2; j++) {
1064             if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx))
1065                 goto err;
1066             if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx))
1067                 goto err;
1068             if (!BN_GF2m_add(z, z, a))
1069                 goto err;
1070         }
1071
1072     } else {                    /* m is even */
1073
1074         rho = BN_CTX_get(ctx);
1075         w2 = BN_CTX_get(ctx);
1076         tmp = BN_CTX_get(ctx);
1077         if (tmp == NULL)
1078             goto err;
1079         do {
1080             if (!BN_priv_rand(rho, p[0], BN_RAND_TOP_ONE, BN_RAND_BOTTOM_ANY))
1081                 goto err;
1082             if (!BN_GF2m_mod_arr(rho, rho, p))
1083                 goto err;
1084             BN_zero(z);
1085             if (!BN_copy(w, rho))
1086                 goto err;
1087             for (j = 1; j <= p[0] - 1; j++) {
1088                 if (!BN_GF2m_mod_sqr_arr(z, z, p, ctx))
1089                     goto err;
1090                 if (!BN_GF2m_mod_sqr_arr(w2, w, p, ctx))
1091                     goto err;
1092                 if (!BN_GF2m_mod_mul_arr(tmp, w2, a, p, ctx))
1093                     goto err;
1094                 if (!BN_GF2m_add(z, z, tmp))
1095                     goto err;
1096                 if (!BN_GF2m_add(w, w2, rho))
1097                     goto err;
1098             }
1099             count++;
1100         } while (BN_is_zero(w) && (count < MAX_ITERATIONS));
1101         if (BN_is_zero(w)) {
1102             BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_TOO_MANY_ITERATIONS);
1103             goto err;
1104         }
1105     }
1106
1107     if (!BN_GF2m_mod_sqr_arr(w, z, p, ctx))
1108         goto err;
1109     if (!BN_GF2m_add(w, z, w))
1110         goto err;
1111     if (BN_GF2m_cmp(w, a)) {
1112         BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR, BN_R_NO_SOLUTION);
1113         goto err;
1114     }
1115
1116     if (!BN_copy(r, z))
1117         goto err;
1118     bn_check_top(r);
1119
1120     ret = 1;
1121
1122  err:
1123     BN_CTX_end(ctx);
1124     return ret;
1125 }
1126
1127 /*
1128  * Find r such that r^2 + r = a mod p.  r could be a. If no r exists returns
1129  * 0. This function calls down to the BN_GF2m_mod_solve_quad_arr
1130  * implementation; this wrapper function is only provided for convenience;
1131  * for best performance, use the BN_GF2m_mod_solve_quad_arr function.
1132  */
1133 int BN_GF2m_mod_solve_quad(BIGNUM *r, const BIGNUM *a, const BIGNUM *p,
1134                            BN_CTX *ctx)
1135 {
1136     int ret = 0;
1137     const int max = BN_num_bits(p) + 1;
1138     int *arr = NULL;
1139     bn_check_top(a);
1140     bn_check_top(p);
1141     if ((arr = OPENSSL_malloc(sizeof(*arr) * max)) == NULL)
1142         goto err;
1143     ret = BN_GF2m_poly2arr(p, arr, max);
1144     if (!ret || ret > max) {
1145         BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD, BN_R_INVALID_LENGTH);
1146         goto err;
1147     }
1148     ret = BN_GF2m_mod_solve_quad_arr(r, a, arr, ctx);
1149     bn_check_top(r);
1150  err:
1151     OPENSSL_free(arr);
1152     return ret;
1153 }
1154
1155 /*
1156  * Convert the bit-string representation of a polynomial ( \sum_{i=0}^n a_i *
1157  * x^i) into an array of integers corresponding to the bits with non-zero
1158  * coefficient.  Array is terminated with -1. Up to max elements of the array
1159  * will be filled.  Return value is total number of array elements that would
1160  * be filled if array was large enough.
1161  */
1162 int BN_GF2m_poly2arr(const BIGNUM *a, int p[], int max)
1163 {
1164     int i, j, k = 0;
1165     BN_ULONG mask;
1166
1167     if (BN_is_zero(a))
1168         return 0;
1169
1170     for (i = a->top - 1; i >= 0; i--) {
1171         if (!a->d[i])
1172             /* skip word if a->d[i] == 0 */
1173             continue;
1174         mask = BN_TBIT;
1175         for (j = BN_BITS2 - 1; j >= 0; j--) {
1176             if (a->d[i] & mask) {
1177                 if (k < max)
1178                     p[k] = BN_BITS2 * i + j;
1179                 k++;
1180             }
1181             mask >>= 1;
1182         }
1183     }
1184
1185     if (k < max) {
1186         p[k] = -1;
1187         k++;
1188     }
1189
1190     return k;
1191 }
1192
1193 /*
1194  * Convert the coefficient array representation of a polynomial to a
1195  * bit-string.  The array must be terminated by -1.
1196  */
1197 int BN_GF2m_arr2poly(const int p[], BIGNUM *a)
1198 {
1199     int i;
1200
1201     bn_check_top(a);
1202     BN_zero(a);
1203     for (i = 0; p[i] != -1; i++) {
1204         if (BN_set_bit(a, p[i]) == 0)
1205             return 0;
1206     }
1207     bn_check_top(a);
1208
1209     return 1;
1210 }
1211
1212 #endif