3 * The Data Encryption Standard
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
35 #include <mLib/bits.h>
43 /*----- Global variables --------------------------------------------------*/
45 const octet des_keysz
[] = { KSZ_SET
, 7, 8, 0 };
47 /*----- Main code ---------------------------------------------------------*/
49 /* --- @des_expand@ --- *
51 * Arguments: @const octet *k@ = pointer to key material
52 * @size_t n@ = number of octets of key material (7 or 8)
53 * @uint32 *xx, *yy@ = where to put the results
57 * Use: Extracts 64 bits of key material from the given buffer,
58 * possibly expanding it from 56 to 64 bits on the way.
59 * Parity is set correctly if the key is expanded.
62 void des_expand(const octet
*k
, size_t n
, uint32
*xx
, uint32
*yy
)
71 x
= (x
& 0xfe000000) | ((x
& 0x01fffff0) >> 1);
72 x
= (x
& 0xfffe0000) | ((x
& 0x0001fff8) >> 1);
73 x
= (x
& 0xfffffe00) | ((x
& 0x000001fc) >> 1);
74 z
= x
; z
^= z
>> 4; z
^= z
>> 2; z
^= z
>> 1;
75 x
|= (z
& 0x01010101) ^ 0x01010101;
76 y
= LOAD32(k
+ 3) << 1; /* Note: misaligned */
77 y
= (y
& 0x000000fe) | ((y
& 0x1fffff00) << 1);
78 y
= (y
& 0x0000fefe) | ((y
& 0x3fff0000) << 1);
79 y
= (y
& 0x00fefefe) | ((y
& 0x7f000000) << 1);
80 z
= y
; z
^= z
>> 4; z
^= z
>> 2; z
^= z
>> 1;
81 y
|= (z
& 0x01010101) ^ 0x01010101;
86 /* --- @des_init@ --- *
88 * Arguments: @des_ctx *k@ = pointer to key block
89 * @const void *buf@ = pointer to key buffer
90 * @size_t sz@ = size of key material
94 * Use: Initializes a DES key buffer. The key buffer may be either 7
95 * or 8 bytes long. If it's 8 bytes, the key is assumed to be
96 * padded with parity bits in the low order bit of each octet.
97 * These are stripped out without checking prior to the actual
101 void des_init(des_ctx
*k
, const void *buf
, size_t sz
)
104 typedef uint32 regty
;
112 * Contains the rotation amounts for the key halves.
115 static const char r
[] = {
116 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
119 /* --- Extract the key into my registers --- *
121 * The 7 byte case is rather horrible. It expands the key to the 8 byte
122 * case before going any further. It could probably do with its own @pc1@
127 des_expand(buf
, sz
, &x
, &y
);
129 /* --- Permute using the pointless PC1 --- *
131 * For reference, the original PC1 permutation is
133 * Left half 57 49 41 33 25 17 9
134 * 1 58 50 42 34 26 18
135 * 10 2 59 51 43 35 27
136 * 19 11 3 60 52 44 36
138 * Right half 63 55 47 39 31 23 15
139 * 7 62 54 46 38 30 22
140 * 14 6 61 53 45 37 29
143 * The network below implements this pretty directly; the two 28-bit halves
144 * end up in the least significant bits of the two output words; the parity
145 * bits, which are formally discarded, end up in the top 4 bits of each
146 * half in some random order, and are finally masked off so that they don't
147 * interfere with the rotation below. (I did an exhaustive search, and
148 * there are no better Beneš networks.)
151 SWIZZLE_2(x
, y
, 1, 0x55005401, 0x55005500);
152 SWIZZLE_2(x
, y
, 2, 0x32320101, 0x33330000);
153 TWIZZLE_0(x
, y
, 0xf0e1f0f1);
154 SWIZZLE_2(x
, y
, 4, 0x0f0e0f0f, 0x08050201);
155 SWIZZLE_2(x
, y
, 8, 0x005a003a, 0x005a005a);
156 SWIZZLE_2(x
, y
, 16, 0x00007c6c, 0x000023cc);
157 TWIZZLE_0(x
, y
, 0x20f1e0f0);
158 SWIZZLE_2(x
, y
, 2, 0x10000333, 0x33201013);
159 SWIZZLE_2(x
, y
, 1, 0x10055005, 0x10455005);
160 x
&= 0x0fffffff; y
&= 0x0fffffff;
162 /* --- Now for the key schedule proper --- */
164 for (i
= 0; i
< 16; i
++) {
166 x
= ((x
<< 1) | (x
>> 27)) & 0x0fffffff;
167 y
= ((y
<< 1) | (y
>> 27)) & 0x0fffffff;
169 x
= ((x
<< 2) | (x
>> 26)) & 0x0fffffff;
170 y
= ((y
<< 2) | (y
>> 26)) & 0x0fffffff;
173 /* --- Apply PC2, which is another Beneš network --- *
175 * The original permutation is described as follows.
177 * S-box 1: 14 17 11 24 1 5
178 * S-box 2: 3 28 15 6 21 10
179 * S-box 3: 23 19 12 4 26 8
180 * S-box 4: 16 7 27 20 13 2
181 * S-box 5: 41 52 31 37 47 55
182 * S-box 6: 30 40 51 45 33 48
183 * S-box 7: 44 49 39 56 34 53
184 * S-box 8: 46 42 50 36 29 32
186 * Firstly, note the way that the key bits are arranged in the words @x@
187 * and @y@: viewed from the way DES numbers bits from the most-
188 * significant end down, there are four padding bits in positions 1--4,
189 * and another four in positions 33--36. Because the bits in the left-
190 * hand half of the key all feed into the first four S-boxes, we must
191 * adjust the bit positions by 4; and we must adjust the positions of the
192 * bits in the right-hand half by 8.
194 * Secondly, this isn't how we want to apply the key. The formal
195 * description of DES includes an `expansion' %$E$%: essentially, we take
196 * each chunk of four bits in the 32-bit half block, and glue on the
197 * nearest bits from the preceding and following chunk to make a six-bit
198 * chunk, which we then XOR with six bits of key and feed into the S-box
199 * to collapse back down to four bits. We avoid having to do this in
200 * practice by doing the S-boxes in two steps: first, the even-numbered
201 * ones and then the odd-numbered ones. Because these two collections of
202 * S-boxes don't involve overlapping input bits, we can just XOR in the
203 * correct key bits and apply the substitution. There's one more little
204 * problem, which is that the input to the final S-box needs the topmost
205 * bit of the input half-block, which we handle by having previously
206 * rotated the message block left by one position. And that's the
207 * permutation that we implement here.
209 * There are too many blank spaces to search exhaustively for an optimal
210 * network. Based on my experience with PC1, I don't expect the optimal
211 * network to be significantly better than this one.
215 SWIZZLE_2(u
, v
, 1, 0x10551050, 0x05500504);
216 SWIZZLE_2(u
, v
, 2, 0x12131230, 0x33102201);
217 SWIZZLE_2(u
, v
, 8, 0x00a200ec, 0x009100ba);
218 SWIZZLE_2(u
, v
, 16, 0x000012ab, 0x000028e0);
219 SWIZZLE_2(u
, v
, 4, 0x0a090805, 0x0b040002);
220 TWIZZLE_0(u
, v
, 0x33856c2a);
221 SWIZZLE_2(u
, v
, 16, 0x00003385, 0x00004c6a);
222 SWIZZLE_2(u
, v
, 8, 0x001500c8, 0x004700e8);
223 SWIZZLE_2(u
, v
, 2, 0x20130212, 0x00310022);
224 SWIZZLE_2(u
, v
, 1, 0x05404145, 0x54510510);
225 kp
[0] = u
; kp
[1] = v
; kp
+= 2;
231 /* --- @des_eblk@, @des_dblk@ --- *
233 * Arguments: @const des_ctx *k@ = pointer to key block
234 * @const uint32 s[2]@ = pointer to source block
235 * @uint32 d[2]@ = pointer to destination block
239 * Use: Low-level block encryption and decryption.
242 void des_eblk(const des_ctx
*k
, const uint32
*s
, uint32
*d
)
245 typedef uint32 regty
;
247 uint32 x
= s
[0], y
= s
[1];
249 DES_EBLK(k
->k
, x
, y
, x
, y
);
256 void des_dblk(const des_ctx
*k
, const uint32
*s
, uint32
*d
)
259 typedef uint32 regty
;
261 uint32 x
= s
[0], y
= s
[1];
263 DES_DBLK(k
->k
, x
, y
, x
, y
);
272 /*----- That's all, folks -------------------------------------------------*/