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 24238384Sjkim * 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 76238384Sjkim/* Calculates and sets the affine coordinates of an EC_POINT from the given 77238384Sjkim * compressed coordinates. Uses algorithm 2.3.4 of SEC 1. 78238384Sjkim * Note that the simple implementation only uses affine coordinates. 79238384Sjkim * 80238384Sjkim * The method is from the following publication: 81238384Sjkim * 82238384Sjkim * Harper, Menezes, Vanstone: 83238384Sjkim * "Public-Key Cryptosystems with Very Small Key Lengths", 84238384Sjkim * EUROCRYPT '92, Springer-Verlag LNCS 658, 85238384Sjkim * published February 1993 86238384Sjkim * 87238384Sjkim * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe 88238384Sjkim * the same method, but claim no priority date earlier than July 29, 1994 89238384Sjkim * (and additionally fail to cite the EUROCRYPT '92 publication as prior art). 90238384Sjkim */ 91238384Sjkimint ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point, 92238384Sjkim const BIGNUM *x_, int y_bit, BN_CTX *ctx) 93238384Sjkim { 94238384Sjkim BN_CTX *new_ctx = NULL; 95238384Sjkim BIGNUM *tmp, *x, *y, *z; 96238384Sjkim int ret = 0, z0; 97238384Sjkim 98238384Sjkim /* clear error queue */ 99238384Sjkim ERR_clear_error(); 100238384Sjkim 101238384Sjkim if (ctx == NULL) 102238384Sjkim { 103238384Sjkim ctx = new_ctx = BN_CTX_new(); 104238384Sjkim if (ctx == NULL) 105238384Sjkim return 0; 106238384Sjkim } 107238384Sjkim 108238384Sjkim y_bit = (y_bit != 0) ? 1 : 0; 109238384Sjkim 110238384Sjkim BN_CTX_start(ctx); 111238384Sjkim tmp = BN_CTX_get(ctx); 112238384Sjkim x = BN_CTX_get(ctx); 113238384Sjkim y = BN_CTX_get(ctx); 114238384Sjkim z = BN_CTX_get(ctx); 115238384Sjkim if (z == NULL) goto err; 116238384Sjkim 117238384Sjkim if (!BN_GF2m_mod_arr(x, x_, group->poly)) goto err; 118238384Sjkim if (BN_is_zero(x)) 119238384Sjkim { 120238384Sjkim if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx)) goto err; 121238384Sjkim } 122238384Sjkim else 123238384Sjkim { 124238384Sjkim if (!group->meth->field_sqr(group, tmp, x, ctx)) goto err; 125238384Sjkim if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx)) goto err; 126238384Sjkim if (!BN_GF2m_add(tmp, &group->a, tmp)) goto err; 127238384Sjkim if (!BN_GF2m_add(tmp, x, tmp)) goto err; 128238384Sjkim if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) 129238384Sjkim { 130238384Sjkim unsigned long err = ERR_peek_last_error(); 131238384Sjkim 132238384Sjkim if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) 133238384Sjkim { 134238384Sjkim ERR_clear_error(); 135238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, EC_R_INVALID_COMPRESSED_POINT); 136238384Sjkim } 137238384Sjkim else 138238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, ERR_R_BN_LIB); 139238384Sjkim goto err; 140238384Sjkim } 141238384Sjkim z0 = (BN_is_odd(z)) ? 1 : 0; 142238384Sjkim if (!group->meth->field_mul(group, y, x, z, ctx)) goto err; 143238384Sjkim if (z0 != y_bit) 144238384Sjkim { 145238384Sjkim if (!BN_GF2m_add(y, y, x)) goto err; 146238384Sjkim } 147238384Sjkim } 148238384Sjkim 149238384Sjkim if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err; 150238384Sjkim 151238384Sjkim ret = 1; 152238384Sjkim 153238384Sjkim err: 154238384Sjkim BN_CTX_end(ctx); 155238384Sjkim if (new_ctx != NULL) 156238384Sjkim BN_CTX_free(new_ctx); 157238384Sjkim return ret; 158238384Sjkim } 159238384Sjkim 160238384Sjkim 161238384Sjkim/* Converts an EC_POINT to an octet string. 162238384Sjkim * If buf is NULL, the encoded length will be returned. 163238384Sjkim * If the length len of buf is smaller than required an error will be returned. 164238384Sjkim */ 165238384Sjkimsize_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, point_conversion_form_t form, 166238384Sjkim unsigned char *buf, size_t len, BN_CTX *ctx) 167238384Sjkim { 168238384Sjkim size_t ret; 169238384Sjkim BN_CTX *new_ctx = NULL; 170238384Sjkim int used_ctx = 0; 171238384Sjkim BIGNUM *x, *y, *yxi; 172238384Sjkim size_t field_len, i, skip; 173238384Sjkim 174238384Sjkim if ((form != POINT_CONVERSION_COMPRESSED) 175238384Sjkim && (form != POINT_CONVERSION_UNCOMPRESSED) 176238384Sjkim && (form != POINT_CONVERSION_HYBRID)) 177238384Sjkim { 178238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 179238384Sjkim goto err; 180238384Sjkim } 181238384Sjkim 182238384Sjkim if (EC_POINT_is_at_infinity(group, point)) 183238384Sjkim { 184238384Sjkim /* encodes to a single 0 octet */ 185238384Sjkim if (buf != NULL) 186238384Sjkim { 187238384Sjkim if (len < 1) 188238384Sjkim { 189238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 190238384Sjkim return 0; 191238384Sjkim } 192238384Sjkim buf[0] = 0; 193238384Sjkim } 194238384Sjkim return 1; 195238384Sjkim } 196238384Sjkim 197238384Sjkim 198238384Sjkim /* ret := required output buffer length */ 199238384Sjkim field_len = (EC_GROUP_get_degree(group) + 7) / 8; 200238384Sjkim ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len; 201238384Sjkim 202238384Sjkim /* if 'buf' is NULL, just return required length */ 203238384Sjkim if (buf != NULL) 204238384Sjkim { 205238384Sjkim if (len < ret) 206238384Sjkim { 207238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 208238384Sjkim goto err; 209238384Sjkim } 210238384Sjkim 211238384Sjkim if (ctx == NULL) 212238384Sjkim { 213238384Sjkim ctx = new_ctx = BN_CTX_new(); 214238384Sjkim if (ctx == NULL) 215238384Sjkim return 0; 216238384Sjkim } 217238384Sjkim 218238384Sjkim BN_CTX_start(ctx); 219238384Sjkim used_ctx = 1; 220238384Sjkim x = BN_CTX_get(ctx); 221238384Sjkim y = BN_CTX_get(ctx); 222238384Sjkim yxi = BN_CTX_get(ctx); 223238384Sjkim if (yxi == NULL) goto err; 224238384Sjkim 225238384Sjkim if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err; 226238384Sjkim 227238384Sjkim buf[0] = form; 228238384Sjkim if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) 229238384Sjkim { 230238384Sjkim if (!group->meth->field_div(group, yxi, y, x, ctx)) goto err; 231238384Sjkim if (BN_is_odd(yxi)) buf[0]++; 232238384Sjkim } 233238384Sjkim 234238384Sjkim i = 1; 235238384Sjkim 236238384Sjkim skip = field_len - BN_num_bytes(x); 237238384Sjkim if (skip > field_len) 238238384Sjkim { 239238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 240238384Sjkim goto err; 241238384Sjkim } 242238384Sjkim while (skip > 0) 243238384Sjkim { 244238384Sjkim buf[i++] = 0; 245238384Sjkim skip--; 246238384Sjkim } 247238384Sjkim skip = BN_bn2bin(x, buf + i); 248238384Sjkim i += skip; 249238384Sjkim if (i != 1 + field_len) 250238384Sjkim { 251238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 252238384Sjkim goto err; 253238384Sjkim } 254238384Sjkim 255238384Sjkim if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID) 256238384Sjkim { 257238384Sjkim skip = field_len - BN_num_bytes(y); 258238384Sjkim if (skip > field_len) 259238384Sjkim { 260238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 261238384Sjkim goto err; 262238384Sjkim } 263238384Sjkim while (skip > 0) 264238384Sjkim { 265238384Sjkim buf[i++] = 0; 266238384Sjkim skip--; 267238384Sjkim } 268238384Sjkim skip = BN_bn2bin(y, buf + i); 269238384Sjkim i += skip; 270238384Sjkim } 271238384Sjkim 272238384Sjkim if (i != ret) 273238384Sjkim { 274238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 275238384Sjkim goto err; 276238384Sjkim } 277238384Sjkim } 278238384Sjkim 279238384Sjkim if (used_ctx) 280238384Sjkim BN_CTX_end(ctx); 281238384Sjkim if (new_ctx != NULL) 282238384Sjkim BN_CTX_free(new_ctx); 283238384Sjkim return ret; 284238384Sjkim 285238384Sjkim err: 286238384Sjkim if (used_ctx) 287238384Sjkim BN_CTX_end(ctx); 288238384Sjkim if (new_ctx != NULL) 289238384Sjkim BN_CTX_free(new_ctx); 290238384Sjkim return 0; 291238384Sjkim } 292238384Sjkim 293238384Sjkim 294238384Sjkim/* Converts an octet string representation to an EC_POINT. 295238384Sjkim * Note that the simple implementation only uses affine coordinates. 296238384Sjkim */ 297238384Sjkimint ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 298238384Sjkim const unsigned char *buf, size_t len, BN_CTX *ctx) 299238384Sjkim { 300238384Sjkim point_conversion_form_t form; 301238384Sjkim int y_bit; 302238384Sjkim BN_CTX *new_ctx = NULL; 303238384Sjkim BIGNUM *x, *y, *yxi; 304238384Sjkim size_t field_len, enc_len; 305238384Sjkim int ret = 0; 306238384Sjkim 307238384Sjkim if (len == 0) 308238384Sjkim { 309238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 310238384Sjkim return 0; 311238384Sjkim } 312238384Sjkim form = buf[0]; 313238384Sjkim y_bit = form & 1; 314238384Sjkim form = form & ~1U; 315238384Sjkim if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 316238384Sjkim && (form != POINT_CONVERSION_UNCOMPRESSED) 317238384Sjkim && (form != POINT_CONVERSION_HYBRID)) 318238384Sjkim { 319238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 320238384Sjkim return 0; 321238384Sjkim } 322238384Sjkim if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) 323238384Sjkim { 324238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 325238384Sjkim return 0; 326238384Sjkim } 327238384Sjkim 328238384Sjkim if (form == 0) 329238384Sjkim { 330238384Sjkim if (len != 1) 331238384Sjkim { 332238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 333238384Sjkim return 0; 334238384Sjkim } 335238384Sjkim 336238384Sjkim return EC_POINT_set_to_infinity(group, point); 337238384Sjkim } 338238384Sjkim 339238384Sjkim field_len = (EC_GROUP_get_degree(group) + 7) / 8; 340238384Sjkim enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2*field_len; 341238384Sjkim 342238384Sjkim if (len != enc_len) 343238384Sjkim { 344238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 345238384Sjkim return 0; 346238384Sjkim } 347238384Sjkim 348238384Sjkim if (ctx == NULL) 349238384Sjkim { 350238384Sjkim ctx = new_ctx = BN_CTX_new(); 351238384Sjkim if (ctx == NULL) 352238384Sjkim return 0; 353238384Sjkim } 354238384Sjkim 355238384Sjkim BN_CTX_start(ctx); 356238384Sjkim x = BN_CTX_get(ctx); 357238384Sjkim y = BN_CTX_get(ctx); 358238384Sjkim yxi = BN_CTX_get(ctx); 359238384Sjkim if (yxi == NULL) goto err; 360238384Sjkim 361238384Sjkim if (!BN_bin2bn(buf + 1, field_len, x)) goto err; 362238384Sjkim if (BN_ucmp(x, &group->field) >= 0) 363238384Sjkim { 364238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 365238384Sjkim goto err; 366238384Sjkim } 367238384Sjkim 368238384Sjkim if (form == POINT_CONVERSION_COMPRESSED) 369238384Sjkim { 370238384Sjkim if (!EC_POINT_set_compressed_coordinates_GF2m(group, point, x, y_bit, ctx)) goto err; 371238384Sjkim } 372238384Sjkim else 373238384Sjkim { 374238384Sjkim if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) goto err; 375238384Sjkim if (BN_ucmp(y, &group->field) >= 0) 376238384Sjkim { 377238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 378238384Sjkim goto err; 379238384Sjkim } 380238384Sjkim if (form == POINT_CONVERSION_HYBRID) 381238384Sjkim { 382238384Sjkim if (!group->meth->field_div(group, yxi, y, x, ctx)) goto err; 383238384Sjkim if (y_bit != BN_is_odd(yxi)) 384238384Sjkim { 385238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 386238384Sjkim goto err; 387238384Sjkim } 388238384Sjkim } 389238384Sjkim 390238384Sjkim if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) goto err; 391238384Sjkim } 392238384Sjkim 393238384Sjkim if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */ 394238384Sjkim { 395238384Sjkim ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); 396238384Sjkim goto err; 397238384Sjkim } 398238384Sjkim 399238384Sjkim ret = 1; 400238384Sjkim 401238384Sjkim err: 402238384Sjkim BN_CTX_end(ctx); 403238384Sjkim if (new_ctx != NULL) 404238384Sjkim BN_CTX_free(new_ctx); 405238384Sjkim return ret; 406238384Sjkim } 407238384Sjkim#endif 408