2 * @(#)UnixCrypt.java 0.9 96/11/25
4 * Copyright (c) 1996 Aki Yoshida. All rights reserved.
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
13 * Unix crypt(3C) utility
15 * @version 0.9, 11/25/96
21 * by Iris Van den Broeke, Daniel Deville
24 package org.eclipse.jetty.util.security;
27 /* ------------------------------------------------------------ */
29 * Unix Crypt. Implements the one way cryptography used by Unix systems for
30 * simple password protection.
32 * @version $Id: UnixCrypt.java,v 1.1 2005/10/05 14:09:14 janb Exp $
33 * @author Greg Wilkins (gregw)
35 public class UnixCrypt
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 };
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 };
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,
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 };
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 };
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,
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 };
61 private static final byte[][] S = { /* 48->32 bit substitution tables */
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 },
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 },
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 },
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 },
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 },
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 },
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 },
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 } };
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 };
90 private static final byte[] CIFP = { /*
91 * compressed/interleaved
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,
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 };
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' };
106 /* ===== Tables that are initialized at run time ==================== */
108 private static final byte[] A64TOI = new byte[128]; /* ascii-64 => 0..63 */
110 /* Initial key schedule permutation */
111 private static final long[][] PC1ROT = new long[16][16];
113 /* Subsequent key schedule rotation permutations */
114 private static final long[][][] PC2ROT = new long[2][16][16];
116 /* Initial permutation/expansion table */
117 private static final long[][] IE3264 = new long[8][16];
119 /* Table that combines the S, P, and E operations. */
120 private static final long[][] SPE = new long[8][64];
122 /* compressed/interleaved => final permutation table */
123 private static final long[][] CF6464 = new long[16][16];
125 /* ==================================== */
129 byte[] perm = new byte[64];
130 byte[] temp = new byte[64];
133 for (int i = 0; i < 64; i++)
134 A64TOI[ITOA64[i]] = (byte) i;
136 // PC1ROT - bit reverse, then PC1, then Rotate, then PC2
137 for (int i = 0; i < 64; i++)
140 for (int i = 0; i < 64; i++)
143 if ((k = PC2[i]) == 0) continue;
145 if ((k % 28) < Rotates[0]) k -= 28;
150 k = (k | 0x07) - (k & 0x07);
155 init_perm(PC1ROT, perm, 8);
157 // PC2ROT - PC2 inverse, then Rotate, then PC2
158 for (int j = 0; j < 2; j++)
161 for (int i = 0; i < 64; i++)
162 perm[i] = temp[i] = 0;
163 for (int i = 0; i < 64; i++)
165 if ((k = PC2[i]) == 0) continue;
166 temp[k - 1] = (byte) (i + 1);
168 for (int i = 0; i < 64; i++)
170 if ((k = PC2[i]) == 0) continue;
172 if ((k % 28) <= j) k -= 28;
176 init_perm(PC2ROT[j], perm, 8);
179 // Bit reverse, intial permupation, expantion
180 for (int i = 0; i < 8; i++)
182 for (int j = 0; j < 8; j++)
184 int k = (j < 2) ? 0 : IP[ExpandTr[i * 6 + j - 2] - 1];
191 k = (k | 0x07) - (k & 0x07);
194 perm[i * 8 + j] = (byte) k;
198 init_perm(IE3264, perm, 8);
200 // Compression, final permutation, bit reverse
201 for (int i = 0; i < 64; i++)
203 int k = IP[CIFP[i] - 1];
207 k = (k | 0x07) - (k & 0x07);
210 perm[k - 1] = (byte) (i + 1);
213 init_perm(CF6464, perm, 8);
216 for (int i = 0; i < 48; i++)
217 perm[i] = P32Tr[ExpandTr[i] - 1];
218 for (int t = 0; t < 8; t++)
220 for (int j = 0; j < 64; j++)
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);
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++)
231 for (int i = 0; i < 4; i++)
232 temp[4 * t + i] = (byte) ((k >> i) & 0x01);
234 for (int i = 24; --i >= 0;)
235 kk = ((kk << 1) | ((long) temp[perm[i] - 1]) << 32 | (temp[perm[i + 24] - 1]));
237 SPE[t][j] = to_six_bit(kk);
243 * You can't call the constructer.
250 * Returns the transposed and split code of a 24-bit code into a 4-byte
251 * code, each having 6 bits.
253 private static int to_six_bit(int num)
255 return (((num << 26) & 0xfc000000) | ((num << 12) & 0xfc0000) | ((num >> 2) & 0xfc00) | ((num >> 16) & 0xfc));
259 * Returns the transposed and split code of two 24-bit code into two 4-byte
260 * code, each having 6 bits.
262 private static long to_six_bit(long num)
264 return (((num << 26) & 0xfc000000fc000000L) | ((num << 12) & 0xfc000000fc0000L) | ((num >> 2) & 0xfc000000fc00L) | ((num >> 16) & 0xfc000000fcL));
268 * Returns the permutation of the given 64-bit code with the specified
269 * permutataion table.
271 private static long perm6464(long c, long[][] p)
274 for (int i = 8; --i >= 0;)
276 int t = (int) (0x00ff & c);
278 long tp = p[i << 1][t & 0x0f];
280 tp = p[(i << 1) + 1][t >> 4];
287 * Returns the permutation of the given 32-bit code with the specified
288 * permutataion table.
290 private static long perm3264(int c, long[][] p)
293 for (int i = 4; --i >= 0;)
295 int t = (0x00ff & c);
297 long tp = p[i << 1][t & 0x0f];
299 tp = p[(i << 1) + 1][t >> 4];
306 * Returns the key schedule for the given key.
308 private static long[] des_setkey(long keyword)
310 long K = perm6464(keyword, PC1ROT);
311 long[] KS = new long[16];
312 KS[0] = K & ~0x0303030300000000L;
314 for (int i = 1; i < 16; i++)
317 K = perm6464(K, PC2ROT[Rotates[i] - 1]);
319 KS[i] = K & ~0x0303030300000000L;
325 * Returns the DES encrypted code of the given word with the specified
328 private static long des_cipher(long in, int salt, int num_iter, long[] KS)
330 salt = to_six_bit(salt);
333 L &= 0x5555555555555555L;
334 R = (R & 0xaaaaaaaa00000000L) | ((R >> 1) & 0x0000000055555555L);
335 L = ((((L << 1) | (L << 32)) & 0xffffffff00000000L) | ((R | (R >> 32)) & 0x00000000ffffffffL));
337 L = perm3264((int) (L >> 32), IE3264);
338 R = perm3264((int) (L & 0xffffffff), IE3264);
340 while (--num_iter >= 0)
342 for (int loop_count = 0; loop_count < 8; loop_count++)
348 kp = KS[(loop_count << 1)];
349 k = ((R >> 32) ^ R) & salt & 0xffffffffL;
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)]);
360 kp = KS[(loop_count << 1) + 1];
361 k = ((L >> 32) ^ L) & salt & 0xffffffffL;
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)]);
377 L = ((((L >> 35) & 0x0f0f0f0fL) | (((L & 0xffffffff) << 1) & 0xf0f0f0f0L)) << 32 | (((R >> 35) & 0x0f0f0f0fL) | (((R & 0xffffffff) << 1) & 0xf0f0f0f0L)));
379 L = perm6464(L, CF6464);
385 * Initializes the given permutation table with the mapping table.
387 private static void init_perm(long[][] perm, byte[] p, int chars_out)
389 for (int k = 0; k < chars_out * 8; k++)
396 for (int j = 0; j < 16; j++)
398 int s = ((k & 0x07) + ((7 - (k >> 3)) << 3));
399 if ((j & l) != 0x00) perm[i][j] |= (1L << s);
405 * Encrypts String into crypt (Unix) code.
407 * @param key the key to be encrypted
408 * @param setting the salt to be used
409 * @return the encrypted String
411 public static String crypt(String key, String setting)
413 long constdatablock = 0L; /* encryption constant */
414 byte[] cryptresult = new byte[13]; /* encrypted result */
416 /* invalid parameters! */
417 if (key == null || setting == null) return "*"; // will NOT match under
418 // ANY circumstances!
420 int keylen = key.length();
422 for (int i = 0; i < 8; i++)
424 keyword = (keyword << 8) | ((i < keylen) ? 2 * key.charAt(i) : 0);
427 long[] KS = des_setkey(keyword);
430 for (int i = 2; --i >= 0;)
432 char c = (i < setting.length()) ? setting.charAt(i) : '.';
433 cryptresult[i] = (byte) c;
434 salt = (salt << 6) | (0x00ff & A64TOI[c]);
437 long rsltblock = des_cipher(constdatablock, salt, 25, KS);
439 cryptresult[12] = ITOA64[(((int) rsltblock) << 2) & 0x3f];
441 for (int i = 12; --i >= 2;)
443 cryptresult[i] = ITOA64[((int) rsltblock) & 0x3f];
447 return new String(cryptresult, 0, 13);
450 public static void main(String[] arg)
454 System.err.println("Usage - java org.eclipse.util.UnixCrypt <key> <salt>");
458 System.err.println("Crypt=" + crypt(arg[0], arg[1]));