src/lib/crypto/des/f_sched.c

   1 /*
   2  * Copyright (c) 1990 Dennis Ferguson.  All rights reserved.
   3  *
   4  * Commercial use is permitted only if products which are derived from
   5  * or include this software are made available for purchase and/or use
   6  * in Canada.  Otherwise, redistribution and use in source and binary
   7  * forms are permitted.
   8  */
   9
  10 /*
  11  * des_make_sched.c - permute a DES key, returning the resulting key schedule
  12  */
  13 #include "des.h"
  14 #include "k5-int.h"
  15
  16 /*
  17  * Permuted choice 1 tables.  These are used to extract bits
  18  * from the left and right parts of the key to form Ci and Di.
  19  * The code that uses these tables knows which bits from which
  20  * part of each key are used to form Ci and Di.
  21  */
  22 static const unsigned KRB_INT32 PC1_CL[8] = {
  23         0x00000000, 0x00000010, 0x00001000, 0x00001010,
  24         0x00100000, 0x00100010, 0x00101000, 0x00101010
  25 };
  26
  27 static const unsigned KRB_INT32 PC1_DL[16] = {
  28         0x00000000, 0x00100000, 0x00001000, 0x00101000,
  29         0x00000010, 0x00100010, 0x00001010, 0x00101010,
  30         0x00000001, 0x00100001, 0x00001001, 0x00101001,
  31         0x00000011, 0x00100011, 0x00001011, 0x00101011
  32 };
  33
  34 static const unsigned KRB_INT32 PC1_CR[16] = {
  35         0x00000000, 0x00000001, 0x00000100, 0x00000101,
  36         0x00010000, 0x00010001, 0x00010100, 0x00010101,
  37         0x01000000, 0x01000001, 0x01000100, 0x01000101,
  38         0x01010000, 0x01010001, 0x01010100, 0x01010101
  39 };
  40
  41 static const unsigned KRB_INT32 PC1_DR[8] = {
  42         0x00000000, 0x01000000, 0x00010000, 0x01010000,
  43         0x00000100, 0x01000100, 0x00010100, 0x01010100
  44 };
  45
  46
  47 /*
  48  * At the start of some iterations of the key schedule we do
  49  * a circular left shift by one place, while for others we do a shift by
  50  * two places.  This has bits set for the iterations where we do 2 bit
  51  * shifts, starting at the low order bit.
  52  */
  53 #define TWO_BIT_SHIFTS  0x7efc
  54
  55 /*
  56  * Permuted choice 2 tables.  The first actually produces the low order
  57  * 24 bits of the subkey Ki from the 28 bit value of Ci.  The second produces
  58  * the high order 24 bits from Di.  The tables are indexed by six bit
  59  * segments of Ci and Di respectively.  The code is handcrafted to compute
  60  * the appropriate 6 bit chunks.
  61  *
  62  * Note that for ease of computation, the 24 bit values are produced with
  63  * six bits going into each byte.  Note also that the table has been byte
  64  * rearranged to produce keys which match the order we will apply them
  65  * in in the des code.
  66  */
  67 static const unsigned KRB_INT32 PC2_C[4][64] = {
  68         0x00000000, 0x00000004, 0x00010000, 0x00010004,
  69         0x00000400, 0x00000404, 0x00010400, 0x00010404,
  70         0x00000020, 0x00000024, 0x00010020, 0x00010024,
  71         0x00000420, 0x00000424, 0x00010420, 0x00010424,
  72         0x01000000, 0x01000004, 0x01010000, 0x01010004,
  73         0x01000400, 0x01000404, 0x01010400, 0x01010404,
  74         0x01000020, 0x01000024, 0x01010020, 0x01010024,
  75         0x01000420, 0x01000424, 0x01010420, 0x01010424,
  76         0x00020000, 0x00020004, 0x00030000, 0x00030004,
  77         0x00020400, 0x00020404, 0x00030400, 0x00030404,
  78         0x00020020, 0x00020024, 0x00030020, 0x00030024,
  79         0x00020420, 0x00020424, 0x00030420, 0x00030424,
  80         0x01020000, 0x01020004, 0x01030000, 0x01030004,
  81         0x01020400, 0x01020404, 0x01030400, 0x01030404,
  82         0x01020020, 0x01020024, 0x01030020, 0x01030024,
  83         0x01020420, 0x01020424, 0x01030420, 0x01030424,
  84
  85         0x00000000, 0x02000000, 0x00000800, 0x02000800,
  86         0x00080000, 0x02080000, 0x00080800, 0x02080800,
  87         0x00000001, 0x02000001, 0x00000801, 0x02000801,
  88         0x00080001, 0x02080001, 0x00080801, 0x02080801,
  89         0x00000100, 0x02000100, 0x00000900, 0x02000900,
  90         0x00080100, 0x02080100, 0x00080900, 0x02080900,
  91         0x00000101, 0x02000101, 0x00000901, 0x02000901,
  92         0x00080101, 0x02080101, 0x00080901, 0x02080901,
  93         0x10000000, 0x12000000, 0x10000800, 0x12000800,
  94         0x10080000, 0x12080000, 0x10080800, 0x12080800,
  95         0x10000001, 0x12000001, 0x10000801, 0x12000801,
  96         0x10080001, 0x12080001, 0x10080801, 0x12080801,
  97         0x10000100, 0x12000100, 0x10000900, 0x12000900,
  98         0x10080100, 0x12080100, 0x10080900, 0x12080900,
  99         0x10000101, 0x12000101, 0x10000901, 0x12000901,
 100         0x10080101, 0x12080101, 0x10080901, 0x12080901,
 101
 102         0x00000000, 0x00040000, 0x00002000, 0x00042000,
 103         0x00100000, 0x00140000, 0x00102000, 0x00142000,
 104         0x20000000, 0x20040000, 0x20002000, 0x20042000,
 105         0x20100000, 0x20140000, 0x20102000, 0x20142000,
 106         0x00000008, 0x00040008, 0x00002008, 0x00042008,
 107         0x00100008, 0x00140008, 0x00102008, 0x00142008,
 108         0x20000008, 0x20040008, 0x20002008, 0x20042008,
 109         0x20100008, 0x20140008, 0x20102008, 0x20142008,
 110         0x00200000, 0x00240000, 0x00202000, 0x00242000,
 111         0x00300000, 0x00340000, 0x00302000, 0x00342000,
 112         0x20200000, 0x20240000, 0x20202000, 0x20242000,
 113         0x20300000, 0x20340000, 0x20302000, 0x20342000,
 114         0x00200008, 0x00240008, 0x00202008, 0x00242008,
 115         0x00300008, 0x00340008, 0x00302008, 0x00342008,
 116         0x20200008, 0x20240008, 0x20202008, 0x20242008,
 117         0x20300008, 0x20340008, 0x20302008, 0x20342008,
 118
 119         0x00000000, 0x00000010, 0x08000000, 0x08000010,
 120         0x00000200, 0x00000210, 0x08000200, 0x08000210,
 121         0x00000002, 0x00000012, 0x08000002, 0x08000012,
 122         0x00000202, 0x00000212, 0x08000202, 0x08000212,
 123         0x04000000, 0x04000010, 0x0c000000, 0x0c000010,
 124         0x04000200, 0x04000210, 0x0c000200, 0x0c000210,
 125         0x04000002, 0x04000012, 0x0c000002, 0x0c000012,
 126         0x04000202, 0x04000212, 0x0c000202, 0x0c000212,
 127         0x00001000, 0x00001010, 0x08001000, 0x08001010,
 128         0x00001200, 0x00001210, 0x08001200, 0x08001210,
 129         0x00001002, 0x00001012, 0x08001002, 0x08001012,
 130         0x00001202, 0x00001212, 0x08001202, 0x08001212,
 131         0x04001000, 0x04001010, 0x0c001000, 0x0c001010,
 132         0x04001200, 0x04001210, 0x0c001200, 0x0c001210,
 133         0x04001002, 0x04001012, 0x0c001002, 0x0c001012,
 134         0x04001202, 0x04001212, 0x0c001202, 0x0c001212
 135 };
 136
 137 static const unsigned KRB_INT32 PC2_D[4][64] = {
 138         0x00000000, 0x02000000, 0x00020000, 0x02020000,
 139         0x00000100, 0x02000100, 0x00020100, 0x02020100,
 140         0x00000008, 0x02000008, 0x00020008, 0x02020008,
 141         0x00000108, 0x02000108, 0x00020108, 0x02020108,
 142         0x00200000, 0x02200000, 0x00220000, 0x02220000,
 143         0x00200100, 0x02200100, 0x00220100, 0x02220100,
 144         0x00200008, 0x02200008, 0x00220008, 0x02220008,
 145         0x00200108, 0x02200108, 0x00220108, 0x02220108,
 146         0x00000200, 0x02000200, 0x00020200, 0x02020200,
 147         0x00000300, 0x02000300, 0x00020300, 0x02020300,
 148         0x00000208, 0x02000208, 0x00020208, 0x02020208,
 149         0x00000308, 0x02000308, 0x00020308, 0x02020308,
 150         0x00200200, 0x02200200, 0x00220200, 0x02220200,
 151         0x00200300, 0x02200300, 0x00220300, 0x02220300,
 152         0x00200208, 0x02200208, 0x00220208, 0x02220208,
 153         0x00200308, 0x02200308, 0x00220308, 0x02220308,
 154
 155         0x00000000, 0x00001000, 0x00000020, 0x00001020,
 156         0x00100000, 0x00101000, 0x00100020, 0x00101020,
 157         0x08000000, 0x08001000, 0x08000020, 0x08001020,
 158         0x08100000, 0x08101000, 0x08100020, 0x08101020,
 159         0x00000004, 0x00001004, 0x00000024, 0x00001024,
 160         0x00100004, 0x00101004, 0x00100024, 0x00101024,
 161         0x08000004, 0x08001004, 0x08000024, 0x08001024,
 162         0x08100004, 0x08101004, 0x08100024, 0x08101024,
 163         0x00000400, 0x00001400, 0x00000420, 0x00001420,
 164         0x00100400, 0x00101400, 0x00100420, 0x00101420,
 165         0x08000400, 0x08001400, 0x08000420, 0x08001420,
 166         0x08100400, 0x08101400, 0x08100420, 0x08101420,
 167         0x00000404, 0x00001404, 0x00000424, 0x00001424,
 168         0x00100404, 0x00101404, 0x00100424, 0x00101424,
 169         0x08000404, 0x08001404, 0x08000424, 0x08001424,
 170         0x08100404, 0x08101404, 0x08100424, 0x08101424,
 171
 172         0x00000000, 0x10000000, 0x00010000, 0x10010000,
 173         0x00000002, 0x10000002, 0x00010002, 0x10010002,
 174         0x00002000, 0x10002000, 0x00012000, 0x10012000,
 175         0x00002002, 0x10002002, 0x00012002, 0x10012002,
 176         0x00040000, 0x10040000, 0x00050000, 0x10050000,
 177         0x00040002, 0x10040002, 0x00050002, 0x10050002,
 178         0x00042000, 0x10042000, 0x00052000, 0x10052000,
 179         0x00042002, 0x10042002, 0x00052002, 0x10052002,
 180         0x20000000, 0x30000000, 0x20010000, 0x30010000,
 181         0x20000002, 0x30000002, 0x20010002, 0x30010002,
 182         0x20002000, 0x30002000, 0x20012000, 0x30012000,
 183         0x20002002, 0x30002002, 0x20012002, 0x30012002,
 184         0x20040000, 0x30040000, 0x20050000, 0x30050000,
 185         0x20040002, 0x30040002, 0x20050002, 0x30050002,
 186         0x20042000, 0x30042000, 0x20052000, 0x30052000,
 187         0x20042002, 0x30042002, 0x20052002, 0x30052002,
 188
 189         0x00000000, 0x04000000, 0x00000001, 0x04000001,
 190         0x01000000, 0x05000000, 0x01000001, 0x05000001,
 191         0x00000010, 0x04000010, 0x00000011, 0x04000011,
 192         0x01000010, 0x05000010, 0x01000011, 0x05000011,
 193         0x00080000, 0x04080000, 0x00080001, 0x04080001,
 194         0x01080000, 0x05080000, 0x01080001, 0x05080001,
 195         0x00080010, 0x04080010, 0x00080011, 0x04080011,
 196         0x01080010, 0x05080010, 0x01080011, 0x05080011,
 197         0x00000800, 0x04000800, 0x00000801, 0x04000801,
 198         0x01000800, 0x05000800, 0x01000801, 0x05000801,
 199         0x00000810, 0x04000810, 0x00000811, 0x04000811,
 200         0x01000810, 0x05000810, 0x01000811, 0x05000811,
 201         0x00080800, 0x04080800, 0x00080801, 0x04080801,
 202         0x01080800, 0x05080800, 0x01080801, 0x05080801,
 203         0x00080810, 0x04080810, 0x00080811, 0x04080811,
 204         0x01080810, 0x05080810, 0x01080811, 0x05080811
 205 };
 206
 207
 208
 209 /*
 210  * Permute the key to give us our key schedule.
 211  */
 212 int INTERFACE
 213 make_key_sched(key, schedule)
 214      mit_des_cblock key;
 215      mit_des_key_schedule schedule;
 216 {
 217         register unsigned KRB_INT32 c, d;
 218
 219         {
 220                 /*
 221                  * Need a pointer for the keys and a temporary KRB_INT32
 222                  */
 223                 register unsigned char *k;
 224                 register unsigned KRB_INT32 tmp;
 225
 226                 /*
 227                  * Fetch the key into something we can work with
 228                  */
 229                 k = (unsigned char *)key;
 230
 231                 /*
 232                  * The first permutted choice gives us the 28 bits for C0 and
 233                  * 28 for D0.  C0 gets 12 bits from the left key and 16 from
 234                  * the right, while D0 gets 16 from the left and 12 from the
 235                  * right.  The code knows which bits go where.
 236                  */
 237                 tmp = ((unsigned KRB_INT32)(*(k)++)) << 24;
 238                 tmp |= ((unsigned KRB_INT32)(*(k)++)) << 16;
 239                 tmp |= ((unsigned KRB_INT32)(*(k)++)) << 8;
 240                 tmp |= (unsigned KRB_INT32)(*(k)++);            /* left part of key */
 241                 c =  PC1_CL[(tmp >> 29) & 0x7]
 242                   | (PC1_CL[(tmp >> 21) & 0x7] << 1)
 243                   | (PC1_CL[(tmp >> 13) & 0x7] << 2)
 244                   | (PC1_CL[(tmp >>  5) & 0x7] << 3);
 245                 d =  PC1_DL[(tmp >> 25) & 0xf]
 246                   | (PC1_DL[(tmp >> 17) & 0xf] << 1)
 247                   | (PC1_DL[(tmp >>  9) & 0xf] << 2)
 248                   | (PC1_DL[(tmp >>  1) & 0xf] << 3);
 249
 250                 tmp = ((unsigned KRB_INT32)(*(k)++)) << 24;
 251                 tmp |= ((unsigned KRB_INT32)(*(k)++)) << 16;
 252                 tmp |= ((unsigned KRB_INT32)(*(k)++)) << 8;
 253                 tmp |= (unsigned KRB_INT32)(*(k)++);            /* right part of key */
 254                 c |= PC1_CR[(tmp >> 28) & 0xf]
 255                   | (PC1_CR[(tmp >> 20) & 0xf] << 1)
 256                   | (PC1_CR[(tmp >> 12) & 0xf] << 2)
 257                   | (PC1_CR[(tmp >>  4) & 0xf] << 3);
 258                 d |= PC1_DR[(tmp >> 25) & 0x7]
 259                   | (PC1_DR[(tmp >> 17) & 0x7] << 1)
 260                   | (PC1_DR[(tmp >>  9) & 0x7] << 2)
 261                   | (PC1_DR[(tmp >>  1) & 0x7] << 3);
 262         }
 263
 264         {
 265                 /*
 266                  * Need several temporaries in here
 267                  */
 268                 register unsigned KRB_INT32 ltmp, rtmp;
 269                 register unsigned KRB_INT32 *k;
 270                 register int two_bit_shifts;
 271                 register int i;
 272                 /*
 273                  * Now iterate to compute the key schedule.  Note that we
 274                  * record the entire set of subkeys in 6 bit chunks since
 275                  * they are used that way.  At 6 bits/char, we need
 276                  * 48/6 char's/subkey * 16 subkeys/encryption == 128 bytes.
 277                  * The schedule must be this big.
 278                  */
 279                 k = (unsigned KRB_INT32 *)schedule;
 280                 two_bit_shifts = TWO_BIT_SHIFTS;
 281                 for (i = 16; i > 0; i--) {
 282                         /*
 283                          * Do the rotation.  One bit and two bit rotations
 284                          * are done separately.  Note C and D are 28 bits.
 285                          */
 286                         if (two_bit_shifts & 0x1) {
 287                                 c = ((c << 2) & 0xffffffc) | (c >> 26);
 288                                 d = ((d << 2) & 0xffffffc) | (d >> 26);
 289                         } else {
 290                                 c = ((c << 1) & 0xffffffe) | (c >> 27);
 291                                 d = ((d << 1) & 0xffffffe) | (d >> 27);
 292                         }
 293                         two_bit_shifts >>= 1;
 294
 295                         /*
 296                          * Apply permutted choice 2 to C to get the first
 297                          * 24 bits worth of keys.  Note that bits 9, 18, 22
 298                          * and 25 (using DES numbering) in C are unused.  The
 299                          * shift-mask stuff is done to delete these bits from
 300                          * the indices, since this cuts the table size in half.
 301                          *
 302                          * The table is torqued, by the way.  If the standard
 303                          * byte order for this (high to low order) is 1234,
 304                          * the table actually gives us 4132.
 305                          */
 306                         ltmp = PC2_C[0][((c >> 22) & 0x3f)]
 307                              | PC2_C[1][((c >> 15) & 0xf) | ((c >> 16) & 0x30)]
 308                              | PC2_C[2][((c >>  4) & 0x3) | ((c >>  9) & 0x3c)]
 309                              | PC2_C[3][((c      ) & 0x7) | ((c >>  4) & 0x38)];
 310                         /*
 311                          * Apply permutted choice 2 to D to get the other half.
 312                          * Here, bits 7, 10, 15 and 26 go unused.  The sqeezing
 313                          * actually turns out to be cheaper here.
 314                          *
 315                          * This table is similarly torqued.  If the standard
 316                          * byte order is 5678, the table has the bytes permuted
 317                          * to give us 7685.
 318                          */
 319                         rtmp = PC2_D[0][((d >> 22) & 0x3f)]
 320                              | PC2_D[1][((d >> 14) & 0xf) | ((d >> 15) & 0x30)]
 321                              | PC2_D[2][((d >>  7) & 0x3f)]
 322                              | PC2_D[3][((d      ) & 0x3) | ((d >>  1) & 0x3c)];
 323
 324                         /*
 325                          * Make up two words of the key schedule, with a
 326                          * byte order which is convenient for the DES
 327                          * inner loop.  The high order (first) word will
 328                          * hold bytes 7135 (high to low order) while the
 329                          * second holds bytes 4682.
 330                          */
 331                         *k++ = (ltmp & 0x00ffff00) | (rtmp & 0xff0000ff);
 332                         *k++ = (ltmp & 0xff0000ff) | (rtmp & 0x00ffff00);
 333                 }
 334         }
 335         return (0);
 336 }