1 /* Originally written by Bodo Moeller for the OpenSSL project. 2 * ==================================================================== 3 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in 14 * the documentation and/or other materials provided with the 15 * distribution. 16 * 17 * 3. All advertising materials mentioning features or use of this 18 * software must display the following acknowledgment: 19 * "This product includes software developed by the OpenSSL Project 20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 21 * 22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23 * endorse or promote products derived from this software without 24 * prior written permission. For written permission, please contact 25 * openssl-core (at) openssl.org. 26 * 27 * 5. Products derived from this software may not be called "OpenSSL" 28 * nor may "OpenSSL" appear in their names without prior written 29 * permission of the OpenSSL Project. 30 * 31 * 6. Redistributions of any form whatsoever must retain the following 32 * acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 35 * 36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47 * OF THE POSSIBILITY OF SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This product includes cryptographic software written by Eric Young 51 * (eay (at) cryptsoft.com). This product includes software written by Tim 52 * Hudson (tjh (at) cryptsoft.com). 53 * 54 */ 55 /* ==================================================================== 56 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 57 * 58 * Portions of the attached software ("Contribution") are developed by 59 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. 60 * 61 * The Contribution is licensed pursuant to the OpenSSL open source 62 * license provided above. 63 * 64 * The elliptic curve binary polynomial software is originally written by 65 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems 66 * Laboratories. */ 67 68 #include <openssl/ec.h> 69 70 #include <openssl/bn.h> 71 #include <openssl/bytestring.h> 72 #include <openssl/err.h> 73 74 #include "internal.h" 75 76 77 static size_t ec_GFp_simple_point2oct(const EC_GROUP *group, 78 const EC_POINT *point, 79 point_conversion_form_t form, 80 uint8_t *buf, size_t len, BN_CTX *ctx) { 81 size_t ret; 82 BN_CTX *new_ctx = NULL; 83 int used_ctx = 0; 84 BIGNUM *x, *y; 85 size_t field_len, i; 86 87 if ((form != POINT_CONVERSION_COMPRESSED) && 88 (form != POINT_CONVERSION_UNCOMPRESSED)) { 89 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_FORM); 90 goto err; 91 } 92 93 if (EC_POINT_is_at_infinity(group, point)) { 94 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 95 goto err; 96 } 97 98 /* ret := required output buffer length */ 99 field_len = BN_num_bytes(&group->field); 100 ret = 101 (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 102 103 /* if 'buf' is NULL, just return required length */ 104 if (buf != NULL) { 105 if (len < ret) { 106 OPENSSL_PUT_ERROR(EC, EC_R_BUFFER_TOO_SMALL); 107 goto err; 108 } 109 110 if (ctx == NULL) { 111 ctx = new_ctx = BN_CTX_new(); 112 if (ctx == NULL) { 113 goto err; 114 } 115 } 116 117 BN_CTX_start(ctx); 118 used_ctx = 1; 119 x = BN_CTX_get(ctx); 120 y = BN_CTX_get(ctx); 121 if (y == NULL) { 122 goto err; 123 } 124 125 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) { 126 goto err; 127 } 128 129 if ((form == POINT_CONVERSION_COMPRESSED) && 130 BN_is_odd(y)) { 131 buf[0] = form + 1; 132 } else { 133 buf[0] = form; 134 } 135 i = 1; 136 137 if (!BN_bn2bin_padded(buf + i, field_len, x)) { 138 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); 139 goto err; 140 } 141 i += field_len; 142 143 if (form == POINT_CONVERSION_UNCOMPRESSED) { 144 if (!BN_bn2bin_padded(buf + i, field_len, y)) { 145 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); 146 goto err; 147 } 148 i += field_len; 149 } 150 151 if (i != ret) { 152 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); 153 goto err; 154 } 155 } 156 157 if (used_ctx) { 158 BN_CTX_end(ctx); 159 } 160 BN_CTX_free(new_ctx); 161 return ret; 162 163 err: 164 if (used_ctx) { 165 BN_CTX_end(ctx); 166 } 167 BN_CTX_free(new_ctx); 168 return 0; 169 } 170 171 172 static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 173 const uint8_t *buf, size_t len, 174 BN_CTX *ctx) { 175 point_conversion_form_t form; 176 int y_bit; 177 BN_CTX *new_ctx = NULL; 178 BIGNUM *x, *y; 179 size_t field_len, enc_len; 180 int ret = 0; 181 182 if (len == 0) { 183 OPENSSL_PUT_ERROR(EC, EC_R_BUFFER_TOO_SMALL); 184 return 0; 185 } 186 form = buf[0]; 187 y_bit = form & 1; 188 form = form & ~1U; 189 if ((form != POINT_CONVERSION_COMPRESSED && 190 form != POINT_CONVERSION_UNCOMPRESSED) || 191 (form == POINT_CONVERSION_UNCOMPRESSED && y_bit)) { 192 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); 193 return 0; 194 } 195 196 field_len = BN_num_bytes(&group->field); 197 enc_len = 198 (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 199 200 if (len != enc_len) { 201 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); 202 return 0; 203 } 204 205 if (ctx == NULL) { 206 ctx = new_ctx = BN_CTX_new(); 207 if (ctx == NULL) { 208 return 0; 209 } 210 } 211 212 BN_CTX_start(ctx); 213 x = BN_CTX_get(ctx); 214 y = BN_CTX_get(ctx); 215 if (x == NULL || y == NULL) { 216 goto err; 217 } 218 219 if (!BN_bin2bn(buf + 1, field_len, x)) { 220 goto err; 221 } 222 if (BN_ucmp(x, &group->field) >= 0) { 223 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); 224 goto err; 225 } 226 227 if (form == POINT_CONVERSION_COMPRESSED) { 228 if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) { 229 goto err; 230 } 231 } else { 232 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) { 233 goto err; 234 } 235 if (BN_ucmp(y, &group->field) >= 0) { 236 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_ENCODING); 237 goto err; 238 } 239 240 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) { 241 goto err; 242 } 243 } 244 245 ret = 1; 246 247 err: 248 BN_CTX_end(ctx); 249 BN_CTX_free(new_ctx); 250 return ret; 251 } 252 253 int EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point, 254 const uint8_t *buf, size_t len, BN_CTX *ctx) { 255 if (group->meth != point->meth) { 256 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); 257 return 0; 258 } 259 return ec_GFp_simple_oct2point(group, point, buf, len, ctx); 260 } 261 262 size_t EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point, 263 point_conversion_form_t form, uint8_t *buf, 264 size_t len, BN_CTX *ctx) { 265 if (group->meth != point->meth) { 266 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); 267 return 0; 268 } 269 return ec_GFp_simple_point2oct(group, point, form, buf, len, ctx); 270 } 271 272 int EC_POINT_point2cbb(CBB *out, const EC_GROUP *group, const EC_POINT *point, 273 point_conversion_form_t form, BN_CTX *ctx) { 274 size_t len = EC_POINT_point2oct(group, point, form, NULL, 0, ctx); 275 if (len == 0) { 276 return 0; 277 } 278 uint8_t *p; 279 return CBB_add_space(out, &p, len) && 280 EC_POINT_point2oct(group, point, form, p, len, ctx) == len; 281 } 282 283 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, 284 EC_POINT *point, const BIGNUM *x, 285 int y_bit, BN_CTX *ctx) { 286 if (BN_is_negative(x) || BN_cmp(x, &group->field) >= 0) { 287 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSED_POINT); 288 return 0; 289 } 290 291 BN_CTX *new_ctx = NULL; 292 BIGNUM *tmp1, *tmp2, *y; 293 int ret = 0; 294 295 ERR_clear_error(); 296 297 if (ctx == NULL) { 298 ctx = new_ctx = BN_CTX_new(); 299 if (ctx == NULL) { 300 return 0; 301 } 302 } 303 304 y_bit = (y_bit != 0); 305 306 BN_CTX_start(ctx); 307 tmp1 = BN_CTX_get(ctx); 308 tmp2 = BN_CTX_get(ctx); 309 y = BN_CTX_get(ctx); 310 if (y == NULL) { 311 goto err; 312 } 313 314 /* Recover y. We have a Weierstrass equation 315 * y^2 = x^3 + a*x + b, 316 * so y is one of the square roots of x^3 + a*x + b. */ 317 318 /* tmp1 := x^3 */ 319 if (group->meth->field_decode == 0) { 320 /* field_{sqr,mul} work on standard representation */ 321 if (!group->meth->field_sqr(group, tmp2, x, ctx) || 322 !group->meth->field_mul(group, tmp1, tmp2, x, ctx)) { 323 goto err; 324 } 325 } else { 326 if (!BN_mod_sqr(tmp2, x, &group->field, ctx) || 327 !BN_mod_mul(tmp1, tmp2, x, &group->field, ctx)) { 328 goto err; 329 } 330 } 331 332 /* tmp1 := tmp1 + a*x */ 333 if (group->a_is_minus3) { 334 if (!BN_mod_lshift1_quick(tmp2, x, &group->field) || 335 !BN_mod_add_quick(tmp2, tmp2, x, &group->field) || 336 !BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) { 337 goto err; 338 } 339 } else { 340 if (group->meth->field_decode) { 341 if (!group->meth->field_decode(group, tmp2, &group->a, ctx) || 342 !BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) { 343 goto err; 344 } 345 } else { 346 /* field_mul works on standard representation */ 347 if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) { 348 goto err; 349 } 350 } 351 352 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) { 353 goto err; 354 } 355 } 356 357 /* tmp1 := tmp1 + b */ 358 if (group->meth->field_decode) { 359 if (!group->meth->field_decode(group, tmp2, &group->b, ctx) || 360 !BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) { 361 goto err; 362 } 363 } else { 364 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) { 365 goto err; 366 } 367 } 368 369 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { 370 unsigned long err = ERR_peek_last_error(); 371 372 if (ERR_GET_LIB(err) == ERR_LIB_BN && 373 ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { 374 ERR_clear_error(); 375 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSED_POINT); 376 } else { 377 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); 378 } 379 goto err; 380 } 381 382 if (y_bit != BN_is_odd(y)) { 383 if (BN_is_zero(y)) { 384 OPENSSL_PUT_ERROR(EC, EC_R_INVALID_COMPRESSION_BIT); 385 goto err; 386 } 387 if (!BN_usub(y, &group->field, y)) { 388 goto err; 389 } 390 } 391 if (y_bit != BN_is_odd(y)) { 392 OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR); 393 goto err; 394 } 395 396 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) { 397 goto err; 398 } 399 400 ret = 1; 401 402 err: 403 BN_CTX_end(ctx); 404 BN_CTX_free(new_ctx); 405 return ret; 406 } 407 408 int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group, 409 EC_POINT *point, const BIGNUM *x, 410 int y_bit, BN_CTX *ctx) { 411 if (group->meth != point->meth) { 412 OPENSSL_PUT_ERROR(EC, EC_R_INCOMPATIBLE_OBJECTS); 413 return 0; 414 } 415 return ec_GFp_simple_set_compressed_coordinates(group, point, x, y_bit, ctx); 416 } 417
