Merge #214: Improve signing API documentation & specification
[secp256k1.git] / src / tests.c
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 #if defined HAVE_CONFIG_H
8 #include "libsecp256k1-config.h"
9 #endif
10
11 #include <stdio.h>
12 #include <stdlib.h>
13
14 #include <time.h>
15
16 #include "secp256k1.c"
17 #include "testrand_impl.h"
18
19 #ifdef ENABLE_OPENSSL_TESTS
20 #include "openssl/bn.h"
21 #include "openssl/ec.h"
22 #include "openssl/ecdsa.h"
23 #include "openssl/obj_mac.h"
24 #endif
25
26 static int count = 64;
27
28 void random_field_element_test(secp256k1_fe_t *fe) {
29     do {
30         unsigned char b32[32];
31         secp256k1_rand256_test(b32);
32         if (secp256k1_fe_set_b32(fe, b32)) {
33             break;
34         }
35     } while(1);
36 }
37
38 void random_field_element_magnitude(secp256k1_fe_t *fe) {
39     secp256k1_fe_t zero;
40     int n = secp256k1_rand32() % 9;
41     secp256k1_fe_normalize(fe);
42     if (n == 0) {
43         return;
44     }
45     secp256k1_fe_clear(&zero);
46     secp256k1_fe_negate(&zero, &zero, 0);
47     secp256k1_fe_mul_int(&zero, n - 1);
48     secp256k1_fe_add(fe, &zero);
49 #ifdef VERIFY
50     CHECK(fe->magnitude == n);
51 #endif
52 }
53
54 void random_group_element_test(secp256k1_ge_t *ge) {
55     secp256k1_fe_t fe;
56     do {
57         random_field_element_test(&fe);
58         if (secp256k1_ge_set_xo_var(ge, &fe, secp256k1_rand32() & 1))
59             break;
60     } while(1);
61 }
62
63 void random_group_element_jacobian_test(secp256k1_gej_t *gej, const secp256k1_ge_t *ge) {
64     secp256k1_fe_t z2, z3;
65     do {
66         random_field_element_test(&gej->z);
67         if (!secp256k1_fe_is_zero(&gej->z)) {
68             break;
69         }
70     } while(1);
71     secp256k1_fe_sqr(&z2, &gej->z);
72     secp256k1_fe_mul(&z3, &z2, &gej->z);
73     secp256k1_fe_mul(&gej->x, &ge->x, &z2);
74     secp256k1_fe_mul(&gej->y, &ge->y, &z3);
75     gej->infinity = ge->infinity;
76 }
77
78 void random_scalar_order_test(secp256k1_scalar_t *num) {
79     do {
80         unsigned char b32[32];
81         int overflow = 0;
82         secp256k1_rand256_test(b32);
83         secp256k1_scalar_set_b32(num, b32, &overflow);
84         if (overflow || secp256k1_scalar_is_zero(num))
85             continue;
86         break;
87     } while(1);
88 }
89
90 void random_scalar_order(secp256k1_scalar_t *num) {
91     do {
92         unsigned char b32[32];
93         int overflow = 0;
94         secp256k1_rand256(b32);
95         secp256k1_scalar_set_b32(num, b32, &overflow);
96         if (overflow || secp256k1_scalar_is_zero(num))
97             continue;
98         break;
99     } while(1);
100 }
101
102 /***** HASH TESTS *****/
103
104 void run_sha256_tests(void) {
105     static const char *inputs[8] = {
106         "", "abc", "message digest", "secure hash algorithm", "SHA256 is considered to be safe",
107         "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq",
108         "For this sample, this 63-byte string will be used as input data",
109         "This is exactly 64 bytes long, not counting the terminating byte"
110     };
111     static const unsigned char outputs[8][32] = {
112         {0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55},
113         {0xba, 0x78, 0x16, 0xbf, 0x8f, 0x01, 0xcf, 0xea, 0x41, 0x41, 0x40, 0xde, 0x5d, 0xae, 0x22, 0x23, 0xb0, 0x03, 0x61, 0xa3, 0x96, 0x17, 0x7a, 0x9c, 0xb4, 0x10, 0xff, 0x61, 0xf2, 0x00, 0x15, 0xad},
114         {0xf7, 0x84, 0x6f, 0x55, 0xcf, 0x23, 0xe1, 0x4e, 0xeb, 0xea, 0xb5, 0xb4, 0xe1, 0x55, 0x0c, 0xad, 0x5b, 0x50, 0x9e, 0x33, 0x48, 0xfb, 0xc4, 0xef, 0xa3, 0xa1, 0x41, 0x3d, 0x39, 0x3c, 0xb6, 0x50},
115         {0xf3, 0x0c, 0xeb, 0x2b, 0xb2, 0x82, 0x9e, 0x79, 0xe4, 0xca, 0x97, 0x53, 0xd3, 0x5a, 0x8e, 0xcc, 0x00, 0x26, 0x2d, 0x16, 0x4c, 0xc0, 0x77, 0x08, 0x02, 0x95, 0x38, 0x1c, 0xbd, 0x64, 0x3f, 0x0d},
116         {0x68, 0x19, 0xd9, 0x15, 0xc7, 0x3f, 0x4d, 0x1e, 0x77, 0xe4, 0xe1, 0xb5, 0x2d, 0x1f, 0xa0, 0xf9, 0xcf, 0x9b, 0xea, 0xea, 0xd3, 0x93, 0x9f, 0x15, 0x87, 0x4b, 0xd9, 0x88, 0xe2, 0xa2, 0x36, 0x30},
117         {0x24, 0x8d, 0x6a, 0x61, 0xd2, 0x06, 0x38, 0xb8, 0xe5, 0xc0, 0x26, 0x93, 0x0c, 0x3e, 0x60, 0x39, 0xa3, 0x3c, 0xe4, 0x59, 0x64, 0xff, 0x21, 0x67, 0xf6, 0xec, 0xed, 0xd4, 0x19, 0xdb, 0x06, 0xc1},
118         {0xf0, 0x8a, 0x78, 0xcb, 0xba, 0xee, 0x08, 0x2b, 0x05, 0x2a, 0xe0, 0x70, 0x8f, 0x32, 0xfa, 0x1e, 0x50, 0xc5, 0xc4, 0x21, 0xaa, 0x77, 0x2b, 0xa5, 0xdb, 0xb4, 0x06, 0xa2, 0xea, 0x6b, 0xe3, 0x42},
119         {0xab, 0x64, 0xef, 0xf7, 0xe8, 0x8e, 0x2e, 0x46, 0x16, 0x5e, 0x29, 0xf2, 0xbc, 0xe4, 0x18, 0x26, 0xbd, 0x4c, 0x7b, 0x35, 0x52, 0xf6, 0xb3, 0x82, 0xa9, 0xe7, 0xd3, 0xaf, 0x47, 0xc2, 0x45, 0xf8}
120     };
121     int i;
122     for (i = 0; i < 8; i++) {
123         unsigned char out[32];
124         secp256k1_sha256_t hasher;
125         secp256k1_sha256_initialize(&hasher);
126         secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
127         secp256k1_sha256_finalize(&hasher, out);
128         CHECK(memcmp(out, outputs[i], 32) == 0);
129         if (strlen(inputs[i]) > 0) {
130             int split = secp256k1_rand32() % strlen(inputs[i]);
131             secp256k1_sha256_initialize(&hasher);
132             secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
133             secp256k1_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
134             secp256k1_sha256_finalize(&hasher, out);
135             CHECK(memcmp(out, outputs[i], 32) == 0);
136         }
137     }
138 }
139
140 void run_hmac_sha256_tests(void) {
141     static const char *keys[6] = {
142         "\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b\x0b",
143         "\x4a\x65\x66\x65",
144         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
145         "\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19",
146         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa",
147         "\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa\xaa"
148     };
149     static const char *inputs[6] = {
150         "\x48\x69\x20\x54\x68\x65\x72\x65",
151         "\x77\x68\x61\x74\x20\x64\x6f\x20\x79\x61\x20\x77\x61\x6e\x74\x20\x66\x6f\x72\x20\x6e\x6f\x74\x68\x69\x6e\x67\x3f",
152         "\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd\xdd",
153         "\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd\xcd",
154         "\x54\x65\x73\x74\x20\x55\x73\x69\x6e\x67\x20\x4c\x61\x72\x67\x65\x72\x20\x54\x68\x61\x6e\x20\x42\x6c\x6f\x63\x6b\x2d\x53\x69\x7a\x65\x20\x4b\x65\x79\x20\x2d\x20\x48\x61\x73\x68\x20\x4b\x65\x79\x20\x46\x69\x72\x73\x74",
155         "\x54\x68\x69\x73\x20\x69\x73\x20\x61\x20\x74\x65\x73\x74\x20\x75\x73\x69\x6e\x67\x20\x61\x20\x6c\x61\x72\x67\x65\x72\x20\x74\x68\x61\x6e\x20\x62\x6c\x6f\x63\x6b\x2d\x73\x69\x7a\x65\x20\x6b\x65\x79\x20\x61\x6e\x64\x20\x61\x20\x6c\x61\x72\x67\x65\x72\x20\x74\x68\x61\x6e\x20\x62\x6c\x6f\x63\x6b\x2d\x73\x69\x7a\x65\x20\x64\x61\x74\x61\x2e\x20\x54\x68\x65\x20\x6b\x65\x79\x20\x6e\x65\x65\x64\x73\x20\x74\x6f\x20\x62\x65\x20\x68\x61\x73\x68\x65\x64\x20\x62\x65\x66\x6f\x72\x65\x20\x62\x65\x69\x6e\x67\x20\x75\x73\x65\x64\x20\x62\x79\x20\x74\x68\x65\x20\x48\x4d\x41\x43\x20\x61\x6c\x67\x6f\x72\x69\x74\x68\x6d\x2e"
156     };
157     static const unsigned char outputs[6][32] = {
158         {0xb0, 0x34, 0x4c, 0x61, 0xd8, 0xdb, 0x38, 0x53, 0x5c, 0xa8, 0xaf, 0xce, 0xaf, 0x0b, 0xf1, 0x2b, 0x88, 0x1d, 0xc2, 0x00, 0xc9, 0x83, 0x3d, 0xa7, 0x26, 0xe9, 0x37, 0x6c, 0x2e, 0x32, 0xcf, 0xf7},
159         {0x5b, 0xdc, 0xc1, 0x46, 0xbf, 0x60, 0x75, 0x4e, 0x6a, 0x04, 0x24, 0x26, 0x08, 0x95, 0x75, 0xc7, 0x5a, 0x00, 0x3f, 0x08, 0x9d, 0x27, 0x39, 0x83, 0x9d, 0xec, 0x58, 0xb9, 0x64, 0xec, 0x38, 0x43},
160         {0x77, 0x3e, 0xa9, 0x1e, 0x36, 0x80, 0x0e, 0x46, 0x85, 0x4d, 0xb8, 0xeb, 0xd0, 0x91, 0x81, 0xa7, 0x29, 0x59, 0x09, 0x8b, 0x3e, 0xf8, 0xc1, 0x22, 0xd9, 0x63, 0x55, 0x14, 0xce, 0xd5, 0x65, 0xfe},
161         {0x82, 0x55, 0x8a, 0x38, 0x9a, 0x44, 0x3c, 0x0e, 0xa4, 0xcc, 0x81, 0x98, 0x99, 0xf2, 0x08, 0x3a, 0x85, 0xf0, 0xfa, 0xa3, 0xe5, 0x78, 0xf8, 0x07, 0x7a, 0x2e, 0x3f, 0xf4, 0x67, 0x29, 0x66, 0x5b},
162         {0x60, 0xe4, 0x31, 0x59, 0x1e, 0xe0, 0xb6, 0x7f, 0x0d, 0x8a, 0x26, 0xaa, 0xcb, 0xf5, 0xb7, 0x7f, 0x8e, 0x0b, 0xc6, 0x21, 0x37, 0x28, 0xc5, 0x14, 0x05, 0x46, 0x04, 0x0f, 0x0e, 0xe3, 0x7f, 0x54},
163         {0x9b, 0x09, 0xff, 0xa7, 0x1b, 0x94, 0x2f, 0xcb, 0x27, 0x63, 0x5f, 0xbc, 0xd5, 0xb0, 0xe9, 0x44, 0xbf, 0xdc, 0x63, 0x64, 0x4f, 0x07, 0x13, 0x93, 0x8a, 0x7f, 0x51, 0x53, 0x5c, 0x3a, 0x35, 0xe2}
164     };
165     int i;
166     for (i = 0; i < 6; i++) {
167         secp256k1_hmac_sha256_t hasher;
168         unsigned char out[32];
169         secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
170         secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), strlen(inputs[i]));
171         secp256k1_hmac_sha256_finalize(&hasher, out);
172         CHECK(memcmp(out, outputs[i], 32) == 0);
173         if (strlen(inputs[i]) > 0) {
174             int split = secp256k1_rand32() % strlen(inputs[i]);
175             secp256k1_hmac_sha256_initialize(&hasher, (const unsigned char*)(keys[i]), strlen(keys[i]));
176             secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i]), split);
177             secp256k1_hmac_sha256_write(&hasher, (const unsigned char*)(inputs[i] + split), strlen(inputs[i]) - split);
178             secp256k1_hmac_sha256_finalize(&hasher, out);
179             CHECK(memcmp(out, outputs[i], 32) == 0);
180         }
181     }
182 }
183
184 void run_rfc6979_hmac_sha256_tests(void) {
185     static const unsigned char key1[32] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f, 0x00};
186     static const unsigned char msg1[32] = {0x4b, 0xf5, 0x12, 0x2f, 0x34, 0x45, 0x54, 0xc5, 0x3b, 0xde, 0x2e, 0xbb, 0x8c, 0xd2, 0xb7, 0xe3, 0xd1, 0x60, 0x0a, 0xd6, 0x31, 0xc3, 0x85, 0xa5, 0xd7, 0xcc, 0xe2, 0x3c, 0x77, 0x85, 0x45, 0x9a};
187     static const unsigned char out1[3][32] = {
188         {0x4f, 0xe2, 0x95, 0x25, 0xb2, 0x08, 0x68, 0x09, 0x15, 0x9a, 0xcd, 0xf0, 0x50, 0x6e, 0xfb, 0x86, 0xb0, 0xec, 0x93, 0x2c, 0x7b, 0xa4, 0x42, 0x56, 0xab, 0x32, 0x1e, 0x42, 0x1e, 0x67, 0xe9, 0xfb},
189         {0x2b, 0xf0, 0xff, 0xf1, 0xd3, 0xc3, 0x78, 0xa2, 0x2d, 0xc5, 0xde, 0x1d, 0x85, 0x65, 0x22, 0x32, 0x5c, 0x65, 0xb5, 0x04, 0x49, 0x1a, 0x0c, 0xbd, 0x01, 0xcb, 0x8f, 0x3a, 0xa6, 0x7f, 0xfd, 0x4a},
190         {0xf5, 0x28, 0xb4, 0x10, 0xcb, 0x54, 0x1f, 0x77, 0x00, 0x0d, 0x7a, 0xfb, 0x6c, 0x5b, 0x53, 0xc5, 0xc4, 0x71, 0xea, 0xb4, 0x3e, 0x46, 0x6d, 0x9a, 0xc5, 0x19, 0x0c, 0x39, 0xc8, 0x2f, 0xd8, 0x2e}
191     };
192
193     static const unsigned char key2[32] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff};
194     static const unsigned char msg2[32] = {0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14, 0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24, 0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c, 0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55};
195     static const unsigned char out2[3][32] = {
196         {0x9c, 0x23, 0x6c, 0x16, 0x5b, 0x82, 0xae, 0x0c, 0xd5, 0x90, 0x65, 0x9e, 0x10, 0x0b, 0x6b, 0xab, 0x30, 0x36, 0xe7, 0xba, 0x8b, 0x06, 0x74, 0x9b, 0xaf, 0x69, 0x81, 0xe1, 0x6f, 0x1a, 0x2b, 0x95},
197         {0xdf, 0x47, 0x10, 0x61, 0x62, 0x5b, 0xc0, 0xea, 0x14, 0xb6, 0x82, 0xfe, 0xee, 0x2c, 0x9c, 0x02, 0xf2, 0x35, 0xda, 0x04, 0x20, 0x4c, 0x1d, 0x62, 0xa1, 0x53, 0x6c, 0x6e, 0x17, 0xae, 0xd7, 0xa9},
198         {0x75, 0x97, 0x88, 0x7c, 0xbd, 0x76, 0x32, 0x1f, 0x32, 0xe3, 0x04, 0x40, 0x67, 0x9a, 0x22, 0xcf, 0x7f, 0x8d, 0x9d, 0x2e, 0xac, 0x39, 0x0e, 0x58, 0x1f, 0xea, 0x09, 0x1c, 0xe2, 0x02, 0xba, 0x94}
199     };
200
201     secp256k1_rfc6979_hmac_sha256_t rng;
202     unsigned char out[32];
203     int i;
204
205     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key1, 32, msg1, 32);
206     for (i = 0; i < 3; i++) {
207         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
208         CHECK(memcmp(out, out1[i], 32) == 0);
209     }
210     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
211
212     secp256k1_rfc6979_hmac_sha256_initialize(&rng, key2, 32, msg2, 32);
213     for (i = 0; i < 3; i++) {
214         secp256k1_rfc6979_hmac_sha256_generate(&rng, out, 32);
215         CHECK(memcmp(out, out2[i], 32) == 0);
216     }
217     secp256k1_rfc6979_hmac_sha256_finalize(&rng);
218 }
219
220 /***** NUM TESTS *****/
221
222 #ifndef USE_NUM_NONE
223 void random_num_negate(secp256k1_num_t *num) {
224     if (secp256k1_rand32() & 1)
225         secp256k1_num_negate(num);
226 }
227
228 void random_num_order_test(secp256k1_num_t *num) {
229     secp256k1_scalar_t sc;
230     random_scalar_order_test(&sc);
231     secp256k1_scalar_get_num(num, &sc);
232 }
233
234 void random_num_order(secp256k1_num_t *num) {
235     secp256k1_scalar_t sc;
236     random_scalar_order(&sc);
237     secp256k1_scalar_get_num(num, &sc);
238 }
239
240 void test_num_negate(void) {
241     secp256k1_num_t n1;
242     secp256k1_num_t n2;
243     random_num_order_test(&n1); /* n1 = R */
244     random_num_negate(&n1);
245     secp256k1_num_copy(&n2, &n1); /* n2 = R */
246     secp256k1_num_sub(&n1, &n2, &n1); /* n1 = n2-n1 = 0 */
247     CHECK(secp256k1_num_is_zero(&n1));
248     secp256k1_num_copy(&n1, &n2); /* n1 = R */
249     secp256k1_num_negate(&n1); /* n1 = -R */
250     CHECK(!secp256k1_num_is_zero(&n1));
251     secp256k1_num_add(&n1, &n2, &n1); /* n1 = n2+n1 = 0 */
252     CHECK(secp256k1_num_is_zero(&n1));
253     secp256k1_num_copy(&n1, &n2); /* n1 = R */
254     secp256k1_num_negate(&n1); /* n1 = -R */
255     CHECK(secp256k1_num_is_neg(&n1) != secp256k1_num_is_neg(&n2));
256     secp256k1_num_negate(&n1); /* n1 = R */
257     CHECK(secp256k1_num_eq(&n1, &n2));
258 }
259
260 void test_num_add_sub(void) {
261     secp256k1_num_t n1;
262     secp256k1_num_t n2;
263     secp256k1_num_t n1p2, n2p1, n1m2, n2m1;
264     int r = secp256k1_rand32();
265     random_num_order_test(&n1); /* n1 = R1 */
266     if (r & 1) {
267         random_num_negate(&n1);
268     }
269     random_num_order_test(&n2); /* n2 = R2 */
270     if (r & 2) {
271         random_num_negate(&n2);
272     }
273     secp256k1_num_add(&n1p2, &n1, &n2); /* n1p2 = R1 + R2 */
274     secp256k1_num_add(&n2p1, &n2, &n1); /* n2p1 = R2 + R1 */
275     secp256k1_num_sub(&n1m2, &n1, &n2); /* n1m2 = R1 - R2 */
276     secp256k1_num_sub(&n2m1, &n2, &n1); /* n2m1 = R2 - R1 */
277     CHECK(secp256k1_num_eq(&n1p2, &n2p1));
278     CHECK(!secp256k1_num_eq(&n1p2, &n1m2));
279     secp256k1_num_negate(&n2m1); /* n2m1 = -R2 + R1 */
280     CHECK(secp256k1_num_eq(&n2m1, &n1m2));
281     CHECK(!secp256k1_num_eq(&n2m1, &n1));
282     secp256k1_num_add(&n2m1, &n2m1, &n2); /* n2m1 = -R2 + R1 + R2 = R1 */
283     CHECK(secp256k1_num_eq(&n2m1, &n1));
284     CHECK(!secp256k1_num_eq(&n2p1, &n1));
285     secp256k1_num_sub(&n2p1, &n2p1, &n2); /* n2p1 = R2 + R1 - R2 = R1 */
286     CHECK(secp256k1_num_eq(&n2p1, &n1));
287 }
288
289 void run_num_smalltests(void) {
290     int i;
291     for (i = 0; i < 100*count; i++) {
292         test_num_negate();
293         test_num_add_sub();
294     }
295 }
296 #endif
297
298 /***** SCALAR TESTS *****/
299
300 void scalar_test(void) {
301     secp256k1_scalar_t s;
302     secp256k1_scalar_t s1;
303     secp256k1_scalar_t s2;
304 #ifndef USE_NUM_NONE
305     secp256k1_num_t snum, s1num, s2num;
306     secp256k1_num_t order, half_order;
307 #endif
308     unsigned char c[32];
309
310     /* Set 's' to a random scalar, with value 'snum'. */
311     random_scalar_order_test(&s);
312
313     /* Set 's1' to a random scalar, with value 's1num'. */
314     random_scalar_order_test(&s1);
315
316     /* Set 's2' to a random scalar, with value 'snum2', and byte array representation 'c'. */
317     random_scalar_order_test(&s2);
318     secp256k1_scalar_get_b32(c, &s2);
319
320 #ifndef USE_NUM_NONE
321     secp256k1_scalar_get_num(&snum, &s);
322     secp256k1_scalar_get_num(&s1num, &s1);
323     secp256k1_scalar_get_num(&s2num, &s2);
324
325     secp256k1_scalar_order_get_num(&order);
326     half_order = order;
327     secp256k1_num_shift(&half_order, 1);
328 #endif
329
330     {
331         int i;
332         /* Test that fetching groups of 4 bits from a scalar and recursing n(i)=16*n(i-1)+p(i) reconstructs it. */
333         secp256k1_scalar_t n;
334         secp256k1_scalar_set_int(&n, 0);
335         for (i = 0; i < 256; i += 4) {
336             secp256k1_scalar_t t;
337             int j;
338             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits(&s, 256 - 4 - i, 4));
339             for (j = 0; j < 4; j++) {
340                 secp256k1_scalar_add(&n, &n, &n);
341             }
342             secp256k1_scalar_add(&n, &n, &t);
343         }
344         CHECK(secp256k1_scalar_eq(&n, &s));
345     }
346
347     {
348         /* Test that fetching groups of randomly-sized bits from a scalar and recursing n(i)=b*n(i-1)+p(i) reconstructs it. */
349         secp256k1_scalar_t n;
350         int i = 0;
351         secp256k1_scalar_set_int(&n, 0);
352         while (i < 256) {
353             secp256k1_scalar_t t;
354             int j;
355             int now = (secp256k1_rand32() % 15) + 1;
356             if (now + i > 256) {
357                 now = 256 - i;
358             }
359             secp256k1_scalar_set_int(&t, secp256k1_scalar_get_bits_var(&s, 256 - now - i, now));
360             for (j = 0; j < now; j++) {
361                 secp256k1_scalar_add(&n, &n, &n);
362             }
363             secp256k1_scalar_add(&n, &n, &t);
364             i += now;
365         }
366         CHECK(secp256k1_scalar_eq(&n, &s));
367     }
368
369 #ifndef USE_NUM_NONE
370     {
371         /* Test that adding the scalars together is equal to adding their numbers together modulo the order. */
372         secp256k1_num_t rnum;
373         secp256k1_num_t r2num;
374         secp256k1_scalar_t r;
375         secp256k1_num_add(&rnum, &snum, &s2num);
376         secp256k1_num_mod(&rnum, &order);
377         secp256k1_scalar_add(&r, &s, &s2);
378         secp256k1_scalar_get_num(&r2num, &r);
379         CHECK(secp256k1_num_eq(&rnum, &r2num));
380     }
381
382     {
383         /* Test that multipying the scalars is equal to multiplying their numbers modulo the order. */
384         secp256k1_scalar_t r;
385         secp256k1_num_t r2num;
386         secp256k1_num_t rnum;
387         secp256k1_num_mul(&rnum, &snum, &s2num);
388         secp256k1_num_mod(&rnum, &order);
389         secp256k1_scalar_mul(&r, &s, &s2);
390         secp256k1_scalar_get_num(&r2num, &r);
391         CHECK(secp256k1_num_eq(&rnum, &r2num));
392         /* The result can only be zero if at least one of the factors was zero. */
393         CHECK(secp256k1_scalar_is_zero(&r) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_zero(&s2)));
394         /* The results can only be equal to one of the factors if that factor was zero, or the other factor was one. */
395         CHECK(secp256k1_num_eq(&rnum, &snum) == (secp256k1_scalar_is_zero(&s) || secp256k1_scalar_is_one(&s2)));
396         CHECK(secp256k1_num_eq(&rnum, &s2num) == (secp256k1_scalar_is_zero(&s2) || secp256k1_scalar_is_one(&s)));
397     }
398
399     {
400         secp256k1_scalar_t neg;
401         secp256k1_num_t negnum;
402         secp256k1_num_t negnum2;
403         /* Check that comparison with zero matches comparison with zero on the number. */
404         CHECK(secp256k1_num_is_zero(&snum) == secp256k1_scalar_is_zero(&s));
405         /* Check that comparison with the half order is equal to testing for high scalar. */
406         CHECK(secp256k1_scalar_is_high(&s) == (secp256k1_num_cmp(&snum, &half_order) > 0));
407         secp256k1_scalar_negate(&neg, &s);
408         secp256k1_num_sub(&negnum, &order, &snum);
409         secp256k1_num_mod(&negnum, &order);
410         /* Check that comparison with the half order is equal to testing for high scalar after negation. */
411         CHECK(secp256k1_scalar_is_high(&neg) == (secp256k1_num_cmp(&negnum, &half_order) > 0));
412         /* Negating should change the high property, unless the value was already zero. */
413         CHECK((secp256k1_scalar_is_high(&s) == secp256k1_scalar_is_high(&neg)) == secp256k1_scalar_is_zero(&s));
414         secp256k1_scalar_get_num(&negnum2, &neg);
415         /* Negating a scalar should be equal to (order - n) mod order on the number. */
416         CHECK(secp256k1_num_eq(&negnum, &negnum2));
417         secp256k1_scalar_add(&neg, &neg, &s);
418         /* Adding a number to its negation should result in zero. */
419         CHECK(secp256k1_scalar_is_zero(&neg));
420         secp256k1_scalar_negate(&neg, &neg);
421         /* Negating zero should still result in zero. */
422         CHECK(secp256k1_scalar_is_zero(&neg));
423     }
424
425     {
426         /* Test secp256k1_scalar_mul_shift_var. */
427         secp256k1_scalar_t r;
428         secp256k1_num_t one;
429         secp256k1_num_t rnum;
430         secp256k1_num_t rnum2;
431         unsigned char cone[1] = {0x01};
432         unsigned int shift = 256 + (secp256k1_rand32() % 257);
433         secp256k1_scalar_mul_shift_var(&r, &s1, &s2, shift);
434         secp256k1_num_mul(&rnum, &s1num, &s2num);
435         secp256k1_num_shift(&rnum, shift - 1);
436         secp256k1_num_set_bin(&one, cone, 1);
437         secp256k1_num_add(&rnum, &rnum, &one);
438         secp256k1_num_shift(&rnum, 1);
439         secp256k1_scalar_get_num(&rnum2, &r);
440         CHECK(secp256k1_num_eq(&rnum, &rnum2));
441     }
442 #endif
443
444     {
445         /* Test that scalar inverses are equal to the inverse of their number modulo the order. */
446         if (!secp256k1_scalar_is_zero(&s)) {
447             secp256k1_scalar_t inv;
448 #ifndef USE_NUM_NONE
449             secp256k1_num_t invnum;
450             secp256k1_num_t invnum2;
451 #endif
452             secp256k1_scalar_inverse(&inv, &s);
453 #ifndef USE_NUM_NONE
454             secp256k1_num_mod_inverse(&invnum, &snum, &order);
455             secp256k1_scalar_get_num(&invnum2, &inv);
456             CHECK(secp256k1_num_eq(&invnum, &invnum2));
457 #endif
458             secp256k1_scalar_mul(&inv, &inv, &s);
459             /* Multiplying a scalar with its inverse must result in one. */
460             CHECK(secp256k1_scalar_is_one(&inv));
461             secp256k1_scalar_inverse(&inv, &inv);
462             /* Inverting one must result in one. */
463             CHECK(secp256k1_scalar_is_one(&inv));
464         }
465     }
466
467     {
468         /* Test commutativity of add. */
469         secp256k1_scalar_t r1, r2;
470         secp256k1_scalar_add(&r1, &s1, &s2);
471         secp256k1_scalar_add(&r2, &s2, &s1);
472         CHECK(secp256k1_scalar_eq(&r1, &r2));
473     }
474
475     {
476         secp256k1_scalar_t r1, r2;
477         secp256k1_scalar_t b;
478         int i;
479         /* Test add_bit. */
480         int bit = secp256k1_rand32() % 256;
481         secp256k1_scalar_set_int(&b, 1);
482         CHECK(secp256k1_scalar_is_one(&b));
483         for (i = 0; i < bit; i++) {
484             secp256k1_scalar_add(&b, &b, &b);
485         }
486         r1 = s1;
487         r2 = s1;
488         if (!secp256k1_scalar_add(&r1, &r1, &b)) {
489             /* No overflow happened. */
490             secp256k1_scalar_add_bit(&r2, bit);
491             CHECK(secp256k1_scalar_eq(&r1, &r2));
492         }
493     }
494
495     {
496         /* Test commutativity of mul. */
497         secp256k1_scalar_t r1, r2;
498         secp256k1_scalar_mul(&r1, &s1, &s2);
499         secp256k1_scalar_mul(&r2, &s2, &s1);
500         CHECK(secp256k1_scalar_eq(&r1, &r2));
501     }
502
503     {
504         /* Test associativity of add. */
505         secp256k1_scalar_t r1, r2;
506         secp256k1_scalar_add(&r1, &s1, &s2);
507         secp256k1_scalar_add(&r1, &r1, &s);
508         secp256k1_scalar_add(&r2, &s2, &s);
509         secp256k1_scalar_add(&r2, &s1, &r2);
510         CHECK(secp256k1_scalar_eq(&r1, &r2));
511     }
512
513     {
514         /* Test associativity of mul. */
515         secp256k1_scalar_t r1, r2;
516         secp256k1_scalar_mul(&r1, &s1, &s2);
517         secp256k1_scalar_mul(&r1, &r1, &s);
518         secp256k1_scalar_mul(&r2, &s2, &s);
519         secp256k1_scalar_mul(&r2, &s1, &r2);
520         CHECK(secp256k1_scalar_eq(&r1, &r2));
521     }
522
523     {
524         /* Test distributitivity of mul over add. */
525         secp256k1_scalar_t r1, r2, t;
526         secp256k1_scalar_add(&r1, &s1, &s2);
527         secp256k1_scalar_mul(&r1, &r1, &s);
528         secp256k1_scalar_mul(&r2, &s1, &s);
529         secp256k1_scalar_mul(&t, &s2, &s);
530         secp256k1_scalar_add(&r2, &r2, &t);
531         CHECK(secp256k1_scalar_eq(&r1, &r2));
532     }
533
534     {
535         /* Test square. */
536         secp256k1_scalar_t r1, r2;
537         secp256k1_scalar_sqr(&r1, &s1);
538         secp256k1_scalar_mul(&r2, &s1, &s1);
539         CHECK(secp256k1_scalar_eq(&r1, &r2));
540     }
541
542     {
543         /* Test multiplicative identity. */
544         secp256k1_scalar_t r1, v1;
545         secp256k1_scalar_set_int(&v1,1);
546         secp256k1_scalar_mul(&r1, &s1, &v1);
547         CHECK(secp256k1_scalar_eq(&r1, &s1));
548     }
549
550     {
551         /* Test additive identity. */
552         secp256k1_scalar_t r1, v0;
553         secp256k1_scalar_set_int(&v0,0);
554         secp256k1_scalar_add(&r1, &s1, &v0);
555         CHECK(secp256k1_scalar_eq(&r1, &s1));
556     }
557
558     {
559         /* Test zero product property. */
560         secp256k1_scalar_t r1, v0;
561         secp256k1_scalar_set_int(&v0,0);
562         secp256k1_scalar_mul(&r1, &s1, &v0);
563         CHECK(secp256k1_scalar_eq(&r1, &v0));
564     }
565
566 }
567
568 void run_scalar_tests(void) {
569     int i;
570     for (i = 0; i < 128 * count; i++) {
571         scalar_test();
572     }
573
574     {
575         /* (-1)+1 should be zero. */
576         secp256k1_scalar_t s, o;
577         secp256k1_scalar_set_int(&s, 1);
578         CHECK(secp256k1_scalar_is_one(&s));
579         secp256k1_scalar_negate(&o, &s);
580         secp256k1_scalar_add(&o, &o, &s);
581         CHECK(secp256k1_scalar_is_zero(&o));
582         secp256k1_scalar_negate(&o, &o);
583         CHECK(secp256k1_scalar_is_zero(&o));
584     }
585
586 #ifndef USE_NUM_NONE
587     {
588         /* A scalar with value of the curve order should be 0. */
589         secp256k1_num_t order;
590         secp256k1_scalar_t zero;
591         unsigned char bin[32];
592         int overflow = 0;
593         secp256k1_scalar_order_get_num(&order);
594         secp256k1_num_get_bin(bin, 32, &order);
595         secp256k1_scalar_set_b32(&zero, bin, &overflow);
596         CHECK(overflow == 1);
597         CHECK(secp256k1_scalar_is_zero(&zero));
598     }
599 #endif
600 }
601
602 /***** FIELD TESTS *****/
603
604 void random_fe(secp256k1_fe_t *x) {
605     unsigned char bin[32];
606     do {
607         secp256k1_rand256(bin);
608         if (secp256k1_fe_set_b32(x, bin)) {
609             return;
610         }
611     } while(1);
612 }
613
614 void random_fe_non_zero(secp256k1_fe_t *nz) {
615     int tries = 10;
616     while (--tries >= 0) {
617         random_fe(nz);
618         secp256k1_fe_normalize(nz);
619         if (!secp256k1_fe_is_zero(nz))
620             break;
621     }
622     /* Infinitesimal probability of spurious failure here */
623     CHECK(tries >= 0);
624 }
625
626 void random_fe_non_square(secp256k1_fe_t *ns) {
627     secp256k1_fe_t r;
628     random_fe_non_zero(ns);
629     if (secp256k1_fe_sqrt_var(&r, ns)) {
630         secp256k1_fe_negate(ns, ns, 1);
631     }
632 }
633
634 int check_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
635     secp256k1_fe_t an = *a;
636     secp256k1_fe_t bn = *b;
637     secp256k1_fe_normalize_weak(&an);
638     secp256k1_fe_normalize_var(&bn);
639     return secp256k1_fe_equal_var(&an, &bn);
640 }
641
642 int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
643     secp256k1_fe_t x;
644     secp256k1_fe_t one;
645     secp256k1_fe_mul(&x, a, ai);
646     secp256k1_fe_set_int(&one, 1);
647     return check_fe_equal(&x, &one);
648 }
649
650 void run_field_convert(void) {
651     static const unsigned char b32[32] = {
652         0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
653         0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18,
654         0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29,
655         0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x40
656     };
657     static const char *c64 = "0001020304050607111213141516171822232425262728293334353637383940";
658     static const secp256k1_fe_storage_t fes = SECP256K1_FE_STORAGE_CONST(
659         0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
660         0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
661     );
662     static const secp256k1_fe_t fe = SECP256K1_FE_CONST(
663         0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
664         0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
665     );
666     secp256k1_fe_t fe2;
667     unsigned char b322[32];
668     char c642[64];
669     secp256k1_fe_storage_t fes2;
670     /* Check conversions to fe. */
671     CHECK(secp256k1_fe_set_b32(&fe2, b32));
672     CHECK(secp256k1_fe_equal_var(&fe, &fe2));
673     CHECK(secp256k1_fe_set_hex(&fe2, c64));
674     CHECK(secp256k1_fe_equal_var(&fe, &fe2));
675     secp256k1_fe_from_storage(&fe2, &fes);
676     CHECK(secp256k1_fe_equal_var(&fe, &fe2));
677     /* Check conversion from fe. */
678     secp256k1_fe_get_b32(b322, &fe);
679     CHECK(memcmp(b322, b32, 32) == 0);
680     secp256k1_fe_get_hex(c642, &fe);
681     CHECK(memcmp(c642, c64, 64) == 0);
682     secp256k1_fe_to_storage(&fes2, &fe);
683     CHECK(memcmp(&fes2, &fes, sizeof(fes)) == 0);
684 }
685
686 void run_field_misc(void) {
687     const unsigned char f32_5[32] = {
688         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
689         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
690         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
691         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x05,
692     };
693     secp256k1_fe_t x;
694     secp256k1_fe_t y;
695     secp256k1_fe_t z;
696     secp256k1_fe_t q;
697     secp256k1_fe_t fe5;
698     int i;
699     CHECK(secp256k1_fe_set_b32(&fe5, f32_5));
700     for (i = 0; i < 5*count; i++) {
701         secp256k1_fe_storage_t xs, ys, zs;
702         random_fe(&x);
703         random_fe_non_zero(&y);
704         /* Test the fe equality and comparison operations. */
705         CHECK(secp256k1_fe_cmp_var(&x, &x) == 0);
706         CHECK(secp256k1_fe_equal_var(&x, &x));
707         z = x;
708         secp256k1_fe_add(&z,&y);
709         secp256k1_fe_normalize(&z);
710         /* Test storage conversion and conditional moves. */
711         secp256k1_fe_to_storage(&xs, &x);
712         secp256k1_fe_to_storage(&ys, &y);
713         secp256k1_fe_to_storage(&zs, &z);
714         secp256k1_fe_storage_cmov(&zs, &xs, 0);
715         CHECK(memcmp(&xs, &zs, sizeof(xs)) != 0);
716         secp256k1_fe_storage_cmov(&ys, &xs, 1);
717         CHECK(memcmp(&xs, &ys, sizeof(xs)) == 0);
718         secp256k1_fe_from_storage(&x, &xs);
719         secp256k1_fe_from_storage(&y, &ys);
720         secp256k1_fe_from_storage(&z, &zs);
721         /* Test that mul_int, mul, and add agree. */
722         secp256k1_fe_add(&y, &x);
723         secp256k1_fe_add(&y, &x);
724         z = x;
725         secp256k1_fe_mul_int(&z, 3);
726         CHECK(check_fe_equal(&y, &z));
727         secp256k1_fe_add(&y, &x);
728         secp256k1_fe_add(&z, &x);
729         CHECK(check_fe_equal(&z, &y));
730         z = x;
731         secp256k1_fe_mul_int(&z, 5);
732         secp256k1_fe_mul(&q, &x, &fe5);
733         CHECK(check_fe_equal(&z, &q));
734         secp256k1_fe_negate(&x, &x, 1);
735         secp256k1_fe_add(&z, &x);
736         secp256k1_fe_add(&q, &x);
737         CHECK(check_fe_equal(&y, &z));
738         CHECK(check_fe_equal(&q, &y));
739     }
740 }
741
742 void run_field_inv(void) {
743     secp256k1_fe_t x, xi, xii;
744     int i;
745     for (i = 0; i < 10*count; i++) {
746         random_fe_non_zero(&x);
747         secp256k1_fe_inv(&xi, &x);
748         CHECK(check_fe_inverse(&x, &xi));
749         secp256k1_fe_inv(&xii, &xi);
750         CHECK(check_fe_equal(&x, &xii));
751     }
752 }
753
754 void run_field_inv_var(void) {
755     secp256k1_fe_t x, xi, xii;
756     int i;
757     for (i = 0; i < 10*count; i++) {
758         random_fe_non_zero(&x);
759         secp256k1_fe_inv_var(&xi, &x);
760         CHECK(check_fe_inverse(&x, &xi));
761         secp256k1_fe_inv_var(&xii, &xi);
762         CHECK(check_fe_equal(&x, &xii));
763     }
764 }
765
766 void run_field_inv_all_var(void) {
767     secp256k1_fe_t x[16], xi[16], xii[16];
768     int i;
769     /* Check it's safe to call for 0 elements */
770     secp256k1_fe_inv_all_var(0, xi, x);
771     for (i = 0; i < count; i++) {
772         size_t j;
773         size_t len = (secp256k1_rand32() & 15) + 1;
774         for (j = 0; j < len; j++)
775             random_fe_non_zero(&x[j]);
776         secp256k1_fe_inv_all_var(len, xi, x);
777         for (j = 0; j < len; j++)
778             CHECK(check_fe_inverse(&x[j], &xi[j]));
779         secp256k1_fe_inv_all_var(len, xii, xi);
780         for (j = 0; j < len; j++)
781             CHECK(check_fe_equal(&x[j], &xii[j]));
782     }
783 }
784
785 void run_sqr(void) {
786     secp256k1_fe_t x, s;
787
788     {
789         int i;
790         secp256k1_fe_set_int(&x, 1);
791         secp256k1_fe_negate(&x, &x, 1);
792
793         for (i = 1; i <= 512; ++i) {
794             secp256k1_fe_mul_int(&x, 2);
795             secp256k1_fe_normalize(&x);
796             secp256k1_fe_sqr(&s, &x);
797         }
798     }
799 }
800
801 void test_sqrt(const secp256k1_fe_t *a, const secp256k1_fe_t *k) {
802     secp256k1_fe_t r1, r2;
803     int v = secp256k1_fe_sqrt_var(&r1, a);
804     CHECK((v == 0) == (k == NULL));
805
806     if (k != NULL) {
807         /* Check that the returned root is +/- the given known answer */
808         secp256k1_fe_negate(&r2, &r1, 1);
809         secp256k1_fe_add(&r1, k); secp256k1_fe_add(&r2, k);
810         secp256k1_fe_normalize(&r1); secp256k1_fe_normalize(&r2);
811         CHECK(secp256k1_fe_is_zero(&r1) || secp256k1_fe_is_zero(&r2));
812     }
813 }
814
815 void run_sqrt(void) {
816     secp256k1_fe_t ns, x, s, t;
817     int i;
818
819     /* Check sqrt(0) is 0 */
820     secp256k1_fe_set_int(&x, 0);
821     secp256k1_fe_sqr(&s, &x);
822     test_sqrt(&s, &x);
823
824     /* Check sqrt of small squares (and their negatives) */
825     for (i = 1; i <= 100; i++) {
826         secp256k1_fe_set_int(&x, i);
827         secp256k1_fe_sqr(&s, &x);
828         test_sqrt(&s, &x);
829         secp256k1_fe_negate(&t, &s, 1);
830         test_sqrt(&t, NULL);
831     }
832
833     /* Consistency checks for large random values */
834     for (i = 0; i < 10; i++) {
835         int j;
836         random_fe_non_square(&ns);
837         for (j = 0; j < count; j++) {
838             random_fe(&x);
839             secp256k1_fe_sqr(&s, &x);
840             test_sqrt(&s, &x);
841             secp256k1_fe_negate(&t, &s, 1);
842             test_sqrt(&t, NULL);
843             secp256k1_fe_mul(&t, &s, &ns);
844             test_sqrt(&t, NULL);
845         }
846     }
847 }
848
849 /***** GROUP TESTS *****/
850
851 void ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
852     CHECK(a->infinity == b->infinity);
853     if (a->infinity)
854         return;
855     CHECK(secp256k1_fe_equal_var(&a->x, &b->x));
856     CHECK(secp256k1_fe_equal_var(&b->y, &b->y));
857 }
858
859 void ge_equals_gej(const secp256k1_ge_t *a, const secp256k1_gej_t *b) {
860     secp256k1_fe_t z2s;
861     secp256k1_fe_t u1, u2, s1, s2;
862     CHECK(a->infinity == b->infinity);
863     if (a->infinity)
864         return;
865     /* Check a.x * b.z^2 == b.x && a.y * b.z^3 == b.y, to avoid inverses. */
866     secp256k1_fe_sqr(&z2s, &b->z);
867     secp256k1_fe_mul(&u1, &a->x, &z2s);
868     u2 = b->x; secp256k1_fe_normalize_weak(&u2);
869     secp256k1_fe_mul(&s1, &a->y, &z2s); secp256k1_fe_mul(&s1, &s1, &b->z);
870     s2 = b->y; secp256k1_fe_normalize_weak(&s2);
871     CHECK(secp256k1_fe_equal_var(&u1, &u2));
872     CHECK(secp256k1_fe_equal_var(&s1, &s2));
873 }
874
875 void test_ge(void) {
876     int i, i1;
877     int runs = 4;
878     /* Points: (infinity, p1, p1, -p1, -p1, p2, p2, -p2, -p2, p3, p3, -p3, -p3, p4, p4, -p4, -p4).
879      * The second in each pair of identical points uses a random Z coordinate in the Jacobian form.
880      * All magnitudes are randomized.
881      * All 17*17 combinations of points are added to eachother, using all applicable methods.
882      */
883     secp256k1_ge_t *ge = malloc(sizeof(secp256k1_ge_t) * (1 + 4 * runs));
884     secp256k1_gej_t *gej = malloc(sizeof(secp256k1_gej_t) * (1 + 4 * runs));
885     secp256k1_gej_set_infinity(&gej[0]);
886     secp256k1_ge_clear(&ge[0]);
887     secp256k1_ge_set_gej_var(&ge[0], &gej[0]);
888     for (i = 0; i < runs; i++) {
889         int j;
890         secp256k1_ge_t g;
891         random_group_element_test(&g);
892         ge[1 + 4 * i] = g;
893         ge[2 + 4 * i] = g;
894         secp256k1_ge_neg(&ge[3 + 4 * i], &g);
895         secp256k1_ge_neg(&ge[4 + 4 * i], &g);
896         secp256k1_gej_set_ge(&gej[1 + 4 * i], &ge[1 + 4 * i]);
897         random_group_element_jacobian_test(&gej[2 + 4 * i], &ge[2 + 4 * i]);
898         secp256k1_gej_set_ge(&gej[3 + 4 * i], &ge[3 + 4 * i]);
899         random_group_element_jacobian_test(&gej[4 + 4 * i], &ge[4 + 4 * i]);
900         for (j = 0; j < 4; j++) {
901             random_field_element_magnitude(&ge[1 + j + 4 * i].x);
902             random_field_element_magnitude(&ge[1 + j + 4 * i].y);
903             random_field_element_magnitude(&gej[1 + j + 4 * i].x);
904             random_field_element_magnitude(&gej[1 + j + 4 * i].y);
905             random_field_element_magnitude(&gej[1 + j + 4 * i].z);
906         }
907     }
908
909     for (i1 = 0; i1 < 1 + 4 * runs; i1++) {
910         int i2;
911         for (i2 = 0; i2 < 1 + 4 * runs; i2++) {
912             /* Compute reference result using gej + gej (var). */
913             secp256k1_gej_t refj, resj;
914             secp256k1_ge_t ref;
915             secp256k1_gej_add_var(&refj, &gej[i1], &gej[i2]);
916             secp256k1_ge_set_gej_var(&ref, &refj);
917
918             /* Test gej + ge (var). */
919             secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2]);
920             ge_equals_gej(&ref, &resj);
921
922             /* Test gej + ge (const). */
923             if (i2 != 0) {
924                 /* secp256k1_gej_add_ge does not support its second argument being infinity. */
925                 secp256k1_gej_add_ge(&resj, &gej[i1], &ge[i2]);
926                 ge_equals_gej(&ref, &resj);
927             }
928
929             /* Test doubling (var). */
930             if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 == ((i2 + 3)%4)/2)) {
931                 /* Normal doubling. */
932                 secp256k1_gej_double_var(&resj, &gej[i1]);
933                 ge_equals_gej(&ref, &resj);
934                 secp256k1_gej_double_var(&resj, &gej[i2]);
935                 ge_equals_gej(&ref, &resj);
936             }
937
938             /* Test adding opposites. */
939             if ((i1 == 0 && i2 == 0) || ((i1 + 3)/4 == (i2 + 3)/4 && ((i1 + 3)%4)/2 != ((i2 + 3)%4)/2)) {
940                 CHECK(secp256k1_ge_is_infinity(&ref));
941             }
942
943             /* Test adding infinity. */
944             if (i1 == 0) {
945                 CHECK(secp256k1_ge_is_infinity(&ge[i1]));
946                 CHECK(secp256k1_gej_is_infinity(&gej[i1]));
947                 ge_equals_gej(&ref, &gej[i2]);
948             }
949             if (i2 == 0) {
950                 CHECK(secp256k1_ge_is_infinity(&ge[i2]));
951                 CHECK(secp256k1_gej_is_infinity(&gej[i2]));
952                 ge_equals_gej(&ref, &gej[i1]);
953             }
954         }
955     }
956
957     /* Test adding all points together in random order equals infinity. */
958     {
959         secp256k1_gej_t sum;
960         secp256k1_gej_t *gej_shuffled = malloc((4 * runs + 1) * sizeof(secp256k1_gej_t));
961         for (i = 0; i < 4 * runs + 1; i++) {
962             gej_shuffled[i] = gej[i];
963         }
964         for (i = 0; i < 4 * runs + 1; i++) {
965             int swap = i + secp256k1_rand32() % (4 * runs + 1 - i);
966             if (swap != i) {
967                 secp256k1_gej_t t = gej_shuffled[i];
968                 gej_shuffled[i] = gej_shuffled[swap];
969                 gej_shuffled[swap] = t;
970             }
971         }
972         secp256k1_gej_set_infinity(&sum);
973         for (i = 0; i < 4 * runs + 1; i++) {
974             secp256k1_gej_add_var(&sum, &sum, &gej_shuffled[i]);
975         }
976         CHECK(secp256k1_gej_is_infinity(&sum));
977         free(gej_shuffled);
978     }
979
980     /* Test batch gej -> ge conversion. */
981     {
982         secp256k1_ge_t *ge_set_all = malloc((4 * runs + 1) * sizeof(secp256k1_ge_t));
983         secp256k1_ge_set_all_gej_var(4 * runs + 1, ge_set_all, gej);
984         for (i = 0; i < 4 * runs + 1; i++) {
985             ge_equals_gej(&ge_set_all[i], &gej[i]);
986         }
987         free(ge_set_all);
988     }
989
990     free(ge);
991     free(gej);
992 }
993
994 void run_ge(void) {
995     int i;
996     for (i = 0; i < count * 32; i++) {
997         test_ge();
998     }
999 }
1000
1001 /***** ECMULT TESTS *****/
1002
1003 void run_ecmult_chain(void) {
1004     secp256k1_gej_t a;
1005     secp256k1_gej_t x;
1006     secp256k1_gej_t x2;
1007     secp256k1_fe_t ax;
1008     secp256k1_fe_t ay;
1009     secp256k1_scalar_t xn;
1010     secp256k1_scalar_t gn;
1011     secp256k1_scalar_t xf;
1012     secp256k1_scalar_t gf;
1013     secp256k1_scalar_t ae;
1014     secp256k1_scalar_t ge;
1015     int i;
1016     /* two random initial factors xn and gn */
1017     static const unsigned char xni[32] = {
1018         0x84, 0xcc, 0x54, 0x52, 0xf7, 0xfd, 0xe1, 0xed,
1019         0xb4, 0xd3, 0x8a, 0x8c, 0xe9, 0xb1, 0xb8, 0x4c,
1020         0xce, 0xf3, 0x1f, 0x14, 0x6e, 0x56, 0x9b, 0xe9,
1021         0x70, 0x5d, 0x35, 0x7a, 0x42, 0x98, 0x54, 0x07
1022     };
1023     static const unsigned char gni[32] = {
1024         0xa1, 0xe5, 0x8d, 0x22, 0x55, 0x3d, 0xcd, 0x42,
1025         0xb2, 0x39, 0x80, 0x62, 0x5d, 0x4c, 0x57, 0xa9,
1026         0x6e, 0x93, 0x23, 0xd4, 0x2b, 0x31, 0x52, 0xe5,
1027         0xca, 0x2c, 0x39, 0x90, 0xed, 0xc7, 0xc9, 0xde
1028     };
1029     /* two small multipliers to be applied to xn and gn in every iteration: */
1030     static const unsigned char xfi[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x13,0x37};
1031     static const unsigned char gfi[32] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0x71,0x13};
1032     char res[131];
1033     char res2[131];
1034     /* random starting point A (on the curve) */
1035     VERIFY_CHECK(secp256k1_fe_set_hex(&ax, "8b30bbe9ae2a990696b22f670709dff3727fd8bc04d3362c6c7bf458e2846004"));
1036     VERIFY_CHECK(secp256k1_fe_set_hex(&ay, "a357ae915c4a65281309edf20504740f0eb3343990216b4f81063cb65f2f7e0f"));
1037     secp256k1_gej_set_xy(&a, &ax, &ay);
1038     secp256k1_scalar_set_b32(&xn, xni, NULL);
1039     secp256k1_scalar_set_b32(&gn, gni, NULL);
1040     secp256k1_scalar_set_b32(&xf, xfi, NULL);
1041     secp256k1_scalar_set_b32(&gf, gfi, NULL);
1042     /* accumulators with the resulting coefficients to A and G */
1043     secp256k1_scalar_set_int(&ae, 1);
1044     secp256k1_scalar_set_int(&ge, 0);
1045     /* the point being computed */
1046     x = a;
1047     for (i = 0; i < 200*count; i++) {
1048         /* in each iteration, compute X = xn*X + gn*G; */
1049         secp256k1_ecmult(&x, &x, &xn, &gn);
1050         /* also compute ae and ge: the actual accumulated factors for A and G */
1051         /* if X was (ae*A+ge*G), xn*X + gn*G results in (xn*ae*A + (xn*ge+gn)*G) */
1052         secp256k1_scalar_mul(&ae, &ae, &xn);
1053         secp256k1_scalar_mul(&ge, &ge, &xn);
1054         secp256k1_scalar_add(&ge, &ge, &gn);
1055         /* modify xn and gn */
1056         secp256k1_scalar_mul(&xn, &xn, &xf);
1057         secp256k1_scalar_mul(&gn, &gn, &gf);
1058
1059         /* verify */
1060         if (i == 19999) {
1061             secp256k1_gej_get_hex(res, &x);
1062             CHECK(memcmp(res, "(D6E96687F9B10D092A6F35439D86CEBEA4535D0D409F53586440BD74B933E830,B95CBCA2C77DA786539BE8FD53354D2D3B4F566AE658045407ED6015EE1B2A88)", 131) == 0);
1063         }
1064     }
1065     /* redo the computation, but directly with the resulting ae and ge coefficients: */
1066     secp256k1_ecmult(&x2, &a, &ae, &ge);
1067     secp256k1_gej_get_hex(res, &x);
1068     secp256k1_gej_get_hex(res2, &x2);
1069     CHECK(memcmp(res, res2, 131) == 0);
1070 }
1071
1072 void test_point_times_order(const secp256k1_gej_t *point) {
1073     /* X * (point + G) + (order-X) * (pointer + G) = 0 */
1074     secp256k1_scalar_t x;
1075     secp256k1_scalar_t nx;
1076     secp256k1_gej_t res1, res2;
1077     secp256k1_ge_t res3;
1078     unsigned char pub[65];
1079     int psize = 65;
1080     random_scalar_order_test(&x);
1081     secp256k1_scalar_negate(&nx, &x);
1082     secp256k1_ecmult(&res1, point, &x, &x); /* calc res1 = x * point + x * G; */
1083     secp256k1_ecmult(&res2, point, &nx, &nx); /* calc res2 = (order - x) * point + (order - x) * G; */
1084     secp256k1_gej_add_var(&res1, &res1, &res2);
1085     CHECK(secp256k1_gej_is_infinity(&res1));
1086     CHECK(secp256k1_gej_is_valid_var(&res1) == 0);
1087     secp256k1_ge_set_gej(&res3, &res1);
1088     CHECK(secp256k1_ge_is_infinity(&res3));
1089     CHECK(secp256k1_ge_is_valid_var(&res3) == 0);
1090     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 0) == 0);
1091     psize = 65;
1092     CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
1093 }
1094
1095 void run_point_times_order(void) {
1096     int i;
1097     char c[64];
1098     secp256k1_fe_t x; VERIFY_CHECK(secp256k1_fe_set_hex(&x, "0000000000000000000000000000000000000000000000000000000000000002"));
1099     for (i = 0; i < 500; i++) {
1100         secp256k1_ge_t p;
1101         if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
1102             secp256k1_gej_t j;
1103             CHECK(secp256k1_ge_is_valid_var(&p));
1104             secp256k1_gej_set_ge(&j, &p);
1105             CHECK(secp256k1_gej_is_valid_var(&j));
1106             test_point_times_order(&j);
1107         }
1108         secp256k1_fe_sqr(&x, &x);
1109     }
1110     secp256k1_fe_get_hex(c, &x);
1111     CHECK(memcmp(c, "7603CB59B0EF6C63FE6084792A0C378CDB3233A80F8A9A09A877DEAD31B38C45", 64) == 0);
1112 }
1113
1114 void test_wnaf(const secp256k1_scalar_t *number, int w) {
1115     secp256k1_scalar_t x, two, t;
1116     int wnaf[256];
1117     int zeroes = -1;
1118     int i;
1119     int bits;
1120     secp256k1_scalar_set_int(&x, 0);
1121     secp256k1_scalar_set_int(&two, 2);
1122     bits = secp256k1_ecmult_wnaf(wnaf, number, w);
1123     CHECK(bits <= 256);
1124     for (i = bits-1; i >= 0; i--) {
1125         int v = wnaf[i];
1126         secp256k1_scalar_mul(&x, &x, &two);
1127         if (v) {
1128             CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
1129             zeroes=0;
1130             CHECK((v & 1) == 1); /* check non-zero elements are odd */
1131             CHECK(v <= (1 << (w-1)) - 1); /* check range below */
1132             CHECK(v >= -(1 << (w-1)) - 1); /* check range above */
1133         } else {
1134             CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
1135             zeroes++;
1136         }
1137         if (v >= 0) {
1138             secp256k1_scalar_set_int(&t, v);
1139         } else {
1140             secp256k1_scalar_set_int(&t, -v);
1141             secp256k1_scalar_negate(&t, &t);
1142         }
1143         secp256k1_scalar_add(&x, &x, &t);
1144     }
1145     CHECK(secp256k1_scalar_eq(&x, number)); /* check that wnaf represents number */
1146 }
1147
1148 void run_wnaf(void) {
1149     int i;
1150     secp256k1_scalar_t n;
1151     for (i = 0; i < count; i++) {
1152         random_scalar_order(&n);
1153         if (i % 1)
1154             secp256k1_scalar_negate(&n, &n);
1155         test_wnaf(&n, 4+(i%10));
1156     }
1157 }
1158
1159 void random_sign(secp256k1_ecdsa_sig_t *sig, const secp256k1_scalar_t *key, const secp256k1_scalar_t *msg, int *recid) {
1160     secp256k1_scalar_t nonce;
1161     do {
1162         random_scalar_order_test(&nonce);
1163     } while(!secp256k1_ecdsa_sig_sign(sig, key, msg, &nonce, recid));
1164 }
1165
1166 void test_ecdsa_sign_verify(void) {
1167     secp256k1_gej_t pubj;
1168     secp256k1_ge_t pub;
1169     secp256k1_scalar_t one;
1170     secp256k1_scalar_t msg, key;
1171     secp256k1_ecdsa_sig_t sig;
1172     int recid;
1173     int getrec;
1174     random_scalar_order_test(&msg);
1175     random_scalar_order_test(&key);
1176     secp256k1_ecmult_gen(&pubj, &key);
1177     secp256k1_ge_set_gej(&pub, &pubj);
1178     getrec = secp256k1_rand32()&1;
1179     random_sign(&sig, &key, &msg, getrec?&recid:NULL);
1180     if (getrec) CHECK(recid >= 0 && recid < 4);
1181     CHECK(secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
1182     secp256k1_scalar_set_int(&one, 1);
1183     secp256k1_scalar_add(&msg, &msg, &one);
1184     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &pub, &msg));
1185 }
1186
1187 void run_ecdsa_sign_verify(void) {
1188     int i;
1189     for (i = 0; i < 10*count; i++) {
1190         test_ecdsa_sign_verify();
1191     }
1192 }
1193
1194 /** Dummy nonce generation function that just uses a precomputed nonce, and fails if it is not accepted. Use only for testing. */
1195 static int precomputed_nonce_function(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
1196     (void)msg32;
1197     (void)key32;
1198     memcpy(nonce32, data, 32);
1199     return (counter == 0);
1200 }
1201
1202 static int nonce_function_test_fail(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
1203    /* Dummy nonce generator that has a fatal error on the first counter value. */
1204    if (counter == 0) return 0;
1205    return nonce_function_rfc6979(nonce32, msg32, key32, counter - 1, data);
1206 }
1207
1208 static int nonce_function_test_retry(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, unsigned int counter, const void *data) {
1209    /* Dummy nonce generator that produces unacceptable nonces for the first several counter values. */
1210    if (counter < 3) {
1211        memset(nonce32, counter==0 ? 0 : 255, 32);
1212        if (counter == 2) nonce32[31]--;
1213        return 1;
1214    }
1215    if (counter < 5) {
1216        static const unsigned char order[] = {
1217            0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1218            0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
1219            0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
1220            0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x41
1221        };
1222        memcpy(nonce32, order, 32);
1223        if (counter == 4) nonce32[31]++;
1224        return 1;
1225    }
1226    /* Retry rate of 6979 is negligible esp. as we only call this in determinstic tests. */
1227    /* If someone does fine a case where it retries for secp256k1, we'd like to know. */
1228    if (counter > 5) return 0;
1229    return nonce_function_rfc6979(nonce32, msg32, key32, counter - 5, data);
1230 }
1231
1232 int is_empty_compact_signature(const unsigned char *sig64) {
1233     static const unsigned char res[64] = {0};
1234     return memcmp(sig64, res, 64) == 0;
1235 }
1236
1237 void test_ecdsa_end_to_end(void) {
1238     unsigned char privkey[32];
1239     unsigned char message[32];
1240     unsigned char privkey2[32];
1241     unsigned char csignature[64];
1242     unsigned char signature[72];
1243     unsigned char pubkey[65];
1244     unsigned char recpubkey[65];
1245     unsigned char seckey[300];
1246     int signaturelen = 72;
1247     int recid = 0;
1248     int recpubkeylen = 0;
1249     int pubkeylen = 65;
1250     int seckeylen = 300;
1251
1252     /* Generate a random key and message. */
1253     {
1254         secp256k1_scalar_t msg, key;
1255         random_scalar_order_test(&msg);
1256         random_scalar_order_test(&key);
1257         secp256k1_scalar_get_b32(privkey, &key);
1258         secp256k1_scalar_get_b32(message, &msg);
1259     }
1260
1261     /* Construct and verify corresponding public key. */
1262     CHECK(secp256k1_ec_seckey_verify(privkey) == 1);
1263     CHECK(secp256k1_ec_pubkey_create(pubkey, &pubkeylen, privkey, (secp256k1_rand32() & 3) != 0) == 1);
1264     if (secp256k1_rand32() & 1) {
1265         CHECK(secp256k1_ec_pubkey_decompress(pubkey, &pubkeylen));
1266     }
1267     CHECK(secp256k1_ec_pubkey_verify(pubkey, pubkeylen));
1268
1269     /* Verify private key import and export. */
1270     CHECK(secp256k1_ec_privkey_export(privkey, seckey, &seckeylen, secp256k1_rand32() % 2) == 1);
1271     CHECK(secp256k1_ec_privkey_import(privkey2, seckey, seckeylen) == 1);
1272     CHECK(memcmp(privkey, privkey2, 32) == 0);
1273
1274     /* Optionally tweak the keys using addition. */
1275     if (secp256k1_rand32() % 3 == 0) {
1276         int ret1;
1277         int ret2;
1278         unsigned char rnd[32];
1279         unsigned char pubkey2[65];
1280         int pubkeylen2 = 65;
1281         secp256k1_rand256_test(rnd);
1282         ret1 = secp256k1_ec_privkey_tweak_add(privkey, rnd);
1283         ret2 = secp256k1_ec_pubkey_tweak_add(pubkey, pubkeylen, rnd);
1284         CHECK(ret1 == ret2);
1285         if (ret1 == 0) return;
1286         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
1287         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
1288     }
1289
1290     /* Optionally tweak the keys using multiplication. */
1291     if (secp256k1_rand32() % 3 == 0) {
1292         int ret1;
1293         int ret2;
1294         unsigned char rnd[32];
1295         unsigned char pubkey2[65];
1296         int pubkeylen2 = 65;
1297         secp256k1_rand256_test(rnd);
1298         ret1 = secp256k1_ec_privkey_tweak_mul(privkey, rnd);
1299         ret2 = secp256k1_ec_pubkey_tweak_mul(pubkey, pubkeylen, rnd);
1300         CHECK(ret1 == ret2);
1301         if (ret1 == 0) return;
1302         CHECK(secp256k1_ec_pubkey_create(pubkey2, &pubkeylen2, privkey, pubkeylen == 33) == 1);
1303         CHECK(memcmp(pubkey, pubkey2, pubkeylen) == 0);
1304     }
1305
1306     /* Sign. */
1307     CHECK(secp256k1_ecdsa_sign(message, signature, &signaturelen, privkey, NULL, NULL) == 1);
1308     CHECK(signaturelen > 0);
1309     /* Verify. */
1310     CHECK(secp256k1_ecdsa_verify(message, signature, signaturelen, pubkey, pubkeylen) == 1);
1311     /* Destroy signature and verify again. */
1312     signature[signaturelen - 1 - secp256k1_rand32() % 20] += 1 + (secp256k1_rand32() % 255);
1313     CHECK(secp256k1_ecdsa_verify(message, signature, signaturelen, pubkey, pubkeylen) != 1);
1314
1315     /* Compact sign. */
1316     CHECK(secp256k1_ecdsa_sign_compact(message, csignature, privkey, NULL, NULL, &recid) == 1);
1317     CHECK(!is_empty_compact_signature(csignature));
1318     /* Recover. */
1319     CHECK(secp256k1_ecdsa_recover_compact(message, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) == 1);
1320     CHECK(recpubkeylen == pubkeylen);
1321     CHECK(memcmp(pubkey, recpubkey, pubkeylen) == 0);
1322     /* Destroy signature and verify again. */
1323     csignature[secp256k1_rand32() % 64] += 1 + (secp256k1_rand32() % 255);
1324     CHECK(secp256k1_ecdsa_recover_compact(message, csignature, recpubkey, &recpubkeylen, pubkeylen == 33, recid) != 1 ||
1325           memcmp(pubkey, recpubkey, pubkeylen) != 0);
1326     CHECK(recpubkeylen == pubkeylen);
1327
1328 }
1329
1330 void test_random_pubkeys(void) {
1331     secp256k1_ge_t elem;
1332     secp256k1_ge_t elem2;
1333     unsigned char in[65];
1334     /* Generate some randomly sized pubkeys. */
1335     uint32_t r = secp256k1_rand32();
1336     int len = (r & 3) == 0 ? 65 : 33;
1337     r>>=2;
1338     if ((r & 3) == 0) len = (r & 252) >> 3;
1339     r>>=8;
1340     if (len == 65) {
1341       in[0] = (r & 2) ? 4 : (r & 1? 6 : 7);
1342     } else {
1343       in[0] = (r & 1) ? 2 : 3;
1344     }
1345     r>>=2;
1346     if ((r & 7) == 0) in[0] = (r & 2040) >> 3;
1347     r>>=11;
1348     if (len > 1) secp256k1_rand256(&in[1]);
1349     if (len > 33) secp256k1_rand256(&in[33]);
1350     if (secp256k1_eckey_pubkey_parse(&elem, in, len)) {
1351         unsigned char out[65];
1352         unsigned char firstb;
1353         int res;
1354         int size = len;
1355         firstb = in[0];
1356         /* If the pubkey can be parsed, it should round-trip... */
1357         CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
1358         CHECK(size == len);
1359         CHECK(memcmp(&in[1], &out[1], len-1) == 0);
1360         /* ... except for the type of hybrid inputs. */
1361         if ((in[0] != 6) && (in[0] != 7)) CHECK(in[0] == out[0]);
1362         size = 65;
1363         CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
1364         CHECK(size == 65);
1365         CHECK(secp256k1_eckey_pubkey_parse(&elem2, in, size));
1366         ge_equals_ge(&elem,&elem2);
1367         /* Check that the X9.62 hybrid type is checked. */
1368         in[0] = (r & 1) ? 6 : 7;
1369         res = secp256k1_eckey_pubkey_parse(&elem2, in, size);
1370         if (firstb == 2 || firstb == 3) {
1371             if (in[0] == firstb + 4) CHECK(res);
1372             else CHECK(!res);
1373         }
1374         if (res) {
1375             ge_equals_ge(&elem,&elem2);
1376             CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, 0));
1377             CHECK(memcmp(&in[1], &out[1], 64) == 0);
1378         }
1379     }
1380 }
1381
1382 void run_random_pubkeys(void) {
1383     int i;
1384     for (i = 0; i < 10*count; i++) {
1385         test_random_pubkeys();
1386     }
1387 }
1388
1389 void run_ecdsa_end_to_end(void) {
1390     int i;
1391     for (i = 0; i < 64*count; i++) {
1392         test_ecdsa_end_to_end();
1393     }
1394 }
1395
1396 /* Tests several edge cases. */
1397 void test_ecdsa_edge_cases(void) {
1398     const unsigned char msg32[32] = {
1399         'T', 'h', 'i', 's', ' ', 'i', 's', ' ',
1400         'a', ' ', 'v', 'e', 'r', 'y', ' ', 's',
1401         'e', 'c', 'r', 'e', 't', ' ', 'm', 'e',
1402         's', 's', 'a', 'g', 'e', '.', '.', '.'
1403     };
1404     const unsigned char sig64[64] = {
1405         /* Generated by signing the above message with nonce 'This is the nonce we will use...'
1406          * and secret key 0 (which is not valid), resulting in recid 0. */
1407         0x67, 0xCB, 0x28, 0x5F, 0x9C, 0xD1, 0x94, 0xE8,
1408         0x40, 0xD6, 0x29, 0x39, 0x7A, 0xF5, 0x56, 0x96,
1409         0x62, 0xFD, 0xE4, 0x46, 0x49, 0x99, 0x59, 0x63,
1410         0x17, 0x9A, 0x7D, 0xD1, 0x7B, 0xD2, 0x35, 0x32,
1411         0x4B, 0x1B, 0x7D, 0xF3, 0x4C, 0xE1, 0xF6, 0x8E,
1412         0x69, 0x4F, 0xF6, 0xF1, 0x1A, 0xC7, 0x51, 0xDD,
1413         0x7D, 0xD7, 0x3E, 0x38, 0x7E, 0xE4, 0xFC, 0x86,
1414         0x6E, 0x1B, 0xE8, 0xEC, 0xC7, 0xDD, 0x95, 0x57
1415     };
1416     unsigned char pubkey[65];
1417     int pubkeylen = 65;
1418     /* signature (r,s) = (4,4), which can be recovered with all 4 recids. */
1419     const unsigned char sigb64[64] = {
1420         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1421         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1422         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1423         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1424         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1425         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1426         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1427         0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1428     };
1429     unsigned char pubkeyb[33];
1430     int pubkeyblen = 33;
1431     int recid;
1432
1433     CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 0));
1434     CHECK(secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 1));
1435     CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 2));
1436     CHECK(!secp256k1_ecdsa_recover_compact(msg32, sig64, pubkey, &pubkeylen, 0, 3));
1437
1438     for (recid = 0; recid < 4; recid++) {
1439         int i;
1440         int recid2;
1441         /* (4,4) encoded in DER. */
1442         unsigned char sigbder[8] = {0x30, 0x06, 0x02, 0x01, 0x04, 0x02, 0x01, 0x04};
1443         unsigned char sigcder_zr[7] = {0x30, 0x05, 0x02, 0x00, 0x02, 0x01, 0x01};
1444         unsigned char sigcder_zs[7] = {0x30, 0x05, 0x02, 0x01, 0x01, 0x02, 0x00};
1445         unsigned char sigbderalt1[39] = {
1446             0x30, 0x25, 0x02, 0x20, 0x00, 0x00, 0x00, 0x00,
1447             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1448             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1449             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1450             0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
1451         };
1452         unsigned char sigbderalt2[39] = {
1453             0x30, 0x25, 0x02, 0x01, 0x04, 0x02, 0x20, 0x00,
1454             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1455             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1456             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1457             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1458         };
1459         unsigned char sigbderalt3[40] = {
1460             0x30, 0x26, 0x02, 0x21, 0x00, 0x00, 0x00, 0x00,
1461             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1462             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1463             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1464             0x00, 0x00, 0x00, 0x00, 0x04, 0x02, 0x01, 0x04,
1465         };
1466         unsigned char sigbderalt4[40] = {
1467             0x30, 0x26, 0x02, 0x01, 0x04, 0x02, 0x21, 0x00,
1468             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1469             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1470             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1471             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04,
1472         };
1473         /* (order + r,4) encoded in DER. */
1474         unsigned char sigbderlong[40] = {
1475             0x30, 0x26, 0x02, 0x21, 0x00, 0xFF, 0xFF, 0xFF,
1476             0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
1477             0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xBA, 0xAE, 0xDC,
1478             0xE6, 0xAF, 0x48, 0xA0, 0x3B, 0xBF, 0xD2, 0x5E,
1479             0x8C, 0xD0, 0x36, 0x41, 0x45, 0x02, 0x01, 0x04
1480         };
1481         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigb64, pubkeyb, &pubkeyblen, 1, recid));
1482         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 1);
1483         for (recid2 = 0; recid2 < 4; recid2++) {
1484             unsigned char pubkey2b[33];
1485             int pubkey2blen = 33;
1486             CHECK(secp256k1_ecdsa_recover_compact(msg32, sigb64, pubkey2b, &pubkey2blen, 1, recid2));
1487             /* Verifying with (order + r,4) should always fail. */
1488             CHECK(secp256k1_ecdsa_verify(msg32, sigbderlong, sizeof(sigbderlong), pubkey2b, pubkey2blen) != 1);
1489         }
1490         /* DER parsing tests. */
1491         /* Zero length r/s. */
1492         CHECK(secp256k1_ecdsa_verify(msg32, sigcder_zr, sizeof(sigcder_zr), pubkeyb, pubkeyblen) == -2);
1493         CHECK(secp256k1_ecdsa_verify(msg32, sigcder_zs, sizeof(sigcder_zs), pubkeyb, pubkeyblen) == -2);
1494         /* Leading zeros. */
1495         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt1, sizeof(sigbderalt1), pubkeyb, pubkeyblen) == 1);
1496         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt2, sizeof(sigbderalt2), pubkeyb, pubkeyblen) == 1);
1497         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == 1);
1498         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == 1);
1499         sigbderalt3[4] = 1;
1500         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == -2);
1501         sigbderalt4[7] = 1;
1502         CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == -2);
1503         /* Damage signature. */
1504         sigbder[7]++;
1505         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 0);
1506         sigbder[7]--;
1507         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, 6, pubkeyb, pubkeyblen) == -2);
1508         CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder)-1, pubkeyb, pubkeyblen) == -2);
1509         for(i = 0; i < 8; i++) {
1510             int c;
1511             unsigned char orig = sigbder[i];
1512             /*Try every single-byte change.*/
1513             for (c = 0; c < 256; c++) {
1514                 if (c == orig ) continue;
1515                 sigbder[i] = c;
1516                 CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) ==
1517                   (i==4 || i==7) ? 0 : -2 );
1518             }
1519             sigbder[i] = orig;
1520         }
1521     }
1522
1523     /* Test the case where ECDSA recomputes a point that is infinity. */
1524     {
1525         secp256k1_gej_t keyj;
1526         secp256k1_ge_t key;
1527         secp256k1_scalar_t msg;
1528         secp256k1_ecdsa_sig_t sig;
1529         secp256k1_scalar_set_int(&sig.s, 1);
1530         secp256k1_scalar_negate(&sig.s, &sig.s);
1531         secp256k1_scalar_inverse(&sig.s, &sig.s);
1532         secp256k1_scalar_set_int(&sig.r, 1);
1533         secp256k1_ecmult_gen(&keyj, &sig.r);
1534         secp256k1_ge_set_gej(&key, &keyj);
1535         msg = sig.s;
1536         CHECK(secp256k1_ecdsa_sig_verify(&sig, &key, &msg) == 0);
1537     }
1538
1539     /* Test r/s equal to zero */
1540     {
1541         /* (1,1) encoded in DER. */
1542         unsigned char sigcder[8] = {0x30, 0x06, 0x02, 0x01, 0x01, 0x02, 0x01, 0x01};
1543         unsigned char sigc64[64] = {
1544             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1545             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1546             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1547             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1548             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1549             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1550             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1551             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1552         };
1553         unsigned char pubkeyc[65];
1554         int pubkeyclen = 65;
1555         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyc, &pubkeyclen, 0, 0) == 1);
1556         CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 1);
1557         sigcder[4] = 0;
1558         sigc64[31] = 0;
1559         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
1560         CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
1561         sigcder[4] = 1;
1562         sigcder[7] = 0;
1563         sigc64[31] = 1;
1564         sigc64[63] = 0;
1565         CHECK(secp256k1_ecdsa_recover_compact(msg32, sigc64, pubkeyb, &pubkeyblen, 1, 0) == 0);
1566         CHECK(secp256k1_ecdsa_verify(msg32, sigcder, sizeof(sigcder), pubkeyc, pubkeyclen) == 0);
1567     }
1568
1569     /*Signature where s would be zero.*/
1570     {
1571         const unsigned char nonce[32] = {
1572             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1573             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1574             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1575             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1576         };
1577         static const unsigned char nonce2[32] = {
1578             0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
1579             0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFE,
1580             0xBA,0xAE,0xDC,0xE6,0xAF,0x48,0xA0,0x3B,
1581             0xBF,0xD2,0x5E,0x8C,0xD0,0x36,0x41,0x40
1582         };
1583         const unsigned char key[32] = {
1584             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1585             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1586             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1587             0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01,
1588         };
1589         unsigned char msg[32] = {
1590             0x86, 0x41, 0x99, 0x81, 0x06, 0x23, 0x44, 0x53,
1591             0xaa, 0x5f, 0x9d, 0x6a, 0x31, 0x78, 0xf4, 0xf7,
1592             0xb8, 0x12, 0xe0, 0x0b, 0x81, 0x7a, 0x77, 0x62,
1593             0x65, 0xdf, 0xdd, 0x31, 0xb9, 0x3e, 0x29, 0xa9,
1594         };
1595         unsigned char sig[72];
1596         int siglen = 72;
1597         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 0);
1598         CHECK(siglen == 0);
1599         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 0);
1600         CHECK(siglen == 0);
1601         msg[31] = 0xaa;
1602         siglen = 72;
1603         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 1);
1604         CHECK(siglen > 0);
1605         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 1);
1606         CHECK(siglen > 0);
1607         siglen = 10;
1608         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) != 1);
1609         CHECK(siglen == 0);
1610     }
1611
1612     /* Nonce function corner cases. */
1613     {
1614         int i;
1615         unsigned char key[32];
1616         unsigned char msg[32];
1617         unsigned char sig[72];
1618         unsigned char sig2[72];
1619         secp256k1_ecdsa_sig_t s[512];
1620         int siglen = 72;
1621         int siglen2 = 72;
1622         int recid2;
1623         memset(msg, 0, 32);
1624         msg[31] = 1;
1625         /* High key results in signature failure. */
1626         memset(key, 0xFF, 32);
1627         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, NULL) == 0);
1628         CHECK(siglen == 0);
1629         /* Zero key results in signature failure. */
1630         memset(key, 0, 32);
1631         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, NULL) == 0);
1632         CHECK(siglen == 0);
1633         /* Nonce function failure results in signature failure. */
1634         key[31] = 1;
1635         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_fail, NULL) == 0);
1636         CHECK(siglen == 0);
1637         CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, nonce_function_test_fail, NULL, &recid) == 0);
1638         CHECK(is_empty_compact_signature(sig));
1639         /* The retry loop successfully makes its way to the first good value. */
1640         siglen = 72;
1641         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_retry, NULL) == 1);
1642         CHECK(siglen > 0);
1643         CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, nonce_function_rfc6979, NULL) == 1);
1644         CHECK(siglen > 0);
1645         CHECK((siglen == siglen2) && (memcmp(sig, sig2, siglen) == 0));
1646         CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, nonce_function_test_retry, NULL, &recid) == 1);
1647         CHECK(!is_empty_compact_signature(sig));
1648         CHECK(secp256k1_ecdsa_sign_compact(msg, sig2, key, nonce_function_rfc6979, NULL, &recid2) == 1);
1649         CHECK(!is_empty_compact_signature(sig2));
1650         CHECK((recid == recid2) && (memcmp(sig, sig2, 64) == 0));
1651         /* The default nonce function is determinstic. */
1652         siglen = 72;
1653         siglen2 = 72;
1654         CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, NULL) == 1);
1655         CHECK(siglen > 0);
1656         CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, NULL) == 1);
1657         CHECK(siglen2 > 0);
1658         CHECK((siglen == siglen2) && (memcmp(sig, sig2, siglen) == 0));
1659         CHECK(secp256k1_ecdsa_sign_compact(msg, sig, key, NULL, NULL, &recid) == 1);
1660         CHECK(!is_empty_compact_signature(sig));
1661         CHECK(secp256k1_ecdsa_sign_compact(msg, sig2, key, NULL, NULL, &recid2) == 1);
1662         CHECK(!is_empty_compact_signature(sig));
1663         CHECK((recid == recid2) && (memcmp(sig, sig2, 64) == 0));
1664         /* The default nonce function changes output with different messages. */
1665         for(i = 0; i < 256; i++) {
1666             int j;
1667             siglen2 = 72;
1668             msg[0] = i;
1669             CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, NULL) == 1);
1670             CHECK(!is_empty_compact_signature(sig));
1671             CHECK(secp256k1_ecdsa_sig_parse(&s[i], sig2, siglen2));
1672             for (j = 0; j < i; j++) {
1673                 CHECK(!secp256k1_scalar_eq(&s[i].r, &s[j].r));
1674             }
1675         }
1676         msg[0] = 0;
1677         msg[31] = 2;
1678         /* The default nonce function changes output with different keys. */
1679         for(i = 256; i < 512; i++) {
1680             int j;
1681             siglen2 = 72;
1682             key[0] = i - 256;
1683             CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, NULL) == 1);
1684             CHECK(secp256k1_ecdsa_sig_parse(&s[i], sig2, siglen2));
1685             for (j = 0; j < i; j++) {
1686                 CHECK(!secp256k1_scalar_eq(&s[i].r, &s[j].r));
1687             }
1688         }
1689         key[0] = 0;
1690     }
1691
1692     /* Privkey export where pubkey is the point at infinity. */
1693     {
1694         unsigned char privkey[300];
1695         unsigned char seckey[32] = {
1696             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
1697             0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xfe,
1698             0xba, 0xae, 0xdc, 0xe6, 0xaf, 0x48, 0xa0, 0x3b,
1699             0xbf, 0xd2, 0x5e, 0x8c, 0xd0, 0x36, 0x41, 0x41,
1700         };
1701         int outlen = 300;
1702         CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 0));
1703         CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 1));
1704     }
1705 }
1706
1707 void run_ecdsa_edge_cases(void) {
1708     test_ecdsa_edge_cases();
1709 }
1710
1711 #ifdef ENABLE_OPENSSL_TESTS
1712 EC_KEY *get_openssl_key(const secp256k1_scalar_t *key) {
1713     unsigned char privkey[300];
1714     int privkeylen;
1715     const unsigned char* pbegin = privkey;
1716     int compr = secp256k1_rand32() & 1;
1717     EC_KEY *ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
1718     CHECK(secp256k1_eckey_privkey_serialize(privkey, &privkeylen, key, compr));
1719     CHECK(d2i_ECPrivateKey(&ec_key, &pbegin, privkeylen));
1720     CHECK(EC_KEY_check_key(ec_key));
1721     return ec_key;
1722 }
1723
1724 void test_ecdsa_openssl(void) {
1725     secp256k1_gej_t qj;
1726     secp256k1_ge_t q;
1727     secp256k1_ecdsa_sig_t sig;
1728     secp256k1_scalar_t one;
1729     secp256k1_scalar_t msg2;
1730     secp256k1_scalar_t key, msg;
1731     EC_KEY *ec_key;
1732     unsigned int sigsize = 80;
1733     int secp_sigsize = 80;
1734     unsigned char message[32];
1735     unsigned char signature[80];
1736     secp256k1_rand256_test(message);
1737     secp256k1_scalar_set_b32(&msg, message, NULL);
1738     random_scalar_order_test(&key);
1739     secp256k1_ecmult_gen(&qj, &key);
1740     secp256k1_ge_set_gej(&q, &qj);
1741     ec_key = get_openssl_key(&key);
1742     CHECK(ec_key);
1743     CHECK(ECDSA_sign(0, message, sizeof(message), signature, &sigsize, ec_key));
1744     CHECK(secp256k1_ecdsa_sig_parse(&sig, signature, sigsize));
1745     CHECK(secp256k1_ecdsa_sig_verify(&sig, &q, &msg));
1746     secp256k1_scalar_set_int(&one, 1);
1747     secp256k1_scalar_add(&msg2, &msg, &one);
1748     CHECK(!secp256k1_ecdsa_sig_verify(&sig, &q, &msg2));
1749
1750     random_sign(&sig, &key, &msg, NULL);
1751     CHECK(secp256k1_ecdsa_sig_serialize(signature, &secp_sigsize, &sig));
1752     CHECK(ECDSA_verify(0, message, sizeof(message), signature, secp_sigsize, ec_key) == 1);
1753
1754     EC_KEY_free(ec_key);
1755 }
1756
1757 void run_ecdsa_openssl(void) {
1758     int i;
1759     for (i = 0; i < 10*count; i++) {
1760         test_ecdsa_openssl();
1761     }
1762 }
1763 #endif
1764
1765 int main(int argc, char **argv) {
1766     uint64_t seed;
1767     /* find iteration count */
1768     if (argc > 1) {
1769         count = strtol(argv[1], NULL, 0);
1770     }
1771
1772     /* find random seed */
1773     if (argc > 2) {
1774         sscanf(argv[2], "%" I64uFORMAT, (unsigned long long*)&seed);
1775     } else {
1776         FILE *frand = fopen("/dev/urandom", "r");
1777         if (!frand || !fread(&seed, sizeof(seed), 1, frand)) {
1778             seed = time(NULL) * 1337;
1779         }
1780         fclose(frand);
1781     }
1782     secp256k1_rand_seed(seed);
1783
1784     printf("test count = %i\n", count);
1785     printf("random seed = %" I64uFORMAT "\n", (unsigned long long)seed);
1786
1787     /* initialize */
1788     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1789
1790     /* initializing a second time shouldn't cause any harm or memory leaks. */
1791     secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1792
1793     run_sha256_tests();
1794     run_hmac_sha256_tests();
1795     run_rfc6979_hmac_sha256_tests();
1796
1797 #ifndef USE_NUM_NONE
1798     /* num tests */
1799     run_num_smalltests();
1800 #endif
1801
1802     /* scalar tests */
1803     run_scalar_tests();
1804
1805     /* field tests */
1806     run_field_inv();
1807     run_field_inv_var();
1808     run_field_inv_all_var();
1809     run_field_misc();
1810     run_field_convert();
1811     run_sqr();
1812     run_sqrt();
1813
1814     /* group tests */
1815     run_ge();
1816
1817     /* ecmult tests */
1818     run_wnaf();
1819     run_point_times_order();
1820     run_ecmult_chain();
1821
1822     /* ecdsa tests */
1823     run_random_pubkeys();
1824     run_ecdsa_sign_verify();
1825     run_ecdsa_end_to_end();
1826     run_ecdsa_edge_cases();
1827 #ifdef ENABLE_OPENSSL_TESTS
1828     run_ecdsa_openssl();
1829 #endif
1830
1831     printf("random run = %llu\n", (unsigned long long)secp256k1_rand32() + ((unsigned long long)secp256k1_rand32() << 32));
1832
1833     /* shutdown */
1834     secp256k1_stop();
1835
1836     /* shutting down twice shouldn't cause any double frees. */
1837     secp256k1_stop();
1838     return 0;
1839 }
This page took 0.121346 seconds and 4 git commands to generate.