Crypto++  5.6.4
Free C++ class library of cryptographic schemes
des.cpp
1 // des.cpp - modified by Wei Dai from Phil Karn's des.c
2 // The original code and all modifications are in the public domain.
3 
4 /*
5  * This is a major rewrite of my old public domain DES code written
6  * circa 1987, which in turn borrowed heavily from Jim Gillogly's 1977
7  * public domain code. I pretty much kept my key scheduling code, but
8  * the actual encrypt/decrypt routines are taken from from Richard
9  * Outerbridge's DES code as printed in Schneier's "Applied Cryptography."
10  *
11  * This code is in the public domain. I would appreciate bug reports and
12  * enhancements.
13  *
14  * Phil Karn KA9Q, karn@unix.ka9q.ampr.org, August 1994.
15  */
16 
17 #include "pch.h"
18 #include "misc.h"
19 #include "des.h"
20 
21 NAMESPACE_BEGIN(CryptoPP)
22 
23 typedef BlockGetAndPut<word32, BigEndian> Block;
24 
25 // Richard Outerbridge's initial permutation algorithm
26 /*
27 inline void IPERM(word32 &left, word32 &right)
28 {
29  word32 work;
30 
31  work = ((left >> 4) ^ right) & 0x0f0f0f0f;
32  right ^= work;
33  left ^= work << 4;
34  work = ((left >> 16) ^ right) & 0xffff;
35  right ^= work;
36  left ^= work << 16;
37  work = ((right >> 2) ^ left) & 0x33333333;
38  left ^= work;
39  right ^= (work << 2);
40  work = ((right >> 8) ^ left) & 0xff00ff;
41  left ^= work;
42  right ^= (work << 8);
43  right = rotl(right, 1);
44  work = (left ^ right) & 0xaaaaaaaa;
45  left ^= work;
46  right ^= work;
47  left = rotl(left, 1);
48 }
49 inline void FPERM(word32 &left, word32 &right)
50 {
51  word32 work;
52 
53  right = rotr(right, 1);
54  work = (left ^ right) & 0xaaaaaaaa;
55  left ^= work;
56  right ^= work;
57  left = rotr(left, 1);
58  work = ((left >> 8) ^ right) & 0xff00ff;
59  right ^= work;
60  left ^= work << 8;
61  work = ((left >> 2) ^ right) & 0x33333333;
62  right ^= work;
63  left ^= work << 2;
64  work = ((right >> 16) ^ left) & 0xffff;
65  left ^= work;
66  right ^= work << 16;
67  work = ((right >> 4) ^ left) & 0x0f0f0f0f;
68  left ^= work;
69  right ^= work << 4;
70 }
71 */
72 
73 // Wei Dai's modification to Richard Outerbridge's initial permutation
74 // algorithm, this one is faster if you have access to rotate instructions
75 // (like in MSVC)
76 static inline void IPERM(word32 &left, word32 &right)
77 {
78  word32 work;
79 
80  right = rotlFixed(right, 4U);
81  work = (left ^ right) & 0xf0f0f0f0;
82  left ^= work;
83  right = rotrFixed(right^work, 20U);
84  work = (left ^ right) & 0xffff0000;
85  left ^= work;
86  right = rotrFixed(right^work, 18U);
87  work = (left ^ right) & 0x33333333;
88  left ^= work;
89  right = rotrFixed(right^work, 6U);
90  work = (left ^ right) & 0x00ff00ff;
91  left ^= work;
92  right = rotlFixed(right^work, 9U);
93  work = (left ^ right) & 0xaaaaaaaa;
94  left = rotlFixed(left^work, 1U);
95  right ^= work;
96 }
97 
98 static inline void FPERM(word32 &left, word32 &right)
99 {
100  word32 work;
101 
102  right = rotrFixed(right, 1U);
103  work = (left ^ right) & 0xaaaaaaaa;
104  right ^= work;
105  left = rotrFixed(left^work, 9U);
106  work = (left ^ right) & 0x00ff00ff;
107  right ^= work;
108  left = rotlFixed(left^work, 6U);
109  work = (left ^ right) & 0x33333333;
110  right ^= work;
111  left = rotlFixed(left^work, 18U);
112  work = (left ^ right) & 0xffff0000;
113  right ^= work;
114  left = rotlFixed(left^work, 20U);
115  work = (left ^ right) & 0xf0f0f0f0;
116  right ^= work;
117  left = rotrFixed(left^work, 4U);
118 }
119 
120 void DES::Base::UncheckedSetKey(const byte *userKey, unsigned int length, const NameValuePairs &)
121 {
122  AssertValidKeyLength(length);
123 
124  RawSetKey(GetCipherDirection(), userKey);
125 }
126 
127 #ifndef CRYPTOPP_IMPORTS
128 
129 /* Tables defined in the Data Encryption Standard documents
130  * Three of these tables, the initial permutation, the final
131  * permutation and the expansion operator, are regular enough that
132  * for speed, we hard-code them. They're here for reference only.
133  * Also, the S and P boxes are used by a separate program, gensp.c,
134  * to build the combined SP box, Spbox[]. They're also here just
135  * for reference.
136  */
137 #ifdef notdef
138 /* initial permutation IP */
139 static byte ip[] = {
140  58, 50, 42, 34, 26, 18, 10, 2,
141  60, 52, 44, 36, 28, 20, 12, 4,
142  62, 54, 46, 38, 30, 22, 14, 6,
143  64, 56, 48, 40, 32, 24, 16, 8,
144  57, 49, 41, 33, 25, 17, 9, 1,
145  59, 51, 43, 35, 27, 19, 11, 3,
146  61, 53, 45, 37, 29, 21, 13, 5,
147  63, 55, 47, 39, 31, 23, 15, 7
148 };
149 
150 /* final permutation IP^-1 */
151 static byte fp[] = {
152  40, 8, 48, 16, 56, 24, 64, 32,
153  39, 7, 47, 15, 55, 23, 63, 31,
154  38, 6, 46, 14, 54, 22, 62, 30,
155  37, 5, 45, 13, 53, 21, 61, 29,
156  36, 4, 44, 12, 52, 20, 60, 28,
157  35, 3, 43, 11, 51, 19, 59, 27,
158  34, 2, 42, 10, 50, 18, 58, 26,
159  33, 1, 41, 9, 49, 17, 57, 25
160 };
161 /* expansion operation matrix */
162 static byte ei[] = {
163  32, 1, 2, 3, 4, 5,
164  4, 5, 6, 7, 8, 9,
165  8, 9, 10, 11, 12, 13,
166  12, 13, 14, 15, 16, 17,
167  16, 17, 18, 19, 20, 21,
168  20, 21, 22, 23, 24, 25,
169  24, 25, 26, 27, 28, 29,
170  28, 29, 30, 31, 32, 1
171 };
172 /* The (in)famous S-boxes */
173 static byte sbox[8][64] = {
174  /* S1 */
175  14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7,
176  0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8,
177  4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0,
178  15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13,
179 
180  /* S2 */
181  15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10,
182  3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5,
183  0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15,
184  13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9,
185 
186  /* S3 */
187  10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8,
188  13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1,
189  13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7,
190  1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12,
191 
192  /* S4 */
193  7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15,
194  13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9,
195  10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4,
196  3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14,
197 
198  /* S5 */
199  2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9,
200  14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6,
201  4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14,
202  11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3,
203 
204  /* S6 */
205  12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11,
206  10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8,
207  9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6,
208  4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13,
209 
210  /* S7 */
211  4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1,
212  13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6,
213  1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2,
214  6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12,
215 
216  /* S8 */
217  13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7,
218  1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2,
219  7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8,
220  2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11
221 };
222 
223 /* 32-bit permutation function P used on the output of the S-boxes */
224 static byte p32i[] = {
225  16, 7, 20, 21,
226  29, 12, 28, 17,
227  1, 15, 23, 26,
228  5, 18, 31, 10,
229  2, 8, 24, 14,
230  32, 27, 3, 9,
231  19, 13, 30, 6,
232  22, 11, 4, 25
233 };
234 #endif
235 
236 /* permuted choice table (key) */
237 static const byte pc1[] = {
238  57, 49, 41, 33, 25, 17, 9,
239  1, 58, 50, 42, 34, 26, 18,
240  10, 2, 59, 51, 43, 35, 27,
241  19, 11, 3, 60, 52, 44, 36,
242 
243  63, 55, 47, 39, 31, 23, 15,
244  7, 62, 54, 46, 38, 30, 22,
245  14, 6, 61, 53, 45, 37, 29,
246  21, 13, 5, 28, 20, 12, 4
247 };
248 
249 /* number left rotations of pc1 */
250 static const byte totrot[] = {
251  1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
252 };
253 
254 /* permuted choice key (table) */
255 static const byte pc2[] = {
256  14, 17, 11, 24, 1, 5,
257  3, 28, 15, 6, 21, 10,
258  23, 19, 12, 4, 26, 8,
259  16, 7, 27, 20, 13, 2,
260  41, 52, 31, 37, 47, 55,
261  30, 40, 51, 45, 33, 48,
262  44, 49, 39, 56, 34, 53,
263  46, 42, 50, 36, 29, 32
264 };
265 
266 /* End of DES-defined tables */
267 
268 /* bit 0 is left-most in byte */
269 static const int bytebit[] = {
270  0200,0100,040,020,010,04,02,01
271 };
272 
273 /* Set key (initialize key schedule array) */
274 void RawDES::RawSetKey(CipherDir dir, const byte *key)
275 {
276 #if (_MSC_VER >= 1600) || (__cplusplus >= 201103L)
277 # define register /* Define to nothing for C++11 and above */
278 #endif
279 
280  SecByteBlock buffer(56+56+8);
281  byte *const pc1m=buffer; /* place to modify pc1 into */
282  byte *const pcr=pc1m+56; /* place to rotate pc1 into */
283  byte *const ks=pcr+56;
284  register int i,j,l;
285  int m;
286 
287  for (j=0; j<56; j++) { /* convert pc1 to bits of key */
288  l=pc1[j]-1; /* integer bit location */
289  m = l & 07; /* find bit */
290  pc1m[j]=(key[l>>3] & /* find which key byte l is in */
291  bytebit[m]) /* and which bit of that byte */
292  ? 1 : 0; /* and store 1-bit result */
293  }
294  for (i=0; i<16; i++) { /* key chunk for each iteration */
295  memset(ks,0,8); /* Clear key schedule */
296  for (j=0; j<56; j++) /* rotate pc1 the right amount */
297  pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
298  /* rotate left and right halves independently */
299  for (j=0; j<48; j++){ /* select bits individually */
300  /* check bit that goes to ks[j] */
301  if (pcr[pc2[j]-1]){
302  /* mask it in if it's there */
303  l= j % 6;
304  ks[j/6] |= bytebit[l] >> 2;
305  }
306  }
307  /* Now convert to odd/even interleaved form for use in F */
308  k[2*i] = ((word32)ks[0] << 24)
309  | ((word32)ks[2] << 16)
310  | ((word32)ks[4] << 8)
311  | ((word32)ks[6]);
312  k[2*i+1] = ((word32)ks[1] << 24)
313  | ((word32)ks[3] << 16)
314  | ((word32)ks[5] << 8)
315  | ((word32)ks[7]);
316  }
317 
318  if (dir==DECRYPTION) // reverse key schedule order
319  for (i=0; i<16; i+=2)
320  {
321  std::swap(k[i], k[32-2-i]);
322  std::swap(k[i+1], k[32-1-i]);
323  }
324 }
325 
326 void RawDES::RawProcessBlock(word32 &l_, word32 &r_) const
327 {
328  word32 l = l_, r = r_;
329  const word32 *kptr=k;
330 
331  for (unsigned i=0; i<8; i++)
332  {
333  word32 work = rotrFixed(r, 4U) ^ kptr[4*i+0];
334  l ^= Spbox[6][(work) & 0x3f]
335  ^ Spbox[4][(work >> 8) & 0x3f]
336  ^ Spbox[2][(work >> 16) & 0x3f]
337  ^ Spbox[0][(work >> 24) & 0x3f];
338  work = r ^ kptr[4*i+1];
339  l ^= Spbox[7][(work) & 0x3f]
340  ^ Spbox[5][(work >> 8) & 0x3f]
341  ^ Spbox[3][(work >> 16) & 0x3f]
342  ^ Spbox[1][(work >> 24) & 0x3f];
343 
344  work = rotrFixed(l, 4U) ^ kptr[4*i+2];
345  r ^= Spbox[6][(work) & 0x3f]
346  ^ Spbox[4][(work >> 8) & 0x3f]
347  ^ Spbox[2][(work >> 16) & 0x3f]
348  ^ Spbox[0][(work >> 24) & 0x3f];
349  work = l ^ kptr[4*i+3];
350  r ^= Spbox[7][(work) & 0x3f]
351  ^ Spbox[5][(work >> 8) & 0x3f]
352  ^ Spbox[3][(work >> 16) & 0x3f]
353  ^ Spbox[1][(work >> 24) & 0x3f];
354  }
355 
356  l_ = l; r_ = r;
357 }
358 
359 void DES_EDE2::Base::UncheckedSetKey(const byte *userKey, unsigned int length, const NameValuePairs &)
360 {
361  AssertValidKeyLength(length);
362 
363  m_des1.RawSetKey(GetCipherDirection(), userKey);
364  m_des2.RawSetKey(ReverseCipherDir(GetCipherDirection()), userKey+8);
365 }
366 
367 void DES_EDE2::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
368 {
369  word32 l,r;
370  Block::Get(inBlock)(l)(r);
371  IPERM(l,r);
372  m_des1.RawProcessBlock(l, r);
373  m_des2.RawProcessBlock(r, l);
374  m_des1.RawProcessBlock(l, r);
375  FPERM(l,r);
376  Block::Put(xorBlock, outBlock)(r)(l);
377 }
378 
379 void DES_EDE3::Base::UncheckedSetKey(const byte *userKey, unsigned int length, const NameValuePairs &)
380 {
381  AssertValidKeyLength(length);
382 
383  m_des1.RawSetKey(GetCipherDirection(), userKey + (IsForwardTransformation() ? 0 : 16));
384  m_des2.RawSetKey(ReverseCipherDir(GetCipherDirection()), userKey + 8);
385  m_des3.RawSetKey(GetCipherDirection(), userKey + (IsForwardTransformation() ? 16 : 0));
386 }
387 
388 void DES_EDE3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
389 {
390  word32 l,r;
391  Block::Get(inBlock)(l)(r);
392  IPERM(l,r);
393  m_des1.RawProcessBlock(l, r);
394  m_des2.RawProcessBlock(r, l);
395  m_des3.RawProcessBlock(l, r);
396  FPERM(l,r);
397  Block::Put(xorBlock, outBlock)(r)(l);
398 }
399 
400 #endif // #ifndef CRYPTOPP_IMPORTS
401 
402 static inline bool CheckParity(byte b)
403 {
404  unsigned int a = b ^ (b >> 4);
405  return ((a ^ (a>>1) ^ (a>>2) ^ (a>>3)) & 1) == 1;
406 }
407 
408 bool DES::CheckKeyParityBits(const byte *key)
409 {
410  for (unsigned int i=0; i<8; i++)
411  if (!CheckParity(key[i]))
412  return false;
413  return true;
414 }
415 
417 {
418  for (unsigned int i=0; i<8; i++)
419  if (!CheckParity(key[i]))
420  key[i] ^= 1;
421 }
422 
423 // Encrypt or decrypt a block of data in ECB mode
424 void DES::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
425 {
426  word32 l,r;
427  Block::Get(inBlock)(l)(r);
428  IPERM(l,r);
429  RawProcessBlock(l, r);
430  FPERM(l,r);
431  Block::Put(xorBlock, outBlock)(r)(l);
432 }
433 
434 void DES_XEX3::Base::UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &)
435 {
436  AssertValidKeyLength(length);
437 
438  if (!m_des.get())
439  m_des.reset(new DES::Encryption);
440 
441  memcpy(m_x1, key + (IsForwardTransformation() ? 0 : 16), BLOCKSIZE);
442  m_des->RawSetKey(GetCipherDirection(), key + 8);
443  memcpy(m_x3, key + (IsForwardTransformation() ? 16 : 0), BLOCKSIZE);
444 }
445 
446 void DES_XEX3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
447 {
448  xorbuf(outBlock, inBlock, m_x1, BLOCKSIZE);
449  m_des->ProcessAndXorBlock(outBlock, xorBlock, outBlock);
450  xorbuf(outBlock, m_x3, BLOCKSIZE);
451 }
452 
453 NAMESPACE_END
the cipher is performing decryption
Definition: cryptlib.h:112
Utility functions for the Crypto++ library.
static void CorrectKeyParityBits(byte *key)
correct DES key parity bits
Definition: des.cpp:416
T rotlFixed(T x, unsigned int y)
Performs a left rotate.
Definition: misc.h:1314
Converts a typename to an enumerated value.
Definition: cryptlib.h:120
CipherDir
Specifies a direction for a cipher to operate.
Definition: cryptlib.h:108
Access a block of memory.
Definition: misc.h:2255
SecBlock typedef.
Definition: secblock.h:731
Provides class member functions to key a block cipher.
Definition: seckey.h:339
static bool CheckKeyParityBits(const byte *key)
check DES key parity bits
Definition: des.cpp:408
CipherDir ReverseCipherDir(CipherDir dir)
Inverts the cipher's direction.
Definition: seckey.h:25
Classes for DES, 2-key Triple-DES, 3-key Triple-DES and DESX.
void xorbuf(byte *buf, const byte *mask, size_t count)
Performs an XOR of a buffer with a mask.
Definition: misc.cpp:28
Access a block of memory.
Definition: misc.h:2217
Crypto++ library namespace.
T rotrFixed(T x, unsigned int y)
Performs a right rotate.
Definition: misc.h:1336
Interface for retrieving values given their names.
Definition: cryptlib.h:282