1238384Sjkim/* crypto/ec/ec2_oct.c */ 2238384Sjkim/* ==================================================================== 3238384Sjkim * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 4238384Sjkim * 5238384Sjkim * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 6238384Sjkim * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 7238384Sjkim * to the OpenSSL project. 8238384Sjkim * 9238384Sjkim * The ECC Code is licensed pursuant to the OpenSSL open source 10238384Sjkim * license provided below. 11238384Sjkim * 12238384Sjkim * The software is originally written by Sheueling Chang Shantz and 13238384Sjkim * Douglas Stebila of Sun Microsystems Laboratories. 14238384Sjkim * 15238384Sjkim */ 16238384Sjkim/* ==================================================================== 17238384Sjkim * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 18238384Sjkim * 19238384Sjkim * Redistribution and use in source and binary forms, with or without 20238384Sjkim * modification, are permitted provided that the following conditions 21238384Sjkim * are met: 22238384Sjkim * 23238384Sjkim * 1. Redistributions of source code must retain the above copyright 24296341Sdelphij * notice, this list of conditions and the following disclaimer. 25238384Sjkim * 26238384Sjkim * 2. Redistributions in binary form must reproduce the above copyright 27238384Sjkim * notice, this list of conditions and the following disclaimer in 28238384Sjkim * the documentation and/or other materials provided with the 29238384Sjkim * distribution. 30238384Sjkim * 31238384Sjkim * 3. All advertising materials mentioning features or use of this 32238384Sjkim * software must display the following acknowledgment: 33238384Sjkim * "This product includes software developed by the OpenSSL Project 34238384Sjkim * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 35238384Sjkim * 36238384Sjkim * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 37238384Sjkim * endorse or promote products derived from this software without 38238384Sjkim * prior written permission. For written permission, please contact 39238384Sjkim * openssl-core@openssl.org. 40238384Sjkim * 41238384Sjkim * 5. Products derived from this software may not be called "OpenSSL" 42238384Sjkim * nor may "OpenSSL" appear in their names without prior written 43238384Sjkim * permission of the OpenSSL Project. 44238384Sjkim * 45238384Sjkim * 6. Redistributions of any form whatsoever must retain the following 46238384Sjkim * acknowledgment: 47238384Sjkim * "This product includes software developed by the OpenSSL Project 48238384Sjkim * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 49238384Sjkim * 50238384Sjkim * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 51238384Sjkim * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52238384Sjkim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 53238384Sjkim * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 54238384Sjkim * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 55238384Sjkim * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 56238384Sjkim * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 57238384Sjkim * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58238384Sjkim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 59238384Sjkim * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 60238384Sjkim * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 61238384Sjkim * OF THE POSSIBILITY OF SUCH DAMAGE. 62238384Sjkim * ==================================================================== 63238384Sjkim * 64238384Sjkim * This product includes cryptographic software written by Eric Young 65238384Sjkim * (eay@cryptsoft.com). This product includes software written by Tim 66238384Sjkim * Hudson (tjh@cryptsoft.com). 67238384Sjkim * 68238384Sjkim */ 69238384Sjkim 70238384Sjkim#include <openssl/err.h> 71238384Sjkim 72238384Sjkim#include "ec_lcl.h" 73238384Sjkim 74238384Sjkim#ifndef OPENSSL_NO_EC2M 75238384Sjkim 76296341Sdelphij/*- 77296341Sdelphij * Calculates and sets the affine coordinates of an EC_POINT from the given 78296341Sdelphij * compressed coordinates. Uses algorithm 2.3.4 of SEC 1. 79238384Sjkim * Note that the simple implementation only uses affine coordinates. 80238384Sjkim * 81238384Sjkim * The method is from the following publication: 82296341Sdelphij * 83238384Sjkim * Harper, Menezes, Vanstone: 84238384Sjkim * "Public-Key Cryptosystems with Very Small Key Lengths", 85238384Sjkim * EUROCRYPT '92, Springer-Verlag LNCS 658, 86238384Sjkim * published February 1993 87238384Sjkim * 88238384Sjkim * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe 89238384Sjkim * the same method, but claim no priority date earlier than July 29, 1994 90238384Sjkim * (and additionally fail to cite the EUROCRYPT '92 publication as prior art). 91238384Sjkim */ 92296341Sdelphijint ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group, 93296341Sdelphij EC_POINT *point, 94296341Sdelphij const BIGNUM *x_, int y_bit, 95296341Sdelphij BN_CTX *ctx) 96296341Sdelphij{ 97296341Sdelphij BN_CTX *new_ctx = NULL; 98296341Sdelphij BIGNUM *tmp, *x, *y, *z; 99296341Sdelphij int ret = 0, z0; 100238384Sjkim 101296341Sdelphij /* clear error queue */ 102296341Sdelphij ERR_clear_error(); 103238384Sjkim 104296341Sdelphij if (ctx == NULL) { 105296341Sdelphij ctx = new_ctx = BN_CTX_new(); 106296341Sdelphij if (ctx == NULL) 107296341Sdelphij return 0; 108296341Sdelphij } 109238384Sjkim 110296341Sdelphij y_bit = (y_bit != 0) ? 1 : 0; 111238384Sjkim 112296341Sdelphij BN_CTX_start(ctx); 113296341Sdelphij tmp = BN_CTX_get(ctx); 114296341Sdelphij x = BN_CTX_get(ctx); 115296341Sdelphij y = BN_CTX_get(ctx); 116296341Sdelphij z = BN_CTX_get(ctx); 117296341Sdelphij if (z == NULL) 118296341Sdelphij goto err; 119238384Sjkim 120296341Sdelphij if (!BN_GF2m_mod_arr(x, x_, group->poly)) 121296341Sdelphij goto err; 122296341Sdelphij if (BN_is_zero(x)) { 123296341Sdelphij if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx)) 124296341Sdelphij goto err; 125296341Sdelphij } else { 126296341Sdelphij if (!group->meth->field_sqr(group, tmp, x, ctx)) 127296341Sdelphij goto err; 128296341Sdelphij if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx)) 129296341Sdelphij goto err; 130296341Sdelphij if (!BN_GF2m_add(tmp, &group->a, tmp)) 131296341Sdelphij goto err; 132296341Sdelphij if (!BN_GF2m_add(tmp, x, tmp)) 133296341Sdelphij goto err; 134296341Sdelphij if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) { 135296341Sdelphij unsigned long err = ERR_peek_last_error(); 136238384Sjkim 137296341Sdelphij if (ERR_GET_LIB(err) == ERR_LIB_BN 138296341Sdelphij && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) { 139296341Sdelphij ERR_clear_error(); 140296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, 141296341Sdelphij EC_R_INVALID_COMPRESSED_POINT); 142296341Sdelphij } else 143296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, 144296341Sdelphij ERR_R_BN_LIB); 145296341Sdelphij goto err; 146296341Sdelphij } 147296341Sdelphij z0 = (BN_is_odd(z)) ? 1 : 0; 148296341Sdelphij if (!group->meth->field_mul(group, y, x, z, ctx)) 149296341Sdelphij goto err; 150296341Sdelphij if (z0 != y_bit) { 151296341Sdelphij if (!BN_GF2m_add(y, y, x)) 152296341Sdelphij goto err; 153296341Sdelphij } 154296341Sdelphij } 155238384Sjkim 156296341Sdelphij if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) 157296341Sdelphij goto err; 158238384Sjkim 159296341Sdelphij ret = 1; 160296341Sdelphij 161238384Sjkim err: 162296341Sdelphij BN_CTX_end(ctx); 163296341Sdelphij if (new_ctx != NULL) 164296341Sdelphij BN_CTX_free(new_ctx); 165296341Sdelphij return ret; 166296341Sdelphij} 167238384Sjkim 168296341Sdelphij/* 169296341Sdelphij * Converts an EC_POINT to an octet string. If buf is NULL, the encoded 170296341Sdelphij * length will be returned. If the length len of buf is smaller than required 171296341Sdelphij * an error will be returned. 172238384Sjkim */ 173296341Sdelphijsize_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 174296341Sdelphij point_conversion_form_t form, 175296341Sdelphij unsigned char *buf, size_t len, BN_CTX *ctx) 176296341Sdelphij{ 177296341Sdelphij size_t ret; 178296341Sdelphij BN_CTX *new_ctx = NULL; 179296341Sdelphij int used_ctx = 0; 180296341Sdelphij BIGNUM *x, *y, *yxi; 181296341Sdelphij size_t field_len, i, skip; 182238384Sjkim 183296341Sdelphij if ((form != POINT_CONVERSION_COMPRESSED) 184296341Sdelphij && (form != POINT_CONVERSION_UNCOMPRESSED) 185296341Sdelphij && (form != POINT_CONVERSION_HYBRID)) { 186296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 187296341Sdelphij goto err; 188296341Sdelphij } 189238384Sjkim 190296341Sdelphij if (EC_POINT_is_at_infinity(group, point)) { 191296341Sdelphij /* encodes to a single 0 octet */ 192296341Sdelphij if (buf != NULL) { 193296341Sdelphij if (len < 1) { 194296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 195296341Sdelphij return 0; 196296341Sdelphij } 197296341Sdelphij buf[0] = 0; 198296341Sdelphij } 199296341Sdelphij return 1; 200296341Sdelphij } 201238384Sjkim 202296341Sdelphij /* ret := required output buffer length */ 203296341Sdelphij field_len = (EC_GROUP_get_degree(group) + 7) / 8; 204296341Sdelphij ret = 205296341Sdelphij (form == 206296341Sdelphij POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 207238384Sjkim 208296341Sdelphij /* if 'buf' is NULL, just return required length */ 209296341Sdelphij if (buf != NULL) { 210296341Sdelphij if (len < ret) { 211296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 212296341Sdelphij goto err; 213296341Sdelphij } 214238384Sjkim 215296341Sdelphij if (ctx == NULL) { 216296341Sdelphij ctx = new_ctx = BN_CTX_new(); 217296341Sdelphij if (ctx == NULL) 218296341Sdelphij return 0; 219296341Sdelphij } 220238384Sjkim 221296341Sdelphij BN_CTX_start(ctx); 222296341Sdelphij used_ctx = 1; 223296341Sdelphij x = BN_CTX_get(ctx); 224296341Sdelphij y = BN_CTX_get(ctx); 225296341Sdelphij yxi = BN_CTX_get(ctx); 226296341Sdelphij if (yxi == NULL) 227296341Sdelphij goto err; 228238384Sjkim 229296341Sdelphij if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) 230296341Sdelphij goto err; 231238384Sjkim 232296341Sdelphij buf[0] = form; 233296341Sdelphij if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) { 234296341Sdelphij if (!group->meth->field_div(group, yxi, y, x, ctx)) 235296341Sdelphij goto err; 236296341Sdelphij if (BN_is_odd(yxi)) 237296341Sdelphij buf[0]++; 238296341Sdelphij } 239238384Sjkim 240296341Sdelphij i = 1; 241238384Sjkim 242296341Sdelphij skip = field_len - BN_num_bytes(x); 243296341Sdelphij if (skip > field_len) { 244296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 245296341Sdelphij goto err; 246296341Sdelphij } 247296341Sdelphij while (skip > 0) { 248296341Sdelphij buf[i++] = 0; 249296341Sdelphij skip--; 250296341Sdelphij } 251296341Sdelphij skip = BN_bn2bin(x, buf + i); 252296341Sdelphij i += skip; 253296341Sdelphij if (i != 1 + field_len) { 254296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 255296341Sdelphij goto err; 256296341Sdelphij } 257238384Sjkim 258296341Sdelphij if (form == POINT_CONVERSION_UNCOMPRESSED 259296341Sdelphij || form == POINT_CONVERSION_HYBRID) { 260296341Sdelphij skip = field_len - BN_num_bytes(y); 261296341Sdelphij if (skip > field_len) { 262296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 263296341Sdelphij goto err; 264296341Sdelphij } 265296341Sdelphij while (skip > 0) { 266296341Sdelphij buf[i++] = 0; 267296341Sdelphij skip--; 268296341Sdelphij } 269296341Sdelphij skip = BN_bn2bin(y, buf + i); 270296341Sdelphij i += skip; 271296341Sdelphij } 272238384Sjkim 273296341Sdelphij if (i != ret) { 274296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 275296341Sdelphij goto err; 276296341Sdelphij } 277296341Sdelphij } 278238384Sjkim 279296341Sdelphij if (used_ctx) 280296341Sdelphij BN_CTX_end(ctx); 281296341Sdelphij if (new_ctx != NULL) 282296341Sdelphij BN_CTX_free(new_ctx); 283296341Sdelphij return ret; 284296341Sdelphij 285238384Sjkim err: 286296341Sdelphij if (used_ctx) 287296341Sdelphij BN_CTX_end(ctx); 288296341Sdelphij if (new_ctx != NULL) 289296341Sdelphij BN_CTX_free(new_ctx); 290296341Sdelphij return 0; 291296341Sdelphij} 292238384Sjkim 293296341Sdelphij/* 294296341Sdelphij * Converts an octet string representation to an EC_POINT. Note that the 295296341Sdelphij * simple implementation only uses affine coordinates. 296238384Sjkim */ 297238384Sjkimint ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 298296341Sdelphij const unsigned char *buf, size_t len, 299296341Sdelphij BN_CTX *ctx) 300296341Sdelphij{ 301296341Sdelphij point_conversion_form_t form; 302296341Sdelphij int y_bit; 303296341Sdelphij BN_CTX *new_ctx = NULL; 304296341Sdelphij BIGNUM *x, *y, *yxi; 305296341Sdelphij size_t field_len, enc_len; 306296341Sdelphij int ret = 0; 307238384Sjkim 308296341Sdelphij if (len == 0) { 309296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 310296341Sdelphij return 0; 311296341Sdelphij } 312296341Sdelphij form = buf[0]; 313296341Sdelphij y_bit = form & 1; 314296341Sdelphij form = form & ~1U; 315296341Sdelphij if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 316296341Sdelphij && (form != POINT_CONVERSION_UNCOMPRESSED) 317296341Sdelphij && (form != POINT_CONVERSION_HYBRID)) { 318296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 319296341Sdelphij return 0; 320296341Sdelphij } 321296341Sdelphij if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 322296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 323296341Sdelphij return 0; 324296341Sdelphij } 325238384Sjkim 326296341Sdelphij if (form == 0) { 327296341Sdelphij if (len != 1) { 328296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 329296341Sdelphij return 0; 330296341Sdelphij } 331238384Sjkim 332296341Sdelphij return EC_POINT_set_to_infinity(group, point); 333296341Sdelphij } 334238384Sjkim 335296341Sdelphij field_len = (EC_GROUP_get_degree(group) + 7) / 8; 336296341Sdelphij enc_len = 337296341Sdelphij (form == 338296341Sdelphij POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 339238384Sjkim 340296341Sdelphij if (len != enc_len) { 341296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 342296341Sdelphij return 0; 343296341Sdelphij } 344238384Sjkim 345296341Sdelphij if (ctx == NULL) { 346296341Sdelphij ctx = new_ctx = BN_CTX_new(); 347296341Sdelphij if (ctx == NULL) 348296341Sdelphij return 0; 349296341Sdelphij } 350238384Sjkim 351296341Sdelphij BN_CTX_start(ctx); 352296341Sdelphij x = BN_CTX_get(ctx); 353296341Sdelphij y = BN_CTX_get(ctx); 354296341Sdelphij yxi = BN_CTX_get(ctx); 355296341Sdelphij if (yxi == NULL) 356296341Sdelphij goto err; 357238384Sjkim 358296341Sdelphij if (!BN_bin2bn(buf + 1, field_len, x)) 359296341Sdelphij goto err; 360296341Sdelphij if (BN_ucmp(x, &group->field) >= 0) { 361296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 362296341Sdelphij goto err; 363296341Sdelphij } 364238384Sjkim 365296341Sdelphij if (form == POINT_CONVERSION_COMPRESSED) { 366296341Sdelphij if (!EC_POINT_set_compressed_coordinates_GF2m 367296341Sdelphij (group, point, x, y_bit, ctx)) 368296341Sdelphij goto err; 369296341Sdelphij } else { 370296341Sdelphij if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 371296341Sdelphij goto err; 372296341Sdelphij if (BN_ucmp(y, &group->field) >= 0) { 373296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 374296341Sdelphij goto err; 375296341Sdelphij } 376296341Sdelphij if (form == POINT_CONVERSION_HYBRID) { 377296341Sdelphij if (!group->meth->field_div(group, yxi, y, x, ctx)) 378296341Sdelphij goto err; 379296341Sdelphij if (y_bit != BN_is_odd(yxi)) { 380296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 381296341Sdelphij goto err; 382296341Sdelphij } 383296341Sdelphij } 384238384Sjkim 385296341Sdelphij if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) 386296341Sdelphij goto err; 387296341Sdelphij } 388296341Sdelphij 389296341Sdelphij /* test required by X9.62 */ 390296341Sdelphij if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 391296341Sdelphij ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); 392296341Sdelphij goto err; 393296341Sdelphij } 394296341Sdelphij 395296341Sdelphij ret = 1; 396296341Sdelphij 397238384Sjkim err: 398296341Sdelphij BN_CTX_end(ctx); 399296341Sdelphij if (new_ctx != NULL) 400296341Sdelphij BN_CTX_free(new_ctx); 401296341Sdelphij return ret; 402296341Sdelphij} 403238384Sjkim#endif 404