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 **********************************************************************/
7 #if defined HAVE_CONFIG_H
8 #include "libsecp256k1-config.h"
16 #include "secp256k1.c"
17 #include "testrand_impl.h"
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"
26 static int count = 64;
28 void random_field_element_test(secp256k1_fe_t *fe) {
30 unsigned char b32[32];
31 secp256k1_rand256_test(b32);
32 if (secp256k1_fe_set_b32(fe, b32)) {
38 void random_field_element_magnitude(secp256k1_fe_t *fe) {
40 int n = secp256k1_rand32() % 9;
41 secp256k1_fe_normalize(fe);
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);
50 CHECK(fe->magnitude == n);
54 void random_group_element_test(secp256k1_ge_t *ge) {
57 random_field_element_test(&fe);
58 if (secp256k1_ge_set_xo_var(ge, &fe, secp256k1_rand32() & 1))
63 void random_group_element_jacobian_test(secp256k1_gej_t *gej, const secp256k1_ge_t *ge) {
64 secp256k1_fe_t z2, z3;
66 random_field_element_test(&gej->z);
67 if (!secp256k1_fe_is_zero(&gej->z)) {
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;
78 void random_scalar_order_test(secp256k1_scalar_t *num) {
80 unsigned char b32[32];
82 secp256k1_rand256_test(b32);
83 secp256k1_scalar_set_b32(num, b32, &overflow);
84 if (overflow || secp256k1_scalar_is_zero(num))
90 void random_scalar_order(secp256k1_scalar_t *num) {
92 unsigned char b32[32];
94 secp256k1_rand256(b32);
95 secp256k1_scalar_set_b32(num, b32, &overflow);
96 if (overflow || secp256k1_scalar_is_zero(num))
102 /***** HASH TESTS *****/
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"
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}
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);
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",
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"
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"
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}
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);
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}
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}
201 secp256k1_rfc6979_hmac_sha256_t rng;
202 unsigned char out[32];
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);
210 secp256k1_rfc6979_hmac_sha256_finalize(&rng);
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);
217 secp256k1_rfc6979_hmac_sha256_finalize(&rng);
220 /***** NUM TESTS *****/
223 void random_num_negate(secp256k1_num_t *num) {
224 if (secp256k1_rand32() & 1)
225 secp256k1_num_negate(num);
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);
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);
240 void test_num_negate(void) {
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));
260 void test_num_add_sub(void) {
263 secp256k1_num_t n1p2, n2p1, n1m2, n2m1;
264 int r = secp256k1_rand32();
265 random_num_order_test(&n1); /* n1 = R1 */
267 random_num_negate(&n1);
269 random_num_order_test(&n2); /* n2 = R2 */
271 random_num_negate(&n2);
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));
289 void run_num_smalltests(void) {
291 for (i = 0; i < 100*count; i++) {
298 /***** SCALAR TESTS *****/
300 void scalar_test(void) {
301 secp256k1_scalar_t s;
302 secp256k1_scalar_t s1;
303 secp256k1_scalar_t s2;
305 secp256k1_num_t snum, s1num, s2num;
306 secp256k1_num_t order, half_order;
310 /* Set 's' to a random scalar, with value 'snum'. */
311 random_scalar_order_test(&s);
313 /* Set 's1' to a random scalar, with value 's1num'. */
314 random_scalar_order_test(&s1);
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);
321 secp256k1_scalar_get_num(&snum, &s);
322 secp256k1_scalar_get_num(&s1num, &s1);
323 secp256k1_scalar_get_num(&s2num, &s2);
325 secp256k1_scalar_order_get_num(&order);
327 secp256k1_num_shift(&half_order, 1);
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;
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);
342 secp256k1_scalar_add(&n, &n, &t);
344 CHECK(secp256k1_scalar_eq(&n, &s));
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;
351 secp256k1_scalar_set_int(&n, 0);
353 secp256k1_scalar_t t;
355 int now = (secp256k1_rand32() % 15) + 1;
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);
363 secp256k1_scalar_add(&n, &n, &t);
366 CHECK(secp256k1_scalar_eq(&n, &s));
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));
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)));
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));
426 /* Test secp256k1_scalar_mul_shift_var. */
427 secp256k1_scalar_t r;
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));
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;
449 secp256k1_num_t invnum;
450 secp256k1_num_t invnum2;
452 secp256k1_scalar_inverse(&inv, &s);
454 secp256k1_num_mod_inverse(&invnum, &snum, &order);
455 secp256k1_scalar_get_num(&invnum2, &inv);
456 CHECK(secp256k1_num_eq(&invnum, &invnum2));
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));
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));
476 secp256k1_scalar_t r1, r2;
477 secp256k1_scalar_t b;
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);
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));
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));
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));
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));
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));
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));
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));
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));
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));
568 void run_scalar_tests(void) {
570 for (i = 0; i < 128 * count; i++) {
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));
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];
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));
602 /***** FIELD TESTS *****/
604 void random_fe(secp256k1_fe_t *x) {
605 unsigned char bin[32];
607 secp256k1_rand256(bin);
608 if (secp256k1_fe_set_b32(x, bin)) {
614 void random_fe_non_zero(secp256k1_fe_t *nz) {
616 while (--tries >= 0) {
618 secp256k1_fe_normalize(nz);
619 if (!secp256k1_fe_is_zero(nz))
622 /* Infinitesimal probability of spurious failure here */
626 void random_fe_non_square(secp256k1_fe_t *ns) {
628 random_fe_non_zero(ns);
629 if (secp256k1_fe_sqrt_var(&r, ns)) {
630 secp256k1_fe_negate(ns, ns, 1);
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);
642 int check_fe_inverse(const secp256k1_fe_t *a, const secp256k1_fe_t *ai) {
645 secp256k1_fe_mul(&x, a, ai);
646 secp256k1_fe_set_int(&one, 1);
647 return check_fe_equal(&x, &one);
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
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
662 static const secp256k1_fe_t fe = SECP256K1_FE_CONST(
663 0x00010203UL, 0x04050607UL, 0x11121314UL, 0x15161718UL,
664 0x22232425UL, 0x26272829UL, 0x33343536UL, 0x37383940UL
667 unsigned char b322[32];
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);
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,
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;
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));
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);
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));
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));
742 void run_field_inv(void) {
743 secp256k1_fe_t x, xi, xii;
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));
754 void run_field_inv_var(void) {
755 secp256k1_fe_t x, xi, xii;
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));
766 void run_field_inv_all_var(void) {
767 secp256k1_fe_t x[16], xi[16], xii[16];
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++) {
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]));
790 secp256k1_fe_set_int(&x, 1);
791 secp256k1_fe_negate(&x, &x, 1);
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);
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));
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));
815 void run_sqrt(void) {
816 secp256k1_fe_t ns, x, s, t;
819 /* Check sqrt(0) is 0 */
820 secp256k1_fe_set_int(&x, 0);
821 secp256k1_fe_sqr(&s, &x);
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);
829 secp256k1_fe_negate(&t, &s, 1);
833 /* Consistency checks for large random values */
834 for (i = 0; i < 10; i++) {
836 random_fe_non_square(&ns);
837 for (j = 0; j < count; j++) {
839 secp256k1_fe_sqr(&s, &x);
841 secp256k1_fe_negate(&t, &s, 1);
843 secp256k1_fe_mul(&t, &s, &ns);
849 /***** GROUP TESTS *****/
851 void ge_equals_ge(const secp256k1_ge_t *a, const secp256k1_ge_t *b) {
852 CHECK(a->infinity == b->infinity);
855 CHECK(secp256k1_fe_equal_var(&a->x, &b->x));
856 CHECK(secp256k1_fe_equal_var(&b->y, &b->y));
859 void ge_equals_gej(const secp256k1_ge_t *a, const secp256k1_gej_t *b) {
861 secp256k1_fe_t u1, u2, s1, s2;
862 CHECK(a->infinity == b->infinity);
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));
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.
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++) {
891 random_group_element_test(&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);
909 for (i1 = 0; i1 < 1 + 4 * runs; i1++) {
911 for (i2 = 0; i2 < 1 + 4 * runs; i2++) {
912 /* Compute reference result using gej + gej (var). */
913 secp256k1_gej_t refj, resj;
915 secp256k1_gej_add_var(&refj, &gej[i1], &gej[i2]);
916 secp256k1_ge_set_gej_var(&ref, &refj);
918 /* Test gej + ge (var). */
919 secp256k1_gej_add_ge_var(&resj, &gej[i1], &ge[i2]);
920 ge_equals_gej(&ref, &resj);
922 /* Test gej + ge (const). */
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);
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);
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));
943 /* Test adding infinity. */
945 CHECK(secp256k1_ge_is_infinity(&ge[i1]));
946 CHECK(secp256k1_gej_is_infinity(&gej[i1]));
947 ge_equals_gej(&ref, &gej[i2]);
950 CHECK(secp256k1_ge_is_infinity(&ge[i2]));
951 CHECK(secp256k1_gej_is_infinity(&gej[i2]));
952 ge_equals_gej(&ref, &gej[i1]);
957 /* Test adding all points together in random order equals infinity. */
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];
964 for (i = 0; i < 4 * runs + 1; i++) {
965 int swap = i + secp256k1_rand32() % (4 * runs + 1 - i);
967 secp256k1_gej_t t = gej_shuffled[i];
968 gej_shuffled[i] = gej_shuffled[swap];
969 gej_shuffled[swap] = t;
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]);
976 CHECK(secp256k1_gej_is_infinity(&sum));
980 /* Test batch gej -> ge conversion. */
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]);
996 for (i = 0; i < count * 32; i++) {
1001 /***** ECMULT TESTS *****/
1003 void run_ecmult_chain(void) {
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;
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
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
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};
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 */
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);
1061 secp256k1_gej_get_hex(res, &x);
1062 CHECK(memcmp(res, "(D6E96687F9B10D092A6F35439D86CEBEA4535D0D409F53586440BD74B933E830,B95CBCA2C77DA786539BE8FD53354D2D3B4F566AE658045407ED6015EE1B2A88)", 131) == 0);
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);
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];
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);
1092 CHECK(secp256k1_eckey_pubkey_serialize(&res3, pub, &psize, 1) == 0);
1095 void run_point_times_order(void) {
1098 secp256k1_fe_t x; VERIFY_CHECK(secp256k1_fe_set_hex(&x, "0000000000000000000000000000000000000000000000000000000000000002"));
1099 for (i = 0; i < 500; i++) {
1101 if (secp256k1_ge_set_xo_var(&p, &x, 1)) {
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);
1108 secp256k1_fe_sqr(&x, &x);
1110 secp256k1_fe_get_hex(c, &x);
1111 CHECK(memcmp(c, "7603CB59B0EF6C63FE6084792A0C378CDB3233A80F8A9A09A877DEAD31B38C45", 64) == 0);
1114 void test_wnaf(const secp256k1_scalar_t *number, int w) {
1115 secp256k1_scalar_t x, two, t;
1120 secp256k1_scalar_set_int(&x, 0);
1121 secp256k1_scalar_set_int(&two, 2);
1122 bits = secp256k1_ecmult_wnaf(wnaf, number, w);
1124 for (i = bits-1; i >= 0; i--) {
1126 secp256k1_scalar_mul(&x, &x, &two);
1128 CHECK(zeroes == -1 || zeroes >= w-1); /* check that distance between non-zero elements is at least w-1 */
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 */
1134 CHECK(zeroes != -1); /* check that no unnecessary zero padding exists */
1138 secp256k1_scalar_set_int(&t, v);
1140 secp256k1_scalar_set_int(&t, -v);
1141 secp256k1_scalar_negate(&t, &t);
1143 secp256k1_scalar_add(&x, &x, &t);
1145 CHECK(secp256k1_scalar_eq(&x, number)); /* check that wnaf represents number */
1148 void run_wnaf(void) {
1150 secp256k1_scalar_t n;
1151 for (i = 0; i < count; i++) {
1152 random_scalar_order(&n);
1154 secp256k1_scalar_negate(&n, &n);
1155 test_wnaf(&n, 4+(i%10));
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;
1162 random_scalar_order_test(&nonce);
1163 } while(!secp256k1_ecdsa_sig_sign(sig, key, msg, &nonce, recid));
1166 void test_ecdsa_sign_verify(void) {
1167 secp256k1_gej_t pubj;
1169 secp256k1_scalar_t one;
1170 secp256k1_scalar_t msg, key;
1171 secp256k1_ecdsa_sig_t sig;
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));
1187 void run_ecdsa_sign_verify(void) {
1189 for (i = 0; i < 10*count; i++) {
1190 test_ecdsa_sign_verify();
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) {
1198 memcpy(nonce32, data, 32);
1199 return (counter == 0);
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);
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. */
1211 memset(nonce32, counter==0 ? 0 : 255, 32);
1212 if (counter == 2) nonce32[31]--;
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
1222 memcpy(nonce32, order, 32);
1223 if (counter == 4) nonce32[31]++;
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);
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;
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;
1248 int recpubkeylen = 0;
1250 int seckeylen = 300;
1252 /* Generate a random key and message. */
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);
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));
1267 CHECK(secp256k1_ec_pubkey_verify(pubkey, pubkeylen));
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);
1274 /* Optionally tweak the keys using addition. */
1275 if (secp256k1_rand32() % 3 == 0) {
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);
1290 /* Optionally tweak the keys using multiplication. */
1291 if (secp256k1_rand32() % 3 == 0) {
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);
1307 CHECK(secp256k1_ecdsa_sign(message, signature, &signaturelen, privkey, NULL, NULL) == 1);
1308 CHECK(signaturelen > 0);
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);
1316 CHECK(secp256k1_ecdsa_sign_compact(message, csignature, privkey, NULL, NULL, &recid) == 1);
1317 CHECK(!is_empty_compact_signature(csignature));
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);
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;
1338 if ((r & 3) == 0) len = (r & 252) >> 3;
1341 in[0] = (r & 2) ? 4 : (r & 1? 6 : 7);
1343 in[0] = (r & 1) ? 2 : 3;
1346 if ((r & 7) == 0) in[0] = (r & 2040) >> 3;
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;
1356 /* If the pubkey can be parsed, it should round-trip... */
1357 CHECK(secp256k1_eckey_pubkey_serialize(&elem, out, &size, len == 33));
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]);
1363 CHECK(secp256k1_eckey_pubkey_serialize(&elem, in, &size, 0));
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);
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);
1382 void run_random_pubkeys(void) {
1384 for (i = 0; i < 10*count; i++) {
1385 test_random_pubkeys();
1389 void run_ecdsa_end_to_end(void) {
1391 for (i = 0; i < 64*count; i++) {
1392 test_ecdsa_end_to_end();
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', '.', '.', '.'
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
1416 unsigned char pubkey[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,
1429 unsigned char pubkeyb[33];
1430 int pubkeyblen = 33;
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));
1438 for (recid = 0; recid < 4; recid++) {
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,
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,
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,
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,
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
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);
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);
1500 CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt3, sizeof(sigbderalt3), pubkeyb, pubkeyblen) == -2);
1502 CHECK(secp256k1_ecdsa_verify(msg32, sigbderalt4, sizeof(sigbderalt4), pubkeyb, pubkeyblen) == -2);
1503 /* Damage signature. */
1505 CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) == 0);
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++) {
1511 unsigned char orig = sigbder[i];
1512 /*Try every single-byte change.*/
1513 for (c = 0; c < 256; c++) {
1514 if (c == orig ) continue;
1516 CHECK(secp256k1_ecdsa_verify(msg32, sigbder, sizeof(sigbder), pubkeyb, pubkeyblen) ==
1517 (i==4 || i==7) ? 0 : -2 );
1523 /* Test the case where ECDSA recomputes a point that is infinity. */
1525 secp256k1_gej_t keyj;
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);
1536 CHECK(secp256k1_ecdsa_sig_verify(&sig, &key, &msg) == 0);
1539 /* Test r/s equal to zero */
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,
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);
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);
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);
1569 /*Signature where s would be zero.*/
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,
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
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,
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,
1595 unsigned char sig[72];
1597 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 0);
1599 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 0);
1603 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) == 1);
1605 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce2) == 1);
1608 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, precomputed_nonce_function, nonce) != 1);
1612 /* Nonce function corner cases. */
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];
1625 /* High key results in signature failure. */
1626 memset(key, 0xFF, 32);
1627 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, NULL) == 0);
1629 /* Zero key results in signature failure. */
1631 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, NULL) == 0);
1633 /* Nonce function failure results in signature failure. */
1635 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_fail, NULL) == 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. */
1641 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, nonce_function_test_retry, NULL) == 1);
1643 CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, nonce_function_rfc6979, NULL) == 1);
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. */
1654 CHECK(secp256k1_ecdsa_sign(msg, sig, &siglen, key, NULL, NULL) == 1);
1656 CHECK(secp256k1_ecdsa_sign(msg, sig2, &siglen2, key, NULL, NULL) == 1);
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++) {
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));
1678 /* The default nonce function changes output with different keys. */
1679 for(i = 256; i < 512; i++) {
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));
1692 /* Privkey export where pubkey is the point at infinity. */
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,
1702 CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 0));
1703 CHECK(!secp256k1_ec_privkey_export(seckey, privkey, &outlen, 1));
1707 void run_ecdsa_edge_cases(void) {
1708 test_ecdsa_edge_cases();
1711 #ifdef ENABLE_OPENSSL_TESTS
1712 EC_KEY *get_openssl_key(const secp256k1_scalar_t *key) {
1713 unsigned char privkey[300];
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));
1724 void test_ecdsa_openssl(void) {
1727 secp256k1_ecdsa_sig_t sig;
1728 secp256k1_scalar_t one;
1729 secp256k1_scalar_t msg2;
1730 secp256k1_scalar_t key, msg;
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);
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));
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);
1754 EC_KEY_free(ec_key);
1757 void run_ecdsa_openssl(void) {
1759 for (i = 0; i < 10*count; i++) {
1760 test_ecdsa_openssl();
1765 int main(int argc, char **argv) {
1767 /* find iteration count */
1769 count = strtol(argv[1], NULL, 0);
1772 /* find random seed */
1774 sscanf(argv[2], "%" I64uFORMAT, (unsigned long long*)&seed);
1776 FILE *frand = fopen("/dev/urandom", "r");
1777 if (!frand || !fread(&seed, sizeof(seed), 1, frand)) {
1778 seed = time(NULL) * 1337;
1782 secp256k1_rand_seed(seed);
1784 printf("test count = %i\n", count);
1785 printf("random seed = %" I64uFORMAT "\n", (unsigned long long)seed);
1788 secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1790 /* initializing a second time shouldn't cause any harm or memory leaks. */
1791 secp256k1_start(SECP256K1_START_SIGN | SECP256K1_START_VERIFY);
1794 run_hmac_sha256_tests();
1795 run_rfc6979_hmac_sha256_tests();
1797 #ifndef USE_NUM_NONE
1799 run_num_smalltests();
1807 run_field_inv_var();
1808 run_field_inv_all_var();
1810 run_field_convert();
1819 run_point_times_order();
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();
1831 printf("random run = %llu\n", (unsigned long long)secp256k1_rand32() + ((unsigned long long)secp256k1_rand32() << 32));
1836 /* shutting down twice shouldn't cause any double frees. */