"Fossies" - the Fresh Open Source Software Archive

Member "openssl-1.1.1g/crypto/ec/ecp_smpl.c" (21 Apr 2020, 49221 Bytes) of package /linux/misc/openssl-1.1.1g.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "ecp_smpl.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 1.1.1f_vs_1.1.1g.

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