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://gladman.plushost.co.uk/oldsite/cryptography_technology/index.php
   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(2^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 /*
  92  * Given a value i in 0..255 as the byte overflow when a field element
  93  * in GF(2^128) is multiplied by x^8, the following macro returns the
  94  * 16-bit value that must be XOR-ed into the low-degree end of the
  95  * product to reduce it modulo the polynomial x^128 + x^7 + x^2 + x + 1.
  96  *
  97  * There are two versions of the macro, and hence two tables: one for
  98  * the "be" convention where the highest-order bit is the coefficient of
  99  * the highest-degree polynomial term, and one for the "le" convention
 100  * where the highest-order bit is the coefficient of the lowest-degree
 101  * polynomial term.  In both cases the values are stored in CPU byte
 102  * endianness such that the coefficients are ordered consistently across
 103  * bytes, i.e. in the "be" table bits 15..0 of the stored value
 104  * correspond to the coefficients of x^15..x^0, and in the "le" table
 105  * bits 15..0 correspond to the coefficients of x^0..x^15.
 106  *
 107  * Therefore, provided that the appropriate byte endianness conversions
 108  * are done by the multiplication functions (and these must be in place
 109  * anyway to support both little endian and big endian CPUs), the "be"
 110  * table can be used for multiplications of both "bbe" and "ble"
 111  * elements, and the "le" table can be used for multiplications of both
 112  * "lle" and "lbe" elements.
 113  */
 114
 115 #define xda_be(i) ( \
 116         (i & 0x80 ? 0x4380 : 0) ^ (i & 0x40 ? 0x21c0 : 0) ^ \
 117         (i & 0x20 ? 0x10e0 : 0) ^ (i & 0x10 ? 0x0870 : 0) ^ \
 118         (i & 0x08 ? 0x0438 : 0) ^ (i & 0x04 ? 0x021c : 0) ^ \
 119         (i & 0x02 ? 0x010e : 0) ^ (i & 0x01 ? 0x0087 : 0) \
 120 )
 121
 122 #define xda_le(i) ( \
 123         (i & 0x80 ? 0xe100 : 0) ^ (i & 0x40 ? 0x7080 : 0) ^ \
 124         (i & 0x20 ? 0x3840 : 0) ^ (i & 0x10 ? 0x1c20 : 0) ^ \
 125         (i & 0x08 ? 0x0e10 : 0) ^ (i & 0x04 ? 0x0708 : 0) ^ \
 126         (i & 0x02 ? 0x0384 : 0) ^ (i & 0x01 ? 0x01c2 : 0) \
 127 )
 128
 129 static const u16 gf128mul_table_le[256] = gf128mul_dat(xda_le);
 130 static const u16 gf128mul_table_be[256] = gf128mul_dat(xda_be);
 131
 132 /*
 133  * The following functions multiply a field element by x^8 in
 134  * the polynomial field representation.  They use 64-bit word operations
 135  * to gain speed but compensate for machine endianness and hence work
 136  * correctly on both styles of machine.
 137  */
 138
 139 static void gf128mul_x8_lle(be128 *x)
 140 {
 141         u64 a = be64_to_cpu(x->a);
 142         u64 b = be64_to_cpu(x->b);
 143         u64 _tt = gf128mul_table_le[b & 0xff];
 144
 145         x->b = cpu_to_be64((b >> 8) | (a << 56));
 146         x->a = cpu_to_be64((a >> 8) ^ (_tt << 48));
 147 }
 148
 149 static void gf128mul_x8_bbe(be128 *x)
 150 {
 151         u64 a = be64_to_cpu(x->a);
 152         u64 b = be64_to_cpu(x->b);
 153         u64 _tt = gf128mul_table_be[a >> 56];
 154
 155         x->a = cpu_to_be64((a << 8) | (b >> 56));
 156         x->b = cpu_to_be64((b << 8) ^ _tt);
 157 }
 158
 159 void gf128mul_lle(be128 *r, const be128 *b)
 160 {
 161         be128 p[8];
 162         int i;
 163
 164         p[0] = *r;
 165         for (i = 0; i < 7; ++i)
 166                 gf128mul_x_lle(&p[i + 1], &p[i]);
 167
 168         memset(r, 0, sizeof(*r));
 169         for (i = 0;;) {
 170                 u8 ch = ((u8 *)b)[15 - i];
 171
 172                 if (ch & 0x80)
 173                         be128_xor(r, r, &p[0]);
 174                 if (ch & 0x40)
 175                         be128_xor(r, r, &p[1]);
 176                 if (ch & 0x20)
 177                         be128_xor(r, r, &p[2]);
 178                 if (ch & 0x10)
 179                         be128_xor(r, r, &p[3]);
 180                 if (ch & 0x08)
 181                         be128_xor(r, r, &p[4]);
 182                 if (ch & 0x04)
 183                         be128_xor(r, r, &p[5]);
 184                 if (ch & 0x02)
 185                         be128_xor(r, r, &p[6]);
 186                 if (ch & 0x01)
 187                         be128_xor(r, r, &p[7]);
 188
 189                 if (++i >= 16)
 190                         break;
 191
 192                 gf128mul_x8_lle(r);
 193         }
 194 }
 195 EXPORT_SYMBOL(gf128mul_lle);
 196
 197 void gf128mul_bbe(be128 *r, const be128 *b)
 198 {
 199         be128 p[8];
 200         int i;
 201
 202         p[0] = *r;
 203         for (i = 0; i < 7; ++i)
 204                 gf128mul_x_bbe(&p[i + 1], &p[i]);
 205
 206         memset(r, 0, sizeof(*r));
 207         for (i = 0;;) {
 208                 u8 ch = ((u8 *)b)[i];
 209
 210                 if (ch & 0x80)
 211                         be128_xor(r, r, &p[7]);
 212                 if (ch & 0x40)
 213                         be128_xor(r, r, &p[6]);
 214                 if (ch & 0x20)
 215                         be128_xor(r, r, &p[5]);
 216                 if (ch & 0x10)
 217                         be128_xor(r, r, &p[4]);
 218                 if (ch & 0x08)
 219                         be128_xor(r, r, &p[3]);
 220                 if (ch & 0x04)
 221                         be128_xor(r, r, &p[2]);
 222                 if (ch & 0x02)
 223                         be128_xor(r, r, &p[1]);
 224                 if (ch & 0x01)
 225                         be128_xor(r, r, &p[0]);
 226
 227                 if (++i >= 16)
 228                         break;
 229
 230                 gf128mul_x8_bbe(r);
 231         }
 232 }
 233 EXPORT_SYMBOL(gf128mul_bbe);
 234
 235 /*      This version uses 64k bytes of table space.
 236     A 16 byte buffer has to be multiplied by a 16 byte key
 237     value in GF(2^128).  If we consider a GF(2^128) value in
 238     the buffer's lowest byte, we can construct a table of
 239     the 256 16 byte values that result from the 256 values
 240     of this byte.  This requires 4096 bytes. But we also
 241     need tables for each of the 16 higher bytes in the
 242     buffer as well, which makes 64 kbytes in total.
 243 */
 244 /* additional explanation
 245  * t[0][BYTE] contains g*BYTE
 246  * t[1][BYTE] contains g*x^8*BYTE
 247  *  ..
 248  * t[15][BYTE] contains g*x^120*BYTE */
 249 struct gf128mul_64k *gf128mul_init_64k_bbe(const be128 *g)
 250 {
 251         struct gf128mul_64k *t;
 252         int i, j, k;
 253
 254         t = kzalloc(sizeof(*t), GFP_KERNEL);
 255         if (!t)
 256                 goto out;
 257
 258         for (i = 0; i < 16; i++) {
 259                 t->t[i] = kzalloc(sizeof(*t->t[i]), GFP_KERNEL);
 260                 if (!t->t[i]) {
 261                         gf128mul_free_64k(t);
 262                         t = NULL;
 263                         goto out;
 264                 }
 265         }
 266
 267         t->t[0]->t[1] = *g;
 268         for (j = 1; j <= 64; j <<= 1)
 269                 gf128mul_x_bbe(&t->t[0]->t[j + j], &t->t[0]->t[j]);
 270
 271         for (i = 0;;) {
 272                 for (j = 2; j < 256; j += j)
 273                         for (k = 1; k < j; ++k)
 274                                 be128_xor(&t->t[i]->t[j + k],
 275                                           &t->t[i]->t[j], &t->t[i]->t[k]);
 276
 277                 if (++i >= 16)
 278                         break;
 279
 280                 for (j = 128; j > 0; j >>= 1) {
 281                         t->t[i]->t[j] = t->t[i - 1]->t[j];
 282                         gf128mul_x8_bbe(&t->t[i]->t[j]);
 283                 }
 284         }
 285
 286 out:
 287         return t;
 288 }
 289 EXPORT_SYMBOL(gf128mul_init_64k_bbe);
 290
 291 void gf128mul_free_64k(struct gf128mul_64k *t)
 292 {
 293         int i;
 294
 295         for (i = 0; i < 16; i++)
 296                 kzfree(t->t[i]);
 297         kzfree(t);
 298 }
 299 EXPORT_SYMBOL(gf128mul_free_64k);
 300
 301 void gf128mul_64k_bbe(be128 *a, const struct gf128mul_64k *t)
 302 {
 303         u8 *ap = (u8 *)a;
 304         be128 r[1];
 305         int i;
 306
 307         *r = t->t[0]->t[ap[15]];
 308         for (i = 1; i < 16; ++i)
 309                 be128_xor(r, r, &t->t[i]->t[ap[15 - i]]);
 310         *a = *r;
 311 }
 312 EXPORT_SYMBOL(gf128mul_64k_bbe);
 313
 314 /*      This version uses 4k bytes of table space.
 315     A 16 byte buffer has to be multiplied by a 16 byte key
 316     value in GF(2^128).  If we consider a GF(2^128) value in a
 317     single byte, we can construct a table of the 256 16 byte
 318     values that result from the 256 values of this byte.
 319     This requires 4096 bytes. If we take the highest byte in
 320     the buffer and use this table to get the result, we then
 321     have to multiply by x^120 to get the final value. For the
 322     next highest byte the result has to be multiplied by x^112
 323     and so on. But we can do this by accumulating the result
 324     in an accumulator starting with the result for the top
 325     byte.  We repeatedly multiply the accumulator value by
 326     x^8 and then add in (i.e. xor) the 16 bytes of the next
 327     lower byte in the buffer, stopping when we reach the
 328     lowest byte. This requires a 4096 byte table.
 329 */
 330 struct gf128mul_4k *gf128mul_init_4k_lle(const be128 *g)
 331 {
 332         struct gf128mul_4k *t;
 333         int j, k;
 334
 335         t = kzalloc(sizeof(*t), GFP_KERNEL);
 336         if (!t)
 337                 goto out;
 338
 339         t->t[128] = *g;
 340         for (j = 64; j > 0; j >>= 1)
 341                 gf128mul_x_lle(&t->t[j], &t->t[j+j]);
 342
 343         for (j = 2; j < 256; j += j)
 344                 for (k = 1; k < j; ++k)
 345                         be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
 346
 347 out:
 348         return t;
 349 }
 350 EXPORT_SYMBOL(gf128mul_init_4k_lle);
 351
 352 struct gf128mul_4k *gf128mul_init_4k_bbe(const be128 *g)
 353 {
 354         struct gf128mul_4k *t;
 355         int j, k;
 356
 357         t = kzalloc(sizeof(*t), GFP_KERNEL);
 358         if (!t)
 359                 goto out;
 360
 361         t->t[1] = *g;
 362         for (j = 1; j <= 64; j <<= 1)
 363                 gf128mul_x_bbe(&t->t[j + j], &t->t[j]);
 364
 365         for (j = 2; j < 256; j += j)
 366                 for (k = 1; k < j; ++k)
 367                         be128_xor(&t->t[j + k], &t->t[j], &t->t[k]);
 368
 369 out:
 370         return t;
 371 }
 372 EXPORT_SYMBOL(gf128mul_init_4k_bbe);
 373
 374 void gf128mul_4k_lle(be128 *a, const struct gf128mul_4k *t)
 375 {
 376         u8 *ap = (u8 *)a;
 377         be128 r[1];
 378         int i = 15;
 379
 380         *r = t->t[ap[15]];
 381         while (i--) {
 382                 gf128mul_x8_lle(r);
 383                 be128_xor(r, r, &t->t[ap[i]]);
 384         }
 385         *a = *r;
 386 }
 387 EXPORT_SYMBOL(gf128mul_4k_lle);
 388
 389 void gf128mul_4k_bbe(be128 *a, const struct gf128mul_4k *t)
 390 {
 391         u8 *ap = (u8 *)a;
 392         be128 r[1];
 393         int i = 0;
 394
 395         *r = t->t[ap[0]];
 396         while (++i < 16) {
 397                 gf128mul_x8_bbe(r);
 398                 be128_xor(r, r, &t->t[ap[i]]);
 399         }
 400         *a = *r;
 401 }
 402 EXPORT_SYMBOL(gf128mul_4k_bbe);
 403
 404 MODULE_LICENSE("GPL");
 405 MODULE_DESCRIPTION("Functions for multiplying elements of GF(2^128)");