src/third_party/boringssl/src/crypto/ec/oct.c

   1 /* Originally written by Bodo Moeller for the OpenSSL project.
   2  * ====================================================================
   3  * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in
  14  *    the documentation and/or other materials provided with the
  15  *    distribution.
  16  *
  17  * 3. All advertising materials mentioning features or use of this
  18  *    software must display the following acknowledgment:
  19  *    "This product includes software developed by the OpenSSL Project
  20  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  21  *
  22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  23  *    endorse or promote products derived from this software without
  24  *    prior written permission. For written permission, please contact
  25  *    openssl-core@openssl.org.
  26  *
  27  * 5. Products derived from this software may not be called "OpenSSL"
  28  *    nor may "OpenSSL" appear in their names without prior written
  29  *    permission of the OpenSSL Project.
  30  *
  31  * 6. Redistributions of any form whatsoever must retain the following
  32  *    acknowledgment:
  33  *    "This product includes software developed by the OpenSSL Project
  34  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  35  *
  36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  47  * OF THE POSSIBILITY OF SUCH DAMAGE.
  48  * ====================================================================
  49  *
  50  * This product includes cryptographic software written by Eric Young
  51  * (eay@cryptsoft.com).  This product includes software written by Tim
  52  * Hudson (tjh@cryptsoft.com).
  53  *
  54  */
  55 /* ====================================================================
  56  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  57  *
  58  * Portions of the attached software ("Contribution") are developed by
  59  * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
  60  *
  61  * The Contribution is licensed pursuant to the OpenSSL open source
  62  * license provided above.
  63  *
  64  * The elliptic curve binary polynomial software is originally written by
  65  * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
  66  * Laboratories. */
  67
  68 #include <openssl/ec.h>
  69
  70 #include <openssl/bn.h>
  71 #include <openssl/err.h>
  72
  73 #include "internal.h"
  74
  75
  76 static size_t ec_GFp_simple_point2oct(const EC_GROUP *group,
  77                                       const EC_POINT *point,
  78                                       point_conversion_form_t form,
  79                                       uint8_t *buf, size_t len, BN_CTX *ctx) {
  80   size_t ret;
  81   BN_CTX *new_ctx = NULL;
  82   int used_ctx = 0;
  83   BIGNUM *x, *y;
  84   size_t field_len, i, skip;
  85
  86   if ((form != POINT_CONVERSION_COMPRESSED) &&
  87       (form != POINT_CONVERSION_UNCOMPRESSED) &&
  88       (form != POINT_CONVERSION_HYBRID)) {
  89     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_INVALID_FORM);
  90     goto err;
  91   }
  92
  93   if (EC_POINT_is_at_infinity(group, point)) {
  94     /* encodes to a single 0 octet */
  95     if (buf != NULL) {
  96       if (len < 1) {
  97         OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL);
  98         return 0;
  99       }
 100       buf[0] = 0;
 101     }
 102     return 1;
 103   }
 104
 105
 106   /* ret := required output buffer length */
 107   field_len = BN_num_bytes(&group->field);
 108   ret =
 109       (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 110
 111   /* if 'buf' is NULL, just return required length */
 112   if (buf != NULL) {
 113     if (len < ret) {
 114       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL);
 115       goto err;
 116     }
 117
 118     if (ctx == NULL) {
 119       ctx = new_ctx = BN_CTX_new();
 120       if (ctx == NULL)
 121         return 0;
 122     }
 123
 124     BN_CTX_start(ctx);
 125     used_ctx = 1;
 126     x = BN_CTX_get(ctx);
 127     y = BN_CTX_get(ctx);
 128     if (y == NULL)
 129       goto err;
 130
 131     if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
 132       goto err;
 133
 134     if ((form == POINT_CONVERSION_COMPRESSED ||
 135          form == POINT_CONVERSION_HYBRID) &&
 136         BN_is_odd(y))
 137       buf[0] = form + 1;
 138     else
 139       buf[0] = form;
 140
 141     i = 1;
 142
 143     skip = field_len - BN_num_bytes(x);
 144     if (skip > field_len) {
 145       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR);
 146       goto err;
 147     }
 148     while (skip > 0) {
 149       buf[i++] = 0;
 150       skip--;
 151     }
 152     skip = BN_bn2bin(x, buf + i);
 153     i += skip;
 154     if (i != 1 + field_len) {
 155       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR);
 156       goto err;
 157     }
 158
 159     if (form == POINT_CONVERSION_UNCOMPRESSED ||
 160         form == POINT_CONVERSION_HYBRID) {
 161       skip = field_len - BN_num_bytes(y);
 162       if (skip > field_len) {
 163         OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR);
 164         goto err;
 165       }
 166       while (skip > 0) {
 167         buf[i++] = 0;
 168         skip--;
 169       }
 170       skip = BN_bn2bin(y, buf + i);
 171       i += skip;
 172     }
 173
 174     if (i != ret) {
 175       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR);
 176       goto err;
 177     }
 178   }
 179
 180   if (used_ctx)
 181     BN_CTX_end(ctx);
 182   if (new_ctx != NULL)
 183     BN_CTX_free(new_ctx);
 184   return ret;
 185
 186 err:
 187   if (used_ctx)
 188     BN_CTX_end(ctx);
 189   if (new_ctx != NULL)
 190     BN_CTX_free(new_ctx);
 191   return 0;
 192 }
 193
 194
 195 static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
 196                                    const uint8_t *buf, size_t len,
 197                                    BN_CTX *ctx) {
 198   point_conversion_form_t form;
 199   int y_bit;
 200   BN_CTX *new_ctx = NULL;
 201   BIGNUM *x, *y;
 202   size_t field_len, enc_len;
 203   int ret = 0;
 204
 205   if (len == 0) {
 206     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_BUFFER_TOO_SMALL);
 207     return 0;
 208   }
 209   form = buf[0];
 210   y_bit = form & 1;
 211   form = form & ~1U;
 212   if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) &&
 213       (form != POINT_CONVERSION_UNCOMPRESSED) &&
 214       (form != POINT_CONVERSION_HYBRID)) {
 215     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
 216     return 0;
 217   }
 218   if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
 219     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
 220     return 0;
 221   }
 222
 223   if (form == 0) {
 224     if (len != 1) {
 225       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
 226       return 0;
 227     }
 228
 229     return EC_POINT_set_to_infinity(group, point);
 230   }
 231
 232   field_len = BN_num_bytes(&group->field);
 233   enc_len =
 234       (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 235
 236   if (len != enc_len) {
 237     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
 238     return 0;
 239   }
 240
 241   if (ctx == NULL) {
 242     ctx = new_ctx = BN_CTX_new();
 243     if (ctx == NULL)
 244       return 0;
 245   }
 246
 247   BN_CTX_start(ctx);
 248   x = BN_CTX_get(ctx);
 249   y = BN_CTX_get(ctx);
 250   if (y == NULL)
 251     goto err;
 252
 253   if (!BN_bin2bn(buf + 1, field_len, x))
 254     goto err;
 255   if (BN_ucmp(x, &group->field) >= 0) {
 256     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
 257     goto err;
 258   }
 259
 260   if (form == POINT_CONVERSION_COMPRESSED) {
 261     if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx))
 262       goto err;
 263   } else {
 264     if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
 265       goto err;
 266     if (BN_ucmp(y, &group->field) >= 0) {
 267       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
 268       goto err;
 269     }
 270     if (form == POINT_CONVERSION_HYBRID) {
 271       if (y_bit != BN_is_odd(y)) {
 272         OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
 273         goto err;
 274       }
 275     }
 276
 277     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
 278       goto err;
 279   }
 280
 281   if (!EC_POINT_is_on_curve(group, point, ctx)) /* test required by X9.62 */
 282   {
 283     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_POINT_IS_NOT_ON_CURVE);
 284     goto err;
 285   }
 286
 287   ret = 1;
 288
 289 err:
 290   BN_CTX_end(ctx);
 291   if (new_ctx != NULL)
 292     BN_CTX_free(new_ctx);
 293   return ret;
 294 }
 295
 296 int EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point,
 297                        const uint8_t *buf, size_t len, BN_CTX *ctx) {
 298   if (group->meth->oct2point == 0 &&
 299       !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) {
 300     OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point,
 301                       ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 302     return 0;
 303   }
 304   if (group->meth != point->meth) {
 305     OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point, EC_R_INCOMPATIBLE_OBJECTS);
 306     return 0;
 307   }
 308   if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) {
 309     return ec_GFp_simple_oct2point(group, point, buf, len, ctx);
 310   }
 311
 312   return group->meth->oct2point(group, point, buf, len, ctx);
 313 }
 314
 315 size_t EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point,
 316                           point_conversion_form_t form, uint8_t *buf,
 317                           size_t len, BN_CTX *ctx) {
 318   if (group->meth->point2oct == 0 &&
 319       !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) {
 320     OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct,
 321                       ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 322     return 0;
 323   }
 324   if (group->meth != point->meth) {
 325     OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct, EC_R_INCOMPATIBLE_OBJECTS);
 326     return 0;
 327   }
 328   if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) {
 329     return ec_GFp_simple_point2oct(group, point, form, buf, len, ctx);
 330   }
 331
 332   return group->meth->point2oct(group, point, form, buf, len, ctx);
 333 }
 334
 335 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
 336                                              EC_POINT *point, const BIGNUM *x_,
 337                                              int y_bit, BN_CTX *ctx) {
 338   BN_CTX *new_ctx = NULL;
 339   BIGNUM *tmp1, *tmp2, *x, *y;
 340   int ret = 0;
 341
 342   ERR_clear_error();
 343
 344   if (ctx == NULL) {
 345     ctx = new_ctx = BN_CTX_new();
 346     if (ctx == NULL) {
 347       return 0;
 348     }
 349   }
 350
 351   y_bit = (y_bit != 0);
 352
 353   BN_CTX_start(ctx);
 354   tmp1 = BN_CTX_get(ctx);
 355   tmp2 = BN_CTX_get(ctx);
 356   x = BN_CTX_get(ctx);
 357   y = BN_CTX_get(ctx);
 358   if (y == NULL) {
 359     goto err;
 360   }
 361
 362   /* Recover y.  We have a Weierstrass equation
 363    *     y^2 = x^3 + a*x + b,
 364    * so  y  is one of the square roots of  x^3 + a*x + b. */
 365
 366   /* tmp1 := x^3 */
 367   if (!BN_nnmod(x, x_, &group->field, ctx)) {
 368     goto err;
 369   }
 370
 371   if (group->meth->field_decode == 0) {
 372     /* field_{sqr,mul} work on standard representation */
 373     if (!group->meth->field_sqr(group, tmp2, x_, ctx) ||
 374         !group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) {
 375       goto err;
 376     }
 377   } else {
 378     if (!BN_mod_sqr(tmp2, x_, &group->field, ctx) ||
 379         !BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) {
 380       goto err;
 381     }
 382   }
 383
 384   /* tmp1 := tmp1 + a*x */
 385   if (group->a_is_minus3) {
 386     if (!BN_mod_lshift1_quick(tmp2, x, &group->field) ||
 387         !BN_mod_add_quick(tmp2, tmp2, x, &group->field) ||
 388         !BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) {
 389       goto err;
 390     }
 391   } else {
 392     if (group->meth->field_decode) {
 393       if (!group->meth->field_decode(group, tmp2, &group->a, ctx) ||
 394           !BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) {
 395         goto err;
 396       }
 397     } else {
 398       /* field_mul works on standard representation */
 399       if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) {
 400         goto err;
 401       }
 402     }
 403
 404     if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) {
 405       goto err;
 406     }
 407   }
 408
 409   /* tmp1 := tmp1 + b */
 410   if (group->meth->field_decode) {
 411     if (!group->meth->field_decode(group, tmp2, &group->b, ctx) ||
 412         !BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) {
 413       goto err;
 414     }
 415   } else {
 416     if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) {
 417       goto err;
 418     }
 419   }
 420
 421   if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) {
 422     unsigned long err = ERR_peek_last_error();
 423
 424     if (ERR_GET_LIB(err) == ERR_LIB_BN &&
 425         ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) {
 426       ERR_clear_error();
 427       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, EC_R_INVALID_COMPRESSED_POINT);
 428     } else {
 429       OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, ERR_R_BN_LIB);
 430     }
 431     goto err;
 432   }
 433
 434   if (y_bit != BN_is_odd(y)) {
 435     if (BN_is_zero(y)) {
 436       int kron;
 437
 438       kron = BN_kronecker(x, &group->field, ctx);
 439       if (kron == -2) {
 440         goto err;
 441       }
 442
 443       if (kron == 1) {
 444         OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates,
 445                           EC_R_INVALID_COMPRESSION_BIT);
 446       } else {
 447         /* BN_mod_sqrt() should have cought this error (not a square) */
 448         OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates,
 449                           EC_R_INVALID_COMPRESSED_POINT);
 450       }
 451       goto err;
 452     }
 453     if (!BN_usub(y, &group->field, y)) {
 454       goto err;
 455     }
 456   }
 457   if (y_bit != BN_is_odd(y)) {
 458     OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates,
 459                       ERR_R_INTERNAL_ERROR);
 460     goto err;
 461   }
 462
 463   if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
 464     goto err;
 465
 466   ret = 1;
 467
 468 err:
 469   BN_CTX_end(ctx);
 470   if (new_ctx != NULL)
 471     BN_CTX_free(new_ctx);
 472   return ret;
 473 }
 474
 475 int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group,
 476                                             EC_POINT *point, const BIGNUM *x,
 477                                             int y_bit, BN_CTX *ctx) {
 478   if (group->meth->point_set_compressed_coordinates == 0 &&
 479       !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) {
 480     OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp,
 481                       ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
 482     return 0;
 483   }
 484   if (group->meth != point->meth) {
 485     OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp,
 486                       EC_R_INCOMPATIBLE_OBJECTS);
 487     return 0;
 488   }
 489   if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) {
 490     return ec_GFp_simple_set_compressed_coordinates(group, point, x, y_bit,
 491                                                     ctx);
 492   }
 493   return group->meth->point_set_compressed_coordinates(group, point, x, y_bit,
 494                                                        ctx);
 495 }