![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to twofish.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [truecrypt] / truecrypt / crypto|
Return to twofish.c CVS log | Up to [truecrypt] / truecrypt / crypto |
1.1 root 1: /* This is an independent implementation of the encryption algorithm: */
2: /* */
3: /* Twofish by Bruce Schneier and colleagues */
4: /* */
5: /* which is a candidate algorithm in the Advanced Encryption Standard */
6: /* programme of the US National Institute of Standards and Technology. */
7: /* */
8: /* Copyright in this implementation is held by Dr B R Gladman but I */
9: /* hereby give permission for its free direct or derivative use subject */
10: /* to acknowledgment of its origin and compliance with any conditions */
11: /* that the originators of the algorithm place on its exploitation. */
12: /* */
13: /* My thanks to Doug Whiting and Niels Ferguson for comments that led */
14: /* to improvements in this implementation. */
15: /* */
16: /* Dr Brian Gladman ([email protected]) 14th January 1999 */
17:
1.1.1.2 ! root 18: /* Adapted for TrueCrypt by the TrueCrypt Foundation */
1.1 root 19:
1.1.1.2 ! root 20: #include "Twofish.h"
! 21: #include "Endian.h"
1.1 root 22:
23: #define Q_TABLES
24: #define M_TABLE
25: #define MK_TABLE
26: #define ONE_STEP
27:
28: static char *alg_name[] = { "twofish", "twofish.c", "twofish" };
29:
30: static char **cipher_name()
31: {
32: return alg_name;
33: }
34:
35: //u4byte k_len;
36: //u4byte l_key[40];
37: //u4byte s_key[4];
38:
39: /* finite field arithmetic for GF(2**8) with the modular */
40: /* polynomial x^8 + x^6 + x^5 + x^3 + 1 (0x169) */
41:
42: #define G_M 0x0169
43:
44: u1byte tab_5b[4] = { 0, G_M >> 2, G_M >> 1, (G_M >> 1) ^ (G_M >> 2) };
45: u1byte tab_ef[4] = { 0, (G_M >> 1) ^ (G_M >> 2), G_M >> 1, G_M >> 2 };
46:
47: #define ffm_01(x) (x)
48: #define ffm_5b(x) ((x) ^ ((x) >> 2) ^ tab_5b[(x) & 3])
49: #define ffm_ef(x) ((x) ^ ((x) >> 1) ^ ((x) >> 2) ^ tab_ef[(x) & 3])
50:
51: u1byte ror4[16] = { 0, 8, 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15 };
52: u1byte ashx[16] = { 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12, 5, 14, 7 };
53:
54: u1byte qt0[2][16] =
55: { { 8, 1, 7, 13, 6, 15, 3, 2, 0, 11, 5, 9, 14, 12, 10, 4 },
56: { 2, 8, 11, 13, 15, 7, 6, 14, 3, 1, 9, 4, 0, 10, 12, 5 }
57: };
58:
59: u1byte qt1[2][16] =
60: { { 14, 12, 11, 8, 1, 2, 3, 5, 15, 4, 10, 6, 7, 0, 9, 13 },
61: { 1, 14, 2, 11, 4, 12, 3, 7, 6, 13, 10, 5, 15, 9, 0, 8 }
62: };
63:
64: u1byte qt2[2][16] =
65: { { 11, 10, 5, 14, 6, 13, 9, 0, 12, 8, 15, 3, 2, 4, 7, 1 },
66: { 4, 12, 7, 5, 1, 6, 9, 10, 0, 14, 13, 8, 2, 11, 3, 15 }
67: };
68:
69: u1byte qt3[2][16] =
70: { { 13, 7, 15, 4, 1, 2, 6, 14, 9, 11, 3, 0, 8, 5, 12, 10 },
71: { 11, 9, 5, 1, 12, 3, 13, 14, 6, 4, 7, 15, 2, 0, 8, 10 }
72: };
73:
74: static u1byte qp(const u4byte n, const u1byte x)
75: { u1byte a0, a1, a2, a3, a4, b0, b1, b2, b3, b4;
76:
77: a0 = x >> 4; b0 = x & 15;
78: a1 = a0 ^ b0; b1 = ror4[b0] ^ ashx[a0];
79: a2 = qt0[n][a1]; b2 = qt1[n][b1];
80: a3 = a2 ^ b2; b3 = ror4[b2] ^ ashx[a2];
81: a4 = qt2[n][a3]; b4 = qt3[n][b3];
82: return (b4 << 4) | a4;
83: };
84:
85: #ifdef Q_TABLES
86:
87: u4byte qt_gen = 0;
88: u1byte q_tab[2][256];
89:
90: #define q(n,x) q_tab[n][x]
91:
92: static void gen_qtab(void)
93: { u4byte i;
94:
95: for(i = 0; i < 256; ++i)
96: {
97: q(0,i) = qp(0, (u1byte)i);
98: q(1,i) = qp(1, (u1byte)i);
99: }
100: };
101:
102: #else
103:
104: #define q(n,x) qp(n, x)
105:
106: #endif
107:
108: #ifdef M_TABLE
109:
110: u4byte mt_gen = 0;
111: u4byte m_tab[4][256];
112:
113: static void gen_mtab(void)
114: { u4byte i, f01, f5b, fef;
115:
116: for(i = 0; i < 256; ++i)
117: {
118: f01 = q(1,i); f5b = ffm_5b(f01); fef = ffm_ef(f01);
119: m_tab[0][i] = f01 + (f5b << 8) + (fef << 16) + (fef << 24);
120: m_tab[2][i] = f5b + (fef << 8) + (f01 << 16) + (fef << 24);
121:
122: f01 = q(0,i); f5b = ffm_5b(f01); fef = ffm_ef(f01);
123: m_tab[1][i] = fef + (fef << 8) + (f5b << 16) + (f01 << 24);
124: m_tab[3][i] = f5b + (f01 << 8) + (fef << 16) + (f5b << 24);
125: }
126: };
127:
128: #define mds(n,x) m_tab[n][x]
129:
130: #else
131:
132: #define fm_00 ffm_01
133: #define fm_10 ffm_5b
134: #define fm_20 ffm_ef
135: #define fm_30 ffm_ef
136: #define q_0(x) q(1,x)
137:
138: #define fm_01 ffm_ef
139: #define fm_11 ffm_ef
140: #define fm_21 ffm_5b
141: #define fm_31 ffm_01
142: #define q_1(x) q(0,x)
143:
144: #define fm_02 ffm_5b
145: #define fm_12 ffm_ef
146: #define fm_22 ffm_01
147: #define fm_32 ffm_ef
148: #define q_2(x) q(1,x)
149:
150: #define fm_03 ffm_5b
151: #define fm_13 ffm_01
152: #define fm_23 ffm_ef
153: #define fm_33 ffm_5b
154: #define q_3(x) q(0,x)
155:
156: #define f_0(n,x) ((u4byte)fm_0##n(x))
157: #define f_1(n,x) ((u4byte)fm_1##n(x) << 8)
158: #define f_2(n,x) ((u4byte)fm_2##n(x) << 16)
159: #define f_3(n,x) ((u4byte)fm_3##n(x) << 24)
160:
161: #define mds(n,x) f_0(n,q_##n(x)) ^ f_1(n,q_##n(x)) ^ f_2(n,q_##n(x)) ^ f_3(n,q_##n(x))
162:
163: #endif
164:
165: static u4byte h_fun(TwofishInstance *instance, const u4byte x, const u4byte key[])
166: { u4byte b0, b1, b2, b3;
167:
168: #ifndef M_TABLE
169: u4byte m5b_b0, m5b_b1, m5b_b2, m5b_b3;
170: u4byte mef_b0, mef_b1, mef_b2, mef_b3;
171: #endif
172:
173: b0 = extract_byte(x, 0); b1 = extract_byte(x, 1); b2 = extract_byte(x, 2); b3 = extract_byte(x, 3);
174:
175: switch(instance->k_len)
176: {
177: case 4: b0 = q(1, b0) ^ extract_byte(key[3],0);
178: b1 = q(0, b1) ^ extract_byte(key[3],1);
179: b2 = q(0, b2) ^ extract_byte(key[3],2);
180: b3 = q(1, b3) ^ extract_byte(key[3],3);
181: case 3: b0 = q(1, b0) ^ extract_byte(key[2],0);
182: b1 = q(1, b1) ^ extract_byte(key[2],1);
183: b2 = q(0, b2) ^ extract_byte(key[2],2);
184: b3 = q(0, b3) ^ extract_byte(key[2],3);
185: case 2: b0 = q(0,q(0,b0) ^ extract_byte(key[1],0)) ^ extract_byte(key[0],0);
186: b1 = q(0,q(1,b1) ^ extract_byte(key[1],1)) ^ extract_byte(key[0],1);
187: b2 = q(1,q(0,b2) ^ extract_byte(key[1],2)) ^ extract_byte(key[0],2);
188: b3 = q(1,q(1,b3) ^ extract_byte(key[1],3)) ^ extract_byte(key[0],3);
189: }
190: #ifdef M_TABLE
191:
192: return mds(0, b0) ^ mds(1, b1) ^ mds(2, b2) ^ mds(3, b3);
193:
194: #else
195:
196: b0 = q(1, b0); b1 = q(0, b1); b2 = q(1, b2); b3 = q(0, b3);
197: m5b_b0 = ffm_5b(b0); m5b_b1 = ffm_5b(b1); m5b_b2 = ffm_5b(b2); m5b_b3 = ffm_5b(b3);
198: mef_b0 = ffm_ef(b0); mef_b1 = ffm_ef(b1); mef_b2 = ffm_ef(b2); mef_b3 = ffm_ef(b3);
199: b0 ^= mef_b1 ^ m5b_b2 ^ m5b_b3; b3 ^= m5b_b0 ^ mef_b1 ^ mef_b2;
200: b2 ^= mef_b0 ^ m5b_b1 ^ mef_b3; b1 ^= mef_b0 ^ mef_b2 ^ m5b_b3;
201:
202: return b0 | (b3 << 8) | (b2 << 16) | (b1 << 24);
203:
204: #endif
205: };
206:
207: #ifdef MK_TABLE
208:
209: #ifdef ONE_STEP
210: //u4byte mk_tab[4][256];
211: #else
212: u1byte sb[4][256];
213: #endif
214:
215: #define q20(x) q(0,q(0,x) ^ extract_byte(key[1],0)) ^ extract_byte(key[0],0)
216: #define q21(x) q(0,q(1,x) ^ extract_byte(key[1],1)) ^ extract_byte(key[0],1)
217: #define q22(x) q(1,q(0,x) ^ extract_byte(key[1],2)) ^ extract_byte(key[0],2)
218: #define q23(x) q(1,q(1,x) ^ extract_byte(key[1],3)) ^ extract_byte(key[0],3)
219:
220: #define q30(x) q(0,q(0,q(1, x) ^ extract_byte(key[2],0)) ^ extract_byte(key[1],0)) ^ extract_byte(key[0],0)
221: #define q31(x) q(0,q(1,q(1, x) ^ extract_byte(key[2],1)) ^ extract_byte(key[1],1)) ^ extract_byte(key[0],1)
222: #define q32(x) q(1,q(0,q(0, x) ^ extract_byte(key[2],2)) ^ extract_byte(key[1],2)) ^ extract_byte(key[0],2)
223: #define q33(x) q(1,q(1,q(0, x) ^ extract_byte(key[2],3)) ^ extract_byte(key[1],3)) ^ extract_byte(key[0],3)
224:
225: #define q40(x) q(0,q(0,q(1, q(1, x) ^ extract_byte(key[3],0)) ^ extract_byte(key[2],0)) ^ extract_byte(key[1],0)) ^ extract_byte(key[0],0)
226: #define q41(x) q(0,q(1,q(1, q(0, x) ^ extract_byte(key[3],1)) ^ extract_byte(key[2],1)) ^ extract_byte(key[1],1)) ^ extract_byte(key[0],1)
227: #define q42(x) q(1,q(0,q(0, q(0, x) ^ extract_byte(key[3],2)) ^ extract_byte(key[2],2)) ^ extract_byte(key[1],2)) ^ extract_byte(key[0],2)
228: #define q43(x) q(1,q(1,q(0, q(1, x) ^ extract_byte(key[3],3)) ^ extract_byte(key[2],3)) ^ extract_byte(key[1],3)) ^ extract_byte(key[0],3)
229:
230: static gen_mk_tab(TwofishInstance *instance, u4byte key[])
231: { u4byte i;
232: u1byte by;
233:
1.1.1.2 ! root 234: // u4byte *l_key = instance->l_key;
! 235: // u4byte *s_key = instance->s_key;
1.1 root 236: u4byte *mk_tab = instance->mk_tab;
237:
238: switch(instance->k_len)
239: {
240: case 2: for(i = 0; i < 256; ++i)
241: {
242: by = (u1byte)i;
243: #ifdef ONE_STEP
244: mk_tab[0 + 4*i] = mds(0, q20(by)); mk_tab[1 + 4*i] = mds(1, q21(by));
245: mk_tab[2 + 4*i] = mds(2, q22(by)); mk_tab[3 + 4*i] = mds(3, q23(by));
246: #else
247: sb[0][i] = q20(by); sb[1][i] = q21(by);
248: sb[2][i] = q22(by); sb[3][i] = q23(by);
249: #endif
250: }
251: break;
252:
253: case 3: for(i = 0; i < 256; ++i)
254: {
255: by = (u1byte)i;
256: #ifdef ONE_STEP
257: mk_tab[0 + 4*i] = mds(0, q30(by)); mk_tab[1 + 4*i] = mds(1, q31(by));
258: mk_tab[2 + 4*i] = mds(2, q32(by)); mk_tab[3 + 4*i] = mds(3, q33(by));
259: #else
260: sb[0][i] = q30(by); sb[1][i] = q31(by);
261: sb[2][i] = q32(by); sb[3][i] = q33(by);
262: #endif
263: }
264: break;
265:
266: case 4: for(i = 0; i < 256; ++i)
267: {
268: by = (u1byte)i;
269: #ifdef ONE_STEP
270: mk_tab[0 + 4*i] = mds(0, q40(by)); mk_tab[1 + 4*i] = mds(1, q41(by));
271: mk_tab[2 + 4*i] = mds(2, q42(by)); mk_tab[3 + 4*i] = mds(3, q43(by));
272: #else
273: sb[0][i] = q40(by); sb[1][i] = q41(by);
274: sb[2][i] = q42(by); sb[3][i] = q43(by);
275: #endif
276: }
277: }
278: };
279:
280: # ifdef ONE_STEP
281: # define g0_fun(x) ( mk_tab[0 + 4*extract_byte(x,0)] ^ mk_tab[1 + 4*extract_byte(x,1)] \
282: ^ mk_tab[2 + 4*extract_byte(x,2)] ^ mk_tab[3 + 4*extract_byte(x,3)] )
283: # define g1_fun(x) ( mk_tab[0 + 4*extract_byte(x,3)] ^ mk_tab[1 + 4*extract_byte(x,0)] \
284: ^ mk_tab[2 + 4*extract_byte(x,1)] ^ mk_tab[3 + 4*extract_byte(x,2)] )
285:
286:
287: # else
288: # define g0_fun(x) ( mds(0, sb[0][extract_byte(x,0)]) ^ mds(1, sb[1][extract_byte(x,1)]) \
289: ^ mds(2, sb[2][extract_byte(x,2)]) ^ mds(3, sb[3][extract_byte(x,3)]) )
290: # define g1_fun(x) ( mds(0, sb[0][extract_byte(x,3)]) ^ mds(1, sb[1][extract_byte(x,0)]) \
291: ^ mds(2, sb[2][extract_byte(x,1)]) ^ mds(3, sb[3][extract_byte(x,2)]) )
292: # endif
293:
294: #else
295:
296: #define g0_fun(x) h_fun(instance, x,s_key)
297: #define g1_fun(x) h_fun(instance, rotl(x,8),s_key)
298:
299: #endif
300:
301: /* The (12,8) Reed Soloman code has the generator polynomial
302:
303: g(x) = x^4 + (a + 1/a) * x^3 + a * x^2 + (a + 1/a) * x + 1
304:
305: where the coefficients are in the finite field GF(2^8) with a
306: modular polynomial a^8 + a^6 + a^3 + a^2 + 1. To generate the
307: remainder we have to start with a 12th order polynomial with our
308: eight input bytes as the coefficients of the 4th to 11th terms.
309: That is:
310:
311: m[7] * x^11 + m[6] * x^10 ... + m[0] * x^4 + 0 * x^3 +... + 0
312:
313: We then multiply the generator polynomial by m[7] * x^7 and subtract
314: it - xor in GF(2^8) - from the above to eliminate the x^7 term (the
315: artihmetic on the coefficients is done in GF(2^8). We then multiply
316: the generator polynomial by x^6 * coeff(x^10) and use this to remove
317: the x^10 term. We carry on in this way until the x^4 term is removed
318: so that we are left with:
319:
320: r[3] * x^3 + r[2] * x^2 + r[1] 8 x^1 + r[0]
321:
322: which give the resulting 4 bytes of the remainder. This is equivalent
323: to the matrix multiplication in the Twofish description but much faster
324: to implement.
325:
326: */
327:
328: #define G_MOD 0x0000014d
329:
330: static u4byte mds_rem(u4byte p0, u4byte p1)
331: { u4byte i, t, u;
332:
333: for(i = 0; i < 8; ++i)
334: {
335: t = p1 >> 24; // get most significant coefficient
336:
337: p1 = (p1 << 8) | (p0 >> 24); p0 <<= 8; // shift others up
338:
339: // multiply t by a (the primitive element - i.e. left shift)
340:
341: u = (t << 1);
342:
343: if(t & 0x80) // subtract modular polynomial on overflow
344:
345: u ^= G_MOD;
346:
347: p1 ^= t ^ (u << 16); // remove t * (a * x^2 + 1)
348:
349: u ^= (t >> 1); // form u = a * t + t / a = t * (a + 1 / a);
350:
351: if(t & 0x01) // add the modular polynomial on underflow
352:
353: u ^= G_MOD >> 1;
354:
355: p1 ^= (u << 24) | (u << 8); // remove t * (a + 1/a) * (x^3 + x)
356: }
357:
358: return p1;
359: };
360:
361: /* initialise the key schedule from the user supplied key */
362:
363: u4byte *twofish_set_key(TwofishInstance *instance, const u4byte in_key[], const u4byte key_len)
364: { u4byte i, a, b, me_key[4], mo_key[4];
365: u4byte *l_key, *s_key;
366:
367: instance->l_key = (u4byte *) ((__int8 *)instance + sizeof (TwofishInstance));
368: instance->s_key = (u4byte *) ((__int8 *)instance + sizeof (TwofishInstance) + TF_L_KEY_SIZE);
369: instance->mk_tab = (u4byte *) ((__int8 *)instance + sizeof (TwofishInstance) + TF_L_KEY_SIZE + TF_S_KEY_SIZE);
370:
371: l_key = instance->l_key;
372: s_key = instance->s_key;
373:
374: #ifdef Q_TABLES
375: if(!qt_gen)
376: {
377: gen_qtab(); qt_gen = 1;
378: }
379: #endif
380:
381: #ifdef M_TABLE
382: if(!mt_gen)
383: {
384: gen_mtab(); mt_gen = 1;
385: }
386: #endif
387:
388: instance->k_len = key_len / 64; /* 2, 3 or 4 */
389:
390: for(i = 0; i < instance->k_len; ++i)
391: {
1.1.1.2 ! root 392: a = LE32(in_key[i + i]); me_key[i] = a;
! 393: b = LE32(in_key[i + i + 1]); mo_key[i] = b;
1.1 root 394: s_key[instance->k_len - i - 1] = mds_rem(a, b);
395: }
396:
397: for(i = 0; i < 40; i += 2)
398: {
399: a = 0x01010101 * i; b = a + 0x01010101;
400: a = h_fun(instance, a, me_key);
401: b = rotl(h_fun(instance, b, mo_key), 8);
402: l_key[i] = a + b;
403: l_key[i + 1] = rotl(a + 2 * b, 9);
404: }
405:
406: #ifdef MK_TABLE
407: gen_mk_tab(instance, s_key);
408: #endif
409:
410: return l_key;
411: };
412:
413: /* encrypt a block of text */
414:
415: #define f_rnd(i) \
416: t1 = g1_fun(blk[1]); t0 = g0_fun(blk[0]); \
417: blk[2] = rotr(blk[2] ^ (t0 + t1 + l_key[4 * (i) + 8]), 1); \
418: blk[3] = rotl(blk[3], 1) ^ (t0 + 2 * t1 + l_key[4 * (i) + 9]); \
419: t1 = g1_fun(blk[3]); t0 = g0_fun(blk[2]); \
420: blk[0] = rotr(blk[0] ^ (t0 + t1 + l_key[4 * (i) + 10]), 1); \
421: blk[1] = rotl(blk[1], 1) ^ (t0 + 2 * t1 + l_key[4 * (i) + 11])
422:
423: void twofish_encrypt(TwofishInstance *instance, const u4byte in_blk[4], u4byte out_blk[])
424: { u4byte t0, t1, blk[4];
425:
426: u4byte *l_key = instance->l_key;
1.1.1.2 ! root 427: // u4byte *s_key = instance->s_key;
1.1 root 428: u4byte *mk_tab = instance->mk_tab;
429:
1.1.1.2 ! root 430: blk[0] = LE32(in_blk[0]) ^ l_key[0];
! 431: blk[1] = LE32(in_blk[1]) ^ l_key[1];
! 432: blk[2] = LE32(in_blk[2]) ^ l_key[2];
! 433: blk[3] = LE32(in_blk[3]) ^ l_key[3];
1.1 root 434:
435: f_rnd(0); f_rnd(1); f_rnd(2); f_rnd(3);
436: f_rnd(4); f_rnd(5); f_rnd(6); f_rnd(7);
437:
1.1.1.2 ! root 438: out_blk[0] = LE32(blk[2] ^ l_key[4]);
! 439: out_blk[1] = LE32(blk[3] ^ l_key[5]);
! 440: out_blk[2] = LE32(blk[0] ^ l_key[6]);
! 441: out_blk[3] = LE32(blk[1] ^ l_key[7]);
1.1 root 442: };
443:
444: /* decrypt a block of text */
445:
446: #define i_rnd(i) \
447: t1 = g1_fun(blk[1]); t0 = g0_fun(blk[0]); \
448: blk[2] = rotl(blk[2], 1) ^ (t0 + t1 + l_key[4 * (i) + 10]); \
449: blk[3] = rotr(blk[3] ^ (t0 + 2 * t1 + l_key[4 * (i) + 11]), 1); \
450: t1 = g1_fun(blk[3]); t0 = g0_fun(blk[2]); \
451: blk[0] = rotl(blk[0], 1) ^ (t0 + t1 + l_key[4 * (i) + 8]); \
452: blk[1] = rotr(blk[1] ^ (t0 + 2 * t1 + l_key[4 * (i) + 9]), 1)
453:
454: void twofish_decrypt(TwofishInstance *instance, const u4byte in_blk[4], u4byte out_blk[4])
455: { u4byte t0, t1, blk[4];
456:
457: u4byte *l_key = instance->l_key;
1.1.1.2 ! root 458: // u4byte *s_key = instance->s_key;
1.1 root 459: u4byte *mk_tab = instance->mk_tab;
460:
1.1.1.2 ! root 461: blk[0] = LE32(in_blk[0]) ^ l_key[4];
! 462: blk[1] = LE32(in_blk[1]) ^ l_key[5];
! 463: blk[2] = LE32(in_blk[2]) ^ l_key[6];
! 464: blk[3] = LE32(in_blk[3]) ^ l_key[7];
1.1 root 465:
466: i_rnd(7); i_rnd(6); i_rnd(5); i_rnd(4);
467: i_rnd(3); i_rnd(2); i_rnd(1); i_rnd(0);
468:
1.1.1.2 ! root 469: out_blk[0] = LE32(blk[2] ^ l_key[0]);
! 470: out_blk[1] = LE32(blk[3] ^ l_key[1]);
! 471: out_blk[2] = LE32(blk[0] ^ l_key[2]);
! 472: out_blk[3] = LE32(blk[1] ^ l_key[3]);
1.1 root 473: };
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.