1d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* Originally written by Bodo Moeller for the OpenSSL project. 2d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ==================================================================== 3d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 4d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 5d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Redistribution and use in source and binary forms, with or without 6d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * modification, are permitted provided that the following conditions 7d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * are met: 8d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 9d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 1. Redistributions of source code must retain the above copyright 10d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer. 11d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 12d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 2. Redistributions in binary form must reproduce the above copyright 13d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * notice, this list of conditions and the following disclaimer in 14d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * the documentation and/or other materials provided with the 15d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * distribution. 16d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 17d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 3. All advertising materials mentioning features or use of this 18d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * software must display the following acknowledgment: 19d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes software developed by the OpenSSL Project 20d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 21d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 22d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * endorse or promote products derived from this software without 24d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * prior written permission. For written permission, please contact 25d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * openssl-core@openssl.org. 26d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 27d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 5. Products derived from this software may not be called "OpenSSL" 28d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * nor may "OpenSSL" appear in their names without prior written 29d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * permission of the OpenSSL Project. 30d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 31d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 6. Redistributions of any form whatsoever must retain the following 32d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * acknowledgment: 33d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * "This product includes software developed by the OpenSSL Project 34d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 35d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 36d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * OF THE POSSIBILITY OF SUCH DAMAGE. 48d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ==================================================================== 49d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 50d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * This product includes cryptographic software written by Eric Young 51d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * (eay@cryptsoft.com). This product includes software written by Tim 52d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Hudson (tjh@cryptsoft.com). 53d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 54d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 55d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* ==================================================================== 56d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 57d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 58d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Portions of the attached software ("Contribution") are developed by 59d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. 60d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 61d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The Contribution is licensed pursuant to the OpenSSL open source 62d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * license provided above. 63d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 64d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The elliptic curve binary polynomial software is originally written by 65d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems 66d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Laboratories. */ 67d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 68d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/ec.h> 69d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 70d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <string.h> 71d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 72d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/bn.h> 73d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/err.h> 74d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include <openssl/mem.h> 75d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 76d9e397b599b13d642138480a28c14db7a136bf0Adam Langley#include "internal.h" 77d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 78d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 79d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyconst EC_METHOD *EC_GFp_simple_method(void) { 80d9e397b599b13d642138480a28c14db7a136bf0Adam Langley static const EC_METHOD ret = {EC_FLAGS_DEFAULT_OCT, 81d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_init, 82d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_finish, 83d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_clear_finish, 84d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_copy, 85d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_set_curve, 86d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_get_curve, 87d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_get_degree, 88d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_group_check_discriminant, 89d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_point_init, 90d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_point_finish, 91d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_point_clear_finish, 92d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_point_copy, 93d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_point_set_to_infinity, 94d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_set_Jprojective_coordinates_GFp, 95d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_get_Jprojective_coordinates_GFp, 96d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_point_set_affine_coordinates, 97d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_point_get_affine_coordinates, 98d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0, 99d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0, 100d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0, 101d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_add, 102d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_dbl, 103d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_invert, 104d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_is_at_infinity, 105d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_is_on_curve, 106d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_cmp, 107d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_make_affine, 108d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_points_make_affine, 109d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0 /* mul */, 110d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0 /* precompute_mult */, 111d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0 /* have_precompute_mult */, 112d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_field_mul, 113d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ec_GFp_simple_field_sqr, 114d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0 /* field_div */, 115d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0 /* field_encode */, 116d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0 /* field_decode */, 117d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 0 /* field_set_to_one */}; 118d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 119d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return &ret; 120d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 121d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 122d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 123d9e397b599b13d642138480a28c14db7a136bf0Adam Langley/* Most method functions in this file are designed to work with non-trivial 124d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * representations of field elements if necessary (see ecp_mont.c): while 125d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * standard modular addition and subtraction are used, the field_mul and 126d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * field_sqr methods will be used for multiplication, and field_encode and 127d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * field_decode (if defined) will be used for converting between 128d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * representations. 129d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 130d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Functions ec_GFp_simple_points_make_affine() and 131d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ec_GFp_simple_point_get_affine_coordinates() specifically assume that if a 132d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * non-trivial representation is used, it is a Montgomery representation (i.e. 133d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 'encoding' means multiplying by some factor R). */ 134d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 135d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_group_init(EC_GROUP *group) { 136d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&group->field); 137d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&group->a); 138d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&group->b); 139d9e397b599b13d642138480a28c14db7a136bf0Adam Langley group->a_is_minus3 = 0; 140d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 141d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 142d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 143d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyvoid ec_GFp_simple_group_finish(EC_GROUP *group) { 144d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&group->field); 145d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&group->a); 146d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&group->b); 147d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 148d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 149d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyvoid ec_GFp_simple_group_clear_finish(EC_GROUP *group) { 150d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_clear_free(&group->field); 151d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_clear_free(&group->a); 152d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_clear_free(&group->b); 153d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 154d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 155d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) { 156d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_copy(&dest->field, &src->field) || 157d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !BN_copy(&dest->a, &src->a) || 158d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !BN_copy(&dest->b, &src->b)) { 159d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 160d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 161d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 162d9e397b599b13d642138480a28c14db7a136bf0Adam Langley dest->a_is_minus3 = src->a_is_minus3; 163d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 164d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 165d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 166d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p, 167d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *a, const BIGNUM *b, 168d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *ctx) { 169d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 170d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 171d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *tmp_a; 172d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 173d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* p must be a prime > 3 */ 174d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { 175d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(EC, ec_GFp_simple_group_set_curve, EC_R_INVALID_FIELD); 176d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 177d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 178d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 179d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 180d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 181e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 182d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 183e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 184d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 185d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 186d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 187d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp_a = BN_CTX_get(ctx); 188e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (tmp_a == NULL) { 189d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 190e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 191d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 192d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* group->field */ 193e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(&group->field, p)) { 194d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 195e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 196d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_set_negative(&group->field, 0); 197d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 198d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* group->a */ 199e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_nnmod(tmp_a, a, p, ctx)) { 200d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 201e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 202d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_encode) { 203e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) { 204d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 205e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 206e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else if (!BN_copy(&group->a, tmp_a)) { 207d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 208e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 209d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 210d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* group->b */ 211e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_nnmod(&group->b, b, p, ctx)) { 212d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 213e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 214e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (group->meth->field_encode && 215e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !group->meth->field_encode(group, &group->b, &group->b, ctx)) { 216e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 217e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 218d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 219d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* group->a_is_minus3 */ 220e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_add_word(tmp_a, 3)) { 221d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 222e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 223d9e397b599b13d642138480a28c14db7a136bf0Adam Langley group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); 224d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 225d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 226d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 227d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 228d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 229e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 230d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 231d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 232d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 233d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, 234d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *b, BN_CTX *ctx) { 235d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 236d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 237d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 238e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (p != NULL && !BN_copy(p, &group->field)) { 239e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley return 0; 240d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 241d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 242d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a != NULL || b != NULL) { 243d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_decode) { 244d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 245d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 246e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 247d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 248e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 249d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 250e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (a != NULL && !group->meth->field_decode(group, a, &group->a, ctx)) { 251e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 252d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 253e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (b != NULL && !group->meth->field_decode(group, b, &group->b, ctx)) { 254e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 255d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 256d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 257e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (a != NULL && !BN_copy(a, &group->a)) { 258e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 259d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 260e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (b != NULL && !BN_copy(b, &group->b)) { 261e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 262d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 263d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 264d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 265d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 266d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 267d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 268d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 269e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 270d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 271d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 272d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 273d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_group_get_degree(const EC_GROUP *group) { 274d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return BN_num_bits(&group->field); 275d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 276d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 277d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) { 278d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 279d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *a, *b, *order, *tmp_1, *tmp_2; 280d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *p = &group->field; 281d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 282d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 283d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 284d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 285d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 286d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(EC, ec_GFp_simple_group_check_discriminant, 287d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ERR_R_MALLOC_FAILURE); 288d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 289d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 290d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 291d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 292d9e397b599b13d642138480a28c14db7a136bf0Adam Langley a = BN_CTX_get(ctx); 293d9e397b599b13d642138480a28c14db7a136bf0Adam Langley b = BN_CTX_get(ctx); 294d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp_1 = BN_CTX_get(ctx); 295d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp_2 = BN_CTX_get(ctx); 296d9e397b599b13d642138480a28c14db7a136bf0Adam Langley order = BN_CTX_get(ctx); 297e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (order == NULL) { 298d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 299e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 300d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 301d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_decode) { 302e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!group->meth->field_decode(group, a, &group->a, ctx) || 303e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !group->meth->field_decode(group, b, &group->b, ctx)) { 304d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 305e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 306d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 307e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(a, &group->a) || !BN_copy(b, &group->b)) { 308d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 309e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 310d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 311d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 312d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* check the discriminant: 313d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) 314d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 0 =< a, b < p */ 315d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_is_zero(a)) { 316e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (BN_is_zero(b)) { 317d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 318e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 319d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else if (!BN_is_zero(b)) { 320e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_sqr(tmp_1, a, p, ctx) || 321e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_mul(tmp_2, tmp_1, a, p, ctx) || 322e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_lshift(tmp_1, tmp_2, 2)) { 323d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 324e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 325d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* tmp_1 = 4*a^3 */ 326d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 327e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_sqr(tmp_2, b, p, ctx) || 328e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mul_word(tmp_2, 27)) { 329d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 330e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 331d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* tmp_2 = 27*b^2 */ 332d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 333e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx) || 334e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_is_zero(a)) { 335d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 336e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 337d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 338d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 339d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 340d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 341e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx != NULL) { 342d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 343e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 344e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 345d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 346d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 347d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 348d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_point_init(EC_POINT *point) { 349d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&point->X); 350d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&point->Y); 351d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_init(&point->Z); 352d9e397b599b13d642138480a28c14db7a136bf0Adam Langley point->Z_is_one = 0; 353d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 354d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 355d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 356d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 357d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyvoid ec_GFp_simple_point_finish(EC_POINT *point) { 358d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&point->X); 359d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&point->Y); 360d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_free(&point->Z); 361d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 362d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 363d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyvoid ec_GFp_simple_point_clear_finish(EC_POINT *point) { 364d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_clear_free(&point->X); 365d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_clear_free(&point->Y); 366d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_clear_free(&point->Z); 367d9e397b599b13d642138480a28c14db7a136bf0Adam Langley point->Z_is_one = 0; 368d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 369d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 370d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) { 371e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(&dest->X, &src->X) || 372e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_copy(&dest->Y, &src->Y) || 373e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_copy(&dest->Z, &src->Z)) { 374d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 375e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 376d9e397b599b13d642138480a28c14db7a136bf0Adam Langley dest->Z_is_one = src->Z_is_one; 377d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 378d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 379d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 380d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 381d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, 382d9e397b599b13d642138480a28c14db7a136bf0Adam Langley EC_POINT *point) { 383d9e397b599b13d642138480a28c14db7a136bf0Adam Langley point->Z_is_one = 0; 384d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_zero(&point->Z); 385d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 386d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 387d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 388d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_set_Jprojective_coordinates_GFp( 389d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const EC_GROUP *group, EC_POINT *point, const BIGNUM *x, const BIGNUM *y, 390d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *z, BN_CTX *ctx) { 391d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 392d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 393d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 394d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 395d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 396e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 397d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 398e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 399d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 400d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 401d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (x != NULL) { 402e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_nnmod(&point->X, x, &group->field, ctx)) { 403e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 404e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 405e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (group->meth->field_encode && 406e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !group->meth->field_encode(group, &point->X, &point->X, ctx)) { 407d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 408d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 409d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 410d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 411d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (y != NULL) { 412e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_nnmod(&point->Y, y, &group->field, ctx)) { 413e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 414e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 415e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (group->meth->field_encode && 416e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !group->meth->field_encode(group, &point->Y, &point->Y, ctx)) { 417d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 418d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 419d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 420d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 421d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (z != NULL) { 422d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int Z_is_one; 423d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 424e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_nnmod(&point->Z, z, &group->field, ctx)) { 425d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 426e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 427d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z_is_one = BN_is_one(&point->Z); 428d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_encode) { 429d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (Z_is_one && (group->meth->field_set_to_one != 0)) { 430e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!group->meth->field_set_to_one(group, &point->Z, ctx)) { 431d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 432e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 433e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) { 434e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 435d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 436d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 437d9e397b599b13d642138480a28c14db7a136bf0Adam Langley point->Z_is_one = Z_is_one; 438d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 439d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 440d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 441d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 442d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 443e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 444d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 445d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 446d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 447d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, 448d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const EC_POINT *point, 449d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *x, BIGNUM *y, 450d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *z, BN_CTX *ctx) { 451d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 452d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 453d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 454d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_decode != 0) { 455d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 456d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 457e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 458d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 459e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 460d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 461d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 462e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) { 463e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 464d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 465e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) { 466e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 467d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 468e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (z != NULL && !group->meth->field_decode(group, z, &point->Z, ctx)) { 469e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 470d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 471d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 472e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (x != NULL && !BN_copy(x, &point->X)) { 473e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 474d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 475e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (y != NULL && !BN_copy(y, &point->Y)) { 476e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 477d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 478e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (z != NULL && !BN_copy(z, &point->Z)) { 479e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 480d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 481d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 482d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 483d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 484d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 485d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 486e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 487d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 488d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 489d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 490d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, 491d9e397b599b13d642138480a28c14db7a136bf0Adam Langley EC_POINT *point, const BIGNUM *x, 492d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *y, BN_CTX *ctx) { 493d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (x == NULL || y == NULL) { 494d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* unlike for projective coordinates, we do not tolerate this */ 495d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point_set_affine_coordinates, 496d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ERR_R_PASSED_NULL_PARAMETER); 497d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 498d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 499d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 500d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ec_point_set_Jprojective_coordinates_GFp(group, point, x, y, 501d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_value_one(), ctx); 502d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 503d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 504d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, 505d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const EC_POINT *point, BIGNUM *x, 506d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *y, BN_CTX *ctx) { 507d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 508d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *Z, *Z_1, *Z_2, *Z_3; 509d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *Z_; 510d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 511d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 512d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (EC_POINT_is_at_infinity(group, point)) { 513d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point_get_affine_coordinates, 514d9e397b599b13d642138480a28c14db7a136bf0Adam Langley EC_R_POINT_AT_INFINITY); 515d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 516d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 517d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 518d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 519d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 520e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 521d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 522e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 523d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 524d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 525d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 526d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z = BN_CTX_get(ctx); 527d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z_1 = BN_CTX_get(ctx); 528d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z_2 = BN_CTX_get(ctx); 529d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z_3 = BN_CTX_get(ctx); 530e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (Z_3 == NULL) { 531d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 532e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 533d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 534d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ 535d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 536d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_decode) { 537e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!group->meth->field_decode(group, Z, &point->Z, ctx)) { 538d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 539e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 540d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z_ = Z; 541d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 542d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z_ = &point->Z; 543d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 544d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 545d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_is_one(Z_)) { 546d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_decode) { 547e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (x != NULL && !group->meth->field_decode(group, x, &point->X, ctx)) { 548e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 549d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 550e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (y != NULL && !group->meth->field_decode(group, y, &point->Y, ctx)) { 551e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 552d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 553d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 554e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (x != NULL && !BN_copy(x, &point->X)) { 555e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 556d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 557e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (y != NULL && !BN_copy(y, &point->Y)) { 558e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 559d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 560d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 561d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 562d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) { 563d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point_get_affine_coordinates, 564d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ERR_R_BN_LIB); 565d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 566d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 567d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 568d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_encode == 0) { 569d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* field_sqr works on standard representation */ 570e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) { 571d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 572e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 573e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) { 574e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 575d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 576d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 577e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley /* in the Montgomery case, field_mul will cancel out Montgomery factor in 578e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley * X: */ 579e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (x != NULL && !group->meth->field_mul(group, x, &point->X, Z_2, ctx)) { 580e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 581d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 582d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 583d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (y != NULL) { 584d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_encode == 0) { 585d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* field_mul works on standard representation */ 586e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) { 587d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 588e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 589e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) { 590e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 591d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 592d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 593d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* in the Montgomery case, field_mul will cancel out Montgomery factor in 594d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Y: */ 595e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) { 596d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 597e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 598d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 599d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 600d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 601d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 602d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 603d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 604d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 605e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 606d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 607d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 608d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 609d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 610d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const EC_POINT *b, BN_CTX *ctx) { 611d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 612d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *); 613d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 614d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *p; 615d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 616d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; 617d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 618d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 619e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (a == b) { 620d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return EC_POINT_dbl(group, r, a, ctx); 621e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 622e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (EC_POINT_is_at_infinity(group, a)) { 623d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return EC_POINT_copy(r, b); 624e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 625e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (EC_POINT_is_at_infinity(group, b)) { 626d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return EC_POINT_copy(r, a); 627e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 628d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 629d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_mul = group->meth->field_mul; 630d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_sqr = group->meth->field_sqr; 631d9e397b599b13d642138480a28c14db7a136bf0Adam Langley p = &group->field; 632d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 633d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 634d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 635e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 636d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 637e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 638d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 639d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 640d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 641d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n0 = BN_CTX_get(ctx); 642d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n1 = BN_CTX_get(ctx); 643d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n2 = BN_CTX_get(ctx); 644d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n3 = BN_CTX_get(ctx); 645d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n4 = BN_CTX_get(ctx); 646d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n5 = BN_CTX_get(ctx); 647d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n6 = BN_CTX_get(ctx); 648e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (n6 == NULL) { 649d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 650e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 651d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 652d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Note that in this function we must not read components of 'a' or 'b' 653d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * once we have written the corresponding components of 'r'. 654d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ('r' might be one of 'a' or 'b'.) 655d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 656d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 657d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n1, n2 */ 658d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (b->Z_is_one) { 659e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(n1, &a->X) || !BN_copy(n2, &a->Y)) { 660d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 661e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 662d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n1 = X_a */ 663d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n2 = Y_a */ 664d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 665e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n0, &b->Z, ctx) || 666e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n1, &a->X, n0, ctx)) { 667d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 668e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 669d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n1 = X_a * Z_b^2 */ 670d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 671e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, n0, n0, &b->Z, ctx) || 672e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n2, &a->Y, n0, ctx)) { 673d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 674e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 675d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n2 = Y_a * Z_b^3 */ 676d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 677d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 678d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n3, n4 */ 679d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->Z_is_one) { 680e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(n3, &b->X) || !BN_copy(n4, &b->Y)) { 681d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 682e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 683d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n3 = X_b */ 684d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n4 = Y_b */ 685d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 686e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n0, &a->Z, ctx) || 687e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n3, &b->X, n0, ctx)) { 688d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 689e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 690d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n3 = X_b * Z_a^2 */ 691d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 692e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, n0, n0, &a->Z, ctx) || 693e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n4, &b->Y, n0, ctx)) { 694d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 695e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 696d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n4 = Y_b * Z_a^3 */ 697d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 698d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 699d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n5, n6 */ 700e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_sub_quick(n5, n1, n3, p) || 701e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(n6, n2, n4, p)) { 702d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 703e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 704d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n5 = n1 - n3 */ 705d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n6 = n2 - n4 */ 706d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 707d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_is_zero(n5)) { 708d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_is_zero(n6)) { 709d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* a is the same point as b */ 710d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 711d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = EC_POINT_dbl(group, r, a, ctx); 712d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = NULL; 713d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 714d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 715d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* a is the inverse of b */ 716d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_zero(&r->Z); 717d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->Z_is_one = 0; 718d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 719d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 720d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 721d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 722d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 723d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* 'n7', 'n8' */ 724e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_add_quick(n1, n1, n3, p) || 725e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(n2, n2, n4, p)) { 726d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 727e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 728d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* 'n7' = n1 + n3 */ 729d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* 'n8' = n2 + n4 */ 730d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 731d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Z_r */ 732d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->Z_is_one && b->Z_is_one) { 733e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(&r->Z, n5)) { 734d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 735e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 736d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 737d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->Z_is_one) { 738e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(n0, &b->Z)) { 739d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 740e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 741d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else if (b->Z_is_one) { 742e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(n0, &a->Z)) { 743d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 744e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 745e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) { 746e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto end; 747d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 748e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, &r->Z, n0, n5, ctx)) { 749d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 750e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 751d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 752d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->Z_is_one = 0; 753d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Z_r = Z_a * Z_b * n5 */ 754d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 755d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* X_r */ 756e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n0, n6, ctx) || 757e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_sqr(group, n4, n5, ctx) || 758e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n3, n1, n4, ctx) || 759e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(&r->X, n0, n3, p)) { 760d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 761e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 762d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* X_r = n6^2 - n5^2 * 'n7' */ 763d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 764d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* 'n9' */ 765e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_lshift1_quick(n0, &r->X, p) || 766e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(n0, n3, n0, p)) { 767d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 768e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 769d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n9 = n5^2 * 'n7' - 2 * X_r */ 770d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 771d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Y_r */ 772e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, n0, n0, n6, ctx) || 773e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n5, n4, n5, ctx)) { 774d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; /* now n5 is n5^3 */ 775e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 776e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, n1, n2, n5, ctx) || 777e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(n0, n0, n1, p)) { 778d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 779e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 780e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (BN_is_odd(n0) && !BN_add(n0, n0, p)) { 781d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 782e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 783d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* now 0 <= n0 < 2*p, and n0 is even */ 784e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_rshift1(&r->Y, n0)) { 785d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 786e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 787d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ 788d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 789d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 790d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 791d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyend: 792e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx) { 793e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley /* otherwise we already called BN_CTX_end */ 794d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 795e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 796e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 797d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 798d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 799d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 800d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, 801d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *ctx) { 802d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 803d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *); 804d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 805d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *p; 806d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 807d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *n0, *n1, *n2, *n3; 808d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 809d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 810d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (EC_POINT_is_at_infinity(group, a)) { 811d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_zero(&r->Z); 812d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->Z_is_one = 0; 813d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 814d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 815d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 816d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_mul = group->meth->field_mul; 817d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_sqr = group->meth->field_sqr; 818d9e397b599b13d642138480a28c14db7a136bf0Adam Langley p = &group->field; 819d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 820d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 821d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 822e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 823d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 824e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 825d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 826d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 827d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 828d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n0 = BN_CTX_get(ctx); 829d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n1 = BN_CTX_get(ctx); 830d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n2 = BN_CTX_get(ctx); 831d9e397b599b13d642138480a28c14db7a136bf0Adam Langley n3 = BN_CTX_get(ctx); 832e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (n3 == NULL) { 833d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 834e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 835d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 836d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Note that in this function we must not read components of 'a' 837d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * once we have written the corresponding components of 'r'. 838d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * ('r' might the same as 'a'.) 839d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 840d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 841d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n1 */ 842d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->Z_is_one) { 843e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n0, &a->X, ctx) || 844e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_lshift1_quick(n1, n0, p) || 845e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(n0, n0, n1, p) || 846e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(n1, n0, &group->a, p)) { 847d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 848e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 849d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n1 = 3 * X_a^2 + a_curve */ 850d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else if (group->a_is_minus3) { 851e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n1, &a->Z, ctx) || 852e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(n0, &a->X, n1, p) || 853e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(n2, &a->X, n1, p) || 854e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n1, n0, n2, ctx) || 855e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_lshift1_quick(n0, n1, p) || 856e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(n1, n0, n1, p)) { 857d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 858e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 859d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) 860d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * = 3 * X_a^2 - 3 * Z_a^4 */ 861d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 862e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n0, &a->X, ctx) || 863e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_lshift1_quick(n1, n0, p) || 864e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(n0, n0, n1, p) || 865e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_sqr(group, n1, &a->Z, ctx) || 866e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_sqr(group, n1, n1, ctx) || 867e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n1, n1, &group->a, ctx) || 868e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(n1, n1, n0, p)) { 869d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 870e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 871d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ 872d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 873d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 874d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Z_r */ 875d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->Z_is_one) { 876e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_copy(n0, &a->Y)) { 877d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 878e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 879e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) { 880e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley goto err; 881d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 882e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_lshift1_quick(&r->Z, n0, p)) { 883d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 884e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 885d9e397b599b13d642138480a28c14db7a136bf0Adam Langley r->Z_is_one = 0; 886d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Z_r = 2 * Y_a * Z_a */ 887d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 888d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n2 */ 889e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n3, &a->Y, ctx) || 890e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n2, &a->X, n3, ctx) || 891e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_lshift_quick(n2, n2, 2, p)) { 892d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 893e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 894d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n2 = 4 * X_a * Y_a^2 */ 895d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 896d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* X_r */ 897e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_lshift1_quick(n0, n2, p) || 898e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_sqr(group, &r->X, n1, ctx) || 899e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(&r->X, &r->X, n0, p)) { 900d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 901e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 902d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* X_r = n1^2 - 2 * n2 */ 903d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 904d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n3 */ 905e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, n0, n3, ctx) || 906e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_lshift_quick(n3, n0, 3, p)) { 907d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 908e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 909d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* n3 = 8 * Y_a^4 */ 910d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 911d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Y_r */ 912e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_sub_quick(n0, n2, &r->X, p) || 913e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, n0, n1, n0, ctx) || 914e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(&r->Y, n0, n3, p)) { 915d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 916e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 917d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Y_r = n1 * (n2 - X_r) - n3 */ 918d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 919d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 920d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 921d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 922d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 923e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 924d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 925d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 926d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 927d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) { 928e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) { 929d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* point is its own inverse */ 930d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 931e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 932d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 933d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return BN_usub(&point->Y, &group->field, &point->Y); 934d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 935d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 936d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) { 937d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return !point->Z_is_one && BN_is_zero(&point->Z); 938d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 939d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 940d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, 941d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *ctx) { 942d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 943d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *); 944d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 945d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *p; 946d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 947d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *rh, *tmp, *Z4, *Z6; 948d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = -1; 949d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 950e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (EC_POINT_is_at_infinity(group, point)) { 951d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 952e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 953d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 954d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_mul = group->meth->field_mul; 955d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_sqr = group->meth->field_sqr; 956d9e397b599b13d642138480a28c14db7a136bf0Adam Langley p = &group->field; 957d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 958d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 959d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 960e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 961d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return -1; 962e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 963d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 964d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 965d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 966d9e397b599b13d642138480a28c14db7a136bf0Adam Langley rh = BN_CTX_get(ctx); 967d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp = BN_CTX_get(ctx); 968d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z4 = BN_CTX_get(ctx); 969d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Z6 = BN_CTX_get(ctx); 970e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (Z6 == NULL) { 971d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 972e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 973d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 974d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* We have a curve defined by a Weierstrass equation 975d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * y^2 = x^3 + a*x + b. 976d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * The point to consider is given in Jacobian projective coordinates 977d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). 978d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Substituting this and multiplying by Z^6 transforms the above equation 979d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * into 980d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * Y^2 = X^3 + a*X*Z^4 + b*Z^6. 981d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * To test this, we add up the right-hand side in 'rh'. 982d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 983d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 984d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* rh := X^2 */ 985e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, rh, &point->X, ctx)) { 986d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 987e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 988d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 989d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!point->Z_is_one) { 990e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, tmp, &point->Z, ctx) || 991e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_sqr(group, Z4, tmp, ctx) || 992e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, Z6, Z4, tmp, ctx)) { 993d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 994e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 995d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 996d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* rh := (rh + a*Z^4)*X */ 997d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->a_is_minus3) { 998e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_lshift1_quick(tmp, Z4, p) || 999e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(tmp, tmp, Z4, p) || 1000e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_sub_quick(rh, rh, tmp, p) || 1001e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, rh, rh, &point->X, ctx)) { 1002d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1003e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1004d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 1005e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, tmp, Z4, &group->a, ctx) || 1006e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(rh, rh, tmp, p) || 1007e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, rh, rh, &point->X, ctx)) { 1008d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1009e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1010d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1011d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1012d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* rh := rh + b*Z^6 */ 1013e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, tmp, &group->b, Z6, ctx) || 1014e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !BN_mod_add_quick(rh, rh, tmp, p)) { 1015d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1016e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1017d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 1018d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* point->Z_is_one */ 1019d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1020d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* rh := (rh + a)*X */ 1021e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_add_quick(rh, rh, &group->a, p) || 1022e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, rh, rh, &point->X, ctx)) { 1023d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1024e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1025d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* rh := rh + b */ 1026e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!BN_mod_add_quick(rh, rh, &group->b, p)) { 1027d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1028e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1029d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1030d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1031d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* 'lh' := Y^2 */ 1032e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, tmp, &point->Y, ctx)) { 1033d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1034e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1035d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1036d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = (0 == BN_ucmp(tmp, rh)); 1037d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1038d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 1039d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 1040e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 1041d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 1042d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 1043d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1044d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, 1045d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const EC_POINT *b, BN_CTX *ctx) { 1046d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* return values: 1047d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * -1 error 1048d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 0 equal (in affine coordinates) 1049d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * 1 not equal 1050d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 1051d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1052d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, 1053d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *); 1054d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); 1055d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 1056d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *tmp1, *tmp2, *Za23, *Zb23; 1057d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *tmp1_, *tmp2_; 1058d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = -1; 1059d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1060d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (EC_POINT_is_at_infinity(group, a)) { 1061d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return EC_POINT_is_at_infinity(group, b) ? 0 : 1; 1062d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1063d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1064e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (EC_POINT_is_at_infinity(group, b)) { 1065d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 1066e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1067d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1068d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (a->Z_is_one && b->Z_is_one) { 1069d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; 1070d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1071d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1072d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_mul = group->meth->field_mul; 1073d9e397b599b13d642138480a28c14db7a136bf0Adam Langley field_sqr = group->meth->field_sqr; 1074d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1075d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 1076d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 1077e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 1078d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return -1; 1079e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1080d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1081d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1082d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 1083d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp1 = BN_CTX_get(ctx); 1084d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp2 = BN_CTX_get(ctx); 1085d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Za23 = BN_CTX_get(ctx); 1086d9e397b599b13d642138480a28c14db7a136bf0Adam Langley Zb23 = BN_CTX_get(ctx); 1087e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (Zb23 == NULL) { 1088d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 1089e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1090d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1091d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* We have to decide whether 1092d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), 1093d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * or equivalently, whether 1094d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). 1095d9e397b599b13d642138480a28c14db7a136bf0Adam Langley */ 1096d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1097d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!b->Z_is_one) { 1098e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, Zb23, &b->Z, ctx) || 1099e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, tmp1, &a->X, Zb23, ctx)) { 1100d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 1101e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1102d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp1_ = tmp1; 1103e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else { 1104d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp1_ = &a->X; 1105e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1106d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!a->Z_is_one) { 1107e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_sqr(group, Za23, &a->Z, ctx) || 1108e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, tmp2, &b->X, Za23, ctx)) { 1109d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 1110e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1111d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp2_ = tmp2; 1112e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else { 1113d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp2_ = &b->X; 1114e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1115d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1116d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* compare X_a*Z_b^2 with X_b*Z_a^2 */ 1117d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_cmp(tmp1_, tmp2_) != 0) { 1118d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; /* points differ */ 1119d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 1120d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1121d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1122d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1123d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!b->Z_is_one) { 1124e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, Zb23, Zb23, &b->Z, ctx) || 1125e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, tmp1, &a->Y, Zb23, ctx)) { 1126d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 1127e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1128d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* tmp1_ = tmp1 */ 1129e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else { 1130d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp1_ = &a->Y; 1131e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1132d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!a->Z_is_one) { 1133e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!field_mul(group, Za23, Za23, &a->Z, ctx) || 1134e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !field_mul(group, tmp2, &b->Y, Za23, ctx)) { 1135d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 1136e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1137d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* tmp2_ = tmp2 */ 1138e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } else { 1139d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp2_ = &b->Y; 1140e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1141d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1142d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ 1143d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_cmp(tmp1_, tmp2_) != 0) { 1144d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; /* points differ */ 1145d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto end; 1146d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1147d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1148d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* points are equal */ 1149d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 0; 1150d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1151d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyend: 1152d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 1153e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 1154d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 1155d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 1156d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1157d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, 1158d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *ctx) { 1159d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 1160d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *x, *y; 1161d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 1162d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1163e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) { 1164d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 1165e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1166d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1167d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 1168d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 1169e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (ctx == NULL) { 1170d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 1171e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1172d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1173d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1174d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 1175d9e397b599b13d642138480a28c14db7a136bf0Adam Langley x = BN_CTX_get(ctx); 1176d9e397b599b13d642138480a28c14db7a136bf0Adam Langley y = BN_CTX_get(ctx); 1177e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (y == NULL) { 1178d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1179e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1180d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1181e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx) || 1182e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley !EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) { 1183d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1184e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley } 1185d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!point->Z_is_one) { 1186d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(EC, ec_GFp_simple_make_affine, ERR_R_INTERNAL_ERROR); 1187d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1188d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1189d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1190d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 1191d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1192d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 1193d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 1194e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 1195d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 1196d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 1197d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1198d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, 1199d9e397b599b13d642138480a28c14db7a136bf0Adam Langley EC_POINT *points[], BN_CTX *ctx) { 1200d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *new_ctx = NULL; 1201d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM *tmp, *tmp_Z; 1202d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BIGNUM **prod_Z = NULL; 1203d9e397b599b13d642138480a28c14db7a136bf0Adam Langley size_t i; 1204d9e397b599b13d642138480a28c14db7a136bf0Adam Langley int ret = 0; 1205d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1206d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (num == 0) { 1207d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 1; 1208d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1209d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1210d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 1211d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ctx = new_ctx = BN_CTX_new(); 1212d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (ctx == NULL) { 1213d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return 0; 1214d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1215d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1216d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1217d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_start(ctx); 1218d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp = BN_CTX_get(ctx); 1219d9e397b599b13d642138480a28c14db7a136bf0Adam Langley tmp_Z = BN_CTX_get(ctx); 1220d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (tmp == NULL || tmp_Z == NULL) { 1221d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1222d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1223d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1224d9e397b599b13d642138480a28c14db7a136bf0Adam Langley prod_Z = OPENSSL_malloc(num * sizeof(prod_Z[0])); 1225d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (prod_Z == NULL) { 1226d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1227d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1228d9e397b599b13d642138480a28c14db7a136bf0Adam Langley memset(prod_Z, 0, num * sizeof(prod_Z[0])); 1229d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 0; i < num; i++) { 1230d9e397b599b13d642138480a28c14db7a136bf0Adam Langley prod_Z[i] = BN_new(); 1231d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (prod_Z[i] == NULL) { 1232d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1233d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1234d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1235d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1236d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Set each prod_Z[i] to the product of points[0]->Z .. points[i]->Z, 1237d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * skipping any zero-valued inputs (pretend that they're 1). */ 1238d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1239d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_is_zero(&points[0]->Z)) { 1240d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_copy(prod_Z[0], &points[0]->Z)) { 1241d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1242d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1243d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 1244d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_set_to_one != 0) { 1245d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!group->meth->field_set_to_one(group, prod_Z[0], ctx)) { 1246d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1247d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1248d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 1249d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_one(prod_Z[0])) { 1250d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1251d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1252d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1253d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1254d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1255d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 1; i < num; i++) { 1256d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_is_zero(&points[i]->Z)) { 1257d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!group->meth->field_mul(group, prod_Z[i], prod_Z[i - 1], 1258d9e397b599b13d642138480a28c14db7a136bf0Adam Langley &points[i]->Z, ctx)) { 1259d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1260d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1261d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 1262d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_copy(prod_Z[i], prod_Z[i - 1])) { 1263d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1264d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1265d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1266d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1267d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1268d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Now use a single explicit inversion to replace every 1269d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * non-zero points[i]->Z by its inverse. */ 1270d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1271d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_mod_inverse(tmp, prod_Z[num - 1], &group->field, ctx)) { 1272d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_PUT_ERROR(EC, ec_GFp_simple_points_make_affine, ERR_R_BN_LIB); 1273d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1274d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1275d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1276d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_encode != NULL) { 1277d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* In the Montgomery case, we just turned R*H (representing H) 1278d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * into 1/(R*H), but we need R*(1/H) (representing 1/H); 1279d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * i.e. we need to multiply by the Montgomery factor twice. */ 1280d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!group->meth->field_encode(group, tmp, tmp, ctx) || 1281d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !group->meth->field_encode(group, tmp, tmp, ctx)) { 1282d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1283d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1284d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1285d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1286d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = num - 1; i > 0; --i) { 1287d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Loop invariant: tmp is the product of the inverses of 1288d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * points[0]->Z .. points[i]->Z (zero-valued inputs skipped). */ 1289d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (BN_is_zero(&points[i]->Z)) { 1290d9e397b599b13d642138480a28c14db7a136bf0Adam Langley continue; 1291d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1292d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1293d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Set tmp_Z to the inverse of points[i]->Z (as product 1294d9e397b599b13d642138480a28c14db7a136bf0Adam Langley * of Z inverses 0 .. i, Z values 0 .. i - 1). */ 1295d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!group->meth->field_mul(group, tmp_Z, prod_Z[i - 1], tmp, ctx) || 1296d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Update tmp to satisfy the loop invariant for i - 1. */ 1297d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !group->meth->field_mul(group, tmp, tmp, &points[i]->Z, ctx) || 1298d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Replace points[i]->Z by its inverse. */ 1299d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !BN_copy(&points[i]->Z, tmp_Z)) { 1300d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1301d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1302d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1303d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1304d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Replace points[0]->Z by its inverse. */ 1305d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_is_zero(&points[0]->Z) && !BN_copy(&points[0]->Z, tmp)) { 1306d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1307d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1308d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1309d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* Finally, fix up the X and Y coordinates for all points. */ 1310d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 0; i < num; i++) { 1311d9e397b599b13d642138480a28c14db7a136bf0Adam Langley EC_POINT *p = points[i]; 1312d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1313d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_is_zero(&p->Z)) { 1314d9e397b599b13d642138480a28c14db7a136bf0Adam Langley /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1). */ 1315d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!group->meth->field_sqr(group, tmp, &p->Z, ctx) || 1316d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !group->meth->field_mul(group, &p->X, &p->X, tmp, ctx) || 1317d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !group->meth->field_mul(group, tmp, tmp, &p->Z, ctx) || 1318d9e397b599b13d642138480a28c14db7a136bf0Adam Langley !group->meth->field_mul(group, &p->Y, &p->Y, tmp, ctx)) { 1319d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1320d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1321d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1322d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (group->meth->field_set_to_one != NULL) { 1323d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!group->meth->field_set_to_one(group, &p->Z, ctx)) { 1324d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1325d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1326d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } else { 1327d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (!BN_one(&p->Z)) { 1328d9e397b599b13d642138480a28c14db7a136bf0Adam Langley goto err; 1329d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1330d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1331d9e397b599b13d642138480a28c14db7a136bf0Adam Langley p->Z_is_one = 1; 1332d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1333d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1334d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1335d9e397b599b13d642138480a28c14db7a136bf0Adam Langley ret = 1; 1336d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1337d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyerr: 1338d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX_end(ctx); 1339e9ada863a7b3e81f5d2b1e3bdd2305da902a87f5Adam Langley BN_CTX_free(new_ctx); 1340d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (prod_Z != NULL) { 1341d9e397b599b13d642138480a28c14db7a136bf0Adam Langley for (i = 0; i < num; i++) { 1342d9e397b599b13d642138480a28c14db7a136bf0Adam Langley if (prod_Z[i] == NULL) { 1343d9e397b599b13d642138480a28c14db7a136bf0Adam Langley break; 1344d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1345d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_clear_free(prod_Z[i]); 1346d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1347d9e397b599b13d642138480a28c14db7a136bf0Adam Langley OPENSSL_free(prod_Z); 1348d9e397b599b13d642138480a28c14db7a136bf0Adam Langley } 1349d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1350d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return ret; 1351d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 1352d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1353d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1354d9e397b599b13d642138480a28c14db7a136bf0Adam Langley const BIGNUM *b, BN_CTX *ctx) { 1355d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return BN_mod_mul(r, a, b, &group->field, ctx); 1356d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 1357d9e397b599b13d642138480a28c14db7a136bf0Adam Langley 1358d9e397b599b13d642138480a28c14db7a136bf0Adam Langleyint ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, 1359d9e397b599b13d642138480a28c14db7a136bf0Adam Langley BN_CTX *ctx) { 1360d9e397b599b13d642138480a28c14db7a136bf0Adam Langley return BN_mod_sqr(r, a, &group->field, ctx); 1361d9e397b599b13d642138480a28c14db7a136bf0Adam Langley} 1362