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