source: grub-pc/trunk/fuentes/grub-core/lib/libgcrypt/cipher/twofish.c @ 22

Last change on this file since 22 was 22, checked in by mabarracus, 4 years ago

updated version and apply net.ifnames=0 into debian/rules

File size: 50.1 KB
Line 
1/* Twofish for GPG
2 * Copyright (C) 1998, 2002, 2003 Free Software Foundation, Inc.
3 * Written by Matthew Skala <mskala@ansuz.sooke.bc.ca>, July 26, 1998
4 * 256-bit key length added March 20, 1999
5 * Some modifications to reduce the text size by Werner Koch, April, 1998
6 *
7 * This file is part of Libgcrypt.
8 *
9 * Libgcrypt is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU Lesser General Public License as
11 * published by the Free Software Foundation; either version 2.1 of
12 * the License, or (at your option) any later version.
13 *
14 * Libgcrypt is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17 * GNU Lesser General Public License for more details.
18 *
19 * You should have received a copy of the GNU Lesser General Public
20 * License along with this program; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
22 ********************************************************************
23 *
24 * This code is a "clean room" implementation, written from the paper
25 * _Twofish: A 128-Bit Block Cipher_ by Bruce Schneier, John Kelsey,
26 * Doug Whiting, David Wagner, Chris Hall, and Niels Ferguson, available
27 * through http://www.counterpane.com/twofish.html
28 *
29 * For background information on multiplication in finite fields, used for
30 * the matrix operations in the key schedule, see the book _Contemporary
31 * Abstract Algebra_ by Joseph A. Gallian, especially chapter 22 in the
32 * Third Edition.
33 *
34 * Only the 128- and 256-bit key sizes are supported.  This code is intended
35 * for GNU C on a 32-bit system, but it should work almost anywhere.  Loops
36 * are unrolled, precomputation tables are used, etc., for maximum speed at
37 * some cost in memory consumption. */
38
39#include <config.h>
40#include <stdio.h>
41#include <stdlib.h>
42#include <string.h> /* for memcmp() */
43
44#include "types.h"  /* for byte and u32 typedefs */
45#include "g10lib.h"
46#include "cipher.h"
47
48/* Prototype for the self-test function. */
49static const char *selftest(void);
50
51/* Structure for an expanded Twofish key.  s contains the key-dependent
52 * S-boxes composed with the MDS matrix; w contains the eight "whitening"
53 * subkeys, K[0] through K[7].  k holds the remaining, "round" subkeys.  Note
54 * that k[i] corresponds to what the Twofish paper calls K[i+8]. */
55typedef struct {
56   u32 s[4][256], w[8], k[32];
57} TWOFISH_context;
58
59/* These two tables are the q0 and q1 permutations, exactly as described in
60 * the Twofish paper. */
61
62static const byte q0[256] = {
63   0xA9, 0x67, 0xB3, 0xE8, 0x04, 0xFD, 0xA3, 0x76, 0x9A, 0x92, 0x80, 0x78,
64   0xE4, 0xDD, 0xD1, 0x38, 0x0D, 0xC6, 0x35, 0x98, 0x18, 0xF7, 0xEC, 0x6C,
65   0x43, 0x75, 0x37, 0x26, 0xFA, 0x13, 0x94, 0x48, 0xF2, 0xD0, 0x8B, 0x30,
66   0x84, 0x54, 0xDF, 0x23, 0x19, 0x5B, 0x3D, 0x59, 0xF3, 0xAE, 0xA2, 0x82,
67   0x63, 0x01, 0x83, 0x2E, 0xD9, 0x51, 0x9B, 0x7C, 0xA6, 0xEB, 0xA5, 0xBE,
68   0x16, 0x0C, 0xE3, 0x61, 0xC0, 0x8C, 0x3A, 0xF5, 0x73, 0x2C, 0x25, 0x0B,
69   0xBB, 0x4E, 0x89, 0x6B, 0x53, 0x6A, 0xB4, 0xF1, 0xE1, 0xE6, 0xBD, 0x45,
70   0xE2, 0xF4, 0xB6, 0x66, 0xCC, 0x95, 0x03, 0x56, 0xD4, 0x1C, 0x1E, 0xD7,
71   0xFB, 0xC3, 0x8E, 0xB5, 0xE9, 0xCF, 0xBF, 0xBA, 0xEA, 0x77, 0x39, 0xAF,
72   0x33, 0xC9, 0x62, 0x71, 0x81, 0x79, 0x09, 0xAD, 0x24, 0xCD, 0xF9, 0xD8,
73   0xE5, 0xC5, 0xB9, 0x4D, 0x44, 0x08, 0x86, 0xE7, 0xA1, 0x1D, 0xAA, 0xED,
74   0x06, 0x70, 0xB2, 0xD2, 0x41, 0x7B, 0xA0, 0x11, 0x31, 0xC2, 0x27, 0x90,
75   0x20, 0xF6, 0x60, 0xFF, 0x96, 0x5C, 0xB1, 0xAB, 0x9E, 0x9C, 0x52, 0x1B,
76   0x5F, 0x93, 0x0A, 0xEF, 0x91, 0x85, 0x49, 0xEE, 0x2D, 0x4F, 0x8F, 0x3B,
77   0x47, 0x87, 0x6D, 0x46, 0xD6, 0x3E, 0x69, 0x64, 0x2A, 0xCE, 0xCB, 0x2F,
78   0xFC, 0x97, 0x05, 0x7A, 0xAC, 0x7F, 0xD5, 0x1A, 0x4B, 0x0E, 0xA7, 0x5A,
79   0x28, 0x14, 0x3F, 0x29, 0x88, 0x3C, 0x4C, 0x02, 0xB8, 0xDA, 0xB0, 0x17,
80   0x55, 0x1F, 0x8A, 0x7D, 0x57, 0xC7, 0x8D, 0x74, 0xB7, 0xC4, 0x9F, 0x72,
81   0x7E, 0x15, 0x22, 0x12, 0x58, 0x07, 0x99, 0x34, 0x6E, 0x50, 0xDE, 0x68,
82   0x65, 0xBC, 0xDB, 0xF8, 0xC8, 0xA8, 0x2B, 0x40, 0xDC, 0xFE, 0x32, 0xA4,
83   0xCA, 0x10, 0x21, 0xF0, 0xD3, 0x5D, 0x0F, 0x00, 0x6F, 0x9D, 0x36, 0x42,
84   0x4A, 0x5E, 0xC1, 0xE0
85};
86
87static const byte q1[256] = {
88   0x75, 0xF3, 0xC6, 0xF4, 0xDB, 0x7B, 0xFB, 0xC8, 0x4A, 0xD3, 0xE6, 0x6B,
89   0x45, 0x7D, 0xE8, 0x4B, 0xD6, 0x32, 0xD8, 0xFD, 0x37, 0x71, 0xF1, 0xE1,
90   0x30, 0x0F, 0xF8, 0x1B, 0x87, 0xFA, 0x06, 0x3F, 0x5E, 0xBA, 0xAE, 0x5B,
91   0x8A, 0x00, 0xBC, 0x9D, 0x6D, 0xC1, 0xB1, 0x0E, 0x80, 0x5D, 0xD2, 0xD5,
92   0xA0, 0x84, 0x07, 0x14, 0xB5, 0x90, 0x2C, 0xA3, 0xB2, 0x73, 0x4C, 0x54,
93   0x92, 0x74, 0x36, 0x51, 0x38, 0xB0, 0xBD, 0x5A, 0xFC, 0x60, 0x62, 0x96,
94   0x6C, 0x42, 0xF7, 0x10, 0x7C, 0x28, 0x27, 0x8C, 0x13, 0x95, 0x9C, 0xC7,
95   0x24, 0x46, 0x3B, 0x70, 0xCA, 0xE3, 0x85, 0xCB, 0x11, 0xD0, 0x93, 0xB8,
96   0xA6, 0x83, 0x20, 0xFF, 0x9F, 0x77, 0xC3, 0xCC, 0x03, 0x6F, 0x08, 0xBF,
97   0x40, 0xE7, 0x2B, 0xE2, 0x79, 0x0C, 0xAA, 0x82, 0x41, 0x3A, 0xEA, 0xB9,
98   0xE4, 0x9A, 0xA4, 0x97, 0x7E, 0xDA, 0x7A, 0x17, 0x66, 0x94, 0xA1, 0x1D,
99   0x3D, 0xF0, 0xDE, 0xB3, 0x0B, 0x72, 0xA7, 0x1C, 0xEF, 0xD1, 0x53, 0x3E,
100   0x8F, 0x33, 0x26, 0x5F, 0xEC, 0x76, 0x2A, 0x49, 0x81, 0x88, 0xEE, 0x21,
101   0xC4, 0x1A, 0xEB, 0xD9, 0xC5, 0x39, 0x99, 0xCD, 0xAD, 0x31, 0x8B, 0x01,
102   0x18, 0x23, 0xDD, 0x1F, 0x4E, 0x2D, 0xF9, 0x48, 0x4F, 0xF2, 0x65, 0x8E,
103   0x78, 0x5C, 0x58, 0x19, 0x8D, 0xE5, 0x98, 0x57, 0x67, 0x7F, 0x05, 0x64,
104   0xAF, 0x63, 0xB6, 0xFE, 0xF5, 0xB7, 0x3C, 0xA5, 0xCE, 0xE9, 0x68, 0x44,
105   0xE0, 0x4D, 0x43, 0x69, 0x29, 0x2E, 0xAC, 0x15, 0x59, 0xA8, 0x0A, 0x9E,
106   0x6E, 0x47, 0xDF, 0x34, 0x35, 0x6A, 0xCF, 0xDC, 0x22, 0xC9, 0xC0, 0x9B,
107   0x89, 0xD4, 0xED, 0xAB, 0x12, 0xA2, 0x0D, 0x52, 0xBB, 0x02, 0x2F, 0xA9,
108   0xD7, 0x61, 0x1E, 0xB4, 0x50, 0x04, 0xF6, 0xC2, 0x16, 0x25, 0x86, 0x56,
109   0x55, 0x09, 0xBE, 0x91
110};
111
112/* These MDS tables are actually tables of MDS composed with q0 and q1,
113 * because it is only ever used that way and we can save some time by
114 * precomputing.  Of course the main saving comes from precomputing the
115 * GF(2^8) multiplication involved in the MDS matrix multiply; by looking
116 * things up in these tables we reduce the matrix multiply to four lookups
117 * and three XORs.  Semi-formally, the definition of these tables is:
118 * mds[0][i] = MDS (q1[i] 0 0 0)^T  mds[1][i] = MDS (0 q0[i] 0 0)^T
119 * mds[2][i] = MDS (0 0 q1[i] 0)^T  mds[3][i] = MDS (0 0 0 q0[i])^T
120 * where ^T means "transpose", the matrix multiply is performed in GF(2^8)
121 * represented as GF(2)[x]/v(x) where v(x)=x^8+x^6+x^5+x^3+1 as described
122 * by Schneier et al, and I'm casually glossing over the byte/word
123 * conversion issues. */
124
125static const u32 mds[4][256] = {
126   {0xBCBC3275, 0xECEC21F3, 0x202043C6, 0xB3B3C9F4, 0xDADA03DB, 0x02028B7B,
127    0xE2E22BFB, 0x9E9EFAC8, 0xC9C9EC4A, 0xD4D409D3, 0x18186BE6, 0x1E1E9F6B,
128    0x98980E45, 0xB2B2387D, 0xA6A6D2E8, 0x2626B74B, 0x3C3C57D6, 0x93938A32,
129    0x8282EED8, 0x525298FD, 0x7B7BD437, 0xBBBB3771, 0x5B5B97F1, 0x474783E1,
130    0x24243C30, 0x5151E20F, 0xBABAC6F8, 0x4A4AF31B, 0xBFBF4887, 0x0D0D70FA,
131    0xB0B0B306, 0x7575DE3F, 0xD2D2FD5E, 0x7D7D20BA, 0x666631AE, 0x3A3AA35B,
132    0x59591C8A, 0x00000000, 0xCDCD93BC, 0x1A1AE09D, 0xAEAE2C6D, 0x7F7FABC1,
133    0x2B2BC7B1, 0xBEBEB90E, 0xE0E0A080, 0x8A8A105D, 0x3B3B52D2, 0x6464BAD5,
134    0xD8D888A0, 0xE7E7A584, 0x5F5FE807, 0x1B1B1114, 0x2C2CC2B5, 0xFCFCB490,
135    0x3131272C, 0x808065A3, 0x73732AB2, 0x0C0C8173, 0x79795F4C, 0x6B6B4154,
136    0x4B4B0292, 0x53536974, 0x94948F36, 0x83831F51, 0x2A2A3638, 0xC4C49CB0,
137    0x2222C8BD, 0xD5D5F85A, 0xBDBDC3FC, 0x48487860, 0xFFFFCE62, 0x4C4C0796,
138    0x4141776C, 0xC7C7E642, 0xEBEB24F7, 0x1C1C1410, 0x5D5D637C, 0x36362228,
139    0x6767C027, 0xE9E9AF8C, 0x4444F913, 0x1414EA95, 0xF5F5BB9C, 0xCFCF18C7,
140    0x3F3F2D24, 0xC0C0E346, 0x7272DB3B, 0x54546C70, 0x29294CCA, 0xF0F035E3,
141    0x0808FE85, 0xC6C617CB, 0xF3F34F11, 0x8C8CE4D0, 0xA4A45993, 0xCACA96B8,
142    0x68683BA6, 0xB8B84D83, 0x38382820, 0xE5E52EFF, 0xADAD569F, 0x0B0B8477,
143    0xC8C81DC3, 0x9999FFCC, 0x5858ED03, 0x19199A6F, 0x0E0E0A08, 0x95957EBF,
144    0x70705040, 0xF7F730E7, 0x6E6ECF2B, 0x1F1F6EE2, 0xB5B53D79, 0x09090F0C,
145    0x616134AA, 0x57571682, 0x9F9F0B41, 0x9D9D803A, 0x111164EA, 0x2525CDB9,
146    0xAFAFDDE4, 0x4545089A, 0xDFDF8DA4, 0xA3A35C97, 0xEAEAD57E, 0x353558DA,
147    0xEDEDD07A, 0x4343FC17, 0xF8F8CB66, 0xFBFBB194, 0x3737D3A1, 0xFAFA401D,
148    0xC2C2683D, 0xB4B4CCF0, 0x32325DDE, 0x9C9C71B3, 0x5656E70B, 0xE3E3DA72,
149    0x878760A7, 0x15151B1C, 0xF9F93AEF, 0x6363BFD1, 0x3434A953, 0x9A9A853E,
150    0xB1B1428F, 0x7C7CD133, 0x88889B26, 0x3D3DA65F, 0xA1A1D7EC, 0xE4E4DF76,
151    0x8181942A, 0x91910149, 0x0F0FFB81, 0xEEEEAA88, 0x161661EE, 0xD7D77321,
152    0x9797F5C4, 0xA5A5A81A, 0xFEFE3FEB, 0x6D6DB5D9, 0x7878AEC5, 0xC5C56D39,
153    0x1D1DE599, 0x7676A4CD, 0x3E3EDCAD, 0xCBCB6731, 0xB6B6478B, 0xEFEF5B01,
154    0x12121E18, 0x6060C523, 0x6A6AB0DD, 0x4D4DF61F, 0xCECEE94E, 0xDEDE7C2D,
155    0x55559DF9, 0x7E7E5A48, 0x2121B24F, 0x03037AF2, 0xA0A02665, 0x5E5E198E,
156    0x5A5A6678, 0x65654B5C, 0x62624E58, 0xFDFD4519, 0x0606F48D, 0x404086E5,
157    0xF2F2BE98, 0x3333AC57, 0x17179067, 0x05058E7F, 0xE8E85E05, 0x4F4F7D64,
158    0x89896AAF, 0x10109563, 0x74742FB6, 0x0A0A75FE, 0x5C5C92F5, 0x9B9B74B7,
159    0x2D2D333C, 0x3030D6A5, 0x2E2E49CE, 0x494989E9, 0x46467268, 0x77775544,
160    0xA8A8D8E0, 0x9696044D, 0x2828BD43, 0xA9A92969, 0xD9D97929, 0x8686912E,
161    0xD1D187AC, 0xF4F44A15, 0x8D8D1559, 0xD6D682A8, 0xB9B9BC0A, 0x42420D9E,
162    0xF6F6C16E, 0x2F2FB847, 0xDDDD06DF, 0x23233934, 0xCCCC6235, 0xF1F1C46A,
163    0xC1C112CF, 0x8585EBDC, 0x8F8F9E22, 0x7171A1C9, 0x9090F0C0, 0xAAAA539B,
164    0x0101F189, 0x8B8BE1D4, 0x4E4E8CED, 0x8E8E6FAB, 0xABABA212, 0x6F6F3EA2,
165    0xE6E6540D, 0xDBDBF252, 0x92927BBB, 0xB7B7B602, 0x6969CA2F, 0x3939D9A9,
166    0xD3D30CD7, 0xA7A72361, 0xA2A2AD1E, 0xC3C399B4, 0x6C6C4450, 0x07070504,
167    0x04047FF6, 0x272746C2, 0xACACA716, 0xD0D07625, 0x50501386, 0xDCDCF756,
168    0x84841A55, 0xE1E15109, 0x7A7A25BE, 0x1313EF91},
169
170   {0xA9D93939, 0x67901717, 0xB3719C9C, 0xE8D2A6A6, 0x04050707, 0xFD985252,
171    0xA3658080, 0x76DFE4E4, 0x9A084545, 0x92024B4B, 0x80A0E0E0, 0x78665A5A,
172    0xE4DDAFAF, 0xDDB06A6A, 0xD1BF6363, 0x38362A2A, 0x0D54E6E6, 0xC6432020,
173    0x3562CCCC, 0x98BEF2F2, 0x181E1212, 0xF724EBEB, 0xECD7A1A1, 0x6C774141,
174    0x43BD2828, 0x7532BCBC, 0x37D47B7B, 0x269B8888, 0xFA700D0D, 0x13F94444,
175    0x94B1FBFB, 0x485A7E7E, 0xF27A0303, 0xD0E48C8C, 0x8B47B6B6, 0x303C2424,
176    0x84A5E7E7, 0x54416B6B, 0xDF06DDDD, 0x23C56060, 0x1945FDFD, 0x5BA33A3A,
177    0x3D68C2C2, 0x59158D8D, 0xF321ECEC, 0xAE316666, 0xA23E6F6F, 0x82165757,
178    0x63951010, 0x015BEFEF, 0x834DB8B8, 0x2E918686, 0xD9B56D6D, 0x511F8383,
179    0x9B53AAAA, 0x7C635D5D, 0xA63B6868, 0xEB3FFEFE, 0xA5D63030, 0xBE257A7A,
180    0x16A7ACAC, 0x0C0F0909, 0xE335F0F0, 0x6123A7A7, 0xC0F09090, 0x8CAFE9E9,
181    0x3A809D9D, 0xF5925C5C, 0x73810C0C, 0x2C273131, 0x2576D0D0, 0x0BE75656,
182    0xBB7B9292, 0x4EE9CECE, 0x89F10101, 0x6B9F1E1E, 0x53A93434, 0x6AC4F1F1,
183    0xB499C3C3, 0xF1975B5B, 0xE1834747, 0xE66B1818, 0xBDC82222, 0x450E9898,
184    0xE26E1F1F, 0xF4C9B3B3, 0xB62F7474, 0x66CBF8F8, 0xCCFF9999, 0x95EA1414,
185    0x03ED5858, 0x56F7DCDC, 0xD4E18B8B, 0x1C1B1515, 0x1EADA2A2, 0xD70CD3D3,
186    0xFB2BE2E2, 0xC31DC8C8, 0x8E195E5E, 0xB5C22C2C, 0xE9894949, 0xCF12C1C1,
187    0xBF7E9595, 0xBA207D7D, 0xEA641111, 0x77840B0B, 0x396DC5C5, 0xAF6A8989,
188    0x33D17C7C, 0xC9A17171, 0x62CEFFFF, 0x7137BBBB, 0x81FB0F0F, 0x793DB5B5,
189    0x0951E1E1, 0xADDC3E3E, 0x242D3F3F, 0xCDA47676, 0xF99D5555, 0xD8EE8282,
190    0xE5864040, 0xC5AE7878, 0xB9CD2525, 0x4D049696, 0x44557777, 0x080A0E0E,
191    0x86135050, 0xE730F7F7, 0xA1D33737, 0x1D40FAFA, 0xAA346161, 0xED8C4E4E,
192    0x06B3B0B0, 0x706C5454, 0xB22A7373, 0xD2523B3B, 0x410B9F9F, 0x7B8B0202,
193    0xA088D8D8, 0x114FF3F3, 0x3167CBCB, 0xC2462727, 0x27C06767, 0x90B4FCFC,
194    0x20283838, 0xF67F0404, 0x60784848, 0xFF2EE5E5, 0x96074C4C, 0x5C4B6565,
195    0xB1C72B2B, 0xAB6F8E8E, 0x9E0D4242, 0x9CBBF5F5, 0x52F2DBDB, 0x1BF34A4A,
196    0x5FA63D3D, 0x9359A4A4, 0x0ABCB9B9, 0xEF3AF9F9, 0x91EF1313, 0x85FE0808,
197    0x49019191, 0xEE611616, 0x2D7CDEDE, 0x4FB22121, 0x8F42B1B1, 0x3BDB7272,
198    0x47B82F2F, 0x8748BFBF, 0x6D2CAEAE, 0x46E3C0C0, 0xD6573C3C, 0x3E859A9A,
199    0x6929A9A9, 0x647D4F4F, 0x2A948181, 0xCE492E2E, 0xCB17C6C6, 0x2FCA6969,
200    0xFCC3BDBD, 0x975CA3A3, 0x055EE8E8, 0x7AD0EDED, 0xAC87D1D1, 0x7F8E0505,
201    0xD5BA6464, 0x1AA8A5A5, 0x4BB72626, 0x0EB9BEBE, 0xA7608787, 0x5AF8D5D5,
202    0x28223636, 0x14111B1B, 0x3FDE7575, 0x2979D9D9, 0x88AAEEEE, 0x3C332D2D,
203    0x4C5F7979, 0x02B6B7B7, 0xB896CACA, 0xDA583535, 0xB09CC4C4, 0x17FC4343,
204    0x551A8484, 0x1FF64D4D, 0x8A1C5959, 0x7D38B2B2, 0x57AC3333, 0xC718CFCF,
205    0x8DF40606, 0x74695353, 0xB7749B9B, 0xC4F59797, 0x9F56ADAD, 0x72DAE3E3,
206    0x7ED5EAEA, 0x154AF4F4, 0x229E8F8F, 0x12A2ABAB, 0x584E6262, 0x07E85F5F,
207    0x99E51D1D, 0x34392323, 0x6EC1F6F6, 0x50446C6C, 0xDE5D3232, 0x68724646,
208    0x6526A0A0, 0xBC93CDCD, 0xDB03DADA, 0xF8C6BABA, 0xC8FA9E9E, 0xA882D6D6,
209    0x2BCF6E6E, 0x40507070, 0xDCEB8585, 0xFE750A0A, 0x328A9393, 0xA48DDFDF,
210    0xCA4C2929, 0x10141C1C, 0x2173D7D7, 0xF0CCB4B4, 0xD309D4D4, 0x5D108A8A,
211    0x0FE25151, 0x00000000, 0x6F9A1919, 0x9DE01A1A, 0x368F9494, 0x42E6C7C7,
212    0x4AECC9C9, 0x5EFDD2D2, 0xC1AB7F7F, 0xE0D8A8A8},
213
214   {0xBC75BC32, 0xECF3EC21, 0x20C62043, 0xB3F4B3C9, 0xDADBDA03, 0x027B028B,
215    0xE2FBE22B, 0x9EC89EFA, 0xC94AC9EC, 0xD4D3D409, 0x18E6186B, 0x1E6B1E9F,
216    0x9845980E, 0xB27DB238, 0xA6E8A6D2, 0x264B26B7, 0x3CD63C57, 0x9332938A,
217    0x82D882EE, 0x52FD5298, 0x7B377BD4, 0xBB71BB37, 0x5BF15B97, 0x47E14783,
218    0x2430243C, 0x510F51E2, 0xBAF8BAC6, 0x4A1B4AF3, 0xBF87BF48, 0x0DFA0D70,
219    0xB006B0B3, 0x753F75DE, 0xD25ED2FD, 0x7DBA7D20, 0x66AE6631, 0x3A5B3AA3,
220    0x598A591C, 0x00000000, 0xCDBCCD93, 0x1A9D1AE0, 0xAE6DAE2C, 0x7FC17FAB,
221    0x2BB12BC7, 0xBE0EBEB9, 0xE080E0A0, 0x8A5D8A10, 0x3BD23B52, 0x64D564BA,
222    0xD8A0D888, 0xE784E7A5, 0x5F075FE8, 0x1B141B11, 0x2CB52CC2, 0xFC90FCB4,
223    0x312C3127, 0x80A38065, 0x73B2732A, 0x0C730C81, 0x794C795F, 0x6B546B41,
224    0x4B924B02, 0x53745369, 0x9436948F, 0x8351831F, 0x2A382A36, 0xC4B0C49C,
225    0x22BD22C8, 0xD55AD5F8, 0xBDFCBDC3, 0x48604878, 0xFF62FFCE, 0x4C964C07,
226    0x416C4177, 0xC742C7E6, 0xEBF7EB24, 0x1C101C14, 0x5D7C5D63, 0x36283622,
227    0x672767C0, 0xE98CE9AF, 0x441344F9, 0x149514EA, 0xF59CF5BB, 0xCFC7CF18,
228    0x3F243F2D, 0xC046C0E3, 0x723B72DB, 0x5470546C, 0x29CA294C, 0xF0E3F035,
229    0x088508FE, 0xC6CBC617, 0xF311F34F, 0x8CD08CE4, 0xA493A459, 0xCAB8CA96,
230    0x68A6683B, 0xB883B84D, 0x38203828, 0xE5FFE52E, 0xAD9FAD56, 0x0B770B84,
231    0xC8C3C81D, 0x99CC99FF, 0x580358ED, 0x196F199A, 0x0E080E0A, 0x95BF957E,
232    0x70407050, 0xF7E7F730, 0x6E2B6ECF, 0x1FE21F6E, 0xB579B53D, 0x090C090F,
233    0x61AA6134, 0x57825716, 0x9F419F0B, 0x9D3A9D80, 0x11EA1164, 0x25B925CD,
234    0xAFE4AFDD, 0x459A4508, 0xDFA4DF8D, 0xA397A35C, 0xEA7EEAD5, 0x35DA3558,
235    0xED7AEDD0, 0x431743FC, 0xF866F8CB, 0xFB94FBB1, 0x37A137D3, 0xFA1DFA40,
236    0xC23DC268, 0xB4F0B4CC, 0x32DE325D, 0x9CB39C71, 0x560B56E7, 0xE372E3DA,
237    0x87A78760, 0x151C151B, 0xF9EFF93A, 0x63D163BF, 0x345334A9, 0x9A3E9A85,
238    0xB18FB142, 0x7C337CD1, 0x8826889B, 0x3D5F3DA6, 0xA1ECA1D7, 0xE476E4DF,
239    0x812A8194, 0x91499101, 0x0F810FFB, 0xEE88EEAA, 0x16EE1661, 0xD721D773,
240    0x97C497F5, 0xA51AA5A8, 0xFEEBFE3F, 0x6DD96DB5, 0x78C578AE, 0xC539C56D,
241    0x1D991DE5, 0x76CD76A4, 0x3EAD3EDC, 0xCB31CB67, 0xB68BB647, 0xEF01EF5B,
242    0x1218121E, 0x602360C5, 0x6ADD6AB0, 0x4D1F4DF6, 0xCE4ECEE9, 0xDE2DDE7C,
243    0x55F9559D, 0x7E487E5A, 0x214F21B2, 0x03F2037A, 0xA065A026, 0x5E8E5E19,
244    0x5A785A66, 0x655C654B, 0x6258624E, 0xFD19FD45, 0x068D06F4, 0x40E54086,
245    0xF298F2BE, 0x335733AC, 0x17671790, 0x057F058E, 0xE805E85E, 0x4F644F7D,
246    0x89AF896A, 0x10631095, 0x74B6742F, 0x0AFE0A75, 0x5CF55C92, 0x9BB79B74,
247    0x2D3C2D33, 0x30A530D6, 0x2ECE2E49, 0x49E94989, 0x46684672, 0x77447755,
248    0xA8E0A8D8, 0x964D9604, 0x284328BD, 0xA969A929, 0xD929D979, 0x862E8691,
249    0xD1ACD187, 0xF415F44A, 0x8D598D15, 0xD6A8D682, 0xB90AB9BC, 0x429E420D,
250    0xF66EF6C1, 0x2F472FB8, 0xDDDFDD06, 0x23342339, 0xCC35CC62, 0xF16AF1C4,
251    0xC1CFC112, 0x85DC85EB, 0x8F228F9E, 0x71C971A1, 0x90C090F0, 0xAA9BAA53,
252    0x018901F1, 0x8BD48BE1, 0x4EED4E8C, 0x8EAB8E6F, 0xAB12ABA2, 0x6FA26F3E,
253    0xE60DE654, 0xDB52DBF2, 0x92BB927B, 0xB702B7B6, 0x692F69CA, 0x39A939D9,
254    0xD3D7D30C, 0xA761A723, 0xA21EA2AD, 0xC3B4C399, 0x6C506C44, 0x07040705,
255    0x04F6047F, 0x27C22746, 0xAC16ACA7, 0xD025D076, 0x50865013, 0xDC56DCF7,
256    0x8455841A, 0xE109E151, 0x7ABE7A25, 0x139113EF},
257
258   {0xD939A9D9, 0x90176790, 0x719CB371, 0xD2A6E8D2, 0x05070405, 0x9852FD98,
259    0x6580A365, 0xDFE476DF, 0x08459A08, 0x024B9202, 0xA0E080A0, 0x665A7866,
260    0xDDAFE4DD, 0xB06ADDB0, 0xBF63D1BF, 0x362A3836, 0x54E60D54, 0x4320C643,
261    0x62CC3562, 0xBEF298BE, 0x1E12181E, 0x24EBF724, 0xD7A1ECD7, 0x77416C77,
262    0xBD2843BD, 0x32BC7532, 0xD47B37D4, 0x9B88269B, 0x700DFA70, 0xF94413F9,
263    0xB1FB94B1, 0x5A7E485A, 0x7A03F27A, 0xE48CD0E4, 0x47B68B47, 0x3C24303C,
264    0xA5E784A5, 0x416B5441, 0x06DDDF06, 0xC56023C5, 0x45FD1945, 0xA33A5BA3,
265    0x68C23D68, 0x158D5915, 0x21ECF321, 0x3166AE31, 0x3E6FA23E, 0x16578216,
266    0x95106395, 0x5BEF015B, 0x4DB8834D, 0x91862E91, 0xB56DD9B5, 0x1F83511F,
267    0x53AA9B53, 0x635D7C63, 0x3B68A63B, 0x3FFEEB3F, 0xD630A5D6, 0x257ABE25,
268    0xA7AC16A7, 0x0F090C0F, 0x35F0E335, 0x23A76123, 0xF090C0F0, 0xAFE98CAF,
269    0x809D3A80, 0x925CF592, 0x810C7381, 0x27312C27, 0x76D02576, 0xE7560BE7,
270    0x7B92BB7B, 0xE9CE4EE9, 0xF10189F1, 0x9F1E6B9F, 0xA93453A9, 0xC4F16AC4,
271    0x99C3B499, 0x975BF197, 0x8347E183, 0x6B18E66B, 0xC822BDC8, 0x0E98450E,
272    0x6E1FE26E, 0xC9B3F4C9, 0x2F74B62F, 0xCBF866CB, 0xFF99CCFF, 0xEA1495EA,
273    0xED5803ED, 0xF7DC56F7, 0xE18BD4E1, 0x1B151C1B, 0xADA21EAD, 0x0CD3D70C,
274    0x2BE2FB2B, 0x1DC8C31D, 0x195E8E19, 0xC22CB5C2, 0x8949E989, 0x12C1CF12,
275    0x7E95BF7E, 0x207DBA20, 0x6411EA64, 0x840B7784, 0x6DC5396D, 0x6A89AF6A,
276    0xD17C33D1, 0xA171C9A1, 0xCEFF62CE, 0x37BB7137, 0xFB0F81FB, 0x3DB5793D,
277    0x51E10951, 0xDC3EADDC, 0x2D3F242D, 0xA476CDA4, 0x9D55F99D, 0xEE82D8EE,
278    0x8640E586, 0xAE78C5AE, 0xCD25B9CD, 0x04964D04, 0x55774455, 0x0A0E080A,
279    0x13508613, 0x30F7E730, 0xD337A1D3, 0x40FA1D40, 0x3461AA34, 0x8C4EED8C,
280    0xB3B006B3, 0x6C54706C, 0x2A73B22A, 0x523BD252, 0x0B9F410B, 0x8B027B8B,
281    0x88D8A088, 0x4FF3114F, 0x67CB3167, 0x4627C246, 0xC06727C0, 0xB4FC90B4,
282    0x28382028, 0x7F04F67F, 0x78486078, 0x2EE5FF2E, 0x074C9607, 0x4B655C4B,
283    0xC72BB1C7, 0x6F8EAB6F, 0x0D429E0D, 0xBBF59CBB, 0xF2DB52F2, 0xF34A1BF3,
284    0xA63D5FA6, 0x59A49359, 0xBCB90ABC, 0x3AF9EF3A, 0xEF1391EF, 0xFE0885FE,
285    0x01914901, 0x6116EE61, 0x7CDE2D7C, 0xB2214FB2, 0x42B18F42, 0xDB723BDB,
286    0xB82F47B8, 0x48BF8748, 0x2CAE6D2C, 0xE3C046E3, 0x573CD657, 0x859A3E85,
287    0x29A96929, 0x7D4F647D, 0x94812A94, 0x492ECE49, 0x17C6CB17, 0xCA692FCA,
288    0xC3BDFCC3, 0x5CA3975C, 0x5EE8055E, 0xD0ED7AD0, 0x87D1AC87, 0x8E057F8E,
289    0xBA64D5BA, 0xA8A51AA8, 0xB7264BB7, 0xB9BE0EB9, 0x6087A760, 0xF8D55AF8,
290    0x22362822, 0x111B1411, 0xDE753FDE, 0x79D92979, 0xAAEE88AA, 0x332D3C33,
291    0x5F794C5F, 0xB6B702B6, 0x96CAB896, 0x5835DA58, 0x9CC4B09C, 0xFC4317FC,
292    0x1A84551A, 0xF64D1FF6, 0x1C598A1C, 0x38B27D38, 0xAC3357AC, 0x18CFC718,
293    0xF4068DF4, 0x69537469, 0x749BB774, 0xF597C4F5, 0x56AD9F56, 0xDAE372DA,
294    0xD5EA7ED5, 0x4AF4154A, 0x9E8F229E, 0xA2AB12A2, 0x4E62584E, 0xE85F07E8,
295    0xE51D99E5, 0x39233439, 0xC1F66EC1, 0x446C5044, 0x5D32DE5D, 0x72466872,
296    0x26A06526, 0x93CDBC93, 0x03DADB03, 0xC6BAF8C6, 0xFA9EC8FA, 0x82D6A882,
297    0xCF6E2BCF, 0x50704050, 0xEB85DCEB, 0x750AFE75, 0x8A93328A, 0x8DDFA48D,
298    0x4C29CA4C, 0x141C1014, 0x73D72173, 0xCCB4F0CC, 0x09D4D309, 0x108A5D10,
299    0xE2510FE2, 0x00000000, 0x9A196F9A, 0xE01A9DE0, 0x8F94368F, 0xE6C742E6,
300    0xECC94AEC, 0xFDD25EFD, 0xAB7FC1AB, 0xD8A8E0D8}
301};
302
303/* The exp_to_poly and poly_to_exp tables are used to perform efficient
304 * operations in GF(2^8) represented as GF(2)[x]/w(x) where
305 * w(x)=x^8+x^6+x^3+x^2+1.  We care about doing that because it's part of the
306 * definition of the RS matrix in the key schedule.  Elements of that field
307 * are polynomials of degree not greater than 7 and all coefficients 0 or 1,
308 * which can be represented naturally by bytes (just substitute x=2).  In that
309 * form, GF(2^8) addition is the same as bitwise XOR, but GF(2^8)
310 * multiplication is inefficient without hardware support.  To multiply
311 * faster, I make use of the fact x is a generator for the nonzero elements,
312 * so that every element p of GF(2)[x]/w(x) is either 0 or equal to (x)^n for
313 * some n in 0..254.  Note that that caret is exponentiation in GF(2^8),
314 * *not* polynomial notation.  So if I want to compute pq where p and q are
315 * in GF(2^8), I can just say:
316 *    1. if p=0 or q=0 then pq=0
317 *    2. otherwise, find m and n such that p=x^m and q=x^n
318 *    3. pq=(x^m)(x^n)=x^(m+n), so add m and n and find pq
319 * The translations in steps 2 and 3 are looked up in the tables
320 * poly_to_exp (for step 2) and exp_to_poly (for step 3).  To see this
321 * in action, look at the CALC_S macro.  As additional wrinkles, note that
322 * one of my operands is always a constant, so the poly_to_exp lookup on it
323 * is done in advance; I included the original values in the comments so
324 * readers can have some chance of recognizing that this *is* the RS matrix
325 * from the Twofish paper.  I've only included the table entries I actually
326 * need; I never do a lookup on a variable input of zero and the biggest
327 * exponents I'll ever see are 254 (variable) and 237 (constant), so they'll
328 * never sum to more than 491.  I'm repeating part of the exp_to_poly table
329 * so that I don't have to do mod-255 reduction in the exponent arithmetic.
330 * Since I know my constant operands are never zero, I only have to worry
331 * about zero values in the variable operand, and I do it with a simple
332 * conditional branch.  I know conditionals are expensive, but I couldn't
333 * see a non-horrible way of avoiding them, and I did manage to group the
334 * statements so that each if covers four group multiplications. */
335
336static const byte poly_to_exp[255] = {
337   0x00, 0x01, 0x17, 0x02, 0x2E, 0x18, 0x53, 0x03, 0x6A, 0x2F, 0x93, 0x19,
338   0x34, 0x54, 0x45, 0x04, 0x5C, 0x6B, 0xB6, 0x30, 0xA6, 0x94, 0x4B, 0x1A,
339   0x8C, 0x35, 0x81, 0x55, 0xAA, 0x46, 0x0D, 0x05, 0x24, 0x5D, 0x87, 0x6C,
340   0x9B, 0xB7, 0xC1, 0x31, 0x2B, 0xA7, 0xA3, 0x95, 0x98, 0x4C, 0xCA, 0x1B,
341   0xE6, 0x8D, 0x73, 0x36, 0xCD, 0x82, 0x12, 0x56, 0x62, 0xAB, 0xF0, 0x47,
342   0x4F, 0x0E, 0xBD, 0x06, 0xD4, 0x25, 0xD2, 0x5E, 0x27, 0x88, 0x66, 0x6D,
343   0xD6, 0x9C, 0x79, 0xB8, 0x08, 0xC2, 0xDF, 0x32, 0x68, 0x2C, 0xFD, 0xA8,
344   0x8A, 0xA4, 0x5A, 0x96, 0x29, 0x99, 0x22, 0x4D, 0x60, 0xCB, 0xE4, 0x1C,
345   0x7B, 0xE7, 0x3B, 0x8E, 0x9E, 0x74, 0xF4, 0x37, 0xD8, 0xCE, 0xF9, 0x83,
346   0x6F, 0x13, 0xB2, 0x57, 0xE1, 0x63, 0xDC, 0xAC, 0xC4, 0xF1, 0xAF, 0x48,
347   0x0A, 0x50, 0x42, 0x0F, 0xBA, 0xBE, 0xC7, 0x07, 0xDE, 0xD5, 0x78, 0x26,
348   0x65, 0xD3, 0xD1, 0x5F, 0xE3, 0x28, 0x21, 0x89, 0x59, 0x67, 0xFC, 0x6E,
349   0xB1, 0xD7, 0xF8, 0x9D, 0xF3, 0x7A, 0x3A, 0xB9, 0xC6, 0x09, 0x41, 0xC3,
350   0xAE, 0xE0, 0xDB, 0x33, 0x44, 0x69, 0x92, 0x2D, 0x52, 0xFE, 0x16, 0xA9,
351   0x0C, 0x8B, 0x80, 0xA5, 0x4A, 0x5B, 0xB5, 0x97, 0xC9, 0x2A, 0xA2, 0x9A,
352   0xC0, 0x23, 0x86, 0x4E, 0xBC, 0x61, 0xEF, 0xCC, 0x11, 0xE5, 0x72, 0x1D,
353   0x3D, 0x7C, 0xEB, 0xE8, 0xE9, 0x3C, 0xEA, 0x8F, 0x7D, 0x9F, 0xEC, 0x75,
354   0x1E, 0xF5, 0x3E, 0x38, 0xF6, 0xD9, 0x3F, 0xCF, 0x76, 0xFA, 0x1F, 0x84,
355   0xA0, 0x70, 0xED, 0x14, 0x90, 0xB3, 0x7E, 0x58, 0xFB, 0xE2, 0x20, 0x64,
356   0xD0, 0xDD, 0x77, 0xAD, 0xDA, 0xC5, 0x40, 0xF2, 0x39, 0xB0, 0xF7, 0x49,
357   0xB4, 0x0B, 0x7F, 0x51, 0x15, 0x43, 0x91, 0x10, 0x71, 0xBB, 0xEE, 0xBF,
358   0x85, 0xC8, 0xA1
359};
360
361static const byte exp_to_poly[492] = {
362   0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x4D, 0x9A, 0x79, 0xF2,
363   0xA9, 0x1F, 0x3E, 0x7C, 0xF8, 0xBD, 0x37, 0x6E, 0xDC, 0xF5, 0xA7, 0x03,
364   0x06, 0x0C, 0x18, 0x30, 0x60, 0xC0, 0xCD, 0xD7, 0xE3, 0x8B, 0x5B, 0xB6,
365   0x21, 0x42, 0x84, 0x45, 0x8A, 0x59, 0xB2, 0x29, 0x52, 0xA4, 0x05, 0x0A,
366   0x14, 0x28, 0x50, 0xA0, 0x0D, 0x1A, 0x34, 0x68, 0xD0, 0xED, 0x97, 0x63,
367   0xC6, 0xC1, 0xCF, 0xD3, 0xEB, 0x9B, 0x7B, 0xF6, 0xA1, 0x0F, 0x1E, 0x3C,
368   0x78, 0xF0, 0xAD, 0x17, 0x2E, 0x5C, 0xB8, 0x3D, 0x7A, 0xF4, 0xA5, 0x07,
369   0x0E, 0x1C, 0x38, 0x70, 0xE0, 0x8D, 0x57, 0xAE, 0x11, 0x22, 0x44, 0x88,
370   0x5D, 0xBA, 0x39, 0x72, 0xE4, 0x85, 0x47, 0x8E, 0x51, 0xA2, 0x09, 0x12,
371   0x24, 0x48, 0x90, 0x6D, 0xDA, 0xF9, 0xBF, 0x33, 0x66, 0xCC, 0xD5, 0xE7,
372   0x83, 0x4B, 0x96, 0x61, 0xC2, 0xC9, 0xDF, 0xF3, 0xAB, 0x1B, 0x36, 0x6C,
373   0xD8, 0xFD, 0xB7, 0x23, 0x46, 0x8C, 0x55, 0xAA, 0x19, 0x32, 0x64, 0xC8,
374   0xDD, 0xF7, 0xA3, 0x0B, 0x16, 0x2C, 0x58, 0xB0, 0x2D, 0x5A, 0xB4, 0x25,
375   0x4A, 0x94, 0x65, 0xCA, 0xD9, 0xFF, 0xB3, 0x2B, 0x56, 0xAC, 0x15, 0x2A,
376   0x54, 0xA8, 0x1D, 0x3A, 0x74, 0xE8, 0x9D, 0x77, 0xEE, 0x91, 0x6F, 0xDE,
377   0xF1, 0xAF, 0x13, 0x26, 0x4C, 0x98, 0x7D, 0xFA, 0xB9, 0x3F, 0x7E, 0xFC,
378   0xB5, 0x27, 0x4E, 0x9C, 0x75, 0xEA, 0x99, 0x7F, 0xFE, 0xB1, 0x2F, 0x5E,
379   0xBC, 0x35, 0x6A, 0xD4, 0xE5, 0x87, 0x43, 0x86, 0x41, 0x82, 0x49, 0x92,
380   0x69, 0xD2, 0xE9, 0x9F, 0x73, 0xE6, 0x81, 0x4F, 0x9E, 0x71, 0xE2, 0x89,
381   0x5F, 0xBE, 0x31, 0x62, 0xC4, 0xC5, 0xC7, 0xC3, 0xCB, 0xDB, 0xFB, 0xBB,
382   0x3B, 0x76, 0xEC, 0x95, 0x67, 0xCE, 0xD1, 0xEF, 0x93, 0x6B, 0xD6, 0xE1,
383   0x8F, 0x53, 0xA6, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x4D,
384   0x9A, 0x79, 0xF2, 0xA9, 0x1F, 0x3E, 0x7C, 0xF8, 0xBD, 0x37, 0x6E, 0xDC,
385   0xF5, 0xA7, 0x03, 0x06, 0x0C, 0x18, 0x30, 0x60, 0xC0, 0xCD, 0xD7, 0xE3,
386   0x8B, 0x5B, 0xB6, 0x21, 0x42, 0x84, 0x45, 0x8A, 0x59, 0xB2, 0x29, 0x52,
387   0xA4, 0x05, 0x0A, 0x14, 0x28, 0x50, 0xA0, 0x0D, 0x1A, 0x34, 0x68, 0xD0,
388   0xED, 0x97, 0x63, 0xC6, 0xC1, 0xCF, 0xD3, 0xEB, 0x9B, 0x7B, 0xF6, 0xA1,
389   0x0F, 0x1E, 0x3C, 0x78, 0xF0, 0xAD, 0x17, 0x2E, 0x5C, 0xB8, 0x3D, 0x7A,
390   0xF4, 0xA5, 0x07, 0x0E, 0x1C, 0x38, 0x70, 0xE0, 0x8D, 0x57, 0xAE, 0x11,
391   0x22, 0x44, 0x88, 0x5D, 0xBA, 0x39, 0x72, 0xE4, 0x85, 0x47, 0x8E, 0x51,
392   0xA2, 0x09, 0x12, 0x24, 0x48, 0x90, 0x6D, 0xDA, 0xF9, 0xBF, 0x33, 0x66,
393   0xCC, 0xD5, 0xE7, 0x83, 0x4B, 0x96, 0x61, 0xC2, 0xC9, 0xDF, 0xF3, 0xAB,
394   0x1B, 0x36, 0x6C, 0xD8, 0xFD, 0xB7, 0x23, 0x46, 0x8C, 0x55, 0xAA, 0x19,
395   0x32, 0x64, 0xC8, 0xDD, 0xF7, 0xA3, 0x0B, 0x16, 0x2C, 0x58, 0xB0, 0x2D,
396   0x5A, 0xB4, 0x25, 0x4A, 0x94, 0x65, 0xCA, 0xD9, 0xFF, 0xB3, 0x2B, 0x56,
397   0xAC, 0x15, 0x2A, 0x54, 0xA8, 0x1D, 0x3A, 0x74, 0xE8, 0x9D, 0x77, 0xEE,
398   0x91, 0x6F, 0xDE, 0xF1, 0xAF, 0x13, 0x26, 0x4C, 0x98, 0x7D, 0xFA, 0xB9,
399   0x3F, 0x7E, 0xFC, 0xB5, 0x27, 0x4E, 0x9C, 0x75, 0xEA, 0x99, 0x7F, 0xFE,
400   0xB1, 0x2F, 0x5E, 0xBC, 0x35, 0x6A, 0xD4, 0xE5, 0x87, 0x43, 0x86, 0x41,
401   0x82, 0x49, 0x92, 0x69, 0xD2, 0xE9, 0x9F, 0x73, 0xE6, 0x81, 0x4F, 0x9E,
402   0x71, 0xE2, 0x89, 0x5F, 0xBE, 0x31, 0x62, 0xC4, 0xC5, 0xC7, 0xC3, 0xCB
403};
404
405
406/* The table constants are indices of
407 * S-box entries, preprocessed through q0 and q1. */
408static byte calc_sb_tbl[512] = {
409    0xA9, 0x75, 0x67, 0xF3, 0xB3, 0xC6, 0xE8, 0xF4,
410    0x04, 0xDB, 0xFD, 0x7B, 0xA3, 0xFB, 0x76, 0xC8,
411    0x9A, 0x4A, 0x92, 0xD3, 0x80, 0xE6, 0x78, 0x6B,
412    0xE4, 0x45, 0xDD, 0x7D, 0xD1, 0xE8, 0x38, 0x4B,
413    0x0D, 0xD6, 0xC6, 0x32, 0x35, 0xD8, 0x98, 0xFD,
414    0x18, 0x37, 0xF7, 0x71, 0xEC, 0xF1, 0x6C, 0xE1,
415    0x43, 0x30, 0x75, 0x0F, 0x37, 0xF8, 0x26, 0x1B,
416    0xFA, 0x87, 0x13, 0xFA, 0x94, 0x06, 0x48, 0x3F,
417    0xF2, 0x5E, 0xD0, 0xBA, 0x8B, 0xAE, 0x30, 0x5B,
418    0x84, 0x8A, 0x54, 0x00, 0xDF, 0xBC, 0x23, 0x9D,
419    0x19, 0x6D, 0x5B, 0xC1, 0x3D, 0xB1, 0x59, 0x0E,
420    0xF3, 0x80, 0xAE, 0x5D, 0xA2, 0xD2, 0x82, 0xD5,
421    0x63, 0xA0, 0x01, 0x84, 0x83, 0x07, 0x2E, 0x14,
422    0xD9, 0xB5, 0x51, 0x90, 0x9B, 0x2C, 0x7C, 0xA3,
423    0xA6, 0xB2, 0xEB, 0x73, 0xA5, 0x4C, 0xBE, 0x54,
424    0x16, 0x92, 0x0C, 0x74, 0xE3, 0x36, 0x61, 0x51,
425    0xC0, 0x38, 0x8C, 0xB0, 0x3A, 0xBD, 0xF5, 0x5A,
426    0x73, 0xFC, 0x2C, 0x60, 0x25, 0x62, 0x0B, 0x96,
427    0xBB, 0x6C, 0x4E, 0x42, 0x89, 0xF7, 0x6B, 0x10,
428    0x53, 0x7C, 0x6A, 0x28, 0xB4, 0x27, 0xF1, 0x8C,
429    0xE1, 0x13, 0xE6, 0x95, 0xBD, 0x9C, 0x45, 0xC7,
430    0xE2, 0x24, 0xF4, 0x46, 0xB6, 0x3B, 0x66, 0x70,
431    0xCC, 0xCA, 0x95, 0xE3, 0x03, 0x85, 0x56, 0xCB,
432    0xD4, 0x11, 0x1C, 0xD0, 0x1E, 0x93, 0xD7, 0xB8,
433    0xFB, 0xA6, 0xC3, 0x83, 0x8E, 0x20, 0xB5, 0xFF,
434    0xE9, 0x9F, 0xCF, 0x77, 0xBF, 0xC3, 0xBA, 0xCC,
435    0xEA, 0x03, 0x77, 0x6F, 0x39, 0x08, 0xAF, 0xBF,
436    0x33, 0x40, 0xC9, 0xE7, 0x62, 0x2B, 0x71, 0xE2,
437    0x81, 0x79, 0x79, 0x0C, 0x09, 0xAA, 0xAD, 0x82,
438    0x24, 0x41, 0xCD, 0x3A, 0xF9, 0xEA, 0xD8, 0xB9,
439    0xE5, 0xE4, 0xC5, 0x9A, 0xB9, 0xA4, 0x4D, 0x97,
440    0x44, 0x7E, 0x08, 0xDA, 0x86, 0x7A, 0xE7, 0x17,
441    0xA1, 0x66, 0x1D, 0x94, 0xAA, 0xA1, 0xED, 0x1D,
442    0x06, 0x3D, 0x70, 0xF0, 0xB2, 0xDE, 0xD2, 0xB3,
443    0x41, 0x0B, 0x7B, 0x72, 0xA0, 0xA7, 0x11, 0x1C,
444    0x31, 0xEF, 0xC2, 0xD1, 0x27, 0x53, 0x90, 0x3E,
445    0x20, 0x8F, 0xF6, 0x33, 0x60, 0x26, 0xFF, 0x5F,
446    0x96, 0xEC, 0x5C, 0x76, 0xB1, 0x2A, 0xAB, 0x49,
447    0x9E, 0x81, 0x9C, 0x88, 0x52, 0xEE, 0x1B, 0x21,
448    0x5F, 0xC4, 0x93, 0x1A, 0x0A, 0xEB, 0xEF, 0xD9,
449    0x91, 0xC5, 0x85, 0x39, 0x49, 0x99, 0xEE, 0xCD,
450    0x2D, 0xAD, 0x4F, 0x31, 0x8F, 0x8B, 0x3B, 0x01,
451    0x47, 0x18, 0x87, 0x23, 0x6D, 0xDD, 0x46, 0x1F,
452    0xD6, 0x4E, 0x3E, 0x2D, 0x69, 0xF9, 0x64, 0x48,
453    0x2A, 0x4F, 0xCE, 0xF2, 0xCB, 0x65, 0x2F, 0x8E,
454    0xFC, 0x78, 0x97, 0x5C, 0x05, 0x58, 0x7A, 0x19,
455    0xAC, 0x8D, 0x7F, 0xE5, 0xD5, 0x98, 0x1A, 0x57,
456    0x4B, 0x67, 0x0E, 0x7F, 0xA7, 0x05, 0x5A, 0x64,
457    0x28, 0xAF, 0x14, 0x63, 0x3F, 0xB6, 0x29, 0xFE,
458    0x88, 0xF5, 0x3C, 0xB7, 0x4C, 0x3C, 0x02, 0xA5,
459    0xB8, 0xCE, 0xDA, 0xE9, 0xB0, 0x68, 0x17, 0x44,
460    0x55, 0xE0, 0x1F, 0x4D, 0x8A, 0x43, 0x7D, 0x69,
461    0x57, 0x29, 0xC7, 0x2E, 0x8D, 0xAC, 0x74, 0x15,
462    0xB7, 0x59, 0xC4, 0xA8, 0x9F, 0x0A, 0x72, 0x9E,
463    0x7E, 0x6E, 0x15, 0x47, 0x22, 0xDF, 0x12, 0x34,
464    0x58, 0x35, 0x07, 0x6A, 0x99, 0xCF, 0x34, 0xDC,
465    0x6E, 0x22, 0x50, 0xC9, 0xDE, 0xC0, 0x68, 0x9B,
466    0x65, 0x89, 0xBC, 0xD4, 0xDB, 0xED, 0xF8, 0xAB,
467    0xC8, 0x12, 0xA8, 0xA2, 0x2B, 0x0D, 0x40, 0x52,
468    0xDC, 0xBB, 0xFE, 0x02, 0x32, 0x2F, 0xA4, 0xA9,
469    0xCA, 0xD7, 0x10, 0x61, 0x21, 0x1E, 0xF0, 0xB4,
470    0xD3, 0x50, 0x5D, 0x04, 0x0F, 0xF6, 0x00, 0xC2,
471    0x6F, 0x16, 0x9D, 0x25, 0x36, 0x86, 0x42, 0x56,
472    0x4A, 0x55, 0x5E, 0x09, 0xC1, 0xBE, 0xE0, 0x91
473};
474/* Macro to perform one column of the RS matrix multiplication.  The
475 * parameters a, b, c, and d are the four bytes of output; i is the index
476 * of the key bytes, and w, x, y, and z, are the column of constants from
477 * the RS matrix, preprocessed through the poly_to_exp table. */
478
479#define CALC_S(a, b, c, d, i, w, x, y, z) \
480   if (key[i]) { \
481      tmp = poly_to_exp[key[i] - 1]; \
482      (a) ^= exp_to_poly[tmp + (w)]; \
483      (b) ^= exp_to_poly[tmp + (x)]; \
484      (c) ^= exp_to_poly[tmp + (y)]; \
485      (d) ^= exp_to_poly[tmp + (z)]; \
486   }
487
488/* Macros to calculate the key-dependent S-boxes for a 128-bit key using
489 * the S vector from CALC_S.  CALC_SB_2 computes a single entry in all
490 * four S-boxes, where i is the index of the entry to compute, and a and b
491 * are the index numbers preprocessed through the q0 and q1 tables
492 * respectively.  CALC_SB is simply a convenience to make the code shorter;
493 * it calls CALC_SB_2 four times with consecutive indices from i to i+3,
494 * using the remaining parameters two by two. */
495
496#define CALC_SB_2(i, a, b) \
497   ctx->s[0][i] = mds[0][q0[(a) ^ sa] ^ se]; \
498   ctx->s[1][i] = mds[1][q0[(b) ^ sb] ^ sf]; \
499   ctx->s[2][i] = mds[2][q1[(a) ^ sc] ^ sg]; \
500   ctx->s[3][i] = mds[3][q1[(b) ^ sd] ^ sh]
501
502#define CALC_SB(i, a, b, c, d, e, f, g, h) \
503   CALC_SB_2 (i, a, b); CALC_SB_2 ((i)+1, c, d); \
504   CALC_SB_2 ((i)+2, e, f); CALC_SB_2 ((i)+3, g, h)
505
506/* Macros exactly like CALC_SB and CALC_SB_2, but for 256-bit keys. */
507
508#define CALC_SB256_2(i, a, b) \
509   ctx->s[0][i] = mds[0][q0[q0[q1[(b) ^ sa] ^ se] ^ si] ^ sm]; \
510   ctx->s[1][i] = mds[1][q0[q1[q1[(a) ^ sb] ^ sf] ^ sj] ^ sn]; \
511   ctx->s[2][i] = mds[2][q1[q0[q0[(a) ^ sc] ^ sg] ^ sk] ^ so]; \
512   ctx->s[3][i] = mds[3][q1[q1[q0[(b) ^ sd] ^ sh] ^ sl] ^ sp];
513
514#define CALC_SB256(i, a, b, c, d, e, f, g, h) \
515   CALC_SB256_2 (i, a, b); CALC_SB256_2 ((i)+1, c, d); \
516   CALC_SB256_2 ((i)+2, e, f); CALC_SB256_2 ((i)+3, g, h)
517
518/* Macros to calculate the whitening and round subkeys.  CALC_K_2 computes the
519 * last two stages of the h() function for a given index (either 2i or 2i+1).
520 * a, b, c, and d are the four bytes going into the last two stages.  For
521 * 128-bit keys, this is the entire h() function and a and c are the index
522 * preprocessed through q0 and q1 respectively; for longer keys they are the
523 * output of previous stages.  j is the index of the first key byte to use.
524 * CALC_K computes a pair of subkeys for 128-bit Twofish, by calling CALC_K_2
525 * twice, doing the Pseudo-Hadamard Transform, and doing the necessary
526 * rotations.  Its parameters are: a, the array to write the results into,
527 * j, the index of the first output entry, k and l, the preprocessed indices
528 * for index 2i, and m and n, the preprocessed indices for index 2i+1.
529 * CALC_K256_2 expands CALC_K_2 to handle 256-bit keys, by doing two
530 * additional lookup-and-XOR stages.  The parameters a and b are the index
531 * preprocessed through q0 and q1 respectively; j is the index of the first
532 * key byte to use.  CALC_K256 is identical to CALC_K but for using the
533 * CALC_K256_2 macro instead of CALC_K_2. */
534
535#define CALC_K_2(a, b, c, d, j) \
536     mds[0][q0[a ^ key[(j) + 8]] ^ key[j]] \
537   ^ mds[1][q0[b ^ key[(j) + 9]] ^ key[(j) + 1]] \
538   ^ mds[2][q1[c ^ key[(j) + 10]] ^ key[(j) + 2]] \
539   ^ mds[3][q1[d ^ key[(j) + 11]] ^ key[(j) + 3]]
540
541#define CALC_K(a, j, k, l, m, n) \
542   x = CALC_K_2 (k, l, k, l, 0); \
543   y = CALC_K_2 (m, n, m, n, 4); \
544   y = (y << 8) + (y >> 24); \
545   x += y; y += x; ctx->a[j] = x; \
546   ctx->a[(j) + 1] = (y << 9) + (y >> 23)
547
548#define CALC_K256_2(a, b, j) \
549   CALC_K_2 (q0[q1[b ^ key[(j) + 24]] ^ key[(j) + 16]], \
550             q1[q1[a ^ key[(j) + 25]] ^ key[(j) + 17]], \
551             q0[q0[a ^ key[(j) + 26]] ^ key[(j) + 18]], \
552             q1[q0[b ^ key[(j) + 27]] ^ key[(j) + 19]], j)
553
554#define CALC_K256(a, j, k, l, m, n) \
555   x = CALC_K256_2 (k, l, 0); \
556   y = CALC_K256_2 (m, n, 4); \
557   y = (y << 8) + (y >> 24); \
558   x += y; y += x; ctx->a[j] = x; \
559   ctx->a[(j) + 1] = (y << 9) + (y >> 23)
560
561
562
563/* Perform the key setup.  Note that this works only with 128- and 256-bit
564 * keys, despite the API that looks like it might support other sizes. */
565
566static gcry_err_code_t
567do_twofish_setkey (TWOFISH_context *ctx, const byte *key, const unsigned keylen)
568{
569  int i, j, k;
570
571  /* Temporaries for CALC_K. */
572  u32 x, y;
573
574  /* The S vector used to key the S-boxes, split up into individual bytes.
575   * 128-bit keys use only sa through sh; 256-bit use all of them. */
576  byte sa = 0, sb = 0, sc = 0, sd = 0, se = 0, sf = 0, sg = 0, sh = 0;
577  byte si = 0, sj = 0, sk = 0, sl = 0, sm = 0, sn = 0, so = 0, sp = 0;
578
579  /* Temporary for CALC_S. */
580  byte tmp;
581
582  /* Flags for self-test. */
583  static int initialized = 0;
584  static const char *selftest_failed=0;
585
586  /* Check key length. */
587  if( ( ( keylen - 16 ) | 16 ) != 16 )
588    return GPG_ERR_INV_KEYLEN;
589
590  /* Do self-test if necessary. */
591  if (!initialized)
592    {
593      initialized = 1;
594      selftest_failed = selftest ();
595      if( selftest_failed )
596        log_error("%s\n", selftest_failed );
597    }
598  if( selftest_failed )
599    return GPG_ERR_SELFTEST_FAILED;
600
601  /* Compute the first two words of the S vector.  The magic numbers are
602   * the entries of the RS matrix, preprocessed through poly_to_exp.    The
603   * numbers in the comments are the original (polynomial form) matrix
604   * entries. */
605  CALC_S (sa, sb, sc, sd, 0, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
606  CALC_S (sa, sb, sc, sd, 1, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
607  CALC_S (sa, sb, sc, sd, 2, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
608  CALC_S (sa, sb, sc, sd, 3, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
609  CALC_S (sa, sb, sc, sd, 4, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
610  CALC_S (sa, sb, sc, sd, 5, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
611  CALC_S (sa, sb, sc, sd, 6, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
612  CALC_S (sa, sb, sc, sd, 7, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
613  CALC_S (se, sf, sg, sh, 8, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
614  CALC_S (se, sf, sg, sh, 9, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
615  CALC_S (se, sf, sg, sh, 10, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
616  CALC_S (se, sf, sg, sh, 11, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
617  CALC_S (se, sf, sg, sh, 12, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
618  CALC_S (se, sf, sg, sh, 13, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
619  CALC_S (se, sf, sg, sh, 14, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
620  CALC_S (se, sf, sg, sh, 15, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
621
622  if (keylen == 32)  /* 256-bit key */
623    {
624      /* Calculate the remaining two words of the S vector */
625      CALC_S (si, sj, sk, sl, 16, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
626      CALC_S (si, sj, sk, sl, 17, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
627      CALC_S (si, sj, sk, sl, 18, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
628      CALC_S (si, sj, sk, sl, 19, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
629      CALC_S (si, sj, sk, sl, 20, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
630      CALC_S (si, sj, sk, sl, 21, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
631      CALC_S (si, sj, sk, sl, 22, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
632      CALC_S (si, sj, sk, sl, 23, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
633      CALC_S (sm, sn, so, sp, 24, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
634      CALC_S (sm, sn, so, sp, 25, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
635      CALC_S (sm, sn, so, sp, 26, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
636      CALC_S (sm, sn, so, sp, 27, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
637      CALC_S (sm, sn, so, sp, 28, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
638      CALC_S (sm, sn, so, sp, 29, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
639      CALC_S (sm, sn, so, sp, 30, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
640      CALC_S (sm, sn, so, sp, 31, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
641
642      /* Compute the S-boxes. */
643      for(i=j=0,k=1; i < 256; i++, j += 2, k += 2 )
644        {
645          CALC_SB256_2( i, calc_sb_tbl[j], calc_sb_tbl[k] );
646        }
647
648      /* Calculate whitening and round subkeys.  The constants are
649       * indices of subkeys, preprocessed through q0 and q1. */
650      CALC_K256 (w, 0, 0xA9, 0x75, 0x67, 0xF3);
651      CALC_K256 (w, 2, 0xB3, 0xC6, 0xE8, 0xF4);
652      CALC_K256 (w, 4, 0x04, 0xDB, 0xFD, 0x7B);
653      CALC_K256 (w, 6, 0xA3, 0xFB, 0x76, 0xC8);
654      CALC_K256 (k, 0, 0x9A, 0x4A, 0x92, 0xD3);
655      CALC_K256 (k, 2, 0x80, 0xE6, 0x78, 0x6B);
656      CALC_K256 (k, 4, 0xE4, 0x45, 0xDD, 0x7D);
657      CALC_K256 (k, 6, 0xD1, 0xE8, 0x38, 0x4B);
658      CALC_K256 (k, 8, 0x0D, 0xD6, 0xC6, 0x32);
659      CALC_K256 (k, 10, 0x35, 0xD8, 0x98, 0xFD);
660      CALC_K256 (k, 12, 0x18, 0x37, 0xF7, 0x71);
661      CALC_K256 (k, 14, 0xEC, 0xF1, 0x6C, 0xE1);
662      CALC_K256 (k, 16, 0x43, 0x30, 0x75, 0x0F);
663      CALC_K256 (k, 18, 0x37, 0xF8, 0x26, 0x1B);
664      CALC_K256 (k, 20, 0xFA, 0x87, 0x13, 0xFA);
665      CALC_K256 (k, 22, 0x94, 0x06, 0x48, 0x3F);
666      CALC_K256 (k, 24, 0xF2, 0x5E, 0xD0, 0xBA);
667      CALC_K256 (k, 26, 0x8B, 0xAE, 0x30, 0x5B);
668      CALC_K256 (k, 28, 0x84, 0x8A, 0x54, 0x00);
669      CALC_K256 (k, 30, 0xDF, 0xBC, 0x23, 0x9D);
670    }
671  else
672    {
673      /* Compute the S-boxes. */
674      for(i=j=0,k=1; i < 256; i++, j += 2, k += 2 )
675        {
676          CALC_SB_2( i, calc_sb_tbl[j], calc_sb_tbl[k] );
677        }
678
679      /* Calculate whitening and round subkeys.  The constants are
680       * indices of subkeys, preprocessed through q0 and q1. */
681      CALC_K (w, 0, 0xA9, 0x75, 0x67, 0xF3);
682      CALC_K (w, 2, 0xB3, 0xC6, 0xE8, 0xF4);
683      CALC_K (w, 4, 0x04, 0xDB, 0xFD, 0x7B);
684      CALC_K (w, 6, 0xA3, 0xFB, 0x76, 0xC8);
685      CALC_K (k, 0, 0x9A, 0x4A, 0x92, 0xD3);
686      CALC_K (k, 2, 0x80, 0xE6, 0x78, 0x6B);
687      CALC_K (k, 4, 0xE4, 0x45, 0xDD, 0x7D);
688      CALC_K (k, 6, 0xD1, 0xE8, 0x38, 0x4B);
689      CALC_K (k, 8, 0x0D, 0xD6, 0xC6, 0x32);
690      CALC_K (k, 10, 0x35, 0xD8, 0x98, 0xFD);
691      CALC_K (k, 12, 0x18, 0x37, 0xF7, 0x71);
692      CALC_K (k, 14, 0xEC, 0xF1, 0x6C, 0xE1);
693      CALC_K (k, 16, 0x43, 0x30, 0x75, 0x0F);
694      CALC_K (k, 18, 0x37, 0xF8, 0x26, 0x1B);
695      CALC_K (k, 20, 0xFA, 0x87, 0x13, 0xFA);
696      CALC_K (k, 22, 0x94, 0x06, 0x48, 0x3F);
697      CALC_K (k, 24, 0xF2, 0x5E, 0xD0, 0xBA);
698      CALC_K (k, 26, 0x8B, 0xAE, 0x30, 0x5B);
699      CALC_K (k, 28, 0x84, 0x8A, 0x54, 0x00);
700      CALC_K (k, 30, 0xDF, 0xBC, 0x23, 0x9D);
701    }
702
703  return 0;
704}
705
706static gcry_err_code_t
707twofish_setkey (void *context, const byte *key, unsigned int keylen)
708{
709  TWOFISH_context *ctx = context;
710  int rc = do_twofish_setkey (ctx, key, keylen);
711  _gcry_burn_stack (23+6*sizeof(void*));
712  return rc;
713}
714
715
716
717/* Macros to compute the g() function in the encryption and decryption
718 * rounds.  G1 is the straight g() function; G2 includes the 8-bit
719 * rotation for the high 32-bit word. */
720
721#define G1(a) \
722     (ctx->s[0][(a) & 0xFF]) ^ (ctx->s[1][((a) >> 8) & 0xFF]) \
723   ^ (ctx->s[2][((a) >> 16) & 0xFF]) ^ (ctx->s[3][(a) >> 24])
724
725#define G2(b) \
726     (ctx->s[1][(b) & 0xFF]) ^ (ctx->s[2][((b) >> 8) & 0xFF]) \
727   ^ (ctx->s[3][((b) >> 16) & 0xFF]) ^ (ctx->s[0][(b) >> 24])
728
729/* Encryption and decryption Feistel rounds.  Each one calls the two g()
730 * macros, does the PHT, and performs the XOR and the appropriate bit
731 * rotations.  The parameters are the round number (used to select subkeys),
732 * and the four 32-bit chunks of the text. */
733
734#define ENCROUND(n, a, b, c, d) \
735   x = G1 (a); y = G2 (b); \
736   x += y; y += x + ctx->k[2 * (n) + 1]; \
737   (c) ^= x + ctx->k[2 * (n)]; \
738   (c) = ((c) >> 1) + ((c) << 31); \
739   (d) = (((d) << 1)+((d) >> 31)) ^ y
740
741#define DECROUND(n, a, b, c, d) \
742   x = G1 (a); y = G2 (b); \
743   x += y; y += x; \
744   (d) ^= y + ctx->k[2 * (n) + 1]; \
745   (d) = ((d) >> 1) + ((d) << 31); \
746   (c) = (((c) << 1)+((c) >> 31)); \
747   (c) ^= (x + ctx->k[2 * (n)])
748
749/* Encryption and decryption cycles; each one is simply two Feistel rounds
750 * with the 32-bit chunks re-ordered to simulate the "swap" */
751
752#define ENCCYCLE(n) \
753   ENCROUND (2 * (n), a, b, c, d); \
754   ENCROUND (2 * (n) + 1, c, d, a, b)
755
756#define DECCYCLE(n) \
757   DECROUND (2 * (n) + 1, c, d, a, b); \
758   DECROUND (2 * (n), a, b, c, d)
759
760/* Macros to convert the input and output bytes into 32-bit words,
761 * and simultaneously perform the whitening step.  INPACK packs word
762 * number n into the variable named by x, using whitening subkey number m.
763 * OUTUNPACK unpacks word number n from the variable named by x, using
764 * whitening subkey number m. */
765
766#define INPACK(n, x, m) \
767   x = in[4 * (n)] ^ (in[4 * (n) + 1] << 8) \
768     ^ (in[4 * (n) + 2] << 16) ^ (in[4 * (n) + 3] << 24) ^ ctx->w[m]
769
770#define OUTUNPACK(n, x, m) \
771   x ^= ctx->w[m]; \
772   out[4 * (n)] = x; out[4 * (n) + 1] = x >> 8; \
773   out[4 * (n) + 2] = x >> 16; out[4 * (n) + 3] = x >> 24
774
775/* Encrypt one block.  in and out may be the same. */
776
777static void
778do_twofish_encrypt (const TWOFISH_context *ctx, byte *out, const byte *in)
779{
780  /* The four 32-bit chunks of the text. */
781  u32 a, b, c, d;
782
783  /* Temporaries used by the round function. */
784  u32 x, y;
785
786  /* Input whitening and packing. */
787  INPACK (0, a, 0);
788  INPACK (1, b, 1);
789  INPACK (2, c, 2);
790  INPACK (3, d, 3);
791
792  /* Encryption Feistel cycles. */
793  ENCCYCLE (0);
794  ENCCYCLE (1);
795  ENCCYCLE (2);
796  ENCCYCLE (3);
797  ENCCYCLE (4);
798  ENCCYCLE (5);
799  ENCCYCLE (6);
800  ENCCYCLE (7);
801
802  /* Output whitening and unpacking. */
803  OUTUNPACK (0, c, 4);
804  OUTUNPACK (1, d, 5);
805  OUTUNPACK (2, a, 6);
806  OUTUNPACK (3, b, 7);
807}
808
809static void
810twofish_encrypt (void *context, byte *out, const byte *in)
811{
812  TWOFISH_context *ctx = context;
813  do_twofish_encrypt (ctx, out, in);
814  _gcry_burn_stack (24+3*sizeof (void*));
815}
816
817
818/* Decrypt one block.  in and out may be the same. */
819
820static void
821do_twofish_decrypt (const TWOFISH_context *ctx, byte *out, const byte *in)
822{
823  /* The four 32-bit chunks of the text. */
824  u32 a, b, c, d;
825
826  /* Temporaries used by the round function. */
827  u32 x, y;
828
829  /* Input whitening and packing. */
830  INPACK (0, c, 4);
831  INPACK (1, d, 5);
832  INPACK (2, a, 6);
833  INPACK (3, b, 7);
834
835  /* Encryption Feistel cycles. */
836  DECCYCLE (7);
837  DECCYCLE (6);
838  DECCYCLE (5);
839  DECCYCLE (4);
840  DECCYCLE (3);
841  DECCYCLE (2);
842  DECCYCLE (1);
843  DECCYCLE (0);
844
845  /* Output whitening and unpacking. */
846  OUTUNPACK (0, a, 0);
847  OUTUNPACK (1, b, 1);
848  OUTUNPACK (2, c, 2);
849  OUTUNPACK (3, d, 3);
850}
851
852static void
853twofish_decrypt (void *context, byte *out, const byte *in)
854{
855  TWOFISH_context *ctx = context;
856
857  do_twofish_decrypt (ctx, out, in);
858  _gcry_burn_stack (24+3*sizeof (void*));
859}
860
861
862/* Test a single encryption and decryption with each key size. */
863
864static const char*
865selftest (void)
866{
867  TWOFISH_context ctx; /* Expanded key. */
868  byte scratch[16];     /* Encryption/decryption result buffer. */
869
870  /* Test vectors for single encryption/decryption.  Note that I am using
871   * the vectors from the Twofish paper's "known answer test", I=3 for
872   * 128-bit and I=4 for 256-bit, instead of the all-0 vectors from the
873   * "intermediate value test", because an all-0 key would trigger all the
874   * special cases in the RS matrix multiply, leaving the math untested. */
875  static  byte plaintext[16] = {
876    0xD4, 0x91, 0xDB, 0x16, 0xE7, 0xB1, 0xC3, 0x9E,
877    0x86, 0xCB, 0x08, 0x6B, 0x78, 0x9F, 0x54, 0x19
878  };
879  static byte key[16] = {
880    0x9F, 0x58, 0x9F, 0x5C, 0xF6, 0x12, 0x2C, 0x32,
881    0xB6, 0xBF, 0xEC, 0x2F, 0x2A, 0xE8, 0xC3, 0x5A
882  };
883  static const byte ciphertext[16] = {
884    0x01, 0x9F, 0x98, 0x09, 0xDE, 0x17, 0x11, 0x85,
885    0x8F, 0xAA, 0xC3, 0xA3, 0xBA, 0x20, 0xFB, 0xC3
886  };
887  static byte plaintext_256[16] = {
888    0x90, 0xAF, 0xE9, 0x1B, 0xB2, 0x88, 0x54, 0x4F,
889    0x2C, 0x32, 0xDC, 0x23, 0x9B, 0x26, 0x35, 0xE6
890  };
891  static byte key_256[32] = {
892    0xD4, 0x3B, 0xB7, 0x55, 0x6E, 0xA3, 0x2E, 0x46,
893    0xF2, 0xA2, 0x82, 0xB7, 0xD4, 0x5B, 0x4E, 0x0D,
894    0x57, 0xFF, 0x73, 0x9D, 0x4D, 0xC9, 0x2C, 0x1B,
895    0xD7, 0xFC, 0x01, 0x70, 0x0C, 0xC8, 0x21, 0x6F
896  };
897  static const byte ciphertext_256[16] = {
898    0x6C, 0xB4, 0x56, 0x1C, 0x40, 0xBF, 0x0A, 0x97,
899    0x05, 0x93, 0x1C, 0xB6, 0xD4, 0x08, 0xE7, 0xFA
900  };
901
902  twofish_setkey (&ctx, key, sizeof(key));
903  twofish_encrypt (&ctx, scratch, plaintext);
904  if (memcmp (scratch, ciphertext, sizeof (ciphertext)))
905    return "Twofish-128 test encryption failed.";
906  twofish_decrypt (&ctx, scratch, scratch);
907  if (memcmp (scratch, plaintext, sizeof (plaintext)))
908    return "Twofish-128 test decryption failed.";
909
910  twofish_setkey (&ctx, key_256, sizeof(key_256));
911  twofish_encrypt (&ctx, scratch, plaintext_256);
912  if (memcmp (scratch, ciphertext_256, sizeof (ciphertext_256)))
913    return "Twofish-256 test encryption failed.";
914  twofish_decrypt (&ctx, scratch, scratch);
915  if (memcmp (scratch, plaintext_256, sizeof (plaintext_256)))
916    return "Twofish-256 test decryption failed.";
917
918  return NULL;
919}
920
921/* More complete test program.  This does 1000 encryptions and decryptions
922 * with each of 250 128-bit keys and 2000 encryptions and decryptions with
923 * each of 125 256-bit keys, using a feedback scheme similar to a Feistel
924 * cipher, so as to be sure of testing all the table entries pretty
925 * thoroughly.  We keep changing the keys so as to get a more meaningful
926 * performance number, since the key setup is non-trivial for Twofish. */
927
928#ifdef TEST
929
930#include <stdio.h>
931#include <string.h>
932#include <time.h>
933
934int
935main()
936{
937  TWOFISH_context ctx;     /* Expanded key. */
938  int i, j;                 /* Loop counters. */
939
940  const char *encrypt_msg; /* Message to print regarding encryption test;
941                            * the printf is done outside the loop to avoid
942                            * stuffing up the timing. */
943  clock_t timer; /* For computing elapsed time. */
944
945  /* Test buffer. */
946  byte buffer[4][16] = {
947    {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77,
948     0x88, 0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF},
949    {0x0F, 0x1E, 0x2D, 0x3C, 0x4B, 0x5A, 0x69, 0x78,
950     0x87, 0x96, 0xA5, 0xB4, 0xC3, 0xD2 ,0xE1, 0xF0},
951    {0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF,
952     0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54 ,0x32, 0x10},
953    {0x01, 0x23, 0x45, 0x67, 0x76, 0x54 ,0x32, 0x10,
954     0x89, 0xAB, 0xCD, 0xEF, 0xFE, 0xDC, 0xBA, 0x98}
955  };
956
957  /* Expected outputs for the million-operation test */
958  static const byte test_encrypt[4][16] = {
959    {0xC8, 0x23, 0xB8, 0xB7, 0x6B, 0xFE, 0x91, 0x13,
960     0x2F, 0xA7, 0x5E, 0xE6, 0x94, 0x77, 0x6F, 0x6B},
961    {0x90, 0x36, 0xD8, 0x29, 0xD5, 0x96, 0xC2, 0x8E,
962     0xE4, 0xFF, 0x76, 0xBC, 0xE5, 0x77, 0x88, 0x27},
963    {0xB8, 0x78, 0x69, 0xAF, 0x42, 0x8B, 0x48, 0x64,
964     0xF7, 0xE9, 0xF3, 0x9C, 0x42, 0x18, 0x7B, 0x73},
965    {0x7A, 0x88, 0xFB, 0xEB, 0x90, 0xA4, 0xB4, 0xA8,
966     0x43, 0xA3, 0x1D, 0xF1, 0x26, 0xC4, 0x53, 0x57}
967  };
968  static const byte test_decrypt[4][16] = {
969    {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77,
970     0x88, 0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF},
971    {0x0F, 0x1E, 0x2D, 0x3C, 0x4B, 0x5A, 0x69, 0x78,
972     0x87, 0x96, 0xA5, 0xB4, 0xC3, 0xD2 ,0xE1, 0xF0},
973    {0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF,
974     0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54 ,0x32, 0x10},
975    {0x01, 0x23, 0x45, 0x67, 0x76, 0x54 ,0x32, 0x10,
976     0x89, 0xAB, 0xCD, 0xEF, 0xFE, 0xDC, 0xBA, 0x98}
977  };
978
979  /* Start the timer ticking. */
980  timer = clock ();
981
982  /* Encryption test. */
983  for (i = 0; i < 125; i++)
984    {
985      twofish_setkey (&ctx, buffer[0], sizeof (buffer[0]));
986      for (j = 0; j < 1000; j++)
987        twofish_encrypt (&ctx, buffer[2], buffer[2]);
988      twofish_setkey (&ctx, buffer[1], sizeof (buffer[1]));
989      for (j = 0; j < 1000; j++)
990        twofish_encrypt (&ctx, buffer[3], buffer[3]);
991      twofish_setkey (&ctx, buffer[2], sizeof (buffer[2])*2);
992      for (j = 0; j < 1000; j++) {
993        twofish_encrypt (&ctx, buffer[0], buffer[0]);
994        twofish_encrypt (&ctx, buffer[1], buffer[1]);
995      }
996    }
997  encrypt_msg = memcmp (buffer, test_encrypt, sizeof (test_encrypt)) ?
998    "encryption failure!\n" : "encryption OK!\n";
999
1000  /* Decryption test. */
1001  for (i = 0; i < 125; i++)
1002    {
1003      twofish_setkey (&ctx, buffer[2], sizeof (buffer[2])*2);
1004      for (j = 0; j < 1000; j++) {
1005        twofish_decrypt (&ctx, buffer[0], buffer[0]);
1006        twofish_decrypt (&ctx, buffer[1], buffer[1]);
1007      }
1008      twofish_setkey (&ctx, buffer[1], sizeof (buffer[1]));
1009      for (j = 0; j < 1000; j++)
1010        twofish_decrypt (&ctx, buffer[3], buffer[3]);
1011      twofish_setkey (&ctx, buffer[0], sizeof (buffer[0]));
1012      for (j = 0; j < 1000; j++)
1013        twofish_decrypt (&ctx, buffer[2], buffer[2]);
1014    }
1015
1016  /* Stop the timer, and print results. */
1017  timer = clock () - timer;
1018  printf (encrypt_msg);
1019  printf (memcmp (buffer, test_decrypt, sizeof (test_decrypt)) ?
1020          "decryption failure!\n" : "decryption OK!\n");
1021  printf ("elapsed time: %.1f s.\n", (float) timer / CLOCKS_PER_SEC);
1022
1023  return 0;
1024}
1025
1026#endif /* TEST */
1027
1028
1029
1030gcry_cipher_spec_t _gcry_cipher_spec_twofish =
1031  {
1032    "TWOFISH", NULL, NULL, 16, 256, sizeof (TWOFISH_context),
1033    twofish_setkey, twofish_encrypt, twofish_decrypt
1034  };
1035
1036gcry_cipher_spec_t _gcry_cipher_spec_twofish128 =
1037  {
1038    "TWOFISH128", NULL, NULL, 16, 128, sizeof (TWOFISH_context),
1039    twofish_setkey, twofish_encrypt, twofish_decrypt
1040  };
Note: See TracBrowser for help on using the repository browser.