kio Library API Documentation

des.cpp

00001 00002 /* Sofware DES functions 00003 * written 12 Dec 1986 by Phil Karn, KA9Q; large sections adapted from 00004 * the 1977 public-domain program by Jim Gillogly 00005 * Modified for additional speed - 6 December 1988 Phil Karn 00006 * Modified for parameterized key schedules - Jan 1991 Phil Karn 00007 * Callers now allocate a key schedule as follows: 00008 * kn = (char (*)[8])malloc(sizeof(char) * 8 * 16); 00009 * or 00010 * char kn[16][8]; 00011 */ 00012 00013 /* modified in order to use the libmcrypt API by Nikos Mavroyanopoulos 00014 * All modifications are placed under the license of libmcrypt. 00015 */ 00016 00017 /* $Id: des.cpp,v 1.1 2004/11/04 21:05:13 gyurco Exp $ */ 00018 00019 #include <string.h> 00020 #include <kswap.h> 00021 #include "des.h" 00022 00023 static void permute_ip (unsigned char *inblock, DES_KEY * key, unsigned char *outblock); 00024 static void permute_fp (unsigned char *inblock, DES_KEY * key, unsigned char *outblock); 00025 static void perminit_ip (DES_KEY * key); 00026 static void spinit (DES_KEY * key); 00027 static void perminit_fp (DES_KEY * key); 00028 static Q_UINT32 f (DES_KEY * key, Q_UINT32 r, char *subkey); 00029 00030 00031 /* Tables defined in the Data Encryption Standard documents */ 00032 00033 /* initial permutation IP */ 00034 static const char ip[] = { 00035 58, 50, 42, 34, 26, 18, 10, 2, 00036 60, 52, 44, 36, 28, 20, 12, 4, 00037 62, 54, 46, 38, 30, 22, 14, 6, 00038 64, 56, 48, 40, 32, 24, 16, 8, 00039 57, 49, 41, 33, 25, 17, 9, 1, 00040 59, 51, 43, 35, 27, 19, 11, 3, 00041 61, 53, 45, 37, 29, 21, 13, 5, 00042 63, 55, 47, 39, 31, 23, 15, 7 00043 }; 00044 00045 /* final permutation IP^-1 */ 00046 static const char fp[] = { 00047 40, 8, 48, 16, 56, 24, 64, 32, 00048 39, 7, 47, 15, 55, 23, 63, 31, 00049 38, 6, 46, 14, 54, 22, 62, 30, 00050 37, 5, 45, 13, 53, 21, 61, 29, 00051 36, 4, 44, 12, 52, 20, 60, 28, 00052 35, 3, 43, 11, 51, 19, 59, 27, 00053 34, 2, 42, 10, 50, 18, 58, 26, 00054 33, 1, 41, 9, 49, 17, 57, 25 00055 }; 00056 00057 /* expansion operation matrix 00058 * This is for reference only; it is unused in the code 00059 * as the f() function performs it implicitly for speed 00060 */ 00061 #ifdef notdef 00062 static const char ei[] = { 00063 32, 1, 2, 3, 4, 5, 00064 4, 5, 6, 7, 8, 9, 00065 8, 9, 10, 11, 12, 13, 00066 12, 13, 14, 15, 16, 17, 00067 16, 17, 18, 19, 20, 21, 00068 20, 21, 22, 23, 24, 25, 00069 24, 25, 26, 27, 28, 29, 00070 28, 29, 30, 31, 32, 1 00071 }; 00072 #endif 00073 00074 /* permuted choice table (key) */ 00075 static const char pc1[] = { 00076 57, 49, 41, 33, 25, 17, 9, 00077 1, 58, 50, 42, 34, 26, 18, 00078 10, 2, 59, 51, 43, 35, 27, 00079 19, 11, 3, 60, 52, 44, 36, 00080 00081 63, 55, 47, 39, 31, 23, 15, 00082 7, 62, 54, 46, 38, 30, 22, 00083 14, 6, 61, 53, 45, 37, 29, 00084 21, 13, 5, 28, 20, 12, 4 00085 }; 00086 00087 /* number left rotations of pc1 */ 00088 static const char totrot[] = { 00089 1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28 00090 }; 00091 00092 /* permuted choice key (table) */ 00093 static const char pc2[] = { 00094 14, 17, 11, 24, 1, 5, 00095 3, 28, 15, 6, 21, 10, 00096 23, 19, 12, 4, 26, 8, 00097 16, 7, 27, 20, 13, 2, 00098 41, 52, 31, 37, 47, 55, 00099 30, 40, 51, 45, 33, 48, 00100 44, 49, 39, 56, 34, 53, 00101 46, 42, 50, 36, 29, 32 00102 }; 00103 00104 /* The (in)famous S-boxes */ 00105 static const char si[8][64] = { 00106 /* S1 */ 00107 {14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7, 00108 0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8, 00109 4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0, 00110 15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13}, 00111 00112 /* S2 */ 00113 {15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10, 00114 3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5, 00115 0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15, 00116 13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9}, 00117 00118 /* S3 */ 00119 {10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8, 00120 13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1, 00121 13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7, 00122 1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12}, 00123 00124 /* S4 */ 00125 {7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15, 00126 13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9, 00127 10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4, 00128 3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14}, 00129 00130 /* S5 */ 00131 {2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9, 00132 14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6, 00133 4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14, 00134 11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3}, 00135 00136 /* S6 */ 00137 {12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11, 00138 10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8, 00139 9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6, 00140 4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13}, 00141 00142 /* S7 */ 00143 {4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1, 00144 13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6, 00145 1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2, 00146 6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12}, 00147 00148 /* S8 */ 00149 {13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7, 00150 1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2, 00151 7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8, 00152 2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11}, 00153 00154 }; 00155 00156 /* 32-bit permutation function P used on the output of the S-boxes */ 00157 static const char p32i[] = { 00158 16, 7, 20, 21, 00159 29, 12, 28, 17, 00160 1, 15, 23, 26, 00161 5, 18, 31, 10, 00162 2, 8, 24, 14, 00163 32, 27, 3, 9, 00164 19, 13, 30, 6, 00165 22, 11, 4, 25 00166 }; 00167 00168 /* End of DES-defined tables */ 00169 00170 /* Lookup tables initialized once only at startup by desinit() */ 00171 00172 /* bit 0 is left-most in byte */ 00173 static const int bytebit[] = { 00174 0200, 0100, 040, 020, 010, 04, 02, 01 00175 }; 00176 00177 static const int nibblebit[] = { 00178 010, 04, 02, 01 00179 }; 00180 00181 /* Allocate space and initialize DES lookup arrays 00182 * mode == 0: standard Data Encryption Algorithm 00183 */ 00184 static int 00185 desinit (DES_KEY * key) 00186 { 00187 00188 spinit (key); 00189 perminit_ip (key); 00190 perminit_fp (key); 00191 00192 return 0; 00193 } 00194 00195 00196 /* Set key (initialize key schedule array) */ 00197 int 00198 ntlm_des_set_key (DES_KEY * dkey, char *user_key, int len) 00199 { 00200 char pc1m[56]; /* place to modify pc1 into */ 00201 char pcr[56]; /* place to rotate pc1 into */ 00202 int i, j, l; 00203 int m; 00204 00205 memset(dkey, 0, sizeof (DES_KEY)); 00206 desinit (dkey); 00207 00208 /* Clear key schedule */ 00209 00210 00211 for (j = 0; j < 56; j++) 00212 { /* convert pc1 to bits of key */ 00213 l = pc1[j] - 1; /* integer bit location */ 00214 m = l & 07; /* find bit */ 00215 pc1m[j] = (user_key[l >> 3] & /* find which key byte l is in */ 00216 bytebit[m]) /* and which bit of that byte */ 00217 ? 1 : 0; /* and store 1-bit result */ 00218 00219 } 00220 for (i = 0; i < 16; i++) 00221 { /* key chunk for each iteration */ 00222 for (j = 0; j < 56; j++) /* rotate pc1 the right amount */ 00223 pcr[j] = pc1m[(l = j + totrot[i]) < (j < 28 ? 28 : 56) ? l : l - 28]; 00224 /* rotate left and right halves independently */ 00225 for (j = 0; j < 48; j++) 00226 { /* select bits individually */ 00227 /* check bit that goes to kn[j] */ 00228 if (pcr[pc2[j] - 1]) 00229 { 00230 /* mask it in if it's there */ 00231 l = j % 6; 00232 dkey->kn[i][j / 6] |= bytebit[l] >> 2; 00233 } 00234 } 00235 } 00236 return 0; 00237 } 00238 00239 /* In-place encryption of 64-bit block */ 00240 static void 00241 ntlm_des_encrypt (DES_KEY * key, unsigned char *block) 00242 { 00243 Q_UINT32 left, right; 00244 char *knp; 00245 Q_UINT32 work[2]; /* Working data storage */ 00246 00247 permute_ip (block, key, (unsigned char *) work); /* Initial Permutation */ 00248 left = KFromToBigEndian(work[0]); 00249 right = KFromToBigEndian(work[1]); 00250 00251 /* Do the 16 rounds. 00252 * The rounds are numbered from 0 to 15. On even rounds 00253 * the right half is fed to f() and the result exclusive-ORs 00254 * the left half; on odd rounds the reverse is done. 00255 */ 00256 knp = &key->kn[0][0]; 00257 left ^= f (key, right, knp); 00258 knp += 8; 00259 right ^= f (key, left, knp); 00260 knp += 8; 00261 left ^= f (key, right, knp); 00262 knp += 8; 00263 right ^= f (key, left, knp); 00264 knp += 8; 00265 left ^= f (key, right, knp); 00266 knp += 8; 00267 right ^= f (key, left, knp); 00268 knp += 8; 00269 left ^= f (key, right, knp); 00270 knp += 8; 00271 right ^= f (key, left, knp); 00272 knp += 8; 00273 left ^= f (key, right, knp); 00274 knp += 8; 00275 right ^= f (key, left, knp); 00276 knp += 8; 00277 left ^= f (key, right, knp); 00278 knp += 8; 00279 right ^= f (key, left, knp); 00280 knp += 8; 00281 left ^= f (key, right, knp); 00282 knp += 8; 00283 right ^= f (key, left, knp); 00284 knp += 8; 00285 left ^= f (key, right, knp); 00286 knp += 8; 00287 right ^= f (key, left, knp); 00288 00289 /* Left/right half swap, plus byte swap if little-endian */ 00290 work[1] = KFromToBigEndian( left ); 00291 work[0] = KFromToBigEndian( right ); 00292 00293 permute_fp ((unsigned char *) work, key, block); /* Inverse initial permutation */ 00294 } 00295 00296 /* Permute inblock with perm */ 00297 static void 00298 permute_ip (unsigned char *inblock, DES_KEY * key, unsigned char *outblock) 00299 { 00300 unsigned char *ib, *ob; /* ptr to input or output block */ 00301 char *p, *q; 00302 int j; 00303 00304 /* Clear output block */ 00305 memset(outblock, 0, 8); 00306 00307 ib = inblock; 00308 for (j = 0; j < 16; j += 2, ib++) 00309 { /* for each input nibble */ 00310 ob = outblock; 00311 p = key->iperm[j][(*ib >> 4) & 0xf]; 00312 q = key->iperm[j + 1][*ib & 0xf]; 00313 /* and each output byte, OR the masks together */ 00314 *ob++ |= *p++ | *q++; 00315 *ob++ |= *p++ | *q++; 00316 *ob++ |= *p++ | *q++; 00317 *ob++ |= *p++ | *q++; 00318 *ob++ |= *p++ | *q++; 00319 *ob++ |= *p++ | *q++; 00320 *ob++ |= *p++ | *q++; 00321 *ob++ |= *p++ | *q++; 00322 } 00323 } 00324 00325 /* Permute inblock with perm */ 00326 static void 00327 permute_fp (unsigned char *inblock, DES_KEY * key, unsigned char *outblock) 00328 { 00329 unsigned char *ib, *ob; /* ptr to input or output block */ 00330 char *p, *q; 00331 int j; 00332 00333 /* Clear output block */ 00334 memset(outblock, 0, 8); 00335 00336 ib = inblock; 00337 for (j = 0; j < 16; j += 2, ib++) 00338 { /* for each input nibble */ 00339 ob = outblock; 00340 p = key->fperm[j][(*ib >> 4) & 0xf]; 00341 q = key->fperm[j + 1][*ib & 0xf]; 00342 /* and each output byte, OR the masks together */ 00343 *ob++ |= *p++ | *q++; 00344 *ob++ |= *p++ | *q++; 00345 *ob++ |= *p++ | *q++; 00346 *ob++ |= *p++ | *q++; 00347 *ob++ |= *p++ | *q++; 00348 *ob++ |= *p++ | *q++; 00349 *ob++ |= *p++ | *q++; 00350 *ob++ |= *p++ | *q++; 00351 } 00352 } 00353 00354 /* The nonlinear function f(r,k), the heart of DES */ 00355 static Q_UINT32 00356 f (DES_KEY * key, Q_UINT32 r, char *subkey) 00357 { 00358 Q_UINT32 *spp; 00359 Q_UINT32 rval, rt; 00360 int er; 00361 00362 #ifdef TRACE 00363 printf ("f(%08lx, %02x %02x %02x %02x %02x %02x %02x %02x) = ", 00364 r, 00365 subkey[0], subkey[1], subkey[2], 00366 subkey[3], subkey[4], subkey[5], subkey[6], subkey[7]); 00367 #endif 00368 /* Run E(R) ^ K through the combined S & P boxes. 00369 * This code takes advantage of a convenient regularity in 00370 * E, namely that each group of 6 bits in E(R) feeding 00371 * a single S-box is a contiguous segment of R. 00372 */ 00373 subkey += 7; 00374 00375 /* Compute E(R) for each block of 6 bits, and run thru boxes */ 00376 er = ((int) r << 1) | ((r & 0x80000000) ? 1 : 0); 00377 spp = &key->sp[7][0]; 00378 rval = spp[(er ^ *subkey--) & 0x3f]; 00379 spp -= 64; 00380 rt = (Q_UINT32) r >> 3; 00381 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 00382 spp -= 64; 00383 rt >>= 4; 00384 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 00385 spp -= 64; 00386 rt >>= 4; 00387 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 00388 spp -= 64; 00389 rt >>= 4; 00390 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 00391 spp -= 64; 00392 rt >>= 4; 00393 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 00394 spp -= 64; 00395 rt >>= 4; 00396 rval |= spp[((int) rt ^ *subkey--) & 0x3f]; 00397 spp -= 64; 00398 rt >>= 4; 00399 rt |= (r & 1) << 5; 00400 rval |= spp[((int) rt ^ *subkey) & 0x3f]; 00401 #ifdef TRACE 00402 printf (" %08lx\n", rval); 00403 #endif 00404 return rval; 00405 } 00406 00407 /* initialize a perm array */ 00408 static void 00409 perminit_ip (DES_KEY * key) 00410 { 00411 int l, j, k; 00412 int i, m; 00413 00414 /* Clear the permutation array */ 00415 memset(key->iperm, 0, 16 * 16 * 8); 00416 00417 for (i = 0; i < 16; i++) /* each input nibble position */ 00418 for (j = 0; j < 16; j++) /* each possible input nibble */ 00419 for (k = 0; k < 64; k++) 00420 { /* each output bit position */ 00421 l = ip[k] - 1; /* where does this bit come from */ 00422 if ((l >> 2) != i) /* does it come from input posn? */ 00423 continue; /* if not, bit k is 0 */ 00424 if (!(j & nibblebit[l & 3])) 00425 continue; /* any such bit in input? */ 00426 m = k & 07; /* which bit is this in the byte */ 00427 key->iperm[i][j][k >> 3] |= bytebit[m]; 00428 } 00429 } 00430 00431 static void 00432 perminit_fp (DES_KEY * key) 00433 { 00434 int l, j, k; 00435 int i, m; 00436 00437 /* Clear the permutation array */ 00438 memset(key->fperm, 0, 16 * 16 * 8); 00439 00440 for (i = 0; i < 16; i++) /* each input nibble position */ 00441 for (j = 0; j < 16; j++) /* each possible input nibble */ 00442 for (k = 0; k < 64; k++) 00443 { /* each output bit position */ 00444 l = fp[k] - 1; /* where does this bit come from */ 00445 if ((l >> 2) != i) /* does it come from input posn? */ 00446 continue; /* if not, bit k is 0 */ 00447 if (!(j & nibblebit[l & 3])) 00448 continue; /* any such bit in input? */ 00449 m = k & 07; /* which bit is this in the byte */ 00450 key->fperm[i][j][k >> 3] |= bytebit[m]; 00451 } 00452 } 00453 00454 /* Initialize the lookup table for the combined S and P boxes */ 00455 static void 00456 spinit (DES_KEY * key) 00457 { 00458 char pbox[32]; 00459 int p, i, s, j, rowcol; 00460 Q_UINT32 val; 00461 00462 /* Compute pbox, the inverse of p32i. 00463 * This is easier to work with 00464 */ 00465 for (p = 0; p < 32; p++) 00466 { 00467 for (i = 0; i < 32; i++) 00468 { 00469 if (p32i[i] - 1 == p) 00470 { 00471 pbox[p] = i; 00472 break; 00473 } 00474 } 00475 } 00476 for (s = 0; s < 8; s++) 00477 { /* For each S-box */ 00478 for (i = 0; i < 64; i++) 00479 { /* For each possible input */ 00480 val = 0; 00481 /* The row number is formed from the first and last 00482 * bits; the column number is from the middle 4 00483 */ 00484 rowcol = (i & 32) | ((i & 1) ? 16 : 0) | ((i >> 1) & 0xf); 00485 for (j = 0; j < 4; j++) 00486 { /* For each output bit */ 00487 if (si[s][rowcol] & (8 >> j)) 00488 { 00489 val |= 1L << (31 - pbox[4 * s + j]); 00490 } 00491 } 00492 key->sp[s][i] = val; 00493 } 00494 } 00495 } 00496 00497 int 00498 ntlm_des_ecb_encrypt (const void *plaintext, int len, DES_KEY * akey, 00499 unsigned char output[8]) 00500 { 00501 int j; 00502 const unsigned char *plain = (const unsigned char *) plaintext; 00503 00504 for (j = 0; j < len / 8; j++) 00505 { 00506 memcpy (&output[j * 8], &plain[j * 8], 8); 00507 ntlm_des_encrypt (akey, &output[j * 8]); 00508 } 00509 00510 if (j == 0 && len != 0) 00511 return -1; /* no blocks were encrypted */ 00512 return 0; 00513 }
KDE Logo
This file is part of the documentation for kio Library Version 3.4.0.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Thu Apr 14 00:20:18 2005 by doxygen 1.3.7 written by Dimitri van Heesch, © 1997-2003