487 lines
9.5 KiB
C#
487 lines
9.5 KiB
C#
using System;
|
|
using System.Text;
|
|
|
|
namespace Org.BouncyCastle.Math.EC
|
|
{
|
|
internal class IntArray
|
|
: ICloneable
|
|
{
|
|
// TODO make m fixed for the IntArray, and hence compute T once and for all
|
|
|
|
// TODO Use uint's internally?
|
|
private int[] m_ints;
|
|
|
|
public IntArray(int intLen)
|
|
{
|
|
m_ints = new int[intLen];
|
|
}
|
|
|
|
private IntArray(int[] ints)
|
|
{
|
|
m_ints = ints;
|
|
}
|
|
|
|
public IntArray(BigInteger bigInt)
|
|
: this(bigInt, 0)
|
|
{
|
|
}
|
|
|
|
public IntArray(BigInteger bigInt, int minIntLen)
|
|
{
|
|
if (bigInt.SignValue == -1)
|
|
throw new ArgumentException("Only positive Integers allowed", "bigint");
|
|
|
|
if (bigInt.SignValue == 0)
|
|
{
|
|
m_ints = new int[] { 0 };
|
|
return;
|
|
}
|
|
|
|
byte[] barr = bigInt.ToByteArrayUnsigned();
|
|
int barrLen = barr.Length;
|
|
|
|
int intLen = (barrLen + 3) / 4;
|
|
m_ints = new int[System.Math.Max(intLen, minIntLen)];
|
|
|
|
int rem = barrLen % 4;
|
|
int barrI = 0;
|
|
|
|
if (0 < rem)
|
|
{
|
|
int temp = (int) barr[barrI++];
|
|
while (barrI < rem)
|
|
{
|
|
temp = temp << 8 | (int) barr[barrI++];
|
|
}
|
|
m_ints[--intLen] = temp;
|
|
}
|
|
|
|
while (intLen > 0)
|
|
{
|
|
int temp = (int) barr[barrI++];
|
|
for (int i = 1; i < 4; i++)
|
|
{
|
|
temp = temp << 8 | (int) barr[barrI++];
|
|
}
|
|
m_ints[--intLen] = temp;
|
|
}
|
|
}
|
|
|
|
public int GetUsedLength()
|
|
{
|
|
int highestIntPos = m_ints.Length;
|
|
|
|
if (highestIntPos < 1)
|
|
return 0;
|
|
|
|
// Check if first element will act as sentinel
|
|
if (m_ints[0] != 0)
|
|
{
|
|
while (m_ints[--highestIntPos] == 0)
|
|
{
|
|
}
|
|
return highestIntPos + 1;
|
|
}
|
|
|
|
do
|
|
{
|
|
if (m_ints[--highestIntPos] != 0)
|
|
{
|
|
return highestIntPos + 1;
|
|
}
|
|
}
|
|
while (highestIntPos > 0);
|
|
|
|
return 0;
|
|
}
|
|
|
|
public int BitLength
|
|
{
|
|
get
|
|
{
|
|
// JDK 1.5: see Integer.numberOfLeadingZeros()
|
|
int intLen = GetUsedLength();
|
|
if (intLen == 0)
|
|
return 0;
|
|
|
|
int last = intLen - 1;
|
|
uint highest = (uint) m_ints[last];
|
|
int bits = (last << 5) + 1;
|
|
|
|
// A couple of binary search steps
|
|
if (highest > 0x0000ffff)
|
|
{
|
|
if (highest > 0x00ffffff)
|
|
{
|
|
bits += 24;
|
|
highest >>= 24;
|
|
}
|
|
else
|
|
{
|
|
bits += 16;
|
|
highest >>= 16;
|
|
}
|
|
}
|
|
else if (highest > 0x000000ff)
|
|
{
|
|
bits += 8;
|
|
highest >>= 8;
|
|
}
|
|
|
|
while (highest > 1)
|
|
{
|
|
++bits;
|
|
highest >>= 1;
|
|
}
|
|
|
|
return bits;
|
|
}
|
|
}
|
|
|
|
private int[] resizedInts(int newLen)
|
|
{
|
|
int[] newInts = new int[newLen];
|
|
int oldLen = m_ints.Length;
|
|
int copyLen = oldLen < newLen ? oldLen : newLen;
|
|
Array.Copy(m_ints, 0, newInts, 0, copyLen);
|
|
return newInts;
|
|
}
|
|
|
|
public BigInteger ToBigInteger()
|
|
{
|
|
int usedLen = GetUsedLength();
|
|
if (usedLen == 0)
|
|
{
|
|
return BigInteger.Zero;
|
|
}
|
|
|
|
int highestInt = m_ints[usedLen - 1];
|
|
byte[] temp = new byte[4];
|
|
int barrI = 0;
|
|
bool trailingZeroBytesDone = false;
|
|
for (int j = 3; j >= 0; j--)
|
|
{
|
|
byte thisByte = (byte)((int)((uint) highestInt >> (8 * j)));
|
|
if (trailingZeroBytesDone || (thisByte != 0))
|
|
{
|
|
trailingZeroBytesDone = true;
|
|
temp[barrI++] = thisByte;
|
|
}
|
|
}
|
|
|
|
int barrLen = 4 * (usedLen - 1) + barrI;
|
|
byte[] barr = new byte[barrLen];
|
|
for (int j = 0; j < barrI; j++)
|
|
{
|
|
barr[j] = temp[j];
|
|
}
|
|
// Highest value int is done now
|
|
|
|
for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--)
|
|
{
|
|
for (int j = 3; j >= 0; j--)
|
|
{
|
|
barr[barrI++] = (byte)((int)((uint)m_ints[iarrJ] >> (8 * j)));
|
|
}
|
|
}
|
|
return new BigInteger(1, barr);
|
|
}
|
|
|
|
public void ShiftLeft()
|
|
{
|
|
int usedLen = GetUsedLength();
|
|
if (usedLen == 0)
|
|
{
|
|
return;
|
|
}
|
|
if (m_ints[usedLen - 1] < 0)
|
|
{
|
|
// highest bit of highest used byte is set, so shifting left will
|
|
// make the IntArray one byte longer
|
|
usedLen++;
|
|
if (usedLen > m_ints.Length)
|
|
{
|
|
// make the m_ints one byte longer, because we need one more
|
|
// byte which is not available in m_ints
|
|
m_ints = resizedInts(m_ints.Length + 1);
|
|
}
|
|
}
|
|
|
|
bool carry = false;
|
|
for (int i = 0; i < usedLen; i++)
|
|
{
|
|
// nextCarry is true if highest bit is set
|
|
bool nextCarry = m_ints[i] < 0;
|
|
m_ints[i] <<= 1;
|
|
if (carry)
|
|
{
|
|
// set lowest bit
|
|
m_ints[i] |= 1;
|
|
}
|
|
carry = nextCarry;
|
|
}
|
|
}
|
|
|
|
public IntArray ShiftLeft(int n)
|
|
{
|
|
int usedLen = GetUsedLength();
|
|
if (usedLen == 0)
|
|
{
|
|
return this;
|
|
}
|
|
|
|
if (n == 0)
|
|
{
|
|
return this;
|
|
}
|
|
|
|
if (n > 31)
|
|
{
|
|
throw new ArgumentException("shiftLeft() for max 31 bits "
|
|
+ ", " + n + "bit shift is not possible", "n");
|
|
}
|
|
|
|
int[] newInts = new int[usedLen + 1];
|
|
|
|
int nm32 = 32 - n;
|
|
newInts[0] = m_ints[0] << n;
|
|
for (int i = 1; i < usedLen; i++)
|
|
{
|
|
newInts[i] = (m_ints[i] << n) | (int)((uint)m_ints[i - 1] >> nm32);
|
|
}
|
|
newInts[usedLen] = (int)((uint)m_ints[usedLen - 1] >> nm32);
|
|
|
|
return new IntArray(newInts);
|
|
}
|
|
|
|
public void AddShifted(IntArray other, int shift)
|
|
{
|
|
int usedLenOther = other.GetUsedLength();
|
|
int newMinUsedLen = usedLenOther + shift;
|
|
if (newMinUsedLen > m_ints.Length)
|
|
{
|
|
m_ints = resizedInts(newMinUsedLen);
|
|
//Console.WriteLine("Resize required");
|
|
}
|
|
|
|
for (int i = 0; i < usedLenOther; i++)
|
|
{
|
|
m_ints[i + shift] ^= other.m_ints[i];
|
|
}
|
|
}
|
|
|
|
public int Length
|
|
{
|
|
get { return m_ints.Length; }
|
|
}
|
|
|
|
public bool TestBit(int n)
|
|
{
|
|
// theInt = n / 32
|
|
int theInt = n >> 5;
|
|
// theBit = n % 32
|
|
int theBit = n & 0x1F;
|
|
int tester = 1 << theBit;
|
|
return ((m_ints[theInt] & tester) != 0);
|
|
}
|
|
|
|
public void FlipBit(int n)
|
|
{
|
|
// theInt = n / 32
|
|
int theInt = n >> 5;
|
|
// theBit = n % 32
|
|
int theBit = n & 0x1F;
|
|
int flipper = 1 << theBit;
|
|
m_ints[theInt] ^= flipper;
|
|
}
|
|
|
|
public void SetBit(int n)
|
|
{
|
|
// theInt = n / 32
|
|
int theInt = n >> 5;
|
|
// theBit = n % 32
|
|
int theBit = n & 0x1F;
|
|
int setter = 1 << theBit;
|
|
m_ints[theInt] |= setter;
|
|
}
|
|
|
|
public IntArray Multiply(IntArray other, int m)
|
|
{
|
|
// Lenght of c is 2m bits rounded up to the next int (32 bit)
|
|
int t = (m + 31) >> 5;
|
|
if (m_ints.Length < t)
|
|
{
|
|
m_ints = resizedInts(t);
|
|
}
|
|
|
|
IntArray b = new IntArray(other.resizedInts(other.Length + 1));
|
|
IntArray c = new IntArray((m + m + 31) >> 5);
|
|
// IntArray c = new IntArray(t + t);
|
|
int testBit = 1;
|
|
for (int k = 0; k < 32; k++)
|
|
{
|
|
for (int j = 0; j < t; j++)
|
|
{
|
|
if ((m_ints[j] & testBit) != 0)
|
|
{
|
|
// The kth bit of m_ints[j] is set
|
|
c.AddShifted(b, j);
|
|
}
|
|
}
|
|
testBit <<= 1;
|
|
b.ShiftLeft();
|
|
}
|
|
return c;
|
|
}
|
|
|
|
// public IntArray multiplyLeftToRight(IntArray other, int m) {
|
|
// // Lenght of c is 2m bits rounded up to the next int (32 bit)
|
|
// int t = (m + 31) / 32;
|
|
// if (m_ints.Length < t) {
|
|
// m_ints = resizedInts(t);
|
|
// }
|
|
//
|
|
// IntArray b = new IntArray(other.resizedInts(other.getLength() + 1));
|
|
// IntArray c = new IntArray((m + m + 31) / 32);
|
|
// // IntArray c = new IntArray(t + t);
|
|
// int testBit = 1 << 31;
|
|
// for (int k = 31; k >= 0; k--) {
|
|
// for (int j = 0; j < t; j++) {
|
|
// if ((m_ints[j] & testBit) != 0) {
|
|
// // The kth bit of m_ints[j] is set
|
|
// c.addShifted(b, j);
|
|
// }
|
|
// }
|
|
// testBit >>>= 1;
|
|
// if (k > 0) {
|
|
// c.shiftLeft();
|
|
// }
|
|
// }
|
|
// return c;
|
|
// }
|
|
|
|
// TODO note, redPol.Length must be 3 for TPB and 5 for PPB
|
|
public void Reduce(int m, int[] redPol)
|
|
{
|
|
for (int i = m + m - 2; i >= m; i--)
|
|
{
|
|
if (TestBit(i))
|
|
{
|
|
int bit = i - m;
|
|
FlipBit(bit);
|
|
FlipBit(i);
|
|
int l = redPol.Length;
|
|
while (--l >= 0)
|
|
{
|
|
FlipBit(redPol[l] + bit);
|
|
}
|
|
}
|
|
}
|
|
m_ints = resizedInts((m + 31) >> 5);
|
|
}
|
|
|
|
public IntArray Square(int m)
|
|
{
|
|
// TODO make the table static readonly
|
|
int[] table = { 0x0, 0x1, 0x4, 0x5, 0x10, 0x11, 0x14, 0x15, 0x40,
|
|
0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55 };
|
|
|
|
int t = (m + 31) >> 5;
|
|
if (m_ints.Length < t)
|
|
{
|
|
m_ints = resizedInts(t);
|
|
}
|
|
|
|
IntArray c = new IntArray(t + t);
|
|
|
|
// TODO twice the same code, put in separate private method
|
|
for (int i = 0; i < t; i++)
|
|
{
|
|
int v0 = 0;
|
|
for (int j = 0; j < 4; j++)
|
|
{
|
|
v0 = (int)((uint) v0 >> 8);
|
|
int u = (int)((uint)m_ints[i] >> (j * 4)) & 0xF;
|
|
int w = table[u] << 24;
|
|
v0 |= w;
|
|
}
|
|
c.m_ints[i + i] = v0;
|
|
|
|
v0 = 0;
|
|
int upper = (int)((uint) m_ints[i] >> 16);
|
|
for (int j = 0; j < 4; j++)
|
|
{
|
|
v0 = (int)((uint) v0 >> 8);
|
|
int u = (int)((uint)upper >> (j * 4)) & 0xF;
|
|
int w = table[u] << 24;
|
|
v0 |= w;
|
|
}
|
|
c.m_ints[i + i + 1] = v0;
|
|
}
|
|
return c;
|
|
}
|
|
|
|
public override bool Equals(object o)
|
|
{
|
|
if (!(o is IntArray))
|
|
{
|
|
return false;
|
|
}
|
|
IntArray other = (IntArray) o;
|
|
int usedLen = GetUsedLength();
|
|
if (other.GetUsedLength() != usedLen)
|
|
{
|
|
return false;
|
|
}
|
|
for (int i = 0; i < usedLen; i++)
|
|
{
|
|
if (m_ints[i] != other.m_ints[i])
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
public override int GetHashCode()
|
|
{
|
|
int i = GetUsedLength();
|
|
int hc = i;
|
|
while (--i >= 0)
|
|
{
|
|
hc *= 17;
|
|
hc ^= m_ints[i];
|
|
}
|
|
return hc;
|
|
}
|
|
|
|
public object Clone()
|
|
{
|
|
return new IntArray((int[]) m_ints.Clone());
|
|
}
|
|
|
|
public override string ToString()
|
|
{
|
|
int usedLen = GetUsedLength();
|
|
if (usedLen == 0)
|
|
{
|
|
return "0";
|
|
}
|
|
|
|
StringBuilder sb = new StringBuilder(Convert.ToString(m_ints[usedLen - 1], 2));
|
|
for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--)
|
|
{
|
|
string hexString = Convert.ToString(m_ints[iarrJ], 2);
|
|
|
|
// Add leading zeroes, except for highest significant int
|
|
for (int i = hexString.Length; i < 8; i++)
|
|
{
|
|
hexString = "0" + hexString;
|
|
}
|
|
sb.Append(hexString);
|
|
}
|
|
return sb.ToString();
|
|
}
|
|
}
|
|
}
|