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