0cc8218a264d5b0434c3bb68fbd2e5c3bd6207db
[akaros.git] / kern / lib / random / rijndael.c
1 /*      $OpenBSD: rijndael.c,v 1.6 2000/12/09 18:51:34 markus Exp $ */
2
3 /* contrib/pgcrypto/rijndael.c */
4
5 /* This is an independent implementation of the encryption algorithm:   */
6 /*                                                                                                                                              */
7 /*                 RIJNDAEL by Joan Daemen and Vincent Rijmen                                   */
8 /*                                                                                                                                              */
9 /* which is a candidate algorithm in the Advanced Encryption Standard   */
10 /* programme of the US National Institute of Standards and Technology.  */
11 /*                                                                                                                                              */
12 /* Copyright in this implementation is held by Dr B R Gladman but I             */
13 /* hereby give permission for its free direct or derivative use subject */
14 /* to acknowledgment of its origin and compliance with any conditions   */
15 /* that the originators of the algorithm place on its exploitation.             */
16 /*                                                                                                                                              */
17 /* Dr Brian Gladman (gladman@seven77.demon.co.uk) 14th January 1999             */
18
19 /* Timing data for Rijndael (rijndael.c)
20
21 Algorithm: rijndael (rijndael.c)
22
23 128 bit key:
24 Key Setup:        305/1389 cycles (encrypt/decrypt)
25 Encrypt:           374 cycles =    68.4 mbits/sec
26 Decrypt:           352 cycles =    72.7 mbits/sec
27 Mean:              363 cycles =    70.5 mbits/sec
28
29 192 bit key:
30 Key Setup:        277/1595 cycles (encrypt/decrypt)
31 Encrypt:           439 cycles =    58.3 mbits/sec
32 Decrypt:           425 cycles =    60.2 mbits/sec
33 Mean:              432 cycles =    59.3 mbits/sec
34
35 256 bit key:
36 Key Setup:        374/1960 cycles (encrypt/decrypt)
37 Encrypt:           502 cycles =    51.0 mbits/sec
38 Decrypt:           498 cycles =    51.4 mbits/sec
39 Mean:              500 cycles =    51.2 mbits/sec
40
41 */
42 #include <u.h>
43 #include <libc.h>
44
45 #include "rijndael.h"
46
47 #include "rijndael.tbl"
48
49 /* 3. Basic macros for speeding up generic operations                           */
50
51 /* Circular rotate of 32 bit values                                                                     */
52
53 #define rotr(x,n)       (((x) >> ((int)(n))) | ((x) << (32 - (int)(n))))
54 #define rotl(x,n)       (((x) << ((int)(n))) | ((x) >> (32 - (int)(n))))
55
56 /* Invert byte order in a 32 bit variable                                                       */
57
58 #define bswap(x)        ((rotl((x), 8) & 0x00ff00ff) | (rotr((x), 8) & 0xff00ff00))
59
60 /* Extract byte from a 32 bit quantity (little endian notation)         */
61
62 #define byte(x,n)       ((uint8_t)((x) >> (8 * (n))))
63
64 #define io_swap(x)      (x)
65
66 #define ff_mult(a,b)    ((a) && (b) ? pow_tab[(log_tab[a] + log_tab[b]) % 255] : 0)
67
68 #define f_rn(bo, bi, n, k)                                                              \
69         (bo)[n] =  ft_tab[0][byte((bi)[n],0)] ^                         \
70                          ft_tab[1][byte((bi)[((n) + 1) & 3],1)] ^       \
71                          ft_tab[2][byte((bi)[((n) + 2) & 3],2)] ^       \
72                          ft_tab[3][byte((bi)[((n) + 3) & 3],3)] ^ *((k) + (n))
73
74 #define i_rn(bo, bi, n, k)                                                      \
75         (bo)[n] =  it_tab[0][byte((bi)[n],0)] ^                         \
76                          it_tab[1][byte((bi)[((n) + 3) & 3],1)] ^       \
77                          it_tab[2][byte((bi)[((n) + 2) & 3],2)] ^       \
78                          it_tab[3][byte((bi)[((n) + 1) & 3],3)] ^ *((k) + (n))
79
80 #define ls_box(x)                                \
81         ( fl_tab[0][byte(x, 0)] ^        \
82           fl_tab[1][byte(x, 1)] ^        \
83           fl_tab[2][byte(x, 2)] ^        \
84           fl_tab[3][byte(x, 3)] )
85
86 #define f_rl(bo, bi, n, k)                                                              \
87         (bo)[n] =  fl_tab[0][byte((bi)[n],0)] ^                         \
88                          fl_tab[1][byte((bi)[((n) + 1) & 3],1)] ^       \
89                          fl_tab[2][byte((bi)[((n) + 2) & 3],2)] ^       \
90                          fl_tab[3][byte((bi)[((n) + 3) & 3],3)] ^ *((k) + (n))
91
92 #define i_rl(bo, bi, n, k)                                                              \
93         (bo)[n] =  il_tab[0][byte((bi)[n],0)] ^                         \
94                          il_tab[1][byte((bi)[((n) + 3) & 3],1)] ^       \
95                          il_tab[2][byte((bi)[((n) + 2) & 3],2)] ^       \
96                          il_tab[3][byte((bi)[((n) + 1) & 3],3)] ^ *((k) + (n))
97
98 #define star_x(x) (((x) & 0x7f7f7f7f) << 1) ^ ((((x) & 0x80808080) >> 7) * 0x1b)
99
100 #define imix_col(y,x)           \
101 do { \
102         u       = star_x(x);            \
103         v       = star_x(u);            \
104         w       = star_x(v);            \
105         t       = w ^ (x);                      \
106    (y)  = u ^ v ^ w;            \
107    (y) ^= rotr(u ^ t,  8) ^ \
108                   rotr(v ^ t, 16) ^ \
109                   rotr(t,24);           \
110 } while (0)
111
112 /* initialise the key schedule from the user supplied key       */
113
114 #define loop4(i)                                                                        \
115 do {   t = ls_box(rotr(t,  8)) ^ rco_tab[i];               \
116         t ^= e_key[4 * i];         e_key[4 * i + 4] = t;        \
117         t ^= e_key[4 * i + 1]; e_key[4 * i + 5] = t;    \
118         t ^= e_key[4 * i + 2]; e_key[4 * i + 6] = t;    \
119         t ^= e_key[4 * i + 3]; e_key[4 * i + 7] = t;    \
120 } while (0)
121
122 #define loop6(i)                                                                        \
123 do {   t = ls_box(rotr(t,  8)) ^ rco_tab[i];               \
124         t ^= e_key[6 * (i)];       e_key[6 * (i) + 6] = t;      \
125         t ^= e_key[6 * (i) + 1]; e_key[6 * (i) + 7] = t;        \
126         t ^= e_key[6 * (i) + 2]; e_key[6 * (i) + 8] = t;        \
127         t ^= e_key[6 * (i) + 3]; e_key[6 * (i) + 9] = t;        \
128         t ^= e_key[6 * (i) + 4]; e_key[6 * (i) + 10] = t;       \
129         t ^= e_key[6 * (i) + 5]; e_key[6 * (i) + 11] = t;       \
130 } while (0)
131
132 #define loop8(i)                                                                        \
133 do {   t = ls_box(rotr(t,  8)) ^ rco_tab[i];               \
134         t ^= e_key[8 * (i)];     e_key[8 * (i) + 8] = t;        \
135         t ^= e_key[8 * (i) + 1]; e_key[8 * (i) + 9] = t;        \
136         t ^= e_key[8 * (i) + 2]; e_key[8 * (i) + 10] = t;       \
137         t ^= e_key[8 * (i) + 3]; e_key[8 * (i) + 11] = t;       \
138         t  = e_key[8 * (i) + 4] ^ ls_box(t);                            \
139         e_key[8 * (i) + 12] = t;                                                        \
140         t ^= e_key[8 * (i) + 5]; e_key[8 * (i) + 13] = t;       \
141         t ^= e_key[8 * (i) + 6]; e_key[8 * (i) + 14] = t;       \
142         t ^= e_key[8 * (i) + 7]; e_key[8 * (i) + 15] = t;       \
143 } while (0)
144
145 rijndaelCtx *
146 rijndael_set_key(rijndaelCtx *ctx, const uint32_t *in_key, const uint32_t key_len,
147                                  int encrypt)
148 {
149         uint32_t                i,
150                                 t,
151                                 u,
152                                 v,
153                                 w;
154         uint32_t           *e_key = ctx->e_key;
155         uint32_t           *d_key = ctx->d_key;
156
157         ctx->decrypt = !encrypt;
158
159         ctx->k_len = (key_len + 31) / 32;
160
161         e_key[0] = io_swap(in_key[0]);
162         e_key[1] = io_swap(in_key[1]);
163         e_key[2] = io_swap(in_key[2]);
164         e_key[3] = io_swap(in_key[3]);
165
166         switch (ctx->k_len)
167         {
168                 case 4:
169                         t = e_key[3];
170                         for (i = 0; i < 10; ++i)
171                                 loop4(i);
172                         break;
173
174                 case 6:
175                         e_key[4] = io_swap(in_key[4]);
176                         t = e_key[5] = io_swap(in_key[5]);
177                         for (i = 0; i < 8; ++i)
178                                 loop6(i);
179                         break;
180
181                 case 8:
182                         e_key[4] = io_swap(in_key[4]);
183                         e_key[5] = io_swap(in_key[5]);
184                         e_key[6] = io_swap(in_key[6]);
185                         t = e_key[7] = io_swap(in_key[7]);
186                         for (i = 0; i < 7; ++i)
187                                 loop8(i);
188                         break;
189         }
190
191         if (!encrypt)
192         {
193                 d_key[0] = e_key[0];
194                 d_key[1] = e_key[1];
195                 d_key[2] = e_key[2];
196                 d_key[3] = e_key[3];
197
198                 for (i = 4; i < 4 * ctx->k_len + 24; ++i)
199                         imix_col(d_key[i], e_key[i]);
200         }
201
202         return ctx;
203 }
204
205 /* encrypt a block of text      */
206
207 #define f_nround(bo, bi, k) \
208 do { \
209         f_rn(bo, bi, 0, k);             \
210         f_rn(bo, bi, 1, k);             \
211         f_rn(bo, bi, 2, k);             \
212         f_rn(bo, bi, 3, k);             \
213         k += 4;                                 \
214 } while (0)
215
216 #define f_lround(bo, bi, k) \
217 do { \
218         f_rl(bo, bi, 0, k);             \
219         f_rl(bo, bi, 1, k);             \
220         f_rl(bo, bi, 2, k);             \
221         f_rl(bo, bi, 3, k);             \
222 } while (0)
223
224 void
225 rijndael_encrypt(rijndaelCtx *ctx, const uint32_t *in_blk, uint32_t *out_blk)
226 {
227         uint32_t                k_len = ctx->k_len;
228         uint32_t           *e_key = ctx->e_key;
229         uint32_t                b0[4],
230                                 b1[4],
231                            *kp;
232
233         b0[0] = io_swap(in_blk[0]) ^ e_key[0];
234         b0[1] = io_swap(in_blk[1]) ^ e_key[1];
235         b0[2] = io_swap(in_blk[2]) ^ e_key[2];
236         b0[3] = io_swap(in_blk[3]) ^ e_key[3];
237
238         kp = e_key + 4;
239
240         if (k_len > 6)
241         {
242                 f_nround(b1, b0, kp);
243                 f_nround(b0, b1, kp);
244         }
245
246         if (k_len > 4)
247         {
248                 f_nround(b1, b0, kp);
249                 f_nround(b0, b1, kp);
250         }
251
252         f_nround(b1, b0, kp);
253         f_nround(b0, b1, kp);
254         f_nround(b1, b0, kp);
255         f_nround(b0, b1, kp);
256         f_nround(b1, b0, kp);
257         f_nround(b0, b1, kp);
258         f_nround(b1, b0, kp);
259         f_nround(b0, b1, kp);
260         f_nround(b1, b0, kp);
261         f_lround(b0, b1, kp);
262
263         out_blk[0] = io_swap(b0[0]);
264         out_blk[1] = io_swap(b0[1]);
265         out_blk[2] = io_swap(b0[2]);
266         out_blk[3] = io_swap(b0[3]);
267 }
268
269 /* decrypt a block of text      */
270
271 #define i_nround(bo, bi, k) \
272 do { \
273         i_rn(bo, bi, 0, k);             \
274         i_rn(bo, bi, 1, k);             \
275         i_rn(bo, bi, 2, k);             \
276         i_rn(bo, bi, 3, k);             \
277         k -= 4;                                 \
278 } while (0)
279
280 #define i_lround(bo, bi, k) \
281 do { \
282         i_rl(bo, bi, 0, k);             \
283         i_rl(bo, bi, 1, k);             \
284         i_rl(bo, bi, 2, k);             \
285         i_rl(bo, bi, 3, k);             \
286 } while (0)
287
288 void
289 rijndael_decrypt(rijndaelCtx *ctx, const uint32_t *in_blk, uint32_t *out_blk)
290 {
291         uint32_t                b0[4],
292                                 b1[4],
293                            *kp;
294         uint32_t                k_len = ctx->k_len;
295         uint32_t           *e_key = ctx->e_key;
296         uint32_t           *d_key = ctx->d_key;
297
298         b0[0] = io_swap(in_blk[0]) ^ e_key[4 * k_len + 24];
299         b0[1] = io_swap(in_blk[1]) ^ e_key[4 * k_len + 25];
300         b0[2] = io_swap(in_blk[2]) ^ e_key[4 * k_len + 26];
301         b0[3] = io_swap(in_blk[3]) ^ e_key[4 * k_len + 27];
302
303         kp = d_key + 4 * (k_len + 5);
304
305         if (k_len > 6)
306         {
307                 i_nround(b1, b0, kp);
308                 i_nround(b0, b1, kp);
309         }
310
311         if (k_len > 4)
312         {
313                 i_nround(b1, b0, kp);
314                 i_nround(b0, b1, kp);
315         }
316
317         i_nround(b1, b0, kp);
318         i_nround(b0, b1, kp);
319         i_nround(b1, b0, kp);
320         i_nround(b0, b1, kp);
321         i_nround(b1, b0, kp);
322         i_nround(b0, b1, kp);
323         i_nround(b1, b0, kp);
324         i_nround(b0, b1, kp);
325         i_nround(b1, b0, kp);
326         i_lround(b0, b1, kp);
327
328         out_blk[0] = io_swap(b0[0]);
329         out_blk[1] = io_swap(b0[1]);
330         out_blk[2] = io_swap(b0[2]);
331         out_blk[3] = io_swap(b0[3]);
332 }
333
334 /*
335  * conventional interface
336  *
337  * ATM it hopes all data is 4-byte aligned - which
338  * should be true for PX.  -marko
339  */
340
341 void
342 aes_set_key(rijndaelCtx *ctx, const uint8_t *key, unsigned keybits, int enc)
343 {
344         uint32_t           *k;
345
346         k = (uint32_t *) key;
347         rijndael_set_key(ctx, k, keybits, enc);
348 }
349
350 void
351 aes_ecb_encrypt(rijndaelCtx *ctx, uint8_t *data, unsigned len)
352 {
353         unsigned        bs = 16;
354         uint32_t           *d;
355
356         while (len >= bs)
357         {
358                 d = (uint32_t *) data;
359                 rijndael_encrypt(ctx, d, d);
360
361                 len -= bs;
362                 data += bs;
363         }
364 }
365
366 void
367 aes_ecb_decrypt(rijndaelCtx *ctx, uint8_t *data, unsigned len)
368 {
369         unsigned        bs = 16;
370         uint32_t           *d;
371
372         while (len >= bs)
373         {
374                 d = (uint32_t *) data;
375                 rijndael_decrypt(ctx, d, d);
376
377                 len -= bs;
378                 data += bs;
379         }
380 }
381
382 void
383 aes_cbc_encrypt(rijndaelCtx *ctx, uint8_t *iva, uint8_t *data, unsigned len)
384 {
385         uint32_t           *iv = (uint32_t *) iva;
386         uint32_t           *d = (uint32_t *) data;
387         unsigned        bs = 16;
388
389         while (len >= bs)
390         {
391                 d[0] ^= iv[0];
392                 d[1] ^= iv[1];
393                 d[2] ^= iv[2];
394                 d[3] ^= iv[3];
395
396                 rijndael_encrypt(ctx, d, d);
397
398                 iv = d;
399                 d += bs / 4;
400                 len -= bs;
401         }
402 }
403
404 void
405 aes_cbc_decrypt(rijndaelCtx *ctx, uint8_t *iva, uint8_t *data, unsigned len)
406 {
407         uint32_t           *d = (uint32_t *) data;
408         unsigned        bs = 16;
409         uint32_t                buf[4],
410                                 iv[4];
411
412         memcpy(iv, iva, bs);
413         while (len >= bs)
414         {
415                 buf[0] = d[0];
416                 buf[1] = d[1];
417                 buf[2] = d[2];
418                 buf[3] = d[3];
419
420                 rijndael_decrypt(ctx, buf, d);
421
422                 d[0] ^= iv[0];
423                 d[1] ^= iv[1];
424                 d[2] ^= iv[2];
425                 d[3] ^= iv[3];
426
427                 iv[0] = buf[0];
428                 iv[1] = buf[1];
429                 iv[2] = buf[2];
430                 iv[3] = buf[3];
431                 d += 4;
432                 len -= bs;
433         }
434 }