Initial import of old CVS repository

8 files changed, 546 insertions, 0 deletions

diff --git a/crypto/src/math/ec/multiplier/ECMultiplier.cs b/crypto/src/math/ec/multiplier/ECMultiplier.cs
new file mode 100644
index 000000000..c6d768ea8
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/ECMultiplier.cs
@@ -0,0 +1,18 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+	/**
+	* Interface for classes encapsulating a point multiplication algorithm
+	* for <code>ECPoint</code>s.
+	*/
+	internal 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);
+	}
+}
diff --git a/crypto/src/math/ec/multiplier/FpNafMultiplier.cs b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs
new file mode 100644
index 000000000..f5a98501a
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/FpNafMultiplier.cs
@@ -0,0 +1,39 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+	/**
+	* Class implementing the NAF (Non-Adjacent Form) multiplication algorithm.
+	*/
+	internal 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)
+		{
+			// 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);
+
+			ECPoint neg = p.Negate();
+			ECPoint R = p;
+
+			for (int i = h.BitLength - 2; i > 0; --i)
+			{             
+				R = R.Twice();
+
+				bool hBit = h.TestBit(i);
+				bool eBit = e.TestBit(i);
+
+				if (hBit != eBit)
+				{
+					R = R.Add(hBit ? p : neg);
+				}
+			}
+
+			return R;
+		}
+	}
+}
diff --git a/crypto/src/math/ec/multiplier/PreCompInfo.cs b/crypto/src/math/ec/multiplier/PreCompInfo.cs
new file mode 100644
index 000000000..d379508c8
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/PreCompInfo.cs
@@ -0,0 +1,11 @@
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+	/**
+	* Interface for classes storing precomputation data for multiplication
+	* algorithms. Used as a Memento (see GOF patterns) for
+	* <code>WNafMultiplier</code>.
+	*/
+	internal interface PreCompInfo
+	{
+	}
+}
diff --git a/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
new file mode 100644
index 000000000..cdccffc2d
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/ReferenceMultiplier.cs
@@ -0,0 +1,30 @@
+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;
+		}
+	}
+}
diff --git a/crypto/src/math/ec/multiplier/WNafMultiplier.cs b/crypto/src/math/ec/multiplier/WNafMultiplier.cs
new file mode 100644
index 000000000..b5cf34ba8
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/WNafMultiplier.cs
@@ -0,0 +1,241 @@
+using System;
+
+namespace Org.BouncyCastle.Math.EC.Multiplier
+{
+	/**
+	* Class implementing the WNAF (Window Non-Adjacent Form) multiplication
+	* algorithm.
+	*/
+	internal 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)
+		{
+			// 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];
+
+			// 2^width as short and BigInteger
+			short pow2wB = (short)(1 << width);
+			BigInteger pow2wBI = BigInteger.ValueOf(pow2wB);
+
+			int i = 0;
+
+			// The actual length of the WNAF
+			int length = 0;
+
+			// 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;
+		}
+
+		/**
+		* 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))
+			{
+				wnafPreCompInfo = (WNafPreCompInfo)preCompInfo;
+			}
+			else
+			{
+				// Ignore empty PreCompInfo or PreCompInfo of incorrect type
+				wnafPreCompInfo = new WNafPreCompInfo();
+			}
+
+			// floor(log2(k))
+			int m = k.BitLength;
+
+			// width of the Window NAF
+			sbyte width;
+
+			// Required length of precomputation array
+			int reqPreCompLen;
+
+			// 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;
+				}
+				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;
+								}
+							}
+						}
+					}
+				}
+			}
+
+			// 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;
+			}
+
+			if (twiceP == null)
+			{
+				// Compute twice(p)
+				twiceP = p.Twice();
+			}
+
+			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);
+
+				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]);
+				}            
+			}
+
+			// 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--)
+			{
+				q = q.Twice();
+
+				if (wnaf[i] != 0)
+				{
+					if (wnaf[i] > 0)
+					{
+						q = q.Add(preComp[(wnaf[i] - 1)/2]);
+					}
+					else
+					{
+						// wnaf[i] < 0
+						q = q.Subtract(preComp[(-wnaf[i] - 1)/2]);
+					}
+				}
+			}
+
+			// Set PreCompInfo in ECPoint, such that it is available for next
+			// multiplication.
+			wnafPreCompInfo.SetPreComp(preComp);
+			wnafPreCompInfo.SetTwiceP(twiceP);
+			p.SetPreCompInfo(wnafPreCompInfo);
+			return q;
+		}
+	}
+}
diff --git a/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
new file mode 100644
index 000000000..d9305dace
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/WNafPreCompInfo.cs
@@ -0,0 +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;
+
+		/**
+		* 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;
+
+		internal ECPoint[] GetPreComp()
+		{
+			return preComp;
+		}
+
+		internal void SetPreComp(ECPoint[] preComp)
+		{
+			this.preComp = preComp;
+		}
+
+		internal ECPoint GetTwiceP()
+		{
+			return twiceP;
+		}
+
+		internal void SetTwiceP(ECPoint twiceThis)
+		{
+			this.twiceP = twiceThis;
+		}
+	}
+}
diff --git a/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
new file mode 100644
index 000000000..f1a605770
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/WTauNafMultiplier.cs
@@ -0,0 +1,120 @@
+using System;
+
+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");
+
+			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();
+
+			ZTauElement rho = Tnaf.PartModReduction(k, m, a, s, mu, (sbyte)10);
+
+			return MultiplyWTnaf(p, rho, preCompInfo, 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;
+			}
+
+			BigInteger tw = Tnaf.GetTw(mu, Tnaf.Width);
+
+			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;
+
+			F2mPoint[] pu;
+			if ((preCompInfo == null) || !(preCompInfo is WTauNafPreCompInfo))
+			{
+				pu = Tnaf.GetPreComp(p, a);
+				p.SetPreCompInfo(new WTauNafPreCompInfo(pu));
+			}
+			else
+			{
+				pu = ((WTauNafPreCompInfo)preCompInfo).GetPreComp();
+			}
+
+			// 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
new file mode 100644
index 000000000..cede4a05d
--- /dev/null
+++ b/crypto/src/math/ec/multiplier/WTauNafPreCompInfo.cs
@@ -0,0 +1,41 @@
+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;
+
+		/**
+		* 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;
+		}
+	}
+}