# 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 <stdio.h>
#include <string.h>

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 << 1) ^ (k & 0x80 ? 0x1B : 0);
// equals l / 3
l ^= l << 1; l ^= l << 2; l ^= l << 4; l ^= l & 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 << 1) | (l >> 7)) ^ ((l << 2) | (l >> 6)) ^ ((l << 3) | (l >> 5)) ^ ((l << 4) | (l >> 4));
x = s ^ 0x63;
return x;
}

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

void instSbox(unsigned char inst []) {
//        printf("Inst is : ");
int i = 0;
//        for (i = 0; i < 32; i++){
//                printf("%c", inst[i]);
//        }
unsigned char in[9];
printf("\n---------------|Byte|SBox\n");
for (i = 0; i < 33; i++){
if (i%8 == 0 && 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);
}

• Do you have to use strings, there are better ways to represent binary in C? – pacmaninbw Feb 24 '19 at 16:29
• my supervisor [] asked me to optimize the code Are you positive she was asking you to reduce time? While symmetric key encryption necessarily takes its own sweet time, substitution boxes don't get changed around. – greybeard Feb 24 '19 at 18:36
• Do be careful when optimizing - sometimes in cryptography, the fastest algorithm is insecure, as it leaks information to an adversary that can monitor timing and/or power consumption differences. – Toby Speight Feb 25 '19 at 14:06

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 << 1) | (l >> 7)) ^ ((l << 2) | (l >> 6)) ^ ((l << 3) | (l >> 5)) ^ ((l << 4) | (l >> 4));


can be replaced with

        uint16_t l16 = l;
uint16_t t = l16 ^ (l16 << 1) ^ (l16 << 2) ^ (l16 << 3) ^ (l16 << 4);
s = (unsigned char)(t ^ (t >> 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.

• I will for sure try the tower of field extensions idea. I just looked at the link you gave and from there found some good resources I can utilize. The affine transformation also looks interesting. the name inst is short of instruction (just to keep it in my mind that I will be feeding 32-bit instructions in form of binary as strings to this algorithm) – Ameer Shalabi Feb 25 '19 at 15:53