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