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

Generated on Sun Mar 14 20:44:25 2004 for Crypto++ by doxygen 1.3.6-20040222