Return to Answer

• moves a bitof interest 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.

• moves a bit of interest 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 free from data-dependent timing variation¹. 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, mult1B_fast (perhaps, made inline) is close to the fastest portable constant-time C code. However, especially on CPUs lacking a barrel shifter, it may be worth trying the mult1B_shift8 variation, which only shifts by a whole byte: the above technique is applied on the high byte 16-bit variables, hence & 1 becomes &256. Assembly language often allows further gain, including thanks to direct access to the carry bit.

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.

No, because full field multiplication is not necessary (also see note¹). Except for computation of the S-box, a natural implementation of AES encryption² (including AES decryption in CTR mode) only needs multiplication by 2. Using the same technique as above, that can be coded as one of:

inline uint8_t double1B(uint8_t a) {
    return (-(a>>7) & 0x1B) ^ (a+a);
}

inline uint8_t double1B_shift8(uint8_t a) {
    uint16_t r = a+a;
    return ((-(r & 256))>>8 & 0x1B) ^ r;
}

² One such natural implementation is there. It is typically free from data-dependent timing variation on CPUs without a data cache when the two 256-byte tables are aligned to a 256-byte boundary. One of these tables is replaceable by double1B, the other is the S-box.

For most platforms, this generates code free from data-dependent timing variation¹. 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, mult1B_fast (perhaps, made inline) is close to the fastest portable C code free from data-dependent timing variation. However, especially on CPUs lacking a barrel shifter, it may be worth trying the mult1B_shift8 variation, which only shifts by a whole byte: the above technique is applied on the high byte 16-bit variables, hence & 1 becomes &256. Assembly language often allows further gain, including thanks to direct access to the carry bit.

Note: Bogus compiler/tool warning on the tune of «unary minus operator applied to unsigned type, result still unsigned» can be silenced, perhaps by changing the occurrences of -( to 0-(. Add parenthesis to satisfy any enforced convention.

No, because full field multiplication is not necessary (also see note¹). Except for computation of the S-box, a natural implementation of AES encryption² (including AES decryption in CTR mode) only needs field multiplication by the field element $x$, encoded 2. Using the same technique as above, that can be coded as one of:

inline uint8_t mul1B_x(uint8_t a) {
    return (-(a>>7) & 0x1B) ^ (a+a);
}

inline uint8_t mul1B_x_shift8(uint8_t a) {
    uint16_t r = a+a;
    return ((-(r & 256))>>8 & 0x1B) ^ r;
}

² One such natural implementation is there. It is typically free from data-dependent timing variation on CPUs without a data cache when the two 256-byte tables are aligned to a 256-byte boundary. One of these tables is replaceable by mul1B_x, the other is the S-box.

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

On many platforms, mult1B_fast (perhaps, made inline) is close to the fastest portable constant-time C code. However, especially on CPUs lacking a barrel shifter, it may be worth trying the mult1B_shift8 variation, which only shifts by a whole byte. Especially on 8-bit CPUs, assembly language often allows further gain thanks to direct access to the carry bit.

In C, multiplication in the field $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ can be coded as one of these three functionally equivalent functions:

On many platforms, mult1B_fast (perhaps, made inline) is close to the fastest portable constant-time C code. However, especially on CPUs lacking a barrel shifter, it may be worth trying the mult1B_shift8 variation, which only shifts by a whole byte: the above technique is applied on the high byte 16-bit variables, hence & 1 becomes &256. Assembly language often allows further gain, including thanks to direct access to the carry bit.