Skip to content

Commit 6466625

Browse files
sipasipa
committed
Improvements for coordinate decompression
1 parent e2100ad commit 6466625

File tree

5 files changed

+94
-5
lines changed

5 files changed

+94
-5
lines changed

‎src/field.h‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -87,9 +87,11 @@ static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp2
8787
* The output magnitude is 1 (but not guaranteed to be normalized). */
8888
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a);
8989

90-
/** Sets a field element to be the (modular) square root (if any exist) of another. Requires the
91-
* input's magnitude to be at most 8. The output magnitude is 1 (but not guaranteed to be
92-
* normalized). Return value indicates whether a square root was found. */
90+
/** If a has a square root, it is computed in r and 1 is returned. If a does not
91+
* have a square root, the root of its negation is computed and 0 is returned.
92+
* The input's magnitude can be at most 8. The output magnitude is 1 (but not
93+
* guaranteed to be normalized). The result in r will always be a square
94+
* itself. */
9395
static int secp256k1_fe_sqrt_var(secp256k1_fe *r, const secp256k1_fe *a);
9496

9597
/** Sets a field element to be the (modular) inverse of another. Requires the input's magnitude to be

‎src/field_impl.h‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,15 @@ SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe *a, const
2929
}
3030

3131
static int secp256k1_fe_sqrt_var(secp256k1_fe *r, const secp256k1_fe *a) {
32+
/** Given that p is congruent to 3 mod 4, we can compute the square root of
33+
* a mod p as the (p+1)/4'th power of a.
34+
*
35+
* As (p+1)/4 is an even number, it will have the same result for a and for
36+
* (-a). Only one of these two numbers actually has a square root however,
37+
* so we test at the end by squaring and comparing to the input.
38+
* Also because (p+1)/4 is an even number, the computed square root is
39+
* itself always a square (a ** ((p+1)/4) is the square of a ** ((p+1)/8)).
40+
*/
3241
secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
3342
int j;
3443

‎src/group.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,12 @@ typedef struct {
4343
/** Set a group element equal to the point with given X and Y coordinates */
4444
static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y);
4545

46+
/** Set a group element (affine) equal to the point with the given X coordinate
47+
* and a Y coordinate that is a quadratic residue modulo p. The return value
48+
* is true iff a coordinate with the given X coordinate exists.
49+
*/
50+
static int secp256k1_ge_set_xquad_var(secp256k1_ge *r, const secp256k1_fe *x);
51+
4652
/** Set a group element (affine) equal to the point with the given X coordinate, and given oddness
4753
* for Y. Return value indicates whether the result is valid. */
4854
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd);

‎src/group_impl.h‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -165,22 +165,27 @@ static void secp256k1_ge_clear(secp256k1_ge *r) {
165165
secp256k1_fe_clear(&r->y);
166166
}
167167

168-
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
168+
static int secp256k1_ge_set_xquad_var(secp256k1_ge *r, const secp256k1_fe *x) {
169169
secp256k1_fe x2, x3, c;
170170
r->x = *x;
171171
secp256k1_fe_sqr(&x2, x);
172172
secp256k1_fe_mul(&x3, x, &x2);
173173
r->infinity = 0;
174174
secp256k1_fe_set_int(&c, 7);
175175
secp256k1_fe_add(&c, &x3);
176-
if (!secp256k1_fe_sqrt_var(&r->y, &c)) {
176+
return secp256k1_fe_sqrt_var(&r->y, &c);
177+
}
178+
179+
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd) {
180+
if (!secp256k1_ge_set_xquad_var(r, x)) {
177181
return 0;
178182
}
179183
secp256k1_fe_normalize_var(&r->y);
180184
if (secp256k1_fe_is_odd(&r->y) != odd) {
181185
secp256k1_fe_negate(&r->y, &r->y, 1);
182186
}
183187
return 1;
188+
184189
}
185190

186191
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a) {

‎src/tests.c‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1420,6 +1420,16 @@ void random_fe(secp256k1_fe *x) {
14201420
} while(1);
14211421
}
14221422

1423+
void random_fe_test(secp256k1_fe *x) {
1424+
unsigned char bin[32];
1425+
do {
1426+
secp256k1_rand256_test(bin);
1427+
if (secp256k1_fe_set_b32(x, bin)) {
1428+
return;
1429+
}
1430+
} while(1);
1431+
}
1432+
14231433
void random_fe_non_zero(secp256k1_fe *nz) {
14241434
int tries = 10;
14251435
while (--tries >= 0) {
@@ -2038,6 +2048,62 @@ void run_ec_combine(void) {
20382048
}
20392049
}
20402050

2051+
void test_group_decompress(const secp256k1_fe* x) {
2052+
/* The input itself, normalized. */
2053+
secp256k1_fe fex = *x;
2054+
secp256k1_fe tmp;
2055+
/* Results of set_xquad_var, set_xo_var(..., 0), set_xo_var(..., 1). */
2056+
secp256k1_ge ge_quad, ge_even, ge_odd;
2057+
/* Return values of the above calls. */
2058+
int res_quad, res_even, res_odd;
2059+
2060+
secp256k1_fe_normalize_var(&fex);
2061+
2062+
res_quad = secp256k1_ge_set_xquad_var(&ge_quad, &fex);
2063+
res_even = secp256k1_ge_set_xo_var(&ge_even, &fex, 0);
2064+
res_odd = secp256k1_ge_set_xo_var(&ge_odd, &fex, 1);
2065+
2066+
CHECK(res_quad == res_even);
2067+
CHECK(res_quad == res_odd);
2068+
2069+
if (res_quad) {
2070+
secp256k1_fe_normalize_var(&ge_quad.x);
2071+
secp256k1_fe_normalize_var(&ge_odd.x);
2072+
secp256k1_fe_normalize_var(&ge_even.x);
2073+
secp256k1_fe_normalize_var(&ge_quad.y);
2074+
secp256k1_fe_normalize_var(&ge_odd.y);
2075+
secp256k1_fe_normalize_var(&ge_even.y);
2076+
2077+
/* No infinity allowed. */
2078+
CHECK(!ge_quad.infinity);
2079+
CHECK(!ge_even.infinity);
2080+
CHECK(!ge_odd.infinity);
2081+
2082+
/* Check that the x coordinates check out. */
2083+
CHECK(secp256k1_fe_equal_var(&ge_quad.x, x));
2084+
CHECK(secp256k1_fe_equal_var(&ge_even.x, x));
2085+
CHECK(secp256k1_fe_equal_var(&ge_odd.x, x));
2086+
2087+
/* Check that the Y coordinate result in ge_quad is a square. */
2088+
CHECK(secp256k1_fe_sqrt_var(&tmp, &ge_quad.y));
2089+
secp256k1_fe_sqr(&tmp, &tmp);
2090+
CHECK(secp256k1_fe_equal_var(&tmp, &ge_quad.y));
2091+
2092+
/* Check odd/even Y in ge_odd, ge_even. */
2093+
CHECK(secp256k1_fe_is_odd(&ge_odd.y));
2094+
CHECK(!secp256k1_fe_is_odd(&ge_even.y));
2095+
}
2096+
}
2097+
2098+
void run_group_decompress(void) {
2099+
int i;
2100+
for (i = 0; i < count * 4; i++) {
2101+
secp256k1_fe fe;
2102+
random_fe_test(&fe);
2103+
test_group_decompress(&fe);
2104+
}
2105+
}
2106+
20412107
/***** ECMULT TESTS *****/
20422108

20432109
void run_ecmult_chain(void) {
@@ -4259,6 +4325,7 @@ int main(int argc, char **argv) {
42594325

42604326
/* group tests */
42614327
run_ge();
4328+
run_group_decompress();
42624329

42634330
/* ecmult tests */
42644331
run_wnaf();

0 commit comments

Comments
 (0)