Return to Revisions

In C, multiplication in the field $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ can go (two functionally equivalent versions):

#include <stdint.h> // bring type uint8_t used for a field element

uint8_t mult1B_compact(uint8_t a, uint8_t b) {
    uint8_t r = 0, i = 8;
    while(i)
        r = (-(b>>--i & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    return r;
}

uint8_t mult1B_fast(uint8_t a, uint8_t b) {
    uint8_t r;
    r = (-(b>>7    ) & a);
    r = (-(b>>6 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>5 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>4 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>3 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>2 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
    r = (-(b>>1 & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
 return (-(b    & 1) & a) ^ (-(r>>7) & 0x1B) ^ (r+r);
}

This code extensively uses a generic technique, applicable to many other languages: it moves a desired bit to the low-order bit of a byte using right-shift >>, isolates it with & 1 if necessary, applies the unary operator - to change 1 to 0xFF…FF (leaving 0unchanged), then uses the outcome as a byte mask.

For most platforms, this is constant time. I know no exception, but still that should be checked, e.g. by inspection of the generated code, and in theory invoking/verifying considerations about what influences the execution time of an instruction on each of the target CPUs.

On many platforms with a barrel shifter, mult1B_fast (perhaps, made inline) is next to the fastest portable constant-time code. On platforms where shift time is proportional to the shift count, there are better options.

Note: This technique leaves other side channels wide open, in particular power analysis.

Note: demonstrating constant-timeness is very difficult in some non-compiled languages. For example, the most minute details about the runtime environment in theory needs to be taken into account; like, what heuristic a Java JITC uses.

Note: Silence any bogus compiler/tool warning on the tune of unary minus operator applied to unsigned type, result still unsigned, perhaps by changing the occurrences of -( to 0-(. Add parenthesis to satisfy any required convention.