1 /* 2 * Copyright 2011-2021 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved 4 * 5 * Licensed under the Apache License 2.0 (the "License"). You may not use 6 * this file except in compliance with the License. You can obtain a copy 7 * in the file LICENSE in the source distribution or at 8 * https://www.openssl.org/source/license.html 9 */ 10 11 /* 12 * ECDSA low level APIs are deprecated for public use, but still ok for 13 * internal use. 14 */ 15 #include "internal/deprecated.h" 16 17 #include <openssl/err.h> 18 #include <openssl/symhacks.h> 19 20 #include "ec_local.h" 21 22 int ossl_ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group, 23 EC_POINT *point, 24 const BIGNUM *x_, int y_bit, 25 BN_CTX *ctx) 26 { 27 BN_CTX *new_ctx = NULL; 28 BIGNUM *tmp1, *tmp2, *x, *y; 29 int ret = 0; 30 31 if (ctx == NULL) { 32 ctx = new_ctx = BN_CTX_new_ex(group->libctx); 33 if (ctx == NULL) 34 return 0; 35 } 36 37 y_bit = (y_bit != 0); 38 39 BN_CTX_start(ctx); 40 tmp1 = BN_CTX_get(ctx); 41 tmp2 = BN_CTX_get(ctx); 42 x = BN_CTX_get(ctx); 43 y = BN_CTX_get(ctx); 44 if (y == NULL) 45 goto err; 46 47 /*- 48 * Recover y. We have a Weierstrass equation 49 * y^2 = x^3 + a*x + b, 50 * so y is one of the square roots of x^3 + a*x + b. 51 */ 52 53 /* tmp1 := x^3 */ 54 if (!BN_nnmod(x, x_, group->field, ctx)) 55 goto err; 56 if (group->meth->field_decode == 0) { 57 /* field_{sqr,mul} work on standard representation */ 58 if (!group->meth->field_sqr(group, tmp2, x_, ctx)) 59 goto err; 60 if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) 61 goto err; 62 } else { 63 if (!BN_mod_sqr(tmp2, x_, group->field, ctx)) 64 goto err; 65 if (!BN_mod_mul(tmp1, tmp2, x_, group->field, ctx)) 66 goto err; 67 } 68 69 /* tmp1 := tmp1 + a*x */ 70 if (group->a_is_minus3) { 71 if (!BN_mod_lshift1_quick(tmp2, x, group->field)) 72 goto err; 73 if (!BN_mod_add_quick(tmp2, tmp2, x, group->field)) 74 goto err; 75 if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, group->field)) 76 goto err; 77 } else { 78 if (group->meth->field_decode) { 79 if (!group->meth->field_decode(group, tmp2, group->a, ctx)) 80 goto err; 81 if (!BN_mod_mul(tmp2, tmp2, x, group->field, ctx)) 82 goto err; 83 } else { 84 /* field_mul works on standard representation */ 85 if (!group->meth->field_mul(group, tmp2, group->a, x, ctx)) 86 goto err; 87 } 88 89 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field)) 90 goto err; 91 } 92 93 /* tmp1 := tmp1 + b */ 94 if (group->meth->field_decode) { 95 if (!group->meth->field_decode(group, tmp2, group->b, ctx)) 96 goto err; 97 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field)) 98 goto err; 99 } else { 100 if (!BN_mod_add_quick(tmp1, tmp1, group->b, group->field)) 101 goto err; 102 } 103 104 ERR_set_mark(); 105 if (!BN_mod_sqrt(y, tmp1, group->field, ctx)) { 106 #ifndef FIPS_MODULE 107 unsigned long err = ERR_peek_last_error(); 108 109 if (ERR_GET_LIB(err) == ERR_LIB_BN 110 && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) { 111 ERR_pop_to_mark(); 112 ERR_raise(ERR_LIB_EC, EC_R_INVALID_COMPRESSED_POINT); 113 } else 114 #endif 115 { 116 ERR_clear_last_mark(); 117 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 118 } 119 goto err; 120 } 121 ERR_clear_last_mark(); 122 123 if (y_bit != BN_is_odd(y)) { 124 if (BN_is_zero(y)) { 125 int kron; 126 127 kron = BN_kronecker(x, group->field, ctx); 128 if (kron == -2) 129 goto err; 130 131 if (kron == 1) 132 ERR_raise(ERR_LIB_EC, EC_R_INVALID_COMPRESSION_BIT); 133 else 134 /* 135 * BN_mod_sqrt() should have caught this error (not a square) 136 */ 137 ERR_raise(ERR_LIB_EC, EC_R_INVALID_COMPRESSED_POINT); 138 goto err; 139 } 140 if (!BN_usub(y, group->field, y)) 141 goto err; 142 } 143 if (y_bit != BN_is_odd(y)) { 144 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 145 goto err; 146 } 147 148 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 149 goto err; 150 151 ret = 1; 152 153 err: 154 BN_CTX_end(ctx); 155 BN_CTX_free(new_ctx); 156 return ret; 157 } 158 159 size_t ossl_ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point, 160 point_conversion_form_t form, 161 unsigned char *buf, size_t len, BN_CTX *ctx) 162 { 163 size_t ret; 164 BN_CTX *new_ctx = NULL; 165 int used_ctx = 0; 166 BIGNUM *x, *y; 167 size_t field_len, i, skip; 168 169 if ((form != POINT_CONVERSION_COMPRESSED) 170 && (form != POINT_CONVERSION_UNCOMPRESSED) 171 && (form != POINT_CONVERSION_HYBRID)) { 172 ERR_raise(ERR_LIB_EC, EC_R_INVALID_FORM); 173 goto err; 174 } 175 176 if (EC_POINT_is_at_infinity(group, point)) { 177 /* encodes to a single 0 octet */ 178 if (buf != NULL) { 179 if (len < 1) { 180 ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL); 181 return 0; 182 } 183 buf[0] = 0; 184 } 185 return 1; 186 } 187 188 /* ret := required output buffer length */ 189 field_len = BN_num_bytes(group->field); 190 ret = 191 (form == 192 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 193 194 /* if 'buf' is NULL, just return required length */ 195 if (buf != NULL) { 196 if (len < ret) { 197 ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL); 198 goto err; 199 } 200 201 if (ctx == NULL) { 202 ctx = new_ctx = BN_CTX_new_ex(group->libctx); 203 if (ctx == NULL) 204 return 0; 205 } 206 207 BN_CTX_start(ctx); 208 used_ctx = 1; 209 x = BN_CTX_get(ctx); 210 y = BN_CTX_get(ctx); 211 if (y == NULL) 212 goto err; 213 214 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx)) 215 goto err; 216 217 if ((form == POINT_CONVERSION_COMPRESSED 218 || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y)) 219 buf[0] = form + 1; 220 else 221 buf[0] = form; 222 223 i = 1; 224 225 skip = field_len - BN_num_bytes(x); 226 if (skip > field_len) { 227 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 228 goto err; 229 } 230 while (skip > 0) { 231 buf[i++] = 0; 232 skip--; 233 } 234 skip = BN_bn2bin(x, buf + i); 235 i += skip; 236 if (i != 1 + field_len) { 237 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 238 goto err; 239 } 240 241 if (form == POINT_CONVERSION_UNCOMPRESSED 242 || form == POINT_CONVERSION_HYBRID) { 243 skip = field_len - BN_num_bytes(y); 244 if (skip > field_len) { 245 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 246 goto err; 247 } 248 while (skip > 0) { 249 buf[i++] = 0; 250 skip--; 251 } 252 skip = BN_bn2bin(y, buf + i); 253 i += skip; 254 } 255 256 if (i != ret) { 257 ERR_raise(ERR_LIB_EC, ERR_R_INTERNAL_ERROR); 258 goto err; 259 } 260 } 261 262 if (used_ctx) 263 BN_CTX_end(ctx); 264 BN_CTX_free(new_ctx); 265 return ret; 266 267 err: 268 if (used_ctx) 269 BN_CTX_end(ctx); 270 BN_CTX_free(new_ctx); 271 return 0; 272 } 273 274 int ossl_ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point, 275 const unsigned char *buf, size_t len, 276 BN_CTX *ctx) 277 { 278 point_conversion_form_t form; 279 int y_bit; 280 BN_CTX *new_ctx = NULL; 281 BIGNUM *x, *y; 282 size_t field_len, enc_len; 283 int ret = 0; 284 285 if (len == 0) { 286 ERR_raise(ERR_LIB_EC, EC_R_BUFFER_TOO_SMALL); 287 return 0; 288 } 289 form = buf[0]; 290 y_bit = form & 1; 291 form = form & ~1U; 292 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) 293 && (form != POINT_CONVERSION_UNCOMPRESSED) 294 && (form != POINT_CONVERSION_HYBRID)) { 295 ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING); 296 return 0; 297 } 298 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) { 299 ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING); 300 return 0; 301 } 302 303 if (form == 0) { 304 if (len != 1) { 305 ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING); 306 return 0; 307 } 308 309 return EC_POINT_set_to_infinity(group, point); 310 } 311 312 field_len = BN_num_bytes(group->field); 313 enc_len = 314 (form == 315 POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len; 316 317 if (len != enc_len) { 318 ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING); 319 return 0; 320 } 321 322 if (ctx == NULL) { 323 ctx = new_ctx = BN_CTX_new_ex(group->libctx); 324 if (ctx == NULL) 325 return 0; 326 } 327 328 BN_CTX_start(ctx); 329 x = BN_CTX_get(ctx); 330 y = BN_CTX_get(ctx); 331 if (y == NULL) 332 goto err; 333 334 if (!BN_bin2bn(buf + 1, field_len, x)) 335 goto err; 336 if (BN_ucmp(x, group->field) >= 0) { 337 ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING); 338 goto err; 339 } 340 341 if (form == POINT_CONVERSION_COMPRESSED) { 342 if (!EC_POINT_set_compressed_coordinates(group, point, x, y_bit, ctx)) 343 goto err; 344 } else { 345 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) 346 goto err; 347 if (BN_ucmp(y, group->field) >= 0) { 348 ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING); 349 goto err; 350 } 351 if (form == POINT_CONVERSION_HYBRID) { 352 if (y_bit != BN_is_odd(y)) { 353 ERR_raise(ERR_LIB_EC, EC_R_INVALID_ENCODING); 354 goto err; 355 } 356 } 357 358 /* 359 * EC_POINT_set_affine_coordinates is responsible for checking that 360 * the point is on the curve. 361 */ 362 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx)) 363 goto err; 364 } 365 366 ret = 1; 367 368 err: 369 BN_CTX_end(ctx); 370 BN_CTX_free(new_ctx); 371 return ret; 372 } 373