[CRYPTO] lib: table driven multiplications in GF(2^128)
[linux-3.10.git] / crypto / gf128mul.c
1 /* gf128mul.c - GF(2^128) multiplication functions
2  *
3  * Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.
4  * Copyright (c) 2006, Rik Snel <rsnel@cube.dyndns.org>
5  *
6  * Based on Dr Brian Gladman's (GPL'd) work published at
7  * http://fp.gladman.plus.com/cryptography_technology/index.htm
8  * See the original copyright notice below.
9  *
10  * This program is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU General Public License as published by the Free
12  * Software Foundation; either version 2 of the License, or (at your option)
13  * any later version.
14  */
15
16 /*
17  ---------------------------------------------------------------------------
18  Copyright (c) 2003, Dr Brian Gladman, Worcester, UK.   All rights reserved.
19
20  LICENSE TERMS
21
22  The free distribution and use of this software in both source and binary
23  form is allowed (with or without changes) provided that:
24
25    1. distributions of this source code include the above copyright
26       notice, this list of conditions and the following disclaimer;
27
28    2. distributions in binary form include the above copyright
29       notice, this list of conditions and the following disclaimer
30       in the documentation and/or other associated materials;
31
32    3. the copyright holder's name is not used to endorse products
33       built using this software without specific written permission.
34
35  ALTERNATIVELY, provided that this notice is retained in full, this product
36  may be distributed under the terms of the GNU General Public License (GPL),
37  in which case the provisions of the GPL apply INSTEAD OF those given above.
38
39  DISCLAIMER
40
41  This software is provided 'as is' with no explicit or implied warranties
42  in respect of its properties, including, but not limited to, correctness
43  and/or fitness for purpose.
44  ---------------------------------------------------------------------------
45  Issue 31/01/2006
46
47  This file provides fast multiplication in GF(128) as required by several
48  cryptographic authentication modes
49 */
50
51 #include <crypto/gf128mul.h>
52 #include <linux/kernel.h>
53 #include <linux/module.h>
54 #include <linux/slab.h>
55
56 #define gf128mul_dat(q) { \
57         q(0x00), q(0x01), q(0x02), q(0x03), q(0x04), q(0x05), q(0x06), q(0x07),\
58         q(0x08), q(0x09), q(0x0a), q(0x0b), q(0x0c), q(0x0d), q(0x0e), q(0x0f),\
59         q(0x10), q(0x11), q(0x12), q(0x13), q(0x14), q(0x15), q(0x16), q(0x17),\
60         q(0x18), q(0x19), q(0x1a), q(0x1b), q(0x1c), q(0x1d), q(0x1e), q(0x1f),\
61         q(0x20), q(0x21), q(0x22), q(0x23), q(0x24), q(0x25), q(0x26), q(0x27),\
62         q(0x28), q(0x29), q(0x2a), q(0x2b), q(0x2c), q(0x2d), q(0x2e), q(0x2f),\
63         q(0x30), q(0x31), q(0x32), q(0x33), q(0x34), q(0x35), q(0x36), q(0x37),\
64         q(0x38), q(0x39), q(0x3a), q(0x3b), q(0x3c), q(0x3d), q(0x3e), q(0x3f),\
65         q(0x40), q(0x41), q(0x42), q(0x43), q(0x44), q(0x45), q(0x46), q(0x47),\
66         q(0x48), q(0x49), q(0x4a), q(0x4b), q(0x4c), q(0x4d), q(0x4e), q(0x4f),\
67         q(0x50), q(0x51), q(0x52), q(0x53), q(0x54), q(0x55), q(0x56), q(0x57),\
68         q(0x58), q(0x59), q(0x5a), q(0x5b), q(0x5c), q(0x5d), q(0x5e), q(0x5f),\
69         q(0x60), q(0x61), q(0x62), q(0x63), q(0x64), q(0x65), q(0x66), q(0x67),\
70         q(0x68), q(0x69), q(0x6a), q(0x6b), q(0x6c), q(0x6d), q(0x6e), q(0x6f),\
71         q(0x70), q(0x71), q(0x72), q(0x73), q(0x74), q(0x75), q(0x76), q(0x77),\
72         q(0x78), q(0x79), q(0x7a), q(0x7b), q(0x7c), q(0x7d), q(0x7e), q(0x7f),\
73         q(0x80), q(0x81), q(0x82), q(0x83), q(0x84), q(0x85), q(0x86), q(0x87),\
74         q(0x88), q(0x89), q(0x8a), q(0x8b), q(0x8c), q(0x8d), q(0x8e), q(0x8f),\
75         q(0x90), q(0x91), q(0x92), q(0x93), q(0x94), q(0x95), q(0x96), q(0x97),\
76         q(0x98), q(0x99), q(0x9a), q(0x9b), q(0x9c), q(0x9d), q(0x9e), q(0x9f),\
77         q(0xa0), q(0xa1), q(0xa2), q(0xa3), q(0xa4), q(0xa5), q(0xa6), q(0xa7),\
78         q(0xa8), q(0xa9), q(0xaa), q(0xab), q(0xac), q(0xad), q(0xae), q(0xaf),\
79         q(0xb0), q(0xb1), q(0xb2), q(0xb3), q(0xb4), q(0xb5), q(0xb6), q(0xb7),\
80         q(0xb8), q(0xb9), q(0xba), q(0xbb), q(0xbc), q(0xbd), q(0xbe), q(0xbf),\
81         q(0xc0), q(0xc1), q(0xc2), q(0xc3), q(0xc4), q(0xc5), q(0xc6), q(0xc7),\
82         q(0xc8), q(0xc9), q(0xca), q(0xcb), q(0xcc), q(0xcd), q(0xce), q(0xcf),\
83         q(0xd0), q(0xd1), q(0xd2), q(0xd3), q(0xd4), q(0xd5), q(0xd6), q(0xd7),\
84         q(0xd8), q(0xd9), q(0xda), q(0xdb), q(0xdc), q(0xdd), q(0xde), q(0xdf),\
85         q(0xe0), q(0xe1), q(0xe2), q(0xe3), q(0xe4), q(0xe5), q(0xe6), q(0xe7),\
86         q(0xe8), q(0xe9), q(0xea), q(0xeb), q(0xec), q(0xed), q(0xee), q(0xef),\
87         q(0xf0), q(0xf1), q(0xf2), q(0xf3), q(0xf4), q(0xf5), q(0xf6), q(0xf7),\
88         q(0xf8), q(0xf9), q(0xfa), q(0xfb), q(0xfc), q(0xfd), q(0xfe), q(0xff) \
89 }
90
91 /*      Given the value i in 0..255 as the byte overflow when a field element
92     in GHASH is multipled by x^8, this function will return the values that
93     are generated in the lo 16-bit word of the field value by applying the
94     modular polynomial. The values lo_byte and hi_byte are returned via the
95     macro xp_fun(lo_byte, hi_byte) so that the values can be assembled into
96     memory as required by a suitable definition of this macro operating on
97     the table above
98 */
99
100 #define xx(p, q)        0x##p##q
101
102 #define xda_bbe(i) ( \
103         (i & 0x80 ? xx(43, 80) : 0) ^ (i & 0x40 ? xx(21, c0) : 0) ^ \
104         (i & 0x20 ? xx(10, e0) : 0) ^ (i & 0x10 ? xx(08, 70) : 0) ^ \
105         (i & 0x08 ? xx(04, 38) : 0) ^ (i & 0x04 ? xx(02, 1c) : 0) ^ \
106         (i & 0x02 ? xx(01, 0e) : 0) ^ (i & 0x01 ? xx(00, 87) : 0) \
107 )
108
109 #define xda_lle(i) ( \
110         (i & 0x80 ? xx(e1, 00) : 0) ^ (i & 0x40 ? xx(70, 80) : 0) ^ \
111         (i & 0x20 ? xx(38, 40) : 0) ^ (i & 0x10 ? xx(1c, 20) : 0) ^ \
112         (i & 0x08 ? xx(0e, 10) : 0) ^ (i & 0x04 ? xx(07, 08) : 0) ^ \
113         (i & 0x02 ? xx(03, 84) : 0) ^ (i & 0x01 ? xx(01, c2) : 0) \
114 )
115
116 static const u16 gf128mul_table_lle[256] = gf128mul_dat(xda_lle);
117 static const u16 gf128mul_table_bbe[256] = gf128mul_dat(xda_bbe);
118
119 /* These functions multiply a field element by x, by x^4 and by x^8
120  * in the polynomial field representation. It uses 32-bit word operations
121  * to gain speed but compensates for machine endianess and hence works
122  * correctly on both styles of machine.
123  */
124
125 static void gf128mul_x_lle(be128 *r, const be128 *x)
126 {
127         u64 a = be64_to_cpu(x->a);
128         u64 b = be64_to_cpu(x->b);
129         u64 _tt = gf128mul_table_lle[(b << 7) & 0xff];
130
131         r->b = cpu_to_be64((b >> 1) | (a << 63));
132         r->a = cpu_to_be64((a >> 1) ^ (_tt << 48));
133 }
134
135 static void gf128mul_x_bbe(be128 *r, const be128 *x)
136 {
137         u64 a = be64_to_cpu(x->a);
138         u64 b = be64_to_cpu(x->b);
139         u64 _tt = gf128mul_table_bbe[a >> 63];
140
141         r->a = cpu_to_be64((a << 1) | (b >> 63));
142         r->b = cpu_to_be64((b << 1) ^ _tt);
143 }
144
145 static void gf128mul_x8_lle(be128 *x)
146 {
147         u64 a = be64_to_cpu(x->a);
148         u64 b = be64_to_cpu(x->b);
149         u64 _tt = gf128mul_table_lle[b & 0xff];
150
151         x->b = cpu_to_be64((b >> 8) | (a << 56));
152         x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
153 }
154
155 static void gf128mul_x8_bbe(be128 *x)
156 {
157         u64 a = be64_to_cpu(x->a);
158         u64 b = be64_to_cpu(x->b);
159         u64 _tt = gf128mul_table_bbe[a >> 56];
160
161         x->a = cpu_to_be64((a << 8) | (b >> 56));
162         x->b = cpu_to_be64((b << 8) ^ _tt);
163 }
164
165 void gf128mul_lle(be128 *r, const be128 *b)
166 {
167         be128 p[8];
168         int i;
169
170         p[0] = *r;
171         for (i = 0; i < 7; ++i)
172                 gf128mul_x_lle(&p[i + 1], &p[i]);
173
174         memset(r, 0, sizeof(r));
175         for (i = 0;;) {
176                 u8 ch = ((u8 *)b)[15 - i];
177
178                 if (ch & 0x80)
179                         be128_xor(r, r, &p[0]);
180                 if (ch & 0x40)
181                         be128_xor(r, r, &p[1]);
182                 if (ch & 0x20)
183                         be128_xor(r, r, &p[2]);
184                 if (ch & 0x10)
185                         be128_xor(r, r, &p[3]);
186                 if (ch & 0x08)
187                         be128_xor(r, r, &p[4]);
188                 if (ch & 0x04)
189                         be128_xor(r, r, &p[5]);
190                 if (ch & 0x02)
191                         be128_xor(r, r, &p[6]);
192                 if (ch & 0x01)
193                         be128_xor(r, r, &p[7]);
194
195                 if (++i >= 16)
196                         break;
197
198                 gf128mul_x8_lle(r);
199         }
200 }
201 EXPORT_SYMBOL(gf128mul_lle);
202
203 void gf128mul_bbe(be128 *r, const be128 *b)
204 {
205         be128 p[8];
206         int i;
207
208         p[0] = *r;
209         for (i = 0; i < 7; ++i)
210                 gf128mul_x_bbe(&p[i + 1], &p[i]);
211
212         memset(r, 0, sizeof(r));
213         for (i = 0;;) {
214                 u8 ch = ((u8 *)b)[i];
215
216                 if (ch & 0x80)
217                         be128_xor(r, r, &p[7]);
218                 if (ch & 0x40)
219                         be128_xor(r, r, &p[6]);
220                 if (ch & 0x20)
221                         be128_xor(r, r, &p[5]);
222                 if (ch & 0x10)
223                         be128_xor(r, r, &p[4]);
224                 if (ch & 0x08)
225                         be128_xor(r, r, &p[3]);
226                 if (ch & 0x04)
227                         be128_xor(r, r, &p[2]);
228                 if (ch & 0x02)
229                         be128_xor(r, r, &p[1]);
230                 if (ch & 0x01)
231                         be128_xor(r, r, &p[0]);
232
233                 if (++i >= 16)
234                         break;
235
236                 gf128mul_x8_bbe(r);
237         }
238 }
239 EXPORT_SYMBOL(gf128mul_bbe);
240
241 /*      This version uses 64k bytes of table space.
242     A 16 byte buffer has to be multiplied by a 16 byte key
243     value in GF(128).  If we consider a GF(128) value in
244     the buffer's lowest byte, we can construct a table of
245     the 256 16 byte values that result from the 256 values
246     of this byte.  This requires 4096 bytes. But we also
247     need tables for each of the 16 higher bytes in the
248     buffer as well, which makes 64 kbytes in total.
249 */
250 /* additional explanation
251  * t[0][BYTE] contains g*BYTE
252  * t[1][BYTE] contains g*x^8*BYTE
253  *  ..
254  * t[15][BYTE] contains g*x^120*BYTE */
255 struct gf128mul_64k *gf128mul_init_64k_lle(const be128 *g)
256 {
257         struct gf128mul_64k *t;
258         int i, j, k;
259
260         t = kzalloc(sizeof(*t), GFP_KERNEL);
261         if (!t)
262                 goto out;
263
264         for (i = 0; i < 16; i++) {
265                 t->t[i] = kzalloc(sizeof(*t->t[i]), GFP_KERNEL);
266                 if (!t->t[i]) {
267                         gf128mul_free_64k(t);
268                         t = NULL;
269                         goto out;
270                 }
271         }
272
273         t->t[0]->t[128] = *g;
274         for (j = 64; j > 0; j >>= 1)
275                 gf128mul_x_lle(&t->t[0]->t[j], &t->t[0]->t[j + j]);
276
277         for (i = 0;;) {
278                 for (j = 2; j < 256; j += j)
279                         for (k = 1; k < j; ++k)
280                                 be128_xor(&t->t[i]->t[j + k],
281                                           &t->t[i]->t[j], &t->t[i]->t[k]);
282
283                 if (++i >= 16)
284                         break;
285
286                 for (j = 128; j > 0; j >>= 1) {
287                         t->t[i]->t[j] = t->t[i - 1]->t[j];
288                         gf128mul_x8_lle(&t->t[i]->t[j]);
289                 }
290         }
291
292 out:
293         return t;
294 }
295 EXPORT_SYMBOL(gf128mul_init_64k_lle);
296
297 struct gf128mul_64k *gf128mul_init_64k_bbe(const be128 *g)
298 {
299         struct gf128mul_64k *t;
300         int i, j, k;
301
302         t = kzalloc(sizeof(*t), GFP_KERNEL);
303         if (!t)
304                 goto out;
305
306         for (i = 0; i < 16; i++) {
307                 t->t[i] = kzalloc(sizeof(*t->t[i]), GFP_KERNEL);
308                 if (!t->t[i]) {
309                         gf128mul_free_64k(t);
310                         t = NULL;
311                         goto out;
312                 }
313         }
314
315         t->t[0]->t[1] = *g;
316         for (j = 1; j <= 64; j <<= 1)
317                 gf128mul_x_bbe(&t->t[0]->t[j + j], &t->t[0]->t[j]);
318
319         for (i = 0;;) {
320                 for (j = 2; j < 256; j += j)
321                         for (k = 1; k < j; ++k)
322                                 be128_xor(&t->t[i]->t[j + k],
323                                           &t->t[i]->t[j], &t->t[i]->t[k]);
324
325                 if (++i >= 16)
326                         break;
327
328                 for (j = 128; j > 0; j >>= 1) {
329                         t->t[i]->t[j] = t->t[i - 1]->t[j];
330                         gf128mul_x8_bbe(&t->t[i]->t[j]);
331                 }
332         }
333
334 out:
335         return t;
336 }
337 EXPORT_SYMBOL(gf128mul_init_64k_bbe);
338
339 void gf128mul_free_64k(struct gf128mul_64k *t)
340 {
341         int i;
342
343         for (i = 0; i < 16; i++)
344                 kfree(t->t[i]);
345         kfree(t);
346 }
347 EXPORT_SYMBOL(gf128mul_free_64k);
348
349 void gf128mul_64k_lle(be128 *a, struct gf128mul_64k *t)
350 {
351         u8 *ap = (u8 *)a;
352         be128 r[1];
353         int i;
354
355         *r = t->t[0]->t[ap[0]];
356         for (i = 1; i < 16; ++i)
357                 be128_xor(r, r, &t->t[i]->t[ap[i]]);
358         *a = *r;
359 }
360 EXPORT_SYMBOL(gf128mul_64k_lle);
361
362 void gf128mul_64k_bbe(be128 *a, struct gf128mul_64k *t)
363 {
364         u8 *ap = (u8 *)a;
365         be128 r[1];
366         int i;
367
368         *r = t->t[0]->t[ap[15]];
369         for (i = 1; i < 16; ++i)
370                 be128_xor(r, r, &t->t[i]->t[ap[15 - i]]);
371         *a = *r;
372 }
373 EXPORT_SYMBOL(gf128mul_64k_bbe);
374
375 /*      This version uses 4k bytes of table space.
376     A 16 byte buffer has to be multiplied by a 16 byte key
377     value in GF(128).  If we consider a GF(128) value in a
378     single byte, we can construct a table of the 256 16 byte
379     values that result from the 256 values of this byte.
380     This requires 4096 bytes. If we take the highest byte in
381     the buffer and use this table to get the result, we then
382     have to multiply by x^120 to get the final value. For the
383     next highest byte the result has to be multiplied by x^112
384     and so on. But we can do this by accumulating the result
385     in an accumulator starting with the result for the top
386     byte.  We repeatedly multiply the accumulator value by
387     x^8 and then add in (i.e. xor) the 16 bytes of the next
388     lower byte in the buffer, stopping when we reach the
389     lowest byte. This requires a 4096 byte table.
390 */
391 struct gf128mul_4k *gf128mul_init_4k_lle(const be128 *g)
392 {
393         struct gf128mul_4k *t;
394         int j, k;
395
396         t = kzalloc(sizeof(*t), GFP_KERNEL);
397         if (!t)
398                 goto out;
399
400         t->t[128] = *g;
401         for (j = 64; j > 0; j >>= 1)
402                 gf128mul_x_lle(&t->t[j], &t->t[j+j]);
403
404         for (j = 2; j < 256; j += j)
405                 for (k = 1; k < j; ++k)
406                         be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
407
408 out:
409         return t;
410 }
411 EXPORT_SYMBOL(gf128mul_init_4k_lle);
412
413 struct gf128mul_4k *gf128mul_init_4k_bbe(const be128 *g)
414 {
415         struct gf128mul_4k *t;
416         int j, k;
417
418         t = kzalloc(sizeof(*t), GFP_KERNEL);
419         if (!t)
420                 goto out;
421
422         t->t[1] = *g;
423         for (j = 1; j <= 64; j <<= 1)
424                 gf128mul_x_bbe(&t->t[j + j], &t->t[j]);
425
426         for (j = 2; j < 256; j += j)
427                 for (k = 1; k < j; ++k)
428                         be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
429
430 out:
431         return t;
432 }
433 EXPORT_SYMBOL(gf128mul_init_4k_bbe);
434
435 void gf128mul_4k_lle(be128 *a, struct gf128mul_4k *t)
436 {
437         u8 *ap = (u8 *)a;
438         be128 r[1];
439         int i = 15;
440
441         *r = t->t[ap[15]];
442         while (i--) {
443                 gf128mul_x8_lle(r);
444                 be128_xor(r, r, &t->t[ap[i]]);
445         }
446         *a = *r;
447 }
448 EXPORT_SYMBOL(gf128mul_4k_lle);
449
450 void gf128mul_4k_bbe(be128 *a, struct gf128mul_4k *t)
451 {
452         u8 *ap = (u8 *)a;
453         be128 r[1];
454         int i = 0;
455
456         *r = t->t[ap[0]];
457         while (++i < 16) {
458                 gf128mul_x8_bbe(r);
459                 be128_xor(r, r, &t->t[ap[i]]);
460         }
461         *a = *r;
462 }
463 EXPORT_SYMBOL(gf128mul_4k_bbe);
464
465 MODULE_LICENSE("GPL");
466 MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)");