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