Differential D7664 Diff 24024 src/secp256k1/src/tests_exhaustive.c

Changeset View

Standalone View

src/secp256k1/src/tests_exhaustive.c

Show First 20 Lines • Show All 60 Lines • ▼ Show 20 Lines	do {
secp256k1_rand256(bin);		secp256k1_rand256(bin);
if (secp256k1_fe_set_b32(x, bin)) {		if (secp256k1_fe_set_b32(x, bin)) {
return;		return;
}		}
} while(1);		} while(1);
}		}
/** END stolen from tests.c */		/** END stolen from tests.c */

		static uint32_t num_cores = 1;
		static uint32_t this_core = 0;

		SECP256K1_INLINE static int skip_section(uint64_t* iter) {
		if (num_cores == 1) return 0;
		*iter += 0xe7037ed1a0b428dbULL;
		return ((((uint32_t)iter ^ (iter >> 32)) * num_cores) >> 32) != this_core;
		}

int secp256k1_nonce_function_smallint(unsigned char nonce32, const unsigned char msg32,		int secp256k1_nonce_function_smallint(unsigned char nonce32, const unsigned char msg32,
const unsigned char key32, const unsigned char algo16,		const unsigned char key32, const unsigned char algo16,
void *data, unsigned int attempt) {		void *data, unsigned int attempt) {
secp256k1_scalar s;		secp256k1_scalar s;
int *idata = data;		int *idata = data;
(void)msg32;		(void)msg32;
(void)key32;		(void)key32;
(void)algo16;		(void)algo16;
Show All 17 Lines	for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {
secp256k1_ge_mul_lambda(&res, &group[i]);		secp256k1_ge_mul_lambda(&res, &group[i]);
ge_equals_ge(&group[i * EXHAUSTIVE_TEST_LAMBDA % EXHAUSTIVE_TEST_ORDER], &res);		ge_equals_ge(&group[i * EXHAUSTIVE_TEST_LAMBDA % EXHAUSTIVE_TEST_ORDER], &res);
}		}
}		}
#endif		#endif

void test_exhaustive_addition(const secp256k1_ge group, const secp256k1_gej groupj) {		void test_exhaustive_addition(const secp256k1_ge group, const secp256k1_gej groupj) {
int i, j;		int i, j;
		uint64_t iter = 0;

/* Sanity-check (and check infinity functions) */		/* Sanity-check (and check infinity functions) */
CHECK(secp256k1_ge_is_infinity(&group[0]));		CHECK(secp256k1_ge_is_infinity(&group[0]));
CHECK(secp256k1_gej_is_infinity(&groupj[0]));		CHECK(secp256k1_gej_is_infinity(&groupj[0]));
for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) {		for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) {
CHECK(!secp256k1_ge_is_infinity(&group[i]));		CHECK(!secp256k1_ge_is_infinity(&group[i]));
CHECK(!secp256k1_gej_is_infinity(&groupj[i]));		CHECK(!secp256k1_gej_is_infinity(&groupj[i]));
}		}

/* Check all addition formulae */		/* Check all addition formulae */
for (j = 0; j < EXHAUSTIVE_TEST_ORDER; j++) {		for (j = 0; j < EXHAUSTIVE_TEST_ORDER; j++) {
secp256k1_fe fe_inv;		secp256k1_fe fe_inv;
		if (skip_section(&iter)) continue;
secp256k1_fe_inv(&fe_inv, &groupj[j].z);		secp256k1_fe_inv(&fe_inv, &groupj[j].z);
for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {		for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {
secp256k1_ge zless_gej;		secp256k1_ge zless_gej;
secp256k1_gej tmp;		secp256k1_gej tmp;
/* add_var */		/* add_var */
secp256k1_gej_add_var(&tmp, &groupj[i], &groupj[j], NULL);		secp256k1_gej_add_var(&tmp, &groupj[i], &groupj[j], NULL);
ge_equals_gej(&group[(i + j) % EXHAUSTIVE_TEST_ORDER], &tmp);		ge_equals_gej(&group[(i + j) % EXHAUSTIVE_TEST_ORDER], &tmp);
/* add_ge */		/* add_ge */
Show All 30 Lines	for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) {
ge_equals_ge(&group[EXHAUSTIVE_TEST_ORDER - i], &tmp);		ge_equals_ge(&group[EXHAUSTIVE_TEST_ORDER - i], &tmp);
secp256k1_gej_neg(&tmpj, &groupj[i]);		secp256k1_gej_neg(&tmpj, &groupj[i]);
ge_equals_gej(&group[EXHAUSTIVE_TEST_ORDER - i], &tmpj);		ge_equals_gej(&group[EXHAUSTIVE_TEST_ORDER - i], &tmpj);
}		}
}		}

void test_exhaustive_ecmult(const secp256k1_context ctx, const secp256k1_ge group, const secp256k1_gej *groupj) {		void test_exhaustive_ecmult(const secp256k1_context ctx, const secp256k1_ge group, const secp256k1_gej *groupj) {
int i, j, r_log;		int i, j, r_log;
		uint64_t iter = 0;
for (r_log = 1; r_log < EXHAUSTIVE_TEST_ORDER; r_log++) {		for (r_log = 1; r_log < EXHAUSTIVE_TEST_ORDER; r_log++) {
for (j = 0; j < EXHAUSTIVE_TEST_ORDER; j++) {		for (j = 0; j < EXHAUSTIVE_TEST_ORDER; j++) {
		if (skip_section(&iter)) continue;
for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {		for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {
secp256k1_gej tmp;		secp256k1_gej tmp;
secp256k1_scalar na, ng;		secp256k1_scalar na, ng;
secp256k1_scalar_set_int(&na, i);		secp256k1_scalar_set_int(&na, i);
secp256k1_scalar_set_int(&ng, j);		secp256k1_scalar_set_int(&ng, j);

secp256k1_ecmult(&ctx->ecmult_ctx, &tmp, &groupj[r_log], &na, &ng);		secp256k1_ecmult(&ctx->ecmult_ctx, &tmp, &groupj[r_log], &na, &ng);
ge_equals_gej(&group[(i * r_log + j) % EXHAUSTIVE_TEST_ORDER], &tmp);		ge_equals_gej(&group[(i * r_log + j) % EXHAUSTIVE_TEST_ORDER], &tmp);
Show All 16 Lines	static int ecmult_multi_callback(secp256k1_scalar sc, secp256k1_ge pt, size_t idx, void *cbdata) {
ecmult_multi_data data = (ecmult_multi_data) cbdata;		ecmult_multi_data data = (ecmult_multi_data) cbdata;
*sc = data->sc[idx];		*sc = data->sc[idx];
*pt = data->pt[idx];		*pt = data->pt[idx];
return 1;		return 1;
}		}

void test_exhaustive_ecmult_multi(const secp256k1_context ctx, const secp256k1_ge group) {		void test_exhaustive_ecmult_multi(const secp256k1_context ctx, const secp256k1_ge group) {
int i, j, k, x, y;		int i, j, k, x, y;
		uint64_t iter = 0;
secp256k1_scratch *scratch = secp256k1_scratch_create(&ctx->error_callback, 4096);		secp256k1_scratch *scratch = secp256k1_scratch_create(&ctx->error_callback, 4096);
for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {		for (i = 0; i < EXHAUSTIVE_TEST_ORDER; i++) {
for (j = 0; j < EXHAUSTIVE_TEST_ORDER; j++) {		for (j = 0; j < EXHAUSTIVE_TEST_ORDER; j++) {
for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) {		for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) {
for (x = 0; x < EXHAUSTIVE_TEST_ORDER; x++) {		for (x = 0; x < EXHAUSTIVE_TEST_ORDER; x++) {
		if (skip_section(&iter)) continue;
for (y = 0; y < EXHAUSTIVE_TEST_ORDER; y++) {		for (y = 0; y < EXHAUSTIVE_TEST_ORDER; y++) {
secp256k1_gej tmp;		secp256k1_gej tmp;
secp256k1_scalar g_sc;		secp256k1_scalar g_sc;
ecmult_multi_data data;		ecmult_multi_data data;

secp256k1_scalar_set_int(&data.sc[0], i);		secp256k1_scalar_set_int(&data.sc[0], i);
secp256k1_scalar_set_int(&data.sc[1], j);		secp256k1_scalar_set_int(&data.sc[1], j);
secp256k1_scalar_set_int(&g_sc, k);		secp256k1_scalar_set_int(&g_sc, k);
Show All 17 Lines	void r_from_k(secp256k1_scalar r, const secp256k1_ge group, int k, int* overflow) {
x = group[k].x;		x = group[k].x;
secp256k1_fe_normalize(&x);		secp256k1_fe_normalize(&x);
secp256k1_fe_get_b32(x_bin, &x);		secp256k1_fe_get_b32(x_bin, &x);
secp256k1_scalar_set_b32(r, x_bin, overflow);		secp256k1_scalar_set_b32(r, x_bin, overflow);
}		}

void test_exhaustive_verify(const secp256k1_context ctx, const secp256k1_ge group) {		void test_exhaustive_verify(const secp256k1_context ctx, const secp256k1_ge group) {
int s, r, msg, key;		int s, r, msg, key;
		uint64_t iter = 0;
for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) {		for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) {
for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) {		for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) {
for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) {		for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) {
for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) {		for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) {
secp256k1_ge nonconst_ge;		secp256k1_ge nonconst_ge;
secp256k1_ecdsa_signature sig;		secp256k1_ecdsa_signature sig;
secp256k1_pubkey pk;		secp256k1_pubkey pk;
secp256k1_scalar sk_s, msg_s, r_s, s_s;		secp256k1_scalar sk_s, msg_s, r_s, s_s;
secp256k1_scalar s_times_k_s, msg_plus_r_times_sk_s;		secp256k1_scalar s_times_k_s, msg_plus_r_times_sk_s;
int k, should_verify;		int k, should_verify;
unsigned char msg32[32];		unsigned char msg32[32];

		if (skip_section(&iter)) continue;

secp256k1_scalar_set_int(&s_s, s);		secp256k1_scalar_set_int(&s_s, s);
secp256k1_scalar_set_int(&r_s, r);		secp256k1_scalar_set_int(&r_s, r);
secp256k1_scalar_set_int(&msg_s, msg);		secp256k1_scalar_set_int(&msg_s, msg);
secp256k1_scalar_set_int(&sk_s, key);		secp256k1_scalar_set_int(&sk_s, key);

/* Verify by hand */		/* Verify by hand */
/* Run through every k value that gives us this r and check that one works.		/* Run through every k value that gives us this r and check that one works.
* Note there could be none, there could be multiple, ECDSA is weird. */		* Note there could be none, there could be multiple, ECDSA is weird. */
Show All 22 Lines	for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) {
}		}
}		}
}		}
}		}
}		}

void test_exhaustive_sign(const secp256k1_context ctx, const secp256k1_ge group) {		void test_exhaustive_sign(const secp256k1_context ctx, const secp256k1_ge group) {
int i, j, k;		int i, j, k;
		uint64_t iter = 0;

/* Loop */		/* Loop */
for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) { /* message */		for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) { /* message */
for (j = 1; j < EXHAUSTIVE_TEST_ORDER; j++) { /* key */		for (j = 1; j < EXHAUSTIVE_TEST_ORDER; j++) { /* key */
		if (skip_section(&iter)) continue;
for (k = 1; k < EXHAUSTIVE_TEST_ORDER; k++) { /* nonce */		for (k = 1; k < EXHAUSTIVE_TEST_ORDER; k++) { /* nonce */
const int starting_k = k;		const int starting_k = k;
secp256k1_ecdsa_signature sig;		secp256k1_ecdsa_signature sig;
secp256k1_scalar sk, msg, r, s, expected_r;		secp256k1_scalar sk, msg, r, s, expected_r;
unsigned char sk32[32], msg32[32];		unsigned char sk32[32], msg32[32];
secp256k1_scalar_set_int(&msg, i);		secp256k1_scalar_set_int(&msg, i);
secp256k1_scalar_set_int(&sk, j);		secp256k1_scalar_set_int(&sk, j);
secp256k1_scalar_get_b32(sk32, &sk);		secp256k1_scalar_get_b32(sk32, &sk);
▲ Show 20 Lines • Show All 45 Lines • ▼ Show 20 Lines	int main(int argc, char** argv) {
if (argc > 1) {		if (argc > 1) {
count = strtol(argv[1], NULL, 0);		count = strtol(argv[1], NULL, 0);
}		}
printf("test count = %i\n", count);		printf("test count = %i\n", count);

/* find random seed */		/* find random seed */
secp256k1_rand_init(argc > 2 ? argv[2] : NULL);		secp256k1_rand_init(argc > 2 ? argv[2] : NULL);

		/* set up split processing */
		if (argc > 4) {
		num_cores = strtol(argv[3], NULL, 0);
		this_core = strtol(argv[4], NULL, 0);
		if (num_cores < 1 \|\| this_core >= num_cores) {
		fprintf(stderr, "Usage: %s [count] [seed] [numcores] [thiscore]\n", argv[0]);
		return 1;
		}
		printf("running tests for core %lu (out of [0..%lu])\n", (unsigned long)this_core, (unsigned long)num_cores - 1);
		}

while (count--) {		while (count--) {
/* Build context */		/* Build context */
ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN \| SECP256K1_CONTEXT_VERIFY);		ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN \| SECP256K1_CONTEXT_VERIFY);
secp256k1_rand256(rand32);		secp256k1_rand256(rand32);
CHECK(secp256k1_context_randomize(ctx, rand32));		CHECK(secp256k1_context_randomize(ctx, rand32));

/* Generate the entire group */		/* Generate the entire group */
secp256k1_gej_set_infinity(&groupj[0]);		secp256k1_gej_set_infinity(&groupj[0]);
▲ Show 20 Lines • Show All 51 Lines • Show Last 20 Lines