1/* $OpenBSD: ecp_oct.c,v 1.21 2023/04/18 18:29:32 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 BIGNUM *tmp1, *tmp2, *x, *y; 74 int ret = 0; 75 76 /* clear error queue */ 77 ERR_clear_error(); 78 79 y_bit = (y_bit != 0); 80 81 BN_CTX_start(ctx); 82 83 if ((tmp1 = BN_CTX_get(ctx)) == NULL) 84 goto err; 85 if ((tmp2 = BN_CTX_get(ctx)) == NULL) 86 goto err; 87 if ((x = BN_CTX_get(ctx)) == NULL) 88 goto err; 89 if ((y = BN_CTX_get(ctx)) == NULL) 90 goto err; 91 92 /* 93 * Recover y. We have a Weierstrass equation y^2 = x^3 + a*x + b, so 94 * y is one of the square roots of x^3 + a*x + b. 95 */ 96 97 /* tmp1 := x^3 */ 98 if (!BN_nnmod(x, x_, &group->field, ctx)) 99 goto err; 100 if (group->meth->field_decode == NULL) { 101 /* field_{sqr,mul} work on standard representation */ 102 if (!group->meth->field_sqr(group, tmp2, x_, ctx)) 103 goto err; 104 if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) 105 goto err; 106 } else { 107 if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) 108 goto err; 109 if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) 110 goto err; 111 } 112 113 /* tmp1 := tmp1 + a*x */ 114 if (group->a_is_minus3) { 115 if (!BN_mod_lshift1_quick(tmp2, x, &group->field)) 116 goto err; 117 if (!BN_mod_add_quick(tmp2, tmp2, x, &group->field)) 118 goto err; 119 if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) 120 goto err; 121 } else { 122 if (group->meth->field_decode) { 123 if (!group->meth->field_decode(group, tmp2, &group->a, ctx)) 124 goto err; 125 if (!BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) 126 goto err; 127 } else { 128 /* field_mul works on standard representation */ 129 if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) 130 goto err; 131 } 132 133 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 134 goto err; 135 } 136 137 /* tmp1 := tmp1 + b */ 138 if (group->meth->field_decode != NULL) { 139 if (!group->meth->field_decode(group, tmp2, &group->b, ctx)) 140 goto err; 141 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) 142 goto err; 143 } else { 144 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) 145 goto err; 146 } 147 148 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) { 149 unsigned long err = ERR_peek_last_error(); 150 151 if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { 152 ERR_clear_error(); 153 ECerror(EC_R_INVALID_COMPRESSED_POINT); 154 } else 155 ECerror(ERR_R_BN_LIB); 156 goto err; 157 } 158 if (y_bit != BN_is_odd(y)) { 159 if (BN_is_zero(y)) { 160 ECerror(EC_R_INVALID_COMPRESSION_BIT); 161 goto err; 162 } 163 if (!BN_usub(y, &group->field, y)) 164 goto err; 165 if (y_bit != BN_is_odd(y)) { 166 ECerror(ERR_R_INTERNAL_ERROR); 167 goto err; 168 } 169 } 170 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 171 goto err; 172 173 ret = 1; 174 175 err: 176 BN_CTX_end(ctx); 177 178 return ret; 179} 180 181size_t 182ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 183 point_conversion_form_t form, unsigned char *buf, size_t len, BN_CTX *ctx) 184{ 185 BIGNUM *x, *y; 186 size_t field_len, i, skip; 187 size_t ret = 0; 188 189 if (form != POINT_CONVERSION_COMPRESSED && 190 form != POINT_CONVERSION_UNCOMPRESSED && 191 form != POINT_CONVERSION_HYBRID) { 192 ECerror(EC_R_INVALID_FORM); 193 return 0; 194 } 195 196 if (EC_POINT_is_at_infinity(group, point) > 0) { 197 /* encodes to a single 0 octet */ 198 if (buf != NULL) { 199 if (len < 1) { 200 ECerror(EC_R_BUFFER_TOO_SMALL); 201 return 0; 202 } 203 buf[0] = 0; 204 } 205 return 1; 206 } 207 208 /* ret := required output buffer length */ 209 field_len = BN_num_bytes(&group->field); 210 ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 211 212 BN_CTX_start(ctx); 213 214 /* if 'buf' is NULL, just return required length */ 215 if (buf != NULL) { 216 if (len < ret) { 217 ECerror(EC_R_BUFFER_TOO_SMALL); 218 goto err; 219 } 220 221 if ((x = BN_CTX_get(ctx)) == NULL) 222 goto err; 223 if ((y = BN_CTX_get(ctx)) == NULL) 224 goto err; 225 226 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) 227 goto err; 228 229 if ((form == POINT_CONVERSION_COMPRESSED || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) 230 buf[0] = form + 1; 231 else 232 buf[0] = form; 233 234 i = 1; 235 236 skip = field_len - BN_num_bytes(x); 237 if (skip > field_len) { 238 ECerror(ERR_R_INTERNAL_ERROR); 239 goto err; 240 } 241 while (skip > 0) { 242 buf[i++] = 0; 243 skip--; 244 } 245 skip = BN_bn2bin(x, buf + i); 246 i += skip; 247 if (i != 1 + field_len) { 248 ECerror(ERR_R_INTERNAL_ERROR); 249 goto err; 250 } 251 if (form == POINT_CONVERSION_UNCOMPRESSED || form == POINT_CONVERSION_HYBRID) { 252 skip = field_len - BN_num_bytes(y); 253 if (skip > field_len) { 254 ECerror(ERR_R_INTERNAL_ERROR); 255 goto err; 256 } 257 while (skip > 0) { 258 buf[i++] = 0; 259 skip--; 260 } 261 skip = BN_bn2bin(y, buf + i); 262 i += skip; 263 } 264 if (i != ret) { 265 ECerror(ERR_R_INTERNAL_ERROR); 266 goto err; 267 } 268 } 269 270 err: 271 BN_CTX_end(ctx); 272 273 return ret; 274} 275 276int 277ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 278 const unsigned char *buf, size_t len, BN_CTX *ctx) 279{ 280 point_conversion_form_t form; 281 int y_bit; 282 BIGNUM *x, *y; 283 size_t field_len, enc_len; 284 int ret = 0; 285 286 if (len == 0) { 287 ECerror(EC_R_BUFFER_TOO_SMALL); 288 return 0; 289 } 290 form = buf[0]; 291 y_bit = form & 1; 292 form = form & ~1U; 293 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 294 && (form != POINT_CONVERSION_UNCOMPRESSED) 295 && (form != POINT_CONVERSION_HYBRID)) { 296 ECerror(EC_R_INVALID_ENCODING); 297 return 0; 298 } 299 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 300 ECerror(EC_R_INVALID_ENCODING); 301 return 0; 302 } 303 if (form == 0) { 304 if (len != 1) { 305 ECerror(EC_R_INVALID_ENCODING); 306 return 0; 307 } 308 return EC_POINT_set_to_infinity(group, point); 309 } 310 field_len = BN_num_bytes(&group->field); 311 enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 312 313 if (len != enc_len) { 314 ECerror(EC_R_INVALID_ENCODING); 315 return 0; 316 } 317 318 BN_CTX_start(ctx); 319 320 if ((x = BN_CTX_get(ctx)) == NULL) 321 goto err; 322 if ((y = BN_CTX_get(ctx)) == NULL) 323 goto err; 324 325 if (!BN_bin2bn(buf + 1, field_len, x)) 326 goto err; 327 if (BN_ucmp(x, &group->field) >= 0) { 328 ECerror(EC_R_INVALID_ENCODING); 329 goto err; 330 } 331 if (form == POINT_CONVERSION_COMPRESSED) { 332 /* 333 * EC_POINT_set_compressed_coordinates checks that the point 334 * is on the curve as required by X9.62. 335 */ 336 if (!EC_POINT_set_compressed_coordinates(group, point, x, y_bit, ctx)) 337 goto err; 338 } else { 339 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 340 goto err; 341 if (BN_ucmp(y, &group->field) >= 0) { 342 ECerror(EC_R_INVALID_ENCODING); 343 goto err; 344 } 345 if (form == POINT_CONVERSION_HYBRID) { 346 if (y_bit != BN_is_odd(y)) { 347 ECerror(EC_R_INVALID_ENCODING); 348 goto err; 349 } 350 } 351 /* 352 * EC_POINT_set_affine_coordinates checks that the point is 353 * on the curve as required by X9.62. 354 */ 355 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 356 goto err; 357 } 358 359 ret = 1; 360 361 err: 362 BN_CTX_end(ctx); 363 364 return ret; 365} 366