crypto/external/bsd/heimdal/dist/lib/hcrypto/DESperate.txt

   1 The hunt for getting a DES with plain BSD license w/o advertisement clause
   2 ==========================================================================
   3
   4 Id
   5
   6 This all feels very silly given that DES is about 30 years old and now
   7 is deprecated.
   8
   9 Helpful documents on the way:
  10
  11 Schider's crypto wasn't that useful since it only told how to do DES,
  12 not how to do des fast or how to not use DES. I find this to be a
  13 common thread in the book, it explain each tool in great detail, but
  14 not its limitations.
  15
  16 Dag Arne Osvik: Efficient Implementation of the Data Encryption Standard
  17
  18 Some threads on sci.crypto was also useful.
  19
  20 PC1 transformations
  21 ===================
  22
  23
  24 Getting the PC1 bit mangling working was hard, I never got it to work.
  25
  26 Printning out the bit usage made me realize a lookup table could be
  27 used since only 12 bits are used from the first half and 16 from the
  28 second.
  29
  30 01110000 01110000 01110000 01110000 01111000 01111000 01111000 01111000
  31 00001111 00001111 00001111 00001111 00000111 00000111 00000111 00000111
  32
  33 The pattern is getting more obvious if it's printed out where the bits
  34 are coming from.
  35
  36  8 16 24  -  -  -  -  -
  37  7 15 23  -  -  -  -  -
  38  6 14 22  -  -  -  -  -
  39  5 13 21  -  -  -  -  -
  40  4 12 20 28  -  -  -  -
  41  3 11 19 27  -  -  -  -
  42  2 10 18 26  -  -  -  -
  43  1  9 17 25  -  -  -  -
  44
  45  -  -  - 60 56 48 40  -
  46  -  -  - 59 55 47 39  -
  47  -  -  - 58 54 46 38  -
  48  -  -  - 57 53 45 37  -
  49  -  -  -  - 52 44 36  -
  50  -  -  -  - 51 43 35  -
  51  -  -  -  - 50 42 34  -
  52  -  -  -  - 49 41 33  -
  53
  54 Only 3 bits-table is needed for the first half and 4 bits for the
  55 second half because they are on diffrent shift offsets.
  56
  57 So to get the bitpattern bit-pattern
  58
  59 gen_pattern("pc1_c_3", 7,  [ 5, 13, 21 ], 0, 0x1000000);
  60 gen_pattern("pc1_c_4", 15, [ 1, 9, 17, 25 ], 0, 0x1000000);
  61 gen_pattern("pc1_d_3", 7, [ 49, 41, 33 ], 32, 0x1000000);
  62 gen_pattern("pc1_d_4", 15, [ 57, 53, 45, 37 ], 32, 0x1000000);
  63
  64 PC2 transformations
  65 ===================
  66
  67 PC2 is also a table lookup, since it's a 24 bit field, I use 4 6-bit
  68 lookup tables. Printing the reverse of the PC2 table reveal that some
  69 of the bits are not used, namely (9, 18, 22, 25) from c and (7, 10,
  70 15, 26) from d.
  71
  72 pc2 from c
  73 ----------
  74
  75  5 24  7 16  6 10 20
  76 18  - 12  3 15 23  1
  77  9 19  2  - 14 22 11
  78  - 13  4  - 17 21  8
  79
  80 pc2 from d
  81 ----------
  82
  83 51 35 31 52 39 45  -
  84 50 32  - 43 36 29 48
  85  - 41 38 47 33 40 42
  86 49 37 30 46  - 34 44
  87
  88 So we generate tables for that too.
  89
  90 gen_pattern("pc2_c_1", 63, [  5, 24,  7, 16,  6, 10 ], 0, 0x800000);
  91 gen_pattern("pc2_c_2", 63, [ 20, 18, 12,  3, 15, 23 ], 0, 0x800000);
  92 gen_pattern("pc2_c_3", 63, [  1,  9, 19,  2, 14, 22 ], 0, 0x800000);
  93 gen_pattern("pc2_c_4", 63, [ 11, 13,  4, 17, 21,  8 ], 0, 0x800000);
  94
  95 gen_pattern("pc2_d_1", 63, [ 51, 35, 31, 52, 39, 45 ], 28, 0x800000);
  96 gen_pattern("pc2_d_2", 63, [ 50, 32, 43, 36, 29, 48 ], 28, 0x800000);
  97 gen_pattern("pc2_d_3", 63, [ 41, 38, 47, 33, 40, 42 ], 28, 0x800000);
  98 gen_pattern("pc2_d_4", 63, [ 49, 37, 30, 46, 34, 44 ], 28, 0x800000);
  99
 100
 101 SBOX transformations
 102 ====================
 103
 104 The SBOX transformations are 6 bit to 4 bit transformations.
 105
 106 Here I grew tired and used Richard Outerbridge SBOXes. Thank you
 107 Richard.
 108