lib/libcrypto/ec/ecp_oct.c

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