crypto/ec/ecp_oct.c

   1 /*
   2  * Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
   3  * for the OpenSSL project. Includes code written by Bodo Moeller for the
   4  * 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 #include <openssl/symhacks.h>
  67
  68 #include "ec_lcl.h"
  69
  70 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
  71                                              EC_POINT *point,
  72                                              const BIGNUM *x_, int y_bit,
  73                                              BN_CTX *ctx)
  74 {
  75     BN_CTX *new_ctx = NULL;
  76     BIGNUM *tmp1, *tmp2, *x, *y;
  77     int ret = 0;
  78
  79     /* clear error queue */
  80     ERR_clear_error();
  81
  82     if (ctx == NULL) {
  83         ctx = new_ctx = BN_CTX_new();
  84         if (ctx == NULL)
  85             return 0;
  86     }
  87
  88     y_bit = (y_bit != 0);
  89
  90     BN_CTX_start(ctx);
  91     tmp1 = BN_CTX_get(ctx);
  92     tmp2 = BN_CTX_get(ctx);
  93     x = BN_CTX_get(ctx);
  94     y = BN_CTX_get(ctx);
  95     if (y == NULL)
  96         goto err;
  97
  98     /*-
  99      * Recover y.  We have a Weierstrass equation
 100      *     y^2 = x^3 + a*x + b,
 101      * so  y  is one of the square roots of  x^3 + a*x + b.
 102      */
 103
 104     /* tmp1 := x^3 */
 105     if (!BN_nnmod(x, x_, group->field, ctx))
 106         goto err;
 107     if (group->meth->field_decode == 0) {
 108         /* field_{sqr,mul} work on standard representation */
 109         if (!group->meth->field_sqr(group, tmp2, x_, ctx))
 110             goto err;
 111         if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx))
 112             goto err;
 113     } else {
 114         if (!BN_mod_sqr(tmp2, x_, group->field, ctx))
 115             goto err;
 116         if (!BN_mod_mul(tmp1, tmp2, x_, group->field, ctx))
 117             goto err;
 118     }
 119
 120     /* tmp1 := tmp1 + a*x */
 121     if (group->a_is_minus3) {
 122         if (!BN_mod_lshift1_quick(tmp2, x, group->field))
 123             goto err;
 124         if (!BN_mod_add_quick(tmp2, tmp2, x, group->field))
 125             goto err;
 126         if (!BN_mod_sub_quick(tmp1, tmp1, tmp2, group->field))
 127             goto err;
 128     } else {
 129         if (group->meth->field_decode) {
 130             if (!group->meth->field_decode(group, tmp2, group->a, ctx))
 131                 goto err;
 132             if (!BN_mod_mul(tmp2, tmp2, x, group->field, ctx))
 133                 goto err;
 134         } else {
 135             /* field_mul works on standard representation */
 136             if (!group->meth->field_mul(group, tmp2, group->a, x, ctx))
 137                 goto err;
 138         }
 139
 140         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field))
 141             goto err;
 142     }
 143
 144     /* tmp1 := tmp1 + b */
 145     if (group->meth->field_decode) {
 146         if (!group->meth->field_decode(group, tmp2, group->b, ctx))
 147             goto err;
 148         if (!BN_mod_add_quick(tmp1, tmp1, tmp2, group->field))
 149             goto err;
 150     } else {
 151         if (!BN_mod_add_quick(tmp1, tmp1, group->b, group->field))
 152             goto err;
 153     }
 154
 155     if (!BN_mod_sqrt(y, tmp1, group->field, ctx)) {
 156         unsigned long err = ERR_peek_last_error();
 157
 158         if (ERR_GET_LIB(err) == ERR_LIB_BN
 159             && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) {
 160             ERR_clear_error();
 161             ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 162                   EC_R_INVALID_COMPRESSED_POINT);
 163         } else
 164             ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 165                   ERR_R_BN_LIB);
 166         goto err;
 167     }
 168
 169     if (y_bit != BN_is_odd(y)) {
 170         if (BN_is_zero(y)) {
 171             int kron;
 172
 173             kron = BN_kronecker(x, group->field, ctx);
 174             if (kron == -2)
 175                 goto err;
 176
 177             if (kron == 1)
 178                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 179                       EC_R_INVALID_COMPRESSION_BIT);
 180             else
 181                 /*
 182                  * BN_mod_sqrt() should have cought this error (not a square)
 183                  */
 184                 ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 185                       EC_R_INVALID_COMPRESSED_POINT);
 186             goto err;
 187         }
 188         if (!BN_usub(y, group->field, y))
 189             goto err;
 190     }
 191     if (y_bit != BN_is_odd(y)) {
 192         ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES,
 193               ERR_R_INTERNAL_ERROR);
 194         goto err;
 195     }
 196
 197     if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
 198         goto err;
 199
 200     ret = 1;
 201
 202  err:
 203     BN_CTX_end(ctx);
 204     BN_CTX_free(new_ctx);
 205     return ret;
 206 }
 207
 208 size_t ec_GFp_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
 209                                point_conversion_form_t form,
 210                                unsigned char *buf, size_t len, BN_CTX *ctx)
 211 {
 212     size_t ret;
 213     BN_CTX *new_ctx = NULL;
 214     int used_ctx = 0;
 215     BIGNUM *x, *y;
 216     size_t field_len, i, skip;
 217
 218     if ((form != POINT_CONVERSION_COMPRESSED)
 219         && (form != POINT_CONVERSION_UNCOMPRESSED)
 220         && (form != POINT_CONVERSION_HYBRID)) {
 221         ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
 222         goto err;
 223     }
 224
 225     if (EC_POINT_is_at_infinity(group, point)) {
 226         /* encodes to a single 0 octet */
 227         if (buf != NULL) {
 228             if (len < 1) {
 229                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 230                 return 0;
 231             }
 232             buf[0] = 0;
 233         }
 234         return 1;
 235     }
 236
 237     /* ret := required output buffer length */
 238     field_len = BN_num_bytes(group->field);
 239     ret =
 240         (form ==
 241          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 242
 243     /* if 'buf' is NULL, just return required length */
 244     if (buf != NULL) {
 245         if (len < ret) {
 246             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 247             goto err;
 248         }
 249
 250         if (ctx == NULL) {
 251             ctx = new_ctx = BN_CTX_new();
 252             if (ctx == NULL)
 253                 return 0;
 254         }
 255
 256         BN_CTX_start(ctx);
 257         used_ctx = 1;
 258         x = BN_CTX_get(ctx);
 259         y = BN_CTX_get(ctx);
 260         if (y == NULL)
 261             goto err;
 262
 263         if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx))
 264             goto err;
 265
 266         if ((form == POINT_CONVERSION_COMPRESSED
 267              || form == POINT_CONVERSION_HYBRID) && BN_is_odd(y))
 268             buf[0] = form + 1;
 269         else
 270             buf[0] = form;
 271
 272         i = 1;
 273
 274         skip = field_len - BN_num_bytes(x);
 275         if (skip > field_len) {
 276             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 277             goto err;
 278         }
 279         while (skip > 0) {
 280             buf[i++] = 0;
 281             skip--;
 282         }
 283         skip = BN_bn2bin(x, buf + i);
 284         i += skip;
 285         if (i != 1 + field_len) {
 286             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 287             goto err;
 288         }
 289
 290         if (form == POINT_CONVERSION_UNCOMPRESSED
 291             || form == POINT_CONVERSION_HYBRID) {
 292             skip = field_len - BN_num_bytes(y);
 293             if (skip > field_len) {
 294                 ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 295                 goto err;
 296             }
 297             while (skip > 0) {
 298                 buf[i++] = 0;
 299                 skip--;
 300             }
 301             skip = BN_bn2bin(y, buf + i);
 302             i += skip;
 303         }
 304
 305         if (i != ret) {
 306             ECerr(EC_F_EC_GFP_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 307             goto err;
 308         }
 309     }
 310
 311     if (used_ctx)
 312         BN_CTX_end(ctx);
 313     BN_CTX_free(new_ctx);
 314     return ret;
 315
 316  err:
 317     if (used_ctx)
 318         BN_CTX_end(ctx);
 319     BN_CTX_free(new_ctx);
 320     return 0;
 321 }
 322
 323 int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
 324                             const unsigned char *buf, size_t len, BN_CTX *ctx)
 325 {
 326     point_conversion_form_t form;
 327     int y_bit;
 328     BN_CTX *new_ctx = NULL;
 329     BIGNUM *x, *y;
 330     size_t field_len, enc_len;
 331     int ret = 0;
 332
 333     if (len == 0) {
 334         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
 335         return 0;
 336     }
 337     form = buf[0];
 338     y_bit = form & 1;
 339     form = form & ~1U;
 340     if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
 341         && (form != POINT_CONVERSION_UNCOMPRESSED)
 342         && (form != POINT_CONVERSION_HYBRID)) {
 343         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 344         return 0;
 345     }
 346     if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
 347         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 348         return 0;
 349     }
 350
 351     if (form == 0) {
 352         if (len != 1) {
 353             ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 354             return 0;
 355         }
 356
 357         return EC_POINT_set_to_infinity(group, point);
 358     }
 359
 360     field_len = BN_num_bytes(group->field);
 361     enc_len =
 362         (form ==
 363          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 364
 365     if (len != enc_len) {
 366         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 367         return 0;
 368     }
 369
 370     if (ctx == NULL) {
 371         ctx = new_ctx = BN_CTX_new();
 372         if (ctx == NULL)
 373             return 0;
 374     }
 375
 376     BN_CTX_start(ctx);
 377     x = BN_CTX_get(ctx);
 378     y = BN_CTX_get(ctx);
 379     if (y == NULL)
 380         goto err;
 381
 382     if (!BN_bin2bn(buf + 1, field_len, x))
 383         goto err;
 384     if (BN_ucmp(x, group->field) >= 0) {
 385         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 386         goto err;
 387     }
 388
 389     if (form == POINT_CONVERSION_COMPRESSED) {
 390         if (!EC_POINT_set_compressed_coordinates_GFp
 391             (group, point, x, y_bit, ctx))
 392             goto err;
 393     } else {
 394         if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
 395             goto err;
 396         if (BN_ucmp(y, group->field) >= 0) {
 397             ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 398             goto err;
 399         }
 400         if (form == POINT_CONVERSION_HYBRID) {
 401             if (y_bit != BN_is_odd(y)) {
 402                 ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 403                 goto err;
 404             }
 405         }
 406
 407         if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx))
 408             goto err;
 409     }
 410
 411     /* test required by X9.62 */
 412     if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
 413         ECerr(EC_F_EC_GFP_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
 414         goto err;
 415     }
 416
 417     ret = 1;
 418
 419  err:
 420     BN_CTX_end(ctx);
 421     BN_CTX_free(new_ctx);
 422     return ret;
 423 }