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 Wed Jul 28 08:07:06 2004 for Crypto++ by doxygen 1.3.7