Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

des.cpp

00001 // des.cpp - modified by Wei Dai from Phil Karn's des.c
00002 // The original code and all modifications are in the public domain.
00003 
00004 /*
00005  * This is a major rewrite of my old public domain DES code written
00006  * circa 1987, which in turn borrowed heavily from Jim Gillogly's 1977
00007  * public domain code. I pretty much kept my key scheduling code, but
00008  * the actual encrypt/decrypt routines are taken from from Richard
00009  * Outerbridge's DES code as printed in Schneier's "Applied Cryptography."
00010  *
00011  * This code is in the public domain. I would appreciate bug reports and
00012  * enhancements.
00013  *
00014  * Phil Karn KA9Q, karn@unix.ka9q.ampr.org, August 1994.
00015  */
00016 
00017 #include "pch.h"
00018 #include "misc.h"
00019 #include "des.h"
00020 
00021 NAMESPACE_BEGIN(CryptoPP)
00022 
00023 typedef BlockGetAndPut<word32, BigEndian> Block;
00024 
00025 // Richard Outerbridge's initial permutation algorithm
00026 /*
00027 inline void IPERM(word32 &left, word32 &right)
00028 {
00029         word32 work;
00030 
00031         work = ((left >> 4) ^ right) & 0x0f0f0f0f;
00032         right ^= work;
00033         left ^= work << 4;
00034         work = ((left >> 16) ^ right) & 0xffff;
00035         right ^= work;
00036         left ^= work << 16;
00037         work = ((right >> 2) ^ left) & 0x33333333;
00038         left ^= work;
00039         right ^= (work << 2);
00040         work = ((right >> 8) ^ left) & 0xff00ff;
00041         left ^= work;
00042         right ^= (work << 8);
00043         right = rotl(right, 1);
00044         work = (left ^ right) & 0xaaaaaaaa;
00045         left ^= work;
00046         right ^= work;
00047         left = rotl(left, 1);
00048 }
00049 inline void FPERM(word32 &left, word32 &right)
00050 {
00051         word32 work;
00052 
00053         right = rotr(right, 1);
00054         work = (left ^ right) & 0xaaaaaaaa;
00055         left ^= work;
00056         right ^= work;
00057         left = rotr(left, 1);
00058         work = ((left >> 8) ^ right) & 0xff00ff;
00059         right ^= work;
00060         left ^= work << 8;
00061         work = ((left >> 2) ^ right) & 0x33333333;
00062         right ^= work;
00063         left ^= work << 2;
00064         work = ((right >> 16) ^ left) & 0xffff;
00065         left ^= work;
00066         right ^= work << 16;
00067         work = ((right >> 4) ^ left) & 0x0f0f0f0f;
00068         left ^= work;
00069         right ^= work << 4;
00070 }
00071 */
00072 
00073 // Wei Dai's modification to Richard Outerbridge's initial permutation 
00074 // algorithm, this one is faster if you have access to rotate instructions 
00075 // (like in MSVC)
00076 static inline void IPERM(word32 &left, word32 &right)
00077 {
00078         word32 work;
00079 
00080         right = rotlFixed(right, 4U);
00081         work = (left ^ right) & 0xf0f0f0f0;
00082         left ^= work;
00083         right = rotrFixed(right^work, 20U);
00084         work = (left ^ right) & 0xffff0000;
00085         left ^= work;
00086         right = rotrFixed(right^work, 18U);
00087         work = (left ^ right) & 0x33333333;
00088         left ^= work;
00089         right = rotrFixed(right^work, 6U);
00090         work = (left ^ right) & 0x00ff00ff;
00091         left ^= work;
00092         right = rotlFixed(right^work, 9U);
00093         work = (left ^ right) & 0xaaaaaaaa;
00094         left = rotlFixed(left^work, 1U);
00095         right ^= work;
00096 }
00097 
00098 static inline void FPERM(word32 &left, word32 &right)
00099 {
00100         word32 work;
00101 
00102         right = rotrFixed(right, 1U);
00103         work = (left ^ right) & 0xaaaaaaaa;
00104         right ^= work;
00105         left = rotrFixed(left^work, 9U);
00106         work = (left ^ right) & 0x00ff00ff;
00107         right ^= work;
00108         left = rotlFixed(left^work, 6U);
00109         work = (left ^ right) & 0x33333333;
00110         right ^= work;
00111         left = rotlFixed(left^work, 18U);
00112         work = (left ^ right) & 0xffff0000;
00113         right ^= work;
00114         left = rotlFixed(left^work, 20U);
00115         work = (left ^ right) & 0xf0f0f0f0;
00116         right ^= work;
00117         left = rotrFixed(left^work, 4U);
00118 }
00119 
00120 #ifndef CRYPTOPP_IMPORTS
00121 
00122 /* Tables defined in the Data Encryption Standard documents
00123  * Three of these tables, the initial permutation, the final
00124  * permutation and the expansion operator, are regular enough that
00125  * for speed, we hard-code them. They're here for reference only.
00126  * Also, the S and P boxes are used by a separate program, gensp.c,
00127  * to build the combined SP box, Spbox[]. They're also here just
00128  * for reference.
00129  */
00130 #ifdef notdef
00131 /* initial permutation IP */
00132 static byte ip[] = {
00133            58, 50, 42, 34, 26, 18, 10,  2,
00134            60, 52, 44, 36, 28, 20, 12,  4,
00135            62, 54, 46, 38, 30, 22, 14,  6,
00136            64, 56, 48, 40, 32, 24, 16,  8,
00137            57, 49, 41, 33, 25, 17,  9,  1,
00138            59, 51, 43, 35, 27, 19, 11,  3,
00139            61, 53, 45, 37, 29, 21, 13,  5,
00140            63, 55, 47, 39, 31, 23, 15,  7
00141 };
00142 
00143 /* final permutation IP^-1 */
00144 static byte fp[] = {
00145            40,  8, 48, 16, 56, 24, 64, 32,
00146            39,  7, 47, 15, 55, 23, 63, 31,
00147            38,  6, 46, 14, 54, 22, 62, 30,
00148            37,  5, 45, 13, 53, 21, 61, 29,
00149            36,  4, 44, 12, 52, 20, 60, 28,
00150            35,  3, 43, 11, 51, 19, 59, 27,
00151            34,  2, 42, 10, 50, 18, 58, 26,
00152            33,  1, 41,  9, 49, 17, 57, 25
00153 };
00154 /* expansion operation matrix */
00155 static byte ei[] = {
00156            32,  1,  2,  3,  4,  5,
00157                 4,  5,  6,  7,  8,  9,
00158                 8,  9, 10, 11, 12, 13,
00159            12, 13, 14, 15, 16, 17,
00160            16, 17, 18, 19, 20, 21,
00161            20, 21, 22, 23, 24, 25,
00162            24, 25, 26, 27, 28, 29,
00163            28, 29, 30, 31, 32,  1
00164 };
00165 /* The (in)famous S-boxes */
00166 static byte sbox[8][64] = {
00167            /* S1 */
00168            14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7,
00169                 0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8,
00170                 4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0,
00171            15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13,
00172 
00173            /* S2 */
00174            15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10,
00175                 3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5,
00176                 0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15,
00177            13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9,
00178 
00179            /* S3 */
00180            10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8,
00181            13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1,
00182            13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7,
00183                 1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12,
00184 
00185            /* S4 */
00186                 7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15,
00187            13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9,
00188            10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4,
00189                 3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14,
00190 
00191            /* S5 */
00192                 2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9,
00193            14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6,
00194                 4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14,
00195            11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3,
00196 
00197            /* S6 */
00198            12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11,
00199            10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8,
00200                 9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6,
00201                 4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13,
00202 
00203            /* S7 */
00204                 4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1,
00205            13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6,
00206                 1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2,
00207                 6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12,
00208 
00209            /* S8 */
00210            13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7,
00211                 1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2,
00212                 7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8,
00213                 2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11
00214 };
00215 
00216 /* 32-bit permutation function P used on the output of the S-boxes */
00217 static byte p32i[] = {
00218            16,  7, 20, 21,
00219            29, 12, 28, 17,
00220                 1, 15, 23, 26,
00221                 5, 18, 31, 10,
00222                 2,  8, 24, 14,
00223            32, 27,  3,  9,
00224            19, 13, 30,  6,
00225            22, 11,  4, 25
00226 };
00227 #endif
00228 
00229 /* permuted choice table (key) */
00230 static const byte pc1[] = {
00231            57, 49, 41, 33, 25, 17,  9,
00232                 1, 58, 50, 42, 34, 26, 18,
00233            10,  2, 59, 51, 43, 35, 27,
00234            19, 11,  3, 60, 52, 44, 36,
00235 
00236            63, 55, 47, 39, 31, 23, 15,
00237                 7, 62, 54, 46, 38, 30, 22,
00238            14,  6, 61, 53, 45, 37, 29,
00239            21, 13,  5, 28, 20, 12,  4
00240 };
00241 
00242 /* number left rotations of pc1 */
00243 static const byte totrot[] = {
00244            1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
00245 };
00246 
00247 /* permuted choice key (table) */
00248 static const byte pc2[] = {
00249            14, 17, 11, 24,  1,  5,
00250                 3, 28, 15,  6, 21, 10,
00251            23, 19, 12,  4, 26,  8,
00252            16,  7, 27, 20, 13,  2,
00253            41, 52, 31, 37, 47, 55,
00254            30, 40, 51, 45, 33, 48,
00255            44, 49, 39, 56, 34, 53,
00256            46, 42, 50, 36, 29, 32
00257 };
00258 
00259 /* End of DES-defined tables */
00260 
00261 /* bit 0 is left-most in byte */
00262 static const int bytebit[] = {
00263            0200,0100,040,020,010,04,02,01
00264 };
00265 
00266 /* Set key (initialize key schedule array) */
00267 void RawDES::UncheckedSetKey(CipherDir dir, const byte *key, unsigned int length)
00268 {
00269         SecByteBlock buffer(56+56+8);
00270         byte *const pc1m=buffer;                 /* place to modify pc1 into */
00271         byte *const pcr=pc1m+56;                 /* place to rotate pc1 into */
00272         byte *const ks=pcr+56;
00273         register int i,j,l;
00274         int m;
00275         
00276         for (j=0; j<56; j++) {          /* convert pc1 to bits of key */
00277                 l=pc1[j]-1;             /* integer bit location  */
00278                 m = l & 07;             /* find bit              */
00279                 pc1m[j]=(key[l>>3] &    /* find which key byte l is in */
00280                         bytebit[m])     /* and which bit of that byte */
00281                         ? 1 : 0;        /* and store 1-bit result */
00282         }
00283         for (i=0; i<16; i++) {          /* key chunk for each iteration */
00284                 memset(ks,0,8);         /* Clear key schedule */
00285                 for (j=0; j<56; j++)    /* rotate pc1 the right amount */
00286                         pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
00287                 /* rotate left and right halves independently */
00288                 for (j=0; j<48; j++){   /* select bits individually */
00289                         /* check bit that goes to ks[j] */
00290                         if (pcr[pc2[j]-1]){
00291                                 /* mask it in if it's there */
00292                                 l= j % 6;
00293                                 ks[j/6] |= bytebit[l] >> 2;
00294                         }
00295                 }
00296                 /* Now convert to odd/even interleaved form for use in F */
00297                 k[2*i] = ((word32)ks[0] << 24)
00298                         | ((word32)ks[2] << 16)
00299                         | ((word32)ks[4] << 8)
00300                         | ((word32)ks[6]);
00301                 k[2*i+1] = ((word32)ks[1] << 24)
00302                         | ((word32)ks[3] << 16)
00303                         | ((word32)ks[5] << 8)
00304                         | ((word32)ks[7]);
00305         }
00306         
00307         if (dir==DECRYPTION)     // reverse key schedule order
00308                 for (i=0; i<16; i+=2)
00309                 {
00310                         std::swap(k[i], k[32-2-i]);
00311                         std::swap(k[i+1], k[32-1-i]);
00312                 }
00313 }
00314 
00315 void RawDES::RawProcessBlock(word32 &l_, word32 &r_) const
00316 {
00317         word32 l = l_, r = r_;
00318         const word32 *kptr=k;
00319 
00320         for (unsigned i=0; i<8; i++)
00321         {
00322                 word32 work = rotrFixed(r, 4U) ^ kptr[4*i+0];
00323                 l ^= Spbox[6][(work) & 0x3f]
00324                   ^  Spbox[4][(work >> 8) & 0x3f]
00325                   ^  Spbox[2][(work >> 16) & 0x3f]
00326                   ^  Spbox[0][(work >> 24) & 0x3f];
00327                 work = r ^ kptr[4*i+1];
00328                 l ^= Spbox[7][(work) & 0x3f]
00329                   ^  Spbox[5][(work >> 8) & 0x3f]
00330                   ^  Spbox[3][(work >> 16) & 0x3f]
00331                   ^  Spbox[1][(work >> 24) & 0x3f];
00332 
00333                 work = rotrFixed(l, 4U) ^ kptr[4*i+2];
00334                 r ^= Spbox[6][(work) & 0x3f]
00335                   ^  Spbox[4][(work >> 8) & 0x3f]
00336                   ^  Spbox[2][(work >> 16) & 0x3f]
00337                   ^  Spbox[0][(work >> 24) & 0x3f];
00338                 work = l ^ kptr[4*i+3];
00339                 r ^= Spbox[7][(work) & 0x3f]
00340                   ^  Spbox[5][(work >> 8) & 0x3f]
00341                   ^  Spbox[3][(work >> 16) & 0x3f]
00342                   ^  Spbox[1][(work >> 24) & 0x3f];
00343         }
00344 
00345         l_ = l; r_ = r;
00346 }
00347 
00348 void DES_EDE2::Base::UncheckedSetKey(CipherDir dir, const byte *key, unsigned int length)
00349 {
00350         AssertValidKeyLength(length);
00351 
00352         m_des1.UncheckedSetKey(dir, key);
00353         m_des2.UncheckedSetKey(ReverseCipherDir(dir), key+8);
00354 }
00355 
00356 void DES_EDE2::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
00357 {
00358         word32 l,r;
00359         Block::Get(inBlock)(l)(r);
00360         IPERM(l,r);
00361         m_des1.RawProcessBlock(l, r);
00362         m_des2.RawProcessBlock(r, l);
00363         m_des1.RawProcessBlock(l, r);
00364         FPERM(l,r);
00365         Block::Put(xorBlock, outBlock)(r)(l);
00366 }
00367 
00368 void DES_EDE3::Base::UncheckedSetKey(CipherDir dir, const byte *key, unsigned int length)
00369 {
00370         AssertValidKeyLength(length);
00371 
00372         m_des1.UncheckedSetKey(dir, key+(dir==ENCRYPTION?0:2*8));
00373         m_des2.UncheckedSetKey(ReverseCipherDir(dir), key+8);
00374         m_des3.UncheckedSetKey(dir, key+(dir==DECRYPTION?0:2*8));
00375 }
00376 
00377 void DES_EDE3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
00378 {
00379         word32 l,r;
00380         Block::Get(inBlock)(l)(r);
00381         IPERM(l,r);
00382         m_des1.RawProcessBlock(l, r);
00383         m_des2.RawProcessBlock(r, l);
00384         m_des3.RawProcessBlock(l, r);
00385         FPERM(l,r);
00386         Block::Put(xorBlock, outBlock)(r)(l);
00387 }
00388 
00389 #endif  // #ifndef CRYPTOPP_IMPORTS
00390 
00391 static inline bool CheckParity(byte b)
00392 {
00393         unsigned int a = b ^ (b >> 4);
00394         return ((a ^ (a>>1) ^ (a>>2) ^ (a>>3)) & 1) == 1;
00395 }
00396 
00397 bool DES::CheckKeyParityBits(const byte *key)
00398 {
00399         for (unsigned int i=0; i<8; i++)
00400                 if (!CheckParity(key[i]))
00401                         return false;
00402         return true;
00403 }
00404 
00405 void DES::CorrectKeyParityBits(byte *key)
00406 {
00407         for (unsigned int i=0; i<8; i++)
00408                 if (!CheckParity(key[i]))
00409                         key[i] ^= 1;
00410 }
00411 
00412 // Encrypt or decrypt a block of data in ECB mode
00413 void DES::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
00414 {
00415         word32 l,r;
00416         Block::Get(inBlock)(l)(r);
00417         IPERM(l,r);
00418         RawProcessBlock(l, r);
00419         FPERM(l,r);
00420         Block::Put(xorBlock, outBlock)(r)(l);
00421 }
00422 
00423 void DES_XEX3::Base::UncheckedSetKey(CipherDir dir, const byte *key, unsigned int length)
00424 {
00425         AssertValidKeyLength(length);
00426 
00427         memcpy(m_x1, key+(dir==ENCRYPTION?0:2*8), BLOCKSIZE);
00428         m_des.UncheckedSetKey(dir, key+8);
00429         memcpy(m_x3, key+(dir==DECRYPTION?0:2*8), BLOCKSIZE);
00430 }
00431 
00432 void DES_XEX3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
00433 {
00434         xorbuf(outBlock, inBlock, m_x1, BLOCKSIZE);
00435         m_des.ProcessAndXorBlock(outBlock, xorBlock, outBlock);
00436         xorbuf(outBlock, m_x3, BLOCKSIZE);
00437 }
00438 
00439 NAMESPACE_END

Generated on Wed Nov 17 21:26:06 2004 for Crypto++ by  doxygen 1.3.9.1