src/field_impl.h

   1 // Copyright (c) 2013 Pieter Wuille
   2 // Distributed under the MIT/X11 software license, see the accompanying
   3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
   4
   5 #ifndef _SECP256K1_FIELD_IMPL_H_
   6 #define _SECP256K1_FIELD_IMPL_H_
   7
   8 #if defined HAVE_CONFIG_H
   9 #include "libsecp256k1-config.h"
  10 #endif
  11
  12 #include "util.h"
  13
  14 #if defined(USE_FIELD_GMP)
  15 #include "field_gmp_impl.h"
  16 #elif defined(USE_FIELD_10X26)
  17 #include "field_10x26_impl.h"
  18 #elif defined(USE_FIELD_5X52)
  19 #include "field_5x52_impl.h"
  20 #else
  21 #error "Please select field implementation"
  22 #endif
  23
  24 void static secp256k1_fe_get_hex(char *r, int *rlen, const secp256k1_fe_t *a) {
  25     if (*rlen < 65) {
  26         *rlen = 65;
  27         return;
  28     }
  29     *rlen = 65;
  30     unsigned char tmp[32];
  31     secp256k1_fe_t b = *a;
  32     secp256k1_fe_normalize(&b);
  33     secp256k1_fe_get_b32(tmp, &b);
  34     for (int i=0; i<32; i++) {
  35         static const char *c = "0123456789ABCDEF";
  36         r[2*i]   = c[(tmp[i] >> 4) & 0xF];
  37         r[2*i+1] = c[(tmp[i]) & 0xF];
  38     }
  39     r[64] = 0x00;
  40 }
  41
  42 void static secp256k1_fe_set_hex(secp256k1_fe_t *r, const char *a, int alen) {
  43     unsigned char tmp[32] = {};
  44     static const int cvt[256] = {0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  45                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  46                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  47                                  0, 1, 2, 3, 4, 5, 6,7,8,9,0,0,0,0,0,0,
  48                                  0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
  49                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  50                                  0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
  51                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  52                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  53                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  54                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  55                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  56                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  57                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  58                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
  59                                  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0};
  60     for (int i=0; i<32; i++) {
  61         if (alen > i*2)
  62             tmp[32 - alen/2 + i] = (cvt[(unsigned char)a[2*i]] << 4) + cvt[(unsigned char)a[2*i+1]];
  63     }
  64     secp256k1_fe_set_b32(r, tmp);
  65 }
  66
  67 int static secp256k1_fe_sqrt(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
  68
  69     // The binary representation of (p + 1)/4 has 3 blocks of 1s, with lengths in
  70     // { 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block:
  71     // 1, [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223]
  72
  73     secp256k1_fe_t x2;
  74     secp256k1_fe_sqr(&x2, a);
  75     secp256k1_fe_mul(&x2, &x2, a);
  76
  77     secp256k1_fe_t x3;
  78     secp256k1_fe_sqr(&x3, &x2);
  79     secp256k1_fe_mul(&x3, &x3, a);
  80
  81     secp256k1_fe_t x6 = x3;
  82     for (int j=0; j<3; j++) secp256k1_fe_sqr(&x6, &x6);
  83     secp256k1_fe_mul(&x6, &x6, &x3);
  84
  85     secp256k1_fe_t x9 = x6;
  86     for (int j=0; j<3; j++) secp256k1_fe_sqr(&x9, &x9);
  87     secp256k1_fe_mul(&x9, &x9, &x3);
  88
  89     secp256k1_fe_t x11 = x9;
  90     for (int j=0; j<2; j++) secp256k1_fe_sqr(&x11, &x11);
  91     secp256k1_fe_mul(&x11, &x11, &x2);
  92
  93     secp256k1_fe_t x22 = x11;
  94     for (int j=0; j<11; j++) secp256k1_fe_sqr(&x22, &x22);
  95     secp256k1_fe_mul(&x22, &x22, &x11);
  96
  97     secp256k1_fe_t x44 = x22;
  98     for (int j=0; j<22; j++) secp256k1_fe_sqr(&x44, &x44);
  99     secp256k1_fe_mul(&x44, &x44, &x22);
 100
 101     secp256k1_fe_t x88 = x44;
 102     for (int j=0; j<44; j++) secp256k1_fe_sqr(&x88, &x88);
 103     secp256k1_fe_mul(&x88, &x88, &x44);
 104
 105     secp256k1_fe_t x176 = x88;
 106     for (int j=0; j<88; j++) secp256k1_fe_sqr(&x176, &x176);
 107     secp256k1_fe_mul(&x176, &x176, &x88);
 108
 109     secp256k1_fe_t x220 = x176;
 110     for (int j=0; j<44; j++) secp256k1_fe_sqr(&x220, &x220);
 111     secp256k1_fe_mul(&x220, &x220, &x44);
 112
 113     secp256k1_fe_t x223 = x220;
 114     for (int j=0; j<3; j++) secp256k1_fe_sqr(&x223, &x223);
 115     secp256k1_fe_mul(&x223, &x223, &x3);
 116
 117     // The final result is then assembled using a sliding window over the blocks.
 118
 119     secp256k1_fe_t t1 = x223;
 120     for (int j=0; j<23; j++) secp256k1_fe_sqr(&t1, &t1);
 121     secp256k1_fe_mul(&t1, &t1, &x22);
 122     for (int j=0; j<6; j++) secp256k1_fe_sqr(&t1, &t1);
 123     secp256k1_fe_mul(&t1, &t1, &x2);
 124     secp256k1_fe_sqr(&t1, &t1);
 125     secp256k1_fe_sqr(r, &t1);
 126
 127     // Check that a square root was actually calculated
 128
 129     secp256k1_fe_sqr(&t1, r);
 130     secp256k1_fe_negate(&t1, &t1, 1);
 131     secp256k1_fe_add(&t1, a);
 132     secp256k1_fe_normalize(&t1);
 133     return secp256k1_fe_is_zero(&t1);
 134 }
 135
 136 void static secp256k1_fe_inv(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
 137
 138     // The binary representation of (p - 2) has 5 blocks of 1s, with lengths in
 139     // { 1, 2, 22, 223 }. Use an addition chain to calculate 2^n - 1 for each block:
 140     // [1], [2], 3, 6, 9, 11, [22], 44, 88, 176, 220, [223]
 141
 142     secp256k1_fe_t x2;
 143     secp256k1_fe_sqr(&x2, a);
 144     secp256k1_fe_mul(&x2, &x2, a);
 145
 146     secp256k1_fe_t x3;
 147     secp256k1_fe_sqr(&x3, &x2);
 148     secp256k1_fe_mul(&x3, &x3, a);
 149
 150     secp256k1_fe_t x6 = x3;
 151     for (int j=0; j<3; j++) secp256k1_fe_sqr(&x6, &x6);
 152     secp256k1_fe_mul(&x6, &x6, &x3);
 153
 154     secp256k1_fe_t x9 = x6;
 155     for (int j=0; j<3; j++) secp256k1_fe_sqr(&x9, &x9);
 156     secp256k1_fe_mul(&x9, &x9, &x3);
 157
 158     secp256k1_fe_t x11 = x9;
 159     for (int j=0; j<2; j++) secp256k1_fe_sqr(&x11, &x11);
 160     secp256k1_fe_mul(&x11, &x11, &x2);
 161
 162     secp256k1_fe_t x22 = x11;
 163     for (int j=0; j<11; j++) secp256k1_fe_sqr(&x22, &x22);
 164     secp256k1_fe_mul(&x22, &x22, &x11);
 165
 166     secp256k1_fe_t x44 = x22;
 167     for (int j=0; j<22; j++) secp256k1_fe_sqr(&x44, &x44);
 168     secp256k1_fe_mul(&x44, &x44, &x22);
 169
 170     secp256k1_fe_t x88 = x44;
 171     for (int j=0; j<44; j++) secp256k1_fe_sqr(&x88, &x88);
 172     secp256k1_fe_mul(&x88, &x88, &x44);
 173
 174     secp256k1_fe_t x176 = x88;
 175     for (int j=0; j<88; j++) secp256k1_fe_sqr(&x176, &x176);
 176     secp256k1_fe_mul(&x176, &x176, &x88);
 177
 178     secp256k1_fe_t x220 = x176;
 179     for (int j=0; j<44; j++) secp256k1_fe_sqr(&x220, &x220);
 180     secp256k1_fe_mul(&x220, &x220, &x44);
 181
 182     secp256k1_fe_t x223 = x220;
 183     for (int j=0; j<3; j++) secp256k1_fe_sqr(&x223, &x223);
 184     secp256k1_fe_mul(&x223, &x223, &x3);
 185
 186     // The final result is then assembled using a sliding window over the blocks.
 187
 188     secp256k1_fe_t t1 = x223;
 189     for (int j=0; j<23; j++) secp256k1_fe_sqr(&t1, &t1);
 190     secp256k1_fe_mul(&t1, &t1, &x22);
 191     for (int j=0; j<5; j++) secp256k1_fe_sqr(&t1, &t1);
 192     secp256k1_fe_mul(&t1, &t1, a);
 193     for (int j=0; j<3; j++) secp256k1_fe_sqr(&t1, &t1);
 194     secp256k1_fe_mul(&t1, &t1, &x2);
 195     for (int j=0; j<2; j++) secp256k1_fe_sqr(&t1, &t1);
 196     secp256k1_fe_mul(r, &t1, a);
 197 }
 198
 199 void static secp256k1_fe_inv_var(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
 200 #if defined(USE_FIELD_INV_BUILTIN)
 201     secp256k1_fe_inv(r, a);
 202 #elif defined(USE_FIELD_INV_NUM)
 203     unsigned char b[32];
 204     secp256k1_fe_t c = *a;
 205     secp256k1_fe_normalize(&c);
 206     secp256k1_fe_get_b32(b, &c);
 207     secp256k1_num_t n;
 208     secp256k1_num_init(&n);
 209     secp256k1_num_set_bin(&n, b, 32);
 210     secp256k1_num_mod_inverse(&n, &n, &secp256k1_fe_consts->p);
 211     secp256k1_num_get_bin(b, 32, &n);
 212     secp256k1_num_free(&n);
 213     secp256k1_fe_set_b32(r, b);
 214 #else
 215 #error "Please select field inverse implementation"
 216 #endif
 217 }
 218
 219 void static secp256k1_fe_inv_all(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
 220     if (len < 1)
 221         return;
 222
 223     VERIFY_CHECK((r + len <= a) || (a + len <= r));
 224
 225     r[0] = a[0];
 226
 227     int i = 0;
 228     while (++i < len) {
 229         secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
 230     }
 231
 232     secp256k1_fe_t u; secp256k1_fe_inv(&u, &r[--i]);
 233
 234     while (i > 0) {
 235         int j = i--;
 236         secp256k1_fe_mul(&r[j], &r[i], &u);
 237         secp256k1_fe_mul(&u, &u, &a[j]);
 238     }
 239
 240     r[0] = u;
 241 }
 242
 243 void static secp256k1_fe_inv_all_var(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
 244     if (len < 1)
 245         return;
 246
 247     VERIFY_CHECK((r + len <= a) || (a + len <= r));
 248
 249     r[0] = a[0];
 250
 251     int i = 0;
 252     while (++i < len) {
 253         secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
 254     }
 255
 256     secp256k1_fe_t u; secp256k1_fe_inv_var(&u, &r[--i]);
 257
 258     while (i > 0) {
 259         int j = i--;
 260         secp256k1_fe_mul(&r[j], &r[i], &u);
 261         secp256k1_fe_mul(&u, &u, &a[j]);
 262     }
 263
 264     r[0] = u;
 265 }
 266
 267 void static secp256k1_fe_start(void) {
 268     static const unsigned char secp256k1_fe_consts_p[] = {
 269         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
 270         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
 271         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
 272         0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F
 273     };
 274     if (secp256k1_fe_consts == NULL) {
 275         secp256k1_fe_inner_start();
 276         secp256k1_fe_consts_t *ret = (secp256k1_fe_consts_t*)malloc(sizeof(secp256k1_fe_consts_t));
 277         secp256k1_num_init(&ret->p);
 278         secp256k1_num_set_bin(&ret->p, secp256k1_fe_consts_p, sizeof(secp256k1_fe_consts_p));
 279         secp256k1_fe_consts = ret;
 280     }
 281 }
 282
 283 void static secp256k1_fe_stop(void) {
 284     if (secp256k1_fe_consts != NULL) {
 285         secp256k1_fe_consts_t *c = (secp256k1_fe_consts_t*)secp256k1_fe_consts;
 286         secp256k1_num_free(&c->p);
 287         free((void*)c);
 288         secp256k1_fe_consts = NULL;
 289         secp256k1_fe_inner_stop();
 290     }
 291 }
 292
 293 #endif