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