Revert c9ef9420e762 (GH #994)

Marcel Keller reports it broke curve operations

1 files changed, 24 insertions, 487 deletions

diff --git a/ecp.cpp b/ecp.cpp
index f349a86d..643ba70a 100644
--- a/ecp.cpp
+++ b/ecp.cpp
@@ -55,489 +55,6 @@ struct ProjectivePoint
 	Integer x, y, z;

 };

 

-/// \brief Addition and Double functions

-/// \sa <A HREF="https://eprint.iacr.org/2015/1060.pdf">Complete

-///  addition formulas for prime order elliptic curves</A>

-struct AdditionFunction

-{

-	explicit AdditionFunction(const ECP::Field& field,

-		const ECP::FieldElement &a, const ECP::FieldElement &b, ECP::Point &r);

-

-	// Double(P)

-	ECP::Point operator()(const ECP::Point& P) const;

-	// Add(P, Q)

-	ECP::Point operator()(const ECP::Point& P, const ECP::Point& Q) const;

-

-protected:

-	/// \brief Parameters and representation for Addition

-	/// \details Addition and Doubling will use different algorithms,

-	///  depending on the <tt>A</tt> coefficient and the representation

-	///  (Affine or Montgomery with precomputation).

-	enum Alpha {

-		/// \brief Coefficient A is 0

-		A_0 = 1,

-		/// \brief Coefficient A is -3

-		A_3 = 2,

-		/// \brief Coefficient A is arbitrary

-		A_Star = 4,

-		/// \brief Representation is Montgomery

-		A_Montgomery = 8

-	};

-

-	const ECP::Field& field;

-	const ECP::FieldElement &a, &b;

-	ECP::Point &R;

-

-	Alpha m_alpha;

-};

-

-#define X p.x

-#define Y p.y

-#define Z p.z

-

-#define X1 p.x

-#define Y1 p.y

-#define Z1 p.z

-

-#define X2 q.x

-#define Y2 q.y

-#define Z2 q.z

-

-#define X3 r.x

-#define Y3 r.y

-#define Z3 r.z

-

-AdditionFunction::AdditionFunction(const ECP::Field& field,

-	const ECP::FieldElement &a, const ECP::FieldElement &b, ECP::Point &r)

-	: field(field), a(a), b(b), R(r), m_alpha(static_cast<Alpha>(0))

-{

-	if (field.IsMontgomeryRepresentation())

-	{

-		m_alpha = A_Montgomery;

-	}

-	else

-	{

-		if (a == 0)

-		{

-			m_alpha = A_0;

-		}

-		else if (a == -3 || (a - field.GetModulus()) == -3)

-		{

-			m_alpha = A_3;

-		}

-		else

-		{

-			m_alpha = A_Star;

-		}

-	}

-}

-

-ECP::Point AdditionFunction::operator()(const ECP::Point& P) const

-{

-	if (m_alpha == A_3)

-	{

-		// Gyrations attempt to maintain constant-timeness

-		// We need either (P.x, P.y, 1) or (0, 1, 0).

-		const Integer x = P.x * IdentityToInteger(!P.identity);

-		const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);

-		const Integer z = 1 * IdentityToInteger(!P.identity);

-

-		ProjectivePoint p(x, y, z), r;

-

-		ECP::FieldElement t0 = field.Square(X);

-		ECP::FieldElement t1 = field.Square(Y);

-		ECP::FieldElement t2 = field.Square(Z);

-		ECP::FieldElement t3 = field.Multiply(X, Y);

-		t3 = field.Add(t3, t3);

-		Z3 = field.Multiply(X, Z);

-		Z3 = field.Add(Z3, Z3);

-		Y3 = field.Multiply(b, t2);

-		Y3 = field.Subtract(Y3, Z3);

-		X3 = field.Add(Y3, Y3);

-		Y3 = field.Add(X3, Y3);

-		X3 = field.Subtract(t1, Y3);

-		Y3 = field.Add(t1, Y3);

-		Y3 = field.Multiply(X3, Y3);

-		X3 = field.Multiply(X3, t3);

-		t3 = field.Add(t2, t2);

-		t2 = field.Add(t2, t3);

-		Z3 = field.Multiply(b, Z3);

-		Z3 = field.Subtract(Z3, t2);

-		Z3 = field.Subtract(Z3, t0);

-		t3 = field.Add(Z3, Z3);

-		Z3 = field.Add(Z3, t3);

-		t3 = field.Add(t0, t0);

-		t0 = field.Add(t3, t0);

-		t0 = field.Subtract(t0, t2);

-		t0 = field.Multiply(t0, Z3);

-		Y3 = field.Add(Y3, t0);

-		t0 = field.Multiply(Y, Z);

-		t0 = field.Add(t0, t0);

-		Z3 = field.Multiply(t0, Z3);

-		X3 = field.Subtract(X3, Z3);

-		Z3 = field.Multiply(t0, t1);

-		Z3 = field.Add(Z3, Z3);

-		Z3 = field.Add(Z3, Z3);

-

-		const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);

-		X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);

-

-		// More gyrations

-		R.x = X3*Z3.NotZero();

-		R.y = Y3*Z3.NotZero();

-		R.identity = Z3.IsZero();

-

-		return R;

-	}

-	else if (m_alpha == A_0)

-	{

-		// Gyrations attempt to maintain constant-timeness

-		// We need either (P.x, P.y, 1) or (0, 1, 0).

-		const Integer x = P.x * IdentityToInteger(!P.identity);

-		const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);

-		const Integer z = 1 * IdentityToInteger(!P.identity);

-

-		ProjectivePoint p(x, y, z), r;

-		const ECP::FieldElement b3 = field.Multiply(b, 3);

-

-		ECP::FieldElement t0 = field.Square(Y);

-		Z3 = field.Add(t0, t0);

-		Z3 = field.Add(Z3, Z3);

-		Z3 = field.Add(Z3, Z3);

-		ECP::FieldElement t1 = field.Add(Y, Z);

-		ECP::FieldElement t2 = field.Square(Z);

-		t2 = field.Multiply(b3, t2);

-		X3 = field.Multiply(t2, Z3);

-		Y3 = field.Add(t0, t2);

-		Z3 = field.Multiply(t1, Z3);

-		t1 = field.Add(t2, t2);

-		t2 = field.Add(t1, t2);

-		t0 = field.Subtract(t0, t2);

-		Y3 = field.Multiply(t0, Y3);

-		Y3 = field.Add(X3, Y3);

-		t1 = field.Multiply(X, Y);

-		X3 = field.Multiply(t0, t1);

-		X3 = field.Add(X3, X3);

-

-		const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);

-		X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);

-

-		// More gyrations

-		R.x = X3*Z3.NotZero();

-		R.y = Y3*Z3.NotZero();

-		R.identity = Z3.IsZero();

-

-		return R;

-	}

-#if 0

-	// Code path disabled at the moment due to https://github.com/weidai11/cryptopp/issues/878

-	else if (m_alpha == A_Star)

-	{

-		// Gyrations attempt to maintain constant-timeness

-		// We need either (P.x, P.y, 1) or (0, 1, 0).

-		const Integer x = P.x * IdentityToInteger(!P.identity);

-		const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);

-		const Integer z = 1 * IdentityToInteger(!P.identity);

-

-		ProjectivePoint p(x, y, z), r;

-		const ECP::FieldElement b3 = field.Multiply(b, 3);

-

-		ECP::FieldElement t0 = field.Square(Y);

-		Z3 = field.Add(t0, t0);

-		Z3 = field.Add(Z3, Z3);

-		Z3 = field.Add(Z3, Z3);

-		ECP::FieldElement t1 = field.Add(Y, Z);

-		ECP::FieldElement t2 = field.Square(Z);

-		t2 = field.Multiply(b3, t2);

-		X3 = field.Multiply(t2, Z3);

-		Y3 = field.Add(t0, t2);

-		Z3 = field.Multiply(t1, Z3);

-		t1 = field.Add(t2, t2);

-		t2 = field.Add(t1, t2);

-		t0 = field.Subtract(t0, t2);

-		Y3 = field.Multiply(t0, Y3);

-		Y3 = field.Add(X3, Y3);

-		t1 = field.Multiply(X, Y);

-		X3 = field.Multiply(t0, t1);

-		X3 = field.Add(X3, X3);

-

-		const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);

-		X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);

-

-		// More gyrations

-		R.x = X3*Z3.NotZero();

-		R.y = Y3*Z3.NotZero();

-		R.identity = Z3.IsZero();

-

-		return R;

-	}

-#endif

-	else  // A_Montgomery

-	{

-		// More gyrations

-		bool identity = !!(P.identity + (P.y == field.Identity()));

-

-		ECP::FieldElement t = field.Square(P.x);

-		t = field.Add(field.Add(field.Double(t), t), a);

-		t = field.Divide(t, field.Double(P.y));

-		ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), P.x);

-		R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);

-		R.x.swap(x);

-

-		// More gyrations

-		R.x *= IdentityToInteger(!identity);

-		R.y *= IdentityToInteger(!identity);

-		R.identity = identity;

-

-		return R;

-	}

-}

-

-ECP::Point AdditionFunction::operator()(const ECP::Point& P, const ECP::Point& Q) const

-{

-	if (m_alpha == A_3)

-	{

-		// Gyrations attempt to maintain constant-timeness

-		// We need either (P.x, P.y, 1) or (0, 1, 0).

-		const Integer x1 = P.x * IdentityToInteger(!P.identity);

-		const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);

-		const Integer z1 = 1 * IdentityToInteger(!P.identity);

-

-		const Integer x2 = Q.x * IdentityToInteger(!Q.identity);

-		const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);

-		const Integer z2 = 1 * IdentityToInteger(!Q.identity);

-

-		ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;

-

-		ECP::FieldElement t0 = field.Multiply(X1, X2);

-		ECP::FieldElement t1 = field.Multiply(Y1, Y2);

-		ECP::FieldElement t2 = field.Multiply(Z1, Z2);

-		ECP::FieldElement t3 = field.Add(X1, Y1);

-		ECP::FieldElement t4 = field.Add(X2, Y2);

-		t3 = field.Multiply(t3, t4);

-		t4 = field.Add(t0, t1);

-		t3 = field.Subtract(t3, t4);

-		t4 = field.Add(Y1, Z1);

-		X3 = field.Add(Y2, Z2);

-		t4 = field.Multiply(t4, X3);

-		X3 = field.Add(t1, t2);

-		t4 = field.Subtract(t4, X3);

-		X3 = field.Add(X1, Z1);

-		Y3 = field.Add(X2, Z2);

-		X3 = field.Multiply(X3, Y3);

-		Y3 = field.Add(t0, t2);

-		Y3 = field.Subtract(X3, Y3);

-		Z3 = field.Multiply(b, t2);

-		X3 = field.Subtract(Y3, Z3);

-		Z3 = field.Add(X3, X3);

-		X3 = field.Add(X3, Z3);

-		Z3 = field.Subtract(t1, X3);

-		X3 = field.Add(t1, X3);

-		Y3 = field.Multiply(b, Y3);

-		t1 = field.Add(t2, t2);

-		t2 = field.Add(t1, t2);

-		Y3 = field.Subtract(Y3, t2);

-		Y3 = field.Subtract(Y3, t0);

-		t1 = field.Add(Y3, Y3);

-		Y3 = field.Add(t1, Y3);

-		t1 = field.Add(t0, t0);

-		t0 = field.Add(t1, t0);

-		t0 = field.Subtract(t0, t2);

-		t1 = field.Multiply(t4, Y3);

-		t2 = field.Multiply(t0, Y3);

-		Y3 = field.Multiply(X3, Z3);

-		Y3 = field.Add(Y3, t2);

-		X3 = field.Multiply(t3, X3);

-		X3 = field.Subtract(X3, t1);

-		Z3 = field.Multiply(t4, Z3);

-		t1 = field.Multiply(t3, t0);

-		Z3 = field.Add(Z3, t1);

-

-		const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);

-		X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);

-

-		// More gyrations

-		R.x = X3*Z3.NotZero();

-		R.y = Y3*Z3.NotZero();

-		R.identity = Z3.IsZero();

-

-		return R;

-	}

-	else if (m_alpha == A_0)

-	{

-		// Gyrations attempt to maintain constant-timeness

-		// We need either (P.x, P.y, 1) or (0, 1, 0).

-		const Integer x1 = P.x * IdentityToInteger(!P.identity);

-		const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);

-		const Integer z1 = 1 * IdentityToInteger(!P.identity);

-

-		const Integer x2 = Q.x * IdentityToInteger(!Q.identity);

-		const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);

-		const Integer z2 = 1 * IdentityToInteger(!Q.identity);

-

-		ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;

-		const ECP::FieldElement b3 = field.Multiply(b, 3);

-

-		ECP::FieldElement t0 = field.Square(Y);

-		Z3 = field.Add(t0, t0);

-		Z3 = field.Add(Z3, Z3);

-		Z3 = field.Add(Z3, Z3);

-		ECP::FieldElement t1 = field.Add(Y, Z);

-		ECP::FieldElement t2 = field.Square(Z);

-		t2 = field.Multiply(b3, t2);

-		X3 = field.Multiply(t2, Z3);

-		Y3 = field.Add(t0, t2);

-		Z3 = field.Multiply(t1, Z3);

-		t1 = field.Add(t2, t2);

-		t2 = field.Add(t1, t2);

-		t0 = field.Subtract(t0, t2);

-		Y3 = field.Multiply(t0, Y3);

-		Y3 = field.Add(X3, Y3);

-		t1 = field.Multiply(X, Y);

-		X3 = field.Multiply(t0, t1);

-		X3 = field.Add(X3, X3);

-

-		const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);

-		X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);

-

-		// More gyrations

-		R.x = X3*Z3.NotZero();

-		R.y = Y3*Z3.NotZero();

-		R.identity = Z3.IsZero();

-

-		return R;

-	}

-#if 0

-	// Code path disabled at the moment due to https://github.com/weidai11/cryptopp/issues/878

-	else if (m_alpha == A_Star)

-	{

-		// Gyrations attempt to maintain constant-timeness

-		// We need either (P.x, P.y, 1) or (0, 1, 0).

-		const Integer x1 = P.x * IdentityToInteger(!P.identity);

-		const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);

-		const Integer z1 = 1 * IdentityToInteger(!P.identity);

-

-		const Integer x2 = Q.x * IdentityToInteger(!Q.identity);

-		const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);

-		const Integer z2 = 1 * IdentityToInteger(!Q.identity);

-

-		ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;

-		const ECP::FieldElement b3 = field.Multiply(b, 3);

-

-		ECP::FieldElement t0 = field.Multiply(X1, X2);

-		ECP::FieldElement t1 = field.Multiply(Y1, Y2);

-		ECP::FieldElement t2 = field.Multiply(Z1, Z2);

-		ECP::FieldElement t3 = field.Add(X1, Y1);

-		ECP::FieldElement t4 = field.Add(X2, Y2);

-		t3 = field.Multiply(t3, t4);

-		t4 = field.Add(t0, t1);

-		t3 = field.Subtract(t3, t4);

-		t4 = field.Add(X1, Z1);

-		ECP::FieldElement t5 = field.Add(X2, Z2);

-		t4 = field.Multiply(t4, t5);

-		t5 = field.Add(t0, t2);

-		t4 = field.Subtract(t4, t5);

-		t5 = field.Add(Y1, Z1);

-		X3 = field.Add(Y2, Z2);

-		t5 = field.Multiply(t5, X3);

-		X3 = field.Add(t1, t2);

-		t5 = field.Subtract(t5, X3);

-		Z3 = field.Multiply(a, t4);

-		X3 = field.Multiply(b3, t2);

-		Z3 = field.Add(X3, Z3);

-		X3 = field.Subtract(t1, Z3);

-		Z3 = field.Add(t1, Z3);

-		Y3 = field.Multiply(X3, Z3);

-		t1 = field.Add(t0, t0);

-		t1 = field.Add(t1, t0);

-		t2 = field.Multiply(a, t2);

-		t4 = field.Multiply(b3, t4);

-		t1 = field.Add(t1, t2);

-		t2 = field.Subtract(t0, t2);

-		t2 = field.Multiply(a, t2);

-		t4 = field.Add(t4, t2);

-		t0 = field.Multiply(t1, t4);

-		Y3 = field.Add(Y3, t0);

-		t0 = field.Multiply(t5, t4);

-		X3 = field.Multiply(t3, X3);

-		X3 = field.Subtract(X3, t0);

-		t0 = field.Multiply(t3, t1);

-		Z3 = field.Multiply(t5, Z3);

-		Z3 = field.Add(Z3, t0);

-

-		const ECP::FieldElement inv = field.MultiplicativeInverse(Z3.IsZero() ? Integer::One() : Z3);

-		X3 = field.Multiply(X3, inv); Y3 = field.Multiply(Y3, inv);

-

-		// More gyrations

-		R.x = X3*Z3.NotZero();

-		R.y = Y3*Z3.NotZero();

-		R.identity = Z3.IsZero();

-

-		return R;

-	}

-#endif

-	else  // A_Montgomery

-	{

-		// More gyrations

-		bool return_Q = P.identity;

-		bool return_P = Q.identity;

-		bool double_P = field.Equal(P.x, Q.x) && field.Equal(P.y, Q.y);

-		bool identity = field.Equal(P.x, Q.x) && !field.Equal(P.y, Q.y);

-

-		// This code taken from Double(P) for below

-		identity = !!((double_P * (P.identity + (P.y == field.Identity()))) + identity);

-

-		ECP::Point S = R;

-		if (double_P)

-		{

-			// This code taken from Double(P)

-			ECP::FieldElement t = field.Square(P.x);

-			t = field.Add(field.Add(field.Double(t), t), a);

-			t = field.Divide(t, field.Double(P.y));

-			ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), P.x);

-			R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);

-			R.x.swap(x);

-		}

-		else

-		{

-			// Original Add(P,Q) code

-			ECP::FieldElement t = field.Subtract(Q.y, P.y);

-			t = field.Divide(t, field.Subtract(Q.x, P.x));

-			ECP::FieldElement x = field.Subtract(field.Subtract(field.Square(t), P.x), Q.x);

-			R.y = field.Subtract(field.Multiply(t, field.Subtract(P.x, x)), P.y);

-			R.x.swap(x);

-		}

-

-		// More gyrations

-		R.x = R.x * IdentityToInteger(!identity);

-		R.y = R.y * IdentityToInteger(!identity);

-		R.identity = identity;

-

-		if (return_Q)

-			return (R = S), Q;

-		else if (return_P)

-			return (R = S), P;

-		else

-			return (S = R), R;

-	}

-}

-

-#undef X

-#undef Y

-#undef Z

-

-#undef X1

-#undef Y1

-#undef Z1

-

-#undef X2

-#undef Y2

-#undef Z2

-

-#undef X3

-#undef Y3

-#undef Z3

-

 ANONYMOUS_NAMESPACE_END

 

 NAMESPACE_BEGIN(CryptoPP)

@@ -742,14 +259,34 @@ const ECP::Point& ECP::Inverse(const Point &P) const
 

 const ECP::Point& ECP::Add(const Point &P, const Point &Q) const

 {

-	AdditionFunction add(GetField(), m_a, m_b, m_R);

-	return (m_R = add(P, Q));

+	if (P.identity) return Q;

+	if (Q.identity) return P;

+	if (GetField().Equal(P.x, Q.x))

+		return GetField().Equal(P.y, Q.y) ? Double(P) : Identity();

+

+	FieldElement t = GetField().Subtract(Q.y, P.y);

+	t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));

+	FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), Q.x);

+	m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);

+

+	m_R.x.swap(x);

+	m_R.identity = false;

+	return m_R;

 }

 

 const ECP::Point& ECP::Double(const Point &P) const

 {

-	AdditionFunction add(GetField(), m_a, m_b, m_R);

-	return (m_R = add(P));

+	if (P.identity || P.y==GetField().Identity()) return Identity();

+

+	FieldElement t = GetField().Square(P.x);

+	t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);

+	t = GetField().Divide(t, GetField().Double(P.y));

+	FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), P.x);

+	m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);

+

+	m_R.x.swap(x);

+	m_R.identity = false;

+	return m_R;

 }

 

 template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end)