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