/*
* Copyright 2001-2018 The OpenSSL Project Authors. All Rights Reserved.
* Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
*
* Licensed under the OpenSSL license (the "License"). You may not use
* this file except in compliance with the License. You can obtain a copy
* in the file LICENSE in the source distribution or at
* https://www.openssl.org/source/license.html
*/
#include <string.h>
#include <openssl/err.h>
#include "internal/cryptlib.h"
#include "internal/bn_int.h"
#include "ec_lcl.h"
#include "internal/refcount.h"
/*
* This file implements the wNAF-based interleaving multi-exponentiation method
* Formerly at:
* http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp
* You might now find it here:
* http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13
* http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf
* For multiplication with precomputation, we use wNAF splitting, formerly at:
* http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp
*/
/* structure for precomputed multiples of the generator */
struct ec_pre_comp_st {
const EC_GROUP *group; /* parent EC_GROUP object */
size_t blocksize; /* block size for wNAF splitting */
size_t numblocks; /* max. number of blocks for which we have
* precomputation */
size_t w; /* window size */
EC_POINT **points; /* array with pre-calculated multiples of
* generator: 'num' pointers to EC_POINT
* objects followed by a NULL */
size_t num; /* numblocks * 2^(w-1) */
CRYPTO_REF_COUNT references;
CRYPTO_RWLOCK *lock;
};
static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group)
{
EC_PRE_COMP *ret = NULL;
if (!group)
return NULL;
ret = OPENSSL_zalloc(sizeof(*ret));
if (ret == NULL) {
ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
return ret;
}
ret->group = group;
ret->blocksize = 8; /* default */
ret->w = 4; /* default */
ret->references = 1;
ret->lock = CRYPTO_THREAD_lock_new();
if (ret->lock == NULL) {
ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
OPENSSL_free(ret);
return NULL;
}
return ret;
}
EC_PRE_COMP *EC_ec_pre_comp_dup(EC_PRE_COMP *pre)
{
int i;
if (pre != NULL)
CRYPTO_UP_REF(&pre->references, &i, pre->lock);
return pre;
}
void EC_ec_pre_comp_free(EC_PRE_COMP *pre)
{
int i;
if (pre == NULL)
return;
CRYPTO_DOWN_REF(&pre->references, &i, pre->lock);
REF_PRINT_COUNT("EC_ec", pre);
if (i > 0)
return;
REF_ASSERT_ISNT(i < 0);
if (pre->points != NULL) {
EC_POINT **pts;
for (pts = pre->points; *pts != NULL; pts++)
EC_POINT_free(*pts);
OPENSSL_free(pre->points);
}
CRYPTO_THREAD_lock_free(pre->lock);
OPENSSL_free(pre);
}
#define EC_POINT_BN_set_flags(P, flags) do { \
BN_set_flags((P)->X, (flags)); \
BN_set_flags((P)->Y, (flags)); \
BN_set_flags((P)->Z, (flags)); \
} while(0)
/*-
* This functions computes a single point multiplication over the EC group,
* using, at a high level, a Montgomery ladder with conditional swaps, with
* various timing attack defenses.
*
* It performs either a fixed point multiplication
* (scalar * generator)
* when point is NULL, or a variable point multiplication
* (scalar * point)
* when point is not NULL.
*
* `scalar` cannot be NULL and should be in the range [0,n) otherwise all
* constant time bets are off (where n is the cardinality of the EC group).
*
* This function expects `group->order` and `group->cardinality` to be well
* defined and non-zero: it fails with an error code otherwise.
*
* NB: This says nothing about the constant-timeness of the ladder step
* implementation (i.e., the default implementation is based on EC_POINT_add and
* EC_POINT_dbl, which of course are not constant time themselves) or the
* underlying multiprecision arithmetic.
*
* The product is stored in `r`.
*
* This is an internal function: callers are in charge of ensuring that the
* input parameters `group`, `r`, `scalar` and `ctx` are not NULL.
*
* Returns 1 on success, 0 otherwise.
*/
int ec_scalar_mul_ladder(const EC_GROUP *group, EC_POINT *r,
const BIGNUM *scalar, const EC_POINT *point,
BN_CTX *ctx)
{
int i, cardinality_bits, group_top, kbit, pbit, Z_is_one;
EC_POINT *p = NULL;
EC_POINT *s = NULL;
BIGNUM *k = NULL;
BIGNUM *lambda = NULL;
BIGNUM *cardinality = NULL;
int ret = 0;
/* early exit if the input point is the point at infinity */
if (point != NULL && EC_POINT_is_at_infinity(group, point))
return EC_POINT_set_to_infinity(group, r);
if (BN_is_zero(group->order)) {
ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_UNKNOWN_ORDER);
return 0;
}
if (BN_is_zero(group->cofactor)) {
ECerr(EC_F_EC_SCALAR_MUL_LADDER, EC_R_UNKNOWN_COFACTOR);
return 0;
}
BN_CTX_start(ctx);
if (((p = EC_POINT_new(group