KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > mortbay > util > UnixCrypt


1 /*
2  * @(#)UnixCrypt.java 0.9 96/11/25
3  *
4  * Copyright (c) 1996 Aki Yoshida. All rights reserved.
5  *
6  * Permission to use, copy, modify and distribute this software
7  * for non-commercial or commercial purposes and without fee is
8  * hereby granted provided that this copyright notice appears in
9  * all copies.
10  */
11
12 /**
13  * Unix crypt(3C) utility
14  *
15  * @version 0.9, 11/25/96
16  * @author Aki Yoshida
17  */
18
19 /**
20  * modified April 2001
21  * by Iris Van den Broeke, Daniel Deville
22  */
23
24 package org.mortbay.util;
25
26 /* ------------------------------------------------------------ */
27 /** Unix Crypt.
28  * Implements the one way cryptography used by Unix systems for
29  * simple password protection.
30  * @version $Id: UnixCrypt.java,v 1.5 2004/10/11 00:28:41 gregwilkins Exp $
31  * @author Greg Wilkins (gregw)
32  */
33 public class UnixCrypt extends Object JavaDoc
34 {
35
36     /* (mostly) Standard DES Tables from Tom Truscott */
37     private static final byte[] IP = { /* initial permutation */
38         58, 50, 42, 34, 26, 18, 10, 2,
39         60, 52, 44, 36, 28, 20, 12, 4,
40         62, 54, 46, 38, 30, 22, 14, 6,
41         64, 56, 48, 40, 32, 24, 16, 8,
42         57, 49, 41, 33, 25, 17, 9, 1,
43         59, 51, 43, 35, 27, 19, 11, 3,
44         61, 53, 45, 37, 29, 21, 13, 5,
45         63, 55, 47, 39, 31, 23, 15, 7};
46
47     /* The final permutation is the inverse of IP - no table is necessary */
48     private static final byte[] ExpandTr = { /* expansion operation */
49         32, 1, 2, 3, 4, 5,
50         4, 5, 6, 7, 8, 9,
51         8, 9, 10, 11, 12, 13,
52         12, 13, 14, 15, 16, 17,
53         16, 17, 18, 19, 20, 21,
54         20, 21, 22, 23, 24, 25,
55         24, 25, 26, 27, 28, 29,
56         28, 29, 30, 31, 32, 1};
57
58     private static final byte[] PC1 = { /* permuted choice table 1 */
59         57, 49, 41, 33, 25, 17, 9,
60         1, 58, 50, 42, 34, 26, 18,
61         10, 2, 59, 51, 43, 35, 27,
62         19, 11, 3, 60, 52, 44, 36,
63     
64         63, 55, 47, 39, 31, 23, 15,
65         7, 62, 54, 46, 38, 30, 22,
66         14, 6, 61, 53, 45, 37, 29,
67         21, 13, 5, 28, 20, 12, 4};
68
69     private static final byte[] Rotates = { /* PC1 rotation schedule */
70         1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
71
72
73     private static final byte[] PC2 = { /* permuted choice table 2 */
74         9, 18, 14, 17, 11, 24, 1, 5,
75         22, 25, 3, 28, 15, 6, 21, 10,
76         35, 38, 23, 19, 12, 4, 26, 8,
77         43, 54, 16, 7, 27, 20, 13, 2,
78
79         0, 0, 41, 52, 31, 37, 47, 55,
80         0, 0, 30, 40, 51, 45, 33, 48,
81         0, 0, 44, 49, 39, 56, 34, 53,
82         0, 0, 46, 42, 50, 36, 29, 32};
83
84     private static final byte[][] S = { /* 48->32 bit substitution tables */
85         /* S[1] */
86         {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
87          0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
88          4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
89          15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13},
90         /* S[2] */
91         {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
92          3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
93          0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
94          13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9},
95         /* S[3] */
96         {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
97          13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
98          13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
99          1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12},
100         /* S[4] */
101         {7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
102          13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
103          10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
104          3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14},
105         /* S[5] */
106         {2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
107          14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
108          4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
109          11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3},
110         /* S[6] */
111         {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
112          10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
113          9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
114          4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13},
115         /* S[7] */
116         {4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
117          13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
118          1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
119          6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12},
120         /* S[8] */
121         {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
122          1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
123          7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
124          2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}};
125
126     private static final byte[] P32Tr = { /* 32-bit permutation function */
127         16, 7, 20, 21,
128         29, 12, 28, 17,
129         1, 15, 23, 26,
130         5, 18, 31, 10,
131         2, 8, 24, 14,
132         32, 27, 3, 9,
133         19, 13, 30, 6,
134         22, 11, 4, 25};
135
136     private static final byte[] CIFP = { /* compressed/interleaved permutation */
137         1, 2, 3, 4, 17, 18, 19, 20,
138         5, 6, 7, 8, 21, 22, 23, 24,
139         9, 10, 11, 12, 25, 26, 27, 28,
140         13, 14, 15, 16, 29, 30, 31, 32,
141
142         33, 34, 35, 36, 49, 50, 51, 52,
143         37, 38, 39, 40, 53, 54, 55, 56,
144         41, 42, 43, 44, 57, 58, 59, 60,
145         45, 46, 47, 48, 61, 62, 63, 64};
146
147     private static final byte[] ITOA64 = { /* 0..63 => ascii-64 */
148         (byte)'.',(byte) '/',(byte) '0',(byte) '1',(byte) '2',(byte) '3',(byte) '4',(byte) '5',
149         (byte)'6',(byte) '7',(byte) '8',(byte) '9',(byte) 'A',(byte) 'B',(byte) 'C',(byte) 'D',
150         (byte)'E',(byte) 'F',(byte) 'G',(byte) 'H',(byte) 'I',(byte) 'J',(byte) 'K',(byte) 'L',
151         (byte)'M',(byte) 'N',(byte) 'O',(byte) 'P',(byte) 'Q',(byte) 'R',(byte) 'S',(byte) 'T',
152         (byte)'U',(byte) 'V',(byte) 'W',(byte) 'X',(byte) 'Y',(byte) 'Z',(byte) 'a',(byte) 'b',
153         (byte)'c',(byte) 'd',(byte) 'e',(byte) 'f',(byte) 'g',(byte) 'h',(byte) 'i',(byte) 'j',
154         (byte)'k',(byte) 'l',(byte) 'm',(byte) 'n',(byte) 'o',(byte) 'p',(byte) 'q',(byte) 'r',
155         (byte)'s',(byte) 't',(byte) 'u',(byte) 'v',(byte) 'w',(byte) 'x',(byte) 'y',(byte) 'z'};
156
157     /* ===== Tables that are initialized at run time ==================== */
158
159     private static byte[] A64TOI = new byte[128]; /* ascii-64 => 0..63 */
160
161     /* Initial key schedule permutation */
162     private static long[][] PC1ROT = new long[16][16];
163
164     /* Subsequent key schedule rotation permutations */
165     private static long[][][] PC2ROT = new long[2][16][16];
166
167     /* Initial permutation/expansion table */
168     private static long[][] IE3264 = new long[8][16];
169
170     /* Table that combines the S, P, and E operations. */
171     private static long[][] SPE = new long[8][64];
172
173     /* compressed/interleaved => final permutation table */
174     private static long[][] CF6464 = new long[16][16];
175
176
177     /* ==================================== */
178
179     static {
180         byte[] perm = new byte[64];
181         byte[] temp = new byte[64];
182
183         // inverse table.
184 for (int i=0; i<64; i++) A64TOI[ITOA64[i]] = (byte)i;
185
186         // PC1ROT - bit reverse, then PC1, then Rotate, then PC2
187 for (int i=0; i<64; i++) perm[i] = (byte)0;;
188         for (int i=0; i<64; i++) {
189             int k;
190             if ((k = (int)PC2[i]) == 0) continue;
191             k += Rotates[0]-1;
192             if ((k%28) < Rotates[0]) k -= 28;
193             k = (int)PC1[k];
194             if (k > 0) {
195                 k--;
196                 k = (k|0x07) - (k&0x07);
197                 k++;
198             }
199             perm[i] = (byte)k;
200         }
201         init_perm(PC1ROT, perm, 8);
202
203         // PC2ROT - PC2 inverse, then Rotate, then PC2
204 for (int j=0; j<2; j++) {
205             int k;
206             for (int i=0; i<64; i++) perm[i] = temp[i] = 0;
207             for (int i=0; i<64; i++) {
208                 if ((k = (int)PC2[i]) == 0) continue;
209                 temp[k-1] = (byte)(i+1);
210             }
211             for (int i=0; i<64; i++) {
212                 if ((k = (int)PC2[i]) == 0) continue;
213                 k += j;
214                 if ((k%28) <= j) k -= 28;
215                 perm[i] = temp[k];
216             }
217
218             init_perm(PC2ROT[j], perm, 8);
219         }
220
221         // Bit reverse, intial permupation, expantion
222 for (int i=0; i<8; i++) {
223             for (int j=0; j<8; j++) {
224                 int k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1];
225                 if (k > 32) k -= 32;
226                 else if (k > 0) k--;
227                 if (k > 0) {
228                     k--;
229                     k = (k|0x07) - (k&0x07);
230                     k++;
231                 }
232                 perm[i*8+j] = (byte)k;
233             }
234         }
235
236         init_perm(IE3264, perm, 8);
237
238         // Compression, final permutation, bit reverse
239 for (int i=0; i<64; i++) {
240             int k = IP[CIFP[i]-1];
241             if (k > 0) {
242                 k--;
243                 k = (k|0x07) - (k&0x07);
244                 k++;
245             }
246             perm[k-1] = (byte)(i+1);
247         }
248
249         init_perm(CF6464, perm, 8);
250
251         // SPE table
252 for (int i=0; i<48; i++)
253             perm[i] = P32Tr[ExpandTr[i]-1];
254         for (int t=0; t<8; t++) {
255             for (int j=0; j<64; j++) {
256                 int k = (((j >> 0) & 0x01) << 5) | (((j >> 1) & 0x01) << 3) |
257                     (((j >> 2) & 0x01) << 2) | (((j >> 3) & 0x01) << 1) |
258                     (((j >> 4) & 0x01) << 0) | (((j >> 5) & 0x01) << 4);
259                 k = S[t][k];
260                 k = (((k >> 3) & 0x01) << 0) | (((k >> 2) & 0x01) << 1) |
261                     (((k >> 1) & 0x01) << 2) | (((k >> 0) & 0x01) << 3);
262                 for (int i=0; i<32; i++) temp[i] = 0;
263                 for (int i=0; i<4; i++) temp[4*t+i] = (byte)((k >> i) & 0x01);
264                 long kk = 0;
265                 for (int i=24; --i>=0; ) kk = ((kk<<1) |
266                                                ((long)temp[perm[i]-1])<<32 |
267                                                ((long)temp[perm[i+24]-1]));
268
269                 SPE[t][j] = to_six_bit(kk);
270             }
271         }
272     }
273
274     /**
275      * You can't call the constructer.
276      */
277     private UnixCrypt() { }
278
279     /**
280      * Returns the transposed and split code of a 24-bit code
281      * into a 4-byte code, each having 6 bits.
282      */
283     private static int to_six_bit(int num) {
284         return (((num << 26) & 0xfc000000) | ((num << 12) & 0xfc0000) |
285                 ((num >> 2) & 0xfc00) | ((num >> 16) & 0xfc));
286     }
287
288     /**
289      * Returns the transposed and split code of two 24-bit code
290      * into two 4-byte code, each having 6 bits.
291      */
292     private static long to_six_bit(long num) {
293         return (((num << 26) & 0xfc000000fc000000L) | ((num << 12) & 0xfc000000fc0000L) |
294                 ((num >> 2) & 0xfc000000fc00L) | ((num >> 16) & 0xfc000000fcL));
295     }
296   
297     /**
298      * Returns the permutation of the given 64-bit code with
299      * the specified permutataion table.
300      */
301     private static long perm6464(long c, long[][]p) {
302         long out = 0L;
303         for (int i=8; --i>=0; ) {
304             int t = (int)(0x00ff & c);
305             c >>= 8;
306             long tp = p[i<<1][t&0x0f];
307             out |= tp;
308             tp = p[(i<<1)+1][t>>4];
309             out |= tp;
310         }
311         return out;
312     }
313
314     /**
315      * Returns the permutation of the given 32-bit code with
316      * the specified permutataion table.
317      */
318     private static long perm3264(int c, long[][]p) {
319         long out = 0L;
320         for (int i=4; --i>=0; ) {
321             int t = (0x00ff & c);
322             c >>= 8;
323             long tp = p[i<<1][t&0x0f];
324             out |= tp;
325             tp = p[(i<<1)+1][t>>4];
326             out |= tp;
327         }
328         return out;
329     }
330
331     /**
332      * Returns the key schedule for the given key.
333      */
334     private static long[] des_setkey(long keyword) {
335         long K = perm6464(keyword, PC1ROT);
336         long[] KS = new long[16];
337         KS[0] = K&~0x0303030300000000L;
338     
339         for (int i=1; i<16; i++) {
340             KS[i] = K;
341             K = perm6464(K, PC2ROT[Rotates[i]-1]);
342
343             KS[i] = K&~0x0303030300000000L;
344         }
345         return KS;
346     }
347
348     /**
349      * Returns the DES encrypted code of the given word with the specified
350      * environment.
351      */
352     private static long des_cipher(long in, int salt, int num_iter, long[] KS) {
353         salt = to_six_bit(salt);
354         long L = in;
355         long R = L;
356         L &= 0x5555555555555555L;
357         R = (R & 0xaaaaaaaa00000000L) | ((R >> 1) & 0x0000000055555555L);
358         L = ((((L << 1) | (L << 32)) & 0xffffffff00000000L) |
359              ((R | (R >> 32)) & 0x00000000ffffffffL));
360     
361         L = perm3264((int)(L>>32), IE3264);
362         R = perm3264((int)(L&0xffffffff), IE3264);
363
364         while (--num_iter >= 0) {
365             for (int loop_count=0; loop_count<8; loop_count++) {
366                 long kp;
367                 long B;
368                 long k;
369
370                 kp = KS[(loop_count<<1)];
371                 k = ((R>>32) ^ R) & salt & 0xffffffffL;
372                 k |= (k<<32);
373                 B = (k ^ R ^ kp);
374
375                 L ^= (SPE[0][(int)((B>>58)&0x3f)] ^ SPE[1][(int)((B>>50)&0x3f)] ^
376                       SPE[2][(int)((B>>42)&0x3f)] ^ SPE[3][(int)((B>>34)&0x3f)] ^
377                       SPE[4][(int)((B>>26)&0x3f)] ^ SPE[5][(int)((B>>18)&0x3f)] ^
378                       SPE[6][(int)((B>>10)&0x3f)] ^ SPE[7][(int)((B>>2)&0x3f)]);
379
380                 kp = KS[(loop_count<<1)+1];
381                 k = ((L>>32) ^ L) & salt & 0xffffffffL;
382                 k |= (k<<32);
383                 B = (k ^ L ^ kp);
384
385                 R ^= (SPE[0][(int)((B>>58)&0x3f)] ^ SPE[1][(int)((B>>50)&0x3f)] ^
386                       SPE[2][(int)((B>>42)&0x3f)] ^ SPE[3][(int)((B>>34)&0x3f)] ^
387                       SPE[4][(int)((B>>26)&0x3f)] ^ SPE[5][(int)((B>>18)&0x3f)] ^
388                       SPE[6][(int)((B>>10)&0x3f)] ^ SPE[7][(int)((B>>2)&0x3f)]);
389             }
390             // swap L and R
391 L ^= R;
392             R ^= L;
393             L ^= R;
394         }
395         L = ((((L>>35) & 0x0f0f0f0fL) | (((L&0xffffffff)<<1) & 0xf0f0f0f0L))<<32 |
396              (((R>>35) & 0x0f0f0f0fL) | (((R&0xffffffff)<<1) & 0xf0f0f0f0L)));
397
398         L = perm6464(L, CF6464);
399
400         return L;
401     }
402
403     /**
404      * Initializes the given permutation table with the mapping table.
405      */
406     private static void init_perm(long[][] perm, byte[] p,int chars_out) {
407         for (int k=0; k<chars_out*8; k++) {
408
409             int l = p[k] - 1;
410             if (l < 0) continue;
411             int i = l>>2;
412             l = 1<<(l&0x03);
413             for (int j=0; j<16; j++) {
414                 int s = ((k&0x07)+((7-(k>>3))<<3));
415                 if ((j & l) != 0x00) perm[i][j] |= (1L<<s);
416             }
417         }
418     }
419
420     /**
421      * Encrypts String into crypt (Unix) code.
422      * @param key the key to be encrypted
423      * @param setting the salt to be used
424      * @return the encrypted String
425      */
426     public static String JavaDoc crypt(String JavaDoc key, String JavaDoc setting)
427     {
428         long constdatablock = 0L; /* encryption constant */
429         byte[] cryptresult = new byte[13]; /* encrypted result */
430         long keyword = 0L;
431         /* invalid parameters! */
432         if(key==null||setting==null)
433             return "*"; // will NOT match under ANY circumstances!
434
435         int keylen = key.length();
436
437         for (int i=0; i<8 ; i++) {
438             keyword = (keyword << 8) | ((i < keylen)? 2*key.charAt(i): 0);
439         }
440
441         long[] KS = des_setkey(keyword);
442
443         int salt = 0;
444         for (int i=2; --i>=0;) {
445             char c = (i < setting.length())? setting.charAt(i): '.';
446             cryptresult[i] = (byte)c;
447             salt = (salt<<6) | (0x00ff&A64TOI[c]);
448         }
449
450         long rsltblock = des_cipher(constdatablock, salt, 25, KS);
451
452         cryptresult[12] = ITOA64[(((int)rsltblock)<<2)&0x3f];
453         rsltblock >>= 4;
454         for (int i=12; --i>=2; ) {
455             cryptresult[i] = ITOA64[((int)rsltblock)&0x3f];
456             rsltblock >>= 6;
457         }
458
459         return new String JavaDoc(cryptresult, 0x00, 0, 13);
460     }
461
462     public static void main(String JavaDoc[] arg)
463     {
464         if (arg.length!=2)
465         {
466             System.err.println("Usage - java org.mortbay.util.UnixCrypt <key> <salt>");
467             System.exit(1);
468         }
469
470         System.err.println("Crypt="+crypt(arg[0],arg[1]));
471     }
472     
473 }
474
475
Popular Tags