A whole bunch of changes to eventually support
[libgcrypt.git] / cipher / twofish.c
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. */
49 static 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]. */
55 typedef struct {
56    u32 s[4][256], w[8], k[32];
57 } TWOFISH_context;
58 \f
59 /* These two tables are the q0 and q1 permutations, exactly as described in
60  * the Twofish paper. */
61
62 static 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
87 static 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 \f
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
125 static 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 \f
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
336 static 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
361 static 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 \f
405
406 /* The table constants are indices of
407  * S-box entries, preprocessed through q0 and q1. */
408 static 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 Psuedo-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 \f
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
566 static gcry_err_code_t
567 do_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
706 static gcry_err_code_t
707 twofish_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 \f
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 \f
775 /* Encrypt one block.  in and out may be the same. */
776
777 static void
778 do_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
809 static void
810 twofish_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 \f
818 /* Decrypt one block.  in and out may be the same. */
819
820 static void
821 do_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
852 static void
853 twofish_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 \f
862 /* Test a single encryption and decryption with each key size. */
863
864 static const char*
865 selftest (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 \f
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
934 int
935 main()
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 \f
1029
1030 gcry_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
1036 gcry_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   };