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