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 #include <openssl/err.h>
74 #ifndef OPENSSL_NO_EC2M
77 #include <openssl/fips.h>
81 const EC_METHOD
*EC_GF2m_simple_method(void)
83 static const EC_METHOD ret
= {
85 NID_X9_62_characteristic_two_field
,
86 ec_GF2m_simple_group_init
,
87 ec_GF2m_simple_group_finish
,
88 ec_GF2m_simple_group_clear_finish
,
89 ec_GF2m_simple_group_copy
,
90 ec_GF2m_simple_group_set_curve
,
91 ec_GF2m_simple_group_get_curve
,
92 ec_GF2m_simple_group_get_degree
,
93 ec_GF2m_simple_group_check_discriminant
,
94 ec_GF2m_simple_point_init
,
95 ec_GF2m_simple_point_finish
,
96 ec_GF2m_simple_point_clear_finish
,
97 ec_GF2m_simple_point_copy
,
98 ec_GF2m_simple_point_set_to_infinity
,
99 0 /* set_Jprojective_coordinates_GFp */,
100 0 /* get_Jprojective_coordinates_GFp */,
101 ec_GF2m_simple_point_set_affine_coordinates
,
102 ec_GF2m_simple_point_get_affine_coordinates
,
106 ec_GF2m_simple_invert
,
107 ec_GF2m_simple_is_at_infinity
,
108 ec_GF2m_simple_is_on_curve
,
110 ec_GF2m_simple_make_affine
,
111 ec_GF2m_simple_points_make_affine
,
113 /* the following three method functions are defined in ec2_mult.c */
115 ec_GF2m_precompute_mult
,
116 ec_GF2m_have_precompute_mult
,
118 ec_GF2m_simple_field_mul
,
119 ec_GF2m_simple_field_sqr
,
120 ec_GF2m_simple_field_div
,
121 0 /* field_encode */,
122 0 /* field_decode */,
123 0 /* field_set_to_one */ };
127 return fips_ec_gf2m_simple_method();
134 /* Initialize a GF(2^m)-based EC_GROUP structure.
135 * Note that all other members are handled by EC_GROUP_new.
137 int ec_GF2m_simple_group_init(EC_GROUP
*group
)
139 BN_init(&group
->field
);
146 /* Free a GF(2^m)-based EC_GROUP structure.
147 * Note that all other members are handled by EC_GROUP_free.
149 void ec_GF2m_simple_group_finish(EC_GROUP
*group
)
151 BN_free(&group
->field
);
157 /* Clear and free a GF(2^m)-based EC_GROUP structure.
158 * Note that all other members are handled by EC_GROUP_clear_free.
160 void ec_GF2m_simple_group_clear_finish(EC_GROUP
*group
)
162 BN_clear_free(&group
->field
);
163 BN_clear_free(&group
->a
);
164 BN_clear_free(&group
->b
);
174 /* Copy a GF(2^m)-based EC_GROUP structure.
175 * Note that all other members are handled by EC_GROUP_copy.
177 int ec_GF2m_simple_group_copy(EC_GROUP
*dest
, const EC_GROUP
*src
)
180 if (!BN_copy(&dest
->field
, &src
->field
)) return 0;
181 if (!BN_copy(&dest
->a
, &src
->a
)) return 0;
182 if (!BN_copy(&dest
->b
, &src
->b
)) return 0;
183 dest
->poly
[0] = src
->poly
[0];
184 dest
->poly
[1] = src
->poly
[1];
185 dest
->poly
[2] = src
->poly
[2];
186 dest
->poly
[3] = src
->poly
[3];
187 dest
->poly
[4] = src
->poly
[4];
188 dest
->poly
[5] = src
->poly
[5];
189 if (bn_wexpand(&dest
->a
, (int)(dest
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) return 0;
190 if (bn_wexpand(&dest
->b
, (int)(dest
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) return 0;
191 for (i
= dest
->a
.top
; i
< dest
->a
.dmax
; i
++) dest
->a
.d
[i
] = 0;
192 for (i
= dest
->b
.top
; i
< dest
->b
.dmax
; i
++) dest
->b
.d
[i
] = 0;
197 /* Set the curve parameters of an EC_GROUP structure. */
198 int ec_GF2m_simple_group_set_curve(EC_GROUP
*group
,
199 const BIGNUM
*p
, const BIGNUM
*a
, const BIGNUM
*b
, BN_CTX
*ctx
)
204 if (!BN_copy(&group
->field
, p
)) goto err
;
205 i
= BN_GF2m_poly2arr(&group
->field
, group
->poly
, 6) - 1;
206 if ((i
!= 5) && (i
!= 3))
208 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE
, EC_R_UNSUPPORTED_FIELD
);
213 if (!BN_GF2m_mod_arr(&group
->a
, a
, group
->poly
)) goto err
;
214 if(bn_wexpand(&group
->a
, (int)(group
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) goto err
;
215 for (i
= group
->a
.top
; i
< group
->a
.dmax
; i
++) group
->a
.d
[i
] = 0;
218 if (!BN_GF2m_mod_arr(&group
->b
, b
, group
->poly
)) goto err
;
219 if(bn_wexpand(&group
->b
, (int)(group
->poly
[0] + BN_BITS2
- 1) / BN_BITS2
) == NULL
) goto err
;
220 for (i
= group
->b
.top
; i
< group
->b
.dmax
; i
++) group
->b
.d
[i
] = 0;
228 /* Get the curve parameters of an EC_GROUP structure.
229 * If p, a, or b are NULL then there values will not be set but the method will return with success.
231 int ec_GF2m_simple_group_get_curve(const EC_GROUP
*group
, BIGNUM
*p
, BIGNUM
*a
, BIGNUM
*b
, BN_CTX
*ctx
)
237 if (!BN_copy(p
, &group
->field
)) return 0;
242 if (!BN_copy(a
, &group
->a
)) goto err
;
247 if (!BN_copy(b
, &group
->b
)) goto err
;
257 /* Gets the degree of the field. For a curve over GF(2^m) this is the value m. */
258 int ec_GF2m_simple_group_get_degree(const EC_GROUP
*group
)
260 return BN_num_bits(&group
->field
)-1;
264 /* Checks the discriminant of the curve.
265 * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
267 int ec_GF2m_simple_group_check_discriminant(const EC_GROUP
*group
, BN_CTX
*ctx
)
271 BN_CTX
*new_ctx
= NULL
;
275 ctx
= new_ctx
= BN_CTX_new();
278 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT
, ERR_R_MALLOC_FAILURE
);
284 if (b
== NULL
) goto err
;
286 if (!BN_GF2m_mod_arr(b
, &group
->b
, group
->poly
)) goto err
;
288 /* check the discriminant:
289 * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p)
291 if (BN_is_zero(b
)) goto err
;
299 BN_CTX_free(new_ctx
);
304 /* Initializes an EC_POINT. */
305 int ec_GF2m_simple_point_init(EC_POINT
*point
)
314 /* Frees an EC_POINT. */
315 void ec_GF2m_simple_point_finish(EC_POINT
*point
)
323 /* Clears and frees an EC_POINT. */
324 void ec_GF2m_simple_point_clear_finish(EC_POINT
*point
)
326 BN_clear_free(&point
->X
);
327 BN_clear_free(&point
->Y
);
328 BN_clear_free(&point
->Z
);
333 /* Copy the contents of one EC_POINT into another. Assumes dest is initialized. */
334 int ec_GF2m_simple_point_copy(EC_POINT
*dest
, const EC_POINT
*src
)
336 if (!BN_copy(&dest
->X
, &src
->X
)) return 0;
337 if (!BN_copy(&dest
->Y
, &src
->Y
)) return 0;
338 if (!BN_copy(&dest
->Z
, &src
->Z
)) return 0;
339 dest
->Z_is_one
= src
->Z_is_one
;
345 /* Set an EC_POINT to the point at infinity.
346 * A point at infinity is represented by having Z=0.
348 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP
*group
, EC_POINT
*point
)
356 /* Set the coordinates of an EC_POINT using affine coordinates.
357 * Note that the simple implementation only uses affine coordinates.
359 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP
*group
, EC_POINT
*point
,
360 const BIGNUM
*x
, const BIGNUM
*y
, BN_CTX
*ctx
)
363 if (x
== NULL
|| y
== NULL
)
365 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES
, ERR_R_PASSED_NULL_PARAMETER
);
369 if (!BN_copy(&point
->X
, x
)) goto err
;
370 BN_set_negative(&point
->X
, 0);
371 if (!BN_copy(&point
->Y
, y
)) goto err
;
372 BN_set_negative(&point
->Y
, 0);
373 if (!BN_copy(&point
->Z
, BN_value_one())) goto err
;
374 BN_set_negative(&point
->Z
, 0);
383 /* Gets the affine coordinates of an EC_POINT.
384 * Note that the simple implementation only uses affine coordinates.
386 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP
*group
, const EC_POINT
*point
,
387 BIGNUM
*x
, BIGNUM
*y
, BN_CTX
*ctx
)
391 if (EC_POINT_is_at_infinity(group
, point
))
393 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES
, EC_R_POINT_AT_INFINITY
);
397 if (BN_cmp(&point
->Z
, BN_value_one()))
399 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES
, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED
);
404 if (!BN_copy(x
, &point
->X
)) goto err
;
405 BN_set_negative(x
, 0);
409 if (!BN_copy(y
, &point
->Y
)) goto err
;
410 BN_set_negative(y
, 0);
418 /* Computes a + b and stores the result in r. r could be a or b, a could be b.
419 * Uses algorithm A.10.2 of IEEE P1363.
421 int ec_GF2m_simple_add(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
, const EC_POINT
*b
, BN_CTX
*ctx
)
423 BN_CTX
*new_ctx
= NULL
;
424 BIGNUM
*x0
, *y0
, *x1
, *y1
, *x2
, *y2
, *s
, *t
;
427 if (EC_POINT_is_at_infinity(group
, a
))
429 if (!EC_POINT_copy(r
, b
)) return 0;
433 if (EC_POINT_is_at_infinity(group
, b
))
435 if (!EC_POINT_copy(r
, a
)) return 0;
441 ctx
= new_ctx
= BN_CTX_new();
447 x0
= BN_CTX_get(ctx
);
448 y0
= BN_CTX_get(ctx
);
449 x1
= BN_CTX_get(ctx
);
450 y1
= BN_CTX_get(ctx
);
451 x2
= BN_CTX_get(ctx
);
452 y2
= BN_CTX_get(ctx
);
455 if (t
== NULL
) goto err
;
459 if (!BN_copy(x0
, &a
->X
)) goto err
;
460 if (!BN_copy(y0
, &a
->Y
)) goto err
;
464 if (!EC_POINT_get_affine_coordinates_GF2m(group
, a
, x0
, y0
, ctx
)) goto err
;
468 if (!BN_copy(x1
, &b
->X
)) goto err
;
469 if (!BN_copy(y1
, &b
->Y
)) goto err
;
473 if (!EC_POINT_get_affine_coordinates_GF2m(group
, b
, x1
, y1
, ctx
)) goto err
;
477 if (BN_GF2m_cmp(x0
, x1
))
479 if (!BN_GF2m_add(t
, x0
, x1
)) goto err
;
480 if (!BN_GF2m_add(s
, y0
, y1
)) goto err
;
481 if (!group
->meth
->field_div(group
, s
, s
, t
, ctx
)) goto err
;
482 if (!group
->meth
->field_sqr(group
, x2
, s
, ctx
)) goto err
;
483 if (!BN_GF2m_add(x2
, x2
, &group
->a
)) goto err
;
484 if (!BN_GF2m_add(x2
, x2
, s
)) goto err
;
485 if (!BN_GF2m_add(x2
, x2
, t
)) goto err
;
489 if (BN_GF2m_cmp(y0
, y1
) || BN_is_zero(x1
))
491 if (!EC_POINT_set_to_infinity(group
, r
)) goto err
;
495 if (!group
->meth
->field_div(group
, s
, y1
, x1
, ctx
)) goto err
;
496 if (!BN_GF2m_add(s
, s
, x1
)) goto err
;
498 if (!group
->meth
->field_sqr(group
, x2
, s
, ctx
)) goto err
;
499 if (!BN_GF2m_add(x2
, x2
, s
)) goto err
;
500 if (!BN_GF2m_add(x2
, x2
, &group
->a
)) goto err
;
503 if (!BN_GF2m_add(y2
, x1
, x2
)) goto err
;
504 if (!group
->meth
->field_mul(group
, y2
, y2
, s
, ctx
)) goto err
;
505 if (!BN_GF2m_add(y2
, y2
, x2
)) goto err
;
506 if (!BN_GF2m_add(y2
, y2
, y1
)) goto err
;
508 if (!EC_POINT_set_affine_coordinates_GF2m(group
, r
, x2
, y2
, ctx
)) goto err
;
515 BN_CTX_free(new_ctx
);
520 /* Computes 2 * a and stores the result in r. r could be a.
521 * Uses algorithm A.10.2 of IEEE P1363.
523 int ec_GF2m_simple_dbl(const EC_GROUP
*group
, EC_POINT
*r
, const EC_POINT
*a
, BN_CTX
*ctx
)
525 return ec_GF2m_simple_add(group
, r
, a
, a
, ctx
);
529 int ec_GF2m_simple_invert(const EC_GROUP
*group
, EC_POINT
*point
, BN_CTX
*ctx
)
531 if (EC_POINT_is_at_infinity(group
, point
) || BN_is_zero(&point
->Y
))
532 /* point is its own inverse */
535 if (!EC_POINT_make_affine(group
, point
, ctx
)) return 0;
536 return BN_GF2m_add(&point
->Y
, &point
->X
, &point
->Y
);
540 /* Indicates whether the given point is the point at infinity. */
541 int ec_GF2m_simple_is_at_infinity(const EC_GROUP
*group
, const EC_POINT
*point
)
543 return BN_is_zero(&point
->Z
);
547 /* Determines whether the given EC_POINT is an actual point on the curve defined
548 * in the EC_GROUP. A point is valid if it satisfies the Weierstrass equation:
549 * y^2 + x*y = x^3 + a*x^2 + b.
551 int ec_GF2m_simple_is_on_curve(const EC_GROUP
*group
, const EC_POINT
*point
, BN_CTX
*ctx
)
554 BN_CTX
*new_ctx
= NULL
;
556 int (*field_mul
)(const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, const BIGNUM
*, BN_CTX
*);
557 int (*field_sqr
)(const EC_GROUP
*, BIGNUM
*, const BIGNUM
*, BN_CTX
*);
559 if (EC_POINT_is_at_infinity(group
, point
))
562 field_mul
= group
->meth
->field_mul
;
563 field_sqr
= group
->meth
->field_sqr
;
565 /* only support affine coordinates */
566 if (!point
->Z_is_one
) return -1;
570 ctx
= new_ctx
= BN_CTX_new();
576 y2
= BN_CTX_get(ctx
);
577 lh
= BN_CTX_get(ctx
);
578 if (lh
== NULL
) goto err
;
580 /* We have a curve defined by a Weierstrass equation
581 * y^2 + x*y = x^3 + a*x^2 + b.
582 * <=> x^3 + a*x^2 + x*y + b + y^2 = 0
583 * <=> ((x + a) * x + y ) * x + b + y^2 = 0
585 if (!BN_GF2m_add(lh
, &point
->X
, &group
->a
)) goto err
;
586 if (!field_mul(group
, lh
, lh
, &point
->X
, ctx
)) goto err
;
587 if (!BN_GF2m_add(lh
, lh
, &point
->Y
)) goto err
;
588 if (!field_mul(group
, lh
, lh
, &point
->X
, ctx
)) goto err
;
589 if (!BN_GF2m_add(lh
, lh
, &group
->b
)) goto err
;
590 if (!field_sqr(group
, y2
, &point
->Y
, ctx
)) goto err
;
591 if (!BN_GF2m_add(lh
, lh
, y2
)) goto err
;
592 ret
= BN_is_zero(lh
);
594 if (ctx
) BN_CTX_end(ctx
);
595 if (new_ctx
) BN_CTX_free(new_ctx
);
600 /* Indicates whether two points are equal.
603 * 0 equal (in affine coordinates)
606 int ec_GF2m_simple_cmp(const EC_GROUP
*group
, const EC_POINT
*a
, const EC_POINT
*b
, BN_CTX
*ctx
)
608 BIGNUM
*aX
, *aY
, *bX
, *bY
;
609 BN_CTX
*new_ctx
= NULL
;
612 if (EC_POINT_is_at_infinity(group
, a
))
614 return EC_POINT_is_at_infinity(group
, b
) ? 0 : 1;
617 if (EC_POINT_is_at_infinity(group
, b
))
620 if (a
->Z_is_one
&& b
->Z_is_one
)
622 return ((BN_cmp(&a
->X
, &b
->X
) == 0) && BN_cmp(&a
->Y
, &b
->Y
) == 0) ? 0 : 1;
627 ctx
= new_ctx
= BN_CTX_new();
633 aX
= BN_CTX_get(ctx
);
634 aY
= BN_CTX_get(ctx
);
635 bX
= BN_CTX_get(ctx
);
636 bY
= BN_CTX_get(ctx
);
637 if (bY
== NULL
) goto err
;
639 if (!EC_POINT_get_affine_coordinates_GF2m(group
, a
, aX
, aY
, ctx
)) goto err
;
640 if (!EC_POINT_get_affine_coordinates_GF2m(group
, b
, bX
, bY
, ctx
)) goto err
;
641 ret
= ((BN_cmp(aX
, bX
) == 0) && BN_cmp(aY
, bY
) == 0) ? 0 : 1;
644 if (ctx
) BN_CTX_end(ctx
);
645 if (new_ctx
) BN_CTX_free(new_ctx
);
650 /* Forces the given EC_POINT to internally use affine coordinates. */
651 int ec_GF2m_simple_make_affine(const EC_GROUP
*group
, EC_POINT
*point
, BN_CTX
*ctx
)
653 BN_CTX
*new_ctx
= NULL
;
657 if (point
->Z_is_one
|| EC_POINT_is_at_infinity(group
, point
))
662 ctx
= new_ctx
= BN_CTX_new();
670 if (y
== NULL
) goto err
;
672 if (!EC_POINT_get_affine_coordinates_GF2m(group
, point
, x
, y
, ctx
)) goto err
;
673 if (!BN_copy(&point
->X
, x
)) goto err
;
674 if (!BN_copy(&point
->Y
, y
)) goto err
;
675 if (!BN_one(&point
->Z
)) goto err
;
680 if (ctx
) BN_CTX_end(ctx
);
681 if (new_ctx
) BN_CTX_free(new_ctx
);
686 /* Forces each of the EC_POINTs in the given array to use affine coordinates. */
687 int ec_GF2m_simple_points_make_affine(const EC_GROUP
*group
, size_t num
, EC_POINT
*points
[], BN_CTX
*ctx
)
691 for (i
= 0; i
< num
; i
++)
693 if (!group
->meth
->make_affine(group
, points
[i
], ctx
)) return 0;
700 /* Wrapper to simple binary polynomial field multiplication implementation. */
701 int ec_GF2m_simple_field_mul(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, BN_CTX
*ctx
)
703 return BN_GF2m_mod_mul_arr(r
, a
, b
, group
->poly
, ctx
);
707 /* Wrapper to simple binary polynomial field squaring implementation. */
708 int ec_GF2m_simple_field_sqr(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
, BN_CTX
*ctx
)
710 return BN_GF2m_mod_sqr_arr(r
, a
, group
->poly
, ctx
);
714 /* Wrapper to simple binary polynomial field division implementation. */
715 int ec_GF2m_simple_field_div(const EC_GROUP
*group
, BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, BN_CTX
*ctx
)
717 return BN_GF2m_mod_div(r
, a
, b
, &group
->field
, ctx
);