src/ecmult_impl.h

   1 /**********************************************************************
   2  * Copyright (c) 2013, 2014 Pieter Wuille                             *
   3  * Distributed under the MIT software license, see the accompanying   *
   4  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
   5  **********************************************************************/
   6
   7 #ifndef _SECP256K1_ECMULT_IMPL_H_
   8 #define _SECP256K1_ECMULT_IMPL_H_
   9
  10 #include "group.h"
  11 #include "scalar.h"
  12 #include "ecmult.h"
  13
  14 /* optimal for 128-bit and 256-bit exponents. */
  15 #define WINDOW_A 5
  16
  17 /** larger numbers may result in slightly better performance, at the cost of
  18     exponentially larger precomputed tables. */
  19 #ifdef USE_ENDOMORPHISM
  20 /** Two tables for window size 15: 1.375 MiB. */
  21 #define WINDOW_G 15
  22 #else
  23 /** One table for window size 16: 1.375 MiB. */
  24 #define WINDOW_G 16
  25 #endif
  26
  27 /** Fill a table 'pre' with precomputed odd multiples of a. W determines the size of the table.
  28  *  pre will contains the values [1*a,3*a,5*a,...,(2^(w-1)-1)*a], so it needs place for
  29  *  2^(w-2) entries.
  30  *
  31  *  There are two versions of this function:
  32  *  - secp256k1_ecmult_precomp_wnaf_gej, which operates on group elements in jacobian notation,
  33  *    fast to precompute, but slower to use in later additions.
  34  *  - secp256k1_ecmult_precomp_wnaf_ge, which operates on group elements in affine notations,
  35  *    (much) slower to precompute, but a bit faster to use in later additions.
  36  *  To compute a*P + b*G, we use the jacobian version for P, and the affine version for G, as
  37  *  G is constant, so it only needs to be done once in advance.
  38  */
  39 static void secp256k1_ecmult_table_precomp_gej_var(secp256k1_gej_t *pre, const secp256k1_gej_t *a, int w) {
  40     secp256k1_gej_t d;
  41     int i;
  42     pre[0] = *a;
  43     secp256k1_gej_double_var(&d, &pre[0]);
  44     for (i = 1; i < (1 << (w-2)); i++) {
  45         secp256k1_gej_add_var(&pre[i], &d, &pre[i-1]);
  46     }
  47 }
  48
  49 static void secp256k1_ecmult_table_precomp_ge_storage_var(secp256k1_ge_storage_t *pre, const secp256k1_gej_t *a, int w) {
  50     secp256k1_gej_t d;
  51     int i;
  52     const int table_size = 1 << (w-2);
  53     secp256k1_gej_t *prej = checked_malloc(sizeof(secp256k1_gej_t) * table_size);
  54     secp256k1_ge_t *prea = checked_malloc(sizeof(secp256k1_ge_t) * table_size);
  55     prej[0] = *a;
  56     secp256k1_gej_double_var(&d, a);
  57     for (i = 1; i < table_size; i++) {
  58         secp256k1_gej_add_var(&prej[i], &d, &prej[i-1]);
  59     }
  60     secp256k1_ge_set_all_gej_var(table_size, prea, prej);
  61     for (i = 0; i < table_size; i++) {
  62         secp256k1_ge_to_storage(&pre[i], &prea[i]);
  63     }
  64     free(prej);
  65     free(prea);
  66 }
  67
  68 /** The number of entries a table with precomputed multiples needs to have. */
  69 #define ECMULT_TABLE_SIZE(w) (1 << ((w)-2))
  70
  71 /** The following two macro retrieves a particular odd multiple from a table
  72  *  of precomputed multiples. */
  73 #define ECMULT_TABLE_GET_GEJ(r,pre,n,w) do { \
  74     VERIFY_CHECK(((n) & 1) == 1); \
  75     VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
  76     VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
  77     if ((n) > 0) { \
  78         *(r) = (pre)[((n)-1)/2]; \
  79     } else { \
  80         secp256k1_gej_neg((r), &(pre)[(-(n)-1)/2]); \
  81     } \
  82 } while(0)
  83 #define ECMULT_TABLE_GET_GE_STORAGE(r,pre,n,w) do { \
  84     VERIFY_CHECK(((n) & 1) == 1); \
  85     VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
  86     VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1)); \
  87     if ((n) > 0) { \
  88         secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
  89     } else { \
  90         secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
  91         secp256k1_ge_neg((r), (r)); \
  92     } \
  93 } while(0)
  94
  95 typedef struct {
  96     /* For accelerating the computation of a*P + b*G: */
  97     secp256k1_ge_storage_t pre_g[ECMULT_TABLE_SIZE(WINDOW_G)];    /* odd multiples of the generator */
  98 #ifdef USE_ENDOMORPHISM
  99     secp256k1_ge_storage_t pre_g_128[ECMULT_TABLE_SIZE(WINDOW_G)]; /* odd multiples of 2^128*generator */
 100 #endif
 101 } secp256k1_ecmult_consts_t;
 102
 103 static const secp256k1_ecmult_consts_t *secp256k1_ecmult_consts = NULL;
 104
 105 static void secp256k1_ecmult_start(void) {
 106     secp256k1_gej_t gj;
 107     secp256k1_ecmult_consts_t *ret;
 108     if (secp256k1_ecmult_consts != NULL) {
 109         return;
 110     }
 111
 112     /* Allocate the precomputation table. */
 113     ret = (secp256k1_ecmult_consts_t*)checked_malloc(sizeof(secp256k1_ecmult_consts_t));
 114
 115     /* get the generator */
 116     secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g);
 117
 118
 119     /* precompute the tables with odd multiples */
 120     secp256k1_ecmult_table_precomp_ge_storage_var(ret->pre_g, &gj, WINDOW_G);
 121
 122 #ifdef USE_ENDOMORPHISM
 123     {
 124         secp256k1_gej_t g_128j;
 125         int i;
 126         /* calculate 2^128*generator */
 127         g_128j = gj;
 128         for (i = 0; i < 128; i++) {
 129             secp256k1_gej_double_var(&g_128j, &g_128j);
 130         }
 131         secp256k1_ecmult_table_precomp_ge_storage_var(ret->pre_g_128, &g_128j, WINDOW_G);
 132     }
 133 #endif
 134
 135     /* Set the global pointer to the precomputation table. */
 136     secp256k1_ecmult_consts = ret;
 137 }
 138
 139 static void secp256k1_ecmult_stop(void) {
 140     secp256k1_ecmult_consts_t *c;
 141     if (secp256k1_ecmult_consts == NULL) {
 142         return;
 143     }
 144
 145     c = (secp256k1_ecmult_consts_t*)secp256k1_ecmult_consts;
 146     secp256k1_ecmult_consts = NULL;
 147     free(c);
 148 }
 149
 150 /** Convert a number to WNAF notation. The number becomes represented by sum(2^i * wnaf[i], i=0..bits),
 151  *  with the following guarantees:
 152  *  - each wnaf[i] is either 0, or an odd integer between -(1<<(w-1) - 1) and (1<<(w-1) - 1)
 153  *  - two non-zero entries in wnaf are separated by at least w-1 zeroes.
 154  *  - the number of set values in wnaf is returned. This number is at most 256, and at most one more
 155  *  - than the number of bits in the (absolute value) of the input.
 156  */
 157 static int secp256k1_ecmult_wnaf(int *wnaf, const secp256k1_scalar_t *a, int w) {
 158     secp256k1_scalar_t s = *a;
 159     int set_bits = 0;
 160     int bit = 0;
 161     int sign = 1;
 162
 163     if (secp256k1_scalar_get_bits(&s, 255, 1)) {
 164         secp256k1_scalar_negate(&s, &s);
 165         sign = -1;
 166     }
 167
 168     while (bit < 256) {
 169         int now;
 170         int word;
 171         if (secp256k1_scalar_get_bits(&s, bit, 1) == 0) {
 172             bit++;
 173             continue;
 174         }
 175         while (set_bits < bit) {
 176             wnaf[set_bits++] = 0;
 177         }
 178         now = w;
 179         if (bit + now > 256) {
 180             now = 256 - bit;
 181         }
 182         word = secp256k1_scalar_get_bits_var(&s, bit, now);
 183         if (word & (1 << (w-1))) {
 184             secp256k1_scalar_add_bit(&s, bit + w);
 185             wnaf[set_bits++] = sign * (word - (1 << w));
 186         } else {
 187             wnaf[set_bits++] = sign * word;
 188         }
 189         bit += now;
 190     }
 191     return set_bits;
 192 }
 193
 194 static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_scalar_t *na, const secp256k1_scalar_t *ng) {
 195     secp256k1_gej_t tmpj;
 196     secp256k1_gej_t pre_a[ECMULT_TABLE_SIZE(WINDOW_A)];
 197     secp256k1_ge_t tmpa;
 198     const secp256k1_ecmult_consts_t *c = secp256k1_ecmult_consts;
 199 #ifdef USE_ENDOMORPHISM
 200     secp256k1_gej_t pre_a_lam[ECMULT_TABLE_SIZE(WINDOW_A)];
 201     secp256k1_scalar_t na_1, na_lam;
 202     /* Splitted G factors. */
 203     secp256k1_scalar_t ng_1, ng_128;
 204     int wnaf_na_1[130];
 205     int wnaf_na_lam[130];
 206     int bits_na_1;
 207     int bits_na_lam;
 208     int wnaf_ng_1[129];
 209     int bits_ng_1;
 210     int wnaf_ng_128[129];
 211     int bits_ng_128;
 212 #else
 213     int wnaf_na[256];
 214     int bits_na;
 215     int wnaf_ng[257];
 216     int bits_ng;
 217 #endif
 218     int i;
 219     int bits;
 220
 221 #ifdef USE_ENDOMORPHISM
 222     /* split na into na_1 and na_lam (where na = na_1 + na_lam*lambda, and na_1 and na_lam are ~128 bit) */
 223     secp256k1_scalar_split_lambda_var(&na_1, &na_lam, na);
 224
 225     /* build wnaf representation for na_1 and na_lam. */
 226     bits_na_1   = secp256k1_ecmult_wnaf(wnaf_na_1,   &na_1,   WINDOW_A);
 227     bits_na_lam = secp256k1_ecmult_wnaf(wnaf_na_lam, &na_lam, WINDOW_A);
 228     VERIFY_CHECK(bits_na_1 <= 130);
 229     VERIFY_CHECK(bits_na_lam <= 130);
 230     bits = bits_na_1;
 231     if (bits_na_lam > bits) {
 232         bits = bits_na_lam;
 233     }
 234 #else
 235     /* build wnaf representation for na. */
 236     bits_na     = secp256k1_ecmult_wnaf(wnaf_na,     na,      WINDOW_A);
 237     bits = bits_na;
 238 #endif
 239
 240     /* calculate odd multiples of a */
 241     secp256k1_ecmult_table_precomp_gej_var(pre_a, a, WINDOW_A);
 242
 243 #ifdef USE_ENDOMORPHISM
 244     for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
 245         secp256k1_gej_mul_lambda(&pre_a_lam[i], &pre_a[i]);
 246     }
 247
 248     /* 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) */
 249     secp256k1_scalar_split_128(&ng_1, &ng_128, ng);
 250
 251     /* Build wnaf representation for ng_1 and ng_128 */
 252     bits_ng_1   = secp256k1_ecmult_wnaf(wnaf_ng_1,   &ng_1,   WINDOW_G);
 253     bits_ng_128 = secp256k1_ecmult_wnaf(wnaf_ng_128, &ng_128, WINDOW_G);
 254     if (bits_ng_1 > bits) {
 255         bits = bits_ng_1;
 256     }
 257     if (bits_ng_128 > bits) {
 258         bits = bits_ng_128;
 259     }
 260 #else
 261     bits_ng     = secp256k1_ecmult_wnaf(wnaf_ng,     ng,      WINDOW_G);
 262     if (bits_ng > bits) {
 263         bits = bits_ng;
 264     }
 265 #endif
 266
 267     secp256k1_gej_set_infinity(r);
 268
 269     for (i = bits-1; i >= 0; i--) {
 270         int n;
 271         secp256k1_gej_double_var(r, r);
 272 #ifdef USE_ENDOMORPHISM
 273         if (i < bits_na_1 && (n = wnaf_na_1[i])) {
 274             ECMULT_TABLE_GET_GEJ(&tmpj, pre_a, n, WINDOW_A);
 275             secp256k1_gej_add_var(r, r, &tmpj);
 276         }
 277         if (i < bits_na_lam && (n = wnaf_na_lam[i])) {
 278             ECMULT_TABLE_GET_GEJ(&tmpj, pre_a_lam, n, WINDOW_A);
 279             secp256k1_gej_add_var(r, r, &tmpj);
 280         }
 281         if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
 282             ECMULT_TABLE_GET_GE_STORAGE(&tmpa, c->pre_g, n, WINDOW_G);
 283             secp256k1_gej_add_ge_var(r, r, &tmpa);
 284         }
 285         if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
 286             ECMULT_TABLE_GET_GE_STORAGE(&tmpa, c->pre_g_128, n, WINDOW_G);
 287             secp256k1_gej_add_ge_var(r, r, &tmpa);
 288         }
 289 #else
 290         if (i < bits_na && (n = wnaf_na[i])) {
 291             ECMULT_TABLE_GET_GEJ(&tmpj, pre_a, n, WINDOW_A);
 292             secp256k1_gej_add_var(r, r, &tmpj);
 293         }
 294         if (i < bits_ng && (n = wnaf_ng[i])) {
 295             ECMULT_TABLE_GET_GE_STORAGE(&tmpa, c->pre_g, n, WINDOW_G);
 296             secp256k1_gej_add_ge_var(r, r, &tmpa);
 297         }
 298 #endif
 299     }
 300 }
 301
 302 #endif