add URL for Internet Draft
[openssl.git] / crypto / ec / ec2_smpl.c
1 /* crypto/ec/ec2_smpl.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  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
31  *
32  * Redistribution and use in source and binary forms, with or without
33  * modification, are permitted provided that the following conditions
34  * are met:
35  *
36  * 1. Redistributions of source code must retain the above copyright
37  *    notice, this list of conditions and the following disclaimer. 
38  *
39  * 2. Redistributions in binary form must reproduce the above copyright
40  *    notice, this list of conditions and the following disclaimer in
41  *    the documentation and/or other materials provided with the
42  *    distribution.
43  *
44  * 3. All advertising materials mentioning features or use of this
45  *    software must display the following acknowledgment:
46  *    "This product includes software developed by the OpenSSL Project
47  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
48  *
49  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
50  *    endorse or promote products derived from this software without
51  *    prior written permission. For written permission, please contact
52  *    openssl-core@openssl.org.
53  *
54  * 5. Products derived from this software may not be called "OpenSSL"
55  *    nor may "OpenSSL" appear in their names without prior written
56  *    permission of the OpenSSL Project.
57  *
58  * 6. Redistributions of any form whatsoever must retain the following
59  *    acknowledgment:
60  *    "This product includes software developed by the OpenSSL Project
61  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
62  *
63  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
64  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
65  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
66  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
67  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
68  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
69  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
70  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
71  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
72  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
73  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
74  * OF THE POSSIBILITY OF SUCH DAMAGE.
75  * ====================================================================
76  *
77  * This product includes cryptographic software written by Eric Young
78  * (eay@cryptsoft.com).  This product includes software written by Tim
79  * Hudson (tjh@cryptsoft.com).
80  *
81  */
82
83 #include <openssl/err.h>
84
85 #include "ec_lcl.h"
86
87
88 const EC_METHOD *EC_GF2m_simple_method(void)
89         {
90         static const EC_METHOD ret = {
91                 NID_X9_62_characteristic_two_field,
92                 ec_GF2m_simple_group_init,
93                 ec_GF2m_simple_group_finish,
94                 ec_GF2m_simple_group_clear_finish,
95                 ec_GF2m_simple_group_copy,
96                 ec_GF2m_simple_group_set_curve,
97                 ec_GF2m_simple_group_get_curve,
98                 ec_GF2m_simple_group_get_degree,
99                 ec_GF2m_simple_group_check_discriminant,
100                 ec_GF2m_simple_point_init,
101                 ec_GF2m_simple_point_finish,
102                 ec_GF2m_simple_point_clear_finish,
103                 ec_GF2m_simple_point_copy,
104                 ec_GF2m_simple_point_set_to_infinity,
105                 0 /* set_Jprojective_coordinates_GFp */,
106                 0 /* get_Jprojective_coordinates_GFp */,
107                 ec_GF2m_simple_point_set_affine_coordinates,
108                 ec_GF2m_simple_point_get_affine_coordinates,
109                 ec_GF2m_simple_set_compressed_coordinates,
110                 ec_GF2m_simple_point2oct,
111                 ec_GF2m_simple_oct2point,
112                 ec_GF2m_simple_add,
113                 ec_GF2m_simple_dbl,
114                 ec_GF2m_simple_invert,
115                 ec_GF2m_mont_mul,
116                 ec_GF2m_mont_precompute_mult,
117                 ec_GF2m_simple_is_at_infinity,
118                 ec_GF2m_simple_is_on_curve,
119                 ec_GF2m_simple_cmp,
120                 ec_GF2m_simple_make_affine,
121                 ec_GF2m_simple_points_make_affine,
122                 ec_GF2m_simple_field_mul,
123                 ec_GF2m_simple_field_sqr,
124                 ec_GF2m_simple_field_div,
125                 0 /* field_encode */,
126                 0 /* field_decode */,
127                 0 /* field_set_to_one */ };
128
129         return &ret;
130         }
131
132
133 /* Initialize a GF(2^m)-based EC_GROUP structure.
134  * Note that all other members are handled by EC_GROUP_new.
135  */
136 int ec_GF2m_simple_group_init(EC_GROUP *group)
137         {
138         BN_init(&group->field);
139         BN_init(&group->a);
140         BN_init(&group->b);
141         return 1;
142         }
143
144
145 /* Free a GF(2^m)-based EC_GROUP structure.
146  * Note that all other members are handled by EC_GROUP_free.
147  */
148 void ec_GF2m_simple_group_finish(EC_GROUP *group)
149         {
150         BN_free(&group->field);
151         BN_free(&group->a);
152         BN_free(&group->b);
153         }
154
155
156 /* Clear and free a GF(2^m)-based EC_GROUP structure.
157  * Note that all other members are handled by EC_GROUP_clear_free.
158  */
159 void ec_GF2m_simple_group_clear_finish(EC_GROUP *group)
160         {
161         BN_clear_free(&group->field);
162         BN_clear_free(&group->a);
163         BN_clear_free(&group->b);
164         group->poly[0] = 0;
165         group->poly[1] = 0;
166         group->poly[2] = 0;
167         group->poly[3] = 0;
168         group->poly[4] = 0;
169         }
170
171
172 /* Copy a GF(2^m)-based EC_GROUP structure.
173  * Note that all other members are handled by EC_GROUP_copy.
174  */
175 int ec_GF2m_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
176         {
177         int i;
178         if (!BN_copy(&dest->field, &src->field)) return 0;
179         if (!BN_copy(&dest->a, &src->a)) return 0;
180         if (!BN_copy(&dest->b, &src->b)) return 0;
181         dest->poly[0] = src->poly[0];
182         dest->poly[1] = src->poly[1];
183         dest->poly[2] = src->poly[2];
184         dest->poly[3] = src->poly[3];
185         dest->poly[4] = src->poly[4];
186         bn_wexpand(&dest->a, (dest->poly[0] + BN_BITS2 - 1) / BN_BITS2);
187         bn_wexpand(&dest->b, (dest->poly[0] + BN_BITS2 - 1) / BN_BITS2);
188         for (i = dest->a.top; i < dest->a.dmax; i++) dest->a.d[i] = 0;
189         for (i = dest->b.top; i < dest->b.dmax; i++) dest->b.d[i] = 0;
190         return 1;
191         }
192
193
194 /* Set the curve parameters of an EC_GROUP structure. */
195 int ec_GF2m_simple_group_set_curve(EC_GROUP *group,
196         const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
197         {
198         int ret = 0, i;
199
200         /* group->field */
201         if (!BN_copy(&group->field, p)) goto err;
202         i = BN_GF2m_poly2arr(&group->field, group->poly, 5);
203         if ((i != 5) && (i != 3))
204                 {
205                 ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_SET_CURVE, EC_R_UNSUPPORTED_FIELD);
206                 goto err;
207                 }
208
209         /* group->a */
210         if (!BN_GF2m_mod_arr(&group->a, a, group->poly)) goto err;
211         bn_wexpand(&group->a, (group->poly[0] + BN_BITS2 - 1) / BN_BITS2);
212         for (i = group->a.top; i < group->a.dmax; i++) group->a.d[i] = 0;
213         
214         /* group->b */
215         if (!BN_GF2m_mod_arr(&group->b, b, group->poly)) goto err;
216         bn_wexpand(&group->b, (group->poly[0] + BN_BITS2 - 1) / BN_BITS2);
217         for (i = group->b.top; i < group->b.dmax; i++) group->b.d[i] = 0;
218                 
219         ret = 1;
220   err:
221         return ret;
222         }
223
224
225 /* Get the curve parameters of an EC_GROUP structure.
226  * If p, a, or b are NULL then there values will not be set but the method will return with success.
227  */
228 int ec_GF2m_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
229         {
230         int ret = 0;
231         
232         if (p != NULL)
233                 {
234                 if (!BN_copy(p, &group->field)) return 0;
235                 }
236
237         if (a != NULL || b != NULL)
238                 {
239                 if (a != NULL)
240                         {
241                         if (!BN_copy(a, &group->a)) goto err;
242                         }
243                 if (b != NULL)
244                         {
245                         if (!BN_copy(b, &group->b)) goto err;
246                         }
247                 }
248         
249         ret = 1;
250         
251   err:
252         return ret;
253         }
254
255
256 /* Gets the degree of the field.  For a curve over GF(2^m) this is the value m. */
257 int ec_GF2m_simple_group_get_degree(const EC_GROUP *group)
258         {
259         return BN_num_bits(&group->field)-1;
260         }
261
262
263 /* Checks the discriminant of the curve.
264  * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p) 
265  */
266 int ec_GF2m_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
267         {
268         int ret = 0;
269         BIGNUM *b;
270         BN_CTX *new_ctx = NULL;
271
272         if (ctx == NULL)
273                 {
274                 ctx = new_ctx = BN_CTX_new();
275                 if (ctx == NULL)
276                         {
277                         ECerr(EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
278                         goto err;
279                         }
280                 }
281         BN_CTX_start(ctx);
282         b = BN_CTX_get(ctx);
283         if (b == NULL) goto err;
284
285         if (!BN_GF2m_mod_arr(b, &group->b, group->poly)) goto err;
286         
287         /* check the discriminant:
288          * y^2 + x*y = x^3 + a*x^2 + b is an elliptic curve <=> b != 0 (mod p) 
289          */
290         if (BN_is_zero(b)) goto err;
291
292         ret = 1;
293
294 err:
295         BN_CTX_end(ctx);
296         if (new_ctx != NULL)
297                 BN_CTX_free(new_ctx);
298         return ret;
299         }
300
301
302 /* Initializes an EC_POINT. */
303 int ec_GF2m_simple_point_init(EC_POINT *point)
304         {
305         BN_init(&point->X);
306         BN_init(&point->Y);
307         BN_init(&point->Z);
308         return 1;
309         }
310
311
312 /* Frees an EC_POINT. */
313 void ec_GF2m_simple_point_finish(EC_POINT *point)
314         {
315         BN_free(&point->X);
316         BN_free(&point->Y);
317         BN_free(&point->Z);
318         }
319
320
321 /* Clears and frees an EC_POINT. */
322 void ec_GF2m_simple_point_clear_finish(EC_POINT *point)
323         {
324         BN_clear_free(&point->X);
325         BN_clear_free(&point->Y);
326         BN_clear_free(&point->Z);
327         point->Z_is_one = 0;
328         }
329
330
331 /* Copy the contents of one EC_POINT into another.  Assumes dest is initialized. */
332 int ec_GF2m_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
333         {
334         if (!BN_copy(&dest->X, &src->X)) return 0;
335         if (!BN_copy(&dest->Y, &src->Y)) return 0;
336         if (!BN_copy(&dest->Z, &src->Z)) return 0;
337         dest->Z_is_one = src->Z_is_one;
338
339         return 1;
340         }
341
342
343 /* Set an EC_POINT to the point at infinity.  
344  * A point at infinity is represented by having Z=0.
345  */
346 int ec_GF2m_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
347         {
348         point->Z_is_one = 0;
349         return (BN_zero(&point->Z));
350         }
351
352
353 /* Set the coordinates of an EC_POINT using affine coordinates. 
354  * Note that the simple implementation only uses affine coordinates.
355  */
356 int ec_GF2m_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
357         const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
358         {
359         int ret = 0;    
360         if (x == NULL || y == NULL)
361                 {
362                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
363                 return 0;
364                 }
365
366         if (!BN_copy(&point->X, x)) goto err;
367         if (!BN_copy(&point->Y, y)) goto err;
368         if (!BN_copy(&point->Z, BN_value_one())) goto err;
369         point->Z_is_one = 1;
370         ret = 1;
371
372   err:
373         return ret;
374         }
375
376
377 /* Gets the affine coordinates of an EC_POINT. 
378  * Note that the simple implementation only uses affine coordinates.
379  */
380 int ec_GF2m_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
381         BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
382         {
383         int ret = 0;
384
385         if (EC_POINT_is_at_infinity(group, point))
386                 {
387                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
388                 return 0;
389                 }
390
391         if (BN_cmp(&point->Z, BN_value_one())) 
392                 {
393                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
394                 return 0;
395                 }
396         if (x != NULL)
397                 {
398                 if (!BN_copy(x, &point->X)) goto err;
399                 }
400         if (y != NULL)
401                 {
402                 if (!BN_copy(y, &point->Y)) goto err;
403                 }
404         ret = 1;
405                 
406  err:
407         return ret;
408         }
409
410
411 /* Include patented algorithms. */
412 #include "ec2_smpt.c"
413
414
415 /* Converts an EC_POINT to an octet string.  
416  * If buf is NULL, the encoded length will be returned.
417  * If the length len of buf is smaller than required an error will be returned.
418  *
419  * The point compression section of this function is patented by Certicom Corp. 
420  * under US Patent 6,141,420.  Point compression is disabled by default and can 
421  * be enabled by defining the preprocessor macro OPENSSL_EC_BIN_PT_COMP at 
422  * Configure-time.
423  */
424 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
425         unsigned char *buf, size_t len, BN_CTX *ctx)
426         {
427         size_t ret;
428         BN_CTX *new_ctx = NULL;
429         int used_ctx = 0;
430         BIGNUM *x, *y, *yxi;
431         size_t field_len, i, skip;
432
433 #ifndef OPENSSL_EC_BIN_PT_COMP
434         if ((form == POINT_CONVERSION_COMPRESSED) || (form == POINT_CONVERSION_HYBRID)) 
435                 {
436                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_DISABLED);
437                 goto err;
438                 }
439 #endif
440
441         if ((form != POINT_CONVERSION_COMPRESSED)
442                 && (form != POINT_CONVERSION_UNCOMPRESSED)
443                 && (form != POINT_CONVERSION_HYBRID))
444                 {
445                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
446                 goto err;
447                 }
448
449         if (EC_POINT_is_at_infinity(group, point))
450                 {
451                 /* encodes to a single 0 octet */
452                 if (buf != NULL)
453                         {
454                         if (len < 1)
455                                 {
456                                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
457                                 return 0;
458                                 }
459                         buf[0] = 0;
460                         }
461                 return 1;
462                 }
463
464
465         /* ret := required output buffer length */
466         field_len = (EC_GROUP_get_degree(group) + 7) / 8;
467         ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
468
469         /* if 'buf' is NULL, just return required length */
470         if (buf != NULL)
471                 {
472                 if (len < ret)
473                         {
474                         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
475                         goto err;
476                         }
477
478                 if (ctx == NULL)
479                         {
480                         ctx = new_ctx = BN_CTX_new();
481                         if (ctx == NULL)
482                                 return 0;
483                         }
484
485                 BN_CTX_start(ctx);
486                 used_ctx = 1;
487                 x = BN_CTX_get(ctx);
488                 y = BN_CTX_get(ctx);
489                 yxi = BN_CTX_get(ctx);
490                 if (yxi == NULL) goto err;
491
492                 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
493
494                 buf[0] = form;
495 #ifdef OPENSSL_EC_BIN_PT_COMP
496                 if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x))
497                         {
498                         if (!group->meth->field_div(group, yxi, y, x, ctx)) goto err;
499                         if (BN_is_odd(yxi)) buf[0]++;
500                         }
501 #endif
502
503                 i = 1;
504                 
505                 skip = field_len - BN_num_bytes(x);
506                 if (skip > field_len)
507                         {
508                         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
509                         goto err;
510                         }
511                 while (skip > 0)
512                         {
513                         buf[i++] = 0;
514                         skip--;
515                         }
516                 skip = BN_bn2bin(x, buf + i);
517                 i += skip;
518                 if (i != 1 + field_len)
519                         {
520                         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
521                         goto err;
522                         }
523
524                 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
525                         {
526                         skip = field_len - BN_num_bytes(y);
527                         if (skip > field_len)
528                                 {
529                                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
530                                 goto err;
531                                 }
532                         while (skip > 0)
533                                 {
534                                 buf[i++] = 0;
535                                 skip--;
536                                 }
537                         skip = BN_bn2bin(y, buf + i);
538                         i += skip;
539                         }
540
541                 if (i != ret)
542                         {
543                         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
544                         goto err;
545                         }
546                 }
547         
548         if (used_ctx)
549                 BN_CTX_end(ctx);
550         if (new_ctx != NULL)
551                 BN_CTX_free(new_ctx);
552         return ret;
553
554  err:
555         if (used_ctx)
556                 BN_CTX_end(ctx);
557         if (new_ctx != NULL)
558                 BN_CTX_free(new_ctx);
559         return 0;
560         }
561
562
563 /* Converts an octet string representation to an EC_POINT. 
564  * Note that the simple implementation only uses affine coordinates.
565  */
566 int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
567         const unsigned char *buf, size_t len, BN_CTX *ctx)
568         {
569         point_conversion_form_t form;
570         int y_bit;
571         BN_CTX *new_ctx = NULL;
572         BIGNUM *x, *y, *yxi;
573         size_t field_len, enc_len;
574         int ret = 0;
575
576         if (len == 0)
577                 {
578                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
579                 return 0;
580                 }
581         form = buf[0];
582         y_bit = form & 1;
583         form = form & ~1;
584         if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
585                 && (form != POINT_CONVERSION_UNCOMPRESSED)
586                 && (form != POINT_CONVERSION_HYBRID))
587                 {
588                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
589                 return 0;
590                 }
591         if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
592                 {
593                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
594                 return 0;
595                 }
596
597         if (form == 0)
598                 {
599                 if (len != 1)
600                         {
601                         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
602                         return 0;
603                         }
604
605                 return EC_POINT_set_to_infinity(group, point);
606                 }
607         
608         field_len = (EC_GROUP_get_degree(group) + 7) / 8;
609         enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
610
611         if (len != enc_len)
612                 {
613                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
614                 return 0;
615                 }
616
617         if (ctx == NULL)
618                 {
619                 ctx = new_ctx = BN_CTX_new();
620                 if (ctx == NULL)
621                         return 0;
622                 }
623
624         BN_CTX_start(ctx);
625         x = BN_CTX_get(ctx);
626         y = BN_CTX_get(ctx);
627         yxi = BN_CTX_get(ctx);
628         if (yxi == NULL) goto err;
629
630         if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
631         if (BN_ucmp(x, &group->field) >= 0)
632                 {
633                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
634                 goto err;
635                 }
636
637         if (form == POINT_CONVERSION_COMPRESSED)
638                 {
639                 if (!EC_POINT_set_compressed_coordinates_GF2m(group, point, x, y_bit, ctx)) goto err;
640                 }
641         else
642                 {
643                 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
644                 if (BN_ucmp(y, &group->field) >= 0)
645                         {
646                         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
647                         goto err;
648                         }
649                 if (form == POINT_CONVERSION_HYBRID)
650                         {
651                         if (!group->meth->field_div(group, yxi, y, x, ctx)) goto err;
652                         if (y_bit != BN_is_odd(yxi))
653                                 {
654                                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
655                                 goto err;
656                                 }
657                         }
658
659                 if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
660                 }
661         
662         if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
663                 {
664                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
665                 goto err;
666                 }
667
668         ret = 1;
669         
670  err:
671         BN_CTX_end(ctx);
672         if (new_ctx != NULL)
673                 BN_CTX_free(new_ctx);
674         return ret;
675         }
676
677
678 /* Computes a + b and stores the result in r.  r could be a or b, a could be b.
679  * Uses algorithm A.10.2 of IEEE P1363.
680  */
681 int ec_GF2m_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
682         {
683         BN_CTX *new_ctx = NULL;
684         BIGNUM *x0, *y0, *x1, *y1, *x2, *y2, *s, *t;
685         int ret = 0;
686         
687         if (EC_POINT_is_at_infinity(group, a))
688                 {
689                 if (!EC_POINT_copy(r, b)) return 0;
690                 return 1;
691                 }
692
693         if (EC_POINT_is_at_infinity(group, b))
694                 {
695                 if (!EC_POINT_copy(r, a)) return 0;
696                 return 1;
697                 }
698
699         if (ctx == NULL)
700                 {
701                 ctx = new_ctx = BN_CTX_new();
702                 if (ctx == NULL)
703                         return 0;
704                 }
705
706         BN_CTX_start(ctx);
707         x0 = BN_CTX_get(ctx);
708         y0 = BN_CTX_get(ctx);
709         x1 = BN_CTX_get(ctx);
710         y1 = BN_CTX_get(ctx);
711         x2 = BN_CTX_get(ctx);
712         y2 = BN_CTX_get(ctx);
713         s = BN_CTX_get(ctx);
714         t = BN_CTX_get(ctx);
715         if (t == NULL) goto err;
716
717         if (a->Z_is_one) 
718                 {
719                 if (!BN_copy(x0, &a->X)) goto err;
720                 if (!BN_copy(y0, &a->Y)) goto err;
721                 }
722         else
723                 {
724                 if (!EC_POINT_get_affine_coordinates_GF2m(group, a, x0, y0, ctx)) goto err;
725                 }
726         if (b->Z_is_one) 
727                 {
728                 if (!BN_copy(x1, &b->X)) goto err;
729                 if (!BN_copy(y1, &b->Y)) goto err;
730                 }
731         else
732                 {
733                 if (!EC_POINT_get_affine_coordinates_GF2m(group, b, x1, y1, ctx)) goto err;
734                 }
735
736
737         if (BN_GF2m_cmp(x0, x1))
738                 {
739                 if (!BN_GF2m_add(t, x0, x1)) goto err;
740                 if (!BN_GF2m_add(s, y0, y1)) goto err;
741                 if (!group->meth->field_div(group, s, s, t, ctx)) goto err;
742                 if (!group->meth->field_sqr(group, x2, s, ctx)) goto err;
743                 if (!BN_GF2m_add(x2, x2, &group->a)) goto err;
744                 if (!BN_GF2m_add(x2, x2, s)) goto err;
745                 if (!BN_GF2m_add(x2, x2, t)) goto err;
746                 }
747         else
748                 {
749                 if (BN_GF2m_cmp(y0, y1) || BN_is_zero(x1))
750                         {
751                         if (!EC_POINT_set_to_infinity(group, r)) goto err;
752                         ret = 1;
753                         goto err;
754                         }
755                 if (!group->meth->field_div(group, s, y1, x1, ctx)) goto err;
756                 if (!BN_GF2m_add(s, s, x1)) goto err;
757                 
758                 if (!group->meth->field_sqr(group, x2, s, ctx)) goto err;
759                 if (!BN_GF2m_add(x2, x2, s)) goto err;
760                 if (!BN_GF2m_add(x2, x2, &group->a)) goto err;
761                 }
762
763         if (!BN_GF2m_add(y2, x1, x2)) goto err;
764         if (!group->meth->field_mul(group, y2, y2, s, ctx)) goto err;
765         if (!BN_GF2m_add(y2, y2, x2)) goto err;
766         if (!BN_GF2m_add(y2, y2, y1)) goto err;
767
768         if (!EC_POINT_set_affine_coordinates_GF2m(group, r, x2, y2, ctx)) goto err;
769
770         ret = 1;
771
772  err:
773         BN_CTX_end(ctx);
774         if (new_ctx != NULL)
775                 BN_CTX_free(new_ctx);
776         return ret;
777         }
778
779
780 /* Computes 2 * a and stores the result in r.  r could be a.
781  * Uses algorithm A.10.2 of IEEE P1363.
782  */
783 int ec_GF2m_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
784         {
785         return ec_GF2m_simple_add(group, r, a, a, ctx);
786         }
787
788
789 int ec_GF2m_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
790         {
791         if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
792                 /* point is its own inverse */
793                 return 1;
794         
795         if (!EC_POINT_make_affine(group, point, ctx)) return 0;
796         return BN_GF2m_add(&point->Y, &point->X, &point->Y);
797         }
798
799
800 /* Indicates whether the given point is the point at infinity. */
801 int ec_GF2m_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
802         {
803         return BN_is_zero(&point->Z);
804         }
805
806
807 /* Determines whether the given EC_POINT is an actual point on the curve defined
808  * in the EC_GROUP.  A point is valid if it satisfies the Weierstrass equation:
809  *      y^2 + x*y = x^3 + a*x^2 + b.
810  */
811 int ec_GF2m_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
812         {
813         BN_CTX *new_ctx = NULL;
814         BIGNUM *rh, *lh, *tmp1;
815         int ret = -1;
816
817         if (EC_POINT_is_at_infinity(group, point))
818                 return 1;
819         
820         /* only support affine coordinates */
821         if (!point->Z_is_one) goto err;
822
823         if (ctx == NULL)
824                 {
825                 ctx = new_ctx = BN_CTX_new();
826                 if (ctx == NULL)
827                         return -1;
828                 }
829
830         BN_CTX_start(ctx);
831         rh = BN_CTX_get(ctx);
832         lh = BN_CTX_get(ctx);
833         tmp1 = BN_CTX_get(ctx);
834         if (tmp1 == NULL) goto err;
835
836         /* We have a curve defined by a Weierstrass equation
837          *      y^2 + x*y = x^3 + a*x^2 + b.
838          * To test this, we add up the right-hand side in 'rh'
839          * and the left-hand side in 'lh'.
840          */
841
842         /* rh := X^3 */
843         if (!group->meth->field_sqr(group, tmp1, &point->X, ctx)) goto err;
844         if (!group->meth->field_mul(group, rh, tmp1, &point->X, ctx)) goto err;
845
846         /* rh := rh + a*X^2 */
847         if (!group->meth->field_mul(group, tmp1, tmp1, &group->a, ctx)) goto err;
848         if (!BN_GF2m_add(rh, rh, tmp1)) goto err;
849
850         /* rh := rh + b */
851         if (!BN_GF2m_add(rh, rh, &group->b)) goto err;
852
853         /* lh := Y^2 */
854         if (!group->meth->field_sqr(group, lh, &point->Y, ctx)) goto err;
855
856         /* lh := lh + x*y */
857         if (!group->meth->field_mul(group, tmp1, &point->X, &point->Y, ctx)) goto err;
858         if (!BN_GF2m_add(lh, lh, tmp1)) goto err;
859
860         ret = (0 == BN_GF2m_cmp(lh, rh));
861
862  err:
863         if (ctx) BN_CTX_end(ctx);
864         if (new_ctx) BN_CTX_free(new_ctx);
865         return ret;
866         }
867
868
869 /* Indicates whether two points are equal.
870  * Return values:
871  *  -1   error
872  *   0   equal (in affine coordinates)
873  *   1   not equal
874  */
875 int ec_GF2m_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
876         {
877         BIGNUM *aX, *aY, *bX, *bY;
878         BN_CTX *new_ctx = NULL;
879         int ret = -1;
880
881         if (EC_POINT_is_at_infinity(group, a))
882                 {
883                 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
884                 }
885         
886         if (a->Z_is_one && b->Z_is_one)
887                 {
888                 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
889                 }
890
891         if (ctx == NULL)
892                 {
893                 ctx = new_ctx = BN_CTX_new();
894                 if (ctx == NULL)
895                         return -1;
896                 }
897
898         BN_CTX_start(ctx);
899         aX = BN_CTX_get(ctx);
900         aY = BN_CTX_get(ctx);
901         bX = BN_CTX_get(ctx);
902         bY = BN_CTX_get(ctx);
903         if (bY == NULL) goto err;
904
905         if (!EC_POINT_get_affine_coordinates_GF2m(group, a, aX, aY, ctx)) goto err;
906         if (!EC_POINT_get_affine_coordinates_GF2m(group, b, bX, bY, ctx)) goto err;
907         ret = ((BN_cmp(aX, bX) == 0) && BN_cmp(aY, bY) == 0) ? 0 : 1;
908
909   err:  
910         if (ctx) BN_CTX_end(ctx);
911         if (new_ctx) BN_CTX_free(new_ctx);
912         return ret;
913         }
914
915
916 /* Forces the given EC_POINT to internally use affine coordinates. */
917 int ec_GF2m_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
918         {
919         BN_CTX *new_ctx = NULL;
920         BIGNUM *x, *y;
921         int ret = 0;
922
923         if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
924                 return 1;
925         
926         if (ctx == NULL)
927                 {
928                 ctx = new_ctx = BN_CTX_new();
929                 if (ctx == NULL)
930                         return 0;
931                 }
932
933         BN_CTX_start(ctx);
934         x = BN_CTX_get(ctx);
935         y = BN_CTX_get(ctx);
936         if (y == NULL) goto err;
937         
938         if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err;
939         if (!BN_copy(&point->X, x)) goto err;
940         if (!BN_copy(&point->Y, y)) goto err;
941         if (!BN_one(&point->Z)) goto err;
942         
943         ret = 1;                
944
945   err:
946         if (ctx) BN_CTX_end(ctx);
947         if (new_ctx) BN_CTX_free(new_ctx);
948         return ret;
949         }
950
951
952 /* Forces each of the EC_POINTs in the given array to use affine coordinates. */
953 int ec_GF2m_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
954         {
955         size_t i;
956
957         for (i = 0; i < num; i++)
958                 {
959                 if (!group->meth->make_affine(group, points[i], ctx)) return 0;
960                 }
961
962         return 1;
963         }
964
965
966 /* Wrapper to simple binary polynomial field multiplication implementation. */
967 int ec_GF2m_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
968         {
969         return BN_GF2m_mod_mul_arr(r, a, b, group->poly, ctx);
970         }
971
972
973 /* Wrapper to simple binary polynomial field squaring implementation. */
974 int ec_GF2m_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
975         {
976         return BN_GF2m_mod_sqr_arr(r, a, group->poly, ctx);
977         }
978
979
980 /* Wrapper to simple binary polynomial field division implementation. */
981 int ec_GF2m_simple_field_div(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
982         {
983         return BN_GF2m_mod_div(r, a, b, &group->field, ctx);
984         }