1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to Berkeley by 6 * Tom Truscott. 7 * 8 * %sccs.include.redist.c% 9 */ 10 11 #if defined(LIBC_SCCS) && !defined(lint) 12 static char sccsid[] = "@(#)crypt.c 5.8 (Berkeley) 04/26/91"; 13 #endif /* LIBC_SCCS and not lint */ 14 15 #include <unistd.h> 16 #include <pwd.h> 17 18 /* 19 * UNIX password, and DES, encryption. 20 * By Tom Truscott, trt@rti.rti.org, 21 * from algorithms by Robert W. Baldwin and James Gillogly. 22 * 23 * References: 24 * "Mathematical Cryptology for Computer Scientists and Mathematicians," 25 * by Wayne Patterson, 1987, ISBN 0-8476-7438-X. 26 * 27 * "Password Security: A Case History," R. Morris and Ken Thompson, 28 * Communications of the ACM, vol. 22, pp. 594-597, Nov. 1979. 29 * 30 * "DES will be Totally Insecure within Ten Years," M.E. Hellman, 31 * IEEE Spectrum, vol. 16, pp. 32-39, July 1979. 32 */ 33 34 /* ===== Configuration ==================== */ 35 36 /* 37 * define "MUST_ALIGN" if your compiler cannot load/store 38 * long integers at arbitrary (e.g. odd) memory locations. 39 * (Either that or never pass unaligned addresses to des_cipher!) 40 */ 41 #if !defined(vax) 42 #define MUST_ALIGN 43 #endif 44 45 /* 46 * define "LONG_IS_32_BITS" only if sizeof(long)==4. 47 * This avoids use of bit fields (your compiler may be sloppy with them). 48 */ 49 #if !defined(cray) 50 #define LONG_IS_32_BITS 51 #endif 52 53 /* 54 * define "B64" to be the declaration for a 64 bit integer. 55 * XXX this feature is currently unused, see "endian" comment below. 56 */ 57 #if defined(cray) 58 #define B64 long 59 #endif 60 #if defined(convex) 61 #define B64 long long 62 #endif 63 64 /* 65 * define "LARGEDATA" to get faster permutations, by using about 72 kilobytes 66 * of lookup tables. This speeds up des_setkey() and des_cipher(), but has 67 * little effect on crypt(). 68 */ 69 #if defined(notdef) 70 #define LARGEDATA 71 #endif 72 73 /* compile with "-DSTATIC=int" when profiling */ 74 #ifndef STATIC 75 #define STATIC static 76 #endif 77 STATIC init_des(), init_perm(), permute(); 78 #ifdef DEBUG 79 STATIC prtab(); 80 #endif 81 82 /* ==================================== */ 83 84 /* 85 * Cipher-block representation (Bob Baldwin): 86 * 87 * DES operates on groups of 64 bits, numbered 1..64 (sigh). One 88 * representation is to store one bit per byte in an array of bytes. Bit N of 89 * the NBS spec is stored as the LSB of the Nth byte (index N-1) in the array. 90 * Another representation stores the 64 bits in 8 bytes, with bits 1..8 in the 91 * first byte, 9..16 in the second, and so on. The DES spec apparently has 92 * bit 1 in the MSB of the first byte, but that is particularly noxious so we 93 * bit-reverse each byte so that bit 1 is the LSB of the first byte, bit 8 is 94 * the MSB of the first byte. Specifically, the 64-bit input data and key are 95 * converted to LSB format, and the output 64-bit block is converted back into 96 * MSB format. 97 * 98 * DES operates internally on groups of 32 bits which are expanded to 48 bits 99 * by permutation E and shrunk back to 32 bits by the S boxes. To speed up 100 * the computation, the expansion is applied only once, the expanded 101 * representation is maintained during the encryption, and a compression 102 * permutation is applied only at the end. To speed up the S-box lookups, 103 * the 48 bits are maintained as eight 6 bit groups, one per byte, which 104 * directly feed the eight S-boxes. Within each byte, the 6 bits are the 105 * most significant ones. The low two bits of each byte are zero. (Thus, 106 * bit 1 of the 48 bit E expansion is stored as the "4"-valued bit of the 107 * first byte in the eight byte representation, bit 2 of the 48 bit value is 108 * the "8"-valued bit, and so on.) In fact, a combined "SPE"-box lookup is 109 * used, in which the output is the 64 bit result of an S-box lookup which 110 * has been permuted by P and expanded by E, and is ready for use in the next 111 * iteration. Two 32-bit wide tables, SPE[0] and SPE[1], are used for this 112 * lookup. Since each byte in the 48 bit path is a multiple of four, indexed 113 * lookup of SPE[0] and SPE[1] is simple and fast. The key schedule and 114 * "salt" are also converted to this 8*(6+2) format. The SPE table size is 115 * 8*64*8 = 4K bytes. 116 * 117 * To speed up bit-parallel operations (such as XOR), the 8 byte 118 * representation is "union"ed with 32 bit values "i0" and "i1", and, on 119 * machines which support it, a 64 bit value "b64". This data structure, 120 * "C_block", has two problems. First, alignment restrictions must be 121 * honored. Second, the byte-order (e.g. little-endian or big-endian) of 122 * the architecture becomes visible. 123 * 124 * The byte-order problem is unfortunate, since on the one hand it is good 125 * to have a machine-independent C_block representation (bits 1..8 in the 126 * first byte, etc.), and on the other hand it is good for the LSB of the 127 * first byte to be the LSB of i0. We cannot have both these things, so we 128 * currently use the "little-endian" representation and avoid any multi-byte 129 * operations that depend on byte order. This largely precludes use of the 130 * 64-bit datatype since the relative order of i0 and i1 are unknown. It 131 * also inhibits grouping the SPE table to look up 12 bits at a time. (The 132 * 12 bits can be stored in a 16-bit field with 3 low-order zeroes and 1 133 * high-order zero, providing fast indexing into a 64-bit wide SPE.) On the 134 * other hand, 64-bit datatypes are currently rare, and a 12-bit SPE lookup 135 * requires a 128 kilobyte table, so perhaps this is not a big loss. 136 * 137 * Permutation representation (Jim Gillogly): 138 * 139 * A transformation is defined by its effect on each of the 8 bytes of the 140 * 64-bit input. For each byte we give a 64-bit output that has the bits in 141 * the input distributed appropriately. The transformation is then the OR 142 * of the 8 sets of 64-bits. This uses 8*256*8 = 16K bytes of storage for 143 * each transformation. Unless LARGEDATA is defined, however, a more compact 144 * table is used which looks up 16 4-bit "chunks" rather than 8 8-bit chunks. 145 * The smaller table uses 16*16*8 = 2K bytes for each transformation. This 146 * is slower but tolerable, particularly for password encryption in which 147 * the SPE transformation is iterated many times. The small tables total 9K 148 * bytes, the large tables total 72K bytes. 149 * 150 * The transformations used are: 151 * IE3264: MSB->LSB conversion, initial permutation, and expansion. 152 * This is done by collecting the 32 even-numbered bits and applying 153 * a 32->64 bit transformation, and then collecting the 32 odd-numbered 154 * bits and applying the same transformation. Since there are only 155 * 32 input bits, the IE3264 transformation table is half the size of 156 * the usual table. 157 * CF6464: Compression, final permutation, and LSB->MSB conversion. 158 * This is done by two trivial 48->32 bit compressions to obtain 159 * a 64-bit block (the bit numbering is given in the "CIFP" table) 160 * followed by a 64->64 bit "cleanup" transformation. (It would 161 * be possible to group the bits in the 64-bit block so that 2 162 * identical 32->32 bit transformations could be used instead, 163 * saving a factor of 4 in space and possibly 2 in time, but 164 * byte-ordering and other complications rear their ugly head. 165 * Similar opportunities/problems arise in the key schedule 166 * transforms.) 167 * PC1ROT: MSB->LSB, PC1 permutation, rotate, and PC2 permutation. 168 * This admittedly baroque 64->64 bit transformation is used to 169 * produce the first code (in 8*(6+2) format) of the key schedule. 170 * PC2ROT[0]: Inverse PC2 permutation, rotate, and PC2 permutation. 171 * It would be possible to define 15 more transformations, each 172 * with a different rotation, to generate the entire key schedule. 173 * To save space, however, we instead permute each code into the 174 * next by using a transformation that "undoes" the PC2 permutation, 175 * rotates the code, and then applies PC2. Unfortunately, PC2 176 * transforms 56 bits into 48 bits, dropping 8 bits, so PC2 is not 177 * invertible. We get around that problem by using a modified PC2 178 * which retains the 8 otherwise-lost bits in the unused low-order 179 * bits of each byte. The low-order bits are cleared when the 180 * codes are stored into the key schedule. 181 * PC2ROT[1]: Same as PC2ROT[0], but with two rotations. 182 * This is faster than applying PC2ROT[0] twice, 183 * 184 * The Bell Labs "salt" (Bob Baldwin): 185 * 186 * The salting is a simple permutation applied to the 48-bit result of E. 187 * Specifically, if bit i (1 <= i <= 24) of the salt is set then bits i and 188 * i+24 of the result are swapped. The salt is thus a 24 bit number, with 189 * 16777216 possible values. (The original salt was 12 bits and could not 190 * swap bits 13..24 with 36..48.) 191 * 192 * It is possible, but ugly, to warp the SPE table to account for the salt 193 * permutation. Fortunately, the conditional bit swapping requires only 194 * about four machine instructions and can be done on-the-fly with about an 195 * 8% performance penalty. 196 */ 197 198 typedef union { 199 unsigned char b[8]; 200 struct { 201 #if defined(LONG_IS_32_BITS) 202 /* long is often faster than a 32-bit bit field */ 203 long i0; 204 long i1; 205 #else 206 long i0: 32; 207 long i1: 32; 208 #endif 209 } b32; 210 #if defined(B64) 211 B64 b64; 212 #endif 213 } C_block; 214 215 /* 216 * Convert twenty-four-bit long in host-order 217 * to six bits (and 2 low-order zeroes) per char little-endian format. 218 */ 219 #define TO_SIX_BIT(rslt, src) { \ 220 C_block cvt; \ 221 cvt.b[0] = src; src >>= 6; \ 222 cvt.b[1] = src; src >>= 6; \ 223 cvt.b[2] = src; src >>= 6; \ 224 cvt.b[3] = src; \ 225 rslt = (cvt.b32.i0 & 0x3f3f3f3fL) << 2; \ 226 } 227 228 /* 229 * These macros may someday permit efficient use of 64-bit integers. 230 */ 231 #define ZERO(d,d0,d1) d0 = 0, d1 = 0 232 #define LOAD(d,d0,d1,bl) d0 = (bl).b32.i0, d1 = (bl).b32.i1 233 #define LOADREG(d,d0,d1,s,s0,s1) d0 = s0, d1 = s1 234 #define OR(d,d0,d1,bl) d0 |= (bl).b32.i0, d1 |= (bl).b32.i1 235 #define STORE(s,s0,s1,bl) (bl).b32.i0 = s0, (bl).b32.i1 = s1 236 #define DCL_BLOCK(d,d0,d1) long d0, d1 237 238 #if defined(LARGEDATA) 239 /* Waste memory like crazy. Also, do permutations in line */ 240 #define LGCHUNKBITS 3 241 #define CHUNKBITS (1<<LGCHUNKBITS) 242 #define PERM6464(d,d0,d1,cpp,p) \ 243 LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]); \ 244 OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]); \ 245 OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]); \ 246 OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]); \ 247 OR (d,d0,d1,(p)[(4<<CHUNKBITS)+(cpp)[4]]); \ 248 OR (d,d0,d1,(p)[(5<<CHUNKBITS)+(cpp)[5]]); \ 249 OR (d,d0,d1,(p)[(6<<CHUNKBITS)+(cpp)[6]]); \ 250 OR (d,d0,d1,(p)[(7<<CHUNKBITS)+(cpp)[7]]); 251 #define PERM3264(d,d0,d1,cpp,p) \ 252 LOAD(d,d0,d1,(p)[(0<<CHUNKBITS)+(cpp)[0]]); \ 253 OR (d,d0,d1,(p)[(1<<CHUNKBITS)+(cpp)[1]]); \ 254 OR (d,d0,d1,(p)[(2<<CHUNKBITS)+(cpp)[2]]); \ 255 OR (d,d0,d1,(p)[(3<<CHUNKBITS)+(cpp)[3]]); 256 #else 257 /* "small data" */ 258 #define LGCHUNKBITS 2 259 #define CHUNKBITS (1<<LGCHUNKBITS) 260 #define PERM6464(d,d0,d1,cpp,p) \ 261 { C_block tblk; permute(cpp,&tblk,p,8); LOAD (d,d0,d1,tblk); } 262 #define PERM3264(d,d0,d1,cpp,p) \ 263 { C_block tblk; permute(cpp,&tblk,p,4); LOAD (d,d0,d1,tblk); } 264 265 STATIC 266 permute(cp, out, p, chars_in) 267 unsigned char *cp; 268 C_block *out; 269 register C_block *p; 270 int chars_in; 271 { 272 register DCL_BLOCK(D,D0,D1); 273 register C_block *tp; 274 register int t; 275 276 ZERO(D,D0,D1); 277 do { 278 t = *cp++; 279 tp = &p[t&0xf]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 280 tp = &p[t>>4]; OR(D,D0,D1,*tp); p += (1<<CHUNKBITS); 281 } while (--chars_in > 0); 282 STORE(D,D0,D1,*out); 283 } 284 #endif /* LARGEDATA */ 285 286 287 /* ===== (mostly) Standard DES Tables ==================== */ 288 289 static unsigned char IP[] = { /* initial permutation */ 290 58, 50, 42, 34, 26, 18, 10, 2, 291 60, 52, 44, 36, 28, 20, 12, 4, 292 62, 54, 46, 38, 30, 22, 14, 6, 293 64, 56, 48, 40, 32, 24, 16, 8, 294 57, 49, 41, 33, 25, 17, 9, 1, 295 59, 51, 43, 35, 27, 19, 11, 3, 296 61, 53, 45, 37, 29, 21, 13, 5, 297 63, 55, 47, 39, 31, 23, 15, 7, 298 }; 299 300 /* The final permutation is the inverse of IP - no table is necessary */ 301 302 static unsigned char ExpandTr[] = { /* expansion operation */ 303 32, 1, 2, 3, 4, 5, 304 4, 5, 6, 7, 8, 9, 305 8, 9, 10, 11, 12, 13, 306 12, 13, 14, 15, 16, 17, 307 16, 17, 18, 19, 20, 21, 308 20, 21, 22, 23, 24, 25, 309 24, 25, 26, 27, 28, 29, 310 28, 29, 30, 31, 32, 1, 311 }; 312 313 static unsigned char PC1[] = { /* permuted choice table (key) */ 314 57, 49, 41, 33, 25, 17, 9, 315 1, 58, 50, 42, 34, 26, 18, 316 10, 2, 59, 51, 43, 35, 27, 317 19, 11, 3, 60, 52, 44, 36, 318 319 63, 55, 47, 39, 31, 23, 15, 320 7, 62, 54, 46, 38, 30, 22, 321 14, 6, 61, 53, 45, 37, 29, 322 21, 13, 5, 28, 20, 12, 4, 323 }; 324 325 static unsigned char Rotates[] = { /* number of rotations of PC1 */ 326 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1, 327 }; 328 329 /* note: each "row" of PC2 is left-padded with bits that make it invertible */ 330 static unsigned char PC2[] = { /* permuted choice key (table) */ 331 9, 18, 14, 17, 11, 24, 1, 5, 332 22, 25, 3, 28, 15, 6, 21, 10, 333 35, 38, 23, 19, 12, 4, 26, 8, 334 43, 54, 16, 7, 27, 20, 13, 2, 335 336 0, 0, 41, 52, 31, 37, 47, 55, 337 0, 0, 30, 40, 51, 45, 33, 48, 338 0, 0, 44, 49, 39, 56, 34, 53, 339 0, 0, 46, 42, 50, 36, 29, 32, 340 }; 341 342 static unsigned char S[8][64] = { /* 48->32 bit substitution tables */ 343 /* S[1] */ 344 14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 345 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 346 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 347 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13, 348 /* S[2] */ 349 15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 350 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 351 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, 352 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9, 353 /* S[3] */ 354 10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 355 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 356 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, 357 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12, 358 /* S[4] */ 359 7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 360 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 361 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, 362 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14, 363 /* S[5] */ 364 2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 365 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 366 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, 367 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3, 368 /* S[6] */ 369 12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 370 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 371 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, 372 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13, 373 /* S[7] */ 374 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 375 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 376 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, 377 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12, 378 /* S[8] */ 379 13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 380 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 381 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, 382 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11, 383 }; 384 385 static unsigned char P32Tr[] = { /* 32-bit permutation function */ 386 16, 7, 20, 21, 387 29, 12, 28, 17, 388 1, 15, 23, 26, 389 5, 18, 31, 10, 390 2, 8, 24, 14, 391 32, 27, 3, 9, 392 19, 13, 30, 6, 393 22, 11, 4, 25, 394 }; 395 396 static unsigned char CIFP[] = { /* compressed/interleaved permutation */ 397 1, 2, 3, 4, 17, 18, 19, 20, 398 5, 6, 7, 8, 21, 22, 23, 24, 399 9, 10, 11, 12, 25, 26, 27, 28, 400 13, 14, 15, 16, 29, 30, 31, 32, 401 402 33, 34, 35, 36, 49, 50, 51, 52, 403 37, 38, 39, 40, 53, 54, 55, 56, 404 41, 42, 43, 44, 57, 58, 59, 60, 405 45, 46, 47, 48, 61, 62, 63, 64, 406 }; 407 408 static unsigned char itoa64[] = /* 0..63 => ascii-64 */ 409 "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 410 411 412 /* ===== Tables that are initialized at run time ==================== */ 413 414 415 static unsigned char a64toi[128]; /* ascii-64 => 0..63 */ 416 417 /* Initial key schedule permutation */ 418 static C_block PC1ROT[64/CHUNKBITS][1<<CHUNKBITS]; 419 420 /* Subsequent key schedule rotation permutations */ 421 static C_block PC2ROT[2][64/CHUNKBITS][1<<CHUNKBITS]; 422 423 /* Initial permutation/expansion table */ 424 static C_block IE3264[32/CHUNKBITS][1<<CHUNKBITS]; 425 426 /* Table that combines the S, P, and E operations. */ 427 static long SPE[2][8][64]; 428 429 /* compressed/interleaved => final permutation table */ 430 static C_block CF6464[64/CHUNKBITS][1<<CHUNKBITS]; 431 432 433 /* ==================================== */ 434 435 436 static C_block constdatablock; /* encryption constant */ 437 static char cryptresult[1+4+4+11+1]; /* encrypted result */ 438 439 /* 440 * Return a pointer to static data consisting of the "setting" 441 * followed by an encryption produced by the "key" and "setting". 442 */ 443 char * 444 crypt(key, setting) 445 register const char *key; 446 register const char *setting; 447 { 448 register char *encp; 449 register long i; 450 register int t; 451 long salt; 452 int num_iter, salt_size, key_size; 453 C_block keyblock, rsltblock; 454 455 for (i = 0; i < 8; i++) { 456 if ((t = 2*(unsigned char)(*key)) != 0) 457 key++; 458 keyblock.b[i] = t; 459 } 460 des_setkey((char *)keyblock.b); /* also initializes "a64toi" */ 461 462 encp = &cryptresult[0]; 463 switch (*setting) { 464 case _PASSWORD_EFMT1: 465 *encp++ = *setting++; 466 467 /* get iteration count */ 468 num_iter = 0; 469 for (i = 4; --i >= 0; ) { 470 if ((t = (unsigned char)setting[i]) == '\0') 471 t = '.'; 472 encp[i] = t; 473 num_iter = (num_iter<<6) | a64toi[t]; 474 } 475 setting += 4; 476 encp += 4; 477 salt_size = 4; 478 key_size = 128; 479 break; 480 default: 481 num_iter = 25; 482 salt_size = 2; 483 key_size = 8; 484 } 485 486 salt = 0; 487 for (i = salt_size; --i >= 0; ) { 488 if ((t = (unsigned char)setting[i]) == '\0') 489 t = '.'; 490 encp[i] = t; 491 salt = (salt<<6) | a64toi[t]; 492 } 493 encp += salt_size; 494 des_cipher((char *)&constdatablock, (char *)&rsltblock, salt, num_iter); 495 496 /* 497 * encrypt the remainder of the password 8 characters at a time. 498 */ 499 while ((key_size -= 8) > 0 && *key) { 500 C_block xdatablock; 501 502 for (i = 0; i < 8; i++) { 503 if ((t = 2*(unsigned char)(*key)) != 0) 504 key++; 505 keyblock.b[i] = t; 506 if (t == 0) 507 break; /* pad out with previous key */ 508 } 509 des_setkey((char *)keyblock.b); 510 des_cipher((char *)&constdatablock, (char *)&xdatablock, 0L, 1); 511 rsltblock.b32.i0 ^= xdatablock.b32.i0; 512 rsltblock.b32.i1 ^= xdatablock.b32.i1; 513 } 514 515 /* 516 * Encode the 64 cipher bits as 11 ascii characters. 517 */ 518 i = ((long)((rsltblock.b[0]<<8) | rsltblock.b[1])<<8) | rsltblock.b[2]; 519 encp[3] = itoa64[i&0x3f]; i >>= 6; 520 encp[2] = itoa64[i&0x3f]; i >>= 6; 521 encp[1] = itoa64[i&0x3f]; i >>= 6; 522 encp[0] = itoa64[i]; encp += 4; 523 i = ((long)((rsltblock.b[3]<<8) | rsltblock.b[4])<<8) | rsltblock.b[5]; 524 encp[3] = itoa64[i&0x3f]; i >>= 6; 525 encp[2] = itoa64[i&0x3f]; i >>= 6; 526 encp[1] = itoa64[i&0x3f]; i >>= 6; 527 encp[0] = itoa64[i]; encp += 4; 528 i = ((long)((rsltblock.b[6])<<8) | rsltblock.b[7])<<2; 529 encp[2] = itoa64[i&0x3f]; i >>= 6; 530 encp[1] = itoa64[i&0x3f]; i >>= 6; 531 encp[0] = itoa64[i]; 532 533 encp[3] = 0; 534 535 return(cryptresult); 536 } 537 538 539 /* 540 * The Key Schedule, filled in by des_setkey() or setkey(). 541 */ 542 #define KS_SIZE 16 543 static C_block KS[KS_SIZE]; 544 545 /* 546 * Set up the key schedule from the key. 547 */ 548 void 549 des_setkey(key) 550 register const char *key; 551 { 552 register DCL_BLOCK(K, K0, K1); 553 register C_block *ptabp; 554 register int i; 555 static int des_ready = 0; 556 557 if (!des_ready) { 558 init_des(); 559 des_ready = 1; 560 } 561 562 PERM6464(K,K0,K1,(unsigned char *)key,(C_block *)PC1ROT); 563 key = (char *)&KS[0]; 564 STORE(K&0xfcfcfcfcL, K0&0xfcfcfcfcL, K1, *(C_block *)key); 565 for (i = 1; i < 16; i++) { 566 key += sizeof(C_block); 567 STORE(K,K0,K1,*(C_block *)key); 568 ptabp = (C_block *)PC2ROT[Rotates[i]-1]; 569 PERM6464(K,K0,K1,(unsigned char *)key,ptabp); 570 STORE(K&0xfcfcfcfcL, K0&0xfcfcfcfcL, K1, *(C_block *)key); 571 } 572 } 573 574 /* 575 * Encrypt (or decrypt if num_iter < 0) the 8 chars at "in" with abs(num_iter) 576 * iterations of DES, using the the given 24-bit salt and the pre-computed key 577 * schedule, and store the resulting 8 chars at "out" (in == out is permitted). 578 * 579 * NOTE: the performance of this routine is critically dependent on your 580 * compiler and machine architecture. 581 */ 582 void 583 des_cipher(in, out, salt, num_iter) 584 const char *in; 585 char *out; 586 long salt; 587 int num_iter; 588 { 589 /* variables that we want in registers, most important first */ 590 #if defined(pdp11) 591 register int j; 592 #endif 593 register long L0, L1, R0, R1, k; 594 register C_block *kp; 595 register int ks_inc, loop_count; 596 C_block B; 597 598 L0 = salt; 599 TO_SIX_BIT(salt, L0); /* convert to 8*(6+2) format */ 600 601 #if defined(vax) || defined(pdp11) 602 salt = ~salt; /* "x &~ y" is faster than "x & y". */ 603 #define SALT (~salt) 604 #else 605 #define SALT salt 606 #endif 607 608 #if defined(MUST_ALIGN) 609 B.b[0] = in[0]; B.b[1] = in[1]; B.b[2] = in[2]; B.b[3] = in[3]; 610 B.b[4] = in[4]; B.b[5] = in[5]; B.b[6] = in[6]; B.b[7] = in[7]; 611 LOAD(L,L0,L1,B); 612 #else 613 LOAD(L,L0,L1,*(C_block *)in); 614 #endif 615 LOADREG(R,R0,R1,L,L0,L1); 616 L0 &= 0x55555555L; 617 L1 &= 0x55555555L; 618 L0 = (L0 << 1) | L1; /* L0 is the even-numbered input bits */ 619 R0 &= 0xaaaaaaaaL; 620 R1 = (R1 >> 1) & 0x55555555L; 621 L1 = R0 | R1; /* L1 is the odd-numbered input bits */ 622 STORE(L,L0,L1,B); 623 PERM3264(L,L0,L1,B.b, (C_block *)IE3264); /* even bits */ 624 PERM3264(R,R0,R1,B.b+4,(C_block *)IE3264); /* odd bits */ 625 626 if (num_iter >= 0) 627 { /* encryption */ 628 kp = &KS[0]; 629 ks_inc = sizeof(*kp); 630 } 631 else 632 { /* decryption */ 633 num_iter = -num_iter; 634 kp = &KS[KS_SIZE-1]; 635 ks_inc = -sizeof(*kp); 636 } 637 638 while (--num_iter >= 0) { 639 loop_count = 8; 640 do { 641 642 #define BTAB(i) (((unsigned char *)&B.b[0])[i]) 643 #define SPTAB(t, i) (*(long *)((unsigned char *)t \ 644 + i*(sizeof(long)/4))) 645 #if defined(gould) 646 /* use this if BTAB(i) is evaluated just once ... */ 647 #define DOXOR(a,b,i) a^=SPTAB(SPE[0][i],BTAB(i));b^=SPTAB(SPE[1][i],BTAB(i)); 648 #else 649 #if defined(pdp11) 650 /* use this if your "long" int indexing is slow */ 651 #define DOXOR(a,b,i) j=BTAB(i); a^=SPTAB(SPE[0][i],j); b^=SPTAB(SPE[1][i],j); 652 #else 653 /* use this if "k" is allocated to a register ... */ 654 #define DOXOR(a,b,i) k=BTAB(i); a^=SPTAB(SPE[0][i],k); b^=SPTAB(SPE[1][i],k); 655 #endif 656 #endif 657 658 #define CRUNCH(L0, L1, R0, R1) \ 659 k = (R0 ^ R1) & SALT; \ 660 B.b32.i0 = k ^ R0 ^ kp->b32.i0; \ 661 B.b32.i1 = k ^ R1 ^ kp->b32.i1; \ 662 kp = (C_block *)((char *)kp+ks_inc); \ 663 \ 664 DOXOR(L0, L1, 0); \ 665 DOXOR(L0, L1, 1); \ 666 DOXOR(L0, L1, 2); \ 667 DOXOR(L0, L1, 3); \ 668 DOXOR(L0, L1, 4); \ 669 DOXOR(L0, L1, 5); \ 670 DOXOR(L0, L1, 6); \ 671 DOXOR(L0, L1, 7); 672 673 CRUNCH(L0, L1, R0, R1); 674 CRUNCH(R0, R1, L0, L1); 675 } while (--loop_count != 0); 676 kp = (C_block *)((char *)kp-(ks_inc*KS_SIZE)); 677 678 679 /* swap L and R */ 680 L0 ^= R0; L1 ^= R1; 681 R0 ^= L0; R1 ^= L1; 682 L0 ^= R0; L1 ^= R1; 683 } 684 685 /* store the encrypted (or decrypted) result */ 686 L0 = ((L0 >> 3) & 0x0f0f0f0fL) | ((L1 << 1) & 0xf0f0f0f0L); 687 L1 = ((R0 >> 3) & 0x0f0f0f0fL) | ((R1 << 1) & 0xf0f0f0f0L); 688 STORE(L,L0,L1,B); 689 PERM6464(L,L0,L1,B.b, (C_block *)CF6464); 690 #if defined(MUST_ALIGN) 691 STORE(L,L0,L1,B); 692 out[0] = B.b[0]; out[1] = B.b[1]; out[2] = B.b[2]; out[3] = B.b[3]; 693 out[4] = B.b[4]; out[5] = B.b[5]; out[6] = B.b[6]; out[7] = B.b[7]; 694 #else 695 STORE(L,L0,L1,*(C_block *)out); 696 #endif 697 } 698 699 700 /* 701 * Initialize various tables. This need only be done once. It could even be 702 * done at compile time, if the compiler were capable of that sort of thing. 703 */ 704 STATIC 705 init_des() 706 { 707 register int i, j; 708 register long k; 709 register int tableno; 710 static unsigned char perm[64], tmp32[32]; /* "static" for speed */ 711 712 /* 713 * table that converts chars "./0-9A-Za-z"to integers 0-63. 714 */ 715 for (i = 0; i < 64; i++) 716 a64toi[itoa64[i]] = i; 717 718 /* 719 * PC1ROT - bit reverse, then PC1, then Rotate, then PC2. 720 */ 721 for (i = 0; i < 64; i++) 722 perm[i] = 0; 723 for (i = 0; i < 64; i++) { 724 if ((k = PC2[i]) == 0) 725 continue; 726 k += Rotates[0]-1; 727 if ((k%28) < Rotates[0]) k -= 28; 728 k = PC1[k]; 729 if (k > 0) { 730 k--; 731 k = (k|07) - (k&07); 732 k++; 733 } 734 perm[i] = k; 735 } 736 #ifdef DEBUG 737 prtab("pc1tab", perm, 8); 738 #endif 739 init_perm(PC1ROT, perm, 8, 8); 740 741 /* 742 * PC2ROT - PC2 inverse, then Rotate (once or twice), then PC2. 743 */ 744 for (j = 0; j < 2; j++) { 745 unsigned char pc2inv[64]; 746 for (i = 0; i < 64; i++) 747 perm[i] = pc2inv[i] = 0; 748 for (i = 0; i < 64; i++) { 749 if ((k = PC2[i]) == 0) 750 continue; 751 pc2inv[k-1] = i+1; 752 } 753 for (i = 0; i < 64; i++) { 754 if ((k = PC2[i]) == 0) 755 continue; 756 k += j; 757 if ((k%28) <= j) k -= 28; 758 perm[i] = pc2inv[k]; 759 } 760 #ifdef DEBUG 761 prtab("pc2tab", perm, 8); 762 #endif 763 init_perm(PC2ROT[j], perm, 8, 8); 764 } 765 766 /* 767 * Bit reverse, then initial permutation, then expansion. 768 */ 769 for (i = 0; i < 8; i++) { 770 for (j = 0; j < 8; j++) { 771 k = (j < 2)? 0: IP[ExpandTr[i*6+j-2]-1]; 772 if (k > 32) 773 k -= 32; 774 else if (k > 0) 775 k--; 776 if (k > 0) { 777 k--; 778 k = (k|07) - (k&07); 779 k++; 780 } 781 perm[i*8+j] = k; 782 } 783 } 784 #ifdef DEBUG 785 prtab("ietab", perm, 8); 786 #endif 787 init_perm(IE3264, perm, 4, 8); 788 789 /* 790 * Compression, then final permutation, then bit reverse. 791 */ 792 for (i = 0; i < 64; i++) { 793 k = IP[CIFP[i]-1]; 794 if (k > 0) { 795 k--; 796 k = (k|07) - (k&07); 797 k++; 798 } 799 perm[k-1] = i+1; 800 } 801 #ifdef DEBUG 802 prtab("cftab", perm, 8); 803 #endif 804 init_perm(CF6464, perm, 8, 8); 805 806 /* 807 * SPE table 808 */ 809 for (i = 0; i < 48; i++) 810 perm[i] = P32Tr[ExpandTr[i]-1]; 811 for (tableno = 0; tableno < 8; tableno++) { 812 for (j = 0; j < 64; j++) { 813 k = (((j >> 0) &01) << 5)| 814 (((j >> 1) &01) << 3)| 815 (((j >> 2) &01) << 2)| 816 (((j >> 3) &01) << 1)| 817 (((j >> 4) &01) << 0)| 818 (((j >> 5) &01) << 4); 819 k = S[tableno][k]; 820 k = (((k >> 3)&01) << 0)| 821 (((k >> 2)&01) << 1)| 822 (((k >> 1)&01) << 2)| 823 (((k >> 0)&01) << 3); 824 for (i = 0; i < 32; i++) 825 tmp32[i] = 0; 826 for (i = 0; i < 4; i++) 827 tmp32[4 * tableno + i] = (k >> i) & 01; 828 k = 0; 829 for (i = 24; --i >= 0; ) 830 k = (k<<1) | tmp32[perm[i]-1]; 831 TO_SIX_BIT(SPE[0][tableno][j], k); 832 k = 0; 833 for (i = 24; --i >= 0; ) 834 k = (k<<1) | tmp32[perm[i+24]-1]; 835 TO_SIX_BIT(SPE[1][tableno][j], k); 836 } 837 } 838 } 839 840 /* 841 * Initialize "perm" to represent transformation "p", which rearranges 842 * (perhaps with expansion and/or contraction) one packed array of bits 843 * (of size "chars_in" characters) into another array (of size "chars_out" 844 * characters). 845 * 846 * "perm" must be all-zeroes on entry to this routine. 847 */ 848 STATIC 849 init_perm(perm, p, chars_in, chars_out) 850 C_block perm[64/CHUNKBITS][1<<CHUNKBITS]; 851 unsigned char p[64]; 852 int chars_in, chars_out; 853 { 854 register int i, j, k, l; 855 856 for (k = 0; k < chars_out*8; k++) { /* each output bit position */ 857 l = p[k] - 1; /* where this bit comes from */ 858 if (l < 0) 859 continue; /* output bit is always 0 */ 860 i = l>>LGCHUNKBITS; /* which chunk this bit comes from */ 861 l = 1<<(l&(CHUNKBITS-1)); /* mask for this bit */ 862 for (j = 0; j < (1<<CHUNKBITS); j++) { /* each chunk value */ 863 if ((j & l) != 0) 864 perm[i][j].b[k>>3] |= 1<<(k&07); 865 } 866 } 867 } 868 869 /* 870 * "setkey" routine (for backwards compatibility) 871 */ 872 void 873 setkey(key) 874 register const char *key; 875 { 876 register int i, j, k; 877 C_block keyblock; 878 879 for (i = 0; i < 8; i++) { 880 k = 0; 881 for (j = 0; j < 8; j++) { 882 k <<= 1; 883 k |= (unsigned char)*key++; 884 } 885 keyblock.b[i] = k; 886 } 887 des_setkey((char *)keyblock.b); 888 } 889 890 /* 891 * "encrypt" routine (for backwards compatibility) 892 */ 893 void 894 encrypt(block, flag) 895 register char *block; 896 int flag; 897 { 898 register int i, j, k; 899 C_block cblock; 900 901 for (i = 0; i < 8; i++) { 902 k = 0; 903 for (j = 0; j < 8; j++) { 904 k <<= 1; 905 k |= (unsigned char)*block++; 906 } 907 cblock.b[i] = k; 908 } 909 des_cipher((char *)&cblock, (char *)&cblock, 0L, (flag? -1: 1)); 910 for (i = 7; i >= 0; i--) { 911 k = cblock.b[i]; 912 for (j = 7; j >= 0; j--) { 913 *--block = k&01; 914 k >>= 1; 915 } 916 } 917 } 918 919 #ifdef DEBUG 920 STATIC 921 prtab(s, t, num_rows) 922 char *s; 923 unsigned char *t; 924 int num_rows; 925 { 926 register int i, j; 927 928 (void)printf("%s:\n", s); 929 for (i = 0; i < num_rows; i++) { 930 for (j = 0; j < 8; j++) { 931 (void)printf("%3d", t[i*8+j]); 932 } 933 (void)printf("\n"); 934 } 935 (void)printf("\n"); 936 } 937 #endif 938