UnixCrypt.java revision 03928aee4356845252ac6b662d5c72c29903813e 
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
24package org.eclipse.jetty.util.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 */
35public 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}
462