Ruby 1.9.2p136(2010-12-25revision30365)

- Main Page
- Modules
- Data Structures
- Files

- File List
- Globals

# missing/crypt.c

Go to the documentation of this file.

    00001 /*
    00002  * Copyright (c) 1989, 1993
    00003  *      The Regents of the University of California.  All rights reserved.
    00004  *
    00005  * This code is derived from software contributed to Berkeley by
    00006  * Tom Truscott.
    00007  *
    00008  * Redistribution and use in source and binary forms, with or without
    00009  * modification, are permitted provided that the following conditions
    00010  * are met:
    00011  * 1. Redistributions of source code must retain the above copyright
    00012  *    notice, this list of conditions and the following disclaimer.
    00013  * 2. Redistributions in binary form must reproduce the above copyright
    00014  *    notice, this list of conditions and the following disclaimer in the
    00015  *    documentation and/or other materials provided with the distribution.
    00016  * 3. Neither the name of the University nor the names of its contributors
    00017  *    may be used to endorse or promote products derived from this software
    00018  *    without specific prior written permission.
    00019  *
    00020  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
    00021  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    00022  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    00023  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
    00024  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
    00025  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
    00026  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
    00027  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
    00028  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
    00029  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    00030  * SUCH DAMAGE.
    00031  */
    00032
    00033 #if defined(LIBC_SCCS) && !defined(lint)
    00034 static char sccsid[] = "@(#)crypt.c     8.1 (Berkeley) 6/4/93";
    00035 #endif /* LIBC_SCCS and not lint */
    00036
    00037 #ifdef HAVE_UNISTD_H
    00038 #include <unistd.h>
    00039 #endif
    00040 #include <limits.h>
    00041 #ifdef HAVE_PWD_H
    00042 #include <pwd.h>
    00043 #endif
    00044 #include <stdio.h>
    00045 #ifndef _PASSWORD_EFMT1
    00046 #define _PASSWORD_EFMT1 '_'
    00047 #endif
    00048
    00049 /*
    00050  * UNIX password, and DES, encryption.
    00051  * By Tom Truscott, trt@rti.rti.org,
    00052  * from algorithms by Robert W. Baldwin and James Gillogly.
    00053  *
    00054  * References:
    00055  * "Mathematical Cryptology for Computer Scientists and Mathematicians,"
    00056  * by Wayne Patterson, 1987, ISBN 0-8476-7438-X.
    00057  *
    00058  * "Password Security: A Case History," R. Morris and Ken Thompson,
    00059  * Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979.
    00060  *
    00061  * "DES will be Totally Insecure within Ten Years," M.E. Hellman,
    00062  * IEEE Spectrum, vol. 16, pp. 32-39, July 1979.
    00063  */
    00064
    00065 /* =====  Configuration ==================== */
    00066
    00067 /*
    00068  * define "MUST_ALIGN" if your compiler cannot load/store
    00069  * long integers at arbitrary (e.g. odd) memory locations.
    00070  * (Either that or never pass unaligned addresses to des_cipher!)
    00071  */
    00072 #if !defined(vax)
    00073 #define MUST_ALIGN
    00074 #endif
    00075
    00076 #ifdef CHAR_BITS
    00077 #if CHAR_BITS != 8
    00078         #error C_block structure assumes 8 bit characters
    00079 #endif
    00080 #endif
    00081
    00082 /*
    00083  * define "LONG_IS_32_BITS" only if sizeof(long)==4.
    00084  * This avoids use of bit fields (your compiler may be sloppy with them).
    00085  */
    00086 #if !defined(cray)
    00087 #define LONG_IS_32_BITS
    00088 #endif
    00089
    00090 /*
    00091  * define "B64" to be the declaration for a 64 bit integer.
    00092  * XXX this feature is currently unused, see "endian" comment below.
    00093  */
    00094 #if defined(cray)
    00095 #define B64     long
    00096 #endif
    00097 #if defined(convex)
    00098 #define B64     long long
    00099 #endif
    00100
    00101 /*
    00102  * define "LARGEDATA" to get faster permutations, by using about 72 kilobytes
    00103  * of lookup tables.  This speeds up des_setkey() and des_cipher(), but has
    00104  * little effect on crypt().
    00105  */
    00106 #if defined(notdef)
    00107 #define LARGEDATA
    00108 #endif
    00109
    00110 int des_setkey(), des_cipher();
    00111
    00112 /* compile with "-DSTATIC=int" when profiling */
    00113 #ifndef STATIC
    00114 #define STATIC  static
    00115 #endif
    00116 STATIC void init_des(), init_perm(), permute();
    00117 #ifdef DEBUG
    00118 STATIC void prtab();
    00119 #endif
    00120
    00121 /* ==================================== */
    00122
    00123 /*
    00124  * Cipher-block representation (Bob Baldwin):
    00125  *
    00126  * DES operates on groups of 64 bits, numbered 1..64 (sigh).  One
    00127  * representation is to store one bit per byte in an array of bytes.  Bit N of
    00128  * the NBS spec is stored as the LSB of the Nth byte (index N-1) in the array.
    00129  * Another representation stores the 64 bits in 8 bytes, with bits 1..8 in the
    00130  * first byte, 9..16 in the second, and so on.  The DES spec apparently has
    00131  * bit 1 in the MSB of the first byte, but that is particularly noxious so we
    00132  * bit-reverse each byte so that bit 1 is the LSB of the first byte, bit 8 is
    00133  * the MSB of the first byte.  Specifically, the 64-bit input data and key are
    00134  * converted to LSB format, and the output 64-bit block is converted back into
    00135  * MSB format.
    00136  *
    00137  * DES operates internally on groups of 32 bits which are expanded to 48 bits
    00138  * by permutation E and shrunk back to 32 bits by the S boxes.  To speed up
    00139  * the computation, the expansion is applied only once, the expanded
    00140  * representation is maintained during the encryption, and a compression
    00141  * permutation is applied only at the end.  To speed up the S-box lookups,
    00142  * the 48 bits are maintained as eight 6 bit groups, one per byte, which
    00143  * directly feed the eight S-boxes.  Within each byte, the 6 bits are the
    00144  * most significant ones.  The low two bits of each byte are zero.  (Thus,
    00145  * bit 1 of the 48 bit E expansion is stored as the "4"-valued bit of the
    00146  * first byte in the eight byte representation, bit 2 of the 48 bit value is
    00147  * the "8"-valued bit, and so on.)  In fact, a combined "SPE"-box lookup is
    00148  * used, in which the output is the 64 bit result of an S-box lookup which
    00149  * has been permuted by P and expanded by E, and is ready for use in the next
    00150  * iteration.  Two 32-bit wide tables, SPE[0] and SPE[1], are used for this
    00151  * lookup.  Since each byte in the 48 bit path is a multiple of four, indexed
    00152  * lookup of SPE[0] and SPE[1] is simple and fast.  The key schedule and
    00153  * "salt" are also converted to this 8*(6+2) format.  The SPE table size is
    00154  * 8*64*8 = 4K bytes.
    00155  *
    00156  * To speed up bit-parallel operations (such as XOR), the 8 byte
    00157  * representation is "union"ed with 32 bit values "i0" and "i1", and, on
    00158  * machines which support it, a 64 bit value "b64".  This data structure,
    00159  * "C_block", has two problems.  First, alignment restrictions must be
    00160  * honored.  Second, the byte-order (e.g. little-endian or big-endian) of
    00161  * the architecture becomes visible.
    00162  *
    00163  * The byte-order problem is unfortunate, since on the one hand it is good
    00164  * to have a machine-independent C_block representation (bits 1..8 in the
    00165  * first byte, etc.), and on the other hand it is good for the LSB of the
    00166  * first byte to be the LSB of i0.  We cannot have both these things, so we
    00167  * currently use the "little-endian" representation and avoid any multi-byte
    00168  * operations that depend on byte order.  This largely precludes use of the
    00169  * 64-bit datatype since the relative order of i0 and i1 are unknown.  It
    00170  * also inhibits grouping the SPE table to look up 12 bits at a time.  (The
    00171  * 12 bits can be stored in a 16-bit field with 3 low-order zeroes and 1
    00172  * high-order zero, providing fast indexing into a 64-bit wide SPE.)  On the
    00173  * other hand, 64-bit datatypes are currently rare, and a 12-bit SPE lookup
    00174  * requires a 128 kilobyte table, so perhaps this is not a big loss.
    00175  *
    00176  * Permutation representation (Jim Gillogly):
    00177  *
    00178  * A transformation is defined by its effect on each of the 8 bytes of the
    00179  * 64-bit input.  For each byte we give a 64-bit output that has the bits in
    00180  * the input distributed appropriately.  The transformation is then the OR
    00181  * of the 8 sets of 64-bits.  This uses 8*256*8 = 16K bytes of storage for
    00182  * each transformation.  Unless LARGEDATA is defined, however, a more compact
    00183  * table is used which looks up 16 4-bit "chunks" rather than 8 8-bit chunks.
    00184  * The smaller table uses 16*16*8 = 2K bytes for each transformation.  This
    00185  * is slower but tolerable, particularly for password encryption in which
    00186  * the SPE transformation is iterated many times.  The small tables total 9K
    00187  * bytes, the large tables total 72K bytes.
    00188  *
    00189  * The transformations used are:
    00190  * IE3264: MSB->LSB conversion, initial permutation, and expansion.
    00191  *      This is done by collecting the 32 even-numbered bits and applying
    00192  *      a 32->64 bit transformation, and then collecting the 32 odd-numbered
    00193  *      bits and applying the same transformation.  Since there are only
    00194  *      32 input bits, the IE3264 transformation table is half the size of
    00195  *      the usual table.
    00196  * CF6464: Compression, final permutation, and LSB->MSB conversion.
    00197  *      This is done by two trivial 48->32 bit compressions to obtain
    00198  *      a 64-bit block (the bit numbering is given in the "CIFP" table)
    00199  *      followed by a 64->64 bit "cleanup" transformation.  (It would
    00200  *      be possible to group the bits in the 64-bit block so that 2
    00201  *      identical 32->32 bit transformations could be used instead,
    00202  *      saving a factor of 4 in space and possibly 2 in time, but
    00203  *      byte-ordering and other complications rear their ugly head.
    00204  *      Similar opportunities/problems arise in the key schedule
    00205  *      transforms.)
    00206  * PC1ROT: MSB->LSB, PC1 permutation, rotate, and PC2 permutation.
    00207  *      This admittedly baroque 64->64 bit transformation is used to
    00208  *      produce the first code (in 8*(6+2) format) of the key schedule.
    00209  * PC2ROT[0]: Inverse PC2 permutation, rotate, and PC2 permutation.
    00210  *      It would be possible to define 15 more transformations, each
    00211  *      with a different rotation, to generate the entire key schedule.
    00212  *      To save space, however, we instead permute each code into the
    00213  *      next by using a transformation that "undoes" the PC2 permutation,
    00214  *      rotates the code, and then applies PC2.  Unfortunately, PC2
    00215  *      transforms 56 bits into 48 bits, dropping 8 bits, so PC2 is not
    00216  *      invertible.  We get around that problem by using a modified PC2
    00217  *      which retains the 8 otherwise-lost bits in the unused low-order
    00218  *      bits of each byte.  The low-order bits are cleared when the
    00219  *      codes are stored into the key schedule.
    00220  * PC2ROT[1]: Same as PC2ROT[0], but with two rotations.
    00221  *      This is faster than applying PC2ROT[0] twice,
    00222  *
    00223  * The Bell Labs "salt" (Bob Baldwin):
    00224  *
    00225  * The salting is a simple permutation applied to the 48-bit result of E.
    00226  * Specifically, if bit i (1 <= i <= 24) of the salt is set then bits i and
    00227  * i+24 of the result are swapped.  The salt is thus a 24 bit number, with
    00228  * 16777216 possible values.  (The original salt was 12 bits and could not
    00229  * swap bits 13..24 with 36..48.)
    00230  *
    00231  * It is possible, but ugly, to warp the SPE table to account for the salt
    00232  * permutation.  Fortunately, the conditional bit swapping requires only
    00233  * about four machine instructions and can be done on-the-fly with about an
    00234  * 8% performance penalty.
    00235  */
    00236
    00237 typedef union {
    00238         unsigned char b[8];
    00239         struct {
    00240 #if defined(LONG_IS_32_BITS)
    00241                 /* long is often faster than a 32-bit bit field */
    00242                 long    i0;
    00243                 long    i1;
    00244 #else
    00245                 long    i0: 32;
    00246                 long    i1: 32;
    00247 #endif
    00248         } b32;
    00249 #if defined(B64)
    00250         B64     b64;
    00251 #endif
    00252 } C_block;
    00253
    00254 /*
    00255  * Convert twenty-four-bit long in host-order
    00256  * to six bits (and 2 low-order zeroes) per char little-endian format.
    00257  */
    00258 #define TO_SIX_BIT(rslt, src) {                         \
    00259                 C_block cvt;                            \
    00260                 cvt.b[0] = (unsigned char)src; src >>= 6; \
    00261                 cvt.b[1] = (unsigned char)src; src >>= 6; \
    00262                 cvt.b[2] = (unsigned char)src; src >>= 6; \
    00263                 cvt.b[3] = (unsigned char)src;          \
    00264                 rslt = (cvt.b32.i0 & 0x3f3f3f3fL) << 2; \
    00265         }
    00266
    00267 /*
    00268  * These macros may someday permit efficient use of 64-bit integers.
    00269  */
    00270 #define ZERO(d,d0,d1)                   d0 = 0, d1 = 0
    00271 #define LOAD(d,d0,d1,bl)                d0 = (bl).b32.i0, d1 = (bl).b32.i1
    00272 #define LOADREG(d,d0,d1,s,s0,s1)        d0 = s0, d1 = s1
    00273 #define OR(d,d0,d1,bl)                  d0 |= (bl).b32.i0, d1 |= (bl).b32.i1
    00274 #define STORE(s,s0,s1,bl)               (bl).b32.i0 = s0, (bl).b32.i1 = s1
    00275 #define DCL_BLOCK(d,d0,d1)              long d0, d1
    00276
    00277 #if defined(LARGEDATA)
    00278         /* Waste memory like crazy.  Also, do permutations in line */
    00279 #define LGCHUNKBITS     3
    00280 #define CHUNKBITS       (1<<LGCHUNKBITS)
    00281 #define PERM6464(d,d0,d1,cpp,p)                         \
    00282         LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]);             \
    00283         OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]);              \
    00284         OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]);              \
    00285         OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]);              \
    00286         OR (d,d0,d1,(p)[(4<<CHUNKBITS)+(cpp)[4]]);              \
    00287         OR (d,d0,d1,(p)[(5<<CHUNKBITS)+(cpp)[5]]);              \
    00288         OR (d,d0,d1,(p)[(6<<CHUNKBITS)+(cpp)[6]]);              \
    00289         OR (d,d0,d1,(p)[(7<<CHUNKBITS)+(cpp)[7]]);
    00290 #define PERM3264(d,d0,d1,cpp,p)                         \
    00291         LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]);             \
    00292         OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]);              \
    00293         OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]);              \
    00294         OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]);
    00295 #else
    00296         /* "small data" */
    00297 #define LGCHUNKBITS     2
    00298 #define CHUNKBITS       (1<<LGCHUNKBITS)
    00299 #define PERM6464(d,d0,d1,cpp,p)                         \
    00300         { C_block tblk; permute(cpp,&tblk,p,8); LOAD (d,d0,d1,tblk); }
    00301 #define PERM3264(d,d0,d1,cpp,p)                         \
    00302         { C_block tblk; permute(cpp,&tblk,p,4); LOAD (d,d0,d1,tblk); }
    00303
    00304 STATIC void
    00305 permute(cp, out, p, chars_in)
    00306         unsigned char *cp;
    00307         C_block *out;
    00308         register C_block *p;
    00309         int chars_in;
    00310 {
    00311         register DCL_BLOCK(D,D0,D1);
    00312         register C_block *tp;
    00313         register int t;
    00314
    00315         ZERO(D,D0,D1);
    00316         do {
    00317                 t = *cp++;
    00318                 tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
    00319                 tp = &p[t>>4];  OR(D,D0,D1,*tp); p += (1<<CHUNKBITS);
    00320         } while (--chars_in > 0);
    00321         STORE(D,D0,D1,*out);
    00322 }
    00323 #endif /* LARGEDATA */
    00324
    00325
    00326 /* =====  (mostly) Standard DES Tables ==================== */
    00327
    00328 static unsigned char IP[] = {           /* initial permutation */
    00329         58, 50, 42, 34, 26, 18, 10,  2,
    00330         60, 52, 44, 36, 28, 20, 12,  4,
    00331         62, 54, 46, 38, 30, 22, 14,  6,
    00332         64, 56, 48, 40, 32, 24, 16,  8,
    00333         57, 49, 41, 33, 25, 17,  9,  1,
    00334         59, 51, 43, 35, 27, 19, 11,  3,
    00335         61, 53, 45, 37, 29, 21, 13,  5,
    00336         63, 55, 47, 39, 31, 23, 15,  7,
    00337 };
    00338
    00339 /* The final permutation is the inverse of IP - no table is necessary */
    00340
    00341 static unsigned char ExpandTr[] = {     /* expansion operation */
    00342         32,  1,  2,  3,  4,  5,
    00343          4,  5,  6,  7,  8,  9,
    00344          8,  9, 10, 11, 12, 13,
    00345         12, 13, 14, 15, 16, 17,
    00346         16, 17, 18, 19, 20, 21,
    00347         20, 21, 22, 23, 24, 25,
    00348         24, 25, 26, 27, 28, 29,
    00349         28, 29, 30, 31, 32,  1,
    00350 };
    00351
    00352 static unsigned char PC1[] = {          /* permuted choice table 1 */
    00353         57, 49, 41, 33, 25, 17,  9,
    00354          1, 58, 50, 42, 34, 26, 18,
    00355         10,  2, 59, 51, 43, 35, 27,
    00356         19, 11,  3, 60, 52, 44, 36,
    00357
    00358         63, 55, 47, 39, 31, 23, 15,
    00359          7, 62, 54, 46, 38, 30, 22,
    00360         14,  6, 61, 53, 45, 37, 29,
    00361         21, 13,  5, 28, 20, 12,  4,
    00362 };
    00363
    00364 static unsigned char Rotates[] = {      /* PC1 rotation schedule */
    00365         1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1,
    00366 };
    00367
    00368 /* note: each "row" of PC2 is left-padded with bits that make it invertible */
    00369 static unsigned char PC2[] = {          /* permuted choice table 2 */
    00370          9, 18,    14, 17, 11, 24,  1,  5,
    00371         22, 25,     3, 28, 15,  6, 21, 10,
    00372         35, 38,    23, 19, 12,  4, 26,  8,
    00373         43, 54,    16,  7, 27, 20, 13,  2,
    00374
    00375          0,  0,    41, 52, 31, 37, 47, 55,
    00376          0,  0,    30, 40, 51, 45, 33, 48,
    00377          0,  0,    44, 49, 39, 56, 34, 53,
    00378          0,  0,    46, 42, 50, 36, 29, 32,
    00379 };
    00380
    00381 static unsigned char S[8][64] = {       /* 48->32 bit substitution tables */
    00382     {
    00383                                         /* S[1]                 */
    00384         14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
    00385          0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
    00386          4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
    00387         15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13,
    00388     },
    00389     {
    00390                                         /* S[2]                 */
    00391         15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
    00392          3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
    00393          0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
    00394         13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9,
    00395     },
    00396     {
    00397                                         /* S[3]                 */
    00398         10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
    00399         13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
    00400         13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
    00401          1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12,
    00402     },
    00403     {
    00404                                         /* S[4]                 */
    00405          7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
    00406         13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
    00407         10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
    00408          3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14,
    00409     },
    00410     {
    00411                                         /* S[5]                 */
    00412          2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
    00413         14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
    00414          4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
    00415         11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3,
    00416     },
    00417     {
    00418                                         /* S[6]                 */
    00419         12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
    00420         10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
    00421          9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
    00422          4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13,
    00423     },
    00424     {
    00425                                         /* S[7]                 */
    00426          4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
    00427         13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
    00428          1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
    00429          6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12,
    00430     },
    00431     {
    00432                                         /* S[8]                 */
    00433         13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
    00434          1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
    00435          7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
    00436          2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11,
    00437     },
    00438 };
    00439
    00440 static unsigned char P32Tr[] = {        /* 32-bit permutation function */
    00441         16,  7, 20, 21,
    00442         29, 12, 28, 17,
    00443          1, 15, 23, 26,
    00444          5, 18, 31, 10,
    00445          2,  8, 24, 14,
    00446         32, 27,  3,  9,
    00447         19, 13, 30,  6,
    00448         22, 11,  4, 25,
    00449 };
    00450
    00451 static unsigned char CIFP[] = {         /* compressed/interleaved permutation */
    00452          1,  2,  3,  4,   17, 18, 19, 20,
    00453          5,  6,  7,  8,   21, 22, 23, 24,
    00454          9, 10, 11, 12,   25, 26, 27, 28,
    00455         13, 14, 15, 16,   29, 30, 31, 32,
    00456
    00457         33, 34, 35, 36,   49, 50, 51, 52,
    00458         37, 38, 39, 40,   53, 54, 55, 56,
    00459         41, 42, 43, 44,   57, 58, 59, 60,
    00460         45, 46, 47, 48,   61, 62, 63, 64,
    00461 };
    00462
    00463 static unsigned char itoa64[] =         /* 0..63 => ascii-64 */
    00464         "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    00465
    00466
    00467 /* =====  Tables that are initialized at run time  ==================== */
    00468
    00469
    00470 static unsigned char a64toi[128];       /* ascii-64 => 0..63 */
    00471
    00472 /* Initial key schedule permutation */
    00473 static C_block  PC1ROT[64/CHUNKBITS][1<<CHUNKBITS];
    00474
    00475 /* Subsequent key schedule rotation permutations */
    00476 static C_block  PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS];
    00477
    00478 /* Initial permutation/expansion table */
    00479 static C_block  IE3264[32/CHUNKBITS][1<<CHUNKBITS];
    00480
    00481 /* Table that combines the S, P, and E operations.  */
    00482 static long SPE[2][8][64];
    00483
    00484 /* compressed/interleaved => final permutation table */
    00485 static C_block  CF6464[64/CHUNKBITS][1<<CHUNKBITS];
    00486
    00487
    00488 /* ==================================== */
    00489
    00490
    00491 static C_block  constdatablock;                 /* encryption constant */
    00492 static char     cryptresult[1+4+4+11+1];        /* encrypted result */
    00493
    00494 /*
    00495  * Return a pointer to static data consisting of the "setting"
    00496  * followed by an encryption produced by the "key" and "setting".
    00497  */
    00498 char *
    00499 crypt(key, setting)
    00500         register const char *key;
    00501         register const char *setting;
    00502 {
    00503         register char *encp;
    00504         register long i;
    00505         register int t;
    00506         long salt;
    00507         int num_iter, salt_size;
    00508         C_block keyblock, rsltblock;
    00509
    00510         for (i = 0; i < 8; i++) {
    00511                 if ((t = 2*(unsigned char)(*key)) != 0)
    00512                         key++;
    00513                 keyblock.b[i] = t;
    00514         }
    00515         if (des_setkey((char *)keyblock.b))     /* also initializes "a64toi" */
    00516                 return (NULL);
    00517
    00518         encp = &cryptresult[0];
    00519         switch (*setting) {
    00520         case _PASSWORD_EFMT1:
    00521                 /*
    00522                  * Involve the rest of the password 8 characters at a time.
    00523                  */
    00524                 while (*key) {
    00525                         if (des_cipher((char *)&keyblock,
    00526                             (char *)&keyblock, 0L, 1))
    00527                                 return (NULL);
    00528                         for (i = 0; i < 8; i++) {
    00529                                 if ((t = 2*(unsigned char)(*key)) != 0)
    00530                                         key++;
    00531                                 keyblock.b[i] ^= t;
    00532                         }
    00533                         if (des_setkey((char *)keyblock.b))
    00534                                 return (NULL);
    00535                 }
    00536
    00537                 *encp++ = *setting++;
    00538
    00539                 /* get iteration count */
    00540                 num_iter = 0;
    00541                 for (i = 4; --i >= 0; ) {
    00542                         if ((t = (unsigned char)setting[i]) == '\0')
    00543                                 t = '.';
    00544                         encp[i] = t;
    00545                         num_iter = (num_iter<<6) | a64toi[t];
    00546                 }
    00547                 setting += 4;
    00548                 encp += 4;
    00549                 salt_size = 4;
    00550                 break;
    00551         default:
    00552                 num_iter = 25;
    00553                 salt_size = 2;
    00554         }
    00555
    00556         salt = 0;
    00557         for (i = salt_size; --i >= 0; ) {
    00558                 if ((t = (unsigned char)setting[i]) == '\0')
    00559                         t = '.';
    00560                 encp[i] = t;
    00561                 salt = (salt<<6) | a64toi[t];
    00562         }
    00563         encp += salt_size;
    00564         if (des_cipher((char *)&constdatablock, (char *)&rsltblock,
    00565             salt, num_iter))
    00566                 return (NULL);
    00567
    00568         /*
    00569          * Encode the 64 cipher bits as 11 ascii characters.
    00570          */
    00571         i = ((long)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | rsltblock.b[2];
    00572         encp[3] = itoa64[i&0x3f];       i >>= 6;
    00573         encp[2] = itoa64[i&0x3f];       i >>= 6;
    00574         encp[1] = itoa64[i&0x3f];       i >>= 6;
    00575         encp[0] = itoa64[i];            encp += 4;
    00576         i = ((long)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | rsltblock.b[5];
    00577         encp[3] = itoa64[i&0x3f];       i >>= 6;
    00578         encp[2] = itoa64[i&0x3f];       i >>= 6;
    00579         encp[1] = itoa64[i&0x3f];       i >>= 6;
    00580         encp[0] = itoa64[i];            encp += 4;
    00581         i = ((long)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2;
    00582         encp[2] = itoa64[i&0x3f];       i >>= 6;
    00583         encp[1] = itoa64[i&0x3f];       i >>= 6;
    00584         encp[0] = itoa64[i];
    00585
    00586         encp[3] = 0;
    00587
    00588         return (cryptresult);
    00589 }
    00590
    00591
    00592 /*
    00593  * The Key Schedule, filled in by des_setkey() or setkey().
    00594  */
    00595 #define KS_SIZE 16
    00596 static C_block  KS[KS_SIZE];
    00597
    00598 /*
    00599  * Set up the key schedule from the key.
    00600  */
    00601 int
    00602 des_setkey(key)
    00603         register const char *key;
    00604 {
    00605         register DCL_BLOCK(K, K0, K1);
    00606         register C_block *ptabp;
    00607         register int i;
    00608         static int des_ready = 0;
    00609
    00610         if (!des_ready) {
    00611                 init_des();
    00612                 des_ready = 1;
    00613         }
    00614
    00615         PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT);
    00616         key = (char *)&KS[0];
    00617         STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key);
    00618         for (i = 1; i < 16; i++) {
    00619                 key += sizeof(C_block);
    00620                 STORE(K,K0,K1,*(C_block *)key);
    00621                 ptabp = (C_block *)PC2ROT[Rotates[i]-1];
    00622                 PERM6464(K,K0,K1,(unsigned char *)key,ptabp);
    00623                 STORE(K&~0x03030303L, K0&~0x03030303L, K1, *(C_block *)key);
    00624         }
    00625         return (0);
    00626 }
    00627
    00628 /*
    00629  * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter)
    00630  * iterations of DES, using the the given 24-bit salt and the pre-computed key
    00631  * schedule, and store the resulting 8 chars at "out" (in == out is permitted).
    00632  *
    00633  * NOTE: the performance of this routine is critically dependent on your
    00634  * compiler and machine architecture.
    00635  */
    00636 int
    00637 des_cipher(in, out, salt, num_iter)
    00638         const char *in;
    00639         char *out;
    00640         long salt;
    00641         int num_iter;
    00642 {
    00643         /* variables that we want in registers, most important first */
    00644 #if defined(pdp11)
    00645         register int j;
    00646 #endif
    00647         register long L0, L1, R0, R1, k;
    00648         register C_block *kp;
    00649         register int ks_inc, loop_count;
    00650         C_block B;
    00651
    00652         L0 = salt;
    00653         TO_SIX_BIT(salt, L0);   /* convert to 4*(6+2) format */
    00654
    00655 #if defined(vax) || defined(pdp11)
    00656         salt = ~salt;   /* "x &~ y" is faster than "x & y". */
    00657 #define SALT (~salt)
    00658 #else
    00659 #define SALT salt
    00660 #endif
    00661
    00662 #if defined(MUST_ALIGN)
    00663         B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3];
    00664         B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7];
    00665         LOAD(L,L0,L1,B);
    00666 #else
    00667         LOAD(L,L0,L1,*(C_block *)in);
    00668 #endif
    00669         LOADREG(R,R0,R1,L,L0,L1);
    00670         L0 &= 0x55555555L;
    00671         L1 &= 0x55555555L;
    00672         L0 = (L0 << 1) | L1;    /* L0 is the even-numbered input bits */
    00673         R0 &= 0xaaaaaaaaL;
    00674         R1 = (R1 >> 1) & 0x55555555L;
    00675         L1 = R0 | R1;           /* L1 is the odd-numbered input bits */
    00676         STORE(L,L0,L1,B);
    00677         PERM3264(L,L0,L1,B.b,  (C_block *)IE3264);      /* even bits */
    00678         PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264);      /* odd bits */
    00679
    00680         if (num_iter >= 0)
    00681         {               /* encryption */
    00682                 kp = &KS[0];
    00683                 ks_inc  = (int)sizeof(*kp);
    00684         }
    00685         else
    00686         {               /* decryption */
    00687                 num_iter = -num_iter;
    00688                 kp = &KS[KS_SIZE-1];
    00689                 ks_inc  = -(int)sizeof(*kp);
    00690         }
    00691
    00692         while (--num_iter >= 0) {
    00693                 loop_count = 8;
    00694                 do {
    00695
    00696 #define SPTAB(t, i)     (*(long *)((unsigned char *)t + i*(sizeof(long)/4)))
    00697 #if defined(gould)
    00698                         /* use this if B.b[i] is evaluated just once ... */
    00699 #define DOXOR(x,y,i)    x^=SPTAB(SPE[0][i],B.b[i]); y^=SPTAB(SPE[1][i],B.b[i]);
    00700 #else
    00701 #if defined(pdp11)
    00702                         /* use this if your "long" int indexing is slow */
    00703 #define DOXOR(x,y,i)    j=B.b[i]; x^=SPTAB(SPE[0][i],j); y^=SPTAB(SPE[1][i],j);
    00704 #else
    00705                         /* use this if "k" is allocated to a register ... */
    00706 #define DOXOR(x,y,i)    k=B.b[i]; x^=SPTAB(SPE[0][i],k); y^=SPTAB(SPE[1][i],k);
    00707 #endif
    00708 #endif
    00709
    00710 #define CRUNCH(p0, p1, q0, q1)  \
    00711                         k = (q0 ^ q1) & SALT;   \
    00712                         B.b32.i0 = k ^ q0 ^ kp->b32.i0;         \
    00713                         B.b32.i1 = k ^ q1 ^ kp->b32.i1;         \
    00714                         kp = (C_block *)((char *)kp+ks_inc);    \
    00715                                                         \
    00716                         DOXOR(p0, p1, 0);               \
    00717                         DOXOR(p0, p1, 1);               \
    00718                         DOXOR(p0, p1, 2);               \
    00719                         DOXOR(p0, p1, 3);               \
    00720                         DOXOR(p0, p1, 4);               \
    00721                         DOXOR(p0, p1, 5);               \
    00722                         DOXOR(p0, p1, 6);               \
    00723                         DOXOR(p0, p1, 7);
    00724
    00725                         CRUNCH(L0, L1, R0, R1);
    00726                         CRUNCH(R0, R1, L0, L1);
    00727                 } while (--loop_count != 0);
    00728                 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE));
    00729
    00730
    00731                 /* swap L and R */
    00732                 L0 ^= R0;  L1 ^= R1;
    00733                 R0 ^= L0;  R1 ^= L1;
    00734                 L0 ^= R0;  L1 ^= R1;
    00735         }
    00736
    00737         /* store the encrypted (or decrypted) result */
    00738         L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L);
    00739         L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L);
    00740         STORE(L,L0,L1,B);
    00741         PERM6464(L,L0,L1,B.b, (C_block *)CF6464);
    00742 #if defined(MUST_ALIGN)
    00743         STORE(L,L0,L1,B);
    00744         out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3];
    00745         out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7];
    00746 #else
    00747         STORE(L,L0,L1,*(C_block *)out);
    00748 #endif
    00749         return (0);
    00750 }
    00751
    00752
    00753 /*
    00754  * Initialize various tables.  This need only be done once.  It could even be
    00755  * done at compile time, if the compiler were capable of that sort of thing.
    00756  */
    00757 STATIC void
    00758 init_des()
    00759 {
    00760         register int i, j;
    00761         register long k;
    00762         register int tableno;
    00763         static unsigned char perm[64], tmp32[32];       /* "static" for speed */
    00764
    00765         /*
    00766          * table that converts chars "./0-9A-Za-z"to integers 0-63.
    00767          */
    00768         for (i = 0; i < 64; i++)
    00769                 a64toi[itoa64[i]] = i;
    00770
    00771         /*
    00772          * PC1ROT - bit reverse, then PC1, then Rotate, then PC2.
    00773          */
    00774         for (i = 0; i < 64; i++)
    00775                 perm[i] = 0;
    00776         for (i = 0; i < 64; i++) {
    00777                 if ((k = PC2[i]) == 0)
    00778                         continue;
    00779                 k += Rotates[0]-1;
    00780                 if ((k%28) < Rotates[0]) k -= 28;
    00781                 k = PC1[k];
    00782                 if (k > 0) {
    00783                         k--;
    00784                         k = (k|07) - (k&07);
    00785                         k++;
    00786                 }
    00787                 perm[i] = (unsigned char)k;
    00788         }
    00789 #ifdef DEBUG
    00790         prtab("pc1tab", perm, 8);
    00791 #endif
    00792         init_perm(PC1ROT, perm, 8, 8);
    00793
    00794         /*
    00795          * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2.
    00796          */
    00797         for (j = 0; j < 2; j++) {
    00798                 unsigned char pc2inv[64];
    00799                 for (i = 0; i < 64; i++)
    00800                         perm[i] = pc2inv[i] = 0;
    00801                 for (i = 0; i < 64; i++) {
    00802                         if ((k = PC2[i]) == 0)
    00803                                 continue;
    00804                         pc2inv[k-1] = i+1;
    00805                 }
    00806                 for (i = 0; i < 64; i++) {
    00807                         if ((k = PC2[i]) == 0)
    00808                                 continue;
    00809                         k += j;
    00810                         if ((k%28) <= j) k -= 28;
    00811                         perm[i] = pc2inv[k];
    00812                 }
    00813 #ifdef DEBUG
    00814                 prtab("pc2tab", perm, 8);
    00815 #endif
    00816                 init_perm(PC2ROT[j], perm, 8, 8);
    00817         }
    00818
    00819         /*
    00820          * Bit reverse, then initial permutation, then expansion.
    00821          */
    00822         for (i = 0; i < 8; i++) {
    00823                 for (j = 0; j < 8; j++) {
    00824                         k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1];
    00825                         if (k > 32)
    00826                                 k -= 32;
    00827                         else if (k > 0)
    00828                                 k--;
    00829                         if (k > 0) {
    00830                                 k--;
    00831                                 k = (k|07) - (k&07);
    00832                                 k++;
    00833                         }
    00834                         perm[i*8+j] = (unsigned char)k;
    00835                 }
    00836         }
    00837 #ifdef DEBUG
    00838         prtab("ietab", perm, 8);
    00839 #endif
    00840         init_perm(IE3264, perm, 4, 8);
    00841
    00842         /*
    00843          * Compression, then final permutation, then bit reverse.
    00844          */
    00845         for (i = 0; i < 64; i++) {
    00846                 k = IP[CIFP[i]-1];
    00847                 if (k > 0) {
    00848                         k--;
    00849                         k = (k|07) - (k&07);
    00850                         k++;
    00851                 }
    00852                 perm[k-1] = i+1;
    00853         }
    00854 #ifdef DEBUG
    00855         prtab("cftab", perm, 8);
    00856 #endif
    00857         init_perm(CF6464, perm, 8, 8);
    00858
    00859         /*
    00860          * SPE table
    00861          */
    00862         for (i = 0; i < 48; i++)
    00863                 perm[i] = P32Tr[ExpandTr[i]-1];
    00864         for (tableno = 0; tableno < 8; tableno++) {
    00865                 for (j = 0; j < 64; j++)  {
    00866                         k = (((j >> 0) &01) << 5)|
    00867                             (((j >> 1) &01) << 3)|
    00868                             (((j >> 2) &01) << 2)|
    00869                             (((j >> 3) &01) << 1)|
    00870                             (((j >> 4) &01) << 0)|
    00871                             (((j >> 5) &01) << 4);
    00872                         k = S[tableno][k];
    00873                         k = (((k >> 3)&01) << 0)|
    00874                             (((k >> 2)&01) << 1)|
    00875                             (((k >> 1)&01) << 2)|
    00876                             (((k >> 0)&01) << 3);
    00877                         for (i = 0; i < 32; i++)
    00878                                 tmp32[i] = 0;
    00879                         for (i = 0; i < 4; i++)
    00880                                 tmp32[4 * tableno + i] = (unsigned char)(k >> i) & 01;
    00881                         k = 0;
    00882                         for (i = 24; --i >= 0; )
    00883                                 k = (k<<1) | tmp32[perm[i]-1];
    00884                         TO_SIX_BIT(SPE[0][tableno][j], k);
    00885                         k = 0;
    00886                         for (i = 24; --i >= 0; )
    00887                                 k = (k<<1) | tmp32[perm[i+24]-1];
    00888                         TO_SIX_BIT(SPE[1][tableno][j], k);
    00889                 }
    00890         }
    00891 }
    00892
    00893 /*
    00894  * Initialize "perm" to represent transformation "p", which rearranges
    00895  * (perhaps with expansion and/or contraction) one packed array of bits
    00896  * (of size "chars_in" characters) into another array (of size "chars_out"
    00897  * characters).
    00898  *
    00899  * "perm" must be all-zeroes on entry to this routine.
    00900  */
    00901 STATIC void
    00902 init_perm(perm, p, chars_in, chars_out)
    00903         C_block perm[64/CHUNKBITS][1<<CHUNKBITS];
    00904         unsigned char p[64];
    00905         int chars_in, chars_out;
    00906 {
    00907         register int i, j, k, l;
    00908
    00909         for (k = 0; k < chars_out*8; k++) {     /* each output bit position */
    00910                 l = p[k] - 1;           /* where this bit comes from */
    00911                 if (l < 0)
    00912                         continue;       /* output bit is always 0 */
    00913                 i = l>>LGCHUNKBITS;     /* which chunk this bit comes from */
    00914                 l = 1<<(l&(CHUNKBITS-1));       /* mask for this bit */
    00915                 for (j = 0; j < (1<<CHUNKBITS); j++) {  /* each chunk value */
    00916                         if ((j & l) != 0)
    00917                                 perm[i][j].b[k>>3] |= 1<<(k&07);
    00918                 }
    00919         }
    00920 }
    00921
    00922 /*
    00923  * "setkey" routine (for backwards compatibility)
    00924  */
    00925 int
    00926 setkey(key)
    00927         register const char *key;
    00928 {
    00929         register int i, j, k;
    00930         C_block keyblock;
    00931
    00932         for (i = 0; i < 8; i++) {
    00933                 k = 0;
    00934                 for (j = 0; j < 8; j++) {
    00935                         k <<= 1;
    00936                         k |= (unsigned char)*key++;
    00937                 }
    00938                 keyblock.b[i] = k;
    00939         }
    00940         return (des_setkey((char *)keyblock.b));
    00941 }
    00942
    00943 /*
    00944  * "encrypt" routine (for backwards compatibility)
    00945  */
    00946 int
    00947 encrypt(block, flag)
    00948         register char *block;
    00949         int flag;
    00950 {
    00951         register int i, j, k;
    00952         C_block cblock;
    00953
    00954         for (i = 0; i < 8; i++) {
    00955                 k = 0;
    00956                 for (j = 0; j < 8; j++) {
    00957                         k <<= 1;
    00958                         k |= (unsigned char)*block++;
    00959                 }
    00960                 cblock.b[i] = k;
    00961         }
    00962         if (des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag ? -1: 1)))
    00963                 return (1);
    00964         for (i = 7; i >= 0; i--) {
    00965                 k = cblock.b[i];
    00966                 for (j = 7; j >= 0; j--) {
    00967                         *--block = k&01;
    00968                         k >>= 1;
    00969                 }
    00970         }
    00971         return (0);
    00972 }
    00973
    00974 #ifdef DEBUG
    00975 STATIC void
    00976 prtab(s, t, num_rows)
    00977         char *s;
    00978         unsigned char *t;
    00979         int num_rows;
    00980 {
    00981         register int i, j;
    00982
    00983         (void)printf("%s:\n", s);
    00984         for (i = 0; i < num_rows; i++) {
    00985                 for (j = 0; j < 8; j++) {
    00986                          (void)printf("%3d", t[i*8+j]);
    00987                 }
    00988                 (void)printf("\n");
    00989         }
    00990         (void)printf("\n");
    00991 }
    00992 #endif
    00993