View Javadoc

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.jetty.security;
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.1 2005/10/05 14:09:14 janb Exp $
31   * @author Greg Wilkins (gregw)
32   */
33  public class UnixCrypt extends Object
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 crypt(String key, String 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(cryptresult, 0x00, 0, 13);
460     }
461 
462     public static void main(String[] 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