src/tests.c

   1 #include <assert.h>
   2
   3 #include "impl/num.h"
   4 #include "impl/field.h"
   5 #include "impl/group.h"
   6 #include "impl/ecmult.h"
   7 #include "impl/ecdsa.h"
   8 #include "impl/util.h"
   9
  10 // #define COUNT 2
  11 #define COUNT 100
  12
  13 void random_num_order(secp256k1_num_t *num) {
  14     do {
  15         unsigned char b32[32];
  16         secp256k1_rand256_test(b32);
  17         secp256k1_num_set_bin(num, b32, 32);
  18         if (secp256k1_num_is_zero(num))
  19             continue;
  20         if (secp256k1_num_cmp(num, &secp256k1_ge_consts->order) >= 0)
  21             continue;
  22         break;
  23     } while(1);
  24 }
  25
  26 void test_run_ecmult_chain() {
  27     // random starting point A (on the curve)
  28     secp256k1_fe_t ax; secp256k1_fe_set_hex(&ax, "8b30bbe9ae2a990696b22f670709dff3727fd8bc04d3362c6c7bf458e2846004", 64);
  29     secp256k1_fe_t ay; secp256k1_fe_set_hex(&ay, "a357ae915c4a65281309edf20504740f0eb3343990216b4f81063cb65f2f7e0f", 64);
  30     secp256k1_gej_t a; secp256k1_gej_set_xy(&a, &ax, &ay);
  31     // two random initial factors xn and gn
  32     secp256k1_num_t xn;
  33     secp256k1_num_init(&xn);
  34     secp256k1_num_set_hex(&xn, "84cc5452f7fde1edb4d38a8ce9b1b84ccef31f146e569be9705d357a42985407", 64);
  35     secp256k1_num_t gn;
  36     secp256k1_num_init(&gn);
  37     secp256k1_num_set_hex(&gn, "a1e58d22553dcd42b23980625d4c57a96e9323d42b3152e5ca2c3990edc7c9de", 64);
  38     // two small multipliers to be applied to xn and gn in every iteration:
  39     secp256k1_num_t xf;
  40     secp256k1_num_init(&xf);
  41     secp256k1_num_set_hex(&xf, "1337", 4);
  42     secp256k1_num_t gf;
  43     secp256k1_num_init(&gf);
  44     secp256k1_num_set_hex(&gf, "7113", 4);
  45     // accumulators with the resulting coefficients to A and G
  46     secp256k1_num_t ae;
  47     secp256k1_num_init(&ae);
  48     secp256k1_num_set_int(&ae, 1);
  49     secp256k1_num_t ge;
  50     secp256k1_num_init(&ge);
  51     secp256k1_num_set_int(&ge, 0);
  52     // the point being computed
  53     secp256k1_gej_t x = a;
  54     const secp256k1_num_t *order = &secp256k1_ge_consts->order;
  55     for (int i=0; i<200*COUNT; i++) {
  56         // in each iteration, compute X = xn*X + gn*G;
  57         secp256k1_ecmult(&x, &x, &xn, &gn);
  58         // also compute ae and ge: the actual accumulated factors for A and G
  59         // if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G)
  60         secp256k1_num_mod_mul(&ae, &ae, &xn, order);
  61         secp256k1_num_mod_mul(&ge, &ge, &xn, order);
  62         secp256k1_num_add(&ge, &ge, &gn);
  63         secp256k1_num_mod(&ge, order);
  64         // modify xn and gn
  65         secp256k1_num_mod_mul(&xn, &xn, &xf, order);
  66         secp256k1_num_mod_mul(&gn, &gn, &gf, order);
  67     }
  68     char res[132]; int resl = 132;
  69     secp256k1_gej_get_hex(res, &resl, &x);
  70     if (COUNT == 100) {
  71       assert(strcmp(res, "(D6E96687F9B10D092A6F35439D86CEBEA4535D0D409F53586440BD74B933E830,B95CBCA2C77DA786539BE8FD53354D2D3B4F566AE658045407ED6015EE1B2A88)") == 0);
  72     }
  73     // redo the computation, but directly with the resulting ae and ge coefficients:
  74     secp256k1_gej_t x2; secp256k1_ecmult(&x2, &a, &ae, &ge);
  75     char res2[132]; int resl2 = 132;
  76     secp256k1_gej_get_hex(res2, &resl2, &x2);
  77     assert(strcmp(res, res2) == 0);
  78     assert(strlen(res) == 131);
  79     secp256k1_num_free(&xn);
  80     secp256k1_num_free(&gn);
  81     secp256k1_num_free(&xf);
  82     secp256k1_num_free(&gf);
  83     secp256k1_num_free(&ae);
  84     secp256k1_num_free(&ge);
  85 }
  86
  87 void test_point_times_order(const secp256k1_gej_t *point) {
  88     // either the point is not on the curve, or multiplying it by the order results in O
  89     if (!secp256k1_gej_is_valid(point))
  90         return;
  91
  92     const secp256k1_num_t *order = &secp256k1_ge_consts->order;
  93     secp256k1_num_t zero;
  94     secp256k1_num_init(&zero);
  95     secp256k1_num_set_int(&zero, 0);
  96     secp256k1_gej_t res;
  97     secp256k1_ecmult(&res, point, order, order); // calc res = order * point + order * G;
  98     assert(secp256k1_gej_is_infinity(&res));
  99     secp256k1_num_free(&zero);
 100 }
 101
 102 void test_run_point_times_order() {
 103     secp256k1_fe_t x; secp256k1_fe_set_hex(&x, "02", 2);
 104     for (int i=0; i<500; i++) {
 105         secp256k1_gej_t j; secp256k1_gej_set_xo(&j, &x, 1);
 106         test_point_times_order(&j);
 107         secp256k1_fe_sqr(&x, &x);
 108     }
 109     char c[65]; int cl=65;
 110     secp256k1_fe_get_hex(c, &cl, &x);
 111     assert(strcmp(c, "7603CB59B0EF6C63FE6084792A0C378CDB3233A80F8A9A09A877DEAD31B38C45") == 0);
 112 }
 113
 114 void test_wnaf(const secp256k1_num_t *number, int w) {
 115     secp256k1_num_t x, two, t;
 116     secp256k1_num_init(&x);
 117     secp256k1_num_init(&two);
 118     secp256k1_num_init(&t);
 119     secp256k1_num_set_int(&x, 0);
 120     secp256k1_num_set_int(&two, 2);
 121     int wnaf[257];
 122     int bits = secp256k1_ecmult_wnaf(wnaf, number, w);
 123     int zeroes = -1;
 124     for (int i=bits-1; i>=0; i--) {
 125         secp256k1_num_mul(&x, &x, &two);
 126         int v = wnaf[i];
 127         if (v) {
 128             assert(zeroes == -1 || zeroes >= w-1); // check that distance between non-zero elements is at least w-1
 129             zeroes=0;
 130             assert((v & 1) == 1); // check non-zero elements are odd
 131             assert(v <= (1 << (w-1)) - 1); // check range below
 132             assert(v >= -(1 << (w-1)) - 1); // check range above
 133         } else {
 134             assert(zeroes != -1); // check that no unnecessary zero padding exists
 135             zeroes++;
 136         }
 137         secp256k1_num_set_int(&t, v);
 138         secp256k1_num_add(&x, &x, &t);
 139     }
 140     assert(secp256k1_num_cmp(&x, number) == 0); // check that wnaf represents number
 141     secp256k1_num_free(&x);
 142     secp256k1_num_free(&two);
 143     secp256k1_num_free(&t);
 144 }
 145
 146 void test_run_wnaf() {
 147     secp256k1_num_t n;
 148     secp256k1_num_init(&n);
 149     for (int i=0; i<COUNT; i++) {
 150         random_num_order(&n);
 151         if (i % 1)
 152             secp256k1_num_negate(&n);
 153         test_wnaf(&n, 4+(i%10));
 154     }
 155     secp256k1_num_free(&n);
 156 }
 157
 158 void test_ecdsa_sign_verify() {
 159     const secp256k1_ge_consts_t *c = secp256k1_ge_consts;
 160     secp256k1_num_t msg, key, nonce;
 161     secp256k1_num_init(&msg);
 162     random_num_order(&msg);
 163     secp256k1_num_init(&key);
 164     random_num_order(&key);
 165     secp256k1_num_init(&nonce);
 166     secp256k1_gej_t pub; secp256k1_ecmult_gen(&pub, &key);
 167     secp256k1_ecdsa_sig_t sig;
 168     secp256k1_ecdsa_sig_init(&sig);
 169     do {
 170         random_num_order(&nonce);
 171     } while(!secp256k1_ecdsa_sig_sign(&sig, &key, &msg, &nonce));
 172     assert(secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
 173     secp256k1_num_inc(&msg);
 174     assert(!secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
 175     secp256k1_ecdsa_sig_free(&sig);
 176     secp256k1_num_free(&msg);
 177     secp256k1_num_free(&key);
 178     secp256k1_num_free(&nonce);
 179 }
 180
 181 void test_run_ecdsa_sign_verify() {
 182     for (int i=0; i<10*COUNT; i++) {
 183         test_ecdsa_sign_verify();
 184     }
 185 }
 186
 187 int main(void) {
 188     secp256k1_fe_start();
 189     secp256k1_ge_start();
 190     secp256k1_ecmult_start();
 191
 192     test_run_wnaf();
 193     test_run_point_times_order();
 194     test_run_ecmult_chain();
 195     test_run_ecdsa_sign_verify();
 196
 197     secp256k1_ecmult_stop();
 198     secp256k1_ge_stop();
 199     secp256k1_fe_stop();
 200     return 0;
 201 }