In preparation of adding secp256k1, add proper support for an 'a' curve coefficient.
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- eccdata.c | 35 ++++++++++++++++++++++++++++------- 1 file changed, 28 insertions(+), 7 deletions(-)
diff --git a/eccdata.c b/eccdata.c index b13547419e3e..a1f5b1135ab2 100644 --- a/eccdata.c +++ b/eccdata.c @@ -53,13 +53,13 @@ struct ecc_point
enum ecc_type { - /* y^2 = x^3 - 3x + b (mod p) */ + /* y^2 = x^3 + a x + b (mod p) */ ECC_TYPE_WEIERSTRASS, #if 0 /* x^2 + y^2 = 1 - d x^2 y^2 */ ECC_TYPE_EDWARDS, #endif - /* -x^2 + y^2 = 1 - d x^2 y^2 */ + /* a x^2 + y^2 = 1 - d x^2 y^2 */ ECC_TYPE_TWISTED_EDWARDS, };
@@ -75,6 +75,8 @@ struct ecc_curve mpz_t p; mpz_t b;
+ int a; + /* Curve order */ mpz_t q; struct ecc_point g; @@ -168,11 +170,14 @@ ecc_dup (const struct ecc_curve *ecc, mpz_mul_ui (m, p->y, 2); mpz_invert (m, m, ecc->p);
- /* t = 3 (x^2 - 1) * m */ + /* t = (3 * x^2 + a) * m */ mpz_mul (t, p->x, p->x); mpz_mod (t, t, ecc->p); - mpz_sub_ui (t, t, 1); mpz_mul_ui (t, t, 3); + if (ecc->a > 0) + mpz_add_ui (t, t, ecc->a); + else + mpz_sub_ui (t, t, -ecc->a);
mpz_mul (t, t, m); mpz_mod (t, t, ecc->p); @@ -296,10 +301,14 @@ ecc_add (const struct ecc_curve *ecc, struct ecc_point *r, mpz_mul (x, x, s); mpz_mod (x, x, ecc->p);
- /* y' = (p_y q_y - p_x q_x) / (1 + t) */ + /* y' = (p_y q_y - a p_x q_x) / (1 + t) */ mpz_mul (y, p->y, q->y); mpz_mod (y, y, ecc->p); - mpz_addmul (y, p->x, q->x); + mpz_mul (s, p->x, q->x); + if (ecc->a > 0) + mpz_submul_ui (y, s, ecc->a); + else + mpz_addmul_ui (y, s, -ecc->a); mpz_mod (y, y, ecc->p); mpz_add_ui (s, t, 1); mpz_invert (s, s, ecc->p); @@ -367,7 +376,7 @@ ecc_set_str (struct ecc_point *p,
static void ecc_curve_init_str (struct ecc_curve *ecc, enum ecc_type type, - const char *p, const char *b, const char *q, + const char *p, int a, const char *b, const char *q, const char *gx, const char *gy, const char *d, const char *t) { @@ -376,6 +385,7 @@ ecc_curve_init_str (struct ecc_curve *ecc, enum ecc_type type, mpz_init_set_str (ecc->p, p, 16); mpz_init_set_str (ecc->b, b, 16); mpz_init_set_str (ecc->q, q, 16); + ecc->a = a; ecc_init (&ecc->g); ecc_set_str (&ecc->g, gx, gy);
@@ -397,6 +407,8 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" "FFFFFFFFFFFFFFFF",
+ -3, + "64210519e59c80e70fa7e9ab72243049" "feb8deecc146b9b1",
@@ -429,6 +441,8 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "ffffffffffffffffffffffffffffffff" "000000000000000000000001",
+ -3, + "b4050a850c04b3abf54132565044b0b7" "d7bfd8ba270b39432355ffb4",
@@ -462,6 +476,8 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "FFFFFFFF000000010000000000000000" "00000000FFFFFFFFFFFFFFFFFFFFFFFF",
+ -3, + "5AC635D8AA3A93E7B3EBBD55769886BC" "651D06B0CC53B0F63BCE3C3E27D2604B",
@@ -496,6 +512,8 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "fffffffffffffffffffffffffffffffe" "ffffffff0000000000000000ffffffff", + -3, + "b3312fa7e23ee7e4988e056be3f82d19" "181d9c6efe8141120314088f5013875a" "c656398d8a2ed19d2a85c8edd3ec2aef", @@ -535,6 +553,8 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "ffffffffffffffffffffffffffffffff" "ffffffffffffffffffffffffffffffff",
+ -3, + "051" "953eb9618e1c9a1f929a21a0b68540ee" "a2da725b99b315f3b8b489918ef109e1" @@ -590,6 +610,7 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) ecc_curve_init_str (ecc, ECC_TYPE_TWISTED_EDWARDS, "7fffffffffffffffffffffffffffffff" "ffffffffffffffffffffffffffffffed", + -1, /* (121665/121666) mod p, from PARI/GP c = Mod(121665, p); c / (c+1) */