Inital import. Initial fork from f2d678e6e89b6508147086610e985d4e8416e867 (1.0.2 beta). (This change contains substantial changes from the original and effectively starts a new history.)
diff --git a/crypto/ec/CMakeLists.txt b/crypto/ec/CMakeLists.txt new file mode 100644 index 0000000..019916f --- /dev/null +++ b/crypto/ec/CMakeLists.txt
@@ -0,0 +1,24 @@ +include_directories(. .. ../../include) + +add_library( + ec + + OBJECT + + ec.c + oct.c + simple.c + ec_montgomery.c + wnaf.c + ec_key.c + ec_asn1.c + ec_error.c +) + +add_executable( + example_mul + + example_mul.c +) + +target_link_libraries(example_mul crypto)
diff --git a/crypto/ec/ec.c b/crypto/ec/ec.c new file mode 100644 index 0000000..ef022bc --- /dev/null +++ b/crypto/ec/ec.c
@@ -0,0 +1,872 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#include <openssl/ec.h> + +#include <openssl/bn.h> +#include <openssl/err.h> +#include <openssl/mem.h> +#include <openssl/obj.h> + +#include "internal.h" + + +/* curve_data contains data about a built-in elliptic curve. */ +struct curve_data { + /* comment is a human-readable string describing the curve. */ + const char *comment; + /* param_len is the number of bytes needed to store a field element. */ + uint8_t param_len; + /* cofactor is the cofactor of the group (i.e. the number of elements in the + * group divided by the size of the main subgroup. */ + uint8_t cofactor; /* promoted to BN_ULONG */ + /* data points to an array of 6*|param_len| bytes which hold the field + * elements of the following (in big-endian order): prime, a, b, generator x, + * generator y, order. */ + const uint8_t data[]; +}; + +static const struct curve_data P224 = { + "NIST P-224", + 28, + 1, + {/* p */ + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x01, + /* a */ + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFE, + /* b */ + 0xB4, 0x05, 0x0A, 0x85, 0x0C, 0x04, 0xB3, 0xAB, 0xF5, 0x41, 0x32, 0x56, + 0x50, 0x44, 0xB0, 0xB7, 0xD7, 0xBF, 0xD8, 0xBA, 0x27, 0x0B, 0x39, 0x43, + 0x23, 0x55, 0xFF, 0xB4, + /* x */ + 0xB7, 0x0E, 0x0C, 0xBD, 0x6B, 0xB4, 0xBF, 0x7F, 0x32, 0x13, 0x90, 0xB9, + 0x4A, 0x03, 0xC1, 0xD3, 0x56, 0xC2, 0x11, 0x22, 0x34, 0x32, 0x80, 0xD6, + 0x11, 0x5C, 0x1D, 0x21, + /* y */ + 0xbd, 0x37, 0x63, 0x88, 0xb5, 0xf7, 0x23, 0xfb, 0x4c, 0x22, 0xdf, 0xe6, + 0xcd, 0x43, 0x75, 0xa0, 0x5a, 0x07, 0x47, 0x64, 0x44, 0xd5, 0x81, 0x99, + 0x85, 0x00, 0x7e, 0x34, + /* order */ + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0x16, 0xA2, 0xE0, 0xB8, 0xF0, 0x3E, 0x13, 0xDD, 0x29, 0x45, + 0x5C, 0x5C, 0x2A, 0x3D, + }}; + +static const struct curve_data P256 = { + "NIST P-256", + 32, + 1, + {/* p */ + 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + /* a */ + 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC, + /* b */ + 0x5A, 0xC6, 0x35, 0xD8, 0xAA, 0x3A, 0x93, 0xE7, 0xB3, 0xEB, 0xBD, 0x55, + 0x76, 0x98, 0x86, 0xBC, 0x65, 0x1D, 0x06, 0xB0, 0xCC, 0x53, 0xB0, 0xF6, + 0x3B, 0xCE, 0x3C, 0x3E, 0x27, 0xD2, 0x60, 0x4B, + /* x */ + 0x6B, 0x17, 0xD1, 0xF2, 0xE1, 0x2C, 0x42, 0x47, 0xF8, 0xBC, 0xE6, 0xE5, + 0x63, 0xA4, 0x40, 0xF2, 0x77, 0x03, 0x7D, 0x81, 0x2D, 0xEB, 0x33, 0xA0, + 0xF4, 0xA1, 0x39, 0x45, 0xD8, 0x98, 0xC2, 0x96, + /* y */ + 0x4f, 0xe3, 0x42, 0xe2, 0xfe, 0x1a, 0x7f, 0x9b, 0x8e, 0xe7, 0xeb, 0x4a, + 0x7c, 0x0f, 0x9e, 0x16, 0x2b, 0xce, 0x33, 0x57, 0x6b, 0x31, 0x5e, 0xce, + 0xcb, 0xb6, 0x40, 0x68, 0x37, 0xbf, 0x51, 0xf5, + /* order */ + 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xBC, 0xE6, 0xFA, 0xAD, 0xA7, 0x17, 0x9E, 0x84, + 0xF3, 0xB9, 0xCA, 0xC2, 0xFC, 0x63, 0x25, 0x51}}; + +static const struct curve_data P384 = { + "NIST P-384", + 48, + 1, + {/* p */ + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, + /* a */ + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, 0xFF, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFC, + /* b */ + 0xB3, 0x31, 0x2F, 0xA7, 0xE2, 0x3E, 0xE7, 0xE4, 0x98, 0x8E, 0x05, 0x6B, + 0xE3, 0xF8, 0x2D, 0x19, 0x18, 0x1D, 0x9C, 0x6E, 0xFE, 0x81, 0x41, 0x12, + 0x03, 0x14, 0x08, 0x8F, 0x50, 0x13, 0x87, 0x5A, 0xC6, 0x56, 0x39, 0x8D, + 0x8A, 0x2E, 0xD1, 0x9D, 0x2A, 0x85, 0xC8, 0xED, 0xD3, 0xEC, 0x2A, 0xEF, + /* x */ + 0xAA, 0x87, 0xCA, 0x22, 0xBE, 0x8B, 0x05, 0x37, 0x8E, 0xB1, 0xC7, 0x1E, + 0xF3, 0x20, 0xAD, 0x74, 0x6E, 0x1D, 0x3B, 0x62, 0x8B, 0xA7, 0x9B, 0x98, + 0x59, 0xF7, 0x41, 0xE0, 0x82, 0x54, 0x2A, 0x38, 0x55, 0x02, 0xF2, 0x5D, + 0xBF, 0x55, 0x29, 0x6C, 0x3A, 0x54, 0x5E, 0x38, 0x72, 0x76, 0x0A, 0xB7, + /* y */ + 0x36, 0x17, 0xde, 0x4a, 0x96, 0x26, 0x2c, 0x6f, 0x5d, 0x9e, 0x98, 0xbf, + 0x92, 0x92, 0xdc, 0x29, 0xf8, 0xf4, 0x1d, 0xbd, 0x28, 0x9a, 0x14, 0x7c, + 0xe9, 0xda, 0x31, 0x13, 0xb5, 0xf0, 0xb8, 0xc0, 0x0a, 0x60, 0xb1, 0xce, + 0x1d, 0x7e, 0x81, 0x9d, 0x7a, 0x43, 0x1d, 0x7c, 0x90, 0xea, 0x0e, 0x5f, + /* order */ + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xC7, 0x63, 0x4D, 0x81, 0xF4, 0x37, 0x2D, 0xDF, 0x58, 0x1A, 0x0D, 0xB2, + 0x48, 0xB0, 0xA7, 0x7A, 0xEC, 0xEC, 0x19, 0x6A, 0xCC, 0xC5, 0x29, 0x73}}; + +static const struct curve_data P521 = { + "NIST P-521", + 66, + 1, + {/* p */ + 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + /* a */ + 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC, + /* b */ + 0x00, 0x51, 0x95, 0x3E, 0xB9, 0x61, 0x8E, 0x1C, 0x9A, 0x1F, 0x92, 0x9A, + 0x21, 0xA0, 0xB6, 0x85, 0x40, 0xEE, 0xA2, 0xDA, 0x72, 0x5B, 0x99, 0xB3, + 0x15, 0xF3, 0xB8, 0xB4, 0x89, 0x91, 0x8E, 0xF1, 0x09, 0xE1, 0x56, 0x19, + 0x39, 0x51, 0xEC, 0x7E, 0x93, 0x7B, 0x16, 0x52, 0xC0, 0xBD, 0x3B, 0xB1, + 0xBF, 0x07, 0x35, 0x73, 0xDF, 0x88, 0x3D, 0x2C, 0x34, 0xF1, 0xEF, 0x45, + 0x1F, 0xD4, 0x6B, 0x50, 0x3F, 0x00, + /* x */ + 0x00, 0xC6, 0x85, 0x8E, 0x06, 0xB7, 0x04, 0x04, 0xE9, 0xCD, 0x9E, 0x3E, + 0xCB, 0x66, 0x23, 0x95, 0xB4, 0x42, 0x9C, 0x64, 0x81, 0x39, 0x05, 0x3F, + 0xB5, 0x21, 0xF8, 0x28, 0xAF, 0x60, 0x6B, 0x4D, 0x3D, 0xBA, 0xA1, 0x4B, + 0x5E, 0x77, 0xEF, 0xE7, 0x59, 0x28, 0xFE, 0x1D, 0xC1, 0x27, 0xA2, 0xFF, + 0xA8, 0xDE, 0x33, 0x48, 0xB3, 0xC1, 0x85, 0x6A, 0x42, 0x9B, 0xF9, 0x7E, + 0x7E, 0x31, 0xC2, 0xE5, 0xBD, 0x66, + /* y */ + 0x01, 0x18, 0x39, 0x29, 0x6a, 0x78, 0x9a, 0x3b, 0xc0, 0x04, 0x5c, 0x8a, + 0x5f, 0xb4, 0x2c, 0x7d, 0x1b, 0xd9, 0x98, 0xf5, 0x44, 0x49, 0x57, 0x9b, + 0x44, 0x68, 0x17, 0xaf, 0xbd, 0x17, 0x27, 0x3e, 0x66, 0x2c, 0x97, 0xee, + 0x72, 0x99, 0x5e, 0xf4, 0x26, 0x40, 0xc5, 0x50, 0xb9, 0x01, 0x3f, 0xad, + 0x07, 0x61, 0x35, 0x3c, 0x70, 0x86, 0xa2, 0x72, 0xc2, 0x40, 0x88, 0xbe, + 0x94, 0x76, 0x9f, 0xd1, 0x66, 0x50, + /* order */ + 0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, + 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFA, 0x51, 0x86, + 0x87, 0x83, 0xBF, 0x2F, 0x96, 0x6B, 0x7F, 0xCC, 0x01, 0x48, 0xF7, 0x09, + 0xA5, 0xD0, 0x3B, 0xB5, 0xC9, 0xB8, 0x89, 0x9C, 0x47, 0xAE, 0xBB, 0x6F, + 0xB7, 0x1E, 0x91, 0x38, 0x64, 0x09}}; + +struct built_in_curve { + int nid; + const struct curve_data *data; + const EC_METHOD *(*method)(void); +}; + +static const struct built_in_curve built_in_curves[] = { + {NID_secp224r1, &P224, 0}, + {NID_X9_62_prime256v1, &P256, 0}, + {NID_secp384r1, &P384, 0}, + {NID_secp521r1, &P521, 0}, + {NID_undef, 0, 0}, +}; + +EC_GROUP *ec_group_new(const EC_METHOD *meth) { + EC_GROUP *ret; + + if (meth == NULL) { + OPENSSL_PUT_ERROR(EC, ec_group_new, EC_R_SLOT_FULL); + return NULL; + } + + if (meth->group_init == 0) { + OPENSSL_PUT_ERROR(EC, ec_group_new, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return NULL; + } + + ret = OPENSSL_malloc(sizeof(EC_GROUP)); + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, ec_group_new, ERR_R_MALLOC_FAILURE); + return NULL; + } + memset(ret, 0, sizeof(EC_GROUP)); + + ret->meth = meth; + BN_init(&ret->order); + BN_init(&ret->cofactor); + ret->asn1_form = POINT_CONVERSION_UNCOMPRESSED; + + if (!meth->group_init(ret)) { + OPENSSL_free(ret); + return NULL; + } + + return ret; +} + +static EC_GROUP *ec_group_new_curve_GFp(const BIGNUM *p, const BIGNUM *a, + const BIGNUM *b, BN_CTX *ctx) { + const EC_METHOD *meth = EC_GFp_mont_method(); + EC_GROUP *ret; + + ret = ec_group_new(meth); + if (ret == NULL) { + return NULL; + } + + if (ret->meth->group_set_curve == 0) { + OPENSSL_PUT_ERROR(EC, ec_group_new_curve_GFp, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (!ret->meth->group_set_curve(ret, p, a, b, ctx)) { + EC_GROUP_free(ret); + return NULL; + } + return ret; +} + +static EC_GROUP *ec_group_new_from_data(const struct built_in_curve *curve) { + EC_GROUP *group = NULL; + EC_POINT *P = NULL; + BN_CTX *ctx = NULL; + BIGNUM *p = NULL, *a = NULL, *b = NULL, *x = NULL, *y = NULL, *order = NULL; + int ok = 0; + unsigned param_len; + const EC_METHOD *meth; + const struct curve_data *data; + const uint8_t *params; + + if ((ctx = BN_CTX_new()) == NULL) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_MALLOC_FAILURE); + goto err; + } + + data = curve->data; + param_len = data->param_len; + params = data->data; + + if (!(p = BN_bin2bn(params + 0 * param_len, param_len, NULL)) || + !(a = BN_bin2bn(params + 1 * param_len, param_len, NULL)) || + !(b = BN_bin2bn(params + 2 * param_len, param_len, NULL))) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_BN_LIB); + goto err; + } + + if (curve->method != 0) { + meth = curve->method(); + if (((group = ec_group_new(meth)) == NULL) || + (!(group->meth->group_set_curve(group, p, a, b, ctx)))) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_EC_LIB); + goto err; + } + } else { + if ((group = ec_group_new_curve_GFp(p, a, b, ctx)) == NULL) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_EC_LIB); + goto err; + } + } + + if ((P = EC_POINT_new(group)) == NULL) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_EC_LIB); + goto err; + } + + if (!(x = BN_bin2bn(params + 3 * param_len, param_len, NULL)) || + !(y = BN_bin2bn(params + 4 * param_len, param_len, NULL))) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_BN_LIB); + goto err; + } + + if (!EC_POINT_set_affine_coordinates_GFp(group, P, x, y, ctx)) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_EC_LIB); + goto err; + } + if (!(order = BN_bin2bn(params + 5 * param_len, param_len, NULL)) || + !BN_set_word(x, (BN_ULONG)data->cofactor)) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_BN_LIB); + goto err; + } + + group->generator = P; + P = NULL; + if (!BN_copy(&group->order, order) || + !BN_set_word(&group->cofactor, (BN_ULONG)data->cofactor)) { + OPENSSL_PUT_ERROR(EC, ec_group_new_from_data, ERR_R_BN_LIB); + goto err; + } + + ok = 1; + +err: + if (!ok) { + EC_GROUP_free(group); + group = NULL; + } + if (P) + EC_POINT_free(P); + if (ctx) + BN_CTX_free(ctx); + if (p) + BN_free(p); + if (a) + BN_free(a); + if (b) + BN_free(b); + if (order) + BN_free(order); + if (x) + BN_free(x); + if (y) + BN_free(y); + return group; +} + +EC_GROUP *EC_GROUP_new_by_curve_name(int nid) { + unsigned i; + const struct built_in_curve *curve; + EC_GROUP *ret = NULL; + + for (i = 0; built_in_curves[i].nid != NID_undef; i++) { + curve = &built_in_curves[i]; + if (curve->nid == nid) { + ret = ec_group_new_from_data(curve); + break; + } + } + + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, EC_GROUP_new_by_curve_name, EC_R_UNKNOWN_GROUP); + return NULL; + } + + ret->curve_name = nid; + return ret; +} + +void EC_GROUP_free(EC_GROUP *group) { + if (!group) { + return; + } + + if (group->meth->group_finish != 0) { + group->meth->group_finish(group); + } + + ec_pre_comp_free(group->pre_comp); + + if (group->generator != NULL) { + EC_POINT_free(group->generator); + } + BN_free(&group->order); + BN_free(&group->cofactor); + + OPENSSL_free(group); +} + +int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src) { + if (dest->meth->group_copy == 0) { + OPENSSL_PUT_ERROR(EC, EC_GROUP_copy, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (dest->meth != src->meth) { + OPENSSL_PUT_ERROR(EC, EC_GROUP_copy, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + if (dest == src) { + return 1; + } + + ec_pre_comp_free(dest->pre_comp); + dest->pre_comp = ec_pre_comp_dup(src->pre_comp); + + if (src->generator != NULL) { + if (dest->generator == NULL) { + dest->generator = EC_POINT_new(dest); + if (dest->generator == NULL) { + return 0; + } + } + if (!EC_POINT_copy(dest->generator, src->generator)) { + return 0; + } + } else { + /* src->generator == NULL */ + if (dest->generator != NULL) { + EC_POINT_clear_free(dest->generator); + dest->generator = NULL; + } + } + + if (!BN_copy(&dest->order, &src->order) || + !BN_copy(&dest->cofactor, &src->cofactor)) { + return 0; + } + + dest->curve_name = src->curve_name; + dest->asn1_form = src->asn1_form; + + return dest->meth->group_copy(dest, src); +} + +EC_GROUP *EC_GROUP_dup(const EC_GROUP *a) { + EC_GROUP *t = NULL; + int ok = 0; + + if (a == NULL) { + return NULL; + } + + t = ec_group_new(a->meth); + if (t == NULL) { + return NULL; + } + if (!EC_GROUP_copy(t, a)) { + goto err; + } + + ok = 1; + +err: + if (!ok) { + if (t) { + EC_GROUP_free(t); + } + return NULL; + } else { + return t; + } +} + +int EC_GROUP_cmp(const EC_GROUP *a, const EC_GROUP *b) { + if (a->curve_name == NID_undef || b->curve_name == NID_undef) { + return 0; + } + return a->curve_name == b->curve_name; +} + +const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group) { + return group->generator; +} + +int EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx) { + if (!BN_copy(order, &group->order)) { + return 0; + } + + return !BN_is_zero(order); +} + +int EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, + BN_CTX *ctx) { + if (!BN_copy(cofactor, &group->cofactor)) { + return 0; + } + + return !BN_is_zero(&group->cofactor); +} + +int EC_GROUP_get_curve_name(const EC_GROUP *group) { return group->curve_name; } + +int EC_GROUP_get_degree(const EC_GROUP *group) { + if (group->meth->group_get_degree == 0) { + OPENSSL_PUT_ERROR(EC, EC_GROUP_get_degree, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + return group->meth->group_get_degree(group); +} + +void EC_GROUP_set_point_conversion_form(EC_GROUP *group, + point_conversion_form_t form) { + group->asn1_form = form; +} + +int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx) { + if (group->meth->mul == 0) { + /* use default */ + return ec_wNAF_precompute_mult(group, ctx); + } + + if (group->meth->precompute_mult != 0) { + return group->meth->precompute_mult(group, ctx); + } + + return 1; /* nothing to do, so report success */ +} + +int EC_GROUP_have_precompute_mult(const EC_GROUP *group) { + if (group->meth->mul == 0) { + /* use default */ + return ec_wNAF_have_precompute_mult(group); + } + + if (group->meth->have_precompute_mult != 0) { + return group->meth->have_precompute_mult(group); + } + + return 0; /* cannot tell whether precomputation has been performed */ +} + +EC_POINT *EC_POINT_new(const EC_GROUP *group) { + EC_POINT *ret; + + if (group == NULL) { + OPENSSL_PUT_ERROR(EC, EC_POINT_new, ERR_R_PASSED_NULL_PARAMETER); + return NULL; + } + if (group->meth->point_init == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_new, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return NULL; + } + + ret = OPENSSL_malloc(sizeof *ret); + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, EC_POINT_new, ERR_R_MALLOC_FAILURE); + return NULL; + } + + ret->meth = group->meth; + + if (!ret->meth->point_init(ret)) { + OPENSSL_free(ret); + return NULL; + } + + return ret; +} + +void EC_POINT_free(EC_POINT *point) { + if (!point) { + return; + } + + if (point->meth->point_finish != 0) { + point->meth->point_finish(point); + } + OPENSSL_free(point); +} + +void EC_POINT_clear_free(EC_POINT *point) { + if (!point) { + return; + } + + if (point->meth->point_clear_finish != 0) { + point->meth->point_clear_finish(point); + } else if (point->meth->point_finish != 0) { + point->meth->point_finish(point); + } + OPENSSL_cleanse(point, sizeof *point); + OPENSSL_free(point); +} + +int EC_POINT_copy(EC_POINT *dest, const EC_POINT *src) { + if (dest->meth->point_copy == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_copy, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (dest->meth != src->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_copy, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + if (dest == src) { + return 1; + } + return dest->meth->point_copy(dest, src); +} + +EC_POINT *EC_POINT_dup(const EC_POINT *a, const EC_GROUP *group) { + EC_POINT *t; + int r; + + if (a == NULL) { + return NULL; + } + + t = EC_POINT_new(group); + if (t == NULL) { + OPENSSL_PUT_ERROR(EC, EC_POINT_dup, ERR_R_MALLOC_FAILURE); + return NULL; + } + r = EC_POINT_copy(t, a); + if (!r) { + EC_POINT_free(t); + return NULL; + } else { + return t; + } +} + +int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point) { + if (group->meth->point_set_to_infinity == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_set_to_infinity, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_set_to_infinity, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->point_set_to_infinity(group, point); +} + +int EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) { + if (group->meth->is_at_infinity == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_is_at_infinity, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_is_at_infinity, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->is_at_infinity(group, point); +} + +int EC_POINT_is_on_curve(const EC_GROUP *group, const EC_POINT *point, + BN_CTX *ctx) { + if (group->meth->is_on_curve == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_is_on_curve, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_is_on_curve, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->is_on_curve(group, point, ctx); +} + +int EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, + BN_CTX *ctx) { + if (group->meth->point_cmp == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_cmp, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return -1; + } + if ((group->meth != a->meth) || (a->meth != b->meth)) { + OPENSSL_PUT_ERROR(EC, EC_POINT_cmp, EC_R_INCOMPATIBLE_OBJECTS); + return -1; + } + return group->meth->point_cmp(group, a, b, ctx); +} + +int EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) { + if (group->meth->make_affine == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_make_affine, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_make_affine, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->make_affine(group, point, ctx); +} + +int EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], + BN_CTX *ctx) { + size_t i; + + if (group->meth->points_make_affine == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINTs_make_affine, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + for (i = 0; i < num; i++) { + if (group->meth != points[i]->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINTs_make_affine, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + } + return group->meth->points_make_affine(group, num, points, ctx); +} + +int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group, + const EC_POINT *point, BIGNUM *x, + BIGNUM *y, BN_CTX *ctx) { + if (group->meth->point_get_affine_coordinates == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_get_affine_coordinates_GFp, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_get_affine_coordinates_GFp, + EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->point_get_affine_coordinates(group, point, x, y, ctx); +} + +int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, + const BIGNUM *x, const BIGNUM *y, + BN_CTX *ctx) { + if (group->meth->point_set_affine_coordinates == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_set_affine_coordinates_GFp, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_set_affine_coordinates_GFp, + EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->point_set_affine_coordinates(group, point, x, y, ctx); +} + +int EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, + const EC_POINT *b, BN_CTX *ctx) { + if (group->meth->add == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_add, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if ((group->meth != r->meth) || (r->meth != a->meth) || + (a->meth != b->meth)) { + OPENSSL_PUT_ERROR(EC, EC_POINT_add, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->add(group, r, a, b, ctx); +} + + +int EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, + BN_CTX *ctx) { + if (group->meth->dbl == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_dbl, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if ((group->meth != r->meth) || (r->meth != a->meth)) { + OPENSSL_PUT_ERROR(EC, EC_POINT_dbl, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->dbl(group, r, a, ctx); +} + + +int EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx) { + if (group->meth->dbl == 0) { + OPENSSL_PUT_ERROR(EC, EC_POINT_invert, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != a->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_invert, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->invert(group, a, ctx); +} + +int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, + const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx) { + /* just a convenient interface to EC_POINTs_mul() */ + + const EC_POINT *points[1]; + const BIGNUM *scalars[1]; + + points[0] = point; + scalars[0] = p_scalar; + + return EC_POINTs_mul(group, r, g_scalar, (point != NULL && p_scalar != NULL), + points, scalars, ctx); +} + +int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, + size_t num, const EC_POINT *points[], const BIGNUM *scalars[], + BN_CTX *ctx) { + if (group->meth->mul == 0) { + /* use default. Warning, not constant-time. */ + return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); + } + + return group->meth->mul(group, r, scalar, num, points, scalars, ctx); +} + +int ec_point_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, + const BIGNUM *x, const BIGNUM *y, + const BIGNUM *z, BN_CTX *ctx) { + if (group->meth->point_set_Jprojective_coordinates_GFp == 0) { + OPENSSL_PUT_ERROR(EC, ec_point_set_Jprojective_coordinates_GFp, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, ec_point_set_Jprojective_coordinates_GFp, + EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + return group->meth->point_set_Jprojective_coordinates_GFp(group, point, x, y, + z, ctx); +}
diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h new file mode 100644 index 0000000..368432e --- /dev/null +++ b/crypto/ec/ec.h
@@ -0,0 +1,367 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#ifndef OPENSSL_HEADER_EC_H +#define OPENSSL_HEADER_EC_H + +#include <openssl/base.h> + +#if defined(__cplusplus) +extern "C" { +#endif + + +typedef struct ec_group_st EC_GROUP; +typedef struct ec_point_st EC_POINT; + +/** Enum for the point conversion form as defined in X9.62 (ECDSA) + * for the encoding of a elliptic curve point (x,y) */ +typedef enum { + /** the point is encoded as z||x, where the octet z specifies + * which solution of the quadratic equation y is */ + POINT_CONVERSION_COMPRESSED = 2, + /** the point is encoded as z||x||y, where z is the octet 0x02 */ + POINT_CONVERSION_UNCOMPRESSED = 4, + /** the point is encoded as z||x||y, where the octet z specifies + * which solution of the quadratic equation y is */ + POINT_CONVERSION_HYBRID = 6 +} point_conversion_form_t; + + +/* Elliptic curve groups. */ + +/* EC_GROUP_new_by_curve_name returns a fresh EC_GROUP object for the elliptic + * curve specified by |nid|, or NULL on error. + * + * The supported NIDs are: + * NID_secp224r1, + * NID_X9_62_prime256v1, + * NID_secp384r1, + * NID_secp521r1 */ +EC_GROUP *EC_GROUP_new_by_curve_name(int nid); + +/* EC_GROUP_free frees |group| and the data that it points to. */ +void EC_GROUP_free(EC_GROUP *group); + +/* EC_GROUP_copy sets |*dest| equal to |*src|. It returns one on success and + * zero otherwise. */ +int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src); + +/* EC_GROUP_dup returns a fresh |EC_GROUP| which is equal to |a| or NULL on + * error. */ +EC_GROUP *EC_GROUP_dup(const EC_GROUP *a); + +/* EC_GROUP_cmp returns one if |a| and |b| are the same group and zero + * otherwise. */ +int EC_GROUP_cmp(const EC_GROUP *a, const EC_GROUP *b); + +/* EC_GROUP_get0_generator returns a pointer to the internal |EC_POINT| object + * in |group| that specifies the generator for the group. */ +const EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group); + +/* EC_GROUP_get_order sets |*order| to the order of |group| using |ctx|, if + * it's not NULL. It returns one on success and zero otherwise. */ +int EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx); + +/* EC_GROUP_get_cofactor sets |*cofactor| to the cofactor of |group| using + * |ctx|, if it's not NULL. It returns one on success and zero otherwise. */ +int EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx); + +/* EC_GROUP_get_curve_name returns a NID that identifies |group|. */ +int EC_GROUP_get_curve_name(const EC_GROUP *group); + +/* EC_GROUP_get_degree returns the number of bits needed to represent an + * element of the field underlying |group|. */ +int EC_GROUP_get_degree(const EC_GROUP *group); + +/* EC_GROUP_set_point_conversion_form sets the form that serialised points will + * take as one of the |POINT_CONVERSION_*| values. */ +void EC_GROUP_set_point_conversion_form(EC_GROUP *group, + point_conversion_form_t form); + +/* EC_GROUP_precompute_mult precomputes multiplies of the generator in order to + * speed up operations that involve calculating generator multiples. It returns + * one on sucess and zero otherwise. If |ctx| is not NULL, it may be used. */ +int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx); + +/* EC_GROUP_have_precompute_mult returns one if |group| contains precomputed + * generator multiples. */ +int EC_GROUP_have_precompute_mult(const EC_GROUP *group); + + +/* Points on elliptic curves. */ + +/* EC_POINT_new returns a fresh |EC_POINT| object in the given group, or NULL + * on error. */ +EC_POINT *EC_POINT_new(const EC_GROUP *group); + +/* EC_POINT_free frees |point| and the data that it points to. */ +void EC_POINT_free(EC_POINT *point); + +/* EC_POINT_clear_free clears the data that |point| points to, frees it and + * then frees |point| itself. */ +void EC_POINT_clear_free(EC_POINT *point); + +/* EC_POINT_copy sets |*dest| equal to |*src|. It returns one on success and + * zero otherwise. */ +int EC_POINT_copy(EC_POINT *dest, const EC_POINT *src); + +/* EC_POINT_dup returns a fresh |EC_POINT| that contains the same values as + * |src|, or NULL on error. */ +EC_POINT *EC_POINT_dup(const EC_POINT *src, const EC_GROUP *group); + +/* EC_POINT_set_to_infinity sets |point| to be the "point at infinity" for the + * given group. */ +int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point); + +/* EC_POINT_is_at_infinity returns one iff |point| is the point at infinity and + * zero otherwise. */ +int EC_POINT_is_at_infinity(const EC_GROUP *group, const EC_POINT *point); + +/* EC_POINT_is_on_curve returns one if |point| is an element of |group| and + * zero otheriwse. If |ctx| is non-NULL, it may be used. */ +int EC_POINT_is_on_curve(const EC_GROUP *group, const EC_POINT *point, + BN_CTX *ctx); + +/* EC_POINT_cmp returns zero if |a| is equal to |b|, greater than zero is + * non-equal and -1 on error. If |ctx| is not NULL, it may be used. */ +int EC_POINT_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, + BN_CTX *ctx); + +/* EC_POINT_make_affine converts |point| to affine form, internally. It returns + * one on success and zero otherwise. If |ctx| is not NULL, it may be used. */ +int EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx); + +/* EC_POINTs_make_affine converts |num| points from |points| to affine form, + * internally. It returns one on success and zero otherwise. If |ctx| is not + * NULL, it may be used. */ +int EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], + BN_CTX *ctx); + + +/* Point conversion. */ + +/* EC_POINT_get_affine_coordinates_GFp sets |x| and |y| to the affine value of + * |point| using |ctx|, if it's not NULL. It returns one on success and zero + * otherwise. */ +int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *group, + const EC_POINT *point, BIGNUM *x, + BIGNUM *y, BN_CTX *ctx); + +/* EC_POINT_set_affine_coordinates sets the value of |p| to be (|x|, |y|). The + * |ctx| argument may be used if not NULL. */ +int EC_POINT_set_affine_coordinates_GFp(const EC_GROUP *group, EC_POINT *point, + const BIGNUM *x, const BIGNUM *y, + BN_CTX *ctx); + +/* EC_POINT_point2oct serialises |point| into the X9.62 form given by |form| + * into, at most, |len| bytes at |buf|. It returns the number of bytes written + * or zero on error if |buf| is non-NULL, else the number of bytes needed. The + * |ctx| argument may be used if not NULL. */ +size_t EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point, + point_conversion_form_t form, uint8_t *buf, + size_t len, BN_CTX *ctx); + +/* EC_POINT_oct2point sets |point| from |len| bytes of X9.62 format + * serialisation in |buf|. It returns one on success and zero otherwise. The + * |ctx| argument may be used if not NULL. */ +int EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point, + const uint8_t *buf, size_t len, BN_CTX *ctx); + +/* EC_POINT_set_compressed_coordinates_GFp sets |point| to equal the point with + * the given |x| coordinate and the y coordinate specified by |y_bit| (see + * X9.62). It returns one on success and zero otherwise. */ +int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, + EC_POINT *point, const BIGNUM *x, + int y_bit, BN_CTX *ctx); + + +/* Group operations. */ + +/* EC_POINT_add sets |r| equal to |a| plus |b|. It returns one on success and + * zero otherwise. If |ctx| is not NULL, it may be used. */ +int EC_POINT_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, + const EC_POINT *b, BN_CTX *ctx); + +/* EC_POINT_dbl sets |r| equal to |a| plus |a|. It returns one on success and + * zero otherwise. If |ctx| is not NULL, it may be used. */ +int EC_POINT_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, + BN_CTX *ctx); + +/* EC_POINT_dbl sets |a| equal to minus |a|. It returns one on success and zero + * otherwise. If |ctx| is not NULL, it may be used. */ +int EC_POINT_invert(const EC_GROUP *group, EC_POINT *a, BN_CTX *ctx); + +/* EC_POINT_mul sets r = generator*n + q*m. It returns one on success and zero + * otherwise. If |ctx| is not NULL, it may be used. */ +int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *n, + const EC_POINT *q, const BIGNUM *m, BN_CTX *ctx); + +/* EC_POINTs_mul sets r = generator*n + sum(p[i]*m[i]). It returns one on + * success and zero otherwise. If |ctx| is not NULL, it may be used. */ +int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *n, + size_t num, const EC_POINT *p[], const BIGNUM *m[], + BN_CTX *ctx); + + +/* Old code expects to get EC_KEY from ec.h. */ +#if !defined(OPENSSL_HEADER_EC_KEY_H) +#include <openssl/ec_key.h> +#endif + + +#if defined(__cplusplus) +} /* extern C */ +#endif + +#define EC_F_ec_pre_comp_new 100 +#define EC_F_ec_GFp_mont_field_decode 101 +#define EC_F_ec_group_new_from_data 102 +#define EC_F_ec_GFp_simple_point_get_affine_coordinates 103 +#define EC_F_ec_GFp_simple_make_affine 104 +#define EC_F_EC_KEY_new_method 105 +#define EC_F_ec_GFp_mont_field_encode 106 +#define EC_F_EC_GROUP_new_by_curve_name 107 +#define EC_F_ec_group_new 108 +#define EC_F_ec_asn1_group2pkparameters 109 +#define EC_F_EC_POINT_set_compressed_coordinates_GFp 110 +#define EC_F_ec_GFp_mont_field_sqr 111 +#define EC_F_EC_POINT_make_affine 112 +#define EC_F_i2d_ECParameters 113 +#define EC_F_ec_wNAF_mul 114 +#define EC_F_EC_GROUP_copy 115 +#define EC_F_EC_POINT_cmp 116 +#define EC_F_ec_GFp_mont_field_mul 117 +#define EC_F_EC_POINT_dup 118 +#define EC_F_EC_POINT_invert 119 +#define EC_F_ec_GFp_simple_point_set_affine_coordinates 120 +#define EC_F_ec_GFp_simple_points_make_affine 121 +#define EC_F_i2o_ECPublicKey 122 +#define EC_F_EC_KEY_check_key 123 +#define EC_F_ec_wNAF_precompute_mult 124 +#define EC_F_EC_POINT_oct2point 125 +#define EC_F_EC_POINT_is_at_infinity 126 +#define EC_F_EC_POINT_get_affine_coordinates_GFp 127 +#define EC_F_ec_point_set_Jprojective_coordinates_GFp 128 +#define EC_F_o2i_ECPublicKey 129 +#define EC_F_ec_GFp_mont_field_set_to_one 130 +#define EC_F_ec_group_new_curve_GFp 131 +#define EC_F_EC_POINT_dbl 132 +#define EC_F_ec_asn1_pkparameters2group 133 +#define EC_F_i2d_ECPKParameters 134 +#define EC_F_EC_KEY_copy 135 +#define EC_F_EC_POINT_new 136 +#define EC_F_EC_POINT_point2oct 137 +#define EC_F_EC_POINT_copy 138 +#define EC_F_EC_POINT_is_on_curve 139 +#define EC_F_ec_GFp_simple_group_set_curve 140 +#define EC_F_i2d_ECPrivateKey 141 +#define EC_F_d2i_ECParameters 142 +#define EC_F_ec_GFp_mont_group_set_curve 143 +#define EC_F_EC_POINT_set_to_infinity 144 +#define EC_F_EC_POINTs_make_affine 145 +#define EC_F_compute_wNAF 146 +#define EC_F_ec_GFp_simple_point2oct 147 +#define EC_F_EC_GROUP_get_degree 148 +#define EC_F_ec_GFp_simple_group_check_discriminant 149 +#define EC_F_d2i_ECPKParameters 150 +#define EC_F_d2i_ECPrivateKey 151 +#define EC_F_ec_GFp_simple_oct2point 152 +#define EC_F_EC_POINT_set_affine_coordinates_GFp 153 +#define EC_F_EC_KEY_set_public_key_affine_coordinates 154 +#define EC_F_EC_KEY_generate_key 155 +#define EC_F_ec_GFp_simple_set_compressed_coordinates 156 +#define EC_F_EC_POINT_add 157 +#define EC_R_PKPARAMETERS2GROUP_FAILURE 100 +#define EC_R_NON_NAMED_CURVE 101 +#define EC_R_COORDINATES_OUT_OF_RANGE 102 +#define EC_R_POINT_AT_INFINITY 103 +#define EC_R_NOT_INITIALIZED 104 +#define EC_R_MISSING_PRIVATE_KEY 105 +#define EC_R_GROUP2PKPARAMETERS_FAILURE 106 +#define EC_R_INVALID_ENCODING 107 +#define EC_R_BUFFER_TOO_SMALL 108 +#define EC_R_D2I_ECPKPARAMETERS_FAILURE 109 +#define EC_R_INVALID_FORM 110 +#define EC_R_INVALID_PRIVATE_KEY 111 +#define EC_R_INVALID_COMPRESSED_POINT 112 +#define EC_R_MISSING_PARAMETERS 113 +#define EC_R_INVALID_FIELD 114 +#define EC_R_INVALID_COMPRESSION_BIT 115 +#define EC_R_GF2M_NOT_SUPPORTED 116 +#define EC_R_POINT_IS_NOT_ON_CURVE 117 +#define EC_R_UNKNOWN_ORDER 118 +#define EC_R_UNKNOWN_GROUP 119 +#define EC_R_WRONG_ORDER 120 +#define EC_R_UNDEFINED_GENERATOR 121 +#define EC_R_INCOMPATIBLE_OBJECTS 122 +#define EC_R_I2D_ECPKPARAMETERS_FAILURE 123 +#define EC_R_EC_GROUP_NEW_BY_NAME_FAILURE 124 +#define EC_R_INVALID_GROUP_ORDER 125 +#define EC_R_SLOT_FULL 126 + +#endif /* OPENSSL_HEADER_EC_H */
diff --git a/crypto/ec/ec_asn1.c b/crypto/ec/ec_asn1.c new file mode 100644 index 0000000..7b4f74f --- /dev/null +++ b/crypto/ec/ec_asn1.c
@@ -0,0 +1,556 @@ +/* Written by Nils Larsch for the OpenSSL project. */ +/* ==================================================================== + * Copyright (c) 2000-2003 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * licensing@OpenSSL.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). */ + +#include <openssl/ec.h> + +#include <openssl/asn1.h> +#include <openssl/asn1t.h> +#include <openssl/bn.h> +#include <openssl/err.h> +#include <openssl/mem.h> +#include <openssl/obj.h> + +#include "internal.h" + + +typedef struct x9_62_fieldid_st { + ASN1_OBJECT *fieldType; + union { + char *ptr; + /* NID_X9_62_prime_field */ + ASN1_INTEGER *prime; + /* anything else */ + ASN1_TYPE *other; + } p; +} X9_62_FIELDID; + +ASN1_ADB_TEMPLATE(fieldID_def) = ASN1_SIMPLE(X9_62_FIELDID, p.other, ASN1_ANY); + +ASN1_ADB(X9_62_FIELDID) = { + ADB_ENTRY(NID_X9_62_prime_field, ASN1_SIMPLE(X9_62_FIELDID, p.prime, ASN1_INTEGER)), +} ASN1_ADB_END(X9_62_FIELDID, 0, fieldType, 0, &fieldID_def_tt, NULL); + +ASN1_SEQUENCE(X9_62_FIELDID) = { + ASN1_SIMPLE(X9_62_FIELDID, fieldType, ASN1_OBJECT), + ASN1_ADB_OBJECT(X9_62_FIELDID) +} ASN1_SEQUENCE_END(X9_62_FIELDID); + +typedef struct x9_62_curve_st { + ASN1_OCTET_STRING *a; + ASN1_OCTET_STRING *b; + ASN1_BIT_STRING *seed; +} X9_62_CURVE; + +ASN1_SEQUENCE(X9_62_CURVE) = { + ASN1_SIMPLE(X9_62_CURVE, a, ASN1_OCTET_STRING), + ASN1_SIMPLE(X9_62_CURVE, b, ASN1_OCTET_STRING), + ASN1_OPT(X9_62_CURVE, seed, ASN1_BIT_STRING) +} ASN1_SEQUENCE_END(X9_62_CURVE); + +typedef struct ec_parameters_st { + long version; + X9_62_FIELDID *fieldID; + X9_62_CURVE *curve; + ASN1_OCTET_STRING *base; + ASN1_INTEGER *order; + ASN1_INTEGER *cofactor; +} ECPARAMETERS; + +ASN1_SEQUENCE(ECPARAMETERS) = { + ASN1_SIMPLE(ECPARAMETERS, version, LONG), + ASN1_SIMPLE(ECPARAMETERS, fieldID, X9_62_FIELDID), + ASN1_SIMPLE(ECPARAMETERS, curve, X9_62_CURVE), + ASN1_SIMPLE(ECPARAMETERS, base, ASN1_OCTET_STRING), + ASN1_SIMPLE(ECPARAMETERS, order, ASN1_INTEGER), + ASN1_OPT(ECPARAMETERS, cofactor, ASN1_INTEGER) +} ASN1_SEQUENCE_END(ECPARAMETERS); + +DECLARE_ASN1_ALLOC_FUNCTIONS(ECPARAMETERS); +IMPLEMENT_ASN1_ALLOC_FUNCTIONS(ECPARAMETERS); + +typedef struct ecpk_parameters_st { + int type; + union { + ASN1_OBJECT *named_curve; + ECPARAMETERS *parameters; + } value; +} ECPKPARAMETERS; + +/* SEC1 ECPrivateKey */ +typedef struct ec_privatekey_st { + long version; + ASN1_OCTET_STRING *privateKey; + ECPKPARAMETERS *parameters; + ASN1_BIT_STRING *publicKey; +} EC_PRIVATEKEY; + +ASN1_CHOICE(ECPKPARAMETERS) = { + ASN1_SIMPLE(ECPKPARAMETERS, value.named_curve, ASN1_OBJECT), + ASN1_SIMPLE(ECPKPARAMETERS, value.parameters, ECPARAMETERS), +} ASN1_CHOICE_END(ECPKPARAMETERS); + +DECLARE_ASN1_FUNCTIONS_const(ECPKPARAMETERS); +DECLARE_ASN1_ENCODE_FUNCTIONS_const(ECPKPARAMETERS, ECPKPARAMETERS); +IMPLEMENT_ASN1_FUNCTIONS_const(ECPKPARAMETERS); + +ASN1_SEQUENCE(EC_PRIVATEKEY) = { + ASN1_SIMPLE(EC_PRIVATEKEY, version, LONG), + ASN1_SIMPLE(EC_PRIVATEKEY, privateKey, ASN1_OCTET_STRING), + ASN1_EXP_OPT(EC_PRIVATEKEY, parameters, ECPKPARAMETERS, 0), + ASN1_EXP_OPT(EC_PRIVATEKEY, publicKey, ASN1_BIT_STRING, 1), +} ASN1_SEQUENCE_END(EC_PRIVATEKEY); + +DECLARE_ASN1_FUNCTIONS_const(EC_PRIVATEKEY); +DECLARE_ASN1_ENCODE_FUNCTIONS_const(EC_PRIVATEKEY, EC_PRIVATEKEY); +IMPLEMENT_ASN1_FUNCTIONS_const(EC_PRIVATEKEY); + + +ECPKPARAMETERS *ec_asn1_group2pkparameters(const EC_GROUP *group, + ECPKPARAMETERS *params) { + int ok = 0, nid; + ECPKPARAMETERS *ret = params; + + if (ret == NULL) { + ret = ECPKPARAMETERS_new(); + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, ec_asn1_group2pkparameters, ERR_R_MALLOC_FAILURE); + return NULL; + } + } else { + if (ret->value.named_curve) { + ASN1_OBJECT_free(ret->value.named_curve); + } + } + + /* use the ASN.1 OID to describe the the elliptic curve parameters. */ + nid = EC_GROUP_get_curve_name(group); + if (nid) { + ret->type = 0; + ret->value.named_curve = (ASN1_OBJECT*) OBJ_nid2obj(nid); + ok = ret->value.named_curve != NULL; + } + + if (!ok) { + ECPKPARAMETERS_free(ret); + return NULL; + } + + return ret; +} + +EC_GROUP *ec_asn1_pkparameters2group(const ECPKPARAMETERS *params) { + EC_GROUP *ret = NULL; + int nid = 0; + + if (params == NULL) { + OPENSSL_PUT_ERROR(EC, ec_asn1_pkparameters2group, EC_R_MISSING_PARAMETERS); + return NULL; + } + + if (params->type != 0) { + OPENSSL_PUT_ERROR(EC, ec_asn1_pkparameters2group, EC_R_NON_NAMED_CURVE); + return NULL; + } + + nid = OBJ_obj2nid(params->value.named_curve); + ret = EC_GROUP_new_by_curve_name(nid); + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, ec_asn1_pkparameters2group, + EC_R_EC_GROUP_NEW_BY_NAME_FAILURE); + return NULL; + } + + return ret; +} + +static EC_GROUP *d2i_ECPKParameters(EC_GROUP **groupp, const uint8_t **inp, + long len) { + EC_GROUP *group = NULL; + ECPKPARAMETERS *params = NULL; + + params = d2i_ECPKPARAMETERS(NULL, inp, len); + if (params == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPKParameters, EC_R_D2I_ECPKPARAMETERS_FAILURE); + ECPKPARAMETERS_free(params); + return NULL; + } + + group = ec_asn1_pkparameters2group(params); + if (group == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPKParameters, EC_R_PKPARAMETERS2GROUP_FAILURE); + ECPKPARAMETERS_free(params); + return NULL; + } + + if (groupp && *groupp) { + EC_GROUP_free(*groupp); + } + if (groupp) { + *groupp = group; + } + + ECPKPARAMETERS_free(params); + return group; +} + +static int i2d_ECPKParameters(const EC_GROUP *group, uint8_t **outp) { + int ret = 0; + ECPKPARAMETERS *tmp = ec_asn1_group2pkparameters(group, NULL); + if (tmp == NULL) { + OPENSSL_PUT_ERROR(EC, i2d_ECPKParameters, EC_R_GROUP2PKPARAMETERS_FAILURE); + return 0; + } + ret = i2d_ECPKPARAMETERS(tmp, outp); + if (ret == 0) { + OPENSSL_PUT_ERROR(EC, i2d_ECPKParameters, EC_R_I2D_ECPKPARAMETERS_FAILURE); + ECPKPARAMETERS_free(tmp); + return 0; + } + ECPKPARAMETERS_free(tmp); + return ret; +} + +EC_KEY *d2i_ECPrivateKey(EC_KEY **a, const uint8_t **in, long len) { + int ok = 0; + EC_KEY *ret = NULL; + EC_PRIVATEKEY *priv_key = NULL; + + priv_key = EC_PRIVATEKEY_new(); + if (priv_key == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_MALLOC_FAILURE); + return NULL; + } + + priv_key = d2i_EC_PRIVATEKEY(&priv_key, in, len); + if (priv_key == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_EC_LIB); + EC_PRIVATEKEY_free(priv_key); + return NULL; + } + + if (a == NULL || *a == NULL) { + ret = EC_KEY_new(); + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_MALLOC_FAILURE); + goto err; + } + if (a) { + *a = ret; + } + } else { + ret = *a; + } + + if (priv_key->parameters) { + if (ret->group) { + EC_GROUP_free(ret->group); + } + ret->group = ec_asn1_pkparameters2group(priv_key->parameters); + } + + if (ret->group == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_EC_LIB); + goto err; + } + + ret->version = priv_key->version; + + if (priv_key->privateKey) { + ret->priv_key = + BN_bin2bn(M_ASN1_STRING_data(priv_key->privateKey), + M_ASN1_STRING_length(priv_key->privateKey), ret->priv_key); + if (ret->priv_key == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_BN_LIB); + goto err; + } + } else { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, EC_R_MISSING_PRIVATE_KEY); + goto err; + } + + /* TODO(fork): loading the public key is silly. Why not calculate it? */ + if (priv_key->publicKey) { + const uint8_t *pub_oct; + size_t pub_oct_len; + + if (ret->pub_key) { + EC_POINT_free(ret->pub_key); + } + ret->pub_key = EC_POINT_new(ret->group); + if (ret->pub_key == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_EC_LIB); + goto err; + } + pub_oct = M_ASN1_STRING_data(priv_key->publicKey); + pub_oct_len = M_ASN1_STRING_length(priv_key->publicKey); + /* save the point conversion form */ + ret->conv_form = (point_conversion_form_t)(pub_oct[0] & ~0x01); + if (!EC_POINT_oct2point(ret->group, ret->pub_key, pub_oct, pub_oct_len, + NULL)) { + OPENSSL_PUT_ERROR(EC, d2i_ECPrivateKey, ERR_R_EC_LIB); + goto err; + } + } + + ok = 1; + +err: + if (!ok) { + if (ret) { + EC_KEY_free(ret); + } + ret = NULL; + } + + if (priv_key) { + EC_PRIVATEKEY_free(priv_key); + } + + return ret; +} + +int i2d_ECPrivateKey(const EC_KEY *key, uint8_t **outp) { + int ret = 0, ok = 0; + uint8_t *buffer = NULL; + size_t buf_len = 0, tmp_len; + EC_PRIVATEKEY *priv_key = NULL; + + if (key == NULL || key->group == NULL || key->priv_key == NULL) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_PASSED_NULL_PARAMETER); + goto err; + } + + priv_key = EC_PRIVATEKEY_new(); + if (priv_key == NULL) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_MALLOC_FAILURE); + goto err; + } + + priv_key->version = key->version; + + buf_len = BN_num_bytes(key->priv_key); + buffer = OPENSSL_malloc(buf_len); + if (buffer == NULL) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_MALLOC_FAILURE); + goto err; + } + + if (!BN_bn2bin(key->priv_key, buffer)) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_BN_LIB); + goto err; + } + + if (!M_ASN1_OCTET_STRING_set(priv_key->privateKey, buffer, buf_len)) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_ASN1_LIB); + goto err; + } + + /* TODO(fork): replace this flexibility with key sensible default? */ + if (!(key->enc_flag & EC_PKEY_NO_PARAMETERS)) { + if ((priv_key->parameters = ec_asn1_group2pkparameters( + key->group, priv_key->parameters)) == NULL) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_EC_LIB); + goto err; + } + } + + /* TODO(fork): replace this flexibility with key sensible default? */ + if (!(key->enc_flag & EC_PKEY_NO_PUBKEY)) { + priv_key->publicKey = M_ASN1_BIT_STRING_new(); + if (priv_key->publicKey == NULL) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_MALLOC_FAILURE); + goto err; + } + + tmp_len = EC_POINT_point2oct(key->group, key->pub_key, key->conv_form, NULL, + 0, NULL); + + if (tmp_len > buf_len) { + uint8_t *tmp_buffer = OPENSSL_realloc(buffer, tmp_len); + if (!tmp_buffer) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_MALLOC_FAILURE); + goto err; + } + buffer = tmp_buffer; + buf_len = tmp_len; + } + + if (!EC_POINT_point2oct(key->group, key->pub_key, key->conv_form, buffer, + buf_len, NULL)) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_EC_LIB); + goto err; + } + + priv_key->publicKey->flags &= ~(ASN1_STRING_FLAG_BITS_LEFT | 0x07); + priv_key->publicKey->flags |= ASN1_STRING_FLAG_BITS_LEFT; + if (!M_ASN1_BIT_STRING_set(priv_key->publicKey, buffer, buf_len)) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_ASN1_LIB); + goto err; + } + } + + ret = i2d_EC_PRIVATEKEY(priv_key, outp); + if (ret == 0) { + OPENSSL_PUT_ERROR(EC, i2d_ECPrivateKey, ERR_R_EC_LIB); + goto err; + } + ok = 1; + +err: + if (buffer) { + OPENSSL_free(buffer); + } + if (priv_key) { + EC_PRIVATEKEY_free(priv_key); + } + return (ok ? ret : 0); +} + +int i2d_ECParameters(const EC_KEY *key, uint8_t **outp) { + if (key == NULL) { + OPENSSL_PUT_ERROR(EC, i2d_ECParameters, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + return i2d_ECPKParameters(key->group, outp); +} + +EC_KEY *d2i_ECParameters(EC_KEY **key, const uint8_t **inp, long len) { + EC_KEY *ret; + + if (inp == NULL || *inp == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECParameters, ERR_R_PASSED_NULL_PARAMETER); + return NULL; + } + + if (key == NULL || *key == NULL) { + ret = EC_KEY_new(); + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, d2i_ECParameters, ERR_R_MALLOC_FAILURE); + return NULL; + } + if (key) { + *key = ret; + } + } else { + ret = *key; + } + + if (!d2i_ECPKParameters(&ret->group, inp, len)) { + OPENSSL_PUT_ERROR(EC, d2i_ECParameters, ERR_R_EC_LIB); + return NULL; + } + + return ret; +} + +EC_KEY *o2i_ECPublicKey(EC_KEY **keyp, const uint8_t **inp, long len) { + EC_KEY *ret = NULL; + + if (keyp == NULL || *keyp == NULL || (*keyp)->group == NULL) { + OPENSSL_PUT_ERROR(EC, o2i_ECPublicKey, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + ret = *keyp; + if (ret->pub_key == NULL && + (ret->pub_key = EC_POINT_new(ret->group)) == NULL) { + OPENSSL_PUT_ERROR(EC, o2i_ECPublicKey, ERR_R_MALLOC_FAILURE); + return 0; + } + if (!EC_POINT_oct2point(ret->group, ret->pub_key, *inp, len, NULL)) { + OPENSSL_PUT_ERROR(EC, o2i_ECPublicKey, ERR_R_EC_LIB); + return 0; + } + /* save the point conversion form */ + ret->conv_form = (point_conversion_form_t)(*inp[0] & ~0x01); + *inp += len; + return ret; +} + +int i2o_ECPublicKey(const EC_KEY *key, uint8_t **outp) { + size_t buf_len = 0; + int new_buffer = 0; + + if (key == NULL) { + OPENSSL_PUT_ERROR(EC, i2o_ECPublicKey, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + + buf_len = EC_POINT_point2oct(key->group, key->pub_key, key->conv_form, NULL, + 0, NULL); + + if (outp == NULL || buf_len == 0) { + /* out == NULL => just return the length of the octet string */ + return buf_len; + } + + if (*outp == NULL) { + *outp = OPENSSL_malloc(buf_len); + if (*outp == NULL) { + OPENSSL_PUT_ERROR(EC, i2o_ECPublicKey, ERR_R_MALLOC_FAILURE); + return 0; + } + new_buffer = 1; + } + if (!EC_POINT_point2oct(key->group, key->pub_key, key->conv_form, *outp, + buf_len, NULL)) { + OPENSSL_PUT_ERROR(EC, i2o_ECPublicKey, ERR_R_EC_LIB); + OPENSSL_free(*outp); + *outp = NULL; + return 0; + } + + if (!new_buffer) { + *outp += buf_len; + } + return buf_len; +}
diff --git a/crypto/ec/ec_error.c b/crypto/ec/ec_error.c new file mode 100644 index 0000000..195b1af --- /dev/null +++ b/crypto/ec/ec_error.c
@@ -0,0 +1,106 @@ +/* Copyright (c) 2014, Google Inc. + * + * Permission to use, copy, modify, and/or distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY + * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION + * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN + * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ + +#include <openssl/err.h> + +#include "ec.h" + +const ERR_STRING_DATA EC_error_string_data[] = { + {ERR_PACK(ERR_LIB_EC, EC_F_EC_GROUP_copy, 0), "EC_GROUP_copy"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_GROUP_get_degree, 0), "EC_GROUP_get_degree"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_GROUP_new_by_curve_name, 0), "EC_GROUP_new_by_curve_name"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_check_key, 0), "EC_KEY_check_key"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_copy, 0), "EC_KEY_copy"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_generate_key, 0), "EC_KEY_generate_key"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_new_method, 0), "EC_KEY_new_method"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_KEY_set_public_key_affine_coordinates, 0), "EC_KEY_set_public_key_affine_coordinates"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_add, 0), "EC_POINT_add"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_cmp, 0), "EC_POINT_cmp"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_copy, 0), "EC_POINT_copy"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_dbl, 0), "EC_POINT_dbl"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_dup, 0), "EC_POINT_dup"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_get_affine_coordinates_GFp, 0), "EC_POINT_get_affine_coordinates_GFp"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_invert, 0), "EC_POINT_invert"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_is_at_infinity, 0), "EC_POINT_is_at_infinity"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_is_on_curve, 0), "EC_POINT_is_on_curve"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_make_affine, 0), "EC_POINT_make_affine"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_new, 0), "EC_POINT_new"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_oct2point, 0), "EC_POINT_oct2point"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_point2oct, 0), "EC_POINT_point2oct"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_set_affine_coordinates_GFp, 0), "EC_POINT_set_affine_coordinates_GFp"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_set_compressed_coordinates_GFp, 0), "EC_POINT_set_compressed_coordinates_GFp"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINT_set_to_infinity, 0), "EC_POINT_set_to_infinity"}, + {ERR_PACK(ERR_LIB_EC, EC_F_EC_POINTs_make_affine, 0), "EC_POINTs_make_affine"}, + {ERR_PACK(ERR_LIB_EC, EC_F_compute_wNAF, 0), "compute_wNAF"}, + {ERR_PACK(ERR_LIB_EC, EC_F_d2i_ECPKParameters, 0), "d2i_ECPKParameters"}, + {ERR_PACK(ERR_LIB_EC, EC_F_d2i_ECParameters, 0), "d2i_ECParameters"}, + {ERR_PACK(ERR_LIB_EC, EC_F_d2i_ECPrivateKey, 0), "d2i_ECPrivateKey"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_decode, 0), "ec_GFp_mont_field_decode"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_encode, 0), "ec_GFp_mont_field_encode"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_mul, 0), "ec_GFp_mont_field_mul"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_set_to_one, 0), "ec_GFp_mont_field_set_to_one"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_field_sqr, 0), "ec_GFp_mont_field_sqr"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_mont_group_set_curve, 0), "ec_GFp_mont_group_set_curve"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_group_check_discriminant, 0), "ec_GFp_simple_group_check_discriminant"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_group_set_curve, 0), "ec_GFp_simple_group_set_curve"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_make_affine, 0), "ec_GFp_simple_make_affine"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_oct2point, 0), "ec_GFp_simple_oct2point"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_point2oct, 0), "ec_GFp_simple_point2oct"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_point_get_affine_coordinates, 0), "ec_GFp_simple_point_get_affine_coordinates"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_point_set_affine_coordinates, 0), "ec_GFp_simple_point_set_affine_coordinates"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_points_make_affine, 0), "ec_GFp_simple_points_make_affine"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_GFp_simple_set_compressed_coordinates, 0), "ec_GFp_simple_set_compressed_coordinates"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_asn1_group2pkparameters, 0), "ec_asn1_group2pkparameters"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_asn1_pkparameters2group, 0), "ec_asn1_pkparameters2group"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_group_new, 0), "ec_group_new"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_group_new_curve_GFp, 0), "ec_group_new_curve_GFp"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_group_new_from_data, 0), "ec_group_new_from_data"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_point_set_Jprojective_coordinates_GFp, 0), "ec_point_set_Jprojective_coordinates_GFp"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_pre_comp_new, 0), "ec_pre_comp_new"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_wNAF_mul, 0), "ec_wNAF_mul"}, + {ERR_PACK(ERR_LIB_EC, EC_F_ec_wNAF_precompute_mult, 0), "ec_wNAF_precompute_mult"}, + {ERR_PACK(ERR_LIB_EC, EC_F_i2d_ECPKParameters, 0), "i2d_ECPKParameters"}, + {ERR_PACK(ERR_LIB_EC, EC_F_i2d_ECParameters, 0), "i2d_ECParameters"}, + {ERR_PACK(ERR_LIB_EC, EC_F_i2d_ECPrivateKey, 0), "i2d_ECPrivateKey"}, + {ERR_PACK(ERR_LIB_EC, EC_F_i2o_ECPublicKey, 0), "i2o_ECPublicKey"}, + {ERR_PACK(ERR_LIB_EC, EC_F_o2i_ECPublicKey, 0), "o2i_ECPublicKey"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_BUFFER_TOO_SMALL), "BUFFER_TOO_SMALL"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_COORDINATES_OUT_OF_RANGE), "COORDINATES_OUT_OF_RANGE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_D2I_ECPKPARAMETERS_FAILURE), "D2I_ECPKPARAMETERS_FAILURE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_EC_GROUP_NEW_BY_NAME_FAILURE), "EC_GROUP_NEW_BY_NAME_FAILURE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_GF2M_NOT_SUPPORTED), "GF2M_NOT_SUPPORTED"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_GROUP2PKPARAMETERS_FAILURE), "GROUP2PKPARAMETERS_FAILURE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_I2D_ECPKPARAMETERS_FAILURE), "I2D_ECPKPARAMETERS_FAILURE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INCOMPATIBLE_OBJECTS), "INCOMPATIBLE_OBJECTS"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_COMPRESSED_POINT), "INVALID_COMPRESSED_POINT"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_COMPRESSION_BIT), "INVALID_COMPRESSION_BIT"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_ENCODING), "INVALID_ENCODING"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_FIELD), "INVALID_FIELD"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_FORM), "INVALID_FORM"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_GROUP_ORDER), "INVALID_GROUP_ORDER"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_INVALID_PRIVATE_KEY), "INVALID_PRIVATE_KEY"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PARAMETERS), "MISSING_PARAMETERS"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_MISSING_PRIVATE_KEY), "MISSING_PRIVATE_KEY"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_NON_NAMED_CURVE), "NON_NAMED_CURVE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_NOT_INITIALIZED), "NOT_INITIALIZED"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_PKPARAMETERS2GROUP_FAILURE), "PKPARAMETERS2GROUP_FAILURE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_AT_INFINITY), "POINT_AT_INFINITY"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_POINT_IS_NOT_ON_CURVE), "POINT_IS_NOT_ON_CURVE"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_SLOT_FULL), "SLOT_FULL"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNDEFINED_GENERATOR), "UNDEFINED_GENERATOR"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_GROUP), "UNKNOWN_GROUP"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_UNKNOWN_ORDER), "UNKNOWN_ORDER"}, + {ERR_PACK(ERR_LIB_EC, 0, EC_R_WRONG_ORDER), "WRONG_ORDER"}, + {0, NULL}, +};
diff --git a/crypto/ec/ec_key.c b/crypto/ec/ec_key.c new file mode 100644 index 0000000..9bef698 --- /dev/null +++ b/crypto/ec/ec_key.c
@@ -0,0 +1,513 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#include <openssl/ec_key.h> + +#include <openssl/ec.h> +#include <openssl/engine.h> +#include <openssl/err.h> +#include <openssl/ex_data.h> +#include <openssl/mem.h> + +#include "internal.h" + + +EC_KEY *EC_KEY_new(void) { return EC_KEY_new_method(NULL); } + +EC_KEY *EC_KEY_new_method(const ENGINE *engine) { + EC_KEY *ret = (EC_KEY *)OPENSSL_malloc(sizeof(EC_KEY)); + if (ret == NULL) { + OPENSSL_PUT_ERROR(EC, EC_KEY_new_method, ERR_R_MALLOC_FAILURE); + return NULL; + } + + memset(ret, 0, sizeof(EC_KEY)); + + if (engine) { + ret->ecdsa_meth = ENGINE_get_ECDSA_method(engine); + } + if (ret->ecdsa_meth) { + METHOD_ref(ret->ecdsa_meth); + } + + ret->version = 1; + ret->conv_form = POINT_CONVERSION_UNCOMPRESSED; + ret->references = 1; + + if (!CRYPTO_new_ex_data(CRYPTO_EX_INDEX_EC_KEY, ret, &ret->ex_data)) { + goto err1; + } + + if (ret->ecdsa_meth && ret->ecdsa_meth->init && !ret->ecdsa_meth->init(ret)) { + goto err2; + } + + return ret; + +err2: + CRYPTO_free_ex_data(CRYPTO_EX_INDEX_EC_KEY, ret, &ret->ex_data); +err1: + if (ret->ecdsa_meth) { + METHOD_unref(ret->ecdsa_meth); + } + OPENSSL_free(ret); + return NULL; +} + +EC_KEY *EC_KEY_new_by_curve_name(int nid) { + EC_KEY *ret = EC_KEY_new(); + if (ret == NULL) { + return NULL; + } + ret->group = EC_GROUP_new_by_curve_name(nid); + if (ret->group == NULL) { + EC_KEY_free(ret); + return NULL; + } + return ret; +} + +void EC_KEY_free(EC_KEY *r) { + if (r == NULL) { + return; + } + + if (CRYPTO_add(&r->references, -1, CRYPTO_LOCK_EC)) { + return; + } + + if (r->ecdsa_meth) { + if (r->ecdsa_meth->finish) { + r->ecdsa_meth->finish(r); + } + METHOD_unref(r->ecdsa_meth); + } + + if (r->group != NULL) { + EC_GROUP_free(r->group); + } + if (r->pub_key != NULL) { + EC_POINT_free(r->pub_key); + } + if (r->priv_key != NULL) { + BN_clear_free(r->priv_key); + } + + CRYPTO_free_ex_data(CRYPTO_EX_INDEX_EC_KEY, r, &r->ex_data); + + OPENSSL_cleanse((void *)r, sizeof(EC_KEY)); + OPENSSL_free(r); +} + +EC_KEY *EC_KEY_copy(EC_KEY *dest, const EC_KEY *src) { + if (dest == NULL || src == NULL) { + OPENSSL_PUT_ERROR(EC, EC_KEY_copy, ERR_R_PASSED_NULL_PARAMETER); + return NULL; + } + /* copy the parameters */ + if (src->group) { + /* TODO(fork): duplicating the group seems wasteful. */ + const EC_METHOD *meth = src->group->meth; + /* clear the old group */ + if (dest->group) { + EC_GROUP_free(dest->group); + } + dest->group = ec_group_new(meth); + if (dest->group == NULL) { + return NULL; + } + if (!EC_GROUP_copy(dest->group, src->group)) { + return NULL; + } + } + + /* copy the public key */ + if (src->pub_key && src->group) { + if (dest->pub_key) { + EC_POINT_free(dest->pub_key); + } + dest->pub_key = EC_POINT_new(src->group); + if (dest->pub_key == NULL) { + return NULL; + } + if (!EC_POINT_copy(dest->pub_key, src->pub_key)) { + return NULL; + } + } + + /* copy the private key */ + if (src->priv_key) { + if (dest->priv_key == NULL) { + dest->priv_key = BN_new(); + if (dest->priv_key == NULL) { + return NULL; + } + } + if (!BN_copy(dest->priv_key, src->priv_key)) { + return NULL; + } + } + /* copy method/extra data */ + CRYPTO_free_ex_data(CRYPTO_EX_INDEX_EC_KEY, dest, &dest->ex_data); + if (!CRYPTO_dup_ex_data(CRYPTO_EX_INDEX_EC_KEY, &dest->ex_data, + &src->ex_data)) { + return NULL; + } + + /* copy the rest */ + dest->enc_flag = src->enc_flag; + dest->conv_form = src->conv_form; + dest->version = src->version; + dest->flags = src->flags; + + return dest; +} + +EC_KEY *EC_KEY_dup(const EC_KEY *ec_key) { + EC_KEY *ret = EC_KEY_new(); + if (ret == NULL) { + return NULL; + } + if (EC_KEY_copy(ret, ec_key) == NULL) { + EC_KEY_free(ret); + return NULL; + } + return ret; +} + +int EC_KEY_up_ref(EC_KEY *r) { + return CRYPTO_add(&r->references, 1, CRYPTO_LOCK_EC) > 1; +} + +const EC_GROUP *EC_KEY_get0_group(const EC_KEY *key) { return key->group; } + +int EC_KEY_set_group(EC_KEY *key, const EC_GROUP *group) { + if (key->group != NULL) { + EC_GROUP_free(key->group); + } + /* TODO(fork): duplicating the group seems wasteful but see + * |EC_KEY_set_conv_form|. */ + key->group = EC_GROUP_dup(group); + return (key->group == NULL) ? 0 : 1; +} + +const BIGNUM *EC_KEY_get0_private_key(const EC_KEY *key) { + return key->priv_key; +} + +int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *priv_key) { + if (key->priv_key) { + BN_clear_free(key->priv_key); + } + key->priv_key = BN_dup(priv_key); + return (key->priv_key == NULL) ? 0 : 1; +} + +const EC_POINT *EC_KEY_get0_public_key(const EC_KEY *key) { + return key->pub_key; +} + +int EC_KEY_set_public_key(EC_KEY *key, const EC_POINT *pub_key) { + if (key->pub_key != NULL) { + EC_POINT_free(key->pub_key); + } + key->pub_key = EC_POINT_dup(pub_key, key->group); + return (key->pub_key == NULL) ? 0 : 1; +} + +unsigned int EC_KEY_get_enc_flags(const EC_KEY *key) { return key->enc_flag; } + +void EC_KEY_set_enc_flags(EC_KEY *key, unsigned int flags) { + key->enc_flag = flags; +} + +point_conversion_form_t EC_KEY_get_conv_form(const EC_KEY *key) { + return key->conv_form; +} + +void EC_KEY_set_conv_form(EC_KEY *key, point_conversion_form_t cform) { + key->conv_form = cform; + if (key->group != NULL) { + EC_GROUP_set_point_conversion_form(key->group, cform); + } +} + +int EC_KEY_precompute_mult(EC_KEY *key, BN_CTX *ctx) { + if (key->group == NULL) { + return 0; + } + return EC_GROUP_precompute_mult(key->group, ctx); +} + +int EC_KEY_check_key(const EC_KEY *eckey) { + int ok = 0; + BN_CTX *ctx = NULL; + const BIGNUM *order = NULL; + EC_POINT *point = NULL; + + if (!eckey || !eckey->group || !eckey->pub_key) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + + if (EC_POINT_is_at_infinity(eckey->group, eckey->pub_key)) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, EC_R_POINT_AT_INFINITY); + goto err; + } + + ctx = BN_CTX_new(); + point = EC_POINT_new(eckey->group); + + if (ctx == NULL || + point == NULL) { + goto err; + } + + /* testing whether the pub_key is on the elliptic curve */ + if (!EC_POINT_is_on_curve(eckey->group, eckey->pub_key, ctx)) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, EC_R_POINT_IS_NOT_ON_CURVE); + goto err; + } + /* testing whether pub_key * order is the point at infinity */ + /* TODO(fork): can this be skipped if the cofactor is one or if we're about + * to check the private key, below? */ + order = &eckey->group->order; + if (BN_is_zero(order)) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, EC_R_INVALID_GROUP_ORDER); + goto err; + } + if (!EC_POINT_mul(eckey->group, point, NULL, eckey->pub_key, order, ctx)) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, ERR_R_EC_LIB); + goto err; + } + if (!EC_POINT_is_at_infinity(eckey->group, point)) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, EC_R_WRONG_ORDER); + goto err; + } + /* in case the priv_key is present : + * check if generator * priv_key == pub_key + */ + if (eckey->priv_key) { + if (BN_cmp(eckey->priv_key, order) >= 0) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, EC_R_WRONG_ORDER); + goto err; + } + if (!EC_POINT_mul(eckey->group, point, eckey->priv_key, NULL, NULL, ctx)) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, ERR_R_EC_LIB); + goto err; + } + if (EC_POINT_cmp(eckey->group, point, eckey->pub_key, ctx) != 0) { + OPENSSL_PUT_ERROR(EC, EC_KEY_check_key, EC_R_INVALID_PRIVATE_KEY); + goto err; + } + } + ok = 1; + +err: + if (ctx != NULL) + BN_CTX_free(ctx); + if (point != NULL) + EC_POINT_free(point); + return ok; +} + +int EC_KEY_set_public_key_affine_coordinates(EC_KEY *key, BIGNUM *x, + BIGNUM *y) { + BN_CTX *ctx = NULL; + BIGNUM *tx, *ty; + EC_POINT *point = NULL; + int ok = 0; + + if (!key || !key->group || !x || !y) { + OPENSSL_PUT_ERROR(EC, EC_KEY_set_public_key_affine_coordinates, + ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + ctx = BN_CTX_new(); + point = EC_POINT_new(key->group); + + if (ctx == NULL || + point == NULL) { + goto err; + } + + tx = BN_CTX_get(ctx); + ty = BN_CTX_get(ctx); + + if (!EC_POINT_set_affine_coordinates_GFp(key->group, point, x, y, ctx) || + !EC_POINT_get_affine_coordinates_GFp(key->group, point, tx, ty, ctx)) { + goto err; + } + + /* Check if retrieved coordinates match originals: if not values + * are out of range. */ + if (BN_cmp(x, tx) || BN_cmp(y, ty)) { + OPENSSL_PUT_ERROR(EC, EC_KEY_set_public_key_affine_coordinates, + EC_R_COORDINATES_OUT_OF_RANGE); + goto err; + } + + if (!EC_KEY_set_public_key(key, point)) { + goto err; + } + + if (EC_KEY_check_key(key) == 0) { + goto err; + } + + ok = 1; + +err: + if (ctx) + BN_CTX_free(ctx); + if (point) + EC_POINT_free(point); + return ok; +} + +int EC_KEY_generate_key(EC_KEY *eckey) { + int ok = 0; + BN_CTX *ctx = NULL; + BIGNUM *priv_key = NULL, *order = NULL; + EC_POINT *pub_key = NULL; + + if (!eckey || !eckey->group) { + OPENSSL_PUT_ERROR(EC, EC_KEY_generate_key, ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + + order = BN_new(); + ctx = BN_CTX_new(); + + if (order == NULL || + ctx == NULL) { + goto err; + } + + if (eckey->priv_key == NULL) { + priv_key = BN_new(); + if (priv_key == NULL) { + goto err; + } + } else { + priv_key = eckey->priv_key; + } + + if (!EC_GROUP_get_order(eckey->group, order, ctx)) { + goto err; + } + + do { + if (!BN_rand_range(priv_key, order)) { + goto err; + } + } while (BN_is_zero(priv_key)); + + if (eckey->pub_key == NULL) { + pub_key = EC_POINT_new(eckey->group); + if (pub_key == NULL) { + goto err; + } + } else { + pub_key = eckey->pub_key; + } + + if (!EC_POINT_mul(eckey->group, pub_key, priv_key, NULL, NULL, ctx)) { + goto err; + } + + eckey->priv_key = priv_key; + eckey->pub_key = pub_key; + + ok = 1; + +err: + if (order) + BN_free(order); + if (pub_key != NULL && eckey->pub_key == NULL) + EC_POINT_free(pub_key); + if (priv_key != NULL && eckey->priv_key == NULL) + BN_free(priv_key); + if (ctx != NULL) + BN_CTX_free(ctx); + return ok; +} + +int EC_KEY_get_ex_new_index(long argl, void *argp, CRYPTO_EX_new *new_func, + CRYPTO_EX_dup *dup_func, + CRYPTO_EX_free *free_func) { + return CRYPTO_get_ex_new_index(CRYPTO_EX_INDEX_EC_KEY, argl, argp, new_func, + dup_func, free_func); +} + +int EC_KEY_set_ex_data(EC_KEY *d, int idx, void *arg) { + return CRYPTO_set_ex_data(&d->ex_data, idx, arg); +} + +void *EC_KEY_get_ex_data(const EC_KEY *d, int idx) { + return CRYPTO_get_ex_data(&d->ex_data, idx); +}
diff --git a/crypto/ec/ec_key.h b/crypto/ec/ec_key.h new file mode 100644 index 0000000..ce4846b --- /dev/null +++ b/crypto/ec/ec_key.h
@@ -0,0 +1,260 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#ifndef OPENSSL_HEADER_EC_KEY_H +#define OPENSSL_HEADER_EC_KEY_H + +#include <openssl/base.h> + +#include <openssl/ec.h> +#include <openssl/engine.h> +#include <openssl/ex_data.h> + +#if defined(__cplusplus) +extern "C" { +#endif + + +/* ec_key.h conatins functions that handle elliptic-curve points that are + * public/private keys. */ + + +/* EC key objects. */ + +/* EC_KEY_new returns a fresh |EC_KEY| object or NULL on error. */ +EC_KEY *EC_KEY_new(void); + +/* EC_KEY_new_method acts the same as |EC_KEY_new|, but takes an explicit + * |ENGINE|. */ +EC_KEY *EC_KEY_new_method(const ENGINE *engine); + +/* EC_KEY_new_by_curve_name returns a fresh EC_KEY for group specified by |nid| + * or NULL on error. */ +EC_KEY *EC_KEY_new_by_curve_name(int nid); + +/* EC_KEY_free frees all the data owned by |key| and |key| itself. */ +void EC_KEY_free(EC_KEY *key); + +/* EC_KEY_copy sets |dst| equal to |src| and returns |dst| or NULL on error. */ +EC_KEY *EC_KEY_copy(EC_KEY *dst, const EC_KEY *src); + +/* EC_KEY_dup returns a fresh copy of |src| or NULL on error. */ +EC_KEY *EC_KEY_dup(const EC_KEY *src); + +/* EC_KEY_up_ref increases the reference count of |key|. It returns one on + * success and zero otherwise. */ +int EC_KEY_up_ref(EC_KEY *key); + +/* EC_KEY_get0_group returns a pointer to the |EC_GROUP| object inside |key|. */ +const EC_GROUP *EC_KEY_get0_group(const EC_KEY *key); + +/* EC_KEY_set_group sets the |EC_GROUP| object that |key| will use to |group|. + * It returns one on success and zero otherwise. */ +int EC_KEY_set_group(EC_KEY *key, const EC_GROUP *group); + +/* EC_KEY_get0_private_key returns a pointer to the private key inside |key|. */ +const BIGNUM *EC_KEY_get0_private_key(const EC_KEY *key); + +/* EC_KEY_set_private_key sets the private key of |key| to |priv|. It returns + * one on success and zero otherwise. */ +int EC_KEY_set_private_key(EC_KEY *key, const BIGNUM *prv); + +/* EC_KEY_get0_public_key returns a pointer to the public key point inside + * |key|. */ +const EC_POINT *EC_KEY_get0_public_key(const EC_KEY *key); + +/* EC_KEY_set_public_key sets the public key of |key| to |pub|, by copying it. + * It returns one on success and zero otherwise. */ +int EC_KEY_set_public_key(EC_KEY *key, const EC_POINT *pub); + +#define EC_PKEY_NO_PARAMETERS 0x001 +#define EC_PKEY_NO_PUBKEY 0x002 + +/* EC_KEY_get_enc_flags returns the encoding flags for |key|, which is a + * bitwise-OR of |EC_PKEY_*| values. */ +unsigned EC_KEY_get_enc_flags(const EC_KEY *key); + +/* EC_KEY_set_enc_flags sets the encoding flags for |key|, which is a + * bitwise-OR of |EC_PKEY_*| values. */ +void EC_KEY_set_enc_flags(EC_KEY *key, unsigned flags); + +/* EC_KEY_get_conv_form returns the conversation form that will be used by + * |key|. */ +point_conversion_form_t EC_KEY_get_conv_form(const EC_KEY *key); + +/* EC_KEY_set_conv_form sets the conversion form to be used by |key|. */ +void EC_KEY_set_conv_form(EC_KEY *key, point_conversion_form_t cform); + +/* EC_KEY_precompute_mult precomputes multiplies of the generator of the + * underlying group in order to speed up operations that calculate generator + * multiples. If |ctx| is not NULL, it may be used. It returns one on success + * and zero otherwise. */ +int EC_KEY_precompute_mult(EC_KEY *key, BN_CTX *ctx); + +/* EC_KEY_check_key performs several checks on |key| (possibly including an + * expensive check that the public key is in the primary subgroup). It returns + * one if all checks pass and zero otherwise. If it returns zero then detail + * about the problem can be found on the error stack. */ +int EC_KEY_check_key(const EC_KEY *key); + +/* EC_KEY_set_public_key_affine_coordinates sets the public key in |key| to + * (|x|, |y|). It returns one on success and zero otherwise. */ +int EC_KEY_set_public_key_affine_coordinates(EC_KEY *key, BIGNUM *x, BIGNUM *y); + + +/* Key generation. */ + +/* EC_KEY_generate_key generates a random, private key, calculates the + * corresponding public key and stores both in |key|. It returns one on success + * or zero otherwise. */ +int EC_KEY_generate_key(EC_KEY *key); + + +/* Serialisation. */ + +/* d2i_ECPrivateKey parses an ASN.1, DER-encoded, private key from |len| bytes + * at |*inp|. If |out_key| is not NULL then, on exit, a pointer to the result + * is in |*out_key|. If |*out_key| is already non-NULL on entry then the result + * is written directly into |*out_key|, otherwise a fresh |EC_KEY| is + * allocated. On successful exit, |*inp| is advanced past the DER structure. It + * returns the result or NULL on error. */ +EC_KEY *d2i_ECPrivateKey(EC_KEY **out_key, const uint8_t **inp, long len); + +/* i2d_ECParameters marshals an EC private key from |key| to an ASN.1, DER + * structure. If |outp| is not NULL then the result is written to |*outp| and + * |*outp| is advanced just past the output. It returns the number of bytes in + * the result, whether written or not, or a negative value on error. */ +int i2d_ECPrivateKey(const EC_KEY *key, uint8_t **outp); + +/* d2i_ECParameters parses an ASN.1, DER-encoded, set of EC parameters from + * |len| bytes at |*inp|. If |out_key| is not NULL then, on exit, a pointer to + * the result is in |*out_key|. If |*out_key| is already non-NULL on entry then + * the result is written directly into |*out_key|, otherwise a fresh |EC_KEY| + * is allocated. On successful exit, |*inp| is advanced past the DER structure. + * It returns the result or NULL on error. */ +EC_KEY *d2i_ECParameters(EC_KEY **out_key, const uint8_t **inp, long len); + +/* i2d_ECParameters marshals EC parameters from |key| to an ASN.1, DER + * structure. If |outp| is not NULL then the result is written to |*outp| and + * |*outp| is advanced just past the output. It returns the number of bytes in + * the result, whether written or not, or a negative value on error. */ +int i2d_ECParameters(const EC_KEY *key, uint8_t **outp); + +/* o2i_ECPublicKey parses an EC point from |len| bytes at |*inp| into + * |*out_key|. Note that this differs from the d2i format in that |*out_key| + * must be non-NULL. On successful exit, |*inp| is advanced past the DER + * structure. It returns |*out_key| or NULL on error. */ +EC_KEY *o2i_ECPublicKey(EC_KEY **out_key, const uint8_t **inp, long len); + +/* i2o_ECPublicKey marshals an EC point from |key|. If |outp| is not NULL then + * the result is written to |*outp| and |*outp| is advanced just past the + * output. It returns the number of bytes in the result, whether written or + * not, or a negative value on error. */ +int i2o_ECPublicKey(const EC_KEY *key, unsigned char **outp); + + +/* ex_data functions. + * + * These functions are wrappers. See |ex_data.h| for details. */ + +int EC_KEY_get_ex_new_index(long argl, void *argp, CRYPTO_EX_new *new_func, + CRYPTO_EX_dup *dup_func, CRYPTO_EX_free *free_func); +int EC_KEY_set_ex_data(EC_KEY *r, int idx, void *arg); +void *EC_KEY_get_ex_data(const EC_KEY *r, int idx); + + +/* ECDSA method. */ + +/* ecdsa_method_st is a structure of function pointers for implementing ECDSA. + * See engine.h. */ +struct ecdsa_method_st { + struct openssl_method_common_st common; + + void *app_data; + + int (*init)(EC_KEY *key); + int (*finish)(EC_KEY *key); + + /* size returns the maximum size of the DER encoded, ECDSA signature + * resulting from |key|. */ + size_t (*size)(const EC_KEY *key); + + /* sign matches the arguments and behaviour of |ECDSA_sign|. */ + int (*sign)(const uint8_t *digest, size_t digest_len, uint8_t *sig, + unsigned int *sig_len, EC_KEY *eckey); + + /* verify matches the arguments and behaviour of |ECDSA_verify|. */ + int (*verify)(const uint8_t *digest, size_t digest_len, const uint8_t *sig, + size_t sig_len, EC_KEY *eckey); +}; + + +#if defined(__cplusplus) +} /* extern C */ +#endif + +#endif /* OPENSSL_HEADER_EC_KEY_H */
diff --git a/crypto/ec/ec_montgomery.c b/crypto/ec/ec_montgomery.c new file mode 100644 index 0000000..ab04556 --- /dev/null +++ b/crypto/ec/ec_montgomery.c
@@ -0,0 +1,296 @@ +/* Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#include <openssl/ec.h> + +#include <openssl/bn.h> +#include <openssl/err.h> +#include <openssl/mem.h> + +#include "internal.h" + + +const EC_METHOD *EC_GFp_mont_method(void) { + static const EC_METHOD ret = {EC_FLAGS_DEFAULT_OCT, + ec_GFp_mont_group_init, + ec_GFp_mont_group_finish, + ec_GFp_mont_group_clear_finish, + ec_GFp_mont_group_copy, + ec_GFp_mont_group_set_curve, + ec_GFp_simple_group_get_curve, + ec_GFp_simple_group_get_degree, + ec_GFp_simple_group_check_discriminant, + ec_GFp_simple_point_init, + ec_GFp_simple_point_finish, + ec_GFp_simple_point_clear_finish, + ec_GFp_simple_point_copy, + ec_GFp_simple_point_set_to_infinity, + ec_GFp_simple_set_Jprojective_coordinates_GFp, + ec_GFp_simple_get_Jprojective_coordinates_GFp, + ec_GFp_simple_point_set_affine_coordinates, + ec_GFp_simple_point_get_affine_coordinates, + 0, + 0, + 0, + ec_GFp_simple_add, + ec_GFp_simple_dbl, + ec_GFp_simple_invert, + ec_GFp_simple_is_at_infinity, + ec_GFp_simple_is_on_curve, + ec_GFp_simple_cmp, + ec_GFp_simple_make_affine, + ec_GFp_simple_points_make_affine, + 0 /* mul */, + 0 /* precompute_mult */, + 0 /* have_precompute_mult */, + ec_GFp_mont_field_mul, + ec_GFp_mont_field_sqr, + 0 /* field_div */, + ec_GFp_mont_field_encode, + ec_GFp_mont_field_decode, + ec_GFp_mont_field_set_to_one}; + + return &ret; +} + +int ec_GFp_mont_group_init(EC_GROUP *group) { + int ok; + + ok = ec_GFp_simple_group_init(group); + group->field_data1 = NULL; + group->field_data2 = NULL; + return ok; +} + +void ec_GFp_mont_group_finish(EC_GROUP *group) { + if (group->field_data1 != NULL) { + BN_MONT_CTX_free(group->field_data1); + group->field_data1 = NULL; + } + if (group->field_data2 != NULL) { + BN_free(group->field_data2); + group->field_data2 = NULL; + } + ec_GFp_simple_group_finish(group); +} + +void ec_GFp_mont_group_clear_finish(EC_GROUP *group) { + if (group->field_data1 != NULL) { + BN_MONT_CTX_free(group->field_data1); + group->field_data1 = NULL; + } + if (group->field_data2 != NULL) { + BN_clear_free(group->field_data2); + group->field_data2 = NULL; + } + ec_GFp_simple_group_clear_finish(group); +} + +int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src) { + if (dest->field_data1 != NULL) { + BN_MONT_CTX_free(dest->field_data1); + dest->field_data1 = NULL; + } + if (dest->field_data2 != NULL) { + BN_clear_free(dest->field_data2); + dest->field_data2 = NULL; + } + + if (!ec_GFp_simple_group_copy(dest, src)) + return 0; + + if (src->field_data1 != NULL) { + dest->field_data1 = BN_MONT_CTX_new(); + if (dest->field_data1 == NULL) + return 0; + if (!BN_MONT_CTX_copy(dest->field_data1, src->field_data1)) + goto err; + } + if (src->field_data2 != NULL) { + dest->field_data2 = BN_dup(src->field_data2); + if (dest->field_data2 == NULL) + goto err; + } + + return 1; + +err: + if (dest->field_data1 != NULL) { + BN_MONT_CTX_free(dest->field_data1); + dest->field_data1 = NULL; + } + return 0; +} + +int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p, + const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + BN_MONT_CTX *mont = NULL; + BIGNUM *one = NULL; + int ret = 0; + + if (group->field_data1 != NULL) { + BN_MONT_CTX_free(group->field_data1); + group->field_data1 = NULL; + } + if (group->field_data2 != NULL) { + BN_free(group->field_data2); + group->field_data2 = NULL; + } + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + mont = BN_MONT_CTX_new(); + if (mont == NULL) + goto err; + if (!BN_MONT_CTX_set(mont, p, ctx)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_mont_group_set_curve, ERR_R_BN_LIB); + goto err; + } + one = BN_new(); + if (one == NULL) + goto err; + if (!BN_to_montgomery(one, BN_value_one(), mont, ctx)) + goto err; + + group->field_data1 = mont; + mont = NULL; + group->field_data2 = one; + one = NULL; + + ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx); + + if (!ret) { + BN_MONT_CTX_free(group->field_data1); + group->field_data1 = NULL; + BN_free(group->field_data2); + group->field_data2 = NULL; + } + +err: + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + if (mont != NULL) + BN_MONT_CTX_free(mont); + return ret; +} + +int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, + const BIGNUM *b, BN_CTX *ctx) { + if (group->field_data1 == NULL) { + OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_mul, EC_R_NOT_INITIALIZED); + return 0; + } + + return BN_mod_mul_montgomery(r, a, b, group->field_data1, ctx); +} + +int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, + BN_CTX *ctx) { + if (group->field_data1 == NULL) { + OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_sqr, EC_R_NOT_INITIALIZED); + return 0; + } + + return BN_mod_mul_montgomery(r, a, a, group->field_data1, ctx); +} + +int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, + BN_CTX *ctx) { + if (group->field_data1 == NULL) { + OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_encode, EC_R_NOT_INITIALIZED); + return 0; + } + + return BN_to_montgomery(r, a, (BN_MONT_CTX *)group->field_data1, ctx); +} + +int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, + BN_CTX *ctx) { + if (group->field_data1 == NULL) { + OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_decode, EC_R_NOT_INITIALIZED); + return 0; + } + + return BN_from_montgomery(r, a, group->field_data1, ctx); +} + +int ec_GFp_mont_field_set_to_one(const EC_GROUP *group, BIGNUM *r, + BN_CTX *ctx) { + if (group->field_data2 == NULL) { + OPENSSL_PUT_ERROR(EC, ec_GFp_mont_field_set_to_one, EC_R_NOT_INITIALIZED); + return 0; + } + + if (!BN_copy(r, group->field_data2)) + return 0; + return 1; +}
diff --git a/crypto/ec/example_mul.c b/crypto/ec/example_mul.c new file mode 100644 index 0000000..1e83d61 --- /dev/null +++ b/crypto/ec/example_mul.c
@@ -0,0 +1,130 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#include <stdio.h> + +#include <openssl/bn.h> +#include <openssl/ec.h> +#include <openssl/obj.h> + + +int example_EC_POINT_mul() { + /* This example ensures that 10×∞ + G = G, in P-256. */ + EC_GROUP *group = NULL; + EC_POINT *p = NULL, *result = NULL; + BIGNUM *n = NULL; + int ret = 0; + const EC_POINT *generator; + + group = EC_GROUP_new_by_curve_name(NID_X9_62_prime256v1); + p = EC_POINT_new(group); + result = EC_POINT_new(group); + n = BN_new(); + + if (p == NULL || + result == NULL || + group == NULL || + n == NULL || + !EC_POINT_set_to_infinity(group, p) || + !BN_set_word(n, 10)) { + goto err; + } + + /* First check that 10×∞ = ∞. */ + if (!EC_POINT_mul(group, result, NULL, p, n, NULL) || + !EC_POINT_is_at_infinity(group, result)) { + goto err; + } + + generator = EC_GROUP_get0_generator(group); + + /* Now check that 10×∞ + G = G. */ + if (!EC_POINT_mul(group, result, BN_value_one(), p, n, NULL) || + EC_POINT_cmp(group, result, generator, NULL) != 0) { + goto err; + } + + ret = 1; + +err: + BN_free(n); + EC_POINT_free(result); + EC_POINT_free(p); + EC_GROUP_free(group); + + return ret; +} + +int main() { + if (!example_EC_POINT_mul()) { + fprintf(stderr, "failed\n"); + return 1; + } + + printf("PASS\n"); + return 0; +}
diff --git a/crypto/ec/internal.h b/crypto/ec/internal.h new file mode 100644 index 0000000..dc79186 --- /dev/null +++ b/crypto/ec/internal.h
@@ -0,0 +1,357 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#ifndef OPENSSL_HEADER_EC_INTERNAL_H +#define OPENSSL_HEADER_EC_INTERNAL_H + +#include <openssl/base.h> + +#include <openssl/bn.h> +#include <openssl/ex_data.h> + +#if defined(__cplusplus) +extern "C" { +#endif + + +/* Use default functions for poin2oct, oct2point and compressed coordinates */ +#define EC_FLAGS_DEFAULT_OCT 0x1 + +typedef struct ec_method_st EC_METHOD; + +struct ec_method_st { + /* Various method flags */ + int flags; + + /* used by EC_GROUP_new, EC_GROUP_free, EC_GROUP_clear_free, EC_GROUP_copy: */ + int (*group_init)(EC_GROUP *); + void (*group_finish)(EC_GROUP *); + void (*group_clear_finish)(EC_GROUP *); + int (*group_copy)(EC_GROUP *, const EC_GROUP *); + + /* used by EC_GROUP_set_curve_GFp, EC_GROUP_get_curve_GFp, */ + /* EC_GROUP_set_curve_GF2m, and EC_GROUP_get_curve_GF2m: */ + int (*group_set_curve)(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, + const BIGNUM *b, BN_CTX *); + int (*group_get_curve)(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, + BN_CTX *); + + /* used by EC_GROUP_get_degree: */ + int (*group_get_degree)(const EC_GROUP *); + + /* used by EC_GROUP_check: */ + int (*group_check_discriminant)(const EC_GROUP *, BN_CTX *); + + /* used by EC_POINT_new, EC_POINT_free, EC_POINT_clear_free, EC_POINT_copy: */ + int (*point_init)(EC_POINT *); + void (*point_finish)(EC_POINT *); + void (*point_clear_finish)(EC_POINT *); + int (*point_copy)(EC_POINT *, const EC_POINT *); + + /* used by EC_POINT_set_to_infinity, + * EC_POINT_set_Jprojective_coordinates_GFp, + * EC_POINT_get_Jprojective_coordinates_GFp, + * EC_POINT_set_affine_coordinates_GFp, ..._GF2m, + * EC_POINT_get_affine_coordinates_GFp, ..._GF2m, + * EC_POINT_set_compressed_coordinates_GFp, ..._GF2m: + */ + int (*point_set_to_infinity)(const EC_GROUP *, EC_POINT *); + int (*point_set_Jprojective_coordinates_GFp)(const EC_GROUP *, EC_POINT *, + const BIGNUM *x, const BIGNUM *y, + const BIGNUM *z, BN_CTX *); + int (*point_get_Jprojective_coordinates_GFp)(const EC_GROUP *, + const EC_POINT *, BIGNUM *x, + BIGNUM *y, BIGNUM *z, BN_CTX *); + int (*point_set_affine_coordinates)(const EC_GROUP *, EC_POINT *, + const BIGNUM *x, const BIGNUM *y, + BN_CTX *); + int (*point_get_affine_coordinates)(const EC_GROUP *, const EC_POINT *, + BIGNUM *x, BIGNUM *y, BN_CTX *); + int (*point_set_compressed_coordinates)(const EC_GROUP *, EC_POINT *, + const BIGNUM *x, int y_bit, BN_CTX *); + + /* used by EC_POINT_point2oct, EC_POINT_oct2point: */ + size_t (*point2oct)(const EC_GROUP *, const EC_POINT *, + point_conversion_form_t form, unsigned char *buf, + size_t len, BN_CTX *); + int (*oct2point)(const EC_GROUP *, EC_POINT *, const unsigned char *buf, + size_t len, BN_CTX *); + + /* used by EC_POINT_add, EC_POINT_dbl, ECP_POINT_invert: */ + int (*add)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, + const EC_POINT *b, BN_CTX *); + int (*dbl)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *); + int (*invert)(const EC_GROUP *, EC_POINT *, BN_CTX *); + + /* used by EC_POINT_is_at_infinity, EC_POINT_is_on_curve, EC_POINT_cmp: */ + int (*is_at_infinity)(const EC_GROUP *, const EC_POINT *); + int (*is_on_curve)(const EC_GROUP *, const EC_POINT *, BN_CTX *); + int (*point_cmp)(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, + BN_CTX *); + + /* used by EC_POINT_make_affine, EC_POINTs_make_affine: */ + int (*make_affine)(const EC_GROUP *, EC_POINT *, BN_CTX *); + int (*points_make_affine)(const EC_GROUP *, size_t num, EC_POINT * [], + BN_CTX *); + + /* used by EC_POINTs_mul, EC_POINT_mul, EC_POINT_precompute_mult, + * EC_POINT_have_precompute_mult + * (default implementations are used if the 'mul' pointer is 0): */ + int (*mul)(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, + size_t num, const EC_POINT *points[], const BIGNUM *scalars[], + BN_CTX *); + int (*precompute_mult)(EC_GROUP *group, BN_CTX *); + int (*have_precompute_mult)(const EC_GROUP *group); + + + /* internal functions */ + + /* 'field_mul', 'field_sqr', and 'field_div' can be used by 'add' and 'dbl' + * so that the same implementations of point operations can be used with + * different optimized implementations of expensive field operations: */ + int (*field_mul)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + const BIGNUM *b, BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); + int (*field_div)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + const BIGNUM *b, BN_CTX *); + + int (*field_encode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + BN_CTX *); /* e.g. to Montgomery */ + int (*field_decode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + BN_CTX *); /* e.g. from Montgomery */ + int (*field_set_to_one)(const EC_GROUP *, BIGNUM *r, BN_CTX *); +} /* EC_METHOD */; + +const EC_METHOD* EC_GFp_mont_method(); + +struct ec_pre_comp_st; +void ec_pre_comp_free(struct ec_pre_comp_st *pre_comp); +void *ec_pre_comp_dup(struct ec_pre_comp_st *pre_comp); + +struct ec_group_st { + const EC_METHOD *meth; + + EC_POINT *generator; /* optional */ + BIGNUM order, cofactor; + + int curve_name; /* optional NID for named curve */ + point_conversion_form_t asn1_form; + + struct ec_pre_comp_st *pre_comp; + + /* The following members are handled by the method functions, + * even if they appear generic */ + + BIGNUM field; /* Field specification. + * For curves over GF(p), this is the modulus; + * for curves over GF(2^m), this is the + * irreducible polynomial defining the field. */ + + int poly[6]; /* Field specification for curves over GF(2^m). + * The irreducible f(t) is then of the form: + * t^poly[0] + t^poly[1] + ... + t^poly[k] + * where m = poly[0] > poly[1] > ... > poly[k] = 0. + * The array is terminated with poly[k+1]=-1. + * All elliptic curve irreducibles have at most 5 + * non-zero terms. */ + + BIGNUM a, b; /* Curve coefficients. + * (Here the assumption is that BIGNUMs can be used + * or abused for all kinds of fields, not just GF(p).) + * For characteristic > 3, the curve is defined + * by a Weierstrass equation of the form + * y^2 = x^3 + a*x + b. + * For characteristic 2, the curve is defined by + * an equation of the form + * y^2 + x*y = x^3 + a*x^2 + b. */ + + int a_is_minus3; /* enable optimized point arithmetics for special case */ + + void *field_data1; /* method-specific (e.g., Montgomery structure) */ + void *field_data2; /* method-specific */ + int (*field_mod_func)(BIGNUM *, const BIGNUM *, const BIGNUM *, + BN_CTX *); /* method-specific */ +} /* EC_GROUP */; + +struct ec_point_st { + const EC_METHOD *meth; + + /* All members except 'meth' are handled by the method functions, + * even if they appear generic */ + + BIGNUM X; + BIGNUM Y; + BIGNUM Z; /* Jacobian projective coordinates: + * (X, Y, Z) represents (X/Z^2, Y/Z^3) if Z != 0 */ + int Z_is_one; /* enable optimized point arithmetics for special case */ +} /* EC_POINT */; + +EC_GROUP *ec_group_new(const EC_METHOD *meth); + +int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, + size_t num, const EC_POINT *points[], const BIGNUM *scalars[], + BN_CTX *); +int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *); +int ec_wNAF_have_precompute_mult(const EC_GROUP *group); + +/* method functions in simple.c */ +int ec_GFp_simple_group_init(EC_GROUP *); +void ec_GFp_simple_group_finish(EC_GROUP *); +void ec_GFp_simple_group_clear_finish(EC_GROUP *); +int ec_GFp_simple_group_copy(EC_GROUP *, const EC_GROUP *); +int ec_GFp_simple_group_set_curve(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, + const BIGNUM *b, BN_CTX *); +int ec_GFp_simple_group_get_curve(const EC_GROUP *, BIGNUM *p, BIGNUM *a, + BIGNUM *b, BN_CTX *); +int ec_GFp_simple_group_get_degree(const EC_GROUP *); +int ec_GFp_simple_group_check_discriminant(const EC_GROUP *, BN_CTX *); +int ec_GFp_simple_point_init(EC_POINT *); +void ec_GFp_simple_point_finish(EC_POINT *); +void ec_GFp_simple_point_clear_finish(EC_POINT *); +int ec_GFp_simple_point_copy(EC_POINT *, const EC_POINT *); +int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *, EC_POINT *); +int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *, EC_POINT *, + const BIGNUM *x, + const BIGNUM *y, + const BIGNUM *z, BN_CTX *); +int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *, + const EC_POINT *, BIGNUM *x, + BIGNUM *y, BIGNUM *z, + BN_CTX *); +int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *, EC_POINT *, + const BIGNUM *x, const BIGNUM *y, + BN_CTX *); +int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *, + const EC_POINT *, BIGNUM *x, + BIGNUM *y, BN_CTX *); +int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *, EC_POINT *, + const BIGNUM *x, int y_bit, + BN_CTX *); +int ec_GFp_simple_add(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, + const EC_POINT *b, BN_CTX *); +int ec_GFp_simple_dbl(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, + BN_CTX *); +int ec_GFp_simple_invert(const EC_GROUP *, EC_POINT *, BN_CTX *); +int ec_GFp_simple_is_at_infinity(const EC_GROUP *, const EC_POINT *); +int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *); +int ec_GFp_simple_cmp(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, + BN_CTX *); +int ec_GFp_simple_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *); +int ec_GFp_simple_points_make_affine(const EC_GROUP *, size_t num, + EC_POINT * [], BN_CTX *); +int ec_GFp_simple_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + const BIGNUM *b, BN_CTX *); +int ec_GFp_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + BN_CTX *); + +/* method functions in montgomery.c */ +int ec_GFp_mont_group_init(EC_GROUP *); +int ec_GFp_mont_group_set_curve(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, + const BIGNUM *b, BN_CTX *); +void ec_GFp_mont_group_finish(EC_GROUP *); +void ec_GFp_mont_group_clear_finish(EC_GROUP *); +int ec_GFp_mont_group_copy(EC_GROUP *, const EC_GROUP *); +int ec_GFp_mont_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + const BIGNUM *b, BN_CTX *); +int ec_GFp_mont_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + BN_CTX *); +int ec_GFp_mont_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + BN_CTX *); +int ec_GFp_mont_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, + BN_CTX *); +int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *); + +int ec_point_set_Jprojective_coordinates_GFp(const EC_GROUP *group, + EC_POINT *point, const BIGNUM *x, + const BIGNUM *y, const BIGNUM *z, + BN_CTX *ctx); + +struct ec_key_st { + int version; + + EC_GROUP *group; + + EC_POINT *pub_key; + BIGNUM *priv_key; + + unsigned int enc_flag; + point_conversion_form_t conv_form; + + int references; + int flags; + + ECDSA_METHOD *ecdsa_meth; + + CRYPTO_EX_DATA ex_data; +} /* EC_KEY */; + + +#if defined(__cplusplus) +} /* extern C */ +#endif + +#endif /* OPENSSL_HEADER_EC_INTERNAL_H */
diff --git a/crypto/ec/oct.c b/crypto/ec/oct.c new file mode 100644 index 0000000..1c5ea14 --- /dev/null +++ b/crypto/ec/oct.c
@@ -0,0 +1,495 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#include <openssl/ec.h> + +#include <openssl/bn.h> +#include <openssl/err.h> + +#include "internal.h" + + +static size_t ec_GFp_simple_point2oct(const EC_GROUP *group, + const EC_POINT *point, + point_conversion_form_t form, + uint8_t *buf, size_t len, BN_CTX *ctx) { + size_t ret; + BN_CTX *new_ctx = NULL; + int used_ctx = 0; + BIGNUM *x, *y; + size_t field_len, i, skip; + + if ((form != POINT_CONVERSION_COMPRESSED) && + (form != POINT_CONVERSION_UNCOMPRESSED) && + (form != POINT_CONVERSION_HYBRID)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_INVALID_FORM); + goto err; + } + + if (EC_POINT_is_at_infinity(group, point)) { + /* encodes to a single 0 octet */ + if (buf != NULL) { + if (len < 1) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL); + return 0; + } + buf[0] = 0; + } + return 1; + } + + + /* ret := required output buffer length */ + field_len = BN_num_bytes(&group->field); + ret = + (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; + + /* if 'buf' is NULL, just return required length */ + if (buf != NULL) { + if (len < ret) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL); + goto err; + } + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + used_ctx = 1; + x = BN_CTX_get(ctx); + y = BN_CTX_get(ctx); + if (y == NULL) + goto err; + + if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) + goto err; + + if ((form == POINT_CONVERSION_COMPRESSED || + form == POINT_CONVERSION_HYBRID) && + BN_is_odd(y)) + buf[0] = form + 1; + else + buf[0] = form; + + i = 1; + + skip = field_len - BN_num_bytes(x); + if (skip > field_len) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); + goto err; + } + while (skip > 0) { + buf[i++] = 0; + skip--; + } + skip = BN_bn2bin(x, buf + i); + i += skip; + if (i != 1 + field_len) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); + goto err; + } + + if (form == POINT_CONVERSION_UNCOMPRESSED || + form == POINT_CONVERSION_HYBRID) { + skip = field_len - BN_num_bytes(y); + if (skip > field_len) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); + goto err; + } + while (skip > 0) { + buf[i++] = 0; + skip--; + } + skip = BN_bn2bin(y, buf + i); + i += skip; + } + + if (i != ret) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR); + goto err; + } + } + + if (used_ctx) + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; + +err: + if (used_ctx) + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return 0; +} + + +static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, + const uint8_t *buf, size_t len, + BN_CTX *ctx) { + point_conversion_form_t form; + int y_bit; + BN_CTX *new_ctx = NULL; + BIGNUM *x, *y; + size_t field_len, enc_len; + int ret = 0; + + if (len == 0) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_BUFFER_TOO_SMALL); + return 0; + } + form = buf[0]; + y_bit = form & 1; + form = form & ~1U; + if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) && + (form != POINT_CONVERSION_UNCOMPRESSED) && + (form != POINT_CONVERSION_HYBRID)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); + return 0; + } + if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); + return 0; + } + + if (form == 0) { + if (len != 1) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); + return 0; + } + + return EC_POINT_set_to_infinity(group, point); + } + + field_len = BN_num_bytes(&group->field); + enc_len = + (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; + + if (len != enc_len) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); + return 0; + } + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + x = BN_CTX_get(ctx); + y = BN_CTX_get(ctx); + if (y == NULL) + goto err; + + if (!BN_bin2bn(buf + 1, field_len, x)) + goto err; + if (BN_ucmp(x, &group->field) >= 0) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); + goto err; + } + + if (form == POINT_CONVERSION_COMPRESSED) { + if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) + goto err; + } else { + if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) + goto err; + if (BN_ucmp(y, &group->field) >= 0) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); + goto err; + } + if (form == POINT_CONVERSION_HYBRID) { + if (y_bit != BN_is_odd(y)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING); + goto err; + } + } + + if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) + goto err; + } + + if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */ + { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_POINT_IS_NOT_ON_CURVE); + goto err; + } + + ret = 1; + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point, + const uint8_t *buf, size_t len, BN_CTX *ctx) { + if (group->meth->oct2point == 0 && + !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) { + OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) { + return ec_GFp_simple_oct2point(group, point, buf, len, ctx); + } + + return group->meth->oct2point(group, point, buf, len, ctx); +} + +size_t EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point, + point_conversion_form_t form, uint8_t *buf, + size_t len, BN_CTX *ctx) { + if (group->meth->point2oct == 0 && + !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) { + OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) { + return ec_GFp_simple_point2oct(group, point, form, buf, len, ctx); + } + + return group->meth->point2oct(group, point, form, buf, len, ctx); +} + +int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, + EC_POINT *point, const BIGNUM *x_, + int y_bit, BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + BIGNUM *tmp1, *tmp2, *x, *y; + int ret = 0; + + ERR_clear_error(); + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) { + return 0; + } + } + + y_bit = (y_bit != 0); + + BN_CTX_start(ctx); + tmp1 = BN_CTX_get(ctx); + tmp2 = BN_CTX_get(ctx); + x = BN_CTX_get(ctx); + y = BN_CTX_get(ctx); + if (y == NULL) { + goto err; + } + + /* Recover y. We have a Weierstrass equation + * y^2 = x^3 + a*x + b, + * so y is one of the square roots of x^3 + a*x + b. */ + + /* tmp1 := x^3 */ + if (!BN_nnmod(x, x_, &group->field, ctx)) { + goto err; + } + + if (group->meth->field_decode == 0) { + /* field_{sqr,mul} work on standard representation */ + if (!group->meth->field_sqr(group, tmp2, x_, ctx) || + !group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) { + goto err; + } + } else { + if (!BN_mod_sqr(tmp2, x_, &group->field, ctx) || + !BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) { + goto err; + } + } + + /* tmp1 := tmp1 + a*x */ + if (group->a_is_minus3) { + if (!BN_mod_lshift1_quick(tmp2, x, &group->field) || + !BN_mod_add_quick(tmp2, tmp2, x, &group->field) || + !BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) { + goto err; + } + } else { + if (group->meth->field_decode) { + if (!group->meth->field_decode(group, tmp2, &group->a, ctx) || + !BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) { + goto err; + } + } else { + /* field_mul works on standard representation */ + if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) { + goto err; + } + } + + if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) { + goto err; + } + } + + /* tmp1 := tmp1 + b */ + if (group->meth->field_decode) { + if (!group->meth->field_decode(group, tmp2, &group->b, ctx) || + !BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) { + goto err; + } + } else { + if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) { + goto err; + } + } + + if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { + unsigned long err = ERR_peek_last_error(); + + if (ERR_GET_LIB(err) == ERR_LIB_BN && + ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { + ERR_clear_error(); + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, EC_R_INVALID_COMPRESSED_POINT); + } else { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, ERR_R_BN_LIB); + } + goto err; + } + + if (y_bit != BN_is_odd(y)) { + if (BN_is_zero(y)) { + int kron; + + kron = BN_kronecker(x, &group->field, ctx); + if (kron == -2) { + goto err; + } + + if (kron == 1) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, + EC_R_INVALID_COMPRESSION_BIT); + } else { + /* BN_mod_sqrt() should have cought this error (not a square) */ + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, + EC_R_INVALID_COMPRESSED_POINT); + } + goto err; + } + if (!BN_usub(y, &group->field, y)) { + goto err; + } + } + if (y_bit != BN_is_odd(y)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, + ERR_R_INTERNAL_ERROR); + goto err; + } + + if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) + goto err; + + ret = 1; + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, + EC_POINT *point, const BIGNUM *x, + int y_bit, BN_CTX *ctx) { + if (group->meth->point_set_compressed_coordinates == 0 && + !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) { + OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp, + ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED); + return 0; + } + if (group->meth != point->meth) { + OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp, + EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) { + return ec_GFp_simple_set_compressed_coordinates(group, point, x, y_bit, + ctx); + } + return group->meth->point_set_compressed_coordinates(group, point, x, y_bit, + ctx); +}
diff --git a/crypto/ec/simple.c b/crypto/ec/simple.c new file mode 100644 index 0000000..144d056 --- /dev/null +++ b/crypto/ec/simple.c
@@ -0,0 +1,1371 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#include <openssl/ec.h> + +#include <openssl/bn.h> +#include <openssl/err.h> +#include <openssl/mem.h> + +#include "internal.h" + + +const EC_METHOD *EC_GFp_simple_method(void) { + static const EC_METHOD ret = {EC_FLAGS_DEFAULT_OCT, + ec_GFp_simple_group_init, + ec_GFp_simple_group_finish, + ec_GFp_simple_group_clear_finish, + ec_GFp_simple_group_copy, + ec_GFp_simple_group_set_curve, + ec_GFp_simple_group_get_curve, + ec_GFp_simple_group_get_degree, + ec_GFp_simple_group_check_discriminant, + ec_GFp_simple_point_init, + ec_GFp_simple_point_finish, + ec_GFp_simple_point_clear_finish, + ec_GFp_simple_point_copy, + ec_GFp_simple_point_set_to_infinity, + ec_GFp_simple_set_Jprojective_coordinates_GFp, + ec_GFp_simple_get_Jprojective_coordinates_GFp, + ec_GFp_simple_point_set_affine_coordinates, + ec_GFp_simple_point_get_affine_coordinates, + 0, + 0, + 0, + ec_GFp_simple_add, + ec_GFp_simple_dbl, + ec_GFp_simple_invert, + ec_GFp_simple_is_at_infinity, + ec_GFp_simple_is_on_curve, + ec_GFp_simple_cmp, + ec_GFp_simple_make_affine, + ec_GFp_simple_points_make_affine, + 0 /* mul */, + 0 /* precompute_mult */, + 0 /* have_precompute_mult */, + ec_GFp_simple_field_mul, + ec_GFp_simple_field_sqr, + 0 /* field_div */, + 0 /* field_encode */, + 0 /* field_decode */, + 0 /* field_set_to_one */}; + + return &ret; +} + + +/* Most method functions in this file are designed to work with non-trivial + * representations of field elements if necessary (see ecp_mont.c): while + * standard modular addition and subtraction are used, the field_mul and + * field_sqr methods will be used for multiplication, and field_encode and + * field_decode (if defined) will be used for converting between + * representations. + + * Functions ec_GFp_simple_points_make_affine() and + * ec_GFp_simple_point_get_affine_coordinates() specifically assume that if a + * non-trivial representation is used, it is a Montgomery representation (i.e. + * 'encoding' means multiplying by some factor R). */ + +int ec_GFp_simple_group_init(EC_GROUP *group) { + BN_init(&group->field); + BN_init(&group->a); + BN_init(&group->b); + group->a_is_minus3 = 0; + return 1; +} + +void ec_GFp_simple_group_finish(EC_GROUP *group) { + BN_free(&group->field); + BN_free(&group->a); + BN_free(&group->b); +} + +void ec_GFp_simple_group_clear_finish(EC_GROUP *group) { + BN_clear_free(&group->field); + BN_clear_free(&group->a); + BN_clear_free(&group->b); +} + +int ec_GFp_simple_group_copy(EC_GROUP *dest, const EC_GROUP *src) { + if (!BN_copy(&dest->field, &src->field) || + !BN_copy(&dest->a, &src->a) || + !BN_copy(&dest->b, &src->b)) { + return 0; + } + + dest->a_is_minus3 = src->a_is_minus3; + return 1; +} + +int ec_GFp_simple_group_set_curve(EC_GROUP *group, const BIGNUM *p, + const BIGNUM *a, const BIGNUM *b, + BN_CTX *ctx) { + int ret = 0; + BN_CTX *new_ctx = NULL; + BIGNUM *tmp_a; + + /* p must be a prime > 3 */ + if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_group_set_curve, EC_R_INVALID_FIELD); + return 0; + } + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + tmp_a = BN_CTX_get(ctx); + if (tmp_a == NULL) + goto err; + + /* group->field */ + if (!BN_copy(&group->field, p)) + goto err; + BN_set_negative(&group->field, 0); + + /* group->a */ + if (!BN_nnmod(tmp_a, a, p, ctx)) + goto err; + if (group->meth->field_encode) { + if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) + goto err; + } else if (!BN_copy(&group->a, tmp_a)) + goto err; + + /* group->b */ + if (!BN_nnmod(&group->b, b, p, ctx)) + goto err; + if (group->meth->field_encode) + if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) + goto err; + + /* group->a_is_minus3 */ + if (!BN_add_word(tmp_a, 3)) + goto err; + group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); + + ret = 1; + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, + BIGNUM *b, BN_CTX *ctx) { + int ret = 0; + BN_CTX *new_ctx = NULL; + + if (p != NULL) { + if (!BN_copy(p, &group->field)) + return 0; + } + + if (a != NULL || b != NULL) { + if (group->meth->field_decode) { + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + if (a != NULL) { + if (!group->meth->field_decode(group, a, &group->a, ctx)) + goto err; + } + if (b != NULL) { + if (!group->meth->field_decode(group, b, &group->b, ctx)) + goto err; + } + } else { + if (a != NULL) { + if (!BN_copy(a, &group->a)) + goto err; + } + if (b != NULL) { + if (!BN_copy(b, &group->b)) + goto err; + } + } + } + + ret = 1; + +err: + if (new_ctx) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_group_get_degree(const EC_GROUP *group) { + return BN_num_bits(&group->field); +} + +int ec_GFp_simple_group_check_discriminant(const EC_GROUP *group, BN_CTX *ctx) { + int ret = 0; + BIGNUM *a, *b, *order, *tmp_1, *tmp_2; + const BIGNUM *p = &group->field; + BN_CTX *new_ctx = NULL; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_group_check_discriminant, + ERR_R_MALLOC_FAILURE); + goto err; + } + } + BN_CTX_start(ctx); + a = BN_CTX_get(ctx); + b = BN_CTX_get(ctx); + tmp_1 = BN_CTX_get(ctx); + tmp_2 = BN_CTX_get(ctx); + order = BN_CTX_get(ctx); + if (order == NULL) + goto err; + + if (group->meth->field_decode) { + if (!group->meth->field_decode(group, a, &group->a, ctx)) + goto err; + if (!group->meth->field_decode(group, b, &group->b, ctx)) + goto err; + } else { + if (!BN_copy(a, &group->a)) + goto err; + if (!BN_copy(b, &group->b)) + goto err; + } + + /* check the discriminant: + * y^2 = x^3 + a*x + b is an elliptic curve <=> 4*a^3 + 27*b^2 != 0 (mod p) + * 0 =< a, b < p */ + if (BN_is_zero(a)) { + if (BN_is_zero(b)) + goto err; + } else if (!BN_is_zero(b)) { + if (!BN_mod_sqr(tmp_1, a, p, ctx)) + goto err; + if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) + goto err; + if (!BN_lshift(tmp_1, tmp_2, 2)) + goto err; + /* tmp_1 = 4*a^3 */ + + if (!BN_mod_sqr(tmp_2, b, p, ctx)) + goto err; + if (!BN_mul_word(tmp_2, 27)) + goto err; + /* tmp_2 = 27*b^2 */ + + if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) + goto err; + if (BN_is_zero(a)) + goto err; + } + ret = 1; + +err: + if (ctx != NULL) + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_point_init(EC_POINT *point) { + BN_init(&point->X); + BN_init(&point->Y); + BN_init(&point->Z); + point->Z_is_one = 0; + + return 1; +} + +void ec_GFp_simple_point_finish(EC_POINT *point) { + BN_free(&point->X); + BN_free(&point->Y); + BN_free(&point->Z); +} + +void ec_GFp_simple_point_clear_finish(EC_POINT *point) { + BN_clear_free(&point->X); + BN_clear_free(&point->Y); + BN_clear_free(&point->Z); + point->Z_is_one = 0; +} + +int ec_GFp_simple_point_copy(EC_POINT *dest, const EC_POINT *src) { + if (!BN_copy(&dest->X, &src->X)) + return 0; + if (!BN_copy(&dest->Y, &src->Y)) + return 0; + if (!BN_copy(&dest->Z, &src->Z)) + return 0; + dest->Z_is_one = src->Z_is_one; + + return 1; +} + +int ec_GFp_simple_point_set_to_infinity(const EC_GROUP *group, + EC_POINT *point) { + point->Z_is_one = 0; + BN_zero(&point->Z); + return 1; +} + +int ec_GFp_simple_set_Jprojective_coordinates_GFp( + const EC_GROUP *group, EC_POINT *point, const BIGNUM *x, const BIGNUM *y, + const BIGNUM *z, BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + int ret = 0; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + if (x != NULL) { + if (!BN_nnmod(&point->X, x, &group->field, ctx)) + goto err; + if (group->meth->field_encode) { + if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) + goto err; + } + } + + if (y != NULL) { + if (!BN_nnmod(&point->Y, y, &group->field, ctx)) + goto err; + if (group->meth->field_encode) { + if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) + goto err; + } + } + + if (z != NULL) { + int Z_is_one; + + if (!BN_nnmod(&point->Z, z, &group->field, ctx)) + goto err; + Z_is_one = BN_is_one(&point->Z); + if (group->meth->field_encode) { + if (Z_is_one && (group->meth->field_set_to_one != 0)) { + if (!group->meth->field_set_to_one(group, &point->Z, ctx)) + goto err; + } else { + if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) + goto err; + } + } + point->Z_is_one = Z_is_one; + } + + ret = 1; + +err: + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP *group, + const EC_POINT *point, + BIGNUM *x, BIGNUM *y, + BIGNUM *z, BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + int ret = 0; + + if (group->meth->field_decode != 0) { + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + if (x != NULL) { + if (!group->meth->field_decode(group, x, &point->X, ctx)) + goto err; + } + if (y != NULL) { + if (!group->meth->field_decode(group, y, &point->Y, ctx)) + goto err; + } + if (z != NULL) { + if (!group->meth->field_decode(group, z, &point->Z, ctx)) + goto err; + } + } else { + if (x != NULL) { + if (!BN_copy(x, &point->X)) + goto err; + } + if (y != NULL) { + if (!BN_copy(y, &point->Y)) + goto err; + } + if (z != NULL) { + if (!BN_copy(z, &point->Z)) + goto err; + } + } + + ret = 1; + +err: + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP *group, + EC_POINT *point, const BIGNUM *x, + const BIGNUM *y, BN_CTX *ctx) { + if (x == NULL || y == NULL) { + /* unlike for projective coordinates, we do not tolerate this */ + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point_set_affine_coordinates, + ERR_R_PASSED_NULL_PARAMETER); + return 0; + } + + return ec_point_set_Jprojective_coordinates_GFp(group, point, x, y, + BN_value_one(), ctx); +} + +int ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP *group, + const EC_POINT *point, BIGNUM *x, + BIGNUM *y, BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + BIGNUM *Z, *Z_1, *Z_2, *Z_3; + const BIGNUM *Z_; + int ret = 0; + + if (EC_POINT_is_at_infinity(group, point)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point_get_affine_coordinates, + EC_R_POINT_AT_INFINITY); + return 0; + } + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + Z = BN_CTX_get(ctx); + Z_1 = BN_CTX_get(ctx); + Z_2 = BN_CTX_get(ctx); + Z_3 = BN_CTX_get(ctx); + if (Z_3 == NULL) + goto err; + + /* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ + + if (group->meth->field_decode) { + if (!group->meth->field_decode(group, Z, &point->Z, ctx)) + goto err; + Z_ = Z; + } else { + Z_ = &point->Z; + } + + if (BN_is_one(Z_)) { + if (group->meth->field_decode) { + if (x != NULL) { + if (!group->meth->field_decode(group, x, &point->X, ctx)) + goto err; + } + if (y != NULL) { + if (!group->meth->field_decode(group, y, &point->Y, ctx)) + goto err; + } + } else { + if (x != NULL) { + if (!BN_copy(x, &point->X)) + goto err; + } + if (y != NULL) { + if (!BN_copy(y, &point->Y)) + goto err; + } + } + } else { + if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point_get_affine_coordinates, + ERR_R_BN_LIB); + goto err; + } + + if (group->meth->field_encode == 0) { + /* field_sqr works on standard representation */ + if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) + goto err; + } else { + if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) + goto err; + } + + if (x != NULL) { + /* in the Montgomery case, field_mul will cancel out Montgomery factor in + * X: */ + if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) + goto err; + } + + if (y != NULL) { + if (group->meth->field_encode == 0) { + /* field_mul works on standard representation */ + if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) + goto err; + } else { + if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) + goto err; + } + + /* in the Montgomery case, field_mul will cancel out Montgomery factor in + * Y: */ + if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) + goto err; + } + } + + ret = 1; + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, + const EC_POINT *b, BN_CTX *ctx) { + int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, + BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); + const BIGNUM *p; + BN_CTX *new_ctx = NULL; + BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; + int ret = 0; + + if (a == b) + return EC_POINT_dbl(group, r, a, ctx); + if (EC_POINT_is_at_infinity(group, a)) + return EC_POINT_copy(r, b); + if (EC_POINT_is_at_infinity(group, b)) + return EC_POINT_copy(r, a); + + field_mul = group->meth->field_mul; + field_sqr = group->meth->field_sqr; + p = &group->field; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + n0 = BN_CTX_get(ctx); + n1 = BN_CTX_get(ctx); + n2 = BN_CTX_get(ctx); + n3 = BN_CTX_get(ctx); + n4 = BN_CTX_get(ctx); + n5 = BN_CTX_get(ctx); + n6 = BN_CTX_get(ctx); + if (n6 == NULL) + goto end; + + /* Note that in this function we must not read components of 'a' or 'b' + * once we have written the corresponding components of 'r'. + * ('r' might be one of 'a' or 'b'.) + */ + + /* n1, n2 */ + if (b->Z_is_one) { + if (!BN_copy(n1, &a->X)) + goto end; + if (!BN_copy(n2, &a->Y)) + goto end; + /* n1 = X_a */ + /* n2 = Y_a */ + } else { + if (!field_sqr(group, n0, &b->Z, ctx)) + goto end; + if (!field_mul(group, n1, &a->X, n0, ctx)) + goto end; + /* n1 = X_a * Z_b^2 */ + + if (!field_mul(group, n0, n0, &b->Z, ctx)) + goto end; + if (!field_mul(group, n2, &a->Y, n0, ctx)) + goto end; + /* n2 = Y_a * Z_b^3 */ + } + + /* n3, n4 */ + if (a->Z_is_one) { + if (!BN_copy(n3, &b->X)) + goto end; + if (!BN_copy(n4, &b->Y)) + goto end; + /* n3 = X_b */ + /* n4 = Y_b */ + } else { + if (!field_sqr(group, n0, &a->Z, ctx)) + goto end; + if (!field_mul(group, n3, &b->X, n0, ctx)) + goto end; + /* n3 = X_b * Z_a^2 */ + + if (!field_mul(group, n0, n0, &a->Z, ctx)) + goto end; + if (!field_mul(group, n4, &b->Y, n0, ctx)) + goto end; + /* n4 = Y_b * Z_a^3 */ + } + + /* n5, n6 */ + if (!BN_mod_sub_quick(n5, n1, n3, p)) + goto end; + if (!BN_mod_sub_quick(n6, n2, n4, p)) + goto end; + /* n5 = n1 - n3 */ + /* n6 = n2 - n4 */ + + if (BN_is_zero(n5)) { + if (BN_is_zero(n6)) { + /* a is the same point as b */ + BN_CTX_end(ctx); + ret = EC_POINT_dbl(group, r, a, ctx); + ctx = NULL; + goto end; + } else { + /* a is the inverse of b */ + BN_zero(&r->Z); + r->Z_is_one = 0; + ret = 1; + goto end; + } + } + + /* 'n7', 'n8' */ + if (!BN_mod_add_quick(n1, n1, n3, p)) + goto end; + if (!BN_mod_add_quick(n2, n2, n4, p)) + goto end; + /* 'n7' = n1 + n3 */ + /* 'n8' = n2 + n4 */ + + /* Z_r */ + if (a->Z_is_one && b->Z_is_one) { + if (!BN_copy(&r->Z, n5)) + goto end; + } else { + if (a->Z_is_one) { + if (!BN_copy(n0, &b->Z)) + goto end; + } else if (b->Z_is_one) { + if (!BN_copy(n0, &a->Z)) + goto end; + } else { + if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) + goto end; + } + if (!field_mul(group, &r->Z, n0, n5, ctx)) + goto end; + } + r->Z_is_one = 0; + /* Z_r = Z_a * Z_b * n5 */ + + /* X_r */ + if (!field_sqr(group, n0, n6, ctx)) + goto end; + if (!field_sqr(group, n4, n5, ctx)) + goto end; + if (!field_mul(group, n3, n1, n4, ctx)) + goto end; + if (!BN_mod_sub_quick(&r->X, n0, n3, p)) + goto end; + /* X_r = n6^2 - n5^2 * 'n7' */ + + /* 'n9' */ + if (!BN_mod_lshift1_quick(n0, &r->X, p)) + goto end; + if (!BN_mod_sub_quick(n0, n3, n0, p)) + goto end; + /* n9 = n5^2 * 'n7' - 2 * X_r */ + + /* Y_r */ + if (!field_mul(group, n0, n0, n6, ctx)) + goto end; + if (!field_mul(group, n5, n4, n5, ctx)) + goto end; /* now n5 is n5^3 */ + if (!field_mul(group, n1, n2, n5, ctx)) + goto end; + if (!BN_mod_sub_quick(n0, n0, n1, p)) + goto end; + if (BN_is_odd(n0)) + if (!BN_add(n0, n0, p)) + goto end; + /* now 0 <= n0 < 2*p, and n0 is even */ + if (!BN_rshift1(&r->Y, n0)) + goto end; + /* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ + + ret = 1; + +end: + if (ctx) /* otherwise we already called BN_CTX_end */ + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, + BN_CTX *ctx) { + int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, + BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); + const BIGNUM *p; + BN_CTX *new_ctx = NULL; + BIGNUM *n0, *n1, *n2, *n3; + int ret = 0; + + if (EC_POINT_is_at_infinity(group, a)) { + BN_zero(&r->Z); + r->Z_is_one = 0; + return 1; + } + + field_mul = group->meth->field_mul; + field_sqr = group->meth->field_sqr; + p = &group->field; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + n0 = BN_CTX_get(ctx); + n1 = BN_CTX_get(ctx); + n2 = BN_CTX_get(ctx); + n3 = BN_CTX_get(ctx); + if (n3 == NULL) + goto err; + + /* Note that in this function we must not read components of 'a' + * once we have written the corresponding components of 'r'. + * ('r' might the same as 'a'.) + */ + + /* n1 */ + if (a->Z_is_one) { + if (!field_sqr(group, n0, &a->X, ctx)) + goto err; + if (!BN_mod_lshift1_quick(n1, n0, p)) + goto err; + if (!BN_mod_add_quick(n0, n0, n1, p)) + goto err; + if (!BN_mod_add_quick(n1, n0, &group->a, p)) + goto err; + /* n1 = 3 * X_a^2 + a_curve */ + } else if (group->a_is_minus3) { + if (!field_sqr(group, n1, &a->Z, ctx)) + goto err; + if (!BN_mod_add_quick(n0, &a->X, n1, p)) + goto err; + if (!BN_mod_sub_quick(n2, &a->X, n1, p)) + goto err; + if (!field_mul(group, n1, n0, n2, ctx)) + goto err; + if (!BN_mod_lshift1_quick(n0, n1, p)) + goto err; + if (!BN_mod_add_quick(n1, n0, n1, p)) + goto err; + /* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) + * = 3 * X_a^2 - 3 * Z_a^4 */ + } else { + if (!field_sqr(group, n0, &a->X, ctx)) + goto err; + if (!BN_mod_lshift1_quick(n1, n0, p)) + goto err; + if (!BN_mod_add_quick(n0, n0, n1, p)) + goto err; + if (!field_sqr(group, n1, &a->Z, ctx)) + goto err; + if (!field_sqr(group, n1, n1, ctx)) + goto err; + if (!field_mul(group, n1, n1, &group->a, ctx)) + goto err; + if (!BN_mod_add_quick(n1, n1, n0, p)) + goto err; + /* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ + } + + /* Z_r */ + if (a->Z_is_one) { + if (!BN_copy(n0, &a->Y)) + goto err; + } else { + if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) + goto err; + } + if (!BN_mod_lshift1_quick(&r->Z, n0, p)) + goto err; + r->Z_is_one = 0; + /* Z_r = 2 * Y_a * Z_a */ + + /* n2 */ + if (!field_sqr(group, n3, &a->Y, ctx)) + goto err; + if (!field_mul(group, n2, &a->X, n3, ctx)) + goto err; + if (!BN_mod_lshift_quick(n2, n2, 2, p)) + goto err; + /* n2 = 4 * X_a * Y_a^2 */ + + /* X_r */ + if (!BN_mod_lshift1_quick(n0, n2, p)) + goto err; + if (!field_sqr(group, &r->X, n1, ctx)) + goto err; + if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) + goto err; + /* X_r = n1^2 - 2 * n2 */ + + /* n3 */ + if (!field_sqr(group, n0, n3, ctx)) + goto err; + if (!BN_mod_lshift_quick(n3, n0, 3, p)) + goto err; + /* n3 = 8 * Y_a^4 */ + + /* Y_r */ + if (!BN_mod_sub_quick(n0, n2, &r->X, p)) + goto err; + if (!field_mul(group, n0, n1, n0, ctx)) + goto err; + if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) + goto err; + /* Y_r = n1 * (n2 - X_r) - n3 */ + + ret = 1; + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx) { + if (EC_POINT_is_at_infinity(group, point) || BN_is_zero(&point->Y)) + /* point is its own inverse */ + return 1; + + return BN_usub(&point->Y, &group->field, &point->Y); +} + +int ec_GFp_simple_is_at_infinity(const EC_GROUP *group, const EC_POINT *point) { + return !point->Z_is_one && BN_is_zero(&point->Z); +} + +int ec_GFp_simple_is_on_curve(const EC_GROUP *group, const EC_POINT *point, + BN_CTX *ctx) { + int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, + BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); + const BIGNUM *p; + BN_CTX *new_ctx = NULL; + BIGNUM *rh, *tmp, *Z4, *Z6; + int ret = -1; + + if (EC_POINT_is_at_infinity(group, point)) + return 1; + + field_mul = group->meth->field_mul; + field_sqr = group->meth->field_sqr; + p = &group->field; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return -1; + } + + BN_CTX_start(ctx); + rh = BN_CTX_get(ctx); + tmp = BN_CTX_get(ctx); + Z4 = BN_CTX_get(ctx); + Z6 = BN_CTX_get(ctx); + if (Z6 == NULL) + goto err; + + /* We have a curve defined by a Weierstrass equation + * y^2 = x^3 + a*x + b. + * The point to consider is given in Jacobian projective coordinates + * where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). + * Substituting this and multiplying by Z^6 transforms the above equation + * into + * Y^2 = X^3 + a*X*Z^4 + b*Z^6. + * To test this, we add up the right-hand side in 'rh'. + */ + + /* rh := X^2 */ + if (!field_sqr(group, rh, &point->X, ctx)) + goto err; + + if (!point->Z_is_one) { + if (!field_sqr(group, tmp, &point->Z, ctx)) + goto err; + if (!field_sqr(group, Z4, tmp, ctx)) + goto err; + if (!field_mul(group, Z6, Z4, tmp, ctx)) + goto err; + + /* rh := (rh + a*Z^4)*X */ + if (group->a_is_minus3) { + if (!BN_mod_lshift1_quick(tmp, Z4, p)) + goto err; + if (!BN_mod_add_quick(tmp, tmp, Z4, p)) + goto err; + if (!BN_mod_sub_quick(rh, rh, tmp, p)) + goto err; + if (!field_mul(group, rh, rh, &point->X, ctx)) + goto err; + } else { + if (!field_mul(group, tmp, Z4, &group->a, ctx)) + goto err; + if (!BN_mod_add_quick(rh, rh, tmp, p)) + goto err; + if (!field_mul(group, rh, rh, &point->X, ctx)) + goto err; + } + + /* rh := rh + b*Z^6 */ + if (!field_mul(group, tmp, &group->b, Z6, ctx)) + goto err; + if (!BN_mod_add_quick(rh, rh, tmp, p)) + goto err; + } else { + /* point->Z_is_one */ + + /* rh := (rh + a)*X */ + if (!BN_mod_add_quick(rh, rh, &group->a, p)) + goto err; + if (!field_mul(group, rh, rh, &point->X, ctx)) + goto err; + /* rh := rh + b */ + if (!BN_mod_add_quick(rh, rh, &group->b, p)) + goto err; + } + + /* 'lh' := Y^2 */ + if (!field_sqr(group, tmp, &point->Y, ctx)) + goto err; + + ret = (0 == BN_ucmp(tmp, rh)); + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_cmp(const EC_GROUP *group, const EC_POINT *a, + const EC_POINT *b, BN_CTX *ctx) { + /* return values: + * -1 error + * 0 equal (in affine coordinates) + * 1 not equal + */ + + int (*field_mul)(const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, + BN_CTX *); + int (*field_sqr)(const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); + BN_CTX *new_ctx = NULL; + BIGNUM *tmp1, *tmp2, *Za23, *Zb23; + const BIGNUM *tmp1_, *tmp2_; + int ret = -1; + + if (EC_POINT_is_at_infinity(group, a)) { + return EC_POINT_is_at_infinity(group, b) ? 0 : 1; + } + + if (EC_POINT_is_at_infinity(group, b)) + return 1; + + if (a->Z_is_one && b->Z_is_one) { + return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; + } + + field_mul = group->meth->field_mul; + field_sqr = group->meth->field_sqr; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return -1; + } + + BN_CTX_start(ctx); + tmp1 = BN_CTX_get(ctx); + tmp2 = BN_CTX_get(ctx); + Za23 = BN_CTX_get(ctx); + Zb23 = BN_CTX_get(ctx); + if (Zb23 == NULL) + goto end; + + /* We have to decide whether + * (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, Y_b/Z_b^3), + * or equivalently, whether + * (X_a*Z_b^2, Y_a*Z_b^3) = (X_b*Z_a^2, Y_b*Z_a^3). + */ + + if (!b->Z_is_one) { + if (!field_sqr(group, Zb23, &b->Z, ctx)) + goto end; + if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) + goto end; + tmp1_ = tmp1; + } else + tmp1_ = &a->X; + if (!a->Z_is_one) { + if (!field_sqr(group, Za23, &a->Z, ctx)) + goto end; + if (!field_mul(group, tmp2, &b->X, Za23, ctx)) + goto end; + tmp2_ = tmp2; + } else + tmp2_ = &b->X; + + /* compare X_a*Z_b^2 with X_b*Z_a^2 */ + if (BN_cmp(tmp1_, tmp2_) != 0) { + ret = 1; /* points differ */ + goto end; + } + + + if (!b->Z_is_one) { + if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) + goto end; + if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) + goto end; + /* tmp1_ = tmp1 */ + } else + tmp1_ = &a->Y; + if (!a->Z_is_one) { + if (!field_mul(group, Za23, Za23, &a->Z, ctx)) + goto end; + if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) + goto end; + /* tmp2_ = tmp2 */ + } else + tmp2_ = &b->Y; + + /* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ + if (BN_cmp(tmp1_, tmp2_) != 0) { + ret = 1; /* points differ */ + goto end; + } + + /* points are equal */ + ret = 0; + +end: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, + BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + BIGNUM *x, *y; + int ret = 0; + + if (point->Z_is_one || EC_POINT_is_at_infinity(group, point)) + return 1; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + x = BN_CTX_get(ctx); + y = BN_CTX_get(ctx); + if (y == NULL) + goto err; + + if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) + goto err; + if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) + goto err; + if (!point->Z_is_one) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_make_affine, ERR_R_INTERNAL_ERROR); + goto err; + } + + ret = 1; + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + return ret; +} + +int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, + EC_POINT *points[], BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + BIGNUM *tmp0, *tmp1; + size_t pow2 = 0; + BIGNUM **heap = NULL; + size_t i; + int ret = 0; + + if (num == 0) + return 1; + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + return 0; + } + + BN_CTX_start(ctx); + tmp0 = BN_CTX_get(ctx); + tmp1 = BN_CTX_get(ctx); + if (tmp0 == NULL || tmp1 == NULL) + goto err; + + /* Before converting the individual points, compute inverses of all Z values. + * Modular inversion is rather slow, but luckily we can do with a single + * explicit inversion, plus about 3 multiplications per input value. + */ + + pow2 = 1; + while (num > pow2) + pow2 <<= 1; + /* Now pow2 is the smallest power of 2 satifsying pow2 >= num. + * We need twice that. */ + pow2 <<= 1; + + heap = OPENSSL_malloc(pow2 * sizeof heap[0]); + if (heap == NULL) + goto err; + + /* The array is used as a binary tree, exactly as in heapsort: + * + * heap[1] + * heap[2] heap[3] + * heap[4] heap[5] heap[6] heap[7] + * heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15] + * + * We put the Z's in the last line; + * then we set each other node to the product of its two child-nodes (where + * empty or 0 entries are treated as ones); + * then we invert heap[1]; + * then we invert each other node by replacing it by the product of its + * parent (after inversion) and its sibling (before inversion). + */ + heap[0] = NULL; + for (i = pow2 / 2 - 1; i > 0; i--) + heap[i] = NULL; + for (i = 0; i < num; i++) + heap[pow2 / 2 + i] = &points[i]->Z; + for (i = pow2 / 2 + num; i < pow2; i++) + heap[i] = NULL; + + /* set each node to the product of its children */ + for (i = pow2 / 2 - 1; i > 0; i--) { + heap[i] = BN_new(); + if (heap[i] == NULL) + goto err; + + if (heap[2 * i] != NULL) { + if ((heap[2 * i + 1] == NULL) || BN_is_zero(heap[2 * i + 1])) { + if (!BN_copy(heap[i], heap[2 * i])) + goto err; + } else { + if (BN_is_zero(heap[2 * i])) { + if (!BN_copy(heap[i], heap[2 * i + 1])) + goto err; + } else { + if (!group->meth->field_mul(group, heap[i], heap[2 * i], + heap[2 * i + 1], ctx)) + goto err; + } + } + } + } + + /* invert heap[1] */ + if (!BN_is_zero(heap[1])) { + if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx)) { + OPENSSL_PUT_ERROR(EC, ec_GFp_simple_points_make_affine, ERR_R_BN_LIB); + goto err; + } + } + if (group->meth->field_encode != 0) { + /* in the Montgomery case, we just turned R*H (representing H) + * into 1/(R*H), but we need R*(1/H) (representing 1/H); + * i.e. we have need to multiply by the Montgomery factor twice */ + if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) { + goto err; + } + if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) { + goto err; + } + } + + /* set other heap[i]'s to their inverses */ + for (i = 2; i < pow2 / 2 + num; i += 2) { + /* i is even */ + if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1])) { + if (!group->meth->field_mul(group, tmp0, heap[i / 2], heap[i + 1], ctx)) + goto err; + if (!group->meth->field_mul(group, tmp1, heap[i / 2], heap[i], ctx)) + goto err; + if (!BN_copy(heap[i], tmp0)) + goto err; + if (!BN_copy(heap[i + 1], tmp1)) + goto err; + } else { + if (!BN_copy(heap[i], heap[i / 2])) + goto err; + } + } + + /* we have replaced all non-zero Z's by their inverses, now fix up all the + * points */ + for (i = 0; i < num; i++) { + EC_POINT *p = points[i]; + + if (!BN_is_zero(&p->Z)) { + /* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ + + if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) + goto err; + if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) + goto err; + + if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) + goto err; + if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) + goto err; + + if (group->meth->field_set_to_one != 0) { + if (!group->meth->field_set_to_one(group, &p->Z, ctx)) + goto err; + } else { + if (!BN_one(&p->Z)) + goto err; + } + p->Z_is_one = 1; + } + } + + ret = 1; + +err: + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + if (heap != NULL) { + /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */ + for (i = pow2 / 2 - 1; i > 0; i--) { + if (heap[i] != NULL) + BN_clear_free(heap[i]); + } + OPENSSL_free(heap); + } + return ret; +} + +int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, + const BIGNUM *b, BN_CTX *ctx) { + return BN_mod_mul(r, a, b, &group->field, ctx); +} + +int ec_GFp_simple_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, + BN_CTX *ctx) { + return BN_mod_sqr(r, a, &group->field, ctx); +}
diff --git a/crypto/ec/wnaf.c b/crypto/ec/wnaf.c new file mode 100644 index 0000000..b86107d --- /dev/null +++ b/crypto/ec/wnaf.c
@@ -0,0 +1,841 @@ +/* Originally written by Bodo Moeller for the OpenSSL project. + * ==================================================================== + * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * 3. All advertising materials mentioning features or use of this + * software must display the following acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" + * + * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to + * endorse or promote products derived from this software without + * prior written permission. For written permission, please contact + * openssl-core@openssl.org. + * + * 5. Products derived from this software may not be called "OpenSSL" + * nor may "OpenSSL" appear in their names without prior written + * permission of the OpenSSL Project. + * + * 6. Redistributions of any form whatsoever must retain the following + * acknowledgment: + * "This product includes software developed by the OpenSSL Project + * for use in the OpenSSL Toolkit (http://www.openssl.org/)" + * + * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY + * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR + * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE. + * ==================================================================== + * + * This product includes cryptographic software written by Eric Young + * (eay@cryptsoft.com). This product includes software written by Tim + * Hudson (tjh@cryptsoft.com). + * + */ +/* ==================================================================== + * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. + * + * Portions of the attached software ("Contribution") are developed by + * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. + * + * The Contribution is licensed pursuant to the OpenSSL open source + * license provided above. + * + * The elliptic curve binary polynomial software is originally written by + * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems + * Laboratories. */ + +#include <openssl/ec.h> + +#include <openssl/bn.h> +#include <openssl/err.h> +#include <openssl/mem.h> + +#include "internal.h" + + +/* This file implements the wNAF-based interleaving multi-exponentation method + * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>); + * for multiplication with precomputation, we use wNAF splitting + * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp>). + * */ + +/* structure for precomputed multiples of the generator */ +typedef struct ec_pre_comp_st { + const EC_GROUP *group; /* parent EC_GROUP object */ + size_t blocksize; /* block size for wNAF splitting */ + size_t numblocks; /* max. number of blocks for which we have precomputation */ + size_t w; /* window size */ + EC_POINT **points; /* array with pre-calculated multiples of generator: + * 'num' pointers to EC_POINT objects followed by a NULL */ + size_t num; /* numblocks * 2^(w-1) */ + int references; +} EC_PRE_COMP; + +static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group) { + EC_PRE_COMP *ret = NULL; + + if (!group) + return NULL; + + ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP)); + if (!ret) { + OPENSSL_PUT_ERROR(EC, ec_pre_comp_new, ERR_R_MALLOC_FAILURE); + return ret; + } + ret->group = group; + ret->blocksize = 8; /* default */ + ret->numblocks = 0; + ret->w = 4; /* default */ + ret->points = NULL; + ret->num = 0; + ret->references = 1; + return ret; +} + +void *ec_pre_comp_dup(EC_PRE_COMP *pre_comp) { + if (pre_comp == NULL) { + return NULL; + } + + CRYPTO_add(&pre_comp->references, 1, CRYPTO_LOCK_EC_PRE_COMP); + return pre_comp; +} + +void ec_pre_comp_free(EC_PRE_COMP *pre_comp) { + int i; + + if (!pre_comp) { + return; + } + + i = CRYPTO_add(&pre_comp->references, -1, CRYPTO_LOCK_EC_PRE_COMP); + if (i > 0) { + return; + } + + if (pre_comp->points) { + EC_POINT **p; + + for (p = pre_comp->points; *p != NULL; p++) { + EC_POINT_free(*p); + } + OPENSSL_free(pre_comp->points); + } + OPENSSL_free(pre_comp); +} + + +/* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'. + * This is an array r[] of values that are either zero or odd with an + * absolute value less than 2^w satisfying + * scalar = \sum_j r[j]*2^j + * where at most one of any w+1 consecutive digits is non-zero + * with the exception that the most significant digit may be only + * w-1 zeros away from that next non-zero digit. + */ +static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) { + int window_val; + int ok = 0; + signed char *r = NULL; + int sign = 1; + int bit, next_bit, mask; + size_t len = 0, j; + + if (BN_is_zero(scalar)) { + r = OPENSSL_malloc(1); + if (!r) { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_MALLOC_FAILURE); + goto err; + } + r[0] = 0; + *ret_len = 1; + return r; + } + + if (w <= 0 || w > 7) /* 'signed char' can represent integers with absolute + values less than 2^7 */ + { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_INTERNAL_ERROR); + goto err; + } + bit = 1 << w; /* at most 128 */ + next_bit = bit << 1; /* at most 256 */ + mask = next_bit - 1; /* at most 255 */ + + if (BN_is_negative(scalar)) { + sign = -1; + } + + if (scalar->d == NULL || scalar->top == 0) { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_INTERNAL_ERROR); + goto err; + } + + len = BN_num_bits(scalar); + r = OPENSSL_malloc( + len + + 1); /* modified wNAF may be one digit longer than binary representation + * (*ret_len will be set to the actual length, i.e. at most + * BN_num_bits(scalar) + 1) */ + if (r == NULL) { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_MALLOC_FAILURE); + goto err; + } + window_val = scalar->d[0] & mask; + j = 0; + while ((window_val != 0) || + (j + w + 1 < len)) /* if j+w+1 >= len, window_val will not increase */ + { + int digit = 0; + + /* 0 <= window_val <= 2^(w+1) */ + + if (window_val & 1) { + /* 0 < window_val < 2^(w+1) */ + + if (window_val & bit) { + digit = window_val - next_bit; /* -2^w < digit < 0 */ + +#if 1 /* modified wNAF */ + if (j + w + 1 >= len) { + /* special case for generating modified wNAFs: + * no new bits will be added into window_val, + * so using a positive digit here will decrease + * the total length of the representation */ + + digit = window_val & (mask >> 1); /* 0 < digit < 2^w */ + } +#endif + } else { + digit = window_val; /* 0 < digit < 2^w */ + } + + if (digit <= -bit || digit >= bit || !(digit & 1)) { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_INTERNAL_ERROR); + goto err; + } + + window_val -= digit; + + /* now window_val is 0 or 2^(w+1) in standard wNAF generation; + * for modified window NAFs, it may also be 2^w + */ + if (window_val != 0 && window_val != next_bit && window_val != bit) { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_INTERNAL_ERROR); + goto err; + } + } + + r[j++] = sign * digit; + + window_val >>= 1; + window_val += bit * BN_is_bit_set(scalar, j + w); + + if (window_val > next_bit) { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_INTERNAL_ERROR); + goto err; + } + } + + if (j > len + 1) { + OPENSSL_PUT_ERROR(EC, compute_wNAF, ERR_R_INTERNAL_ERROR); + goto err; + } + len = j; + ok = 1; + +err: + if (!ok) { + OPENSSL_free(r); + r = NULL; + } + if (ok) + *ret_len = len; + return r; +} + + +/* TODO: table should be optimised for the wNAF-based implementation, + * sometimes smaller windows will give better performance + * (thus the boundaries should be increased) + */ +#define EC_window_bits_for_scalar_size(b) \ + ((size_t)((b) >= 2000 ? 6 : (b) >= 800 ? 5 : (b) >= 300 \ + ? 4 \ + : (b) >= 70 ? 3 : (b) >= 20 \ + ? 2 \ + : 1)) + +/* Compute + * \sum scalars[i]*points[i], + * also including + * scalar*generator + * in the addition if scalar != NULL + */ +int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, + size_t num, const EC_POINT *points[], const BIGNUM *scalars[], + BN_CTX *ctx) { + BN_CTX *new_ctx = NULL; + const EC_POINT *generator = NULL; + EC_POINT *tmp = NULL; + size_t totalnum; + size_t blocksize = 0, numblocks = 0; /* for wNAF splitting */ + size_t pre_points_per_block = 0; + size_t i, j; + int k; + int r_is_inverted = 0; + int r_is_at_infinity = 1; + size_t *wsize = NULL; /* individual window sizes */ + signed char **wNAF = NULL; /* individual wNAFs */ + size_t *wNAF_len = NULL; + size_t max_len = 0; + size_t num_val; + EC_POINT **val = NULL; /* precomputation */ + EC_POINT **v; + EC_POINT ***val_sub = + NULL; /* pointers to sub-arrays of 'val' or 'pre_comp->points' */ + const EC_PRE_COMP *pre_comp = NULL; + int num_scalar = 0; /* flag: will be set to 1 if 'scalar' must be treated like + * other scalars, + * i.e. precomputation is not available */ + int ret = 0; + + if (group->meth != r->meth) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + + if ((scalar == NULL) && (num == 0)) { + return EC_POINT_set_to_infinity(group, r); + } + + for (i = 0; i < num; i++) { + if (group->meth != points[i]->meth) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, EC_R_INCOMPATIBLE_OBJECTS); + return 0; + } + } + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + goto err; + } + + if (scalar != NULL) { + generator = EC_GROUP_get0_generator(group); + if (generator == NULL) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, EC_R_UNDEFINED_GENERATOR); + goto err; + } + + /* look if we can use precomputed multiples of generator */ + + pre_comp = group->pre_comp; + + if (pre_comp && pre_comp->numblocks && + (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0)) { + blocksize = pre_comp->blocksize; + + /* determine maximum number of blocks that wNAF splitting may yield + * (NB: maximum wNAF length is bit length plus one) */ + numblocks = (BN_num_bits(scalar) / blocksize) + 1; + + /* we cannot use more blocks than we have precomputation for */ + if (numblocks > pre_comp->numblocks) + numblocks = pre_comp->numblocks; + + pre_points_per_block = (size_t)1 << (pre_comp->w - 1); + + /* check that pre_comp looks sane */ + if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block)) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR); + goto err; + } + } else { + /* can't use precomputation */ + pre_comp = NULL; + numblocks = 1; + num_scalar = 1; /* treat 'scalar' like 'num'-th element of 'scalars' */ + } + } + + totalnum = num + numblocks; + + wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]); + wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]); + wNAF = OPENSSL_malloc((totalnum + 1) * + sizeof wNAF[0]); /* includes space for pivot */ + val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]); + + if (!wsize || !wNAF_len || !wNAF || !val_sub) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_MALLOC_FAILURE); + goto err; + } + + wNAF[0] = NULL; /* preliminary pivot */ + + /* num_val will be the total number of temporarily precomputed points */ + num_val = 0; + + for (i = 0; i < num + num_scalar; i++) { + size_t bits; + + bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar); + wsize[i] = EC_window_bits_for_scalar_size(bits); + num_val += (size_t)1 << (wsize[i] - 1); + wNAF[i + 1] = NULL; /* make sure we always have a pivot */ + wNAF[i] = + compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]); + if (wNAF[i] == NULL) + goto err; + if (wNAF_len[i] > max_len) + max_len = wNAF_len[i]; + } + + if (numblocks) { + /* we go here iff scalar != NULL */ + + if (pre_comp == NULL) { + if (num_scalar != 1) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR); + goto err; + } + /* we have already generated a wNAF for 'scalar' */ + } else { + signed char *tmp_wNAF = NULL; + size_t tmp_len = 0; + + if (num_scalar != 0) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR); + goto err; + } + + /* use the window size for which we have precomputation */ + wsize[num] = pre_comp->w; + tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len); + if (!tmp_wNAF) + goto err; + + if (tmp_len <= max_len) { + /* One of the other wNAFs is at least as long + * as the wNAF belonging to the generator, + * so wNAF splitting will not buy us anything. */ + + numblocks = 1; + totalnum = num + 1; /* don't use wNAF splitting */ + wNAF[num] = tmp_wNAF; + wNAF[num + 1] = NULL; + wNAF_len[num] = tmp_len; + if (tmp_len > max_len) + max_len = tmp_len; + /* pre_comp->points starts with the points that we need here: */ + val_sub[num] = pre_comp->points; + } else { + /* don't include tmp_wNAF directly into wNAF array + * - use wNAF splitting and include the blocks */ + + signed char *pp; + EC_POINT **tmp_points; + + if (tmp_len < numblocks * blocksize) { + /* possibly we can do with fewer blocks than estimated */ + numblocks = (tmp_len + blocksize - 1) / blocksize; + if (numblocks > pre_comp->numblocks) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR); + goto err; + } + totalnum = num + numblocks; + } + + /* split wNAF in 'numblocks' parts */ + pp = tmp_wNAF; + tmp_points = pre_comp->points; + + for (i = num; i < totalnum; i++) { + if (i < totalnum - 1) { + wNAF_len[i] = blocksize; + if (tmp_len < blocksize) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR); + goto err; + } + tmp_len -= blocksize; + } else + /* last block gets whatever is left + * (this could be more or less than 'blocksize'!) */ + wNAF_len[i] = tmp_len; + + wNAF[i + 1] = NULL; + wNAF[i] = OPENSSL_malloc(wNAF_len[i]); + if (wNAF[i] == NULL) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_MALLOC_FAILURE); + OPENSSL_free(tmp_wNAF); + goto err; + } + memcpy(wNAF[i], pp, wNAF_len[i]); + if (wNAF_len[i] > max_len) + max_len = wNAF_len[i]; + + if (*tmp_points == NULL) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR); + OPENSSL_free(tmp_wNAF); + goto err; + } + val_sub[i] = tmp_points; + tmp_points += pre_points_per_block; + pp += blocksize; + } + OPENSSL_free(tmp_wNAF); + } + } + } + + /* All points we precompute now go into a single array 'val'. + * 'val_sub[i]' is a pointer to the subarray for the i-th point, + * or to a subarray of 'pre_comp->points' if we already have precomputation. + */ + val = OPENSSL_malloc((num_val + 1) * sizeof val[0]); + if (val == NULL) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_MALLOC_FAILURE); + goto err; + } + val[num_val] = NULL; /* pivot element */ + + /* allocate points for precomputation */ + v = val; + for (i = 0; i < num + num_scalar; i++) { + val_sub[i] = v; + for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) { + *v = EC_POINT_new(group); + if (*v == NULL) + goto err; + v++; + } + } + if (!(v == val + num_val)) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_mul, ERR_R_INTERNAL_ERROR); + goto err; + } + + if (!(tmp = EC_POINT_new(group))) + goto err; + + /* prepare precomputed values: + * val_sub[i][0] := points[i] + * val_sub[i][1] := 3 * points[i] + * val_sub[i][2] := 5 * points[i] + * ... + */ + for (i = 0; i < num + num_scalar; i++) { + if (i < num) { + if (!EC_POINT_copy(val_sub[i][0], points[i])) + goto err; + } else { + if (!EC_POINT_copy(val_sub[i][0], generator)) + goto err; + } + + if (wsize[i] > 1) { + if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) + goto err; + for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) { + if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) + goto err; + } + } + } + +#if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */ + if (!EC_POINTs_make_affine(group, num_val, val, ctx)) + goto err; +#endif + + r_is_at_infinity = 1; + + for (k = max_len - 1; k >= 0; k--) { + if (!r_is_at_infinity) { + if (!EC_POINT_dbl(group, r, r, ctx)) + goto err; + } + + for (i = 0; i < totalnum; i++) { + if (wNAF_len[i] > (size_t)k) { + int digit = wNAF[i][k]; + int is_neg; + + if (digit) { + is_neg = digit < 0; + + if (is_neg) + digit = -digit; + + if (is_neg != r_is_inverted) { + if (!r_is_at_infinity) { + if (!EC_POINT_invert(group, r, ctx)) + goto err; + } + r_is_inverted = !r_is_inverted; + } + + /* digit > 0 */ + + if (r_is_at_infinity) { + if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) + goto err; + r_is_at_infinity = 0; + } else { + if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) + goto err; + } + } + } + } + } + + if (r_is_at_infinity) { + if (!EC_POINT_set_to_infinity(group, r)) + goto err; + } else { + if (r_is_inverted) + if (!EC_POINT_invert(group, r, ctx)) + goto err; + } + + ret = 1; + +err: + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + if (tmp != NULL) + EC_POINT_free(tmp); + if (wsize != NULL) + OPENSSL_free(wsize); + if (wNAF_len != NULL) + OPENSSL_free(wNAF_len); + if (wNAF != NULL) { + signed char **w; + + for (w = wNAF; *w != NULL; w++) + OPENSSL_free(*w); + + OPENSSL_free(wNAF); + } + if (val != NULL) { + for (v = val; *v != NULL; v++) + EC_POINT_clear_free(*v); + + OPENSSL_free(val); + } + if (val_sub != NULL) { + OPENSSL_free(val_sub); + } + return ret; +} + + +/* ec_wNAF_precompute_mult() + * creates an EC_PRE_COMP object with preprecomputed multiples of the generator + * for use with wNAF splitting as implemented in ec_wNAF_mul(). + * + * 'pre_comp->points' is an array of multiples of the generator + * of the following form: + * points[0] = generator; + * points[1] = 3 * generator; + * ... + * points[2^(w-1)-1] = (2^(w-1)-1) * generator; + * points[2^(w-1)] = 2^blocksize * generator; + * points[2^(w-1)+1] = 3 * 2^blocksize * generator; + * ... + * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) * 2^(blocksize*(numblocks-2)) * + *generator + * points[2^(w-1)*(numblocks-1)] = 2^(blocksize*(numblocks-1)) * + *generator + * ... + * points[2^(w-1)*numblocks-1] = (2^(w-1)) * 2^(blocksize*(numblocks-1)) * + *generator + * points[2^(w-1)*numblocks] = NULL + */ +int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *ctx) { + const EC_POINT *generator; + EC_POINT *tmp_point = NULL, *base = NULL, **var; + BN_CTX *new_ctx = NULL; + BIGNUM *order; + size_t i, bits, w, pre_points_per_block, blocksize, numblocks, num; + EC_POINT **points = NULL; + EC_PRE_COMP *pre_comp; + int ret = 0; + + /* if there is an old EC_PRE_COMP object, throw it away */ + if (group->pre_comp) { + ec_pre_comp_free(group->pre_comp); + group->pre_comp = NULL; + } + + if ((pre_comp = ec_pre_comp_new(group)) == NULL) + return 0; + + generator = EC_GROUP_get0_generator(group); + if (generator == NULL) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, EC_R_UNDEFINED_GENERATOR); + goto err; + } + + if (ctx == NULL) { + ctx = new_ctx = BN_CTX_new(); + if (ctx == NULL) + goto err; + } + + BN_CTX_start(ctx); + order = BN_CTX_get(ctx); + if (order == NULL) + goto err; + + if (!EC_GROUP_get_order(group, order, ctx)) + goto err; + if (BN_is_zero(order)) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, EC_R_UNKNOWN_ORDER); + goto err; + } + + bits = BN_num_bits(order); + /* The following parameters mean we precompute (approximately) + * one point per bit. + * + * TBD: The combination 8, 4 is perfect for 160 bits; for other + * bit lengths, other parameter combinations might provide better + * efficiency. + */ + blocksize = 8; + w = 4; + if (EC_window_bits_for_scalar_size(bits) > w) { + /* let's not make the window too small ... */ + w = EC_window_bits_for_scalar_size(bits); + } + + numblocks = (bits + blocksize - 1) / + blocksize; /* max. number of blocks to use for wNAF splitting */ + + pre_points_per_block = (size_t)1 << (w - 1); + num = pre_points_per_block * + numblocks; /* number of points to compute and store */ + + points = OPENSSL_malloc(sizeof(EC_POINT *) * (num + 1)); + if (!points) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, ERR_R_MALLOC_FAILURE); + goto err; + } + + var = points; + var[num] = NULL; /* pivot */ + for (i = 0; i < num; i++) { + if ((var[i] = EC_POINT_new(group)) == NULL) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, ERR_R_MALLOC_FAILURE); + goto err; + } + } + + if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group))) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, ERR_R_MALLOC_FAILURE); + goto err; + } + + if (!EC_POINT_copy(base, generator)) + goto err; + + /* do the precomputation */ + for (i = 0; i < numblocks; i++) { + size_t j; + + if (!EC_POINT_dbl(group, tmp_point, base, ctx)) + goto err; + + if (!EC_POINT_copy(*var++, base)) + goto err; + + for (j = 1; j < pre_points_per_block; j++, var++) { + /* calculate odd multiples of the current base point */ + if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx)) + goto err; + } + + if (i < numblocks - 1) { + /* get the next base (multiply current one by 2^blocksize) */ + size_t k; + + if (blocksize <= 2) { + OPENSSL_PUT_ERROR(EC, ec_wNAF_precompute_mult, ERR_R_INTERNAL_ERROR); + goto err; + } + + if (!EC_POINT_dbl(group, base, tmp_point, ctx)) + goto err; + for (k = 2; k < blocksize; k++) { + if (!EC_POINT_dbl(group, base, base, ctx)) + goto err; + } + } + } + + if (!EC_POINTs_make_affine(group, num, points, ctx)) + goto err; + + pre_comp->group = group; + pre_comp->blocksize = blocksize; + pre_comp->numblocks = numblocks; + pre_comp->w = w; + pre_comp->points = points; + points = NULL; + pre_comp->num = num; + + group->pre_comp = pre_comp; + pre_comp = NULL; + + ret = 1; + +err: + if (ctx != NULL) + BN_CTX_end(ctx); + if (new_ctx != NULL) + BN_CTX_free(new_ctx); + if (pre_comp) + ec_pre_comp_free(pre_comp); + if (points) { + EC_POINT **p; + + for (p = points; *p != NULL; p++) + EC_POINT_free(*p); + OPENSSL_free(points); + } + if (tmp_point) + EC_POINT_free(tmp_point); + if (base) + EC_POINT_free(base); + return ret; +} + + +int ec_wNAF_have_precompute_mult(const EC_GROUP *group) { + return group->pre_comp != NULL; +}