| Linux kernel & device driver programming |
| [ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] |
1 /* gf128mul.c - GF(2^128) multiplication funct 1
2 *
3 * Copyright (c) 2003, Dr Brian Gladman, Worce
4 * Copyright (c) 2006, Rik Snel <rsnel@cube.dy
5 *
6 * Based on Dr Brian Gladman's (GPL'd) work pu
7 * http://gladman.plushost.co.uk/oldsite/crypt
8 * See the original copyright notice below.
9 *
10 * This program is free software; you can redi
11 * under the terms of the GNU General Public L
12 * Software Foundation; either version 2 of th
13 * any later version.
14 */
15
16 /*
17 ---------------------------------------------
18 Copyright (c) 2003, Dr Brian Gladman, Worcest
19
20 LICENSE TERMS
21
22 The free distribution and use of this softwar
23 form is allowed (with or without changes) pro
24
25 1. distributions of this source code includ
26 notice, this list of conditions and the
27
28 2. distributions in binary form include the
29 notice, this list of conditions and the
30 in the documentation and/or other associ
31
32 3. the copyright holder's name is not used
33 built using this software without specif
34
35 ALTERNATIVELY, provided that this notice is r
36 may be distributed under the terms of the GNU
37 in which case the provisions of the GPL apply
38
39 DISCLAIMER
40
41 This software is provided 'as is' with no exp
42 in respect of its properties, including, but
43 and/or fitness for purpose.
44 ---------------------------------------------
45 Issue 31/01/2006
46
47 This file provides fast multiplication in GF(
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(
58 q(0x08), q(0x09), q(0x0a), q(0x0b), q(
59 q(0x10), q(0x11), q(0x12), q(0x13), q(
60 q(0x18), q(0x19), q(0x1a), q(0x1b), q(
61 q(0x20), q(0x21), q(0x22), q(0x23), q(
62 q(0x28), q(0x29), q(0x2a), q(0x2b), q(
63 q(0x30), q(0x31), q(0x32), q(0x33), q(
64 q(0x38), q(0x39), q(0x3a), q(0x3b), q(
65 q(0x40), q(0x41), q(0x42), q(0x43), q(
66 q(0x48), q(0x49), q(0x4a), q(0x4b), q(
67 q(0x50), q(0x51), q(0x52), q(0x53), q(
68 q(0x58), q(0x59), q(0x5a), q(0x5b), q(
69 q(0x60), q(0x61), q(0x62), q(0x63), q(
70 q(0x68), q(0x69), q(0x6a), q(0x6b), q(
71 q(0x70), q(0x71), q(0x72), q(0x73), q(
72 q(0x78), q(0x79), q(0x7a), q(0x7b), q(
73 q(0x80), q(0x81), q(0x82), q(0x83), q(
74 q(0x88), q(0x89), q(0x8a), q(0x8b), q(
75 q(0x90), q(0x91), q(0x92), q(0x93), q(
76 q(0x98), q(0x99), q(0x9a), q(0x9b), q(
77 q(0xa0), q(0xa1), q(0xa2), q(0xa3), q(
78 q(0xa8), q(0xa9), q(0xaa), q(0xab), q(
79 q(0xb0), q(0xb1), q(0xb2), q(0xb3), q(
80 q(0xb8), q(0xb9), q(0xba), q(0xbb), q(
81 q(0xc0), q(0xc1), q(0xc2), q(0xc3), q(
82 q(0xc8), q(0xc9), q(0xca), q(0xcb), q(
83 q(0xd0), q(0xd1), q(0xd2), q(0xd3), q(
84 q(0xd8), q(0xd9), q(0xda), q(0xdb), q(
85 q(0xe0), q(0xe1), q(0xe2), q(0xe3), q(
86 q(0xe8), q(0xe9), q(0xea), q(0xeb), q(
87 q(0xf0), q(0xf1), q(0xf2), q(0xf3), q(
88 q(0xf8), q(0xf9), q(0xfa), q(0xfb), q(
89 }
90
91 /* Given the value i in 0..255 as the byt
92 in GHASH is multipled by x^8, this functio
93 are generated in the lo 16-bit word of the
94 modular polynomial. The values lo_byte and
95 macro xp_fun(lo_byte, hi_byte) so that the
96 memory as required by a suitable definitio
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 & 0x4
104 (i & 0x20 ? xx(10, e0) : 0) ^ (i & 0x1
105 (i & 0x08 ? xx(04, 38) : 0) ^ (i & 0x0
106 (i & 0x02 ? xx(01, 0e) : 0) ^ (i & 0x0
107 )
108
109 #define xda_lle(i) ( \
110 (i & 0x80 ? xx(e1, 00) : 0) ^ (i & 0x4
111 (i & 0x20 ? xx(38, 40) : 0) ^ (i & 0x1
112 (i & 0x08 ? xx(0e, 10) : 0) ^ (i & 0x0
113 (i & 0x02 ? xx(03, 84) : 0) ^ (i & 0x0
114 )
115
116 static const u16 gf128mul_table_lle[256] = gf1
117 static const u16 gf128mul_table_bbe[256] = gf1
118
119 /* These functions multiply a field element by
120 * in the polynomial field representation. It
121 * to gain speed but compensates for machine e
122 * correctly on both styles of machine.
123 */
124
125 static void gf128mul_x_lle(be128 *r, const be1
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)
130
131 r->b = cpu_to_be64((b >> 1) | (a << 63
132 r->a = cpu_to_be64((a >> 1) ^ (_tt <<
133 }
134
135 static void gf128mul_x_bbe(be128 *r, const be1
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 void gf128mul_x_ble(be128 *r, const be128 *x)
146 {
147 u64 a = le64_to_cpu(x->a);
148 u64 b = le64_to_cpu(x->b);
149 u64 _tt = gf128mul_table_bbe[b >> 63];
150
151 r->a = cpu_to_le64((a << 1) ^ _tt);
152 r->b = cpu_to_le64((b << 1) | (a >> 63
153 }
154 EXPORT_SYMBOL(gf128mul_x_ble);
155
156 static void gf128mul_x8_lle(be128 *x)
157 {
158 u64 a = be64_to_cpu(x->a);
159 u64 b = be64_to_cpu(x->b);
160 u64 _tt = gf128mul_table_lle[b & 0xff]
161
162 x->b = cpu_to_be64((b >> 8) | (a << 56
163 x->a = cpu_to_be64((a >> 8) ^ (_tt <<
164 }
165
166 static void gf128mul_x8_bbe(be128 *x)
167 {
168 u64 a = be64_to_cpu(x->a);
169 u64 b = be64_to_cpu(x->b);
170 u64 _tt = gf128mul_table_bbe[a >> 56];
171
172 x->a = cpu_to_be64((a << 8) | (b >> 56
173 x->b = cpu_to_be64((b << 8) ^ _tt);
174 }
175
176 void gf128mul_lle(be128 *r, const be128 *b)
177 {
178 be128 p[8];
179 int i;
180
181 p[0] = *r;
182 for (i = 0; i < 7; ++i)
183 gf128mul_x_lle(&p[i + 1], &p[i
184
185 memset(r, 0, sizeof(r));
186 for (i = 0;;) {
187 u8 ch = ((u8 *)b)[15 - i];
188
189 if (ch & 0x80)
190 be128_xor(r, r, &p[0])
191 if (ch & 0x40)
192 be128_xor(r, r, &p[1])
193 if (ch & 0x20)
194 be128_xor(r, r, &p[2])
195 if (ch & 0x10)
196 be128_xor(r, r, &p[3])
197 if (ch & 0x08)
198 be128_xor(r, r, &p[4])
199 if (ch & 0x04)
200 be128_xor(r, r, &p[5])
201 if (ch & 0x02)
202 be128_xor(r, r, &p[6])
203 if (ch & 0x01)
204 be128_xor(r, r, &p[7])
205
206 if (++i >= 16)
207 break;
208
209 gf128mul_x8_lle(r);
210 }
211 }
212 EXPORT_SYMBOL(gf128mul_lle);
213
214 void gf128mul_bbe(be128 *r, const be128 *b)
215 {
216 be128 p[8];
217 int i;
218
219 p[0] = *r;
220 for (i = 0; i < 7; ++i)
221 gf128mul_x_bbe(&p[i + 1], &p[i
222
223 memset(r, 0, sizeof(r));
224 for (i = 0;;) {
225 u8 ch = ((u8 *)b)[i];
226
227 if (ch & 0x80)
228 be128_xor(r, r, &p[7])
229 if (ch & 0x40)
230 be128_xor(r, r, &p[6])
231 if (ch & 0x20)
232 be128_xor(r, r, &p[5])
233 if (ch & 0x10)
234 be128_xor(r, r, &p[4])
235 if (ch & 0x08)
236 be128_xor(r, r, &p[3])
237 if (ch & 0x04)
238 be128_xor(r, r, &p[2])
239 if (ch & 0x02)
240 be128_xor(r, r, &p[1])
241 if (ch & 0x01)
242 be128_xor(r, r, &p[0])
243
244 if (++i >= 16)
245 break;
246
247 gf128mul_x8_bbe(r);
248 }
249 }
250 EXPORT_SYMBOL(gf128mul_bbe);
251
252 /* This version uses 64k bytes of table s
253 A 16 byte buffer has to be multiplied by a
254 value in GF(128). If we consider a GF(128
255 the buffer's lowest byte, we can construct
256 the 256 16 byte values that result from th
257 of this byte. This requires 4096 bytes. B
258 need tables for each of the 16 higher byte
259 buffer as well, which makes 64 kbytes in t
260 */
261 /* additional explanation
262 * t[0][BYTE] contains g*BYTE
263 * t[1][BYTE] contains g*x^8*BYTE
264 * ..
265 * t[15][BYTE] contains g*x^120*BYTE */
266 struct gf128mul_64k *gf128mul_init_64k_lle(con
267 {
268 struct gf128mul_64k *t;
269 int i, j, k;
270
271 t = kzalloc(sizeof(*t), GFP_KERNEL);
272 if (!t)
273 goto out;
274
275 for (i = 0; i < 16; i++) {
276 t->t[i] = kzalloc(sizeof(*t->t
277 if (!t->t[i]) {
278 gf128mul_free_64k(t);
279 t = NULL;
280 goto out;
281 }
282 }
283
284 t->t[0]->t[128] = *g;
285 for (j = 64; j > 0; j >>= 1)
286 gf128mul_x_lle(&t->t[0]->t[j],
287
288 for (i = 0;;) {
289 for (j = 2; j < 256; j += j)
290 for (k = 1; k < j; ++k
291 be128_xor(&t->
292 &t->
293
294 if (++i >= 16)
295 break;
296
297 for (j = 128; j > 0; j >>= 1)
298 t->t[i]->t[j] = t->t[i
299 gf128mul_x8_lle(&t->t[
300 }
301 }
302
303 out:
304 return t;
305 }
306 EXPORT_SYMBOL(gf128mul_init_64k_lle);
307
308 struct gf128mul_64k *gf128mul_init_64k_bbe(con
309 {
310 struct gf128mul_64k *t;
311 int i, j, k;
312
313 t = kzalloc(sizeof(*t), GFP_KERNEL);
314 if (!t)
315 goto out;
316
317 for (i = 0; i < 16; i++) {
318 t->t[i] = kzalloc(sizeof(*t->t
319 if (!t->t[i]) {
320 gf128mul_free_64k(t);
321 t = NULL;
322 goto out;
323 }
324 }
325
326 t->t[0]->t[1] = *g;
327 for (j = 1; j <= 64; j <<= 1)
328 gf128mul_x_bbe(&t->t[0]->t[j +
329
330 for (i = 0;;) {
331 for (j = 2; j < 256; j += j)
332 for (k = 1; k < j; ++k
333 be128_xor(&t->
334 &t->
335
336 if (++i >= 16)
337 break;
338
339 for (j = 128; j > 0; j >>= 1)
340 t->t[i]->t[j] = t->t[i
341 gf128mul_x8_bbe(&t->t[
342 }
343 }
344
345 out:
346 return t;
347 }
348 EXPORT_SYMBOL(gf128mul_init_64k_bbe);
349
350 void gf128mul_free_64k(struct gf128mul_64k *t)
351 {
352 int i;
353
354 for (i = 0; i < 16; i++)
355 kfree(t->t[i]);
356 kfree(t);
357 }
358 EXPORT_SYMBOL(gf128mul_free_64k);
359
360 void gf128mul_64k_lle(be128 *a, struct gf128mu
361 {
362 u8 *ap = (u8 *)a;
363 be128 r[1];
364 int i;
365
366 *r = t->t[0]->t[ap[0]];
367 for (i = 1; i < 16; ++i)
368 be128_xor(r, r, &t->t[i]->t[ap
369 *a = *r;
370 }
371 EXPORT_SYMBOL(gf128mul_64k_lle);
372
373 void gf128mul_64k_bbe(be128 *a, struct gf128mu
374 {
375 u8 *ap = (u8 *)a;
376 be128 r[1];
377 int i;
378
379 *r = t->t[0]->t[ap[15]];
380 for (i = 1; i < 16; ++i)
381 be128_xor(r, r, &t->t[i]->t[ap
382 *a = *r;
383 }
384 EXPORT_SYMBOL(gf128mul_64k_bbe);
385
386 /* This version uses 4k bytes of table sp
387 A 16 byte buffer has to be multiplied by a
388 value in GF(128). If we consider a GF(128
389 single byte, we can construct a table of t
390 values that result from the 256 values of
391 This requires 4096 bytes. If we take the h
392 the buffer and use this table to get the r
393 have to multiply by x^120 to get the final
394 next highest byte the result has to be mul
395 and so on. But we can do this by accumulat
396 in an accumulator starting with the result
397 byte. We repeatedly multiply the accumula
398 x^8 and then add in (i.e. xor) the 16 byte
399 lower byte in the buffer, stopping when we
400 lowest byte. This requires a 4096 byte tab
401 */
402 struct gf128mul_4k *gf128mul_init_4k_lle(const
403 {
404 struct gf128mul_4k *t;
405 int j, k;
406
407 t = kzalloc(sizeof(*t), GFP_KERNEL);
408 if (!t)
409 goto out;
410
411 t->t[128] = *g;
412 for (j = 64; j > 0; j >>= 1)
413 gf128mul_x_lle(&t->t[j], &t->t
414
415 for (j = 2; j < 256; j += j)
416 for (k = 1; k < j; ++k)
417 be128_xor(&t->t[j + k]
418
419 out:
420 return t;
421 }
422 EXPORT_SYMBOL(gf128mul_init_4k_lle);
423
424 struct gf128mul_4k *gf128mul_init_4k_bbe(const
425 {
426 struct gf128mul_4k *t;
427 int j, k;
428
429 t = kzalloc(sizeof(*t), GFP_KERNEL);
430 if (!t)
431 goto out;
432
433 t->t[1] = *g;
434 for (j = 1; j <= 64; j <<= 1)
435 gf128mul_x_bbe(&t->t[j + j], &
436
437 for (j = 2; j < 256; j += j)
438 for (k = 1; k < j; ++k)
439 be128_xor(&t->t[j + k]
440
441 out:
442 return t;
443 }
444 EXPORT_SYMBOL(gf128mul_init_4k_bbe);
445
446 void gf128mul_4k_lle(be128 *a, struct gf128mul
447 {
448 u8 *ap = (u8 *)a;
449 be128 r[1];
450 int i = 15;
451
452 *r = t->t[ap[15]];
453 while (i--) {
454 gf128mul_x8_lle(r);
455 be128_xor(r, r, &t->t[ap[i]]);
456 }
457 *a = *r;
458 }
459 EXPORT_SYMBOL(gf128mul_4k_lle);
460
461 void gf128mul_4k_bbe(be128 *a, struct gf128mul
462 {
463 u8 *ap = (u8 *)a;
464 be128 r[1];
465 int i = 0;
466
467 *r = t->t[ap[0]];
468 while (++i < 16) {
469 gf128mul_x8_bbe(r);
470 be128_xor(r, r, &t->t[ap[i]]);
471 }
472 *a = *r;
473 }
474 EXPORT_SYMBOL(gf128mul_4k_bbe);
475
476 MODULE_LICENSE("GPL");
477 MODULE_DESCRIPTION("Functions for multiplying
478
| This page was automatically generated by the LXR engine. |