lib/silccrypt/rijndael.c

   1 /* Modified for SILC. -Pekka */
   2
   3 /* This is an independent implementation of the encryption algorithm:   */
   4 /*                                                                      */
   5 /*         RIJNDAEL by Joan Daemen and Vincent Rijmen                   */
   6 /*                                                                      */
   7 /* which is a candidate algorithm in the Advanced Encryption Standard   */
   8 /* programme of the US National Institute of Standards and Technology.  */
   9 /*                                                                      */
  10 /* Copyright in this implementation is held by Dr B R Gladman but I     */
  11 /* hereby give permission for its free direct or derivative use subject */
  12 /* to acknowledgment of its origin and compliance with any conditions   */
  13 /* that the originators of the algorithm place on its exploitation.     */
  14 /*                                                                      */
  15 /* Dr Brian Gladman (gladman@seven77.demon.co.uk) 14th January 1999     */
  16
  17 /* Timing data for Rijndael (rijndael.c)
  18
  19 Algorithm: rijndael (rijndael.c)
  20
  21 128 bit key:
  22 Key Setup:    305/1389 cycles (encrypt/decrypt)
  23 Encrypt:       374 cycles =    68.4 mbits/sec
  24 Decrypt:       352 cycles =    72.7 mbits/sec
  25 Mean:          363 cycles =    70.5 mbits/sec
  26
  27 192 bit key:
  28 Key Setup:    277/1595 cycles (encrypt/decrypt)
  29 Encrypt:       439 cycles =    58.3 mbits/sec
  30 Decrypt:       425 cycles =    60.2 mbits/sec
  31 Mean:          432 cycles =    59.3 mbits/sec
  32
  33 256 bit key:
  34 Key Setup:    374/1960 cycles (encrypt/decrypt)
  35 Encrypt:       502 cycles =    51.0 mbits/sec
  36 Decrypt:       498 cycles =    51.4 mbits/sec
  37 Mean:          500 cycles =    51.2 mbits/sec
  38
  39 */
  40
  41 #include "silcincludes.h"
  42 #include "rijndael.h"
  43
  44 #define LARGE_TABLES
  45
  46 u1byte  pow_tab[256];
  47 u1byte  log_tab[256];
  48 u1byte  sbx_tab[256];
  49 u1byte  isb_tab[256];
  50 u4byte  rco_tab[ 10];
  51 u4byte  ft_tab[4][256];
  52 u4byte  it_tab[4][256];
  53
  54 u4byte  fl_tab[4][256];
  55 u4byte  il_tab[4][256];
  56
  57 u4byte  tab_gen = 0;
  58
  59 #define ff_mult(a,b)    (a && b ? pow_tab[(log_tab[a] + log_tab[b]) % 255] : 0)
  60
  61 #define f_rn(bo, bi, n, k)                          \
  62     bo[n] =  ft_tab[0][byte(bi[n],0)] ^             \
  63              ft_tab[1][byte(bi[(n + 1) & 3],1)] ^   \
  64              ft_tab[2][byte(bi[(n + 2) & 3],2)] ^   \
  65              ft_tab[3][byte(bi[(n + 3) & 3],3)] ^ *(k + n)
  66
  67 #define i_rn(bo, bi, n, k)                          \
  68     bo[n] =  it_tab[0][byte(bi[n],0)] ^             \
  69              it_tab[1][byte(bi[(n + 3) & 3],1)] ^   \
  70              it_tab[2][byte(bi[(n + 2) & 3],2)] ^   \
  71              it_tab[3][byte(bi[(n + 1) & 3],3)] ^ *(k + n)
  72
  73 #ifdef LARGE_TABLES
  74
  75 #define ls_box(x)                \
  76     ( fl_tab[0][byte(x, 0)] ^    \
  77       fl_tab[1][byte(x, 1)] ^    \
  78       fl_tab[2][byte(x, 2)] ^    \
  79       fl_tab[3][byte(x, 3)] )
  80
  81 #define f_rl(bo, bi, n, k)                          \
  82     bo[n] =  fl_tab[0][byte(bi[n],0)] ^             \
  83              fl_tab[1][byte(bi[(n + 1) & 3],1)] ^   \
  84              fl_tab[2][byte(bi[(n + 2) & 3],2)] ^   \
  85              fl_tab[3][byte(bi[(n + 3) & 3],3)] ^ *(k + n)
  86
  87 #define i_rl(bo, bi, n, k)                          \
  88     bo[n] =  il_tab[0][byte(bi[n],0)] ^             \
  89              il_tab[1][byte(bi[(n + 3) & 3],1)] ^   \
  90              il_tab[2][byte(bi[(n + 2) & 3],2)] ^   \
  91              il_tab[3][byte(bi[(n + 1) & 3],3)] ^ *(k + n)
  92
  93 #else
  94
  95 #define ls_box(x)                            \
  96     ((u4byte)sbx_tab[byte(x, 0)] <<  0) ^    \
  97     ((u4byte)sbx_tab[byte(x, 1)] <<  8) ^    \
  98     ((u4byte)sbx_tab[byte(x, 2)] << 16) ^    \
  99     ((u4byte)sbx_tab[byte(x, 3)] << 24)
 100
 101 #define f_rl(bo, bi, n, k)                                      \
 102     bo[n] = (u4byte)sbx_tab[byte(bi[n],0)] ^                    \
 103         rotl(((u4byte)sbx_tab[byte(bi[(n + 1) & 3],1)]),  8) ^  \
 104         rotl(((u4byte)sbx_tab[byte(bi[(n + 2) & 3],2)]), 16) ^  \
 105         rotl(((u4byte)sbx_tab[byte(bi[(n + 3) & 3],3)]), 24) ^ *(k + n)
 106
 107 #define i_rl(bo, bi, n, k)                                      \
 108     bo[n] = (u4byte)isb_tab[byte(bi[n],0)] ^                    \
 109         rotl(((u4byte)isb_tab[byte(bi[(n + 3) & 3],1)]),  8) ^  \
 110         rotl(((u4byte)isb_tab[byte(bi[(n + 2) & 3],2)]), 16) ^  \
 111         rotl(((u4byte)isb_tab[byte(bi[(n + 1) & 3],3)]), 24) ^ *(k + n)
 112
 113 #endif
 114
 115 void gen_tabs(void)
 116 {   u4byte  i, t;
 117     u1byte  p, q;
 118
 119     /* log and power tables for GF(2**8) finite field with  */
 120     /* 0x11b as modular polynomial - the simplest prmitive  */
 121     /* root is 0x11, used here to generate the tables       */
 122
 123     for(i = 0,p = 1; i < 256; ++i)
 124     {
 125         pow_tab[i] = (u1byte)p; log_tab[p] = (u1byte)i;
 126
 127         p = p ^ (p << 1) ^ (p & 0x80 ? 0x01b : 0);
 128     }
 129
 130     log_tab[1] = 0; p = 1;
 131
 132     for(i = 0; i < 10; ++i)
 133     {
 134         rco_tab[i] = p;
 135
 136         p = (p << 1) ^ (p & 0x80 ? 0x1b : 0);
 137     }
 138
 139     /* note that the affine byte transformation matrix in   */
 140     /* rijndael specification is in big endian format with  */
 141     /* bit 0 as the most significant bit. In the remainder  */
 142     /* of the specification the bits are numbered from the  */
 143     /* least significant end of a byte.                     */
 144
 145     for(i = 0; i < 256; ++i)
 146     {
 147         p = (i ? pow_tab[255 - log_tab[i]] : 0); q = p;
 148         q = (q >> 7) | (q << 1); p ^= q;
 149         q = (q >> 7) | (q << 1); p ^= q;
 150         q = (q >> 7) | (q << 1); p ^= q;
 151         q = (q >> 7) | (q << 1); p ^= q ^ 0x63;
 152         sbx_tab[i] = (u1byte)p; isb_tab[p] = (u1byte)i;
 153     }
 154
 155     for(i = 0; i < 256; ++i)
 156     {
 157         p = sbx_tab[i];
 158
 159 #ifdef  LARGE_TABLES
 160
 161         t = p; fl_tab[0][i] = t;
 162         fl_tab[1][i] = rotl(t,  8);
 163         fl_tab[2][i] = rotl(t, 16);
 164         fl_tab[3][i] = rotl(t, 24);
 165 #endif
 166         t = ((u4byte)ff_mult(2, p)) |
 167             ((u4byte)p <<  8) |
 168             ((u4byte)p << 16) |
 169             ((u4byte)ff_mult(3, p) << 24);
 170
 171         ft_tab[0][i] = t;
 172         ft_tab[1][i] = rotl(t,  8);
 173         ft_tab[2][i] = rotl(t, 16);
 174         ft_tab[3][i] = rotl(t, 24);
 175
 176         p = isb_tab[i];
 177
 178 #ifdef  LARGE_TABLES
 179
 180         t = p; il_tab[0][i] = t;
 181         il_tab[1][i] = rotl(t,  8);
 182         il_tab[2][i] = rotl(t, 16);
 183         il_tab[3][i] = rotl(t, 24);
 184 #endif
 185         t = ((u4byte)ff_mult(14, p)) |
 186             ((u4byte)ff_mult( 9, p) <<  8) |
 187             ((u4byte)ff_mult(13, p) << 16) |
 188             ((u4byte)ff_mult(11, p) << 24);
 189
 190         it_tab[0][i] = t;
 191         it_tab[1][i] = rotl(t,  8);
 192         it_tab[2][i] = rotl(t, 16);
 193         it_tab[3][i] = rotl(t, 24);
 194     }
 195
 196     tab_gen = 1;
 197 };
 198
 199 #define star_x(x) (((x) & 0x7f7f7f7f) << 1) ^ ((((x) & 0x80808080) >> 7) * 0x1b)
 200
 201 #define imix_col(y,x)       \
 202     u   = star_x(x);        \
 203     v   = star_x(u);        \
 204     w   = star_x(v);        \
 205     t   = w ^ (x);          \
 206    (y)  = u ^ v ^ w;        \
 207    (y) ^= rotr(u ^ t,  8) ^ \
 208           rotr(v ^ t, 16) ^ \
 209           rotr(t,24)
 210
 211 /* initialise the key schedule from the user supplied key   */
 212
 213 #define loop4(i)                                    \
 214 { \
 215    t = ls_box(rotr(t,  8)) ^ rco_tab[i];           \
 216     t ^= e_key[4 * i];     e_key[4 * i + 4] = t;    \
 217     t ^= e_key[4 * i + 1]; e_key[4 * i + 5] = t;    \
 218     t ^= e_key[4 * i + 2]; e_key[4 * i + 6] = t;    \
 219     t ^= e_key[4 * i + 3]; e_key[4 * i + 7] = t;    \
 220 }
 221
 222 #define loop6(i)                                    \
 223 {   t = ls_box(rotr(t,  8)) ^ rco_tab[i];           \
 224     t ^= e_key[6 * i];     e_key[6 * i + 6] = t;    \
 225     t ^= e_key[6 * i + 1]; e_key[6 * i + 7] = t;    \
 226     t ^= e_key[6 * i + 2]; e_key[6 * i + 8] = t;    \
 227     t ^= e_key[6 * i + 3]; e_key[6 * i + 9] = t;    \
 228     t ^= e_key[6 * i + 4]; e_key[6 * i + 10] = t;   \
 229     t ^= e_key[6 * i + 5]; e_key[6 * i + 11] = t;   \
 230 }
 231
 232 #define loop8(i)                                    \
 233 {   t = ls_box(rotr(t,  8)) ^ rco_tab[i];           \
 234     t ^= e_key[8 * i];     e_key[8 * i + 8] = t;    \
 235     t ^= e_key[8 * i + 1]; e_key[8 * i + 9] = t;    \
 236     t ^= e_key[8 * i + 2]; e_key[8 * i + 10] = t;   \
 237     t ^= e_key[8 * i + 3]; e_key[8 * i + 11] = t;   \
 238     t  = e_key[8 * i + 4] ^ ls_box(t);              \
 239     e_key[8 * i + 12] = t;                          \
 240     t ^= e_key[8 * i + 5]; e_key[8 * i + 13] = t;   \
 241     t ^= e_key[8 * i + 6]; e_key[8 * i + 14] = t;   \
 242     t ^= e_key[8 * i + 7]; e_key[8 * i + 15] = t;   \
 243 }
 244
 245 u4byte *rijndael_set_key(RijndaelContext *ctx,
 246                          const u4byte in_key[], const u4byte key_len)
 247 {
 248     u4byte  i, t, u, v, w;
 249     u4byte *e_key = ctx->e_key;
 250     u4byte *d_key = ctx->d_key;
 251     u4byte k_len;
 252
 253     if(!tab_gen)
 254         gen_tabs();
 255
 256     k_len = ctx->k_len = (key_len + 31) / 32;
 257
 258     e_key[0] = in_key[0]; e_key[1] = in_key[1];
 259     e_key[2] = in_key[2]; e_key[3] = in_key[3];
 260
 261     switch(k_len)
 262     {
 263         case 4: t = e_key[3];
 264                 for(i = 0; i < 10; ++i)
 265                     loop4(i);
 266                 break;
 267
 268         case 6: e_key[4] = in_key[4]; t = e_key[5] = in_key[5];
 269                 for(i = 0; i < 8; ++i)
 270                     loop6(i);
 271                 break;
 272
 273         case 8: e_key[4] = in_key[4]; e_key[5] = in_key[5];
 274                 e_key[6] = in_key[6]; t = e_key[7] = in_key[7];
 275                 for(i = 0; i < 7; ++i)
 276                     loop8(i);
 277                 break;
 278     }
 279
 280     d_key[0] = e_key[0]; d_key[1] = e_key[1];
 281     d_key[2] = e_key[2]; d_key[3] = e_key[3];
 282
 283     for(i = 4; i < 4 * k_len + 24; ++i)
 284     {
 285         imix_col(d_key[i], e_key[i]);
 286     }
 287
 288     return e_key;
 289 };
 290
 291 /* encrypt a block of text  */
 292
 293 #define f_nround(bo, bi, k) \
 294     f_rn(bo, bi, 0, k);     \
 295     f_rn(bo, bi, 1, k);     \
 296     f_rn(bo, bi, 2, k);     \
 297     f_rn(bo, bi, 3, k);     \
 298     k += 4
 299
 300 #define f_lround(bo, bi, k) \
 301     f_rl(bo, bi, 0, k);     \
 302     f_rl(bo, bi, 1, k);     \
 303     f_rl(bo, bi, 2, k);     \
 304     f_rl(bo, bi, 3, k)
 305
 306 void rijndael_encrypt(RijndaelContext *ctx,
 307                       const u4byte in_blk[4], u4byte out_blk[4])
 308 {
 309     u4byte  b0[4], b1[4], *kp;
 310     u4byte *e_key = ctx->e_key;
 311     u4byte k_len = ctx->k_len;
 312
 313     b0[0] = in_blk[0] ^ e_key[0]; b0[1] = in_blk[1] ^ e_key[1];
 314     b0[2] = in_blk[2] ^ e_key[2]; b0[3] = in_blk[3] ^ e_key[3];
 315
 316     kp = e_key + 4;
 317
 318     if(k_len > 6)
 319     {
 320         f_nround(b1, b0, kp); f_nround(b0, b1, kp);
 321     }
 322
 323     if(k_len > 4)
 324     {
 325         f_nround(b1, b0, kp); f_nround(b0, b1, kp);
 326     }
 327
 328     f_nround(b1, b0, kp); f_nround(b0, b1, kp);
 329     f_nround(b1, b0, kp); f_nround(b0, b1, kp);
 330     f_nround(b1, b0, kp); f_nround(b0, b1, kp);
 331     f_nround(b1, b0, kp); f_nround(b0, b1, kp);
 332     f_nround(b1, b0, kp); f_lround(b0, b1, kp);
 333
 334     out_blk[0] = b0[0]; out_blk[1] = b0[1];
 335     out_blk[2] = b0[2]; out_blk[3] = b0[3];
 336 };
 337
 338 /* decrypt a block of text  */
 339
 340 #define i_nround(bo, bi, k) \
 341     i_rn(bo, bi, 0, k);     \
 342     i_rn(bo, bi, 1, k);     \
 343     i_rn(bo, bi, 2, k);     \
 344     i_rn(bo, bi, 3, k);     \
 345     k -= 4
 346
 347 #define i_lround(bo, bi, k) \
 348     i_rl(bo, bi, 0, k);     \
 349     i_rl(bo, bi, 1, k);     \
 350     i_rl(bo, bi, 2, k);     \
 351     i_rl(bo, bi, 3, k)
 352
 353 void rijndael_decrypt(RijndaelContext *ctx,
 354                       const u4byte in_blk[4], u4byte out_blk[4])
 355 {
 356     u4byte  b0[4], b1[4], *kp;
 357     u4byte *e_key = ctx->e_key;
 358     u4byte *d_key = ctx->d_key;
 359     u4byte k_len = ctx->k_len;
 360
 361     b0[0] = in_blk[0] ^ e_key[4 * k_len + 24]; b0[1] = in_blk[1] ^ e_key[4 * k_len + 25];
 362     b0[2] = in_blk[2] ^ e_key[4 * k_len + 26]; b0[3] = in_blk[3] ^ e_key[4 * k_len + 27];
 363
 364     kp = d_key + 4 * (k_len + 5);
 365
 366     if(k_len > 6)
 367     {
 368         i_nround(b1, b0, kp); i_nround(b0, b1, kp);
 369     }
 370
 371     if(k_len > 4)
 372     {
 373         i_nround(b1, b0, kp); i_nround(b0, b1, kp);
 374     }
 375
 376     i_nround(b1, b0, kp); i_nround(b0, b1, kp);
 377     i_nround(b1, b0, kp); i_nround(b0, b1, kp);
 378     i_nround(b1, b0, kp); i_nround(b0, b1, kp);
 379     i_nround(b1, b0, kp); i_nround(b0, b1, kp);
 380     i_nround(b1, b0, kp); i_lround(b0, b1, kp);
 381
 382     out_blk[0] = b0[0]; out_blk[1] = b0[1];
 383     out_blk[2] = b0[2]; out_blk[3] = b0[3];
 384 };