2 * Copyright 2002-2018 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
5 * Licensed under the Apache License 2.0 (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
14 #include "internal/cryptlib.h"
17 #ifndef OPENSSL_NO_EC2M
20 * Maximum number of iterations before BN_GF2m_mod_solve_quad_arr should
23 # define MAX_ITERATIONS 50
25 # define SQR_nibble(w) ((((w) & 8) << 3) \
31 /* Platform-specific macros to accelerate squaring. */
32 # if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
34 SQR_nibble((w) >> 60) << 56 | SQR_nibble((w) >> 56) << 48 | \
35 SQR_nibble((w) >> 52) << 40 | SQR_nibble((w) >> 48) << 32 | \
36 SQR_nibble((w) >> 44) << 24 | SQR_nibble((w) >> 40) << 16 | \
37 SQR_nibble((w) >> 36) << 8 | SQR_nibble((w) >> 32)
39 SQR_nibble((w) >> 28) << 56 | SQR_nibble((w) >> 24) << 48 | \
40 SQR_nibble((w) >> 20) << 40 | SQR_nibble((w) >> 16) << 32 | \
41 SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >> 8) << 16 | \
42 SQR_nibble((w) >> 4) << 8 | SQR_nibble((w) )
44 # ifdef THIRTY_TWO_BIT
46 SQR_nibble((w) >> 28) << 24 | SQR_nibble((w) >> 24) << 16 | \
47 SQR_nibble((w) >> 20) << 8 | SQR_nibble((w) >> 16)
49 SQR_nibble((w) >> 12) << 24 | SQR_nibble((w) >> 8) << 16 | \
50 SQR_nibble((w) >> 4) << 8 | SQR_nibble((w) )
53 # if !defined(OPENSSL_BN_ASM_GF2m)
55 * Product of two polynomials a, b each with degree < BN_BITS2 - 1, result is
56 * a polynomial r with degree < 2 * BN_BITS - 1 The caller MUST ensure that
57 * the variables have the right amount of space allocated.
59 # ifdef THIRTY_TWO_BIT
60 static void bn_GF2m_mul_1x1(BN_ULONG
*r1
, BN_ULONG
*r0
, const BN_ULONG a
,
63 register BN_ULONG h
, l
, s
;
64 BN_ULONG tab
[8], top2b
= a
>> 30;
65 register BN_ULONG a1
, a2
, a4
;
67 a1
= a
& (0x3FFFFFFF);
78 tab
[7] = a1
^ a2
^ a4
;
82 s
= tab
[b
>> 3 & 0x7];
85 s
= tab
[b
>> 6 & 0x7];
88 s
= tab
[b
>> 9 & 0x7];
91 s
= tab
[b
>> 12 & 0x7];
94 s
= tab
[b
>> 15 & 0x7];
97 s
= tab
[b
>> 18 & 0x7];
100 s
= tab
[b
>> 21 & 0x7];
103 s
= tab
[b
>> 24 & 0x7];
106 s
= tab
[b
>> 27 & 0x7];
113 /* compensate for the top two bits of a */
128 # if defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
129 static void bn_GF2m_mul_1x1(BN_ULONG
*r1
, BN_ULONG
*r0
, const BN_ULONG a
,
132 register BN_ULONG h
, l
, s
;
133 BN_ULONG tab
[16], top3b
= a
>> 61;
134 register BN_ULONG a1
, a2
, a4
, a8
;
136 a1
= a
& (0x1FFFFFFFFFFFFFFFULL
);
148 tab
[7] = a1
^ a2
^ a4
;
152 tab
[11] = a1
^ a2
^ a8
;
154 tab
[13] = a1
^ a4
^ a8
;
155 tab
[14] = a2
^ a4
^ a8
;
156 tab
[15] = a1
^ a2
^ a4
^ a8
;
160 s
= tab
[b
>> 4 & 0xF];
163 s
= tab
[b
>> 8 & 0xF];
166 s
= tab
[b
>> 12 & 0xF];
169 s
= tab
[b
>> 16 & 0xF];
172 s
= tab
[b
>> 20 & 0xF];
175 s
= tab
[b
>> 24 & 0xF];
178 s
= tab
[b
>> 28 & 0xF];
181 s
= tab
[b
>> 32 & 0xF];
184 s
= tab
[b
>> 36 & 0xF];
187 s
= tab
[b
>> 40 & 0xF];
190 s
= tab
[b
>> 44 & 0xF];
193 s
= tab
[b
>> 48 & 0xF];
196 s
= tab
[b
>> 52 & 0xF];
199 s
= tab
[b
>> 56 & 0xF];
206 /* compensate for the top three bits of a */
227 * Product of two polynomials a, b each with degree < 2 * BN_BITS2 - 1,
228 * result is a polynomial r with degree < 4 * BN_BITS2 - 1 The caller MUST
229 * ensure that the variables have the right amount of space allocated.
231 static void bn_GF2m_mul_2x2(BN_ULONG
*r
, const BN_ULONG a1
, const BN_ULONG a0
,
232 const BN_ULONG b1
, const BN_ULONG b0
)
235 /* r[3] = h1, r[2] = h0; r[1] = l1; r[0] = l0 */
236 bn_GF2m_mul_1x1(r
+ 3, r
+ 2, a1
, b1
);
237 bn_GF2m_mul_1x1(r
+ 1, r
, a0
, b0
);
238 bn_GF2m_mul_1x1(&m1
, &m0
, a0
^ a1
, b0
^ b1
);
239 /* Correction on m1 ^= l1 ^ h1; m0 ^= l0 ^ h0; */
240 r
[2] ^= m1
^ r
[1] ^ r
[3]; /* h0 ^= m1 ^ l1 ^ h1; */
241 r
[1] = r
[3] ^ r
[2] ^ r
[0] ^ m1
^ m0
; /* l1 ^= l0 ^ h0 ^ m0; */
244 void bn_GF2m_mul_2x2(BN_ULONG
*r
, BN_ULONG a1
, BN_ULONG a0
, BN_ULONG b1
,
249 * Add polynomials a and b and store result in r; r could be a or b, a and b
250 * could be equal; r is the bitwise XOR of a and b.
252 int BN_GF2m_add(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
)
255 const BIGNUM
*at
, *bt
;
260 if (a
->top
< b
->top
) {
268 if (bn_wexpand(r
, at
->top
) == NULL
)
271 for (i
= 0; i
< bt
->top
; i
++) {
272 r
->d
[i
] = at
->d
[i
] ^ bt
->d
[i
];
274 for (; i
< at
->top
; i
++) {
285 * Some functions allow for representation of the irreducible polynomials
286 * as an int[], say p. The irreducible f(t) is then of the form:
287 * t^p[0] + t^p[1] + ... + t^p[k]
288 * where m = p[0] > p[1] > ... > p[k] = 0.
291 /* Performs modular reduction of a and store result in r. r could be a. */
292 int BN_GF2m_mod_arr(BIGNUM
*r
, const BIGNUM
*a
, const int p
[])
301 /* reduction mod 1 => return 0 */
307 * Since the algorithm does reduction in the r value, if a != r, copy the
308 * contents of a into r so we can do reduction in r.
311 if (!bn_wexpand(r
, a
->top
))
313 for (j
= 0; j
< a
->top
; j
++) {
320 /* start reduction */
321 dN
= p
[0] / BN_BITS2
;
322 for (j
= r
->top
- 1; j
> dN
;) {
330 for (k
= 1; p
[k
] != 0; k
++) {
331 /* reducing component t^p[k] */
336 z
[j
- n
] ^= (zz
>> d0
);
338 z
[j
- n
- 1] ^= (zz
<< d1
);
341 /* reducing component t^0 */
343 d0
= p
[0] % BN_BITS2
;
345 z
[j
- n
] ^= (zz
>> d0
);
347 z
[j
- n
- 1] ^= (zz
<< d1
);
350 /* final round of reduction */
353 d0
= p
[0] % BN_BITS2
;
359 /* clear up the top d1 bits */
361 z
[dN
] = (z
[dN
] << d1
) >> d1
;
364 z
[0] ^= zz
; /* reduction t^0 component */
366 for (k
= 1; p
[k
] != 0; k
++) {
369 /* reducing component t^p[k] */
371 d0
= p
[k
] % BN_BITS2
;
374 if (d0
&& (tmp_ulong
= zz
>> d1
))
375 z
[n
+ 1] ^= tmp_ulong
;
385 * Performs modular reduction of a by p and store result in r. r could be a.
386 * This function calls down to the BN_GF2m_mod_arr implementation; this wrapper
387 * function is only provided for convenience; for best performance, use the
388 * BN_GF2m_mod_arr function.
390 int BN_GF2m_mod(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
)
396 ret
= BN_GF2m_poly2arr(p
, arr
, OSSL_NELEM(arr
));
397 if (!ret
|| ret
> (int)OSSL_NELEM(arr
)) {
398 BNerr(BN_F_BN_GF2M_MOD
, BN_R_INVALID_LENGTH
);
401 ret
= BN_GF2m_mod_arr(r
, a
, arr
);
407 * Compute the product of two polynomials a and b, reduce modulo p, and store
408 * the result in r. r could be a or b; a could be b.
410 int BN_GF2m_mod_mul_arr(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
411 const int p
[], BN_CTX
*ctx
)
413 int zlen
, i
, j
, k
, ret
= 0;
415 BN_ULONG x1
, x0
, y1
, y0
, zz
[4];
421 return BN_GF2m_mod_sqr_arr(r
, a
, p
, ctx
);
425 if ((s
= BN_CTX_get(ctx
)) == NULL
)
428 zlen
= a
->top
+ b
->top
+ 4;
429 if (!bn_wexpand(s
, zlen
))
433 for (i
= 0; i
< zlen
; i
++)
436 for (j
= 0; j
< b
->top
; j
+= 2) {
438 y1
= ((j
+ 1) == b
->top
) ? 0 : b
->d
[j
+ 1];
439 for (i
= 0; i
< a
->top
; i
+= 2) {
441 x1
= ((i
+ 1) == a
->top
) ? 0 : a
->d
[i
+ 1];
442 bn_GF2m_mul_2x2(zz
, x1
, x0
, y1
, y0
);
443 for (k
= 0; k
< 4; k
++)
444 s
->d
[i
+ j
+ k
] ^= zz
[k
];
449 if (BN_GF2m_mod_arr(r
, s
, p
))
459 * Compute the product of two polynomials a and b, reduce modulo p, and store
460 * the result in r. r could be a or b; a could equal b. This function calls
461 * down to the BN_GF2m_mod_mul_arr implementation; this wrapper function is
462 * only provided for convenience; for best performance, use the
463 * BN_GF2m_mod_mul_arr function.
465 int BN_GF2m_mod_mul(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
466 const BIGNUM
*p
, BN_CTX
*ctx
)
469 const int max
= BN_num_bits(p
) + 1;
474 if ((arr
= OPENSSL_malloc(sizeof(*arr
) * max
)) == NULL
)
476 ret
= BN_GF2m_poly2arr(p
, arr
, max
);
477 if (!ret
|| ret
> max
) {
478 BNerr(BN_F_BN_GF2M_MOD_MUL
, BN_R_INVALID_LENGTH
);
481 ret
= BN_GF2m_mod_mul_arr(r
, a
, b
, arr
, ctx
);
488 /* Square a, reduce the result mod p, and store it in a. r could be a. */
489 int BN_GF2m_mod_sqr_arr(BIGNUM
*r
, const BIGNUM
*a
, const int p
[],
497 if ((s
= BN_CTX_get(ctx
)) == NULL
)
499 if (!bn_wexpand(s
, 2 * a
->top
))
502 for (i
= a
->top
- 1; i
>= 0; i
--) {
503 s
->d
[2 * i
+ 1] = SQR1(a
->d
[i
]);
504 s
->d
[2 * i
] = SQR0(a
->d
[i
]);
509 if (!BN_GF2m_mod_arr(r
, s
, p
))
519 * Square a, reduce the result mod p, and store it in a. r could be a. This
520 * function calls down to the BN_GF2m_mod_sqr_arr implementation; this
521 * wrapper function is only provided for convenience; for best performance,
522 * use the BN_GF2m_mod_sqr_arr function.
524 int BN_GF2m_mod_sqr(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
, BN_CTX
*ctx
)
527 const int max
= BN_num_bits(p
) + 1;
532 if ((arr
= OPENSSL_malloc(sizeof(*arr
) * max
)) == NULL
)
534 ret
= BN_GF2m_poly2arr(p
, arr
, max
);
535 if (!ret
|| ret
> max
) {
536 BNerr(BN_F_BN_GF2M_MOD_SQR
, BN_R_INVALID_LENGTH
);
539 ret
= BN_GF2m_mod_sqr_arr(r
, a
, arr
, ctx
);
547 * Invert a, reduce modulo p, and store the result in r. r could be a. Uses
548 * Modified Almost Inverse Algorithm (Algorithm 10) from Hankerson, D.,
549 * Hernandez, J.L., and Menezes, A. "Software Implementation of Elliptic
550 * Curve Cryptography Over Binary Fields".
552 static int BN_GF2m_mod_inv_vartime(BIGNUM
*r
, const BIGNUM
*a
,
553 const BIGNUM
*p
, BN_CTX
*ctx
)
555 BIGNUM
*b
, *c
= NULL
, *u
= NULL
, *v
= NULL
, *tmp
;
570 if (!BN_GF2m_mod(u
, a
, p
))
582 while (!BN_is_odd(u
)) {
585 if (!BN_rshift1(u
, u
))
588 if (!BN_GF2m_add(b
, b
, p
))
591 if (!BN_rshift1(b
, b
))
595 if (BN_abs_is_word(u
, 1))
598 if (BN_num_bits(u
) < BN_num_bits(v
)) {
607 if (!BN_GF2m_add(u
, u
, v
))
609 if (!BN_GF2m_add(b
, b
, c
))
615 int ubits
= BN_num_bits(u
);
616 int vbits
= BN_num_bits(v
); /* v is copy of p */
618 BN_ULONG
*udp
, *bdp
, *vdp
, *cdp
;
620 if (!bn_wexpand(u
, top
))
623 for (i
= u
->top
; i
< top
; i
++)
626 if (!bn_wexpand(b
, top
))
630 for (i
= 1; i
< top
; i
++)
633 if (!bn_wexpand(c
, top
))
636 for (i
= 0; i
< top
; i
++)
639 vdp
= v
->d
; /* It pays off to "cache" *->d pointers,
640 * because it allows optimizer to be more
641 * aggressive. But we don't have to "cache"
642 * p->d, because *p is declared 'const'... */
644 while (ubits
&& !(udp
[0] & 1)) {
645 BN_ULONG u0
, u1
, b0
, b1
, mask
;
649 mask
= (BN_ULONG
)0 - (b0
& 1);
650 b0
^= p
->d
[0] & mask
;
651 for (i
= 0; i
< top
- 1; i
++) {
653 udp
[i
] = ((u0
>> 1) | (u1
<< (BN_BITS2
- 1))) & BN_MASK2
;
655 b1
= bdp
[i
+ 1] ^ (p
->d
[i
+ 1] & mask
);
656 bdp
[i
] = ((b0
>> 1) | (b1
<< (BN_BITS2
- 1))) & BN_MASK2
;
664 if (ubits
<= BN_BITS2
) {
665 if (udp
[0] == 0) /* poly was reducible */
686 for (i
= 0; i
< top
; i
++) {
690 if (ubits
== vbits
) {
692 int utop
= (ubits
- 1) / BN_BITS2
;
694 while ((ul
= udp
[utop
]) == 0 && utop
)
696 ubits
= utop
* BN_BITS2
+ BN_num_bits_word(ul
);
709 # ifdef BN_DEBUG /* BN_CTX_end would complain about the
720 * Wrapper for BN_GF2m_mod_inv_vartime that blinds the input before calling.
721 * This is not constant time.
722 * But it does eliminate first order deduction on the input.
724 int BN_GF2m_mod_inv(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
, BN_CTX
*ctx
)
730 if ((b
= BN_CTX_get(ctx
)) == NULL
)
733 /* generate blinding value */
735 if (!BN_priv_rand(b
, BN_num_bits(p
) - 1,
736 BN_RAND_TOP_ANY
, BN_RAND_BOTTOM_ANY
))
738 } while (BN_is_zero(b
));
741 if (!BN_GF2m_mod_mul(r
, a
, b
, p
, ctx
))
745 if (!BN_GF2m_mod_inv_vartime(r
, r
, p
, ctx
))
748 /* r := b/(a * b) = 1/a */
749 if (!BN_GF2m_mod_mul(r
, r
, b
, p
, ctx
))
760 * Invert xx, reduce modulo p, and store the result in r. r could be xx.
761 * This function calls down to the BN_GF2m_mod_inv implementation; this
762 * wrapper function is only provided for convenience; for best performance,
763 * use the BN_GF2m_mod_inv function.
765 int BN_GF2m_mod_inv_arr(BIGNUM
*r
, const BIGNUM
*xx
, const int p
[],
773 if ((field
= BN_CTX_get(ctx
)) == NULL
)
775 if (!BN_GF2m_arr2poly(p
, field
))
778 ret
= BN_GF2m_mod_inv(r
, xx
, field
, ctx
);
787 * Divide y by x, reduce modulo p, and store the result in r. r could be x
788 * or y, x could equal y.
790 int BN_GF2m_mod_div(BIGNUM
*r
, const BIGNUM
*y
, const BIGNUM
*x
,
791 const BIGNUM
*p
, BN_CTX
*ctx
)
801 xinv
= BN_CTX_get(ctx
);
805 if (!BN_GF2m_mod_inv(xinv
, x
, p
, ctx
))
807 if (!BN_GF2m_mod_mul(r
, y
, xinv
, p
, ctx
))
818 * Divide yy by xx, reduce modulo p, and store the result in r. r could be xx
819 * * or yy, xx could equal yy. This function calls down to the
820 * BN_GF2m_mod_div implementation; this wrapper function is only provided for
821 * convenience; for best performance, use the BN_GF2m_mod_div function.
823 int BN_GF2m_mod_div_arr(BIGNUM
*r
, const BIGNUM
*yy
, const BIGNUM
*xx
,
824 const int p
[], BN_CTX
*ctx
)
833 if ((field
= BN_CTX_get(ctx
)) == NULL
)
835 if (!BN_GF2m_arr2poly(p
, field
))
838 ret
= BN_GF2m_mod_div(r
, yy
, xx
, field
, ctx
);
847 * Compute the bth power of a, reduce modulo p, and store the result in r. r
848 * could be a. Uses simple square-and-multiply algorithm A.5.1 from IEEE
851 int BN_GF2m_mod_exp_arr(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
852 const int p
[], BN_CTX
*ctx
)
863 if (BN_abs_is_word(b
, 1))
864 return (BN_copy(r
, a
) != NULL
);
867 if ((u
= BN_CTX_get(ctx
)) == NULL
)
870 if (!BN_GF2m_mod_arr(u
, a
, p
))
873 n
= BN_num_bits(b
) - 1;
874 for (i
= n
- 1; i
>= 0; i
--) {
875 if (!BN_GF2m_mod_sqr_arr(u
, u
, p
, ctx
))
877 if (BN_is_bit_set(b
, i
)) {
878 if (!BN_GF2m_mod_mul_arr(u
, u
, a
, p
, ctx
))
892 * Compute the bth power of a, reduce modulo p, and store the result in r. r
893 * could be a. This function calls down to the BN_GF2m_mod_exp_arr
894 * implementation; this wrapper function is only provided for convenience;
895 * for best performance, use the BN_GF2m_mod_exp_arr function.
897 int BN_GF2m_mod_exp(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
,
898 const BIGNUM
*p
, BN_CTX
*ctx
)
901 const int max
= BN_num_bits(p
) + 1;
906 if ((arr
= OPENSSL_malloc(sizeof(*arr
) * max
)) == NULL
)
908 ret
= BN_GF2m_poly2arr(p
, arr
, max
);
909 if (!ret
|| ret
> max
) {
910 BNerr(BN_F_BN_GF2M_MOD_EXP
, BN_R_INVALID_LENGTH
);
913 ret
= BN_GF2m_mod_exp_arr(r
, a
, b
, arr
, ctx
);
921 * Compute the square root of a, reduce modulo p, and store the result in r.
922 * r could be a. Uses exponentiation as in algorithm A.4.1 from IEEE P1363.
924 int BN_GF2m_mod_sqrt_arr(BIGNUM
*r
, const BIGNUM
*a
, const int p
[],
933 /* reduction mod 1 => return 0 */
939 if ((u
= BN_CTX_get(ctx
)) == NULL
)
942 if (!BN_set_bit(u
, p
[0] - 1))
944 ret
= BN_GF2m_mod_exp_arr(r
, a
, u
, p
, ctx
);
953 * Compute the square root of a, reduce modulo p, and store the result in r.
954 * r could be a. This function calls down to the BN_GF2m_mod_sqrt_arr
955 * implementation; this wrapper function is only provided for convenience;
956 * for best performance, use the BN_GF2m_mod_sqrt_arr function.
958 int BN_GF2m_mod_sqrt(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
, BN_CTX
*ctx
)
961 const int max
= BN_num_bits(p
) + 1;
965 if ((arr
= OPENSSL_malloc(sizeof(*arr
) * max
)) == NULL
)
967 ret
= BN_GF2m_poly2arr(p
, arr
, max
);
968 if (!ret
|| ret
> max
) {
969 BNerr(BN_F_BN_GF2M_MOD_SQRT
, BN_R_INVALID_LENGTH
);
972 ret
= BN_GF2m_mod_sqrt_arr(r
, a
, arr
, ctx
);
980 * Find r such that r^2 + r = a mod p. r could be a. If no r exists returns
981 * 0. Uses algorithms A.4.7 and A.4.6 from IEEE P1363.
983 int BN_GF2m_mod_solve_quad_arr(BIGNUM
*r
, const BIGNUM
*a_
, const int p
[],
986 int ret
= 0, count
= 0, j
;
987 BIGNUM
*a
, *z
, *rho
, *w
, *w2
, *tmp
;
992 /* reduction mod 1 => return 0 */
1000 w
= BN_CTX_get(ctx
);
1004 if (!BN_GF2m_mod_arr(a
, a_
, p
))
1007 if (BN_is_zero(a
)) {
1013 if (p
[0] & 0x1) { /* m is odd */
1014 /* compute half-trace of a */
1017 for (j
= 1; j
<= (p
[0] - 1) / 2; j
++) {
1018 if (!BN_GF2m_mod_sqr_arr(z
, z
, p
, ctx
))
1020 if (!BN_GF2m_mod_sqr_arr(z
, z
, p
, ctx
))
1022 if (!BN_GF2m_add(z
, z
, a
))
1026 } else { /* m is even */
1028 rho
= BN_CTX_get(ctx
);
1029 w2
= BN_CTX_get(ctx
);
1030 tmp
= BN_CTX_get(ctx
);
1034 if (!BN_priv_rand(rho
, p
[0], BN_RAND_TOP_ONE
, BN_RAND_BOTTOM_ANY
))
1036 if (!BN_GF2m_mod_arr(rho
, rho
, p
))
1039 if (!BN_copy(w
, rho
))
1041 for (j
= 1; j
<= p
[0] - 1; j
++) {
1042 if (!BN_GF2m_mod_sqr_arr(z
, z
, p
, ctx
))
1044 if (!BN_GF2m_mod_sqr_arr(w2
, w
, p
, ctx
))
1046 if (!BN_GF2m_mod_mul_arr(tmp
, w2
, a
, p
, ctx
))
1048 if (!BN_GF2m_add(z
, z
, tmp
))
1050 if (!BN_GF2m_add(w
, w2
, rho
))
1054 } while (BN_is_zero(w
) && (count
< MAX_ITERATIONS
));
1055 if (BN_is_zero(w
)) {
1056 BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR
, BN_R_TOO_MANY_ITERATIONS
);
1061 if (!BN_GF2m_mod_sqr_arr(w
, z
, p
, ctx
))
1063 if (!BN_GF2m_add(w
, z
, w
))
1065 if (BN_GF2m_cmp(w
, a
)) {
1066 BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD_ARR
, BN_R_NO_SOLUTION
);
1082 * Find r such that r^2 + r = a mod p. r could be a. If no r exists returns
1083 * 0. This function calls down to the BN_GF2m_mod_solve_quad_arr
1084 * implementation; this wrapper function is only provided for convenience;
1085 * for best performance, use the BN_GF2m_mod_solve_quad_arr function.
1087 int BN_GF2m_mod_solve_quad(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
,
1091 const int max
= BN_num_bits(p
) + 1;
1095 if ((arr
= OPENSSL_malloc(sizeof(*arr
) * max
)) == NULL
)
1097 ret
= BN_GF2m_poly2arr(p
, arr
, max
);
1098 if (!ret
|| ret
> max
) {
1099 BNerr(BN_F_BN_GF2M_MOD_SOLVE_QUAD
, BN_R_INVALID_LENGTH
);
1102 ret
= BN_GF2m_mod_solve_quad_arr(r
, a
, arr
, ctx
);
1110 * Convert the bit-string representation of a polynomial ( \sum_{i=0}^n a_i *
1111 * x^i) into an array of integers corresponding to the bits with non-zero
1112 * coefficient. Array is terminated with -1. Up to max elements of the array
1113 * will be filled. Return value is total number of array elements that would
1114 * be filled if array was large enough.
1116 int BN_GF2m_poly2arr(const BIGNUM
*a
, int p
[], int max
)
1124 for (i
= a
->top
- 1; i
>= 0; i
--) {
1126 /* skip word if a->d[i] == 0 */
1129 for (j
= BN_BITS2
- 1; j
>= 0; j
--) {
1130 if (a
->d
[i
] & mask
) {
1132 p
[k
] = BN_BITS2
* i
+ j
;
1148 * Convert the coefficient array representation of a polynomial to a
1149 * bit-string. The array must be terminated by -1.
1151 int BN_GF2m_arr2poly(const int p
[], BIGNUM
*a
)
1157 for (i
= 0; p
[i
] != -1; i
++) {
1158 if (BN_set_bit(a
, p
[i
]) == 0)