Skip to content

Commit b340123

Browse files
sipasipa
committed
Merge bitcoin#402: Add support for testing quadratic residues
e6e9805 Add function for testing quadratic residue field/group elements. (Pieter Wuille) efd953a Add Jacobi symbol test via GMP (Peter Dettman)
2 parents fa36a0d + e6e9805 commit b340123

File tree

8 files changed

+238
-4
lines changed

8 files changed

+238
-4
lines changed

‎src/bench_internal.c‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -227,6 +227,15 @@ void bench_group_add_affine_var(void* arg) {
227227
}
228228
}
229229

230+
void bench_group_jacobi_var(void* arg) {
231+
int i;
232+
bench_inv_t *data = (bench_inv_t*)arg;
233+
234+
for (i = 0; i < 20000; i++) {
235+
secp256k1_gej_has_quad_y_var(&data->gej_x);
236+
}
237+
}
238+
230239
void bench_ecmult_wnaf(void* arg) {
231240
int i;
232241
bench_inv_t *data = (bench_inv_t*)arg;
@@ -299,6 +308,21 @@ void bench_context_sign(void* arg) {
299308
}
300309
}
301310

311+
#ifndef USE_NUM_NONE
312+
void bench_num_jacobi(void* arg) {
313+
int i;
314+
bench_inv_t *data = (bench_inv_t*)arg;
315+
secp256k1_num nx, norder;
316+
317+
secp256k1_scalar_get_num(&nx, &data->scalar_x);
318+
secp256k1_scalar_order_get_num(&norder);
319+
secp256k1_scalar_get_num(&norder, &data->scalar_y);
320+
321+
for (i = 0; i < 200000; i++) {
322+
secp256k1_num_jacobi(&nx, &norder);
323+
}
324+
}
325+
#endif
302326

303327
int have_flag(int argc, char** argv, char *flag) {
304328
char** argm = argv + argc;
@@ -339,6 +363,7 @@ int main(int argc, char **argv) {
339363
if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_var", bench_group_add_var, bench_setup, NULL, &data, 10, 200000);
340364
if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine", bench_group_add_affine, bench_setup, NULL, &data, 10, 200000);
341365
if (have_flag(argc, argv, "group") || have_flag(argc, argv, "add")) run_benchmark("group_add_affine_var", bench_group_add_affine_var, bench_setup, NULL, &data, 10, 200000);
366+
if (have_flag(argc, argv, "group") || have_flag(argc, argv, "jacobi")) run_benchmark("group_jacobi_var", bench_group_jacobi_var, bench_setup, NULL, &data, 10, 20000);
342367

343368
if (have_flag(argc, argv, "ecmult") || have_flag(argc, argv, "wnaf")) run_benchmark("wnaf_const", bench_wnaf_const, bench_setup, NULL, &data, 10, 20000);
344369
if (have_flag(argc, argv, "ecmult") || have_flag(argc, argv, "wnaf")) run_benchmark("ecmult_wnaf", bench_ecmult_wnaf, bench_setup, NULL, &data, 10, 20000);
@@ -350,5 +375,8 @@ int main(int argc, char **argv) {
350375
if (have_flag(argc, argv, "context") || have_flag(argc, argv, "verify")) run_benchmark("context_verify", bench_context_verify, bench_setup, NULL, &data, 10, 20);
351376
if (have_flag(argc, argv, "context") || have_flag(argc, argv, "sign")) run_benchmark("context_sign", bench_context_sign, bench_setup, NULL, &data, 10, 200);
352377

378+
#ifndef USE_NUM_NONE
379+
if (have_flag(argc, argv, "num") || have_flag(argc, argv, "jacobi")) run_benchmark("num_jacobi", bench_num_jacobi, bench_setup, NULL, &data, 10, 200000);
380+
#endif
353381
return 0;
354382
}

‎src/field.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,9 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a);
9494
* itself. */
9595
static int secp256k1_fe_sqrt_var(secp256k1_fe *r, const secp256k1_fe *a);
9696

97+
/** Checks whether a field element is a quadratic residue. */
98+
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a);
99+
97100
/** Sets a field element to be the (modular) inverse of another. Requires the input's magnitude to be
98101
* at most 8. The output magnitude is 1 (but not guaranteed to be normalized). */
99102
static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a);

‎src/field_impl.h‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -280,4 +280,29 @@ static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe *r, const secp256k
280280
r[0] = u;
281281
}
282282

283+
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a) {
284+
#ifndef USE_NUM_NONE
285+
unsigned char b[32];
286+
secp256k1_num n;
287+
secp256k1_num m;
288+
/* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
289+
static const unsigned char prime[32] = {
290+
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
291+
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
292+
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
293+
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F
294+
};
295+
296+
secp256k1_fe c = *a;
297+
secp256k1_fe_normalize_var(&c);
298+
secp256k1_fe_get_b32(b, &c);
299+
secp256k1_num_set_bin(&n, b, 32);
300+
secp256k1_num_set_bin(&m, prime, 32);
301+
return secp256k1_num_jacobi(&n, &m) >= 0;
302+
#else
303+
secp256k1_fe r;
304+
return secp256k1_fe_sqrt_var(&r, a) == 1;
305+
#endif
306+
}
307+
283308
#endif

‎src/group.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,9 @@ static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a);
9494
/** Check whether a group element is the point at infinity. */
9595
static int secp256k1_gej_is_infinity(const secp256k1_gej *a);
9696

97+
/** Check whether a group element's y coordinate is a quadratic residue. */
98+
static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a);
99+
97100
/** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0).
98101
* a may not be zero. Constant time. */
99102
static void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr);

‎src/group_impl.h‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -629,4 +629,18 @@ static void secp256k1_ge_mul_lambda(secp256k1_ge *r, const secp256k1_ge *a) {
629629
}
630630
#endif
631631

632+
static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a) {
633+
secp256k1_fe yz;
634+
635+
if (a->infinity) {
636+
return 0;
637+
}
638+
639+
/* We rely on the fact that the Jacobi symbol of 1 / a->z^3 is the same as
640+
* that of a->z. Thus a->y / a->z^3 is a quadratic residue iff a->y * a->z
641+
is */
642+
secp256k1_fe_mul(&yz, &a->y, &a->z);
643+
return secp256k1_fe_is_quad_var(&yz);
644+
}
645+
632646
#endif

‎src/num.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,9 @@ static void secp256k1_num_set_bin(secp256k1_num *r, const unsigned char *a, unsi
3232
/** Compute a modular inverse. The input must be less than the modulus. */
3333
static void secp256k1_num_mod_inverse(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *m);
3434

35+
/** Compute the jacobi symbol (a|b). b must be positive and odd. */
36+
static int secp256k1_num_jacobi(const secp256k1_num *a, const secp256k1_num *b);
37+
3538
/** Compare the absolute value of two numbers. */
3639
static int secp256k1_num_cmp(const secp256k1_num *a, const secp256k1_num *b);
3740

@@ -57,6 +60,9 @@ static void secp256k1_num_shift(secp256k1_num *r, int bits);
5760
/** Check whether a number is zero. */
5861
static int secp256k1_num_is_zero(const secp256k1_num *a);
5962

63+
/** Check whether a number is one. */
64+
static int secp256k1_num_is_one(const secp256k1_num *a);
65+
6066
/** Check whether a number is strictly negative. */
6167
static int secp256k1_num_is_neg(const secp256k1_num *a);
6268

‎src/num_gmp_impl.h‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -144,6 +144,32 @@ static void secp256k1_num_mod_inverse(secp256k1_num *r, const secp256k1_num *a,
144144
memset(v, 0, sizeof(v));
145145
}
146146

147+
static int secp256k1_num_jacobi(const secp256k1_num *a, const secp256k1_num *b) {
148+
int ret;
149+
mpz_t ga, gb;
150+
secp256k1_num_sanity(a);
151+
secp256k1_num_sanity(b);
152+
VERIFY_CHECK(!b->neg && (b->limbs > 0) && (b->data[0] & 1));
153+
154+
mpz_inits(ga, gb, NULL);
155+
156+
mpz_import(gb, b->limbs, -1, sizeof(mp_limb_t), 0, 0, b->data);
157+
mpz_import(ga, a->limbs, -1, sizeof(mp_limb_t), 0, 0, a->data);
158+
if (a->neg) {
159+
mpz_neg(ga, ga);
160+
}
161+
162+
ret = mpz_jacobi(ga, gb);
163+
164+
mpz_clears(ga, gb, NULL);
165+
166+
return ret;
167+
}
168+
169+
static int secp256k1_num_is_one(const secp256k1_num *a) {
170+
return (a->limbs == 1 && a->data[0] == 1);
171+
}
172+
147173
static int secp256k1_num_is_zero(const secp256k1_num *a) {
148174
return (a->limbs == 1 && a->data[0] == 0);
149175
}

‎src/tests.c‎

Lines changed: 133 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -473,6 +473,8 @@ void test_num_negate(void) {
473473
}
474474

475475
void test_num_add_sub(void) {
476+
int i;
477+
secp256k1_scalar s;
476478
secp256k1_num n1;
477479
secp256k1_num n2;
478480
secp256k1_num n1p2, n2p1, n1m2, n2m1;
@@ -498,13 +500,119 @@ void test_num_add_sub(void) {
498500
CHECK(!secp256k1_num_eq(&n2p1, &n1));
499501
secp256k1_num_sub(&n2p1, &n2p1, &n2); /* n2p1 = R2 + R1 - R2 = R1 */
500502
CHECK(secp256k1_num_eq(&n2p1, &n1));
503+
504+
/* check is_one */
505+
secp256k1_scalar_set_int(&s, 1);
506+
secp256k1_scalar_get_num(&n1, &s);
507+
CHECK(secp256k1_num_is_one(&n1));
508+
/* check that 2^n + 1 is never 1 */
509+
secp256k1_scalar_get_num(&n2, &s);
510+
for (i = 0; i < 250; ++i) {
511+
secp256k1_num_add(&n1, &n1, &n1); /* n1 *= 2 */
512+
secp256k1_num_add(&n1p2, &n1, &n2); /* n1p2 = n1 + 1 */
513+
CHECK(!secp256k1_num_is_one(&n1p2));
514+
}
515+
}
516+
517+
void test_num_mod(void) {
518+
int i;
519+
secp256k1_scalar s;
520+
secp256k1_num order, n;
521+
522+
/* check that 0 mod anything is 0 */
523+
random_scalar_order_test(&s);
524+
secp256k1_scalar_get_num(&order, &s);
525+
secp256k1_scalar_set_int(&s, 0);
526+
secp256k1_scalar_get_num(&n, &s);
527+
secp256k1_num_mod(&n, &order);
528+
CHECK(secp256k1_num_is_zero(&n));
529+
530+
/* check that anything mod 1 is 0 */
531+
secp256k1_scalar_set_int(&s, 1);
532+
secp256k1_scalar_get_num(&order, &s);
533+
secp256k1_scalar_get_num(&n, &s);
534+
secp256k1_num_mod(&n, &order);
535+
CHECK(secp256k1_num_is_zero(&n));
536+
537+
/* check that increasing the number past 2^256 does not break this */
538+
random_scalar_order_test(&s);
539+
secp256k1_scalar_get_num(&n, &s);
540+
/* multiply by 2^8, which'll test this case with high probability */
541+
for (i = 0; i < 8; ++i) {
542+
secp256k1_num_add(&n, &n, &n);
543+
}
544+
secp256k1_num_mod(&n, &order);
545+
CHECK(secp256k1_num_is_zero(&n));
546+
}
547+
548+
void test_num_jacobi(void) {
549+
secp256k1_scalar sqr;
550+
secp256k1_scalar small;
551+
secp256k1_scalar five; /* five is not a quadratic residue */
552+
secp256k1_num order, n;
553+
int i;
554+
/* squares mod 5 are 1, 4 */
555+
const int jacobi5[10] = { 0, 1, -1, -1, 1, 0, 1, -1, -1, 1 };
556+
557+
/* check some small values with 5 as the order */
558+
secp256k1_scalar_set_int(&five, 5);
559+
secp256k1_scalar_get_num(&order, &five);
560+
for (i = 0; i < 10; ++i) {
561+
secp256k1_scalar_set_int(&small, i);
562+
secp256k1_scalar_get_num(&n, &small);
563+
CHECK(secp256k1_num_jacobi(&n, &order) == jacobi5[i]);
564+
}
565+
566+
/** test large values with 5 as group order */
567+
secp256k1_scalar_get_num(&order, &five);
568+
/* we first need a scalar which is not a multiple of 5 */
569+
do {
570+
secp256k1_num fiven;
571+
random_scalar_order_test(&sqr);
572+
secp256k1_scalar_get_num(&fiven, &five);
573+
secp256k1_scalar_get_num(&n, &sqr);
574+
secp256k1_num_mod(&n, &fiven);
575+
} while (secp256k1_num_is_zero(&n));
576+
/* next force it to be a residue. 2 is a nonresidue mod 5 so we can
577+
* just multiply by two, i.e. add the number to itself */
578+
if (secp256k1_num_jacobi(&n, &order) == -1) {
579+
secp256k1_num_add(&n, &n, &n);
580+
}
581+
582+
/* test residue */
583+
CHECK(secp256k1_num_jacobi(&n, &order) == 1);
584+
/* test nonresidue */
585+
secp256k1_num_add(&n, &n, &n);
586+
CHECK(secp256k1_num_jacobi(&n, &order) == -1);
587+
588+
/** test with secp group order as order */
589+
secp256k1_scalar_order_get_num(&order);
590+
random_scalar_order_test(&sqr);
591+
secp256k1_scalar_sqr(&sqr, &sqr);
592+
/* test residue */
593+
secp256k1_scalar_get_num(&n, &sqr);
594+
CHECK(secp256k1_num_jacobi(&n, &order) == 1);
595+
/* test nonresidue */
596+
secp256k1_scalar_mul(&sqr, &sqr, &five);
597+
secp256k1_scalar_get_num(&n, &sqr);
598+
CHECK(secp256k1_num_jacobi(&n, &order) == -1);
599+
/* test multiple of the order*/
600+
CHECK(secp256k1_num_jacobi(&order, &order) == 0);
601+
602+
/* check one less than the order */
603+
secp256k1_scalar_set_int(&small, 1);
604+
secp256k1_scalar_get_num(&n, &small);
605+
secp256k1_num_sub(&n, &order, &n);
606+
CHECK(secp256k1_num_jacobi(&n, &order) == 1); /* sage confirms this is 1 */
501607
}
502608

503609
void run_num_smalltests(void) {
504610
int i;
505611
for (i = 0; i < 100*count; i++) {
506612
test_num_negate();
507613
test_num_add_sub();
614+
test_num_mod();
615+
test_num_jacobi();
508616
}
509617
}
510618
#endif
@@ -689,6 +797,10 @@ void scalar_test(void) {
689797
secp256k1_scalar_inverse(&inv, &inv);
690798
/* Inverting one must result in one. */
691799
CHECK(secp256k1_scalar_is_one(&inv));
800+
#ifndef USE_NUM_NONE
801+
secp256k1_scalar_get_num(&invnum, &inv);
802+
CHECK(secp256k1_num_is_one(&invnum));
803+
#endif
692804
}
693805
}
694806

@@ -2067,9 +2179,10 @@ void run_ec_combine(void) {
20672179
void test_group_decompress(const secp256k1_fe* x) {
20682180
/* The input itself, normalized. */
20692181
secp256k1_fe fex = *x;
2070-
secp256k1_fe tmp;
2182+
secp256k1_fe fez;
20712183
/* Results of set_xquad_var, set_xo_var(..., 0), set_xo_var(..., 1). */
20722184
secp256k1_ge ge_quad, ge_even, ge_odd;
2185+
secp256k1_gej gej_quad;
20732186
/* Return values of the above calls. */
20742187
int res_quad, res_even, res_odd;
20752188

@@ -2101,13 +2214,29 @@ void test_group_decompress(const secp256k1_fe* x) {
21012214
CHECK(secp256k1_fe_equal_var(&ge_odd.x, x));
21022215

21032216
/* Check that the Y coordinate result in ge_quad is a square. */
2104-
CHECK(secp256k1_fe_sqrt_var(&tmp, &ge_quad.y));
2105-
secp256k1_fe_sqr(&tmp, &tmp);
2106-
CHECK(secp256k1_fe_equal_var(&tmp, &ge_quad.y));
2217+
CHECK(secp256k1_fe_is_quad_var(&ge_quad.y));
21072218

21082219
/* Check odd/even Y in ge_odd, ge_even. */
21092220
CHECK(secp256k1_fe_is_odd(&ge_odd.y));
21102221
CHECK(!secp256k1_fe_is_odd(&ge_even.y));
2222+
2223+
/* Check secp256k1_gej_has_quad_y_var. */
2224+
secp256k1_gej_set_ge(&gej_quad, &ge_quad);
2225+
CHECK(secp256k1_gej_has_quad_y_var(&gej_quad));
2226+
do {
2227+
random_fe_test(&fez);
2228+
} while (secp256k1_fe_is_zero(&fez));
2229+
secp256k1_gej_rescale(&gej_quad, &fez);
2230+
CHECK(secp256k1_gej_has_quad_y_var(&gej_quad));
2231+
secp256k1_gej_neg(&gej_quad, &gej_quad);
2232+
CHECK(!secp256k1_gej_has_quad_y_var(&gej_quad));
2233+
do {
2234+
random_fe_test(&fez);
2235+
} while (secp256k1_fe_is_zero(&fez));
2236+
secp256k1_gej_rescale(&gej_quad, &fez);
2237+
CHECK(!secp256k1_gej_has_quad_y_var(&gej_quad));
2238+
secp256k1_gej_neg(&gej_quad, &gej_quad);
2239+
CHECK(secp256k1_gej_has_quad_y_var(&gej_quad));
21112240
}
21122241
}
21132242

0 commit comments

Comments
 (0)