001: package org.bouncycastle.math.ec;
002:
003: import org.bouncycastle.util.Arrays;
004:
005: import java.math.BigInteger;
006:
007: class IntArray {
008: // TODO make m fixed for the IntArray, and hence compute T once and for all
009:
010: private int[] m_ints;
011:
012: public IntArray(int intLen) {
013: m_ints = new int[intLen];
014: }
015:
016: public IntArray(int[] ints) {
017: m_ints = ints;
018: }
019:
020: public IntArray(BigInteger bigInt) {
021: this (bigInt, 0);
022: }
023:
024: public IntArray(BigInteger bigInt, int minIntLen) {
025: if (bigInt.signum() == -1) {
026: throw new IllegalArgumentException(
027: "Only positive Integers allowed");
028: }
029: if (bigInt.equals(ECConstants.ZERO)) {
030: m_ints = new int[] { 0 };
031: return;
032: }
033:
034: byte[] barr = bigInt.toByteArray();
035: int barrLen = barr.length;
036: int barrStart = 0;
037: if (barr[0] == 0) {
038: // First byte is 0 to enforce highest (=sign) bit is zero.
039: // In this case ignore barr[0].
040: barrLen--;
041: barrStart = 1;
042: }
043: int intLen = (barrLen + 3) / 4;
044: if (intLen < minIntLen) {
045: m_ints = new int[minIntLen];
046: } else {
047: m_ints = new int[intLen];
048: }
049:
050: int iarrJ = intLen - 1;
051: int rem = barrLen % 4 + barrStart;
052: int temp = 0;
053: int barrI = barrStart;
054: if (barrStart < rem) {
055: for (; barrI < rem; barrI++) {
056: temp <<= 8;
057: int barrBarrI = barr[barrI];
058: if (barrBarrI < 0) {
059: barrBarrI += 256;
060: }
061: temp |= barrBarrI;
062: }
063: m_ints[iarrJ--] = temp;
064: }
065:
066: for (; iarrJ >= 0; iarrJ--) {
067: temp = 0;
068: for (int i = 0; i < 4; i++) {
069: temp <<= 8;
070: int barrBarrI = barr[barrI++];
071: if (barrBarrI < 0) {
072: barrBarrI += 256;
073: }
074: temp |= barrBarrI;
075: }
076: m_ints[iarrJ] = temp;
077: }
078: }
079:
080: public boolean isZero() {
081: return m_ints.length == 0
082: || (m_ints[0] == 0 && getUsedLength() == 0);
083: }
084:
085: public int getUsedLength() {
086: int highestIntPos = m_ints.length;
087:
088: if (highestIntPos < 1) {
089: return 0;
090: }
091:
092: // Check if first element will act as sentinel
093: if (m_ints[0] != 0) {
094: while (m_ints[--highestIntPos] == 0) {
095: }
096: return highestIntPos + 1;
097: }
098:
099: do {
100: if (m_ints[--highestIntPos] != 0) {
101: return highestIntPos + 1;
102: }
103: } while (highestIntPos > 0);
104:
105: return 0;
106: }
107:
108: public int bitLength() {
109: // JDK 1.5: see Integer.numberOfLeadingZeros()
110: int intLen = getUsedLength();
111: if (intLen == 0) {
112: return 0;
113: }
114:
115: int last = intLen - 1;
116: int highest = m_ints[last];
117: int bits = (last << 5) + 1;
118:
119: // A couple of binary search steps
120: if ((highest & 0xffff0000) != 0) {
121: if ((highest & 0xff000000) != 0) {
122: bits += 24;
123: highest >>>= 24;
124: } else {
125: bits += 16;
126: highest >>>= 16;
127: }
128: } else if (highest > 0x000000ff) {
129: bits += 8;
130: highest >>>= 8;
131: }
132:
133: while (highest != 1) {
134: ++bits;
135: highest >>>= 1;
136: }
137:
138: return bits;
139: }
140:
141: private int[] resizedInts(int newLen) {
142: int[] newInts = new int[newLen];
143: int oldLen = m_ints.length;
144: int copyLen = oldLen < newLen ? oldLen : newLen;
145: System.arraycopy(m_ints, 0, newInts, 0, copyLen);
146: return newInts;
147: }
148:
149: public BigInteger toBigInteger() {
150: int usedLen = getUsedLength();
151: if (usedLen == 0) {
152: return ECConstants.ZERO;
153: }
154:
155: int highestInt = m_ints[usedLen - 1];
156: byte[] temp = new byte[4];
157: int barrI = 0;
158: boolean trailingZeroBytesDone = false;
159: for (int j = 3; j >= 0; j--) {
160: byte this Byte = (byte) (highestInt >>> (8 * j));
161: if (trailingZeroBytesDone || (this Byte != 0)) {
162: trailingZeroBytesDone = true;
163: temp[barrI++] = this Byte;
164: }
165: }
166:
167: int barrLen = 4 * (usedLen - 1) + barrI;
168: byte[] barr = new byte[barrLen];
169: for (int j = 0; j < barrI; j++) {
170: barr[j] = temp[j];
171: }
172: // Highest value int is done now
173:
174: for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) {
175: for (int j = 3; j >= 0; j--) {
176: barr[barrI++] = (byte) (m_ints[iarrJ] >>> (8 * j));
177: }
178: }
179: return new BigInteger(1, barr);
180: }
181:
182: public void shiftLeft() {
183: int usedLen = getUsedLength();
184: if (usedLen == 0) {
185: return;
186: }
187: if (m_ints[usedLen - 1] < 0) {
188: // highest bit of highest used byte is set, so shifting left will
189: // make the IntArray one byte longer
190: usedLen++;
191: if (usedLen > m_ints.length) {
192: // make the m_ints one byte longer, because we need one more
193: // byte which is not available in m_ints
194: m_ints = resizedInts(m_ints.length + 1);
195: }
196: }
197:
198: boolean carry = false;
199: for (int i = 0; i < usedLen; i++) {
200: // nextCarry is true if highest bit is set
201: boolean nextCarry = m_ints[i] < 0;
202: m_ints[i] <<= 1;
203: if (carry) {
204: // set lowest bit
205: m_ints[i] |= 1;
206: }
207: carry = nextCarry;
208: }
209: }
210:
211: public IntArray shiftLeft(int n) {
212: int usedLen = getUsedLength();
213: if (usedLen == 0) {
214: return this ;
215: }
216:
217: if (n == 0) {
218: return this ;
219: }
220:
221: if (n > 31) {
222: throw new IllegalArgumentException(
223: "shiftLeft() for max 31 bits " + ", " + n
224: + "bit shift is not possible");
225: }
226:
227: int[] newInts = new int[usedLen + 1];
228:
229: int nm32 = 32 - n;
230: newInts[0] = m_ints[0] << n;
231: for (int i = 1; i < usedLen; i++) {
232: newInts[i] = (m_ints[i] << n) | (m_ints[i - 1] >>> nm32);
233: }
234: newInts[usedLen] = m_ints[usedLen - 1] >>> nm32;
235:
236: return new IntArray(newInts);
237: }
238:
239: public void addShifted(IntArray other, int shift) {
240: int usedLenOther = other.getUsedLength();
241: int newMinUsedLen = usedLenOther + shift;
242: if (newMinUsedLen > m_ints.length) {
243: m_ints = resizedInts(newMinUsedLen);
244: //System.out.println("Resize required");
245: }
246:
247: for (int i = 0; i < usedLenOther; i++) {
248: m_ints[i + shift] ^= other.m_ints[i];
249: }
250: }
251:
252: public int getLength() {
253: return m_ints.length;
254: }
255:
256: public boolean testBit(int n) {
257: // theInt = n / 32
258: int theInt = n >> 5;
259: // theBit = n % 32
260: int theBit = n & 0x1F;
261: int tester = 1 << theBit;
262: return ((m_ints[theInt] & tester) != 0);
263: }
264:
265: public void flipBit(int n) {
266: // theInt = n / 32
267: int theInt = n >> 5;
268: // theBit = n % 32
269: int theBit = n & 0x1F;
270: int flipper = 1 << theBit;
271: m_ints[theInt] ^= flipper;
272: }
273:
274: public void setBit(int n) {
275: // theInt = n / 32
276: int theInt = n >> 5;
277: // theBit = n % 32
278: int theBit = n & 0x1F;
279: int setter = 1 << theBit;
280: m_ints[theInt] |= setter;
281: }
282:
283: public IntArray multiply(IntArray other, int m) {
284: // Lenght of c is 2m bits rounded up to the next int (32 bit)
285: int t = (m + 31) >> 5;
286: if (m_ints.length < t) {
287: m_ints = resizedInts(t);
288: }
289:
290: IntArray b = new IntArray(other
291: .resizedInts(other.getLength() + 1));
292: IntArray c = new IntArray((m + m + 31) >> 5);
293: // IntArray c = new IntArray(t + t);
294: int testBit = 1;
295: for (int k = 0; k < 32; k++) {
296: for (int j = 0; j < t; j++) {
297: if ((m_ints[j] & testBit) != 0) {
298: // The kth bit of m_ints[j] is set
299: c.addShifted(b, j);
300: }
301: }
302: testBit <<= 1;
303: b.shiftLeft();
304: }
305: return c;
306: }
307:
308: // public IntArray multiplyLeftToRight(IntArray other, int m) {
309: // // Lenght of c is 2m bits rounded up to the next int (32 bit)
310: // int t = (m + 31) / 32;
311: // if (m_ints.length < t) {
312: // m_ints = resizedInts(t);
313: // }
314: //
315: // IntArray b = new IntArray(other.resizedInts(other.getLength() + 1));
316: // IntArray c = new IntArray((m + m + 31) / 32);
317: // // IntArray c = new IntArray(t + t);
318: // int testBit = 1 << 31;
319: // for (int k = 31; k >= 0; k--) {
320: // for (int j = 0; j < t; j++) {
321: // if ((m_ints[j] & testBit) != 0) {
322: // // The kth bit of m_ints[j] is set
323: // c.addShifted(b, j);
324: // }
325: // }
326: // testBit >>>= 1;
327: // if (k > 0) {
328: // c.shiftLeft();
329: // }
330: // }
331: // return c;
332: // }
333:
334: // TODO note, redPol.length must be 3 for TPB and 5 for PPB
335: public void reduce(int m, int[] redPol) {
336: for (int i = m + m - 2; i >= m; i--) {
337: if (testBit(i)) {
338: int bit = i - m;
339: flipBit(bit);
340: flipBit(i);
341: int l = redPol.length;
342: while (--l >= 0) {
343: flipBit(redPol[l] + bit);
344: }
345: }
346: }
347: m_ints = resizedInts((m + 31) >> 5);
348: }
349:
350: public IntArray square(int m) {
351: // TODO make the table static final
352: final int[] table = { 0x0, 0x1, 0x4, 0x5, 0x10, 0x11, 0x14,
353: 0x15, 0x40, 0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55 };
354:
355: int t = (m + 31) >> 5;
356: if (m_ints.length < t) {
357: m_ints = resizedInts(t);
358: }
359:
360: IntArray c = new IntArray(t + t);
361:
362: // TODO twice the same code, put in separate private method
363: for (int i = 0; i < t; i++) {
364: int v0 = 0;
365: for (int j = 0; j < 4; j++) {
366: v0 = v0 >>> 8;
367: int u = (m_ints[i] >>> (j * 4)) & 0xF;
368: int w = table[u] << 24;
369: v0 |= w;
370: }
371: c.m_ints[i + i] = v0;
372:
373: v0 = 0;
374: int upper = m_ints[i] >>> 16;
375: for (int j = 0; j < 4; j++) {
376: v0 = v0 >>> 8;
377: int u = (upper >>> (j * 4)) & 0xF;
378: int w = table[u] << 24;
379: v0 |= w;
380: }
381: c.m_ints[i + i + 1] = v0;
382: }
383: return c;
384: }
385:
386: public boolean equals(Object o) {
387: if (!(o instanceof IntArray)) {
388: return false;
389: }
390: IntArray other = (IntArray) o;
391: int usedLen = getUsedLength();
392: if (other.getUsedLength() != usedLen) {
393: return false;
394: }
395: for (int i = 0; i < usedLen; i++) {
396: if (m_ints[i] != other.m_ints[i]) {
397: return false;
398: }
399: }
400: return true;
401: }
402:
403: public int hashCode() {
404: int usedLen = getUsedLength();
405: int hash = 0;
406: for (int i = 0; i < usedLen; i++) {
407: hash ^= m_ints[i];
408: }
409: return hash;
410: }
411:
412: public Object clone() {
413: return new IntArray(Arrays.clone(m_ints));
414: }
415:
416: public String toString() {
417: int usedLen = getUsedLength();
418: if (usedLen == 0) {
419: return "0";
420: }
421:
422: StringBuffer sb = new StringBuffer(Integer
423: .toBinaryString(m_ints[usedLen - 1]));
424: for (int iarrJ = usedLen - 2; iarrJ >= 0; iarrJ--) {
425: String hexString = Integer.toBinaryString(m_ints[iarrJ]);
426:
427: // Add leading zeroes, except for highest significant int
428: for (int i = hexString.length(); i < 8; i++) {
429: hexString = "0" + hexString;
430: }
431: sb.append(hexString);
432: }
433: return sb.toString();
434: }
435: }
|