Rijndael S-box for a string of bits My question is more of a "can someone give me tips" rather than "can you do it for me"

I have been writing a C code implementation that takes a 32-char String in the form of binary (supposed to act as a 32-bit instruction) and divides it to four 8-char strings. Those four strings are converted to Hex and fed to a small code program that returns the Rijndael S-box Forward and Inverse equivalent.

When I showed the code to my supervisor, he asked me to optimize the code I have. Even though after many iterations of changing different parts of the code and reducing the performance time slightly, I do not have ideas of how to improve it. So, the code is below, and I would be grateful for any tips and suggestions of how I can improve the performance of the code below. (Also, if you could suggest how to improve the amount of memory the code is using, that would be fabulous as well.)

#include &lt;stdio.h&gt;
#include &lt;string.h&gt;

unsigned char mulinv(unsigned char in) {
     //  multiplicative inverse in Rijndael's finite field.
    unsigned char k = 1, l = 1;
    //GF(2^8) = GF(2)[x]/(x8 + x4 + x3 + x + 1)
    //this takes the number of times I have to itterate in Rijndael's
    //finite field before I get my equivelant
    do {
        // equals k * 3 
        k = k ^ (k &lt;&lt; 1) ^ (k &amp; 0x80 ? 0x1B : 0);
        // equals l / 3
        l ^= l &lt;&lt; 1; l ^= l &lt;&lt; 2; l ^= l &lt;&lt; 4; l ^= l &amp; 0x80 ? 0x09 : 0;
        } while (k != in);
        return l;
}

unsigned char makesbox(unsigned char in) {
        unsigned char s, x, l;
        l = mulinv(in);
        // affine transformation
        s = l ^ ((l &lt;&lt; 1) | (l &gt;&gt; 7)) ^ ((l &lt;&lt; 2) | (l &gt;&gt; 6)) ^ ((l &lt;&lt; 3) | (l &gt;&gt; 5)) ^ ((l &lt;&lt; 4) | (l &gt;&gt; 4));
        x = s ^ 0x63;
        return x;       
} 

unsigned char invsbox(unsigned char in) {
        unsigned char x;
         // affine transformation
        x = ((in &lt;&lt; 1) | (in &gt;&gt; 7)) ^ ((in &lt;&lt; 3) | (in &gt;&gt; 5)) ^ ((in &lt;&lt; 6) | (in &gt;&gt; 2)) ^ 0x05;
        x = mulinv(x);
        return x;
}

void instSbox(unsigned char inst []) {
//        printf("Inst is : ");
        int i = 0;
//        for (i = 0; i &lt; 32; i++){
//                printf("%c", inst[i]);
//        }
        unsigned char in[9];
        printf("\n---------------|Byte|SBox\n");
        for (i = 0; i &lt; 33; i++){
                if (i%8 == 0 &amp;&amp; i != 0) {
                        in[8] = '\0'; //NUL terminate the string.
                        unsigned char t = (unsigned char) strtol(in, NULL, 2);
                        printf("0x%X ", t);
                        printf("0x%X ", makesbox(t));
                        printf("0x%X \n", invsbox(t));
        }
        in[i%8] = inst[i];
        printf("%c ", in[i%8]);
    }
}

void main(){

    unsigned char inst [32] = "10101010101010101111111100111101"; // 32 bits (length of instructions)
    instSbox(inst);
}
The indentation seems to have gone wrong. This may not be entirely your fault - the Stack Exchange backend converts tabs to spaces - but it makes it harder than it should be to match { and } on some blocks.



The obvious place to look for optimisation is mulinv. One way to speed it up is a logarithm table - basically, do the loop once to fill a table with all 256 cases, and then just look up values in the table. More sophisticated approaches are to use Euclid's algorithm for GCD on elements of \$GF(2^8)\$, or to consider the field \$GF(2^8)\$ as a tower of field extensions, \$GF(2)[x]/p(x)/q(x)\$, which makes it fairly simple to reduce the inversion to one in \$GF(16)\$. You can find more detailed explanations on another site from this network in a rather unusual challenge format: https://codegolf.stackexchange.com/q/9276/194



The rotations for the affine transforms also look ripe for optimisation. If you use a 16-bit integer then


        s = l ^ ((l &lt;&lt; 1) | (l &gt;&gt; 7)) ^ ((l &lt;&lt; 2) | (l &gt;&gt; 6)) ^ ((l &lt;&lt; 3) | (l &gt;&gt; 5)) ^ ((l &lt;&lt; 4) | (l &gt;&gt; 4));



can be replaced with

        uint16_t l16 = l;
        uint16_t t = l16 ^ (l16 &lt;&lt; 1) ^ (l16 &lt;&lt; 2) ^ (l16 &lt;&lt; 3) ^ (l16 &lt;&lt; 4);
        s = (unsigned char)(t ^ (t &gt;&gt; 8));


and similarly in invsbox.



Finally, a point on names. inst is completely cryptic to me with the context given. Perhaps you could use the full word, comment on the meaning, or consider whether in fact whatever word it abbreviates is inherently what is operated on or merely a specific application.