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