aboutsummaryrefslogtreecommitdiff
path: root/src/ecmult_impl.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/ecmult_impl.h')
-rw-r--r--src/ecmult_impl.h99
1 files changed, 61 insertions, 38 deletions
diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h
index 508902564e..445b81593f 100644
--- a/src/ecmult_impl.h
+++ b/src/ecmult_impl.h
@@ -7,8 +7,8 @@
#ifndef _SECP256K1_ECMULT_IMPL_H_
#define _SECP256K1_ECMULT_IMPL_H_
-#include "num.h"
#include "group.h"
+#include "scalar.h"
#include "ecmult.h"
/* optimal for 128-bit and 256-bit exponents. */
@@ -16,7 +16,11 @@
/** larger numbers may result in slightly better performance, at the cost of
exponentially larger precomputed tables. WINDOW_G == 14 results in 640 KiB. */
+#ifdef USE_ENDOMORPHISM
#define WINDOW_G 14
+#else
+#define WINDOW_G 15
+#endif
/** Fill a table 'pre' with precomputed odd multiples of a. W determines the size of the table.
* pre will contains the values [1*a,3*a,5*a,...,(2^(w-1)-1)*a], so it needs place for
@@ -69,7 +73,9 @@ static void secp256k1_ecmult_table_precomp_ge_var(secp256k1_ge_t *pre, const sec
typedef struct {
/* For accelerating the computation of a*P + b*G: */
secp256k1_ge_t pre_g[ECMULT_TABLE_SIZE(WINDOW_G)]; /* odd multiples of the generator */
+#ifdef USE_ENDOMORPHISM
secp256k1_ge_t pre_g_128[ECMULT_TABLE_SIZE(WINDOW_G)]; /* odd multiples of 2^128*generator */
+#endif
} secp256k1_ecmult_consts_t;
static const secp256k1_ecmult_consts_t *secp256k1_ecmult_consts = NULL;
@@ -85,14 +91,18 @@ static void secp256k1_ecmult_start(void) {
const secp256k1_ge_t *g = &secp256k1_ge_consts->g;
secp256k1_gej_t gj; secp256k1_gej_set_ge(&gj, g);
+#ifdef USE_ENDOMORPHISM
/* calculate 2^128*generator */
secp256k1_gej_t g_128j = gj;
for (int i=0; i<128; i++)
secp256k1_gej_double_var(&g_128j, &g_128j);
+#endif
/* precompute the tables with odd multiples */
secp256k1_ecmult_table_precomp_ge_var(ret->pre_g, &gj, WINDOW_G);
+#ifdef USE_ENDOMORPHISM
secp256k1_ecmult_table_precomp_ge_var(ret->pre_g_128, &g_128j, WINDOW_G);
+#endif
/* Set the global pointer to the precomputation table. */
secp256k1_ecmult_consts = ret;
@@ -111,56 +121,62 @@ static void secp256k1_ecmult_stop(void) {
* with the following guarantees:
* - 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.
- * - the index of the highest non-zero entry in wnaf (=return value-1) is at most bits, where
- * bits is the number of bits necessary to represent the absolute value of the input.
+ * - the number of set values in wnaf is returned. This number is at most 256, and at most one more
+ * - than the number of bits in the (absolute value) of the input.
*/
-static int secp256k1_ecmult_wnaf(int *wnaf, const secp256k1_num_t *a, int w) {
- int ret = 0;
- int zeroes = 0;
- secp256k1_num_t x;
- secp256k1_num_copy(&x, a);
+static int secp256k1_ecmult_wnaf(int *wnaf, const secp256k1_scalar_t *a, int w) {
+ secp256k1_scalar_t s = *a;
+
int sign = 1;
- if (secp256k1_num_is_neg(&x)) {
+ if (secp256k1_scalar_get_bits(&s, 255, 1)) {
+ secp256k1_scalar_negate(&s, &s);
sign = -1;
- secp256k1_num_negate(&x);
}
- while (!secp256k1_num_is_zero(&x)) {
- while (!secp256k1_num_is_odd(&x)) {
- zeroes++;
- secp256k1_num_shift(&x, 1);
+
+ int set_bits = 0;
+ int bit = 0;
+ while (bit < 256) {
+ if (secp256k1_scalar_get_bits(&s, bit, 1) == 0) {
+ bit++;
+ continue;
+ }
+ while (set_bits < bit) {
+ wnaf[set_bits++] = 0;
}
- int word = secp256k1_num_shift(&x, w);
- while (zeroes) {
- wnaf[ret++] = 0;
- zeroes--;
+ int now = w;
+ if (bit + now > 256) {
+ now = 256 - bit;
}
+ int word = secp256k1_scalar_get_bits_var(&s, bit, now);
if (word & (1 << (w-1))) {
- secp256k1_num_inc(&x);
- wnaf[ret++] = sign * (word - (1 << w));
+ secp256k1_scalar_add_bit(&s, bit + w);
+ wnaf[set_bits++] = sign * (word - (1 << w));
} else {
- wnaf[ret++] = sign * word;
+ wnaf[set_bits++] = sign * word;
}
- zeroes = w-1;
+ bit += now;
}
- return ret;
+ return set_bits;
}
-static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_num_t *na, const secp256k1_num_t *ng) {
+static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_scalar_t *na, const secp256k1_scalar_t *ng) {
const secp256k1_ecmult_consts_t *c = secp256k1_ecmult_consts;
#ifdef USE_ENDOMORPHISM
- secp256k1_num_t na_1, na_lam;
+ secp256k1_scalar_t na_1, na_lam;
/* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
- secp256k1_gej_split_exp_var(&na_1, &na_lam, na);
+ secp256k1_scalar_split_lambda_var(&na_1, &na_lam, na);
/* build wnaf representation for na_1 and na_lam. */
- int wnaf_na_1[129]; int bits_na_1 = secp256k1_ecmult_wnaf(wnaf_na_1, &na_1, WINDOW_A);
- int wnaf_na_lam[129]; int bits_na_lam = secp256k1_ecmult_wnaf(wnaf_na_lam, &na_lam, WINDOW_A);
+ int wnaf_na_1[130]; int bits_na_1 = secp256k1_ecmult_wnaf(wnaf_na_1, &na_1, WINDOW_A);
+ int wnaf_na_lam[130]; int bits_na_lam = secp256k1_ecmult_wnaf(wnaf_na_lam, &na_lam, WINDOW_A);
+ VERIFY_CHECK(bits_na_1 <= 130);
+ VERIFY_CHECK(bits_na_lam <= 130);
int bits = bits_na_1;
if (bits_na_lam > bits) bits = bits_na_lam;
#else
/* build wnaf representation for na. */
- int wnaf_na[257]; int bits_na = secp256k1_ecmult_wnaf(wnaf_na, na, WINDOW_A);
+ int wnaf_na[256]; int bits_na = secp256k1_ecmult_wnaf(wnaf_na, na, WINDOW_A);
int bits = bits_na;
#endif
@@ -172,19 +188,22 @@ static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const
secp256k1_gej_t pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)];
for (int i=0; i<ECMULT_TABLE_SIZE(WINDOW_A); i++)
secp256k1_gej_mul_lambda(&pre_a_lam[i], &pre_a[i]);
-#endif
/* Splitted G factors. */
- secp256k1_num_t ng_1, ng_128;
+ secp256k1_scalar_t ng_1, ng_128;
/* split ng into ng_1 and ng_128 (where gn = gn_1 + gn_128*2^128, and gn_1 and gn_128 are ~128 bit) */
- secp256k1_num_split(&ng_1, &ng_128, ng, 128);
+ secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
/* Build wnaf representation for ng_1 and ng_128 */
int wnaf_ng_1[129]; int bits_ng_1 = secp256k1_ecmult_wnaf(wnaf_ng_1, &ng_1, WINDOW_G);
int wnaf_ng_128[129]; int bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, &ng_128, WINDOW_G);
if (bits_ng_1 > bits) bits = bits_ng_1;
if (bits_ng_128 > bits) bits = bits_ng_128;
+#else
+ int wnaf_ng[257]; int bits_ng = secp256k1_ecmult_wnaf(wnaf_ng, ng, WINDOW_G);
+ if (bits_ng > bits) bits = bits_ng;
+#endif
secp256k1_gej_set_infinity(r);
secp256k1_gej_t tmpj;
@@ -202,12 +221,6 @@ static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const
ECMULT_TABLE_GET_GEJ(&tmpj, pre_a_lam, n, WINDOW_A);
secp256k1_gej_add_var(r, r, &tmpj);
}
-#else
- if (i < bits_na && (n = wnaf_na[i])) {
- ECMULT_TABLE_GET_GEJ(&tmpj, pre_a, n, WINDOW_A);
- secp256k1_gej_add_var(r, r, &tmpj);
- }
-#endif
if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
ECMULT_TABLE_GET_GE(&tmpa, c->pre_g, n, WINDOW_G);
secp256k1_gej_add_ge_var(r, r, &tmpa);
@@ -216,6 +229,16 @@ static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const
ECMULT_TABLE_GET_GE(&tmpa, c->pre_g_128, n, WINDOW_G);
secp256k1_gej_add_ge_var(r, r, &tmpa);
}
+#else
+ if (i < bits_na && (n = wnaf_na[i])) {
+ ECMULT_TABLE_GET_GEJ(&tmpj, pre_a, n, WINDOW_A);
+ secp256k1_gej_add_var(r, r, &tmpj);
+ }
+ if (i < bits_ng && (n = wnaf_ng[i])) {
+ ECMULT_TABLE_GET_GE(&tmpa, c->pre_g, n, WINDOW_G);
+ secp256k1_gej_add_ge_var(r, r, &tmpa);
+ }
+#endif
}
}
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-15 15:31:38 +0000