Crypto++
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  SecByteBlock buffer(56+56+8);
277  byte *const pc1m=buffer; /* place to modify pc1 into */
278  byte *const pcr=pc1m+56; /* place to rotate pc1 into */
279  byte *const ks=pcr+56;
280  register int i,j,l;
281  int m;
282 
283  for (j=0; j<56; j++) { /* convert pc1 to bits of key */
284  l=pc1[j]-1; /* integer bit location */
285  m = l & 07; /* find bit */
286  pc1m[j]=(key[l>>3] & /* find which key byte l is in */
287  bytebit[m]) /* and which bit of that byte */
288  ? 1 : 0; /* and store 1-bit result */
289  }
290  for (i=0; i<16; i++) { /* key chunk for each iteration */
291  memset(ks,0,8); /* Clear key schedule */
292  for (j=0; j<56; j++) /* rotate pc1 the right amount */
293  pcr[j] = pc1m[(l=j+totrot[i])<(j<28? 28 : 56) ? l: l-28];
294  /* rotate left and right halves independently */
295  for (j=0; j<48; j++){ /* select bits individually */
296  /* check bit that goes to ks[j] */
297  if (pcr[pc2[j]-1]){
298  /* mask it in if it's there */
299  l= j % 6;
300  ks[j/6] |= bytebit[l] >> 2;
301  }
302  }
303  /* Now convert to odd/even interleaved form for use in F */
304  k[2*i] = ((word32)ks[0] << 24)
305  | ((word32)ks[2] << 16)
306  | ((word32)ks[4] << 8)
307  | ((word32)ks[6]);
308  k[2*i+1] = ((word32)ks[1] << 24)
309  | ((word32)ks[3] << 16)
310  | ((word32)ks[5] << 8)
311  | ((word32)ks[7]);
312  }
313 
314  if (dir==DECRYPTION) // reverse key schedule order
315  for (i=0; i<16; i+=2)
316  {
317  std::swap(k[i], k[32-2-i]);
318  std::swap(k[i+1], k[32-1-i]);
319  }
320 }
321 
322 void RawDES::RawProcessBlock(word32 &l_, word32 &r_) const
323 {
324  word32 l = l_, r = r_;
325  const word32 *kptr=k;
326 
327  for (unsigned i=0; i<8; i++)
328  {
329  word32 work = rotrFixed(r, 4U) ^ kptr[4*i+0];
330  l ^= Spbox[6][(work) & 0x3f]
331  ^ Spbox[4][(work >> 8) & 0x3f]
332  ^ Spbox[2][(work >> 16) & 0x3f]
333  ^ Spbox[0][(work >> 24) & 0x3f];
334  work = r ^ kptr[4*i+1];
335  l ^= Spbox[7][(work) & 0x3f]
336  ^ Spbox[5][(work >> 8) & 0x3f]
337  ^ Spbox[3][(work >> 16) & 0x3f]
338  ^ Spbox[1][(work >> 24) & 0x3f];
339 
340  work = rotrFixed(l, 4U) ^ kptr[4*i+2];
341  r ^= Spbox[6][(work) & 0x3f]
342  ^ Spbox[4][(work >> 8) & 0x3f]
343  ^ Spbox[2][(work >> 16) & 0x3f]
344  ^ Spbox[0][(work >> 24) & 0x3f];
345  work = l ^ kptr[4*i+3];
346  r ^= Spbox[7][(work) & 0x3f]
347  ^ Spbox[5][(work >> 8) & 0x3f]
348  ^ Spbox[3][(work >> 16) & 0x3f]
349  ^ Spbox[1][(work >> 24) & 0x3f];
350  }
351 
352  l_ = l; r_ = r;
353 }
354 
355 void DES_EDE2::Base::UncheckedSetKey(const byte *userKey, unsigned int length, const NameValuePairs &)
356 {
357  AssertValidKeyLength(length);
358 
359  m_des1.RawSetKey(GetCipherDirection(), userKey);
360  m_des2.RawSetKey(ReverseCipherDir(GetCipherDirection()), userKey+8);
361 }
362 
363 void DES_EDE2::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
364 {
365  word32 l,r;
366  Block::Get(inBlock)(l)(r);
367  IPERM(l,r);
368  m_des1.RawProcessBlock(l, r);
369  m_des2.RawProcessBlock(r, l);
370  m_des1.RawProcessBlock(l, r);
371  FPERM(l,r);
372  Block::Put(xorBlock, outBlock)(r)(l);
373 }
374 
375 void DES_EDE3::Base::UncheckedSetKey(const byte *userKey, unsigned int length, const NameValuePairs &)
376 {
377  AssertValidKeyLength(length);
378 
379  m_des1.RawSetKey(GetCipherDirection(), userKey + (IsForwardTransformation() ? 0 : 16));
380  m_des2.RawSetKey(ReverseCipherDir(GetCipherDirection()), userKey + 8);
381  m_des3.RawSetKey(GetCipherDirection(), userKey + (IsForwardTransformation() ? 16 : 0));
382 }
383 
384 void DES_EDE3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
385 {
386  word32 l,r;
387  Block::Get(inBlock)(l)(r);
388  IPERM(l,r);
389  m_des1.RawProcessBlock(l, r);
390  m_des2.RawProcessBlock(r, l);
391  m_des3.RawProcessBlock(l, r);
392  FPERM(l,r);
393  Block::Put(xorBlock, outBlock)(r)(l);
394 }
395 
396 #endif // #ifndef CRYPTOPP_IMPORTS
397 
398 static inline bool CheckParity(byte b)
399 {
400  unsigned int a = b ^ (b >> 4);
401  return ((a ^ (a>>1) ^ (a>>2) ^ (a>>3)) & 1) == 1;
402 }
403 
404 bool DES::CheckKeyParityBits(const byte *key)
405 {
406  for (unsigned int i=0; i<8; i++)
407  if (!CheckParity(key[i]))
408  return false;
409  return true;
410 }
411 
413 {
414  for (unsigned int i=0; i<8; i++)
415  if (!CheckParity(key[i]))
416  key[i] ^= 1;
417 }
418 
419 // Encrypt or decrypt a block of data in ECB mode
420 void DES::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
421 {
422  word32 l,r;
423  Block::Get(inBlock)(l)(r);
424  IPERM(l,r);
425  RawProcessBlock(l, r);
426  FPERM(l,r);
427  Block::Put(xorBlock, outBlock)(r)(l);
428 }
429 
430 void DES_XEX3::Base::UncheckedSetKey(const byte *key, unsigned int length, const NameValuePairs &)
431 {
432  AssertValidKeyLength(length);
433 
434  if (!m_des.get())
435  m_des.reset(new DES::Encryption);
436 
437  memcpy(m_x1, key + (IsForwardTransformation() ? 0 : 16), BLOCKSIZE);
438  m_des->RawSetKey(GetCipherDirection(), key + 8);
439  memcpy(m_x3, key + (IsForwardTransformation() ? 16 : 0), BLOCKSIZE);
440 }
441 
442 void DES_XEX3::Base::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
443 {
444  xorbuf(outBlock, inBlock, m_x1, BLOCKSIZE);
445  m_des->ProcessAndXorBlock(outBlock, xorBlock, outBlock);
446  xorbuf(outBlock, m_x3, BLOCKSIZE);
447 }
448 
449 NAMESPACE_END
static void CorrectKeyParityBits(byte *key)
correct DES key parity bits
Definition: des.cpp:412
CipherDir
used to specify a direction for a cipher to operate in (encrypt or decrypt)
Definition: cryptlib.h:93
a block of memory allocated using A
Definition: secblock.h:238
static bool CheckKeyParityBits(const byte *key)
check DES key parity bits
Definition: des.cpp:404
interface for retrieving values given their names
Definition: cryptlib.h:225