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