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