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