projects / u / mdw / catacomb / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Renamed from `rsa-decrypt', since the name was no longer appropriate.
[u/mdw/catacomb] / twofish.c
1 /* -*-c-*-
2 *
3 * $Id: twofish.c,v 1.2 2000/06/22 18:58:00 mdw Exp $
4 *
5 * Implementation of the Twofish cipher
6 *
7 * (c) 2000 Straylight/Edgeware
8 */
9
10 /*----- Licensing notice --------------------------------------------------*
11 *
12 * This file is part of Catacomb.
13 *
14 * Catacomb is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU Library General Public License as
16 * published by the Free Software Foundation; either version 2 of the
17 * License, or (at your option) any later version.
18 *
19 * Catacomb is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU Library General Public License for more details.
23 *
24 * You should have received a copy of the GNU Library General Public
25 * License along with Catacomb; if not, write to the Free
26 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
27 * MA 02111-1307, USA.
28 */
29
30 /*----- Revision history --------------------------------------------------*
31 *
32 * $Log: twofish.c,v $
33 * Revision 1.2 2000/06/22 18:58:00 mdw
34 * Twofish can handle keys with any byte-aligned size.
35 *
36 * Revision 1.1 2000/06/17 12:10:17 mdw
37 * New cipher.
38 *
39 */
40
41 /*----- Header files ------------------------------------------------------*/
42
43 #include <assert.h>
44
45 #include <mLib/bits.h>
46
47 #include "blkc.h"
48 #include "gcipher.h"
49 #include "twofish.h"
50 #include "twofish-tab.h"
51 #include "paranoia.h"
52
53 /*----- Global variables --------------------------------------------------*/
54
55 const octet twofish_keysz[] = { KSZ_RANGE, TWOFISH_KEYSZ, 0, 32, 1 };
56
57 /*----- Important tables --------------------------------------------------*/
58
59 static const octet q0[256] = TWOFISH_Q0, q1[256] = TWOFISH_Q1;
60 static const uint32 qmds[4][256] = TWOFISH_QMDS;
61 static const octet rslog[] = TWOFISH_RSLOG, rsexp[] = TWOFISH_RSEXP;
62 static const octet rs[32] = TWOFISH_RS;
63
64 /*----- Key initialization ------------------------------------------------*/
65
66 /* --- @h@ --- *
67 *
68 * Arguments: @uint32 x@ = input to the function
69 * @const uint32 *l@ = key values to mix in
70 * @unsigned k@ = number of key values there are
71 *
72 * Returns: The output of the function @h@.
73 *
74 * Use: Implements the Twofish function @h@.
75 */
76
77 static uint32 h(uint32 x, const uint32 *l, unsigned k)
78 {
79 /* --- Apply a series of @q@ tables to an integer --- */
80
81 # define Q(x, qa, qb, qc, qd) \
82 ((qa[((x) >> 0) & 0xff] << 0) | \
83 (qb[((x) >> 8) & 0xff] << 8) | \
84 (qc[((x) >> 16) & 0xff] << 16) | \
85 (qd[((x) >> 24) & 0xff] << 24))
86
87 /* --- Grind through the tables --- */
88
89 switch (k) {
90 case 4: x = Q(x, q1, q0, q0, q1) ^ l[3];
91 case 3: x = Q(x, q1, q1, q0, q0) ^ l[2];
92 case 2: x = Q(x, q0, q1, q0, q1) ^ l[1];
93 x = Q(x, q0, q0, q1, q1) ^ l[0];
94 break;
95 }
96
97 #undef Q
98
99 /* --- Apply the MDS matrix --- */
100
101 return (qmds[0][U8(x >> 0)] ^ qmds[1][U8(x >> 8)] ^
102 qmds[2][U8(x >> 16)] ^ qmds[3][U8(x >> 24)]);
103 }
104
105 /* --- @twofish_init@ --- *
106 *
107 * Arguments: @twofish_ctx *k@ = pointer to key block to fill in
108 * @const void *buf@ = pointer to buffer of key material
109 * @size_t sz@ = size of key material
110 *
111 * Returns: ---
112 *
113 * Use: Initializes a Twofish key buffer. Twofish accepts key sizes
114 * of up to 256 bits (32 bytes).
115 */
116
117 void twofish_init(twofish_ctx *k, const void *buf, size_t sz)
118 {
119 # define KMAX 4
120
121 uint32 mo[KMAX], me[KMAX];
122 octet s[4][KMAX];
123
124 /* --- Expand the key into the three word arrays --- */
125
126 {
127 size_t ssz;
128 const octet *p, *q;
129 octet b[32];
130 int i;
131
132 /* --- Sort out the key size --- */
133
134 KSZ_ASSERT(twofish, sz);
135 if (sz <= 16)
136 ssz = 16;
137 else if (sz <= 24)
138 ssz = 24;
139 else if (sz <= 32)
140 ssz = 32;
141 else
142 assert(((void)"This can't happen (bad key size in twofish_init)", 0));
143
144 /* --- Extend the key if necessary --- */
145
146 if (sz == ssz)
147 p = buf;
148 else {
149 memcpy(b, buf, sz);
150 memset(b + sz, 0, ssz - sz);
151 p = b;
152 }
153
154 /* --- Finally get the word count --- */
155
156 sz = ssz / 8;
157
158 /* --- Extract words from the key --- *
159 *
160 * The @s@ table, constructed using the Reed-Solomon matrix, is cut into
161 * sequences of bytes, since this is actually more useful for computing
162 * the S-boxes.
163 */
164
165 q = p;
166 for (i = 0; i < sz; i++) {
167 octet ss[4];
168 const octet *r = rs;
169 int j;
170
171 /* --- Extract the easy subkeys --- */
172
173 me[i] = LOAD32_L(q);
174 mo[i] = LOAD32_L(q + 4);
175
176 /* --- Now do the Reed-Solomon thing --- */
177
178 for (j = 0; j < 4; j++) {
179 const octet *qq = q;
180 unsigned a = 0;
181 int k;
182
183 for (k = 0; k < 8; k++) {
184 if (*qq)
185 a ^= rsexp[rslog[*qq] + *r];
186 qq++;
187 r++;
188 }
189
190 s[j][sz - 1 - i] = ss[j] = a;
191 }
192 q += 8;
193 }
194
195 /* --- Clear away the temporary buffer --- */
196
197 if (p == b)
198 BURN(b);
199 }
200
201 /* --- Construct the expanded key --- */
202
203 {
204 uint32 p = 0x01010101;
205 uint32 ip = 0;
206 int i;
207
208 for (i = 0; i < 40; i += 2) {
209 uint32 a, b;
210 a = h(ip, me, sz);
211 b = h(ip + p, mo, sz);
212 b = ROL32(b, 8);
213 a += b; b += a;
214 k->k[i] = U32(a);
215 k->k[i + 1] = ROL32(b, 9);
216 ip += 2 * p;
217 }
218 }
219
220 /* --- Construct the S-box tables --- */
221
222 {
223 unsigned i;
224 static const octet *q[4][KMAX + 1] = {
225 { q1, q0, q0, q1, q1 },
226 { q0, q0, q1, q1, q0 },
227 { q1, q1, q0, q0, q0 },
228 { q0, q1, q1, q0, q1 }
229 };
230
231 for (i = 0; i < 4; i++) {
232 unsigned j;
233 uint32 x;
234
235 for (j = 0; j < 256; j++) {
236 x = j;
237
238 /* --- Push the byte through the q tables --- */
239
240 switch (sz) {
241 case 4: x = q[i][4][x] ^ s[i][3];
242 case 3: x = q[i][3][x] ^ s[i][2];
243 case 2: x = q[i][2][x] ^ s[i][1];
244 x = q[i][1][x] ^ s[i][0];
245 break;
246 }
247
248 /* --- Write it in the key schedule --- */
249
250 k->g[i][j] = qmds[i][x];
251 }
252 }
253 }
254
255 /* --- Clear everything away --- */
256
257 BURN(me);
258 BURN(mo);
259 BURN(s);
260 }
261
262 /*----- Main encryption ---------------------------------------------------*/
263
264 /* --- Feistel function --- */
265
266 #define GG(k, t0, t1, x, y, kk) do { \
267 t0 = (k->g[0][U8(x >> 0)] ^ \
268 k->g[1][U8(x >> 8)] ^ \
269 k->g[2][U8(x >> 16)] ^ \
270 k->g[3][U8(x >> 24)]); \
271 t1 = (k->g[1][U8(y >> 0)] ^ \
272 k->g[2][U8(y >> 8)] ^ \
273 k->g[3][U8(y >> 16)] ^ \
274 k->g[0][U8(y >> 24)]); \
275 t0 += t1; \
276 t1 += t0; \
277 t0 += kk[0]; \
278 t1 += kk[1]; \
279 } while (0)
280
281 /* --- Round operations --- */
282
283 #define EROUND(k, w, x, y, z, kk) do { \
284 uint32 _t0, _t1; \
285 GG(k, _t0, _t1, w, x, kk); \
286 kk += 2; \
287 y ^= _t0; y = ROR32(y, 1); \
288 z = ROL32(z, 1); z ^= _t1; \
289 } while (0)
290
291 #define DROUND(k, w, x, y, z, kk) do { \
292 uint32 _t0, _t1; \
293 kk -= 2; \
294 GG(k, _t0, _t1, w, x, kk); \
295 y = ROL32(y, 1); y ^= _t0; \
296 z ^= _t1; z = ROR32(z, 1); \
297 } while (0)
298
299 /* --- Complete encryption functions --- */
300
301 #define EBLK(k, a, b, c, d, w, x, y, z) do { \
302 const uint32 *_kk = k->k + 8; \
303 uint32 _a = a, _b = b, _c = c, _d = d; \
304 _a ^= k->k[0]; _b ^= k->k[1]; _c ^= k->k[2]; _d ^= k->k[3]; \
305 EROUND(k, _a, _b, _c, _d, _kk); \
306 EROUND(k, _c, _d, _a, _b, _kk); \
307 EROUND(k, _a, _b, _c, _d, _kk); \
308 EROUND(k, _c, _d, _a, _b, _kk); \
309 EROUND(k, _a, _b, _c, _d, _kk); \
310 EROUND(k, _c, _d, _a, _b, _kk); \
311 EROUND(k, _a, _b, _c, _d, _kk); \
312 EROUND(k, _c, _d, _a, _b, _kk); \
313 EROUND(k, _a, _b, _c, _d, _kk); \
314 EROUND(k, _c, _d, _a, _b, _kk); \
315 EROUND(k, _a, _b, _c, _d, _kk); \
316 EROUND(k, _c, _d, _a, _b, _kk); \
317 EROUND(k, _a, _b, _c, _d, _kk); \
318 EROUND(k, _c, _d, _a, _b, _kk); \
319 EROUND(k, _a, _b, _c, _d, _kk); \
320 EROUND(k, _c, _d, _a, _b, _kk); \
321 _c ^= k->k[4]; _d ^= k->k[5]; _a ^= k->k[6]; _b ^= k->k[7]; \
322 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
323 } while (0)
324
325 #define DBLK(k, a, b, c, d, w, x, y, z) do { \
326 const uint32 *_kk = k->k + 40; \
327 uint32 _a = a, _b = b, _c = c, _d = d; \
328 _a ^= k->k[4]; _b ^= k->k[5]; _c ^= k->k[6]; _d ^= k->k[7]; \
329 DROUND(k, _a, _b, _c, _d, _kk); \
330 DROUND(k, _c, _d, _a, _b, _kk); \
331 DROUND(k, _a, _b, _c, _d, _kk); \
332 DROUND(k, _c, _d, _a, _b, _kk); \
333 DROUND(k, _a, _b, _c, _d, _kk); \
334 DROUND(k, _c, _d, _a, _b, _kk); \
335 DROUND(k, _a, _b, _c, _d, _kk); \
336 DROUND(k, _c, _d, _a, _b, _kk); \
337 DROUND(k, _a, _b, _c, _d, _kk); \
338 DROUND(k, _c, _d, _a, _b, _kk); \
339 DROUND(k, _a, _b, _c, _d, _kk); \
340 DROUND(k, _c, _d, _a, _b, _kk); \
341 DROUND(k, _a, _b, _c, _d, _kk); \
342 DROUND(k, _c, _d, _a, _b, _kk); \
343 DROUND(k, _a, _b, _c, _d, _kk); \
344 DROUND(k, _c, _d, _a, _b, _kk); \
345 _c ^= k->k[0]; _d ^= k->k[1]; _a ^= k->k[2]; _b ^= k->k[3]; \
346 w = U32(_c); x = U32(_d); y = U32(_a); z = U32(_b); \
347 } while (0)
348
349 /* --- @twofish_eblk@, @twofish_dblk@ --- *
350 *
351 * Arguments: @const twofish_ctx *k@ = pointer to key block
352 * @const uint32 s[4]@ = pointer to source block
353 * @uint32 d[4]@ = pointer to destination block
354 *
355 * Returns: ---
356 *
357 * Use: Low-level block encryption and decryption.
358 */
359
360 void twofish_eblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
361 {
362 EBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
363 }
364
365 void twofish_dblk(const twofish_ctx *k, const uint32 *s, uint32 *d)
366 {
367 DBLK(k, s[0], s[1], s[2], s[3], d[0], d[1], d[2], d[3]);
368 }
369
370 BLKC_TEST(TWOFISH, twofish)
371
372 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)