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     }