diff options
Diffstat (limited to 'crypto/src/math/ec')
| -rw-r--r-- | crypto/src/math/ec/ECPoint.cs | 4 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/djb/Curve25519.cs | 100 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/djb/Curve25519Field.cs (renamed from crypto/src/math/ec/custom/sec/Curve25519Field.cs) | 8 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs | 233 | ||||
| -rw-r--r-- | crypto/src/math/ec/custom/djb/Curve25519Point.cs | 264 |
5 files changed, 604 insertions, 5 deletions
diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs index cd6811dfa..0430a6110 100644 --- a/crypto/src/math/ec/ECPoint.cs +++ b/crypto/src/math/ec/ECPoint.cs @@ -1191,13 +1191,13 @@ namespace Org.BouncyCastle.Math.EC ECFieldElement W = ZZ[1]; if (W == null) { - // NOTE: Rarely, twicePlus will result in the need for a lazy W1 calculation here + // NOTE: Rarely, TwicePlus will result in the need for a lazy W1 calculation here ZZ[1] = W = CalculateJacobianModifiedW(ZZ[0], null); } return W; } - protected FpPoint TwiceJacobianModified(bool calculateW) + protected virtual FpPoint TwiceJacobianModified(bool calculateW) { ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord, Z1 = this.RawZCoords[0], W1 = GetJacobianModifiedW(); diff --git a/crypto/src/math/ec/custom/djb/Curve25519.cs b/crypto/src/math/ec/custom/djb/Curve25519.cs new file mode 100644 index 000000000..3dbdac051 --- /dev/null +++ b/crypto/src/math/ec/custom/djb/Curve25519.cs @@ -0,0 +1,100 @@ +using System; + +using Org.BouncyCastle.Math.EC.Custom.Sec; +using Org.BouncyCastle.Math.Field; +using Org.BouncyCastle.Utilities.Encoders; + +namespace Org.BouncyCastle.Math.EC.Custom.Djb +{ + internal class Curve25519 + : ECCurve + { + public static readonly BigInteger q = Nat256.ToBigInteger(Curve25519Field.P); + + private const int Curve25519_DEFAULT_COORDS = COORD_JACOBIAN_MODIFIED; + + protected readonly Curve25519Point m_infinity; + + public Curve25519() + : base(FiniteFields.GetPrimeField(q)) + { + this.m_infinity = new Curve25519Point(this, null, null); + + this.m_a = FromBigInteger(new BigInteger(1, + Hex.Decode("2AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA984914A144"))); + this.m_b = FromBigInteger(new BigInteger(1, + Hex.Decode("7B425ED097B425ED097B425ED097B425ED097B425ED097B4260B5E9C7710C864"))); + this.m_order = new BigInteger(1, Hex.Decode("1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED")); + this.m_cofactor = BigInteger.ValueOf(8); + this.m_coord = Curve25519_DEFAULT_COORDS; + } + + protected override ECCurve CloneCurve() + { + return new Curve25519(); + } + + public override bool SupportsCoordinateSystem(int coord) + { + switch (coord) + { + case COORD_JACOBIAN_MODIFIED: + return true; + default: + return false; + } + } + + public virtual BigInteger Q + { + get { return q; } + } + + public override ECPoint Infinity + { + get { return m_infinity; } + } + + public override int FieldSize + { + get { return q.BitLength; } + } + + public override ECFieldElement FromBigInteger(BigInteger x) + { + return new Curve25519FieldElement(x); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, bool withCompression) + { + return new Curve25519Point(this, x, y, withCompression); + } + + protected internal override ECPoint CreateRawPoint(ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + { + return new Curve25519Point(this, x, y, zs, withCompression); + } + + protected override ECPoint DecompressPoint(int yTilde, BigInteger X1) + { + ECFieldElement x = FromBigInteger(X1); + ECFieldElement alpha = x.Square().Add(A).Multiply(x).Add(B); + ECFieldElement beta = alpha.Sqrt(); + + // + // if we can't find a sqrt we haven't got a point on the + // curve - run! + // + if (beta == null) + throw new ArithmeticException("Invalid point compression"); + + if (beta.TestBitZero() != (yTilde == 1)) + { + // Use the other root + beta = beta.Negate(); + } + + return new Curve25519Point(this, x, beta, true); + } + } +} diff --git a/crypto/src/math/ec/custom/sec/Curve25519Field.cs b/crypto/src/math/ec/custom/djb/Curve25519Field.cs index ee0f88311..084ca96af 100644 --- a/crypto/src/math/ec/custom/sec/Curve25519Field.cs +++ b/crypto/src/math/ec/custom/djb/Curve25519Field.cs @@ -1,7 +1,9 @@ using System; using System.Diagnostics; -namespace Org.BouncyCastle.Math.EC.Custom.Sec +using Org.BouncyCastle.Math.EC.Custom.Sec; + +namespace Org.BouncyCastle.Math.EC.Custom.Djb { internal class Curve25519Field { @@ -190,7 +192,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec c >>= 32; if (c != 0) { - Nat.IncAt(7, z, 1); + Nat.IncAt(8, z, 1); } z[7] &= P7; } @@ -202,7 +204,7 @@ namespace Org.BouncyCastle.Math.EC.Custom.Sec c >>= 32; if (c != 0) { - Nat.DecAt(7, z, 1); + Nat.DecAt(8, z, 1); } z[7] &= P7; } diff --git a/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs b/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs new file mode 100644 index 000000000..8d5a80326 --- /dev/null +++ b/crypto/src/math/ec/custom/djb/Curve25519FieldElement.cs @@ -0,0 +1,233 @@ +using System; + +using Org.BouncyCastle.Math.EC.Custom.Sec; +using Org.BouncyCastle.Utilities; + +namespace Org.BouncyCastle.Math.EC.Custom.Djb +{ + internal class Curve25519FieldElement + : ECFieldElement + { + public static readonly BigInteger Q = Curve25519.q; + + // Calculated as ECConstants.TWO.modPow(Q.shiftRight(2), Q) + private static readonly uint[] PRECOMP_POW2 = new uint[]{ 0x4a0ea0b0, 0xc4ee1b27, 0xad2fe478, 0x2f431806, + 0x3dfbd7a7, 0x2b4d0099, 0x4fc1df0b, 0x2b832480 }; + + protected internal readonly uint[] x; + + public Curve25519FieldElement(BigInteger x) + { + if (x == null || x.SignValue < 0 || x.CompareTo(Q) >= 0) + throw new ArgumentException("value invalid for Curve25519FieldElement", "x"); + + this.x = Curve25519Field.FromBigInteger(x); + } + + public Curve25519FieldElement() + { + this.x = Nat256.Create(); + } + + protected internal Curve25519FieldElement(uint[] x) + { + this.x = x; + } + + public override bool IsZero + { + get { return Nat256.IsZero(x); } + } + + public override bool IsOne + { + get { return Nat256.IsOne(x); } + } + + public override bool TestBitZero() + { + return Nat256.GetBit(x, 0) == 1; + } + + public override BigInteger ToBigInteger() + { + return Nat256.ToBigInteger(x); + } + + public override string FieldName + { + get { return "Curve25519Field"; } + } + + public override int FieldSize + { + get { return Q.BitLength; } + } + + public override ECFieldElement Add(ECFieldElement b) + { + uint[] z = Nat256.Create(); + Curve25519Field.Add(x, ((Curve25519FieldElement)b).x, z); + return new Curve25519FieldElement(z); + } + + public override ECFieldElement AddOne() + { + uint[] z = Nat256.Create(); + Curve25519Field.AddOne(x, z); + return new Curve25519FieldElement(z); + } + + public override ECFieldElement Subtract(ECFieldElement b) + { + uint[] z = Nat256.Create(); + Curve25519Field.Subtract(x, ((Curve25519FieldElement)b).x, z); + return new Curve25519FieldElement(z); + } + + public override ECFieldElement Multiply(ECFieldElement b) + { + uint[] z = Nat256.Create(); + Curve25519Field.Multiply(x, ((Curve25519FieldElement)b).x, z); + return new Curve25519FieldElement(z); + } + + public override ECFieldElement Divide(ECFieldElement b) + { + //return Multiply(b.Invert()); + uint[] z = Nat256.Create(); + Mod.Invert(Curve25519Field.P, ((Curve25519FieldElement)b).x, z); + Curve25519Field.Multiply(z, x, z); + return new Curve25519FieldElement(z); + } + + public override ECFieldElement Negate() + { + uint[] z = Nat256.Create(); + Curve25519Field.Negate(x, z); + return new Curve25519FieldElement(z); + } + + public override ECFieldElement Square() + { + uint[] z = Nat256.Create(); + Curve25519Field.Square(x, z); + return new Curve25519FieldElement(z); + } + + public override ECFieldElement Invert() + { + //return new Curve25519FieldElement(ToBigInteger().ModInverse(Q)); + uint[] z = Nat256.Create(); + Mod.Invert(Curve25519Field.P, x, z); + return new Curve25519FieldElement(z); + } + + /** + * return a sqrt root - the routine verifies that the calculation returns the right value - if + * none exists it returns null. + */ + public override ECFieldElement Sqrt() + { + /* + * Q == 8m + 5, so we use Pocklington's method for this case. + * + * First, raise this element to the exponent 2^252 - 2^1 (i.e. m + 1) + * + * Breaking up the exponent's binary representation into "repunits", we get: + * { 251 1s } { 1 0s } + * + * Therefore we need an addition chain containing 251 (the lengths of the repunits) + * We use: 1, 2, 3, 4, 7, 11, 15, 30, 60, 120, 131, [251] + */ + + uint[] x1 = this.x; + if (Nat256.IsZero(x1) || Nat256.IsOne(x1)) + return this; + + uint[] x2 = Nat256.Create(); + Curve25519Field.Square(x1, x2); + Curve25519Field.Multiply(x2, x1, x2); + uint[] x3 = x2; + Curve25519Field.Square(x2, x3); + Curve25519Field.Multiply(x3, x1, x3); + uint[] x4 = Nat256.Create(); + Curve25519Field.Square(x3, x4); + Curve25519Field.Multiply(x4, x1, x4); + uint[] x7 = Nat256.Create(); + Curve25519Field.SquareN(x4, 3, x7); + Curve25519Field.Multiply(x7, x3, x7); + uint[] x11 = x3; + Curve25519Field.SquareN(x7, 4, x11); + Curve25519Field.Multiply(x11, x4, x11); + uint[] x15 = x7; + Curve25519Field.SquareN(x11, 4, x15); + Curve25519Field.Multiply(x15, x4, x15); + uint[] x30 = x4; + Curve25519Field.SquareN(x15, 15, x30); + Curve25519Field.Multiply(x30, x15, x30); + uint[] x60 = x15; + Curve25519Field.SquareN(x30, 30, x60); + Curve25519Field.Multiply(x60, x30, x60); + uint[] x120 = x30; + Curve25519Field.SquareN(x60, 60, x120); + Curve25519Field.Multiply(x120, x60, x120); + uint[] x131 = x60; + Curve25519Field.SquareN(x120, 11, x131); + Curve25519Field.Multiply(x131, x11, x131); + uint[] x251 = x11; + Curve25519Field.SquareN(x131, 120, x251); + Curve25519Field.Multiply(x251, x120, x251); + + uint[] t1 = x251; + Curve25519Field.Square(t1, t1); + + uint[] t2 = x120; + Curve25519Field.Square(t1, t2); + + if (Nat256.Eq(x1, t2)) + { + return new Curve25519FieldElement(t1); + } + + /* + * If the first guess is incorrect, we multiply by a precomputed power of 2 to get the second guess, + * which is ((4x)^(m + 1))/2 mod Q + */ + Curve25519Field.Multiply(t1, PRECOMP_POW2, t1); + + Curve25519Field.Square(t1, t2); + + if (Nat256.Eq(x1, t2)) + { + return new Curve25519FieldElement(t1); + } + + return null; + } + + public override bool Equals(object obj) + { + return Equals(obj as Curve25519FieldElement); + } + + public override bool Equals(ECFieldElement other) + { + return Equals(other as Curve25519FieldElement); + } + + public virtual bool Equals(Curve25519FieldElement other) + { + if (this == other) + return true; + if (null == other) + return false; + return Nat256.Eq(x, other.x); + } + + public override int GetHashCode() + { + return Q.GetHashCode() ^ Arrays.GetHashCode(x, 0, 8); + } + } +} diff --git a/crypto/src/math/ec/custom/djb/Curve25519Point.cs b/crypto/src/math/ec/custom/djb/Curve25519Point.cs new file mode 100644 index 000000000..65b6792eb --- /dev/null +++ b/crypto/src/math/ec/custom/djb/Curve25519Point.cs @@ -0,0 +1,264 @@ +using System; + +using Org.BouncyCastle.Math.EC.Custom.Sec; + +namespace Org.BouncyCastle.Math.EC.Custom.Djb +{ + internal class Curve25519Point + : ECPointBase + { + /** + * Create a point which encodes with point compression. + * + * @param curve the curve to use + * @param x affine x co-ordinate + * @param y affine y co-ordinate + * + * @deprecated Use ECCurve.createPoint to construct points + */ + public Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y) + : this(curve, x, y, false) + { + } + + /** + * Create a point that encodes with or without point compresion. + * + * @param curve the curve to use + * @param x affine x co-ordinate + * @param y affine y co-ordinate + * @param withCompression if true encode with point compression + * + * @deprecated per-point compression property will be removed, refer {@link #getEncoded(bool)} + */ + public Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y, bool withCompression) + : base(curve, x, y, withCompression) + { + if ((x == null) != (y == null)) + throw new ArgumentException("Exactly one of the field elements is null"); + } + + internal Curve25519Point(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs, bool withCompression) + : base(curve, x, y, zs, withCompression) + { + } + + protected override ECPoint Detach() + { + return new Curve25519Point(null, AffineXCoord, AffineYCoord); + } + + protected internal override bool CompressionYTilde + { + get { return this.AffineYCoord.TestBitZero(); } + } + + public override ECFieldElement GetZCoord(int index) + { + if (index == 1) + { + return GetJacobianModifiedW(); + } + + return base.GetZCoord(index); + } + + public override ECPoint Add(ECPoint b) + { + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return this; + if (this == b) + return Twice(); + + ECCurve curve = this.Curve; + + ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord; + ECFieldElement X2 = b.RawXCoord, Y2 = b.RawYCoord; + + ECFieldElement Z1 = this.RawZCoords[0]; + ECFieldElement Z2 = b.RawZCoords[0]; + + bool Z1IsOne = Z1.IsOne; + + ECFieldElement Z1Squared, U2, S2; + if (Z1IsOne) + { + Z1Squared = Z1; U2 = X2; S2 = Y2; + } + else + { + Z1Squared = Z1.Square(); + U2 = Z1Squared.Multiply(X2); + ECFieldElement Z1Cubed = Z1Squared.Multiply(Z1); + S2 = Z1Cubed.Multiply(Y2); + } + + bool Z2IsOne = Z2.IsOne; + ECFieldElement Z2Squared, U1, S1; + if (Z2IsOne) + { + Z2Squared = Z2; U1 = X1; S1 = Y1; + } + else + { + Z2Squared = Z2.Square(); + U1 = Z2Squared.Multiply(X1); + ECFieldElement Z2Cubed = Z2Squared.Multiply(Z2); + S1 = Z2Cubed.Multiply(Y1); + } + + ECFieldElement H = U1.Subtract(U2); + ECFieldElement R = S1.Subtract(S2); + + // Check if b == this or b == -this + if (H.IsZero) + { + if (R.IsZero) + { + // this == b, i.e. this must be doubled + return this.Twice(); + } + + // this == -b, i.e. the result is the point at infinity + return curve.Infinity; + } + + ECFieldElement HSquared = H.Square(); + ECFieldElement G = HSquared.Multiply(H); + ECFieldElement V = HSquared.Multiply(U1); + + ECFieldElement X3 = R.Square().Add(G).Subtract(Two(V)); + ECFieldElement Y3 = V.Subtract(X3).MultiplyMinusProduct(R, G, S1); + + ECFieldElement Z3 = H; + if (!Z1IsOne) + { + Z3 = Z3.Multiply(Z1); + } + if (!Z2IsOne) + { + Z3 = Z3.Multiply(Z2); + } + + ECFieldElement Z3Squared = (Z3 == H) ? HSquared : null; + + // TODO If the result will only be used in a subsequent addition, we don't need W3 + ECFieldElement W3 = CalculateJacobianModifiedW(Z3, Z3Squared); + + ECFieldElement[] zs = new ECFieldElement[]{ Z3, W3 }; + + return new Curve25519Point(curve, X3, Y3, zs, IsCompressed); + } + + public override ECPoint Twice() + { + if (this.IsInfinity) + return this; + + ECCurve curve = this.Curve; + + ECFieldElement Y1 = this.RawYCoord; + if (Y1.IsZero) + return curve.Infinity; + + return TwiceJacobianModified(true); + } + + public override ECPoint TwicePlus(ECPoint b) + { + if (this == b) + return ThreeTimes(); + if (this.IsInfinity) + return b; + if (b.IsInfinity) + return Twice(); + + ECFieldElement Y1 = this.RawYCoord; + if (Y1.IsZero) + return b; + + return TwiceJacobianModified(false).Add(b); + } + + public override ECPoint ThreeTimes() + { + if (this.IsInfinity || this.RawYCoord.IsZero) + return this; + + return TwiceJacobianModified(false).Add(this); + } + + protected virtual ECFieldElement Two(ECFieldElement x) + { + return x.Add(x); + } + + protected virtual ECFieldElement Three(ECFieldElement x) + { + return Two(x).Add(x); + } + + public override ECPoint Subtract(ECPoint b) + { + if (b.IsInfinity) + return this; + + return Add(b.Negate()); + } + + public override ECPoint Negate() + { + if (IsInfinity) + return this; + + return new Curve25519Point(Curve, RawXCoord, RawYCoord.Negate(), RawZCoords, IsCompressed); + } + + protected virtual ECFieldElement CalculateJacobianModifiedW(ECFieldElement Z, ECFieldElement ZSquared) + { + ECFieldElement a4 = this.Curve.A; + if (Z.IsOne) + return a4; + + if (ZSquared == null) + { + ZSquared = Z.Square(); + } + + return ZSquared.Square().Multiply(a4); + } + + protected virtual ECFieldElement GetJacobianModifiedW() + { + ECFieldElement[] ZZ = this.RawZCoords; + ECFieldElement W = ZZ[1]; + if (W == null) + { + // NOTE: Rarely, TwicePlus will result in the need for a lazy W1 calculation here + ZZ[1] = W = CalculateJacobianModifiedW(ZZ[0], null); + } + return W; + } + + protected virtual Curve25519Point TwiceJacobianModified(bool calculateW) + { + ECFieldElement X1 = this.RawXCoord, Y1 = this.RawYCoord, Z1 = this.RawZCoords[0], W1 = GetJacobianModifiedW(); + + ECFieldElement X1Squared = X1.Square(); + ECFieldElement M = Three(X1Squared).Add(W1); + ECFieldElement _2Y1 = Two(Y1); + ECFieldElement _2Y1Squared = _2Y1.Multiply(Y1); + ECFieldElement S = Two(X1.Multiply(_2Y1Squared)); + ECFieldElement X3 = M.Square().Subtract(Two(S)); + ECFieldElement _4T = _2Y1Squared.Square(); + ECFieldElement _8T = Two(_4T); + ECFieldElement Y3 = M.Multiply(S.Subtract(X3)).Subtract(_8T); + ECFieldElement W3 = calculateW ? Two(_8T.Multiply(W1)) : null; + ECFieldElement Z3 = Z1.IsOne ? _2Y1 : _2Y1.Multiply(Z1); + + return new Curve25519Point(this.Curve, X3, Y3, new ECFieldElement[] { Z3, W3 }, IsCompressed); + } + } +} |