crypto/ec/ecp_mont.c

   1 /*
   2  * Copyright 2001-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
   4  *
   5  * Licensed under the Apache License 2.0 (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  */
  10
  11 /*
  12  * ECDSA low level APIs are deprecated for public use, but still ok for
  13  * internal use.
  14  */
  15 #include "internal/deprecated.h"
  16
  17 #include <openssl/err.h>
  18
  19 #include "ec_local.h"
  20
  21 const EC_METHOD *EC_GFp_mont_method(void)
  22 {
  23     static const EC_METHOD ret = {
  24         EC_FLAGS_DEFAULT_OCT,
  25         NID_X9_62_prime_field,
  26         ec_GFp_mont_group_init,
  27         ec_GFp_mont_group_finish,
  28         ec_GFp_mont_group_clear_finish,
  29         ec_GFp_mont_group_copy,
  30         ec_GFp_mont_group_set_curve,
  31         ec_GFp_simple_group_get_curve,
  32         ec_GFp_simple_group_get_degree,
  33         ec_group_simple_order_bits,
  34         ec_GFp_simple_group_check_discriminant,
  35         ec_GFp_simple_point_init,
  36         ec_GFp_simple_point_finish,
  37         ec_GFp_simple_point_clear_finish,
  38         ec_GFp_simple_point_copy,
  39         ec_GFp_simple_point_set_to_infinity,
  40         ec_GFp_simple_point_set_affine_coordinates,
  41         ec_GFp_simple_point_get_affine_coordinates,
  42         0, 0, 0,
  43         ec_GFp_simple_add,
  44         ec_GFp_simple_dbl,
  45         ec_GFp_simple_invert,
  46         ec_GFp_simple_is_at_infinity,
  47         ec_GFp_simple_is_on_curve,
  48         ec_GFp_simple_cmp,
  49         ec_GFp_simple_make_affine,
  50         ec_GFp_simple_points_make_affine,
  51         0 /* mul */ ,
  52         0 /* precompute_mult */ ,
  53         0 /* have_precompute_mult */ ,
  54         ec_GFp_mont_field_mul,
  55         ec_GFp_mont_field_sqr,
  56         0 /* field_div */ ,
  57         ec_GFp_mont_field_inv,
  58         ec_GFp_mont_field_encode,
  59         ec_GFp_mont_field_decode,
  60         ec_GFp_mont_field_set_to_one,
  61         ec_key_simple_priv2oct,
  62         ec_key_simple_oct2priv,
  63         0, /* set private */
  64         ec_key_simple_generate_key,
  65         ec_key_simple_check_key,
  66         ec_key_simple_generate_public_key,
  67         0, /* keycopy */
  68         0, /* keyfinish */
  69         ecdh_simple_compute_key,
  70         ecdsa_simple_sign_setup,
  71         ecdsa_simple_sign_sig,
  72         ecdsa_simple_verify_sig,
  73         0, /* field_inverse_mod_ord */
  74         ec_GFp_simple_blind_coordinates,
  75         ec_GFp_simple_ladder_pre,
  76         ec_GFp_simple_ladder_step,
  77         ec_GFp_simple_ladder_post
  78     };
  79
  80     return &ret;
  81 }
  82
  83 int ec_GFp_mont_group_init(EC_GROUP *group)
  84 {
  85     int ok;
  86
  87     ok = ec_GFp_simple_group_init(group);
  88     group->field_data1 = NULL;
  89     group->field_data2 = NULL;
  90     return ok;
  91 }
  92
  93 void ec_GFp_mont_group_finish(EC_GROUP *group)
  94 {
  95     BN_MONT_CTX_free(group->field_data1);
  96     group->field_data1 = NULL;
  97     BN_free(group->field_data2);
  98     group->field_data2 = NULL;
  99     ec_GFp_simple_group_finish(group);
 100 }
 101
 102 void ec_GFp_mont_group_clear_finish(EC_GROUP *group)
 103 {
 104     BN_MONT_CTX_free(group->field_data1);
 105     group->field_data1 = NULL;
 106     BN_clear_free(group->field_data2);
 107     group->field_data2 = NULL;
 108     ec_GFp_simple_group_clear_finish(group);
 109 }
 110
 111 int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src)
 112 {
 113     BN_MONT_CTX_free(dest->field_data1);
 114     dest->field_data1 = NULL;
 115     BN_clear_free(dest->field_data2);
 116     dest->field_data2 = NULL;
 117
 118     if (!ec_GFp_simple_group_copy(dest, src))
 119         return 0;
 120
 121     if (src->field_data1 != NULL) {
 122         dest->field_data1 = BN_MONT_CTX_new();
 123         if (dest->field_data1 == NULL)
 124             return 0;
 125         if (!BN_MONT_CTX_copy(dest->field_data1, src->field_data1))
 126             goto err;
 127     }
 128     if (src->field_data2 != NULL) {
 129         dest->field_data2 = BN_dup(src->field_data2);
 130         if (dest->field_data2 == NULL)
 131             goto err;
 132     }
 133
 134     return 1;
 135
 136  err:
 137     BN_MONT_CTX_free(dest->field_data1);
 138     dest->field_data1 = NULL;
 139     return 0;
 140 }
 141
 142 int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p,
 143                                 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 144 {
 145     BN_CTX *new_ctx = NULL;
 146     BN_MONT_CTX *mont = NULL;
 147     BIGNUM *one = NULL;
 148     int ret = 0;
 149
 150     BN_MONT_CTX_free(group->field_data1);
 151     group->field_data1 = NULL;
 152     BN_free(group->field_data2);
 153     group->field_data2 = NULL;
 154
 155     if (ctx == NULL) {
 156         ctx = new_ctx = BN_CTX_new_ex(group->libctx);
 157         if (ctx == NULL)
 158             return 0;
 159     }
 160
 161     mont = BN_MONT_CTX_new();
 162     if (mont == NULL)
 163         goto err;
 164     if (!BN_MONT_CTX_set(mont, p, ctx)) {
 165         ECerr(EC_F_EC_GFP_MONT_GROUP_SET_CURVE, ERR_R_BN_LIB);
 166         goto err;
 167     }
 168     one = BN_new();
 169     if (one == NULL)
 170         goto err;
 171     if (!BN_to_montgomery(one, BN_value_one(), mont, ctx))
 172         goto err;
 173
 174     group->field_data1 = mont;
 175     mont = NULL;
 176     group->field_data2 = one;
 177     one = NULL;
 178
 179     ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
 180
 181     if (!ret) {
 182         BN_MONT_CTX_free(group->field_data1);
 183         group->field_data1 = NULL;
 184         BN_free(group->field_data2);
 185         group->field_data2 = NULL;
 186     }
 187
 188  err:
 189     BN_free(one);
 190     BN_CTX_free(new_ctx);
 191     BN_MONT_CTX_free(mont);
 192     return ret;
 193 }
 194
 195 int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
 196                           const BIGNUM *b, BN_CTX *ctx)
 197 {
 198     if (group->field_data1 == NULL) {
 199         ECerr(EC_F_EC_GFP_MONT_FIELD_MUL, EC_R_NOT_INITIALIZED);
 200         return 0;
 201     }
 202
 203     return BN_mod_mul_montgomery(r, a, b, group->field_data1, ctx);
 204 }
 205
 206 int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
 207                           BN_CTX *ctx)
 208 {
 209     if (group->field_data1 == NULL) {
 210         ECerr(EC_F_EC_GFP_MONT_FIELD_SQR, EC_R_NOT_INITIALIZED);
 211         return 0;
 212     }
 213
 214     return BN_mod_mul_montgomery(r, a, a, group->field_data1, ctx);
 215 }
 216
 217 /*-
 218  * Computes the multiplicative inverse of a in GF(p), storing the result in r.
 219  * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
 220  * We have a Mont structure, so SCA hardening is FLT inversion.
 221  */
 222 int ec_GFp_mont_field_inv(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
 223                             BN_CTX *ctx)
 224 {
 225     BIGNUM *e = NULL;
 226     BN_CTX *new_ctx = NULL;
 227     int ret = 0;
 228
 229     if (group->field_data1 == NULL)
 230         return 0;
 231
 232     if (ctx == NULL
 233             && (ctx = new_ctx = BN_CTX_secure_new_ex(group->libctx)) == NULL)
 234         return 0;
 235
 236     BN_CTX_start(ctx);
 237     if ((e = BN_CTX_get(ctx)) == NULL)
 238         goto err;
 239
 240     /* Inverse in constant time with Fermats Little Theorem */
 241     if (!BN_set_word(e, 2))
 242         goto err;
 243     if (!BN_sub(e, group->field, e))
 244         goto err;
 245     /*-
 246      * Exponent e is public.
 247      * No need for scatter-gather or BN_FLG_CONSTTIME.
 248      */
 249     if (!BN_mod_exp_mont(r, a, e, group->field, ctx, group->field_data1))
 250         goto err;
 251
 252     /* throw an error on zero */
 253     if (BN_is_zero(r)) {
 254         ECerr(EC_F_EC_GFP_MONT_FIELD_INV, EC_R_CANNOT_INVERT);
 255         goto err;
 256     }
 257
 258     ret = 1;
 259
 260   err:
 261     BN_CTX_end(ctx);
 262     BN_CTX_free(new_ctx);
 263     return ret;
 264 }
 265
 266 int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r,
 267                              const BIGNUM *a, BN_CTX *ctx)
 268 {
 269     if (group->field_data1 == NULL) {
 270         ECerr(EC_F_EC_GFP_MONT_FIELD_ENCODE, EC_R_NOT_INITIALIZED);
 271         return 0;
 272     }
 273
 274     return BN_to_montgomery(r, a, (BN_MONT_CTX *)group->field_data1, ctx);
 275 }
 276
 277 int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r,
 278                              const BIGNUM *a, BN_CTX *ctx)
 279 {
 280     if (group->field_data1 == NULL) {
 281         ECerr(EC_F_EC_GFP_MONT_FIELD_DECODE, EC_R_NOT_INITIALIZED);
 282         return 0;
 283     }
 284
 285     return BN_from_montgomery(r, a, group->field_data1, ctx);
 286 }
 287
 288 int ec_GFp_mont_field_set_to_one(const EC_GROUP *group, BIGNUM *r,
 289                                  BN_CTX *ctx)
 290 {
 291     if (group->field_data2 == NULL) {
 292         ECerr(EC_F_EC_GFP_MONT_FIELD_SET_TO_ONE, EC_R_NOT_INITIALIZED);
 293         return 0;
 294     }
 295
 296     if (!BN_copy(r, group->field_data2))
 297         return 0;
 298     return 1;
 299 }