ecmult.h

   1 #ifndef _SECP256K1_ECMULT_
   2 #define _SECP256K1_ECMULT_
   3
   4 #include <sstream>
   5 #include <algorithm>
   6
   7 #include "group.h"
   8 #include "num.h"
   9
  10 // optimal for 128-bit and 256-bit exponents
  11 #define WINDOW_A 5
  12
  13 // larger numbers may result in slightly better performance, at the cost of
  14 // exponentially larger precomputed tables. WINDOW_G == 13 results in 640 KiB.
  15 #define WINDOW_G 14
  16
  17 namespace secp256k1 {
  18
  19 template<typename G, int W> class WNAFPrecomp {
  20 private:
  21     G pre[1 << (W-2)];
  22
  23 public:
  24     WNAFPrecomp() {}
  25
  26     void Build(Context &ctx, const G &base) {
  27         pre[0] = base;
  28         GroupElemJac x(base);
  29         GroupElemJac d; d.SetDouble(x);
  30         for (int i=1; i<(1 << (W-2)); i++) {
  31             x.SetAdd(d,pre[i-1]);
  32             pre[i].SetJac(ctx, x);
  33         }
  34     }
  35
  36     WNAFPrecomp(Context &ctx, const G &base) {
  37         Build(ctx, base);
  38     }
  39
  40     void Get(G &out, int exp) const {
  41         assert((exp & 1) == 1);
  42         assert(exp >= -((1 << (W-1)) - 1));
  43         assert(exp <=  ((1 << (W-1)) - 1));
  44         if (exp > 0) {
  45             out = pre[(exp-1)/2];
  46         } else {
  47             out.SetNeg(pre[(-exp-1)/2]);
  48         }
  49     }
  50 };
  51
  52 template<int B> class WNAF {
  53 private:
  54     int naf[B+1];
  55     int used;
  56
  57     void PushNAF(int num, int zeroes) {
  58         assert(used < B+1);
  59         for (int i=0; i<zeroes; i++) {
  60             naf[used++]=0;
  61         }
  62         naf[used++]=num;
  63     }
  64
  65 public:
  66     WNAF(Context &ctx, const Number &exp, int w) : used(0) {
  67         int zeroes = 0;
  68         Context ct(ctx);
  69         Number x(ct);
  70         x.SetNumber(exp);
  71         int sign = 1;
  72         if (x.IsNeg()) {
  73             sign = -1;
  74             x.Negate();
  75         }
  76         while (!x.IsZero()) {
  77             while (!x.IsOdd()) {
  78                 zeroes++;
  79                 x.Shift1();
  80             }
  81             int word = x.ShiftLowBits(ct,w);
  82             if (word & (1 << (w-1))) {
  83                 x.Inc();
  84                 PushNAF(sign * (word - (1 << w)), zeroes);
  85             } else {
  86                 PushNAF(sign * word, zeroes);
  87             }
  88             zeroes = w-1;
  89         }
  90     }
  91
  92     int GetSize() const {
  93         return used;
  94     }
  95
  96     int Get(int pos) const {
  97         assert(pos >= 0 && pos < used);
  98         return naf[pos];
  99     }
 100
 101     std::string ToString() {
 102         std::stringstream ss;
 103         ss << "(";
 104         for (int i=0; i<GetSize(); i++) {
 105             ss << Get(used-1-i);
 106             if (i != used-1)
 107                 ss << ',';
 108         }
 109         ss << ")";
 110         return ss.str();
 111     }
 112 };
 113
 114 class ECMultConsts {
 115 public:
 116     WNAFPrecomp<GroupElem,WINDOW_G> wpg;
 117     WNAFPrecomp<GroupElem,WINDOW_G> wpg128;
 118
 119     ECMultConsts() {
 120         Context ctx;
 121         const GroupElem &g = GetGroupConst().g;
 122         GroupElemJac g128j(g);
 123         for (int i=0; i<128; i++)
 124             g128j.SetDouble(g128j);
 125         GroupElem g128; g128.SetJac(ctx, g128j);
 126         wpg.Build(ctx, g);
 127         wpg128.Build(ctx, g128);
 128     }
 129 };
 130
 131 const ECMultConsts &GetECMultConsts() {
 132     static const ECMultConsts ecmult_consts;
 133     return ecmult_consts;
 134 }
 135
 136 void ECMult(Context &ctx, GroupElemJac &out, const GroupElemJac &a, const Number &an, const Number &gn) {
 137     Context ct(ctx);
 138     Number an1(ct), an2(ct);
 139     Number gn1(ct), gn2(ct);
 140
 141     SplitExp(ct, an, an1, an2);
 142 //    printf("an=%s\n", an.ToString().c_str());
 143 //    printf("an1=%s\n", an1.ToString().c_str());
 144 //    printf("an2=%s\n", an2.ToString().c_str());
 145 //    printf("an1.len=%i\n", an1.GetBits());
 146 //    printf("an2.len=%i\n", an2.GetBits());
 147     gn.SplitInto(ct, 128, gn1, gn2);
 148
 149     WNAF<128> wa1(ct, an1, WINDOW_A);
 150     WNAF<128> wa2(ct, an2, WINDOW_A);
 151     WNAF<128> wg1(ct, gn1, WINDOW_G);
 152     WNAF<128> wg2(ct, gn2, WINDOW_G);
 153     GroupElemJac a2; a2.SetMulLambda(a);
 154     WNAFPrecomp<GroupElemJac,WINDOW_A> wpa1(ct, a);
 155     WNAFPrecomp<GroupElemJac,WINDOW_A> wpa2(ct, a2);
 156     const ECMultConsts &c = GetECMultConsts();
 157
 158     int size_a1 = wa1.GetSize();
 159     int size_a2 = wa2.GetSize();
 160     int size_g1 = wg1.GetSize();
 161     int size_g2 = wg2.GetSize();
 162     int size = std::max(std::max(size_a1, size_a2), std::max(size_g1, size_g2));
 163
 164     out = GroupElemJac();
 165     GroupElemJac tmpj;
 166     GroupElem tmpa;
 167
 168     for (int i=size-1; i>=0; i--) {
 169         out.SetDouble(out);
 170         int nw;
 171         if (i < size_a1 && (nw = wa1.Get(i))) {
 172             wpa1.Get(tmpj, nw);
 173             out.SetAdd(out, tmpj);
 174         }
 175         if (i < size_a2 && (nw = wa2.Get(i))) {
 176             wpa2.Get(tmpj, nw);
 177             out.SetAdd(out, tmpj);
 178         }
 179         if (i < size_g1 && (nw = wg1.Get(i))) {
 180             c.wpg.Get(tmpa, nw);
 181             out.SetAdd(out, tmpa);
 182         }
 183         if (i < size_g2 && (nw = wg2.Get(i))) {
 184             c.wpg128.Get(tmpa, nw);
 185             out.SetAdd(out, tmpa);
 186         }
 187     }
 188 }
 189
 190 }
 191
 192 #endif