ShaHash.java

00001 // ShaHash - the Secure Hash Algorithm
00002 //
00003 // Copyright (C) 1996 by Jef Poskanzer <jef@acme.com>.  All rights reserved.
00004 //
00005 // Redistribution and use in source and binary forms, with or without
00006 // modification, are permitted provided that the following conditions
00007 // are met:
00008 // 1. Redistributions of source code must retain the above copyright
00009 //    notice, this list of conditions and the following disclaimer.
00010 // 2. Redistributions in binary form must reproduce the above copyright
00011 //    notice, this list of conditions and the following disclaimer in the
00012 //    documentation and/or other materials provided with the distribution.
00013 //
00014 // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
00015 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00016 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00017 // ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
00018 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00019 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00020 // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00021 // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00022 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00023 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00024 // SUCH DAMAGE.
00025 //
00026 // Visit the ACME Labs Java page for up-to-date versions of this and other
00027 // fine Java utilities: http://www.acme.com/java/
00028 
00029 package Acme.Crypto;
00030 
00031 import java.io.*;
00032 
00034 // <P>
00035 // This is surprisingly fast, processing 28000 bytes per second on a
00036 // SPARC Ultra.
00037 // <P>
00038 // <A HREF="/resources/classes/Acme/Crypto/ShaHash.java">Fetch the software.</A><BR>
00039 // <A HREF="/resources/classes/Acme.tar.gz">Fetch the entire Acme package.</A>
00040 
00041 public class ShaHash extends Hash
00042     {
00043 
00045     public ShaHash()
00046         {
00047         super( SHA_DIGESTSIZE );
00048         reset();
00049         }
00050 
00052     public void reset()
00053         {
00054         shaInit();
00055         }
00056 
00058     public void add( byte b )
00059         {
00060         // Just use the block add routine.  Maybe add a buffer later.
00061         byte[] data = new byte[1];
00062         data[0] = b;
00063         add( data, 0, 1 );
00064         }
00065 
00067     public void add( byte[] data, int off, int len )
00068         {
00069         shaUpdate( data, off, len );
00070         }
00071     
00073     protected void prepare()
00074         {
00075         shaFinal();
00076         spreadIntsToBytes( digest, 0, hashBytes, 0, SHA_DIGESTSIZE/4 );
00077         }
00078 
00079     private static final boolean USE_MODIFIED_SHA = true;
00080     private static final int SHA_BLOCKSIZE = 64;
00081     private static final int SHA_DIGESTSIZE = 20;
00082 
00083     private int[] digest = new int[SHA_DIGESTSIZE/4];   // message digest
00084     private long bitCount;                              // 64-bit bit count
00085     private byte[] dataB = new byte[SHA_BLOCKSIZE];     // SHA byte data buffer
00086     private int[] dataI = new int[SHA_BLOCKSIZE/4];     // SHA long data buffer
00087 
00088     // This implementation includes a change to the algorithm introduced by
00089     // NIST at the behest of the NSA.  It supposedly corrects a weakness in
00090     // the original formulation.  Bruce Schneier described it thus in a
00091     // posting to the Cypherpunks mailing list on June 21, 1994 (as told to
00092     // us by Steve Bellovin):
00093     //
00094     //  This is the fix to the Secure Hash Standard, NIST FIPS PUB 180:
00095     //
00096     //       In Section 7 of FIPS 180 (page 9), the line which reads
00097     //
00098     //       "b) For t=16 to 79 let Wt = Wt-3 XOR Wt-8 XOR Wt-14 XOR
00099     //       Wt-16."
00100     //
00101     //       is to be replaced by
00102     //
00103     //       "b) For t=16 to 79 let Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR
00104     //       Wt-16)."
00105     //
00106     //       where S1 is a left circular shift by one bit as defined in
00107     //       Section 3 of FIPS 180 (page 6):
00108     //
00109     //       S1(X) = (X<<1) OR (X>>31).
00110 
00111     // The SHA f()-functions
00112 
00113     // Rounds 0-19.
00114     private static int f1( int x, int y, int z )
00115         {
00116         return ( x & y ) | ( ~x & z );
00117         }
00118 
00119     // Rounds 20-39.
00120     private static int f2( int x, int y, int z )
00121         {
00122         return x ^ y ^ z;
00123         }
00124 
00125     // Rounds 40-59.
00126     private static int f3( int x, int y, int z )
00127         {
00128         return ( x & y ) | ( x & z ) | ( y & z );
00129         }
00130 
00131     // Rounds 60-79.
00132     private static int f4( int x, int y, int z )
00133         {
00134         return x ^ y ^ z;
00135         }
00136 
00137     // The SHA Mysterious Constants.
00138     private static final int K1 = 0x5a827999;     // rounds  0-19
00139     private static final int K2 = 0x6ed9eba1;     // rounds 20-39
00140     private static final int K3 = 0x8f1bbcdc;     // rounds 40-59
00141     private static final int K4 = 0xca62c1d6;     // rounds 60-79
00142 
00143     // SHA initial values.
00144     private static final int h0init = 0x67452301;
00145     private static final int h1init = 0xefcdab89;
00146     private static final int h2init = 0x98badcfe;
00147     private static final int h3init = 0x10325476;
00148     private static final int h4init = 0xc3d2e1f0;
00149 
00150     // 32-bit left rotate - kludged with shifts.
00151     private static int rotateL( int x, int n )
00152         {
00153         return ( x << n ) | ( x >>> ( 32 - n ) );
00154         }
00155 
00156 
00157     // The four SHA sub-rounds.
00158 
00159     private void subRound1( int count )
00160         {
00161         int temp = rotateL( A, 5 ) + f1( B, C, D ) + E + W[count] + K1;
00162         E = D;
00163         D = C;
00164         C = rotateL( B, 30 );
00165         B = A;
00166         A = temp;
00167         }
00168 
00169     private void subRound2( int count )
00170         {
00171         int temp = rotateL( A, 5 ) + f2( B, C, D ) + E + W[count] + K2;
00172         E = D;
00173         D = C;
00174         C = rotateL( B, 30 );
00175         B = A;
00176         A = temp;
00177         }
00178 
00179     private void subRound3( int count )
00180         {
00181         int temp = rotateL( A, 5 ) + f3( B, C, D ) + E + W[count] + K3;
00182         E = D;
00183         D = C;
00184         C = rotateL( B, 30 );
00185         B = A;
00186         A = temp;
00187         }
00188 
00189     private void subRound4( int count )
00190         {
00191         int temp = rotateL( A, 5 ) + f4( B, C, D ) + E + W[count] + K4;
00192         E = D;
00193         D = C;
00194         C = rotateL( B, 30 );
00195         B = A;
00196         A = temp;
00197         }
00198 
00199     // The two buffers of 5 32-bit words.
00200     private int h0, h1, h2, h3, h4;
00201     private int A, B, C, D, E;
00202 
00204     private void shaInit()
00205         {
00206         // Set the h-vars to their initial values.
00207         digest[0] = h0init;
00208         digest[1] = h1init;
00209         digest[2] = h2init;
00210         digest[3] = h3init;
00211         digest[4] = h4init;
00212 
00213         // Initialise bit count.
00214         bitCount = 0;
00215         }
00216 
00217     private int[] W = new int[80];
00218 
00220     private void shaTransform()
00221         {
00222         int i;
00223 
00224         // Step A.  Copy the data buffer into the local work buffer.
00225         for( i = 0; i < SHA_BLOCKSIZE/4; ++i )
00226             W[i] = dataI[i];
00227 
00228         // Step B.  Expand the 16 words into 64 temporary data words.
00229         for ( ; i < 80; ++i )
00230             {
00231             W[i] = W[i - 3] ^ W[i - 8] ^ W[i - 14] ^ W[i - 16];
00232             if ( USE_MODIFIED_SHA )
00233                 W[i] = rotateL( W[i], 1 );
00234             }
00235 
00236         // Step C.  Set up first buffer
00237         A = digest[0];
00238         B = digest[1];
00239         C = digest[2];
00240         D = digest[3];
00241         E = digest[4];
00242 
00243         // Step D.  Serious mangling, divided into four sub-rounds.
00244         for ( i = 0; i < 20; ++i )
00245             subRound1( i );
00246         for ( ; i < 40; ++i )
00247             subRound2( i );
00248         for ( ; i < 60; ++i )
00249             subRound3( i );
00250         for ( ; i < 80; ++i )
00251             subRound4( i );
00252 
00253         // Step E.  Build message digest.
00254         digest[0] += A;
00255         digest[1] += B;
00256         digest[2] += C;
00257         digest[3] += D;
00258         digest[4] += E;
00259         }
00260 
00262     // is a multiple of SHA_BLOCKSIZE bytes long, which makes the code a lot
00263     // more efficient since it does away with the need to handle partial blocks
00264     // between calls to shaUpdate().
00265     private void shaUpdate( byte[] buffer, int offset, int count )
00266         {
00267         // Update bitcount.
00268         bitCount += count << 3;
00269 
00270         // Process data in SHA_BLOCKSIZE chunks.
00271         while ( count >= SHA_BLOCKSIZE )
00272             {
00273             copyBlock( buffer, offset, dataB, 0, SHA_BLOCKSIZE );
00274             squashBytesToInts( dataB, 0, dataI, 0, SHA_BLOCKSIZE/4 );
00275             shaTransform();
00276             offset += SHA_BLOCKSIZE;
00277             count -= SHA_BLOCKSIZE;
00278             }
00279 
00280         // Handle any remaining bytes of data.  This should only happen once
00281         // on the final lot of data.
00282         copyBlock( buffer, offset, dataB, 0, count );
00283         }
00284 
00285     private void shaFinal()
00286         {
00287         int count;
00288 
00289         // Compute number of bytes mod 64.
00290         count = (int) ( bitCount >>> 3 ) & 0x3F;
00291 
00292         // Set the first char of padding to 0x80.  This is safe since there is
00293         // always at least one byte free.
00294         dataB[count++] = (byte) 0x80;
00295 
00296         // Pad out to 56 mod 64.
00297         if ( count > SHA_BLOCKSIZE - 8 )
00298             {
00299             // Two lots of padding:  Pad the first block to 64 bytes.
00300             fillBlock( dataB, count, (byte) 0, SHA_BLOCKSIZE - count );
00301             squashBytesToInts( dataB, 0, dataI, 0, SHA_BLOCKSIZE/4 );
00302             shaTransform();
00303 
00304             // Now fill the next block with 56 bytes.
00305             fillBlock( dataB, 0, (byte) 0, SHA_BLOCKSIZE - 8 );
00306             }
00307         else
00308             // Pad block to 56 bytes.
00309             fillBlock( dataB, count, (byte) 0, SHA_BLOCKSIZE - 8 - count );
00310         squashBytesToInts( dataB, 0, dataI, 0, SHA_BLOCKSIZE/4 );
00311 
00312         // Append length in bits and transform.
00313         dataI[14] = (int) ( bitCount >>> 32 );
00314         dataI[15] = (int) ( bitCount & 0xffffffff );
00315 
00316         shaTransform();
00317         }
00318 
00319 
00320     // ----------------------------- SHA Test code ---------------------------
00321 
00322     // Size of buffer for SHA speed test data.
00323     private static int TEST_BLOCK_SIZE = SHA_DIGESTSIZE * 100;
00324 
00325     // Number of bytes of test data to process.
00326     private static int TEST_BYTES = 10000000;
00327     private static int TEST_BLOCKS = TEST_BYTES / TEST_BLOCK_SIZE;
00328 
00329     public static void main( String[] args )
00330         {
00331         ShaHash h = new ShaHash();
00332 
00333         // Test output data (this is the only test data given in the SHA
00334         // document, but chances are if it works for this it'll work for
00335         // anything).
00336         h.addASCII( "abc" );
00337         byte[] hb = h.get();
00338         byte[] oldCorrect = {
00339             (byte) 0x01, (byte) 0x64, (byte) 0xb8, (byte) 0xa9,
00340             (byte) 0x14, (byte) 0xcd, (byte) 0x2a, (byte) 0x5e,
00341             (byte) 0x74, (byte) 0xc4, (byte) 0xf7, (byte) 0xff,
00342             (byte) 0x08, (byte) 0x2c, (byte) 0x4d, (byte) 0x97,
00343             (byte) 0xf1, (byte) 0xed, (byte) 0xf8, (byte) 0x80
00344             };
00345         byte[] newCorrect = {
00346             (byte) 0xa9, (byte) 0x99, (byte) 0x3e, (byte) 0x36,
00347             (byte) 0x47, (byte) 0x06, (byte) 0x81, (byte) 0x6a,
00348             (byte) 0xba, (byte) 0x3e, (byte) 0x25, (byte) 0x71,
00349             (byte) 0x78, (byte) 0x50, (byte) 0xc2, (byte) 0x6c,
00350             (byte) 0x9c, (byte) 0xd0, (byte) 0xd8, (byte) 0x9d
00351             };
00352         byte[] correct;
00353         if ( USE_MODIFIED_SHA )
00354             correct = newCorrect;
00355         else
00356             correct = oldCorrect;
00357         System.out.println( "Got:  " + toStringBlock( hb ) );
00358         System.out.println( "Want: " + toStringBlock( correct ) );
00359         if ( ! equalsBlock( hb, correct ) )
00360             {
00361             System.err.println( "Error in SHA implementation." );
00362             System.exit( 1 );
00363             }
00364 
00365         // Now perform time trial, generating MD for 10MB of data.  First,
00366         // initialize the test data.
00367         byte[] data = new byte[TEST_BLOCK_SIZE];
00368         int i;
00369 
00370         fillBlock( data, (byte) 0 );
00371 
00372         System.out.println( "SHA time trial.  Processing " + TEST_BYTES + " characters..." );
00373 
00374         // Calculate SHA message digest in TEST_BLOCK_SIZE byte blocks.
00375         h.reset();
00376         for ( i = TEST_BLOCKS; i > 0; i-- )
00377             h.add( data, 0, TEST_BLOCK_SIZE );
00378         h.get();
00379 
00380         System.out.println( "Done." );
00381 
00382         }
00383 
00384     }

Generated on Mon Dec 4 11:03:30 2006 for OpenMobileIS by  doxygen 1.5.1-p1