crypto/ec/ecp_oct.c

   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_lcl.h"
  15
  16 int 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
 154 size_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
 269 int 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 }