crypto/ec/ec2_oct.c

   1 /*
   2  * Copyright 2011-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 /* ====================================================================
  11  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
  12  *
  13  * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
  14  * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
  15  * to the OpenSSL project.
  16  *
  17  * The ECC Code is licensed pursuant to the OpenSSL open source
  18  * license provided below.
  19  *
  20  * The software is originally written by Sheueling Chang Shantz and
  21  * Douglas Stebila of Sun Microsystems Laboratories.
  22  *
  23  */
  24
  25 #include <openssl/err.h>
  26
  27 #include "ec_lcl.h"
  28
  29 #ifndef OPENSSL_NO_EC2M
  30
  31 /*-
  32  * Calculates and sets the affine coordinates of an EC_POINT from the given
  33  * compressed coordinates.  Uses algorithm 2.3.4 of SEC 1.
  34  * Note that the simple implementation only uses affine coordinates.
  35  *
  36  * The method is from the following publication:
  37  *
  38  *     Harper, Menezes, Vanstone:
  39  *     "Public-Key Cryptosystems with Very Small Key Lengths",
  40  *     EUROCRYPT '92, Springer-Verlag LNCS 658,
  41  *     published February 1993
  42  *
  43  * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe
  44  * the same method, but claim no priority date earlier than July 29, 1994
  45  * (and additionally fail to cite the EUROCRYPT '92 publication as prior art).
  46  */
  47 int ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group,
  48                                               EC_POINT *point,
  49                                               const BIGNUM *x_, int y_bit,
  50                                               BN_CTX *ctx)
  51 {
  52     BN_CTX *new_ctx = NULL;
  53     BIGNUM *tmp, *x, *y, *z;
  54     int ret = 0, z0;
  55
  56     /* clear error queue */
  57     ERR_clear_error();
  58
  59     if (ctx == NULL) {
  60         ctx = new_ctx = BN_CTX_new();
  61         if (ctx == NULL)
  62             return 0;
  63     }
  64
  65     y_bit = (y_bit != 0) ? 1 : 0;
  66
  67     BN_CTX_start(ctx);
  68     tmp = BN_CTX_get(ctx);
  69     x = BN_CTX_get(ctx);
  70     y = BN_CTX_get(ctx);
  71     z = BN_CTX_get(ctx);
  72     if (z == NULL)
  73         goto err;
  74
  75     if (!BN_GF2m_mod_arr(x, x_, group->poly))
  76         goto err;
  77     if (BN_is_zero(x)) {
  78         if (!BN_GF2m_mod_sqrt_arr(y, group->b, group->poly, ctx))
  79             goto err;
  80     } else {
  81         if (!group->meth->field_sqr(group, tmp, x, ctx))
  82             goto err;
  83         if (!group->meth->field_div(group, tmp, group->b, tmp, ctx))
  84             goto err;
  85         if (!BN_GF2m_add(tmp, group->a, tmp))
  86             goto err;
  87         if (!BN_GF2m_add(tmp, x, tmp))
  88             goto err;
  89         if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) {
  90             unsigned long err = ERR_peek_last_error();
  91
  92             if (ERR_GET_LIB(err) == ERR_LIB_BN
  93                 && ERR_GET_REASON(err) == BN_R_NO_SOLUTION) {
  94                 ERR_clear_error();
  95                 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,
  96                       EC_R_INVALID_COMPRESSED_POINT);
  97             } else
  98                 ECerr(EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES,
  99                       ERR_R_BN_LIB);
 100             goto err;
 101         }
 102         z0 = (BN_is_odd(z)) ? 1 : 0;
 103         if (!group->meth->field_mul(group, y, x, z, ctx))
 104             goto err;
 105         if (z0 != y_bit) {
 106             if (!BN_GF2m_add(y, y, x))
 107                 goto err;
 108         }
 109     }
 110
 111     if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))
 112         goto err;
 113
 114     ret = 1;
 115
 116  err:
 117     BN_CTX_end(ctx);
 118     BN_CTX_free(new_ctx);
 119     return ret;
 120 }
 121
 122 /*
 123  * Converts an EC_POINT to an octet string. If buf is NULL, the encoded
 124  * length will be returned. If the length len of buf is smaller than required
 125  * an error will be returned.
 126  */
 127 size_t ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
 128                                 point_conversion_form_t form,
 129                                 unsigned char *buf, size_t len, BN_CTX *ctx)
 130 {
 131     size_t ret;
 132     BN_CTX *new_ctx = NULL;
 133     int used_ctx = 0;
 134     BIGNUM *x, *y, *yxi;
 135     size_t field_len, i, skip;
 136
 137     if ((form != POINT_CONVERSION_COMPRESSED)
 138         && (form != POINT_CONVERSION_UNCOMPRESSED)
 139         && (form != POINT_CONVERSION_HYBRID)) {
 140         ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_INVALID_FORM);
 141         goto err;
 142     }
 143
 144     if (EC_POINT_is_at_infinity(group, point)) {
 145         /* encodes to a single 0 octet */
 146         if (buf != NULL) {
 147             if (len < 1) {
 148                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 149                 return 0;
 150             }
 151             buf[0] = 0;
 152         }
 153         return 1;
 154     }
 155
 156     /* ret := required output buffer length */
 157     field_len = (EC_GROUP_get_degree(group) + 7) / 8;
 158     ret =
 159         (form ==
 160          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 161
 162     /* if 'buf' is NULL, just return required length */
 163     if (buf != NULL) {
 164         if (len < ret) {
 165             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, EC_R_BUFFER_TOO_SMALL);
 166             goto err;
 167         }
 168
 169         if (ctx == NULL) {
 170             ctx = new_ctx = BN_CTX_new();
 171             if (ctx == NULL)
 172                 return 0;
 173         }
 174
 175         BN_CTX_start(ctx);
 176         used_ctx = 1;
 177         x = BN_CTX_get(ctx);
 178         y = BN_CTX_get(ctx);
 179         yxi = BN_CTX_get(ctx);
 180         if (yxi == NULL)
 181             goto err;
 182
 183         if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx))
 184             goto err;
 185
 186         buf[0] = form;
 187         if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) {
 188             if (!group->meth->field_div(group, yxi, y, x, ctx))
 189                 goto err;
 190             if (BN_is_odd(yxi))
 191                 buf[0]++;
 192         }
 193
 194         i = 1;
 195
 196         skip = field_len - BN_num_bytes(x);
 197         if (skip > field_len) {
 198             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 199             goto err;
 200         }
 201         while (skip > 0) {
 202             buf[i++] = 0;
 203             skip--;
 204         }
 205         skip = BN_bn2bin(x, buf + i);
 206         i += skip;
 207         if (i != 1 + field_len) {
 208             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 209             goto err;
 210         }
 211
 212         if (form == POINT_CONVERSION_UNCOMPRESSED
 213             || form == POINT_CONVERSION_HYBRID) {
 214             skip = field_len - BN_num_bytes(y);
 215             if (skip > field_len) {
 216                 ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 217                 goto err;
 218             }
 219             while (skip > 0) {
 220                 buf[i++] = 0;
 221                 skip--;
 222             }
 223             skip = BN_bn2bin(y, buf + i);
 224             i += skip;
 225         }
 226
 227         if (i != ret) {
 228             ECerr(EC_F_EC_GF2M_SIMPLE_POINT2OCT, ERR_R_INTERNAL_ERROR);
 229             goto err;
 230         }
 231     }
 232
 233     if (used_ctx)
 234         BN_CTX_end(ctx);
 235     BN_CTX_free(new_ctx);
 236     return ret;
 237
 238  err:
 239     if (used_ctx)
 240         BN_CTX_end(ctx);
 241     BN_CTX_free(new_ctx);
 242     return 0;
 243 }
 244
 245 /*
 246  * Converts an octet string representation to an EC_POINT. Note that the
 247  * simple implementation only uses affine coordinates.
 248  */
 249 int ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
 250                              const unsigned char *buf, size_t len,
 251                              BN_CTX *ctx)
 252 {
 253     point_conversion_form_t form;
 254     int y_bit;
 255     BN_CTX *new_ctx = NULL;
 256     BIGNUM *x, *y, *yxi;
 257     size_t field_len, enc_len;
 258     int ret = 0;
 259
 260     if (len == 0) {
 261         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_BUFFER_TOO_SMALL);
 262         return 0;
 263     }
 264     form = buf[0];
 265     y_bit = form & 1;
 266     form = form & ~1U;
 267     if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED)
 268         && (form != POINT_CONVERSION_UNCOMPRESSED)
 269         && (form != POINT_CONVERSION_HYBRID)) {
 270         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 271         return 0;
 272     }
 273     if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
 274         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 275         return 0;
 276     }
 277
 278     if (form == 0) {
 279         if (len != 1) {
 280             ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 281             return 0;
 282         }
 283
 284         return EC_POINT_set_to_infinity(group, point);
 285     }
 286
 287     field_len = (EC_GROUP_get_degree(group) + 7) / 8;
 288     enc_len =
 289         (form ==
 290          POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
 291
 292     if (len != enc_len) {
 293         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 294         return 0;
 295     }
 296
 297     if (ctx == NULL) {
 298         ctx = new_ctx = BN_CTX_new();
 299         if (ctx == NULL)
 300             return 0;
 301     }
 302
 303     BN_CTX_start(ctx);
 304     x = BN_CTX_get(ctx);
 305     y = BN_CTX_get(ctx);
 306     yxi = BN_CTX_get(ctx);
 307     if (yxi == NULL)
 308         goto err;
 309
 310     if (!BN_bin2bn(buf + 1, field_len, x))
 311         goto err;
 312     if (BN_ucmp(x, group->field) >= 0) {
 313         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 314         goto err;
 315     }
 316
 317     if (form == POINT_CONVERSION_COMPRESSED) {
 318         if (!EC_POINT_set_compressed_coordinates_GF2m
 319             (group, point, x, y_bit, ctx))
 320             goto err;
 321     } else {
 322         if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
 323             goto err;
 324         if (BN_ucmp(y, group->field) >= 0) {
 325             ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 326             goto err;
 327         }
 328         if (form == POINT_CONVERSION_HYBRID) {
 329             if (!group->meth->field_div(group, yxi, y, x, ctx))
 330                 goto err;
 331             if (y_bit != BN_is_odd(yxi)) {
 332                 ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_INVALID_ENCODING);
 333                 goto err;
 334             }
 335         }
 336
 337         if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))
 338             goto err;
 339     }
 340
 341     /* test required by X9.62 */
 342     if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
 343         ECerr(EC_F_EC_GF2M_SIMPLE_OCT2POINT, EC_R_POINT_IS_NOT_ON_CURVE);
 344         goto err;
 345     }
 346
 347     ret = 1;
 348
 349  err:
 350     BN_CTX_end(ctx);
 351     BN_CTX_free(new_ctx);
 352     return ret;
 353 }
 354 #endif