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