summary refs log tree commit diff
path: root/crypto/src/math
diff options
context:
space:
mode:
authorPeter Dettman <peter.dettman@bouncycastle.org>2014-01-23 18:21:40 +0700
committerPeter Dettman <peter.dettman@bouncycastle.org>2014-01-23 18:21:40 +0700
commit0f05a8dc4b27623d96b08f7619c056a4e65baa9b (patch)
tree18169d7c4c8fbea895811eba8fbe7a9b9e6250ab /crypto/src/math
parentUse ImportPoint to make sure points are on same curve (diff)
downloadBouncyCastle.NET-ed25519-0f05a8dc4b27623d96b08f7619c056a4e65baa9b.tar.xz
Port of several interrelated things from Java build:
- Z coordinates for points
- More point normalization code
- Curve management of point precomp info
- Add WNafUtilities and use in multipliers/ECAlgorithms
- Make various fields/classes protected/public
Diffstat (limited to 'crypto/src/math')
-rw-r--r--crypto/src/math/ec/ECAlgorithms.cs50
-rw-r--r--crypto/src/math/ec/ECCurve.cs92
-rw-r--r--crypto/src/math/ec/ECPoint.cs352
-rw-r--r--crypto/src/math/ec/multiplier/ECMultiplier.cs30
-rw-r--r--crypto/src/math/ec/multiplier/FpNafMultiplier.cs41
-rw-r--r--crypto/src/math/ec/multiplier/ReferenceMultiplier.cs61
-rw-r--r--crypto/src/math/ec/multiplier/WNafMultiplier.cs274
-rw-r--r--crypto/src/math/ec/multiplier/WNafPreCompInfo.cs76
-rw-r--r--crypto/src/math/ec/multiplier/WNafUtilities.cs394
-rw-r--r--crypto/src/math/ec/multiplier/WTauNafMultiplier.cs207
-rw-r--r--crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs57
11 files changed, 1056 insertions, 578 deletions
diff --git a/crypto/src/math/ec/ECAlgorithms.cs b/crypto/src/math/ec/ECAlgorithms.cs
index 070c8326c..a7030700e 100644
--- a/crypto/src/math/ec/ECAlgorithms.cs
+++ b/crypto/src/math/ec/ECAlgorithms.cs
@@ -1,5 +1,6 @@
 using System;
 
+using Org.BouncyCastle.Math.EC.Multiplier;
 using Org.BouncyCastle.Math.Field;
 
 namespace Org.BouncyCastle.Math.EC
@@ -105,32 +106,35 @@ namespace Org.BouncyCastle.Math.EC
         internal static ECPoint ImplShamirsTrick(ECPoint P, BigInteger k,
             ECPoint Q, BigInteger l)
         {
-            int m = System.Math.Max(k.BitLength, l.BitLength);
-            ECPoint Z = P.Add(Q);
-            ECPoint R = P.Curve.Infinity;
+            ECCurve curve = P.Curve;
+            ECPoint infinity = curve.Infinity;
 
-            for (int i = m - 1; i >= 0; --i)
+            // TODO conjugate co-Z addition (ZADDC) can return both of these
+            ECPoint PaddQ = P.Add(Q);
+            ECPoint PsubQ = P.Subtract(Q);
+
+            ECPoint[] points = new ECPoint[] { Q, PsubQ, P, PaddQ };
+            curve.NormalizeAll(points);
+
+            ECPoint[] table = new ECPoint[] {
+            points[3].Negate(), points[2].Negate(), points[1].Negate(),
+            points[0].Negate(), infinity, points[0],
+            points[1], points[2], points[3] };
+
+            byte[] jsf = WNafUtilities.GenerateJsf(k, l);
+
+            ECPoint R = infinity;
+
+            int i = jsf.Length;
+            while (--i >= 0)
             {
-                R = R.Twice();
+                int jsfi = jsf[i];
 
-                if (k.TestBit(i))
-                {
-                    if (l.TestBit(i))
-                    {
-                        R = R.Add(Z);
-                    }
-                    else
-                    {
-                        R = R.Add(P);
-                    }
-                }
-                else
-                {
-                    if (l.TestBit(i))
-                    {
-                        R = R.Add(Q);
-                    }
-                }
+                // NOTE: The shifting ensures the sign is extended correctly
+                int kDigit = ((jsfi << 24) >> 28), lDigit = ((jsfi << 28) >> 28);
+
+                int index = 4 + (kDigit * 3) + lDigit;
+                R = R.TwicePlus(table[index]);
             }
 
             return R;
diff --git a/crypto/src/math/ec/ECCurve.cs b/crypto/src/math/ec/ECCurve.cs
index 2db6bdc80..38daa719c 100644
--- a/crypto/src/math/ec/ECCurve.cs
+++ b/crypto/src/math/ec/ECCurve.cs
@@ -109,6 +109,28 @@ namespace Org.BouncyCastle.Math.EC
             return coord == COORD_AFFINE;
         }
 
+        public virtual PreCompInfo GetPreCompInfo(ECPoint p)
+        {
+            CheckPoint(p);
+            return p.m_preCompInfo;
+        }
+
+        /**
+         * Sets the <code>PreCompInfo</code> for a point on this curve. Used by
+         * <code>ECMultiplier</code>s to save the precomputation for this <code>ECPoint</code> for use
+         * by subsequent multiplication.
+         * 
+         * @param point
+         *            The <code>ECPoint</code> to store precomputations for.
+         * @param preCompInfo
+         *            The values precomputed by the <code>ECMultiplier</code>.
+         */
+        public virtual void SetPreCompInfo(ECPoint point, PreCompInfo preCompInfo)
+        {
+            CheckPoint(point);
+            point.m_preCompInfo = preCompInfo;
+        }
+
         public virtual ECPoint ImportPoint(ECPoint p)
         {
             if (this == p.Curve)
@@ -123,7 +145,56 @@ namespace Org.BouncyCastle.Math.EC
             // TODO Default behaviour could be improved if the two curves have the same coordinate system by copying any Z coordinates.
             p = p.Normalize();
 
-            return CreatePoint(p.X.ToBigInteger(), p.Y.ToBigInteger(), p.withCompression);
+            return CreatePoint(p.X.ToBigInteger(), p.Y.ToBigInteger(), p.IsCompressed);
+        }
+
+        /**
+         * Normalization ensures that any projective coordinate is 1, and therefore that the x, y
+         * coordinates reflect those of the equivalent point in an affine coordinate system. Where more
+         * than one point is to be normalized, this method will generally be more efficient than
+         * normalizing each point separately.
+         * 
+         * @param points
+         *            An array of points that will be updated in place with their normalized versions,
+         *            where necessary
+         */
+        public virtual void NormalizeAll(ECPoint[] points)
+        {
+            CheckPoints(points);
+
+            if (this.CoordinateSystem == ECCurve.COORD_AFFINE)
+            {
+                return;
+            }
+
+            /*
+             * Figure out which of the points actually need to be normalized
+             */
+            ECFieldElement[] zs = new ECFieldElement[points.Length];
+            int[] indices = new int[points.Length];
+            int count = 0;
+            for (int i = 0; i < points.Length; ++i)
+            {
+                ECPoint p = points[i];
+                if (null != p && !p.IsNormalized())
+                {
+                    zs[count] = p.GetZCoord(0);
+                    indices[count++] = i;
+                }
+            }
+
+            if (count == 0)
+            {
+                return;
+            }
+
+            ECAlgorithms.MontgomeryTrick(zs, 0, count);
+
+            for (int j = 0; j < count; ++j)
+            {
+                int index = indices[j];
+                points[index] = points[index].Normalize(zs[j]);
+            }
         }
 
         public abstract ECPoint Infinity { get; }
@@ -148,6 +219,25 @@ namespace Org.BouncyCastle.Math.EC
             get { return m_coord; }
         }
 
+        protected virtual void CheckPoint(ECPoint point)
+        {
+            if (null == point || (this != point.Curve))
+                throw new ArgumentException("must be non-null and on this curve", "point");
+        }
+
+        protected virtual void CheckPoints(ECPoint[] points)
+        {
+            if (points == null)
+                throw new ArgumentNullException("points");
+
+            for (int i = 0; i < points.Length; ++i)
+            {
+                ECPoint point = points[i];
+                if (null != point && this != point.Curve)
+                    throw new ArgumentException("entries must be null or on this curve", "points");
+            }
+        }
+
         public virtual bool Equals(ECCurve other)
         {
             if (this == other)
diff --git a/crypto/src/math/ec/ECPoint.cs b/crypto/src/math/ec/ECPoint.cs
index 1b00b764f..7a4450ac1 100644
--- a/crypto/src/math/ec/ECPoint.cs
+++ b/crypto/src/math/ec/ECPoint.cs
@@ -2,8 +2,6 @@ using System;
 using System.Collections;
 using System.Diagnostics;
 
-using Org.BouncyCastle.Asn1.X9;
-
 using Org.BouncyCastle.Math.EC.Multiplier;
 
 namespace Org.BouncyCastle.Math.EC
@@ -13,41 +11,122 @@ namespace Org.BouncyCastle.Math.EC
      */
     public abstract class ECPoint
     {
-        internal readonly ECCurve			curve;
-        internal readonly ECFieldElement	x, y;
-        internal readonly bool				withCompression;
-        internal PreCompInfo				preCompInfo = null;
+        protected static ECFieldElement[] EMPTY_ZS = new ECFieldElement[0];
+
+        protected static ECFieldElement[] GetInitialZCoords(ECCurve curve)
+        {
+            // Cope with null curve, most commonly used by implicitlyCa
+            int coord = null == curve ? ECCurve.COORD_AFFINE : curve.CoordinateSystem;
+
+            switch (coord)
+            {
+                case ECCurve.COORD_AFFINE:
+                case ECCurve.COORD_LAMBDA_AFFINE:
+                    return EMPTY_ZS;
+                default:
+                    break;
+            }
+
+            ECFieldElement one = curve.FromBigInteger(BigInteger.One);
+
+            switch (coord)
+            {
+                case ECCurve.COORD_HOMOGENEOUS:
+                case ECCurve.COORD_JACOBIAN:
+                case ECCurve.COORD_LAMBDA_PROJECTIVE:
+                    return new ECFieldElement[] { one };
+                case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
+                    return new ECFieldElement[] { one, one, one };
+                case ECCurve.COORD_JACOBIAN_MODIFIED:
+                    return new ECFieldElement[] { one, curve.A };
+                default:
+                    throw new ArgumentException("unknown coordinate system");
+            }
+        }
+
+        protected internal readonly ECCurve m_curve;
+        protected internal readonly ECFieldElement m_x, m_y;
+        protected internal readonly ECFieldElement[] m_zs;
+        protected internal readonly bool m_withCompression;
 
-        protected internal ECPoint(
+        protected internal PreCompInfo m_preCompInfo = null;
+
+        protected ECPoint(
             ECCurve			curve,
             ECFieldElement	x,
             ECFieldElement	y,
             bool			withCompression)
         {
-            if (curve == null)
-                throw new ArgumentNullException("curve");
+            this.m_curve = curve;
+            this.m_x = x;
+            this.m_y = y;
+            this.m_withCompression = withCompression;
+        }
+
+        protected ECPoint(ECCurve curve, ECFieldElement x, ECFieldElement y, ECFieldElement[] zs)
+        {
+            this.m_curve = curve;
+            this.m_x = x;
+            this.m_y = y;
+            this.m_zs = zs;
+        }
 
-            this.curve = curve;
-            this.x = x;
-            this.y = y;
-            this.withCompression = withCompression;
+        public virtual ECCurve Curve
+        {
+            get { return m_curve; }
         }
 
-        public ECCurve Curve
+        protected virtual int CurveCoordinateSystem
         {
-            get { return curve; }
+            get
+            {
+                // Cope with null curve, most commonly used by implicitlyCa
+                return null == m_curve ? ECCurve.COORD_AFFINE : m_curve.CoordinateSystem;
+            }
         }
 
-        public ECFieldElement X
+        public virtual ECFieldElement X
         {
-            get { return x; }
+            get { return m_x; }
         }
 
-        public ECFieldElement Y
+        public virtual ECFieldElement Y
         {
-            get { return y; }
+            get { return m_y; }
         }
 
+        public virtual ECFieldElement GetZCoord(int index)
+        {
+            return (index < 0 || index >= m_zs.Length) ? null : m_zs[index];
+        }
+
+        public virtual ECFieldElement[] GetZCoords()
+        {
+            int zsLen = m_zs.Length;
+            if (zsLen == 0)
+            {
+                return m_zs;
+            }
+            ECFieldElement[] copy = new ECFieldElement[zsLen];
+            Array.Copy(m_zs, 0, copy, 0, zsLen);
+            return copy;
+        }
+
+        protected virtual void CheckNormalized()
+        {
+            if (!IsNormalized())
+                throw new InvalidOperationException("point not in normal form");
+        }
+
+        public virtual bool IsNormalized()
+        {
+            int coord = this.CurveCoordinateSystem;
+
+            return coord == ECCurve.COORD_AFFINE
+                || coord == ECCurve.COORD_LAMBDA_AFFINE
+                || IsInfinity;
+                //|| zs[0].isOne();
+        }
 
         /**
          * Normalization ensures that any projective coordinate is 1, and therefore that the x, y
@@ -57,17 +136,64 @@ namespace Org.BouncyCastle.Math.EC
          */
         public virtual ECPoint Normalize()
         {
-            return this;
+            if (this.IsInfinity)
+            {
+                return this;
+            }
+
+            switch (this.CurveCoordinateSystem)
+            {
+                case ECCurve.COORD_AFFINE:
+                case ECCurve.COORD_LAMBDA_AFFINE:
+                {
+                    return this;
+                }
+                default:
+                {
+                    ECFieldElement Z1 = GetZCoord(0);
+                    if (Z1.IsOne)
+                    {
+                        return this;
+                    }
+
+                    return Normalize(Z1.Invert());
+                }
+            }
+        }
+
+        internal virtual ECPoint Normalize(ECFieldElement zInv)
+        {
+            throw new InvalidOperationException("not a projective coordinate system");
+
+            //switch (this.CurveCoordinateSystem)
+            //{
+            //    case ECCurve.COORD_HOMOGENEOUS:
+            //    case ECCurve.COORD_LAMBDA_PROJECTIVE:
+            //    {
+            //        return CreateScaledPoint(zInv, zInv);
+            //    }
+            //    case ECCurve.COORD_JACOBIAN:
+            //    case ECCurve.COORD_JACOBIAN_CHUDNOVSKY:
+            //    case ECCurve.COORD_JACOBIAN_MODIFIED:
+            //    {
+            //        ECFieldElement zInv2 = zInv.Square(), zInv3 = zInv2.Multiply(zInv);
+            //        return CreateScaledPoint(zInv2, zInv3);
+            //    }
+            //    default:
+            //    {
+            //        throw new InvalidOperationException("not a projective coordinate system");
+            //    }
+            //}
         }
 
         public bool IsInfinity
         {
-            get { return x == null && y == null; }
+            get { return m_x == null && m_y == null; }
         }
 
         public bool IsCompressed
         {
-            get { return withCompression; }
+            get { return m_withCompression; }
         }
 
         public override bool Equals(object obj)
@@ -102,29 +228,32 @@ namespace Org.BouncyCastle.Math.EC
             return hc;
         }
 
-        /**
-         * Sets the <code>PreCompInfo</code>. Used by <code>ECMultiplier</code>s
-         * to save the precomputation for this <code>ECPoint</code> to store the
-         * precomputation result for use by subsequent multiplication.
-         * @param preCompInfo The values precomputed by the
-         * <code>ECMultiplier</code>.
-         */
-        internal void SetPreCompInfo(
-            PreCompInfo preCompInfo)
-        {
-            this.preCompInfo = preCompInfo;
-        }
-
         public virtual byte[] GetEncoded()
         {
-            return GetEncoded(withCompression);
+            return GetEncoded(m_withCompression);
         }
 
         public abstract byte[] GetEncoded(bool compressed);
 
+        protected internal abstract bool CompressionYTilde { get; }
+
         public abstract ECPoint Add(ECPoint b);
         public abstract ECPoint Subtract(ECPoint b);
         public abstract ECPoint Negate();
+
+        public virtual ECPoint TimesPow2(int e)
+        {
+            if (e < 0)
+                throw new ArgumentException("cannot be negative", "e");
+
+            ECPoint p = this;
+            while (--e >= 0)
+            {
+                p = p.Twice();
+            }
+            return p;
+        }
+
         public abstract ECPoint Twice();
         public abstract ECPoint Multiply(BigInteger b);
 
@@ -151,41 +280,37 @@ namespace Org.BouncyCastle.Math.EC
         {
         }
 
-        protected internal abstract bool YTilde { get; }
-
         /**
          * return the field element encoded with point compression. (S 4.3.6)
          */
         public override byte[] GetEncoded(bool compressed)
         {
             if (this.IsInfinity)
+            {
                 return new byte[1];
+            }
+
+            ECPoint normed = Normalize();
 
-            // Note: some of the tests rely on calculating byte length from the field element
-            // (since the test cases use mismatching fields for curve/elements)
-            int byteLength = X9IntegerConverter.GetByteLength(x);
-            byte[] X = X9IntegerConverter.IntegerToBytes(this.X.ToBigInteger(), byteLength);
-            byte[] PO;
+            byte[] X = normed.X.GetEncoded();
 
             if (compressed)
             {
-                PO = new byte[1 + X.Length];
-
-                PO[0] = (byte)(YTilde ? 0x03 : 0x02);
+                byte[] PO = new byte[X.Length + 1];
+                PO[0] = (byte)(normed.CompressionYTilde ? 0x03 : 0x02);
+                Array.Copy(X, 0, PO, 1, X.Length);
+                return PO;
             }
-            else
-            {
-                byte[] Y = X9IntegerConverter.IntegerToBytes(this.Y.ToBigInteger(), byteLength);
-                PO = new byte[1 + X.Length + Y.Length];
 
-                PO[0] = 0x04;
+            byte[] Y = normed.Y.GetEncoded();
 
-                Y.CopyTo(PO, 1 + X.Length);
+            {
+                byte[] PO = new byte[X.Length + Y.Length + 1];
+                PO[0] = 0x04;
+                Array.Copy(X, 0, PO, 1, X.Length);
+                Array.Copy(Y, 0, PO, X.Length + 1, Y.Length);
+                return PO;
             }
-
-            X.CopyTo(PO, 1);
-
-            return PO;
         }
 
         /**
@@ -203,9 +328,9 @@ namespace Org.BouncyCastle.Math.EC
                 return this;
 
             if (k.SignValue == 0)
-                return this.curve.Infinity;
+                return Curve.Infinity;
 
-            return this.Curve.GetMultiplier().Multiply(this, k, preCompInfo);
+            return Curve.GetMultiplier().Multiply(this, k);
         }
     }
 
@@ -249,12 +374,9 @@ namespace Org.BouncyCastle.Math.EC
                 throw new ArgumentException("Exactly one of the field elements is null");
         }
 
-        protected internal override bool YTilde
+        protected internal override bool CompressionYTilde
         {
-            get
-            {
-                return this.Y.TestBitZero();
-            }
+            get { return this.Y.TestBitZero(); }
         }
 
         // B.3 pg 62
@@ -274,8 +396,8 @@ namespace Org.BouncyCastle.Math.EC
                 return Twice();
             }
 
-            ECFieldElement X1 = this.x, Y1 = this.y;
-            ECFieldElement X2 = b.x, Y2 = b.y;
+            ECFieldElement X1 = this.X, Y1 = this.Y;
+            ECFieldElement X2 = b.X, Y2 = b.Y;
 
             ECFieldElement dx = X2.Subtract(X1), dy = Y2.Subtract(Y1);
 
@@ -288,14 +410,14 @@ namespace Org.BouncyCastle.Math.EC
                 }
 
                 // this == -b, i.e. the result is the point at infinity
-                return curve.Infinity;
+                return Curve.Infinity;
             }
 
             ECFieldElement gamma = dy.Divide(dx);
             ECFieldElement X3 = gamma.Square().Subtract(X1).Subtract(X2);
             ECFieldElement Y3 = gamma.Multiply(X1.Subtract(X3)).Subtract(Y1);
 
-            return new FpPoint(curve, X3, Y3, this.withCompression);
+            return new FpPoint(Curve, X3, Y3, IsCompressed);
         }
 
         // B.3 pg 62
@@ -306,20 +428,20 @@ namespace Org.BouncyCastle.Math.EC
                 return this;
             }
 
-            ECFieldElement Y1 = this.y;
+            ECFieldElement Y1 = this.Y;
             if (Y1.IsZero) 
             {
-                return curve.Infinity;
+                return Curve.Infinity;
             }
 
-            ECFieldElement X1 = this.x;
+            ECFieldElement X1 = this.X;
 
             ECFieldElement X1Squared = X1.Square();
             ECFieldElement gamma = Three(X1Squared).Add(this.Curve.A).Divide(Two(Y1));
             ECFieldElement X3 = gamma.Square().Subtract(Two(X1));
             ECFieldElement Y3 = gamma.Multiply(X1.Subtract(X3)).Subtract(Y1);
 
-            return new FpPoint(curve, X3, Y3, this.withCompression);
+            return new FpPoint(Curve, X3, Y3, IsCompressed);
         }
 
         public override ECPoint TwicePlus(ECPoint b)
@@ -337,14 +459,14 @@ namespace Org.BouncyCastle.Math.EC
                 return Twice();
             }
 
-            ECFieldElement Y1 = this.y;
+            ECFieldElement Y1 = this.Y;
             if (Y1.IsZero)
             {
                 return b;
             }
 
-            ECFieldElement X1 = this.x;
-            ECFieldElement X2 = b.x, Y2 = b.y;
+            ECFieldElement X1 = this.X;
+            ECFieldElement X2 = b.X, Y2 = b.Y;
 
             ECFieldElement dx = X2.Subtract(X1), dy = Y2.Subtract(Y1);
 
@@ -369,7 +491,7 @@ namespace Org.BouncyCastle.Math.EC
             ECFieldElement d = X.Multiply(Two(X1).Add(X2)).Subtract(Y);
             if (d.IsZero)
             {
-                return curve.Infinity;
+                return Curve.Infinity;
             }
 
             ECFieldElement D = d.Multiply(dx);
@@ -379,27 +501,27 @@ namespace Org.BouncyCastle.Math.EC
             ECFieldElement X4 = (L2.Subtract(L1)).Multiply(L1.Add(L2)).Add(X2);
             ECFieldElement Y4 = (X1.Subtract(X4)).Multiply(L2).Subtract(Y1);
 
-            return new FpPoint(curve, X4, Y4, this.withCompression);
+            return new FpPoint(Curve, X4, Y4, IsCompressed);
         }
 
         public override ECPoint ThreeTimes()
         {
-            if (this.IsInfinity || this.y.IsZero)
+            if (IsInfinity || this.Y.IsZero)
             {
                 return this;
             }
 
-            ECFieldElement X1 = this.x, Y1 = this.y;
+            ECFieldElement X1 = this.X, Y1 = this.Y;
 
             ECFieldElement _2Y1 = Two(Y1);
             ECFieldElement X = _2Y1.Square();
-            ECFieldElement Z = Three(X1.Square()).Add(this.Curve.A);
+            ECFieldElement Z = Three(X1.Square()).Add(Curve.A);
             ECFieldElement Y = Z.Square();
 
             ECFieldElement d = Three(X1).Multiply(X).Subtract(Y);
             if (d.IsZero)
             {
-                return this.Curve.Infinity;
+                return Curve.Infinity;
             }
 
             ECFieldElement D = d.Multiply(_2Y1);
@@ -409,7 +531,7 @@ namespace Org.BouncyCastle.Math.EC
 
             ECFieldElement X4 = (L2.Subtract(L1)).Multiply(L1.Add(L2)).Add(X1);
             ECFieldElement Y4 = (X1.Subtract(X4)).Multiply(L2).Subtract(Y1);
-            return new FpPoint(curve, X4, Y4, this.withCompression);
+            return new FpPoint(Curve, X4, Y4, IsCompressed);
         }
 
         protected virtual ECFieldElement Two(ECFieldElement x)
@@ -455,7 +577,20 @@ namespace Org.BouncyCastle.Math.EC
 
         public override ECPoint Negate()
         {
-            return new FpPoint(this.curve, this.x, this.y.Negate(), this.withCompression);
+            if (IsInfinity)
+            {
+                return this;
+            }
+
+            ECCurve curve = this.Curve;
+            //int coord = curve.CoordinateSystem;
+
+            //if (ECCurve.COORD_AFFINE != coord)
+            //{
+            //    return new FpPoint(curve, X, Y.Negate(), this.m_zs, IsCompressed);
+            //}
+
+            return new FpPoint(curve, X, Y.Negate(), IsCompressed);
         }
     }
 
@@ -499,10 +634,10 @@ namespace Org.BouncyCastle.Math.EC
             if (x != null)
             {
                 // Check if x and y are elements of the same field
-                F2mFieldElement.CheckFieldElements(this.x, this.y);
+                F2mFieldElement.CheckFieldElements(x, y);
 
                 // Check if x and a are elements of the same field
-                F2mFieldElement.CheckFieldElements(this.x, this.curve.A);
+                F2mFieldElement.CheckFieldElements(x, curve.A);
             }
         }
 
@@ -516,7 +651,7 @@ namespace Org.BouncyCastle.Math.EC
         {
         }
 
-        protected internal override bool YTilde
+        protected internal override bool CompressionYTilde
         {
             get
             {
@@ -539,7 +674,7 @@ namespace Org.BouncyCastle.Math.EC
             ECPoint	b)
         {
             // Check, if points are on the same curve
-            if (!a.curve.Equals(b.curve))
+            if (!a.Curve.Equals(b.Curve))
                 throw new ArgumentException("Only points on the same curve can be added or subtracted");
 
 //			F2mFieldElement.CheckFieldElements(a.x, b.x);
@@ -575,28 +710,28 @@ namespace Org.BouncyCastle.Math.EC
             F2mFieldElement y2 = (F2mFieldElement) b.Y;
 
             // Check if b == this or b == -this
-            if (this.x.Equals(x2))
+            if (this.X.Equals(x2))
             {
                 // this == b, i.e. this must be doubled
-                if (this.y.Equals(y2))
+                if (this.Y.Equals(y2))
                     return (F2mPoint) this.Twice();
 
                 // this = -other, i.e. the result is the point at infinity
-                return (F2mPoint) this.curve.Infinity;
+                return (F2mPoint) Curve.Infinity;
             }
 
-            ECFieldElement xSum = this.x.Add(x2);
+            ECFieldElement xSum = this.X.Add(x2);
 
             F2mFieldElement lambda
-                = (F2mFieldElement)(this.y.Add(y2)).Divide(xSum);
+                = (F2mFieldElement)(this.Y.Add(y2)).Divide(xSum);
 
             F2mFieldElement x3
-                = (F2mFieldElement)lambda.Square().Add(lambda).Add(xSum).Add(this.curve.A);
+                = (F2mFieldElement)lambda.Square().Add(lambda).Add(xSum).Add(Curve.A);
 
             F2mFieldElement y3
-                = (F2mFieldElement)lambda.Multiply(this.x.Add(x3)).Add(x3).Add(this.y);
+                = (F2mFieldElement)lambda.Multiply(this.X.Add(x3)).Add(x3).Add(this.Y);
 
-            return new F2mPoint(curve, x3, y3, withCompression);
+            return new F2mPoint(Curve, x3, y3, IsCompressed);
         }
 
         /* (non-Javadoc)
@@ -639,21 +774,34 @@ namespace Org.BouncyCastle.Math.EC
 
             // if x1 == 0, then (x1, y1) == (x1, x1 + y1)
             // and hence this = -this and thus 2(x1, y1) == infinity
-            if (this.x.IsZero)
-                return this.curve.Infinity;
+            if (this.X.IsZero)
+            {
+                return Curve.Infinity;
+            }
 
-            F2mFieldElement lambda = (F2mFieldElement) this.x.Add(this.y.Divide(this.x));
-            F2mFieldElement x2 = (F2mFieldElement)lambda.Square().Add(lambda).Add(this.curve.A);
-            ECFieldElement ONE = this.curve.FromBigInteger(BigInteger.One);
-            F2mFieldElement y2 = (F2mFieldElement)this.x.Square().Add(
+            F2mFieldElement lambda = (F2mFieldElement) this.X.Add(this.Y.Divide(this.X));
+            F2mFieldElement x2 = (F2mFieldElement)lambda.Square().Add(lambda).Add(Curve.A);
+            ECFieldElement ONE = Curve.FromBigInteger(BigInteger.One);
+            F2mFieldElement y2 = (F2mFieldElement)this.X.Square().Add(
                 x2.Multiply(lambda.Add(ONE)));
 
-            return new F2mPoint(this.curve, x2, y2, withCompression);
+            return new F2mPoint(Curve, x2, y2, IsCompressed);
         }
 
         public override ECPoint Negate()
         {
-            return new F2mPoint(curve, this.x, this.x.Add(this.y), withCompression);
+            if (IsInfinity)
+            {
+                return this;
+            }
+
+            ECFieldElement X1 = this.X;
+            if (X1.IsZero)
+            {
+                return this;
+            }
+
+            return new F2mPoint(Curve, X1, X1.Add(this.Y), IsCompressed);
         }
     }
 }
diff --git a/crypto/src/math/ec/multiplier/ECMultiplier.cs b/crypto/src/math/ec/multiplier/ECMultiplier.cs
index ad576ff55..8d6136b34 100644
--- a/crypto/src/math/ec/multiplier/ECMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/ECMultiplier.cs
@@ -1,18 +1,18 @@
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
-	/**
-	* Interface for classes encapsulating a point multiplication algorithm
-	* for <code>ECPoint</code>s.
-	*/
-	public interface ECMultiplier
-	{
-		/**
-		* Multiplies the <code>ECPoint p</code> by <code>k</code>, i.e.
-		* <code>p</code> is added <code>k</code> times to itself.
-		* @param p The <code>ECPoint</code> to be multiplied.
-		* @param k The factor by which <code>p</code> i multiplied.
-		* @return <code>p</code> multiplied by <code>k</code>.
-		*/
-		ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo);
-	}
+    /**
+    * Interface for classes encapsulating a point multiplication algorithm
+    * for <code>ECPoint</code>s.
+    */
+    public interface ECMultiplier
+    {
+        /**
+         * Multiplies the <code>ECPoint p</code> by <code>k</code>, i.e.
+         * <code>p</code> is added <code>k</code> times to itself.
+         * @param p The <code>ECPoint</code> to be multiplied.
+         * @param k The factor by which <code>p</code> is multiplied.
+         * @return <code>p</code> multiplied by <code>k</code>.
+         */
+        ECPoint Multiply(ECPoint p, BigInteger k);
+    }
 }
diff --git a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs
index 3453e5600..e7efa2a44 100644
--- a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs
@@ -1,38 +1,27 @@
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
     /**
-    * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm.
-    */
-    internal class FpNafMultiplier
+     * Class implementing the NAF (Non-Adjacent Form) multiplication algorithm (left-to-right).
+     */
+    public class FpNafMultiplier
         : ECMultiplier
     {
-        /**
-        * D.3.2 pg 101
-        * @see org.bouncycastle.math.ec.multiplier.ECMultiplier#multiply(org.bouncycastle.math.ec.ECPoint, java.math.BigInteger)
-        */
-        public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo)
+        public virtual ECPoint Multiply(ECPoint p, BigInteger k)
         {
-            // TODO Probably should try to add this
-            // BigInteger e = k.Mod(n); // n == order of p
-            BigInteger e = k;
-            BigInteger h = e.Multiply(BigInteger.Three);
+            int[] naf = WNafUtilities.GenerateCompactNaf(k);
 
-            ECPoint neg = p.Negate();
-            ECPoint R = p;
+            ECPoint addP = p.Normalize(), subP = addP.Negate();
 
-            for (int i = h.BitLength - 2; i > 0; --i)
-            {             
-                bool hBit = h.TestBit(i);
-                bool eBit = e.TestBit(i);
+            ECPoint R = p.Curve.Infinity;
 
-                if (hBit == eBit)
-                {
-                    R = R.Twice();
-                }
-                else
-                {
-                    R = R.TwicePlus(hBit ? p : neg);
-                }
+            int i = naf.Length;
+            while (--i >= 0)
+            {
+                int ni = naf[i];
+                int digit = ni >> 16, zeroes = ni & 0xFFFF;
+
+                R = R.TwicePlus(digit < 0 ? subP : addP);
+                R = R.TimesPow2(zeroes);
             }
 
             return R;
diff --git a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
index cdccffc2d..a3763848e 100644
--- a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
@@ -1,30 +1,37 @@
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
-	internal class ReferenceMultiplier
-		: ECMultiplier
-	{
-		/**
-		* Simple shift-and-add multiplication. Serves as reference implementation
-		* to verify (possibly faster) implementations in
-		* {@link org.bouncycastle.math.ec.ECPoint ECPoint}.
-		* 
-		* @param p The point to multiply.
-		* @param k The factor by which to multiply.
-		* @return The result of the point multiplication <code>k * p</code>.
-		*/
-		public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo)
-		{
-			ECPoint q = p.Curve.Infinity;
-			int t = k.BitLength;
-			for (int i = 0; i < t; i++)
-			{
-				if (k.TestBit(i))
-				{
-					q = q.Add(p);
-				}
-				p = p.Twice();
-			}
-			return q;
-		}
-	}
+    public class ReferenceMultiplier
+        : ECMultiplier
+    {
+        /**
+         * Simple shift-and-add multiplication. Serves as reference implementation
+         * to verify (possibly faster) implementations in
+         * {@link org.bouncycastle.math.ec.ECPoint ECPoint}.
+         * 
+         * @param p The point to multiply.
+         * @param k The factor by which to multiply.
+         * @return The result of the point multiplication <code>k * p</code>.
+         */
+        public virtual ECPoint Multiply(ECPoint p, BigInteger k)
+        {
+            ECPoint q = p.Curve.Infinity;
+            int t = k.BitLength;
+            if (t > 0)
+            {
+                if (k.TestBit(0))
+                {
+                    q = p;
+                }
+                for (int i = 1; i < t; i++)
+                {
+                    p = p.Twice();
+                    if (k.TestBit(i))
+                    {
+                        q = q.Add(p);
+                    }
+                }
+            }
+            return q;
+        }
+    }
 }
diff --git a/crypto/src/math/ec/multiplier/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafMultiplier.cs
index 570ceee95..c2bb8c465 100644
--- a/crypto/src/math/ec/multiplier/WNafMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/WNafMultiplier.cs
@@ -6,238 +6,98 @@ namespace Org.BouncyCastle.Math.EC.Multiplier
     * Class implementing the WNAF (Window Non-Adjacent Form) multiplication
     * algorithm.
     */
-    internal class WNafMultiplier
-        : ECMultiplier 
+    public class WNafMultiplier
+        : ECMultiplier
     {
         /**
-        * Computes the Window NAF (non-adjacent Form) of an integer.
-        * @param width The width <code>w</code> of the Window NAF. The width is
-        * defined as the minimal number <code>w</code>, such that for any
-        * <code>w</code> consecutive digits in the resulting representation, at
-        * most one is non-zero.
-        * @param k The integer of which the Window NAF is computed.
-        * @return The Window NAF of the given width, such that the following holds:
-        * <code>k = &#8722;<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup>
-        * </code>, where the <code>k<sub>i</sub></code> denote the elements of the
-        * returned <code>sbyte[]</code>.
-        */
-        public sbyte[] WindowNaf(sbyte width, BigInteger k)
+         * Multiplies <code>this</code> by an integer <code>k</code> using the
+         * Window NAF method.
+         * @param k The integer by which <code>this</code> is multiplied.
+         * @return A new <code>ECPoint</code> which equals <code>this</code>
+         * multiplied by <code>k</code>.
+         */
+        public virtual ECPoint Multiply(ECPoint p, BigInteger k)
         {
-            // The window NAF is at most 1 element longer than the binary
-            // representation of the integer k. sbyte can be used instead of short or
-            // int unless the window width is larger than 8. For larger width use
-            // short or int. However, a width of more than 8 is not efficient for
-            // m = log2(q) smaller than 2305 Bits. Note: Values for m larger than
-            // 1000 Bits are currently not used in practice.
-            sbyte[] wnaf = new sbyte[k.BitLength + 1];
+            // Clamp the window width in the range [2, 16]
+            int width = System.Math.Max(2, System.Math.Min(16, GetWindowSize(k.BitLength)));
 
-            // 2^width as short and BigInteger
-            short pow2wB = (short)(1 << width);
-            BigInteger pow2wBI = BigInteger.ValueOf(pow2wB);
+            WNafPreCompInfo wnafPreCompInfo = WNafUtilities.Precompute(p, width, true);
+            ECPoint[] preComp = wnafPreCompInfo.PreComp;
+            ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg;
 
-            int i = 0;
+            int[] wnaf = WNafUtilities.GenerateCompactWindowNaf(width, k);
 
-            // The actual length of the WNAF
-            int length = 0;
+            ECPoint R = p.Curve.Infinity;
 
-            // while k >= 1
-            while (k.SignValue > 0)
-            {
-                // if k is odd
-                if (k.TestBit(0))
-                {
-                    // k Mod 2^width
-                    BigInteger remainder = k.Mod(pow2wBI);
-
-                    // if remainder > 2^(width - 1) - 1
-                    if (remainder.TestBit(width - 1))
-                    {
-                        wnaf[i] = (sbyte)(remainder.IntValue - pow2wB);
-                    }
-                    else
-                    {
-                        wnaf[i] = (sbyte)remainder.IntValue;
-                    }
-                    // wnaf[i] is now in [-2^(width-1), 2^(width-1)-1]
-
-                    k = k.Subtract(BigInteger.ValueOf(wnaf[i]));
-                    length = i;
-                }
-                else
-                {
-                    wnaf[i] = 0;
-                }
-
-                // k = k/2
-                k = k.ShiftRight(1);
-                i++;
-            }
-
-            length++;
-
-            // Reduce the WNAF array to its actual length
-            sbyte[] wnafShort = new sbyte[length];
-            Array.Copy(wnaf, 0, wnafShort, 0, length);
-            return wnafShort;
-        }
+            int i = wnaf.Length;
 
-        /**
-        * Multiplies <code>this</code> by an integer <code>k</code> using the
-        * Window NAF method.
-        * @param k The integer by which <code>this</code> is multiplied.
-        * @return A new <code>ECPoint</code> which equals <code>this</code>
-        * multiplied by <code>k</code>.
-        */
-        public ECPoint Multiply(ECPoint p, BigInteger k, PreCompInfo preCompInfo)
-        {
-            WNafPreCompInfo wnafPreCompInfo;
-
-            if ((preCompInfo != null) && (preCompInfo is WNafPreCompInfo))
+            /*
+             * NOTE This code optimizes the first window using the precomputed points to substitute an
+             * addition for 2 or more doublings.
+             */
+            if (i > 1)
             {
-                wnafPreCompInfo = (WNafPreCompInfo)preCompInfo;
-            }
-            else
-            {
-                // Ignore empty PreCompInfo or PreCompInfo of incorrect type
-                wnafPreCompInfo = new WNafPreCompInfo();
-            }
-
-            // floor(log2(k))
-            int m = k.BitLength;
+                int wi = wnaf[--i];
+                int digit = wi >> 16, zeroes = wi & 0xFFFF;
+
+                int n = System.Math.Abs(digit);
+                ECPoint[] table = digit < 0 ? preCompNeg : preComp;
+
+                /*
+                 * NOTE: We use this optimization conservatively, since some coordinate systems have
+                 * significantly cheaper doubling relative to addition.
+                 * 
+                 * (n << 2) selects precomputed values in the lower half of the table
+                 * (n << 3) selects precomputed values in the lower quarter of the table
+                 */
+                //if ((n << 2) < (1 << width))
+                if ((n << 3) < (1 << width))
+                {
+                    int highest = LongArray.BitLengths[n];
+                    int lowBits =  n ^ (1 << (highest - 1));
+                    int scale = width - highest;
 
-            // width of the Window NAF
-            sbyte width;
+                    int i1 = ((1 << (width - 1)) - 1);
+                    int i2 = (lowBits << scale) + 1;
+                    R = table[i1 >> 1].Add(table[i2 >> 1]);
 
-            // Required length of precomputation array
-            int reqPreCompLen;
+                    zeroes -= scale;
 
-            // Determine optimal width and corresponding length of precomputation
-            // array based on literature values
-            if (m < 13)
-            {
-                width = 2;
-                reqPreCompLen = 1;
-            }
-            else
-            {
-                if (m < 41)
-                {
-                    width = 3;
-                    reqPreCompLen = 2;
+    //              Console.WriteLine("Optimized: 2^" + scale + " * " + n + " = " + i1 + " + " + i2);
                 }
                 else
                 {
-                    if (m < 121)
-                    {
-                        width = 4;
-                        reqPreCompLen = 4;
-                    }
-                    else
-                    {
-                        if (m < 337)
-                        {
-                            width = 5;
-                            reqPreCompLen = 8;
-                        }
-                        else
-                        {
-                            if (m < 897)
-                            {
-                                width = 6;
-                                reqPreCompLen = 16;
-                            }
-                            else
-                            {
-                                if (m < 2305)
-                                {
-                                    width = 7;
-                                    reqPreCompLen = 32;
-                                }
-                                else 
-                                {
-                                    width = 8;
-                                    reqPreCompLen = 127;
-                                }
-                            }
-                        }
-                    }
+                    R = table[n >> 1];
                 }
-            }
-
-            // The length of the precomputation array
-            int preCompLen = 1;
 
-            ECPoint[] preComp = wnafPreCompInfo.GetPreComp();
-            ECPoint twiceP = wnafPreCompInfo.GetTwiceP();
-
-            // Check if the precomputed ECPoints already exist
-            if (preComp == null)
-            {
-                // Precomputation must be performed from scratch, create an empty
-                // precomputation array of desired length
-                preComp = new ECPoint[]{ p };
-            }
-            else
-            {
-                // Take the already precomputed ECPoints to start with
-                preCompLen = preComp.Length;
+                R = R.TimesPow2(zeroes);
             }
 
-            if (twiceP == null)
+            while (i > 0)
             {
-                // Compute twice(p)
-                twiceP = p.Twice();
-            }
+                int wi = wnaf[--i];
+                int digit = wi >> 16, zeroes = wi & 0xFFFF;
 
-            if (preCompLen < reqPreCompLen)
-            {
-                // Precomputation array must be made bigger, copy existing preComp
-                // array into the larger new preComp array
-                ECPoint[] oldPreComp = preComp;
-                preComp = new ECPoint[reqPreCompLen];
-                Array.Copy(oldPreComp, 0, preComp, 0, preCompLen);
+                int n = System.Math.Abs(digit);
+                ECPoint[] table = digit < 0 ? preCompNeg : preComp;
+                ECPoint r = table[n >> 1];
 
-                for (int i = preCompLen; i < reqPreCompLen; i++)
-                {
-                    // Compute the new ECPoints for the precomputation array.
-                    // The values 1, 3, 5, ..., 2^(width-1)-1 times p are
-                    // computed
-                    preComp[i] = twiceP.Add(preComp[i - 1]);
-                }            
+                R = R.TwicePlus(r);
+                R = R.TimesPow2(zeroes);
             }
 
-            // Compute the Window NAF of the desired width
-            sbyte[] wnaf = WindowNaf(width, k);
-            int l = wnaf.Length;
-
-            // Apply the Window NAF to p using the precomputed ECPoint values.
-            ECPoint q = p.Curve.Infinity;
-            for (int i = l - 1; i >= 0; i--)
-            {
-                int wi = wnaf[i];
-                if (wi == 0)
-                {
-                    q = q.Twice();
-                }
-                else
-                {
-                    int n = System.Math.Abs(wi);
-                    ECPoint r = preComp[n >> 1];
-                    if (wi < 0)
-                    {
-                        r = r.Negate();
-                    }
-
-                    q = q.TwicePlus(r);
-                }
-            }
+            return R;
+        }
 
-            // Set PreCompInfo in ECPoint, such that it is available for next
-            // multiplication.
-            wnafPreCompInfo.SetPreComp(preComp);
-            wnafPreCompInfo.SetTwiceP(twiceP);
-            p.SetPreCompInfo(wnafPreCompInfo);
-            return q;
+        /**
+         * Determine window width to use for a scalar multiplication of the given size.
+         * 
+         * @param bits the bit-length of the scalar to multiply by
+         * @return the window size to use
+         */
+        protected virtual int GetWindowSize(int bits)
+        {
+            return WNafUtilities.GetWindowSize(bits);
         }
     }
 }
diff --git a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
index d9305dace..7e0a73154 100644
--- a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
+++ b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
@@ -1,46 +1,46 @@
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
-	/**
-	* Class holding precomputation data for the WNAF (Window Non-Adjacent Form)
-	* algorithm.
-	*/
-	internal class WNafPreCompInfo
-		: PreCompInfo 
-	{
-		/**
-		* Array holding the precomputed <code>ECPoint</code>s used for the Window
-		* NAF multiplication in <code>
-		* {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply()
-		* WNafMultiplier.multiply()}</code>.
-		*/
-		private ECPoint[] preComp = null;
+    /**
+    * Class holding precomputation data for the WNAF (Window Non-Adjacent Form)
+    * algorithm.
+    */
+    public class WNafPreCompInfo
+        : PreCompInfo 
+    {
+        /**
+         * Array holding the precomputed <code>ECPoint</code>s used for a Window
+         * NAF multiplication.
+         */
+        protected ECPoint[] m_preComp = null;
 
-		/**
-		* Holds an <code>ECPoint</code> representing twice(this). Used for the
-		* Window NAF multiplication in <code>
-		* {@link org.bouncycastle.math.ec.multiplier.WNafMultiplier.multiply()
-		* WNafMultiplier.multiply()}</code>.
-		*/
-		private ECPoint twiceP = null;
+        /**
+         * Array holding the negations of the precomputed <code>ECPoint</code>s used
+         * for a Window NAF multiplication.
+         */
+        protected ECPoint[] m_preCompNeg = null;
 
-		internal ECPoint[] GetPreComp()
-		{
-			return preComp;
-		}
+        /**
+         * Holds an <code>ECPoint</code> representing Twice(this). Used for the
+         * Window NAF multiplication to create or extend the precomputed values.
+         */
+        protected ECPoint m_twice = null;
 
-		internal void SetPreComp(ECPoint[] preComp)
-		{
-			this.preComp = preComp;
-		}
+        public virtual ECPoint[] PreComp
+        {
+            get { return m_preComp; }
+            set { this.m_preComp = value; }
+        }
 
-		internal ECPoint GetTwiceP()
-		{
-			return twiceP;
-		}
+        public virtual ECPoint[] PreCompNeg
+        {
+            get { return m_preCompNeg; }
+            set { this.m_preCompNeg = value; }
+        }
 
-		internal void SetTwiceP(ECPoint twiceThis)
-		{
-			this.twiceP = twiceThis;
-		}
-	}
+        public virtual ECPoint Twice
+        {
+            get { return m_twice; }
+            set { this.m_twice = value; }
+        }
+    }
 }
diff --git a/crypto/src/math/ec/multiplier/WNafUtilities.cs b/crypto/src/math/ec/multiplier/WNafUtilities.cs
new file mode 100644
index 000000000..d8b0c6e6a
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/WNafUtilities.cs
@@ -0,0 +1,394 @@
+using System;
+
+using Org.BouncyCastle.Math;
+
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+    public abstract class WNafUtilities
+    {
+        private static int[] DEFAULT_WINDOW_SIZE_CUTOFFS = new int[]{ 13, 41, 121, 337, 897, 2305 };
+
+        public static int[] GenerateCompactNaf(BigInteger k)
+        {
+            if ((k.BitLength >> 16) != 0)
+                throw new ArgumentException("must have bitlength < 2^16", "k");
+
+            BigInteger _3k = k.ShiftLeft(1).Add(k);
+
+            int digits = _3k.BitLength - 1;
+            int[] naf = new int[(digits + 1) >> 1];
+
+            int length = 0, zeroes = 0;
+            for (int i = 1; i <= digits; ++i)
+            {
+                bool _3kBit = _3k.TestBit(i);
+                bool kBit = k.TestBit(i);
+
+                if (_3kBit == kBit)
+                {
+                    ++zeroes;
+                }
+                else
+                {
+                    int digit  = kBit ? -1 : 1;
+                    naf[length++] = (digit << 16) | zeroes;
+                    zeroes = 0;
+                }
+            }
+
+            if (naf.Length > length)
+            {
+                naf = Trim(naf, length);
+            }
+
+            return naf;
+        }
+
+        public static int[] GenerateCompactWindowNaf(int width, BigInteger k)
+        {
+            if (width == 2)
+            {
+                return GenerateCompactNaf(k);
+            }
+
+            if (width < 2 || width > 16)
+                throw new ArgumentException("must be in the range [2, 16]", "width");
+            if ((k.BitLength >> 16) != 0)
+                throw new ArgumentException("must have bitlength < 2^16", "k");
+
+            int[] wnaf = new int[k.BitLength / width + 1];
+
+            // 2^width and a mask and sign bit set accordingly
+            int pow2 = 1 << width;
+            int mask = pow2 - 1;
+            int sign = pow2 >> 1;
+
+            bool carry = false;
+            int length = 0, pos = 0;
+
+            while (pos <= k.BitLength)
+            {
+                if (k.TestBit(pos) == carry)
+                {
+                    ++pos;
+                    continue;
+                }
+
+                k = k.ShiftRight(pos);
+
+                int digit = k.IntValue & mask;
+                if (carry)
+                {
+                    ++digit;
+                }
+
+                carry = (digit & sign) != 0;
+                if (carry)
+                {
+                    digit -= pow2;
+                }
+
+                int zeroes = length > 0 ? pos - 1 : pos;
+                wnaf[length++] = (digit << 16) | zeroes;
+                pos = width;
+            }
+
+            // Reduce the WNAF array to its actual length
+            if (wnaf.Length > length)
+            {
+                wnaf = Trim(wnaf, length);
+            }
+
+            return wnaf;
+        }
+
+        public static byte[] GenerateJsf(BigInteger g, BigInteger h)
+        {
+            int digits = System.Math.Max(g.BitLength, h.BitLength) + 1;
+            byte[] jsf = new byte[digits];
+
+            BigInteger k0 = g, k1 = h;
+            int j = 0, d0 = 0, d1 = 0;
+
+            int offset = 0;
+            while ((d0 | d1) != 0 || k0.BitLength > offset || k1.BitLength > offset)
+            {
+                int n0 = ((int)((uint)k0.IntValue >> offset) + d0) & 7;
+                int n1 = ((int)((uint)k1.IntValue >> offset) + d1) & 7;
+
+                int u0 = n0 & 1;
+                if (u0 != 0)
+                {
+                    u0 -= (n0 & 2);
+                    if ((n0 + u0) == 4 && (n1 & 3) == 2)
+                    {
+                        u0 = -u0;
+                    }
+                }
+
+                int u1 = n1 & 1;
+                if (u1 != 0)
+                {
+                    u1 -= (n1 & 2);
+                    if ((n1 + u1) == 4 && (n0 & 3) == 2)
+                    {
+                        u1 = -u1;
+                    }
+                }
+
+                if ((d0 << 1) == 1 + u0)
+                {
+                    d0 ^= 1;
+                }
+                if ((d1 << 1) == 1 + u1)
+                {
+                    d1 ^= 1;
+                }
+
+                if (++offset == 30)
+                {
+                    offset = 0;
+                    k0 = k0.ShiftRight(30);
+                    k1 = k1.ShiftRight(30);
+                }
+
+                jsf[j++] = (byte)((u0 << 4) | (u1 & 0xF));
+            }
+
+            // Reduce the JSF array to its actual length
+            if (jsf.Length > j)
+            {
+                jsf = Trim(jsf, j);
+            }
+
+            return jsf;
+        }
+
+        public static byte[] GenerateNaf(BigInteger k)
+        {
+            BigInteger _3k = k.ShiftLeft(1).Add(k);
+
+            int digits = _3k.BitLength - 1;
+            byte[] naf = new byte[digits];
+
+            for (int i = 1; i <= digits; ++i)
+            {
+                bool _3kBit = _3k.TestBit(i);
+                bool kBit = k.TestBit(i);
+
+                naf[i - 1] = (byte)(_3kBit == kBit ? 0 : kBit ? -1 : 1);
+            }
+
+            return naf;
+        }
+
+        /**
+         * Computes the Window NAF (non-adjacent Form) of an integer.
+         * @param width The width <code>w</code> of the Window NAF. The width is
+         * defined as the minimal number <code>w</code>, such that for any
+         * <code>w</code> consecutive digits in the resulting representation, at
+         * most one is non-zero.
+         * @param k The integer of which the Window NAF is computed.
+         * @return The Window NAF of the given width, such that the following holds:
+         * <code>k = &sum;<sub>i=0</sub><sup>l-1</sup> k<sub>i</sub>2<sup>i</sup>
+         * </code>, where the <code>k<sub>i</sub></code> denote the elements of the
+         * returned <code>byte[]</code>.
+         */
+        public static byte[] GenerateWindowNaf(int width, BigInteger k)
+        {
+            if (width == 2)
+            {
+                return GenerateNaf(k);
+            }
+
+            if (width < 2 || width > 8)
+                throw new ArgumentException("must be in the range [2, 8]", "width");
+
+            byte[] wnaf = new byte[k.BitLength + 1];
+
+            // 2^width and a mask and sign bit set accordingly
+            int pow2 = 1 << width;
+            int mask = pow2 - 1;
+            int sign = pow2 >> 1;
+
+            bool carry = false;
+            int length = 0, pos = 0;
+
+            while (pos <= k.BitLength)
+            {
+                if (k.TestBit(pos) == carry)
+                {
+                    ++pos;
+                    continue;
+                }
+
+                k = k.ShiftRight(pos);
+
+                int digit = k.IntValue & mask;
+                if (carry)
+                {
+                    ++digit;
+                }
+
+                carry = (digit & sign) != 0;
+                if (carry)
+                {
+                    digit -= pow2;
+                }
+
+                length += (length > 0) ? pos - 1 : pos;
+                wnaf[length++] = (byte)digit;
+                pos = width;
+            }
+
+            // Reduce the WNAF array to its actual length
+            if (wnaf.Length > length)
+            {
+                wnaf = Trim(wnaf, length);
+            }
+        
+            return wnaf;
+        }
+
+        public static WNafPreCompInfo GetWNafPreCompInfo(PreCompInfo preCompInfo)
+        {
+            if ((preCompInfo != null) && (preCompInfo is WNafPreCompInfo))
+            {
+                return (WNafPreCompInfo)preCompInfo;
+            }
+
+            return new WNafPreCompInfo();
+        }
+
+        /**
+         * Determine window width to use for a scalar multiplication of the given size.
+         * 
+         * @param bits the bit-length of the scalar to multiply by
+         * @return the window size to use
+         */
+        public static int GetWindowSize(int bits)
+        {
+            return GetWindowSize(bits, DEFAULT_WINDOW_SIZE_CUTOFFS);
+        }
+
+        /**
+         * Determine window width to use for a scalar multiplication of the given size.
+         * 
+         * @param bits the bit-length of the scalar to multiply by
+         * @param windowSizeCutoffs a monotonically increasing list of bit sizes at which to increment the window width
+         * @return the window size to use
+         */
+        public static int GetWindowSize(int bits, int[] windowSizeCutoffs)
+        {
+            int w = 0;
+            for (; w < windowSizeCutoffs.Length; ++w)
+            {
+                if (bits < windowSizeCutoffs[w])
+                {
+                    break;
+                }
+            }
+            return w + 2;
+        }
+
+        public static WNafPreCompInfo Precompute(ECPoint p, int width, bool includeNegated)
+        {
+            ECCurve c = p.Curve;
+            WNafPreCompInfo wnafPreCompInfo = GetWNafPreCompInfo(c.GetPreCompInfo(p));
+            
+            ECPoint[] preComp = wnafPreCompInfo.PreComp;
+            if (preComp == null)
+            {
+                preComp = new ECPoint[]{ p };
+            }
+
+            int preCompLen = preComp.Length;
+            int reqPreCompLen = 1 << System.Math.Max(0, width - 2);
+
+            if (preCompLen < reqPreCompLen)
+            {
+                ECPoint twiceP = wnafPreCompInfo.Twice;
+                if (twiceP == null)
+                {
+                    twiceP = preComp[0].Twice().Normalize();
+                    wnafPreCompInfo.Twice = twiceP;
+                }
+
+                preComp = ResizeTable(preComp, reqPreCompLen);
+
+                /*
+                 * TODO Okeya/Sakurai paper has precomputation trick and  "Montgomery's Trick" to speed this up.
+                 * Also, co-Z arithmetic could avoid the subsequent normalization too.
+                 */
+                for (int i = preCompLen; i < reqPreCompLen; i++)
+                {
+                    /*
+                     * Compute the new ECPoints for the precomputation array. The values 1, 3, 5, ...,
+                     * 2^(width-1)-1 times p are computed
+                     */
+                    preComp[i] = twiceP.Add(preComp[i - 1]);
+                }
+
+                /*
+                 * Having oft-used operands in affine form makes operations faster.
+                 */
+                c.NormalizeAll(preComp);
+            }
+
+            wnafPreCompInfo.PreComp = preComp;
+
+            if (includeNegated)
+            {
+                ECPoint[] preCompNeg = wnafPreCompInfo.PreCompNeg;
+
+                int pos;
+                if (preCompNeg == null)
+                {
+                    pos = 0;
+                    preCompNeg = new ECPoint[reqPreCompLen]; 
+                }
+                else
+                {
+                    pos = preCompNeg.Length;
+                    if (pos < reqPreCompLen)
+                    {
+                        preCompNeg = ResizeTable(preCompNeg, reqPreCompLen);
+                    }
+                }
+
+                while (pos < reqPreCompLen)
+                {
+                    preCompNeg[pos] = preComp[pos].Negate();
+                    ++pos;
+                }
+
+                wnafPreCompInfo.PreCompNeg = preCompNeg;
+            }
+
+            c.SetPreCompInfo(p, wnafPreCompInfo);
+
+            return wnafPreCompInfo;
+        }
+
+        private static byte[] Trim(byte[] a, int length)
+        {
+            byte[] result = new byte[length];
+            Array.Copy(a, 0, result, 0, result.Length);
+            return result;
+        }
+
+        private static int[] Trim(int[] a, int length)
+        {
+            int[] result = new int[length];
+            Array.Copy(a, 0, result, 0, result.Length);
+            return result;
+        }
+
+        private static ECPoint[] ResizeTable(ECPoint[] a, int length)
+        {
+            ECPoint[] result = new ECPoint[length];
+            Array.Copy(a, 0, result, 0, a.Length);
+            return result;
+        }
+    }
+}
diff --git a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
index f1a605770..c2f78da93 100644
--- a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
+++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
@@ -4,117 +4,120 @@ using Org.BouncyCastle.Math.EC.Abc;
 
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
-	/**
-	* Class implementing the WTNAF (Window
-	* <code>&#964;</code>-adic Non-Adjacent Form) algorithm.
-	*/
-	internal class WTauNafMultiplier
-		: ECMultiplier
-	{
-		/**
-		* Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint}
-		* by <code>k</code> using the reduced <code>&#964;</code>-adic NAF (RTNAF)
-		* method.
-		* @param p The F2mPoint to multiply.
-		* @param k The integer by which to multiply <code>k</code>.
-		* @return <code>p</code> multiplied by <code>k</code>.
-		*/
-		public ECPoint Multiply(ECPoint point, BigInteger k, PreCompInfo preCompInfo)
-		{
-			if (!(point is F2mPoint))
-				throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier");
+    /**
+    * Class implementing the WTNAF (Window
+    * <code>&#964;</code>-adic Non-Adjacent Form) algorithm.
+    */
+    public class WTauNafMultiplier
+        : ECMultiplier
+    {
+        /**
+        * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint}
+        * by <code>k</code> using the reduced <code>&#964;</code>-adic NAF (RTNAF)
+        * method.
+        * @param p The F2mPoint to multiply.
+        * @param k The integer by which to multiply <code>k</code>.
+        * @return <code>p</code> multiplied by <code>k</code>.
+        */
+        public virtual ECPoint Multiply(ECPoint point, BigInteger k)
+        {
+            if (!(point is F2mPoint))
+                throw new ArgumentException("Only F2mPoint can be used in WTauNafMultiplier");
 
-			F2mPoint p = (F2mPoint)point;
+            F2mPoint p = (F2mPoint)point;
 
-			F2mCurve curve = (F2mCurve) p.Curve;
-			int m = curve.M;
-			sbyte a = (sbyte) curve.A.ToBigInteger().IntValue;
-			sbyte mu = curve.GetMu();
-			BigInteger[] s = curve.GetSi();
+            F2mCurve curve = (F2mCurve) p.Curve;
+            int m = curve.M;
+            sbyte a = (sbyte) curve.A.ToBigInteger().IntValue;
+            sbyte mu = curve.GetMu();
+            BigInteger[] s = curve.GetSi();
 
-			ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10);
+            ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10);
 
-			return MultiplyWTnaf(p, rho, preCompInfo, a, mu);
-		}
+            return MultiplyWTnaf(p, rho, curve.GetPreCompInfo(p), a, mu);
+        }
 
-		/**
-		* Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint}
-		* by an element <code>&#955;</code> of <code><b>Z</b>[&#964;]</code> using
-		* the <code>&#964;</code>-adic NAF (TNAF) method.
-		* @param p The F2mPoint to multiply.
-		* @param lambda The element <code>&#955;</code> of
-		* <code><b>Z</b>[&#964;]</code> of which to compute the
-		* <code>[&#964;]</code>-adic NAF.
-		* @return <code>p</code> multiplied by <code>&#955;</code>.
-		*/
-		private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda,
-			PreCompInfo preCompInfo, sbyte a, sbyte mu)
-		{
-			ZTauElement[] alpha;
-			if (a == 0)
-			{
-				alpha = Tnaf.Alpha0;
-			}
-			else
-			{
-				// a == 1
-				alpha = Tnaf.Alpha1;
-			}
+        /**
+        * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint}
+        * by an element <code>&#955;</code> of <code><b>Z</b>[&#964;]</code> using
+        * the <code>&#964;</code>-adic NAF (TNAF) method.
+        * @param p The F2mPoint to multiply.
+        * @param lambda The element <code>&#955;</code> of
+        * <code><b>Z</b>[&#964;]</code> of which to compute the
+        * <code>[&#964;]</code>-adic NAF.
+        * @return <code>p</code> multiplied by <code>&#955;</code>.
+        */
+        private F2mPoint MultiplyWTnaf(F2mPoint p, ZTauElement lambda,
+            PreCompInfo preCompInfo, sbyte a, sbyte mu)
+        {
+            ZTauElement[] alpha;
+            if (a == 0)
+            {
+                alpha = Tnaf.Alpha0;
+            }
+            else
+            {
+                // a == 1
+                alpha = Tnaf.Alpha1;
+            }
 
-			BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width);
+            BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width);
 
-			sbyte[]u = Tnaf.TauAdicWNaf(mu, lambda, Tnaf.Width,
-				BigInteger.ValueOf(Tnaf.Pow2Width), tw, alpha);
+            sbyte[]u = Tnaf.TauAdicWNaf(mu, lambda, Tnaf.Width,
+                BigInteger.ValueOf(Tnaf.Pow2Width), tw, alpha);
 
-			return MultiplyFromWTnaf(p, u, preCompInfo);
-		}
-	    
-		/**
-		* Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint}
-		* by an element <code>&#955;</code> of <code><b>Z</b>[&#964;]</code>
-		* using the window <code>&#964;</code>-adic NAF (TNAF) method, given the
-		* WTNAF of <code>&#955;</code>.
-		* @param p The F2mPoint to multiply.
-		* @param u The the WTNAF of <code>&#955;</code>..
-		* @return <code>&#955; * p</code>
-		*/
-		private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u,
-			PreCompInfo preCompInfo)
-		{
-			F2mCurve curve = (F2mCurve)p.Curve;
-			sbyte a = (sbyte) curve.A.ToBigInteger().IntValue;
+            return MultiplyFromWTnaf(p, u, preCompInfo);
+        }
+        
+        /**
+        * Multiplies a {@link org.bouncycastle.math.ec.F2mPoint F2mPoint}
+        * by an element <code>&#955;</code> of <code><b>Z</b>[&#964;]</code>
+        * using the window <code>&#964;</code>-adic NAF (TNAF) method, given the
+        * WTNAF of <code>&#955;</code>.
+        * @param p The F2mPoint to multiply.
+        * @param u The the WTNAF of <code>&#955;</code>..
+        * @return <code>&#955; * p</code>
+        */
+        private static F2mPoint MultiplyFromWTnaf(F2mPoint p, sbyte[] u,
+            PreCompInfo preCompInfo)
+        {
+            F2mCurve curve = (F2mCurve)p.Curve;
+            sbyte a = (sbyte) curve.A.ToBigInteger().IntValue;
 
-			F2mPoint[] pu;
-			if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo))
-			{
-				pu = Tnaf.GetPreComp(p, a);
-				p.SetPreCompInfo(new WTauNafPreCompInfo(pu));
-			}
-			else
-			{
-				pu = ((WTauNafPreCompInfo)preCompInfo).GetPreComp();
-			}
+            F2mPoint[] pu;
+            if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo))
+            {
+                pu = Tnaf.GetPreComp(p, a);
 
-			// q = infinity
-			F2mPoint q = (F2mPoint) p.Curve.Infinity;
-			for (int i = u.Length - 1; i >= 0; i--)
-			{
-				q = Tnaf.Tau(q);
-				if (u[i] != 0)
-				{
-					if (u[i] > 0)
-					{
-						q = q.AddSimple(pu[u[i]]);
-					}
-					else
-					{
-						// u[i] < 0
-						q = q.SubtractSimple(pu[-u[i]]);
-					}
-				}
-			}
+                WTauNafPreCompInfo pre = new WTauNafPreCompInfo();
+                pre.PreComp = pu;
+                curve.SetPreCompInfo(p, pre);
+            }
+            else
+            {
+                pu = ((WTauNafPreCompInfo)preCompInfo).PreComp;
+            }
 
-			return q;
-		}
-	}
+            // q = infinity
+            F2mPoint q = (F2mPoint) p.Curve.Infinity;
+            for (int i = u.Length - 1; i >= 0; i--)
+            {
+                q = Tnaf.Tau(q);
+                if (u[i] != 0)
+                {
+                    if (u[i] > 0)
+                    {
+                        q = q.AddSimple(pu[u[i]]);
+                    }
+                    else
+                    {
+                        // u[i] < 0
+                        q = q.SubtractSimple(pu[-u[i]]);
+                    }
+                }
+            }
+
+            return q;
+        }
+    }
 }
diff --git a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs
index cede4a05d..3c18404c0 100644
--- a/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs
+++ b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs
@@ -1,41 +1,24 @@
 namespace Org.BouncyCastle.Math.EC.Multiplier
 {
-	/**
-	* Class holding precomputation data for the WTNAF (Window
-	* <code>&#964;</code>-adic Non-Adjacent Form) algorithm.
-	*/
-	internal class WTauNafPreCompInfo
-		: PreCompInfo
-	{
-		/**
-		* Array holding the precomputed <code>F2mPoint</code>s used for the
-		* WTNAF multiplication in <code>
-		* {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply()
-		* WTauNafMultiplier.multiply()}</code>.
-		*/
-		private readonly F2mPoint[] preComp;
+    /**
+     * Class holding precomputation data for the WTNAF (Window
+     * <code>&#964;</code>-adic Non-Adjacent Form) algorithm.
+     */
+    public class WTauNafPreCompInfo
+        : PreCompInfo
+    {
+        /**
+         * Array holding the precomputed <code>F2mPoint</code>s used for the
+         * WTNAF multiplication in <code>
+         * {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply()
+         * WTauNafMultiplier.multiply()}</code>.
+         */
+        protected F2mPoint[] m_preComp;
 
-		/**
-		* Constructor for <code>WTauNafPreCompInfo</code>
-		* @param preComp Array holding the precomputed <code>F2mPoint</code>s
-		* used for the WTNAF multiplication in <code>
-		* {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply()
-		* WTauNafMultiplier.multiply()}</code>.
-		*/
-		internal WTauNafPreCompInfo(F2mPoint[] preComp)
-		{
-			this.preComp = preComp;
-		}
-
-		/**
-		* @return the array holding the precomputed <code>F2mPoint</code>s
-		* used for the WTNAF multiplication in <code>
-		* {@link org.bouncycastle.math.ec.multiplier.WTauNafMultiplier.multiply()
-		* WTauNafMultiplier.multiply()}</code>.
-		*/
-		internal F2mPoint[] GetPreComp()
-		{
-			return preComp;
-		}
-	}
+        public virtual F2mPoint[] PreComp
+        {
+            get { return m_preComp; }
+            set { this.m_preComp = value; }
+        }
+    }
 }