001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License. You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied. See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 *
019 */
020
021 /*
022 * @(#)UnixCrypt.java 0.9 96/11/25
023 *
024 * Copyright (c) 1996 Aki Yoshida. All rights reserved.
025 *
026 * Permission to use, copy, modify and distribute this software
027 * for non-commercial or commercial purposes and without fee is
028 * hereby granted provided that this copyright notice appears in
029 * all copies.
030 */
031
032 /**
033 * Unix crypt(3C) utility
034 *
035 * @version 0.9, 11/25/96
036 * @author Aki Yoshida
037 */
038
039 /**
040 * modified April 2001
041 * by Iris Van den Broeke, Daniel Deville
042 */
043
044 package org.apache.directory.shared.ldap.util;
045
046 import org.apache.directory.shared.i18n.I18n;
047
048
049 /*
050 * @(#)UnixCrypt.java 0.9 96/11/25
051 *
052 * Copyright (c) 1996 Aki Yoshida. All rights reserved.
053 *
054 * Permission to use, copy, modify and distribute this software
055 * for non-commercial or commercial purposes and without fee is
056 * hereby granted provided that this copyright notice appears in
057 * all copies.
058 */
059
060 /**
061 * Unix crypt(3C) utility
062 *
063 * @version 0.9, 11/25/96
064 * @author Aki Yoshida
065 */
066
067 /**
068 * modified April 2001
069 * by Iris Van den Broeke, Daniel Deville
070 */
071
072
073 /* ------------------------------------------------------------ */
074 /** Unix Crypt.
075 * Implements the one way cryptography used by Unix systems for
076 * simple password protection.
077 * @version $Id: UnixCrypt.java,v 1.1 2005/10/05 14:09:14 janb Exp $
078 * @author Greg Wilkins (gregw)
079 */
080 public class UnixCrypt extends Object
081 {
082
083 /* (mostly) Standard DES Tables from Tom Truscott */
084 private static final byte[] IP = { /* initial permutation */
085 58, 50, 42, 34, 26, 18, 10, 2,
086 60, 52, 44, 36, 28, 20, 12, 4,
087 62, 54, 46, 38, 30, 22, 14, 6,
088 64, 56, 48, 40, 32, 24, 16, 8,
089 57, 49, 41, 33, 25, 17, 9, 1,
090 59, 51, 43, 35, 27, 19, 11, 3,
091 61, 53, 45, 37, 29, 21, 13, 5,
092 63, 55, 47, 39, 31, 23, 15, 7};
093
094 /* The final permutation is the inverse of IP - no table is necessary */
095 private static final byte[] ExpandTr = { /* expansion operation */
096 32, 1, 2, 3, 4, 5,
097 4, 5, 6, 7, 8, 9,
098 8, 9, 10, 11, 12, 13,
099 12, 13, 14, 15, 16, 17,
100 16, 17, 18, 19, 20, 21,
101 20, 21, 22, 23, 24, 25,
102 24, 25, 26, 27, 28, 29,
103 28, 29, 30, 31, 32, 1};
104
105 private static final byte[] PC1 = { /* permuted choice table 1 */
106 57, 49, 41, 33, 25, 17, 9,
107 1, 58, 50, 42, 34, 26, 18,
108 10, 2, 59, 51, 43, 35, 27,
109 19, 11, 3, 60, 52, 44, 36,
110
111 63, 55, 47, 39, 31, 23, 15,
112 7, 62, 54, 46, 38, 30, 22,
113 14, 6, 61, 53, 45, 37, 29,
114 21, 13, 5, 28, 20, 12, 4};
115
116 private static final byte[] Rotates = { /* PC1 rotation schedule */
117 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
118
119
120 private static final byte[] PC2 = { /* permuted choice table 2 */
121 9, 18, 14, 17, 11, 24, 1, 5,
122 22, 25, 3, 28, 15, 6, 21, 10,
123 35, 38, 23, 19, 12, 4, 26, 8,
124 43, 54, 16, 7, 27, 20, 13, 2,
125
126 0, 0, 41, 52, 31, 37, 47, 55,
127 0, 0, 30, 40, 51, 45, 33, 48,
128 0, 0, 44, 49, 39, 56, 34, 53,
129 0, 0, 46, 42, 50, 36, 29, 32};
130
131 private static final byte[][] S = { /* 48->32 bit substitution tables */
132 /* S[1] */
133 {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
134 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
135 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
136 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13},
137 /* S[2] */
138 {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
139 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
140 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
141 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9},
142 /* S[3] */
143 {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
144 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
145 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
146 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12},
147 /* S[4] */
148 {7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
149 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
150 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
151 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14},
152 /* S[5] */
153 {2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
154 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
155 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
156 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3},
157 /* S[6] */
158 {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
159 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
160 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
161 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13},
162 /* S[7] */
163 {4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
164 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
165 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
166 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12},
167 /* S[8] */
168 {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
169 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
170 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
171 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}};
172
173 private static final byte[] P32Tr = { /* 32-bit permutation function */
174 16, 7, 20, 21,
175 29, 12, 28, 17,
176 1, 15, 23, 26,
177 5, 18, 31, 10,
178 2, 8, 24, 14,
179 32, 27, 3, 9,
180 19, 13, 30, 6,
181 22, 11, 4, 25};
182
183 private static final byte[] CIFP = { /* compressed/interleaved permutation */
184 1, 2, 3, 4, 17, 18, 19, 20,
185 5, 6, 7, 8, 21, 22, 23, 24,
186 9, 10, 11, 12, 25, 26, 27, 28,
187 13, 14, 15, 16, 29, 30, 31, 32,
188
189 33, 34, 35, 36, 49, 50, 51, 52,
190 37, 38, 39, 40, 53, 54, 55, 56,
191 41, 42, 43, 44, 57, 58, 59, 60,
192 45, 46, 47, 48, 61, 62, 63, 64};
193
194 private static final byte[] ITOA64 = { /* 0..63 => ascii-64 */
195 (byte)'.',(byte) '/',(byte) '0',(byte) '1',(byte) '2',(byte) '3',(byte) '4',(byte) '5',
196 (byte)'6',(byte) '7',(byte) '8',(byte) '9',(byte) 'A',(byte) 'B',(byte) 'C',(byte) 'D',
197 (byte)'E',(byte) 'F',(byte) 'G',(byte) 'H',(byte) 'I',(byte) 'J',(byte) 'K',(byte) 'L',
198 (byte)'M',(byte) 'N',(byte) 'O',(byte) 'P',(byte) 'Q',(byte) 'R',(byte) 'S',(byte) 'T',
199 (byte)'U',(byte) 'V',(byte) 'W',(byte) 'X',(byte) 'Y',(byte) 'Z',(byte) 'a',(byte) 'b',
200 (byte)'c',(byte) 'd',(byte) 'e',(byte) 'f',(byte) 'g',(byte) 'h',(byte) 'i',(byte) 'j',
201 (byte)'k',(byte) 'l',(byte) 'm',(byte) 'n',(byte) 'o',(byte) 'p',(byte) 'q',(byte) 'r',
202 (byte)'s',(byte) 't',(byte) 'u',(byte) 'v',(byte) 'w',(byte) 'x',(byte) 'y',(byte) 'z'};
203
204 /* ===== Tables that are initialized at run time ==================== */
205
206 private static byte[] A64TOI = new byte[128]; /* ascii-64 => 0..63 */
207
208 /* Initial key schedule permutation */
209 private static long[][] PC1ROT = new long[16][16];
210
211 /* Subsequent key schedule rotation permutations */
212 private static long[][][] PC2ROT = new long[2][16][16];
213
214 /* Initial permutation/expansion table */
215 private static long[][] IE3264 = new long[8][16];
216
217 /* Table that combines the S, P, and E operations. */
218 private static long[][] SPE = new long[8][64];
219
220 /* compressed/interleaved => final permutation table */
221 private static long[][] CF6464 = new long[16][16];
222
223
224 /* ==================================== */
225
226 static {
227 byte[] perm = new byte[64];
228 byte[] temp = new byte[64];
229
230 // inverse table.
231 for (int i=0; i<64; i++) A64TOI[ITOA64[i]] = (byte)i;
232
233 // PC1ROT - bit reverse, then PC1, then Rotate, then PC2
234 for (int i=0; i<64; i++) perm[i] = (byte)0;
235 for (int i=0; i<64; i++) {
236 int k;
237 if ((k = PC2[i]) == 0) continue;
238 k += Rotates[0]-1;
239 if ((k%28) < Rotates[0]) k -= 28;
240 k = PC1[k];
241 if (k > 0) {
242 k--;
243 k = (k|0x07) - (k&0x07);
244 k++;
245 }
246 perm[i] = (byte)k;
247 }
248 init_perm(PC1ROT, perm, 8);
249
250 // PC2ROT - PC2 inverse, then Rotate, then PC2
251 for (int j=0; j<2; j++) {
252 int k;
253 for (int i=0; i<64; i++) perm[i] = temp[i] = 0;
254 for (int i=0; i<64; i++) {
255 if ((k = PC2[i]) == 0) continue;
256 temp[k-1] = (byte)(i+1);
257 }
258 for (int i=0; i<64; i++) {
259 if ((k = PC2[i]) == 0) continue;
260 k += j;
261 if ((k%28) <= j) k -= 28;
262 perm[i] = temp[k];
263 }
264
265 init_perm(PC2ROT[j], perm, 8);
266 }
267
268 // Bit reverse, intial permupation, expantion
269 for (int i=0; i<8; i++) {
270 for (int j=0; j<8; j++) {
271 int k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1];
272 if (k > 32) k -= 32;
273 else if (k > 0) k--;
274 if (k > 0) {
275 k--;
276 k = (k|0x07) - (k&0x07);
277 k++;
278 }
279 perm[i*8+j] = (byte)k;
280 }
281 }
282
283 init_perm(IE3264, perm, 8);
284
285 // Compression, final permutation, bit reverse
286 for (int i=0; i<64; i++) {
287 int k = IP[CIFP[i]-1];
288 if (k > 0) {
289 k--;
290 k = (k|0x07) - (k&0x07);
291 k++;
292 }
293 perm[k-1] = (byte)(i+1);
294 }
295
296 init_perm(CF6464, perm, 8);
297
298 // SPE table
299 for (int i=0; i<48; i++)
300 perm[i] = P32Tr[ExpandTr[i]-1];
301 for (int t=0; t<8; t++) {
302 for (int j=0; j<64; j++) {
303 int k = (((j >> 0) & 0x01) << 5) | (((j >> 1) & 0x01) << 3) |
304 (((j >> 2) & 0x01) << 2) | (((j >> 3) & 0x01) << 1) |
305 (((j >> 4) & 0x01) << 0) | (((j >> 5) & 0x01) << 4);
306 k = S[t][k];
307 k = (((k >> 3) & 0x01) << 0) | (((k >> 2) & 0x01) << 1) |
308 (((k >> 1) & 0x01) << 2) | (((k >> 0) & 0x01) << 3);
309 for (int i=0; i<32; i++) temp[i] = 0;
310 for (int i=0; i<4; i++) temp[4*t+i] = (byte)((k >> i) & 0x01);
311 long kk = 0;
312 for (int i=24; --i>=0; ) kk = ((kk<<1) |
313 ((long)temp[perm[i]-1])<<32 |
314 (temp[perm[i+24]-1]));
315
316 SPE[t][j] = to_six_bit(kk);
317 }
318 }
319 }
320
321 /**
322 * You can't call the constructer.
323 */
324 private UnixCrypt() { }
325
326 /**
327 * Returns the transposed and split code of a 24-bit code
328 * into a 4-byte code, each having 6 bits.
329 */
330 private static int to_six_bit(int num) {
331 return (((num << 26) & 0xfc000000) | ((num << 12) & 0xfc0000) |
332 ((num >> 2) & 0xfc00) | ((num >> 16) & 0xfc));
333 }
334
335 /**
336 * Returns the transposed and split code of two 24-bit code
337 * into two 4-byte code, each having 6 bits.
338 */
339 private static long to_six_bit(long num) {
340 return (((num << 26) & 0xfc000000fc000000L) | ((num << 12) & 0xfc000000fc0000L) |
341 ((num >> 2) & 0xfc000000fc00L) | ((num >> 16) & 0xfc000000fcL));
342 }
343
344 /**
345 * Returns the permutation of the given 64-bit code with
346 * the specified permutataion table.
347 */
348 private static long perm6464(long c, long[][]p) {
349 long out = 0L;
350 for (int i=8; --i>=0; ) {
351 int t = (int)(0x00ff & c);
352 c >>= 8;
353 long tp = p[i<<1][t&0x0f];
354 out |= tp;
355 tp = p[(i<<1)+1][t>>4];
356 out |= tp;
357 }
358 return out;
359 }
360
361 /**
362 * Returns the permutation of the given 32-bit code with
363 * the specified permutataion table.
364 */
365 private static long perm3264(int c, long[][]p) {
366 long out = 0L;
367 for (int i=4; --i>=0; ) {
368 int t = (0x00ff & c);
369 c >>= 8;
370 long tp = p[i<<1][t&0x0f];
371 out |= tp;
372 tp = p[(i<<1)+1][t>>4];
373 out |= tp;
374 }
375 return out;
376 }
377
378 /**
379 * Returns the key schedule for the given key.
380 */
381 private static long[] des_setkey(long keyword) {
382 long K = perm6464(keyword, PC1ROT);
383 long[] KS = new long[16];
384 KS[0] = K&~0x0303030300000000L;
385
386 for (int i=1; i<16; i++) {
387 KS[i] = K;
388 K = perm6464(K, PC2ROT[Rotates[i]-1]);
389
390 KS[i] = K&~0x0303030300000000L;
391 }
392 return KS;
393 }
394
395 /**
396 * Returns the DES encrypted code of the given word with the specified
397 * environment.
398 */
399 private static long des_cipher(long in, int salt, int num_iter, long[] KS) {
400 salt = to_six_bit(salt);
401 long L = in;
402 long R = L;
403 L &= 0x5555555555555555L;
404 R = (R & 0xaaaaaaaa00000000L) | ((R >> 1) & 0x0000000055555555L);
405 L = ((((L << 1) | (L << 32)) & 0xffffffff00000000L) |
406 ((R | (R >> 32)) & 0x00000000ffffffffL));
407
408 L = perm3264((int)(L>>32), IE3264);
409 R = perm3264((int)(L&0xffffffff), IE3264);
410
411 while (--num_iter >= 0) {
412 for (int loop_count=0; loop_count<8; loop_count++) {
413 long kp;
414 long B;
415 long k;
416
417 kp = KS[(loop_count<<1)];
418 k = ((R>>32) ^ R) & salt & 0xffffffffL;
419 k |= (k<<32);
420 B = (k ^ R ^ kp);
421
422 L ^= (SPE[0][(int)((B>>58)&0x3f)] ^ SPE[1][(int)((B>>50)&0x3f)] ^
423 SPE[2][(int)((B>>42)&0x3f)] ^ SPE[3][(int)((B>>34)&0x3f)] ^
424 SPE[4][(int)((B>>26)&0x3f)] ^ SPE[5][(int)((B>>18)&0x3f)] ^
425 SPE[6][(int)((B>>10)&0x3f)] ^ SPE[7][(int)((B>>2)&0x3f)]);
426
427 kp = KS[(loop_count<<1)+1];
428 k = ((L>>32) ^ L) & salt & 0xffffffffL;
429 k |= (k<<32);
430 B = (k ^ L ^ kp);
431
432 R ^= (SPE[0][(int)((B>>58)&0x3f)] ^ SPE[1][(int)((B>>50)&0x3f)] ^
433 SPE[2][(int)((B>>42)&0x3f)] ^ SPE[3][(int)((B>>34)&0x3f)] ^
434 SPE[4][(int)((B>>26)&0x3f)] ^ SPE[5][(int)((B>>18)&0x3f)] ^
435 SPE[6][(int)((B>>10)&0x3f)] ^ SPE[7][(int)((B>>2)&0x3f)]);
436 }
437 // swap L and R
438 L ^= R;
439 R ^= L;
440 L ^= R;
441 }
442 L = ((((L>>35) & 0x0f0f0f0fL) | (((L&0xffffffff)<<1) & 0xf0f0f0f0L))<<32 |
443 (((R>>35) & 0x0f0f0f0fL) | (((R&0xffffffff)<<1) & 0xf0f0f0f0L)));
444
445 L = perm6464(L, CF6464);
446
447 return L;
448 }
449
450 /**
451 * Initializes the given permutation table with the mapping table.
452 */
453 private static void init_perm(long[][] perm, byte[] p,int chars_out) {
454 for (int k=0; k<chars_out*8; k++) {
455
456 int l = p[k] - 1;
457 if (l < 0) continue;
458 int i = l>>2;
459 l = 1<<(l&0x03);
460 for (int j=0; j<16; j++) {
461 int s = ((k&0x07)+((7-(k>>3))<<3));
462 if ((j & l) != 0x00) perm[i][j] |= (1L<<s);
463 }
464 }
465 }
466
467 /**
468 * Encrypts String into crypt (Unix) code.
469 * @param key the key to be encrypted
470 * @param setting the salt to be used
471 * @return the encrypted String
472 */
473 public static String crypt(String key, String setting)
474 {
475 long constdatablock = 0L; /* encryption constant */
476 byte[] cryptresult = new byte[13]; /* encrypted result */
477 long keyword = 0L;
478 /* invalid parameters! */
479 if(key==null||setting==null)
480 return "*"; // will NOT match under ANY circumstances!
481
482 int keylen = key.length();
483
484 for (int i=0; i<8 ; i++) {
485 keyword = (keyword << 8) | ((i < keylen)? 2*key.charAt(i): 0);
486 }
487
488 long[] KS = des_setkey(keyword);
489
490 int salt = 0;
491 for (int i=2; --i>=0;) {
492 char c = (i < setting.length())? setting.charAt(i): '.';
493 cryptresult[i] = (byte)c;
494 salt = (salt<<6) | (0x00ff&A64TOI[c]);
495 }
496
497 long rsltblock = des_cipher(constdatablock, salt, 25, KS);
498
499 cryptresult[12] = ITOA64[(((int)rsltblock)<<2)&0x3f];
500 rsltblock >>= 4;
501 for (int i=12; --i>=2; ) {
502 cryptresult[i] = ITOA64[((int)rsltblock)&0x3f];
503 rsltblock >>= 6;
504 }
505
506 return new String(cryptresult, 0x00, 0, 13);
507 }
508
509 public static void main(String[] arg)
510 {
511 if (arg.length!=2)
512 {
513 System.err.println( I18n.err( I18n.ERR_04439 ) );
514 System.exit(1);
515 }
516
517 System.err.println( I18n.err( I18n.ERR_04440, crypt(arg[0],arg[1]) ) );
518 }
519
520 }