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