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 Fri Aug 27 16:09:15 2004 for Crypto++ by doxygen 1.3.8