crypto/ec/ecp_oct.c

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