src/ecmult_gen_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_GEN_IMPL_H_
   8 #define _SECP256K1_ECMULT_GEN_IMPL_H_
   9
  10 #include "scalar.h"
  11 #include "group.h"
  12 #include "ecmult_gen.h"
  13
  14 typedef struct {
  15     /* For accelerating the computation of a*G:
  16      * To harden against timing attacks, use the following mechanism:
  17      * * Break up the multiplicand into groups of 4 bits, called n_0, n_1, n_2, ..., n_63.
  18      * * Compute sum(n_i * 16^i * G + U_i, i=0..63), where:
  19      *   * U_i = U * 2^i (for i=0..62)
  20      *   * U_i = U * (1-2^63) (for i=63)
  21      *   where U is a point with no known corresponding scalar. Note that sum(U_i, i=0..63) = 0.
  22      * For each i, and each of the 16 possible values of n_i, (n_i * 16^i * G + U_i) is
  23      * precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0..63).
  24      * None of the resulting prec group elements have a known scalar, and neither do any of
  25      * the intermediate sums while computing a*G.
  26      */
  27     secp256k1_ge_storage_t prec[64][16]; /* prec[j][i] = 16^j * i * G + U_i */
  28 } secp256k1_ecmult_gen_consts_t;
  29
  30 static const secp256k1_ecmult_gen_consts_t *secp256k1_ecmult_gen_consts = NULL;
  31
  32 static void secp256k1_ecmult_gen_start(void) {
  33     secp256k1_ge_t prec[1024];
  34     secp256k1_gej_t gj;
  35     secp256k1_gej_t nums_gej;
  36     secp256k1_ecmult_gen_consts_t *ret;
  37     int i, j;
  38     if (secp256k1_ecmult_gen_consts != NULL) {
  39         return;
  40     }
  41
  42     /* Allocate the precomputation table. */
  43     ret = (secp256k1_ecmult_gen_consts_t*)checked_malloc(sizeof(secp256k1_ecmult_gen_consts_t));
  44
  45     /* get the generator */
  46     secp256k1_gej_set_ge(&gj, &secp256k1_ge_const_g);
  47
  48     /* Construct a group element with no known corresponding scalar (nothing up my sleeve). */
  49     {
  50         static const unsigned char nums_b32[33] = "The scalar for this x is unknown";
  51         secp256k1_fe_t nums_x;
  52         secp256k1_ge_t nums_ge;
  53         VERIFY_CHECK(secp256k1_fe_set_b32(&nums_x, nums_b32));
  54         VERIFY_CHECK(secp256k1_ge_set_xo_var(&nums_ge, &nums_x, 0));
  55         secp256k1_gej_set_ge(&nums_gej, &nums_ge);
  56         /* Add G to make the bits in x uniformly distributed. */
  57         secp256k1_gej_add_ge_var(&nums_gej, &nums_gej, &secp256k1_ge_const_g);
  58     }
  59
  60     /* compute prec. */
  61     {
  62         secp256k1_gej_t precj[1024]; /* Jacobian versions of prec. */
  63         secp256k1_gej_t gbase;
  64         secp256k1_gej_t numsbase;
  65         gbase = gj; /* 16^j * G */
  66         numsbase = nums_gej; /* 2^j * nums. */
  67         for (j = 0; j < 64; j++) {
  68             /* Set precj[j*16 .. j*16+15] to (numsbase, numsbase + gbase, ..., numsbase + 15*gbase). */
  69             precj[j*16] = numsbase;
  70             for (i = 1; i < 16; i++) {
  71                 secp256k1_gej_add_var(&precj[j*16 + i], &precj[j*16 + i - 1], &gbase);
  72             }
  73             /* Multiply gbase by 16. */
  74             for (i = 0; i < 4; i++) {
  75                 secp256k1_gej_double_var(&gbase, &gbase);
  76             }
  77             /* Multiply numbase by 2. */
  78             secp256k1_gej_double_var(&numsbase, &numsbase);
  79             if (j == 62) {
  80                 /* In the last iteration, numsbase is (1 - 2^j) * nums instead. */
  81                 secp256k1_gej_neg(&numsbase, &numsbase);
  82                 secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej);
  83             }
  84         }
  85         secp256k1_ge_set_all_gej_var(1024, prec, precj);
  86     }
  87     for (j = 0; j < 64; j++) {
  88         for (i = 0; i < 16; i++) {
  89             secp256k1_ge_to_storage(&ret->prec[j][i], &prec[j*16 + i]);
  90         }
  91     }
  92
  93     /* Set the global pointer to the precomputation table. */
  94     secp256k1_ecmult_gen_consts = ret;
  95 }
  96
  97 static void secp256k1_ecmult_gen_stop(void) {
  98     secp256k1_ecmult_gen_consts_t *c;
  99     if (secp256k1_ecmult_gen_consts == NULL) {
 100         return;
 101     }
 102
 103     c = (secp256k1_ecmult_gen_consts_t*)secp256k1_ecmult_gen_consts;
 104     secp256k1_ecmult_gen_consts = NULL;
 105     free(c);
 106 }
 107
 108 static void secp256k1_ecmult_gen(secp256k1_gej_t *r, const secp256k1_scalar_t *gn) {
 109     const secp256k1_ecmult_gen_consts_t *c = secp256k1_ecmult_gen_consts;
 110     secp256k1_ge_t add;
 111     secp256k1_ge_storage_t adds;
 112     int bits;
 113     int i, j;
 114     secp256k1_gej_set_infinity(r);
 115     add.infinity = 0;
 116     for (j = 0; j < 64; j++) {
 117         bits = secp256k1_scalar_get_bits(gn, j * 4, 4);
 118         for (i = 0; i < 16; i++) {
 119             secp256k1_ge_storage_cmov(&adds, &c->prec[j][i], i == bits);
 120         }
 121         secp256k1_ge_from_storage(&add, &adds);
 122         secp256k1_gej_add_ge(r, r, &add);
 123     }
 124     bits = 0;
 125     secp256k1_ge_clear(&add);
 126 }
 127
 128 #endif