001: package com.knowgate.misc;
002:
003: import java.math.*;
004:
005: /**
006: * Tiny Encryption Algorithm.
007: * <P>
008: * (The following description is from the web page for the C and Assembler source
009: * code at <A HREF="http://vader.brad.ac.uk/tea/tea.shtml"> University of Bradford
010: * Yorkshire, England - The Cryptography & Computer Communications Security
011: * Group</A>) The description is used with the permission of the authors,
012: * Dr S J Shepherd and D A G Gillies.
013: * <P>
014: * The Tiny Encryption Algorithm is one of the fastest and most efficient
015: * cryptographic algorithms in existence. It was developed by David
016: * Wheeler and Roger Needham at the Computer Laboratory of Cambridge
017: * University. It is a Feistel cipher which uses operations from mixed
018: * (orthogonal) algebraic groups - XORs and additions in this case. It
019: * encrypts 64 data bits at a time using a 128-bit key. It seems highly
020: * resistant to differential cryptanalysis, and achieves complete
021: * diffusion (where a one bit difference in the plaintext will cause
022: * approximately 32 bit differences in the ciphertext) after only six
023: * rounds. Performance on a modern desktop computer or workstation is
024: * very impressive.
025: * <P>
026: * TEA takes 64 bits of data in v[0] and v[1], and 128 bits of key in
027: * k[0] - k[3]. The result is returned in w[0] and w[1]. Returning the
028: * result separately makes implementation of cipher modes other than
029: * Electronic Code Book a little bit easier.
030: * <P>
031: * TEA can be operated in any of the modes of DES.
032: * <P>
033: * n is the number of iterations. 32 is ample, 16 is sufficient, as few
034: * as eight should be OK for most applications, especially ones where
035: * the data age quickly (real-time video, for example). The algorithm
036: * achieves good dispersion after six iterations. The iteration count
037: * can be made variable if required.
038: * <P>
039: * Note this algorithm is optimised for 32-bit CPUs with fast shift
040: * capabilities. It can very easily be ported to assembly language on
041: * most CPUs.
042: * <P>
043: * delta is chosen to be the Golden ratio ((5/4)1/2 - 1/2 ~ 0.618034)
044: * multiplied by 232. On entry to decipher(), sum is set to be delta *
045: * n. Which way round you call the functions is arbitrary: DK(EK(P)) =
046: * EK(DK(P)) where EK and DK are encryption and decryption under key K
047: * respectively.
048: * <P>
049: * Translator's notes:
050: * <UL>
051: * <LI> Although the <I>this algorithm is optimised for
052: * 32-bit CPUs with fast shift capabilities</I> Java manages to throw
053: * it all away by not providing unsigned values resulting in the excessive
054: * use of AND's to prevent sign extension on promotion of a byte
055: * to an integer.
056: * </LI>
057: * <P>
058: * <LI>
059: * The following description is taken from the
060: * Mach5 Software cryptography archives at
061: * <A HREF="http://www.mach5.com/crypto/">www.mach5.com/crypto</A>.
062: * <p><font face="Arial" size="4">Tiny Encryption Algorithm (TEA)</font><br>
063: * <font size="3" face="Arial">TEA is a cryptographic algorithm designed to minimize memory
064: * footprint, and maximize speed. However, the cryptographers from <a
065: *
066: * href="http://www.counterpane.com">Counterpane Systems</a> have <a
067: *
068: * href="http://www.cs.berkeley.edu/~daw/keysched-crypto96.ps">discovered three related-key
069: * attacks </a>on TEA, the best of which requires only 223 chosen plaintexts and one related
070: * key query. The problems arise from the overly simple key schedule. Each TEA key can be
071: * found to have three other equivalent keys, as described in <a
072: *
073: * href="http://www.cs.berkeley.edu/~daw/keysched-icics97.ps">a paper</a> by <a
074: *
075: * href="http://www.cs.berkeley.edu/~daw/">David Wagner</a>, John Kelsey, and <a
076: *
077: * href="http://www.counterpane.com/schneier.html">Bruce Schneier</a>. This precludes the
078: * possibility of using TEA as a hash function. Roger Needham and David Wheeler have proposed
079: * <a href="http://www.cl.cam.ac.uk/ftp/users/djw3/xtea.ps">extensions to TEA</a> that
080: * counters the above attacks.</font></p>
081: * </LI>
082: * </UL>
083: *
084: * <P> Example of use:
085: * <PRE>
086: * byte key[] = new BigInteger("39e858f86df9b909a8c87cb8d9ad599", 16).toByteArray();
087: * TEA t = new TEA(key);
088: * <BR>
089: * String src = "hello world!";
090: * System.out.println("input = " + src);
091: * byte plainSource[] = src.getBytes();
092: * int enc[] = t.encode(plainSource, plainSource.length);
093: * System.out.println(t.padding() + " bytes added as padding.");
094: * byte dec[] = t.decode(enc);
095: * System.out.println("output = " + new String(dec));
096: * </PRE>
097: *
098: * @author Translated by Michael Lecuyer (mjl@theorem.com) from the C Language.
099: * @version 1.0 Sep 8, 1998
100: * @since JDK1.1
101: */
102:
103: public class TEA {
104: private int _key[]; // The 128 bit key.
105: private byte _keyBytes[]; // original key as found
106: private int _padding; // amount of padding added in byte --> integer conversion.
107:
108: /**
109: * Encodes and decodes "Hello world!" for your personal pleasure.
110: */
111: public static void main(String args[]) {
112: // A simple test of TEA.
113:
114: byte key[] = new BigInteger("39e858f86df9b909a8c87cb8d9ad599",
115: 16).toByteArray();
116: TEA t = new TEA(key);
117:
118: String src = "hello world!";
119: System.out.println("input = " + src);
120: byte plainSource[] = src.getBytes();
121: int enc[] = t.encode(plainSource, plainSource.length);
122: System.out.println(t.padding() + " bytes added as padding.");
123: byte dec[] = t.decode(enc);
124: System.out.println("output = " + new String(dec));
125: }
126:
127: /**
128: * Accepts key for enciphering/deciphering.
129: *
130: * @throws ArrayIndexOutOfBoundsException if the key isn't the correct length.
131: *
132: * @param key 128 bit (16 byte) key.
133: */
134: public TEA(byte key[]) {
135: int klen = key.length;
136: _key = new int[4];
137:
138: // Incorrect key length throws exception.
139: if (klen != 16)
140: throw new ArrayIndexOutOfBoundsException(this .getClass()
141: .getName()
142: + ": Key is not 16 bytes");
143:
144: int j, i;
145: for (i = 0, j = 0; j < klen; j += 4, i++)
146: _key[i] = (key[j] << 24) | (((key[j + 1]) & 0xff) << 16)
147: | (((key[j + 2]) & 0xff) << 8)
148: | ((key[j + 3]) & 0xff);
149:
150: _keyBytes = key; // save for toString.
151: }
152:
153: /**
154: * Representation of TEA class
155: */
156: public String toString() {
157: String tea = this .getClass().getName();
158: tea += ": Tiny Encryption Algorithm (TEA) key: "
159: + dumpBytes(_keyBytes);
160: return tea;
161: }
162:
163: /**
164: * Encipher two <code>int</code>s.
165: * Replaces the original contents of the parameters with the results.
166: * The integers are usually created from 8 bytes.
167: * The usual way to collect bytes to the int array is:
168: * <PRE>
169: * byte ba[] = { .... };
170: * int v[] = new int[2];
171: * v[0] = (ba[j] << 24 ) | (((ba[j+1])&0xff) << 16) | (((ba[j+2])&0xff) << 8) | ((ba[j+3])&0xff);
172: * v[1] = (ba[j+4] << 24 ) | (((ba[j+5])&0xff) << 16) | (((ba[j+6])&0xff) << 8) | ((ba[j+7])&0xff);
173: * v = encipher(v);
174: * </PRE>
175: *
176: * @param v two <code>int</code> array as input.
177: *
178: * @return array of two <code>int</code>s, enciphered.
179: */
180: public int[] encipher(int v[]) {
181: int y = v[0];
182: int z = v[1];
183: int sum = 0;
184: int delta = 0x9E3779B9;
185: int a = _key[0];
186: int b = _key[1];
187: int c = _key[2];
188: int d = _key[3];
189: int n = 32;
190:
191: while (n-- > 0) {
192: sum += delta;
193: y += (z << 4) + a ^ z + sum ^ (z >> 5) + b;
194: z += (y << 4) + c ^ y + sum ^ (y >> 5) + d;
195: }
196:
197: v[0] = y;
198: v[1] = z;
199:
200: return v;
201: }
202:
203: /**
204: * Decipher two <code>int</code>s.
205: * Replaces the original contents of the parameters with the results.
206: * The integers are usually decocted to 8 bytes.
207: * The decoction of the <code>int</code>s to bytes can be done
208: * this way.
209: * <PRE>
210: * int x[] = decipher(ins);
211: * outb[j] = (byte)(x[0] >>> 24);
212: * outb[j+1] = (byte)(x[0] >>> 16);
213: * outb[j+2] = (byte)(x[0] >>> 8);
214: * outb[j+3] = (byte)(x[0]);
215: * outb[j+4] = (byte)(x[1] >>> 24);
216: * outb[j+5] = (byte)(x[1] >>> 16);
217: * outb[j+6] = (byte)(x[1] >>> 8);
218: * outb[j+7] = (byte)(x[1]);
219: * </PRE>
220: *
221: * @param v <code>int</code> array of 2
222: *
223: * @return deciphered <code>int</code> array of 2
224: */
225: public int[] decipher(int v[]) {
226: int y = v[0];
227: int z = v[1];
228: int sum = 0xC6EF3720;
229: int delta = 0x9E3779B9;
230: int a = _key[0];
231: int b = _key[1];
232: int c = _key[2];
233: int d = _key[3];
234: int n = 32;
235:
236: // sum = delta<<5, in general sum = delta * n
237:
238: while (n-- > 0) {
239: z -= (y << 4) + c ^ y + sum ^ (y >> 5) + d;
240: y -= (z << 4) + a ^ z + sum ^ (z >> 5) + b;
241: sum -= delta;
242: }
243:
244: v[0] = y;
245: v[1] = z;
246:
247: return v;
248: }
249:
250: /**
251: * Encipher two <code>bytes</code>s.
252: *
253: * @param v <code>byte</code> array of 2
254: *
255: * @return enciphered <code>byte</code> array of 2
256: */
257: public byte[] encipher(byte v[]) {
258: byte y = v[0];
259: byte z = v[1];
260: int sum = 0;
261: int delta = 0x9E3779B9;
262: int a = _key[0];
263: int b = _key[1];
264: int c = _key[2];
265: int d = _key[3];
266: int n = 32;
267:
268: while (n-- > 0) {
269: sum += delta;
270: y += (z << 4) + a ^ z + sum ^ (z >> 5) + b;
271: z += (y << 4) + c ^ y + sum ^ (y >> 5) + d;
272: }
273:
274: v[0] = y;
275: v[1] = z;
276:
277: return v;
278: }
279:
280: /**
281: * Decipher two <code>bytes</code>s.
282: *
283: * @param v <code>byte</code> array of 2
284: *
285: * @return decipherd <code>byte</code> array of 2
286: */
287: public byte[] decipher(byte v[]) {
288: byte y = v[0];
289: byte z = v[1];
290: int sum = 0xC6EF3720;
291: int delta = 0x9E3779B9;
292: int a = _key[0];
293: int b = _key[1];
294: int c = _key[2];
295: int d = _key[3];
296: int n = 32;
297:
298: // sum = delta<<5, in general sum = delta * n
299:
300: while (n-- > 0) {
301: z -= (y << 4) + c ^ y + sum ^ (y >> 5) + d;
302: y -= (z << 4) + a ^ z + sum ^ (z >> 5) + b;
303: sum -= delta;
304: }
305:
306: v[0] = y;
307: v[1] = z;
308:
309: return v;
310: }
311:
312: /**
313: * Byte wrapper for encoding.
314: * Converts bytes to ints.
315: * Padding will be added if required.
316: *
317: * @param b incoming <code>byte</code> array
318: *
319: * @param byte count
320: *
321: * @return integer conversion array, possibly with padding.
322: *
323: * @see #padding
324: */
325: public int[] encode(byte b[], int count) {
326: int j, i;
327: int bLen = count;
328: byte bp[] = b;
329:
330: _padding = bLen % 8;
331: if (_padding != 0) // Add some padding, if necessary.
332: {
333: _padding = 8 - (bLen % 8);
334: bp = new byte[bLen + _padding];
335: System.arraycopy(b, 0, bp, 0, bLen);
336: bLen = bp.length;
337: }
338:
339: int intCount = bLen / 4;
340: int r[] = new int[2];
341: int out[] = new int[intCount];
342:
343: for (i = 0, j = 0; j < bLen; j += 8, i += 2) {
344: // Java's unforgivable lack of unsigneds causes more bit
345: // twiddling than this language really needs.
346: r[0] = (bp[j] << 24) | (((bp[j + 1]) & 0xff) << 16)
347: | (((bp[j + 2]) & 0xff) << 8)
348: | ((bp[j + 3]) & 0xff);
349: r[1] = (bp[j + 4] << 24) | (((bp[j + 5]) & 0xff) << 16)
350: | (((bp[j + 6]) & 0xff) << 8)
351: | ((bp[j + 7]) & 0xff);
352: encipher(r);
353: out[i] = r[0];
354: out[i + 1] = r[1];
355: }
356:
357: return out;
358: }
359:
360: /**
361: * Report how much padding was done in the last encode.
362: *
363: * @return bytes of padding added
364: *
365: * @see #encode
366: */
367: public int padding() {
368: return _padding;
369: }
370:
371: /**
372: * Convert a byte array to ints and then decode.
373: * There may be some padding at the end of the byte array from
374: * the previous encode operation.
375: *
376: * @param b bytes to decode
377: * @param count number of bytes in the array to decode
378: *
379: * @return <code>byte</code> array of decoded bytes.
380: */
381: public byte[] decode(byte b[], int count) {
382: int i, j;
383:
384: int intCount = count / 4;
385: int ini[] = new int[intCount];
386: for (i = 0, j = 0; i < intCount; i += 2, j += 8) {
387: ini[i] = (b[j] << 24) | (((b[j + 1]) & 0xff) << 16)
388: | (((b[j + 2]) & 0xff) << 8) | ((b[j + 3]) & 0xff);
389: ini[i + 1] = (b[j + 4] << 24) | (((b[j + 5]) & 0xff) << 16)
390: | (((b[j + 6]) & 0xff) << 8) | ((b[j + 7]) & 0xff);
391: }
392: return decode(ini);
393: }
394:
395: /**
396: * Decode an integer array.
397: * There may be some padding at the end of the byte array from
398: * the previous encode operation.
399: *
400: * @param b bytes to decode
401: * @param count number of bytes in the array to decode
402: *
403: * @return <code>byte</code> array of decoded bytes.
404: */
405: public byte[] decode(int b[]) {
406: // create the large number and start stripping ints out, two at a time.
407: int intCount = b.length;
408:
409: byte outb[] = new byte[intCount * 4];
410: int tmp[] = new int[2];
411:
412: // decipher all the ints.
413: int i, j;
414: for (j = 0, i = 0; i < intCount; i += 2, j += 8) {
415: tmp[0] = b[i];
416: tmp[1] = b[i + 1];
417: decipher(tmp);
418: outb[j] = (byte) (tmp[0] >>> 24);
419: outb[j + 1] = (byte) (tmp[0] >>> 16);
420: outb[j + 2] = (byte) (tmp[0] >>> 8);
421: outb[j + 3] = (byte) (tmp[0]);
422: outb[j + 4] = (byte) (tmp[1] >>> 24);
423: outb[j + 5] = (byte) (tmp[1] >>> 16);
424: outb[j + 6] = (byte) (tmp[1] >>> 8);
425: outb[j + 7] = (byte) (tmp[1]);
426: }
427:
428: return outb;
429: }
430:
431: // Display some bytes in HEX.
432: //
433: private String dumpBytes(byte b[]) {
434: StringBuffer r = new StringBuffer();
435: final String hex = "0123456789ABCDEF";
436:
437: for (int i = 0; i < b.length; i++) {
438: int c = ((b[i]) >>> 4) & 0xf;
439: r.append(hex.charAt(c));
440: c = ((int) b[i] & 0xf);
441: r.append(hex.charAt(c));
442: }
443:
444: return r.toString();
445: }
446:
447: }
|