crypto/ec/ecp_oct.c

   1 /*
   2  * Copyright 2011-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 /* ====================================================================
  11  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  12  * Portions of this software developed by SUN MICROSYSTEMS, INC.,
  13  * and contributed to the OpenSSL project.
  14  */
  15
  16 #include <openssl/err.h>
  17 #include <openssl/symhacks.h>
  18
  19 #include "ec_lcl.h"
  20
  21 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
  22                                              EC_POINT *point,
  23                                              const BIGNUM *x_, int y_bit,
  24                                              BN_CTX *ctx)
  25 {
  26     BN_CTX *new_ctx = NULL;
  27     BIGNUM *tmp1, *tmp2, *x, *y;
  28     int ret = 0;
  29
  30     /* clear error queue */
  31     ERR_clear_error();
  32
  33     if (ctx == NULL) {
  34         ctx = new_ctx = BN_CTX_new();
  35         if (ctx == NULL)
  36             return 0;
  37     }
  38
  39     y_bit = (y_bit != 0);
  40
  41     BN_CTX_start(ctx);
  42     tmp1 = BN_CTX_get(ctx);
  43     tmp2 = BN_CTX_get(ctx);
  44     x = BN_CTX_get(ctx);
  45     y = BN_CTX_get(ctx);
  46     if (y == NULL)
  47         goto err;
  48
  49     /*-
  50      * Recover y.  We have a Weierstrass equation
  51      *     y^2 = x^3 + a*x + b,
  52      * so  y  is one of the square roots of  x^3 + a*x + b.
  53      */
  54
  55     /* tmp1 := x^3 */
  56     if (!BN_nnmod(x, x_, group->field, ctx))
  57         goto err;
  58     if (group->meth->field_decode == 0) {
  59         /* field_{sqr,mul} work on standard representation */
  60         if (!group->meth->field_sqr(group, tmp2, x_, ctx))
  61             goto err;
  62         if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx))
  63             goto err;
  64     } else {
  65         if (!BN_mod_sqr(tmp2, x_, group->field, ctx))
  66             goto err;
  67         if (!BN_mod_mul(tmp1, tmp2, x_, group->field, ctx))
  68             goto err;
  69     }
  70
  71     /* tmp1 := tmp1 + a*x */
  72     if (group->a_is_minus3) {
  73         if (!BN_mod_lshift1_quick(tmp2, x, group->field))
  74             goto err;
  75         if (!BN_mod_add_quick(tmp2, tmp2, x, group->field))
  76             goto err;
  77         if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, group->field))
  78             goto err;
  79     } else {
  80         if (group->meth->field_decode) {
  81             if (!group->meth->field_decode(group, tmp2, group->a, ctx))
  82                 goto err;
  83             if (!BN_mod_mul(tmp2, tmp2, x, group->field, ctx))
  84                 goto err;
  85         } else {
  86             /* field_mul works on standard representation */
  87             if (!group->meth->field_mul(group, tmp2, group->a, x, ctx))
  88                 goto err;
  89         }
  90
  91         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field))
  92             goto err;
  93     }
  94
  95     /* tmp1 := tmp1 + b */
  96     if (group->meth->field_decode) {
  97         if (!group->meth->field_decode(group, tmp2, group->b, ctx))
  98             goto err;
  99         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field))
 100             goto err;
 101     } else {
 102         if (!BN_mod_add_quick(tmp1, tmp1, group->b, group->field))
 103             goto err;
 104     }
 105
 106     if (!BN_mod_sqrt(y, tmp1, group->field, ctx)) {
 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_clear_error();
 112             ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 113                   EC_R_INVALID_COMPRESSED_POINT);
 114         } else
 115             ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 116                   ERR_R_BN_LIB);
 117         goto err;
 118     }
 119
 120     if (y_bit != BN_is_odd(y)) {
 121         if (BN_is_zero(y)) {
 122             int kron;
 123
 124             kron = BN_kronecker(x, group->field, ctx);
 125             if (kron == -2)
 126                 goto err;
 127
 128             if (kron == 1)
 129                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 130                       EC_R_INVALID_COMPRESSION_BIT);
 131             else
 132                 /*
 133                  * BN_mod_sqrt() should have cought this error (not a square)
 134                  */
 135                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 136                       EC_R_INVALID_COMPRESSED_POINT);
 137             goto err;
 138         }
 139         if (!BN_usub(y, group->field, y))
 140             goto err;
 141     }
 142     if (y_bit != BN_is_odd(y)) {
 143         ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 144               ERR_R_INTERNAL_ERROR);
 145         goto err;
 146     }
 147
 148     if (!EC_POINT_set_affine_coordinates_GFp(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 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         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, 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                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, 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             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 198             goto err;
 199         }
 200
 201         if (ctx == NULL) {
 202             ctx = new_ctx = BN_CTX_new();
 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_GFp(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             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, 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             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, 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                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, 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             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, 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 ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
 275                             const unsigned char *buf, size_t len, BN_CTX *ctx)
 276 {
 277     point_conversion_form_t form;
 278     int y_bit;
 279     BN_CTX *new_ctx = NULL;
 280     BIGNUM *x, *y;
 281     size_t field_len, enc_len;
 282     int ret = 0;
 283
 284     if (len == 0) {
 285         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
 286         return 0;
 287     }
 288     form = buf[0];
 289     y_bit = form & 1;
 290     form = form & ~1U;
 291     if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
 292         && (form != POINT_CONVERSION_UNCOMPRESSED)
 293         && (form != POINT_CONVERSION_HYBRID)) {
 294         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 295         return 0;
 296     }
 297     if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
 298         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 299         return 0;
 300     }
 301
 302     if (form == 0) {
 303         if (len != 1) {
 304             ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 305             return 0;
 306         }
 307
 308         return EC_POINT_set_to_infinity(group, point);
 309     }
 310
 311     field_len = BN_num_bytes(group->field);
 312     enc_len =
 313         (form ==
 314          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 315
 316     if (len != enc_len) {
 317         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 318         return 0;
 319     }
 320
 321     if (ctx == NULL) {
 322         ctx = new_ctx = BN_CTX_new();
 323         if (ctx == NULL)
 324             return 0;
 325     }
 326
 327     BN_CTX_start(ctx);
 328     x = BN_CTX_get(ctx);
 329     y = BN_CTX_get(ctx);
 330     if (y == NULL)
 331         goto err;
 332
 333     if (!BN_bin2bn(buf + 1, field_len, x))
 334         goto err;
 335     if (BN_ucmp(x, group->field) >= 0) {
 336         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 337         goto err;
 338     }
 339
 340     if (form == POINT_CONVERSION_COMPRESSED) {
 341         if (!EC_POINT_set_compressed_coordinates_GFp
 342             (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             ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 349             goto err;
 350         }
 351         if (form == POINT_CONVERSION_HYBRID) {
 352             if (y_bit != BN_is_odd(y)) {
 353                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 354                 goto err;
 355             }
 356         }
 357
 358         /*
 359          * EC_POINT_set_affine_coordinates_GFp is responsible for checking that
 360          * the point is on the curve.
 361          */
 362         if (!EC_POINT_set_affine_coordinates_GFp(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 }