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