~mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
base/permute.h, utils/permute.lisp, symm/...: Formalize bit permutations.
[catacomb] / symm / des-base.h
1 /* -*-c-*-
2 *
3 * Common features for DES implementation
4 *
5 * (c) 1999 Straylight/Edgeware
6 */
7
8 /*----- Licensing notice --------------------------------------------------*
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.
16 *
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.
21 *
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
28 #ifndef CATACOMB_DES_BASE_H
29 #define CATACOMB_DES_BASE_H
30
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34
35 /*----- Header files ------------------------------------------------------*/
36
37 #include <mLib/bits.h>
38
39 #ifndef CATACOMB_PERMUTE_H
40 # include "permute.h"
41 #endif
42
43 /*----- External data -----------------------------------------------------*/
44
45 extern const uint32 des_sp[8][64];
46
47 /*----- Macros ------------------------------------------------------------*/
48
49 /* --- @DES_ROUND@ --- *
50 *
51 * This is the basic DES round function. The inputs are the two subkey
52 * halves, and the left and right block halves. Note that the block halves
53 * are rotated left one place at this point. This wraps what's meant to be
54 * the top bit around to the bottom, so I get a clear run at the S-boxes.
55 */
56
57 #define DES_ROUND(ka, kb, x, y) do { \
58 uint32 _t = (y) ^ (ka); \
59 (x) ^= des_sp[7][(_t >> 0) & 0x3f] ^ \
60 des_sp[5][(_t >> 8) & 0x3f] ^ \
61 des_sp[3][(_t >> 16) & 0x3f] ^ \
62 des_sp[1][(_t >> 24) & 0x3f]; \
63 _t = ROR32((y), 4) ^ (kb); \
64 (x) ^= des_sp[6][(_t >> 0) & 0x3f] ^ \
65 des_sp[4][(_t >> 8) & 0x3f] ^ \
66 des_sp[2][(_t >> 16) & 0x3f] ^ \
67 des_sp[0][(_t >> 24) & 0x3f]; \
68 } while (0)
69
70 /* --- @DES_IP@, @DES_IPINV@ --- *
71 *
72 * The cryptographically useless initial and final permutations. The initial
73 * permutation also rotates the two block halves left by one place. This is
74 * undone by the inverse permutation at the end.
75 *
76 * The initial permutation is traditionally given by the table
77 *
78 * 58 50 42 34 26 18 10 2
79 * 60 52 44 36 28 20 12 4
80 * 62 54 46 38 30 22 14 6
81 * 64 56 48 40 32 24 16 8
82 * 57 49 41 33 25 17 9 1
83 * 59 51 43 35 27 19 11 3
84 * 61 53 45 37 29 21 13 5
85 * 63 55 47 39 31 23 15 7
86 *
87 * The bit numbering is terrible. If the two halves are X and Y, then the
88 * numbering starts with the most significant bit of X, which is bit 1,
89 * working down towards the least significant bit, and then continuing with
90 * the bits of Y, again in order of decreasing significance. The table
91 * entries are in this same order, indicating that `bit 1' of the output is
92 * `bit 58' of the input and so on.
93 *
94 * I opt instead to number the bits starting from the least significant bit
95 * of Y, which is bit 0, up to the most significant bit of X, which is
96 * bit 63. This means that we need to reverse the table (because we're going
97 * to read it in the other direction) and subtract each entry from 64 (to
98 * correct the bit numbering). The resulting table is
99 *
100 * 57 49 41 33 25 17 9 1
101 * 59 51 43 35 27 19 11 3
102 * 61 53 45 37 29 21 13 5
103 * 63 55 47 39 31 23 15 7
104 * 56 48 40 32 24 16 8 0
105 * 58 50 42 34 26 18 10 2
106 * 60 52 44 36 28 20 12 4
107 * 62 54 46 38 30 22 14 6
108 *
109 * which, interestingly, is /also/ what you get if you just subtract one from
110 * each of the original table's entries.
111 *
112 * If we look at this table in binary, the patterns are much clearer.
113 *
114 * 111001 110001 101001 100001 011001 010001 001001 000001
115 * 111011 110011 101011 100011 011011 010011 001011 000011
116 * 111101 110101 101101 100101 011101 010101 001101 000101
117 * 111111 110111 101111 100111 011111 010111 001111 000111
118 * 111000 110000 101000 100000 011000 010000 001000 000000
119 * 111010 110010 101010 100010 011010 010010 001010 000010
120 * 111100 110100 101100 100100 011100 010100 001100 000100
121 * 111110 110110 101110 100110 011110 010110 001110 000110
122 *
123 * We can implement this efficiently using our permutation machinery.
124 * Writing ~k for index bit @k@ inverted, this permutation reflects the index
125 * transformation given by ~0, 2, 1, ~5, ~4, ~3. The following sequence of
126 * operations is traditional. Essentially this is an antitranspose -- a
127 * reflection about the antidiagonal -- followed by a couple of fixup stages.
128 */
129
130 #define DES_IP(x, y) do { /* 5, 4, 3, 2, 1, 0 */ \
131 TWIZZLE_XCPL (x, y, 2); /* ~2, 4, 3, ~5, 1, 0 */ \
132 SWIZZLE_XCPL2(x, y, 1, 4); /* ~2, ~1, 3, ~5, ~4, 0 */ \
133 SWIZZLE_XCPL2(x, y, 0, 3); /* ~2, ~1, ~0, ~5, ~4, ~3 */ \
134 SWIZZLE_XCPL2(x, y, 3, 4); /* ~2, 0, 1, ~5, ~4, ~3 */ \
135 TWIZZLE_XCPL (x, y, 4); /* ~0, 2, 1, ~5, ~4, ~3 */ \
136 x = ROL32(x, 1); y = ROL32(y, 1); \
137 } while (0)
138
139 #define DES_IPINV(x, y) do { \
140 x = ROR32(x, 1); y = ROR32(y, 1); /* ~0, 2, 1, ~5, ~4, ~3 */ \
141 TWIZZLE_XCPL (x, y, 4); /* ~2, 0, 1, ~5, ~4, ~3 */ \
142 SWIZZLE_XCPL2(x, y, 3, 4); /* ~2, ~1, ~0, ~5, ~4, ~3 */ \
143 SWIZZLE_XCPL2(x, y, 0, 3); /* ~2, ~1, 3, ~5, ~4, 0 */ \
144 SWIZZLE_XCPL2(x, y, 1, 4); /* ~2, 4, 3, ~5, 1, 0 */ \
145 TWIZZLE_XCPL (x, y, 2); /* 5, 4, 3, 2, 1, 0 */ \
146 } while (0)
147
148 /* --- @DES_EBLK@, @DES_DBLK@ --- *
149 *
150 * Whole block encryption and decryption.
151 */
152
153 #define DES_EBLK(k, a, b, c, d) do { \
154 const uint32 *_k = (k); \
155 uint32 _x = (a), _y = (b); \
156 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
157 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
158 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
159 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
160 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
161 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
162 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
163 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
164 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
165 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
166 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
167 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
168 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
169 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
170 DES_ROUND(_k[0], _k[1], _x, _y); _k += 2; \
171 DES_ROUND(_k[0], _k[1], _y, _x); _k += 2; \
172 (c) = _y; \
173 (d) = _x; \
174 } while (0)
175
176 #define DES_DBLK(k, a, b, c, d) do { \
177 const uint32 *_k = (k) + 32; \
178 uint32 _x = (a), _y = (b); \
179 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
180 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
181 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
182 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
183 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
184 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
185 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
186 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
187 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
188 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
189 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
190 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
191 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
192 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
193 _k -= 2; DES_ROUND(_k[0], _k[1], _x, _y); \
194 _k -= 2; DES_ROUND(_k[0], _k[1], _y, _x); \
195 (c) = _y; \
196 (d) = _x; \
197 } while (0)
198
199 /*----- That's all, folks -------------------------------------------------*/
200
201 #ifdef __cplusplus
202 }
203 #endif
204
205 #endif
Catacomb cryptographic library