1 /* crypto/ec/ec2_smpl.c */
2 /* ====================================================================
3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
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.
9 * The ECC Code is licensed pursuant to the OpenSSL open source
10 * license provided below.
12 * The software is originally written by Sheueling Chang Shantz and
13 * Douglas Stebila of Sun Microsystems Laboratories.
16 /* ====================================================================
17 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
23 * 1. Redistributions of source code must retain the above copyright
24 * notice, this list of conditions and the following disclaimer.
26 * 2. Redistributions in binary form must reproduce the above copyright
27 * notice, this list of conditions and the following disclaimer in
28 * the documentation and/or other materials provided with the
31 * 3. All advertising materials mentioning features or use of this
32 * software must display the following acknowledgment:
33 * "This product includes software developed by the OpenSSL Project
34 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
36 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
37 * endorse or promote products derived from this software without
38 * prior written permission. For written permission, please contact
39 * openssl-core@openssl.org.
41 * 5. Products derived from this software may not be called "OpenSSL"
42 * nor may "OpenSSL" appear in their names without prior written
43 * permission of the OpenSSL Project.
45 * 6. Redistributions of any form whatsoever must retain the following
47 * "This product includes software developed by the OpenSSL Project
48 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
50 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
51 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
52 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
53 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
54 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
55 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
56 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
57 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
59 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
60 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
61 * OF THE POSSIBILITY OF SUCH DAMAGE.
62 * ====================================================================
64 * This product includes cryptographic software written by Eric Young
65 * (eay@cryptsoft.com). This product includes software written by Tim
66 * Hudson (tjh@cryptsoft.com).
70 #define OPENSSL_FIPSAPI
72 #include <openssl/err.h>
76 #ifndef OPENSSL_NO_EC2M
79 const EC_METHOD
*EC_GF2m_simple_method(void)
81 static const EC_METHOD ret
= {
83 NID_X9_62_characteristic_two_field
,
84 ec_GF2m_simple_group_init
,
85 ec_GF2m_simple_group_finish
,
86 ec_GF2m_simple_group_clear_finish
,
87 ec_GF2m_simple_group_copy
,
88 ec_GF2m_simple_group_set_curve
,
89 ec_GF2m_simple_group_get_curve
,
90 ec_GF2m_simple_group_get_degree
,
91 ec_GF2m_simple_group_check_discriminant
,
92 ec_GF2m_simple_point_init
,
93 ec_GF2m_simple_point_finish
,
94 ec_GF2m_simple_point_clear_finish
,
95 ec_GF2m_simple_point_copy
,
96 ec_GF2m_simple_point_set_to_infinity
,
97 0 /* set_Jprojective_coordinates_GFp */,
98 0 /* get_Jprojective_coordinates_GFp */,
99 ec_GF2m_simple_point_set_affine_coordinates
,
100 ec_GF2m_simple_point_get_affine_coordinates
,
104 ec_GF2m_simple_invert
,
105 ec_GF2m_simple_is_at_infinity
,
106 ec_GF2m_simple_is_on_curve
,
108 ec_GF2m_simple_make_affine
,
109 ec_GF2m_simple_points_make_affine
,
111 /* the following three method functions are defined in ec2_mult.c */
113 ec_GF2m_precompute_mult
,
114 ec_GF2m_have_precompute_mult
,
116 ec_GF2m_simple_field_mul
,
117 ec_GF2m_simple_field_sqr
,
118 ec_GF2m_simple_field_div
,
119 0 /* field_encode */,
120 0 /* field_decode */,
121 0 /* field_set_to_one */ };
127 /* Initialize a GF(2^m)-based EC_GROUP structure.
128 * Note that all other members are handled by EC_GROUP_new.
130 int ec_GF2m_simple_group_init(EC_GROUP
*group
)
132 BN_init(&group
->field
);
139 /* Free a GF(2^m)-based EC_GROUP structure.
140 * Note that all other members are handled by EC_GROUP_free.
142 void ec_GF2m_simple_group_finish(EC_GROUP
*group
)
144 BN_free(&group
->field
);
150 /* Clear and free a GF(2^m)-based EC_GROUP structure.
151 * Note that all other members are handled by EC_GROUP_clear_free.
153 void ec_GF2m_simple_group_clear_finish(EC_GROUP
*group
)
155 BN_clear_free(&group
->field
);
156 BN_clear_free(&group
->a
);
157 BN_clear_free(&group
->b
);
167 /* Copy a GF(2^m)-based EC_GROUP structure.
168 * Note that all other members are handled by EC_GROUP_copy.
170 int ec_GF2m_simple_group_copy(EC_GROUP
*dest
, const EC_GROUP
*src
)
173 if (!BN_copy(&dest
->field
, &src
->field
)) return 0;
174 if (!BN_copy(&dest
->a
, &src
->a
)) return 0;
175 if (!BN_copy(&dest
->b
, &src
->b
)) return 0;
176 dest
->poly
[0] = src
->poly
[0];
177 dest
->poly
[1] = src
->poly
[1];
178 dest
->poly
[2] = src
->poly
[2];
179 dest
->poly
[3] = src
->poly
[3];
180 dest
->poly
[4] = src
->poly
[4];
181 dest
->poly
[5] = src
->poly
[5];
182 if (bn_wexpand(&dest
->a
, (int)(dest
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) return 0;
183 if (bn_wexpand(&dest
->b
, (int)(dest
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) return 0;
184 for (i
= dest
->a
.top
; i
< dest
->a
.dmax
; i
++) dest
->a
.d
[i
] = 0;
185 for (i
= dest
->b
.top
; i
< dest
->b
.dmax
; i
++) dest
->b
.d
[i
] = 0;
190 /* Set the curve parameters of an EC_GROUP structure. */
191 int ec_GF2m_simple_group_set_curve(EC_GROUP
*group
,
192 const BIGNUM
*p
, const BIGNUM
*a
, const BIGNUM
*b
, BN_CTX
*ctx
)
197 if (!BN_copy(&group
->field
, p
)) goto err
;
198 i
= BN_GF2m_poly2arr(&group
->field
, group
->poly
, 6) - 1;
199 if ((i
!= 5) && (i
!= 3))
201 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE
, EC_R_UNSUPPORTED_FIELD
);
206 if (!BN_GF2m_mod_arr(&group
->a
, a
, group
->poly
)) goto err
;
207 if(bn_wexpand(&group
->a
, (int)(group
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) goto err
;
208 for (i
= group
->a
.top
; i
< group
->a
.dmax
; i
++) group
->a
.d
[i
] = 0;
211 if (!BN_GF2m_mod_arr(&group
->b
, b
, group
->poly
)) goto err
;
212 if(bn_wexpand(&group
->b
, (int)(group
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) goto err
;
213 for (i
= group
->b
.top
; i
< group
->b
.dmax
; i
++) group
->b
.d
[i
] = 0;
221 /* Get the curve parameters of an EC_GROUP structure.
222 * If p, a, or b are NULL then there values will not be set but the method will return with success.
224 int ec_GF2m_simple_group_get_curve(const EC_GROUP
*group
, BIGNUM
*p
, BIGNUM
*a
, BIGNUM
*b
, BN_CTX
*ctx
)
230 if (!BN_copy(p
, &group
->field
)) return 0;
235 if (!BN_copy(a
, &group
->a
)) goto err
;
240 if (!BN_copy(b
, &group
->b
)) goto err
;
250 /* Gets the degree of the field. For a curve over GF(2^m) this is the value m. */
251 int ec_GF2m_simple_group_get_degree(const EC_GROUP
*group
)
253 return BN_num_bits(&group
->field
)-1;
257 /* Checks the discriminant of the curve.
258 * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
260 int ec_GF2m_simple_group_check_discriminant(const EC_GROUP
*group
, BN_CTX
*ctx
)
264 BN_CTX
*new_ctx
= NULL
;
268 ctx
= new_ctx
= BN_CTX_new();
271 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT
, ERR_R_MALLOC_FAILURE
);
277 if (b
== NULL
) goto err
;
279 if (!BN_GF2m_mod_arr(b
, &group
->b
, group
->poly
)) goto err
;
281 /* check the discriminant:
282 * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
284 if (BN_is_zero(b
)) goto err
;
292 BN_CTX_free(new_ctx
);
297 /* Initializes an EC_POINT. */
298 int ec_GF2m_simple_point_init(EC_POINT
*point
)
307 /* Frees an EC_POINT. */
308 void ec_GF2m_simple_point_finish(EC_POINT
*point
)
316 /* Clears and frees an EC_POINT. */
317 void ec_GF2m_simple_point_clear_finish(EC_POINT
*point
)
319 BN_clear_free(&point
->X
);
320 BN_clear_free(&point
->Y
);
321 BN_clear_free(&point
->Z
);
326 /* Copy the contents of one EC_POINT into another. Assumes dest is initialized. */
327 int ec_GF2m_simple_point_copy(EC_POINT
*dest
, const EC_POINT
*src
)
329 if (!BN_copy(&dest
->X
, &src
->X
)) return 0;
330 if (!BN_copy(&dest
->Y
, &src
->Y
)) return 0;
331 if (!BN_copy(&dest
->Z
, &src
->Z
)) return 0;
332 dest
->Z_is_one
= src
->Z_is_one
;
338 /* Set an EC_POINT to the point at infinity.
339 * A point at infinity is represented by having Z=0.
341 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP
*group
, EC_POINT
*point
)
349 /* Set the coordinates of an EC_POINT using affine coordinates.
350 * Note that the simple implementation only uses affine coordinates.
352 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP
*group
, EC_POINT
*point
,
353 const BIGNUM
*x
, const BIGNUM
*y
, BN_CTX
*ctx
)
356 if (x
== NULL
|| y
== NULL
)
358 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES
, ERR_R_PASSED_NULL_PARAMETER
);
362 if (!BN_copy(&point
->X
, x
)) goto err
;
363 BN_set_negative(&point
->X
, 0);
364 if (!BN_copy(&point
->Y
, y
)) goto err
;
365 BN_set_negative(&point
->Y
, 0);
366 if (!BN_copy(&point
->Z
, BN_value_one())) goto err
;
367 BN_set_negative(&point
->Z
, 0);
376 /* Gets the affine coordinates of an EC_POINT.
377 * Note that the simple implementation only uses affine coordinates.
379 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP
*group
, const EC_POINT
*point
,
380 BIGNUM
*x
, BIGNUM
*y
, BN_CTX
*ctx
)
384 if (EC_POINT_is_at_infinity(group
, point
))
386 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES
, EC_R_POINT_AT_INFINITY
);
390 if (BN_cmp(&point
->Z
, BN_value_one()))
392 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES
, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED
);
397 if (!BN_copy(x
, &point
->X
)) goto err
;
398 BN_set_negative(x
, 0);
402 if (!BN_copy(y
, &point
->Y
)) goto err
;
403 BN_set_negative(y
, 0);
411 /* Computes a + b and stores the result in r. r could be a or b, a could be b.
412 * Uses algorithm A.10.2 of IEEE P1363.
414 int ec_GF2m_simple_add(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
, const EC_POINT
*b
, BN_CTX
*ctx
)
416 BN_CTX
*new_ctx
= NULL
;
417 BIGNUM
*x0
, *y0
, *x1
, *y1
, *x2
, *y2
, *s
, *t
;
420 if (EC_POINT_is_at_infinity(group
, a
))
422 if (!EC_POINT_copy(r
, b
)) return 0;
426 if (EC_POINT_is_at_infinity(group
, b
))
428 if (!EC_POINT_copy(r
, a
)) return 0;
434 ctx
= new_ctx
= BN_CTX_new();
440 x0
= BN_CTX_get(ctx
);
441 y0
= BN_CTX_get(ctx
);
442 x1
= BN_CTX_get(ctx
);
443 y1
= BN_CTX_get(ctx
);
444 x2
= BN_CTX_get(ctx
);
445 y2
= BN_CTX_get(ctx
);
448 if (t
== NULL
) goto err
;
452 if (!BN_copy(x0
, &a
->X
)) goto err
;
453 if (!BN_copy(y0
, &a
->Y
)) goto err
;
457 if (!EC_POINT_get_affine_coordinates_GF2m(group
, a
, x0
, y0
, ctx
)) goto err
;
461 if (!BN_copy(x1
, &b
->X
)) goto err
;
462 if (!BN_copy(y1
, &b
->Y
)) goto err
;
466 if (!EC_POINT_get_affine_coordinates_GF2m(group
, b
, x1
, y1
, ctx
)) goto err
;
470 if (BN_GF2m_cmp(x0
, x1
))
472 if (!BN_GF2m_add(t
, x0
, x1
)) goto err
;
473 if (!BN_GF2m_add(s
, y0
, y1
)) goto err
;
474 if (!group
->meth
->field_div(group
, s
, s
, t
, ctx
)) goto err
;
475 if (!group
->meth
->field_sqr(group
, x2
, s
, ctx
)) goto err
;
476 if (!BN_GF2m_add(x2
, x2
, &group
->a
)) goto err
;
477 if (!BN_GF2m_add(x2
, x2
, s
)) goto err
;
478 if (!BN_GF2m_add(x2
, x2
, t
)) goto err
;
482 if (BN_GF2m_cmp(y0
, y1
) || BN_is_zero(x1
))
484 if (!EC_POINT_set_to_infinity(group
, r
)) goto err
;
488 if (!group
->meth
->field_div(group
, s
, y1
, x1
, ctx
)) goto err
;
489 if (!BN_GF2m_add(s
, s
, x1
)) goto err
;
491 if (!group
->meth
->field_sqr(group
, x2
, s
, ctx
)) goto err
;
492 if (!BN_GF2m_add(x2
, x2
, s
)) goto err
;
493 if (!BN_GF2m_add(x2
, x2
, &group
->a
)) goto err
;
496 if (!BN_GF2m_add(y2
, x1
, x2
)) goto err
;
497 if (!group
->meth
->field_mul(group
, y2
, y2
, s
, ctx
)) goto err
;
498 if (!BN_GF2m_add(y2
, y2
, x2
)) goto err
;
499 if (!BN_GF2m_add(y2
, y2
, y1
)) goto err
;
501 if (!EC_POINT_set_affine_coordinates_GF2m(group
, r
, x2
, y2
, ctx
)) goto err
;
508 BN_CTX_free(new_ctx
);
513 /* Computes 2 * a and stores the result in r. r could be a.
514 * Uses algorithm A.10.2 of IEEE P1363.
516 int ec_GF2m_simple_dbl(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
, BN_CTX
*ctx
)
518 return ec_GF2m_simple_add(group
, r
, a
, a
, ctx
);
522 int ec_GF2m_simple_invert(const EC_GROUP
*group
, EC_POINT
*point
, BN_CTX
*ctx
)
524 if (EC_POINT_is_at_infinity(group
, point
) || BN_is_zero(&point
->Y
))
525 /* point is its own inverse */
528 if (!EC_POINT_make_affine(group
, point
, ctx
)) return 0;
529 return BN_GF2m_add(&point
->Y
, &point
->X
, &point
->Y
);
533 /* Indicates whether the given point is the point at infinity. */
534 int ec_GF2m_simple_is_at_infinity(const EC_GROUP
*group
, const EC_POINT
*point
)
536 return BN_is_zero(&point
->Z
);
540 /* Determines whether the given EC_POINT is an actual point on the curve defined
541 * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
542 * y^2 + x*y = x^3 + a*x^2 + b.
544 int ec_GF2m_simple_is_on_curve(const EC_GROUP
*group
, const EC_POINT
*point
, BN_CTX
*ctx
)
547 BN_CTX
*new_ctx
= NULL
;
549 int (*field_mul
)(const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, const BIGNUM
*, BN_CTX
*);
550 int (*field_sqr
)(const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
552 if (EC_POINT_is_at_infinity(group
, point
))
555 field_mul
= group
->meth
->field_mul
;
556 field_sqr
= group
->meth
->field_sqr
;
558 /* only support affine coordinates */
559 if (!point
->Z_is_one
) return -1;
563 ctx
= new_ctx
= BN_CTX_new();
569 y2
= BN_CTX_get(ctx
);
570 lh
= BN_CTX_get(ctx
);
571 if (lh
== NULL
) goto err
;
573 /* We have a curve defined by a Weierstrass equation
574 * y^2 + x*y = x^3 + a*x^2 + b.
575 * <=> x^3 + a*x^2 + x*y + b + y^2 = 0
576 * <=> ((x + a) * x + y ) * x + b + y^2 = 0
578 if (!BN_GF2m_add(lh
, &point
->X
, &group
->a
)) goto err
;
579 if (!field_mul(group
, lh
, lh
, &point
->X
, ctx
)) goto err
;
580 if (!BN_GF2m_add(lh
, lh
, &point
->Y
)) goto err
;
581 if (!field_mul(group
, lh
, lh
, &point
->X
, ctx
)) goto err
;
582 if (!BN_GF2m_add(lh
, lh
, &group
->b
)) goto err
;
583 if (!field_sqr(group
, y2
, &point
->Y
, ctx
)) goto err
;
584 if (!BN_GF2m_add(lh
, lh
, y2
)) goto err
;
585 ret
= BN_is_zero(lh
);
587 if (ctx
) BN_CTX_end(ctx
);
588 if (new_ctx
) BN_CTX_free(new_ctx
);
593 /* Indicates whether two points are equal.
596 * 0 equal (in affine coordinates)
599 int ec_GF2m_simple_cmp(const EC_GROUP
*group
, const EC_POINT
*a
, const EC_POINT
*b
, BN_CTX
*ctx
)
601 BIGNUM
*aX
, *aY
, *bX
, *bY
;
602 BN_CTX
*new_ctx
= NULL
;
605 if (EC_POINT_is_at_infinity(group
, a
))
607 return EC_POINT_is_at_infinity(group
, b
) ? 0 : 1;
610 if (EC_POINT_is_at_infinity(group
, b
))
613 if (a
->Z_is_one
&& b
->Z_is_one
)
615 return ((BN_cmp(&a
->X
, &b
->X
) == 0) && BN_cmp(&a
->Y
, &b
->Y
) == 0) ? 0 : 1;
620 ctx
= new_ctx
= BN_CTX_new();
626 aX
= BN_CTX_get(ctx
);
627 aY
= BN_CTX_get(ctx
);
628 bX
= BN_CTX_get(ctx
);
629 bY
= BN_CTX_get(ctx
);
630 if (bY
== NULL
) goto err
;
632 if (!EC_POINT_get_affine_coordinates_GF2m(group
, a
, aX
, aY
, ctx
)) goto err
;
633 if (!EC_POINT_get_affine_coordinates_GF2m(group
, b
, bX
, bY
, ctx
)) goto err
;
634 ret
= ((BN_cmp(aX
, bX
) == 0) && BN_cmp(aY
, bY
) == 0) ? 0 : 1;
637 if (ctx
) BN_CTX_end(ctx
);
638 if (new_ctx
) BN_CTX_free(new_ctx
);
643 /* Forces the given EC_POINT to internally use affine coordinates. */
644 int ec_GF2m_simple_make_affine(const EC_GROUP
*group
, EC_POINT
*point
, BN_CTX
*ctx
)
646 BN_CTX
*new_ctx
= NULL
;
650 if (point
->Z_is_one
|| EC_POINT_is_at_infinity(group
, point
))
655 ctx
= new_ctx
= BN_CTX_new();
663 if (y
== NULL
) goto err
;
665 if (!EC_POINT_get_affine_coordinates_GF2m(group
, point
, x
, y
, ctx
)) goto err
;
666 if (!BN_copy(&point
->X
, x
)) goto err
;
667 if (!BN_copy(&point
->Y
, y
)) goto err
;
668 if (!BN_one(&point
->Z
)) goto err
;
673 if (ctx
) BN_CTX_end(ctx
);
674 if (new_ctx
) BN_CTX_free(new_ctx
);
679 /* Forces each of the EC_POINTs in the given array to use affine coordinates. */
680 int ec_GF2m_simple_points_make_affine(const EC_GROUP
*group
, size_t num
, EC_POINT
*points
[], BN_CTX
*ctx
)
684 for (i
= 0; i
< num
; i
++)
686 if (!group
->meth
->make_affine(group
, points
[i
], ctx
)) return 0;
693 /* Wrapper to simple binary polynomial field multiplication implementation. */
694 int ec_GF2m_simple_field_mul(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, BN_CTX
*ctx
)
696 return BN_GF2m_mod_mul_arr(r
, a
, b
, group
->poly
, ctx
);
700 /* Wrapper to simple binary polynomial field squaring implementation. */
701 int ec_GF2m_simple_field_sqr(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
, BN_CTX
*ctx
)
703 return BN_GF2m_mod_sqr_arr(r
, a
, group
->poly
, ctx
);
707 /* Wrapper to simple binary polynomial field division implementation. */
708 int ec_GF2m_simple_field_div(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, BN_CTX
*ctx
)
710 return BN_GF2m_mod_div(r
, a
, b
, &group
->field
, ctx
);