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