1 |
/* Rijndael Cipher |
2 |
|
3 |
Written by Mike Scott 21st April 1999 |
4 |
Copyright (c) 1999 Mike Scott |
5 |
See rijndael documentation |
6 |
|
7 |
Permission for free direct or derivative use is granted subject |
8 |
to compliance with any conditions that the originators of the |
9 |
algorithm place on its exploitation. |
10 |
|
11 |
Inspiration from Brian Gladman's implementation is acknowledged. |
12 |
|
13 |
Written for clarity, rather than speed. |
14 |
Full implementation. |
15 |
Endian indifferent. |
16 |
*/ |
17 |
|
18 |
/* $Id: rijndael.c,v 1.1.1.1 1999/10/15 22:49:23 nmav Exp $ */ |
19 |
|
20 |
#include <libdefs.h> |
21 |
#include <rijndael.h> |
22 |
|
23 |
/* rotates x one bit to the left */ |
24 |
|
25 |
#define ROTL(x) (((x)>>7)|((x)<<1)) |
26 |
|
27 |
/* Rotates 32-bit word left by 1, 2 or 3 byte */ |
28 |
|
29 |
#define ROTL8(x) (((x)<<8)|((x)>>24)) |
30 |
#define ROTL16(x) (((x)<<16)|((x)>>16)) |
31 |
#define ROTL24(x) (((x)<<24)|((x)>>8)) |
32 |
|
33 |
/* Fixed Data */ |
34 |
|
35 |
static word8 InCo[4]={0xB,0xD,0x9,0xE}; /* Inverse Coefficients */ |
36 |
|
37 |
static word8 fbsub[256]; |
38 |
static word8 rbsub[256]; |
39 |
static word8 ptab[256],ltab[256]; |
40 |
static word32 ftable[256]; |
41 |
static word32 rtable[256]; |
42 |
static word32 rco[30]; |
43 |
|
44 |
/* Parameter-dependent data */ |
45 |
|
46 |
/* in "rijndael.h" */ |
47 |
|
48 |
static word32 pack(word8 *b) |
49 |
{ /* pack bytes into a 32-bit Word */ |
50 |
return ((word32)b[3]<<24)|((word32)b[2]<<16)|((word32)b[1]<<8)|(word32)b[0]; |
51 |
} |
52 |
|
53 |
static void unpack(word32 a,word8 *b) |
54 |
{ /* unpack bytes from a word */ |
55 |
b[0]=(word8)a; |
56 |
b[1]=(word8)(a>>8); |
57 |
b[2]=(word8)(a>>16); |
58 |
b[3]=(word8)(a>>24); |
59 |
} |
60 |
|
61 |
static word8 xtime(word8 a) |
62 |
{ |
63 |
word8 b; |
64 |
if (a&0x80) b=0x1B; |
65 |
else b=0; |
66 |
a<<=1; |
67 |
a^=b; |
68 |
return a; |
69 |
} |
70 |
|
71 |
static word8 bmul(word8 x,word8 y) |
72 |
{ /* x.y= AntiLog(Log(x) + Log(y)) */ |
73 |
if (x && y) return ptab[(ltab[x]+ltab[y])%255]; |
74 |
else return 0; |
75 |
} |
76 |
|
77 |
static word32 SubByte(word32 a) |
78 |
{ |
79 |
word8 b[4]; |
80 |
unpack(a,b); |
81 |
b[0]=fbsub[b[0]]; |
82 |
b[1]=fbsub[b[1]]; |
83 |
b[2]=fbsub[b[2]]; |
84 |
b[3]=fbsub[b[3]]; |
85 |
return pack(b); |
86 |
} |
87 |
|
88 |
static word8 product(word32 x,word32 y) |
89 |
{ /* dot product of two 4-byte arrays */ |
90 |
word8 xb[4],yb[4]; |
91 |
unpack(x,xb); |
92 |
unpack(y,yb); |
93 |
return bmul(xb[0],yb[0])^bmul(xb[1],yb[1])^bmul(xb[2],yb[2])^bmul(xb[3],yb[3]); |
94 |
} |
95 |
|
96 |
static word32 InvMixCol(word32 x) |
97 |
{ /* matrix Multiplication */ |
98 |
word32 y,m; |
99 |
word8 b[4]; |
100 |
|
101 |
m=pack(InCo); |
102 |
b[3]=product(m,x); |
103 |
m=ROTL24(m); |
104 |
b[2]=product(m,x); |
105 |
m=ROTL24(m); |
106 |
b[1]=product(m,x); |
107 |
m=ROTL24(m); |
108 |
b[0]=product(m,x); |
109 |
y=pack(b); |
110 |
return y; |
111 |
} |
112 |
|
113 |
word8 ByteSub(word8 x) |
114 |
{ |
115 |
word8 y=ptab[255-ltab[x]]; /* multiplicative inverse */ |
116 |
x=y; x=ROTL(x); |
117 |
y^=x; x=ROTL(x); |
118 |
y^=x; x=ROTL(x); |
119 |
y^=x; x=ROTL(x); |
120 |
y^=x; y^=0x63; |
121 |
return y; |
122 |
} |
123 |
|
124 |
void _mcrypt_rijndael_gentables(void) |
125 |
{ /* generate tables */ |
126 |
int i; |
127 |
word8 y,b[4]; |
128 |
|
129 |
/* use 3 as primitive root to generate power and log tables */ |
130 |
|
131 |
ltab[0]=0; |
132 |
ptab[0]=1; ltab[1]=0; |
133 |
ptab[1]=3; ltab[3]=1; |
134 |
for (i=2;i<256;i++) |
135 |
{ |
136 |
ptab[i]=ptab[i-1]^xtime(ptab[i-1]); |
137 |
ltab[ptab[i]]=i; |
138 |
} |
139 |
|
140 |
/* affine transformation:- each bit is xored with itself shifted one bit */ |
141 |
|
142 |
fbsub[0]=0x63; |
143 |
rbsub[0x63]=0; |
144 |
for (i=1;i<256;i++) |
145 |
{ |
146 |
y=ByteSub((word8)i); |
147 |
fbsub[i]=y; rbsub[y]=i; |
148 |
} |
149 |
|
150 |
for (i=0,y=1;i<30;i++) |
151 |
{ |
152 |
rco[i]=y; |
153 |
y=xtime(y); |
154 |
} |
155 |
|
156 |
/* calculate forward and reverse tables */ |
157 |
for (i=0;i<256;i++) |
158 |
{ |
159 |
y=fbsub[i]; |
160 |
b[3]=y^xtime(y); b[2]=y; |
161 |
b[1]=y; b[0]=xtime(y); |
162 |
ftable[i]=pack(b); |
163 |
|
164 |
y=rbsub[i]; |
165 |
b[3]=bmul(InCo[0],y); b[2]=bmul(InCo[1],y); |
166 |
b[1]=bmul(InCo[2],y); b[0]=bmul(InCo[3],y); |
167 |
rtable[i]=pack(b); |
168 |
} |
169 |
} |
170 |
|
171 |
void _mcrypt_rijndael_set_key( RI* rinst, int nb,int nk, word8 *key) |
172 |
{ /* blocksize=32*nb bits. Key=32*nk bits */ |
173 |
/* currently nb,bk = 4, 6 or 8 */ |
174 |
/* key comes as 4*rinst->Nk bytes */ |
175 |
/* Key Scheduler. Create expanded encryption key */ |
176 |
int i,j,k,m,N; |
177 |
int C1,C2,C3; |
178 |
word32 CipherKey[8]; |
179 |
|
180 |
rinst->Nb=nb; rinst->Nk=nk; |
181 |
|
182 |
/* rinst->Nr is number of rounds */ |
183 |
if (rinst->Nb>=rinst->Nk) rinst->Nr=6+rinst->Nb; |
184 |
else rinst->Nr=6+rinst->Nk; |
185 |
|
186 |
C1=1; |
187 |
if (rinst->Nb<8) { C2=2; C3=3; } |
188 |
else { C2=3; C3=4; } |
189 |
|
190 |
/* pre-calculate forward and reverse increments */ |
191 |
for (m=j=0;j<nb;j++,m+=3) |
192 |
{ |
193 |
rinst->fi[m]=(j+C1)%nb; |
194 |
rinst->fi[m+1]=(j+C2)%nb; |
195 |
rinst->fi[m+2]=(j+C3)%nb; |
196 |
rinst->ri[m]=(nb+j-C1)%nb; |
197 |
rinst->ri[m+1]=(nb+j-C2)%nb; |
198 |
rinst->ri[m+2]=(nb+j-C3)%nb; |
199 |
} |
200 |
|
201 |
N=rinst->Nb*(rinst->Nr+1); |
202 |
|
203 |
for (i=j=0;i<rinst->Nk;i++,j+=4) |
204 |
{ |
205 |
CipherKey[i]=pack(&key[j]); |
206 |
} |
207 |
for (i=0;i<rinst->Nk;i++) rinst->fkey[i]=CipherKey[i]; |
208 |
for (j=rinst->Nk,k=0;j<N;j+=rinst->Nk,k++) |
209 |
{ |
210 |
rinst->fkey[j]=rinst->fkey[j-rinst->Nk]^SubByte(ROTL24(rinst->fkey[j-1]))^rco[k]; |
211 |
if (rinst->Nk<=6) |
212 |
{ |
213 |
for (i=1;i<rinst->Nk && (i+j)<N;i++) |
214 |
rinst->fkey[i+j]=rinst->fkey[i+j-rinst->Nk]^rinst->fkey[i+j-1]; |
215 |
} |
216 |
else |
217 |
{ |
218 |
for (i=1;i<4 &&(i+j)<N;i++) |
219 |
rinst->fkey[i+j]=rinst->fkey[i+j-rinst->Nk]^rinst->fkey[i+j-1]; |
220 |
if ((j+4)<N) rinst->fkey[j+4]=rinst->fkey[j+4-rinst->Nk]^SubByte(rinst->fkey[j+3]); |
221 |
for (i=5;i<rinst->Nk && (i+j)<N;i++) |
222 |
rinst->fkey[i+j]=rinst->fkey[i+j-rinst->Nk]^rinst->fkey[i+j-1]; |
223 |
} |
224 |
|
225 |
} |
226 |
|
227 |
/* now for the expanded decrypt key in reverse order */ |
228 |
|
229 |
for (j=0;j<rinst->Nb;j++) rinst->rkey[j+N-rinst->Nb]=rinst->fkey[j]; |
230 |
for (i=rinst->Nb;i<N-rinst->Nb;i+=rinst->Nb) |
231 |
{ |
232 |
k=N-rinst->Nb-i; |
233 |
for (j=0;j<rinst->Nb;j++) rinst->rkey[k+j]=InvMixCol(rinst->fkey[i+j]); |
234 |
} |
235 |
for (j=N-rinst->Nb;j<N;j++) rinst->rkey[j-N+rinst->Nb]=rinst->fkey[j]; |
236 |
} |
237 |
|
238 |
|
239 |
/* There is an obvious time/space trade-off possible here. * |
240 |
* Instead of just one ftable[], I could have 4, the other * |
241 |
* 3 pre-rotated to save the ROTL8, ROTL16 and ROTL24 overhead */ |
242 |
|
243 |
void _mcrypt_rijndael_encrypt(RI *rinst, word8 *buff) |
244 |
{ |
245 |
int i,j,k,m; |
246 |
word32 a[8],b[8],*x,*y,*t; |
247 |
|
248 |
for (i=j=0;i<rinst->Nb;i++,j+=4) |
249 |
{ |
250 |
a[i]=pack(&buff[j]); |
251 |
a[i]^=rinst->fkey[i]; |
252 |
} |
253 |
k=rinst->Nb; |
254 |
x=a; y=b; |
255 |
|
256 |
/* State alternates between a and b */ |
257 |
for (i=1;i<rinst->Nr;i++) |
258 |
{ /* rinst->Nr is number of rounds. May be odd. */ |
259 |
|
260 |
/* if rinst->Nb is fixed - unroll this next |
261 |
loop and hard-code in the values of fi[] */ |
262 |
|
263 |
for (m=j=0;j<rinst->Nb;j++,m+=3) |
264 |
{ /* deal with each 32-bit element of the State */ |
265 |
/* This is the time-critical bit */ |
266 |
y[j]=rinst->fkey[k++]^ftable[(word8)x[j]]^ |
267 |
ROTL8(ftable[(word8)(x[rinst->fi[m]]>>8)])^ |
268 |
ROTL16(ftable[(word8)(x[rinst->fi[m+1]]>>16)])^ |
269 |
ROTL24(ftable[x[rinst->fi[m+2]]>>24]); |
270 |
} |
271 |
t=x; x=y; y=t; /* swap pointers */ |
272 |
} |
273 |
|
274 |
/* Last Round - unroll if possible */ |
275 |
for (m=j=0;j<rinst->Nb;j++,m+=3) |
276 |
{ |
277 |
y[j]=rinst->fkey[k++]^(word32)fbsub[(word8)x[j]]^ |
278 |
ROTL8((word32)fbsub[(word8)(x[rinst->fi[m]]>>8)])^ |
279 |
ROTL16((word32)fbsub[(word8)(x[rinst->fi[m+1]]>>16)])^ |
280 |
ROTL24((word32)fbsub[x[rinst->fi[m+2]]>>24]); |
281 |
} |
282 |
for (i=j=0;i<rinst->Nb;i++,j+=4) |
283 |
{ |
284 |
unpack(y[i],&buff[j]); |
285 |
x[i]=y[i]=0; /* clean up stack */ |
286 |
} |
287 |
return; |
288 |
} |
289 |
|
290 |
void _mcrypt_rijndael_decrypt(RI *rinst, word8 *buff) |
291 |
{ |
292 |
int i,j,k,m; |
293 |
word32 a[8],b[8],*x,*y,*t; |
294 |
|
295 |
for (i=j=0;i<rinst->Nb;i++,j+=4) |
296 |
{ |
297 |
a[i]=pack(&buff[j]); |
298 |
a[i]^=rinst->rkey[i]; |
299 |
} |
300 |
k=rinst->Nb; |
301 |
x=a; y=b; |
302 |
|
303 |
/* State alternates between a and b */ |
304 |
for (i=1;i<rinst->Nr;i++) |
305 |
{ /* rinst->Nr is number of rounds. May be odd. */ |
306 |
|
307 |
/* if rinst->Nb is fixed - unroll this next |
308 |
loop and hard-code in the values of ri[] */ |
309 |
|
310 |
for (m=j=0;j<rinst->Nb;j++,m+=3) |
311 |
{ /* This is the time-critical bit */ |
312 |
y[j]=rinst->rkey[k++]^rtable[(word8)x[j]]^ |
313 |
ROTL8(rtable[(word8)(x[rinst->ri[m]]>>8)])^ |
314 |
ROTL16(rtable[(word8)(x[rinst->ri[m+1]]>>16)])^ |
315 |
ROTL24(rtable[x[rinst->ri[m+2]]>>24]); |
316 |
} |
317 |
t=x; x=y; y=t; /* swap pointers */ |
318 |
} |
319 |
|
320 |
/* Last Round - unroll if possible */ |
321 |
for (m=j=0;j<rinst->Nb;j++,m+=3) |
322 |
{ |
323 |
y[j]=rinst->rkey[k++]^(word32)rbsub[(word8)x[j]]^ |
324 |
ROTL8((word32)rbsub[(word8)(x[rinst->ri[m]]>>8)])^ |
325 |
ROTL16((word32)rbsub[(word8)(x[rinst->ri[m+1]]>>16)])^ |
326 |
ROTL24((word32)rbsub[x[rinst->ri[m+2]]>>24]); |
327 |
} |
328 |
for (i=j=0;i<rinst->Nb;i++,j+=4) |
329 |
{ |
330 |
unpack(y[i],&buff[j]); |
331 |
x[i]=y[i]=0; /* clean up stack */ |
332 |
} |
333 |
return; |
334 |
} |
335 |
#if 0 |
336 |
int main() |
337 |
{ /* test driver */ |
338 |
int i,j,n,nb,nk; |
339 |
word8 y,x,m; |
340 |
char key[32]; |
341 |
char block[32]; |
342 |
|
343 |
gentables(); |
344 |
|
345 |
for (i=0;i<32;i++) key[i]=0; |
346 |
key[0]=1; |
347 |
for (i=0;i<32;i++) block[i]=i; |
348 |
|
349 |
for (nb=4;nb<=8;nb+=2) |
350 |
for (nk=4;nk<=8;nk+=2) |
351 |
{ |
352 |
printf("\nBlock Size= %d bits, Key Size= %d bits\n",nb*32,nk*32); |
353 |
gkey(nb,nk,key); |
354 |
printf("Plain= "); |
355 |
for (i=0;i<nb*4;i++) printf("%2x",block[i]); |
356 |
printf("\n"); |
357 |
encrypt(block); |
358 |
printf("Encrypt= "); |
359 |
for (i=0;i<nb*4;i++) printf("%2x",(unsigned char)block[i]); |
360 |
printf("\n"); |
361 |
decrypt(block); |
362 |
printf("Decrypt= "); |
363 |
for (i=0;i<nb*4;i++) printf("%2x",block[i]); |
364 |
printf("\n"); |
365 |
} |
366 |
return 0; |
367 |
} |
368 |
|
369 |
#endif |