Improve.
[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 \f
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 gpg_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        initialized = 1;
593        selftest_failed = selftest ();
594        if( selftest_failed )
595          log_error("%s\n", selftest_failed );
596     }
597     if( selftest_failed )
598        return GPG_ERR_SELFTEST_FAILED;
599
600     /* Compute the first two words of the S vector.  The magic numbers are
601      * the entries of the RS matrix, preprocessed through poly_to_exp.  The
602      * numbers in the comments are the original (polynomial form) matrix
603      * entries. */
604     CALC_S (sa, sb, sc, sd, 0, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
605     CALC_S (sa, sb, sc, sd, 1, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
606     CALC_S (sa, sb, sc, sd, 2, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
607     CALC_S (sa, sb, sc, sd, 3, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
608     CALC_S (sa, sb, sc, sd, 4, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
609     CALC_S (sa, sb, sc, sd, 5, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
610     CALC_S (sa, sb, sc, sd, 6, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
611     CALC_S (sa, sb, sc, sd, 7, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
612     CALC_S (se, sf, sg, sh, 8, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
613     CALC_S (se, sf, sg, sh, 9, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
614     CALC_S (se, sf, sg, sh, 10, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
615     CALC_S (se, sf, sg, sh, 11, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
616     CALC_S (se, sf, sg, sh, 12, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
617     CALC_S (se, sf, sg, sh, 13, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
618     CALC_S (se, sf, sg, sh, 14, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
619     CALC_S (se, sf, sg, sh, 15, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
620
621     if (keylen == 32) { /* 256-bit key */
622         /* Calculate the remaining two words of the S vector */
623         CALC_S (si, sj, sk, sl, 16, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
624         CALC_S (si, sj, sk, sl, 17, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
625         CALC_S (si, sj, sk, sl, 18, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
626         CALC_S (si, sj, sk, sl, 19, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
627         CALC_S (si, sj, sk, sl, 20, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
628         CALC_S (si, sj, sk, sl, 21, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
629         CALC_S (si, sj, sk, sl, 22, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
630         CALC_S (si, sj, sk, sl, 23, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
631         CALC_S (sm, sn, so, sp, 24, 0x00, 0x2D, 0x01, 0x2D); /* 01 A4 02 A4 */
632         CALC_S (sm, sn, so, sp, 25, 0x2D, 0xA4, 0x44, 0x8A); /* A4 56 A1 55 */
633         CALC_S (sm, sn, so, sp, 26, 0x8A, 0xD5, 0xBF, 0xD1); /* 55 82 FC 87 */
634         CALC_S (sm, sn, so, sp, 27, 0xD1, 0x7F, 0x3D, 0x99); /* 87 F3 C1 5A */
635         CALC_S (sm, sn, so, sp, 28, 0x99, 0x46, 0x66, 0x96); /* 5A 1E 47 58 */
636         CALC_S (sm, sn, so, sp, 29, 0x96, 0x3C, 0x5B, 0xED); /* 58 C6 AE DB */
637         CALC_S (sm, sn, so, sp, 30, 0xED, 0x37, 0x4F, 0xE0); /* DB 68 3D 9E */
638         CALC_S (sm, sn, so, sp, 31, 0xE0, 0xD0, 0x8C, 0x17); /* 9E E5 19 03 */
639
640         /* Compute the S-boxes. */
641         for(i=j=0,k=1; i < 256; i++, j += 2, k += 2 ) {
642             CALC_SB256_2( i, calc_sb_tbl[j], calc_sb_tbl[k] );
643         }
644
645         /* Calculate whitening and round subkeys.  The constants are
646          * indices of subkeys, preprocessed through q0 and q1. */
647         CALC_K256 (w, 0, 0xA9, 0x75, 0x67, 0xF3);
648         CALC_K256 (w, 2, 0xB3, 0xC6, 0xE8, 0xF4);
649         CALC_K256 (w, 4, 0x04, 0xDB, 0xFD, 0x7B);
650         CALC_K256 (w, 6, 0xA3, 0xFB, 0x76, 0xC8);
651         CALC_K256 (k, 0, 0x9A, 0x4A, 0x92, 0xD3);
652         CALC_K256 (k, 2, 0x80, 0xE6, 0x78, 0x6B);
653         CALC_K256 (k, 4, 0xE4, 0x45, 0xDD, 0x7D);
654         CALC_K256 (k, 6, 0xD1, 0xE8, 0x38, 0x4B);
655         CALC_K256 (k, 8, 0x0D, 0xD6, 0xC6, 0x32);
656         CALC_K256 (k, 10, 0x35, 0xD8, 0x98, 0xFD);
657         CALC_K256 (k, 12, 0x18, 0x37, 0xF7, 0x71);
658         CALC_K256 (k, 14, 0xEC, 0xF1, 0x6C, 0xE1);
659         CALC_K256 (k, 16, 0x43, 0x30, 0x75, 0x0F);
660         CALC_K256 (k, 18, 0x37, 0xF8, 0x26, 0x1B);
661         CALC_K256 (k, 20, 0xFA, 0x87, 0x13, 0xFA);
662         CALC_K256 (k, 22, 0x94, 0x06, 0x48, 0x3F);
663         CALC_K256 (k, 24, 0xF2, 0x5E, 0xD0, 0xBA);
664         CALC_K256 (k, 26, 0x8B, 0xAE, 0x30, 0x5B);
665         CALC_K256 (k, 28, 0x84, 0x8A, 0x54, 0x00);
666         CALC_K256 (k, 30, 0xDF, 0xBC, 0x23, 0x9D);
667     }
668     else {
669         /* Compute the S-boxes. */
670         for(i=j=0,k=1; i < 256; i++, j += 2, k += 2 ) {
671             CALC_SB_2( i, calc_sb_tbl[j], calc_sb_tbl[k] );
672         }
673
674         /* Calculate whitening and round subkeys.  The constants are
675          * indices of subkeys, preprocessed through q0 and q1. */
676         CALC_K (w, 0, 0xA9, 0x75, 0x67, 0xF3);
677         CALC_K (w, 2, 0xB3, 0xC6, 0xE8, 0xF4);
678         CALC_K (w, 4, 0x04, 0xDB, 0xFD, 0x7B);
679         CALC_K (w, 6, 0xA3, 0xFB, 0x76, 0xC8);
680         CALC_K (k, 0, 0x9A, 0x4A, 0x92, 0xD3);
681         CALC_K (k, 2, 0x80, 0xE6, 0x78, 0x6B);
682         CALC_K (k, 4, 0xE4, 0x45, 0xDD, 0x7D);
683         CALC_K (k, 6, 0xD1, 0xE8, 0x38, 0x4B);
684         CALC_K (k, 8, 0x0D, 0xD6, 0xC6, 0x32);
685         CALC_K (k, 10, 0x35, 0xD8, 0x98, 0xFD);
686         CALC_K (k, 12, 0x18, 0x37, 0xF7, 0x71);
687         CALC_K (k, 14, 0xEC, 0xF1, 0x6C, 0xE1);
688         CALC_K (k, 16, 0x43, 0x30, 0x75, 0x0F);
689         CALC_K (k, 18, 0x37, 0xF8, 0x26, 0x1B);
690         CALC_K (k, 20, 0xFA, 0x87, 0x13, 0xFA);
691         CALC_K (k, 22, 0x94, 0x06, 0x48, 0x3F);
692         CALC_K (k, 24, 0xF2, 0x5E, 0xD0, 0xBA);
693         CALC_K (k, 26, 0x8B, 0xAE, 0x30, 0x5B);
694         CALC_K (k, 28, 0x84, 0x8A, 0x54, 0x00);
695         CALC_K (k, 30, 0xDF, 0xBC, 0x23, 0x9D);
696     }
697
698     return 0;
699 }
700
701 static gpg_err_code_t
702 twofish_setkey (void *context, const byte *key, unsigned int keylen)
703 {
704   TWOFISH_context *ctx = (TWOFISH_context *) context;
705   int rc = do_twofish_setkey (ctx, key, keylen);
706   _gcry_burn_stack (23+6*sizeof(void*));
707   return rc;
708 }
709
710
711 \f
712 /* Macros to compute the g() function in the encryption and decryption
713  * rounds.  G1 is the straight g() function; G2 includes the 8-bit
714  * rotation for the high 32-bit word. */
715
716 #define G1(a) \
717      (ctx->s[0][(a) & 0xFF]) ^ (ctx->s[1][((a) >> 8) & 0xFF]) \
718    ^ (ctx->s[2][((a) >> 16) & 0xFF]) ^ (ctx->s[3][(a) >> 24])
719
720 #define G2(b) \
721      (ctx->s[1][(b) & 0xFF]) ^ (ctx->s[2][((b) >> 8) & 0xFF]) \
722    ^ (ctx->s[3][((b) >> 16) & 0xFF]) ^ (ctx->s[0][(b) >> 24])
723
724 /* Encryption and decryption Feistel rounds.  Each one calls the two g()
725  * macros, does the PHT, and performs the XOR and the appropriate bit
726  * rotations.  The parameters are the round number (used to select subkeys),
727  * and the four 32-bit chunks of the text. */
728
729 #define ENCROUND(n, a, b, c, d) \
730    x = G1 (a); y = G2 (b); \
731    x += y; y += x + ctx->k[2 * (n) + 1]; \
732    (c) ^= x + ctx->k[2 * (n)]; \
733    (c) = ((c) >> 1) + ((c) << 31); \
734    (d) = (((d) << 1)+((d) >> 31)) ^ y
735
736 #define DECROUND(n, a, b, c, d) \
737    x = G1 (a); y = G2 (b); \
738    x += y; y += x; \
739    (d) ^= y + ctx->k[2 * (n) + 1]; \
740    (d) = ((d) >> 1) + ((d) << 31); \
741    (c) = (((c) << 1)+((c) >> 31)); \
742    (c) ^= (x + ctx->k[2 * (n)])
743
744 /* Encryption and decryption cycles; each one is simply two Feistel rounds
745  * with the 32-bit chunks re-ordered to simulate the "swap" */
746
747 #define ENCCYCLE(n) \
748    ENCROUND (2 * (n), a, b, c, d); \
749    ENCROUND (2 * (n) + 1, c, d, a, b)
750
751 #define DECCYCLE(n) \
752    DECROUND (2 * (n) + 1, c, d, a, b); \
753    DECROUND (2 * (n), a, b, c, d)
754
755 /* Macros to convert the input and output bytes into 32-bit words,
756  * and simultaneously perform the whitening step.  INPACK packs word
757  * number n into the variable named by x, using whitening subkey number m.
758  * OUTUNPACK unpacks word number n from the variable named by x, using
759  * whitening subkey number m. */
760
761 #define INPACK(n, x, m) \
762    x = in[4 * (n)] ^ (in[4 * (n) + 1] << 8) \
763      ^ (in[4 * (n) + 2] << 16) ^ (in[4 * (n) + 3] << 24) ^ ctx->w[m]
764
765 #define OUTUNPACK(n, x, m) \
766    x ^= ctx->w[m]; \
767    out[4 * (n)] = x; out[4 * (n) + 1] = x >> 8; \
768    out[4 * (n) + 2] = x >> 16; out[4 * (n) + 3] = x >> 24
769 \f
770 /* Encrypt one block.  in and out may be the same. */
771
772 static void
773 do_twofish_encrypt (const TWOFISH_context *ctx, byte *out, const byte *in)
774 {
775    /* The four 32-bit chunks of the text. */
776    u32 a, b, c, d;
777
778    /* Temporaries used by the round function. */
779    u32 x, y;
780
781    /* Input whitening and packing. */
782    INPACK (0, a, 0);
783    INPACK (1, b, 1);
784    INPACK (2, c, 2);
785    INPACK (3, d, 3);
786
787    /* Encryption Feistel cycles. */
788    ENCCYCLE (0);
789    ENCCYCLE (1);
790    ENCCYCLE (2);
791    ENCCYCLE (3);
792    ENCCYCLE (4);
793    ENCCYCLE (5);
794    ENCCYCLE (6);
795    ENCCYCLE (7);
796
797    /* Output whitening and unpacking. */
798    OUTUNPACK (0, c, 4);
799    OUTUNPACK (1, d, 5);
800    OUTUNPACK (2, a, 6);
801    OUTUNPACK (3, b, 7);
802 }
803
804 static void
805 twofish_encrypt (void *context, byte *out, const byte *in)
806 {
807   TWOFISH_context *ctx = (TWOFISH_context *) context;
808   do_twofish_encrypt (ctx, out, in);
809   _gcry_burn_stack (24+3*sizeof (void*));
810 }
811
812 \f
813 /* Decrypt one block.  in and out may be the same. */
814
815 static void
816 do_twofish_decrypt (const TWOFISH_context *ctx, byte *out, const byte *in)
817 {
818    /* The four 32-bit chunks of the text. */
819    u32 a, b, c, d;
820
821    /* Temporaries used by the round function. */
822    u32 x, y;
823
824    /* Input whitening and packing. */
825    INPACK (0, c, 4);
826    INPACK (1, d, 5);
827    INPACK (2, a, 6);
828    INPACK (3, b, 7);
829
830    /* Encryption Feistel cycles. */
831    DECCYCLE (7);
832    DECCYCLE (6);
833    DECCYCLE (5);
834    DECCYCLE (4);
835    DECCYCLE (3);
836    DECCYCLE (2);
837    DECCYCLE (1);
838    DECCYCLE (0);
839
840    /* Output whitening and unpacking. */
841    OUTUNPACK (0, a, 0);
842    OUTUNPACK (1, b, 1);
843    OUTUNPACK (2, c, 2);
844    OUTUNPACK (3, d, 3);
845 }
846
847 static void
848 twofish_decrypt (void *context, byte *out, const byte *in)
849 {
850   TWOFISH_context *ctx = (TWOFISH_context *) context;
851   do_twofish_decrypt (ctx, out, in);
852   _gcry_burn_stack (24+3*sizeof (void*));
853 }
854
855 \f
856 /* Test a single encryption and decryption with each key size. */
857
858 static const char*
859 selftest (void)
860 {
861    TWOFISH_context ctx; /* Expanded key. */
862    byte scratch[16];    /* Encryption/decryption result buffer. */
863
864    /* Test vectors for single encryption/decryption.  Note that I am using
865     * the vectors from the Twofish paper's "known answer test", I=3 for
866     * 128-bit and I=4 for 256-bit, instead of the all-0 vectors from the
867     * "intermediate value test", because an all-0 key would trigger all the
868     * special cases in the RS matrix multiply, leaving the math untested. */
869    static  byte plaintext[16] = {
870       0xD4, 0x91, 0xDB, 0x16, 0xE7, 0xB1, 0xC3, 0x9E,
871       0x86, 0xCB, 0x08, 0x6B, 0x78, 0x9F, 0x54, 0x19
872    };
873    static byte key[16] = {
874       0x9F, 0x58, 0x9F, 0x5C, 0xF6, 0x12, 0x2C, 0x32,
875       0xB6, 0xBF, 0xEC, 0x2F, 0x2A, 0xE8, 0xC3, 0x5A
876    };
877    static const byte ciphertext[16] = {
878       0x01, 0x9F, 0x98, 0x09, 0xDE, 0x17, 0x11, 0x85,
879       0x8F, 0xAA, 0xC3, 0xA3, 0xBA, 0x20, 0xFB, 0xC3
880    };
881    static byte plaintext_256[16] = {
882       0x90, 0xAF, 0xE9, 0x1B, 0xB2, 0x88, 0x54, 0x4F,
883       0x2C, 0x32, 0xDC, 0x23, 0x9B, 0x26, 0x35, 0xE6
884    };
885    static byte key_256[32] = {
886       0xD4, 0x3B, 0xB7, 0x55, 0x6E, 0xA3, 0x2E, 0x46,
887       0xF2, 0xA2, 0x82, 0xB7, 0xD4, 0x5B, 0x4E, 0x0D,
888       0x57, 0xFF, 0x73, 0x9D, 0x4D, 0xC9, 0x2C, 0x1B,
889       0xD7, 0xFC, 0x01, 0x70, 0x0C, 0xC8, 0x21, 0x6F
890    };
891    static const byte ciphertext_256[16] = {
892       0x6C, 0xB4, 0x56, 0x1C, 0x40, 0xBF, 0x0A, 0x97,
893       0x05, 0x93, 0x1C, 0xB6, 0xD4, 0x08, 0xE7, 0xFA
894    };
895
896    twofish_setkey (&ctx, key, sizeof(key));
897    twofish_encrypt (&ctx, scratch, plaintext);
898    if (memcmp (scratch, ciphertext, sizeof (ciphertext)))
899      return "Twofish-128 test encryption failed.";
900    twofish_decrypt (&ctx, scratch, scratch);
901    if (memcmp (scratch, plaintext, sizeof (plaintext)))
902      return "Twofish-128 test decryption failed.";
903
904    twofish_setkey (&ctx, key_256, sizeof(key_256));
905    twofish_encrypt (&ctx, scratch, plaintext_256);
906    if (memcmp (scratch, ciphertext_256, sizeof (ciphertext_256)))
907      return "Twofish-256 test encryption failed.";
908    twofish_decrypt (&ctx, scratch, scratch);
909    if (memcmp (scratch, plaintext_256, sizeof (plaintext_256)))
910      return "Twofish-256 test decryption failed.";
911
912    return NULL;
913 }
914 \f
915 /* More complete test program.  This does 1000 encryptions and decryptions
916  * with each of 250 128-bit keys and 2000 encryptions and decryptions with
917  * each of 125 256-bit keys, using a feedback scheme similar to a Feistel
918  * cipher, so as to be sure of testing all the table entries pretty
919  * thoroughly.  We keep changing the keys so as to get a more meaningful
920  * performance number, since the key setup is non-trivial for Twofish. */
921
922 #ifdef TEST
923
924 #include <stdio.h>
925 #include <string.h>
926 #include <time.h>
927
928 int
929 main()
930 {
931    TWOFISH_context ctx;     /* Expanded key. */
932    int i, j;                /* Loop counters. */
933
934    const char *encrypt_msg; /* Message to print regarding encryption test;
935                              * the printf is done outside the loop to avoid
936                              * stuffing up the timing. */
937    clock_t timer; /* For computing elapsed time. */
938
939    /* Test buffer. */
940    byte buffer[4][16] = {
941       {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77,
942        0x88, 0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF},
943       {0x0F, 0x1E, 0x2D, 0x3C, 0x4B, 0x5A, 0x69, 0x78,
944        0x87, 0x96, 0xA5, 0xB4, 0xC3, 0xD2 ,0xE1, 0xF0},
945       {0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF,
946        0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54 ,0x32, 0x10},
947       {0x01, 0x23, 0x45, 0x67, 0x76, 0x54 ,0x32, 0x10,
948        0x89, 0xAB, 0xCD, 0xEF, 0xFE, 0xDC, 0xBA, 0x98}
949    };
950
951    /* Expected outputs for the million-operation test */
952    static const byte test_encrypt[4][16] = {
953       {0xC8, 0x23, 0xB8, 0xB7, 0x6B, 0xFE, 0x91, 0x13,
954        0x2F, 0xA7, 0x5E, 0xE6, 0x94, 0x77, 0x6F, 0x6B},
955       {0x90, 0x36, 0xD8, 0x29, 0xD5, 0x96, 0xC2, 0x8E,
956        0xE4, 0xFF, 0x76, 0xBC, 0xE5, 0x77, 0x88, 0x27},
957       {0xB8, 0x78, 0x69, 0xAF, 0x42, 0x8B, 0x48, 0x64,
958        0xF7, 0xE9, 0xF3, 0x9C, 0x42, 0x18, 0x7B, 0x73},
959       {0x7A, 0x88, 0xFB, 0xEB, 0x90, 0xA4, 0xB4, 0xA8,
960        0x43, 0xA3, 0x1D, 0xF1, 0x26, 0xC4, 0x53, 0x57}
961    };
962    static const byte test_decrypt[4][16] = {
963       {0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77,
964        0x88, 0x99, 0xAA, 0xBB, 0xCC, 0xDD, 0xEE, 0xFF},
965       {0x0F, 0x1E, 0x2D, 0x3C, 0x4B, 0x5A, 0x69, 0x78,
966        0x87, 0x96, 0xA5, 0xB4, 0xC3, 0xD2 ,0xE1, 0xF0},
967       {0x01, 0x23, 0x45, 0x67, 0x89, 0xAB, 0xCD, 0xEF,
968        0xFE, 0xDC, 0xBA, 0x98, 0x76, 0x54 ,0x32, 0x10},
969       {0x01, 0x23, 0x45, 0x67, 0x76, 0x54 ,0x32, 0x10,
970        0x89, 0xAB, 0xCD, 0xEF, 0xFE, 0xDC, 0xBA, 0x98}
971    };
972
973    /* Start the timer ticking. */
974    timer = clock ();
975
976    /* Encryption test. */
977    for (i = 0; i < 125; i++) {
978       twofish_setkey (&ctx, buffer[0], sizeof (buffer[0]));
979       for (j = 0; j < 1000; j++)
980         twofish_encrypt (&ctx, buffer[2], buffer[2]);
981       twofish_setkey (&ctx, buffer[1], sizeof (buffer[1]));
982       for (j = 0; j < 1000; j++)
983         twofish_encrypt (&ctx, buffer[3], buffer[3]);
984       twofish_setkey (&ctx, buffer[2], sizeof (buffer[2])*2);
985       for (j = 0; j < 1000; j++) {
986         twofish_encrypt (&ctx, buffer[0], buffer[0]);
987         twofish_encrypt (&ctx, buffer[1], buffer[1]);
988       }
989    }
990    encrypt_msg = memcmp (buffer, test_encrypt, sizeof (test_encrypt)) ?
991                  "encryption failure!\n" : "encryption OK!\n";
992
993    /* Decryption test. */
994    for (i = 0; i < 125; i++) {
995       twofish_setkey (&ctx, buffer[2], sizeof (buffer[2])*2);
996       for (j = 0; j < 1000; j++) {
997         twofish_decrypt (&ctx, buffer[0], buffer[0]);
998         twofish_decrypt (&ctx, buffer[1], buffer[1]);
999       }
1000       twofish_setkey (&ctx, buffer[1], sizeof (buffer[1]));
1001       for (j = 0; j < 1000; j++)
1002         twofish_decrypt (&ctx, buffer[3], buffer[3]);
1003       twofish_setkey (&ctx, buffer[0], sizeof (buffer[0]));
1004       for (j = 0; j < 1000; j++)
1005         twofish_decrypt (&ctx, buffer[2], buffer[2]);
1006    }
1007
1008    /* Stop the timer, and print results. */
1009    timer = clock () - timer;
1010    printf (encrypt_msg);
1011    printf (memcmp (buffer, test_decrypt, sizeof (test_decrypt)) ?
1012            "decryption failure!\n" : "decryption OK!\n");
1013    printf ("elapsed time: %.1f s.\n", (float) timer / CLOCKS_PER_SEC);
1014
1015    return 0;
1016 }
1017
1018 #endif /* TEST */
1019
1020 \f
1021
1022 gcry_cipher_spec_t cipher_spec_twofish =
1023   {
1024     "TWOFISH", 16, 256, sizeof (TWOFISH_context),
1025     twofish_setkey, twofish_encrypt, twofish_decrypt,
1026   };
1027
1028 gcry_cipher_spec_t cipher_spec_twofish128 =
1029   {
1030     "TWOFISH128", 16, 128, sizeof (TWOFISH_context),
1031     twofish_setkey, twofish_encrypt, twofish_decrypt,
1032   };