Changeset View
Changeset View
Standalone View
Standalone View
src/secp256k1/src/group_impl.h
| Show First 20 Lines • Show All 530 Lines • ▼ Show 20 Lines | static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, const secp256k1_fe *bzinv) { | ||||
| secp256k1_fe_add(&r->y, &h3); | secp256k1_fe_add(&r->y, &h3); | ||||
| } | } | ||||
| static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) { | static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) { | ||||
| /* Operations: 7 mul, 5 sqr, 24 add/cmov/half/mul_int/negate/normalize_weak/normalizes_to_zero */ | /* Operations: 7 mul, 5 sqr, 24 add/cmov/half/mul_int/negate/normalize_weak/normalizes_to_zero */ | ||||
| secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr; | secp256k1_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr; | ||||
| secp256k1_fe m_alt, rr_alt; | secp256k1_fe m_alt, rr_alt; | ||||
| int infinity, degenerate; | int degenerate; | ||||
| VERIFY_CHECK(!b->infinity); | VERIFY_CHECK(!b->infinity); | ||||
| VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); | VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); | ||||
| /** In: | /* In: | ||||
| * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks. | * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks. | ||||
| * In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002. | * In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002. | ||||
| * we find as solution for a unified addition/doubling formula: | * we find as solution for a unified addition/doubling formula: | ||||
| * lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation. | * lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation. | ||||
| * x3 = lambda^2 - (x1 + x2) | * x3 = lambda^2 - (x1 + x2) | ||||
| * 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2). | * 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2). | ||||
| * | * | ||||
| * Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives: | * Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives: | ||||
| ▲ Show 20 Lines • Show All 45 Lines • ▼ Show 20 Lines | static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b) { | ||||
| secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */ | secp256k1_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */ | ||||
| secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */ | secp256k1_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */ | ||||
| t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */ | t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */ | ||||
| m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */ | m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */ | ||||
| secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */ | secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */ | ||||
| secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 */ | secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 */ | ||||
| secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (2) */ | secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (2) */ | ||||
| secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (3) */ | secp256k1_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (3) */ | ||||
| /** If lambda = R/M = 0/0 we have a problem (except in the "trivial" | /* If lambda = R/M = R/0 we have a problem (except in the "trivial" | ||||
| * case that Z = z1z2 = 0, and this is special-cased later on). */ | * case that Z = z1z2 = 0, and this is special-cased later on). */ | ||||
| degenerate = secp256k1_fe_normalizes_to_zero(&m) & | degenerate = secp256k1_fe_normalizes_to_zero(&m); | ||||
| secp256k1_fe_normalizes_to_zero(&rr); | |||||
| /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2. | /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2. | ||||
| * This means either x1 == beta*x2 or beta*x1 == x2, where beta is | * This means either x1 == beta*x2 or beta*x1 == x2, where beta is | ||||
| * a nontrivial cube root of one. In either case, an alternate | * a nontrivial cube root of one. In either case, an alternate | ||||
| * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2), | * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2), | ||||
| * so we set R/M equal to this. */ | * so we set R/M equal to this. */ | ||||
| rr_alt = s1; | rr_alt = s1; | ||||
| secp256k1_fe_mul_int(&rr_alt, 2); /* rr = Y1*Z2^3 - Y2*Z1^3 (2) */ | secp256k1_fe_mul_int(&rr_alt, 2); /* rr = Y1*Z2^3 - Y2*Z1^3 (2) */ | ||||
| secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 */ | secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 */ | ||||
| secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); | secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); | ||||
| secp256k1_fe_cmov(&m_alt, &m, !degenerate); | secp256k1_fe_cmov(&m_alt, &m, !degenerate); | ||||
| /* Now Ralt / Malt = lambda and is guaranteed not to be 0/0. | /* Now Ralt / Malt = lambda and is guaranteed not to be Ralt / 0. | ||||
| * From here on out Ralt and Malt represent the numerator | * From here on out Ralt and Malt represent the numerator | ||||
| * and denominator of lambda; R and M represent the explicit | * and denominator of lambda; R and M represent the explicit | ||||
| * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */ | * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */ | ||||
| secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */ | secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */ | ||||
| secp256k1_fe_negate(&q, &t, 2); /* q = -T (3) */ | secp256k1_fe_negate(&q, &t, 2); /* q = -T (3) */ | ||||
| secp256k1_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */ | secp256k1_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */ | ||||
| /* These two lines use the observation that either M == Malt or M == 0, | /* These two lines use the observation that either M == Malt or M == 0, | ||||
| * so M^3 * Malt is either Malt^4 (which is computed by squaring), or | * so M^3 * Malt is either Malt^4 (which is computed by squaring), or | ||||
| * zero (which is "computed" by cmov). So the cost is one squaring | * zero (which is "computed" by cmov). So the cost is one squaring | ||||
| * versus two multiplications. */ | * versus two multiplications. */ | ||||
| secp256k1_fe_sqr(&n, &n); | secp256k1_fe_sqr(&n, &n); | ||||
| secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (2) */ | secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (2) */ | ||||
| secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */ | secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */ | ||||
| secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */ | secp256k1_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */ | ||||
| infinity = secp256k1_fe_normalizes_to_zero(&r->z) & ~a->infinity; | |||||
| secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */ | secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */ | ||||
| r->x = t; /* r->x = X3 = Ralt^2 + Q (2) */ | r->x = t; /* r->x = X3 = Ralt^2 + Q (2) */ | ||||
| secp256k1_fe_mul_int(&t, 2); /* t = 2*X3 (4) */ | secp256k1_fe_mul_int(&t, 2); /* t = 2*X3 (4) */ | ||||
| secp256k1_fe_add(&t, &q); /* t = 2*X3 + Q (5) */ | secp256k1_fe_add(&t, &q); /* t = 2*X3 + Q (5) */ | ||||
| secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */ | secp256k1_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */ | ||||
| secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (3) */ | secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (3) */ | ||||
| secp256k1_fe_negate(&r->y, &t, 3); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (4) */ | secp256k1_fe_negate(&r->y, &t, 3); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (4) */ | ||||
| secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 (3) */ | secp256k1_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 (3) */ | ||||
| /** In case a->infinity == 1, replace r with (b->x, b->y, 1). */ | /* In case a->infinity == 1, replace r with (b->x, b->y, 1). */ | ||||
| secp256k1_fe_cmov(&r->x, &b->x, a->infinity); | secp256k1_fe_cmov(&r->x, &b->x, a->infinity); | ||||
| secp256k1_fe_cmov(&r->y, &b->y, a->infinity); | secp256k1_fe_cmov(&r->y, &b->y, a->infinity); | ||||
| secp256k1_fe_cmov(&r->z, &secp256k1_fe_one, a->infinity); | secp256k1_fe_cmov(&r->z, &secp256k1_fe_one, a->infinity); | ||||
| r->infinity = infinity; | |||||
| /* Set r->infinity if r->z is 0. | |||||
| * | |||||
| * If a->infinity is set, then r->infinity = (r->z == 0) = (1 == 0) = false, | |||||
| * which is correct because the function assumes that b is not infinity. | |||||
| * | |||||
| * Now assume !a->infinity. This implies Z = Z1 != 0. | |||||
| * | |||||
| * Case y1 = -y2: | |||||
| * In this case we could have a = -b, namely if x1 = x2. | |||||
| * We have degenerate = true, r->z = (x1 - x2) * Z. | |||||
| * Then r->infinity = ((x1 - x2)Z == 0) = (x1 == x2) = (a == -b). | |||||
| * | |||||
| * Case y1 != -y2: | |||||
| * In this case, we can't have a = -b. | |||||
| * We have degenerate = false, r->z = (y1 + y2) * Z. | |||||
| * Then r->infinity = ((y1 + y2)Z == 0) = (y1 == -y2) = false. */ | |||||
| r->infinity = secp256k1_fe_normalizes_to_zero(&r->z); | |||||
| } | } | ||||
| static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s) { | static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *s) { | ||||
| /* Operations: 4 mul, 1 sqr */ | /* Operations: 4 mul, 1 sqr */ | ||||
| secp256k1_fe zz; | secp256k1_fe zz; | ||||
| VERIFY_CHECK(!secp256k1_fe_is_zero(s)); | VERIFY_CHECK(!secp256k1_fe_is_zero(s)); | ||||
| secp256k1_fe_sqr(&zz, s); | secp256k1_fe_sqr(&zz, s); | ||||
| secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */ | secp256k1_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */ | ||||
| ▲ Show 20 Lines • Show All 76 Lines • Show Last 20 Lines | |||||