Added Montgomery support

This check-in enables support for elliptic curves over prime fields
using the Montgomery equation. Support for Edwards curves will follow as
soon as all bugs are eliminated.

9 files changed, 750 insertions, 0 deletions

diff --git a/eccrypto.cpp b/eccrypto.cpp
index 3ac4f194..3e39d92f 100644
--- a/eccrypto.cpp
+++ b/eccrypto.cpp
@@ -122,6 +122,24 @@ template<> struct EcRecommendedParameters<ECP>
 	unsigned int h;

 };

 

+template<> struct EcRecommendedParameters<ECPM>

+{

+	EcRecommendedParameters(const OID &oid, const char *p, const char *A, const char *B, const char *g, const char *n, unsigned int h)

+		: oid(oid), p(p), A(A), B(B), g(g), n(n), h(h) {}

+	ECPM *NewEC() const

+	{

+		StringSource ssP(p, true, new HexDecoder);

+		StringSource ssA(A, true, new HexDecoder);

+		StringSource ssB(B, true, new HexDecoder);

+		return new ECPM(Integer(ssP, (size_t)ssP.MaxRetrievable()), ECPM::FieldElement(ssA, (size_t)ssA.MaxRetrievable()), ECPM::FieldElement(ssB, (size_t)ssB.MaxRetrievable()));

+	};

+

+	OID oid;

+	const char *p;

+	const char *A, *B, *g, *n;

+	unsigned int h;

+};

+

 struct OIDLessThan

 {

 	template <typename T>

@@ -430,6 +448,58 @@ static void GetRecommendedParameters(const EcRecommendedParameters<ECP> *&begin,
 	end = rec + sizeof(rec)/sizeof(rec[0]);

 }

 

+static void GetRecommendedParameters(const EcRecommendedParameters<ECPM> *&begin, const EcRecommendedParameters<ECPM> *&end)

+{

+	// this array must be sorted by OID

+	static const EcRecommendedParameters<ECPM> rec[] =

+	{

+		EcRecommendedParameters<ECPM>(ASN1::cryptoppM221(),

+			"1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD",

+			"0000000000000000000000000000000000000000000000000001C93A",

+			"00000000000000000000000000000000000000000000000000000001",

+			"04000000000000000000000000000000000000000000000000000000040F7ACDD2A4939571D1CEF14ECA37C228E61DBFF10707DC6C08C5056D",

+			"040000000000000000000000000015A08ED730E8A2F77F005042605B",

+			8),

+		EcRecommendedParameters<ECPM>(ASN1::cryptoppM383(),

+			"7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF45",

+			"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001F82FE",

+			"000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001",

+			"0400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000C1EC7ED04AAF834AF310E304B2DA0F328E7C165F0E8988ABD3992861290F617AA1F1B2E7D0B6E332E969991B62555E77E",

+			"10000000000000000000000000000000000000000000000006C79673AC36BA6E7A32576F7B1B249E46BBC225BE9071D7",

+			8),

+		EcRecommendedParameters<ECPM>(ASN1::cryptoppM511(),

+			"7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF45",

+			"00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000081806",

+			"00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001",

+			"04000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000052fbdc0ad8530803d28fdbad354bb488d32399ac1cf8f6e01ee3f96389b90c809422b9429e8a43dbf49308ac4455940abe9f1dbca542093a895e30a64af056fa5",

+			"100000000000000000000000000000000000000000000000000000000000000017B5FEFF30C7F5677AB2AEEBD13779A2AC125042A6AA10BFA54C15BAB76BAF1B",

+			8),

+		EcRecommendedParameters<ECPM>(ASN1::cryptoppCurve383187(),

+			"7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF45",

+			"000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000038251",

+			"000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001",

+			"040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000051EEBE07DC1871896732B12D5504A32370471965C7A11F2C89865F855AB3CBD7C224E3620C31AF3370788457DD5CE46DF",

+			"1000000000000000000000000000000000000000000000000e85a85287a1488acd41ae84b2b7030446f72088b00a0e21",

+			8),

+		EcRecommendedParameters<ECPM>(ASN1::ietfCurve25519(),

+			"7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",

+			"0000000000000000000000000000000000000000000000000000000000076D06",

+			"0000000000000000000000000000000000000000000000000000000000000001",

+			"04000000000000000000000000000000000000000000000000000000000000000920AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9",

+			"1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed",

+			8),

+		EcRecommendedParameters<ECPM>(ASN1::ietfCurve448(),

+			"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF",

+			"00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000262A6",

+			"0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001",

+			"0400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000057D235D1295F5B1F66C98AB6E58326FCECBAE5D34F55545D060F75DC28DF3F6EDB8027E2346430D211312C4B150677AF76FD7223D457B5B1A",

+			"3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7CCA23E9C44EDB49AED63690216CC2728DC58F552378C292AB5844F3",

+			4),

+	};

+	begin = rec;

+	end = rec + sizeof(rec) / sizeof(rec[0]);

+}

+

 template <class EC> OID DL_GroupParameters_EC<EC>::GetNextRecommendedParametersOID(const OID &oid)

 {

 	const EcRecommendedParameters<EllipticCurve> *begin, *end;

diff --git a/eccrypto.h b/eccrypto.h
index a3d15e95..3adbbf9c 100644
--- a/eccrypto.h
+++ b/eccrypto.h
@@ -319,18 +319,24 @@ NAMESPACE_BEGIN(CryptoPP)
 

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_GroupParameters_EC<ECP>;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_GroupParameters_EC<EC2N>;

+CRYPTOPP_DLL_TEMPLATE_CLASS DL_GroupParameters_EC<ECPM>

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PublicKeyImpl<DL_GroupParameters_EC<ECP> >;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PublicKeyImpl<DL_GroupParameters_EC<EC2N> >;

+CRYPTOPP_DLL_TEMPLATE_CLASS DL_PublicKeyImpl<DL_GroupParameters_EC<ECPM> >;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PublicKey_EC<ECP>;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PublicKey_EC<EC2N>;

+CRYPTOPP_DLL_TEMPLATE_CLASS DL_PublicKey_EC<ECPM>;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKeyImpl<DL_GroupParameters_EC<ECP> >;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKeyImpl<DL_GroupParameters_EC<EC2N> >;

+CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKeyImpl<DL_GroupParameters_EC<ECPM> >;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKey_EC<ECP>;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKey_EC<EC2N>;

+CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKey_EC<ECPM>;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_Algorithm_GDSA<ECP::Point>;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_Algorithm_GDSA<EC2N::Point>;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKey_WithSignaturePairwiseConsistencyTest<DL_PrivateKey_EC<ECP>, ECDSA<ECP, SHA256> >;

 CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKey_WithSignaturePairwiseConsistencyTest<DL_PrivateKey_EC<EC2N>, ECDSA<EC2N, SHA256> >;

+CRYPTOPP_DLL_TEMPLATE_CLASS DL_PrivateKey_WithSignaturePairwiseConsistencyTest<DL_PrivateKey_EC<ECPM>, ECDSA<ECPM, SHA256> >;

 

 NAMESPACE_END

 

diff --git a/ecpm.cpp b/ecpm.cpp
new file mode 100644
index 00000000..163308de
--- /dev/null
+++ b/ecpm.cpp
@@ -0,0 +1,396 @@
+// ecpm.cpp - written and placed in public domain by Jean-Pierre Muench. Copyright assigned to the Crypto++ project.
+
+#include "pch.h"
+
+#ifndef CRYPTOPP_IMPORTS
+
+#include "ecp.h"
+#include "ecpm.h"
+#include "asn.h"
+#include "integer.h"
+#include "nbtheory.h"
+#include "modarith.h"
+#include "filters.h"
+#include "algebra.cpp"
+
+NAMESPACE_BEGIN(CryptoPP)
+
+ANONYMOUS_NAMESPACE_BEGIN
+static inline ECP::Point ToMontgomery(const ModularArithmetic &mr, const ECP::Point &P) // straight from ecp.cpp
+{
+	return P.identity ? P : ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
+}
+
+static inline ECP::Point FromMontgomery(const ModularArithmetic &mr, const ECP::Point &P) // straight from ecp.cpp
+{
+	return P.identity ? P : ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
+}
+static inline ECP* GenerateWeierstrassCurve(const ECPM& MontgomeryCurve)
+{
+	const Integer& A = MontgomeryCurve.GetA();
+	const Integer& B = MontgomeryCurve.GetB();
+	const ModularArithmetic& Field = MontgomeryCurve.GetField();
+
+	// now construct the equivalent Weierstrass curve
+	// refer to https://crypto.stackexchange.com/q/27842 for the details
+	// use m_FieldPtr to ensure encoding (eventual Montgomery Representation) is handled correctly
+	//the transformations also appear independently on http ://safecurves.cr.yp.to/equation.html
+
+	// a = (3-A)/(3B^2)
+	Integer aWeierstrass = Field.Subtract(3, Field.Square(A)); // a = 3 - A
+	aWeierstrass = Field.Divide(aWeierstrass, Field.Multiply(3, Field.Square(B))); // a = a / (3B^2)
+	// b = (2A^3-9A) / (27 B^3)
+	Integer bWeierstrass = Field.Multiply(A, Field.Subtract(Field.Multiply(2, Field.Square(A)), 9)); // b = A(2A^2-9)
+	bWeierstrass = Field.Divide(bWeierstrass, Field.Multiply(27, Field.Exponentiate(B, 3))); // b = b / (27 B^3)
+
+	return new ECP(MontgomeryCurve.GetField().GetModulus(), aWeierstrass, bWeierstrass);
+}
+NAMESPACE_END
+
+ECPM::ECPM(const Integer &modulus, const FieldElement &A, const FieldElement &B): 
+	m_fieldPtr(new Field(modulus))
+{
+	// store A and B for later use
+	m_A = A.IsNegative() ? (A + modulus) : A;// straight from ecp.cpp
+	m_B = B.IsNegative() ? (B + modulus) : B;// straight from ecp.cpp
+
+	m_ComputeEngine.reset(GenerateWeierstrassCurve(*this));
+
+	// to speed up the conversions
+	m_AThirds = m_fieldPtr->Divide(m_A, 3);
+	m_BInv = m_fieldPtr->MultiplicativeInverse(m_B);
+}
+
+// straight adaption from ecp.cpp
+ECPM::ECPM(const ECPM &ecpm, bool convertToMontgomeryRepresentation)
+{
+	if (convertToMontgomeryRepresentation && !ecpm.GetField().IsMontgomeryRepresentation())
+	{
+		m_fieldPtr.reset(new MontgomeryRepresentation(ecpm.GetField().GetModulus()));
+		m_ComputeEngine.reset(new ECP(*ecpm.m_ComputeEngine.get(),convertToMontgomeryRepresentation));
+		m_A = GetField().ConvertIn(ecpm.m_A);
+		m_B = GetField().ConvertIn(ecpm.m_B);
+		m_AThirds = GetField().ConvertIn(ecpm.m_AThirds);
+		m_BInv = GetField().ConvertIn(ecpm.m_BInv);
+	}
+	else
+		operator=(ecpm);
+}
+
+ECPM::ECPM(BufferedTransformation &bt)
+	: m_fieldPtr(new Field(bt))
+{
+	BERSequenceDecoder seq(bt);
+	GetField().BERDecodeElement(seq, m_A);
+	GetField().BERDecodeElement(seq, m_B);
+	// skip optional seed
+	if (!seq.EndReached())
+	{
+		SecByteBlock seed;
+		unsigned int unused;
+		BERDecodeBitString(seq, seed, unused);
+	}
+	seq.MessageEnd();
+
+	m_ComputeEngine.reset(GenerateWeierstrassCurve(*this));
+
+	m_AThirds = m_fieldPtr->Divide(m_A, 3);
+	m_BInv = m_fieldPtr->MultiplicativeInverse(m_B);
+}
+
+// straight adaption from ecp.cpp
+void ECPM::DEREncode(BufferedTransformation &bt) const
+{
+	GetField().DEREncode(bt);
+	DERSequenceEncoder seq(bt);
+	GetField().DEREncodeElement(seq, m_A);
+	GetField().DEREncodeElement(seq, m_B);
+	seq.MessageEnd();
+}
+
+// straight adaption from ecp.cpp
+bool ECPM::DecodePoint(ECPM::Point &P, const byte *encodedPoint, size_t encodedPointLen) const
+{
+	StringStore store(encodedPoint, encodedPointLen);
+	return DecodePoint(P, store, encodedPointLen);
+}
+
+// straight adaption from ecp.cpp
+bool ECPM::DecodePoint(ECPM::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
+{
+	byte type;
+	if (encodedPointLen < 1 || !bt.Get(type))
+		return false;
+
+	switch (type)
+	{
+	case 0:
+		P.identity = true;
+		return true;
+	case 2:
+	case 3:
+	{
+		if (encodedPointLen != EncodedPointSize(true))
+			return false;
+
+		Integer p = FieldSize();
+
+		P.identity = false;
+		P.x.Decode(bt, GetField().MaxElementByteLength());
+		// curve is: By^2=x^3+Ax^2+x <=> y=sqrt(x/B(x(A+x)+1)
+		P.y = (m_BInv * P.x *(P.x * (P.x + m_A) + Integer::One()))%p;
+
+		if (Jacobi(P.y, p) != 1)
+			return false;
+
+		P.y = ModularSquareRoot(P.y, p);
+
+		if ((type & 1) != P.y.GetBit(0))
+			P.y = p - P.y;
+
+		return true;
+	}
+	case 4:
+	{
+		if (encodedPointLen != EncodedPointSize(false))
+			return false;
+
+		unsigned int len = GetField().MaxElementByteLength();
+		P.identity = false;
+		P.x.Decode(bt, len);
+		P.y.Decode(bt, len);
+		return true;
+	}
+	default:
+		return false;
+	}
+}
+
+// straight adaption from ecp.cpp
+void ECPM::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
+{
+	if (P.identity)
+		NullStore().TransferTo(bt, EncodedPointSize(compressed));
+	else if (compressed)
+	{
+		bt.Put(2 + P.y.GetBit(0));
+		P.x.Encode(bt, GetField().MaxElementByteLength());
+	}
+	else
+	{
+		unsigned int len = GetField().MaxElementByteLength();
+		bt.Put(4);	// uncompressed
+		P.x.Encode(bt, len);
+		P.y.Encode(bt, len);
+	}
+}
+
+// straight adaption from ecp.cpp
+void ECPM::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
+{
+	ArraySink sink(encodedPoint, EncodedPointSize(compressed));
+	EncodePoint(sink, P, compressed);
+	assert(sink.TotalPutLength() == EncodedPointSize(compressed));
+}
+
+// straight adaption from ecp.cpp
+ECPM::Point ECPM::BERDecodePoint(BufferedTransformation &bt) const
+{
+	SecByteBlock str;
+	BERDecodeOctetString(bt, str);
+	Point P;
+	if (!DecodePoint(P, str, str.size()))
+		BERDecodeError();
+	return P;
+}
+
+// straight adaption from ecp.cpp
+void ECPM::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
+{
+	SecByteBlock str(EncodedPointSize(compressed));
+	EncodePoint(str, P, compressed);
+	DEREncodeOctetString(bt, str);
+}
+
+// straight adaption from ecp.cpp
+bool ECPM::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
+{
+	Integer p = FieldSize();
+
+	bool pass = p.IsOdd();
+	pass = pass && !m_A.IsNegative() && m_A<p && !m_B.IsNegative() && m_B<p;
+
+	if (level >= 1)
+		pass = pass && ((m_B * (m_A * m_A - 4)) % p).IsPositive();
+
+	if (level >= 2)
+		pass = pass && VerifyPrime(rng, p);
+
+	return pass;
+}
+
+// straight adaption from ecp.cpp
+bool ECPM::VerifyPoint(const Point &P) const
+{
+	const FieldElement &x = P.x, &y = P.y;
+	Integer p = FieldSize();
+
+	// use the field arithmetic here, in case our data is in Montgomery form
+	// ecp.cpp does this with plain integer arithmetic -> will fail if montgomery representation is on, but was never called when montgomery representation was on
+	const FieldElement IsOnCurve = m_fieldPtr->Subtract(m_fieldPtr->Multiply(x,(m_fieldPtr->Add(1,m_fieldPtr->Multiply(x,(m_fieldPtr->Add(m_A,x)))))),m_fieldPtr->Multiply(m_B,m_fieldPtr->Square(y)));
+
+	return P.identity ||
+		(!x.IsNegative() && x<p && !y.IsNegative() && y<p
+			&& !(IsOnCurve));
+	// By^2=x^3+Ax^2+x <=> 0 == x(1+x(A+x))-By^2
+}
+
+// straight adaption from ecp.cpp
+bool ECPM::Equal(const Point &P, const Point &Q) const
+{
+	if (P.identity && Q.identity)
+		return true;
+
+	if (P.identity && !Q.identity)
+		return false;
+
+	if (!P.identity && Q.identity)
+		return false;
+
+	return (GetField().Equal(P.x, Q.x) && GetField().Equal(P.y, Q.y));
+}
+
+// straight adaption from ecp.cpp
+const ECPM::Point& ECPM::Identity() const
+{
+	return Singleton<Point>().Ref();
+}
+
+// straight adaption from ecp.cpp
+const ECPM::Point& ECPM::Inverse(const Point &P) const
+{
+	if (P.identity)
+		return P;
+	else
+	{
+		m_R.identity = false;
+		m_R.x = P.x;
+		m_R.y = GetField().Inverse(P.y);
+		return m_R;
+	}
+}
+
+// straight adaption from ecp.cpp
+const ECPM::Point& ECPM::Add(const Point &P, const Point &Q) const
+{
+	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 = y_Q - y_P
+	t = GetField().Divide(t, GetField().Subtract(Q.x, P.x)); // t = (y_Q - y_P) / (x_Q - x_P)
+	FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Subtract(GetField().Multiply(m_B,GetField().Square(t)), P.x), Q.x),m_A); // x = B*t^2-x_P-x_Q-A
+	m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y); // y = t * (x_P - x) - y_P
+
+	m_R.x.swap(x);
+	m_R.identity = false;
+	return m_R;
+}
+
+// straight adaption from ecp.cpp
+const ECPM::Point& ECPM::Double(const Point &P) const
+{
+	if (P.identity || P.y == GetField().Identity()) return Identity();
+
+	FieldElement t = GetField().Add(GetField().Double(P.x), P.x);// t = 2x_P + x_P = 3x_P 
+	t = GetField().Add(GetField().Multiply(P.x,GetField().Add(t,GetField().Double(m_A))), GetField().ConvertIn(1)); // x_P * ( t + 2 * A)+1
+	FieldElement h1= GetField().Multiply(t, m_BInv), h2= GetField().Double(P.y); // put this in two steps or it fails somehow otherwise
+	t = GetField().Divide(h1, h2); // t = (x_P(3x_P + 2A)+1)/(2B*y_P)
+	FieldElement& x = m_R.x;
+	x = GetField().Multiply(m_B, GetField().Square(t)); // put this in two steps or it fails somehow otherwise
+	x = GetField().Subtract(GetField().Subtract(x, GetField().Double(P.x)), m_A); // x = B * t^2 - A -  x_1 - x_2
+	m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y); // t (x_P - x) -y_P
+
+	m_R.identity = false;
+	return m_R;
+}
+
+// straight adaption from ecp.cpp
+ECPM::Point ECPM::ScalarMultiply(const Point &P, const Integer &k) const
+{
+	Element result;
+	if (k.BitCount() <= 5)
+		AbstractGroup<ECPPoint>::SimultaneousMultiply(&result, P, &k, 1);
+	else
+		ECPM::SimultaneousMultiply(&result, P, &k, 1);
+	
+	return result;
+}
+
+// this is probably the cause of the issue 
+void ECPM::SimultaneousMultiply(ECPM::Point *results, const ECPM::Point &P, const Integer *expBegin, unsigned int expCount) const
+{
+	Point ConvertedBase = MontgomeryToWeierstrass(P);
+	// let the compute engine do its optimized work
+	m_ComputeEngine->SimultaneousMultiply(results, ConvertedBase, expBegin, expCount);
+
+	// fetch the results and convert them back to our preferred form
+	for (unsigned int i = 0; i < expCount; ++i)
+		results[i] = WeierstrassToMontgomery(results[i]);
+
+	return;
+
+	// implement Montgomery ladder below
+}
+
+// straight adaption from ecp.cpp
+ECPM::Point ECPM::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
+{
+	if (!GetField().IsMontgomeryRepresentation())
+	{
+		ECPM ecpmr(*this, true);
+		const ModularArithmetic &mr = ecpmr.GetField();
+		return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
+	}
+	else
+		return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
+}
+
+// added as ECP doesn't offer a Clone() function which is required for assignment
+void ECPM::operator=(const ECPM& rhs)
+{
+	m_A = rhs.m_A;
+	m_AThirds = rhs.m_AThirds;
+	m_B = rhs.m_B;
+	m_BInv = rhs.m_BInv;
+	m_fieldPtr = rhs.m_fieldPtr->Clone();
+	m_ComputeEngine.reset(new ECP(*rhs.m_ComputeEngine,rhs.m_ComputeEngine->GetField().IsMontgomeryRepresentation()));
+}
+
+// converts weierstrass points to montgomery points
+// it can be checked at https://crypto.stackexchange.com/q/27842 and http://safecurves.cr.yp.to/equation.html
+inline ECPM::Point ECPM::WeierstrassToMontgomery(const Point& In) const
+{
+	// (x,y) -> (Bx-A/3,By)
+	ECPPoint Out;
+	Out.identity = In.identity;
+	Out.x = GetField().Subtract(m_fieldPtr->Multiply(m_B,In.x),m_AThirds);
+	Out.y = GetField().Multiply(In.y,m_B);
+	return Out;
+}
+
+// converts weierstrass points to montgomery points, the math *should* be right
+inline ECPM::Point ECPM::MontgomeryToWeierstrass(const Point& In) const
+{
+	// (x,y) -> ((x+A/3)/B,y/B)
+	ECPPoint Out;
+	Out.identity = In.identity;
+	Out.x = GetField().Multiply(m_fieldPtr->Add(In.x,m_AThirds),m_BInv);
+	Out.y = GetField().Multiply(In.y, m_BInv);
+	return Out;
+}
+
+NAMESPACE_END
+
+#endif
diff --git a/ecpm.h b/ecpm.h
new file mode 100644
index 00000000..f23a9dda
--- /dev/null
+++ b/ecpm.h
@@ -0,0 +1,142 @@
+// ecpm.h - written and placed in public domain by Jean-Pierre Muench. Copyright assigned to Crypto++ project.
+
+//! \file ecpm.h
+//! \brief Classes for montgomery curves over prime fields
+
+#ifndef CRYPTOPP_ECPM_H
+#define CRYPTOPP_ECPM_H
+
+#include "cryptlib.h"
+#include "integer.h"
+#include "modarith.h"
+#include "eprecomp.h"
+#include "smartptr.h"
+#include "pubkey.h"
+#include "ecp.h"
+
+NAMESPACE_BEGIN(CryptoPP)
+
+// strategy:
+// first do it the conservative way: each SimultaneousMultiply is followed and preceeded by a transformation
+// later replace this algorithm using an optimized algorithm using the Montgomery Ladder
+class CRYPTOPP_DLL ECPM : public AbstractGroup<ECPPoint>
+{
+public:
+	typedef ModularArithmetic Field;
+	typedef Integer FieldElement;
+	typedef ECPPoint Point;
+
+	ECPM() {}
+	ECPM(const ECPM &ecp, bool convertToMontgomeryRepresentation = false);
+	ECPM(const Integer &modulus, const FieldElement &A, const FieldElement &B);
+	// construct from BER encoded parameters
+	// this constructor will decode and extract the the fields fieldID and curve of the sequence ECParameters
+	ECPM(BufferedTransformation &bt);
+
+	// encode the fields fieldID and curve of the sequence ECParameters
+	void DEREncode(BufferedTransformation &bt) const;
+
+	bool Equal(const Point &P, const Point &Q) const;
+	const Point& Identity() const;
+	const Point& Inverse(const Point &P) const;
+	bool InversionIsFast() const { return true; }
+	const Point& Add(const Point &P, const Point &Q) const;
+	const Point& Double(const Point &P) const;
+	Point ScalarMultiply(const Point &P, const Integer &k) const;
+	Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const;
+	void SimultaneousMultiply(Point *results, const Point &base, const Integer *exponents, unsigned int exponentsCount) const;
+
+	Point Multiply(const Integer &k, const Point &P) const
+	{
+		return ScalarMultiply(P, k);
+	}
+	Point CascadeMultiply(const Integer &k1, const Point &P, const Integer &k2, const Point &Q) const
+	{
+		return CascadeScalarMultiply(P, k1, Q, k2);
+	}
+
+	bool ValidateParameters(RandomNumberGenerator &rng, unsigned int level = 3) const;
+	bool VerifyPoint(const Point &P) const;
+
+	unsigned int EncodedPointSize(bool compressed = false) const
+	{
+		return 1 + (compressed ? 1 : 2)*GetField().MaxElementByteLength();
+	}
+	// returns false if point is compressed and not valid (doesn't check if uncompressed)
+	bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const;
+	bool DecodePoint(Point &P, const byte *encodedPoint, size_t len) const;
+	void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const;
+	void EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const;
+
+	Point BERDecodePoint(BufferedTransformation &bt) const;
+	void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const;
+
+	Integer FieldSize() const { return GetField().GetModulus(); }
+	const Field & GetField() const { return *m_fieldPtr; }
+	const FieldElement & GetA() const { return m_A; }
+	const FieldElement & GetB() const { return m_B; }
+
+	bool operator==(const ECPM &rhs) const
+	{
+		return GetField() == rhs.GetField() && m_A == rhs.m_A && m_B == rhs.m_B;
+	}
+
+	void operator=(const ECPM &rhs);
+
+#ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
+	virtual ~ECPM() {}
+#endif
+
+private:
+	inline Point WeierstrassToMontgomery(const Point& In) const;
+	inline Point MontgomeryToWeierstrass(const Point& In) const;
+
+	clonable_ptr<Field> m_fieldPtr;
+	clonable_ptr<ECP> m_ComputeEngine; // does the heavy lifting on the scalar multiplication
+	FieldElement m_A, m_B; // M_B * y^2 = x^3 + m_A * x^2 + x (mod p)
+	FieldElement m_AThirds, m_BInv; // for faster conversion, A/3 and 1/B
+	mutable Point m_R;
+
+};
+
+template <class T> class EcPrecomputation;
+
+//! ECPM precomputation
+template<> class EcPrecomputation<ECPM> : public DL_GroupPrecomputation<ECPM::Point>
+{
+public:
+	typedef ECPM EllipticCurve;
+
+	// DL_GroupPrecomputation
+	bool NeedConversions() const { return true; }
+	Element ConvertIn(const Element &P) const
+	{
+		return P.identity ? P : ECPM::Point(m_ec->GetField().ConvertIn(P.x), m_ec->GetField().ConvertIn(P.y));
+	};
+	Element ConvertOut(const Element &P) const
+	{
+		return P.identity ? P : ECPM::Point(m_ec->GetField().ConvertOut(P.x), m_ec->GetField().ConvertOut(P.y));
+	}
+	const AbstractGroup<Element> & GetGroup() const { return *m_ec; }
+	Element BERDecodeElement(BufferedTransformation &bt) const { return m_ec->BERDecodePoint(bt); }
+	void DEREncodeElement(BufferedTransformation &bt, const Element &v) const { m_ec->DEREncodePoint(bt, v, false); }
+
+	// non-inherited
+	void SetCurve(const ECPM &ec)
+	{
+		m_ec.reset(new ECPM(ec, true));
+		m_ecOriginal = ec;
+	}
+	const ECPM & GetCurve() const { return *m_ecOriginal; }
+
+#ifndef CRYPTOPP_MAINTAIN_BACKWARDS_COMPATIBILITY_562
+	virtual ~EcPrecomputation() {}
+#endif
+
+private:
+	value_ptr<ECPM> m_ec, m_ecOriginal;
+};
+
+NAMESPACE_END
+
+#endif
\ No newline at end of file
diff --git a/oids.h b/oids.h
index 4ce6546d..030606c0 100644
--- a/oids.h
+++ b/oids.h
@@ -48,6 +48,32 @@ DEFINE_OID(1, iso)
 			DEFINE_OID(oiw()+3, oiw_secsig);

 				DEFINE_OID(oiw_secsig()+2, oiw_secsig_algorithms);

 					DEFINE_OID(oiw_secsig_algorithms()+26, id_sha1);

+			DEFINE_OID(identified_organization() + 6, dod);

+				DEFINE_OID(dod() + 1, dod_internet);

+					DEFINE_OID(dod_internet() + 4, dod_internet_private);

+						DEFINE_OID(dod_internet_private() + 1, dod_internet_private_enterprise);

+							DEFINE_OID(dod_internet_private_enterprise() + 9509, denis_bider);

+								DEFINE_OID(denis_bider() + 5, cryptopp); // denis bider provided us with this OID root, see https://github.com/weidai11/cryptopp/issues/67#issuecomment-160915245

+									DEFINE_OID(cryptopp() + 1, cryptopp_montgomery_curves);

+									// see http://safecurves.cr.yp.to/equation.html for the curves

+										DEFINE_OID(cryptopp_montgomery_curves() + 1, cryptoppM221);

+										DEFINE_OID(cryptopp_montgomery_curves() + 2, cryptoppM383);

+										DEFINE_OID(cryptopp_montgomery_curves() + 3, cryptoppM511);

+										DEFINE_OID(cryptopp_montgomery_curves() + 4, cryptoppCurve383187);

+									DEFINE_OID(cryptopp() + 2, cryptopp_edwards_curves);

+										DEFINE_OID(cryptopp_edwards_curves() + 1, cryptoppE222);

+										DEFINE_OID(cryptopp_edwards_curves() + 2, cryptoppE382);

+										DEFINE_OID(cryptopp_edwards_curves() + 3, cryptoppEd448);

+										DEFINE_OID(cryptopp_edwards_curves() + 4, cryptoppE521);

+										DEFINE_OID(cryptopp_edwards_curves() + 5, cryptoppCurve1174);

+										DEFINE_OID(cryptopp_edwards_curves() + 6, cryptoppCurve41417);

+							DEFINE_OID(dod_internet_private_enterprise() + 11591, gnu);

+								DEFINE_OID(gnu() + 15, gnu_elliptic_curve);

+									// as per https://tools.ietf.org/html/draft-josefsson-pkix-newcurves

+									DEFINE_OID(gnu_elliptic_curve() + 1, ietfCurve25519);

+									DEFINE_OID(gnu_elliptic_curve() + 2, ietfCurve448);

+									DEFINE_OID(gnu_elliptic_curve() + 3, ietfCurve25519ph);

+									DEFINE_OID(gnu_elliptic_curve() + 4, ietfCurve448ph);

 

 		DEFINE_OID(identified_organization()+36, teletrust);

 			DEFINE_OID(teletrust()+3, teletrust_algorithm)

diff --git a/test.cpp b/test.cpp
index a6a27005..88fbd250 100644
--- a/test.cpp
+++ b/test.cpp
@@ -937,6 +937,7 @@ bool Validate(int alg, bool thorough, const char *seedInput)
 	case 68: result = ValidateGCM(); break;

 	case 69: result = ValidateCMAC(); break;

 	case 70: result = ValidateHKDF(); break;

+	case 71: result = ValidateECPM(); break;

 	default: return false;

 	}

 

diff --git a/validat1.cpp b/validat1.cpp
index 892dcc81..720fb195 100644
--- a/validat1.cpp
+++ b/validat1.cpp
@@ -144,6 +144,7 @@ bool ValidateAll(bool thorough)
 	pass=ValidateRW() && pass;

 //	pass=ValidateBlumGoldwasser() && pass;

 	pass=ValidateECP() && pass;

+	pass = ValidateECPM() && pass;

 	pass=ValidateEC2N() && pass;

 	pass=ValidateECDSA() && pass;

 	pass=ValidateESIGN() && pass;

diff --git a/validat2.cpp b/validat2.cpp
index fd6d244a..e7b0c9b2 100644
--- a/validat2.cpp
+++ b/validat2.cpp
@@ -26,6 +26,7 @@
 #include "integer.h"

 #include "gf2n.h"

 #include "ecp.h"

+#include "ecpm.h"

 #include "ec2n.h"

 #include "asn.h"

 #include "rng.h"

@@ -715,6 +716,112 @@ bool ValidateECP()
 	return pass;

 }

 

+bool ValidateECPM()

+{

+	cout << "\nECPM validation suite running...\n\n";

+

+	ECIES<ECPM> ::Decryptor cpriv(GlobalRNG(), ASN1::ietfCurve25519());

+	ECIES<ECPM>::Encryptor cpub(cpriv);

+	ByteQueue bq;

+	cpriv.GetKey().DEREncode(bq);

+	cpub.AccessKey().AccessGroupParameters().SetEncodeAsOID(true);

+	cpub.GetKey().DEREncode(bq);

+	ECDSA<ECPM, SHA>::Signer spriv(bq);

+	ECDSA<ECPM, SHA>::Verifier spub(bq);

+	ECDH<ECPM>::Domain ecdhc(ASN1::ietfCurve25519());

+	ECMQV<ECPM>::Domain ecmqvc(ASN1::ietfCurve25519());

+

+	spriv.AccessKey().Precompute();

+	ByteQueue queue;

+	spriv.AccessKey().SavePrecomputation(queue);

+	spriv.AccessKey().LoadPrecomputation(queue);

+

+	bool pass = SignatureValidate(spriv, spub);

+	cpub.AccessKey().Precompute();

+	cpriv.AccessKey().Precompute();

+	pass = CryptoSystemValidate(cpriv, cpub) && pass;

+	pass = SimpleKeyAgreementValidate(ecdhc) && pass;

+	pass = AuthenticatedKeyAgreementValidate(ecmqvc) && pass;

+

+	cout << "Turning on point compression..." << endl;

+	cpriv.AccessKey().AccessGroupParameters().SetPointCompression(true);

+	cpub.AccessKey().AccessGroupParameters().SetPointCompression(true);

+	ecdhc.AccessGroupParameters().SetPointCompression(true);

+	ecmqvc.AccessGroupParameters().SetPointCompression(true);

+	pass = CryptoSystemValidate(cpriv, cpub) && pass;

+	pass = SimpleKeyAgreementValidate(ecdhc) && pass;

+	pass = AuthenticatedKeyAgreementValidate(ecmqvc) && pass;

+

+	cout << "Testing recommended montgomery curves..." << endl;

+	OID oid;

+	while (!(oid = DL_GroupParameters_EC<ECPM>::GetNextRecommendedParametersOID(oid)).m_values.empty())

+	{

+		DL_GroupParameters_EC<ECPM> params(oid);

+		bool fail = !params.Validate(GlobalRNG(), 2);

+		cout << (fail ? "FAILED" : "passed") << "    " << dec << params.GetCurve().GetField().MaxElementBitLength() << " bits" << endl;

+		pass = pass && !fail;

+	}

+

+	/*cout << "Performing the IRTF KATs..." << endl;

+

+	// tests from page 10 of IRTF curves draft 11

+	// calculate the y coordinates for the test

+	DL_GroupParameters_EC<ECPM> Curve25519(ASN1::ietfCurve25519());

+	const char* KAT_Base_25519_1 = "0231029842492115040904895560451863089656472772604678260265531221036453811406496";

+	const char* KAT_Base_25519_2 = "02e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493";

+	StringSource SS25519KAT_1(KAT_Base_25519_1,true,new HexDecoder);

+	StringSource SS25519KAT_2(KAT_Base_25519_2, true, new HexDecoder);

+	Integer()

+	ECPPoint P_KAT_Base_25519_1, P_KAT_Base_25519_2;

+	Curve25519.GetCurve().DecodePoint(P_KAT_Base_25519_1, SS25519KAT_1, 67);

+	Curve25519.GetCurve().DecodePoint(P_KAT_Base_25519_2, SS25519KAT_2, 67);

+	Integer x125519("0xe6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c");

+	Integer x225519("0xe5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493");

+	Integer BInv25519 = Curve25519.GetCurve().GetField().MultiplicativeInverse(Curve25519.GetCurve().GetB());

+	Integer y125519 = (x125519*BInv25519*(x125519*(x125519 + Curve25519.GetCurve().GetA()) + 1)) % Curve25519.GetCurve().GetField().GetModulus();

+	y125519 = ModularSquareRoot(y125519, Curve25519.GetCurve().GetField().GetModulus());

+	Integer y225519 = (x225519*BInv25519*(x225519*(x225519 + Curve25519.GetCurve().GetA()) + 1)) % Curve25519.GetCurve().GetField().GetModulus();

+	y225519 = ModularSquareRoot(y225519, Curve25519.GetCurve().GetField().GetModulus());

+

+	cout <<hex<< "x1: " << x125519 << endl;

+

+	ECPPoint Test125519 = Curve25519.ExponentiateElement(P_KAT_Base_25519_1, Integer("0xa546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4"));

+	ECPPoint Test225519 = Curve25519.ExponentiateElement(P_KAT_Base_25519_2, Integer("0x4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d"));

+

+	Integer Result125519("0xe6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c");

+	Integer Result225519("0xe5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493");

+

+	bool failedKATs = false;

+	pass = pass && (Result125519 == Test125519.x);

+	pass = pass && (Result225519 == Test225519.x);

+	failedKATs = failedKATs || (Result125519 != Test125519.x);

+	failedKATs = failedKATs || (Result225519 != Test225519.x);

+

+	DL_GroupParameters_EC<ECPM> Curve448(ASN1::ietfCurve448());

+	Integer x1448("0x06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086");

+	Integer x2448("0x0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db");

+	Integer BInv448 = Curve448.GetCurve().GetField().MultiplicativeInverse(Curve448.GetCurve().GetB());

+	Integer y1448 = (x1448*BInv448*(x1448*(x1448 + Curve448.GetCurve().GetA()) + 1)) % Curve448.GetCurve().GetField().GetModulus();

+	y1448 = ModularSquareRoot(y1448, Curve448.GetCurve().GetField().GetModulus());

+	Integer y2448 = (x2448*BInv448*(x2448*(x2448 + Curve448.GetCurve().GetA()) + 1)) % Curve448.GetCurve().GetField().GetModulus();

+	y2448 = ModularSquareRoot(y2448, Curve448.GetCurve().GetField().GetModulus());

+

+	ECPPoint Test1448 = Curve448.ExponentiateElement(ECPPoint(x1448, y1448), Integer("0x3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3"));

+	ECPPoint Test2448 = Curve448.ExponentiateElement(ECPPoint(x2448, y2448), Integer("0x203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c538345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f"));

+

+	Integer Result1448("0xce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239fe14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f");

+	Integer Result2448("0x884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d");

+

+	pass = pass && (Result1448 == Test1448.x);

+	pass = pass && (Result2448 == Test2448.x);

+	failedKATs = failedKATs || (Result1448 != Test1448.x);

+	failedKATs = failedKATs || (Result2448 != Test2448.x);

+

+	cout << (failedKATs ? "FAILED" : "passed") << "    " << "known anser tests" << endl;*/

+

+	return pass;

+}

+

 bool ValidateEC2N()

 {

 	cout << "\nEC2N validation suite running...\n\n";

diff --git a/validate.h b/validate.h
index 898df436..d979bd8a 100644
--- a/validate.h
+++ b/validate.h
@@ -81,6 +81,7 @@ bool ValidateRabin();
 bool ValidateRW();

 //bool ValidateBlumGoldwasser();

 bool ValidateECP();

+bool ValidateECPM();

 bool ValidateEC2N();

 bool ValidateECDSA();

 bool ValidateESIGN();