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