UnixCrypt xref

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