URL
https://opencores.org/ocsvn/bluespec_md6/bluespec_md6/trunk
Subversion Repositories bluespec_md6
[/] [bluespec_md6/] [trunk/] [C_implementation/] [md6_compress.c] - Rev 2
Go to most recent revision | Compare with Previous | Blame | View Log
/* File: md6_compress.c ** Author: Ronald L. Rivest ** (with optimizations by Jayant Krishnamurthy) ** Address: Room 32G-692 Stata Center ** 32 Vassar Street ** Cambridge, MA 02139 ** Email: rivest@mit.edu ** Date: 9/25/2008 ** ** (The following license is known as "The MIT License") ** ** Copyright (c) 2008 Ronald L. Rivest and Jayant Krishnamurthy ** ** Permission is hereby granted, free of charge, to any person obtaining a copy ** of this software and associated documentation files (the "Software"), to deal ** in the Software without restriction, including without limitation the rights ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell ** copies of the Software, and to permit persons to whom the Software is ** furnished to do so, subject to the following conditions: ** ** The above copyright notice and this permission notice shall be included in ** all copies or substantial portions of the Software. ** ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR ** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, ** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE ** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER ** LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, ** OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN ** THE SOFTWARE. ** ** (end of license) ** ** This is part of the definition of the MD6 hash function. ** The files defining the md6 hash function are: ** md6.h ** md6_compress.c ** md6_mode.c ** ** The files defining the interface between MD6 and the NIST SHA-3 ** API are: ** md6_nist.h ** md6_nist.c ** The NIST SHA-3 API is defined in: ** http://www.csrc.nist.gov/groups/ST/hash/documents/SHA3-C-API.pdf ** ** See http://groups.csail.mit.edu/cis/md6 for more information. ** */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "md6.h" /* Useful macros: min and max */ #ifndef min #define min(a,b) ((a)<(b)? (a) : (b)) #endif #ifndef max #define max(a,b) ((a)>(b)? (a) : (b)) #endif /* Variables defining lengths of various values */ #define w md6_w /* # bits in a word (64) */ #define n md6_n /* # words in compression input (89) */ #define c md6_c /* # words in compression output (16) */ #define b md6_b /* # message words per compression input block (64) */ #define v md6_v /* # words in control word (1) */ #define u md6_u /* # words in unique nodeID (1) */ #define k md6_k /* # key words per compression input block (8) */ #define q md6_q /* # Q words per compression input block (15) */ /* "Tap positions" for feedback shift-register */ #if (n==89) #define t0 17 /* index for linear feedback */ #define t1 18 /* index for first input to first and */ #define t2 21 /* index for second input to first and */ #define t3 31 /* index for first input to second and */ #define t4 67 /* index for second input to second and */ #define t5 89 /* last tap */ #endif /* Loop-unrolling setup. ** ** Define macros for loop-unrolling within compression function ** These expand to: loop_body(right-shift,left-shift,step) ** These are given for word sizes 64, 32, 16, and 8, although ** only w=64 is needed for the standard MD6 definition. ** ** Also given for each word size are the constants S0 and Smask ** needed in the recurrence for round constants. */ #if (w==64) /* for standard word size */ #define RL00 loop_body(10,11, 0) #define RL01 loop_body( 5,24, 1) #define RL02 loop_body(13, 9, 2) #define RL03 loop_body(10,16, 3) #define RL04 loop_body(11,15, 4) #define RL05 loop_body(12, 9, 5) #define RL06 loop_body( 2,27, 6) #define RL07 loop_body( 7,15, 7) #define RL08 loop_body(14, 6, 8) #define RL09 loop_body(15, 2, 9) #define RL10 loop_body( 7,29,10) #define RL11 loop_body(13, 8,11) #define RL12 loop_body(11,15,12) #define RL13 loop_body( 7, 5,13) #define RL14 loop_body( 6,31,14) #define RL15 loop_body(12, 9,15) const md6_word S0 = (md6_word)0x0123456789abcdefULL; const md6_word Smask = (md6_word)0x7311c2812425cfa0ULL; #elif (w==32) /* for variant word size */ #define RL00 loop_body( 5, 4, 0) #define RL01 loop_body( 3, 7, 1) #define RL02 loop_body( 6, 7, 2) #define RL03 loop_body( 5, 9, 3) #define RL04 loop_body( 4,13, 4) #define RL05 loop_body( 6, 8, 5) #define RL06 loop_body( 7, 4, 6) #define RL07 loop_body( 3,14, 7) #define RL08 loop_body( 5, 7, 8) #define RL09 loop_body( 6, 4, 9) #define RL10 loop_body( 5, 8,10) #define RL11 loop_body( 5,11,11) #define RL12 loop_body( 4, 5,12) #define RL13 loop_body( 6, 8,13) #define RL14 loop_body( 7, 2,14) #define RL15 loop_body( 5,11,15) const md6_word S0 = (md6_word)0x01234567UL; const md6_word Smask = (md6_word)0x7311c281UL; /* Loop-unrolling setup (continued). ** */ #elif (w==16) /* for variant word size */ #define RL00 loop_body( 5, 6, 0) #define RL01 loop_body( 4, 7, 1) #define RL02 loop_body( 3, 2, 2) #define RL03 loop_body( 5, 4, 3) #define RL04 loop_body( 7, 2, 4) #define RL05 loop_body( 5, 6, 5) #define RL06 loop_body( 5, 3, 6) #define RL07 loop_body( 2, 7, 7) #define RL08 loop_body( 4, 5, 8) #define RL09 loop_body( 3, 7, 9) #define RL10 loop_body( 4, 6,10) #define RL11 loop_body( 3, 5,11) #define RL12 loop_body( 4, 5,12) #define RL13 loop_body( 7, 6,13) #define RL14 loop_body( 7, 4,14) #define RL15 loop_body( 2, 3,15) const md6_word S0 = (md6_word)0x01234; const md6_word Smask = (md6_word)0x7311; #elif (w==8) /* for variant word size */ #define RL00 loop_body( 3, 2, 0) #define RL01 loop_body( 3, 4, 1) #define RL02 loop_body( 3, 2, 2) #define RL03 loop_body( 4, 3, 3) #define RL04 loop_body( 3, 2, 4) #define RL05 loop_body( 3, 2, 5) #define RL06 loop_body( 3, 2, 6) #define RL07 loop_body( 3, 4, 7) #define RL08 loop_body( 2, 3, 8) #define RL09 loop_body( 2, 3, 9) #define RL10 loop_body( 3, 2,10) #define RL11 loop_body( 2, 3,11) #define RL12 loop_body( 2, 3,12) #define RL13 loop_body( 3, 4,13) #define RL14 loop_body( 2, 3,14) #define RL15 loop_body( 3, 4,15) const md6_word S0 = (md6_word)0x01; const md6_word Smask = (md6_word)0x73; #endif /* Main compression loop. ** */ void md6_main_compression_loop( md6_word* A , int r ) /* ** Perform the md6 "main compression loop" on the array A. ** This is where most of the computation occurs; it is the "heart" ** of the md6 compression algorithm. ** Input: ** A input array of length t+n already set up ** with input in the first n words. ** r number of rounds to run (178); each is c steps ** Modifies: ** A A[n..r*c+n-1] filled in. */ { md6_word x, S; int i,j; /* ** main computation loop for md6 compression */ S = S0; for (j = 0, i = n; j<r*c; j+=c) { /* ***************************************************************** */ #define loop_body(rs,ls,step) \ x = S; /* feedback constant */ \ x ^= A[i+step-t5]; /* end-around feedback */ \ x ^= A[i+step-t0]; /* linear feedback */ \ x ^= ( A[i+step-t1] & A[i+step-t2] ); /* first quadratic term */ \ x ^= ( A[i+step-t3] & A[i+step-t4] ); /* second quadratic term */ \ x ^= (x >> rs); /* right-shift */ \ A[i+step] = x ^ (x << ls); /* left-shift */ /* ***************************************************************** */ /* ** Unroll loop c=16 times. (One "round" of computation.) ** Shift amounts are embedded in macros RLnn. */ RL00 RL01 RL02 RL03 RL04 RL05 RL06 RL07 RL08 RL09 RL10 RL11 RL12 RL13 RL14 RL15 /* Advance round constant S to the next round constant. */ S = (S << 1) ^ (S >> (w-1)) ^ (S & Smask); i += 16; } } /* ``Bare'' compression routine. ** ** Compresses n-word input to c-word output. */ int md6_compress( md6_word *C, md6_word *N, int r, md6_word *A ) /* Assumes n-word input array N has been fully set up. ** Input: ** N input array of n w-bit words (n=89) ** A working array of a = rc+n w-bit words ** A is OPTIONAL, may be given as NULL ** (then md6_compress allocates and uses its own A). ** r number of rounds ** Modifies: ** C output array of c w-bit words (c=16) ** Returns one of the following: ** MD6_SUCCESS (0) ** MD6_NULL_N ** MD6_NULL_C ** MD6_BAD_r ** MD6_OUT_OF_MEMORY */ { md6_word* A_as_given = A; /* check that input is sensible */ if ( N == NULL) return MD6_NULL_N; if ( C == NULL) return MD6_NULL_C; if ( r<0 || r > md6_max_r) return MD6_BAD_r; if ( A == NULL) A = calloc(r*c+n,sizeof(md6_word)); if ( A == NULL) return MD6_OUT_OF_MEMORY; memcpy( A, N, n*sizeof(md6_word) ); /* copy N to front of A */ md6_main_compression_loop( A, r ); /* do all the work */ memcpy( C, A+(r-1)*c+n, c*sizeof(md6_word) ); /* output into C */ if ( A_as_given == NULL ) /* zero and free A if nec. */ { memset(A,0,(r*c+n)*sizeof(md6_word)); /* contains key info */ free(A); } return MD6_SUCCESS; } /* Control words. */ md6_control_word md6_make_control_word( int r, int L, int z, int p, int keylen, int d ) /* Construct control word V for given inputs. ** Input: ** r = number of rounds ** L = mode parameter (maximum tree height) ** z = 1 iff this is final compression operation ** p = number of pad bits in a block to be compressed ** keylen = number of bytes in key ** d = desired hash output length ** Does not check inputs for validity. ** Returns: ** V = constructed control word */ { md6_control_word V; V = ( (((md6_control_word) 0) << 60) | /* reserved, width 4 bits */ (((md6_control_word) r) << 48) | /* width 12 bits */ (((md6_control_word) L) << 40) | /* width 8 bits */ (((md6_control_word) z) << 36) | /* width 4 bits */ (((md6_control_word) p) << 20) | /* width 16 bits */ (((md6_control_word) keylen) << 12 ) | /* width 8 bits */ (((md6_control_word) d)) ); /* width 12 bits */ return V; } /* Node ID's. */ md6_nodeID md6_make_nodeID( int ell, /* level number */ int i /* index (0,1,2,...) within level */ ) /* Make "unique nodeID" U based on level ell and position i ** within level; place it at specified destination. ** Inputs: ** dest = address of where nodeID U should be placed ** ell = integer level number, 1 <= ell <= ... ** i = index within level, i = 0, 1, 2,... ** Returns ** U = constructed nodeID */ { md6_nodeID U; U = ( (((md6_nodeID) ell) << 56) | ((md6_nodeID) i) ); return U; } /* Assembling components of compression input. */ void md6_pack( md6_word*N, const md6_word* Q, md6_word* K, int ell, int i, int r, int L, int z, int p, int keylen, int d, md6_word* B ) /* Pack data before compression into n-word array N. */ { int j; int ni; md6_nodeID U; md6_control_word V; ni = 0; for (j=0;j<q;j++) N[ni++] = Q[j]; /* Q: Q in words 0--14 */ for (j=0;j<k;j++) N[ni++] = K[j]; /* K: key in words 15--22 */ U = md6_make_nodeID(ell,i); /* U: unique node ID in 23 */ /* The following also works for variants ** in which u=0. */ memcpy((unsigned char *)&N[ni], &U, min(u*(w/8),sizeof(md6_nodeID))); ni += u; V = md6_make_control_word( r,L,z,p,keylen,d);/* V: control word in 24 */ /* The following also works for variants ** in which v=0. */ memcpy((unsigned char *)&N[ni], &V, min(v*(w/8),sizeof(md6_control_word))); ni += v; memcpy(N+ni,B,b*sizeof(md6_word)); /* B: data words 25--88 */ } /* Standard compress: assemble components and then compress */ int md6_standard_compress( md6_word* C, const md6_word* Q, md6_word* K, int ell, int i, int r, int L, int z, int p, int keylen, int d, md6_word* B ) /* Perform md6 block compression using all the "standard" inputs. ** Input: ** Q q-word (q=15) approximation to (sqrt(6)-2) ** K k-word key input (k=8) ** ell level number ** i index within level ** r number of rounds in this compression operation ** L mode parameter (max tree height) ** z 1 iff this is the very last compression ** p number of padding bits of input in payload B ** keylen number of bytes in key ** d desired output hash bit length ** B b-word (64-word) data input block (with zero padding) ** Modifies: ** C c-word output array (c=16) ** Returns one of the following: ** MD6_SUCCESS (0) MD6_BAD_p ** MD6_NULL_B MD6_BAD_HASHLEN ** MD6_NULL_C MD6_NULL_K ** MD6_BAD_r MD6_NULL_Q ** MD6_BAD_ELL MD6_OUT_OF_MEMORY */ { md6_word N[md6_n]; md6_word A[5000]; /* MS VS can't handle variable size here */ /* check that input values are sensible */ if ( (C == NULL) ) return MD6_NULL_C; if ( (B == NULL) ) return MD6_NULL_B; if ( (r<0) | (r>md6_max_r) ) return MD6_BAD_r; if ( (L<0) | (L>255) ) return MD6_BAD_L; if ( (ell < 0) || (ell > 255) ) return MD6_BAD_ELL; if ( (p < 0) || (p > b*w ) ) return MD6_BAD_p; if ( (d <= 0) || (d > c*w/2) ) return MD6_BADHASHLEN; if ( (K == NULL) ) return MD6_NULL_K; if ( (Q == NULL) ) return MD6_NULL_Q; /* pack components into N for compression */ md6_pack(N,Q,K,ell,i,r,L,z,p,keylen,d,B); /* call compression hook if it is defined. */ /* -- for testing and debugging. */ if (compression_hook != NULL) compression_hook(C,Q,K,ell,i,r,L,z,p,keylen,d,B); return md6_compress(C,N,r,A); } /* end of md6_compress.c */
Go to most recent revision | Compare with Previous | Blame | View Log