Rijndael S-box for a string of bits
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.