More method functions for EC_GFp_simple_method.
[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 /* ====================================================================
5  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * 1. Redistributions of source code must retain the above copyright
12  *    notice, this list of conditions and the following disclaimer. 
13  *
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in
16  *    the documentation and/or other materials provided with the
17  *    distribution.
18  *
19  * 3. All advertising materials mentioning features or use of this
20  *    software must display the following acknowledgment:
21  *    "This product includes software developed by the OpenSSL Project
22  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
23  *
24  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
25  *    endorse or promote products derived from this software without
26  *    prior written permission. For written permission, please contact
27  *    openssl-core@openssl.org.
28  *
29  * 5. Products derived from this software may not be called "OpenSSL"
30  *    nor may "OpenSSL" appear in their names without prior written
31  *    permission of the OpenSSL Project.
32  *
33  * 6. Redistributions of any form whatsoever must retain the following
34  *    acknowledgment:
35  *    "This product includes software developed by the OpenSSL Project
36  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
37  *
38  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
39  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
40  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
41  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
42  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
44  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
45  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
46  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
47  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
49  * OF THE POSSIBILITY OF SUCH DAMAGE.
50  * ====================================================================
51  *
52  * This product includes cryptographic software written by Eric Young
53  * (eay@cryptsoft.com).  This product includes software written by Tim
54  * Hudson (tjh@cryptsoft.com).
55  *
56  */
57
58 #include <openssl/err.h>
59
60 #include "ec_lcl.h"
61
62
63 const EC_METHOD *EC_GFp_simple_method(void)
64         {
65         static const EC_METHOD ret = {
66                 ec_GFp_simple_group_init,
67                 ec_GFp_simple_group_set_curve_GFp,
68                 ec_GFp_simple_group_finish,
69                 ec_GFp_simple_group_clear_finish,
70                 ec_GFp_simple_group_copy,
71                 ec_GFp_simple_group_set_generator,
72                 /* TODO: 'set' and 'get' functions for EC_GROUPs */
73                 ec_GFp_simple_point_init,
74                 ec_GFp_simple_point_finish,
75                 ec_GFp_simple_point_clear_finish,
76                 ec_GFp_simple_point_copy,
77                 ec_GFp_simple_point_set_to_infinity,
78                 ec_GFp_simple_point_set_affine_coordinates_GFp,
79                 ec_GFp_simple_point_get_affine_coordinates_GFp,
80                 /* TODO: other 'set' and 'get' functions for EC_POINTs */
81                 ec_GFp_simple_point2oct,
82                 ec_GFp_simple_oct2point,
83                 ec_GFp_simple_add,
84                 ec_GFp_simple_dbl,
85                 ec_GFp_simple_is_at_infinity,
86                 ec_GFp_simple_is_on_curve,
87                 ec_GFp_simple_make_affine,
88                 ec_GFp_simple_field_mul,
89                 ec_GFp_simple_field_sqr,
90                 0 /* field_encode */,
91                 0 /* field_decode */ };
92
93         return &ret;
94         }
95
96
97 int ec_GFp_simple_group_init(EC_GROUP *group)
98         {
99         BN_init(&group->field);
100         BN_init(&group->a);
101         BN_init(&group->b);
102         group->a_is_minus3 = 0;
103         group->generator = NULL;
104         BN_init(&group->order);
105         BN_init(&group->cofactor);
106         return 1;
107         }
108
109
110 int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *group,
111         const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
112         {
113         int ret = 0;
114         BN_CTX *new_ctx = NULL;
115         BIGNUM *tmp_a;
116         
117         if (ctx == NULL)
118                 {
119                 ctx = new_ctx = BN_CTX_new();
120                 if (ctx == NULL)
121                         return 0;
122                 }
123
124         BN_CTX_start(ctx);
125         tmp_a = BN_CTX_get(ctx);
126         if (tmp_a == NULL) goto err;
127
128         /* group->field */
129         if (!BN_copy(&group->field, p)) goto err;
130         group->field.neg = 0;
131
132         /* group->a */
133         if (!BN_nnmod(tmp_a, a, p, ctx)) goto err;
134         if (group->meth->field_encode)
135                 { if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) goto err; }     
136         else
137                 if (!BN_copy(&group->a, tmp_a)) goto err;
138         
139         /* group->b */
140         if (!BN_nnmod(&group->b, b, p, ctx)) goto err;
141         if (group->meth->field_encode)
142                 if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) goto err;
143         
144         /* group->a_is_minus3 */
145         if (!BN_add_word(tmp_a, 3)) goto err;
146         group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field));
147
148         ret = 1;
149
150  err:
151         BN_CTX_end(ctx);
152         if (new_ctx != NULL)
153                 BN_CTX_free(new_ctx);
154         return ret;
155         }
156
157
158 void ec_GFp_simple_group_finish(EC_GROUP *group)
159         {
160         BN_free(&group->field);
161         BN_free(&group->a);
162         BN_free(&group->b);
163         if (group->generator != NULL)
164                 EC_POINT_free(group->generator);
165         BN_free(&group->order);
166         BN_free(&group->cofactor);
167         }
168
169
170 void ec_GFp_simple_group_clear_finish(EC_GROUP *group)
171         {
172         BN_clear_free(&group->field);
173         BN_clear_free(&group->a);
174         BN_clear_free(&group->b);
175         if (group->generator != NULL)
176                 {
177                 EC_POINT_clear_free(group->generator);
178                 group->generator = NULL;
179                 }
180         BN_clear_free(&group->order);
181         BN_clear_free(&group->cofactor);
182         }
183
184
185 int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src)
186         {
187         if (!BN_copy(&dest->field, &src->field)) return 0;
188         if (!BN_copy(&dest->a, &src->a)) return 0;
189         if (!BN_copy(&dest->b, &src->b)) return 0;
190
191         dest->a_is_minus3 = src->a_is_minus3;
192
193         if (src->generator != NULL)
194                 {
195                 if (dest->generator == NULL)
196                         {
197                         dest->generator = EC_POINT_new(dest);
198                         if (dest->generator == NULL) return 0;
199                         }
200                 if (!EC_POINT_copy(dest->generator, src->generator)) return 0;
201                 }
202         else
203                 {
204                 /* src->generator == NULL */
205                 if (dest->generator != NULL)
206                         {
207                         EC_POINT_clear_free(dest->generator);
208                         dest->generator = NULL;
209                         }
210                 }
211
212         if (!BN_copy(&dest->order, &src->order)) return 0;
213         if (!BN_copy(&dest->cofactor, &src->cofactor)) return 0;
214
215         return 1;
216         }
217
218
219 int ec_GFp_simple_group_set_generator(EC_GROUP *group, const EC_POINT *generator,
220         const BIGNUM *order, const BIGNUM *cofactor)
221         {
222         if (generator)
223                 {
224                 ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_GENERATOR, ERR_R_PASSED_NULL_PARAMETER);
225                 return 0   ;
226                 }
227
228         if (group->generator == NULL)
229                 {
230                 group->generator = EC_POINT_new(group);
231                 if (group->generator == NULL) return 0;
232                 }
233         if (!EC_POINT_copy(group->generator, generator)) return 0;
234
235         if (order != NULL)
236                 { if (!BN_copy(&group->order, order)) return 0; }       
237         else
238                 { if (!BN_zero(&group->order)) return 0; }      
239
240         if (cofactor != NULL)
241                 { if (!BN_copy(&group->cofactor, cofactor)) return 0; } 
242         else
243                 { if (!BN_zero(&group->cofactor)) return 0; }   
244
245         return 1;
246         }
247
248
249 /* TODO: 'set' and 'get' functions for EC_GROUPs */
250
251
252 int ec_GFp_simple_point_init(EC_POINT *point)
253         {
254         BN_init(&point->X);
255         BN_init(&point->Y);
256         BN_init(&point->Z);
257         point->Z_is_one = 0;
258
259         return 1;
260         }
261
262
263 void ec_GFp_simple_point_finish(EC_POINT *point)
264         {
265         BN_free(&point->X);
266         BN_free(&point->Y);
267         BN_free(&point->Z);
268         }
269
270
271 void ec_GFp_simple_point_clear_finish(EC_POINT *point)
272         {
273         BN_clear_free(&point->X);
274         BN_clear_free(&point->Y);
275         BN_clear_free(&point->Z);
276         point->Z_is_one = 0;
277         }
278
279
280 int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src)
281         {
282         if (!BN_copy(&dest->X, &src->X)) return 0;
283         if (!BN_copy(&dest->Y, &src->Y)) return 0;
284         if (!BN_copy(&dest->Z, &src->Z)) return 0;
285         dest->Z_is_one = src->Z_is_one;
286
287         return 1;
288         }
289
290
291 int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
292         {
293         point->Z_is_one = 0;
294         return (BN_zero(&point->Z));
295         }
296
297
298 int ec_GFp_simple_point_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
299         const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
300         {
301         BN_CTX *new_ctx = NULL;
302         int ret = 0;
303
304         if (!BN_copy(&point->X, x)) goto err;
305         if (!BN_copy(&point->Y, y)) goto err;
306         if (!BN_one(&point->Z)) goto err;
307
308         if (group->meth->field_encode)
309                 {
310                 if (ctx == NULL)
311                         {
312                         ctx = new_ctx = BN_CTX_new();
313                         if (ctx == NULL)
314                                 return 0;
315                         }
316                 
317                 if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) goto err;
318                 if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) goto err;
319                 if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
320                 }
321
322         point->Z_is_one = 1;
323         
324  err:
325         if (new_ctx != NULL)
326                 BN_CTX_free(new_ctx);
327         return ret;
328         }
329
330
331 int ec_GFp_simple_point_get_affine_coordinates_GFp(const EC_GROUP *group, const EC_POINT *point,
332         BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
333         {
334         BN_CTX *new_ctx = NULL;
335         BIGNUM *X, *Y, *Z, *Z_1, *Z_2, *Z_3;
336         const BIGNUM *X_, *Y_, *Z_;
337         int ret = 0;
338
339         if (EC_POINT_is_at_infinity(group, point))
340                 {
341                 ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP, EC_R_POINT_AT_INFINITY);
342                 return 0;
343                 }
344
345         if (ctx == NULL)
346                 {
347                 ctx = new_ctx = BN_CTX_new();
348                 if (ctx == NULL)
349                         return 0;
350                 }
351
352         BN_CTX_start(ctx);
353         X = BN_CTX_get(ctx);
354         Y = BN_CTX_get(ctx);
355         Z = BN_CTX_get(ctx);
356         Z_1 = BN_CTX_get(ctx);
357         Z_2 = BN_CTX_get(ctx);
358         Z_3 = BN_CTX_get(ctx);
359         if (Z_3 == NULL) goto err;
360
361         /* transform  (X, Y, Z)  into  (x, y) := (X/Z^2, Y/Z^3) */
362         
363         if (group->meth->field_decode)
364                 {
365                 if (!group->meth->field_decode(group, X, &point->X, ctx)) goto err;
366                 if (!group->meth->field_decode(group, Y, &point->Y, ctx)) goto err;
367                 if (!group->meth->field_decode(group, Z, &point->Z, ctx)) goto err;
368                 X_ = X; Y_ = Y; Z_ = Z;
369                 }
370         else
371                 {
372                 X_ = &point->X;
373                 Y_ = &point->Y;
374                 Z_ = &point->Z;
375                 }
376         
377         if (BN_is_one(Z_))
378                 {
379                 if (!BN_copy(x, X_)) goto err;
380                 if (!BN_copy(y, Y_)) goto err;
381                 }
382         else
383                 {
384                 if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx))
385                         {
386                         ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP, ERR_R_BN_LIB);
387                         goto err;
388                         }
389                 if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
390                 if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
391         
392                 if (!BN_mod_mul(x, X_, Z_2, &group->field, ctx)) goto err;
393                 if (!BN_mod_mul(y, Y_, Z_3, &group->field, ctx)) goto err;
394                 }
395
396         ret = 1;
397
398  err:
399         BN_CTX_end(ctx);
400         if (new_ctx != NULL)
401                 BN_CTX_free(new_ctx);
402         return ret;
403         }
404
405
406 /* TODO: other 'set' and 'get' functions for EC_POINTs */
407
408
409 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form,
410         unsigned char *buf, size_t len, BN_CTX *ctx)
411         {
412         size_t ret;
413         BN_CTX *new_ctx = NULL;
414         int used_ctx = 0;
415         BIGNUM *x, *y;
416         size_t field_len, i, skip;
417
418         if ((form != POINT_CONVERSION_COMPRESSED)
419                 && (form != POINT_CONVERSION_UNCOMPRESSED)
420                 && (form != POINT_CONVERSION_HYBRID))
421                 {
422                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
423                 goto err;
424                 }
425
426         if (EC_POINT_is_at_infinity(group, point))
427                 {
428                 /* encodes to a single 0 octet */
429                 if (buf != NULL)
430                         {
431                         if (len < 1)
432                                 {
433                                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
434                                 return 0;
435                                 }
436                         buf[0] = 0;
437                         }
438                 return 1;
439                 }
440
441
442         /* ret := required output buffer length */
443         field_len = BN_num_bytes(&group->field);
444         ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
445
446         /* if 'buf' is NULL, just return required length */
447         if (buf != NULL)
448                 {
449                 if (len < ret)
450                         {
451                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
452                         goto err;
453                         }
454
455                 if (ctx == NULL)
456                         {
457                         ctx = new_ctx = BN_CTX_new();
458                         if (ctx == NULL)
459                                 return 0;
460                         }
461
462                 BN_CTX_start(ctx);
463                 used_ctx = 1;
464                 x = BN_CTX_get(ctx);
465                 y = BN_CTX_get(ctx);
466                 if (y == NULL) goto err;
467
468                 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
469
470                 if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_bit_set(y, 0))
471                         buf[0] = form + 1;
472                 else
473                         buf[0] = form;
474         
475                 i = 1;
476                 
477                 skip = field_len - BN_num_bytes(x);
478                 if (skip > field_len)
479                         {
480                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
481                         goto err;
482                         }
483                 while (skip > 0)
484                         {
485                         buf[i++] = 0;
486                         skip--;
487                         }
488                 skip = BN_bn2bin(x, buf + i);
489                 i += skip;
490                 if (i != 1 + field_len)
491                         {
492                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
493                         goto err;
494                         }
495
496                 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID)
497                         {
498                         skip = field_len - BN_num_bytes(y);
499                         if (skip > field_len)
500                                 {
501                                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
502                                 goto err;
503                                 }
504                         while (skip > 0)
505                                 {
506                                 buf[i++] = 0;
507                                 skip--;
508                                 }
509                         skip = BN_bn2bin(y, buf + i);
510                         i += skip;
511                         }
512
513                 if (i != ret)
514                         {
515                         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
516                         goto err;
517                         }
518                 }
519         
520         if (used_ctx)
521                 BN_CTX_end(ctx);
522         if (new_ctx != NULL)
523                 BN_CTX_free(new_ctx);
524         return ret;
525
526  err:
527         if (used_ctx)
528                 BN_CTX_end(ctx);
529         if (new_ctx != NULL)
530                 BN_CTX_free(new_ctx);
531         return 0;
532         }
533
534
535 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
536         const unsigned char *buf, size_t len, BN_CTX *ctx)
537         {
538         point_conversion_form_t form;
539         int y_bit;
540         BN_CTX *new_ctx = NULL;
541         BIGNUM *x, *y;
542         size_t field_len, enc_len;
543         int ret = 0;
544
545         if (len <= 0)
546                 {
547                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
548                 return 0;
549                 }
550         form = buf[0];
551         y_bit = form & 1;
552         form = form & ~1;
553         if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
554                 && (form != POINT_CONVERSION_UNCOMPRESSED)
555                 && (form != POINT_CONVERSION_HYBRID))
556                 {
557                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
558                 return 0;
559                 }
560         if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit)
561                 {
562                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
563                 return 0;
564                 }
565
566         if (form == 0)
567                 {
568                 if (len != 1)
569                         {
570                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
571                         return 0;
572                         }
573
574                 return EC_POINT_set_to_infinity(group, point);
575                 }
576         
577         field_len = BN_num_bytes(&group->field);
578         enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len;
579
580         if (len != enc_len)
581                 {
582                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
583                 return 0;
584                 }
585
586         if (ctx == NULL)
587                 {
588                 ctx = new_ctx = BN_CTX_new();
589                 if (ctx == NULL)
590                         return 0;
591                 }
592
593         BN_CTX_start(ctx);
594         x = BN_CTX_get(ctx);
595         y = BN_CTX_get(ctx);
596         if (y == NULL) goto err;
597
598         if (!BN_bin2bn(buf + 1, field_len, x)) goto err;
599         if (BN_ucmp(x, &group->field) >= 0)
600                 {
601                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
602                 goto err;
603                 }
604
605         if (form != POINT_CONVERSION_COMPRESSED)
606                 {
607                 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err;
608                 if (BN_ucmp(y, &group->field) >= 0)
609                         {
610                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
611                         goto err;
612                         }
613                 if (form == POINT_CONVERSION_HYBRID)
614                         {
615                         if (y_bit != BN_is_bit_set(y, 0))
616                                 {
617                                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
618                                 goto err;
619                                 }
620                         }
621                 }
622
623         if (form == POINT_CONVERSION_COMPRESSED)
624                 {
625                 /* Recover y.  We have a Weierstrass equation
626                  *     y^2 = x^3 + a*x + b,
627                  * so  y  is one of the square roots of  x^3 + a*x + b.
628                  */
629
630                 BIGNUM *tmp1, *tmp2;
631                 
632                 tmp1 = BN_CTX_get(ctx);
633                 tmp2 = BN_CTX_get(ctx);
634                 if (tmp2 == NULL) goto err;
635                 
636                 /* tmp1 := x^3 */
637                 if (!BN_mod_sqr(tmp2, x, &group->field, ctx)) goto err;
638                 if (!BN_mod_mul(tmp1, tmp2, x, &group->field, ctx)) goto err;
639
640                 /* tmp1 := tmp1 + a*x */
641                 if (group->a_is_minus3)
642                         {
643                         if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) goto err;
644                         if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) goto err;
645                         if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
646                         }
647                 else
648                         {
649                         if (!BN_mod_mul(tmp2, &group->a, x, &group->field, ctx)) goto err;
650                         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
651                         }
652                 
653                 /* tmp1 := tmp1 + b */
654                 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) goto err;
655
656                 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
657                         {
658                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, ERR_R_BN_LIB);
659                         goto err;
660                         }
661
662                 if (y_bit != BN_is_bit_set(y, 0))
663                         {
664                         if (!BN_usub(y, &group->field, y)) goto err;
665                         }
666                 if (y_bit != BN_is_bit_set(y, 0))
667                         {
668                         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, ERR_R_INTERNAL_ERROR);
669                         goto err;
670                         }
671                 }
672         
673         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
674
675         if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
676                 {
677                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
678                 goto err;
679                 }
680
681         ret = 1;
682         
683  err:
684         BN_CTX_end(ctx);
685         if (new_ctx != NULL)
686                 BN_CTX_free(new_ctx);
687         return ret;
688         }
689
690
691 int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
692         {
693         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
694         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
695         const BIGNUM *p;
696         BN_CTX *new_ctx = NULL;
697         BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6;
698         int ret = 0;
699         
700         if (a == b)
701                 return EC_POINT_dbl(group, r, a, ctx);
702         if (EC_POINT_is_at_infinity(group, a))
703                 return EC_POINT_copy(r, b);
704         if (EC_POINT_is_at_infinity(group, b))
705                 return EC_POINT_copy(r, a);
706         
707         field_mul = group->meth->field_mul;
708         field_sqr = group->meth->field_sqr;
709         p = &group->field;
710
711         if (ctx == NULL)
712                 {
713                 ctx = new_ctx = BN_CTX_new();
714                 if (ctx == NULL)
715                         return 0;
716                 }
717
718         BN_CTX_start(ctx);
719         n0 = BN_CTX_get(ctx);
720         n1 = BN_CTX_get(ctx);
721         n2 = BN_CTX_get(ctx);
722         n3 = BN_CTX_get(ctx);
723         n4 = BN_CTX_get(ctx);
724         n5 = BN_CTX_get(ctx);
725         n6 = BN_CTX_get(ctx);
726         if (n6 == NULL) goto end;
727
728         /* n1, n2 */
729         if (b->Z_is_one)
730                 {
731                 if (!BN_copy(n1, &a->X)) goto end;
732                 if (!BN_copy(n2, &a->Y)) goto end;
733                 /* n1 = X_a */
734                 /* n2 = Y_a */
735                 }
736         else
737                 {
738                 if (!field_sqr(group, n0, &b->Z, ctx)) goto end;
739                 if (!field_mul(group, n1, &a->X, n0, ctx)) goto end;
740                 /* n1 = X_a * Z_b^2 */
741
742                 if (!field_mul(group, n0, n0, &b->Z, ctx)) goto end;
743                 if (!field_mul(group, n2, &a->Y, n0, ctx)) goto end;
744                 /* n2 = Y_a * Z_b^3 */
745                 }
746
747         /* n3, n4 */
748         if (a->Z_is_one)
749                 {
750                 if (!BN_copy(n3, &b->X)) goto end;
751                 if (!BN_copy(n4, &b->Y)) goto end;
752                 /* n3 = X_b */
753                 /* n4 = Y_b */
754                 }
755         else
756                 {
757                 if (!field_sqr(group, n0, &a->Z, ctx)) goto end;
758                 if (!field_mul(group, n3, &b->X, n0, ctx)) goto end;
759                 /* n3 = X_b * Z_a^2 */
760
761                 if (!field_mul(group, n0, n0, &a->Z, ctx)) goto end;
762                 if (!field_mul(group, n4, &b->Y, n0, ctx)) goto end;
763                 /* n4 = Y_b * Z_a^3 */
764                 }
765
766         /* n5, n6 */
767         if (!BN_mod_sub_quick(n5, n1, n3, p)) goto end;
768         if (!BN_mod_sub_quick(n6, n2, n4, p)) goto end;
769         /* n5 = n1 - n3 */
770         /* n6 = n2 - n4 */
771
772         if (BN_is_zero(n5))
773                 {
774                 if (BN_is_zero(n6))
775                         {
776                         /* a is the same point as b */
777                         BN_CTX_end(ctx);
778                         ret = EC_POINT_dbl(group, r, a, ctx);
779                         ctx = NULL;
780                         goto end;
781                         }
782                 else
783                         {
784                         /* a is the inverse of b */
785                         if (!BN_zero(&r->Z)) goto end;
786                         r->Z_is_one = 0;
787                         ret = 1;
788                         goto end;
789                         }
790                 }
791
792         /* 'n7', 'n8' */
793         if (!BN_mod_add_quick(n1, n1, n3, p)) goto end;
794         if (!BN_mod_add_quick(n2, n2, n4, p)) goto end;
795         /* 'n7' = n1 + n3 */
796         /* 'n8' = n2 + n4 */
797
798         /* Z_r */
799         if (a->Z_is_one && b->Z_is_one)
800                 {
801                 if (!BN_copy(&r->Z, n5)) goto end;
802                 }
803         else
804                 {
805                 if (a->Z_is_one)
806                         { if (!BN_copy(n0, &b->Z)) goto end; }
807                 else if (b->Z_is_one)
808                         { if (!BN_copy(n0, &a->Z)) goto end; }
809                 else
810                         { if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) goto end; }
811                 if (!field_mul(group, &r->Z, n0, n5, ctx)) goto end;
812                 }
813         r->Z_is_one = 0;
814         /* Z_r = Z_a * Z_b * n5 */
815
816         /* X_r */
817         if (!field_sqr(group, n0, n6, ctx)) goto end;
818         if (!field_sqr(group, n4, n5, ctx)) goto end;
819         if (!field_mul(group, n3, n1, n4, ctx)) goto end;
820         if (!BN_mod_sub_quick(&r->X, n0, n3, p)) goto end;
821         /* X_r = n6^2 - n5^2 * 'n7' */
822         
823         /* 'n9' */
824         if (!BN_mod_lshift1_quick(n0, &r->X, p)) goto end;
825         if (!BN_mod_sub_quick(n0, n3, n0, p)) goto end;
826         /* n9 = n5^2 * 'n7' - 2 * X_r */
827
828         /* Y_r */
829         if (!field_mul(group, n0, n0, n6, ctx)) goto end;
830         if (!field_mul(group, n5, n4, n5, ctx)) goto end; /* now n5 is n5^3 */
831         if (!field_mul(group, n1, n2, n5, ctx)) goto end;
832         if (!BN_mod_sub_quick(n0, n0, n1, p)) goto end;
833         if (BN_is_odd(n0))
834                 if (!BN_add(n0, n0, p)) goto end;
835         /* now  0 <= n0 < 2*p,  and n0 is even */
836         if (!BN_rshift1(&r->Y, n0)) goto end;
837         /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */
838
839         ret = 1;
840
841  end:
842         if (ctx) /* otherwise we already called BN_CTX_end */
843                 BN_CTX_end(ctx);
844         if (new_ctx != NULL)
845                 BN_CTX_free(new_ctx);
846         return ret;
847         }
848
849
850 int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
851         {
852         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
853         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
854         const BIGNUM *p;
855         BN_CTX *new_ctx = NULL;
856         BIGNUM *n0, *n1, *n2, *n3;
857         int ret = 0;
858         
859         if (EC_POINT_is_at_infinity(group, a))
860                 {
861                 if (!BN_zero(&r->Z)) return 0;
862                 r->Z_is_one = 0;
863                 return 1;
864                 }
865
866         field_mul = group->meth->field_mul;
867         field_sqr = group->meth->field_sqr;
868         p = &group->field;
869
870         if (ctx == NULL)
871                 {
872                 ctx = new_ctx = BN_CTX_new();
873                 if (ctx == NULL)
874                         return 0;
875                 }
876
877         BN_CTX_start(ctx);
878         n0 = BN_CTX_get(ctx);
879         n1 = BN_CTX_get(ctx);
880         n2 = BN_CTX_get(ctx);
881         n3 = BN_CTX_get(ctx);
882         if (n3 == NULL) goto err;
883
884         /* n1 */
885         if (a->Z_is_one)
886                 {
887                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
888                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
889                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
890                 if (!BN_mod_add_quick(n1, n0, &group->a, p)) goto err;
891                 /* n1 = 3 * X_a^2 + a_curve */
892                 }
893         else if (group->a_is_minus3)
894                 {
895                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
896                 if (!BN_mod_add_quick(n0, &a->X, n1, p)) goto err;
897                 if (!BN_mod_sub_quick(n2, &a->X, n1, p)) goto err;
898                 if (!field_mul(group, n1, n0, n2, ctx)) goto err;
899                 if (!BN_mod_lshift1_quick(n0, n1, p)) goto err;
900                 if (!BN_mod_add_quick(n1, n0, n1, p)) goto err;
901                 /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2)
902                  *    = 3 * X_a^2 - 3 * Z_a^4 */
903                 }
904         else
905                 {
906                 if (!field_sqr(group, n0, &a->X, ctx)) goto err;
907                 if (!BN_mod_lshift1_quick(n1, n0, p)) goto err;
908                 if (!BN_mod_add_quick(n0, n0, n1, p)) goto err;
909                 if (!field_sqr(group, n1, &a->Z, ctx)) goto err;
910                 if (!field_sqr(group, n1, n1, ctx)) goto err;
911                 if (!field_mul(group, n1, n1, &group->a, ctx)) goto err;
912                 if (!BN_mod_add_quick(n1, n1, n0, p)) goto err;
913                 /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */
914                 }
915
916         /* Z_r */
917         if (a->Z_is_one)
918                 {
919                 if (!BN_copy(n0, &a->Y)) goto err;
920                 }
921         else
922                 {
923                 if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) goto err;
924                 }
925         if (!BN_mod_lshift1_quick(&r->Z, n0, p)) goto err;
926         r->Z_is_one = 0;
927         /* Z_r = 2 * Y_a * Z_a */
928
929         /* n2 */
930         if (!field_sqr(group, n3, &a->Y, ctx)) goto err;
931         if (!field_mul(group, n2, &a->X, n3, ctx)) goto err;
932         if (!BN_mod_lshift_quick(n2, n2, 2, p)) goto err;
933         /* n2 = 4 * X_a * Y_a^2 */
934
935         /* X_r */
936         if (!BN_mod_lshift1_quick(n0, n2, p)) goto err;
937         if (!field_sqr(group, &r->X, n1, ctx)) goto err;
938         if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) goto err;
939         /* X_r = n1^2 - 2 * n2 */
940         
941         /* n3 */
942         if (!field_sqr(group, n0, n3, ctx)) goto err;
943         if (!BN_mod_lshift_quick(n3, n0, 3, p)) goto err;
944         /* n3 = 8 * Y_a^4 */
945         
946         /* Y_r */
947         if (!BN_mod_sub_quick(n0, n2, &r->X, p)) goto err;
948         if (!field_mul(group, n0, n1, n0, ctx)) goto err;
949         if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) goto err;
950         /* Y_r = n1 * (n2 - X_r) - n3 */
951
952         ret = 1;
953
954  err:
955         BN_CTX_end(ctx);
956         if (new_ctx != NULL)
957                 BN_CTX_free(new_ctx);
958         return ret;
959         }
960
961
962 int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
963         {
964         return BN_is_zero(&point->Z);
965         }
966
967
968 int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
969         {
970         int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *);
971         int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *);
972         const BIGNUM *p;
973         BN_CTX *new_ctx = NULL;
974         BIGNUM *rh, *tmp1, *tmp2, *Z4, *Z6;
975         int ret = -1;
976
977         if (EC_POINT_is_at_infinity(group, point))
978                 return 1;
979         
980         field_mul = group->meth->field_mul;
981         field_sqr = group->meth->field_sqr;
982         p = &group->field;
983
984         if (ctx == NULL)
985                 {
986                 ctx = new_ctx = BN_CTX_new();
987                 if (ctx == NULL)
988                         return -1;
989                 }
990
991         BN_CTX_start(ctx);
992         rh = BN_CTX_get(ctx);
993         tmp1 = BN_CTX_get(ctx);
994         tmp2 = BN_CTX_get(ctx);
995         Z4 = BN_CTX_get(ctx);
996         Z6 = BN_CTX_get(ctx);
997         if (Z6 == NULL) goto err;
998
999         /* We have a curve defined by a Weierstrass equation
1000          *      y^2 = x^3 + a*x + b.
1001          * The point to consider is given in Jacobian projective coordinates
1002          * where  (X, Y, Z)  represents  (x, y) = (X/Z^2, Y/Z^3).
1003          * Substituting this and multiplying by  Z^6  transforms the above equation into
1004          *      Y^2 = X^3 + a*X*Z^4 + b*Z^6.
1005          * To test this, we add up the right-hand side in 'rh'.
1006          */
1007
1008         /* rh := X^3 */
1009         if (!field_sqr(group, rh, &point->X, ctx)) goto err;
1010         if (!field_mul(group, rh, rh, &point->X, ctx)) goto err;
1011
1012         if (!point->Z_is_one)
1013                 {
1014                 if (!field_sqr(group, tmp1, &point->Z, ctx)) goto err;
1015                 if (!field_sqr(group, Z4, tmp1, ctx)) goto err;
1016                 if (!field_mul(group, Z6, Z4, tmp1, ctx)) goto err;
1017
1018                 /* rh := rh + a*X*Z^4 */
1019                 if (!field_mul(group, tmp1, &point->X, Z4, ctx)) goto err;
1020                 if (&group->a_is_minus3)
1021                         {
1022                         if (!BN_mod_lshift1_quick(tmp2, tmp1, p)) goto err;
1023                         if (!BN_mod_add_quick(tmp2, tmp2, tmp1, p)) goto err;
1024                         if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err;
1025                         }
1026                 else
1027                         {
1028                         if (!field_mul(group, tmp2, tmp1, &group->a, ctx)) goto err;
1029                         if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err;
1030                         }
1031
1032                 /* rh := rh + b*Z^6 */
1033                 if (!field_mul(group, tmp1, &group->b, Z6, ctx)) goto err;
1034                 if (!BN_mod_add_quick(rh, rh, tmp1, p)) goto err;
1035                 }
1036         else
1037                 {
1038                 /* point->Z_is_one */
1039
1040                 /* rh := rh + a*X */
1041                 if (&group->a_is_minus3)
1042                         {
1043                         if (!BN_mod_lshift1_quick(tmp2, &point->X, p)) goto err;
1044                         if (!BN_mod_add_quick(tmp2, tmp2, &point->X, p)) goto err;
1045                         if (!BN_mod_sub_quick(rh, rh, tmp2, p)) goto err;
1046                         }
1047                 else
1048                         {
1049                         if (!field_mul(group, tmp2, &point->X, &group->a, ctx)) goto err;
1050                         if (!BN_mod_add_quick(rh, rh, tmp2, p)) goto err;
1051                         }
1052
1053                 /* rh := rh + b */
1054                 if (!BN_mod_add_quick(rh, rh, &group->b, p)) goto err;
1055                 }
1056
1057         /* 'lh' := Y^2 */
1058         if (!field_sqr(group, tmp1, &point->Y, ctx)) goto err;
1059
1060         ret = (0 == BN_cmp(tmp1, rh));
1061
1062  err:
1063         BN_CTX_end(ctx);
1064         if (new_ctx != NULL)
1065                 BN_CTX_free(new_ctx);
1066         return ret;
1067         }
1068
1069
1070 int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
1071         {
1072         BN_CTX *new_ctx = NULL;
1073         BIGNUM *x, *y;
1074         int ret = 0;
1075
1076         if (point->Z_is_one || EC_POINT_is_at_infinity(group, point))
1077                 return 1;
1078
1079         if (ctx == NULL)
1080                 {
1081                 ctx = new_ctx = BN_CTX_new();
1082                 if (ctx == NULL)
1083                         return 0;
1084                 }
1085
1086         BN_CTX_start(ctx);
1087         x = BN_CTX_get(ctx);
1088         y = BN_CTX_get(ctx);
1089         if (y == NULL) goto err;
1090
1091         if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1092         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) goto err;
1093         if (!point->Z_is_one)
1094                 {
1095                 ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR);
1096                 goto err;
1097                 }
1098         
1099         ret = 1;
1100
1101  err:
1102         BN_CTX_end(ctx);
1103         if (new_ctx != NULL)
1104                 BN_CTX_free(new_ctx);
1105         return ret;
1106         }
1107
1108
1109 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
1110         {
1111         return BN_mod_mul(r, a, b, &group->field, ctx);
1112         }
1113
1114
1115 int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
1116         {
1117         return BN_mod_sqr(r, a, &group->field, ctx);
1118         }