Source for gnu.javax.crypto.mac.UHash32

   1: /* UHash32.java --
   2:    Copyright (C) 2001, 2002, 2003, 2006 Free Software Foundation, Inc.
   3: 
   4: This file is a part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2 of the License, or (at
   9: your option) any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; if not, write to the Free Software
  18: Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
  19: USA
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version.  */
  37: 
  38: 
  39: package gnu.javax.crypto.mac;
  40: 
  41: import gnu.java.security.prng.IRandom;
  42: import gnu.java.security.prng.LimitReachedException;
  43: import gnu.javax.crypto.cipher.IBlockCipher;
  44: import gnu.javax.crypto.prng.UMacGenerator;
  45: 
  46: import java.io.ByteArrayOutputStream;
  47: import java.math.BigInteger;
  48: import java.security.InvalidKeyException;
  49: import java.util.HashMap;
  50: import java.util.Map;
  51: 
  52: /**
  53:  * <i>UHASH</i> is a keyed hash function, which takes as input a string of
  54:  * arbitrary length, and produces as output a string of fixed length (such as 8
  55:  * bytes). The actual output length depends on the parameter UMAC-OUTPUT-LEN.
  56:  * <p>
  57:  * <i>UHASH</i> has been shown to be <i>epsilon-ASU</i> ("Almost Strongly
  58:  * Universal"), where epsilon is a small (parameter-dependent) real number.
  59:  * Informally, saying that a keyed hash function is <i>epsilon-ASU</i> means
  60:  * that for any two distinct fixed input strings, the two outputs of the hash
  61:  * function with a random key "look almost like a pair of random strings". The
  62:  * number epsilon measures how non-random the output strings may be.
  63:  * <p>
  64:  * <i>UHASH</i> has been designed to be fast by exploiting several
  65:  * architectural features of modern commodity processors. It was specifically
  66:  * designed for use in <i>UMAC</i>. But <i>UHASH</i> is useful beyond that
  67:  * domain, and can be easily adopted for other purposes.
  68:  * <p>
  69:  * <i>UHASH</i> does its work in three layers. First, a hash function called
  70:  * <code>NH</code> is used to compress input messages into strings which are
  71:  * typically many times smaller than the input message. Second, the compressed
  72:  * message is hashed with an optimized <i>polynomial hash function</i> into a
  73:  * fixed-length 16-byte string. Finally, the 16-byte string is hashed using an
  74:  * <i>inner-product hash</i> into a string of length WORD-LEN bytes. These
  75:  * three layers are repeated (with a modified key) until the outputs total
  76:  * UMAC-OUTPUT-LEN bytes.
  77:  * <p>
  78:  * References:
  79:  * <ol>
  80:  * <li><a href="http://www.ietf.org/internet-drafts/draft-krovetz-umac-01.txt">
  81:  * UMAC</a>: Message Authentication Code using Universal Hashing.<br>
  82:  * T. Krovetz, J. Black, S. Halevi, A. Hevia, H. Krawczyk, and P. Rogaway.</li>
  83:  * </ol>
  84:  */
  85: public class UHash32
  86:     extends BaseMac
  87: {
  88:   // UMAC prime values
  89:   private static final BigInteger PRIME_19 = BigInteger.valueOf(0x7FFFFL);
  90:   private static final BigInteger PRIME_32 = BigInteger.valueOf(0xFFFFFFFBL);
  91:   private static final BigInteger PRIME_36 = BigInteger.valueOf(0xFFFFFFFFBL);
  92:   private static final BigInteger PRIME_64 = new BigInteger(1, new byte[] {
  93:       (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF,
  94:       (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xC5 });
  95:   private static final BigInteger PRIME_128 = new BigInteger(1, new byte[] {
  96:       (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF,
  97:       (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF,
  98:       (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0xFF,
  99:       (byte) 0xFF, (byte) 0xFF, (byte) 0xFF, (byte) 0x61 });
 100:   static final BigInteger TWO = BigInteger.valueOf(2L);
 101:   static final long BOUNDARY = TWO.shiftLeft(17).longValue();
 102:   // 2**64 - 2**32
 103:   static final BigInteger LOWER_RANGE = TWO.pow(64).subtract(TWO.pow(32));
 104:   // 2**128 - 2**96
 105:   static final BigInteger UPPER_RANGE = TWO.pow(128).subtract(TWO.pow(96));
 106:   static final byte[] ALL_ZEROES = new byte[32];
 107:   int streams;
 108:   L1Hash32[] l1hash;
 109: 
 110:   /** Trivial 0-arguments constructor. */
 111:   public UHash32()
 112:   {
 113:     super("uhash32");
 114:   }
 115: 
 116:   /**
 117:    * Private constructor for cloning purposes.
 118:    *
 119:    * @param that the instance to clone.
 120:    */
 121:   private UHash32(UHash32 that)
 122:   {
 123:     this();
 124: 
 125:     this.streams = that.streams;
 126:     if (that.l1hash != null)
 127:       {
 128:         this.l1hash = new L1Hash32[that.streams];
 129:         for (int i = 0; i < that.streams; i++)
 130:           if (that.l1hash[i] != null)
 131:             this.l1hash[i] = (L1Hash32) that.l1hash[i].clone();
 132:       }
 133:   }
 134: 
 135:   /**
 136:    * The prime numbers used in UMAC are:
 137:    * <pre>
 138:    *   +-----+--------------------+---------------------------------------+
 139:    *   |  x  | prime(x) [Decimal] | prime(x) [Hexadecimal]                |
 140:    *   +-----+--------------------+---------------------------------------+
 141:    *   | 19  | 2^19  - 1          | 0x0007FFFF                            |
 142:    *   | 32  | 2^32  - 5          | 0xFFFFFFFB                            |
 143:    *   | 36  | 2^36  - 5          | 0x0000000F FFFFFFFB                   |
 144:    *   | 64  | 2^64  - 59         | 0xFFFFFFFF FFFFFFC5                   |
 145:    *   | 128 | 2^128 - 159        | 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFF61 |
 146:    *   +-----+--------------------+---------------------------------------+
 147:    *</pre>
 148:    *
 149:    * @param n a number of bits.
 150:    * @return the largest prime number less than 2**n.
 151:    */
 152:   static final BigInteger prime(int n)
 153:   {
 154:     switch (n)
 155:       {
 156:       case 19:
 157:         return PRIME_19;
 158:       case 32:
 159:         return PRIME_32;
 160:       case 36:
 161:         return PRIME_36;
 162:       case 64:
 163:         return PRIME_64;
 164:       case 128:
 165:         return PRIME_128;
 166:       default:
 167:         throw new IllegalArgumentException("Undefined prime("
 168:                                            + String.valueOf(n) + ")");
 169:       }
 170:   }
 171: 
 172:   public Object clone()
 173:   {
 174:     return new UHash32(this);
 175:   }
 176: 
 177:   public int macSize()
 178:   {
 179:     return UMac32.OUTPUT_LEN;
 180:   }
 181: 
 182:   public void init(Map attributes) throws InvalidKeyException,
 183:       IllegalStateException
 184:   {
 185:     byte[] K = (byte[]) attributes.get(MAC_KEY_MATERIAL);
 186:     if (K == null)
 187:       throw new InvalidKeyException("Null Key");
 188:     if (K.length != UMac32.KEY_LEN)
 189:       throw new InvalidKeyException("Invalid Key length: "
 190:                                     + String.valueOf(K.length));
 191:     // Calculate iterations needed to make UMAC-OUTPUT-LEN bytes
 192:     streams = (UMac32.OUTPUT_LEN + 3) / 4;
 193:     // Define total key needed for all iterations using UMacGenerator.
 194:     // L1Key and L3Key1 both reuse most key between iterations.
 195:     IRandom kdf1 = new UMacGenerator();
 196:     IRandom kdf2 = new UMacGenerator();
 197:     IRandom kdf3 = new UMacGenerator();
 198:     IRandom kdf4 = new UMacGenerator();
 199:     Map map = new HashMap();
 200:     map.put(IBlockCipher.KEY_MATERIAL, K);
 201:     map.put(UMacGenerator.INDEX, Integer.valueOf(0));
 202:     kdf1.init(map);
 203:     map.put(UMacGenerator.INDEX, Integer.valueOf(1));
 204:     kdf2.init(map);
 205:     map.put(UMacGenerator.INDEX, Integer.valueOf(2));
 206:     kdf3.init(map);
 207:     map.put(UMacGenerator.INDEX, Integer.valueOf(3));
 208:     kdf4.init(map);
 209:     // need to generate all bytes for use later in a Toepliz construction
 210:     byte[] L1Key = new byte[UMac32.L1_KEY_LEN + (streams - 1) * 16];
 211:     try
 212:       {
 213:         kdf1.nextBytes(L1Key, 0, L1Key.length);
 214:       }
 215:     catch (LimitReachedException x)
 216:       {
 217:         x.printStackTrace(System.err);
 218:         throw new RuntimeException("KDF for L1Key reached limit");
 219:       }
 220: 
 221:     l1hash = new L1Hash32[streams];
 222:     for (int i = 0; i < streams; i++)
 223:       {
 224:         byte[] k1 = new byte[UMac32.L1_KEY_LEN];
 225:         System.arraycopy(L1Key, i * 16, k1, 0, UMac32.L1_KEY_LEN);
 226:         byte[] k2 = new byte[24];
 227:         try
 228:           {
 229:             kdf2.nextBytes(k2, 0, 24);
 230:           }
 231:         catch (LimitReachedException x)
 232:           {
 233:             x.printStackTrace(System.err);
 234:             throw new RuntimeException("KDF for L2Key reached limit");
 235:           }
 236:         byte[] k31 = new byte[64];
 237:         try
 238:           {
 239:             kdf3.nextBytes(k31, 0, 64);
 240:           }
 241:         catch (LimitReachedException x)
 242:           {
 243:             x.printStackTrace(System.err);
 244:             throw new RuntimeException("KDF for L3Key1 reached limit");
 245:           }
 246:         byte[] k32 = new byte[4];
 247:         try
 248:           {
 249:             kdf4.nextBytes(k32, 0, 4);
 250:           }
 251:         catch (LimitReachedException x)
 252:           {
 253:             x.printStackTrace(System.err);
 254:             throw new RuntimeException("KDF for L3Key2 reached limit");
 255:           }
 256:         L1Hash32 mac = new L1Hash32();
 257:         mac.init(k1, k2, k31, k32);
 258:         l1hash[i] = mac;
 259:       }
 260:   }
 261: 
 262:   public void update(byte b)
 263:   {
 264:     for (int i = 0; i < streams; i++)
 265:       l1hash[i].update(b);
 266:   }
 267: 
 268:   public void update(byte[] b, int offset, int len)
 269:   {
 270:     for (int i = 0; i < len; i++)
 271:       this.update(b[offset + i]);
 272:   }
 273: 
 274:   public byte[] digest()
 275:   {
 276:     byte[] result = new byte[UMac32.OUTPUT_LEN];
 277:     for (int i = 0; i < streams; i++)
 278:       {
 279:         byte[] partialResult = l1hash[i].digest();
 280:         System.arraycopy(partialResult, 0, result, 4 * i, 4);
 281:       }
 282:     reset();
 283:     return result;
 284:   }
 285: 
 286:   public void reset()
 287:   {
 288:     for (int i = 0; i < streams; i++)
 289:       l1hash[i].reset();
 290:   }
 291: 
 292:   public boolean selfTest()
 293:   {
 294:     return true;
 295:   }
 296: 
 297:   /**
 298:    * First hash stage of the UHash32 algorithm.
 299:    */
 300:   class L1Hash32
 301:       implements Cloneable
 302:   {
 303:     private int[] key; // key material as an array of 32-bit ints
 304:     private byte[] buffer; // work buffer L1_KEY_LEN long
 305:     private int count; // meaningful bytes in buffer
 306:     private ByteArrayOutputStream Y;
 307:     private long totalCount;
 308:     private L2Hash32 l2hash;
 309:     private L3Hash32 l3hash;
 310: 
 311:     /** Trivial 0-arguments constructor. */
 312:     L1Hash32()
 313:     {
 314:       super();
 315: 
 316:       key = new int[UMac32.L1_KEY_LEN / 4];
 317:       buffer = new byte[UMac32.L1_KEY_LEN];
 318:       count = 0;
 319:       Y = new ByteArrayOutputStream();
 320:       totalCount = 0L;
 321:     }
 322: 
 323:     /**
 324:      * Private constructor for cloning purposes.
 325:      *
 326:      * @param that the instance to clone.
 327:      */
 328:     private L1Hash32(L1Hash32 that)
 329:     {
 330:       this();
 331: 
 332:       System.arraycopy(that.key, 0, this.key, 0, that.key.length);
 333:       System.arraycopy(that.buffer, 0, this.buffer, 0, that.count);
 334:       this.count = that.count;
 335:       byte[] otherY = that.Y.toByteArray();
 336:       this.Y.write(otherY, 0, otherY.length);
 337:       this.totalCount = that.totalCount;
 338:       if (that.l2hash != null)
 339:         this.l2hash = (L2Hash32) that.l2hash.clone();
 340:       if (that.l3hash != null)
 341:         this.l3hash = (L3Hash32) that.l3hash.clone();
 342:     }
 343: 
 344:     public Object clone()
 345:     {
 346:       return new L1Hash32(this);
 347:     }
 348: 
 349:     public void init(byte[] k1, byte[] k2, byte[] k31, byte[] k32)
 350:     {
 351:       for (int i = 0, j = 0; i < (UMac32.L1_KEY_LEN / 4); i++)
 352:         key[i] =  k1[j++]         << 24
 353:                | (k1[j++] & 0xFF) << 16
 354:                | (k1[j++] & 0xFF) << 8
 355:                | (k1[j++] & 0xFF);
 356:       l2hash = new L2Hash32(k2);
 357:       l3hash = new L3Hash32(k31, k32);
 358:     }
 359: 
 360:     public void update(byte b)
 361:     {
 362:       // Break M into L1_KEY_LEN byte chunks (final chunk may be shorter)
 363: 
 364:       // Let M_1, M_2, ..., M_t be strings so that M = M_1 || M_2 || .. ||
 365:       // M_t, and length(M_i) = L1_KEY_LEN for all 0 < i < t.
 366: 
 367:       // For each chunk, except the last: endian-adjust, NH hash
 368:       // and add bit-length.  Use results to build Y.
 369:       buffer[count] = b;
 370:       count++;
 371:       totalCount++;
 372:       if (count >= UMac32.L1_KEY_LEN)
 373:         {
 374:           byte[] y = nh32(UMac32.L1_KEY_LEN);
 375:           Y.write(y, 0, 8);
 376: 
 377:           count = 0;
 378: 
 379:           // For each iteration, extract key and three-layer hash.
 380:           // If length(M) <= L1_KEY_LEN, then skip L2-HASH.
 381:           if (Y.size() == 16) // we already hashed twice L1_KEY_LEN
 382:             {
 383:               byte[] A = Y.toByteArray();
 384:               Y.reset();
 385:               l2hash.update(A, 0, 16);
 386:             }
 387:         }
 388:     }
 389: 
 390:     public byte[] digest()
 391:     {
 392:       // For the last chunk: pad to 32-byte boundary, endian-adjust,
 393:       // NH hash and add bit-length.  Concatenate the result to Y.
 394:       if (count != 0)
 395:         {
 396:           if (count % 32 != 0)
 397:             {
 398:               int limit = 32 * ((count + 31) / 32);
 399:               System.arraycopy(ALL_ZEROES, 0, buffer, count, limit - count);
 400:               count += limit - count;
 401:             }
 402:           byte[] y = nh32(count);
 403:           Y.write(y, 0, 8);
 404:         }
 405:       byte[] A = Y.toByteArray();
 406:       Y.reset();
 407:       byte[] B;
 408:       if (totalCount <= UMac32.L1_KEY_LEN)
 409:         {
 410:           // we might have 'update'd the bytes already. check
 411:           if (A.length == 0) // we did
 412:             B = l2hash.digest();
 413:           else // did not
 414:             {
 415:               B = new byte[16];
 416:               System.arraycopy(A, 0, B, 8, 8);
 417:             }
 418:         }
 419:       else
 420:         {
 421:           if (A.length != 0)
 422:             l2hash.update(A, 0, A.length);
 423:           B = l2hash.digest();
 424:         }
 425:       byte[] result = l3hash.digest(B);
 426:       reset();
 427:       return result;
 428:     }
 429: 
 430:     public void reset()
 431:     {
 432:       count = 0;
 433:       Y.reset();
 434:       totalCount = 0L;
 435:       if (l2hash != null)
 436:         l2hash.reset();
 437:     }
 438: 
 439:     /**
 440:      * 5.1  NH-32: NH hashing with a 32-bit word size.
 441:      *
 442:      * @param len count of bytes, divisible by 32, in buffer to process
 443:      * @return Y, string of length 8 bytes.
 444:      */
 445:     private byte[] nh32(int len)
 446:     {
 447:       // Break M and K into 4-byte chunks
 448:       int t = len / 4;
 449:       // Let M_1, M_2, ..., M_t be 4-byte strings
 450:       // so that M = M_1 || M_2 || .. || M_t.
 451:       // Let K_1, K_2, ..., K_t be 4-byte strings
 452:       // so that K_1 || K_2 || .. || K_t  is a prefix of K.
 453:       int[] m = new int[t];
 454:       int i;
 455:       int j = 0;
 456:       for (i = 0, j = 0; i < t; i++)
 457:         m[i] =  buffer[j++]         << 24
 458:              | (buffer[j++] & 0xFF) << 16
 459:              | (buffer[j++] & 0xFF) << 8
 460:              | (buffer[j++] & 0xFF);
 461:       // Perform NH hash on the chunks, pairing words for multiplication
 462:       // which are 4 apart to accommodate vector-parallelism.
 463:       long result = len * 8L;
 464:       for (i = 0; i < t; i += 8)
 465:         {
 466:           result += ((m[i + 0] + key[i + 0]) & 0xFFFFFFFFL)
 467:                   * ((m[i + 4] + key[i + 4]) & 0xFFFFFFFFL);
 468:           result += ((m[i + 1] + key[i + 1]) & 0xFFFFFFFFL)
 469:                   * ((m[i + 5] + key[i + 5]) & 0xFFFFFFFFL);
 470:           result += ((m[i + 2] + key[i + 2]) & 0xFFFFFFFFL)
 471:                   * ((m[i + 6] + key[i + 6]) & 0xFFFFFFFFL);
 472:           result += ((m[i + 3] + key[i + 3]) & 0xFFFFFFFFL)
 473:                   * ((m[i + 7] + key[i + 7]) & 0xFFFFFFFFL);
 474:         }
 475:       return new byte[] {
 476:           (byte)(result >>> 56), (byte)(result >>> 48),
 477:           (byte)(result >>> 40), (byte)(result >>> 32),
 478:           (byte)(result >>> 24), (byte)(result >>> 16),
 479:           (byte)(result >>>  8), (byte) result };
 480:     }
 481:   }
 482: 
 483:   /**
 484:    * Second hash stage of the UHash32 algorithm.
 485:    * <p>
 486:    * 5.4 L2-HASH-32: Second-layer hash.
 487:    * <ul>
 488:    * <li>Input:<br>
 489:    * K string of length 24 bytes.<br>
 490:    * M string of length less than 2^64 bytes.</li>
 491:    * <li>Returns:<br>
 492:    * Y, string of length 16 bytes.</li>
 493:    * </ul>
 494:    */
 495:   class L2Hash32
 496:       implements Cloneable
 497:   {
 498:     private BigInteger k64, k128;
 499:     private BigInteger y;
 500:     private boolean highBound;
 501:     private long bytesSoFar;
 502:     private ByteArrayOutputStream buffer;
 503: 
 504:     L2Hash32(byte[] K)
 505:     {
 506:       super();
 507: 
 508:       if (K.length != 24)
 509:         throw new ExceptionInInitializerError("K length is not 24");
 510:       //  Extract keys and restrict to special key-sets
 511:       //         Mask64  = uint2str(0x01FFFFFF01FFFFFF, 8);
 512:       //         Mask128 = uint2str(0x01FFFFFF01FFFFFF01FFFFFF01FFFFFF, 16);
 513:       //         k64    = str2uint(K[1..8]  and Mask64);
 514:       //         k128   = str2uint(K[9..24] and Mask128);
 515:       int i = 0;
 516:       k64 = new BigInteger(1, new byte[] {
 517:           (byte)(K[i++] & 0x01), (byte)(K[i++] & 0xFF),
 518:           (byte)(K[i++] & 0xFF), (byte)(K[i++] & 0xFF),
 519:           (byte)(K[i++] & 0x01), (byte)(K[i++] & 0xFF),
 520:           (byte)(K[i++] & 0xFF), (byte)(K[i++] & 0xFF) });
 521:       k128 = new BigInteger(1, new byte[] {
 522:           (byte)(K[i++] & 0x01), (byte)(K[i++] & 0xFF),
 523:           (byte)(K[i++] & 0xFF), (byte)(K[i++] & 0xFF),
 524:           (byte)(K[i++] & 0x01), (byte)(K[i++] & 0xFF),
 525:           (byte)(K[i++] & 0xFF), (byte)(K[i++] & 0xFF),
 526:           (byte)(K[i++] & 0x01), (byte)(K[i++] & 0xFF),
 527:           (byte)(K[i++] & 0xFF), (byte)(K[i++] & 0xFF),
 528:           (byte)(K[i++] & 0x01), (byte)(K[i++] & 0xFF),
 529:           (byte)(K[i++] & 0xFF), (byte)(K[i++] & 0xFF) });
 530:       y = BigInteger.ONE;
 531:       highBound = false;
 532:       bytesSoFar = 0L;
 533:     }
 534: 
 535:     private L2Hash32(L2Hash32 that)
 536:     {
 537:       super();
 538: 
 539:       this.k64 = that.k64;
 540:       this.k128 = that.k128;
 541:       this.y = that.y;
 542:       this.highBound = that.highBound;
 543:       this.bytesSoFar = that.bytesSoFar;
 544:       if (that.buffer != null)
 545:         {
 546:           byte[] thatbuffer = that.buffer.toByteArray();
 547:           this.buffer = new ByteArrayOutputStream();
 548:           this.buffer.write(thatbuffer, 0, thatbuffer.length);
 549:         }
 550:     }
 551: 
 552:     public Object clone()
 553:     {
 554:       return new L2Hash32(this);
 555:     }
 556: 
 557:     // this is called with either 8-bytes or 16-bytes
 558:     void update(byte[] b, int offset, int len)
 559:     {
 560:       if (len == 0)
 561:         return;
 562: 
 563:       if (! highBound) // do the first (only?) 8-bytes
 564:         {
 565:           poly(64, LOWER_RANGE, k64, b, offset, 8);
 566:           bytesSoFar += 8L;
 567:           highBound = (bytesSoFar > BOUNDARY);
 568:           if (highBound) // if we just crossed the limit then process y
 569:             {
 570:               poly(128, UPPER_RANGE, k128, yTo16bytes(), 0, 16);
 571:               buffer = new ByteArrayOutputStream();
 572:             }
 573:           // do the rest if any
 574:           update(b, offset + 8, len - 8);
 575:         }
 576:       else
 577:         { // we're already beyond the 2**17 bytes size limit
 578:           // process in chuncks of 16
 579:           buffer.write(b, offset, len);
 580:           if (buffer.size() > 16)
 581:             {
 582:               byte[] bb = buffer.toByteArray();
 583:               poly(128, UPPER_RANGE, k128, bb, 0, 16);
 584:               if (bb.length > 16)
 585:                 buffer.write(bb, 16, bb.length - 16);
 586:             }
 587:         }
 588:     }
 589: 
 590:     byte[] digest()
 591:     {
 592:       // If M no more than 2^17 bytes, hash under 64-bit prime,
 593:       // otherwise, hash first 2^17 bytes under 64-bit prime and
 594:       // remainder under 128-bit prime.
 595:       if (! highBound) // y is up-to-date
 596:         {
 597:           // do nothing
 598:         }
 599:       else // we may have some bytes in buffer
 600:         {
 601:           byte[] bb = buffer.toByteArray();
 602:           byte[] lastBlock = new byte[16];
 603:           System.arraycopy(bb, 0, lastBlock, 0, bb.length);
 604:           lastBlock[bb.length] = (byte) 0x80;
 605:           poly(128, UPPER_RANGE, k128, lastBlock, 0, 16);
 606:         }
 607:       byte[] result = yTo16bytes();
 608:       reset();
 609:       return result;
 610:     }
 611: 
 612:     void reset()
 613:     {
 614:       y = BigInteger.ONE;
 615:       highBound = false;
 616:       bytesSoFar = 0L;
 617:       if (buffer != null)
 618:         buffer.reset();
 619:     }
 620: 
 621:     private byte[] yTo16bytes()
 622:     {
 623:       byte[] yy = y.toByteArray();
 624:       byte[] result = new byte[16];
 625:       if (yy.length > 16)
 626:         System.arraycopy(yy, yy.length - 16, result, 0, 16);
 627:       else
 628:         System.arraycopy(yy, 0, result, 16 - yy.length, yy.length);
 629: 
 630:       return result;
 631:     }
 632: 
 633:     /**
 634:      * 5.3 POLY: Polynomial hash Function Name: POLY
 635:      *
 636:      * @param wordbits positive integer divisible by 8: called with 64 or 128.
 637:      * @param maxwordrange positive integer less than 2**wordbits.
 638:      * @param k integer in the range 0 .. prime(wordbits) - 1.
 639:      * @param M string with length divisible by (wordbits / 8) bytes. return y,
 640:      *          integer in the range 0 .. prime(wordbits) - 1.
 641:      */
 642:     private void poly(int wordbits, BigInteger maxwordrange, BigInteger k,
 643:                       byte[] M, int off, int len)
 644:     {
 645:       byte[] mag = new byte[len];
 646:       System.arraycopy(M, off, mag, 0, len);
 647:       // Define constants used for fixing out-of-range words
 648:       BigInteger p = prime(wordbits);
 649:       BigInteger offset = TWO.pow(wordbits).subtract(p); // 2^wordbits - p;
 650:       BigInteger marker = p.subtract(BigInteger.ONE);
 651:       // Break M into chunks of length wordbytes bytes
 652:       //         long n = M.length / wordbytes;
 653:       // Let M_1, M_2, ..., M_n be strings of length wordbytes bytes
 654:       // so that M = M_1 || M_2 || .. || M_n
 655: 
 656:       // For each input word, compare it with maxwordrange.  If larger
 657:       // then hash the words 'marker' and (m - offset), both in range.
 658:       //         for (int i = 0; i < n; i++) {
 659:       BigInteger m = new BigInteger(1, mag);
 660:       if (m.compareTo(maxwordrange) >= 0) // m >= maxwordrange
 661:         {
 662:           y = y.multiply(k).add(marker).mod(p); // (k * y + marker) % p;
 663:           y = y.multiply(k).add(m.subtract(offset)).mod(p); // (k * y + (m - offset)) % p;
 664:         }
 665:       else
 666:         y = y.multiply(k).add(m).mod(p); // (k * y + m) % p;
 667:     }
 668:   }
 669: 
 670:   /**
 671:    * Third hash stage of the UHash32 algorithm.
 672:    * <ul>
 673:    * <li>Input:<br/>
 674:    * K1 string of length 64 bytes.<br/>
 675:    * K2 string of length 4 bytes.<br/>
 676:    * M string of length 16 bytes.</li>
 677:    * <li>Returns:<br/>
 678:    * Y, string of length 4 bytes.</li>
 679:    * </ul>
 680:    */
 681:   class L3Hash32
 682:       implements Cloneable
 683:   {
 684:     private static final long PRIME_36 = 0x0000000FFFFFFFFBL;
 685:     private int[] k = new int[9];
 686: 
 687:     /**
 688:      * @param K1 string of length 64 bytes.
 689:      * @param K2 string of length 4 bytes.
 690:      */
 691:     L3Hash32(byte[] K1, byte[] K2)
 692:     {
 693:       super();
 694: 
 695:       // pre-conditions
 696:       if (K1.length != 64)
 697:         throw new ExceptionInInitializerError("K1 length is not 64");
 698:       if (K2.length != 4)
 699:         throw new ExceptionInInitializerError("K2 length is not 4");
 700:       // Break K1 into 8 chunks and convert to integers
 701:       for (int i = 0, j = 0; i < 8; i++)
 702:         {
 703:           long kk = (K1[j++] & 0xFFL) << 56
 704:                   | (K1[j++] & 0xFFL) << 48
 705:                   | (K1[j++] & 0xFFL) << 40
 706:                   | (K1[j++] & 0xFFL) << 32
 707:                   | (K1[j++] & 0xFFL) << 24
 708:                   | (K1[j++] & 0xFFL) << 16
 709:                   | (K1[j++] & 0xFFL) <<  8
 710:                   | (K1[j++] & 0xFFL);
 711:           k[i] = (int)(kk % PRIME_36);
 712:         }
 713:       k[8] =  K2[0]         << 24
 714:            | (K2[1] & 0xFF) << 16
 715:            | (K2[2] & 0xFF) << 8
 716:            | (K2[3] & 0xFF);
 717:     }
 718: 
 719:     private L3Hash32(int[] k)
 720:     {
 721:       super();
 722: 
 723:       this.k = k;
 724:     }
 725: 
 726:     public Object clone()
 727:     {
 728:       return new L3Hash32((int[]) k.clone());
 729:     }
 730: 
 731:     /**
 732:      * @param M string of length 16 bytes.
 733:      * @return Y, string of length 4 bytes.
 734:      */
 735:     byte[] digest(byte[] M)
 736:     {
 737:       if (M.length != 16)
 738:         throw new IllegalArgumentException("M length is not 16");
 739: 
 740:       long m, y = 0L;
 741:       for (int i = 0, j = 0; i < 8; i++)
 742:         {
 743:           // Break M into 8 chunks and convert to integers
 744:           m = (M[j++] & 0xFFL) << 8 | (M[j++] & 0xFFL);
 745:           // Inner-product hash, extract last 32 bits and affine-translate
 746:           //            y = (m_1 * k_1 + ... + m_8 * k_8) mod prime(36);
 747:           //            y = y mod 2^32;
 748:           y += (m * (k[i] & 0xFFFFFFFFL)) % PRIME_36;
 749:         }
 750:       int Y = ((int) y) ^ k[8];
 751:       return new byte[] {
 752:           (byte)(Y >>> 24),
 753:           (byte)(Y >>> 16),
 754:           (byte)(Y >>> 8),
 755:           (byte) Y };
 756:     }
 757:   }
 758: }