Crypto++  5.6.5
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 namespace {
225  const byte p32i[] = {
226  16, 7, 20, 21,
227  29, 12, 28, 17,
228  1, 15, 23, 26,
229  5, 18, 31, 10,
230  2, 8, 24, 14,
231  32, 27, 3, 9,
232  19, 13, 30, 6,
233  22, 11, 4, 25
234  };
235 }
236 #endif
237 
238 /* permuted choice table (key) */
239 namespace {
240  const byte pc1[] = {
241  57, 49, 41, 33, 25, 17, 9,
242  1, 58, 50, 42, 34, 26, 18,
243  10, 2, 59, 51, 43, 35, 27,
244  19, 11, 3, 60, 52, 44, 36,
245 
246  63, 55, 47, 39, 31, 23, 15,
247  7, 62, 54, 46, 38, 30, 22,
248  14, 6, 61, 53, 45, 37, 29,
249  21, 13, 5, 28, 20, 12, 4
250  };
251 }
252 
253 /* number left rotations of pc1 */
254 namespace {
255  const byte totrot[] = {
256  1,2,4,6,8,10,12,14,15,17,19,21,23,25,27,28
257  };
258 }
259 
260 /* permuted choice key (table) */
261 namespace {
262  const byte pc2[] = {
263  14, 17, 11, 24, 1, 5,
264  3, 28, 15, 6, 21, 10,
265  23, 19, 12, 4, 26, 8,
266  16, 7, 27, 20, 13, 2,
267  41, 52, 31, 37, 47, 55,
268  30, 40, 51, 45, 33, 48,
269  44, 49, 39, 56, 34, 53,
270  46, 42, 50, 36, 29, 32
271  };
272 }
273 
274 /* End of DES-defined tables */
275 
276 /* bit 0 is left-most in byte */
277 namespace {
278  const int bytebit[] = {
279  0200,0100,040,020,010,04,02,01
280  };
281 }
282 
283 /* Set key (initialize key schedule array) */
284 void RawDES::RawSetKey(CipherDir dir, const byte *key)
285 {
286 #if (_MSC_VER >= 1600) || (__cplusplus >= 201103L)
287 # define register /* Define to nothing for C++11 and above */
288 #endif
289 
290  SecByteBlock buffer(56+56+8);
291  byte *const pc1m=buffer; /* place to modify pc1 into */
292  byte *const pcr=pc1m+56; /* place to rotate pc1 into */
293  byte *const ks=pcr+56;
294  register int i,j,l;
295  int m;
296 
297  for (j=0; j<56; j++) { /* convert pc1 to bits of key */
298  l=pc1[j]-1; /* integer bit location */
299  m = l & 07; /* find bit */
300  pc1m[j]=(key[l>>3] & /* find which key byte l is in */
301  bytebit[m]) /* and which bit of that byte */
302  ? 1 : 0; /* and store 1-bit result */
303  }
304  for (i=0; i<16; i++) { /* key chunk for each iteration */
305  memset(ks,0,8); /* Clear key schedule */
306  for (j=0; j<56; j++) /* rotate pc1 the right amount */
307  pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
308  /* rotate left and right halves independently */
309  for (j=0; j<48; j++){ /* select bits individually */
310  /* check bit that goes to ks[j] */
311  if (pcr[pc2[j]-1]){
312  /* mask it in if it's there */
313  l= j % 6;
314  ks[j/6] |= bytebit[l] >> 2;
315  }
316  }
317  /* Now convert to odd/even interleaved form for use in F */
318  k[2*i] = ((word32)ks[0] << 24)
319  | ((word32)ks[2] << 16)
320  | ((word32)ks[4] << 8)
321  | ((word32)ks[6]);
322  k[2*i+1] = ((word32)ks[1] << 24)
323  | ((word32)ks[3] << 16)
324  | ((word32)ks[5] << 8)
325  | ((word32)ks[7]);
326  }
327 
328  if (dir==DECRYPTION) // reverse key schedule order
329  for (i=0; i<16; i+=2)
330  {
331  std::swap(k[i], k[32-2-i]);
332  std::swap(k[i+1], k[32-1-i]);
333  }
334 }
335 
336 void RawDES::RawProcessBlock(word32 &l_, word32 &r_) const
337 {
338  word32 l = l_, r = r_;
339  const word32 *kptr=k;
340 
341  for (unsigned i=0; i<8; i++)
342  {
343  word32 work = rotrFixed(r, 4U) ^ kptr[4*i+0];
344  l ^= Spbox[6][(work) & 0x3f]
345  ^ Spbox[4][(work >> 8) & 0x3f]
346  ^ Spbox[2][(work >> 16) & 0x3f]
347  ^ Spbox[0][(work >> 24) & 0x3f];
348  work = r ^ kptr[4*i+1];
349  l ^= Spbox[7][(work) & 0x3f]
350  ^ Spbox[5][(work >> 8) & 0x3f]
351  ^ Spbox[3][(work >> 16) & 0x3f]
352  ^ Spbox[1][(work >> 24) & 0x3f];
353 
354  work = rotrFixed(l, 4U) ^ kptr[4*i+2];
355  r ^= Spbox[6][(work) & 0x3f]
356  ^ Spbox[4][(work >> 8) & 0x3f]
357  ^ Spbox[2][(work >> 16) & 0x3f]
358  ^ Spbox[0][(work >> 24) & 0x3f];
359  work = l ^ kptr[4*i+3];
360  r ^= Spbox[7][(work) & 0x3f]
361  ^ Spbox[5][(work >> 8) & 0x3f]
362  ^ Spbox[3][(work >> 16) & 0x3f]
363  ^ Spbox[1][(work >> 24) & 0x3f];
364  }
365 
366  l_ = l; r_ = r;
367 }
368 
369 void DES_EDE2::Base::UncheckedSetKey(const byte *userKey, unsigned int length, const NameValuePairs &)
370 {
371  AssertValidKeyLength(length);
372 
373  m_des1.RawSetKey(GetCipherDirection(), userKey);
374  m_des2.RawSetKey(ReverseCipherDir(GetCipherDirection()), userKey+8);
375 }
376 
377 void DES_EDE2::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
378 {
379  word32 l,r;
380  Block::Get(inBlock)(l)(r);
381  IPERM(l,r);
382  m_des1.RawProcessBlock(l, r);
383  m_des2.RawProcessBlock(r, l);
384  m_des1.RawProcessBlock(l, r);
385  FPERM(l,r);
386  Block::Put(xorBlock, outBlock)(r)(l);
387 }
388 
389 void DES_EDE3::Base::UncheckedSetKey(const byte *userKey, unsigned int length, const NameValuePairs &)
390 {
391  AssertValidKeyLength(length);
392 
393  m_des1.RawSetKey(GetCipherDirection(), userKey + (IsForwardTransformation() ? 0 : 16));
394  m_des2.RawSetKey(ReverseCipherDir(GetCipherDirection()), userKey + 8);
395  m_des3.RawSetKey(GetCipherDirection(), userKey + (IsForwardTransformation() ? 16 : 0));
396 }
397 
398 void DES_EDE3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
399 {
400  word32 l,r;
401  Block::Get(inBlock)(l)(r);
402  IPERM(l,r);
403  m_des1.RawProcessBlock(l, r);
404  m_des2.RawProcessBlock(r, l);
405  m_des3.RawProcessBlock(l, r);
406  FPERM(l,r);
407  Block::Put(xorBlock, outBlock)(r)(l);
408 }
409 
410 #endif // #ifndef CRYPTOPP_IMPORTS
411 
412 static inline bool CheckParity(byte b)
413 {
414  unsigned int a = b ^ (b >> 4);
415  return ((a ^ (a>>1) ^ (a>>2) ^ (a>>3)) & 1) == 1;
416 }
417 
418 bool DES::CheckKeyParityBits(const byte *key)
419 {
420  for (unsigned int i=0; i<8; i++)
421  if (!CheckParity(key[i]))
422  return false;
423  return true;
424 }
425 
427 {
428  for (unsigned int i=0; i<8; i++)
429  if (!CheckParity(key[i]))
430  key[i] ^= 1;
431 }
432 
433 // Encrypt or decrypt a block of data in ECB mode
434 void DES::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
435 {
436  word32 l,r;
437  Block::Get(inBlock)(l)(r);
438  IPERM(l,r);
439  RawProcessBlock(l, r);
440  FPERM(l,r);
441  Block::Put(xorBlock, outBlock)(r)(l);
442 }
443 
444 void DES_XEX3::Base::UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &)
445 {
446  AssertValidKeyLength(length);
447 
448  if (!m_des.get())
449  m_des.reset(new DES::Encryption);
450 
451  memcpy(m_x1, key + (IsForwardTransformation() ? 0 : 16), BLOCKSIZE);
452  m_des->RawSetKey(GetCipherDirection(), key + 8);
453  memcpy(m_x3, key + (IsForwardTransformation() ? 16 : 0), BLOCKSIZE);
454 }
455 
456 void DES_XEX3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
457 {
458  xorbuf(outBlock, inBlock, m_x1, BLOCKSIZE);
459  m_des->ProcessAndXorBlock(outBlock, xorBlock, outBlock);
460  xorbuf(outBlock, m_x3, BLOCKSIZE);
461 }
462 
463 NAMESPACE_END
the cipher is performing decryption
Definition: cryptlib.h:108
Utility functions for the Crypto++ library.
static void CorrectKeyParityBits(byte *key)
correct DES key parity bits
Definition: des.cpp:426
T rotlFixed(T x, unsigned int y)
Performs a left rotate.
Definition: misc.h:1263
Converts an enumeration to a type suitable for use as a template parameter.
Definition: cryptlib.h:116
CipherDir
Specifies a direction for a cipher to operate.
Definition: cryptlib.h:104
Access a block of memory.
Definition: misc.h:2233
SecBlock typedef.
Definition: secblock.h:731
Provides class member functions to key a block cipher.
Definition: seckey.h:324
static bool CheckKeyParityBits(const byte *key)
check DES key parity bits
Definition: des.cpp:418
CipherDir ReverseCipherDir(CipherDir dir)
Inverts the cipher's direction.
Definition: seckey.h:31
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:2195
Crypto++ library namespace.
T rotrFixed(T x, unsigned int y)
Performs a right rotate.
Definition: misc.h:1285
Interface for retrieving values given their names.
Definition: cryptlib.h:279