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