Source code: Freenet/crypt/SHA1.java
1 /**<PRE>
2 * SHA1.java - An implementation of the SHA-1 Algorithm
3 * This version integrated into Freenet by Ian Clarke (02-02-2000)
4 * (i.clarke@dynamicblue.com) from a previous public domain version by
5 * Chuck McManis (cmcmanis@netcom.com) which was public domain
6 * Tweaked by Mr.Tines<tines@windsong.demon.co.uk> for pegwit, June 1997
7 * - added method 'frob()' which wipes the contents, so as to match
8 * the bizarre behaviour of Pegwit's double barreled hashing.
9 *
10 * Based on the C code that Steve Reid wrote his header
11 * was :
12 * SHA-1 in C
13 * By Steve Reid <steve@edmweb.com>
14 * 100% Public Domain
15 *
16 * Test Vectors (from FIPS PUB 180-1)
17 * "abc"
18 * A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D
19 * "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
20 * 84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1
21 * A million repetitions of "a"
22 * 34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F
23 </pre>*/
24 package Freenet.crypt;
25 import java.util.*;
26
27 /**
28 * This is a simple port of Steve Reid's SHA-1 code into Java.
29 * I've run his test vectors through the code and they all pass.
30 *
31 */
32 public class SHA1
33 {
34 /**
35 * This takes a string and return a hash of that string.
36 **/
37 public String doHash(String s)
38 {
39 this.init();
40 for (int i=0; i<s.length(); i++)
41 {
42 this.update((byte) s.charAt(i));
43 }
44 this.finish();
45 return this.digout();
46 }
47
48 private int state[] = new int[5];
49 private long count;
50 private boolean digestValid = false;
51 private byte[] digestBits;
52 private boolean NSA = true;
53
54 /**
55 * retrieve the value of a hash
56 * @param digest int[] into which to place 5 elements
57 * @param offset index of first of the 5 elements
58 */
59 public void extract(int[] digest, int offset)
60 {
61 for(int i=0; i<5; ++i)
62 {
63 digest[i+offset] =
64 ((digestBits[4*i+0]<<24) & 0xFF000000) |
65 ((digestBits[4*i+1]<<16) & 0x00FF0000) |
66 ((digestBits[4*i+2]<< 8) & 0x0000FF00) |
67 ((digestBits[4*i+3] ) & 0x000000FF);
68 }
69 }
70
71 /**
72 * Variant constructor
73 * @param b true for SHA-1, false for the original SHA-0
74 */
75 public SHA1(boolean b) {
76 count = 0;
77 digestValid = false;
78 NSA = b;
79 init();
80 }
81 /**
82 * Simple constructor for SHA-1
83 */
84 public SHA1() {
85 this(true);
86 }
87
88 /*
89 * The following array forms the basis for the transform
90 * buffer. Update puts bytes into this buffer and then
91 * transform adds it into the state of the digest.
92 */
93 private int block[] = new int[16];
94 private int blockIndex;
95
96 /*
97 * These functions are taken out of #defines in Steve's
98 * code. Java doesn't have a preprocessor so the first
99 * step is to just promote them to real methods.
100 * Later we can optimize them out into inline code,
101 * note that by making them final some compilers will
102 * inline them when given the -O flag.
103 */
104 private final int rol(int value, int bits) {
105 int q = (value << bits) | (value >>> (32 - bits));
106 return q;
107 }
108
109 private final int blk0(int i) {
110 block[i] = (rol(block[i],24)&0xFF00FF00) |
111 (rol(block[i],8)&0x00FF00FF);
112 return block[i];
113 }
114
115 private final int blk(int i) {
116 block[i&15] = block[(i+13)&15]^block[(i+8)&15]^
117 block[(i+2)&15]^block[i&15];
118 if(NSA)
119 { // this makes it SHA-1
120 block[i&15] = rol(block[i&15], 1);
121 }
122 return (block[i&15]);
123 }
124
125 private final void R0(int data[], int v, int w, int x , int y, int z, int i) {
126 data[z] += ((data[w] & (data[x] ^ data[y] )) ^ data[y]) +
127 blk0(i) + 0x5A827999 + rol(data[v] ,5);
128 data[w] = rol(data[w], 30);
129 }
130
131 private final void R1(int data[], int v, int w, int x, int y, int z, int i) {
132 data[z] += ((data[w] & (data[x] ^ data[y])) ^ data[y]) +
133 blk(i) + 0x5A827999 + rol(data[v] ,5);
134 data[w] = rol(data[w], 30);
135 }
136
137 private final void R2(int data[], int v, int w, int x, int y, int z, int i) {
138 data[z] += (data[w] ^ data[x] ^ data[y]) +
139 blk(i) + 0x6ED9EBA1 + rol(data[v] ,5);
140 data[w] = rol(data[w], 30);
141 }
142
143 private final void R3(int data[], int v, int w, int x, int y, int z, int i) {
144 data[z] += (((data[w] | data[x]) & data[y]) | (data[w] & data[x])) +
145 blk(i) + 0x8F1BBCDC + rol(data[v] ,5);
146 data[w] = rol(data[w], 30);
147 }
148
149 private final void R4(int data[], int v, int w, int x, int y, int z, int i) {
150 data[z] += (data[w] ^ data[x] ^ data[y]) +
151 blk(i) + 0xCA62C1D6 + rol(data[v] ,5);
152 data[w] = rol(data[w], 30);
153 }
154
155
156 /*
157 * Steve's original code and comments :
158 *
159 * blk0() and blk() perform the initial expand.
160 * I got the idea of expanding during the round function from SSLeay
161 *
162 * #define blk0(i) block->l[i]
163 * #define blk(i) (block->l[i&15] = rol(block->l[(i+13)&15]^block->l[(i+8)&15] \
164 * ^block->l[(i+2)&15]^block->l[i&15],1))
165 *
166 * (R0+R1), R2, R3, R4 are the different operations used in SHA1
167 * #define R0(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk0(i)+0x5A827999+rol(v,5);w=rol(w,30);
168 * #define R1(v,w,x,y,z,i) z+=((w&(x^y))^y)+blk(i)+0x5A827999+rol(v,5);w=rol(w,30);
169 * #define R2(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0x6ED9EBA1+rol(v,5);w=rol(w,30);
170 * #define R3(v,w,x,y,z,i) z+=(((w|x)&y)|(w&x))+blk(i)+0x8F1BBCDC+rol(v,5);w=rol(w,30);
171 * #define R4(v,w,x,y,z,i) z+=(w^x^y)+blk(i)+0xCA62C1D6+rol(v,5);w=rol(w,30);
172 */
173
174 private int dd[] = new int[5];
175
176 /**
177 * Hash a single 512-bit block. This is the core of the algorithm.
178 *
179 * Note that working with arrays is very inefficent in Java as it
180 * does a class cast check each time you store into the array.
181 *
182 */
183
184 private void transform() {
185
186 /* Copy context->state[] to working vars */
187 dd[0] = state[0];
188 dd[1] = state[1];
189 dd[2] = state[2];
190 dd[3] = state[3];
191 dd[4] = state[4];
192 /* 4 rounds of 20 operations each. Loop unrolled. */
193 R0(dd,0,1,2,3,4, 0); R0(dd,4,0,1,2,3, 1); R0(dd,3,4,0,1,2, 2); R0(dd,2,3,4,0,1, 3);
194 R0(dd,1,2,3,4,0, 4); R0(dd,0,1,2,3,4, 5); R0(dd,4,0,1,2,3, 6); R0(dd,3,4,0,1,2, 7);
195 R0(dd,2,3,4,0,1, 8); R0(dd,1,2,3,4,0, 9); R0(dd,0,1,2,3,4,10); R0(dd,4,0,1,2,3,11);
196 R0(dd,3,4,0,1,2,12); R0(dd,2,3,4,0,1,13); R0(dd,1,2,3,4,0,14); R0(dd,0,1,2,3,4,15);
197 R1(dd,4,0,1,2,3,16); R1(dd,3,4,0,1,2,17); R1(dd,2,3,4,0,1,18); R1(dd,1,2,3,4,0,19);
198 R2(dd,0,1,2,3,4,20); R2(dd,4,0,1,2,3,21); R2(dd,3,4,0,1,2,22); R2(dd,2,3,4,0,1,23);
199 R2(dd,1,2,3,4,0,24); R2(dd,0,1,2,3,4,25); R2(dd,4,0,1,2,3,26); R2(dd,3,4,0,1,2,27);
200 R2(dd,2,3,4,0,1,28); R2(dd,1,2,3,4,0,29); R2(dd,0,1,2,3,4,30); R2(dd,4,0,1,2,3,31);
201 R2(dd,3,4,0,1,2,32); R2(dd,2,3,4,0,1,33); R2(dd,1,2,3,4,0,34); R2(dd,0,1,2,3,4,35);
202 R2(dd,4,0,1,2,3,36); R2(dd,3,4,0,1,2,37); R2(dd,2,3,4,0,1,38); R2(dd,1,2,3,4,0,39);
203 R3(dd,0,1,2,3,4,40); R3(dd,4,0,1,2,3,41); R3(dd,3,4,0,1,2,42); R3(dd,2,3,4,0,1,43);
204 R3(dd,1,2,3,4,0,44); R3(dd,0,1,2,3,4,45); R3(dd,4,0,1,2,3,46); R3(dd,3,4,0,1,2,47);
205 R3(dd,2,3,4,0,1,48); R3(dd,1,2,3,4,0,49); R3(dd,0,1,2,3,4,50); R3(dd,4,0,1,2,3,51);
206 R3(dd,3,4,0,1,2,52); R3(dd,2,3,4,0,1,53); R3(dd,1,2,3,4,0,54); R3(dd,0,1,2,3,4,55);
207 R3(dd,4,0,1,2,3,56); R3(dd,3,4,0,1,2,57); R3(dd,2,3,4,0,1,58); R3(dd,1,2,3,4,0,59);
208 R4(dd,0,1,2,3,4,60); R4(dd,4,0,1,2,3,61); R4(dd,3,4,0,1,2,62); R4(dd,2,3,4,0,1,63);
209 R4(dd,1,2,3,4,0,64); R4(dd,0,1,2,3,4,65); R4(dd,4,0,1,2,3,66); R4(dd,3,4,0,1,2,67);
210 R4(dd,2,3,4,0,1,68); R4(dd,1,2,3,4,0,69); R4(dd,0,1,2,3,4,70); R4(dd,4,0,1,2,3,71);
211 R4(dd,3,4,0,1,2,72); R4(dd,2,3,4,0,1,73); R4(dd,1,2,3,4,0,74); R4(dd,0,1,2,3,4,75);
212 R4(dd,4,0,1,2,3,76); R4(dd,3,4,0,1,2,77); R4(dd,2,3,4,0,1,78); R4(dd,1,2,3,4,0,79);
213 /* Add the working vars back into context.state[] */
214 state[0] += dd[0];
215 state[1] += dd[1];
216 state[2] += dd[2];
217 state[3] += dd[3];
218 state[4] += dd[4];
219 }
220
221 /**
222 * zero the count and state arrays; used to support
223 * Pegwit's anomalous 2-barrel hsahing
224 */
225 public void frob() // Pegwit's little anomaly
226 {
227 count=0;
228 state[0] = state[1] = state[2] = state[3] = state[4] = 0;
229 }
230
231 /**
232 *
233 * Initializes new context
234 */
235 protected void init() {
236 /* SHA1 initialization constants */
237 state[0] = 0x67452301;
238 state[1] = 0xEFCDAB89;
239 state[2] = 0x98BADCFE;
240 state[3] = 0x10325476;
241 state[4] = 0xC3D2E1F0;
242 count = 0;
243 digestBits = new byte[20];
244 digestValid = false;
245 blockIndex = 0;
246 }
247
248 /**
249 * Add one byte to the digest. When this is implemented
250 * all of the abstract class methods end up calling
251 * this method for types other than bytes.
252 * @param b byte to add
253 */
254 public synchronized void update(byte b) {
255 int mask = (8 * (blockIndex & 3));
256
257 count += 8;
258 block[blockIndex >> 2] &= ~(0xff << mask);
259 block[blockIndex >> 2] |= (b & 0xff) << mask;
260 blockIndex++;
261 if (blockIndex == 64) {
262 transform();
263 blockIndex = 0;
264 }
265 }
266
267 /**
268 * Add many bytes to the digest.
269 * @param data byte data to add
270 * @param offset start byte
271 * @param length number of bytes to hash
272 */
273 public void update(byte[] data, int offset, int length)
274 {
275 for(int i=0; i<length; ++i) update(data[offset+i]);
276 }
277
278 /**
279 * Return completed digest.
280 * @return the byte array result
281 */
282 public byte[] digest()
283 {
284 finish();
285 byte [] out = new byte[20];
286 System.arraycopy(digestBits, 0, out, 0, digestBits.length);
287 init();
288 return out;
289 }
290
291 /**
292 * Complete processing on the message digest.
293 */
294 protected void finish() {
295 byte bits[] = new byte[8];
296 int i, j;
297 for (i = 0; i < 8; i++) {
298 bits[i] = (byte)((count >>> (((7 - i) * 8))) & 0xff);
299 }
300
301 update((byte) 128);
302 while (blockIndex != 56)
303 update((byte) 0);
304 // This should cause a transform to happen.
305 for(i=0; i<8; ++i) update(bits[i]);
306 for (i = 0; i < 20; i++) {
307 digestBits[i] = (byte)
308 ((state[i>>2] >>> ((3-(i & 3)) * 8) ) & 0xff);
309 }
310 digestValid = true;
311 }
312
313 /**
314 * Print out the digest in a form that can be easily compared
315 * to the test vectors.
316 */
317 protected String digout() {
318 StringBuffer sb = new StringBuffer();
319 for (int i = 0; i < 20; i++) {
320 char c1, c2;
321
322 c1 = (char) ((digestBits[i] >>> 4) & 0xf);
323 c2 = (char) (digestBits[i] & 0xf);
324 c1 = (char) ((c1 > 9) ? 'A' + (c1 - 10) : '0' + c1);
325 c2 = (char) ((c2 > 9) ? 'A' + (c2 - 10) : '0' + c2);
326 sb.append(c1);
327 sb.append(c2);
328 }
329 return sb.toString();
330 }
331
332 /**
333 * test driver
334 */
335 public static void main(String[] args)
336 {
337 SHAselfTest();
338 }
339
340 /**
341 * perfoms a self-test - spits out the test vector outputs on System.out
342 */
343 public static void SHAselfTest()
344 {
345 int i, j;
346 SHA1 s = new SHA1(true);
347 // This line may be safely deleted, its to make it easy to see
348 // the output of the program.
349 System.out.println("SHA-1 Test PROGRAM.");
350 System.out.println("This code runs the test vectors through the code.");
351
352 /* "abc"
353 A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D */
354
355 System.out.println("First test is 'abc'");
356 String z = "abc";
357 s.init();
358 s.update((byte) 'a');
359 s.update((byte) 'b');
360 s.update((byte) 'c');
361 s.finish();
362 System.out.println(s.digout());
363 System.out.println("A9993E364706816ABA3E25717850C26C9CD0D89D");
364
365 /* "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
366 84983E44 1C3BD26E BAAE4AA1 F95129E5 E54670F1 */
367
368 System.out.println("Next Test is 'abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq'");
369 z = "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
370 s.init();
371 for( i=0; i<z.length(); ++i)
372 {
373 s.update((byte) z.charAt(i));
374 }
375 s.finish();
376 System.out.println(s.digout());
377 System.out.println("84983E441C3BD26EBAAE4AA1F95129E5E54670F1");
378
379 /* A million repetitions of "a"
380 34AA973C D4C4DAA4 F61EEB2B DBAD2731 6534016F */
381 long startTime = 0 - System.currentTimeMillis();
382
383 System.out.println("Last test is 1 million 'a' characters.");
384 s.init();
385 for (i = 0; i < 1000000; i++)
386 s.update((byte) 'a');
387 s.finish();
388 System.out.println(s.digout());
389 System.out.println("34AA973CD4C4DAA4F61EEB2BDBAD27316534016F");
390 startTime += System.currentTimeMillis();
391 double d = ((double)startTime)/1000.0;
392 System.out.println(" done, elapsed time = "+d);
393 }
394 }