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