Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/ecmult_impl.h
/***************************************************************************** | /***************************************************************************** | ||||
* Copyright (c) 2013, 2014, 2017 Pieter Wuille, Andrew Poelstra, Jonas Nick * | * Copyright (c) 2013, 2014, 2017 Pieter Wuille, Andrew Poelstra, Jonas Nick * | ||||
* Distributed under the MIT software license, see the accompanying * | * Distributed under the MIT software license, see the accompanying * | ||||
* file COPYING or http://www.opensource.org/licenses/mit-license.php. * | * file COPYING or http://www.opensource.org/licenses/mit-license.php. * | ||||
*****************************************************************************/ | *****************************************************************************/ | ||||
#ifndef SECP256K1_ECMULT_IMPL_H | #ifndef SECP256K1_ECMULT_IMPL_H | ||||
#define SECP256K1_ECMULT_IMPL_H | #define SECP256K1_ECMULT_IMPL_H | ||||
#include <string.h> | #include <string.h> | ||||
#include <stdint.h> | #include <stdint.h> | ||||
#include "util.h" | |||||
#include "group.h" | #include "group.h" | ||||
#include "scalar.h" | #include "scalar.h" | ||||
#include "ecmult.h" | #include "ecmult.h" | ||||
#if defined(EXHAUSTIVE_TEST_ORDER) | #if defined(EXHAUSTIVE_TEST_ORDER) | ||||
/* We need to lower these values for exhaustive tests because | /* We need to lower these values for exhaustive tests because | ||||
* the tables cannot have infinities in them (this breaks the | * the tables cannot have infinities in them (this breaks the | ||||
* affine-isomorphism stuff which tracks z-ratios) */ | * affine-isomorphism stuff which tracks z-ratios) */ | ||||
▲ Show 20 Lines • Show All 284 Lines • ▼ Show 20 Lines | #define ECMULT_TABLE_GET_GE_STORAGE(r,pre,n,w) do { \ | ||||
if ((n) > 0) { \ | if ((n) > 0) { \ | ||||
secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \ | secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \ | ||||
} else { \ | } else { \ | ||||
secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \ | secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \ | ||||
secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \ | secp256k1_fe_negate(&((r)->y), &((r)->y), 1); \ | ||||
} \ | } \ | ||||
} while(0) | } while(0) | ||||
static const size_t SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE = | |||||
ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)) | |||||
#ifdef USE_ENDOMORPHISM | |||||
+ ROUND_TO_ALIGN(sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G)) | |||||
#endif | |||||
; | |||||
static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx) { | static void secp256k1_ecmult_context_init(secp256k1_ecmult_context *ctx) { | ||||
ctx->pre_g = NULL; | ctx->pre_g = NULL; | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
ctx->pre_g_128 = NULL; | ctx->pre_g_128 = NULL; | ||||
#endif | #endif | ||||
} | } | ||||
static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, const secp256k1_callback *cb) { | static void secp256k1_ecmult_context_build(secp256k1_ecmult_context *ctx, void **prealloc) { | ||||
secp256k1_gej gj; | secp256k1_gej gj; | ||||
void* const base = *prealloc; | |||||
size_t const prealloc_size = SECP256K1_ECMULT_CONTEXT_PREALLOCATED_SIZE; | |||||
if (ctx->pre_g != NULL) { | if (ctx->pre_g != NULL) { | ||||
return; | return; | ||||
} | } | ||||
/* get the generator */ | /* get the generator */ | ||||
secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g); | secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g); | ||||
{ | { | ||||
size_t size = sizeof((*ctx->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); | size_t size = sizeof((*ctx->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); | ||||
/* check for overflow */ | /* check for overflow */ | ||||
VERIFY_CHECK(size / sizeof((*ctx->pre_g)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); | VERIFY_CHECK(size / sizeof((*ctx->pre_g)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); | ||||
ctx->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); | ctx->pre_g = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size); | ||||
} | } | ||||
/* precompute the tables with odd multiples */ | /* precompute the tables with odd multiples */ | ||||
secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g, &gj); | secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g, &gj); | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
{ | { | ||||
secp256k1_gej g_128j; | secp256k1_gej g_128j; | ||||
int i; | int i; | ||||
size_t size = sizeof((*ctx->pre_g_128)[0]) * ((size_t) ECMULT_TABLE_SIZE(WINDOW_G)); | size_t size = sizeof((*ctx->pre_g_128)[0]) * ((size_t) ECMULT_TABLE_SIZE(WINDOW_G)); | ||||
/* check for overflow */ | /* check for overflow */ | ||||
VERIFY_CHECK(size / sizeof((*ctx->pre_g_128)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); | VERIFY_CHECK(size / sizeof((*ctx->pre_g_128)[0]) == ((size_t)ECMULT_TABLE_SIZE(WINDOW_G))); | ||||
ctx->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); | ctx->pre_g_128 = (secp256k1_ge_storage (*)[])manual_alloc(prealloc, sizeof((*ctx->pre_g_128)[0]) * ECMULT_TABLE_SIZE(WINDOW_G), base, prealloc_size); | ||||
/* calculate 2^128*generator */ | /* calculate 2^128*generator */ | ||||
g_128j = gj; | g_128j = gj; | ||||
for (i = 0; i < 128; i++) { | for (i = 0; i < 128; i++) { | ||||
secp256k1_gej_double_var(&g_128j, &g_128j, NULL); | secp256k1_gej_double_var(&g_128j, &g_128j, NULL); | ||||
} | } | ||||
secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g_128, &g_128j); | secp256k1_ecmult_odd_multiples_table_storage_var(ECMULT_TABLE_SIZE(WINDOW_G), *ctx->pre_g_128, &g_128j); | ||||
} | } | ||||
#endif | #endif | ||||
} | } | ||||
static void secp256k1_ecmult_context_clone(secp256k1_ecmult_context *dst, | static void secp256k1_ecmult_context_finalize_memcpy(secp256k1_ecmult_context *dst, const secp256k1_ecmult_context *src) { | ||||
const secp256k1_ecmult_context *src, const secp256k1_callback *cb) { | if (src->pre_g != NULL) { | ||||
if (src->pre_g == NULL) { | /* We cast to void* first to suppress a -Wcast-align warning. */ | ||||
dst->pre_g = NULL; | dst->pre_g = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g) - (unsigned char*)src)); | ||||
} else { | |||||
size_t size = sizeof((*dst->pre_g)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); | |||||
dst->pre_g = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); | |||||
memcpy(dst->pre_g, src->pre_g, size); | |||||
} | } | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
if (src->pre_g_128 == NULL) { | if (src->pre_g_128 != NULL) { | ||||
dst->pre_g_128 = NULL; | dst->pre_g_128 = (secp256k1_ge_storage (*)[])(void*)((unsigned char*)dst + ((unsigned char*)(src->pre_g_128) - (unsigned char*)src)); | ||||
} else { | |||||
size_t size = sizeof((*dst->pre_g_128)[0]) * ((size_t)ECMULT_TABLE_SIZE(WINDOW_G)); | |||||
dst->pre_g_128 = (secp256k1_ge_storage (*)[])checked_malloc(cb, size); | |||||
memcpy(dst->pre_g_128, src->pre_g_128, size); | |||||
} | } | ||||
#endif | #endif | ||||
} | } | ||||
static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx) { | static int secp256k1_ecmult_context_is_built(const secp256k1_ecmult_context *ctx) { | ||||
return ctx->pre_g != NULL; | return ctx->pre_g != NULL; | ||||
} | } | ||||
static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx) { | static void secp256k1_ecmult_context_clear(secp256k1_ecmult_context *ctx) { | ||||
free(ctx->pre_g); | |||||
#ifdef USE_ENDOMORPHISM | |||||
free(ctx->pre_g_128); | |||||
#endif | |||||
secp256k1_ecmult_context_init(ctx); | secp256k1_ecmult_context_init(ctx); | ||||
} | } | ||||
/** Convert a number to WNAF notation. The number becomes represented by sum(2^i * wnaf[i], i=0..bits), | /** Convert a number to WNAF notation. The number becomes represented by sum(2^i * wnaf[i], i=0..bits), | ||||
* with the following guarantees: | * with the following guarantees: | ||||
* - each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1) | * - each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1) | ||||
* - two non-zero entries in wnaf are separated by at least w-1 zeroes. | * - two non-zero entries in wnaf are separated by at least w-1 zeroes. | ||||
* - the number of set values in wnaf is returned. This number is at most 256, and at most one more | * - the number of set values in wnaf is returned. This number is at most 256, and at most one more | ||||
Show All 40 Lines | while (bit < len) { | ||||
last_set_bit = bit; | last_set_bit = bit; | ||||
bit += now; | bit += now; | ||||
} | } | ||||
#ifdef VERIFY | #ifdef VERIFY | ||||
CHECK(carry == 0); | CHECK(carry == 0); | ||||
while (bit < 256) { | while (bit < 256) { | ||||
CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0); | CHECK(secp256k1_scalar_get_bits(&s, bit++, 1) == 0); | ||||
} | } | ||||
#endif | #endif | ||||
return last_set_bit + 1; | return last_set_bit + 1; | ||||
} | } | ||||
struct secp256k1_strauss_point_state { | struct secp256k1_strauss_point_state { | ||||
#ifdef USE_ENDOMORPHISM | #ifdef USE_ENDOMORPHISM | ||||
secp256k1_scalar na_1, na_lam; | secp256k1_scalar na_1, na_lam; | ||||
int wnaf_na_1[130]; | int wnaf_na_1[130]; | ||||
▲ Show 20 Lines • Show All 754 Lines • Show Last 20 Lines |