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