1  /***********************************************************************
  2   * Copyright (c) Pieter Wuille, Peter Dettman                          *
  3   * Distributed under the MIT software license, see the accompanying    *
  4   * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
  5   ***********************************************************************/
  6  
  7  #ifndef SECP256K1_ECMULT_GEN_H
  8  #define SECP256K1_ECMULT_GEN_H
  9  
 10  #include "hash.h"
 11  #include "scalar.h"
 12  #include "group.h"
 13  
 14  
 15  /* Configuration parameters for the signed-digit multi-comb algorithm:
 16   *
 17   * - COMB_BLOCKS is the number of blocks the input is split into. Each
 18   *   has a corresponding table.
 19   * - COMB_TEETH is the number of bits simultaneously covered by one table.
 20   * - COMB_RANGE is the number of bits in supported scalars. For production
 21   *   purposes, only 256 is reasonable, but smaller numbers are supported for
 22   *   exhaustive test mode.
 23   *
 24   * The comb's spacing (COMB_SPACING), or the distance between the teeth,
 25   * is defined as ceil(COMB_RANGE / (COMB_BLOCKS * COMB_TEETH)). Each block covers
 26   * COMB_SPACING * COMB_TEETH consecutive bits in the input.
 27   *
 28   * The size of the precomputed table is COMB_BLOCKS * (1 << (COMB_TEETH - 1))
 29   * secp256k1_ge_storages.
 30   *
 31   * The number of point additions equals COMB_BLOCKS * COMB_SPACING. Each point
 32   * addition involves a cmov from (1 << (COMB_TEETH - 1)) table entries and a
 33   * conditional negation.
 34   *
 35   * The number of point doublings is COMB_SPACING - 1. */
 36  
 37  #if defined(EXHAUSTIVE_TEST_ORDER)
 38  /* We need to control these values for exhaustive tests because
 39   * the table cannot have infinities in them (secp256k1_ge_storage
 40   * doesn't support infinities) */
 41  #  undef COMB_BLOCKS
 42  #  undef COMB_TEETH
 43  #  if EXHAUSTIVE_TEST_ORDER == 7
 44  #    define COMB_RANGE 3
 45  #    define COMB_BLOCKS 1
 46  #    define COMB_TEETH 2
 47  #  elif EXHAUSTIVE_TEST_ORDER == 13
 48  #    define COMB_RANGE 4
 49  #    define COMB_BLOCKS 1
 50  #    define COMB_TEETH 2
 51  #  elif EXHAUSTIVE_TEST_ORDER == 199
 52  #    define COMB_RANGE 8
 53  #    define COMB_BLOCKS 2
 54  #    define COMB_TEETH 3
 55  #  else
 56  #    error "Unknown exhaustive test order"
 57  #  endif
 58  #  if (COMB_RANGE >= 32) || ((EXHAUSTIVE_TEST_ORDER >> (COMB_RANGE - 1)) != 1)
 59  #    error "COMB_RANGE != ceil(log2(EXHAUSTIVE_TEST_ORDER+1))"
 60  #  endif
 61  #else /* !defined(EXHAUSTIVE_TEST_ORDER) */
 62  #  define COMB_RANGE 256
 63  #endif /* defined(EXHAUSTIVE_TEST_ORDER) */
 64  
 65  /* Use (11, 6) as default configuration, which results in a 22 kB table. */
 66  #ifndef COMB_BLOCKS
 67  #  define COMB_BLOCKS 11
 68  #  ifdef DEBUG_CONFIG
 69  #    pragma message DEBUG_CONFIG_MSG("COMB_BLOCKS undefined, assuming default value")
 70  #  endif
 71  #endif
 72  #ifndef COMB_TEETH
 73  #  define COMB_TEETH 6
 74  #  ifdef DEBUG_CONFIG
 75  #    pragma message DEBUG_CONFIG_MSG("COMB_TEETH undefined, assuming default value")
 76  #  endif
 77  #endif
 78  /* Use ceil(COMB_RANGE / (COMB_BLOCKS * COMB_TEETH)) as COMB_SPACING. */
 79  #define COMB_SPACING CEIL_DIV(COMB_RANGE, COMB_BLOCKS * COMB_TEETH)
 80  
 81  /* Range checks on the parameters. */
 82  
 83  /* The remaining COMB_* parameters are derived values, don't modify these. */
 84  /* - The number of bits covered by all the blocks; must be at least COMB_RANGE. */
 85  #define COMB_BITS (COMB_BLOCKS * COMB_TEETH * COMB_SPACING)
 86  /* - The number of entries per table. */
 87  #define COMB_POINTS (1 << (COMB_TEETH - 1))
 88  
 89  /* Sanity checks. */
 90  #if !(1 <= COMB_BLOCKS && COMB_BLOCKS <= 256)
 91  #  error "COMB_BLOCKS must be in the range [1, 256]"
 92  #endif
 93  #if !(1 <= COMB_TEETH && COMB_TEETH <= 8)
 94  #  error "COMB_TEETH must be in the range [1, 8]"
 95  #endif
 96  #if COMB_BITS < COMB_RANGE
 97  #  error "COMB_BLOCKS * COMB_TEETH * COMB_SPACING is too low"
 98  #endif
 99  
100  /* These last 2 checks are not strictly required, but prevent gratuitously inefficient
101   * configurations. Note that they compare with 256 rather than COMB_RANGE, so they do
102   * permit somewhat excessive values for the exhaustive test case, where testing with
103   * suboptimal parameters may be desirable. */
104  #if (COMB_BLOCKS - 1) * COMB_TEETH * COMB_SPACING >= 256
105  #  error "COMB_BLOCKS can be reduced"
106  #endif
107  #if COMB_BLOCKS * (COMB_TEETH - 1) * COMB_SPACING >= 256
108  #  error "COMB_TEETH can be reduced"
109  #endif
110  
111  #ifdef DEBUG_CONFIG
112  #  pragma message DEBUG_CONFIG_DEF(COMB_RANGE)
113  #  pragma message DEBUG_CONFIG_DEF(COMB_BLOCKS)
114  #  pragma message DEBUG_CONFIG_DEF(COMB_TEETH)
115  #  pragma message DEBUG_CONFIG_DEF(COMB_SPACING)
116  #endif
117  
118  typedef struct {
119      /* Whether the context has been built. */
120      int built;
121  
122      /* Values chosen such that
123       *
124       *   n*G == comb(n + scalar_offset, G/2) + ge_offset.
125       *
126       * This expression lets us use scalar blinding and optimize the comb precomputation. See
127       * ecmult_gen_impl.h for more details. */
128      secp256k1_scalar scalar_offset;
129      secp256k1_ge ge_offset;
130  
131      /* Factor used for projective blinding. This value is used to rescale the Z
132       * coordinate of the first table lookup. */
133      secp256k1_fe proj_blind;
134  } secp256k1_ecmult_gen_context;
135  
136  static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context* ctx, const secp256k1_hash_ctx *hash_ctx);
137  static void secp256k1_ecmult_gen_context_clear(secp256k1_ecmult_gen_context* ctx);
138  
139  /** Multiply with the generator: R = a*G */
140  static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context* ctx, secp256k1_gej *r, const secp256k1_scalar *a);
141  
142  static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const secp256k1_hash_ctx *hash_ctx, const unsigned char *seed32);
143  
144  #endif /* SECP256K1_ECMULT_GEN_H */