noinst_HEADERS += src/ecdsa_impl.h
noinst_HEADERS += src/ecmult.h
noinst_HEADERS += src/ecmult_impl.h
+noinst_HEADERS += src/ecmult_gen.h
+noinst_HEADERS += src/ecmult_gen_impl.h
noinst_HEADERS += src/num.h
noinst_HEADERS += src/num_impl.h
noinst_HEADERS += src/field_10x26.h
#include "field.h"
#include "group.h"
#include "ecmult.h"
+#include "ecmult_gen.h"
#include "ecdsa.h"
void static secp256k1_ecdsa_sig_init(secp256k1_ecdsa_sig_t *r) {
-// Copyright (c) 2013 Pieter Wuille
-// Distributed under the MIT/X11 software license, see the accompanying
+// Copyright (c) 2013-2014 Pieter Wuille
+// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#ifndef _SECP256K1_ECMULT_
static void secp256k1_ecmult_start(void);
static void secp256k1_ecmult_stop(void);
-/** Multiply with the generator: R = a*G */
-static void secp256k1_ecmult_gen(secp256k1_gej_t *r, const secp256k1_num_t *a);
/** Double multiply: R = na*A + ng*G */
static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_num_t *na, const secp256k1_num_t *ng);
--- /dev/null
+// Copyright (c) 2013-2014 Pieter Wuille
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef _SECP256K1_ECMULT_GEN_
+#define _SECP256K1_ECMULT_GEN_
+
+#include "num.h"
+#include "group.h"
+
+static void secp256k1_ecmult_gen_start(void);
+static void secp256k1_ecmult_gen_stop(void);
+
+/** Multiply with the generator: R = a*G */
+static void secp256k1_ecmult_gen(secp256k1_gej_t *r, const secp256k1_num_t *a);
+
+#endif
--- /dev/null
+// Copyright (c) 2013-2014 Pieter Wuille
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef _SECP256K1_ECMULT_GEN_IMPL_H_
+#define _SECP256K1_ECMULT_GEN_IMPL_H_
+
+#include <assert.h>
+#include "num.h"
+#include "group.h"
+#include "ecmult_gen.h"
+
+typedef struct {
+ // For accelerating the computation of a*G:
+ // To harden against timing attacks, use the following mechanism:
+ // * Break up the multiplicand into groups of 4 bits, called n_0, n_1, n_2, ..., n_63.
+ // * Compute sum(n_i * 16^i * G + U_i, i=0..63), where:
+ // * U_i = U * 2^i (for i=0..62)
+ // * U_i = U * (1-2^63) (for i=63)
+ // where U is a point with no known corresponding scalar. Note that sum(U_i, i=0..63) = 0.
+ // For each i, and each of the 16 possible values of n_i, (n_i * 16^i * G + U_i) is
+ // precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0..63).
+ // None of the resulting prec group elements have a known scalar, and neither do any of
+ // the intermediate sums while computing a*G.
+ // To make memory access uniform, the bytes of prec(i, n_i) are sliced per value of n_i.
+ unsigned char prec[64][sizeof(secp256k1_ge_t)][16]; // prec[j][k][i] = k'th byte of (16^j * i * G + U_i)
+} secp256k1_ecmult_gen_consts_t;
+
+static const secp256k1_ecmult_gen_consts_t *secp256k1_ecmult_gen_consts = NULL;
+
+static void secp256k1_ecmult_gen_start(void) {
+ if (secp256k1_ecmult_gen_consts != NULL)
+ return;
+
+ // Allocate the precomputation table.
+ secp256k1_ecmult_gen_consts_t *ret = (secp256k1_ecmult_gen_consts_t*)malloc(sizeof(secp256k1_ecmult_gen_consts_t));
+
+ // get the generator
+ const secp256k1_ge_t *g = &secp256k1_ge_consts->g;
+ secp256k1_gej_t gj; secp256k1_gej_set_ge(&gj, g);
+
+ // Construct a group element with no known corresponding scalar (nothing up my sleeve).
+ secp256k1_gej_t nums_gej;
+ {
+ static const unsigned char nums_b32[32] = "The scalar for this x is unknown";
+ secp256k1_fe_t nums_x;
+ secp256k1_fe_set_b32(&nums_x, nums_b32);
+ secp256k1_ge_t nums_ge;
+ VERIFY_CHECK(secp256k1_ge_set_xo(&nums_ge, &nums_x, 0));
+ secp256k1_gej_set_ge(&nums_gej, &nums_ge);
+ // Add G to make the bits in x uniformly distributed.
+ secp256k1_gej_add_ge(&nums_gej, &nums_gej, g);
+ }
+
+ // compute prec.
+ secp256k1_ge_t prec[1024];
+ {
+ secp256k1_gej_t precj[1024]; // Jacobian versions of prec.
+ int j = 0;
+ secp256k1_gej_t gbase; gbase = gj; // 16^j * G
+ secp256k1_gej_t numsbase; numsbase = nums_gej; // 2^j * nums.
+ for (int j=0; j<64; j++) {
+ // Set precj[j*16 .. j*16+15] to (numsbase, numsbase + gbase, ..., numsbase + 15*gbase).
+ precj[j*16] = numsbase;
+ for (int i=1; i<16; i++) {
+ secp256k1_gej_add(&precj[j*16 + i], &precj[j*16 + i - 1], &gbase);
+ }
+ // Multiply gbase by 16.
+ for (int i=0; i<4; i++) {
+ secp256k1_gej_double(&gbase, &gbase);
+ }
+ // Multiply numbase by 2.
+ secp256k1_gej_double(&numsbase, &numsbase);
+ if (j == 62) {
+ // In the last iteration, numsbase is (1 - 2^j) * nums instead.
+ secp256k1_gej_neg(&numsbase, &numsbase);
+ secp256k1_gej_add(&numsbase, &numsbase, &nums_gej);
+ }
+ }
+ secp256k1_ge_set_all_gej(1024, prec, precj);
+ }
+ for (int j=0; j<64; j++) {
+ for (int i=0; i<16; i++) {
+ const unsigned char* raw = (const unsigned char*)(&prec[j*16 + i]);
+ for (int k=0; k<sizeof(secp256k1_ge_t); k++)
+ ret->prec[j][k][i] = raw[k];
+ }
+ }
+
+ // Set the global pointer to the precomputation table.
+ secp256k1_ecmult_gen_consts = ret;
+}
+
+static void secp256k1_ecmult_gen_stop(void) {
+ if (secp256k1_ecmult_gen_consts == NULL)
+ return;
+
+ secp256k1_ecmult_gen_consts_t *c = (secp256k1_ecmult_gen_consts_t*)secp256k1_ecmult_gen_consts;
+ secp256k1_ecmult_gen_consts = NULL;
+ free(c);
+}
+
+void static secp256k1_ecmult_gen(secp256k1_gej_t *r, const secp256k1_num_t *gn) {
+ secp256k1_num_t n;
+ secp256k1_num_init(&n);
+ secp256k1_num_copy(&n, gn);
+ const secp256k1_ecmult_gen_consts_t *c = secp256k1_ecmult_gen_consts;
+ secp256k1_gej_set_infinity(r);
+ secp256k1_ge_t add;
+ int bits;
+ for (int j=0; j<64; j++) {
+ bits = secp256k1_num_shift(&n, 4);
+ for (int k=0; k<sizeof(secp256k1_ge_t); k++)
+ ((unsigned char*)(&add))[k] = c->prec[j][k][bits];
+ secp256k1_gej_add_ge(r, r, &add);
+ }
+ bits = 0;
+ secp256k1_ge_clear(&add);
+ secp256k1_num_clear(&n);
+ secp256k1_num_free(&n);
+}
+
+#endif
-// Copyright (c) 2013 Pieter Wuille
-// Distributed under the MIT/X11 software license, see the accompanying
+// Copyright (c) 2013-2014 Pieter Wuille
+// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#ifndef _SECP256K1_ECMULT_IMPL_H_
secp256k1_ge_t pre_g_128[ECMULT_TABLE_SIZE(WINDOW_G)]; // odd multiples of 2^128*generator
} secp256k1_ecmult_consts_t;
-typedef struct {
- // For accelerating the computation of a*G:
- // To harden against timing attacks, use the following mechanism:
- // * Break up the multiplicand into groups of 4 bits, called n_0, n_1, n_2, ..., n_63.
- // * Compute sum(n_i * 16^i * G + U_i, i=0..63), where:
- // * U_i = U * 2^i (for i=0..62)
- // * U_i = U * (1-2^63) (for i=63)
- // where U is a point with no known corresponding scalar. Note that sum(U_i, i=0..63) = 0.
- // For each i, and each of the 16 possible values of n_i, (n_i * 16^i * G + U_i) is
- // precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0..63).
- // None of the resulting prec group elements have a known scalar, and neither do any of
- // the intermediate sums while computing a*G.
- // To make memory access uniform, the bytes of prec(i, n_i) are sliced per value of n_i.
- unsigned char prec[64][sizeof(secp256k1_ge_t)][16]; // prec[j][k][i] = k'th byte of (16^j * i * G + U_i)
-} secp256k1_ecmult_gen_consts_t;
-
static const secp256k1_ecmult_consts_t *secp256k1_ecmult_consts = NULL;
-static const secp256k1_ecmult_gen_consts_t *secp256k1_ecmult_gen_consts = NULL;
static void secp256k1_ecmult_start(void) {
if (secp256k1_ecmult_consts != NULL)
secp256k1_ecmult_consts = ret;
}
-static void secp256k1_ecmult_gen_start(void) {
- if (secp256k1_ecmult_gen_consts != NULL)
- return;
-
- // Allocate the precomputation table.
- secp256k1_ecmult_gen_consts_t *ret = (secp256k1_ecmult_gen_consts_t*)malloc(sizeof(secp256k1_ecmult_gen_consts_t));
-
- // get the generator
- const secp256k1_ge_t *g = &secp256k1_ge_consts->g;
- secp256k1_gej_t gj; secp256k1_gej_set_ge(&gj, g);
-
- // Construct a group element with no known corresponding scalar (nothing up my sleeve).
- secp256k1_gej_t nums_gej;
- {
- static const unsigned char nums_b32[32] = "The scalar for this x is unknown";
- secp256k1_fe_t nums_x;
- secp256k1_fe_set_b32(&nums_x, nums_b32);
- secp256k1_ge_t nums_ge;
- VERIFY_CHECK(secp256k1_ge_set_xo(&nums_ge, &nums_x, 0));
- secp256k1_gej_set_ge(&nums_gej, &nums_ge);
- // Add G to make the bits in x uniformly distributed.
- secp256k1_gej_add_ge(&nums_gej, &nums_gej, g);
- }
-
- // compute prec.
- secp256k1_ge_t prec[1024];
- {
- secp256k1_gej_t precj[1024]; // Jacobian versions of prec.
- int j = 0;
- secp256k1_gej_t gbase; gbase = gj; // 16^j * G
- secp256k1_gej_t numsbase; numsbase = nums_gej; // 2^j * nums.
- for (int j=0; j<64; j++) {
- // Set precj[j*16 .. j*16+15] to (numsbase, numsbase + gbase, ..., numsbase + 15*gbase).
- precj[j*16] = numsbase;
- for (int i=1; i<16; i++) {
- secp256k1_gej_add(&precj[j*16 + i], &precj[j*16 + i - 1], &gbase);
- }
- // Multiply gbase by 16.
- for (int i=0; i<4; i++) {
- secp256k1_gej_double(&gbase, &gbase);
- }
- // Multiply numbase by 2.
- secp256k1_gej_double(&numsbase, &numsbase);
- if (j == 62) {
- // In the last iteration, numsbase is (1 - 2^j) * nums instead.
- secp256k1_gej_neg(&numsbase, &numsbase);
- secp256k1_gej_add(&numsbase, &numsbase, &nums_gej);
- }
- }
- secp256k1_ge_set_all_gej(1024, prec, precj);
- }
- for (int j=0; j<64; j++) {
- for (int i=0; i<16; i++) {
- const unsigned char* raw = (const unsigned char*)(&prec[j*16 + i]);
- for (int k=0; k<sizeof(secp256k1_ge_t); k++)
- ret->prec[j][k][i] = raw[k];
- }
- }
-
- // Set the global pointer to the precomputation table.
- secp256k1_ecmult_gen_consts = ret;
-}
-
static void secp256k1_ecmult_stop(void) {
if (secp256k1_ecmult_consts == NULL)
return;
free(c);
}
-static void secp256k1_ecmult_gen_stop(void) {
- if (secp256k1_ecmult_gen_consts == NULL)
- return;
-
- secp256k1_ecmult_gen_consts_t *c = (secp256k1_ecmult_gen_consts_t*)secp256k1_ecmult_gen_consts;
- secp256k1_ecmult_gen_consts = NULL;
- free(c);
-}
-
/** Convert a number to WNAF notation. The number becomes represented by sum(2^i * wnaf[i], i=0..bits),
* with the following guarantees:
* - each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1)
return ret;
}
-void static secp256k1_ecmult_gen(secp256k1_gej_t *r, const secp256k1_num_t *gn) {
- secp256k1_num_t n;
- secp256k1_num_init(&n);
- secp256k1_num_copy(&n, gn);
- const secp256k1_ecmult_gen_consts_t *c = secp256k1_ecmult_gen_consts;
- secp256k1_gej_set_infinity(r);
- secp256k1_ge_t add;
- int bits;
- for (int j=0; j<64; j++) {
- bits = secp256k1_num_shift(&n, 4);
- for (int k=0; k<sizeof(secp256k1_ge_t); k++)
- ((unsigned char*)(&add))[k] = c->prec[j][k][bits];
- secp256k1_gej_add_ge(r, r, &add);
- }
- bits = 0;
- secp256k1_ge_clear(&add);
- secp256k1_num_clear(&n);
- secp256k1_num_free(&n);
-}
-
void static secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_num_t *na, const secp256k1_num_t *ng) {
const secp256k1_ecmult_consts_t *c = secp256k1_ecmult_consts;
#include "field_impl.h"
#include "group_impl.h"
#include "ecmult_impl.h"
+#include "ecmult_gen_impl.h"
#include "ecdsa_impl.h"
void secp256k1_start(unsigned int flags) {
projects / secp256k1.git / commitdiff