1/* crypto/ec/ec2_oct.c */ 2/* ==================================================================== 3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 4 * 5 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 6 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 7 * to the OpenSSL project. 8 * 9 * The ECC Code is licensed pursuant to the OpenSSL open source 10 * license provided below. 11 * 12 * The software is originally written by Sheueling Chang Shantz and 13 * Douglas Stebila of Sun Microsystems Laboratories. 14 * 15 */ 16/* ==================================================================== 17 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 18 * 19 * Redistribution and use in source and binary forms, with or without 20 * modification, are permitted provided that the following conditions 21 * are met: 22 * 23 * 1. Redistributions of source code must retain the above copyright 24 * notice, this list of conditions and the following disclaimer. 25 * 26 * 2. Redistributions in binary form must reproduce the above copyright 27 * notice, this list of conditions and the following disclaimer in 28 * the documentation and/or other materials provided with the 29 * distribution. 30 * 31 * 3. All advertising materials mentioning features or use of this 32 * software must display the following acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 35 * 36 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 37 * endorse or promote products derived from this software without 38 * prior written permission. For written permission, please contact 39 * openssl-core@openssl.org. 40 * 41 * 5. Products derived from this software may not be called "OpenSSL" 42 * nor may "OpenSSL" appear in their names without prior written 43 * permission of the OpenSSL Project. 44 * 45 * 6. Redistributions of any form whatsoever must retain the following 46 * acknowledgment: 47 * "This product includes software developed by the OpenSSL Project 48 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 49 * 50 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 51 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 53 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 54 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 55 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 56 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 57 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 59 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 60 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 61 * OF THE POSSIBILITY OF SUCH DAMAGE. 62 * ==================================================================== 63 * 64 * This product includes cryptographic software written by Eric Young 65 * (eay@cryptsoft.com). This product includes software written by Tim 66 * Hudson (tjh@cryptsoft.com). 67 * 68 */ 69 70#include <openssl/err.h> 71 72#include "ec_lcl.h" 73 74#ifndef OPENSSL_NO_EC2M 75 76/*- 77 * Calculates and sets the affine coordinates of an EC_POINT from the given 78 * compressed coordinates. Uses algorithm 2.3.4 of SEC 1. 79 * Note that the simple implementation only uses affine coordinates. 80 * 81 * The method is from the following publication: 82 * 83 * Harper, Menezes, Vanstone: 84 * "Public-Key Cryptosystems with Very Small Key Lengths", 85 * EUROCRYPT '92, Springer-Verlag LNCS 658, 86 * published February 1993 87 * 88 * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe 89 * the same method, but claim no priority date earlier than July 29, 1994 90 * (and additionally fail to cite the EUROCRYPT '92 publication as prior art). 91 */ 92int ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group, 93 EC_POINT *point, 94 const BIGNUM *x_, int y_bit, 95 BN_CTX *ctx) 96{ 97 BN_CTX *new_ctx = NULL; 98 BIGNUM *tmp, *x, *y, *z; 99 int ret = 0, z0; 100 101 /* clear error queue */ 102 ERR_clear_error(); 103 104 if (ctx == NULL) { 105 ctx = new_ctx = BN_CTX_new(); 106 if (ctx == NULL) 107 return 0; 108 } 109 110 y_bit = (y_bit != 0) ? 1 : 0; 111 112 BN_CTX_start(ctx); 113 tmp = BN_CTX_get(ctx); 114 x = BN_CTX_get(ctx); 115 y = BN_CTX_get(ctx); 116 z = BN_CTX_get(ctx); 117 if (z == NULL) 118 goto err; 119 120 if (!BN_GF2m_mod_arr(x, x_, group->poly)) 121 goto err; 122 if (BN_is_zero(x)) { 123 if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx)) 124 goto err; 125 } else { 126 if (!group->meth->field_sqr(group, tmp, x, ctx)) 127 goto err; 128 if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx)) 129 goto err; 130 if (!BN_GF2m_add(tmp, &group->a, tmp)) 131 goto err; 132 if (!BN_GF2m_add(tmp, x, tmp)) 133 goto err; 134 if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) { 135 unsigned long err = ERR_peek_last_error(); 136 137 if (ERR_GET_LIB(err) == ERR_LIB_BN 138 && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) { 139 ERR_clear_error(); 140 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, 141 EC_R_INVALID_COMPRESSED_POINT); 142 } else 143 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES, 144 ERR_R_BN_LIB); 145 goto err; 146 } 147 z0 = (BN_is_odd(z)) ? 1 : 0; 148 if (!group->meth->field_mul(group, y, x, z, ctx)) 149 goto err; 150 if (z0 != y_bit) { 151 if (!BN_GF2m_add(y, y, x)) 152 goto err; 153 } 154 } 155 156 if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) 157 goto err; 158 159 ret = 1; 160 161 err: 162 BN_CTX_end(ctx); 163 if (new_ctx != NULL) 164 BN_CTX_free(new_ctx); 165 return ret; 166} 167 168/* 169 * Converts an EC_POINT to an octet string. If buf is NULL, the encoded 170 * length will be returned. If the length len of buf is smaller than required 171 * an error will be returned. 172 */ 173size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 174 point_conversion_form_t form, 175 unsigned char *buf, size_t len, BN_CTX *ctx) 176{ 177 size_t ret; 178 BN_CTX *new_ctx = NULL; 179 int used_ctx = 0; 180 BIGNUM *x, *y, *yxi; 181 size_t field_len, i, skip; 182 183 if ((form != POINT_CONVERSION_COMPRESSED) 184 && (form != POINT_CONVERSION_UNCOMPRESSED) 185 && (form != POINT_CONVERSION_HYBRID)) { 186 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM); 187 goto err; 188 } 189 190 if (EC_POINT_is_at_infinity(group, point)) { 191 /* encodes to a single 0 octet */ 192 if (buf != NULL) { 193 if (len < 1) { 194 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 195 return 0; 196 } 197 buf[0] = 0; 198 } 199 return 1; 200 } 201 202 /* ret := required output buffer length */ 203 field_len = (EC_GROUP_get_degree(group) + 7) / 8; 204 ret = 205 (form == 206 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 207 208 /* if 'buf' is NULL, just return required length */ 209 if (buf != NULL) { 210 if (len < ret) { 211 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL); 212 goto err; 213 } 214 215 if (ctx == NULL) { 216 ctx = new_ctx = BN_CTX_new(); 217 if (ctx == NULL) 218 return 0; 219 } 220 221 BN_CTX_start(ctx); 222 used_ctx = 1; 223 x = BN_CTX_get(ctx); 224 y = BN_CTX_get(ctx); 225 yxi = BN_CTX_get(ctx); 226 if (yxi == NULL) 227 goto err; 228 229 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx)) 230 goto err; 231 232 buf[0] = form; 233 if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) { 234 if (!group->meth->field_div(group, yxi, y, x, ctx)) 235 goto err; 236 if (BN_is_odd(yxi)) 237 buf[0]++; 238 } 239 240 i = 1; 241 242 skip = field_len - BN_num_bytes(x); 243 if (skip > field_len) { 244 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 245 goto err; 246 } 247 while (skip > 0) { 248 buf[i++] = 0; 249 skip--; 250 } 251 skip = BN_bn2bin(x, buf + i); 252 i += skip; 253 if (i != 1 + field_len) { 254 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 255 goto err; 256 } 257 258 if (form == POINT_CONVERSION_UNCOMPRESSED 259 || form == POINT_CONVERSION_HYBRID) { 260 skip = field_len - BN_num_bytes(y); 261 if (skip > field_len) { 262 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 263 goto err; 264 } 265 while (skip > 0) { 266 buf[i++] = 0; 267 skip--; 268 } 269 skip = BN_bn2bin(y, buf + i); 270 i += skip; 271 } 272 273 if (i != ret) { 274 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR); 275 goto err; 276 } 277 } 278 279 if (used_ctx) 280 BN_CTX_end(ctx); 281 if (new_ctx != NULL) 282 BN_CTX_free(new_ctx); 283 return ret; 284 285 err: 286 if (used_ctx) 287 BN_CTX_end(ctx); 288 if (new_ctx != NULL) 289 BN_CTX_free(new_ctx); 290 return 0; 291} 292 293/* 294 * Converts an octet string representation to an EC_POINT. Note that the 295 * simple implementation only uses affine coordinates. 296 */ 297int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 298 const unsigned char *buf, size_t len, 299 BN_CTX *ctx) 300{ 301 point_conversion_form_t form; 302 int y_bit; 303 BN_CTX *new_ctx = NULL; 304 BIGNUM *x, *y, *yxi; 305 size_t field_len, enc_len; 306 int ret = 0; 307 308 if (len == 0) { 309 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL); 310 return 0; 311 } 312 form = buf[0]; 313 y_bit = form & 1; 314 form = form & ~1U; 315 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 316 && (form != POINT_CONVERSION_UNCOMPRESSED) 317 && (form != POINT_CONVERSION_HYBRID)) { 318 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 319 return 0; 320 } 321 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 322 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 323 return 0; 324 } 325 326 if (form == 0) { 327 if (len != 1) { 328 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 329 return 0; 330 } 331 332 return EC_POINT_set_to_infinity(group, point); 333 } 334 335 field_len = (EC_GROUP_get_degree(group) + 7) / 8; 336 enc_len = 337 (form == 338 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 339 340 if (len != enc_len) { 341 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 342 return 0; 343 } 344 345 if (ctx == NULL) { 346 ctx = new_ctx = BN_CTX_new(); 347 if (ctx == NULL) 348 return 0; 349 } 350 351 BN_CTX_start(ctx); 352 x = BN_CTX_get(ctx); 353 y = BN_CTX_get(ctx); 354 yxi = BN_CTX_get(ctx); 355 if (yxi == NULL) 356 goto err; 357 358 if (!BN_bin2bn(buf + 1, field_len, x)) 359 goto err; 360 if (BN_ucmp(x, &group->field) >= 0) { 361 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 362 goto err; 363 } 364 365 if (form == POINT_CONVERSION_COMPRESSED) { 366 if (!EC_POINT_set_compressed_coordinates_GF2m 367 (group, point, x, y_bit, ctx)) 368 goto err; 369 } else { 370 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 371 goto err; 372 if (BN_ucmp(y, &group->field) >= 0) { 373 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 374 goto err; 375 } 376 if (form == POINT_CONVERSION_HYBRID) { 377 if (!group->meth->field_div(group, yxi, y, x, ctx)) 378 goto err; 379 if (y_bit != BN_is_odd(yxi)) { 380 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING); 381 goto err; 382 } 383 } 384 385 if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx)) 386 goto err; 387 } 388 389 /* test required by X9.62 */ 390 if (EC_POINT_is_on_curve(group, point, ctx) <= 0) { 391 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE); 392 goto err; 393 } 394 395 ret = 1; 396 397 err: 398 BN_CTX_end(ctx); 399 if (new_ctx != NULL) 400 BN_CTX_free(new_ctx); 401 return ret; 402} 403#endif 404