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