Change array representation of binary polynomials to make GF2m part of
[openssl.git] / crypto / ec / ecp_smpl.c
1 /* crypto/ec/ecp_smpl.c */
2 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3  * for the OpenSSL project. 
4  * Includes code written by Bodo Moeller for the OpenSSL project.
5 */
6 /* ====================================================================
7  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  *
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer. 
15  *
16  * 2. Redistributions in binary form must reproduce the above copyright
17  *    notice, this list of conditions and the following disclaimer in
18  *    the documentation and/or other materials provided with the
19  *    distribution.
20  *
21  * 3. All advertising materials mentioning features or use of this
22  *    software must display the following acknowledgment:
23  *    "This product includes software developed by the OpenSSL Project
24  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25  *
26  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
27  *    endorse or promote products derived from this software without
28  *    prior written permission. For written permission, please contact
29  *    openssl-core@openssl.org.
30  *
31  * 5. Products derived from this software may not be called "OpenSSL"
32  *    nor may "OpenSSL" appear in their names without prior written
33  *    permission of the OpenSSL Project.
34  *
35  * 6. Redistributions of any form whatsoever must retain the following
36  *    acknowledgment:
37  *    "This product includes software developed by the OpenSSL Project
38  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39  *
40  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
41  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
43  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
44  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
45  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
46  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
47  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
49  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
50  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
51  * OF THE POSSIBILITY OF SUCH DAMAGE.
52  * ====================================================================
53  *
54  * This product includes cryptographic software written by Eric Young
55  * (eay@cryptsoft.com).  This product includes software written by Tim
56  * Hudson (tjh@cryptsoft.com).
57  *
58  */
59 /* ====================================================================
60  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
61  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
62  * and contributed to the OpenSSL project.
63  */
64
65 #include <openssl/err.h>
66 #include <openssl/symhacks.h>
67
68 #include "ec_lcl.h"
69
70 const EC_METHOD *EC_GFp_simple_method(void)
71         {
72         static const EC_METHOD ret = {
73                 NID_X9_62_prime_field,
74                 ec_GFp_simple_group_init,
75                 ec_GFp_simple_group_finish,
76                 ec_GFp_simple_group_clear_finish,
77                 ec_GFp_simple_group_copy,
78                 ec_GFp_simple_group_set_curve,
79                 ec_GFp_simple_group_get_curve,
80                 ec_GFp_simple_group_get_degree,
81                 ec_GFp_simple_group_check_discriminant,
82                 ec_GFp_simple_point_init,
83                 ec_GFp_simple_point_finish,
84                 ec_GFp_simple_point_clear_finish,
85                 ec_GFp_simple_point_copy,
86                 ec_GFp_simple_point_set_to_infinity,
87                 ec_GFp_simple_set_Jprojective_coordinates_GFp,
88                 ec_GFp_simple_get_Jprojective_coordinates_GFp,
89                 ec_GFp_simple_point_set_affine_coordinates,
90                 ec_GFp_simple_point_get_affine_coordinates,
91                 ec_GFp_simple_set_compressed_coordinates,
92                 ec_GFp_simple_point2oct,
93                 ec_GFp_simple_oct2point,
94                 ec_GFp_simple_add,
95                 ec_GFp_simple_dbl,
96                 ec_GFp_simple_invert,
97                 ec_GFp_simple_is_at_infinity,
98                 ec_GFp_simple_is_on_curve,
99                 ec_GFp_simple_cmp,
100                 ec_GFp_simple_make_affine,
101                 ec_GFp_simple_points_make_affine,
102                 0 /* mul */,
103                 0 /* precompute_mult */,
104                 0 /* have_precompute_mult */,   
105                 ec_GFp_simple_field_mul,
106                 ec_GFp_simple_field_sqr,
107                 0 /* field_div */,
108                 0 /* field_encode */,
109                 0 /* field_decode */,
110                 0 /* field_set_to_one */ };
111
112         return &ret;
113         }
114
115
116 /* Most method functions in this file are designed to work with
117  * non-trivial representations of field elements if necessary
118  * (see ecp_mont.c): while standard modular addition and subtraction
119  * are used, the field_mul and field_sqr methods will be used for
120  * multiplication, and field_encode and field_decode (if defined)
121  * will be used for converting between representations.
122
123  * Functions ec_GFp_simple_points_make_affine() and
124  * ec_GFp_simple_point_get_affine_coordinates() specifically assume
125  * that if a non-trivial representation is used, it is a Montgomery
126  * representation (i.e. 'encoding' means multiplying by some factor R).
127  */
128
129
130 int ec_GFp_simple_group_init(EC_GROUP *group)
131         {
132         BN_init(&group->field);
133         BN_init(&group->a);
134         BN_init(&group->b);
135         group->a_is_minus3 = 0;
136         return 1;
137         }
138
139
140 void ec_GFp_simple_group_finish(EC_GROUP *group)
141         {
142         BN_free(&group->field);
143         BN_free(&group->a);
144         BN_free(&group->b);
145         }
146
147
148 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
149         {
150         BN_clear_free(&group->field);
151         BN_clear_free(&group->a);
152         BN_clear_free(&group->b);
153         }
154
155
156 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
157         {
158         if (!BN_copy(&dest->field, &src->field)) return 0;
159         if (!BN_copy(&dest->a, &src->a)) return 0;
160         if (!BN_copy(&dest->b, &src->b)) return 0;
161
162         dest->a_is_minus3 = src->a_is_minus3;
163
164         return 1;
165         }
166
167
168 int ec_GFp_simple_group_set_curve(EC_GROUP *group,
169         const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
170         {
171         int ret = 0;
172         BN_CTX *new_ctx = NULL;
173         BIGNUM *tmp_a;
174         
175         /* p must be a prime > 3 */
176         if (BN_num_bits(p) <= 2 || !BN_is_odd(p))
177                 {
178                 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD);
179                 return 0;
180                 }
181
182         if (ctx == NULL)
183                 {
184                 ctx = new_ctx = BN_CTX_new();
185                 if (ctx == NULL)
186                         return 0;
187                 }
188
189         BN_CTX_start(ctx);
190         tmp_a = BN_CTX_get(ctx);
191         if (tmp_a == NULL) goto err;
192
193         /* group->field */
194         if (!BN_copy(&group->field, p)) goto err;
195         BN_set_negative(&group->field, 0);
196
197         /* group->a */
198         if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
199         if (group->meth->field_encode)
200                 { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }     
201         else
202                 if (!BN_copy(&group->a, tmp_a)) goto err;
203         
204         /* group->b */
205         if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
206         if (group->meth->field_encode)
207                 if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
208         
209         /* group->a_is_minus3 */
210         if (!BN_add_word(tmp_a, 3)) goto err;
211         group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
212
213         ret = 1;
214
215  err:
216         BN_CTX_end(ctx);
217         if (new_ctx != NULL)
218                 BN_CTX_free(new_ctx);
219         return ret;
220         }
221
222
223 int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
224         {
225         int ret = 0;
226         BN_CTX *new_ctx = NULL;
227         
228         if (p != NULL)
229                 {
230                 if (!BN_copy(p, &group->field)) return 0;
231                 }
232
233         if (a != NULL || b != NULL)
234                 {
235                 if (group->meth->field_decode)
236                         {
237                         if (ctx == NULL)
238                                 {
239                                 ctx = new_ctx = BN_CTX_new();
240                                 if (ctx == NULL)
241                                         return 0;
242                                 }
243                         if (a != NULL)
244                                 {
245                                 if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
246                                 }
247                         if (b != NULL)
248                                 {
249                                 if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
250                                 }
251                         }
252                 else
253                         {
254                         if (a != NULL)
255                                 {
256                                 if (!BN_copy(a, &group->a)) goto err;
257                                 }
258                         if (b != NULL)
259                                 {
260                                 if (!BN_copy(b, &group->b)) goto err;
261                                 }
262                         }
263                 }
264         
265         ret = 1;
266         
267  err:
268         if (new_ctx)
269                 BN_CTX_free(new_ctx);
270         return ret;
271         }
272
273
274 int ec_GFp_simple_group_get_degree(const EC_GROUP *group)
275         {
276         return BN_num_bits(&group->field);
277         }
278
279
280 int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx)
281         {
282         int ret = 0;
283         BIGNUM *a,*b,*order,*tmp_1,*tmp_2;
284         const BIGNUM *p = &group->field;
285         BN_CTX *new_ctx = NULL;
286
287         if (ctx == NULL)
288                 {
289                 ctx = new_ctx = BN_CTX_new();
290                 if (ctx == NULL)
291                         {
292                         ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE);
293                         goto err;
294                         }
295                 }
296         BN_CTX_start(ctx);
297         a = BN_CTX_get(ctx);
298         b = BN_CTX_get(ctx);
299         tmp_1 = BN_CTX_get(ctx);
300         tmp_2 = BN_CTX_get(ctx);
301         order = BN_CTX_get(ctx);
302         if (order == NULL) goto err;
303
304         if (group->meth->field_decode)
305                 {
306                 if (!group->meth->field_decode(group, a, &group->a, ctx)) goto err;
307                 if (!group->meth->field_decode(group, b, &group->b, ctx)) goto err;
308                 }
309         else
310                 {
311                 if (!BN_copy(a, &group->a)) goto err;
312                 if (!BN_copy(b, &group->b)) goto err;
313                 }
314         
315         /* check the discriminant:
316          * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 
317          * 0 =< a, b < p */
318         if (BN_is_zero(a))
319                 {
320                 if (BN_is_zero(b)) goto err;
321                 }
322         else if (!BN_is_zero(b))
323                 {
324                 if (!BN_mod_sqr(tmp_1, a, p, ctx)) goto err;
325                 if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) goto err;
326                 if (!BN_lshift(tmp_1, tmp_2, 2)) goto err;
327                 /* tmp_1 = 4*a^3 */
328
329                 if (!BN_mod_sqr(tmp_2, b, p, ctx)) goto err;
330                 if (!BN_mul_word(tmp_2, 27)) goto err;
331                 /* tmp_2 = 27*b^2 */
332
333                 if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) goto err;
334                 if (BN_is_zero(a)) goto err;
335                 }
336         ret = 1;
337
338 err:
339         if (ctx != NULL)
340                 BN_CTX_end(ctx);
341         if (new_ctx != NULL)
342                 BN_CTX_free(new_ctx);
343         return ret;
344         }
345
346
347 int ec_GFp_simple_point_init(EC_POINT *point)
348         {
349         BN_init(&point->X);
350         BN_init(&point->Y);
351         BN_init(&point->Z);
352         point->Z_is_one = 0;
353
354         return 1;
355         }
356
357
358 void ec_GFp_simple_point_finish(EC_POINT *point)
359         {
360         BN_free(&point->X);
361         BN_free(&point->Y);
362         BN_free(&point->Z);
363         }
364
365
366 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
367         {
368         BN_clear_free(&point->X);
369         BN_clear_free(&point->Y);
370         BN_clear_free(&point->Z);
371         point->Z_is_one = 0;
372         }
373
374
375 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
376         {
377         if (!BN_copy(&dest->X, &src->X)) return 0;
378         if (!BN_copy(&dest->Y, &src->Y)) return 0;
379         if (!BN_copy(&dest->Z, &src->Z)) return 0;
380         dest->Z_is_one = src->Z_is_one;
381
382         return 1;
383         }
384
385
386 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
387         {
388         point->Z_is_one = 0;
389         BN_zero(&point->Z);
390         return 1;
391         }
392
393
394 int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
395         const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *ctx)
396         {
397         BN_CTX *new_ctx = NULL;
398         int ret = 0;
399         
400         if (ctx == NULL)
401                 {
402                 ctx = new_ctx = BN_CTX_new();
403                 if (ctx == NULL)
404                         return 0;
405                 }
406
407         if (x != NULL)
408                 {
409                 if (!BN_nnmod(&point->X, x, &group->field, ctx)) goto err;
410                 if (group->meth->field_encode)
411                         {
412                         if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
413                         }
414                 }
415         
416         if (y != NULL)
417                 {
418                 if (!BN_nnmod(&point->Y, y, &group->field, ctx)) goto err;
419                 if (group->meth->field_encode)
420                         {
421                         if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
422                         }
423                 }
424         
425         if (z != NULL)
426                 {
427                 int Z_is_one;
428
429                 if (!BN_nnmod(&point->Z, z, &group->field, ctx)) goto err;
430                 Z_is_one = BN_is_one(&point->Z);
431                 if (group->meth->field_encode)
432                         {
433                         if (Z_is_one && (group->meth->field_set_to_one != 0))
434                                 {
435                                 if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
436                                 }
437                         else
438                                 {
439                                 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
440                                 }
441                         }
442                 point->Z_is_one = Z_is_one;
443                 }
444         
445         ret = 1;
446         
447  err:
448         if (new_ctx != NULL)
449                 BN_CTX_free(new_ctx);
450         return ret;
451         }
452
453
454 int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
455         BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *ctx)
456         {
457         BN_CTX *new_ctx = NULL;
458         int ret = 0;
459         
460         if (group->meth->field_decode != 0)
461                 {
462                 if (ctx == NULL)
463                         {
464                         ctx = new_ctx = BN_CTX_new();
465                         if (ctx == NULL)
466                                 return 0;
467                         }
468
469                 if (x != NULL)
470                         {
471                         if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
472                         }
473                 if (y != NULL)
474                         {
475                         if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
476                         }
477                 if (z != NULL)
478                         {
479                         if (!group->meth->field_decode(group, z, &point->Z, ctx)) goto err;
480                         }
481                 }
482         else    
483                 {
484                 if (x != NULL)
485                         {
486                         if (!BN_copy(x, &point->X)) goto err;
487                         }
488                 if (y != NULL)
489                         {
490                         if (!BN_copy(y, &point->Y)) goto err;
491                         }
492                 if (z != NULL)
493                         {
494                         if (!BN_copy(z, &point->Z)) goto err;
495                         }
496                 }
497         
498         ret = 1;
499
500  err:
501         if (new_ctx != NULL)
502                 BN_CTX_free(new_ctx);
503         return ret;
504         }
505
506
507 int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
508         const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
509         {
510         if (x == NULL || y == NULL)
511                 {
512                 /* unlike for projective coordinates, we do not tolerate this */
513                 ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER);
514                 return 0;
515                 }
516
517         return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx);
518         }
519
520
521 int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
522         BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
523         {
524         BN_CTX *new_ctx = NULL;
525         BIGNUM *Z, *Z_1, *Z_2, *Z_3;
526         const BIGNUM *Z_;
527         int ret = 0;
528
529         if (EC_POINT_is_at_infinity(group, point))
530                 {
531                 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY);
532                 return 0;
533                 }
534
535         if (ctx == NULL)
536                 {
537                 ctx = new_ctx = BN_CTX_new();
538                 if (ctx == NULL)
539                         return 0;
540                 }
541
542         BN_CTX_start(ctx);
543         Z = BN_CTX_get(ctx);
544         Z_1 = BN_CTX_get(ctx);
545         Z_2 = BN_CTX_get(ctx);
546         Z_3 = BN_CTX_get(ctx);
547         if (Z_3 == NULL) goto err;
548
549         /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
550         
551         if (group->meth->field_decode)
552                 {
553                 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
554                 Z_ = Z;
555                 }
556         else
557                 {
558                 Z_ = &point->Z;
559                 }
560         
561         if (BN_is_one(Z_))
562                 {
563                 if (group->meth->field_decode)
564                         {
565                         if (x != NULL)
566                                 {
567                                 if (!group->meth->field_decode(group, x, &point->X, ctx)) goto err;
568                                 }
569                         if (y != NULL)
570                                 {
571                                 if (!group->meth->field_decode(group, y, &point->Y, ctx)) goto err;
572                                 }
573                         }
574                 else
575                         {
576                         if (x != NULL)
577                                 {
578                                 if (!BN_copy(x, &point->X)) goto err;
579                                 }
580                         if (y != NULL)
581                                 {
582                                 if (!BN_copy(y, &point->Y)) goto err;
583                                 }
584                         }
585                 }
586         else
587                 {
588                 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
589                         {
590                         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB);
591                         goto err;
592                         }
593                 
594                 if (group->meth->field_encode == 0)
595                         {
596                         /* field_sqr works on standard representation */
597                         if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
598                         }
599                 else
600                         {
601                         if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
602                         }
603         
604                 if (x != NULL)
605                         {
606                         /* in the Montgomery case, field_mul will cancel out Montgomery factor in X: */
607                         if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) goto err;
608                         }
609
610                 if (y != NULL)
611                         {
612                         if (group->meth->field_encode == 0)
613                                 {
614                                 /* field_mul works on standard representation */
615                                 if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
616                                 }
617                         else
618                                 {
619                                 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
620                                 }
621
622                         /* in the Montgomery case, field_mul will cancel out Montgomery factor in Y: */
623                         if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) goto err;
624                         }
625                 }
626
627         ret = 1;
628
629  err:
630         BN_CTX_end(ctx);
631         if (new_ctx != NULL)
632                 BN_CTX_free(new_ctx);
633         return ret;
634         }
635
636
637 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
638         const BIGNUM *x_, int y_bit, BN_CTX *ctx)
639         {
640         BN_CTX *new_ctx = NULL;
641         BIGNUM *tmp1, *tmp2, *x, *y;
642         int ret = 0;
643
644         /* clear error queue*/
645         ERR_clear_error();
646
647         if (ctx == NULL)
648                 {
649                 ctx = new_ctx = BN_CTX_new();
650                 if (ctx == NULL)
651                         return 0;
652                 }
653
654         y_bit = (y_bit != 0);
655
656         BN_CTX_start(ctx);
657         tmp1 = BN_CTX_get(ctx);
658         tmp2 = BN_CTX_get(ctx);
659         x = BN_CTX_get(ctx);
660         y = BN_CTX_get(ctx);
661         if (y == NULL) goto err;
662
663         /* Recover y.  We have a Weierstrass equation
664          *     y^2 = x^3 + a*x + b,
665          * so  y  is one of the square roots of  x^3 + a*x + b.
666          */
667
668         /* tmp1 := x^3 */
669         if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
670         if (group->meth->field_decode == 0)
671                 {
672                 /* field_{sqr,mul} work on standard representation */
673                 if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
674                 if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
675                 }
676         else
677                 {
678                 if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
679                 if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
680                 }
681         
682         /* tmp1 := tmp1 + a*x */
683         if (group->a_is_minus3)
684                 {
685                 if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
686                 if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
687                 if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
688                 }
689         else
690                 {
691                 if (group->meth->field_decode)
692                         {
693                         if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) goto err;
694                         if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) goto err;
695                         }
696                 else
697                         {
698                         /* field_mul works on standard representation */
699                         if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
700                         }
701                 
702                 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
703                 }
704         
705         /* tmp1 := tmp1 + b */
706         if (group->meth->field_decode)
707                 {
708                 if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) goto err;
709                 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
710                 }
711         else
712                 {
713                 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
714                 }
715         
716         if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
717                 {
718                 unsigned long err = ERR_peek_last_error();
719                 
720                 if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
721                         {
722                         ERR_clear_error();
723                         ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
724                         }
725                 else
726                         ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB);
727                 goto err;
728                 }
729
730         if (y_bit != BN_is_odd(y))
731                 {
732                 if (BN_is_zero(y))
733                         {
734                         int kron;
735
736                         kron = BN_kronecker(x, &group->field, ctx);
737                         if (kron == -2) goto err;
738
739                         if (kron == 1)
740                                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSION_BIT);
741                         else
742                                 /* BN_mod_sqrt() should have cought this error (not a square) */
743                                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT);
744                         goto err;
745                         }
746                 if (!BN_usub(y, &group->field, y)) goto err;
747                 }
748         if (y_bit != BN_is_odd(y))
749                 {
750                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_INTERNAL_ERROR);
751                 goto err;
752                 }
753
754         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
755
756         ret = 1;
757
758  err:
759         BN_CTX_end(ctx);
760         if (new_ctx != NULL)
761                 BN_CTX_free(new_ctx);
762         return ret;
763         }
764
765
766 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
767         unsigned char *buf, size_t len, BN_CTX *ctx)
768         {
769         size_t ret;
770         BN_CTX *new_ctx = NULL;
771         int used_ctx = 0;
772         BIGNUM *x, *y;
773         size_t field_len, i, skip;
774
775         if ((form != POINT_CONVERSION_COMPRESSED)
776                 && (form != POINT_CONVERSION_UNCOMPRESSED)
777                 && (form != POINT_CONVERSION_HYBRID))
778                 {
779                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
780                 goto err;
781                 }
782
783         if (EC_POINT_is_at_infinity(group, point))
784                 {
785                 /* encodes to a single 0 octet */
786                 if (buf != NULL)
787                         {
788                         if (len < 1)
789                                 {
790                                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
791                                 return 0;
792                                 }
793                         buf[0] = 0;
794                         }
795                 return 1;
796                 }
797
798
799         /* ret := required output buffer length */
800         field_len = BN_num_bytes(&group->field);
801         ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
802
803         /* if 'buf' is NULL, just return required length */
804         if (buf != NULL)
805                 {
806                 if (len < ret)
807                         {
808                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
809                         goto err;
810                         }
811
812                 if (ctx == NULL)
813                         {
814                         ctx = new_ctx = BN_CTX_new();
815                         if (ctx == NULL)
816                                 return 0;
817                         }
818
819                 BN_CTX_start(ctx);
820                 used_ctx = 1;
821                 x = BN_CTX_get(ctx);
822                 y = BN_CTX_get(ctx);
823                 if (y == NULL) goto err;
824
825                 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
826
827                 if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
828                         buf[0] = form + 1;
829                 else
830                         buf[0] = form;
831         
832                 i = 1;
833                 
834                 skip = field_len - BN_num_bytes(x);
835                 if (skip > field_len)
836                         {
837                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
838                         goto err;
839                         }
840                 while (skip > 0)
841                         {
842                         buf[i++] = 0;
843                         skip--;
844                         }
845                 skip = BN_bn2bin(x, buf + i);
846                 i += skip;
847                 if (i != 1 + field_len)
848                         {
849                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
850                         goto err;
851                         }
852
853                 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
854                         {
855                         skip = field_len - BN_num_bytes(y);
856                         if (skip > field_len)
857                                 {
858                                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
859                                 goto err;
860                                 }
861                         while (skip > 0)
862                                 {
863                                 buf[i++] = 0;
864                                 skip--;
865                                 }
866                         skip = BN_bn2bin(y, buf + i);
867                         i += skip;
868                         }
869
870                 if (i != ret)
871                         {
872                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
873                         goto err;
874                         }
875                 }
876         
877         if (used_ctx)
878                 BN_CTX_end(ctx);
879         if (new_ctx != NULL)
880                 BN_CTX_free(new_ctx);
881         return ret;
882
883  err:
884         if (used_ctx)
885                 BN_CTX_end(ctx);
886         if (new_ctx != NULL)
887                 BN_CTX_free(new_ctx);
888         return 0;
889         }
890
891
892 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
893         const unsigned char *buf, size_t len, BN_CTX *ctx)
894         {
895         point_conversion_form_t form;
896         int y_bit;
897         BN_CTX *new_ctx = NULL;
898         BIGNUM *x, *y;
899         size_t field_len, enc_len;
900         int ret = 0;
901
902         if (len == 0)
903                 {
904                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
905                 return 0;
906                 }
907         form = buf[0];
908         y_bit = form & 1;
909         form = form & ~1U;
910         if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
911                 && (form != POINT_CONVERSION_UNCOMPRESSED)
912                 && (form != POINT_CONVERSION_HYBRID))
913                 {
914                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
915                 return 0;
916                 }
917         if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
918                 {
919                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
920                 return 0;
921                 }
922
923         if (form == 0)
924                 {
925                 if (len != 1)
926                         {
927                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
928                         return 0;
929                         }
930
931                 return EC_POINT_set_to_infinity(group, point);
932                 }
933         
934         field_len = BN_num_bytes(&group->field);
935         enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
936
937         if (len != enc_len)
938                 {
939                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
940                 return 0;
941                 }
942
943         if (ctx == NULL)
944                 {
945                 ctx = new_ctx = BN_CTX_new();
946                 if (ctx == NULL)
947                         return 0;
948                 }
949
950         BN_CTX_start(ctx);
951         x = BN_CTX_get(ctx);
952         y = BN_CTX_get(ctx);
953         if (y == NULL) goto err;
954
955         if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
956         if (BN_ucmp(x, &group->field) >= 0)
957                 {
958                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
959                 goto err;
960                 }
961
962         if (form == POINT_CONVERSION_COMPRESSED)
963                 {
964                 if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) goto err;
965                 }
966         else
967                 {
968                 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
969                 if (BN_ucmp(y, &group->field) >= 0)
970                         {
971                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
972                         goto err;
973                         }
974                 if (form == POINT_CONVERSION_HYBRID)
975                         {
976                         if (y_bit != BN_is_odd(y))
977                                 {
978                                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
979                                 goto err;
980                                 }
981                         }
982
983                 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
984                 }
985         
986         if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
987                 {
988                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
989                 goto err;
990                 }
991
992         ret = 1;
993         
994  err:
995         BN_CTX_end(ctx);
996         if (new_ctx != NULL)
997                 BN_CTX_free(new_ctx);
998         return ret;
999         }
1000
1001
1002 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1003         {
1004         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1005         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1006         const BIGNUM *p;
1007         BN_CTX *new_ctx = NULL;
1008         BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
1009         int ret = 0;
1010         
1011         if (a == b)
1012                 return EC_POINT_dbl(group, r, a, ctx);
1013         if (EC_POINT_is_at_infinity(group, a))
1014                 return EC_POINT_copy(r, b);
1015         if (EC_POINT_is_at_infinity(group, b))
1016                 return EC_POINT_copy(r, a);
1017         
1018         field_mul = group->meth->field_mul;
1019         field_sqr = group->meth->field_sqr;
1020         p = &group->field;
1021
1022         if (ctx == NULL)
1023                 {
1024                 ctx = new_ctx = BN_CTX_new();
1025                 if (ctx == NULL)
1026                         return 0;
1027                 }
1028
1029         BN_CTX_start(ctx);
1030         n0 = BN_CTX_get(ctx);
1031         n1 = BN_CTX_get(ctx);
1032         n2 = BN_CTX_get(ctx);
1033         n3 = BN_CTX_get(ctx);
1034         n4 = BN_CTX_get(ctx);
1035         n5 = BN_CTX_get(ctx);
1036         n6 = BN_CTX_get(ctx);
1037         if (n6 == NULL) goto end;
1038
1039         /* Note that in this function we must not read components of 'a' or 'b'
1040          * once we have written the corresponding components of 'r'.
1041          * ('r' might be one of 'a' or 'b'.)
1042          */
1043
1044         /* n1, n2 */
1045         if (b->Z_is_one)
1046                 {
1047                 if (!BN_copy(n1, &a->X)) goto end;
1048                 if (!BN_copy(n2, &a->Y)) goto end;
1049                 /* n1 = X_a */
1050                 /* n2 = Y_a */
1051                 }
1052         else
1053                 {
1054                 if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
1055                 if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
1056                 /* n1 = X_a * Z_b^2 */
1057
1058                 if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
1059                 if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
1060                 /* n2 = Y_a * Z_b^3 */
1061                 }
1062
1063         /* n3, n4 */
1064         if (a->Z_is_one)
1065                 {
1066                 if (!BN_copy(n3, &b->X)) goto end;
1067                 if (!BN_copy(n4, &b->Y)) goto end;
1068                 /* n3 = X_b */
1069                 /* n4 = Y_b */
1070                 }
1071         else
1072                 {
1073                 if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
1074                 if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
1075                 /* n3 = X_b * Z_a^2 */
1076
1077                 if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
1078                 if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
1079                 /* n4 = Y_b * Z_a^3 */
1080                 }
1081
1082         /* n5, n6 */
1083         if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
1084         if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
1085         /* n5 = n1 - n3 */
1086         /* n6 = n2 - n4 */
1087
1088         if (BN_is_zero(n5))
1089                 {
1090                 if (BN_is_zero(n6))
1091                         {
1092                         /* a is the same point as b */
1093                         BN_CTX_end(ctx);
1094                         ret = EC_POINT_dbl(group, r, a, ctx);
1095                         ctx = NULL;
1096                         goto end;
1097                         }
1098                 else
1099                         {
1100                         /* a is the inverse of b */
1101                         BN_zero(&r->Z);
1102                         r->Z_is_one = 0;
1103                         ret = 1;
1104                         goto end;
1105                         }
1106                 }
1107
1108         /* 'n7', 'n8' */
1109         if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
1110         if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
1111         /* 'n7' = n1 + n3 */
1112         /* 'n8' = n2 + n4 */
1113
1114         /* Z_r */
1115         if (a->Z_is_one && b->Z_is_one)
1116                 {
1117                 if (!BN_copy(&r->Z, n5)) goto end;
1118                 }
1119         else
1120                 {
1121                 if (a->Z_is_one)
1122                         { if (!BN_copy(n0, &b->Z)) goto end; }
1123                 else if (b->Z_is_one)
1124                         { if (!BN_copy(n0, &a->Z)) goto end; }
1125                 else
1126                         { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
1127                 if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
1128                 }
1129         r->Z_is_one = 0;
1130         /* Z_r = Z_a * Z_b * n5 */
1131
1132         /* X_r */
1133         if (!field_sqr(group, n0, n6, ctx)) goto end;
1134         if (!field_sqr(group, n4, n5, ctx)) goto end;
1135         if (!field_mul(group, n3, n1, n4, ctx)) goto end;
1136         if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
1137         /* X_r = n6^2 - n5^2 * 'n7' */
1138         
1139         /* 'n9' */
1140         if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
1141         if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
1142         /* n9 = n5^2 * 'n7' - 2 * X_r */
1143
1144         /* Y_r */
1145         if (!field_mul(group, n0, n0, n6, ctx)) goto end;
1146         if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
1147         if (!field_mul(group, n1, n2, n5, ctx)) goto end;
1148         if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
1149         if (BN_is_odd(n0))
1150                 if (!BN_add(n0, n0, p)) goto end;
1151         /* now  0 <= n0 < 2*p,  and n0 is even */
1152         if (!BN_rshift1(&r->Y, n0)) goto end;
1153         /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
1154
1155         ret = 1;
1156
1157  end:
1158         if (ctx) /* otherwise we already called BN_CTX_end */
1159                 BN_CTX_end(ctx);
1160         if (new_ctx != NULL)
1161                 BN_CTX_free(new_ctx);
1162         return ret;
1163         }
1164
1165
1166 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
1167         {
1168         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1169         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1170         const BIGNUM *p;
1171         BN_CTX *new_ctx = NULL;
1172         BIGNUM *n0, *n1, *n2, *n3;
1173         int ret = 0;
1174         
1175         if (EC_POINT_is_at_infinity(group, a))
1176                 {
1177                 BN_zero(&r->Z);
1178                 r->Z_is_one = 0;
1179                 return 1;
1180                 }
1181
1182         field_mul = group->meth->field_mul;
1183         field_sqr = group->meth->field_sqr;
1184         p = &group->field;
1185
1186         if (ctx == NULL)
1187                 {
1188                 ctx = new_ctx = BN_CTX_new();
1189                 if (ctx == NULL)
1190                         return 0;
1191                 }
1192
1193         BN_CTX_start(ctx);
1194         n0 = BN_CTX_get(ctx);
1195         n1 = BN_CTX_get(ctx);
1196         n2 = BN_CTX_get(ctx);
1197         n3 = BN_CTX_get(ctx);
1198         if (n3 == NULL) goto err;
1199
1200         /* Note that in this function we must not read components of 'a'
1201          * once we have written the corresponding components of 'r'.
1202          * ('r' might the same as 'a'.)
1203          */
1204
1205         /* n1 */
1206         if (a->Z_is_one)
1207                 {
1208                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1209                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1210                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1211                 if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
1212                 /* n1 = 3 * X_a^2 + a_curve */
1213                 }
1214         else if (group->a_is_minus3)
1215                 {
1216                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1217                 if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
1218                 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
1219                 if (!field_mul(group, n1, n0, n2, ctx)) goto err;
1220                 if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
1221                 if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
1222                 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
1223                  *    = 3 * X_a^2 - 3 * Z_a^4 */
1224                 }
1225         else
1226                 {
1227                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
1228                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
1229                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
1230                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
1231                 if (!field_sqr(group, n1, n1, ctx)) goto err;
1232                 if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
1233                 if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
1234                 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
1235                 }
1236
1237         /* Z_r */
1238         if (a->Z_is_one)
1239                 {
1240                 if (!BN_copy(n0, &a->Y)) goto err;
1241                 }
1242         else
1243                 {
1244                 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
1245                 }
1246         if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
1247         r->Z_is_one = 0;
1248         /* Z_r = 2 * Y_a * Z_a */
1249
1250         /* n2 */
1251         if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
1252         if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
1253         if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
1254         /* n2 = 4 * X_a * Y_a^2 */
1255
1256         /* X_r */
1257         if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
1258         if (!field_sqr(group, &r->X, n1, ctx)) goto err;
1259         if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
1260         /* X_r = n1^2 - 2 * n2 */
1261         
1262         /* n3 */
1263         if (!field_sqr(group, n0, n3, ctx)) goto err;
1264         if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
1265         /* n3 = 8 * Y_a^4 */
1266         
1267         /* Y_r */
1268         if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
1269         if (!field_mul(group, n0, n1, n0, ctx)) goto err;
1270         if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
1271         /* Y_r = n1 * (n2 - X_r) - n3 */
1272
1273         ret = 1;
1274
1275  err:
1276         BN_CTX_end(ctx);
1277         if (new_ctx != NULL)
1278                 BN_CTX_free(new_ctx);
1279         return ret;
1280         }
1281
1282
1283 int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1284         {
1285         if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y))
1286                 /* point is its own inverse */
1287                 return 1;
1288         
1289         return BN_usub(&point->Y, &group->field, &point->Y);
1290         }
1291
1292
1293 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
1294         {
1295         return BN_is_zero(&point->Z);
1296         }
1297
1298
1299 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
1300         {
1301         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1302         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1303         const BIGNUM *p;
1304         BN_CTX *new_ctx = NULL;
1305         BIGNUM *rh, *tmp, *Z4, *Z6;
1306         int ret = -1;
1307
1308         if (EC_POINT_is_at_infinity(group, point))
1309                 return 1;
1310         
1311         field_mul = group->meth->field_mul;
1312         field_sqr = group->meth->field_sqr;
1313         p = &group->field;
1314
1315         if (ctx == NULL)
1316                 {
1317                 ctx = new_ctx = BN_CTX_new();
1318                 if (ctx == NULL)
1319                         return -1;
1320                 }
1321
1322         BN_CTX_start(ctx);
1323         rh = BN_CTX_get(ctx);
1324         tmp = BN_CTX_get(ctx);
1325         Z4 = BN_CTX_get(ctx);
1326         Z6 = BN_CTX_get(ctx);
1327         if (Z6 == NULL) goto err;
1328
1329         /* We have a curve defined by a Weierstrass equation
1330          *      y^2 = x^3 + a*x + b.
1331          * The point to consider is given in Jacobian projective coordinates
1332          * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1333          * Substituting this and multiplying by  Z^6  transforms the above equation into
1334          *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1335          * To test this, we add up the right-hand side in 'rh'.
1336          */
1337
1338         /* rh := X^2 */
1339         if (!field_sqr(group, rh, &point->X, ctx)) goto err;
1340
1341         if (!point->Z_is_one)
1342                 {
1343                 if (!field_sqr(group, tmp, &point->Z, ctx)) goto err;
1344                 if (!field_sqr(group, Z4, tmp, ctx)) goto err;
1345                 if (!field_mul(group, Z6, Z4, tmp, ctx)) goto err;
1346
1347                 /* rh := (rh + a*Z^4)*X */
1348                 if (group->a_is_minus3)
1349                         {
1350                         if (!BN_mod_lshift1_quick(tmp, Z4, p)) goto err;
1351                         if (!BN_mod_add_quick(tmp, tmp, Z4, p)) goto err;
1352                         if (!BN_mod_sub_quick(rh, rh, tmp, p)) goto err;
1353                         if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1354                         }
1355                 else
1356                         {
1357                         if (!field_mul(group, tmp, Z4, &group->a, ctx)) goto err;
1358                         if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1359                         if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1360                         }
1361
1362                 /* rh := rh + b*Z^6 */
1363                 if (!field_mul(group, tmp, &group->b, Z6, ctx)) goto err;
1364                 if (!BN_mod_add_quick(rh, rh, tmp, p)) goto err;
1365                 }
1366         else
1367                 {
1368                 /* point->Z_is_one */
1369
1370                 /* rh := (rh + a)*X */
1371                 if (!BN_mod_add_quick(rh, rh, &group->a, p)) goto err;
1372                 if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1373                 /* rh := rh + b */
1374                 if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1375                 }
1376
1377         /* 'lh' := Y^2 */
1378         if (!field_sqr(group, tmp, &point->Y, ctx)) goto err;
1379
1380         ret = (0 == BN_ucmp(tmp, rh));
1381
1382  err:
1383         BN_CTX_end(ctx);
1384         if (new_ctx != NULL)
1385                 BN_CTX_free(new_ctx);
1386         return ret;
1387         }
1388
1389
1390 int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
1391         {
1392         /* return values:
1393          *  -1   error
1394          *   0   equal (in affine coordinates)
1395          *   1   not equal
1396          */
1397
1398         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
1399         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
1400         BN_CTX *new_ctx = NULL;
1401         BIGNUM *tmp1, *tmp2, *Za23, *Zb23;
1402         const BIGNUM *tmp1_, *tmp2_;
1403         int ret = -1;
1404         
1405         if (EC_POINT_is_at_infinity(group, a))
1406                 {
1407                 return EC_POINT_is_at_infinity(group, b) ? 0 : 1;
1408                 }
1409         
1410         if (a->Z_is_one && b->Z_is_one)
1411                 {
1412                 return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1;
1413                 }
1414
1415         field_mul = group->meth->field_mul;
1416         field_sqr = group->meth->field_sqr;
1417
1418         if (ctx == NULL)
1419                 {
1420                 ctx = new_ctx = BN_CTX_new();
1421                 if (ctx == NULL)
1422                         return -1;
1423                 }
1424
1425         BN_CTX_start(ctx);
1426         tmp1 = BN_CTX_get(ctx);
1427         tmp2 = BN_CTX_get(ctx);
1428         Za23 = BN_CTX_get(ctx);
1429         Zb23 = BN_CTX_get(ctx);
1430         if (Zb23 == NULL) goto end;
1431
1432         /* We have to decide whether
1433          *     (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3),
1434          * or equivalently, whether
1435          *     (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3).
1436          */
1437
1438         if (!b->Z_is_one)
1439                 {
1440                 if (!field_sqr(group, Zb23, &b->Z, ctx)) goto end;
1441                 if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) goto end;
1442                 tmp1_ = tmp1;
1443                 }
1444         else
1445                 tmp1_ = &a->X;
1446         if (!a->Z_is_one)
1447                 {
1448                 if (!field_sqr(group, Za23, &a->Z, ctx)) goto end;
1449                 if (!field_mul(group, tmp2, &b->X, Za23, ctx)) goto end;
1450                 tmp2_ = tmp2;
1451                 }
1452         else
1453                 tmp2_ = &b->X;
1454         
1455         /* compare  X_a*Z_b^2  with  X_b*Z_a^2 */
1456         if (BN_cmp(tmp1_, tmp2_) != 0)
1457                 {
1458                 ret = 1; /* points differ */
1459                 goto end;
1460                 }
1461
1462
1463         if (!b->Z_is_one)
1464                 {
1465                 if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) goto end;
1466                 if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) goto end;
1467                 /* tmp1_ = tmp1 */
1468                 }
1469         else
1470                 tmp1_ = &a->Y;
1471         if (!a->Z_is_one)
1472                 {
1473                 if (!field_mul(group, Za23, Za23, &a->Z, ctx)) goto end;
1474                 if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) goto end;
1475                 /* tmp2_ = tmp2 */
1476                 }
1477         else
1478                 tmp2_ = &b->Y;
1479
1480         /* compare  Y_a*Z_b^3  with  Y_b*Z_a^3 */
1481         if (BN_cmp(tmp1_, tmp2_) != 0)
1482                 {
1483                 ret = 1; /* points differ */
1484                 goto end;
1485                 }
1486
1487         /* points are equal */
1488         ret = 0;
1489
1490  end:
1491         BN_CTX_end(ctx);
1492         if (new_ctx != NULL)
1493                 BN_CTX_free(new_ctx);
1494         return ret;
1495         }
1496
1497
1498 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1499         {
1500         BN_CTX *new_ctx = NULL;
1501         BIGNUM *x, *y;
1502         int ret = 0;
1503
1504         if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1505                 return 1;
1506
1507         if (ctx == NULL)
1508                 {
1509                 ctx = new_ctx = BN_CTX_new();
1510                 if (ctx == NULL)
1511                         return 0;
1512                 }
1513
1514         BN_CTX_start(ctx);
1515         x = BN_CTX_get(ctx);
1516         y = BN_CTX_get(ctx);
1517         if (y == NULL) goto err;
1518
1519         if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1520         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1521         if (!point->Z_is_one)
1522                 {
1523                 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1524                 goto err;
1525                 }
1526         
1527         ret = 1;
1528
1529  err:
1530         BN_CTX_end(ctx);
1531         if (new_ctx != NULL)
1532                 BN_CTX_free(new_ctx);
1533         return ret;
1534         }
1535
1536
1537 int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
1538         {
1539         BN_CTX *new_ctx = NULL;
1540         BIGNUM *tmp0, *tmp1;
1541         size_t pow2 = 0;
1542         BIGNUM **heap = NULL;
1543         size_t i;
1544         int ret = 0;
1545
1546         if (num == 0)
1547                 return 1;
1548
1549         if (ctx == NULL)
1550                 {
1551                 ctx = new_ctx = BN_CTX_new();
1552                 if (ctx == NULL)
1553                         return 0;
1554                 }
1555
1556         BN_CTX_start(ctx);
1557         tmp0 = BN_CTX_get(ctx);
1558         tmp1 = BN_CTX_get(ctx);
1559         if (tmp0  == NULL || tmp1 == NULL) goto err;
1560
1561         /* Before converting the individual points, compute inverses of all Z values.
1562          * Modular inversion is rather slow, but luckily we can do with a single
1563          * explicit inversion, plus about 3 multiplications per input value.
1564          */
1565
1566         pow2 = 1;
1567         while (num > pow2)
1568                 pow2 <<= 1;
1569         /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
1570          * We need twice that. */
1571         pow2 <<= 1;
1572
1573         heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
1574         if (heap == NULL) goto err;
1575         
1576         /* The array is used as a binary tree, exactly as in heapsort:
1577          *
1578          *                               heap[1]
1579          *                 heap[2]                     heap[3]
1580          *          heap[4]       heap[5]       heap[6]       heap[7]
1581          *   heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
1582          *
1583          * We put the Z's in the last line;
1584          * then we set each other node to the product of its two child-nodes (where
1585          * empty or 0 entries are treated as ones);
1586          * then we invert heap[1];
1587          * then we invert each other node by replacing it by the product of its
1588          * parent (after inversion) and its sibling (before inversion).
1589          */
1590         heap[0] = NULL;
1591         for (i = pow2/2 - 1; i > 0; i--)
1592                 heap[i] = NULL;
1593         for (i = 0; i < num; i++)
1594                 heap[pow2/2 + i] = &points[i]->Z;
1595         for (i = pow2/2 + num; i < pow2; i++)
1596                 heap[i] = NULL;
1597         
1598         /* set each node to the product of its children */
1599         for (i = pow2/2 - 1; i > 0; i--)
1600                 {
1601                 heap[i] = BN_new();
1602                 if (heap[i] == NULL) goto err;
1603                 
1604                 if (heap[2*i] != NULL)
1605                         {
1606                         if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
1607                                 {
1608                                 if (!BN_copy(heap[i], heap[2*i])) goto err;
1609                                 }
1610                         else
1611                                 {
1612                                 if (BN_is_zero(heap[2*i]))
1613                                         {
1614                                         if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
1615                                         }
1616                                 else
1617                                         {
1618                                         if (!group->meth->field_mul(group, heap[i],
1619                                                 heap[2*i], heap[2*i + 1], ctx)) goto err;
1620                                         }
1621                                 }
1622                         }
1623                 }
1624
1625         /* invert heap[1] */
1626         if (!BN_is_zero(heap[1]))
1627                 {
1628                 if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
1629                         {
1630                         ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
1631                         goto err;
1632                         }
1633                 }
1634         if (group->meth->field_encode != 0)
1635                 {
1636                 /* in the Montgomery case, we just turned  R*H  (representing H)
1637                  * into  1/(R*H),  but we need  R*(1/H)  (representing 1/H);
1638                  * i.e. we have need to multiply by the Montgomery factor twice */
1639                 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1640                 if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
1641                 }
1642
1643         /* set other heap[i]'s to their inverses */
1644         for (i = 2; i < pow2/2 + num; i += 2)
1645                 {
1646                 /* i is even */
1647                 if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
1648                         {
1649                         if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
1650                         if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
1651                         if (!BN_copy(heap[i], tmp0)) goto err;
1652                         if (!BN_copy(heap[i + 1], tmp1)) goto err;
1653                         }
1654                 else
1655                         {
1656                         if (!BN_copy(heap[i], heap[i/2])) goto err;
1657                         }
1658                 }
1659
1660         /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
1661         for (i = 0; i < num; i++)
1662                 {
1663                 EC_POINT *p = points[i];
1664                 
1665                 if (!BN_is_zero(&p->Z))
1666                         {
1667                         /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
1668
1669                         if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
1670                         if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
1671
1672                         if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
1673                         if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
1674                 
1675                         if (group->meth->field_set_to_one != 0)
1676                                 {
1677                                 if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
1678                                 }
1679                         else
1680                                 {
1681                                 if (!BN_one(&p->Z)) goto err;
1682                                 }
1683                         p->Z_is_one = 1;
1684                         }
1685                 }
1686
1687         ret = 1;
1688                 
1689  err:
1690         BN_CTX_end(ctx);
1691         if (new_ctx != NULL)
1692                 BN_CTX_free(new_ctx);
1693         if (heap != NULL)
1694                 {
1695                 /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
1696                 for (i = pow2/2 - 1; i > 0; i--)
1697                         {
1698                         if (heap[i] != NULL)
1699                                 BN_clear_free(heap[i]);
1700                         }
1701                 OPENSSL_free(heap);
1702                 }
1703         return ret;
1704         }
1705
1706
1707 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1708         {
1709         return BN_mod_mul(r, a, b, &group->field, ctx);
1710         }
1711
1712
1713 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1714         {
1715         return BN_mod_sqr(r, a, &group->field, ctx);
1716         }