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