1 /* $OpenBSD: ec2_oct.c,v 1.16 2021/05/03 14:42:45 tb Exp $ */ 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/opensslconf.h> 71 72 #include <openssl/err.h> 73 74 #include "ec_lcl.h" 75 76 #ifndef OPENSSL_NO_EC2M 77 78 /* Calculates and sets the affine coordinates of an EC_POINT from the given 79 * compressed coordinates. Uses algorithm 2.3.4 of SEC 1. 80 * Note that the simple implementation only uses affine coordinates. 81 * 82 * The method is from the following publication: 83 * 84 * Harper, Menezes, Vanstone: 85 * "Public-Key Cryptosystems with Very Small Key Lengths", 86 * EUROCRYPT '92, Springer-Verlag LNCS 658, 87 * published February 1993 88 * 89 * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe 90 * the same method, but claim no priority date earlier than July 29, 1994 91 * (and additionally fail to cite the EUROCRYPT '92 publication as prior art). 92 */ 93 int 94 ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point, 95 const BIGNUM *x_, int y_bit, 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 y_bit = (y_bit != 0) ? 1 : 0; 110 111 BN_CTX_start(ctx); 112 if ((tmp = BN_CTX_get(ctx)) == NULL) 113 goto err; 114 if ((x = BN_CTX_get(ctx)) == NULL) 115 goto err; 116 if ((y = BN_CTX_get(ctx)) == NULL) 117 goto err; 118 if ((z = BN_CTX_get(ctx)) == NULL) 119 goto err; 120 121 if (!BN_GF2m_mod_arr(x, x_, group->poly)) 122 goto err; 123 if (BN_is_zero(x)) { 124 if (y_bit != 0) { 125 ECerror(EC_R_INVALID_COMPRESSED_POINT); 126 goto err; 127 } 128 if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx)) 129 goto err; 130 } else { 131 if (!group->meth->field_sqr(group, tmp, x, ctx)) 132 goto err; 133 if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx)) 134 goto err; 135 if (!BN_GF2m_add(tmp, &group->a, tmp)) 136 goto err; 137 if (!BN_GF2m_add(tmp, x, tmp)) 138 goto err; 139 if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) { 140 unsigned long err = ERR_peek_last_error(); 141 142 if (ERR_GET_LIB(err) == ERR_LIB_BN && 143 ERR_GET_REASON(err) == BN_R_NO_SOLUTION) { 144 ERR_clear_error(); 145 ECerror(EC_R_INVALID_COMPRESSED_POINT); 146 } else 147 ECerror(ERR_R_BN_LIB); 148 goto err; 149 } 150 z0 = (BN_is_odd(z)) ? 1 : 0; 151 if (!group->meth->field_mul(group, y, x, z, ctx)) 152 goto err; 153 if (z0 != y_bit) { 154 if (!BN_GF2m_add(y, y, x)) 155 goto err; 156 } 157 } 158 159 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 160 goto err; 161 162 ret = 1; 163 164 err: 165 BN_CTX_end(ctx); 166 BN_CTX_free(new_ctx); 167 return ret; 168 } 169 170 171 /* Converts an EC_POINT to an octet string. 172 * If buf is NULL, the encoded length will be returned. 173 * If the length len of buf is smaller than required an error will be returned. 174 */ 175 size_t 176 ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 177 point_conversion_form_t form, 178 unsigned char *buf, size_t len, BN_CTX * ctx) 179 { 180 size_t ret; 181 BN_CTX *new_ctx = NULL; 182 int used_ctx = 0; 183 BIGNUM *x, *y, *yxi; 184 size_t field_len, i, skip; 185 186 if ((form != POINT_CONVERSION_COMPRESSED) 187 && (form != POINT_CONVERSION_UNCOMPRESSED) 188 && (form != POINT_CONVERSION_HYBRID)) { 189 ECerror(EC_R_INVALID_FORM); 190 goto err; 191 } 192 if (EC_POINT_is_at_infinity(group, point) > 0) { 193 /* encodes to a single 0 octet */ 194 if (buf != NULL) { 195 if (len < 1) { 196 ECerror(EC_R_BUFFER_TOO_SMALL); 197 return 0; 198 } 199 buf[0] = 0; 200 } 201 return 1; 202 } 203 /* ret := required output buffer length */ 204 field_len = (EC_GROUP_get_degree(group) + 7) / 8; 205 ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 206 1 + 2 * field_len; 207 208 /* if 'buf' is NULL, just return required length */ 209 if (buf != NULL) { 210 if (len < ret) { 211 ECerror(EC_R_BUFFER_TOO_SMALL); 212 goto err; 213 } 214 if (ctx == NULL) { 215 ctx = new_ctx = BN_CTX_new(); 216 if (ctx == NULL) 217 return 0; 218 } 219 BN_CTX_start(ctx); 220 used_ctx = 1; 221 if ((x = BN_CTX_get(ctx)) == NULL) 222 goto err; 223 if ((y = BN_CTX_get(ctx)) == NULL) 224 goto err; 225 if ((yxi = BN_CTX_get(ctx)) == NULL) 226 goto err; 227 228 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) 229 goto err; 230 231 buf[0] = form; 232 if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) { 233 if (!group->meth->field_div(group, yxi, y, x, ctx)) 234 goto err; 235 if (BN_is_odd(yxi)) 236 buf[0]++; 237 } 238 i = 1; 239 240 skip = field_len - BN_num_bytes(x); 241 if (skip > field_len) { 242 ECerror(ERR_R_INTERNAL_ERROR); 243 goto err; 244 } 245 while (skip > 0) { 246 buf[i++] = 0; 247 skip--; 248 } 249 skip = BN_bn2bin(x, buf + i); 250 i += skip; 251 if (i != 1 + field_len) { 252 ECerror(ERR_R_INTERNAL_ERROR); 253 goto err; 254 } 255 if (form == POINT_CONVERSION_UNCOMPRESSED || 256 form == POINT_CONVERSION_HYBRID) { 257 skip = field_len - BN_num_bytes(y); 258 if (skip > field_len) { 259 ECerror(ERR_R_INTERNAL_ERROR); 260 goto err; 261 } 262 while (skip > 0) { 263 buf[i++] = 0; 264 skip--; 265 } 266 skip = BN_bn2bin(y, buf + i); 267 i += skip; 268 } 269 if (i != ret) { 270 ECerror(ERR_R_INTERNAL_ERROR); 271 goto err; 272 } 273 } 274 if (used_ctx) 275 BN_CTX_end(ctx); 276 BN_CTX_free(new_ctx); 277 return ret; 278 279 err: 280 if (used_ctx) 281 BN_CTX_end(ctx); 282 BN_CTX_free(new_ctx); 283 return 0; 284 } 285 286 287 /* 288 * Converts an octet string representation to an EC_POINT. 289 * Note that the simple implementation only uses affine coordinates. 290 */ 291 int 292 ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 293 const unsigned char *buf, size_t len, BN_CTX *ctx) 294 { 295 point_conversion_form_t form; 296 int y_bit; 297 BN_CTX *new_ctx = NULL; 298 BIGNUM *x, *y, *yxi; 299 size_t field_len, enc_len; 300 int ret = 0; 301 302 if (len == 0) { 303 ECerror(EC_R_BUFFER_TOO_SMALL); 304 return 0; 305 } 306 307 /* 308 * The first octet is the point conversion octet PC, see X9.62, page 4 309 * and section 4.4.2. It must be: 310 * 0x00 for the point at infinity 311 * 0x02 or 0x03 for compressed form 312 * 0x04 for uncompressed form 313 * 0x06 or 0x07 for hybrid form. 314 * For compressed or hybrid forms, we store the last bit of buf[0] as 315 * y_bit and clear it from buf[0] so as to obtain a POINT_CONVERSION_*. 316 * We error if buf[0] contains any but the above values. 317 */ 318 y_bit = buf[0] & 1; 319 form = buf[0] & ~1U; 320 321 if (form != 0 && form != POINT_CONVERSION_COMPRESSED && 322 form != POINT_CONVERSION_UNCOMPRESSED && 323 form != POINT_CONVERSION_HYBRID) { 324 ECerror(EC_R_INVALID_ENCODING); 325 return 0; 326 } 327 if (form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) { 328 if (y_bit != 0) { 329 ECerror(EC_R_INVALID_ENCODING); 330 return 0; 331 } 332 } 333 334 /* The point at infinity is represented by a single zero octet. */ 335 if (form == 0) { 336 if (len != 1) { 337 ECerror(EC_R_INVALID_ENCODING); 338 return 0; 339 } 340 return EC_POINT_set_to_infinity(group, point); 341 } 342 343 field_len = (EC_GROUP_get_degree(group) + 7) / 8; 344 enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 345 1 + 2 * field_len; 346 347 if (len != enc_len) { 348 ECerror(EC_R_INVALID_ENCODING); 349 return 0; 350 } 351 352 if (ctx == NULL) { 353 ctx = new_ctx = BN_CTX_new(); 354 if (ctx == NULL) 355 return 0; 356 } 357 BN_CTX_start(ctx); 358 if ((x = BN_CTX_get(ctx)) == NULL) 359 goto err; 360 if ((y = BN_CTX_get(ctx)) == NULL) 361 goto err; 362 if ((yxi = BN_CTX_get(ctx)) == NULL) 363 goto err; 364 365 if (!BN_bin2bn(buf + 1, field_len, x)) 366 goto err; 367 if (BN_ucmp(x, &group->field) >= 0) { 368 ECerror(EC_R_INVALID_ENCODING); 369 goto err; 370 } 371 if (form == POINT_CONVERSION_COMPRESSED) { 372 /* 373 * EC_POINT_set_compressed_coordinates checks that the 374 * point is on the curve as required by X9.62. 375 */ 376 if (!EC_POINT_set_compressed_coordinates(group, point, x, y_bit, ctx)) 377 goto err; 378 } else { 379 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 380 goto err; 381 if (BN_ucmp(y, &group->field) >= 0) { 382 ECerror(EC_R_INVALID_ENCODING); 383 goto err; 384 } 385 if (form == POINT_CONVERSION_HYBRID) { 386 /* 387 * Check that the form in the encoding was set 388 * correctly according to X9.62 4.4.2.a, 4(c), 389 * see also first paragraph of X9.62 4.4.1.b. 390 */ 391 if (BN_is_zero(x)) { 392 if (y_bit != 0) { 393 ECerror(EC_R_INVALID_ENCODING); 394 goto err; 395 } 396 } else { 397 if (!group->meth->field_div(group, yxi, y, x, 398 ctx)) 399 goto err; 400 if (y_bit != BN_is_odd(yxi)) { 401 ECerror(EC_R_INVALID_ENCODING); 402 goto err; 403 } 404 } 405 } 406 /* 407 * EC_POINT_set_affine_coordinates checks that the 408 * point is on the curve as required by X9.62. 409 */ 410 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 411 goto err; 412 } 413 414 ret = 1; 415 416 err: 417 BN_CTX_end(ctx); 418 BN_CTX_free(new_ctx); 419 return ret; 420 } 421 #endif 422