Commit | Line | Data |
---|---|---|
d03ab969 | 1 | /* -*-c-*- |
2 | * | |
d03ab969 | 3 | * The Data Encryption Standard |
4 | * | |
5 | * (c) 1999 Straylight/Edgeware | |
6 | */ | |
7 | ||
45c0fd36 | 8 | /*----- Licensing notice --------------------------------------------------* |
d03ab969 | 9 | * |
10 | * This file is part of Catacomb. | |
11 | * | |
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. | |
45c0fd36 | 16 | * |
d03ab969 | 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. | |
45c0fd36 | 21 | * |
d03ab969 | 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, | |
25 | * MA 02111-1307, USA. | |
26 | */ | |
27 | ||
d03ab969 | 28 | /*----- Header files ------------------------------------------------------*/ |
29 | ||
30 | #include <assert.h> | |
31 | #include <stdio.h> | |
32 | #include <stdlib.h> | |
33 | #include <string.h> | |
34 | ||
35 | #include <mLib/bits.h> | |
36 | ||
37 | #include "blkc.h" | |
38 | #include "des-base.h" | |
39 | #include "des.h" | |
d3f33b9a | 40 | #include "permute.h" |
89ae755d | 41 | #include "gcipher.h" |
42 | ||
43 | /*----- Global variables --------------------------------------------------*/ | |
44 | ||
45 | const octet des_keysz[] = { KSZ_SET, 7, 8, 0 }; | |
d03ab969 | 46 | |
47 | /*----- Main code ---------------------------------------------------------*/ | |
48 | ||
986527ae | 49 | /* --- @des_expand@ --- * |
50 | * | |
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 | |
54 | * | |
55 | * Returns: --- | |
56 | * | |
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. | |
60 | */ | |
61 | ||
62 | void des_expand(const octet *k, size_t n, uint32 *xx, uint32 *yy) | |
63 | { | |
64 | uint32 x, y, z; | |
65 | ||
66 | if (n == 8) { | |
67 | x = LOAD32(k + 0); | |
68 | y = LOAD32(k + 4); | |
69 | } else { | |
70 | x = LOAD32(k + 0); | |
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; | |
82 | } | |
83 | *xx = x; *yy = y; | |
84 | } | |
85 | ||
d03ab969 | 86 | /* --- @des_init@ --- * |
87 | * | |
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 | |
91 | * | |
92 | * Returns: --- | |
93 | * | |
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 | |
98 | * key scheduling. | |
99 | */ | |
100 | ||
101 | void des_init(des_ctx *k, const void *buf, size_t sz) | |
102 | { | |
c7c44436 MW |
103 | #define REGWD 32 |
104 | typedef uint32 regty; | |
105 | ||
106 | uint32 x, y, u, v; | |
d03ab969 | 107 | uint32 *kp = k->k; |
108 | int i; | |
109 | ||
c7c44436 | 110 | /* --- @r@ --- * |
d03ab969 | 111 | * |
112 | * Contains the rotation amounts for the key halves. | |
113 | */ | |
114 | ||
c7c44436 | 115 | static const char r[] = { |
d03ab969 | 116 | 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 |
117 | }; | |
118 | ||
119 | /* --- Extract the key into my registers --- * | |
120 | * | |
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@ | |
123 | * table. | |
124 | */ | |
125 | ||
89ae755d | 126 | KSZ_ASSERT(des, sz); |
986527ae | 127 | des_expand(buf, sz, &x, &y); |
45c0fd36 | 128 | |
c7c44436 MW |
129 | /* --- Permute using the pointless PC1 --- * |
130 | * | |
131 | * For reference, the original PC1 permutation is | |
132 | * | |
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 | |
137 | * | |
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 | |
141 | * 21 13 5 28 20 12 4 | |
142 | * | |
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.) | |
149 | */ | |
d03ab969 | 150 | |
c7c44436 MW |
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; | |
d03ab969 | 161 | |
162 | /* --- Now for the key schedule proper --- */ | |
163 | ||
164 | for (i = 0; i < 16; i++) { | |
c7c44436 | 165 | if (r[i] == 1) { |
d03ab969 | 166 | x = ((x << 1) | (x >> 27)) & 0x0fffffff; |
167 | y = ((y << 1) | (y >> 27)) & 0x0fffffff; | |
168 | } else { | |
169 | x = ((x << 2) | (x >> 26)) & 0x0fffffff; | |
170 | y = ((y << 2) | (y >> 26)) & 0x0fffffff; | |
171 | } | |
c7c44436 MW |
172 | |
173 | /* --- Apply PC2, which is another Beneš network --- * | |
174 | * | |
175 | * The original permutation is described as follows. | |
176 | * | |
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 | |
185 | * | |
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. | |
193 | * | |
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. | |
208 | * | |
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. | |
212 | */ | |
213 | ||
214 | u = x; v = y; | |
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; | |
d03ab969 | 226 | } |
c7c44436 MW |
227 | |
228 | #undef REGWD | |
d03ab969 | 229 | } |
230 | ||
231 | /* --- @des_eblk@, @des_dblk@ --- * | |
232 | * | |
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 | |
236 | * | |
237 | * Returns: --- | |
238 | * | |
239 | * Use: Low-level block encryption and decryption. | |
240 | */ | |
241 | ||
242 | void des_eblk(const des_ctx *k, const uint32 *s, uint32 *d) | |
243 | { | |
d3f33b9a MW |
244 | #define REGWD 32 |
245 | typedef uint32 regty; | |
246 | ||
d03ab969 | 247 | uint32 x = s[0], y = s[1]; |
248 | DES_IP(x, y); | |
249 | DES_EBLK(k->k, x, y, x, y); | |
250 | DES_IPINV(x, y); | |
251 | d[0] = x, d[1] = y; | |
d3f33b9a MW |
252 | |
253 | #undef REGWD | |
d03ab969 | 254 | } |
255 | ||
256 | void des_dblk(const des_ctx *k, const uint32 *s, uint32 *d) | |
257 | { | |
d3f33b9a MW |
258 | #define REGWD 32 |
259 | typedef uint32 regty; | |
260 | ||
d03ab969 | 261 | uint32 x = s[0], y = s[1]; |
262 | DES_IP(x, y); | |
263 | DES_DBLK(k->k, x, y, x, y); | |
264 | DES_IPINV(x, y); | |
265 | d[0] = x, d[1] = y; | |
d3f33b9a MW |
266 | |
267 | #undef REGWD | |
d03ab969 | 268 | } |
269 | ||
270 | BLKC_TEST(DES, des) | |
271 | ||
272 | /*----- That's all, folks -------------------------------------------------*/ |